Instance-Wise Weighted Nonnegative Matrix Factorization for Aggregating Partitions with Locally Reliable Clusters

1 Introduction

We address the problem of combining multiple partitions (or clusterings) into a single consolidated partition, where each partition is a set of clusters made over the same set of instances [Li et al., 2010; Ghosh and Acharya, 2011]. In the literature, this problem has been called in various ways: ensemble clustering, clustering aggregation, consensus clustering and so on. The objective of this problem is to improve the results given by single clustering algorithms [Strehl and Ghosh, 2003]. There already exist a lot of different types of ensemble clustering approaches, which are based on graphs [Strehl and Ghosh, 2003; Fern and Brodley, 2004; Gionis et al., 2005], similarities [Strehl and Ghosh, 2003], probabilistic models [Topchy et al., 2005; Wang et al., 2011], and consensus functions [Nguyen and Caruana, 2007; Li et al., 2007]. See the Related Work section for detail on these methods, particularly graph-based and consensus functionsbased methods.

∗Shanghai Key Laboratory of Intelligent Information Processing and School of Computer Science, Fudan University

† Institute for Chemical Research, Kyoto University

Hiroshi Mamitsuka

Kyoto University† Uji, Japan mami@kuicr.kyoto-u.ac.jp

A key point of ensemble clustering is local cluster reliability, which can be measured by how often the same instance set shares clusters over multiple partitions. That is, if a cluster is shared by a certain size of same instance set a larger number of times, this cluster is more reliable, meaning that cluster reliability can be estimated from input partitions, if input partitions are diverse enough 1 . Furthermore we can say that clusters can be weighted according to reliability through instances. All existing methods have neither considered such intrinsic local properties of input partitions nor realized this idea. The key idea of our method is to explicitly consider the cluster reliability by using cluster weights to enhance the performance of ensemble clustering.

We first present a simple NMF-based ensemble clustering (NMFE), which is a rather straightforward application of typical nonnegative matrix bi-factorization to ensemble clustering. We then extend NMFE by the idea of cluster reliability. That is, if a cluster has particular (coherent) instances, which are always in the same cluster a larger number of times, this cluster must be more reliable. We propose a method, which we call Instance-wise weighted NMF-based Aggregation (INA), which formulates the idea of cluster reliability by incorporating weights over clusters to be estimated from given partitions. More concretely, the point is to capture the shared clusters (and the shared instance set) through the matrix factors, by which the shared (reliable) clusters will be weighted more. To estimate the factorized matrices and weights, INA uses an iterative algorithm which repeats the following two steps alternately: 1) H and W are estimated using the same way as NMFE while cluster weights are fixed, and 2) the (globally) optimal weights are estimated analytically while H and W are fixed. Thus, INA is time-efficient as long as NMFE is fast.

We empirically evaluated our proposed methods, NMFE and INA, comparing with several cutting-edge ensemble clustering methods by using three different scenarios on experimental data: 1) a synthetic dataset with seven different types of clusters, such as the normal distribution, scroll-shaped and circle-shaped clusters which was introduced in [Jain, 2010] as a challenging problem for developing new clustering methods; 2) real datasets from UCI [Newman et al., 1998] and CLUTO [Karypis, 2002] data repositories, from which partitions are generated to have locally reliable clusters; and 3) real dataset of multiview using partitions generated over each view. INA outperformed other competing methods throughout all three experiments, confirming the validity of our idea on capturing locally reliable clusters.

1 Reducing redundant partitions is one important research topic in ensemble clustering, resulting in many good work already [Hadjitodorov et al., 2006; Li and Ding, 2008; Fern and Lin, 2008; Azimi and Fern, 2009]. Thus we can reasonably assume that input partitions are diverse enough.

2 Method

2.1 Notation and ProblemFormulation

Let P = {P 1 , P 2 , . . . , P M } be M input partitions, sharing the same set of N instances X = {x1, x2, . . . , xN}. Partition P m (m = 1, 2, . . . ,M) consists of a set of clusters C m = {Cm 1 ,Cm 2 , . . . ,C m Km }, where Km is the number of clusters for partition P m and X = ⋃Km k=1 C m k . K = ∑Mm=1 Km. We can further define binary indicator matrix Lm, showing the clusters to which each instance belongs, as follows:

Note that for each m, C m j can be reordered without loss of generality. The input is N × K binary matrix L = [L1 L2 . . . LM ]. Fig. 1 shows an example of L.

2.2 Nonnegative Matrix Factorization for Ensemble Clustering (NMFE)

Our objective is to find a consolidated partition P ∗ which can be shown by indicator matrix H = {0, 1}N×K∗ , where K∗ is the number of clusters in P ∗ . For each P m, we introduce a column permutation matrix Wm = {0, 1}Km×K∗ to align columns of H to those of P m so that Lm should be approximated by HW Tm. Thus the problem can be defined as follows:

where ‖ · ‖ is the Frobenius norm. Letting W = [W T1 W T2 . . . W TM ]T , Eq. (2) is equivalent to the following general NMF problem:

where H and W are binary matrices.

Eq. (3) is an integer optimization problem, which is NPhard [Moret, 1997; Brucker, 1978; Cohen, 1960]. A general solution of this problem is to relax H and W into a nonnegative continuous domain:

A locally optimal solution of Eq. (4) can be obtained easier than solving the optimization of Eq. (3) by using a standard multiplicative updating procedure [Lee and Seung, 2001] as follows:

Finally, instance i is assigned to cluster x if x = arg max j Hij.

2.3 Instance-wiseWeighted NMF-based Aggregation (INA)

Formulation

The key idea of INA is that, instead of considering input partitions (and clusters) uniformly, we introduce weights over clusters (κij for cluster j and instance i of L), indicating the reliability of cluster j per instance i. Specifically, with the regularization term on the cluster weights, the objective function can be as follows:

where Ψ = (κij )N×K is a weighting matrix, L ⊙ Ψ denote the element-wise product of matrices L and Ψ, and λ is a regularization coefficient.

Optimization Algorithm

We can solve this problem by a locally optimal solution, which uses an iterative algorithm that first updates H and W and then updates Ψ alternately:

Step 1: Fix Ψ and optimize H and W according to NMFE. Step 2: Fix H and W and optimize Ψ.

We can rewrite Eq. (7) by using scalars as follows:

where L∗ = HW T , Eij = L2ij + λ, Fij = -2LijL∗ij and Gij = (L∗ij )2 .

Thus Eq. (7) is a convex problem, which can be solved analytically through a usual derivation of taking the derivative of

-----------------------

Input: L, λ

Output: H, W , Ψ

INA (L, λ, H, W , Ψ)

• 1: Initialize Ψ (e.g., κij ← 1M )
• 2: while until convergence do
• 3: Optimize H andW according to Eqs. (5) and (6)
• 4: Optimize Ψ according to Eq. (8)

• 5: end while

-----------------------

Figure 2: Pseudocode of the optimized algorithm of Instancewise weighted NMF-based Aggregation (INA)

Lagrange multiplier and satisfying the Karush-Kuhn-Tucker (KKT) conditions. Then Ψ is given as follows:

where

After obtaining H, W and Ψ, we assign cluster x to instance i, if x = argmax j Hij. Fig. 2 shows a pseudocode of the optimization algorithm of INA. For the validity of this algorithm, the time complexity and convergence proof are shown in appendices. Finally we can briefly show the validity of our formulation fromEq. (8): If we remove the regularization term (i.e. λ = 0), κij can be approximated as follows:

We note that this indicates that the prediction result, i.e. L∗ij , is directly connected to reliability weight κij, being consistent with our motivation of incorporating the cluster weights.

3 RelatedWork

Graph-based methods: Three representative ensemble clustering methods are all graph-based methods [Strehl and Ghosh, 2003]: Cluster-based Similarity Partitioning Algorithm (CSPA), HyperGraph-Partitioning Algorithm (HGPA) and Meta-CLustering Algorithm (MCLA). CSPA has two steps: 1) a similarity matrix over instances is generated by how many times each pair of two instances is in the same cluster and 2) similarity-based graph partitioning is applied to the similarity matrix. HGPA and MCLA use hypergraphs, in which a node is an instance and a hyperedge is a cluster of instances in a partition. HGPA applies graph-cut partitioning to the nodes in the hypergraph, while in MCLA hyperedges are clustered and then each instance is assigned to its mostly associated cluster (i.e. hyperedge).

Another graph-based ensemble clustering method, hybrid bipartite graph formation (HBGF) [Fern and Brodley, 2004] generates a "meta-graph" (in which both input instances and input clusters are nodes) which is a bipartite graph, in which nodes are clustered. This is a one-step procedure which partitions given clusters into "meta-clusters" and assigns each instance to one meta-cluster simultaneously. HBGF always works well, comparing to a variety of graph-based ensemble clustering methods [Huang et al., 2011], including CSPA, HGPA and MCLA (this was confirmed in our experiment).

Nonnegative matrix factorization (NMF): The first, representative NMF-based method is NMF-based consensus clustering (NMFC) [Li et al., 2007], which uses orthogonal nonnegative matrix tri-factorization (tri-NMF) [Ding et al., 2006]. NMFC was extended to weighted consensus clustering (WCC) by considering weights over input partitions [Li and Ding, 2008].

The input of NMFC is a connectivity (similarity) matrix W, in which W mij is 1 if instances i and j are in the same cluster of the m-th partition, zero otherwise. Then to obtain the consensus clustering, which is closest to all partitions, NMFC formulates the following optimization problem:

where ˜Wij = 1M ∑Mi=1 W mij . NMFC solves this problem by a multiplicative updating rule which is very similar to most standard optimization method of NMF. NMFC deals with the input multiple partitions equally and also clusters in one partition uniformly, by which important information of the input partitions might be lost.

To overcome this issue, WCC [Li and Ding, 2008] introduces weights over input partitions to formulate connectivity matrix ˜W as follows:

where w = (w1,w2, . . . ,wM)T , wm ≥ 0, ‖w‖1 = 1. The problem formulation is tri-NMF again, and the optimization algorithm repeats the following two steps alternately: 1) weights w are fixed and H is estimated by a standard multiplicative updating for tri-NMF, and 2) H is fixed and weights w are estimated by using quadratic programming (QP). This procedure is similar to INA, while QP may cause the following two serious problems, which are not in INA: 1) QP leads to a relatively sparse solution, like choosing only the best partition, and so it may not work if there are no good partitions, 2) QP may be computationally inefficient.

In WCC, weights are over input partitions only, while weights of INA are over all clusters of the input partitions. In other words, WCC deals with clustering in each partition equally, by which cluster reliability information cannot be incorporated and discarded in WCC. The next section shows that this difference between INA and WCC leads to the performance advantage of INA over WCC.

4 Experiments

We conducted three experiments to evaluate the performance of the two proposed methods, NMFE and INA, comparing with six cutting-edge methods, CSPA, HGPA, MCLA, HBGF, NMFC and WCC. Note that HBGF is one of the highest performance graph-based method and NMFC and WCC

are the two latest NMF-based methods. Through all experiments, for a fair comparison, the true number of clusters was given as a priori parameter to all methods. The performance was evaluated by normalized mutual information (NMI), a well-used information theoretic measure for evaluating clustering methods [Fred and Jain, 2003], averaging over 100 trials for each method, with paired t-test to examine the significance on the performance difference between two methods.

4.1 Experiment 1: Benchmark Data in [Jain, 2010]

We first used a famous benchmark dataset with seven clusters, which are shaped by two Gaussians, two scrolls and three cycles [Jain, 2010]. The structures of these seven clusters are very diverse, which makes it very hard to separate these clusters each other. No existing clustering methods could completely separate these seven clusters [Jain, 2010].

We obtained twenty different partitions by running the following twenty different clustering algorithms: two k-means

(the Euclidean distance and the city block distance), three hierarchical clustering (single-linkage, average-linkage and complete linkage) and 15 spectral clustering (eight with the manifold distance under different parameters, six with the Gaussian distance under different parameters and the last one with the Euclidean distance). Fig. 3 shows clustering results by typical clustering methods (points shown by the same shape are in the same cluster). We can easily see that all these clustering results were partially correct but failed to separate the seven clusters clearly.

Fig. 4 shows results obtained by running eight ensemble clustering methods, CSPA, HGPA, MCLA, HBGF, NMFC, WCC, NMFE and INA over the twenty partitions (points of the same shape are in the same resultant cluster). This figure shows that any clustering methods cannot separate seven true clusters clearly, except INA (Fig. 4h), which obtained the perfect clustering result. The second best method was HBGF (Fig. 4d), which gave a perfect result except two scrolls which were wrongly clustered. Overall INA outperformed all other seven ensemble clustering methods on the very difficult benchmark dataset. HBGF was the best among the graph-based methods, and so we will show the results of HBGF only out of them in the subsequent experiments, due to space limitations. Thus hereafter we focused on the five best methods, i.e. HBGF, NMFC, WCC, NMFE and INA.

4.2 Experiment 2: UCI and CLUTO

Table 1 shows the summary of the datasets we used in this experiment: 1) eight from the UCI data repository [Newman et al., 1998] under the criterion that each dataset has less than 1,000 instances and the number of labels (clusters) is between 4 to 10 to make all compared methods run in a practical amount of computation time. 2) six from the CLUTO data repository [Karypis, 2002], a standard document database often used for document clustering, extracted under the same criterion as that on the UCI data repository.

For each dataset, we generated input partitions from the ground truth with imposed local property, since controlled experiments are helpful for understanding the characteristic of competing methods. We first assigned true cluster labels to instances and then made instances move to different clusters, with a certain probability (which we call perturbation rate). For example, when the perturbation rate is 0.1, we move 10% of all instances to different clusters. However, in order to check the performance of capturing correct (or reliable) clusters, we kept one cluster per partition correct with a certain probability (which we call selection probability). The following is a simple example with 15 instances for 4 clusters (with the sizes of 5, 4, 3 and 3) where the first cluster (assigned by 1) is the correct cluster (with the selection probability of 1.0).

|11111|3212|432|143|

We fixed the perturbation rate and the selection probability at 0.9 and 0.5, respectively, arbitrarily. For each dataset, 30 partitions were generated.

Table 2 is the results of all five methods, clearly showing that INA outperformed all other competing methods in all 14 datasets, being statistically significant (paired t-test not shown due to space limitations), except only one dataset. The second best was NMFE, which outperformed the other three competing methods (WCC, NMFC and HBGF) in all datasets except only five cases. We further stress that even under the selection probability of 0.5 (meaning that only one reliable cluster per two partitions on average), the NMI values by INA were very high, implying the high robustness of INA.

We further checked the change of reliability weights of INA during the optimization procedure by using Breast in Table 1. Fig. 5 (a) shows the changes of weights over 30 partitions, in which 15 partitions were generated in the above manner (one cluster in each partition can be correct) while the other 15 partitions were with random cluster assignment. Starting with random values, the weights for partitions with correct clusters became larger (more red) through the iterations, because the same set of examples share the same correct clusters two or three times. On the other hand, Fig. 5 (b) shows the weight change for only 5 partitions with correct clusters and 25 partitions with random assignment. In this case, the correct clusters could not be captured well, because of no examples, which share the same cluster more than once (since, for six true clusters, only five partitions with one different correct cluster). This result directly shows that the reliability weights can capture the cluster reliability in terms of how often clusters are shared by the same set of instances.

4.3 Experiment 3: Multi-views Dataset

We finally used real text datasets, called 3-Sources 2 , which was retrieved from three online news sources: BBC, Reuters, and The Guardian. From February to April 2009, 169 distinct news stories were reported by all three sources. By manual annotation, each story was labeled (and used as true cluster label) with one of six different topics: business, entertainment, health, politics, sport and technology. Table 3 shows the statistics of the 3-Sources dataset.

2 http://mlg.ucd.ie/datasets/3sources.html

Each news source, which we call a view, has its own characteristic and should be separated. We generated features by processing words in original sentences using TFIDF [Manning et al., 2008] and randomly selected P% of all features to make the data more diverse. We then generated 10 partitions from each view by using k-means.

Table 4 shows the results, indicating that INA outperformed other competing methods in all cases, being statistically significant (detailed numbers of paired t-test not shown due to space limitations). The second best method was NMFE, which was followed by HBGF, NMFC and WCC.

5 Concluding Remarks

We have proposed INA, a new NMF-based ensemble clustering formulation and an efficient algorithm for factorizing matrices and estimating cluster weights. A key feature of INA is the weights over clusters (per instance) which are trained from given partitions. The trained weights allow to capture locally reliable clusters, coherent instances and eventually key clusters, which are important to obtain the most consistent partition. We empirically showed that this unique feature makes INA the most powerful method in performance among the cutting-edge ensemble clustering methods.

Acknowledgments

This work has been partially supported by National Natural Science Foundation of China (61170097 and 61272480), KAKENHI (2430054) of MEXT, JSPS Invitation Fellowships for Research in Japan, and ICR-KU International Shortterm Exchange Program for Young Researchers.

A Time Complexity

The time complexity of the optimization algorithm of INA is O(K2NMT) (T is the number of iterations), while that of NMFC is O(KN 2T), implying that INA is much faster than NMFC (and WCC), since in reality KM ≪ N.

B Convergence Proof

We denote the loss function, ‖L⊙Ψ-HW T ‖2 +λ‖Ψ‖2 , by J. Let J t1 be J before Step 1 at the t-th iteration of the optimization algorithm, and similarly let J t2 be J before Step 2 at iteration t.

First J t1 ≥ 0. We then prove that J is reduced by each step of the algorithm, i.e. J t1 ≥ J t2 and J t2 ≥ J t+1 1 .

For Step 1, we can see J t1 ≥ J t2 by the standard derivation of NMF [Lee and Seung, 2001].

For Step 2, in Eq. (8), κij is updated as follows:

where a = Lij + λ Lij , b = L∗ij and γ = µi.

Lemma 1 Let a1, a2, b1, b2, c and γ be real values. We assume that the sum of two real values x and y is given by x+ y = b1-γ a1 + b2-γ a2 .

f(x, y)(= a1x2 +b1x+a2y2 +b2y+c) is minimized when x = x0 and y = y0, where x0 = b1-γ a1 and y0 = b2-γ a2 .

Proof Assume that x = b1-γ a1 + ϵ and y = b2-γ a2 - ϵ, then f(x, y) = a1(x- b1 a1 )2 + a2(y - b2 a2 )2 +C = a1( γ a1 - ϵ)2 + a2( γ a2 - ϵ)2 + C = ( 1 a1 + 1 a2 )γ 2 + (a1 + a2)ϵ2 + C > ( 1 a1 + 1 a2 )γ 2 +C = f(x0, y0). (C is a constant.) □

Theorem 1 J t2 ≥ J t+1 1 .

Proof In Step 2, for each i, κij is updated by Eq. (8), which is in the form of bij-γ aij (again γ = µi). We prove that Eq. (8) is the only updating rule which can reduce J most at Step 2. We assume that the optimized κij at Step 2 can have different γ for different j. However Lemma 1 says that the loss can be reduced more if we use the same γ for different j. This leads to a contradiction, meaning that optimal κij must be obtained from the same γ for different j. This further means that Eq. (8) is the only updating rule of κij that minimizes the loss at Step 2. This proves J t2 ≥ J t+1 1 . □

The proof is complete, since J t1 ≥ 0 and J t1 ≥ J t2 ≥ J t+1 1 .