(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210574168.8 (22)申请日 2022.05.25 (71)申请人 支付宝 （杭州） 信息技 术有限公司 地址 310000 浙江省杭州市西湖区西溪路 556号8层B段801-1 1 (72)发明人 刘颖婷　王力　王磊　 (74)专利代理 机构 北京亿腾知识产权代理事务 所(普通合伙) 11309 专利代理师 陈霁　周良玉 (51)Int.Cl. G06F 16/35(2019.01) G06K 9/62(2022.01) G06F 21/62(2013.01) (54)发明名称 一种基于隐私保护的聚类方法及装置 (57)摘要 本说明书实施例提供一种基于隐私保护的 多方联合数据聚类的方法及装置， 第一方和第二 方分别持有用于构成待聚类的所有样本对象的 总特征矩阵的第一特征矩阵和第二特征矩阵； 方 法通过第一方执行， 包括多轮迭代， 任意一轮迭 代包括： 基于第一特征矩阵及第一质 心分片， 与 第二方执行第一多方安全计算， 得到距离矩阵的 第一距离分片， 距离矩阵的第二距离分片由第二 方持有； 基于第一距离分片， 与第二方持有的第 二距离分片执行安全比较计算， 得到类簇索引矩 阵的第一索引分片， 类簇索引矩阵的第二索引分 片由第二方持有； 基于第一特征矩阵及第一索引 分片， 与第二方执行第二多方安全计算， 得到本 轮迭代更新后的第一质心分片， 更新后的第二质 心分片由第二方持有。 权利要求书3页 说明书21页 附图3页 CN 114996449 A 2022.09.02 CN 114996449 A 1.一种基于隐私保护的多方联合数据聚类的方法， 涉及第一方和第二方， 所述第一方 和第二方分别持有第一特征矩阵和 第二特征矩阵， 第一和 第二特征矩阵用于构成待聚类的 所有样本对象的总特征矩阵； 所述方法通过第一方执行， 包括多轮迭代， 其中任意一轮迭代 包括： 基于第一特征矩阵及当前质心矩阵的第 一质心分片， 与第 二方执行基于安全矩阵乘法 的第一多方安全计算， 得到距离矩阵的第一距离分片， 所述距离矩阵表征所有样本对 象与 各类簇的当前质心的距离， 所述距离矩阵的第二距离分片由第二方持有； 基于所述第一距离分片， 与第二方就其持有的第二距离分片执行安全比较计算， 得到 类簇索引矩阵的第一索引分片， 其中， 所述类簇索引矩阵表征所有样本对 象各自所属的类 簇， 所述类簇索引矩阵的第二索引分片由第二方持有； 基于所述第一特征矩阵及所述第一索引分片， 与第二方执行第二多方安全计算， 得到 本轮迭代更新后的第一质心分片， 更新后的第二质心分片由第二方持有。 2.如权利要求1所述的方法， 其中， 所述第一多方安全计算包括： 基于所述第一质心分片， 与第二方持有的第二质心分片， 执行包括安全矩阵乘法的安 全计算， 确定第一中间结果； 基于所述第一特 征矩阵和所述第一质心分片进行本地 运算， 确定第二中间结果； 基于所述第一特征矩阵， 与第二方持有的第二质心分片执行安全矩阵乘法， 确定第三 中间结果； 基于所述第一质心分片， 与第二方持有的第二特征矩阵执行安全矩阵乘法， 确定第 四 中间结果； 基于所述第 一中间结果、 第 二中间结果、 第三中间结果和第四中间结果， 确定所述第一 距离分片。 样本对 象的全部特征构成的矩阵， 所述第二特征矩阵为所述所有样本对 象中第 二部分样本对。 3.如权利要求2所述的方法， 其中， 所述第 一特征矩阵为所述所有样本对象中第 一部分 对象的全部特征构成的矩阵， 所述当前质心矩阵和第一质心分片的维度均为k*d维， 其中d 为所述全部特 征的维度， k 为预设的类簇数目。 4.如权利要求2所述的方法， 其中， 所述第 一特征矩阵为所述所有样本对象的第 一部分 特征构成的矩阵， 所述第二特 征矩阵为所述所有样本对象的第二部分特 征构成的矩阵； 所述当前质心矩阵包括对应于所述第一部分特征的第一子矩阵和对应于所述第二部 分特征的第二子矩阵； 所述第一质心分片包括所述第一子矩阵的第一方分片和所述第二子 矩阵的第一方分片； 所述第二质心分片包括所述第一子矩阵的第二方分片和所述第二子矩 阵的第二方分片； 所述确定第三中间结果包括， 基于所述第一特征矩阵， 与第二方持有的所述第一子矩 阵的第二方分片执 行安全矩阵乘法， 得到第三中间结果； 所述确定第四中间结果包括， 基于所述第二子矩阵的第一方分片， 与第二方持有的所 述第二特 征矩阵执 行安全矩阵乘法， 得到第四中间结果。 5.如权利要求1所述的方法， 其中， 所述第 一特征矩阵为所述所有样本对象的全部特征 的第一特征分片构成的矩阵， 所述第二特征矩阵为所述所有样本对象的全部特征的第二特 征分片构成的矩阵， 所述当前质心矩阵和第一质心分片的维度均为k*d维， 其中d为所述全权　利　要　求　书 1/3 页 2 CN 114996449 A 2部特征的维度， k 为预设的类簇数目。 6.如权利要求2 ‑5所述的方法， 其中， 所述安全矩阵乘法是基于秘密分享协议的通用矩 阵乘法， 或者是基于同态加密协议和秘密分享协议的稀疏矩阵乘法。 7.如权利要求2所述的方法， 其中， 所述安全矩阵乘法是基于同态加密协议和秘密分享 协议的稀疏矩阵乘法； 所述确定第三中间结果， 包括： 获得第二质心分片密文， 第 二质心分片密文是第 二方利用第 一目标公钥对第 二质心分 片同态加密所 得的； 计算所述第一特 征矩阵与所述第二质心分片密文的乘积， 得到第一乘积密文； 生成第一随机矩阵， 作为所述第一乘积密文的第一结果分片， 将所述第一结果分片作 为所述第三中间结果； 基于所述第 一乘积密文和所述第 一随机矩阵， 确定所述第 一乘积密文的第 二结果分片 密文， 将其发送至所述第二方， 以使第二方解密第二结果分片密文， 得到第二结果分片， 作 为与所述第三中间结果对应的第二方中间结果。 8.如权利要求2所述的方法， 其中， 所述安全矩阵乘法是基于同态加密协议和秘密分享 协议的稀疏矩阵乘法； 所述确定第三中间结果， 包括： 利用第二目标公钥加密所述第一特征矩阵， 得到第一矩阵密文， 将其发送至所述第二 方； 从所述第二方接收第三结果分片密文， 对所述第三结果分片密文进行解密， 得到第三 结果分片 明文， 作为所述第三中间结果， 其中， 所述第三结果分片密文是， 所述第二方基于 第二乘积密 文和所述第二方所生成的第二随机矩阵而确定的， 所述第二乘积密文 是所述第 一矩阵密 文与第二方持有的第二质心分片的乘积结果， 所述第二随机矩阵作为所述第二方 持有的与所述第三中间结果对应的第二方中间结果。 9.如权利要求1所述的方法， 其中， 所述得到类簇索引矩阵的第一索引分片， 包括： 基于预设的类簇数量 k构建二叉树的叶子节点； 对于任意样本对象， 针对二叉树的各层节点指示的类簇中的相邻两个类簇， 利用所述 第一距离分片中该样本对象对应于该两个类簇的两个距离值分片， 与第二方执行安全比较 算法， 得到距离更近的类簇作为下一层节点， 直到 达到根节点； 根据各个样本对象的根节点， 确定所述第一索引分片。 10.如权利要求1所述的方法， 其中， 所述得到 本轮迭代更新后的第一质心分片， 包括： 基于所述第 一特征矩阵和所述第 一索引分片， 与第 二方持有的第 二特征矩阵和第 二索 引分片进行安全矩阵乘法， 确定出属于各类簇的样本对 象的特征向量之和的第一和分片， 所述属于各类簇的样本对象的特 征向量之和的第二和分片由所述第二方持有； 基于所述第一索引分片与第二方 执行安全计算， 统计属于各类簇的样本对象的数量； 基于所述第 一和分片及属于各类簇的样本对象的数量， 与所述第 二方就其持有的第 二 和分片执 行安全矩阵乘法， 得到 本轮迭代更新后的第一质心分片。 11.如权利要求1所述的方法， 所述任意 一轮迭代还 包括： 基于所述当前质心矩阵的第 一质心分片、 本轮迭代更新后的第 一质心分片以及预设误 差阈值， 与第二方执行安全比较计算， 得到本轮迭代更新后的质心矩阵与所述当前质心矩 阵的差值与所述预设误差阈值的比较结果， 基于比较结果， 确定是否达到预设迭代停止条权　利　要　求　书 2/3 页 3 CN 114996449 A 3