Multiple Kernel Clustering with Local Kernel Alignment Maximization

Introduction

Multiple kernel clustering (MKC) aims to optimally integrate a group of pre-specified kernels to improve clustering performance [Zhao et al., 2009; Lu et al., 2014; Xia et al., 2014; Zhou et al., 2015; Kumar and Daum´e, 2011]. Existing research in this regard can roughly be grouped into two categories. The first one learns a consensus matrix via lowrank optimization [Xia et al., 2014; Zhou et al., 2015; Kumar and Daum´e, 2011]. The work in [Xia et al., 2014] firstly constructs a transition probability matrix from each single view, and them uses them to recover a shared lowrank transition probability matrix as a crucial input to the standard Markov chain method for clustering. In [Zhou et al., 2015], it is proposed to capture the structures of noises in each kernel and integrate them into a robust and consensus

Yong Dou, Jianping Yin, En Zhu

School of Computer National University of Defense Technology

Changsha, China, 410073

framework to learn a low-rank matrix. The algorithm [Kumar and Daum´e, 2011] learns the clustering in one view and uses it to "label" the data in other views to modify a similarity matrix. By following multiple kernel learning (MKL) framework, the other category optimizes a group of kernel coefficients, and uses the combined kernel for clustering [Yu et al., 2012; G¨onen and Margolin, 2014; Du et al., 2015; Lu et al., 2014]. Along this line, the work in [Yu et al., 2012] proposes a multiple kernel k-means clustering algorithm. In [G¨onen and Margolin, 2014], the kernel combination weights are allowed to adaptively change with respect to samples to better capture their individual characteristics. By replacing the squared error in k-means with an `2↪1-norm based one, [Du et al., 2015] presents a robust multiple kernel k-means algorithm that simultaneously finds the best clustering labels and the optimal combination of multiple kernels. In [Lu et al., 2014], kernel alignment maximization is employed to jointly perform the k-means clustering and MKL. Our work in this paper belongs to the second category.

Among the above clustering algorithms in the second category, the kernel alignment maximization criterion for clustering [Lu et al., 2014] has demonstrated promising performance. Actually, according to [Liu et al., 2016], many classic MKC criteria such as [Yu et al., 2012; G¨onen and Margolin, 2014] can be interpreted from the perspective of kernel alignment maximization, suggesting the importance of this criterion for clustering. Nevertheless, although this alignment has the aforementioned good properties, we observe that it is implemented in a global manner, which: i) rigidly forces closer and farther sample pairs to be equally aligned to the same ideal similarity, and inappropriately neglects the intra-cluster variation of samples; and ii) is inconsistent with a well-established concept that the similarity evaluated for two farther samples in a high dimensional space is less reliable due to the presence of underlying manifold structure. As a result, maximizing global alignment could make these pre-specified kernels less effectively utilized, and in turn adversely affect the clustering performance.

To address these issues, we propose a novel MKC algorithm with a "local" kernel alignment. In specific, this local alignment only requires that the similarity of a sample to its k-nearest neighbours be aligned with the ideal similarity matrix. Such an alignment helps the clustering process to focus on closer sample pairs that shall stay together, avoids involving unreliable similarity evaluation for farther sample pairs, and also give the clustering process more flexibility to arrange the farther pairs according to the nature of data distribution. By this way, the local structure of the data can be well utilized to produce better alignment for clustering. After that, the optimization objective of the proposed local kernel alignment is carefully designed and an efficient algorithm with proved convergence is developed to solve the resultant optimization problem. Extensive experimental study has been conducted on six MKL benchmark data sets to evaluate clustering performance of the proposed algorithm. As indicated, our algorithm significantly outperforms the state-of-the-art ones, validating the effectiveness and advantage of the proposed local kernel alignment maximization.

Related Work

Kernel k-means clustering (KKM)

Let ¶xi♦ni=1 ✓ X be a collection of n samples, and φ(·) : x 2 X 7! H be a feature mapping which maps x onto a reproducing kernel Hilbert space H. The objective of kernel kmeans clustering is to minimize the sum-of-squares loss over the cluster assignment matrix Z 2 ¶0↪ 1♦n⇥k , which can be formulated as the following optimization problem,

where nc = Pni=1 Zic and θc = 1 nc Pni=1 Zicφ(xi) are the number and centroid of the c - th (1  c  k) cluster.

The optimization problem in Eq.(1) can be equivalently rewritten as the following matrix-vector form,

where K is a kernel matrix with Kij = φ(xi)>φ(xj)↪ L = diag([n-1 1 ↪ n-1 2 ↪ · · · ↪ n-1 k ]) and 1` 2 R` is a column vector with all elements 1.

The variables Z in Eq.(2) is discrete, which makes the optimization problem very difficult to solve. However, this problem is usually approximated through relaxing Z to take arbitrary real values. Specifically, by defining H = ZL 12 and letting H take real values, we obtain a relaxed version of the above problem.

where Ik is an identity matrix with size k ⇥ k. Noting that Z>Z = L-1 , it can be obtained that L 12Z>ZL 12 = Ik, and this leads to the orthogonality constraint on H. Finally, one can obtain the optimal H for Eq.(3) by taking the k eigenvectors that correspond to the k largest eigenvalues of K.

Multiple kernel k-means clustering (MKKM)

In a 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 that needs to be optimized during learning. Correspondingly, the kernel function over the above mapping function can be calculated as

By replacing the kernel matrix K in Eq.(3) with Kθ computed via Eq.(4), the following optimization objective is obtained for MKKM,

This problem can be solved by alternately updating H and θ: i) Optimizing H given θ. With the kernel coefficients θ fixed, the H can be obtained by solving a kernel k-means clustering optimization problem in Eq.(3); ii) Optimizing θ given H. With H fixed, θ can be optimized via solving the following quadratic programming with linear constraints,

As noted in [Yu et al., 2012; G¨onen and Margolin, 2014], using a convex combination of kernels Pmp=1 θpKp to replace Kθ in Eq.(5) is not a viable option, because this could make only one single kernel be activated and all the others assigned with zero weights. Also, other recent work using `2norm combination can be found in [Kloft et al., 2011; 2009; Cortes et al., 2009].

Proposed Formulation

The Connection Between MKKM and Unsupervised Kernel Alignment Maximization

As a well-established criterion, kernel alignment maximization has been widely used to tune kernel parameters in supervised learning [Cortes et al., 2012]. Nevertheless, this criterion is not readily applicable to clustering since the true labels in unsupervised learning is absent. A promising remedy is to update kernel coefficients by maximizing the alignment between the combined kernel Kθ and HH>, where H can be treated as pseudo-labels in the last iteration [Liu et al., 2016]. In specific, the kernel alignment maximization for clustering can be fulfilled as,

where hKθ↪HH>iF = Tr(KθHH>), hKθ↪KθiF = ˆθ>Mˆθ with ˆθ = [θ21 ↪ · · · ↪ θ2m]> and M is a positive semidefinite matrix with Mpq = Tr(K>p Kq) [Cortes et al., 2012].

Although Eq.(7) is not difficult to understood, directly optimizing it is difficult since it is a fourth-order fractional optimization problem. In the following, we derive a new and related optimization problem from this kernel alignment maximization problem, based on the following two results.

Theorem 0.1 provides a second-order upper bound for the denominator in Eq.(7).

Theorem 0.1 θ>Mθ is an upper bound of ˆθ>Mˆθ.

Proof 1 For any positive semi-definite matrices Kp and Kq, there exists matrices Up and Uq such that Kp = UpU>p and Kq = UqU>q . Consequently, Mpq = Tr(K>p Kq) = Tr(UpU>p UqU>q ) = Tr((U>p Uq)(U>p Uq)>) = kU>p Uqk2F ≥ 0, where k · kF denotes Frobenius norm. Also, we have θ>Mθ = Pmp↪q=1 Mpqθpθq ≥ Pmp↪q=1 Mpqθ2pθ2q = ˆθ>Mˆθ since θ 2 Rm+ ↪ θ>1m = 1 and Mpq ≥ 0. This completes the proof.

Compared with ˆθ>Mˆθ, θ>Mθ is much easier to handle since it leads to a well studied quadratic programming. Moreover, this term can be treated as a regularization on the kernel coefficients to prevent θp and θq from being jointly assigned to a large weight if Mpq is relatively high.

In addition, we find that minimizing the negative of numerator, i.e., -Tr(KθHH>), together with θ>Mθ simultaneously cannot guarantee that the whole objective is convex w.r.t θ with fixed H. This would affect the quality of solution at each iteration, leading to unsatisfying performance. Fortunately, the following Theorem gives a good substitute of -Tr(KθHH>) while with convexity.

Theorem 0.2 Tr (Kθ(In -HH>)) is convex w.r.t θ with fixed H.

Proof 2 We have HH>H = H since H>H = Ik. By denoting H = [h1↪ · · · ↪ hk], we can see that HH>hc = hc, 81  c  k. This means HH> has k eigenvalue with 1. Meanwhile, its rank is no more than k, which implies its has n - k eigenvalue with 0. Correspondingly, In -HH> has n-k and k eigenvalue with 1 and 0. As a result, Tr (Kp(In -HH>)) ≥ 0. Tr (Kθ(In -HH>)) = Pmp=1 θ2pTr (Kp(In -HH>)), which is therefore convex w.r.t θ. This completes the proof.

Based on the above-mentioned observations, instead of maximizing the kernel alignment by solving a fractional optimization in Eq.(7), we turn to minimize the following,

Actually, Tr (Kθ(In -HH>)) can be intuitively understood by adding a prior Pmp=1 θ2pTr (Kp) on -Tr(KθHH>) to guarantee its convexity with θ.

where λ is introduced to trade off the two terms.

The above results will be used in the next section to develop our optimization problem for the proposed local kernel alignment.

Multiple Kernel Clustering with Local Kernel Alignment Maximization

As seen, Eq.(7) (or Eq.(8)) maximizes the alignment between the combined kernel matrices Kθ and the ideal kernel matrix HH> globally. By following the analysis in introduction, such a global criterion: i) indiscriminately forces closer and Algorithm 1 Multiple Kernel Clustering with Local Kernel Alignment Maximization

• 1: Input: ¶Kp♦mp=1, k, λ and ✏0.
• 2: Output: H and θ.
• 3: Initialize θ(1) = 1m◁m and t = 1.
• 4: Generating S(i) for i-th samples (1  i  n) by Kθ(1) .
• 6: K(t) θ = Pmp=1 ⇣θ(t) p ⌘2Kp.
• 5: repeat
• 7: Update H(t) by solving Eq.(12) with given K(t) θ .
• 8: Update θ(t) by solving Eq.(13) with given H(t) .
• 9: t = t + 1.

farther sample pairs to be equally aligned to the same ideal similarity, and inappropriately neglects the intra-cluster variation of samples; and ii) is inconsistent with a well-established concept that the similarity evaluated for two farther samples in a high dimensional space is less reliable. These two drawbacks could adversely impact the clustering performance. In this paper, instead of enforcing the global alignment of all samples, we propose to locally align the similarity of each sample to its k-nearest neighbours with corresponding ideal kernel matrix, which is flexible and able to well handle the intra-cluster variations. In specific, the local kernel alignment for the i-th sample can be calculated as,

where K(i) θ and H(i) are sub-matrix of Kθ and H whose indices are specified by the ⌧-nearest neighbors of the i-th sample, andM(i) is a matrix withM (i) pq = Tr(K(i) p >K(i) q ).

By following the aforementioned analysis in subsection , Eq.(9) can be conceptually rewritten as,

where K(i) θ = S(i)>KθS(i) , H(i) = S(i)>H, S(i) 2 ¶0↪ 1♦n⇥⌧ is a matrix indicating the ⌧-nearest neighbors of the i-th sample and I⌧ is an identity matrix with size ⌧ .

By taking over the local kernel alignment in Eq.(10) for each sample and defining A(i) = S(i)S(i)>, we obtain the objective function of our proposed algorithm as follows,

Alternate optimization

Although the kernel alignment is maximized in a localized way, the resultant optimization problem in Eq.(11) is not altered significantly and still easy to solve by existing off-theshelf packages. In specific, we design a two-step algorithm to solve this problem alternately. (i) Optimizing H with fixed θ. Given θ, H can be obtained by solving the following optimization problem,

which is a standard kernel k-means clustering problem and can be efficiently solved; (ii) Optimizing θ with fixed H. Given H, the optimization in Eq.(11) w.r.t θ is a quadratic programming with linear constraints, which essentially solves the following problem,

In sum, our algorithm for solving Eq.(11) is outlined in Algorithm 1, where obj(t) denotes the objective value at the t-th iterations. It is worth pointing out that the neighborhood of each sample is kept unchanged during the optimization. In specific, the ⌧-nearest neighbors of each samples are measured by Kθ(1) . By doing so, the objective of Algorithm 1 is guaranteed to be monotonically decreased when optimizing one variable with the other fixed at each iteration. At the same time, the whole optimization problem is lower-bounded. As a result, the proposed algorithm can be guaranteed to be convergent. We also record the objective at each iteration and the results validate the convergence. The algorithm usually converges in less than ten iterations in all of our experiments.

Experiments

Data sets

The proposed algorithm is experimentally evaluated on six widely used MKL benchmark data sets shown in Table 1. They are UCI-Digital 1 , Oxford Flower17 2 , Protein fold prediction 3 , YALE 4 , Oxford Flower102 5 and Caltech102 6 .

For ProteinFold, we generate 12 base kernel matrices by following [Damoulas and Girolami, 2008], where the second order polynomial kernel and inner product (cosine) kernel are applied to the first ten feature sets and the last two feature sets, respectively. For YALE, five base kernel matrices are constructed according to [Zhou et al., 2015]. For the rest of the other data sets, all kernel matrices are pre-computed and publicly downloaded from the above websites.

Compared algorithms

Many recently proposed method are compared, including

• ÷ Average multiple kernel k-means (A-MKKM): All kernels are uniformly weighted to generate a new kernel, which is taken as the input of kernel k-means.
• ÷ Single best kernel k-means (SB-KKM): Kernel k-means is performed on each single kernel and the best result is reported.
• ÷ Multiple kernel k-means (MKKM) [Huang et al., 2012]: The algorithm alternately performs kernel k-means and updates kernel coefficients.
• ÷ Localized multiple kernel k-means (LMKKM) [G¨onen and Margolin, 2014]: LMMKM combines the kernels by sample-adaptive weights.
• ÷ Robust multiple kernel k-means (RMKKM) [Du et al., 2015]: RMKKM improves the robustness of MKKM by replacing the sum-of-squared loss with an `2↪1-norm one.
• ÷ Co-regularized spectral clustering (CRSC) [Kumar and Daum´e, 2011]: CRSC provides a co-regularization way to perform spectral clustering.
• ÷ Robust multiview 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 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.

The Matlab codes of KKM, MKKM and LMKKM are publicly available at https://github.com/mehmetgonen/lmkkmeans. For RMKKM, CRSC, RMSC and RCE, we use their matlab implementations from authors' websites in our experiments.

Experimental settings

In all our experiments, all base kernels are first centered and then scaled so that for all i and p we have Kp(xi↪ xi) = 1 by following [Cortes et al., 2012; 2013]. For all data sets, it is assumed that the true number of clusters is known and set as the true number of classes. The parameters of RMKKM, RMSC and RMKC are selected by grid search according to the suggestions in their papers. For the proposed algorithm, its regularization parameters λ and ⌧ are chosen from [2-15 ↪ 2-13 ↪ · · · ↪ 215 ] and [0▷05↪ 0▷1↪ · · · ↪ 0▷95] ⇤ n by grid search, where n is the number of samples.

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 affect of randomness caused by k-means, and report the best result.

Experimental results

The ACC, NMI and purity of the above-mentioned algorithms on the six data sets are reported in Table 2. We have the following observations from these results:

• ÷ Our algorithm demonstrates the best clustering performance in terms of clustering accuracy, NMI and purity on all data sets. Taking the results in Table

2 as an example, it exceeds the second best one by 5▷85%, 9▷85%, 3▷03%, 5▷45%, 3▷58% and 3▷92% on Digital, Flower17, ProteinFold, YALE, Flower102 and Caltech102, respectively. Also, its superiority is also confirmed from the NMI and purity reported in Table 2.

• ÷ The proposed algorithm significantly outperforms exiting MKKM, which can be seen as a special case of global kernel alignment. In specific, the clustering accuracy of MKKM is only 47% on Digital, which implies that it may even not work on this data set. In contrast, our algorithm achieves 96▷25%, which is the best result among all the compared ones.
• ÷ As a strong baseline, A-MKKM usually demonstrates comparable or even better performance than most of algorithms in comparison. However, our algorithm clearly outperforms this baseline on all data sets, which indicates its superiority in clustering performance.

Table 2 also reports the comparison of NMI and purity. Again, we observe that the proposed algorithm significantly outperforms the compared ones. In all, these results have well verified the effectiveness of maximizing the kernel alignment in a local way.

To investigate the clustering performance with respect to the number of classes, we select samples from the first 10↪ 20↪ · · · ↪ 100 classes on both Flower102 and Caltech102, where 20 and 15 samples are randomly selected for each class. By this way, we generate ten data sets on Flower102 and Caltech102, respectively.

The ACC, NMI and purity of the above-mentioned algorithms with different number of classes on Flower102 are plotted in sub-figures 1(a), 1(b) and 1(c). As shown, our algorithm (in red) consistently keeps on the top of all subfigures, indicating the best performance. Meanwhile, we also find similar results from the results on Caltech102 in subfigures 1(d), 1(e) and 1(f). Moreover, we report the aggregated ACC, NMI and purity of each algorithm, which is defined as the mean of ACC (NMI, purity) on Flower102 or Caltech102 with the number of classes varied in the range of 10↪ 20↪ · · · ↪ 100, as shown in Table 3. Again, our algorithm is superior to other compared algorithms in terms of the aggregated ACC, NMI and purity.

From the above experiments, we can conclude that the proposed algorithm: i) effectively addresses the issues of indiscriminately forcing all sample pairs to be equally aligned to the same ideal similarity; and ii) well utilizes the local structure of data to significantly improve clustering performance. Our local kernel alignment is flexible and allows the prespecified kernels to be aligned for better clustering, bringing the significant improvements on clustering performance.

Parameter selection and Convergence

As can be seen in Eq.(11), our algorithm introduces the number of neighbors ⌧ and regularization parameter λ. We then experimentally show the effect of each parameter on the performance of our algorithm by fixing the other on Digital.

Figure 2(a) plots the ACC of our algorithm by varying ⌧ in a large range [0▷05↪ 0▷1↪ · · · ↪ 0▷95] ⇤ n with λ = 2-1 . From this figure, we observe: i) with the increase of ⌧, the ACC first maintains on a high value and then decreases, validating the effectiveness of maximizing the local kernel alignment; and ii) our algorithm shows stable performance across a wide range of ⌧. Similarly, Figure 2(b) presents the ACC of our algorithm by varying λ from 2-15 to 215 with ⌧ = 0▷05. Again, our algorithm demonstrates stable performance across a wide range of λ. These results indicate that the performance of our method is stable across a wide range of parameters.

An example of the objective value of our algorithm at each iteration is plotted in Figure 2(c). As observed from this example, the objective value is monotonically decreased and the algorithm quickly converges in less than ten iterations.

Conclusions

This work proposes the multiple kernel clustering algorithm by maximizing the kernel alignment locally-a more flexible and effective algorithm which well handles the issue of indiscriminately forcing all sample pairs to be equally aligned to the same ideal similarity and integrates the underlying local structure of data to achieve better alignment for clustering. A two-step algorithm with proved convergence is designed to solve the resultant optimization problem. Experimental results clearly demonstrates the superiority of our algorithm. In the future, we plan to extend our algorithm to a more general framework, and use it as a platform to revisit existing multiple kernel clustering algorithms and uncover their relationship. Meanwhile, designing an sample-specific penalty for each sample is also worth exploring.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (project No. 61403405 and U1435219).