Optimizing K-Means Clustering with Privacy Budget Allocation Based on Variance and Sensitivity

This paper presents a novel approach for enhancing k-means clustering through a privacy-preserving budget allocation mechanism based on variance and sensitivity analysis. The proposed method aims to balance the trade-off between data utility and privacy preservation by selectively allocating privacy budgets across features, emphasizing features with higher variance and lower sensitivity to maintain clustering accuracy. We employ differential privacy techniques, particularly the Laplace mechanism, to introduce controlled noise, protecting user data while minimizing information loss. Comparative analysis with traditional uniform privacy allocation reveals that our approach better preserves cluster cohesion and separation, resulting in superior performance in clustering tasks. Experiments conducted on healthcare datasets demonstrate the efficacy of the proposed strategy in achieving robust privacy guarantees with minimal impact on clustering utility, making it suitable for sensitive data analysis scenarios.