AffinityPropagation聚类算法扩展和改进研究

《AffinityPropagation聚类算法扩展和改进研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、http://www.paper.edu.cnAffinityPropagation聚类算法的扩展及改进研究陈新泉上饶师范学院数学与计算机科学学院chenxqscut@126.com摘要在有限区域内分布的稀疏不均的、具有一定分布结构的海量数据集的高效、高精度聚类问题是一个尚未完全圆满解决的难题。针对AffinityPropagation聚类算法(AP)的不足之处，提出了两个改进型的聚类算法。在这两个算法中，基于单元网格的AP聚类算法(APGC)是在单元网格层次上对AP算法的一种有效的扩展性改进，而基于近邻抽样的AP聚类算法(APNS)在时空复

2、杂度上对AP算法做了一点改进。为描述并实现这两个新算法而给出了单元网格、近邻点集等几个比较重要的概念及方法。通过3个聚类算法对多个数据集的仿真对比实验，可以看出APGC和APNS算法在时空复杂度方面相对于AP算法的改进是明显的。其中APGC算法在过滤掉噪声的同时能对海量数据集进行有效地聚类，最终可以获得良好的聚类结果。可见，APGC算法是一种很有应用前景的聚类算法。最后给出了两个颇有价值的研究方向。关键词：相似性度量；AffinityPropagation;单元网格；近邻点集中图分类号：TP1811.引言在机器学习领域，聚类又称为无监督学习，

3、指的是试图发现无标号数据集中内在的分布结构。从直觉上来说，同一个聚类里的数据点应该比不同聚类的数据点更相似一点。聚类在许多领域中都得到应用，如：心理学和其它社会科学、生物学、统计学、模式识别、信息检索、机器学习和数据挖掘[1,2]。聚类算法大致可分为基于划分的优化聚类算法，层次聚类算法，基于密度的聚类算法，基于网格的聚类算法，基于模型的聚类算法这五大类。其中每类算法都有大量的研究文献。但高维、多处含随机噪声或孤立点、聚类区域的大小及形状不一、空间分布不均的海量数据集的聚类分析仍未获得圆满有效地解决。AffinityPropagation(AP

4、)聚类算法是B.J.Frey等[3]于2007年发表在science上的一种聚类方法。尽管该文称其聚类效果良好，聚类速度快，但我们认为该文更大的价值是体现在理论创新上。这种新型聚类算法的一个很大的缺点就是它需要在给定一种相似性度量之后计算出数据集的相似性矩阵来，这在时间和空间上就需要Θ(n2)的代价(采用C语言实现该算法时需要O(t·n3)的时间代价)。InmarE.Givoni等[4]于2008年将AP算法推广到二分类别属性数据集的聚类分析中。接下来的几年里，这个研究组又发表了多篇侧重于应用方面的论文，从而扩大了这类聚类算法的影响力。基于密

5、度的聚类算法，主要有Ester等[5]提出的DBSCAN算法和Ertoz等[6]提出的SNN算法。最初开发出的DBSCAN算法的时间复杂度为O(n2)。后续的研究者设计出支持区域查询的空间索引结构，称将时间复杂度降低到O(nlogn)。具有O(nlogn)时间复杂度的算法基本上能满足低维海量数据集的聚类分析，却未必适合于高维海量数据集。因为这种建立在树型存储结构上的改进式算法忽略了维数对存储空间及时间复杂度的影响。11http://www.paper.edu.cnSTING[7]是基于网格的一种多分辨率的聚类方法，它将空间量化为网格结构，后续

6、的所有聚类操作都是在网格上进行的。CLIQUE[8]是基于网格和基于密度的混合聚类方法。这两类算法与本文提出的基于单元网格的AP聚类算法在思想上具有某些相似。本文针对在m维有限区域内分布的海量数据集，提出了构建在一定数据结构之上的能改善时空复杂度的两个聚类算法。第一个算法具有DBSCAN聚类算法的一点思想，还含有采用多维网格划分法而使用的一些优化改进技术。第二个算法则利用近邻点集的思想来改进AP算法的时空效率。这两种算法是在AP算法的基本思想及方法基础上的改进。本文第1节描述了单元网格的几个相关概念之后，介绍了基于单元网格的AP聚类算法。第2

7、节介绍了基于近邻抽样的AP聚类算法。第3节通过多个人工数据集的仿真对照实验，来比较这两个新算法与AP算法在聚类效果及时空复杂度方面的优劣。最后对本文作简要的总结并指出进一步的研究方向。1.单元网格层次上的聚类分析2.1问题描述及定义设数据集S={X1,X2,…,Xn}分布在m维有序属性空间(A1×…×Am)的某个有限空间内。如果数据集在多个局部区域非常密集，数据点数目也非常多，则可在采用多维网格划分法划分空间后来统计超过一定数据点数目的单元网格，从而将对数据集在数据点层次上的聚类分析转换为单元网格层次上的空间结构分布分析，这样可以提高算法的效

8、率。以单元网格的数据点数目及其中心位置来描述该单元网格，就有点类似于基于密度的聚类。以一个单元网格代替某个小区域内所含的数据点，并把它看作一个单元来进行聚类分析，这