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

i 嬲 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra p p l i c a t i o n1 e c h n o l o g y r e s e a r c ha n d a p p l i c a t i o no fn e w s a u t o m a t i c c l a s s i f i c a t i o nt e c h n o l o g yb a s e do ns u p p o r tv e c t o r m a c h i n e s b y x i a o s u p e r v i s o r ：p r o f e s s o rz h a n gb i n n o r t h e a s t e r nu n i v e r s i 够 j a n u a r y2 0 0 8 独创性l 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 岛荔 签字日期： 矿啮i 甚 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位做作者签名：玛嘲导师签名：飞山 。 签字 日期 ：俨蹄i 爿签字日期：川- 】i _ 东北大学硕士学位论文摘要 基于支持向量机的新闻自动分类技术的研究与应用 摘要 随着网络信息的迅猛发展，信息处理已经成为人们获取有用信息不可缺少的工具， 文本自动分类系统是信息处理的重要研究方向，它是指在给定的分类体系下，根据文本 的内容自动判别文本类别的过程。利用文本自动分类技术，可以快速地处理大规模的文 本数据，大大地提高信息的可用性和利用率。目前，文本分类系统大多采用统计和机器 学习的方法，这类方法在语义的水平上来分析文本内容，判断其相似度，从而得到类别 划分。 本文在对文本分类理论了解的基础上，对基于统计学习理论的支持向量机理论进行 了深入的研究和探讨，然后提出了基于双词典的改进型双向最大匹配算法和基于动态表 的停用词消除算法，这两个算法有效地提高了文本预处理的正确率，去掉了绝大多数无 用的词项，使得表达文档特征的向量更准确。通过在文本预处理阶段提高预处理结果的 准确性，尽量减少能够影响分类精度的文档噪声，提高s v m 分类器输入的准确性，使 得s v m 分类器能够得到尽可能准确的结果。 本文还提出了基于改进型多项式核的s v m 多类分类算法，该算法比较好地解决了 多类文本分类的问题，同时有效地利用了人工添加的类别，在较少的时间内可以完成整 个训练和分类工作。最后结合这三个算法完整地设计和实现了一个新闻自动分类系统， 并给出了评估方法和实验结果。 铲关键词：文本分类：支持向量机：双向最大匹配；停用词；s v m 分类器 一 l a r e s e a r c ha n d a p p l i c a t i o no fn e w sa u t o m a t i cc l a s s i f i c a t i o n t b c h n o l o g yb a s e do ns u p p o r tv b c t o rm a c h i n e s a b s t r a c t l l lr e c e n ty e a r s ，1 i l f b n i l a t i o np r o c e s s i n gt u l l l ：s m o r ea n dm o r ei m p o 眦l t 如r 瑚t og e t u s e f h l i - o m l a t i o n t e x tc a t e 9 0 r i z a t i o n ，也ea u t o m a t e da s s i g n i n go f n a t u r ml 锄g u a g et e x t st 0 p r e d e f m e dc a t e g o r i e sb 舔e do nm e i rc o n t e n t s ，i sat 船ko f 妣r e 硒i n gi m p o n 锄c e u s i n gm e t e c 上1 1 1 0 j o g yo f t e x tc a t e g 嘶删o i l ，也el 鹕e - s c a l et e x td a t ai s p r o c e s s e dm p i d l y a n d 龇 u t l l l z a t l o n 舭锄du s a b i l i t yo fi 晌m a t i o n i si m p r o v e dc o l l s 啪e d l y a t p r e s e n t ，t l l es y s t e m0 f t e x tc a t e g o n z a t l o nu s 叫l yu s e 恤w a y0 fs 诅t i s t i c 觚d m a c h 沁l e a n l i n g i ta n a l y s e st l l e c o n t e n to ft e ) 【t ，j u d g e st h es i 嘶l 撕t ya z l dg e t s 龀c a t e 9 0 r i z a t i o n o nm el e v e lo fs e m 删c 1 1 1t i 虹sp 印e r ，t 1 1 et l l e o r ) ，o fs u p p o r tv e c t o rm a c 场n e s b a s e d0 ns t a t i s t i c a l1 e 觚l i n gt h e 0 w i s r c s e a r c h e da i l dd i s c u s s e di i ld e 呻o n 恤b a s i so f s 伽yi nt e x tc a t e g o r i z a t i o n 1 1 1 ei i i l p r o v e d b 1 。d l r e c t i o nm a x l m 啪m a t c l l i n gb 硒e do n b i - d i c t i o l l a 】眵觚dt i l es t o pw o r d se l i m i i l a _ t i o n 砒g o n 也mb a u s e do nd y n a i i l i cd i c t i o i l a r i e s i sp 即s e d n e a l g o r i m m si n l p m v em e a c c 啪c yr a t eo ft e x tp r e 讹a 衄e n t ，r e n l o v em ev a s tm 萄。岫o f u s e l e s st e m s 姐dm a k em e e l g e n v e c t o ro ft e x tm o r ea c c u r a t e b y 妇p r 0 v i n gt 1 1 ea c c u r a c yr a _ t eo f t e x tp r e t r c a n n e n t ，弱f 缸 私p o s s l b l et 0r e d u c et l l ei m p a c t0 fu s e l e s st e m s 锄dr a j s et l l e a c c u r a c yr a t eo ft 1 1 ei 1 1 p u to f s v m c l 懿s i f i s om a ti tc 锄m a k e 恤r e s u l t so fs v m c l a s s i f i c a t i o n 勰a c c u r 砒e 舔p o s s i b l e t h es v mm u l t i c l 嬲sc l a l s s i f i c a t i o na 1 9 0 r i t h mb a l s e do nh p r o v e d p o l y i l o 耐a lk e m e li s 砒s op r o p o s e di i lm i sp a p e r n l ea l g o r i t h ms o l v e st 1 1 e p r o b l e mo fm u l t i c l 嬲sc l 嬲s i f i c a t i o n c o n u n e n d a b l y u s e s 纰抓i f i c i a jc a t e g o r i e se 髓c t i v e l y 觚dc o m p l e t e s 也et a s ko f 砌m n g a n d c j a s s l 士- c a n o nms h o r tt i m e a tl 船t 州t l lm e 缸e ea l g o r i t h m sas y s t e mo f 鹏w sa u t o m a t i c c i a l s s l f l c a t l o nl sd e s i 髓e da n di m p l e m e n t e d 锄dg i v e s 也ee v a l u a t i o l l s 锄dr e s u l t s k e ，啊。r d s ：t e x tc a t e g 。r i z a t i 。n ；s u p p 。r tv e c t 。rm a c l l i n e s ；b i d i r e c t i 。nm a x i m 啪m a t c k n g ； s t o pw o r d s ；s v mc l a s s i f i e r i i i ；夕 叮 ， 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 文本分类研究的概述1 1 2 研究现状。3 1 2 1 概率方法3 1 2 2 基于实例的分类器4 1 2 3 支持向量机( s u p p o r tv e c t o rm a c m n e s ) 5 1 2 4 分类委员会( c l 弱s i f i e rc o 衄i t t e e s ) 6 1 2 5 其他常用分类方法7 1 3 课题来源与主要研究内容8 1 4 本文组织结构8 第二章支持向量机理论。9 2 1 统计学习理论9 2 1 1 机器学习问题的表示9 2 1 2 经验风险最小化一9 2 1 3v c 维1 0 2 1 4 泛化性能的上界1 0 2 1 5 结构风险最小化1 l 2 2 支持向量分类理论12 2 2 1 最优分割超平面13 2 2 2 解的稀疏性1 4 2 2 3 不可分情况下的扩展1 4 2 2 4 最优超平面和s r m 15 2 2 5 推广到高维特征空间15 2 3 支持向量分类的实现细节16 2 3 1 实现技术1 6 2 3 2 门限1 7 2 3 3 概率解1 7 2 3 4 推广到多类分类17 2 3 5 层次化分类2 l i v 一 东北大学硕士学位论文 目录 2 - 3 6 分类评价标准2 3 2 4 小结2 4 第三章支持新闻自动分类的关键算法设计2 5 3 1 基于双词典的改进型双向最大匹配算法2 5 3 1 1 基础算法选取2 5 3 1 2 算法原理2 6 3 1 3 算法设计2 8 3 1 4 实验和性能评价3 2 3 2 基于动态表的停用词消除算法3 3 3 2 1 算法原理与设计3 3 3 2 2 实验和性能评价3 5 3 3 基于改进型多项式核的s v m 多类分类算法3 6 3 3 1 算法原理3 6 3 3 2 算法设计3 8 3 3 3 实验和性能评价3 9 3 4 ，j 、结4 0 第四章新闻自动分类系统的设计与实现4 1 4 1 总体设计4 1 4 1 1 训练样本收集模块设计4 3 4 1 2 分类预处理模块设计4 4 4 1 3s v m 分类器模块设计4 6 4 2 系统实现4 7 4 2 1 训练样本收集模块的实现4 7 4 2 2 分类预处理模块的实现4 8 4 2 3s v m 分类器模块的实现5 2 4 3 ，j 、结5 4 第五章结论一5 5 5 1 系统总体评价5 5 5 2 总结5 5 5 3 未来工作5 6 参考文献。5 7 至殳谢6l v f j 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早瑁了匕 1 1 文本分类研究的概述 随着信息技术尤其是i n t e m e t 相关技术的发展与成熟，i n t e n l e t 、企业内部网和电子 图书馆中可获得的信息越来越多并且还在不断增长。面对海量信息，人们已经不能简单 。地靠人工来处理所有的信息，需要辅助工具来帮助人们更好地发现、过滤和管理这些信 ， 息资源。 |文本分类是指基于文本内容，通过事先给定分类体系和训练样例( 标注好类别信息 的文本) ，将待定文本划分到某个或者某几个类别中的方法，它是有监督指导学习 ( s u p e r v i s e dl e a r n j n g ) 的一种。 最初的文本分类是依靠专家手工进行的，它对领域知识要求较高且花费巨大，不能 满足大规模文档处理的要求。文本自动分类能较好地解决大量文档信息归类的问题并可 以应用到很多情况下，包括基于受控词典的文档自动索引、文档过滤、元数据的自动生 成、词义辨别、类似于y _ o h 0 01 的w 曲资源层次分类等，它是很多信息管理任务的重要 组成部分。自动分类研究始于5 0 年代末，h p l u h n 在这一领域进行了开创性的研究。 1 9 6 1 年，m a r o n 发表了有关自动分类的第一篇论文乜1 ，随后许多著名的情报学家如 s p a r c k 、s a l t o n 等都在这一领域进行了卓有成效的研究口 引。到8 0 年代末之前，有效的二 建立自动分类系统的方法大多是知识工程的方法，即利用专家规则来进行分类；到了9 0 年代以后，统计方法和机器学习的方法被引入到文本自动分类中，取得了丰硕的成果并 逐渐取代了知识工程方法；机器学习方法较少考虑文本的语义信息，因此将语义分析和 概念网络等方法与机器学习方法相结合会取得更好的分类效果。而目前在大量的w 曲 。文档中包含了链接、文档结构等更丰富的信息，利用这些信息进行w r e b 文档的挖掘和 i分类是目前研究的热点之一口3 。 ，- 在实际生活中，文本分类应用已经非常广泛，例如： ( a ) 垃圾邮件的判定，类别 s p 锄，n o t - s p 锄) ( b ) 新闻出版按照栏目分类，类别 政治，财经，体育，军事，) ( c ) 词性标注，类别 名词，动词，形容词，) ( d ) 词性排歧，类别 词义1 ，词义2 ，) 文本自动分类是分析待定文本的特征，并与已知类别中文本所具有的共同特征进行 东北大学硕士学位论文第一章绪论 比较，然后将待定文本划归为特征最接近的一类并赋予相应的分类号。文本分类一般包 括了文本的表达、分类器的选择与训练、分类结果的评价与反馈等过程，其中文本的表 达又可细分为文本预处理、索引和统计、特征选择等步骤。 文本分类系统的主要功能模块为，如图1 1 所示。 ( 1 ) 预处理：将原始语料格式化为同一格式，便于后续的统一处理； ( 2 ) 索引：将文档分解为基本处理单元，同时降低后续处理的开销； ( 3 ) 统计：词频统计，项( 单词、概念) 与分类的相关概率； ( 4 ) 特征选择：从文档中选择出反映文档主题的特征； ( 5 ) 分类器：分类器的训练： ( 6 ) 评价：分类器的测试结果分析。 类似r e u t e r 2 1 5 7 8 的x m l 文件，标签内容 “， “i 燃 倒排索引、词根还原、概念索引 ；扣?j?童 。“ 。一j。4 词频统计，项与分类的相关概率 ，、 。，一i 女 、 。l 。嘭 特征向量，去停用词和虚词，概念网络 ? v?：一i。矗* 分类器数据( 类中心向量，词与分类的相关概率) t t，。 一 ；。f 性能指标( f l ，r e c a l l ，p r e c i s i ) 图1 1 文本分类系统的总体框架 f i g1 1m eo v e r a 胁e 、0 呔o f 把 ( tc a t e g o r i 盟t i o ns y s t e m 在文本分类过程中，需要重点考虑的问题包括：文本的表达方式、分类器的选择及 训练、基准平台选择、分类器的结果评价等。 一2 一 f ， l 东北大学硕士学位论文 ，啦。”批。+ 。_ 一 叫 “ 、十，小：，+ 第一章绪论 从文本分类的类别数目来看，主要是两种问题。一种是2 类( b i n a r y ) 问题，类别 ， “： 体系由两个互补类构成，一篇文本属于或不属于某一类。另一种是多类( m u l t i c 1 2 l s s ) 问题，类别体系由三个或者以上的类别构成，一篇文本可以属于某一个或者多个类别， 通常可以通过拆分成多个2 类问题来实现，也有直接面对多类问题的分类方法。 从文本分类是否兼类来看，主要是两种问题。一种是单标签( s i n g l el a b e l ) 问题， 一个文本只属于一个类。另一种是多标签( m u l t i l a b e l ) 问题：一个文本可以属于多类， 即出现兼类现象。 文本分类的分类体系的构建标准可以是按照语义( 如：政治、经济、军事、) ， 一 7 也可以是按照其他标准( 如：垃圾v s 非垃圾、游戏网站v s 非游戏网站) ，这完全取决于 实际目标应用的需求。分类体系一般由人工构造，可以是层次结构。例如一些常见的分 类体系：r e u t e r s 语料分类体系、中图分类、y 址o o ! 分类目录等。对于计算机而言，分 类体系就是一棵目录树，训练样例文本就是最后的叶子节点。而且对于计算机处理而言， 只需要训练样例文本及其对应类别信息，整个过程通常并不会考虑类别标签的意义。也 就是说：几篇文档合在一起表示某个类别。 1 2 研究现状 在目前的基于统计方法和机器学习的文本分类比较成熟，在很多系统中得到应用， 这一节中将主要介绍概率方法、基于实例的分类、支持向量机方法和分类委员会的方法， 另外简要说明在线线性分类、回归模型、神经网络、决策树和规则学习等方法。 在说明基于统计和机器学习的文本分类方法之前，首先给出以下基本定义：文档d j 表示为向量空间中的一个向量d 。= ，r 为词典中的词项数量，于是一个包 含g 个文档的文档集可以表示为a = ( w k ，) m ，其中w k 。表示词项t - 在文档d 。中的权重。预 定义的类为c = c 。，c 。) 。 ， 1 2 1 概率方法 概率方法是最早用于文本分类的分类器算法。概率分类器基于贝叶斯理论来计算待 定文档d j 与已知各类的条件概率，它用p ( c 。i d j ) ，如式( 1 1 ) 所示。 叱= 锴驴 。 其中p ( d j ) 对计算结果无影响，因此可不计算。贝叶斯方法的基本假设是词项之间的 一3 一 东北大学硕士学位论文 第一章绪论 p ( z lq ) = 兀p ( iq ) p ( c 。) 和p ( w k j i c 。) 可用式( 1 3 ) 和式( 1 4 ) 来估计。 p ( c 2 q ) 2 詈 p ( i q ) = 单、。 ，+ 其中，n ；为类c 。中的文档数目，l l i c 。为词项t i 在类c 。中出现的词频总数。 基于上述假设的概率分类器一般称为贝叶斯分类器。贝叶斯分类器是应用比较广泛 的文本分类器，在很多文献中都有出现乜8 、副。贝叶斯分类器易于理解，计算简单，分类 效果基本能满足要求，但其关于词项独立性的假设受到很多研究者的质疑n 引。 1 2 2 基于实例的分类器 基于实例的分类器也称为“懒惰学习系统”( l a z yl e 鲫【l i i l gs y s t e m ) ，这种方法不是 建立类别的明确的、直接的表达，而是依赖于训练集文档的分类来推断待定文档的所属 类别”1 。最常见的基于实例的分类器为k n n 分类器，其基本思想是：给定一个测试文 档，系统在训练集中查找离它最近的k 个邻居，根据这些邻居的分类来给该文档的候选 分类评分，并用邻居与文档d j 之间的相似度来加权。如图1 2 所示。 r e q u e s t 肌：i g h t s t r a i n i n g d ( ) c l 脏n t s w e i g h t s t r a i n i n g d 1 ) ( ：u 把n t s 图1 2l 心烈方法示意图 f i g1 2t h es k e t c h 啪po f k n na l g o 打【l l m 一4 一 c a t e g o r i e s s si g m n 三n t s ，、，、，、， 2 3 4 1 l 1 l ，l，k，l 东北大学硕士学位论文第一章绪论 文档之间的匹配度( 相似度) 衡量可用基于向量的评价和概率评价来完成。其阈值 j k 的确定一般通过实验的方法来进行，即通过校验集来确定该值。研究表明，k 值在一 定范围内的增加不会明显降低性能。一般取3 0 k 4 5 1 。 k n n 方法的计算时间和训练文档集的文档数目成线性关系，而且分类效果很好， 是最有效的文本分类方法之一曲j 1 1 2 1 。基于l i 烈n 方法还可以实现不同变化，例如将基于 概括的方法与基于实例的方法结合，在这种方法中，先对训练样本进行聚类得到“一般 。 实例 ( g e n e r a j i z e di n s t a n c e ) ，然后用一般实例代替训练文档作为l 心附的输入n 副。 产1 2 3 支持向量机( s u p p o r tv e c t o rm a c h i n e s ) 支持向量机( s u p p o r tv e c t o rm a c l l i n e s ，s v m ) 由、r a p n i k 在1 9 9 5 年提出，用于解决 二分类模式识别问题n 6 1 。而j o a c l l i m s 最早将s v m 方法用于文本分类n 副。支持向量机集 成了降维和分类，它将文本分类问题变为一系列二分类问题。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础上 的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推 广能力( g e n e r a l i z a t i o na b i l i t ) r ) 。 孝 从几何上说，支持向量机就是要在r 维空间中寻找到最佳决策面，该决策面能最好 地区分正例和反例，使正例与反例之间的分类间隔最大。s v m 的基本思想可以用正例 和反例线性可分的情况来说明，如图1 3 所示。 图1 3s v m 方法示意图 f i g1 3t h es k e t c hm a po fs v ma l g o r i t h m 一5 一y 9 1 n - i i 东北大学硕士学位论文第一章绪论 图中，实心点和空心点代表两类样本，h 为分类线，h 。、h 。分别为过各类中离分类 线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔( m 鹕i 1 1 ) 。可以 选择不同的平行线集来区分正例与反例，而支持向量机选择使平行线区间间隔最大的一 组作为最佳决策面。最佳决策面上的样本称为支持向量。对于非线性问题，可以通过非 线性变换转化为某个高维空间中的线性问题，在变换空间中寻找最优分类面。s v m 方 法有很坚实的理论基础，s v m 训练的本质是解决一个二次规划( q p ) 问题，得到的是 全局最优解，这使它有着其他统计学习技术难以比拟的优越性。s v m 分类器的文本分 类效果很好，是最好的分类器之一。其缺点是核函数的选择缺乏指导，难以针对具体问 题选择最佳的核函数；另外s v m 训练速度极大地受到训练集规模的影响，计算开销比 较大，针对s v m 的训练速度问题，研究者提出了很多改进方法，包括c h u i l k i n g 方法、 o s u l l a 算法、s m o 算法和交互s v m 等等n 7 制。 1 2 4 分类委员会( c l a s s i f i e rc o m m i t t e e s ) 分类委员会的基本假设是：对一个需要专家进行的任务，k 个专家个人判断的有效 组合应该优于个人的判断。在文本分类中，选择k 个不同的分类器进行同样的分类任务， 然后将其分类结果进行合适的组合得到最终的分类结果n 射。 最简单的组合规则是多票表决( m 匈o r i t ) rv o t i n g ，m v ) ，即对于二分类的分类器， 得到超过半数投票的结果被选为最终结果。 另一种规则是线性加权组合( w b i g h t e dl i n e 盯c o m b i l l a t i o n ，w l c ) ，对k 个分类器 的结果进行加权求和得到最终的分类结果。加权的权重反映了各分类器的分类有效性。 动态分类器选择( d y n a i l l i cc l 嬲s i f i e rs e l e c t i o n ，d c s ) 考察与d j 最相近的校验集文 档中的分类器性能，选择表现最好的分类器作为委员会的选择。 自适应分类器组合( a d a p t i v ec l a s s i f i e rc o m b i i l a t i o n ，a c c ) 是介于w l c 和d c s 之间的一种策略。它用委员会中的所有分类器进行判断并求和，但其权重是以与d j 最相 近的校验集文档中分类器的有效性来计算。 b o o s t i n g 方法是一种有效的改进分类委员会分类结果的方法，在这种方法中，分类 器不是并行地训练，而是按顺序进行，后一个分类器的训练是基于前面分类器的结果来 进行，它关注的是使前面分类器错分的文档能更好地被分类。a d a b 0 0 s t 是b o o s t i n g 算法 的代表口1 翻。 分类委员会方法的综合了多个成员分类器的结果，分类效果通常比较好，但其计算 一6 一 东北大学硕士学位论文第一章绪论 复杂度和计算开销取决于不同分类器的计算复杂度，同时还需要加上不同分类器结果综 合时的计算开销，这使得分类委员会的训练时间比较长。 1 2 5 其他常用分类方法 1 2 5 1 在线线性分类器 线性分类器也称为基于概括的分类器，它从训练集中显式地抽取了类别的概要描 述，将类别表示为文档向量空间中的一个向量c ，= ，然后考察文档向量与 类别向量的内积来判断文档向量所属的类别。 线性分类器可以大致分为两类，分别是批处理分类器和在线分类器。批处理归纳方 法一次处理全部的训练数据，其代表是r d c c l l i o 分类器，由h u u 于1 9 9 4 年最先提出。 在线归纳方法在考察第一个训练文档后即迅速构造分类器，并在考察新文档时不断优化 分类器。这种方法尤其适用于训练集一开始不能完全得到或类别随时间改变的情况，如 自适应文本过滤。该方法同样适用于能得到用户反馈的应用，此时在运行过程中根据用 户的反馈不断调整分类器。在线分类器包括感知器、w i d r o w - h o f r 分类器、s l e e p i n g e x p e i 盯s 算法等方法n 旷“1 3 1 。 1 2 5 2 回归模型 在统计学习范畴内，回归是指从训练数据中拟合出一个函数以近似实际函数。线性 最小平方拟合( l i m a rl e a s ts q u a 嘴sf i t ，l l s f ) 是g 在1 9 9 4 提出的一种回归模型， 它从训练集文档和分类中学习得到多元回归模型( m u l t i v a r i a t er e 鲈e s s i o nm o d e l ) 慨1 1 3 。 训练数据用输入输出向量对表示，其中输入向量用传统向量空间模型表示的文档( 词和 权重) ，输出向量则是文档对应的分类( 带有二元权重) 。通过求解这些向量对的线性最 小平方拟合，可以得到一个单词分类的回归系数矩阵，如式( 1 5 ) 所示。 = a r g i i l i n l i 剐一耶 ( 1 5 ) 其中矩阵f l s 为求解矩阵，定义了从任意文档到加权分类向量的映射。对这些分类权重 排序，则可以得到输入文档可能分类的列表。然后再指定阈值，就可以判别文档的分类。 1 2 5 3 神经网络 神经网络( n e u r a ln e t w o r k ，n n e t ) 技术是人工智能中的成熟技术。w i e n e r 和n g 曾分别将该技术用于文本分类。神经网络由一组神经元组成，其输入单元通常代表词项， 输出单元表示类别或类别兴趣度，神经元的连接权重表示条件依赖关系。对于文本分类， 文档向量权重通常作为输入。其训练通常用b p 算法来进行，时间开销一般很大n j j “2 引。 一7 一 东北大学硕士学位论文第一章绪论 最简单的文本分类神经网络为感知器，最近也有研究者将基于匹配的自组织特征映 射模型( s o m ) 方法应用于h l t e m e t 信息的自动分类乜射。 1 2 5 4 决策树和规则学习算法 决策树和规则学习方法通过构造决策树来进行分类判断，但规则学习方法能产生更 简洁的分类器。常用的决策树方法包括c 6 姻算法、i d 3 、c 4 5 、c h a i d 等汹1 。 规则学习分类器利用包含析取范式( d 蠲u i l c t i v en o m a lf o m ，d n f ) 的归纳规则学 习方法来构造分类器，其代表系统为c o n s t r u e 矧。 一 d n f 规则学习根据选词项的方法、启发式以及用于产生和修剪的准则的不同而有 很多变种，主要系统有c h a r a d e 、s w a j p 1 、r j p p e r 、s c a r 等1 m2 5 例。 7 1 3 课题来源与主要研究内容 本文中的课题来源于百度在线网络技术( 北京) 公司，通过设计一个新闻自动分类 系统，来实现将从h l t e m e t 上抓取到的网页数据库中的新闻w r c b 文档进行文本处理、分 类等一系列任务，并获得较好的自动分类结果。 本文的主要研究内容是基于支持向量机的新闻自动分类技术及其在实际项目中的 应用，包括了中文文本分词、停用词消除和s v m 多类分类等相关算法的研究和设计， 并对这些技术在具体应用中的设计和实现进行了深入的探讨。 1 4 本文组织结构 全文一共分为五章。 第一章中首先阐述了文本分类的基本概念，然后简要地探讨了在当前文本分类研究 邻域中一些典型的文本分类技术。 一 第二章中首先对统计学习理论和支持向量分类理论进行了简要地阐述，然后针对一 些支持向量分类的重要细节进行了较为深入的讨论。 r 第三章中给出了本文所提出的三个核心算法，分别是基于双词典的改进型双向最大 匹配算法、基于动态表的停用词消除算法和基于改进型多项式核的s v m 多类分类算法， 对每一个算法都给出了详细的算法设计，并进行了实验与评价。 第四章中给出了基于支持向量机的新闻自动分类技术在具体应用中的详细设计和 实现。 第五章中首先总结了全文，然后提出了一些对相关技术未来工作的展望。 一8 一 东北大学硕士学位论文 第二章支持向量机理论 第二章支持向量机理论 支持向量机( s u p p o r r tv e c t o rm a c m n e s ) 是在统计学习理论基础上发展起来的新一代 学习算法。近些年来，支持向量机在理论方面不断深入，在实践中不断拓广，已经成为 了在机器学习和数据挖掘领域中的标准工具。 支持向量机最初是由v 却n i l 【提出的。s v m 由于具有许多引人注目的特点和有前途 的实验性能而越来越受到重视晗7 1 。s v m 是基于结构风险最小化s r m ( s t m i c t u l 试黜s k 产m i i l i m i z a t i o n ) 的方法，明显优于传统的基于经验风险最小化e r m ( e m p i r i c a l 鼬s k m i i l i m i z a t i o n ) 的传统神经网络方法。s i 蝴最小化带来的误差是v c ( v a p n j k c h e r v o n e l l l d s ) 维( “泛化误差”) 的上限，而e r m 最小化带来的误差是训练数据上的误 差。这一差别使得s v m 具有良好的泛化性能。 2 1 统计学习理论 2 1 1 机器学习问题的表示 已知变量y 与输入x 之间存在一定的未知依赖关系，即存在一个未知的联合概率分 布f 【x ，y ) ，其中x 和y 之间的确定关系可以看作是一个特例，机器学习就是根据n 个独 立同分布的观测样本( ，y 。) ，( x z ，y 2 ) ，( x 。，y 。) ，在一组函数 f ( x ，y ) ) 中求一个最优函数 f 【x ，。) ，使预测的期望风险最小，如式( 2 1 ) 所示。 盯g 哪n r ( 彩) = p ( y ，厂( x ，彩) ) p ( 训) 螂 ( 2 1 ) 模式识别( 分类) 也是学习问题的一种，对应的损失函数如式( 2 2 ) 所示。 三( y ，( x ，) ) = ；i 乡譬：； c 2 2 ， 2 1 2 经验风险最小化 由于p ( x ，y ) 是不知道的，一个很直观的想法找到这样一个函数，它在训练样本集上 的经验风险最小，式( 2 3 ) 表示训练样本集上的经验风险。对于模式识别问题来说， 就是要找到在训练样本集上错误率最低的分类器。 2 吉善三( m ，m ，训 ( 2 3 ) 一9 一 东北大学硕士学位论文 第二章支持向量机理论 2 1 3v c 维 v c 维是一个标量，它可以被用来度量一个函数集合的容量。v c 维是这样定义的： 当一个函数集合的v c 维为h 的时候，那么存在一个点集 x 。) “。钔它的所有可能的( 两 类) 组合( 即2 。种组合) 全部可以使用这个函数集合分隔开，而对于任何大于h 的点集 x t ) “t 。- ( n h ) 则都不能满足上述条件，也就是说至少存在一种组合不能用这个函数集合 分隔开。 例如，在二维平面上的3 个点的任意组合可以用直线分隔开，但是4 个点的任意组 合就不能用直线分隔开，因此，在二维平面中的线性函数集合的v c 维就是3 。如图2 1 所示，就阐明了这种情况。 在这种情况下，v c 维恰好等于自由参数的数目，但是在一般情况下并非如此，例 如s i n ( h x ) 的v c 维就是无穷。 图2 1 二维平面中线性函数集合的v c 维 f i g 2 1v cd i m e 璐i o no fl i n e 盯矗m c t i o ns e ti i lm o _ d i m e n s i o n a lp l 柚e 2 1 4 泛化性能的上界 在理论上，式( 2 4 ) 中的上界在概率为1 6 的意义下是成立的。 尺( 缈) ( 缈) + ( 2 4 ) 其中，r ( ) 是期望风险，r 唧( ) 是经验风险，h 是函数集合的v c 维，n 是样本数。 公式中整个根号的部分又被称为v c 信任。 泛化性能的上界是松弛的。当l 咖 0 3 7 时，v c 信任将超过1 。对于模式识别问题， 风险最大等于l ，说明对任何样本均分类错误，这显然是没有意义的。 v c 信任的曲线如图2 2 所示。 一1 0 一 ， 东北大学硕士学位论文第二章支持向量机理论 1 4 1 2 垄 1 n 藿 o 8 o o 呈o 6 0 4 0 2 一。i 。 。 7， 。 o 10 20 3o 40 50 60 7o 80 91 h ，l = v cd i m e n s i o n ，s a m p i es i z e 图2 2v c 信任随v c 维与样本数目的比值单调上升的曲线 f i g2 2v cc o n f i d e n c ei sm o n o t o n i ci nh 嚣】 泛化性能的上界是对最坏情况下的结论，所以给出的界往往是松弛的。因而也不能 保证具有较高v c 维的学习机器一定没有较好的泛化性能。 泛化性能的上界虽然是松弛的，但是却有很好的指示性，即当这个界达到最小的时 候，期望风险也往往在最小值附近乜引。 2 1 5 结构风险最小化 建立这样的一个结构，使得s 。是v c 维为h 的假设空间，如式( 2 5 ) 所示。 sc 岛c c & ( 2 5 ) s r m 由式( 2 6 ) 表示的问题构成。 a r gr n l n ( 缈) + 1 l( 2 6 ) j 图2 3 诠释了s 1 w 的想法，就是找到s 中的某个函数f ( x ，o ) 使得期望风险最小。 东北大学硕士学位论文 第二章支持向量