（信号与信息处理专业论文）基于支持向量机的文本分类问题的研究.pdf

中文摘要 中文摘要 摘要：我们生活在信息爆炸的时代。从海量信息中迅速查找资源需要对信息进行 分类，因此文本分类技术应运而生。文本自动分类是基于内容的信息自动分类的 核心技术，它是由计算机自动判别文本类别的过程。文本分类问题具有文本向量 稀疏性大、维数高、特征之问具有较大的相关性等特点，因此，支持向量机非常 适合于文本分类问题，在文本分类中具有很大的应用潜力。同时，文本分类也给 支持向量机提出了许多富有挑战性的课题。例如，文本分类具有类别和样本数目 多、噪音多等特点，支持向量机用于文本分类时存在训练和分类速度较慢等缺点。 本文从降低文本分类过程中文本向量数目的角度出发，来加快训练支持向量 机分类的速度。采用密度聚类的方法提取原始样本中对分类起决定性作用的样本 点作为新的训练集进行分类器训练。 如果将常见的密度聚类算法直接拿来使用，效果并不理想，因为它们的时间 复杂度太高，导致整体的分类训练过程效率比较低。本文采用一种改进的密度聚 类算法，该算法融合了层次聚类算法的特点，既保留密度聚类算法对边缘点比较 敏感的特性，又降低了算法的时间复杂度。同时，本文通过大量的试验得出了针 对文本分类样本的高维性特点，在对其进行密度聚类时初始参数的动态设置方法， 从而在一定程度上解决了以前只能通过人工估算来确定参数值时效率低、实际应 用效果不佳的弊端。 本文的主要工作情况如下： 一、论文系统的介绍了文本分类的相关理论。研究对比了国内外研究较多、 性能较好的分类方法( 朴素贝叶斯、k n n 、s v m ) ，同时采用了文档型和词频型两 种概率估计方法进行了对比实验。结果显示s v m 是进行文本分类相对较好的方法。 二、针对文本分类前期处理中的特征选择技术，分析了四种常用方法的缺点， 并提出了基于类内频率的特征选择方法，通过实验对比说明该方法是一种性能比 较好的特征选择方法，并且适用于以s v m 作为分类器进行分类的方法。 三、讨论了为何选取基于密度聚类算法应用到文本分类系统中，采用改进的 密度聚类算法提取边缘点的方法，提出了在高维数据环境下对改进的密度聚类算 法中两个初始参数进行动态调整的方法。 四、采用改进的密度聚类算法提取边缘点，具体实现了基于支持向量机的分 类方法。实验结果表明系统采用上述方法后，在不损失查全率及查准率的前提下 提高了文本分类训练过程的速度。 关键词：支持向量机；文本分类；密度聚类 a b s t r a c t a b s t r a c t a b s t r a c t ：w el i v ei na ne r ao fi n f o r m a t i o n i n f o r r n a t i o n f o rf i n dt h ei n f o r m a t i o nn e e d e d e x p l o s i o n ，w en e e dt oc l a s s i f y q u i c k l y f r o mt h em a s so f i n f o r m a t i o n t e c h n o l o g y c a m ei n t o b e i n g o nt h et e x tc l a s s i f i c a t i o n t e x t a u t o c l a s s i f i c a t i o ni st h ec o r et e c h n o l o g yo fi n f o r m a t i o na u t o c l a s s i f i c a t i o n t h e r ea r e m a n yf e a t u r e sa b o u tt e x tc l a s s i f i c a t i o n ：w i d es p a r eo ft e x tv e c t o r , h i g hd i m e n s i o n , c o m p a r a t i v e l yr e l a t i o na m o n gf e a t u r e s s os v mi sv e r ys u i t a b l ea n dp o t e n t i a l f o r r e s o l v i n gt e x tc l a s s i f i c a t i o n t h i sp a p e rs p e e d su pt h ec l a s s i f i c a t i o np r o c e s sb yd e c l i n i n gt h en u m b e ro ft e x t v e c t o r s t h i st h e s i sc h o o s e st h ed e c i s i v es a m p l e sf r o mt h eo r i g i n a ls e tb yu s i n gd e n s i t y c l u s t e r i n ga l g o r i t h m i t sn o tag o o dw a yf o rm a k i n gu s eo ft h ec o m m o nd e n s i t yc l u s t e r i n ga l g o r i t h m d i r e c t l y , b e c a u s et h e i rt i m ec o m p l e x i t yi sv e r yh i g h ，t h i sw i l lc a u s e t h et o t a lc l a s s i f y i n g p r o g r e s se f f i c i e n c yv e r yl o w s ot h i s a r t i c l eu s e sa ni m p r o v e dd e n s i t yc l u s t e r i n g a l g o r i t h m ，t h i sa l g o r i t h mm i x e sf e a t u r e so fh i e r a c h i c a lc l u s t e r i n ga l g o r i t h mc u r e i t n o to n l yr e t a i n st h ef e a t u r et h a ti ss e n s i t i v et oe d g ep o i n t ，b u ta l s od e c l i n e st h et i m e c o m p l e x i t yo fd e n s i t yc l u s t e r i n gp r o g r e s s t h em a i nw o r ki sa sf o l l o w si nt h ep a p e r ： f i r s t l y , t h i sp a p e ri n t r o d u c e st h ec l a s s i f i c a t i o na n dc o n t r a s t st h ec l a s s i f i c a t i o n a n d a d o p tad o c u m e n tt y p ea n df r e q u e n c yo ft h et w om e t h o d st oe s t i m a t et h ep r o b a b i l i t yo f c o m p a r a t i v ee x p e r i m e n t s v mi sar e l a t i v e l yb e t t e rw a y s e c o n d l y , p o s eam e t h o db a s e do nt h ep r o p o s e dc a t e g o r yo ft h ef r e q u e n c y c h a r a c t e r i s t i c so fo p t i o n s b yc o n t r a s ts h o w st h a tt h ee x p e r i m e n t a lm e t h o di sag o o d f e a t u r es e l e c t i o nm e t h o d s t h i r d l y , p o s eam e t h o db yu s eo ft h ed e n s i t yo fc l u s t e r i n ga l g o r i t h mf r o mt h e b o u n d a r ya n db ym a d ei nh i g h - d i m e n s i o n a ld a t ae n v i r o n m e n td y n a m i cp a r a m e t e r so f t h e w a y f o u r t m y , ac o n c r e t er e a l i z a t i o no f t h ed e n s i t yo fc l u s t e rp o i n t sf r o mt h eb o u n d a r yo f t h ec l a s s i f i c a t i o n k e y w o r d s ：s v m ；t e x tc a t e g o r i z a t i o n ；d e n s i t yc l u s t e r i n ga l g o r i t h m v l l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 噌磷 导师签名： 祸1 卵吾 签字日期：渺彦年易月9 日 签字r 期： 。g 年勿月3 日 北京交通人学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：呷吁 签字日期： 砌旷年多月2 日 7 8 致谢 本论文的工作是在我的导师杨晓晖副教授的悉心指导下完成的，杨晓晖副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三 年来杨晓晖老师对我的关心和指导。 在此还要感谢苗振江教授，苗振江教授悉心指导我们完成了实验室的科研工 作，对于我的科研工作和论文都提出了许多的宝贵意见，在学习上和生活上都给 予了我很大的关心和帮助，在此向苗振江老师表示衷心的谢意。 在实验室工作及撰写论文期间，王海龙、王琛、纪现清、明悦、唐晓丹、杜 鲁燕、高国栋、l a u r e n te x s t e e n s 等实验室同学，王红波、赵燕燕、侯妍颖、王晶、 宋飞等同学都对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激 之情。 另外也感谢我的父亲母亲及各位家人，他们的理解和支持使我能够在学校专 心完成我的学业。 序 序 论文工作从2 0 0 7 年7 月开始至2 0 0 8 年5 月完成。旨在研究文本分类的有效 方法。 引言 1 引言 1 1 课题背景 随着信息时代的来临，为了从海量的信息中迅速查找需要的信息，就需要对信 息进行分类。传统的做法是对信息进行人工分类，并加以组织和整理，为人们提 供一种相对有效的信息获取手段。但是，这种传统的人工分类的做法存在着许多 弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一致性不高的问题。 这就要求我们探索文本自动分类的有效方法，提高分类效率。只有这样才能保证 检索的查全率和查准率都得到提高。 面对如此复杂的问题，分类技术在信息检索、信息过滤、数据挖掘等方面起 着至关重要的作用。而网上的大部分信息以文本的形式存在，内容包括新闻文章、 研究论文、书籍、报刊、报告、专利说明书、会议文献、技术档案、政府出版物、 数字图书馆、技术标准、产品样本、电子邮件消息、w e b 页面等。因此，文本自 动分类就成为信息处理领域的一个重要的研究课题。文本自动分类是信息检索技 术和人工智能技术相结合的研究领域，是进行基于内容的自动信息管理的核心技 术。文本分类的目标是在分析文本内容的基础上，给文本分配一个或多个比较合 适的类别，从而提高文本检索等应用的处理效率。 文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都 有着广泛的应用。可用于门户网站的网页管理，图书馆的电子资料管理，情报信 息部门的情报处理，以及政府、企业等对于电子邮件的管理等等。例如对新闻出 版按照栏目进行分类，可分为政治、体育、军事等不同的主题；对于垃圾邮件的 判定，类别为垃圾邮件和非垃圾邮件；在自然语言处理的分词系统中，需要进行 词性标注，可以认为是一个分类问题，类别为名词、动词、形容词等；在信息过 滤中，应用文本分类，分为用户感兴趣的文档和用户不感兴趣的文档；在文本检 索，文本过滤以及主题发现与跟踪等研究中都占据着重要的位置。 我们生活在一个信息爆炸的时代，i n t e m e t 的奇迹般的发展导致可利用的在线 信息资源呈指数级增长 1 ，在过去几年里，估计已发布的网页已达到“亿 数量 级，而且这个数字每天都在增加。然而人们却越来越发觉i n t e m e t 这个数字时代 的图书馆并不像真正的图书馆那样支持有组织的信息检索和管理，相反它是一个 杂乱无章的信息仓库，人们所需要的有用信息往往被大量的信息垃圾所淹没，寻 找有用信息无异于大海捞针。去伪存真，去粗取精，无疑要花费人们大量的精力 北京交通人学硕士学位论文 和时间。而且这种状况将随着信息量的不断膨胀而日益严重。随着数据信息库积 累的数据和主题越来越多，从大量数据中发现有用知识的数据挖掘( d a t am i n i n g ， 简称d m ) ，就成为一个十分迫切的富有挑战性的研究课题。 基于数据的机器学习( m a c h i n el e a r n i n g ，简称m l ) 是数据挖掘技术中的重要 内容 2 ，主要研究如何从一些观测数据出发得出目前尚不能通过原理分析得到的 规律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测。 统计是我们面对数据而又缺乏理论模型时的最基本的分析手段。传统统计学所研 究的是渐进理论，即当样本数目趋向于无穷大时的极限特性。但实际应用中，这 种前提条件却往往得不到满足。因此一些理论上很优秀的学习方法在实际应用中 的表现却可能不尽人意。v a p n i k 等人从二十世纪六、七十年代开始致力于统计学 习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，简称s l t ) 的研究 3 - 4 ，随着其理论的不断发 展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论 开始受到越来越广泛的重视。 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m ) 是在统计学习理论基础上发 展起来的一种新型机器学习方法 5 8 。它最初于2 0 世纪9 0 年代提出，近年来 在其理论研究和算法实现方面都取得了突破性进展，开始成为克服“维数灾难 和“过学习 等传统困难的有力手段。s v m 已经成功应用于人脸识别、语音识别 、文本分类等领域 9 一1 5 ，取得了良好的效果。支持向量机从提出、被广泛重视 到现在只有几年的时间，其中还有很多尚未解决或尚未充分解决的问题，在应用 方面还具有很大的潜力。因此，支持向量机是一个十分值得大力研究的领域。 文本分类是对用自然语言写成的文本按照预先定义的主题类别进行分类。文 本分类作为文本挖掘的重要组成部分，可以应用到任何需要文档管理或信息分发 的应用中，在文本分类的基础上，可以更好地进行信息的检索和信息的个性化服 务。传统的文本分类工作是由特定领域的专家人工完成的，这种人工分类方法需 要耗费大量的时间和精力，特别是随着文本信息量的增加，人工方法己经很难满 足分类的需求，因此利用计算机对文本进行自动分类的研究日益受到重视。文本 分类的目的是把文档按照它们的主题或者主旨来划分类别。文本分类系统的任务 可简单的定义为：给定分类体系后，根据文本内容自动确定文本关联的类别。从 数学角度来看，文本分类是一个映射过程，它将未标明类别的文本映射到现有类 别中，该映射可以是一一映射，也可以是一对多映射，因为通常一篇文本可以与 多个类别相关联。文本分类的映射规则是，系统根据已知类别中若干样本的数据 信息总结出分类的规律性，建立类别判别公式和判别规则。当遇到新文本时，根 据总结出的类别判别规则确定文本所属的类别。 文本分类具有以下特点： 2 引言 ( 1 ) 文本分类所需要处理的样本空间非常庞大，即便通过简化，仅考虑词， 而不考虑词的次序不同、断句等的不同所表达的含义的不同，样本的维数也很高； ( 2 ) 文本向量非常稀疏； ( 3 ) 文本特征之间存在较大的相关性； ( 4 ) 文本训练样本集中存在较多噪音； ( 5 ) 不同文本类别的训练样本数目往往存在较大差别。 在实际中，大量高质量的文本集合的获得是非常困难的，通过人工的方法对 每篇文档进行筛选也不现实。一般的情况下，人们比较容易得到一些大体比较相 关的文档，比如从专业资源库、互联网、新闻组等等。然而，这些资源中的文本 的质量是参差不齐的，有些甚至是错误的，使得训练样本中存在大量错误( 噪声) 。 并且，由于一些文本类别的样本易于获取，而一些类别的样本较难获取，使得文 本分类存在类别样本数目不均衡的问题。文本分类的这些特点，使得很多分类算 法的效果不好。与其它文本分类算法相比，支持向量机主要具有如下优势： ( 1 ) 文本数据向量维数很高，对于高维问题，支持向量机具有其它机器学习 方法不可比拟的优势； ( 2 ) 文本向量特征相关性大，许多文本分类算法建立在特征独立性假设基础 上，受特征相关性的影响较大，而支持向量机对于特征相关性不敏感； ( 3 ) 文本向量存在高维稀疏问题，一些文本分类算法不同时适合于稠密特征 矢量与稀疏特征矢量的情况，但支持向量机对此不敏感； ( 4 ) 文本分类样本收集困难、内容变化迅速，支持向量机能够找出包含重要 分类信息的支持向量，是强有力的增量学习和主动学习工具，在文本分类中具有 很大的应用潜力 1 2 国内外研究现状 1 2 1 文本分类 文本分类的研究可以追溯到上世纪六十年代，早期的文本分类主要是基于知 识工程( k n o w l e d g ee n g i n e e r i n g ) ，通过手工定义一些规则来对文本进行分类，这种 方法费时费力，并且必须对某一领域有足够的了解，才能写出合适的规则。1 9 7 1 年，r o c c h i o 提出了在用户查询中不断通过用户的反馈来修正类权重向量来构成简 单的线性分类器。1 9 7 9 年，v a nr i j s b e r g e n 对信息检索领域的研究做了系统的总结， 里面关于信息检索的一些概念，如向量空间模型( v e c t o rs p a c em o d e l ) 和评估标准如 准确率( p r e c i s i o n ) 、召回率( r e c a l l ) 。1 9 9 2 年，l e w i s 在他的博士论文( ( r e p r e s e n t a t i o n 北京交通大学硕士学位论文 a n dl e a r n i n gi ni n f o r m a t i o nr e t r i e v a l ) ) 中系统的介绍了文本分类系统实现方法的各 个细节，并且在自己建立的数据集r e u t e r s 2 2 1 7 3 ( 后来去掉一些重复的文本修订为 r e u t e r s 2 1 5 7 8 数据集) 上进行了测试。1 9 9 5 年，v i p n i k 基于统计理论提出了支持 向量机( s u p p o r t v e c t o r m a c h i n e ) 方法。在支持向量机出现的同时，1 9 9 5 年及其后， 以y o a vf r e u n d 和r o b e r te s c h a p i r e 发表的关于a d ab o o s t 的论文为标志，机器学 习算法的研究出现了另一个高峰。r o b e re s c h a p i r e 从理论和试验上给出a d ab o o s t 算法框架的合理性。其后的研究者在这个框架下给出了许多类似的b o o s t i n g 算法， 比较有代表性的有r e a la d ab o o s t ，g e n t l eb o o s t ，l o g i tb o o s t 等。这些b o o s t i n g 算法均已被应用到文本分类的研究中，并且取得了比较好的效果。 国外自动分类的研究起步较早，始于1 9 5 0 年代末。1 9 5 7 年，i b m 公司的 h e l u h n 在这一领域进行了开创性的研究，他首先将词频统计的思想用于文本分 类中。1 9 6 0 年m a r o n 在j o u r n a lo f a s m 上发表了有关自动分类的第一篇论文o n r e l e v a n c ep r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ) ) ，标志着自动分类作为一 个研究课题的开始。1 9 6 2 年博科( h b o r k o ) 等人提出了利用因子分析法进行文献的 自动分类，其后许多学者在这一领域进行了卓有成效的研究。国外的文本分类经 历了可行性基础研究和实验性开创研究，目前已经进入到实际性商业应用，在信 息检索、电子会议、网络安全、机器翻译等方面都得到了广泛应用。 文本分类的发展历史大致可分为两个阶段。从6 0 年代起步至8 0 年代末，主 要是以专家人工构建的知识工程技术为支撑，分类系统包括专家定义的一系列逻 辑规则，依据这些规则可以把新给定的文本归类为某种或某几种特定类别，典型 的代表系统有麻省理工学院( m i t ) 为白宫开发的邮件分类系统、卡内基集团为路透 社开发的c o n s t r u e 系统等。第二阶段从9 0 年代开始，随着互联网技术的快速发展， 文本自动分类的研究也进入了一个新的阶段，各种方法相继得到了发展，机器学 习技术为主的信息分类技术逐渐取代了基于知识工程的方法成为了文本自动分类 研究的主要形式，如n a v i eb a y e s ，d e c i s i o nt r e e ，神经网络等等。1 9 9 5 年d o r t m u n d 大学的j o a c h i m s 探讨了用支持向量机方法进行文本分类，取得了很好的效果。此 外，一些学者还采用b o o s t i n g 方法来探讨提高分类处理的方法。这类分类算法通 常是从预先分类正确的训练文本集合中学习到类别的特征判别信息，在通过测试 文本集合对分类器性能进行测试 1 6 】。 国内自动分类研究起步较晚，始于2 0 世纪8 0 年代初期。1 9 8 1 年侯汗清对计 算机在文献分类工作中的应用做了探讨，并介绍了国外在计算机管理分类表、计 算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，国内 的研究者在英文文本分类研究的基础上采取相应的策略，结合中文文本的特定知 识，将基于支持向量机的文本分类问题研究应用于中文之上，继而形成中文文本 4 引言 自动分类研究体系。到目前为止，我国陆续研制出一批计算机辅助分类系统和自 动分类系统。这其中有基于人工智能技术的分类系统，有基于统计技术的分类系 统，还有基于模糊技术的分类系统，近几年来基于统计知识的分类方法占主流， 也不乏有基于规则的分类方法。国内清华大学、上海交通大学、哈工大、中国科 学院等科研院所在文本分类领域做了很多的研究，在中文文本自动分类领域中已 经取得了令人瞩目的研究成果，其中一些已经被成功的推广和应用，典型的代表 系统有北大天网和百度搜索等。 文本分类的实际应用和它自身固有的特性给机器学习、人工智能提出了新的 挑战，这使得文本分类的研究仍是信息处理领域的一个开放的、重要的研究方向。 常用的自动文本分类算法主要包括三大类。一类是基于概率和信息理论的分 类算法，如朴素贝叶斯算法( n a i v eb a y e s ，简称n b ) 1 7 1 8 ，最大熵算法( m a x i m u m e n t r o p y ) 等【1 9 】；另一类是基于t f i d f 权值计算方法的分类算法 2 0 】，这类算法包 括r o c c h i o 算法，t f i d f 算法，k 近邻算法( kn e a r e s tn e i g h b o r s ，简称k n n ) 等 2 1 】 第三类是基于知识学习的分类算法，如决策树( d e c i s i o nt r e e ) ，人工神经网络 ( a r t i f i c i a ln e u r a ln e t w o r k s ，简称a n - n ) ，支持向量机( s u p p o r t v e c t o rm a c h i n e ，简称 s v m ) 等算法 5 8 】。文献【1 3 】对几种常用的文本分类算法进行了分析和比较，结果 表明，支持向量机、k 近邻、朴素贝叶斯是三种较好的文本分类算法，其中支持 向量机具有最高的分类精度但速度最慢，n b 具有最高的分类速度但精度最低。 1 2 2 支持向量机在文本分类中的应用 支持向量机的应用研究非常广泛，目前，支持向量机方法己在分类、时间序 列预测、控制等诸多领域都有应用。支持向量机最初是被应用在模式识别中。其 中，最突出的应用研究是贝尔实验室对美国邮政手写数字库进行的实验 4 】。这是 一个可识别性较差的数据库，人工识别平均错误率是2 5 ，用决策树方法识别错 误率是1 6 2 ，两层神经网络中错误率最小的是5 9 ，专门针对该问题设计的五 层神经网络错误率为5 1 ，而用三种支持向量机方法得到的错误率分别为4 0 ， 4 1 和4 2 。这之后，支持向量机被广泛地应用于图像分割、图像检测、图像检 索、遥感图像分析、三维物体识别、语音识别【1 0 】、人脸识别 9 】、文本分类、人类 基因表示数据分析、蛋白质结构预测医疗诊断、特征选择等许多方面。以下主要 介绍支持向量机在文本分类领域的应用研究。 1 9 9 8 年，d o r t m u n d 大学的j o a c h i m s 报道了将支持向量机用于文本分类的实 验结果【1 l 】。实验在r e u t e r s 和o h s u m e d 两个标准数据集上进行，在与贝叶斯、 k 近邻和决策树等分类方法的比较中，支持向量机方法取得了最好的分类精度。 5 北京交通人学硕士学位论文 微软的d u m a i s 和c a r n e g i em e l l o n 大学的y a n g 等很多学者也相继对此进行了 研究 1 4 ，1 5 ，1 7 】，并报道了类似的结果。 另外，针对超文本分类问题，研究者们还提出了许多解决此问题的支持向量 机方法。文献 2 2 】和文献 2 3 】把支持向量机应用于超大规模网页数据集，文献 2 4 】 采用站点摘要的方式来合成新的网页，再用支持向量机进行分类。 此外，研究者还提出了支持向量机的许多变种及改进方法 2 5 】。文献 2 6 】提出 多种方法将文本输入空间的维数减少，并通过实验证明，即使在显著减少文本输 入空间维数的情况下，文本分类的精度也没有降低，而训练和分类的时间却得到 了减少。文献【2 7 】提出一种新的训练方法，在线性时间内训练线性支持向量机，显 著地提高了支持向量机的训练速度。文献 2 8 】对每一个类别构造一个原型，测试文 本将被划分到与其最相似的原型所对应的类别中。s u y k c n s 等人提出的最d , - - 乘支 持向量机( l s s v m ) 2 9 ，将二次规划问题转变成线性方程组的求解，简化了计算 复杂性。但由于每个样本数据对分类器都有贡献，最小二乘支持向量机失去了稀 疏性这一支持向量机的优点。文献 3 0 1 提出了直接支持向量机( d i r e c t s v m ) 采用了 启发式搜索方法在所有训练样本集中搜索支持向量，从而避免了二次规划最优求 解。该方法具有直观且求解速度快等优点。此外，还有n n s v m 31 ，c s v m 3 2 ， f s v m 3 3 3 4 等变种，不再一一叙述。 总体来说，目前，支持向量机在文本分类中的应用研究主要包括两方面的内 容：一是利用支持向量机的优势：支持向量机能够找出包含重要分类信息的支持 向量，是强有力的增量学习和主动学习工具等，挖掘支持向量机在文本分类中的 应用潜力，解决文本分类中存在的问题；二是研究支持向量机在文本分类的应用 中存在的尚未解决或尚未完全解决的问题，针对文本分类的特点，提出提高支持 向量机在文本分类中的应用效果的新方法。 1 3 本文的研究内容 支持向量机从被广泛重视到现在只有几年的时间，其中还存在很多尚未解决 或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需要。面对文 本分类等具有类别和样本数目多、噪音多等特点的应用，支持向量机在应用过程 中存在以下问题： ( 1 ) 支持向量机是针对二分类问题提出的，当用于多分类问题时必须将其推广。 对于类别数目较多的分类问题，目前仍缺乏有效的支持向量机多分类方法。在文 本分类应用中，多分类问题非常普遍，支持向量机多分类方法的研究具有很大的 实用价值，是支持向量机研究中的重要内容。 6 引言 ( 2 ) 标准支持向量机对所有样本采用相同的错分惩罚，对噪音敏感，分类时倾 向于样本数目较多的类别，并且对于需要求解二次规划问题的支持向量机模型， 当样本数目较多时，其训练速度较慢。如何进一步改进和完善支持向量机模型及 其训练算法，是支持向量机研究中的热点问题。 ( 3 ) 一般情况下，文本分类问题的样本数目越多，支持向量机的分类速度越慢。 对于训练样本数目多的分类问题，支持向量机的分类速度过慢，这一点限制了支 持向量机的应用，成为支持向量机方法进入大规模实用化阶段的瓶颈。 本文从缩减原始文档训练集的规模，提高支持向量机的分类速度方面入手， 考虑到支持向量在支持向量机分类中的重要作用，采用改进的密度聚类的方法对 原始的文档向量集进行简约处理，提取训练集中的边缘点，也就是支持向量。利 用简约后的训练集进行分类器的训练，这样可以减少训练的时间代价。 本文的工作主要包含以下几个方面： 第一章：介绍了文本自动分类的意义及目前的研究现状。 第二章：从特征词的表示，特征选择，向量空间模型三方面介绍了文本的表 示。 第三章：支持向量机背景理论及其实现算法的综述，概要介绍了支持向量机 的背景理论统计学习理论。然后对其他两种常用的分类方法进行介绍，通过 对比实验和分析，得出支持向量机是这三种方法中分类性能最好的一种分类器。 第四章：讨论了为何选取密度聚类算法应用到我们的系统中。详细介绍了利 用密度聚类方法对原始的文本向量集进行聚类处理并提取边缘点集作为新的训练 集提供给分类器进行分类的方法，并提出了用一种改进的密度聚类算法提取边缘 点，对改进的密度聚类算法的两个初始参数密度半径、密度闭值的设置作了分析 研究，提出了在高维数据环境下动态调整参数值的方法。 第五章：介绍了采用基于密度聚类的提取边缘点的分类方法的具体实现过程 及对分类结果进行分析。 最后，对已做的工作进行总结，并对以后的工作进行展望。 7 北京交通人学硕士学位论文 2 文本表示与特征选择方法对比 2 1 文本分类概述 文本分类指将文本按照其内容含义将其划分到不同的类型中去，其中文本可 以是各种各样的信息资料，可以是新闻、文章、报告、单据、邮件、短信等内容。 文本分类可以定义为下述的决策二维数组中的a ，赋予集合 0 ，1 ) 中的一个数的过 程。其中c = c i ，c 2 ，靠) 是预先定义好的一个类别的集合， d = d 。，d 2 ，以) 是要进行分类的文档的集合。a 盯为l 表示文档d ，在q 中，反 之，口，为0 则表示文档d ，不在岛中。 表2 1 文本分类 t a b l e 2 it e x tc a t e g o r i z a t i o n 4d ， d n c la i i a i iq 。 qa i la l la i n a ，h ia m ，口m 文本的类别和数量可以是事先没有定义好的，也可以是事先确定好了的。对 事先没有确定的，需要经过文本的自组织、聚类后才可以获得，这种文本的分类 是没有确定结果的，无需人工事先进行人工的分类，但是这样分类的结果却是未 知的，不能确定结果的范围。对事先定义好了类别的文本分类，可以获得我们所 需要的类别的文本，我们把它称之为有指导的文本分类，也称之为自动分类。对 无指导的分类，我们称之为自动聚类。 自动聚类是一个将文本集分组的全自动处理过程。每个类别的文本在一定方 面相互接近。如果把文本内容作为聚类的基础，不同的组则与文本集不同的主题 相对应。所以聚类是一种发现文本集包含内容的办法。为了帮助确定一个组的主 题，自动聚类工具定义了一个在文件组中常见的单词词汇表。聚类也可以根据文 件属性的组合来进行，例如它们的长度、耗费和同期等。在数学方面的智能性聚 类工具也可以适用于这种问题。自动聚类是指文本聚类，即对给定的待分类文本 集利用聚类方法将其划分为多个类别。自动据类系统不需要训练文本，划分出的 文档类也是不确定的。 自动分类的一般做法是，预先确定好文本的类别，并且对每个文本类别提供 文本表示与特征选择方法对比 一批预先分好类的文本称为训练文本集，分类系统通过训练文本集学习分类知识， 在实际分类时，再根据学习到的分类知识为需要分类的文本确定一个或者多个文 档类别。本文研究文本自动分类。 根据需要不同、标准不同、目的不同，可以设计不同类别体系。对于计算机 进行的文本自动分类，要求各个类别之间有一定的区分度，这个区分度的确定是 分类系统的重要指标。 类别体系确定以后，如何将文本划分到各个类别中呢。我们看一下人是如何 进行分类的。人类在与周围社会、自然环境的接触过程中储备了庞大的知识库在 人脑中。这使人在进行分类时，可以通过人脑所具有的抽象思维能力来理解文本 内容，达到文本分类的目的。人类所做的文本分类是一种基于篇章理解的分类。 由于自然语言的复杂性以及知识库的严重不足，目前采用计算机来做篇章理解， 还远远不能达到理解各种各样真实文章的水平。因此需要通过各种方法找出真实 文本的一些可以量化的特征来描述文本，并以此作为分类的依据。自此，文本自 动分类问题可以被看作为一种特定的模式识别问题，真实文本所反映的文本类别 特征可以看作实一种待识别的模式。 在文本分类中，包括中文文本分类和西文文本分类。其中中文文本的分类相 对比较难，下面主要针对中文文本分类技术做一些介绍。文本分类大致可分为几 个重要步骤：文本的向量模型表示，分词，特征选择和分类器训练。接下来将详 细介绍这些关键技术。 2 2 基于统计的中文文本自动分类 根据分类知识获取方法的不同，可以将分类系统分为两大类：第一、基于知 识工程的分类系统；第二、基于统计的分类系统。 基于知识工程的方法主要依赖语言学知识，需要编制大量的推理规则作为分 类知识，实现相当复杂，而且其开发费用是相当昂贵的。相比之下，统计方法由 于其相对简单的机制，以及在实践环境中所表现出来的良好性能，被大多数文档 分类系统所采用。利用统计学习方法实现文档分类具有速度快、实现简单等特点， 且分类准确度也较高，能够满足一般应用的要求。基于统计的分类方法具有如下 特点：1 、忽略文本的语言学结构；2 、把文本作为特征项集合对待；3 、利用加权 特征项构成向量作为文本表示；4 、根据词频信息对文本特征进行加权。 由于中文和西文之间存在差异，所以面向中文的文本自动分类既具有西文自 动分类的共同之处，又具有其自身的特点。基于统计的中文文本自动分类所涉及 到的关键技术大致包括以下几个方面： 9 北京交通大学硕士学位论文 ( 1 ) 中文文本自动分词技术 自动分词是针对中文的一种自然语言处理技术，中文同英文不同，句子中各 个词条间没有固有的间隔，为了对文本信息进行分类、索引等处理，首先需要对 中文文本进行词条切分( 简称分词) 。中文文本的分词处理是指在中文文本中切分 出连续的能够代表语义单元的词或者n 元词条，将中文文本的连续的字节流形式 转化为离散单词流形式的过程。自动分词技术是各种中文信息处理的基础。也是 中西文之间研究文本自动分类的主要差异所在，中文文本自动分类要在自动分词 的基础上进行，对中文文本进行分词的过程也是文本特征集的确定过程。 ( 2 ) 文本特征的抽取技术 特征选择是文本分类的一个重要环节。由于文本特征集的数量非常庞大，一 般的学习算法无法对其进行类别学习，使得进行特征子集的抽取变得十分必要。 特征选择可以从两个方面提高系统的性能。一是分类速度，通过特征选择，可以 大大减少特征集合中的特征数，降低文本向量的特征数，提高系统运行速度。二 是准确率，通过适当的特征选择，不但不会降低系统的准确率，反而会使系统提 高精度。 ( 3 ) 文本分类特征权值计算模型 为了使计算机能够真正处理文本特征，必须对文本特征进行特征加权，将文 本表示成计算机可以处理的数学向量。自从文本检索和信息检索概念首次被提出 后，出现了许多基于文档和问题之间相关词语比较的计算模型，具有代表性的有 布尔模型、向量空间模型、概率模型等。这些模型从不同角度出发，使用不同方 法处理特征加权、类别学习和相似性计算等问题。 ( 4 ) 识别算法 文本分类是一个特定的模式识别问题，在文本中使用模式识别的机器学习方 法取得比相关反馈方法更好的效果。如果说文本分类曾一度被看作信息检索问题， 现在文本分类越来越被作为模式识别的一个特例进行研究。大量经典模式识别学 习算法已经被应用于文本分类中，如k 近邻分类法、贝叶斯决策法、决策树、神 经网络、支持向量机等，并取得了令人鼓舞的成果。 2 3 向量空间模型( v s m ) 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 2 7 是由s a l t o n 等人在六十年 代末到七十年代初期提出的模型，近年来应用较多且效果好。v s m 是由一组规范 化正交词条矢量所组成的向量空间，每一个文档映射向量空间的一个点，向量间 的距离表示文档之间的相似度。通过这种模型可以将给定的文档以向量的形式表 1 0 文本表示与特征选择方法对比 示出来，从而将文档之间的相似性这一抽象的问题转化为具体的空间的点与点的 距离问题，通过计算出任意两个向量之间的近似程度，从而来反映所对应的文档 间的相似性。 在v s m 中，主要涉及到以下几个概念： ( 1 ) 文档( d o c u m e n t ) ：指一篇文章。 ( 2 ) 项( t e r m ) ：也称为索引项或特征项，一般指文档中的词或短语。给文档分 类主要是依据特征项，即一些特殊的项，可以起到代表文档的作用。 ( 3 ) 项的权重( t e r mw e i g h t ) ：假设一个系统包含有m 个文档，疗个不同的项， 则b = ( t l , t 2 ，厶) ( 1 f m ) ，表示一个文档：给其中的项t i ( 1 k n ) 赋值，记为， 表示它在文档中的重要程度，通常称为项以的权重。 ( 4 ) 向量空间模型：由( 3 ) 得到一个含值的文档表示，记作： q = ( w ，f 2 w 2 ，乞) 。由于f l ，f 2 ，厶互不相同，可以把它们看作是刀维欧氏空间 的n 个坐标，把( w ，w 2 ，) 看作是万维欧氏空间的向量。这样，称 q = ( w ，乞w 2 ，乙) 为文档口的向量表示。为特征项词条，w 为对应坐标值， 即特征词条权值。 ( 5 ) 相似度( s i m i l a r i t y ) ：两个文本d l 和砬之间的( 内容) 相关度( d e g r e eo f r e l e v a n c e ) 常常用他们之间的相似度s i m ( d 。d 2 ) 来度量。当文本被表示为向量空间 模型时，我们可以借助于向量之间的某种距离来表示文本间的相似度。常用向量 之间的内积进行就算： l s i m ( d j d p = w i m t ( 2 1 ) k = l 或者用央角的余弦值表示 三 艺tm t s i m ( d i d 2 ) = 1 坠一 ( 2 2 ) 、吒吒 yk = l k = l 夹角余弦值的图例表示 北京交通人学硕士学位论文 2 4 文本特征词的表示 图2 1 向量夹角余弦图例 f i 9 2 1v e c t o ra n g l ec o s i n e l ， 1 4 ) 2 2 ，心丘) 通过计算机对文本进行分类，首先要把文本表示成计算机能处理的数据形式。 在文本分类中最常见的是对文本进行分词，这样文本就变为词集，而将全部词集 作为文本分类的特征，构成文本词汇的数量是相当大的，可以达到几万个，因此 需要对词集进行相应的压缩以获得对分类有用的特征，这样做的目的主要有两个： 第一，为了提高分类程序的效率；第二，为了提高分类的精度，由于不同的词汇对 文本分类的意义是不同的，一些是通用的、各个类别都普遍存在的词汇对分类的 贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的 贡献大，因此，