Privacy-Preserving Clustering on Distributed Databases: A Review and Some Contributions
L. Flavius, Jose Alfredo F. Cost · InTech eBooks · 2011
Clustering is the process of discovering groups within high-dimensional databases, based on similarities, with a minimal knowledge of their structure.Traditional clustering algorithms perform it over centralized databases, however, recent applications require datasets distributed among several sites.Therefore, in distributed database environments, all distributed data must be concentrated on a central site before applying traditional algorithms.There is a series of limitations which hinder the utilization of traditional data mining techniques on distributed databases.The approach commonly taken, the gathering of all distributed databases in a central unit, followed by algorithm application, is strongly criticized, because in these cases, it is important to take into consideration some issues, namely: the possibility of existence of similar data with different names and formats, differences in data structures, and conflicts between one and another database (Zhang et al., 2003).Besides, the unification of all of the registers in a single database may take to the loss of meaningful information, once that statistically interesting values in a local context may be ignored when gathered to other ones in a larger volume.On the other hand, integration of several database in a single location is not suggested when it is composed of very large databases.If a great organization has large disperse databases and needs to gather all the data in order to apply on them data mining algorithms, this process may demand great data transference, which may be slow and costly (Forman & Zhang, 2000).Moreover, any change that may occur in distributed data, for instance inclusion of new information or alteration of those already existing will have to be updated along with the central database.This requires a very complex data updating strategy, with overload of information transference in the system.Furthermore, in some domains such as medical and business areas whereas distributed databases occurs, transferring raw datasets among parties can be insecure because confidential information can be obtained, putting in risk privacy preserving and security requirements.Due to all of these problems related to database integration, research for algorithms that perform data mining in a distributed way is not recent.In the end of the 90s, several researches about algorithms to effectuate distributed data mining started to appear, having been strengthened mainly by the rise of the distributed database managing systems and of the need for an analysis of such data in the way that they were dispersed (DeWitt & Gray, 1992; Souza, 1998).Currently, there is an increasing demand for methods with the ability to www.intechopen.comSelf Organizing Maps -Applications and Novel Algorithm Design 34 process clustering securely that has motivated the development of algorithms to analyze each database separately and to combine the partial results to obtain a final result.An updated bibliography about the matter can be obtained in (Bhaduri et al., 2006).This chapter presents a wide bibliographical review on privacy-preserving data clustering.Initially, different alternatives for data partitioning are discussed, as well as issues related to the utilization of classification and clustering ensembles.Further, some techniques of information merging used in literature to combine results that come from multiple clustering processes are analyzed.Then, are discussed several papers about security and privacy-preserving in distributed data clustering, highlighting the most widely used techniques, as well as their advantages and limitations.Finally, authors present an alternative approach to this problem based on the partSOM architecture and discuss about the confidentiality of the information that is analyzed through application of this approach in geographically distributed database cluster analysis. Bibliographic reviewCurrently, a growing number of companies have strived to obtain a competitive advantage through participation in corporative organizations, as local productive arrangements, cooperatives networks and franchises.Insofar as these companies come together to overcome new challenges, their particular knowledge about the market needs to be shared among all of them.However, no company wants to share information about their customer and transact business with other companies and even competitors, because it is needed to maintain commercial confidentiality and due to local legislation matters.Hence, a large number of studies in this research area, called privacy preserving data mining -where security and confidentiality of data must be maintained throughout the process -have been prompted by the need of sharing information about a particular business segment among several companies involved in this process, avoiding jeopardizing the privacy of its customers.A comprehensive review of these studies is presented below. Data partitioning methodsThere are two distinct situations that demand the need for effecting cluster analysis in a distributed way.The first occurs when the volume of data to be analyzed is relatively great, which demand a considerable computational effort, which sometimes is even unfeasible, to accomplish this task.The best alternative, then, is splitting data, cluster them in a distributed way and unify the results.The second occurs when data is naturally distributed among several geographically distributed units and the cost associated to its centralization is very high.Certain current applications hold databases so large, that it is not possible to keep them integrally in the main memory, even using robust machines.Kantardzic (2002) presents three approaches to solve this problem: i. Storing data in a secondary memory and clustering data subsets separately.Partial results are kept and, in a posterior stage, are gathered to cluster the whole set; ii.Using an incremental clustering algorithm, in which every element is individually brought to the main memory and associated to one of the existing clusters or allocated in a new cluster.The results are kept and the element is discarded, in order to grant space to the other one; iii.Using parallel implementation, in which several algorithms work simultaneously on stored data, increasing efficacy.