感知机 perceptron
感知机是一种线性模型
是神经网络，支持向量机等的基础
1.感知机模型
f(x) = sign(wx + b)
w是权重向量weight，b是偏置向量bias
sign(x) = 1 (x>=0)
sign(x) = -1 (x < 0)
wx + b 对应特征空间中的一个超平面S
w 是超平面的法向量，b 是截距
2.学习策略
只能用于线性可分数据
损失函数 - 误分类点到超平面的距离之和
算距离时，选择几何距离，不能用函数距离
几何距离：|wx + b| / ||w||
函数距离：|wx + b|
若使用函数距离，模型在训练时，会等比例缩小 w b 来减小损失，不可取
对于误分类的数据
-yi * (w * xi + b) > 0
即 -yi * (w * xi + b) / ||w|| > 0
3.原始形式
用梯度下降法极小化目标函数
L(w, b) = - ∑ [yi * (wxi + b)]
对w求偏导 - ∑ yi * xi
对b求偏导 - ∑ yi
算法步骤
1.选取初始值w0，b0
2.在训练集中选取数据 (xi, yi)
3.若 yi * (w * xi + b) < 0
w = w - (- ? * yi * i )
b = b - ( - ? * yi )
4.转到 2，直至无误分类点
4.对偶形式
若 w，b 起始为0，假设修改 n 次，对于样本点 (xi, yi) 而言
w 的增量为 ai * yi * xi ， 其中 ai = ni * ? ， n是样本误分类次数
即最终结果
w = ∑ ai * yi * xi
将 w 带入原始形式的模型
f(x) = sign(∑ (ai* xi* yi * x) + b )
a = (a1, a2, a3, … , an)T
算法步骤
1.a 和 b 必须初始为 0 （开始无误分类点 -> n = 0 -> a = 0)
2.在训练集中选取 (xi, yi)
3.若 yi * ( ∑ (aj * xj * yj) * xi + b ) < 0
ai = ai + ? 即表示 n += 1 （误分类次数加一）
b = b + ? * yi
4.转至2，直至无误分类点
对于第三步的 aj * xj * yj * xi
其中 yj 取值 1/-1 ， aj 是简单的数值，但 xj * xi 是矩阵乘法，计算时间较长
可将训练集中的实例间的内积先计算出来并以矩阵形式储存，之后用到时直接查表
预处理一个 xi * xj 的矩阵Gram
5.感知机算法收敛性证明
证明：感知机的原始形式在线性可分数据上收敛
将 b 放入 w 中，并给x 向量补上 1 ，以方便运算
Eg：
[w1, w2, w3, b] * [x1, x2, x3, 1]T
6.代码实现（对偶模式待补）
此处完成对手写体数字的分类
大于等于5的数字分类为 1
小于等于五的数字分类为 -1
训练集包含 60000 个数据
测试集包含 10000 个数据
以像素点的形式给出
code
'''
-------------------
模型
perceptron
-------------------
数据集
训练集数量 60000
测试集数量 10000
-------------------
运行结果
iter: 100 60 50
正确率： 0.76 0.80 0.78
运行时常：149.77s 95.38s 81.62s
-------------------
'''
import numpy as np
import time
#读取数据
def loadData(fileName):
'''
加载数据集Mnist
:param filename: 要加载的数据集路径
:return: list形式的数据集及标记
'''
print("Start to read data")
#存放数据和标记的list
dataArr = []
labelArr = []
#打开文件
fr = open(fileName, 'r')
#按行读取文件
for line in fr.readlines():
#对每一行的数据按','进行切割，返回字段列表
curLine = line.strip().split(',')
#Mnist的标记为0-9，感知集进行而分类，故将>=5分作1，<5分作-1
if int(curLine[0]) >= 5:
labelArr.append(1)
else:
labelArr.append(-1)
#存放数据，遍历curLine除第一个元素以外的元素，转成int类型，并全部加入dataArr
dataArr.append([int(num) for num in curLine[1:]])
return dataArr, labelArr
#训练模型
def perceptron(dataArr, labelArr, iter=50):
'''
训练模型perceptron
:param dataArr: 训练集数据（list）
:param labelArr: 训练集标记（list）
:param iter: 迭代次数
:return: 训练好的w和b
'''
print("Start to train")
#将数据转换成矩阵，每一个样本的向量在矩阵中横向排列
dataMat = np.mat(dataArr)
#将标签转换成矩阵，转置，变成纵向分布，方便后面读取
labelMat = np.mat(labelArr).T
#矩阵的大小
m, n = np.shape(dataMat)
#创建初始权重，设置为0，大小为n，创建初始偏置，设为0，创建初始步长
w = np.zeros((1, n))
b = 0
h = 0.0001
#进行iter次迭代
for k in range(iter):
for i in range(m):
xi = dataMat[i]
yi = labelMat[i]
#判断是否是误分类
if (-1 * yi * (w * xi.T + b)) >= 0:
#对于误分类点，进行梯度下降
w = w + h * yi * xi
b = b + h * yi
#显示训练进度
print("Round %d / %d traning" % (k, iter))
return w, b
#测试模型
def model_test(dataArr, labelArr, w, b):
'''
测试准确率
:param dataArr: 测试数据集
:param labelArr: 测试标签集
:param w: 训练好的权重
:param b: 训练好的偏置
:return: 准确率
'''
print("Start to test")
#将数据集和测试集转换成矩阵
dataMat = np.mat(dataArr)
labelMat = np.mat(labelArr).T
#获取测试集矩阵的大小
m, n = np.shape(dataMat)
#错误样本的总计
errorCnt = 0
#遍历所有样本
for i in range(m):
xi = dataMat[i]
yi = labelMat[i]
if (-1 * yi * (w * xi.T + b)) >= 0:
errorCnt += 1
accurRate = 1 - (errorCnt / m)
return accurRate
if __name__ == '__main__':
#获取当前时间，在结束后再次获取时间，相减可得运行时间
start = time.time()
#获取训练集，测试集
trainData, trainLabel = loadData('/Users/bigstone/downloads/code/Statistical/Mnist/mnist_train.csv')
testData, testLabel = loadData('/Users/bigstone/downloads/code/Statistical/Mnist/mnist_test.csv')
#训练模型，返回权重和偏置
w, b = perceptron(trainData, trainLabel, iter=50)
#进行测试，返回正确率
accurRate = model_test(testData, testLabel, w, b)
end = time.time()
print("Accuracy rata is:", accurRate)
print("Run time:", end - start)