半监督谱聚类特征向量选择算法.docx
- 文档编号:17666178
- 上传时间:2023-07-27
- 格式:DOCX
- 页数:38
- 大小:42.20KB
半监督谱聚类特征向量选择算法.docx
《半监督谱聚类特征向量选择算法.docx》由会员分享,可在线阅读,更多相关《半监督谱聚类特征向量选择算法.docx(38页珍藏版)》请在冰点文库上搜索。
半监督谱聚类特征向量选择算法
第24卷第l期
2011年2月
模式识别与人工智能
PR&AI
V01.24Feb
No.1201l
半监督谱聚类特征向量选择算法木
赵凤
焦李成
刘汉强
公茂果
(西安电子科技大学智能感知与图像理解教育部重点实验室西安710071)
摘要对于一个K类问题,Ng.Jordan.Weiss(NJW)谱聚类算法通常采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量作为数据的一种表示.然而,对于某些模式识别问题,这K个特征向量不一定能够体现原始数据的结构.文中提出一种半监督谱聚类特征向量选择算法.该算法利用一定量的监督信息寻找能够体现数据结构的特征向量组合,进而获得优于传统谱聚类算法的聚类性能.UCI标准数据集和MNIST手写体数据集上的仿真实验验证该算法的有效性和鲁棒性.
关键词谱聚类,特征向量选择,半监督学习,免疫克隆选择中图法分类号TP
181
Semi-SupervisedEigenvectorSelectionforSpectralClustering
ZHAOFeng,JIAOLi—Cheng,LIU
Han-Qiang,GONG
Mao—Guo
Education
(Key
Laboratory
ofIntelligentPerceptionandImageUnderstandingofMinistryof
of
China,
XidianUniversity,Xi"an710071)
ABSTRACT
For
a
Kclustering
problem,Ng-Jordan・Weiss(NJW)spectral
to
clustering
method
adopts
the
a
eigenvectorscorresponding
theKlargesteigenvaluesofthenormalizedaffinitymatrixderivedfrom
can
dataset
the
asa
novelrepresentationoftheoriginaldata.However,theseKeigenveetors
not
alwaysreflect
structure
oftheoriginaldataforsomepatternrecognitionproblems.Inthispaper,asemi—supervised
utilizessome
amount
eigenvectorselectionmethodforspectralclusteringisproposed.Thismethodsupervisedinformation
to
of
searchtheeigenvectorcombinationwhich
more
can
reflectthestructureofthe
original
data,andthenobtainsExperimentalresults
on
satisfying
performance
than
theclassicalspectralclusteringalgorithms.
UCIbenchmarkdatasetsandMNISThandwritten
digits
datasetsshowthatthe
proposedmethod
Key
iseffectiveandrobust.
Words
Spectral
Selection
Clustering,EigenvectorSelection,Semi—SupervisedLearning,ImmuneClone
奉国家973计划项目(No.2006CB705707)、国家863计划项目(No.2008AAOIZl25,2009AAl22210)、国家自然科学基金项目(No.60702062,60970067)、教育部重点项目(No.108115)和高等学校学科创新引智计划项目(1ll计划)(No.1307048)资助收稿门期:
2009—10—19;修心口期:
2010—04—20
作者简介赵凤,女,1980年生,博士研究生,主要研究方向为机器学习、模糊信息处理和图像处理.E.mail:
fengzlll9@sina.corn.焦李成,男,1959年生,教授.博士牛导师,主要研究方向为自然计算、信号和图像处理、智能信息处理等.刘汉强,男,1981年生,博上研究生,主要研究方向为模式识别、机器学习和图像处理.公茂果,男,1979年生,教授,博士生导师,主要研究方向为计算智能、数据挖掘、模式识别和图像处理.E—mail:
gong@ieee.org.
万方数据
1期赵凤等:
半监督谱聚类特征向量选择算法
49
1
引言
谱聚类是一种基于两点间相似关系的聚类方法….该类算法利用数据的规范化亲和度矩阵的特征向量进行聚类,获得图谱划分准则在放松的连续域中的全局最优解.与其它聚类方法相比,谱聚类算法最大的优势是具有识别非高斯分布的能力,非常适合于许多实际问题,已成功应用到并行计算旧J,超大规模集成电路(Very
LargeScale
IntegratedCir-
cuits,VLSI)设计∞j,文本挖掘H。
J,生物信息挖掘∞1和图像分割"1等方面.比较经典的谱聚类算法有2000年Shi和Malik07j提出的sM算法和2002年Ng等旧1提出的k-way划分的Ng—Jordan—Weiss算法(简称为NJW算法).此外,为解决谱聚类不适用于大规模数据的问题,2004年Fowlkes等一1提出使用NystrtJm逼近方法减少求解特征值和特征向量的计算复杂度.为利用样本先验信息来改善谱聚类算法的聚类性能,2007年王玲等。
m’通过设计一种基于密度敏感的距离测度并结合成对限制信息,提出一种密度敏感的半监督谱聚类算法(Density—Sensitive
Semi—SupervisedSpectral
Clustering,DS—SSC).对于
一个K类问题,NJW算法通常采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量作为数据的一个表示.本文在NJW算法的基础上,希望利用一定量的监督信息指导谱聚类的特征向量选择,进而提高谱聚类的算法性能.
Sun等…1提出对主分量分析(PCA)提取的特征进行选择,即不再使用特征值较大的几个特征向量,而是采用遗传算法(GA)搜索PCA空间,找到能够反映目标概念信息的特征向量子集作为主成分方向.随后,u等¨2。
提出采用GA对分别利用PCA和偏最小二乘(Paaial
Least
Square,PLS)方法获得的
特征进行联合选择的方法.最近有文献指出,谱聚类算法的特征向量也是需要选择的u引,对于特征向量而言,并不是特征值越大,对于分类的信息量也越大,而且每个特征向量对于分类的信息量也是不同的.在文献[13]中,作者首先定义一个相关性度量,用于衡量每个候选特征向量为分类提供的信息量,然后采用所有相关性度量值大于0.5的特征向量(称之为相关的特征向量)组成最终的特征向量组合.众所周知,由单个最优的特征组成的特征组合不一定是最优的特征组合.同样地,每个相关的特征向量可为分类提供信息,但是所有相关的特征向量不一定是一个好的特征向量组合,即它不一定能体现原始数据的结构,进而无法保证获得好的聚类性能.
万方数据
在实际应用中,我们有时可从数据中获得一定量的监督信息.本文利用这些监督信息,提出一种半监督谱聚类特征向量选择算法(Semi-Supervised
Eigenvector
Selection
for
Spectral
Clustering,SES—
SC).我们首先利用监督信息定义一个衡量特征向量组合好坏的度量准则,并把它作为适应度函数.然后采用某种优化算法来确定最优的特征向量组合.本文采用的优化算法是免疫克隆选择算法.免疫克隆选择算法【14o是模拟自然免疫系统功能的一种优化方法,它具有学习、记忆、抗体多样性等性能.由于其较强的全局搜索能力,将免疫克隆选择算法应用于谱聚类特征向量选择有可能是一个好的选择.我们在UCI标准数据集和MNIST手写体数据集上进行仿真实验,证明本文算法可有效选择对于分类具有较大信息量的特征向量组合,获得优于传统谱聚类算法的聚类性能.
2
谱聚类特征向量选择的必要性
设X={石,,戈:
,…,z。
}表示一个数据集合.谱聚
类算法对数据集x进行聚类之前,需要构造亲和度矩阵,该矩阵中每个元素表示的是两两数据点之间相似性.在谱聚类算法中,一般采用高斯函数构造亲和度矩阵.需要指出的是,谱聚类算法的性能对于高斯函数尺度参数的取值非常敏感.为消除尺度参数对于谱聚类结果的影响,使得谱聚类算法的性能只受特征向量选择的影响,我们计算每个数据点的局部尺度参数¨纠来代替固定的尺度参数,数据点名i和巧之间的相似性:
s。
…p(-等).
(1)
对于数据点菇i,将ar(xi,龙i,)作为戈i的尺度参数ori,其中,石i,是zi的第z个邻接点,同理可得盯,.在本文中,参数z设置为7.值得指出的是,对于小规模的数据集,可利用式(1)构造全连接的亲和度矩阵,即任意两个数据点之间都建立相似性关系.对于大规模的数据集,全连接的亲和度矩阵的存储代价是巨大的.在本文中,对于大规模的数据集,我们采用式(1)构造后.邻接的亲和度矩阵,即每个数据点仅与它的k个最近邻之间建立相似性关系.在本文中,参数k设置为lO.
NJW算法哺1直接采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量作为数据的一个表示,然后采用I|}.均值聚类算法对其进行聚类.实际
模式识别与人工智能
24卷
上,对于谱聚类算法来说,特征向量的选择是十分必要的¨3|.图1(a1)和(a2)给出2个具有不同流形结构的人工数据集,下面以这2个数据集为例指出谱聚类特征向量选择的必要性.对于Three—circle数据,NJW算法采用特征向量1,2和3可获得完全正确的聚类结果.这是因为数据在这3个特征向量上的映射是可分的(见图l(b1)).实际上,对于这个数据而言,只需采用特征向量2就可获得数据的正确划分,如图l(c1)所示.对于Two.moon数据,NJW算法采用特征向量1和2,由于数据在这两个特征向量上的映射是不可分的(见图1(b2)),因此该算法得不到正确的聚类结果.需要指出的是,Two-moon数据在特征向量2,4上的映射是可分的,如图l(c2)所示,采用这个特征向量组合可获得完全正确的数据划分.综上所述,我
们认为NJW算法直接采用数据规范化亲和度矩阵的前K个最大特征值对应的特征向量在某些情况下是不适用的,谱聚类的特征向量是需要进行选择的.
3
3.1
半监督谱聚类特征向量选择算法
特征向量组合的评价准则
谱聚类算法的特征向量选择需要一个定量的准
则来衡量所选特征向量组合对于聚类的有效性.在实际的模式识别问题中,我们有时可从数据集中获得一定量的监督信息.利用监督信息来指导特征向量选择应该是一个好的选择.在本文中,我们把少量具有真实标签的数据点作为监督信息,这部分数据点组成的集合称之为训练集.这里,我们给出特征向量组合的评价函数:
以ai)=Al・accuracyt。
i。
(ai)+A2。
len。
。
i。
(ai),
(2)
始聋媒抵
爆姑姆r猴
其中,ai表示一个特征向量组合,accuracy㈣。
(ai)表示训练集在这个特征向量组合下的聚类准确率,
第一维特征
第一维特征
len—i。
(ai)=Km—length(ai)表示没有被选择的
特征向量的数目,Km表示初始选择的特征向量数目,即最多可选择的特征向量数目,length(ai)表示特征向量组合ai中的特征向量的数目.A。
和A:
是调节聚类准确率和特征向量数目在评价函数中作用的权重参数,在实验中,A。
和A:
分别取值为104和100/Km.accuracy“。
(ai)的取值范围是0—1之间,因此式(2)中的第一项的变化范围是0—10000.由于特征向量组合中至少要包含一个特征向量,len。
。
i。
(ai)这一项的变化范围是0~Km一1,使得式(2)中的第二项的取值小于等于100.这样设置A。
和A:
使得accuracyⅢ。
(ai)在这个评价函数中占据主导作用,如果多个特征向量组合下的训练集的聚类准确率相差不多时,选择那些特征向量数目较少的特征向量组合.
3.2
(a1)Three—circle(a2)Two・moon
∞
1.00
删o.05
囊-o是
-1.00
O
(b1)Three.circle的特征
向量1,2,3
(b1)Eigenvectors(b2)Eigenvectors
(b2)Two・moon的特征
向量1,2
1,2,3ofThree-circle1,2ofTwo—moon
基于免疫克隆的特征向量选择
我们采用免疫克隆优化算法为谱聚类选择最优
的特征向量组合,具体介绍如下.
3.2.1
二进制编码
-0.10加.05
数据点数目
00.050.100.15
特征向量2
给定数据集X={z,,戈:
,…,石。
f,聚类数为尼我们把数据集彳的规范化亲和度矩阵的前Km(Km>K)个最大特征值对应的特征向量组成的矩阵记为
(c1)Three—circle的特征向量2(c2)Two—moon的特征向量2,4
(c1)Eigenvector2ofThree—circle
‰={l,1,l,2,…,l,踟}.来自于数据集X的监督信息
构成的训练集记为
XS={%尥,…以},l≤s<n,l≤少≤n,1≤r≤s,它们的真实标签记为
(c2)Eigenvectors
图I
Fig.1
2,4ofTwo—moon
Three.circle和Two—moon的特征向量组合
EigenvectorcombinationsofThree-circleandTwo-moon
万方数据
1期赵凤等:
半监督谱聚类特征向量选择算法
LS=%,乞,…,毛},知∈{l,2,…,K},
这个训练集在‰中的对应部分记为%,其中,%
的每一列对应一个特征向量.这里,每个抗体表示一
个特征向量组合,搜索空间为吃的列的子集.由于
每个基因位对应的模式只存在两种可能,我们采用二进制编码,编码长度为Km(即一个特征向量对应一个基因).如果某基因位的值是1,那么该特征向量被选中,如果值是0,则该特征向量被忽略.
3.2.2
适应度函数
设抗体种群为A={a.,a2,…,a。
},ai(1≤i≤m)表示一个特征向量组合.我们将式(2)作为免疫克隆选择算法的适应度函数.谱聚类特征向量选择的目标就是寻找到一个可获得满意聚类结果的特征向量组合,这个适应度函数能够在充分保证训练集取得较高的聚类准确率的同时,尽量采用较少的特征向量.
3.2.3
克隆、变异、选择算子设计
克隆操作.在本文算法中,对于抗体种群A(k)={a,(k),a:
(k),…,a。
(k)}
中的每个抗体ai(k)来说,经过克隆操作后形成的
克隆子种群为{a:
(k),a;(k),…,口r(k)},其中的
每个抗体与抗体口i(k)具有完全相同的属性,聊为克隆比例.经过克隆操作后的种群为
A
7(k)={《(k)},i=1,2,…,m;J=1,2,…,凡c.变异操作.由于本文算法采用二进制编码方法,
因此,变异操作定义为抗体的每一基因位以概率《(k)经过变异操作后的抗体用彰(k)表示.经过变异操作后的种群为
A”(七)={6《(k)},i=1,2,…,m;歹=1,2,…,nC.
克隆选择操作.该操作是指从抗体经过克隆和变异后的子代中按照适应度函数的大小选择出优秀的个体,形成新的种群
A(k+1)={a1(k+1),a2(k+1),…,a。
(k+1)},
其中,ai(k+1)是口i(k)和{b;(k),b;(k),…,
6,(k)}中适应度最高的个体,i=1,2,…,m.
3.3
算法实现
下面给出半监督谱聚类特征向量选择算法
(SESSC)的详细步骤.
stepl
对于数据集X=‰,算:
,…,并。
},按照
式(1)计算亲和度矩阵S并得到其对应的规范化亲和度矩阵L,将£的前Km(Km>K)个最大特征值对应的特征向量组成矩阵y舯
step2
假设来自于数据集|jf的监督信息构成
的训练集为邪,在‰中取出训练集的对应部分,
万方数据
记为y:
。
.
step
3
免疫克隆算法初始化.设置免疫克隆
算法的初始参数;产生初始种群A(0)={a,(0),a:
(0),…,a。
(0)},其中,oj(0)是一个特征向量组合,表示y幺的对应列被选择;设置当前迭代次数k
step
4
初始种群抗体的适应度值计算.对于
每个抗体,首先取出其在yk。
中的对应列构成矩阵y’,归一化y的行向量得到矩阵z’.其次将z’的每一行看成一个数据点,使用后一调和均值聚类算法¨6]将其聚为K类,将获得的聚类准确率记为accuracy。
商。
.然后将抗体中基因位为0的基因的数目记为len。
。
舻最后按照式(2)计算抗体的适应度值.
step
5
停机判断.判断是否满足终止条件,即
是否完成设定的迭代次数,若完成迭代次数,则终止迭代,确定由当前较优个体构成的种群为最优种群,转向step1l,否则执行step
6.
step
6
克隆操作.对当前的第k代父代种群A(k)进行克隆,得到A’(蠡).
step
7
变异操作.对A’(k)进行变异,得到A”(后).
step
8
A”(k)中抗体的适应度值的计算.按照step
4中的操作计算A”(k)中抗体的适应度值.
step9
克隆选择操作.对抗体群A(k)和A”(k)进行选择,得到新的抗体种群A(k+1).
step10
k=k+l,转向step
5.
step
l1
寻找最优特征向量组合.在最优种群
中寻找适应度值最大的个体,把它作为最优特征向量组合.
step
12
将最优特征向量组合中出现的特征向量构成矩阵V
step
13
归一化y的行向量,得到矩阵z,即
弘南‘
step14将z的每一行看成新的数据空间中的
一个点,使用后.调和均值聚类算法ll钊将其聚为K类,最终得到数据x的划分.3.4算法复杂性分析
本文算法的复杂度主要由两部分构成:
特征向量的获取,特征向量的选择.获得Km个特征向量的复杂度是0(Km・n2),其中凡为数据集x的数据个数.进行特征向量选择的复杂度由免疫克隆算法的复杂度决定.不失一般性,假设免疫克隆选择算法的最大迭代次数为Go,种群规模为m,克隆比例为nC.免疫克隆选择算法初始化的时间复杂度为0(m).
pm(O<pm<1)进行取反操作.种群中的抗体
52
模式识别与人工智能
24卷
在每一代运行中,克隆操作的时间复杂度为O(m・rtc);变异操作的时间复杂度为0(m・眦).克隆选择操作主要包括适应度函数的计算以及适应度函数值的排序,适应度函数计算的时间复杂度为0(m・lzc),排序算法的时间复杂度最差为0((m・lie)2).因此,进行特征向量选择的复杂度为
O(m)+O(C,a・(m・nc+,n・nc+,n・船+(m・,圮)2)).所以,本文算法的复杂度为
0(Km・n2+G口・(m・/zc)2+3.G口.(m.nc)+,n).4
较方法,该算法利用式(1)构造亲和度矩阵,采用k-i靖l和均值聚类算法代替I|}一均值算法进行后续聚类.实际上,对于本文算法来说,10%的有标签数据仅用来指导特征向量选择,并没有用来指导数据的聚类.然而,鉴于NJW算法是一种无监督的算法,为与它进行更加公平的比较,我们为NJW算法设计一个新的聚类准确率度量.当NJw算法获得的数据标签是C={cI,c2,…,c。
},Ci∈{1,2,…,K},1≤i≤厅,我们使用
实验比较与结果分析
实验设置
为验证本文SESSC算法的有效性,我们采用
“¨∞,三=
来修改标签c并计算相应的聚类准确率,记为accuracy_1.值得指出的是,如果采用的训练集不同,本文算法选出的特征向量也会不同.所以,对于每个数据集,本文算法进行10次独立实验,10次实验取得的最小、最大和平均聚类准确率分别记为accuracy_min、accuracy_max和accuracy_ave.当然,由于训练集的不同,accuracy_l的值也会有一些差别,我们计算10次的平均值作为accuracyj的最终取值.
此外,我们在4.4节考察监督数据规模对于SESSC性能的影响.在4.5节部分,我们给出SESSC和NJW两个算法的鲁棒性分析.在4.6节部分,我们提出SESSC的一个提高版本,进一步提高SESSC的性能,并与支持向量机算法㈣3和密度敏感半监督谱聚类算法(DS_SSC)¨叫进行比较.
4.2
4.1
UCI标准数据集‘”1和MNIST手写体数据集【183进行仿真实验,分别呈现在4.2节和4.3节部分.在实验中,对于每个数据集,我们抽取10%的有标签数据作为监督信息,构成训练集
XS={并d,髫皿,…,戈p},
s=I
n/lO
l,1≤jr≤n,1≤r≤s,
它们的真实标签为
LS={fJl,如,…,k},0∈{1,2,…,K}.
实验中免疫克隆优化算法的最大迭代次数锄设置
为200,种群规模m为7,克隆比例rtc为6,变异概率pm为0.1.k一调和均值聚类算法¨钊的最大迭代次数设置为500.初始选择的特征向量数目Km=20.本文采用聚类准确率¨到来定量评价算法性能,其定义如下:
’
UCI标准数据集上的实验
本节我们采用4个UCI标准数据集作为实验数
,,=
n
..’.
(3)
IjJ
据,由于每个数据集的数据个数都少于1000,我们构造全连接的亲和度矩阵.实验结果如表1所示.
对于Iris数据来说,NJW方法采用特征向量1,2和3,数据在其上的映射如图2(a)所示.本文算法在10次实验中有5次选择出特征向量2,3这个组合,数据在此特征向量组合上的映射如图3(a)所示,获得的聚类准确率为0.94.其余5次实验选出的特征向量组合各不相同,但都包含特征向量2和3(见图3(b)、(c)),表明这2个特征向量具有较大
其中,n为数据的数目,己和C分别表示数据的真实标签和算法获得的聚类结果.Num(A,B)表示真实划分A和算法获得的划分B中相同的数据点个数.map(・)是把聚类标签转换成类别标签的置换函数,我们使用Num(L,map(C))的最大值来计算聚类准确率.
在4.2节和4.3节中,我们采用NJW算法作为比
表1
仉Iblel
2种算法在UCI标准数据集上的性能对比
On
。
…一数据集
Iris
样本数维数
15017835l683
413349
………。
。
类数‘磊品i芳荔i二面‘磊磊鬲j磊万Fi=磊鬲j磊孑万—乏瓦乏ij万
¨,。
,
Performancecomparisonbetweem2algorithms
UCIbenchmarkdatasets
SESSC
NJW
口ccHrnc,/‘幻occ“九∞’,l/‘幻
92.6796.6373.2271.89
93.8096.9776.0774.69
∞curt阳VmI,∥%口cc比rⅡc’,,rmj∥%口ccHr口c’,n口e/%
79.3395.5l85.7594.00
94.0097.1994.3097.07
91.1996.0090.1296.24
3322
Wine
IonosphereBreast-w
万方数据
1期
赵凤等:
半监督谱聚类特征向量选择算法
53
的分类信息量.实际上,本文算法仅在一次实验中取得的特征向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 监督 谱聚类 特征向量 选择 算法