SVM--簡(jiǎn)介

支持向量機(jī)(Support Vector Machines)是一種二分類(lèi)模型，它的目的是尋找一個(gè)超平面來(lái)對(duì)樣本進(jìn)行分割，分割的原則是間隔最大化，最終轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題來(lái)求解。

在機(jī)器學(xué)習(xí)領(lǐng)域，是一個(gè)有監(jiān)督的學(xué)習(xí)模型，通常用來(lái)進(jìn)行模式識(shí)別、分類(lèi)以及回歸分析。

由簡(jiǎn)至繁的模型包括：當(dāng)訓(xùn)練樣本線(xiàn)性可分時(shí)，通過(guò)硬間隔最大化，學(xué)習(xí)一個(gè)線(xiàn)性可分支持向量機(jī)；

當(dāng)訓(xùn)練樣本近似線(xiàn)性可分時(shí)，通過(guò)軟間隔最大化，學(xué)習(xí)一個(gè)線(xiàn)性支持向量機(jī)；

當(dāng)訓(xùn)練樣本線(xiàn)性不可分時(shí)，通過(guò)核技巧和軟間隔最大化，學(xué)習(xí)一個(gè)非線(xiàn)性支持向量機(jī)；

SVM--思想

建立一個(gè)最優(yōu)決策超平面，使得該平面兩側(cè)距離平面最近的兩類(lèi)樣本之間的距離最大化，從而對(duì)分類(lèi)問(wèn)題提供良好的泛化能力。

說(shuō)白了就是：當(dāng)樣本點(diǎn)的分布無(wú)法用一條直線(xiàn)或幾條直線(xiàn)分開(kāi)時(shí)(即線(xiàn)性不可分)SVM提供一種算法，求出一個(gè)曲面用于劃分。這個(gè)曲面，就稱(chēng)為最優(yōu)決策超平面。

而且，SVM采用二次優(yōu)化，因此最優(yōu)解是唯一的，且為全局最優(yōu)。前面提到的距離最大化就是說(shuō)，這個(gè)曲面讓不同分類(lèi)的樣本點(diǎn)距離最遠(yuǎn)，即求最優(yōu)分類(lèi)超平面等價(jià)于求最大間隔。

SVM--原理

SVM大致原理：

①假設(shè)我們要通過(guò)三八線(xiàn)把星星和紅點(diǎn)分成兩類(lèi)。

②那么有無(wú)數(shù)多條線(xiàn)可以完成這個(gè)任務(wù)。

③在SVM中，我們尋找一條最優(yōu)的分界線(xiàn)使得它到兩邊的Margin都最大。

④在這種情況下邊緣的幾個(gè)數(shù)據(jù)點(diǎn)就叫做Support Vector，這也是這個(gè)分類(lèi)算法名字的來(lái)源。

線(xiàn)性可分支持向量機(jī)

1、定義給定線(xiàn)性可分訓(xùn)練數(shù)據(jù)集，通過(guò)間隔最大化或等價(jià)地求解相應(yīng)的凸二次規(guī)劃問(wèn)題學(xué)習(xí)得到的分離超平面為 wx+b=0 以及相應(yīng)的分類(lèi)決策函數(shù) f(x)=sign(wx+b) 稱(chēng)為線(xiàn)性可分支持向量機(jī)。

圖1

由于訓(xùn)練數(shù)據(jù)線(xiàn)性可分，如圖1所示，這時(shí)有許多超平面能將兩類(lèi)數(shù)據(jù)正確劃分，線(xiàn)性可分支持向量機(jī)的目的就是從中找到最佳的超平面，使得預(yù)測(cè)新數(shù)據(jù)時(shí)有較好的表現(xiàn)。以二維空間為例，相對(duì)于把超平面方程 wx+b=0 理解為一條平面直線(xiàn) y=kx+b，個(gè)人更傾向于將其理解為空間平面z=ax+by+c與平面z=0的交線(xiàn)。將訓(xùn)練數(shù)據(jù)集中的樣本點(diǎn)帶入wx+b 得到的值表示空間平面z=ax+by+c上的點(diǎn)與z=0之間的距離，距離為正的樣本為正例，距離為負(fù)的樣本為負(fù)例。注意，二維空間中的超平面是圖2中的紅色直線(xiàn)。

圖2 二維空間中的超平面

2、函數(shù)間隔和幾何間隔

圖3 二類(lèi)分類(lèi)問(wèn)題

在如上圖所示的二維空間中，假設(shè)已經(jīng)找到了超平面將二維空間劃分為兩類(lèi)，“○”表示正例，“×”表示負(fù)例。其中A，B，C三個(gè)點(diǎn)表示3個(gè)樣本點(diǎn)。一般來(lái)說(shuō)，一個(gè)點(diǎn)距離超平面的遠(yuǎn)近可以表示分類(lèi)預(yù)測(cè)的確信程度。比如，預(yù)測(cè)這三個(gè)點(diǎn)的類(lèi)別的時(shí)候，點(diǎn)A距離超平面較遠(yuǎn)，若預(yù)測(cè)該點(diǎn)為正例，就有比較大的把握。相反，點(diǎn)C距離超平面較近，若預(yù)測(cè)該點(diǎn)為正例就不那么確定，因?yàn)橛锌赡苁浅矫孢x擇的不合理而導(dǎo)致點(diǎn)C被誤分為正例。因此，相比距離超平面較遠(yuǎn)的點(diǎn)，距離較近的點(diǎn)對(duì)超平面的選擇有更大的影響，我們將其稱(chēng)之為支持向量。支持向量決定了我們?nèi)绾芜x擇超平面，可見(jiàn)支持向量的重要性。函數(shù)間隔和幾何間隔的提出，為找到最佳的超平面提供了依據(jù)。

2.1、函數(shù)間隔

對(duì)于給定的訓(xùn)練數(shù)據(jù)集T和超平面(ω，b)，定義超平面(ω，b)關(guān)于樣本點(diǎn)(x_i，y_i)的函數(shù)間隔為

定義超平面(ω，b)關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔為超平面(ω，b)關(guān)于T中所有樣本點(diǎn)(x_i，y_i)的函數(shù)間隔的最小值，即

函數(shù)間隔越小的點(diǎn)離超平面越近，因此通過(guò)最大化訓(xùn)練數(shù)據(jù)集的函數(shù)間隔，即找到一條直線(xiàn)離兩類(lèi)樣本點(diǎn)盡量的遠(yuǎn)，來(lái)找到最佳的超平面聽(tīng)起來(lái)似乎很合理。但是，用函數(shù)間隔來(lái)選擇超平面存在一個(gè)問(wèn)題：只要成比例地改變?chǔ)睾蚥，超平面并沒(méi)有改變但是函數(shù)間隔卻會(huì)改變。在二維空間中，成比例地改變?chǔ)睾蚥就是將空間平面z=ax+by+c以超平面為軸心進(jìn)行轉(zhuǎn)動(dòng)。因此，需要對(duì)ω進(jìn)行規(guī)范化，從而引出了幾何間隔的概念。

2.2、幾何間隔

對(duì)于給定的訓(xùn)練數(shù)據(jù)集T和超平面(ω，b)，定義超平面(ω，b)關(guān)于樣本點(diǎn)(x_i，y_i)的幾何間隔為

定義超平面(ω，b)關(guān)于訓(xùn)練數(shù)據(jù)集T的幾個(gè)間隔為超平面(ω，b)關(guān)于T中所有樣本點(diǎn)(x_i，y_i)的函數(shù)間隔的最小值，即

在二維空間中，幾何間隔就是將空間平面z=ax+by+c固定，不再以超平面為軸心進(jìn)行轉(zhuǎn)動(dòng)。此時(shí)，成比例地改變?chǔ)睾蚥不再對(duì)幾何間隔有影響。

3.間隔最大化

支持向量機(jī)學(xué)習(xí)的基本想法是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的超平面。對(duì)于線(xiàn)性可分的訓(xùn)練數(shù)據(jù)集而言，超平面有無(wú)窮多個(gè)，但是幾何間隔最大的超平面是唯一的。這里的間隔最大化稱(chēng)為硬間隔最大化。這是因?yàn)閹缀伍g隔是指離超平面最近的正負(fù)樣本點(diǎn)，最大化幾何間隔意味著當(dāng)前的超平面不僅可以很合理地劃分訓(xùn)練數(shù)據(jù)集，對(duì)未知的測(cè)試數(shù)據(jù)集應(yīng)當(dāng)也有較好的分類(lèi)預(yù)測(cè)能力。因此，接下來(lái)的問(wèn)題就是如何求得一個(gè)幾何間隔最大的超平面。這個(gè)問(wèn)題可以表示為約束最優(yōu)化問(wèn)題：

考慮幾何間隔和函數(shù)間隔的關(guān)系，可將這個(gè)問(wèn)題改寫(xiě)為：

正如前文所述，成比例地改變?chǔ)睾蚥會(huì)影響函數(shù)間隔，但不影響超平面，因此不妨通過(guò)調(diào)整ω和b使得函數(shù)間隔取值為1。同時(shí)，注意到最大化1/||ω||與最小化||ω||等價(jià)，因此，上式可以轉(zhuǎn)化為如下形式：

目標(biāo)函數(shù)的系數(shù)1/2僅僅是為了方便求導(dǎo)，無(wú)其他任何含義。通過(guò)利用拉格朗日對(duì)偶算法，求解上述約束最優(yōu)化問(wèn)題得到w和b，從而得到分類(lèi)決策函數(shù)f(x)=sign(ωx+b)。基于分類(lèi)決策函數(shù)可對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分類(lèi)。

線(xiàn)性支持向量機(jī)

1、簡(jiǎn)介

線(xiàn)性支持向量機(jī)是針對(duì)線(xiàn)性不可分的數(shù)據(jù)集的，這樣的數(shù)據(jù)集可以通過(guò)近似可分的方法實(shí)現(xiàn)分類(lèi)。對(duì)于這樣的數(shù)據(jù)集，類(lèi)似線(xiàn)性可分支持向量機(jī)，通過(guò)求解對(duì)應(yīng)的凸二次規(guī)劃問(wèn)題，也同樣求得分離超平面：

以及相應(yīng)的分類(lèi)決策函數(shù)

2、線(xiàn)性支持向量機(jī)的原理

線(xiàn)性支持向量機(jī)的原始問(wèn)題：

接下來(lái)的問(wèn)題就變成如何求解這樣一個(gè)最優(yōu)化問(wèn)題(稱(chēng)為原始問(wèn)題)。引入拉格朗日函數(shù)：

此時(shí)，原始問(wèn)題即變成

利用拉格朗日函數(shù)的對(duì)偶性，將問(wèn)題變成一個(gè)極大極小優(yōu)化問(wèn)題：

首先求解，將拉格朗日函數(shù)分別對(duì)求偏導(dǎo)，并令其為0：

即為：

將其帶入拉格朗日函數(shù)，即得：

第二步，求，即求：

由可得，因?yàn)樵诘诙角髽O大值的過(guò)程中，函數(shù)只與有關(guān)。

將上述的極大值為題轉(zhuǎn)化為極小值問(wèn)題：

這就是原始問(wèn)題的對(duì)偶問(wèn)題。

3、線(xiàn)性支持向量機(jī)的過(guò)程

(1)、設(shè)置懲罰參數(shù)，并求解對(duì)偶問(wèn)題：

假設(shè)求得的最優(yōu)解為；

(2)、計(jì)算原始問(wèn)題的最優(yōu)解：

選擇中滿(mǎn)足的分量，計(jì)算：

(3)、求分離超平面和分類(lèi)決策函數(shù)：分離超平面為：

分類(lèi)決策函數(shù)為：

非線(xiàn)性支持向量機(jī)

1、適合場(chǎng)景

如果訓(xùn)練輸入線(xiàn)性不可分，可以使用非線(xiàn)性支持向量機(jī)，利用核技巧將輸入空間非線(xiàn)性問(wèn)題轉(zhuǎn)化到特征空間線(xiàn)性可分問(wèn)題。

2、核函數(shù)的條件設(shè)

是定義在χ×χ上的對(duì)稱(chēng)函數(shù)，如果對(duì)任意

對(duì)應(yīng)的Gram矩陣是半正定矩陣，則稱(chēng)K(x,z)是正定核。

3、常用核函數(shù)(1)多項(xiàng)式核函數(shù)

(2)高斯核函數(shù)

4、構(gòu)建目標(biāo)函數(shù)SVM的對(duì)偶問(wèn)題

只是涉及到實(shí)例和實(shí)例之間的內(nèi)積xi?xj，可以直接使用核函數(shù)進(jìn)行替換，無(wú)需知道映射函數(shù)的具體形式。目標(biāo)函數(shù)可替換為

假設(shè)

是上面問(wèn)題的最優(yōu)解，那么:

選擇一個(gè)下標(biāo)j，使得0

構(gòu)造決策函數(shù)：

5、求最優(yōu)解

要求解的最優(yōu)化問(wèn)題如下：

考慮使用序列最小最優(yōu)化算法(SMO，sequential minimal optimization)

SVM--實(shí)現(xiàn)

SVM# -*- coding: utf-8 -*-

# Mathieu Blondel, September 2010

# License: BSD 3 clause

import numpy as np

from numpy import linalg

import cvxopt

import cvxopt.solvers

def linear_kernel(x1, x2):

return np.dot(x1, x2)

def polynomial_kernel(x, y, p=3):

return (1 + np.dot(x, y)) ** p

def gaussian_kernel(x, y, sigma=5.0):

return np.exp(-linalg.norm(x-y)**2 / (2 * (sigma ** 2)))

class SVM(object):

def __init__(self, kernel=linear_kernel, C=None):

self.kernel = kernel

self.C = C

if self.C is not None: self.C = float(self.C)

def fit(self, X, y):

n_samples, n_features = X.shape

# Gram matrix

K = np.zeros((n_samples, n_samples))

for i in range(n_samples):

for j in range(n_samples):

K[i,j] = self.kernel(X[i], X[j])

P = cvxopt.matrix(np.outer(y,y) * K)

q = cvxopt.matrix(np.ones(n_samples) * -1)

A = cvxopt.matrix(y, (1,n_samples))

b = cvxopt.matrix(0.0)

if self.C is None:

G = cvxopt.matrix(np.diag(np.ones(n_samples) * -1))

h = cvxopt.matrix(np.zeros(n_samples))

else:

tmp1 = np.diag(np.ones(n_samples) * -1)

tmp2 = np.identity(n_samples)

G = cvxopt.matrix(np.vstack((tmp1, tmp2)))

tmp1 = np.zeros(n_samples)

tmp2 = np.ones(n_samples) * self.C

h = cvxopt.matrix(np.hstack((tmp1, tmp2)))

# solve QP problem

solution = cvxopt.solvers.qp(P, q, G, h, A, b)

# Lagrange multipliers

'''

數(shù)組的flatten和ravel方法將數(shù)組變?yōu)橐粋€(gè)一維向量(鋪平數(shù)組)。

flatten方法總是返回一個(gè)拷貝后的副本，

而ravel方法只有當(dāng)有必要時(shí)才返回一個(gè)拷貝后的副本(所以該方法要快得多，尤其是在大數(shù)組上進(jìn)行操作時(shí))

'''

a = np.ravel(solution['x'])

# Support vectors have non zero lagrange multipliers

'''

這里a>1e-5就將其視為非零

'''

sv = a > 1e-5 # return a list with bool values

ind = np.arange(len(a))[sv] # sv's index

self.a = a[sv]

self.sv = X[sv] # sv's data

self.sv_y = y[sv] # sv's labels

print("%d support vectors out of %d points" % (len(self.a), n_samples))

# Intercept

'''

這里相當(dāng)于對(duì)所有的支持向量求得的b取平均值

'''

self.b = 0

for n in range(len(self.a)):

self.b += self.sv_y[n]

self.b -= np.sum(self.a * self.sv_y * K[ind[n],sv])

self.b /= len(self.a)

# Weight vector

if self.kernel == linear_kernel:

self.w = np.zeros(n_features)

for n in range(len(self.a)):

# linear_kernel相當(dāng)于在原空間，故計(jì)算w不用映射到feature space

self.w += self.a[n] * self.sv_y[n] * self.sv[n]

else:

self.w = None

def project(self, X):

# w有值，即kernel function 是 linear_kernel，直接計(jì)算即可

if self.w is not None:

return np.dot(X, self.w) + self.b

# w is None --> 不是linear_kernel,w要重新計(jì)算

# 這里沒(méi)有去計(jì)算新的w(非線(xiàn)性情況不用計(jì)算w),直接用kernel matrix計(jì)算預(yù)測(cè)結(jié)果

else:

y_predict = np.zeros(len(X))

for i in range(len(X)):

s = 0

for a, sv_y, sv in zip(self.a, self.sv_y, self.sv):

s += a * sv_y * self.kernel(X[i], sv)

y_predict[i] = s

return y_predict + self.b

def predict(self, X):

return np.sign(self.project(X))

if __name__ == "__main__":

import pylab as pl

def gen_lin_separable_data():

# generate training data in the 2-d case

mean1 = np.array([0, 2])

mean2 = np.array([2, 0])

cov = np.array([[0.8, 0.6], [0.6, 0.8]])

X1 = np.random.multivariate_normal(mean1, cov, 100)

y1 = np.ones(len(X1))

X2 = np.random.multivariate_normal(mean2, cov, 100)

y2 = np.ones(len(X2)) * -1

return X1, y1, X2, y2

def gen_non_lin_separable_data():

mean1 = [-1, 2]

mean2 = [1, -1]

mean3 = [4, -4]

mean4 = [-4, 4]

cov = [[1.0,0.8], [0.8, 1.0]]

X1 = np.random.multivariate_normal(mean1, cov, 50)

X1 = np.vstack((X1, np.random.multivariate_normal(mean3, cov, 50)))

y1 = np.ones(len(X1))

X2 = np.random.multivariate_normal(mean2, cov, 50)

X2 = np.vstack((X2, np.random.multivariate_normal(mean4, cov, 50)))

y2 = np.ones(len(X2)) * -1

return X1, y1, X2, y2

def gen_lin_separable_overlap_data():

# generate training data in the 2-d case

mean1 = np.array([0, 2])

mean2 = np.array([2, 0])

cov = np.array([[1.5, 1.0], [1.0, 1.5]])

X1 = np.random.multivariate_normal(mean1, cov, 100)

y1 = np.ones(len(X1))

X2 = np.random.multivariate_normal(mean2, cov, 100)

y2 = np.ones(len(X2)) * -1

return X1, y1, X2, y2

def split_train(X1, y1, X2, y2):

X1_train = X1[:90]

y1_train = y1[:90]

X2_train = X2[:90]

y2_train = y2[:90]

X_train = np.vstack((X1_train, X2_train))

y_train = np.hstack((y1_train, y2_train))

return X_train, y_train

def split_test(X1, y1, X2, y2):

X1_test = X1[90:]

y1_test = y1[90:]

X2_test = X2[90:]

y2_test = y2[90:]

X_test = np.vstack((X1_test, X2_test))

y_test = np.hstack((y1_test, y2_test))

return X_test, y_test

# 僅僅在Linears使用此函數(shù)作圖，即w存在時(shí)

def plot_margin(X1_train, X2_train, clf):

def f(x, w, b, c=0):

# given x, return y such that [x,y] in on the line

# w.x + b = c

return (-w[0] * x - b + c) / w[1]

pl.plot(X1_train[:,0], X1_train[:,1], "ro")

pl.plot(X2_train[:,0], X2_train[:,1], "bo")

pl.scatter(clf.sv[:,0], clf.sv[:,1], s=100, c="g")

# w.x + b = 0

a0 = -4; a1 = f(a0, clf.w, clf.b)

b0 = 4; b1 = f(b0, clf.w, clf.b)

pl.plot([a0,b0], [a1,b1], "k")

# w.x + b = 1

a0 = -4; a1 = f(a0, clf.w, clf.b, 1)

b0 = 4; b1 = f(b0, clf.w, clf.b, 1)

pl.plot([a0,b0], [a1,b1], "k--")

# w.x + b = -1

a0 = -4; a1 = f(a0, clf.w, clf.b, -1)

b0 = 4; b1 = f(b0, clf.w, clf.b, -1)

pl.plot([a0,b0], [a1,b1], "k--")

pl.axis("tight")

pl.show()

def plot_contour(X1_train, X2_train, clf):

# 作training sample數(shù)據(jù)點(diǎn)的圖

pl.plot(X1_train[:,0], X1_train[:,1], "ro")

pl.plot(X2_train[:,0], X2_train[:,1], "bo")

# 做support vectors 的圖

pl.scatter(clf.sv[:,0], clf.sv[:,1], s=100, c="g")

X1, X2 = np.meshgrid(np.linspace(-6,6,50), np.linspace(-6,6,50))

X = np.array([[x1, x2] for x1, x2 in zip(np.ravel(X1), np.ravel(X2))])

Z = clf.project(X).reshape(X1.shape)

# pl.contour做等值線(xiàn)圖

pl.contour(X1, X2, Z, [0.0], colors='k', linewidths=1, origin='lower')

pl.contour(X1, X2, Z + 1, [0.0], colors='grey', linewidths=1, origin='lower')

pl.contour(X1, X2, Z - 1, [0.0], colors='grey', linewidths=1, origin='lower')

pl.axis("tight")

pl.show()

def test_linear():

X1, y1, X2, y2 = gen_lin_separable_data()

X_train, y_train = split_train(X1, y1, X2, y2)

X_test, y_test = split_test(X1, y1, X2, y2)

clf = SVM()

clf.fit(X_train, y_train)

y_predict = clf.predict(X_test)

correct = np.sum(y_predict == y_test)

print("%d out of %d predictions correct" % (correct, len(y_predict)))

plot_margin(X_train[y_train==1], X_train[y_train==-1], clf)

def test_non_linear():

X1, y1, X2, y2 = gen_non_lin_separable_data()

X_train, y_train = split_train(X1, y1, X2, y2)

X_test, y_test = split_test(X1, y1, X2, y2)

clf = SVM(gaussian_kernel)

clf.fit(X_train, y_train)

y_predict = clf.predict(X_test)

correct = np.sum(y_predict == y_test)

print("%d out of %d predictions correct" % (correct, len(y_predict)))

plot_contour(X_train[y_train==1], X_train[y_train==-1], clf)

def test_soft():

X1, y1, X2, y2 = gen_lin_separable_overlap_data()

X_train, y_train = split_train(X1, y1, X2, y2)

X_test, y_test = split_test(X1, y1, X2, y2)

clf = SVM(C=0.1)

clf.fit(X_train, y_train)

y_predict = clf.predict(X_test)

correct = np.sum(y_predict == y_test)

print("%d out of %d predictions correct" % (correct, len(y_predict)))

plot_contour(X_train[y_train==1], X_train[y_train==-1], clf)

# test_soft()

# test_linear()

test_non_linear()

運(yùn)行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的python 支持向量机预测结果相同_Python机器学习算法 — 支持向量机（SVM）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。