一种基于隐私保护的聚类方法及装置.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114996449A(43)申请公布日2022.09.02(21)申请号202210574168.8(22)申请日2022.05.25(71)申请人支付宝（杭州）信息技术有限公司地址310000浙江省杭州市西湖区西溪路556号8层B段801-11(72)发明人刘颖婷王力王磊(74)专利代理机构北京亿腾知识产权代理事务所(普通合伙)11309专利代理师陈霁周良玉(51)Int.Cl.G06F16/35(2019.01)G06K9/62(2022.01)G06F21/62(2013.01)权利要求书3页说明书21页附图3页(54)发明名称一种基于隐私保护的聚类方法及装置(57)摘要本说明书实施例提供一种基于隐私保护的多方联合数据聚类的方法及装置，第一方和第二方分别持有用于构成待聚类的所有样本对象的总特征矩阵的第一特征矩阵和第二特征矩阵；方法通过第一方执行，包括多轮迭代，任意一轮迭代包括：基于第一特征矩阵及第一质心分片，与第二方执行第一多方安全计算，得到距离矩阵的第一距离分片，距离矩阵的第二距离分片由第二方持有；基于第一距离分片，与第二方持有的第二距离分片执行安全比较计算，得到类簇索引矩阵的第一索引分片，类簇索引矩阵的第二索引分片由第二方持有；基于第一特征矩阵及第一索引分片，与第二方执行第二多方安全计算，得到本轮迭代更新后的第一质心分片，更新后的第二质心分片由第二方持有。CN114996449ACN114996449A权利要求书1/3页1.一种基于隐私保护的多方联合数据聚类的方法，涉及第一方和第二方，所述第一方和第二方分别持有第一特征矩阵和第二特征矩阵，第一和第二特征矩阵用于构成待聚类的所有样本对象的总特征矩阵；所述方法通过第一方执行，包括多轮迭代，其中任意一轮迭代包括：基于第一特征矩阵及当前质心矩阵的第一质心分片，与第二方执行基于安全矩阵乘法的第一多方安全计算，得到距离矩阵的第一距离分片，所述距离矩阵表征所有样本对象与各类簇的当前质心的距离，所述距离矩阵的第二距离分片由第二方持有；基于所述第一距离分片，与第二方就其持有的第二距离分片执行安全比较计算，得到类簇索引矩阵的第一索引分片，其中，所述类簇索引矩阵表征所有样本对象各自所属的类簇，所述类簇索引矩阵的第二索引分片由第二方持有；基于所述第一特征矩阵及所述第一索引分片，与第二方执行第二多方安全计算，得到本轮迭代更新后的第一质心分片，更新后的第二质心分片由第二方持有。2.如权利要求1所述的方法，其中，所述第一多方安全计算包括：基于所述第一质心分片，与第二方持有的第二质心分片，执行包括安全矩阵乘法的安全计算，确定第一中间结果；基于所述第一特征矩阵和所述第一质心分片进行本地运算，确定第二中间结果；基于所述第一特征矩阵，与第二方持有的第二质心分片执行安全矩阵乘法，确定第三中间结果；基于所述第一质心分片，与第二方持有的第二特征矩阵执行安全矩阵乘法，确定第四中间结果；基于所述第一中间结果、第二中间结果、第三中间结果和第四中间结果，确定所述第一距离分片。样本对象的全部特征构成的矩阵，所述第二特征矩阵为所述所有样本对象中第二部分样本对。3.如权利要求2所述的方法，其中，所述第一特征矩阵为所述所有样本对象中第一部分对象的全部特征构成的矩阵，所述当前质心矩阵和第一质心分片的维度均为k*d维，其中d为所述全部特征的维度，k为预设的类簇数目。4.如权利要求2所述的方法，其中，所述第一特征矩阵为所述所有样本对象的第一部分特征构成的矩阵，所述第二特征矩阵为所述所有样本对象的第二部分特征构成的矩阵；所述当前质心矩阵包括对应于所述第一部分特征的第一子矩阵和对应于所述第二部分特征的第二子矩阵；所述第一质心分片包括所述第一子矩阵的第一方分片和所述第二子矩阵的第一方分片；所述第二质心分片包括所述第一子矩阵的第二方分片和所述第二子矩阵的第二方分片；所述确定第三中间结果包括，基于所述第一特征矩阵，与第二方持有的所述第一子矩阵的第二方分片执行安全矩阵乘法，得到第三中间结果；所述确定第四中间结果包括，基于所述第二子矩阵的第一方分片，与第二方持有的所述第二特征矩阵执行安全矩阵乘法，得到第四中间结果。5.如权利要求1所述的方法，其中，所述第一特征矩阵为所述所有样本对象的全部特征的第一特征分片构成的矩阵，所述第二特征矩阵为所述所有样本对象的全部特征的第二特征分片构成的矩阵，所述当前质心矩阵和第一质心分片的维度均为k*d维，其中d为所述全2CN114996449A权利要求书2/3页部特征的维度，k为预设的类簇数目。6.如权利要求2‑5所述的方法，其中，所述安全矩阵乘法是基于秘密分享协议的通用矩阵乘法，或者是基于同态加密协议和秘密分享协议的稀疏矩阵乘法。7.如权利要求2所述的