（管理科学与工程专业论文）文本分类中的关键技术研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 随着i n t 锄e t 的大规模普及，信息量的迅猛增加，用户要在信息海洋里，快速、 准确、全面地找到所需要的信息，就像大海捞针一样困难。如何有效地组织和管理 数据，方便人们的检索? 如何快速地区分有用信息和无用信息? 如何从海量的数据 中高效地获取有用知识? 如何满足各种用户的个性化需求? 所有这些问题都成了 人们面临的挑战性课题。 文本分类是将自然文本根据内容自动分为预先定义的一个或者几个类别的过 程。它作为处理和组织大量文本数据的关键技术，可以在较大程度上解决信息杂乱 无章的问题，方便用户准确地定位所需的信息。在文本分类领域，有两个影响分类 效果的主要因素，分别是特征选择算法和文本分类算法。特征选择主要是找出描述 特定领域的相关词汇，去除影响分类效果的噪音词汇( 如虚词、形容词等) ，它可 以大大减少特征集合中的特征数，提高系统运行的速度和分类准确度；而好的分类 算法则是取得满意的分类效果的保证。 z 统计量( c l l i s q u a r e ，c h i ) 是一种重要的特征选择算法，这种算法考虑了特 征与类别出现的各种可能性，表现出了良好的分类效果和稳定性。但也存在着缺陷 和不足，它对低文档频的特征项不可靠，而且不能说明词条和类别的相关性。本文 根据z 统计量算法存在的这两个缺点，对其进行了改进，提出了统计频率( s t a t i s t i c a l f r e q u e n c y ，s f ) 算法，实验结果表明，统计频率算法能够弥补这些不足，在文本分类 中表现出了良好的分类效果。 在文本分类领域，本文在阐述几种常见的分类算法后，重点分析了k 近邻 ( 1 【- n e a r e s tn e i g h b o r ，呵算法。经典k n n 算法在文本分类中表现出了较高的分类 准确率，应用较为广泛。但是经典k n n 易受k 值选择和训练文本分布的影响，使 分类结果偏向于文本数较多的一类。本文对k n n 算法进行了优化，实验结果表明， 基于统计频率及改进的k n n 算法能够减少样本库对分类效果的影响，改善了分类 性能。 关键词：文本分类；特征选择；l 心烈；z 2 统计量 a b s t r a c t w i t ht h ed c v e l o p m e n to fw w w ，t h em m l b e ro f 。d o c u m e n t so nt h eh l t 锄e tl n c r e 勰e s s w i f t l y 锄dv i 0 1 e i l t l y i t sad i 伍c u h yt 嬲kf o ru s e r st 0f i n du s e m li n f o n n a t i o nw i t hr a p i d p r e c i s i o n 觚de 1 【t i r e i i lt h ei n f o m a t i o n a lo c e a n h o wt oo 玛a i l i z e 锄dm a n a g ed a t a e 舵c t i v e l yf o ru s e r s ? h o wt 0d i s t i n g u i s hi i l f o m a t i o nb e 俩e e i lu s e m la n dm a l u a b l e ? h o wt 0f e t c hu s e m li n f o m l a t i o ne 伍c i e n t l yf 0 姗m e s eg r e a tc 印a c i t i e so fd o c u m e n t s ? h o wt 0m e e tt h er e q u i r 锄e n to fi i l d i v i d u a l i z a t i o n ? i ti sac h a l l e n g i n gs u b j e c tf o rp e o p l e t 0d e a lw i ma ht h e s eq u e s t i o i l s a u t o m a t i ct e x tc 1 硒s i f i c a t i o ni st 0s o r td o c 啪e n t st 0o n eo rm o r ec a t e 9 0 d e s a u t o m a t i c a l l y i tp l a y sa ni i i 州a n tr o l ei nt e x tm 缸i n g 缸l d d o c u m e n tm a n a 咎m 朗t i tc 孤 r c s o l v et h ed i s o r d e ri i l f o m a t i o nf o mal a 唱ee x t e n t ，u s e r sc 觚f i n dt h eu s e m l i 0 m a t i o n c o n v e i l i 饥t l y h lm ef i e l do ft e x tc l a u s s i f i c a t i o n ，t h e r ea r et w of a c t o r s f e a l l l r es e l e c t i o n a n dt e x tc a t e g o r i z a t i o na 1 9 0 d t h mi n n u e i l c em ep e r f o 彻a i l c eo fm ec l a s s i f i c a t i o n t h e f e a n l r es e l e c t i o ni sa b o u t 丘n d i n gu s e f h l ( r e l c v 肌t ) f i e a n 胎st od e s c 曲e 觚a p p l i c a t i o n d o m a i l l s e l e c t i n gr e l e v 锄t 锄de 1 1 0 u g l lf e a n 鹏st 0e 虢c t i v e l yr 印r e s e i l ta n di 1 1 d e xm e 西v e i ld a t a s e ti s 锄i m p o n a i l tt 嬲kt 0s o l v et l l ec l a s s i f i c a t i o n 觚dc l u s t e r i r 培p r o b l c m s i n t e l l i g e n t l y ag o o df e a t u r es e l e c t i o nm e t h o dc 觚f i n dt l l e s m a l l e s tf e a t l l r es c tt 0 r 印r e s e n tt l l ei n d e x e so fa 百v e l ld a t 弱e t ，i m p r 0 v et h ee m c i e i l c ya l l da c c u r a c yo ft h e c l a u s s i f i c a t i o n af a v o r a ：b l et e x tc a t e g o r i z a t i o na l g o d t h mi sb 雒i cf o rt e x tc l a s s i f i c a t i o n c 1 1 i s q u a r ca l g o d c l l m ( c h ii ns h o n ) i sai m p o r t a n tm e t h o do ff e a t u r es e l e c t i o r 塔，l i s a l g o r i l i i l c a l c u l a t ea 1 1 p o s s i b i l i 哆o ff e a t u r e s a n dc a t e 9 0 r i e s ， s h o w ss a t i s f 缸t o 巧 p e r f o 姗a 1 1 c ei i lt e x tc a t e 9 0 r i z a t i o n b u tt h e r ea r ee x i s ts o m ed e f e c t s n sl l i l r e l i a b l ef o r 1 0 w d o c 啪e n t 舭q u e n c y ，锄di td i d i l ts ：h o wm ep e n i i l e n c ef o rt e 咖肌dc l 弱s i f i c a t i o n 1 l l i sp a p e rf i r s t l yi 劬d u c e st h ep o p u l a rm 甜l o d so ff e a t u r es e l e c t i o n s ，t 1 1 e i la 眦1 w s t a f t i s t i c a lf r e q u e n c ya 1 9 0 r i m m ( s fi ns h 0 哟i sp r o p o s e da c c o r d i n gt 0t l l ec l l i e f s h o r t c o m i n g s t l l ee x p 嘶m 饥t so fm es fa l g o r i i sv a l i 眦e d b yc o m p 耐s o i l ，t h e r c s u l t ss h o wt h a ti m p r 0 v e da 1 9 0 r i t h mp e 响衄sw e l l h lt h ef i e l do ft e x tc 1 雒s i f i c a t i o n ，t h i sp 印c rf i r g t l y 砷d u c e s 坨p o p u l a ra 1 9 0 r i 饥 n s o ft e x tc l a s s i f i c a t i o n ，a n dl a yh e a v ys n s so nk - n e a r c s tn e i 曲b o ra l g o r i m m ( 町ni l l s h o n ) ，w t l i c hs h o w s 铲e a tp r e c i s i o ni nt e x tc l a s s i f i c a t i o i l ，u s e sp o p u l a r l y b u tk n n i s i i v e 巧s e i l s i t i v et 0t 1 c h o i c eo f t 1 1 ep a r 锄e t e rka i l dt h ec l a s sd i s t r i b u t i o no ft h e 仃a i l l i i l g s e t ，m a l 【e st l l er e s u l tp r e f 打t 0a l el a r g e rc l a s s h l 嘶sp a p 锄i m p r 0 v e dk n e a r e s t n e i g h b o r ( k n i sp r o p o s e d i t sp r o v e dm a tt h ei m p r 0 v e dc h i a n dk n na l g o r i 恤m s h e l pr e d u c i n gt h e1 1 1 i s c l a s s i f i c a t i o i l ，a n di m p r 0 v et h ep e 墒咖a n c e s i l le x p e r i m 咖s k e yw b r d s ：t e x tc a t e g o r i z a t i o n ；f e 抓鹏s e l e c t i o n ；州；c h i - s q u a r e l i i 硕士学位论文 m a s t e r st h e s l s 1 1 研究意义 1 绪论 i n t e r n e t 信息量的迅猛增加，增加了人们获取有效信息的难度，而且信息产 生的速度远远超过人们收集信息、利用信息的速度，使得人们无法快速地查找到最 新的信息，从而造成了时间、资金和精力的巨大浪费。面对网上海量的信息，传统 的做法是对网上信息进行人工分类，并加以组织和整理，从而为人们提供一种相对 有效的信息获取手段。但是，这种人工分类的做法存在着许多弊端，不仅耗费大量 的人力、物力和财力，而且存在着分类性能不佳的问题。因此，如何有效的组织和 管理数据，方便人们的检索? 如何区分有用的信息和无用信息? 如何从海量的数据 中高效地获取有用知识? 如何满足用户的个性化需求? 所有这些都成了人们亟待 解决的问题。 文本分类( t e x tc a t e g o r i z a t i o n ) 是指在给定的分类模型下，将用自然语言表 示的文本，根据其内容，自动地确定该文本所属的一个或多个类别。其实质是一个 知识学习和应用的过程，首先，分类器根据学习每个类中若干样本的数据信息，总 结出各个类别的规律性，并建立起判别公式和判别规则，这是知识学习过程；然后， 在遇到新文本时，分类器根据总结出的判别规则，确定新文本所属的类别，这是知 识应用的过程。文本分类技术在人们的生活中起着越来越重要的作用，并得到了空 前的发展，在垃圾邮件过滤、邮件自动分类、网页搜索、网页分类、信息组织、信 息推送、数字图书馆的数字化管理等领域具有极高的研究价值和广阔的应用前景。 在文本分类中，把文本表示为向量空间的形式时，训练文本集中的特征项可能 多达数万个。这些特征词中，只有少数词对实现正确的分类有贡献，而大多数词对 分类并无贡献，且过多的特征词会导致样本统计变得更加困难，高维向量的处理具 有极高的计算复杂度，极易产生“维数灾难 的问题。因此，如何保留那些对分 类起着重要贡献的特征，去除那些冗余的特征，以减少特征词总数，即如何进行特 征选择，已成为一个日益重要的研究领域。 2 z 统计量( c h i s q u a r c ，c h i ) 是一种重要的特征提取算法，它的主要思想是： 2 认为词条与类别之间没有独立性，并可类比为一个自由度的z 分布，z 统计量的 值越高，词条和类别之间的独立性越小，相关性就越强。这种算法考虑了特征与类 硕士擘位论文 m a s t e r st h e s i s 别出现的各种可能性，在实验中表现出了良好的分类效果和稳定性，但是也存在很 多的缺陷和不足。本文对其优缺点进行详细分析，并提出改进以弥补其不足，最后， 本文通过实验证明，改进的特征选择算法，能较大的提高文本分类性能。 文本分类算法能建立从文档特征到文档类别之间的映射关系，是文本分类的核 心问题。常用的方法有朴素贝叶斯( n a 如eb a y e s ，n b ) 、k 近邻( k - n e a r e s tn e i 9 1 1 b o r ， 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，s ) 等。其中k n n 算法应用最为 广泛，k n n 算法的基本原理为：给一篇待测文本，系统在训练集中找到与之最相 似的k 个近邻，k 个近邻文档中多数属于哪一类，就把待测文档归为哪一类中。经 典k n n 算法因为其具有思路非常简单直观，易于实现，分类效果不错，正确率很 高，具有较强的稳定性，通过训练样本来自动学习分类规则，不需要领域专家的参 与等优点得到了广泛的认可和应用。但同时l ( n n 算法也存在一些缺陷，如在分类过 程中相似度计算量过大、对样本库过于依赖等问题。本文主要针对k n n 算法的这两 个缺点进行改进，使其达到更好的分类效果。 1 2 国内外研究现状 文本分类的理论研究可以追溯到2 0 世纪6 0 年代初，其发展过程大致可以划分 为三个阶段： 第一阶段是2 0 世纪6 0 年代前。在这一时期，主要是分类理论的研究，并将文 本分类应用于信息检索。在这一时期，提出了很多经典文本分类的数学模型。如 m a r o n 和k u h n s 提出概率标引( p r o b a b i l i s t i ci n d e x i n g ) 模型，并将其应用于信息 检索中；s a l t o n 提出利用向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 对文本进行描 述等等。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用传统的知识工程技术，根据 专家提供的知识形成规则，手工建立分类器。这一时期，信息检索技术逐渐成熟应 用，为文本分类提供了许多技术支持，最著名的信息检索系统是s a l t o n 的s m a r t 系统。r o c c h i o 在1 9 7 1 年也提出了在用户查询中不断通过用户的反馈来修正类权重 向量，来构成简单的线性分类器。v a nr i j s b e r g e n 提出了信息检索的评估标准如准 确率、查全率等。 第三阶段是2 0 世纪9 0 年代以后。在这一时期，文本分类的主要特点是采用统 计机器学习方法，自动建立分类器，学习和分类过程来自于机器对训练文本的自主 学习，从而不需要领域专家的支持，不需要人工干预，而分类效率和准确率得以提 高。如1 9 9 2 年，l e w i s 在他的博士论文中提出了标准数据集r e u t e r s 2 2 1 7 3 ，并在 2 硕士学位论文 m a s t e r st h e s i s 此数据集上进行了实验测试；y a n gy i m i n g 对各种特征选择算法进行了分析比较， 讨论了文档频率( 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 ) 、 互信息( m u l t i i n f o r i i l a t i o n ，m i ) 和c h i 等方法，结合k n n 分类器，得出i g 和c h i 方法分类效果相对较好的结论，对后来的研究起到了重要的参考作用。新加坡的 h w e et o un g 等人研究了用p e r c e p t r o nl e a r n i n g 的方法进行文本分类，使用了一 种树状的分类结构，其准确率达到7 3 3 。 随着研究的深入，文本分类问题被进一步细化，如：分类算法，特征降维，性 能评价，样本学习，分类性能推广等，专家们试图从多个方面提高文本分类的效果。 在此，本文主要是对文本特征选择算法、分类器及k n n 算法进行改进。 文本特征描述一般采用基于内容的向量空间模型表示。它是从文本中抽取信息 来表示文本内容，并从大规模语料库中发现能表示文本类别的词汇，利用统计原理 和文本在一些特征项集合上的分布规律，对文本进行分类。对文档分类来说，关键 问题之一就是降维，降维技术是利用某种评价函数来保留这些具有分类能力和描述 能力的特征词，过滤掉弱信息特征词，并提取出最少的、最能表达文章主题的词作 为特征词汇。降维的方法，有特征选择( f e a t u r es e l e c t i o n ，f s ) 和特征提取( f e a t u r e e x t r a c t i o n ，f e ) 两类，本文主要介绍特征选择算法。 特征选择一般是利用某种评价函数独立地对每个原始特征项进行评分，然后将 它们按分值的高低排序，从中选取若干个分值最高的特征项。选择并没有改变原始 特征空间的性质，只是从原始特征空间选择了一部分重要的特征，组成一个新的低 维空间。评价函数的好坏是影响特征选择的关键问题。目前比较成熟的特征选择方 法主要有：文档频数、信息增益、期望交叉熵( e x p e c t e dc r o s se n t r o p y ，e c e ) 、 互信息、文本证据权( w e i g h to fe v i d e n c ef o rt e x t ，w e t ) 、z 2 统计量等。 特征提取的基本思想是利用映射( 或变换) 的方法把原始特征项集映射到较低 维的空间中，映射后的特征叫二次特征，它们是原始特征的某种组合( 通常是线性 组合) 。常用的特征提取方法有：主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 、 f i s h e r 线性判别分析( f i s h e rl i n e a rd i s c r i m i n a t ea n a l y s i s ，f d a ) 、潜在语义索 弓i ( l a t e n ts e m a n t i ci n d e x ，l s i ) 等。 文本分类是按照预先定义的主题类别，为文档集合中的每个文档确定一个类 别。这样用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查 找更容易、快捷。文本分类可以在较大程度上解决目前文本以及网络上信息杂乱的 现象，方便用户准确地定位所需的信息和分流信息。因此，文本自动分类己成为一 项具有较大实用价值的关键技术，是组织和管理数据的有力手段，可被用于垃圾邮 硕士学位论文 m a s t e r st h e s i s 件过滤、邮件自动分类、网页搜索、网页分类、信息组织、信息推送、数字图书馆 的数字化管理等领域中。 目前，分类器的构造方法有多种，主要有机器学习方法、基于规则的方法等。 基于机器学习的英文自动分类已经取得了很好的成绩，如回归模型、k 近邻、贝叶 斯、决策树、推导规则、神经网络、支撑向量机等。 国外对文档分类技术的应用研究也己经开展了多年，其中较为成功的系统有麻 省理工学院为白宫开发的邮件分类系统、卡内基集团为路透社开发的c o n s t r u e 系 统，s a l t o n 的s m a r t 系统，l e w i s 采用了一个线性分类器，建立了o h s u m e d 、r e u t e r s 等标准的分类熟语料和统一的评价方法等。 国内在中文文本分类领域也进行了大量的研究，如中科院计算所的李晓黎、史 忠植等人应用概念推理网进行文本分类，召回率达到9 4 2 ，准确率达到9 9 4 。 中国科技大学的范众等人在i ( n n 、b a y e s 和文档相似性研究的基础上提出了一个超 文本协调分类器，正确率接近8 0 9 6 ，它的一个特色是适当考虑了h t m l 文本中的结构 化信息，并且将文本分类器和超文本结构信息分类器结合起来，从而达到更好的效 果。但由于语料和评价方法各不相同，很难对它们做出严格的比较。在国内文本分 类和过滤领域里，复旦大学黄萱菁等人设计的文本过滤系统很值得一提，它主要针 对英文，能够通过特征抽取和伪反馈建立初始的过滤模板，并设置初始阈值，在过 滤阶段，则根据用户的反馈信息自适应地调整模板和阈值，并且该系统在2 0 0 0 年举 行的第9 次文本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，t r e c ) 的评测中取得了很 好的效果，自适应过滤和批过滤的平均准确率分别为2 6 5 和3 1 7 ，在来自多个 国家的1 5 个系统中名列前茅，获得自适应过滤第3 名和批过滤第1 名的好成绩。 关于文本分类算法k n n ，目前，大多学者主要从三个方面进行改进，分别是减 少训练样本的存储量、加快k 个最近邻的搜索速度和调整k 值的选择。 当训练样本集过大时，为了减小计算开销，可以对训练文本进行编辑处理，即 从原始训练样本集中选择最优的参考子集进行k 个最近邻寻找，从而提高计算效率。 这种途径主要的方法是h a r t 的c o n d e n s i n g 算法、w i l s o n 的e d i t i n g 算法和 d e v i j v e r 的m u l t i - e d i t 算法，另外k u n c h e v a 使用遗传算法在这方面也进行了一些 研究。 有的学者是采用加快k n n 搜索速度的算法，使之在尽量短的时间内找到k 个最 近邻文本。在进行搜索时不是盲目迭代，而是采用一定的方法加快搜索速度或减小 搜索范围，例如构造交叉索引表，利用匹配成功与否的历史来修改样本库的结构， 使用样本和概念来构造层次或网络来组织训练样本。此类方法主要可分为三类：空 4 硕士学位论文 m a s t e r st h e s i s 间数据分区方法、以扫描作为基础的方法和线性化方法。如香港中文大学的w a il 锄 等人将k n n 方法和线性分类器结合，取得了较好效果。 k 值的选择主要有两种方法：( 1 ) 通过大量独立的测试数据、多个模型来验证 最佳k 值的选择；( 2 ) k 值可以事先确定，也可以动态变化，例如采用固定的距离 指标，只对小于该指标的样本进行分析。本文针对k n n 算法的样本数量不平衡的情 况，提出对k n n 算法进行优化，使k 值能够自适应与文本分类规模。 1 3 本文的组织结构 本论文的组织结构如下： 第一章：本文阐述了文本分类的研究意义和应用前景，对国内外特征提取和文 本分类算法的研究现状进行了分析归纳，提出了本文的主要研究内容。 第二章：首先提出了基于向量空间模型的文本分类流程图，并指出了其主要功 能模块，阐述了基于向量空间模型的文本分类系统流程图。 第三章：分析和比较了多种特征选择算法，研究了特征选择在文本分类中的作 用，针对z 2 统计量算法的缺点和不足，对其进行了改进，并提出了统计频率算法。 第四章：阐述了现有的分类算法，对l ( n n 算法的原理、优点和缺点进行了深入 分析，针对它对训练文本的依赖性过强等问题，对其进行了优化，并给出了算法的 实现。 第五章：介绍了文本分类的评价标准，通过实验对本论文所提出的改进算法进 行分析、评估和验证。 第六章：总结本文的主要研究工作和创新点，并对未来工作进行了展望。 硕士擘位论文 m a s t e r st h e s i s 2 1 文本表示模型 2 系统流程设计与文本预处理 在当前的计算机技术的研究水平下，机器还不可能识别自然文本，从根本上说， 它只认识o 和1 ，所以必须将文本转换为计算机可以识别的形式。而要想让计算机 “读懂”文本，必须能够找到用于文本表示的数学模型。随着信息检索技术的发展， 逐渐发展起来的主要有三个文本检索模型，分别是：布尔模型( b 0 0 1 e a i lm o d e l ，b m ) 、 向量空间模型( v c 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 ，p m ) ，这 些模型从不同角度使用不同的方法处理特征加权、类别学习和相似度计算等问题， 而最经典、最实用的是向量空间模型，本文的研究是建立在向量空间模型之上的。 向量空间模型是由s a l t o n 在2 0 世纪6 0 年代末提出的，它最早应用于信息检索 领域，例如著名的s m 6 衄( s y s t e mf o r t h em a i l i p u l a t i o na n dr e t r i e v a lo f t e x t ) 系统 就成功的应用了向量空间模型技术，后来又在文本分类领域得到了广泛的应用。向 量空间模型的基于两个基本假设，一是文档所属的类别仅与某些特定的词或词组在 该文档中出现的频数有关，而与词或词组在文档中出现的位置或顺序无关；二是假 设文档的各特征词之间是相互独立的。这样，只需要提取出一份文档中蕴涵的各个 特征词的词频信息就可以对其进行正确的分类。 向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一致， 并可以通过向量空间进行描述。下面介绍文档向量空间的一些基本概念： 文本：泛指一般的文献或文献中的片段( 段落、句子或句子组) ，一般指一篇 文章( 假设文档中不包含除文字以外的其他多媒体信息) 。 特征项：文本的内容特征常常用它所含有的基本语言单位( 字、词、词组或短 语) 来表示，一般中文中使用词语作为文本的特征项。 特征项的权重：对于含有，1 个特征项的文本d ( f | ，f 2 ，乙) ，常用一定的权重心表 示特征项乙在文本d 中的重要程度。 即把文本表示为( 吐，d ：，d 。) ，特征词表示为( ，f 2 ，) ，特征词的权重表 示为( ，) 。这样自然语言形式的文本文档就可以在向量空间中完全由特 6 硕士学位论文 m a s t e r st h e s i s 征向量来表示。 对两个文本喀和以之间的内容相关程度的度量被称为相似度跏( 西，乃) ，可 以用如下公式计算。 s i m ( 珥，嘭) = 耐 喙 七= l 其中， 聊为特征向量的维数尼，表示第f 个文本的第七个特征项的权重值。 向量空间模型的主要优点在于：( 1 ) 标引词加权改进了检索效果；( 2 ) 其部分 匹配策略允许检出与查询条件相接近的文献；( 3 ) 利用余弦公式，根据待测文献与 训练文献之间的相似度对其进行排序。与其他的检索模型相比，向量空间模型简单、 便捷，而且分类性能也非常好，已成为当今最流行的检索模型。 2 2 系统流程设计 文本分类系统的工作流程是：首先对文本进行预处理，将文本用向量空间模型 表示，进行特征提取；然后构造分类器，最后用分类器对新文本进行分类( 见图2 1 ) 。 其具体步骤如下： ( 1 ) 利用字符编码转化系统，将所有文字转化为删c o d e 编码统一处理，初始 化系统的主词典、同义词词典和停用词词典。 ( 2 ) 对训练文本经过文本预处理，特征提取后，进行分类，构建训练集数据 库。 ( 3 ) 利用词典对训练文档进行词条切分和词频统计，并根据词频分布生成各 文档类的特征向量。 ( 4 ) 读入待分类文档，进行分词和新词提取，然后提取其特征向量。 ( 5 ) 计算待分类文档向量与各文档类向量的相似度，根据相似度确定文档的 类别。 7 硕士擘位论文 m a s t e r st h e s l s 2 ；萋雾雾薹蚕蓁 羹萋。i 掣墓菩茸季娥鋈 冀垂。l 馔鉴辩掣癯圜 聚驶垮霎们几乎囊删虽射哥摧俳；塑薹野犁影翱出翥必副剥i 吼弼铆麒隙 翔悔强捐丽月嘶探否堪悃僵悃陋i 翘蹶舍棼啦譬要薹蝼硝毯鞫型二鲫 驯鞠塑幕孽 燮翟，冀囊萼主錾皂爵乔囊萋霪蓁熏奏丁 蚕髂耀萋囊：蠹孽薹鋈要岳型涤bj 裂莲蓬荫冁濮瀑耸 蒂瞰薹雀盛耋? 频率 等信息，以便用于后面的权重计算和特征选择。 识别阶段根据句中位置和b i g r a m 信息动态识别停用词，而不仅仅依赖静态停 用词表。实验表明：这一方法具有较好性能，不使用停用词过滤的小样本分类准确 率只有6 0 多，而使用停用词表对文本词过滤后分类的准确率达到7 0 多。过滤停 用词后，系统处理的语句词语相对较少，减少非信息内容的停用词语干扰检索效果， 同时应注意，作为文本信息分类的基础工程，停用词过滤必须谨慎，以免错误过滤 有效词语，影响正确结果的检出。 2 3 4 统计词频 最初的向量表示完全是0 、1 形式，即如果一篇文本中出现了该词，那么文本 向量表示中的该维为1 ，否则为o 。显然，这种简单的表示方法无法体现这个词在 文本中的重要程度。所以o 、1 形式逐渐被词频所替代。词频分为绝对词频和相对 词频。绝对词频是指特征项在文本中出现的频率；相对词频为归一化的词频，其计 算方法主要是运用词频一逆文档词频( t e 瑚f r e q u e n c y i n v e r s ed o c u m e n t f r e q u e n c y ，t f i d f ) 公式。 硕士擘位论文 m a s t e r st h e s i s c d w s ：c d w s 分词系统是我国第一个实用的自动分词系统，由北京航空航天 大学计算机系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以 构词纠错技术。其分词速度为5 1 0 字秒，切分精度约为1 6 2 5 ，基本满足了词频统 计和其他一些应用的需要。这是汉语自动分词实践的首次尝试，具有很大的启发作 用和理论意义。 a b w s 是山西大学计算机系研制的自动分词系统，系统使用的分词方法称为 “两次扫描联想回溯 方法，用“联想回溯 来解决引起组合切分歧义。 系统词库运用了较多的词法、句法等知识。其切分正确率为9 8 6 ( 不包括非常用、 未登录的专用名词) ，运行速度为4 8 词分钟。 c a s s 是北京航空航天大学于1 9 8 8 年实现的分词系统。它使用的是一种变形的 最大匹配方法，运用知识库来处理歧义字段。其机械分词速度为2 0 0 字秒以上，知 识库分词速度为1 5 0 字秒( 没有完全实现) 。 书面汉语自动分词专家系统是由北京师范大学现代教育研究所于1 9 9 1 年研制 实现的，它首次将专家系统方法完整地引入到分词技术中。据报道，系统对封闭原 料的切分精度为9 9 9 4 ，对开放语料的切分精度达到9 9 8 ，在3 8 6 机器上切分速 度达到2 0 0 字秒左右。这个系统的理论意义是研究了歧义切分字段，剖析了汉语歧 义切分字段的性质，给出了当前基于句法和语义处理技术的歧义分析精度的上限， 但该系统由于结构复杂、知识库建造困难，不易维护、效率低，因此该系统未能广 泛流行。 清华大学早期s e g 分词系统：此系统提供了带回溯的正向、反向、双向最大匹 配法和全切分评价切分算法，由用户来选择合适的切分算法。经过封闭试验， 在多遍切分之后，全切分一评价算法的精度可以达到9 9 左右。 清华大学s e g t a g 系统：此系统着眼于将各种各类的信息进行综合，以便最大 限度地利用这些信息提高切分精度。通过实验，该系统的切分精度基本上可达到 9 9 左右，能够处理未登录词比较密集的文本，切分速度约为3 0 字秒。 复旦分词系统：此系统由四个模块构成，分别是预处理模块，歧义识别模块， 歧义字段处理模块和未登录词识别模块。系统对中文姓氏进行了自动识别，它利用 了中文姓名的用字规律、频率，以及姓名的上下文等信息。实验过程中，对中文姓 氏的自动辨别达到了7 0 的准确率。系统对文本中的地名和领域专有词汇也进行了 一定的识别。 哈工大统计分词系统：该系统是一种典型的运用统计方法的纯切词系统，它试 图将串频统计和词匹配结合起来。经测试，此系统的分词错误率为1 5 ，速度为 9 硕士擘位论文 m a s t e r st h e s l s ( 船) ：丝垡些型垒竺竺) _ ( 2 ) 瓣【矿( ，x ) 1 0 9 ( 惕+ o 0 1 ) 】2 其中，矽( f ，z ) 为词f 在文本x 中的权重，矿( f ，z ) 为词芒在文本x 中的词 频，为训练文本的总数，为文本集中出现芒的文本数。 另外，还有其他的t f i d f 公式，例如： 缈( ) ： 三型堕丝丝丝丝丝亏 ( 3 ) 础【l + 1 0 9 ：矿o ，x ) ) l o g ( ) 】2 可以看出，总的来说，两个公式都是基于这样一种思想：对区别文本最有意义 的词语应该是那些在少量文本中出现频率足够高，而在整个文本集合的其它文本中 的出现频率足够低的词语，这种思想也符合香农的信息学理论。本文利用常见的公 式( 1 ) 统计词频。 1 2 硕士学位论文 m a s t e r st h e s l s 3 1 特征选择算法 3 特征选择算法 3 1 1 概念和作用 特征选择是一个在分类聚类中都要解决的关键问题，对于样本文档，可能有成 千上万的特征，但并非所有特征都是有用的，即使去掉低频词和虚词等停用词后， 仍然会有数万维的特征留下。选择哪些特征将是一个很关键的问题，为了提高机器 学习的效率和精度，有必要降低文本向量空间的维数，而特征选择是文本降维的有 效方法。 特征选择是从特征向量集丁= 瓴，f 2 ，厶) 中选择一个真子集z = ( ，f 2 ，乙) ，满 足( 甩 b c 时，说明词条和类别正相关，词条出现说明某个类别也可能出现， 此时了统计量越大，文本中包含该词条时属于某个类别的可能性越大。然而，当b c a d ，也就是特征词在其他类别频繁出现而在指定类中很少存在时，计算出来的z 统 计量很高。这也是它的不足之处，它提高了在指定类中出现频率较低而普遍存在于 其他类的特征项在该类中的权重。因此，即使两个词条对某类的z 。统计值相同，但 对于某个文本而言，该特征词在该文本中，是否属于这一类，可能结果完全相反。 针对z 统计量存在的这两个问题，本文进行了改进，并提出了统计频率算法。 首先，在公式中引入频率的概念。正如刚才讨论所知，z 统计量对于低频特征 项不可靠。本文是基于如下想法：在某一类文本中出现次数越多的特征项越能代表 这类文本，因此选择在同一类文本中出现频度最高的若干特征项作为该类文本的类 别特征。设训练文本集中类别为c ，的文本有d ，l ，d 加，特征，在文本d 肚( 1 七优) 硕士擘位论文 m a s t e r st h e s i s 中出现的频度为娠，则特征项f 在类别c ：，中出现的频度( f r e q u e n c y ，用f 表示) 其次，对于z 2 统计量的第二个问题，本文也稍作改进，改进的z 2 统计量不仅 能够表示出词条对某个文本类的类别贡献程度，也可表示出改词条和这个文本类别 的相关性。改进的z 统计量的计算方法如下： 矿咖丽蒜瑞， 综合以上两个方面，本文提出了改进，改进后的最终公式表示如下： 蹶，2 丽稍筹赫善c ， 、 ” ( 彳+ c ) 幸( b + d ) 木( 么+ b ) 半( c + d ) 。、智“p 。( 】3 ) 为了区别原有的z 统计量算法，本文将改进后的c h i 称之为统计频率 ( s t a t i s t i c a lf r e q u e n c y ，s f ) 算法。统计频率算法引入频率的概念，使得在计 算特征项的z 统计量时考虑了特征项在文档内的出现频率，解决了z 统计量算法 对低文档频特征项不可靠的问题；另外，s f 算法具有正负两个值，能够更好的表现 词条和类别的相关性。 1 9 硕士擘位论文 m a s t e r st h e s l s 4 1 文本分类算法概述 4 文本分类算法 文本分类系统就是按照文本的主题以及事先制定的类别系统地将具体的文本 划归适当类别的计算机系统，有时也称作分类器( c l a s s i 丘e r ) 。 文本分类算法是设计实现分类器的理论基础也是研究超文本分类的理论基础。 分类方法大部分来自于模式分类，基本上可以分为两大类。一种是基于统计的方法， 如简单贝叶斯，k 最近邻方法、类中心向量( 也称为中心法) 、回归模型、支持向 量机等方法；还有一种是基于规则的方法，如决策树( d e c i s i o nt i r e e ，d t ) 、粗糙集 ( r d u g l ls e t s ，r s ) 等，这些方法的主要区别在于规则的获取方式。下面将简单介绍文 本分类的几种典型的分类算法。这些分类算法的理论基础，实现形式各不相同，算 法的性能各异，有各自的特性。 4 2 常见文本分类算法 4 2 1 基于统计的文本分类算法 基于统计的方法包括有中心法、朴素贝叶斯、支持向量机、神经网络和k 近邻 算法等。 ( 1 ) 中心法 中心法是一种非常简单而比较有效的分类算法。它基于向量空间模型，其训练 与分类速度很快，并且分类效果不错，因此在文本分类中得到了广泛的应用。在分 类阶段，对于某一给定的文档d ，计算文档和每个类别中心向量的相似度，然后按 相似度进行从大到小排序。相似度最大值所对应的类别，就是文档的所属类别。如 果希望文档可以属于多个类别，可以定义一个阈值，文档属于相似度超过阈值的所 有类。 ( 2 ) 朴素贝叶斯 朴素贝叶斯( n a j c v eb a y e s ，n b ) 是一种简单的线性分类器。它在