Fuzzy orthopartitions and their logical entropy Stefania Boffa, Davide Ciucci Università degli Studi di Milano-Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336 – 20126, Milano, Italy Abstract In this paper, we present special families of intuitionistic fuzzy sets called fuzzy orthopartitions, which are generalizations of standard fuzzy partitions useful to model situations where both vagueness and uncertainty are involved. Moreover, we define and explain how to compute the lower and upper entropy, which measure the quantity of information contained in a fuzzy orthopartition. Keywords Entropy, Ruspini Partitions, Intuitionistic Fuzzy Sets, Orthopartitions 1. Introduction The first purpose of the present work is to introduce the so-called fuzzy orthopartitions, which are generalized (fuzzy) partitions involving both vagueness and uncertainty. A fuzzy orthopartition is mathematically defined as a collection of intuitionistic fuzzy sets satisfying specific properties. An intuitionistic fuzzy set A of a universe U is a pair (µA , νA ), where µA and νA are functions from U to [0, 1] such that µA (u) + νA (u) ≤ 1 for each u ∈ U , and are respectively called the membership and non-membership functions of A. Moreover, the hesitation margin of an element u of U , given by hA (u) = 1 − (µA (u) + νA (u)), expresses the degree of indeterminacy of u to A [1, 2]. Intuitionistic fuzzy sets can be seen as extensions of both orthopairs and fuzzy sets. More precisely, an orthopair (M, N ) of U , i.e. a pair of disjoint subsets of U [3], is viewed as an intuitionistic fuzzy set (µ, ν) such that µ(u) = 1 if u ∈ M , and µ(u) = 0 otherwise, while ν(u) = 1 if u ∈ N , and ν(u) = 0 otherwise. Furthermore, each fuzzy set π on U , i.e. π : U → [0, 1], is identified with an intuitionistic fuzzy set (π, 1 − π) such that (1 − π)(u) = 1 − π(u) for each u ∈ U . Analogously, fuzzy orthopartitions are considered generalizations of both classical orthopar- titions and Ruspini (fuzzy) partitions. Orthopartitions are generalized partitions where the membership class of some elements of the initial universe is not precisely known [4]. Mathematically, an orthopartition of U is a family O = {(M1 , N1 ), . . . , (Mn , Nn )} of orthopairs of U satisfying the following properties: they are mutually disjoint, i.e. Mi ∩Mj = ∅ and Mi ∩Bj = ∅ for each i 6= j, where Bj = U \(Mj ∪Nj ); the union of P1 ∪ . . . ∪ Pn and B1 ∪ . . . Bn covers U ; for each u ∈ U , if u ∈ Bi then there exits WILF’21 WILF 2021:The 13th International Workshop on Fuzzy Logic and Applications, December 20-22, 2021, Vietri sul Mare, Italy ! stefania.boffa@unimib.it (S. Boffa); davide.ciucci@unimib.it (D. Ciucci) ! 0000-0002-4171-3459 (S. Boffa); 0000-0001-7116-9338 (D. Ciucci) Copyright for this paper by its authors. macro © 2021 Author:Pleasefillinthe\copyrightclause Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Wor Pr ks hop oceedi ngs ht I tp: // ceur - SSN1613- ws .or 0073 g CEUR Workshop Proceedings (CEUR-WS.org) j 6= i such that u ∈ Bj ; the number of orthopairs of O is less than or equal to the cardinality of U 1. Ruspini partitions are generalized partitions where elements of the initial universe belong to the blocks with a membership degree of [0,1] [5]. Mathematically, a Ruspini partition of U is a family π = {π1 , . . . , πn } of fuzzy sets on U such that π1 (u) + . . . + πn (u) = 1 for each u ∈ U . The second purpose of this work is to present the concepts of logical entropy of a Ruspini partition, and lower and upper entropy of a fuzzy orthopartition. All of them are extensions of the logical entropy of a classical partition introduced in [6]. The logical entropy measures the quantity of information associated with a partition of a finite universe, and its definition is based on the notion of distinction (or dit) considered the atom of information. Given a partition π of U , a distinction is a pair of elements of U that belong to different blocks of π. Therefore, the logical entropy of a partition is mathematically defined as the number of distinctions normalized by the number of ordered pairs of U . We point out that our approach is different from that shown in [7]. More precisely, our measure of entropy in the intuitionistic fuzzy case is based on the generalized notion of distinction, while the authors in [7] provide the logical entropy definition of special collections of intuitionistic fuzzy sets representing the results of a random experiment and so, characterized by a probability distribution. Finally, we notice that we decided to generalize the logical entropy instead of the Shannon one, since already in the crisp orthopartition case, calculating the Shannon entropy is computationally intractable [4]. In the sequel, we will provide all concepts and notions by assuming that our universe is finite. 2. Fuzzy orthopartitions This section principally presents the notion of fuzzy orthopartitions. A fuzzy orthopartition is a generalized partition, where an element u of the initial universe belongs to a block represented by the intuitionistic fuzzy set (µi , νi ) with a degree of the interval [µi (u), µi (u) + hi (u)] that is not precisely known. Definition 1. Let O = {(µ1 , ν1 ), . . . , (µn , νn )} be a finite family of intuitionistic fuzzy sets of U . Then, O is a fuzzy orthopartition of U if and only if the followings hold for each u ∈ U : Pn (a) i=1 µi (u) ≤ 1, (b) µi (u) + hj (u) ≤ 1, for each i 6= j, Pn (c) i=1 µi (u) + hi (u) ≥ 1, (d) for each i ∈ {1, . . . , n} with hi (u) > 0, there exists j ∈ {1, . . . , n}\{i} such that hj (u) > 0. Axioms (a) and (b) capture the idea that intuitionistic fuzzy sets of O must represent mutually disjoints blocks of U , and Axiom (c) corresponds to the covering condition. The following theorem shows that Axiom (d) allows fuzzy orthopartitions to be extensions of crisp orthopartitions. 1 In this paper, we deal with more general orthopartitions, where the last property can be unsatisfied. Theorem 1. Let O = {(µ1 , ν1 ), . . . , (µn , νn )} be a fuzzy orthopartition of U such that µi (u), νi (u) ∈ {0, 1}, for each u ∈ U and i ∈ {1, . . . , n}. Then, {(M1 , N1 ), . . . , (Mn , Nn )} is an orthopartition of U , where Mi = {u ∈ U | µi (u) = 1} and Ni = {u ∈ U | νi (u) = 1}, for each i ∈ {1, . . . , n}. Proof. Let i, j ∈ {1, . . . , n} such that i 6= j. If u ∈ Mi , then u cannot belong neither to Mj from Axiom (a) or to U \ (Mj ∪ Nj ) from Axiom (b). Therefore, (Mi , Ni ) and (Mj , Nj ) are disjoint. Suppose that there exists u ∈ U such that u ∈ Ni forP each i ∈ {1, . . . , n}. Then, since n (µ1 , ν1 ), . . . , (µn , νn ) are intuitionistic fuzzy sets, we get Si=1 µi (u) + hi (u) = 0. But, the latter contradicts Axiom (c). Consequently, we can conclude ni=1 (Mi ∪ Bi ) = U . Lastly, given u ∈ U and i ∈ {1, . . . , n}, hi (u) > 0 if and only if hi (u) = 1 (i.e. u ∈ Bi ), from hypothesis. Thus, Axiom (d) is equivalent to the third property of classical orthopartitions. Additionally, Ruspini partitions can be viewed as special fuzzy orthopartitions. More precisely, the following theorem holds. Theorem 2. Let π1 , . . . , πn be some fuzzy sets on U . Then, {π1 , . . . , πn } is a Ruspini partition if and only if {(π1 , 1 − π1 ), . . . , (πn , 1 − πn )} is a fuzzy orthopartition. Proof. The thesis clearly follows from Definition 1. By the previous theorem, each Ruspini partition is identified with a fuzzy orthopartition. Vice-versa, a fuzzy orthopartition corresponds to a collection of Ruspini partitions. Their definition is formulated by thinking that fuzzy orthopartitions approximate Ruspini partitions when the truth degree of elements of the initial universe is not exactly known. Definition 2. A Ruspini partition π = {π1 , . . . , πn } of U is compatible with a fuzzy orthopar- tition O = {(µ1 , ν1 ), . . . , (µn , νn )} of U if and only if µi (u) ≤ πi (u) ≤ µi (u) + hi (u) for each u ∈ U and i ∈ {1, . . . , n}. Moreover, we indicate with ΠO the set of all Ruspini partitions compatible with O. Example 1. Let U = {u}. We consider an orthopartition O = {(µ1 , ν1 ), (µ2 , ν2 ), (µ3 , ν3 )} of U , where µ1 (u) = 0.2, ν1 (u) = 0.6, µ2 (u) = 0.4, ν2 (u) = 0.3, µ3 (u) = 0.2, and ν3 (u) = 0.3. Then, π = {π1 , π2 , π3 } such that π1 (u) = 0.2, π2 (u) = 0.4 and π3 (u) = 0.4 is an example of Ruspini partition compatible with O. 3. Lower and upper entropy of fuzzy orthopartitions This section aims to generalize the logical entropy of standard partitions to Ruspini partitions and fuzzy orthopartitions. 3.1. Logical entropy of Ruspini partitions In this subsection, we provide the notion of logical entropy of a Ruspini partition. Given a Ruspini partition π of U , since the total membership degree of each element of U is distributed among all blocks of π, a pair of elements (u, u′ ) of U × U forms a distinction of π with a certain degree in [0, 1]. Therefore, we can generalize the concept of distinction to the case of Ruspini partitions by defining a fuzzy relation that assigns to each pair (u, u′ ) ∈ U × U the maximum of the distances between u and u′ w.r.t. all blocks of π. Definition 3. Let π = {π1 , . . . , πn } be a Ruspini partition of U . Then, we consider a fuzzy relation ditπ : U × U → [0, 1] such that let u, u′ ∈ U , ditπ(u, u′ ) = max{|πi (u) − πi (u′ )| such that i ∈ {1, . . . , n}}. (1) We call ditπ(u, u′ ) the degree of distinction of (u, u′ ), and it is interpreted as the capacity of π to distinguish u and u′ by means of its fuzzy sets π1 , . . . , πn . A Ruspini partition π = {π1 , . . . , πn } of U such that πi (u) ∈ {0, 1} for each u ∈ U and i ∈ {1, . . . , n}, corresponds to a crisp partition. Thus, it is easy to prove that a pair of elements is a distinction in the classical sense, i.e. it is made by elements of different blocks, if and only if the degree of distinction given by (1) is equal to 1. Proposition 1. Let π = {π1 , . . . , πn } be Ruspini partition of U such that πi (u) ∈ {0, 1} for each u ∈ U and i ∈ {1, . . . , n}. Then, ditπ(u, u′ ) = 1 if and only if there exist i, j ∈ {1, . . . , n} with i 6= j such that πi (u) = 1 and πj (u′ ) = 1. Proof. The thesis clearly follows from Definition 3. We now define the logical entropy of a Ruspini partition as the normalized sum of the degrees of distinctions of all pairs of the initial universe. Definition 4. Let π = {π1 , . . . , πn } be a Ruspini partition of U . Then, the logical entropy of π is given by ′ P (u,u′ )∈U ×U ditπ(u, u ) h(π) = . (2) |U × U | Finally, Proposition 1 implies h(π), given by (2), coincides with the standard logical entropy when π = {π1 , . . . , πn } and πi (u) ∈ {0, 1}, for each u ∈ U and i ∈ {1, . . . , n}. 3.2. Lower and upper entropy of fuzzy orthopartitions In this subsection, we define and explain how to compute the lower and upper entropy of a fuzzy orthopartition. Definition 5. Let O be a fuzzy orthopartition of U , the lower and upper entropy are respectively given by h∗ (O) = min{h(π) | π ∈ ΠO } and h∗ (O) = max{h(π) | π ∈ ΠO }.2 2 Let us recall that ΠO is the set of all Ruspini partitions compatible with O (see Definition 2). By Definition 5, h∗ (O) ≤ h∗ (O) for each fuzzy orthopartition O. Moreover, it is easy to verify that if π = {π1 , . . . , πn } is a Ruspini partition, then h(π) given by (2) equals both the lower and upper entropy of {(π1 , 1 − π1 ), . . . , (πn , 1 − πn )}. We now intend to show how to compute the lower and upper entropy of a fuzzy orthopartition O = {(µ1 , ν1 ), . . . , (µn , νn )} by using Definition 5. To achieve this goal, we need to find the Ruspini partitions π∗ and π ∗ of ΠO such that h∗ (O) = h(π∗ ) and h∗ (O) = h(π ∗ ). By Definitions 3 and 4, π∗ and π ∗ are respectively the minimum and the maximum points of the function f : ΠO → R+ such that X f (π) = max{ |πi (u) − πi (u′ )| such that i ∈ {1, . . . , n} }, (u,u′ )∈U ×U for each π = {π1 , . . . , πn } ∈ ΠO . Let us notice that π ∗ and π∗ exist because ΠO is always non-empty from Definition 2. Then, the problem to find π∗ and π ∗ can be transformed in a constrained optimization problem as follows. Let {π1 , . . . , πn } ∈ ΠO , and let U = {u1 , . . . , um }, we put I = {1, . . . , n} and J = {1, . . . , m}. Then, µi (uj ) ≤ πi (uj ) for each (i, j) ∈ I × J from Definition 2, and so, we can write πi (uj ) = µi (uj ) + xij . (3) where xij ≥ 0. Consequently, since every µi (uj ) is known, each Ruspini partition π of ΠO can be identified with a matrix (xij ) ∈ Rn×m having the elements determined by (3). Hence, our aim becomes to find the maximum and the minimum points of a new function g : Rn×m → R+ such that let m ∈ Rn×m , X g(m) = max{|(µi (uh ) + xih ) − (µi (uk ) + xik )| such that i ∈ I} (h,k)∈J×J subject to the constraints (P n i=1 (µi (uj ) + xij ) = 1 for each j ∈ J, (4) 0 ≤ xij ≤ hi (uj ) for each (i, j) ∈ I × J. We can observe constraint 1 assures us that π, corresponding to m through (3), is a Ruspini partition, and constraint 2 is necessary so that π is also compatible with O. Finally, this problem can be converted into a linear programming problem by introducing n2 !  additional variables. More precisely, let X2 = {X ⊆ U such that |X| = 2}, we consider P a new variable yX for each X ∈ X2 , and we aim to minimize or maximize a new function X∈X2 yX subject to the previous constraints, plus the followings: ( yX ≥ (µi (uh ) + xih ) − (µi (uk ) + xik ), for each X ∈ X2 , i ∈ I and (h, k) ∈ J × J, yX ≥ (µi (uk ) + xik ) − (µi (uh ) + xih ), for each X ∈ X2 , i ∈ I and (h, k) ∈ J × J. (5) Thus, we can compute the optimal solutions, i.e. the matrices of Rn×m representing π ∗ and π∗ , by using one of the standard techniques in linear programming like the Simplex method [8]. Once obtained π ∗ and π∗ , we can compute h(π ∗ ) and h(π∗ ) by using (3), which correspond to the upper and lower entropy of O, respectively. Example 2. Let U = {u, v, z}, consider a fuzzy orthopartition O = {(µ1 , ν1 ), (µ2 , ν2 ), (µ3 , ν3 )} according to the definition in Table 1. µ1 ν1 µ2 ν2 µ3 ν3 u 0.3 0.2 0.4 0.3 0 0.7 v 0.2 0.4 0.3 0.2 0.3 0.3 z 0 0.5 0.3 0.4 0.6 0.2 Table 1 Definition of the elements of the orthopartition. We suppose that (µ1 , ν1 ), (µ2 , ν2 ), and (µ3 , ν3 ) express the interest in three topics T1 , T2 , and T3 of three different groups u, v, and z of users of a social network. For instance, by Table 1, the users of u are interested in the topic T2 with a degree from µ2 (u) = 0.4 to 1 − ν2 (u) = 0.7. Therefore, in this case, the upper and lower entropy of O measure how much the interests of u, v, and z (valued w.r.t. {T1 , T2 , T3 }) diverge from each other. Then, in order to find the upper and lower entropy of O, we have to maximize and minimize the function y{u,v} + y{u,z} + y{v,z} subject to the constraints given by equations (4) and (5). The maximum and the minimum points of this function are respectively the matrices m∗ and m∗ of R3×3 , where     0 0 0.3 0 0.3 0 m∗ = 0.1 0.1 0  and m∗ = 0 0.2 0  . 0.1 0 0 0 0 0.1 By (3), their corresponding Ruspini partitions are π ∗ = {π1∗ , π2∗ , π3∗ } and π∗ = {π∗1 , π∗2 , π∗3 } as defined in Table 2. π∗1 π∗2 π∗3 π1∗ π2∗ π3∗ u 0.3 0.7 0 0.3 0.4 0.3 v 0.2 0.5 0.3 0.3 0.4 0.3 z 0 0.3 0.7 0.1 0.3 0.6 Table 2 Definition of the obtained Ruspini partitions. Lastly, h(π ∗ ) = 0.31 and h(π∗ ) = 0.13 from Definition 4, which are the upper and lower entropy of O, respectively. 4. Future directions In the future, we intend to extend the contents of this paper as follows. Firstly, we want to verify that h∗ (O) and h∗ (O) given by Definition 5 respectively coincide with the upper and lower entropy defined in [4], when O is a crisp orthopartition. Then, in order to provide a new measure of entropy, given a fuzzy orthopartition O, we will find a Ruspini partition π̃ of ΠO such that h(π̃) is the arithmetic mean of h∗ (O) and h∗ (O). On the long term, we plan to apply our results to the machine learning field (similarly as it has been done with orthopartitions [4, 9]) in order to define new algorithms with the ability to handle both uncertainty and vagueness. References [1] K. Atanassov, Review and new results on intuitionistic fuzzy sets, preprint Im-MFAIS-1-88, Sofia 5 (1988) l. [2] K. Atanassov, Intuitionistic fuzzy sets, International Journal Bioautomation 20 (2016) 1. [3] D. Ciucci, Orthopairs and granular computing, Granular Computing 1 (2016) 159–170. [4] A. Campagner, D. Ciucci, Orthopartitions and soft clustering: soft mutual information measures for clustering validation, Knowledge-Based Systems 180 (2019) 51–61. [5] E. H. Ruspini, A new approach to clustering, Information and control 15 (1969) 22–32. [6] D. Ellerman, Counting distinctions: on the conceptual foundations of shannon’s information theory, Synthese 168 (2009) 119–149. [7] D. Markechová, B. Riečan, Logical entropy and logical mutual information of experiments in the intuitionistic fuzzy case, Entropy 19 (2017) 429. [8] S. I. Gass, Linear programming: methods and applications, Courier Corporation, 2003. [9] A. Campagner, F. Cabitza, D. Ciucci, The three-way-in and three-way-out framework to treat and exploit ambiguity in data, International Journal of Approximate Reasoning 119 (2020) 292–312.