十分種讀懂KNN
引言
機器學習的演算法常常模擬人類的思考方式來對物體進行判斷。在人類進行學習和理解世界的過程中，常常採用一種將相似物體分到同一類別的方式進行對事物的判斷，也就是：「物以類聚，人以群分」的思維方式。機器學習中也有這樣的分類演算法。以下的例子可以幫助我們更好的解釋這樣的演算法。
通過對於一些電影的畫面內容的分析，我們發現，以下的幾部電影有這樣一些特點：
在一段視頻類型的判斷上，我們通過打鬥鏡頭數目和接吻鏡頭數目來判斷電影的類型，接吻多的是Romance類型的，而打鬥多的是動作電影。當給出一段新的視頻時，我們發現這一段視頻中出現了75個接吻鏡頭，8個打鬥鏡頭，那麼我們如何判斷新的視頻的類型呢？
我們發現75和8這兩個數字和上述表格仲的前三組數據很相近，而前三組數據都被歸類為Romance類型的電影，所以新的視頻也屬於這樣的類型。實際上，上述的問題是一個典型的鄰近演算法問題(或者說KNN，K-NearestNeighbor)。就是先用打鬥次數和接吻次數作為電影的坐標，然後計算其他六部電影與未知電影之間的距離，取得前K個距離最近的電影，然後統計這k個距離最近的電影里，屬於哪種類型的電影最多，比如Action最多，則說明未知的這部電影屬於動作片類型。
在這樣的演算法中，我們首先要獲得一些數據的特徵和已知的他們的分類或者回歸結果，面對新的數據的特徵時，我們找到與新的數據特徵最為相近，也就是特徵的距離最小的K個已知數據，通過這K個數據的分類結果來判斷新的數據的類型。當K個數據屬於不同的類別的時候，我們就通過「少數服從多數」的方式來進行判斷。下面我們就將介紹KNN鄰近演算法以及其中的實現細節。
什麼是特徵？
任何回歸分類的判斷都離不開對於特徵的處理。一般情況下，我們的特徵可以是連續的也可以是離散的。所謂連續的就是指在一定範圍內，特徵的數值可以是這個範圍內的任何數字，比如溫度、濕度、身高、體重。而離散的指的是特徵的數值只能是一段數值中的某幾個值，比如台階的個數只能是整數，而不會出現是2.3這樣的數字。在鄰近演算法在中，我們的所有特徵都要是能通過數字來表達的值，不能是主觀的判斷，比如一般美，特別丑等等。
在KNN演算法中，我們已知的數據的特徵和需要被判斷的特徵都要是屬於相同類別，特徵的種類相同，數目相同。
在數學中，我們用坐標來表示點的位置，這個位置就可以認為是特徵。而當特徵的種類比較多時，我們採取一個數列來表示這種特徵。當第i個人的身高（160cm）、體重（53kg）、視力（1.0）、年齡（17）、腰圍（65cm）作為特徵時，他的特徵a可以表示為ai=(160, 53, 1, 17, 65)。這就是他的特徵向量。
特徵之間的距離
如何判斷樣本之間特徵的相似程度呢？在直角坐標系中，我們用點與點之間直線距離表示點與點的相近程度，在鄰近演算法中，我們採取了相似的方式描述特徵之間的相似程度。在一個直角坐標系中，點A(x1,y1)與點B(x2,y2)之間的距離常常可以計算為：
這個距離又叫做歐氏距離。
在鄰近演算法中，我們可以把每個樣本看成是高緯度的空間中的點，而他們的相近程度也可以被點之間的距離來定義。我們假設此時我們有d維度的特徵，也就是d維度的空間。那麼樣本下x,y相似度可以用歐氏距離表示為：
距離越近表示樣本越相似，距離越大表示樣本特徵相差較大。
KNN鄰近演算法
KNN鄰近演算法的定義是指對一個D維空間的樣本x，找到訓練集樣本空間中K個距離x最近的點，統計這K個距離最近的點的類別，找出個數對多的類別，將x歸入該類別。
其實KNN是一種相當直觀的演算法，KNN通過比較一個未分類樣本與已訓練樣本集的相似性，來確定該樣本的類別。
KNN演算法有以下的條件：
- 給出一個正整數K，作為最鄰近的點的個數
- 給定一個已知類別的訓練集
- 給定一個用來描述樣本之間距離的標準
形象化的展示如下：
配圖 1 通過KNN演算法判斷點的類別
我們需要判斷Xu點的類別，屬於紅色、綠色還是藍色類別，給出K=5的要求，找到歐氏距離定義下最為臨近的5個點。此時發現這5個點有四個屬於紅色，一個屬於綠色。說明在紅色組出現的概率比較大，少數服從多數，那麼心的點就屬於紅色類別。
K值的選擇
KNN演算法中，K的值是我們自己指定的，那麼K的值應該如何進行選擇呢？K值的選擇又會對結果帶來什麼樣的影響呢？如何根據不同的題目條件選擇不同的K值呢？我們看這樣一個例子：
在圖中，我們希望對綠色的圓形進行分類，判斷這個圓形屬於紅色的三角形還是藍色的方形。圖片上的距離已經是距離綠色的點進行計算之後的距離。
配圖 2 通過KNN演算法判斷點的類別
當我們認為K = 3 的時候，小圈裡最近的點有三個，兩個紅色一個藍色，那麼紅色的概率比較大，說明綠色的點屬於紅色類別。然而，如果我們認為K = 5，神奇的事情發生了，在虛線的圓里，有三個藍色，兩個紅色的物體，那麼按照少數服從多數的原則，綠色的小點應該屬於藍色類別。這個例子說明了，K的選擇能夠改變最終的分類結果。
事實上，k值選擇過小，得到的近鄰數過少，會降低分類精度，同時也會放大雜訊數據的干擾；而如果k值選擇過大，並且待分類樣本屬於訓練集中包含數據數較少的類，那麼在選擇k個近鄰的時候，實際上並不相似的數據亦被包含進來，造成雜訊增加而導致分類效果的降低。
在實際的使用中，K值的選擇通常小於訓練樣本數目的平方根。還常常對不同的K值進行多次實驗，找到最為合適的K值。
而在上圖中我們又意識到，距離樣本相對近的點和在K值範圍內距離樣本相對遠的點實際上可能對樣本的分類有不同的意義。距離近的點理應在分類結果上受到偏向和有待。所以在實際計算中，當確定了K值範圍內的點後，我們不僅僅採取「少數服從多數」的思想，而是讓距離樣本近的點擁有更大的話語權，加重他們的權重。
拓展閱讀：K值的選擇
配圖 3 K值對於分類結果的影響
在上圖中，我們想要把黃色和藍色的樣本進行區分，圖上的每一點都是已知的訓練數據，紫色的線描述了實際上的真是分類曲線。黑色的線描述了使用KNN演算法時採用不同的K值進行計算後得到的分類曲線。我們可以發現，K越小，分類邊界曲線越光滑，偏差越小，方差越大；K越大，分類邊界曲線越平坦，偏差越大，方差越小。當k值比較小的時候，容易發現「過擬合」現象，即擬合的結果和給出的例子關係很大，而K值過大，常常出現「欠擬合」現象，也就是說擬合的不夠精準。關於「過擬合」和「欠擬合」的問題我們會在其他演算法進一步討論。
KNN演算法優劣
優勢：
- KNN演算法與人類日常思考模式很相近，不需要估計參數，也不會生成最終的分類器。
- 適合對稀有事件進行分類。較小數據量的快速分類常常使用KNN演算法。
- 特別適合於多分類問題(multi-modal,對象具有多個類別標籤)。在這一類問題上，KNN演算法要優於很多其他的機器學習演算法。
劣勢
- KNN演算法是一種懶惰演算法，進行分類時由於要計算每個樣本之間的距離，計算開銷很大，運行比較慢。當數據量非常大時，不適合用KNN演算法。
- 當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。在極端情況下，如果某一類別的樣本數目甚至小於K，那麼最終的分類結果勢必要收到很大的影響。
- 分類結果完全以來於訓練樣本，不能給出分類規則。
KNN演算法流程
- 準備數據，對數據進行預處理
- 選用合適的數據結構存儲訓練數據和測試數據
- 設定參數，如k，選擇距離評判方式
- 維護一個大小為k的的按距離由大到小的優先順序隊列，用於存儲最近鄰訓練數據。隨機從訓練數據中選取k個數據作為初始的最近鄰樣本，分別計算測試數據到這k個樣本的距離，將訓練樣本標號和距離存入優先順序隊列
- 遍歷訓練數據集，計算當前訓練數據與測試數據的距離，將所得距離L 與優先順序隊列中的最大距離Lmax
- 進行比較。若L>=Lmax，則捨棄該數據，遍歷下一個數據。若L < Lmax，刪除優先順序隊列中最大距離的數據，將當前訓練數據存入優先順序隊列。
- 遍歷完畢，計算優先順序隊列中k 個數據的多數類，並將其作為測試數據的類別。
- 測試數據集測試完畢後計算誤差率，繼續設定不同的k 值重新進行訓練，最後取誤差率最小的k 值。
學會使用Scikit-Learn中決策樹工具
【問題描述】
你在一家互聯網企業從事數據挖掘的職位，你的朋友在同一家互聯網公司的人力資源部工作，經常要篩選各類簡歷。她最近在忙於找到合適的軟體開發工程師人選，可是簡歷很多，她想通過幾個標準對候選人進行分類。在從前的招聘過程中，曾經留下了之前候選人的資料和他們面試的評級，這位HR小姐姐希望在輸入一些特徵之後，直接對評級進行預測，減少工作量。特徵分別是「每半年寫程序行數」，「在github上提交開源代碼的項目數」和「每個月看專業書籍的數量」。HR小姐姐將這些候選人分類為「牛逼程序員」（1），「一般程序員」（2）和「有待提高的程序員」（3）。這些數據的一部分例子如下，其他數據保存在txt文檔中。
【應聘者條件與應聘結果】
【解題思路】
1） 數據預處理：
我們得將txt文本中提供的數據放到矩陣或矢量中進行存儲，然後還需要將數據進行歸一化。
- 首先將數據從txt轉化為矩陣進行存儲
#函數名：file2matrix
#輸入：文件名
#輸出：returnMat為txt文本數據的前三列構成的二維數組
# classLabelVector為txt文本數據第四列的分類信息的一維矢量
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines()) #get the number of lines in the file
returnMat = zeros((numberOfLines,3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split( )
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
- 將數據進行歸一化
為什麼要進行數據歸一化？分析下數據可以看出，代碼數量相對於其他兩個特徵的數據來說通常要大的多，如果不進行數據歸一化，那麼在計算距離的時候飛行距離對結果的影響占絕對主導性，這顯然是不合理的，所以需要進行數據歸一化，歸一化的python代碼如下所示：
#函數名：autoNorm
#輸入：dataSet為原始數據二維數組
#輸出：normDataSet歸一化之後的二維數組，ranges為每一列最大值減去最小值的範圍，minVals為每一列的最小值。
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals
2）測試演算法
通常來說，我們使用數據的90%作為訓練數據，10%的數據作為測試數據。測試的指標為出錯率，當預測的分類和實際的分類結果不一致時，記錄一個錯誤，錯誤的總數/測試的樣本數即為出錯率。
#函數名：workingClassTest
#輸入：無
#輸出：無，但是會列印出錯個數及錯誤率。
def workingClassTest():
hoRatio = 0.50 #hold out 10%
workingDataMat,workingLabels = file2matrix(workingTestSet2.txt) #load data setfrom file
normMat, ranges, minVals = autoNorm(workingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],workingLabels[numTestVecs:m],3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, workingLabels[i])
if (classifierResult != workingLabels[i]): errorCount += 1.0
print "the total error rate is: %f" % (errorCount/float(numTestVecs))
print errorCount
結果如下， 錯誤率為6.4%
3）應用演算法：
當錯誤率達到滿意時，我們對演算法進行使用。
def classifyPerson():
resultList = [excellent,so so,not good]
github = float(raw_input("githubproject:"))
codelines = float(raw_input("linesofcode"))
bookNum = float(raw_input("reading books per month:"))
workingDataMat, workingLabels = file2matrix("workingTestSet2.txt")
normMat, ranges, minVals = autoNorm(workingDataMat)
inArray = array([codelines, github, bookNum])
classifyResult = classify0((inArray - minVals)/ranges, normMat, workingLabels, 3)
print "prediction result is: ", resultList[classifyResult - 1]
運行結果knn.classifyPerson() 輸入三個指標，就可以幫助HR小姐姐減小工作量啦。
想學習了解人工智慧知識的小夥伴們，請關註：
http://weixin.qq.com/r/KSoBGQ3EulDFrUl69387 (二維碼自動識別)
推薦閱讀：