第二十章 KNN演算法(上)

KNN分類演算法，是理論上比較成熟的方法，也是最簡單的機器學習演算法之一。

該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

一個對於KNN演算法解釋最清楚的圖如下所示：

藍方塊和紅三角均是已有分類數據，當前的任務是將綠色圓塊進行分類判斷，判斷是屬於藍方塊或者紅三角。

當然這裡的分類還跟K值是有關的：

如果K=3(實線圈)，紅三角佔比2/3，則判斷為紅三角；

如果K=5(虛線圈)，藍方塊佔比3/5，則判斷為藍方塊。

由此可以看出knn演算法實際上根本就不用進行訓練，而是直接進行計算的，訓練時間為0，計算時間為訓練集規模n。

knn演算法的基本要素大致有3個：

　　1、K 值的選擇

　　2、距離的度量

　　3、分類決策規則

使用方式

1. K 值會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最有的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。
2. 演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別
3. 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規範化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。

knn演算法在分類時主要的不足是，當樣本不平衡時，如果一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的 K 個鄰居中大容量類的樣本占多數。

KNN演算法python2代碼實現

from numpy import *import operatorfrom os import listdirimport matplotlibimport matplotlib.pyplot as pltdef classify0(inX, dataSet, labels, k):#對每組數據進行分類，inX為用於分類的輸入向量， dataSetSize = dataSet.shape[0] diffMat = tile(inX, (dataSetSize,1)) - dataSet#歐式距離計算tile函數位於python模塊 numpy.lib.shape_base中，他的功能是重複某個數組。比如tile(A,n)，功能是將數組A重複n次，構成一個新的數組 sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 sortedDistIndicies = distances.argsort() classCount={} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)#，將classCount字典分解為元祖列表，排序k個距離值 return sortedClassCount[0][0]#返回發生頻率最高的元素標籤def createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = [A,A,B,B] return group, labelsdef 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創建返回的numpy矩陣，這裡的3 可以按照實際需求去改 classLabelVector = [] #prepare labels return fr = open(filename) index = 0 for line in fr.readlines():#解析文件數據到列表 line = line.strip()#截取掉所有的回車字元 #print line listFromLine = line.split( )#分割成元素列表 #print listFromLine returnMat[index,:] = listFromLine[0:3]#選取前3個元素存儲到特徵矩陣中 #print returnMat[index,:] classLabelVector.append(int(listFromLine[-1]))#將列表中的最後一列存儲到向量classLabelVector中，這裡必須是int,否則會默認字元串 index += 1 return returnMat,classLabelVector#輸出為訓練樣本矩陣與類標籤向量 def autoNorm(dataSet):#該函數可以自動將數字特徵值轉換為0到1的區間 minVals = dataSet.min(0)#將每列的最小值放在變數minVals中 maxVals = dataSet.max(0)#將每列的最大值放在變數maxVals中 ranges = maxVals - minVals normDataSet = zeros(shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - tile(minVals, (m,1))#tile()函數將變數內容複製成輸入矩陣同樣大小的矩陣 normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide#/表示具體特徵值相除而不是矩陣相除 return normDataSet, ranges, minVals def datingClassTest():#計算錯誤率 評估分類器準確率，該函數可以在任何時候測試分類器效果 hoRatio = 0.10 #hold out 10% datingDataMat,datingLabels = file2matrix(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/datingTestSet2.txt) #load data setfrom file normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRatio)#計算測試樣本的數量 errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],4)#將訓練與測試數據輸入到分類器函數classify0函數中 #print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]) if (classifierResult != datingLabels[i]): errorCount += 1.0 print "the total error rate is: %f" % (errorCount/float(numTestVecs))#改變hoRatio與k的值，檢驗錯誤率會有所不同。 print errorCount def img2vector(filename):#在二進位存儲的圖像數據上使用KNN，將圖像轉換為測試向量 returnVect = zeros((1,1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32):#循環讀出文件的前32行 returnVect[0,32*i+j] = int(lineStr[j])#將32*32的二進位圖像矩陣轉化為1*1024的向量 return returnVect#返回數組from os import listdirdef handwritingClassTest():#測試演算法，使用knn識別手寫數字 hwLabels = [] trainingFileList = listdir(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/trainingDigits) #load the training set 列出給定目錄的文件名 m = len(trainingFileList) trainingMat = zeros((m,1024))#訓練矩陣，該矩陣的每行數據存儲一個圖像 for i in range(m):#從文件名解析分類數字 fileNameStr = trainingFileList[i] fileStr = fileNameStr.split(.)[0] #take off .txt classNumStr = int(fileStr.split(_)[0])# hwLabels.append(classNumStr)#將類編碼存儲在hwLabels向量中 trainingMat[i,:] = img2vector(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/trainingDigits/%s % fileNameStr) testFileList = listdir(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/testDigits) #iterate through the test set errorCount = 0.0 mTest = len(testFileList) for i in range(mTest): fileNameStr = testFileList[i] fileStr = fileNameStr.split(.)[0] #take off .txt classNumStr = int(fileStr.split(_)[0]) vectorUnderTest = img2vector(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/testDigits/%s % fileNameStr) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr) if (classifierResult != classNumStr): errorCount += 1.0 print "
the total number of errors is: %d" % errorCount print "
the total error rate is: %f" % (errorCount/float(mTest)) if __name__=="__main__": datingDataMat,datingLabels=file2matrix(C:/Users/HZF/Desktop/machinelearninginaction/Ch02/datingTestSet2.txt) print datingDataMat #print datingLabels[:20] normDataSet, ranges, minVals=autoNorm(datingDataMat) print normDataSet errorCount=datingClassTest() handwritingClassTest() #print errorCount fig=plt.figure()#創建散點圖圖形化數據，以辨識數據模式 ax=fig.add_subplot(111) ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))#使用數據集的第2,3列數據,利用變數datingLables存儲的類標籤屬性，繪製色彩，尺寸不同的點 plt.show()

KNN演算法上篇就寫這麼多，歡迎評論！

參考文獻

1、[機器學習] --KNN K-最鄰近演算法

2、《機器學習實戰》 （書）

推薦閱讀：