第七章 支持向量机

支持向量机(SVM-- Support Vector Machine)是一种非常好的分类算法,是公认的在线性和非线性分类中效果较好的一种分类器。现在有非常多的关于SVM的资料,支持向量机的理论较为复杂,并不是非常容易理解,这里主要介绍支持向量机算法的思想,对于太复杂的公式理论,有些现成的结论就直接进行调用而不再这里进行详细的推导。如果需要进一步了解公式理论的话,可以参考相应的资料。

从SVM的思想入手

在收集的数据中,本身知道这些数据的分类,如下红黑点是已知的,利用这些已知的数据来估计未来的一些点,预估的数据并不知道具体的分类,需要通过已知的数据估计出这些点的分类。

svm 分类点

在logistic回归中,如果数据符合线性关系可以分为整正类和负类,在已知的红黑点的情况下去确定x,y的线性关系,形成一条直线或为超平面,能够最好的把红黑点分开,算法的思想是把这条直线映射到0,1之间,如果概率大于0.5则为正类,如果小于0.5则为负类。

映射函数为:$\frac{1}{1+e^{\theta x}}$,不管在何值最终规划在0,1下。

阶跃函数

在推导最后结论的时候,使用的是极大似然法,也就是最大限度的满足所有点的条件。这里就不展开来说logistic回归了。

回想logistic回归中在极大似然法的时候,使用是所有观察点的乘积,目标函数考虑的是所有的点,但这有没有必要呢?是否可以考虑某些特殊的点,而其他的点只要满足某些条件就可以了。

svm分点

一个群组中,有一些点在和另一个群组的区分起到关键的作用。越是互相靠近的不同类的点,分离更开就好。如在红黑两组的数据中,带绿色圈子的点在区分群组里,起到了关键点的作用,支持了两个群组的分类,其他的一些点,只要满足一些条件就可以。如其他所有的红点,只要在两个带圈红点的下方就可行,其他的黑点只要在带圈黑点的上方就可以。

svm分点分线

这种方式先确定关键的点,其他的点满足某一个条件,只要把关键的点分开,其他的点自然而然就分开了。

跟logistic不一样的是并不需要所有的点都满足某一条件,只需要一些关键点满足特定的严格的条件,而其他点符合一些简单的条件就行。

SVM的算法推导过程,就是在寻找这些特殊点,也就是支持分类的这些点,找到了这些支持点,问题就解决了一大步。

利用间隔最大化分割数据

为了比较清楚的写清算法的过程,这里使用的示例为直线分割,用数学的过程来表示SVM的思想。

假设我们已经找到了支持向量的点,如图所示,在这些点上可以找到两条直线分别为: $\overrightarrow w \bullet \overrightarrow x + b = -1 $和$\overrightarrow w \bullet \overrightarrow x + b = +1 $,这两条直线可以当做为区分两组数据的边缘线,这两条直线是平行的,而其他的点符合$\overrightarrow w \bullet \overrightarrow x +b -1 > 0 $,保证其他的点在直线的两边。这里看似有三个条件,$\overrightarrow w \bullet \overrightarrow x + b = -1 $ $\overrightarrow w \bullet \overrightarrow x + b = +1 $,和,引入一条中间线为:$\overrightarrow w \bullet \overrightarrow x + b =0 $,使得特征点到直线$\overrightarrow w \bullet \overrightarrow x + b =0 $距离最大,这样表示更容易分开。这样在求解的过程中把三个条件降为了两个条件,条件一:特征点到直线$\overrightarrow w \bullet \overrightarrow x + b =0 $距离最大,条件二:所有的点满足$\overrightarrow w \bullet \overrightarrow x + b -1 > 0 $。

svm分点分线

用数学的形式来表达条件一,复习一下点到直线的距离:

svm分点分线

推导的过程,有多种方式,其中一种是通过l直线的斜率确定通过p和他垂直的直线,计算两直线的交点Q,求出P和Q之间的距离即可:

$$d=|\frac{Ax_0+By_0+c}{\sqrt{ A^2+B^2}}|$$

有了点到线的公示后,扩展到其他维数,点到超平面的距离为,$d=\frac{\overrightarrow w \overrightarrow x +b}{||w||}$,基础的公式有了以后,可以开始推导SVM了。

支持分类的点在超平面上$d=\overrightarrow w \overrightarrow x +b = -1$或者$d=\overrightarrow w \overrightarrow x +b = +1$上,距离可写成

$$d=\frac {||\overrightarrow w x_1 +b ||}{||w||} + \frac {||\overrightarrow w x_2 +b ||}{||w||}=\frac {1}{||w||}+\frac {||-1||}{||w||}=\frac {2}{w}$$

求解SVM的问题可以转换为:

$$max \frac{2}{||w||}$$

$$s.t yi(w xi+b) \ge 0 i=1,2,...,N$$

最大化$\frac{2}{||w||}$和最小化$\frac{1}{2}||w||^2$是等价的,问题再次变为:

$$min \frac{1}{2}||w||^2$$

$$s.t yi(w xi+b) \ge 0 i=1,2,...,N$$

SVM算法的过程

到这里SVM算法的过程如下:

1.从约束最优化问题求解:

$$min \frac {1}{2} ||w||^2$$

$$s.t yi(w xi+b) \ge 0 i=1,2,...,N$$

求得最优解 $w^\star,b^\star$

由此得到分离超平面:$w^\star \bullet x + b^\star = 0$

2.分类决策函数:

$$f(x)=sign(w^\star \bullet x + b^\star )$$

求解得到$w^\star,b^\star$,就可以进行分类了,这里只能把结果分为正例和负例,通过sign进行分组。

知道了SVM分类的步骤,但是怎么样求解$w^\star,b^\star$还不清楚,这个过程需要有非常的多数学知识作为支撑,有些推导并不容易,涉及到太多的推导过程,可以参考具体的文献。 推导过程会涉及到拉格朗日函数,KKT条件,对偶问题求解,最后用的是SMO算法。

SMO算法求解SVM

这里直接给出SMO算法的具体步骤: 最终需要求解的变量是:w和b 初始化 $\alpha_j,b$,其中 $\alpha_j$可以看做是各个已知点的权重,权重大的即为支持点。 1:计算误差,其中$x_i,y_i$为观察到的数据点,即为已知的数据。

$$E_i=f(x_i)-y<>i = \sum{(j=1)}^n\alpha _j y_j x_i x_j + b - y_i$$

2:求得上界H和下界L,其中C为常数

$$\begin{cases} L=max(0,\alpha _j ^{old} - \alpha _i ^{old}),H=min(C,C+\alpha _j ^{old} - \alpha _i ^{old}) if y_i \not= y_j \ L=max(0,\alpha _j ^{old} + \alpha _i ^{old} -C),H=min(C,C+\alpha _j ^{old} + \alpha _i ^{old}) if y_i = y_j \ \end{cases}$$

在这里就能比较明显的看出,SMO的算法主要是两个数两个数来算的,$\alpha _i ,\alpha _j $每次算一对数据,不停的迭代。

3:计算中间变量 $\eta$

$$\eta = x_i^Tx_i+x_j^Tx_j-2x_i^Tx_j$$

4:更新$\alpha _j$

$$\alpha _j ^{new}=\alpha _j ^{old}+ \frac {y_i(E_i-E_j)}{\eta}$$

5:对$\alpha _j$进行修剪

$$\alpha^{new,clipped}\begin{cases} H \ if \ \alpha _j ^{new} \ge H\ \alpha _j ^{new} \ if \ \alpha _j ^{new} \le H\ L \ if \ \alpha _j ^{new} \le L\ \end{cases}$$

6:更新$\alpha _j$

$$a_i^{new}=a_i^{new}+y_iy_j(\alpha _j^{old}-\alpha _j^{new,clipped})$$

7:更新中间变量b1和b2从而更新b:

$$b_1^{new}=b^{old}-E_i-y_i(\alpha _i^{new}-\alpha _i^{old})x_i^Tx_i-y_i(\alpha _j^{new}-\alpha _j^{old})x_j^Tx_i$$

$$b_2^{new}=b^{old}-E_i-y_i(\alpha _i^{new}-\alpha _i^{old})x_i^Tx_i-y_i(\alpha _j^{new}-\alpha _j^{old})x_j^Tx_i$$

则:

$$b=\begin{cases} b_1 \ 0<\alpha_i^{new}<C\ b_2 \ 0<\alpha_j^{new}<C\ \frac{b_1+b_2}{2} \ otherwise\ \end{cases}$$

8:通过不停的迭代得到$\alpha_i$和b,通过$\alpha_i$求得w:

$$w=\sum_{i=1}{N} \alpha_iy_ix_i $$

这样所有的参数就都能求得。求解的过程就很容易用python进行编写了,这是一段从《机器学习实践》中摘抄的代码,描述了这一个过程。 求解$\alpha_i$和b的过程如下:

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
    b = 0; m,n = shape(dataMatrix)
    alphas = mat(zeros((m,1)))
    iter = 0
    while (iter < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
                j = selectJrand(i,m)
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();
                if (labelMat[i] != labelMat[j]):
                    L = max(0, alphas[j] - alphas[i])
                    H = min(C, C + alphas[j] - alphas[i])
                else:
                    L = max(0, alphas[j] + alphas[i] - C)
                    H = min(C, alphas[j] + alphas[i])
                if L==H: print "L==H"; continue
                eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >= 0: print "eta>=0"; continue
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                alphas[j] = clipAlpha(alphas[j],H,L)
                if (abs(alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#update i by the same amount as j
                                                                        #the update is in the oppostie direction
                b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]): b = b1
                elif (0 < alphas[j]) and (C > alphas[j]): b = b2
                else: b = (b1 + b2)/2.0
                alphaPairsChanged += 1
                print "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
        if (alphaPairsChanged == 0): iter += 1
        else: iter = 0
        print "iteration number: %d" % iter
    return b,alphas

其中dataMatIn:输入, classLabels:输入的分类, C常数, toler学习率, maxIter最大迭代次数。 接着继续求解:

def calcWs(alphas,dataArr,classLabels):
    X = mat(dataArr); labelMat = mat(classLabels).transpose()
    m,n = shape(X)
    w = zeros((n,1))
    for i in range(m):
        w += multiply(alphas[i]*labelMat[i],X[i,:].T)
    return w

支持点和线性分类如下,w,b确定了线性方程,$\alpha_i$确定了支持点。

svm分点分线

在推导计算方法的时候,限制了两点,第一:线性可分,第二:只能分为两类,正例和负例。对于非线性和多分类SVM都能够做到。 这是sklearn在SVM的实例,可以直接采用现成的SVM算法。

svm分点分线

参考: 1.Fast Training of Support Vector Machines using Sequential Minimal Optimization 2.支持向量机SVM(一) 3.支持向量机

PS: 如本文对您有帮助,不妨通过一下方式支持一下博主噢 ^_^

官方
微信
官方微信
Q Q
咨询
意见
反馈
返回
顶部