A Robust Convex Formulation for Ensemble Clustering

1 Introduction

Clustering is a major technique in data science with many applications including text clustering [Huang et al., 2011] and image segmentation [Shi and Malik, 2000], etc. However, no single clustering algorithm, such as k-means [Hartigan and Wong, 1979] and spectral clustering [Ng et al., 2002], can capture all types of patterns and so clustering results are likely to be unstable, if the assumption behind the used model is violated [Jain, 2010].

Ensemble clustering [Strehl and Ghosh, 2003] has been proposed to improve the performance of a single clustering algorithm by integrating more than one clustering results (i.e., the partition vectors p, see Figure 1). Ensemble clustering can be regarded as a meta-learning algorithm [Zhou, 2012], and there exist various types of methods including graph theory based approaches [Fern and Brodley, 2004], probabilistic models [Topchy et al., 2005; Wang et al., 2011], matrix factorization based models [Li et al., 2007], and matrix completion [Yi et al., 2012]. However, these algorithms implicitly assume that all input partitions by different clustering algorithms are reasonably good while this assumption can be easily violated if partition vectors include anomalous partitions.

For solving the problem of anomalous partitions, the weighted consensus clustering (WCC) algorithm has been proposed [Li and Ding, 2008]. WCC uses "importance" weights over partitions which are estimated from inputs by quadratic programming (QP), resulting lower weights for more anomalous partitions to be removed. Recently, an alternative approach, Instance-wise weighted NMF (Nonnegative Matrix Factorization)-based Aggregation (INA), has been proposed [Zheng et al., 2015]. INA tries to find anomalous clusters within a partition (See Figure 1), while WCC tries to find anomalous partitions. Both approaches are state-of-theart ensemble clustering methods that can deal with anomalous partitions/clusters. However, they are non-convex; the clustering performance heavily depends on initial parameter values. That is, for both WCC and INA, parameter values need to be carefully initialized. However, finding appropriate initial parameter values is a rather hard problem.

We propose Robust Convex Ensemble Clustering (RCEC). Specifically, we formulate the ensemble clustering problem as a nuclear norm and cluster-wise group norm regularization problem. A clear advantage of RCEC over WCC and INA is that the formulation of RCEC is convex and can find the globally optimal solution, being free from tuning initial parameter values. Moreover, the group norm regularization allows to remove anomalous clusters efficiently. Through synthetic and real-world experiments, we show that the proposed method outperformed state-of-the-art ensemble clustering methods. In summary, the contributions of this paper are as follows:

• ÷ We formulate the ensemble clustering problem as an optimization problem with nuclear norm and cluster-wise group norm regularization, and propose an efficient optimization algorithm over this problem.
• ÷ We introduce the `2↪1 norm regularization to detect anomalous clusters. To our knowledge, this is the first work to use the `2↪1 norm in ensemble problems.
• ÷ The proposed method empirically outperformed stateof-the-art ensemble clustering algorithms.

2 ProblemFormulation

Let S = [s1↪ ▷ ▷ ▷ ↪ sN] 2 Rd⇥N be the feature matrix for N instances and P = [p1↪ ▷ ▷ ▷ ↪ pM] 2 RN⇥M be the input partition matrix obtained by applying M clustering algorithms to S. The pm = [p1↪m↪ p2↪m↪ ▷ ▷ ▷ ↪ pN↪m]> 2 RN are the partition vectors, where pi↪m 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪Km♦ and Km is the number of clusters for the m-th partition. Note that, the number of clusters in different partitions can be different.

We further define binary cluster assignment matrices Lm 2 RN⇥Km , indicating the clusters to which each instance belongs, as follows:

The columns of the partition matrix Lm can be permuted without loss of generality.

We pool all binary cluster assignment matrices as

and use L as the input matrix for our algorithm. In this paper, we assume two types of clusters: normal clusters with dominant patterns and anomalous clusters without the patterns. Figure 1 shows an example of L.

The goal of this paper is to find normal partitions/clusters from the binary cluster assignment matrices, and use the obtained normal clusters for meta-clustering.

3 RelatedWork

We first introduce related ensemble clustering methods and discuss their drawbacks.

Graph-based ensemble methods: Graph-based methods first construct a graph (bi-graph, hypergraph, or meta-graph) from input partitions and then apply a graph-cut partitioning algorithm to get ensemble clustering results. The hybrid bipartite graph formation (HBGF) generates a bipartite meta-graph from a binary assignment matrix L, where both input clusters and instances are nodes. HBGF then finds a clustering assignment from the bipartite graph. HBGF has been empirically verified to be a state-of-the-art graph-based method [Huang et al., 2011; Fern and Brodley, 2004]. However, HBGF treats normal and anomalous partitions/clusters equally.

Matrix completion based ensemble methods: ECMC [Yi et al., 2012] is a two-step method. The first step is to construct the similarity matrixW m (W m ij = 1 if instances i and j are in the same cluster of the m-th partition, zero otherwise.) from a binary assignment matrix L and filter out uncertain data pairs (possibly anomalous input pairs) using predefined thresholds. Then, they use a matrix completion algorithm to complete the partially observed similarity matrix. Finally, spectral clustering is used to obtain the final clustering result from the completed similarity matrix. ECMC uses pre-defined thresholding parameters, and may lose some important information. Similarly, the Robust Clustering Ensemble (RCE) [Zhou et al., 2015] also focuses on detecting anomalous instance pairs.

Non-negative matrix factorization (NMF) based ensemble methods: NMF-based methods factorize the input similarity matrix or the cluster assignment matrix, to obtain a consensus cluster assignment matrix. NMF-based consensus clustering (NMFC) [Li et al., 2007] is the first NMF-based algorithm. Similar to ECMC, NMFC first computes the similarity matrix from L and then uses orthogonal non-negative matrix trifactorization (tri-NMF) [Ding et al., 2006] to have a cluster assignment matrix. Since NMFC uses the input similarity matrix that is estimated from all normal and anomalous partitions, the performance of NMFC can be poor if there exist some anomalous partitions. To overcome this issue, WCC [Li and Ding, 2008] introduces "importance" weights over input partitions which are determined by quadratic programming (QP). That is, WCC computes the similarity matrix by putting larger weights for normal partitions and smaller weights for anomalous partitions. However, WCC assumes that some partition vectors p are anomalous. This means even if clusters within an anomalous partition are normal, WCC may ignore those information. Moreover, WCC is computationally expensive due to the QP computation.

Instance-wise Weighted NMF-based Aggregation (INA) [Zheng et al., 2015] was proposed to overcome the problem of WCC. More specifically, INA introduces weights over clusters to explicitly consider normal/anomalous clusters. The objective function of INA is given as

where = (φij)N⇥K is a weighting matrix, indicating the reliability of cluster j for instance i. WCC and INA can handle anomalous partitions/clusters, but both are non-convex, resulting in that initial parameter values need to be carefully tuned.

4 Proposed method

4.1 Robust Convex Ensemble ClusteringModel

The key idea of RCEC is to reconstruct a cluster assignment matrix X from L by choosing representative normal clusters. To this end, we impose cluster-wise (column-wise) sparsity by assigning a `2↪1 regularizer to X. Moreover, since the matrix L tends to be low-rank, we assume the rank of the obtained assignment matrix to be smaller than the number of true clusters c.

The optimization problem can be written as

where β ≥ 0 is the regularization parameter tuning the number of anomalous clusters, k·kF is the Frobenius norm, and k· k2↪1 is the `2↪1-norm defined as follows [Yuan and Lin, 2006; Yang et al., 2011; He et al., 2012; Yang et al., 2013]:

where X▷j represents the j-th column of X, which corresponds to a particular cluster. The `2↪1-norm enforces sparsity over groups and non-sparsity within a group, and thus, the coefficients of anomalous clusters can be shrunk to zero by imposing the `2↪1-norm regularization. Note that, we add the non-negativity constraint X ≥ 0, since the input binary partition matrix L is non-negative.

The rank constraint in Eq. (1) is non-convex, and we use the nuclear norm as a convex surrogate of the rank function. The nuclear norm is defined as

where σi is the singular values of X. Since the nuclear norm is defined as the sum of singular values, it can be regarded as the `1 regularization of singular values. Thus, by imposing the nuclear norm, we can obtain low-rank estimation.

We then reformulate the objective function as the following:

where λ ≥ 0 is a regularization parameter.

Due to the non-differentiability of the nuclear norm, we consider the Schatten-p norm as a uniform smooth approximation to the nuclear norm [Mohan and Fazel, 2012]. The smooth Schatten-p function is given as

The fp(X) is differentiable for p > 0 and convex for p ≥ 1. With γ = 0, f1(X) = kXk⇤, which is also known as the Schatten-1 norm [Mohan and Fazel, 2012].

Using the Schatten-1 norm as a smooth approximation to the nuclear norm, our objective function becomes

where I 2 RK⇥K denotes the identity matrix. Eq. (2) is a convex optimization problem with respect to X.

After obtaining the assignment matrix X, we apply the normalize cuts method (Ncut) [Shi and Malik, 2000] on the linear kernel of X to obtain the final clustering results.

4.2 Optimization

We propose an iterative algorithm to solve Eq. (2). We first rewrite Eq. (2) as

where Lagrangian multipliers ∆ 2 RN⇥K enforce the nonnegativity constraints X ≥ 0.

The derivative of Eq. (3) with respect to X is given as

where Dii = 1 kX▷ik2 1 , H+ = (♣H♣ + H)◁2, H- = (♣H♣ - H)◁2, and H = (XT X + γI)-1◁2 . From the Karush-Kuhn-Tucker (KKT) conditions, [ @J(X) @X ]ijXij = 0 and ∆ijXij = 0↪ 8i↪ j, we have

This is a fixed point equation that the solution must satisfy when converged.

Next, we show that the following updating rule satisfies the KKT condition of Eq. (4):

The limiting solution of updating rule of Eq. (5) makes the rule to satisfy the fixed point equation: when converged, X(1) = X(t+1) = X(t) = X where t ! 1. Then, the updating rule of Eq. (5) reduces

From Eq. (6), we get the following equations:

Eq. (7) is identical to Eq. (4). Hence if Eq. (7) holds, Eq. (4) also holds and vice versa. So we have proved that the limiting solution of the updating rule of Eq. (5) satisfies the KKT condition.

The pseudo-code of our optimization process is presented in Algorithm 1.

Complexity Analysis: The complexity of computing H is O(K3 ), because of matrix inversion. Thus, the entire complexity for updating X is O(T (K3 +NK2 )), while the time complexity of INA is O(c2NKT) (c and T are the number of clusters and iterations, respectively.). In reality, since K is the order of hundreds and K ⌧ N, the complexity of the proposed method is practically feasible.

1 When kX▷ik2 = 0, we cannot set Dii. Thus we use (kX▷ik2 + &) which approximates kX▷ik2, when & ! 0.

Algorithm 1 The RCEC algorithm

Input: S 2 Rd⇥N , the number of clusters c

• Output: X 2 RN⇥K , consensus partition 1: Generate input partitions P from S using clustering algorithms, and construct the binary assignment matrix L. 2: Initialize X(0) randomly. 3: repeat 4: Compute D(t) = 1 kX(t) k2 H(t) = (XT (t)X(t) + γI)-1◁2 5: Optimize X by solving Eq. (5). 6: until converges 7: Return the final clustering result as : consensus partition = Ncut(XXT ↪ c)

5 Experiments

In this section, we first examine the proposed method using synthetic data sets, and then compare the performance of RCEC with five ensemble clustering algorithms HBGF, ECMC, NMFC, WCC, and INA using real-world data sets. For a fair comparison, the true number of clusters is given as a priori parameter to all methods. The performance is evaluated by normalized mutual information (NMI), a widely used information theoretic measure for evaluating clustering methods [Ana and Jain, 2003; Chen and Cai, 2011].

5.1 Synthetic Dataset

In this experiment, we first generate a true partition vector p⇤ 2 R100 , which consists of 10 clusters, and each cluster has 10 instances (Figure 2 (a)) 2 . Then, we generate 10 normal partitions ¶pm♦10 m=1 based on the true partition p⇤ (Figure 2 (b)). A normal partition pm consists of 5 normal clusters and 5 anomalous clusters. In a normal cluster, only 20%

2 In Figure 2, The y-axis indicates instances, and different colors correspond to different clusters. The normal partition includes more normal clusters than the anomalous partitions which consist of a few normal clusters and many anomalous clusters.

of instances are randomly permuted to other clusters, while in an anomalous cluster, 80% of instances are randomly permuted to other clusters. Moreover, we prepare some anomalous partitions and extremely anomalous partitions. As shown in Figure 2 (c), each anomalous partition p0m consists of 10 anomalous clusters. We use the pooled normal and anomalous partitions ¶pm♦10 m=1 [ ¶p0m♦n0 m=1 as the input. We vary the number of (extremely) anomalous partitions n0 and report the average NMI score. Note that the extremely anomalous partition (Figure 2 (d)) contains one true cluster and nine extremely anomalous clusters, where all instances scatter in different true clusters.

Figure 3 (a) and (b) show the results of Ave 3 , HBGF, ECMC, NMFC, WCC, INA and RCEC when adding anomalous partitions and extremely anomalous partitions, respectively. As shown in these figures, the performance of existing methods significantly decreased by adding anomalous clusters, while RCEC was more robust against anomalous clusters.

Furthermore, we checked whether the RCEC algorithm can safely get rid of anomalous clusters. To this end, we define two indicators (normalized magnitude) lj◁maxj(lj) and xj◁maxj(xj), where lj = PNi=1 Lij ↪ xj = PNi=1 Xij ↪ j = 1↪ 2↪ ▷ ▷ ▷ ↪K. Please note when lj◁maxj(lj) is large and xj◁maxj(xj) is small (possibly zero), the cluster would be likely to be an anomalous cluster. Figure 4 (a) and (b) show the indicators of L and X when n0 = 5 and extremely anomalous partitions are added. From the figures, we can see that clusters 101 to 150 correspond to extremely anomalous clusters, and blue and red regions correspond to normal and anomalous clusters, respectively. We can then clearly see that RCEC could retain normal clusters (blue) and filter out anomalous clusters (red).

5.2 Real-world Data sets

We evaluated the RCEC algorithm using two text and one image data sets, which are summarized in Table 1.

For the text data sets, we used the TFIDF [Manning et al., 2008] features. We randomly chose 60%↪ 70%↪ ▷ ▷ ▷ ↪ 100% of the entire features for experiments. In this experiment, 30 partitions estimated by k-means were used as the input. We repeated the experiment 10 times by changing the random seed and reported the average NMI values. We used λ = 0▷1, γ = 0▷01, and β = ¶0▷01↪ 1↪ 2↪ 4↪ 6↪ ▷ ▷ ▷ ↪ 20♦. For NMF-based ensemble methods (including NMFC, WCC, and INA), we ran those algorithms five times with different initial parameter values and averaged over the clustering results. This is a common heuristic to stabilize the ensemble clustering algorithms.

3 "Ave" is the average NMI values of all input partitions (clustering algorithms).

Tables 2, 3 and 4 show the performance of different algorithms in terms of NMI. We could not include WCC, since WCC is computationally too expensive. The three tables clearly indicate that RCEC outperformed existing methods, being statistically significant.

Number of Partitions and Parameters: We evaluated the clustering performance as a function of the number of input partitions. The process of generating input partitions was repeated 10 times. In the experiments, we used 60% of input features, γ = 0▷01, and λ = 0▷1. Figure 5 (a) shows the results with changing the number of input partitions on the Tr11 data set. RCEC outperformed other methods through all the numbers of input partitions.

RCEC has two essential parameters β and λ. Figure 6 shows how the performance of RCEC varied with the parameter values of β and λ. From the results, the performance of RCEC could be kept consistently when β is within [10↪ 16] and λ in [10-6 ↪ 100 ].

Convergence and Computation: Figure 5 (b) shows the speed of convergence of the proposed algorithm on the Tr11 data set. We can see that the multiplicative updating rule converged very quickly, usually within 20 iterations. We also compared the computation time of the proposed method with INA (Figure 5 (c)). In this experiment, since INA is a nonconvex method, we ran INA several times with different initializations and averaged over those clustering results to obtain a stable result. From the results, we can see that the clustering performance of INA were better by increasing a larger number of initializations, which however results in a larger amount of computation time. On the other hand, RCEC can find the global minimum, by which we just need to run RCEC only once. Hence RCEC runs faster than INA in practice, which makes the performance of RCEC higher.

6 Conclusion

We have proposed a new method for ensemble clustering which we call Robust Convex Ensemble Clustering (RCEC). The key idea of RCEC is to use the nuclear norm to handle the low-rank structure of the cluster assignment matrix and the group norm to detect anomalous clusters. The formulation has the convex property, which allows to obtain the global minimum, for which we have presented a simple yet effective multiplicative updating rule. Extensive experiments on synthetic and real data sets showed the effectiveness and efficiency of our approach comparing to the state-of-the-art ensemble clustering methods.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (61572139) and ICR-KU International Short term Exchange Program for Young Researchers. Funding acknowledgement: M.Y.: MEXT KAKENHI #16K16114, S.K.: Academy of Finland, COIN and grants 294238 and 292334, H.M.: MEXT KAKENHI #16H02868, M.Y. and H.M.: JST, ACCEL, "Reinforcement of Resiliency of Concentrated Polymer Brushes and Its Tribological Applications", H.M. and S.K.: Tekes, FiDiPro.