论文部分内容阅读
摘要：机器学习和数据挖掘可以有效的应用于各种各样的数据模式识别中，其中包括对电子邮件进行的模式识别、分类和知识发现。现在使用的垃圾邮件检测系统可以精确的进行邮件判别。但是，现实是总有一些误判，而这些误判有时会带来很大的损失。现提出的混合模式分类器分析了两个单个分类器的混合，降低了误判率，提高了检测的准确率。
关键词：电子邮件挖掘；垃圾邮件；复合分类器；模式混合
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)03-10674-01
1 引言
电子邮件无疑是因特网最重要的应用之一，它就像电话一样进入现代人的生活，并且，提供分析新的任务的机会，用户或组织可以用电子邮件来方便在商业领域不同应用中交流。本文集中于讨论混合两种算法的垃圾邮件检测的问题。
目前有许多研究集中于定义什么是垃圾邮件，并且用一般的方法来检测出它们。事实情况是尽管99%的用户同意相当多的邮件是垃圾，但是仍然有1%的用户希望收到这些邮件，也就是说一个正确的判断对另一个用户来说可能是错误的，反之亦然。
本文定义垃圾邮件为用户不想要的，或用户不需要的邮件。我们主要研究和检测哪些邮件是用户确实想要的，哪些不是，这比用一部分用户的定义来代替所有用户要好。
2 有监督的机器学习算法
这里提出将朴素贝叶斯分类算法应用到内容无关性中，N-gram余弦模型应用到电子邮件正文上。两个算法都是机器学习算法。应用于有监督的训练并输出一个类标和一个置信度值。一个用户可以从众多数据集和电子邮件文档中选择得到一个二元的类标。下面是有监督的机器学习算法。
2.1 内容无关的朴素贝叶斯分类器
传统的机器学习电子邮件分类建模都是基于内容的，其典型的特征是，信息是从电子邮件正文或者头数据中提取的。然后由一些机器学习算法处理。在近些年的研究中已经提出并集中于如何用内容无关方法区分垃圾电子邮件和普通的正常的邮件。这些特例的统计数据是基于信封信息而不是基于电子邮件的正文的内容。研究的最多的一种机器学习算法是贝叶斯算法。贝叶斯算法是基于早期的模式识别，给定不确定的实例，分类器能对其进行分类，贝叶斯理论是基于概率论的知识。通过一系列训练邮件从中提取特征，一个朴素贝叶斯分类器计算一个电子邮件是属于一个或另一个类。这一分类器被称作朴素的是因为它使用一个朴素的假设就是统计特征是独立的。尽管这过于简单化但这大大减少了神经网络判定树中可能的条件，并已经得到应用[3]。由这一分类器提取的一系列的数字都是静态的，包括发送者和接收者的电子邮件名，域名，另外邮件的大小和接受者的个数，附件数。对于连续的值用高斯统计算法来估计可能的值。
2.2 N-gram分类器
N-gram 以马尔可夫模型为理论基础[1]，对一词串W，w = 1,w2,...,wn，可以认为词i w (1≤i≤n)的出现与上文的前n 个词相关，则词串W出现的概率可通过如下的方法得出：
一般来说，n 取2或3。在语言模型的构造中，可以字、词、词性或词义等作为n-gram 的统计单元。由于n-gram 模型只观察2 到3 个历史信息，所以它反映的是语言的局部规律，但如果训练语料足够大，模型构造合理，这个局部规律将比较可靠。利用这一特点，我们应用n-gram 对文本进行局部分析。
在分析邮件文本时，一个N-gram代表一系列出现在文档中的N邻近特征或象征。我们使用一个特征窗口，检查一个完整的电子邮件的正文体，一个特征一次，并统计每个不同的N-gram出现的次数，例如，对一个5-gram，“hello word ”可以被分解为hello–ello llo w lowo 等。对电子邮件检测建模其算法工作如下：先统计每个电子邮件的每个N-gram出现的次数，这可能被作为文档导航器对给定的一系列训练电子邮件使用文档导航器数字平均值作为这一系列的中心，对于一个未知的测试电子邮件，计算距离这个中心的余弦距离，如果是1，那么两个文档是相似的，距离越小两个文档就越不同，余弦距离定义为：
其中j是训练测试电子邮件中可能出现的N-gram的总数，x是一个测试电子邮件的文档向量，y是一组训练的中心，xj代表jthN-granm出现的频率，yk是kthN-gram的出现频率。
3 混合分类器
模式混合的目标是通过给定任务平衡多种专家学习，从而提高每个单个模式的执行效果。同时也必须考虑到多种类型分类器的输入可能不同，为避免任何一个分类器失效。许多研究表明在一个组织中，混合模式分类器比单个的分类器都有好的结果。接下来介绍一种混合算法在垃圾邮件检测领域中的应用。
本文为检测垃圾邮件，定义一个两类问题，正常邮件和垃圾邮件。每个分类器的输出是一个类标和一个置信度，这些输出通过简单的一定的算法被强制限制在0-201内以简化计算和输出。101-201的被认为是垃圾邮件，因此，0被认为是最高可能的正常值，而201被认为是最高可能不正常值。因此，对于两值分类器输出单个数简化计算相关函数。我们认为这一输出为原始值，这与一组相关函数相结合。
训练方法需要一些扩充，一组邮件事先指出是否是垃圾邮件，这也可以用来收集用户的行为信息。一旦组成部分的单个分类器被应用到这些已明确类别的电子邮件上，一系列的模式输出就与相关函数相结合，一些这样的相关函数需要一个训练阶段和一个训练集。
3.1 朴素贝叶斯混合
朴素贝叶斯算法中试图评估一个分类器可能的正确的值，这可以从分类器的训练实例中得到，本文算法可以度量分类器的错误率和可能的正确性，这可以通过描述分类器的训练的值来估算，应用一些小的数据分组，聚类获得统计的例子，并减少计算量[2]。数据分组的个数N是一个参数，对每一个可以统计真实垃圾邮件的个数和正常邮件的个数。同时保存整个账户的类标然后估计值：
对特别的分组来Ci是我们混合的Ith分类器。P(Ci|S,BINj)是用同一种方法计算的，最终的返回值通过计算规格化可能的值使其在0-201之间。P(S)中，S是垃圾邮件。规格化的计算如下公式：
4 實验
一个电子邮件数据集被用于模式混合方法学习和训练该方法，由用户指出哪个是垃圾邮件，并将他们移动到一个特定的文件夹中，这些是每个用户都不想要的，现在的一般邮箱用户的垃圾邮件率大约为60%。我们用80/20规则测试该模式，也就是说用80%已排序的电子邮件来训练每个组成的单个分类器和相关函数。同时用另外的20%来测试结果，这里建立一个模拟的实用的自动分类系统，随着时间的增加，新收到的电子邮件作为训练数据用来提升分类器。这些新的数据接下来又会被新一轮的数据替代。
表1分类器的表现比较
尽管相关函数需要训练数据，很多情况下还是愿意训练单个混合算法，虽然可以首先给每个分类器所有的训练实例并提取值，但我们还是感觉到这与现实情况有所不同，这里，将训练数据分为1000个分组，每个分类器在一个分组上执行并产生初始值，这些值接下来输入混合算法中，来训练相关函数，为了提高效率将一个组的大小定为1000，当然，任何大小都是可以产生比较的结果的。单个的分类器会转换单个值依赖于已知的数据的多少。对有些分类器来说，训练5000和1000的值有可能会不同。然而，这里模拟一个更现实的训练方法以反映这一系统可以如何精确的实际应用，并相信这种分组逼近是可行的。
这些数据是原始的并且是没有经过修改的，电子邮件内容没有被预先处理过并且电子邮件头被忽略。对N-gram分类器来说，可以截去电子邮件的一部分。由于考虑到计算量和特征字检测中的噪音干扰，只使用邮件附件的前800个字节以提高效率，若使用整个邮件体会增加10%的检测量。
5 结束语
前文研究了一种特别的模式混合算法并介绍了它们的表现。但也要看到有几封电子邮件总是被混合分类器误判，这些特别的邮件的共同点是一般只包含图片附件，新闻组中假的新闻讨论和一些没有邮件体的空邮件，相信如果在数据集中考虑到提取的邮件头信息，那么会有更低的误判率。
使用混合算法的主要原因来自于计算机安全领域：防止攻击。集中于一种分类器只能让垃圾邮件发送者不断的测试，并最终找到途径躲避检测。而使用了混合算法，一个小的电子邮件的领地被保护起来，这与单个分类器不同。单个分类器已经不能很好的防止恶意攻击，而混合算法能很好地应付这种攻击。
在以后的工作中，将混合更多算法，并且使系统能自动选择最好的单个分类器的混合以获得最好的结果。
参考文献：
[1]毛伟, 徐蔚然, 郭军基. 于n-gram语言模型和链状朴素贝叶斯分类器的中文文本分类系统.中文信息学报,2005(9).
[2]Shlomo Hershkop, Salvatore J. Stolfo. Combining Email Models for False Positive Reduction. KDD 2005(8).
[3]顾昊, 钱晓俊. 一种贝叶斯方法邮件过滤的实现[M].http://www.cnblogs.com/howard/archive,2004.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：电子邮件挖掘；垃圾邮件；复合分类器；模式混合
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)03-10674-01
1 引言
电子邮件无疑是因特网最重要的应用之一，它就像电话一样进入现代人的生活，并且，提供分析新的任务的机会，用户或组织可以用电子邮件来方便在商业领域不同应用中交流。本文集中于讨论混合两种算法的垃圾邮件检测的问题。
目前有许多研究集中于定义什么是垃圾邮件，并且用一般的方法来检测出它们。事实情况是尽管99%的用户同意相当多的邮件是垃圾，但是仍然有1%的用户希望收到这些邮件，也就是说一个正确的判断对另一个用户来说可能是错误的，反之亦然。
本文定义垃圾邮件为用户不想要的，或用户不需要的邮件。我们主要研究和检测哪些邮件是用户确实想要的，哪些不是，这比用一部分用户的定义来代替所有用户要好。
2 有监督的机器学习算法
这里提出将朴素贝叶斯分类算法应用到内容无关性中，N-gram余弦模型应用到电子邮件正文上。两个算法都是机器学习算法。应用于有监督的训练并输出一个类标和一个置信度值。一个用户可以从众多数据集和电子邮件文档中选择得到一个二元的类标。下面是有监督的机器学习算法。
2.1 内容无关的朴素贝叶斯分类器
传统的机器学习电子邮件分类建模都是基于内容的，其典型的特征是，信息是从电子邮件正文或者头数据中提取的。然后由一些机器学习算法处理。在近些年的研究中已经提出并集中于如何用内容无关方法区分垃圾电子邮件和普通的正常的邮件。这些特例的统计数据是基于信封信息而不是基于电子邮件的正文的内容。研究的最多的一种机器学习算法是贝叶斯算法。贝叶斯算法是基于早期的模式识别，给定不确定的实例，分类器能对其进行分类，贝叶斯理论是基于概率论的知识。通过一系列训练邮件从中提取特征，一个朴素贝叶斯分类器计算一个电子邮件是属于一个或另一个类。这一分类器被称作朴素的是因为它使用一个朴素的假设就是统计特征是独立的。尽管这过于简单化但这大大减少了神经网络判定树中可能的条件，并已经得到应用[3]。由这一分类器提取的一系列的数字都是静态的，包括发送者和接收者的电子邮件名，域名，另外邮件的大小和接受者的个数，附件数。对于连续的值用高斯统计算法来估计可能的值。
2.2 N-gram分类器
N-gram 以马尔可夫模型为理论基础[1]，对一词串W，w = 1,w2,...,wn，可以认为词i w (1≤i≤n)的出现与上文的前n 个词相关，则词串W出现的概率可通过如下的方法得出：
一般来说，n 取2或3。在语言模型的构造中，可以字、词、词性或词义等作为n-gram 的统计单元。由于n-gram 模型只观察2 到3 个历史信息，所以它反映的是语言的局部规律，但如果训练语料足够大，模型构造合理，这个局部规律将比较可靠。利用这一特点，我们应用n-gram 对文本进行局部分析。
在分析邮件文本时，一个N-gram代表一系列出现在文档中的N邻近特征或象征。我们使用一个特征窗口，检查一个完整的电子邮件的正文体，一个特征一次，并统计每个不同的N-gram出现的次数，例如，对一个5-gram，“hello word ”可以被分解为hello–ello llo w lowo 等。对电子邮件检测建模其算法工作如下：先统计每个电子邮件的每个N-gram出现的次数，这可能被作为文档导航器对给定的一系列训练电子邮件使用文档导航器数字平均值作为这一系列的中心，对于一个未知的测试电子邮件，计算距离这个中心的余弦距离，如果是1，那么两个文档是相似的，距离越小两个文档就越不同，余弦距离定义为：
其中j是训练测试电子邮件中可能出现的N-gram的总数，x是一个测试电子邮件的文档向量，y是一组训练的中心，xj代表jthN-granm出现的频率，yk是kthN-gram的出现频率。
3 混合分类器
模式混合的目标是通过给定任务平衡多种专家学习，从而提高每个单个模式的执行效果。同时也必须考虑到多种类型分类器的输入可能不同，为避免任何一个分类器失效。许多研究表明在一个组织中，混合模式分类器比单个的分类器都有好的结果。接下来介绍一种混合算法在垃圾邮件检测领域中的应用。
本文为检测垃圾邮件，定义一个两类问题，正常邮件和垃圾邮件。每个分类器的输出是一个类标和一个置信度，这些输出通过简单的一定的算法被强制限制在0-201内以简化计算和输出。101-201的被认为是垃圾邮件，因此，0被认为是最高可能的正常值，而201被认为是最高可能不正常值。因此，对于两值分类器输出单个数简化计算相关函数。我们认为这一输出为原始值，这与一组相关函数相结合。
训练方法需要一些扩充，一组邮件事先指出是否是垃圾邮件，这也可以用来收集用户的行为信息。一旦组成部分的单个分类器被应用到这些已明确类别的电子邮件上，一系列的模式输出就与相关函数相结合，一些这样的相关函数需要一个训练阶段和一个训练集。
3.1 朴素贝叶斯混合
朴素贝叶斯算法中试图评估一个分类器可能的正确的值，这可以从分类器的训练实例中得到，本文算法可以度量分类器的错误率和可能的正确性，这可以通过描述分类器的训练的值来估算，应用一些小的数据分组，聚类获得统计的例子，并减少计算量[2]。数据分组的个数N是一个参数，对每一个可以统计真实垃圾邮件的个数和正常邮件的个数。同时保存整个账户的类标然后估计值：
对特别的分组来Ci是我们混合的Ith分类器。P(Ci|S,BINj)是用同一种方法计算的，最终的返回值通过计算规格化可能的值使其在0-201之间。P(S)中，S是垃圾邮件。规格化的计算如下公式：
4 實验
一个电子邮件数据集被用于模式混合方法学习和训练该方法，由用户指出哪个是垃圾邮件，并将他们移动到一个特定的文件夹中，这些是每个用户都不想要的，现在的一般邮箱用户的垃圾邮件率大约为60%。我们用80/20规则测试该模式，也就是说用80%已排序的电子邮件来训练每个组成的单个分类器和相关函数。同时用另外的20%来测试结果，这里建立一个模拟的实用的自动分类系统，随着时间的增加，新收到的电子邮件作为训练数据用来提升分类器。这些新的数据接下来又会被新一轮的数据替代。
表1分类器的表现比较
尽管相关函数需要训练数据，很多情况下还是愿意训练单个混合算法，虽然可以首先给每个分类器所有的训练实例并提取值，但我们还是感觉到这与现实情况有所不同，这里，将训练数据分为1000个分组，每个分类器在一个分组上执行并产生初始值，这些值接下来输入混合算法中，来训练相关函数，为了提高效率将一个组的大小定为1000，当然，任何大小都是可以产生比较的结果的。单个的分类器会转换单个值依赖于已知的数据的多少。对有些分类器来说，训练5000和1000的值有可能会不同。然而，这里模拟一个更现实的训练方法以反映这一系统可以如何精确的实际应用，并相信这种分组逼近是可行的。
这些数据是原始的并且是没有经过修改的，电子邮件内容没有被预先处理过并且电子邮件头被忽略。对N-gram分类器来说，可以截去电子邮件的一部分。由于考虑到计算量和特征字检测中的噪音干扰，只使用邮件附件的前800个字节以提高效率，若使用整个邮件体会增加10%的检测量。
5 结束语
前文研究了一种特别的模式混合算法并介绍了它们的表现。但也要看到有几封电子邮件总是被混合分类器误判，这些特别的邮件的共同点是一般只包含图片附件，新闻组中假的新闻讨论和一些没有邮件体的空邮件，相信如果在数据集中考虑到提取的邮件头信息，那么会有更低的误判率。
使用混合算法的主要原因来自于计算机安全领域：防止攻击。集中于一种分类器只能让垃圾邮件发送者不断的测试，并最终找到途径躲避检测。而使用了混合算法，一个小的电子邮件的领地被保护起来，这与单个分类器不同。单个分类器已经不能很好的防止恶意攻击，而混合算法能很好地应付这种攻击。
在以后的工作中，将混合更多算法，并且使系统能自动选择最好的单个分类器的混合以获得最好的结果。
参考文献：
[1]毛伟, 徐蔚然, 郭军基. 于n-gram语言模型和链状朴素贝叶斯分类器的中文文本分类系统.中文信息学报,2005(9).
[2]Shlomo Hershkop, Salvatore J. Stolfo. Combining Email Models for False Positive Reduction. KDD 2005(8).
[3]顾昊, 钱晓俊. 一种贝叶斯方法邮件过滤的实现[M].http://www.cnblogs.com/howard/archive,2004.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。