Cluster Analysis: Basic and Advanced Methods

Cluster Analysis: Basic and Advanced Methods

Overview

Exam: ★★★★☆

Cluster analysis groups unlabeled objects so that within-cluster similarity is high and between-cluster similarity is low. The central difficulty is that a “cluster” is not unique: the same data may admit several meaningful resolutions and several notions of structure. This chapter therefore progresses from cluster definitions to prototype-based K-means, hierarchical linkage, density-based DBSCAN, fuzzy/probabilistic/subspace/graph extensions, and finally cluster validation.

Cluster Structure and Problem Formulation

Exam: ★★★★☆

A partitional clustering divides objects into non-overlapping subsets; a hierarchical clustering produces nested clusters represented by a dendrogram. Exclusive clustering assigns one cluster per point, while non-exclusive clustering allows multiple memberships. Fuzzy clustering uses with . Complete clustering assigns every object; partial clustering may leave noise unassigned.

The lecture uses five cluster notions:

• Well-separated: every point is closer to every point in its own cluster than to any outside point.
• Prototype-based: assignment is determined by closeness to a representative/centroid.
• Connectivity-based: points are joined through chains of nearby neighbors.
• Density-based: dense regions are separated by low-density regions.
• Objective/model-based: clusters optimize a criterion or fit a parameterized statistical model.

Thus dimensionality, sparsity, attribute type and scale, distribution, autocorrelation, noise/outliers, and differences in cluster size, density, shape, and separation directly affect which method is appropriate.

K-means and Prototype-Based Extensions

Exam: ★★★★★

K-means is a complete, exclusive, partitional method requiring . With Euclidean distance it minimizes

where is the centroid of . Starting from centers, repeatedly assign every point to its nearest center and update . Each step cannot increase SSE, but convergence is only to a local optimum/fixed point.

Initialization matters. If equally sized true clusters each contain points, the probability that independently sampled initial centers contain exactly one point from each cluster is

For , . K-means++ chooses later centers with probability proportional to squared distance from the nearest chosen center and has an expected approximation guarantee. Bisecting K-means repeatedly applies 2-means to split clusters and is less exposed to one global initialization.

K-means prefers compact, roughly globular clusters and can fail for differing sizes/densities, non-globular shapes, and outliers. Over-clustering into small pieces followed by merging is one workaround.

Fuzzy c-means

Hard K-means can use :

Simply relaxing to still yields hard assignments because the objective is linear in . Fuzzy c-means introduces :

The updates are

Larger produces softer memberships.

Mixture models and EM

Mixture clustering models

For Gaussian mixtures, EM alternates responsibilities

with parameter updates. Let :

EM resembles K-means in alternating assignment/update structure and initialization sensitivity, but posterior probabilities give soft membership and full covariance Gaussians can model elliptical clusters. Full covariance requires parameters per component; EM may converge slowly and only guarantees a local optimum.

Hierarchical Clustering and Linkage

Exam: ★★★★★

Agglomerative clustering starts from singleton clusters and repeatedly merges the closest pair; divisive clustering starts from one cluster and splits. A dendrogram records this sequence and can be cut at different heights.

For clusters ,

Single link (MIN) follows connectivity and handles non-elliptical shapes, but noisy bridges cause chaining. Complete link (MAX) is less susceptible to chaining but favors compact clusters and can break large clusters. Group average is a compromise but remains biased toward globular structure.

Ward’s method chooses the merge with smallest increase in SSE:

It is a hierarchical analogue of K-means. Traditional proximity-matrix implementations require space; straightforward implementations can require time, although better algorithms reduce this. Agglomerative merges are irreversible.

Density-Based and Subspace Clustering

Exam: ★★★★★

DBSCAN uses radius and minimum count . Define . A core point has , counting itself; a border point is non-core but lies near a core point; all others are noise. Connected core points form cluster backbones and border points attach to neighboring core clusters.

DBSCAN handles irregular shapes and noise and determines the number of clusters from density connectivity. It performs poorly with strongly varying densities and in high dimensions. A sorted -distance plot can suggest : the knee separates dense points from sparse/noise points.

Grid-based clustering discretizes space into cells, computes cell density, removes low-density cells, and joins adjacent dense cells. CLIQUE extends this to subspace clustering: clusters may exist only on subsets of attributes. It partitions candidate subspaces into equal-volume units, marks units dense above threshold , and joins contiguous dense units. An Apriori-like monotonicity rule prunes superspaces when lower-dimensional units are not dense. CLIQUE can find overlapping subspace clusters, but worst-case search is exponential and fixed density/grid parameters are difficult when cluster densities differ.

Graph-Based Adaptive Clustering: Chameleon

Exam: ★★★★☆

Graph-based clustering represents points as vertices with proximity-weighted edges. Sparsification keeps strong/local edges, usually nearest-neighbor links, reducing computation and weakening noisy long-range connections.

Chameleon addresses the static nature of MIN and group-average merging. It first constructs a sparse -NN graph, partitions it into many relatively pure, well-connected subclusters, then agglomeratively merges them using relative interconnectivity (RI) and relative closeness (RC).

If is total cross-edge weight and are internal cut connectivities,

RI near means cross-connectivity is comparable to internal connectivity. With average edge weights and sizes ,

RC near means cross-cluster closeness resembles internal closeness. This normalization lets merging adapt to the scale, density, and connectivity of candidate clusters, preserving self-similarity rather than applying one absolute linkage rule.

Clustering Evaluation

Exam: ★★★★★

Clustering algorithms can find apparent structure even in random data, so validation is essential. Internal indices use only the data and clustering; external indices compare cluster labels with supplied class labels.

For centroid-based clustering,

measures cohesion and

measures separation, where is the global mean. For fixed data,

The lecture example has total : one cluster gives SSE , SSB ; clusters and give SSE , SSB .

Calinski–Harabasz is

with larger values preferred.

For point , let be average distance to its own cluster and the minimum average distance to another cluster. The silhouette coefficient is

It lies in : near is good, near indicates a boundary, and negative values suggest possible misassignment.

An ideal similarity matrix contains for same-cluster pairs and otherwise. Correlation with a proximity matrix assesses agreement between labels and pairwise geometry. Only off-diagonal pairs are distinct. If proximity is a distance, a good clustering gives a large-magnitude negative correlation; for similarity it gives a positive one. This criterion is less suitable for some density/connectivity clusters. Reordering the proximity matrix by cluster label provides a visual block-structure check.

SSE can estimate using the elbow/change-point heuristic: choose a point after which additional clusters produce much smaller reductions in SSE.

With external classes, for cluster define . Its entropy and purity are

Overall scores are size-weighted:

Lower entropy and higher purity mean stronger agreement with external labels, but these labels are evaluation information, not training labels.

Finally, any validity score needs a reference scale. The lecture proposes comparing the observed index with its distribution under random data: an unusually good SSE or correlation relative to randomized data is evidence that the clustering reflects genuine structure rather than an algorithm imposing patterns on noise.

Choosing an Algorithm

Exam: ★★★★☆

The final choice should jointly consider clustering type (flat versus taxonomy), cluster concept (prototype, connectivity, density, model, subspace), expected shape/size/density/separation, attribute types and scales, dimensionality, noise/outliers, data size, determinism/order dependence, scalability, and parameter burden.

K-means is simple and efficient when centroids and compact clusters are meaningful. DBSCAN is preferable for irregular shapes and noise when a global density scale is meaningful. Single-link hierarchy captures connectivity but chains through noise. Gaussian mixtures add probabilistic memberships and covariance structure at higher statistical/computational cost. CLIQUE targets subspace clusters. Chameleon is designed for complex graph structure with varying internal characteristics.