Privacy-preserving collaborative data mining

Data collection is a necessary step in data mining process. Due to privacy reasons, collecting data from different parties becomes difficult. Privacy concerns may prevent the parties from directly sharing the data and some types of information about the data. How multiple parties collaboratively conduct data mining without breaching data privacy presents a challenge. The objective of this paper is to provide solutions for privacy-preserving collaborative data mining problems. In particular, we illustrate how to conduct privacy-preserving naive Bayesian classification which is one of the data mining tasks. To measure the privacy level for privacy- preserving schemes, we propose a definition of privacy and show that our solutions preserve data privacy.     

水平划分数据的私密保持序贯模式挖掘

研究了以下情况下的私密保持序贯模式挖掘：(1)多方参与；(2)每方均有自己的私有数据集；(3)要求在这多个水平划分的私有数据集的并集上多方合作挖掘序贯模式，同时各方均不向其他方泄露自己的私有数据信息。利用可交换加密技术和同态加密技术，提出一个新颖的基于安全多方计算的私密保持序贯模式挖掘算法。     

Privacy-preserving distributed association rule mining via semi-trusted mixer

Distributed data mining applications, such as those dealing with health care, finance, counter-terrorism and homeland defence, use sensitive data from distributed databases held by different parties. This comes into direct conflict with an individual’s need and right to privacy. In this paper, we come up with a privacy-preserving distributed association rule mining protocol based on a new semi-trusted mixer model. Our protocol can protect the privacy of each distributed database against the coalition up to n − 2 other data sites or even the mixer if the mixer does not collude with any data site. Furthermore, our protocol needs only two communications between each data site and the mixer in one round of data collection.     

隐私保护数据挖掘研究进展

近年来隐私保护数据挖掘已经成为数据挖掘的研究热点, 并取得了丰富的研究成果。但是, 随着移动通信、嵌入式、定位等技术的发展与物联网、位置服务、基于位置的社交网络等应用的出现, 具有个人隐私的信息内容更加丰富, 利用数据挖掘工具对数据进行综合分析更容易侵犯个人隐私。针对新的应用需求, 对隐私保护数据挖掘方法进行深入研究具有重要的现实意义。在分析现有的隐私保护数据挖掘方法分类与技术特点的基础上, 提出现有方法并应用于新型分布式系统架构应用系统、高维数据及时空数据等领域存在的挑战性问题, 并指出了今后研究的方向。     

Large-scale k-means clustering with user-centric privacy-preservation

A k-means clustering with a new privacy-preserving concept, user-centric privacy preservation, is presented. In this framework, users can conduct data mining using their private information by storing them in their local storage. After the computation, they obtain only the mining result without disclosing private information to others. In most cases, the number of parties that can join conventional privacy-preserving data mining has been assumed to be only two. In our framework, we assume large numbers of parties join the protocol; therefore, not only scalability but also asynchronism and fault-tolerance is important. Considering this, we propose a k-mean algorithm combined with a decentralized cryptographic protocol and a gossip-based protocol. The computational complexity is O(log n) with respect to the number of parties n, and experimental results show that our protocol is scalable even with one million parties.     

Hiding co-occurring prioritized sensitive patterns over distributed progressive sequential data streams

Recently, privacy preservation in data mining is an important area of research. It can be done in several ways. Hiding of sensitive patterns is one such important method. In a typical scenario, multiple parties may wish to collaborate to extract interesting global patterns from their integrated data items without revealing their respective local data to each other. Typical applications include finance, medical research, retail sales etc. In certain cases, there may be some patterns whose co-occurrence may lead to revelation of sensitive information. In the present work, hiding of co-occurring sensitive patterns dynamically from distributed progressive databases has been proposed. In addition in the proposed work dynamic priorities have also been coupled, along with the items. This helps to decide which patterns to hide from the set of sensitive patterns. The various partitioning scenarios for distributed databases that have been used include horizontal, vertical and arbitrary. In all such cases, the data is distributive progressive in nature i.e., old data items may become obsolete whereas new data items may be treated as more significant.     

Multi-objective optimization based privacy preserving distributed data mining in Peer-to-Peer networks

This paper proposes a scalable, local privacy-preserving algorithm for distributed Peer-to-Peer (P2P) data aggregation useful for many advanced data mining/analysis tasks such as average/sum computation, decision tree induction, feature selection, and more. Unlike most multi-party privacy-preserving data mining algorithms, this approach works in an asynchronous manner through local interactions and it is highly scalable. It particularly deals with the distributed computation of the sum of a set of numbers stored at different peers in a P2P network in the context of a P2P web mining application. The proposed optimization-based privacy-preserving technique for computing the sum allows different peers to specify different privacy requirements without having to adhere to a global set of parameters for the chosen privacy model. Since distributed sum computation is a frequently used primitive, the proposed approach is likely to have significant impact on many data mining tasks such as multi-party privacy-preserving clustering, frequent itemset mining, and statistical aggregate computation.     

Privacy-preserving Kruskal–Wallis test

Statistical tests are powerful tools for data analysis. Kruskal–Wallis test is a non-parametric statistical test that evaluates whether two or more samples are drawn from the same distribution. It is commonly used in various areas. But sometimes, the use of the method is impeded by privacy issues raised in fields such as biomedical research and clinical data analysis because of the confidential information contained in the data. In this work, we give a privacy-preserving solution for the Kruskal–Wallis test which enables two or more parties to coordinately perform the test on the union of their data without compromising their data privacy. To the best of our knowledge, this is the first work that solves the privacy issues in the use of the Kruskal–Wallis test on distributed data.     

联邦学习中的隐私保护技术研究综述

近年来,联邦学习成为解决机器学习中数据孤岛与隐私泄露问题的新思路。联邦学习架构不需要多方共享数据资源,只要参与方在本地数据上训练局部模型,并周期性地将参数上传至服务器来更新全局模型,就可以获得在大规模全局数据上建立的机器学习模型。联邦学习架构具有数据隐私保护的特质,是未来大规模数据机器学习的新方案。然而,该架构的参数交互方式可能导致数据隐私泄露。目前,研究如何加强联邦学习架构中的隐私保护机制已经成为新的热点。从联邦学习中存在的隐私泄露问题出发,探讨了联邦学习中的攻击模型与敏感信息泄露途径,并重点综述了联邦学习中的几类隐私保护技术：以差分隐私为基础的隐私保护技术、以同态加密为基础的隐私保护技术、以安全多方计算（SMC）为基础的隐私保护技术。最后,探讨了联邦学习中隐私保护中的若干关键问题,并展望了未来研究方向。     

Protecting data privacy in growing neural gas

Growing neural gas is a well-known algorithm in evolutionary computing. It is very effective for training neural networks. However, if the training data for growing neural gas comes from two different parties, privacy concerns may become a hurdle for using this algorithm: Each party may not be willing to reveal her own data to the other, although she wants to collaborate with the other party in running the growing neural gas algorithm on their joint data. In this paper, we propose a privacy-preserving algorithm for growing neural gas with training data from two parties. Our algorithm allows two parties to jointly execute the growing neural gas algorithm without revealing any party’s data to the other. Our algorithm is secure in that it leaks no knowledge about any participant’s data to the other. Experiments on the real-world data show that our algorithm is very efficient.     

Private multiparty sampling and approximation of vector combinations

We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have primarily been studied only in the two-party case. In contrast, this work focuses on multi-party settings.     

Random projection-based multiplicative data perturbation for privacy preserving distributed data mining

This paper explores the possibility of using multiplicative random projection matrices for privacy preserving distributed data mining. It specifically considers the problem of computing statistical aggregates like the inner product matrix, correlation coefficient matrix, and Euclidean distance matrix from distributed privacy sensitive data possibly owned by multiple parties. This class of problems is directly related to many other data-mining problems such as clustering, principal component analysis, and classification. This paper makes primary contributions on two different grounds. First, it explores independent component analysis as a possible tool for breaching privacy in deterministic multiplicative perturbation-based models such as random orthogonal transformation and random rotation. Then, it proposes an approximate random projection-based technique to improve the level of privacy protection while still preserving certain statistical characteristics of the data. The paper presents extensive theoretical analysis and experimental results. Experiments demonstrate that the proposed technique is effective and can be successfully used for different types of privacy-preserving data mining applications.     

Privacy-preserving algorithms for distributed mining of frequent itemsets

Standard algorithms for association rule mining are based on identification of frequent itemsets. In this paper, we study how to maintain privacy in distributed mining of frequent itemsets. That is, we study how two (or more) parties can find frequent itemsets in a distributed database without revealing each party’s portion of the data to the other. The existing solution for vertically partitioned data leaks a significant amount of information, while the existing solution for horizontally partitioned data only works for three parties or more. In this paper, we design algorithms for both vertically and horizontally partitioned data, with cryptographically strong privacy. We give two algorithms for vertically partitioned data; one of them reveals only the support count and the other reveals nothing. Both of them have computational overheads linear in the number of transactions. Our algorithm for horizontally partitioned data works for two parties and above and is more efficient than the existing solution.     

Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets

Finding the nearest k objects to a query object is a fundamental operation for many data mining algorithms. With the recent interest in privacy, it is not surprising that there is strong interest in k-NN queries to enable clustering, classification and outlier-detection tasks. However, previous approaches to privacy-preserving k-NN have been costly and can only be realistically applied to small data sets. In this paper, we provide efficient solutions for k-NN queries for vertically partitioned data. We provide the first solution for the L _∞ (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving L _∞ by providing a practical approach to the Yao’s millionaires problem with more than two parties. This is based on a pragmatic and implementable solution to Yao’s millionaires problem with shares. We also provide privacy-preserving algorithms for combinations of local metrics into a global metric that handles the large dimensionality and diversity of attributes common in vertically partitioned data. To manage very large data sets, we provide a privacy-preserving SASH (a very successful data structure for associative queries in high dimensions). Besides providing a theoretical analysis, we illustrate the efficiency of our approach with an empirical evaluation.     

量化关联规则的隐私保持挖掘方法

根据数据库中量化属性值和分类属性值数量的不同,分别提出了基于布尔关联规则的量化关联规则隐私保持挖掘方法和基于部分变换机制的量化关联规则隐私保持挖掘方法。对于每一种方法都进行了隐私度和正确度分析,并通过实验证明了其正确性和可行性。     

FRAPP: a framework for high-accuracy privacy-preserving mining

To preserve client privacy in the data mining process, a variety of techniques based on random perturbation of individual data records have been proposed recently. In this paper, we present FRAPP, a generalized matrix-theoretic framework of random perturbation, which facilitates a systematic approach to the design of perturbation mechanisms for privacy-preserving mining. Specifically, FRAPP is used to demonstrate that (a) the prior techniques differ only in their choices for the perturbation matrix elements, and (b) a symmetric positive-definite perturbation matrix with minimal condition number can be identified, substantially enhancing the accuracy even under strict privacy requirements. We also propose a novel perturbation mechanism wherein the matrix elements are themselves characterized as random variables, and demonstrate that this feature provides significant improvements in privacy at only a marginal reduction in accuracy. The quantitative utility of FRAPP, which is a general-purpose random-perturbation-based privacy-preserving mining technique, is evaluated specifically with regard to association and classification rule mining on a variety of real datasets. Our experimental results indicate that, for a given privacy requirement, either substantially lower modeling errors are incurred as compared to the prior techniques, or the errors are comparable to those of direct mining on the true database. A partial and preliminary version of this paper appeared in the Proc. of the 21st IEEE Intl. Conf. on Data Engineering (ICDE), Tokyo, Japan, 2005, pgs. 193–204.     

A semi-supervised privacy-preserving clustering algorithm for healthcare

With the proliferation of healthcare data, the cloud mining technology for E-health services and applications has become a hot research topic. While on the other hand, these rapidly evolving cloud mining technologies and their deployment in healthcare systems also pose potential threats to patient’s data privacy. In order to solve the privacy problem in the cloud mining technique, this paper proposes a semi-supervised privacy-preserving clustering algorithm. By employing a small amount of supervised information, the method first learns a Large Margin Nearest Cluster metric using convex optimization. Then according to the trained metric, the method imposes multiplicative perturbation on the original data, which can change the distribution shape of the original data and thus protect the privacy information as well as ensuring high data usability. The experimental results on the brain fiber dataset provided by the 2009 PBC demonstrated that the proposed method could not only protect data privacy towards secure attacks, but improve the clustering purity.     

一种保护原始数据的多属性值分类挖掘算法

针对基于随机响应的隐私保护分类挖掘算法仅适用于原始数据属性值是二元的问题,设计了一种适用于多属性值原始数据的隐私保护分类挖掘算法。算法分为两个部分:a)通过比较参数设定值和随机产生数之间的大小,决定是否改变原始数据的顺序,以实现对原始数据进行变换,从而起到保护数据隐私性的目的;b)通过求解信息增益比例的概率估计值,在伪装后的数据上构造决策树。     

基于隐私保护的关联规则挖掘研究

鉴于现行数据隐私问题日益严重,如何防止数据挖掘过程中隐私信息的泄漏,是一个重要的研究议题.针对关联规则挖掘技术,从数据挖掘资源共享方面探讨隐私信息的保护,提出数据汇总概念的保护机制,将欲公开的内容隐藏到汇总内容中.此机制不仅确保公开内容的隐私,还可以从汇总内容中获取有用信息,从而在隐私保护和知识获取间取得平衡.     

More than modelling and hiding: towards a comprehensive view of Web mining and privacy

Over the last decade, privacy has been widely recognised as one of the major problems of data collections in general and the Web in particular. This concerns specifically data arising from Web usage (such as querying or transacting) and social networking (characterised by rich self-profiling including relational information) and the inferences drawn from them. The data mining community has been very conscious of these issues and has addressed in particular the inference problems through various methods for “privacy-preserving data mining” and “privacy-preserving data publishing”. However, it appears that these approaches by themselves cannot effectively solve the privacy problems posed by mining. We argue that this is due to the underlying notions of privacy and of data mining, both of which are too narrow. Drawing on notions of privacy not only as hiding, but as control and negotiation, as well as on data mining not only as modelling, but as the whole cycle of knowledge discovery, we offer an alternative view. This is intended to be a comprehensive view of the privacy challenges as well as solution approaches along all phases of the knowledge discovery cycle. The paper thus combines a survey with an outline of an agenda for a comprehensive, interdisciplinary view of Web mining and privacy.