二分k-means锚点提取的快速谱聚类 罗兴隆.pdf

该【二分k-means锚点提取的快速谱聚类 罗兴隆 】是由【玉柱儿】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【二分k-means锚点提取的快速谱聚类 罗兴隆 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
计算机工程与应用
ComputerEngineeringandApplications
ISSN1002-8331,CN11-2127/TP
《计算机工程与应用》网络首发论文
题目:二分k-means锚点提取的快速谱聚类
作者:罗兴隆,贺兴时,杨新社
网络首发日期:2022-06-13
引用格式:罗兴隆,贺兴时,-means锚点提取的快速谱聚类[J/OL].计算
机工程与应用.
.
网络首发:在编辑部工作流程中,稿件从录用到出版要经历录用定稿、排版定稿、整期汇编定稿等阶
段。录用定稿指内容已经确定,且通过同行评议、主编终审同意刊用的稿件。排版定稿指录用定稿按照期
刊特定版式(包括网络呈现版式)排版后的稿件,可暂不确定出版年、卷、期和页码。整期汇编定稿指出
版年、卷、期、页码均已确定的印刷或数字出版的整期汇编稿件。录用定稿网络首发稿件内容必须符合《出
版管理条例》和《期刊出版管理规定》的有关规定;学术研究成果具有创新性、科学性和先进性,符合编
辑部对刊文的录用要求,不存在学术不端行为及其他侵权行为;稿件内容应基本符合国家有关书刊编辑、
出版的技术标准,正确使用和统一规范语言文字、符号、数字、外文字母、法定计量单位及地图标注等。
为确保录用定稿网络首发的严肃性,录用定稿一经发布,不得修改论文题目、作者、机构名称和学术内容,
只可基于编辑规范进行少量文字的修改。
出版确认:纸质期刊编辑部通过与《中国学术期刊(光盘版)》电子杂志社有限公司签约,在《中国
学术期刊(网络版)》出版传播平台上创办与纸质期刊内容一致的网络版,以单篇或整期出版形式,在印刷
出版之前刊发论文的录用定稿、排版定稿、整期汇编定稿。因为《中国学术期刊(网络版)》是国家新闻出
版广电总局批准的网络连续型出版物(ISSN2096-4188,CN11-6037/Z),所以签约期刊的网络版上网络首
发论文视为正式出版。
:.
췸싧쫗랢쪱볤ꎺ2022-06-1311:56:28
췸싧쫗랢뗘횷ꎺ.
1ComputerEngineeringandApplications
二分k-means锚点提取的快速谱聚类
112
罗兴隆,贺兴时,杨新社
,西安710600
,伦敦NW44BT
摘要:光谱聚类(Spectralclustering,SC)由于其在无监督学****中的有效性而受到越来越多的关注。然而,由
于其计算复杂度高,不适用于处理大规模数据。近年来,已经提出了许多基于锚点图方法来加速大规模光
谱聚类,然而这些方法选取的锚点通常不能很好体现原始数据的信息,从而导致聚类性能下降。为克服这
些缺陷,提出了一种二分k-means锚点提取的快速谱聚类算法(Fastspectralclusteringalgorithmbasedon
anchorpointextractionwithbisectingk-means,FCAPBK)。首先,该方法利用二分k-means从原始数据中选
取一些具有代表性的锚点,接着构建基于锚点的多层无核相似图;然后通过锚点与样本间的相似关系构造
层次二部图。最后在5个基准数据集上分别进行实验验证,结果表明,FCAPBK方法能够在较短的时间内
获得良好的聚类性能。
关键词:二分k-means;二部图;锚点图;谱聚类
文献标志码:A中图分类号:TP181doi:.1002--0036
FastSpectralClusteringbasedonAnchorpointextractionwithBisectingk-means
LUOXinglong1,HEXingshi1,YANGXinshe2
,Xi’anPolytechnicUniversity,Xi’an710600,China
,MiddlesexUniversity,LondonNW44BT,UK
Abstract:Spectralclustering(SC)hasreceivedincreasingattentionduetoitseffectivenessinunsupervisedlearning.
However,duetoitshighcomputationalcomplexity,itisnotsuitableforprocessinglarge-,
manyanchorpointsgraph-basedmethodshavebeenproposedtoacceleratelarge-,
theanchorpointsselectedbythesemethodsusuallycannotwellreflecttheinformationoftheoriginaldata,which
,afastspectralclusteringalgo-
rithmbasedonanchorpointextractionwithbisectingk-means(FCAPBK),themethodusesbi-
sectingk-meanstoselectsomerepresentativeanchorpointsfromtheoriginaldata;thenconstructsamulti-layer
kernel-freesimilaritygraphbasedonanchorpoints,andthenconstructahierarchicalbipartitegraphsthroughthe
,experimentsarecarriedoutonfivebench-
markdatasets,andtheresultsshowthattheFCAPBKmethodcanobtaingoodclusteringperformanceinashort
time.
Keywords:bisectingk-means;bipartitegraphs;anchorpoints;spectralclustering
基金项目:国家自然科学基金(12101477);陕西省自然科学基础研究计划(2020JQ-831)。
作者简介:罗兴隆(1997-),男,硕士研究生,主要研究方向为聚类分析、智能计算算法,E-mail:******@;贺兴时(1960-),
男,硕士,教授,研究方向为优化算法及应用、数理统计等;杨新社(1965-),男,英国牛津大学应用数学专业博士、
英国国家物理实验室高级科学家,主要研究领域为数学建模、工程优化以及科学、数值计算方法等。
:.
2ComputerEngineeringandApplications
聚类是通过对相似数据进行分类而获得有价中心。Chen[18]和Liu等人[19]基于一些数据点快速收
值的信息[1]。大部分聚类算法通过欧氏几何度量数敛到真实嵌入,引入了一种顺序缩减算法,从而使
据相似性[2-3],如常见的k-means通常用于进行快速早期停止策略加速分解。然而,这类方法由于
聚类,但它局限于凸分布的数据集,对于一些非凸k-means的局部收敛,若某一质心点聚类错误,则
数据集常常很难有效的描述。相比之下,谱聚类该质心点附近的点均同样聚类错误。
(SpectralClustering,SC)是一种基于图的聚类技术,本研究针对以上选取锚点算法的不足,提出一
能够有效利用数据的图和流形信息处理非凸形状种二分k-means锚点提取的快速谱聚类算法(Fast
的簇,与k-means相比,它能够处理更复杂的数据spectralclusteringalgorithmbasedonanchorpoint
结构。但由于求解特征向量时计算复杂度高而无法extractionwithbisectingk-means,FCAPBK)。利用二
直接处理大规模数据。因此,构建解决大规模数据分k-means从原始数据中选取一部分具有代表性的
的谱聚类算法成为研究的难点。锚点。通过锚点和数据点构造多层锚点图,然后利
近年来,许多基于锚点图的方法被提出来处理用原始数据点和最后一层锚点构造二部图,使多层
谱聚类的大规模数据集,如可扩展的半监督学****4-5]、
锚点图构成一个层次二部图,该方法既可以使选取
多视图大尺度光谱聚类[6]、大规模光谱聚类降维[7-9]、
[10]到的锚点具有代表性,也可以使谱聚类的复杂度大
以及基于二部图的谱聚类。与传统的图方法不同,
大降低。最后,对其相似图进行谱聚类分析,并在
基于锚图的方法根据锚点建立与原始数据点之间
[11]不同实验数据集上验证其最终聚类效果。
的邻接关系。Zhang等人首先建议使用一组锚点
来对数据流形进行有效的低秩近似,并给出一个信
[12]1相关工作
息损失最小的模型。Liu等人提出了锚点图模型,
[13]
并将其引入到基于图的学****任务中。Wang等人
设Xx,xx[,,]12n表示TndnR个样本的d
随后提出了一种改进的算法,显示了更好的性能和
维数据集矩阵,其中xiRd表示数据集X中的第i
计算效率。与传统的图相比,这些基于锚点图的方
个数据点,将每个数据点xi看作是亲和图上的一个
法可以大大降低图构造的复杂性。
[14]顶点,每个点和点之间的边表示邻接关系。对于n个
Fowlkes等人采用经典的Nyström方法加速
任意的点i和点j,w表示xi和x之间的边的权重,
了特征分解,并应用于谱聚类得到了处理大数据ijj
WwRnn表示亲和图的邻接矩阵。其中w以
ASC算法,该方法使用随机抽样,虽然简单快速,ijij
但其不确定性在很大程度上影响了聚类结果,且性高斯核函数表示如下:
能取决于样本集的质量。Li等人[15]利用随机低秩矩
||||xxij2222(1)
阵近似算法提出了一种可扩展的Nyström方法,对weKNNorKNN22,()()xxxx
ijijji
0,otherwise
从输入图中采样的列集的内子矩阵进行近似奇异
其中,||||xxij2222是xi和xj欧氏距离的平方,
值分解(SVD),进一步加快了该算法的分解速度。
是核参数,KNN()xi表示样本xi的k近邻集合。
但这类方法占用内存大,易丢失小簇且数值稳定性
[16]设L表示图拉普拉斯矩阵,其定义为:LDW。
不高。Shinnou和Sasaki将原始数据集被替换为
归一化后的图拉普拉斯矩阵为:
相对较少的数据集,并对较小数据集对应的邻接矩
[17]LDLDIDWD11112222(2)
阵进行后续操作。Yan等人提出了基于均值的近
式中D是一个对角矩阵,第i个对角线上元素
似光谱聚类(KASP)方法:该方法首先对集群数的数[20]
为。因此,归一化谱聚类的目标函数
据集执行k-means;然后,将传统的光谱聚类应用dwiijj
被定义为:
于个聚类中心,数据点被分配给集群作为其最近的
:.
ComputerEngineeringandApplications3
(3)一局限性,很多国内外学者都做了相关的研究。左
FFIminTrT()FLFT
进等[22]等通过计算数据点的紧密性值,选取不是异
其中,Tr为矩阵的迹,FRnc表示数据集
常值的初始聚类中心,使聚类效果在全局范围内是
的类指示矩阵。由于F的元素是离散值,因此,求
最佳的。Xia等[23]通过搜索邻居簇和将查询到的簇
解方程(3)是NP难题。为了使该问题得到解决,
划分为稳定的和活跃的区域来加速标准k-means算
通常将矩阵F从离散值松弛为连续值。通过对L的
法。Duan等[24]提出了一种基于大距离和高密度的
特征值分解,使其化为L的c个最小特征值对应的
中心点初始化方法。用距离加权平均的倒数表示样
特征向量,得到由特征向量组成的松弛连续解。然
本密度,选择距离较大、密度较高的数据样本作为
后,通过利用kmeans等聚类方法来计算离散解。
初始聚类中心。Ding等[25]提出了一种Yinyang
谱聚类步骤如下:
k-means算法。通过在初始阶段对中心进行聚类,
Step1:数据矩阵Xx,xx[,,]12n,生TndR
有效地保持数据点和中心点之间的上下界,避免了
成图的邻接矩阵W和对角矩阵D;
不必要的距离计算。有学者提出了二分k-means聚
Step2:归一化普拉斯矩阵LIDWD1122;
类算法,该算法减少了聚类相似度的计算量,从而
Step3:生成L的最小c个特征值及其对应的
能加快k-means执行速度。在选取聚类中心时进行
特征向量;
了优化,因此,能较好地克服对初始中心敏感的问
Step4:将c个特征值对应的特征向量通过
题,有着相对稳定的聚类性能。
kmeans聚类。[26]
二分k-means算法具体步骤:首先,将数据
-means选取锚点
[21]集的所有样本初始化为同一个簇,计算该簇数据集
近年来,在大规模数据集中基于锚点的方法
的质心;其次,使用k-means算法将该簇一分为二
有了广泛的应用,不仅在基于图的方法中降低了其
划分,以最小化聚类代价函数(误差平方和)为选
计算成本,且获得了良好的效果。
择依据,在所得到的簇中选择一个簇进行一分为二
基于锚点的方法是从原始数据点中选取
划分;不断重复以上步骤,直到选出给定的k个簇
m(m<<n)个代表原始数据结构的代表点,将其称为
为终止条件。
锚点。锚点的选取方式通常有两种:一种是从原始
算法1:基于二分k-means算法
数据中随机选取锚点,随机选取虽然快速、简单,
输入:数据集矩阵Xx,xx[,,]12n,聚类簇数Tk
但得到的锚点是随机的,不能很好体现原始数据的
输出:簇划分CCCC12,,...,k
结构;另一种是采用k-means选取,该方法使用
(1)将所有数据看作一个簇,计算簇中心(数
k-means得到原始数据的中心,使用得到的中心点作
据点的质心)
为锚点,该方法虽然得到锚点比随机选取有代表性,
(2)while簇中心个数hk时。
但由于k-means对数据输入顺序敏感而且仅考虑数
(3)forihdo1,.2,...,
据的空间局部信息,易选取过多的噪声成为锚点。
(4)使用k-means算法对第i个簇进行二分聚
针对这些问题,本文引入二分k-means算法来
类的划分。
选取锚点,不但对噪声鲁棒对数据输入顺序不敏感,
(5)计算划分后子簇的欧氏距离总和SSE。
而且通过每次选择误差和SSE最小的簇进行划分,
(6)比较第h次划分后的SSE,选择具有最小
在一定程度上能避免选取到噪声点。
总和SSE的划分方式。
-means
(7)更新簇的分配方式。
k-means是一种基于划分方法的聚类,然而传
(8)添加新的簇中心。
统k-means算法对噪声点和离群点很敏感。针对这
(9)untill簇中心个数达到k为止。
:.
Step1二分k-means
。。。
xxxxxx
x
4ComputerEngineeringandApplications
134567
2
。。。锚点
-means第i行稀疏向量,矩阵H为稀疏矩阵。其中
基于二分k-means算法从原始数据中得到聚类||||=()()xuxuxuijijij2222。正则化参数T
簇中心,将得到的簇中心作为锚点,再进行锚图的,由文献[27]得到的求
(2)(12)kddkhij
构造。相关步骤如图1:ikij,1,j1
解公式如下:
ddikij,1,。。。样本点
k(6),jk
hijkddikij,1,j1
0,jk

其中,k为近邻数据点的数量。hh
由以上计算表达式可以得到无核邻近分配[27]
方法的以下优势:Step2锚图构造
h
(1)上式中求解到的邻接矩阵是自然稀疏矩阵,6263
图1选取锚点和构造二部图的过程
而稀疏矩阵对于基于图学****任务的计算效率很高;
-
structingabipartitegraphs(2)通过表达式计算亲和度只涉及一个近邻参
61
数k,此参数是一个整数,易于调整,且表达式只
此图为选取锚点和构造锚图的过程,其中第一层
涉及基本的简单运算。而采用LLE和稀疏编码等方
黑色的数据点为原始数据点,第二层为用二分k-means
法计算亲和度,涉及到计算高斯函数和其他的参数;
选取得到的锚点集,第三四层为锚点和数据点的锚图
(3)数据点的亲和度具有伸缩不变性,不会因
构造过程。
为数据样本的扩大、缩小若干倍影响其度量尺度。

数据点间的距离特征与它们之间的亲和度也具有
设Uuu[,,]1mTmd表示生成的锚点R集,
一致性。
HRnm为数据点和锚点之间的邻接矩阵,矩阵Huuu
中的元素h表示第i个数据点与第j个锚点之间的
ij
邻接关系[12],计算方法为:
123
K(,)xu(4)
hjijiij,
sK(,)xuis
i
其中i1,...,m表示U中xi的k个最近锚点
的索引,K()表示一个核函数,通常采用高斯核图2锚点图的构造
,
Kexp(,)(||-||2)xuxuijij2
数需要人工选择合适的参数来得到良好的结果。
图2为锚点和数据点的锚点图构造过程。图中,
为了避免这种情况,此处采用一种无核邻近分配方
[27]h61、h62和h63是第6个数据点与第1、2、3个锚点
法构造基于锚点的相似图。邻接矩阵H中的h
ij的邻接关系(是数据点,、、是锚
xx17,...,u1u2u3
可通过解决如下问题求出:
点),且hhh6162631。
m(5)
hiijT1minhh1,0h||||xuijijij222222
j12层次二部图的谱聚类分析
上式中第一项为正则化项(锚点和原始数据点

之间平滑度);第二项是稀疏项,式中hiT表示H的[6]
在半监督学****中,设GXUE,,表示基于
:.
ComputerEngineeringandApplications5
锚点的层次图,其中XRnd为数据集矩阵,U为为:
锚点集,E为相邻层间边邻接矩阵的集合。假设原I00H
nH
始数据点用底层表示,其余的锚点层是由多个LT
XL00DbH0H(12)
锚点集组成的表示,其中I0I0nnIHIH-
ULaha(1,...,)UanHnH
LHDT11T
()的大小逐渐减小,即Hb22
UaRahmda,1,...,0D0D-HDHb
由归一化后的bb可知
,是中的锚点个数。LIDWD1122
mm1hmaLa1
2
,其中是nmmmL11,...,hhI-HDnHb
EHH0,11,,...,hhHaa1,Ra1
1
和La数据点之间的邻接矩阵。2T
-DHIbHm
在此引入无监督学****中的层次二部图[28],由文
(13)1
2
献[28]可知,层次二部图由原始数据层L0和最后一0HDHb
=I1
层构造。因此,二部图的邻接矩阵[12]可以写为2T
LhDH0
bH
(7)其中Im是mm阶单位矩阵。
W0HTH
H0H

其中,WR()()nmnmhh是邻接矩阵,0表示全0[28]
由经典谱聚类可知,基于层次二部图的谱聚
矩阵,HHRnmh表示原始数据点层L0到最后一层类的目标函数[29]定义为:
锚点Lh之间累积的邻接矩阵。接下来,(14)
FFIminTrT()FLFT
的方法计算从Lh到Lh1层间的邻接矩阵Hhh,-1,从而其中表示矩阵的迹,是单位矩阵,
Tr()I
得到邻接矩阵
Fx是所有数据点的类指标矩阵。由谱聚类
(8)FFG
HHHHhh0,11,...
设表示中锚点数据集的类指标矩阵,的相关求解知识可知,对L的特征值分解即为
FGLhFx
为中数据点的类指标矩阵。利用上述累积[6]邻接(14)的最优解,由归一化的L可得目标函数为:
L0
矩阵,可以得到从密集到稀疏的类指标矩阵[28],
L0Lh1
(0M15)0HD2
如下所示:minTr(())FIFTTHb
FFIminTrT(())FIF1T
TDH0bHT2
FHHFHF...(9)FFIM0
xhhGHG0,11,
接下来,通过邻接矩阵求得数据集的对角矩接下来,令MHDHb12,因此,目标函数(15)
W
可以写成如下:T0M
阵D为:
maxTr()FFT
FFIT
M0
D0a(10)
D0Db
T
其中,nn和mmhh是一个对角矩阵,FFxx0M
DaRDbR
maxTr()(16)T
Da的对角元素是H的行和,Db的对角元素是H的FFFFITT
xxGGFFGGM0
列和。对于HH中的向量,由行的归一化hiT11(1
T
是全为1的列向量)可知,DIan(In是nn阶单maxTr()FMFxG
FFFFITT
位矩阵)。故可以写为:xxGG
D
接下来,通过使用奇异值分解方法对M进行分
I0n(11)解,得到的松弛连续解,令为左奇异向
D0DbFURnn
因此,拉普拉斯矩阵LDW(D为对角矩阵)量矩阵、Rnmh为奇异值矩阵、VRmmhh为右奇
:.
6ComputerEngineeringandApplications
异向量矩阵。因此,矩阵M的SVD(奇异值分解)(5)对松弛离散解执行kmeans所需要的计算
可以写成如下:复杂度为Onmct()h,(其中t是迭代次数)。
MUVT(17)因此,FCAPBK的计算复杂度可以近似为
最后,通过kmeans聚类方法进行离散化处理,Onmdtdmct(((1)))1h。
计算出离散类指标Y。此外,总结了3种典型方法的时间复杂度:
算法2的过程如下所示:LLGC[30]、AGR[12]和[31]。从表1中观察到,
Nystrom
算法2:FCAPBK算法
输入:样本数据集XRnd,类簇数,每一层锚LLGC在图的正则化中具有三次方的时间复杂度,
c
数m1,m2,...,mh,近邻数k。当数据集规模很大时,计算会相当地耗时;
Nystrom
输出:c个类簇的标签。
也面临二次方的计算复杂度;AGR在图构造中的复

(6)得到相邻层邻接矩阵杂性与数据大小呈线性关系,但当要达到合理精度
HH011,,,...,hh所需锚点足够密集时,面临的计算成本显著增加。
(8)得到矩阵HH然而,本文由于采用层次锚点的方法,使得最密集
HHHHhh0,11,...锚点的规模比较小。因此,本文方法的计算成本降
(7)计算多层二部图的邻接矩阵
低了很多,并且能够处理大规模数据集。
0HH
WH0HT表1四种方法的时间复杂度比较
12进行奇异值分解,Table1Comparisonofthetimecomplexityofthefour
MHDHb
methods
得到Fx和FG的松弛连续解
算法复杂度
聚类方法获得最终c类指标LLGC
Odnnn(log)3
YAGR
Odnmknmmnmc(log)11113

NystromOnmknmdm()23
给定n个样本数据集XRnd,类簇数c,LFCAPBK
1Onmdtdmct(((1)))1h
到Lh层中的锚点数mm1,...,h,FCAPBK的计算复杂
度由以下5个部分组成:(n为样本点数、d为样本的维度、m为标记
(1)通过从层到层的二分选择的样本点数、c为类簇数、t为迭代次数、h为锚层
L1Lhkmeans
得到m个锚点的计算复杂度为数)
Onmdtmmdtmmdt(...)1121,由于nmm1hh,h
3
因此可近似为Onmdt()1。

(2)从H0,1到Hhh,-1的矩阵需要的计算复杂度
为。由于,
Odnmmm((...))11hhnmm1h
计算复杂度可以近似为Omnd()1。以下给出一个合成数据集的实例来分析和验
(3)由于nmm1,h故HH的计算复杂度证本文方法的效果。
可以近似为Onmm()1h。
(4)通过对矩阵M进行SVD,得到F的松弛连
续解的计算复杂度Onmc()h。
:.
ComputerEngineeringandApplications7
由图3可以看出:图3(a)为由四个类的人工合
成数据集组成的初始数据,有243个数据点和四类
样本。图3(b)为采用二分k-means方法选择得到的
16个锚点数据图,其中红色五角星代表从数据中选
择的锚点,显然,采用二分k-means方法得到的锚
点能大致的代表原始数据图的结构,类内的选择和
类之间的选择也大体一致。图3(c)显示了该数据集
(a)人工合成数据集的原始图
(a)Theoriginalplotofthesyntheticdatasets中对c个类簇的选择结果和最终的聚