（计算机应用技术专业论文）文本分类新方法的研究与应用.pdf

摘要 摘要 网络技术的快速发展使得互联网上的信息呈现爆炸式的增长。为了有效地利用和管 理海量信息，基于内容的信息检索和数据挖掘逐渐成为备受关注的领域。文本分类技术 t c ( t e x tc a t e g o r i z a t i o n ) 是信息检索和数据挖掘的核心内容。其中基于机器学习的文本 分类方法被认为在分类精度和灵活性上达到了较为满意的效果，但是它仍然存在着譬如 非线性、数据集偏斜、标注瓶颈、多层分类、算法的扩展性及w e b 网页分类等问题。 本文在数据集不完整和类别关系复杂的情况下进行了一系列的研究，主要包括文本 表示，特征提取，特征选择，以及文本分类算法等问题。重点的目标就是通过研究这些 问题找到如何在不完整样本集下提高文本分类精度的方法，以及如何在样本集中类别无 法确定的情况下，发现新的类别，避免错分，借此提高文本分类效果。 现实世界中的数据往往是不完整的，因此对于不完整数据集的文本分类的研究，经 常采用的方法是利用朴素贝叶斯分类模型与e m 算法相结合的办法来得到最终的分类 器。但由于朴素贝叶斯分类器和e m 算法对初始数据值有很大的依赖性，特别是当样本 集中的无标记文本即缺失数据数量所占比重较大时，分类器的测试精度会受到影响。为 了改善文本分类的效果，本文在b e r n o u l l i 混合模型和e m 算法的基础上进行了研究。首先 通过朴素贝叶斯算法在已标记数据的基础上得到似然函数参数估计初始值，然后利用含 有权值名的e m 算法矛t l b e m o u l l i 混合模型对分类器的先验概率模型进行参数估计，从而得 到最终的分类器。实验结果表明，对于不完整数据集而言所提出的方法在准确率和查全 率方面要优于朴素贝叶斯文本分类及结合了e m 算法的朴素贝叶斯分类。 在以上方法基础上对不完整数据集对于文本分类的影响进行了进一步的研究。发现 适当的在测试集中加入未标记数据样本是在现实世界中是需要经常面对的问题，本文在 这方面做了相关的工作，将网页分类看成文本分类的一种特殊情况，同时考虑了网页结 构对文本分类造成的影响，重点研究了文本相似度算法在这类问题上的应用，简单的文 本相似度算法无法区分出有类别文本和无类别文本的区别，本文的研究结合特征提取， 特征选择，最优截尾法，提出了一种新的文本分类方法，首先对网页进行预处理，得到想 要的网页内容，在此基础上借助特征向量在有类别文本和无类别文本上的不同分布，达 到区分不同类别的目的。实验证明这种方法对于不完整数据而言，一方面可以改善分类 精度，另一方面可以达到发现新类别的目的。 关键词：文本分类，网页分类，朴素贝叶斯算法，e m 算法，不完整数据集 a b s t r a c t a b s t r a c t t h ei n f o r m a t i o no nt h ew e bw a si n c r e a s e dr a p i d l yw i t ht h ed e v e l o p m e n to ft h ei n t e m e t i no r d e rt ou s et h ei n f o r m a t i o ne a s i l y , m a n yp e o p l ef o c u s e do nt h es e a r c he n g i n ea n dt h ed a t a m i n i n g t e x tc a t e g o r i z a t i o n ( t c ) i sv e r yi m p o r t a n ti nt h es e a r c he n g i n ea n dt h ed a t am i n i n g t h em e t h o d sb a s e do nt h em a c h i n el e a r n i n gg o tag o o dr e s u l ti nt h et e x tc a t e g o r i z a t i o n b u t t h ep r o b l e ms u c ha sn o n l i n e a r i t y , s k e w e dd a t ad i s t r i b u t i o n ，l a b e l i n gb o t t l e n e c k ，h i e r a r c h i c a l c a t e g o r i z a t i o n ，s c a l a b i l i t yo fa l g o r i t h m sa n dc a t e g o r i z a t i o no fw e bp a g e sw e r et h ep r o b l e m s t ot h es t u d yo ft e x tc a t e g o r i z a t i o n i nt h i sp a p e r , t h er e s e a r c ho nt h eu n l a b e l e dd a t aa n dh i e r a r c h i c a lc a t e g o r i z a t i o nw e r e s t u d i e d t h ep r o b l e m ss u c ha sf e a t u r es e l e c t i o n , f e a t u r ed i s t i l l ，a l g o r i t h mo ft h et e x t c a t e g o r i z a t i o nw e r ed i s c u s s e d t h ed a t af r o mr e a lw o r l di sa l w a y si n c o m p l e t e s oc o n s t r u c t i n gt h ec l a s s i f i e r sf r o m i n c o m p l e t ed a t aw a sa ni m p o r t a n tp r o b l e m t h en o r m a lw a yu s e dt h en a i v eb a y e sc l a s s i f i e r a n de ma l g o r i t h mt ot r a i nt h ed a t as e t b u tb o t ht h en a i v eb a y e sc l a s s i f i e ra n de ma l g o r i t h m d e p e n d e do nt h ei n i t i a ld a t a e s p e c i a l l y , w h e nt h en u m b e ro ft h eu n l a b e l e dd a t a ( i n c o m p l e t e d a t a ) w a sm o r et h a nt h el a b e l e dd a t a t h ep r e c i s i o no ft h ec l a s s i f i e rw i l lb ea f f e c t e d i no r d e r t oi m p r o v et h er e s u l to ft h ec l a s s i f i c a t i o n ，t h i sp a p e ri n t r o d u c e dan e wm e t h o dt h a tw a sb a s e d o nb e r n o u l l im i x t u r em o d e la n de ma l g o r i t h m c o m m o nw e b c a t e g o r ym e t h o dm o s t l yb a s e do nt e x tc l a s s i f i c a t i o n ，w h i c hd i d n tt a k ef u l l c o n s i d e r a t i o n so np a r t i c u l a r i t yo ft h ew e bc l a s s i f i c a t i o ni n c l u d es e m i s t r u c t u r e df e a t u r ea n d t h en o i s yi n f o r m a t i o n f u r t h e r m o r e ，t h et e s t i n gd a t aa n dt r a i n i n gd a t ac a m ef r o mt h es a m e d a t as a m p l ei nm a n yw e bc l a s s i f i c a t i o n s ，b u ts o m e t i m e s ，w en e e dc o n s i d e rt h es a m p l ei nt h e t e s t i n gd a t ad i d n tc o m ef r o mt h es a m es a m p l e i tw a sc o n s i d e r e dt h a tt h et e s t i n gd a t aw a s c o n s t i t u t e db yl a b e l e dd a t aa n du n l a b e l e dd a t a aw e bc a t e g o r ym e t h o dl u d ( l e a r n i n gb y u n l a b e l e dd a t a ) w a sp r o v i d e dt oi m p r o v et h ep r e c i s eo fc l a s s i f i c a t i o n t h ee x p e r i m e n t a l r e s u l t ss h o w e dt h a tl u dm e t h o dw a sb e t t e rt h a nc o m m o nc l a s s i f i c a t i o nm e t h o d ；t h ef o r m e r c o u l di m p r o v et h ep r e c i s eo fc l a s s i f i c a t i o na n dp r o v i d e dam e t h o df o rd i s c o v e r i n gt h en e w c a t e g o r y 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 ，w e bc l a s s i f i c a t i o n ，n a i v eb a y e s ，e ma l g o r i t h m ， i n c o m p l e t ed a t a i i 独创生声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：藤案丕奠日 期：2 。3 口r 罗 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名： 导师签名： 日耘：o b o8 。口。j j 第一章绪论 第一章绪论 随着信息技术的发展，互联网上的信息呈现爆炸式的增长，人们在日常的生活中无 时无刻的都需要获得信息，分析信息，利用信息，于是如何才能够正确且快速准确的利 用互联网上的海量信息，引起了学者的广泛关注。 1 1 选题背景和研究意义 1 1 1 选题背景 自上世纪9 0 年代后期以来，因特网技术发展迅猛，网页的极大增多和网络数据的急 剧膨胀使人们感受到了信息浪潮带来的冲击，因特网已经成为世界上最大的信息资源 地。然而，在互联网上信息不断增加、信息的种类也在不断扩张的同时，是网络带来海 量的数据使人们获取有效信息的需求却变得越来越困难。有效信息往往被一些不相关的 信息所湮没，使人们迷失在信息的浪潮中。在信息爆炸时代，大规模的数据就是信息， 人们想得到正确的信息就需要对数据进行分析，发现其中蕴含的规律【l 捌。这时数据挖掘， 信息检索技术应运而生。数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程，它是一种综合应用统计分析、数据库、智能语言等来分析庞大数据资料 的智能化技术【3 ，4 】。信息检索( i n f o r m a t i o nr e t r i e v a l ) 是指将信息按一定的方式组织和存储 起来，并根据信息用户的需要找出有关的信息过程，所以它的全称又叫“信息的存储与 检索( i n f o r m a t i o ns t o r a g ea n dr e t r i e v a l ) ，这是广义的信息检索。狭义的信息检索则仅指 该过程的后半部分，即从信息集合中找出所需要的信息的过程，相当于人们通常所说的 信息查寻( i n f o r m a t i o ns e a r c h ) 2 ，3 4 j 。 1 1 2 研究意义 无论是数据挖掘还是信息检索技术，其中的核心内容都是文本分类t c ( t e x t c a t e g o r i z a t i o n ) 。其主要任务是指在给定文本分类体系下，根据文本内容判定文本所属类 别。文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有着广 泛的应用。早期的文本分类技术主要是基于知识系统，通过手工定义的一些规则来对文 本进行分类，这种方法由于自身的局限性( 费时，需要有相关领域的专家) 而没有得到广 泛的发展【1 1 。而目前基于机器学习的文本分类技术由于更注重分类器的模型自动挖掘和 生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本 分类模式有所突破，因此成为相关领域研究和应用的重点。其中主要包括文本表示，文 本分词( 中文) ，特征提取，特征选择和分类算法。 一方面基于机器学习的文本分类技术能够很好的适应数据挖掘和信息检索的应用， 但与此同时由于数据的不确定性和数据量的庞大性，文本分类技术也面临着很多问题譬 如非线性、数据集偏斜、标注瓶颈、多层分类、算法的扩展性及w e b 页分类等问题【2 】。 其中衡量文本分类最重要的分类效果一直是人们研究的重点，分类效果的好坏直接的关 系到应用的健壮性。同时由于文本分类的数据集包含有庞大的信息，如何能够研究出更 江南大学硕士学位论文 有效的方法提高分类效率也是人们普遍关心的问题。 1 2 研究现状 文本分类是指在给定的分类模型下，根据文本内容确定文本类别的过程。简单来说 它的发展过程大体可以分为三个阶段。上世纪6 0 年代到8 0 年代大部分的文本分类器都 是基于专家系统的，在分类精度上达到了较好的效果，但是也面临着很多问题，第一就 是大量各个领域的专家耗费了很多经费，第二就是随着互联网的逐渐兴起，需要处理更 多更复杂的数据【2 】。这时基于机器学习的文本分类系统应运而生，它不但在分类精度上 可以和专家系统相比，在分类速度上也远远好于前者，适合处理大量数据，在这期间机 器学习的大量算法被应用到文本分类领域。包括最近邻【5 1 、贝叶斯【6 1 、决策树【7 1 、神经 网络 8 】等等。y a n g 9 1 总结了各种分类算法在不同数据集上的分类效果，对基于机器学 - - j 的文本分类技术做了完美的总结。目前贝叶斯算法和最近邻算法被证明在实际应用中效 果最好。目前很多的研究也多是基于此类文本分类技术。要说明的是9 0 年代中后期， 人们将支持向量机的概念引入到文本分类领域，s v m f l 0 】的分类器也取得了非常好的效 果。 苏【2 】在他的论文中对基于机器学习的文本分类算法所面临的问题做出了总结，目前 关于文本分类问题的研究主要集中在以下几个方面： 数据集倾斜：当样本集的文本数量很大时，往往会发生这种样本不均衡的问题，类 别之间的样本数量有可能存在数量级的差距，这种情况下由于样本集中数据分布的不均 匀使得分类精度受到很大的影响，分类器被大类所主导，严重影响分类效果。与此同时 大部分的经典算法都是基于分布均匀的样本数据集。因此这类问题引起了很多学者的关 注【2 1 。 目前较为常用的解决方法对策有：( 1 ) 在取样的时候，弱化大类，强化小类。但存在 的问题也很明显就是会增加很多的干扰信息【l 。( 2 ) 通过误差加权增大小类样本对分类器 的贡献【1 2 】。( 3 ) 通过不同的特征选择办法来分别对大类和小类提取特征向量【1 3 】。解决这 类问题的关键就是如何加大分类器对于小类样本特征的重视。 互联网上的海量信息往往都是有层次的，每一个大类包含着若干个小类，构成了一 种类似于树状结构的组织。这种分类问题的最大好处就是可以提高分类效率，在多层分 类的高层就可以过滤掉很多不相关的文档。目前所研究的文本分类方法可以看成是多层 分类的底层 1 4 , 1 5 ，是多层分类技术的特例。多层分类的问题在于类别之间关系的复杂度， 以及不同层次之间分类所造成的误差。 不完整数据集：所谓不完整数据集就是指在样本集中存在着大量未标记数据，即小 样本问题。互联网的兴起，使人们可以方便快捷的获得大量数据，但要想获得大量的有 标记数据样本，还是要耗费大量的人力物力，如何才能更好的利用大量未标记数据集逐 渐引起了很多学者的关注【2 】。 n i g a m 1 6 】在他的博士论文中首次利用e m 算法结合朴素贝叶斯分类器对这类问题进 行了深入研究，它的主要思想是利用已标注样本集训练得到初始分类器，利用朴素贝叶 斯分类器和e m 算法估计未标记样本的所属类别并得到相应参数，之后重新训练分类器， 2 第一章绪论 如此反复迭代直到满足一定条件为止，借此得到最终的分类器。陈【1 7 】等人设计了一种基 于不完整数据集的贝叶斯分类器，也对这类问题展开了研究。 另外一种应用于不完整数据的文本分类方法是j a o c h i m s 提出的直推向量机方法 ( t s v m ) 1 8 l9 1 ，它的主要思想是首先利用有标记样本集通过s v m 方法训练得到一个分类 器，在这基础之上对未标记样本集进行误差预测，将误差较小的一些样本加入到有标记 样本集中得到新的分类器，反复迭代直到收敛为止。 还有一些方法包括l i u 2 0 , 2 h 等人提出的使用正例样本和未标注样本进行学习；利用 s v m 2 2 】主动学习来解决这类问题。 w e b 网页分类：目前讨论的大部分问题都是面向文本内容的。如果信息来源于网页 则不考虑网页的结构等信息。然而在越来越多的研究中发现，网页结构信息可以有效得 帮助改善分类效果【2 3 1 ，因此如何利用h t m l 结构信息引起了很多学者的关注。 第一种考虑就是如何利用网页的超链信息，大部分的网页超链接包含的都是噪音信 息，但与此同时有些超链又包含有用信息，因此如何在这之间做出平衡也是摆在很多学 者面前的问题。“【2 4 】等人提出了一种基于网页结构的模型，考虑到一个网站内部噪音结 构的相似性来达到去除噪音改善分类效果的目的。 第二种情况则是范焱【2 5 】等人提出的组合分类器的思想，重点考虑网页信息中所包含 的例如标题，加粗字段，这些文本内容的权值都要比普通的文本大，继而利用文本类别 相似度算法对不同的网页进行分类，达到较好的分类效果。 综上所述，在发现文本分类领域的研究在不断进展的同时，也面临着很多问题有待 研究。 1 3 研究内容 本文的内容集中在样本是不完整数据集的情况下文本分类的相关研究。包括文本表 示，特征选择，改进算法在不完整数据集上的应用，以及未标记数据集在w e b 网页分类 上的研究。主要研究内容如下： 利用朴素贝叶斯分类器结合e m 2 6 】算法改进基于不完整数据集的文本分类精度，由 于朴素贝叶斯分类器和e m 算法对初始数据值有很大的依赖性，特别是当样本集中的无 标记文本即缺失数据数量所占比重较大时，分类器的测试精度会受到影响。为了改善文 本分类的效果，本文在b e r n o u l l i 混合模型和e m 算法的基础上给出了一种基于不完整数 据的改进方法。首先通过b e r n o u l l i 混合模型和朴素贝叶斯算法在已标记数据的基础上得 到似然函数参数估计初始值 2 7 , 2 8 】，然后利用含有权值兄的e m 算法对分类器的先验概率 模型进行参数估计，从而得到最终的分类器【1 6 】。实验结果表明，对于不完整数据集而言 本文所提出的方法在准确率和查全率方面要优于朴素贝叶斯文本分类。 在以上研究的基础上，提出了如何利用不完整数据集识别出新类别样本的方法。在 文本分类的过程中，特别是网页分类中，有一个问题是无法回避的，事实也证明它会影 响分类精度，那就是在样本集中包含有未知类别的情况，特别是在不完整数据集中，如 何保证未标记数据中无类别文本不影响文本分类的精度，本文在这方面做了研究，将网 页分类看成文本分类的一种特殊情况，同时考虑了网页结构对文本分类造成的影响，重 江南大学硕士学位论文 点研究了文本相似度算法在这类问题上的应用【1 9 ，2 9 ，3 0 1 ，提出了一种新的文本分类方法 ( l u d ) ，首先对网页进行预处理，得到想要的网页内容，在此基础上借助特征向量在有 类别文本和无类别文本上的不同分布，达到区分不同类别的目的。实验证明这种方法对 于不完整数据而言，一方面可以改善分类精度，另一方面可以达到发现新类别的目的。 1 4 论文结构 本文由6 章组成，各章的主要内容安排如下： 第1 章为绪论，分为4 个小节。第1 小节介绍了课题研究的背景；第2 小节简要介 绍了课题研究相关内容的研究现状；第3 小节则介绍课题研究的意义和目标；第4 小节 则介绍了本文的章节安排。 第2 章是文本分类概述。这一章主要内容是较全面的总结和回顾文本分类的准则和 主要方法。第l 小节主要介绍了文本预处理与文本表示；第2 小节回顾了文本分类的主 要算法；第3 小节则介绍了文本分类的评价标准和相关语料库；最后简要的介绍了特征 排序的内容。 第3 章是基于不完整数据集的文本分类方法介绍。在这一章中重点介绍了朴素贝叶 斯分类器结合e m 算法和p u 。l e a r n i n g 问题，并介绍了在本文提出算法中将要采用的估 计方法。第l 小节简介了朴素贝叶斯分类器结合e m 算法的相关内容；在第2 小节中， 则概述了直推向量机；第3 小节里，主要介绍了在训练集和测试集中的样本不同分布的 情况下，如何处理不完整数据集。 第4 章是改进的基于不完整数据集的文本分类新方法，这一章里介绍了几本理论， 用实验来验证它的可行性，并和各种现有方法的比较情况。在第1 小节里，主要阐述了 统计推理和最大似然估计；第2 小节中，则介绍了混合模型的e m 算法；在3 小节中针 对贝叶斯分类器和e m 算法提出e m n b 算法；第4 小结用大量的实验来验证本文算法 的可行性以及和一些类似算法的比较结果；最后在第5 小节里对这一章内容进行了总结。 第5 章是基于不完整数据集发现新类别的文本分类方法。这一章里介绍了相关理 论，用实验来验证它的可行性，并和各种现有方法的比较情况。在第l 小节里，主要阐 述了基于文本相似度算法的原理；第2 小节中，则网页噪音处理对网页内容进行预处理； 在3 小节中提出结合前面两种问题的l u d 算法；第4 小结用大量的实验来验证本文算 法的可行性以及和一些类似算法的比较结果；最后在第5 小节里对这一章内容进行了总 结。 第6 章为总结与展望。在这一章里，主要是对本文进行了回顾总结，并对以后的工 作和方向进行了展望。 4 第二章文本分类概述 第二章文本分类概述 本章主要介绍文本分类领域比较成熟的技术，包括文本预处理，文本的表示，文本 特征向量的提取，特征向量的选择，文本分类的相关算法，文本分类效果评估和文本分 类领域的语料库等。 2 1 文本预处理与文本表示 2 1 1 文本预处理 文本预处理是文本分类的前提，如何将一个普通的文本转化为可以处理的数据是它 的研究重点。同时为了适应各种不同的情况，文本预处理也会有所不同，其主旨是将文 本处理为适合分类器的数据集。般来说文本预处理主要包括，去除停用词，过滤非法 字符，中文文本分类中还有分词的问题，同时还包括在w e b 网页分类中如何处理h t m l 结构化语言的问题。 1 1 去除停用词 停用词是指常见常用而导致对文本分类没有贡献的词，这类词主要包含三类，1 ：常 见名词没有特殊的含义，2 ：语气词，助词等等。例如：“t h e ，“a ，“a n d ，“的 等。 上述这些词的特点是没有明确的涵义，同时在文本中多次出现，对文本分类没有贡献。 而第三类词则是对于特定的文本分类，会有些出现频率太低的特别词，是对文本分类没 有贡献的。因此，需要在文本预处理的过程中过滤掉停用词，以免影响分类精度。 2 ) 过滤非法字符 非法字符也类似于停用表，但是和停用表不同的是对于不同等的分类方法而言，非 法字符往往也是不一样的，而停用词则是适用于所用情况。因此这里同样也要过滤掉非 法字符来改善分类结果。 以上两种方法具有普遍的适用性，就是过滤掉无用的词。下面两种方法针对中文文 本分类和w e b 网页文本分类来讨论文本预处理方法。 3 ) 中文分词技术 中文分词技术是中文分类中特有的概念，由于英文单词之间有空格将各个词分隔开， 而中文则是根据词和词之间的概念来区分，所以有更大的难度，正因为这样，中文分词 是中文文本分类预处理中关键的一步。黄【3 l 】给出了一种基本的方法最大匹配法又称基于 字符串的匹配方法。这种方法的基本过程是：假设词表中最长的词由f 个字组成，则每次 从句子头上截取一个长度为f 的字串，令它同词表中的词条依次匹配，如果词表中确有这 样一个f 字词，匹配成功，就把这个字串作为一个词从句子头上切分出去。基于理解的分 词方法通过让计算机模拟人对句子的理解，达到识别词的效果。另外一种方法则是基于 统计的。这种方法认为在上下文中，相邻的字出现次数越多，就越有可能构成一个词。 上述方法都可以达到一定的分类效果，但也各有缺点，对于匹配方法而言，如何给 定切分规则是一个不可回避的问题。同时文本中有大量的无法识别的词，如何处理这些 词也是需要考虑的问题。相比较而言基于统计的方法在切分词和识别新词方面的分词效 果好于前面两种方法，但是这种方法的局限在于抽取出来的词并不是有意义的。 江南大学硕+ 学位论文 4 ) w e b 网页预处理： 互联网是信息的载体，构成互联网的w e b 网页则是载体中的单元。w e b 网页不同于 普通的文本，多数是由半结构化的语言h t m l 构成，如何提取出w e b 网页中相对有用 的信息是w e b 文本分类中重要的一环。大体上有以下几种处理方法，首先将w e b 网页 中所有文字都认为是有用信息或都被认为是无用信息，这就造成己可能包含大量的噪音 信息或者去掉了大量有用信息。第二种情况是将诸如网页标题和字体加粗的链接信息看 成是有用信息，而其他的链接信息则过滤掉。这种方法相对于第一种而言做出了相对的 平衡可以达到较好的效果。最后一种是根据一定的规则判断出要保留那些链接信息，对 于特定的网页分类而言，有特定的规则，这种方法无疑是预处理中最好的。但是存在着 适用面不广的问题。 2 1 2 文本表示 人工智能的主要宗旨就是让计算机具有像人一样的分辨能力和思考能力，虽然目前 在这一领域的进展没有达到人们的预期，但是在很多方面还是取得了很大的成就。在文 本分类中让机器识别文本是本文首要考虑的问题。表示文本的方法包括词，词组，概念 等等。目前较常用的系统通常依赖于词条匹配和计数技术，即通过词条出现的次数向量 隐含并近似的捕捉了文档语义。目f j 较常用的文本表示模型有布尔模型，向量空间模型， 概率检索模型三种。 1 ) 布尔模型 布尔模型是在早期的信息检索系统中很常用的一种模型，在这种模型中每篇文档被 表示成文档中出现的特征集合，这里面的词条权就是指出某个词条是否在相应的文档中 出现【3 2 1 。向量中的每个权重向量表示为0 和l ，1 表示词条出现，而0 则表示未出现。 2 ) 向量空间模型 向量空间模型由s a l t o n 【3 3 ，3 4 】等人提出，此模型被认为是处理信息检索领域问题的最 佳模型。它的主要思想是，对于一个文本集合d ，选择n 个最具代表性的标引词t ，构成 特征集合丁，每一个特征集合中的元素f ，就对应空间模型的一维，文本d 就可以表示 为一个, 维的向量，其中为第f 维特征在该文本中的权重。这样，每一个文本就可以 映射为向量空间模型中的一个点，文本之间的相关性就可以通过向量之间的距离来计 算。将文档表示成向量空间模型主要有两部分组成，第一是特征项，文本的内容由前面 提到的词或词组等特征项来表示。正是由这些基本的单位组成了文本。另外一个则是特 征项的权重，每一个特征项对应一个特征权重，表示此特征项在文本中的重要程度。 由此就得到了一个由特征项和特征项权重组成的向量空间模型【3 】，对于特征项而言 利用前面提到的分词和特殊字符过滤等技术来达到预处理的目的，得到相应的特征项。 由于权重表达了特征项在文本中的重要程度，因此有多种不同的方法来计算权重。目前 较常用的技术包括以下两点，布尔权重和通过t f i d f 来计算权重。布尔权重考虑的方式 相对简单，如果特征项在文本中不出现则权重是o ，相反则为l 。布尔权重无法体现出 词条的重要程度。t f i d f 是不但考虑的特征项在文本中出现的频度，同时还考虑到了其 6 第二章文本分类概述 在整个语料中的分布情况，因此被认为是较好的特征项权重计算公式。其中t f 表示了 特征在文本中出现的频率，而i d f 则表示特征在整个语料的文本中的分布情况。t f 越 大，表示了此特征在这个文本中重要程度越高，而i d f 越大表示了其在整个文本中的分 布相对集中。 2 1 3 特征选择 特征选择的定义是指，在有文本表示组成的特征空间中进行筛选，最终得到符合要 求的新特征，是文本分类的重要一环，也是文本表示的最后一环。由于文本表示的特征 项所包含的信息存在维数过高和特征项分布不均匀的特点，因此如何对特征进行选择是 确保文本分类精度不受影响的一大关键。特征选择的主要目的是提高文本分类的效率， 改善文本分类效果。目前特征选择的常用技术主要有以下几种：文档频率( d o c u m e n t f r e q u e n c y ，d f ) t 3 5 1 ，信息增益( i n f o r m a t i o ng a i n ，i g ) t 1 1 ，互信。皂, ( m u t u a li n f o r m a t i o n ， m i ) t 3 6 1 ，期望交3 ( 嫡( e x p e c t e dc r o s se n t r o p y ，e c e ) t 3 7 】等。 1 ) 文档频率：首先根据特征项在文本中出现的频度来计算权值，然后根据需要设定 阈值，将文本频率高于设定阈值的值选定为表示文本的特征。以此方法来过滤掉一些出 现频率低，影响力不够的特征。因此该方法是最简单但同时也是很有效的一种特征选择 方法。 2 ) 信息增益：信息增益通过特征项在文本中的出现与否来判断其携带的信息量。其 公式如下所示： 佑( 磁) 一羔尸( q ) 1 0 9 p ( q ) + 尸( 川mp ( c ：f w ) l o g p ( c i w ) + 尸( 习兰p ( qi 习l o g p ( c ：fi ) ( 2 1 ) 其中p ( c i ) 表示任意一篇文本属于第i x 的概率，p ( w ) 表示特征项在文本集中出 现的概率。p ( w ) 表示除外的特征项在文本集中出现的概率。p ( qw ) 表示任意一篇 包含w 的文本属于第f 类的概率。p fc ，1w l 表示不包含w 的文本属于第f 类的概率。 3 ) 互信息在统计语言模型中被广泛采用。互信息是信息熵的引申概念，是对两个随 机事件的相关性度量。特征项对于类别的互信息越大，它们之间的共现概率也越大。将 低于特定阈值的特征项从原始特征空间中移除，保留高于阈值的特征项。词条和类别之 间的互信息有公式计算如下： m ( w ，q ) = l 。g 币p ( w , 万c i ) ( 2 2 ) 其中p ( 嵋q ) 表示特征项w 在类别q 中出现的概率，尸( w ，c ) 表示特征项在所有文档 中出现的概率。互信息公式主要体现了特征项和类别之间的依赖程度，如果它们的分布 都是独立的，那么特征项和类别之间没有任何关系。同时设定阈值，考察那些关联程度 强的特征项保留下来，以达到特征提取的目的。 4 ) 期望交叉熵，反映了文本类别的概率分布和出现了某特定特征项的条件下的文本 类别概率分布之间的距离。特征项的熵越大，对文本越重要。公式如下所示： 7 江南大学硕士学位论文 e c e ( 小善p c i w ) 1 0 9 帮 ( 2 3 ) 其中p ( c fw ) 表示文档包含特征项w 时属于q 类的条件概率，尸( q ) 表示q 类文档 在样本集中出现的概率。如果特征项和类别强相关，如果特征项和类别强相关，也就是 p ( qw ) 大，且相应的类别出现概率小，则说明特征项对分类的影响大，相应的e c e ( w ) 值就大，就很可能被选中作为特征项。 2 2 文本分类相关算法 算法是文本分类的核心内容，文本预处理，文本表示和特征选择都是它的重要组成 部分。由于基于机器学习和统计学的算法在文本分类方面取得了很好的分类效果，因此 文本分类的相关经典算法大都来自于上述两个领域。常见的分类算法有文本相似度算 法，朴素贝叶斯分类算法，逝邻分类算法，神经网络分类算法以及基于统计学的s v m 分类算法等等。 2 2 1 文本相似度算法 这种方法【4 】的思路相对简单，利用向量空间模型通过特征项来代表每一个文本，同 时根据相应的提取规则为每一类生成一个代表该类的特征向量集合。当有新的文本到来 时，计算该文本的向量与每一类别向量之间的相似度，凭此来判断新文本所属类别。 s i m u = ，竹 k = l ( 2 4 ) 其中& m 。表示文本f 和类别，之间的相似度，经过此公式后确定文本所属类别。 2 2 2 朴素贝叶斯模型 朴素贝叶斯是一种线性分类器 6 1 。依据贝叶斯条件概率公式，假设样本的特征是相 互独立的，计算样本属于不同类别的条件概率，然后依据最大似然原理将该文档归为具 有最大后验概率的那一类。这种方法之所以在文本分类领域得到了广泛的应用，是因为 做出了较强的特征相互独立假设，对于这种假设一方面大大简化了贝叶斯分类器的计算 量；另一方面也导致了分类器的分类质量的不稳定性。该模型将样本看作独立的词条集 合，根据贝叶斯理论在训练集的基础上得到词条在不同类别的概率，构造出贝叶斯模型。 朴素贝叶斯分类方法的基本思想如下： 对于某个测试文本d i ，首先对其进行分词，然后按照下面的公式计算该文本属于类c ， 的概率： 枇) 2 裂孵揣 、 p ( e ) 与p ( q ) 有相同的定义，i c i 为类的个数，n 为文本4 的特征词个数。 第二章文本分类概述 将文本分到概率p ( qi 喀) 最大的那个类别中。其中p ( ic ) 的计算公式如下所示： 也= 老銎端鬻 仁6 ， m 是特征词的总个数，( w ，喀) 是指文档吐中词w 出现的次数；将文档的类别标记 为乃，如果文档西属于类别勺，则有咒= c i ，尸( 咒= c jl4 ) o ，1 ) 。当喀勺时， 尸( = c j id , ) - - 1 ，否则尸( 乃= c jd , ) = o 。类别勺的概率估计p ( q ) 为： 如) ：摧辞掣 ( 2 7 ) 2 2 3k 近邻 所谓i 逝邻算法又称最近邻算法，考察和待分类文本最相近的k 篇文本。根据k 个近 邻来确定未知文本所属的类别【7 1 。较常用的分类公式是未知样本被分至：l j k 个近邻中最相 似的类别中去。文本与某个类相似度的计算公式为： s i m ( x ，勺) = s f 聊( x ，4 ) ，( 喀，勺) ( 2 8 ) 其中s i m ( x ，4 ) 表示未知文本x 与第f 个最近邻文本之间的相似度( 欧拉距离) 厂( 喀，c j ) ( o ，1 ) 是一个函数，当喀的类为c j 时，其值为l ，否则为o 。 k 近邻方法在文本分类领域取得了很大的成功，具有良好的文本分类效果，同时它 也不需要训练与归纳，因为它认为类中所有的样本都可以代表该类，但这也导致了一个 问题就是分类时间过长，当类别文本过多时，需要和每一个文本计算距离。当引入阈值 后可以改善分类时问过长的问题，但与此同时也就需要一个判断的过程。 2 2 4 神经网络 神经网络系统是由大量简单的处理单元( 即神经元) 广泛连接而成的复杂网络系统。 它反映了人脑功能的许多基本特性，但它并不完全是人脑神经网络系统的真实写照，而 只是对其做某种简化、抽象和模拟。目前在文本分类领域得到广泛应用的是前馈式神经 网络，又称多层感知机【8 1 。多层感知机的输入输出关系，可以看成是一种映射关系，即 每一组输入对应着一组输出。多层感知机的分类精度相当高，仅次于支持向量机。 2 2 5 支持向量机 支持向量机( s v m ) 是在统计学的基础上发展起来的模式识别方法。在文本分类领域 取得了很大的成功。它的基本思想是找到一个超平面，使得它能够尽可能多的将两类数 据点正确地分开，同时使分开的两类数据点距离分类面最远。支持向量机方法是建立在 统计学习理论的v c 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型 的复杂性和学习能力之间寻求最佳折衷，以获得最好的推广能力【9 】。 s v m 是从线性可分得情况下的最优分类面发展而来的，基本思想是在一个平面中分 9 江南大学硕士学位论文 别用实心点和空心点代表两类样本，h 为分类线，h l ，h 2 分别为过各类中距离分类线最 近的样本且平行于分类线的直线，他们之间的距离叫做分类间隔。所谓最优分类线就是 要求分类线不但能将两类正确分开( i ) l l 练错误率为o ) ，而且使分类间隔最大。分类线方程 为x 1 3 v + b = 0 ，可以对它进行归一化，使得对线性可分得样本集 ( 鼍，y i ) ，f = 1 ，甩，x r d , y + 1 ，一l ，满足 y , e ( w 薯) + 6 一1 o ，i = 1 ，l ( 2 9 ) 此时分类间隔等于2 , q i ，使问隔最大等价于使| | w i l 2 最小。满足上面公式的条件且使 去i i 叫j 2 最小的分类面叫做最优分类面，h 1 ，h 2 上的训练样本点就称作支持向量。利用 l a g r a n g e 优化方法可以把上述最优分类面问题转化为其对偶问题，即下述公式， = o ，和口，0 i = 1 ，甩下对哆求解下列函数的最大值： q ( 口) = 嘶一去a ，口j y i y j ( x l _ ) ( 2 1 0 ) 为原问题中与每个约束条件对应的l a g r a n g e 乘子。最终得到最优分类函数 ( x ) - - s g n c w x ) + 6 ) = s g n c t t y i ( x i x ) + 6 ( 2 1 1 ) 其中的b 代表分类阈值，可以用任一个支持向量求得，以上完成了线性分类器的主 要步骤。支持向量机在现实中被认为是效果非常好的分类器，因此得到了广泛的应用， 但是由于支持向量机的训练是一个二次规划问题，所以它的训练集规模受到严格的限 制，对于大规模语料集的训练还存在很多问题。 2 3 性能评价与相关语料库 2 3 1 性能评价 如何判断文本效果的好坏是文本分类重要的课题，在文本分类研究领域，较常用的 评价准则有三种，分别是准确率，召回率和f s c o r e 。 准确率是指一个文本分类器分到某一类别而且的确属于这个类别的概率。 召回率又称查全率是指一个文档应该属于某一类别而分类器也确实将其分到该类别 的概率。 f s c o r e 是综合考虑了查全率和准确率根据一定的公式得到的评判标准。 准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学公式表 示如下： 准确率= 蒜黼 ( 2 1 2 ) 查全率是人工分类应有的文本中分类系统吻合的文本所占的比率，其数学公式表示 如下： 1 0 第二章文本分类概述 查全率= 等器 ( 2 1 3 ) 准确率和查全率反映是从两个不同的角度反映文本分类效果，因此人们提出了新的 评判准则，f - s c o r e 值。此方法由v a nr i j s b e r g e n 在19 7 9 年首先提出，该指标将查全率 和准确率两者结合为一个指标，两者相对重要性用参数来刻画，c 的计算公式如下所 示： f 1 + 口2 1 p r e c i s i d 玎r e c a l l 易2 罱磊磊忑面1 0 0 ( 2 1 4 ) 其中p r e c i s i o n 代表准确率，r e c a l l 代表查全率。的取值不同代表着不同的涵义， 取值范围为【o ，0 0 】。p = o 时，易就是代表准确率，当= l 准确率与查全率在评判的 过程中