Multi-view Clustering via Late Fusion Alignment Maximization

1 Introduction

Multi-view clustering (MVC) has been intensively studied recently by integrating the available multi-view information to categorize data items with similar structures or patterns into the same group [Chen et al., 2007; G¨onen and Alpaydin, 2008; Yu et al., 2012; Huang et al., 2012; Liu et al., 2013; G¨onen and Margolin, 2014; Liu et al., 2016; Li et al., 2016; Liu et al., 2017; Liu et al., 2018]. Existing research in this filed can be summarized into two categories. The first one learns a latent consensus matrix via low-rank optimization [Xia et al., 2014; Zhou et al., 2015]. In [Xia et al., 2014], it is proposed to learn a latent low-rank transition probability matrix shared frommultiple views as the input to the standard Markov chain for clustering. The work in [Zhou et al., 2015] captures the noises in each kernel and integrates them into a low-rank framework. By following multiple kernel learning framework, the other category optimizes the optimal kernel matrix as a linear combination of known kernel matrices from a given library [Chen et al., 2007; Yu et al., 2012; Liu et al., 2013; G¨onen and Margolin, 2014; Liu et al., 2016; Li et al., 2016; Liu et al., 2017; Liu et al., 2019]. In [Chen et al., 2007], a three-step alternate algorithm is proposed to jointly optimize clustering, kernel coefficients and dimension reduction. The work in [Liu et al., 2016] proposes a multiple kernel k-means clustering algorithm with matrix-induced regularization to reduce the redundancy of the pre-defined kernels. Furthermore, local kernel alignment criterion has been applied to multiple kernel learning to enhance the clustering performance in [Li et al., 2016]. In [Liu et al., 2017], a multiple kernel algorithm is proposed to allow the optimal kernel to reside in the neighborhood of the combinational kernels. Our method in this paper belongs to the second category.

∗Corresponding author

Although the aforementioned algorithms have improved multi-view clustering from different aspects, we observe that they suffer from the following drawbacks. i) The intensive computational complexity, i.e., usually O(n3 ) per iteration with n the number of samples, prevents them from being applied into medium or large-scale clustering tasks. ii) As the work in [Liu et al., 2018] mentions, the optimization processes of these methods are usually over-complicated, which could increase the risk of being trapped into local minimums, leading to unsatisfying clustering performance.

In this paper, we theoretically show that maximizing the alignment between base partitions and consensus partition is conceptually equivalent to minimize the loss function of existing k-means clustering. Based on this observation, we propose a novel algorithm named Multi-view Clustering via Late Fusion Alignment Maximization (MVC-LFA). It maximizes the alignment between the consensus partition matrix and the weighted base partition matrices with orthogonal transformation, where each base partition is generated by performing clustering on each single view. The proposed MVC-LFA jointly optimizes the orthogonal transformation matrices, weight coefficients and the optimal consensus partition. Moreover, we develop an efficient algorithm to solve the resultant optimization problem, and theoretically analyze its computational complexity and convergence. Extensive experiments on five multiple-view benchmark datasets are conducted to evaluate the effectiveness and efficiency of our proposed method, including the clustering performance, the running time, the evolution of the learned consensus matrix and the objective value with iterations. As demonstrated, the proposed algorithm enjoys superior clustering performance with significant reduction in computational cost, in comparison with several state-of-the-art multi-view clustering methods.

The contributions of this paper are summarized as follows,

• We theoretically prove that maximizing the alignment between base partitions and the consensus partition is conceptually equivalent to minimize the loss function of k-means clustering. This observation motivates us to design a simple but effective multi-view clustering algorithm.
• The proposed MVC-LFA integrates multiple views in a late fusion manner. It simultaneously optimizes the consensus partition, transformation matrices and the weight coefficients of each view in a joint framework. To the best of our knowledge, the proposed MVC-LFA is the first attempt to address multiple view clustering via maximizing alignment between consensus clustering matrix and weighted base partitions.
• An alternate optimization algorithm with proved convergence is designed to efficiently tackle the resultant problem. By the virtue of it, MVC-LFA shows clearly superior clustering performance in comparison with state-ofthe-art methods. More importantly, MVC-LFA requires significantly less computational time, especially critical for large datasets with limited computing sources.

2 RelatedWork

2.1 K-means Clustering

As one of the classical and widely-used algorithms, k-means provides an intuitive and effective way to perform clustering. To be specific, the clustering loss function of existing k-means algorithms can be written as mentioned in [Boutsidis et al., 2015],

where X and H∗ are the data and partition matrix respectively. We can obtain the optimal H∗ for Eq. (1) by taking the k eigenvectors that correspond to the k largest eigenvalues of XXT.

Eq. (1) could not directly apply to data with multi views. To overcome this limitation, many novel algorithms have been proposed to extend the k-means into multi-kernel kmeans to handle multi-view clustering, which will be introduced in the next section.

2.2 Multiple Kernel K-means Clustering (MKKM)

For the multi-view based setting, we suppose that {xi}ni=1 ⊆ X is a collection of n samples with m views, and φp(·) : x ∈ X ↦→ Hp be the p-th feature mapping, which transfers x into a reproducing kernel Hilbert space Hp (1 ≤ p ≤ m). Hence each sample xi is represented as φβ(x) = [β1φ1(x)⊤, · · · , βmφm(x)⊤]⊤ from m views, where β = [β1, · · · , βm]⊤ consists of the coefficients of the m base kernels {κp(·, ·)}mp=1 . These coefficients will be optimized during clustering. Based on the definition of φβ(x), a kernel function can be expressed as,

By denoting the optimal kernel matrix Kβ = ∑mp=1 β2 pKp, the optimization goal of MKKM algorithm can be formulated as,

The optimization problem in Eq. (3) can be solved by alternately updating H and β. i) Optimizing H by fixed β. With the kernel coefficients β fixed, H can be obtained by solving a kernel k-means clustering optimization problem,

The optimal H for Eq. (4) can be obtained by taking the k eigenvectors corresponding to the largest k eigenvalues of Kβ. ii) Optimizing β by fixed H. With H fixed, β can be optimized via solving the following quadratic programming with linear constraints,

Along with this line, many variants of MKKM have been proposed in the literature. The work in [Liu et al., 2016] proposes a multiple kernel k-means clustering algorithm with matrix-induced regularization to reduce the redundancy and enhance the diversity of the pre-defined kernels. Furthermore, local kernel alignment criterion has been applied to multiple kernel learning to enhance the clustering performance in [Li et al., 2016].

Although demonstrating promising performance, we observe that most of the existing multi-view clustering methods extend the Eq. (1) into multi-view by assuming that Kβ = ∑mp=1 βpKp for instance and learn an optimal similarity representation K∗ to perform kernel k-means clustering. As mentioned in [Liu et al., 2018], this category causes intensive computational complexity , i.e., usually O(n3 ) per iteration with n the number of samples and over-complicated optimization increasing the risk of trapped into low-quality local minimum. In the next section, we propose Multi-view Clustering via Late Fusion Alignment Maximization(MVC-LFA) to address this issue.

3 Multi-viewClustering via Late Fusion Alignment Maximization (MVC-LFA)

3.1 Proposed Formulation

According to the aforementioned discussions, we firstly show our theoretical result on the connection between the widelyused k-means loss function and our proposed late fusion alignment. In the following, we derive a new and related optimization goal of Eq. (1) for multi-view clustering based on the following Theorem 1.

Lemma 1. For any given orthogonal matrix P with the size of k×k, the inequality Tr2 (P) ≤ k ·Tr(PTP) always holds.

Theorem 1. Based on Lemma 1, minimizing Eq. (1) is conceptually equivalent to maximize Tr(H∗TX).

Proof. By taking P = H∗TX and according to Lemma 1, we can see that Tr2 (H∗TX) ≤ k · Tr(H∗TXXTH∗ ). As a result, Tr(XXT) - Tr(H∗TXXTH∗ ) ≤ 2k - Tr(H∗TXXTH∗ ) ≤ 2k - 1k Tr2 (H∗TX). Therefore, minimizing Tr(XXT)-Tr(H∗TXYTH∗ ) is conceptually equivalent to maximize Tr(H∗TX). This completes the proof.

Based on Theorem 1, we derive a simple but effective clustering loss function for clustering. This new formulation can be readily extended to handle multi-view clustering. To be specific, after obtaining the basic partitions {Hp}m p=1 from each single view, we conduct the new optimal combinational data partition X = ∑mp=1 βpHpWp to maximally align with the optimal clustering partition. Compared with minimizing Eq. (1), maximizing Tr(H∗TX) is much easier to optimize since it only requires the singular value decomposition of X in contrast to XXT so that significantly reduces the timecomplexity and simplifies the optimization procedure.

As a result, we obtain the objective function of our proposed algorithm as follows,

where {Wp}mp=1 are a set of rotation matrices, M denotes the average partition region and λ is a trade-off parameter. The latter Tr(H∗TM) is a regularization on the consensus partition to prevent H∗ from being too far way from prior average partition. It is worth noting that we not only set an optimization goal for the multi-view clustering with late fusion, but also offer a new framework to fuse various clustering methods, which implies that any kind of ensemble clustering results can be applied to our framework. Moreover, as the following optimization process shows, the proposed function could be easily solved by an alternate algorithm with proved convergence.

3.2 Alternate Algorithm

Although the problem in Eq. (6) is a relaxed version, it is still troublesome to be solved by existing packages. In order to solve it, we design a three-step alternate algorithm with proved convergence, where each step could be easily solved by the existing off-the-shelf packages.

With {Wp}mp=1 and β being fixed, the optimization Eq. (6) could be rewritten as follows,

where U = ∑mp=1 βpHpWp + λM. The problem in Eq. (7) could be easily solved by taking the singular value decomposition (SVD) of the given matrix U. Here the following Theorem gives a closed-form solution for the problem in Eq. (7).

Theorem 2. Suppose that the matrix U in Eq. (7) has the economic rank-k singular value decomposition form as U = SkΣkV⊤ k , where Sk ∈ Rn×k , Σk ∈ Rk×k , Vk ∈ Rk×k . The optimization in Eq. (7) has a closed-form solution as follows,

Proof. By taking the the normal singular value decomposition U = SΣVT, the Eq. (7) could be rewritten as,

Considering that Q = VTH∗TS, we have QQT = VTH∗TSSTH∗V = Ik. Therefore we can take Tr(VTH∗TSΣ) = Tr(QΣ) ≤ ∑ki=1 σi. Hence in order to maximize the value of Eq. (7), the solution should be given as Eq. (8).

With H∗ and β being fixed, for each singleWp, the optimization problem in Eq. (6) is equivalent to Eq. (10) as follows,

where A = βpHTp H∗ . And this problem in Eq. (10) could be easily solved by taking the singular value decomposition (SVD) of the given matrix V. Like the closed-form expressed in Theorem 2, if the matrixV has the singular value decomposition form as A = SΣGT, the optimization in Eq. (10) has a closed-form solution as Wp = SGT. Therefore, we optimize one Wp with other Wi̸=p fixed at each iteration. As a result, we can obtain a set of optimized {Wp}mp=1 .

Optimization β with fixed H∗ and {Wp}mp=1

With H∗ and {Wp}mp=1 being fixed, the optimization problem in Eq. (6) is equivalent to the optimization problem as follows,

where δp = Tr(H∗THpWp). This could be easily solved with closed-form solution as follows,

In sum, our algorithm is outlined in Algorithm 1, where obj(t) denotes the objective value at the t-th iteration. The following Theorem 3 shows our algorithm is guaranteed to converge.

Theorem 3. The proposed algorithm 1 is proved to converge to a local optimum,

Proof. Note that for ∀p, q, Tr[(βpHpWp)T(βqHqWq)] ≤ Tr[(HpWp)T(HqWq)] ≤ 12 (Tr[(HpWp)T(HpWp)] + Tr[(HqWq)T(HqWq)]) = k. As a result, we could derive the upper bound of the optimization goal in Eq. (6). We obtain that Tr(H∗TX) ≤ 12 (Tr[H∗TH∗ ] + Tr[XTX]) = 1 2 (Tr[H∗TH∗ ] + Tr(∑mp,q=1 (βpHpWp)T(βqHqWq))) ≤ k2 (m2 + 1). Meanwhile, the (H∗TM) ≤ 12 (Tr[H∗TH∗ ] + Tr[MTM]) = k. Consequently, the whole optimization function is upper bounded. As the three subproblem is strictly convex when optimizing one variable and keeping the others fixed. The objective of Algorithm 1 is monotonically increased when optimizing one variable with the others fixed at each iteration. At the same time, the whole optimization problem is upper-bounded. As a result, the proposed algorithm can be verified to be convergent. This completes the proof.

3.3 Discussion and Extensions

In this section, we analyze the computational complexity and potential extensions.

Computational Complexity: With the optimization process outlined in Algorithm 1, the computational complexity of MVC-LFA is O(nk2 + mk3 ) per iteration, where n,m, k represents the number of samples, views and clusters respectively. This implies that our algorithm has a linearly growing complexity with the number of samples, making it efficiently to handle large-scale tasks comparing to the state-of-the-art multiple-kernel clustering algorithms.

Algorithm 1 Multi-view Clustering via Late Fusion Alignment Maximization

Input: {Hp}mp=1 , k, λ and ϵ0.

Output: H∗ and β.

• 1: Initialize {Wp}mp=1 = Ik, β = 1 √m and t = 1.
• 2: Calculate M by kernel k-means with average kernel.
• 3: while not converged do
• 4: Update H∗ by solving Eq. (7) with fixed {Wp}mp=1 and β.
• 5: Update {Wp}mp=1 with fixedH∗ and β by solving Eq. (10).
• 6: Update β by solving Eq. (12) with fixed H∗ and {Wp}mp=1 .
• 7: t = t + 1.
• 8: end while(obj(t-1) -obj(t))/obj(t) ≤ ϵ0
• 9: returnH∗ and β.

Extensions: MVC-LFA can be easily extended with the following considerations. Firstly, MVC-LFA could be further improved by capturing the noises or low-quality partitions existing in basic partitions. For example, we could integrate the basic partitions {Hp}mp=1 into the optimization procedure to capture more advanced base partitions. By doing so, the high-quality basic partitions are further used to guide the generation of consensus partition. Secondly, we could apply more similarity-based clustering methods to generate basic partitions. Exploring other generating methods and evaluating their clustering performance will be an interesting future work.

4 Experiments and Analysis

In this section, we evaluate the effectiveness and efficiency of the proposed MVC-LFA for five widely used multi-view benchmark datasets from the aspects of clustering performance, computational efficiency and convergence.

4.1 Experimental Settings

Datasets

The datasets used in our experiments are Oxford Flower17 and Flower102 1 , and Protein fold prediction 2 and Columbia Consumer Video (CCV) 3 and Caltech 101 4 . The detailed information of the several datasets are listed in Table 1.

Compared Algorithm

In the experiments, MVC-LFA is compared with the following state-of-the-art multi-view clustering methods. (1) Average multiple kernel k-means (A-MKKM): All kernels are averagely weighted to conduct the optimal kernel, which is used as the input of kernel k-means algorithm. (2) Single best

1 http://www.robots.ox.ac.uk/˜vgg/data/ flowers/ 2 http://mkl.ucsd.edu/dataset/ protein-fold-prediction 3 http://www.ee.columbia.edu/ln/dvmm/CCV/ 4 http://www.vision.caltech.edu /Image Datasets/Caltech101

kernel k-means (SB-KKM): Kernel k-means is performed on each single kernel and the best result is outputted. (3) Multiple kernel k-means (MKKM) ([Huang et al., 2012]): The algorithm alternatively performs kernel k-means and updates the kernel coefficients. (4) Optimized data fusion for kernel k-means clustering (OKKC) ([Yu et al., 2012]): The algorithm propose to jointly optimize clustering, the kernel coefficients and dimension reduction based on the metric of Mahalanobis distance. (5) Co-regularized spectral clustering (CRSC) ([Kumar et al., 2011]): CRSC provides a coregularization way to perform spectral clustering on multiple views. (6) Multiple kernel k-means with matrix-induced regularization (MKKM-MR) ([Liu et al., 2016]): The algorithm applies the multiple kernel k-means clustering with a matrix-induced regularization to reduce the redundancy and enhance the diversity of the kernels. (7) Multiple kernel clustering with local kernel alignment maximization (MKC-LKA)([Li et al., 2016]): The algorithm maximizes the local kernel with multiple kernel clustering and focuses on closer sample pairs that they shall stay together. (8) Optimal neighborhood kernel clustering with multiple kernels (ONKC)([Liu et al., 2017]): ONKC allows the optimal kernel to reside in the neighborhood of linear combination of base kernels and effectively enlarges the region from which an optimal kernel can be chosen.

In all our experiments, all base kernels are first centered and then normalized so that for all sample xi and p, we have Kp(xi, xi) = 1 by following [Cortes et al., 2012]. For all data sets, it is assumed that the true number of clusters is known and set as the true number of classes. For the proposed algorithm, the trade-off parameter λ is chosen from [2-15 , 2-14 , · · · , 215 ] by grid search.

The widely used clustering accuracy (ACC), normalized mutual information (NMI) and purity are applied to evaluate the clustering performance. For all algorithms, we repeat each experiment for 50 times with random initialization to reduce the effectiveness of randomness caused by k-means, and report the best result. All the experiments are performed on a desktop with Intel core i7-5820k CPU and 16G RAM.

4.2 Clustering Performance

The ACC, NMI and Purity of the compared algorithms on the five benchmark datasets are displayed in Table 2, where the best results are presented in red. From the results, we have the following observations: i) As a strong baseline, the recently proposed MKC-LKA ([Li et al., 2016]) outperforms other early-fusion multiple-kernel clustering methods in comparison. For example, it exceeds the second best early-fusion method (MKKM-MR) by 1.6%, 6.6%, 1.4%, 0.6%, 4.5% in terms of ACC on Flower17, ProteinFold, Flower102, Caltech and CCV respectively. These results verify the effectiveness of maximizing the kernel alignment in a local way. ii) The proposed algorithm MKC-LFA significantly and consistently outperforms MKCLKA by 0.7%, 2.9%, 3.2%, 6.5%, 17.3% in terms of ACC on Flower17, ProteinFold, Flower102, Caltech and CCV, respectively. Table 2 also reports the comparison of NMI and purity. As can be seen, we also observe that our proposed algorithm outperforms all other methods in both NMI and purity.

In summary, the above experimental results have well demonstrated the effectiveness of our proposed MVC-LFA comparing to other state-of-the-art methods. We attribute the superiority of MVC-LFA as two aspects: i) MVC-LFA employs joint fusion to update weighted basic partitions and the consensus one and gets slightly higher performance than other methods. To be specific, when a higher quality consensus partition is obtained, we could further make full use of the high-quality partition to guide the weighted basics ones and improve the performance. ii) Comparing with the existing early-fusion methods, the proposed MVC-LFA fuses multiple kernel information in the partition level, which demonstrates the benefits of fusing high-level information. These two factors contributes to the significant improvements on clustering performance.

4.3 Running Time

To compare the computational efficiency of the proposed algorithms, we record the running time of various algorithms on these benchmark datasets and report them in Figure 3. As can be seen, MVC-LFA in red has the shortest running time on all datasets comparing to the-state-of-art multi-view methods (MKKM, OKKC, CRSC, MKC-LKA (in green), MKKM-MR and ONKC), demonstrating the computational efficiency of the proposed method. As theoretically demonstrated, MVC-LFA reduces the time complexity from O(n)3 to O(n) per iteration and avoid complicated optimization procedure. In sum, both the theoretical and the experimental results in Figure 3 have well demonstrated the computational advantage of MVC-LFA, making it efficient to handle with multi-view clustering.

4.4 Convergence and Parameter Sensitivity Study

Our algorithm is theoretically guaranteed to converge according to Theorem 3. For the experimental study, we conduct an experiment on CCV dataset and set the hyperparameters λ as 22 . Specifically, we evaluate the ACC, NMI and Purity of consensus partition H∗ learned at each iteration, as shown in Figure 2a. As can be observed, the clustering performance of MVC-LFA shown in Figure 2a gradually increases and has a slight variation with the increasing of iterations. This has clearly demonstrated the effectiveness of the learned consensus matrix H∗ . Furthermore, as shown in Figure 2b, the objective value of MVC-LFA does monotonically increase at each iteration and it usually converges in less than 10 iterations.

We also conduct the parameter sensitivity study on CCV dataset and report the clustering performance by ranging λ within the set of [2-15 , 2-14 , · · ·, 215 ] shown in Figure 2c. From the observation, NMI first increases to a high value and generally maintains it up to slight variation with the increasing value of λ. The curves with other datasets are similar and committed due to space limit. Comparing to MKKM-MR, MVC-LFA demonstrates stable performance across a wide range of λ.

5 Conclusion

In this article, we propose a simple but effective method MVC-LFA, which maximizes the alignment between the consensus partition matrix and the weighted base partition matrices with orthogonal transformation. We theoretically uncover the connection between the existing k-means and the proposed alignment. Based on this, we derive a simple novel optimization goal for multi-view clustering, which significantly reduces the computational complexity and simplifies the optimization procedure. The proposed algorithm is developed to efficiently solve the resultant optimization. By the virtue of it, MVC-LFA shows clearly superior clustering performance with significant reduction in computational cost on benchmark datasets, in comparison with state-of-the-art methods. In the future, we will explore to capture the noises or bad partition existing in basic partitions and further improve the fusion method.

Acknowledgements

This work was supported by the National Key R&D Program of China 2018YFB1003203 and the National Natural Science Foundation of China (Grant NO.61672528, NO. 61773392).