Online Credibilistic Fuzzy Clustering of Data Using Membership Functions of Special Type

Abstract

In the paper new online method of credibilistic fuzzy clustering of data was proposed. This algorithm is based on credibilistic approaches using on batch and online modes of information prosessing. Using proposed approach it's possible to solve clustering task in on-line mode when data are fed to processing sequentially, possible in real time.

Keywords

• fuzzy clustering
• learning rule
• possibilistic fuzzy clustering
• probabilistic fuzzy clustering
• credibilistic fuzzy clustering
• measure of similarity

-

1 Introduction The task of clustering (classification in the self-learning mode) of multidimensional data is an important part of Data Mining, within which a number of directions and approaches have developed [1, 2]. One of these areas is formed by fuzzy clustering methods, that are based on the assumption that the generated clusters - classes mutually overlap so that each vector - observation with different levels of membership-probability-possibility can belong to several or to all classes.

Here, the algorithms of probabilistic fuzzy clustering and, first of all, the fuzzy cmeans method (FCM) are most widely used [3, 4]. The possibilities of this approach are limited by probabilistic restrictions on membership levels so that observations “contaminated” with disturbances and outliers can be assigned to different classes with almost identical membership levels.

In this regard, in [5] was proposed the possibilistic fuzzy clustering method (PCM) that is more resistant to noise and disturbances. At the same time, PCM algorithms suffer from the so-called coincident problem, when during the processing of information some clusters begin to merge with each other, that leads to an incorrect estimate of the number of formed clusters.

Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

Algorithms of credibilistic fuzzy clustering [6-8], based on the apparatus of the theory of credibility [9], are devoid of these shortcomings. As part of this approach in the calculate process to evaluate not only the fuzzy membership levels, but also credibility levels based on a membership measure of a special type [10]. The experimental results have shown [7, 8] that the credibilistic methods provide a higher quality of clustering comparively with probabilistic and possibilistic methods.

The initial information for solving the problem of fuzzy clustering is an array of n - dimensional observations - vectors X  {x1, x2 ,..., xN }  Rn , x(k )  X , k  1, 2,..., N , that should be divided into m classes-clusters with a certain level of membership – probability – possibility Uq (k ) of k th vector xk to q th cluster (1  m  N ,1  q  m) . It should also be noted that the initial data are pre-processed so that 1  xki  1 (1  i  n) where xki – i th component of vector xk .

Thus, the clustering problem is solved in batch mode, when the entire data array is processed multiple times based on alternating cluster estimation [8]. If the data arrive for processing in the form of a stream or form big data, the batch mode does not allow to solve the problem under consideration effectively. In this situation, the most effective are the recursive fuzzy clustering procedures that allow to solve the problem online and refine the desired solution as each new observation that arrives. Thus, in the [11, 12] recurrent variants of FCM have been proposed that are essentially gradient optimization procedures adopted by the goal function, and in [13, 14] recurrent PCM modifications have been introduced designed for sequential data processing.

In this regard, it seems appropriate to develop a recurrent modification of the method of credibilistic fuzzy clustering, that allows clarifying the desired characteristics of the clusters as each new observation arrives. 2 Recurrent Method Of Credibilistic Fuzzy Clustering (RCCM) The most popular method of probabilistic fuzzy clustering is associated with minimizing the goal function ( 1 ) [4]

N m E(Uq (k ), wq )   Uq (k )D2 (xk , wq )

k 1 q1 m m with constrains Uq (k )  1, 0  Uq (k )  N. Solving the nonlinear programming q1 q1 problem using the method of indefinite Lagrange multipliers, we arrive to the known result ( 2 ) and ( 3 ) 1  Uq 1  k    D2  xk,wq  1   lm1  D2  xk , wl   1  , 1 1 ( 1 ) ( 2 ) Clq (1  q  m) , wq - prototype - centroid of q th cluster,   1 fuzzifier, that defines the “blurring” of boundaries between classes, D  xk , wq  –  the distance between xk and wq in adopted metric,   0,1, 2, – index of the epoch of information processing in the alternate estimation mode. In this case, the calculation process continues until the conditions w 1  wq    1  q  m

q is satisfied, where  – reassigned threshold calculation accuracy.

In the case, when   2 and Euclidean metric D2  xk , wq   xk  wq 22 is used, we obtain to the popular fuzzy c-means algorithm (FCM) [15] in the form ( 4 ), ( 5 )

Uq 1  k   xk  wq  2  lm1 xk  wl  2 1 , ( 4 ) wq 1  kN1 Uq 1  k 2 xk  kN1 Uq 1  k 2 1 . ( 5 ) If the data are processed sequentially online, the nonlinear programming task can be solved using the Arrow-Hurwitz-Uzawa algorithm, which is essentially a gradient procedure for finding the saddle point of the Lagrange function based on criterion ( 1 ) with constraints on the sum of membership levels.

In this case relations ( 2 ), ( 3 ) can be rewritten in the form ( 6 )  k 11  m 1 1 Uq k  1   D2  xk 1, wq    xk 1, wl (k)1    l1  , ( 6 )  wq k 1  w k    k 1Uq k  1  xk 1  wq  k  where  (k) – learning rate parameter, and ( 4 ), ( 5 ) can be rewritten in the form ( 7 )  2  m 1 Uq k  1  xk  wq k   l1 xk  wl  k  2   wq k 1  wq   k  1Uq2 k  1  xk 1  wq k  which are a generalization of the recurrent procedures of Park-Dagger [11] and Chung-Lee [12].

Possibilistic algorithms for fuzzy clustering are based on minimizing the goal function ( 8 ) [5]  E Uq  k  , wq , q   Uq  K  D2  xk , wq    q  1 Uq  k  , ( 8 ) m q1 where  q  0 determines the distance at which the membership level takes the value 0.5, i.e. Uq (k )  0 if D2 (xk , wq )   .

Minimization of criterion ( 8 ) allows us to obtain analytical solution in the form ( 9 ) which in the quadratic case takes the form ( 12 ) – ( 14 )

N m and in the case   2 ( 16 ) with constraints 0  Crq k   1q, k; supCrq (k)  0, 5k ; Crq k   supCrl  k   1 for any q and k for which Crq k   0.5 . Here Crq  k  – credibility that observation xk belongs to a cluster Clq . In this case, the membership level is calculated based on the membership function (18) [15]

Uq k    q  D  xk , wq  where:  q  – monotonically decreases in the interval [0, ] ,  q 0  1 ,  q   0 .

It is easy to see that function (18) is essentially measure of similarity based on distance [16]. As such a function, it was proposed in [15] to use the expression (19) ( 16 ) ( 17 ) (18) (19) (20)    Uq k  1  1     xk 1  wq k   q k 

Credibilistic fuzzy clustering is associated with minimizing the goal function ( 17 ) and for the Euclidean metric and   2 takes the form of a Cauchy distribution density function with a width parameter  q2 (21), (22), [17]

Uq k   1  D2  xk , wq  .

1 It is interesting to note that expression ( 2 ) can be rewritten in the form (20) 1  m 1  Uq k    D2  xk , wq k 1 ,   D2  xk , wl k 1     l1 

1 1 1 m 1   D2  xk , wk k 1  D2  xk , wq k 1    D2  xk , wl k 1 )1   Uq  k   1   

xk wqq2  k  2 1 ,  m 1  q2   ll1q xk  wl (k) 2  . (22)

It is easy to see that the membership function (19) is a special case of (21) for  q2  1 .

Finally, a batch algorithm of credibilistic fuzzy clustering can be written in the form (23) – (26) [7, 8]:

U  1  k   1 D2  xk , wq  1 ,

q U *q 1  k   U  1 k  supUl 1 k 1 ,

q Crq 1 k   12 Uq( 1)  k   1  supUl k   , lq  (23) (24) (25)

N   N  1 wq 1   Crq 1 k  xk   Crq 1 k   . (26)

k 1  k 1 

Based on ( 17 ), (21) – (26), we can write online version of the credibilistic fuzzy clustering method in the form (27) U*k 1  Uq k  1 supUl  k  11 ,  Crq  k 1  12 Uq* k  1  1  supUl*  k 1  ,  lq  wq k 1  wq  k    k 1 Crq  k  1  xk1  wq  k .  

Therefore, from a computational point of view, the online algorithm for credibilistic fuzzy clustering is no more complicated than the recurrent versions of FCM and PCM, while retaining the advantages of a credibility approach.   m 1  q2 k  1    xk 1  wl  k  2 

 ,  ll1q      Uq k  1  1    xk 1  wq  k  2 1

 ,  q2  k 1   (27) To check the performance efficiency of the developed methods as well as to prove their benefits over the analogs, experimental research was conducted with the help on two different databases. Also conducted a comparative analysis of the quality of clustering data on the main characteristics quality ratings, such as: Partition Coefficient (PC) defines "overlapping" between groups of points, Partition Index (SC) quantifies the ratio sum of compactness and separation of the clusters, Xie and Beni’s Index (XB) gauges a ratio of the total variability inside clusters and their separation, of existing clustering methods and proposed method.

The experimental results are given in Table 1 and Table 2.

Such clustering tools as fuzzy c-means (FCM) and the algorithm by GustafsonKessel (GK), Gath-Geva (GG), Adaptive probabilistic fuzzy clustering, Adaptive fuzzy possibilistic data clustering and Adaptive fuzzy credibilistic data clustering were chosen for comparison with the developed procedure. Fig. 1. Comparison CE of Adaptive fuzzy credibilistic data clustering and Fuzzy

C-means (FCM) methods for First Data Set Fig. 2. Comparison PC of Adaptive fuzzy credibilistic data clustering and Fuzzy

C-means (FCM) methods for First Data Set

In comparison with the well-known methods, this approach to data clustering demonstrates somewhat reliable results (Fig. 1, Fig. 2, Fig. 3, Fig. 4 ).

Fig. 3. Comparison CE of Adaptive fuzzy credibilistic data clustering and Fuzzy

C-means (FCM) methods for Second Data Set Fig. 4. Comparison PC of Adaptive fuzzy credibilistic data clustering and Fuzzy

C-means (FCM) methods for Second Data Set 4 Conclusion The problem of fuzzy clustering based on probabilistic, possibilistic and credibilistic approaches based online mode of information processing was considered. A recurrent version of credibilistic algorithm is introduced, which is essentially a gradient optimization procedure for the accepted criterion for fuzzy credibilistic clustering. A modification of the membership function is introduced, which is essentially a measure of similarity and a generalization of previously known functions. The considered recursive procedures are simple in numerical implementation and are intended to solve problems arising in the framework of Data Stream Mining.

References

1. Xu , R. , Wunsch , D.C. : Clustering. Hoboken , N.J. John Wiley & Sons, Inc. ( 2009 )

2. Aggarwal , C.C. : Data Mining: Text Book. Springer ( 2015 ).

3. Bezdek , J.C. : Pattern Recognition with Fuzzy Objective Function Algorithms . Plenum Press, New York ( 1981 ).

4. Höeppner , F. , Klawonn , F. , Kruse , R. , Runker , T. : Fuzzy Clustering Analysis: Methods for Classification, Data Analysis and Image Recognition . Chichester, John Wiley &Sons ( 1999 )

5. Krishnapuram , R., Keller, J.M.: A possibilistic approach to clustering . Fuzzy Systems, №2 , pp. 98 - 110 ( 1993 )

6. Chintalapudi , K. K. , Kam , M.: A noise resistant fuzzy c-means algorithm for clustering . In: IEEE Conference on Fuzzy Systems Proceedings , vol. 2 , pp. 1458 - 1463 ( 1998 )

7. Zhou , J. , Wang , Q. , Hung , C.-C., Yi , X. : Credibilistic clustering: the model and algorithms . Int.J. of Uncertainty, Fuzziness and Knowledge-Based Systems, №4 , pp. 545 - 564 ( 2015 ).

8. Zhou , J. , Wang , Q. , Hung , C. C. : Credibilistic clustering algorithms via alternating cluster estimation . J. Intell. Manuf. , pp. 727 - 738 ( 2017 ).

9. Liu , B. , & Liu , Y. Expected value of fuzzy variable and fuzzy expected value models . In: “IEEE Transactions on Fuzzy Systems”, № 4 , pp. 445 - 450 ( 2002 ).

10. Liu , B. : A survey of credibility theory . Fuzzy Optimization and Decision Making, №4 , pp. 387 - 408 ( 2006 ).

11. Park , D.C. , Dagher , I. : Gradient based fuzzy c-means (GBFCM) algorithm . In: Proc. IEEE Int. Conf. on Neural Networks , pp. 1626 - 1631 ( 1984 ).

12. Chung , F.L. , Lee , T. : Fuzzy competitive clustering . Neural Networks , 7 ( 3 ), pp. 539 - 552 . ( 1994 ).

13. Bodyanskiy , Ye, Kolodyazhniy, V. , Stephan , A. : Recursive fuzzy clustering algorithms . In : Proc 10th East West Fuzzy Coll. Zittau-Görlitz, HS , pp. 276 - 283 ( 2002 ).

14. Bodyanskiy , Ye.: Computational intelligence techniques for data analisys . In: Lecture Notes in Informatics . Bonn: V.P. - 72, GI, pp. 15 - 36 ( 2005 ).

15. Zhou , J. , & Hung , C.-C. : A generalized approach to possibilistic clustering algorithms . Int. J. of Uncertainty, Fuzziness and Knowledge-Based Systems. 15 . pp. 117 - 138 . ( 2007 ).

16. Young , F.W. , Hamer , R.M. : Theory and Applications of Multidimensional Scaling- Hillsdale , N.J.: Erlbaum ( 1994 ).

17. Hu , Zh., Bodyanskiy , Ye, Tyshchenko, O. , Shafronenko , A. : Fuzzy clustering of incomplete data by means of similarity measures . In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering UKRCON - 2019, Conference Proceedings, July 2-6 , 2019 , Lviv, Ukraine, pp. 149 - 152 ( 2019 ) doi: 10.1109/UKRCON. 2019 . 8879844 .