半监督线性维数约减算法

半监督线性维数约减算法

1半监督维数约减方法在模式识别和机械学习领域，一些应用程序，如人脸识别、图像搜索和网络挖掘，往往会导致高维数据。为了解决这个问题，自然地考虑找到一个低维流形式来表示这些高维数据。在此基础上，维数约减法可以将高维数据投影到低维空间。此外，通过减小维数约法减少数据维数，排序和距离算法的执行变得更加快速和直观。因此，近年来，维数约减吸引了越来越多研究人员的兴趣。基于可获得的约束信息,现有的维数约减方法可分为三类:监督维数约减方法,半监督维数约减方法和无监督维数约减方法.通常,无监督维数约减方法寻找高维数据的低维流形时,由于缺乏先验信息的引导,很难得到令人满意的投影结果;监督维数约减方法需要大量有类标号的数据作为训练样本,能得到较为满意的结果.然而,这类方法难以推广到实际应用中,因为所需的数据类标号并不容易得到.半监督维数约减方法是借助于一部分辅助信息和无标号样本来寻找高维数据的低维流行.该方法既能提高无监督维数约减方法的性能,也无需大量的类标号.所以,半监督维数约减方法已成最近研究的一个重要方向.最近,Sandler等人指出基于谱图理论的方法需要计算近邻样本之间的距离,而这类距离一般难以正确地计算.他的方法将权向量的特征结构作为正则化项引入到分类目标函数中来求解分类方向.事实上,Sandler的方法忽略了数据的内在几何结构对求解分类方向的作用,而且,他的方法需要大量数据的类标号作为训练样本.为了克服上述问题,本文提出新颖的半监督正则化学习算法(SSRL).新算法的重要思想就是通过对成对约束和大量无标号样本的学习,得到一个光滑和有判别力的子空间.具体地说,分别使用成对约束信息和大量无标号样本得到数据的判别结构和内在几何结构,并通过正则化技术合并投影向量的特征结构到半监督维数约减算法中求解最优投影方向.辅助信息有多种形式,如类标号信息,成对约束等.相比数据的类标号,得到成对约束更容易.因为对一个专家或者用户来说,指出两个样本是否属于相同类要相对容易.而且由数据类标号能得到成对约束,但不能由成对约束来得到数据的类标号.成对约束有must-link约束和cannot-link约束两种形式,它们定义如下:一个must-link约束规定:两个样本属于相同类;一个cannot-link约束规定:两个样本属于不同类.2线性维数约减方法给定一个由n个样本组成的数据集X,{x1,…,xn}∈Rd,线性维数约减方法需要找到一个变换矩阵A=(a1,…,ar)∈Rd×r,将n个样本投影到低维空间里:2.1做st+sl的amoaaatsbaatCai等人将线性判别分析算法引入半监督领域中,提出一种半监督判别分析算法(SDA).SDA的目标函数是:maxaaΤSbaaΤ(St+λSl)amaxaaTSbaaT(St+λSl)a(2)其中,Sl定义如下:Sl=12n2n∑i,j=1Sij(xi-xj)(xi-xj)ΤSl=12n2∑i,j=1nSij(xi−xj)(xi−xj)T(3)Sij度量两个样本xi和xj之间的相似性,Sb是给定一部分有标号样本的类间散布矩阵.由于缺乏大量样本的类标号,难以准确计算类内散布矩阵Sw.因此,Cai使用St=Sb+Sw代替Sw.2.2ssr目标函数Zhang等人提出了一种半监督维数约减算法(SSDR).不同于SDA使用一部分样本类标号作为先验知识,对给定的must-link约束集合和cannot-link约束集合,Zhang使用成对约束来引导维数约减过程.SSDR最大化下面目标函数:J(a)=12n2n∑i,j=1(aΤxi-aΤxj)2+α2nc∑(xi,xj)∈C(aΤxi-aΤxj)2-β2nm∑(xi,xj)∈Μ(aΤxi-aΤxj)2(4)J(a)=12n2∑i,j=1n(aTxi−aTxj)2+α2nc∑(xi,xj)∈C(aTxi−aTxj)2−β2nm∑(xi,xj)∈M(aTxi−aTxj)2(4)其中,M和C分别表示must-link约束和cannot-link约束集合,α和β是折中参数.式(4)实际上就是约束的主成份分析(PCA),或者是半监督的主成份分析.该方法忽略了数据的局部几何结构.2.3基于球形k-均值算法的样本聚类方法相似于Zhang等人的方法,Tang等人借助于成对约束,提出基于球形K-均值的特征投影方法(SCREEN).SCREEN最大化下面的目标函数:J(A)=∑(xi,xj)∈C∥AΤxi-AΤxj∥2-∑(xi,xj)∈Μ∥AΤxi-AΤxj∥2(5)J(A)=∑(xi,xj)∈C∥ATxi−ATxj∥2−∑(xi,xj)∈M∥ATxi−ATxj∥2(5)s.t.aΤiaj={1ifi=j0ifi≠jaTiaj={1ifi=j0ifi≠j(6)在求出投影矩阵A后,SCREEN使用基于球形K-均值算法对所有样本聚类.该方法仅仅使用成对约束来寻找高维数据的低维流形.显然,SCREEN的缺点是不仅忽略大量无标号样本对维数约减的贡献,也没有考虑到数据的局部几何结构.因此,Tang得到的解并不是最优的投影方向.2.4traaSong等人利用部分类标号,提出一个半监督维数约减框架.在这个框架里他们分别优化两个目标函数.他们优化的第一个目标函数是:A=argmaxtr(AΤSbA)tr(AΤ(Sw+λ1Sl+λ2Ι)A)A=argmaxtr(ATSbA)tr(AT(Sw+λ1Sl+λ2I)A)(7)不难发现,式(7)实质上就是在SDA方法基础上添加了一项Tikhonov正则化.Song等人优化的第二个目标函数是:A=argmaxAΤA=Ιtr(AΤ(Sb-λ1Sw-λ2Sl)A)A=argmaxATA=Itr(AT(Sb−λ1Sw−λ2Sl)A)(8)其中,tr(B)是求解矩阵B的迹.显然,式(8)是半监督化的最大间隔标准(MMC).3半监督正则化学习算法大多数半监督维数约减方法使用数据的局部几何结构来寻找投影空间.文中提出的半监督正则化学习算法(SSRL)不仅保持了数据的局部几何结构,还使用投影矩阵的特征结构作为正则化项合并到目标函数中,从而得到最优的嵌入空间.3.1目标函数的建立对所求的投影向量a,构建一个无向图G1=(V,E,P),顶点V={1,…,d}对应于投影向量的每个特征,每条边对应于一个权值Pij,用来度量两个顶点i和j的相似性(P的求解见第四节实验部分).显然,权值是一个非负实数,而且权值越大,意味着相应的顶点有更大的相似性.如果权值为0意味着这两个顶点没有相似性.类似于,优化下面的目标函数:minJ(a)=d∑j=1(aj-∑kΡjkak)2minJ(a)=∑j=1d(aj−∑kPjkak)2(9)s.t.∑kΡjk=1s.t.∑kPjk=1(10)将式(9)写成矩阵形式:J(a)=aTHa(11)其中,H=(I-P)T(I-P).3.2局部几何结构给定样本集合X,构建一个p近邻无向图G2来建模近邻样本之间的关系.详细地说,如果图中两个顶点xi和xj互为近邻,那么它们之间就存在一条边,相应的权值矩阵为S,其定义如下:Sij={1ifxi∈Νp(xj)orxj∈Νp(xi)0otherwise(12)Sij={1ifxi∈Np(xj)orxj∈Np(xi)0otherwise(12)其中,Np(xi)表示样本xi的p近邻集合.根据上述定义,如果两个样本之间存在一条边,那么这两个样本有可能属于相同类.因此,高维空间中的两个近邻样本被投影到低维流形时,自然地期望这两个仍保持近邻.为了达到这个目的,最小化下面目标函数:h(a)=n∑i,j=1(aΤxi-aΤxj)2Sijh(a)=∑i,j=1n(aTxi−aTxj)2Sij(13)最小化上述目标函数,在得到低维流形的同时,保持了数据的局部几何结构.设X=[x1,x2,…,xn],则h(a)=n∑i,j=1(aΤxi-aΤxj)2Sij=2n∑i=1aΤxiDiixΤia-2n∑i,j=1aΤxiSijxΤja=2aΤXDXΤa-2aΤXSXΤa(14)h(a)=∑i,j=1n(aTxi−aTxj)2Sij=2∑i=1naTxiDiixTia−2∑i,j=1naTxiSijxTja=2aTXDXTa−2aTXSXTa(14)其中,矩阵S是对称阵,矩阵D是对角阵,且Dii=∑jSijDii=∑jSij.若aTXDXTa的值被固定,最小化h(a)等价于最大化aTXSXTa.3.3优化目标函数给定must-link和cannot-link成对约束集合M和C,文中的目标就是让属于M集合的样本对在投影空间中的距离尽可能的近,属于C集合的样本对在投影空间中的距离尽可能的远.为此,通过下面式子计算给定的must-link成对约束之间的距离.dw=∑(xi,xj)∈Μ(aΤxi-aΤxj)2=aΤSwadw=∑(xi,xj)∈M(aTxi−aTxj)2=aTSwa(15)其中,Sw被称为must-link约束散布矩阵,其表达式为:Sw=∑(xi,xj)∈Μ(xi-xj)(xi-xj)ΤSw=∑(xi,xj)∈M(xi−xj)(xi−xj)T(16)类似地,可以计算cannot-link成对约束之间的距离:db=∑(xi,xj)∈C(aΤxi-aΤxj)2=aΤSbadb=∑(xi,xj)∈C(aTxi−aTxj)2=aTSba(17)Sb被称为cannot-link约束散布矩阵:Sb=∑(xi,xj)∈C(xi-xj)(xi-xj)ΤSb=∑(xi,xj)∈C(xi−xj)(xi−xj)T(18)为了达到最大化cannot-link成对约束之间的距离,而最小化must-link成对约束之间的距离,优化下面的目标函数:maxaΤSbaaΤSwamaxaTSbaaTSwa(19)3.4半监督维数约减目标函数和半监督维数约减目标函数显然,式(19)只是利用了给定的成对约束信息来求解投影向量.因此,最大化(19),得到的结果并非最优的投影向量.为了得到最优的投影向量,不仅要使用成对约束信息和数据的局部几何结构,还要考虑到投影向量的特征结构.事实上,在现有的半监督和无监督维数约减领域中,大多数算法在求解投影向量时都忽略了它的特征结构.SSRL的目的就是将投影向量的特征结构和数据的局部几何结构作为正则化项添加到半监督维数约减目标函数中,得到最优的投影向量.根据上述分析,SSRL的目标函数是:maxaΤ(Sb+λ1XSXΤ)aaΤ(Sw+λ2Η+λ3XDXΤ)amaxaT(Sb+λ1XSXT)aaT(Sw+λ2H+λ3XDXT)a(20)其中,λ1,λ2和λ3是正则化系数.最大化这个目标函数,最优的投影向量是由求解下面式子的广义特征值问题得到:(Sb+λ1XSXT)a=η(Sw+λ2H+λ3XDXT)a(21)式(21)前r个最大特征值对应的特征向量,构成所求的投影矩阵A=(a1,…,ar).综上分析,SSRL算法描述如下:输入:样本集X,成对约束集合M和C;输出:投影矩阵A;第1步:构建特征结构的无向图,求解矩阵H=(I-P)T(I-P);第2步:构建数据的近邻图,由式(12),求解矩阵S和D;第3步:根据式(16)和(18),分别计算must-link约束散布矩阵Sw和cannot-link约束散布矩阵Sb;第4步:求解式(21)广义特征值问题,对特征值降序排列,取前r个特征值对应的特征向量,组成投影矩阵A=(a1,…,ar);第5步:输出投影矩阵A.4实验结果——k均值算法实验本节使用UCI数据集,文本数据集和图像数据集来验证文中所提出SSRL算法的有效性.为评价新算法的性能,文中使用最近发表DisKmeans,SCREEN,SSDR和LMDM与SSRL比较.由于K均值算法是一个简单有效的聚类算法,且在变换空间里,聚类性能充分反映维数约减算法的质量,因此,在投影空间里,文中使用K均值算法来聚类投影结果.进而,聚类结果作为最终衡量算法性能的依据.实验中,式(21)中的三个正则化参数的值分别设置为0.01.在3.1节构建的特征图中,每个边的权值Pij由这两个顶点的余弦相似度确定.对某个特征来说,与其它特征相连的所有边上,选择余弦权值最大的20个边作为k的值(在UCI数据集里,k=8).为公平比较,聚类数取数据的真正类数,且所有算法对数据的维数都降到c-1维(c是聚类数).4.1实验2.2聚类结果文中使用聚类算法中常用的两种度量来评价聚类结果.第一个度量是精度(Acc),其定义如下:Acc=1nn∑i=1f(si,map(ri))Acc=1n∑i=1nf(si,map(ri))(22)其中,n是样本数,si与ri分别是样本xi的类标号和聚类标号.如果x=y,则f(x,y)=1,否则为f(x,y)=0.map(ri)是个映射函数,将聚类标号转换为该样本的类标号.第二个度量是归一化互信息(NMI),其定义为:ΝΜΙ=Ι(E,F)√Η(E)Η(F)NMI=I(E,F)H(E)H(F)√(23)其中,E是聚类结果,F是样本的类标号.I(E,F)是E与F互信息量,H(E)和H(F)分别是E与F的熵.另外,所有的算法运行在Matlab环境里.五个算法在每个数据集分别重复实验20次.在每次实验中随机选择300对成对约束并在整个数据集上来测试算法的性能,取20次的均值作为最终的聚类结果.4.2sslr的性能在这个小节里,使用4个UCI数据集来评价五个算法的性能.4个UCI数据集的描述如表1所示.相应的实验结果如表2和图1(见下页)所示.从表2和图1,能得到如下观察:在Satimage,Pendigits和Soybean数据集上,SSRL的性能要明显优于其他4个算法.其中在Pendigits数据集上,SSRL的Acc值要比次优的SSDR高出5个百分点.在Solar数据集上,SSRL的性能也能SSDR相比.显然,集成数据的局部几何结构以及投影向量的特征结构,能保证SSRL有很好的性能.SSDR的性能尽管次于SSRL,但优于其它三个算法.原因是SSDR不仅使用了成对约束信息,还使用了所有的无标号样本来指导维数约减.而不论是SCREEN,还是LMDM,在算法执行中都没有考虑到无标号样本.在所有五个算法中,DisKmeans执行的最差.不难理解,由于DisKmeans是无监督维数约减,因此它并不能得到满意的结果.这也说明一个事实:半监督维数约减算法能够改进无监督维数约减算法的性能.4.3聚类性能对比为了进一步验证SSRL算法的性能,在这个小节里,使用文本和图像数据集来评价5个算法.两个文本数据集Reuters和20Newsgroups.其中,在Reuters数据集中,选择10类2900个样本,它们的维数是1000维;在20Newsgroups数据集里,选择10类7500个样本,它们的维数是4000维.两个图像数据集是USPS数字图像和ORL人脸图像.在USPS中,选择10类7000个样本,维数是256维;在ORL中,图像大小是32×32像素,是256级灰度图像,选择40个人400个人脸图像.实验结果如表3和图2所示.从表3和图2能够观察到,SSRL在20Newsgroups,USPS和ORL上聚类性能最好.在Reuters数据集上,SSDR执行的最好.类似于UCI数据集,DisKmeans在所有算法中聚类性能最差.总体上,SSRL的性能要优于其它四个算法.不过,也应该看到,在Solar和Reuters数据集上,尽管SSRL的聚类性能不是最优,但SSRL的聚类性能接近SSDR的结果.根据上述实验结