# 0 賽題思路

（賽題出來以后第一時(shí)間在CSDN分享）

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

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

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

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

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

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

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

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

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

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

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

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

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

瞧，f(x)不是出來了嘛，sign是啥？wx+b是啥？別著急，我們?cè)倏匆幌聅igin函數(shù)是什么。

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

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

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

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

細(xì)節(jié)：

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

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

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

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

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

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

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

有一種解釋是這樣說的：感知機(jī)是誤分類驅(qū)動(dòng)的算法，它的終極目標(biāo)是沒有誤分類的點(diǎn)，如果沒有誤分類的點(diǎn)，總和距離就變成了0，w和b值怎樣都沒用。所以幾何間隔和函數(shù)間隔在感知機(jī)的應(yīng)用上沒有差別，為了計(jì)算簡單，使用函數(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
測(cè)試集數(shù)量：10000
------------------------------
運(yùn)行結(jié)果：
正確率：81.72%（二分類）
運(yùn)行時(shí)長：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)記的listdataArr = []; labelArr = []# 打開文件fr = open(fileName, 'r')# 將文件按行讀取for line in fr.readlines():# 對(duì)每一行數(shù)據(jù)按切割福','進(jìn)行切割，返回字段列表curLine = line.strip().split(',')# Mnsit有0-9是個(gè)標(biāo)記，由于是二分類任務(wù)，所以將>=5的作為1，<5為-1if 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和labelreturn 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ù)中每一個(gè)樣本的向量都是橫向的dataMat = np.mat(dataArr)#將標(biāo)簽轉(zhuǎn)換成矩陣，之后轉(zhuǎn)置(.T為轉(zhuǎn)置)。#轉(zhuǎn)置是因?yàn)樵谶\(yùn)算中需要單獨(dú)取label中的某一個(gè)元素，如果是1xN的矩陣的話，無法用label[i]的方式讀取#對(duì)于只有1xN的label可以不轉(zhuǎn)換成矩陣，直接label[i]即可，這里轉(zhuǎn)換是為了格式上的統(tǒng)一labelMat = np.mat(labelArr).T#獲取數(shù)據(jù)矩陣的大小，為m*nm, 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為0b = 0#初始化步長，也就是梯度下降過程中的n，控制梯度下降速率h = 0.0001#進(jìn)行iter次迭代計(jì)算for k in range(iter):#對(duì)于每一個(gè)樣本進(jìn)行梯度下降#李航書中在2.3.1開頭部分使用的梯度下降，是全部樣本都算一遍以后，統(tǒng)一#進(jìn)行一次梯度下降#在2.3.1的后半部分可以看到（例如公式2.6 2.7），求和符號(hào)沒有了，此時(shí)用#的是隨機(jī)梯度下降，即計(jì)算一個(gè)樣本就針對(duì)該樣本進(jìn)行一次梯度下降。#兩者的差異各有千秋，但較為常用的是隨機(jī)梯度下降。for i in range(m):#獲取當(dāng)前樣本的向量xi = dataMat[i]#獲取當(dāng)前樣本所對(duì)應(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:#對(duì)于誤分類樣本，進(jìn)行梯度下降，更新w和bw = w + h *  yi * xib = b + h * yi#打印訓(xùn)練進(jìn)度print('Round %d:%d training' % (k, iter))#返回訓(xùn)練完的w、breturn w, b
def test(dataArr, labelArr, w, b):'''測(cè)試準(zhǔn)確率:param dataArr:測(cè)試集:param labelArr: 測(cè)試集標(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中#對(duì)于這部分的解說labelMat = np.mat(labelArr).T#獲取測(cè)試數(shù)據(jù)集矩陣的大小m, n = np.shape(dataMat)#錯(cuò)誤樣本數(shù)計(jì)數(shù)errorCnt = 0#遍歷所有測(cè)試樣本for i in range(m):#獲得單個(gè)樣本向量xi = dataMat[i]#獲得該樣本標(biāo)記yi = labelMat[i]#獲得運(yùn)算結(jié)果result = -1 * yi * (w * xi.T + b)#如果-yi(w*xi+b)>=0，說明該樣本被誤分類，錯(cuò)誤樣本數(shù)加一if result >= 0: errorCnt += 1#正確率 = 1 - （樣本分類錯(cuò)誤數(shù) / 樣本總數(shù)）accruRate = 1 - (errorCnt / m)#返回正確率return accruRate
if __name__ == '__main__':#獲取當(dāng)前時(shí)間#在文末同樣獲取當(dāng)前時(shí)間，兩時(shí)間差即為程序運(yùn)行時(shí)間start = time.time()#獲取訓(xùn)練集及標(biāo)簽trainData, trainLabel = loadData('../Mnist/mnist_train.csv')#獲取測(cè)試集及標(biāo)簽testData, testLabel = loadData('../Mnist/mnist_test.csv')#訓(xùn)練獲得權(quán)重w, b = perceptron(trainData, trainLabel, iter = 30)#進(jìn)行測(cè)試，獲得正確率accruRate = test(testData, testLabel, w, b)#獲取當(dāng)前時(shí)間，作為結(jié)束時(shí)間end = time.time()#顯示正確率print('accuracy rate is:', accruRate)#顯示用時(shí)時(shí)長print('time span:', end - start)

4 建模資料

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