ベクトルマシン(SVM)アルゴリズムをサポートするPython実装
10194 ワード
ベクトルマシン(SVM)アルゴリズムをサポートするPython実装
より多くの機械学習アルゴリズムの実現、詳細はhttps://github.com/WiseDoge/ML-by-Python
より多くの機械学習アルゴリズムの実現、詳細はhttps://github.com/WiseDoge/ML-by-Python
import numpy as np
class SVC(object):
"""
(Support Vector Machine) ,
。
, 1 , -1 。
, 。
"""
def __init__(self, C, e=0.3, kernel='poly'):
'''
:param C: C,
:param e: ,
:param kernel: ,
'''
self.kernel = self.poly_kern
self.e = e
self.C = C
self.bias = 0
def poly_kern(self, x, z, p=1):
'''
:param x:
:param z:
:param p: , 1, 。
:return: (np.dot(x, z) + 1) ** p
'''
return (np.dot(x, z) + 1) ** p
def fit(self, train_x, train_y):
'''
:param train_x: X
:param train_y: Y
:return: None
SVM
'''
self.train_x = train_x
self.train_y = train_y
self.alpha = np.zeros(train_x.shape[0])
while True:
index1, index2 = self.choose_alpha()
if index1 == -1:
break
if self.train(index1, index2):
break
def get_index_two(self, index1):
'''
:param index1: alpha1
:return: alpha2
SMO , alpha1 , MAX|E1 - E2| alpha2
'''
errors = np.array([abs(self.error(i) - self.error(index1)) for i in range(self.train_x.shape[0])])
return np.where(errors == errors.max())[0][0]
def choose_alpha(self):
'''
:return: alpha1 alpha2
SMO , alpha1
'''
for i in range(self.alpha.shape[0]):
if 0 < self.alpha[i] < self.C:
if 1 - self.e <= self.train_y[i] * self.g(self.train_x[i]) <= 1 + self.e:
index2 = self.get_index_two(i)
return i, index2
for i in range(self.alpha.shape[0]):
if 0 < self.alpha[i] < self.C:
continue
if self.alpha[i] == 0:
if self.train_y[i] * self.g(self.train_x[i]) < 1:
index2 = self.get_index_two(i)
return i, index2
else:
if self.train_y[i] * self.g(self.train_x[i]) > 1:
index2 = self.get_index_two(i)
return i, index2
return -1, -1
def train(self, i1, i2):
'''
:param i1: alpha1
:param i2: alpha2
:return: True, False
SMO alpha, bias
'''
x1 = self.train_x[i1]
x2 = self.train_x[i2]
y1 = self.train_y[i1]
y2 = self.train_y[i2]
old_alpha = self.alpha.copy()
eta = self.kernel(x1, x1) \
+ self.kernel(x2, x2) \
- 2.0 * self.kernel(x1, x2)
alpha2 = self.alpha[i2] \
+ self.train_y[i2] * (self.error(i1) - self.error(i2)) / eta
if y1 == y2:
l = max(0, self.alpha[i2] + self.alpha[i1] - self.C)
h = min(self.C, self.alpha[i2] + self.alpha[i1])
else:
l = max(0, self.alpha[i2] - self.alpha[i1])
h = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])
if alpha2 > h:
alpha2 = h
elif alpha2 < l:
alpha2 = l
alpha_old_1 = self.alpha[i1]
self.alpha[i1] += y1 * y2 * (self.alpha[i2] - alpha2)
self.alpha[i2] = alpha2
b1 = -1 * self.error(i1) \
- y1 * self.kernel(x1, x1) * (self.alpha[i1] - alpha_old_1) \
- y2 * self.kernel(x2, x1) * (self.alpha[2] - alpha2) \
+ self.bias
b2 = -1 * self.error(i2) \
- y1 * self.kernel(x1, x2) * (self.alpha[i1] - alpha_old_1) \
- y2 * self.kernel(x2, x2) * (self.alpha[2] - alpha2) \
+ self.bias
if 0 < self.alpha[i1] < self.C:
self.bias = b1
elif 0 < self.alpha[i2] < self.C:
self.bias = b2
else:
self.bias = 0.5 * (b1 + b2)
if np.linalg.norm(old_alpha - self.alpha) < self.e:
return True
else:
return False
def error(self, index):
'''
:param index:
:return: E(X)
E(X) = g(x) - y,
'''
return self.g(self.train_x[index]) - self.train_y[index]
def g(self, x):
'''
:param x:
:return: g(x)
g(x) = Σ(alpha[i] * y[i] * k(x, xi)) + bias
'''
ans = 0.0
for i in range(self.train_x.shape[0]):
ans += self.alpha[i] * self.train_y[i] * self.kernel(x, self.train_x[i])
return ans + self.bias
def predict_one(self, x):
'''
:param x: .
:return:
'''
return 1 if self.g(x) >= 0 else -1
def predict(self, test_x):
'''
:param test_x:
:return:
'''
return np.array([self.predict_one(x) for x in test_x])