Improved K-means Algorithm with the Pretreatment of PCA Dimension Reduction

Hongtao Liu, Chen Fang, Yu Wu, Ke Xu, Dai TianInternational Journal of Hybrid Information Technology 2015 · DOI

Abstract

The improvements we have made are to get the optimal K value, to obtain the initial cluster centers and to calculate the distance by the feature weight. Meanwhile, to cater to the characters of dataset, the IWK-means algorithm uses the principal component analysis (PCA) method as a pretreatment to reduce the dimension of dataset. Finally, the proposed method is experimentally validated on the datasets from the UCI Machine Learning Repository and compared with the existing clustering algorithms by the two evaluation criteria of Rand Index and Adjusted Rand Index.

Introduction

K-means clustering is one of the most widely used unsupervised learning algorithms due to its simplicity and efficiency. However, it suffers from three notorious flaws: the requirement to pre-specify the number of clusters ($K$), a high sensitivity to initial centroid placement which often leads to local optima, and the "curse of dimensionality" where irrelevant features can degrade distance metrics. This paper introduces the IWK-means (Improved Weighted K-means) algorithm, which integrates Principal Component Analysis (PCA) to automate parameter selection and stabilize clustering results.

Methodology: The IWK-means Pipeline

The proposed IWK-means algorithm introduces a four-step pipeline designed to address the traditional limitations of K-means:

  1. PCA Pretreatment: The dataset is first transformed using PCA to reduce dimensionality. This step filters out noise and reduces computational complexity while retaining the most informative characteristics of the data.
  2. Automatic $K$ Selection: To eliminate the need for manual guessing, the algorithm uses a distance evaluation function $F(S, K)$ based on the ratio of intra-cluster tightness to inter-cluster separation. The optimal $K$ is found where this function is minimized.
  3. Intelligent Initialization: To avoid poor random starts, the algorithm projects data onto the two primary PCA axes. It selects the first center as the point furthest from the global mean, and subsequent centers are chosen using an accumulation scheme to ensure they are statistically likely to belong to different clusters.
  4. Feature Weighting: Not all features are equally important. IWK-means uses the "contribution degrees" (explained variance) from the PCA step as dynamic weights in the distance calculation, ensuring that the most significant components have the most influence on the clustering outcome.
Clustering results for the Iris dataset illustrating the algorithm's ability to identify well-defined clusters and centroids.

Experimental Evaluation

The researchers evaluated IWK-means using six benchmark datasets from the UCI Machine Learning Repository: Iris, Wine, Glass, WPBC (Wisconsin Prognostic Breast Cancer), Ionosphere, and Housing. These datasets represent a range of complexities, with attributes varying from 4 to 34 and records ranging from 150 to over 500.

Key Results and Discussion

The performance of IWK-means was compared against standard K-means and Fuzzy C-Means (FCM) using the Rand Index (RI) and the Adjusted Rand Index (ARI).

  • Rand Index Superiority: IWK-means consistently outperformed existing algorithms across all six datasets. A standout result was seen in the Housing dataset, where the Rand Index improved from 0.5217 (standard K-means) to 0.9958 (IWK-means).
  • Initialization Stability: The geometric initialization method provided a clear advantage. In the Glass dataset, the Rand Index jumped from 0.6693 with random initialization to 0.8543 using the proposed PCA-based method.
  • ARI Performance: While the Rand Index showed universal improvement, the Adjusted Rand Index (which accounts for chance) was more volatile. Strong gains were observed in the Iris and WPBC datasets, though the algorithm performed slightly worse on the Wine and Glass datasets compared to some existing methods, suggesting areas for further refinement in specific data distributions.
Comprehensive overview of IWK-means clustering results across all six UCI benchmark datasets.

Conclusion and Future Work

The IWK-means algorithm successfully mitigates the classic "K-means headaches" by repurposing PCA for both dimensionality reduction and intelligent initialization. Future work will focus on addressing information loss when the top two PCA components represent less than 95% of total variance and improving the stability of the Adjusted Rand Index across diverse data structures.

Summary updated

Abstract

The improvements we have made are to get the optimal K value, to obtain the initial cluster centers and to calculate the distance by the feature weight. Meanwhile, to cater to the characters of dataset, the IWK-means algorithm uses the principal component analysis (PCA) method as a pretreatment to reduce the dimension of dataset. Finally, the proposed method is experimentally validated on the datasets from the UCI Machine Learning Repository and compared with the existing clustering algorithms by the two evaluation criteria of Rand Index and Adjusted Rand Index
BibTeX
@article{liu2015improved,
  author = {Hongtao Liu and Chen Fang and Yu Wu and Ke Xu and Dai Tian},
  title = {{Improved K-means Algorithm with the Pretreatment of PCA Dimension Reduction}},
  journal = {International Journal of Hybrid Information Technology},
  year = {2015},
  doi = {10.14257/ijhit.2015.8.6.19},
}
Figure