（信号与信息处理专业论文）无监督与半监督降维算法研究.pdf

摘要 摘要 在机器学习和模式识别领域，会不可避免地遇到很多高维数据，从而出现“维 数灾难”。为了避免“维数灾难”问题，需要对高维数据进行特征降维。特征降维 是指通过线性或者非线性映射把高维数据投影到一个低维的空间，同时揭示隐藏 在数据中的内在结构信息。本文主要研究基于无监督和半监督的特征降维算法。 首先，在无监督降维方面，高斯过程隐变量模型是一种有效的方法。它提供 了一个从低维隐变量空间到高维观测数据空间的光滑映射。这种光滑映射就可以 使得在隐空间中相距较近的样本点，经过映射到观测数据空间后，依然相距较近。 然而，它并不能保证在数据空间相距较近的样本点经该映射降维到隐空间后依然 相距较近。为了解决高斯过程隐变量模型的这一不足，提出了一种基于局部保持 的隐变量模型算法。该算法能使得在数据空间相距较近的样本点经过降维后，在 隐空间中依然相距较近。在几类数据库上进行的测试结果表明了该算法的有效性。 其次，在半监督降维方面，除了可以知道样本的类标信息，还有另外一种监 督信息，即成对约束信息。成对约束是指两个样本要么属于同一类，要么不属于 同一类。但是目前利用成对约束进行降维的算法只是简单的利用约束关系，并没 有挖掘成对约束关系中的本质特性，比如传递性和排斥性。因此，提出了两种半 监督降维算法：一种是基于整体保持的半监督降维算法，该算法不仅利用了约束 关系的传递性和排斥性，而且还保持数据集所在低维流形的整体结构；另一种是 基于局部保持的半监督降维算法，该算法除了利用了成对约束的传递性和排斥性 外，还可以保持数据集所在低维流形的局部结构。在几类数据库上实验表明，该 算法要优于其他的降维算法。 关键词：降维高斯过程隐变量模型成对约束 a b s t r a c t a b s t r a c t i nm a c h i n el e a r n i n ga n dp a t t e r nr e c o g n i t i o n ，i ti si n e v i t a b l et oe n c o u n t e rw i t h h i g h d i m e n s i o n a ld a t as e t s ，w h i c hu s u a l l yc a u s eap r o b l e mc a l l e d t h ec u r s eo f d i m e n s i o n a l i t y t h e ni ti sn e c e s s a r yt or e d u c et h ed i m e n s i o no ft h ed a t as e t st oa v o i dt h e c u r s eo fd i m e n s i o n a l i t y d i m e n s i o n a l i t yr e d u c t i o na i m st oc a p t u r et h es t r u c t u r eo ft h e d a t as e t se m b e d d e di nt h el o w - d i m e n s i o n a ls p a c et h r o u g ht h el i n e a ro rn o n - l i n e a r m a p p i n g s n em a i np u r p o s eo ft h i sp a p e ri s t o d e v e l o pu n s u p e r v i s e da n ds e m i - s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m s f i r s t l y , i nt h eu n s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n , o a u s s i a np r o c e s sl a t e n t v a r i a b l em o d e l ( g p l v m ) i sa ne f f e c t i v ea l g o r i t h mo fd i m e n s i o n a l i t yr e d u c t i o n i t p r o v i d e sas m o o t hm a p p i n gf r o mt h el a t e n ts p a c et ot h ed a t as p a c e t l l i ss p e c i f i e st h a t p o i n t sw h i c ha r ec l o s ei nl a t e n ts p a c ew i l lb es t i l lm a p p e da sc l o s ei n d a t as p a c e h o w e v e r , i td o e sn o tg u a r a n t e et h a tp o i n t sw h i c ha r ec l o s ei nd a t as p a c ew i l lb ec l o s ei n t h el a t e n ts p a c e i no r d e rt oo v e r c o m et h i sd r a w b a c k ，al a t e n tv a l i a b l em o d e lb a s e do n l o c a l i t yp r e s e r v i n gp r o j e c t i o n si sp r o p o s e di nt h i sp a p e r1 1 1 el a t e n tv a r i a b l em o d e lc a n f o r c ep o i n t sw h i c ha r ec l o s ei nd a t as p a c et ob ec l o s ei nt h el a t e n ts p a c e e x p e r i m e n t a l r e s u l t so ns e v e r a ld a t a s e t sd e m o n s t r a t et h ee f f e c t i v e n e s so ft h i sm e t h o d s e c o n d l y , i nt h es e m i s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n ，e x c e p tt h el a b e lo f i n s t a n c e s ，t h e r ei sa n o t h e rk i n do fs u p e r v i s e di n f o r m a t i o n , i e ，p a ir w i s ec o n s t r a i n t s p a i r w i s ec o n s t r a i n t si n d i c a t ew h e t h e rt w oi n s t a n c e sb e l o n gt ot h es a m ec l a s so rn o t h o w e v e r , t h ee x i s t i n ga l g o r i t h m sb a s e do np a i r w i s ec o n s t r a i n t sh a v en o te x p l o i t e dt h e i n t r i n s i cp r o p e r t i e so fc o n s t r a i n t s ，s u c ha st r a n s i t i v i t ya n de x c l u s i v i t y t h e r e f o r e ，t w o s e m i s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m sa l ep r o p o s e di nt h i sp a p e r o n ei s ad i m e n s i o n a l i t yr e d u c t i o nb yu s i n gg l o b a lp r e s e r v i n ga l g o r i t h mb a s e do np a i r w i s e c o n s t r a i n t s ，w h i c hc a nn o to n l ye x p l o i tt h et r a n s i t i v i t ya n de x c l u s i v i t y , b u ta l s op r e s e r v e t h eg l o b a ls t r u c t u r eo ft h ed a t am a n i f o l di nl o wd i m e n s i o n a le m b e d d i n gs p a c e ；t h eo t h e r i sad i m e n s i o n a l i t yr e d u c t i o nb yu s i n gl o c a lp r e s e r v i n gb a s e do np a i r w i s ec o n s t r a i n t s ， w h i c hc a np r e s e r v et h et r a n s i t i v i t ya n de x c l u s i v i t ya sw e l la st h el o c a ls t r u c t u r eo ft h e d a t am a n i f o l d e x p e r i m e n t so ns e v e r a ld a t as e t ss h o wt h a ti ti ss u p e r i o rt oo t h e r d i m e n s i o n a l i t yr e d u c t i o nm e t h o d s k e y w o r d s ：d i m e n s i o n a l i t yr e d u c t i o n g a u s s i a np r o c e s s l a t e n tv a r i a b l e m o d e lp a i r w i s ec o n s t r a i n t s 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加 以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的 研究成果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期竺止：! ：! l 西安电子科技大学 关于论文使用授权的说明 术人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期i 自j 论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布 沦文的个部或部分内容。可以允许采用影印、缩印或其它复制手段保存论文。 本人签名：j 啦 导师签名：瘟垒盘! 盘 日期竺型：! 1 日期塑! ! ：! ：! ! 第一章绪论 第一章绪论 1 1 研究背景与意义 随着当今科技的日新月异，人们获取信息数据的方式越来越多样化，获得的 信息也以爆炸式的速度增长，并且这些数据具有高维数、非线性、极复杂等特性。 这些数据既对客观对象提供了丰富、细致的描述，同时也给后面的数据处理工作 带来了很多问题。在实际应用中，人们总是希望能揭示隐藏在这些复杂繁琐的数 据里的内在规律，这就需要对数据进行特征降维。特别是在模式识别领域【l 】【2 】中， 数据的特征降维【3 j 是一个必不可少的环节。模式识别主要包括两个阶段，即训练阶 段和分类识别阶段。训练阶段是指通过大量的样本数据对分类器进行训练，从而 寻找分类规律的过程。当然，在训练阶段也要对训练样本数据进行降维处理。识 别阶段主要是指根据分类规律对未知的样本进行分类和识别的过程。模式识别可 以分为很多个研究领域，比如句法结构模式识别【4 1 、人工神经网络模式识别【5 1 和统 计模式识别【6 j 【7 j 等。 句法结构模式识别：句法结构模式识别是美籍华人傅京孙教授提出的，它将 对象模式由一定的基元之间的结构关系表征，采用规则或语法函数作为识别函数， 选择接受错误率作为准则函数进行模式识别。除了分类信息外，句法结构方法还 能给出模式的结构信息。句法结构办法为模式识别提供了用简单的有限模式基元 和文法规则的有限集来描述一个复杂模式集合的可能性。句法结构模式识别是从 待识别对象的结构特征的描述入手，对对象进行模式识别。 人工神经网络模式识别：人工神经网络的研究起源于对生物神经系统的研究。 人工神经网络区别于其他识别方法的最大特点是它对待识别的对象不要求有太多 的分析与了解，具有一定的智能化处理的特点。 统计模式识别：统计模式识别是受决策论的影响而产生的一种模式识别方法。 它假设被采样的样本数据是符合一定分布的随机变量。该样本数据是一个高维特 征向量，其各分量是由采样对象的特征属性构成的。统计模式识别的基本思想便 是将特征向量定义在一个特征空间里，不同的样本数据对应于特征空间中不同的 点。在分类识别的时候，根据决策论的原理对特征空间进行划分，划分成几个互 不相交的区域，从而达到识别不同特征对象的目的。本文所研究的内容主要属于 统计模式识别范畴。 一个模式识别系统大致由三部分组成，分别是数据采集、数据预处理和分类 识别。数据采集是指通过各种传感器把被研究的对象的各种属性转换为计算机可 无监督与半监督降维算法研究 以处理的数值或符号。通常，把这些数值或符号称为模式，它们所组成的空间称 为模式空间。为了降低计算复杂度和提取对识别有效的信息，必须要对这些原始 数据进行降维处理，形成模式的特征空间。后续的分类识别过程便是在特征空间 中进行的。数据预处理主要是是对数据进行降维，去除冗余信息和降低计算复杂 度。分类器设计的主要是通过训练确定判决规则，使按此类判决规则分类时，错 误率最低，把这些判决规则建成标准库。分类决策主要是指在特征空间中对被识 别对象进行分类。 总的来说，模式识别系统基本组成和识别过程可以概括如下副8 1 。 图1 1 模式识别过程示意图 从图1 1 可以看出，特征降维是模式识别系统中至关重要的一环，对后续的识 别过程起着重要的作用。 模式识别根据从样本中提取的特征，把样本划分成不同的模式类别。其主要 步骤是，先将样本表示为特征空间中的向量，即特征向量；然后利用训练样本对 分类算法或学习算法进行训练，寻找出隐藏在训练样本中各个模式类别中的统计 特性，然后根据这些统计特性确定出分类准则；最后根据这些准则对未知的模式 样本进行分类识别。样本的特征是否准确将严重影响分类识别的结果。 一般情况下，包含足够的类别信息的样本在通过分类器的时候才能被正确的 分类。可是，样本中是否包含足够多的类别信息，人们是很难确定的。为了能提 高识别率，人们便采集了大量的特征信息，这使得原始特征空间的维数达到上千 甚至上万维。l i - , 女n 在人脸图像识别【9 】中，处理一幅2 5 6 x 2 5 6 的人脸图像的时候，通 常会先把它拉成一个向量，把它看作观测空间中的一个点，然后再对它进行后续 的处理。该向量的维数达到了2 5 6 x 2 5 6 = 6 5 5 3 6 ，维数十分的巨大。如果在观测空 间中直接对原始数据进行处理，并进行分类器的训练，将会带来一些棘手的问题。 因为随着输入样本的维数的增加，分类器所要估计的一些参数也在增加，这样引 第一章绪论 3 进误差的可能性也大大增加了；同时，很多分类算法在低维特征空间中能表现出 良好的分类识别性能，但是在高维空间中却表现得很差，这无疑也造成了识别率 的降低。还有，样本的特征中也可能存在较大的相关性，这些信息不但不会提高 识别率，相反还会降低识别精度。此外，在高维空间中对处理原始数据，会带来 极大的计算复杂度，还可能使得识别率大大地降低。所以，一般都是先对高维数 据实行降维操作后，然后再进行相应的分类识别操作。 在实际应用中，人们经常会遇到这样的问题：样本点数据的维数很高，样本 点数据的数量却较少，而估计高维数据所需要的样本个数与维数成指数增长的关 系，这就是著名的“维数灾难 【l o 】问题。在很多新兴的模式识别领域中，如人脸 检测和识别i l l 】和文本分类【1 2 】等，都曾遇到过“维数灾难”问题。如果不进行适当 的数据降维，那么很难对原始数据进行有效的分析。幸运的是实际应用中的高维 数据的各维数之间存在一定的相关性和规律性，也就是实际数据常存在外在维数 和本征维数。而本征维数相对外在维数来说比较低，这意味着存在对高维数据进 行降维，从而避免维数灾难的可能性。数据降维在很多领域都起着重要的作用。 在模式识别领域，高维数据经过降维投影到了一个低维空间中，可以揭示数据的 低维结构，提高识别的效率。 作为数据的预处理步骤，降维是指高维数据样本从观测空间通过线性或者非 线性映射投影到一个低维的空间，从而寻找隐藏在数据间的内在关系和规律。在 低维空间中，对数据进行模式分类便可以得到更加精确的结果，同时大大地降低 的运算复杂度和运算时间。另外，降维还经常用在数据可视化领域。高维数据的 可视化降维处理，就是将观测空间中的高维数据变换成低维( 如二维或三维) 数 据，然后就能够很直观的看到高维观测数据在低维窄间中所隐藏的聚类性质、空 间分布等结构特性。 因此，特征降维是一个值得研究的问题，本文主要针对这一问题进行了研究。 1 2 研究进展及状况 b e l l m a n 在1 9 6 1 年提出了“维数灾难”问题，当时是指估计一个变量函数所 需要的样本采样点数会随着变量个数的增加呈指数增长。对应到模式识别领域是 指对高维样本数据进行处理时，需要的样本点数很多，而实际中可以利用的样本 点个数相对样本维数来说却少得多。特征降维是克服“维数灾难”问题的有效手 段之一。它通过对高维数据集合的分析来寻找嵌入在高维数据空间中的本征低维 结构，以达到数据降维目的。 特征降维大体上可以分为特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e a t u r e 4 无监督与半监督降维算法研究 e x t r a c t i o n ) 两大类。两者的主要区别是特征选择没有产生新的特征，而特征提取则 产生了新的特征。 特征选择的目的是努力寻找一个可以合适表示原始数据的特征子集。合适的 特征以及合适的特征数目是根据不同的准则来选择的。当训练样本的数量有限， 样本的维数很大的时候，只使用少量的特征对分类器来说是有利的。例如，在使 用基因表达的数据进行诊断时，分类器将会根据上万个基因数据的表达水平来确 定一个病人的疾病。可是经常只有十来个病人的数据来对分类器进行训练【l3 1 。此 时，使用少量相关的子集得到可靠的参数估计就显得非常重要。特征选择可以分 为”w r a p p e r 和”f i l t e r ”两种u4 。其中，通过方差和f i s h e r 分数( f i s h e rs c o r e ) 以及 l a p l a c i a n 分数( l a p l a c i a ns c o r e ) t ”】进行特征选择都属于”f i l t e r 方法；基于特定分类 器( 比如支持向量机) 1 6 】的特征选择属于w r a p p e r ，方法【1 7 1 1 引。 特征提取也称为特征变换，它是通过对原始特征进行处理而产生新的特征子 集。根据不同的准则，目前的特征提取方法的分类也不同。比如按照是否为线性， 可以分为线性降维方法和非线性降维方法。线性的特征提取所产生的新特征是原 始特征的线性组合。主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 【1 9 儿2 0 】和线性判 别分析( l i n e a rd i s c r i m i n a t i v ea n a l y s i s ，l d a ) t 2 1 儿2 2 】便是两种最经典和应用最广泛的 线性特征变换方法。此外，b i s h o p 等人【2 3 】还对p c a 进行了概率上的阐述，提出了 概率的p c a 方法( p r o b a b i l i s t i cp r i n c i p a lc o m p o n e n ta n a l y s i s ，p p c a ) 。x h e 与 e n i y o g i 提出了局部保持映射算法( l o c a l i t yp r e s e r v i n gp r o j e c t i o n s ，l p p ) 阱l 。对于非 线性降维，核方法【2 5 】使用比较广泛，如核主成分分析( k e r n e lp r i n c i p a lc o m p o n e n t a n a l y s i s ，k _ p c a ) 嵋6 j 、核f i s h e r 线性判别分析( k e r n e lf i s h e rl i n e a rd i s c i r m a t i v e a n a l y s i s ，k f l d a ) t 2 7 】等广泛应用到很多领域。除此之外，还有另一类非线性降维方 法是从流形学习的角度提出的。其中以局部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ， l l e ) 1 2 8 】和i s o m a p 2 9 】最为典型。后来又出现了l a p l a c i a ne i g e n m a p s 3 0 1 。这类方法 仅仅是对训练样本进行特征变换，产生低维数据。由于这类算法不存在从原始特 征到变换特征的映射，所以对于训练样本以外的未知样本来说，其低维空间的表 示有一定的难度【3 1 1 。除此之外，n e i l l a r r a n c e 提出的高斯过程隐变量模型算法 ( g a u s s i a np r o c e s sl a t e n tv a r i a b l em o d e l ，g p l v m ) 1 3 2 1 3 3 】【划也是一种有效的非线性 降维算法，而且已经应用到了很多领域。 按照是否包含监督信息，大致可以分为无监督降维方法、有监督降维方法。 无监督降维方法主要是提取保持数据结构的特征信息，有监督降维方法主要是提 取数据判别特性的特征信息。其中p c a ，l l e ，l p p ，i s o m a p ，k p c a ，g p l v m 等都属于无监督降维方法，而l d a 显然属于有监督的降维方法。 有时候，人们会面临这样的尴尬情况：就是可以获得一部分数据的标签先验 知识，而剩余的大部分数据却无任何先验知识。这个时候该如何处理这些样本数 第一章绪论 据以便揭示它们之间的内在联系呢? 如果直接对样本数据进行无监督降维方法处 理，那么就没能很好的利用一部分样本数据的先验信息，得到的结果将不能很好 的揭示样本数据的关系：同理，如果仅仅利用有监督降维方法来处理这些样本数 据，那么就没能很好的利用大量的无先验信息的样本数据，降维的结果肯定也是 不理想的。想要既利用到部分样本数据的先验信息又要利用大量无先验信息的样 本数据来进行降维，无监督和有监督降维方法都不能满足，为此需要进行一些半 监督降维算法的研究。然而在很多情况下，人们往往不能明确得知某一样本的具 体标签先验信息，所知道的先验信息仅仅是某两个样本是否属于同一类别( 类别 标签未知) 的信息，这种信息称为成对约束( p a i r w i s ec o n s t r a i n t s ) 信息【3 5 】。成对约束 包括两种形式：一种是m u s t 1 i n k 约束，另一种是c a n n o t 1 i n k 约束。m u s t 1 i n k 约束 表示两个样本属于同一类，但是不知道其确切的标签信息；c a n n o t 1 i n k 约束表示两 个样本不属于同一个类别。从成对约束信息中可以知道，属于m u s t l i n k 约束的数 据样本对在经过降维处理后应该尽量聚集，而属于c a n n o t 1 i n k 约束的数据样本对 经过降维处理后应该尽量的发散。成对约束信息是一种比标签信息更一般的信息， 因为从标签信息得到成对约束信息，但是从成对约束信息得不到标签信息。 最近，利用成对约束信息进行数据降维受到了越来越多的关注。s h e n t a l 等人 提出了一种相关成分分析算法( r e l e v a n tc o m p o n e n t a n a l y s i s ，r c a ) i 3 6 j ，但是该算法 仅仅利用了m u s t 1 i n k 约束信息，没有利用c a n n o t 1 i n k 约束信息，同时忽略了隐藏 在大量未标记数据中的潜在的数据结构信息。t a n g 和x i n g 等人【3 7 】提出的算法很好 的利用了成对约束信息，但是没能利用隐藏在未标记数据中的潜在结构信息。 z h a n g 等人提出了一种半监督降维算法( s e m i s u p e r v i s e dd i m e n s i o n a l i t yr e d u c t i o n s s d r ) t 3 3 】，该算法不仅能很好的利用了成对约束信息而且还能够保持未标记数据 所在的低维流型的整体结构。s t e v e n 等人提出了一种判别成分分析算法 ( d i s c r i m i n a t i v ec o m p o n e n ta n a l y s i s ，d c a ) t 3 9 1 ，该算法虽然利用到了成对约束问韵 传递性和排斥性，但是它却没能进一步地利用隐藏在未标记数据中的结构信息。 1 3 论文研究内容及章节安排 特征降维是对数据的预处理，它可以去除数据的冗余信息，可视化数据以及 降低计算复杂度等。本文主要针对无监督降维和半监督降维方法进行研究，并在 前人的工作的基础上，提出了一些新的思想和方法，并且取得了较好的结果。 概括起来，本文所取得的主要研究成果如下： 1 关于无监督降维，提出了一种基于局部保持的隐变量模型算法。 g p l v m 算法是一种很有效的无监督降维算法，它由于建立了从低维隐空间 到高维观测空间的光滑映射，所以能很好的保持隐空间数据的局部结构。然而 6 无监督与半监督降维算法研究 g p l v m 却不能保持数据空间的局部结构。因此，为了能克服这一不足，本文提 出了一种局部保持的隐变量模型算法。该算法是用l p p 来约束g p l v m ，在降维 时能很好的保持数据的局部信息。 2 关于半监督降维，主要是针对成对约束的半监督降维，提出了两种算法：一种 是整体保持的成对约束降维算法，另一种是局部保持的成对约束降维算法。 在模式识别领域，成对约束是一种比标签信息更一般的先验信息。基于成对 约束的半监督降维算法也越来越受人关注。然而它们很少利用成对约束关系的传 递性和排斥性。针对这些不足，本文便是立足于约束关系传递性和排斥性，根据 数据结构信息的不同，提出了两种不同的算法：整体保持的成对约束降维算法和 局部保持的成对约束降维算法。 全文一共分为五章，各章节具体安排如下： 第一章介绍了半监督学习算法的研究背景及意义，分析了国内外研究进展及 现状，并概述了本文所取得的主要研究成果和论文的内容安排。 第二章介绍特征降维和模式分类的基础知识，以及常用的降维和分类算法。 第三章着重介绍了高斯过程隐变量模型算法，针对其不足，提出了一种基于 局部保持的隐变量模型算法。该算法为高斯过程隐变量模型和局部保 持映射算法的结合，同时给出了实验结果和分析。 第四章着重介绍了基于成对约束的判别成分分析算法，针对其不足提出了基 于整体保持的成对约束降维算法和基于局部保持的成对约束降维算 法，同时给出了实验结果和分析。 第五章对本文的研究内容进行总结，并展望未来的研究工作。 第二章特征降维和模式分类 第二章特征降维和模式分类 2 1 引言 通过第一章的介绍可以知道，在样本数量有限或者相对较少的时候，使用过 多的特征来训练分类器，不论是从计算复杂度还是从分类器的性能来说都是不合 适的。所以，如何使得样本数据从高维观测空间投影到低维空间并能保持数据的 关键信息，就成为了一个很值得研究的课题，这一过程也就是特征降维。 特征选择和特征提取是特征降维的两种主要的方法。特征选择是根据一定的 准则甄选出对模式分类或识别有用的或重要的特征，而抛弃其他的特征，在此过 程中不会产生新的特征；特征提取则是从原来的特征空间变换到一个新的相对低 维的特征空间，在此过程中产生的新特征取代原来的特征。本文所研究的降维方 法主要是属于特征提取范畴的。 2 2 降维的定义 若x = x 。，x ：，h ) cr d 是d 维空间中的一组数据样本，假设其来自本征维 数为d ( d “d ) 的某一数据流形的采样。目标是寻求一个变换函数，将原始高维数 据集合投影到低维空间，从而获得原始数据集合的低维表示。这样也就实现了用 较少的能代表数据本质信息的特征来替代原始的高维特征。这样变换有几个一下 理由【2 】： ( 1 ) 降低了计算复杂度，提高了计算速度； ( 2 ) 特征变换后产生了较好的特征集，提高了分类器的性能； ( 3 ) 能去除数据间的冗余信息； ( 4 ) 用较低维数表示数据，便于可视化数据，更容易揭示数据的结构。 降维的定义便可由以下部分组成： ( 1 ) 高维数据空间q d ，通常是尺d 的某个子集； ( 2 ) 低维表示空间q d ，通常是r d 的某个子集； ( 3 ) 映射函数f ， f ：q djq d x y = ，( x ) ， 称y 为x 的低维表示； 8 无监督与半监督降维算法研究 ( 4 ) 重构映射函数f - 1 ( 此步骤为非必须) ， f 一1 ：q d 专q d ， y x = f 1 ( y ) ， 满足以下的一些限制： a ) d d ，且在不丢失原始数据信息的基础上，尽可能的小； b ) 重构误差应尽可能的小。重构误差的定义为： e r r o r = d ( 吒，) ，# = f - 1 ( f ( 屹) ) f ；l 其中，d ( ，) 为q d 中的距离测度，比如r d 中的欧式距离测度等。 2 3 常见的降维算法 降维是通过构造映射函数，获得高维数的低维表示方法。根据映射函数的不 同，可以把降维方法划分为线性和非线性方法。线性降维方法比如主成分分析方 法( p c a ) 【2 0 1 、线性判别分析( l d a ) 【2 2 1 ，以及局部保持映射( l p p ) 【2 4 】等。这类方法适 合用于处理结构是线性的数据，而且思想比较易懂，计算比较方便，是经常使用 的降维方法。对于一些本身结构就是非线性的数据来说，使用线性降维方法就不 太合适了。为此出现了非线性的降维方法，核方法是使用比较多的一种方法，如 核主成分分析方法等。还有一些基于流形学习的降维方法，比如l l e 2 引、i s m o a p 冽 等，其他的还有基于隐变量模型的降维方法，比如g p l v m t 3 l 】等。 下面简略的介绍一下常用的线性降维方法以及一些常用流形学习方法，基于 隐变量模型的降维方法在论文的第三章会着重介绍。 2 3 1主成分分析方法 主成分分析( p c a ) 是p e a r s o n 在1 9 0 1 年研究回归分析时提出的，h o t e l l i n g 于 1 9 3 3 年将此概念推广到了随机变量。主成分分析是最通用的线性特征降维方法之 一，它是一种统计学方法，在信号处理、模式识别、数字图像处理等领域已经得 到了广泛的应用。 主成分分析方法基本思想是提取出原始空间数据中的主要特征( 主元) ，减少 数据冗余，使得数据在一个低维的特征空间里被处理，同时保持原始数据的绝大 部分的信息，从而解决数据空间维数过高的瓶颈问题。p c a 算法可以从两个不同 的角度进行定义。方面，p c a 可定义成数据在低维线性空间或主子空间( p r i n c i p a l 第二章特征降维和模式分类 9 s u b s p a c e ) j ：f l 向 e 交投影，使得投影后的数据的方差最大。另一方面，在文献【4 1 】 中它被定义成一个线性投影，使得平均投影损失，即数据点和其投影之间的均值 平方距离最小化，也就是使得数据在重构时候的误差最小。主成分分析的最终目 的就是用较少量的特征对样本进行描述，降低特征空间的维数，同时又保留所需 要的识别信息。 这里从最大化投影数据的方差这个角度来考虑。假设投影后的数据维数为 d ( d 1 时，设前d 个最大的特征值按逆序排列为 九允：九0 ，相应的特征向量依次为w l ，w 2 ，w d ，它们组成了投影矩阵 形，即w = w 1 ，w 2 ，w d 。 这样降维的过程可以表示为：x 。专y ，= w7 x ，。 但是需要注意的是，l d a 还存在一些问题： ( 1 ) 受到类间散度矩阵秩的限制，l d a 最多只能得到c 一1 个投影特征向量， 这在许多情况下是不够的【1 9 】； 无监督与半监督降维算法研究 ( 2 ) 小样本问题，即著名的3 s ( s m a l ls a m p l es i z e ) 问题( 人脸识别1 9 1 1 1 0 中表现较 为显著1 。 2 33 局部线性嵌入 流形学习算法是近几年来发展起来的一类降维方法。由于直接对分布在高维 空m 中的数据进行分析是比较困难的，学习数据集台分布的流形有助于发现高维 数据集分布的内在规律性及数据可视化。局部线性嵌f t ) i s ：法( l l e ) ”便是一种典型 的流形学习算法，是由r o w e i s 和s a u l1 ：2 0 0 0 年提出的。它的提出极大的丰富了 对降维的认识，引起了人们广泛的注意。虽然其名字中带有“线性”，但其事实上 是l l e 一种非线性降维方法，它主要利用局部的线性来逼近全局的非线性，保持 局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整 体的几何性质。 根据泰勒定理，如果一个函数可微( 即可导) ，则该函数具有良好的局部线性 性质，即该函数的每个点的微小邻域总是可以用线性模型米近似描述。同样地， 对任意光滑流形i l i i 言，它的微小局部在一定程度上也应该具有线性的特征。只要 能够清晰的描述这一局部线性特征那么就在一定程度l 抓住了数据流形的根本 所在。l l e 便是基于数据流形的局部线性性质的一种非线性降维方法。图2 2 为 l l e 算法实例图i “j 。其中，( a ) 是二维流形，f b ) 是采样的样本点( 三维) ，( c ) 是经 l l e 降维后的样本点。 彦旁 i ( 却( b )( c ) 圈2 2l l e 算法实例 从图2 2 中( c 】的颜色可以看出，经过l l e 降维后的数据很好的保持了原始数 据的邻域结构。 可以用数学的语言来描述局部线性性质一共包括两部分。第一部分是数据 集的局部邻域的描述。可以选撵多种方式，比如k 近邻域，6 | j 域等。l l e 方法 选择了世一近邻域。第二部分是局部邻域的线性描述，也就是要寻求r 邻域内的点 x 加j ，j * 与点，之间的线性表示关系。 l l e 算法的基本思想是假设采样数槲所在的低维流形在局部是线性的，即每 第二章特征降维和模式分类 个采样点可以用它的近邻点线性表示。在低维空间中保持每个邻域中的权值不变， 即假设嵌入映射在局部是线性的条件下，最小化重构误差。 它首先寻找数据点x ，的k 一近邻域；然后计算该数据点的局部重构权值矩阵 既；最后由局部重构权值矩阵及其近邻数据点计算低维输出向量y ，。其具体算法 步骤如下： ( 1 ) 用欧式距离找到每个数据点t 的k 近邻域的数据点，其组成的集合可用 n ( x ，) 来表示。每个数据点的重构误差用成本函数t ( w ) 来衡量，这是一个 带约束的最小二乘问题，即 岬，辞一_ 藐，讨， p ( 2 ) 确定权值矩阵 式( 2 1 1 ) 中的权值说明第个数据点对重构第i 个数据点的权值贡献。为了 得到合适的权值，需要两个限制条件： a 每个数据点只能通过它的足近邻域数据点来构造，并且当某个数据点不属 于所重构数据点的k 一近邻域时，形，= 0 ； b 权值矩阵每一行的所有元素之和等于1 ，即y 彬，= 1 ； _ jv ( 3 ) 计算低维流形 l l e 算法假定在观测空间中获得的k 一邻域和线性表示x ，的权重系数彬，在嵌 入低维空间中应该最大程度的保留，因此重构出来的y ，应该能满足最小化函数 形，辞一勺藐，“， p 其中，y = ( y l ，y 2 ，y ，) 。 优化式( 2 1 2 ) 便转化为如下特征值问题 r = a r g m i n 妒( y ) = 鹕唧n 喜一一蒹，乃j 1 2 。2 一。3 ， = a r g 哪n i i ( i - w ) r l l 2 = a r g 吨n t r ( y 1 ( ，一形) 1 ( i - w ) y ) 其中，表示单位矩阵，表示权重矩阵，护( ) 表示矩阵的迹。 最优解y 。是矩阵( ，一) r ( ，一形) 最小的第d + 1 个到最小的第二个特征值对应 的特征向量所组成的矩阵的转置，因为最小特征值是0 。图2 3 为l l e 算法的示意 图【2 8 1 。 1 4 无监督与半监督降维算法研究 。0 ! 竺 o 、 x 。 、 oo 2 利用线性权值重构 。 二， ，oo ， ， 3 映射到低维嵌入空问 图2 3l l e 算法示意图 l l e 算法有利于找到嵌入在高维数据空间的低维光滑流形，克服了p c a 等方 法在降维过程中可能破坏邻域节点的拓扑关系的缺点；同时它能够很好地发现高 维数据中的低维嵌入流形结构，并且保持了其原有的拓扑结构，具有发现数据集 的内在规律性和数据的分布形式的优点；还具有旋转、缩放、平移不变性等特点。 但是l l e 算法也存在着一些不足，比如对样本中的噪音很敏感，而且对于未知样 本的映射需要重新计算；要求所学习的流形只能是非闭合的，并且在局部是线性 的。 2 3 4 局部保持映射 由于常用的线性降维方法无法揭示数据的非线性结构，而上面提到的l l e 算 法处理未知样本时候需要重新计算。为了解决这些问题，x h e 等人在拉普拉斯映 射方法【3 0 】的基础上提出了一种局部保持映射方法( l p p ) 【2 4 1 。该方法不仅具有保持数 据集非线性结构的特点，而且具有了线性方法计算方便、快捷的优点，最主要的 是它提供了一个从高维观测空间到低维嵌入空间的线性映射函数。从而局部保持 映射算法要优于一般的线性降维方法，并且还具有高维数据内蕴特征或非线性结 构的自动发现功能。 l p p 算法的基本思想是寻找这样的投影方向：在原始数据空间相距很近的样 本经过投影降维后，在低维空间依然相距很近；在原始数据空间相距较远的样本 经投影降维后，依然相距较远。具体实现步骤如下：一 第二章特征降维和模式分类 1 5 ( 1 ) 为样本点构建邻接图g 。如果两个样本点相距很近，它们之间就用一条边 连接起来。构建的方法有两种： a 七一邻域法。如果t 是x 的七一近邻域或者x 是x ，的| j - 近邻域，则t 和x ，之 间用一条边连接起来。 b s - 邻域法。如果忙- - x j i l 2 g ，贝, t j x ，和x ，之间用一条边连接起来。 ( 2 ) 选择权重。权重矩阵形是一个n x n 的稀疏矩阵，其元素便是连接t 和 x 边的权重系数。构造的方法有下面两种： a 若节点x ，和x 之间有边连接，则= 1 ，否则，= 0 ； b 若节她鸭之脯边蛾峨一p f 一毕 ，酬，一o o ( 3 ) 计算广义特征值和广义特征向量 x l x7 a = x d x r a ( 2 - 1 4 ) 其中，d 是对角矩阵，d 。是权重矩阵形第纤于或第f 列的和，即d l ；= ， l = d w 是拉普拉斯矩阵，x = x 1x ：，x 】是样本点组成的矩阵。 假设上式的前d 个最小特征值依次为九 a ： 1 时，设前d 个最小的特征值按逆序排列为 a ：a d ，相 应的特征向量依次为a i 口2 ，乃，它们组成了投影矩阵w ，即a = a i 口：，哟】。 这样，降维的过程可以表示为：x t - 9 , y i = a7 五。 l p p 算法与前面介绍的p c a 、l d a 、l l e 比较有如下优点： ( 1 ) p c a 是获取样本数据的全局信息， 保持了样本数据的局部流形结构。 息往往比全局结构信息更重要。 l d a 获取样本数据的判别信息，而l p p 而在很多实际应用中，局部流形结构信 ( 2 ) 虽然l p p 和l l e 都具有保持局部结构的特性，但是l p p