Recovery of Corrupted Multiple Kernels for Clustering

1 Introduction

Clustering is a fundamental unsupervised machine learning problem. Kernel-based clustering methods, such as kernel kmeans, are widely used due to their effectiveness of separating non-linearly separable clusters [Dhillon et al., 2004]. In real world applications, we can construct different candidate kernels; for example, different kernel functions and parameters can lead to different kernels, and various views or data sources can also generate various kernels. The performance of kernel-based clustering highly depends on the choice of kernels [Yu et al., 2012]. Unfortunately, it is still a challenge to determine a suitable one among an extensive range of possible kernels for the given data and task in advance. Recent years there have been considerable interests in multiple kernel learning [Xu et al., 2008; Tzortzis and Likas, 2012; Huang et al., 2012b; G¨onen and Margolin, 2014], which aims at learning a suitable kernel from multiple kernel candidates for classification and clustering.

∗Corresponding author

Unsupervised multiple kernel learning methods usually learn a consensus kernel by linearly combining a set of candidate kernels [Zhao et al., 2009; Kulis et al., 2009; Huang et al., 2012b; 2012a]. Since the original data may be corrupted with noises and outliers, the induced kernel matrix may also be contaminated; moreover, given a dateset each kernel can be viewed as one with a certain degree of noises w.r.t. this dataset. However, to the best of our knowledge, no existing multiple kernel learning method has a mechanism to effectively handle kernel noises [G¨onen and Margolin, 2014].

In this paper, we propose a novel Robust Multiple Kernel Clustering (RMKC) method; it contains a special mechanism capturing the structure of noises in multiple kernels. We observe that once an instance is corrupted with noise, both the corresponding row and column of a kernel will be simultaneously contaminated. Thus we introduce an error matrix for each kernel which expresses such row-wise and column-wise noises. We integrate the error matrices into a multiple kernel consensus framework. A valid consensus kernel should be symmetric and positive semi-definite (p.s.d.); in addition, to obtain a clear cluster structure we further impose a low rank constraint [Kulis et al., 2006]. This leads to a hard optimization problem. To solve it we derive an alternating minimization procedure which can be theoretically guaranteed to converge. Note that we solve this problem by directly minimizing the rank of the consensus kernel without using any convex or non-convex approximated surrogates; this differs from existing approximated approaches [Luo et al., 2012; Liu et al., 2013; Xia et al., 2014b; Lu et al., 2014]. We have done empirical studies, which demonstrates the effectiveness of our method and show statistically significants improvements on compared algorithms.

2 RelatedWork

Multiple kernel learning has been actively studied [Xu et al., 2008; Tzortzis and Likas, 2012; Huang et al., 2012b; G¨onen and Margolin, 2014]. Based on the availability of class labels, multiple kernel learning can be categorized into two classes: supervised algorithms and unsupervised methods. Although supervised multiple kernel learning has been extensively studied [Xu et al., 2008; 2010; Hoi et al., 2013;

Xia et al., 2014a], unsupervised algorithm is more challenging due to the absence of class labels.

Several unsupervised algorithms have been developed in the framework of kernel k-means. [Tzortzis and Likas, 2012] proposed weighted kernel-based multi-view clustering including multi-view kernel k-means and multi-view spectral clustering respectively. [Yu et al., 2012] developed a multiple kernel k-means where the kernel combinational coefficients are optimized automatically. [Huang et al., 2012b] also presented a multiple kernel k-means and extended it to fuzzy k-means problem. [Zhuang et al., 2011] explored local information for multiple kernel learning.

Due to the connection between kernel k-means and spectral clustering, the latter has also been extended to deal with multiple kernels [Dhillon et al., 2004]. [Huang et al., 2012a] aggregated kernels with different weights into a unified one for spectral clustering. [Kumar et al., 2011] linearly combined spectral embeddings to get the final clustering. By resorting to the spectral method, [G¨onen and Margolin, 2014] also proposed to solve a multiple kernel k-means associated with two-layer weights.

All the above methods try to learn the consensus clustering via the linear combination of multiple input kernels. As discussed before, such integration schema has no mechanism for handling noises and outliers in kernels.

In contrast to our multiple kernel learning, [Xia et al., 2014b] proposed a method which learns a consensus matrix from a set of probabilistic transition matrices. Although this method also has a mechanism for handling noises, our method is designed for multiple kernel clustering while they are developed for transition matrices integration. Consequently, our noise structure and objective function constraints are totally different. The noises in transition matrix are sparse, while kernel noises are more sophisticated, i.e., they are symmetric with row-wise and column-wise sparsity. Besides, the consensus kernel is attached with additional complex constraints, i.e., symmetric, low-rank and p.s.d., which make it hard to solve.

3 Robust Multiple Kernel Learning

In this section, we present a framework for robust multiple kernel learning, and then introduce a method to solve the corresponding optimization problem.

3.1 Formulation

Given n instances, we calculate m kernels K(1) ,K(2) , ...,K(m) which are n × n matrices. The task of multiple kernel learning is to learn a consensus kernel matrix K from K(1) , ...,K(m) . As discussed before, instances may contain noises, and inappropriate kernels can be viewed as matrices with certain degree of noises. In particular, we have the following key observation. When the j-th instance is corrupted with noise, both the j-th row and the j-th column of the kernel are simultaneously contaminated. To alleviate the adverse effect of these noises, we introduce the row-wise sparse matrix E(i) ∈ Rn×n to capture noises on the rows of the i-th kernel. Naturally, E(i)T is a column-wise sparse matrix characterizing the column noises. As a result, the noises of the i-th kernel is obtained by the aggregation of E(i) and E(i)T , leading to the final symmetric error matrix E(i) + E(i)T . Then the cleaned matrix of the i-th kernel is K(i) -(E(i) +E(i)T ). To learn the final consensus kernel K from K(i) 's, we minimize the average disagreements between K and the cleaned matrices K(i) - (E(i) +E(i)T ). Thus, we have the following optimization problem for robust multiple kernel clustering.

where γ1 is a balancing parameter and ρ is a parameter in (0, 1). The ℓ2,1-norm is used to ensure the row sparsity of E(i) . The constraints on K ensure that K satisfies the properties of kernel matrix: symmetric and positive semidefinite. αi ≥ 0 is used to control the weight of kernel, and ∑mi=1 αρ i = 1 is to avoid trivial solution.

For the purpose of clustering, to obtain a more cleared cluster structure [Kulis et al., 2006], we also impose the low-rank constraint on the consensus kernel K; this is achieved by directly minimizing the rank of K. To sum up, we obtain the following formulation:

where γ2 is a balancing parameter. Note that the key of our formulation of multiple kernel clustering is the explicit characterization of error matrices E(i) + E(i)T , which makes it robust. Moreover, regarding the low-rank term, we do not use any approximation (neither convex nor non-convex approximation); this is different from previous ones such as those in [Luo et al., 2012; Liu et al., 2013; Xia et al., 2014b; Lu et al., 2014].

3.2 Optimization

The optimization problem in Eq.(2) involves three groups variables, i.e., K, E(i) , and αi. We develop an alternating minimization algorithm to solve this problem.

We introduce a diagonal matrix D(i) , where the j-th diagonal element is 1 2‖E(i) j ‖2 , and ‖E(i) j ‖2 is the ℓ2-norm of the j-th row of E(i) .

By setting the derivative of Eq.(3) w.r.t. E(i) to zero, we get

where I is an identity matrix. Denote A(i) = K(i) +K(i)T - K-KT , d(i) jj as the (j, j)-th element of D(i) and e(i) jk as the (j, k)-th element in E(i) . Considering the (j, k)-th element and (k, j)-th element on both sides of Eq.(4), we obtain

Solving Eq.(5), we get

Note that K and K(i) are symmetric, thus A(i) is also symmetric. We can simplify e(i) kj as

Theorem 1. Applying Eq.(6) monotonically decreases the objective function Eq.(3).

Proof. The detailed proof is similar as that in [Yang et al., 2011].

Optimize K by Fixing E(i) and αi

While fixing E(i) and αi, the Eq.(2) becomes

Let B = ∑mi=1 αi(K(i)-E(i)-E(i)T ) ∑mi=1 αi , τ = γ2 ∑mi=1 αi , and simplify Eq.(7) asmin

Let UKΣKVKT = K be the Singular Value Decomposition (SVD) of K. Since K should be symmetric and positive semi-definite, UK = [u1, ..., un], VK = [u1, ..., un], and

where λ1, ..., λn are n eigenvalues of K, u1, ..., un are corresponding eigenvectors of K. Similarly, let UBΣBVBT = B be the SVD decomposition of B. Because B is symmetric, UB = [v1, v2, ..., vn], VB = [sign(σ1) ∗v1, ..., sign(σn) ∗ vn], and

where σ1, ..., σn are n eigenvalues of B, v1, ..., vn are corresponding eigenvectors, and sign(·) is a sign function, i.e. sign(x) = -1 if x is negative and sign(x) = 1 otherwise.

Theorem 2. Let UKΣKVKT = K be the SVD decomposition of K, UBΣBVBT = B be the SVD decomposition of B, and λi, σi be as denoted before, then the solution of Eq.(8) is

Proof.

where tr(·) is the trace function. According to Von Neumanns trace inequality, we have tr(KBT ) ≤ tr(ΣKΣB), then

which leads to

Thus, to minimize Eq.(8), we should set UK = UB and VK = VB, i.e., the eigenvectors of K should be the same as eigenvectors of B. Note that K ⪰ 0, which means λi ≥ 0 leads to that if sign(σi) = -1, i.e. σi < 0, then λi must be zero.

To handle the rank function, we define function f:

Since the rank of K is the number of non-zero singular values of K, Eq.(8) can be rewritten as:

Note that if σi < 0, then λi = 0, so we drop all negative σi in Eq.(12):

Eq.(13) can be solved easily:

Next considering the case σi < 0 in addition, we get the final solution of λi:

To sum up, we get the global optima of this sub problem K = UBΣKVBT , where ΣK is obtained by Eq.(15). Since the input K(i) is kernel matrix which is symmetric, B is also symmetric and it leads to that K is also symmetric.

Optimize αi by Fixing E(i) and K

When K and E(i) are fixed, the optimization problem w.r.t. αi is:

where ri = ‖K - (K(i) - E(i) - E(i)T )‖2F + γ1‖E(i) ‖2,1. Introducing Lagrange multiplier l, we get

Setting the derivative w.r.t. αi to zero and considering ∑i αρ i = 1, we solve the l as l = - 1ρ (∑i r ρ ρ-1 i ) ρ-1 ρ and then obtain the solution of αi:

To sum up, we alternatively optimize E(i) , K, and αi until it converges. Algorithm 1 summarizes the whole process.

3.3 Convergence Analysis

Theorem 3. The iterative approach in Algorithm 1 converges.

Proof. Theorem 1 shows that updating E(i) as Eq.(6) can monotonically decreases the objective function Eq.(2). When updating K and αi, we find the global optima of the subproblem which also monotonically decreases the objective function. In addition, the objective function is always greater than 0. Thus Algorithm 1 converges.

3.4 Complexity Analysis

In each iteration, when updating E(i) , there are only elementwise optimizations, thus the complexity is O(n2m), where n is the number of instances and m the number of kernels. When updating K, the complexity is O(n3 ) due to the SVD decomposition. Computing αi just costs O(m). To sum up, in one iteration, the time complexity is O(n2m+n3 ), thus the total complexity is O((n2m+ n3 )q), where q is the number of iterations.

Algorithm 1 Robust Multiple Kernel Clustering

Input: multiple kernels K(1) , ...,K(m) , parameters γ1, γ2, ρ.

Output: the consensus kernel matrixK, error matrix of each kernel E(i) , kernel weights α.

• 1: Initialize K = 1m ∑mi=1 K(i) , αi = ( 1m ) 1ρ and E(i) = 12 (K(i) - K).
• 2: while not converge do
• 3: Compute E(i) as Eq.(6).
• 4: Compute UB,ΣB,VB as SVD decomposition of B.
• 5: Compute ΣK as Eq.(15) and obtain K as K = UBΣKVBT .
• 6: Compute α as Eq.(17).
• 7: end while

4 Experiment

To demonstrate the effectiveness of out method, we apply RMKC for clustering tasks and compare it with several stateof-the-art multiple kernel clustering methods on benchmark datasets.

4.1 Datasets

We collect 9 datasets, including 5 text corpora, i.e. CSTR [Du et al., 2012], BBCNews, Tr31, Hitech [Greene and Cunningham, 2005], News4a [Wu and Sch¨olkopf, 2006]; 3 image datasets, i.e., YALE [Belhumeur et al., 1997], JAFFE [Lyons et al., 1999], UCI Digits 1 and 1 chemical analysis dataset of wine, i.e., WINE 2 , which are frequently used in clustering task. Datasets from different areas serve as a good test bed for a comprehensive evaluation. The important statistics of these datasets are summarized in Table 1.

4.2 ComparedMethods

We compare the following algorithms

• Single kernel methods. Since we have multiple kernels, we run kernel k-means and spectral clustering on each kernel separately. Both the best and the average results over all kernels are reported, which are referred to as KKM-b, KKM-a, SC-b, SC-a, respectively. Due to space limitation, the worst results of single kernel are not

1 https://archive.ics.uci.edu/ml/datasets/Multiple+Features

2 https://archive.ics.uci.edu/ml/datasets/Wine

reported. It should be pointed out that the worst results are often far below the average.

• Equal weighted methods. The multiple input kernels are combined into a single kernel with equal weights. The results are referred to as KKM-ew and SC-ew.
• MKKM. 3 The MKKM (Multiple Kernel K-Means) is proposed in [Huang et al., 2012b] which extends kernel k-means in multiple kernel setting.
• Co-regSC. 4 The Co-regSC is a co-regularized multiview spectral clustering proposed by [Kumar et al., 2011].
• LMKKM. 5 The LMKKM is proposed in [G¨onen and Margolin, 2014]. It transfers the kernel k-means to spectral methods and uses the results from eigenvalue decomposition to clustering. Thus it is a spectral method in fact.
• RMSC. 6 The RMSC (Robust Multiview Spectral Clustering) is proposed by [Xia et al., 2014b]. We first transform the kernels into probabilistic transition matrices following [Xia et al., 2014b], and then apply RMSC to get the final clustering results.
• RMKC, which is our proposed method. We use RMKC to learn the consensus kernel, and then apply kernel k-means and spectral clustering on the learned kernel, which are referred to as RMKC-KM and RMKC-SC, respectively.

rar

3 http://imp.iis.sinica.edu.tw/IVCLab/research/Sean/mkfc/code.

4 http://www.umiacs.umd.edu/∼abhishek/code cospectral.zip

5 https://github.com/mehmetgonen/lmkkmeans

6 http://ss.sysu.edu.cn/∼py/RMSC.zip

4.3 Experiment Setup

Following the similar experimental protocol of other multiple kernel learning methods, we apply 8 different kernel functions as basis for multiple kernel clustering. These kernels are 5 RBF kernels K(xi, xj) = exp(-‖xi -xj‖2 /(2t2 )) with t = t0 ∗ dmax, where dmax is the maximal distance between samples and t0 varies in the range of {0.01, 0.1, 1, 10, 100}, 2 polynomial kernels K(xi, xj) = (xi T xj)a with a = 2, 4 and a linear kernel. Finally, all kernels are normalized to normalized-cut weighted form as [Xu and Gong, 2004] did and then rescaled to [0, 1].

The number of clusters is set to the true number of classes for all the datasets and clustering algorithms. The results of most of these compared algorithms depend on the initialization. We independently repeat the experiments for 10 times with random initializations and report the average results and t-test results. In our method, we tune ρ in {0.3, 0.5, 0.7}, and tune γ1 from [10-3 , 103 ], γ2 from [10-2 , 102 ] by grid search. For other compared methods, we tune the parameters as suggested in their papers.

Two clustering evaluation metrics are adopted to measure the clustering performance, including clustering Accuracy (ACC) and Normalized Mutual Information (NMI).

4.4 Experimental Results

We conduct two groups of experiment: we compare our methods RMKC-KM and RMKC-SC with k-means based methods and spectral clustering methods respectively. Table 2 and Table 3 show the results. Bold font indicates that the difference is statically significant (the p-value of t-test is smaller than 0.05). Note that since we aim to compare with other multiple kernel methods, we do not calculate the p-value of KKM-b, KKM-a, SC-b and SC-a.

The results reveal some interesting points:

• The performances of kernel k-means and spectral clustering are largely determined by the choice of kernel

functions. With a proper kernel function, these methods usually present good results. However, the performances are significantly deteriorated on inappropriate kernels. Such observations also motivate the development of multiple kernel clustering.

• With proper kernel weight learning schema, the multiple kernel clustering approaches usually improve the results over simple equally weighted combination.
• The proposed RMKC outperforms other methods significantly in most of the datasets. The performance of RMKC is usually close to or even better than the result of the best single kernel. Note that, RMKC does not need perform exhaustive search on a predefined pool of kernels. Such results well demonstrate the superiority of the proposed method.

4.5 Parameter Study

We explore the effect of parameters (γ1 and γ2) on clustering performance by tuning γ1 from [10-3 , 103 ] and γ2 from [10-2 , 102 ]. We show the ACC on CSTR and Hitech datasets. The results on other datasets are similar.

Figure 1 shows the ACC results, from which we can see that our algorithm is better than the closest baseline method for most of the γ1 and γ2 values. It indicates that the performance of our method is stable across a wide range of the parameters.

5 Conclusion

In this paper, we proposed a novel robust multiple kernel clustering method. We observed that the noises of kernels have specific structures, i.e., they are symmetric, row-wise and column-wise. Based on this observation, we introduced both row-sparse and column-sparse matrices to our multiple kernel formulation, such that robust and low-rank consensus kernel can be learned by minimizing the disagreement over the cleaned kernels. We provided an iterative algorithm to solve the hard optimization problem. Experimental results on real world datasets show that our method outperforms other compared methods.

In the future, we will study scalability issue with multiple kernel learning. Besides, we will further explore some common structure of noises in multiple kernels.

Acknowledgments

This work is supported in part by China National 973 program 2014CB340301 and NSFC grant 61379043, 61273291.