A Genetic XK-Means Algorithm with Empty Cluster Reassignment

Chao Zhang, Chun Hua, Feng Li, Chao Zhang 0017, Jie Yang, Wei WuSymmetry 2019 · DOI

TL;DR

This paper introduces GEXK-Means, a novel clustering algorithm that enhances the XK-Means method by incorporating an empty cluster reassignment strategy and a genetic algorithm. GEXK-Means aims to overcome the limitations of traditional K-Means, such as falling into local optima and sensitivity to initial conditions, while also addressing the issue of empty clusters that can arise in XK-Means.

What Problem Does This Paper Address?

Clustering algorithms, like K-Means, are fundamental for unsupervised data analysis. However, K-Means suffers from two major drawbacks: it can easily get stuck in local optima, and its performance is highly dependent on the initial placement of cluster centers. While XK-Means was proposed to mitigate these issues by introducing an "exploratory disturbance" to cluster centers, it can lead to the formation of empty clusters. These empty clusters reduce the algorithm's efficiency and violate the assumption of having a fixed number of clusters. This paper tackles the problem of empty clusters in XK-Means and proposes a more robust and globally convergent clustering solution by combining an empty cluster reassignment technique with a genetic algorithm.

Methods

The paper introduces two main algorithmic enhancements:

  • EXK-Means (Empty-cluster-reassignment K-Means): This method builds upon XK-Means by adding a specific procedure to handle empty clusters. When an empty cluster is detected after an XK-Means iteration, EXK-Means reassigns the most marginal points from non-empty clusters to form new centers for the empty clusters. This ensures that the desired number of clusters is maintained and improves clustering efficiency.
  • GEXK-Means (Genetic EXK-Means): This is the core contribution. It combines the EXK-Means algorithm with a genetic mechanism. The genetic algorithm operates on "label vectors" representing cluster assignments. Key genetic operations include:
  • Initialization: A population of label vectors is initialized, designed to avoid empty clusters from the start.
  • Selection: A roulette wheel strategy is used to select individuals for reproduction based on their fitness (inversely proportional to MSE).
  • Mutation: A probabilistic mutation operator is applied to introduce variations, with a specific formula to calculate the probability of a gene being reassigned to a different cluster. This mutation is designed to avoid creating empty clusters.
  • EXK-Means Operation: The EXK-Means algorithm is applied as a "local search" step within the genetic algorithm to refine individuals.
  • Super Individual: The best individual found so far is maintained throughout generations, ensuring that the global optimum, once found, is preserved.

The paper also theoretically proves the probabilistic global convergence of GEXK-Means.

Datasets

The algorithms were evaluated on thirteen real-world datasets:

  • Gene Expression Datasets: Sporulation, Yeast Cell Cycle, Lymphoma, Yeast, and Ecoli.
  • Other UCI Datasets: Dermatology, Glass Identification, Image Segmentation, Wine Quality, Wireless Indoor Localization, Statlog (Vehicle Silhouettes), Page Blocks Classification, and Wine.

These datasets vary in size, number of attributes, and the presence of missing values. For datasets with missing values, a KNN imputation strategy was employed.

Key Insights and Ideas

  • Empty Clusters are Problematic: The paper clearly demonstrates that while XK-Means attempts to escape local optima, the resulting empty clusters are a significant drawback that hinders efficiency and violates core clustering assumptions.
  • Empty Cluster Reassignment Works: The proposed EXK-Means method effectively addresses the empty cluster issue, showing improved performance over XK-Means.
  • Genetic Algorithms Enhance Global Search: Combining EXK-Means with a genetic algorithm (GEXK-Means) further improves clustering accuracy and provides a theoretical guarantee of global convergence.
  • Trade-off Between Speed and Accuracy: While GEXK-Means offers superior accuracy, it comes at the cost of increased computational time compared to simpler algorithms like K-Means and XK-Means.

Key Results

  • GEXK-Means Superiority: Across all thirteen datasets and four evaluation metrics (MSE, S, DB, XB), GEXK-Means consistently achieved the best or near-best results, outperforming K-Means, XK-Means, EXK-Means, and GXK-Means.
  • EXK-Means Improvement: EXK-Means showed a noticeable improvement over XK-Means, demonstrating the effectiveness of the empty cluster reassignment technique.
  • Statistical Significance: The Nemenyi test indicated that GEXK-Means showed a significant difference compared to GXK-Means for all evaluated metrics. EXK-Means also showed a significant difference from XK-Means for the DB index.
  • Computational Cost: EXK-Means and GEXK-Means were computationally more expensive than K-Means and XK-Means, respectively. For instance, on the Yeast Cell Cycle dataset, GEXK-Means took approximately 5432 seconds, while K-Means took about 58 seconds.

Limitations and Future Work

  • Computational Time: The primary limitation acknowledged is the increased computational time of GEXK-Means. While the authors suggest this might be acceptable for non-massive datasets where accuracy is paramount, it remains a practical concern.
  • Theoretical vs. Practical Convergence: The paper proves theoretical global convergence with probability 1 over an infinite number of iterations. However, it notes that this does not guarantee reaching a global optimum within a finite number of iterations in practice.
  • Future Work: The paper implicitly suggests that further optimizations to reduce computational time while maintaining accuracy would be valuable. Exploring different genetic operators or hybridizing with other optimization techniques could be future research directions.

Summary updated

BibTeX
@article{zhang2019genetic,
  author = {Chao Zhang and Chun Hua and Feng Li and Chao Zhang and Jie Yang and Wei Wu},
  title = {{A Genetic XK-Means Algorithm with Empty Cluster Reassignment}},
  journal = {Symmetry},
  year = {2019},
  doi = {10.3390/sym11060744},
}
Figure