Abstract
Standard semi-supervised clustering typically assumes that at least one labeled example is available for every category. However, in real-world scenarios, prior knowledge is often incomplete, leaving some categories entirely unseeded. This paper introduces two novel algorithms, Farthest-Seeded-KMeans (FS-KMeans) and Splitting-Seeded-KMeans (SS-KMeans), designed to handle incomplete seeding by intelligently estimating initial centers for unknown categories. Experimental results on text datasets demonstrate that SS-KMeans significantly outperforms existing methods, maintaining high performance even as the number of unseeded categories increases.
Introduction
Clustering is a fundamental task in machine learning, aimed at grouping unlabeled data points based on inherent similarities. Semi-supervised clustering enhances this process by incorporating a small amount of prior knowledge, typically in the form of "seeds"—a few labeled examples for each category. While this approach has proven effective, most existing algorithms, such as Seeded-KMeans, operate under the assumption of "complete seeding." They require at least one labeled object for every cluster to initialize the process effectively.
In practical applications, this assumption is often violated. Researchers may only have information about a subset of categories, while others remain entirely "unseeded." When faced with these missing categories, standard algorithms often produce unstable or inaccurate partitions because they lack a proper starting point for the unknown groups. This paper addresses this gap by proposing two new variants of the KMeans algorithm: FS-KMeans and SS-KMeans.
Proposed Methods
The authors propose two strategies to bridge the gap between labeled and unlabeled categories by intelligently initializing centroids for unseeded clusters.
Farthest-Seeded-KMeans (FS-KMeans)
FS-KMeans is based on the heuristic that "missing" clusters are likely located in regions of the data space furthest from the known, seeded clusters. The algorithm first initializes centroids for labeled classes using the provided seeds. For the remaining $K-L$ clusters (where $K$ is the total number of clusters and $L$ is the number of seeded categories), it iteratively selects the data point furthest from any existing cluster center to serve as a new starting centroid.
Splitting-Seeded-KMeans (SS-KMeans)
SS-KMeans operates on the logic that a large, high-variance cluster likely contains multiple sub-categories. The process involves three main phases:
- Initial Clustering: Perform KMeans only on the $L$ known categories using the provided seeds.
- Splitting Step: Identify the cluster with the largest Sum of Squared Errors (SSE) and split it into two using a local KMeans ($K=2$). This process repeats until the total desired number of clusters ($K$) is reached.
- Refining Step: Run standard KMeans on the entire dataset using the $K$ centroids generated in the previous steps as initialization. This final pass fine-tunes the results and allows the algorithm to recover from potential errors during the splitting phase.
Experimental Setup
The proposed algorithms were evaluated using high-dimensional text datasets derived from the CMU 20-Newsgroups corpus. The researchers varied the "seed fraction" (the proportion of labeled points) and specifically tested the "incomplete seeding" scenario. In these tests, the number of unseeded categories was increased from 0 (complete seeding) to 5 (five categories with no seeds). Performance was measured using Mutual Information (MI), where higher values indicate better alignment with the ground truth labels.
Results and Discussion
The experimental results, summarized in Figure 1, highlight the superior performance and robustness of the proposed methods, particularly SS-KMeans.
As shown in the table, SS-KMeans consistently outperformed all other methods. Notably, even when 5 categories were entirely unseeded, SS-KMeans achieved an MI score of 0.579, which is nearly as high as the performance of standard Seeded-KMeans with complete information (0.588).
Several key insights emerged from the analysis:
- Outlier Sensitivity: While FS-KMeans is intuitive, it is sensitive to outliers. Because it selects the absolute farthest point for initialization, a single noisy data point can lead the algorithm to place a cluster center in a "ghost" region.
- The Power of Refinement: SS-KMeans proved more robust due to its refinement step. By treating the split clusters as a global initialization and then running a final KMeans pass, it consistently finds better local minima for the objective function.
- Stability in Ignorance: SS-KMeans maintains high performance even as the number of unknown categories increases, whereas the performance of standard Seeded-KMeans decays rapidly under incomplete seeding.
Conclusion
This paper demonstrates that the assumption of complete seeding in semi-supervised clustering is a significant limitation that can be overcome with intelligent initialization strategies. SS-KMeans, with its iterative splitting and refinement approach, provides a robust solution for scenarios where prior knowledge is incomplete. Future work could explore alternative heuristics for picking initial centers in FS-KMeans or investigate the computational scalability of the SS-KMeans hierarchical approach on massive-scale datasets.
Summary updated