本文介绍感知机定义以及推导过程，并使用python代码实现。也介绍了对偶形式的实现和原理。
1. 感知机定义
感知机(perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应输入空间将实例划分为正负两类的分离超平面，属于判别模型。
感知机学习目的在于求出将训练数据进行线性划分的分离超平面，为此导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。
给定一个n维输入$x = (x_1,x_2,\dots,x_n)$。
其中，$W$是n维的权重向量，b是偏置项。W和b是未知的，需要从给定的训练数据学习得到。
如果使用增广的输入和权重向量，那么公式简写为：
2. 学习算法
如果给定N个训练样本$(X_i,y_i), i = 1,\dots,N$，我们希望学习得到$W^{*}$。
公式等价于$W^{*T} (y_iX_i) > 0$
假设训练数据集是线性可分的，感知机学习目的求一个能够将训练集正负实例点完全正确分开的分离超平面。为了找到这样的超平面，我们需要确定学习策略，即定义损失函数，并将损失函数极小化。
损失函数选择为误分类点到超平面S的总距离。首先输入空间$R^n$中任一点$x_0$到超平面S距离：
这里$||W||$是$W$的$L_2$范数。
对于误分类的数据$(X_i,y_i)$来说，
用增广的输入和权重向量那就是，以下都用增广向量表示：
因为当$W^T X_i > 0, y_i = -1$，当$W^T X_i < 0, y_i = +1$，所以可以得到误分类点到超平面S的总距离。假设超平面S的误分类点集合为M。
不考虑$\frac{1}{||W||}$，就得到感知机($sign(W^T X)$)学习的损失函数。
M是超平面误分类点集合。
显然损失函数$L(y,f(X,W))$是非负的，并且给定训练数据集，损失函数是连续可导函数。可以使用梯度下降法进行求解。
3. 随机梯度下降法求解
目前问题已经化解为求解如下函数的极值问题。
首先任意选取一个超平面$W_0$(包括w,和b的增广向量)
每次迭代，随机选取一个误分类点$(X_i,y_i)$，也就是
其中$\lambda$是步长，通过迭代可以期待损失函数不断减小，直到0为止。
4. 算法原始形式
输入：$T=\{(X_1,y_1),(X_2,y_2)…(X_N,y_N)\}$,其中$X_i \in X = R^n，yi \in Y = {-1, +1}，i = 1,2…N$，学习速率为$\lambda$。
输出：$W^{*}$;
感知机模型（增广向量形式）：
(1) 初始化$W_0$
(2) 在训练数据集中选取$(X_i, y_i)$
(3) 如果$y_i (W^T X_i) ≤ 0$
(4) 转至（2）
下面是一个感知机学习过程图：
5. 对偶形式
对偶形式的基本想法是，将W和b表示为实例$X_i$和标记$y_i$的线性组合的形式，通过求解其系数而得到W和b。假设按照之前的修改过程经过n次。那么W，b关于$(x_i,y_i)$的增量为$a_iy_ix_i$和$a_iy_i$，其中$a_i=n_i\lambda$。那么最后的W和b可以表示：
如果是增广形式，那么就是。
这里的$a_i \ge 0, i = 1,2,\dots,N，当\lambda=1$,表示第i个实例点犹豫误分类而进行更新的次数，实例点更新次数越多，那么它距离分离超平面越近，也就越难分类。换句话，这些事例对学习结果影响最大。
输入：$T = \{ (X_1,y_1),(X_2,y_2)…(X_N,y_N) \} $ 其中$X_i \in X = R^n，yi \in Y = {-1, +1}，i = 1,2…N$，学习速率为$\lambda$。
输出：a,b;
感知机模型
(1) 初始化$w_0,b_0$
(2) 在训练数据集中选取$(x_i, y_i)$
(3) 如果 $y_i (\sum_{j=1}^{N}a_jy_jx_j \cdot x_i + b) \le 0$
(4) 转至（2）
对偶形式中训练数据仅以内积的形式出现，为了方便可以预先把训练数据间内积计算出来并以矩阵的形式存储起来，这个矩阵就是所谓的Gram矩阵。
6. 代码实现
整个代码放到我的GitHub上了。分为train和test，每个都是500行数据。train做训练集。
trainFile = ‘data/perceptron_train.txt’
testFile = ‘data/perceptron_test.txt’
数据格式为：
0.94544 0.42842 0.79833 0.16244 -1
0.85365 0.084168 0.5682 0.49221 -1
0.17095 0.82127 0.98444 0.51486 -1
0.51412 0.92124 0.42323 0.097934 -1
0.28147 0.71434 0.075309 0.9116 1
0.46295 0.64512 0.96324 0.31516 -1
0.97789 0.80155 0.90235 0.74203 -1
0.41825 0.69419 0.46246 0.31523 -1
0.75203 0.20264 0.8765 0.47593 -1
程序源码：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# -*- coding: utf-8 -*-
# @Author: Lich_Amnesia
# @Email: [email protected]
# @Date: 2016-04-12 15:40:14
# @Last Modified time: 2016-04-12 18:25:20
# @FileName: Perceptron.py
import numpy as np
import matplotlib.pyplot as plt
import sys,os
# process the origin data to formatted train/test data like the following
# train.txt
# 0.28147 0.71434 0.075309 0.9116 1
# 0.46295 0.64512 0.96324 0.31516 -1
# Also random generate train/test dataset.
# All the dataset size is 500, 500 for test set and other for training.
# load data from train/test file.
def loadData():
trainFile = 'data/perceptron_train.txt'
testFile = 'data/perceptron_test.txt'
trainDataSet = np.loadtxt(open(trainFile,"rb"))
testDataSet = np.loadtxt(open(testFile,"rb"))
# Add X0 to the dataSet
X0 = np.array([1.0 for i in range(trainDataSet.shape[0])])
trainDataSet = np.c_[X0,trainDataSet]
X0 = np.array([1.0 for i in range(testDataSet.shape[0])])
testDataSet = np.c_[X0,testDataSet]
return trainDataSet, testDataSet
# normalization,
def norm(input_x):
mean = np.mean(input_x,axis=0)
std = np.std(input_x,axis=0)
n, m = input_x.shape
for i in range(n):
for j in range(m):
if std[j] != 0:
input_x[i][j] = (input_x[i][j] - mean[j]) / std[j]
return input_x
class Perceptron:
def __init__(self, W, alpha, eps = 1e-8):
self.W = np.mat(W)
self.alpha = alpha
self.eps = eps
def loss(self, x, y):
return y * (np.dot(self.W.T,x.T))
def sgd(self, x, y):
self.W += (self.alpha * y * x).T
def train(self, trainDataSet):
X_parameters, Y_parameters = trainDataSet[:,:-1],trainDataSet[:,-1]
# X_parameters = norm(X_parameters)
X_mat = np.mat(X_parameters) # size: n * m (m = 6 now, has X_0)
y_mat = np.mat(Y_parameters).T # size: 1 * n
n, m = X_mat.shape
while True:
M = len(X_mat) # wrong classification number
for i in range(len(X_mat)):
if self.loss(X_mat[i], y_mat[i]) <= 0:
self.sgd(X_mat[i], y_mat[i])
else:
M -= 1
if M == 0:
print('self.W is \n {0}'.format(self.W))
break
return self.W
def classify(self, testDataSet):
X_parameters, Y_parameters = testDataSet[:,:-1],testDataSet[:,-1]
# X_parameters = norm(X_parameters)
X_mat = np.mat(X_parameters) # size: n * m (m = 6 now, has X_0)
y_mat = np.mat(Y_parameters).T # size: n * 1
n, m = X_mat.shape
M = len(X_mat) # wrong classification number
for i in range(len(X_mat)):
x = X_mat[i]
if np.dot(self.W.T,x.T) <= 0 and y_mat[i] == -1:
M -= 1
elif np.dot(self.W.T,x.T) > 0 and y_mat[i] == 1 :
M -= 1
error = float(M) / len(X_mat)
print('error rate is {0:.4f}'.format(error))
return error
class Perceptron_dual:
def __init__(self, alpha, b, ita, eps = 1e-8):
self.alpha = alpha
self.b = b
self.ita = ita
self.eps = eps
def gram(self,X):
return np.dot(X,X.T)
def train(self, trainDataSet):
X_parameters, Y_parameters = trainDataSet[:,1:-1],trainDataSet[:,-1]
# X_parameters = norm(X_parameters)
X_mat = np.mat(X_parameters) # size: n * m (m = 2 now,not has X_0)
y_mat = np.mat(Y_parameters).T # size: n * 1
# Y_parameters 1 * n
n, m = X_mat.shape
G = self.gram(X_mat)
while True:
M = len(X_mat) # wrong classification number
for j in range(len(X_mat)):
if y_mat[j] * (np.sum(self.alpha * Y_parameters * G[j].T) + self.b) <= 0:
self.alpha[j] += self.ita
self.b += self.ita * y_mat[j]
else:
M -= 1
# print M
if M == 0:
print('self.alpha is \n {0}\nself.b is \n {1}'.format(self.alpha,self.b))
break
return self.alpha, self.b
def main():
trainDataSet, testDataSet = loadData()
# configure steplength and iterations
alpha = 1
perceptronTrain = Perceptron(np.zeros((trainDataSet.shape[1] - 1,1)),alpha)
W = perceptronTrain.train(trainDataSet)
perceptronTrain.classify(testDataSet)
perceptronDualTrain = Perceptron_dual(np.zeros(trainDataSet.shape[1] - 1), 0, alpha)
W = perceptronDualTrain.train(trainDataSet)
if __name__ == '__main__':
main()
参考文献
[1] 统计学习方法 李航
[2] 感知机学习算法 python实现：http://www.cnblogs.com/hanahimi/p/4693289.html
因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info