CS3001 - Clustering

What is the first step in the K-Means Algorithm?

1. Each data point starts as its own cluster (N clusters total).

2. Find the 2 closest clusters and merge them into one.

3. Recalculate distances between the new cluster and all remaining clusters.

4. Repeat until only 1 cluster remains. Result: a DENDROGRAM (tree diagram).

Advantages of the K-Means Algorithm?

Fast and simple

Good for round (globular) clusters

Scales well to large datasets

Disadvantages of the K-Means Algorithm?

Must specify K in advance

Different random starts can give different results

Cannot handle oddly-shaped clusters

Steps in Hierarchical Clustering

1. Each data point starts as its own cluster (N clusters total).

2. Find the 2 closest clusters and merge them into one.

3. Recalculate distances between the new cluster and all remaining clusters.

4. Repeat until only 1 cluster remains. Result: a DENDROGRAM (tree diagram).

How do you determine the number of clusters from a dendrogram?

Cut the dendrogram with a horizontal line; the number of vertical lines crossed equals the number of clusters.

What does Single Linkage measure in Hierarchical Clustering?

MINIMUM — closest pair between the two clusters

Single = Smallest gap

What does Complete Linkage measure in Hierarchical Clustering?

MAXIMUM — farthest pair between the two clusters

Complete = Widest gap

What does Average Linkage measure in Hierarchical Clustering?

The mean distance of all pairs between two clusters.

Average = Middle ground

Advantages of Hierarchical Clustering

No need to choose K in advance.

Dendrogram reveals full cluster structure

Works with any cluster shape

Disadvantages of Hierarchical Clustering

It is slow on large datasets.

Early merges cannot be undone (greedy)

Different linkage methods give different results