Clustering High-Dimensional Data

1. The Problem — Curse of Dimensionality

Real applications (text documents, gene expression, images, market baskets) have hundreds to thousands of dimensions. In high dimensions:

Distance concentration: for many distributions the ratio of the farthest to the nearest neighbour distance tends to 1, so "nearest" and "farthest" lose meaning.

\lim_{d\to\infty}\frac{dist_{\max}-dist_{\min}}{dist_{\min}}\to 0

Data sparsity: the data space grows as $k^{d}$ while the number of objects grows only linearly — the data become sparse and density-based notions break down.
No full-space cluster: a meaningful cluster usually exists in only a few of the dimensions (a subspace); two objects may be similar in one subspace and completely different in another.
Grid-based methods explode combinatorially ( $\#cells = k^{d}$ and $\#subspaces = 2^{d}-1$ ) and classical silhouette/elbow heuristics become unreliable.

2. Two Major Strategies

 HIGH-DIMENSIONAL CLUSTERING
   |-- (1) SUBSPACE CLUSTERING         -> find clusters in different subspaces
   |      |-- Bottom-up search   (CLIQUE, ENCLUS, MAFIA, CBF)
   |      |-- Top-down search    (PROCLUS, ORCLUS, FINDIT)
   |-- (2) DIMENSIONALITY REDUCTION   -> project/select features first
          |-- Feature transformation  (PCA, SVD, wavelet, spectral embedding)
          |-- Feature selection       (information gain, chi-square, Laplacian score)

Difference between the two:

Dimensionality reduction finds one projection and clusters in it — the same dimensions are used for all clusters.
Subspace clustering lets each cluster have its own (usually different) relevant dimensions — much more informative for high-dimensional data.

3. Subspace Clustering (Bottom-Up): CLIQUE-style

Uses the Apriori/monotonicity property: if a $k$ -dimensional unit is dense, then all its $(k-1)$ -dimensional projections are dense. Search level by level in the dimensionality of the dense units:

k = 1: find all dense 1-D units (each dimension separately)
k = 2: candidates = pairs of dimensions of dense 1-D units; verify density
k = 3: candidates must have ALL 2-D projections dense; verify
...   until no dense units in k dimensions
Merge adjacent dense units into clusters; describe each cluster as a DNF:
      (d1 in I1) AND (d2 in I2)  OR  (d1 in I3) AND (d4 in I4) ...

Advantages: automatically discovers subspaces; number of passes = highest dimensionality of a dense unit; insensitive to order and outliers. Disadvantages: density threshold and grid granularity are delicate; can produce overlapping/redundant clusters; still exponential in the dense-unit dimensionality.

4. Subspace Clustering (Top-Down): PROCLUS and ORCLUS

PROCLUS — projective clustering with k-medoids in an iterative refinement scheme:

Initialisation: take a sample, greedily choose $k$ well-separated medoids (like CLARANS), assigning each remaining point to the closest medoid.
Iterative refinement:
- Compute dimensions: for each current cluster, find the $l$ dimensions (average cluster dimensionality) whose average distance from the points to the medoid is smallest → the cluster's subspace.
- Compute medoids: for each cluster, choose new medoids based on the distances computed only in the cluster's own subspace.
- Reassign points to the closest medoid in the appropriate subspace, and drop/redistribute clusters that end up with too few points ( $< minDev$ ).
Repeat until convergence. MANIFOLD shaping further improves the search by locally adjusting the subspace dimensions of each cluster.
Parameters to set: $k$ (number of clusters), $l$ (average number of dimensions per cluster), $minDev$ .

 PROCLUS concept:  cluster 1 relevant dims = {d2, d7, d9}
                   cluster 2 relevant dims = {d1, d5}
                   cluster 3 relevant dims = {d3, d4, d8}
   (each cluster is characterised by its own projected subspace)

ORCLUS uses arbitrary (not axis-parallel) directions — it computes covariance-based eigenvectors within each cluster and chooses the subspace as the subspace spanned by the $l$ eigenvectors with the smallest eigenvalues (i.e. the directions of least spread, where the cluster is compact), making it able to find arbitrarily oriented projected clusters.

5. Dimensionality-Reduction Approaches

Method	Idea	Notes
PCA / SVD	Project onto the top- $k$ principal components capturing most variance; then cluster the projected data	Simple and effective with k-means; components are combinations of all attributes → hard to interpret; unsupervised (may discard dimensions useful for clustering)
Feature selection	Rank attributes by information gain, $\chi^2$ , variance, Laplacian score, and keep the top- $m$ ; then cluster	Interpretable (original attributes retained); assumes one common feature set
Wavelet transform	Keep the largest wavelet coefficients (see WaveCluster for grid+wavelet)	Handles spatial/skewed data
Spectral / manifold embedding	Build a similarity graph, use its top eigenvectors as embedding, then cluster	Captures non-linear manifolds; costly for huge $n$
Random projection	Multiply by a random matrix preserving distances with high probability (Johnson-Lindenstrauss)	Cheap; used for very high $d$

6. Other High-Dimensional Clustering Ideas

Frequent-pattern-based (pattern-based) clustering: mine frequent itemsets/patterns from high-dimensional categorical data, then cluster the patterns (e.g. pCluster — a pCluster is a set of objects and a set of dimensions with pairwise density ≥ threshold; the algorithm mines pClusters, decouples the clustering from the pattern-mining step and can compute clusters for many different thresholds efficiently). Example of a pCluster: age ∈ {20-35}, salary ∈ {40k-70k}, education = "degree" with density ≥ $\delta$ .
Co-clustering / bi-clustering — clusters rows and columns simultaneously (used in gene-expression analysis).
Ensemble/projection-based clustering — cluster many random low-dimensional projections and combine (e.g. ProClust, hough-based, consensus clustering).

7. Evaluation in High Dimensions

Clusters found in different subspaces are not comparable with standard full-space validity indices; use pattern-based/interpretability evaluation (coverage of the dense units, description length of the DNF, cluster density in its subspace) and MDL-based model selection.

8. Exam Points

Explain the curse of dimensionality and why conventional clustering fails in high dimensions — 5 marks.
Explain subspace clustering with CLIQUE's bottom-up search and monotonicity property — 7-10 marks.
Explain PROCLUS with its dimensions-computing and medoid step, and contrast it with ORCLUS — 7-10 marks.
Contrast subspace clustering with dimensionality reduction for clustering — 5 marks.
Short note on pCluster / pattern-based clustering — 3 marks.

Clustering High-Dimensional Data