Robust Multiple Kernel K-means Using L21-Norm

1 Introduction

Clustering is one of the most important research topics in both machine learning and data mining communities. It aims at partitioning the data points into groups with similar objects. An enormous number and variety of methods have been proposed over the past decades. Due to the simplicity and the effectiveness, the k-means algorithm [Wu et al., 2008] becomes one of the most commonly-used methods for data clustering. However, the standard k-means algorithm is limited to the squared Euclidean distance and cannot identify arbitrarily shaped clusters.

∗Wenjian Wang is also affiliated with the Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University

†Corresponding Author

Kernel clustering algorithms have the ability to capture the non-linear structure inherent in many real world data sets and thereby usually achieve better clustering performance. The typical kernel-based clustering methods include: kernel kmeans [Sch¨olkopf et al., 1998] and spectral clustering [Ng et al., 2002]. Efforts have been made to further improve the result of kernel k-means. [Dhillon et al., 2007] shows that the spectral clustering can be equivalently reformulated as a weighted variant of kernel k-means. [Yu et al., 2012] and [Huang et al., 2012b] propose to integrate multiple information for clustering. [Chitta et al., 2011], [Chitta et al., 2012] and [Elgohary et al., 2014] develop efficient optimization schema to improve the scalability of kernel k-means to hanle large scale data.

Although kernel k-means based methods have attracted increasing attention in recent years, they still suffer from the following problems in real applications. First, these methods adopt the squared loss, which is well-known to be unstable with respect to outliers and noises, to measure the reconstruction error. As a result, a few noisy entries with large errors may easily dominate the result. Second, it is known that the performance of these single kernel methods are largely determined by the choice of kernel. Unfortunately, the most suitable kernel for a particular task is often unknown in advance. Moreover, exhaustive search on a user-defined pool of kernels will be quite time-consuming when the size of the pool becomes large [Zeng and Cheung, 2011]. In addition, real world data sets are often generated from different sources equipped with heterogeneous features. However, single kernel methods may fail to fully utilize such information. By leveraging multiple input kernels from different views or sources, multiple kernel methods are with great potential to integrate complementary information [Yu et al., 2012]. To alleviate the effort for kernel designing and make full use of complementary information, it is imperative to learn an appropriate kernel efficiently to make the performance of the kernel k-means robust or even improved. However, unlike the multiple kernel learning in supervised setting [G¨onen and Alpaydın, 2011], kernel learning in unsupervised scenario is more challenging due to the absence of class labels that could guide the search for relevant kernels.

To improve the robustness with respect to noises and outliers, we first propose a robust k-means method by using ℓ2,1norm to measure the distances between data points and cluster centers. To recap the powerfulness of kernel method, we also provide the robust k-means in kernel space. To alleviate the effort of kernel construction and make use of complementary information, we further propose a robust multiple kernel k-means (RMKKM) algorithm. In particular, RMKKM performs robust k-means with an appropriate consensus kernel learned from a linear combination of multiple input kernels. To solve the optimization problem where all the variables are encapsulated by the non-smooth ℓ2,1-norm, an alternating iterative algorithm is provided to find the optimal value. Experimental results on benchmark data sets have shown that the proposed approaches achieve better clustering results in both the single kernel and multiple kernel learning settings.

The rest of the paper is organized as follows. The robust multiple kernel k-means is introduced in Section 2. Section 3 provides the optimization schema. A variety of experimental results are presented in Section 4. Finally, we provide some concluding remarks in Section 5.

Notations. In this paper, matrices are written as uppercase letters and vectors are written as boldface lower-case letters. Given a matrix A = {aij}, we denote its i-th column as ai. The ℓ2-norm of a vector x is defined as ||x||2 = √xT x. The ℓ2,1-norm of a matrix is defined as ||A||2,1 = ∑ni=1 √∑mj=1 a2ij = ∑ni=1 ||ai||2.

2 Robust Multiple Kernel K-means

In this section, we first present the robust k-means using the ℓ2,1-norm. Then we extend it to kernel space and get robust multiple kernel k-means. To improve the effectiveness of kernel method, we further propose a novel robust multiple kernel k-means (RMKKM) algorithm for data clustering.

2.1 Robust K-means

Suppose we are given a data set X = [x1, x2, · · · , xn] ∈ Rd×n , and aim to partition these data points into c disjoint clusters {C1, C2, . . . , Cc}. The k-means algorithm finds optimal solutions with respect to the clustering error, defined as the sum of squared Euclidean distance between each data point xi and the cluster center uj where xi belongs to. The objective function of k-means can be written as

where U ∈ Rd×c is the cluster centroid matrix, and Z ∈ Rn×c is the cluster indicator matrix.

Though the k-means algorithm has been widely used for data clustering, it is known that the squared loss used in Eq. (1) is very sensitive to data outliers, and they greatly affect the performance of clustering. In order to have a more stable result with respect to a fixed initialization, the robust k-means algorithm is desired. Inspired by the recent developed robust multi-view k-means [Cai et al., 2013], we also use the ℓ2,1norm to measure the reconstruction error, and get the following problem

where the ℓ1-norm is imposed among data points and the ℓ2norm is used for features. By introducing the sparsity induced norm, ℓ2,1-norm, the effects of data outliers can be reduced and a more robust result is expected.

2.2 Robust Kernel K-means

The effectiveness of k-means is largely limited to spherical clusters, that is, the clusters must be linearly separable [Dhillon et al., 2004]. By applying kernel trick, the kernel kmeans [Sch¨olkopf et al., 1998] algorithm attempts to address this problem by mapping data with non-linear transformation into appropriate feature space and applying k-means on the induced feature space. This can lead to linear separated clusters in the new feature space while these clusters are not linear separable in the original space. Thus, kernel k-means is much preferred for general clusteringn [Bishop and others, 2006].

Similar to the kernel k-means algorithm, the proposed robust k-means in Eq. (2) can also be easily extended to the kernel version by using a general kernelization framework [Zhang et al., 2010]. Let φ : Rd → H be a kernel mapping from the original space to the kernel space, where H is a Reproducing Kernel Hilbert Space (RKHS) induced by a kernel function K(x, z) = φ(x)T φ(z). Then φ(X) = [φ(x1), φ(x2), · · · , φ(xn)], and the robust k-means in Eq. (2) in the kernel space becomes:

where V is the cluster center matrix in the implicit feature space. It can be shown later (see Eq. (11)), the j-th cluster center vj can be determined by vj = ∑i aijφ(xi), where aij is the membership of xi belongs to j-th cluster. Hence, the above problem can be re-written as

where the kernel matrix is denoted by K ∈ Rn×n and the (i, j)-th entry of K is kij = φ(xi)T φ(xj).

2.3 Robust Multiple Kernel K-means

The proposed method above only works for single kernel data clustering. However, one of the central problems with kernel methods in general is that it is often unclear which kernel is the most suitable for a particular task. In this subsection, we further extend the above method to automatically learn an appropriate kernel from the convex linear combination of several pre-computed kernel matrices within the multiple kernel learning framework [G¨onen and Alpaydın, 2011].

Suppose there are altogether m different kernel functions {K}mt=1 available for the clustering task in hand. Accordingly, there are m different associated feature spaces denoted as {H}mt . To combine these kernels and also ensure that the resulted kernel still satisfies Mercer condition, we consider a nonnegative combination of these feature maps, φ′ , that is,

Unfortunately, as these implicit mappings do not necessarily have the same dimensionality, such a linear combination may be unrealistic. Hence, we construct an augmented Hilbert space ˜H = ⊕mt=1Hi by concatenating all feature spaces ˜ φ(x) = [√w1φ1(x); √w2φ2(x); . . . ; √wmφm(x)]T with different weight √wt(wt ≥ 0) , or equivalently the importance factor for kernel function Kt . It can be verified that clustering in feature space ˜H is equivalent to employing a combined kernel function [Zeng and Cheung, 2011]

It is known that the convex combination, with w(wt ≥ 0), of the positive semi-definite kernel matrices {K}mt=1 is still a positive semi-definite kernel matrix. By replacing the single kernel in Eq. (4) with the combined kernel, we propose a new Robust Multiple Kernel k-means method by solving:

where γ is the parameter to control the kernel weight distribution with 0 < γ < 1. It should be noticed that RMKKM aims at improving the stability of kernel k-means without suffering the choice of appropriate kernel functions, where the weak kernels can be computed either on single view or multi-view data [Cai et al., 2013].

3 Optimization Algorithm and Analysis

The optimization problem in Eq. (7) is not convex in all variables together, but convex in them separately. The difficulty of solving the proposed objective mainly lies that all variables are encapsulated into a non-smooth ℓ2,1-norm. In the following, we introduce an iterative algorithm based on block coordinate descent to solve it. We separately update the value of A, Z, and w while holding the other variables as constant. Thus, a local minima can be expected by solving a sequence of convex optimization problems.

3.1 Optimizing w.r.t. cluster centroid when Z and w are fixed

Recall that, we have introduced cluster centroid matrix V in the implicit feature space in Eq. (3), conceptually we further denote ˜ vj to be the concatenated implicit representations for j-th cluster center. The optimization problem in Eq. (7) with respect to the cluster centroid matrix can be re-written as

It can be verified that the derivative of J is equivalent to the derivative of the following proxy function L( ˜ V ),

Actually, the above problem is the weighted version of kernel k-means [Dhillon et al., 2004]. By setting the derivative to be zero, we have

Thus, it is clear that the cluster centroid matrix for robust (multiple) kernel k-means can be determined by the weighted combination of the data in implicit feature space, where the membership matrix A can be computed by

And the actual value of Dii can be computed by

3.2 Optimizing w.r.t. partition matrix Z when A and w are fixed

The minimization of the objective function in Eq. (7) with respect to Z can be decomposed into solving n independent sub-problems, that is

where zij = {0, 1}, ∑cj=1 zij = 1. And, the optimal solution of the above problem is given by

3.3 Optimizing w.r.t. kernel weight w when A and Z are fixed

By defining E ∈ Rn×m with

the optimization of Eq. (7) with respect to w can be simplified as solving the following problem

It is obvious that the derivative in Eq. (17) can also be regarded as the derivative of the following objective function

where ht is denoted as

The Lagrange function of Eq. (18) is J (w) = wT h+λ(1∑t wγ t ). By using the KKT condition ∂J(w) ∂wt wt = 0 and the constraint ∑mt=1 wγ t = 1, the optimal solution of w can be obtained by

In summary, we present the alternating iterative algorithm for optimizing Eq. (7) in Algorithm 1.

Algorithm 1 The algorithm of RMKKM

Input: A set of kernels {Kt}mt=1 , the desired number of cluster c and the parameter γ.

Initialize the indicator matrix Z randomly, such that Z satisfies zij = {0, 1} and ∑j zij = 1;

Initialize the kernel weight wt = 1/m for each kernel;

Initialize the diagonal matrix D = In, where In is the identity matrix;

repeat

Update the membership matrix A by Eq. (12);

Update the cluster indicator matrix Z by Eq. (15);

Update the kernel weight w by Eq. (20);

Update the diagonal matrix D by Eq. (13);

until Converges

Output: Partition matrix Z, membership matrix A, and the kernel weights w.

3.4 Convergence Analysis

The optimization problem of Eq. (7) is a convex problem with respect to one variable while holding the others. For each subproblem, our algorithm will guarantee that we can find the optimal solution. Therefore, by solving these subproblems alternatively, our algorithm will reduce the objective function monotonically. Meanwhile, the whole problem is lower bounded. Thus, the convergence of the proposed algorithm can be verified.

3.5 Complexity Analysis

In the following, we give the complexity analysis of the optimization algorithm. Initially, we need to compute the n × n × m kernel matrices {K}mt=1 , whose cost is generally O(n2dm). In each iteration, the cost of updating A by Eq. (12) is O(nc), the cost of updating Z by Eq. (15) is O((n2 + n)cm), the cost of updating w by Eq. (20) is O((n2 + n)nm+ nm+m), and the cost of updating D by Eq. (13) is O((n2 + n)nm). Since c ≪ n, the total cost is O(n2dm+ (n3 + n2 + n)ml), where l is the number of iterations. Compared with kernel k-means with fixed kernel weights and sample weights, the proposed algorithm is less efficient due to the involvement of updating kernel weight w and sample weight D.

3.6 Discussion of the parameter γ

The parameter γ is used to control the distribution of weights for different kernels. From Eq. (20), we can observe that when γ → 1, we will assign 1 to the kernel whose ht is the smallest and assign 0 to the weights of other kernels. And when γ → 0, we will get equal weights. With this strategy, we can avoid the trivial solution of the kernel weights w and control the whole weights distribution flexibly.

4 Experimental Results

In this section, we evaluate the clustering performance of the proposed algorithm on a number of real world data sets.

4.1 Data Sets

We collect a variety of data sets, including 6 image data sets and 3 text corpora, most of which have been frequently used to evaluate the performance of different clustering algorithms. The statistics of these data sets are summarized in Table 1.

4.2 Compared Algorithms

To demonstrate how the clustering performance can be improved by the proposed approaches, we compared the results of the following algorithms:

• Single kernel methods. Since we have multiple input kernels in hand, we run Kernel K-means (KKM), Spectral Clustering (SC) [Ng et al., 2002], and Robust Kernel K-means (RKKM) in Eq. (4) on each kernel separately. And both the best and the average results over all these kernels are reported, which are referred to KKM-b, KKM-a, SC-b, SC-a, RKKM-b, RKKM-a, respectively. Due to space limitation, the worst results for single kernel are not 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, and then report the results of KKM-ew, SC-ew, RKKM-ew. Note that such strategy often gets more stable results in multiple kernel learning [G¨onen and Alpaydın, 2011].
• MKKM 1 . The MKKM proposed in [Huang et al.,

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

• 2012b] also extends k-means in multiple kernel setting. Both the loss function and the constraint on the kernel weight distribution are different to our method.
• AASC 2 . The AASC algorithm is proposed in [Huang et al., 2012a] for multiple affinities aggregation.
• RMKKM 3 . The proposed robust multiple kernel kmeans method for data clustering.

4.3 Experiment Setup

Following the similar strategy of other multiple kernel learning approaches, we apply 12 different kernel functions as basis for multiple kernel clustering. These ker-

rar.

2 http://imp.iis.sinica.edu.tw/IVCLab/research/Sean/aasc/code. rar.

3 For the purpose of reproducibility, we provide the code at https: //github.com/csliangdu/RMKKM.

nels include, seven RBF kernels K(xi, xj) = exp(-||xi - xj||2 /2δ2 ) with δ = t ∗ D0, where D0 is the maximum distance between samples and t varies in the range of {0.01, 0.05, 0.1, 1, 10, 50, 100}, four polynomial kernels K(xi, xj ) = (a+xTi xj )b with a = {0, 1} and b = {2, 4} and a cosine kernel K(xi, xj) = (xTi xj)/(||xi|| · ||x||). Finally,

all the kernels have been normalized through K(xi, xj) = K(xi, xj)/√K(xi, xi)K(xj , xj) and then rescaled to [0, 1]. The number of clusters is set to the true number of classes for all the data sets and clustering algorithms. For SC and AASC, the discrete clustering result is obtained by running k-means on spectral embedding. For the proposed method RMKKM, the parameter γ to control the kernel weight distribution is set to 0.3. In addition, the results of all these compared algorithms depend on the initialization. As suggested in [Yang et al., 2010], we independently repeat the experiments for 20 times with random initializations and report the best results corresponding to the best objective values.

Three clustering evaluation metrics are adopted to measure the clustering performance, that is, Clustering Accuracy (Acc), Normalized Mutual Information(NMI) and Purity.

4.4 Experimental Results

Table 2 shows the clustering results in terms of accuracy, NMI and purity on all the data sets. Both the best results for single kernel methods and multiple kernel methods are highlighted in boldface. These experiments reveal a number of interesting points: 1)The performance of single kernel methods (the first 6 columns), i.e., KKM, SC, RKKM, is largely determined by the choice of kernel function. On the one hand, with proper kernel function, these methods usually present good results. On the other hand, their performances are significantly deteriorated on inappropriate kernels. Such observations also motivate the development of robust kernel k-means for multiple kernel learning. Besides, it can also be seen that the proposed RKKM give best results on 5 data sets with single input kernel. 2)Clustering on the equal weighted multiple kernel combination often gives more reasonable and reliable results. Thus, it could be expected that with much carefully designed kernel weighting schema, the performance of multiple kernel clustering can be further boosted. 3)With proper kernel weight learning schema, the multiple kernel clustering approaches usually improve the results over simple equally weighted combination. 4)The proposed RMKKM gives the best results on these data sets for multiple kernel clustering. The performance of RMKKM is usually better or close to the result on the best single kernel. Note that, RMKKM does not need perform exhaustive search on a predefined pool of kernels. Such results well demonstrate the superiority of our method.

4.5 Parameter Selection

Our proposed method RMKKM introduces the parameter γ to control the kernel weight distribution. The effect of the parameter γ has been discussed in previous section. Here, we evaluate it empirically. Figure 1 shows how the clustering result in terms of NMI varies with the parameter γ on two image data sets, JAFFE and ORL, and two document data sets, TR11 and TR41.

As we can see, the performance of RMKKM is very stable with respect to the parameter γ. Compared with the average performance of single kernel method, i.e., KKM-a, and the result of equally weighted kernel fusion, i.e., KKM-ew, the RMKKM achieves consistently good performance when γ varies from 0.3 to 0.9 on all four data sets.

5 Conclusion

In this paper, we presented a robust k-means method which uses ℓ2,1-norm to quantify the distances between data points and cluster centers. Then we extended it to perform robust kmeans in the kernel space. To fully recap the powerfulness of kernel methods, we further proposed a robust multiple kernel k-means algorithm for clustering, i.e. RMKKM. It automatically learns an appropriate kernel from a lot of input kernels, which significantly reduces the effort of kernel designing or selection. Experimental results well demonstrate the superiority of the proposed method on benchmark data sets with multiple input kernels.

It has been shown that, given the kernel weight, the remained problem can be finally reformulated as a adaptively weighted kernel k-means (see Eq. (9)). Thus, in the future, we plan to investigate the use of the Nystr¨om method [Elgohary et al., 2014] and the random fourier feature [Yang et al., 2012] to make the proposed algorithms more efficient in terms of computational and memory complexity. Besides, we want to further investigate the effectiveness of the proposed method on multi-view and multi-source data clustering, where a bundle of input kernels is also available.

6 Acknowledgments

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

61203241, 61473212, Shanxi Scholarship Council of China (No.2012-008), Open Project Foundation of Information Technology Research Base of Civil Aviation Administration of China (No. CAAC-ITRB-201305).