Enhancing semi-supervised clustering: a feature projection perspective

Wei Tang, Hui Xiong, Shi Zhong, Jie WuKDD 2007 · DOI

TL;DR

This paper introduces SCREEN, a novel semi-supervised clustering method that tackles the challenge of clustering high-dimensional, sparse data. SCREEN enhances traditional clustering by incorporating pairwise instance constraints (must-link and cannot-link) through a constraint-guided feature projection technique, leading to improved clustering performance and efficiency.

What Problem Does This Paper Address?

Clustering algorithms aim to group similar data points together. Semi-supervised clustering leverages limited human guidance, such as knowing that two points must be in the same cluster (must-link) or must not be in the same cluster (cannot-link), to improve accuracy over unsupervised methods. However, many existing semi-supervised clustering techniques struggle with high-dimensional, sparse data (like text documents). This is because traditional notions of distance and density become less meaningful in such datasets, and many methods are computationally too expensive. The paper addresses this gap by proposing a method that effectively reduces dimensionality while preserving the crucial information from pairwise constraints.

Methods

The core of the SCREEN method lies in its two main components:

  • Constraint-Guided Feature Projection (SCREENPROJ): This is the novel contribution. Instead of directly learning a distance metric, SCREENPROJ learns a projection matrix that maps the high-dimensional data into a lower-dimensional space. The projection is guided by the pairwise constraints, aiming to maximize the distance between instances that cannot be linked and minimize the distance between instances that must be linked. This is formulated as an optimization problem with an analytical solution derived from eigenvectors of a covariance matrix.
  • Constrained Spherical K-means: After dimensionality reduction, a modified spherical K-means algorithm is applied to the projected data. This algorithm is adapted to handle the cannot-link constraints by using a local greedy heuristic to update cluster centroids, ensuring that cannot-link pairs are not assigned to the same cluster. The must-link constraints are handled during an initialization phase by creating representative "average" instances.

Datasets

The authors evaluated their method on a variety of datasets:

  • UCI Datasets: Six relatively low-dimensional datasets (balance-scale, ionosphere, iris, soybean, vehicle, wine) were used to compare SCREENPROJ with PCA and RCA.
  • TREC Datasets: Six high-dimensional datasets (tr11, tr12, tr23, tr31, tr41, tr45) were used to compare SCREENPROJ with PCA and RCA on challenging data.
  • 20-Newsgroup Corpus: Nine datasets derived from this corpus, known for its high dimensionality and sparsity (common in text data), were used to compare the overall SCREEN method against other state-of-the-art semi-supervised clustering algorithms.

Key Insights and Ideas

  • Feature Projection over Metric Learning for High Dimensions: The paper argues that for high-dimensional, sparse data, learning an adaptive distance metric (as in some prior work) is computationally expensive and less effective than projecting the data into a lower-dimensional space guided by constraints.
  • Cannot-Link Constraints are Crucial: Experiments reveal that cannot-link constraints are significantly more important than must-link constraints for guiding the feature projection and achieving good clustering performance.
  • Optimal Dimensionality is Dataset-Dependent: The ideal reduced dimensionality (k) for SCREEN is not fixed but varies across datasets, with median values often falling between 20 and 40 for good performance.
  • SCREEN Balances Performance and Efficiency: SCREEN achieves competitive or superior clustering performance compared to other methods while being more computationally efficient than some metric-learning-based approaches.

Key Results

  • SCREEN consistently outperforms or matches PCA and RCA in clustering performance on both low-dimensional UCI and high-dimensional TREC datasets, especially as the number of constraints increases.
  • On the 20-Newsgroup datasets, SCREEN demonstrates better clustering performance (higher NMI) than SPKM, PCSKM, and PCSKM+M, particularly with a larger number of constraints.
  • SCREEN is computationally more efficient than PCSKM+M (a metric learning approach) and only slightly slower than PCSKM (which doesn't do feature projection), making it a good trade-off for high-dimensional data.
  • The analysis of constraint impact shows that using only must-link constraints leads to a sharp drop in performance, highlighting the importance of cannot-link constraints.

Limitations and Future Work

  • Determining Optimal Dimensionality: The paper acknowledges that the optimal reduced dimensionality k is dataset-dependent and currently requires empirical evaluation. Future work could involve automatically identifying this optimal k.
  • Supervised Feature Clustering: The authors suggest exploring alternative methods to employ supervision, such as supervised feature clustering.
  • Handling Noisy Constraints: While the paper mentions that their algorithm allows some relaxation of pairwise constraints, a more robust handling of potentially mis-specified or noisy constraints could be a future direction.

Summary updated

BibTeX
@inproceedings{tang2007enhancing,
  author = {Wei Tang and Hui Xiong and Shi Zhong and Jie Wu},
  title = {{Enhancing semi-supervised clustering: a feature projection perspective}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2007},
  doi = {10.1145/1281192.1281268},
}
Figure