A Study of Some Privacy-Preserving Clustering Schemes

Clustering is one of the most useful techniques to do some data analysis. But the conventional way to perform clustering usually offends one’s privacy. In the era of digital information, privacy is a very important concern in our daily life. To preserve one’s privacy, we exploit several privacy-preserving clustering schemes in this thesis. In the beginning, introduction to clustering, distributed clustering, and privacy-preserving clustering schemes will be given in order. And then, two major schemes, privacy-preserving k-means clustering and privacy-preserving hierarchical clustering, are illustrated in details. We implement these algorithms and perform experiments with both simulated ones and realistic data sets to learn the characteristics of each privacy-preserving clustering algorithm and evaluate the feasibility and usefulness of privacy-preserving clustering schemes.Chapter 1 Introduction 1hapter 2 Related Work 5hapter 3 Distributed Clustering 9.1 Distributed K-Means Clustering 10.1.1 K-Means Clustering 10.1.2 Distributed K-Means Clustering 12.2 Distributed Hierarchical Clustering 16.2.1 Hierarchical Clustering 16.2.2 Modified Hierarchical Clustering 18.2.3 Distributed Hierarchical Clustering 20hapter 4 Privacy-Preserving Clustering 23.1 Preliminaries 23.1.1 Paillier Cryptosystem 23.1.2 Secure Weighted Average Protocol 26.1.3 Permute Share 28.1.4 Secure Scalar Product 29.1.5 Yao’s Millionaires’ Protocol 31.2 Privacy-Preserving K-Means Clustering 33.3 Privacy-Preserving Hierarchical Clustering 35.3.1 Share Centers and Weights 36.3.2 Construct the Proximity Matrix 38.3.3 Find the Nearest Pair 41.3.4 Merge the Nearest Pair 43hapter 5 System Implementation 47.1 Interface 47.2 Implementation Detail 50.3 Experiment Results 51.3.1 Characteristics of Clustering Algorithms 51.3.2 Distributed Clustering Algorithm Comparisons 55.3.3 Privacy-Preserving Clustering Algorithm Comparisons 59hapter 6 Conclusions and Future Work 63eference 6