（计算机软件与理论专业论文）基于支持向量机的迁移学习研究.pdf

中山大学硕士学位论文基于支持向量机的迁移学习研究 基于支持向量机的迁移学习研究 专业：计算机软件与理论 硕士生：彭妤 指导老师：印鉴教授 摘要 本文介绍了分类问题的研究背景、研究现状，着重分析了分类领域中具有 重要意义的朴素贝叶斯算法、决策树算法、神经网络算法、k 近邻算法和支持 向量机算法，并讨论了他们的优缺点。 然而，传统的分类算法在训练集和目标集的分布不同时分类效果欠佳，为 了解决这一闯题，近年来分类领域提出了迁移学习的概念，对于小样本问题和 样本不平衡问题，迁移学习方法表现出良好的泛化能力。本文介绍了近年来迁 移学习领域的研究成果，在分析三个重要的迁移学习算法的基础上，总结出迁 移学习的基本思路。 在分析和总结前人工作的基础上，本文提出了一种基于支持向量机的迁移 学习新思路。在该思路的指导下，本文提出了两种针对不同训练数据的迁移学 习算法：k n n s v m 算法和旺1 心玳t s 订算法。这两种算法都是以待分类 数据的分布特征为指导，对训练数据进行筛选，分别计算每个训练样本在训练 时的权重，使得训练集与待分类集的相似度提高，从而达到迁移学习的目的。 与以往的迁移算法不同，本文提出的算法在不引入辅助集的情况下，有效地提 高了训练集与待分类集的相似性，在u c i 的两个非文本数据集和2 0 n e w s g r 0 1 l p s 文本数据集上的实验表明，k n n s 订和( z k n n t s v i 算法都表现出良好 的迁移特性，在相同的训练集和目标集上，其分类精度比不迁移的情况下分别 提高了1 0 6 和1 4 3 l 。 关键词：支持向量机，迁移学习，分类 中山大学硕士学位论文 基于支持向量机的迁移学习研究 r e s e a r c ho ft r a n s f e rl e 锄i n gb a s e do ns u p p o r tv e c t o rm a c h i n e m a j o r ：c o m p u t e rs o f 【、a r ea 1 1 dt h e 0 巧 n 锄e ：y u p e i l g s u p e r v i s o r ：p r o f e s s o rj i a i ly i n a b s t r a c t mt h i s p 叩w e 砷加d u c et l l eb a c k 鲫d 觚dr e s e a r c hp r 0 黟e s s o f c l a s s i f i c a t i o ni l ld a t a m i n i i l g d u r i n gm ei n 昀d l l c t i o n o fs e v e r a l i m p o r t a n t c l a s s i f i c a t i o na l g o r i t l l i i l s ：n a i v eb a y e s ，d e c i s i o nt r e e ，n e u r a ln e ta i l ds u p p o nv e c t o r m a c h i i l e ，w ea n a l y z ea i l dd i s c l l s st l l ea d v a n t a g e sa n dd i s a d v a l l t a g e so fm ea l g o r i m m s h o w e v e r ，m e s e 拄a d i t i o n a lc l a s s i f i c a t i o na l g o r i 1 | n sc 觚n o tp e r f o mw e l lw h e i l m e 慨i l i n gs e ti sq u i t ed i 脑t 舶mm et e s ts e t t od e a lw 池m ep r o b l e i l l ，an e w m e t h o d m m s f i e r1 e 锄i n gh a sm a d el o t so fa 凼e v e i i l e n td u r i n gr e c e l l ty e a r s b a s e do nm e a 1 1 a l y s i so fm r e ei m p o r t a n tt r a l l s f e rl e 锄i n ga l g o r i t h m s ，w ec o n c l u d et h e b 嬲i ci d e 弱d e a l i n gw i ms m a l ls a m p l ep r o b l e m b 嬲e do nm ea i l a l y s i sa b o v c ，w ep r e s e l l tan o v e lt r a n s f 酹l e 锄i n gi d e a ，u n d e r w l l i c hw ep m p o s et w o 饥m s f 打l e a n l i n ga l g o r i t l l m sb a s e do nm es u p p o r tv r e 酏0 r m a c h i n e ，w l l i c hi s 鲥d e db yt l l eu i l l a b e l e dt a 玛e td a t a i i lo r d e rt oi m p r 0 v et h e a c c u r a c y ，b o t l lo ft h en e wa l g o r i l m si n c r e a s em es i m i l a r i t yb e 晰e e nn l et r a i n i n gs e t a 1 1 d 廿l et a 玛雠s e tb y 丘l t e r i n gm eb a dd a t aw h i c hg oa g a i l l s t 也eo p t i m u mh y p e r - p l a n e 丘o mt h e 删i l i i l gs e t ，a n d 孚v i n gl l i 曲e rw e i g h tt om eo n e 讹c h sb e n e f i tf o rm e c l a s s i 丘c a t i o nw 1 1 i l e 仃a i 疵培s i m u l a t i o ne x p 嘶m e n t so nu c id a t a s e t sa 1 1 d2 0 n e w s g r o u p s d a t a s e ts h o wm a t ，t l l e p r o p o s e d k n n s v m a l g o r i t l u n a n d l o 屹- k 1 州- t s a l g o r i t l l i np e r f 0 珊w e l li nt r a i l s 矗言ra 1 1 dm ea c c w a c y a r e10 6 a 1 1 d 1 4 31 r e s p e 以v e l yb 甜e rm 锄t h eo n ew 油o u t 仃a 1 1 s f 醯o na v e r a g e k e y w o r d s ：s u p p o r tv e c t o rm a c l l i n e t r a l l s f 打l e 锄血g ，c 1 a s s i 6 c a t i o n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作者签名：药畸 日期：砌3 年月2 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者签名： 葛呼 日期：枷年【月g 日 导师签名： 日矿厂月矿 中山大学硕士学位论文 基于支持向量机的迁移学习研究 1 1 研究的背景 第1 章引言 当今世界处于一个信息爆炸的时代。据统计，全世界每年出版的图书已经达 到8 0 万种，每一分钟就有一种新书出版。近二十年来，每年形成的文献资料的 页数，仅美国就达到一千七百五十亿页。除此之外，随着互联网的不断发展和壮 大，互联网上的信息量也呈爆炸式的增长势头，截至2 0 0 4 年底，世界最大的搜 索引擎公司g o o 西e 宣称其索引的网页数量已经超过了8 0 亿。另有报告称，全球 印刷信息的生产量每5 年翻一番，近3 0 年来，人类生产的信息已经超过过去5 0 0 0 年信息生产的总和【。种种迹象表明，我们已经来到一个信息爆炸的时代。然而， 我们处理信息的能力却没有随之而增强。我们一方面享受着网络上丰富的信息带 来的便利，另一方面也在忍受着“信息爆炸的困扰。因此，我们迫切地需要一 种帮助用户从网络上提取有价值的信息的技术，也就是数据挖掘技术。为了从海 量的信息里找到有价值的知识或者规则，首先必须将信息按照主题进行分门别 类，以便于组织和管理。而信息量的快速增长，也给信息分类的精度与速度提出 了更高的要求。 随着数据挖掘技术的发展，学者们提出了一系列行之有效的分类算法。特别 是2 0 世纪9 0 年代以来，基于机器学习的自动分类算法借助其高精度、高速度的 有时，在信息分类领域中逐渐地占据了统治地位。如最小二乘模型、最近邻算法、 朴素贝叶斯算法、决策树算法以及神经网络算法等。然而，在这些经典算法中， 普遍存在着一个基本的假设：训练数据集的分布与测试数据集相同。一旦这个假 设不成立，那么传统的分类算法的泛化能力将大打折扣。 然而在现实世界里，数据集往往随时间的变化而变化，在很大程度上无法保 证该假设成立。在网页分类中，在旧网页上训练好的分类模型，在经过一段时间 后，无法对新网页进行准确的分类。因为每天都会产生成千上万的新增网页，这 些新的网页改变了网页集合的分布，从而无法按照旧的分类模型进行分类。数据 集的变化给数据挖掘带来了很多困难，对新数据进行标记，不仅需要花费相当长 的时间采集数据，人工标记的工作量也不容乐观。因此，要在短时间内获得足够 中山大学硕士学位论文基于支持向量机的迁移学习研究 的新的标记数据非常困难。然而，使用过期的旧标记数据训练出的分类器，对未 标记的新数据的分类质量往往欠佳，其主要原因就是，新的未标记数据与旧的标 记数据的分布存在较大的差异。因此，如何能从旧标记数据和少量的新标记数据 中训练出适合未标记数据集的高精度分类器，是一个亟待解决的问题。 1 2 研究现状 众所周知，生物具有迁移学习的能力。迁移是指一种学习对另一种学习的影 响。凡是一种学习对另一种学习起促进作用称之为正迁移，反之，称之为负迁移。 在生活中可以发现，与不会游泳的人相比，会游泳的人更容易学习潜水；与不会 跳国标舞的人相比，会跳国标舞的人更容易学会拉丁舞：与不会法语的人相比， 会法语的人更容易学好英语。在外语学习中，这种迁移现象尤为显著。2 0 世纪 5 0 年代以来形成的与外语学习有关的语言迁移理论，就是要借助于母语的语音、 词义、结构规则或文化习惯，帮助学习者在使用目的语进行交际时表达思想。利 用母语与外语的相似之处，学习者可以在双语对照中获益匪浅，进步很大。 因此，如果能在机器学习领域，运用迁移学习的思想，使分类器在遇到不同 的数据集时，通过自适应的迁移学习，使得分类器能够在未知分布的新数据集中 取得良好的分类效果。 由于标记数据的短缺和数据集分布的快速变化，迁移学习成为近年来数据挖 掘领域的研究热点。n i g 锄将e m 算法和朴素贝叶斯分类器结合起来，对标记数 据和未标记数据进行半监督学习，使得分类精度最多提高了3 0 圆；w u 等人通 过辅助数据集的帮助，使得分类器在小样本的学习过程中，逐步提高分类精度【3 】； z a d r o z i l y 从未标记数据集中寻找样本选择的偏置，来帮助决策树进行分类【4 l ； i b s e i l s t e i i l 提出了一种基于辅助数据集的分级朴素贝叶斯方法【5 1 ；b i c k e l 和 s c h e 行e r 将样本选择偏置用于垃圾邮件的过滤【6 】。 1 3 研究的方向与重点 本文对迁移学习方法进行了研究，深入挖掘了训练集与目标集的共性，针对 不同的数据集，采用半监督和监督学习的方法，以目标集为指导，找到一种能够 2 中山大学硕二l 学位论文 基于支持向量机的迁移学习研究 提高分类精度的迁移学习框架。本文的研究重点是如何挖掘训练集和目标集的共 性，消除有害样本对分类器的误导，通过提高训练集与目标集的相似度，来提高 分类精度。 根据研究重点，本文做了如下的工作： 1 研究和总结近年来迁移学习算法的一般思路； 2 研究总结分类算法、特别是支持向量机理论及其优缺点； 3 提出一种基于支持向量机的迁移学习算法； 4 通过对文本数据和非文本数据进行分类实验，证明本文提出的迁移学习 方法的有效性，并对实验结果进行了分析和比较。 本文的创新之处在于不引入额外的辅助集合，仅仅通过数据挖掘的手段深入 挖掘训练集与目标集的分布特征来达到迁移学习的目的。本文借助聚类的方法挖 掘出待分类集合的特征，以簇集的中心、大小和半径，作为待分类集合的特征， 并以此作为从训练集中选取合适的迁移学习的训练样本的标准，引导分类器进行 分类，从而使得数据分布得以迁移，获得理想的分类效果。 1 4 文章结构 本文共分为六个章节，具体结构如下： 第1 章为引言，介绍了本课题提出的由来和意义，研究的出发点，本文包括 的内容要点、创新之处以及文章结构。 第2 章介绍了几种重要的基于机器学习的分类算法，并分析了当前分类问题 中难点。 第3 章为本文研究的迁移学习的知识背景。重点介绍了三种重要的迁移学习 方法及其特点。 第4 章为本文提出的迁移学习算法。主要包括算法思路，算法描述和算法预 期。 第5 章为实验方法和实验结果。主要包括：实验配置，实验数据集介绍，实 验结果及分析，参数分析等。 第6 章为小结，对本文所阐述的内容进行了总结，并对进一步的研究工作进 行了展望。 中山大学硕士学位论文基于支持向量机的迁移学习研究 第2 章分类问题及支持向量机算法 2 1 分类概况 2 1 1 数据挖掘 数据挖掘( d m ，d a t am i l l i n g ) 【刀是从大量的、不完全的、有噪声的、随机 的实际应用数据中提取出隐含的、未知的、对决策有潜在价值的知识和规则的过 程，是知识发现最关键的步骤。数据挖掘首先要确定挖掘的目标，如进行数据总 结、分类、聚类、发现关联规则、时序模式、趋势分析等等，然后才能决定使用 哪种挖掘算法。再根据应用数据的不同，采取合适的模型和参数，最后达到最初 的挖掘目标。数据挖掘的主要对象是传统的结构化数据仓库，对于非结构化信息， 不能直接使用数据挖掘技术，而要对挖掘对象进行特征提取，满足挖掘要求后才 能使用适当的数据挖掘技术。 2 1 2 分类 分类是数据挖掘中的一项重要技术，也是最广为人知的数据挖掘技术之一。 分类的目的是根据已经分类的样本，找出一个分类的规则或者模型，根据这个模 型就可以把未知分类的样本映射到一个已有的类别中，实现数据的自动分类。分 类和回归都可以用来做预测，但是分类输出的是离散的类别值，而回归输出的是 连续的函数值。分类可以应用于图像与模式识别，医疗诊断，金融证券市场预测 等方面【引。 构造分类模型，一般分为训练和测试两个阶段。在训练阶段，假定每个数据 由一个元组来表示，例如： 。，材：，材。；c ) ，其中为属性值，c 为类别值。通 过各种分类规则和数学公式，让分类模型在训练数据集上不断学习，由于给出了 数据的类别，因此这一阶段是有指导的学习，当学习到分类精度不再提高或者达 到1 0 0 以后，进入测试阶段。测试阶段是用学习好的分类器对测试集中的数据 进行分类，并用得出的分类准确率来评估分类效果，如果对测试集的分类精度达 到一定的水平，则将该分类器应用于其他的数据，进行分类；否则，若分类效果 4 中山大学硕士学位论文基于支持向量机的迁移学习研究 不够理想，分类准确率没有达到可以接受的水平，则需要重新训练。一个好的分 类器或分类规则，应该具有很好的泛化能力，也就说在非训练集的其他数据集上 也能表现出很高的准确性。 2 2 分类算法 近年来，分类算法得到了极大的发展，特别是2 0 世纪9 0 年代以来，机器学 习的引入，使得分类算法无论从精度上还是速度上，都得到了大幅度的提高。基 于机器学习的自动分类算法不仅在分类准确度上与人工分类不相上下，而且在速 度上有人工分类无法比拟的优势。分类算法按不同的理论基础，可以分为以下几 种【9 l o 】： 1 基于统计的算法，如：回归分析模型和贝叶斯分类模型； 2 基于距离的算法，如：k - 近邻算法； 3 基于决策树的算法，如：i d 3 ，c 4 5 和c 5 o 算法，以及c 舢汀算法； 4 基于神经网络的算法； 5 基于统计学习理论的支持向量机算法。 下面将简单介绍几种经典的分类算法，重点介绍本文将要使用的支持向量机 算法。 2 2 1 朴素贝叶斯分类 朴素贝叶斯算法的基本思路是【1 1 】：计算每个类别在训练数据中出现的频率， 来估计每个类别的先验概率。类似的，对于每个属性，也可以计算它在某个类别 中出现的频率。利用训练集中的条件概率和先验概率，就可以计算出待分类数据 的后验概率，而该数据则被分到具有最高后验概率的类别中。朴素贝叶斯方法的 一般步骤如下： ( 1 ) 计算每个属性属于每个类别的概率向量( w ，比，心) ，其中 i d | 1 + ( 形，以) 嵋= p ( 形iq ) = 川i d i m + ( 形，以) j = l = l ，p ( 形iq ) 为属性彬在类别q 中出现的比 5 中山大学硕士学位论文 基于支持向量机的辽移学习研究 重，l d i 为该类别中的训练样本数，( 彬，以) 为属性彬在数据以中出现的频率， 纠吲 y i 为属性的总数，( 形，屯) 为所有属性值的频率之和。 ( 2 ) 对于待分类数据，用以下的公式计算待分类数据d 属于类q 的概率： 尸( dlq ) = 兀尸( 形iq ) ( 2 - 1 ) f = i 其中，p ( 彬iq ) 为属性彬在类别q 中的概率。 ( 3 ) 比较d 属于所有类别的概率，将该文本分到概率最大的那个类别当中。 朴素贝叶斯算法成立的前提是各属性之间相互独立，即属性间满足： 尸( 彬，哌lc ，) = 尸( 形ic ，) p ( kic ，) ( 2 2 ) 因此，当数据集满足这一独立性假设时，分类精度较高，否则，分类精度欠佳。 朴素贝叶斯方法易于使用，并且只需要扫描一次训练数据，节省了训练时间。然 而，在现实数据中，数据的各个属性通常不是独立的，因此在使用贝叶斯方法进 行分类时，要对数据的属性进行预处理，选择只包含独立属性的子集作为分类属 性。 2 2 2 决策树 决策树分类器采用的是分而治之”的分治策略【1 2 】，自顶向下建立一棵决 策树，最终使得同一类别的数据属于同一子树。建立决策树的步骤如下： ( 1 )从属性中选择包含信息最多的属性为特征属性，作为当前节点； ( 2 )按照属性的权重将训练集分类，得到相应的子类，作为决策树的分支； ( 3 )对各个子类进行递归操作，直到子类中的数据都属于同一类别，初步得 到一棵完整的决策树； ( 4 )对决策树进行剪枝，合并部分子树，生成更合理的决策树。 一旦建好了决策树，就可以计算待分类数据对应的子树，从而得到它的分类。 因此，决策树方法可以简单地分为两个步骤：构建决策树和利用决策树分类。 决策树方法的优点在于，决策树易于理解而且分类效率高。由于树的规模独 立于数据库的规模，因此决策时适用于大型数据库的分类，并且具有很好的泛化 6 中山大学硕二t = 学位论文基于支持向量机的迁移学习研究 能力。但是，决策树也存在一些不足。比如，决策树在处理连续属性值上存在困 难，属性值必须划分为不同的类别，变成离散值才能被决策树处理。另外，决策 树是依据训练数据建立的，因此容易出现过学习过拟合的现象。 为了改善决策树算法的分类能力，在其基础上产生了i d 3 算法，其核心思路 是：以信息增益作为各级节点选择属性的标准，使得每一个非叶节点进行测试时， 总能获得被测试记录最大的类别信息。i d 3 算法的具体方法是：检查每一个属性， 选择信息增益最大的属性产生决策树的新节点，依据该属性的不同值建立分值， 以此类推，用递归的方法构造出整个决策树直到所有的子树仅包含同一类别的样 本为止【9 1 。其中信息增益的计算方法如下： j g 口伽( d ，s ) = 日( d ) 一尸( d f ) 日( q ) ( 2 3 ) f = l 其中，日( d ) 和日( 皿) 分别为按照该属性分裂前后的信息熵，烈口) 为分裂后各 个属性值的概率( 权重) 。日( d ) 的计算方法如下： 日( d ) = ( 鼽l o g ( 1 仍) ) ( 2 4 ) 其中只为该样本属于c ；的概率。日( q ) 的算法与之类似，此处不再赘述。 此后，又出现了c 4 5 、c 5 o 以及c a r i t 算法，针对缺失属性值、属性值离 散化和剪枝策略等方面对i d 3 算法进行了改进。 2 2 3k 近邻 k 近邻算法的基本思路是：计算训练样本中与待分类样本距离最近的k 个样 本，根据这k 个样本的类别来判断新文本所属的类别1 4 】。具体的步骤如下： ( 1 ) 根据特征选择将每个样本数据表示为一个特征向量； ( 2 ) 计算待分类数据与所有训练样本的相似度，选择k 个最相似的训练样本。 k 为预先设定的参数，一般为几百到几千之间。对于不同的数据，相似度 函数的算法也不同，这取决于数据之间距离的定义。对于一般的属性数据， 相似度函数可以定义为欧式距离。对于文本数据来说，相似度函数一般定 义为余弦函数： 7 中山人学硕士学位论文基于支持向量机的迁移学习研究 砌( ) 一s ( 西，畋) 2 龋 ( 2 5 ) ( 3 ) 在k 个最近邻中，依次计算每个类别的权重： 尸( d ，q ) = j 拥( d ，4 ) j ，( 应，q ) ( 2 6 ) 其坝鸲) = 牌号。 ( 4 ) 将待分类数据分到权重最大的那个类别中。 k 近邻算法是一种基于实例的分类方法，不需要提前训练分类器，而是等到 需要分类时，才建立分类。因此，k 近邻算法在训练时速度快，但分类时速度较 慢，特别是当待分类数据附近存在大量训练样本时，有很大的计算量，因而分类 速度非常缓慢。 2 2 4 神经网络 神经网络是人类仿照生物大脑的学习机制和工作原理，构造出的类似大脑的 神经网络模型，并借助于这个模型完成分类、预测等学习目标【1 3 】。利用神经网 络求解分类问题主要分为以下几个步骤： ( 1 ) 确定输入的属性数目和输出的结点数目； ( 2 ) 确定网络中的权值和函数； ( 3 ) 对于训练集中的每个样本数据，输入到网络中，根据已有的标记判断输出 值对应的分类是否正确，若输出正确则调整权重，使得这个输出具有更高 的权值。否则，降低该样本的权值，进行下一次的训练； ( 4 ) 训练完成后，将所有待分类数据输入到网络中，网络的输出值对应的就是 该数据的分类。 与其他的算法相比，神经网络算法有很好的鲁棒性，特别是对有噪声的数据 分类时，神经网络算法的泛化能力较强。 2 2 5 其他的分类算法 除了上述几种经典的分类算法外，还有模拟生物进化过程的遗传算法f 1 5 】， 基于关联规则的分类算法【1 6 1 ，基于粗糙集和模糊集的分类算澍1 7 1 ，基于数据库 8 中山大学硕士学位论文基于支持向量机的迁移学习研究 的m i n d 算法等。评价一个分类算法的好坏，主要依据分类的准确率，分类速 度，算法的鲁棒性，处理海量数据的能力以及分类模型的简洁性和可理解性【1 1 。 2 3 支持向量机算法 支持向量机( s u p p o r tv e c t o rm a c h i l l e s ，以下简称s ) 是v 印n i k 等人于 在解决模式识别问题时提出的一种基于统计学习理论的机器学习方法【1 8 】。它的 基本思想是：通过某种事先选择的非线性映射将输入向量x 映射到一个高维特征 空间z ，在这个空间中构造最优分类超平面【1 9 1 。支持向量机建立了一套良好的理 论框架和通用方法，能较好地解决小样本，高维数和局部极小点等实际问题，因 此受到国内外学者的广泛关注，其发展速度非常快【2 0 1 。目前，s v m 已经广泛应 用于手写字识别【2 1 1 ，人脸识别阎，文本分类【2 3 1 ，语音识别冽等方面，取得了良 好的应用效果。 4 0 年前，f r o s e n b l a 仕提出了第一个学习机器的模型，称作感知器，这标志 着人们对学习问题的研究的开始。1 9 6 2 年，n o v i k o f j f 证明了关于感知器的第一 个定理，这一定理实际上是学习理论的开始。随后，人们很快提出了一些其他类 型的学习机器，如b w i d r o w 构造的m a d a l i n e 自适应学习机、k s t e i n b u s h 提出 的学习矩阵等。1 9 8 6 年n h n e h a n 等人提出的用于多层感知器学习的反向传播 ( b p ) 算法引发了人工神经网络的研究热潮。近年来的研究重点在于提出一些解 决问题的新算法和新模型，而所有的算法和模型均以统计学习理论作为统一理 论基础其中比较重要的研究工作如：c o m o n 在1 9 9 4 年首先提出的独立元分析 算法：1 9 9 5 年v a p n i k 等人提出的支持向量机算法【1 9 】。下面首先介绍统计学习理 论中的一些基本概念。 2 3 1 经验风险最小化原则( e i 眦) 记，以蝴表示某输入x 的应有输出y 和实际输出y = k 曲之间的损 失或差异，称为损失函数。 另一种常用的损失函数定义为：工( y ，厂( x ，叻) = ( j ，一厂瓴w ) ) 2 ，损失函数的期 望值称为期望风险( r i s k ) 。它可以表示为： 9 中山大学硕士学位论文基于支持向量机的迁移学习研究 r ( 川= 弘( y ，厂( x ，w ) ) 卵( x ，y ) ( 2 7 ) 其中：f ( 工，j ，) 为z 与y 的联合分布函数。 学习的目的使在函数类( z ，w ) ( w 形) 中寻找使尺( w ) 值最小的函数，实际上 就是确定w 的值，设w o 和厂( z ，) 分别为使r ( w ) 值达到最小的权值和相应的响 应。由于联合分布f ( 五y ) = ，( ylx ) ，( x ) 为未知，所以很难计算期望风险尺( w ) 【1 9 1 。 我们唯一的信息来源是训练集( 而，m ) ，所以要构造经验风险函数： ( 叻= 手喜三( 乃，( 薯，w ) ) ( 2 _ 8 ) 虽然f ( x ，y ) 未知，但是可以用( w ) 代替真正的风险r ( w ) ，令和 厂( 毛) 分别使( 们达到最小的权值和相应的响应，和w o 都属于权空 间，我们要研究在什么条件下近似解厂( 石，) 接近于希望的解厂“) 。对于 某一个固定的权值，风险函数确定了随机变量z w = ( y ，( x ，w ) ) 的数学期望， 而经验风险函数( ) 则是随即变量z 的均值。 根据概率理论，在一般情况下，训练样本数，趋于无穷大时均值收敛于期望 值，但应该注意，仅仅由于z w 的均值趋于它的期望还不能得出“使经验风险 ( w ) 最小的，同时也会使r ( w ) 最小”这个结论。如图2 一l 所示。 r ( w ) ( w ) 图2 1 经验风险最小与期望风险最小的偏差 1 0 中山大学硕士学位论文基于支持向量机的迁移学习研究 为了得到上述结论则需要更强的条件，即经验风险最小化原理。 经验风险最小化原理可简述如下：令表示使经验风险( w ) 最小化的 权值，则在经验风险( 们一致收敛于实际风险r ( w ) 的条件下，( w ) 依概 率收敛于实际风险尺( 们的最小值。即：p s u p k ( w ) 一( w ) 占1 ) 专o ，也就是 “| e 说：当样本趋于无穷时，使经验风险最小化对应的期望奉献，也差不多是最 小的。这就是经验风险最小化原则，即e r m 原则。 2 3 2 最优分类超平面 为了保证经验风险最小化，在支持向量机中，这是通过构造最优分类超平面 来实现的。假设训练数据( 西，y i ) ，( 吃，y 2 ) ，( 西，m ) 可以被一个超平面 ( w 功一6 = 0 ( 2 9 ) 分开。如果这个训练集中没有一个向量被超平面错误地分开，并且离超平面最近 的向量与超平面之间的距离是最大的，那么这个超平面就是这个训练集的最优超 平面。容易验证，最优超平面就是满足以下条件 乃【( w x ) 一6 】1 ，f = 1 ，z ( 2 1 0 ) 且使得 ( 叻= m ( 2 1 1 ) 最小的超平面【1 9 】。如图2 2 所示： 图2 - 2 最优超平面示意图 中山人学硕：l ：学位论文基于支持向量机的迁移学习研究 2 3 3 构造支持向量机 为了找到这个超平面，必须求解式( 2 1 0 ) 和( 2 1 1 ) 组成的二次规划问题。 这个优化问题的解是由下面的拉格朗日函数的鞍点给出： 三( w ，6 ，口) ：丢( w 们一圭q 【( 薯w ) 一6 乃一1 ) ( 2 1 2 ) 三( w ，6 ，口) = 寺( w 们一q 【( 薯w ) 一6 乃一1 ) ( 2 - 1 2 ) 通过分析上述方程式，利用l a 莎a j l g e 优化方法，对式( 2 - 1 2 ) 两边分别对w 和6 求偏导数，令其为o ，可以得到最优超平面的如下特性： 1 系数口? 必须满足约束 掣见= o ，钟o ，扛l ， ( 2 一1 3 ) 2 最优超平面是训练集中的向量的线性组合 ， w o = 咒群蕾，钟o ，江l ， ( 2 1 4 ) ，= l 其中的支持向量是在的展开式中具有非零系数的向量【1 9 】。 根据上述特征可知，拉格朗日乘子和支持向量决定了最优超平面，因此我们 只需要解决一个简单的二次规划问题。 设= ( 掣，钟) 为这个二次规划问题的解，那么基于最优超平面的分类规 则就是下面的指示函数： ，( 功= s 烈辫群( 薯z ) 一易。) ( 2 - 1 5 ) 支持向量 其中毛是支持向量，群是对应的拉格朗日系数，6 。是常数( 阈值，可由任 一支持向量求得，或者通过两类中任一对支持向量取中指求得) ， = 去 ( w o x ( 1 ) + ，( 一1 ) ) 】 ( 2 - 1 6 ) 二 其中石( 1 ) 和，( 一1 ) 分别代表两类支持向量。根据上面的分析，在得到最优分 类超平面后，对于给定的未知数据样本，只需要计算厂( x ) 即可判断工所属的分类。 为了将输入向量映射到高维特征空间，然后在此高维空间构造最优超平面， s v m 算法采用核函数( k e r n e lf u n c t i o n ) 【2 5 】来避免高维空间中的复杂运算，而 1 2 中山大学硕士学位论文基于支持向量机的迁移学习研究 通过原空间的函数来实现内积运算。因此，选择合适的核函数k ( 五，x ，) 就可以实 现某一非线性变换后的线性分类，而计算复杂度却没有增加。所以，带有核函数 的目标函数为： ( 口) = q 一去哆哆m 乃k ( 五，_ ) ( 2 - 1 7 ) 相应的分类函数变为： ( 功= s 盟( 乃q k ( 誓功一6 ) ( 2 1 8 ) 所以，选择不同的核函数，可以构造出不同的支持向量机，常用的核函数有以下 几种【1 9 】： 1 ) 多项式核函数： k ( t ，巧) = 【( 薯) + l 】4 ( 2 _ 1 9 ) 2 ) 径向基核函数： 地州：时呼 协2 。) 3 ) 二层神经网络核函数： k ( 薯，) = t a i l h 【s ( 薯。+ 厂) 】 ( 2 - 2 1 ) 除了以上三种常用的核函数外，还有多维核、正交多项式展开的核、傅立叶 展开的核等各种基于不同需要而生成的核函数。 目前，s 讧主要的应用领域有f 2 6 】：人脸识别、语音识别、文字识别、图像 处理、函数拟合，文本分类等【2 3 ，2 4 ，2 7 ，2 8 1 。其中，最经典的成功试验有：贝尔实验 室用s v l 对美国邮政手写数据库进行识别；m r r 使用s v m 进行人脸识别的试 验【1 9 1 。 2 4 分类中的难点 分类算法发展至今，无论是分类精度还是分类速度，都有了显著的改善。然 而随着信息时代的到来，海量的信息数据给分类提出了新的挑战。在分类问题中， 仍然存在以下难点问题。 1 3 中山大学硕士学位论文基于支持向量机的迁移学习研究 2 4 1 属性特征选择 由于过多的属性会给训练时间和空间带来很大的开销，特别是在文本分类 中，一个文本数据的维度可能是几千甚至上万，因此，人们称之为“维数灾难 。 同时，属性间存在着各种关系，这些关系对分类算法的效果具有显著的影响，例 如贝叶斯算法中要求属性间互相独立。因此，如果挖掘出属性间的关系，对属性 进行选择和抽取【2 9 1 ，一方面能够降低数据的维度，节省训练时间和空间，提高 分类效率：另一方面也能避免属性间的关联对分类算法的影响。然而不同的数据 源于不同的背景，目前还没有找到一种通用的属性筛选的方法。 2 4 2 小样本问题 采用监督学习方法一个主要困难是需要大量标记的训练样本。而在实际工作 中，获得的标记样本需要花费大量的人力物力。因此分类器能够获得的训练样本 是非常有限的。然而，小样本往往不能刻画出整个数据集的总体分布特征，因此 导致分类效果欠佳【3 0 1 。因此，从少量标记样本或者大量未标记近似样本中训练 出分类精度较高的分类模型是分类问题中的一个难题。 2 4 3 样本不平衡 样本不平衡问题【4 6 1 是指某些大类占据了大部分的训练样本，而其余的类别 只包含少数的样本。从这样的训练集合中训练得到的分类模型，由于学习到的大 部分是大类的特征，因此对大类的分类精度很高，而对小类的分类精度很低。针 对这一问题，学者们提出了三类方法：取样、误差加权和识别。 2 4 4 参数的确定 很多分类算法都需要设定参数，然而对于不同的分类数据，其最适合的参数 也不一样。如何让算法自动选择较好的参数，在算法的执行过程中，自适应的调 整参数设置，是很多算法在应用上必须解决的关键问题。 2 4 5 海量信息 由于信息量的迅速增加，如何高效地存储和处理与日俱增的海量信息，也是 1 4 中山大学硕士学位论文 基于支持向量机的迁移学习研究 分类算法必须解决的问题。目前的分类算法在数据量剧增的情况下，分类速度往 往不尽如人意，因此，未来的分类算法必须在时间和空间复杂度上有所提高，才 能保证其对海量信息的处理能力。 2 5 本章小结 本章主要介绍了分类问题的背景和研究现状。针对经典的贝叶斯、决策树、 k 近邻和神经网络算法，逐一进行了简单的介绍，分析了各个算法的优缺点。本 章着重描述了支持向量机算法的基本思路，理论基础、一般步骤等，为后文中支 持向量机的运用做了铺垫。最后，本章讨论了分类算法面临的几个难题，以及目 前在这些问题上的进展情况。 1 5 中山大学硕：j 二学位论文基于支持向量机的迁移学习研究 3 1 迁移学习研究 第3 章迁移学习 迁移学习的研究起源于训练集和目标集的分布不同导致的学习效果欠佳 【3 1 1 。在现实中采集到的数据集，受到时问等因素的影响，无法保证训练集与将 来获得的目标集合不同的分布一致，而传统的学习算法都只能保证训练集和目标 集分布相同的前提下，保证其学习效果【5 】。 在分类问题中，如果摒弃旧的数据集，重新足够多的目标数据，并一一标记， 需要耗费大量的时间和人力。特别是在网页分类过程中，网页的分布随时间而变 化，刚刚标记好的数据集往往与现在的目标集存在差异。因此，如果能利用迁移 学习方法，从目标集和原有的训练集中找出一些通用特征，以及它们的不同之处， 从而指导学习器进行有目的的学习，就能在不重新搜集数据或者搜集少量数据的 情况下，有效地提高分类效果。迁移学习就是从与目标集不一致的训练集中，寻 找有利于提高学习效果的因素，学习出适用于目标集的学习器。在现实问题中， 迁移学习方法能显著地提高的学习效果，因而受到学者们的瞩目，成为机器学习 研究领域上的一个热点，3 2 3 5 1 。 学习的目的是通过有限数量的训练样本观测、学习，发掘出隐含在训练样本 背后的规律( 表现为显式或隐式的函数形式) 【捌。下面从三部分来描述样本学 习的一般模型： 产生器( g ) ( 又称环境) ：它是被学习的对象，产生随机向量x r ，他们 是从固定但未知的概率分布函数f ( 工) 中独立抽取的。 训练器( s ) ( 又称教师) ：它本身存储了有关环境的知识，因而可对每一个 输入向量x 返回一个输出值y ，产生输出的根据同样是固定而未知的条件分布函 数f ( yl 功。 学习机器( m ) ( 又称算法或网络) ：它可以实现一定的函数集厂( 工，口) ，口a ， 其中a 是一组自由的参数集合。 1 6 中山大学硕士学位论文基于支持向量机的迁移学习研究 如图3 1 所示。 i g l l s ， 一 l 一 1 r 1 ， r lm1 1 ， 。 l r 图3 一l 学习模型 根据上述模型，在学习过程中，观察数据对( x ，j ，) ( 训练集) 在训练之后， 学习机m 须对任意输入x 给出输出y ，使之最接近训练器s 的响应( 应有的输出) j ，。也就是说，学习问题就是在一组给定函数集( 某固定结构的网络) 中选择出 能最佳逼近训练器的响应y 的函数y = 厂( x ，货) ( 如通过调节权值) 。这种选择是 基于训练集的。训练集由联合分布函数f ( x ，y ) = ，( x ) f ( yix ) 抽取出的，个独立分 布的观测值：( 五，少。) ，( 艺，咒) ，( 薯，乃) 组成。 一般而言，学习方法有三种：监督学习、非监督学习和激励学习。 监督学习( s u p e i s e d - l e a n l i n g ) ：在这种学习方式中，外界环境里存在训练 器“教师 ，他可对一组给定输入提供应有的输出。结果这组已知的输入输出数 据对称为训练样本集。学习系统可根据已知输出与实际输出之间的差值来调节系 统参数。由于训练样本已经有概念标记，因此监督学习的训练精度较高，但泛化 能力较差，易出现过学习的现象。 非监督学习( u i l s u p e 州s e d l e a m i n g ) ：这种学习方式不存在外部训练器，学 习系统完全按照环境提供的数据、统计规律和学习规则来调节自身参数或结构。 非监督学习通过对没有概念标记的训练样本进行学习，因此其训练精度较低，但 泛化能力较高。 激励学习( s t r e i l g t l l e i l 一1 e a l i n g ) ：这种学习介于上述两种情况之间，外部环 境对系统输出结果只给出评价而不给出正确结果，学习系统通过强化那些受奖励 的操作来改善自身性能。 此外，还存在一种半监督学习( s e m i - s u p e n ，i s e dl e 锄i n g ) ，它用未标记的样 本来辅助对已标记样本的学习。这与监督学习、非监督学习、强化学习等天生的 1 7 中山大学硕士学位论文基于支持向量机的迁移学习研究 歧义性完全不同。 由于监督学习的泛化能力较差，因此迁移学习经常使用的一种方法是半监督 学习，通过未标记的新数据来辅导对已标记的旧数据的学习，训练出适合新数据 的分类器。因此，本文所采用的学习方法是半监督学习。 3 2 几种典型的迁移学习算法 3 2 1 基于辅助集的迁移算法 基于辅助数据集的迁移算法【3 】通过利用与训练集和目标集不同的辅助数据 集合来提高k 近邻算法和支持向量机算法的分类精度。因此，该算法适用于训 练样本不足以训练出一个分类精度较高的分类器的情况，通过辅助数据集的帮 助，使得分类器在小样本的学习过程中，逐步提高分类精度。 为了达到迁移学习的目的，基于辅助数据集的迁移算法对目标函数进行了改 进，在原有的目标函数 ，( i l ) = ( j i l ( t ) ，m ) + 加( 厅) ( 3 - 1 ) ， 的基础上，加入了辅助集的损失函数： n pn n ，( 办) = ( 办( 鼍p ) ，m p ) + y 三( 办( t 口) ，m 口) + 兄d ( 厅) ( 3 2 ) ff 其中：为估计损失函数，p ，4 分别为训练集和辅助集的大小，d ( j 1 ) 为为 了防止过学习而设置的惩罚函数，y ，五为平衡各部分损失的参数。 对于k 均值算法中，增加了辅助数据集的投票权，并与训练集的投票结果 一起加权得到样本最终的分类结果： y ( c ) = 耿y p ( c ) k p ) + ( 1 一目) ( y 4 ( 力k 4 ) ( 3 3 ) 其中参数臼用来平衡原训练集中k p 个最近邻和辅助集中k 4 个最近邻对分类结 果的影响。 与改进的k 均值算法类似，改进后的s v m 算法采用将原训练集与辅助集同 时学习的策略，在原规划的目标函数和约束条件中，分别增加辅助集的惩罚函数 1 8 中山大学硕士学位论文 基于支持向量机的迁移学习研究 和约束条件，使s 在迭代学习