An efficient incremental clustering algorithm based on differential privacy

Abstract In the era of big data, traditional clustering methods face challenges such as insufficient privacy protection, lack of convergence guarantees, and high computational overhead, limiting their practical applicability. To address these issues, we propose an E fficient I ncremental C lustering algorithm based on D ifferential P rivacy (EICDP). By leveraging incremental learning, EICDP dynamically adjusts the number of cluster centroids and introduces a convergence criterion to ensure algorithmic stability, thereby enhancing the reliability of clustering results. To address privacy concerns, EICDP employs a dynamic privacy budget allocation strategy based on Euclidean distance, adaptively injecting noise during centroid updates to balance data utility and privacy preservation. Theoretical analysis demonstrates that EICDP satisfies $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -differential privacy and converges to stable cluster centroids. Extensive experiments validate the algorithm’s effectiveness: EICDP achieves approximately 15% improvement in clustering quality and 65% reduction in computational time compared to state-of-the-art methods, while demonstrating exceptional efficiency in handling large-scale datasets. Additionally, the extension to dynamic data streams (DEICDP) highlights its robustness in real-time scenarios. This study provides a scalable and privacy-aware solution for applications requiring rapid and secure data analysis, such as healthcare and financial systems.