Clustering Millions of Faces by Identity

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Clustering unlabeled face images into unknown identities is crucial for applications like social media analysis and law enforcement.
• Existing clustering algorithms face challenges with run-time complexity and cluster quality when dealing with massive datasets (hundreds of millions of faces).

Purpose of the Study:

• To address the limitations of current methods, this study introduces an approximate Rank-Order clustering algorithm.
• The algorithm aims to improve both run-time efficiency and cluster quality for large-scale facial clustering.

Main Methods:

• An approximate Rank-Order clustering algorithm was developed and compared against popular methods like k-Means and Spectral clustering.
• Experiments involved clustering up to 123 million face images into over 10 million clusters.
• Clustering performance was evaluated using external (known labels) and internal (unknown labels) quality measures, alongside run-time analysis.

Main Results:

• The Rank-Order algorithm achieved an F-measure of 0.87 on the Labeled Faces in the Wild (LFW) benchmark.
• Performance on a larger dataset combining LFW with 123 million distractor images resulted in an F-measure of 0.27.
• Clustering of frames from the YouTube benchmark yielded an F-measure of 0.71.
• A novel internal per-cluster quality measure was developed to identify compact and isolated clusters for manual review.

Conclusions:

• The proposed Rank-Order clustering algorithm offers a viable solution for large-scale, unlabeled facial clustering.
• The algorithm demonstrates superior performance compared to traditional methods, particularly in terms of scalability and efficiency.
• The developed internal quality measure aids in the practical application of clustering results by facilitating the identification of high-quality clusters.