（计算机应用技术专业论文）基于统计方法的网页内容分类技术研究.pdf

独创性声明 声明所呈交的论文是我个人在导师指导下( 或我个人) 进行的研究 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 包含其他人已经发表或撰写过的研究成果，也不包含为获得西南科技大 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 何贡献均已在论文中作了明确的说明并表示了谢意。 签名：趁3 钙日期： p ，u 6 7 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：砂岛 翩签名：瓤日期：砂二7 西南科技大学硕士研究生学位论文第1 页 摘要 由于通信及网络技术的发展，网络数据呈现海量特征。如何从浩如烟海 的信息数据中找到自己需要的信息，是目前亟待解决的一大问题。网页自动 分类技术可以使信息组织更加条理，富有层次性，有助于人们信息的获取。 本文研究了网页内容分类中的相关技术，具体包括： ( 1 )基于相似度的网页正文获取算法。传统网页正文获取需要经过分 块和正文定位两个步骤，由于网页结构复杂多样，使得分块过程较为复杂而 且正文定位困难。本文主要研究无需分块的网页正文提取，提出了基于相似 度的网页正文提取算法。首先提取出最大文本行，然后根据文本内容相似度 和标签相似度来提取网页正文内容，略过了传统的分块步骤。 ( 2 )改进的特征选择算法。由于经典的卡方统计在选择特征时偏向于 低频度特征，本文在研究了卡方统计算法之后，提出了基于词频扩散的卡方 统计降维算法，利用特征的文档频率和词频结合的方式来代替传统的卡方统 计公式中的文档频率。 ( 3 )网页分类实验平台的搭建。网页分类实验平台主要包括两个模 块：特征选择和分类。本文对常见的特征选择算法做了大量实验，并初步验 证了分类算法的性能。 相关实验表明，根据相似度来提取网页正文的精度在9 5 以上，利用余 弦距离计算的正文内容能够增加网页内容在主题上的凝聚性，有益于网页的 分类。改进的特征选择算法在低维度空间相对于原算法在分类精度上提升大 概1 5 ，达到了降维的目的。 关键词：网页分类网页正文获取特征选择词频扩散 c o n v e n i e n t l y t h i sp a p e rd i s c u s s e sr e l a t e dt e c h n o l o g i e so ft h ew e bp a g e sc l a s s i f i c a t i o n ， s p e c i f i c a l l yi n c l u d i n g ： ( 1 ) t h et e c h n o l o g y o fe x t r a c t i n gc o n t e n to fw e bp a g eb a s e do n s i m i l a r i t y t h et r a d i t i o n a lm e t h o d sn e e das t e pc a l l e db l o c k i n gt ob l o c kw e b p a g e ，a n dt h e np o s i t i o n i n gt h ec o n t e n t t h i sa p p r o a c ha v o i d sa t r a d i t i o n a ls t e po f b l o c k i n gw h e nd e a l i n gw i t hw e bp a g e s i tf i r s te x t r a c t st h el a r g e s t t e x tl i n ea n d c o m p u t e st h es i m i l a r i t yo fl i n et e x ta n dl i n et a g sb e t w e e ne a c hl i n e ，t h e n ，u s e s t e x ts i m i l a r i t ya n dt a gs i m i l a r i t yt oe x t r a c tw e bp a g ec o n t e n t ( 2 1a ni m p r o v e dm e t h o do ff e a t u r es e l e c t i o n a st h ec l a s s i cc h i s q u a r e a l g o r i t h mt e n d st oc o l l e c t sl o wf r e q u e n c yf e a t u r e sw h e ns e l e c t i n gf e a t u r e s ，a f t e r s t u d y i n gt h i sm e t h o d ，t h i sp a p e rp r o p o s e da ni m p r o v e da l g o r i t h mc a l l t e r m f r e q u e n c yd i f f u s i o n ( t f d ) ，w h i c hu s e st e r mf r e q u e n c y ( t f ) i nad o c u m e n t c o m b i n e dw i t hd o c u m e n tf r e q u e n c y ( d f ) i n s t e a do fd ft oi m p r o v et h e p e r f o r m a n c eo fc l a s s i c a lc h i - s q u a r ea l g o r i t h m ( 3 ) a ne x p e r i m e n t a lp l a t f o r mf o rw e bp a g ec l a s s i f i c a t i o n i tc o n t a i n e d t w om o d e l s ：f e a t u r es e l e c t i o nm e t h o d sa n dc l a s s i f ym e t h o d s t h i sp a p e rd i dal o t o fw o r kt ot e s tt h ep e r f o r m a n c eo f e a c hc o m m o nf e a t u r es e l e c t i o nm e t h o d s ，a n d d i ds o m ep r e l i m i n a r ye x p e r i m e n t sf o rc l a s s i f ya l g o r i t h m s r e l e v a n te x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tw e bp a g ec o n t e n te x t r a c t i o n b a s e do ns i m i l a r i t yc a nr e a c hah i g ha c c u r a c yo f9 5 e x t r a c tt h eb o d yo ft h e p a g eb a s e do ns i m i l a r i t yc a n i n c r e a s et h ec o h e s i o no ft h es u b j e c to fw e bp a g e s c o n t e n t ，w h i c hi su s e f u lf o rw e bp a g ec l a s s i f i c a t i o n i m p r o v e df e a t u r es e l e c t i o n a l g o r i t h mc a nm e e tab e t t e rc l a s s i f i c a t i o nr e s u l ti nl o w - d i m e n s i o n a ls p a c e ( b r i n g 15 a b o v et h a na d d i t i o n a lm e t h o d ) ，a c c o r d i n gw i t ht h ed e m a n d so ff e a t u r e s e l e c t i o na l g o r i t h m k e y w o r d s ：w e bp a g ec l a s s i f i c a t i o n ；w e bp a g ec o n t e n te x t r a c t i o n ；f e a t u r e s e l e c t i o n ；t e r mf r e q u e n c yd i f f u s i o n 南科技大学硕士研究生学位论文第页 目录 1 1 意义1 ： ： 1 3 2 文本分类4 1 4 论文的研究内容与结构4 1 4 1 论文的研究内容4 1 4 2论文的结构5 2文本分类相关技术简介6 2 1 语料库6 2 1 1r e u t e r s 一2 1 5 7 8 6 2 1 2 t a n c o r p 7 2 1 3 s o u g o u c 7 2 2 文本预处理7 2 2 1 分词技术7 2 2 2向量空间模型( v s m ) 8 2 3 文本降维技术8 2 3 1 特征选择9 2 3 2 特征提取1 2 2 4 文本分类算法1 2 2 4 1 中心法1 2 2 4 2k 近邻1 3 2 4 3朴素贝叶斯13 2 4 4支持向量机1 4 2 4 5分类委员会1 4 2 4 6 回归模型15 2 5 文本分类评价方法1 5 2 5 1 准确率、查全率和f 1 值1 5 2 6 本章小结1 6 3基于相似度的网页正文提取算法研究1 7 西南科技大学硕士研究生学位论文第v 页 3 1 基于相似度的中文网页正文提取算法1 7 3 1 1网页规范化1 9 3 1 2 正文提取算法1 9 3 1 3 算法复杂度分析2 0 3 2 实验与结果2 2 3 2 1数据集选取2 2 3 3 实验结果2 2 3 4 本章总结2 3 4改进的卡方统计算法2 5 4 1 卡方统计降维算法模型2 6 4 2 改进的卡方统计算法2 6 4 2 1经典卡方统计的不足2 7 4 2 2基于t f d 的卡方统计降维方法2 8 4 3 实验设计2 9 4 3 1数据集选择2 9 4 3 2 分类算法选取2 9 4 3 3 评价方法2 9 4 3 4 实验结果3 0 4 4 本章小结3 3 5 网页分类实验平台的设计与实现3 4 5 1 系统功能结构设计3 4 5 。1 1网页分类系统处理流程3 4 5 1 2系统功能结构设计3 5 5 2 实验结果及性能评价3 6 5 2 1数据集选择3 6 5 2 2实验环境说明3 6 5 3 实验结果分析3 6 5 3 1r e u t e r s 实验数据3 6 5 3 2 s o g o u 数据集3 9 5 3 2 t a n c o r p 数据集4 2 5 4 本章总结4 5 6结论及展望4 6 6 1 总结4 6 西南科技大学硕士研究生学位论文第v i 页 6 2 进一步工作展望4 7 致谢j 4 9 参考文献5 0 攻读硕士学位期间发表的论文及科研成果5 4 西南科技大学硕士研究生学位论文第1 页 1 绪论 1 1 课题来源 论文的研究工作来源于国家8 6 3 计划项目“多层网络数据语义分类与理 解技术研究”( 2 0 0 7 a a 0 1 2 1 5 1 ) 。 “多层网络数据语义分类与理解技术研究 项目包括对网络多层数据语 义描述架构的研究，对网络数据的分层语义抽取技术和分层分类技术的研 究，对网络数据跨层语义集成与理解技术的研究，对网络数据不同层语义相 关性度量方法的研究和对基于分层语义抽取技术和跨层语义集成技术的应 用研究。旨在建立全息的网络数据映像( 扩展的统一内容定位符，e x t e n d u n i f o r mc o n t e n tl o c a t o r ，e x u c l ) 来提高信息获取的效率和对网络信息内 容的理解。 本课题以该项目为背景展开理论和实验研究，重点研究应用层上的数据 内容按主题分类( 网页分类) 的技术。 1 2课题研究背景及意义 由于互联网的迅猛发展，使得大量的、庞杂的文字信息，以计算机可读 的形式出现在各式各样的载体上，互联网已经成为人们学习、工作和生活必 不可少的资源宝库。网络信息资源的激增以及信息内容的复杂，使得人们无 法很有效地利用如此庞大的信息，人们面临着日益严重的信息挑战。 2 0 0 5 年雅虎公布其可搜索网页数量达到1 9 2 亿，2 0 0 8 年g o o g l e 宣布 其索引的网页数量达到了一万亿，反映出如今浩如烟海的庞大信息量。另一 方面，2 0 0 6 年c n n 报道全球网站数量突破1 亿，由于网站架构技术，网站 设计语言的多种多样，使得这些网站的信息组织没有统一的结构，信息冗余 度大，严重影响信息的有效获取。从浩如烟海的网络资源中，便捷、高效地 获取所需的信息，是信息处理领域的重要目标之一，也成为现代信息技术的 研究热点。网页分类技术就是在各种信息量异常庞大、信息载体纷繁复杂的 形势下，对信息进行管理的一项重要技术。网页分类能够根据需求自动对网 页进行分门别类，从而更好地帮助人们把握文档信息，挖掘文档信息，提高 信息服务的质量。 研究网页分类技术有非常重要的意义。首先，互联网是一个巨大的信息 西南科技大学硕士研究生学位论文第2 页 与知识储存库，是一个庞大而混沌的网络，信息发布者的言论自由和快速、 无序的信息增长对于信息的使用者来说却意味着混乱的开始，对于用户来 讲，从数以亿计的网页中准确找到所需要的信息，几乎是一个困难乃至于不 可能完成的任务，这就造成了“数据丰富，知识贫乏”的现象广泛存在。将 网页划分到不同类别，将信息组织条理化，层次化，能够大大提高用户检索 信息的效率。 其次，对于网络而言，网页分类大大降低了用户检索信息的结果的冗余 度。从传输的角度来讲，就是大大降低了数据传输占用的带宽，能够有效的 避免网络的堵塞，提高网络的利用率。 1 3 研究现状 1 3 1特征表示 网页分类的方法根据其选取特征的不同，可大致分为三类：超文本特 征，链接特征和邻近类特征。超文本方法选取页面内文本特征和上下文( 锚 文本) 特征。锚文本实际上就是链接文本比引。s h e n h 3 应用这些特征通过摘 要来提取网页主题，然后进行分类。在s h e n 的方法中，首先选择文本内容 和上下文作为特征，然后结合四种主要的网页摘要算法作为分类用的摘要算 法( l u h n 的摘要生成技术，潜在语义索引，把b o d y 主题内容作为摘要，有 指导的学习方法) 。对于网页的每个句子，采用四种方法计算重要度分数， 然后赋权相加作为最后的分数。s h e n 在其实验中发现，任意一种摘要算法 都能提高分类精度，在进一步的实验中，s h e n 认为大的网页会出现有用信 息丢失的现象，而摘要能够提取这些有用的信息，这就是摘要算法提高分类 精度的原因。由于这些摘要算法在提取正确摘要的同时都产生了一些噪声即 不重要的句子，因此采用了一个加权组合的方式，实验证明，这种线性组合 能很好的去掉噪声。达到与人工摘要相媲美的精度( 提升1 2 0 v s1 3 2 ) 。 后，s h e n 哺1 等人又加入了一种摘要算法( 图分析方法) 而去掉了锚文本的特 征，实验结果表明其方法效果很好。 为进一步提高分类精度，很多学者开始对超链接进行研究。f i s h e r 嘲在 利用概率l s i ( 潜在语义索引) 和概率h i t s ( 基于超文本主题选择) 方法进 行大量的文本分类实验之后得出，只有在文档中的超链接数量达到一定数 目，以及链接质量很高( 很重要) 时，链接信息才能提升分类精度。在估计 链接密度时，f i s h e r 等采用有向图模型来表示文档及其链接( 定点表示文 西南科技大学硕士研究生学位论文第3 页 档，有向边表示链接) ，用边数除以定点得到链接密度。s h e n 口1 在其研究中 发现在以往的链接分类中都只利用了文档之间的超链接，于是提出了利用新 的资源一查询日志来获取另一种重要链接一隐藏链接来提高网页分类性能， 基于查询日志，提出了隐藏链接这一概念。通过a t ( 锚文本) 和e a t ( 扩展 锚文本) 之间的隐藏链接来提取a s ( 链接句子) ，并用此来定义虚拟文档。 将此虚拟文档加入“通过链接近邻 分类方法中，大大提高了分类正确率。 邻近类方法与链接分析密切相关，因为邻近类方法的思想就是通过邻近 网页的类别来判断待处理网页类别，而邻近网页需要链接分析才能得出。 由于网页分类的特征与纯文本分类时不同，有更多的额外信息可以参 考，所以近年来提出了很多扩展的特征选择方法，即考虑利用文本内容之外 的信息来帮助提高分类精度。c h e n 眵3 提出了一种降维算法f f s s ( f a i r f e a t u r e s u b s e ts e l e c t i o n ) 。f f s s 不仅同时考虑类内和类间的关键字有用 度，同时也考虑对待每个类的公平程度，先用k f 和d f 得到类中关键字表示 类作用的局部得分，然后用一个标准化过程将局部得分转化为全局的标志， 以便于类间的比较，最后应用 q = 杰 m a x 冬一1 | l s 多一s 细】对关键字进行全 k = 1 j 一1 局评分以得到最终值，便于进行特征选择。c h e n 凹3 提出了两种进行特征选择 时的特征相关度估计方法：基于f u z z yr a n k i n ga n a l y s i s 的二步提升和判 别能力估计。二步提升包括两个步骤：i n t r a - 1 e v e lp r o m o t i o n 和 i n t e r l e v e lp r o m o t i o n 。将非单调相关度估计转换为单调估计( 便于对特 征的相关度值进行排序，便于选取相关度特征) ，然后对余下的估计进行聚 合( 由1 得到一个特征相关度与决策之间的矩阵，对矩阵进行聚合，得到每 个特征总的相关度) 。当相关度测量信息不足时，二步提升收到限制，于是 提出了判别能力估计( 选择那些能最大程度区分类别的特征) 。也分两步，l 、 根据文档频率计算每个特征对每个类的差分，2 、对每个特征的差分求和。 c h a u n 在页面内容和标题特征基础上，加入了相邻页面的内容特征( 父页面， 子页面，兄弟页面的标题和词项特征，) 和链接特征( h i t s 算法得到的h u b 中心性网页系数和a u t h o r i t y 一权威性网页系数，p a g e r a n k 系数，父页面， 子页面和兄弟页面的个数) 。p o b l e t e n 妇利用查询代替真实文档内容来表示文 本一查询文档模型。f e r s i n i n 2 1 提出一种基于t f i d f 的特征加权方法，基于 如下假设：图像是吸引用户的重要因素。提出反特征重要度矩阵，将图像因 素考虑进去。提出图像加权特征频率( i w t f ) ，先计算每个文本特征对于图 根据文档和类别中共同出现的词项来决定文献的类别。8 0 年代后期，知识 工程方法成为研究的热门领域。9 0 年代以后，机器学习在文本自动分类中 的应用研究受到越来越多的关注。上世纪末本世纪初，随着世界范围内数字 图书馆研究的兴起，特别是2 0 世纪9 0 年代末互联网的迅速普及和发展，出 现了大量的需要进行分类的语料，使得文本自动分类技术得到了迅猛的发 展，逐渐由可行性研究转向实用化研究阶段。这个阶段出现了大量的基于统 计和机器学习技术的分类方法。 随着w e b 信息的迅速增加，面向w e b 的以网页作为语料库的自动分类研 究已经成为新的研究热点。目前，一些常用的比较成熟的文本分类算法己经 被应用到了w e b 自动文本分类中，主要包括三大类：一类是基于t f i d f 的分 类算法，主要利用t f i d f 权值公式计算指定词项在文档中的重要性，然后用 余弦距离或欧式距离公式计算两个文档的相似度，这类算法包括r o c c h i o 算 法，t f i d f 算法，c e n t r o i d 算法，k 近邻算法( k - n e a r e s tn e i g h b o r s ，k n n ) 等；另一类是基于概率统计和信息论的分类算法，如朴素贝叶斯算法( n a i v e b a y e s ，n b ) ，最大熵算法( m a x i m u me n t r o p y ) 等；第三类是基于机器学习 的分类算法，如决策树( d e c i s i o r lt r e e ) ，人工神经网络( a r t i f i c i a ln e u r a l n e t w o r k s ，a n n ) ，支持向量机( s u p p o r tv e c t o rm a c h i n e 。s v m ) 。 1 4 论文的研究内容与结构 1 4 1 论文的研究内容 本文以8 6 3 计划项目“多层网络数据语义分类与理解技术研究 为背景， 研究网页分类过程中的相关技术，主要包括以下三个部分： ( 1 ) 研究网页分类过程中预处理技术，提出了基于相似度的中文新闻网 页正文提取算法。 ( 2 ) 研究文本分类中的特征选择算法，改进了卡方统计算法，这是本文 的重点。 ( 3 ) 全面了解了网页分类的相关技术，重点了解了当前主流的特征选择 西南科技大学硕士研究生学位论文第5 页 算法和分类算法，设计并实现了网页分类实验平台。 1 4 2 论文的结构 第一章介绍了论文的课题来源、背景及研究内容与论文章节安排。 第二章详细介绍了文本分类中的各个步骤以及每个步骤当中的主流算 法。 第三章主要研究了网页正文提取的方法，并针对其特点，提出了基于相 似度的网页正文提取算法，结合实验结果证明了算法的有效性。 第四章是本文重点，着重研究了卡方统计降维算法，并提出了基于词频 扩散的方法来改进卡方统计。 第五章介绍网页分类实验平台的设计方案和实现机制，最后给出相关的 实验结果。 结论是对论文工作的一个总结，并讨论了进一步的研究工作。 西南科技大学硕士研究生学位论文第6 页 2 文本分类相关技术简介 + 文本分类技术最早可追溯到2 0 世纪5 0 年代。h p l u h n 在这个领域进 行了开创性的研究，提出了基于词频统计的自动文本分类方法。1 9 6 0 年， m a r o n 发表了关于自动分类算法的第一篇论文。1 9 7 5 年，s a l t o n 等人在其 论文中提出了一个新的文本分类计算模型( v e c t o rs p a c em o d e l ，v s m ) ，成 为文本自动分类领域最通用的计算模型。此后，在人工智能、信息检索和机 器学习推动下，在文本信息智能处理的巨大需求的牵引下，自动文本分类技 术的研究引起了人们越来越多的关注与重视，并在诸多领域取得了初步的应 用成果。 文本分类的任务是将文档根据内容划分到预定义好的类别当中。文本分 类包括五个方面：语料库选择、文本预处理、降维、分类和评估。 2 1 语料库 自动文本分类算法都包括学习与预测两个部分：即先利用已有的知识， 根据不同的算法训练出文本分类模型，然后利用分类模型去预测待分类文档 的所属类别，最后根据待分类文档的真实类别来评估分类模型的精度。这个 已有的知识和待分类文档的真实类别，便来自于语料库。实际使用中，语料 库一般分为两个部分：训练集和测试集。训练集训练文本分类模型，测试集 评估分类模型的优劣程度。语料库的出现，为自动文本分类提供了统一的评 测标准，国外已经出现了许多标准的文本分类语料库，如r e u t e r s - 2 1 5 7 8 ， 2 0 n e w s g r o u p ，w e b k b 等，而中文预料库因为起步较晚，大多是个人从网站 下载的一批网页做的测试，所以语料库不是很标准，但也出现了一批优秀的 中文语料库。如：t a n c o r p ，s o u g o u c 等。 2 1 1r e u t e rs - 2 15 7 8 r e u t e r s 一2 1 5 7 8 是由卡内基集团收集和手动标注的路透社在1 9 8 7 年间 发表的新闻稿件，发布于2 0 0 4 年。前一版本为r e u s t e r s 一2 2 1 7 3 ，发布于1 9 9 4 年。该语料库解压后2 2 8 m ，有2 2 个数据文件，共2 1 5 7 8 篇文稿，分属于 1 3 5 个类别。其中有的文稿属于多个类别，有的文稿只有标题没有内容，每 个类别的文档数量也不相同。所以，该语料库是一个多标签，非均衡的文本 分类语料库。 西南科技大学硕士研究生学位论文第7 页 在本文实验中，我们筛选了语料库中的5 9 个类别中主题真实存在的共 8 3 9 9 篇文档，其中6 0 5 6 篇文档作为训练集，测试集共2 3 4 3 篇。 2 1 2t a n c o rp t a n c o r p 是谭松波老师及其同事手动收集的中文文本分类语料库。共计 1 2 个大类：财经、地域、电脑、科技、房产、体育、汽车、人才、卫生、 娱乐、艺术。每个大类又分为若干小类，共计6 0 个，总共包含1 4 5 1 0 篇新 闻文档。是一个单标签多层次的非均衡语料库。由于该语料库信息完整，在 本文的实验中，我们未对该语料库裁剪。 2 1 3 s o u g o u c s o u g o u c 语料库是搜狗实验室搜集的新闻文本，共1 0 个类别，每个类别 8 0 0 0 篇文本，共计8 0 0 0 0 个新闻文档。在本文实验中，我们提取了每个类 别中的6 0 0 篇文档，共6 0 0 0 篇作为我们的语料库。 2 2 文本预处理 计算机并不具备人的智能，文本分类器无法直接处理文本文档，因此， 想让计算机能够自动的区分文本，文本分类的首要任务就是将文本文档表示 为分类模型可以识别和处理的形式。文本预处理的任务就是采用自动分词技 术，对文本进行切分词处理，去掉无意义的词项比如虚词等，然后抽取文本 中的词汇作为其特征项。将最终获得的特征项，及其统计频率，用文档模型 进行表示，具有代表性的模型有布尔模型( b o o l e a nm o d e l ) 、向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 等。 2 2 1分词技术 中文分词就是将连续的中文汉字按照汉语规范重新组合成词或词组序 列的过程。中文分词是进行信息检索、汉字智能输入、机器翻译、文本发现 等的必要组成部分。中文的词与词之间没有像英文一样中间有明显的空格， 而且汉语的句子构成复杂多变，使得中文分词一直成为中文信息处理的难 点。 现有的中文分词算法可分为三大类：基于字符串匹配的分词方法、基于 统计的分词方法和基于理解的分词方法。 第8 页 t f i d f ( t e r mf r e q u e n c y i n v e r s ed o c u m e n tf r e q u e n c y ) 是一种用于 信息检索与文本挖掘的常用特征加权技术。在t f - i d f 公示中，t f 是特征项 在文本中出现的次数，而i d f 表示在文本集合中该特征出现的文本个数。公 式如下： 矿：j 一 ( 2 1 ) 。7 ， 克刀庇， 上式中， 吩，j 是该词在文件勺中的出现次数，而分母则是在文件 勺中所有字词的出现次数之和。 得 域= l o g ( 2 2 ) 其中， i d l ： 语料库中的文档总数 i d ：勺d ) l ： 包含词语f ，的文档数目( 即 ，o 的文档数目) ，综合可 缉d 3 t ? j 2 舒o i 呱 ( 2 3 ) 2 3 文本降维技术 文本经过分词映射到向量空间之后，由于语料库的容量以及词项数目的 西南科技大学硕士研究生学位论文第9 页 巨大，导致了一个文本分类时普遍遇到的一个主要问题，即维数灾难。所以， 降维是文本分类中的重要步骤。从目前的研究看，特征降维分为两个方向： 特征选择和特征提取。 2 3 1 特征选择 特征选择是指从原有的特征集合中选择一个子集作为新的特征，这个子 集完全属于原始特征集合。这种特征选择方法一般通过阈值来选取有用的特 征。y a n g n 铂对之前出现的5 种主流特征选择方法( 文档频率( d f ) ，信息增益 ( i g ) ，卡方统计( c h i ) ，互信息( m i ) 和特征权重( t s ) ) 进行了对比研究， 在其文章中，y a n g 指出i g 和c h i 表现相当，在去除9 8 的特征的情况下仍 能保持其精度。此后不久，m o n i c a n 5 1 等人又对这些特征选择算法的组合做了 详细的实验分析，发现i g 组合c s 的算法能取得最好的降维结果。 2 3 1 1 文档频率 文档频率( d o c u m e n tf r e q u e n c y ，d f ) 是出现该特征的文档数。通过d f 进行特征选择就是将特征按照文档频率大小排序，然后按一定比例选择某一 部分文档频率大的特征，达到减少特征数量的目的。d f 是最简单的降维技 术之一，它能够在近似线性时间内显著的降低大训练集的计算复杂度。所以， d f 经常是用来提高分类效率而不是提高分类精度。d f 也有缺点，因为文档 频率小的单词可能在某一类文本中包含着重要的标志信息，在此情况下，d f 将会降低分类精度。 文档频率不需要依赖类信息，所以是一种无监督的特征选择，常被集成 在文本预处理中用来删除出现次数过少或者出现次数过多的单词以提高后 续处理的效率。 2 3 1 2信息增益 信息增益( i n f o r m a t i o ng a i n ，i g ) 在机器学习领域中常作为衡量一个特 征好坏的标准。重要性的衡量标准就是看特征能够为分类系统带来多少信 息，带来的信息越多，该特征越重要。定义如公式( 2 4 ) ： 西南科技大学硕士研究生学位论文第l o 页 i g ( t ) 一，) 崦) + i = 1 黝l d 崦i d + z2 1 嗣i - ) 魄i _ ) i = 1 ( 2 4 ) 其中，尸( 乃是词项芒不在文本集合中出现的概率，p ( 气i ，) 表示词f 出现 的情况下文本属于c ，类的概率，p ( c ：i _ ) 表示词芒不出现的情况下文本属于 c ，类的概率。 利用i g 进行特征选择，首先计算训练集中所有特征的i g ，然后移除那 些小于预先设定的阈值的特征。计算包括两个部分：指定特征下某类别的条 件概率估计和熵的计算。整的时间复杂度为0 ( v m ) ，其中v 是词库容量，m 是类别数目。， 2 3 1 3 互信息 互信息( m u t u a li n f o r m a t i o n ，i i ) 的定义如公式( 2 - 5 ) ： 瓣f i 骅c i ) l o g 等 ( 2 - 5 ) 似d 2 f 三1 以勺昔 q 。5 ) p ( c ：) 表示第j 类文本在训练文本集合中出现的概率，p ( f ) 表示词t 在训 练文本集合中出现的概率，尸( ，i c ：) 表示在第j 类的文本中芒的出现概率。i i 越大，词和类的共现程度越大。 近似计算公式如( 2 - 6 ) ： ，o ，c ) = l o g 面石a 丽x n ( 2 6 ) 其中：a 为特征t 与文档c ，类同时出现的次数；b 为特征t 出现而c ，类 文档不出现的次数；c 为c ，类文档出现而特征芒不出现的次数；n 为文档总 数。如果芒与c 相互之间独立，那么m i ( t ，c ，) 为零。 学硕士研究生学位论文第1 1 页 衡量的是一个单词与一个类之间的相关程 劬f ) ：坐丝望二丝蔓( 2 7 ) 、7 i ( 么+ c ) ( 曰+ d ) ( 么+ b ) ( c + d ) 其中：a 表示c i 类中出现词t 的文档数；b 表示其它类中出现词t 的文 档数；c 表示c i 类中不出现词t 的文档数；d 表示其它类中不出现词t 的文 档数；n 表示文档总数。这个公式计算的只是一个单词相对于某一个类的c h i 值，它相对于整个文本数据的c h i 值是其相对于所有类c h i 值的综合。综合 的方式通常有两种，一种是加权平均，如公式( 2 - 8 ) ： lci 伽去( ) _ f 三1 尸( i ) 伽( 屯巳) 2 8 ) 另一种是取最大值，如公式( 2 - 9 ) ： 明( r ) 21 峄( 伽( f ，勺) ) ( 2 9 ) 一 j 卡方统计具有二次复杂度。卡方统计与m i 的主要区别是卡方统计是一个 归一化的值。因此卡方统计可以衡量相同类别中的特征。然而如果某一特征 在上述公式的四个量( a b c d ) 当中出现不均衡，则将会破坏卡方统计的归一 性。即卡方统计不适合计算低频率的特征。 2 3 1 5交叉熵 交叉熵( c r o s se n t r o p y ，c e ) 公式与i g 类似，不同在于交叉熵只计算在 文档中出现过的特征，其公式如( 2 1 0 ) 。 c e ( 沪莩剐) l o g 等 ( 2 - 2 3 1 6其它 此外，还有词强度( t e r ms t r e n t h ，t s ) ，优势率( o d d sr a t i o ，o r ) 等等。 第1 2 页 2 4 文本分类算法 在特征降维之后，就将应用分类器对文本分类。本文将简述如下分类方 法：中心法，近邻法，朴素贝叶斯，支持向量机，分类委员会以及回归模型。 2 4 1中心法 h a n n 们在2 0 0 0 年提出了中心化算法( c e n t r o i d ) 。首先，h a n 先对文档集 中的每个类别进行聚类，得到每个类的中心向量，如公式( 2 1 1 ) ： n 勺2 f 三1 哆 q 。d 其中n 是类c ，的大小。然后，再计算待分类文档与所有类中心的距离( 欧 式距离或余弦距离) ，选择最相似的类中心作为待分类文档的类别。然而在 文中，h a n 假设每个样本到其类中心的距离小于到其他类中心的距离。而这 是不符合实际情况的，即当数据不逞球形分布时，这将产生错误。为此， t h e e r a m u n k o n g n 7 3 改进了中心算法，采用了特征长度标准化，考虑了类内和 类问的特征频率分布即( 1 ) 类间因素，( 2 ) 类内因素，( 3 ) 文档因素，( 4 ) 标准化因素。简单讲，就是将原来的不规则形状规则化，或者说是充分考虑 了类分布的形状，在实验中，t h a n a r u k 的方法取得了较好的结果。由于数 据分布的随机性，t h a n a r u k 的方法无法解决如下的数据误分类问题。 为改进这种方法，t a n n 8 3 提出了基于拉推策略的中心法。同b a g g i n g ， b o o s t i n g 算法相似，t a n 利用训练集的误分样本迭代的调整分类器偏差。拉 推策略的基本思想是：如果a 类中一个样本误分到了b 类，那么就调整a 类 中心a ，b 类中心b 和误分样本之间的距离，或拉近a 与样本的距离，或推 远b 与样本的距离。以提高分类精度。同时，t a n 也将这种策略应用到了k n n 等其他分类方法中。 西南科技大学硕士研究生学位论文第1 3 页 2 4 2k 近邻 近邻法( k n n ) 于6 0 年代提出，在文本分类领域被证明是一个性能极佳 的经典算法。k n n 的思想是：先将待分类文本表示成与类中文本一样的向量， 然后应用某个度量策略( 余弦相似度或欧式距离) 来计算它们之间的相似程 度( 距离) ，然后选择k 个距离最小的文本作为分类参考文本，再根据这k 个文本判断待分类文本的类别。 由于k n n 存在计算复杂度大，样本依赖度大等缺点，因此有很多方法来 改进k n n 的效率。目前主要有两类方法：提高计算速度和优化度量距离。提 高计算速度又可分两类：浓缩训练样本和加快搜索速度。 2 4 3 朴素贝叶斯 概率方法是最早用于文本分类的分类器算法。概率分类器基于贝叶斯理 论来计算待定文档与已知各个类的条件概率。其公式如( 2 1 2 ) ： p ( c 1 d ) ：p ( c i ) ? ( 5 i c ) 。 ( 2 1 2 ) p ( 勺l 勺) = 矿 ( 2 - 1 2 ) 其中： 尸li 少后n ： 2 1 3 而p ( d ) 是固定的，可以不计算。 j n i r n 们提出的朴素贝叶斯( n b ) 假定各特征值之间的取值相互独立，虽然 这与文本分类的实际情况不符，但是在分类过程中却表现出很好的性能。然 而，当数据集特征取值相互依赖时，n b 的分类精度将受到影响，为改进这 个问题，z h a n g 乜们提出隐朴素贝叶斯模型( h n b ) ，如公式( 2 1 4 ) 。在h n b 中， 类中每个属性的值用其隐藏父属性的值代替，而这个父属性值具有表示属性 依赖度的能力。 42c 锄 a ， p n n = ) 1 cp l i c 4 ” ：、 正 p 中 其 西南科技大学硕士研究生学位论文第1 4 页 p 4 i f c 卜歹：石二f 叩4i 勺，o q 。1 5 ) 其中， 4 ，厶是类c 的属性， f 是鸣的隐藏父属性。其决策规则公式 ( 2 1 6 ) o 2 4 4 支持向量机 从v a p n i k 心提出支持向量机( s v m ) 以来，支持向量机迅速成为机器学 习领域的最有效方法，也被证明是文本分类中最好的分类器。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原 理基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学 习精度) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷， 以期获得最好的推广能力。 从几何上说，支持向量机就是要在r 维空间中寻找到最佳决策面，该决 策面能最好地区分正例和反例，使正例与反例之间的分类间隔最大。最佳决 策面上的样本称为支持向量。对于非线性问题，可以通过非线性变换转化为 某个高维空间中的线性问题，在变换空间中寻找最优分类面。 对于非线性问题，可以通过非线性变换转化为某个高维空间中的线性问 题，在变换空间中寻找最优分类面。 s v m 方法有很坚实的理论基础，s v m 训练的本质是解决一个二次规划 ( q p ) 问题，得到的是全局最优解，这使它有着其他统计学习技术难以比拟 的优越性。 2 4 5 分类委员会 分类委员会基于如下假设：对一个需要进行的任务，五个人判断的有效 组合应该优于个人的判断。在文本分类中，选择詹个不同的分类器进行同 样的分类任务，然后将其分类结果进行合适的组合得到最终的分类结果乜纠。 最简单的组合规则是投票( m a j o r i t yv o t i n g ，m v ) ，即对于二分类的分 类器，得到超过半数投票的结果被选为最终结果。