Literature Review: K-Means Clustering with Differential Privacy in Horizontal and Vertical Federation Settings

Analysis of Modern Research on K-means, Differential Privacy, and Federated Learning

This review examines key research at the intersection of clustering algorithms, data privacy protection, and distributed machine learning paradigms.

Need help with this topic? Get a consultation in 10 minutes! Telegram: @Diplomit Phone/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Place an order online: Order Thesis

Differential Privacy in K-means: From Theory to Practice

Distributed and Federated Scenarios

1. Distributed K-Means with Local Differential Privacy Guarantees

• What was done: The paper proposes the first mechanism for a distributed K-means algorithm providing Local Differential Privacy (LDP). This means users distort their own data on their device before sending it to an untrusted server for clustering. The authors also introduced an extended mechanism to protect intermediate results and considered a scenario with varying user privacy requirements.
• Results: The mechanism is theoretically proven to provide LDP. Experiments on real-world datasets showed that this approach preserves clustering quality better than standard methods with centralized DP, especially in a distributed setting without a trusted aggregator.
• Drawbacks: The main limitation is the inevitable loss of utility due to the strong noise inherent to the LDP model. Algorithm performance can degrade significantly under very strict privacy requirements (small ε).
• Future Directions: The proposed mechanism is fundamental for Horizontal Federated Learning (HFL) scenarios. Further research may focus on developing adaptive privacy budget allocation schemes to further improve utility.

2. Federated Learning with Heterogeneous Differential Privacy

• What was done: The problem of heterogeneous differential privacy within FL was investigated. The authors analyzed the optimal solution for a simplified linear task and proposed a new algorithm, FedHDP, which uses personalization and server-side weighted averaging based on client privacy choices.
• Results: Theoretical analysis shows that under heterogeneous privacy, the optimal solution for clients is a personalized model. Experiments demonstrate that FedHDP achieves a performance gain of up to 9.27% compared to baseline DP-FL.
• Drawbacks: The research focuses on theoretical analysis for linear models and simplified tasks. Applying the approach to complex nonlinear models requires further study.
• Future Directions: This approach is crucial for the practical deployment of DP in FL. A promising direction is integrating such heterogeneous schemes with clustering algorithms like K-means within FL.

Need help with this topic? Get a consultation in 10 minutes! Telegram: @Diplomit Phone/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Place an order online: Order Thesis

Centralized and Practical Methods

3. Practical Differentially Private Clustering (Google)

• What was done: A new practical algorithm for differentially private clustering in the central model is presented. The algorithm uses Locality-Sensitive Hashing (LSH) to create a private data "core" on which a standard algorithm (e.g., K-means++) is then run.
• Results: The algorithm is implemented in an open-source Google library. Evaluation showed that it provides competitive or better quality compared to existing baseline methods.
• Drawbacks: The algorithm requires the user to specify a priori the radius of a sphere containing all data. Separate privacy handling is also needed at the data preprocessing stage.
• Future Directions: This work demonstrates the transition of theoretical developments into practical tools. The research shows the possibility of creating efficient and practical DP versions of standard machine learning algorithms.

5. An Improved Differentially Private K-means Clustering Algorithm

• What was done: An improved DP-Kmeans algorithm is proposed, which adds Laplace noise adaptively based on the silhouette coefficient of each cluster. This allows adding different levels of noise to different clusters in each iteration.
• Results: Experiments show that the new algorithm improves the utility of clustering results under privacy constraints, especially for small privacy budget (ε) values.
• Drawbacks: The method still relies on the centralized model of a trusted data aggregator. It does not consider scenarios with an untrusted coordinator, as in LDP or FL.
• Future Directions: The proposed idea of adaptively allocating the privacy budget among clusters can be transferred to the context of federated learning to improve clustering quality under strict privacy constraints.

8. Differentially Private k-Means Clustering (Su et al., 2016)

• What was done: This paper proposes a comprehensive algorithm for differentially private K-means in the centralized model. The authors modify key steps: 1) centroid initialization using a DP version of K-means++, 2) iterative centroid updating with Laplace noise, 3) limiting iterations.
• Results: Key results include rigorous proof of differential privacy and experiments showing the algorithm significantly outperforms naive methods.
• Drawbacks: Dependency on a trusted center. The algorithm is not directly intended for federated scenarios.
• Future Directions: Methods proposed in this paper are prime candidates for transfer to HFL and VFL architectures. Questions: how to distribute noise addition in HFL and how to coordinate computations in VFL.

Vertical Federated Learning (VFL) and Privacy

4. Survey of Privacy Threats and Protection Methods in Vertical Federated Learning

• What was done: This is the first comprehensive survey systematizing privacy threats and protection methods in VFL. Threats and countermeasures are classified from the perspective of the model lifecycle.
• Results: Provides a clear taxonomy of attacks and defense mechanisms in VFL. Serves as a valuable resource for understanding the problem landscape.
• Drawbacks: Does not propose new algorithmic solutions but focuses on systematizing existing ones.
• Future Directions: Clearly identifies open problems. This sets the direction for future research, including the development of DP K-means within VFL.

7. Privacy-preserving k-means clustering via multi-party computation (Bunn & Ostrovsky, 2007)

• What was done: This early work explores privacy-preserving clustering in vertical data partitioning (VFL). The authors propose a protocol based on Secure Multi-Party Computation (MPC).
• Results: Main result is a working cryptographic protocol guaranteeing confidentiality under honest-but-curious participants.
• Drawbacks: High computational and communication overhead. Lack of formal differential privacy guarantees.
Future Directions: Prospects are seen in combining MPC with differential privacy and optimizing protocols for use with improved initialization algorithms like K-means++.

13. Differentially Private Vertical Federated Clustering (Z. Li et al., 2022)

• What was done: Proposes the first practical algorithm for vertical federated (VFL) k-means with differential privacy. Based on an untrusted central server with local DP computation.
• Results: Algorithm with proven ε-differential privacy guarantees. Approach outperforms baseline methods, approaching centralized DP solution quality.
• Drawbacks: Quality depends on accuracy of weighted grid construction. Does not use advanced initialization methods like k-means++.
• Future Directions: Integrating improved initialization algorithms (k-means++) into VFL architecture to improve initial centroids and reduce privacy budget consumption.

Need help with this topic? Get a consultation in 10 minutes! Telegram: @Diplomit Phone/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Place an order online: Order Thesis

Theoretical Foundations and Improvements of K-means++

Fundamental Works and Surveys

6. K-means++: The Advantages of Careful Seeding (Arthur & Vassilvitskii, 2007)

• What was done: Introduces the K-means++ algorithm, which became the de facto standard for centroid initialization. Describes the D² sampling strategy.
• Results: Theoretical proof that the algorithm guarantees an O(log k) approximation of the objective function. Experiments confirm faster convergence.
• Drawbacks: Does not address computational efficiency on large data, distributed computing, or confidentiality aspects.
• Future Directions: Any system using K-means benefits from this initialization. Key challenge: adapting "careful seeding" to distributed data (HFL/VFL) with noise for DP.

9. Optimal k-means Clustering in One Dimension by Dynamic Programming (Wang & Song, 2011)

• What was done: Proposes an exact algorithm for K-means in one dimension solved by dynamic programming in O(kn) time.
• Results: This result is theoretically optimal.
• Drawbacks: Does not directly address federated learning or privacy.
• Future Directions: Opens prospect for more efficient local steps in HFL/VFL. Can reduce iterations and cumulative privacy leakage.

10, 27. k-means++: A Survey — Survey articles (Anselm, Ri, Wang, 2024)

• What was done: Presents a modern structured overview of k-means++, its theoretical foundations, and improvements. Details the proof and discusses "bad" datasets.
• Results: Systematization of knowledge about the algorithm. Serves as excellent starting point.
• Drawbacks: Does not propose new solutions. Does not consider modifications for distributed environments or confidentiality mechanisms.
• Future Directions: Provides solid theoretical foundation. Prospect: applying principles to federated learning tasks with added noise for privacy.

Improvements and Modifications of K-means++

11. CAPKM++2.0: An upgraded version... (Li & Wang, 2023)

• What was done: Upgraded version of Collaborative Annealing Power k-means++ (CAPKM++2.0). Aims to reduce dependency on initialization.
• Results: Statistically significantly outperforms predecessor and six other classical algorithms.
• Drawbacks: Conducted within centralized data model. Does not consider distributed scenarios or DP.
• Future Directions: Main idea can be adapted for federated learning to achieve stable clustering under privacy constraints.

12. Noisy k-means++ Revisited (Grunau et al., 2023)

• What was done: Theoretical work proving robustness of k-means++ to adversarial noise in sampling probabilities.
• Results: Rigorous proof that algorithm retains O(log k) approximation guarantee with adversarial inaccuracy.
• Drawbacks: Purely theoretical. Noise modeled as adversarial perturbation, not stochastic noise (e.g., Gaussian for DP).
• Future Directions: Has direct importance for topic. Robustness to controlled noise is fundamental prerequisite for DP versions.

17. Local Search k-means++ with Foresight (Conrads et al., 2024)

• What was done: Research on improving practical efficiency of LS++ algorithm. Proposes new Foresight LS++ (FLS++) algorithm.
• Results: New algorithm demonstrates better solution quality than LS++ while maintaining guarantees.
• Drawbacks: Focuses exclusively on centralized setting. Does not consider distributed computing or data privacy.
• Future Directions: Key prospect: adapting FLS++ principles for federated scenarios with privacy constraints.

20. k-variates++: more pluses in the k-means++ (Nock et al., 2016)

• What was done: Two-sided generalization of k-means++ initialization. Generalizes sampling procedure and theoretical guarantee.
• Results: Main result: new adaptation of k-variates++ for Differential Privacy tasks.
• Drawbacks: Does not disclose noise addition details or precise privacy guarantees. Unclear interaction with FL architecture.
• Future Directions: Critically important theoretical bridge. Directly points to possibility of building DP versions of initialization algorithm.

22. Noisy, Greedy and Not So Greedy k-means++ (Bhattacharya et al., 2019)

• What was done: Theoretical analysis of greedy and noisy versions of k-means++.
• Results: For noisy version: proven to preserve polylogarithmic O(log² k) guarantee under adversarial distortion.
• Drawbacks: Does not propose specific mechanism for ensuring DP. Purely theoretical.
• Future Directions: Provides critically important theoretical foundation. Result indicates base algorithm can be robust to deliberate noising required for DP.

Need help with this topic? Get a consultation in 10 minutes! Telegram: @Diplomit Phone/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Place an order online: Order Thesis

Applied Research and Hybrid Models with K-means++

Clustering in Various Domains

14. Using k-means++ algorithm for researchers clustering (Rukmi, Iqbal, 2017)

• What was done: Method for clustering researchers based on publications and social network characteristics using K-means++.
• Results: Application presenting information about researchers within clusters developed.
• Drawbacks: Purely applied. No theoretical analysis. Does not consider scalability, confidentiality, or collaborative clustering.
• Future Directions: Pipeline can be adapted for Horizontal Federated Learning scenarios.

15. Hybrid model based on K-means++ algorithm... for short-term photovoltaic power prediction (2023)

• What was done: Innovative hybrid model (HKSL) for forecasting photovoltaic power. K-means++ classifies weather types.
• Results: Significant reduction in forecast error compared to baseline methods.
• Drawbacks: Model is centralized. Does not consider scenario where data distributed among energy grid participants.
• Future Directions: Ideal candidate for Vertical Federated Learning. Task: create federated and DP analogue of HKSL model.

16. A novel hybrid method of lithology identification based on k-means++ algorithm and fuzzy decision tree (2022)

• What was done: New method for lithology identification from well-logging data. K-means++ optimizes initial cluster centers.
• Results: Accuracy reached 93.92%, surpassing other ML algorithms.
• Drawbacks: Method centralized. Does not consider realistic scenario with data held by different companies.
• Future Directions: Task can be reformulated in VFL context. Promising direction: developing federated version with DP guarantees.

18. An indoor thermal comfort model based on K-means++ algorithm (2025)

• What was done: Model for predicting group thermal comfort indoors based on unsupervised learning using K-means++.
• Results: Achieved prediction accuracy above 90%, surpassing classical PMV-PPD model.
• Drawbacks: Built on assumption of centralized dataset. Reality: data collected by different systems.
• Future Directions: Ideally illustrates need for VFL with DP. Jointly training K-means++ on distributed data while protecting privacy is important practical task.

19. Spatial classification of hyperspectral images using the k-means++ clustering method (Zimichev et al., 2014)

• What was done: Comprehensive method for classifying hyperspectral images considering spatial proximity. Combines SVM with segmentation via k-means++.
• Results: Improves both accuracy and speed of classification.
• Drawbacks: Applied and outdated. No theoretical analysis. Does not consider distributed processing, confidentiality, or FL.
• Future Directions: Pipeline still relevant. Adaptation to HFL conditions where hyperspectral images stored by different organizations.

23. K-Means++ Clustering Algorithm in Categorization of Glass Cultural Relics (2023)

• What was done: K-means++ used for subcategorization of ancient glass artifacts based on chemical composition data.
• Results: Pipeline successfully identified six plausible subcategories. Algorithm showed high robustness to random noise.
• Drawbacks: Specialized case-study. Does not contribute to theory. Does not address distributed computing, confidentiality, or FL.
• Future Directions: Illustrates how applied tasks can drive complex research. Prospect: considering similar task in HFL scenario requiring DP protocols.

26. A K-means++ Based User Classification Method for Social E-commerce (Cui et al., 2021)

• What was done: User classification method for social e-commerce based on K-means++. Data collected via mobile app with secure container.
• Results: Successfully tested on real data. Identified three stable user classes differing by retention rate.
• Drawbacks: Purely applied and centralized. Assumes collection of raw behavioral data on central server.
• Future Directions: Architecture of interest for HFL scenarios. Devices could locally run private K-means++, with safe aggregation on server.

Hybrid and Accelerated Methods

21. SOM++: Integration of Self-Organizing Map and K-Means++ Algorithms (Dogan et al., 2013)

• What was done: Hybrid SOM++ algorithm where K-means++ used for intelligent initialization of SOM weights.
• Results: SOM++ has good stability and significantly outperforms ordinary SOM in training time.
• Drawbacks: Narrowly specialized. Does not consider K-means++ as standalone method.
• Future Directions: Idea of using K-means++ as "smart initializer" fruitful. Opens prospect for hybrid federated algorithms.

25. Nyström Method with Kernel K-means++ Samples as Landmarks (Oglic, Gärtner, 2017)

• What was done: Proposes using kernel k-means++ sampling for selecting landmarks in Nyström method for low-rank kernel matrix approximation.
• Results: First theoretical guarantee on relative approximation error for Nyström with landmarks selected via kernel k-means++.
• Drawbacks: Does not focus on improving k-means++, applies it as tool for another task.
• Future Directions: Demonstrates power of k-means++ for selecting representative data subset. In HFL, DP version could select local landmarks for safe aggregation.

28. A Clustering Optimization for Energy Consumption Problems in Wireless Sensor Networks using Modified K-Means++ Algorithm (Mukti et al., 2022)

• What was done: Modifies k-means++ for integration into LEACH routing protocol to optimize energy consumption in WSN.
• Results: Proposed protocol forms more balanced clusters, reduces energy consumption, prolongs network lifecycle.
• Drawbacks: Centralized. Does not consider distributed scenarios or data confidentiality.
• Future Directions: Demonstrates effectiveness of k-means++ for network structure optimization. In HFL, clients could run private version to form local candidates for global energy-efficient structure.

29. A Hybrid K-Means++ and Particle Swarm Optimization Approach for Enhanced Document Clustering (Hassan et al., 2025)

• What was done: Hybrid approach combining K-Means++ for initialization and PSO for global document clustering optimization.
• Results: Demonstrated superiority over baseline methods on multiple datasets.
• Drawbacks: May face scalability issues due to PSO complexity. Sensitive to hyperparameter tuning.
• Future Directions: Could be adapted for horizontal FL: clients locally execute K-Means++, centroids safely aggregated for global PSO initialization.

30. Accelerating the k-Means++ Algorithm by Using Geometric Information (Rodríguez Corominas et al., 2025)

• What was done: Two exact methods for accelerating k-means++ initialization using geometric information (triangle inequality and norm filter).
• Results: Significantly reduces points examined and distances calculated while preserving theoretical guarantees.
• Drawbacks: Practical acceleration doesn't always match theoretical due to cache issues. Not intended for distributed scenarios.
• Future Directions: Could be adapted for client side in HFL. Clients run accelerated k-means++, candidates aggregated for global initialization.

Theoretical Limitations and "Bad" Cases

24. A bad instance for k-means++ (Brunsch, Röglin, 2012)

• What was done: Definitive answer about probabilistic properties of k-means++. Shows algorithm behaves poorly with high probability on special instances.
• Results: Rigorous proof that instances exist where k-means++ achieves no better than (2/3 — ε)·log k approximation with probability exponentially close to 1.
• Drawbacks: Artificiality and high dimensionality of constructed instances. Purely theoretical.
• Future Directions: Establishes fundamental limits. Important caution for distributed scenarios. Prospect: investigating how DP noise affects probability of "bad" scenarios.

Additional Reference List

1. A comparative study of K-Means, K-Means++ and Fuzzy C-Means clustering algorithms // 2017 3rd International Conference on Computational Intelligence & Communication Technology (CICT). – Ghaziabad, India, 2017. – P. 1–5. – DOI: 10.1109/CIACT.2017.7977272.

2. Robust k-means++ / A. Deshpande, P. Kacham, R. Pratap // Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI). – 2020. – Vol. 124. – P. 799–808.

3. Improving Scalable K-Means++ / M. A. [author] // Algorithms. – 2021. – Vol. 14, iss. 1. – Art. 6. – DOI: 10.3390/a14010006.

4. Scalable K-Means++ / B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii. – 2012. – arXiv: 1203.6402.

5. A novel defect prediction method for web pages using k-means++ / M. M. Ozturk, U. Cavusoglu, A. Zengin // Expert Systems with Applications. – 2015. – Vol. 42, iss. 19. – P. 6496–6506.

6. Parallelization of the K-Means++ Clustering Algorithm / S. Daoudi, C. M. A. Zouaoui, M. C. El-Mezouar, N. Taleb // Ingénierie des Systèmes d'Information. – 2021. – Vol. 26, no. 1. – P. 59–66.

7. A Better k-means++ Algorithm via Local Search / S. Lattanzi, C. Sohler // Proceedings of the 36th International Conference on Machine Learning (ICML). – 2019. – Vol. 97. – P. 3662–3671.

8. CAPKM++2.0: An upgraded version of the collaborative annealing power -means++ clustering algorithm // Knowledge-Based Systems. – 2023. – Vol. 259. – Art. 110067.

9. Noisy k-means++ Revisited / C. Grunau, A. A. Özüdoğru, V. Rozhoň. – 2023. – arXiv: 2307.13685.

10. Notice of Violation of IEEE Publication Principles: K-means versus k-means ++ clustering technique / S. Agarwal, S. Yadav, K. Singh // 2012 World Congress on Information and Communication Technologies (WICT). – 2012. – P. 368–373.

11. Efficient k-means++ with random projection / J. Y. K. Chan, A. P. Leung // 2017 International Conference on Fuzzy Theory and Its Applications (iFUZZY). – 2017. – P. 22–27.

12. A bad instance for k-means++ / T. Brunsch, H. Röglin // Theoretical Computer Science. – 2013. – Vol. 493. – P. 7–18.

13. Beyond k-Means++: Towards better cluster exploration with geometrical information / Y. Ping, H. Li, B. Hao, C. Guo, B. Wang // Pattern Recognition. – 2024. – Vol. 145. – Art. 109886.

14. Nyström Method with Kernel K-means++ Samples as Landmarks / D. Oglic, T. Gärtner // Proceedings of the 34th International Conference on Machine Learning (ICML). – 2017. – Vol. 70. – P. 2652–2660.

15. Hybrid model based on K-means++ algorithm, optimal similar day approach, and long short-term memory neural network for short-term photovoltaic power prediction / R. Bai, Y. Shi, M. Yue, X. Du // Energy Reports. – 2023. – Vol. 9, Suppl. 8. – P. 456–466.

16. A novel hybrid method of lithology identification based on k-means++ algorithm and fuzzy decision tree / Q. Ren, H. Zhang, D. Zhang, X. Zhao, L. Yan, J. Rui // Journal of Petroleum Science and Engineering. – 2022. – Vol. 208, Part D. – Art. 109516.

17. Local Search k-means++ with Foresight / T. Conrads, L. Drexler, J. Könen, D. R. Schmidt, M. Schmidt. – 2024. – arXiv: 2406.02739.

18. An indoor thermal comfort model for group thermal comfort prediction based on K-means++ algorithm / Y. Liu, X. Li, C. Sun, Q. Dong, Q. Yin, B. Yan // Energy and Buildings. – 2024. – Vol. 310. – Art. 114080.

19. Spatial classification of hyperspectral images using the k-means++ clustering method / E. A. Zimichev, N. L. Kazansky, P. G. Serafimovich // Computer Optics. – 2022. – Vol. 46, No. 2. – P. 274–281.

20. PERFORMANCE COMPARISON OF K-MEANS, PARALLEL K-MEANS AND K-MEANS++ / R. Aliguliyev, S. F. Tahirzada // RT&A. – 2025. – №SI 7 (83).

21. Novel Automated K-means++ Algorithm for Financial Data Sets / G. Du, X. Li, L. Zhang, L. Liu, C. Zhao // Mathematical Problems in Engineering. – 2021. – Vol. 2021. – Art. ID 5521119.

22. k-variates++: more pluses in the k-means++ / R. Nock, R. Canyasse, R. Boreli, F. Nielsen // Proceedings of The 33rd International Conference on Machine Learning (ICML). – 2016. – Vol. 48. – P. 145–154.

23. SOM++: Integration of Self-Organizing Map and K-Means++ Algorithms // Advances in Knowledge Discovery and Data Mining: PAKDD 2013. – 2013. – P. 235–246.

24. Noisy, Greedy and Not So Greedy k-means++ / A. Bhattacharya, J. Eube, H. Röglin, M. Schmidt. – 2019. – arXiv: 1912.00653.

25. K-Means++ Clustering Algorithm in Categorization of Glass Cultural Relics / J. Meng, Z. Yu, Y. Cai, X. Wang // Applied Sciences. – 2023. – Vol. 13, iss. 8. – Art. 4736.

26. A Bad Instance for k-means++ // Theory and Applications of Models of Computation: TAMC 2011 / ed. by M. Ogihara, J. Tarui. – Berlin, Heidelberg : Springer, 2011. – P. 325–336.

27. A K-means++ Based User Classification Method for Social E-commerce / H. Cui, S. Niu, K. Li, C. Shi, S. Shao, Z. Gao // Intelligent Automation & Soft Computing. – 2021. – Vol. 28, no. 1. – P. 277–291.

28. Nyström Method with Kernel K-means++ Samples as Landmarks / D. Oglic, T. Gärtner // Proceedings of the 34th International Conference on Machine Learning (ICML 2017). – 2017. – P. 2652–2660.

29. Parallelization of the K-Means++ Clustering Algorithm / S. Daoudi, C. M. A. Zouaoui, M. C. El-Mezouar, N. Taleb // Intelligent Systems and Applications. – 2021. – P. 59–66.

30. A Hybrid K-Means++ and Particle Swarm Optimization Approach for Enhanced Document Clustering / E. Hassan et al. // IEEE Access. – 2025. – Vol. 13. – P. 48818–48840.

Need help with this topic? Get a consultation in 10 minutes! Telegram: @Diplomit Phone/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Place an order online: Order Thesis