感知机模型-鲸之声

前期知识准备

线性可分定义

给定一个数据集

$T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) \}$

其中， $x_i \in \chi=\mathrm{R}^n, y_i \in \mathcal{Y}=\{+1,-1\},i=1,2,\dots,N$ ，如果存在某个超平面(类似于我们初等数学学的线性方程，区别是用高维向量形式表示)

$\omega·x+b=0$

S能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 $y_i=+1$ 的实例 $i$ ，有 $\omega · x_i+b>0$ ；对所有 $y_i=-1$ 的实例 $i$ ，有 $\omega · x_i+b<0$ ，则称数据集 $T$ 为线性可分数据集(linearly separable data set)；否则，称数据集 $T$ 线性不可分。
常见范数(距离)介绍

样本之间的距离的计算，我们一般使用对于一般使用 $L_p$ 距离进行计算。当 $p=1$ 时候，称为曼哈顿距离(Manhattan distance)，当 $p=2$ 时候，称为欧氏距离(Euclidean distance)，当 $p=∞$ 时候，称为极大距离(infty distance), 表示各个坐标的距离最大值,另外也包含夹角余弦等方法。一般采用欧式距离较多，但是文本分类则倾向于使用余弦来计算相似度。

对于两个向量 $(x_i,x_j)$ ,一般使用 $L_p$ 距离进行计算。假设特征空间 $X$ 是n维实数向量空间 $R^n$ , 其中, $x_i,x_j \in X$ , $x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right)$ , $x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \ldots, x_{j}^{(n)}\right)$ x_i，x_j的 $L_p$ 距离定义为:

$L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}$

这里的 $p\geq1$ . 当 $p=2$ 时候，称为欧氏距离(Euclidean distance)：

$L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}}$

当 $p=1$ 时候，称为曼哈顿距离(Manhattan distance)：

$L_{1}\left(x_{i}, x_{j}\right)=\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$

当 $p=\infty$ 时候，称为极大距离(infty distance), 表示各个坐标的距离最大值：

$L_{p}\left(x_{i}, x_{j}\right)=\max _{l} n\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$

感知机模型介绍

感知机(Perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，通常取+1和-1值(这里取值和支持向量机类似，都是为了方便后续处理，当然你随便取任意两个值都没关系的捏)。感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性化分的分离超平面，为此导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单容易实现的优点，分为原始形式和对偶形式。

模型定义

假设输入空间(特征空间)是 $\chi \subseteq \mathrm{R}^n$ ，输出空间是 $\mathcal{Y} = \{+1,-1\}$ 。输入 $x \in \chi$ 表示实例的特征向量，对应于输入空间(特征空间)的点；输出 $y \in \mathcal{Y}$ 表示实例的类别。由输入空间到输出空间的如下函数：

$f(x)=\mathrm{sign}(\omega·x+b)$

称为感知机，其中， $\omega$ 和 $b$ 为感知机模型的参数， $\omega \in \mathrm{R}^n$ 叫做权值(weight)或权值向量(weight vector)， $b \in R$ 叫做偏置(bias)， $\omega$ · $x$ 表示 $\omega$ 和 $x$ 的内积。sign是符号函数。

感知机学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能将训练集正实例点和负实例点完全正确分开得超平面，为了找到这样得超平面，即正确确定感知机模型参数 $\omega$ 和 $b$ ，需要确定一个学习策略，即定义(经验)损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数。但是由于这样的损失函数不是参数 $\omega$ 和 $b$ 的的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的，为此，首先写出输入空间 $\mathrm{R}^n$ 中任一点 $x_0$ 到超平面S的距离：

$\frac{1}{||\omega||}|\omega·x_0+b|$

其中， $||\omega||$ 是 $\omega$ 的 $L_2$ 范数。由于对误分类的数据 $(x_i,y_i)$ 来说，总是有

$-y_i(\omega·x_i+b)>0$

成立。

上式成立的原因解释：对于误分类点样本点，当 $\omega · x_i+b>0$ 时， $y_i=-1$ ；而当 $\omega · x_i+b<0$ 时， $y_i=+1$ (这就是先前所说的为了后续方便处理)

因此，假设超平面S的误分类点集合为 $M$ ，所有误分类点到超平面S的总距离为：

$-\frac{1}{||\omega||}\sum_{x_i\in M}y_i(\omega·x_i+b)$

不考虑 $\frac{1}{||\omega||}$ ，就是感知机学习的损失函数。

关于为什么不考虑分母的原因解释：

由于 $\omega·x+b=0$ 和 $a\omega·x+ab=0$ 表示的是同一个超平面，总能找到一个a来缩放原来的超平面使得关于 $a\omega$ 的二范数为1。支持向量机也运用了同样的思想；换一种说法是， $\omega$ 为超平面的法向量，只要和超平面垂直的向量都是法向量，我们可以限制法向量的长度为1

因此，感知机的损失函数定义为：

$L(\omega,b)=-\sum_{x_i\in M}y_i(\omega·x_i+b)$

可以通过梯度下降等方法来求 $\omega$ 和 $b$

(算法)感知机学习算法的原始形式

**输入：**训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) \}$ ，其中 $x_i \in \chi=\mathrm{R}^n$ , $y_i \in \mathcal{Y}=\{+1,-1\},i=1,2,\dots,N$ ;学习率 $\eta$ (0<$\eta \leq $1);

输出： $\omega,b$ ；感知机模型 $f(x)=\mathrm{sign}(\omega·x+b)$

选取初值 $\omega_0,b_0$ ；
在训练集中选取数据 $(x_i,y_i)$
如果 $y_i(\omega·x_i+b) \leq 0$
\omega \leftarrow \omega+\eta y_i x_i \\ b \leftarrow b+\eta y_i
转至第2步，直到训练集中没有误分类点

(算法)感知机学习算法的对偶形式

**输入：**训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) \}$ ，其中 $x_i \in \chi=\mathrm{R}^n$ , $y_i \in \mathcal{Y}=\{+1,-1\},i=1,2,\dots,N$ ;学习率 $\eta$ (0<$\eta \leq $1);

输出： $\alpha,b$ ；感知机模型 $f(x)=\mathrm{sign}(\sum_{j=1}^{N}\alpha_jy_jx_j·x+b)$ ，其中 $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_N)^T$

$\alpha \leftarrow 0,b \leftarrow 0$ ;
在训练集中选取数据 $(x_i,y_i)$
如果 $y_i(\sum_{j=1}^{N}\alpha_jy_jx_j·x_i+b)\leq0$

$\alpha \leftarrow \alpha_i + \eta$
$b \leftarrow b + \eta y_i$
转至第2步直到没有误分类数据

代码实战

通过面向对象建立感知机模型

import numpy as np  #传入的数据要求列是变量，行是观测，假设n个观测，p个变量
class PerceptionMethod(object):  # 定义 感知机学习 类
    def __init__(self, X, Y, eta):  # 类中参数是 X,Y（X,Y)均为numpy数组,eta,eta是学习率
        if X.shape[0] != Y.shape[0]:  # 要求X,Y中的行数一样，(n相同)
            raise ValueError('Error,X and Y must be same when axis=0 ')
        else:  # 在类中储存参数
            self.X = X
            self.Y = Y
            self.eta = eta

    def ini_Per(self):  # 感知机的原始形式
        weight = np.zeros(self.X.shape[1])  # 初始化weight,b（weight是p维的向量）
        b = 0
        number = 0  # 记录训练次数
        mistake = True  # mistake是变量用来说明分类是否有错误
        while mistake is True:  # 当有错时
            mistake = False  # 开始下一轮纠错前需要将mistake变为true，一来判断这一轮是否有错误
            for index in range(self.X.shape[0]):  # index取值0~n-1(一共n个观测)
                if self.Y[index] * (weight @ self.X[index] + b) <= 0:  # 错误判断条件,@表示内积，*表示对应元素相乘
                    weight += self.eta * self.Y[index] * self.X[index]  # 进行更新weight，b
                    b += self.eta * self.Y[index]
                    number += 1
                    #print(weight, b)
                    mistake = True  # 此轮检查出错误，表明mistake为true，进行下列一轮
                    break  # 找出第一个错误后调出循环
                #假如说有(12345)其中2，4是误分类点，那么计算顺序是12/1234/12345就是说每更新一次，下一次都是从头开始。
        return weight, b  # 返回值
        
    #对偶形式
    def dual_Per(self):
        Gram = np.dot(self.X, self.X.T) #计算Gram矩阵
        alpha = np.zeros(self.X.shape[0]) #初始化a向量，学习率为1时，a_i代表X_i的更新次数
        b = 0
        mistake = True
        while mistake is True:
            mistake = False
            for index in range(self.X.shape[0]):
                if self.Y[index] * (alpha * self.Y @ Gram[index] + b) <= 0: #y_i*(求和a_j*x_j*y_j+b)
                #@表示对应元素相乘再相加（a,b中有一个是一维数组），*表示对应元素相乘，计算顺序从左往右
                    alpha[index] += self.eta
                    b += self.eta * self.Y[index]
                    #print(alpha, b)
                    mistake = True
                    break
        weight = self.Y * alpha @ self.X #w是p维向量，@是矩阵乘法，
        #(我也不清楚np里面的矩阵行向量与列向量的区别，反正乘再加就是@或者np.dot,只乘不加就是*)
        return weight, b

当然，如果用Sklearn机器学习包的话，更加的方便。以经典的鸢尾花数据集为例，只选取两个特征变量做二分类，最终代码和表现结果如下：

import sklearn
from sklearn.linear_model import Perceptron
from sklearn.datasets import load_iris
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
from Perception import PerceptionMethod

# 数据预处理
iris = load_iris()
df = pd.DataFrame(iris.data, columns = iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
data = np.array(df.iloc[:100, [0, 1, -1]])
x, y = data[:, :-1], data[:, -1] 
y = np.array([1 if i == 1 else -1 for i in y])

#采用PerceptionMethod模型训练
clf_1 = PerceptionMethod(x,y,0.01)
clf_1_coef_,clf_1_intercept_= clf_1.ini_Per()

# 输出参数w, b
print('w_1 = ' + str(clf_1_coef_) + ', b_1 = ' + str(clf_1_intercept_))

# 采用sklearn库模型训练
clf = Perceptron(fit_intercept = True, max_iter = 1000, tol = None, shuffle = True)
clf.fit(x, y)

# 输出参数w, b
print('w_2 = ' + str(clf.coef_) + ', b_2 = ' + str(clf.intercept_))

# 画出图形
plt.figure(figsize = (10, 10)) #设置画布大小
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.title('鸢尾花线性数据示例')

# 画出散点图, iris-setosa:山鸢尾, iris-versicolour: 杂色鸢尾
plt.scatter(data[:50, 0], data[:50, 1], c = 'b', label = 'iris-setosa')
plt.scatter(data[50:100, 0], data[50:100, 1], c = 'orange', label = 'iris-versicolor')

# 画出感知机的线
x_ = np.arange(4, 8)
y_1 = -(clf.coef_[0][0]*x_ + clf.intercept_) / clf.coef_[0][1]
y_2 = -(clf_1_coef_[0]*x_ + clf_1_intercept_) / clf_1_coef_[1]
plot1 = plt.plot(x_,y_1,'-',label = '基于sklearn感知机线')
plot2 = plt.plot(x_,y_2,':',label = '基于PerceptionMethod感知机线')

plt.legend((plot1[0],plot2[0]),('基于sklearn感知机线','基于PerceptionMethod感知机线'),loc = 'best',fontsize = 10) #图例
plt.grid(False) # 不显示网络
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.show()