2023年国赛数学建模思路 - 案例：感知机原理剖析及实现

# 0 赛题思路

赛题出来以后第一时间在CSDN分享

https://blog.csdn.net/dc_sinor?type=blog

1 感知机的直观理解

感知机应该属于机器学习算法中最简单的一种算法其原理可以看下图

比如说我们有一个坐标轴图中的黑色线横的为x1轴竖的x2轴。图中的每一个点都是由x1x2决定的。如果我们将这张图应用在判断零件是否合格上x1表示零件长度x2表示零件质量坐标轴表示零件的均值长度和均值重量并且蓝色的为合格产品黄色为劣质产品需要剔除。那么很显然如果零件的长度和重量都大于均值说明这个零件是合格的。也就是在第一象限的所有蓝色点。反之如果两项都小于均值就是劣质的比如在第三象限的黄色点。

在预测上很简单拿到一个新的零件我们测出它的长度x1质量x2如果两项都大于均值说明零件合格。这就是我们人的人工智能。

那么程序怎么知道长度重量都大于均值的零件就是合格的呢
或者说

它是怎么学会这个规则的呢
程序拿到手的是当前图里所有点的信息以及标签也就是说它知道所有样本x的坐标为x1 x2同时它属于蓝色或黄色。对于目前手里的这些点要是能找到一条直线把它们分开就好了这样我拿到一个新的零件知道了它的质量和重量我就可以判断它在线的哪一侧就可以知道它可能属于好的或坏的零件了。例如图里的黄、蓝、粉三条线都可以完美地把当前的两种情况划分开。甚至x1坐标轴或x2坐标轴都能成为一个划分直线这两个直线均能把所有点正确地分开。

读者也看到了对于图中的两堆点我们有无数条直线可以将其划分开事实上我们不光要能划分当前的点当新来的点进来是也要能很好地将其划分所以哪条线最好呢

怎样一条直线属于最佳的划分直线实际上感知机无法找到一条最佳的直线它找到的可能是图中所有画出来的线只要能把所有的点都分开就好了。

得出结论
如果一条直线能够不分错一个点那就是一条好的直线
进一步来说

如果我们把所有分错的点和直线的距离求和让这段求和的举例最小最好是0这样就表示没有分错的点了这条直线就是我们要找的。

2 感知机的数学角度

首先我们确定一下终极目标甭管找最佳划分直线啥中间乱七八糟的步骤反正最后生成一个函数f(x)当我们把新的一个数据x扔进函数以后它会预测告诉我这是蓝的还是黄的多简单啊。所以我们不要去考虑中间过程先把结果定了。

瞧f(x)不是出来了嘛sign是啥wx+b是啥别着急我们再看一下sigin函数是什么。

sign好像很简单当x大于等于0sign输出1否则输出-1。那么往前递归一下wx+b如果大于等于0f(x)就等于1反之f(x)等于-1。

那么wx+b是啥
它就是那条最优的直线。我们把这个公式放在二维情况下看二维中的直线是这样定义的y=ax+b。在二维中w就是ab还是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
在本文中使用零件作为例子上文使用了长度和重量x1x2来表示一个零件的属性所以一个二维平面就足够那么如果零件的品质和色泽也有关系呢那就得加一个x3表示色泽样本的属性就变成了x1x2x3变成三维了。wx+b并不是只用于二维情况在三维这种情况下仍然可以使用这个公式。所以wx+b与ax+b只是在二维上近似一致实际上是不同的东西。在三维中wx+b是啥我们想象屋子里一个角落有蓝点一个角落有黄点还用一条直线的话显然是不够的需要一个平面所以在三维中wx+b是一个平面至于为什么后文会详细说明。四维呢emmm…好像没法描述是个什么东西可以把四维空间分开但是对于四维来说应该会存在一个东西像一把刀一样把四维空间切成两半。能切成两半应该是一个对于四维来说是个平面的东西就像对于三维来说切割它的是一个二维的平面二维来说是一个一维的平面。总之四维中wx+b可以表示为一个相对于四维来说是个平面的东西然后把四维空间一切为二我们给它取名叫超平面。由此引申在高维空间中wx+b是一个划分超平面这也就是它正式的名字。

正式来说
wx+b是一个n维空间中的超平面S其中w是超平面的法向量b是超平面的截距这个超平面将特征空间划分成两部分位于两部分的点分别被分为正负两类所以超平面S称为分离超平面。

细节

w是超平面的法向量对于一个平面来说w就是这么定义的是数学知识可以谷歌补习一下

b是超平面的截距可以按照二维中的ax+b理解

特征空间也就是整个n维空间样本的每个属性都叫一个特征特征空间的意思是在这个空间中可以找到样本所有的属性组合

我们从最初的要求有个f(x)引申到能只输出1和-1的sign(x)再到现在的wx+b看起来越来越简单了只要能找到最合适的wx+b就能完成感知机的搭建了。前文说过让误分类的点距离和最大化来找这个超平面首先我们要放出单独计算一个点与超平面之间距离的公式这样才能将所有的点的距离公式求出来对不

先看wx+b在二维空间中我们可以认为它是一条直线同时因为做过转换整张图旋转后wx+b是x轴那么所有点到x轴的距离其实就是wx+b的值对不当然了考虑到x轴下方的点得加上绝对值->|wx+b|求所有误分类点的距离和也就是求|wx+b|的总和让它最小化。很简单啊把w和b等比例缩小就好啦比如说w改为0.5wb改为0.5b线还是那条线但是值缩小两倍啦你还不满意我可以接着缩缩到0去所以啊我们要加点约束让整个式子除以w的模长。啥意思就是w不管怎么样要除以它的单位长度。如果我w和b等比例缩小那||w||也会等比例缩小值一动不动很稳。没有除以模长之前|wx+b|叫函数间隔除模长之后叫几何间隔几何间隔可以认为是物理意义上的实际长度管你怎么放大缩小你物理距离就那样不可能改个数就变。在机器学习中求距离时通常是使用几何间隔的否则无法求出解。

对于误分类的数据例如实际应该属于蓝色的点线的右侧y>0但实际上预测出来是在左侧wx+b<0)那就是分错了结果是负这时候再加个符号结果就是正了再除以w的模长就是单个误分类的点到超平面的举例。举例总和就是所有误分类的点相加。

上图最后说不考虑除以模长就变成了函数间隔为什么可以这么做呢不考虑wb等比例缩小这件事了吗上文说的是错的吗

有一种解释是这样说的感知机是误分类驱动的算法它的终极目标是没有误分类的点如果没有误分类的点总和距离就变成了0w和b值怎样都没用。所以几何间隔和函数间隔在感知机的应用上没有差别为了计算简单使用函数间隔。

以上是损失函数的正式定义在求得划分超平面的终极目标就是让损失函数最小化如果是0的话就相当完美了。

感知机使用梯度下降方法求得w和b的最优解从而得到划分超平面wx+b关于梯度下降及其中的步长受篇幅所限可以自行谷歌。

3 代码实现

#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)的返回值为mn -> 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 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 = test(testData, testLabel, w, b)
    #获取当前时间作为结束时间
    end = time.time()
    #显示正确率
    print('accuracy rate is:', accruRate)
    #显示用时时长
    print('time span:', end - start)

4 建模资料

资料分享: 最强建模资料