A Generalized Single Linkage Method for Estimating the Cluster Tree of a Density
A Generalized Single Linkage Method for Estimating the Cluster Tree of a Density
复制标题
DOI：
10.1198/jcgs.2009.07049
复制
发表时间：
2010-06-01
影响因子：
2.4
通讯作者：
Nugent, Rebecca
中科院分区：
文献类型：
--
作者：
Stuetzle, Werner;Nugent, Rebecca
聚类的目标是检测数据集中不同组的存在，并为观察值分配组标签。非参数聚类的前提是，观测值可以被视为特征空间中某个潜在密度的样本，并且组对应于该密度的模式。然后，目标是找到模态，并将每个观测值分配到一个模态的吸引域。用聚类树来概括密度的模态结构；密度的模式对应于簇树的叶子。估计聚类树是非参数聚类分析的主要目标。我们采用插件方法进行聚类树估计：通过密度估计的聚类树估计特征密度的聚类树。对于某些密度估计，聚类树可以精确计算；对于另一些人，我们不得不满足于一个近似值。我们提出了一种基于图的方法，可以近似任何密度估计的聚类树。密度估计往往具有由采样可变性引起的伪模式，导致图簇树中的伪分支。我们建议用多余的质量来衡量树枝的大小，这反映了相对于周围谷底的密度峰值的高度以及它的空间范围。多余的质量可以作为修剪图聚类树的指南。我们指出了单链接聚类的数学和算法联系，并通过几个例子说明了我们的方法。本文的补充材料，包括实现广义单链接聚类的R包，示例中使用的所有数据集，以及生成图形和数值结果的R代码，都可以在网上获得。
The goal of clustering is to detect the presence of distinct groups in a dataset and assign group labels to the observations. Nonparametric clustering is based on the premise that the observations may be regarded as a sample from some underlying density in feature space and that groups correspond to modes of this density. The goal then is to find the modes and assign each observation to the domain of attraction of a mode. The modal structure of a density is summarized by its cluster tree; modes of the density correspond to leaves of the cluster tree. Estimating the cluster tree is the primary goal of nonparametric cluster analysis. We adopt a plug-in approach to cluster tree estimation: estimate the cluster tree of the feature density by the cluster tree of a density estimate. For some density estimates the cluster tree can be computed exactly; for others we have to be content with an approximation. We present a graph-based method that can approximate the cluster tree of any density estimate. Density estimates tend to have spurious modes caused by sampling variability, leading to spurious branches in the graph cluster tree. We propose excess mass as a measure for the size of a branch, reflecting the height of the corresponding peak of the density above the surrounding valley floor as well as its spatial extent. Excess mass can be used as a guide for pruning the graph cluster tree. We point out mathematical and algorithmic connections to single linkage clustering and illustrate our approach on several examples. Supplemental materials for the article, including an R package implementing generalized single linkage clustering, all datasets used in the examples, and R code producing the figures and numerical results, are available online.