A Categorization of Major Clustering Methods

1. What is Cluster Analysis?

Clustering partitions a set of data objects into groups (clusters) so that objects within a cluster are similar to one another and dissimilar to objects in other clusters. It is unsupervised learning — no class labels are used.

D=\{o_1,\dots,o_n\} \longrightarrow \{C_1,\dots,C_k\},\qquad C_i \cap C_j = \emptyset,\ \ \bigcup_i C_i = D

Typical requirements: scalability, ability to deal with different attribute types, arbitrary-shaped clusters, domain knowledge (constraints), noise and outlier handling, insensitivity to input order, high dimensionality, and interpretability.

2. Clustering vs Classification

Aspect	Clustering	Classification
Supervision	Unsupervised — no labels	Supervised — labelled training data
Output	Groups discovered	Predicted class of a new object
Classes	Unknown, named after analysis	Predefined
Example	Segment customers by behaviour	Predict whether a customer will default

3. Categorization of Major Clustering Methods

                       MAJOR CLUSTERING METHODS
 ┌───────────────┬────────────────┬────────────────┬─────────────────┐
 │ PARTITIONING  │  HIERARCHICAL  │  DENSITY-BASED │  GRID-BASED     │
 │ k-means,      │  agglomerative,│  DBSCAN,       │  STING, CLIQUE, │
 │ k-medoids,    │  divisive,     │  OPTICS,       │  WaveCluster    │
 │ CLARANS, PAM  │  BIRCH, Chameleon, CURE, ROCK | DENCLUE        │
 └───────────────┴────────────────┴────────────────┴─────────────────┘
 ┌────────────────────────────┬──────────────────────┬───────────────┐
 │ MODEL-BASED                │ CONSTRAINED /        │ SOFT /        │
 │ EM (GMM), SOM, COBWEB,     │ SEMI-SUPERVISED      │ FUZZY         │
 │ statistical & neural       │ COP-KMeans,          │ Fuzzy c-means,│
 │ methods                    │ constrained DBSCAN   │ rough sets    │
 └────────────────────────────┴──────────────────────┴───────────────┘

#	Category	Principle	Representatives	Finds
1	Partitioning	Partition $n$ objects into $k$ clusters optimising an objective (e.g. minimise sum of squared errors); each cluster has a representative	k-means, k-medoids/PAM, CLARA, CLARANS	Convex / spherical clusters, needs $k$
2	Hierarchical	Build a dendrogram by agglomerating (bottom-up) or dividing (top-down)	AGNES, DIANA, BIRCH, CURE, ROCK, Chameleon	Nested clusterings, no $k$ needed
3	Density-based	Grow clusters from dense regions; clusters = connected dense areas separated by low-density regions	DBSCAN, OPTICS, DENCLUE	Arbitrary shapes + noise
4	Grid-based	Quantise space into a finite number of cells and cluster on the grid (cell statistics)	STING, WaveCluster, CLIQUE	Fast, multi-resolution, high-dim (CLIQUE)
5	Model-based	Assume data fits a model; clusters = mixture components / learned model	EM with Gaussian mixtures, COBWEB (concept tree), SOM, AutoClass	Probabilistic/soft assignments
6	Constrained	Clustering must satisfy user/business constraints (must-link, cannot-link)	COP-KMeans, constrained DBSCAN	Domain-fitting clusters
7	Fuzzy / soft	Each object may belong to several clusters with degrees of membership $\mu_{ij}\in[0,1]$ with $\sum_j \mu_{ij}=1$	Fuzzy c-means, rough k-means	Overlapping clusters

4. Taxonomy by the Shape of Clusters Found

  (a) well-separated        (b) centre-based        (c) contiguous
      ○○○    △△△               ○○○   △△△            ○○○
     ○○○○○  △△△△△             ○○○○  △△△△          ○○○○○○○
                                                            △△△
  (d) density-based         (e) conceptual / shared property / graph
      ○○○○  ○○○○                nodes linked by similar attributes

Cluster type	Definition	Best methods
Well-separated	Any point in a cluster is closer to every point in its own cluster than to any point outside	k-means, k-medoids
Centre-based (prototype)	Point nearer to its own centre than to another	k-means, k-medoids
Contiguous (nearest-neighbour)	A point is closer to one or more points of its cluster than to any outside point	Hierarchical (single link)
Density-based	Dense region of points separated by sparse regions	DBSCAN, DENCLUE
Conceptual / shared-property	Points share a common property or fit a common model	COBWEB, conceptual clustering

5. Measures of Clustering Quality

Internal (no ground truth):

SSE (sum of squared errors) / cohesion: $\text{SSE}=\sum_{i=1}^{k}\sum_{p\in C_i}(p - m_i)^2$ — used by k-means.
Silhouette coefficient for point $i$ : $s(i)=\dfrac{b(i)-a(i)}{\max\{a(i),b(i)\}}$ , where $a$ = mean intra-cluster distance, $b$ = mean nearest-cluster distance; $s\in[-1,1]$ , higher is better.
Davies–Bouldin index (lower better), Dunn index (higher better), Calinski–Harabasz.

External (labels known): purity, entropy, precision/recall, Rand index, Adjusted Rand Index (ARI), F-measure, Jaccard, Normalised Mutual Information.

\text{Rand index}=\frac{a+b}{\binom{n}{2}},\qquad \text{ARI}=\frac{\text{RI}-E[\text{RI}]}{\max \text{RI}-E[\text{RI}]}

where $a$ = pairs together in both partitions, $b$ = pairs apart in both.

6. Choosing a Method

Requirement	Suitable methods
Big data, numeric, need speed, $k$ known	k-means / CLARANS
Arbitrary shapes with noise	DBSCAN / OPTICS
No idea of $k$ , need a hierarchy	AGNES / DIANA / BIRCH
Very high dimensional (text)	CLIQUE / subspace clustering / ROCK, cosine k-means
Need membership probabilities	EM (mixture models)
Business rules must hold	Constrained clustering
Objects in multiple clusters	Fuzzy c-means

7. Exam Points

Enumerate and explain the major categories of clustering methods with one algorithm example each — 10 marks (very frequent).
Explain well-separated/centre-based/contiguous/density/conceptual cluster types with sketches — 5-7 marks.
Distinguish clustering from classification — 3 marks.
State clustering requirements (scalability, arbitrary shape, noise, input order, high dimension) — 5 marks.
Write short notes on measures of clustering quality (SSE, silhouette, Rand index) — 5 marks.

A Categorization of Major Clustering Methods