Clustering is a popular technique that can be used to reveal patterns in data or as a preprocessing step in data analysis. Clustering tends to group similar objects into groups that are called clusters and to place dissimilar objects into different clusters. Its application domains include data mining, information retrieval, bioinformatics, image processing and many others.
Many clustering algorithms have been introduced so far, an extensive overview of clustering techniques can be found in [1]. Since we have the No Free Lunch Theorem [36], which states that there is no single, supreme algorithm that would optimally run on all datasets, it is complicated for a user to decide which algorithm to choose.
Ensemble methods have been successfully applied in supervised learning [25] and similar attempts appeared in the unsupervised learning area [32], [14], [34]. Cluster ensemble methods should eliminate the drawbacks of individual methods by combining multiple solutions into one final clustering.
The main objective of clustering ensembles is to combine multiple clusterings into one, preferably high-quality solution.
Let X = {x 1 , x 2 , . . . , x n } be a set of n data points, where each x i ∈ X is represented by a vector of d attributes. A cluster ensemble is defined as Π = {π 1 , π 2 , . . . , π m } with m clusterings. Each base clustering π i consists of a set of clusters π i = {C i 1 ,C i 2 , . . . ,C i k i }, such that ∪ k i j=1 C i j = X, where k i is the number of clusters in a given ensemble member (it does not have to be the same for all members).
where K is the number of clusters in the result and π * summarizes the information from ensemble Π.
The process consists of two major steps. Firstly, we need to generate a set of clustering solutions and secondly we need ti combine the information from these solutions. A typical result of the ensemble process is a single clustering. It has been shown in supervised ensembles that the best results are achieved when using a set of predictors whose errors are dissimilar [25]. Thus it is desirable to introduce diversity between ensemble members.
Several approaches have been used to initialize clustering solutions in order to create an ensemble.
• Homogeneous ensembles: Base clusterings are created using repeated runs of a single clustering algorithm. This is quite a popular approach, repeated runs of k-means with random center initialization have been used in [14]. When using k-means the number of clusters is typically fixed to √ n , where n is the size of the dataset [22].
• Varying k: Repeated runs of k-means with random initialization and k [15], a golden standard is using k in the range from 2 to √ n.
• Random subspacing An ensemble is created from base clusterings that use different initial data. This could be achieved by projecting data onto different subspaces [13], [16] choosing different subsets of features [32], [37], or using data sampling techniques [10].
• Heterogeneous ensembles: Diversity of solutions is introduced by applying different algorithms on the same dataset.
Having multiple clusterings in an ensemble, many functions have been proposed to derive a final clustering.
When only one solution is considered as the result, it is usually referred as a consensus function, unlike meta clustering where the output is a set of multiple clusterings [6].
There are several approaches as to how to represent information contained in base clusterings, some use matrices while others use graph representation.
• Pairwise similarities: A pairwise similarity matrix is created and afterwards a clustering algorithm (e.g. hierarchical agglomerative clustering) is applied to group together items that were most frequently together in the same cluster in all the base clusterings [14]. the Cluster-based Similarity Partitioning Algorithm (CSPA) from Strehl and Ghosh [32] uses METIS [24] for partitioning a similarity matrix into k components.
• Feature-based approach: The ensemble problem is formulated as categorical data clustering. For each data point an m-dimensional vector containing labels in base clusterings is created. The goal is to find a partition π * which summarizes the information gathered from the partitions Π [28], [33], [4].
• Graph based: Many methods use graph representation for capturing relationships between base clusterings. Strehl and Ghosh [32] also proposed the HyperGraph-Partitioning Algorithm (HGPA), where vertices correspond to data points and a hyperedge represents clusters. Another approach chooses CO-MUSA [27] which increases the weight of the edge for each occurrence of data pairs in the same cluster. Afterwards the nodes are sorted by the attachment score, which is defined as the ratio between the sum of the node's weights and its number of incident edges. The nodes with the highest attachment score are then used as a foundation for new clusters. This approach is relatively fast to compute, however it might fail to capture complex relationships between very diverse clusterings.
Multi-objective clustering usually optimizes two objective functions. Using more than a few objectives is not usual because the whole process of optimization becomes less effective.
The first multi-objective evolutionary clustering algorithm was introduced in 2004 by Handl and Knowles [18] and is called VIENNA (the Voronoi Initialized Evolutionary Nearest-Neighbour Algorithm).
Subsequently, in 2007 Handl and Knowles published a Pareto-based multi-objective evolutionary clustering algorithm called MOCK [19] (Multi-Objective Clustering with automatic K-determination). Each individual in MOCK is represented as a directed graph which is then translated into a clustering. The genotype is encoded as an array of integers whose length is same as the number of instances in the dataset. Each number is a pointer to another instance (an edge in the graph), since it is connected to the instance at a given index. This easily enables the application of mutation and crossover operations.
As a Multi-Objective Evolutionary Algorithm (MOEA), MOCK employs the Pareto Envelope-based Selection Algorithm version 2 (PESA-II) [7], which keeps two populations, an internal population of fixed size and a larger external population which is exploited to explore good solutions. Two complementary objectives, deviation and connectivity, are used as objectives in the evolutionary process.
A clear disadvantage of MOCK is its computation complexity, which is a typical characteristic of evolutionary algorithms. Nevertheless, the computation time spent on MOCK should result in high-quality solutions. Faceli et al. [12] reported that for some high-dimensional data it is not guaranteed that the algorithm will complete, unless the control front distribution has been adjusted for the given data set.
Faceli et al. [12] combined a multi-objective approach to clustering with ensemble methods and the resulting algorithm is called MOCLE (Muli-Objective Clustering Ensemble Algorithm). The objectives used in the MOCLE algorithm are the same as those used in MOCK [19]: deviation and connectivity. Unlike MOCK, in this case the evolutionary algorithm used is NSGA-II [9].
There are many ways to produce a final consensus, nonetheless in this work we focus on the selection of highquality and diverse clusterings.
In order to optimize ensemble member selection, we apply a multi-objective optimization. The whole process is shown in Fig. 1. In our previous work [3] we have shown that introducing multiple objectives into the clustering process can improve the quality of clustering, specifically using the Akaike information criterion (AIC) [2] (or BIC [31]) with another criterion leads to better results. The second criterion is typically based on computing a ratio between cluster compactness and the sum of distances between cluster centres.
AIC is typically used in supervised learning when trying to estimate model error. Essentially it attempts to estimate the optimism of the model and then add it to the error [20]:
where L n (k) is the maximum likelihood of a model with k parameters based on a sample of size n.
The SD index was introduced in 2000 by Halkidi et al. [17] and it is based on concepts of average cluster scattering and total separation of clusters which were previously used by Rezaee et al. [29] for evaluation of fuzzy clusterings. The average scattering is defined as:
where x is the norm of a vector, ci is the centroid of the i-th cluster, σ (X)
is the variance of the input dataset.
σ (X) ∈ R m with m being the number of dataset dimensions. Variance for a dimension d is defined as:
The total separation is given by:
where D max is the maximum distance and D min is the minimum distance between cluster centers ( ci ) and k is the number of clusters.
Then we can define the SD validity index as follows:
where should be a weighting factor equal to Dis(c max ) with c max being the maximum number of clusters [17]. This makes perfect sense for fuzzy clustering (as was proposed in [29]), however it is rather unclear how to compute c max in the case of crisp clustering, when c max k without running another clustering with c max as the requested number of clusters. Nonetheless, [17] mentions that "SD proposes an optimal number of clusters almost irrespective of c max , the maximum number of clusters", thus we consider the special case where c max = k:
The idea of minimizing inner cluster distances and maximizing distances between cluster centres it not really new. In fact most of the clustering objective functions use this idea. Instead of the SD index we could have used C-index [21], Calinski-Harabasz Index [5], Davies-Bouldin [8] or Dunn's index [11], just to name a few. Each of these indexes might perform better on some dataset, however it is out of scope of this paper to compare which combination would be better. We considered
As an evolutionary algorithm we use NSGA-II [9] while using only the mutation operator and a relatively small population (see Table 2). Each individual in the population contains a configuration of a clustering algorithm. For this experiment we used only the basic k-means [26] algorithm with random initialization. The number of clusters k is the only parameter that we change during the evolutionary process. For k we used a constraint in order to keep the number of clusters within reasonable boundaries. For all test datasets we used the interval 2, √ n . In order to evaluate the effect of Pareto optimal solutions selection for the ensemble bagging process, we compare two strategies for generating base clusterings. The first one generates 10 k-means clusterings with random initialization with k within the interval 2, √ n . The second method uses multi-objective evolution of clusterings where each individual represents a k-means clustering.
As a consensus function we use either a graph based COMUSA algorithm or a hierarchical agglomerative clustering of the co-association matrix. Both approaches have their drawbacks, the COMUSA algorithm is locally consistent, however fails to integrate the information contained in different base clusterings, thus final clustering does not overcome limitations of base clustering algorithms. The latter could be very slow on larger datasets (complexity O(n 3 )) and might produce noisy clustering in case of very diverse base clusterings. To evaluate clustering quality we use NMI 1 (Normalized Mutual Information) [32]. NMI has proved to be a better criterion than the Adjusted Rand Index (ARI) for the evaluation of datasets with apriori known labels. However it does not capture noise in clusters (which does not occur in the case of traditional k-means), which might be introduced by some consensus methods. Another limitation of these evaluation metrics is apparent from Figure 6, where clustering with obvious 50% assignment error gets lowest possible score. Both indexes do not penalize correctly higher number of clusters, thus algorithms producing many small clusters will be preferred by these objectives.
Most of the datasets used in these experiments come from the Fundamental Clustering Problems Suite [35]. We have intentionally chosen low dimensional data in order to be able to visually evaluate the results. An overview of the datasets used can be found in Table 1.
As objectives during the multi-objective evolution we used AIC and SD index in all cases. The advantage is combination of two measures that are based on very different grounds. We tried using Deviation and Connectivity, as it was proposed by Handl [19] (and later used by [12]), but for all tested datasets, our approach was better or at least comparable with these objectives.
In the case of the COMUSA approach, the multiobjective selection either improved the final NMI score or it was comparable with the random selection. There were only a few exceptions, especially in case of compact datasets like the 9 diamond dataset which contains a specific regular pattern that is unlikely to appear in any realworld dataset (see Table 3). The number of clusters produces by COMUSA approach was usually higher than the correct number of clusters and clustering contains many nonsense clusters. Despite these facts the NMI score does not penalize these properties appropriately.
Agglomerative clustering of the co-association matrix despite its high computational requirement provide pretty good results. Nonetheless in the case of the chainlink dataset there is over 50% improvement in NMI. It is important to note, that for HAC-RAND and HAC-MO we did not provide the information about the correct number of clusters. Still these methods manages to estimate number of clusters or at least provide result that is very close to the number of supervised classes. 4: NMI sqrt score from the clustering of various artificial datasets. As a consensus method, hierarchical agglomerative clustering (with complete linkage) of coassociation matrix is used. In the case of HAC-RAND we run 10 independent k-means clusterings with a random number of clusters (between 2 and √ n), then form a co-association matrix and finally run agglomerative clustering of the matrix. HAC-RAND works in very similar manner, but instead of the first step a multi-objective evolution of k-means is performed. 10 dominating solutions are selected and the rest of the algorithm is the same.
During our experiments we have shown that careful selection of clusterings for the ensemble process can significantly improve overall clustering quality for non-trivial datasets (measured by NMI).
It is interesting that non-spherical clusters could be discovered by consensus function when agglomerative hierarchical clustering is used (compare Fig. 2 and 3).
Using a multi-objective optimization for clustering se- lection improved the overall quality of clustering results, however ensemble methods might produce noisy clustering with a higher evaluation score. Noisy clusterings are hard to measure with current evaluation metrics, therefore it might be beneficial to include an unsupervised score in the results. In further research we would like to examine the process of selecting optimal objectives for each dataset.
The research reported in this paper was supported by the Czech Science Foundation (GA ČR) grant 13-17187S.