（计算机应用技术专业论文）基于直推式支持向量机的图像分类算法研究与应用.pdf

中文摘要 摘要：随着互联网技术的发展以及网络使用的普及，多媒体信息尤其是图像和视 觉信息由于其丰富多彩的信息，已经成为了信息检索的重要内容，其中视频信息 又是以图像信息为基础的。在图像检索技术上，为了检索的结果更接近人的思想， 如何使用基于语义内容的图像检索来使用图像底层特征拟合人类的高层语义成为 了关键。 本文首先介绍了各种现有的分类检索算法，其中支持向量机( s u p p o r tv e c t o r m a c h i n e ，s 讧) 被认为是一种高效的有优越表现的分类器，在很多场合都能得到 应用。在这基础上，直推式支持向量机( t r a n s d u c t i v e s u p p o r t v e c t o r m a c h i n e ，t s v m ) 是在结合支持向量机算法，实现的一种高效的分类算法。但是它有算法时间复杂 度比较高，需要预先设置正负例比例等不足。 本论文中，提出了一种新的算法，该算法在原有t s v m 算法的基础上，利用 有标签样本的同时，考虑无标签样本对分类器的影响，并且在原有过程中添加部 分筛选条件，以及进行流程改进，使得新的算法在时间复杂度上有明显下降，同 时对算法效果没有明显的影响。 本论文还设计并实现了一个实验检索系统，该系统使用了改进的新算法，利用 算法渐进式的特点，实现了基于语义类、图片类、用户白定义语义类的多层次语 义，和使用样例图片、语义关键字的多种方式的检索。 关键词：支持向量机；直推式学习；图像分类。 分类号：t p 3 9 1 a b s t r a c t a b s t r a c t ： w i t ht h er a p i dd e v e l o p m e n to f w e bt e c h n o l o g ya n dp o p u l a r i t yo f u s i n gt h ei n t e m e t , s e a r c he n g i n e sb e c o m ea ni m p o r t a n tw a yf o rm a n yp e o p l et o g e ti n f o r m a t i o n m u l t i m e d i a , e s p e c i a l l yi m a g ea n dv i d e oi n f o r m a t i o nb e c o m ea ni m p o r t a n tc o n t e n to f i n f o r m a t i o nr e t r i e v a l ，a n di m a g er e t r i e v a li sm o r ef u n d a m e n t a l i ni m a g er e t r i e v a l t e c h n o l o g y , h o wt o t , k s ec o n t e n t - b a s e di m a g er e t r i e v a li st h ek e yo fm a k i n gt h e d i f f e r e n c eb e t w e e nr e t r i e v a lr e s u l t sa n du s 0 1 ss e m a n t i c sa ss m a l l e ra sp o s s i b l e i nt h i st h e s i s ，w ef i r s t l yr e v i e ws o m ek i n d so fr e t r i e v a la l g o r i t h m s ，i nw h i c hs v m i sc o n s i d e r e dt ob ea ne f f i c i e n to n e b a s i n go ni t , t r a n s d u e t i v es u p p o r tv e c t o rm a c h i n e s a l em o r ee f f i c i e n tt h a ni n d u c t i v es v m s ，e s p e c i a l l yf o rv e r ys m a l lt r a i n i n gs e t sw i t h l a r g et e s ts e t s b u tt h e yh a v ed i s a d v a n t a g e s ，s u c ha sh i 班t i m ec o m p l e x i t ya n dt h e r e q u i r e m e n to f “r l u m + w ep r o m o t ean e wa l g o r i t h mi n t h i st h e s i s ，w h i c hb a s e so nt s v m b u tw ea d d s o m ef i l t e ri ni ta n di m p r o v et h ef l o w , w h i c hr e d u c e st h et i m ec o m p l e x i t yw i t hl i t t l e i n f l u e n c eo i lt h ep e r f o r m a n c e f u r t h e rm o r e ，繇e x p e r i m e n t a ls y s t e mw a sd e s i g n e da n di m p l e m e n t e di nt h i st h e s i s 。 w h i c hu s e dt h e i m p r o v e da l g o r i t h m ，a n dt h ep r o g r e s s i v ec h a r a c t e r i tb a s e do n m u l t i - l a y e rs e m a n t i cw h i c hc o n t a i n e ds e m a n t i cc l a s s ，i m a g ec l a s s ，s e l f - d e f i n ec l a s s ，a n d h a dt w os e a r c hm o d e l sw h i c hw e r es a m p l eb a s e da n ds e m a n t i ck e yw o r d sb a s e d k e y w o i i d s ：s v m ；t r a m d u c t i v el e a r n i n g ；i m a g ec l a s s i f i c a t i o n c l a s s n o ：t p 3 9 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：7 一 年l 瑚日 朋钼，朋 亵 ： 7 名 ： 签 期 师 日 导 字 签 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取锝的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 糊一躲赫秽一期：哆 月矽日 致谢 本论文的工作是在我的导师许宏丽副教授的悉心指导下完成的，许宏丽副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三 年来许宏丽老师对我的关心和指导。 许宏丽副教授悉心指导我完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向许宏丽老师表示衷心的谢意。 许宏丽副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 在实验室工作及撰写论文期问，陆景辉等同学对我论文中的分类算法研究工 作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人爸爸妈妈，他们的理解和支持使我能够在学校专心完成我的 学业。 1 引言 1 1 研究背景 最近一些年，搜索引擎成为了i n t e m e t 的热门，例如g o o g l e 、y a h o o 、b a i d u 等。它的广泛使用为众多的i n t e m e t 的用户提供了方便。其中图片的搜索需求也是 日趋增长，于是基于内容的图像检索( c b i r ，c o n t e n t - b a s e di m a g er e t r i e v a l ) 技术 一直是研究的热点之一。 实现图像检索的重要障碍在于要跨越语义内容和底层特征之间的“语义鸿 沟”，一直以来的解决方法有：相关特征提取、相关反馈、图像标注等。相关特征 提取的研究主要是在上世纪九十年代前中期( 1 9 9 0 - 1 9 9 8 ) ，它着力于在图像的底层 特征中提取相关有用特征，用这些底层特征来代表高层语义内容 1 】。相关反馈的 研究主要是在1 9 9 5 年至2 0 0 1 年，它主要是利用用户的反馈来优化检索，利用用 户对语义的判断来跨越“语义鸿沟”，尽管不同用户对于同一语义的理解有偏差， 但相对于底层特征和高层语义的差距还是小得多。目前的搜索引擎对于图片的搜 索大多都是基于文本图像标注的，图像标注虽然较好的跨越了语义鸿沟，对于图 像的语义能有较好的描述，但是这样的描述很难全面的描述图像的信息，比如图 像的颜色、纹理等信息。本文研究的基于内容的图像检索是使用颜色，纹理，形 状及区域等视觉特征来获得图像信息，进而得到图像的高层语义知识，并以此来 衡量图像之问的相似程度以实现基于语义内容的图像检索。 本文研究主要针对各种机器学习算法，重点研究支持向量机、直推式支持向 量机，并且对其改进得到一种基于直推式支持向量机的半监督学习分类算法，它 对原有经典的直推式支持向量机的算法复杂度加以改进，使得直推式支持向量机 可以用于大样本的检索。最后基于该改进的直推式支持向量机算法，结合相关反 馈技术，实现了一个图像检索系统，并且在该系统上进行了一系列的相关比较实 验，得出一些结论、发现一些不足。 1 2 机器学习分类 从广义的讲，任何设计分类器时所用的方法，只要该算法利用了训练样本的 信息，都可以认为运用了学习( 算法) 。实践中有意义的模式识别系统要实现得到 一个最佳的分类判决面是很困难的。因此分类其的大部分的时间都用于研究学习 问题。建造分类器的过程要涉及：给定一般的模型或分类器的形式，利用训练样 本去学习或估计模型的未知参数。这里的学习是指用某种算法来降低训练样本的 分类误差。一大类基于梯度下降的算法，能够调节分类器的参数，使它朝着能够 降低误差的方向前进，目前已经成为统计模式识别领域的主流学习算法。 1 2 1 有监督学习 关于机器学习的分类，从是否对于样本进行了标注的角度，主要可分为两种 类别；有监督学 7 ( s u p e r v i s e dt e a m i n g ) 和无监督学习( 唧e 嘶s e dl e a r n i n g ) 在有监督学习中，存在一个教师信号，对训练样本集中的每个样本能提供类 别标记和分类代价，并寻找能降低总体代价的方向。在有监督学习算法中，使用 这样的训练数据集： r = 【而，y ，】e r “r ，i = l ，以)( 1 1 ) 它由n 个数据对组成( x 1 y 1 ) ，( x 2 , y 2 ) ，( x t t , y n ) ，其中x i 是i t i 维的向量x i e r “， y i 是对应x i 的样本标签，可以是连续的值或者是离散的值( e 学，布尔值) 。至今已 经提出了很多的有监督分类算法，比如朴素贝叶斯算法( n a i v eb a y e s x l e w i s 1 9 9 8 ) 2 】，最近邻算法( n e a r e s tn e i g h b o r ) ( m a s a n d1 9 9 2 ) 3 ，神经网络算法( n e u r a l n e t w o r k s ) ( n g1 9 9 7 ) 4 ，回归算法( r e g r e s s i o n ) ( y a n g1 9 9 4 ) 5 ，规则推理算法( r u l e i n d u c t i o n ) ( a p t e1 9 9 4 ) 6 1 ，以及支持向量机算法( s u p p o r t v e c t o rm a c h i n e s ( s v m ) ) ( v a p n i k1 9 9 5 ，j o a c h i m s1 9 9 8 ) 【7 】【8 】。其中支持向量机被认为是最有效的分 类器。 常见的分类器有以下几种： 1 ) n a i v eb a y e s 分类器 使用贝叶斯公式，通过先验概率和类别的条件概率来估计图像d 对类别c i 的 后验概率，以此实现对图像d 所属类别的判断。 根据b a y e s 定理，得： p ( qi d j ) = 等 ( 1 2 ) p ( d j ) 对所有的类别是一样的；先验概率p ( 可通过简单的估计得到，通常取 c i 的图像数占整个训练集图像数的比值。 对p 妈恸的计算，利用独立假设( 如同i r 的概率模型，这样做不严格) f p ( d jic，)=兀p(峋lq)(1-3) s f f i l 这样，就将它转化为计算图像特征在类别c i 中的分布情况。 2 在我的实验中，采用r g b 彩色直方图。对于每个特征，在所有训练样本中， 计算均值和标准差为： ：窆毛 舻：去毛 盯：上窆( 一) z n i 智“ ( 1 4 ) ( 1 - 5 ) 然后对预测集中的图像用公式f 【x ) ，可求得p ( w s j l q ) 4 2 。 则该样本所属的分类与e ( c ，i 以) 值最大的类相同。 t妇一，r 八力2 志一( 1 - 6 ) 2 ) k n n ( k _ n e a r e s tn e i g h b o r ) 分类器 i ( n n 分类算法思想很简单：对于一幅待分类图像，系统在训练集中找到k 个 最相近的邻居，使用这k 个邻居的类别为该图像的候选类别。该图像与k 个邻居 之间的相似度按类别分别求和，减去一个预先得到的截尾阈值，就得到该图像的 类别测度。 可以把邻居图像和测试图像的相似度作为邻居图像所在类的类权重。如果这k 个邻居中的部分图像属于同一个类，则该分类中的每个邻居的类权重之和作为该 类别和铡试图像的相似度 y ( i ，c ，) = s i m ( i ，t ) y ( t ，勺) 一q ( 1 - 7 ) d t e k 最简单判别方法：测试图像的类别与k 个最邻近的邻居中占有最多数的类相 同。当只有两类进行分类的时候，k 取奇数，为了防止k i = k 2 的情况下无法判断 所属的类烈 k n n 是一种l a z y - l e a r n i n g 算法，分类器不需要使用训练集进行训练，训练时 间复杂度为0 ，在进行分类时计算样本点与训练集中样本的距离。算法的复杂度与 训练集的个数n 有关，为o ( 1 1 ) ，因为要与每一个训练样本计算距离 3 ) s v m 分类器 一个线性判别函数( d i s c r i m i n a t e c t i o n ) 是指由样本点x 的各个分量的线性组 合而成的函数： g ( 功= w r x + w 0( 1 8 ) 在两类情况( c i 和c 2 ) 下，对于两类问题的决策规则为： 如果g ( x ) o ，则判定x 属于c i ； 如果g ( x ) o ，则判定x 属于c 2 ； 如果g ( x ) = o ，则可以将x 任意分到某一类或者拒绝判定。 由此可得，方程g ( x 产o 定义了一个判定面，它把归类于c l 的点与归类于c 2 的点分开来。当甙x ) 是线性函数时，这个平面被称为“超平面”( h y p e r p l a n e ) 。 在特征空间中构造分割平面：( w 曲+ 6 = 0 使得： ：i ；：i ：。儿y l ：= 一1 ，即，e c w 一，+ 6 ，z = t ，z c t 9 ， 可以计算出，训练数据集到给定的分割平面的最小距离为： p ( w 6 ) 2 m i n ，竺萨一m a x ，兰萨2 两2 ( 1 1 0 ) 从s v m 对优化分割平面的定义可以看出，对该平面的求解问题可以简化为： 在满足条件式( 1 - 9 ) 的情况下计算能最大化p ( w ，b ) 的分割平面的法向量w 和偏移量 b 。v a p n i k 等人证明了分割超平面的法向量w o 是所有训练集向量的线性组合，即 w o 可以描述为： w o = ( 口? 乃) 而 ( 口? 0 ) ，i = 1 ，l( 1 1 1 ) 定义判别函数： ，( 功= w o z + b o ( 1 一1 2 ) 则测试集的分类函数可以描述为： l a b e l ( x ) = s g n ( f ( x ) ) = s g n ( w o x + b o )( 1 1 3 ) 在多数情况下，式( 1 - 1 1 ) w o 的展开式中，系数oo 为零值，而非零值的ao 所 对应的x i 就称为支持向量s v 这些向量充分描述了整个训练数据集数据的特征，使 得对s v 集的线性划分等价于对整个数据集的分割。 最优分割平面的求解等价于在式( 1 9 ) 约束下最大化下面的式( 1 1 4 ) ： 中( w ) = 刮叫1 2( 1 1 4 ) 引入拉格朗日乘子a i ，i = 1 , 2 ，1 并定义 ， 础) = 口l y l x l ( 1 1 5 ) 如l 使用w o l f e 对偶定理把上述问题转化为其对偶问题： 4 妇职= 2 ；5 - 三。讹) 巾) l( 1 - 1 6 ) s u b j e c tt o 盯l 0 ，口y l = o i 对于线性不可分的训练集，可以引入松弛变量，把式( 1 9 ) 改写为下面的求解 u i t 圭n 1 2 军点) ( 1 - 1 7 ) s u b j e c tt o y ，( w + 1 一茧，身0 j m a x w ( 口) = q 一寻巾) 以盯) l 。蜘t o o 乞，墨喾m ：。 o 。8 形如式( 1 1 6 ) 和式( 1 - 1 8 ) 的求解是一个典型的有约束的二次型优化问题，已经 1 2 2 无监督学习 在无监督学习算法或“聚类算法”中并没有显式的“教师”。系统对输入样本 自动形成“聚类”( c l u s t e r ) 或“自然的”组织。所谓“自然”与否是由聚类系统 所采用的显式或隐式的准则确定的。给定一个特定的模式集和代价函数，不同的 聚类算法将导致不同的结果。通常要求用户事先指定预定的聚类的数目。 有很多理由来相信“无监督”方法是非常有用的。首先，收集并标记大型样 本集是个非常费时费力的工作。比如，记录语音信息是相当方便的，但是要准确 的标记出每个发音所对应的单词或音素的代价却是巨大的。第二，也许有人希望 你想解决问题：先用大量未标记的样本集来自动的训练分类器，在人工的标记数 据分类组( g r o u p i n g ) 的结果。这种方法比较适合“数据挖掘”( d a t a m i n i n g ) 方面 的大型应用。第三，存在很多应用，待分类模式的性质会随着时间发生缓慢的变 化。例如，自动食品分类中的食品会随着季节更换而变化。第四，可以用无监督 的方法提取一些基本特征，这些特征对于进一步的分类会很有作用。最后，在任 何一项探索性的工作中，无监督的方法都可以揭示观测数据的一些内部结构和规 律。 从原理上讲，究竟能不能直接从未标记的样本中学习到一些有用的东西，这 5 完全取决于是否接受一些假设( a s s u m p t i o n ) 。毕竟，任何理论的证明都是以一些 假设为前提的。最基本的假定是这样的：样本的概率密度的函数形式是已知的， 而待估计的是一些未知的参数向量。这个假设的无监督问题的解在形式上与有监 督学习问题的解几乎是一样的【9 】。 在无监督学习算法中，使用这样的训练数据集： r = 而r ”r ，f = l ，1 ) ，( 1 - 1 9 ) 与有监督学习相比，无监督学习的训练集只有向量集合，x i r 户，没有对应的 标签y i ，聚类算法就是一种很常用的属于无监督学的学习算法b o ，常用的聚类算 法可以分为五个类别：划分方法( p a r t i t i o n i n gm e t h o d ) 、层次方法( h i e r a r c h i c a l m e t h o d ) 、基于密度的方法( d e n s i t y - b a s e dm e t l l o d ) 、基于网格的方法( g r i d - b a s e d m e t h o d ) 以及基于模型的方法( m o d e l - b a s e dm e t h o d ) 1 l 】。 1 2 3 半监督学习( 直推式学习) “有监督学习”与“无监督学习”这两个概念，相同点是，产生某个样本工的 过程都是：首先根据先验概率p ( 峨) 选择自然状态q ，然后在自然状态q 下，独 立的( 即不受其他自然状态的影响) 根据类条件概率密度p ( x i m ，) 来选取x 。不同 点是：在估计概率密度时，有监督学习问题的每一个样本的所属的自然状态；( 有 时称为这个样本的“标记”( 1 a b e l ) ) 都是已知的，而对于无监督学习问题，每个 样本的自然状态是未知的。 在有监督分类学习算法中，大多数已知的算法都需要足够大的训练集，这样 才能得到较好的分类效果。如果训练集中个类别的样本减少的话，这些传统分类 器的分类效果就会大幅下降。但是，在实际情况中，加标签的样本数量通常比较 稀少，而如果要人为的对样本进行加标签将是耗时耗力的，而无标签样本通常都 是大量存在的。因此将无标签样本引入到有监督学习中成为了一项热门的研究领 域，这就是被称为直推式学习或半监督学习的算法 1 0 】【1 2 】。 在直推式学习中，使用这样的训练集： r = 【葺，y ，】e r 4 r ，工，e r 。，f = l ，f ，歹= f + 1 ，以) ，( 1 - 2 0 ) 有两个子集d l 和d u ，都由向量x r m 组成。其中，d l 是由有标签样本组成的 子集，它由( x i ，y i ) 这样的数据对组成，其中l i t ，y i 是对应x i 的样本标签，可以 是连续的值或者是离散的值。d u 是由无标签样本组成的子集，它由x i 这样的样本 数据组成，其中t + l o v 刈( 2 棚 v ：巧 _ l ，+ l 其中c 和c 是用户制定用以调节的参数，c 是有标签样本的影响因子，c + 是 无标签样本的影响因予；y ：是对于k 个无标签样本z 的未知标签；占，和占：分别是 训练集样本和无标签样本在训练中错分的惩罚因子。 v a p n i k ，j o a c h i m s 等人在t s v m 这方面做了重要的工作，其中j o a c h i m s 的 s v m l i g h t 软件已经实现了这样的算法，并且已经被应用于文本分类、图像识别、 生物技术等方面。 j o a c h i m s 的t s v m 算法步骤如下： a l o g o r i t h mt s v m ： ( 面，6 ，t 一) ：= s o l v es v m _ q p ( ( i - ，) ，i ) ( 孑。，y 。) 1 1 1 ，c o 。o ) ； c ：# 1 0 。： # s o m es m a l ln u m b e r c ：1 0 一s ? 竺殳； 石一b u m w h i l e ( ( c ： c ) i i ( c ： o ) ( 8 ：+ 2 ) ) l o o p2 y ：# 一y ：； t a k eap o s i t i v ea n dan e g a t i v et e s te x a m p l e , ，；# 一y 知 s w i t c h t h e i rl a b e l s ，a n d 蛐 ( 面，6 己百) 一s o l v e _ s v m _ q p ( ( i 。i ) ( i 。) 1 工( 置：) ( i ：) 】，c c ：，c ：) ；l z 。j ， 6 、 ) c ：# r a i n ( c _ * * 2 ，c + ) ； c ：r a m ( c ：* 2 ，c ) ； ) r a t u e l l ( j ，：) ； 该算法的输入是训练集( 墨，乃) ，( i ，只) 和测试集并，葛，豸，茸；参数有c ， c 分别是已标签样本和无标签样本的影响因子，珊瑚+ 是测试集中判为正类的数量； 输出是测试集中样本的标签y ：，y ：。函数s d 船? 珊卵是t s v m 算法的一个子过 程，它也是一个类似于i n d u c t i v es v m 的二次优化过程： l o m i n 妇：v 而蝴三1 确噶岛+ c 影+ c 窘 ( 2 - 6 ) s u b j e c tt o ： v 二：y l 1 1 暑+ 6 】1 一 v ：。：巧晒巧+ 6 】2 1 一巧 墨- ：? ： 陆， v ：。： o ” 整个t s v m 算法的过程可以看作是一个从推导式s v m ( = c 二= o ) 到完全 的直推式s v m ( 芷= c = ) 的缓慢提升；在逐渐增大c 的过程中，未标记样本 的影响逐渐增大，这样兼顾了标记样本和未标记样本在分类中的贡献。 在推导式支持向量机的学习方法中，学习的目标是在训练集上获得一个低的 误差率，以训练集的样本分布来预计测试集的样本分布：但是在直推式支持向量 机的学习中，学习的目标是在一个给定的测试集上，得到小的分类误差，这个显 然是一秘更符合实际情况的合理的改进。在t s v m 学习中，测试集也为决策超平 面的确立提供了除训练集以外的额外信息，这个有助于提高分类器的效果。 j o a c h i m s 的这个算法，是第一个可以解决超过1 0 0 个样本的直推式算法，并且通 过实验可以看出，与推导式支持向量机相比，在分类效果上有了根本性的改善。 但是在时间复杂度上，t s v m 与s v m 相比要显著的长很多。这也是t s v m 很 重要的不足之处，当样本数量增加的时候，这就成为了主要问题。所以有很多算 法都在算法的复杂度上进行了改进。 2 1 2 c o - t r a i n i n g 算法 c o t r a i n i n g 是目前很流行的一种半监督机器学习的方法，它是由b l u m 和 m i t c h e l l 提出的f 1 3 】。它的基本思想是：构造两个不同的分类器，利用小规模的标 注语料，对大规模的未标注语料进行标注的方法。已经有人把c o - t r a i n i n g 的学习 方法运用到文本分类、英语基本名词短语识别、英语专名识别等研究上，而且取 得了很不错的效果，甚至超过了传统的有监督机器学习方法。c o - t r a i n i n g 方法最大 的优点是不用人工干涉，能够从未标注的语料中自动学习到知识。 b l u m 和m i t c h e l l 在研究中发现，在一些问题中，同一个样本可以从多个角度 读对其进行描述，例如，一个网页，可以被描述成网页文本，也可以被描述为一 个指向本页的超链接。于是他们利用这种多重描述的特性，提出c o - t r a i n i n g 算法。 图2 - 2 是c o t r a i n i n g 算法的示意图，图中，x i 和x 2 是观察同一实例的两个角 度，左边的节点是x l 中的点，右边的节点是x 2 中的点。实线表示在训练集和测 试集中的样本，其中训练集的样本加+ 和一标签，测试集的样本不加标签。虚线表 示未在训练集和测试集中出现的非零概率的样本d 3 。 图2 - 2c o 打a i n 如g 算法示意图 f i g u r e2 - 2c o t r a i n i n ga l g o r i t h m c o - t r a i n i n g 算法则利用两个不同学习器在数据集的“分割”的特性集上独立学 习，并结合两个学习器的学习结果作出最后学习结论，这样来达到降低错误率的 目的。c o t r a i n i n g 方法形式化定义如下d 3 ： 定义实例空间z = 置x ：，其中x l 和x 2 是观察同一实例的两个角度，因此， 实例x 可以由( 五，矗) 来表示。假设每个角度观测出来的信息都足够对其进行正确分 类。设x 的分布为d ，c l 和c 2 分别为在x l 和x 2 上定义的概念类，假设在分布d 下实例所有概率不为0 的标注都与目标函数z 和 一致，z c l ，正c 2 。即对于 任意实例x = ( ，x ：) 如果有标注z ，则，( 力= 五( 五) = 五( 而) = ，。对于实例瓴，x 2 ) ，如 果正( 而) ( x ：) ，则在d 下该实例概率为0 。则称函数f = ( ， ) c i xc 2 与分布d 是相容的。 对于x 的一个给定的分布d ，如果分布d 赋予零概率值给那些正“) 五也) 的 实例“，而) ，则认为目标函数f = ( z ，a ) e c , g 与分布d 是相容的a 寻找目到标函 数厂，这样就能够使用更多的未带标注实例来获得一个更好的和目标概念的相容 的目标函数，这就意味着，能减少学习算法所需要的带标签实例的的数目。 c o - t r a i n i n g 算法的两个条件独立的假设，一是使用这两个属性中的任一个就可 以进行分类。二是这两个属性的联系不密切，即没有一个确定的从x i 到x 2 的函数。 设n 个实例( x i j ，x 2 i ) 中前m 个标有标注y i ，而i fm + l ，1 1 的实例未带标，学习 的任务是找出函数，满足触“墨筋户y i ，文献【1 3 】认为，必需找出函数z 和厶满足以 下两个约束： ( 1 ) 对于带标实例n 和f 2 必需标注正确，即当i - l 。m 时，z “，o = a 如，力= 舅； ( 2 ) 对于未带标签实例f l 和亿必需保持一致，即当i - - - m + 1 ，n 时， z ( 而，刁= ( x 2 ，0 1 2 2 1 3e m 算法 e m 算法是一种最常用的统计算法之一。e m 算法最基本的思想就是在给出初 始的对缺省值的估计后，在两个基本步骤之闻反复地迭代。这两个基本步骤的第 一步是求期望，也就是e 步( e x p e c t a t i o ns t e p ) ，该步骤在已知变量和目前参数估 计的情况下，对缺省值给出估计。另一步骤就是最大化，即m 步( m a x i m i z a t i o n s t e p ) ，该步骤是在承认e 步的估计是正确的前提下，重新对参数进行估计，使得 参数值是在e 步中补充完整的数据的极大似然。可以证明似然值在每一步迭代过 程中都不会减少 2 4 1 ，这样就可以保证最后能收敛到局部最大。e m 算法的弱点就 是在数据集比较大的情况下，计算复杂度较大，收敛速度比较慢，所以e m 算法 对数据集大小的适应能力还有改进的空间。 在给定数据集不完整或有缺失的情况下，e m 算法是一个常用于估计参数最大 似然的方法。e m 算法的每一步迭代都涉及到两个步骤，oi 1 表示参数。经过n 步 迭代后的当前值，在给定观测数据和目前的参数值以后，z 的分布是 芦4 = p ( z i y ，0 “) ，那么第n 次迭代的算法就可以表示为： e 步： q ( oi 口4 ，y ) = e 矿【，( 口lj ，) 】= l l o g p ( oiz ，y ) l p ( zi 口“，y ) d z ( 2 _ 8 ) m 步： 0 ”= a r g m a x q ( o ，0 4 ) ( 2 - 9 ) 以上两步需要进行多次重复迭代，每一次迭代都保证了对数似然的增加，从 而保证了算法能收敛到局部最优。 文献 1 5 】的e m 算法中，使用了一个多元朴素贝叶斯分类器，尽管在使用朴素 贝叶斯时的独立条件假设很显然在文本分类中不适用，但是相对于普通的朴素贝 砰斯分类器，使用e m 算法对于分类效果有碉显的提高。 2 2 对于半监督学习的改进 尽管上述提出的多种半监督学习算法在分类效果上比传统的有监督学习都要 显著的好，但是也各自存在着一些不足之处，和各自不同的适用范匿。铡如，t s v i v l 算法的时间复杂度比s v m 要高很多；c 0 仃a a n i n g 算法的独立假设条件和约束条件。 研究者们对于这些算法进行了众多的研究和改进 2 2 1 对s v m 以及t s v m 的改进算法 1 ) t o p o g r a p h i cs v m 2 5 】 在通常的分类器设计中，总是对样本作独立同分布的假设，但是在很多实际 情况中，这种假设是很难实现的，样本间总是有一些邻近相关性。在这篇文章中 提出的分类算法，不仅使用了特征矢量的信息，还考虑了相邻样本标签的信息。 这种算法基于“t o p o g r a p h i c ”的核函数，被称为“t o p o g r a p h i cs u p p o r tv e c t o r m a c h i n e ”。 文中提出了一种扩展的核函数： x ( “，v ，) = k l ( 毛，x j ) + 五( ，v ，) ( 2 1 0 ) 其中，表示象素点h 周围象素的标签构成的向量，五是一个超参量，核函 数k l 可以是任意可用的核函数，k 2 可以是任意的点乘的核函数。 这种算法基于这样的假设，对于局部标签分布的信息有助于提高单独样本点 的分类效果。例如，一系列关于相似形状的图像分割块，他们在灰度和纹理上的 相似性很小；这种情况下，局部标签分布信息就具有很高的相似性。 2 ) a c t i v es v m 2 6 】 在交互式的机器学习中，所有的样本都被添加了标签，但是在添加过程中， 选择不同的样本进行加标签，会得到不同的结果。比如，选择一个和已标签样本 非常接近的样本进行加标签，对分类器几乎不会产生影响。所以如何在交互式学 习中选择样本进行加标签尤为重要。 在t 0 n g 的s v m a c t i v e 2 7 q a ，总是选择比较难以自动分类的样本进行主动学 习，即最靠近s v m 分类边界的m 个样本。在第j 次交互中，选择如下样本： x o ) j , t 2 u 9 # o 0 1 1 气u ，气啊+ v ，玉一丛(211) - - 棚v - - * 、忑玩一i n s r e l e v a n t 在文献f 2 6 】中，对s j 的选择进行了动态的调整。用钿g ) 和表示楣关样本 和不相关样本的数量，当钿 u ) 时，增加；反之，s j 减少。具体公式如下： 5 ，+ i = 5 ，+ a ( ，u ) 一，k ( ，) ) ( 2 - 1 2 ) 实验结果表明，a c t i v es v m 对于分类效果有很好的提高，并且动态调整s j 的 主动学习方法要好于t o n g 的s v m a c t i v e 算法。 3 ) b o o t s t r a p p i n ga c t i v es v m 2 s 】 当初始的已标签较少时，s v m 主动学习算法的效果将不是很好。在这篇文献 中，提出了一种将未标签样本引入学习过程中的主动学习算法。在这个算法中， 初始的s v m 分类器由少量的已标签样本和一些随机选择的未标签样本训练得到。 1 4 从理论和实验中，都显示这种引入未标签样本的主动学习算法能够提高主动学习 的效果。 这是一种半监督的学习算法，通过在主动学习开始前引入未标签样本，来减 少需要用户加标签的样本数量。在主动学习开始以后，使用通常的s v m 主动学习 算法。这也是一种通用的方法，也适用于其他的通过已标签样本和未标签样本进 行学习的算法。 4 ) 基于支持向量机的渐进直推式分类学习算法( p t s v m ) 2 9 1 该文献是对直推式学习的进一步研究，试图寻找一个比已有的方法更为普遍 和通用的直推式学习算法。该文献在详细论述直推式学习思想的基础上，基于支 持向量机分类的固有特点，设计了一个支持渐进直推式学习算法的支持向量机分 类器。该分类器使用的渐进判别法充分利用了支持向量机的最优超平面分割特性， 能够在训练过程中有效地对无标签样本循序渐进地做出判别分类，并具有一定的 差错修复能力。同时，通过直推式学习，有效地优化了原始分类器的分类性能， 得到了比直接进行归纳式学习好得多的测试结果。 在这种新的直推式算法中，没有必要事先设定无标签样本中的正标签样本数， 而是在训练过程中，一次选择l - 2 个有可能对后续训练过程产生较大影响的无标签 样本，赋予其当前状态下最可能的标签值，然后，把它们加入到有标签样本中， 并对新得到的有标签样本集重新训练。在这一过程中，动态地调整最优分割平面 并用类似于t s v m 中的方法来渐进地求解式( 1 1 6 ) 所描述的优化问题。由于这种算 法没有对无标签样本中的正标签样本数做出盲目规定，而是在训练过程中渐进地 对无标签样本赋予标签并动态地予以调整，所以可以预期，该算法所产生的分类 器可以更好地描述样本的分布特征，从而具有更好的推广性能。这种算法称为渐 进直推式支持向量机( p r o g r e s s i v et r a m d u c t i v es u p p o r tv e c t o rm a c h i n e ，简称 p t s v m ) 渐进直推式支持向量机训练算法的主要步骤如下： 步骤1 指定参数c 和c ，使用归纳式学习对有标签样本进行一次初始学习， 得到一个初始分类器。 步骤2 用初始分类器对无标签样本进行学习，计算每一个无标签样本的判别 函数输出。用成对标注的法则在当前边界区域内的无标签样本标注一个新的正标 签和一个新的负标签。 步骤3 对所有样本重新训练，计算每一个无标签样本的判别函数输出。如果 发现某一个早期标注的无标签样本的标签值和当前判别函数的输出值不一致，则 按照标签重置的法则取消对该样本的标注 1 5 步骤4 用成对标注法寻找当前边界区域内符合新加标注条件的未标注的无标 签样本。如果存在这样的无标签样本，则对其加以标注并返回步骤3 ；如果不存在 这样的无标签样本，则用当前的分割平面对剩下的全部无标签样本做分类并加标 签。算法结束，并输出结果。 5 ) 其他改进算法3 0 1 经典s v m 训练算法都是把原问题转化为对偶的二次规划问题进行求解。对偶 优化求解存在着计算量大，速度慢，参数选择不具有自适应性的问题。近年来人 们针对s v m 方法本身的特点提出了许多改进的算法。例如s m o ( s e q u e n t i a l m i n i m a l o p t i m i z a t i o n ) 算法、加速分解方法和s v m l i g h t 方法。这些方法使用了所有的训 练样本，共同的思路就是将原问题分解为若干子问题，按照某种迭代策略，反复 求解子问题，直到收敛到原问题的最优解。这些方法本身都是针对调练过程，而 不涉及分类过程，因此分类速度没有明显提高。r s v m ( r e d u c e ds u p p o r tv e c t o r m a c h i n e s ) 方法通过随机选择训练样本子集，减少了训练规模，提高了训练速度。 该方法的缺陷在于随机选择训练样本的数目不同而在不同程度上影响所得分类器 的速度与性能，算法本身缺乏平稳性。l s 2 s v m ( i c a s ts q u a r es u p p o r tv e c t o rm a c h i n e ， 最小二乘支持向量机) 将二次规划问题转化为线性方程组的求解，大大简化了计算 的复杂度。该方法的不足之处在于优化参数更小，因此所得支持向量更多而影响 分类速度，对于非平衡数据分类准确度下降明显。 2 2 2 其他对半监督学习算法的改进 1 ) c b c ( c l u s t e r i n gb a s e dc l a s s i f i c a t i o n ) 1 2 】 在半监督学习算法中，使用有标签样本和未标签样本来构造分类器。尽管未 标签样本可以在一定程度上提高分类器的精确度，但是在有标签样本数量较少并 且与实际的样本分布有较大偏移的时候，仍然有较大困难。在本文献中，提出了 一种基于聚类的分类算法( c l u s t e r i n gb a s e dc l a s s i f i c a t i o n ：c b c ) 。 在该算法有两个步骤：步骤一，训练集中的有标签样本和未标签样本根据有 标签样本进行聚类，步骤二，在扩展后的有标签样本集上训练分类器。这种方法 同样可以使用在t s v m 的分类器