感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出 为实例的类别，取+1和–1二值。感知机对应于输入空间（特征空间）中将实例划分为正 负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化， 求得感知机模型。感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的输入实例进行分类。感知机1957年由 Rosenblatt提出，是神经网络与支持向量机的基础。 本章首先介绍感知机模型；然后叙述感知机的学习策略，特别是损失函数；最后介绍 感知机学习算法，包括原始形式和对偶形式，并证明算法的收敛性。
2.1感知机模型
感知机是一种线性的、二类分类模型，可以将空间划分为正类和负类，是一种判别模型，输入为具体的实例，输出为实例的类别（+1，-1）。有原始形式和对偶形式两种。感知机是神经网络和支持向量机的基础。
感知机预测是利用学习到的模型对输入实例进行类别的划分。由输入空间到输出空间有如下函数：
感知机是一种线性分类模型，属于判别模型．感知机模型的假设空间是定义在特征空间中的所有线性分类模型（ linear classification model)或线性分类器(linear classifier)，
即函数集合{f|f(x)=w*x+b}.
感知机有如下几何解释:线性方程 w*x+b=0
对应于特征空间R”中的一个超平面S，其中w是超平面的法向量b是超平面的截距．这个超平面将特征空间划分为两个部分．位于两部分的点(特征向量）分别被分为正、负两类．因此，超平面S称为分离超平面（ separatitng hyperplane),
如图2.1所示
2.2感知机学习策略
数据集的线性可分性
感知机学习策略
假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面．为了找出这样的超平面，即确定感知机模型参数w,b，需要确定一个学习策略，即定义（经验损失函数并将损失函数极小化)。
损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数w,b的连续可导函数，不易优化.损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的.为此，首先写出输入空间R"中任一点x0到超平面S的距离:
显然，损失函数L(w,b)是非负的．如果没有误分类点，损失函数值是0．而且，误分类点越少，误分类点离超平面越近，损失函数值就越小．一个特定的样本点的损失函数:在误分类时是参数w,b的线性函数，在正确分类时是0.因此,给定训练数据集T，损失函数L(w,b)是w,b的连续可导函数。
感知机学习的策略是在假设空间中选取使损失函数式(2.4)最小的模型参数wb,即感知机模型.
2.3感知机学习算法
感知机学习问题转化为求解损失函数式（2.4）的最优化问题，最优化的方法是随机梯度下降法.本节叙述感知机学习的具体算法，包括原始形式和对偶形式，并证明在训练数据线性可分条件下感知机学习算法的收敛性。
感知机学习算法的原始形式
感知机学习算法是误分类驱动的，具体采用随机梯度下降法( stochasticgradient descent)．首先，任意选取一个超平面w0,b0，然后用梯度下降法不断地极小化目标函数(2.5).极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
import pandas as pd import numpy as np import matplotlib.pyplot as plt from sklearn.utils import shuffle # In[266]: # examole 2.1 # python版本 x = np.array([[3,3], [4,3], [1,1]]) y = [1, 1, -1] # In[306]: """ np.dot([2,2],[1,1]) 4 np.dot([2,2],[[1],[1]]) array([4]) """ w = [0 ,0] b = 0 yita = 1 # In[307]: #是否还存在误分类点 def isHasMisclassification(x, y, w, b): misclassification = False ct = 0 misclassification_index = 0 for i in range(0, len(y)): if y[i]*(np.dot(w, x[i]) + b) <= 0: ct += 1 misclassification_index = i if ct>0: misclassification = True return misclassification, misclassification_index # In[308]: # 更新系数w, b def update(x, y, w, b, i): w = w + y[i]*x[i] b = b + y[i] return w, b # In[309]: #更新迭代 import random def optimization(x, y, w, b): misclassification, misclassification_index = isHasMisclassification(x, y, w, b) while misclassification: print ("误分类的点：", misclassification_index) w, b = update(x, y, w, b, misclassification_index) print ("采用误分类点 {} 更新后的权重为:w是 {} , b是 {} ".format(misclassification_index, w, b)) misclassification, misclassification_index = isHasMisclassification(x, y, w, b) return w, b # In[310]: optimization(x, y, w, b) # In[311]: w, b = optimization(x, y, w, b) # In[312]: w,b
算法的收敛性
证明略
感知机学习算法的对偶形式
import pandas as pd import numpy as np import matplotlib.pyplot as plt from sklearn.utils import shuffle # In[266]: # examole 2.2 (对偶形式) # python版本 x = np.array([[3,3], [4,3], [1,1]]) x_transpose = x.T g = np.dot(x, x_transpose) y = [1, 1, -1] # In[306]: """ np.dot([2,2],[1,1]) 4 np.dot([2,2],[[1],[1]]) array([4]) """ alfa = np.array([0, 0, 0]) b = 0 yita = 1 # In[307]: #是否还存在误分类点 def isHasMisclassification(y, g, b): misclassification = False ct = 0 misclassification_index = 0 for i in range(0, len(y)): sum1 = 0 for j in range(0, len(y)): sum1 += (alfa[j]*y[j]*g[j][i] + b) if y[i]*sum1 <= 0: ct += 1 misclassification_index = i if ct > 0: misclassification = True return misclassification, misclassification_index # In[308]: # 更新系数alfa, b def update(y, alfa, yita, b, i): alfa[i] = alfa[i] + yita b = b + yita*y[i] return alfa, b # In[309]: #更新迭代 import random def optimization(y, alfa, b, yita): misclassification, misclassification_index = isHasMisclassification(y, g, b) while misclassification: print ("误分类的第{}点{}：".format(misclassification_index, x[misclassification_index])) alfa, b = update(y, alfa, yita, b, misclassification_index) print ("采用第{}误分类点 {} 更新后的权重为:alfa是 {} , b是 {} ".format(misclassification_index, x[misclassification_index], alfa, b)) misclassification, misclassification_index = isHasMisclassification(y, g, b) return alfa, b # In[310]: optimization(y, alfa, b, yita) # In[311]: alfa, b = optimization(y, alfa, b, yita) # In[312]: #w=sum(alfa_i*y_i*x_i) alfa_y = np.multiply(list(alfa),y) w = np.dot(alfa_y,x) b = np.dot(alfa, y) print("w是{},b是{}".format(w, b))
结果：
误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 0 1] , b是 -1 误分类的第1点[4 3]： 采用第1误分类点 [4 3] 更新后的权重为:alfa是 [0 1 1] , b是 0 误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 1 2] , b是 -1 误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 1 3] , b是 -2 误分类的第1点[4 3]： 采用第1误分类点 [4 3] 更新后的权重为:alfa是 [0 2 3] , b是 -1 误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 2 4] , b是 -2 误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 2 5] , b是 -3 误分类的第2点[1 1]： 采用第2误分类点 [1 1] 更新后的权重为:alfa是 [0 2 6] , b是 -1 w是[2 0],b是-4
代码部分参考：http://t.csdn.cn/MyEBk
