基于稀疏Parzen窗密度估计的快速自适应相似度聚类方法

摘要：

相似度聚类方法(Similarity-based clustering method,SCM)因其简单易实现和具有鲁棒性而广受关注.但由于内含相似度聚类算法(Similarity clustering algorithm,SCA)的高时间复杂度和凝聚型层次聚类(Agglomerative hierarchicalclustering,AHC)的高空间复杂度,SCM不适用大数据集场合.本文首先发现了 SCM和核密度估计问题的本质联系,并以此入手,通过快速压缩集密度估计器(Fast reduced set density estimator,FRSDE)和基于图的松弛聚类(Graph-based relaxed clustering,GRC)算法提出了快速自适应相似度聚类方法(Fast adaptive similarity-based clustering method,FASCM).相比于原SCM,该方法的主要优点是:1)其总体渐近时间复杂度与样本容量呈线性关系;2)不依赖于人工经验的干预,具有了自适应性.由此,FASCM适用于大数据集环境.该方法的有效性在图像分割应用中进行了验证.

关键词：相似度聚类、密度估计、时间复杂度、图像分割

所属期刊栏目：37

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金60903100;60975027;60773206

在线出版日期：2011-08-10（万方平台首次上网日期，不代表论文的发表时间）

页码：179-187