监督学习之线性模型(3)-- 支持向量机

一、基本概念

支持向量机,因其英文名为support vector machine,故一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化。

1、支持向量与超平面

如图所示,就是一个二维几何空间中的分类。中间那条直线就是这个分类的超平面。我们不难发现,用来确定这条直线其实只需要两条虚线上的三个点就够了,其他距离很远的点,虽然是训练样本,但是因为特征太明显,不会引起歧义,也对我们分类的超平面的确定意义并不大。所以只要找到最靠近分类平面的这些点,我们就能够很好的确定出所需要的超平面。
这一部分有帮助的点的向量在几何空间中也表示向量,那么就把这些能够用来确定超平面的向量称为支持向量(直接支持超平面的生成),这也是”支持向量机”名字的由来。
训练SVM模型的过程实际上是对每个数据点对于数据分类决定边界的重要性进行判断。所以这个算法的好处就很明显了,任你训练样本如何庞大,只需要找到支持向量就能很好的完成任务了,计算量就大大缩小了。

2、寻找合适的超平面(线性)

首先,在下面的场景1中我们有三个超平面(A、B、C)。我们需要用正确的超平面对星形和圆形进行分类。

场景1

需要记住一个经验的法则来识别正确的超平面:“选择更好的可以隔离两个类别的超平面”。在这种情况下,超平面B就非常完美的完成了这项工作。
接下来,在下面的场景2中我们又有三个超平面(A,B,C),并且所有这些超平面都很好地隔离了类。现在,我们如何选择正确的超平面?

场景2

在这里,将最近的数据点(任一类)和超平面之间的距离最大化将有
助于我们选择正确的超平面。该距离称为”边距”。让我们看一下下面的图片:

可以看到超平面C的边距与A和B相比都很高。因此,我们将正确的超平面选择为C。选择边距较高的超平面的另一个决定性因素是稳健性。如果我们选择一个低边距的超平面,那么很有可能进行错误分类。

3、寻找合适的超平面(非线性)

有时候我们无法使用直线来分隔两个类,如下面的场景3。

场景3

但是SVM可以通过引入额外的特征来解决这个问题!在这里我们引入一个新的特征z代表x和y的平方和。在原图中,红色圆圈出现在靠近x和y轴原点的位置,导致z值比较低。星形相对远离原点,导致z值较高。这样一来,很容易就可以在这两个类之间建立线性超平面。

但是另一个需要解决的问题是,我们是否需要总是手动添加特征来获得超平面?不,并不需要这么做,SVM提供了一些函数用于把低维度的输入空间转换为更高维度的空间,也就是将不可分离的问题转换为可分离的问题,这些函数称为”核函数”。

核函数
简单来说,核函数会执行一些非常复杂的数据转换,然后根据你定义的标签找出分离数据的过程。

二、SVM的优缺点

优点:
解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。
有大量的核函数可以使用,从而可以很灵活的来解决各种非线性的分类回归问题。
缺点:
如果特征维度远远大于样本数时,SVM表现一般。
非线性问题的核函数的选择没有通用标准,难以选择一个合适的核函数。
SVM在样本量非常大,核函数映射维度非常高时,计算量过大,不太适合使用。
当数据集具有很多噪声,也就是目标类重叠时,它的表现性能也不会很好。

三、SVM的实现

1、sklearn版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import numpy as np
import matplotlib.pyplot as plt
from pylab import show
from sklearn import svm

np.random.seed(0)
X = np.r_[np.random.randn(20,2)-[2,2],np.random.randn(20,2)+[2,2]] # 随机生成左下方20个点,右上方20个点
Y = [0]*20+[1]*20 # 将前20个归为标记0,后20个归为标记1

# 建立模型
clf = svm.SVC(kernel='linear')
clf.fit(X,Y) # 传入参数

# 画出建立的超平面
w = clf.coef_[0] # 取得w值,w是二维的
a = -w[0]/w[1] # 计算直线斜率
xx = np.linspace(-5,5) # 随机产生连续x值
yy = a*xx-(clf.intercept_[0])/w[1] # 根据随机x得到y值

# 计算与直线相平行的两条直线
b = clf.support_vectors_[0]
yy_down = a*xx+(b[1]-a*b[0])
b = clf.support_vectors_[-1]
yy_up = a*xx+(b[1]-a*b[0])

print('w:',w)
print('a:',a)
print('support_vectors:',clf.support_vectors_)
print('clf.coef_',clf.coef_)

# 画出三条直线
plt.plot(xx,yy,'k-')
plt.plot(xx,yy_down,'k--')
plt.plot(xx,yy_up,'k--')

plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],s=80,facecolors='none')
plt.scatter(X[:,0],X[:,1],c=Y, cmap=plt.cm.Paired)

plt.axis('tight')
plt.show()

了解更多1
了解更多2

2、源码版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
import math
from sklearn.datasets.samples_generator import make_blobs

#========================================================
# step 1: 构造数据
#========================================================
X, y = make_blobs(n_samples=50,
n_features=2,
centers=2,
cluster_std=1.05,
random_state=40)

# plt.scatter(X[:,0], X[:,1],marker='o', c=y)
# plt.axis([-5,10,-12,-1])
# plt.show()

#========================================================
# step 2: 数据分堆
#========================================================

positive_data = list()
negative_data = list()
for i, v in enumerate(y):
if v == 0:
negative_data.append(X[i])
else:
positive_data.append(X[i])

data_dict = {1: np.array(positive_data), -1: np.array(negative_data)}
# print(data_dict)

#========================================================
# step 3: svm训练
#========================================================

w = [] # weights 2 dimesional vector
b = [] # bias
max_feature_value = float('-inf')
min_feature_value = float('+inf')

for yi in data_dict:
if np.amax(data_dict[yi]) > max_feature_value:
max_feature_value = np.amax(data_dict[yi])

if np.amin(data_dict[yi]) < min_feature_value:
min_feature_value = np.amin(data_dict[yi])

# print(max_feature_value, min_feature_value)
learning_rates = [max_feature_value * 0.1,
max_feature_value * 0.01,
max_feature_value * 0.001]

def svm_training(data_dict):
i = 1
global w
global b

length_w_vector = {}
transforms = [[1, 1], [-1, 1], [-1, -1], [1, -1]]
b_step_size = 2
b_multiple = 5
w_optimum = max_feature_value * 0.5

for rate in learning_rates:
w = np.array([w_optimum, w_optimum])
optimized = False

while not optimized:
for b in np.arange(-1 * (max_feature_value * b_step_size), max_feature_value * b_step_size,
rate * b_multiple):
for transformation in transforms:
w_t = w * transformation
correctly_classified = True

for yi in data_dict:
for xi in data_dict[yi]:
if yi * (np.dot(w_t, xi) + b) < 1:
correctly_classified = False

if correctly_classified:
length_w_vector[np.linalg.norm(w_t)] = [w_t, b]
if w[0] < 0:
optimized = True
else:
w = w - rate

norms = sorted([n for n in length_w_vector])

minimum_w_length = length_w_vector[norms[0]]
w = minimum_w_length[0]
b = minimum_w_length[1]

w_optimum = w[0] + rate * 2

svm_training(data_dict)

print("w: ", w)
print("b: ", b)

#========================================================
# step 4: 绘制svm分类结果
#========================================================

colors = {1:'r',-1:'b'}
fig = plt.figure()
ax = fig.add_subplot(1,1,1)

def visualize(data_dict):
plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)

# hyperplane = x.w+b
# v = x.w+b
# psv = 1
# nsv = -1
# dec = 0
def hyperplane_value(x, w, b, v):
return (-w[0] * x - b + v) / w[1]

datarange = (min_feature_value * 0.9, max_feature_value * 1.)
hyp_x_min = datarange[0]
hyp_x_max = datarange[1]

# (w.x+b) = 1
# positive support vector hyperplane
psv1 = hyperplane_value(hyp_x_min, w, b, 1)
psv2 = hyperplane_value(hyp_x_max, w, b, 1)
ax.plot([hyp_x_min, hyp_x_max], [psv1, psv2], 'y--')

# (w.x+b) = -1
# negative support vector hyperplane
nsv1 = hyperplane_value(hyp_x_min, w, b, -1)
nsv2 = hyperplane_value(hyp_x_max, w, b, -1)
ax.plot([hyp_x_min, hyp_x_max], [nsv1, nsv2], 'y--')

# (w.x+b) = 0
# positive support vector hyperplane
db1 = hyperplane_value(hyp_x_min, w, b, 0)
db2 = hyperplane_value(hyp_x_max, w, b, 0)
ax.plot([hyp_x_min, hyp_x_max], [db1, db2], 'k')

plt.axis([-5, 10, -12, -1])
plt.show()

visualize(data_dict)

了解更多

0%