# 0 賽題思路

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

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

1 感知機的直觀理解

感知機應該屬于機器學習算法中最簡單的一種算法，其原理可以看下圖：

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

在預測上很簡單，拿到一個新的零件，我們測出它的長度x1，質量x2，如果兩項都大于均值，說明零件合格。這就是我們人的人工智能。

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

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

讀者也看到了，對于圖中的兩堆點，我們有無數條直線可以將其劃分開，事實上我們不光要能劃分當前的點，當新來的點進來是，也要能很好地將其劃分，所以哪條線最好呢？

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

得出結論：
如果一條直線能夠不分錯一個點，那就是一條好的直線
進一步來說：

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

2 感知機的數學角度

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

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

sign好像很簡單，當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是一條直線（比如說本文最開始那張圖中的藍線）。如果新的點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…好像沒法描述是個什么東西可以把四維空間分開，但是對于四維來說，應該會存在一個東西像一把刀一樣把四維空間切成兩半。能切成兩半，應該是一個對于四維來說是個平面的東西，就像對于三維來說切割它的是一個二維的平面，二維來說是一個一維的平面?？傊木S中wx+b可以表示為一個相對于四維來說是個平面的東西，然后把四維空間一切為二，我們給它取名叫超平面。由此引申，在高維空間中，wx+b是一個劃分超平面，這也就是它正式的名字。

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

細節(jié)：

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.5w，b改為0.5b，線還是那條線，但是值縮小兩倍啦！你還不滿意？我可以接著縮！縮到0去！所以啊，我們要加點約束，讓整個式子除以w的模長。啥意思？就是w不管怎么樣，要除以它的單位長度。如果我w和b等比例縮小，那||w||也會等比例縮小，值一動不動，很穩(wěn)。沒有除以模長之前，|wx+b|叫函數間隔，除模長之后叫幾何間隔，幾何間隔可以認為是物理意義上的實際長度，管你怎么放大縮小，你物理距離就那樣，不可能改個數就變。在機器學習中求距離時，通常是使用幾何間隔的，否則無法求出解。

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

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

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

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

感知機使用梯度下降方法求得w和b的最優(yōu)解，從而得到劃分超平面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')# 存放數據及標記的listdataArr = []; labelArr = []# 打開文件fr = open(fileName, 'r')# 將文件按行讀取for line in fr.readlines():# 對每一行數據按切割福','進行切割，返回字段列表curLine = line.strip().split(',')# Mnsit有0-9是個標記，由于是二分類任務，所以將>=5的作為1，<5為-1if 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和labelreturn 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*nm, n = np.shape(dataMat)#創(chuàng)建初始權重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#進行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小節(jié)#在書的公式中寫的是>0，實際上如果=0，說明改點在超平面上，也是不正確的if -1 * yi * (w * xi.T + b) >= 0:#對于誤分類樣本，進行梯度下降，更新w和bw = w + h *  yi * xib = b + h * yi#打印訓練進度print('Round %d:%d training' % (k, iter))#返回訓練完的w、breturn 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 建模資料

資料分享: 最強建模資料