A Tutorial on Clustering Algorithms
Introduction  Kmeans  Fuzzy Cmeans  Hierarchical  Mixture of Gaussians  Links
Fuzzy
CMeans Clustering
The
Algorithm
Fuzzy cmeans (FCM) is a method of clustering which allows one piece of data
to belong to two or more clusters. This method (developed by Dunn
in 1973 and improved by Bezdek in 1981) is frequently
used in pattern recognition. It is based on minimization of the following objective
function:
,
where m
is any real number greater than 1, u_{ij} is the degree of
membership of x_{i} in the cluster j, x_{i}
is the ith of ddimensional measured data, c_{j} is
the ddimension center of the cluster, and * is any norm expressing the
similarity between any measured data and the center.
Fuzzy partitioning is carried
out through an iterative optimization of the objective function shown above,
with the update of membership u_{ij} and the cluster centers
c_{j} by:
,
This iteration will
stop when , where
is a termination criterion between 0 and 1, whereas k are the iteration
steps. This procedure converges to a local minimum or a saddle point of J_{m}.
The algorithm is composed
of the following steps:

Remarks
As already told, data are
bound to each cluster by means of a Membership Function, which represents the
fuzzy behaviour of this algorithm. To do that, we simply have to build an appropriate
matrix named U whose factors are numbers between 0 and 1, and represent the
degree of membership between data and centers of clusters.
For a better understanding, we may consider this simple monodimensional example.
Given a certain data set, suppose to represent it as distributed on an axis.
The figure below shows this:
Looking at the picture, we may identify two clusters in proximity of the two data concentrations. We will refer to them using ‘A’ and ‘B’. In the first approach shown in this tutorial  the kmeans algorithm  we associated each datum to a specific centroid; therefore, this membership function looked like this:
In the FCM approach, instead, the same given datum does not belong exclusively to a well defined cluster, but it can be placed in a middle way. In this case, the membership function follows a smoother line to indicate that every datum may belong to several clusters with different values of the membership coefficient.
In the figure above, the datum shown as a red marked spot belongs more to the B cluster rather than the A cluster. The value 0.2 of ‘m’ indicates the degree of membership to A for such datum. Now, instead of using a graphical representation, we introduce a matrix U whose factors are the ones taken from the membership functions:
(a) (b)
The number of rows
and columns depends on how many data and clusters we are considering. More exactly
we have C = 2 columns (C = 2 clusters) and N rows, where C is the total number
of clusters and N is the total number of data. The generic element is so indicated:
u_{ij}.
In the examples above we have considered the kmeans (a) and FCM (b) cases.
We can notice that in the first case (a) the coefficients are always unitary.
It is so to indicate the fact that each datum can belong only to one cluster.
Other properties are shown below:
An
Example
Here, we consider the simple case of a monodimensional application of the FCM.
Twenty data and three clusters are used to initialize the algorithm and to compute
the U matrix. Figures below (taken from our interactive
demo) show the membership value for each datum and for each cluster. The
color of the data is that of the nearest cluster according to the membership
function.
In the simulation shown in the figure above we have used a fuzzyness coefficient m = 2 and we have also imposed to terminate the algorithm when . The picture shows the initial condition where the fuzzy distribution depends on the particular position of the clusters. No step is performed yet so that clusters are not identified very well. Now we can run the algorithm until the stop condition is verified. The figure below shows the final condition reached at the 8th step with m=2 and =0.3:
Is it possible to do better? Certainly, we could use an higher accuracy but we would have also to pay for a bigger computational effort. In the next figure we can see a better result having used the same initial conditions and =0.01, but we needed 37 steps!
It is also important to notice that different initializations cause different evolutions of the algorithm. In fact it could converge to the same result but probably with a different number of iteration steps.
Bibliography
Fuzzy Cmeans interactive demo