【统计学习方法】感知机Python 对偶形式实现

比眉伴天荒 2022-06-10 09:22 279阅读 0赞

代码可在Github上下载:([https://github.com/FlameCharmander/MachineLearning][https_github.com_FlameCharmander_MachineLearning])

# 前言 #

上篇博文[感知机的原始形式][Link 1]提到了感知机的原始形式，而这篇博文介绍的是感知机的对偶形式。

# 算法理论 #

感知机的原始形式提到的参数更新：

\\\[\\begin\{array\}\{l\}  
w \\leftarrow w + \\eta \{y\_i\}\{x\_i\}\\\\  
b \\leftarrow b + \\eta \{y\_i\}  
\\end\{array\}\\\]

从原始形式可以看出，\\(w\\)总共进行了n次更新，而每种样本\\(\{x\_i\}\\)进行了\\(\{n\_i\}\\)次更新，注意到\\(\\sum\\limits\_1^\{\\rm\{T\}\} \{ \{n\_i\}\} = 1\\),其中\\(T\\)（注意书上用的是\\(N\\)，我这里为了区分\\(n\\)做了符号修改）为样本\\(\\left( \{ \{x\_1\},\{x\_2\},\{x\_3\},...,\{x\_T\}\} \\right)\\)的数量。现在假设\\(w\\)初始为0，那么可以直接将\\(\{n\_i\}\\)次修改的量给计算出来写成\\(\{\\alpha \_i\}=\{n\_i\}\\eta\\)，所以\\(w\\)和\\(b\\)可被改写成：

\\\[\\begin\{array\}\{l\}  
w = \\sum\\limits\_\{i = 1\}^T \{ \{\\alpha \_i\}\{y\_i\}\{x\_i\}\} \\\\  
b = \\sum\\limits\_\{i = 1\}^T \{ \{\\alpha \_i\}\{y\_i\}\}  
\\end\{array\}\\\]

将\\(w\\)代入到感知机原始形式的模型中，那么在对偶形式中，感知机的模型是:  
\\\[f(x) = sign\\left( \{\\sum\\limits\_\{j = 1\}^N \{ \{\\alpha \_j\}\{y\_j\}\{x\_j\} \\cdot x + b\} \} \\right)\\\]

那么对偶形式的参数更新则变成求\\(\{ \{\\alpha \_i\}\}\\)和\\(b\\)（\\(b\\)还是跟原始形式一样），当我们找到一个误分类的样本\\(\{y\_i\}\\left( \{\\sum\\limits\_\{j = 1\}^N \{ \{\\alpha \_j\}\{y\_j\}\{x\_j\} \\cdot \{x\_i\} + b\} \} \\right) \\le 0\\)时：

\\\[\\begin\{array\}\{l\}  
\{\\alpha \_i\} \\leftarrow \\eta \\left( \{ \{n\_i\} + 1\} \\right) = \\eta \{n\_i\} + \\eta = \{\\alpha \_i\} + \\eta \\\\  
b \\leftarrow b + \\eta \{y\_i\}  
\\end\{array\}\\\]

# 算法实现 #

# --*-- coding:utf:8 --*--
    import numpy as np
    
    class PerceptronDual:  # 感知机
        def __init__(self, dataSet, labels):  # 初始化数据集和标签
            self.dataSet = np.array(dataSet)
            self.labels = np.array(labels).transpose()
    
        def train(self):
            m, n = np.shape(self.dataSet)  # m是行和n是列
            weights = np.zeros(n)
            bias = 0
            flag = False
            Gram = np.zeros((m, m))
            for i in range(m):  # 计算Gram矩阵 gram matrix
                for j in range(m):
                    Gram[i][j] = dataSet[i] * np.mat(dataSet[j]).transpose()
            print(Gram)
            a = np.zeros(m)
            while flag != True:
                flag = True
                for i in range(m):  # 遍历样本
                    sum = 0
                    for j in range(m):  # 求误分条件
                        sum += a[j] * self.labels[j] * Gram[j][i]
                    sum += bias
                    if (sum * self.labels[i] <= 0):
                        a[i] += 1
                        bias += self.labels[i]
                        flag = False
            for i in range(m):
                weights += a[i] * self.dataSet[i] * self.labels[i]
            return weights, bias
    
        def sign(self, y):  # 符号函数
            if (y > 0):
                return 1
            else:
                return -1

Line1 指定utf8编码。

Line2 导入numpy数值计算包。（推荐使用anaconda安装python）

Line4~7 写成一个类，并且指定init函数来初始化数据集和标签，当类被实例化时候将会调用这个函数。

Line9 训练函数

Line10 这个例子的数据集是一个三行两列的矩阵，所以通过numpy得到数据集的行数列数。

Line11~12 指定权重向量为一个n维的行向量，并指定一个偏置。

Line13 先设置个flag标记，这个标记是用来标记训练出来的参数\\(w\\)和\\(b\\) 是否含有误分类点（进入循环时先设置为True,遍历训练样本时一旦发现有误分类点就设置为False，需要继续训练）。

Line14~17 从对偶形式的模型\\(f = sign\\left( \{\\sum\\limits\_\{j = 1\}^N \{ \{\\alpha \_j\}\{y\_j\}\{x\_j\} \\cdot x + b\} \} \\right)\\)的公式中可以看出需要计算\\(\{\\sum\\limits\_\{j = 1\}^N \{ \{\\alpha \_j\}\{y\_j\}\{x\_j\} \\cdot x + b\} \}\\)，需要进行计算当前样本\\(x\\)和每个\\(\{x\_j\},j = 1,2,....,N\\)，，所以可以先创建一个Gram矩阵\\(G = \{\\left\[ \{ \{x\_i\} \\cdot \{x\_j\}\} \\right\]\_\{N \\times N\}\}\\)来存储\\(\{x\_i\} \\cdot \{x\_j\}\\)内积以便于计算。

Line19 初始化\\(\\alpha \\)

Line22 遍历样本

Line24~30 求\\(f = sign\\left( \{\\sum\\limits\_\{j = 1\}^N \{ \{\\alpha \_j\}\{y\_j\}\{x\_j\} \\cdot x + b\} \} \\right)\\)的结果值，如果小于0，就是误分类的点，需要进行更新。

Line31~32 参数更新。

Line35~39 符号函数，如果\\(w \\cdot x + b > 0\\)时\\(\{y\_i\} = + 1\\)，所有\\(w \\cdot x + b < 0\\)时\\(\{y\_i\} = - 1\\)。

Line49~56 训练过程。

我们提供了一份训练数据，详情请点击以下的Github网址，如果方便的话，麻烦点个赞啊。

完整代码：[感知机对偶完整代码][Link 2]

[https_github.com_FlameCharmander_MachineLearning]: https://github.com/FlameCharmander/MachineLearning
[Link 1]: https://blog.csdn.net/tudaodiaozhale/article/details/77193533
[Link 2]: https://github.com/FlameCharmander/MachineLearning/blob/master/perceptron/perceptron_dual.py