Private Hierarchical Clustering and Efficient Approximation
Private Hierarchical Clustering and Efficient Approximation
复制标题
DOI：
10.1145/3474123.3486760
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Xianrui Meng;D. Papadopoulos;Alina Oprea;Nikos Triandopoulos
中科院分区：
文献类型：
--
作者：
Xianrui Meng;D. Papadopoulos;Alina Oprea;Nikos Triandopoulos
在协作学习中，多方贡献自己的数据集，共同推导出众多预测任务的全局机器学习模型。尽管有效，但这种学习范式未能涵盖涉及高度敏感数据的关键应用领域，例如医疗保健和安全分析，其中隐私风险限制实体仅使用自己的数据集单独训练模型。在这项工作中，我们的目标是保护隐私的协作层次聚类。我们引入了一个正式的安全定义，旨在实现实用性和隐私之间的平衡，并提出一个可证明满足它的两方协议。然后，我们通过以下方式扩展我们的协议：（i）单链接聚类的优化版本，以及（ii）可扩展的近似变体。我们实施了所有方案，并通过实验评估了它们在合成数据集和真实数据集上的性能和准确性，获得了非常令人鼓舞的结果。例如，我们的安全近似协议针对超过 1M 的 10 维数据样本的端到端执行需要 35 秒的计算，并达到 97.09% 的准确率。
In collaborative learning, multiple parties contribute their datasets to jointly deduce global machine learning models for numerous predictive tasks. Despite its efficacy, this learning paradigm fails to encompass critical application domains that involve highly sensitive data, such as healthcare and security analytics, where privacy risks limit entities to individually train models using only their own datasets. In this work, we target privacy-preserving collaborative hierarchical clustering. We introduce a formal security definition that aims to achieve balance between utility and privacy and present a two-party protocol that provably satisfies it. We then extend our protocol with: (i) an optimized version for single-linkage clustering, and (ii) scalable approximation variants. We implement all our schemes and experimentally evaluate their performance and accuracy on synthetic and real datasets, obtaining very encouraging results. For example, end-to-end execution of our secure approximate protocol for over 1M 10-dimensional data samples requires 35sec of computation and achieves 97.09% accuracy.