Rough Inclusion Functions and Similarity Indices?

Abstract

Rough inclusion functions are mappings considered in the rough set theory with which one can measure the degree of inclusion of a set in a set (and in particular, the degree of inclusion of an information granule in an information granule) in line with rough mereology. On the other hand, similarity indices are mappings in cluster analysis with which one can compare clusterings, and clustering methods with respect to similarity. In this article we investigate the relationships between rough inclusion functions and similarity indices.

Keywords

• rough inclusion function
• rough mereology
• similarity index
• cluster analysis
• granular computing

Introduction

In 1994, L. Polkowski and A. Skowron introduced the formal notion of a rough inclusion, making it a fundamental concept of rough mereology (see, e.g. [1{4]).3 Rough inclusion may be interpreted as a ternary relation with which one can express the fact that a set of objects is to some degree included in the same or another set of objects. Rough mereology is a theory extending the Lesniewski mereology [ 6, 7 ] from a theory of being-a-part to a theory of being-a-part-to-degree. Rough inclusion functions (RIFs) are mappings with which one can measure the degree of inclusion of sets in sets and which comply with the axioms of rough inclusion. Since according to L. A. Zadeh's de nition [ 8 ], an information granule is a clump of objects drawn together on the basis of indistinguishability, similarity or functionality, RIFs can be used in particular to measure the degree of inclusion of information granules in information granules. Hence, the concept of a RIF is fundamental not only for the rough set theory [ 5, 9 ] but also for the foundations and the development of granular computing [ 10, 11 ]. ? Many thanks to the anonymous referees for interesting comments on the paper. All errors left are our sole responsibility. 3 It is worthy to note that some ideas on rough inclusion were presented by Z. Pawlak in [ 5 ].

RIFs can be useful in the rough set theory and, more generally, in granular computing in many ways. First, they can be applied to compare sets (and information granules) with respect to inclusion. Secondly, they can be used to de ne rough membership functions [ 12 ] and various approximation operators as those in the Skowron { Stepaniuk approach (see, e.g. [ 13, 14 ] and other papers by the same authors), in the Ziarko variable-precision rough set model (see, e.g. [ 15, 16 ] and more recent papers), or in the decision-theoretic rough set model [ 17, 18 ]. RIFs can also be used to estimate the con dence (known as accuracy as well) and the coverage of decision rules and association rules (see, e.g. [ 19 ]). Another application of RIFs is graded semantics of formulas (see, e.g. [ 20 ]). An important application of RIFs is obviously their usage to compute the degree of similarity (nearness, closeness) between sets of objects and, in particular, between information granules. Some steps into this direction have already been made (see, e.g. [ 21, 4, 14 ]).

The similarity indices we are going to speak about are used in cluster analysis [22{24] to compare clusterings, and clustering methods with respect to how they are similar to (or dissimilar from) one another. Many of these similarity indices were originally designed to compare species with respect to their mutual similarity, given information about presence and/or absence of some features. A. N. Albatineh, M. Niewiadomska-Bugaj, and D. Michalko thoroughly examined 28 similarity indices known from the literature on classi cation and cluster analysis, from which 22 turned out to be di erent.4 The results of their research on correction for chance agreement for similarity indices can be found, e.g. in [ 25 ]. In the present article we continue our earlier works [ 26, 27 ], where among other things, three similarity indices out of those 22 were derived from RIFs. Our actual goal is to show that all 22 similarity indices investigated in [ 25 ] can be obtained starting with the RIFs $, 1, and 2 only. This reveals one more connection between the rough set theory and cluster analysis.

The rest of the paper is organized as follows. In Sect. 2 we recall the notion of a rough inclusion function and the three particular RIFs mentioned above. In Sect. 3 we present the 22 similarity indices known from the literature and discussed in [ 25 ], and we characterize them one by one by means of the standard RIF $ or two other RIFs, viz. 1 and 2. The last section contains nal remarks. 2

Rough Inclusion Functions

Rough inclusion functions (RIFs for short) are supposed to be mappings to measure the degree of inclusion of sets in sets and to comply with the axioms of rough inclusion. In detail, a rough inclusion function upon a non-empty set of objects U (in short, a RIF upon U or simply, a RIF) is a mapping : }U }U 7! [0; 1], assigning to any pair of sets (X; Y ) of elements of U , a number (X; Y ) from the unit interval [0; 1] interpreted as the degree to which X is included in 4 Some similarity indices were introduced more than once, under di erent names. Y , and such that the conditions rif 1( ) and rif2( ) are satis ed, where rif1( ) d,ef 8X; Y rif2( ) d,ef 8X; Y; Z

U:( (X; Y ) = 1 , X

U:( (Y; Z) = 1 )

Y ); (X; Y ) (X; Z)): Condition rif1( ) expresses the fact that the set-theoretical inclusion of sets is the most perfect case of rough inclusion. When rif 1( ) holds, condition rif 2( ) will be equivalent with condition rif 2( ) below: rif2( ) d,ef 8X; Y; Z

U:(Y

Z ) (X; Y ) (X; Z)) expressing monotonicity of in the second variable. In the literature, weaker versions of RIFs are considered as well, where rif 1( ) is replaced by \a half of it". Then, rif2( ) and rif2( ) will de ne di erent classes of inclusion mappings (see, e.g. [ 28 ]).

In summary, any RIF upon U should satisfy rif 1( ) and rif2( ) or, equivalently, rif1( ) and rif2( ). Among RIFs, various subclasses of mappings can be distinguished by adding new postulates to be satis ed. These can be, for instance, rif3( ) d,ef 8; 6= X rif4( ) d,ef 8X; Y rif4 1( ) d,ef 8; 6= X rif5( ) d,ef 8; 6= X rif6( ) d,ef 8; 6= X rif7( ) d,ef 8X; Y; Z

U: (X; ;) = 0; U:( (X; Y ) = 0 )

X \ Y = ;); U:8Y U:8Y U:8Y U:(Z

U:(X \ Y = ; )

(X; Y ) = 0); U:( (X; Y ) = 0 ,

X \ Y = ;); U: (X; Y ) + (X; Y c) = 1; Y

X ) (X; Z) (Y; Z)); where Y c denotes the set-theoretical complement of Y .5 Obviously, rif 5( ) if and only if rif4( ) and rif4 1( ). Apart from that rif4 1( ) ) rif3( ); rif1( ) & rif6( ) ) rif5( ):

The standard RIF, denoted by $ here, is the most famous and frequently used by the rough set community. The idea underlying this notion is closely related to the conditional probability. In logic, J. Lukasiewicz was the rst who employed this idea when calculating the probability of truth associated with implicative formulas [ 31, 32 ]. Let us recall that $ is only de ned for a nite U by putting $(X; Y ) d=ef ( #(X\Y ) if X 6= ;;

#X 1 otherwise, 5 The last condition was mentioned in [ 29, 30 ]. There, rough inclusion is understood in a di erent way than in our paper. (1) (2) where X; Y are any subsets of U and #X denotes the number of elements of X. In words, the standard RIF measures the fraction of the elements having the property described by the second argument (Y ) among the elements with the property described by the rst argument (X). Apart from being a true RIF, $ has a number of interesting properties recalled, e.g. in [ 27 ]. For instance, it satis es rifi( ) (i = 3; : : : ; 7) and rif4 1( ).

Examples of other RIFs are mappings 1 and 2 such that for any X; Y U , 1(X; Y ) d=ef

#Y #(X[Y ) if X [ Y 6= ;; 1 otherwise, (3) Also in this case, U has to be nite. While 1 was introduced in [ 26 ], 2 had already been mentioned in [ 33 ]. The both RIFs were investigated in detail in [ 27 ]. The RIFs $, 1, and 2 are di erent from one another. Below we recall a few other properties of these mappings.

Proposition 1. For any X; Y

U , we have: (i) X 6= ; ) ( 1(X; Y ) = 0 , Y = ;); (ii) 2(X; Y ) = 0 , X = U & Y = ;; (iii) rif4( 1) & rif4( 2); (iv) $(X; Y )

1(X; Y ) (v)

1(X; Y ) = (vi) 2(X; Y ) = $(X [ Y; Y ) & $(U; Xc [ Y ): 2(X; Y ); $(X; Y ) = 1(X; X \ Y ); Let us also note that due to (i), rif 3( 1) holds. The same cannot be however said about 2 (compare (ii)). 3

Similarity Indices in Terms of RIFs

In this section we reformulate the similarity indices studied in [ 25 ] in terms of the RIFs $, 1, or 2. The proofs that the indices can really be expressed in this way will be given in the full version of this paper.

Consider a set U0 of m > 0 data points to be grouped by some clustering methods A1 and A2. Let U (our universe) be the set of all unordered pairs of data points fx; yg U0 to be compared in order to obtain clusterings, i.e. partitions of U0 generated by A1 and by A2, and denoted by C1 and C2 here. Thus, #U = M = m2 = m(m 1)=2. The similarity between the clusterings C1 and C2 (and the clustering methods A1 and A2) is usually assessed on the basis of the number of pairs of data points that are put into the same cluster or are put into di erent clusters by each of the grouping methods considered. For i = 1; 2, let us de ne

Xi = ffx; yg 2 U j x; y are clustered by Aig: (4)

Additionally, let

In words, a is the number of pairs of data points fx; yg such that x and y are placed in the same cluster according to both A1 and A2; b (respectively, c) is the number of pairs of data points fx; yg such that x and y are placed in the same cluster by A1 (resp., A2), but they are placed in di erent clusters by A2 (resp., A1); nally, d is the number of pairs of data points fx; yg such that x and y are placed in di erent clusters according to both A1 and A2. We also have #X1 = a+b, #X2 = a+c, #X1c = c+d, #X2c = b+d, and #U = a+b+c+d = M . For simplicity assume that a; b; c; d > 0. Then, we will have that a $(X1; X2) = ; a + b

a + c 1(X1; X2) = a + b + c ;

a + c + d 2(X1; X2) = M : (6)

In what follows we will present similarity indices one by one and their new formulation in terms of $, 1, or 2.

Wallace (1983). The similarity indices W1; W2 with range [0; 1] were introduced by D. L. Wallace: (5) (7) (8) (9) (10) K can be rewritten to the following form: In words, K(C1; C2) is the arithmetical mean of $(X1; X2) and Kulczynski (1927). The similarity index K with range [0; 1] was proposed by S. Kulczynski in 1927: McConnaughey (1964). The similarity index M C with range [ 1; 1] goes back to B. H. McConnaughey:

M C(C1; C2) d=ef

a2 bc (a + b)(a + c) This index can be expressed by the following equation:

M C(C1; C2) = $(X1; X2) + $(X2; X1) 1 Peirce (1884). The similarity index P E with range [ 1; 1] is attributed to C. S. Peirce:

P E(C1; C2) d=ef

ad bc (a + c)(b + d) The index P E can be characterized as follows:

P E(C1; C2) = $(X2; X1) + $(X2c; X1c) $(X2; X1c) $(X2c; X1) Ochiai (1957), Fowlkes and Mallows (1983). The similarity index OF M ranges over [0; 1]. It was introduced by A. Ochiai in 1957 and again by E. B. Fowlkes and C. L. Mallows in 1983:

After rewriting we get

OF M (C1; C2) d=ef That is, OF M (C1; C2) is the geometrical mean of $(X1; X2) and $(X2; X1). The Gamma index. The similarity index with range [ 1; 1] is given by (C1; C2) d=ef

ad bc p(a + b)(a + c)(b + d)(c + d) : In this case, the following characterization can be obtained: The Pearson index. The similarity index P named after C. Pearson ranges over [ 1; 1]. It is given by

P (C1; C2) d=ef

ad bc (a + b)(a + c)(b + d)(c + d)

Sokal and Sneath (1963). The similarity indices SS1; SS2; SS3 with range [0; 1] were introduced by R. R. Sokal and P. H. Sneath in 1963. The third index is also attributed to A. Ochiai (1957): (21) (22) (23) Thus, SS1(C1; C2) (resp., SS3(C1; C2)) is the arithmetical (geometrical) mean of $(X1; X2), $(X2; X1), $(X1c; X2c), and $(X2c; X1c).

Jaccard (1908). The similarity index J with range [0; 1] goes back to P. Jaccard:

J (C1; C2) d=ef

a a + b + c

It can be shown that

J (C1; C2) = 1(X1; X2) + 1(X2; X1) 1: Sokal and Michener (1958), Rand (1971). The similarity index R with range [0; 1] was introduced by R. R. Sokal and C. D. Michener, and later independently by W. Rand:

R(C1; C2) d=ef a + d

M

The index R can be rewritten to

R(C1; C2) = 2(X1; X2) + 2(X2; X1) 1: Hamann (1961), Hubert (1977). The similarity index H, ranging over [ 1; 1], was proposed by U. Hamann and independently by L. J. Hubert: H(C1; C2) d=ef (a + d) (b + c)

M

By certain transformations we obtain

H(C1; C2) = 2( 2(X1; X2) + 2(X2; X1)) 3: Czekanowski (1932), Dice (1945), Gower and Legendre (1986). The similarity index CZ ranges over [0; 1]. It was proposed by J. Czekanowski in 1932, L. R. Dice in 1945, and by J. C. Gower and P. Legendre in 1986:

On can prove the following:

CZ(C1; C2) d=ef

2a 2a + b + c CZ(C1; C2) = 2( 1(X1; X2) + 1(X2; X1) 1)

1(X1; X2) + 1(X2; X1) Russel and Rao (1940). The similarity index RR ranges over [0; 1] and is attributed to P. F. Russel and T. R. Rao:

RR(C1; C2) d=ef a

M

In this case we obtain that

RR(C1; C2) =

$(U; X1 \ X2) = 2(U; X1 \ X2): Fager and McGowan (1963). The similarity index F M G with range [ 1=2; 1) goes back to E. W. Fager and J. A. McGowan :

F M G(C1; C2) d=ef for an arbitrary u 2 X1. Sokal and Sneath (1963), Gower and Legendre (1986). The similarity index GL with range [0; 1] was introduced by R. R. Sokal and P. H. Sneath in 1963, and again by J. C. Gower and P. Legendre in 1986:

GL(C1; C2) d=ef

a + d a + 12 (b + c) + d A characterization of GL in terms of 2 is the following:

GL(C1; C2) = 2( 2(X1; X2) + 2(X2; X1) 1)

2(X1; X2) + 2(X2; X1) Rogers and Tanimoto (1960). The similarity index RT with range [0; 1] is attributed to D. J. Rogers and T. T. Tanimoto: This index can be rewritten to the following form:

RT (C1; C2) d=ef

a + d a + 2(b + c) + d RT (C1; C2) =

2(X1; X2) + 2(X2; X1) 1 3 ( 2(X1; X2) + 2(X2; X1)) Yule (1927), Goodman and Kruskal (1954). The similarity index GK ranges over [ 1; 1]. It was proposed by G. U. Yule in 1927, and again by L. A. Goodman and W. H. Kruskal in 1954:

GK(C1; C2) d=ef ad bc ad + bc This index can be expressed in terms of the standard RIF as follows: GK(C1; C2) = $(X2; X1) $(X2c; X1c)

$(X2; X1c) $(X2c; X1) $(X2; X1) $(X2c; X1c) + $(X2; X1c) $(X2c; X1) Baulieu (1989). The similarity indices B1 and B2 range over [0; 1] and [ 1=4; 1=4], respectively. They were introduced by F. B. Baulieu in 1989:

B1(C1; C2) d=ef M 2 B2(C1; C2) d=ef adM 2bc :

M (b + c) + (b c)2

M 2 ; As in all previous cases, a RIF (precisely, 2 here) underlies the de nitions of these similarity indices, viz.,

B1(C1; C2) = 2(X1; X2) + 2(X2; X1) 1 + ( 2(U; X1) 2(U; X2))2; B2(C1; C2) = (1 2(X1; X2c)) 2(U; X1c) (1 2(X1c; X2c)) 2(U; X1): (42) (35) (36) (37) (38) (39) (40) (41)

Final Remarks

The main goal realized in this paper was to show that a pretty vast number of various similarity indices known from the literature can be formulated in terms of some rough inclusion functions. Rough inclusion functions (RIFs) are mappings, inspired by the notion of a rough inclusion introduced by L. Polkowski and A. Skowron as a basic concept of rough mereology, by means of which one can measure the degree of inclusion of a set of objects in a set of objects. Since information granules can be viewed as particular sets of objects, RIFs are important not only for the rough set theory but also for granular computing.

Starting with the standard RIF $ and two other RIFs of a similar origin, denoted by 1 and 2, we have obtained all 22 similarity indices discussed in [ 25 ]. In the paper just mentioned it is proved that the indices K and MC are equivalent after some correction known as the correction for agreement due to chance, and the same holds for R, H, and CZ. We have not referred to this question because we are interested in other aspects concerning similarity indices. For example, we think about a usage of similarity indices in granular computing to calculate the degree of similarity between compound information granules such as indistinguishability relations and tolerance relations on a set of elementary objects considered. Let us note that similarity indices can also be used in granular computing in a more general setting, viz. to compute the degree of similarity between arbitrary sets of objects.

In the full version of this article we will give an illustrating example and proofs of the formulas characterizing the similarity indices considered. In the future research we will generalize our results, viz. we will propose general schemata for generation of similarity indices from an arbitrary RIF. Another question, also suggested by the referee, is the discovery of relationships among RIFs and quality measures for clusters.

References

1. Polkowski , L. : Reasoning by Parts: An Outline of Rough Mereology , Warszawa ( 2011 )

2. Polkowski , L. , Skowron , A. : Rough mereology. Lecture Notes in Arti cial Intelligence 869 ( 1994 ) 85 { 94

3. Polkowski , L. , Skowron , A. : Rough mereology: A new paradigm for approximate reasoning . Int. J. Approximated Reasoning 15 ( 4 ) ( 1996 ) 333 { 365

4. Polkowski , L. , Skowron , A. : Rough mereological calculi of granules: A rough set approach to computation . Computational Intelligence 17 ( 3 ) ( 2001 ) 472 { 492

5. Pawlak , Z.: Rough Sets . Theoretical Aspects of Reasoning About Data . Kluwer, Dordrecht ( 1991 )

6. Lesniewski , S. : Foundations of the General Set Theory 1 (in Polish) . Volume 2 of Works of the Polish Scienti c Circle ., Moscow ( 1916 ) Also in [7], pages 128 { 173 .

7. Surma , S.J. , Srzednicki , J.T. , Barnett , J.D., eds.: Stanislaw Lesniewski Collected Works. Kluwer/Polish Scienti c Publ., Dordrecht/Warsaw ( 1992 )

8. Zadeh , L.A. : Outline of a new approach to the analysis of complex system and decision processes . IEEE Trans. on Systems, Man, and Cybernetics 3 ( 1973 ) 28 { 44

9. Pawlak , Z. , Skowron , A. : Rudiments of rough sets . Information Sciences 177 ( 1 ) ( 2007 ) 3 { 27

10. Pedrycz , W. , Skowron , A. , Kreinovich , V., eds.: Handbook of Granular Computing. John Wiley & Sons, Chichester ( 2008 )

11. Stepaniuk , J.: Rough-Granular Computing in Knowledge Discovery and Data Mining . Springer-V., Berlin Heidelberg ( 2008 )

12. Pawlak , Z. , Skowron , A. : Rough membership functions . In Fedrizzi, M. , Kacprzyk , J. , Yager , R .R., eds.: Fuzzy Logic for the Management of Uncertainty . John Wiley & Sons, New York ( 1994 ) 251 { 271

13. Skowron , A. , Stepaniuk , J.: Tolerance approximation spaces . Fundamenta Informaticae 27 ( 2 {3) ( 1996 ) 245 { 253

14. Stepaniuk , J.: Knowledge discovery by application of rough set models . In: [34] . ( 2001 ) 137 { 233

15. Ziarko , W.: Variable precision rough set model . J. Computer and System Sciences 46 ( 1 ) ( 1993 ) 39 { 59

16. Ziarko , W. : Probabilistic decision tables in the variable precision rough set model . Computational Intelligence 17 ( 3 ) ( 2001 ) 593 { 603

17. Yao , Y.Y. : Decision-theoretic rough set models . Lecture Notes in Arti cial Intelligence 4481 ( 2007 ) 1 { 12

18. Yao , Y.Y. , Wong , S.K.M.: A decision theoretic framework for approximating concepts . Int. J. of Man{Machine Studies 37 ( 6 ) ( 1992 ) 793 { 809

19. Tsumoto , S. : Modelling medical diagnostic rules based on rough sets . Lecture Notes in Arti cial Intelligence 1424 ( 1998 ) 475 { 482

20. Gomolinska , A. : Satis ability and meaning of formulas and sets of formulas in approximation spaces . Fundamenta Informaticae 67 ( 1 {3) ( 2005 ) 77 { 92

21. Nguyen , H.S. , Skowron , A. , Stepaniuk , J.: Granular computing: A rough set approach . Computational Intelligence 17 ( 3 ) ( 2001 ) 514 { 544

22. Cios , K.J. , Pedrycz , W. , Swiniarski , R.W. , Kurgan , L.A. : Data Mining: A Knowledge Discovery Approach . Springer Science + Business Media, LLC , New York ( 2007 )

23. Jain , A.K. , Murty , M.N. , Flynn , P.J. : Data clustering: A review . ACM Computing Surveys 31 ( 3 ) ( 1999 ) 264 { 323

24. Kaufman , L., Rousseeuw , P.J. : Finding Groups in Data: An Introduction to Cluster Analysis . John Wiley & Sons, Chichester ( 1990 )

25. Albatineh , A.N. , Niewiadomska-Bugaj , M. , Mihalko , D. : On similarity indices and correction for chance agreement . J. of Classi cation 23 ( 2006 ) 301 { 313

26. Gomolinska , A. : On three closely related rough inclusion functions . Lecture Notes in Arti cial Intelligence 4585 ( 2007 ) 142 { 151

27. Gomolinska , A. : On certain rough inclusion functions . Transactions on Rough Sets IX: journal subline of LNCS 5390 ( 2008 ) 35 { 55

28. Gomolinska , A. : Rough approximation based on weak q-RIFs . Transactions on Rough Sets X: journal subline of LNCS 5656 ( 2009 ) 117 { 135

29. Xu , Z.B. , Liang , J.Y. , Dang , C.Y. , Chin , K.S.: Inclusion degree: A perspective on measures for rough set data analysis . Information Sciences 141 ( 2002 ) 227 { 236

30. Zhang , W.X. , Leung , Y. : Theory of including degrees and its applications to uncertainty inference . In: Proc. of 1996 Asian Fuzzy System Symposium . ( 1996 ) 496 { 501

31. Borkowski , L., ed.: Jan Lukasiewicz { Selected Works. North Holland/Polish Scienti c Publ., Amsterdam/Warsaw ( 1970 )

32. Lukasiewicz , J.: Die logischen Grundlagen der Wahrscheinlichkeitsrechnung , Krakow ( 1913 ) English translation in [31], pages 16 - 63 .

33. Drwal , G. , Mrozek , A. : System RClass { software implementation of a rough classi er . In Klopotek, M.A. , Michalewicz , M. , Ras , Z.W., eds. : Proc. 7th Int. Symp. Intelligent Information Systems (IIS' 1998 ), Malbork, Poland, June 1998 . ( 1998 ) 392 { 395

34. Polkowski , L. , Tsumoto , S. , Lin , T.Y., eds.: Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems . Physica V., Heidelberg New York ( 2001 )