Need of clustering; hierarchical vs partitioning; K-means

Need for cluster analysis

Cluster analysis groups unlabelled objects so that objects in a cluster are similar and those in different clusters are dissimilar. It is needed because:

• Large data sets have no class labels; clustering discovers natural groups and the structure of the data (e.g. customer segments for marketing).
• It summarises and compresses data: each cluster can be represented by its centre.
• It is a preprocessing step for other methods and helps detect outliers (objects far from every cluster).
• Applications: image segmentation, document grouping, biology (gene groups), city planning, fraud detection.

Hierarchical vs partitioning clustering

K-means on the data (K = 2)

Assumption: K = 2, and the first two instances are the initial centroids: C1 = (1.0, 1.5) and C2 = (2.5, 5.5). Euclidean distance d = √[(x − cx)² + (y − cy)²].

Iteration 1 (centroids C1 = (1.0, 1.5), C2 = (2.5, 5.5))

Clusters: C1 = {1, 3, 4}, C2 = {2, 5, 6}. New centroids: C1 = ((1.0 + 1.5 + 2.0)/3, (1.5 + 1.0 + 3.0)/3) = (1.50, 1.83); C2 = ((2.5 + 2.5 + 4.0)/3, (5.5 + 3.5 + 6.2)/3) = (3.00, 5.07).

Iteration 2 (centroids C1 = (1.50, 1.83), C2 = (3.00, 5.07))

The assignment is unchanged, so the algorithm has converged (the centroids would stay the same).

Answer: Cluster 1 = {instances 1, 3, 4} with centroid (1.50, 1.83); Cluster 2 = {instances 2, 5, 6} with centroid (3.00, 5.07).