基于稀疏表示的近邻传播聚类算法①胡XX②,邹XX③,陈XX③②③XX大学计算机与信息科学学院,重庆400000摘要:,,,:稀疏表示,近邻传播,聚类,距离度量图书分类号标识码:、数据挖掘、机器学习、数据压缩存储及城市规划等方面都有广泛的应用[1].聚类算法一般可以分为树式聚类算法、划分式聚类算法、网格式聚类算法、①基金项目:国家自然科学项目(项目号:61003203)②胡XX(1988-)男安徽XX人硕士研究方向:机器学习,智能web与网络③通讯作者:邹XX(1965-)男四川XX人副教授研究方向:智能web技术及其应用、信息技术教育2007年在《Science》上提出的近邻传播聚类(AffinityPropagationclustering,AP)[2][3](如Kmeans,SpectralClustering[1])传播聚类算法不要求输入的距离矩阵为对称,亦不要求样本之间的距离大小为正,因而具有更广泛的应用空间,近几年得到广泛的研究和关注[4][5]类似其他的基于距离度量的聚类算法,,针对该算法在高维数据上的聚类效果不佳的不足,[6][7][8],将稀疏表示理论得到的样本重构系数,转化为样本间的相似性度量,再引入到近邻传播算法到中,,稀疏表示能够提高近邻传播聚类算法的效果,,第2部分介绍近邻传播算法,第3部分介绍稀疏表示理论及其在近邻传播算法中的应用,第4部分进行实验分析,(AP)算法是一种基于近邻信息传递的聚类算法,它将每个数据点都当成网络中的一个结点,通过网络中节点的连线进行近邻信息传播来找到最优的类中心点集合,使得所有数据点到最近的类中心点的相似度之和最[9]数据集中所有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作为聚类中心的可能性也增大,这样不断迭代,可得到最终的聚类中心[2]4XX大学学报(自然科学版)(SR)[3]是对一个N维的信号进行变换,只用K个非零系统来近似或完整地表示该信号,其中K<<∈Rm,且X=[x1,x2,x3,…,xn],则X∈Rm×n,n为样本数量,∈Rn就是其重构系数:=argmin||s||0subjecttoXs=y()||s||0是求取s的0阶范式,()公式是一个NP难问题,故在知道s稀疏的情况下,可将对s的的求解转换为下面的公式:=argmin||s||1subjectto||Xs-y||2≤ε()上式由于有噪声影响,难以得到样本y,为了平衡范式与重构误差,引入参数λ,可将公式()转化为下列公式:s()则=[,,…]为重构误差最小和稀疏表示约束下的稀疏重构系数,本文把作为样本间相似度的测量,则为y与xi的相似度大小[7].
基于稀疏表示的近邻传播算法-原始论文 来自淘豆网m.daumloan.com转载请标明出处.
