（计算机应用技术专业论文）基于支持向量机的文本分类研究.pdf

硕+ 牛、! k 沦史 摘要 i n t e r n e t 作为一个开放的信息空间，近年来得到了飞速发展，已经成为人们进行信 息交互和处理的有效平台。但随着i n t e r n e t 上信息量的爆炸式增长，人们很难从大量的 信息中迅速有效地获得所需的信息。为了快速地帮助用户找到所需的信息，有效地利用 这些信息，就需要对信息进行分类组织管理。文本信息在网络信息资源中占有很大分量， 因此文本自动分类技术的研究就显得尤为重要。 统计学习理论是一种专门研究小样本情况下机器学习规律的理论。支持向量机是建 立在统计学习理论基础之上的机器学习方法，它克服了神经网络分类和传统统计分类方 法的许多缺点，具有较高的泛化性能。 本文以自动文本分类的过程为主线，在深入研究了文本表示、特征提取和重构以及 分类算法的基础上，提出了一种基于最小二乘支持向量机和潜在语义分析的网页分类算 法。首先研究了网页文本的特征提取算法。与文本数据不同，网页数据是一种半结构化 的数据，在网页表示中，对任一特征而言，有两个因素影响特征的权值：一是词在h t m l 文档中出现的词频，另一个是该词在该文档中出现的位置。在研究了文本特征提取算法 的基础上，根据网页特征的特殊性，对网页文本特征提取和加权算法进行了改进。潜在 语义分析通过奇异值分解获得原始词文档矩阵的潜在语义结构，在一定程度上解决 了一词多义和多词一义的问题，最小二乘支持向量机在大数据集上学习效率比较高，特 别是在获得有标签样本成本较高的情况下。本文采用了一种新颖的网页特征权重计算方 法，并利用摘要算法消除网页噪音，在保证了网页分类的准确性不变的情况下，提高了 分类器的学习效率。 最后，通过从网络采集的中文语料库，共1 2 6 8 4 篇中文文档，其中9 0 0 0 篇用来训 练，3 6 8 4 篇用于测试，对算法进行了验证，取得了较好的分类效果，这充分证明算法是 有效的。 关键词：文本分类；支持向量机；特征选择；特征重构；直推式学习 i i i 荩+ r 芰打向昂帆的文本分燮研究 a b s t r a c t i n t e m e tr e g a r da sa no p e ni n f o r m a t i o ns p a c e s ，h a sas p e e d yd e v e l o p m e n t r e c e n ty e a r s i th a sa l r e a d yb e e na ne f f e c t u a lp l a t f o r mw h i c hp e o p l ec a nt r a n s m i t a n dd i s p o s ei n f o r m a t i o no ni t b u to w i n gt ot h er a p i di n c r e a s eo fal a r g e q u a n t i t yo fi n f o r m a t i o no nt h ei n t e r n e t ，p e o p l ea r ed i f f i c u l tt os p e e d i l ya n d e f f i c a c i o u s l yg e tt h en e e d f u li n f o r m a t i o n f o rt h es a k eo fh e l p i n gr a p i d l yt h e u s e r sf i n dt h en e e d f u li n f o r m a t i o na n dt a k i n ge f f i c a c i o u s l ya d v a n t a g eo ft h i s i n f o r m a t i o n ，i ti sn e c e s s a r yt oc l a s s i f y , a r r a n g ea n dm a n a g e t h ei n f o r m a t i o no f t e x t sh a sal a r g ep r o p o r t i o no ft h ew e bi n f o r m a t i o n ，s ot h er e s e a r c ha b o u tt h e t e c h n i q u eo ft h ea u t o m a t i o nt e x tc l a s s i f i c a t i o nl o o k si m p o r t a n te s p e c i a l l y s t a t i s t i c st h e o r yi st h et h e o r yo ft h em a c h i n el e a r n i n gr u l ei nc a s eo f s p e c i a l l ys t u d y i n gt h es m a l ls a m p l e s u p p o r tv e c t o rm a c h i n ei st h em e t h o do f m a c h i n el e a r n i n go nt h eb a s i so ft h es t a t i s t i c st h e o r y i to v e r c a m eal o to f s h o r t c o m i n g sb o t ht h en e r v e n e t w o r kc l a s s i f i c a t i o na n dt h et r a d i t i o n a ls t a t i s t i c a l c l a s s i f i c a t i o n ，a n dh a dh i g h e rg e n e r a l i z a t i o np e r f o r m a n c e t h i st h e s i sr e g a r d st h ep r o c e s so ft h ea u t o m a t i ct e x tc l a s s i f i c a t i o na st h e t h r e a d o nt h eb a s i so ft h ed e e p - s e a t e ds t u d yo ft h et e x tr e p r e s e n t a t i o n ，t h e f e a t u r ee x t r a c t i o n ，t h ef e a t u r er e c o n s t r u c t i o na n dt h ec l a s s i f i c a t i o na l g o r i t h m ， p r e s e n t sac l a s s i f i c a t i o na l g o r i t h mo ft h ew e bp a g e sw h i c hb a s e so nt h el e a s t s q u a r es u p p o r tv e c t o rm a c h i n ea n dt h el a t e n ts e m a n t i ca n a l y s i s a tf i r s t ，w e s t u d i e dt h ea l g o r i t h mo ff e a t u r e se x t r a c t o i no fw e bp a g e s w e bp a g ed a t aa r e s e m i - s t r u c t u r e dd a t ad i f f e r e n tf r o mt e x td a t a i nw e bp a g ee x p r e s s i o n ，t h e 硕十毕、i k 论文 w e i g h to fe v e r yf e a t u r ei si n f l u e n c e db yt w of a c t o r s o n ei st h ef r e q u e n c yt h a t t h ef e a t u r ea p p e a r si nt h eh t m ld o c u m e n t ；t h eo t h e ri st h ep l a c ew h e r et h e f e a t u r ei si nt h i sh t m ld o c u m e n t o nt h eb a s i so f s t u d y i n gt h ea l g o r i t h mo f t e x t f r e a t u r ee x t r a c t i o n ，w ei m p r o v et h ea l g o r i t h mo fw e bp a g ef e a t u r ee x t r a c t i o na n d w e i g h t i n ga c c o r d i n gt ot h ep a r t i c u l a r i t yo fw e bp a g ef e a t u r e l a t e n ts e m a n t i c a n a l y s i sg e t st h el a t e n ts e m a n t i cs t r u c t u r eo ft h et e r m d o c u m e n tm a t r i xw i t h s i n g u l a r i t y v a l u e d e c o m p o s i t i o n ，t o ac e r t a i n e x t e n t ，w h i c h s e t t l e st h e p o l y s e m o u sa n ds y n o n y m o u sp r o b l e m l e a s ts q u a r es u p p o r tv e c t o rm a c h i n eh a s h i g hl e a r n i n ge f f i c i e n c yo nt h el a r g ed a t a s e t ，s p e c i o u s l yu n d e rt h ec i r c u m s t a n c e s o fo b t a i n i n gt h el a b e ls a m p l ec o s t l y a d o p t i n gt h ea l g o r i t h mo fan o v e lw e b p a g ef e a t u r ew e i g h ta n du t i l i z i n gt h es u m m a r i z a t i o na l g o r i t h mc l e a rt h ew e b p a g en o i s e ，a n di m p r o v et h ea c c u r a c yo ft h ew e bc l a s s i f i c a t i o n f i n a l l y , w eg a i nt h ec h i n e s ec o r p u sf r o mt h ei n t e m e t ，w h i c hh a s 12 ，6 8 4 c h i n e s ed o c u m e n t s ，i n c l u d i n gw h i c h9 0 0 0a r t i c l e sa p p l yt ot r a i na n d3 ，6 8 4 d o c u m e n t sa p p l yt ot e s t ，t h ea l g o r i t h mi sv e r i f i e da n dg a i nam o r ec l a s s i f i c a t i o n e f f e c t ，a sw e l la st h ei m p r o v e m e n to ft h ea l g o r i t h mi se f f e c t i v e k e y w o r d s ：t e x tc l a s s i f i c a t i o n ；s u p p o r t v e c t o rm a c h i n e ；f e a t u r es e l e c t i o n ； f e a t u r er e c o n s t r u c t i o n ；t r a n s d u c t i v el e a r n i n ga l g o r i t h m v 堆下支持向嚣机的文本分娄研究 插图索引 图1 1文本分类过程图2 图2 1机器学习的一般模型1 0 图2 2 结构风险最小化原则示意图1 5 图2 3 最优分类超平面l6 图2 4 输入空间到特征空间的映射l8 图3 1潜在语义分析矩阵分解2 8 图5 1矩阵奇异值分解3 7 图5 2l s s v m 。s v ma n dk n n 查准率对比图4 l 图5 3l s s v m ，s v ma n dk n n 查全率对比图4 2 图5 4l s s v m 。s v ma n dk n nf 值对比图4 3 图5 5s v m 和l s s v m 训练时间对比图4 3 v i 硕十牛、! k 论史 附表索引 表l数据集4 0 表2l s s v m s v ma n dk n n 的杏准率4 l 表3l s s v m s v ma n dk n n 的查全率4 2 表4l s s v m ，s v ma n dk n n 的f 值4 2 表5s v m 和l s s v m 训练时问对比4 3 v i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者虢超支式 嘿枷哆年r 月邮 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名搜支式 导师签名： 砚扎 日期：h 刁年6 月，。日 日期：坷年多月，夕e l 硕十牛、论文 _ m i i 一。一i 一皇蔓曼一一 一! 曼曼 曼一一i i 皇曼曼皇量皇曼皂舅舅曼曼曼皇曼置 第一章绪论 1 1 研究背景 i n t e m e t 作为一个开放的信息空间，近年来得到了飞速的发展，已经成为人们进行 信息交互和处理的有效平台。其中以文本形式表示的信息以极高的速度增长，面对如此 巨大的信息资源，人们很难迅速有效地获取所需信息，为了方便用户有效地检索和利用 i n t e m e t 信息资源，就需要对这些信息进行分类处理，以帮助用户快速查找有价值的信 息。在当前g b ，t b 级的文本集上，人工分类显然已不能适应。因此，如何利用计算机 有效地组织和分析海量的信息资源，使人们能够按照内容实现对文本的自动分类，帮助 用户迅速地获取其所需的知识和信息，已成为计算机科学发展的必然选择，且具有广泛 的应用前景和实用价值。 1 2 研究意义 文本分类( t e x tc a t e g o r i z a t i o n ，简称t c ) 技术是信息检索和文本挖掘的重要基础，其 主要任务是在预先给定的类别标记集合下，根据文本内容判定它的类别。利用文本分类 技术可以把数量巨大但缺乏结构的文本数据组织成规范的文本数据，帮助人们提高信 息检索的效率。通过对文本信息进行基于内容的分类，自动生成便于用户使用的文本分 类系统，从而可以大大降低组织整理文档耗费的人力资源，帮助用户快速找到所需信 息。 研究文本分类技术的实际概括如下： 1 节约人力资源。在互联网“信息爆炸的今天，在当前g b ，t b 级的文本集上， 若用人工进行分类，耗费的人力资源可想而知。考虑到计算机运算速度快和准确性高的 特点，利用计算机进行文本自动分类，不仅节约了人力资源，而且提高了分类的准确性。 2 提高信息检索效率。i n t e r n e t 的信息大多为非结构化的，其内容杂乱无章，组织管 理难度大，人们很难从大量的无组织的信息中迅速有效地获取自己所需信息，利用文本 分类技术可以把数量巨大但缺乏结构的文本数据组织成规范的文本数据，帮助人们提 高信息检索的效率。 3 文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有 着广泛的应用。2 0 世纪9 0 年代逐渐成熟的基于机器学习的文本分类方法，更注重分类器 模型的自动挖掘和生成及动态优化的能力，在分类效果和灵活性上都比之前基于知识工 程和专家系统的文本分类模式有所突破，成为相关领域研究和应用的经典范例。 1 3 研究现状 幕于支打向爱 l 的文本分类研究 詈曼量曼曼曼曼曼曼曼曼曼量量舅l 一 i i 一 ；一 i i 曼曼量曼曼量曼曼曼曼曼曼量曼舅 1 3 1 文本分类研究进展总体分析 国外在自动文本分类以及相关的信息检索、信息抽取领域进行了较为深入的研究。 八十年代，自动文本分类以知识工程的方法为主，根据领域专家对给定文本集合的分类 经验，人工提取出一组逻辑规则，作为计算机自动文本分类的依据。进入九十年代，基于 统计的自动文本分类方法日益受到重视，它在准确率和稳定性方面具有明显的优势n 1 。 到目前为止，国外的文本自动分类研究已经从最初的可行性基础研究经历了实验性研 究进入实用的阶段，并在邮件分类、电子会议、信息过滤方面取得了较为广泛的应用乜1 。 国内对文本分类研究比较晚，1 9 8 1 年，侯汉清教授首先探讨和介绍了国外文本分 类的研究情况。1 9 8 6 年，上海交大电脑应用技术研究所的朱兰娟、王永成等开发了中 文科技文献( 计算机类) 实验性分类系统。1 9 9 5 年，清华大学电子工程系的吴军研制的 汉语语料自动分类系统，以语料相关系数作为分类依据，以字频、词频及常用搭配为补 充，采用停用词表排除非特征词，进行人工指导分类。1 9 9 8 年，东北大学计算机系的 张月杰、姚天顺研制的新闻语料汉语文本自动分类模型，通过计算预定义类别和文本特 征项之间的相关性来进行自动分类。1 9 9 9 年，邹涛、王继成等开发的中文技术文本分 类系统c t d s ( c h i n e s et e c h n i c a ld o c u m e n tc l a s s i f i c a t i o ns y s t e m ) 采用了向量空间模型 和基于统计的特征词提取技术，能够根据文本的具体内容将其分配到一个或多个类别。 近年来，将文本简化为所谓的b o w ( b a go f w o r d s ) ，在特征处理和统计学习算法的 基础上获得对文本语义内容及类别信息的估计与预测，已经成为文本分类的标准模式。 图1 1 所示为文本分类过程，由人工正确分类的语料库起，经过预处理形成便于计算机 处理的结构化特征数据，特征数据与分类算法相结合形成分类器，待分类文本经预处理 后形成文档特征向量，输入分类器进行判断得出分类结果。 图1 1 文本分类过程图 1 3 2 文本表示、特征提取和降维技术的研究进展 最常用的文本表示模型是由g s a l t o n 等人提出的向量空间模型( v e c t o rs p a c em o d a l ， v s m ) 1 。v s m 是基于这样一个关键假设，即文章中词条出现的顺序是无关紧要的，他们 2 硕+ 中、f k 论文 对于文档的类别所起的作用是相互独立的，因此可以把文档看作一系列无序词条的集 合。在该模型中，文档空间被视为一组正交词条向量组成的向量空间，每个文本谚都可 以映射为此空间中的一个特征向量，v ( 4 ) = ( 0 n ，w 。) ，( t ：，w ：) ，( 屯，嵋。) ) ，其中，为词 条项，权重嵋，表示特征项t ，对文本z 分类的贡献程度，文本z 简化为以特征项权重为 分量的向量( 彬，w ：，) 表示，文本信息的匹配问题转化为向量空间中的向量匹配问 题，大大减小了问题的复杂性h 1 。 常用的关于特征向量的降维技术有特征选择和特征重构。特征选择是通过某种方法 挑选出对分类最有用的部分特征，以此来降低特征矩阵的维数。特征选择算法一般是构 造一个权重函数，对特征集中的每一个特征进行独立的评估，这样每个特征都获得一个 评估分，然后对所有的特征按照其评估分的大小进行排序，选取预定数目的特征作为结 果的特征子集。主要的方法有睁7 1 ：文本频数( d o c u m e n tf r e q u e n c y ，d f ) 、信息增益 ( i n f o r m a t i o ng a i n ，i g ) 、互信，皂, ( m u t u a li n f o r m a t i o n ，m i ) 、开方校验( c h i - - s q u a r e ) 、期 望交叉熵( e x p e c t e dc r o s se n t r o p y ) 、优势率( o d d sr a t i o ) 、文本权 = i e ( t h ew e i g h to f e v i d e n c e f o rt e x t ) 等哺1 。 特征重构是依据某一原则构造从原始特征空间到新的低维特征空间的一个变换，是 将分散在众多原始特征中的分类信息集中到少量的新特征上，重新生成一个维数更低， 特征之间更独立的特征空间。目前主要有两种：特征词聚类( t e r mc l u s t e r i n g ) 和潜在语义 分析( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) 。 1 3 3 文本分类算法分析 文本分类的核心问题是如何根据语料库构建一个分类函数或分类模型，并利用此分 类模型将未知类别文本映射到指定的类别空间。目前文本分类的算法有：1 ) 基于概率的 朴素贝叶斯分类算法阳3 ：2 ) 基于实例的k 最近邻算法( k n e a r e s tn e i g h b o r s ，州) n 伽：3 ) 基 于规则的决策树算法( d e c i s i o nt r e e s ，d t ) ：4 ) 基于结构风险最小( s t r u c t u r a l r i s k m i n i m i z a t i o n ，s r m ) 原理的支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 算法n 玎：5 ) 神经 网络算法( n e u r a ln e t w o r k ，n n ) 。 1 朴素贝叶斯分类算法( n a i v eb a y e s ，n b ) 贝叶斯分类器是一种典型的基于概率统计的分类器n2 | 。其数学基础是贝叶斯定理， 主要思想就是计算在给定一待分类文档的条件下其属于各个类别的条件概率，然后选择 条件概率最高的那个类别为该文档所属的类别。朴素贝叶斯分类器是基于一个条件独立 性假设( 朴素假设) ，即假设一个文档中任何两个特征词之间的出现与否是相互独立的。 令论域u = ( w ，w 2 ，c ) 是离散随机变量的有限集，其中w ，嵋，为特征项 集，类变量c 的取值范围为( c 1 ，c ：，q ) ，一个文档z 表示为特征向量( 嵋，) ， 则谚属于类c ，的概率可表示为： 幕f 乏持向晕机的文本分类研究 北，川) = 盟羔掣 ( 1 3 1 ) 根据概率的链规则： p ( w l ，w 2 ，ic ) = 兀p ( w iw , ，w 29 * * * 9 嵋1 ，o )( 1 3 2 ) l = 1 朴素贝叶斯分类模型中的属性独立假设假定所有的属性都是相互条件独立，即： p ( w ，fw l ，w 2 ，w i 1 ，c j ) = p ( w flc j ) ( 1 3 3 ) 结合公式( 1 3 2 ) 、( 1 3 3 ) ，公式( 1 3 1 ) 则变为： 兀p ( w ic j ) p ( c ，) p ( c ，iw l ，w 2 ，w n ) = 型j _ ( 1 3 4 ) 。 p l ，w 2 ，kj 根据贝叶斯最大后验准则，给定某一待分类文本z = ( ，w 2 ，) ，贝叶斯分类器选择 使后验概率p ( c ，iw i ，w 2 ，。，) ) 最大的类作为该文本的类标签。朴素贝叶斯的独立性假 设提高了分类的效率，但在实际应用中这种独立性假设是不太可能满足的。 2 k 最近邻算法( k n e a r e s tn e i g h b o r s ，k n n ) k n n 算法是由c o v e r 和h a r t 于1 9 6 8 年提出的，是一种基于实例的学习方法n 3 14 1 。算法 的基本思想是：根据v s m 模型，文本以特征向量的形式定义到实数域中。计算一个测试 文本与训练样本集中每个文本的相似度，相似度一般使用标准欧式距离测量，找出测试 文本的k 个最近邻居，并按k 个邻居的类别分开统计，把测试文本划分到最相近的一类 中去。具体算法可描述如下： ( 1 ) 采用v s m 模型，根据文本特征词形成测试文本特征向量矩阵。 ( 2 ) 计算测试文本与训练集中每个文本的文本相似度，一般应用余弦定理： 丛 既 s i m i l a r i t y ( d r ，嘭) = c o s ( d , ，t ) 2 下萨气一 ( 1 3 5 ) 1 ( 暖) ( 形力 i = lk = i 其中，z 为测试文本的特征向量，d ，为第_ 类的中心向量，m 为特征向量的维数。 k 值的确定须根据试验测试结果进行调整。 根据相似度，在训练文本集中选出与新文本最相似的k 个文本。 ( 3 ) 在测试文本的k 个邻居中，应用下面的公式依次计算每类的权重： p ( x ，q ) = s i m i l a ，i t y ( x ，d , ) y ( d j ，q ) ( 1 3 6 ) a i e 蹦拍 4 硕十毕、f p 论文 其中，；为测试文本的特征向量， s i m i l a r i t y ( x 一，d 一，) 为相似度计算公式，而y ( 刁，q ) 是类别属性函数，即当z 属于c ，时，函数值为1 ，否则，函数值为0 。 ( 4 ) 比较类的权重，将文本分到权重最大的那个类别中。 3 决策树算法( d e c i s i o nt r e e s ，d t ) 决策树方法n 5 1 起源于2 0 世纪6 0 年代的概念学习建模，后期q u i n l a n 提出了用信息增 益作为启发策略的i d 3 方法，该方法通过对样本的学习来构造专家系统：同时b r e i n a m 和 f r i e d m a n 提出了c a r t ( 分类与回归树) 方法，该方法类似于i d 3 ：1 9 9 3 年q u i n d a n 提出了 改进决策树归纳包( c 4 5 ) ，这些方法都是目前被普遍采用为分类方法。 决策树可视为一棵树状的预测模型，树的根节点是整个数据集合空间，每个分节点 是一个分裂问题，它通过对属性的测试，该测试将数据集合空间分割成两个或更多块， 每个叶节点可看作满足一定属性的具体类别。从决策树的根节点到叶节点的一条路径就 形成了对相应对象的类别预测。决策树建树的算法有很多，例女i i i d 3 n 刮，c l s ，c 4 5 7 1 ， c a r t ，s l i q ，s p r i n t ，m e d g e n 和m e d g e n a d - j u e t 算法等等。这些算法均采用自顶向下 的贪婪算法，在每个节点选择分类效果最好的属性将节点分裂为两个或多个子节点，继 续这一过程直到这棵树能准确地分类训练样本，或所有属性都已被使用过。决策树的核 心问题是选取测试属性和决策树的剪枝。决策树是实例( 表示为特征向量) 的分类器，节 点表示测试特征，边表示特征的每个值，叶节点对应分类。从根到叶节点的一条路径就 对应着一条规则，整个决策树就对应着一组析取表达式规则。 4 神经网络算法( n e u r a ln e t w o r k ，n n ) 神经网络n8 1 们系统是由大量的、同时也是很简单的处理单元( 或称神经元) ，通过广 泛地互相连接而形成的复杂网络系统。虽然每个神经元的结构和功能十分简单，但由大 量神经元构成的网络系统的行为却是丰富多彩和十分复杂的。 神经网络文本分类问题包括两个阶段：网络训练阶段和网络工作阶段。在网络训练 前期，将训练集映射到向量空间模型上，从而转化为神经网络识别的数据结构。网络训 练时，把输入层的数据经过隐含层传递到达输出层，输出结果与预定的结果存在误差， 这个误差反向传播修正节点连接权，直到误差小于给定的要求为止。经过网络训练后稳 定下来的权值就是作为文本分类时的知识，利用它完成在网络工作阶段对文本进行正确 分类的任务。 神经网络系统是一个高度复杂的非线性系统，不但具有一般非线性系统的共性，更 主要的是它还具有自己的特点，比如高维性、神经元之间的广泛互连性以及自适应性或 自组织性等。经过多年的发展，目前已有上百种的神经网络模型被提出。 幕于支持向晕：机的艾本分炎研究 5 支持向量机算法( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 支持向量机( s v m ) 陋2 3 1 是i - ! - 1 v a p n i k 提出的一种基于结构风险最小化原则的机器学习 方法，是统计学习理论中最年轻的内容，也是最实用的部分乜4 ，2 副。支持向量机的基本思 想是这样的：首先把训练数据集非线性地映射到一个高维特征空间( 这个高维特征空间 是h i l b e r t 空间) ，这个非线性映射的目的是把在输入空间中的线性不可分数据集映射到 高维特征空间后变为是线性可分的数据集，随后在特征空间建立一个具有最大分隔距离 的最优分类超平面，这也相当于在输入空间产生一个最优非线性决策边界。 要实现上述的思想，根据实际问题构造一个支持向量机，必须解决两个关键的技术 问题1 ：( 1 ) 如何找到一个非线性映射，通过该映射把输入空间中的线性不可分数据集 映射到高维特征空间中的线性可分数据集；( 2 ) 在高维特征空间中如何确定最优分类超 平面。对于这两个问题，将在后面章节中详细给出解答。 1 3 4分类器性能评价 评估分类准确程度的依据是通过专家对文本的正确分类结果的比较，与人工分类结 果越相近，分类的准确程度就越高，常用评估文本分类系统的指标是查准率( p r e c i s i o n ) 、 查全率( r e c a l l ) 、f 1 值、宏平均( m a c r o a v e r a g e ds c o r e ) 和微平均( m i c r o a v e r a g e ds c o r e ) 。 查准率= 哥蓑筹m 。 查全率= 甓篱鬻川。 查准率查全率x 2 一 查准率+ 查全率 宏平均用于评价分类器的整体表现，将p r e c i s i o n 、r e c a l l 、f 1 标准在单个类别上的 数值进行平均，则分别得到它们的宏观平均值。 微平均是分类器在整个测试集上做出的分类中正确的比率，即在各类上正确分类的 文档数与分类器分类的总文档数之比，是在整体上来平均。 1 4 存在的问题 基于机器学习的文本分类技术经过2 0 多年的不断发展，特别是直接从机器学习等领 域借鉴最新的研究成果，已能较好地解决大部分具有数据量相对较小、标注比较完整及 数据分布相对均匀等特点的问题和应用。但是，自动文本分类技术的大规模应用仍受到 很多问题的困扰，如：单是刻画文本问( 非线性的) 语义联系的问题，都被认为没有很好 地得以解决。近年来面临的主要挑战来自于互联网上w e b 等海量信息的处理，其主要特 征是例： 1 大规模的类别体系给分类器训练带来扩展性的困难； 6 硕十毕业论文 2 建立分类器时所获得的样本相对于海量的未知数据非常有限，模拟样本的空间分 布变得困难，这可能带来过拟合( o v e r f i t t i n g ) 及数据偏斜的问题； 3 文本和类别的更新频繁，在力求对每个类别获得更多的样本时，存在标注瓶颈的 问题； 4 类别间的关系也更加复杂，需要有更好的类别组织方法； 5 w e b 文本是一种半结构化( s e m i s t r u c t u r e d ) 的数据，其结构信息( 如链接关系、主 题等) 可能对分类提供某些帮助。 综合来看，我们认为文本分类技术现阶段主要面临非线性、数据集偏斜、标注瓶颈、 多层分类、算法的规模扩展性及w e b 页面分类等几个关键的问题。 1 5 研究的内容 在深入学习了现在文本分类算法的基础上，主要对下面两个方面进行了研究和算法 的改进： 1 网页特征的提取 与文本数据不同，网页数据是一种半结构化的数据，在网页文本表示中，对任一特 征而言，有两个因素影响特征的权值。一是特征词在h t m l 文档中出现的频率，另一个 是该特征词在文档中出现的位置。在研究了文本特征提取算法的基础上，根据网页文本 特征的特殊性，对网页文本特征提取和加权算法进行了改进。 2 基于l s - s v m 和l s a 的网页分类算法 中文网页分类在数据挖掘领域是一个热门的研究课题，为了提高网页分类效率，提 出了一种基于最小二乘支持向量机( l e 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 ，l s s v m ) 和潜 在语义分析( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) 的网页分类方法。l s a 通过奇异值分解获得 原始词一文档矩阵的潜在语义结构，在一定程度上解决了一词多义和多词一义问题。 l s s v m 在大数据集上学习效率比较高，特别是在获得有标签样本成本较高的情况下。 采用了种新颖的网页特征权重计算方法，利用摘要算法消除网页噪音，实验初步证明， 这种分类方法取得较好的效果。 1 6 论文的组织 本文致力于基于支持向量机的文本分类研究，全文共分六章，具体内容安排如下： 第一章是绪论，介绍了自动文本分类的研究背景、意义及国内外的研究现状，包括 总体研究进展和技术研究现状，最后阐述了论文的研究内容及组织结构。 第二章在对机器学习进行了简单的介绍之后，详细的叙述了统计学习理论和支持向 量机理论，为以后文本分类器的构建奠定理论基础。 第三章介绍了文本表示方法v s m ，几种特征选择算法，以及在维数很大时的降维算 法。 7 基于芷行门t 机的艾本分类研究 第四章讲述了s v m 分类模型的建立，在分析了核函数的基础上，通过训练算法来逐 步确定支持向量机的参数，建立分类模型。 第五章是本文研究的主要内容。首先利用网页噪音消除算法对网页中的噪音进行消 除，根据网页特征的特殊性，对网页特征提取和加权算法进行了改进。利用l s s v m 模 型进行网页分类，通过实验对l s - s v m 、s v m 和k n n 三种方法的对比，证明在小数据集上， l s s v m 有更高的准确性，更快的分类速度。 第六章对本文的研究工作做了总结，并对未来的研究进行了展望。 硕十毕、1 k 论文 第二章支持向量机理论 2 1 机器学习 2 1 1 机器学习的概念 机器学习研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重 新组织已有的知识结构使之不断改善自身的性能。 机器学习问题可以看作是：通过某种训练方法，对某系统的输入与输出之间的依赖 关系进行估计，并且期望这一估计能够对任意给定输入尽量准确地进行输出预测1 。 该问题可以一般的表示为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知 的联合概率r ( x ，y ) ，( x 和y 之间的确定性关系可以看作是其特例) ，机器学习问题就是 根据，个独立同分布的观测样本： ( 五，m ) ，( 恐，儿) ，( 而，y t ) ( 2 1 1 ) 在一组函数 厂( x ，w ) 中求一个最优的函数f ( x ，) 对依赖关系进行估计，使期望风 险 r ( w ) = il ( y ，f ( x ，w ) ) a r f ( x ，少) ( 2 1 2 ) 最小，其中， f ( x ，w ) 称为预测函数集，w 为函数的广义参数， f ( x ，w ) ) 可以表示任意 函数集；l ( y ，f ( x ，w ) ) 为由于用f ( x ，叻对y 进行预测而造成的损失，不同类型的学习问 题有不同形式的损失函数。以下三种不同类型的损失度量，分别对应机器学习中的三个 基本问题：即模式识别、回归估计和概率密度估计。 1 模式识别问题 模式识别问题也即分类问题。对模式识别问题，输出y 是类别标号啪1 。在两类情况 下：y = o ，1 ) 跏= 一1 ，1 ) ，f ( x ，w ) 为指示函数集，损失函数可以定义为 坳胞咖 攒；震0 亿 ， 对于模式识别问题，机器学习就是在概率分布函数f ( x ，y ) 未知的情况下，根据训 练集，寻找使得风险泛函r ( w ) 最小的函数。 2 回归估计问题 回归估计问题也即函数逼近问题，y 是连续变量( 这里假设为单值函数) ，损失函 数可定义为 l ( y ，f ( x ，们) = ( y - f ( x ，w ) ) 2( 2 1 4 ) 即采用最小平方误差准则。 3 密度估计问题 对于概率密度估计问题，学习的目的是根据训练样本确定x 的概率密度，记估计 9 荩于支持向罩f j 【的丈本分茭硎究 的密度函数为p ( x ，w ) ，则损失函数可以定义为 l ( y ，f ( x ，们) = 一l o g ( p ( x ，w ) ) ( 2 1 5 ) 所要求的密度函数就是在损失函数下使得r ( w ) 最小化。 2 1 2 机器学习的模型和目标 机器学习的一般模型主要包括以下几个部分： 图2 1 机器学习的一般模型 1 产生器( g ) ：产生随机向量x r ”，它们相互独立且都服从分布， ) 。 2 训练器( s ) ：对每个输入向量x 返回一个输出值j ，它们也相互独立且都服从分布 f ( yx ) 。 3 学习机器( l m ) ：它能够实现一定的函数集f ( x ，w ) ，w e a 。 学习的目标就是从给定的函数集f ( x ，w ) ，w 人中选出最好的逼近训练器响应的函 数。训练集序列( 誓，y 从f - 1 ，2 ，) 服从分布f ( x ，y ) = f ( x ) f ( yx ) 。因此，学 - - j 的目标 就是最小化如下的风险泛函： r ( 们= i l ( z ，w ) d f ( z ) ( 2 1 6 ) 其中l ( z ，w ) 表示对样本序列中的训练样本z 而言，采取决策w 时造成的损失，f ( z ) 表 示样本的分布。 2 1 3 经验风险最小化 显然，要使式( 2 1 2 ) 定义的期望风险最小化，必须依赖联合概率f ( x ，y ) 的信息， 在模式识别问题中就是必须已知类先验概率和类条件概率密度。但是，在实际问题中， 联合概率f ( x ，y ) 是未知的，只能利用已知样本的信息，因此期望风险无法直接计算和 最小化。 根据概率论中大数定理的思想，常用的方法是用算术平均代替( 2 1 2 ) 式中的数学期 望 ， ( w ) = 1 2 l ( y , ，厂( ，w ) ) ( 2 1 7 ) t = l 即用式( 2 1 7 ) 逼近( 2 1 2 ) 式，( 2 1 7 ) 式称为经验风险。用对参数w 求经验风险r e 。( w ) 的 1 0 硕卜毕业论文 最小值代替求期望风险r ( 们的最小值，就是所谓的经验风险最小化( e r m ) 原则。显然， 大多数传统的方法都是基于经验风险最小的，但是只有当样本数目趋于无穷时，r 。( w ) 才在概率意义下趋近于r ( 们，但是实际情况下样本的数目是有限的，而且，即使样本 数目很大，也不能保证屯。( w ) 和尺( w ) 的最小值相近。 仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可以发 现，从期望风险最小化到经验风险最小化并