Information Theoretical Clustering via Semidefinite Programming

Meihong Wang, Fei ShaAISTATS 2011 · OpenReview

Abstract

Information Theoretical Clustering (ITC) is a robust non-parametric clustering approach that maximizes mutual information between data points and cluster assignments. Despite its advantages over distance-based methods like K-means, ITC is computationally challenging due to its NP-hard combinatorial nature. This paper presents a novel framework that transforms ITC into a convex optimization problem using Semidefinite Programming (SDP). By employing a low-rank refinement heuristic, the authors demonstrate that this approach achieves superior clustering accuracy and provides a more stable alternative to traditional greedy local search methods.

Problem Statement

Traditional clustering algorithms like K-means minimize the distance between points and cluster centroids. While effective, K-means assumes spherical cluster shapes and is highly sensitive to outliers. Information Theoretical Clustering (ITC) offers a more flexible alternative by maximizing the Mutual Information (MI) between data points and their cluster assignments.

However, maximizing MI is an NP-hard combinatorial problem. Previous implementations typically relied on greedy local searches—iteratively moving single points to improve the objective function. Such methods are prone to local optima and lack theoretical guarantees regarding the global optimality of the resulting partition.

Proposed Methodology

The authors propose a multi-step pipeline to transform ITC into a robust, solvable convex optimization problem:

  1. Nonparametric Estimation: To calculate entropy in high-dimensional spaces without the "curse of dimensionality," the authors use an estimator based on pairwise distances.
  2. Graph Formulation: Minimizing conditional entropy is shown to be equivalent to a Max $k$-cut problem on a weighted graph, where the goal is to partition the graph to maximize edge weights between different clusters.
  3. SDP Relaxation: Since Max $k$-cut is NP-hard, the discrete constraints are relaxed into a Semidefinite Program (SDP). This transformation makes the problem convex, ensuring a single global optimum that can be found in polynomial time.
  4. Low-Rank Refinement: Initial SDP solutions can be "blurry," failing to define sharp cluster boundaries. The authors introduce a logdet heuristic—an iterative process that encourages the solution matrix to have a low rank equal to the number of clusters $K$.
The low-rank refinement process (b) sharpens the initial SDP solution (a) into a clear block-diagonal structure.

Experimental Evaluation

The approach was evaluated on several datasets from the UCI repository (Wine, Iris, Glass, Vehicle) and the USPS handwritten digits dataset. The results demonstrate that the proposed ITC-SDP methods consistently outperform standard K-means and greedy ITC-Local algorithms.

Comparison of clustering accuracy (RAND score) across different datasets and methods.

Notably, the SDP formulation showed significant resilience on the Glass dataset, which is characterized by highly imbalanced cluster sizes. The low-rank refinement was particularly effective; for instance, on the usps-100 dataset, it improved the RAND score from 0.877 to 0.921.

Key Insights and Discussion

  • Optimization vs. Metric: A key finding was that SDP-relaxed K-means performed similarly to SDP-relaxed ITC. This suggests that the choice of optimization (convex relaxation vs. greedy search) may be more impactful for clustering quality than the specific objective function.
  • Robustness to Outliers: By utilizing the logarithm of pairwise distances, ITC is naturally more robust to outliers compared to the linear or squared distances used in K-means.
  • Visual Clarity: The "sparsity plots" generated by the low-rank refinement produce clean, block-diagonal matrices that closely mirror ground-truth structures, as seen in the methodology section.

Limitations and Future Work

The primary bottleneck of the proposed method is computational complexity. Standard SDP solvers scale at approximately $O(N^6)$, limiting the "Exact" method to datasets of around 200 points. Additionally, while the method handles imbalanced data well in practice, the current formulation theoretically assumes balanced clusters ($N/K$ points per cluster). Future research will focus on developing specialized, faster SDP solvers and exploring approximate graph cut algorithms to scale the framework to larger datasets.

Summary updated

BibTeX
@inproceedings{wang2011information,
  author = {Meihong Wang and Fei Sha},
  title = {{Information Theoretical Clustering via Semidefinite Programming}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=5JOv4LQ9-dG},
}
Figure