Generalized Cluster Aggregation

1 Introduction

Aggregation/Ensemble methods, such as bagging [Breiman, 1996] and boosting, have been widely used in supervised classification to make the results more stable and robust. In fact, data clustering usually suffers from the stability/robustness problems as well because (1) the off-the-shelf clustering methods may discover very different structures in a given set of data because of their different objectives; (2) for a single clustering algorithm, there is no ground truth against which the clustering result can be validated so no cross validation can be performed to tune the parameters; (3) some iterative methods (such as k-means) are highly dependent on its initialization. To improve the quality of the clustering results, the idea of aggregation has also been brought into the field of clustering. The problem of cluster aggregation can be described as: how to make use of a set of different (input) clusterings that have been obtained for a particular data set to find a single final (consensus) clustering that is better than existing clusterings in some sense.

∗The work is partially supported by NSF grants IIS-0546280, DMS-0844513 and CCF-0830659.

During the last decade, many algorithms have been proposed to solve the clustering aggregation problem, e.g., the graph cut method [Fern and Brodley, 2004], informationtheoretic method [Topchy et al., 2003][Strehl et al., 2002], matrix factorization based method [Li et al., 2007], and the Bayesian method [Wang et al., 2009]. Most of the traditional approaches treat each input clustering equally. Recently, some researchers proposed to weigh different clusterings differently when performing cluster aggregation to further improve the diversity and reduce the redundancy in combining the input clusterings [Al-Razgan and Domeniconi, 2006][Li and Ding, 2008][Fern and Lin, 2008]. Now cluster aggregation has been widely applied in many AI areas such as computer vision [Yu et al., 2008], information retrieval [Sevillano et al., 2006] and bioinformatics [Hu and Yoo, 2004].

In this paper, we propose a novel cluster aggregation method based on the cluster connectivity matrix (CCM) [Li et al., 2007], where we aim to find an optimal clustering of the data set whose CCM is consensus with respect to the CCMs of the input clusterings. We use Bregman divergence [Banerjee et al., 2004] to measure the quantity of such consensus and the resulting problem is a convex one which can be efficiently solved. We also formulate the weighted cluster aggregation problem within our framework and derive a block coordinate descent algorithm to solve it. Moreover, we also show that prior knowledge on the cluster structures, such as pairwise constraints which indicate whether a pair of data points belong to the same cluster, can be easily incorporated into the framework. We also derive a novel approach, semisupervised cluster aggregation, to utilize these constraints in cluster aggregation. Finally the experimental results are presented to show the effectiveness of our method.

It is worthwhile to highlight several aspects of our method:

• Unlike some traditional methods which use Euclidean distance or KL divergence to measure matrix consensus, we adopt a much general criterion - Bregman divergence, which can include many commonly used distortion measures as its special cases.
• We extend our framework to formulate the weighted cluster aggregation problem. We show that both the unweighted and weighted problems are convex and can be efficiently solved.
• We also generalize our framework to incorporate pair-

wise constraints, which have widely been used in semisupervised clustering [Basu et al., 2008] but rarely in cluster aggregation, and we show that the resulting problem can be efficiently solved.

2 Unsupervised Cluster Aggregation with Bregman Divergence

Before we go into the details of our framework, some frequently used notations will be introduced. Let X = {x1, x2, · · · , xn} be a set of n data points. Suppose we are given a set of m clusterings (or partitions) P = {P 1, P 2 , · · · ,P m} of the data in X, each partition P i (i = 1, 2, · · · ,m) consists of a set of clusters {πi1, πi2, · · · , πik }, where k is the number of clusters for partition P i and X = ⋃kj=1 πij . Note that the number of clusters k could be different for different clusterings.

2.1 Generalized Cluster Aggregation

We define the connectivity matrix Mi for partition P i as

Let ∇MJ1 = 0 then we can get

Since J1 is convex in M, the solution to Eq.(5) is the global optimum for minimizing J1. Some typical Bregman divergence measures and their corresponding connectivity matrices are summarized in Table 1.

2.2 GeneralizedWeighted Cluster Aggregation

The objective in Eq.(2) treats each partition equally. However, in real world cases we may want to treat different partition with different importance. Therefore we propose to introduce a set of weighting factors {wi}mi=1 subject to ∀ i = 1, 2, · · · ,m, wi ≥ 0, ∑i wi = 1 and minimize the following weighted objective

The problem is not convex with respect in w = (w1, w2, · · · , wm)T and M. We propose a block coordinate descent algorithm above. Keeping one variable fixed, the optimization over the other is a convex problem with a unique solution. This guarantees monotonic decrease of the objective function and convergence to a stationary point.

Fixing w, the resulted problem is similar to the problem of minimizing J1, and we can get the solution by setting

(1)

Thus Mi is a n by n symmetric square matrix which can be used to represent partition P i (in some cases we can also get a soft connectivitymatrixMi such thatMiuv denotes the possibility that xu and xv belong to the same cluster, in this case Miuv ∈ [0, 1]). Then a general way for finding a consensus partition P ∗ is to minimize

where Dφ denotes any separable Bregman divergence as

and

where φ : S ⊆ R → R is a strictly convex function. Therefore ∇MJ1 can be computed as:

We can get that

Fixing M, the problem becomes a linear programming problem

which is a linear programming problem and can be efficiently solved. However, the solution will always be

To avoid such trivial solution, we propose to add one regularization term on J2 and solve the following optimization problem

where λ > 0 is a tradeoff parameter. In this way, we will solve a quadratic programming problem with respect to w when fixing M.

Finally, the generalized weighted cluster aggregation (generalized WCA) algorithm is summarized in Algorithm 1.

Algorithm 1 GENERALIZED WCA

Require: Partitions {P i}mi=1 , precision ϵ

• 1: Construct m cluster aggregation matrix {Mi}mi=1
• 2: Initialize w0 = [1/m, 1/m, · · · , 1/m]T ∈ Rm×1 , M0 = In×n, Δ= +∞, t = 0
• 3: while Δ> ϵ do
• 4: t = t +1
• 5: SolveMt by minimizing ∑i wiDφ(Mt , Mi )
• 6: Solve wt by

7: Compute Δ = ‖Mt

- Mt-1‖F

• 8: end while

3 Semi-supervised Cluster Aggregation with Bregman Divergence

In this section we will consider a novel cluster aggregation setting: in addition to the m partitions, we are also given two sets of pairwise constraintsMand C, such that (xp, xq) ∈ M indicates that xp and xq belong to the same cluster; and (xp, xq) ∈ C denotes they belong to different clusters. Such constraints has widely been used in semi-supervised clustering [Basu et al., 2004][Basu et al., 2008][Wang et al., 2008], however, to the best of our knowledge, there are rarely any works on applying those constraints into cluster aggregation.

3.1 Generalized Cluster Aggregation with Constraints

To incorporate the constraints inMand C into the process of generalized cluster aggregation, we need to solve the following problem:

Clearly, problem (12) is a convex optimization problem with linear constraints. We first rewrite it as

where eki ∈ Rn×1 is a indicator vector with only the kiith element being one and all other elements being zero, and k is the index of the constraint and K is the total number of constraints. bk = 0 if (xkp , xkq ) ∈ C and bk = 1 if (xkp , xkq ) ∈ M. Now we introduce a set of Lagrangian multipliers {αi}ki=1 and construct the Lagrangian for problem (13) as

Then

Let ∂L/∂M = 0 and ∂L/∂αk = 0 then we can get the following equations

At the first glance, this is a differential equation group which is hard to solve, however, as we only consider separable Bregman divergence in this paper, and (ekp )T Mekq = Mkpkq , then we can derive the solution of M as

• For regular elements

• For constrained elements

where we call Mpq as a regular element if (xp, xq) ̸∈Mand (xp, xq) ̸∈ C; we call Mpq as a constrained element if either (xp, xq) ∈ Mor (xp, xq) ∈ C. Comparing with Eq.(5), we can find that the solutions for regular elements inMbetween semi-supervised and unsupervised generalized cluster aggregation are the same; for constrained elements inM, according to Eq.(21), the semi-supervised algorithm just set them to the exact values in their constraints.

3.2 GeneralizedWeighted Cluster Aggregation with Constraints

In the semi-supervised weighted cluster aggregation setting, we aim to solve the following problem

The same as problem (11), although it is not obvious whether problem (22) with respect to w and M jointly, it is convex with respect to them separately with the other one fixed. Therefore we can adopt the block coordinate descent approach to solve the problem. Specifically, when w is fixed, we should solve the optimal M by

Similar to solving problem (12), we can get the solution to the above problem as

• IfMpq is a constrained element, then

• IfMpq is a regular element, thenMpq can be solved by

If M is fixed, then we can solve the optimal w by

which is a convex QP problem and can be efficiently solved. Algorithm 2 summarizes the basic procedure of generalized weighted cluster aggregation (WCA) with constraints.

Algorithm 2 GENERALIZED WCA WITH CONSTRAINTS

Require: Partitions {P i}mi=1 , constraint sets M and C, precision ϵ

• 1: Construct m cluster aggregation matrix {Mi}mi=1
• 2: Initialize w0 = [1/m, 1/m, · · · , 1/m]T ∈ Rm×1 , M0 = In×n, Δ= +∞, t = 0
• 3: while Δ> ϵ do
• 4: t = t +1
• 5: ObtainMt by solving problem (23) with w =wt
• 6: Obtain wt by solving problem (26) withM = Mt
• 7: Compute Δ = ‖Mt - Mt-1‖F
• 8: end while

4 Experiments

In this section we will present a set of experiments to test the effectiveness of the proposed generalized cluster aggregation (GCA) method. The data sets used in our experiments include both synthetic and real world data sets.

4.1 Toy Examples

In this section we construct two synthetic data sets to test the power of the proposed GCA method. Specifically, the two data sets are constructed in the following way:

• Clusters with different shapes. This data set contains five clusters with shapes like letter I (100 points), J (200 points), C (183 points), A (223 points), I (100 points). The distribution of the data set is shown in Fig.1(a).
• Clusters lie in different subspaces. Points with four clusters, each of which exists in just two dimensions with the third dimension being noise [Parsons et al., 2004]. The first two clusters exist in dimensions x and y. The data forms a normal distribution with means 0.6 and -0.6 in dimension x and 0.5 in dimension y, and standard deviations of 0.1. In dimension z, these clusters have μ = 0 and σ = 1. The second two clusters are in dimensions y and z and are generated in the same manner.

We first run K-means on these data sets with randomly initialized cluster centers, and the number of clusters is set to the number of true clusters. The results are shown in Fig.1(b)(e), from which we can see that K-means is totally confused in these cases. We also test the performance of our generalized weighted cluster aggregation (GWCA) algorithm (see section 2.2) under the Euclidean distance, where the 30 base cluster connectivity matrices are obtained by clustering the data set into 20 clusters using K-means with randomly initialized cluster centers. The weight vector is initialized to w = [1/30, 1/30, · · · , 1/30]T ∈ R30×1 . Finally the clustering result is obtained by running K-means on the aggregated cluster connectivity matrix, and the results are shown in Fig.1(c)(f), which clearly illustrate the superiority of our method.

4.2 Experiments on Real World Data Sets

In this section we will present the results of applying our algorithm to a set of real world data sets. First we will describe the basic characteristics of the data sets.

Data Sets

We use totally 14 data sets to evaluate the effectiveness of our proposed. The basic information of these data sets are summarized in Table 2. In the following we will briefly introduce these data sets.

• UCI Data Sets. These data sets are from the UCI Repository, which include Digits 389, Glass, Ionosphere, Iris, Letter IJL, Protein, Soybean, Wine, and Zoo, where Digits 389 is a randomly sampled subset of the handwritten digits 3, 8, 9 from the digits data set, and Letter IJL is a randomly sampled subset containing I, J, L from the letters data set.
• Text Data Sets. These data sets are standard benchmark data sets that commonly used to assess text clustering algorithms. The CSTR data set contains 476 abstracts of technical reports published in the Department of Computer Science at a research university; The Log data set contains 1367 text messages of system log from different desktop machines describing the status of computer components; The Reuters data set is a subset of the Reuters-21578 Text Categorization Test collection contains 10 most frequent categories among the 135 topics; The WebACE data set was from WebACE project, which contains 2340 documents consisting news articles from Reuters new service via the Web in October 1997[Han et al., 1998]; The WebKB data set contains web pages gathered

from university computer science departments. We use a subset containing categories student, faculty, course and project. All the data sets are preprocessed by the rainbow package.

Evaluation Measure

We use Clustering Accuracy to measure the performance of our proposed methods. It discovers the one-to-one relationship between clusters and classes and measures the extent to which each cluster contained data points from the corresponding class. It sums up the whole matching degree between all pair class-clusters. Clustering accuracy can be computed as:

where Ck denotes the k-th cluster in the final results, and Lm is the true m-th class. T(Ck,Lm) is the number of entities which belong to class m are assigned to cluster k. Accuracy computes the maximum sum of T(Ck,Lm) for all pairs of clusters and classes, and these pairs have no overlaps. Greater clustering accuracy means the better clustering performance.

Comparative Methods

Besides our method, we also show the experimental results of some other methods for comparison including

• K-means, which is randomly initialized and the results are averaged over 50 independent runs.
• Spectral Clustering (SC), which is implemented in the same way as in [Yu and Shi, 2003].
• Cluster-based Similarity Partitioning Algorithm (CSPA) and Hyper-Graph-Partitioning Algorithm (HGPA), implemented as in [Strehl et al., 2002].
• Nonnegative Matrix Factorization based Consensus clustering (NMFC), implemented as in [Li et al., 2007].
• Weighted Consensus clustering (WC). The implementation is the same as in [Li and Ding, 2008].

We present the results of our GWCA algorithm and the Semi-Supervised GWCA (SSGWCA) algorithm under the Euclidean and exponential distance (denoted as EGWCA and eGWCA). For the semi-supervised approaches, we first randomly label 10% of the data, and then use these data labels to generate the constraint sets M and C.

Experimental Results

The experimental results are summarized in Table 3, where for our GWCA series methods, we run spectral clustering on the final combined cluster aggregation matrix (i.e., which is used as the similarity matrix). From Table 3 we can clearly observe that our GWCA based algorithm can generate better clusterings, and the results can be further improved with pairwise instance-level constraints.

5 Conclusions

In this paper we propose a general framework for cluster aggregation based on Bregman divergence, and we derive a series of clustering aggregation algorithms under such a framework. Finally the experiments on several real world data sets are presented to show the effectiveness of our method.