改进了序列聚类的稳定性条件,让SLINK算法适用范围更广且更省样本。
Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences
- 用更宽松的簇内距离条件替代旧假设,提升算法适用性。
- 实验表明在某些情况下k-medoids失效而SLINK仍能正确聚类。
- 提出新序列算法SLINK-SEQ,相同错误率下所需样本更少。
本文研究独立同分布(i.i.d.)数据序列的非参数聚类问题,其中M个数据序列来自未知分布,其分布本身属于K个潜在分布簇。现有指数一致的非参数聚类方法(如单链接聚类SLINK、k- medoids分布聚类)通常要求簇内最大距离(d_L)小于簇间最小距离(d_H)。本文在固定样本量(FSS)设定下证明:当d_I < d_H时,SLINK可实现指数一致性,其中d_I为某簇内任意两个子簇间的最大距离,一般有d_I < d_L。因此,该结果扩大了SLINK的适用范围。模拟显示,在某些情形下k- medoids无法识别真簇,而SLINK仍具指数一致性。随后提出基于SLINK的顺序聚类算法SLINK-SEQ,证明其同样具有指数一致性;模拟结果表明,相同错误概率下,SLINK-SEQ所需期望样本数少于FSS SLINK。
原文摘要 · Abstract (English)
In this paper, we consider nonparametric clustering of $M$ independent and identically distributed (i.i.d.) data sequences generated from {\em unknown} distributions. The distributions of the $M$ data sequences belong to $K$ underlying distribution clusters. Existing results on exponentially consistent nonparametric clustering algorithms, like single linkage-based (SLINK) clustering and $k$-medoids distribution clustering, assume that the maximum intra-cluster distance ($d_L$) is smaller than the minimum inter-cluster distance ($d_H$). First, in the fixed sample size (FSS) setting, we show that exponential consistency can be achieved for SLINK clustering under a less strict assumption, $d_I < d_H$, where $d_I$ is the maximum distance between any two sub-clusters of a cluster that partition the cluster. Note that $d_I < d_L$ in general. Thus, our results show that SLINK is exponentially consistent for a larger class of problems than previously known. In our simulations, we also identify examples where $k$-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent. Then, we propose a sequential clustering algorithm, named SLINK-SEQ, based on SLINK and prove that it is also exponentially consistent. Simulation results show that the SLINK-SEQ algorithm requires fewer expected number of samples than the FSS SLINK algorithm for the same probability of error.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。