Efficient Parameter-free Clustering Using First Neighbor Relations

2019/02/28 by M. Saquib Sarfraz, Vivek Sharma, Sarfraz, M. Saquib +3 · 13 citations
Computer Science · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Face and Expression Recognition

paper · pdf · doi:10.48550/arxiv.1902.11266

openalex publication_date 2019/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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\n 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

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