TL;DR
This paper introduces "subclustering," a new approach to image clustering that aims to produce smaller, purer clusters by focusing on a subset of images from each class. They propose both a passive algorithm and an active learning variant that leverages human input to further refine these subclusters, offering significant improvements in efficiency and accuracy for large-scale image datasets.
What Problem Does This Paper Address?
Clustering large image datasets is a significant challenge, especially when dealing with many classes. Traditional clustering algorithms struggle with high dimensionality and noisy automatically computed image distances, often resulting in impure clusters. This makes tasks like image retrieval and browsing difficult, as users have to sift through many irrelevant or redundant images. The paper addresses this by proposing "subclustering," which aims to create representative subsets of images for each class, making browsing and retrieval more efficient and accurate. They also tackle the problem of requiring extensive human labeling in active learning by developing an approach that uses pairwise constraints, which are easier for humans to provide than full labels.
Methods
The paper introduces two main algorithmic contributions:
- Passive Subclustering: This algorithm aims to produce subclusters by optimizing a cost function that maximizes the probability of images within a cluster belonging to the same class and minimizes the probability of different centroids being from the same class. It's inspired by the Partition Around Medoids (PAM) algorithm but optimized for subclustering and significantly reduces runtime.
- Active Subclustering: This algorithm builds upon the passive subclustering by incorporating human feedback. It intelligently selects pairs of images (either between-class centroid pairs or within-class centroid-image pairs) to ask humans for constraints (e.g., "are these two images from the same class?"). The algorithm prioritizes queries that are most likely to correct errors (both between-class and within-class) and updates the subclusters iteratively. This approach is designed to be efficient with human input, requiring far fewer questions than traditional active clustering methods.
Datasets
The authors evaluate their algorithms on the following datasets:
- Pubfig [18]: A face image dataset known for its challenging, uncontrolled settings. They create several subsets: Face-40, Face-80, Face-120, Face-160, and Face-200 (the complete dataset with 51,418 images and 200 classes).
- Leafsnap [2]: A plant species identification dataset. They use a subset called Leaf-27 (1535 images, 27 classes).
- Small datasets: Face-10 (250 images, 10 classes) and Leaf-25 (250 images, 25 classes) were also used for testing.
Key Insights and Ideas
- Subclustering as a distinct problem: The paper argues that subclustering is a more direct and efficient approach for tasks like browsing and retrieval than trying to achieve it as a byproduct of complete clustering.
- Pairwise constraints are powerful and efficient: Humans are much better at judging if two images belong to the same class than assigning absolute labels. This insight is central to their active subclustering approach, leading to significantly less human effort.
- Balancing between-class and within-class errors: The active subclustering algorithm intelligently decides which type of error to address next, considering the likelihood of a centroid remaining in the set, which is a novel approach to active learning in clustering.
- Novel evaluation metric (SJC): The Subclustering Jaccard's Coefficient (SJC) is introduced to specifically evaluate the quality of subclusters, considering both coverage (representing all classes) and purity (clusters being free of errors).
Key Results
- Passive Subclustering: The proposed passive algorithm significantly outperforms baseline methods like Fast-PAM, K-medoids, Normalized Cut, and BBC-S in terms of Subclustering Jaccard's Coefficient (SJC) on the Leaf-27 dataset. It is also substantially faster, achieving a 30x speedup over Fast-PAM for the Face-200 dataset.
- Active Subclustering: For the large Face-200 dataset, their active algorithm achieves a high SJC of 0.92 with approximately 143,000 questions, costing around $358 via Mechanical Turk. This is a significant improvement over prior active clustering methods, which achieved much lower SJC with the same number of questions or required vastly more questions/higher costs. The active algorithm also performs well on smaller datasets (Leaf-25, Face-10), outperforming other approaches with fewer questions.
Limitations and Future Work
- Limitations: The paper acknowledges that while their active algorithm is efficient, it's still an iterative process. The performance of the active algorithm is also compared to previous active clustering methods that were not specifically designed for subclustering, so their "poor performance" might not be a direct criticism of those algorithms in their intended context.
- Future Work: The authors suggest that their subclustering idea can be extended to any clustering domain beyond images. They also mention making their code publicly available, which will facilitate further research and application of their methods.
Summary updated