智能垃圾邮件过滤算法实现讨论[二]（对不起各位，这个话题可能要暂停一下）

key

好不容易终于把Bayesian算法写完了。写得太长，如果再往下续就影响阅读和讨论了，所以就开了新题目。

从这个题目开始，我打算说一下svm在反垃圾邮件技术中的应用。事实上svm在文本分类器的应用是很多的。
现在吹水说自己提供了Naive Bayesian算法的反垃圾邮件过滤器有很多，但暂时还没有听到哪个商用的
产品吹水说自己提供了svm。当然，技术不是越新越好，我只是把这个当成一种尝试，而结论就是，暂时
还没有听说到商用的svm垃圾邮件过滤器技术的尝试。

另一方面，我也找不到针对垃圾邮件过滤的svm开源项目。所以，这篇文章可能更多的是通用的svm应用讨论，
我只是结合自己的经验说一下“可能”的应用。但事实上，我还不知道自己会写出什么来。我只希望能把原理说
清楚了，把程序说明白了。而基本上说，我对后者的信心更大。

---- Key 2009/05

我这段时间有个重要的事情要做，这个话题需要暂停一下。我可能会写一些其他文章，但这个话题需要暂时停下来。

[ 本帖最后由 key 于 23-5-2009 00:48 编辑 ]

ubuntuhk

SVM应该是NLP方面最近几年最热门的统计学方法了，我没有仔细研究过，觉得最大的缺点就是训练时间比较长，而且对多类的分类问题需要拆解成多个二类问题来解决。

这里有个粗略介绍的文章：
http://qkzz.net/magazine/1009-3044/2007/09/837063.htm

摘要：介绍分析了SVM基础理论和目前多类SVM分类算法及其优缺点，提出了一种边界向量抽取算法，并基于该算法改进了1ar和1a1两种多类SVM算法。实验结果表明该边界向量抽取算法可以有效的减少训练样本的数量，在保持分类器推广能力的条件下缩短SVM的训练时间，特别是在大样本训练数据时 1arΔ可以提供最好的训练性能。
　　关键词：向量机；多类支持向量机；支持向量；边界向量；分类
　　中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)06-11590-04
　　
　　1 引言
　　支持向量机（SVM）最初是作为二类问题分类提出来的，然而在实际应用中，人们所面对的问题更多的则是多类分类问题，为此很多研究者提出了多类SVM分类算法，该算法也是当今SVM算法的研究重点之一。多类SVM算法的实现思想主要有两种：
　　(1)通过某种方式把多类分类问题分解为多个二类分类问题，该方法需要对训练样本进行重新分配，使得样本符合新的多个二类问题分类的需要，同时根据算法的实现采取不同策略决定测试样本所属类别。比较常用且性能较好的此类算法有one-against-rest、one-against- one、DAG、二叉树算法等，在这些算法的基础上又提出了一些改进的算法，如ACDMSVM[1]、MACM[2]、基于聚类的二叉树[3]、基于超球体或超方体的二叉树[4]等。这些改进的算法有的提高了多类SVM分类器的分类精度和推广能力，有的有效地加快了分类器训练和预测的速度。
　　(2)把多个分类面的求解合并到一个最优化问题中，该方法是二类问题的推广，一次性的求解一个大的二次规划问题，直接将多类问题同时分开 [6]。该方法虽然比第一种思想简单，但其算法复杂度大大增加，需要更多的变量，训练时间较长，推广能力也不比第一种方法更优，不适合应用于大规模的数据样本。
　　可以看出，上述多类SVM算法思想都要考虑两个非常重要的问题：
　　(1)尽可能提高多类SVM分类算法的推广能力和分类精度。由于多类SVM分类算法是由二类SVM算法推广而来，其本身就存在如何提高推广能力的问题，推广到多类以后，不同的多类SVM算法实现，分类精度就有不同的扩散影响。
　　(2)尽可能减少多类SVM分类器算法的执行时间，包括训练和预测时间。根据多类SVM分类器的使用场合可能采取不同的策略：有时要有高效的训练速度，另一种情况是对分类器预测的响应速度非常敏感，需要大大减少分类器对测试样本的分类响应时间。
　　对于多类SVM算法，在相同训练样本和测试样本情况下，分类器消耗的训练时间和预测时间与其实现方法有很大关系，不同实现方法需要的时间可能相差很大。前面两个问题需要整体考虑，精度和速度的提高本来就是互相矛盾的，当然同时得到提高是最好的。本文在介绍分析SVM基础理论和各类多类SVM分类算法优缺点的基础上，提出一种边界向量抽取算法，将其应用到一对一和一对多多类SVM分类算法，实验证明该方法可以提高训练速度而不失较高的推广能力，在大样本情况下训练速度提高更明显。
　　
　　2 支持向量机（SVM）简介[9]
　　统计学习理论是支持向量机的理论基础，该理论由Vapnik等人提出，是一种专门研究小样本情况下机器学习规律的理论。支持向量机的实现是保持经验风险值固定，最小化置信范围，取得实际期望风险的最小化，而神经网络是保持置信范围固定，最小化经验风险。神经网络的解可能是局部极小值，但SVM 可得全局最优解。随着该理论的不断发展和成熟，同时也因神经网络等学习方法在理论上缺乏实质性进展，SVM开始受到越来越广泛的重视。
　　支持向量机的具体实现思想是通过某种非线性映射把输入向量x映射到高维特征空间Z，在这个新空间中构建最优分类超平面。映射的原因是无法把训练样本在原来的空间中线性可分，但这也带来一个技术问题，这种映射会大大增加向量的特征空间的维数，既“维数灾难”。
　　根据最优分类超平面的构造原理可知公式(1)，l为样本向量的个数，
　　公式(1)使支持向量机的训练问题变为一个简单的二次规化问题，即在满足约束条件ai≥0,1...,l 和情况下求解a0最大化W(a)，结果可得大部分ai0为0，不为0的样本向量称为支持向量，假设a0=(a10,...,al0)，且ai0≠0, (i=1,...,l)，可得最优超平面的向量，基于最优超平面的分类规则的指示函数是，
　　上面公式讨论中(xi·x)表示向量的内积，如果训练样本线性可分计算内积没有任何困难，但如果线性不可分就需要映射到高维处理，设Z=Φ(x)，定义x→Φ(x)为x到空间的映射，则公式(1)和(2)变为，
　　原来x空间的内积变为了Z空间的内积，为了避免计算非线性函数和变换空间中的内积，可以把映射空间中的内积转换为原空间的某个函数的计算，根据在Hilbert空间中的内积表达式，
　　称之为内积的回旋，在SVM应用中称为核函数，公式(3)和(4)变为
　　这就把线性情况推广到了非线性的情况，常用的核函数有多项式、RBF（径向基）、Sigmoid，这些核函数已被证明适合绝大部分非线性分类问题，当然也可定义自己的核函数。由此我们看到前面的“维数灾难”不是SVM的主要问题，而是训练样本数量很大时，训练的速度可能会很慢。
　　前面的讨论是假设线性和非线性都可分的情况，既训练样本可以被最优超平面完全无误的分开，但实际存在不可分的情况，为了推广到不可分情况引入惩罚参数C，构造软间隔最优超平面来分开样本，允许存在错分且错分程度应该尽可能的小，具体讨论可参考[9]。
　　
　　3 常用的多类SVM算法
　　引言中介绍了把SVM推广到多类情况一般有两种实现思想，本文主要介绍第一种，其中心思想是把多类问题分解为多个二类问题，通过合理的分解训练样本训练生成多个SVM模型，根据算法用其中的一些或全部SVM模型对测试样本进行预测，再根据算法对多个结果评估得到测试样本所属的类别。

ubuntuhk

当然如果只是训练模型的时间长，但是测试的时间短，也问题不大，但是多类拆分成二类问题的办法，貌似测试时间也短不了，搬凳子继续听key兄分析。

key

原帖由 ubuntuhk 于 22-5-2009 23:13 发表

                               
登录/注册后可看大图

当然如果只是训练模型的时间长，但是测试的时间短，也问题不大，但是多类拆分成二类问题的办法，貌似测试时间也短不了，搬凳子继续听key兄分析。

我不是这方面的专家，不要期望我写出点什么东西来。
主要是想起个题目，说一些自己的理解，然后大家讨论讨论。

coredump

看来UB也是这方面的行家啊

ubuntuhk

不敢冒充砖家，就是混了个学位。

我的硕士论文是做基于Maximum Entropy建模方式来进行自然语言处理，那时候MaxEnt比较流行，现在换SVM统领江山了