通信学报2026，Vol.47Issue(1)：74-90,17.DOI:10.11959/j.issn.1000−436x.2026009
基于稀疏矩阵变换和有界随机扰动的K-Means聚类外包方案
K-Means clustering outsourcing scheme based on sparse matrix transformation and bounded random perturbation
摘要
Abstract
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.关键词
K-Means聚类/矩阵变换/随机扰动/局部敏感哈希/外包计算/隐私保护Key words
K-Means clustering/matrix transformation/random perturbation/locality sensitive hashing/outsourcing com-putation/privacy-preserving分类
信息技术与安全科学引用本文复制引用
赵韦,谭静文,王焕然,韩帅,杨武,赖明珠..基于稀疏矩阵变换和有界随机扰动的K-Means聚类外包方案[J].通信学报,2026,47(1):74-90,17.基金项目
国家自然科学基金资助项目(No.U22A2036,No.U21B2019,No.62272127,No.62572144) （No.U22A2036,No.U21B2019,No.62272127,No.62572144）
黑龙江省自然科学基金资助项目(No.TD2022F001,No.LH2024F036) （No.TD2022F001,No.LH2024F036）
海南省自然科学基金高层次人才基金资助项目(No.622RC672)The National Natural Science Foundation of China(No.U22A2036,No.U21B2019,No.62272127,No.62572144),The Natural Science Foundation of Heilongjiang(No.TD2022F001,No.LH2024F036),The Natural Science Foundation High-level Talents of Hainan(No.622RC672) （No.622RC672）
