Question

INTRODUCTION TO DATA MINING

Question 3: K-means clustering

Use the k-means algorithm and Euclidean distance to cluster the following seven examples into two clusters:

A1=(1, 1), A2=(1.5, 2), A3=(3,4), A4=(5,7), A5=(3.5,5), A6=(4.5,5), A7=(3.5,4.5)

Suppose that the initial seeds (centers of each cluster) are A1 and A4. Run the k-means algorithm for 2 epochs. At

the end of this epoch show:

a) Distance matrix by calculating Euclidean distance.

b) The new clusters (i.e. the examples belonging to each cluster)

c) The centers of the new clusters

d) Where the algorithm should stop?

Answer 1

At the end of second epoch:

Let C1 & C2 represents the cluster means, and after 2^nd epoch C1 & C2 turns out to be

C1 = (1.25 , 1.5)

C2 = (3.9 , 5.1)

a) The distance matrix :

	A1	A2	A3	A4	A5	A6	A7
C1	0.56	0.56	3.05	6.66	4.16	4.78	3.75
C2	5.02	3.92	1.42	2.2	0.41	0.61	0.72

the euclidean distance formula is given as where is the i^th dimension of the points.

For example: The euclidean distance between C1 = (1.25, 1.5) and A1 = (1, 1) can be calculated  as ​​​​​​​

b) The new clusters are as following:

A data point gets associated with the cluster mean which is closest to it hence:

• C1 has A1 and A2 points.
• C2 has A3, A4, A5, A6 and A7 points.

c) The centers of the clusters after 2^nd epoch are:

C1 = (1.25 , 1.5)

C2 = (3.9 , 5.1)

d) After the 2^nd epoch the algorithm should stop.