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.

本文针对高维低样本量情况下聚类算法性能下降的问题，介绍了一种基于云图的 MADD 差异度量方法，并证明了其在高维数据聚类上的有效性；根据理论和实验结果，比较了多种算法及其聚类效果评估方法，发现在使用 MADD 代替欧氏距离时，已有算法的表现得到提升。同时，作者提出了一种基于罚函数 Dunn 指数的新的聚类数目估计方法，在固定样本数量、维数增加的情况下使方法相对于样本数更稳定。最后，研究运用了多组真实和模拟数据集来证明 MADD 方法对高维数据聚类分析中的重要性。