基于随机游走的数据聚类

《基于随机游走的数据聚类》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

HansJournalofDataMining数据挖掘,2017,7(3),70-76 PublishedOnlineJuly2017inHans.http://www.hanspub.org/journal/hjdm https://doi.org/10.12677/hjdm.2017.73008DataClusteringBasedonRandomWalkWeiCui1,XunXia1,YuluSun2*1LuzhouVocationalandTechnicalCollege,LuzhouSichuan2CollegeofElectronic&InformationEngineering,SichuanUniversity,ChengduSichuanReceived:Jun.28th,2017;accepted:Jul.17th,2017;published:Jul.20th,2017AbstractInordertorealizetheclusteringanalysisoflargedatavolumeandcomplextypesofdata,the randomwalkalgorithmmapsthedatasetintographs,eachdatarepresentsnode,andusesa weightingfunctiontorepresenttherelationshipbetweendataanddata.Thesimilaritycriterion indicatestheweightbetweentwodatainthedataset.Intherandomwalkalgorithm,theweightof theweightrepresentstherandomwalkerfromthenon-seedpointforthefirsttimetoreacha seedpointofpreference.Finally,clusteranalysisisrealizedaccordingtothemaximumtransition probability.Theresultsshowthattherandomwalkalgorithmcanachieveclusteringintheclus- teringanalysisofnumericaldata.KeywordsClusteringAnalysis,RandomWalkAlgorithm,WeightingFunction基于随机游走的数据聚类崔伟1，夏汛1，孙瑜鲁2*1泸州职业技术学院，四川泸州2四川大学电子信息学院，四川成都收稿日期：2017年6月28日；录用日期：2017年7月17日；发布日期：2017年7月20日摘要为了实现大数据量、复杂类型数据的聚类分析，本文运用随机游走算法是将数据集合映射为图，各个数 据表示节点，用一个加权函数表示数据与数据之间的关系，该加权函数能根据相似性准则表示数据集中*通讯作者。文章引用:崔伟,夏汛,孙瑜鲁.基于随机游走的数据聚类[J].数据挖掘,2017,7(3):70-76.https://doi.org/10.12677/hjdm.2017.73008 崔伟等两个数据间的权重。在随机游走算法中，权重的大小代表了随机游走者从非种子点第一次到达某一种子 点的偏好。最后根据最大转移概率实现聚类分析。结果表明随机游走算法在数值型数据的聚类分析中能够实现聚类。关键词聚类分析，随机游走，权重函数Copyright©2017byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY). http://creativecommons.org/licenses/by/4.0/OpenAccess1.引言聚类是按照某个特定准则把已知数据集分成不同的类，同类的数据对象间相似度尽可能大，不同类的数据对象间的相似度尽可能小。聚类分析作为数据挖掘技术中的重要组成部分，目前在许多领域都得到了广泛的研究和应用如模式识别[1]、数据分析[2]、图像处理[3]、市场研究[4]、Web文档分类[5]等。聚类算法的选择取决于数据的类型及其聚类的目的。根据其基本思想可分为划分、层次、密度、基于网格的方法以及基于模型的方法。基于划分的主要思想是：首先给定簇数目，然后对数据集采用迭代重定位方法实现划分，划分质量取决于初始种子和聚类标准。K-means算法[6]从数据集中任意选择k个对象作为初始种子，以最短距离为准则将数据进行分类，该方法以均值表示类中心易受奇异数据的影响，为了抑制异常数据对聚类的影响，K-medoids算法[7]以类个体表示聚类中心。上述算法因采用平方误差作为收敛条件，聚类结果为局部最优解，对此提出了调和均值(KHM)算法[8]的评价函数。基于划分方法的聚类需要先验知识，即事先指定数据类别个数，为了避免个数对聚类结果的影响提出了层次聚类算法如AGNES算法[9]，其主要思想是首先将每个数据对象作为初始簇，然后对这些单元类逐层根据距离最近原则进行聚合，使单元簇越来越大直至满足所要求的簇数目为止。AGNES算法比较简单，但可伸缩性较差。为此提出了DIANA算法[10]，该算法将给定数据看作一个大的簇，在每一步迭代过程中将上层簇根据簇的直径或平均相异度分解为更小的簇，直至满足终止条件。传统层次聚类方法聚类过程中会遇到合并或分裂点选择的困难，因此Guha等人提出了改进的层次聚类算法CURE算法[11]。该方法用具有代表性的若干点代表一个聚类，避免了用所有点或单个质心代表一个簇的传统方法，使其能够识别具有复杂形状和不同大小的聚类，从而对孤立点的处理更加健壮。大多数聚类算法在进行聚类时只估计点与点之间的相似度，这种局部算法很容易出现错误。因此ROCK算法[12]在CURE算法基础上根据成对点的邻域情况进行聚类比只关注相似度的聚类方法更加鲁棒。基于层次和划分的聚类算法对凸形的聚类簇效果较好，而数字点阵图由于形状变化较大，聚类效果较差且运行时间较长。为了弥补上述聚类算法的不足，本文利用随机游走算法进行分析。随机游走在聚类分析中的应用首先选择聚类中心，以初始聚类中心为中心，逐个输入样本；利用随机游走算法得到各个初始聚类中心到达输入样本的概率，以最大转移概率为原则将样本归入聚类中心所属的那一类。同时利用均值计算该类的重心，以该重心作为新的聚类中心再输入下一个样本，直到所有数据被分类。2.随机游走随机游走算法将给定数据集合看作固定数目的节点和边的离散对象，然后将数据聚类分析问题转化71 崔伟等为无向加权图来进行求解。对数据集进行统一的定义，首先将数据集映射成一个无向加权图G=(V,E)，它由代表数据值的节点v∈V和表示数据与其相邻数据间关系的边界e∈E⊆V×V组成。e表示连接两iij个顶点vV和V的边，每条边被赋予一定的权值，记为w，表示两个顶点之间的相似或差异程度。顶点ijijid=∑w，它等于所有与结点的度定义为V相关联的边的权值的和；此外，假设w>0且w=w。由iijiijijji于随机游走算法是一种人工交互式的算法，因此用户需要预先根据数据性质设置k个种子点(标记点)，然后为每个未被标记的数据节点分配一个k维向量，来表示一个未被标记点到达所有种子点的随机游走过程，每一维向量表示从每个未标记点出发，第一次到达k个种子点的概率。k个概率中最大的值为未标记点所属的类标签，通过该方法具有相似性的数据就可归为一类，从而根据不同类别之间的差异实现数据聚类。利用径向基核函数定义数据间的相似度即：−2qqw=−,expijijk(1)其中，k表示聚类数目，q,q表示数据集中任意两个数据。ij1.随机游走求解在一定的边界条件下，随机游走转移概率的求解问题与联合狄利克雷求解问题的解相似。因此，可以通过求解联合狄利克雷问题的解来实现随机游走算法求解。在给定区域Ω上狄利克雷积分形式为：1[]=∫∇2Ω(2) Duud2Ω随机游走从一个非标记点到标记点的概率等于该标记点在边界条件下的狄利克雷函数，求解的问题即在某个边界条件下求解拉普拉斯函数如：∂2∂2uu∇u=+=2220∂i∂j(3)组合拉普拉斯矩阵在映射图中定义如下所示：di=jiL=−wv与v为相邻接点ijijij0其它(4) 拉普拉斯L的值由节点ijv与iv共同决定，该矩阵是满足边界条件下的对称正定矩阵。d为节点v的jii度，定义为=∑表示w第i行所有元素之和。ndwij=ij1图G的m×n条边即顶点间的关联矩阵为：+1i=kA=−j=k1evijk0其它(5)由上式可知，关联矩阵由边e和节点ijv决定，图中ke为任意方向，A为联合梯度算子，AT为联合ij散度算子。我们构造一个大小为m×m的对角阵C，其对角线上的值为映射图边上的权值即：72 崔伟等Ceeijks==(),weikjs=ij0(6)如果连续，联合梯度算子和联合散度算子之积可以表示各向同性的联合拉普拉斯矩阵即：L=ATA。在映射图中，矩阵C可看作向量上一个加权内积大小的度量，此情况下，当C=I时，L=ATCA可简化为L=ATA。因此，调和函数求解问题可通过上述定义解决即：在固定标记点值已知情况下，非标记点到标记点的概率值可求。于是式(2)可转化为：11[]=()T()=∑(−)(7)2DxAxCAxwxxijij22e∈Eij式中，L为联合的拉普拉斯矩阵，x为图中数据的概率值，D[x]的最小值可通过联合调和函数x求得，映射图中的所有节点可分为未标记点集合V且V∪V=V，V∩V=ϕ。将拉普拉V和标记点集合集UMMUMU斯矩阵按标记点和未标记点排列得：1LBx[]=TTMMDxXXUMUT2BLxUU(8)拉普拉斯矩阵分解为：LLB=MBLTU(9)其中，,Dx求XX分别为标记点和非标记点的随机游走概率值，对[]BUUX的微分得：ULx=−Bx(10)TUUM令xs表示未标记点到达标记点为s的概率，定义一个表示所有标记点集合的函数：i(),Qv=s∀v∈V且0