山东大学
硕士学位论文
电子邮件智能分类系统的设计与实现
姓名：徐海涛
申请学位级别：硕士
专业：计算机应用技术
指导教师：柴乔林
20040312
山东大学硕士学位论文
摘要
本文主要介绍了在Ｗｉｎｄｏｗｓ环境下电子邮件智能分类的设计模型和实现方法。该分类系统能够对一些典型垃圾邮件进行识别判断，而且也同时能够对其它邮件进行分类。山于如今电子邮件服务在网络中应用非常广泛，一个电子邮件信箱所接收到的邮件信息通常是五花八门。目前大部分的电子邮件收发软件，都提供简单的分类功能，不过需使用者自订分类规则。最近几年有许多邮件过滤的相关研究，但大部分的研究均针对英文来分类，无法直接使用在中文邮件分类上。所以本文介绍的Ｗｉｎｄｏｗｓ下的电子邮件智能分类系统，专门针对中文邮件的分类进行了研究，具有很高的研究价值。
开发该系统的主要目的是了解当前邮件智能分类的发展现状，学习中文邮件系统的处理的基本概念。通过学习和实践，发现中文邮件分类发展中遇到的问题，并结合自己的研究工作提出一些看法和见解。
本文首先介绍了关于文档分类的一些基本概念和原理，又简单介绍了一下其发展过程。然后，重点介绍了具体的中文邮件智能分类系统的设计和实现方法。最后，总结了当前中文邮件智能分类系统所面临的主要发展障碍，探讨了解决这些问题的一些方法和思路，指出了中文邮件智能分类系统今后的研究方向和发展趋势，为以后的研究工作做出了一定的方向性指导。
本论文的目的便是希望设计一个能够适用在中文邮件上的分类系统。在本论文中，我们考虑邮件中不同的特征应各自使用较为适合的分类器，并结合了分类器来预测邮件类别。我们将此邮件分类器应用在客户端，对邮件进行类别的标记。藉由此类别标记，邮件应用软件便能依据单一标记而直接的将邮件分派到各个目录，大量减轻了使用者进行纯人工分类或使用者制定复杂分类规则的负担。实验结果显示本论文中的系统使用在邮件分类上有可较好的正确率。
关键词：电子邮件，分类，中文分词，精确率，召回率
山东大学硕士学位论文
ＡＢＳＴＲＡＣＴ
Ｔ１１ｉＳｐａｐｅｒｍａｄｅｓｏｍｅｉｎｔｒｏｄｕｃｔｉＯｉｌｆｏｒｔｈｅｍｏｄｅ］ｄｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｈｅＥｍａｉｌＳＩｎｔｅｌｌｊｇｅｎｔＣｌａｓｓｉｆｉｃａｔｉｏｎｕｎｄｅｒｔｈｅｗｉｎｄｏｗｓｅｎｖｉｒｏｎｍｅｎｔ．ＴｈｉＳＣｌａｓｓｉｆｉｃａｔｉｏｎｓｙｓｔｅｍｃａｎｍａｋｅｔｈｅｒｅｃｏｇｎＪＺｉｎｇａｎｄｊｕｄｇｅｍｅｎｔｆｏｒｓｏｍｅｔｙｐｉｃａｌｊｕｎｋ—ｅｍａｉｌＳ，ａｎｄｉｎｔｈｅｍｅａｎｗｈｉｌｅｍａｋｅｔｈｅｃｌａｓｓｌｆｉｃａｔｉｏｎｆｏｒｓｏｍｅｏｔｈｅｒｍａｉｌｓ．ＡｓｔｈｅｐｏｐｕｌａｒｕｓａｇｅｏｆｔｈｅｅｍａｉｌｓｅｒｖｉｃｅｉｎｔｈｅＩｎｔｅｒｎｅｔｎｏｗａｄａｙｓ，ｏｎｅｅｍａｉｌａｃｃｏｕｎｔｃａｒｔｒｅｃｅｉｖｅＩｏｔｓｏｆｄｉｆｆｅｒｅｎｔｅｍａｉ１Ｓ．Ｃｕｒｒｅｎｔｌｙ，ｍｏｓｔｅｍａｉ１ｒｅｃｅｉｖｉｎｇａｎｄｓｅｎｄｉｎｇｓｏｆｔｗａｒｅｓｃａｎｊｕｓｔｏｌｆｅｒｓｏｍｅｓｉｍｐｌｅｃｌａｓｓｉｆｉｃａｔｊｏｎｆｕｎｃｔｉｏｎｅａｎｄｉｔｎｅｅｄｓｔｈｅｕｓｅｒｓｔｏｓｅｔｔｈｅｉｒｏｗｎｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓ．ＲｅｃｅｎｔｌｙｔｈｅｒｅｉＳｓｏｍｅｅｍａＪ１“ｌｔｅｒｉｎｇｒｅｌａｔｅｄｒｅｓｅａｒｃｈ，ａｎｄｍｏｓｔｏｆｔｈｅｍａｒｅｕｓｅｄｉｎＥｎｇｌｉｓｈａｎｄｃａｎｎｏｔｂｅｄｉｒｅｃｔｌｙｕｓｅｄｏｎｔｈｅＣｈｉｎｅｓｅｅｍａｉｌｃｌａｓｓｉｆｉｃａｔｉｏｎｓ．ＴｈｅＥｍａｉｌＳＩｎｔｅｌｌｉｇｅｎｔＣｌａｓｓｉｆｉｃａｔｉｏｎｕｎｄｅｒｔｈｅｗｉｎｄｏｗｓｅｎｖｉｒｏｎｍｅｎｔｉｎｔｒｏｄｕｃｅｄｂｙｔｈｉＳｐａｐｅｒｍａｄｅｓｏｍｅｓｐｅｃｉａｌｒｅｓｅａｒｃｈｆｏｒｔｈｅＣｈｉｎｅｓｅｃｌａｓｓｉｆｉｃａｔｉｏｎｓｈａｖｅｇｒｅａｔｒｅｓｅａｒｃｈｅｖａｌｕａｔｉｏｎ．
ＴｈｅｐｕｒｐｏｓｅｏｎｄｅｖｅｌｏｐｉｎｇｔｈｉｓｓｙｓｔｅｍｉＳｔｏｕｎｄｅｒｓｔａｎｄｔｈｅｃｕｒｒｅｎｔｅｍａｉｌｉｎｔｅｌｌｉｇｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎｒｅｓｅａｒｃｈａｎｄ１ｅａｒｎｓｏｍｅｆｕｎｄａｍｅｎｔａｌｃｏｎｃｅｐｔｓｏｎｔｈｅＣｈｉｎｅｓｅｅｍａｉｌｐｒｏｃｅｓｓｉｎｇｓｙｓｔｅｍ．Ｉｎｔｈｅｍｅａｎｗｈｉｌｅ，ｆｉｎｄｔｈｅｐｒｏｂｌｅｍｍｅｔｉｎｔｈｅｅｍａｉｌｃｌａｓｓｉｆｉｃａｔｉｏｎｄｅｖｅｌｏｐｍｅｎｔａｎｄｐｒｏｐｏｓｅｓｏｍｅ
ｔｈｅｐｒａｃｔｉｃｅ．
Ｄｅｗｉｄｅａｓａｎｄｕｎｄｅｒｓｔａｎｄｉｎｇｓａｆｔｅｒｔｈｅｓｔｕｄｙａｎｄ
Ｔｈｅｐａｐｅｒｍａｄｅｓｏｍｅｉｎｔｒｏｄｕｃｔｉｏｎｏｎｔｈｅｆｕｎｄａｍｅｎｔａｌｃｏｎｃｅｐｔｓａｎｄｔｈｅｏｒｉｅｓｆｏｒｔｈｅｄｏｃｕｍｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎｔｈｅｎｍａｄｅｓｏｍｅｓｉｍｐｌｅｉｎｔｒｏｄｕｃｔｉｏｎｏｆｔｈｅｄｅｖｅｌｏｐｉｎｇｐｒｏｃｅｓｓ．Ａｆｔｅｒｔｈｉｓ，ｉｔｆｏｃｕｓｅｄｏｎｔｈｅｄｅｔａｉｊｅｄｍｏｄｅｌｄｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｎｔｈｅＥｍａｉｌＳＩｎｔｅｌ］ｉｇｅｎｔｃｌａｓｓＪｆｉｃａｔｉｏｎ．Ａｎｄｆｉｈａｌｌｙ，ｍａｄｅｓｏｍｅｓｕｍｍａｒｙｆｏｒｔｈｅｃｕｒｒｅｎｔｍａｉｎｐｒｏｂｌｅｍｓｉｎｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｎｔｈｅＣｈｉｎｅｓｅＥｍａｉｌｓＩｎｔｅｌｌｉｇｅｎｔＣｌａｓｓＪｆｉｃａｔｉｏｎＳｙｓｔｅｍａｎｄｐｒｏｐｏｓｅｄｓｏｍｅｍｅｔｈｏｄｓａｎｄｉｄｅａｓｔｏｓｏｌｖｅｔｈｅｓｅｐｒｏｂｌｅｍｓ．ＴｈｉＳｐａｐｅｒａｌＳＯｐｏｉｎｔｅｄｏｕｔｔｈｅｔｅｎｄｅｎｃｙａｎｄｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｆｏｒｔｈｅＣｈｉｎｅｓｅＥｍａｉｌＳＩｎｔｅｌｌｉｇｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎａｎｄｇａｖｅｓｏｍｅｖａｌｕａｂｌｅｇｕｉｄｅｆｏｒｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｏｎｔｈｉＳｓｕｂｊｅｃｔ．
ＴｈｅｐｕｒｐｏｓｅｏｆｔｈｉｓｐａｐｅｒｉｓｔｏｄｅｓｉｇｎａｃｌａｓｓｉｆｉｃａｔｉｏｎｓｙｓｔｅｍｔｈａｔｉｓｓｕｉｔａｂｌｅｆｏｒｔｈｅＣｈｉｎｅｓｅｅｍａｉｌＳ．Ｉｎｔｈｅｐａｐｅｒｗｅｔｈｉｎｋｔｈｅｄｉｆｆｅｒｅｎｔ
ｔｈｅｓｕｉｔａｂｌｅｃｌａｓｓｉｆｉｅｒｒｅｓｐｅｃｔｉｖｅＪｙｐｒｏｐｅｒｔＪｅｓｆｏｒｔｈｅｅｍａｉｉｓｓｈｏｕｌｄｕｓｅ
．１ｌ?
山东大学硕士学位论文ａｎｄｗｅａｌｓｏｃｏｍｂｉｎｅｄｔｈｅｃｌａｓｓｉｆｉｅｒｓｔｏｐｒｅｄｉｃｔｔｈｅｔｙｐｅｏｆｔｈｅｅｍａｉｌｓ．Ｗｅｉｎｓｔａ］】ｅｄｔｈｉｓｅｍａｉｌｃｌａｓｓｉｆｉｅｒｏｎｔｈｅｃｌｉｅｎｔｃｏｍｐｕｔｅｒａｎｄｍａｄｅｔｈｅｃｌａｓｓｅｓｌａｂｅｌｆｏｒｔｈｅｅｍａｉｌｓｏｎｔｈｅｃｌｉｅｎｔ．ＴｈｅｅｍａｉｉａｐｐｌｉｃａｔｉｏｎｓｏｆｔｗａｒｅｃａｎｄｉｒｅｃｔｉＦｐｕｔｔｈｅｅｍａｉｌｓｔｏｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｆｏｌｄｅｒａｃｃｏｒｄｉｎｇｔｏｔｈｅｓｉｎｇｌｅｌａｂｅｌ，ａｎｄｔｈｉｓｗｉｌｌｇｒｅａｔｌＹｄｅｃｒｅａｓｅｔｈｅｍａｎｕａｌｃｌａｓｓｉｆｉｅａｔｉｏｎｓｂｙｔｈｅｕｓｅｒｓｏｒｔｈｅｂｕｒｄｅｎｆｏｒｔｈｅｕｓｅｒｓｔｏｍａｋｅｓｏｍｅｃｏｍｐｌｉｃａｔｅｄｃｌａｓｓｉｆｙｉｎｇｒｕｌｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓ’ｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｅｓｙｓｔｅｍｐｒｏｐｏｓｅｄｂｙｔｈｉｓｐａｐｅｒｃａｎｇｅｔｇｏｏｄａｃｃｕｒａｃｙｏｎｔｈｅＣｈｉｎｅｓｅｅｍａｉｌｓｃｌａｓｓｉｆｉｃａｔｉｏｎ．
Ｋｅｙｗｏｒｄｓ：Ｅ－ｒｅａｌｌ，ｃｌａｓｓｉｆｉｅｒ，Ｃｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ，ｐｒｅｃｉｓｉｏｎｆｅｃａｌｌ
．ＩＩＩ．
原创性声明
本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独
立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不
包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研
究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明
的法律责任由本人承担。
论文作者签名：Ｉ坌迦盗日期：ｏ盘Ｚ：三：弘
关于学位论文使用授权的声明
本人完全了解山东大学有关保留、使用学位论文的规定，同意学
校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论
文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分
内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段
保存论文和汇编本学位论文。
ｆ保密论文在解密后应遵守此规定）
论文作者签名：ｌ敞导师签名：鞯日期：２堡墼协
山东大学硕士学位论文１绪论
１．１问题的提出及其研究意义
Ｉｎｔｅｒｎｅｔ从７０年代诞生至今，其规模一直以爆炸式的速度发展。在Ｉｎｔｅｒｎｅｔ向我们提供海量的信息和服务的同时，“信息过载”等问题也随之产生了。信息过载是现代社会中产生的新问题，其根源是用户所能接触到的和需要处理的信息超过了他们所能处理的最大限度。通常表现为用户被太多的信息包围，没有足够的时间去整理过滤出有用的信息，然后来理解和运用他们。解决这个问题的一个有效方法就是采用计算机程序来帮助完成信息的搜集分类和检索等工作，这样大大减轻了人的工作负担，而且及时快速的帮助人们找到迫切需要解决的问题和迫切需要的信息。电子邮件作为Ｉｎｔｅｒｎｅｔ上另一项重要的传统服务［１］，同样也面临着信息过载的问题。
网络时代的人们饱尝垃圾邮件带来的烦恼，几乎每个人的信箱都充斥着大量来历不明的邮件，垃圾邮件像瘟疫一样蔓延、污染网络环境，影响网络的正常通信。根据调查［２］意大利在２００２年就有７００亿封电子邮件，而２００１年才有ＢＯＯ亿封。对一些业务繁忙的企业或个人来说，每天也许会收到上百封电子邮件，需要拿出大量的时间阅读和处理这些信件。因而需要用计算机程序来完成一些邮件的预处理工作，需要能够自动将邮件分类保存，按照重要程度标出优先级，自动对垃圾邮件进行过滤的处理软件。
目前大部分的电子邮件的收发软件，都提供能够减轻使用者邮件分类的的功能，不过需使用者自订邮件分类规则，如ＭｉｃｒｏｓｏｆｔＯｕｔｌｏｏｋ，仅提供使用者制定对特定几个字段内容，进行以关键词为基础的过滤规则。此方法的缺点为只考虑规则中数个关键词是否出现，并不全盘考虑文章中所有词汇在整个文档中应占的权重。并且，由人工分析并订定出能够涵盖并代表整个类别的一组规则是非常困难的。最近几年有许多邮件过滤的相关研究［３］［４］，但大部分的研究均针对英文文档来分类，并无法直接使用在中文邮件分类上。借由过去的文档自动分类相关研究及中文处理技术的方法，我们希望建构一个应用机器学习（ｍａｃｈｉｎｅ
ｌｅａｒｎｉｎｇ）技术来过滤邮件并能处理中文信息的邮件分类器。
山东大学硕士学位论文１．２国内外研究状况
关于文档的自动分类问题，国外研究进行的比较早，而且也有很多了成熟的技术和成果［５］［６］［７］［８］。但是绝大部分研究基于以英语文信息，因此主要索引的单位为英文词汇，然而，此种索引技术并无法直接应用在中文信息处理上。中文文档与英文文档最大的不同在于，英文文档中英文单词之间被空白或其它符号所分丌，而中文文档旱，中文词可由一个或两个以上的相邻中文字（ｃｈｊｔｉｅｓｅｃｈａｒａｃｔｅｒ）组成，中文词之间大多并无明显的边界（ｗｏｒｄｂｏｕｎｄａｒｙ）。国内在借鉴国外成果的基础上针对中文的文档分类也进行了大量的研究，也有很多不错的方法和实际应用，如常见的分类器（ｃｌａｓｓｉｆｉｅｒ）有ＴＦＩＤＦ分类器（ＴＦＩＤＦｃｌａｓｓｉ±’ｉｅｒ）［９］、ｋＮＮ分类器（ＫＮＮｃｌａｓｓｉｆｉｅｒ）［１０３、决策树分类器（ｄｅｃｉＳｉｏｎｔｒｅｅｃｌａｓｓｉｆｉｅｒ）［１１］［１２］、ｎａｉｖｅＢａｙｅｓ分类器（ｎａｉｖｅＢａｙｅｓｃｌａｓｓｉｆｉｅｒ）［１３］，支持向量机（ｓｕＰＰｏｒｔＶｅｃｔｏｒＭａｏｈｉｎｅｓ）［１４］。
１．３系统的功能和特色
本文提出的邮件智能分类系统，不仅可以对英文邮件进行分类，同时也可以对中文邮件进行分类。对中文邮件的分类过程中，可以根据系统的配置和分类精度的需要选择是否配备中文词库。系统根据其功能的实现不同，划分为了六个功能模块１．邮件接收与发送程序、２．邮件特征提取程序、３．决策树分类器、４．ＮａｉｖｅＢａｙｅｓ分类器、５．类别标记程序、６．中文词提取程序六部分组成。邮件接收与发送程序提供了经由ＳｇＴＰ协议与邮件服务器连接的能力。接收邮件后，系统会将邮件送至邮件特征提取程序中，邮件特征提取程序会从邮件资料区块取出分类器所需的特征，然后再送至决策树分类器来预测类别，若预测类别的结果有极高的可信度则直接将邮件送往类别标记程序，若预测类别的结果可信度不高，则将可能的发生的类别信息送往ｎａｉｖｅＢａｙｅｓ分类器，ｎａｉｖｅＢａｙｅｓ分类器预测出结果后，将邮件送往类别标已程序。类别标记程序为邮件加上类别符号，中文词提取程序则使用来提取出邮件中的中文词，产生系统所需的中文词库。
具体来说，邮件智能分类系统的主要功能有：
（１）丁Ｆ常接收和发送邮件；
（２）对邮件进行『Ｅ确的分类；
（３）清除和拒绝垃圾邮件：
（４）更新训练资料。
该系统的重点是研究邮件分类算法的设计与实现．该系统工作在客户端。考虑到很多企业和个人在邮件处理程序上采用了Ｏｕｔｌｏｏｋ２０００这个软件，因此将邮件分类程序作成了Ｏｕｔ］ｏｏｋ２０００的一个插件，这样既利用了Ｏｕｔｌｏｏｋ２０００在邮件管理的上的强大功能，又实现了邮件分类的增值功能。该版本代码部分主要是用ＶｉｓｕａｌＢａｓｉｃ［１５］实现的。邮件训练和词库的数据库采用了目前比较流行的ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ２０００［１６］［１７］作为其后台数据库服务器，它将作为一个可升级的、可靠的并且易于使用的产品为企业用户所青睐。它能够缩放，以适用从便携式计算到企业级应用等各种规模，它们可以使用完全相同的代码，提供了Ｉ（１０％的代码兼容性。ＳＱＬＳｅｒｖｅｒ２０００能够与ｗｉｎｄｏｗｓ２０００ｓｅｒｖｅｒ最佳无缝集成。本课题数据库部分的开发采用了ＭＦＣＯＤＢＣ技术。ＯＤＢＣ提供了一种统一访问数据库的接口，但是直接使用ＯＤＢＣＡＰＩ创建应用程序需要编制大量的代码。而ＭＦＣＯＤＢＣ将ＯＤＢＣＡＰＩ函数进行了封装，大大简化了数据库开发的编程工作。对于相对简单的数据库应用程序，使用ＭＦＣＯＤＢＣ是一个合适的选择。
本系统的主要特点有：
（１）可以对邮件进行智能分类
（２）分类速度快。
（３）分类精度较高。
（４）可以选择加挂词库和无词库２种方式。
－３－
２相关的主要研究
２．１相关的协议和技术规范
目前互连网上，Ｅｍａｉｌ的使用是越来越广泛了。在所有的ＴＣＰ连接线路中，大概有一半的线路是用来收发Ｅｍａｉｌ的。电子邮件类软件作为Ｉｎｔｅｒｎｅｔ上的应用软件，其设计开发必须符合Ｉｎｔｅｒｎｅｔ上成熟的技术规范（如ＲＦＣ文档系列规范）和相关协议（如ＳｈＩＴＰ、ＰＯＰ、ＩｂｌＡＰ以及ＭＩＭＥ等）。只有在遵循了上述规范和协议的基础上进行编程才能真正实现邮件类软件产品和服务的开放性和标准化。目前大多数ＥＭＡＩＬ系统都是使用ＳＭＴＰ协议来作为发送协议，使用ＰＯＰ３扔议来作为接受协议。下面我重点介绍一下ＳＭＴＰ协议和ＰＯＰ３协议，简单介绍ＩＭＡＰ以及ＭＩＭＥ协议。
２．１．１ＳＭＴＰ协议
ＳＭＴＰ（ＳｉｍｐｌｅＭｅｓｓａｇｅＴｒａｎｓｆｅｒＰｒｏｔｏｃ０１）简单邮件传输协议［１８］是ＴＣＰ／ＩＰ协议族［１９］［２０］中的一员，主要对如何将电子邮件从发送方地址传送到接收方地址，也即是对传输的规则做了规定。
ＳＭＴＰ协议通讯模型
ＳＭＴＰ协议的通信模型并不复杂，主要工作集中在发送ＳＭＴＰ和接收ＳＭＴＰ上：首先针对用户发出的邮件请求，由发送ＳＭＴＰ建立一条连接到接收ＳＭＴＰ的双工通讯链路，这里的接收ＳＭＴＰ是相对于发送ＳＭＴＰ而言的，实际上它既可以是最终的接收者也可以是中间传送者。发送ＳＭＴＰ负责向接收ＳＭＴＰ发送ＳＭＴＰ命令，而接收ＳＭＴ９则负责接收并反馈应答。可大致用下面的通讯模型示意图来表示：
ＳＭＴＰ通讯模型示意图
图１ＳＭＴＰ通讯模型示意圈
ＳＭ一１Ｐ｜办议的命令和应答
从前面的通讯模型可以看出ＳＭＴＰ协议在发送ＳＭＴＰ和接收ＳＭＴＰ之间的会话是靠发送ＳＭＴＰ的ＳＭＴＰ命令和接收ＳＭＴＰ反馈的应答柬完成的。在通讯链路建立后，发送ＳＭＴＰ发送ＭＡＩＬ命令指令邮件发送者，若接收ＳＭＴＰ此时可以接收邮件则作出ＯＫ的应答，然后发送ＳＭＴＰ继续发出ＲＣＰＴ命令以确认邮件是否收到，如果接收到就作出０Ｋ的应答，否则就发出拒绝接收应答，但这并不会对整个邮件操作造成影响。双方如此反复多次，直至邮件处理完毕。ＳＭＴＰ协议共包含１０个ＳＭＴＰ命令，列表如下：
一～一
…＿一———一
＾一——一————————＿－———一———————————’＿——————————————————＾…—————一：ＳＭ。”命令
：命令说明Ｊ：ＨＥＩ，１．０＜ｄｏｍａｉｎ＞＜ＣＲＬＦ＞：识别发送方到接收ＳＭＴＰ的一个ＨＥＬＬＯ命令！＜ｒｅｖｅｒｓｅ～ｐａｔｈ＞为发送者地址。此命令告诉接ｉ：
；’收方一个新邮件发送的开始，并对所有的状态和｛撇儿ＦＲＯＭ：＜ｒｅｖｅｒｓｅ—Ｄａｔｈ＞＜。
ｌ‘：缓冲区进行初始化。此命令开始一个邮件传输处ｌＣＲＬ，Ｆ＞ｊ
：；理，最终完成将邮件数据传送到一个或多个邮箱ｉ
ｌ！ＲＣＰ＇Ｉ’ＴＯ：＜ｆｏｒｗａｒｄ－ｐａｔｈ＞＜ＣＲＬＦＩ
ｌｊ＜ｆｏｒｗａｒｄ—ｐａｔｈ＞标识各个邮件接收者的地址ｌ＞！｝．———，．．—．—?—；——．—．＋—．—－—．——！——一—一：；
ｌ｛｝ｉＤＡＴＡ＜ＣＲＬＦ＞接收ＳＭＴＰ将把其后的行为看作邮件数据去处理，ｉ
ｌ以＜ＣＲＬＦ＞，＜ＣＲＬＦ＞标识数据的结尾。
ＲＥＳＴ＜ＣＲＬＦ＞
：退出／复位当前的邮件传输ＮＯＯＰ＜ＣＲＬＦ＞ｊ要求接收ＳＭＴＰ仅做ｏＫ应答。（用于测试）ＱＵＩＴ＜ＣＲＬＦ＞｛要求接收ＳＭＴＰ返回一个ｏＫ应答并关闭传输。
ＶＲ｝、Ｙ＜ｓｔｒｉｎｇ＞＜ＣＲＬＦ＞
验证指定的邮箱是否存在，由于安全因素，服务
器多禁止此命令。
Ｌｘ州＜ｓｔｒｉｎｇ＞＜ＣＲＬＦ＞！验证给定的邮箱列表是否存在，扩充邮箱列表，１
一一—．—．——。．—————．．———．．——————————．————，————Ｌ————————————————————?———————————————————————————”——————————＋———一－Ｓ．
山东大学硕士学位论文
一景景罢喜＝景＝詈！！鼻鼻！＝！！黑兽喜！景＝＝！等＝烹詈鼻！鼻喜！罢呈＝鼻詈呈喜景＝＝＝鼻尝喜詈＝竺！！！！！！景鼻＝！謇也常禁止使用。
——，一…～一———一一…一…一－＿。●＿一一一～。＿
ＥＬＰ＜ＣＲＬＦ＞碴询服务器支持什么命令
洼：＜ＣＲＬＦ＞为回车、换行，ＡＳＣＩＩ码分别为１３、ｉ０（十进制）。
ＳＭＴＰ协议的每一个命令都会返回一个应答码，应答码的每一个数字都是有特定含义的，如第一位数字为２时表示命令成功；为５表失败；３表没有完成。一些较复杂的邮件程序利用该特点，首先检查应答码的首数字，并根据其值来决定下一步的动作。下面将￥ＭＴＰ的应答码列表如下：
‘
…—。一——…‘———。。。’’。。。。＿＿‘—。一
应答码浇明５０ｌ５０２参数格式错误
………一一一一一…’一一
命令不可实现
５０３：错误的命令序列５（１４；命令参数不可实现ｉ——一—————二————．———．．．．．．．．．———．．—．．—．．．．．．．．．——．———————————。————————————————————————————————————一一２ｊ１系统状态或系统帮助响应｛２１４２２０２２１帮助信息
＜ｄｏｍａｉｎ＞服务就绪
＜ｄｏｍａｉｎ＞服务关闭
４２１。＜ｄｏｍａｉｎ＞服务未就绪，关闭传输信道
一一，＿————————————
２５０要求的邮件操作完成；——一～————二——————————．。．．．———．————————?———－—??————————————————————————————————————————————————’—。。。■２５１用户非本地，将转发向＜ｆｏｒｗａｒｄ—ｐａｔｈ＞
４５０要求的邮件操作未完成，邮箱不可用
５５０
要求的邮件操作未完成，邮箱不可用……一————一一一一一４５１
放弃要求的操作；处理过程中出错５５１；用户非本地，：…一一一请尝试＜ｆｏｒｗａｒｄ—ｐａｔｈ＞
４５２．系统存储不足，要求的操作未执行
５５２－过量的存储分配，要求的操作未执行
５５３；邮箱名不可用，要求的操作未执行．．６．
山东大学硕士学位论文３５４丌始邮件输入，以”．”结束
５５４操作失败
２．１．２ＰＯＰ３协议
ＰＯＰ３（ＰｏｓｔＯｆｆｉｏｅＰｒｏｔｏｃｏ］）邮局协议是该协议的第３的版本［２１］。ＰＯＰ３是Ｉｎｔｅｒｎｅｔ上的大多数人用来接收邮件的机制，它规定怎样将个人计算机连接到Ｉｎｔｅｒｎｅｔ的邮件服务器和下载电子邮件的电子协议。它是因特网电子邮件的第一个离线协议标准，ＰＯＰ３允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上，同时删除保存在邮件服务器上的邮件，而ＰＯＰ３服务器则是遵循ＰＯＰ３协议的接收邮件服务器，用来接收电子邮件的。
对于在网络上的ｔＥ较小的结点，支持消息传输系统（ＭＴＳ）是不实际的。例如，一台工作站可能不具有充足的资源允许ｓ婀Ｐ服务器和相当的本地邮件传送系统保持驻留，并持续运行。同样的，将一台个人计算机长时间连接在ＩＰ类型网络上的费用也是可观的。
虽然如此，在这样的小结点上允许管理邮件是十分有用的，并且这些结点经常支持一个用户代理来管理邮件。为解决这一问题，能够支持ＭＴＳ的结点就为这些不能支持的结点提供了邮件存储功能。邮局协议一版本３就是使这样的工作站可以用一种比较实用的方法来访问存储于服务器上的储存邮件。通常，这意味着工作站可以从服务器上取得邮件，而服务器为它暂时保存邮件。
在下文中，客户主机指的是利用ＰＯＰ３服务的主机，而服务器主机指的是提供ＰＯＰ３服务的主机。
初始时，服务器通过侦听ＴＣＰ端口１１０开始ＰＯＰ３服务。当客户主机需要使用服务酬，它将与服务器主机建立ＴＣＰ连接。当连接建立后，ＰＯＰ３发送确认消息。客户和ＰＯＰ３服务器相互（分别）交换命令和响应，这一过程一直要持续到连接终止。
ＰＯＰ３命令由一个命令和一些参数组成。所有命令以一个ＣＲＬＦ对结束。命令和参数由可打印的ＡＳＣＩＩ字符组成，它们之间由空格间隔。命令一般是三到四个字母，每个参数却可达４０个字符长。
ＰＯＰ３响应由一个状态码和一个可能跟有附加信息的命令组成。所有响应也是由ＣｎＦ对结束。现在有两种状态码，“确定”（“＋ＯＫ”）和“失败”（“一ＥＲＲ”）。
对于特定命令的响应是出许多字符组成的。在这些情况中，下面一一表述：在发送第一行响应和一个ＣＲＬＦ之后，任何的附加信息行发送，他们也由ＣＲＬＦ列
山东大学硕士学位论文结束。当所有信息发送结束时，发送最后一行，包括一个结束字符（十进制码４６，也就是“．”）和一个ＣＲＬＦ对。如果信息中的任何一行以结束字符开始，此行就是通过在那一行预先装入结束而进行字符填充的。因此，多行响应由五个ＣＲＬＦ．ＣＲＬＦ结束。当检测多行响应时，客户检测以确认此行是否以结束字符丌始。如果是的，而且其后的字符不是ＣＲＬＦ，此行的第一个字符（结束字符）将被抛弃；如果其后紧跟ＣＲＬＦ，从ＰＯＰ服务器来的响应终止，包括．ＣＲＬＦ的行也不被认为是多行响应的一部分了。
在生命周期中，ＰＯＰ３会话有几个不同的状态。一旦ＴＣＰ连接被打开，而且ＰＯＰ３服务器发送了确认信息，此过程就进入了“确认”状态。在此状态中，客户必须向ＰＯＰ３服务器确认自己是其的客户。一旦确认成功，服务器就获取与客户邮件相关的资源，此时这～过程进入了“操作”状态。在此状态中，客户提出服务，当客户发出ＱＵＩＴ命令时，此过程进入了“更新”状态。在此状态中，ＰＯＰ３服务器释放在”操作”状态中取得的资源，并发送消息，终止连接。
ＰＯＰ３服务器可以搠有一个自动退出登录的记时器。此记时器必须至少可以记录１０分钟。这样从客户发送的消息才可能刷新此记时器。当记时器失效时，ＰＯＰ３会话并不进入“更新”状态，而是关闭ＴＣＰ连接，而且不删除任何消息，不向客户发送任何响应。
“确认””状态：这时ＴＣＰ连接由ＰＯＰ３客户打开，ＰＯＰ３服务器发送一个单行的确认。这个消息可以是由ＣＲＬＦ结束的任何字符。例如，它可以是：Ｓ：＋ＯＫＰＯＰ３ｓｅｒｖｅｒｒｅａｄｙ
注意：这个消息是一个ＰＯＰ３应答。ＰＯＰ３服务器应该给出一个“确定”响应作为确认。
此时ＰＯＰ３会话就进入了“确认”状态。此时，客户必须向服务器证明它的身份。在文档中介绍两种可能的处理机制，一种是ＵＳＥＲ和ＰＡＳＳ命令，另一种是在后面要介绍的ＡＰＯＰ命令。
用ＵＳＥＲ和ＰＡＳＳ命令进行确认过程，客户必须首先发送ＵＳＥＲ命令，如果ＰＯＰ３服务器以“确认”状态码响应，客户就可以发送ＰＡＳＳ命令以完成确认，或者发送ＱＵＩＴ命令终止ＰＯＰ３会话。如果ＰＯＰ３服务器返回”失败”状态码，客户可以再发送确认命令，或者发送ＱＵＩＴ命令。
当客户发送了ＰＡＳＳ命令后，服务器根据ＵＳＥＲ和ＰＡＳＳ命令的附加信息决定是否允许访问相应的存储邮件。
一旦服务器通过这些数据决定允许客户访问储存邮件，服务器会在邮件上加上排它锁，以防止在进入”更新”状态前对邮件的改变。如果成功获得了排它锁，
臌务器返回一个“确认”状态码。会话进入“操作状态”，同时没有任何邮件被标汜为删除。如果邮件因为某种原因不能打开（例如，排它锁不能获得，客户不能访问相应的邮件或者邮件不能进行语法分析），服务器将返回”失败”状态码。征返回“失败”状态码后，服务器会关闭连接。如果服务器没有关闭连接，客户可以重新发送确认命令，重新开始，或者发送ＱＵＩＴ命令。
在服务器打开邮件后，它为每个消息指定一个消息号，并以八进制表示每个消息的长度。第一个消息被指定为ｌ，第二个消息被指定为２，以此类推，第Ｎ个消息被指定为Ｎ。在ＰＯＰ３命令和响应中，所以的消息号和长度以十进制表示。
“操作”状态：一旦客户向服务器成功地确认了自己的身份，服务器将会锁住并打开相应的邮件，这时ＰＯＰ３会话进入“操作”状态。现在客户可以重复下面的ＰＯＰ３命令，对于每个命令服务器都会返回应答。最后，客户发送ＱＵＩＴ命令，会话进入“更新”状态。
“更新”状态：当客户在“操作”状态下发送ＱＵＩＴ命令后，会话进入“更新”状态。（注意：如果客户在”确认”状态下发送ＱＵＩＴ后，会话并不进入”更新”状态。）
如果会话因为ＱＵＩＴ命令以外的原因中断，会话并不进入“更新”状态，也不从服务器中删除任何信件。
２．１．３ＩＭＡＰ协议
ＩＭＡＰ（ＩｎｔｅｒｎｅｔＭｅｓｓａｇｅＡｃｃｅｓｓＰｒｏｔｏｃ０１）网络消息访问协议［２２］，主要提供的是通过Ｉｎｔｅｒｎｅｔ获取信息的一种协议。ＩＭＡＰ４是ＩＭＡＰ协议的第４个版本，正如ＰＯＰ３是ＰＯＰ协议的第３个版本一样。
ＩＭＡＰ和ＰＯＰ３的区别：由于很多用户都对ＰＯＰ３非常熟悉，我们就从ＰＯＰ３说起。ＰＯＰ３提供了快捷的邮件下载服务，用户可以利用ＰＯＰ３把邮箱里的信下载到Ｐｃ上进行离线阅读。一旦邮件进入Ｐｃ的本地硬盘，就可以选择把邮件从服务器上删除，然后脱离与Ｉｎｔｅｒｎｅ％的连接并选择在任何时候阅读已经下载的邮件。ＩＭＡＰ同样提供了方便的邮件下载服务，让用户能进行离线阅读，但ＩＭＡＰ能完成的却远远不只这些。
首先，ＩＭＡＰ提供的摘要浏览功能可以让你在阅读完所有的邮件到达时间、主题、发件人、大小等信息后才作出是否下载的决定。也就是说，你不必等所有的邮件都下载完毕后才知道究竟邮件里都有些什么。如果你根据摘要信息就可以决定某些邮件对你毫无＿辟ｊ｜处，你就可以直接在服务器上把这些邮件删除掉，而不必浪费你宝贵的上网时间。如果你的ＩＭＡＰ客户端软件完整支持ＩＭＡＰ４ｒｅｖｌ的话（如
－９－
Ｎｅｔｓｃａｐｅ４．５），则你还可以享受选择性下载刚件的服务。举例来说，假如一封邮件里含有不同大小的５个附件，而其中只有２个附件是你需要的，你就可以只Ｆ载那两个附件，节省了下载其余：｛个的时间。
和ＷｅｂＭａｉｌ的比较：也有很多用户喜欢通过Ｗｅｂ来联机收发邮件，其中～个很重要的原因是这些用户希望把他的邮件都留在服务器上，并且通过ＷｅｂＭａｉｌ服务建立多个文件夹，然后分类归档地管理自己的邮件。这样，ＷｅｂＭａｉｌ的用户就可以不分时间地点，只要有一个浏览器就可以马上从服务器上获得自己的邮件，不管是刚收到的还是已经存放了很久，也不必担心客户端的Ｐｃ重新安装了操作系统或换了一台电脑以后邮件全部丢失了的问题。ＩＭＡＰ同样满足了ＷｅｂＭａｉｌ用户的需要。ＴＭＡＰ与ＰＯＰ３不同的地方关键是在支持离线阅读的同时也鼓励用户把邮件存储和组织在服务器上。和ＷｅｂＭａｉｌ一样，通过ＩＭＡＰ，允许用户在服务器．卜建立任意层次结构的文件夹，并且可以灵活地在文件夹之间移动邮件，随心所欲地组织你的邮箱（这些显然是通过ＰＯＰ３做不到的）。只要你的邮件存储在服务器上，任何时候通过一个ＩＭＡＰ的客户端软件都可以立即联机获得你的邮件，这一点与ｆｆｅｂＭａｉｌ保持一致。但是，ＩＭＡＰ具有以下优点：凡是ＷｅｂＭａｉｌ的用户都必需无奈地阅读页面上的广告，都必需花费宝贵的时间和带宽来下载页面上的图片、修饰字符等等；ＩＭＡＰ则忠实地只为你的Ｅｍａｉｌ服务，不让你的资源有丝毫的浪费。此外，Ｉ鼢Ｐ协议还允许你方便地利用你的邮箱作为信息存储工具，一般的ＩＭＡＰ４客户软件都支持邮件在本地文件夹间和服务器文件夹间的随意拖动，让你得心应手地把本地硬盘上的文件存放到服务器上，然后在你需要的时候同样方便地取回来。
２．１．４ＭＩＭＥ协议
ＭＩＭＥ（ＭｕｌｔｉｐｕｒｐｏｓｅＩｎｔｅｒｎｅｔＭａｉｌＥｘｔｅｎｓｉＯｎＰｒｏｔｏｃ０１）多用途的网际邮件扩充协议，它不是～种邮件传输协议。ＭＩＭＥ规定了通过ＳＭＴＰ协议传输非文本电子邮件附件的标准。。它定义传输的内容：消息的格式、附件等。许多文档都定义了ＭＩＭＥ协议，包含：ＲＦＣ８２２、ＲＦＣ２０４５、ＲＦＣ２０４６和ＲＦＣ２０４７。现在绝大多数邮件系统都支持ＭＩＭＥ协议。
２．２文档自动分类
文档分类（ｄｏｃｕｍｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎ）是将一群文档依据文档特征将它们分别归类到一个或多个事先定义好的类别。文档分类一直是信息提取（ｉｎｆｏｒｍａｔｉｏｎ
ｒｅｔｒｉｅｖａｌ）领域上的～项很重要的研究。且随着现今电子信息，如网页、电子邮件，数量呈等比级数般的增长，文档自动分类技术的研究越显得有其必要性与实用性。传统以人工来进行过滤分类文档将越来越不可行。文档分类已经成为处理和组织大规模文档数掘的关键技术。现有文档分类技术基本上是基于词信息１２４］，这使得文档分类需要借助于词典和使用专门的词提取技术。在文档分类方法中，文档的表示方法（ｄｏｃｕｍｅｎｔｒｅｐｒｅｓｅｎｔａｔｉｏｎ）因系统使用不同的分类器而有所不同［２５］。常见的分类器有ＴＦＩＤＦ分类器、ＫＮＮ分类器、决策树分类器、ｎａｉｖｅＢａｙｅｓ分类器，ＳＶＭ等。
２．２．１ＴＦＩＤＦ分类器
ＴＦＩＤＦ（ＴｅｒｍＦｒｅｑｕｅｎｃｙ．ＩｎｖｅｒｔＤｏｃｕｍｅｎｔＦｒｅｑｕｅｎｃｙ）其实应算是文档词汇加权（ｔｅｒｍｗｅｉｇｈｔｉｎｇ）［２６］的一种方法，因为以ＴＦＩＤＦ取权重为基础的相似方法，大量的被使用在各种文档分类器上。所以我们通过一个属于基于质心的分类器（ｃｅｎｔｒｏｉｄｂａｓｅｄｃｌａｓｓｉｆｉｅｒ）［２７］的例子，来说明ＴＦＩＤＦ的计算方式，基于质心的分类器使用单一质心向量来描述一个类别，举例来说，第ｉ个类９Ｊｆｆ］质心１．ｈ量ｄ为类别内所有文档向量｛厅ｌｄ∈Ｃｉ）的总和，即
ｃｉ－三ｙｄ（式２一１）
＂篇，
其中ｄ为文档向量，ｄ＝（ｄ“’，ｄ。，…，ｄ“…’），ｄ“’表示第Ｊ个词汇ｗｊ在文档ｄ中的权重（ｗｅｉｇｈｔ），Ｉｄｌ为文档向量的长度，ｎ为Ｃｉ中的文档数。文档向量内每一维度的权重则是以ＴＦＩＤＦ来给定。ＴＦＩＤＦ计算方法如（式２—２）所示：ｄ。’＝Ｉ＂Ｆ（ｗｊ，ｄ）?ＩＤＦ（ｗｊ）
其中ＴＦ“ｊ，ｄ）为关键词ｗｊ在文档ｄ中出现的次数，
肼㈨卜蛔Ｉ器ｌ
ＤＦ（ｗｊ）为文档中有出现关键词ｗｊ的文档篇数。由ＤＦ方程式得知，当关键词在文档ｄ中出现次数越频繁，ＴＦ值则会越高代表此关键词对文档ｄ来说越重要，当关键词在越少的文档出现，ＩＤＦ值则会越高，代表此关键词对文档ｄ来说越具有代表性。相反来浇，当关键词在文档ｄ出现次数越少，ＴＦ值则会越低，代表此关键词对文档ｄ来说越不重要，当关键词在越多的文档出现，ＩＤＦ
?ｔ１－
山东大学硕士学位论文值则会越低，代表此关键词对文档ｄ来说越不具有代表性。
壤后，指定在所有类别里与文档ｄ相似程度最高的类别给文档ｄ。如（式２－３）所示，类别向量与文档向量的相似程度的比较是由一相似度函数（ｓｉｍｉｌａｒｉｔｙｆｕｎｃｔｉｏｎ），Ｓｉｍ（），来决定。
‰¨ｆ’一”ｇＩ㈨ｉＱａｘ８ｉｍ（。ｊ～）（式２—３）
其中Ｃ表示所有类别的集合，ｃｊ为第ｊ个类别，代表类别ｃｊ的权重向量，ｄ代表文档ｄ的文档向量。
在向量空间模式中，最常被使用来设计相似度函数的工具为余弦系数（ＣＯＳｉｆｉｅｃｏｅｆｆｉｃｉｅｎｔ），余弦系数公式如下式所示：
余弦系数
其中Ｘ、Ｙ为两文档向量，Ｘ＝（ｘ，，ｘ。，…，Ｘ。），Ｙ＝（Ｙ；，Ｙ∥“，Ｙ。），ｔ则为ｘ与Ｙ的维度。
由余弦系数方程式（式２－３）我们可得知，当两文档向量的维度之间的比例均相同，即两向量互相平行，向量间夹角为０，两向量的余弦值为１，代表着两文档有极高的相似度。反之，当两文档向量的每一维度比例越不楣同，余弦值为将越低，代表着两文档并不相似。另外，Ｊａｃｃａｒｄ系数（Ｊａｃｃａｒｄｃｏｅｆｆｉｃｉｅｎｔ）与Ｄｉｃｅ系数（Ｄｉｃｅｃｏｅｆｆｉｃｉｅｎｔ）也是两个常被用来钡０量两向量间相似性程度的工具。］ａｃｃａｒｄ系数与Ｄｉｃｅ系数的方程式如下所示：
Ｊａｃｃａｒｄ系数式
Ｊａｃｃａｒｄ（Ｘ．Ｙ）：！薹：＝！鲨（２吲
味Ｊ卜墨ｔＦ．２券ｔ面．２ｔ?－他＿’其中ｘ、Ｙ为两文档向量，Ｘ＝（ｘ。ｘ：，…，ｘ。），Ｙ＝（ｙ－，ｙ：，…，ｙ．），ｔ则为ｘ与Ｙ的维度。
Ｄｉｃｅ系数
Ｄｉｃｅ（Ｘ，Ｙ）２夏２面∑＇，ｘｉｙｉｃｚ训
其中ｘ、Ｙ为两文档向量，Ｘ＝（ｘ；，Ｘ矿”，ｘ。），Ｙ＝（ｙ，，Ｙｂ…，ｙ。），ｔ则为Ｘ与Ｙ的维度。－１２－
２．２．２基于ｋＮＮ法的文档分类
ｋＮＮ分类器属于基于个例的分类器（ｉｎｓｔａｎｃｅｂａｓｅｄｃｌａｓｓｊｆｉｅｒ）。ｋＮＮ分类器在学习阶段只是简单的将每笔训练数据（ｔｒａｉｎｉｎｇｄａｔａ）作适当的表示后便储存起来，就完成了训练工作。当有一笔测试数据（ｔｅｓｔｄａｔａ）需要分类时，再将测试数据与所有训练数据逐一比对，找出ｋ笔最近的调练数据，再依据这ｋ个训练数据所属的类别，与这ｋ个训练数据和测试数据间的距离来评估此测试数据最后应归属的类别。基于个例的分类器可以算是没有训练时间，等到有新的测试数据时才开始作处理，因此这种学习又称为懒惰学习（１ａｚｙｌｅａｒｎｉｎｇ）或延迟学习（ｄｅｌａｙｌｅａｒｎｉｎｇ）。
在ｋＮＮ文档分类方法中，所有文档均用向量空间模型表示。因此，一个文档就是文档向量空间中的一个向量，这个向量也称为文档向量。文档向量中各个维对应于用于表征文档的各个词（词组），这也就是文档属性。对于某一具体文档，其向量中各个维的值为该向量维对应的词在文档库中的权值［２８］。
对于文档库Ｄ，假设对应的文档属性集为Ｖ，Ｖ＝｛Ｗｉｌ，（ｉ＝ｌ’ｔｑ）。现有一文档ｄ，用向量模型表示为：
ｄ＝（ｗｌ，Ｗｂ…，Ｗ。）
上面的Ｗ．（ｉ＝ｌ’ｎ）为属性ｗｉ对应的权值。权值的计算一般采用ＴＦＩＤＦ估算方法。ｋＮＮ方法进行文档分类的过程如下：对于某一给定的测试文档ｄ，在训练文档集中，通过相似度找到与之最相似的ｋ个训练文档。在此基础上，给每一个文档类打分，分值为ｋ个训练文档中属于该类的文档与测试文档之间的相似度之和。也就是说，如果在这ｋ个文档中，有多个文档同属于一个类，则该类的分值为这些文档与测试文档之闻的相似度之和。对这ｋ个文档所属类的分值统计完毕后，即按分值进行排序。还应当选定一个闽值，只有分值超过阈值的类才予以考虑。测试文档属于超过闽值的所有类。形式化表示为：
Ｓｃｏｒｅ（云，Ｃｉ）＝∑Ｓｉｍ（ｄ一，ａ—ｙ）ｙ（ｄ—ｊ，ｃｉ）一ｂｉ（式２－７）
式中ｙ（巧，ｃ。）＝ｌ巧∈ｃ
Ｙ（巧，Ｃ，）＝ｏ巧《Ｃ
－１３．
１１．为阀值：
ＳＣＯＦｅ（ｃ，，Ｃ．）为测试文档ｄ属于Ｃ，类的分值。
对于某一特定类来说，ｂ，是一个有待优化选择的值。一般，ｂ。可以通过一个验证文档集来进行凋整。验证文档集是训练文档集的一部分。根掘式（２－７）的结果，呵以确定测试文档的类别。很显然，对于每一个测试文档，必须求解它和训练文档库中所有文档的相似度。因此，ｋＮＮ方法的时间复杂度为
０（｜Ｄｎ，）。（注：｜ＤＩｎ，与分别为训练文档总数和测试文档总数）
ｋＮＮ分类器的优点为在训练资料文档量很少的时候，效果不错。但其最主要的缺点为当训练数据量很多或者特征向量（ｆｅａｔｕｒｅｖｅｃｔｏｒ）的维度（ｄｉｍｅｎｓｉｏｎ）很高时，若没事前做适当的处理，例如，分割（ｐａｒｔｉｔｉｏｎ）文档集、缩小文档集项目等，分类时将会需要许多的大量的计算，因此速度与基于质心的分类器比较起来相对慢一些。
２．２．３决策树分类器
决策树（ｄｅｃｉｓｉｏｎｔｒｅｅ）被广泛的应用在分类问题上。而常见的决策树分类器有
ＩＤ３［２９］及ｃ４．５［３０］等。决策树分类器的主要优点为其结果可转成容易为人所解读的ＩＦ－ＴＨＥＮ法则（ＩＦ—ＴＨＥＮＲｕｌｅ），分类速度快。
决策树模型建立的基本策略为一开始以～个根节点（ｒｏｏｔｎｏｄｅ）代表所有资料。若节点（ｎｏｄｅ）内的所有的训练数据均属于同～类别，则此节点便成为叶节点（１ｅａｆｎｏｄｅ），否则，就测量并选择一个属性，此属性最能将训练数据分割成单一类别自成一群。每一内部节点代表一个属性，这～个属性为此节点上的测试属性（ｔｅｓｔａｔｔｒｉｂｕｔｅ）；节点的每个分支（ｂｒａｎｃｈ）代表＿；９１０试属性所有可能的数值，而节点内的训练数据依据此数值被切割至子节点内。算法依据相同的方法，递归的将每群数据分割，推导出整个决策树，当节点里的所有训练数据大部分为相同类别时，便停止分割。
２．２．４ＮａｉｖｅＢａｙｅｓ分类器
ＮａｉｖｅＢａｙｅｓ分类器被广泛的使用在文档分类上。并且根据过去文献［３１］［３２］显示，ＮａｉｖｅＢａｙｅｓ在文档分类的应用上有相当不错的表现。ＮａｉｖｅＢａｙｅｓ分类器做了一个简化的假设，对于结果来说每个参数之间出现的机率是互相独立的。此简化的假设使ＮａｉｖｅＢａｙｅｓ分类器有简单快速的特性。不过大部分情况
一１４－
山东大学硕士学位论文Ｆ参数出现的机率是并不是互相独立的，对预测的结果来说，此一简化的假设也耗损了一些精确度。如（式２－８）所示，
Ｐ（ｄＩｃ－）２ｎＰ（ｄ．ＩＣｋ）
／＝Ｉ
ＮａＪｖｅＢａｙｅｓ分别计算在一给定文档下，文档归属于每一类别的机率，并将文档的类别指定给机率最高的类别。公式ｄ表示文档向量，ｄ＝（ｄ，，ｄ。…，ｄ。），Ｉｎ为文档向量的维度，Ｎ为类别数目，Ｃｋ表示第ｋ个类别。
２．２．５ＳＶＭ分类器
支持向量机（ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅｓ）是一种分类器，最早由Ｖａｐｎｉｋ在１９７９年提出，当时没有得到重视，随后Ｖａｐｎｉｋ等人花了很长时间完善统计模式识别的基本数学理论，随着结构风险最小准则的提出，ＳＶＭ的理论基础基本完备，终于引起注意。直到最近，它才成为一个研究上的热点，并开始得到非常广泛的应用。和传统的分类器，例如神经网络相比，它从理论上解决了神经网络难以控制自身推广能力的问题，找到了计算实际识别中分类器错误率上界（但是只是上界）的方法。
支持向量机（ＳＶＭ）是一种建立在统计学习理论基础上的机器学习方法［３３］［３４］。通过该学习算法，ＳＶＭ可以自动寻找那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的推广性能和较高的分类准确率。
支持向量机ＳＶＭ是一个预先定义了参数的函数集合，训练一个ＳＶＭ就是由一个训练样本集来得到此集合中各个函数的参数，ｎ个样本的训练集可以训练出ｎ个自由的参数谢。为了得到ａ，必须求解二次最优问题。因为涉及到一个ｎ×ｎ的矩阵，尽管形式比较简单，但是在训练样本的数量总体上较大的情况下，必须采用适当的算法来解决这一问题。目前比较常用的有复杂数据结构法、分解法和ｓＭＯ法等。其中ＳＭＯ法速度更快～些［３５］。一般情况下，用ｓＶＭ方法进行分类的过程可以描述为：
（１）通过求解一个约束条件下的二次最优问题，得到使
ｎ
Ｍａｒｇｉｎ＝２／１（＾）１最大的∞＝（ｙ耐＋Ｙｄ，）和分类闽值ｂ，
百
其中ｄｆ为由撕不为０（ａｉ＋）而确定的支持向量（预先训练阶段）。
．１Ｓ－