# On perfect clustering of high dimension, low sample size data

arXiv: https://arxiv.org/abs/1612.09121 · HTML: https://mlsanity.com/paper/1612.09121/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2016.

## Built on by (most cited first, 10 of 10)

- [Flexible Clustered Federated Learning for Client-Level Data Distribution Shift](https://mlsanity.com/paper/2108.09749/) (2021)
- [Classifier Clustering and Feature Alignment for Federated Learning under Distributed Concept Drift](https://mlsanity.com/paper/2410.18478/) (2024)
- [InfoMerge: Information-aware Token Compression for Efficient Video Large Language Models](https://mlsanity.com/paper/2606.02161/) (2026)
- [Few-Example Clustering via Contrastive Learning](https://mlsanity.com/paper/2207.04050/) (2022)
- [Simple and Scalable Algorithms for Cluster-Aware Precision Medicine](https://mlsanity.com/paper/2211.16553/) (2022)
- [Uniform tensor clustering by jointly exploring sample affinities of various orders](https://mlsanity.com/paper/2302.01569/) (2023)
- [Classification Using Global and Local Mahalanobis Distances](https://mlsanity.com/paper/2402.08283/) (2024)
- [On high-dimensional modifications of the nearest neighbor classifier](https://mlsanity.com/paper/2407.05145/) (2024)
- [Value-Aware Product Recommendation by Customer Segmentation using a suitable High-Dimensional Similarity Measure](https://mlsanity.com/paper/2604.26983/) (2026)
- [A scalable version of MADD for big-data classification](https://mlsanity.com/paper/2607.08334/) (2026)

## Abstract (arXiv)

Popular clustering algorithms based on usual distance functions (e.g., Euclidean distance) often suffer in high dimension, low sample size (HDLSS) situations, where concentration of pairwise distances has adverse effects on their performance. In this article, we use a dissimilarity measure based on the data cloud, called MADD, which takes care of this problem. MADD uses the distance concentration phenomenon to its advantage, and as a result, clustering algorithms based on MADD usually perform better for high dimensional data. Using theoretical and numerical results, we amply demonstrate it in this article. We also address the problem of estimating the number of clusters. This is a very challenging problem in cluster analysis, and several algorithms have been proposed for it. We show that many of these existing algorithms have superior performance in high dimensions when MADD is used instead of the Euclidean distance. We also construct a new estimator based on penalized Dunn index and prove its consistency in the HDLSS asymptotic regime, where the sample size remains fixed and the dimension grows to infinity. Several simulated and real data sets are analyzed to demonstrate the importance of MADD for cluster analysis of high dimensional data.