2014, Vol. 
随着计算机通信技术和存储技术的发展,数据的获取越来越便利.如何处理海量数据,成为现代科学研究面临的一个巨大挑战.传统的数据挖掘技术在数据维数和规模扩大时,所需资源呈指数级增加,研究既有效又简易的数据表示方法,从而消除数据冗余,建立高效率低成本的数据处理、存储和通信新技术,是大数据分析的一大难题[1].因此,需要研究大数据降维算法,通过寻求其低维特征表示,发现数据潜在的有价值信息.
数据降维算法可以分为线性和非线性两类,其中,非线性算法主要是流形学习方法,经典算法包括等度规特征映射(isometric feature mapping,简称ISOMAP)[2]、局部线性嵌入(local linear embedding,简称LLE)[3]、Laplacian特征映射(Laplacian eigenmap,简称LE)[4]、局部切空间重排列(local tangent space alignment,简称LTSA)[5]、Hessian特征映射(Hessian eigenmaps,简称HLLE)[6]、最大方差展开(maximum variance unfolding,简称MVU)[7]等.近年来,流形学习已被成功应用于人脸识别[8]、图像检索[9, 29]、文本分类[10]和视频分析[11, 12]等领域.然而,在实际应用中仍然存在一些困难:一是所谓的“外样本(out-of-sample)”问题[13],即,高维数据和低维表示之间的映射关系是隐式的,需要通过对所有训练样本进行学习来获得,对于新的测试样本,无法直接求得其低维表示;二是“局部过学习(overlearning of locality)”问题[14],流形学习方法通常是考虑了数据的局部结构,并在局部信息保持的前提下进行特征提取,然而这与用户所要提取的信息并无直接关联;三是计算复杂度高, 尤其是在图像和文本等超高维数据的分析处理中,变得难以施行.由于线性算法可以克服以上难点,从而引起了许多研究者的关注.
传统的线性降维方法有主成分分析(principle component analysis,简称PCA)[15]和线性判别分析(linear discriminant analysis,简称LDA)[16, 17]两种.PCA是一种无监督算法,没有考虑样本的类别信息,从而不能有效地发现数据潜在的判别结构;而LDA算法可直接应用于分类任务,通过最大化类间散度和最小化类内散度,从而获取其低维表示.但是LDA要求类内散度矩阵非奇异,这在实际应用中难以保证.比如,当样本维数高于样本个数时,类内散度矩阵是奇异的,这种情形通常称为小样本(small size sample,简称SSS)问题[18],是机器学习研究领域的一个开放性难题.另外,LDA最多只能提取C-1维的特征(这里,C表示样本的类别个数),这限制了LDA的应用范围.
为了克服LDA应用中的小样本问题,李海峰等人[19]提出了最大边界准则(maximum margin criterion,简称MMC);之后,有学者通过正则化技术对MMC进行了一系列的改进[20，21，22].邱锡鹏等人[23]提出了一种非参数边界最大化准则,通过最大化每个样本点与其不同类的最近样本点距离和最小化每个样本点与其同类的最远样本点距离,来获得低维表示.颜水成等人[24, 25]在图嵌入的框架下提出了边际Fisher分析,其目标在于最大化局部类间散度和最小化局部类内散度,通过数据建图,MFA使得局部边界增大,从而获得判别性能更好的低维表示. MF A可以看作是LDA的局部化扩展.由于线性降维算法等价于学习一个合适的马氏距离度量,Weinberger等人[26]从度量学习的角度提出了基于K最近邻分类器的大边界准则,并将其归结为半定规划问题.王飞、张长水等人[27]提出了平均邻域边界最大化(average neighborhood margin maximization,简称ANMM)算法,该算法将属于同一类的近邻点尽可能地“拉近”,而将属于不同类的近邻点尽可能地“推开”.与MMC考虑数据的全局欧氏结构不同,王海贤等人[28]提出了局部和加权的最大边界判别分析(local and weighted maximum margin discriminant analysis,简称LWMMDA),考虑了数据流形的局部性质,通过权重参数来调整不同类别之间的平均边界,可以有效发现非线性数据流形中的判别结构.蔡登等人[29]根据局部判别分析的思想,构建近邻图以对数据流形的几何结构进行建模,提出了一种半监督的线性降维方法,称为最大边界投影(maximum margin projection,简称MMP),并将其应用于图像检索领域.这些基于边界思想的算法在应用于高维大数据集时,都具有较高的计算代价,或者容易导致数值不稳定.
本文重新定义了样本边界,提出了一种新的有监督的线性降维算法,将其称为边界判别投影(margin discriminant projection,简称MDP).MDP通过最大化属于不同类别的样本之间的最小距离和最小化属于同一类别的样本之间的最大距离,来获得具有最佳判别性能的低维表示.与经典的基于边界思想的数据降维算法相比, MDP算法的优点概述如下:
(1) 边界的定义具有几何直观性.引入边界概念的目的是描述属于不同类别的样本之间的线性可分性,最大化属于不同类别的样本之间的最小距离,这意味着任意两个属于不同类别的样本之间的距离都在增大;而最小化属于不同类别的样本之间的最大距离,就意味着任意两个属于同一类别的样本之间的距离都在减小;
(2) 计算复杂性低.MDP算法只考虑了边界样本点(具体定义见第2.1节),即,属于同一类的距离最大的两个样本点以及属于不同类的距离最小的两个样本点,且不涉及参数调整.在数据建图中,表征样本间相似关系的权值矩阵严重稀疏,给大规模数据矩阵的快速特征分解提供了便利;
(3) 可直接应用于小样本问题.与MMC类似,MDP算法可归结为迹差准则优化问题,其求解过程中不涉及逆矩阵的计算,从而避免了奇异性问题,使得数值求解更加稳定;
(4) 在保持数据流形的几何结构的同时,发现其判别结构.MDP得到的投影矩阵的列向量是Rr一组规范正交基,相当于将原始高维数据在这组规范正交基下进行正交分解,由此得到的新的低维坐标表示不会改变原始数据的度量结构和分布形状(证明见第2.3.1节中的定理3),从而保持了数据的全局几何结构.
1 相关工作给定数据矩阵X={x1,x2,…,xn}ÎRdxn,即n个d维的样本数据,每个样本对应的类别为label(xi)ÎC,其中, C={c1,c2,…,cm}表示类别集合.线性降维算法通常假设高维数据xi与其低维表示yi之间具有显式的映射关系,即:
yi=VTxi (1)
其中,V={v1,v2,…,vr}ÎRdxr称为投影矩阵(其中,r<d).
人们对数据感兴趣的特征不同,从而导致了不同的降维算法.通常,用于降维准则设计的思路有数据流形的全局结构(如距离保持等)、数据流形的局部结构(如近邻关系保持等)和数据类别的判别结构.其中,基于边界思想的经典算法有线性判别分析(LDA)、最大边界准则(MMC)和边界Fisher分析(MFA).
1.1 线性判别分析(LDA)LDA通过最大化类间散度,同时最小化类内散度,来获得判别性较强的低维表示.其中,类间散度矩阵Sb和类内散度矩阵Sw定义如下:
(2)
(3)
其中,ci表示第i类样本集合,mi表示第i类样本均值,m是所有样本均值.于是,LDA算法可归结为下面的优化问题:
(4)
等价地,优化问题(4)可以改写为迹比优化形式:
(5)
由于目标函数(5)是非凸的,没有解析形式的全局最优解,通常将其近似转化为如下的比迹优化问题:
max tr((VTSwV)-1VTSbV) (6)
当类内散度矩阵Sw非奇异时,由公式(6)得到的最优投影矩阵V由
的r个最大特征值所对应的特征向量构成[30].
与LDA类似,MMC的优化目标也是希望投影之后的低维空间中样本的类间散度最大,类内散度最小.不同之处在于,MMC采用了迹差优化模型:
J(V)=tr(VT(Sb-Sw)VT) (7)
限定V的每一列都是单位向量,于是,V可以通过下面的特征分解来求得:
(Sb-Sw)vi=livi (8)
1.3 边界Fisher分析(MFA)训练样本数据之间的内在关系可以通过无向加权图G={G,W}来表示,其中,图的节点集合为训练样本数据X,权重矩阵W表示数据节点之间的某种相似性度量.图G的Laplacian矩阵L定义为
L=D-W (9)
这里,D是一个对角矩阵,且
为了利用数据的局部判别信息,MFA算法采用本征图G+={G,W+}和惩罚图G-={G,W-}表示数据之间的关系,其中,本征图刻画了属于同类的样本之间的近邻关系,而惩罚图刻画了属于不同类的样本之间的近邻关系.于是,权重矩阵可分别定义为
(10)
(11)
这里,
表示与训练样本xi同类的k1个最近邻节点的下标集合,
表示与训练样本xi异类的k2个最近邻节点的下标集合.
在投影之后的低维空间中,训练样本之间的类内紧密性和类间分离性可以分别用公式(12)和公式(13)表示:
(12)
(13)
为了使得样本的低维表示更有利于分类,类似于公式(4),MFA最大化下面的目标函数:
(14)
其中,L-=D--W-和L+=D+-W+分别是惩罚图和本征图所对应的Laplacian矩阵.目标函数(14)的求解过程与目标函数(5)的求解过程类似.
2 边界判别投影 2.1 算法基本思想为了增强原始样本低维表示的判别性能,我们希望经过投影之后,在低维子空间中,类间距离更大,类内距离更小.于是,不同类之间的样本边界更大,从而使得低维表示更加有利于分类.为此,需要重新定义类间距离、类内距离和边界等基本概念.
定义1. 假设xi与xj为任意给定的两个样本,它们之间的距离定义为
d(xi,xj)=||xi-xj||2.
定义2. 假设ci与cj为任意给定的两个不同类别的样本集合,称其类间最近距离的样本点
与
为异类边界样本点,即:
定义3. 对于任意给定的属于同一类的样本集合ci,称其类内最远距离的样本点
与
为同类边界样本点,即:
注:异类边界样本点和同类边界样本点统称为边界样本点.
定义4. 假设ci与cj为任意给定的两个不同类别的样本集合,其类间距离定义为
定义5. 对于任意给定的某类样本集合ci,其类内距离定义为
定义6. 假设样本数据X共有C类,即
,其边界定义为
边界判别投影的基本思想是:将原始高维数据投影至低维空间,使其边界最大,即最大化类间距离,最小化类内距离.如图 1所示,不同的几何形状代表不同的类,类间距离由实线表示,类内距离由虚线表示,通过实线或者虚线连接的样本点为边界样本点,经过变换之后,在保持数据的总体几何结构的前提下,边界得到了增强,样本的可分性更好.
 |
Fig. 1 Illustration of main idea behind our algorithm 图 1 MDP算法基本思想 |
为了保持数据的整体几何结构,我们引入正交约束,即VTV=I,于是,边界判别投影的目标函数为
(15)
其中,d(ci,cj)和d(ci)分别为投影之后的低维数据的类间距离和类内距离,投影之后的低维数据之间的距离为
d(yi,yj)=||VTxi-VTxj||2.
根据定义4,有:
(16)
根据定义5,有:
(17)
将公式(16)和公式(17)代入公式(15),则目标函数可改写为
(18)
显然,在目标函数(18)的计算中,用到的样本点个数至多为
当每类的样本个数大于C+1时,MDP算法可以降低计算量.
为了获得MDP算法目标函数更为简洁的表示,我们将其归结到图嵌入框架下,为此引入类间相似性权重W(b)和类内相似性权重W(w):
(19)
(20)
于是,目标函数(18)可表达为
(21)
根据公式(12)、公式(13)的推导过程,优化问题(21)可以化简为
(22)
其中,L(b)=D(b)-W(b),L(w)=D(w)-W(w),为Laplacian矩阵.
若令S(b)=XL(b)XT,S(w)=XL(w)XT,则公式(22)又可表示为
(23)
从形式上来看,MDP的目标函数与MMC相同.特别地,当训练集中每类只有2个样本时,MDP等价于MMC.
2.2.2 算法介绍在人脸识别、文本分类等实际应用中,样本的维数d通常远远大于样本的个数n,直接通过特征分解求解目标函数(23)的时间复杂度为O(d2),空间复杂度为O(d2),此时,计算耗时且可能导致数值不稳定.比如在人脸识别中,对于一张分辨率为112x92的人脸图像(d=10304),计算中时间代价和存储代价分别为1012和108,对于PC来说,代价过高.MDP算法采用矩阵的QR分解技术[28, 31]来避免这些问题,技术细节推导见第2.3.1节中的定理2.
MDP算法的步骤总结如下:
输入:数据矩阵X,类别标号以及目标维数r;
输出:低维表示Y.
过程:
第1步:计算Laplacian矩阵L=L(b)-L(w).
第2步:QR分解.采用不完全Cholesky分解技术[32],将数据矩阵X分解为X=QR.
第3步:对RLRT作特征分解,获得U=[u1,u2,…,ur],其中,ui是矩阵RLRT的第r个最大特征值对应的特征向量.
第4步:计算投影矩阵V=QU.
第5步:计算yi=VTxi,获得低维表示Y.特别地,对于训练数据X,低维表示可以表示为
Y=VTX=(QU)TQR=UTR (24)
2.3 算法理论分析 2.3.1 相关证明第2.2.2节中,MDP算法第3步求得的投影矩阵的每一列是规范正交的,理论依据见下面的定理1.
定理1. 假设L是nxn对称矩阵,则存在规范正交矩阵V=[v1,v2,…,vd ]ÎRdxd,使得:
XLXTvi=livi,1≤i≤d.
证明:下面采用数学归纳法证明此结论.令k为规范正交向量的个数,则:
当k=1时,显然成立.
假设当k=d-1时结论成立.如果令XLXTv1=l1v1,v1ÎRd且||v1||=1,对任意的
,有:
(XLXTu)Tv1=uTXLXTv1=uTl1v1=l1(uTv1)=0.
因此,
.这里,
.根据假设,当k=d-1时,存在正交矩阵V¢=[v2,v3,…,vd]ÎRdx(d-1),使得:
XLXTvi=livi,2≤i≤d.
令V=v1+V¢ÎRdxd,故V=[v1,v2,…,vd]ÎRdxd为正交矩阵,且满足:
XLXTvi=livi,1≤i≤d. □
定理2. 假设X=QR,其中,QÎRdxt,RÎRtxn,t=rank(X)且QTQ=I,L是nxn对称矩阵,则XLXT与RLRT具有相同的特征值,且相应的特征向量具有下列关系:V=QU ,其中,V和U的列向量分别为XLXT与RLRT的特征向量.
证明:将X=QR代入XLXT,得:
XLXT=QRL(QR)T=Q(RLRT)QT (25)
因为V和U分别由XLXT与RLRT的特征向量构成,即:
XLXTV=VL1,RLRTU=UL2 (26)
又XLXT与RLRT是对称矩阵,则:
VTV=I,UTU=I.
于是,公式(26)可分别改写为
VTXLXTV=L1 (27)
UTRLRTU=L2 (28)
将公式(25)代入公式(27),得:
VTQ(RLRT)QTV=L1 (29)
对比公式(28)和公式(29),可知:
L1=L2且QTV=U,
即,V=QU. □
定理3. MDP可以保持数据流形的几何形状.
证明:对任意两个数据点的低维表示yi,yj,其欧氏距离可以表示为
由于V=(v1,v2,…,vr)的列向量是规范正交的,则
,于是:
因此,低维表示之间的欧氏距离等价于原始样本在前r个坐标轴上做正交投影之后的欧氏距离,即,MDP所得到的低维表示保持了原始样本的几何形状.
2.3.2 复杂度分析第1步中,距离计算的时间复杂度为O(dn2),寻找同类最远样本点和不同类最近样本点时可采用单轮的冒泡排序算法,其时间复杂度为O(n);
第2步中,计算R时,对X进行QR分解的时间复杂度为O(t2n);
第3步中,对RLRT进行特征分解的时间复杂度为O(t3).
因此,MDP算法的时间复杂度为O(t3+t2n+dn2+n).
由于计算中矩阵的最大规模为dxn,因此,空间复杂度为O(dn).
3 实 验图像数据是典型的高维数据,为了验证MDP算法的有效性,我们将其应用于人脸识别,并与PCA,LDA, MFA,MMC等经典算法进行比较.
3.1 数据集描述实验中所选用的人脸数据集相关描述见表 1.为了便于数值处理,均采用灰度人脸图像,且经过裁剪和缩放至合适的大小,数据集中示例图像如图 2~图 7所示.UMIST数据集(http://www.sheffield.ac.uk/eee/research/iel/ research/face)共有20个人的564张人脸图像,包括不同的种族、性别、外貌以及从侧面转向正面的不同姿态,具有典型的流形结构.YaleB数据集(http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html)包含了38个人在不同的光照条件和面部表情下的人脸图像.FERET数据集(http://www.datatang.com/data/44111)共有14 051张人脸图像,本文仅选取了该数据集的200个人共1 400张图像用于实验,每个人有7张图像,包含了表情、光照和姿态等变化.GeorgiaTech数据集(http://www.anefian.com/research/face_reco.htm)由50个人在不同的时间下拍摄,每个人有15张图像,包含不同的倾斜、表情和光照.Yale数据集(http://cvc.yale.edu/projects/yalefaces/ yalefaces.html)由耶鲁大学计算视觉与控制中心创建,每个人脸有15张图像,包括了光照(如正面、左侧和右侧)、是否戴眼镜、人脸表情(如正常、高兴、悲伤、困乏、惊讶和眨眼)等因素的变化.AR数据集(http://rvl1.ecn.purdue. edu/~aleix/aleix_face_DB.html)是公认度比较高的一种数据库,实验中 选取了100个人,每人14张图像,分别对应于不同表情和光照条件下的人脸.
|
Table 1 Data sets description 表 1 数据集说明 |
 |
Fig. 2 Sample image from UMIST data set 图 2 UMIST数据集上的图像示例 |
 |
Fig. 3 Sample image from YaleB data set 图 3 YaleB数据集上的图像示例 |
 |
Fig. 4 Sample image from FERET data set 图 4 FERET数据集上的图像示例 |
 |
Fig. 5 Sample image from GeorgiaTech data set 图 5 GeorgiaTech数据集上的图像示例 |
 |
Fig. 6 Sample image from Yale data set 图 6 Yale数据集上的图像示例 |
 |
Fig. 7 Sample image from AR data set 图 7 AR数据集上的图像示例 |
为了克服计算中的奇异性问题,其中,LDA和MFA均采用PCA进行预处理,并设置主成分贡献率为0.95.实验中所涉及的参数均由经验给出,MFA算法Gauss热核参数t的设置参见局部判别嵌入[33]的源代码(http://www.cs.nthu.edu.tw/~htchen/),MFA中的近邻参数k设置为5,同类近邻参数k1设置为2,异类近邻参数k2设置为10.降维之后,统一采用KNN算法进行分类,并比较其分类的准确率(即识别率).每次实验中,在每个类别中随机选取l(l=3,4,5)个样本作为训练集,剩余的样本作为测试集.重复进行20次随机划分,并计算其平均识别率和标准差(均采用百分比).
3.3 结果分析表 2~表 7分别报告了在不同人脸数据集选取不同数目的标记样本下的实验结果,包括最优平均识别率及其对应的标准差和目标维数.从中可以看出,除Yale数据集外,MDP算法在其他人脸数据集上的识别率都高于PCA,LDA,MFA和MMC.在Yale数据集上,当l=3时,MDP和MFA最优识别率基本一致,高于其他算法,然而在l=4和l=5时,MDP算法的识别率低于MFA.与MFA 相比,MDP只考虑了数据的全局结构,而在某些复杂结构的数据集中,全局结构不足以较好地刻画不同类别数据之间的判别信息.图 8显示了在UMIST数据集上,不同数目的标记样本情况下,随着目标维数的改变,这5种算法平均识别率的变化.随着训练样本个数的增加,识别率也在增加.MDP算法不涉及参数的调整,而且在不同的数据集和不同训练样本情况下,均取得了最优的识别率.
|
|
Table 2 Recognition results on UMIST data set 表 2 UMIST数据集上的识别结果 |
|
|
Table 3 Recognition results on YaleB data set 表 3 YableB数据集上的识别结果 |
|
|
Table 4 Recognition results on FERET data set 表 4 FERET数据集上的识别结果 |
|
|
Table 5 Recognition results on GeorgiaTech data set 表 5 GeorgiaTech数据集上的识别结果 |
|
|
Table 6 Recognition results on Yale data set 表 6 Yale数据集上的识别结果 |
|
|
Table 7 Recognition results on AR data set 表 7 AR数据集上的识别结果 |
 |
Fig. 8 Comparisons of recognition results on UMIST data set 图 8 UMIST数据集上的识别结果比较 |
PCA预处理在克服小样本问题的同时,也降低了后续算法处理的计算量.为了比较各算法的时间损耗以及PCA预处理对MDP算法性能的影响,表 8报告了AR人脸数据集(l=5,重复20次随机划分)上各算法在经过PCA预处理(主成分贡献率为0.95)后的数据上的平均最优识别率及其对应的标准差(均采用百分比表示)和取得最优识别率的维数,以及各算法平均运行1次的时间消耗(时间单位以秒计).实验均采用MATLAB 2010编码实现,计算设备为个人计算机,其中,处理器为英特尔双核3.16GHz,内存为4G,操作系统为64位Windows 7.对比表6和表7的结果可以看出:MDP算法的运行时间与LDA相当,但低于MFA和MMC.同时,PCA预处理会降低MDP算法的识别率[34].
|
|
Table 8 Performance comparison on AR data set (l=5) 表 8 AR数据集(l=5)上的性能比较 |
另外,实验中注意到,MMC算法并不稳定,在某些数据集上识别率很差.当样本数目小于样本维数(即小样本问题)时,基于迹差准则(即目标函数(7))的降维算法比基于迹比准则(即目标函数(5))的降维算法效果更好;当样本数目较多或者计算中的奇异性问题能够被有效避免时,基于迹比准则的降维算法比基于迹差准则的降维算法效果更好,因为迹比准则所生成的投影向量是相互统计无关的[35].
4 结束语
作为一种新的有监督线性降维方法,MDP通过最大化异类样本之间的最小距离,同时最小化同类样本之间的最大距离,在保持样本全局几何结构的基础上,增强数据的判别性能.与经典的基于边界思想的降维算法相比,MDP无需额外的参数设置,而且求得的投影矩阵的列向量是规范正交的,保持了原始数据流形的全局几何结构.从计算的角度来讲,MDP避免了小样本问题,并采用QR分解技术建立了高效而稳定的算法.人脸数据集上的实验结果表明了该算法的有效性.
致谢 在此,我们向对本文的工作给予支持和建议的同行,尤其是武汉大学软件工程国家重点实验室丁立新教授领导的讨论班上的同学和老师表示感谢.
| [1] | Li GJ. The scientific value of big data. Research Communications of The CCF, 2012,8(9):8-15 (in Chinese with English abstract). |
| [2] | Tenenbaum JB, De Silva V, Langford JC. A global geometric framework for nonlinear dimensionality reduction. Science, 2000, 290(5500):2319-2323 . |
| [3] | Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000,290(5500):2323-2326 . |
| [4] | Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In: Proc. of the NIPS, Vol.14. 2001. 585-591. http://machinelearning.wustl.edu/mlpapers/paper_files/nips02-AA42.pdf |
| [5] | Zhang Z, Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. Journal of Shanghai University (English Edition), 2004,8(4):406-424 . |
| [6] | Donoho DL, Grimes C. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. of the National Academy of Sciences, 2003,100(10):5591-5596 . |
| [7] | Weinberger KQ, Sha F, Saul LK. Learning a kernel matrix for nonlinear dimensionality reduction. In: Proc. of the 21st Int’l Conf. on Machine Learning (ICML 2004). 2004. 839-846 . |
| [8] | He XF, Yan SC, Hu YX, Niyogi P, Zhang HJ. Face recognition using laplacianfaces. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2005, 27(3):328-340 . |
| [9] | He XF, Ma WY, Zhang HJ. Learning an image manifold for retrieval. In: Proc. of the 12th Annual ACM Int’l Conf. on Multimedia. ACM Press, 2004. 17-23 . |
| [10] | Cai D, He XF. Manifold adaptive experimental design for text categorization. IEEE Trans. on Knowledge and Data Engineering, 2012,24(4):707-719 . |
| [11] | Tang JH, Hua XS, Qi GJ, Wang M, Mei T, Wu XQ. Structure-Sensitive manifold ranking for video concept detection. In: Proc. of the ACM Conf. on Multimedia. New York: ACM Press, 2007. 852-861 . |
| [12] | Hoi SCH, Lyu MR. A multimodal and multilevel ranking scheme for large-scale video retrieval. IEEE Trans. on Multimedia, 2008, 10(4):607-619 . |
| [13] | Bengio Y, Paiement JF, Vincent P. Out-of-Sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. In: Advances in Neural Information Processing Systems. MIT Press, 2003. 177-184. http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10.1.1.5.1709 |
| [14] | Vlassis N, Motomura Y, Krose B. Supervised dimension reduction of intrinsically low dimensional data. Neural Computation, 2002, 14(1):191-215 . |
| [15] | Jolliffe IT. Principal Component Analysis. New York: Springer-Verlag, 1986. |
| [16] | Fisher RA. The statistical utilization of multiple measurements. Annals of Eugenics, 1938,8(4):376-386 . |
| [17] | Rao CR. The utilization of multiple measurements in problems of biological classification. Journal of the Royal Statistical Society-Series B: Statistical Methodology, 1948,10(2):159-203. |
| [18] | Belhumeur PN, Hespanda J, Kiregeman D. Eigenfaces vs. fisherfaces: Recognition using class specific linear projection. IEEE Trans. on PAMI, 1997 . |
| [19] | Li HF, Jiang T, Zhang KS. Efficient and robust feature extraction by maximum margin criterion. IEEE Trans. on Neural Networks, 2006,17(1):157-165 . |
| [20] | Zheng WM, Zou CR, Zhao L. Weighted maximum margin discriminant analysis with kernels. Neurocomputing, 2005,67:357-362 . |
| [21] | Liu QS, Tang XO, Lu HQ, Ma SD. Face recognition using kernel scatter-difference-based discriminant analysis. IEEE Trans. on Neural Networks, 2006,17(4):1081-1085 . |
| [22] | Liu J, Chen SC, Tan XY, Zhang DQ. Comments on “efficient and robust feature extraction by maximum margin criterion”. IEEE Trans. on Neural Networks, 2007,18(6):1862-1864 . |
| [23] | Qiu XP, Wu LD. Face recognition by stepwise nonparametric margin maximum criterion. In: Proc. of the 10th IEEE Int’l Conf. on Computer Vision (ICCV 2005), Vol.2. IEEE, 2005. 1567-1572 . |
| [24] | Yan SC, Xu D, Zhang BY, Zhang HJ. Graph embedding: A general framework for dimensionality reduction. In: Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR 2005), Vol.2. IEEE, 2005. 830-837 . |
| [25] | Yan SC, Xu D, Zhang BY, Zhang HJ, Yang Q. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2007,29(1):40-51 . |
| [26] | Weinberger KQ, Blitzer J, Saul LK. Distance metric learning for large margin nearest neighbor classification. In: Advances in Neural Information Processing Systems, Vol.18. MIT Press, 2006. 1473. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1. 117.5831 |
| [27] | Wang F, Zhang CS. Feature extraction by maximizing the average neighborhood margin. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR 2007). IEEE, 2007. 1-8 . |
| [28] | Wang HX, Zheng WM, Hu ZL, Chen SB. Local and weighted maximum margin discriminant analysis. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR 2007). IEEE, 2007. 1-8 . |
| [29] | He XF, Cai D, Han JW. Learning a maximum margin subspace for image retrieval. IEEE Trans. on Knowledge and Data Engineering, 2008,20(2):189-201 . |
| [30] | Fukunaga K. Introduction to Statistical Pattern Recognition. 2nd ed., Boston: Academic Press, 1990. |
| [31] | Ye JP, Li Q, Xiong H, Park H, Janardan R, Kumar V. Idr/qr: An incremental dimension reduction algorithm via qr decomposition. In: Proc. of the 10th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD 2004). New York, 2004. 364-373 . |
| [32] | Shawe-Taylor J, Cristianini N. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004. |
| [33] | Chen HT, Chang HW, Liu TL. Local discriminant embedding and its variants. In: Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, Vol.2. IEEE, 2005.846-853 . |
| [34] | Zhang TP, Fang B, Tang YY, Shang ZW, Xu B. Generalized discriminant analysis: A matrix exponential approach. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010,40(1):186-197 . |
| [35] | Tao Y, Yang J. Quotient vs. difference: Comparison between the two discriminant criteria. Neurocomputing, 2010,73(10): 1808-1817 . |
| [1] | 李国杰.大数据研究的科学价值.中国计算机学会通讯,2012,8(9):8-15. |