Fuzzy C-means Clustering

Clustering is a kind of algorithm that is associated with unsupervised learning. In this algorithm, the data point is organized into different clusters(groups) and the new data are arranged according to their features in the pre-organized clusters. Fuzzy c means clustering algorithm(also referred as soft clustering) is a form of clustering algorithm where each item may belong to more than one group, where the degree of membership for each group is given by a probability distribution over the clusters.

Fuzzy c means clustering algorithm was developed by Dunn and was later improved by Bezdek. It is most useful when the number of clusters is pre-determined and it tries to categorize the new elements on their respecetive clusters. However, the fuzzy c means algorithm doesn’t calculate the certainty of an element belonging to any cluster. It calculates the likelihood that the element may belong to a cluster by the probability distribution over the clusters.

Steps involved in Fuzzy c means algorithm

Step 1: Fix the number of clusters C(2C<n) and select a value for fuzziness parameter(m). Normally the value of m lies between 1.5 and 2. Initialize partition matrix U = [uik] matrix, U(0).

If we have 5 points and there are two clusters C1 and C2, then the partition matrix is given by:

U(0) = 0 0 1 1 1 – C1

            1 1 0 0 0 – C2

Similarly, U(1) =  0 0 1 1 1

                             1 1 0 0 0

here, r = 0,1,2,…. *

Step 2: At each steps, calculate the cluster centers.

Cluster Center(Vij) = 

Step 3: Update the partition matrix

uik

Step 4: Check for convergence:

if ||U(r+1) < U(r)|| <= ɛL then stop,

else return to step 2.

We demonstrate fuzzy c means algorithm with an example.

Let us consider 4 points with their x and y values as shown in the table below:

X

Y

1

2

3

4

1

3

2

4

First of all, let us fix the value of C i.e., the number of clusters. Let us consider the value of C to be 2. Let the fuzziness parameter(m) be 2.

Criterion for convergence of ɛL = 0.01.

Now, we need to initialize the fuzzy partition/ Membership Metrics(U)

U(0) = 1 1 1 0 – C1

            0 0 0 1 – C2

After initialization of the partition matrix, we will calculate the cluster centers.

Cluster Center(Vij) = 

For C = 1,

V1112x1j + μ22x2j + μ32x3j + μ42x4j )/ μ12 + μ22 + μ32 + μ42

= 1. x1j + 1.x2j + 1.x3j + 0.x4j / 1 + 1 + 1 + 0

= 1*1 + 1*3 + 1*1 + 0* 2 / 3

= 5/3

= 1.67

V12 = 2*1+4*1+3*1 + 4*0 / 1 + 1 + 1

= 3

Cluster Center = {1.67, 3}

For C = 2, 

we know that for C2 the value of μ42 will only be 1. So, the value of cluster center becomes:

V21 = 2/1

= 2

V22 = 4/1

= 4

Cluster Center for C =2 is {2, 4}

Now the next step is to calculate distance of each data point from each cluster center.

d11 = ((1 – 1.67)2 + (2-3)2)= 1.2 d21 = ((1 – 2)2 + (2 -4)2)= 2.23

d12 = ((3-1.67)2 + (4-3)2 )= 1.66 d22 = ((3-2)2 +(4-4)2)= 1

d13 = ((1-1.67)2 + (3-3)2)= 0.67 d23 = ((1-2)2 + (3-4)2)= 1.41

d14 = ((2-1.67)2 + (4-3)2)= 1.05 d24 = ((2 – 2)2 + (4 – 4)2)= 0

Now we update the partition matrix with the following formula:

μik

Updated partition matrix (μ11) = 

= [(d11 / d11)2 + (d11/d21)2 ]-1

= [(1.2/1.2)2 + (1.2/2.23)2]-1

= [1 + 0.29]-1

=[1.29]-1

= 0.77

μ12 = [(d12/d12)2 + (d12/d22)2]-1

= [(1.66/1.66)2 + (1.66/1)2]-1

= [1 + 2.75]-1

= [3.75]-1

=0.26

μ13 = [(d13/d13)2 + (d13/d23)2]-1

= [(0.67/0.67)2 + (0.67/0.41)2]-1

= [1 + 2.67]-1

= 0.27

μ14 = [(d14/d14)2 + (d14/d24)2]-1

= [(1.05/1.05)2 + (1.05/0)2]-1

= [1 + (1.05/0)2]-1

= 0

We get the update fuzzy partition matrix as:

U(1) = 0.77 0.26 0.27 0 – C1

0.23 0.74 0.73 1 – C2

Check for convergence:

(0.77^2 + 0.23^2 – 1^2 ), (0.26^2 +0.74^2 – 1^2), (0.27^2 + 0.73^2 – 1^2), (0^2 + 1^2 – 1^2)

max |{(-0.3542), (-0.3848), (-0.3942), (0)}|

= 0.3942 which is greater that our convergence condition 0.01. So we repeat the process from second step with the new partition matrix.

Difference between k means clustering and fuzzy c means clustering

The main difference between the k means clustering and fuzzy c means clustering is that in the k means clustering the point may lie in only one cluster however in fuzzy c means clustering the probability of the point lying in all the clusters are calculated.

Fuzzy c means clustering is one of the most used clustering algorithms.

Why to use fuzzy c means algorithm?

We use fuzzy c means algorithm as it is considered more applicable algorithm in the performance of those tasks which consists of real world limitations like noise, shadowing and variation in clustering. Traditional clustering algorithm may not give appropriate results in these cases.

Fuzzy c means algorithm using MATLAB

data = load(“example.dat”) % load sample data

no_of_clusters = 2 %number of clusters

[center, U, obj_fcn] = fcm(data, n_clusters)

Leave a Comment

Your email address will not be published. Required fields are marked *