之前學習了k-近鄰算法的實現后，參考《機器學習實戰》中的例子進行了k-近鄰算法的測驗，主要測試了針對約會網站和手寫識別系統的數據分類，這兩個測試使用的是《機器學習實戰》提供的數據集。 在編寫函數前，需在.py文件中添加以下內容： ~~~ from numpy import * import numpy as np import operator from os import listdir ~~~ **第一部分是針對約會網站的數據分類**，用于改進約會網站的配對效果。該實例的簡介如下： * 海倫一直使用在線約會網站尋找合適自己的約會對象。盡管約會網站會推薦不同的人選，但她沒有從中找到喜歡的人。經過一番總結，她發現曾交往過三種類型的人：? 1.不喜歡的人（ 以下簡稱1 ）；? 2.魅力一般的人（ 以下簡稱2 ）；? 3.極具魅力的人（ 以下簡稱3 ） * 盡管發現了上述規律，但海倫依然無法將約會網站推薦的匹配對象歸入恰當的分類。她覺得可以在周一到周五約會哪些魅力一般的人，而周末則更喜歡與那些極具魅力的人為伴。海倫希望我們的分類軟件可以更好的幫助她將匹配對象劃分到確切的分類中。此外海倫還收集了一些約會網站未曾記錄的數據信息，她認為這些數據更有助于匹配對象的歸類。 * 這里提取一下這個案例的目標：根據一些數據信息，對指定人選進行分類（1或2或3）。為了使用kNN算法達到這個目標，我們需要哪些信息？前面提到過，就是需要樣本數據，仔細閱讀我們發現，這些樣本數據就是“海倫還收集了一些約會網站未曾記錄的數據信息 ”。 針對以上的描述，需要進行以下步驟： 1. 收集數據 2. 準備數據 3. 設計算法分析數據 4. 測試算法 **1.收集數據** 海倫收集的數據是記錄一個人的三個特征：每年獲得的飛行常客里程數；玩視頻游戲所消耗的時間百分比；每周消費的冰淇淋公升數。數據是txt格式文件，如下圖，前三列依次是三個特征，第四列是分類（1：代表不喜歡的人，2：代表魅力一般的人，3：代表極具魅力的人），每一行數據代表一個人。  **2.準備數據** 計算機需要對數據文件txt讀取數據，因此需要把數據進行格式化，對于數學運算，計算機擅長把數據存放在矩陣中。以下代碼中`file2matrix(filename)`函數完成了這一工作，該函數輸入數據文件名（字符串），輸出訓練樣本矩陣和類標簽向量。 這一過程返回兩個矩陣：一個矩陣用于存放每個人的三個特征數據，一個矩陣存放每個人對應的分類。 **3.設計算法分析數據** k-近鄰算法的思想是尋找測試數據的前k個距離最近的樣本，然后根據這k個樣本的分類來確定該數據的分類，**遵循“多數占優”原則**。因此，如何尋找樣本成為主要的問題，**在信號處理和模式識別領域中，常常使用“距離”來度量信號或特征的相似度**。在這里，我們假定可以使用三個特征數據來代替每個人，比如第一個人的屬性我們用[40920， 8.326976， 0.953952]來代替，并且他的分類是3。那么此時的距離就是點的距離。 求出測試樣本與訓練樣本中每個點的距離，然后進行從小到大排序，前k位的就是k-近鄰，然后看看這k位近鄰中占得最多的分類是什么，也就獲得了最終的答案。這一部分是k-近鄰算法的核心，代碼中`classify()`函數就實現了k-近鄰算法的核心部分。 一個優化算法效果的步驟——歸一化數據： 打開數據文件我們可用發現第一列代表的特征數值遠遠大于其他兩項特征，這樣在求距離的公式中就會占很大的比重，致使兩個樣本的距離很大程度上取決于這個特征，其他特征的特性變得可有可無，這顯然有悖于實際情況。因此通常我們可用使用歸一化這一數學工具對數據進行預處理，這一處理過后的各個特征既不影響相對大小又可以不失公平。`Normalize(data)`函數實現了這一功能。 **4.測試算法** 經過了對數據進行預處理后、歸一化數值，可用驗證kNN算法有效性，測試代碼為：`WebClassTest()`?由于數據有1000條，我們設置一個比率`ratio = 0.1`也就是令?`1000 * ratio = 100`?條作為測試樣本，其余`900`條作為訓練樣本，當然，`ratio`的值可用改變，對算法效果是有影響的。 實現代碼： ~~~ def classify(data, sample, label, k): SampleSize = sample.shape[0] DataMat = tile(data, (SampleSize, 1)) delta = (DataMat - sample)**2 distance = (delta.sum(axis = 1))**0.5 # sortedDist = distance.argsort() classCount = {} for i in range(k): votedLabel = label[sortedDist[i]] classCount[votedLabel] = classCount.get(votedLabel, 0) + 1 result = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True) return result[0][0] #print classify([10,0], sample, label, 3) def file2matrix(filename): fil = open(filename) fileLines = fil.readlines() # Convert the contents of a file into a list lenOfLines = len(fileLines) Mat = zeros((lenOfLines, 3)) classLabel = [] index = 0 for line in fileLines: line = line.strip() listFromLine = line.split('\t') Mat[index,: ] = listFromLine[0:3] classLabel.append(int(listFromLine[-1])) # the last one of listFromLine is Label index += 1 return Mat, classLabel mat,label = file2matrix('datingTestSet2.txt') #print mat # draw import matplotlib import matplotlib.pyplot as plt fil = open('datingTestSet2.txt') fileLines = fil.readlines() # Convert the contents of a file into a list lenOfLines = len(fileLines) figure = plt.figure() axis = figure.add_subplot(111) lab = ['didntLike', 'smallDoses', 'largeDoses'] for i in range(3): n = [] l = [] for j in range(lenOfLines): if label[j] == i + 1: n.append(list(mat[j,0:3])) l.append(label[j]) n = np.array(n) # list to numpy.adarray #reshape(n, (3,k)) axis.scatter(n[:,0], n[:,1], 15.0*array(l), 15.0*array(l), label = lab[i]) print type(mat) print type(n) plt.legend() plt.show() def Normalize(data): minValue = data.min(0) maxValue = data.max(0) ValueRange = maxValue - minValue norm_data = zeros(shape(data)) k = data.shape[0] norm_data = data - tile(minValue, (k, 1)) norm_data = norm_data / tile(ValueRange, (k, 1)) return norm_data, ValueRange, minValue def WebClassTest(): ratio = 0.1 dataMat, dataLabels = file2matrix('datingTestSet2.txt') normMat, ValueRange, minValue = Normalize(dataMat) k = normMat.shape[0] num = int(k * ratio) # test sample : 10% errorCount = 0.0 for i in range(num): result = classify(normMat[i,:], normMat[num:k,:],\ dataLabels[num:k], 7) # k = 3 print "The classifier came back with: %d, the real answer is %d"\ % (result, dataLabels[i]) if (result != dataLabels[i]): errorCount += 1 print "The total error rate is %f " % (errorCount / float(num)) WebClassTest() ~~~ 在程序設計過程中，需要注意list、array、adarray等數據結構的使用，numpy.ndarray和標準Python庫類array.array功能是不相同的。以上代碼中`print type(mat)`和`print type(n)`?就是為了觀察各變量的類型。允許以上代碼，可用畫出散點圖如下：  以上散點使用數據集中第二維和第三維數據繪制而出，當然，你可用選擇其他維度的數據畫二維散點圖，或者使用所有維度的數據畫高維圖（未實現），如下圖所示：  對約會網站分類的測試，由于分類效果依賴于參數k和測試樣本占樣本數目的比例，開始測試按照書中的參數進行，取`k=3`，測試樣本占總樣本比例為`0.1`進行測試，結果如下：  理論上來說，增大k的取值可以提高準確率，但實際上若k值太大，也會造成準確率下降，而且運算復雜度增大。 k = 7：  k = 17：  另一方面，降低ratio值（即增大訓練樣本集的比率）也可以提高算法的準確率，但由于每次算法需要比較更多的樣本，因此算法復雜度也會增加。 **第二部分是手寫數字識別**： 首先來看看書本給出的數據集： ~~~ def img2vector(filename): returnVect = zeros((1,1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnVect[0,32*i+j] = int(lineStr[j]) return returnVect def handwritingClassTest(): hwLabels = [] trainingFileList = listdir('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) trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr) testFileList = listdir('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('testDigits/%s' % fileNameStr) classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 3) # k = 3 print "The classifier came back with: %d, the real answer is: %d"\ % (classifierResult, classNumStr) if (classifierResult != classNumStr): errorCount = errorCount + 1.0 print "\nThe total number of errors is: %d" % errorCount print "\nThe total error rate is: %f" % (errorCount/float(mTest)) handwritingClassTest() ~~~ 一個結果（`k = 3`）：  `k = 7`時的結果，正確率并不比`k = 3`時要好：  在手寫數字識別過程中，隨著k值得增大，準確率反而降低了。k的取值并不是越大越好。 至此，完成了k-近鄰算法的學習和實例驗證。比起其他機器學習方法，k-近鄰算法是最簡單最有效的分類數據算法，使用算法時必須有接近實際數據的訓練樣本數據。但是如前一節所說的，該算法的缺點也很多，最大的一點是無法給出數據的內在含義。事實上k決策樹是k-近鄰算法的優化版本，比起前者，決策樹有效減少了儲存空間和計算空間的開銷，后期需繼續深入學習！