（计算机软件与理论专业论文）利用关联规则挖掘算法的中文短文本分类研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重庞自g 直太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：王今旧救 签字日期： 2 。? 年f 月；，日 学位论文版权使用授权书 本学位论文作者完全了解重麽邮电态堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权 重麽自e 鱼太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王；嗣板 导师签名：蕴矿 签字日期： z 寸。7 年乡月3 1 日 签字日期：加。7 年月? 日 重庆邮电大学硕士论文摘要 摘要 即时通讯技术的发展以及信息技术的普及促进了手机短信、基于互联 网和手机短信息的客户评论等短文本信息处理技术的发展，同时短文本处 理技术的发展和实际应用又息息相关，它在信息安全、客户评论反馈等领 域都存在着实际的需求，使中文短文本分类问题成为一个重要的研究方 向。 由于短文本所描述概念信号弱的特性，现有的对长文本分类性能好的 分类技术用于短文本时分类器性能变坏。短文本分类的可行途径是利用外 部资源中的额外信息来辅助分类，以弥补短文本的固有缺陷。关联规则挖 掘算法正好可以在一定程度上解决短文本知识发现的问题。本文利用关联 规则挖掘算法，就中文短文本中共现关系的挖掘、特征的扩展进行了研究。 主要工作如下： ( 1 ) 提出一种基于测试文本特征扩展的短文本分类方法。该方法将短 文本视作事务，将特征词视作项，利用f p g r o w t h 算法挖掘训练集特征项 中的共现关系，创建特征共现集作为扩展词表。在分类阶段，先根据特征 共现集把测试文本中的特征的共现词作为特征补充进来，然后再进行分 类。 ( 2 ) 提出一种基于训练文本特征扩展的短文本分类方法。该方法与( 1 ) 中方法基于相同的扩展词表，但是扩展方法不同。在没有引入新的特征的 前提下，在训练阶段用一种基于共现关系的特征权重调整方法实现训练文 本特征扩展。 实验结果表明，这两种方法具有较高的分类性能，其微平均f 1 和宏 平均f l 值都高于常规的文本分类方法，在一定程度上解决短文本所描述 概念信号弱的问题。 关键词：短文本分类，关联规则挖掘，特征扩展，共现关系 a b s t r a c t n l ed e v e l o p m e mo fi 粥t a i l t m e s s a g i n gt e c l l l l o l o g ) r 锄dt l l ep o p u l 撕z a t i o no f i 1 1 f 1 0 m a t i o np c e s s i n gt e c l u l o l o g yp r o m o t e d l eb o o m i n go fs h o r t - t e x ti l l f 0 彻a t i o n p r o c e s s i n gt e c l l i 】l o l o g ) r ，s u c ha st l l em o b i l ep h o n es m s ，c u s t o m e rr e v i e w sb a s e do nt h e i n t e n l e ta i l dm o b i l ep h o n es h o r tm e s s a g e s t h ed e v e l o p m e n to fs h o r t t e x ti n f o m a t i o n p r o c e s s i n gt e c t h l o l o g y ，o nt h eo t h e rh a n d ，i sc l o s e l yr e l a t e dt op m c t i c a la p p l i c a t i o n i t s a c t u a ld e m 觚d si i l 也ea r e ao fi i l f o m a t i o ns e c 面t ) ra i l dc u s t o m e rc o m m e n t j sf e e d b a c k ， e t c ，m a k et l l ep r o b l e mo fc l l i n e s es h o r t t e x tc l a s s i f i c a t i o nb e c o m ea i li m p o r t a n tr e s e a r c h d i r e c t i o n b e c a u s eo ft l 圮c h a r a c t e r i s t i c st l l a ts h o r tt e x t sd e s c r i b e w e a l 【s i 鳟a l s ，吐l c c l a s s m c a t i o n 劬c t i o no ft h ec u 盯e n tm e t l l o d sf o r1 0 n g - t e x tc l 嬲s m c “o i l ，w h e na p p l i e d t os h o r t t e x tc a t e g o r i z a t i o n ，d e t e r i o r a t e s o n ef e a s i b l ew a y t 0s h o n - t e x tc a t e g o r i z a t i o ni s t 0u t i l i z e l ee x n ai 1 1 f o 咖a t i o no fe x t e r i o rr e s o u r c e st 0 部s i s t l ec l a s s i f i c a t i o n a s s o c i a t i o nm i em i l l i n ga l g o r i 也m sc a nr e s o l v et h ep r o b l e mo fe x p l o r i i 唱k n o 、v l e d g ei n s h o n - t e x tt 0s o m ee x t e n t t h ep r e s e n tp a p e re x p l o r e st h em i i l i n go fc o o c c l l n e n c e r e l a t i o n s l l i pi i ls h o r t - t e x ta n dt l l ee x t e n d i n gm e t h o d so fi t s 佗狐鹏s ，b o t l la r el e a m tb y f p _ 3 t 0 叭ha l g o r i t l 皿： ( 1 ) am e t h o df o rc h i n e s es h o n t e x tc l a s s i f i c a t i o nb a s e do nt e s t i n gs e t 诧a _ t u r e e x t e n s i o ni sp r o p o s e d t 1 1 i sm e t l l o dv i e w ss h o n - t e x t 嬲n 独s a c t i o 脚，锄d 缸l m r e s 船 t e m s ，l l s i n gf p g r o w ma l g o r i t h mt om i r l ct l l ec o - o c c u r r e n c er e l a t i o n s l l i p 锄o n gt l l e f e a _ t u r ei t e m so f 慨n i i l gs e t ，a i l dt 0c o n s t r u c tt h es e to ff e a t i l r ec o o c c u r r e n c e 勰 e x p a i l s i o nv o c a b u l a 彤f i r s t l y ，也ef i e 孤鹏c o - o c c l l 玎e n c ew o r di sa d d e d 弱n e wf e a t l 鹏 a c c o r d i n gt 0 t l 抡s e to ff e a t u r ec o o c c u r r e n c ei nt h ec l a s s i f i c a t i o n s t a g e ，锄dt l l e n c l a s s i f i e d ( 2 ) am e t h o df o rc h i n e s es h o r t t e x tc l a s s i f i c a t i o nb a s e do n 缸a i l l i n gs e tf e a t u r e e x t e n s i o ni sp r o p o s e d t 嫩sm e t h o da n dt l l em e t l l o di n ( 1 ) w e r eb 弱e do nt h et l l es 锄e c x p a n s i o nv o c a b u l a 可，b u te x p a j l di 1 1d i 脏萤胁tw a y s i l lt l l e 锄i 1 1 i n gs t a g e ，t 0a c h i e v et 1 1 e e x p a i l s i o no ft l l e 仃a i nt e x tb yu s i n gam e t h o d w h i c hb a s e do nc o - 0 c c u 玎e n c er e l a t i o n s l l i p t oa d j u s tt l l ew e i g h to fc h a r a c t e r i s t i c s ，w i t h o u tn e wf e a n l r e s r e s u i t ss h o wt t l a t t t l et w op r o p o s e dm e t l l o d sp e 响n n 、l l ，s i n c eb o t l lo fi t s m i c r o f1a n dm em a c r 0 一f1a r eh i 曲e rt i l a i lt i l o s eo fc o n v e n t i o i l a l 印p r o a c h e s ，a n db o t l l i i 重庆邮电大学硕士论文a b s t r a c t t 0s o l v et l l ep r o b l e mo fs h o r tt e x t sd e s c r i b ew e a ks i g n a l st os o m ee x t e m k e yw o r d s ： s h o r tt e x tc l a s s i f i c a t i o n ，a s s o c i a t i o nm l em i i l i n g ，f e a t u r e se x t e n s i o n ， c o o c c u n e n c er e l a t i o n s h i p i i i 重庆邮电大学硕士论文目录 目录 摘要”i a b s t r a c t ii 第一章绪论 1 1 引言l 1 2 短文本分类的研究现状l 1 3 论文研究背景3 1 4 论文工作内容4 1 5 论文组织结构5 第二章相关理论基础6 2 1 引言6 2 2 文本分类相关理论6 2 2 1 预处理”7 2 2 2 特征选择“8 2 2 3 分类模型1l 2 2 4 文本分类的评估指标l3 2 3 关联规则挖掘理论基础一15 2 3 1 关联的形式描述1 5 2 3 2 关联规则挖掘的目的和过程1 6 2 3 3 关联规则挖掘算法1 6 2 4 本章小结。1 8 第三章基于测试文本特征扩展的短文本分类研究”19 3 1 引言l9 3 2 特征共现集的创建。2 0 3 3 测试文本特征扩展2 2 3 3 1 测试短文本特征扩展算法2 3 3 4 实验测试2 4 3 4 1 实验数据集2 4 3 4 2 特征共现集的生成实验2 4 3 4 - 3 中文短文本分类实验设置2 7 3 4 4 中文短文本分类实验结果与分析2 8 重庆邮电大学硕士论文目录 3 5 本章小结3 0 第四章基于训练文本特征扩展的短文本分类研究”3 1 4 1 引言3l 4 2 训练文本特征扩展的策略。3 2 4 2 1 基于共现关系的特征权重提升计算公式3 2 4 2 2 训练文本特征扩展算法3 3 4 3 实验测试3 4 4 3 1 实验数据3 4 4 3 2 实验方法设置3 4 4 3 3 实验结果及分析3 4 4 4 本章小结。3 6 第五章总结及未来工作3 8 5 1 总结3 8 5 2 未来工作。3 8 致j 射4 1 攻硕期间从事的科研工作及取得的研究成果4 2 参考文献4 3 v 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 随着互联网技术与移动通信技术的结合，手机短信、基于互联网和手 机短信息的客户评论等中文短文本形式的信息在最近几年进入了爆发式 的增长时期，已经成为一种重要的信息传播渠道，渗透到社会和生活的各 个领域，逐渐成为人们生活中不可或缺的沟通方式。这些形式的信息都有 一些共同特点：字数不多，大多数为1 6 0 字以内，但是数量非常大。 如此丰富的短文本资源给人们的生活的各个方面带来了许多便利的 同时也带来了重要的商业应用前景。例如，基于互联网络和手机短信息的 客户评论是企业获取产品性能、服务质量等反馈信息的重要途径。对大量 的客户评论进行自动分类为企业改进产品性能、改善服务质量等商业决策 提供了技术支持，在信息时代的今天具有特别重要的意义。 但是，也带来了信息安全的重大隐患。随着规模庞大、红红火火的短 信经济的发展，一些垃圾短信、骚扰短信也频频出现。从中奖通知到虚假 广告，从交友信息到黄色笑话五花八门的垃圾短信，令人烦不胜烦， 据工业和信息化部2 0 0 8 年1 1 月通信业移动电话用户数量统计结果显示中 国手机用户平均每周收到垃圾短信息的数量为l0 3 5 条【l l ，而中国2 0 0 8 年 垃圾短信息总量达3 4 1 l 亿条。在用户收到的违法、不良短信息中，涉嫌 欺诈类( 中奖、汇款等) 所占比例最高，达到2 8 6 0 ，与去年同期相比增 加了7 7 1 个百分点。垃圾短信数目巨大，已经严重影响了人们的工作和 生活，成为影响社会稳定的重要因素之一。因此必须对短信息中的有害信 息进行及时拦截和过滤。而短文本分类是解决手机短信息过滤这一现实任 务的基础。 上述应用使中文短文本分类问题成为一个重要的研究方向。 1 2 短文本分类的研究现状 近年来，越来越多的科研机构和企业开始关注短文本的处理方法，部 分单位也已经开展相关技术的研究【2 】 【3 1 。然而，当前的研究主要还局限于 重庆邮电大学硕士论文 第一章绪论 文本分类、信息检索等领域使用的长文本处理方法，结合大规模短文本自 身特点的处理方法尚未形成。在短文本分类领域，国内外只进行了少量的 工作【4 l ，【9 】，且其效果并不理想。由于文本自动分类的研究相对较早，而且 拥有比较成熟的技术，因此目前大多数短文本处理采用的方法主要还是传 统的文本分类、信息过滤和检索的方法，专门针对短文本自身特点的算法 还未形成。然而，与普通文本相比，由于短文本具有所描述信号弱、组织 随意、噪音数据繁多等特点，其自动分类的实现具有更多的挑战。 近年来，有研究者考虑将基于推理的方法用于短文本分类【4 1 ，h e n l y 的评估表明：和长文本相比，短文本分类要求不同的特征，甚至不同的分 类器来获得最好的性能。因此，用于短文本分类的分类系统需要在这些方 面进行一些层级配置。 z e l i k o v i t z 【5 】，【6 】在短文本分类中尝试使用了潜在语义索引( l a t e n t s e m a n t i ci n d e x i n g ，l s i ) 。l s i 是通过奇异值分解来创建简化向量空间的无指 导学习器。z e l i k o v i t z 在创建简化向量空间时将训练数据和未标记的测试样 本进行组合。她得出结论：扩展的特征空间中包括了对短文本分类有帮助 的语义关联。z e l i k o v i t z 【。7 j 也使用了在某些方面和训练数据相关的未标记的 背景信息来辅助分类。例如，当分类科学论文的标题时，未标记的背景信 息可以是训练集中论文的摘要。 q i a n gp u 和g u o w e iy a n g l 8 j 利用潜在语义索引l s i 进行文本预处理， 然后再利用独立部件分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，i c a ) 分类器对 中文短文本进行了研究。实验表明，组合l s i 和i c a 的方法仅比单独使用i c a 的方法好些，总体效果不理想。 s h e n z h e n gz u o 等1 9 j 通过从训练语料中抽取关键词语对中文短文本进 行了研究，尽管其实实验效果有所改善，但总体效果仍然不理想。吴薇【l o 】 等对短文本的过滤和分类技术进行了探索和研究。 樊兴华】等通过两步分类策略对短文本进行分类研究，为更好地挖掘 文本信息，研究了将两步策略用于中文短文本分类的3 个关键问题，提出 了基于组合朴素贝叶斯( n b ) 和k 近邻( k n n ) 分类器的两步中文短文本分类 方法：( 1 ) 直接利用n b 和k n n 的输出构造其对应的二维空间，根据该空间 内错误文本的分布将测试文本集分为3 部分：能被k n n 可靠分类的文本集 a ，不能被k n n 可靠分类但能被n b 可靠分类的文本集b ，其他文本集c 。( 2 ) 用k n n 、n b 分别对文本集a 和b 进行分类，根据训练语料的类别分布，直 接给属于文本集c 的文本分配标签。与n b 、k n n 和支持向量机( s v m ) 的对 比实验表明，该方法可获得较高的分类性能。 2 重庆邮电大学硕士论文第一章绪论 1 3 论文研究背景 短文本处理技术在信息安全、客户评论反馈等方面都存在着实际的需 求，因此，对短文本信息这类具有特殊意义的文本进行分析和研究，并建 立有效、准确的分类体系，显得尤其重要和紧迫。 在已有的短文本分类研究中，由于短文本具有所描述概念信号弱、类 别模糊度高的固有缺陷，现有的对长文本分类性能好的分类技术用于短文 本时分类器性能变坏。目前在短文本分类领域的研究成果表明，短文本分 类的可行途径是利用外部资源中的额外信息来辅助分类，目的是挖掘短文 本所表达的信息量，进行特征扩展，以弥补短文本天生的固有缺陷。特征 扩展中最关键的技术之一就在于扩展词表的构造，扩展词表的构造来源通 常有两种方式【l2 j ： 第一种是机器自动构造的资源( 例如未标记的测试数据和背景语料 等) ； 第二种是专家构造的资源( 例如现存的各种语言知识库等) 。如 w o r d n e t ，h o w n e t 等； z e l i k o v i t z 的工作【5 】，1 6 】正是对这种思想的一种尝试。使用了潜在语义索 引将训练数据和未标记的测试样本进行组合，z e l i k o v i t z 得出结论：扩展 的特征空间中包括了对短文本分类有帮助的语义关联。但她的方法总体效 果不理想。s h e n z h e n gz u o 等【9 j 通过从训练语料中抽取关键词语对中文短 文本进行了研究，尽管其实实验效果有所改善，但总体效果仍然不理想。 h u ih e 【1 3 】等用聚类的方法实现短文本文本主题信息的挖掘，首次采用统计 字符串还原算法进行特征提取。如何找到合适的方法挖掘资源中的有效信 息用于短文本特征扩展成为亟待解决的问题。 a g r a w a l 提出的关联规则( a s s o c i a t i o nr u l e s ) 就是为了发现数据集中不 同数据项之间的关系，如数据项对另一数据项的影响，而发现这样的规则 有利于数据分类，是解决挖掘短文本信息量的有效途径之一。关联规则挖 掘的优点是不需要预先给定检测对象的某些属性或特征的数学描述，而是 直接从给定问题的知识分类出发，通过机器自动建立的各种关系，如挖掘 关联、因果关系、序列模式、事件、基于约束挖掘等。 文献【1 4 】提出一种基于关联规则挖掘的文档分类系统和快速学习算法， 将关联规则从传统的决策支持、市场预测等领域扩展到文档研究领域；文 献【1 5 】将其引入到图像处理中，用于获取图像中的结构信息和统计信息，取 得了不错的效果。 重庆邮电人学硕士论文第一章绪论 1 4 论文工作内容 本文在以上研究背景下实现一种基于特征扩展的中文短文本分类方 法。该方法针对短文本长度短、所描述概念信号弱的问题，主要研究内容 如下：首先以训练数据作为背景语料，首先利用关联规则挖掘算法挖掘训 练集文本中的共现关系，创建特征共现集作为扩展词表。然后用特征共现 集分别对测试文本和训练文本进行特征扩展，两种方法基于相同的特征共 现集，但是扩展方法是不同的。最后是基于特征扩展的中文短文本分类方 法的模拟实验验证。基于测试文本特征扩展和基于训练文本特征扩展工作 流程如下图1 1 和图1 2 所示： 图1 1 基于测试文本特征扩展的短文本分类流程 训练文本 。i 一关联规则j 、一r 一一、 7 ：一一塑一一 测试文本 f 、一t 7 1 预处理 一一一主 j r ，、 训 一上一一一、 ：特征共现集j 预处理 分 练 训练文本! 类 过 特征扩展：1 1r “ 程 i 习羞 特征选择 l 堑堡皇塑一j l 之= 爿 分类器 。i 胜。爿。口i 特征空间 j 7 l；廿不炎刀y ! ：= 二：一 图1 2 基于训练文本特征扩展的短文本分类流程 4 重庆邮电大学硕士论文第一章绪论 测试文本特征扩展指在分类阶段，先根据特征共现集把测试文本中的 特征的共现词作为新特征补充进来，然后再进行分类。 训练文本特征扩展是指在训练阶段，用一种基于共现关系的特征权重 调整方法实现训练文本特征扩展，没有加入新的特征。 1 5 论文组织结构 本文引入特征扩展理论，探讨了关联规则挖掘在文本分类中的应用， 论文的基本组织结构如下： 第一章：绪论。介绍了短文本分类的研究现状，以及本论文的研究背 景和研究工作。 第二章：相关技术基础。从中文文本分类技术基础和关联规则挖掘理 论基础两个方面介绍了文本分类的技术基础，文本预处理、特征选择和分 类模型、以及分类评估指标和关联规则挖掘算法。分类讨论了目前各种算 法的优缺点，指出了当前存在的许多问题，尤其是处理海量短文本数据和 抗噪声干扰方面更有待进一步改进。 第三章：基于测试文本特征扩展的短文本分类研究。介绍了基于测试 文本特征扩展的相关概念，扩展测试文本的分类策略，特征共现集的抽取 过程，扩展算法，通过大量的实验分析比较方法之间的优缺点。 第四章：基于训练文本特征扩展的短文本分类研究。介绍了训练文本 特征扩展的思想，基于共现关系的特征权重调整计算公式，扩展算法，通 过大量的实验分析比较方法之间的优缺点。 第五章：总结和展望。对本论文的主题进行讨论，总结研究的贡献， 并探讨其中的问题、不足与未来的研究方向。 本论文工作得到国家自然科学基金( 6 0 7 0 3 0 1 0 ) 基于特征联想的中文 短文本分类方法研究；重庆市自然科学基金( 2 0 0 6 b b 2 3 7 4 ) ：重庆市教委 科学技术研究项目( k j 0 7 0 5l9 ) ：教育部回国留学人员启动基金( 教外司留 2 0 0 7 1l0 8 号) ；重庆邮电大学科研基金( n o a 2 0 0 6 0 5 ) 的资助。 重庆邮电大学硕士论文 第二章相关理论基础 2 1 引言 第二章相关理论基础 在短文本信息出现之前，人们已经研究过许多文本的分类方法【1 6 】，【l7 1 ， 形成了各种文档自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ，a t c ) 技术。随着 海量短文本信息的涌现，a t c 技术的处理对象从普通长文本文档扩展到短 文本信息，a t c 技术成了实现短文本自动分类的基础。但短文本分类问题 相对长文本分类更加难处理，要考虑更多的因素，这主要是由短文本数据 的特性决定的。短文本数据有效特征少，所描述的概念信号弱、以及类别 模糊度高，采用长文本方式处理短文本显然是不合理的，因此，人们提出 了在短文本分类的过程中必须综合考虑短文本数据信息，挖掘出反映短文 本数据之间依赖或者关联的知识来辅助分类。数据挖掘( d a t am i n i n g ) 中的 关联规则( a s s o c i a t i o nr u l e s ) 挖掘是数据挖掘中最活跃的研究方法之一【1 3 】， 被用来挖掘关联、因果关系、序列模式、事件、基于约束挖掘等，是解决 短文本数据中知识发现的可用途径之一。本章将对现有的中文文本自动分 类的关键技术包括文本特征抽取、特征选择、分类算法等以及经典的关联 规则挖掘算法做一一介绍。 2 2 文本分类相关理论 文本分类就是将用自然语言表示的文本，根据其内容，自动分类到预 先设定的类型集合中，使得一篇文本对应类型集合中的一( 几) 类。文本分 类问题可以形式化定义如下。给定问题： c = c l ， ，d = d l 4 ，彳= 【q j ) 。，【q ，) = o ，1 ) 其中：c = k ，气 为预先设定的类型集合，肌2 为类型数； d = d 一) 为某一领域的所有文本集合，厂为文本总数；么= f q ，1 为脚， 矩阵，( q ，) = o ，1 ) ，表示文本d ，按照其内容是否属于类型q 。假定在文本 与类型之间存在一个未知的映射函数：厂：d c _ o ，l 。 文本分类就是要找一个函数：厂：d cj 0 ，l 尽量逼近未知的真实函 数。在t c 中，函数厂称为一个分类器( c l a s s i f i e r ) 。 6 重庆邮电大学硕士论文第二章相关理论基础 像其他的机器学习一样，t c 一般有训练和分类两个阶段。文本分类 的一般过程如图2 1 所示，首先对训练文本进行预处理，把抽取出来的特 征用特征选择算法进行过滤，得到一个特征空间( 常用的有特征向量空间 v s m ) ，对特征空间用分类算法学习获得一个分类器；预处理测试文本形 成一个测试文本特征空间，把这些文本向量输入到分类器，分类器实现对 测试文本的分类。 2 2 1 预处理 图2 1 文本分类的一般过程 构成文本的词汇，数量是相当大的，我们需要对文档进行预处理： ( 1 ) 禁用词( s t o pw o r d s ) 的去除 这些词在文档中出现的频率非常高，但却没有任何意义。( 如：的、是、 了，英文中的t h e 、i s 、a m 、a r e ) ( 2 ) 词根抽取 从文件或查询中去掉词的前后缀，做这件事是为了把具有同样概念意 义的词( 如w a l k ，w a l k e d ，w a i k e r ，w a l k i n g ) 统一处理。 ( 3 ) ( 中文) 分词、词性标注、短语识别 由于汉语为表意文字，词与词之间无形式符号，所以要对中文文档进 行分词，把句子切分成字、词和短语作为特征项，标注出动词、名词、形 容词和副词。根据实验结果，通常认为选取词作为特征要优于字和短语。 ( 4 ) 词频统计 a ) 词频( t e r mf r e q u e n c y ) 7 重庆邮电大学硕士论文第二章相关理论基础 指某特征项在一篇文档中出现的次数。词频分为绝对词频和相对词 频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一 化的词频，其计算方法主要运用t f i d f 公式，公式如下： 形( f ，d ) = 矿( f ，孑) l 。g ( 盟+ o 0 1 ) ( 2 1 ) 其中，形( r ，孑) 为词f 在文本孑中的权重，而矿( f ，孑) 为词r 在文本孑中 的词频，为训练文本的总数，为训练文本集中出现，的文本数，分母 为归一化因子。 根据t f i d f 公式，文档集中包含某一词条的文档越多，说明它区分 文档类别属性的能力越低，其权值越小；另一方面，某一文档中某一词条 出现的频率越高，说明它区分文档内容属性的能力越强，其权值越大。 b ) 文档频率( d o c u m e n tf r e q u e n c y ) 所有文档集合中出现某特征的文档数目。 ( 5 ) 去除区分度较小的噪音特征项可以提高分类准确率，去除重要性 较低的低频特征项可以加快运行速度。 2 2 2 特征选择 基于机器学习的自动文本分类问题，本质上是一个统计模式识别问题 【i9 1 。在运用统计模式识别方法进行文本分类之前，需要将文本表示成特征 向量。无论采用什么样的文本表示模型，中等规模文本分类问题( 如 r e u t e r s 2 1 5 7 8 ) 所对应的文本特征空间通常都高达几万维、甚至十几万维， 其维数远远超出用于分类器训练的文本文档的个数，带来两个棘手的问 题：一是很多在低维空间具有良好性能的统计分类算法在计算上变得不可 行；二是在训练样本容量( 训练文本的个数) 一定的前提下，过多的特征使 得样本统计特性的估计变得非常困难，因此必须进行维数削减。 维数削减的根本任务就是将分散在各个原始特征中的有关模式类别 的统计信息有效地集中起来，以达到提高统计分类器的识别能力和降低分 类器训练和分类工作量的目的。维数削减的基本途径是特征选择 ( f e a t u r e s e l e e t i o n ) 。 文本特征选择就是从特征集丁= ，l ，f 。) 中选择一个真子集 丁= ，1 ，f ，) ( s “s ) 。其中：s 为原始特征集的大小，s 为选择后的特征集 8 重庆邮电大学硕士论文第二章相关理论基础 大小。选择的依据是特征对分类作用的大小，通常用一个统计量来度量。 常用的方法有互信息( m u t u a li n f o r m a t i o n ，简记为m 1 ) 、z 2 统计量 ( c h i - s q u a r es t a t i s t i c ，简记为c h i ) 以及文挡频率( d o e u m e n t f r e q u e n e y ，简 记为d f ) 等。下面我们将对其简要介绍。 ( 1 ) 互信息( m u t u a l i n f o r m a t i o n ，简记为m i ) 互信息可以度量特征项和类别的共现关系，特征项对于类别的互信息 越大，它们之间的共现概率也越大。假设文档集合分为k 类，记为 c l ，c 2 ，e ，特征项w 对于文档类别q 的互信息由下式进行计算： m ( w ，q ) _ l o g 等掣 ( 2 2 ) 其中尸( w ，q ) 为特征项出现在q 类中的概率，尸( w ，c ) 为特征项在所有文 档中的出现频率。 平均互信息公式： m ( w ) = 善俐。g 等 ( 2 3 ) 尸( q ) 表示第f 类文本在训练文本集合中出现的概率，尸( w ) 表示词w 在 训练文本集合中出现的概率，尸( 鸭c ) 表示在第f 类文本中w 的出现概率。 特征w 与类别c 的互信息越大，词和类的共现程度越大。 互信息的缺点是倾向于选择稀有单词。然而对于文本分类而言，出现 次数较多的单词比出现次数较少的单词往往具有更大的作用。 ( 2 ) c h i - s q u a r e 统计量( c h i ) c h i 统计量( c h i s q u a r es t a t i s t i c ，简记为c h i ) 的概念来自列联表检验 ( c o n t i n g e n e yt a b i et e s t ) ，它可以用来衡量特征w 和类别c 之间的统计相关 性。在文本分类中，特征w 。的c h i 权重如公式所示。 ；c 惭，= 业嚣蒜等铲 亿4 ， 其中：为训练集的大小，尸( ，白) 为训练集中不出现特征并且不 属于类型c 的文本数除以，尸( ，c ，) 为训练集中出现特征并且不属于 类型q 的文本数除以，尸( ，g ) 为训练集中不出现特征并且属于类型q 的文本数除以。 当特征w 与q 类别相互独立时，c l l i ( m ，q ) = 0 ，此时特征w 不包含任何 与类别相关的鉴别信息。特征w 与类别c f 的统计相关性越强，c m ( ，c f ) 的 值就越大，此时特征w 包含的与类别q 有关的鉴别信息就越多。 ( 3 ) 相关系数( c o r r e l a t i o nc o e m c i e n t ，c c ) 9 重庆邮电大学硕士论文第二章相关理论基础 n ge ta 1 【2 0 】指出，在公式2 4 ( c h i 统计量) 中，分子取平方使得特征与 类型的正相关能力与负相关能力被同等对待，但是对于分类来说，特征的 重要性主要由特征与类型的正相关能力决定。基于这一观察，提出了特征 的“相关系数 ，如下公式所示： c c ( ，q ) ：型尘丝丝丝尘竺丝鳖墼型( 2 5 ) 助( m ) 助( q ) 胁( ) 儿( c f ) 参数说明与公式( c h i 统计量) 一致。c c 的平方就是c h i ，c c 只在小 特征集上对c h i 有微弱的改善。 ( 4 ) 文档频率( d o c u m e n tf r e q u e n c y ，d f ) d f k 指训练集中出现特征w k 的文本数。它认为特征在越多的文本中 出现，分类作用越大。采用d f k 方法对大量的低频特征进行降维是很有效 的，但是对于高频特征没有作用。y a n g 和p e d e r s e n 【2 1 1 的实验表明在不损失 有效性的情况下，通过d f 可能使特征空间维度缩减到原来的十分之一。 通常认为d f 太小的词没有代表性，而d f 太大的词又没有区分度， 所以基于d f 的特征选择方法只留下那些d f 介于中间的词作为特征。 ( 5 ) 信息增益( i n f o r m a t i o ng a i n ，i g ) 在文本分类中特征t 的信息增益如下面公式所示： 且 弼o ) = 一p ( c 川o g 尸( q ) i c f 矧i c l ( 2 6 ) i r ii r l 、7 + 尸( f ) 芝p ( ql ，) l o 妒( ql ，) + 尸( ；) 艺尸( qi ；) l o 酽( ql ；) 佑( f ) 反映了该词为整个分类所提供的信息量。 上式中，p ( ，) 表示词芒不出现的概率，尸( ql f ) 表示词，出现的情况下 文本属于q 类的概率，尸( qi ，) 表示词不出现的情况下文本属于q 类的概率。 它表示特征在文本中出现或不出现为确定文本的类型所提供信息量 的大小。i g 有利于高频特征。 ( 6 ) 期望交叉熵( e x p e c t e dc r o s se n t r o p h y ) 期望交叉熵又称相对熵，也称k l 距离。它考虑了文档集合的信息熵和 文档中词语的条件熵之间信息量的增益关系，并以此来确定该词语在文本 分类中所能提供的信息量。期望交叉熵的公式为： ( w 却( w ) 军讹。g 等 ( 2 7 ) 其中p ( w ) 为特征w 出现的概率，尸( q1w ) 为类别q 在特征w 出现的情况 1 0 重庆邮电大学硕士论文第二章相关理论基础 下的概率，p ( q ) 为类别q 的出现概率。 2 2 3 分类模型 文本分类方法很多，大多来自于模式分类，基本上可分为三类：一类 是词匹配法，它根据文本和类别中共同出现的词决定文本属于哪些类；一 类是基于知识工程的方法，它需要知识工程师手工地编制大量的推理规 则，且分类质量严重依赖于推理规则的质量，在实际的分类系统中较少使 用；一类是基于统计的方法，其基本思路是先搜集一些与待分类文本同处 一个领域的文档作为训练集，并由专家进行人工分类，保证分类的准确性， 然后分析这些已经分好类的文本。从中挖掘关键词和类之间的联系，最后 再利用这些学到的知识对文本分类。 其中，基于统计的方法具有较好的理论基础、简单的实现机制，以及 较好的文档分类质量等优点，目前实用的分类系统基本上都是采用这种分 类。其中的支持向量机算法、k 近邻法和朴素贝叶斯算法【2 2 】，【2 3 】，【2 4 1 由于分 类效果比较好成为研究的热点。由于各种分类算法不能一一介绍，本文将 选择这些有代表性的常用算法简要介绍。 ( 1 ) k 近邻法( kn e a r e s tn e i 曲b o r ，简记为k n n ) k 近邻算法思想很简单：给定一篇待识别的文章，系统在训练集中找 到最近的k 个最近邻，看这k 个最近邻中多数属于哪一类，就把待识别的文 章归为哪一类。k 一最近邻法的决策规则可以通过以下公式表示： y ( x ，巳) = s 拥( x ，珥沙( 谚，巳) 一i ( 2 8 ) 其中，x 为一篇待分类网页的向量表示；4 为训练集中的一篇实例网 页的向量表示；q 为一类别；y ( d ，q ) o ，1 ) ，( 当z 属于q 时取1 ，否则取o ) ； 6 ，为预先计算得到的q 的最优截尾阈值，各个分类的阈值6 ，则是通过训 练集合的交叉检验得到，s i m ( x ，d ，) 为待分类文本与文本实例之间的相似度， 由文本间的余弦相似度计算公式得到： 一， s 砌( x ，乃) = c o s ( x ，d ) = 尚 ( 2 9 ) 刚口，l 有以上可以看出，k n n 算法本身简单有效。 ( 2 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 支持向量机【2 5 1 是一类基于v a p n i k 的统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ，s l t ) 和w o l f e 对偶规划理论的分类和函数估计方法。 重庆邮电大学硕士论文第二章相关理论基础 其基本思想是：根据结构风险最小化的原理，对一个给定的具有有限 数量训练样本的学习任务，如何在高维空问中寻找一个最佳超平面作为两 类的分割，以保证最小的误差率。支持向量机在解决小样本、非线性及高 维模式识别问题上表现出许多特有的优势，并在很多领域得到成功的应 用。在文本分类方面s v m 表现也不错，其分类的准确率和召回率超过了现 有的大部分方法1 2 6 1 。 对于文本分类中的两分类问题，给定一组训练样本： ( x l ，y 1 ) ，( x ，y ，) ，( x 材，y 肼) ，x f r ”，j ， 一l ，+ l 其中而为文本d f 的特征向量( 1 f n ) ，只= l 表示文本也属于第一种类 型，弘= 一