（计算机应用技术专业论文）中文邮件分类系统的研究及其实现.pdf

中文邮件分类系统的研究及其实现 摘要 摘要 随着办公自动化的快速发展，越来越多的人喜欢用电子邮件进行交流。由于人们 每天需要处理越来越多的邮件，所以迫切需要对邮件进行分类处理。与此同时，随着 机器学习和数据挖掘的研究与发展，基于内容的文本分类技术也获得了空前的发展。 目前为止，研究人员在邮件过滤上投入了很多的精力，做出了不少的贡献。但是由于 邮件分类中存在分类标准的动态变化、传统的文本分类算法效率不高或者分类的准确 度偏低等问题，所以实用的邮件分类系统的研究还未多见。本文借鉴邮件过滤算法， 通过对中文邮件语料的研究，提出了建设一个基于平凡算法和规则相结合的、具有自 适应能力的、实用的邮件分类系统。 首先，本文分析了英文邮件语料库的特点，结合实际提出了构建中文邮件语料库 的方法，并建立了一个实用的、尽量规范的中文邮件语料库。 然后，面对众多可选的文本分类算法，文章分析、比较了几种具有代表性的文本 分类算法，选择了一种时空复杂度低的、适合在线学习的、名叫w i n n o w 的邮件过滤 算法作为研究对象，改进了w i n n o w 标准算法，并通过实验证明了该算法也可以用于 邮件的分类，并具有效率高、准确度较好等特点。 最后，文章对邮件分类系统中普遍存在的自适应问题进行分析与讨论，提出了一 种建立在触发器基础上的增量学习方法，有效地解决了邮件分类系统的自适应问题， 并通过实现一个z h h z 邮件分类系统，测试了系统的自适应能力。实验证明，通过 建立规则、增加w i n n o w 分类的自适应能力，采用w i n n o w 算法能够实现一个高效的、 可靠的、能够适应用户分类标准变化的邮件分类系统。 关键词：w i n n o w ；中文邮件分类；中文邮件语料库；规则：自适应 作者：周志军 指导老师：朱巧明 a b s l r a c t t h er e s e a r c ha n di m p l e m e n t a t i o no f c h i n e s em a r lc l a s s i f i c a t i o ns y s t e m t h er e s e a r c ha n di m p l e m e n t a t i o no fc h i n e s em a i l c l a s s i f i c a t i o ns y s t e m a b s t r a c t w i t ht h ed e v e l o p m e n to fo f f i c ea u t o m a t i o ns y s t e mr a p i d l y ，m o l ea n dm o r ep e o p l e l i k et ou s ee - m a i lt oc o m m u n i c a t ew i me a c ho t h e r d u et op r o c e s sm o l ea n dm o r ee - m a i l s p e o p l en e e da ne - m a i la u t o m a t i cc l a s s i f i c a t i o ns y s t e m i nt h em e a n t i m e ，t h ec o n t e n t - b a s e d t e x tc a t e g o r i z a t i o nt e c h n o l o g yh a sg o t t e nar a p i dd e v e l o p m e n tw i t ht h er e s e a r c ha n dt h e d e v e l o p m e n to f m a c h i n el e a r n i n ga n dd a t am i n i n g r e s e a r c h e r sh a v ed e v o t e dt h e m s e l v e st os t u d ym a i lf i l t e r i n gf o rm a n yy e a r s , a n dh a v e o b t a i n e dm a n yu s e f u lr e s u l t si nt h i sa r e a h o w e v e r , a st h e r ea r ed y n a m i ca l t e r a b l es t a n d a r d i nm a i lc a t e g o r i z a t i o na n dt h ei n e f f i c i e n c ya n di m p r e c i s i o no ft h et r a d i t i o n a lt e x t c l a s s i f i c a t i o na l g o r i t h m s , t h e r ea r eaf e wa p p l i e dm a i lc a t e g o r i z a t i o ns y s t e m s i nt h em a r k e t s ot h i st h e s i sb r i n g sf o r w a r dt oc o n s t r u c tas e l f - a d 哪i v ee n dp r a c t i c a lm a i lc l a s s i f i c a t i o n s y s t e mb a s e do nt h ei n l e g r a t i o no fn o r m a la l g o r i t h mw i 也r e g u l a t i o n sa f t e rs t u d y i n g c h i n e s em a i lc o r p u s f i r s t l y , t h et h e s i sa n a l y s e st h ec h a r a c t e r i s t i c so f e n g i i s hm a l le o r p l l s ，p u t sf o r w a r dt h e m e t h o do fc o n s t r u c t i n gac h i n e s em a i lc o r p u sb yp r a c t i c a ls i t u a t i o na n dc o n s t r u c t sa l l p r a c t i c a la n d n o r m a t i v ec h i n e s em a i lc o r p u s t h e n ，f a c i n gm a n yt e x tc l a s s i f i c a t i o na l g o r i t h m s ，t h et h e s i sa n a l y s e sa n dc o m p a r e s s e v e r a l r e p r e s e n t a t i v e t e x tc l a s s i f i c a t i o n a l g o r i t h m s ，c h o o s e s al e s s s p a c e - t i m e c o m p l e x i t y sa l g o r i t h i nn a m e dw i n n o ww h i c hf i t st oo n - l i n es t u d ya n du s e dt of i l t e rm a i l a st h er e s e a r c ho b j e c t a f t e ri m p r o v i n gt h ew i n n o ws t a n d a r da l g o r i t h m ，t h et h e s i sh a s p r o v e dt h a t t h i sa l g o r i t h mc a nb eu s e dt ot h ec l a s s i f i c a t i o no ft h em a i la n dh a ss u c h c h a r a c t e r i s t i c sa st t i g he f f i c i e n c ya n db e t t e ra c c u r a c yb ye x p e r i m e n t s f i n a l l y , t h et h e s i sa n a l y s e sa n dd i s c u s s e st h eu b i q u i t o u ss d f - a d a p t i v ep r o b l e mi nt h e m a i lc l a s s i f i c a t i o ns y s t e m ，p r o p o s e sa k i n do fi n c r e m e n t a ll e a r n i n gm e t h o db a s e do n t r i g g e rt os o l v et h es d f a d a p t i v ep r o b l e mo ft h em a i lc l a s s i f i c a t i o ne f f e c t i v e l v a 矗e rt h a t 1 i t h er e s e a r c ha n dh n p l o n c n t a t i o no f c h i n e s em a i lc l a s s i f i c a t i o ns y s t e m a b s g a c t t h et h e s i sg i v e st h et e s t i n gr e s u l t sf o rt h es e l f - a d a p t i v ea b i l i t yb yi m p l e m e n t i n gz h h zm a i l c l a s s i f i e r i ti sp r o v e dt h a tt h ew i n n o wa l g o r i t h mc a nb eu s e dt oi m p l e m e n to nm a i l c l a s s i f i c a t i o ns y s t e mw h i c hh a sh i g he f f i c i e n t ，r e l i a b l ef e a t u r e sa n dc a l lm e e t st h ec h a n g e o fa s e r sc r i t e r i af o rc l a s s i f i c a t i o nt h r o u g hs e t t i n gu pt h er u l e sa n dt h r o u 曲a d d i n g s e l f - a d a p t i v ea b i l i t yt ow i n n o wa l g o r i t h m k e yw o r d s ：w i n n o w ；c h i n e s em a i lc a t e g o r i z a t i o n ；c h i n e s em a i lc o r p u s ；r e g u l a t i o n ； s e l f - a d a p t i v e 1 1 w r i t t e nb yz h o uz h i j u n s u p e r v i s e db yz h uq i a o m i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承 担本声明的法律责任。 研究生签名：尘坦日期： 学位论文使用授权声明 d v 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名 期：兰! ! ：竺 期： 中文邮件分类系统的研究及其实现 第一章序言 1 1 课题背景 第一章序言 目前，电子邮件已成为人们生活中快速、便捷的重要通信手段之一。然而正因 为其快速便捷，它也愈来愈成为一些不法分子利用的工具，最典型的例子就是不请 自来的广告或垃圾信息。其次，随着办公自动化的快速发展，人们通过电子邮件的 往来日益频繁，每天都要处理大量的邮件o 】，那么如何来区分其轻重缓急并为其归 类处理呢? 在某个程度上。如果我们能够让计算机自动地对邮件分类，那么这两个 问题都迎刃而解。比如，如果计算机能识别出广告，那我们就免受广告的干扰；如 果计算机能区分私人信件和工作信件，我们就能很快地分出轻重缓急继而有序地处 理邮件。 假如把邮件看作一个普通的文本( 这里暂时忽视附件等因素) ，邮件分类自然隶 属于文本分类的范畴本文也正是利用文本分类的技术来解决邮件的自动分类问题， 所以，我们先来看看文本分类的国内外现状。 现在文本分类是信息处理领域里的一个热门话题，国内外都有很多单位在进行 研究，欧美在这个领域内占有很大的优势。在中文文本分类上，香港和台湾的起步 较早，水平相对要高一些，大陆在这个方面起步较晚。 国外主要的研究单位如c m u ，斯坦福等，在理论研究上有很高的水平，这与 其整体学术水平高不无关系，也与英语词汇的特点有关。国内主要的研究单位有复 旦大学、北大、哈工大、中科院计算所、t r $ 、广州西风公司等。 到目前为止，文本自动分类在国外大致经历了三个发展阶段：第一阶段( 】9 5 8 1 9 6 4 ) 主要进行自动分类的可行性研究；第二阶段( 1 9 6 5 1 9 7 4 ) 进行自动分类的 试验研究：第三阶段( 1 9 7 5 至今) 进入实用化阶段，并在邮件分类、电子会议、 信息过滤等方面取得较为广泛的应用，其中较为成功的系统有麻省理工学院( m i t ) 为白宫开发的邮件分类系统，卡内基集团为路透社开发的c o n s t r u e 系统等。 我国文本分类的研究工作始于蕊世纪8 0 年代，大体经历了可行性探讨辅 助分类系统自动分类系统三个阶段。总体来说，中文文本分类还处在试验研究 阶段，j 下确分类率约为6 0 9 0 ，但也逐渐向商业化的软件应用靠拢，并已经尝 第一章序言 中文邮件分类系统的研究及其实现 试开发了一批自动分类系统。例如，清华大学吴军研制的自动分类系统、山西大学 刘正瑛等人开发的金融自动分类系统、上海交通大学王永成等研制的基于神经网络 优化算法的中文自动分类系统、广州西风公司研制开发的西风文本自动分类系统。 如何找到合适的应用并且在实践中不断改善算法，以此改善分类的效果和提高系统 的性能成为文本分类的当务之急。 邮件过滤是邮件分类的特例，即将邮件分为垃圾邮件和合法邮件。在这一方面， 人们不断尝试法律的和技术的手段。2 0 0 4 年9 月1 7 日，国际报道称美国联邦贸易 委员会( f t c ) 考虑出六位数美元悬赏揭发发送上百万封垃圾邮件的举报人，这是人们 有意从法律上寻求帮助。在技术线路上，对过滤技术的应用和研究主要集中在以下 方面：利用i p 或“黑自名单”进行的邮件限制或过滤，典型应用包括结合d n s 的实 时黑名单( r b l ) 过滤，用户自定义邮件自通道加严整的过滤方法；基于数据挖掘 技术进行的邮件过滤研究，利用文本分类与统计算法进行垃圾邮件检测，比较有代 表性的是贝叶斯( b a y e s ) 过滤器。其他研究包括：基于记忆信息、基于事件特征描述 信息进行数据挖掘的垃圾邮件检测方法；基于垃圾邮件的特征分析、规则提取的规 则匹配过滤方法，对这种技术的应用，s p a m a s s a s s i n 是个典范。 经过很多科研工作者多年的努力，文本分类已经取得了根大的进展。而文本分 类的一个自然应用领域：邮件分类，因为存在用户分类标准的动态变化、传统的文 本分类算法效率不高或者分类的准确度偏低等问题，所以真正实用的邮件分类系统 的研究还未多见，有关的少数研究也大多是基于英文语料的，这在一定的程度上虽 然可以比较出分类算法的优劣，然而英文语料毕竟不等同于中文语料，适合英文邮 件的分类算法并不一定适合中文的环境，所以真实地面对中文邮件语料进行研究和 探讨是摆在我们面前的一个不容懈怠的课题。 本文正是基于以上现象和问题的思考，从文本分类、邮件分类的现状入手，并 通过建立真实的中文郏件语料库为基础，找到适合中文邮件文类的算法以及如何尽 可能的增强中文邮件分类器的可信度和实用性，最后的目标是能够利用该邮件分类 器构建一个效果不错、性能上乘、具有自适应能力的中文邮件分类系统。 中文邮件分类系统的研究及其实现 第一章序言 1 2 课题研究目标及相关问题 本文是面对人们频繁处理大量纷繁复杂的中文邮件这一现实问题，基于文本数 据挖掘和中文处理技术，采用文本分类算法、统计知识并结合邮件的个性化特点， 提出对中文邮件实现自动分类的设想。此外，本文还要对邮件分类系统中普遍存在 的自适应问题进行分析与讨论，找到合理的解决办法。课题主要解决以下几个问题： ( 1 ) 建设中文邮件语料库； ( 2 ) 总结邮件分类算法； ( 3 ) 尝试将w i n n o w 算法用于中文邮件语料库和公用语料库； ( 4 ) 比较w i n n o w 、k n n 、b a y e $ 算法的优劣； ( 5 ) 合理改善w i n n o w 算法： ( 6 ) 充分挖掘中文邮件的个性特征，建立规则或规则库； ( 7 ) 合理解决邮件分类系统的自适应闯题； ( 8 ) 集成邮件分类系统，检验系统的效果和自适应能力。 1 3 论文的结构 第一章序言 论述论文的研究背景与意义以及论文的主要工作。 第二章构建邮件分类器的关键技术 总结归纳了构建邮件分类器的关键技术，包括训练集和测试集的概 念、预处理、邮件标引和空间将维、常用的邮件分类器及其算法、中文 语料库的建设以及阈值选择和评估准则。 第三章b a y e s 和k n n 分类器在邮件语料上的实验 本章进步介绍了b a y e s 和k n n 这两种典型、有效的文本分类器，并在新建 的中文邮件语料上进行了实验，给出了实验的结果并统计了它们的性能表现。 第四章中文邮件分类器的设计 第一章序苦中文邮件分类系统的研究及其实现 本章介绍了一种在线学习的、基于错误反馈机制的、名叫w i n n o w 的算法，并 在同一中文邮件语料库上做了实验与改进，通过和b a y e s 以及k n n 比较，得出 w i n n o w 更适合中文邮件分类的结论。本章也就中文邮件的个性特点做了专门的研 究，提出了规则与平凡算法的组合共同提高系统可靠性的办法。本章最后讨论了解 决分类系统自适应问题的实现途径与方法。 第五章z h h z 中文邮件分类系统的实现 根据所提出的系统目标，给出其总体框架、组成部分以及实现的步骤，中间插 入介绍了j m a i l 组件，最后介绍分类器的应用及z h h z 分类系统的表现。 第六张总结与展望 对论文的工作进行总结，提出将来的研究方向。 中文邮件分类系统的研究及其实现 第二章构建邮件分类器的关键技术 第二章构建邮件分类器的关键技术 2 1 训练集和测试集 机器学习方法依赖于一个已经被正确归类的初始文档集c b = f ，d ，j ，而这 个初始集合又包括了两个不相交的子集：训练集和测试集。 ( 1 ) 训练集抒= 瓦，石 ：用于计算机观察、学习、提取文档的分类特征， 构造分类器。有的时候进一步将训练集分为两部分：t r ( t r a i m n gs e t ) 和v a ( v a l i d a t i o n s e t ) ，v a 用于调整向量特征维数，使分类性能达到最优。 ( 2 ) 测试集乃= i ，石 ：用于测试分类器的分类效果与性能。 2 2 邮件标引和空间降维 2 2 1 预处理 在对邮件进行标引等工作之前，一般先要对邮件进行预处理。预处理通常包括 如下几个或全部环节： ( 1 ) 去掉某些特定的格式标记，比如i - i t m l 中的一些t a g 标记； ( 2 ) 去掉附件和图片( 附件和图片，甚至h t m l 标记应该也包含分类的信息， 可以作为分类的参考，但是本文暂时没有把它们作为研究的范畴) ； ( 3 ) 禁用词( s t o p w o r d s ) 去除、数字合并、词根还原( s t e m m i n g ) ： ( 4 ) 分词、词性标注、短语识别： ( 5 ) 词频统计： ( 6 ) 数据清洗，即去掉不合适的噪声邮件或邮件中的垃圾数据。 这里说明一下“禁用词”这个概念，禁用词是指那些出现频率过高，不具有类 别区分度的词，比如介词、连词、代名词等，禁用词还可以包括那些几乎不携带分 类信息的生僻词等。 第二章掏建邮件分类器的_ 关键技术 中文邮件分类系统的研究投j 实现 2 2 2 邮件标弓 邮件并不能够被分类器或者构造分类器的算法直接解释，标引过程就是将邮件 形式化，即将邮件d ，映射到计算机可以识别的形式( 反映邮件的内容) ，并且这种 映射法则必须保证在训练集和测试集上的一致性。映射法则的选择取决于个人将什 么视为邮件中有意义的单元以及帮助这些单元进行有意义的组合的自然语言法则， 前者是词汇语义学问题，后者是组合语义学问题。就象信息检索中一样，后者通常 忽略不管，而一篇邮件通常被表示为关于词语( t e r m ) 权重的向量d ，= ( w l ，叫 ，) ， 这里的7 是指至少在训练样本集t r 的至少一篇邮件中出现过的词语( 或称特征) ， 0 蔓1 代表词语f 。在表达邮件d ，语义上的贡献大小。处理这个问题技术上的不 同体现在两个方面： ( 1 ) 如何理解这里所说的词语； ( 2 ) 如何计算词语的权重。 对于( 1 ) ，典型的是选择文本中的词条。在许多的实验中瑚，选用复杂的描 述来反映文本的内容弗没有出现重要意义上的突出效果。有些研究者选择短语作为 标引项，直到今天，都没有取得大的鼓舞，丽无论这种短语的概念源自下面哪一种： 依照句法的，即这个短语是语言语法意义上的； 基于统计规律的，这样的短语不强调语法上的意义，只是文本中相邻的一些 字词的序列，它们在统计上具有重要性。 l e w i s 分析过单独采用源自句法的短语来标引结果不理想的原因：与单独采用 词来标引的方式相比，它们尽管有更出众的语义质量，但是统计质量却比不上了。 既然如此，如果结合二者应该是最好的选择了，对此，t z e r a s 和h a r t r a a n n 作了尝试。 他们结合句法和统计标准，只选择那些既满足句法特点又具有良好统计规律( 至少 在该类别的正面例子中出现三次) 的名词短语，结果获得了很大的改善。到底怎样 的短语是最好的，c a r o p r e s o 等人积极追踪了这个方向的研究”。 至于( 2 ) t 权重取值范围通常在0 到l 之间，特殊时候也采用二元权重( 0 表示该词语在该文档中不出现，l 表示该词语在文档中出现) ，至于到底用二元权 重还是非二元权重取决于分类器学习算法。有多种不同的方法来反映权重的大小， 但是大多数的方法都基于下列经验的观察： 6 中文邮件分类系统的研究搜其实现 第二二章构建邮件分类器的关键技术 一个词在一篇邮件中出现的次数越多，它与这篇由b 件对应的主题越相关； 一个词在整个邮件集中出现的频率越高，它的类别区分度越小。 下面是我们4 种常用的权重计算方法，其中7 瓦是指特征词i 在邮件j 中的频 率，n 是测试文档总数，d 只代表在整个邮件集中出现特征词i 的邮件数： ( i ) 布尔权重( b o o l e a nw e i g h t i n 曲： 。一j l ，如果赐 o 公式( 2 ) 嘞2 1 0 ，如果砜= 0 。 ( 2 ) t f i d f 型权重，具体又包括下面几种： t f ：令= 玛 t f + i d f ：令= 觋x l o g ( n d f ) t f c ：即对上式进行归一化，令 砜x l o g ( n d f ) 驴霹幕萧 公式( 2 2 ) 公式( 2 3 ) 公式( 2 4 ) l t c ：目的是降低t f 的作用，令 w 。：一4 1 0 9 ( 丁瓦- + 1 o ) l o g ( ，, 啦, i ) ：公式( 2 5 ) m j = 一 =h 。7 9 ，压烁觋+ 1 0 ) l o 科，玻) 】 ( 3 ) 基于熵概念的权重 n d p yw e i g h t i n g ) , 令 乩卿“x 1 + 击喜t 斋埔嘞 馘眩 其中b 薯毋岫g 白卜加哟翱赢 如果t e r m 分布极度均匀：熵等予- 1 只在一个文档中出现：熵等于0 ( 4 ) o k a p i 权重函数；即在t f i d f 的基础上考虑邮件的有效长度，令 3 彘嘲c 笔挚 馘( 2 7 ) a v g d l 标引的时候是对整个邮件的全部文本进行标引还是只选择一部分标引值得商 榷。存文档的标引中，前者是通常的做法，但也可以根据具体的应用选择后者。例 第二章构建邮件分类器的关键技术 中文邮件分类系统的研究及苴实现 如，l a r k e y 在为专利进行分类的应用中5 1 ，仅仅标引标题、关键词、摘要的前2 0 行 以及描述这种发明、创造新颖之处的部分。这种方法之所以可行在于专利文档是结 构化文档的事实。类似的，当能够知晓文档的标题的情况下，我们可以对标题中的 字词赋予较大的权重系数来突出它们的重要性。而当文档是非结构化文档时，识别 文档中的关键部分就不是件容易的事了，这个时候多数选择对全部文本进行标引。 邮件是一种半结构化的文档，有结构性的一面，但是，一封垃圾邮件往往会在标题 等方面进行乔装打扮，这样并不保证标题具有绝对的衡量价值或者说优势，所以我 们在本文中，采用对所有邮件文本进行标引的方法，同时充分利用邮件的半结构化 特点。 2 2 3 空间降维 文本检索( t e x tr e t r i e v a l ) 的典型算法( 比如余弦距离法) 尚可以承受高维向 量空间( 很大的口i 值) ，然而对于构造分类器的复杂算法( 如l l s f ) ，情形就不 一样了。此外，模式识别系统的复杂度麓着系统维数( 所使用的特征数) 的增长而 快速增长，同时，有噪声的或高相关性的特征的增加事实上会降低系统的性能。正 因为此，在构造分类嚣之前，我们一般要对向量空间进行砗维处理。针对每类，去 除那些表现力不强的词汇，使得旷 c ，这里的t 是降维后的特征集合。 另外，降维处理也有助于避免过分拟合( o v e r l i t t i n g ) ，过分拟合是指分类器 被训练成不仅符合某个类别的构成特征，还符合训练集上的一些偶然性或暂时性特 征。过分拟合的分类器用来重新分类训练集中的文档( 即后愿提到的封闭测试) ，效 果很好；但是，用来分类未知文档时( 即后面提到的开放测试) ，效果糟糕，在下 面介绍的w i n n o w 算法中，就存在对过分拟合问题的思考经验表明。为了避免过 分拟含，训练文档的数量与所选择的特征的数量之比应该达到一定的比例, f u h r 和 b u c l d e y 建议：在文本分类中。每一个特征应该安排5 0 - 1 0 0 篇训练文档【6 】。这意味 着，采用降维处理后。尽管采用了较小的训练集，我们还是有效地避免了过分拟合。 然而，移除某些特征的做法有一定的风险，即很可能去掉一些有用的信息，所以， 为了达到最优的效果，降维处理应该十分小一1 1 , 。下面介绍的各种降维技术，要么源 于信息理论，要么有线性代数的支持，并且在实际中接受了一些检验： ! 垫竺坌耋墨竺竺竺窒苎苎型 竺三兰竖竺竺竺兰竺塑鳖 空间降维的一种区分是：局部空间降维与全局空间降维。 ( 1 ) 局部空间降维( l o c a ld r ) ：分别为每一个类别q ，选择它的特征子集正， 使得lz i | 7 i 。这表明，我们必须针对不同的类别为同一个文档d ，分配不同的向量 空间，典型的1 0 纠正巨5 0 。 ( 2 ) 全局空间降维( g l o b a l d r ) ：为所有类别选择公共的特征子集丁，使得 j t i | t l 。 这种区分通常不影响空间降维技术的选择，大多数技术既可以用在局部降维也 可以用在全局降维上。 另外，根据最后的特征的特点，降维技术还可以分为： ( 1 ) 特征选择降维：t 是t 的子集； ( 2 ) 特征抽取降维：t ，中的元素并不完全与t 中的元素( 原始特征) 相同。 而是来自于t 中元素的合并或者转化。 这种区分下的降维方法采用着完全不同的技术，在下面，我们将对这两种降维 技术分别介绍。 ( 一) 特征选择( f e a t u r e s e l e c t i o n ) 特征选择是为了提高分类效率、减小计算复杂度，从而努力移除原始特征中不 带分类信息或者信息较少的词。y y a n g 统计了最常用而且最有效的方法，包括文档 频率、信息增益、工2 统计、互信息，我们一一介绍： ( 1 ) 文档频率p f ) 词条的文档频率( d o c 咖舶tf r e q u e n c y ) 是指在训练语料中出现该词条的文本 数。d f 作为特征抽取基于如下基本假设：d f 值低于某个阚值的词条是低频词，它 们不含或含有较少的类别信息。将这样的词条从原始特征空间中移除，不但能够降 低特征空间的维数，而且还有可能提高分类的精度。 文档频率是最简单的特征提取技术，由于其具有相对训练语料规模的线性计算 复杂度，它能够容易地被用于大规模语料统计。但是信息抽取( i n f o r m a t i o nr e t r i e v a l ) 研究中却通常认为d f 值低的词条相对于d f 值高的词条具有较多的信息量，不应 该将它们完全移除。y y a n g 的试验证明：在英文环境中，当1 0 和c h i 等统计方法 的计算“费用”太高而变得不可用时，d f 可以安全的代替它们被使用。 优点：去掉低频词，减少特征空问的维数，当低频词为噪音时，可提高分类效 o 第二章构建邮件分类器的关键技术 中文邮件分类系统的研究及扎实现 果 算法简单，计算量小。 缺点：认为低频词无信息量，但低频词也可能带有很大信息量，这时直接去掉 低频词会影响分类效果。 ( 2 ) 信息增益0 g ) 信息增益( i n f o r m a t i o ng a i n ) 在机器学习领域被广泛使用。对于词条t 和文档类 别c ，i ( 3 考察c 中出现和不出现t 的文档频数来衡量t 对于c 的信息增益。我们采用 如下定义式： 1 g ( t ) = 一：。尸( q ) l o gp ( q ) + p o z ；。p ( c i o g p ( c i i t ) + p o ( 即a ：) 所对 应的样本向量； 第二步将用主题词向量形式表示的待分向量d 和支持向量d ，用核函数 ( k ( d ，d t ) ) 映射到线性空间。常用的核函数有多项式核【( d ，d ，) + 1 】，q 是自然数、 径向基核( r b f ) e x p 卜掣、两层神经网络核s ( 4 ( d ，d ，) + f ) ，其中s 是s i g m 。i d 仃 函数，a ，t 是某些常数。 第三步用核函敷置( d ，d ，) = m ( d ) 中( d ，) 来代替点积( d ，d ，) ，然后用口，加权，从而构 成口：y ，k ( d ，d ，) ； 第四步判断，( d ) = s 印( 口? ，k ( d ，d ，) + 6 ) 是否+ l 或一l ，决定文档d 属于 哪一类。表达式中s g n 为符号函数，口，为每个样本对应的l a g r a n g e 乘子。 说明：v c 维是指示函数集能够打散的最大样本数，对应学习机器即分类器的 复杂程度。 第二章构建邮件分类器的关键技术 中文邮件分类系统的研究发其实现 2 3 5d e c i s i o nt r e e 一决策树方法 决策树是一种非常有效的机器学习分类算法。决策树方法的起源是概念学习系 统c l s ，然后发展到i d 3 方法而为高潮，最后又演化为能处理连续属性的c 5 0 。有 名的决策树方法还有c a r t 和a s s i s t a n t 。 这种学习着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类 规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据 不同的属性值判断从该结点向下的分支，在决策树的时结点得到结论。所以从根到 叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规 则。基于决策树的学习算法的一个最大的优点就是它在学习过程中不需要使用者了 解很多背景知识( 这也同时是它最大的缺点) ，只要训练例子能够用属性一结论式的 方式表达出来，就能使用该算法来学习，该算法的萋本步骤如下： 第一步对训练文本预处理和特征选择，把文本表示为特征向量； 第二步生成树( g r o w t hp h a s e ) ，用递归算法实现的伪代码如下： p a r t i t i o n f r r a i n d a t as ) i f 【a l lp o i n t si n8a mo f t h es a mc l a s s ) r h e ar e t u r n ； f o r e a c h 鲥= h 诅m 武e a d o e v a l u a t es p l i t so na t t r i b u t ea ： u s eb e s ts p l i tf o u n dt op 蚵i t i o nsi n t os la n ds 2 ： p a r t i t i o n ( s1 ) ； p a x t i t i o n ( s 2 ) ； ) ； 第三步修剪生成树( p r u n ep h a s e ) ，利用向后剪枝法或向前剪枝法对前面生成的 决策树实行剪枝处理，去除那些对分类影响不大的分支，比如采用一棵树t 的可调 节错误率来衡量，公式如下： e 。( t ) = e ( r ) + d v 。( t ) 其中，心。( 7 1 ) 是树的叶子数，a 是一个常数 第四步依据最终形成的树，生成规则集： 1 6 公式( 2 1 8 ) 中文邮件分类系统的研究及其实现 第二章构建邮件分类器的关键技术 第五步将待分类的文本表示为文本向量，匹配规则集，得到所属类别。 2 3 6n e u r a ln e t w o r k s 神经网络方法 神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机 制而建立的一种计算模型。常用的神经计算模型有多层感知机、反传网络、自适应 映射网络等。神经网络通常由输入层、输出层和若干个隐层组成，输入层的神经元 个数等于样本的特征数，输出层就是分类判决层，它的神经元个数等于样本类数。 最流行的神经网络学习算法是b p 算法( b a c k - p r o p a g a t i o na l g o r i t h m ) ，在这 种模型中，分类知识被隐式地存储在连接的权值上，使用迭代算法来确定权值向量。 当网络输出判断正确时，权值向量保持不变，否则进行增加或降低的调整，因此也 成为奖惩法，算法的基本步骤如下： 第一步初始化网络各层的权值( 0 ) 和神经元阀值0 ，( 0 ) 为小的随机数； 第二步提供文本训练样本，即输入向量x 。和输出向量y 。，n = l ，n ； 第三步计算网络的实际输出及隐层单元的状态： o - - - f ( e 一岛) ( 隐层) f d 一= ，( 如以) ( 输出层) 式中；法，( 对= 再焉五1 而，为训练样本为p 时节点i 的输入； 第四步计算误差对各层的影响： = ( 1 0 一) 靠( 隐层 公式( 2 1 9 ) 公式( 2 2 0 ) 公式( 2 2 1 ) = o 斗0 一o 肿) ( 一0 业) ( 输出层) 公式( 2 2 2 ) 表达式中k 为训练样本为p 时网络输出层节点k 的期望输出 第五步修正权值和闽值： + 1 ) 5 w o ( n ) + ，7 ，0 ，+ a ( 峋( n ) 一( ”一1 ) ) 公式( 2 2 3 ) 撼一二章构建邮件分类器的关键技术 中文邮件分类系统的研究及其实现 o y ( n + 1 ) = 0 j ( n ) + ，? s p j + 口( 色( n ) 一哆( n 1 ) ) 公式( 2 2 4 ) 表达式中玎为学习率，口为动量因子； 第六步计算网络输出误差： e = 1 1 2 ( k 一) 2 公式( 2 2 5 ) 第七步判断误差是否满足要求，若满足则转到第八步，否则转到第三步； 第八步训练结束。 除了以上方法以外，v o t i n gm e m o d 基于投票的方法，m a x i m u me n t r o p y m o d e l 一一最大熵模型，d e c i s i o nr u l ea a s s m e r 一一决策规则法，w i d r o w - h o f f c l 船s 讯e r 一又称最小均方法l m s ( l e a s tm e a ns q u a r e ) 也得到了不同程度的应用， 并且取得了一定的效果。 2 4 中文邮件语料库的建设 与一般的中文语料库的建设不同，邮件有它固有的特殊性，合法的、真实的邮 件往往涉及到个人隐私，所以建立邮件语料库并不象普通文本语料库一样相对简单。 d d 删】l s o o d o g 、j 妇虹m 船帆等人【1 2 】在邮件语料痒的建设上徽了不少卓有成效的 工作，他们一方面从公用的邮件列表或者新闻组里获取原始邮件加以分类整理，一 方面将可能涉及个人隐私的邮件加密( 比如用燕数代替词汇，并且不公开这种对应 关系) 来隐藏邮件的真实性但是又不影响试验进行。目前，公用的邮件语料库有 l i n g - s p a m 、p u i 、p u l 2 3 a 等，这些可以在h t t p ：w w w i i t d e m o k r i t o s g r s k e l i - e o n f i g f d o w n l o a d s 站点下载到。以p u i 为例，p u i 中包括了4 8 1 封垃圾邮件和 6 1 8 封合法邮件，共1 0 9 9 封。为了保护隐私，邮件中的每个词汇用唯一的整数来代 替。邮件中的附件、h t m l 标记都被剔除，同一天里收到的相同垃圾邮件也只保留 一个副本。另外，整个邮件语料分成数量基本相等的1 0 份。p u i 包含4 种进行了 不同层次预处理的语料：b a r e 、l e m m 、s t o p 、l e m ms t o p ，其中b a r e 是相对原始的 语料，l e m m 进行了词根还原处理，s t o p 去掉了停用词，l e m ms t o p 既进行了词根 还原，也去掉了停用词。 在认真比较和研究了目前公用的邮件语料库和中文邮件之后，我们发现： ( 1 ) 普通的中文语料中的内容特征并不完全具备邮件文本的特点：比如邮件 1r 中文邮件分类系统的研究及托实现 第u i 章构建邮件分类器的关键技术 中的词汇更加生活化、个性化或者说口语化； ( 2 ) 邮件有其自身的结构特点：邮件是一种半结构化的文档，包括发件人、 邮件服务器地址、主题、信体等，恰当地使用这些结构特点，将有利于邮件的分类： ( 3 ) 网上提供的邮件语料几乎都是英文语料：单纯的英文语料训练出来的分 类器并不一定适合中文环境，更谈不上两种语言都适合： ( 4 ) p u l 等邮件语料只有两个类别，垃圾邮件和合法邮件。这是因为这些语 料库主要用于邮件过滤的应用研究，邮件过滤是邮件分类的特例，它们之间有很多 相似之处，但是二者毕竟不能完全等同。 正因为这样，建设一个真实的、标准的中文邮件语料库就显得非常重要。我们 在中文邮件语料库的建设中，着重在以下三个方面开展工作：第一是要找到合适的 邮件语料源，第二要建立合乎实际需要的分类标准，第三是要有完好的个人隐私保 护措施。 合适的邮件语料源是建立邮件语料库的基础。当我们着手建立中文邮件语料库 的时候，我们就会问：从哪里去弄那么多的邮件? 这也许是至今为止中国还没有一 个公开的邮件语料库的部分原因。我们首先想到的是公用的邮件列表和新闻组，从 这些地方去获取几千封邮件并不是很难的工作，而且没有隐私之嫌，但是我们很快 发现这些邮件内容比较单一，多是针对学习或者某种社会现象韵讨论。之后，我们 把目标锁定在专用的邮件服务器上，这里有数百、上千人的个人邮件帐户。在征询 了个人意见，并且保证对个别敏感信息保密之后，我们从邮件服务器上分批取得共 1 5 7 g 原始的、还加密着的邮件语料，这是第一手真实的材料。 合乎实际的准确的分类标准的制定是一个语料库成功的关键。一个标准模糊， 实际归类不准确的语料库只能把研究带入歧途，误导研究人员。在一般的文本分类 领域，经过许多年的发展，一些分类标准几经修正已经逐渐完善，并被人们广泛接 受，比如中国图书馆图书分类法的分类标准【1 3 1 。邮件分类不需要中国图书馆 图书分类法这样细致，也不能这样划分，几乎没有几个用户