A Bibliographic View on Constrained Clustering

Ludmila Kuncheva, Francis Williams, Samuel HennesseyarXiv 2022 · OpenReview

TL;DR

This paper offers a comprehensive bibliographic review of constrained clustering, analyzing trends, topics, and available software. It highlights a notable lack of large-scale comparative studies and suggests that application-oriented research, deep learning, and active learning are driving the field's future.

What Problem Does This Paper Address?

Constrained clustering is a subfield of semi-supervised machine learning that aims to improve clustering results by incorporating prior knowledge in the form of constraints. These constraints can be "must-link" (items must be in the same cluster) or "cannot-link" (items must be in different clusters). While the field has seen significant research, there's a need for a systematic overview of its landscape, trends, and experimental practices. This paper addresses this by providing a bibliographic analysis of the constrained clustering literature, identifying key themes, popular methods, and areas for future development.

Methods

The authors conducted a systematic keyword search on Web-of-Science to identify relevant publications. They then compiled a bibliography of 183 papers for detailed analysis. Their methodology involved:

  • Bibliometric Analysis: Examining publication trends over time, using citation counts and publication years to identify influential papers and research directions.
  • Pareto Analysis: Plotting papers based on publication year and citation count to identify "Pareto fronts" representing highly influential works. This was done both for the entire collection and for ten identified sub-topics.
  • Topic Taxonomy: Developing a rough, non-mutually exclusive grouping of research topics within constrained clustering.
  • Software Cataloging: Compiling a list of available software implementations for constrained clustering.
  • Experimental Study Analysis: Reviewing the experimental sections of the collected papers to understand common datasets, algorithms, and evaluation metrics.

Datasets

The paper identifies a total of 245 datasets used in the experimental studies analyzed. However, it notes a significant deficiency in comparative studies, with 179 datasets being used only once. The four most commonly used datasets, appearing more than six times, are:

  • Iris
  • Wine
  • Glass
  • Ionosphere

These datasets are all from the UCI Machine Learning Repository. The paper also highlights that only a few works use more than 10 datasets, further emphasizing the lack of large-scale comparisons.

Key Insights and Ideas

  • Dominance of K-Means: K-means remains the undisputed leader in constrained clustering algorithms, with "pairwise" and "spectral" also being highly prevalent keywords.
  • Emerging Trends: "Deep learning" and "active learning" are increasingly prominent, suggesting a shift towards more advanced methodologies.
  • Application-Oriented Focus: Recent Pareto front analyses show a strong trend towards application-driven research, indicating that practical use cases are becoming a major driver of the field.
  • Lack of Large-Scale Comparisons: A significant finding is the scarcity of studies that conduct extensive experimental comparisons between different constrained clustering methods, hindering direct evaluation and progress.
  • Software Availability is Key: The authors emphasize that sharing software is crucial for unifying approaches and facilitating comparisons, which is seen as the way forward.
  • External Labels for Evaluation: The prevalence of evaluation metrics that rely on external labeled datasets suggests a common, though potentially "fundamentally flawed," approach to assessing clustering quality.

Key Results

  • Publication Trends: The overall number of publications on constrained clustering is rising, but when scaled against "machine learning" publications, interest appears to decline from 2016, possibly due to the deep learning boom. However, when scaled against "clustering" alone, a steady upward trend is observed.
  • Top Research Areas: Computer Science is the dominant research area, followed by Engineering, Telecommunications, and Mathematics.
  • Software Landscape: A table lists various available software packages for constrained clustering, indicating a growing ecosystem of tools.
  • Experimental Study Deficiencies: The analysis of experimental studies revealed a lack of large comparative studies, with a high number of datasets used only once and a limited number of papers comparing more than 10 algorithms.

Limitations and Future Work

The authors acknowledge that citation count is not a perfect metric for scientific impact but use it as a proxy. They also note that their list of available software is not exhaustive.

Future work suggested by the paper includes:

  • Encouraging Comparative Studies: The authors strongly advocate for more extensive experimental comparisons to provide a clearer understanding of method performance.
  • Promoting Software Sharing: They highlight the importance of shared software for reproducibility and comparability.
  • Observing Future Trends: The paper anticipates that "deep learning" and application-specific keywords will continue to grow in prominence, while K-means and spectral clustering might see relatively less representation in future surveys.

Summary updated

Abstract

A keyword search on constrained clustering on Web-of-Science returned just under 3,000 documents. We ran automatic analyses of those, and compiled our own bibliography of 183 papers which we analysed in more detail based on their topic and experimental study, if any. This paper presents general trends of the area and its sub-topics by Pareto analysis, using citation count and year of publication. We list available software and analyse the experimental sections of our reference collection. We found a notable lack of large comparison experiments. Among the topics we reviewed, applications studies were most abundant recently, alongside deep learning, active learning and ensemble learning.
BibTeX
@misc{kuncheva2022bibliographic,
  author = {Ludmila Kuncheva and Francis Williams and Samuel Hennessey},
  title = {{A Bibliographic View on Constrained Clustering}},
  year = {2022},
  eprint = {2209.11125},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.11125},
}
Figure