数据挖掘算法—SVM算法

✅作者简介：热爱科研的算法开发者，Python、Matlab项目可交流、沟通、学习。

????个人主页：算法工程师的学习日志

简介

SVM(Support Vector Machine)名为支持向量机，是常见的一种判别方法。在机器学习领域，是一个有监督的学习模型，通常用来进行模式识别、分类以及回归分析。

相关概念

分类器：分类器就是给定一个样本的数据，判定这个样本属于哪个类别。例如在天气预测中，我们认为晚上能看到星星数量和亮度对于第二天的天气情况是有影响的，那么分类器就是通过能看到星星数量和亮度预测第二天的天气情况。

特征：在分类问题中，输入分类器的数据叫做特征。天气预测问题特征就是前一天晚上能看到星星数量和亮度。

线性分类器：线性分类器是分类器中的一种，就是判定分类结果的根据是通过特征的线性组合得到的。以上面的天气预测问题为例，判断的依据只能是前一天晚上能看到星星数量和亮度的线性组合，不能将星星数量和亮度值进行开方、立方等运算。

线性分类器起源

在实际中我们往往遇到这样的问题：给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。

用二维空间举个例子，我们用一条直线把空间切割开来，直线左边的点属于类别-1，直线右边的点属于类别1。

如果用数学语言呢，就是这样的：空间是由X1和X2组成的二维空间，直线的方程是X1+X2 = 1，用向量表示即为[1,1]^{T}[X1,X2]-1=0 。点x在直线左边时，把x放入方程左边，计算结果小于0。同理，在右边就是把x放入方程左边，计算出的结果大于0。

在三维空间中呢，需要用一个平面把空间切成两半，对应的方程是X1+X2+X3=1，也就是[1,1,1]^{T}[X1,X2,X3]-1=0 。 

在高维（n>3）空间呢？就需要用到n-1维的超平面将空间切割开，数学描述：

如果用x表示数据点，用y表示类别，一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane），把空间切割开，W^{T}中的T代表转置： 

W^{T}X+b=0

分类器类型

常见的线性分类器有感知器模型和逻辑回归。上一节举出的例子是感知器模型，直接分好类。有时候，我们除了要知道分类器对于新数据的分类结果，还希望知道分类器对于这次分类的概率-->逻辑回归。

逻辑回归将线性分类器的超平面方程计算结果通过logistic函数从正负无穷映射到0到1。这样，映射的结果就可以认为是分类器将x判定为类别1的概率，从而指导后面的学习过程。

举个例子，用感知器的天气预报只会告诉你明天要下雨（y=1），或者明天不下雨（y=-1）；而用了逻辑回归的天气预报就能告诉你明天有80%的概率要下雨，20%的概率不下雨。

逻辑回归的公式g(z)=\frac{1}{1+e^{-z}} ： 

 

在感知器模型中，将特征代入判别方程中，如果得到的值是-3，我们可以判定类别是-1（因为-3<0）。而逻辑回归中呢，将-3代入g(z)，我们就知道，该数据属于类别1的概率是0.05（近似数值），那么属于类别-1的概率就是1 – 0.05 = 0.95。

SVM

SVM最基本的应用是分类。求解最优的分类面，然后用于分类。

最优分类面的定义： 

对于SVM，存在一个分类面，两个点集到此平面的最小距离最大，两个点集中的边缘点到此平面的距离最大。

从直观上来看，下图左边的，肯定不是最优分类面；而右边的能让人感觉到其距离更大，使用的支撑点更多，至少使用了三个分类面，应该是最优分类面。

 

那么，是不是一个最优分类面需要两个或三个以上的点才能确定那？

这个要依据实际情况而定。

如下图，左图是由三个点，来确定的一个最优分类面，不同类别的两个点确定一个中心点，而同类的两个点可以确定方向向量。这个最优分类面，需要三个点。

但对于右图，直接获取不同类别的两个点的垂面，即是最优分类面。这个分类面，则需要两个点。

 

以上，情况的分析，使得求解最优分类面的思路，模式比较复杂。

若采用穷举法，至少需要以下过程。

先取不同类别的两个点，求解中心连线的垂面。如以上右图模式

然后判断其他点到此垂面的距离，若有更小的距离（或负值，即分类错误），则选取以上左图模式。

穷举所有点。采用最直接的方式处理，则其运算复杂度为 m*n*n， 若n > m.

这个还没有用到高维映射哪，如果再加上高维映射的处理，算法恐怕就更复杂了。所以，穷举法是不太现实的。

核函数

在原始特征的维度上，能直接找到一条分离超平面将数据完美的分成两类的情况。但如果找不到呢？

比如，原始的输入向量是一维的，0< x <1的类别是1，其他情况记做-1。这样的情况是不可能在1维空间中找到分离超平面的（一维空间中的分离超平面是一个点，aX+b=0）。

 

这就要说到SVM的黑科技—核函数。核函数可以将原始特征映射到另一个高维特征空间中。 

将原始的一维特征空间映射到二维特征空间X^{2}和x，那么就可以找到分离超平面X^{2}-X=0。当X^{2}-X<0的时候，就可以判别为类别1，当X^{2}-X>0 的时候，就可以判别为类别0。如下图： 

 

再将X^2-X=0映射回原始的特征空间，就可以知道在0和1之间的实例类别是1，剩下空间上（小于0和大于1）的实例类别都是0。 

 

利用特征映射，就可以将低维空间中的线性不可分问题解决了。核函数除了能够完成特征映射，而且还能把特征映射之后的内积结果直接返回，大幅度降低了简化了工作。

样例代码

# encoding=utf-8
import time
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn import datasets
from sklearn import svm


if __name__ == '__main__':
    print('prepare datasets...')
    # Iris数据集
    iris = datasets.load_iris()
    features = iris.data
    labels = iris.target


    # 选取33%数据作为测试集，剩余为训练集


    train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33,
                                                                                random_state=0)


    time_2 = time.time()
    print('Start training...')
    clf = svm.SVC()  # svm class   
    clf.fit(train_features, train_labels)  # training the svc model 
    time_3 = time.time()
    print('training cost %f seconds' % (time_3 - time_2))


    print('Start predicting...')
    test_predict = clf.predict(test_features)
    time_4 = time.time()
    print('predicting cost %f seconds' % (time_4 - time_3))


    score = accuracy_score(test_labels, test_predict)
print("The accruacy score is %f" % score)

prepare datasets...
Start training...
training cost 0.001999 seconds
Start predicting...
predicting cost 0.000000 seconds
The accruacy score is 0.980000