基于稀疏矩阵变换和有界随机扰动的K-Means聚类外包方案OA

To address the problem that existing secure outsourcing schemes for K-Means clustering incur high computa-tional and communication overhead,making them difficult to satisfy the efficiency requirements of practical applications,a privacy-preserving K-Means clustering outsourcing scheme based on sparse matrix transformation and bounded random perturbation was proposed.Firstly,a sparse key matrix was constructed by using Gram-Schmidt orthogonalization to per-form efficient orthogonal transformations on plaintext data,effectively hiding the numerical characteristics of the plaintext data.Secondly,bounded random perturbations following a Gaussian distribution were introduced to protect the distance in-formation between plaintext data points,enhancing the security of user data.Finally,an approximate distance estimation method was designed by combining locality sensitive hashing to reduce the computational overhead of the outsourcing scheme under the premise of ensuring clustering accuracy.Theoretical analysis demonstrates that the proposed scheme achieves the design goals of correctness,security and efficiency.Experimental results on multiple real-world datasets show that compared to existing K-Means clustering outsourcing schemes based on homomorphic encryption,the proposed scheme significantly reduces computational and communication overhead while maintaining clustering accuracy.