Subject: Data Mining And Business Intelligence

Topic: Clustering

Difficulty: High

K-means Clustering Problem

The Given Dataset = {(20, 9), (21, 9), (15, 7), (22, 17), (20, 8), (25, 12), (26, 14), (18, 9)}

Number of Clusters = K = 3

Iteration - 1

Step 1 -

• Randomly select any 3 data points as cluster centers because the number of clusters is 3.
• Select cluster centers in such a way that they are as farther as possible from each other.
• So here we choose 3 random initial cluster centers as

$$C1 = (15, 7), C2 = (22, 17), C3 = (25, 12)$$

Step 2 -

• Calculate the distance between each data point and each cluster center.
• The distance may be calculated either by using the Distance Function or by using the Euclidean distance formula.
• Here, we calculate the distance by using the Distance Function between two points a = (x1, y1) and b = (x2, y2) as follows:

$$P(a,b)=|x2–x1|+|y2–y1|$$

Step 3 -

• Calculate the distance between each data point and each cluster center.
• A data point is assigned to that cluster whose center is nearest to that data point.

• Therefore, three clusters K1, K2, and K3 can be formed as follows:

$$ K1 = \{(20, 9), (15, 7), (20, 8), (18, 9)\} $$ $$ K2 = \{(22, 17)\} $$ $$ K3 = \{(21,9), (25, 12), (26, 14)\} $$

Step 4 -

• Re-compute the center of newly formed clusters.
• The center of a cluster is computed by taking the mean of all the data points contained in that cluster.

1] Center for Cluster-1 (K1) -

$$ X = \frac {(20 + 15 + 20 + 18)}{4} = 18.25 $$

$$ Y = \frac {(9 + 7 + 8 + 9)}{4} = 8.25 $$

Therefore, new Clsuter Center C1 = (18.25, 8.25)

2] Center for Cluster-2 (K2) -

Cluster-2 (K2) has only 1 data point.

Therefore, new Clsuter Center C2 = (22, 17)

3] Center for Cluster-3 (K3) -

$$ X = \frac {(21 + 25 + 26)}{3} = 24 $$

$$ Y = \frac {(9 + 12 + 14)}{3} = 11.67 $$

Therefore, new Clsuter Center C3 = (24, 11.67)

This is the completion of Iteration 1.

Iteration - 2

Again Repeat steps 3 and 4 same as performed in Iteration - 1.

Therefore,

• Therefore, three clusters K1, K2, and K3 can be formed as follows:

$$ K1 = \{(20, 9), (15, 7), (20, 8), (18, 9), (21,9)\} $$ $$ K2 = \{(22, 17)\} $$ $$ K3 = \{(25, 12), (26, 14)\} $$

• Re-compute the center of newly formed clusters.
• The center of a cluster is computed by taking the mean of all the data points contained in that cluster.

1] Center for Cluster-1 (K1) -

$$ X = \frac {(20 + 15 + 20 + 18 + 21)}{5} = 18.8 $$

$$ Y = \frac {(9 + 7 + 8 + 9 + 9)}{5} = 8.4 $$

Therefore, new Clsuter Center C1 = (18.8, 8.4)

2] Center for Cluster-2 (K2) -

Cluster-2 (K2) has only 1 data point.

Therefore, new Clsuter Center C2 = (22, 17)

3] Center for Cluster-3 (K3) -

$$ X = \frac {(25 + 26)}{2} = 25.5 $$

$$ Y = \frac {(12 + 14)}{2} = 13 $$

Therefore, new Clsuter Center C3 = (25.5, 13)

This is the completion of Iteration 2.

Iteration - 3

Again Repeat steps 3 and 4 same as performed in Iteration - 1.

Therefore,

• Therefore, three clusters K1, K2, and K3 can be formed as follows:

$$ K1 = \{(20, 9), (15, 7), (20, 8), (18, 9), (21,9)\} $$ $$ K2 = \{(22, 17)\} $$ $$ K3 = \{(25, 12), (26, 14)\} $$

• Re-compute the center of newly formed clusters.
• The center of a cluster is computed by taking the mean of all the data points contained in that cluster.

1] Center for Cluster-1 (K1) -

$$ X = \frac {(20 + 15 + 20 + 18 + 21)}{5} = 18.8 $$

$$ Y = \frac {(9 + 7 + 8 + 9 + 9)}{5} = 8.4 $$

Therefore, new Clsuter Center C1 = (18.8, 8.4)

2] Center for Cluster-2 (K2) -

Cluster-2 (K2) has only 1 data point.

Therefore, new Clsuter Center C2 = (22, 17)

3] Center for Cluster-3 (K3) -

$$ X = \frac {(25 + 26)}{2} = 25.5 $$

$$ Y = \frac {(12 + 14)}{2} = 13 $$

Therefore, new Clsuter Center C3 = (25.5, 13)

This is the completion of Iteration 3.

• Here we stopped after the 3 - Iterations because

  • The Center of newly formed clusters does not change
  • Data points remain present in the same clusters.

• After 3 - Iterations we get the 3 - Clusters with their Center Points are as follows:

$$ K1 = \{(20, 9), (15, 7), (20, 8), (18, 9), (21,9)\}\ with\ Center\ C1 = (18.8, 8.4) $$ $$ K2 = \{(22, 17)\}\ with\ Center\ C2 = (22, 17) $$ $$ K3 = \{(25, 12), (26, 14)\} \ with\ Center\ C3 = (25.5, 13) $$

Important Point -

• Here, we see Cluster K2 holds only one data point.
• Such, 1 data point clusters occur quite frequently in k-means because of dirty data.
• That indicates K-means is highly sensitive to noise.
• K-means minimizes squared errors by assigning outlier points to their own cluster and gives "optimal" results for the squared errors objective.
• So this is often the correct result.
• This makes k-means sensitive to the noises.