本文仅讨论两类的问题
参考文献：【感知机学习算法及其Python实现】，【基于sklearn的感知机python3】，【统计学习方法 第二版】
感知机（perception）是二类分类的线性模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型，感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的输入实例进行分类。
2. 感知机模型假设输入空间（特征空间）是
χ
⊆
R
n
chi subseteq R^n
χ⊆Rn，输出空间是
γ
=
{
+
1
,
−
1
}
gamma={+1,-1}
γ={+1,−1}。输入
x
∈
χ
x in chi
x∈χ表示实例的特征向量，对应于输入空间（特征空间）的点；输出
y
∈
γ
y in gamma
y∈γ表示实例的类别。由输入空间到输出空间的如下函数：
f
(
x
)
=
s
i
g
n
(
w
⋅
x
+
b
)
(1)
f(x)=sign(w·x+b) tag 1
f(x)=sign(w⋅x+b)(1)
称为感知机。其中，
w
w
w和
b
b
b为感知机模型参数，
w
∈
R
n
w in R^n
w∈Rn叫作权值或权值向量（weight vector），
b
∈
R
b in R
b∈R叫做偏置（bias），
w
⋅
x
w·x
w⋅x表示
w
w
w和
x
x
x的内积。
s
i
g
n
sign
sign是符号函数（若
x
≥
0
x geq 0
x≥0，取值为+1；若
x
<
0
x < 0
x<0，取值为-1）。
感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器（linear classifier），即函数集合
{
f
∣
f
(
x
)
=
w
⋅
x
+
b
}
{f|f(x)=w·x+b}
{f∣f(x)=w⋅x+b}。
感知机有如下几何解释：线性方程
w
⋅
x
+
b
=
0
(2)
w·x+b=0 tag 2
w⋅x+b=0(2)
对应于特征空间
R
n
R^n
Rn中的一个超平面
S
S
S，其中
w
w
w是超平面的法向量，
b
b
b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被划分为正、负两类。因此，超平面
S
S
S得名为**分离超平面（separating hyperplane），如图所示：
感知机学习，由训练数据集（实例的特征向量及类别）
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
}
(3)
T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} tag 3
T={(x1,y1),(x2,y2),...,(xN,yN)}(3)
其中，
x
i
∈
χ
=
R
n
x_i in chi=R^n
xi∈χ=Rn，
y
i
∈
γ
=
{
+
1
,
−
1
}
y_i in gamma={+1,-1}
yi∈γ={+1,−1}，
i
=
1
,
2
,
.
.
.
,
N
i=1,2,...,N
i=1,2,...,N，求得感知机模型
(
1
)
(1)
(1)，即求得模型参数
w
,
b
w,b
w,b。感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。
假设数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面，即确定感知机模型参数
w
,
b
w,b
w,b，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。
损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数
w
,
b
w,b
w,b的连续可导函数，不易优化。损失函数的另一选择是误分类点到超平面
S
S
S的总距离，这时感知机所采用的。为此，首先写出输入空间
R
n
R^n
Rn中任一点
x
0
x_0
x0到超平面
S
S
S的距离：
1
∣
∣
w
∣
∣
∣
w
⋅
x
0
+
b
∣
(4)
frac{1}{||w||}|w·x_0+b| tag 4
∣∣w∣∣1∣w⋅x0+b∣(4)
这里，
∣
∣
w
∣
∣
||w||
∣∣w∣∣是
w
w
w的
L
2
L_2
L2范数。
其次，对于误分类的数据
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)来说，
−
y
i
(
w
⋅
x
i
+
b
)
>
0
(5)
-y_i(w·x_i+b) > 0 tag 5
−yi(w⋅xi+b)>0(5)
成立。因为当
w
⋅
x
i
+
b
>
0
w·x_i+b > 0
w⋅xi+b>0时，
y
i
=
−
1
y_i=-1
yi=−1；而当
w
⋅
x
i
+
b
<
0
w·x_i+b < 0
w⋅xi+b<0时，
y
i
=
+
1
y_i=+1
yi=+1。因此，误分类点
x
i
x_i
xi到超平面
S
S
S的距离是
−
1
∣
∣
w
∣
∣
y
i
(
w
⋅
x
i
+
b
)
(6)
-frac{1}{||w||}y_i(w·x_i+b) tag 6
−∣∣w∣∣1yi(w⋅xi+b)(6)
这样，假设超平面
S
S
S的误分类点集合为
M
M
M，那么所有误分类点到超平面
S
S
S的总距离为
−
1
∣
∣
w
∣
∣
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
(7)
-frac{1}{||w||}sum_{x_i in M} y_i(w·x_i+b) tag 7
−∣∣w∣∣1xi∈M∑yi(w⋅xi+b)(7)
不考虑
1
∣
∣
w
∣
∣
frac{1}{||w||}
∣∣w∣∣1，就得到感知机学习的损失函数。
给定一个训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
}
T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}
T={(x1,y1),(x2,y2),...,(xN,yN)}
其中，
x
i
∈
χ
=
R
n
x_i in chi=R^n
xi∈χ=Rn，
y
i
∈
γ
=
{
+
1
,
−
1
}
y_i in gamma={+1,-1}
yi∈γ={+1,−1}，
i
=
1
,
2...
,
N
i=1,2...,N
i=1,2...,N。感知机
s
i
g
n
(
w
⋅
x
+
b
)
sign(w·x+b)
sign(w⋅x+b)学习的损失函数定义为：
L
(
w
,
b
)
=
−
∑
x
i
∈
M
y
i
(
w
⋅
x
i
+
b
)
(8)
L(w,b)=-sum_{x_i in M} y_i(w·x_i+b) tag 8
L(w,b)=−xi∈M∑yi(w⋅xi+b)(8)
其中
M
M
M为误分类点的集合。该函数为非负函数，且误分类点越少，函数值越小。
感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。首先，任意选取一个超平面
w
0
,
b
0
w_0,b_0
w0,b0，然后用梯度下降法不断地极小化目标函数。极小化过程不是一次使所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
假设误分类点集合
M
M
M是固定的，那么损失函数
L
(
w
,
b
)
L(w,b)
L(w,b)的梯度由：
∇
w
L
(
w
,
b
)
=
−
∑
x
i
∈
M
y
i
x
i
∇
b
L
(
w
,
b
)
=
−
∑
x
i
∈
M
y
i
(9)
nabla_wL(w,b)=-sum_{x_i in M} y_ix_i \ nabla_bL(w,b)=-sum_{x_i in M} y_i tag 9
∇wL(w,b)=−xi∈M∑yixi∇bL(w,b)=−xi∈M∑yi(9)
给出。
随机选取一个误分类点
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)，对
w
,
b
w,b
w,b进行更新：
w
←
w
+
η
y
i
x
i
(10)
w leftarrow w+eta y_ix_i tag {10}
w←w+ηyixi(10)
b
←
b
+
η
y
i
(11)
b leftarrow b+eta y_i tag {11}
b←b+ηyi(11)
式中
η
(
0
≤
η
≤
1
)
eta(0 leq eta leq 1)
η(0≤η≤1)是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数
L
(
w
,
b
)
L(w,b)
L(w,b)不断减小，直到为0.综上所述，得到如下算法：
算法：
输入：训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
}
T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}
T={(x1,y1),(x2,y2),...,(xN,yN)}，其中
x
i
∈
χ
=
R
n
,
y
i
∈
γ
=
{
+
1
,
−
1
}
,
i
=
1
,
2...
,
N
x_i in chi = R^n,y_i in gamma ={+1,-1},i=1,2...,N
xi∈χ=Rn,yi∈γ={+1,−1},i=1,2...,N；学习率
η
(
0
≤
η
≤
1
)
eta(0 leq eta leq 1)
η(0≤η≤1)；
输出：
w
,
b
w,b
w,b；感知机模型
f
(
x
)
=
s
i
g
n
(
w
⋅
x
+
b
)
f(x)=sign(w·x+b)
f(x)=sign(w⋅x+b)。
- 选取初值 w 0 , b 0 w_0,b_0 w0,b0；
- 在训练集中选取数据 ( x i , y i ) (x_i,y_i) (xi,yi)；
- 如果
y
i
(
w
⋅
x
i
+
b
)
≤
0
y_i(w·x_i+b) leq 0
yi(w⋅xi+b)≤0，
w ← w + η y i x i b ← b + η y i w leftarrow w+eta y_ix_i \ b leftarrow b+eta y_i w←w+ηyixib←b+ηyi - 转至 ( 2 ) (2) (2)，直至训练集中没有误分类点。
直观解释：
当一个实例点被误分类时，即位于分离超平面的错误一侧时，则调整
w
,
b
w,b
w,b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。
感知机算法的收敛性证明
Perceptron.py：
import operator
import os
# 感知机分类
def perceptronClassify(trainGroup,trainLabels):
global w, b
isFind = False # 是否找到最佳参数w和b的标志
numSamples = trainGroup.shape[0]
mLenth = trainGroup.shape[1]
w = [0]*mLenth
b = 0
while(not isFind):
for i in range(numSamples):
if cal(trainGroup[i],trainLabels[i]) <= 0:
print(w,b)
update(trainGroup[i],trainLabels[i])
break
elif i == numSamples-1:
print(w,b)
isFind = True
def cal(row,trainLabel):
global w, b
res = 0
for i in range(len(row)):
res += row[i] * w[i]
res += b
res *= trainLabel
return res
def update(row,trainLabel):
global w, b
for i in range(len(row)):
w[i] += trainLabel * row[i]
b += trainLabel
testPerceptron.py：
import numpy as np
# 构建数据集（数据集来源于统计学习方法第二版）
def createDataSet():
# create a matrix: each row as a sample
group = np.array([[3,3], [4,3], [1,1]])
labels = [1, 1, -1]
return group, labels
import Perceptron
g,l =createDataSet()
Perceptron.perceptronClassify(g,l)
5. 感知机学习算法的对偶形式
DualPerceptron.py：
import numpy as np
import operator
import os
# 感知机分类
def dualPerceptionClassify(trainGroup,trainLabels):
global a,b
isFind = False
numSamples = trainGroup.shape[0]
#mLenth = trainGroup.shape[1]
a = [0]*numSamples
b = 0
gMatrix = cal_gram(trainGroup)
while(not isFind):
for i in range(numSamples):
if cal(gMatrix,trainLabels,i) <= 0:
cal_wb(trainGroup,trainLabels)
update(i,trainLabels[i])
break
elif i == numSamples-1:
cal_wb(trainGroup,trainLabels)
isFind = True
# 计算Gram矩阵
def cal_gram(group):
mLenth = group.shape[0]
gMatrix = np.zeros((mLenth,mLenth))
for i in range(mLenth):
for j in range(mLenth):
gMatrix[i][j] = np.dot(group[i],group[j])
return gMatrix
def update(i,trainLabel):
global a,b
a[i] += 1
b += trainLabel
def cal(gMatrix,trainLabels,key):
global a,b
res = 0
for i in range(len(trainLabels)):
res += a[i]*trainLabels[i]*gMatrix[key][i]
res = (res + b)*trainLabels[key]
return res
# 计算w和b，并输出
def cal_wb(group,labels):
global a,b
w=[0]*(group.shape[1])
h = 0
for i in range(len(labels)):
h +=a[i]*labels[i]
w +=a[i]*labels[i]*group[i]
print (w,h)
testDualPerceptron.py：
import numpy as np
# 构建数据集
def createDataSet():
# create a matrix: each row as a sample
group = np.array([[3,3], [4,3], [1,1]])
labels = [1, 1, -1] # four samples and two classes
return group, labels
import DualPerceptron
g,l = createDataSet()
DualPerceptron.dualPerceptionClassify(g,l)
6. 基于digits数据集的感知机预测分析
导入数据：
from sklearn.datasets import load_digits digits=load_digits()
数据标准化处理：
from sklearn.preprocessing import StandardScaler scaler=StandardScaler() scaler.fit(digits.data) x_scaled=scaler.transform(digits.data)
将数据分别赋予X,y：
X=x_scaled y=digits.target
划分训练集、测试集：
from sklearn.model_selection import train_test_split X_train,X_test,y_train,y_test=train_test_split(X,y)
调用sklearn，使用感知机预测：
from sklearn.neural_network import MLPClassifier mlp=MLPClassifier(hidden_layer_sizes=(30,30,30),activation='logistic',max_iter=100) mlp.fit(X_train,y_train)
进行预测，并观察效果：
from sklearn.metrics import classification_report predicted=mlp.predict(X_test) print(classification_report(y_test, predicted))
precision recall f1-score support
0 0.93 0.93 0.93 40
1 0.93 0.83 0.88 47
2 0.88 0.88 0.88 43
3 0.76 0.85 0.80 48
4 0.98 0.98 0.98 43
5 0.82 0.67 0.74 46
6 0.95 0.97 0.96 37
7 0.86 0.92 0.89 52
8 0.77 0.74 0.76 50
9 0.71 0.77 0.74 44
accuracy 0.85 450
macro avg 0.86 0.86 0.85 450
weighted avg 0.85 0.85 0.85 450
