二分k-means锚点提取的快速谱聚类.pdf
《二分k-means锚点提取的快速谱聚类.pdf》由会员分享,可在线阅读,更多相关《二分k-means锚点提取的快速谱聚类.pdf(8页珍藏版)》请在咨信网上搜索。
1、Computer Engineering and Applications计算机工程与应用2023,59(16)聚类是通过对相似数据进行分类而获得有价值的信息1。大部分聚类算法通过欧氏几何度量数据相似性2-3,如常见的k-means通常用于进行快速聚类,但它局限于凸分布的数据集,对于一些非凸数据集常常很难有效地描述。相比之下,谱聚类(spectral clustering,SC)是一种基于图的聚类技术,能够有效利用数据的图和流形信息处理非凸形状的簇,与k-means相比,它能够处理更复杂的数据结构,但由于求解特征向量时计算复杂度高而无法直接处理大规模数据。因此,构建解决大规模数据的谱聚类算法成
2、为研究的难点。二分k-means锚点提取的快速谱聚类罗兴隆1,贺兴时1,杨新社21.西安工程大学 理学院,西安 7106002.密德萨斯大学 科学与技术学院,伦敦 NW4 4BT摘要:光谱聚类(spectral clustering,SC)由于在无监督学习中的有效性而受到越来越多的关注。然而其计算复杂度高,不适用于处理大规模数据。近年来提出了许多基于锚点图方法来加速大规模光谱聚类,然而这些方法选取的锚点通常不能很好地体现原始数据的信息,从而导致聚类性能下降。为克服这些缺陷,提出了一种二分k-means锚点提取的快速谱聚类算法(fast spectral clustering algorithm
3、 based on anchor point extraction with bisectingk-means,FCAPBK)。该方法利用二分k-means从原始数据中选取一些具有代表性的锚点,构建基于锚点的多层无核相似图;然后通过锚点与样本间的相似关系构造层次二部图。最后在5个基准数据集上分别进行实验验证,结果表明FCAPBK方法能够在较短的时间内获得良好的聚类性能。关键词:二分k-means;二部图;锚点图;谱聚类文献标志码:A中图分类号:TP181doi:10.3778/j.issn.1002-8331.2205-0036Fast Spectral Clustering Based on
4、 Anchor Point Extraction with Bisectingk-meansLUO Xinglong1,HE Xingshi1,YANG Xinshe21.College of Science,Xi an Polytechnic University,Xi an 710600,China2.College of Science and Technology,Middlesex University,London NW4 4BT,UKAbstract:Spectral clustering(SC)has received increasing attention due to i
5、ts effectiveness in unsupervised learning.However,due to its high computational complexity,it is not suitable for processing large-scale data.In recent years,manyanchor points graph-based methods have been proposed to accelerate large-scale spectral clustering.However,the anchorpoints selected by th
6、ese methods usually cannot well reflect the information of the original data,which leads to the degra-dation of clustering performance.To overcome these shortcomings,a fast spectral clustering algorithm based on anchorpoint extraction with bisectingk-means(FCAPBK)is proposed.The method uses bisectin
7、gk-means to select some repre-sentative anchor points from the original data,then constructs a multi-layer kernel-free similarity graph based on anchorpoints,and constructs a hierarchical bipartite graphs through the similar relationship between the anchor points and thesample.Finally,experiments ar
8、e carried out on five benchmark datasets,and the results show that the FCAPBK method canobtain good clustering performance in a short time.Key words:bisectingk-means;bipartite graphs;anchor points;spectral clustering理论与研发基金项目:国家自然科学基金(12101477);陕西省自然科学基础研究计划(2020JQ-831)。作者简介:罗兴隆(1997),男,硕士研究生,主要研究方向
9、为聚类分析、智能计算,E-mail:;贺兴时(1960),男,硕士,教授,研究方向为优化算法及应用、数理统计等;杨新社(1965),男,博士,英国国家物理实验室高级科学家,主要研究领域为数学建模、工程优化以及科学、数值计算方法等。收稿日期:2022-05-05修回日期:2022-06-13文章编号:1002-8331(2023)16-0074-08742023,59(16)近年来,提出了许多基于锚点图的方法,用于处理谱聚类的大规模数据集,如可扩展的半监督学习4-5、多视图大尺度光谱聚类6、大规模光谱聚类降维7-9以及基于二部图的谱聚类10。与传统的图方法不同,基于锚点图的方法根据锚点建立与原始
10、数据点之间的邻接关系。Zhang等人11首先建议使用一组锚点来对数据流形进行有效的低秩近似,并给出一个信息损失最小的模型。Liu等人12提出了锚点图模型,并将它引入到基于图的学习任务中。Wang等人13随后提出了一种改进算法,显示了更好的性能和计算效率。与传统的图相比,这些基于锚点图的方法可以大大降低图构造的复杂性。Fowlkes等人14采用经典的Nystrm方法加速了特征分解,并应用于谱聚类,得到了处理大数据的ASC算法。该方法使用随机抽样,虽然简单快速,但其不确定性在很大程度上影响了聚类结果,且性能取决于样本集的质量。Li等人15利用随机低秩矩阵近似算法提出了一种可扩展的 Nystrm 方
11、法,对从输入图中采样的列集的内子矩阵进行近似奇异值分解(singular valuedecomposition,SVD),进一步加快了该算法的分解速度。但这类方法占用内存大,易丢失小簇且数值稳定性不高。Shinnou等人16将原始数据集替换为相对较少的数据集,并对较小数据集对应的邻接矩阵进行后续操作。Yan等人17提出了基于均值的近似光谱聚类(k-means-based approximate spectral clustering algorithm,KASP)方法。该方法首先对集群的数据集执行k-means;然后,将传统的光谱聚类应用于各聚类中心,数据点被分配给集群作为其最近的中心。Che
12、n等人18和Liu等人19基于一些数据点快速收敛到真实嵌入,引入了一种顺序缩减算法,从而使早期停止策略加速分解。然而,这类方法由于k-means的局部收敛,若某一质心点聚类错误,则该质心点附近的点均同样聚类错误。本文针对以上选取锚点算法的不足,提出一种二分k-means锚点提取的快速谱聚类算法(fast spectral clus-tering algorithm based on anchor point extraction withbisectingk-means,FCAPBK)。利用二分k-means从原始数据中选取一部分具有代表性的锚点。通过锚点和数据点构造多层锚点图,然后利用原始数
13、据点和最后一层锚点构造二部图,使多层锚点图构成一个层次二部图,该方法既可以使选取到的锚点具有代表性,也可以使谱聚类的复杂度大大降低。最后,对相似图进行谱聚类分析,并在不同实验数据集上验证最终聚类效果。1相关工作1.1谱聚类算法设X=x1,x2,xnTRnd表示n个样本的d维数据集矩阵,其中xiRd表示数据集X中的第i个数据点,将每个数据点xi看作是亲和图上的一个顶点,每个点和点之间的边表示邻接关系。对于n个任意的点i和点j,wij表示xi和xj之间边的权重,W=wijRnn表示亲和图的邻接矩阵。wij以高斯核函数表示如下:wij=e-xi-xj2222,xiKNN(xj)or xjKNN(xi
14、)0,otherwise(1)其中,xi-xj22是xi和xj欧氏距离的平方,是核参数,KNN(xi)表示样本xi的k近邻集合。设L表示图拉普拉斯矩阵,其定义为L=D-W。归一化后的图拉普拉斯矩阵为:L=D-12LD-12=I-D-12WD-12(2)式中,D是一个对角矩阵,第i个对角线上元素为di=jwij。因此,归一化谱聚类20的目标函数被定义为:minFTF=Itr(FTLF)(3)其中,tr()为矩阵的迹,FRnc表示数据集的类指示矩阵。由于F的元素是离散值,求解方程(3)是NP难题。为了使该问题得到解决,通常将矩阵F从离散值松弛为连续值。通过对L的特征值分解,使其转化为L的c个最小特
15、征值对应的特征向量,得到由特征向量组成的松弛连续解。然后,利用k-means等聚类方法来计算离散解。谱聚类步骤如下:步骤 1 数据矩阵X=x1,x2,xnTRnd,生成图的邻接矩阵W和对角矩阵D;步骤2 归一化普拉斯矩阵L=I-D-12WD-12;步骤3 生成L的最小c个特征值及其对应的特征向量;步骤4 将c个特征值对应的特征向量通过k-means聚类。1.2基于二分k-means选取锚点近年来,在大规模数据集中基于锚点的方法21有了广泛的应用,不仅在基于图的方法中降低了计算成本,而且获得了良好的效果。基于锚点的方法是从原始数据点中选取m(mn)个代表原始数据结构的代表点,称为锚点。锚点的选取
16、方式通常有两种:一种是从原始数据中随机选取锚点,随机选取虽然快速、简单,但得到的锚点是随机的,不能很好地体现原始数据的结构;另一种是采用k-means选取锚点,使用k-means得到原始数据的中心,使用得到的中心点作为锚点。该方法虽然得到锚点比随机选取有代表性,但由于k-means对数据输入顺序敏感而且仅考虑数据的空间局部信息,易选取过多的噪声成为锚点。针对这些问题,本文引入二分k-means算法来选取锚点,不但对噪声鲁棒,对数据输入顺序不敏感,而且通罗兴隆,等:二分k-means锚点提取的快速谱聚类75Computer Engineering and Applications计算机工程与应用
17、2023,59(16)过每次选择误差和SSE最小的簇进行划分,在一定程度上能避免选取到噪声点。1.2.1二分k-means算法k-means是一种基于划分方法的聚类,然而传统k-means算法对噪声点和离群点很敏感。针对这一局限性,很多国内外学者都做了相关的研究。左进等人22通过计算数据点的紧密性值,选取不是异常值的初始聚类中心,使聚类效果在全局范围内是最佳的。Xia等人23通过搜索邻居簇和将查询到的簇划分为稳定的和活跃的区域来加速标准k-means算法。Duan等人24提出了一种基于大距离和高密度的中心点初始化方法,用距离加权平均的倒数表示样本密度,选择距离较大、密度较高的数据样本作为初始聚
18、类中心。Ding等人25提出了一种Yinyangk-means算法,通过在初始阶段对中心进行聚类,有效地保持数据点和中心点之间的上下界,避免了不必要的距离计算。有学者提出了二分k-means聚类算法,该算法减少了聚类相似度的计算量,从而能加快k-means执行速度。在选取聚类中心时进行了优化,因此能较好地克服对初始中心敏感的问题,有着相对稳定的聚类性能。二分k-means算法26具体步骤如下:首先,将数据集的所有样本初始化为同一个簇,计算该簇数据集的质心;其次,使用k-means算法将该簇一分为二,以最小化聚类代价函数(误差平方和)为选择依据,在所得到的簇中选择一个簇进行一分为二划分;不断重复
19、以上步骤,直到选出给定的k个簇作为终止条件。算法1 基于二分k-means算法输入:数据集矩阵X=x1,x2,xnT,聚类簇数k。输出:簇划分C=C1,C2,Ck。1.将所有数据看作一个簇,计算簇中心(数据点的质心)2.while簇中心个数hk(6)其中,k为近邻数据点的数量。由以上计算表达式可以得到无核邻近分配27方法的以下优势:(1)式中求解到的邻接矩阵是自然稀疏矩阵,而稀疏矩阵对于基于图学习任务的计算效率很高。(2)通过表达式计算亲和度只涉及一个近邻参数k,此参数是一个整数,易于调整,且表达式只涉及基本的简单运算。而采用LLE和稀疏编码等方法计算亲和度,涉及到计算高斯函数和其他参数。步骤
20、1 二分k-means步骤2 锚图构造锚点样本点图1选取锚点和构造二部图的过程Fig.1Process of selecting anchor points andconstructing bipartite graphs762023,59(16)(3)数据点的亲和度具有伸缩不变性,不会因为数据样本的扩大、缩小影响其度量尺度。数据点间的距离特征与它们之间的亲和度也具有一致性。图2为锚点和数据点的锚点图构造过程。图中h61、h62和h63是第6个数据点与第1、2、3个锚点的邻接关系(x1,x2,x7是数据点,u1、u2、u3是锚点),且h61+h62+h63=1。2层次二部图的谱聚类分析2.1层
21、次二部图的构造在半监督学习6中,设G=X,U,E表示基于锚点的层次图,其中XRnd为数据集矩阵,U为锚点集,E为相邻层间边邻接矩阵的集合。假设原始数据点X用底层L0表示,其余的锚点层是由多个锚点集U组成的La(a=1,2,h)表示,其中Ua(UaRmad,a=1,2,h)的大小逐渐减小,即m1m2mh,ma是La中的锚点个数。E=H0,1,H1,2,Hh-1,hRnm1,m1m2,mh-1mh,其中Ha-1,a是La-1和La数据点之间的邻接矩阵。在此引入无监督学习中的层次二部图28,由文献28可知,层次二部图由原始数据层L0和最后一层Lh构造。因此,二部图的邻接矩阵12可以写为:W=0HHH
22、TH0(7)其中,WR(n+mh)(n+mh)是邻接矩阵,0表示全 0矩阵,HHRnmh表示原始数据点层L0到最后一层锚点Lh之间累积的邻接矩阵。接下来,使用第1.3节的方法计算从Lh到Lh-1层间的邻接矩阵Hh,h-1,从而得到邻接矩阵:HH=H0,1H1,2Hh-1,h(8)设FG表示Lh中锚点数据集的类指标矩阵,Fx为L0中数据点的类指标矩阵。利用上述累积6邻接矩阵,可以得到从密集L0到稀疏Lh的类指标矩阵28:Fx=H0,1H1,2Hh-1,hFG=HHFG(9)接下来,通过邻接矩阵W求得数据集的对角矩阵D为:D=Da00Db(10)其中,DaRnn和DbRmhmh是一个对角矩阵,Da
23、的对角元素是H的行和,Db的对角元素是H的列和。对于HH中的向量,由行的归一化hTi1=1(1是全为1的列向量)可知,Da=In(In是nn阶单位矩阵),故D可以写为:D=In00Db(11)因此,拉普拉斯矩阵L=D-W(D为对角矩阵)为:L=In00Db-0HHHTH0=In-HH-HTHDb(12)由归一化后的L=I-D-12WD-12可知:L=In00D-12bIn-HH-HTHDbIn00D-12b=In-HHD-12b-D-12bHTHIm=I-0HHD-12bD-12bHTH0(13)其中,Im是mm阶单位矩阵。2.2谱聚类分析由经典谱聚类可知,基于层次二部图28的谱聚类的目标函数
24、29定义为:minFTF=Itr(FTLF)(14)其中,tr()表示矩阵的迹,I是单位矩阵,F=FxFG是所有数据点的类指标矩阵。由谱聚类的相关求解知识可知,对L的特征值分解即为(14)的最优解,由归一化的L可得目标函数为:minFTF=ItrFTI-0HHD-12bD-12bHTH0F(15)接下来,令M=HHD-12b,因此,目标函数(15)可以写成如下:minFTF=Itr FTI-0MMT0F=maxFTF=ItrFT0MMT0F=maxFTxFx+FTGFG=ItrFxFGT0MMT0FxFG=maxFTxFx+FTGFG=Itr(FTxMFG)(16)接下来,通过使用奇异值分解方
25、法对M进行分解,得到F的松弛连续解,令URnn为左奇异向量矩阵、Rnmh为奇异值矩阵、VRmhmh为右奇异向量矩阵。因此,矩阵M的奇异值分解(SVD)可以写成如下:M=UVT(17)最后,通过k-means聚类方法进行离散化处理,计算出离散类指标Y。h63h61h62x2x1x4x3x6x5x7u2u1u3图2锚点图的构造Fig.2Construction of anchor points graph罗兴隆,等:二分k-means锚点提取的快速谱聚类77Computer Engineering and Applications计算机工程与应用2023,59(16)算法2 FCAPBK算法输入:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 means 提取 快速 谱聚类
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。