感知机概要如下：
误分类驱动，只能用于线性可分数据，损失函数定义为错分点到超平面的函数间隔 sigma_i( -yi*(wi*x+b) ) 对于每个被错分的 (xi,yi)正确分类样本损失为0，误分类损失就是函数间隔，类似铰链损失向左移动学习采用随机梯度下降法，每次选取一个误分类样本来更新w,b选定一个误分类样本(xi,yi)， w += yi*xi*ita，b += yi*ita，其中ita为学习率 代码如下： #%% 感知机算法 import random class Perceptron(object): def __init__(self, train_x, train_y, ita=None): self.ita = 0.1 if ita is None else ita self.train_x = train_x self.train_y = train_y self.n_sample = len(train_x) self.dimension = len(train_x[0]) self.w, self.b = [0]*self.dimension, 0 def inner_product(self,a,b): return sum([x*y for x,y in zip(a,b)]) def cal_loss(self): # 损失函数为 sigma( -yi*(wi*x+b) ) 对于每个被错分的 (xi,yi) each_loss = [-y*(self.inner_product(self.w, x)+self.b) for \ (x, y) in zip(self.train_x, self.train_y)] self.mis_classify_loss = sum(filter(lambda x:x>=0, each_loss)) mis_classify_i = [] for i in range(self.n_sample): if each_loss[i]>=0: mis_classify_i.append(i) # 在误分类样本中随机选择一个进行随机梯度下降 if mis_classify_i==[]: return -1 else: return random.sample(mis_classify_i, 1)[0] @timeit def training(self): i_chosen = self.cal_loss() i_round = 0 while i_chosen != -1: i_round += 1 print 'training round', i_round, ', loss =', self.mis_classify_loss, ', i_chosen = ', i_chosen # 更新w和b self.w = [wi+self.ita*self.train_y[i_chosen]*xi for \ (wi, xi) in zip(self.w, self.train_x[i_chosen])] self.b += self.ita*self.train_y[i_chosen] print [round(wi,2) for wi in self.w], round(self.b,2) i_chosen = self.cal_loss() print 'training done!' return self.w, self.b def test_Perceptron(): train_x = [[1,1], [1,1.9], [2,0.8], [1.5,1.4], [0,0], [1.5,1.6],[3,1],[2,2]] train_y = [-1, -1, -1, -1, -1, 1, 1, 1] p = Perceptron(train_x, train_y, 1) w, b = p.training() pre_y = map(lambda x:p.inner_product(w,x)+b, train_x) print train_y test_Perceptron() 结果如下： training round 1 , loss = 0.0 , i_chosen = 2 [-2.0, -0.8] -1.0 training round 2 , loss = 19.68 , i_chosen = 5 [-0.5, 0.8] 0.0 training round 3 , loss = 2.39 , i_chosen = 6 [2.5, 1.8] 1.0 training round 4 , loss = 27.93 , i_chosen = 1 [1.5, -0.1] 0.0 training round 5 , loss = 7.74 , i_chosen = 3 [0.0, -1.5] -1.0 training round 6 , loss = 9.9 , i_chosen = 7 [2.0, 0.5] 0.0 training round 7 , loss = 13.55 , i_chosen = 1 [1.0, -1.4] -1.0 training round 8 , loss = 3.54 , i_chosen = 7 [3.0, 0.6] 0.0 training round 9 , loss = 19.56 , i_chosen = 0 [2.0, -0.4] -1.0 training round 10 , loss = 4.96 , i_chosen = 0 [1.0, -1.4] -2.0 training round 11 , loss = 5.94 , i_chosen = 7 [3.0, 0.6] -1.0 training round 12 , loss = 15.56 , i_chosen = 1 [2.0, -1.3] -2.0 training round 13 , loss = 2.64 , i_chosen = 2 [0.0, -2.1] -3.0 training round 14 , loss = 18.66 , i_chosen = 6 [3.0, -1.1] -2.0 training round 15 , loss = 4.08 , i_chosen = 2 [1.0, -1.9] -3.0 training round 16 , loss = 11.24 , i_chosen = 6 [4.0, -0.9] -2.0 training round 17 , loss = 9.41 , i_chosen = 0 [3.0, -1.9] -3.0 training round 18 , loss = 3.82 , i_chosen = 5 [4.5, -0.3] -2.0 training round 19 , loss = 15.22 , i_chosen = 1 [3.5, -2.2] -3.0 training round 20 , loss = 3.91 , i_chosen = 2 [1.5, -3.0] -4.0 training round 21 , loss = 16.05 , i_chosen = 5 [3.0, -1.4] -3.0 training round 22 , loss = 2.62 , i_chosen = 2 [1.0, -2.2] -4.0 training round 23 , loss = 15.62 , i_chosen = 7 [3.0, -0.2] -3.0 training round 24 , loss = 4.06 , i_chosen = 2 [1.0, -1.0] -4.0 training round 25 , loss = 10.1 , i_chosen = 7 [3.0, 1.0] -3.0 training round 26 , loss = 9.6 , i_chosen = 3 [1.5, -0.4] -4.0 training round 27 , loss = 4.19 , i_chosen = 5 [3.0, 1.2] -3.0 training round 28 , loss = 10.62 , i_chosen = 1 [2.0, -0.7] -4.0 training round 29 , loss = 3.52 , i_chosen = 7 [4.0, 1.3] -3.0 training round 30 , loss = 16.63 , i_chosen = 2 [2.0, 0.5] -4.0 training round 31 , loss = 0.6 , i_chosen = 2 [0.0, -0.3] -5.0 training round 32 , loss = 16.38 , i_chosen = 7 [2.0, 1.7] -4.0 training round 33 , loss = 3.97 , i_chosen = 3 [0.5, 0.3] -5.0 training round 34 , loss = 10.37 , i_chosen = 6 [3.5, 1.3] -4.0 training round 35 , loss = 9.88 , i_chosen = 1 [2.5, -0.6] -5.0 training round 36 , loss = 3.41 , i_chosen = 7 [4.5, 1.4] -4.0 training round 37 , loss = 15.89 , i_chosen = 1 [3.5, -0.5] -5.0 training round 38 , loss = 2.15 , i_chosen = 2 [1.5, -1.3] -6.0 training round 39 , loss = 14.23 , i_chosen = 7 [3.5, 0.7] -5.0 training round 40 , loss = 3.79 , i_chosen = 3 [2.0, -0.7] -6.0 training round 41 , loss = 8.22 , i_chosen = 5 [3.5, 0.9] -5.0 training round 42 , loss = 4.44 , i_chosen = 1 [2.5, -1.0] -6.0 training round 43 , loss = 6.85 , i_chosen = 7 [4.5, 1.0] -5.0 training round 44 , loss = 9.85 , i_chosen = 0 [3.5, 0.0] -6.0 training round 45 , loss = 1.75 , i_chosen = 2 [1.5, -0.8] -7.0 training round 46 , loss = 14.93 , i_chosen = 6 [4.5, 0.2] -6.0 training round 47 , loss = 4.19 , i_chosen = 3 [3.0, -1.2] -7.0 training round 48 , loss = 7.82 , i_chosen = 7 [5.0, 0.8] -6.0 training round 49 , loss = 7.78 , i_chosen = 3 [3.5, -0.6] -7.0 training round 50 , loss = 3.91 , i_chosen = 5 [5.0, 1.0] -6.0 training round 51 , loss = 8.6 , i_chosen = 1 [4.0, -0.9] -7.0 training round 52 , loss = 3.52 , i_chosen = 2 [2.0, -1.7] -8.0 training round 53 , loss = 18.82 , i_chosen = 5 [3.5, -0.1] -7.0 training round 54 , loss = 2.11 , i_chosen = 5 [5.0, 1.5] -6.0 training round 55 , loss = 11.15 , i_chosen = 1 [4.0, -0.4] -7.0 training round 56 , loss = 2.32 , i_chosen = 5 [5.5, 1.2] -6.0 training round 57 , loss = 12.37 , i_chosen = 1 [4.5, -0.7] -7.0 training round 58 , loss = 2.81 , i_chosen = 2 [2.5, -1.5] -8.0 training round 59 , loss = 14.65 , i_chosen = 5 [4.0, 0.1] -7.0 training round 60 , loss = 1.92 , i_chosen = 2 [2.0, -0.7] -8.0 training round 61 , loss = 14.22 , i_chosen = 5 [3.5, 0.9] -7.0 training round 62 , loss = 1.03 , i_chosen = 2 [1.5, 0.1] -8.0 training round 63 , loss = 13.79 , i_chosen = 7 [3.5, 2.1] -7.0 training round 64 , loss = 3.36 , i_chosen = 1 [2.5, 0.2] -8.0 training round 65 , loss = 6.83 , i_chosen = 6 [5.5, 1.2] -7.0 training round 66 , loss = 8.67 , i_chosen = 2 [3.5, 0.4] -8.0 training round 67 , loss = 2.31 , i_chosen = 5 [5.0, 2.0] -7.0 training round 68 , loss = 9.7 , i_chosen = 0 [4.0, 1.0] -8.0 training round 69 , loss = 1.2 , i_chosen = 5 [5.5, 2.6] -7.0 training round 70 , loss = 15.51 , i_chosen = 0 [4.5, 1.6] -8.0 training round 71 , loss = 3.27 , i_chosen = 2 [2.5, 0.8] -9.0 training round 72 , loss = 7.07 , i_chosen = 6 [5.5, 1.8] -8.0 training round 73 , loss = 8.13 , i_chosen = 3 [4.0, 0.4] -9.0 training round 74 , loss = 2.56 , i_chosen = 5 [5.5, 2.0] -8.0 training round 75 , loss = 8.95 , i_chosen = 1 [4.5, 0.1] -9.0 training round 76 , loss = 2.17 , i_chosen = 2 [2.5, -0.7] -10.0 training round 77 , loss = 16.97 , i_chosen = 5 [4.0, 0.9] -9.0 training round 78 , loss = 1.56 , i_chosen = 5 [5.5, 2.5] -8.0 training round 79 , loss = 11.0 , i_chosen = 0 [4.5, 1.5] -9.0 training round 80 , loss = 1.2 , i_chosen = 2 [2.5, 0.7] -10.0 training round 81 , loss = 10.53 , i_chosen = 5 [4.0, 2.3] -9.0 training round 82 , loss = 1.06 , i_chosen = 2 [2.0, 1.5] -10.0 training round 83 , loss = 10.1 , i_chosen = 6 [5.0, 2.5] -9.0 training round 84 , loss = 5.75 , i_chosen = 2 [3.0, 1.7] -10.0 training round 85 , loss = 3.38 , i_chosen = 5 [4.5, 3.3] -9.0 training round 86 , loss = 6.78 , i_chosen = 1 [3.5, 1.4] -10.0 training round 87 , loss = 2.71 , i_chosen = 5 [5.0, 3.0] -9.0 training round 88 , loss = 7.8 , i_chosen = 1 [4.0, 1.1] -10.0 training round 89 , loss = 2.24 , i_chosen = 5 [5.5, 2.7] -9.0 training round 90 , loss = 8.82 , i_chosen = 1 [4.5, 0.8] -10.0 training round 91 , loss = 1.97 , i_chosen = 5 [6.0, 2.4] -9.0 training round 92 , loss = 9.84 , i_chosen = 2 [4.0, 1.6] -10.0 training round 93 , loss = 1.44 , i_chosen = 5 [5.5, 3.2] -9.0 training round 94 , loss = 10.87 , i_chosen = 3 [4.0, 1.8] -10.0 training round 95 , loss = 1.12 , i_chosen = 5 [5.5, 3.4] -9.0 training round 96 , loss = 11.69 , i_chosen = 2 [3.5, 2.6] -10.0 training round 97 , loss = 0.59 , i_chosen = 5 [5.0, 4.2] -9.0 training round 98 , loss = 12.92 , i_chosen = 0 [4.0, 3.2] -10.0 training round 99 , loss = 1.12 , i_chosen = 3 [2.5, 1.8] -11.0 training round 100 , loss = 8.47 , i_chosen = 7 [4.5, 3.8] -10.0 training round 101 , loss = 5.83 , i_chosen = 1 [3.5, 1.9] -11.0 training round 102 , loss = 2.91 , i_chosen = 5 [5.0, 3.5] -10.0 training round 103 , loss = 6.85 , i_chosen = 1 [4.0, 1.6] -11.0 training round 104 , loss = 2.44 , i_chosen = 5 [5.5, 3.2] -10.0 training round 105 , loss = 7.87 , i_chosen = 2 [3.5, 2.4] -11.0 training round 106 , loss = 1.91 , i_chosen = 5 [5.0, 4.0] -10.0 training round 107 , loss = 8.9 , i_chosen = 1 [4.0, 2.1] -11.0 training round 108 , loss = 1.64 , i_chosen = 5 [5.5, 3.7] -10.0 training round 109 , loss = 9.92 , i_chosen = 1 [4.5, 1.8] -11.0 training round 110 , loss = 1.37 , i_chosen = 5 [6.0, 3.4] -10.0 training round 111 , loss = 10.94 , i_chosen = 2 [4.0, 2.6] -11.0 training round 112 , loss = 0.84 , i_chosen = 5 [5.5, 4.2] -10.0 training round 113 , loss = 11.97 , i_chosen = 3 [4.0, 2.8] -11.0 training round 114 , loss = 0.52 , i_chosen = 5 [5.5, 4.4] -10.0 training round 115 , loss = 12.79 , i_chosen = 2 [3.5, 3.6] -11.0 training done! [-1, -1, -1, -1, -1, 1, 1, 1] >>> runfile('C:/Users/Administrator/Desktop/algorithm.py', wdir='C:/Users/Administrator/Desktop') training round 1 , loss = 0.0 , i_chosen = 0 [-1.0, -1.0] -1.0 training round 2 , loss = 14.1 , i_chosen = 7 [1.0, 1.0] 0.0 training round 3 , loss = 10.6 , i_chosen = 0 [0.0, 0.0] -1.0 training round 4 , loss = 3.0 , i_chosen = 7 [2.0, 2.0] 0.0 training round 5 , loss = 21.2 , i_chosen = 4 [2.0, 2.0] -1.0 training round 6 , loss = 17.2 , i_chosen = 2 [0.0, 1.2] -2.0 training round 7 , loss = 1.16 , i_chosen = 5 [1.5, 2.8] -1.0 training round 8 , loss = 18.53 , i_chosen = 2 [-0.5, 2.0] -2.0 training round 9 , loss = 2.85 , i_chosen = 6 [2.5, 3.0] -1.0 training round 10 , loss = 25.05 , i_chosen = 0 [1.5, 2.0] -2.0 training round 11 , loss = 10.45 , i_chosen = 0 [0.5, 1.0] -3.0 training round 12 , loss = 1.15 , i_chosen = 7 [2.5, 3.0] -2.0 training round 13 , loss = 21.05 , i_chosen = 0 [1.5, 2.0] -3.0 training round 14 , loss = 6.45 , i_chosen = 3 [0.0, 0.6] -4.0 training round 15 , loss = 9.24 , i_chosen = 5 [1.5, 2.2] -3.0 training round 16 , loss = 7.47 , i_chosen = 3 [0.0, 0.8] -4.0 training round 17 , loss = 8.32 , i_chosen = 7 [2.0, 2.8] -3.0 training round 18 , loss = 13.28 , i_chosen = 3 [0.5, 1.4] -4.0 training round 19 , loss = 2.31 , i_chosen = 6 [3.5, 2.4] -3.0 training round 20 , loss = 19.49 , i_chosen = 3 [2.0, 1.0] -4.0 training round 21 , loss = 1.2 , i_chosen = 3 [0.5, -0.4] -5.0 training round 22 , loss = 13.59 , i_chosen = 5 [2.0, 1.2] -4.0 training round 23 , loss = 1.92 , i_chosen = 1 [1.0, -0.7] -5.0 training round 24 , loss = 11.72 , i_chosen = 6 [4.0, 0.3] -4.0 training round 25 , loss = 7.53 , i_chosen = 2 [2.0, -0.5] -5.0 training round 26 , loss = 4.8 , i_chosen = 5 [3.5, 1.1] -4.0 training round 27 , loss = 8.86 , i_chosen = 3 [2.0, -0.3] -5.0 training round 28 , loss = 4.08 , i_chosen = 5 [3.5, 1.3] -4.0 training round 29 , loss = 9.88 , i_chosen = 0 [2.5, 0.3] -5.0 training round 30 , loss = 1.01 , i_chosen = 5 [4.0, 1.9] -4.0 training round 31 , loss = 15.69 , i_chosen = 1 [3.0, 0.0] -5.0 training round 32 , loss = 1.5 , i_chosen = 5 [4.5, 1.6] -4.0 training round 33 , loss = 16.91 , i_chosen = 3 [3.0, 0.2] -5.0 training round 34 , loss = 1.34 , i_chosen = 5 [4.5, 1.8] -4.0 training round 35 , loss = 17.93 , i_chosen = 1 [3.5, -0.1] -5.0 training round 36 , loss = 2.03 , i_chosen = 2 [1.5, -0.9] -6.0 training round 37 , loss = 12.39 , i_chosen = 6 [4.5, 0.1] -5.0 training round 38 , loss = 5.97 , i_chosen = 3 [3.0, -1.3] -6.0 training round 39 , loss = 6.18 , i_chosen = 7 [5.0, 0.7] -5.0 training round 40 , loss = 11.07 , i_chosen = 1 [4.0, -1.2] -6.0 training round 41 , loss = 3.36 , i_chosen = 5 [5.5, 0.4] -5.0 training round 42 , loss = 12.29 , i_chosen = 3 [4.0, -1.0] -6.0 training round 43 , loss = 2.8 , i_chosen = 5 [5.5, 0.6] -5.0 training round 44 , loss = 13.31 , i_chosen = 2 [3.5, -0.2] -6.0 training round 45 , loss = 1.91 , i_chosen = 5 [5.0, 1.4] -5.0 training round 46 , loss = 14.64 , i_chosen = 3 [3.5, 0.0] -6.0 training round 47 , loss = 1.75 , i_chosen = 2 [1.5, -0.8] -7.0 training round 48 , loss = 14.93 , i_chosen = 7 [3.5, 1.2] -6.0 training round 49 , loss = 2.89 , i_chosen = 3 [2.0, -0.2] -7.0 training round 50 , loss = 8.92 , i_chosen = 6 [5.0, 0.8] -6.0 training round 51 , loss = 7.78 , i_chosen = 1 [4.0, -1.1] -7.0 training round 52 , loss = 4.08 , i_chosen = 2 [2.0, -1.9] -8.0 training round 53 , loss = 19.74 , i_chosen = 6 [5.0, -0.9] -7.0 training round 54 , loss = 3.22 , i_chosen = 2 [3.0, -1.7] -8.0 training round 55 , loss = 12.32 , i_chosen = 6 [6.0, -0.7] -7.0 training round 56 , loss = 5.46 , i_chosen = 3 [4.5, -2.1] -8.0 training round 57 , loss = 7.81 , i_chosen = 5 [6.0, -0.5] -7.0 training round 58 , loss = 5.9 , i_chosen = 3 [4.5, -1.9] -8.0 training round 59 , loss = 7.09 , i_chosen = 7 [6.5, 0.1] -7.0 training round 60 , loss = 8.97 , i_chosen = 3 [5.0, -1.3] -8.0 training round 61 , loss = 4.14 , i_chosen = 5 [6.5, 0.3] -7.0 training round 62 , loss = 9.48 , i_chosen = 3 [5.0, -1.1] -8.0 training round 63 , loss = 3.58 , i_chosen = 2 [3.0, -1.9] -9.0 training round 64 , loss = 16.24 , i_chosen = 6 [6.0, -0.9] -8.0 training round 65 , loss = 3.72 , i_chosen = 5 [7.5, 0.7] -7.0 training round 66 , loss = 16.82 , i_chosen = 1 [6.5, -1.2] -8.0 training round 67 , loss = 4.28 , i_chosen = 2 [4.5, -2.0] -9.0 training round 68 , loss = 9.45 , i_chosen = 7 [6.5, 0.0] -8.0 training round 69 , loss = 6.75 , i_chosen = 3 [5.0, -1.4] -9.0 training round 70 , loss = 5.54 , i_chosen = 7 [7.0, 0.6] -8.0 training round 71 , loss = 9.96 , i_chosen = 1 [6.0, -1.3] -9.0 training round 72 , loss = 4.04 , i_chosen = 2 [4.0, -2.1] -10.0 training round 73 , loss = 13.66 , i_chosen = 5 [5.5, -0.5] -9.0 training round 74 , loss = 3.15 , i_chosen = 5 [7.0, 1.1] -8.0 training round 75 , loss = 12.11 , i_chosen = 2 [5.0, 0.3] -9.0 training round 76 , loss = 2.26 , i_chosen = 5 [6.5, 1.9] -8.0 training round 77 , loss = 13.44 , i_chosen = 2 [4.5, 1.1] -9.0 training round 78 , loss = 1.37 , i_chosen = 2 [2.5, 0.3] -10.0 training round 79 , loss = 12.37 , i_chosen = 7 [4.5, 2.3] -9.0 training round 80 , loss = 2.81 , i_chosen = 3 [3.0, 0.9] -10.0 training round 81 , loss = 6.36 , i_chosen = 7 [5.0, 2.9] -9.0 training round 82 , loss = 7.39 , i_chosen = 1 [4.0, 1.0] -10.0 training round 83 , loss = 2.4 , i_chosen = 5 [5.5, 2.6] -9.0 training round 84 , loss = 8.41 , i_chosen = 2 [3.5, 1.8] -10.0 training round 85 , loss = 1.87 , i_chosen = 5 [5.0, 3.4] -9.0 training round 86 , loss = 9.44 , i_chosen = 2 [3.0, 2.6] -10.0 training round 87 , loss = 1.34 , i_chosen = 5 [4.5, 4.2] -9.0 training round 88 , loss = 10.47 , i_chosen = 1 [3.5, 2.3] -10.0 training round 89 , loss = 1.07 , i_chosen = 5 [5.0, 3.9] -9.0 training round 90 , loss = 11.49 , i_chosen = 1 [4.0, 2.0] -10.0 training round 91 , loss = 0.8 , i_chosen = 5 [5.5, 3.6] -9.0 training round 92 , loss = 12.61 , i_chosen = 2 [3.5, 2.8] -10.0 training round 93 , loss = 0.27 , i_chosen = 5 [5.0, 4.4] -9.0 training round 94 , loss = 13.94 , i_chosen = 0 [4.0, 3.4] -10.0 training round 95 , loss = 1.94 , i_chosen = 3 [2.5, 2.0] -11.0 training round 96 , loss = 7.55 , i_chosen = 7 [4.5, 4.0] -10.0 training round 97 , loss = 6.65 , i_chosen = 1 [3.5, 2.1] -11.0 training round 98 , loss = 2.39 , i_chosen = 5 [5.0, 3.7] -10.0 training round 99 , loss = 7.67 , i_chosen = 1 [4.0, 1.8] -11.0 training round 100 , loss = 2.12 , i_chosen = 5 [5.5, 3.4] -10.0 training round 101 , loss = 8.69 , i_chosen = 2 [3.5, 2.6] -11.0 training round 102 , loss = 1.59 , i_chosen = 5 [5.0, 4.2] -10.0 training round 103 , loss = 9.72 , i_chosen = 3 [3.5, 2.8] -11.0 training round 104 , loss = 1.27 , i_chosen = 5 [5.0, 4.4] -10.0 training round 105 , loss = 10.54 , i_chosen = 3 [3.5, 3.0] -11.0 training round 106 , loss = 0.95 , i_chosen = 5 [5.0, 4.6] -10.0 training round 107 , loss = 11.36 , i_chosen = 3 [3.5, 3.2] -11.0 training round 108 , loss = 0.63 , i_chosen = 5 [5.0, 4.8] -10.0 training round 109 , loss = 12.18 , i_chosen = 1 [4.0, 2.9] -11.0 training round 110 , loss = 0.36 , i_chosen = 5 [5.5, 4.5] -10.0 training round 111 , loss = 13.2 , i_chosen = 2 [3.5, 3.7] -11.0 training done! time consuming: 0.0100946187692 [-1, -1, -1, -1, -1, 1, 1, 1]