From Ensemble Clustering to Multi-View Clustering

1 Introduction

Multi-View learning benefits from leveraging the complementary information from multiple views of a particular dataset, where these views can be obtained by various sensors or represented with different descriptors. For example, we may capture human activity from RGB video cameras, depth cameras, and on-body sensors [Li et al., 2016]; for vision tasks, images could be encoded by host of handcrafted and deep features. Some interesting multi-view problems include subspace learning [Ding and Fu, 2014], outlier detection [Li et al., 2015a; Zhao and Fu, 2015], crossdomain learning [Wang et al., 2017], and incomplete multiview case [Zhao et al., 2016]. In this paper, we focus on the Multi-View Clustering (MVC) problem. Considerable research efforts have been made to solve the MVC problem, such as optimizing certain loss function with concatenated multi-view features [Bickel and Scheffer, 2004; Kumar and III, 2011], conducting traditional clustering on a common low-dimensional latent subspace [Chaudhuri et al., 2009; Xia et al., 2014; Wang et al., 2016; Zhao et al., 2017], and late fusion approaches [Greene and Cunningham, 2009; Bruno and Marchand-Maillet, 2009].

The key problem for MVC is how to integrate the complementary information from multiple views. For instance, [Kumar et al., 2011] enhanced the similarity of eigenvectors learnt from different views and integrated it within a spectral clustering framework; [Liu et al., 2013b] designed a joint matrix factorization method and sought for a compatible solution of multi-view data. However, the noises of each single-view data can seriously degrade the performance of these pioneering works. In light of this, [Xia et al., 2014] learned a consensus affinity graph among multiple views and handled the view-specific noises via a low-rank and sparse decomposition framework. Along this line, [Wang et al., 2016] captured the local manifold structure in each view and achieved the clustering agreement by minimizing the difference across views. All these MVC methods directly integrate the raw multi-view data, which, however, is not an easy task due to the distinct gap among heterogeneous feature spaces. Thus, one promising way (i.e. late fusion methods) for solving MVC is to first transform multi-view data into the same partition space [Greene and Cunningham, 2009; Bruno and Marchand-Maillet, 2009], and then obtain the clustering result in an ensemble clustering manner.

Ensemble Clustering (EC) [Strehl and Ghosh, 2003; Fred and Jain, 2005] methods take as input a set of Basic Partitions (BPs) and integrate multiple BPs into a consensus one. Thus, it naturally has the ability of leveraging complementary information from heterogeneous sources [Wu et al., 2015]. Nevertheless, ensemble clustering draws little attention in the field of multi-view clustering, and it neglects to explore the connection among different views. Moreover, most existing EC methods also suffer from the noises in the multi-view BPs, which could be caused by the intra-view or inter-view disagreement among all the BPs [Tao et al., 2016].

To address the above challenges, we propose a novel MultiView Ensemble Clustering (MVEC) algorithm in this paper. Specifically, we first generate a group of BPs for each single view, and summarize each group as a view-specific coassociation matrix [Fred and Jain, 2005], which works as a pairwise affinity matrix upon the categorical data. After that, we employ low-rank and sparse decomposition to seek for the consensus affinity matrix shared by all the views and compensate the disagreement among all the BPs. Meanwhile, the spectral ensemble clustering task [Liu et al., 2015; 2017] is also involved by our MVEC framework with a carefully designed constraint, leading to a unified optimization framework to jointly integrate multi-view information and find the consensus partition.

MVEC is inspired by two previous works [Xia et al., 2014; Tao et al., 2016]. Compared with [Xia et al., 2014], we solve MVC in a partition space rather than using raw features, since it is more reasonable to uncover the cluster structure shared by multi-view co-association matrices. Moreover, different from [Xia et al., 2014] that only learns a low-rank matrix, our approach simultaneously performs the tasks of low-rank representation learning and spectral graph partitioning. On the other side, [Tao et al., 2016] focuses on the single-view case and thus cannot make full use of the multi-view data. In contrast, our MVEC explicitly utilizes the connection between different views and employs the learned consensus partition to iteratively enhance the cluster structure of each view.

The contributions of this work are summarized as follows: (1) A general Multi-View Ensemble Clustering (MVEC) framework is proposed, which effectively exploits the multiview basic partitions to solve the MVC problem. (2) We jointly learn the view-consensus affinity matrix and find the consensus partition within a unified optimization framework. (3) A novel self-boost constraint is designed to iteratively improve the clustering performance.

2 Multi-View Ensemble Clustering

2.1 ProblemFormulation

Given a set of n data points with m views (i.e., feature representations or modalities), we denote the dataset of each view as X (v) = {x(v) 1 , . . . , x(v) n }, 1 ≤ v ≤ m. For ∀v, we assume X (v) is sampled from K crispy clusters, denoted as C = {C1, . . . ,CK}. Let Π(v) = {π(v) 1 , . . . , π(v) r } be a group of r basic partitions (BPs) for X (v) , where each BP π(v) i partitions X (v) into Ki clusters, i.e., π(v) i = {π(v) i (x(v) 1 ), . . . , π(v) i (x(v) n )} is a set of categorical data, 1 ≤ π(v) i (x(v) j ) ≤ Ki, 1 ≤ i ≤ r, and 1 ≤ j ≤ n. For each view, we obtain Π(v) by using the Random Parameter Selection (RPS) strategy [Fred and Jain, 2005; Wu et al., 2015], which performs K-means algorithm on X (v) r times with varying cluster number from K to √n. It has been shown that, RPS can capture various cluster structures existing in the real-world datasets [Fred and Jain, 2005].

In this paper, we aim to solve multi-view clustering in an ensemble clustering way. By following [Fred and Jain, 2005; Liu et al., 2015], each Π(v) is summarized as a co-association matrix S(v) ∈ Rn×n :

where x(v) p , x(v) q ∈ X (v) and δ(a, b) = 1 if a = b; 0 otherwise. By this means, we actually compute a pairwise affinity graph for each view upon the partition space, and thus, we can naturally conduct graph partitioning on S(v) to find a consensus clustering result. In particular, each view could be solved by spectral ensemble clustering [Liu et al., 2015]:

where H ∈ Rn×K is the scaled partition matrix that represents the cluster membership of all the data points: Hjk = 1/√|Ck| if xj ∈ Ck; 0 otherwise, and L(v) s is the normalized Laplacian matrix [Ng et al., 2001] of the co-association matrix in the v-th view.

However, Eq. (2) only tackles each view individually, yet without utilizing the complementary information between different views. There are still two challenging problems of employing the co-association matrices from multiple views for the clustering aim: (1) How do we seek a consensus coassociation matrix to identify the underlying cluster structure shared by multi-view data? (2) How can we capture the disagreements among multiple BPs of intra-view or inter-view?

To address the above challenges, we propose to learn a common representation shared by multi-view co-association matrices via low-rank and sparse matrix decomposition [Ye et al., 2012; Xia et al., 2014]. Moreover, we jointly perform the tasks of spectral graph partitioning and low-rank representation learning. Our Multi-View Ensemble Clustering (MVEC) algorithm is formulated as:

where H ∈ Rn×K represents the consensus partition, Z ∈ Rn×n is the low-rank representation, E(v) ∈ Rn×n captures noises for the vth view, 1 ∈ Rn is the vector of all ones, and λ1, λ2 > 0 are two balancing parameters. Lz = Dz - Z is the Laplacian matrix [Ng et al., 2001] of Z, and Dz is a diagonal matrix consisting of the sum of each row in Z. By following [Liu et al., 2013a], we employ the nuclear norm ‖Z‖∗ to measure the matrix rank, and the ℓ1 norm ‖E(v) ‖1 to characterize the sparseness.

Considering that, the co-association matrices of all the views share with the same cluster structure, and the rank of S(v) ideally equals to the cluster number K (K ≪ n), we seek for a low-rank representation Z to reveal the membership between data points through all the views. Meanwhile, to alleviate the "conflict" among different views and handle the outliers existing in co-association matrix, we learn a sparse error matrix E(v) for each single view. Hence, we may take Z as a consensus pairwise affinity matrix, and find the consensus partition H on Z by spectral clustering.

Taking a close look at Eq. (3), we develop a self-boost constraint to iteratively enhance the original co-association matrix of each view, i.e., S(v) +HHT = S(v)Z+E(v) , where HHT enjoys a clear cluster structure. By using this carefully designed constraint, we first find a high quality consensus partition H from Z, and then in return, H is leveraged to better guide the learning of Z. Besides, we also add the probabilistic simplex constraint (Z ≥ 0, Z1 = 1) [Duchi et al., 2008] to guarantee the probability property of Z.

2.2 Optimization

A unified optimization framework of three variable groups is provided by Eq. (3), which is convex with respect to each variable by keeping the others fixed. Thus, we can divide it into several subproblems, and solve them in an iterative way. In details, we apply the Augmented Lagrange Multiplier (ALM) algorithm [Lin et al., 2011] to address our MVEC problem. To facilitate the optimization process, we introduce an auxiliary variable J ∈ Rn×n with Z = J to make Eq. (3) separable. Then, our problem could be equivalently converted as:

The augmented Lagrange function of Eq. (4) is written as:

where Z ≥ 0, ∀v Y(v) ∈ Rn×n , Λ ∈ Rn×n , and w ∈ Rn are Lagrange multipliers, Φ(A, B) ≡ 〈A, B〉 + µ2 ‖A‖2F , and µ > 0 is a penalty parameter. In the next, we will give the details of iteratively solving J, Z, E(v) and H in sequence. Subproblem of J. Solving L w.r.t J is equivalent to:

Following the previous work [Liu et al., 2013a], Eq. (6) could be effectively solved by a closed-form solution:

where S(·) is the Singular Value Threshold (SVT) operator [Cai et al., 2010].

Subproblem of Z. Generally, we obtain the solution of Z(t+1) by taking derivate of L w.r.t. Z and setting it as zero. However, it is not straightforward to solve tr(HTLzH) in a matrix form, since Lz = Dz -Z and Dz is the degree matrix of Z. Thus, to simplify this term, we introduce an auxiliary matrix P ∈ Rn×n as:

where Hj is the j th row vector in H. By utilizing the property of Laplacian matrix and Eq. (8), we have the following simple deduction:

Algorithm 1. Multi-View Ensemble Clustering by ALM

Input: Basic partitions sets of m views Π(1) , . . . , Π(m) , cluster number K, two parameters λ1, λ2 > 0.

Initial: J(0) = Z(0) = Λ(0) = 0 ∈ Rn×n ,

• 1: Derive S(v) fromΠ(v) via Eq. (1) for each view;
• 2: while not converged do
• 3: Update J(t+1) via Eq. (7);
• 4: Update Z(t+1) via Eq. (11);
• 5: Update E(t+1) via Eq. (13);
• 6: Update Lz and Dz by Z(t+1);
• 7: Set H(t+1) as the K smallest eigenvectors of Lz;
• 8: Update the Lagrangian multipliers via Eq. (15);
• 9: Check the convergence condition:

• 10: µ(t+1) =min{ρµ(t), µmax}, t = t +1;
• 11: end while
• 12: Find the final partition π by running K-means on H or spectral clustering on Z.

Output: The final clustering result π.

Then, we can solve Z(t+1) via the following equivalent formulation as:

Inspired by [Zhuang et al., 2016; Lin et al., 2011], we linearize the Eq. (9) at Z(t) as:

where η(t) = ‖P(t)‖22 + ∑v ‖S(v) ‖22 + 1 + ‖1‖22 , and F(t) equals:

Then, the solution of Z(t+1) is given by:

Subproblem of E(v) . For each view v, we update E(v) (t+1) by:

Following [Lin et al., 2011], we have:

where D(·) denotes the element-wise soft-thresholding shrinkage operator [Lin et al., 2011].

Subproblem of H. Clearly, there are two parts w.r.t H in Eq. (5), which are corresponding to spectral ensemble clustering and our self-boost constraint, respectively. Recall that, we devise this constraint to involve an interaction between learning Z and finding H. As shown by Eq. (11), the term of HHT can effectively hold the cluster structure of Z(t+1). However, when computing H from Z, considering this term will take some unnecessary "noises" induced by E(v) and Y(v) into the clustering process. Hence, we omit the part of L that contains HHT, and recast the subproblem of H as:

where Lz is updated by Z(t+1). As suggested by [Zha et al., 2002; Dhillon et al., 2004], Eq. (14) is solved by directly setting H(t+1) as the K smallest eigenvectors of Lz.

Multipliers. Totally, we have m + 2 multipliers, which can be updated by:

where ∆(v) is introduced for the conciseness. The entire solution for MVEC is summarized in Algorithm 1.

2.3 Discussion

Convergence Analysis. As shown by Algorithm 1, the proposed MVEC can be divided into four subproblems, each of which is convex w.r.t one variable and solved with a closedform solution. Thus, by finding the optimal solution for each subproblem alternatively, our algorithm at least converges to a local minimum solution.

Complexity Analysis. The major computation of Algorithm 1 lies at step 3-5 and step 7. In details, step 3 costs O(n3 ) due to the SVD operation. Step 4 involves several matrix multiplications, leading to a complexity of O(ln3 ), where l is the number of multiplications. For each view, Eq. (13) takes O(n2 ), thus the complexity of step 5 is O(mn2 ). The eigenvalue decomposition in step 7 costs O(n3 ). Hence, the total cost of Algorithm 1 is O(T(mn2 + (l + 2)n3 )), where T is the iteration number. To make our algorithm scalable for large-scale datasets, several off-the-shell acceleration methods could be used, such as divide-and-conquer [Talwalkar et al., 2013] and the skinny SVD based ones [Zhang et al., 2014; Xiao et al., 2015].

3 Experiment

3.1 Experimental Setting

Datasets. Six real-world datasets are used in the experiment, which cover three text-type ones, i.e., the 3-Source 1 dataset, the 4-Areas 2 dataset, and the BBCSport dataset provided by [Xia et al., 2014]; and three image-type ones, i.e., a 20-class subset [Li et al., 2015b] of the Caltech101 3 image dataset, the UCI Digit 4 dataset, and the Notting-Hill dataset [Zhang et al., 2009] provided by [Cao et al., 2015]. We summarize these datasets in Table 1.

1 http://mlg.ucd.ie/datasets

2 http://web.cs.ucla.edu/~yzsun/data/four area.zip

Compared Methods. Multi-View Clustering Methods. By following [Xia et al., 2014], we generate affinity matrix with Gaussian kernels, and conduct spectral clustering [Ng et al., 2001] under different setting to obtain three baseline methods: (1) Spectral BSV returns the clustering result of the Best Single View (BSV); (2) Spectral CON concatenates the feature of each individual view and performs spectral clustering on the affinity graph built with the concatenated features; (3) Spectral SUM sums the affinity matrices of all the views and does spectral clustering on the averaged one. Besides, several effective multi-view clustering methods are also employed in the experiment, including Co-Regularized Spectral Clustering (CRSC) [Kumar et al., 2011], MultiView Nonnegative Matrix Factorization (MultiNMF) [Liu et al., 2013b] and Robust Multi-View Spectral Clustering (RMVSC) [Xia et al., 2014]. Ensemble Clustering Methods. Since our approach actually takes as input existing basic partitions (BPs), we also compare the proposed MVEC with three state-of-the-art ensemble clustering algorithms, including K-means based Consensus Clustering (KCC) [Wu et al., 2015], Spectral Ensemble Clustering (SEC) [Liu et al., 2015; 2017], and Robust SEC (RSEC) [Tao et al., 2016]. SECBSV (RSECBSV) represents the best ensemble clustering result of each single view, whilst SECSUM (RSECSUM) denotes the result with the averaged co-association matrices of all the views. Note that, since KCC directly finds consensus clustering among multiple BPs, we only report the KCCBSV.

Clustering Tools. Following [Wu et al., 2015; Liu et al., 2016; Tao et al., 2017], we generate a set of r = 100 basic partitions for each individual view by using the Random Parameter Selection (RPS) strategy, which performs K-means algorithm with cosine distance and various cluster numbers. We feed these basic partitions sets as the default input to all the EC methods. For traditional clustering methods, we directly take the raw data as input and follow their preprocessing steps. Two widely-used clustering validation criteria are used to evaluate the clustering performance of all the methods, which are Normalized Mutual Information (NMI) and Normalized Rand Index (Rn) [Wu et al., 2009]. Both these two metrics are positive measures and ranged from 0 to 1, where NMI will drop to zero for the random partition and Rn might be negative to the extremely poor clustering result.

3 http://www.vision.caltech.edu/Image Datasets/Caltech101/

4 http://archive.ics.uci.edu/ml/datasets.html

The top NMI value is highlighted by red bold font and the second best by blue italic.

• indicates the difference between MVEC and runner-up is statistically significant on this dataset.

For all the compared methods, we use the true cluster number for fair comparison, and run the codes provided by authors with the parameters as suggested in their work. We test each method 20 times, and report the average result as well as the standard deviation (std). To validate the statistic significance of comparison results, the p-value is also calculated with t-test. In the experiment, we set λ1 = 1 and λ2 = 0.01 as the default setting for our MVEC method.

3.2 Clustering Performance

Table 2 and Table 3 summarize the clustering results of the proposed MVEC and other methods in terms of NMI and Rn, respectively. As can be seen, our approach generally performs best on all the datasets by both metrics. In details, we improve around 12% NMI (8% Rn) and 4% NMI (6% Rn) over the runner-up on 3-Sources and 4-Areas, which clearly shows the effectiveness of our approach. To further evaluate the performance, we compute a measurement score by following [Wu et al., 2015]: score(Ai) = ∑j f (Ai ,Dj ) maxi f(Ai,Dj) , where f (Ai, Dj ) indicates the NMI or Rn value of Ai method on the Dj dataset. This score gives an overall evaluation on all the datasets, which shows our approach outperforms the other methods substantially. Besides, according to p-value, our model outperforms the second best method with a statistically significant level in most cases.

Ensemble Clustering vs Multi-View Clustering. Based on the input data, we may divide all the methods in Table 2

and Table 3 as two categories, such as ensemble clustering (EC) methods (e.g., KCCBSV, SECBSV and KCCSUM) that employ basic partitions, and multi-view clustering methods (e.g., Spectral SUM , CRSC and RMVC) that directly use the multiview data. As can be seen, EC methods generally outperform the multi-view clustering ones, and even the EC method of single-view performs much better than the traditional ones. This demonstrates the significant superiority and great potentiality of using ensemble clustering methods to solve the multi-view clustering problem.

Single-View vs Multi-View. As shown by Table 2 and 3, traditional multi-view clustering methods perform slightly better than the single-view ones. For example, RMVSC only improves 0.08 (0.04) overall score over Spectral BSV by NMI (Rn). The similar observation appears at the ensemble clustering case, where the EC methods integrating BPs from all the views generally outperform the BSV ones with a little improvement. Specifically, SECSUM is only 0.09 (0.21) higher than SECBSV in Table 2 (3). These two observations indicate that: (i) Traditional multi-view clustering methods sometimes cannot improve the performance compared with the singleview ones, since they may suffer from the conflict among different views; (ii) Existing EC methods neglect to fully exploit the multi-view information. In contrast, our MVEC method not only improves the robustness of co-association matrix to the multi-view BPs, but also explicitly considers the connection between different views. Thus, we achieve better perfor- The top Rn value is highlighted by red bold font and the second best by blue italic.

* indicates the difference between MVEC and runner-up is statistically significant on this dataset.

mance than multi-view and ensemble clustering methods.

3.3 Discussion

Convergence. To show the convergence property of our method, we compute the relative error of the stop criterion by max{‖∆(v) ‖F/‖S(v) ‖F}mv=1 . Fig. 1(a) shows the relative error curve of our approach. As can be seen, MVEC converges steadily within 60 iterations. Moreover, we also plot the NMI curve during the optimization process. Along with iterations, the clustering performance of MVEC generally goes up, and achieves stable within several reasonable fluctuations, which indicates our approach has a strong convergence behavior. It is worthy to note that, the similar convergence behavior of MVEC can be observed on the other datasets.

Parameter Analysis. Recall the Eq. (3), λ1 and λ2 are two major parameters in our model, where λ1 controls the rankness of the low-rank representation and λ2 balances the sparseness of error matrices for all the views. We report the clustering performance of MVEC by ranging λ1 and λ2 within the set of {10-4 , 5 × 10-4 , 10-3 , 5 × 10-3 , 0.01, 0.05, 0.1, 0.5, 1}. As shown by Fig. 1(b), our approach is quite insensitive to these two parameters. Considering that, the error matrices can compensate the disagreement between different views, we suggest to set λ2 as a relatively small value.

Impact of Basic Partitions Number. We employ r = 100 basic partitions (BPs) for each view v (denoted by Π(v) ) in all the above experiments. Here, we will explore the impact of different BPs number to the clustering performance of our approach. In details, for ∀v, we randomly sample r BPs from

Π(v) , and conduct MVEC with the sampled BPs sets of all the views. This process is repeated 100 times for a certain BPs number r. Fig. 1(c) shows the boxplots of NMI on the 3-Sources dataset, where r is increased from 10 to 90 with a step size of 10. One may note that, as r increases, the NMI generally goes up and its variance tends to be reduced. This is mainly because a larger BPs number can enrich the diversity of basic partitions and also improve the stableness of ensemble clustering [Wu et al., 2015]. In summary, our method is robust to a large BPs number, such as r ≥ 50.

Impact of Noisy Data. We consider noisy data under two scenarios: (1) noisy basic partitions (BPs) and (2) noisy features, where the first one randomly corrupts BPs for each view according to a certain missing ratio, and the second randomly "dropouts" some feature dimensions for the multiview data and then generates BPs upon the noisy features. As shown by Fig. 2, for both these two cases, we range the missing ratio from 10% to 50% along each view, and report the clustering performance of MVEC by NMI. Generally, our method is quite stable to the noises among basic partitions, due to the robustness inherited from ensemble clustering. On the other side, the performance of MVEC mainly degrades along with the diagonal direction of Fig. 2(b), showing that our method is robust to the noises of an individual view.

4 Conclusion

In this paper, we presented a novel Multi-View Ensemble Clustering (MVEC) framework, which employed coassociation matrix to characterize the pairwise affinity of each sing-view data upon multiple basic partitions. A unified optimization framework with the self-boost constraint was provided to jointly learn a consensus affinity matrix shared by multiple views and find the final clustering result. Experiments on six real-world datasets showed the effectiveness of the proposed method compared with both ensemble and multi-view clustering methods.

Acknowledgments

This work is supported in part by the NSF IIS award 1651902, ONR Young Investigator Award N00014-14-1-0484 and U.S. Army Research Office Young Investigator Award W911NF14-1-0218.