Clustering via Concave Minimization

Paul S. Bradley, Olvi L. Mangasarian, W. Nick StreetNeurIPS 1996

Overview

This paper introduces a robust alternative to the classic $k$-means algorithm by formulating clustering as a concave minimization problem using the 1-norm (Manhattan distance). By treating the problem as a bilinear program, the authors developed a fast, finite "$k$-Median" algorithm that is significantly more resistant to outliers and provides better prognostic insights, particularly in medical datasets.

The Problem with $k$-Means

The "gold standard" for unsupervised clustering has long been the $k$-means algorithm. However, $k$-means relies on the 2-norm (Euclidean distance) and specifically minimizes the square of those distances. Mathematically, squaring the distance gives outliers an outsized "vote" on where the cluster centers should be, often pulling centers away from the actual data density.

The authors seek a clustering method that is:

  1. Robust: Less sensitive to noisy data and extreme outliers.
  2. Computationally Efficient: Able to handle large datasets without the overhead of complex global optimization.
  3. Mathematically Sound: Formulated within a framework that allows for clear convergence properties.

Methodology: $k$-Median and Concave Minimization

The core innovation is the shift from the 2-norm to the 1-norm (the sum of absolute differences). The authors formulate the problem as minimizing a piecewise-linear concave function over a polyhedral set.

Because minimizing concave functions is generally NP-hard, the authors use a clever mathematical "bridge":

  • Bilinear Programming: They reformulate the clustering objective into a bilinear program—a problem where the variables are split into two sets, and the function is linear if you hold one set constant.
  • The $k$-Median Algorithm: This leads to an iterative two-step process:
  • Cluster Assignment: Assign each point to the nearest center using the 1-norm.
  • Center Update: Update the cluster center by calculating the median (rather than the mean) of the points assigned to it.

Crucially, the 1-norm median has a simple closed-form solution (it is just the median of each coordinate independently), making the algorithm extremely fast and guaranteed to terminate in a finite number of steps at a stationary point.

Key Insights

  • The "Outlier" Advantage: By using the 1-norm, the algorithm effectively ignores the "pull" of extreme outliers. In $k$-means, a single point far from the center can drastically shift the mean; in $k$-median, that same point has the same influence as any other point.
  • Closed-Form Efficiency: Many robust clustering methods are computationally expensive. By showing that the $k$-median sub-problems can be solved as simple linear programs in closed form, the authors proved that robustness does not have to come at the cost of speed.
  • Prognostic Value: The paper argues that clustering isn't just about grouping similar points—it is about discovering groups that have different real-world outcomes, such as survival rates in clinical settings.

Datasets and Key Results

The authors evaluated their algorithm on several real-world databases, primarily from the UCI Machine Learning Repository, including the Wisconsin Diagnostic Breast Cancer (WDBC) dataset, the Wisconsin Prognostic Breast Cancer (WPBC) dataset, Cleveland Heart Disease, United States Congressional Votes, and Star/Galaxy-Bright.

Accuracy and Stability

On the WDBC dataset, the $k$-Median algorithm achieved a training correctness of 93.2%, outperforming $k$-means (91.1%). Furthermore, in testing set evaluations, $k$-Median's accuracy remained highly stable (92.3%–93.5%) regardless of the test set size. In contrast, $k$-means was more volatile and consistently less accurate (88.0%–91.3%).

Testing Set Correctness vs. Testing Set Size

Survival Analysis

The most striking practical result came from the WPBC database, which includes follow-up data used to predict the timing of cancer recurrence. The $k$-Median algorithm successfully separated patients into three groups with distinct, clinically significant survival curves. In contrast, the $k$-means algorithm produced overlapping curves that offered little to no value for medical prognosis.

Survival Curves for k-Median vs k-Mean

Limitations and Future Work

  • Local Optima: Like $k$-means, the $k$-Median algorithm is a local search method. It is guaranteed to find a stationary point, but not necessarily the global minimum. The final clustering can vary based on the initial starting centers.
  • Initialization Heuristics: The authors suggest using heuristics (like placing centers at the densest intervals of the axes) to mitigate the starting point issue, but more research is needed to find the optimal initialization strategy.
  • Problem Specificity: While $k$-Median outperformed $k$-means on several datasets, it was slightly less effective on others (like the Cleveland and Votes datasets). Further work is required to pinpoint exactly which underlying data distributions favor the 1-norm over the 2-norm.

Summary updated

BibTeX
@inproceedings{bradley1996clustering,
  author = {Paul S. Bradley and Olvi L. Mangasarian and W. Nick Street},
  title = {{Clustering via Concave Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
}
Figure