（计算机软件与理论专业论文）基于svm的分类方法在内容管理中的应用.pdf

摘要 摘要 自动文本分类技术是内容管理研究的热点之一。大部分内容管理系统中的类 别层次都对应一定的分类法f 例如y a h o o ) 或者存在一个预定义的具有类似于树型 结构的分类体系，这就要求在内容管理系统中使用的文本分类技术具备层次分类 能力；然而现有大部分的分类技术都局限于水平分类，即认为类别之间是无结构 的，相互独立的【3 5 1 。 本文首先对文本分类所涉及到的各方面的技术进行了概括，重点提出了一种 基于支持向量机( s v m ) 的自动层次文本分类方法h t c s v m ，支持向量机是由 v a p n i c 在1 9 9 2 年提出的，是一类相对比较新的机器学习方法，它是建立在统 计学习理论和结构风险最小化基础之上的，是迄今在分类方面最好的方法【1 4 ，具 有完备的数学理论基础和其他方法所没有的优良特性。目前s v m 在层次分类方 面应用的较少。本文对h t c s v m 层次分类方法迸行了时间复杂度分析，推导出 h t c s v m 层次分类方法在训练阶段的时间复杂度为多项式阶。并且利用本文提出 的层次分类性能评估框架p m f h c 对h t c s v m 层次分类方法进行了评估，实验 结果表明：h t c s v m 分类方法的分类效果是令人满意的。本文成功的将h t c s v m 层次分类方法应用于陕西省工业攻关项目( 项目编号：2 0 0 3 k 0 5 一g 3 2 ) 中，项目的 实际运行情况证明了h t c s v m 分类方法是稳定可靠的。并且在分类精度方面能 够满足实用要求。 为了评估层次分类性能，本文提出了一种新的层次分类性能评估框架 p m f h c ，该框架引入了类别相似度和类别距离的概念，在评估时充分考虑类别之 间的层次结构关系对分类性能的影响。p m f h c 评估框架是对水平分类性能评估 方法的扩展，并且与它保持兼容。 本文还对几种有代表性的文本特征选择策略进行了研究，并对它们进行了对 比实验，结果证明：z2 统计( c h i ) 方法对分类性能的提升贡献最大，本文最终采 用该方法作为特征选择策略。 关键词：内容管理；文本挖掘；支持向量机；层次分类； a b s t r a c t a b s tr a c t t h ea u t o m a t e dc a t e g o r i z a t i o no ft e x t si n t op r e d e f i n e dc a t e g o r i e sh a sb e e na n i m p o r t a n tp a r to fc o n t e n tm a n a g e m e n tr e s e a r c h s i n c et h ec a t e g o r i e si n v o l v e di n c o n t e n tm a n a g e m e n ta p p l i c a t i o na r ed e f i n e do v e ral a r g et a x o n o m y ( s u c ha sy a h 0 0 ) o r h i e r a r c h i c a l l yo r g a n i z e di nt r e e l i k es t r u c t u r e s ，i ti sm o r e n a t u r a la n d a p p r o p r i a t et ou s e a l la u t o m a t i ch i e r a r c h i c a lt e x tc l a s s i f i c a t i o nm e t h o d u n f o r t u n a t e l y , m o s tp o p u l a r c a t e g o r i z a t i o nt e c h n i q u e sf o c u so nf l a tc l a s s i f i c a t i o nw h e r et h ep r e d e f i n e dc a t e g o r i e s a r et r e a t e di ni s o l a t i o na n dt h e r ei sn os t r u c t u r ed e f i n i n gt h er e l a t i o na m o n gt h e m 3 5 】 t h i sp a p e rg i v e sa l lo v e r v i e wo fa u t o m a t i ct e x tc l a s s i f i c a t i o na n d ，s p e c i f i c a l l y , d e s i g n sa na n t o m a t i ch i e r a r c h i c a lt e x tc l a s s i f i c a t i o na p p r o a c h ( h t c s v m ) b a s e do n s v m s u p p o r tv e c t o rm a c h i n e s ( s v m ) i sar e l a t i v en e wc l a s so fm a c h i n el e a r n i n g t e c h n i q u e sf i r s ti n t r o d u c e db yv a p n i ki n19 9 2 5 6 1a n db a s e do nt h es t r u c t u r a lr i s k m i n i m i z a t i o np r i n c i p l ef r o mt h es t a t i s t i c a ll e a r n i n gt h e o r y , w h i c hh a v e b e e np r o m i s i n g m e t h o d sf o rc l a s s i f i c a t i o nb e c a u s eo ft h e i rs o l i dm a t h e m a t i c a lf o u n d a t i o n sa n dc o n v e y s e v e r a ls a l i e n tp r o p e r t i e st h a to t h e rm e t h o d sh a r d l yp r o v i d ea n ds c a r c e l yh a v eb e e n p r e v i o u s l ye x p l o r e di nt h ec o n t e x to fh i e r a r c h i c a lc l a s s i f i c a t i o n 【1 4 】。w ea l s op r o v i d ea f o r m a la n a l y s i so fc o m p u t a t i o n a lc o m p l e x i t yo fh t c s v mm e t h o da n dd e r i v ea c o m p l e x i t yo f p o l y n o m i a l t i m ef o rt r a i n i n gp h a s eo f h t c s v m f u r t h e r m o r e ，w ea p p l y o u r p r o p o s e dp e r f o r m a n c em e a s u r e m e n tf r a m e w o r kc a l l e d p m f h ct oe v a l u a t e h t c s v mm e t h o da n de x p e r i m e n t ss h o w so u rm e t h o di se f f e c t i v ea n df e a s i b l e ，a t s a m et i m et h es u c c e s s f u l a p p l i c a t i o no fh t c s v mm e t h o dt o r e a lp r o d u c tt h a t s u p p o r t e db yf o u n d a t i o nu n d e rg r a n t ( 2 0 0 3 k 0 5 一g 3 2 ) h a sw i t n e s s e dt h a to u ra l g o r i t h m i sr o b u s t ，p r a c t i c a l l yu s e f u l w ee s t a b l i s han e wp e r f o r m a n c em e a s u r e m e n t f r a m e w o r k ( p m f h c ) f o r h i e r a r c h i c a lc l a s s i f i c a t i o nw h i c hu s i n gc a t e g o r ys i m i l a r i t ya n dd i s t a n c et h a tc a p t u r et h e r e l a t i o n s h i p sb e t w e e nc a t e g o r i e s ，p m f h ci sn a t u r a le x t e n s i o no ft h o s eu s e di nf l a t c l a s s i f i c a t i o na n d c o n s i s t e n c y t ot h e m t h i st h e s i si n v e s t i g a t es e v e r a lr e p r e s e n t a t i v et e x tf e a t u r es e l e c t i o ns t r a t e g i e s ，a n d c o n d u c tt h ee x p e r i m e n t a lc o m p a r i s o nb e t w e e nt h e mw h i c hp r o v ez 2s t a t i s t i c s ( c h d g e n e r a l l yo u t r e r f o r m so t h e rf e a t u r es e l e c t i o nm e a s u r e s ，f i n a l l y , w h i c hi sa d o p t e di n h t c s v mc a t e g o r i z a t i o nm e t h o d k e y w o r d s ：c o n t e n tm a n a g e m e n t ；t e x tm i n i n g ；s v m ；h i e r a r c h i c a lc l a s s i f i c a t i o n ； 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名； 持指导教师签名：炙江 口年g 月，彦日口f 年月，7 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获碍西北大学或其它教育机构的学位或证书两使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：；樟 6 歹年i 月 第一章绪论 1 1 内容管理理论 第一章绪论 本节主要介绍内容管理，内容管理系统的相关的概念，应用领域和研究现状 等问题，最后提出了本文具体的研究内容。 1 1 1 内容管理概述 内容管理是目前业内的一项热门技术和应用，对于这项新兴的技术，业内尚 未有一个统一的定义。综合来看，内容管理是指在计算机系统中对内容整个生命 周期进行管理的过程，是协助组织和个人，借助信息技术，实现内容的创建、储 存、发布或者共享、应用、更新，并在企业、个人、组织、业务、战略等诸方面 产生价值的过程【2 1 。例如，对组织的管理者而言，内容管理系统可以为其提供决 策支持；而组织内部的员工以及其合作伙伴则通过该平台达到知识共享的功能等 【引。这里内容实质上就是任何类型的数字信息的结合体，内容来自多个信息源， 可以是文本、图形图像、w e b 页面、业务文档、数据库表单、视频、声音文件等。 应该说，内容是一个比数据、文档和信息更广的概念，是对各种结构化数据、非 结构化文档、信息的聚合。 内容管理系统就是能够支撑内容管理的一套工具的组合f 2 j ，更具体的说：它 实际上是一个从内容创建，审核一直到内容发布的平台，借助此平台，组织或者 个人以很低的成本实现对内容生命周期的管理。 内容管理系统在各个行业和领域具有广泛的应用前景控1 ，从目前国外的使用 情况看，内容管理几乎跨越了所有的行业：电信、金融、制造、零售、教育， 具体的应用领域包括：门户网站，项目协同管理，部门知识库系统，电子商务， 企业内部的知识管理，e l e a r n i n g 等。 内容管理系统可以分为两类：企业内容管理系统和w e b 内容管理系统。 ( 1 ) w e b 内容管理系统 目前，决定各种各样的商业化网站和信息服务系统生存与发展的关键是看其 能否为信息消费者及时而有效地提供他们所需要的最新信息，早期的w e b 丌发技 第一章绪论 术和w e b 更新方式已经无法满足要求，一方面是内容处理效率低下另一方面是内 容量的不断膨胀和内容种类的复杂多变，这迫切需要个高效低成本的工具来有 效管理我们的内容。 回顾w e b 开发技术转变过程，可以很清晰了解w e b 内容管理系统及其在商业 网站和各种各样的信息服务系统中不可替代的作用。 w e b 开发技术是一个由静态向动态逐渐发展的过程。w e b 的更新方式也有了 较大的变更，其变化主要有三个阶段：第一阶段：静态更新( s t a t i c ) ，主要特点 有手工编写h t m l 或借用网页制作工具、通过f t p 上传n i l e 务器上，更新缓慢， 容易出现链接错误，文档一致性难以保证，难以对数据进行有效的组织和维护， 对服务器无特别要求等；第二阶段：实时更新，主要特点有制作模板，使用动态 主页技术输出h t m l ( c g i 、p e r l 、a s p 、p h p 、j s p 、s e r v l e t ) ，更新速度菲常快， 需要服务器上有数据库支持，对服务器资源占用很严重，现在的大多数中小网站 广泛采用等；第三阶段：及时更掰，主要特点有引入了内容管理系统，自动的内 容复制功能，更新及时，不依赖于服务器平台、通过工作流对内容整个生命周期 进行支持，可进行版本控制，易扩展等。 目前大部分成熟的商业w e b 内容管理系统均具备一下特征： 1 ) 能够从多个信息源获取内容，包括：数据库，文件系统，应用程序，i n t e m e t 等。能够理解和接受各种形式的内容，例如：数据库记录，w o r d 或者p d f 文档， x m l 格式的数据，h t m l 格式的数据等，并能够将它们转换为统一格式进行存 储，例如以x m l 格式存储，从而实现内容本身与其表现形式的分离。 2 ) 可自由定制的内容模板以及直接在浏览器中使用所见即所得( w y s t w i g ) 编辑器在线编辑，一方面保证所发布内容在外观风格上保持一致，另外可以使组 织成员将注意力集中于内容本身，而不需要面对复杂的网页编辑，链接等复杂的 技术。 3 ) 多渠道内容发布，多形式内容发布。内容管理系统除了支持传统的p c 上 的浏览器外，还支持各种移动设备中的浏览器访问：内容可以使用h t m l ，p d f 或者w o r d 等格式来发布。 4 ) 内容生命周期中各个环节有工作流支持。基于角色的用户权限控制。 5 ) 支持层次化的类别结构或者频道( 栏目) 管理，多语言支持。 第一章绪论 6 ) 基于浏览器的界面，具有高可用性。 7 ) 内容有效性实际控制。 ( 2 ) 企业级内容管理系统 企业内容管理系统拥有了w e b 内容管理系统除拥有一切特征，区别仅在于企 业内容管理平台能够提供完整的a p i ，支持用户或者其他厂商开发自己的内容管 理应用。例如：如果内容管理平台提供了具有数据访问功能的a p i ，则用户可以 利用其他厂商提供的数据挖掘工具对存储的内容进行诸如分类，聚类，相关性分 析等数据挖掘工作，所挖掘出的分类，聚类，关联模式可以改善企业的经营和管 理，从而使内容真正转化为能够产生巨大价值的资产【9 1 。企业内容管理平台的a p i 应尽可能遵循现有的业界标准，保证开发人员易于上手，应用容易移植。 1 1 。2 内容管理研究现状 内容管理的应用范围较广，研究题目也很多。有关内容管理的研究可以分为 三个主要研究方向： ( 1 ) 功能研究，包括数据检索、数据存储、格式转换、多语种支持、安全管理、 页面创建、个性化定制、同步和复制等。 ( 2 ) 特定应用领域的研究，包括流媒体服务、多媒体内容管理、电子数据交换、 元数据和标引等。 ( 3 ) 内容管理技术研究以及内容管理和其他应用的集成研究：包括工作流管 理、数字版权保护、以及包括分类，聚类，相关性分析在内的数据挖掘和智能关 联技术等2 1 。 上述各个研究领域都有各自相对独立的研究内容，但也相互交叉而形成综合 的研究方向。本文的研究属于内容管理和其他应用的集成研究，具体探讨数据挖 掘领域的文本自动分类技术在内容管理中的应用。由于只限于对文本进行自动分 类，因此后面所提到的内容泛指文本形式的内容。 1 2 文本分类与内容管理 在内容管理系统中，内容的发布是一个重要的环节。为便于用户查找和导航 浏览，通常存在一个预定义的分类层次或者类似于树型结构的分类体系，例如， 美国国会图书馆分类法，或者美国专利分类法，甚至可以是领域专家自定义的分 第一章绪论 类体系，例如在y a h o o 中几万个目录构成一个庞大的目录树。任何内容通常都会 被置于这个层次化的分类体系中一个确定的类别，用户可以从根目录开始查找需 要的内容，逐步细化查找类别，还可以浏览相似的类别中的内容。如果不存在这 样一个层次化的分类体系，内容被无序的堆砌在一起，用户被迫在一个庞杂的内 容集合中逐个查找自己想要的内容，这是不可想象的。而人机交互领域的研究也 表明：与简单的将内容堆砌在一起相比，将内容按照一定的目录层次结构进行发 布将提升系统的可用性【1 7 l o 川，因此，将内容分类到一个预定义的主题层次或者 分类体系中是内容管理的一个关键步骤，但随着内容数量急剧增长和目录层次的 逐渐复杂，完全依赖人工完成分类将难以满足要求，一方面手工分类将使内容管 理系统的操作人员劳动强度过大，另一方面缓慢的手工分类也会对内容的发布造 成一定延迟。如果使用知识工程中的提出方法对文本进行自动分类，需要领域专 家手动建立复杂规则，并且随着系统的演化，需要对规则进行及时更新，系统维 护所花费的代价依然很大。而数据挖掘领域的机器学习方法所具有的优势则可以 很好的克服上述困难，它既可以对海量文本内容实现快速分类缩短内容从创建 到发布的时间延迟，减少手工分类的劳动强度；其次，使用学习方法建立起来的 分类模型无需设计人员进行复杂的编程或者领域专家建立繁琐的分类规则，并且 训练分类器的过程简单且易操作，无需专业人员干预，即使对机器学习方法一无 所知的人也能够很快熟练操作，降低了系统维护的难度，甚至如果在很好的解决 了二次规划以及载入平衡的问题后，实现分类器的自主学习，自动更新，使文本 自动分类技术对普通系统操作人员完全透明也是有可能的，这将进一步降低内容 管理系统操作人员的技术门槛，并且随着系统的使用和演化，极大的减少在系统 维护方面的开销。因此，将数据挖掘领域中的基于机器学习的文本分类技术移植 到内容管理中是内容管理领域的研究热点之一。 尽管基于机器学习的文本分类方法具备很多优点，且已取得丰硕的研究成果， 但目前对该方法大部分研究都集中于水平分类，即类别之间是无结构的，相互独 立的。而内容管理领域的类别体系是一种层次化的，类似于树状的结构，类别之 间有一定的相关性，因此简单的将机器学习的水平分类方法克隆到内容管理领域 显然是行不通的，内容管理领域需要一种新的能够进行层次分类的方法，该方法 可以将文本分类到层次化的类别空间中的一个或多个具体的类中，它是对原有水 第一章绪论 平分类方法的扩展，且训练和预测的过程中必须考虑类别之间的关系。从另一个 角度讲，当类别数量增大到一定程度后，例如像y a h o o 就存在几万个类别，如果 将分布于y a h o o 的树型层次结构中的几万个类别映射到一个平面上，形成一个具 有平面结构的类别体系，并且完全忽略类别之间的关系，则信息过载又一次发生 了，但这次发生在类别层，因为各个类无序的存在于一个平面，用户需要大量的 时间去逐个浏览和查找每一个类别。由此可以看出树型结构的分类层次相对于平 面结构的优势。 1 2 1 文本自动分类技术现状 文本 文本分类 习 图1 2 i 1 文本分类与机器学习之间的关系 自动文本分类是指依据文本包含的信息将文本按照一定的分类策略归于一个 或者多个类别中的应用技术。直到8 0 年代末，在自动文本分类领域占主导地位的 一直是基于知识工程的方法，它的思想是手工建立一个能够进行分类决策的专家 系统，这类专家系统包括了一些形如i f t h e n 的规则。 这种方法的典型例子是c o n s t r u e 系统。分类决策的专家系统的缺点是构建自 动分类器时必须为领域专家获取的知识和知识工程师的知识表示之间架起桥梁， 二者缺一不可，如果把这种分类器转移到不同的领域，工作必须重新开始。 9 0 年代以来，随着信息存储技术和通信技术的发展，大量的文字信息以计算 机可读的形式存在，这一方面加剧了对于快速，自动的文本分类的迫切需求，另 一方面又为基于机器学习的文本分类方法准备了充分的资源f 样例) 。在这种情况 第一章绪论 下，数据挖掘领域的机器学习的文本分类方法逐渐取代了知识工程的分类方法。 图1 2 1 1 中描述了文本分类与机器学习方法之间的关系。基于机器学习方法 的文本分类技术是文本挖掘领域一个重要分支，文本挖掘是数据挖掘领域中对复 杂类型数据挖掘的技术。文本挖掘是机器学习方法和信息检索两门学科的交叉边 缘学科，近年来以成为一个相对独立的研究领域并且取得了长足的发展。 机器学习方法一般是通过让计算机从样例中学习( 归纳) 输入到输出之间的函 数关系1 1 】，而不是由人去手动编程去实现输入到输出的函数映射，更直接的说： 这是一个由样例拟合计算机程序的过程。当计算机应用于非常复杂的问题时，有 时并不知道如何由给定的输入计算出期望的输出，或者这种计算的代价可能很高 时，机器学习更加体现出它的价值。 目前普遍使用的基于机器学习方法的自动分类技术有朴素贝叶斯分类，查找 相似性，决策树，贝叶斯网络和支持向量机( s v m 等。其中支持向量机是v a p n i k 在1 9 9 2 年提出的，具有完备的理论基础( 统计学习理论) 和优秀的分类性能，这是 本文以下将要详细讨论的机器学习方法。 国外对文本分类技术研究已经开展了很多年，并在邮件分类，电子会议，信 息过滤等方面得到了广泛的应用，其中较为成功的系统有麻省理工学院( n i t ) 为白 宫开发的邮件分类系统，卡耐基集团为路透社开发的c o n s t r u e 系统等1 。研究者 在运用机器学习方法对英文和欧洲语种进行自动文本分类方面积累了大量成果， 特别是对英文文本分类，几乎在在所有涉及到的问题上都有相当深入的探索。很 多实验结果表明s v m 是英文文本分类的最好方法 4 , 5 7 , 5 8 】。s u s a nd u m a i s 等学者 对这5 种方法在学习速度，分类速度，分类精确度等方面进行了专门的比较l ”j ， 对比实验表明：s v m 能够快速学习，快速分类，并且分类精度达到最高。 机器学习的文本分类方法通过学习来构建一个文本分类器，以最简单的二元 s v m 分类器为例：学习所使用的训练样本集是由标记为正或者负的文本文档构成 的，将训练样本归于正类或者负类的劳动是人们使用机器学习方法进行自动分类 所付出的唯一代价，相对于知识工程中的自动分类需要领域专家和知识工程师的 介入，机器学习方法的代价是微不足道的。这种优势使得基于机器学习方法的自 动分类系统极易推广和移植。 我因的自动文本分类工作起步较晚，大约始于8 0 年代初，由于中英文之间存 第一章绪论 在较大的差异，因此无法照搬国外的研究成果。中英文自动分类最大的区别在于 对中文文本进行特征选择和文本表达之前，首先需要对其进行分词。目前，各中 文分类系统的分类准确率都很低，离实用化，商品化还有很长的距离，其中主要 原因有： ( 1 ) 分词算法不足导致自动分类精度不高甚至无法分类。汉语词与词之间没有 自然切分标记，目前为止各种分词算法对歧异切分都还没有好的解决办法。 f 2 ) 分类主题词表不足。各学科发展迅猛异常，分支学科，边缘学科不断涌现， 使得词表的编制总是落后于学科的发展，使得基于词典切分算法总会有一些新词 切分不出，最终导致一部分文献无法分类。 ( 3 ) 中文文本分类领域缺乏一个标准的测试集用以评估分类性能。英文文本分 类已经有多个标准测试集来评价分类系统，例如最著名的r e u t e r s 一2 1 5 7 8 ， o h u s m e d 等。 因此，中文分词技术是制约中文文本分类的瓶颈。需要指出的是：目前提出 的屈指可数的几种机器学习的层次分类方法都是在原有的水平分类方法上的扩 充，两者有许多共同的概念，因此以下以水平分类为例介绍机器学习方法的一些 基本概念，模型和框架。 1 2 2 基于机器学习方法的文本分类技术 ( 1 ) 问题描述 简单地说，文档分类系统的任务是在给定的分类体系下，根据文档的内容自 动地确定文档所属的类别。从数学角度来看，文档分类是一个映射的过程，它将 未标明类别的文档映射到已有的类别中。该映射可以是一对一映射，也可以是一 对多的映射，一对多的映射也称为文档的多归属阔题。因为通常一篇文档可以同 多个类别相关联，用数学公式表示如下： f ：a 崎b 其中，a 为待分类的文档集合，b 为分类体系中的类别集合。文档分类的映射规 则是系统根据已经掌握的每类着干样本的数据信息，总结出分类的规律性而建立 的判别公式和判别规则；然后在遇到新文档时，根据总结出的判别规则，确定文 档相关的类别。 ( 2 ) 文本分类系统框架 第一章绪论 图1 2 ，2 ，1 概括了文本分类的框架体系。主要包括3 项： 1 ) 文本特征抽取( 文本表示) ：将文本从文档空间映射到文本特征空间，即将字 符串表示的文本转换为特征向量的形式。这涉及到通过一定的特征选择算法构建 特征空间，以及采用特征抽取和特征加权方法对文本进行预处理，对于中文文本， 还需要中文分词技术。大量的研究表明：“文本表示”的好坏将影响学习器的选择 与训练，对分类精度也有很大的影响。 2 ) i ) q 练分类器。让计算机通过学习已知的分类样本来拟合输入与输出之间的 函数映射关系，最终得到个分类模型，并且可以通过对象序列化将此分类模型 写入文件，当有分类任务时再调入该分类模型来预测样本的类别。 3 ) 使用分类器进行分类。首先将待预测的样本表示为文本特征向量的形式， 然后系统载入分类模型，预测该样本的类别。 甄 j 预测 门丽分类阶段 i 测试样例1分类阶段 l 一n 。 图1 2 , 2 1 文本分类框架 ( 3 ) 文本多归属 文档可以归属为多个类别。比如篇关于篮球的文档即可以属于体育类，也 可以属于商品类。这就要求分类器能够将某些具有多类别属性的文档分别划分到 相应的多个类别中。针对分类结果足概率值的分类器，例如b a y e s 分类器，可以 选择一个阈值，概率超过闽值的结果保留；否则，舍弃。这样最终得到的结果类 别的个数可以大于1 。而基于s v m 的多分类器采用投票法预测文本所属类别， 可以选择一个票数的阂值( 见2 3 节) 。票数超过阈值的类别保留：否则，舍弃。以 第一章绪论 1 一d 一1 的聚合方法为例：共有n ：掣个s v m 二元分类器，共有n 票。 2 最简单的方法可以根据总票数来选择阈值( 比如可以选择2 ) 。在确定闽值 时要综合考虑数据集的情况和类别界限，才能处理好多归属的问题。 1 3 本文所做的工作 包括分类、摘要、标引、聚类、相关性分析等在内的数据挖掘技术是目前内 容管理研究的热点之- - 1 “。本文紧密结合内容管理的特点和具体项目的实际需求， 在全面论述文本自动分类涉及的各项技术基础之上，设计了一种适用于内容管理 的文本层次分类方法h t c s v m ，它是对基本的二元5 v m 分类器的扩展。本文通过 实现内容管理平台提供的a p i 而将h t c s v m 分类方法成功应用于陕西省工业攻 关项目( 编号：2 0 0 3 k 0 5 一g 3 2 ) 中，实现了内容管理系统的层次文本自动分类功能。 本文在设计h t c s v m 层次分类方法的同时又提出了一种新的层次分类性能 评估框架p m f h c ，并且使用该评估框架对h t c s v m 层次分类方法的分类性能进 行了评估，实验结果表明：h t c s v m 层次分类方法性能良好，完全满足实用要求。 本文所作的主要工作总结如下： ( 1 ) 重点分析s v m 的理论基础和算法实现：本文重点分析s v m 理论基础一 统计学习理论来论述s v m 为什么能够避免经典学习方法中的过拟合，维数灾难 等问题，特别分析了s v m 在小样本的情况下为什么仍然具有良好的泛化能力， 而这些优势都是其他分类器所不具备的。由此证明在构造更复杂的层次分类方法 中使用s v m 作为基本的二元分类器是合理的选择。 ( 2 ) 层次分类方法h t c s v m ：针对内容管理系统的类别体系具有类似于树状 的结构这一特点，以及基本的二元s v m 无法直接应用于层次分类这事实，设 计了一个完整的层次分类方法h t c s v m ，并对h t c s v m 方法进行了复杂度分 析，而且使用本文提出的新的层次分类性能评估框架p m f h c 对其分类性能进行 评估，实验结果表明h t c s v m 方法的分类性能良好，所实现的层次分类系统能 够满足实用要求。 ( 3 ) 层次分类性能评估框架p m f h c ：传统的分类性能评估方法只针对水平 分类，本文提出一种新的层次分类，陆能评估框架，它与原有的水平分类性能评估 方法保持兼容，同时又充分考虑了层次分类的特点和类别之间的相关性对分类性 第一章绪论 能的影响。 ( 4 ) 文本特征选择技术：特征选择是文本分类的一个重要环节。由于特征空 间往往是高维的，对维数敏感的学习方法由于维数灾难而变的不可用。另外过高 的维数使得在进行文本特征抽取( 文本表达) 时所耗费的时间大大超过分类器预测 的时间。而一个好的特征选择策略对分类性能的提升是有帮助的。本文以s v m 作 为分类器，通过对比实验发现z 2 统计( c h i ) 特征选择策略对分类性能的提升贡献 最大，最终本文选择z2 统计( c h i ) 作为h t c s v m 方法的特征选择策略。 ( 5 ) 层次分类方法h t c s v m 在项目中的成功应用：陕西省工业攻关项目基 于文本挖掘的主动信息服务系统本质上是一个内容管理平台，通过实现该平台 提供的a p i 使得h t c s v m 层次分类方法成功应用于内容管理系统中，从而使该 系统具备了自动文本层次分类功能。该系统已经稳定运行半年左右，这不仅证明 了h t c s v m 方法在分类性能上是满足实用要求的，而且运行稳定可靠。 本文各章内容安排如下： 第二章首先介绍了机器学习方法的一些概念，阐述了几种基于机器学习方法 的文本分类技术原理；接着对s v m 理论基础进行了重点分析包括统计学习理论， 结构风险最小化，s v m 分类器原理，最后阐述了s v m 分类器聚合问题。 第三章第四章是本文的重点，分别详细阐述了本文提出的h t c s v m 层次分类方 法及其应用在陕西工业攻关项目中的实现细节，包括h t c s v i 层次分类方法的复杂 度分析和所采用文本特征选择和特征抽取方法：提出一个新的层次分类评估框架 p m f h c ，以及使用p m f h c 评估框架对h t c s v m 层次分类方法进行实验评估和实 验结果分析等，另外对陕西工业攻关项目基于文本挖掘的主动信息服务系统 也做了简要介绍。 第五章对本文的工作进行了总结，并阐述了h t c s v m 方法在未来需要改进 的地方。 o 第二章支持向量机与文本分类技术 第二章支持向量机与文本分类技术 本章将介绍机器学习方法的基本理论，对常用的基于机器学习的分类算法进 行了简单介绍和比较；解释支持向量机为什么能够解决机器学习系统所面临的问 题；详细讨论支持向量机的理论基础一一统计学习理论和结构风险最小化；最后 对s v m 分类器聚合问题进行论述。 2 1 机器学习方法简介 长期以来，构造可以从经验中学习的机器无论在哲学界还是在科技界都是研 究目标之一。人工智能领域的研究者从一开始就考虑了学习的问题，a l a nt r u i n g 在1 9 5 0 年就指出了学习器的思想，机器学习方法的发展已成为人工智能的一个重 要的子领域，最终形成了机器学习这样一个独立的学科领域f ”。 2 1 1 机器学习方法基本理论 当计算机应用到实际问题时，通常可以显式的描述出给定组输入如何推出 所需要的输出。而系统的设计者和最终的编码实现人员的任务是将其转换为一系 列的指令，使计算机能够遵循指令达到期望的结果；而当计算机应用于更复杂的 问题时，有时并不知道如何由给定的输入计算出期望的输出，或者这种计算的代 价可能很高。例如对一个复杂的化学反应进行建模，则无法获知不同反应物之间 相互作用的关系；再例如利用d n a 序列对蛋白质进行分类，或者对信用卡申请 表进行分类，以区分哪些人有能力偿还债务；这些问题都不能用传统的编程途径 来解决，因为系统设计者无法精确指定从输入数据到输出的方法。解决此问题的 一种策略是：让计算机从样例中学习输入到输出之间的函数对应关系，就像儿童 学习辨认赛车的过程，我们不需要告诉他区分赛车与普通汽车的标准或者规则， 只需要给他大量的赛车的例子即可。这种使用样例来合成计算机程序的方法称为 机器学习方法。其中当样例是以输入输出对给出时，称为监督学习。而有关输入 输出函数关系的样例称为训练数据。 机器学习的基本模型如图2 1 1 1 所示： s 是待研究的系统，l m 是学习器。给定z ，s 输出y ，l m 输出y 。可以一 第二章支持向量机与文本分类技术 般的表示为：变量j ，与x 之间存在定的未知的依赖关系，即遵循某未知的联 合概率f ( x ，y ) ，x 和y 之间的确定关系可以看作是其特例，机器学习就是根据n 一趋坠蔓r 丐荪r 飞一墼￥+ 一一一h 杀兰祀f n l 一一 二一l 堂翌垫竺塑f 二磊苗厂 图2 1 ，i i 机器学习的基本模型 个独立同分布的观测样本( _ ，y ，) ，( 石：，y ：) ，( _ ，y 。) 在一组函数杪( 中求一 个最优函数f ( x ，w o ) 对依赖关系进行估计，使期望风险 月( w ) = l l ( y ，f ( x ，w ) ) d f ( x ，j ，) 最小。其中t r ( x ，w ) 称为预测函数集或者称为假设集合或者假设空间，w 为函数 的广义参数，扩( w ) 可以表示任何函数集，l ( y ，f ( x ，w ) ) 是由于厂( 五w ) 对y 进行 预测而造成的损失。不同类型的学习问题有不同形式的损失函数。预测函数也称 为学习函数，学习模型或者学习机器。 ( 2 ) 二类问题，多类问题以及回归问题 在学习赛车的例子中，输出简单的为是或者否，它可以看作是二元输出值。 对于识别蛋白质类型的问题，输出值为有限数量的类型之一。对于化学反应的问 题输出值为实数值表示反应化合物的浓度。有二元输出值的问题称为二类问题， 有多个类别的问题称为多类问题。而实值输出的问题称为回归问题。 ( 3 ) 在线学习和批量学习 学习模型的另外一个问题是训练数据如何产生及如何输出到学习器。批量学 习和在线学习存在明显的区别，前者在学习一开始就把所有的训练数据都提供给 学习器；后者则让学习器一次只学习一个样例，并在正确接受输出前给出自己对 输出的估计。在线学习根据每个新样例更新当前假设，学习器的质量由学习期问 产生的总的错误数量来衡量。 第二章支持向量机与文本分类技术 “) 泛化性 一个假设正确分类训练集之外的数据的能力称为泛化性。这正是要优化的属 性。泛化性准则对学习算法附加了一种约束，这一点可以从一种极端情况下的机 械式学习来说明，许多经典的机器学习算法能够表示任意函数，并且对于困难的 训练数据集会得到一个类似机械式学习器的假设。所谓机械式学习器是指能够正 确分类训练数据，但对未见数据会做出根本无关联的预测。例如决策树可能会过 度增长直至针对每个训练样例有一个叶子节点。为了得到一致假设而使假设变得 过于复杂称为过拟合。控制此问题的方法是控制决策树的规模。例如可以对决策 树进行修剪操作。奥卡姆剃刀是该类方法的准则之一，它建议如果没有必要，不 必增加复杂性，或者说更精细的复杂性必须显著提高训练数据的分类精度。这实 际是在假设的复杂性和分类的精度之间获得一种平衡。 在本文的研究中，我们所采用的方法是为了获得另一种平衡，它涉及泛化误 差率上的统计边界。这样的边界通常依赖于分类器间隔这样的变量，并引发最优 化该变量的算法。统计结果为该变量的优化算法提供了一个有充分依据的理论基 础，它能够避免基于错误直觉的启发式方法所带来的危险。 从理论上讲，学习器可以1 0 0 的正确分类训练数据，但对于本文的研究， 这是没有意义的。如上所述，我们已经将研究的目标转移到泛化性上，既我们更 注重学习器对未见数据的分类效果。如果学习器的假设对训练数据具有很高的分 类精度，而对测试数据的分类精度较低，则说明学习器的假设出现了过拟合。本 章的后面部分将给出本文解决此问题的有效方法。 2 1 2 基于机器学习方法的分类算法概述 目前存在多种归纳式学习的分类算法，如支持向量机算法、决策树、神经网 络方法，最大平均熵方法，最近k 邻居方法和贝叶斯方法和向量距离分类法等。 本文重点采用s v m 方法进行分类算法的研究。 简单向量距离分类法 该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类 的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中一0 向 量间的距离( 相似度) ，最后判定文本属于与文本距离最近的类，具体步骤如下： ( 1 ) ；, - i - 算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平 第二章支持向量机与文本分类技术 均。 ( 2 ) 新文本到来后，分词，将文本表示为特征向量。 ( 3 ) 计算新文本特征向量和每类中心向量间的相似度，一般使用向量之间的内 积( 或者称为向量之间的余弦值) 来表达向量间的相似度，如图2 1 2 1 所示，公 式为： m s i m ( d f ，d ，) = 其中，d i 为待预测的文档的特征向量，d 为第v ，类的中心向量，为文档特征向 量的维数。为向量的第后维。 j 图2 1 2 1 文本特征向量之间的相似度比较 ( 4 ) 比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别 中。 贝叶斯分类方法 贝叶斯分类方法是一种最常用的有指导的方法。以贝叶斯定理为理论基础， 是一种在已知先验概率与条件概率的情况下的模式识别方法。贝叶斯分类器分两 种。一种是朴素贝叶斯分类器，它假设一个属性对给定类的影响独立于其他属性， 即特征独立性假设。当假设成立时，与其它分类算法相比，朴素贝叶斯分类器是 最精确的。但是，文本属性之间的依赖关系是可能存在的。另一种是贝叶斯网络 分类器。可以考虑属性之间的依赖程度，其计算复杂度l l t l - 素贝叶斯高得多，但 更能反映真实文本的情况。 该算法的基本思路是计算文本属于类别的概率，文本属于类别的几率等于文 本中每个词属于类别的几率的综合表达式，具体算法步骤如下： 第二章支持向置机与文本分类技术 ( 1 ) 计算特征词属于每个类别的几率向量，( w l ，w 2 ，”w n ) ，其中 l q i l + n ( w k ，d ，) = p ( l c ) = i v l f d i | 矿| + ( 暇，d ，) ( 2 1 2 1 ) 计算公式与计算互信息量的公式相l 司，表示特种库中总的特征数量，d j 表示第 c 类中文档集合。 ( 2 ) 在预测新的文档类别时，根据特征库中的特征( 词) 对文档进行分词，然后 按下面的公式计算该文档的d ，属于c j 类的概率。 蚂珏# 坐皿里竖( 2 m 2 ) 艺p ( cj 晷) 兀：，p ( e ；晷) ”k 鳓 其中，p ( qi 甸= 害篙筹，p ( ei 郇具有相似含义，| q 为类别总数 ( ，d ，) 为职在d ，中的词频。”为特征总数。 ( 3 ) 比较待预测文本属于各个类的概率，将文本分类