In the paper the online fuzzy clustering recurrent procedure has been introduced that allows the forming of hyperellipsoidal clusters with an arbitrary orientation of the axes is investigated. The proposed clustering system is the generalization of a number of known algorithms, it is intended to solve tasks within the general problems of Medical Data Mining, when information is sequentially fed to processing in online mode.
Clustering task has a special place in the general problem of Data Mining [1,2] since it’s solution implements in self-learning mode (unsupervised learning) when the researcher doesn’t have a marked-up training dataset in advance. It is clear that here the level of a priori uncertainty is much higher comparatively to other problems of data analysis, which led to the emergence of a variety of approaches, methods and algorithms for this problem solving [3-6], differing both in initial premises and in mathematical procedures, which often leads to different results in the end. This is distinguishes the task of clustering from other traditional Data Mining tasks such as classification, forecasting, identification of hidden dependencies contained in data, etc.
Clustering task is complicated if the data for processing are received sequentially in online mode, forming a data stream [7], in doing so the frequency of data income is such that it's impossible to process an accumulated information in time between two neighboring observations. The situation is even more complex if the amount of data is so large that it’s processing is impossible as a single array (Big Data concept [8]). Hence, the idea of online clustering of data flow seems to be very attractive, especially in Medical Data Mining task, connected with mass examination of patients.
Artificial neural networks, fuzzy reasoning systems, and hybrid neuro-fuzzy systems [3, 9, 10] can be successfully used to solve the problems of processing data in online mode, while performance issues come to the fore, especially learning processes. Obviously, that multi-epoch learning in this situation is ineffective. The incremental learning is more promising when the parameters of the clustering system are refined sequentially synchronously with data arrival. Here, first of all, it is necessary to note the clustering Kohonen’s neural networks [9] – self-organizing maps (SOM), which have shown their effectiveness in solving many real-world problems. It should be remembered that SOMs solve clustering problems under convex (linearly separable) nonoverlapped classes.
In real-world problems, data usually form overlapping classes, wherein each observation simultaneously belonging to two or more classes. It’s clear, in this case, in the process of clustering, it is necessary to calculate both the possible classes and the probability membership levels of each vector-pattern to each of the possible classes. Obviously, that in this situation, the traditional Kohonen’s neural network is ineffective. In this case, the so-called soft computing methods come to the fore, among them the most popular is the Expectation-Maximization approach (EM-algorithm) [9-15], which is based on probabilistic assumptions. It should also be noted a powerful method of Fuzzy-C-Means (FCM) [10-12] proposed by J.C.Bezdek. Both of these methods were combined in the hybrid approach proposed in [15].
However, it must be noted that EM and FCM are algorithms that process information in batch form in multi-epoch mode, which makes it impossible to use them in Data Stream Mining tasks. In this regard, recurrent adaptive FCM versions operating in the online sequential mode were introduced in [16, 17]. The disadvantages of this approach include the use of conventional Euclidean metrics, which allows the formation of clusters of only a spherical shape. Obviously that in the class conditions of a complex nonconvex form, there may be too many such spheroid clusters, which reduces the speed of the processing.
In this regard, it is advisable to develop recurrent online algorithms of sequential fuzzy clustering which allow forming data clusters of a more complex form than the hyperspheres and, particularly, hyprellipsoidal one arbitrarily oriented in the feature space of overlapping classes. 2
Batch Clustering Using Probabilistic And Fuzzy Approaches Let the initial data array be given in the dataset form of n-dimensional observation vectors such that x(k ) = ( x1 (k ) ,..., x ( k ) ,..., xn (k ))T Î Rn , where k =1, 2,..., N i describes the number of the observation in this dataset. As a result of clustering, this dataset should be divided into m (1<m<N) overlapping ellipsoidal classes.
In the framework of the statistical approach (EM-algorithm), it is assumed that the data are of a random nature and have a Gaussian density distribution:
ae n p j ( x ) = ç ( 2p )2 è
ö-1 ae
det å j ÷ exp ç
ø è
12 ( x - wj )T å-j1 ( x - wj ) ö÷ø
where wj - n-dimensional vector centroid of the j-th cluster, å j - the correlation
matrix of the j-th cluster of dimension (n ´ n) :
(
It’s obviously that using of this metrics instead of the traditional Euclidean one in the FCM algorithm allows to restore the classes of the hyperellipsoidal form with an arbitrary orientation of the axes in the initial space of features.
In the process of clustering using the EM-approach, the maximization of the function of log likelihood is implemented: å j =
N1 åkN=1 ( x ( k ) - wj ) ( x ( k ) - wj )T .
Basing on (
N N ae n p ( x ) = å p j p j ( x ) = å p j ç (2p )2 k =1 k =1 è
ö-1 ae 1 det å j ÷ exp ç ø è 2 ( x - wj )T å-j1 ( x - wj ) ö÷ø =
N ae n = å p j ç (2p )2 k =1 è
ö-1 ae 1 ö det å j ÷ø exp çè - 2 d M2 ( x, wj ) ÷ø where p j - a priori probabilities that satisfy standard conditions
It is easy to see that equation (
Due to the constraints of (
Let’s introduce Mahalanobis distance between centroids wj and vectors-pattern x(k ) in the form of dm2 ( x ( k ) , wj ) = ( x (k ) - wj ) å-j1 ( x (k ) - wj ).
T wherein, the final result can be written in the form [13] ïíw = åN p j ( x (k )) x (k ) ïî j k =1
N å p j ( x (k )).
k =1 ì ö m ö ïï p j ( x (k )) = exp aeèç - 12 d M2 ( x (k ) , wj ) ÷ø ål=1 exp aeèç - 12 d M2 ( x (k ) , wj ) ÷ø ,
It should be noted that when pj = m-1 and the unity matrix å-1 , the EM algorithm coincides with the standard K-means clustering procedure.
As it is known [4,5] K-means clustering procedure is related with minimization of the goal function
N m E ( x (k ), wj ) = ååµ j (k ) x (k ) - wj k=1 j=1 2
N m = ååµ j (k ) dE2 ( x (k ), wj )
k=1 j=1 ìï1, if x (k ) belongs to j - th cluster, µ j (k ) = í
ïî0, otherwise.
In doing so, the use of Euclidean metrics leads to the fact that the emerging clusters have a spherical shape. A modification of the standard K-means is the procedure [6] of Mahalanobis K-means, associated with the goal function
N ae m ö E ( x (k ) , wj , å j , p j ) = ålog ç å p j p j ( x (k )) ÷
k=1 è k=1 ø
N m E ( x (k ) , wj ) = å åµ j (k ) ( x(k) - wj )T å-j1 ( x(k) - wj ) =
k=1 j=1
N m = å åµ j (k ) d M2 ( x (k ) , wj )
k=1 j=1
where
(
N wj = åµ j (k ) x (k ) k =1
N åµ j (k ) = k =1 1
å x (k ) N j x(k)ÎClj where N j - is the number of observations of the initial dataset associated with the j-th cluster.
Crisp goal functions (
N m E ( x (k ), wj , µ j ) = å åµ bj (k ) d 2 ( x (k ), wj )
k=1 j=1 where a positive fuzzifier b > 0 describes blurring of the clusters, wherein most often (FCM) the value of this parameter is equal to two. At the same time, as distances d 2 ( x (k ) , wj ) – Euclidean metrics are taken.
The solution of the minimization of the goal function problem (
N åµ 2j (k ). k =1
x (k ) - wj
= m
å x (k ) - wl
l=1
-2
-2
The first relation (
çè ll=¹1j, ø÷ -1
It is interesting to note here that if the EM algorithm is based on Gaussian distribution, then fuzzy procedures are connected with the distribution of Cauchy.
It is also interesting to note that the popular clustering algorithm of Gath-Geva
[20], which minimizes the goal function (
-1 ae 1 ö dG2G ( x (k ) , wj ) = q j ( det å j ) exp ç - ( x - wj )T å=j1 ( x - wj ) ÷ø =
è 2 aeè 12 d M2 ( x, wj ) ÷ø = q j ( det å j )=1 exp ç - ö
N q j = åµ bj (k ) k =1
N m å åµlb (k ).
k =1 l=1
As a result of minimization (
T
m 2
å d 1-b ( x (k ) , w j ) ,
l=1
which is the FCM modification for the clusters-hyperellipsoids case.
(
Online Fuzzy Probabilistic Clustering In The Case Of
Hyperellipsoidal Classes
The procedures discussed above assume that the initial dataset is specified in the
batch of data form, which is processed several times in multi-epoch learning mode. It
is clear that if the information is fed for processing in the form of a data stream x (
As is known, self-organizing T. Kohonen’s map solves the clustering problem in
sequential mode by minimizing the goal function (
The self-learning rule (
Similarly (
For fuzzy situations where the clusters being formed are mutually overlapped, in
addition to the procedure (26), an assessment of the membership level can be declared
similar to (
M m å d -2 ( x (k ) , wl (k )) =
M l=1 (( x (k ) - wj (k )) å-j1 (k ) ( x (k ) - wj (k )))
T = m å (( x (k ) - wl (k ))T ål-1 (k ) ( x (k ) - wl (k ))) l=1 -1
Next, solving the nonlinear programming problem (goal function (
E l=1 ìïwj (k +1) = wj (k ) +h (k +1)µ 2j (k +1) ( x (k +1) - wj (k )), í ïîµ j (k +1) = x (k +1) - wj (k ) -2 m å x (k +1) - wl (k ) -2 . l=1
Here, the multipliers µ bj (k +1) , µ 2j (k +1) in fact are neighbourhood functions in Kohonen’s self-learning rule “Winner Takes More”. Wherein, instead of the usual Gaussian, generalized Gaussian and Cauchian are used. It is interesting to note that the receptive fields parameters of these functions are automatically evaluated here.
It should be noted that the recurrent modification of the Gath-Geva algorithm [20] was introduced in [23], but this modification is not related to optimization procedures. Further modification can be written in the form of recurrence relations ïìwj (k +1) = wj (k ) +h (k + 1) ( x (k + 1) - wj (k )), if w j (k ) - " winner ", ïîíå j (k + 1) = (1-h (k + 1)) å j (k ) +h (k ) ( x (k + 1) - wj (k )) ( x (k + 1) - w j (k ))T .
It can be noticed that relations (30) are the WTA self-learning rule of T.Kohonen and the procedure for correcting the correlation matrix. It is interesting to note that this matrix doesn’t fluent the process of the centroids tuning.
A more effective is algorithm also proposed in [23], where a correction is made to the membership levels of the form: (30) (31) (32) k +1 U j (k +1) = åµ bj (t ) = U j (k ) + µ bj (k +1).
t =1 In this case, the algorithm has the form: ì µ bj (k +1) ïwj (k +1) = wj (k ) + ï U j (k +1) ï ï ae ïå j (k +1) = U j (k ) U j (k +1) çç å j (k ) + í è ïï! ( x (k +1) - wj (k ))T ) , ï ï 2 ïîµ j (k +1) = dG1-Gb ( x (k +1) , wj (k )) ( x (k +1) - wj (k )) , µ bj (k +1) U j (k +1)
( x (k +1) - wj (k )) !
Algorithm (32) is close to procedure (28) and coincides with it when h (k +1) = U -j1 (k +1), however, the metric dG2G ( x (k +1) , wj (k )) used is significantly different from the previously used one dE2 ( x (k +1) , wj (k )) . Once again, in this algorithm, the correlation matrix å j (k ) does not affect the process of centroids tuning.
Combining procedure (25) using the gradient of Mahalanobis ’metrics and the standard Gath-Geva algorithm, we will get a relation describing the fuzzy clustering method with the hyperellipsoidal classes: ( x (k +1) - wj (k )) !
(33) Using the fuzzifier b = 2 , we get adaptive recurrent procedure [24]: ì ïU j (k +1) = U j ( k ) + µ 2j (k +1) , ï µ 2j (k +1) ïïwj (k +1) = wj (k ) + U j ( k +1) å-j1 ( x (k + 1) - wj (k )) , ï ï U j (k ) ae µ 2j (k +1) ïíå j (k +1) = U j (k +1) çèç å j (k ) + U j (k +1) ïï! ( x (k +1) - wj (k ))T ) , ï ï ïîµ j (k +1) = dG-G2 ( x (k +1) , wj (k )) m å dG-G2 ( x (k +1) , wj (k )). l=1 ( x (k +1) - wj (k )) (34) 4
Computer Experiments With Medical Data As a demonstration of the developed method Online Fuzzy Probabilistic Clustering, two medical samples from the UCI repository were used. The first series of experiments was performed on a dataset of Breast Cancer Wisconsin, which related to the applied problem in the medical field. The data describe two types of tumors – malignant or benign. Clustering results are represented as a 3D model.
The structure of Breast Cancer Wisconsin dataset is complex and non-linear. The maximum classification accuracy reached 97.5 percent. Fig. 1, 2, and 3 show the visualization of clustering results in three different projections. For visualization of our dataset, that was previously compressed with Principal Component Analysis method (PCA-method) into three principal components.
The received results we compared with standard EM-algorithm and Fuzzy Cmeans method of J. Bezdek. The results of the experiment can be seen in Table 1. In the first row of the table, the outputs of EM-procedure are represented, in the second row – FCM one and in the third – the proposed approach. It can certainly be seen, that considered procedures surpass the quality of results both EM and FCM algorithms.
For each cell nucleus, ten real signs are calculated that are columns in the sample: radius (average distance from the center to the points along the perimeter), texture (standard deviation of gray values); perimeter; square; smoothness; compactness; concavity (the severity of the concave parts of the contour); the number of firing points (the number of concave parts on the contour of the tumor); symmetry; fractal size.
The obtained accuracy ranged from 89% to 97.5%, which in general was from 569 examples correctly classified from 490 to 547 examples.
The second series of experiments was carried out on a sample of Dermatology which is the data obtained as a result of a study of the histopathological features of patients with dermatological diseases. The goal is to determine the type of dermatological disease.
The dataset has 33 attributes, of which: one target attribute, which shows the presence of a specific dermatological disease, there are 6 classes. Classification: 1st class (psoriasis) – 112 examples, 2nd class (seborrheic dermatitis) – 61 examples, 3rd grade (lichen) – 72 examples, 4th grade (pink lichen) – 49 examples, 5th grade (chronic dermatitis) – 52 examples, 6th grade (lichen planus) – 20 examples.
This sample is not quite popular for testing various algorithms for medical data analytics since it has several linearly inseparable clusters that are difficult to process with standard clustering algorithms.
The final results of the clustering of the developed method are presented in Fig. 4 and 5. As can be seen in Fig. 4 and 5 some examples of one cluster are very close to another cluster, this suggests that some clusters are not linearly separable.
A series of experiments indicate that the proposed Online Fuzzy Probabilistic Clustering method works quite quickly and shows the high quality of clustering of data arrays in conditions of non-linear data. And also the experiment proves that the proposed method can solve practical problems in the field of medical data processing. The problem of online fuzzy clustering of data that are fed to processing sequentially in the form of data stream was considered. A feature of approach under consideration is that the formed classes have the hyperellipsoidal shape with an arbitrary orientation of the axes in feature space. The proposed procedure uses Mahalanobis’ metrics and also it is the generalization of a number of well-known clustering algorithms, has high speed and simple, in computational implementation. The obtained results allow solving a number of problems arising in Data Mining and especially Medical Data Mining ones connected with mass examination of patients.