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(k²+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.