Adaptive Fuzzy Clustering Approach Based on Evolutionary Cat Swarm Optimization

Abstract

Computational intelligence methods are widely used to solve many complex problems, including, of course, traditional: Data Mining and such new directions as Dynamic Data Mining, Data Stream Mining, Big Data Mining, Web Mining, Text Mining, etc. One of the main areas of computational intelligence are evolutionary algorithms that essentially represent certain mathematical models of biological organisms evolution. In the paper adaptive methods of fuzzy clustering using on evolutionary cat swarm optimization were proposed. Using proposed approach it's possible to solve clustering task in on-line mode.

1 Introduction

The task of classification in the self-learning mode (clustering) of multidimensional data is an important part of traditional intellectual analysis such as Data Mining, Dynamic Data Mining, Data Stream Mining, Big Data Mining, Web Mining [1, 2].

One of the main areas of computational intelligence are the so-called evolutionary algorithms, which are mathematical models of biological organisms evolution. The problem connected with by vector-observations, clustering often occurs in many applications of data mining, and first of all in data fuzzy clustering when processing vector-observation with different levels of probability possibility, credibility etc. can belong to more than one class.

Very effective are Kohonen self-organizing maps [3] and the evolutionary algorithms that can improve data clusterization in case, when the data are processed sequentially in online mode.

The problem of fuzzy clustering of data arrays is considered in the conditions when the formed clusters arbitrarily overlap in the space of features. The source information for solving the problem is an array of multidimensional data vectors, formed by a set of vector-observations X  ( x( 1 ), x( 2 ),..., x(k ),...x( N ))  Rn where k in the general case the observation number in the initial array, x(k )  ( x1 (k ),..., xi (k ),..xn (n))T . The result of clustering is the partition of this array on m overlapped classes with

Copyright © 2020 for this paper by its authors. Use permitted under Creative

Commons License Attribution 4.0 International (CC BY 4.0).

prototypes-centroids Cl j  Rn , j  1, 2,..., m , and computing of membership levels 0  U j (k )  1 of each vector-observation x(k ) to every cluster Cl j . 2 Adaptive algorithm for probabilistic fuzzy clustering (APrFC)

The goal function of popular probabilistic clustering has the form [4]

N m E(U j (k ), Cl j )   U j (k )D2 (xk , Cl j ) we obtain the probabilistic fuzzy clustering algorithm  1  m 1 1 U (j 1) (k )  D2 ( xk , Cl (j ) ))1 *  l1 (D 2 ( xk , Cll( ) ))1  ,     N  N 1 Cl (j 1)   (U (j 1) ) xk *   (U (j 1) (k ))  ,  k 1  k 1  ( 1 ) ( 2 ) ( 3 ) ( 4 ) in case when the   2 - parameter that is called fuzzyfier and defines "blurring" the boundaries between classes we come to a decision, that has the form 

k 1  1 U (j 1) (k)  xk  Cl(j ) 2 * m xk  Cll( ) 2  ,    l1  N  N 1 Clq( 1)   (U (j 1) (k))2 xk *   (U (j 1) (k))2  .

 k1  The process of fuzzy clustering can be organized in on-line adaptive mode 

1  m 1  U j (k  1)  (D2 (xk1, Cl (jk ) ))1 *   (D2 (xk1, Cll (k )))1  ,   l1   Cl j (k  1)  Cl j (k )  (k  1)U j (k  1)(xk1  Cl j (k )). 1 3 Adaptive algorithm for possibilistic fuzzy clustering (APosFC)

The goal function of possibilistic clustering has the form

N m m N E(U j (k ), Cl j , j )   U j (k )D2 (xk , Cl j )   j  (1  U j (k )) k 1 j1 j1 k 1 ( 5 ) where   0 - the scalar parameter that specifies the distance at which the level of membership equals 0.5.

Minimizing the equation ( 5 ) relatively, U j (k ) , Clq and  j we obtain the system of equations ( 6 ) in case when the   2 we come to a decision, that has the form ( 7 ):            D2 (x(k ), Cl (j ) ) )11 1 , U ( 1) (k )  1  (  j   (j )    N   N 1 Cl (j 1)   (U (j 1) (k )) x(k ) *   (U (j 1) (k ))  , k 1  k 1 

N  N  ( 1)   U (j 1) (k )) D2 ( x(k ), Cl (j 1)  *   (U (j 1) (k ))  ,  j k 1  k 1   x(k )  Cl(j ) 2 1  ,   U ( 1) (k )  1   j   ( )   j  N  N 1 Cl(j 1)   (U (j ) (k ))2 x(k ) *   (U (j ) (k ))2  ,

k1  k 1   ( 1)   (U (j ) (k ))2 x(k )  Cl(j 1) 2  N

N 

*   (U (j ) (k ))2  .  j k 1  k 1  1 In the online mode algorithms ( 6 ), ( 7 ) can be written in recurrent form ( 8 )   D2 (x(k  1), Cl j (k )) )11 1 , U j (k  1)  1  (    j (k )    Cl j (k  1)  Cl j (k )  (k  1)U j (k  1)(x(k  1)  Cl j (k )),  k 1  k 1 1  j (k  1)  U j ( p)D2 (x( p), Cl j (k  1)) *  U j ( p)   p1  p1  1 ( 6 ) ( 7 ) ( 8 ) and U j (k  1)  1  x(k )  c j (k ) 2 1 ,    j (k )   c j (k  1)  c j (k )  (k  1)U 2j (k  1)(x(k  1)  c j (k )),  k 1 2  k 1  j (k  1)  U 2j ( p) x( p)  c j (k  1) *  U 2j ( p)  ,  p1  p1   ( 9 ) ( 10 ) ( 11 ) ( 12 ) that permits to solve the fuzzy clustering task in sequental mode. 4 Adaptive Credibilistic Fuzzy Clustering (ACrFC) Credibilistic fuzzy clustering is associated with minimizing the goal function ( 10 )

N m E Crq k  , wq   Crq  k  D2  xk , wq 

k 1 q1 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 using on the membership function [5, 6]

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

It is easy to see that function ( 11 ) is essentially measure of similarity based on distance [7]. As such a function, it was proposed in [8] to use the expression 1

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

It is interesting to note that expression ( 12 ) can be rewritten in the form    1 m 1   1   D2  xk , Clq  k 1   D2  xk , Cll k 1   l1   lq  l1 lq

1 1  m 1  Uq k    D2  xk , Clq  k 1 ,   D2  xk , Cll k 1     l1 

1 1 1 m 1   D2  xk , Clk k 1  D2  xk , Clq k 1    D2  xk , Cll  k 1 )1  ( 13 ) that for the Euclidean metric and   2 takes the form of a Cauchy distribution density function with a width parameter  q2 [9]

It is easy to see that the membership function ( 13 ) is a special case of ( 14 ) for Finally, a batch algorithm of credibilistic fuzzy clustering can be written in the  Uq k   1    xk  Clq k   2

q   m  q2    xk  Cll (k )  l1  lq 2 1  ,    1  2    

.

U  1  k   1 D2  xk , Clq   ,

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

1 q q Crq 1 k   1 Uq( 1)  k   1  supUl k   ,

 2  lq 

N   N   Clq 1   Crq 1 k  xk   Crq 1 k   .

k 1  k 1  1 form [5, 6]:

Based on this formulas, we can introduce into consideration online version of the credibilistic fuzzy clustering method in the form ( 14 ) ( 15 ) (16) (17) (18) (19) U*k 1  Uq  k 1 supUl  k 11 ,  Crq k 1  12 Uq*  k 1 1 supUl*  k 1  ,  lq  Clq  k 1  Clq  k    k 1 Crq k 1  xk1  Clq  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.

5 Evolutionary Cat Swarm Optimization To search global extremum of a function ( 1 ) ( 5 ) and ( 10 ) it is expedient to use the bioinspired evolutionary particles swarm optimization algorithms [10]. Among the swarm algorithms, one of the fastest ones are the so-called algorithms of the cats swarm [11, 12], that proved to be effective in solving a wide range of Data Mining tasks.

Cat swarm-CS model of behavior, assumes that each cat cat p of swarm consisting of Q individuals ( p  1, 2,..., Q) , can be in one of two states: Seeking Mode (SM) and Tracing Mode (TM). In this case, the seeking mode is associated with slow movements with a slight amplitude near the initial position (space scanning in the vicinity of the current position), and the tracing mode that is determined by fast jumps with a large amplitude and allows the cat cat p go put from local extremum, if she got there. The combination of local scanning and abrupt changes in the current state makes it more likely to find a global extremum compared to traditional multi-extrema optimization methods.

In the general case, both of these modes for each of the cats swarms can be described by the recurrent optimization procedure [13] catp ( 1)  catp ( )  (catp ( )  catp ( 1)) ˆ EM (catp ( ))  ( ), where cat p (  1) - state of p -th cat of swarm on  -th iteration of the search,  parameter that determines the inertia properties of the tracing mode. In a case when   0 process optimization approaches to the standard gradient search.  - seeking mode step, ˆ E(catp ( )) - gradient estimate of the goal function ( 1 ), ( 5 ) and ( 10 ) in the neighborhood of the point сat p ( ) , ( ) - a random component that introduces additional stochastic motions into the tracing process,  - parameter that specifies the amplitude of these movements.

In this algorithm, each cat can have two parallel states: search mode and tracking mode. This approach provides a search for a global extremum in the case when the number of cats in the swarm is sufficient.

6 Experimental research

Fuzzy clustering based on evolutionary cat swarm optimization (CSO) was performed on four different data samples: Iris, Cancer, Wine and Glass. Each of the data sets has a number of parameters, presented in Table 1.

Also conducted a comparative analysis of the quality of clustering data on the main characteristics quality ratings, such as: Partition Coefficient (PC), Partition Index (SC), Xie and Beni’s Index (XB) of existing clustering methods and proposed method.

Number of iterations

APrFCCSO 50 100 150

Number of iterations APosFCCSO 50 100 150

Number of iterations APosFCCSO 50 100 150

Cancer

Wine

Glass

Data Set

7 Conclusion

The problem of fuzzy clustering based on probabilistic, possibilistic and credibilistic online approaches was considered. The recurrent modifications of well-known batch procedures designed to solve problems of Data Stream Mining allow to process information in online mode as sequential additions to the system under consideration. Since the goal functions of fuzzy clustering in the general case are multi-extremal, was is proposed to refine the solutions using swarm evolutionary optimization algorithms. The modification introduced on the basis of the optimization procedure cat swarms with improved properties through the use of a stochastic gradient estimate was proposed.

The experiments confirmed the effectiveness of the developed approach, which is characterized by simplicity of numerical implementation and a sufficiently high convergency rale.

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. Kohonen , T. : Self-Organizing Maps . Berlin: Springer-Verlag ( 1995 )

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

5. 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 ).

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

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

8. 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 ).

9. Hu , Zh., Bodyanskiy , Ye, Tyshchenko, O. , Shafronenko , A. : Fuzzy clustering of incomplete data by means of similarity measures . Proc.2019 IEEE 2nd Ukr. Conf. on Electrical and Computer Engineering (UKRCON), Track 6 . Lviv , Ukraine, pp. 149 - 152 ( 2019 ).

10. Grosan , C. , Abraham , A. , Chis , M. : Swarm intelligence in Data Mining - Studies in Computational Intelligence ( 2006 )

11. Chu , S.-C., Tsai , P.-W., Pan , J.S.: Cat swarm optimization . In: Lecture Notes in Artificial Intelligence . Berlin Heidelberg: Springer-Verlag ( 2006 ).

12. Chu , S.-C., Tsai , P.-W.: Computational Intelligence based on the behavior of cats . In: “Int. J. of Innovative Computing , Information, and Control”, №1, pp. 163 - 173 ( 2007 )

13. Shafronenko , A. , Bodyanskiy , Ye. Pliss, I. , Patlan , K. : Fuzzy Clusterization of Distorted by Missing Observations Data Sets Using Evolutionary Optimization . In: Proceedings “Advanced Computer Information Technologies (ACIT' 2019 )”, Česke Budejovice , Czech Republic, June 5-7, 2019 , pp. 217 - 220 ( 2019 ). doi: 10 .1109/ACITT. 2019 .8779888

14. 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 .

15. Shafronenko , A. Yu , Bodyanskiy, Ye. V. , Pliss I.P.: The Fast Modification of Evolutionary Bioinspired Cat Swarm Optimization Method . In: 2019 IEEE 8th International Conference on Advanced Optoelectronics and Lasers (CAOL) , Sozopol, Bulgaria, 6 - 8 Sept. 2019 , pp. 548 - 552 . ( 2019 ) doi: 10.1109/CAOL46282. 2019 .9019583