可验证的隐私保护k-means聚类方案

张 恩，李会敏，常 键

（1.河南师范大学计算机与信息工程学院，河南新乡 453007；2.智慧商务与物联网技术河南省工程实验室（河南师范大学），河南新乡 453007）

（*通信作者电子邮箱zhangenzdrj@163.com）

0 引言

聚类算法在机器学习、信息检索、模式识别等领域的数据挖掘中具有广泛的应用，在现实生活中，对医疗、社会科学、商业等应用的研究有着重要的作用。例如，现有两个医疗机构，每个机构都拥有患者的疾病和临床等治疗过程收集的数据集。假设这两家机构使用各自的方法收集数据后，希望将数据组合在一起进行训练，并确定使用聚类算法能够给疾病控制机制提供更好的研究方向。由于政策法规的约束以及数据的敏感性，双方均不愿意将数据共享，如何在保护隐私的前提下协作地在联合数据集上进行聚类成为一个具有挑战性的问题。

目前，大数据的存储和计算研究已趋近成熟，但是面临来自不同数据源的联合数据的隐私问题仍有待优化。在联合计算过程中，如果有一个可信的第三方，Alice和Bob都愿意将数据发送给该第三方，那么该第三方可以使用聚类算法训练双方的数据并将聚类中心发送给Alice和Bob。然而，在现实中，很难找到完全可信的第三方。针对此类问题，一系列文章结合安全多方计算［1-4］对聚类算法进行研究。

现有的保护隐私的聚类方法需要大量的计算、通信和存储开销，当训练大量数据时，如果用户没有足够的资源，就无法进行聚类。云外包计算的出现提供了很好的解决方法，云外包计算［5-6］的一个基本优势是数据外包的实现，使得用户在资源受限的设备上进行大量的数据存储和使用。……