Privacy-preserving LOF outlier detection
Privacy-preserving LOF outlier detection
复制标题
DOI：
10.1007/s10115-013-0692-0
复制
发表时间：
2015-03
影响因子：
2.7
通讯作者：
Lu Li;Liusheng Huang;Wei Yang;Xiaohui Yao;An Liu
中科院分区：
文献类型：
--
作者：
Lu Li;Liusheng Huang;Wei Yang;Xiaohui Yao;An Liu
LOF是一种基于密度的离群点检测方法，近年来受到广泛关注。由于LOF运行的数据通常分散在多个参与者之间，并且由于法律的或道德的考虑，没有人愿意透露他的敏感信息，因此设计一个保护隐私的LOF离群点检测算法是很重要的。然而，这是一个困难的问题，因为参与者需要在不学习这些对象的信息的情况下找到对象与其k-最近邻（k-NN）之间的最大距离。在本文中，我们提出了一个有效的协议保护隐私的LOF离群检测。我们首先采用一个洗牌协议来排列不同参与者所拥有的距离向量。然后，我们设计了一个安全的选择方法，以获得gambledk-NN指数和份额的k-距离给定的对象。对于每个对象，我们利用所有对象的k-距离来构造一个向量，在此基础上再次执行置换协议以获得新的k-距离份额。最后，选择对应于混淆的k-NN指标的份额作为期望结果。我们的协议确保了所有的中间体之间共享多个参与者，从而避免信息泄漏。此外，我们的协议是有效的，因为我们证明了我们的协议的计算和通信的复杂性是有界的。
LOF is a well-known approach for density-based outlier detection and has received much attention recently. It is important to design a privacy-preserving LOF outlier detection algorithm as the data on which LOF runs is typically spilt among multiple participants and no one is willing to disclose his sensitive information due to legal or moral considerations. This is, however, a hard problem since participants need to find the maximum one of the distances between an object and itsk-Nearest Neighbors (k-NN) without learning the information of these objects. In this paper, we propose an efficient protocol for privacy-preserving LOF outlier detection. We first employ a shuffle protocol to permute the distance vectors owned by different participants. Then, we design a secure selection method to obtain the garbledk-NN indexes and shares ofk-distance for given objects. For each object, we make use of thek-distance of all objects to construct a vector, based on which the permute protocol is executed again to obtain new shares ofk-distance. Finally, the shares corresponding to the garbledk-NN indexes are selected as the expected result. Our protocol ensures that all the intermediates are shared between multiple participants and thus avoid information leaking. In addition, our protocol is efficient as we prove that the computation and communication complexity of our protocol is bounded by.