Online Neuro Fuzzy Clustering of Data with Omissions and Outliers based on Сompletion Strategy

Abstract

In the paper new recurrent adaptive algorithms for fuzzy clustering of data with missing values are proposed. This algorithm is based on fuzzy clustering procedures and self-learning Kohonen's rule using principle “Winner-Takes-More” with Cauchy neighborhood function. Using proposed approach it's possible to solve clustering task in on-line mode in situation when the amount of missing values in data is too big.

1 Introduction

The problem of data sets described by vector-images clustering often occurs in many applications associated with Data Mining, but recently the focus on fuzzy clustering [ 1-3 ], when processed vector-image with different levels of probabilities, possibilities or memberships, can belong to more than one class.

However, there are situations when the data sets contain omissions and outliers, the information that is lost. In this situation more effective is to use mathematical apparatus of Computational Intelligence [ 4 ] and, first of all artificial neural networks [ 5 ], that solve the task of restoring the lost observations, and modifications of the popular method of fuzzy c-means [ 6 ], which solve the problem of clustering without recovery of data.

Existing approaches [ 7,8 ] for data processing with omissions and outliers, are efficient in cases when the massive of the original observations is given in batch form and does not change during the processing. At the same time, there is a wide class of problems in which the data that arrive to the processing, have the form of sequence that is feed in real time as it occurs in the training of Kohonen self-organizing maps [ 9 ] or their modifications [ 10 ]. In this regard we introduced [ 11 ] the adaptive neurofuzzy Kohonen network to solve the problem of clustering data with gaps based on the strategy of partial distances (PDS FCM). However, in situations where the number of such omissions and outliers is so much, the strategy of partial distances [ 12 ] may be not effective, and therefore it may be necessary, along with the solution of fuzzy clustering simultaneously estimate the missing observations. In this situation, a more efficient is approach that is based on the optimal expansion strategy (OCS FCM) [ 6 ]. This work is devoted to the task of on-line data clustering using the optimal expansion strategy, adapted to the case when information is processed in a sequential mode, and its volume is not determined in advance. 2 Probabilistic adaptive fuzzy clustering with missing data based on the optimal completion strategy Baseline information for solving the task of clustering in a batch mode is the sample of observations, formed from N n -dimensional feature vectors X  {x1, x2 ,..., xN }  Rn , xk  X , k  1, 2,..., N . The result of clustering is the partition of original data set into m classes (1  m  N ) with some level of membership Uq (k ) of k -th feature vector to the q -th cluster (1  q  m) . Incoming data previously are centered and standardized by all features, so that all observations belong to the hypercube [1,1]n . Therefore, the data for clustering form array X  {x1,..., xk ,..., xN }  Rn , xk  (xk1,..., xki ,..., xkn )T , 1  xki  1 , 1  m  N , 1  q  m , 1  i  n , 1  k  N that is, all observations xki are available for processing.

Introducing the objective function of clustering [ 1 ]

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

k 1 q1 m N with constraints Uq (k )  1, 0  Uq (k )  N and solving standard nonlinear q1 k 1 programming problem, we get the probabilistic fuzzy clustering algorithm [ 2, 3 ]       Uq( 1) (k ) 

N  (Uq( 1) (k )) xk  ( 1)  k 1 wq N   (Uq( 1) (k ))  k 1 , where wq - prototype (centroid) of q -th cluster,   1 - parameter that is called fuzzyfier and defines "vagueness" of boundaries between classes, D2 ( xk , wq ) - the distance between xk and wq in adopted metric,   0,1, 2,... - index of epoch of information processing which is organized as a sequence of w(0)  U (1)  w(1)  U (2)  ... . The calculation process continues until satisfy the q q q q condition w( 1)  w( )    1  q  m,

q q (here  - defines threshold of accuracy) or until the specified maximum number of epochs Q (  0,1, 2,..., Q ).

Note also that when   2 and 1 (D2 (xk , wq( ) ))1 m 1 ,  (D2 (xk , wl( ) ))1 l 1 (1) (2) D2 (xk , wq )  xk  wq , 2 where  (k  1) - learning rate parameter, Uq (k  1) - bell-shaped neighborhood function of neuro-fuzzy Kohonen network (Cauchy function), designed to solve the problems of fuzzy clustering [ 10, 11 ], based on the principle "Winner Takes More» (WTM) [ 9 ].

In the presence of an unknown number of missing values in vector images xk , that form array X , following [ 6 ], we introduce the sub-arrays: X F  {xk  X | xk - vector containing all components} ;

The optimal completion strategy consists in the fact that the elements of sub-array X G are considered as additional variables, which are estimated by minimization of objective function E . Thus, in parallel with clustering (optimization E by U q (k ) and w ) estimation of missing observations is made (optimization E by q xki  X G ). In this case, the algorithm of fuzzy c-means based on the optimal expansion strategy can be written as the following sequence of steps [ 6 ]: 1. Setting the initial conditions for the algorithm:   0 ; 1  m  N ;   0 ; wq(0) ; 1  q  m ;   0,1, 2,...,Q ; X (0)  {1  xˆ(0)  1} , where X (0)  NG (1  N

G ki G G  (n 1)N ) arbitrary initial estimates xˆk(i0) of missing values xki  X G ; 2. Calculation of membership levels by solving the optimization problem:

Uq (k ) U ( 1) (k )  arg min E(Uq (k ), wq( ) , X ( ) )  q G m l1 (D2 ( xˆk( ) , w( ) ))1

q  (D2 (xˆk( ) , w( ) ))1 l 1

1  ( xˆ( )  w( ) 2 )1 k q

1 l1 m 1  ( xˆ( )  w( ) 2 )1 k l (here vector xˆk( ) differs from xk by replacing missing values xki  X G by estimates xˆk(i ) that are calculated for the  -th epoch of data processing); 3. Calculation the centroids of clusters:

wq wq( 1)  arg min E(Uq( 1) (k ), wq , X G( ) )  k 1 N  (U ( 1) (k )) xˆ( )

q k 4. Checking the stop conditions: w( 1)  w( )    1  q  m or   Q , then the algorithm terminates, othq q erwise go to step 5; 5.

Estimation of missing observations by solving the optimization problem: or, equivalently that leads to

X G( 1)  arg min E(U q( 1) (k ), wq( 1) , X G )

XG E(U q( 1) (k ), wq( 1) , X G ) xˆki

 0, xˆk(i 1)  m (U q( 1) (k )) wq(i 1) m (U q( 1) (k )) .

q1 q1 Information processing with this algorithm is organized as a sequence w(0)  U (1)  xˆ(1)  w(1)  U (2)  ...  w( )  U ( 1)  q q ki q q q q  xˆk(i 1)  wq( 1)  ...  wq(Q) . 3 Possibilistic adaptive fuzzy clustering with missing data based on the optimal completion strategy The main disadvantage of conventional probabilistic algorithms is connected with the constraints on membership levels which sum has to be equal unity. This reason has led to the creation of possibilistic fuzzy clustering algorithms [ 14 ].

In possibilistic clustering algorithms the objective function has the form

N m m N E(U q (k ), wq ,  q )   U q (k )D2 ( xk , wq )    q  (1  U q (k )) k 1 q1 q1 k 1 (where the scalar parameter   0 determines the distance at which level of membership equals to 0.5, i.e. if D2 ( xk , wq )   q , then wq (k )  0.5 ) and its minimization by U q (k ) , wq ,  q leads to the result:  1 U q( 1) (k )  1 1  (D2 ( xk , wq( ) )  q( ) ) 1 , wq( 1)  N (U q( 1) (k )) xk  k 1 k 1  q( 1)  kN1 (U q( 1) (k )) D2 ( xk , wq( 1) )

N  (U ( 1) (k )) , q (3) In the on-line processing recurrent form of the algorithm (3) can be written as [ 10,13 ]: and the second relation in (4) differs only in the form of the neighborhood function Uq (k  1) . Thus, the recurrent possibilistic fuzzy clustering is based on Kohonen competitive self learning.

Considering the situation with missing observations and using the optimal completion strategy, as the objective function of possibilistic fuzzy clustering use the expression:

E(Uq (k ), wq , q , XG )  N m Uq (k )D2 (xˆk , wq )  m  q N (1  Uq (k )) k 1q1 q1 k 1 and its minimization leads to the system of obvious relations: or E(Uq (k ), wq , q , X G ) Uq (k )  0,   wq E(Uq (k ), wq , q , XG )  0, E(Uq (k ), wq , q , X G ) xˆki  0,  E(Uq (k ), wq , q , X G )  q  0,   Uq( 1) (k )  1 1  (

1 D2 (xˆk( ) , wq( ) ) ) 1 , k 1 m  ( 1)   (Uq( 1) (k )) wq(i 1) xˆki  q1  N ( 1) )  q( 1)   (Uq( 1) (k )) D2 (xˆk( 1) , wq  k 1 N (Uq( 1) (k )) , k 1 m (Uq( 1) (k )) , q1 N (Uq( 1) (k )) . k 1 (5)

Similarly to probabilistic fuzzy clustering based on optimal completion strategy we can organize the possibilistic clustering process with missing observations 2 ) 1  1

, , xˆk()1  wq (k )

1 or in accelerate time  ( 1) (k  1)  U q   1  (  wq(0) (k  1)  wq(Q) (k ),  ˆ( 1)  q1  xk 1,i (6) (7) 2 ) 1  1

, , 2

, ( 1) (k  1))  (U q

 ( 1) ( p))  (U q

xˆ(p 1)  wq( 1) (k  1) k 1 p1

( 1) ( p))  (U q 2 .

It’s understandable that the algorithm (7) from computational point of view is the most unwieldy; however, its advantage is that it can be used in on-line mode to detect the emergence of new clusters. In the procedures (6), (7) is unnecessary accumulate the processed sample, which is important in problems (for example, Web Mining), where large amounts of information have to be processed.

4 Experiments

Experimental research conducted on two standard samples of data such as Wine and Iris UCI repository.

To estimate the quality of the algorithm we used quality criteria partitioning into clusters such as: Partition Coefficient (PC), Classification Entropy (CE), Partition Index (SC), Separation Index (S), Xie and Beni's Index (XB), Dunn's Index (DI).

We also compared the results of our proposed algorithm with other more wellknown such as Fuzzy C-means (FCM) clustering algorithm and Gustafson-Kessel clustering algorithm.

As seen from the experimental results (Table 1, Table 2 and Table 3), the proposed algorithm shown better results than the FCM and Gustafson-Kessel clustering algorithm. s p a G 0 1

Iris UCI repository

Wine UCI repository

I I B B E E S S D D C C X X C S 5 7 7 3 , 0 4 7 1 0 , 0 9 1 2 5 , 0 C S 9 0 2 1 , 0 1 8 1 0 , 0

Adaptive fuzzy

possibilistic clustering data with missing values FCM s p a G 0 5 s p a G The problem of probabilistic and possibilistic fuzzy adaptive clustering, containing a priori unknown number of gaps, based on the optimal completion of data strategy is considered. The proposed algorithms are based on the recurrent optimization of a special type of goal functions. Missing observations are replaced by their estimates also obtained in the solution of optimization problem. Сentroids of recovered clusters are tuned using a procedure close to the T.Kohonen WTM-rule with the function of the neighborhood (membership), having the Cauchian form.

References

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

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

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

4. Rutkowski , L. : Computational Intelligence. Methods and Techniques . BerlinHeidelberg: Springer-Verlag ( 2008 )

5. Marwala , T. : Computational Intelligence for Missing Data Imputation, Estimation, and Management: Knowledge Optimization Techniques . Hershey-New York, Information Science Reference ( 2009 )

6. Hathaway , R.J. , Bezdek , J.C. : Fuzzy c -means clustering of incomplete data . IEEE Trans. on Systems, Man, and Cybernetics , № 5 , 31 , pp. 735 - 744 ( 2001 )

7. Zagoruyko , N.G. : Empirical predictions . Novosibirsk, Nauka ( 1979 )

8. Zagoruyko , N.G. : Applied Data Analysis and Knowledge . Novosibirsk ( 1999 )

9. Kohonen , T. : Self-Organizing Maps . Berlin: Springer-Verlag ( 1995 )

10. Gorshkov , Ye., Kolodyazhniy , V. , Bodyanskiy , Ye.: New recursive learning algorithms for fuzzy Kohonen clustering network . Proc. 17th Int. Workshop on Nonlinear Dynamics of Electronc Systems. (Rapperswil , Switzerland, June 21-24, 2009 ) Rapperswil, Switzerland, pp. 58 - 61 ( 2009 )

11. Bodyanskiy , Ye., Shafronenko , A. , Volkova , V. : Adaptive clustering of incomplete data using neuro-fuzzy Kohonen network . In “Artificial Intelligence Methods and Techniques for Business and Engineering Applications” - Rzeszow-Sofia: ITHEA, pp. 287 - 296 ( 2012 )

12. Shafronenko , A. , Dolotov , A. , Bodyanskiy , Y. , Setlak , G.: Fuzzy Clustering of Distorted Observations Based on Optimal Expansion Using Partial Distances . In “2018 IEEE Second International Conference on Data Stream Mining & Processing (DSMP)” , pp. 327 - 330 ( 2018 )

13. Bodyanskiy , Ye.: Computational intelligence techniques for data analysis . Lecture Notes in Informatics. Bonn: GI ( 2005 )

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