Approximate Large-scale Multiple Kernel k-means Using Deep Neural Network

1 Introduction

Multiple view clustering (MVC) algorithms have been extensively studied recently because they can exploit the complementary information among multiple views of data in an unsupervised way [Zhou and Burges, 2007; Weiran et al., 2015; Jinglin et al., 2016; Cao et al., 2015; Zhang et al., 2015]. Most of these MVC algorithms adopt an underlying assumption; that is, all data points are mapped into the Euclidean, Hamming, or other simple geometric spaces, so they cannot fully exploit the nonlinear similarities among data points. Kernel based algorithms overcome this limitation by mapping samples into a reproducing kernel Hilbert space and defining the similarity using a nonlinear kernel function. This enables kernel clustering to handle the linearly non-separable problem in an input space that MVC algorithms suffer from.

∗The corresponding author.

Continuing in this direction, many multiple kernel clustering (MKC) algorithms have been proposed [Zhao et al., 2009; Huang et al., 2012; Lu et al., 2014; Xia et al., 2014; Zhou et al., 2015; Kumar et al., 2011]. Although demonstrating promising performance, these MKC algorithms cannot be applied to large-scale applications due to the following two issues. Firstly, all MKC algorithms need to calculate the base kernels, and the computational complexity of this process which equals O(m ∗ d2 ∗ N 2 ), is huge, where d, m, and N represent the dimension, the number of kernels and the number of samples, respectively. Secondly, the memory requirement of all MKC algorithms is large, which equals O(m ∗ N 2 ). For example, when N = 100, 000 and m = 3, MKC algorithms need over 100GB of running memory. The huge memory requirement cannot be satisfied even on a server. A direct remedy to address the memory issue is data blocking, which splits kernel matrices into several pieces and stores them on the hard disk. In this way, the kernel matrices stored in memory will be replaced frequently, which greatly increases the timing overhead.

To address the time and memory issues, we revisit one classical representative of MKC algorithms, called the multiple kernel k-means (MKKM), and propose an approximate algorithm to avoid computing and loading kernel matrices. To further illustrate how to reduce the running time and memory, we divide the MKKM into three stages: i) multiple kernel generation; ii) an optimized process that updates the indicating matrix H and coefficients γ alternately; iii) k-means on H, which is to obtain clustering labels. The first two stages of MKKM will map the input features X into a kernel matrix K, and then into the indicating matrix H. These two stages consume too much memory and time. To reduce the time and memory requirements of MKKM, we design a deep neural network to approximate the first two stages in MKKM. Specifically, we sample a subset from the whole dataset, and then use MKKM to get the indicating matrix of the subset Hsub. After that, we design a deep neural network to regress the Hsub. Next, we take the whole dataset as the input of the trained network, and get the approximate indicating matrix ˜H of the large dataset using the trained network. Finally, we perform k-means on ˜H. Note that the full kernel matrices are required in MKKM because the optimized process needs the combined kernel matrix to obtain H. By mapping features into ˜H directly, we avoid computing the full kernel matrix. Therefore, the computational and memory requirements of our approach are only a small portion of the MKKM, which further leads to a significant speedup of MKKM. By observing that the dimension of the features will influence the running time of k-means, we use principal component analysis (PCA) to reduce the dimension of ˜H. As a byproduct, the dimensionality reduction may also be appropriate when the ˜H is noisy. In this way, the output of our algorithm is of better quality and lower dimension, and is more suitable for clustering.

We end up this section by summarizing the main contributions of this work as follows:

i) We propose a deep neural network to approximate the MKKM. It can avoid computing kernels and completing singular value decomposition (SVD) in MKKM by mapping the features into the indicating matrix directly, which reduces the memory and time requirements.

ii) The experimental results show that our approach and MKKM give results of comparable accuracy on several small datasets, which means our approximate approach is effective. On some large-scale datasets, the memory requirement of MKKM is too large to satisfy, while our approach also works well and achieves promising performance.

2 RelatedWork

We first review the related work on MKC, and then give a brief introduction to large-scale clustering algorithms.

2.1 Multiple Kernel Clustering (MKC) Algorithms

Much effort have been devoted to improving MKC from all kinds of aspects. 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 [Yu et al., 2012; Cortes et al., 2012; G¨onen and Margolin, 2014; Du et al., 2015; Lu et al., 2014; Liu et al., 2016]. In [Yu et al., 2012], the authors propose an MKKM algorithm that externs kernel k-means from a single kernel to multiple kernels. The work in [G¨onen and Margolin, 2014] offers a similar algorithm with the difference being that the kernels are combined in a localized way to better capture their individual characteristics. In [Lu et al., 2014], kernel alignment maximization is employed to jointly perform the k-means clustering and MKL. The algorithm described in [Cortes et al., 2012], called co-regularized spectral clustering (CRSC), provides a co-regularization method to perform spectral clustering. Instead of explicitly optimizing the combined kernel, it learns the indicating matrix H directly. To reduce the redundancy and enforce the diversity of the selected kernels, MKKM clustering with matrix-induced regularization (MKKM-MR) is proposed [Liu et al., 2016]. MKKM-MR uses a regularization term that is able to characterize the correlation of each pair of kernels.

The second category learns a consensus matrix via lowrank optimization [Xia et al., 2014; Zhou et al., 2015; Kumar et al., 2011]. In [Xia et al., 2014], they firstly construct a transition probability matrix from each single view, and use these matrices to recover a shared low-rank transition probability matrix as an input to the standard Markov chain method for clustering. Another work [Zhou et al., 2015] presents to capturing the structures of noises in each kernel, and integrating them into a robust and consensus framework to learn a low-rank matrix. In [Kumar et al., 2011], the clustering is learned in one view and is then used to label data in other views to modify a similarity matrix.

Although these algorithms achieve promising performance, they cannot be applied to large-scale datasets due to i)the heavy computational cost to calculate the kernels; and ii) insufficient memory to store the kernel matrices and optimize the combined kernel.

2.2 Large-scale Clustering Algorithms

To efficiently cluster large-scale datasets, a number of algorithms have been developed. Some methods aim to improve the scalability of clustering algorithms [Cai et al., 2013; Chen and Cai, 2011; Zhang and Lu, 2016; Wang et al., 2016]. In [Cai et al., 2013], they put forward a new, robust, large-scale multi-view clustering method to integrate heterogeneous representations of large-scale data. The work in [Wang et al., 2016] proposes three new nonnegative matrix factorization (NMF) and nonnegative matrix tri-factorization (NMTF) models, which are robust to outliers. To avoid the presence of noise in the large-scale data, a large-scale sparse clustering (LSSC) algorithm is detailed in [Zhang and Lu, 2016].

Other algorithms have been proposed to reduce the high computational cost of clustering [Gong et al., 2015; Li et al., 2015; Zhang and Lu, 2016; Shen et al., 2017]. In [Gong et al., 2015], a fast binary k-means algorithm is presented that works directly on the similarity-preserving hashes of images and clusters them into binary centers. The work [Li et al., 2015] offers a large-scale multiple view spectral clustering approach based on a bipartite graph. Compressed k-means (CKM) is suggested in [Shen et al., 2017] which significantly reduces the memory and time requirements by mapping data points as binary codes, so it is well suited to fast clustering.

Most existing large-scale clustering methods can only achieve mediocre performance because i) they always adopt approximate ways to speedup the clustering process; and ii)

they do not use kernel functions to map data points into reproduced kernel Hilbert spaces, so they cannot fully exploit the non-linear similarity among data points, which limits the clustering performance. In our work, we propose a novel approach to approximate MKKM, which achieves the comparable performance to MKKM, while it consumes less time and memory than most contrasted algorithms.

3 Approximate Large-scale Multiple Kernel k-means Using Deep Neural Network

3.1 Notations and Background

In this part, we introduce some of the notations used in our paper. 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. Correspondingly, the kernel function over the above mapping function can be written as:

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

where H is the indicating matrix of all data. The problem described in Eq.(2) can be solved by alternatively updating H and γ.

The memory requirement of MKKM is at least O(m∗N 2 ), and the computational complexity of it equals O(N 3 ) due to the SVD. These two issues limit the MKKM to being applied to large-scale tasks.

3.2 Approximate Large-scale Multiple Kernel k-means Using Deep Neural Network

In our paper, we use a deep neural network to approximate MKKM, which can achieve comparable performance to MKKM. Our network includes one 1D convolutional layer, one max pooling layer, and four fully connected layers. After the pooling layer, we concatenate the multiple features and send the combined feature into the fully connected layer. By combining multiple views of data, our network can achieve better performance.

In our implementation, we fix the network structure except for the output layer. The dimension of our output layer is decided by the number of classes. For example, the handwritten digital dataset has 10 classes, so the dimension of our output layer equals 10.

There are two stages in our approximate algorithm. In the first stage, we sample data from the whole dataset and obtain multiple views of the data. To facilitate effective feature learning, all views are normalized into the same unit View 2

Figure 2: The network structure used in our work. It includes one convolutional layer, one pooling layer, and four fully connected layers.

box. Then, multiple kernels of the subset are generated and MKKM is performed on these kernels to obtain the Hsub, which is the target of our network. After that, we train a deep neural network to regress Hsub, as shown in Figure 2. The corresponding loss function of our network can be written as follows:

Where θ is the parameters of our network and fθ(X) is the output of our network, which equals gn(· · · g2(W⊤ 2 (g1(W⊤ 1 ∗ X + b1)) + b2) · · · ). gl, Wl and bl denote the activating function, weight matrix and bias vector of the l-th layer, respectively. To regress Hsub, we use stochastic gradient descent (SGD) method to minimize the loss function. The training stage is shown in Algorithm 1.

Algorithm 1: Training stage

Input: Xsub

Output: θ

• 1 Generate multiple kernels {Ki}mi=1 with Xsub;
• 2 Compute indicating matrix Hsub using MKKM;
• 3 Initialize θ randomly;

4 repeat

• 5 Complete forward pass to get the output fθ(Xsub);
• 6 Perform backward pass to compute ∂JH/∂θ;
• 7 Update θ;
• 8 until Convergence;

After the training stage, our approach is performed on the whole datasets, as shown in Algorithm 2. In this stage, we fix the deep neural network, and send all data points into it to obtain the approximate indicating matrix Ho. To further decrease the dimension of the indicating matrix, we adopt PCA, and get ˜H. Finally, we perform k-means on ˜H to obtain the clustering results ˜Y.

3.3 Discussion

Although it includes a training stage and testing stage, our algorithm is an unsupervised algorithm. In fact, the "label" used in our training stage is obtained in an unsupervised way. By using the indicating matrix Hsub of the subset, the performance of our algorithm is nearly identical to that of MKKM. Moreover, when performed on large-scale datasets, our algorithm does not need to compute kernels and perform SVD, which indicates the time and memory requirements are only a small portion of MKKM, so our algorithm is more suitable for large-scale datasets than MKKM. It is well understood that the sampling strategy is crucial to the performance of the proposed algorithm. In fact, sampling strategy is an important area of machine learning research. In our paper, we do not consider the influence of other strategies, and only adopt the random uniform sampling without replacement.

4 Experimental Results

4.1 Datasets and Experimental Settings

We evaluate our algorithm on eight datasets detailed in Table 1. To compare the performance of our algorithm with MKKM, we use four small-scale datasets, such as mnist10k, cifar100-10k, Oxford 102 Category Flowers (102flowers), and birds200, for which the numbers of samples are fewer than 15,000. To display the performance of our algorithm on large-scale datasets, we use four datasets, such as Caltech256, cifar100, mnist, and ImageNet, for which the numbers of samples are greater than 30000. It is worth mentioning that ImageNet has more than 1.2 million samples. For all datasets, we use two 4096-dimensional features extracted using the Alexnet model [Krizhevsky et al., 2012] and Visual Geometry Group-19 (VGG19) model [Simonyan and Zisserman, 2014] to represent the images. We also generate six kernels, including two linear kernels and four Gaussian kernels for several small datasets, such as 102flowers, mnist-10k, cifar100-10k and birds200. Furthermore, to test the performance of all algorithms with respect to the number of samples, we generate ten subsets by randomly selecting 1,000, 2,000, · · · , and 10,000 samples on Caltech256, cifar100 and birds200. The widely used clustering accuracy (ACC), normalized mutual information (NMI) and purity are applied in our paper to evaluate the clustering performance. For all algorithms, we repeat each experiment 20 times with random initialization to reduce the effect of randomness caused by k-means, and report the mean result.

Figure 3 shows some samples for 102flowers, ImageNet, and birds200. All the algorithms reported this paper are performed on a workstation with a 32-core Intel E5-2650 2.00 GHz processor and 256 GB memory.

4.2 Compared Algorithms

• k-means. This is the conventional k-means method based on Euclidean distance. It is the baseline method in our work.
• PCA+k-means. We perform a PCA over the samples and use the coefficient matrix as new features. We choose the first p principal components whose cumulative percent is greater than 0.99.
• LSC-k [Chen and Cai, 2011]. The landmark-based large scale spectral clustering method using k-means for landmark selection.
• Robust multi-view k-means clustering (RMKMC [Cai et al., 2013]. RMKMC can be easily parallelized and performed on multi-core processors for big data clustering. Moreover, it is robust to data outliers.
• Auto-weightedmultiple graph learning (AMGL) [Nie et al., 2016]. AMGL learns a set of weights automatically for all views and does not need any parameters.
• Multi-view learning with adaptive neighbors (MLAN) [Nie et al., 2017]. It performs multi-view clustering and local manifold structure learning simultaneously. Similar to AMGL, it has no explicit weight parameters.
• CKM [Shen et al., 2017]. CKM aims to jointly learn binary codes and clusters. The advantages of CKM over conventional clustering methods is the low computational cost and storage.
• MKKM [Huang et al., 2012]: The algorithm alternatively performs kernel k-means and updates the kernel coefficients, as introduced in the related work. It can be seen as the baseline of our algorithm. Note that this algorithm can only be performed on small datasets due to its heavy memory requirement.

4.3 Experimental Results

Performance on small datasets. Compared with alternative clustering algorithms, our algorithm consumes 1.26s, 14.3s, 0.76s, and 0.49s for clustering, and reports 35.2%, 31.34%, 55.99%, and 70.78% clustering accuracy on cifar100-10k, birds200, 102flowers and mnist-10k, respectively. By contrast, MKKM takes 24.2s, 61.3s, 16s, and 10.1s, and achieves comparative clustering accuracy. We also contrast our algorithm with six other algorithms: k-means, PCA+k-means, LSC-k, RMKMC, AMGL and MLAN. Figure 5 displays the performance on small datasets of all algorithms. Although AMGL and MLAN achieve the best accuracy on mnist-10k (91.99% and 88.12%, respectively), they consume too much time, which means they should not be applied to large-scale datasets. Furthermore, they only show the best performance on this dataset; however, on other three datasets, our two algorithms show better performance while costing less time.

Performance on large datasets. Table 2 reports the clustering performance and timing performance of all the aforementioned algorithms. It can be observed that our algorithms achieve the best performance on all data sets, while needing relatively less running time. On large-scale dataset, such as ImageNet, our algorithms achieve an accuracy of 38.84% and 38.92%, and the speed up compared to k-means are 3.3 and 11.05, which means our algorithms are more suitable for large-scale datasets. This indicates that our approximate algorithms can be applied to estimate the performance of MKKM on large-scale datasets. In addition, our algorithms would not lose too much performance after reducing the dimension; for example, by using PCA, the performance of our algorithm decreases by an average of less than 1%. These observations show that the proposed clustering algorithms are effective and efficient.

Performance with different numbers of training samples. As mentioned before, our algorithm has a training stage and testing stage. In the training stage, we sample a subset from the whole data set. In this section, we report on the clustering performance using different sizes of training set. In order to verify the effect of the size of the training set on the final clustering performance, we change the size of the training set and train different networks, then test these networks on three datasets. Figure 6 presents the results. From this figure, we can see that the accuracy, NMI, and purity have no significant changes when the size of the training set changes, which indicates that our algorithm is stable.

Performance with different sizes of datasets. Figure 4 displays the performance of our algorithm on subsets with different number of samples. It is observed that i) the running time of the compared algorithms dramatically increases when the numbers of samples is varied, while ours increase slightly; ii) there are no fixed rules between clustering performance and the number of samples; and iii) MKKM and our algorithm always achieve the best performance with different numbers of samples.

Performance of single-view data. To display the advantage of multi-view, we report the clustering accuracy of single-view on all datasets in Table 3.

From Table 3, we can conclude that i) our algorithms achieve better performance on single view datasets; and ii) the performance of multi-view data is higher than that of single-view.

5 Conclusion

In this paper, we propose a novel algorithm to overcome timing and memory issues. It achieves comparative performance with MKC algorithms. In particular, our algorithm trains a deep neural network to regress the indicating matrix generated by MKC algorithms on a small subset, then obtains the approximate indicating matrix of the whole dataset using the trained network, and performs the k-means on the output of our network. To further reduce the execution time of our algorithm, we add the PCA to our network to descend the dimension of output. Extensive experiments show that our algorithm is effective and efficient.

Acknowledgments

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