Multiple Kernel Clustering Framework with Improved Kernels

1 Introduction

Multiple view clustering (MVC) [Zhou and Burges, 2007; Weiran et al., 2015; Jinglin et al., 2016; Cao et al., 2015; Zhang et al., 2015; Yu et al., 2016] and multiple kernel clustering (MKC) algorithms [Zhao et al., 2009; Huang et al., 2012; Lu et al., 2014; Xia et al., 2014; Zhou et al., 2015; Kumar et al., 2011] have been extensively studied due to their efficiency and effectiveness. Although existing MKC algorithms have demonstrated promising performance in various scenarios, we observe that the success of these algorithms is largely dependent on the quality of base kernels. In existing MKC algorithms, the base kernels are usually pre-calculated and kept unchanged during the learning procedure, which indicates that the clustering performance would be poor when the quality of pre-defined kernels is low. Unfortunately, in many practical applications, the quality of pre-specified base kernels cannot be guaranteed due to that: i) some views of a sample may be missing, leading to the incomplete base kernels, i.e. some rows or columns of the base kernels shall be absent; ii) the extracted features may not be able to produce good clustering performance even when none view of any samples is missing; and iii) inappropriate kernel types in generating base kernels, for example, some applications get better performance using linear kernels, while other applications obtain better performance using Gaussian kernels. All these factors may adversely affect the quality of base kernels, leading to unsatisfying clustering performance.

∗The corresponding author.

To reduce the influence of base kernels, we propose a simple while effective framework to adaptively improve the quality of the base kernels during the learning process of multiple kernel clustering, as illustrated in Figure 1. Our framework firstly discovers outliers in each kernel based on the previous clustering results, and then designs an alternative algorithm to optimize them iteratively. In this way, our framework enhances the negotiation between the resultant base kernels and the clustering, leading to the improvement on clustering performance. To implement this framework, two issues are naturally raised: i) how to find outliers reducing the performance; and ii) how to optimize base kernels. To address the first issue, we exploit the connections between base kernels and clustering results, and find that the samples with further distance to their clustering center are more unascertainable. This is rather intuitive since these unascertainable samples could be considered as outliers. To address the second issue, we propose an alternative algorithm to optimize base kernels and recover those inappropriate values in each kernel. Under our framework, we instantiate three MKC algorithms based on the widely used multiple kernel k-means clustering (MKKM) [Huang et al., 2012], MKKM with matrixinduced regularization (MKKM-MR) [Liu et al., 2016] and co-regularized multi-view spectral clustering (CRSC) [Kumar et al., 2011], and design three efficient algorithms with proved convergence to solve the resultant optimization problems, respectively. To the best of our knowledge, our framework bridges the gap between kernel adaption and clustering procedure for the first time in the literature. More importantly, our framework is flexible and readily extendable for generating better MKC algorithms. Extensive experimental results show that our framework improves the performance of existing MKC algorithms on most datasets. Meanwhile, our framework shows better performance than compared ones with imperfect kernels.

2 RelatedWork

Existing MKC algorithms can roughly be grouped into two categories. The first category optimizes a group of kernel coefficients, and uses the combined kernel for clustering, called pre-fusion category, including MKKM [Huang et al., 2012] and its variants such as MKKM-MR [Liu et al., 2016], RMKC [Zhou et al., 2015], and localized multiple kernel k-means (LMKKM) [G¨onen and Margolin, 2014]. By following multiple kernel learning (MKL) framework, the other category learns the indicating matrix H without explicitly obtaining the combined kernel, like CRSC [Kumar et al., 2011]. In this section, we give a brief introduction of three typical representatives belonging to these categories.

2.1 Multiple Kernel k-means Clustering (MKKM)

Let {xi}ni=1⊆X be a collection of n samples, and φ(·):x ∈ X ↦→ H be a feature mapping which maps x onto a reproducing kernel Hilbert space H. In the multiple kernel setting, each sample has multiple feature representations via a group of feature mappings {φp(·)}mp=1 . Specifically, each sample is represented as φγ(x) = [γ1φ1(x)⊤, γ2φ2(x)⊤, · · · , γmφm(x)⊤]⊤, where γ = [γ1, γ2, · · · , γm]⊤ denotes the coefficients of each base kernel.

Given the combined kernel matrix Kγ, the optimization problem for MKKM can be written as,

This problem can be solved by alternatively updating H and γ.

2.2 MKKMClustering withMatrix-induced Regularization (MKKM-MR)

By integrating the matrix-induced regularization into the objective function of existing MKKM, the optimization problem of MKKM-MR can be obtained as follows,

where λ is a parameter to trade off the clustering cost function and the regularization term.

2.3 Co-regularized Spectral Clustering (CRSC)

Co-regularized spectral clustering (CRSC) provides a coregularization way to perform spectral clustering. Instead of explicitly optimizing the combined kernel, it learns the indicating matrix H directly. The objective function can be written as:

where λp reflects the importance of Kp. The optimal H⋆ and Hp can be obtained in an alternative way. In fact, the optimal problem can be rewritten as the spectral clustering objective function when H⋆ or Hp fixed.

Existing MKC algorithms have been applied to many clustering tasks successfully. However, the performance of these algorithms are largely dependent on the quality of pre-defined base kernels. Moreover, these base kernels are kept unchanged during the learning process. By this way, the performance would be poor if the base kernels have low quality. To eliminate the limitation, we design a novel clustering framework to adaptively improve the quality of the base kernels during the learning process.

3 Multiple Kernel Clustering Framework with Improved Kernels (MKCF-IK)

Although achieving promising performance, the aforementioned existing MKC algorithms largely depend on the quality of base kernels. Meanwhile, the pre-calculated kernels would not be changed during the learning procedure even if they are imperfect. To adaptively improve the quality of base kernels, we introduce our multiple kernel clustering framework with improved kernels (MKCF-IK), as shown in Algorithm 1. The proposed framework firstly adopts a simple while effective strategy to discover inappropriate values among each kernel which may be inappropriate for clustering, as described in Algorithm 2. After that, we carefully design corresponding alternative algorithms to recover these values automatically according to the previous clustering results.

In Algorithm 1, O(t) p means the indices of outliers, while S(t) p indicates the indices of stable samples, and ρ(0,t) represents the average kernel alignment value, which indicates the similarity between original and improved kernels. It is intuitive that the original base kernels would keep some good properties of data, so we set a threshold for ρ(0,t) to prevent the original kernels changing too much.

Algorithm 1: Proposed MKCF-IK.

Input: {Kp}mp=1 , ϵ0, η0

Output: H⋆ , {Kp}mp=1

• 1 K(0) p =Kp, p = 1, · · · ,m, t=1.
• 2 repeat
• 3 Obtain indices of stable samples S(t) p and outliers O(t) p using Algorithm 2 with K(t-1) p .
• 4 Optimize K(t) p and H⋆ using improved MKC algorithms with S(t) p and K(t-1) p .
• 5 Calculate alignment value ρ(0,t) using Eq.(4). 6 t = t + 1.
• 7 until (ρ(0,t) ≤ η0 ) || ((obj (t-1) - obj (t) )/obj (t) ≤ ϵ0 );

Algorithm 2: Discovering Outliers.

Input: {Kp}mp=1 , r

Output: {Sp,Op}mp=1

1 for each p ≤mdo

3

2 Compute labels and centers using KKMwith Kp. for each clustering center j do

4

5

6

Collect Nj samples belongs to this center. Add the Nj ∗ r samples with further distance to the j-th center to Op.

Add other Nj ∗ (1 - r) samples to Sp.

3.1 Discovering Outliers

By exploiting the connections between base kernels and clustering results, we observe that samples with further distances to their clustering centers are more unascertainable. It is rather intuitive that these unascertainable samples are prone to become outliers. Moreover, different base kernels describe different relationships among samples, which implies that we can obtain different outliers based on different kernels. By this way, we are able to identify the locations of outliers for each kernel. In specific, we first perform kernel k-means (KKM) on each base kernel Kp, which produces initial clustering labels of samples. After that, we compute the distance between each sample and its clustering center. For each center, we collect a proportion of samples with top largest distances to it, and add their indices to Op. We term this proportion as r. In our experiments, this r is set to be 0.05 or 0.1. In addition, we also record the relatively stable samples as Sp.

3.2 MKCAlgorithms with Enhanced Kernels

After obtaining the locations of outliers in each base kernel, we design different alternative algorithms based on different MKC algorithms to optimize the inappropriate values among these base kernels, making them better serve for clustering. Under our framework, we instantiate three classical MKC algorithms, and design three efficient algorithms with proved convergence to solve the resultant optimization problems, respectively. Here we only introduce the implementation of MKCF-IK on CRSC due to the space limitation.

3.3 An Instantiation: CRSC-IK

Let Sp(1 ≤ p ≤ m) denotes the sample indices for which the p-th view is present and K(cc) p be used to indicate the sub-kernel matrix computed with these samples. Then the objective function of CRSC-IK can be written as Eq.(5).

As can be seen, the difference between the objective function of CRSC-IK and that of CRSC in Eq.(3) is the incorporation of optimizing {Kp}mp=1 . Note that the constraint Kp(Sp, Sp) = K(cc) p is imposed to ensure that the improved Kp maintains the relatively stable kernel values during the course.

CRSC-IK considers base kernels as the optimized target. It aims to enhance the base kernels for clustering by treating {Kp}mp=1 as extra variables into our algorithm. To solve the problem described in Eq.(5), we design a three-step algorithm in an alternative way, as shown in Algorithm 3.

1. Optimizing H⋆ with {Hp}mp=1 and {Kp}mp=1 fixed. Given Hp, the H⋆ can be obtained by solving the following objective function:

which is equivalent to solving the standard spectral clustering objective for H⋆ with a modified Laplacian ∑p λpHpH⊤p ;

1. Alternatively optimize Hp for p = 1, 2, · · · ,m with fixed H⋆ , {Kp}mp=1 and {Hj}j̸=p. Given H⋆ and all other view-specific eigenvectors, Hp for view p can be solved by Eq.(7).max

By using the properties of matrix traces, Eq.(7) can be written as following:max

which is equivalent to solving the standard spectral clustering objective for Hp with a modified Laplacian (Kp + λpH⋆H⋆⊤).

1. Optimizing {Kp}mp=1 with fixed {Hp}mp=1 . Given Hp, p ∈ {1, 2, · · · ,m}, the optimization problem in Kp can be written as:

where the constraint Kp(Sp, Sp) = K(cc) p guarantees that the improved Kp maintains the normal values during the optimized process.

Algorithm 3: Proposed CSRC-IK.

• 1 For all p, initialize K(0) p and t = 1.
• 2 For all p, initialize H(0) p by solving Eq.(3) with given K(0) p .

3 repeat

• 4 Update H⋆(t) by solving Eq.(6) with given H(t-1) p .
• 5 For all p, update H(t) p by solving Eq.(8) with fixed K(t-1) p , and H⋆(t) .
• 6 Update K(t) p by Eq.(13) with fixed H(t) p .
• 7 t = t + 1.
• 8 until (obj (t-1) - obj (t) )/obj (t) ≤ ϵ0;

As is well known, Eq.(9) is equivalent to the Eq.(10) as follows:

Note that Kp is positive semi-definite (PSD), so we can decompose Kp as ApA⊤p . Then we write Ap = [A(c) p A(m) p ] with A(c) p A(c) p ⊤ = K(cc) p , and assume that Qp = I-HpH⊤p , then rewrite Eq.(10) as:

where Qp is replaced with its blocked form.

To optimize Eq.(11), we compute the derivative of it with respect to A(m) p and let it equals to zero. Then we can obtain an analytical solution to the optimal A(m) p as:

Then the optimal Kp in Eq.(9) can be obtained as:

(13) Note that, compared with CRSC-IK, the implementations on MKKM and MKKM-MR optimize base kernels in a slightly different way. They use Qp to replace (I - HH⊤) other than (I -HpH⊤p ).

3.4 Discussion

In this section, we discuss why our framework would work. By revisiting Eq.(13), we observe that the enhanced kernels refine the inappropriate parts of each base kernel using fixed K(cc) p andQ. InMKKM-IK,Qdenotes (I-HH⊤), whereH is calculated by combined kernel K. Therefore, Q integrates the clustering information from all base kernels to optimize the p-th kernel. CRSC-IK does not use the global H to get information from other kernels because only Hp is used to optimize Kp. However, we observe that the optimized procedure of Hp in CRSC-IK would introduce the H. This indicates that the Hp already carries the global information from H. As a result, CRSC-IK also exploits the information from all base kernels to improve the quality of one base kernels. In conclusion, our framework integrates the information from all kernels to fill the inappropriate parts approximately.

4 Experimental Results

4.1 Datasets and Experimental Settings

To report the performance of our framework, we evaluate three instances of our framework, like MKKM-IK, CRSCIK and MKKM-MR-IK, on seven datasets, as shown in Tabel 1. Furthermore, to test the performance of all algorithms with respect to the number of classes, we generate ten datasets by randomly selecting samples the first 10, 20, · · · , 100 classes on Caltech102.

To evaluate the performance of our framework with incomplete base kernels, we randomly generate incomplete kernels with different missing ratios. Note that the missing ratio in our experiments means the percentage of samples with missing views, other than the percentage of missing rows (columns) in each kernel. Meanwhile, we randomly generate the incomplete patterns for 30 times and report the statistical results. The aggregated ACC, NMI and purity are used to evaluate the goodness of the algorithms in comparison. Following the literature [Cortes et al., 2012], all base kernels are centered and scaled so that we have κp(xi, xi) = 1 for all i and p.

4.2 Compared Algorithms

Our algorithms are compared with several recently proposed counterparts, including

• Average MKKM (A-MKKM): All kernels are uniformly weighted to generate a new kernel, which is taken as the input of kernel k-means.
• MKKM [Huang et al., 2012]: The algorithm alternatively performs kernel k-means and updates the kernel coefficients, as introduced in the related work.
• Localized MKKM (LMKKM) [G¨onen and Margolin, 2014]: LMMKM improves MKKM by combining the kernels in a localized way.
• Robust multi-view spectral clustering (RMSC) [Xia et al., 2014]: RMSC constructs a transition probability matrix from each single view, and uses them to recover

a shared low-rank transition probability matrix for clustering.

• Robust Multiple Kernel Clustering (RMKC) [Zhou et al., 2015]: RMKC learns a robust yet low-rank kernel for clustering by capturing the structure of noises in multiple kernels.
• CRSC: [Kumar et al., 2011]: It provides a coregularization way to perform spectral clustering.
• MKKM-MR [Liu et al., 2016]: MKKM-MR reduces the redundancy and enhances the diversity of base kernels by introducing a matrix-induced regularization.

4.3 Experimental Results

The clustering performance of the above mentioned algorithms on all datasets are reported in Table 2. As is shown in Table 2, three instances of our framework achieve promising clustering performance.

Taking the result on bbcsport for example, the clustering accuracy of MKKM, CRSC, and MKKM-MR are 67.91%, 80.51%, and 66.91%. In contrast, our improved algorithms, MKKM-IK, CRSC-IK, and MKKM-MR-IK, achieve 88.6%, 91.73% and 74.82%, respectively. In order to demonstrate performance more vividly, we use t-SNE [Laurens, 2013] to visualize the indicating matrices H of bbcsport in Figure 4. It can be observed that our algorithms would make five classes much further and more discriminative than other MKC algorithms.

We also investigate the clustering performance of each algorithm with respect to the number of classes, as shown in Figure 2. As observed, the curves of CRSC-IK and MKKMMR-IK are above that of CRSC and MKKM-MR when the number of classes varies. Moreover, MKKM-MR-IK keepii) can better recover the incomplete base kernels by taking account the goal of clustering. In short, our framework well bridges the gap between kernel adaption and clustering procedure for the first time in the literature and is readily extendable, bringing forth significant improvements on clustering performance.

5 Conclusion

In this paper, we propose a novel framework to adaptively improve the quality of base kernels. Our framework enhances the negotiation between the base kernels and the clustering performance, leading to the improvement on clustering performance. Under our framework, we instantiate three MKC algorithms based on MKKM, MKKM-MR, and CRSC. After that, we design three alternative algorithms to solve the resultant optimization problems. To the best of our knowledge, our framework fills the gap between kernel adaption and clustering procedure for the first time in the literature. Extensive experimental research has been conducted on synthetic dataset, MKC benchmarks and some computer vision datasets. As shown, our algorithms consistently and significantly improve the performance of the base MKC algorithms, indicating the effectiveness of the proposed framework.

Acknowledgements

This work was supported in part by the Natural Science Foundation of China (61403405, U1435219, 61402499).

s on the top of all sub-figures when the number of classes varies, indicating the best performance.

Figure 3 presents the clustering performance comparison of the above algorithms with absent kernels on Flower17 and Caltech102. It can be observed that: i) MKKM-IK, CRSCIK and MKKM-MR-IK demonstrate the overall best performance in all the sub-figures; ii) the variation of MKKM-IK, CRSC-IK and MKKM-MR-IK with respect to the missing ratio is relatively smaller when compared with other algorithms, demonstrating its stability in the case of intensive absence.

Convergence. Two examples of the evolution of the objective value of MKKM-IK on Digital and YALE are demonstrated in Figure 5. As we can see, the objective value of MKKM-IK does monotonically decrease at each iteration.

From the above experiments, we conclude that the proposed framework: i) improves the performance of base MKC algorithms when the base kernels are complete; ii) achieves better clustering performance than other MKC algorithms; i-