Efficient Parameter-free Clustering Using First Neighbor Relations

2019/02/28 by M. Saquib Sarfraz, Vivek Sharma, Sarfraz, M. Saquib +3 · 16 citations
Computer Science · #Advanced Clustering Algorithms Research #Artificial intelligence #Bayesian Methods and Mixture Models #CURE data clustering algorithm #Cluster analysis #Complete-linkage clustering #Computer Vision and Pattern Recognition (cs.CV) #Computer science #Contrast (vision) #Correlation clustering #Data mining #Database #FOS: Computer and information sciences #Face and Expression Recognition #Hierarchical clustering #Overhead (engineering) #Sample (material) #Scalability #Single-linkage clustering #cs.CV

paper · pdf · doi:10.48550/arxiv.1902.11266

published in arXiv (Cornell University) (Cornell University) · CVPR 2019

arxiv created 2019/02/28 · openalex publication_date 2019/02/28 · arxiv updated 2019/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

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.

Citations

• Synthetic Data and Artificial Neural Networks for Natural Scene Text Recognition
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Gradient-based learning applied to document recognition
• A tutorial on spectral clustering
• Multi-view low-rank sparse subspace clustering

Cited by

• ReSAM: Refine, Requery, and Reinforce: Self-Prompting Point-Supervised Segmentation for Remote Sensing Images
• An Adaptive Resonance Theory-based Topological Clustering Algorithm with a Self-Adjusting Vigilance Parameter
• Divide, Conquer and Unite: Hierarchical Style-Recalibrated Prototype Alignment for Federated Medical Segmentation
• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version)
• Active Learning for Animal Re-Identification with Ambiguity-Aware Sampling
• Disentangled Concepts Speak Louder Than Words: Explainable Video Action Recognition
• CLEANet: Robust and Efficient Anomaly Detection in Contaminated Multivariate Time Series
• EReLiFM: Evidential Reliability-Aware Residual Flow Meta-Learning for Open-Set Domain Generalization under Noisy Labels
• Joint Superpixel and Self-Representation Learning for Scalable Hyperspectral Image Clustering
• Category Discovery: An Open-World Perspective
• MolCluster: Integrating Graph Neural Network with Community Detection for Coarse-Grained Mapping
• Skeleton Motion Words for Unsupervised Skeleton-Based Temporal Action Segmentation
• Multi-class Image Anomaly Detection for Practical Applications: Requirements and Robust Solutions
• CLoVE: Personalized Federated Learning through Clustering of Loss Vector Embeddings
• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images
• Feature-Based Instance Neighbor Discovery: Advanced Stable Test-Time Adaptation in Dynamic World
• PCBEAR: Pose Concept Bottleneck for Explainable Action Recognition

Related

• Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity
• A Parameter-free Affinity Based Clustering
• A sampling-based approach for efficient clustering in large datasets
• Nearest Neighbour Equilibrium Clustering
• Fast and explainable clustering based on sorting