  In this work, we attempt to address the following problem: Given a large
number of unlabeled face images, cluster them into the individual identities
present in this data. We consider this a relevant problem in different
application scenarios ranging from social media to law enforcement. In
large-scale scenarios the number of faces in the collection can be of the order
of hundreds of million, while the number of clusters can range from a few
thousand to millions--leading to difficulties in terms of both run-time
complexity and evaluating clustering and per-cluster quality. An efficient and
effective Rank-Order clustering algorithm is developed to achieve the desired
scalability, and better clustering accuracy than other well-known algorithms
such as k-means and spectral clustering. We cluster up to 123 million face
images into over 10 million clusters, and analyze the results in terms of both
external cluster quality measures (known face labels) and internal cluster
quality measures (unknown face labels) and run-time. Our algorithm achieves an
F-measure of 0.87 on a benchmark unconstrained face dataset (LFW, consisting of
13K faces), and 0.27 on the largest dataset considered (13K images in LFW, plus
123M distractor images). Additionally, we present preliminary work on video
frame clustering (achieving 0.71 F-measure when clustering all frames in the
benchmark YouTube Faces dataset). A per-cluster quality measure is developed
which can be used to rank individual clusters and to automatically identify a
subset of good quality clusters for manual exploration.
