（计算数学专业论文）基于流形的半监督分类方法研究.pdf

浙江大学博士学位论文 摘要 半监督学 - - o ，特别是关于数据聚类的半监督学习方法，是机器学 - - j 领域近年 来广受关注的研究方向。非线性流形降维和再生核空间是两个非常重要的研究内 容。本文重点研究用于数据聚类的非线性降维方法和基于部分的属类异同信息下的 核( k e r n e l ) 学 - j 方法，及其导出的聚类算法。我们的主要成果分成两部分：基于属 类概率的数据降维和基于点对属类异同概率的k e r n e l 学 - - j 。这两部分互相关联，核 学习方法也可用于数据降维。 一、关于数据聚类的非线性降维方法。 1 我们提出了基于属类概率预估的非线性降维方法p l l e 。其主要特点是将属 类概率向量用于距离函数的构造。这个距离函数，不同于通常的欧几里得距离或流 形测地距离，它既保持了欧几里得距离的部分特性，也具有元素属类的特性。与原 先提出的只适用于部分训练点集的方式相比，这一距离函数适用于整个训练集和 测试集，因而具有整体性。p l l e 结合了经典的( 用于无监督问题的) 非线性降维方 法l l e 的思想，更具有半监督分类的特点。它克服了一般流形学 - - o 算法在处理监督 信息上的缺憾。 2 p l l e 算法的关键部分是属类概率向量的估计。我们进一步提出了预估 属类概率向量的p e 算法。它基于经典的逻辑回归( l d ) 思想。数值实验证明， p l l e - 与p e 结合后得到的p l l e c 算法是一个性能卓越的有监督分类算法。 3 我们将属类概率预估的思想用于拉普拉斯特征映射( l e ) 方法，进行数据 降维，提出了具有属类信息的半监督降维的p l e 算法，这可用于数据聚类。p l e 算 法中所需的属类概率预估，可以采用前述的p e 方法得到，也可以用我们提出的基 于k e r n e l 学习的方法估计。 二、基于部分属类异同信息的核( k e r n e l ) 学习。 1 对于具有部分属类异同信息的数据，现有许多算法是通过寻找最佳线性 投影来完成降维任务的，这类方法的效果对于数据的分布非常敏感。针对这一问 题，我们给出了一种创新性的分类可靠性函数以及概率向量的确定方式。它基于 摘要 由点对约束传播( p c p ) 方法得到的k e r n e l 矩阵。我们将其用于p l e 方法，提出了称 为p c p p l e 的分类算法，及其改进了的结合维数类别数因素的p c p p l e 幸降维方法。 这些算法由于包含了具有分类效果的隐式映射，因此，对于任何形式的数据分布均 可有效完成保持属类异同信息的降维工作，实验表明，p c p - p l e * 要优于一些最新 的基于同样背景的算法。 2 点对约束传播的k e r n e l 学习算法p c p 在应用中具有一定的局限性。我们详细 研究了其特点，发现用由p c p 得到的核矩阵作核形式的k - m e a n s 聚类时，所得分类的 规范共信度值并不随着已知的属类相同信息量的增加而改善。p c p 更依赖于已知属 类异同点对的分布。根据p c p 的弱点，提出了一种具有点对之间属类异同的概率约 束传播的k e r n e l 学习算法p p c p 。在很多情形下，p p c p 可能比p c p 更加有效。更为重 要的是：基于我们提出的属类异同可靠性估计方法，p p c p 可以用于无任何先验的 点对属类异同信息。因而可作为一种无监督的聚类算法，这更有利于实际应用。 3 在可靠性函数的基础上，我们提出了一种主动的k e r n e l 学习算法：a c t i v e p c p 和a c t i v e p p c p 。该算法能够自适应地搜索对分类起消极作用的点对，并对其进 行去除或者松弛约束的处理，进而提升分类效果。此外，我们最新研究的有关自动 扩张约束集合以改进分类的工作也在文中进行了介绍和讨论。 全文由六章组成。第一章为读者阐述了本文课题的研究背景、发展现状以及 文章的主要科研成果。第二章简介流形学习和核方法领域的经典工作。第三章主 要描述了p l l e ，p e ，p l l e c ，p l e 算法。第四章详细介绍了p c p 、k - m e a n s 方法以及 聚类有效性指标n m i ，给出了p c p p l e ，p c p k p c a 和p c p - p l e * 算法。第五章提出 了p p c p ，p c p ( p p c p ) 一k m e a n s ，a c t i v e - p c p ( p p c p ) 以及扩张的p c p ( p p c p ) 算法。第 六章总结了全文的工作，并对后续的研究课题加以展望。 关键词：流形学习半监督学习分类降维核方法 i i i 浙江大学博士学位论文 a b s t r a c t s e m i s u p e r v i s e dl e a r n i n g ，e s p e c i a l l ys e m i - s u p e r v i s e dm e t h o d sf o rc l u s t e r i n g ，i sa p o p u l a ri s s u ei nt h em a c h i n el e a r n i n gf i e l d n o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o nb a s e do n m a n i f o l dl e a r n i n ga n dr e p r o d u c ek e r n e lh i l b e as p a c ea r ea l li m p o r t a n tt o p i c si nt h i sf i e l d t h i st h e s i sc o n c e m sa b o u tn o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o nf o rd a t ac l a s s i f i c a t i o n ，p a i r - w i s ec o n s t r a i n t s - b a s e dk e r n e ll e a r n i n ga n da l s ot h em e t h o do fc l u s t e r i n g t h e r ea r et w o p i e c e so f w o r kw ea d d r e s s ：d i m e n s i o n a l i t yr e d u c t i o nb a s e do nc l a s s p r o b a b i l i t ya n dk e r n e l l e a r n i n gb a s e do np r o b a b i l i s t i cp a i r w i s ec o n s t r a i n t s t h e s et w op a r t sa r ei n t e r p e n e t r a b l e ， a n dk e r n e ll e a r n i n gm e t h o dc a na l s ob eu s e df o rd i m e n s i o n a l i t yr e d u c t i o n 1 n o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o nf o rd a t ac l a s s i f i c a t i o n ( a ) w ep r o p o s ean o v e ln o n l i n e a rd 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 mb a s e do nc l a s s p r o b a b i l i t y t h ea l g o r i t h mc a l l e dp l l ed e s i g n sad i s t a n c em e t r i cf r o m t h ec l a s s - p r o b a b i l i t y d i f f e r e n tf r o me u c l i d e a nd i s t a n c eo rm a n i f o l dg e o d e s i cd i s t a n c e ，t h i sm e t r i ck e e p sn o t o n l y o t h es p e c i a l i t yo fe u c l i d e a nd i s t a n c eb u ta l s ot h ec h a r a c t e ro fe l e m e n t s c l a s sl a b e l s t h u s ， t h i sm e t r i ci sm u c hm o r es u i t a b l ef o rt h ew h o l ed a t as e ta n dt e s t i n gs e tt h a nt h o s ef i t t e dt o t h et r a i n i n gs e to n l y p l l ea b s o r b st h ei d e ao fc l a s s i c a ln o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o n m e t h o dl l e ，a n dh a si t so w ns p e c i a l i t yo fs e m i - s u p e r v i s e dc l a s s i f i c a t i o n i tp e r f e c t l yd e a l s w i t ht h ed i f f i c u l t yt h a ti n t r o d u c i n gs u p e r v i s e di n f o r m a t i o ni n t om a n i f o l dl e a r n i n gm e t h o d s ( b ) t h ep r e d i c t i o no fc l a s s p r o b a b i l i t yi st h ek e yp a r to fp l l e t h et h e s i sp r o p o s e s ap ea l g o r i t h mt oe v a l u a t et h ec l a s s - p r o b a b i l i t yv e c t o r i tc o m e sf r o mt h ei d e ao fl o g i s t i c d i s c r i m i n a n tm e t h o d p l l e c ，w h i c hi sac o m b i n a t i o no fp l l ea n dp e ，i ss h o w na sa l l e f f e c t i v es u p e r v i s e dc l a s s i f i e rt h r o u g hn u m e r i c a le x p e r i m e n t s ( c ) w ep r o p o s eas 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 nm e t h o dc a l l e dp l e p l e i sa c l a s s - p r o b a b i l i t ya l g o r i t h mb a s e d o nl a p l a c i a ne i g e n m a pb ya d o p t i n gt h ei d e ao f c l a s s - p r o b a b i l i t yp r e d i c t i o n t h i sm e t h o dc a nb eu s e df o rd a t ac l u s t e r i n g t h ec l a s s - p r o b a b i l i t y c a nb eo b t a i n e db ye i t h e rp eo rt h ep r e d i c t i o nb a s e do nk e r n e ll e a r n i n gm e t h o d s i v 摘要 2 k e r n e ll e a r n 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 ( a ) m a n yd 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 ss e e kt of i n dt h eb e s tl i n e a rp r o j e c t i o n f o rd a t as e t sw i t hp a i r w i s ec o n s t r a i n t s ，b u tt h e s em e t h o d sa r eh i g h l ys e n s i t i v et ot h ed i s t r i b u t i o no fd a t a t oa d d r e s st h i sp r o b l e m ，an o v e lm e t h o di sp r o p o s e dt od e t e r m i n eap r o b a b i l i t yf u n c t i o no rc l a s s p r o b a b i l i t yv e c t o rf o rc l a s s i f i c a t i o n i ti sb a s e do nt h ek e r n e lm a t r i x f r o mp c ew ec o m b i n ei tw i t hp l e ，a n dg e tc l a s s i f i c a t i o nm e t h o dc a l l e dp c p - p l e t a k i n g t h en u m b e ro fd i m e n s i o n sa n dc l a s s e si n t oa c o u n t ，a nu p d a t ev e r s i o nc a l l e dp c p p l e * i s r a i s e d t h e r ei sa ni m p l i c i tm a p p i n gd e s i g n e df o rc l a s s i f i c a t i o ni nt h e s et w oa l g o r i t h m s t h u st h e yc a na c h i e v eab e t t e rd i m e n s i o n a l i t yr e d u c t i o ng o a lf o rd a t au n d e rv a r i o u sd i s t r i b u t i o n s t h en u m e r i c a lr e s u l t ss h o wt h a tp c p p l e p e r f o r m sb e t t e r , c o m p a r e dw i t hs o m e o ft h el a t e s ta l g o r i t h m so nt h es a m es c e n a r i o ( b ) p a i r w i s ec o n s t r a i n tp r o p a g a t i o n ( p c p ) ，w h i c hw ea n a l y z ei nd e t a i l ，h a ss o m e l i m i t a t i o n sa sak e r n e ll e a m i n gm e t h o d w ef i n dt h a ts o m e t i m e st h en o r m a l i z e dm u t u a l i n f o r m a t i o nm a yn o ti m p r o v e c o n s i s t e n t l yw i t ht h ei n c r e a s i n gc o n s t r a i n t s ，w h e nk e m e lk - m e a n si su s e df o rc l u s t e r i n g t h i sm e a n st h ep e r f o r m a n c eo fp c pi sq u i t er e l e v a n tt ot h e d i s t r i b u t i o no fp a i r w i s ec o n s t r a i n t s s ow er a i s eap p c pm o d e lw h i c hr e l a x e st h ep a i r w i s e c o n s t r a i n t sb yp r o b a b i l i s t i cc o n s t r a i n t s p p c pm a yb em o r ee f f e c t i v et h a np c pi ns o m e c a s e s f u r t h e rm o r e ，b a s e do nt h ep r o b a b i l i t yf u n c t i o nd e s i g n e da b o v e ，p p c pc a nb eu s e d w i t h o u ta n yp r i o rp a i r w i s ec o n s t r a i n tk n o w l e d g e t h e r e f o r e ，i tc a nb ea p p l i e di nm o r ec a s e s a sa nu n s u p e r v i s e dc l u s t e r i n ga l g o r i t h m ( c ) b a s e do nt h ep r o b a b i l i t yf u n c t i o n ，w ep r o p o s eat y p eo fa c t i v ek e r n e ll e a r n i n g a l g o r i t h m s ：a c t i v e - p c pa n da c t i v e - p p c et h ea l g o r i t h m sc a na d a p t i v es e a r c ht h en e g a t i v e p a i r w i s ec o n s t r a i n sf o rc l a s s i f i c a t i o n ，a n dt h e nd e a lw i t ht h e mb ye l i m i n a t i o no rr e l a x a t i o n ， w h i c hc a ni m p r o v et h ep e r f o r m a n c eo f c l a s s i f i c a t i o n a p a r tf r o mt h e s e ，w ep r o p o s ea na p p r o a c ht oe n l a r g et h es e to fp a i r w i s ec o n s t r a i n t sa u t o m a t i c a l l yw h i c hm a k e st h ea l g o r i t h m m o r es u i t a b l ef o rc l a s s i f i c a t i o n t h e r ea r es i xc h a p t e r si nt h i st h e s i s c h a p t e r1s t a t e st h eb a s i cc o n c e p t s ，b a c k g r o u n d k n o w l e d g ea n dd e v e l o p m e n to ft h ei s s u e ，a n da l s ol i s t st h ep r o d u c t i o no f t h et h e s i s c h a p t e r v 浙江大学博士学位论文 2g i v e sab r i e fr e v i e wo nt h ew o r ko fm a n i f o l dl e a r n i n ga n dk e m e lm e t h o d s t h em a i na l g o r i t h m sa r ei l l u s t r a t e di nc h a p t e r s3 ，4 ，a n d5 c o n c l u s i o nr e m a r k sa n df u t u r ep e r s p e c t i v e s a r es h o w ni nt h el a s tc h a p t e r k e y w o r d s ：m a n i f o l dl e a r n i n g ，s e m i s u p e r v i s e dl e a r n i n g ，c l a s s i f i c a t i o n ，d i m e n - s i o nr e d u c t i o n ，k e r n e lm e t h o d v l 致谢 致谢 时光荏苒，博士阶段的生活即将走向尾声。面对即将完成的论文，我想这些都 应当归功于我的导师张振跃教授。感谢张老师的悉心指导和鼓励，让我得以完成这 份论文。回想五年的博士生活，张老师严谨的治学态度，渊博的学术知识，深厚的 学术积累，敏锐的数学直觉、幽默生动的表达以及低调踏实的作风无不给予我无尽 的教诲。我要衷心感谢张老师花费大量的时间和精力对我培养，将我引领进科学的 大门，让我从一无所知到对科研有所认识，我的每一点成绩无不凝聚着张老师耐心 授业解惑的心血。“高山仰止，景行行止，虽不能至，心向往之”，张老师的为人为 师之道将使我受益终生。 感谢授课的程晓良、韩丹夫、黄正达、许洪伟、刘康生、何勇等老师，他们的教 授让我具备了扎实的知识基础，他们的敬业精神给予了我更强的学 - - - j 动力。 感谢课题组的李旭东、王靖、方敏、裘渔洋、杜克勤、方腊、卢俊峰、李丽敏、陈 孝瑞、何睿、曹沛霖、徐丽娟、蔡晓昊、加帮平、张永亮、潘建民、赵科科、许熳峰、 罗起祥、严孝伟等和应文隆老师，感谢你们的讨论带给我的收获和提高。 感谢我的好友戴晓霞、唐培培和金佩卿，感谢你们对我生活上的关心和学习上 的帮助，感谢你们给我的温暖友情。感谢魏嗣明和胡崇海等师兄对我的启发和帮 助，与你们的讨论让我对该领域的前沿进展有了更清晰的认识。感谢我的同窗好友 王昕、胡潇哲和朱建平等，感谢你们对我学业上的鼓励和帮助。 感谢我的父母多年来对我的理解、支持和关怀，我将继续努力前行! 绪论 1 绪论 学习是人类具有的一种重要智能行为。通过学习，我们传承了先人积累的大量 知识，并能够从历史中总结经验，更好的建设现在和未来。自计算机问世以来，如 何让计算机具有和人类相仿的学习能力的问题，一直吸引着科学家们的兴趣。一般 将这类问题的研究归为人工智能领域。机器学习正是这一领域的一个新兴分支。虽 然目前对“机器学习”的定义还一直是众说纷纭，没有一个公认的准确说法，但是 从字面看，机器学习就是研究如何使用计算机来模拟人类学习行为的一门学科，更 细致的看，机器学习就是研究如何让计算机获取新的信息，或者识别现有信息的学 科。这里，不妨援引m i t c h e l l 在其著作 【l 】中的定义来支持我们的 理解，。机器学习是对计算机算法的研究，通过对经验知识的学习来提高算法的自 动性”( m a c h i n el e a r n i n gi st h es t u d yo fc o m p u t e ra l g o r i t h m st h a ti m p r o v ea u t o m a t i c a l l y t h r o u g he x p e r i e n c e ) 。二十一世纪被称为信息世纪，为了不让我们被信息的海洋淹 没，科学家们不断的研究更有效的机器学习算法，统计学、人工智能、哲学、信息 论、生物学、认知科学、计算复杂性和控制论等众多领域的成果都被引入到机器学 习中。机器学习成果的应用也越来越渗透到我们的生活中，医疗系统可以通过对现 有病例记录的学习而获取诊断，网站可以通过对用户点击的学习而为其安排感兴趣 的新闻，邮局可以通过对字体的学习而设计按邮编自动分拣信件的系统。我们的研 究也正是在这一背景下展开。 1 1 基本概念 许多机器学习任务的目标都是预测数据的某些感兴趣的特征( 称为l a b e l ) 。 已有的方法都可以概括为：在给定的训练集的基础上，寻找数据与这些特征 之间的函数关系。所谓的训练集，指的是一些已知的样本数据及其相应的已知 特征。我们用x = z 1 ，z 。，z n + 1 ，z ) 表示已知的输入数据点集，其中部 分x x ，z 。，】对应的l a b e l 值集合记为y = 【可1 ，玑， ，其中，x i l 的l a b e l 值 y i ，i = 1 ，祝。通常，n n ，并将 z l ，z n ，) 和 y i ，玑，】_ 简称为训 浙江大学博士学位论文 练集，这是因为两者之间的一一对应关系是巳知的。在许多应用问题中，要获得样 本点的l a b e l 值是不容易的，或代价较大的。因而实际的l a b e l 值是不完全的。依据已 知输入数据点集与已知l a b e l 值集之间的匹配度的差异性，机器学习可以分成监督学 习、半监督学习，及无监督学习这三类。 定义1 1 1 监督学习。所谓监督学习指的是：已知的数据点集x 具有完全的己 知l a b e l 集y 与之匹配，即佗= n 。 一般地，监督学习的任务是寻找预测函数9 ( x ) ，使得用来衡量预测函数输出值 和真实l a b e l 值偏差的损失函数c ( y 1 9 ( x ) ) 值最小。 定义1 1 2 半监督学习。如果已知的l a b e l 值数量要少于已知的样本数，即n - - j 的理论应用在了机器学 - - j 领域，提 出了著名的支持向量机【2 0 】( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 算法，在这一算法 中，核的概念被明确的提出，它将这个原本只能处理线性可分问题的分类器推广 到了非线性的情形。1 9 9 7 年，s c h o l k o p f 等学者将核的思想应用到了经典的p c a 方法 上【2 1 1 ，通过核的引入，使p c a 这个线性减维的算法也能够很好的处理某些非线性 性质很强的数据。这一鼓舞人心的成果使得核方法在机器学 - - j 、数据挖掘、人工智 浙江大学博士学位论文 能等领域得到了广泛的应用，直至十几年后的今天，大量关于核方法的研究成果 依然常常见诸于顶级的学术会议报告和期刊里。如何将核引入这类给定部分同异 类信息的半监督问题? 常见的想法有：通过设定核的类型并学习其参数的核学习 方法，如 1 0 ，1 2 ，2 2 等工作都属于此类。假设核是一系列核的线性组合并求解其系 数也是常见的处理方式，其中代表性工作有 1 3 ，1 4 等。此外，还有一些值得关注 的工作，如 9 ，1 1 ，1 3 1 5 等，则是通过非参数化的方式来求解核的。本文将重点介 绍i 均p c p t 2 3 1 算法也属于此类。p c p 算法是将所有点隐式映射到单位球面上，其中同 类点映射到同一点，异类点位置正交，并通过拉普拉斯特征映射的权重来保持原 始的图结构。和大多数同类问题类似，隐式映射对应的最佳核可以通过解半定规 划( s d p ) 问题得到，其中s d p 可由s e d u m i 2 4 等工具包求解。 基于同异类学习的工作不仅仅有分类，降维也是其中的一项重要任务。如何 基于流形假设以及同异类信息进行合理的降维同样是机器学习中经常涉及的问 题。b a r - h i l l e l 等人提出n f l d 算法【2 5 】基于相关主成分分析( r c a ) 给出了已知同类 关系下的降维方法，但是这项工作只能处理同类关系。为此，z h o u z 等最近提出了 用于半监督降维的s s d r 算法【2 6 1 ，这一工作的核心思想是寻找能最大程度保持同异 类关系的线性投影方向，该问题可通过求解文中定义的拉普拉斯矩阵的特征值问题 来完成。 聚类分析也是机器学习的重要研究方向，理想的聚类算法应该具有可扩展性、 可探测任意形状、用户输入参数少、对噪声不敏感、可处理高维数据、可解释性 和可用性。在众多的聚类算法中，常用的主要有k m e a n s 算法【2 m 9 1 、d b s c a n 算 法 3 0 , 3 1 、c l i q u e 算法【3 2 ，3 3 】和b i r c h 算法【3 4 3 5 】等。 1 3 本文主要成果 流形学习作为近年发展起来的新方向被广泛用于数据降维，其主要思想是利用 欧氏距离来挖掘邻域信息。然而对予带类别属性的情形，由于局部距离关系可能和 分类相悖，传统流形学习方法经常会失去其原有效果。s l l e 算法解决了所有样本点 类标确定的前提下数据有效降维的工作，但是获取类标信患往往代价较大，而且该 算法对未知类标点有不兼容性，将其转化成一个有效分类算法是非常困难的。针对 4 绪论 这一背景，我们提出了p l l e 这一基于概率属类信息的半监督降维算法。通过设计一 个基于属类信息的距离度量，p l l e 将各点的概率信息以距离增量的形式融入模型， 使得降维起到同类相聚异类相离的效果。同时，概率的灵活性使得对未知类标样本 点的分类工作变得可能，有效的解决了s l l e 算法中的不相客问题。同时，我们还 基于逻辑回归和马尔可夫链给出了预估未知类标点的p e 算法，并结合p l l e 和p e 得 雯j p l l e c 这一有监督的分类算法。同时也给出了p l l e 算法在拉普拉斯特征映射算 法上的推广，即p l e 算法。数值试验表明p l l e c 算法是一个非常有效的分类器。 半监督信息以点对同异类关系形式给出的模型是十分常见的，然而如何基于这 种分类信息完成数据降维依然是富有挑战性的工作。对于此类问题，常见的处理方 式是寻找某个最佳投影方向以达到同类相聚异类相离的效果。但是线性降维的方 式常常因为数据的非线性分布而失效。我们注意到最近提出的p c p 算法能够通过求 解s d p 问题得到最佳分类核，即该核诱导的隐式映射可以使得的数据分布更接近其 类别属性。基于这一点，我们首创性地给出了利用分类核确定数据点属类概率向量 和同类可靠性函数的方法。结合由p c p 得到概率向量和p l e 方法，我们又提出了能 够有效完成带同异类关系数据的降维算法，称为p c p p l e 算法。同样的背景下，注 意到p c p 给出的核矩阵具有空间中的低秩结构，对其作用k p c a 算法也是一种可行 的降维方式。对于类别数目较小，降维维数较低的问题，p c p k p c a 也是非常有效 的。因此我们结合p c p p l e 和p c p - k p c a ，提出了p c p p l e 木降维方法。 p c p 算法由于对同类和异类点强制性的定位使其在某些情形下缺乏灵活性。针 对这一缺陷，我们提出了将同异类约束以概率形式“放松”的p p c p 算法，希望其 能够在由p c p 推广的某些问题中取代p c p ，获得更优越的效果。传统的k - m e a n s 方 法是一个基于整体位置关系来确定点对类别的无监督分类算法，由于k m e a n s 在 操作中忽略了局部性质，因此聚类结果可能与数据集的流形假设相悖。在本文 中，我们创新性地设计了这样一个算法：由初始k m e a n s 确定的点对可靠性函数 来产生约束集，将原始的无监督聚类问题半监督化，再利用p c p 结合核k - m e a n s 完 成分类。我们称之为p c p k m e a n s 算法。将类似延伸至p p c p ，即有p p c p k m e a n s 算 法。p c p ( p p c p ) k m e a n s 实质上是一个利用局部结构传播类别属性的过程，因此最 终聚类效果好于初始的k m e a n s ，数值试验也充分证明了我们的论断。此外，针对 5 浙江大学博士学位论文 和p c p 算法会随机出现分类准确度伴随约束点对增多而降低的问题，我们提出了利 用可靠性函数搜索并处理不利约束的a c t i v e p c p 和a c t i v e - p p c p 方法，前者可主动性 的去除不利约束，后者则将主动搜索到的不利约束改成“放松”的p p c p 形式，数值 实验表明了a c t i v e p p c p 方案的有效性。最后，本文尝试了通过扩张约束集合来提升 分类效果的方案。 本文的内容组织如下：论文的第一章阐述了课题的研究背景、现状以及本 文的主要科研成果，第二章介绍了流形学习和核方法领域的经典工作。第三章 主要描述了p l l ，p e ，p l l e c 和p l e 算法。第四章详细介绍了p c p 、k - m e a n s 方法以 及聚类有效性指标n m i ，给出了p c p p l e ，p c p k p c a ，p c p - p l e 幸算法。第五章提出 了p p c p ，p c p ( p p c p ) 一k m e a n s ，a c t i v e p c p ( p p c p ) 以及扩张的p c p ( p p c p ) 算法，第 六章总结了全文的工作，并对后续的研究课题加以展望。 6 流形学习与核方法简介 2 流形学习与核方法简介 2 1 流形学习 2 1 1 流形学习的研究背景 随着信息时代的到来，数据集增长更新的速度加快、数据维数更高以及非结构 化性的问题变得更为突出。技术的落后，造成了信息资源的巨大浪费。我们被信患 淹没，却又缺乏知识。如何在保持数据信息足够完整的意义下从海量数据集中提取 出有效而又合理的约简数据，满足存储处理等需求是亟需解决的问题。 从上世纪开始，微分几何学高速发展，对于高维空间的微分几何以及曲线、曲 面整体性质的研究，使微分几何学同现代数学方向如黎曼几何、李群代数、拓扑学、 变分学等相互渗透，成为数学领域的热点研究问题之一。微分几何发展的意义不仅 在于本身，其在多个学科之间都有着广泛的应用，例如，爱因斯坦在研究广义相对 论时，认识到由于引力的作用，空问可能弯曲，黎曼几何则为描述这种弯曲的空间 提供了理想的工具。微分几何学的高速发展和广泛应用为我们研究新的机器学习算 法提供了坚实的理论基础。 流形学习理论就是在这样的背景下产生的，它以微分几何学作为理论基础，结 合多种学科，研究机器学习所面临的新问题，其主要目标在于降低原始数据的维 数，提取最重要的特征，揭示其潜在的结构，学习和发现嵌入在高维空间中的低维 特性。 2 1 2 流形学习中的基本数学定义 在机器学习中，研究的对象通常采样自欧氏空间，并可看作是处于欧氏空间的 一个低维流形上，一般这个低维流形满足微分流形的性质。流形学习的目标就是如 何运用已知的样本点重构出原有流形的低维结构。影响重构流形效果的因素是多样 的，比如，现实世界中的数据往往是离散的，数据采样的稠密度就会很大程度的影 响重构效果。当然，算法的设计和选择也至关重要，比如对于一个由带状流形弯曲 7 浙江大学博士学位论文 生成的瑞士卷形状的流形，任何通过寻找线性投影来重构其嵌入结构的算法都不能 奏效。为了能合理的分析各种因素，我们必须了解流形学习中的基本概念。在本小 节，我们简单的给出几个文中用到的流形相关定义【3 毛3 7 1 ： 定义2 1 1 微分流形。一个d 维c 七流形就是一对( m ，人) ，其中m 为d 维流形， a = _ 【( 玩，) ，。a 为一伊的微分结构，即满足以下条件： ( 1 ) ( 局部欧氏性) | 巩：o a ) 构成m 的一个开覆盖，：巩_ ( 玩) c 剧为同胚映射； ( 2 ) ( 伊相容性) 若巩n 仍，则双射 o 1 ：卿( 玩n ) _ ( 玩n ) 和它的逆映射都是k 次可微的，则称( 既，) 与( ，妒p ) 是相容的； ( 3 ) ( 最大性) 若u 为m 中的开集，妒：u _ v ( u ) cr d 与人中的每个( ，) 都相容，则( 妒) a 。 定义2 1 2 切向量和切空间。光滑流形m 在点z 的切向量就是一个映射v 。： c ( m ) _ 冗，且对，h c ( m ) ，a ，b r 满足： ( 1 ) v x ( 0 9 + b h ) 一a v = ( g ) + 地( ) ； ( 2 ) v = ( g h ) = u z ( 9 ) 危( z ) + g ( x ) v x ( h ) 。 假设( 以妒) 为点x 的一个局部坐标系，则映射 ( 最k9 一( 瓦o g ) 茁三( 地等( 圳，9 c 。( m ) 为z 点的一个切向量。光滑流形的切向量是曲线的切向量的一种推广。x 点的切向 量全体记为t z ( m ) ，它是一个实线性空间，称之为m 在点z 的切空间。 定义2 1 3 测地距离。设p 、q 是黎曼流形m 中任何两点，则这两点间的测地距离 d m ( p ，q ) 为m 中连接p 、q 的所有分段光滑曲线的弧长的下确界。 定义2 1 4 等距流形。设m 为d 维的黎曼流形，若存在光滑映射g ：m _ 满 足： 8 流形学习与核方法简介 ( 1 ) g ：m g ( m ) 为同胚； ( 2 ) 对任意的p ，q m ，有d m ( p ，q ) = 怕) 一9 ( 口) 则称m 为d 维的等距流形。 2 1 3 局部线性嵌入算法( l l e ) l l e 2 1 是以保留流形局部样本点之间的线性表示权信息为基本思想的算法。可 以想象，一个流形在足够小的局部邻域上是可以近似的看作线性的，因此，在这种 非常小的局部邻域，我们可以把一个样本点近似的用其周围的点的线性组合来表 示，并且通过最小二乘的思想，我们甚至可以找到一个和原来样本点差异( 这里用 在f 范数下的误差衡量) 最小的所谓最优线性表示。l l e 算法就是把这种线性拟合的 系数当作流形的局部几何性质的刻画。因此，在l l e 算法的衡量标准下，一个好的 低维表示，就应该也具有同样的局部几何性质。l l e 的基本算法如下： l l e 算法： s t e p1 寻找最近邻域。使用k 近邻( k n n ) 方法为每一个数据点x i ，i = 1 ，2 ， 按照欧氏距离寻找其k 个最近的邻居点，构成的邻点集( 邻域) ，记为( z t ) 。 s t e p2 计算重构权值 训u ) 。在每个点现的邻域中，对翰的每一个邻点巧分配一个用 于线性重构的的权值训玎，暇= w i j 来自于求解下列优化问题： m i n e ( w i ) = 慨一伽巧z j l i ( 2 1 ) 厂0 i ) 其中邑w i j = 1 ，并且，如果巧不是翰的邻近点，则蚴= 0 。 s t e p3 计算由 叫巧) 最优重构的低维嵌入向量 们 。通过极小化嵌入( e m b e d d i n g ) 的整体价值函数： m i n e ( y ) = 慨一w t j y j l 2 ， ( 2 2 ) 协d v ( 叭) 可得到低维投影。其中( 仇) 指得是犰的邻点集，- 与n ( z i ) 具有相同的邻点指标 集。 9 浙江大学博士学位论文 叫巧) 的约束条件保证了相邻点对之间的平移、旋转和伸缩的不变性。为保证 求解上述优化问题能得到唯一的解，这里需要补充两个关于低维嵌入向量 玑) l 的约 束条件： ( 1 ) 中心化：墨ly i = o ； ( 2 ) 单位化：竺1 犰鲥= i 。 当 叫巧) 确定后，求解优化问题( 2 2 ) 。它等价于求矩阵m = ( i 一彬) 7 ( j r w ) 第 二到第d + 1 个小的特征向量，而这些特征向量就形成了低维嵌入矩阵y 的行。 通过利用线性重构的局部对称性质，l l e f l 邑够学习非线性流形的全局结构，并 在人脸识别，文本分类，图像识别，生物信息学等诸多领域得到广泛应用。l l e 算 法的有参数少( 预先只需确定邻域个数k 和像空间的维数d ) 、计算效率高( 优化求 解时，避免了出现求解局部最小的情况) 等优点。当然，l l e 也有不足之处，它的一 个主要缺陷是当有新的样本点加入时，我们不能从原有的嵌入出发，而必须重新计 算，才能得到新的嵌入。 2 1 4多维尺度分析法( m d s ) 与等距映射