0 賽題思路

（賽題出來以后第一時間在群內(nèi)分享）

2023高教社杯全國大學(xué)生數(shù)學(xué)建模競賽

資料思路分享Q群：575833716

1 感知機(jī)的直觀理解

感知機(jī)應(yīng)該屬于機(jī)器學(xué)習(xí)算法中最簡單的一種算法，其原理可以看下圖：

比如說我們有一個坐標(biāo)軸（圖中的黑色線），橫的為x1軸，豎的x2軸。圖中的每一個點(diǎn)都是由（x1，x2）決定的。如果我們將這張圖應(yīng)用在判斷零件是否合格上，x1表示零件長度，x2表示零件質(zhì)量，坐標(biāo)軸表示零件的均值長度和均值重量，并且藍(lán)色的為合格產(chǎn)品，黃色為劣質(zhì)產(chǎn)品，需要剔除。那么很顯然如果零件的長度和重量都大于均值，說明這個零件是合格的。也就是在第一象限的所有藍(lán)色點(diǎn)。反之如果兩項(xiàng)都小于均值，就是劣質(zhì)的，比如在第三象限的黃色點(diǎn)。

在預(yù)測上很簡單，拿到一個新的零件，我們測出它的長度x1，質(zhì)量x2，如果兩項(xiàng)都大于均值，說明零件合格。這就是我們?nèi)说娜斯ぶ悄堋?/p>

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

它是怎么學(xué)會這個規(guī)則的呢？ 程序拿到手的是當(dāng)前圖里所有點(diǎn)的信息以及標(biāo)簽，也就是說它知道所有樣本x的坐標(biāo)為（x1， x2），同時它屬于藍(lán)色或黃色。對于目前手里的這些點(diǎn)，要是能找到一條直線把它們分開就好了，這樣我拿到一個新的零件，知道了它的質(zhì)量和重量，我就可以判斷它在線的哪一側(cè)，就可以知道它可能屬于好的或壞的零件了。例如圖里的黃、藍(lán)、粉三條線，都可以完美地把當(dāng)前的兩種情況劃分開。甚至x1坐標(biāo)軸或x2坐標(biāo)軸都能成為一個劃分直線（這兩個直線均能把所有點(diǎn)正確地分開）。

讀者也看到了，對于圖中的兩堆點(diǎn)，我們有無數(shù)條直線可以將其劃分開，事實(shí)上我們不光要能劃分當(dāng)前的點(diǎn)，當(dāng)新來的點(diǎn)進(jìn)來是，也要能很好地將其劃分，所以哪條線最好呢？

怎樣一條直線屬于最佳的劃分直線？實(shí)際上感知機(jī)無法找到一條最佳的直線，它找到的可能是圖中所有畫出來的線，只要能把所有的點(diǎn)都分開就好了。

得出結(jié)論： 如果一條直線能夠不分錯一個點(diǎn)，那就是一條好的直線 進(jìn)一步來說：

如果我們把所有分錯的點(diǎn)和直線的距離求和，讓這段求和的舉例最?。ㄗ詈檬?，這樣就表示沒有分錯的點(diǎn)了），這條直線就是我們要找的。

2 感知機(jī)的數(shù)學(xué)角度

首先我們確定一下終極目標(biāo)：甭管找最佳劃分直線啥中間亂七八糟的步驟，反正最后生成一個函數(shù)f(x)，當(dāng)我們把新的一個數(shù)據(jù)x扔進(jìn)函數(shù)以后，它會預(yù)測告訴我這是藍(lán)的還是黃的，多簡單啊。所以我們不要去考慮中間過程，先把結(jié)果定了。

瞧，f(x)不是出來了嘛，sign是啥？wx+b是啥？別著急，我們再看一下sigin函數(shù)是什么。

sign好像很簡單，當(dāng)x大于等于0，sign輸出1，否則輸出-1。那么往前遞歸一下，wx+b如果大于等于0，f(x)就等于1，反之f(x)等于-1。

那么wx+b是啥？ 它就是那條最優(yōu)的直線。我們把這個公式放在二維情況下看，二維中的直線是這樣定義的：y=ax+b。在二維中，w就是a，b還是b。所以wx+b是一條直線（比如說本文最開始那張圖中的藍(lán)線）。如果新的點(diǎn)x在藍(lán)線左側(cè)，那么wx+b<0,再經(jīng)過sign，最后f輸出-1，如果在右側(cè)，輸出1。等等，好像有點(diǎn)說不通，把情況等價到二維平面中，y=ax+b，只要點(diǎn)在x軸上方，甭管點(diǎn)在線的左側(cè)右側(cè)，最后結(jié)果都是大于0啊，這個值得正負(fù)跟線有啥關(guān)系？emmm….其實(shí)wx+b和ax+b表現(xiàn)直線的形式一樣，但是又稍有差別。我們把最前頭的圖逆時針旋轉(zhuǎn)45度，藍(lán)線是不是變成x軸了？哈哈這樣是不是原先藍(lán)線的右側(cè)變成了x軸的上方了？其實(shí)感知機(jī)在計算wx+b這條線的時候，已經(jīng)在暗地里進(jìn)行了轉(zhuǎn)換，使得用于劃分的直線變成x軸，左右側(cè)分別為x軸的上方和下方，也就成了正和負(fù)。

那么，為啥是wx+b，而不叫ax+b？ 在本文中使用零件作為例子，上文使用了長度和重量（x1，x2）來表示一個零件的屬性，所以一個二維平面就足夠，那么如果零件的品質(zhì)和色澤也有關(guān)系呢？那就得加一個x3表示色澤，樣本的屬性就變成了（x1，x2，x3），變成三維了。wx+b并不是只用于二維情況，在三維這種情況下，仍然可以使用這個公式。所以wx+b與ax+b只是在二維上近似一致，實(shí)際上是不同的東西。在三維中wx+b是啥？我們想象屋子里一個角落有藍(lán)點(diǎn)，一個角落有黃點(diǎn)，還用一條直線的話，顯然是不夠的，需要一個平面！所以在三維中，wx+b是一個平面！至于為什么，后文會詳細(xì)說明。四維呢？emmm…好像沒法描述是個什么東西可以把四維空間分開，但是對于四維來說，應(yīng)該會存在一個東西像一把刀一樣把四維空間切成兩半。能切成兩半，應(yīng)該是一個對于四維來說是個平面的東西，就像對于三維來說切割它的是一個二維的平面，二維來說是一個一維的平面。總之四維中wx+b可以表示為一個相對于四維來說是個平面的東西，然后把四維空間一切為二，我們給它取名叫超平面。由此引申，在高維空間中，wx+b是一個劃分超平面，這也就是它正式的名字。

正式來說： wx+b是一個n維空間中的超平面S，其中w是超平面的法向量，b是超平面的截距，這個超平面將特征空間劃分成兩部分，位于兩部分的點(diǎn)分別被分為正負(fù)兩類，所以，超平面S稱為分離超平面。

細(xì)節(jié)：

w是超平面的法向量：對于一個平面來說w就是這么定義的，是數(shù)學(xué)知識，可以谷歌補(bǔ)習(xí)一下

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

特征空間：也就是整個n維空間，樣本的每個屬性都叫一個特征，特征空間的意思是在這個空間中可以找到樣本所有的屬性組合

我們從最初的要求有個f(x)，引申到能只輸出1和-1的sign(x)，再到現(xiàn)在的wx+b，看起來越來越簡單了，只要能找到最合適的wx+b，就能完成感知機(jī)的搭建了。前文說過，讓誤分類的點(diǎn)距離和最大化來找這個超平面，首先我們要放出單獨(dú)計算一個點(diǎn)與超平面之間距離的公式，這樣才能將所有的點(diǎn)的距離公式求出來對不？

先看wx+b，在二維空間中，我們可以認(rèn)為它是一條直線，同時因?yàn)樽鲞^轉(zhuǎn)換，整張圖旋轉(zhuǎn)后wx+b是x軸，那么所有點(diǎn)到x軸的距離其實(shí)就是wx+b的值對不？當(dāng)然了，考慮到x軸下方的點(diǎn)，得加上絕對值->|wx+b|，求所有誤分類點(diǎn)的距離和，也就是求|wx+b|的總和，讓它最小化。很簡單啊，把w和b等比例縮小就好啦，比如說w改為0.5w，b改為0.5b，線還是那條線，但是值縮小兩倍啦！你還不滿意？我可以接著縮！縮到0去！所以啊，我們要加點(diǎn)約束，讓整個式子除以w的模長。啥意思？就是w不管怎么樣，要除以它的單位長度。如果我w和b等比例縮小，那||w||也會等比例縮小，值一動不動，很穩(wěn)。沒有除以模長之前，|wx+b|叫函數(shù)間隔，除模長之后叫幾何間隔，幾何間隔可以認(rèn)為是物理意義上的實(shí)際長度，管你怎么放大縮小，你物理距離就那樣，不可能改個數(shù)就變。在機(jī)器學(xué)習(xí)中求距離時，通常是使用幾何間隔的，否則無法求出解。

對于誤分類的數(shù)據(jù)，例如實(shí)際應(yīng)該屬于藍(lán)色的點(diǎn)（線的右側(cè)，y>0），但實(shí)際上預(yù)測出來是在左側(cè)（wx+b<0)，那就是分錯了，結(jié)果是負(fù)，這時候再加個符號，結(jié)果就是正了，再除以w的模長，就是單個誤分類的點(diǎn)到超平面的舉例。舉例總和就是所有誤分類的點(diǎn)相加。

上圖最后說不考慮除以模長，就變成了函數(shù)間隔，為什么可以這么做呢？不考慮wb等比例縮小這件事了嗎？上文說的是錯的嗎？

有一種解釋是這樣說的：感知機(jī)是誤分類驅(qū)動的算法，它的終極目標(biāo)是沒有誤分類的點(diǎn)，如果沒有誤分類的點(diǎn)，總和距離就變成了0，w和b值怎樣都沒用。所以幾何間隔和函數(shù)間隔在感知機(jī)的應(yīng)用上沒有差別，為了計算簡單，使用函數(shù)間隔。

以上是損失函數(shù)的正式定義，在求得劃分超平面的終極目標(biāo)就是讓損失函數(shù)最小化，如果是0的話就相當(dāng)完美了。

感知機(jī)使用梯度下降方法求得w和b的最優(yōu)解，從而得到劃分超平面wx+b，關(guān)于梯度下降及其中的步長受篇幅所限可以自行谷歌。

3 代碼實(shí)現(xiàn)

#coding=utf-8
#Author:Dodo
#Date:2018-11-15
#Email:lvtengchao@pku.edu.cn
'''
數(shù)據(jù)集：Mnist
訓(xùn)練集數(shù)量：60000
測試集數(shù)量：10000
------------------------------
運(yùn)行結(jié)果：
正確率：81.72%（二分類）
運(yùn)行時長：78.6s
'''
import numpy as np
import time
def loadData(fileName):
? ?'''
? ?加載Mnist數(shù)據(jù)集
? ?:param fileName:要加載的數(shù)據(jù)集路徑
? ?:return: list形式的數(shù)據(jù)集及標(biāo)記
? ?'''
? ?print('start to read data')
? ?# 存放數(shù)據(jù)及標(biāo)記的list
? ?dataArr = []; labelArr = []
? ?# 打開文件
? ?fr = open(fileName, 'r')
? ?# 將文件按行讀取
? ?for line in fr.readlines():
? ? ? ?# 對每一行數(shù)據(jù)按切割福','進(jìn)行切割，返回字段列表
? ? ? ?curLine = line.strip().split(',')
? ? ? ?# Mnsit有0-9是個標(biāo)記，由于是二分類任務(wù)，所以將>=5的作為1，<5為-1
? ? ? ?if int(curLine[0]) >= 5:
? ? ? ? ? ?labelArr.append(1)
? ? ? ?else:
? ? ? ? ? ?labelArr.append(-1)
? ? ? ?#存放標(biāo)記
? ? ? ?#[int(num) for num in curLine[1:]] -> 遍歷每一行中除了以第一哥元素（標(biāo)記）外將所有元素轉(zhuǎn)換成int類型
? ? ? ?#[int(num)/255 for num in curLine[1:]] -> 將所有數(shù)據(jù)除255歸一化(非必須步驟，可以不歸一化)
? ? ? ?dataArr.append([int(num)/255 for num in curLine[1:]])
? ?#返回data和label
? ?return dataArr, labelArr
def perceptron(dataArr, labelArr, iter=50):
? ?'''
? ?感知器訓(xùn)練過程
? ?:param dataArr:訓(xùn)練集的數(shù)據(jù) (list)
? ?:param labelArr: 訓(xùn)練集的標(biāo)簽(list)
? ?:param iter: 迭代次數(shù)，默認(rèn)50
? ?:return: 訓(xùn)練好的w和b
? ?'''
? ?print('start to trans')
? ?#將數(shù)據(jù)轉(zhuǎn)換成矩陣形式（在機(jī)器學(xué)習(xí)中因?yàn)橥ǔ６际窍蛄康倪\(yùn)算，轉(zhuǎn)換稱矩陣形式方便運(yùn)算）
? ?#轉(zhuǎn)換后的數(shù)據(jù)中每一個樣本的向量都是橫向的
? ?dataMat = np.mat(dataArr)
? ?#將標(biāo)簽轉(zhuǎn)換成矩陣，之后轉(zhuǎn)置(.T為轉(zhuǎn)置)。
? ?#轉(zhuǎn)置是因?yàn)樵谶\(yùn)算中需要單獨(dú)取label中的某一個元素，如果是1xN的矩陣的話，無法用label[i]的方式讀取
? ?#對于只有1xN的label可以不轉(zhuǎn)換成矩陣，直接label[i]即可，這里轉(zhuǎn)換是為了格式上的統(tǒng)一
? ?labelMat = np.mat(labelArr).T
? ?#獲取數(shù)據(jù)矩陣的大小，為m*n
? ?m, n = np.shape(dataMat)
? ?#創(chuàng)建初始權(quán)重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
? ?#進(jìn)行iter次迭代計算
? ?for k in range(iter):
? ? ? ?#對于每一個樣本進(jìn)行梯度下降
? ? ? ?#李航書中在2.3.1開頭部分使用的梯度下降，是全部樣本都算一遍以后，統(tǒng)一
? ? ? ?#進(jìn)行一次梯度下降
? ? ? ?#在2.3.1的后半部分可以看到（例如公式2.6 2.7），求和符號沒有了，此時用
? ? ? ?#的是隨機(jī)梯度下降，即計算一個樣本就針對該樣本進(jìn)行一次梯度下降。
? ? ? ?#兩者的差異各有千秋，但較為常用的是隨機(jī)梯度下降。
? ? ? ?for i in range(m):
? ? ? ? ? ?#獲取當(dāng)前樣本的向量
? ? ? ? ? ?xi = dataMat[i]
? ? ? ? ? ?#獲取當(dāng)前樣本所對應(yīng)的標(biāo)簽
? ? ? ? ? ?yi = labelMat[i]
? ? ? ? ? ?#判斷是否是誤分類樣本
? ? ? ? ? ?#誤分類樣本特診為： -yi(w*xi+b)>=0，詳細(xì)可參考書中2.2.2小節(jié)
? ? ? ? ? ?#在書的公式中寫的是>0，實(shí)際上如果=0，說明改點(diǎn)在超平面上，也是不正確的
? ? ? ? ? ?if -1 * yi * (w * xi.T + b) >= 0:
? ? ? ? ? ? ? ?#對于誤分類樣本，進(jìn)行梯度下降，更新w和b
? ? ? ? ? ? ? ?w = w + h * ?yi * xi
? ? ? ? ? ? ? ?b = b + h * yi
? ? ? ?#打印訓(xùn)練進(jìn)度
? ? ? ?print('Round %d:%d training' % (k, iter))
? ?#返回訓(xùn)練完的w、b
? ?return w, b
def test(dataArr, labelArr, w, b):
? ?'''
? ?測試準(zhǔn)確率
? ?:param dataArr:測試集
? ?:param labelArr: 測試集標(biāo)簽
? ?:param w: 訓(xùn)練獲得的權(quán)重w
? ?:param b: 訓(xùn)練獲得的偏置b
? ?:return: 正確率
? ?'''
? ?print('start to test')
? ?#將數(shù)據(jù)集轉(zhuǎn)換為矩陣形式方便運(yùn)算
? ?dataMat = np.mat(dataArr)
? ?#將label轉(zhuǎn)換為矩陣并轉(zhuǎn)置，詳細(xì)信息參考上文perceptron中
? ?#對于這部分的解說
? ?labelMat = np.mat(labelArr).T
? ?#獲取測試數(shù)據(jù)集矩陣的大小
? ?m, n = np.shape(dataMat)
? ?#錯誤樣本數(shù)計數(shù)
? ?errorCnt = 0
? ?#遍歷所有測試樣本
? ?for i in range(m):
? ? ? ?#獲得單個樣本向量
? ? ? ?xi = dataMat[i]
? ? ? ?#獲得該樣本標(biāo)記
? ? ? ?yi = labelMat[i]
? ? ? ?#獲得運(yùn)算結(jié)果
? ? ? ?result = -1 * yi * (w * xi.T + b)
? ? ? ?#如果-yi(w*xi+b)>=0，說明該樣本被誤分類，錯誤樣本數(shù)加一
? ? ? ?if result >= 0: errorCnt += 1
? ?#正確率 = 1 - （樣本分類錯誤數(shù) / 樣本總數(shù)）
? ?accruRate = 1 - (errorCnt / m)
? ?#返回正確率
? ?return accruRate
if __name__ == '__main__':
? ?#獲取當(dāng)前時間
? ?#在文末同樣獲取當(dāng)前時間，兩時間差即為程序運(yùn)行時間
? ?start = time.time()
? ?#獲取訓(xùn)練集及標(biāo)簽
? ?trainData, trainLabel = loadData('../Mnist/mnist_train.csv')
? ?#獲取測試集及標(biāo)簽
? ?testData, testLabel = loadData('../Mnist/mnist_test.csv')
? ?#訓(xùn)練獲得權(quán)重
? ?w, b = perceptron(trainData, trainLabel, iter = 30)
? ?#進(jìn)行測試，獲得正確率
? ?accruRate = test(testData, testLabel, w, b)
? ?#獲取當(dāng)前時間，作為結(jié)束時間
? ?end = time.time()
? ?#顯示正確率
? ?print('accuracy rate is:', accruRate)
? ?#顯示用時時長
? ?print('time span:', end - start)

4 建模資料

資料分享: 最強(qiáng)建模資料

2023高教社杯全國大學(xué)生數(shù)學(xué)建模競賽

資料思路分享Q群：575833716