统计学习方法-感知机+手写代码

前言

最近在看李航博士的《统计学习方法》在这里做一个小小的记录,写一下自己的理解 欢迎大家批评指正。

正文
感知机的直观理解
感知机应该属于机器学习算法中最简单的一种算法,其原理可以看下图:统计学习方法-感知机+手写代码
比如说我们有一个坐标轴(图中的黑色线),横的为x1轴,竖的x2轴。图中的每一个点都是由(x1,x2)决定的。如果我们将这张图应用在判断零件是否合格上,x1表示零件长度,x2表示零件质量,坐标轴表示零件的均值长度和均值重量,并且蓝色的为合格产品,黄色为劣质产品,需要剔除。那么很显然如果零件的长度和重量都大于均值,说明这个零件是合格的。也就是在第一象限的所有蓝色点。反之如果两项都小于均值,就是劣质的,比如在第三象限的黄色点。
但是我们怎样让计算机这道这个规则呢?
我们目前知道的数据集是当前图里面的所有点的信息以及标签,也就是所有的样本的额(x1,x2),对于上面的这些点,如果我们能够找到一条合理的直线将他们完美的分开就好了,这样我们拿来一个新的样本,知道了她的两个参数就能够判断它在线的那一侧了

我们能够看到,想要把图中的两个点分开,我们有很多条线可以做到,但是怎样找到最优的那一条分割线呢?
实际上,我们的感知机没法找到一条最佳的直线,它找到的可能就是图中画出来的左右的线,但是只要是所有的点都可以分开就可以了。
因此:如果一条直线能够不分错一个点,那就是一条好的直线。

下面我们来谈一下,怎样找这条直线呢?这条直线首先是一条能够有限次分错类的一条直线。因此,我们可以 计算所有分错的点和直线的距离求和,让这个距离达到最小就是我们所要求解的直线。
感知机涉及的数学公式
因为我们做到是二分类,所以分为一正一负最好了,那这时候我们设计一个+1与一个-1正好可以完美的分为两类。
于是我们得到了一个函数:统计学习方法-感知机+手写代码
这个sign函数的具体定义如下所示:
统计学习方法-感知机+手写代码
当自变量x不小于0的时候函数值为正1,当自变量的值小于0的时候函数值是-1.
那么,上面我们引入的wx+b是什么东西呢?
它就是那条最优的直线。我们把这个公式放在二维情况下看,二维中的直线是这样定义的:y=ax+b。在二维中,w就是a,b还是b。所以wx+b是一条直线(比如说本文最开始那张图中的蓝线)。如果新的点x在蓝线左侧,那么wx+b<0,再经过sign,最后f输出-1,如果在右侧,输出1。等等,好像有点说不通,把情况等价到二维平面中,y=ax+b,只要点在x轴上方,甭管点在线的左侧右侧,最后结果都是大于0啊,这个值得正负跟线有啥关系?emmm…其实wx+b和ax+b表现直线的形式一样,但是又稍有差别。我们把最前头的图逆时针旋转45度,蓝线是不是变成x轴了?哈哈这样是不是原先蓝线的右侧变成了x轴的上方了?其实感知机在计算wx+b这条线的时候,已经在暗地里进行了转换,使得用于划分的直线变成x轴,左右侧分别为x轴的上方和下方,也就成了正和负。
那么究竟wx+b与ax+b有什么不同呢?
在本文中使用零件作为例子,上文使用了长度和重量(x1,x2)来表示一个零件的属性,所以一个二维平面就足够,那么如果零件的品质和色泽也有关系呢?那就得加一个x3表示色泽,样本的属性就变成了(x1,x2,x3),变成三维了。wx+b并不是只用于二维情况,在三维这种情况下,仍然可以使用这个公式。所以wx+b与ax+b只是在二维上近似一致,实际上是不同的东西。在三维中wx+b是啥?我们想象屋子里一个角落有蓝点,一个角落有黄点,还用一条直线的话,显然是不够的,需要一个平面!所以在三维中,wx+b是一个平面!至于为什么,后文会详细说明。四维呢?emmm…好像没法描述是个什么东西可以把四维空间分开,但是对于四维来说,应该会存在一个东西像一把刀一样把四维空间切成两半。能切成两半,应该是一个对于四维来说是个平面的东西,就像对于三维来说切割它的是一个二维的平面,二维来说是一个一维的平面。总之四维中wx+b可以表示为一个相对于四维来说是个平面的东西,然后把四维空间一切为二,我们给它取名叫超平面。由此引申,在高维空间中,wx+b是一个划分超平面,这也就是它正式的名字。
综合来讲:wx+b对应的是n维空间中的超平面S,其中w是超平面的法向量,b是超平面的截距。这个超平面把空间划分为两个部分。位于两个部分的点就会被分为正负两类,所以超平面S也叫做分离超平面。

如何计算距离

我们从最初的要求有个f(x),引申到能只输出1和-1的sign(x),再到现在的wx+b,看起来越来越简单了,只要能找到最合适的wx+b,就能完成感知机的搭建了。前文说过,让误分类的点距离和最大化来找这个超平面,首先我们要放出单独计算一个点与超平面之间距离的公式,如下:hi欸统计学习方法-感知机+手写代码
在二维空间中,我们可以认为它是一条直线,但是因为做过转化,整图旋转后wx+b是x轴,所有点到x轴的距离其实就是wx+b的绝对值。那么我们求所有的误分类点的距离和,也就是求|wx+b|的总和,让它最小化。当我们进行数值比较的时候,用更小的数值更加方便计算,因此,我们需要将整体的数值缩小n倍,但是具体是多少呢?我们的经验告诉我们化为单位长度是最好比较的,因此我们可以除以|w|,于是便可以得到上面的形式。
损失函数的定义
统计学习方法-感知机+手写代码
对于误分类的数据,例如实际应该属于正类的点,但是实际上预测成了负类。对于分错的类别,我们这时候应该加上一个负号,结果就是正的了。
,|wx+b|叫函数间隔,除模长之后叫几何间隔,几何间隔可以认为是物理意义上的实际长度,管你怎么放大缩小,你物理距离就那样,不可能改个数就变。在机器学习中求距离时,通常是使用几何间隔的,否则无法求出解。
但是上面说不考虑除以模长,就变成了函数间隔。为什么可以这么做呢?
下面给出了一种解释:感知机是误分类驱动的算法,它的终极目标是没有误分类的点,如果没有误分类的点,总和距离就变成了0,w和b值怎样都没用。所以几何间隔和函数间隔在感知机的应用上没有差别,为了计算简单,使用函数间隔。
统计学习方法-感知机+手写代码
上面就是损失函数的正式定义,在求得划分超平面得最终目标就是让损失函数最小化,如果是0得话当然是最好。
统计学习方法-感知机+手写代码
感知机使用梯度下降方法求得w和b的最优解,从而得到划分超平面wx+b。
(梯度下降算法后期会整理)
下面得例子是李航博士《统计学习方法》中得例题:
统计学习方法-感知机+手写代码

统计学习方法-感知机+手写代码
统计学习方法-感知机+手写代码

感知机学习的对偶形式

具体过程如下图:
统计学习方法-感知机+手写代码

实现代码:

#coding=utf-8
#Author:Dodo
#Date:2018-11-15
#Email:lvtengchao@pku.edu.cn

'''
数据集:Mnist
训练集数量:60000
测试集数量:10000
------------------------------
运行结果:
正确率:81.72%(二分类)
运行时长:78.6s
'''

import numpy as np
import time

def loadData(fileName):
    '''
    加载Mnist数据集
    :param fileName:要加载的数据集路径
    :return: list形式的数据集及标记
    '''
    print('start to read data')
    # 存放数据及标记的list
    dataArr = []; labelArr = []
    # 打开文件
    fr = open(fileName, 'r')
    # 将文件按行读取
    for line in fr.readlines():
        # 对每一行数据按切割福','进行切割,返回字段列表
        curLine = line.strip().split(',')

        # Mnsit有0-9是个标记,由于是二分类任务,所以将>=5的作为1,<5为-1
        if int(curLine[0]) >= 5:
            labelArr.append(1)
        else:
            labelArr.append(-1)
        #存放标记
        #[int(num) for num in curLine[1:]] -> 遍历每一行中除了以第一哥元素(标记)外将所有元素转换成int类型
        #[int(num)/255 for num in curLine[1:]] -> 将所有数据除255归一化(非必须步骤,可以不归一化)
        dataArr.append([int(num)/255 for num in curLine[1:]])

    #返回data和label
    return dataArr, labelArr

def perceptron(dataArr, labelArr, iter=50):
    '''
    感知器训练过程
    :param dataArr:训练集的数据 (list)
    :param labelArr: 训练集的标签(list)
    :param iter: 迭代次数,默认50
    :return: 训练好的w和b
    '''
    print('start to trans')
    #将数据转换成矩阵形式(在机器学习中因为通常都是向量的运算,转换称矩阵形式方便运算)
    #转换后的数据中每一个样本的向量都是横向的
    dataMat = np.mat(dataArr)
    #将标签转换成矩阵,之后转置(.T为转置)。
    #转置是因为在运算中需要单独取label中的某一个元素,如果是1xN的矩阵的话,无法用label[i]的方式读取
    #对于只有1xN的label可以不转换成矩阵,直接label[i]即可,这里转换是为了格式上的统一
    labelMat = np.mat(labelArr).T
    #获取数据矩阵的大小,为m*n
    m, n = np.shape(dataMat)
    #创建初始权重w,初始值全为0。
    #np.shape(dataMat)的返回值为m,n -> np.shape(dataMat)[1])的值即为n,与
    #样本长度保持一致
    w = np.zeros((1, np.shape(dataMat)[1]))
    #初始化偏置b为0
    b = 0
    #初始化步长,也就是梯度下降过程中的n,控制梯度下降速率
    h = 0.0001

    #进行iter次迭代计算
    for k in range(iter):
        #对于每一个样本进行梯度下降
        #李航书中在2.3.1开头部分使用的梯度下降,是全部样本都算一遍以后,统一
        #进行一次梯度下降
        #在2.3.1的后半部分可以看到(例如公式2.6 2.7),求和符号没有了,此时用
        #的是随机梯度下降,即计算一个样本就针对该样本进行一次梯度下降。
        #两者的差异各有千秋,但较为常用的是随机梯度下降。
        for i in range(m):
            #获取当前样本的向量
            xi = dataMat[i]
            #获取当前样本所对应的标签
            yi = labelMat[i]
            #判断是否是误分类样本
            #误分类样本特诊为: -yi(w*xi+b)>=0,详细可参考书中2.2.2小节
            #在书的公式中写的是>0,实际上如果=0,说明改点在超平面上,也是不正确的
            if -1 * yi * (w * xi.T + b) >= 0:
                #对于误分类样本,进行梯度下降,更新w和b
                w = w + h *  yi * xi
                b = b + h * yi
        #打印训练进度
        print('Round %d:%d training' % (k, iter))

    #返回训练完的w、b
    return w, b


def model_test(dataArr, labelArr, w, b):
    '''
    测试准确率
    :param dataArr:测试集
    :param labelArr: 测试集标签
    :param w: 训练获得的权重w
    :param b: 训练获得的偏置b
    :return: 正确率
    '''
    print('start to test')
    #将数据集转换为矩阵形式方便运算
    dataMat = np.mat(dataArr)
    #将label转换为矩阵并转置,详细信息参考上文perceptron中
    #对于这部分的解说
    labelMat = np.mat(labelArr).T

    #获取测试数据集矩阵的大小
    m, n = np.shape(dataMat)
    #错误样本数计数
    errorCnt = 0
    #遍历所有测试样本
    for i in range(m):
        #获得单个样本向量
        xi = dataMat[i]
        #获得该样本标记
        yi = labelMat[i]
        #获得运算结果
        result = -1 * yi * (w * xi.T + b)
        #如果-yi(w*xi+b)>=0,说明该样本被误分类,错误样本数加一
        if result >= 0: errorCnt += 1
    #正确率 = 1 - (样本分类错误数 / 样本总数)
    accruRate = 1 - (errorCnt / m)
    #返回正确率
    return accruRate

if __name__ == '__main__':

    #获取当前时间
    #在文末同样获取当前时间,两时间差即为程序运行时间
    start = time.time()

    #获取训练集及标签
    trainData, trainLabel = loadData('../Mnist/mnist_train.csv')
    #获取测试集及标签
    testData, testLabel = loadData('../Mnist/mnist_test.csv')

    #训练获得权重
    w, b = perceptron(trainData, trainLabel, iter = 30)
    #进行测试,获得正确率
    accruRate = model_test(testData, testLabel, w, b)

    #获取当前时间,作为结束时间
    end = time.time()
    #显示正确率
    print('accuracy rate is:', accruRate)
    #显示用时时长
    print('time span:', end - start)


本文参考链接:添加链接描述

上一篇:wx.onLocationChange


下一篇:微信小程序:蓝牙通讯,搜索、发送与接收