Abstract
We present a novel pairwise clustering method. Given a proximity matrix of pairwise relations (i.e. pairwise similarity or dissimilarity estimates) between data points, our algorithm extracts the two most prominent clusters in the data set. The algorithm, which is completely nonparametric, iteratively employs a two-step transformation on the proximity matrix. The first step of the transformation represents each point by its relation to all other data points, and the second step re-estimates the pairwise distances using a statistically motivated proximity measure on these representations. Using this transformation, the algorithm iteratively partitions the data points, until it finally converges to two clusters. Although the algorithm is simple and intuitive, it generates a complex dynamics of the proximity matrices. Based on this bipartition procedure we devise a hierarchical clustering algorithm, which employs the basic bipartition algorithm in a straightforward divisive manner. The hierarchical clustering algorithm copes with the model validation problem using a general cross-validation approach, which may be combined with various hierarchical clustering methods.
Introduction
Clustering is a fundamental challenge in unsupervised learning: how do we group data points without prior labels? Most traditional methods, like k-means, require the user to specify the number of clusters ($k$) beforehand and often assume clusters have specific shapes (like spheres).
Pairwise clustering—where we only know the distances (proximities) between points rather than their raw features—is more flexible but faces two major hurdles:
- Global vs. Local Structure: Many algorithms focus on local neighbors, missing the "big picture" of the dataset.
- The Validation Problem: In hierarchical clustering, how do we know when to stop splitting? Most algorithms will keep dividing data until every point is its own cluster, leading to "meaningless" partitions.
Methodology: Iterative Distance Profile Estimation
The core of this paper is a two-step iterative transformation applied to a proximity matrix $M$. The central insight is treating a point's relationship to the entire dataset as its defining feature—a "distance profile." Two points are considered "close" not just if they are near each other, but if they "see the rest of the world" in a similar way.
- Normalization: For every point $i$, its distances to all other points are treated as a vector. This vector is normalized to represent a probability distribution.
- Re-estimation: The distance between two points $i$ and $j$ is recalculated as the Jensen-Shannon (JS) divergence between their probability distributions.
Unlike the more common Kullback-Leibler divergence, JS-divergence is symmetric, bounded, and has a clear statistical interpretation: it measures how likely it is that two samples originated from the same source.
The algorithm repeats these steps until the matrix converges to a stable, binary state (0s and 1s), effectively "sharpening" the relationships until only two distinct blocks remain. This transformation acts like a filter that gradually suppresses noise and amplifies the most prominent structural signals in the data. To find more than two clusters, the authors use a divisive hierarchical approach, recursively applying this bipartition.
To solve the validation problem, they introduce a cross-validation index ($\rho$). They split a cluster into two overlapping subsets, cluster them independently, and measure how much the results agree on the shared points. If the agreement is high (relative to a Monte-Carlo sampled "null hypothesis" of random data), the split is considered meaningful.
Experimental Evaluation
The authors evaluated the algorithm on a mix of synthetic and real-world data:
- Synthetic 2D Data: Used to test non-linear shapes (concentric rings) and robustness to three types of noise (proximity noise, data point jitter, and missing entries). The algorithm is surprisingly resilient; in experiments with missing data, results remained stable even after losing 90% of the proximity entries, provided the missing values were substituted with column averages.
- UCI Iris Dataset: The algorithm correctly classified 124 out of 150 samples, performing on par with sophisticated methods like Super-Paramagnetic clustering.
- ISOLET Speech Dataset: It effectively grouped phonetically similar letters (like the "nasal" group M and N) without any prior linguistic knowledge.
- Music Style Dataset: It successfully separated musical pieces into two main stylistic groups: "Early/Classical" and "Romantic/Impressionist," demonstrating an ability to capture abstract stylistic nuances.
Discussion and Limitations
While the algorithm is highly versatile for complex, high-dimensional data, it has some drawbacks. The primary challenge is the $O(n^3)$ time complexity per iteration, making it expensive for very large datasets. The authors suggest using random projections to bring this down to $O(n^2)$. Additionally, the algorithm has a slight bias toward creating clusters of similar sizes. If a dataset has one massive cluster and one tiny outlier cluster, the bipartition might struggle.
Future work includes exploring global normalization schemes, extending the method to ordinal data, and providing a formal mathematical proof of convergence for all proximity measures, which remains an open challenge despite strong empirical evidence.
Summary updated