In this paper we propose a clustering process which uses a multi-objective evolution to select a set of diverse clusterings. The selected clusterings are then combined using a consensus method. This approach is compared to a clustering process where no selection is applied. We show that careful selection of input ensemble members can improve the overall quality of the final clustering. Our algorithm provides more stable clustering results and in many cases overcomes the limitations of base algorithms.
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 [
Ensemble methods have been successfully applied in
supervised learning [
The problem is how to obtain a final clustering π∗ = {C1∗,C2∗, . . . ,CK∗ }, 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 [
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 [
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 [
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 [
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 [
Subsequently, in 2007 Handl and Knowles published a
Pareto-based multi-objective evolutionary clustering
algorithm called MOCK [
As a Multi-Objective Evolutionary Algorithm (MOEA),
MOCK employs the Pareto Envelope-based Selection
Algorithm version 2 (PESA-II) [
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. [
Faceli et al. [
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 [
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 [
k + 2 · n (1) where Ln(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. [
min i, j∈{1,...,k} i6= j
( c¯i − c¯j ) fSD = α · Scat(k) + Dis(k)
Then we can define the SD validity index as follows:
where α should be a weighting factor equal to Dis(cmax)
with cmax being the maximum number of clusters [
= Dis(k) · (Scat(k) + 1)
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 [
As an evolutionary algorithm we use NSGA-II [
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 h2, √ni. 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(n3)) and might produce noisy clustering in case of very diverse base clusterings. σ (X ) ∈ Rm with m being the number of dataset dimensions. Variance for a dimension d is defined as: σ d = kσ (X )k = 1 ∑n xid − x¯d 2 n i=1 s m ∑(σ d )2 i=1 The total separation is given by:
Dis(k) = Dmax ∑k k ∑ Dmin i=1 j=1 c¯i − c¯j !−1 where Dmax is the maximum distance and Dmin is the minimum distance between cluster centers (c¯i) and k is the number of clusters.
Dmax =
max
i, j∈{1,...,k}
i6= j
( c¯i − c¯j )
To evaluate clustering quality we use NMI1
(Normalized Mutual Information) [
Most of the datasets used in these experiments come from
the Fundamental Clustering Problems Suite [
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 1There are several versions of this evaluation method, sometimes it is referred as NMIsqrt
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. 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 selection 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 (GACˇ R) grant 13-17187S.