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

向右看齐 2022-06-10 09:09 187阅读 0赞

# 前言 #

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

感知机作为一个二分类模型，在1957年由Rosenblatt提出，是感知机是支持向量机SVM和神经网络的一个基础。目的是通过将一个实例（比如一个西瓜是否好坏）进行分类，输入的是实例特征向量，输出的是实例的类别。

紧记机器学习三要素：模型，策略，算法。

首先简要地说下感知机\\(f = sign\\left( \{\\sum\\limits\_\{j = 1\}^N \{w \\cdot x + b\} \} \\right)\\)，采用的策略是误分类点的总距离来作为损失函数，算法是随机梯度下降法。

# 算法理论 #

首先单层感知机要求在线性可分，如果存在一个超平面\\(w \\cdot x + b = 0\\)(在二维时可以看作一个直线，三维时看作一个平面)能够使所有\\(\{y\_i\} = + 1\\)时\\(w \\cdot x + b > 0\\)，所有\\(\{y\_i\} = - 1\\)时\\(w \\cdot x + b < 0\\)，此时可以找出一个超平面将数据集T分为正负样本，否则不可分，请移步别的模型，比如SVM。

现在给定数据集：\\(T = \\left\\\{ \{\\left( \{ \{x\_1\},\{y\_1\}\} \\right),\\left( \{ \{x\_2\},\{y\_2\}\} \\right),...\\left( \{ \{x\_N\},\{y\_N\}\} \\right)\} \\right\\\},x \\in X \\in \{R^n\},y \\in Y \\in \\left\\\{ \{ - 1,1\} \\right\\\}\\)

这里的任务是通过数据集来找到一组权重向量\\(w\\)来使得感知机能够准确地分类，在这里我们引入机器学习的假设空间的概念，感知机的假设空间是定义在特征空间中的所有线性分类模型，意思就是说需要从假设空间找到能够拟合给定数据集的线性分类模型（可能有多个线性分类模型可以拟合）。

其次我们需要寻找一个损失函数来进行学习，直观的想法是希望误分类的数目越小越好，但是这样的损失函数对于\\(w\\),\\(b\\)不是连续可导的函数，所以另一个直观的想法是找到一个误分类点到超平面的总距离作为目标函数。

之前提到，如果分类正确，\\(\{y\_i\} = + 1\\)时\\(w \\cdot x + b > 0\\)，所有\\(\{y\_i\} = - 1\\)时\\(w \\cdot x + b < 0\\)，所以相反的，误分类点可以把公式写为\\( - \{y\_i\}\\left( \{w \\cdot x + b\} \\right) > 0\\),结合点到超平面距离公式\\(\\frac\{1\}\{ \{\\left\\| w \\right\\|\}\}\\left| \{w \\cdot \{x\} + b\} \\right|\\)可以得到误分类点到超平面的总距离\\( - \\frac\{1\}\{ \{\\left\\| w \\right\\|\}\}\\sum\\limits\_\{ \{x\_i\} \\in M\} \{ \{y\_i\}\\left( \{w \\cdot \{x\_i\} + b\} \\right)\} \\)。

其次，不考虑\\(\\frac\{1\}\{ \{\\left\\| w \\right\\|\}\}\\)（因为这是一个常数，求导梯度时不影响），所以目标函数为：\\\[\\mathop \{\\min \}\\limits\_\{w,b\} L\\left( \{w,b\} \\right) = - \\sum\\limits\_\{ \{x\_i\} \\in M\}^\{\} \{ \{y\_i\}\\left( \{w \\cdot \{x\_i\} + b\} \\right)\} \\\]

在此我们极小化目标函数。

根据偏导为零可求出梯度为：

\\\[\\begin\{array\}\{l\}\{\\nabla \_w\}L\\left( \{w,b\} \\right) = - \\sum\\limits\_\{ \{x\_i\} \\in M\}^\{\} \{ \{y\_i\}\{x\_i\}\} \\\\\{\\nabla \_b\}L\\left( \{w,b\} \\right) = - \\sum\\limits\_\{ \{x\_i\} \\in M\}^\{\} \{ \{y\_i\}\} \\end\{array\}\\\]

最后采用随机梯度下降法(随机地选择一个误分类的点来进行梯度更新，而不是选择所有的误分类的点)。

其中w,b的更新为：\\\[\\begin\{array\}\{l\}  
w \\leftarrow w + \\eta \{y\_i\}\{x\_i\}\\\\  
b \\leftarrow b + \\eta \{y\_i\}  
\\end\{array\}\\\]

好了，有了理论知识，我们可以将其写出代码。（以下代码在python3的环境下测试运行通过）

# 代码实现 #

数据集来自书上例2.1的例子，此次代码是感知机的原始形式实现。

# --*-- coding:utf:8 --*--
    import numpy as np
    
    class Perceptron:  # 感知机
        def __init__(self, dataSet, labels):  # 初始化数据集和标签, initial dataset and label
            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([1, n])  #row vector
            bias = 0
            flag = False
            while flag != True:
                flag = True
                for i in range(m):  # 遍历样本 iterate samples
                    y = weights * np.mat(dataSet[i]).T + bias  # 以向量的形式计算
                    if (self.sign(y) * self.labels[i] < 0):  # 说明是误分类了  it means this is wrong misclassification data
                        weights += self.labels[i] * self.dataSet[i]  # 更新权重
                        bias += self.labels[i]  # 更新偏置
                        print("weights %s, bias %s" % (weights, bias))
                        flag = False
            return weights, bias
    
        def sign(self, y):  # 符号函数 sign function
            if (y > 0):
                return 1
            else:
                return -1
    
        @property
        def dataSet(self):
            return self._dataSet
    
        @property
        def labels(self):
            return self._labels

推荐两个显示器，一个显示代码，一个显示代码解释。

Line1 指定utf8编码。

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

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

Line9 训练函数

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

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

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

Line16 遍历所有样本。

LIne17 分类器的函数表示。

Line18 说明误分类了。

Line19~20 根据梯度下降对权重向量\\(w\\)和偏置\\(b\\)进行更新。

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

Line39~46 训练过程，可以得到最后的输出为：

weights [[3. 3.]], bias 1
    weights [[2. 2.]], bias 0
    weights [[1. 1.]], bias -1
    weights [[0. 0.]], bias -2
    weights [[3. 3.]], bias -1
    weights [[2. 2.]], bias -2
    weights [[1. 1.]], bias -3
    final weights:[[1. 1.]], bias:-3

跟p30表2.1的结果一致。

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

完整代码：[感知机完整代码下载][Link 1]

[https_github.com_FlameCharmander_MachineLearning]: https://github.com/FlameCharmander/MachineLearning
[Link 1]: https://github.com/FlameCharmander/MachineLearning/blob/master/perceptron/perceptron.py