Self-paced Consensus Clustering with Bipartite Graph

1 Introduction

Clustering is a fundamental problem in unsupervised learning and attracts many attentions in past decades. However, according to [Wang et al., 2009a], traditional clustering methods suffer from the stable and robust problems. To address these problems, consensus clustering is proposed.

Consensus clustering provides an elegant framework for integrating multiple weak base clusterings to generate a consensus clustering result [Topchy et al., 2004]. In recent years, many consensus clustering methods have been proposed [Strehl and Ghosh, 2003; Zhou and Tang, 2006; Zhou et al., 2015a; Liu et al., 2018]. For example, [Strehl and Ghosh, 2003] and [Topchy et al., 2003] proposed information theoretic based consensus clustering methods; [Zhou and Tang, 2006] proposed an alignment method to combine multiple k-means clustering results; [Liu et al., 2015] provided a spectral clustering based ensemble method; [Wang et al., 2009b] and [Huang et al., 2016a] introduced probabilistic graphical model into consensus clustering. Besides these works which ensembled all base clustering results, some works tried to select some informative and non-redundant base clustering results for ensemble. For example, [Azimi and Fern, 2009] proposed an adaptive clustering ensemble selection method; [Zhao et al., 2017] applied internal validity indices to select based clustering results.

∗Corresponding Author

Note that, these methods always apply all instances for ensemble learning. However, since the base results may not be fully reliable, it is inappropriate to always use all data for ensemble. Intuitively, some instances are unreliable for clustering or even outliers, which lead to the poor performance of the base clusterings. At the beginning of learning, these unreliable instances may mislead the model, because the early model may not have the ability to handle these unreliable ones.

To address this issue, we propose a novel Self-paced Consensus Clustering with Bipartite Graph (SCCBG), which involves instances from more reliable to less reliable ones into the ensemble learning. The basic idea is that, we train the model with the easier or more reliable instances in the process of ensemble, until it is strong enough to handle the difficult ones. Firstly, we construct an initial bipartite graph from base clustering results, where a node represents an instance or a cluster and an edge indicates that an instance belongs to a cluster. Then, from it, we learn a structured bipartite graph, which contains exact c components, where c is the number of clusters. As introduced before, since the base clustering results are imperfect, some edges in the graph are also unreliable. Therefore, we apply the self-paced learning framework to learn the structured graph, i.e., we automatically decide the reliability of each edge and use the edges for learning in order of their reliability. On the one hand, the reliable edges are helpful to the graph learning; and on the other hand, with the process of graph learning, the edges become more and more reliable. By introducing a carefully designed regularized term to characterize the reliability, we seamlessly integrate the reliability evaluating and graph learning into a unified selfpaced learning framework. At last, we obtain the final clustering result from the learned structured graph by finding its connective components. The extensive experiments show that our methods often outperform the state-of-the-art consensus clustering methods.

2 Preliminaries

Throughout this paper, we use boldface uppercase and lowercase letters to denote matrices and vectors, respectively. For a matrix M, we use Mi. and M.i to denote the i-th row and column of M, respectively. We denote the (i, j)-th element in M as Mij .

2.1 Consensus Clustering

Let X = {x1, · · · , xn} be a data set with n instances. Given a set of m base clusterings C = {C 1 , · · · , Cm} of X, each clustering C i consists of a set of clusters {πi1 , · · · , πiki }, where ki is the number of clusters in C i and X = ⋃ki j=1 πij . Consensus clustering aims to learn a consensus partition of X from the m base clusterings C = {C 1 , · · · , Cm} [Strehl and Ghosh, 2003; Topchy et al., 2003; Topchy et al., 2004].

To learn the consensus partition, in this paper, we construct a bipartite graph G = {V 1 , V 2 , E} from C = {C 1 , · · · , Cm}. In more detail, V 1 contains n nodes and each node represents an instance. V 2 contains k = ∑mi=1 ki nodes and each node represents a cluster πij (i = 1, · · · ,m, and j = 1, · · · , ki). E is a set of edges which link nodes between V 1 and V 2 . If instance xi belongs to the cluster πqp , then there is an edge between xi and πqp . Fig. 1 shows an illustration of constructing the bipartite graph. In this example, we have 5 instances x1, · · · , x5 and 3 base clusterings. For example, in the first clustering C 1 , x1 and x2 belong to cluster π1 1 , and x3, x4 and x5 belong to the cluster π1 2 . The right side of Fig.1 shows the corresponding bipartite graph G. V 1 contains the blue nodes, V 2 contains the red nodes, and E denotes the set of edges. After obtaining the bipartite graph G, we aim to learn a partition on G as the consensus clustering result.

2.2 Self-paced Learning

The basic idea of self-paced learning is to incrementally involve instances into learning, where easy ones are involved first and difficult ones are then involved gradually [Kumar et al., 2010]. More formally, given a data set D = {(x1, y1), · · · , (xn, yn)}, where xi ∈ Rd is the feature vector of the i-th instance and yi is its label, we denote L(g(xi, θ), yi) as the loss function of the i-th instance, where g(xi, θ) is the decision function and θ is the model parameter. According to [Zhang et al., 2017], the self-paced learning introduces a weighted loss term on instances and a general regularized term on the weights as follows:

where λ is the "age" parameter to control the learning pace and grows with the learning process, and f(wi, λ) is the selfpaced regularized term.

In Eq.(1), if we fix the model parameter θ, supposing w∗ i (λ, li) is the optimum weight of xi, where li = L(g(xi, θ), yi), then f(wi, λ) should satisfy that w∗ i (λ, li) is monotonically decreasing with li and increasing with λ as suggested in [Jiang et al., 2015; Meng et al., 2017]. Note that, on the one hand, since w∗ i (λ, li) is decreasing with li, easy instances, which has low loss, will have a large weight, which means they will be involved in learning first. On the other hand, w∗ i (λ, li) is increasing with λ, which means with the learning process (λ grows), more and more instances are involved in learning.

Therefore, self-paced learning optimizes Eq.(1) via alternating minimization. Fixing θ and solving w is to learn the weight of each instance and finding the easy ones; solving θ by fixing w is to learn the model using the easy instances. Due to its promising performance and the benefit of alleviating the local optimum problem in non-convex optimization [Basu and Christensen, 2013], self-paced learning has been widely used in many scenarios, such as multi-task learning [Li et al., 2017], robust classification [Ren et al., 2017] and subspace learning [Jiang et al., 2018]. In this paper, we will extend it to unsupervised ensemble learning.

3 Self-paced Consensus Clustering with Bipartite Graph

In this section, we introduce the proposed SCCBG method in detail.

3.1 Formulation

Given m base clustering results, we first construct the initial bipartite graph as introduced in Section 2.1. Note that this initial bipartite graph may not have a very clear clustering structure since each base clustering may not be perfect. Taking Fig. 1 as an example, we find that there is only 1 connective component in the graph, i.e., all instances are entangled together. To make it have a clearer clustering structure and obtain the final consensus partition, we need to learn a structured graph G ′ which has exact c connective components where c is the number of clusters. Then clustering on G ′ is trivial because we just need to put instances in the same connective components into the same cluster.

More formally, we define the adjacent matrix of G as

where Y ∈ {0, 1}n×k and k = ∑mi=1 ki is the total number of clusters in all clustering results. Yij = 1 means there is an edge linking the i-th instance (xi) and the j-th cluster (πj), and Yij = 0 means there is no edge between them.

Similarly, we can define the adjacent matrix of the structured bipartite graph G ′ as

where S ∈ [0, 1]n×k . To make G ′ preserve G as well as possible, we should minimize ‖S-Y‖2F . Moreover, we also need to impose some constraints on S to make sure that G ′ has c connective components.

Given G′ , we can first obtain its normalized Laplacian matrix L = I - D- 1 2G′D- 12 , where I is an identity matrix and D is a diagonal matrix whose diagonal element Dii = ∑k+n j=1 G′ij . Then according to [Nie et al., 2017], we have that the number of connected components in G ′ is equal to n+k minus the rank of L, i.e., rank(L) = n+k-c. To this end, we obtain the following formula:

As introduced before, since the base clusterings may not be perfect, each edge obtained from the base clusterings may also be unreliable. To characterize the reliability of each edge, we introduce a weight matrix W ∈ [0, 1]n×k where the larger Wij is, the more reliable the corresponding edge is. With W we can integrate our consensus clustering task into the self-paced learning framework seamlessly. We involve edges gradually from more reliable edges to less reliable ones. As suggested in [Jiang et al., 2015], we set f(wi, λ) in Eq.(1) as -λ‖W‖1, and obtain:

where ⊙ is the Hadamard product, which means the elementwise production of two matrices; the second term is the selfpaced regularized term, and λ is the age parameter and becomes increasingly larger in the process of optimization.

Unfortunately, it is not enough to characterize the reliability of edges only by the first term in Eq.(5). We need to take a closer look at W. Note that, if two cluster πp and πq are similar, then for any instance xi, either xi belongs to the both clusters or xi belongs to neither. Therefore, if (Sip - Siq)2 is large, which means xi is more likely to belong to one of the clusters, then at least one of Sip and Siq is unreliable, i.e., at least one of Wip and Wiq should be small. More formally, we use the following carefully designed regularized term to characterise the reliability of edges:

where Cpq is the (p, q)-th element in C ∈ Rk×k , which characterizes the similarity of two clusters. C can be easily obtained by C = YT Y. We can find that, if Cpq is large (i.e.,

πp and πq are similar) and (Sip -Siq)2 is large (i.e., xi only belongs to one of the clusters), then by minimizing Eq.(6), at least one of Wip and Wiq should be small. Taking it into our self-paced framework (Eq.(5)), we obtain the final objective function:min

where γ is a balanced parameter.

3.2 Optimization

Eq.(7) involves the constraint rank(L) = n + k - c which is hard to optimize. We first handle this constraint. By introducing the auxiliary orthogonal matrix F ∈ R(n+k)×c and a large enough parameter ρ, Eq.(7) is equivalent to the following formula:

Then we optimize W, F, S respectively by fixing the other variables.

Optimizing W

When optimizing W, we find that Eq.(8) can be decoupled into n independent subproblems by rows. Considering the i-th subproblem, we have

Note that, Eq.(9) is a quadratic programming with bounded constraint and can be solved by standard optimization method, such as trust region reflective algorithm. In our implication, we use quadprog function provided in Matlab.

Optimizing F

When optimizing F, we need to solve the following subproblem:

Eq.(10) can be solved by computing the eigen-decomposition of L. However, conducting eigen-decomposition on an (n + k) × (n + k) matrix is often in O((n + k)3 ) time and is very time consuming. Fortunately, since L is a Laplacian matrix of a bipartite graph, according to Lemma 1 in [Nie et al., 2017], Eq.(10) can be solved by conducting Singular Valued Decomposition (SVD) on a small rectangle matrix. In more detail, define diagonal matrices ˆD ∈ Rn×n and ˜D ∈ Rk×k whose diagonal elements are ˆDii = ∑kj=1 Sij and ˜Djj = ∑ni=1 Sij respectively, and then compute the SVD of ˆD- 1 2S˜D- 12 as ˆD- 1 2 S ˜D- 12 = UΣVT , where U and V contain the left and right singular vectors respectively, and Σ is a diagonal matrix which contains the singular values. Let U′ ∈ Rn×c and V′ ∈ Rn×c be the c left and right singular vectors in U and V corresponding to the smallest c singular values, respectively. Then, the closed-form solution of Eq.(10) is:

Note that since ˆD- 12S˜D- 1 2 is an n × k matrix and often has n ≫ k, the time complexity of computing its SVD is O(nk2 ) which is much smaller than O((n + k)3 ).

Optimizing S

When optimizing S, Eq.(8) can also be decoupled into n subproblems by rows. Considering the i-th subproblem, we have:

Similar to Eq.(9), Eq.(12) is also a quadratic programming with bounded constraint and can be solved similarly.

Algorithm 1 summarizes the whole process of SCCBG.

Algorithm 1 SCCBG

Input: m base clustering results, number of clusters c, parameter γ.

Output: Consensus clustering results

• 1: Construct the initial bipartite graph from m based clustering and obtain Y, and initialize the age parameter λ = 0.5, S = Y.
• 2: Compute the cluster similarity matrix C=YT Y.
• 3: while not converge do
• 4: UpdateWby solving Eq.(9).
• 5: Update F by solving Eq.(10).
• 6: Update S by solving Eq.(12).
• 7: Update the age parameter by λ = λ ∗ 2.
• 8: end while
• 9: Obtain the final bipartite graph G ′ from S.
• 10: Obtain the final clustering result from the c connective component in G ′ .

3.3 Discussion

Firstly, we analyze the space and time complexity of our method. Since the graph we used is a bipartite graph, the space complexity of our method is O(nk).

For the time complexity, we analyze it step by step. Firstly, computing C needs O(nk2 ) time. Then, in each iteration, when updating W, we need to solve n quadratic programming problem and each problem involves k variables. Note that, in practice, we set γ a small value to make sure the quadratic programming problem is convex. Therefore, each subproblem costs O(k3 ) time and updating W costs O(nk3 ) time. Updating F needs O(nk2 ) as introduced in previous subsection. Updating S also needs to solve n quadratic programming problem and each problem involves k variables. The time complexity is also O(nk3 ). Supposing the number of iterations is l, the whole time complexity is O(lnk3 ).

Last but not the least, we discuss the robust consensus clustering, which is very related to our self-paced ensemble. Robust consensus clustering extracts the noises from data or base results and recovers the clean results for ensemble. For example, [Tao et al., 2016; Tao et al., 2019] proposed robust consensus clustering methods based on spectral clustering; [Huang et al., 2016b] used probability trajectories to robust consensus clustering; [Wang et al., 2019] provided an ensemble method on incomplete data. These methods only focus on the noises or outliers without distinguishing between uncontaminated instances. However, in our method, the contaminated instances can be regarded as the most unreliable ones, and in addition, the uncontaminated instances can also be handled in order of reliability. Therefore, our method provides a more sophisticated framework to handle instances. Moreover, in our self-paced framework, the reliability of edges is changing in the process of learning. With the growth of λ, Wwill be increasingly large until it reaches 1, which means the edges become increasingly more reliable with learning.

4 Experiments

In this section, we conduct the extensive experiments by comparing our SCCBG with several state-of-the-art consensus clustering methods on benchmark data sets.

• Robust Clustering Ensemble (RCE) [Zhou et al., 2015b], which learns a robust consensus result via minimize the KL divergence among each base result.
• Multi-view Ensemble Clustering (MEC) [Tao et al., 2017], which is a robust multi-view consensus clustering method using low-rank and sparse decomposition to ensemble base clustering and detect the noises.
• Locally Weighted Evidence Accumulation (LWEA) [Huang et al., 2018], which is a hierarchical agglomerative consensus clustering method based on uncertainty estimation and local weighting strategy.
• Locally Weighted Graph Partitioning (LWGP) [Huang et al., 2018], which is a graph partition method based on the local weighting strategy.
• Robust Spectral Ensemble Clustering (RSEC) [Tao et al., 2019], which is a robust clustering ensemble method based on spectral clustering.
• Dense Representation Ensemble Clustering (DREC) [Zhou et al., 2019], which learns a dense representation for clustering ensemble.
• SCCBG-W, which is our ensemble method without self-paced learning. In more detail, we fix the weight matrix W in SCCBG as 1 and do not update it.

The number of clusters is set to the true number of classes for all data sets and algorithms. Our method adjusts λ automatically as introduced in Algorithm 1. The parameter ρ is also automatically decided. We first initialize ρ = 1, and then, if the rank of L is larger than n + k - c, we double it. If its rank is smaller than n + k - c, we reduce ρ by half. The only hyper-parameter needed to tune manually is γ. As discussed before, γ should not be too large to make the subproblem convex, thus we tune it in the range [10-5 , 100 ]. We use Accuracy (ACC) and Normalized Mutual Information (NMI) to evaluate the clustering performance. To validate the statistic significance of results, we also calculate the p-value of t-test.

4.1 Data Sets

We use 8 data sets, including ALLAML 1 , GLIOMA 1 , K1b [Zhao and Karypis, 2004], Lung 1 , Medical [Zhou et al., 2015b], Tdt2 2 , Tr41 [Zhao and Karypis, 2004], and TOX 1 . The details of these data sets are summarized in Table 1.

4.2 Experimental Setup

Following the experimental setup in [Wang et al., 2009b; Zhou et al., 2015b], we use k-means to generate the base clusterings. In more detail, we run k-means 200 times with different initializations to obtain 200 base results. Then we divide them into 10 subsets, with 20 base results in each subset. Next, we apply consensus clustering methods on each subsets, and report the average results on the 10 subsets. We compare our SCCBG with the following methods:

• KM, which is the average result of all base clustering.
• KM-best, which is the best result of all base results.
• Cluster-based Similarity Partitioning Algorithm (CSPA) [Strehl and Ghosh, 2003], which signifies a relationship between instances in the same cluster to establish a measure of pairwise similarity for ensemble.
• HyperGraph Partitioning Algorithm (HGPA) [Strehl and Ghosh, 2003], which integrates base results with a constrained minimum cut objective.
• Meta-CLustering Algorithm (MCLA)[Strehl and Ghosh, 2003], which transforms the ensemble into a cluster correspondence problem.
• Nonnegative Matrix Factorization based Consensus clustering (NMFC) [Li and Ding, 2008], which uses NMF to aggregate base results.
• Bayesian Clustering Ensemble (BCE) [Wang et al., 2009b], which is a Bayesian model for ensemble.

1 http://featureselection.asu.edu/datasets.php

2 http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html

learning, we adopted the idea of self-paced learning, which automatically decided the reliability of each edge and involves the edges into graph learning in the order of reliability. At last, we obtained the final consensus clustering result by finding the connective components of the learned graph. We conducted extensive experiments on benchmark data sets. Compared with other state-of-the-art consensus clustering methods, our method often performs better than them, which well demonstrates the effectiveness and superiority of the proposed method.

Acknowledgements

This work is supported by the National Natural Science Fund of China grants 61806003, 61976129, and 61972001.

4.3 Experimental Results

Tables 2 and 3 shows the ACC and NMI results of all ensemble methods. The bold fonts means the difference is statistically significant (i.e., the p-value is smaller than 0.05). Note that, due to their high time and space complexity, RCE and MEC run out of memory on the largest data set Tdt2.

From these tables, we find that: (1) many ensemble methods outperform the KM, which indicates the effectiveness of consensus clustering. (2) Compared with other ensemble methods, our algorithm outperforms them on most data sets, which demonstrates its superiority. Even compared with the robust methods (RCE, MEC, and RSEC), ours also performs better, because our self-paced framework can handle data more finely as discussed in Section 3.3. Moreover, to further demonstrate the effectiveness of the self-paced learning framework, we also compare it with SCCBG-W, which is the version without self-paced learning. From the tables, we can see that our method significantly outperforms it, which also demonstrates the necessity of the self-paced learning framework. (3) On most data sets, our method is closed to or even better than KM-best. Note that, ours does not need to perform exhaustive search on the predefined pool of base clusterings, which also well demonstrates the effectiveness of SCCBG.

4.4 Parameter Study

The only hyper-parameter needed to tune manually is γ. As discussed before, γ should not be too large to guarantee the convexity of the subproblems. So we tune it in [10-5 , 100 ]. Fig. 2 shows the results on Lung and Tr41 data sets. We can see that our method works well when γ is in the range [10-5 , 10-3 ]. When γ becomes larger, the performance will deteriorate, which is in line with our previous discussion.

5 Conclusion

In this paper, we proposed a novel self-paced consensus clustering method with the bipartite graph. We constructed an initial bipartite graph based on the base results. Then we learned a structured graph from it. In the process of graph