资源描述：
《基于稀疏表示的近邻传播算法-原始论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于稀疏表示的近邻传播聚类算法①胡XX②，邹XX③,陈XX③②③XX人学计算机与信息科学学院，重庆400000摘要：近邻传播聚类算法是一种基丁-近邻样木之间消息传播的高效聚类方法.该算法不要求输入的样本间距离矩阵为对称或大于0.其最终聚类结杲依赖于距离矩阵的选取，因而设计良好的距离度最可提高近邻传播聚类效果.借助稀疏表示具冇较好刻画样木Z间相似度的特点，木文提出一种基于稀疏表示的近邻传播聚类算法.通过在多个数据集上的实现分析表明，本聚类算法较肚于其它距离度最的算法能获得更好的聚类效果.关键词：稀疏表示，近邻传播，聚类，距离度量图书分类号标识码：A1引言聚类
2、算法是一种在没有显示指导信息下有效的数据分析方法•聚类算法在模式识别、数据挖掘、机器学习、数据压缩存储及城市规划等方面都有广泛的应用⑴.聚类算法一般可以分为树式聚类算法、划分式聚类算法、网格式聚类算法、密度聚类算法和其它聚类算法等.Frey和Ducck①基金项目：国家自然科学项目(项目号：61003203)②胡XX(1988-)男安徽XX人硕士研究方向：机器学习，智能web与网络③通讯作者:邹XX(1965・)男四川XX人副教授研究方向：智能web技术及其应用、信息技术教育2007年在《Science》上提出的近邻传播聚类(AffinityPropaga
3、tionclustering,AP)⑵⑶是新近提出的一•种高效聚类算法•不同于经典聚类算法(如Kmeans,SpectralClustering111)传播聚类算法不要求输入的距离矩阵为对称，亦不要求样本之间的距离大小为正，因而具有更广泛的应用空间，近几年得到广泛的研究和关注⑷闻类似其他的基于距离度量的聚类算法，近邻传播聚类算法也依赖于样本之间的距离度量.原始的近邻传播聚类算法基于样本Z间的欧式距离，针对该算法在高维数据上的聚类效果不佳的不足，廖予良等人提出了基于鲁棒路径相似度的近邻传播聚类算法.本文受稀疏表示对噪声特征鲁棒和具有较好判别性的优点启⑹⑺⑻，
4、将稀疏表示理论得到的样本重构系数，转化为样本间的相似性度量，再引入到近邻传播算法到中，提出一种基于稀疏表示的近邻传播聚类算法.在多个数据集上的实验结杲表明，稀疏表示能够提高近邻传播聚类算法的效果，本文提出的算法较基于其他距离度量的近邻传播算法能够获得更好的聚类效果.本文组织如下，第2部分介绍近邻传播算法，第3部分介绍稀疏表示理论及其在近邻传播算法中的应用，第4部分进行实验分析，第5部分总结全文并提出进一步研究方向.2近邻传播算法介绍近邻传播聚类(AP)算法是一种基于近邻信息传递的聚类算法，它将每个数据点都当成网络中的一个结点，通过网络中节点的连线进行近邻信
5、息传播来找到最优的类屮心点集合，使得所有数据点到最近的类川心点的相似度Z和最®数据集中所有N个样本都被视为候选的聚类中心点，为每个样本xi建立与其它样本xj的相似度关系s(i,j).s(i,j)值越大，相应的点xi被选为聚类屮心点的可能性也越人.算法开始时会假设每个样本数据点成为聚类中心点的倾向程度相同，即s(i,j)为相同的值p,p一般定义为相似度矩阵中的相似度均值.近邻传播算法通过不断迭代更新吸引度(responsibility)和归属度(availability)信息得到聚类此'.吸引度r(i,j)由样本点xi指向候选聚类屮心xj,用来表示xi选择x
6、j作为聚类中心点的支持程度；归属度a(i,j)市候选聚类屮心xj指向样本点xi,用来表示xi选择xj作为聚类由心点的合适程度.这样就综合了xj的最近邻信息和除最近邻信息外的附近点信息，当r(i,j)与a(i,j)增大，xj作为聚类中心的可能性也增大，这样不断迭代，可得到最终的聚类小心〔2】点作为中心点的可能性，综合前两者可以得到xj成为聚类屮心点的可能性⑻a(ij)信息更新规则为:D—min呵®旳J)十Emax畑心妙凶仃)]}(3.6)a(i,j)表示xj成为xi聚类中心点的可能性，r(j,j)为xj点成为中心点的可能性，£皿舐"5钝表示其它不包含xi点的
7、样本点选择xj作为屮心点的可能性.当旳加十签max畑畑®蟻仃力为非负数时，a(i,j)的值为0,即xj点更倾向于成为聚类中心点；反Z,xj更适合作为非聚类中心点.当i=j时，a(j,j)变成j成为其他点的聚类中心点的可能性，呛,j)信息更新规则为：(3.7)a(j,j)由所有其他点所有非负值r(i',j)累加得到[叫算法在迭代过程中，特别是有多个点同吋适合某一类的聚类代表点，算法会出现聚类不稳定的震荡现象•因此在迭代过程中引入重要参数入，即阻尼因子(dampingfactor).在每一次迭代过程中，r(i,j)和a(i,j)的更新结果都是由当前迭代更新的值
8、和上一步的值加权得到，加权更新后的公式如下：eQD・枫■点D+(1
