2. 支持向量机（SVM）和它的运算速率问题
SVM图例
SVM Planes
对于SVM来说，数据点被视为p维向量，而我们试图用(p-1)维超平面分开这些点，即创造所谓的“线性分割器”。为此，我们要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面，则称为最大间隔超平面，而其定义的线性分类器被称为最大间隔分类器，或者叫做最佳稳定性感知器。SVM的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
(A Support Vector Machine (SVM) is a discriminative classifier formally defined by a separating hyperplane. In other words, given labeled training data (supervised learning), the algorithm outputs an optimal hyperplane which categorizes new examples.)
遇到线性不可分的情况时，需要使用Kernal投射到高维。其实Kernal函数和SVM可以理解为两个不同的东西，SVM只不过是用到了kernel trick把有些线性不可分的情况变得在高维线性可分（理想上），任何可以用内积计算距离的分类器或者其他的都可以用kernel trick。Kernal函数的好处是把低维空间投影到高维，有些核函数投影到有限维，比如多项式核，有些投影到无穷维，比如RBF。但这只是增大的线性可分的可能性，并不能保证。所以还要进入松弛系数（slash coefficients） 如果形象的理解，就是如果你有N个点，如果N个点分布在N维空间里，那他们肯定是线性可分的（比如2个点在平面上）。所以SVM用kenel的目的就在于此。
参考资料：
http://blog.csdn.net/v_july_v/article/details/7624837
http://docs.opencv.org/2.4/doc/tutorials/ml/introduction_to_svm/introduction_to_svm.html
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
一个邮件识别，在Python中运用SVM。运用了几个不同的kernal：linear, poly, rbf，sigmoid，修改了几次数据集大小。
1、1%集，clf = SVC(kernel="linear")：88%正确率，16秒
2、20%集，clf = SVC(kernel="linear")：95%正确率，64秒
3、全集，clf = SVC(kernel="linear")：98%正确率，308秒
1、1%集，clf = SVC(kernel="rbf")：62%正确率，1.8秒
2、20%集，clf = SVC(kernel="linear")：49%正确率，13秒
3、20%集，clf = SVC(kernel="rbf", C = 1000): 94%正确率，11秒
4、20%集，clf = SVC(kernel="rbf", C = 10000): 95%正确率，8秒
5、全集，clf = SVC(kernel="rbf", C = 10000): 99%正确率
在计算效率方面，SVM是通过QP来求解的。基于libsvm的实现时间复杂度在O(d * n^2) ~ O(d * n^3)之间，变化取决于如何使用cache. 所以如果我们内存足够的话那么可以调大cache_size来加快计算速度。其中d表示feature大小，如果数据集合比较稀疏的话，那么可以认为d是non-zero的feature平均数量。libsvm处理数据集合大小最好不要超过10k. 相比之下，liblinear的效率则要好得多，可以很容易训练million级别的数据集合。
kernel函数支持1.linear 2. polynomial 3. rbf 4. sigmoid(tanh). 对于unbalanced的问题，sklearn实现允许指定 1.class_weight 2.sample_weight. 其中class_weight表示每个class对应的权重，这个在构造classifier时候就需要设置。如果不确定的话就设置成为'auto'。sample_weight则表示每个实例对应的权重，这个可以在调用训练方法fit的时候传入。另外一个比较重要的参数是C(惩罚代价),通常来说设置成为1.0就够了。但是如果数据中太多噪音的话那么最好减小一些。
参数方面，可使用GridCV，一种几乎能自动查找最优参数调整的优秀 sklearn 工具。
===========================
