(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210949562.5 (22)申请日 2022.08.09 (71)申请人 中国人民解 放军国防科技大 学 地址 410003 湖南省长 沙市开福区德雅路 109号 (72)发明人 柳林　付绍静　邓晏湘　罗玉川　 王勇军　赵文涛　罗淞巍　 (74)专利代理 机构 北京风雅颂专利代理有限公 司 11403 专利代理师 曾志鹏 (51)Int.Cl. G06K 9/62(2022.01) G06F 21/62(2013.01) G06F 21/60(2013.01) (54)发明名称 一种基于kd-tree的隐私保护外包k-means 聚类方法、 系统 (57)摘要 本发明提供一种基于kd ‑tree的隐私保护外 包k‑means聚类方法、 系 统， 其中方法包括： 获取 安全最值协议、 安全欧式距离协议、 安全比较协 议、 安全聚类协议； 用户在明文上基于数据构造 kd‑tree， 然后进行加性秘密共享分为两份发送 给云服务器； 两个 云服务器获取设定数量的数据 簇中心， 采用过滤算法， 根据所述安全欧式距离 协议、 安全比较协议、 安全最值协议、 安全聚类协 议和所述kd ‑tree， 对所述待聚类数据进行聚类。 本发明的技术方案， 能够在双云服务器上进行高 效安全的外包k ‑means聚类 。 权利要求书2页 说明书6页 附图2页 CN 115329859 A 2022.11.11 CN 115329859 A 1.一种基于kd ‑tree的隐私保护外包k ‑means聚类方法， 其特 征在于， 包括： 获取安全最值协议、 安全欧式距离协议、 安全比较协议、 安全聚类协议， 其kd ‑tree的构 建交给用户后进行加密发送给双云服 务器； 获取待聚类数据， 计算数据所有维度的方差， 以方差最大的维度作为 参考依据； 根据所述参考维度， 找到维度 数据的中位数， 将数据均匀的划分为两份， 并且重复上述 过程， 直到数据被划分到给定数量； 获取设定数量的数据簇中心， 采用过滤算法， 根据 所述安全欧式距离协议、 安全比较协 议、 安全最 值协议、 安全聚类协议和所述 kd‑tree， 对所述待聚类数据进行聚类。 2.根据权利要求1所述的基于kd ‑tree的隐私 保护外包k ‑means聚类方法， 其特征在于， 所述采用安全比较协议和安全划分子协议， 构建所述待聚类数据的kd ‑tree包括： 将所述待聚类数据作为所述 根节点的集 合； 响应于节点的集合中具有多个待聚类数据， 根据安全比较协议获取该节点集合中待聚 类数据在所述参考维度下 的中值， 将该中值所对应的待聚类数据存储在该节点中， 并将参 考维度下大于和小于中值的待聚类数据分别作为该节点的左子节点的集合和右子节点的 集合； 响应于节点的集 合中仅有一个待聚类数据， 将该待聚类数据存 储在该节点中。 3.根据权利要求1所述的基于kd ‑tree的隐私 保护外包k ‑means聚类方法， 其特征在于， 所述采用过 滤算法对所述 kd‑tree进行聚类包括： 从所述kd‑tree的根节点 开始遍历其各节点， 并根据安全过 滤算法对各节点进行聚类； 响应于聚类成功， 停止遍历所述 kd‑tree。 4.根据权利要求3所述的基于kd ‑tree的隐私 保护外包k ‑means聚类方法， 其特征在于， 所述据安全过 滤算法对各节点进行聚类包括： 获取节点的集 合中各待聚类数据的均值； 根据安全欧式距离协议， 计算所述均值与候选簇集合中各数据簇中心之间的欧氏距 离， 并根据所述安全最值协议得到与所述均值欧式距离最小的数据簇中心， 将该数据簇中 心作为第一备选数据簇中心； 将第一备选簇 中心与候选簇集合中其他簇中心进行比较， 若节点内所有数据相较于其 他簇中心均距离备选簇中心更近， 则将其他簇中心从候选簇集合中移除， 若候选簇集合中 最后仅剩一个簇， 则认为该节点中所有数据均可被划分到备选数据簇中心中， 不再对子节 点进行聚类； 否则， 传递将当前候选簇集合作为子节点候选簇集合， 对子节点进行上述过 程， 直到所有节点均被划分成功。 5.一种计算机设备， 其特征在于， 包括处理器和存储器， 所述存储器上存储有用于在所 述处理器上执行 的计算机程序指令， 所述处理器执行该计算机程序指令时， 实现如权利要 求1‑4任意一项所述的基于kd ‑tree的隐私保护外包k ‑means聚类方法。 6.一种计算机存储介质， 其特征在于， 其存储有计算机指令， 所述计算机指令由处理器 运行时， 实现根据权利要求1 ‑4的任意一项所述的基于kd ‑tree的隐私保护外包k ‑means聚 类方法。 7.一种基于kd ‑tree的隐私保护外包k ‑means聚类系统， 其特征在于， 包括多个客户端 和两个云服 务器， 其中权　利　要　求　书 1/2 页 2 CN 115329859 A 2所述客户端用于： 首先基于存储的数据构造kd ‑tree， 然后加性秘密共享划分为两部 分， 最后将各部分 分别发送给不同的云服 务器； 所述云服务器用于根据权利要求1 ‑4任意一项所述的基于kd ‑tree的隐私保护外包k ‑ means聚类方法聚类所接收到的数据。权　利　要　求　书 2/2 页 3 CN 115329859 A 3