An objective formulation of membership function based on fuzzy entropy and pairwise comparison

2.1 Civarnlar and Trussell’s model

As a mathematical approach to obtain a membership function objectively, Civanlar and Trussell [7] considered minimizing fuzziness of MF based on the PDF derived from real-world data. The continuous MF μ (x) is obtained by solving the following mathematical programming problem under given PDF p (x):

Minimize 1 2 ∫ - ∞ ∞ μ 2 ( x ) dx subject to ∫ - ∞ ∞ μ ( x ) p ( x ) dx ≥ C , 0 ≤ μ ( x ) ≤ 1 , ∀ x ∈ R(1)

The objective function is to minimize fuzziness of μ (x), that is, it means that the size of a fuzzy set is as small as possible [7]. As an important constraint in problem (1), the total expected membership value E ( x ) = ∫ - ∞ ∞ μ ( x ) p ( x ) dx is more than the target value C. For instance, if C is a large and close to 1, the obtained μ (x) is similar to a function whose membership values satisfying p (x) > 0 are 1. On the other hand, if C is a small and close to 0, μ (x) is similar to a function whose values are 0 in almost all x. Therefore, it is important to flexibly and interactively set C according to the decision maker’s feelings. In addition, we consider set I with discrete random events {x₁, x₂, … , x _n  } and p _i is the corresponding probability of event x _i , and the discrete formulation of problem (1) is also obtained as follows:

Minimize 1 2 ∑ k = 1 n μ k 2 subject to ∑ k = 1 n μ k p k ≥ C , 0 ≤ μ k ≤ 1 , k = 1 , 2 , … , n(2) where μ _k  = μ (x _k ).

Various definitions of fuzzy entropy have been proposed (for instance, Al-sharhan and Karray [1], Nieradka and Butkiewicz [17], Pal and Bezdek [18]). For instance, Shannon entropy for random events is one of the most standard entropies in information theory, and formulated as - ∑ i = 1 n p i log p i . Some researchers have extended Shannon entropy to fuzzy entropy transforming each probability p _i into corresponding membership values μ _i which is simply defined as - ∑ i = 1 n μ i log μ i . Of course, continuous fuzzy Shannon entropy is also defined as - ∫ - ∞ ∞ μ ( x ) log μ ( x ) dx . In addition, it is possible to represent fuzzy Shannon entropy as - ∑ i = 1 n { μ i log μ i + ( 1 - μ i ) log ( 1 - μ i ) } which is very similar to the standard Shannon entropy in the case of binary discrete random variables. In order to develop an efficient constructing approach, we focus on the simple form of discrete fuzzy Shannon entropy - ∑ i = 1 n μ i log μ i .

On the other hand, as a natural extension of Shannon entropy, Harvda and Charvat [12] defined the following entropy: 1 q - 1 ( 1 - ∑ i = 1 n p i q ) , ( q > 0 , q ≠ 1 )(3)

If we consider q → 1, (3) is equivalently transformed into Shannon entropy - ∑ i = 1 n p i log p i [15], and hence, Harvda and Charvat entropy is a natural extension of Shannon entropy. Furthermore, the fuzzification of Harvda and Charvat entropy is simply introduced as follows: 1 q - 1 ( 1 - ∑ i = 1 n μ i q ) , ( q > 0 , q ≠ 1 )(4)

In addition, we consider maximizing simple fuzzy Harvda and Charvat entropy (4), and can equivalently transform the following form in the case q = 2:

Maximize 1 2 - 1 ( 1 - ∑ i = 1 n μ i 2 ) ⇔ Maximize 1 - ∑ i = 1 n μ i 2 ⇔ Minimize ∑ i = 1 n μ i 2(5)

Therefore, Civarnlar and Trussell’s model is the same as the Harvda and Charvat entropy-based model under q = 2.

In real-world decision making, it is often subjective to determine a specific MF such as trapezoidal and Gaussian functions, and hence, it is not appropriate to apply the optimal solution straightforwardly. In statistics and machine learning, a piecewise linear function is introduced as a general nonlinear function, because almost all nonlinear functions are approximately formulated as a corresponding piecewise linear function. Therefore, it is natural to introduce a piecewise linear membership function as a general MF. In order to formulate a piecewise linear function, we divide received data into n groups and set I k = { a k - 1 ≤ x ≤ a k } = [ a k - 1 , a k ] , ( k = 1 , 2 , … , n )

In I _k , we introduce the following piecewise linear function: f ( x ) = c k - c k - 1 a k - a k - 1 ( x - a k - 1 ) + c k - 1 , ( x ∈ I k )

In the case that the MF is determined by using this linear membership function, parameters c_k-1 and c _k are replaced as membership values μ k L and μ k U , respectively. The parameter setting also holds μ k - 1 U = μ k L , ∀ k ∈ { 1 , 2 , … , n } under μ 1 L = 0 and μ n U = 1 which are boundary conditions derived from decision maker’s interval estimation.

In this paper, we assume that PDF p (x) is a histogram, i.e., ∫_{x∈I k} p (x) dx = p _k ,  ∀ x ∈ I _k . Of course, our proposed approach can be apply to any PDFs, but we focus on the histogram which can be constructed from only received data without assuming the specific PDF. In this case, it is also natural to divide intervals including all data into same width, that is, a _k  - a_k-1 = T, ∀ k ∈ { 1, 2, …, n } holds. Furthermore, from this assumption, we can consider optimizing each intermediate value μ _k based on μ k = μ k L + μ k U 2 instead of optimizing parameters μ k L and μ k U , because μ k L and μ k U are automatically set by obtaining optimal value μ _k from linearity on I _k and boundary conditions μ 1 L = 0 and μ n U = 1 .

2.4 Subjective and objective evaluation of utility function based on mathematical programming

Yoshizumi [21] proposed a method to objectively determine a utility function from the decision maker’s qualitative and subjective evaluations. The idea is to use a scale for measuring such as the Likert scale based on paired differences of two feasible solutions, and to formulate these differences as constraints in mathematical programming.

We assume that the utility function consists of K metrics which is represented as y  = (y₁, y₂, …, y _K ). For instance, as a simple utility function, the following weighted sum function is assumed: f w ( y ) = ∑ k = 1 K w k y k(6) where w _k ,  (k = 1, 2, …, K) is the weight to each factor. Using (6), we consider that a decision maker’s evaluations are “Solution i is better than solution j.” and “Solution s is far better than solution k.” In the case we consider only the magnitude relation between two solutions, the following simple inequalities hold:

f w ( y ( i ) ) > f w ( y ( j ) ) f w ( y ( s ) ) > f w ( y ( k ) )(7)

However, this formulation cannot represent the difference between “better than” and “far better than” strictly. Therefore, Yoshizumi [21] introduced the following definition each boundary.

A decision maker evaluates that solution i is “similar to” solution j.

This situation represents 3 point satisfaction of Likert scale. Of course, it is easy to define 5 or 7 point satisfaction in the same manner. We define R₀ = R_≈, R₁ = R_> and R₂ = R_>> in the above-mentioned 3 point satisfaction.

From these definitions, the decision maker’s pairwise comparison of n alternative solutions is mathematically represented as the following constraints: - b 0 ≤ f w ( y ( i ) ) - f w ( y ( j ) ) + ɛ ij ≤ b 0 , ∀ ( i , j ) ∈ R 0(8) b u - 1 ≤ f w ( y ( i ) ) - f w ( y ( j ) ) + ɛ ij ≤ b u , ∀ ( i , j ) ∈ R u where ɛ _ij is error term derived from the pairwise comparison and b _u is the boundary value to divide two scales initially set by the decision maker. For instance, constraints (7) are reformulated as follows using formula (8): b 0 ≤ f w ( y ( i ) ) - f w ( y ( j ) ) + ɛ ij ≤ b 1 , b 1 ≤ f w ( y ( s ) ) - f w ( y ( k ) ) + ɛ sk ≤ b 2

Under these constraints, the optimal weight in the decision maker’s utility function is obtained to solve the following problem [21]:

Minimize w ∑ i = 1 n ∑ j = 1 n ɛ ij subject to - b 0 ≤ f w ( y ( i ) ) - f w ( y ( j ) ) + ɛ ij ≤ b 0 , ∀ ( i , j ) ∈ R 0 b u - 1 ≤ f w ( y ( i ) ) - f w ( y ( j ) ) + ɛ ij ≤ b u , ∀ ( i , j ) ∈ R u ∑ k = 1 K w k = 1 , 0 ≤ w k ≤ 1 , ( k = 1 , 2 , … , K )(9)

This problem is a linear programming problem of w , and hence, it is easy to obtain the optimal weight w ^* and the corresponding appropriate utility function f _{w ^*}  ( y ). In the case of MF, f _w  ( y ) is transformed into μ (x).

The main objective function of our approach is to maximize the fuzzy Harvda-Charvat entropy. The available data is histogram-based PDF p _k corresponding to I _k derived from real-world data and information of pairwise comparison by the decision maker. Constraints are based on Civanlar and Trussell study [6]. In addition, from the pairwise comparison using the interview or questionnaire to the decision maker such as Likert scale, membership values at the intermediate value a ¯ k = a k - 1 + a k 2 of piecewise linear MF are interactively set. For instance, if the decision maker considers 5 point satisfaction of Likert scale; “same as”, “a little higher than”, “intermediately higher than”, “higher than”, “much higher than” in terms of membership value and evaluate “membership value of a ¯ k is higher than that of a ¯ k - 1 ”, the following inequality is introduced based on subsection II-D: b 2 ≤ μ k - μ k - 1 + ɛ k , k - 1 ≤ b 3

From the received pairwise comparison by decision maker, the appropriate MF is obtained as the optimal solution of the following problem to integrate problem (2) with formulas (4) and (9): Maximize 1 q - 1 ( 1 - ∑ k = 1 n μ k q ) - W ∑ i = 1 n ∑ i < j n ɛ ij

subject to ∑ k = 1 n μ k p k ≥ C , - b 0 ≤ μ i - μ j + ɛ ij ≤ b 0 , ∀ ( i , j ) ∈ R 0 b u - 1 ≤ μ i - μ j + ɛ ij ≤ b u , ∀ ( i , j ) ∈ R u 0 ≤ μ k ≤ 1 , ( k = 1 , 2 , … , n )(10) i.e. Minimize 1 1 - q ( 1 - ∑ k = 1 n μ k q ) + W ∑ i = 1 n ∑ i < j n ɛ ij

subject to ∑ k = 1 n μ k p k ≥ C , - b 0 ≤ μ i - μ j + ɛ ij ≤ b 0 , ∀ ( i , j ) ∈ R 0 b u - 1 ≤ μ i - μ j + ɛ ij ≤ b u , ∀ ( i , j ) ∈ R u 0 ≤ μ k ≤ 1 , ( k = 1 , 2 , … , n )(11) where W is the weight for ∑ i = 1 n ∑ i < j n ɛ ij comparing with Harvda-Charvat entropy 1 1 - q ( 1 - ∑ k = 1 n μ k q ) . In the following discussion, we consider cases ∑ k = 1 n μ k p k = C and q > 1 without loss of optimality. This problem is a convex programming problem, and hence, the decision maker obtains the optimal membership value using nonlinear programming problem. However, it may be difficult to obtain it rapidly and efficiently. In addition, it is also difficult to set parameter C strictly, because the total expected membership value is an indirect measure to evaluate the decision maker’s feeling. Therefore, in the next subsection, we divide problem (11) into subproblems, and develop an efficient algorithm to set parameter C derived from information of pairwise comparison and to obtain the optimal membership value.

In this subsection, we divide problem (11) into two problem: (i) linear programming problem based on problem (9) to obtain the baseline membership value, and (ii) convex programming problem which is a simplification of problem (11). The first problem (i) is formulated as follows:

Minimize ∑ i = 1 n ∑ i < j n ɛ ij subject to - b 0 ≤ μ i - μ j + ɛ ij ≤ b 0 , ∀ ( i , j ) ∈ R 0 b u - 1 ≤ μ i - μ j + ɛ ij ≤ b u , ∀ ( i , j ) ∈ R u 0 ≤ μ k ≤ 1 , ( k = 1 , 2 , … , n )(12)

The decision variables are μ _i and ɛ _ij , and this problem is a linear programming problem. Therefore, we can efficiently obtain the optimal value of problem (12). In this subsection, the optimal value is represented as μ ˆ i , and we consider μ ˆ i as a baseline membership value of problem (11). In addition, we set parameter C as C ˆ = ∑ k = 1 n μ ˆ k p k . In previous approaches, parameter C is initially set by the decision maker by trial and error. On the other hand, parameter C is objectively set to solve problem (12) based on subjective pairwise comparison, and hence, this paper’s approach will be improved more than previous approaches.

Next, we focus on the second problem (11). In order to obtain the explicit optimal membership value, we propose the following problem introducing adjustment values μ k q and ∑ k = 1 n μ ˆ k q p k = C ˆ a :

Minimize 1 1 - q ( 1 - ∑ k = 1 n μ k q ) + W ′ ( μ k q - μ ˆ k q ) 2 subject to ∑ k = 1 n μ k q p k = C ˆ a , 0 ≤ μ k q ≤ 1 , ( k = 1 , 2 , … , n )(13) where W′ is the penalty value to differences between adjustment optimal membership value μ k q and adjustment baseline membership value μ ˆ k q . W′ is set as a positive value corresponding to decision maker’s feeling. If W′ is large, the decision maker considers the optimal membership value is closed to the baseline membership value.

In problem (13), without loss of optimality, we substitute μ k q into μ k ′ and reformulate problem (13) as follows:

Minimize 1 1 - q ( 1 - ∑ k = 1 n μ k ′ ) + W ′ ( μ k ′ - μ ˆ k q ) 2 subject to ∑ k = 1 n μ k ′ p k = C ˆ a , 0 ≤ μ k ′ ≤ 1 , ( k = 1 , 2 , … , n )(14)

This problem is a simple extension of Civanlar and Trussell problem (2) considering the balance from baseline membership values. The Lagrange function is also obtained as follows:

L = 1 1 - q ( 1 - ∑ k = 1 n μ k ′ ) + W ′ ( μ k ′ - μ ˆ k q ) 2 + λ ( C ˆ a - ∑ k = 1 n μ k ′ p k ) + ∑ k = 1 n α k ( μ k ′ - 1 ) - ∑ k = 1 n β k μ k ′(15) where λ is the Lagrange multiple. The KKT condition is calculated as follows: { - 1 1 - q + 2 W ′ ( μ k ′ - μ ˆ k q ) - λ p k + α k - β k = 0 , ∑ k = 1 n μ k ′ p k = C ˆ a , α k ( μ k ′ - 1 ) = 0 , β k μ k ′ = 0 , ( k = 1 , 2 , … , n )(16)

With respect to first Equation in (16), there are three patterns of optimal membership values μ k ′ as follows: μ k ′ = { 1 ( M k U < λ ) μ k ′ * ( M k L ≤ λ ≤ M k U ) 0 ( λ < M k L ) M k L = 1 p k ( - 2 W ′ μ ˆ k q - 1 1 - q )(17) M k U = 1 p k ( 2 W ′ ( 1 - μ ˆ k q ) - 1 1 - q )

To simplify the following discussion, we consider that M k L ≤ λ ≤ M k U on all k = 1, 2, …, n. If some optimal values become 0 and 1, we recalculate ∑ k = 1 n μ k ′ p k = ∑ k ∈ P 1 p k + ∑ k ∈ P * μ k ′ * p k where P₁ is the set of indices with 1 and P_* is the set of indices with μ k ′ * , and reset ∑ k ∈ P * μ k ′ * p k = C ˆ a = ∑ k ∈ P 1 p k = C ˆ a ′ . In this case, we can formulate the similar problem of problem (14).

The optimal value μ k ′ in (16) under 0 < μ k ′ < 1 is obtained as the following form with Lagrange multiple λ:

- 1 1 - q + 2 W ′ ( μ k ′ - μ ˆ k q ) - λ p k = 0 ⇔ 2 W ′ ( μ k ′ - μ ˆ k q ) = λ p k + 1 1 - q ⇔ μ k ′ = μ ˆ k q + p k 2 W ′ λ + 1 2 W ′ ( 1 - q )(18)

We assign the optimal value μ k ′ of (18) into constraint ∑ k = 1 n μ k ′ p k = C ˆ a , and calculate optimal value of λ as follows:

∑ k = 1 n μ k ′ p k = C ˆ a ⇔ ∑ k = 1 n μ ˆ k q p k + λ 2 W ′ ∑ k = 1 n p k 2 + 1 2 W ′ ( 1 - q ) ∑ k = 1 n p k = C ˆ a ⇔ C ˆ a + ( 1 2 W ′ ∑ k = 1 n p k 2 ) λ + 1 2 W ′ ( 1 - q ) = C ˆ a ⇔ λ * = - 1 ( 1 - q ) ∑ k = 1 n p k 2(19)

The membership value μ k ′ * is obtained as the following explicit form:

μ k ′ * = μ ˆ k q + p k 2 W ′ λ * + 1 2 W ′ ( 1 - q ) = μ ˆ k q + 1 2 W ′ ( 1 - q ) ( 1 - p k ∑ k = 1 n p k 2 )(20)

Therefore, the optimal membership function μ k * is obtained as follows:

μ k * = ( μ k ′ * ) 1 / q = ( μ ˆ k q + 1 2 W ′ ( 1 - q ) ( 1 - p k ∑ k = 1 n p k 2 ) ) 1 / q(21)

If we find parameter ramda

From these discussions and interactive setting based on the decision maker’s pairwise comparison, the following interactive constructing approach to obtain the strict membership value is developed.

Interactive and efficient approach to obtain the membership value

Step 1: Set histogram-based PDF p _k from real-world data and the intervals with membership values 0 and 1. Do the pairwise comparison by questionnaires such as 5 point satisfaction. Set parameter b _u for the boundary between two categories. Go to Step 2.

Step 2: Solve problem (12) and obtain baseline membership value μ ˆ k and parameters C ˆ = ∑ k = 1 n μ ˆ k p k and C ˆ a = ∑ k = 1 n μ ˆ k q p k . Go to Step 3

Step 3: Solve problem (13) and obtain the optimal membership value μ k * as shown in (21). Go to Step 4.

Step 4: The decision maker compares optimal membership value μ k * with baseline membership value μ ˆ k . If the decision maker is satisfied with the current membership function, terminate this algorithm. If not, revise the pairwise comparison, parameter b _u or penalty value W′ interactively, and return to Step 2.

In Step 4, if the decision maker considers that the that the difference between μ k * and μ ˆ k is too large, we reset a larger penalty value W′. Furthermore, we advance some baseline MFs and the corresponding MF by changing values of parameter b _u , we can construct the appropriate MF for the decision maker interactively.

Using the proposed approach, all parameters are straightforwardly calculated. Furthermore, in terms of fuzzy entropy, fuzzy Harvda and Charvat entropy includes fuzzy Shannon entropy as a special case. Therefore, our proposed approach is also more efficient and more versatile than previous approaches.