（计算机科学与技术专业论文）基于tan的文本分类方法研究.pdf

中文摘要 中文摘要 随着信息技术的发展，特别是i n t e r n e t 的应用和普及，文本信息迅速膨胀，使 得文本自动分类技术成为信息技术领域的一个重要研究方向。贝叶斯方法具有简 单、直观、性能稳定的优点，但目前基于贝叶斯模型的文本分类还主要局限于朴 素贝叶斯方法。朴素贝叶斯由于基于一个条件独立性假设，无法表达属性间的依 赖关系而影响了分类性能，贝叶斯网络虽然能表示这种依赖，但由于学习的复杂 性而无法应用于文本分类。t a n ( t r e e a u g m e n t e dn a i v eb a y e s ) 模型将贝叶斯网 络表示依赖关系的能力与朴素贝叶斯的简易性相结合，体现了学习的效率与准确 地描述属性之间相关性的一种适当折衷。目前基于t a n 文本分类的研究还比较少， 而且在已有的t a n 文本分类模型中也存在着许多不足，为此，本文对基于t a n 的文本分类模型进行研究。 一方面，本文对当前的t a n 文本分类模型b l t a n 进行了深入地分析，指出 该模型中存在的三个问题：未考虑文本中未出现的特征；忽略了特征的词频信息； t a n 模型构造中阈值选取的问题。针对第一个问题，本文结合朴素贝叶斯的多变 量伯努利文本分类模型，提出了t a n 文本分类的第一个改进模型b n l t a n ，实 验中验证b n l t a n 比b l t a n 具有更好的分类性能；针对第二个问题，本文类比 朴素贝叶斯的多项式模型，提出了t a n 文本分类的第二个改进模型m u l t a n ， 实验中验证m u l - t a n 的分类性能显著优于b n l t a n ；针对第三个问题，本文借 鉴传统贝叶斯网络学习中搜索+ 评估的思想，采用在“固定结构”上“顺序搜索” 的学习策略，提出了完全抛弃阈值选取的t a n 文本自动分类框架a t a n ，实验中 验证a t a n 可以取得与手动选取最好阈值相当的分类性能。 另一方面，本文对集成学习的框架和主要方法进行了深入研究，并针对t a n 进行了t a n 集成的三次尝试，提出了基于t a n 集成的三种模型，这三种模型均 以t a n 为基分类器，结论生成方法则统一采用投票方法，不同点在于个体分类器 的生成策略。a d a m l t a n 将t a n 与a d a b o o s t m 1 算法结合，通过不断调整训练 集的权重分布学习得到个体分类器；e b a g t a n 扩展了b a g g i n g 算法的思想，通过 在t a n 模型构造过程中无向加权树转成有向时随机选择根变量的方法，产生有差 异的个体分类器；f r s t a n 利用基于特征集的集成方法，在特征空间中随机选择 特征子集，并对其进行学习从而构造结构不同的个体分类器。实验中将三种集成 分类模型分别用于文本分类，对比其性能，并对实验结果给出了相应分析。 关键词：文本分类；t a n ；集成学习；贝叶斯网络；朴素贝叶斯 分类号：t p l 8 1 北京交通大学硕十论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , e s p e c i a l l yt h ea p p l i c a t i o na n d p o p u l a r i z a t i o no fi n t e r n e t ，e l e c t r o n i ct e x ti n f o r m a t i o ni se x p a n d i n gr a p i d l y , w h i c h m a k e s t e x tc a t e g o r i z a t i o nt e c h n o l o g yb e c o m ea l li m p o r t a n tr e s e a r c ha r e a a l t h o u g hb a y e s i a n m e t h o d sa r es i m p l e ，i n t u i t i v ea n ds t a b l ei np e r f o r m a n c e ，c u r r e n tt e x tc a t e g o r i z a t i o n a l g o r i t h m sb a s e do nb a y e s i a nm o d e l sa r em a i n l yc o n f i n e dt on a i v eb a y e sm e t h o d n a i v eb a y e ss h o w sap o o rc l a s s i f i c a t i o np e r f o r m a n c eb e c a u s eo fi t s a t t r i b u t e i n d e p e n d e n c ea s s u m p t i o n ，w h i c hm a k e si tu n a b l et oe x p r e s st h ed e p e n d e n c ea m o n g a t t r i b u t e s c o m p a r e dw i t hn a i v eb a y e s ，b a y e s i a nn e t w o r k se x p r e s st h ed e p e n d e n c e p e r f e c t l y , b u ts t i l lc a n tb eu s e df o rt e x tc a t e g o r i z a t i o na sar e s u l to ft h ec o m p l e x i t yo f l e a r n i n g t a n ( t r e e a u g m e n t e dn a i v eb a y e s ) c o m b i n e st h es i m p l i c i t yo fn a i v eb a y e s w i t ht h ea b i l i t yt oe x p r e s st h ed e p e n d e n c ea m o n ga t t r i b u t e si nb a y e s i a nn e t w o r k ，w h i c h r e f l e c t sa na p p r o p r i a t ec o m p r o m i s eb e t w e e nt h ee f f i c i e n c yo fl e a r n i n ga n da c c u r a t e d e s c r i p t i o no fc o r r e l a t i o na m o n ga t t r i b u t e s a tp r e s e n t ，l i t t l et e x tc a t e g o r i z a t i o nr e s e a r c h i sb a s e do nt a nm o d e la n dt h e r ea r es o m ed e f e c t si nt h ee x i s t i n gt a nt e x t c a t e g o r i z a t i o nm o d e l s ，c o n s e q u e n t l y , s e v e r a li s s u e so f t e x tc a t e g o r i z a t i o nb a s e do nt a n a r es t u d i e di nt h i st h e s i s o nt h eo n eh a n d ，t h i st h e s i si n t e n s i v e l ys t u d y st h ee x i s t i n gt a nt e x tc a t e g o r i z a t i o n m o d e lb l t a na n dp o i n t so u tt h r e ep r o b l e m s f i r s to fa 1 1 b l - t a nd o n tt a k et h e f e a t u r e st h a ta r en o ta p p e a r e di nt h et e x ti n t oa c c o u n t f o rt h i sp r o b l e m ，c o m b i n e dw i t h m u l t i v a r i a t eb e r n o u l l it e x tc a t e g o r i z a t i o nm o d e lo fn a i v eb a y e s ，t h i st h e s i sp r o p o s e s t h ef i r s ti m p r o v e da l g o r i t h mb n l t a n e x p e r i m e n t sr e s u l t ss h o wb n l t a nh a sb e t t e r c l a s s i f i c a t i o np e r f o r m a n c et h a nb l - t a n s e c o n d l y , b l t a ni g n o r e st h ei n f o r m a t i o no f w o r df r e q u e n c y , w h i c hi sv e r yi m p o r t a n tf o rf e a t u r e s f o rt h i sp r o b l e m ，c o m b i n e dw i t h m u l t i n o m i a lm o d e lo fn a i v eb a y e s ，t h i st h e s i sp r o p o s e st h es e c o n di m p r o v e da l g o r i t h m m u l - t a n e x p e r i m e n t sr e s u l t ss h o wm u l - t a n h a ss i g n i f i c a n t l yb e t t e rp e r f o r m a n c e t h a nb n l t a n f i n a l l y , t h e r ei sat h r e s h o l ds e l e c t i o np r o b l e mn o to n l yi nb l t a n ，b u t a l s oi nb n l - t a na n dm u l - t a n f o rt h i si s s u e ，d r a w i n go nt h es e a r c h i n g + s c o r i n g i d e a so ft r a d i t i o n a lb a y e s i a nn e t w o r kl e a r n i n g , t h i st h e s i sm a k e su s eo ft h es t r a t e g yo f f i x e dn e t w o r k a n d s e q u e n t i a ls e a r c h i n g ，a n dp r o p o s e sa na u t o m a t i ct a nt e x t c a t e g o r i z a t i o nf r a m e w o r ka t a n ，w h i c hg e t sr i do ft h et h r e s h o l ds e l e c t i o np r o b l e m c o m p l e t e l y e x p e r i m e n t sr e s u l t ss h o wa t a nc a n r e c e i v ee x a c t l yt h es a m ec l a s s i f i c a t i o n a b s t r a c t p e r f o r m a n c ea sm e t h o d sb ym a n u a l l ys e l e c t i n gt h eb e s tt h r e s h o l d s o nt h eo t h e rh a n d ，t h i st h e s i ss t u d i e st h ef r a m e w o r ka n dp r i m a r y l e a r n i n gm e t h o d s o fe n s e m b l el e a r n i n g , a n dp r o p o s e st h r e ee n s e m b l em o d e sb a s e do nt a n ，w h i c ha r ea l l u s i n gv o t i n ga st h eu n i f i e dc o n c l u s i o ng e n e r a t i n gm e t h o dw h i l ed i f f e r e n ti n t h e g e n e r a t i o ns t r a t e g y o fi n d i v i d u a lc l a s s i f i e r a d a m1 一t a nc o m b i n e st a nw i t h a d a b o o s t m1a l g o r i t h m ，l e a r n i n gd i f f e r e n ti n d i v i d u a lc l a s s i f i e r st h r o u g hc o n t i n u o u s a d j u s t m e n to ft h ew e i g h td i s t r i b u t i o no nt r a i n i n gs e t e b a g - t a ne x p a n d st h ei d e ao f b a g g i n ga l g o r i t h m ，o b t a i n i n gv a r i o u si n d i v i d u a lc l a s s i f i e r sb yr a n d o m l ys e l e c t i n gr o o t v a r i a b l e si nt h ec o u r s eo fc o n s t r u c t i n gt a ns t r u c t u r ew h e naw e i g h t e du n d i r e c t e dt r e e t r a n s f e r r e dt oad i r e c t e dt r e e f r s t a nm a k e su s eo ff e a t u r es e t sb a s e de n s e m b l e m e t h o d s ，w h i c hr a n d o m l ys e l e c t sf e a t u r es u b s e t sa n dr e c e i v e sd i f f e r e n ti n d i v i d u a l c l a s s i f i e r sb yl e a r n i n gt h e s ef e a t u r es u b s e t s i ne x p e r i m e n t s ，t h e s et h r e ee n s e m b l e m o d e l sa l eu s e df o rt e x t c a t e g o r i z a t i o n ；t h i s t h e s i sc o m p a r e st h ec l a s s i f i c a t i o n p e r f o r m a n c e sa n dg i v e sc o r r e s p o n d i n ga n a l y s i so ft h ee x p e r i m e n t a lr e s u l t s k e y w o r d s ：t e x tc a t e g o r i z a t i o n ；t a n ；e n s e m b l el e a r n i n g ；b a y e s i a nn e t w o r k ； n a i v eb a y e s c i 。a s s n 0 ：t p l8 1 北京交通人学硕十论文 独创一陛声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字同期：年匆月扩日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字同期：1 尸7 年月 新繇亍磊7 签字日期：厮石月，彳日 致谢 值此论文完成之际，谨向两年来给我以指导、帮助、支持的所有老师和同学 们表示衷心地感谢。学位论文的顺利完成得益于众多师长、学友和亲人的鼎力支 持，感激之情，难于言表。 首先，我要衷心地感谢我的导师于剑教授，本文是在他的悉心指导下完成的。 于剑教授深厚的理论功底、渊博的学识、严谨的治学态度、和蔼可亲的待人方式 深深地影响和教育着我，也为我将来的工作和学习树立了榜样。在此，谨向于老 师表达我的谢意! 其次，我要感谢贾彩燕老师，在论文的撰写过程中，贾老师给予我热情的关 怀、指导和帮助，对我的论文进行了详细的指导，倾注了很多心血，并提出了很 多中肯的意见和建议，使我得以比较顺利地完成本论文的工作。 再次，感谢实验室的周雪忠、景丽萍老师在讨论班上给予的帮助和中肯意见。 感谢师兄弟庄力、王国栋、秦建、纳跃跃，师姐妹肖字、朱岩、杨丽丽、刘东菊、 马丽艳、恽佳丽，与他们的讨论拓宽了我的思路，开阔了我的视野。感谢我的舍 友孟庆祥同学，还有我的好朋友田春子、卢晓露、高芳、赵虹、马文琳，我深深 地感谢他们在学习和生活上对我的帮助。 特别地，我要感谢我的父母和哥哥嫂嫂，感谢我的女朋友韩雪，他们一直是 我坚强的后盾和信心的源泉，没有他们就没有我的一切! 再一次感谢所有关心、支持和帮助过我的人们! 刘佳 2 0 0 9 年5 月于北京 i 绪论 1 1研究背景与意义 1 绪论 随着信息技术的发展，特别是i n t e m e t 的应用和普及，电子信息资源急剧增长， 中国网页总数已超过1 6 0 亿个【1 】，谷歌的网页索引数量更是突破了一万亿【2 】，然 而这也仅仅是当前全球网页的一小部分。人们已经从一个信息匮乏的时代过渡到 信息极为极为丰富的数字化时代。由于互联网上拥有的信息资源呈无限、无序、 庞杂的特征，增加了人们获取有效信息的难度；再者，当今信息产生的速度远远 超过人们对信息的利用能力，使得人们在日益膨胀的信息面前无法快速地查找到 所需的信息，从而造成了时间、金钱和精力上的巨大浪费。如何有效地组织和管 理这些资源，并快速、准确地找到用户所需信息成为当前信息技术领域面临的一 大问题。传统的仅仅依靠人工对文档进行分类和管理已经远远不能满足社会发展 的需要，研究与开发自动、快速、准确的文本分类系统，以实现对大规模文档信 息的智能分析、组织和管理就显得尤为重要。 文本分类【3 】( t e x tc a t e g o r i z a t i o n ，t c ) 是根据给定文本的内容，将其判别为 事先确定的若干个文本类别中的某一类或者几类的过程。从数学角度看，文本分 类是一个映射过程，它将未标明类别的文档映射到分类系统下已有的类别中，该 映射是一对一或者一对多的映射，分别表示了文本对应一个或者多个类别的情况。 目前，自动文本分类已成为一项具有较大实用价值的关键技术，应用领域广 泛，包括信息过滤、信息检索、文本数据库、数字化图书馆等【4 】。 1 、信息过滤 信息过滤( i n f o r m a t i o nf i l t e r i n g ，i f ) 是指根据用户的需要，对产生或到来的 文档信息进行动态地分类、筛选，保留相关信息、屏蔽无关信息的过程。网络的 发展与普及，大大方便了我们获取信息，但信息量之大也给人们对信息的处理带 来了极大困难，无法快速地得到用户所需的信息，同时还会带来一些反面的信息。 信息过滤可以用来解决这些问题，其本质是一个二分类问题( 分为“相关”和“无 关”两类) ，既可以用来将用户反感的信息滤掉，如色情、暴力、反动信息、垃圾 邮件等，也可以用来将用户感兴趣的信息滤出，主动推送给用户，方便用户快速 准确地获取信息。 2 、信息检索 信息检索( i n f o r m a t i o nr e t r i e v a l ) 通常指文本信息检索，是根据用户的需求从 北京交通大学硕十论文 大规模文档集中提取并返回用户所需信息的过程。将大量的文本信息按主题层次 归类组织可以极大简化对信息的检索，如果按照类别对文档进行检索或对检索结 果进行一次文档分类，都可以提高检索的查准率。目前很多w e b 搜索引擎站点都 使用了w e b 文档层次化分类组织，比如y a h o o 、d m o z 、l o o k s m a r t 等都是这样。 3 、文本数据库 对信息进行有效地加工和整理可以使人们更好地掌握信息，如图书馆利用图 书分类法管理所收藏图书资料，y a h o o 利用人工分类的方法标记其分类条目等。一 方面，文本数据库通过对文档的组织和条理化，可以为以后的文档使用和查找提 供方便，提高使用效率。另一方面，随着研究的深入，文本数据库的功能已不局 限于存储、组织和查询文档信息，而是可以提供多层次的服务，如文本挖掘等。 由此可见，文本分类技术不仅对文本数据库存储、文档组织具有重要的意义，而 且也是文本挖掘的重要内容。 4 、数字化图书馆 数字图书馆是提供资源的组织机构，它选择、结构化、注释、分发、完整保 存数字资源，并提供知识访问服务，以便资源容易地和经济地被用户和团体使用， 它以计算机可存取的形式保存所有的或部分的馆藏资料，这些数字资料是对常规 印刷和缩微胶片资料的补充。图书馆的数字化管理是当前图书馆工程的一项重要 内容，是大势所趋，资料的数字化比重正同益增大，对其进行归类时，管理员不 可能对各个学科都非常了解，使用文本自动分类技术，则可以帮助其正确归类。 以上说的只是文本分类技术应用的几个方面，它还可以用在词义辨析、文档 流派划分、自动文摘等领域。可见，文本分类的研究有着广阔的应用前景，可以 创造巨大的经济和社会效益。 1 2国内外研究现状 文本分类是一个复杂的过程，包括文本预处理、文本表示、特征选择、分类 模型设计、性能评估等主要步骤，其中核心是分类模型的设计，它对文本分类性 能的影响最大。 从文本分类的方法看，现有的文本分类技术主要采用三种类型的方法 4 】：基 于统计的方法，如朴素贝叶斯 5 【6 】【7 】( n a i v eb a y e s ，n b ) 、k 近邻【8 】【9 】【l o 】 ( k n e a r e s tn e i g h b o r ，k n n ) 、支持向量机【l1 】 1 2 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 、 线性最小平方拟合 1 3 1 4 】( l i n e a rl e a s t s q u a r ef i t ，l l s f ) 等方法：基于连接的 方法，如人工神经网络 1 5 】( n e u r a ln e t w o r k ，n n e t ) ；基于规则的方法，如决策树 【1 6 1 7 、关联规则 1 8 】【1 9 】等。文本分类的效果一般和文本集合直接相关，如有的 2 1 绪论 文本集包含大量噪音，有的存在缺失数据，有的分布稀疏，因此，普遍认为没有 一种适合所有数据的最佳模型。 一直以来，贝叶斯方法以其坚实的概率论基础和直观的图形表示，在模式识 别与模式分类领域被广泛应用与研究。与其它方法相比，贝叶斯方法更加简单、 直观，可以方便的将先验知识和后验数据相结合，避免只使用先验信息可能带来 的主观偏见和只使用样本数据带来的噪声影响，同时它可以将定性判断与定量分 析相结合，更加灵活方便。目前，贝叶斯应用涉及的领域包括计算机视觉、自然 语言处理、机器人导航、医疗诊断、金融分析等。在文本处理中，贝叶斯方法已 经被成功应用于文本检索 2 0 】 2 1 】、文本信息抽取 2 2 和文本分类 2 3 2 4 】，但是文 档中动辄成千上万的特征也对贝叶斯方法的执行效率构成了极大影响，因此，早 期的文本应用中，研究大多集中于结构更简单的朴素贝叶斯模型。 朴素贝叶斯是目前公认的一种简单有效的概率分类方法，其模型假定所有的 属性变量都是相互类条件独立的，每个结点只与类结点相关联。相对于其它分类 算法，朴素贝叶斯的最大特点是不需要搜索，只需要简单地计算训练例中各个属 性值发生的频率，就可以估计出每个属性的概率值，因而朴素贝叶斯分类器的效 率比较高，而且适合处理属性个数较多的分类问题。然而在现实世界中，朴素贝 叶斯的这种独立性假设经常是不满足的，属性之间或多或少存在着联系，朴素贝 叶斯无法表达这种依赖关系而影响了分类性能。 相对于朴素贝叶斯，贝叶斯网络 2 5 1 的最大特点是可以表示属性之间的依赖关 系，它由一个有向无坏图( d i r e c t e d a c y c l i cg r a p h ，d a g ) 和条件概率表( c o n d i t i o n a l p r o b a b i l i t yt a b l e ，c p t ) 组成。d a g 中的结点代表随机变量，弧表示两结点间的 依赖关系，依赖程度由条件概率参数决定；网络中任意结点均有一个相应的c p t ， 用以表示该结点在父结点取各可能值时的条件概率。在贝叶斯网中，也有一个独 立性假设，即：给定变量的父结点，该变量条件独立于它的非后继结点。独立性 声明可以减少刻画概率分布所需的参数个数，有效地计算后验概率，但是，即使 如此，贝叶斯网的学习依然非常困难，有文献已证明贝叶斯网络的学习是一个 n p h a r d 问题 2 6 】 2 7 】，尤其在属性个数较多的情况下，学习没有任何限制的贝叶 斯网络所需要的时间和空间都是系统难以承受的。 f r i e d m a n 等人 2 8 提出了一种树状贝叶斯网络模型t a n ( t r e e a u g m e n t e d n a i v eb a y e s ) ，该模型是对朴素贝叶斯的一种改进，它放松朴素贝叶斯中的独立性 假设条件，将贝叶斯网络表示依赖关系的能力与朴素贝叶斯的简易性相结合，以 增强分类性能。t a n 是具有较好综合性能的分类模型，它体现了学习的效率与准 确地描述属性之间相关性的一种适当的折衷，与朴素贝叶斯分类器相比，其分类 性能明显优于朴素贝叶斯分类器 2 8 】【2 9 】。 北京交通大学硕士论文 目前，基于t a n 的研究主要集中在模式分类 2 9 】【3 0 】【3l 】【3 2 】 3 3 】【3 4 】，将t a n 模型用于文本分类的研究还比较少，石洪波等 3 5 3 1 3 6 最早将t a n 模型引入文本分 类，并在实验中与朴素贝叶斯方法比较，验证了t a n 在文本分类中具有较好的分 类性能。然而，石洪波等【3 5 】【3 6 】提出的t a n 文本分类模型仍存在着不足，比如模 型中没有考虑文档中未出现的特征、采用布尔表示法描述文档忽略了词频信息、 阈值的选取问题等，t a n 用于文本分类的这些问题值得考虑。 另外，集成学习已经成为国际机器学习界的研究热点，并被国际权威t g d i e t t e r i c h 称为当前机器学习四大研究方向之首 3 7 ，基于t a n 的集成在模式分类 中已有一定的研究 3 8 3 9 ，如何将集成技术与t a n 模型相结合并应用于文本分 类，从而进一步提升t a n 文本分类模型的分类性能值得研究。 l - 3 论文主要工作 本文旨在对t a n 文本分类方法进行深入研究，针对其面临的一些关键问题提 出有效的解决或改进方法，以提高t a n 在文本分类中的性能和可扩展性，本文的 主要工作可以概括为以下两个方面： l 、基于t a n 的文本分类 t a n 模型由于网络结构简单、分类性能好，在模式分类中得到了广泛应用， 然而基于t a n 模型的文本分类研究却寥寥无几。石洪波等【3 5 】【3 6 最早将t a n 模 型引入文本分类问题，并在实验中与朴素贝叶斯比较，验证了t a n 在文本分类中 具有较好的分类性能。本文对石洪波的t a n 文本分类模型b l t a n 进行详细的分 析，针对该模型中存在的三个问题分别进行了改进，进而提出了两个改进算法和 一个改进框架。首先，b l t a n 在对t a n 网络结构进行参数估计时，只考虑了文 本中出现的特征，忽略了未出现的特征，然而实际中未出现的特征可能也会提供 有利于分类的重要信息，本文类比于朴素贝叶斯的多变量伯努利文本分类模型， 对t a n 文本分类模型进行了第一次改进并提出了第一个改进算法b n l t a n ，实 验中验证b n l t a n 比b l - t a n 具有更好的分类性能；其次，b l t a n 采用布尔表 示法描述文档，忽略特征词频信息的重要性，类比于朴素贝叶斯文本分类的多项 式模型，本文又对t a n 文本分类模型进行了第二次改进，并提出了第二个改进算 法m u l t a n ，实验中验证m u l t a n 的分类性能显著优于b n l t a n ；再次，不 管是b l t a n ，还是对其进行的前两次改进b n l t a n 、m u l t a n ，都存在着阈值 选取的问题，本文借鉴传统贝叶斯网络学习中搜索+ 评估的思想，采用在“固定结 构”上“顺序搜索”的学习策略，提出了完全抛弃阈值选取的自动t a n 文本分类 框架a t a n ，实验中验证a t a n 可以取得与手动选取最好阈值相当的分类性能。 4 1 绪论 2 、基于t a n 集成的文本分类 集成学习已经成为国际机器学习界的研究热点，并被国际权威t gd i e t t e r i c h 称为当前机器学习四大研究方向之首 3 7 。集成学习方法主要包括基于数据的集 成( b o o s t i n g 和b a g g i n g 方法等) 和基于特征集的集成。本文对集成学习的框架和 主要方法进行了深入研究，并结合t a n 进行了t a n 集成的三次尝试，提出了基 于t a n 集成的三种模型，这三种模型均以t a n 为基分类器，结论生成方法则统 一采用投票方法，不同点在于个体分类器的生成策略。第一个模型a d a m l - t a n ， 将t a n 与a d a b o o s t m 1 算法结合，通过不断调整训练集的权重分布学习得到个体 分类器；第二个模型e b a g t a n ，借鉴了b a g g i n g 算法的思想但对其进行扩展，通 过在t a n 模型构造过程中无向加权树转成有向时随机选择根变量的方法，产生有 差异的个体分类器；第三个模型f r s t a n ，利用了基于特征集的集成方法，在特 征空间中随机选择特征子集，并对其进行学习从而构造结构不同的个体分类器。 本文在文本分类实验中对这三种t a n 集成模型进行性能对比，并对实验结果给出 了相应分析。 1 4 论文组织结构 本文分为六章，文章结构及各章主要内容组织如下t 第一章介绍了课题的研究背景与意义，分析了国内外研究现状，概括了本文 的主要工作，最后给出了本文的整体组织结构。 、。 第二章介绍了文本分类的基础理论，包括文本表示、文本特征选择、文本分 类算法、文本分类性能评价等。 第三章介绍了贝叶斯网络的基础理论，包括贝叶斯网络的表示与学习，重点 总结了贝叶斯网络的参数学习和结构学习方法。 第四章研究基于t a n 的文本分类。首先对石洪波等提出的t a n 文本分类模 型进行详细的分析，然后针对该模型存在的几个问题，对其进行了三次改进，包 括两个改进算法和一个改进框架，最后在实验中验证了t a n 文本分类改进模型的 分类性能。 第五章研究基于t a n 集成的文本分类。首先对当前集成学习的框架和主要方 法进行研究，然后结合t a n 进行了三次t a n 集成尝试，提出了基于t a n 集成的 三种模型，最后在实验中对这几种集成模型的分类性能进行对比，并对实验结果 给出了分析。 第六章总结了本文的研究工作，并对今后的研究做出了展望。 北京交通人学硕十论文 2 1文本表示 2 文本分类基础理论 在大规模文本分类系统中，我们所处理的原始数据是非结构化的自然语言文 本，计算机并不能轻易地“读懂 它们，因而若要对这些信息进行分析与处理， 首要的任务就是将它们从一个无结构的原始文本转化为计算机可识别处理的结构 化信息，即对文本进行形式化处理，这个形式化的结果一般称为文本表示 3 7 】。 文本表示问题包括两个方面：用于表征文档语义的特征和这些特征的组织方 式 4 】。常用的文本特征包括词、短语、n - g r a m 项 4 l 】 4 2 】【4 3 】，词性【4 4 】等，在实 际应用中，到底选择哪种单位作为文本的特征必须要综合考虑，如处理速度、精 度要求、存储空间等诸多因素。选择的单位越具有代表性，语言的层次越高，它 所包含的信息也就越丰富，但同时进行分析所付出的代价也就越大。大量研究表 明，用单个词与用复杂的表示( 如短语、词性等) 作为特征分类的效果差异不大。 然而可以很容易地想到，用短语或词性等表示特征必然会导致计算更加复杂以及 耗费更多的资源，因此大部分文本分类的研究都是将单个词作为特征。特征的组 织方式亦即文本的表示模型，包括向量空间模型 4 5 】( v e c t o rs p a c em o d e l ，v s m ) 、 布尔模型( b o o l e a nm o d e l ) 及概率模型( p r o b a b i l i s t i cm o d e l ) 等。向量空间模型 是s a l t o n 等于上世纪6 0 年代提出的，是现在应用最广泛的基于统计的模型，本文 也将采用此模型。 向量空间模型的基本思想是用词袋( b a go fw 6 r d s ，b o w ) 表示文本，每个 词条作为特征空间坐标系的一维，将文本看作特征空问的一个向量，用两个向量 之间的夹角来衡量两个文本之间的相似度。在向量空间模型中，每一个文档都被 表示为一组规范化j 下交词条向量所张成的向量空间中的一个点。假设由刀个特征 项词条组成的集合为v = t ，t ，f 。) ，则文档d ，形式化为刀维空问的一个向量： d ，= w l ，w f 2 ，) ，表示d ，的第k 个特征项词条，。的权重( 其中k = l ，z ，1 ) 。 向量的每一维的值表示了特征项在文档中的权重，用以刻画该特征项在描述此文 档内容时所起作用的重要程度，权值越大，表示该特征项在文档中的分量越重， 即该特征项越能反映d ；的内容。 目前特征项权重的计算通常有布尔函数、丌根号函数及t f i d f 4 6 函数等多种 方法。t f i d f 是目前广泛采用的权重计算方法，是由s a l t o n 在1 9 8 8 年提出的，它 的指导思想是：在一个文本中出现次数很多的单词，在另一个同类文本中出现次 数也会很多，反之办然。该方法是根据特征词的重要性与特征词的文档内频数成 6 2 文本分类基础理论 正比，与训练文档中出现该词条的文档频数成反比的原理构造的。常用频率因子 和文档集因子的乘积表示： = 如坝 ( 2 1 ) 其中心定义同上，频率因子吮表示特征项气在文档d ，中出现的频率；文档集 因子坝是该特征项在文档集合中分量情况的量化。 经典的t f i d f 方法考虑两个因素：( 1 ) 词语频率t f ( t e r mf r e q u e n c y ) ：词语 在文档中出现的次数；( 2 ) 词语倒排文档频率i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) - 该词语在文档集合中分布情况的一种量化，常用的计算方法是l o g ( n n 。+ o 0 1 ) ， 其中为文档集合中的文档数目，刀。为出现该词语的文本数。 根据以上两个因素，可以得出公式： = 如l o g ( n n t + o 0 1 ) 考虑到文本长度对权值的影响，还应对项的权值公式做归一化的处理， 特征项权值规范到【o ，l 】之间，公式如下： ( 2 - 2 ) 将各 ：下丝丝些坠坠( 2 - 3 ) 、( 如) 2 l 0 9 2 ( n n t + o 0 1 ) yk = i 另外，对于特征较为明显的文本类别，往往有少数项的出现频率远远大于其 它项，根据上述计算公式计算出的权值会很高，如果个别权值很高，在分类过程 中往往会抑制其它项的作用。因此在计算各项权重的时候，应对统计出的词频做 适当的均衡处理，较为简单的均衡处理方法是对统计出的权值进行开平方。经过 词频均衡处理的t f i d f 权值计算公式为： ：；丝丝丝竺竺( 2 - 4 )m - = 7 2 = = = = = = = = = = = = = = = = = = = = o 、( 吮) 2 l 0 9 2 ( n n t + o 0 1 ) yk = l 该公式基于这样的假设：区分文档最有意义的特征词是那些在指定文档中出 现频率足够大，而在文档集的其它文档中出现频率足够小的词。t f i d f 权重计算 法刻画了特征表达文本内容属性的能力，t f 越大，特征项在文档集中出现的范围 越广，说明它的重要程度越高；i d f 越大，特征项在文档中的分布越集中，说明它 在区分该文档内容属性方面的能力越强。最终那些具有较高出现频率并且在文档 集合中较少的文档中出现的特征项将被赋予较高的权值。本文对于特征项权重的 计算将采用公式( 2 4 ) 。 7 北京交通人学硕士论文 2 2文本特征选择 由于文本数据的半结构甚至无结构化的特点，使得用特征向量对文档进行表 示的时候，通常会达到几万甚至几十万维，即使经过初始的筛选处理( 如去除停 用词等) 仍会有很高维数的特征向量留下。然而，并不是选择的特征越多就越好， 有些特征的加入不但增加了计算复杂度，而且还可能会使分类性能降低。有研究 表i 耍j 4 7 ，在经过特征压缩后的特征空间中进行文本分类不但不会降低分类系统的 分类性能，而且会有助于提高分类的精确度。因此无论从降低计算复杂度，提高 效率的角度，还是从提高分类准确率的角度考虑，我们都有必要进行特征选择。 目前，特征选择一般是首先通过一个特征评价函数，对特征空间的每一个特 征进行评估量化，然后依据评估分数的大小对所有特征排序，最后根据需要选取 预定数目的最佳特征。在文本分类的特征选择中常见的评价函数有 4 7 4 8 】：文档 频率( 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 ) ，期望交叉 熵( e x p e c t e dc r o s se n t r o p y ，c e ) ，互信息( m u t u a li n f o r m a t i o n ) ，z 2 统计法( c h i ) 等。这些方法都是基于闽值的统计方法，即对每一个特征计算某种统计度量值， 然后设定一个阈值s ，过滤值小于s 的那些特征，剩下的即认为是有效特征。以下 选择几种有代表性的选择方法作简单介绍。 2 2 1文档频率 文档频率( d o c u m e n tf r e q u e n c y ，d f ) ，定义为包含该特征的训练文档数目。 在运用文档频率进行特征选择时，首先要计算各个特征项在训练集合中的文档频 率，然后根据预先设定的阈值排除那些文档频率特别低和特别高的特征项，因为 它们分别代表了“没有代表性”和“没有区分度”两种极端的情况。文档频率的 计算复杂度较低，随训练集的增加而线性增加，能够适用于大规模语料。 文档频率是最简单的一种文本特征选择方法，同时也是最有效的文本特征选 择方法之一。然而，由于缺乏必要的理论基础，文档频率一直被认为是一种用来 改善文本分类器效率的权益之计，而不能算是严格意义上的文本特征选择方法。 2 2 2信息增益 信息增益( i n f o r m a t i o ng a i n ，i g ) ，是一个基于熵的评估方法，定义为特征为 整个分类提供的信息量( 不考虑该特征的熵与考虑该特征后的熵的差值) ，定义如 ( 2 - 5 ) ： 8 2 文本分类基础理论