affinitypropagation聚类算法的扩展及改进研究

《affinitypropagation聚类算法的扩展及改进研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、AffinityPropagation聚类算法的扩展及改进研究AffinityPropagation聚类算法的扩展及改进研究陈新泉上饶师范学院数学与计算机科学学院，江西上饶（334001）摘要当前在有限区域内分布的稀疏不均的、具有一定分布结构的海量数据点集的聚类分析是一个尚未圆满解决的难题，针对AffinityPropagation(AP)聚类算法的不足之处，提出了两个扩展及改进型的聚类算法。在这两个算法中，基于“单元网格”的AP聚类算法是在“单元网格”层次上对AP聚类算法的一种扩展，而基于近邻点集的AP聚类算法是试图在时间上对AP聚类算法做一些改进。为实现这两个算法

2、介绍了“单元网格”、近邻点集等几个比较重要的概念及思想方法。最后给出了一点颇有价值的研究方向。关键词：相似性度量；AffinityPropagation;单元网格；近邻点集中图分类号：TP1811.引言当前，高维、噪声、孤立点、大小形状不一、数据点的空间分布不均的海量数据集的聚类分析仍未获得圆满的解决。AffinityPropagation聚类算法是B.J.Frey等[1]于2007年发表在science上的一种聚类方法。尽管该文称其聚类效果很好，计算速度也很快，但它也有几个缺点。第一，它也需要事先定义一个相似性度量，从而计算出数据点集之间的相似性矩阵来，这在时间和空

3、间上就需要O(n2)。第二，迭代次数需要人工设定，而且聚类结果对此也较敏感。第三，获得聚类结果后，不能获得聚类分布的层次性，有时这是不够的。基于密度的聚类算法，主要有Ester等[2]提出的DBSCAN算法和Ertoz等[3]提出的SNN算法。DBSCAN算法最初的时间复杂度为O(n2)。后续的研究者设计出支持区域查询的空间索引结构，宣称将时间复杂度降低到O(nlogn)。我们认为，具有这种时间复杂度的算法能满足海量数据集的聚类分析，但未必适合于高维情形下的聚类分析。因为这种建立在树型存储结构上的改进式算法忽略了维数对存储空间及时间复杂度的影响。本文针对在m维有限区域

4、内分布的海量数据点集，构造出一种与相应数据结构相匹配的能改善时间及空间复杂度的高效聚类算法。该算法既有DBSCAN聚类算法的一点思想，也具有AffinityPropagation算法的一些方法，还具有多维网格划分法的一些优化改进方面的实现技术。本文第2节描述了“单元网格”层次上的聚类分析的概念及相关定义，第3节介绍了基于“单元网格”的AP聚类算法，第4节介绍了基于近邻点集的AP聚类算法，最后对本文作简要的总结并指出进一步的研究方向。2.“单元网格”层次上的聚类分析2.1问题描述设数据点集},,,{21nXXXSL=位于m维有序属性空间)(1mAA××L的某个区域内。如

5、果数据点集分布非常密集，数据点数目也非常多，则可采用多维网格划分法来统计具有一定数据点数目的“单元网格”，从而将对数据点集的聚类分析转换为有效“单元网格”的空间结1//.paper.edu中国科技论文在线构分布分析，这样可以提高算法的效率。以“单元网格”的数据点数目来描述该“单元网格”，就有点基于密度聚类的思想。以一个“单元网格”代替某个小区域的“数据点”作为一个小整体来进行聚类分析，这就是“单元网格”层次的近似聚类分析。2.2几个定义定义1：“单元网格”的定义：数据点集经过多维网格划分后得到一个个相连接的单个网格，就被称为“单元网格”。若某个“单元网格”所包含的数据

6、点数目超过某个阈值，它就被称为有效“单元网格”。“单元网格”的数据结构定义为：DS(g)=(Grid_Label,Grid_Position,Grid_Range,Point_Number)(1)式(1)中，Grid_Label:记录“单元网格”的标号；Grid_Position:记录“单元网格”的中心位置，它为m维向量，即),,(1mppPL=；Grid_Range:记录“单元网格”所包含的区域范围，它为m维的有序局部区间，即：])2/,2/[,],2/,2/([1111mmmmrprprprpR+??+??=L(2)式(2)中，为“单元网格”在第i维的区间长度；)

7、,,1(miriL=Point_Number:记录“单元网格”所包含的数据点数目。这样，原来对n个数据点的聚类分析就可以转换为N个“单元网格”的空间拓扑结构分析了。定义2：“单元网格”间的相似性度量设有效“单元网格”集为},,,{)(21NgggSGridL=，当jigg≠时，借鉴万有引力定律及库仑定律，定义一种相似性度量为),(1)()(),(??jijijiggdgcgcggs+??=(3)式(3)中，采用“单元网格”g),(jiggdi和gj的中心点之间的距离来作为它们的相异性度量，c(gi)为有效“单元网格”gi所含数据点的个数。对归一化，得