Trading off privacy, utility, and stability in privacy-preserving K-means clustering using an adaptive multi-objective memetic algorithm

Abstract Protecting sensitive information while maintaining data utility is a fundamental challenge in privacy-preserving data mining. Differential Privacy (DP)-based K -means clustering provides a principled solution by injecting noise through a privacy budget; however, determining an optimal budget allocation remains a complex task due to the inherent trade-offs among privacy protection, clustering utility, and model stability. Motivated by the effectiveness of Evolutionary Algorithms (EAs) in solving complex optimization problems, this paper proposes an enhanced Adaptive Multi-Objective Memetic Algorithm for Differentially Private K -means (AMOMA-DPK) clustering. Unlike many existing approaches that primarily focus on one or two objectives, the proposed method simultaneously optimizes three conflicting objectives: maximizing privacy by minimizing the total privacy budget, maximizing clustering utility by minimizing the Normalized Intra-Cluster Variance (NICV), and maximizing clustering stability by minimizing clustering instability. These objectives are formulated within a Multi-Objective Optimization (MOO) framework, enabling the generation of a diverse set of Pareto-optimal solutions that support flexible decision-making based on application-specific privacy requirements. To effectively explore the search space, AMOMA-DPK incorporates an adaptive parameter memory mechanism that dynamically adjusts crossover and mutation rates based on historically successful configurations. This is complemented by a gene-wise adaptive crossover strategy, probabilistic mutation with budget-aware perturbation, and an imbalanced local search refinement that enhances exploitation by redistributing privacy budgets across iterations. Together, these components form a robust memetic framework capable of balancing exploration and exploitation while maintaining feasibility through repair operators. Experiments on three real-world datasets show that the proposed method generally produces more competitive Pareto fronts and higher hypervolume (HV) values than representative baselines, with the highest mean HV across all tested budget and cluster-count settings on Online Shoppers. Additional comparisons with fixed allocation strategies support its effectiveness, while ablation results show that individual component effects are dataset- and budget-dependent. These findings highlight the effectiveness of AMOMA-DPK for optimizing privacy budget allocation under the evaluated settings. The source code used in this study is publicly available at https://github.com/Wayne-on-the-road/AMOMA-DPK .