Twin Learning for Similarity and Clustering: A Unified Kernel Approach

Many similarity-based clustering methods work in two separate steps including similarity matrix computation and subsequent spectral clustering. However, similarity measurement is challenging because it is usually impacted by many factors, e.g., the choice of similarity metric, neighborhood size, scale of data, noise and outliers. Thus the learned similarity matrix is often not suitable, let alone optimal, for the subsequent clustering. In addition, nonlinear similarity often exists in many real world data which, however, has not been effectively considered by most existing methods. To tackle these two challenges, we propose a model to simultaneously learn cluster indicator matrix and similarity information in kernel spaces in a principled way. We show theoretical relationships to kernel k-means, k-means, and spectral clustering methods. Then, to address the practical issue of how to select the most suitable kernel for a particular clustering task, we further extend our model with a multiple kernel learning ability. With this joint model, we can automatically accomplish three subtasks of finding the best cluster indicator matrix, the most accurate similarity relations and the optimal combination of multiple kernels. By leveraging the interactions between these three subtasks in a joint framework, each subtask can be iteratively boosted by using the results of the others towards an overall optimal solution. Extensive experiments are performed to demonstrate the effectiveness of our method.  Clustering is a fundamental topic in data mining and machine learning (Peng et al. 2016). It partitions data points into different groups, such that the objects within a group are similar to one another and different from those in other groups. Various methods have been proposed over the past decades. Some well-known algorithms include k-means clustering (MacQueen 1967), spectral clustering (Ng et al. 2002), and hierarchical clustering (Johnson 1967). Thanks to the simplicity and the effectiveness, the kmeans algorithm is widely used. However, it fails to identify arbitrarily shaped clusters. Kernel k-means (Schölkopf, Smola, and Müller 1998) has been developed to capture nonlinear structure information hidden in data sets. Kernelbased learning methods requires one to specify a kernel, which means one assumes a certain shape of the underlying Copyright c  Thus the performance of kernel-based methods are largely affected by the choice of kernel. Spectral clustering does a low-dimensional embedding of the similarity matrix of the data before performing k-means clustering (Ng et al. 2002). The similarity between every pair of points, as an input, leverages the manifold information in this clustering model. Thus similarity-based clustering methods usually show better performance than k-means algorithm. However, the performance of this kind of methods is largely determined by the similarity matrix (Huang, Nie, and Huang 2015). Any variations during the similarity measurement, such as metric, neighborhood size, and data scale, may lead to suboptimal performance. Recently, self-expression has been successfully utilized in subspace recovery (Elhamifar and Vidal 2009; Luo et al. 2011), low rank representation (Kang, Peng, and Cheng 2015b; 2015a), and recommender systems (Kang and Cheng 2016). It represents each data point in terms of the other points. By solving an optimization problem, the similarity information is automatically learned from the data. This approach can not only reveal low-dimensional structure, but also be robust to noise and data scale (Huang, Nie, and Huang 2015).  In this paper, we perform clustering built upon the idea of using samples from the data to “express itself”. Rather than local structure learning (Nie, Wang, and Huang 2014), this approach extracts the global structure of data and can be extended to kernel spaces. Unlike existing clustering algorithms that work in two separate steps, we simultaneously learn similarity matrix and cluster indicators by imposing a rank constraint on the Laplacian matrix of the learned similarity matrix. By leveraging the intrinsic interactions between learning similarity and cluster indicators, our proposed model seamlessly integrates them into a joint framework, where the result of one task is used to improve the other one. To capture the nonlinear structure information inherent in many real world data sets, we directly develop our method in a kernel space, which is well known for its ability to explore the nonlinear relation. We design an efficient algorithm to find an optimal solution to our model, and show the theoretical analysis on the connections to kernel k-means, k-means, and spectral clustering methods.