基于稀疏表示的近邻传播算法.doc

基于稀疏表示的近邻传播聚类算法摘要:,,,:稀疏表示,近邻传播,聚类,、数据挖掘、机器学习、数据压缩存储及城市规划等方面都有广泛的应用[1].聚类算法一般可以分为树式聚类算法、划分式聚类算法、网格式聚类算法、《Science》上提出的近邻传播聚类(AffinityPropagationclustering,AP)[2][3](如Kmeans,SpectralClustering[1])传播聚类算法不要求输入的距离矩阵为对称,亦不要求样本之间的距离大小为正,因而具有更广泛的应用空间,近几年得到广泛的研究和关注[4][5].类似其他的基于距离度量的聚类算法,,针对该算法在高维数据上的聚类效果不佳的不足,[6][7][8],将稀疏表示理论得到的样本重构系数,转化为样本间的相似性度量,再引入到近邻传播算法到中,,稀疏表示能够提高近邻传播聚类算法的效果,,第2部分介绍近邻传播算法,第3部分介绍稀疏表示理论及其在近邻传播算法中的应用,第4部分进行实验分析,(AP)算法是一种基于近邻信息传递的聚类算法,它将每个数据点都当成网络中的一个结点,通过网络中节点的连线进行近邻信息传播来找到最优的类中心点集合,使得所有数据点到最近的类中心点的相似度之和最大[1].数据集中所有N个样本都被视为候选的聚类中心点,为每个样本xi建立与其它样本xj的相似度关系s(i,j).s(i,j)值越大,,即s(i,j)为相同的值p,(responsibility)和归属度(availability)(i,j)由样本点xi指向候选聚类中心xj,用来表示xi选择xj作为聚类中心点的支持程度;归属度a(i,j)由候选聚类中心xj指向样本点xi,,当r(i,j)与a(i,j)增大,xj作为聚类中心的可能性也增大,这样不断迭代,可得到最终的聚类