Privacy-Preserving Clustering on Distributed Databases: A Review and Some Contributions
---
paper_title: Parallel Database Systems : The Future of High Performance Database Processing

paper_content:

Parallel database machine architectures have evolved from the use of exotic hardware to a software parallel dataflow architecture based on conventional shared-nothing hardware. These new designs provide impressive speedup and scaleup when processing relational database queries. This paper reviews the techniques used by such systems, and surveys current commercial and research systems.
---
paper_title: Distributed data clustering can be efficient and exact

paper_content:

Data clustering is one of the fundamental techniques in scientific data analysis and data mining. It partitions a data set into groups of similar items, as measured by some distance metric. Over the years, data set sizes have grown rapidly with the exponential growth of computer storage and increasingly automated business and manufacturing processes. Many of these datasets are geographically distributed across multiple sites, e.g. different sales or warehouse locations. To cluster such large and distributed data sets, efficient distributed algorithms are called for to reduce the communication overhead, central storage requirements, and computation time, as well as to bring the resources of multiple machines to bear on a given problem as the data set sizes scale-up. We describe a technique for parallelizing a family of center-based data clustering algorithms. The central idea is to communicate only sufficient statistics, yielding linear speed-up with excellent efficiency. The technique does not involve approximation and may be used orthogonally in conjunction with sampling or aggregation-based methods, such as BIRCH, to lessen the quality degradation of their approximation or to handle larger data sets. We demonstrate in this paper that even for relatively small problem sizes, it can be more cost effective to cluster the data in-place using an exact distributed algorithm than to collect the data in one central location for clustering.
---
paper_title: Privacy-preserving distributed k-means clustering over arbitrarily partitioned data

paper_content:

Advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. Data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. However, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.Distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. Privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. Our paper makes two contributions in privacy-preserving data mining. First, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. Second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.
---
paper_title: How to play any mental game, or a completeness theorem for protocols with honest majority.

paper_content:

Permission to copy without fee all or part of this material is granted provided that the copies are not made or Idistributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machimery. To copy otherwise, or to republish, requires a fee and/or specfic permission. correctly run a given Turing machine hi on these 2;‘s while keeping the maximum possible pniracy about them. That is, they want to compute Y~(~l,..., 2,) without revealing more about the Zi’s than it is already contained in the value y itself. For instance, if M computes the sum of the q’s, every single player should not be able to learn more than the sum of the inputs of the other parties. Here A4 ma.y very well be a probabilistic Turing machine. In this case, all playen want to agree on a single string y, selected with the right probability distribution, as M’s output.
---
paper_title: A Short Introduction to Boosting

paper_content:

Boosting is a general method for improving the accuracy of any given learning algorithm. This short overview paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting, including an explanation of why boosting often does not suffer from overfitting as well as boosting’s relationship to support-vector machines. Some examples of recent applications of boosting are also described.
---
paper_title: Parallel implementation of self-organizing maps

paper_content:

This chapter focuses on parallel implementations of the Self-Organizing Map (SOM) featuring different levels of parallelism. The basic arithmetic-logical operations of SOM are first reviewed for a consideration of implementation issues such as number precision, memory consumption and time complexity. Mapping involves network, training set, neuron and weight parallelism. Examples of the weight and neuron parallel mappings are given for abstract platforms to conduct general principles. Neuron parallel mapping is considered in great detail as it is the most commonly used approach. A review of implementations is given from supercomputers to VLSI (Very Large Scale Integration) chips with criteria for performance comparison.
---
paper_title: PicSOM – content-based image retrieval with selforganizing maps

paper_content:

We have developed a novel system for content-based image retrieval in large, unannotated databases. The system is called PicSOM, and it is based on tree structured self-organizing maps (TS-SOMs). Given a set of reference images, PicSOM is able to retrieve another set of images which are similar to the given ones. Each TS-SOM is formed with a diAerent image feature representation like color, texture, or shape. A new technique introduced in PicSOM facilitates automatic combination of responses from multiple TS-SOMs and their hierarchical levels. This mechanism adapts to the user’s preferences in selecting which images resemble each other. Thus, the mechanism implements a relevance feedback technique on content-based image retrieval. The image queries are performed through the World Wide Web and the queries are iteratively refined as the system exposes more images to the user. ” 2000 Elsevier Science B.V. All rights reserved.
---
paper_title: Privacy-preserving clustering with distributed EM mixture modeling

paper_content:

Privacy and security considerations can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery can alleviate this problem. We present a technique that uses EM mixture modeling to perform clustering on distributed data. This method controls data sharing, preventing disclosure of individual data items or any results that can be traced to an individual site.
---
paper_title: Distributed Clustering Using Collective Principal Component Analysis

paper_content:

This paper considers distributed clustering of high-dimensional heterogeneous data using a distributed principal component analysis (PCA) technique called the collective PCA. It presents the collective PCA technique, which can be used independent of the clustering application. It shows a way to integrate the Collective PCA with a given off-the-shelf clustering algorithm in order to develop a distributed clustering technique. It also presents experimental results using different test data sets including an application for web mining.
---
paper_title: Mapping nominal values to numbers for effective visualization

paper_content:

Data sets with a large number of nominal variables, some with high cardinality, are becoming increasingly common and need to be explored. Unfortunately, most existing visual exploration displays are designed to handle numeric variables only. When importing data sets with nominal values into such visualization tools, most solutions to date are rather simplistic. Often, techniques that map nominal values to numbers do not assign order or spacing among the values in a manner that conveys semantic relationships. Moreover, displays designed for nominal variables usually cannot handle high cardinality variables well. This paper addresses the problem of how to display nominal variables in general-purpose visual exploration tools designed for numeric variables. Specifically, we investigate (1) how to assign order and spacing among the nominal values, and (2) how to reduce the number of distinct values to display. We propose that nominal variables be pre-processed using a distance-quantification-classing (DQC) approach before being imported into a visual exploration tool. In the distance step, we identify a set of independent dimensions that can be used to calculate the distance between nominal values. In the quantification step, we use the independent dimensions and the distance information to assign order and spacing among the nominal values. In the classing step, we use results from the previous steps to determine which values within a variable are similar to each other and thus can be grouped together. Each step in the DQC approach can be accomplished by a variety of techniques. We extended the XmdvTool package to incorporate this approach. We evaluated our approach on several data sets using a variety of evaluation measures.
---
paper_title: Concurrent self-organizing maps for pattern classification

paper_content:

We present a new neural classification model called concurrent self-organizing maps (CSOM), representing a winner-takes-all collection of small SOM networks. Each SOM of the system is trained individually to provide best results for one class only. We have considered two significant applications: face recognition and multispectral satellite image classification. For the first application, we have used the ORL database of 400 faces (40 classes). With CSOM (40 small linear SOMs), we have obtained a recognition score of 91%, while using a single big SOM one obtains a score of 83.5% only! For second application, we have classified the multispectral pixels belonging to a LANDSAT TM image with 7 bands into seven thematic categories. The experimental results lead to the recognition rate Of 95.29% using CSOM (7 circular SOMs), while with a single big SOM, one obtains a 94.31% recognition rate. Simultaneously, CSOM leads to a significant reduction of training time by comparison to SOM.
---
paper_title: Image Segmentation Based on Cluster Ensemble

paper_content:

Image segmentation is a classical problem in the area of image processing, multimedia, medical image, and so on. Although there exist a lot of approaches to perform image segmentation, few of them study the image segmentation by the cluster ensemble approach. In this paper, we propose a new algorithm called the cluster ensemble algorithm (CEA) for image segmentation. Specifically, CEA first obtains two set of segmented regions which are partitioned by EM according to the color feature and the texture feature respectively. Then, it integrates these regions to ksegmented regions based on the similarity measure and the fuzzy membership function. Finally, CEA performs the denoise algorithm on the segmented regions to remove the noise. The experiments show that CEA works well during the process of image segmentation.
---
paper_title: Bagging Predictors

paper_content:

Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does a plurality vote when predicting a class. The multiple versions are formed by making bootstrap replicates of the learning set and using these as new learning sets. Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy. The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.
---
paper_title: Um framework para análise de agrupamento baseado na combinação multi-objetivo de algoritmos de agrupamento

paper_content:

This Thesis presents a framework for exploratory data analysis via clustering techniques. The goal is to facilitate the work of the experts in the data domain. The core of the framework is a multi-objective clustering ensemble algorithm, the MOCLE algorithm, complemented by a method for integrated visualization of a set of partitions. By applying together the ideas of clustering ensemble and multi-objective clustering, MOCLE automatically performs important steps of cluster analysis: run several conceptually different clustering algorithms with various parameter configuration, combine the partitions resulting from these algorithms, and select the partitions with the best trade-offs for different validation measures. MOCLE is a robust approach to deal with different types of structures that can be present in a dataset. It results in a concise and stable set of high quality alternative structures, without the need of previous knowledge about the data or deep knowledge on cluster analysis. Furthermore, in order to facilitate the discovery of more complex structures, MOCLE allows the automatic integration of previous knowledge of a simple structure via their objective functions. Finally, the visualization method proposed allows the simultaneous observation of a set of partitions. This helps in the analysis of MOCLE results.
---
paper_title: Distributed data clustering can be efficient and exact

paper_content:

Data clustering is one of the fundamental techniques in scientific data analysis and data mining. It partitions a data set into groups of similar items, as measured by some distance metric. Over the years, data set sizes have grown rapidly with the exponential growth of computer storage and increasingly automated business and manufacturing processes. Many of these datasets are geographically distributed across multiple sites, e.g. different sales or warehouse locations. To cluster such large and distributed data sets, efficient distributed algorithms are called for to reduce the communication overhead, central storage requirements, and computation time, as well as to bring the resources of multiple machines to bear on a given problem as the data set sizes scale-up. We describe a technique for parallelizing a family of center-based data clustering algorithms. The central idea is to communicate only sufficient statistics, yielding linear speed-up with excellent efficiency. The technique does not involve approximation and may be used orthogonally in conjunction with sampling or aggregation-based methods, such as BIRCH, to lessen the quality degradation of their approximation or to handle larger data sets. We demonstrate in this paper that even for relatively small problem sizes, it can be more cost effective to cluster the data in-place using an exact distributed algorithm than to collect the data in one central location for clustering.
---
paper_title: Relationship-based Clustering and Cluster Ensembles for High-dimensional Data Mining

paper_content:

This dissertation takes a relationship-based approach to cluster analysis of high (1000 and more) dimensional data that side-steps the ‘curse of dimensionality’ issue by working in a suitable similarity space instead of the original feature space. We propose two frameworks that leverage graph algorithms to achieve relationship-based clustering and visualization, respectively. In the visualization framework, the output from the clustering algorithm is used to reorder the data points so that the resulting permuted similarity matrix can be readily visualized in 2 dimensions, with clusters showing up as bands. Results on retail transaction, document (bag-of-words), and web-log data show that our approach can yield superior results while also taking additional balance constraints into account. ::: The choice of similarity is a critical step in relationship-based clustering and this motivates our systematic comparative study of the impact of similarity measures on the quality of document clusters . The key findings of our experimental study are: (i) Cosine, correlation, and extended Jaccard similarities perform comparably; (ii) Euclidean distances do not work well; (iii) graph partitioning tends to be superior to k-means and SOMs especially when balanced clusters are desired; and (iv) performance curves generally do not cross. We also propose a cluster quality evaluation measure based on normalized mutual information and find an analytical relation between similarity measures. ::: It is widely recognized that combining multiple classification or regression models typically provides superior results compared to using a single, well-tuned model. However, there are no well known approaches to combining multiple clusterings. The idea of combining cluster labelings without accessing the original features leads to a general knowledge reuse framework that we call cluster ensembles. We propose a formal definition of the cluster ensemble as an optimization problem. Taking a relationship-based approach we propose three effective and efficient combining algorithms for solving it heuristically based on a hypergraph model. Results on synthetic as well as real data-sets show that cluster ensembles can (i) improve quality and robustness, and (ii) enable distributed clustering, and (iii) speed up processing significantly with little loss in quality.
---
paper_title: Clustering Mixed Numeric and Categorical Data: A Cluster Ensemble Approach

paper_content:

Clustering is a widely used technique in data mining applications for discovering patterns in underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this paper, we propose a novel divide-and-conquer technique to solve this problem. First, the original mixed dataset is divided into two sub-datasets: the pure categorical dataset and the pure numeric dataset. Next, existing well established clustering algorithms designed for different types of datasets are employed to produce corresponding clusters. Last, the clustering results on the categorical and numeric dataset are combined as a categorical dataset, on which the categorical data clustering algorithm is used to get the final clusters. Our contribution in this paper is to provide an algorithm framework for the mixed attributes clustering problem, in which existing clustering algorithms can be easily integrated, the capabilities of different kinds of clustering algorithms and characteristics of different types of datasets could be fully exploited. Comparisons with other clustering algorithms on real life datasets illustrate the superiority of our approach.
---
paper_title: A new method for constructing clustering ensembles

paper_content:

There are some general procedures to generate the clusterings in clustering ensembles. One can apply different algorithms to create different clusterings of the data. Some clustering algorithms like k-means require initialization of parameters. Different initializations can lead to different clustering results. The parameters of a clustering algorithm, such as the number of clusters, can be altered to create different data clusterings. Different versions of the data can also be used as the input to the clustering algorithm, leading to different partitions. In this paper, we propose a new scheme for constructing multiple independent clusterings using additional artificially generated data. Then, we compare our new method with seven general clustering ensemble constructing methods. The experiments show that our approach can achieve higher or comparable performance than the other methods.
---
paper_title: Distributed artificial neural network architectures

paper_content:

The computational cost of training artificial neural network (ANN) algorithms limits the use of large systems capable of processing complex problems. Implementing ANNs on a parallel or distributed platform to improve performance is therefore desirable. This work illustrates a method to predict and evaluate the performance of distributed ANN algorithms by analyzing the performance of the comparatively simple mathematical operations, which are used to construct the ANN. The ANN algorithms are divided into simple components: matrix and vector multiplication, matrix processed through a function, competition in a matrix. These basic operational parts are examined individually and it is demonstrated that the computation processes of distributed neural networks can be derived from the composition of these basic operations. Three popular network architectures are examined: multi-layer perceptrons with back-propagation learning, self-organizing map, and radial basis functions network.
---
paper_title: A survey of neural network ensembles

paper_content:

A neural network ensemble combines a finite number of neural networks or other types of predictors, which are trained simultaneously for a common classification task. Compared with a single neural network, the ensemble is able to efficiently improve the generalization ability of the classifier. The objective of this paper is to introduce existing research work on the neural network ensembles, including effective analysis, general implement steps of ensembles, and traditional technologies for training component neural networks, and also description the applications of it
---
paper_title: A data partition method for parallel self-organizing map

paper_content:

We propose a method to partition training vectors into clusters for a parallel implementation of self-organizing map (SOM) algorithm. The proposed algorithm assigns a cluster to a processor such that, in updating weights, the neighbourhoods of a winning node in a cluster do not overlap the neighboring nodes of some winning nodes in other clusters. It reduces the overheads caused by synchronization (i.e., maintaining coherency) of the weight matrices in the processors since the proposed algorithm allows multiple vectors to find their winning nodes and update weights in parallel. Our experimental results show that an average speedup of 3.15 for a parallel implementation of a four processor simulation.
---
paper_title: Classifier Ensembles: Select Real-World Applications

paper_content:

Broad classes of statistical classification algorithms have been developed and applied successfully to a wide range of real-world domains. In general, ensuring that the particular classification algorithm matches the properties of the data is crucial in providing results that meet the needs of the particular application domain. One way in which the impact of this algorithm/application match can be alleviated is by using ensembles of classifiers, where a variety of classifiers (either different types of classifiers or different instantiations of the same classifier) are pooled before a final classification decision is made. Intuitively, classifier ensembles allow the different needs of a difficult problem to be handled by classifiers suited to those particular needs. Mathematically, classifier ensembles provide an extra degree of freedom in the classical bias/variance tradeoff, allowing solutions that would be difficult (if not impossible) to reach with only a single classifier. Because of these advantages, classifier ensembles have been applied to many difficult real-world problems. In this paper, we survey select applications of ensemble methods to problems that have historically been most representative of the difficulties in classification. In particular, we survey applications of ensemble methods to remote sensing, person recognition, one vs. all recognition, and medicine.
---
paper_title: PicSOM: self-organizing maps for content-based image retrieval

paper_content:

Content-based image retrieval is an important approach to the problem of processing the increasing amount of visual data. It is based on automatically extracted features from the content of the images, such as color, texture, shape and structure. We have started a project to study methods for content-based image retrieval using the self-organizing map (SOM) as the image similarity scoring method. Our image retrieval system, named PicSOM, can be seen as a SOM-based approach to relevance feedback which is a form of supervised learning to adjust the subsequent queries based on the user's responses during the information retrieval session. In PicSOM, a separate tree structured SOM (TS-SOM) is trained for each feature vector type in use. The system then adapts to the user's preferences by returning her more images from those SOMs where her responses have been most densely mapped.
---
paper_title: Methods for Designing Multiple Classifier Systems

paper_content:

In the field of pattern recognition, multiple classifier systems based on the combination of outputs of a set of different classifiers have been proposed as a method for the development of high performance classification systems. In this paper, the problem of design of multiple classifier system is discussed. Six design methods based on the so-called "overproduce and choose" paradigm are described and compared by experiments. Although these design methods exhibited some interesting features, they do not guarantee to design the optimal multiple classifier system for the classification task at hand. Accordingly, the main conclusion of this paper is that the problem of the optimal MCS design still remains open.
---
paper_title: Distributing SOM Ensemble Training using Grid Middleware

paper_content:

In this paper we explore the distribution of training of self-organised maps (SOM) on grid middleware. We propose a two-level architecture and discuss an experimental methodology comprising ensembles of SOMs distributed over a grid with periodic averaging of weights. The purpose of the experiments is to begin to systematically assess the potential for reducing the overall time taken for training by a distributed training regime against the impact on precision. Several issues are considered: (i) the optimum number of ensembles; (ii) the impact of different types of training data; and (iii) the appropriate period of averaging. The proposed architecture has been evaluated in a grid environment, with clock-time performance recorded.
---
paper_title: Concurrent self-organizing maps -a powerfuu artificial neural tool for biometric technology

paper_content:

We investigate the new artificial neural classification model called Concurrent Self-Organizing Maps (CSOM), representing a winner-takes-all collection or small SOM units. We evaluate two significant areas of CSOM applications in Biometric Technology face recognition and speaker recognition. For thc ORL face database of 40 subjects, we obtain a recognition score of 91% using CSOM, while with a single big SOM one yields a score of 71% only! For a speaker database provided by 25 talkers, we obtain 3 recognition score of 92.17% using CSOM, by comparison to SOM that lcads to thc recognition ratc of 79.63%!
---
paper_title: SOM Ensemble-Based Image Segmentation

paper_content:

Image segmentation plays an important role in image analysis and image understanding. In this paper, an image segmentation method based on ensemble of SOM neural networks is proposed, which clusters the pixels in an image according to color and spatial features with many SOM neural networks, and then combines the clustering results to give the final segmentation. Experimental results show that the proposed method performs better than some existing clustering-based image segmentation methods.
---
paper_title: How to play any mental game, or a completeness theorem for protocols with honest majority.

paper_content:

Permission to copy without fee all or part of this material is granted provided that the copies are not made or Idistributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machimery. To copy otherwise, or to republish, requires a fee and/or specfic permission. correctly run a given Turing machine hi on these 2;‘s while keeping the maximum possible pniracy about them. That is, they want to compute Y~(~l,..., 2,) without revealing more about the Zi’s than it is already contained in the value y itself. For instance, if M computes the sum of the q’s, every single player should not be able to learn more than the sum of the inputs of the other parties. Here A4 ma.y very well be a probabilistic Turing machine. In this case, all playen want to agree on a single string y, selected with the right probability distribution, as M’s output.
---
paper_title: A Cluster Ensemble Framework for Large Data sets

paper_content:

Combining multiple clustering solutions is important for obtaining a robust clustering solution, merging distributed clustering solutions, and scaling to large data sets. The combination of multiple clustering solutions within a scalable and robust framework for large data sets is discussed. A scalable framework requires both cluster ensemble creation and merging to be efficient in terms of time and memory complexity. We also introduce the concept of filtering malformed clusters from the ensemble. They result from unfortunate initialization or unbalanced data distribution or noise. Experimental results on real data sets show that this approach will scale and provide cluster partitions which are functionally better or equivalent when compared to clustering all the data at once and clustering solutions contained in the ensemble. We have also compared our algorithm with other ensemble merging and scalable algorithms to point out its strengths and limitations.
---
paper_title: Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions

paper_content:

This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant 'knowledge reuse' framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared mutual information. In addition to a direct maximization approach, we propose three effective and efficient techniques for obtaining high-quality combiners (consensus functions). The first combiner induces a similarity measure from the partitionings and then reclusters the objects. The second combiner is based on hypergraph partitioning. The third one collapses groups of clusters into meta-clusters which then compete for each object to determine the combined clustering. Due to the low computational costs of our techniques, it is quite feasible to use a supra-consensus function that evaluates all three approaches against the objective function and picks the best solution for a given situation. We evaluate the effectiveness of cluster ensembles in three qualitatively different application scenarios: (i) where the original clusters were formed based on non-identical sets of features, (ii) where the original clustering algorithms worked on non-identical sets of objects, and (iii) where a common data-set is used and the main purpose of combining multiple clusterings is to improve the quality and robustness of the solution. Promising results are obtained in all three situations for synthetic as well as real data-sets.
---
paper_title: Relationship-based Clustering and Cluster Ensembles for High-dimensional Data Mining

paper_content:

This dissertation takes a relationship-based approach to cluster analysis of high (1000 and more) dimensional data that side-steps the ‘curse of dimensionality’ issue by working in a suitable similarity space instead of the original feature space. We propose two frameworks that leverage graph algorithms to achieve relationship-based clustering and visualization, respectively. In the visualization framework, the output from the clustering algorithm is used to reorder the data points so that the resulting permuted similarity matrix can be readily visualized in 2 dimensions, with clusters showing up as bands. Results on retail transaction, document (bag-of-words), and web-log data show that our approach can yield superior results while also taking additional balance constraints into account. ::: The choice of similarity is a critical step in relationship-based clustering and this motivates our systematic comparative study of the impact of similarity measures on the quality of document clusters . The key findings of our experimental study are: (i) Cosine, correlation, and extended Jaccard similarities perform comparably; (ii) Euclidean distances do not work well; (iii) graph partitioning tends to be superior to k-means and SOMs especially when balanced clusters are desired; and (iv) performance curves generally do not cross. We also propose a cluster quality evaluation measure based on normalized mutual information and find an analytical relation between similarity measures. ::: It is widely recognized that combining multiple classification or regression models typically provides superior results compared to using a single, well-tuned model. However, there are no well known approaches to combining multiple clusterings. The idea of combining cluster labelings without accessing the original features leads to a general knowledge reuse framework that we call cluster ensembles. We propose a formal definition of the cluster ensemble as an optimization problem. Taking a relationship-based approach we propose three effective and efficient combining algorithms for solving it heuristically based on a hypergraph model. Results on synthetic as well as real data-sets show that cluster ensembles can (i) improve quality and robustness, and (ii) enable distributed clustering, and (iii) speed up processing significantly with little loss in quality.
---
paper_title: Distributing SOM Ensemble Training using Grid Middleware

paper_content:

In this paper we explore the distribution of training of self-organised maps (SOM) on grid middleware. We propose a two-level architecture and discuss an experimental methodology comprising ensembles of SOMs distributed over a grid with periodic averaging of weights. The purpose of the experiments is to begin to systematically assess the potential for reducing the overall time taken for training by a distributed training regime against the impact on precision. Several issues are considered: (i) the optimum number of ensembles; (ii) the impact of different types of training data; and (iii) the appropriate period of averaging. The proposed architecture has been evaluated in a grid environment, with clock-time performance recorded.
---
paper_title: Ensemble clustering with voting active clusters

paper_content:

Clustering is an integral part of pattern recognition problems and is connected to both the data reduction and the data understanding steps. Combining multiple clusterings into an ensemble clustering is critical in many real world applications, particularly for domains with large data sets, high-dimensional feature sets and proprietary data. This paper presents voting active clusters (VACs), a method for combining multiple ''base'' clusterings into a single unified ''ensemble'' clustering that is robust against missing data and does not require all the data to be collected in one central location. In this approach, separate processing centers produce many base clusterings based on some portion of the data. The clusterings of such separate processing centers are then pooled to produce a unified ensemble clustering through a voting mechanism. The major contribution of this work is in providing an adaptive voting method by which the clusterings (e.g., spatially distributed processing centers) update their votes in order to maximize an overall quality measure. Our results show that this method achieves comparable or better performance than traditional cluster ensemble methods in noise-free conditions, and remains effective in noisy scenarios where many traditional methods are inapplicable.
---
paper_title: Mining Local Data Sources For Learning Global Cluster Models

paper_content:

Distributed data mining has been a topic getting more important nowadays as there are many cases where physically sharing of data is probibited, e.g., due to huge data volume or data privacy. In this paper, we are interested in learning a global cluster model by exploring data in distributed sources. A methodology based on periodic model exchange and merge is proposed and applied to hyperlinked Web pages analysis. In addition, we have tested a number of variations of the basic idea, including putting more emphasis on the privacy concern and testing the effect of having different numbers of distributed sources. Experimental results show that the proposed distributed learning scheme is effective with accuracy close to the case with all the data physically shared for the learning.
---
paper_title: Privacy Preserving Data Mining

paper_content:

In this paper we address the issue of privacy preserving data mining. Specifically, we consider a scenario in which two parties owning confidential databases wish to run a data mining algorithm on the union of their databases, without revealing any unnecessary information. Our work is motivated by the need both to protect privileged information and to enable its use for research or other purposes. ::: ::: The above problem is a specific example of secure multi-party computation and, as such, can be solved using known generic protocols. However, data mining algorithms are typically complex and, furthermore, the input usually consists of massive data sets. The generic protocols in such a case are of no practical use and therefore more efficient protocols are required. We focus on the problem of decision tree learning with the popular ID3 algorithm. Our protocol is considerably more efficient than generic solutions and demands both very few rounds of communication and reasonable bandwidth.
---
paper_title: Competitive learning by information maximization: eliminating dead neurons in competitive learning

paper_content:

In this paper, we propose a new information theoretic competitive learning method. In realizing competition, neither the winner-take-all algorithm nor the lateral inhibition is used. Instead, the new method is based upon mutual information maximization between input patterns and competitive units. In maximizing mutual information, the entropy of competitive units is increased as much as possible. This means that all competitive units must equally be used in our framework. Thus, no under-utilized neurons (dead neurons) are generated. We applied our method to a simple artificial data problem and an actual road classification problem. In both cases, experimental results confirmed that the new method can produce the final solutions almost independently of initial conditions, and classification performance is significantly improved.
---
paper_title: Privacy-preserving clustering with distributed EM mixture modeling

paper_content:

Privacy and security considerations can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery can alleviate this problem. We present a technique that uses EM mixture modeling to perform clustering on distributed data. This method controls data sharing, preventing disclosure of individual data items or any results that can be traced to an individual site.
---
paper_title: A framework for privacy-preserving cluster analysis

paper_content:

Releasing person-specific data could potentially reveal sensitive information of individuals. k-anonymization is a promising privacy protection mechanism in data publishing. Though substantial research has been conducted on k-anonymization and its extensions in recent years, few of them consider releasing data for a specific purpose of data analysis. This paper presents a practical data publishing framework for determining a generalized version of data that preserves both individual privacy and information usefulness for cluster analysis. Experiments on real-life data suggest that, by focusing on preserving cluster structure in the generalization process, the cluster quality is significantly better than the cluster quality on the generalized data without such focus. The major challenge of generalizing data for cluster analysis is the lack of class labels that could be used to guide the generalization process. Our approach converts the problem into the counterpart problem for classification analysis where class labels encode the cluster structure in the data, and presents a framework to evaluate the cluster quality on the generalized data.
---
paper_title: Privacy preserving sequential pattern mining in distributed databases

paper_content:

Research in the areas of privacy preserving techniques in databases and subsequently in privacy enhancement technologies have witnessed an explosive growth-spurt in recent years. This escalation has been fueled by the growing mistrust of individuals towards organizations collecting and disbursing their Personally Identifiable Information (PII). Digital repositories have become increasingly susceptible to intentional or unintentional abuse, resulting in organizations to be liable under the privacy legislations that are being adopted by governments the world over. These privacy concerns have necessitated new advancements in the field of distributed data mining wherein, collaborating parties may be legally bound not to reveal the private information of their customers. In this paper, we present a new algorithm PriPSeP ( Pri vacy P reserving SE quential P atterns) for the mining of sequential patterns from distributed databases while preserving privacy. A salient feature of PriPSeP is that due to its flexibility it is more pertinent to mining operations for real world applications in terms of efficiency and functionality. Under some reasonable assumptions, we prove that our architecture and protocol employed by our algorithm for multi-party computation is secure.
---
paper_title: Privacy-preserving distributed clustering using generative models

paper_content:

We present a framework for clustering distributed data in unsupervised and semisupervised scenarios, taking into account privacy requirements and communication costs. Rather than sharing parts of the original or perturbed data, we instead transmit the parameters of suitable generative models built at each local data site to a central location. We mathematically show that the best representative of all the data is a certain "mean" model, and empirically show that this model can be approximated quite well by generating artificial samples from the underlying distributions using Markov Chain Monte Carlo techniques, and then fitting a combined global model with a chosen parametric form to these samples. We also propose a new measure that quantifies privacy based on information theoretic concepts, and show that decreasing privacy leads to a higher quality of the combined model and vice versa. We provide empirical results on different data types to highlight the generality of our framework. The results show that high quality distributed clustering can be achieved with little privacy loss and low communication cost.
---
paper_title: Privacy-preserving distributed k-means clustering over arbitrarily partitioned data

paper_content:

Advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. Data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. However, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.Distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. Privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. Our paper makes two contributions in privacy-preserving data mining. First, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. Second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.
---
paper_title: Privacy-preserving collaborative data mining

paper_content:

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.
---
paper_title: How to generate and exchange secrets

paper_content:

In this paper we introduce a new tool for controlling the knowledge transfer process in cryptographic protocol design. It is applied to solve a general class of problems which include most of the two-party cryptographic problems in the literature. Specifically, we show how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors (p, q), is hidden from either party individually but is recoverable jointly if desired. This can be utilized to give a protocol for two parties with private values i and j to compute any polynomially computable functions f(i,j) and g(i,j) with minimal knowledge transfer and a strong fairness property. As a special case, A and B can exchange a pair of secrets sA, sB, e.g. the factorization of an integer and a Hamiltonian circuit in a graph, in such a way that sA becomes computable by B when and only when sB becomes computable by A. All these results are proved assuming only that the problem of factoring large intergers is computationally intractable.
---
paper_title: A New Privacy-Preserving Distributed k-Clustering Algorithm

paper_content:

We present a simple I/O-efficient k-clustering algorithm that was designed with the goal of enabling a privacy-preserving version of the algorithm. Our experiments show that this algorithm produces cluster centers that are, on average, more accurate than the ones produced by the well known iterative k-means algorithm. We use our new algorithm as the basis for a communication-efficient privacy-preservingk-clustering protocol for databases that are horizontally partitioned between two parties. Unlike existing privacy-preserving protocols based on the k-means algorithm, this protocol does not reveal intermediate candidate cluster centers.
---
paper_title: Private representative-based clustering for vertically partitioned data

paper_content:

This work studies how to construct a representative-based clustering algorithm under the scenario that the dataset is partitioned into at least two sections. One section of the data is owned by Alice while the other is owned by Bob. Both want to compute clusters from the union of the data but do not trust each other. Thus, they do not want the other party to learn anything about their share of the data except what can be inferred from the results. We present a protocol that allows Alice and Bob to carry this task under the k-medoids algorithm. Clustering with medoids (medians or other loss functions) is a more robust alternative that clustering with k-MEANS (the only method for which a privacy preserving protocol is known, but a methods that is statistically biased and statistically inconsistent with very low robustness to noise). Our approach highlights the necessary building blocks for extending our protocol to the family of representative-based clustering algorithms.
---
paper_title: Privacy preserving K-Medoids clustering

paper_content:

Privacy is an important issue in the collaborative data mining since 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. This paper seeks to investigate solutions for privacy- preserving K-Medoids clustering which is one of data mining tasks.
---
paper_title: Privacy-preserving k-means clustering over vertically partitioned data

paper_content:

Privacy and security concerns can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. The key is to obtain valid results, while providing guarantees on the (non)disclosure of data. We present a method for k-means clustering when different sites contain different attributes for a common set of entities. Each site learns the cluster of each entity, but learns nothing about the attributes at other sites.
---
paper_title: A Cluster Ensemble Framework for Large Data sets

paper_content:

Combining multiple clustering solutions is important for obtaining a robust clustering solution, merging distributed clustering solutions, and scaling to large data sets. The combination of multiple clustering solutions within a scalable and robust framework for large data sets is discussed. A scalable framework requires both cluster ensemble creation and merging to be efficient in terms of time and memory complexity. We also introduce the concept of filtering malformed clusters from the ensemble. They result from unfortunate initialization or unbalanced data distribution or noise. Experimental results on real data sets show that this approach will scale and provide cluster partitions which are functionally better or equivalent when compared to clustering all the data at once and clustering solutions contained in the ensemble. We have also compared our algorithm with other ensemble merging and scalable algorithms to point out its strengths and limitations.
---
paper_title: Competitive learning by information maximization: eliminating dead neurons in competitive learning

paper_content:

In this paper, we propose a new information theoretic competitive learning method. In realizing competition, neither the winner-take-all algorithm nor the lateral inhibition is used. Instead, the new method is based upon mutual information maximization between input patterns and competitive units. In maximizing mutual information, the entropy of competitive units is increased as much as possible. This means that all competitive units must equally be used in our framework. Thus, no under-utilized neurons (dead neurons) are generated. We applied our method to a simple artificial data problem and an actual road classification problem. In both cases, experimental results confirmed that the new method can produce the final solutions almost independently of initial conditions, and classification performance is significantly improved.
---

Title: Privacy-Preserving Clustering on Distributed Databases: A Review and Some Contributions

Section 1: Introduction
Description 1: Describe the motivation for privacy-preserving clustering in distributed databases, including challenges with traditional clustering methods and reasons for distributed approaches.

Section 2: Bibliographic review
Description 2: Provide a comprehensive literature review on privacy-preserving data clustering, highlighting key studies and contributions in this area.

Section 3: Data partitioning methods
Description 3: Discuss various methods for partitioning data in distributed environments, including horizontal and vertical partitioning, and their impact on clustering.

Section 4: Classification and cluster ensemble
Description 4: Explain the concept of cluster ensembles and their advantages in producing consistent and reliable clustering results.

Section 5: Combining ensemble results
Description 5: Describe the techniques for combining partial results from different clustering processes to form a unified clustering outcome.

Section 6: Security and privacy preserving data mining
Description 6: Analyze the importance of security and privacy in distributed data mining and review techniques to ensure these aspects during clustering.

Section 7: The partSOM architecture clustering process
Description 7: Present the partSOM architecture's methodology for privacy-preserving clustering in distributed databases, detailing each step in the process.

Section 8: Some contributions to partSOM clustering process
Description 8: Propose enhancements to the partSOM process, including pre-processing stages, pruning algorithms, and the use of covariance matrices to improve data security and reduce information loss.

Section 9: Conclusion
Description 9: Summarize the main points discussed in the paper, including the effectiveness of privacy-preserving clustering methods and potential future research directions.