（计算机应用技术专业论文）基于改进向量空间模型的邮件分类.pdf

摘要 电子邮件在当今已经成为人们联系交流不可缺少的通信工 具，但用户每天都需要花费大量的工作时间对众多邮件进行整理。 因此，研究邮件的自动归类具有重要意义，目前邮件自动归类有 基于统计和基于规则两类。本文主要研究的是基于统计的分类。 本文对电子邮件分类系统中所有必要的构成阶段进行了研究， 包括训练阶段和分类阶段，并给出了在两个阶段中经常采用的技 术。这些技术主要有邮件表示、特征选择与提取、分类技术等。在 这些技术中本文主要讨论了邮件的表示方法，着重分析了基于向量 空间模型的表示形式。 基于统计的邮件分类一般采用向量空间模型来表示邮件，该模 型将邮件表示成为向量形式，将对邮件内容的处理简化成了对向量 空间中的向量进行运算，从而使模式识别和其他领域的计算方法能 够在自然语言文本处理中运用，得以实现对邮件的可操作性和可计 算性。但是该模型并未考虑到词所在邮件的结构特征，影响了分类 的精度。 针对向量空间模型存在的缺点，本文的系统借助粘合性衡量方 法提取n g r a m 的思想，对向量空间模型进行改进，提出了计算词 权重的一种新方法。这种方法以段落为邮件的最小分块，将邮件内 容视为一个n - g r a m ，段落视为n - g r a m 中的单词，并结合段落问的 逻辑关系计算词的权重。它不仅没有打乱邮件内容的顺序性，而且 也较好地体现了邮件的结构特征，这使得系统在发挥向量空间模型 优势的同时，也能够提高分类的精确度。 本论文的实验证明，采用改进向量空间模型的邮件分类系统与 采用传统的向量空间模型算法相比，在分类的精度上有了明显提 高，从而有效地改善了分类的性能。 关键词自然语言处理，邮件分类，向量空间模型，粘合性衡量 a b s t r a c t n o w a d a y s e m a i lb e c o m e sac o m m u n i c a t i o nt o o lw h i c hi se s s e n t i a l t ot h ep e o p l e b u ti tt a k e sc o n s u m e r sl o t so ft i m et o a r r a n g ee m a i l s t h e r e f o r e i ti si m p o r t a n tt os t u d ya u t o m a t i ce m a i lc l a s s i f i c a t i o n a t p r e s e n t a u t o m a t i ce m a i lc l a s s i f i c a t i o n c o n t a i n st w om e t h o d s ：o n ei s b a s e do nr e g u l a t i o n ，t h eo t h e ri sb a s e do ns t a t i s t i c h e r e ，i tm a i n l ys t u d i e s t h es t a t i s t i cm e t h o d t h i sp a p e rh a ss t u d i e dt w os t a g e st h a ta r en e c e s s a r yi ne m a i l c l a s s i f i c a t i o n ，i n c l u d i n gt r a i n i n gs t a g ea n dc l a s s i f i c a t i o ns t a g e i th a sa l s o s t u d i e dt h et e c h n o l o g i e sw h i c ha r eo f t e na d o p t e di nt h e s et w os t a g e s t h e s et e c h n o l o g i e sc o n t a i ne m a i l e x p r e s s i o n 、f e a t u r es e l e c t i o n a n d e x t r a c t i o n 、c l a s s i f i c a t i o na n ds oo n a m o n gt h e s et e c h n o l o g i e st h i sp a p e r m a i n l yd i s c u s s e st h ee m a i le x p r e s s i o na n da t t a c h e si m p o r t a n c et ot h e v e c t o rs p a c em o d e l ( v s m ) e m a i lc l a s s i f i c a t i o no f t e nu s e sv s ma sat o o lt or e p r e s e n te m a i l t h i sm o d e le x p r e s s e st h ee m a i li nav e c t o rf o r m , w h i c hc a l lo n l yc a l c u l a t e t h ev e c t o ri n s t e a do ft h ee m a i l sc o n t e n t a sa r e s u l t ，m e t h o d si np a r e m r e c o g n i t i o na n do t h e rf i e l d sc a nb e u s e di n t o t h en a t u r a ll a n g u a g e p r o c e s s i n g ，a l s ot h ee m a i lc a nb eo p e r a t e da n dc a l c u l a t e d b u tt h ev s m i g n o r e se m a i l ss t u c t u r e ，w h i c ha f f e c t st h ep r e c i s i o no fc l a s s i f i c a t i o n i na l l u s i o nt o s h o r t c o m i n g s o ft h ev s m ，an e wm e t h o dt h a t c a l c u l a t e sw o r d sw e i g h ti sp r o p o s e d ，w h i c ha d o p t st h ei d e at h a tu s e sg l u e m e a s u r et oe x t r a c tn - g r a m s t h em e t h o dt a k e sp a r a g r a p h sa su n i t s ，t a k e s e m a i l sc o n t e n ta san g r a m ，t a k e sp a r a g r a p h sa st h ew o r d si na n g r a m ， c o m b i n e sl o g i c a lr e l a t i o n sb e t w e e np a r a g r a p h st oc a l c u l a t ew o r d sw e i g h t t h i sm e t h o dn o to n l yd o e sn o tu p s e te m a i lc o n t e n t so r d e rb u ta l s o e m b o d i e st h ef e a t u r eo fe m a i l ss t r u c t u r e i tc a nb r i n gt h ev e c t o rs p a c e m o d e la d v a n t a g ei n t op l a y , a l s oi tc a ni m p r o v et h ep r e c i s i o no f c 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 lr e s u l t si nt h i sp a p e rp r o v et h a tt h em o d i f i e dv e c t o r s p a c em o d e la l g o r i t h mn o to n l yi m p r o v e st h ea c c u r a c yo fc l a s s i f i c a t i o n b u ta l s oi m p r o v e st h ep e r f o r m a n c eo fc l a s s i f i c a t i o n ，c o m p a r e dw i t ht h e t r a d i t i o n a lv e c t o rs p a c em o d e l k e yw o r d sn a t u r a ll a n g u a g ep r o c e s s i n g ，e m a i lc l a s s i f i c a t i o n ，v e c t o r s p a c em o d e l ，g l u em e a s u r e 1 1 1 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名： 江 日期：与l 年工月 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 储虢牡导师虢斟期：4 年王月粤日 硕士学位论文第一章绪论 第一章绪论 本章主要对本论文的研究对象作了一个总体的介绍，包括邮件分类的概念、 研究背景，并从国内外两个方面对邮件分类的发展历程进行了探讨，在此基础上 论述了本文研究的主要内容和论文的结构布局。 1 1 研究背景 随着i n t e m e t 的快速发展，电子邮件正逐步地取代传统的邮递方式，成为人 们快速通信的一种方法。通过电子邮件系统，用户可以与世界上任何一个角落的 网络用户进行经济、方便和快捷的信息交流，这些电子邮件可以是文字、声音、 图象等各种方式。同时，用户可以得到大量免费的新闻、专题邮件，并实现轻松 的信息搜索，这是任何传统的邮递方式无法相比的。正是由于电子邮件的使用简 易、投递迅速、收费低廉、易于保存、全球畅通无阻，使得电子邮件被广泛地应 用，它使人们的交流方式得到了极大的改变。 但是电子邮件的普及使得用户每天都能接收到大量的邮件。据统计，一位普 通用户每天可以收到大约4 0 5 0 封邮件，有些用户每天甚至可以收到上百封。 同时接收到的邮件信息也是五花八门的，甚至可能还包括用户并不想接收到的大 量垃圾邮件，面对各种各样的邮件，用户不得不花费一定的时间来处理【”。随着 电子邮件成为人们交流的主要通信工具，阅读和回复邮件的时间将会增多，这势 必会给用户带来工作和生活上的许多不便。 面对邮件给用户带来的问题，邮件分类随之产生。它作为一种整理工具，是 人类文明发展到一定高度后的产物。它能帮助用户在众多的邮件当中准确、全面、 迅速地获取到自己关心的内容，大大提高了工作效率，从而减少了人力、财力、 物力在邮件处理上所造成的不必要的损失。 1 2 电子邮件分类概况 1 2 1 概念 邮件分类的方法目前主要分为人工分类和自动分类两大类团。人工分类主要 是指通过人工来对邮件进行分类。人工分类由于是人为进行操作的，一般对于海 量数据的处理，有时还需要大量熟练的相关领域内的专家进行参与。虽然分类精 度高，服务质量好，但是人为进行分类耗时、耗力，并且难以及时更新，维护也 硕士学位论文第一章绪论 较难。尤其是随着计算机的飞速发展，计算机成为了辅助人类认识和改造世界强 大的工具后，信息快速增多了，人工分类已远远不能满足现代社会发展的需求， 因此必须发展自动分类技术来适应这种变化。 邮件自动分类是指计算机根据邮件的内容，将其自动归到一个或者多个最适 合该邮件的类别中去。而自动分类包含多种研究方法1 3 1 ，在目前的研究阶段，自 动分类主要有自动聚类和自动归类两种。 自动聚类也称为无指导( u n s u p e r v i s e d ) 的分类，它的邮件类别是不确定的，是 从待分类对象中提取出特征，然后将提取出的全部特征进行比较，再根据一定的 要求，将具有相同或相近特征的对象归为一类。自动聚类不需要预先对邮件进行 分析，最后得出的邮件类别根据需要、标准、目的的不同而有所区别。自动聚类 一般有数值矢量法、图分法、逐步聚类法等。 自动归类，也称有指导( s u p e r v i s e d ) 的分类，需要预先定义类别体系，它是按 照一定的分类标准或者分类参考，预先确定好邮件类别，并且对每个邮件类别分 配一批预先分好类的邮件( 称为训练集) ，在训练阶段对训练集进行学习得到一定 的规则，在分类阶段，根据学到的规则来对待分类的邮件进行分类。根据实现技 术的不同，自动归类又分为基于规则的方法和基于统计学习的方法。 基于规则的分类方法一般适合于某个特定领域的研究，因为它是在知识工程 师和领域专家的帮助下，用规则将己知的知识和经验归纳出来再用于邮件的分 类。目前大多数电子邮件的客户端软件都提供了这种分类功能。它虽然在特定领 域具有良好的应用前景，但是要依赖语言学知识，需要编制大量的推理规则作为 分类知识。另外，由于网络上的数据是随着网络应用的变化而不断改变的，这种 分类方法要基于一种预先定义的知识库，这就意味着它不可能根据网络数据的变 化自适应地改变，因此存在着知识库更新慢，修改和移植都比较困难的局限性。 这种分类方法有时也被称作基于知识的分类方法。 基于统计学习的分类方法，忽略了邮件的语言学结构，只需提供一组相对 较少的手工分好类的训练邮件，就可以通过学习算法自动发现这些训练邮件中隐 藏着的分类特性，产生分类规则。它通过己知类别的训练集构造出分类函数或分 类模型( 分类器) ，并利用此分类模型将未知的文档映射到给定的类别空间，将邮 件分类问题视为一模式识别问题，实现起来比较简单，并且分类准确度也高，能 够满足一般应用的要求。 1 2 2 研究现状 由于邮件的正文是非结构化的文本文件，即没有较强的结构性，不能由程序 控制自动产生。因此，目前邮件分类方法大部分采用的就是文本分类方法，邮件 2 硕士学位论文 第一章绪论 分类是文本分类的一大应用之一。文本分类就是由计算机自动提取文本的特征 项，依据一定的算法，将文本按内容或属性归到一个或多个类别的过程。文本分 类从开始出现到现在，经历了从基于规则到基于统计的分类，再到规则和统计结 合的一个过程。在文本分类当中，一般致力于两方面的研究：一个是分类的预处 理，另一个分类决策【4 】。同样，邮件分类也主要着力于这两方面。 国外对电子邮件自动分类和文本分类问题的研究比较早。1 9 9 5 年l a n g 5 】就 运用r o e h i o 分类方法对新闻组进行了分类，设计的系统允许用户将网络新闻分 为5 个级别，然后运用设计的等级来训练r o c c h i o 分类方法，从而实现对新闻组 的分类。1 9 9 6 年c o h e n 忡1 提出了基于r i p p e r 规则的电子邮件自动分类方法，并 且在小样本集上进行了测试。这种算法容易使用，另外用户也可以进行规则的扩 展或修改。1 9 9 8 年t a k k i n e n 和s h a h m e h r i 7 】设计实现了一个概念模型，即电子邮 件分类助手。这个模型可以在邮件当中组织、检索和修改信息。它根据用户的需 要设计了三种运行模式，使得这些模式能够符合用户的一些用法习惯。同年， s a h a m i i s 等提出了用二项朴素贝叶斯分类器对一些垃圾邮件进行过滤，并且结合 垃圾邮件的特征人工合成一些新特征来对邮件进行过滤。1 9 9 9 年，j e f f e r s o n l 9 提 出贝叶斯分类器和基于r i p p e r 规则学习的两种电子邮件自动分类方法，在精确 度上，前者胜过后者。 2 0 0 0 年，d i a o 等【”】借助了文献【8 】中所构造的人工特征，并且将电子邮件头 部的结构特征也加入进去，分别使用朴素贝叶斯分类器和决策树分类器在一个大 型的电子邮件库上进行了测试。从实验结果中发现，这两种分类器都能够达到比 较理想的分类结果，决策树分类器在对特征集进行优化后分类效果更好一些。 2 0 0 1 年k i f i t c h e n k o 和m a t w i n 1 提出利用互相训练的方法，将未标签的数据和少 量已标签的数据结合起来对邮件进行分类。这种方法允许运用一些标签好的例子 来产生一个最初的弱分类器，而且仅仅运用未标签的数据来提高性能，该方法可 以克服只有少量标签数据的情况。2 0 0 3 年k a z e m 1 2 】等试着将本体运用到邮件分 类中，首先将邮件转变为c i i p s 实例的集合，它能够加载成一个同由p r o t e g e 产生 的定义和实例相结合的c l i p s 程序，这些规则能匹配从本体得到的类实例的邮件 实例。如果所有提出的预测都满足，则可从c l i p s 中输出每个邮件的特征，并根 据训练集计算出这些特征的关联概率，作为向量的一部分运用到贝叶斯分类器。 同年，n e n k o v a 和b a g g a i l3 】提出一种新的邮件分类方法，他们将分类系统分为两 部分：一部分用于邮件的区分，即区分邮件是单一邮件( 不需要立即回复的邮件) 还是根邮件( 需要立即回复的邮件) ，这样有利于辨别重要邮件；另一部分则是 对邮件的分类，这些邮件分为根邮件、内部邮件和叶子邮件。 2 0 0 4 年，a e r y 和c h a k r a v a r t h y1 1 4 j 提出使用图挖掘方法和频繁项集方法来对 硕士学位论文第一章绪论 邮件分类，在图挖掘方法中，将邮件表示成图形，在图产生之前，停用词需被去 除。在图中使用词的数目是由邮件体的长度决定的，从中选择具有代表性的子结 构，将子结构相比较得到分类。这种方法虽然比较新颖，但邮件的图表示以及子 结构的比较本身就是一个很复杂的问题。频繁方法则是基于一定的剪枝算法，从 频繁项集中获得一个文件夹中的具有代表性的项集，新邮件也被提取项集并与每 个文件夹中的项集相比较，具有最大相似度的文件夹则为该邮件所属类。2 0 0 5 年，w a n g 和i a nc l o e t e i l 副提出将邮件分到一个有层次关系的文件夹中，并可自 动地根据所收到的邮件来决定工作。l u o 等【1 6 l 采用了换位思考的方法，将本用于 分类的a d a b o o s t 算法运用于选择特征。它主要是将每个特征看成是一个弱假设， 每次的学习过程是为了辨别出具有最大区别度的特征。当学习过程完成时，一个 有影响力的特征空间是由一些可区别的特征组成，最后运用这些特征来实现对文 本的分类。z h u 等1 1 7 j 认为向量空间模型打乱了文本的最初结构并且忽视了文本的 句子，提出了用句子为基础来建立句子空间模型。在文本中选取n 个句子，并 计算每个句子对类的贡献程度，得到句子和类的关联矩阵，最后采用投票的方法 来得到文本的分类。这种方法比较新颖，但是并未考虑到词间关系问题。 国内也有学者在这方面进行了实验性的研究。2 0 0 0 年，林鸿飞等f 1 8 】通过分 析文本的结构来获得词的权重。文章首先将词映射到概念的层次，然后对文本进 行分层，结合词长和在段落中的频率来得到词在单元中的频率，从而对文本的结 构进行逻辑划分。2 0 0 1 年，华南理工大学的朱斌教授等【1 9 l 运用人工智能的有关 知识设计了一个电子邮件智能分类系统，对规则系统在算法上进行了改进，采用 机器学习的方法来实现知识自动获取，从而使得在系统中增加了智能的部分，提 高了系统的工作效率。2 0 0 3 年徐海涛等【2 0 1 设计了一个中文邮件分类器，采用了 基于中文文本的n g r a m 信息统计式分词法来对词进行分类，这种方法实现了与 词库的结合，同时也摆脱了对复杂切词处理程序的依赖。经过切词后，结合n a i v e b a y e s 分类器和决策树分类器来对邮件的类别作了评估。同年，何绍华和王非【2 1 】 在初步探讨了电子邮件系统处理信息过载的机制后，运用虚拟目录及建立在其基 础上的分类和检索机制来对邮件进行分类，该方法可以将同一个邮件在逻辑上同 一个或多个目录关联起来，而不需要将实际的邮件复制到目录中，从而可以节省 内存空间并有利于邮件的移动。 2 0 0 4 年，章成敏和章成志田j 提出基于知识库的电子邮件自动分类系统，先 从电子邮件文本信息中抽取概念词串，将概念词串与分类知识库的主题词串进行 词形匹配或语义相似度计算，给出对应的最佳分类号。这种方法在建立分类知识 库时就需要花费很多的时间。2 0 0 4 年宗平和田震生【2 3 1 提出了对邮件进行分级来 处理的思想，即将邮件按照重要程度分为第一、第二、每三、第四等级，系统根 4 硕士学位论文第一章绪论 据邮件的等级来做出相应的处理措施。这种方法虽然在一定程度上取得了较好效 果，但是在有些级与级之间的分界线并不是很清晰，从而对邮件的分类带来了一 些麻烦。 2 0 0 5 年，林夕伟1 2 4 】提出将本体运用到邮件分类中，使用“泛化发展”的方 法引入相应的背景知识，从而对电子邮件分类，该方法根据邮件的外在特征来从 本体中获得背景知识，然后再把知识运用到分类中去，但并未考虑到邮件的内容 与本体的结合。同年，邱科宁等【2 5 l 提出了一个基于a g e n t 的个性化邮件分类系统， 通过收集和分析用户的信息来了解用户的兴趣和习惯，从而得到用户的个性化需 求，并根据用户对分类的需求和邮件内容本身的特征来达到最终的分类目的。此 外，叶浩等【2 6 】提出了一种基于潜在语义的多类文本分类方法，当从原始空间中 获得潜在语义空间时，文中的方法不但尽量保留文档信息，而且还通过对文档信 息和类别信息建模，把文档和类别之间的关联也考虑进来。它首先计算了所有的 潜在变量对，然后按照文中给的步骤来得到分类结果。该方法的分类效果虽然比 较好，但是计算复杂度较高。余刚等【2 7 l 针对向量空间模型没有考虑词关系的问 题，提出了将词关系加入到向量空间模型中，从而实现对向量空间模型的改进。 文中首先以句子为基本单位，计算出两词在同一文档中的同现频率，然后将每个 词的同现频率与词在文档中的权重值进行结合从而得到了词的最终权重。2 0 0 6 年，王小伟和王黎明【2 8 】提出了动态人工免疫分类算法，即使用虚拟基因库技术 对用于邮件分类的人工免疫系统进行了改进，充分利用能正确分类的抗体，而对 于用于错误分类的抗体，进行体细胞高频变异，从而提高了整个系统的分类性能。 可见，在国内，人们也越来越关注对邮件分类的研究了。 1 3 论文研究的主要内容 通过对邮件分类的研究背景进行探讨，本论文把研究重心放在了邮件的表示 上面。因为只有采用较好的方法表示邮件，才能为邮件的分类打下良好的基础。 在邮件分类当中，一般采用向量空间模型来表示邮件。向量空间模型将邮件 表示成为向量形式，将对邮件的内容处理简化成了对向量空间中的向量进行运 算，有效地解决了文本数据在分类中的处理问题。但是该模型并没有考虑到词的 位置关系。它不但会使邮件损失大量的文本结构信息，而且向量空间模型对于结 构特性的忽略，会使得特征向量不能很好地表达邮件的内容。 针对向量空间模型所存在的缺点，本文提出一种计算特征权重的新方法。即 通过对电子邮件结构进行分析，根据段落在文档中的重要意义，以段落为邮件的 最小分块，充分分析了每个段落当中的内容，并借助粘合性衡量方法提取n - g r a m 硕士学位论文 第一章绪论 的思想，计算出词对邮件内容中的段落在体现同一主题时的贡献程度，从而对词 的权重进行赋值。运用这种方法设计一个邮件分类系统，并使用常用的几个评价 指标对分类结果进行了测试，最后通过测试结果对分类系统性能进行了评价。 另外，论文不但给出了电子邮件的格式，而且也对邮件分类的相关技术进行 了详细地介绍和分析，主要有邮件表示方式、特征提取和选择方法以及分类技术。 i 4 论文结构 本论文共分五章，内容安排如下： 第一章对论文的研究对象作了一个总体的介绍，包括邮件分类的概念、研究 背景和发展历程，并给出了本文研究的主要内容和论文的结构。 第二章探讨了开发邮件分类系统的相关技术，主要有关于邮件的表示方法、 邮件特征的选择与提取、邮件的分类技术和分类的评价指标。 第三章是本论文的重点章节，主要分析了向量空间模型在表示邮件内容时所 存在的优缺点，针对其缺点提出了一种新的改进算法，并对算法的来源和算法的 计算过程进行了详细地介绍。 第四章则是论述了系统实现与设计过程，主要对邮件分类系统的系统结构、 各个主要模块包括预处理、特征提取、训练算法、分类算法、评价方法等进行详 细介绍，以程序框图的形式描述了各模块的处理过程，并对各模块中比较重要的 函数作了介绍。 第五章对论文全文进行了总结，并对将来的研究方向进行了展望。 6 硕士学位论文 第二章邮件分类技术研究 第二章邮件分类技术研究 本章主要讨论邮件的表示方法，着重介绍了向量空间模型的表示方法，并给 出特征选择、提取方法以及在邮件分类中常用的几种分类技术，最后介绍了评价 分类器的标准。 2 1 邮件的表示 为了能让计算机执行和完成分类任务，必须首先将关于分类对象的有用信息 输入到计算机中。由于计算机只能识别一系列的0 或1 二进制数，所以不能直接 识别邮件中的自然文本。因此，要完成分类操作，必须先将邮件中的内容表示成 为计算机可以识别的形式，将它进行科学的抽象，建立它的数学模型，用以描述 和代替邮件。具体地讲，就是对邮件进行分析，将其中的内容按照一定的方式组 织和存储起来，得到表征它重要特征或属性的一组数据。为使髓便，可将邮件 表示成矢量形式，称其为特征矢量，也可以把对象的特征属性作为基元，同时用 符号来表示，从而将整个邮件中的内容转换成符号串、关系图或某个数学表达式。 在对邮件的表示进行具体介绍之前，首先对涉及到邮件分类系统的一些基本 概念进行解释。 定义l ：文档( d o c u m e n t ) ：指文本或文本中的片断( 段落、句群或句子) ，本文 指的是邮件。 定义2 ：邮件集：指大量邮件组成的集合。在邮件分类中邮件集分为训练邮件集 ( 简称训练集) 和测试邮件集( 简称测试集) 。训练集是用于归纳各个 类别特性的邮件集合，在这个邮件集当中事先知道了邮件的类别：测试 集则是用于测试分类结果，从而评判分类系统的优劣。 定义3 ：特征项( t e r m ) ：用来描述文本的内容或主题的单词或短语等，本文以单 词作为特征项。一般特征项对于文本来说有一定的代表性，它能够表示 文本的一些特性。如果一个文档表示成为d ( f i ，w 。；t 2 ，w 2 ；f 。，) ，一般 简称为d ( w l ，w 2 ，w n ) ，那么，则为文档d 中的一个特征项。特征项可以 是文档中的各种语言单位，但是特征项的选择要顾及到系统在处理速 度、精度等各方面的要求。 定义4 ：特征权重：在文本分类当中，通常用一个赋有权重的特征向量来表示一 篇文本，即d = “，w 2 ) * 0 0 9 w n ) ，表示向量中第f 个特征项f ，的权重值， 其中l i 疗。特征项是包含了文本的一些重要信息的关键词，而m 表 硕士学位论文 第二章邮件分类技术研究 征的就是该特征项在文本中的重要程度。 在文本分类中，出现了许多关于文本之间词语比较的计算模型，具有代表性 的有布尔模型( b o u l e a r lm o d e l ) 、向量空间模型( v s t o fs p a c em o d e l ，v s m ) 、基 于知识模型( k n o w l e d g e b a ! s e dm o d e l ) 和概牢模型( p r o b a b i l i s t i em o d e l ) 等。在这些 模型当中，文本被表示为关键词( k e y w o r d ) 的集合，这种表示方式又被称为文本 的平面结构( f l a ts t r u c t u r e ) 。关健词贝为陈停用词之外的代表文本内容的词汇关 键词大多为名词；停用词则为那些在文本当中经常出现的，对文本的分类无多大 贡献的词，如a n d , t h e ，o f , o i l ，t h e i r 等等。例如，如果停用词包括( t h e y , o n l y , a ，a n d ， t h e n ，a w a y , ，o f , h a v e ，b e e n ，i t h ，b e ，o r , m a y ) ，则文本 t h e ye x i s to n l yas h o r tt i m ea n dt h e ns l o w l yw a s t ea w a yjl i s t a s u n n o t i c e d o b j e c t so fs h e e r e s tb e a u t yt h e yh a v eb e e nc a l l e d a p p e a r i n gi na n e n d l e s sv a r i e t yo f s h a p e s ，t h e y m a yb ed a z z l i n g l yw h i t e ，0 rt h e ym a yb eg l a s s y b l u e ，g r e e no r p u r p l e ，f i n | e d f a i n t l y o f i n d a r k e r h u e s 在去掉停用词后所剩的为关键词，则文本中的关键词有 211 布尔模型 布尔模型是一种简单文本表示模型，文本中特征项的状态只有0 或i 两种形 式，0 表示该特征项没有出现在文本中1 则表示文本包含该特征项。布尔模型 通过0 和1 的字串将文本表示成了一个0 1 序列。这种模型的优点就是设计比较 简单，分类效率较高，但是由于它的分类能力有限。在序列中只能够知道该特征 项是否在文本中出现，而不知道特征项在文本中出现的频率，这使得它不能很好 地体现文本问的梢关程度。从而影响分类的精度。 212 向量空间模型 向量空间模型足自然语言理解当中用于表示文本的常用模型之一，是由 s a l t o n 等人l 凹1 在2 0 世纪6 0 年代术提出，并在著名的s m a r tfs y s t e mf o rt h e m a n i p u l a t i o na n d r e t r i e v a l o f t e x t ) 系统中得到了成功应用。向量空间模型足文本 分类中应用最广泛的一种文本表示模型，它的相关技术如特征选择在文本分类、 信息检索等领域都取得了较好地效果。 硕士学位论文第二章邮件分类技术研究 在文本分类中，由于自然文本不能够被构造的分类算法直接处理，所以首 先需要对文本进行某种处理，变成分类器能够识别的形式。假设一个文档的r 个 特征项的值分别为w 1 ，w ：，由于它们来自同一待研究的文档，所以应将它 们视为一个整体来考虑，让这些特征项构成一个特征向量d 来表示原研究对象。 此时，对文档的研究就转化为了对它的特征向量的研究。在向量空间模型中， 将每个文本看为是n 维空间中的的一个向量( 如图2 1 所示) ，此时一个文本d 由 一个带权重的特征向量来表示，即 _ ，、 d = 【w 1 ，w 2 ，j ( 2 - 1 ) 其中，w 为第f 个特征项的权重，l 为特征向量的维数。目前广泛采用的权 重计算公式是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 ) 公式【3 0 1 。 矿o ，d ) 表示特征项f 在文档d 中出现的频率，特征项t 出现的频率越高，则权重就 越大。缸扩( f ) 表示特征项t 出现至少一次的文档频率，含有t 的文档数目越多，则 ，就越普通，所分配的权重就越小。t f i d f 一般按如下公式计算权重： ( f ，们： 堑( ! ! 垡! ! ! ! g ! 丝! 堡! ：! ! ! ( 2 2 ) , j e , 。 t f ( t , d ) x l o g ( n n , + o 0 1 汗 其中，( r ，d ) 为文档d 中第i 个特征项，的权重，表示文档集中的文档数 目，刀，为文档训练集中出现t 的文档数。分母为归一化因子，它是为了抑制文本 由于不同长度所造成的负面影响，对权重所做的范化处理。 文本由向量空间模型表示后，两个文本间的相关程度【3 l 】就可以通过向量之 间的某种距离来衡量，一般采用向量之间的内积或夹角余弦来表示文本间的相似 度。 内积计算公式如下： s i n ( d 1 ，d 2 ) = ( r ，d 1 ) 。( f ，d 2 ) ( 2 - 3 ) i f f i l 夹角余弦计算公式如下； s i n ( d 1 ，d 2 ) = e o s o = h w j ( f ，d ，) 。( f ，d 2 ) l - 1 ( 2 - 4 ) 向量空间模型将文档表示成为向量形式，将对文档的内容处理简化成了对向 量空间中的向量进行运算，有效地解决了文本数据在分类中的处理问题，从而大 大提高了文本在计算机中的处理速度。同时它使模式识别和其他领域的计算方法 能够在自然语言文本处理中运用，得以实现文本的可操作性和可计算性。但该模 9 硕士学位论文 第二章邮件分类技术研究 型并没有考虑特征项在文本中的先后次序，并且它里面的元素是互异的( 即没有 重复) ，从而无法体现出文本的结构特征。 2 2 特征选择与提取 图2 1 向量空间模型 在对文本进行分类时，如果同类的模型分布越接近，而不同类间的模型分布 差异越大的话，不仅能使分类的准确率提高，而且也可为分类提高运算速度和节 省资源。因此，在得到文本的若干特征后，一般会对文本进行选择和提取特征。 这些经筛选后的特征应当尽量做到对同类对象差别较小而不同类对象的差别要 大，这样就比较容易设计出性能较好的分类器。由于实际中出现的各种问题使得 很难找到满足以上要求的有效特征，所以特征选择和特征提取技术【3 2 】越来越受 到人们的关注。 由于从文本中产生的特征数量可能很大，特征空间的维数一般高达数千维甚 至数万维，计算量也相当大，所以不能反映文本的本质。而且这么多的特征可能 会影响运行速度和分类精度，也可能会占用很多的存储单元。所以，必须得将特 征空间从高维变换成低维空间，从而解决以上问题。特征提取一般就是通过映射 ( 或称作变换) 的方法将特征空间的维数进行压缩。映射前的特征称为原始特征， 经映射后的特征称为二次特征。在特征提取中，用全部可能的变量把数据变换f 线 性或非线性变换) 到维数减少了的数据空间上。它变换的目的是用较少的潜在的 变量代替原始变量。这样，特征提取不仅可以减少输入特征的数目，提高计算速 度，还可以为分类器提供一个适当的特征集，使得分类器的性能得到提高。 特征选择也是为了提高运行速度和分类精度、节约存储空间，从原始的特征 当中挑选出一些对分类有效的特征以达到降低特征空间维数的目的。经特征选择 后的特征一般具有代表性，它能够代表文本的基本特性。一般特征越具有代表性， 0 硕士学位论文 第二章邮件分类技术研究 则它们所含文本中的信息就越丰富，但是这样分析的代价就越高。词、词组是组 成文本的最基本的元素，它们的出现具有一定的规律性，所以一般采用词或词组 来区分文本内容。在本文中，是以单词作为基本的抽取单位来分析文本的。但是 在采用单词或词组时常会出现一些对文本来说无任何意义的词，即前面提到过的 停用词，这些词在特征空间中出现会影响分类精度，所以就将它们从特征空间中 去掉。而且进行特征的选择时可能会丢失一部分对文本来说是比较有用的信息， 所以如果能够采用好的选择方法，就能够找出具有高分辨率的特征来，使得分类 精度提高。因此，采用什么样的特征选择和提取方法是非常重要的。 有时候特征提取和选择并不是截然分开的。例如，可以先将原始特征空间映 射到维数较低的空间，在这个空间中进行选择以进一步降低维数。也可以先经过 选择去掉那些明显没有分类信息的特征，再进行映射以降低维数。 特征选择和提取方法有很多，主要包括文档频率、互信息、t f i d f 方法等。 这些方法大部分都是对特征赋予权值，通过权值从大到小排列来对特征进行选 择。 2 2 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 通常只是作为其它评估函 数的辅助标准。 2 2 2 互信息 引进互信息1 3 3 i ( m u t u a li n f o r m a t i o n ，简称m i ) 主要是用于表征类和特征之 间的关联信息。两个随机变量的互信息是非负、对称的量度，可以解释为知道一 个随机变量的取值后对另一个随机变量的不确定性的减少量，或者一个随机变量 包含的另一个随机变量的信息量。类c 和特征t 间的互信息公式为： m 力- l o g 兹粉 ( 2 5 ) 其中p ( f ) 和p ( c ) 分别是随机变量弭口c 的概率，p ( t ，c ) 表示特征f 和类c 同时 出现的概率。 对于特征t ，它在每个类中都有一对应的互信息值，求出每个类的互信息值， 硕士学位论文 第二章邮件分类技术研究 然后取其平均作为特征t 的选取标准。当特征t t o 类c 不相关时，i ( t ，c 1 为0 ，说 明特征t 在各个类别中的分布是均匀的。当互信息值增大，则t 和c 的关联程度就 越大。 互信息的不足之处在于在计算低频词时，会使低频词的互信息值增大，这使 得这种选择方法会去掉一些经常出现的有用的特征项。互信息标准在统计模型中 用得较多，它考虑的是类与特征之间的相互关系，关系越紧密，互信息值就越大。 这种方法一般用在统计语言的处理当中。例如在研究两词的关系时，经常使用互 信息作为两个单词之间关联程度大小的量度。本文就运用了这种方法来度量两词 的关联程度。 2 2 3t f i d f 方法 t f i d f 方法是目前广泛采用的计算特征权重的方法，本论文的实验中就用 到了这种方法，t f i d f 主要是结合t f 和i d f 来对特征进行评估。 t f 即t e r mf r e q u e n c y ，是特征频度。指的是特征在文档中出现的频率。在 不同类别的文档中，一般特征出现的次数越多，表征类别的信息就越多。所以， t f 作为衡量特征权值的一个标准。但是并不是所有的t f 值大的特征，就对分类 有贡献，如在文档中频繁出现的停用词，t f 值较大，但是对于分类来说并没有 很大贡献，这些词反而会影响分类的精确度。因此，应当结合i d f 来综合评估 特征的贡献程度。 i d f 即i n v e r s ed o c u m e n tf r e q e n c y ，是反文档频度，是信息检索领域中计算 词与文献关联权重的计算方法。自从1 9 7 2 年s p a r kj o n e s 提出计算文献频率有助 于计算词的权重后，i d f 在信息检索中得到了广泛运用。i d f 公式认为在大多 数文档中广泛出现的特征的重要性比只在小部分文档中出现的重要性要低。i d f 的计算公式如下： i d f ( t ) = l o g ( n n , + 三) ( 2 - 6 ) 其中，表示文档集中的文档数目，n ，为文档训练集中出现t 的文档数。三 的取值通过实验确定，一般取值为o 0 1 。 t f i d f 算法的公式为： t f i d f ( t ) = d f ( t ) xi d f ( t )( 2 7 ) 具体的表达形式和意义如公式( 2 2 ) 所示。 2 3 分类技术 1 2 硕士学位论文 第二章邮件分类技术研究 当前的文本自动分类技术主要采用基于统计的分类方法和基于知识的分类 方法。在2 0 世纪8 0 年代，也就是刚使用分类器时，主要是采用基于知识工程的 规则方法，卡耐基集团当时就利用该方法为路透社开发了c o n s t r u e 系统l j ， c o n s t r u e 系统可以对所接收到的稿件进行自动分类。现在自动分类主要采用的是 基于统计分类的方法，该方法在自动分类中占据着较大的优势，是文本分类的主 要方法。因此本节将介绍目前主要的一些统计分类方法。 统计分类的表达形式是建立在一个坚实的方法和公式之上的，它主要是用概 率模型来得到各类别的特征向量分布，从而实现分类的功能。统计分类是一种有 监督的学习方法，因为它是基于一个类别已知的训练集的。它将己知类别的样本 经训练后来得到分类，下面介绍几种常用的分类方法。 2 3 1 朴素贝叶斯分类法