A Comparative study Between Fuzzy Clustering Algorithm and Hard Clustering Algorithm

the

3. Update U(k) , U(k+1)

4.

If || U(k+1) - U(k)||< then STOP; otherwise

return to step 2.

In FCM, data are bound to each cluster by means of a

Membership Function, which represents the fuzzy

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

,

This

iteration

will

stop

3. K-Means Algorithm:

when

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

, where

The formal algorithm is :

1.

Initialize U=[uij] matrix, U(0)

2. At k-step: calculate the centers vectors

U(k)

C(k)=[cj]

with

The K-Means [2] is one of the famous hard clustering

algorithm [5][6][7]. It takes the input parameter k, the

number of clusters, and partitions a set of n objects

into k clusters so that the resulting intra-cluster

similarity is high but the inter-cluster similarity is

low. The main idea is to define k centroids, one for

each cluster. These centroids should be placed in a

cunning way because of different location causes

different results. So, the better choice is to place them

as much as possible far away from each other. The

next step is to take each point belonging to a given

data set and associate it to the nearest centroid. When

no point is pending, the first step is completed and an

early groupage is done. At this point we need to re-

calculate k new centroids. After we have these k new

centroids, a new binding has to be done between the

same data set points and the nearest new centroid. A

loop has been generated. As a result of this loop we

may notice that the k centroids change their location

step by step until no more changes are done. In other

any more.

words

Finally,

at minimizing

an objective function, in this case a squared error

function. The objective function

centroids do not move

algorithm

aims

this

ISSN: 2231-2803 http://www.ijcttjournal.org Page109

International Journal of Computer Trends and Technology (IJCTT) – volume 10 number 2 – Apr 2014

,

where

is a chosen distance measure

between a data point

and the cluster centre

is an indicator of the distance of the n data points

from their respective cluster centers.

,

The Formal Algorithm [7] is:

1. Select K points as initial centroids.

2. Repeat.

3.

Form k clusters by assigning all points to the

closest centroid.

Recompute the centroid of each cluster.

4.

5. Until the centroids do not change.

K-means algorithm is significantly sensitive to the

initial

randomly selected cluster centers. The

algorithm can be run multiple times to reduce this

effect. The K-Means is a simple algorithm that has

been adapted to many problem domains and it is a

good candidate to work for a randomly generated

data points.

4. Experimental Results:

We chose Matlab for our experiments. The

experiments done are mentioned below:

4.1 Matlab Implementation of K-means algorithm:

in

[8].

Matlab

We have “kmeans” function to perform K-means

The

clustering

function kmeans performs K-Means clustering, using

an iterative algorithm that assigns objects to clusters

so that the sum of distances from each object to its

cluster centroid, over all clusters, is a minimum. k

means returns an n-by-1 vector IDX containing the

cluster indices of each point. By default, kmeans uses

squared Euclidean distances. When X is a vector,

kmeans treats it as an n-by-1 data matrix, regardless

of its orientation.

[IDX,C] = kmeans(X,k) returns the k cluster centroid

locations in the k-by-p matrix C.

[IDX,C,sumd] = kmeans(X,k) returns the within-

cluster sums of point-to-centroid distances in the 1-

by-k vector sumd.

[IDX,C,sumd,D] = kmeans(X,k) returns distances

from each point to every centroid in the n-by-k

matrix D.

The Iris flower

“iris ” dataset [9][11] is chosen for the purpose of our

data

experiment.

set or Fisher's Iris data set (some times also known as

Anderson's Iris data) is

a multivariate data

set introduced by Sir Ronald Fisher (1936) as an

example of discriminant analysis. The data set

consists of 50 samples from each of three species

of Iris (Iris setosa, Iris virginica and Iris versicolor).

Four features were measured from each sample: the

length and the width of the sepals and petals, in

centimeters[9].

Figure1: A 3-D plot of Iris data

We specify 4 clusters and 5 replicates. Also

‘display’ parameter is used for printing out final sum

ISSN: 2231-2803 http://www.ijcttjournal.org Page110

International Journal of Computer Trends and Technology (IJCTT) – volume 10 number 2 – Apr 2014

of distances for each of the solutions. Replicate

parameter is used to avoid local minima. The code

for this purpose and with result obtained is as

follows:

[cidx3,cmeans3,sumd3]

kmeans(meas,4,'replicates',5,'display','final');

=

Replicate 1, 6 iterations, total sum of distances =

71.7595.

So, we found the best total sum of distances as

57.2285, and total elapsed time required is 1.4531

seconds.

4.2 Matlab Implementation of Fuzzy C Means:

In Matlab, Fuzzy C Means clustering can be

performed with the function “fcm”. This function can

be described as follows[10]:

[center, U, obj_fcm] = fcm(data,cluster_ n)

Replicate 2, 8 iterations, total sum of distances =

57.2656.

The arguments of this function are:

Replicate 3, 4 iterations, total sum of distances =

57.2656.

1) data - lots of data to be clustering, each line

describes a point in a multidimensional feature space;

Replicate 4, 16 iterations, total sum of distances =

71.4452.

2) cluster_n - number of clusters (more than one).

Replicate 5, 17 iterations, total sum of distances =

57.2656.

Best total sum of distances = 57.2656

The function returns the following parameters:

1) center - the matrix of cluster centers, where each

row contains the coordinates of the center of an

individual cluster;

2) U - resulting matrix;

3) obj_fcn - the objective function value at each

iteration

This means as input arguments, fcm takes a data set

and a desired number of clusters. As output, it returns

optimal clusters center, the resulting matrix U and the

value of the objective function at each iteration. For

our experiment, the same iris data set [9][11] is taken

because, to compare the performance of K-means

algorithm and Fuzzy C Means algorithm,

the

experiments should be performed on the same

dataset. The data to be clustered is 4-dimensional

data and represents sepal length, sepal width, petal

length, and petal width. From each of the three

groups

two

characteristics (for example, sepal length vs. sepal

width) of the flowers are plotted in a 2-dimensional

plot.

(setosa, versicolor and virginica),

Figure 2: Plotting of Four Clusters returned by

kmeans function

ISSN: 2231-2803 http://www.ijcttjournal.org Page111

International Journal of Computer Trends and Technology (IJCTT) – volume 10 number 2 – Apr 2014

5. Comparison of FCM and K-Means

done on

the basis of Experimental

Results:

Comparison between FCM and K- Means algorithms

is done on the basis of their respective computation

times taken for the experiments and on the basis of

their respective time complexities. First of all, it is

merely visible from the observations that FCM

algorithm is taking more time for computation than

that of K-Means.

Figure 3 : A Two Dimensional Plot Of The Iris

Dataset

We initialized the total number of clusters as 4 ,

maximum iteration no 100, exponent for U as 2.0 and

minimum improvement as 1e-6. After initializing

these values, we run the Fuzzy C Means. At

maximum Iteration count = 28, the value of the obj.

fcn obtained is 4168.707061. The total elapsed time

taken is 4 seconds.

Figure 4: Figure showing initial and final clusters

Figure 5: FCM Vs K-Means in terms Elapsed Time

The time complexity of K-Means algorithm is

O(ncdi) and

is

O(ndc2i)[12][13][14].

time complexity of FCM

Here n is the number of data points, c is the number

of clusters, d is the dimension of the data and i is the

number of iterations. Say n= 200, c = 1 to 4, d = 4, i=

28. Then, we have :

Exp

No.

1

2

3

4

No. Of

Clusters

1

2

3

4

K-Means

Complexity

22400

44800

67200

89600

FCM

Complexity

22400

89600

201600

358400

ISSN: 2231-2803 http://www.ijcttjournal.org Page112

International Journal of Computer Trends and Technology (IJCTT) – volume 10 number 2 – Apr 2014

research work concludes the fact that the K-Mean’s

performance is better than FCM’s performance in

terms computational time. Since, fuzzy clustering

algorithm includes much more fuzzy logic based

calculations, so its computational time increases

comparatively.

References:

[1] A. K. Jain, M. N. Murty and P. J. Flynn, “Data Clustering: A

review”, ACM Computing Surveys, vol. 31, no. 3, 1999.

[2] MacQueen, J. B. ,"Some Methods for classification and

Analysis of Multivariate Observations". Proceedings of 5th

Berkeley Symposium on Mathematical Statistics and Probability 1.

University of California Press. 1967, pp. 281–297

[3] J. C. Dunn , "A Fuzzy Relative of the ISODATA Process and

Its Use in Detecting Compact Well-Separated Clusters", Journal of

Cybernetics 3: 1973, 32-57

[4] J. C. Bezdek ,"Pattern Recognition with Fuzzy Objective

Function Algoritms", Plenum Press, New York, 1981

[5] Steinhaus, H., "Sur la division des corps matériels en

parties". Bull. Acad. Polon. Sci.(in French) 4 (12),1957, pp. 801–

804.

[6]Lloyd., S. P. "Least squares quantization in PCM". IEEE

Transactions on Information Theory 28 (2), 1982, pp. 129–137

[7] Shaeela Ayesha, Tasleem Mustafa, Ahsan Raza Sattar &

M.Inayat Khan, “Data Mining Model for Higher Education System

“,European Journal of Scientific Research, ISSN 1450-216X

Vol.43 No.1 ,2010, pp.27.

[8]

analysis.html

http://www.mathworks.in/help/stats/examples/cluster-

[9] http://archive.ics.uci.edu/ml/datasets/Iris

[10] Makhalova Elena, “Fuzzy C Means Clustering In Matlab”,

The 7th International Days of Statistics and Economics, Prague,

September 19-21, 2013,pp. 905-914 .

[11] A. Asuncion and D. J. Newman, UCI Machine Learning

Repository Irvine, CA: University of California, School of

Information and Computer Science, 2013.

[12] S. l Har-Peled and B. Sadri, "How fast is the k-means

Method," in ACM-SIAM Symposium on Discrete Algorithms,

Vancouver, 2005.

[13] A. Rui and J. M. C. Sousa, “Comparison of fuzzy clustering

algorithms

International Symposium on

for Classification”,

Evolving Fuzzy Systems, 2006 , pp. 112-117.

[14]Soumi Ghosh and Sanjay Kumar Dubey, “Comparative

Analysis of K-Means and Fuzzy C-Means Algorithms”, IJACSA,

Vol. 4, No.4, 2013,pp. 35-39.

Figure 6: FCM Vs K-Means

Complexities with Varying Number Of Clusters

in

terms Time

So, we have seen that, as soon as the number of

cluster increases, the time complexity of FCM

increases with a more rapid growth rate than that of

K-Means algorithm. This draws the conclusion that

K- Means algorithm is less complex than FCM.

6. Conclusion:

Choosing a particular clustering algorithm is solely

dependent on the type of the data to be clustered and

the purpose of the clustering applications. Hard

clustering algorithm like K-Means algorithm is

suitable for exclusive clustering task; on the other

hand, fuzzy clustering algorithm like FCM is suitable

for overlapping clustering task. In some situations,

we cannot directly consider that data belongs to only

one cluster. It may be possible that some data’s

properties contribute to more than one cluster. Like in

case of document clustering, a particular document

may be categorized into two different categories. For

those purposes, we generally prefer membership

value based clustering like FCM. In this paper, we

have gone through a comparative research between

Fuzzy clustering algorithm and Hard clustering

algorithm.FCM is chosen on the behalf of Fuzzy

clustering algorithm and K-Means algorithm

is

chosen on the behalf of Hard clustering algorithm.

On the basis of experiments, we have found that the

computational time of K-Means algorithm is less than

that of FCM algorithm for the Iris dataset. So, this

ISSN: 2231-2803 http://www.ijcttjournal.org Page113