Centerless Clustering.

Although lots of clustering models have been proposed recently, k-means and the family of spectral clustering methods are both still drawing a lot of attention due to their simplicity and efficacy. We first reviewed the unified framework of k-means and graph cut models, and then proposed a clustering method called k-sums where a k-nearest neighbor ( k-NN) graph is adopted. The main idea of k-sums is to minimize directly the sum of the distances between points in the same cluster. To deal with the situation where the graph is unavailable, we proposed k-sums-x that takes features as input. The computational and memory overhead of k-sums are both O(nk), indicating that it can scale linearly w.r.t. the number of objects to group. Moreover, the costs of computational and memory are Irrelevant to the product of the number of points and clusters. The computational and memory complexity of k-sums-x are both linear w.r.t. the number of points. To validate the advantage of k-sums and k-sums-x on facial datasets, extensive experiments have been conducted on 10 synthetic datasets and 17 benchmark datasets. While having a low time complexity, the performance of k-sums is comparable with several state-of-the-art clustering methods.

A portable clustering algorithm based on compact neighbors for face tagging.

We focus on the following problem: Given a collection of unlabeled facial images, group them into the individual identities where the number of subjects is not known. To this end, a Portable clustering algorithm based on Compact Neighbors called PCN is proposed. (1) Benefiting from the compact neighbor, the local density of each sample can be determined automatically and only one user-specified parameter, the number of nearest neighbors k, is involved in our model. (2) More importantly, the performance of PCN is not sensitive to the number of nearest neighbors. Therefore this parameter is relatively easy to determine in practical applications. (3) The computational overhead of PCN is O(nk(k2+log(nk))) that is nearly linear with respect to the number of samples, which means it is easily scalable to large-scale problems. In order to verify the effectiveness of PCN on the face clustering problem, extensive experiments based on a two-stage framework (extracting features using a deep model and performing clustering in the feature space) have been conducted on 16 middle- and 5 large-scale benchmark datasets. The experimental results have shown the efficiency and effectiveness of the proposed algorithm, compared with state-of-the-art methods. [code].