（模式识别与智能系统专业论文）基于图的半监督学习和维数约简方法及其应用研究.pdf

摘要 摘要 半监督学习和维数约简已经成为当前机器学习领域的研究热点。半监督学习 研究的目的是在整个数据集中只有一部分样本有标记的情况下，如何对数据进行 分类。本文主要研究的是基于图的半监督学习方法与应用。维数约简是在尽可能 多地保持数据集结构的前提下，将数据集转换成一个新的数据集，新数据集的维 数是原始数据集的本征维数。本文对基于图的半监督学习和维数约简方法与应用 进行了系统的研究，具体来说，全文的主要工作概括如下： ( 1 ) 提出了一种新的多步骤降维方法对基因表达谱数据进行降维。首先采用 秩和检验方法来进行差异表达的基因选择，然后将排在前面的一定数量的基因再 进行离散余弦变换，并采用主成分分析对变换后的系数进行主成分提取。我们首 先将基于图的半监督方法引入到肿瘤分类中，采用基于图的半监督学习算法对抽 取的主成分特征进行分类性能评估。 ( 2 ) 针对基于图的半监督学习方法提出了一种新的自适应权值学习方法。传 统的基于图的半监督学习算法大都采用高斯函数来计算图的边权。我们提出一种 新颖的针对基于图的半监督学习方法的边权设计方法。该方法添加了标签信息， 并且采用测地距离而不是欧氏距离来计算两个样本点之间的距离。此外，我们还 添加了类的先验信息，并针对基于局部和全局一致性的学习方法来改进边权。实 验结果表明，我们所提出的方法要优于原算法。 ( 3 ) 提出了一种基于局部保持投影的监督特征提取方法，即局部保持判别投 影算法。局部保持投影c l p p ) 没有加入判别信息，仅仅考虑局部信息。我们将类 内散度矩阵和类问散度矩阵加入到l p p 的目标函数中，从而提出局部保持判别 投影( l p d p ) 方法。该方法的优点是能够最大化类间距离和最小化类内距离，同时 保持l p p 的局部保持特性。l p d p 可被看作是一种组合了流形准则和f i s h e r 准则 的新方法。因此，与l p p 相比，l p d p 能够成功地找到具有更好判别性能的子空 间，因而更适合于做分类，从而能有效地提高识别率。 ( 4 ) 提出了基于谱回归的判别分析( s p e c t r a lr e g r e s s i o nd i s c r i m i n a n t a n a l y s i s ， s r d a ) 和基于谱回归的核化判别分析( s p e c t r a lr e g r e s s i o nk e r n e ld i s c r i m i n a n t 摘要 a n a l y s i s ，s r k d a ) 的正则化参数估计方法。s r d a 的正则化参数的估计在以往的 研究中没有得到很好的解决。我们基于扰动的线性判别分析( p e r t u r b a t i o nl i n e a r d i s c r i m i n a n ta n a l y s i s ，p l d a ) 准则提出一种新的方法，来估计s r d a 的正则化参 数。在另一方面，s r k d a 的正则化参数估计在以前的研究中也没有解决。我们 提出两种方法来估计s r k d a 的正则化参数，在不同数据集上的实验结果显示我 们的方法是有效可行的。 关键词：基于图的半监督学习；维数约简；多步骤降维；局部保持投影：基于谱 回归的判别分析 a b s t r a c t a b s t r a c t r e c e n t l y , s e m i s u p e r v i s e dl e a r n i n ga n dd i m e n s i o n a l i t yr e d u c t i o nh a v eb e c o m e h o tt o p i c si nt h ef i e l do fm a c h i n el e a r n i n g 1 1 1 eg o a lo fs e m i s u p e r v i s e dl e a r n i n gi st o l e a r nf r o m p a r t i a l l y l a b e l e dd a t a i nt h i st h e s i s ，i f o c u s e do n g r a p h b a s e d s e m i s u p e r v i s e dl e a m i n g d i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e sc a nt r a n s f o r md a t a s e t xw i t hd i m e n s i o n a l i t ydi n t oan e wd a t a s e tyw i t hd i m e n s i o n a l i t yd ，w h i l er e t a i n i n g t h eg e o m e t r yo ft h ed a t aa sm u c ha sp o s s i b l e t h ed i m e n s i o n a l i t yo f t h en e wd a t as e t , i e di st h ei n t r i n s i cd i m e n s i o n a l i t y im a k eat h r o u g hs t u d yo ng r a p h b a s e d s e m i s u p e r v i s e dl e a r n i n ga n dd 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 m o r ec o n c r e t e l y , t h e m a i n w o r kf o rt h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) b o t hs u p e r v i s e dm e t h o d sa n du n s u p e r v i s e dm e t h o d sh a v eb e e nw i d e l yu s e d t os o l v et h et u m o rc l a s s i f i c a t i o np r o b l e mb a s e do ng e n ee x p r e s s i o np r o f i l e s t h i s p a p e ri n t r o d u c e sas e m i s u p e r v i s e dg r a p h b a s e dm e t h o d f o rt u m o rc l a s s i f i c a t i o n f e a t u r ee x t r a c t i o np l a y sak e yr o l e i nt u m o rc l a s s i f i c a t i o nb a s e do ng e n ee x p r e s s i o n p r o f i l e s ，a n dc a ng r e a t l yi m p r o v et h ep e r f o r m a n c eo fa c l a s s i f i e r i nt h i sp a p e rw e p r o p o s e dan o v e lf e a t u r ee x t r a c t i o nm e t h o d f o re x t r a c t i n gt u m o r - r e l a t e df e a t u r e s f i r s t t h ew i l c o x o nr a n k s u mt e s tw a su s e df o rg e n es e l e c t i o n t h e ng e n er a n k i n ga n d d i s c r e t ec o s i n et r a n s f o r ma r ec o m b i n e dw i t hp r i n c i p a lc o m p o n e n ta n a l y s i sf o rf e a t u r e e x t r a c t i o n f i n a l l y , t h ep e r f o r m a n c ew a se v a l u a t e db ys e m i - s u p e r v i s e dl e a r n i n g a l g o r i t h m s ( 2 ) am o d i f i e dv e r s i o nf o rs e m i s u p e r v i s e dl e a r n i n ga l g o r i t h mw i t hl o c a la n d g l o b a lc o n s i s t e n c yw a sp r o p o s e di n t h i sp a p e r t h en e wm e t h o da d d st h el a b e l i n f o r m a t i o n ，a n da d o p t st h eg e o d e s i cd i s t a n c er a t h e rt h a ne u c l i d e a nd i s t a n c ea st h e m e a s u r eo ft h ed i f f e r e n c eb e t w e e nt w od a t ap o i n t sw h e nc o n d u c t i n gc a l c u l a t i o n i n a d d i t i o n ，w ea d dc l a s sp r i o rk n o w l e d g ei n t ot h ec o s tf u n c t i o n i tw a s f o u n dt h a tt h e e f f e c to fc l a s sp r i o rk n o w l e d g ew a sd i f f e r e n tb e t w e e nu n d e rh i g hl a b e lr a t ea n dl o w l a b e lr a t e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ec h a n g e sa t t a i nt h es a t i s f y i n g c l a s s i f i c a t i o np e r f o r m a n c eb e t t e rt h a nt h eo r i g i n a la l g o r i t h m s ( 3 ) an e ws u b s p a c el e a r n i n ga l g o r i t h mc a l l e dl o c a l i t yp r e s e r v i n gd i s c r i m i n a n t p r o j e c t i o n s ( l p d p ) w a sp r o p o s e db ya d d i n gt h em a x i m u mm a r g i nc r i t e r i o n ( m m c ) i n t ot h eo b j e c t i v ef u n c t i o no fl 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 p d pr e m a i n st h e l o c a l i t yp r e s e r v i n gc h a r a c t e r i s t i co fl p pa n du t i l i z e s l a b e li n f o r m a t i o ni nm m c ， m a b s t r a c t w h i c hc a nm a x i m i z et h eb e t w e e n c l a s sd i s t a n e ea n dm i n i m i z et h ew i t h i n c l a s s d i s t a n c e t h u so u rp r o p o s e dl p d pi san e wm e t h o dt h a tc o m b i n e sm a n i f o l dc r i t e r i o n a n df i s h e rc r i t e r i o na n dh a sm o r ed i s c r i m i n a n tp o w e ra n dm o r es u i t a b l ef o r r e c o g n i t i o nt a s k st h a nl p pw h i c hc o n s i d e r so n l yt h el o c a li n f o r m a t i o nf o rc l u s t e r i n g o rc l a s s i f i c a t i o nt a s k s m o r e o v e r , t w ok i n d so ft e n s o r i z e d ( m u l t i l i n e a r ) f o r m so fl p d p a r ea l s od e r i v e di nt h i sp a p e r o n ei si t e r a t i v ew h i l et h eo t h e ri sn o n i t e r a t i v e f i n a l l y , t h ep r o p o s e dl p d pm e t h o di sa p p l i e dt of a c ea n dp a l m p r i n tb i o m e t r i c sa n di s e x a m i n e du s i n gt h ey a l e ，o i uf a c e i m a g ed a t a b a s e sa n dt h ep o l y up a l m p r i n t d a t a b a s e e x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ep r o p o s e dl p d pa n d d e m o n s t r a t et h a tl p d pi sag o o dc h o i c ef o rr e a l w o r l db i o m e t r i c sa p p l i c a t i o n s ( 4 ) s p e c t r a lr e g r e s s i o nd i s c r i m i n a n ta n a l y s i s ( s r d a ) a n di t sk e r n e lv e r s i o n s r k d aa r ei m p o r t a n ts u b s p a c el e a r n i n gm e t h o d sp r o p o s e dr e c e n t l y , b o t ho fw h i c h h a v eaf r e ep a r a m e t e r , i e ，t h er e g u l a r i z a t i o np a r a m e t e r h o w e v e r , h o wt os e tt h i s p a r a m e t e ra u t o m a t i c a l l yh a sn o tb e e nw e l ls o l v e db e f o r e i ns r d a ，t h i sr e g u l a r i z a t i o n p a r a m e t e rw a so n l ys e ta sac o n s t a n t , w h i c hi so b v i o u s l ys u b o p t i m a l i nt h i sp a p e r , w e d e v e l o p e dan e wa l g o r i t h mt oa u t o m a t i c a l l ye s t i m a t et h er e g u l a r i z a t i o np a r a m e t e ro f s r d ab a s e do nt h ep e r t u r b a t i o nl i n e a rd i s c r i m i n a n t a n a l y s i s ( p l d a ) w ea l s o p r o p o s e dt w om e t h o d sf o rr e g u l a r i z a t i o np a r a m e t e re s t i m a t i o no fs r k d a o n ei s d e r i v e df r o mt h em e t h o do fo p t i m a lr e g u l a r i z a t i o np a r a m e t e re s t i m a t i o nf o rs r d a ( o r - s r d a ) t h eo t h e ri st o u t i l i z et h ek e r n e lv e r s i o no fp l d a e x p e r i m e n t so n d i f f e r e n td a t as 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 sa n d f e a s i s b l i t yo fp r o p o s e dm e t h o d s k e yw o r d s ：g r a p h - b a s e ds e m i s u p e r v i s e dl e a r n i n g ；d i m e n s i o n a l i t yr e d u c t i o n ； m u l t i s t e pd i m e n s i o n a l i t yr e d u c t i o 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 s ；s p e c t r a l r e g r e s s i o nd i s c r i m i n a n ta n a l y s i s i v 表格日录 插图目录 图1 1 在双月数据上的分类( a ) 有两个标记样本的双月数据；( b ) s v m 采用r b f 核的分 类结果；( c ) k n n 在k - - 1 的分类结果；( d ) l g c 的分类结果( 该图来自文献( z h o uc ta 1 ， 2 0 0 4 ) ) 5 图1 2 在双月数据上采用l g c 分类的结果6 图1 3 在所有数据的演绎结果7 图1 4 降维的图示，一个给定的系统仅仅当向量的维数不超过给定的维数才有效，因 此高维数据在进入系统时必须首先降维8 图1 5图嵌入和线性化、核化和张量化：一个统一的降维框架。最上面一行是图嵌入 类型，中间一行是相应的目标函数，第三行列出了典型算法( 该图来自( y a nc ta 1 ， 2 0 0 7 b ) ) 9 图1 6 有监督学习、无监督学习和半监督学习的区别和联系( 该图来自( 王飞，2 0 0 8 ) 的 图1 1 ) 1 0 图1 7 有监督学习和半监督学习在t o yd a t a 上的分类比较，半监督学习找到了与输入 密度更加光滑的分类( 该图来自( f e r g u sc ta 1 ，2 0 0 9 ) 的图1 ) l o 图1 8 ( a ) 中心点有五个近邻，相同颜色和形状的点属于同一类；( b ) 类内图瓯连接了 有相同标号的近邻点；( c ) 类间图g 连接了有不同标号的近邻点；( d ) 在l s d a 后 不同类的边沿被最大化( 该图来自文献( c a ie ta 1 ，2 0 0 7 9 ) ) 1 3 图1 9m f a 本质图和惩罚图的近邻关系，注意到左图，每个样本仅与同类且权值较 大的点相连( 该图来自文献( y a ne ta 1 ，2 0 0 7 b ) ) 1 4 图1 1 0 最大f i s h e r 分析步骤1 5 图1 1 l在一个人造数据集上l d a 和m f a 最优投影的比较，注意到实线和虚线分别 代表投影方向和最优分类超平面( 该图来自文献( y a hc ta 1 ，2 0 0 7 b ) ) 1 5 图1 1 2p c a 和l d a 的比较( 该图来自文献( b e l h u m e u rc ta 1 ，1 9 9 7 ) ) 1 6 图1 1 3 拉普拉斯特征映射的步骤1 7 图1 1 4 第一个图和第三个图是p c a 的结果，第二个和第四个是l p p 的结果。两个线 分别代表两个基，第一个基用长线表示，第二个基用短线表示。显然，与p c a 相 比，l p p 对离群点( o u t l i e r s ) 不是很敏感，更具有判别能力( 该图来自文献( h ea n d n i y o g i 2 0 0 4 ) ) 18 图1 1 5 手写体数字( o 到9 ) 映射n - - 维窄间，左、中和右分别代表l e 、l p p 和p c a 的映射结果( 该图来自文献( h ea n dn i y o g i ，2 0 0 4 ) ) 。1 8 图1 1 6 使用l p p 对人脸数据集的二维表达。典型人脸显示在数据点的旁边。可以看 到，面部表情和人脸朝向改变得很光滑( 该图来自文献( h e a n d n i y o g i ，2 0 0 4 ) ) 。1 9 图1 1 7 半监督谱回归算法步骤2 0 图1 1 8 降维从线性与否分类2 1 图1 1 9 降维从如何利用局部性分类2 l 图1 2 0 在数据集上建立图结构的一个半监督学习的例子( 该图来自( z h ue ta 1 ，2 0 0 3 a ) ) ：! z i 图1 2 1p c a 和l d a 的邻接图( a ) p c a 中的本质图和约束图( b ) l o a 中的本质图和约束 图( 该图来自( y a ne tai 2 0 0 y b ) ) 2 5 表格卜j 录 图2 1算法伪代码一3 5 图2 2 基因选择对l g c 和l g c n o r m 分类效果的影响。w i t h ：有基冈选择：w i t h o u t ： 没有基因选择3 6 图2 3p c a 对l g c 和l g c n o r m 分类效果的影响3 6 图2 4 在白血病数据集上基因p 值的分布。3 7 图2 5 一个白血病样本的d c t 变换3 8 图2 6 不同分类器的准确率4 l 图2 7 准确率随参数口的变化曲线4 2 图2 8 准确率随参数盯的变化曲线4 2 图2 9 准确率随有标记样本数量的变化曲线4 3 图3 i流形结构和测地距离。4 7 图3 2 在h y p o t h y r o i d 数据集上，不同的k 和标记率时的错误率5 3 图3 3在s i c k 数据集上，不同的k 和标记率时的错误率5 3 图3 4 在不同的k 和标记率时的性能比较5 5 图4 1 两类二维样本和投影轴5 8 图4 2y a l e 人脸数据库的样本图像6 6 图4 3y a l e 人脸数据库的前十e i g e n f a c e s ，f i s h e r f a c e s 和l p d p f a c e s 6 7 图4 4y a l e 人脸数据上识别率随维数变化曲线6 8 图4 5 在o r l 人脸数据库上一个人的十幅经过裁剪和调整大小后的图像6 9 图4 6o i 也人脸数据上识别率随维数变化曲线7 l 图4 7 在p o l y u 掌纹数据库上一些典型图像。7 l 图4 8 在p o l y u 掌纹数据库上识别率与维数变化曲线图。7 2 图5 1s r d a 和r l d a 的关系7 9 图5 2 s r d a 的模型选择，曲线代表s r d a 关于+ 1 ) 的识别率变化，水平线代表 我们的方法p f 。s r d a 的性能8 6 图5 3( a ) 针对t l 、t 2 和t 3 ，b e s t s r k d a 、r p e - s r k d a 和k p l d a - s r k d a 在i s o l e t 上的性能比较；( b ) 针对t 1 、t 2 和t 3 ，在i s o l e t 上识别率和随机采样率的变化曲 线8 8 图5 4 ( a ) 随着训练样本数变化，b e s t - s r k d a 、r p e s r k d a 和k p l d a s r k d a 在p i e 上的性能比较；c o ) 随着训练样本数变化，在p i e 上的识别率和随机采样率的变化 曲线8 9 图5 5 ( a ) 随着训练样本数变化，b e s t s r k d a 、 r p e s r k d a 和k p l d a s r k d a 在 u s p s 上的性能比较；( b ) 随着训练样本数变化，在u s p s 上的识别率和随机采样率 的变化曲线。9 0 图5 6 在i s o l e t 上计算时间( 秒) 9 1 图5 7 在c m up i e 上计算时间( 秒) 。9 2 图5 8 在u s p s 上计算时间( 秒) 9 3 v m 表格目录 表格目录 表2 1四个两类肿瘤数据集的总结3 6 表2 2 结肠癌数据的准确率3 9 表2 3白血病数据的准确率3 9 表2 4 肝癌数据的准确率3 9 表2 5 高分级胶质瘤数据的准确率3 9 表2 6 在四个数据集上的实验结果总结，每个数据集的最佳结果以粗体突出展示4 0 表2 7 在四个数据集上不同分类器的准确性，每个数据集的最佳结果以粗体突出展示 4 1 表3 1 在实验中使用的数据集。5 0 表3 2s l g c ，s l g c c m n ，l g c ，h a r m o n i c 和h a r m o n i c - c m n 在u c i 数据集上1 0 标 记率的性能。5 l 表3 3s l g c ，s l g c c m n ，l g c ，h a r m o n i c 和h a r m o n i c c m n 在u c i 数据集上3 0 标 记率的性能5 1 表3 4s l g c ，s l g c c m n ，l g c ，h a r m o n i c 和h a r m o n i c c m n 在u c i 数据集上5 0 标 记率的性能5 l 表3 5s l g c ，s l g c c m n ，l g c ，h a r m o n i c 和h a r m o n i c c m n 在u c i 数据集上7 0 标 记率的性能5l 表3 6s l g c ，s l g c c m n ，l g c ，h a r m o n i c 和h a r m o n i c c m n 在u c i 数据集上9 0 标 记率的性能5 l 表3 7 在s i c k 数据集上，标记率分别为1 0 ，3 0 ，5 0 和7 0 时h a r m o n i c c m n 十 次独立运行的错误率5 2 表3 8 标记率为1 0 时的错误率和方差5 4 表3 9 标记率为3 0 时的错误率和方差。5 4 表3 1 0 标记率为5 0 时的错误率和方差5 4 表3 1 1 标记率为7 0 时的错误率和方差5 4 表3 1 2 标记率为9 0 时的错误率和方差5 4 表4 1l p d p 算法步骤6 l 表4 2t l p d p 算法步骤6 3 表4 3n t l p d p 算法步骤。6 5 表4 4 在y a l e 人脸数据库上的二十次运行的最大平均识别率，标准偏差和维数( 显示 在括号中) 6 7 表4 5 在0 r l 人脸数据库上的二十次运行的最大平均识别率，标准偏差和维数( 显示 在括号中) 6 9 表4 6 在p o l y u 掌纹数据库上最大识别率和相应的维数7 2 表4 7 在p o l y u 掌纹数据库，y a l e 和0 r l 人脸数据库随口变化最大平均识别率，方差 和相应的维数7 3 表5 1 本章使用的一些符号。7 7 表5 2k p l d a s r k d a 的伪代码8 3 i x 表格日录 表5 3 表5 4 表5 5 ：表5 6 表5 7 表5 8 表5 9 表5 1 0 表5 1 l 表5 1 2 表5 1 3 表5 1 4 表5 1 5 表5 1 6 在p i e 上的分类准确率( 均值标准方蔗) 8 5 在i s o l e t 上的分类准确率( 均值标准方差) 8 5 在m n i s t 上的分类准确率( 均值标准方差) 8 5 在2 0n e w s g r o u p s 上的分类准确率( 均值标准方差) 8 6 在i s o l e t 上z - s r k d a ，o - s r k d a ，r p e - s r k d a 和k p l d a - s r k d a 的识别率8 7 在i s o l e t 上根据采样率吒变化k p l d a s r k d a 的识别率，气定义在( 4 3 ) 8 7 在p i e 上z - s r k d a ，o - s r k d a ，r p e - s r k d a 和k p l d a - s r k d a 的识别率8 8 在p i e 上根据采样率变化k p l d a - s r k d a 的识别率，r k 定义在( 4 3 ) 8 8 在p i e 上r p e s r k d a 和k p l d a _ s r k d a 估计的正贝0 化参数8 8 在u s p s 上z - s r k d a ，o - s r k d a ，r p e s r k d a 和k p l d a - s r k d a 的识别率9 0 在u s p s 上根据采样率吒变化k p l d a - s r k d a 的识别率，定义在( 4 3 ) 9 0 在i s o l e t 上计算时间( 秒) 9 1 在c m up i e 上计算时间( 秒) 9 2 在u s p s 上计算时间( 秒) 9 2 x 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除 已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成 果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。 作者签名：丝签字日期：兰! ：生! 望! ! 兰 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位 论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件 和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸 质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 导师签名： 签字日期： 第1 章绪论 第1 章绪论 1 1 基于图的半监督学习 半监督学习，又称为从有标记和无标记数据中学习，是机器学习中的一个研 究热点( l i ue ta 1 ，2 0 0 9 ，f e r g u se ta 1 ，2 0 0 9 ，c u l pa n dm i c h a i l i d i s ，2 0 0 9 ，z h a n ge ta 1 ， 2 0 0 7 a ，c a ie ta 1 ，2 0 0 7 c ，y a na n dd o m e n i c o n i ，2 0 0 6 ，d ue ta 1 ，2 0 0 5 ，z h o ua n d s c h o l k o p f , 2 0 0 4 ，t i a ne ta 1 ，2 0 0 4 ，x z h u ，s e e g e r ) 。半监督学习又分为半监督分类， 半监督聚类和半监督回归。在本文中我们只研究半监督分类，它是分类的一种特 殊形式。传统的分类器仅仅使用标记数据( 特征标记对) 来训练。获取有标记数 据通常很难，代价很高且耗时，因为需要有经验的人来标注。同时，无标记数据 也许相对容易获得。例如，文本分类，一个人很容易获得大量文本( 如通过抓网 页) ，仅仅少部分已经手工分类。一般来说，很少有使用无标记数据来进行分类 的情况。半监督学习正是解决这个问题，通过无标记样本和有标记样本一起构建 更好的分类器。因为半监督学习需要很少的人力，给出了很高的准确率，在理论 和实践中已经引起了广泛的兴趣。 半监督分类方法很多，包括：产生式模型( c a s t e l l ia n dc o v e r , 19 9 5 ，n i g a me t a 1 ，2 0 0 0 ) 、自学习( s e l f - t r a i n i n g ) ( a s h o k , 19 7 0 ) 、协同训练( c o - 仃a i n i n g ) ( l i ue ta 1 ，2 0 0 9 ， c u l pa n dm i c h a i l i d i s ，2 0 0 9 ) 和基于图的方法( h u a n ga n dk e c m a n ，2 0 0 4 ，s c h e n k e re t a 1 ，2 0 0 4 ，s z u m m e ra n dj a a k k o l a ，2 0 0 2 ，w a n ga n dz h a n g , ，2 0 0 8 ，z h o ue ta 1 ，2 0 0 4 , ， z h ue ta 1 。2 0 0 3 a ) 等等。本文集中于基于图的方法，这些方法由于其扎实的数学背 景，与核方法的关系，稀疏特性，模型可视化，在许多领域，例如文本分类( z h o u e ta 1 ，2 0 0 4 ，h u a n ga n dk e c m a n , ，2 0 0 4 ) 、数字识吴j l j ( z h o ue ta 1 ，2 0 0 4 ，z h ue ta 1 ， 2 0 0 3 a ) 、音素分类( b e l k i na n dn i y o g i ，2 0 0 4 ) 和人脸识另u ( d ue ta 1 ，2 0 0 5 ) 等领域取得 了很好的结果。 基于图的半监督方法定义了一个图，节点是数据集中的有标记和无标记数 据。边的权重反应了样本的相似性。许多基于图的方法可被看作估计图上的一个 函数厂，希望厂同时满足下面两点：应该与标记数据上的给定的标记儿接近；应 该在整个图上光滑。这可被表示成一个正则化框架，第一项是一个损失函数，第 二项是一个正则项，很多基于图的方法都是彼此类似的，它们的区别在于选择不 同的损失函数和正则项。我们认为构造一个好的图比选择方法更重要。我们后面 将会提到，如何构造一个好的图还是一个公开问题。 半监督学习的一般数学形式：给定数据集x = ，而，而，而，) 和相应的标 第1 章绪论 记集c = l 一，c ，假设前，个样本的标记“，儿，m c ，而其余的无标记。半监督 学习的目标是预测无标记样本的标记。下面我们将介绍几利一有代表性的基于图的 半监督学习方法。 1 1 1 基于高斯域和调和函数的半监督学习 z h u 等( z h ue ta 1 ，2 0 0 3 a ) 提出基于高斯域和调和函数的半监督学习 ( s e m i - s u p e r v i s e dl e a r n i n gu s i n g g a u s s i a nf i e l d sa n dh a r m o n i cf u n c t i o n s ， h a r m o n i c ) 方法。 给定数据集x = ，屯，而，而舻， 和相应的标记集c = 1 ，一，c ) ，假设前，个样 本的标记饥，耽，乃 ec ，而其余的无标记。 首先形成相似矩阵矽定义如下： 抖p p _ 必： 州 n 。， 1 0j ：， 生成对角矩阵d ，d 的第i 行第i 列元素等于矩阵w 的第i 行的行和。 h a r m o n i c 的能量函数定义如下： e ( ) = 去( z 一乃) 2 s t z = 咒，i = 1 ，2 ，1 ( 1 2 ) z ，m 分别代表第价样本的预测标记和实际标记。 h a r m o n i c 整体思路围绕a f = 0 f 展开，a f 可以理解为一阶微分，= d 一形 称为差分矩阵( 组合拉普拉斯) ，其可