Learning by Unsupervised Nonlinear Diffusion
Learning by Unsupervised Nonlinear Diffusion
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
M. Maggioni;James M. Murphy
中科院分区：
文献类型：
--
作者：
M. Maggioni;James M. Murphy
本文提出并分析了一种新的聚类算法，结合基于图的扩散几何技术的密度和模式估计。所提出的方法是适用于从混合物的分布密度，这是多峰和非线性形状的数据。该算法的一个重要方面是使用时间的数据适应扩散过程作为尺度参数，这是不同于许多聚类算法中使用的局部空间尺度参数。我们证明了一个灵活的非参数数据模型下的扩散距离相对于这个时间参数的行为的估计，确定一个范围内的时间，其中揭示了介观平衡的基本过程，对应于集群内和集群间的扩散距离之间的差距。这些结构可能会被谱聚类中常用的图拉普拉斯算子的顶部特征向量遗漏。利用这种分析来证明充分条件，保证所提出的\n {无监督非线性扩散学习（隆德）}过程的准确性。我们实现隆德和证实其理论性质的说明性数据集，展示了理论和经验的优势，谱聚类和基于密度的聚类技术。
This paper proposes and analyzes a novel clustering algorithm that combines graph-based diffusion geometry with techniques based on density and mode estimation. The proposed method is suitable for data generated from mixtures of distributions with densities that are both multimodal and have nonlinear shapes. A crucial aspect of this algorithm is the use of time of a data-adapted diffusion process as a scale parameter that is different from the local spatial scale parameter used in many clustering algorithms. We prove estimates for the behavior of diffusion distances with respect to this time parameter under a flexible nonparametric data model, identifying a range of times in which the mesoscopic equilibria of the underlying process are revealed, corresponding to a gap between within-cluster and between-cluster diffusion distances. These structures can be missed by the top eigenvectors of the graph Laplacian, commonly used in spectral clustering. This analysis is leveraged to prove sufficient conditions guaranteeing the accuracy of the proposed \emph{learning by unsupervised nonlinear diffusion (LUND)} procedure. We implement LUND and confirm its theoretical properties on illustrative datasets, demonstrating the theoretical and empirical advantages over both spectral clustering and density-based clustering techniques.