AffinityPropagation算法介绍
更新时间:2024-04-13 00:39:01 阅读量: 综合文库 文档下载
AP聚类算法
1.分类与聚类 1.1 分类算法简介
分类(classification )是找出描述并区分数据类或概念的模型(或函数),以便能够使用模型预测类标记未知的对象类。在分类算法中输入的数据,或称训练集(Training Set),是一条条的数据库记录(Record)组成的。每一条记录包含若干条属性(Attribute),组成一个特征向量。训练集的每条记录还有一个特定的类标签(Class Label)与之对应。该类标签是系统的输入,通常是以往的一些经验数据。一个具体样本的形式可为样本向量:(v1, v2, ... , vn; c)。在这里vi表示字段值,c表示类别。
分类的目的是:分析输入的数据,通过在训练集中的数据表现出来的特性,为每一个类找到一种准确的描述或者模型,这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的,我们仍可以由此预测这些新数据所属的类。注意是预测,而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说:我们获得了对这个类的知识。 下面对分类流程作个简要描述:
训练:训练集——>特征选取——>训练——>分类器 分类:新样本——>特征选取——>分类——>判决
常见的分类算法有:决策树、KNN法(K-Nearest Neighbor)、SVM法、VSM法、Bayes法、神经网络等。
1.2 聚类算法简介
聚类(clustering)是指根据“物以类聚”的原理,将本身没有类别的样本聚集成不同的组,这样的一组数据对象的集合叫做簇,并且对每一个这样的簇进行描述的过程。与分类规则不同,进行聚类前并不知道将要划分成几个组和什么样的组,也不知道根据哪些空间区分规则来定义组。它的目的是使得属于同一个簇的样本之间应该彼此相似,而不同簇的样本应该足够不相似。
聚类分析的算法可以分为:划分法(Partitioning Methods)、层次法(Hierarchical Methods)、基于密度的方法(density-based methods)、基于网格的方法(grid-based methods)、基于模型的方法(Model-Based Methods)。经典的K-means和K-centers都是划分法。
1.3 分类与聚类的区别
聚类分析也称无监督学习或无指导学习,聚类的样本没有标记,需要由聚类学习算法来自动确定;在分类中,对于目标数据库中存在哪些类是知道的,要做的就是将每一条记录分别属于哪一类标记出来。聚类学习是观察式学习,而不是示例式学习。可以说聚类分析可以作为分类分析的一个预处理步骤。
2. k-means算法
k-means算法接受输入量k;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较低。簇的相似度是关于簇中对象的均值度量,可以看作簇的质心(centriod)或重心(center of gravity)。
k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中
心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.,其定义如下:
????|p?mi|2i?1p?Cik(1)
其中,E是数据集中所有对象的平方误差和,p是空间中的点,表示给定对象,mi是簇Ci的均值(p和mi都是多维的)。换句话说,对于每个簇中的每个对象,求对象到其簇中心距离的平方,然后求和。这个准则试图使生成的k个结果簇尽可能的紧凑和独立。
例1:我们在二维空间中随机的生成20个数据点,将聚类数目指定为5个,并随机生成一个聚类中心(用“×”来标注),根据对象与簇中心的距离,每个对象分属于最近的簇。初始示例图如下:
图1.随机生成的数据点及初始聚类中心示例图
下一步,更新簇中心。也就是说,根据簇中的当前对象,重新计算每个簇的均值。使用这些新的簇中心,将对象重新分成到簇中心最近的簇中。
不断迭代上面的过程,直到簇中对象的重新分布不再发生,处理结束。最终的聚类结果示例图如下:
图2. 最终聚类结果示例图
从上图中我们可以看到,最终的聚类结果受初始聚类中心的影响很大,而且最后的簇质心点不一定是在数据点上。
K均值算法试图确定最小化平方误差的k个划分。当结果簇是紧凑的,并且簇与簇之间明显分离时,它的效果较好。对处理大数据集,该算法是相对可伸缩的和有效率的,因为它的计算复杂度是O(nkt),其中n是对象的总数,k是簇的个数,t 是迭代的次数。通常地,k< 然而,只有当簇均值有定义的情况下k均值方法才能使用。在某些应用中,例如当涉及具有分类属性的数据时,均值可能无定义。用户必须事先给出要生成的簇的数目k可以算是该方法的缺点。K均值方法不适合于发现非凸形状的簇,或者大小差别很大的簇。此外,它对于噪声和离群点数据是敏感的,因为少量的这类数据能够对均值产生极大的影响。 3.AP算法 Affinity Propagation (AP) 聚类是最近在Science杂志上提出的一种新的聚类算法。它根据n个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即两个数据点互相之间的相似度不等。这些相似度组成n*n的相似度矩阵s(其中n表示数据集有n个数据点)。 AP算法不需要事先指定聚类数目,相反它将所有的数据点都作为潜在的聚类中心,称之为exemplar。以s矩阵的对角线上的数值s(k, k)作为k点能否成为聚类中心的评判标准,这意味着该值越大,这个点成为聚类中心的可能性也就越大,这个值又称作参考度p (preference)。聚类的数量受到参考度p的影响,如果认为每个数据点都有可能作为聚类中心,那么p就应取相同的值。如果取输入的相似度的均值作为p的值,得到聚类数量是中等的。如果取最小值,得到类数较少的聚类。 AP算法中传递两种类型的消息(responsibility)和(availability)。r(i,k)表示从点i发送到候选聚类中心k的数值消息,反映k点是否适合作为i点的聚类中心。a(i,k)则从候选聚类中心k发送到i的数值消息,反映i点是否选择k作为其聚类中心。r (i,k)与a (i, k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值,直到产生m个高质量的exemplar,同时将其余的数据点分配到相应的聚类中。 在这里介绍几个文中常出现的名词: exemplar:指的是聚类中心。 similarity:数据点i和点j的相似度记为s(i, j)。是指点j作为点i的聚类中心的相似度。一般使用欧氏距离来计算,如?(xi?xj)2?(yi?yj)2。文中,所有点与点的相似度值全部取为负值。因为我们可以看到,相似度值越大说明点与点的距离越近,便于后面的比较计算。 preference:数据点i的参考度称为p(i)或s(i,i)。是指点i作为聚类中心的参考度。一般取s相似度值的中值。 responsibility: r(i,k)用来描述点k适合作为数据点i的聚类中心的程度。 availability:a(i,k)用来描述点i选择点k作为其聚类中心的适合程度。 两者的关系如下图: responsibility 数据点i availability 图3. 数据点之间传递消息示意图 下面是r与a的计算公式: 数据点k ''r(i,k)?s(i,k)?max{a(i,k)?s(i,k)}'k?k(2) '?min0,r(k,k)?max{0,r(i,k)}},i?k??'?i?{i,k}a(i,k)??i?k??max{0,r(i',k)},'??i?k{(3) 由上面的公式可以看出,当s(k, k)较大使得r(k, k)较大时,a(i, k)也较大, 从而类代表k作为 最终聚类中心的可能性较大;同样,当越多的s(k, k)较大时,越多的类代表倾向于成为最终的聚类中心。因此,增大或减小s(k, k)可以增加或减少AP输出的聚类数目。 Damping factor(阻尼系数):主要是起收敛作用的。AP聚类算法迭代过程很容易产生震荡,所以一般每次迭代都加上一个阻尼系数?(??[0.5,1)): rnew(i,k)??*rold(i,k)?(1??)*r(i,k)anew(i,k)??*aold(i,k)?(1??)*a(i,k)(4) (5) AP算法的具体工作过程如下: 先计算n个点之间的相似度值,将值放在s矩阵中,再选取p值(一般取s的中值)。设置一个最大迭代次数maxits (文中设默认值为1000),迭代过程开始。 迭代的过程主要更新两个矩阵,代表(Responsibility)矩阵r=[r(i,k)],(n*n)和适选(Availabilities)矩阵a=[a(i,k)],(n*n)。这两个矩阵初始化为0,n是所有样本的数目。r(i,k)表示第k个样本适合作为第i个样本的类代表点的代表程度,a(i,k)表示第i个样本选择第k个样本作为类代表样本的适合程度。迭代更新公式如(2)(3)。 每次更新后就可以确定当前样本i的代表样本(exemplar)点k,k就是使{a(i,k)+r(i,k)}取得最大值的那个k,如果i=k的话,那么说明样本i就是自己这个cluster的类代表点,如果不是,那么说明i属于k所属的那个cluster。当然,迭代停止的条件就是所有的样本的所属经过连续的convits次迭代都不再变化,或者迭代超过了maxits次。 AP聚类算法迭代过程很容易产生震荡,所以一般每次迭代都使用公式(4)(5)。 例2:我们在二维空间中随机的生成20个数据点,将p值设为s矩阵的中值,将convits值设置成20,maxits值设置成1000,用AP算法进行计算,最终聚类结果如下图: 图4. AP算法迭代过程示意图 图5.最终聚类结果示意图 在AP算法中,迭代次数和聚类数目主要受到两个参数的影响。其中,聚数数目主要受preference值(负值)的影响。下面对同一组数据集(200个数据点)进行计算,取不同的preference值得到的聚类数目如下: Preference值 聚类数目 16 11 8 median(s) 2median(s) 2×median(s) 表1.不同的preference得到的聚类数目比较 由表1,我们可以看出,当preference越大时,得到的聚类数目越多。 当取不同的?(阻尼系数)值时,迭代次数和迭代过程中数据的摆动都会有很大的不同,下面同样是对同一组数据集(200个数据点)进行计算,取有代表性的两个值(0.5和0.9)进行比较结果如下: 图6. ?取0.9时的迭代示意图 图 7.?取0.5时的迭代示意图 从上面两个图对比中我们可以发现,当?值越小时,迭代次数会减少,但是迭代过程中net Similarity值波动会很大,当要聚类的数据点比较大时,这样难于收敛。当?值较大时,迭代次数会增加,但是总的net Similarity比较平稳。 根据式(4)和式(5),我们也可以看到,每一次迭代的r(i,k)和a(i,k)受到?的影响。当 ?取较小的值时,rnew(i,k)和anew(i,k)相比上一次迭代的rold(i,k)和aold(i,k)会发生较大 的变化,这也是为什么net Similarity值摆动比较大的原因;当?取较大值时,rnew(i,k)和 anew(i,k)和上一次迭代的rold(i,k)和aold(i,k)比较接近,这也是导致迭代次数比较多的原 因。 正是因为如此,有人提出了自适应仿射传播聚类(在文献2中可以看到),文中主要提出了如何根据数据集自动生成preference值和?值的方法。 4. k-means算法与AP算法比较 例3:下面,我们随机在二维空间中生成50个数据点,分别用上面讲述的两种聚类算法进行聚类计算。 我们先进行AP算法聚类,将生成的聚类数量用于k-means算法中,将结果示意图进行比较,具体结果如下: 图 8.AP算法迭代过程 图9.AP算法最终计算结果 图10. k-means算法初始聚类中心示意图 图11.k-means算法最终聚类结果 5.总结与展望 k-means算法对于离散和噪声数据比较敏感,对于初始聚类中心的选择很关键,因为初始聚类中心选择的好坏直接影响到聚类结果,而且这个算法要求进行聚类时输入聚类数目,这也可以说是对聚类算法的一种限制。不过,这种算法运行速度相对于AP算法要快一些,因此,对于那些小而且数据比较密集的数据集来说,这种聚类算法还是比较好的。 AP算法对于p值的选取比较关键,这个值的大小,直接影响都最后的聚类数量。值越 大,生成的聚类数越多,反之如此。而且,那个阻尼系数?对迭代也是很关键的。在文献[2]中有人提及,此算法可能会出现数据震荡现象,即迭代过程中产生的聚类数不断发生变化不能收敛。增大?可消除震荡现象。但根据式[4]和式[5]来看,一味的增大?会使r和a的更新变的缓慢,增加了计算时间。因此,如何选取一个合适?的来进行计算也成了一个提升算法运行速度的重要因素。
正在阅读:
19世纪初期文学03-14
第三章 农业技术变革与部门就业结构的转变(AAA)05-30
电大创业教育2016在线考试题及答案207-27
调查问卷策划书210-24
爱是教师最美丽的语言05-15
基于MATLAB的信号去噪研究04-14
基于平衡计分卡的绩效考核设计方案05-26
- 冀教版版五年级科学下册复习资料
- 微生物学复习提纲
- 2013—2014学年小学第二学期教研组工作总结
- 国有土地转让委托服务合同协议范本模板
- 我的固废说明书
- 企业管理诊断报告格式
- 东鼎雅苑施工组织设计
- 谈谈如何做好基层党支部书记工作
- 浮梁县环保局市级文明单位创建工作汇报
- 管理学基础知识
- 大学物理实验报告23 - PN结温度传感器特性1
- 计算机网络实践
- 酒桌上这四种情况下要坐牢,千万别不当回事……
- 国家康居示范工程建设技术要点
- 中国贴布行业市场调查研究报告(目录) - 图文
- 新课标下如何在高中物理教学中培养学生的创新能力初探
- 营养师冬季养生食谱每日一练(7月4日)
- 关注江西2017年第3期药品质量公告
- 建设海绵城市专题习题汇总
- 10万吨年环保净水剂建设项目报告书(2).pdf - 图文
- AffinityPropagat
- 算法
- 介绍
- ion
- 循证医学试题及答案 - 图文
- 中式宴会摆台比赛规则和评分标准
- 2017年露天采石场安全生产试题题库(十套附答案)
- 关于发布安庆市钢管脚手架补充定额的通知
- 材料力学(填空、、判断、选择)超好
- 小升初数学总复习题库(超全) - 图文
- 3RRR并联机器人机构奇异性分析
- 人教版五年级语文下册全册教案(含教后感)
- 飞思卡尔单片机mc9s12dg128的pwm参考程序
- 2017-2018学年小学六年级语文下册期末检测试卷
- 语法习题(有答案)
- 基于声卡的信号发生器-开题报告
- 圆柱绕流的数值模拟
- 小学趣味运动会方案1
- 青岛版小学数学五年级上册《三角形的面积》教学设计 - 图文
- 生化习题
- 论网络监督的利弊
- 河南方言-南阳方言与普通话的差异
- 实验四 SIMULINK仿真daan
- 《财务管理》第01章到第10章在线测试(全对)要点