《统计学习方法》——算法实现

一、感知机学习算法

1.原始形式

给定一个训练数据集：T={(x1,y1),(x2,y2),...,(xN,yN)}T=\lbrace(x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbraceT={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in \chi =R_n$，yi∈Υ={+1,−1}y_i\in\Upsilon=\lbrace+1,-1\rbraceyi​∈Υ={+1,−1}，求参数$w$,，$b$，使其为以下损失函数极小化问题的解:
$$\underset{w,b}{\min }-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)\text{\hspace{1em}(1)}$$
其中M为误分类点的集合。
感知机学习算法的优化方法是随机梯度下降法。首先，任意选取一个超平面$w_0$，$b_0$，然后用梯度下降法不断地极小化目标函数$(1)$。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
假设误分类点集合M是固定的，那么损失函数$L(w,b)$的梯度由
$${\nabla }_{w}L(w,b)=-\sum _{x_i\in M}{y}_i{x}_i\text{\hspace{1em}(2)}$$ $${\nabla }_{b}L(w,b)=-\sum _{x_i\in M}{y}_i\text{\hspace{1em}(3)}$$
给出。
随机选取一个误分类点$(x_i,y_i)$，对$w$,$b$进行更新：
$$w\leftarrow w+\eta y_i{x}_i$$ $$b\leftarrow b+\eta y_i$$式中$\eta (0<\eta \le 1)$是步长，在统计学习中又称为学习率。这样，通过迭代可以期待损失函数$L(w,b)$不断减小，直到为0.综上所述，得到如下算法：

输入： 训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}T=\lbrace(x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbraceT={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in \chi =R_n$，yi∈Υ={+1,−1}y_i\in\Upsilon=\lbrace+1,-1\rbraceyi​∈Υ={+1,−1}，$i=1,2,...,N$；学习率$\eta (0<\eta \le 1)$；
输出：$w,b$，感知机模型$f(x)=sign(w\cdot x+b)$。
(1) 选取初值$w_0,b_0$。
(2) 在训练集中选取数据$(x_i,y_i)$
(3) 如果$y_i(w\cdot x_i+b)\le 0$，$$w\leftarrow w+\eta y_i{x}_i$$ $$b\leftarrow b+\eta y_i$$
(4) 转至 (2)，直至训练集中没有误分类点。

训练数据集

首先我们要选择训练数据集，数据集要是线性可分的（当然也可以使用线性不可分数据进行测试）。为了方便算法调试，我使用了书中最简单的三个点的例子。三个实例点分别为$x_1=(3,3{)}^T$，$x_2=(4,3{)}^T$，$x_3=(1,1{)}^T$，$x_1，x_2$是正实例点，$x_3$是负实例点。
数据信息也可以随机生成一些样本点，并手动给予类别。

读取数据

要保证程序的通用性，数据最好可以从文件中读取，便于修改和测试。这里采用的是从excel中读取，包括数据点信息和类别信息。
首先，新建两个excel文件data.xlsx和label.xlsx，分别存放数据点和类别标签，示例如下两图所示：


代码如下，采用pandas读取数据，读入到numpy数组中：

import pandas as pd

data = pd.read_excel('data.xlsx')  # 读取点数据
label = pd.read_excel('label.xlsx')  # 读取分类标签

# 将两者读取到numpy数组当中，可进行相应数值操作
x = data.values
y = label.values

可视化

可以对这三个点进行可视化（matplotlib），由于二维或三维才能绘制，高维数据可以降维之后再进行可视化：

from matplotlib import pyplot as plt

# 可视化
plt.title('Data Visualization')  # 标题
plt.xlim((0, 5))  # 设置x坐标轴范围
plt.ylim((0, 5))  # 设置y坐标轴范围
map_color = {-1: 'r', 1: 'b'}  # 类别及其对应点颜色的映射
color = []
for dot in y:
    color += map_color[dot[0]]
plt.scatter(x[:, 0], x[:, 1], c=color)
plt.show()

感知机学习

根据之前的算法，可以编写实现代码如下，其中需要注意的内容也在注释中。这里我只采用了顺序取点的方法，实际上应该用随机数选取点的方法更好：

# 感知机学习
w = np.zeros(x[0].shape)
b = 0
yetta = 1  # 学习率
steps = 0  # 记录全局步数
remain_list = [i for i in range(len(x))]
while len(remain_list) is not 0:  # 没有完全正确分类，则继续计算
    remain_list = [i for i in range(len(x))]  # 未能正确分类的点索引，一开始是所有点，分类正确则被移除
    for item in [i for i in range(len(x))]:  # 这里随机选取点也可，列表为空就结束选择
        if y[item] * (np.dot(x[item], w.T) + b) <= 0:  # 未能正确分类
            steps += 1
            w = w + y[item] * x[item]  # 更新w和b
            b = b + y[item]
            print("Step", steps, ": ", "(", x[item][0], ",", x[item][1], ")", "w = (", w[0], ",", w[1], ")'",
                  "  b = ", b)  # 显示中间结果
        else:  # 正确分类
            remain_list.remove(item)  # 从列表中移除

结果展示

首先是中间过程，即随机梯度下降选择了哪几个点，以及更新后的 $w$ 和 $b$ 各是多少，示例如下：

Step 1 :  ( 3 , 3 ) w = ( 3.0 , 3.0 )'   b =  [1]
Step 2 :  ( 1 , 1 ) w = ( 2.0 , 2.0 )'   b =  [0]
Step 3 :  ( 1 , 1 ) w = ( 1.0 , 1.0 )'   b =  [-1]
Step 4 :  ( 1 , 1 ) w = ( 0.0 , 0.0 )'   b =  [-2]
Step 5 :  ( 3 , 3 ) w = ( 3.0 , 3.0 )'   b =  [-1]
Step 6 :  ( 1 , 1 ) w = ( 2.0 , 2.0 )'   b =  [-2]
Step 7 :  ( 1 , 1 ) w = ( 1.0 , 1.0 )'   b =  [-3]

最后是感知机分类结果图的绘制，其中红色直线就是最终在二维平面上的结果$x_0+x_1-3=0$，如果是随机选取训练点的话，结果可能是不同的，分类正确即可：

对于一个新的点$(4,2)$，可以很直观地看出其应该是蓝色一类（正例）。用上面训练好的分类器进行验证：$4+2-3>0$，结果为正例，分类正确。
其他数据点的学习结果：

不足之处

• 代码有很多不足的地方，比如无法自由调节维度，根据二维进行的可视化，高维还需修改代码。
• 不是随机选取点，将问题进行了简化。
• 代码繁多不够简洁巧妙。
• 没有采用函数模块的方式编写，灵活性差。
• 可以采用tensorflow等机器学习库等进行编写，练习构建计算图。