Source-linked AI summary
Efficient Parameter-free Clustering Using First Neighbor Relations
M. Saquib Sarfraz, Vivek Sharma, Rainer Stiefelhagen
TL;DR
Clustering methods often require distance structures, thresholds, or a predefined number of clusters, limiting their generality and scalability. FINCH uses first-neighbor relations to construct clusters and recursively forms a hierarchical set of partitions. Across diverse datasets ranging from 1077 to 8.1 million samples, it converges quickly and reports strong clustering performance.
Problem
Existing clustering methods commonly require full pairwise distances, hyper-parameters, thresholds, or a predefined number of clusters, hindering generality across datasets and scalability to large data.
Method
FINCH constructs a sparse adjacency graph from each sample’s first neighbor and recursively applies the relation to cluster means in a hierarchical agglomerative procedure.
Results
FINCH was evaluated across diverse domains and dataset sizes from 1077 to 8.1 million samples, converging in 4-10 steps while providing valid partitions at each step.
Takeaways & Limitations
The paper presents FINCH as a parameter-free, scalable clustering method that can produce meaningful groupings without prior knowledge of data structure.
Takeaways & Limitations
For well-separated ground-truth clusters, an additional FINCH merge can collapse a correct multi-cluster partition into one cluster, so stopping at the appropriate partition matters.
Abstract
from arXiv · showhide
We present a new clustering method in the form of a single clustering equation that is able to directly discover groupings in the data. The main proposition is that the first neighbor of each sample is all one needs to discover large chains and finding the groups in the data. In contrast to most existing clustering algorithms our method does not require any hyper-parameters, distance thresholds and/or the need to specify the number of clusters. The proposed algorithm belongs to the family of hierarchical agglomerative methods. The technique has a very low computational overhead, is easily scalable and applicable to large practical problems. Evaluation on well known datasets from different domains ranging between 1077 and 8.1 million samples shows substantial performance gains when compared to the existing clustering techniques.
1. Introduction
The paper addresses the lack of a clustering method that simultaneously discovers accurate groupings without user parameters, generalizes across domains, and scales to millions of samples. It proposes a fully parameter-free algorithm based on first-neighbor chaining.
- Existing clustering methods generally require assumptions such as a preset cluster count, distance thresholds, or other hyper-parameters.These choices are subjective, unstable across datasets, and tied to the underlying data distribution.
- The paper proposes a fully parameter-free unsupervised algorithm requiring neither user-defined thresholds or cluster counts nor prior knowledge of the data distribution.The method is intended to discover natural clusters directly from the data.
- The method is designed for low computational overhead, fast processing, large datasets, and meaningful high-purity groupings.
2. Related Work
Prior clustering approaches span partitioning, hierarchical, and graph-partitioning families, but commonly depend on distance structures or user-specified assumptions. The paper positions its proposal as a scalable alternative that avoids full pairwise distance storage and prior knowledge.
- Clustering methods are commonly organized into centroid or partitioning, hierarchical agglomerative or divisive, and graph-partitioning approaches.
- Center-based methods can depend on initialization or objective-function choices, while spectral methods commonly require full similarity graph Laplacians and quadratic complexity.
- Shared-neighbor methods define similarity through matching nearest neighbors rather than only direct Euclidean distances.
- Hierarchical agglomerative clustering starts with singleton clusters and iteratively merges similar clusters using linkage-based similarity measures.Its clustering tree supports interpretation at different levels of granularity.
- The proposed method avoids full pairwise distance floats and user-specified cluster counts, thresholds, or algorithm-specific hyper-parameters.
3. The Proposed Clustering Method
FINCH uses each point’s first neighbor to construct a sparse adjacency graph whose connected components form clusters, then recursively merges cluster representations into a hierarchy. This produces successive valid partitions with low computational cost and can be refined to a requested cluster count.
- The Proposed Clustering Method: The method treats each point’s first neighbor as sufficient to discover linking chains without maintaining a full distance matrix or setting thresholds.
- The Clustering Equation: The adjacency matrix links each point to its first neighbor and links points sharing the same first neighbor.
- The Clustering Equation: Equation 1 produces a symmetric sparse graph whose connected components directly specify the clusters without distance-weighted graph partitioning.The matrix combines 1-nearest-neighbor and shared-nearest-neighbor relations.
- The Clustering Equation: In the planet example, the equation forms chains and discovers three clusters from nine samples represented by 15 measurements.
- Proposed Hierarchical Clustering: FINCH recursively computes first neighbors of cluster means, yielding a hierarchy of valid fine-to-coarse partitions with complexity O(Nlog(N)).
- Proposed Hierarchical Clustering: A refinement procedure can merge clusters one at a time when an application requires a specific number of clusters.
4. Experiments
FINCH is evaluated across biological, text, digit, face, object, and large-scale datasets against clustering methods with varied parameter and scalability requirements. The experiments report strong performance, deep-clustering gains, and substantially lower computational and memory costs.
- Datasets: The evaluation spans biological, text, digit, face, and object datasets, with feature dimensionalities ranging from 77 to 4096.The datasets include Mice Protein, REUTERS, STL-10, MNIST, and video face-identification datasets.
- Comparison with baselines: Table 2 compares FINCH with methods that estimate clusters using hyper-parameters or thresholds and methods requiring the number of clusters as input.For methods requiring the number of clusters, the evaluation uses the number estimated by FINCH; out-of-memory cases are marked accordingly.
- Large-scale datasets: FINCH performs significantly better than previously published methods on the BBTs01 and BFs05 video face-identification datasets.The comparison uses features from a pre-trained model without data-specific transfer or video-level constraints.
- Deep Clustering: Unsupervised Learning: On STL-10, FINCH-driven deep clustering reaches approximately 95% performance, improving by almost 10% over existing state-of-the-art deep-clustering methods.FINCH directly clusters ResNet50 base features and then supplies estimated clusters as pseudo-labels for MLP training and re-clustering.
- Computational Advantage: FINCH requires O(N) memory and O(Nlog(N)) computational complexity, compared with O(N^2) memory, O(N^3) spectral methods, and O(N^2log(N)) hierarchical linkage methods.Its memory use retains the data and an N × 1 array of first-neighbor indices; many other algorithms exceed 192 GB RAM or fail on datasets larger than 70k samples.
5. Discussion
FINCH is evaluated across diverse datasets and produces valid, accurate partitions in few recursive steps, while remaining parameter-free and scalable. The method’s main limitation is that it cannot produce singleton clusters.
- 5. Discussion: FINCH was evaluated on image, biological, and text data represented in 77 to 4096 dimensions.The evaluation covered datasets ranging from 1077 to 8.1 million samples.
- 5. Discussion: 4–10 recursive steps produced valid partitions across datasets ranging from 1077 to 8.1 million samples.Cluster accuracy was maintained through large successive merges.
- 5. Discussion: FINCH recovered exactly 10 MNIST clusters with above 99% accuracy for both 10k and 70k samples.The method stopped before merging the ten-cluster partition into one cluster.
- 5. Discussion: FINCH cannot discover singleton clusters because every sample is linked to its first neighbor, setting the smallest cluster size to 2.Singletons are therefore paired with their nearest sample point.
- 5. Discussion: The paper concludes that FINCH combines parameter-free clustering, low computational expense, and scalability to large datasets.The authors identify applications including unsupervised feature representation learning and scientific discovery.
Datasets Detail
The experiments use image datasets with CNN and raw-pixel representations, varying feature dimensions to test clustering across diverse input spaces.
- Datasets Detail: STL-10, BBTs01, BFs05, and MNIST are represented using CNN features, while MNIST also includes raw-pixel experiments.ResNet50 ImageNet features are used for STL-10, VGG2-Face ResNet50 features for the face datasets, and both 4096- and 256-dimensional features for MNIST.
Face Clustering- State-of-the-art Comparison on BBTs01, BFs05 and Accio Datasets
FINCH is compared with state-of-the-art methods on face-clustering datasets, including multi-episode and individual-episode settings, as well as the large Accio dataset.
- Face Clustering- State-of-the-art Comparison on BBTs01, BFs05 and Accio Datasets: 97.42% and 94.02% pairwise F-measure were obtained on BBTs01 and BFs05, compared with 78.2% and 62.99% reported for Jin et al.These results use the ground-truth numbers of clusters: 5 for BBTs01 and 6 for BFs05.
- Face Clustering- State-of-the-art Comparison on BBTs01, BFs05 and Accio Datasets: FINCH estimated 7 clusters for BFs05e02 and exactly 5 clusters for BBTs01e01.The BFs05e02 estimate was reduced to the ground-truth six clusters using Algorithm 2.
- Face Clustering- State-of-the-art Comparison on BBTs01, BFs05 and Accio Datasets: The Accio evaluation clusters 166885 faces from a Harry Potter movie series with 36 named characters using B-Cube precision, recall, and F-score.Performance is measured at 40 clusters, matching the compared methods.
- Face Clustering- State-of-the-art Comparison on BBTs01, BFs05 and Accio Datasets: For the reported face-clustering results, FINCH uses extracted VGG2 feature vectors without data-specific feature training or video-level constraints.The compared methods use additional video or training constraints described in the passage.
Partitions for each dataset
FINCH produces a sequence of partitions for each dataset, reporting cluster counts and clustering accuracy at every step. Across varying datasets and feature distributions, it recovers the ground-truth or a nearby partition.
- Partitions for each dataset: Each FINCH step produces a partition with a reported number of clusters and corresponding clustering accuracy.The partition sequence is summarized using cluster counts and ACC values.
- Partitions for each dataset: FINCH recovered the ground-truth clustering or a very close partition across datasets with varying distributions and dimensionalities.The conclusion is based on the reported merges and resulting clusters.
Details for baselines
The baseline comparison uses recommended or experimentally varied parameters and implementations from established software packages or authors. Tables 9 and 10 document parameter sensitivity and the settings used for the baselines.
- Baseline methods were evaluated using recommended parameters where applicable, with the best reported NMI scores selected.The authors also tried different parameter values for the baselines.
- Table 9 illustrates how changing Affinity Propagation's preference parameter affects estimated cluster counts and NMI performance across two datasets.Preference=-100 estimates eight clusters for mice-protein but yields the worst performance, while producing substantially more clusters than ground truth on MNIST-10k.
- Affinity Propagation, spectral clustering, Birch, and k-means++ use scikit-learn implementations.
- Recognize Anything uses OpenBR, hierarchical agglomerative clustering uses Matlab, and JP uses the implementation available from reference.
- RCC, SSC, and MV-LRSSC use Python or Matlab implementations recommended or provided by their respective authors.
- Table 10 summarizes the parameter settings used for the baseline methods.