[題外話]近期申請了一個微信公衆号：平凡程式人生。有興趣的朋友可以關注，那裡将會涉及更多機器學習、OpenCL+OpenCV以及圖像處理方面的文章。
2.2 簡單執行個體
為了驗證前面實作的K近鄰算法正确性，先設計一個簡單執行個體。
該執行個體中，在code中調用函數createDataSet()建立了樣本資料group及分類 labels，具體實作如下：
def createDataSet():
group = array([[1.1, 1.1], [1.0, 1.2], [0.2, 0.4], [0.9, 0.1]]) #建立4x2的數組作為訓練樣本
labels = ['A', 'A', 'B', 'B'] #4個訓練樣本所屬類的标記
return group, labels
然後調用子產品kNN的函數kNN.knnClassify()對應測試樣本[0.2, 0]進行分類測試，其分類結果為B，符合預期。具體實作如下：
group, labels = createDataSet() #建立訓練樣本和對應标記
realIndex = kNN.knnClassify([0.2, 0], group, labels, 3) #檢測測試樣本[0.2, 0]屬于哪個類
print realIndex
為了清楚地看到訓練樣本各個類别的分類情況，可以調用matplotlib繪制了樣本資料的散列圖。具體實作如下：
#Matplotlib 裡的常用類的包含關系為 Figure -> Axes -> (Line2D, Text, etc.)
#一個Figure對象可以包含多個子圖(Axes)，在matplotlib中用Axes對象表示一個繪圖區域，可以了解為子圖。
fig = plt.figure() #建立圖表fig
ax = fig.add_subplot(1, 1, 1) #在圖表fig中建立一個子圖ax
#繪制散列圖，前兩個參數表示x軸和y軸所要顯示的資料，s表示符号大小，c表示顔色，marker表示符号類型
#ax.scatter(group[:, 0], group[:, 1], s = 50, c = 'r', marker = 'o')
label = list(ones(2))+list(2*ones(2)) #定義4個元素的數組
#使用數組label中的值來改變s和c的值
ax.scatter(group[:, 0], group[:, 1], 15.0 * array(label), 15.0 * array(label), marker = 'o')
#設定坐标系x軸和y軸的上下限
ax.axis([0, 2, 0, 2])
ax.set_title('kNN_4_simple_group') #設定子圖的的标題
plt.xlabel('x_value')
plt.ylabel('y_value')
plt.savefig("kNN_4_simple_group.pdf")
plt.show()
散列圖的結果如下圖所示。兩個藍色點為A類，黃色點為B類。測試樣本[0.2, 0]應該為B類，這與K近鄰算法的分類結果一緻。
2.3 約會網站
這個執行個體中會對約會網站的使用者資訊進行分類，友善使用者選擇自己喜歡的約會對象。我們有1000個樣本，存儲在txt檔案datingTestSet2.txt中。每個樣本有4種資訊，分别為：每年獲得的飛行常客裡程數、玩視訊遊戲所耗時間百分比、每周消費的冰淇淋公升數和樣本分類。
由于樣本資料存儲在文本檔案中，需要先從檔案中讀出樣本資料。這裡使用函數file2matrix(filename)來完成這項任務。打開文本檔案，擷取到樣本個數，建立存儲所有樣本資訊的二維數組returnMat，同時建立一個清單classLabelVector用來存儲每個樣本的分類資訊。從文本檔案中讀取一行資料，将其分割，将前三項寫入二維數組returnMat，最後一項寫入classLabelVector。具體實作如下：
#從訓練樣本檔案中讀取樣本資訊，并将分類資訊與其他資料分别存儲在不同的數組中
def file2matrix(filename):
fd = open(filename)
numberOfLines = len(fd.readlines()) #擷取檔案中樣本的數目
#建立numberOfLinesx3的二維數組，并初始化為0；存儲從檔案中讀取的樣本資訊的前三列
returnMat = zeros((numberOfLines, 3))
classLabelVector = [] #定義存儲樣本類别的清單
fd = open(filename) #重新打開檔案，因為前面為了擷取樣本數目從檔案中讀取了所有樣本，檔案指針不在檔案最前面
index = 0
for line in fd.readlines(): #從檔案中循環讀取每一行資料進行處理
line = line.strip() #去掉這一行前面和後面的空格
listFromLine = line.split('\t') #将資料按空格分割，本示例中将所讀行資料分為4個獨立資料
returnMat[index, :] = listFromLine[0 : 3] #将前3個資料存儲到returnMat數組中
classLabelVector.append(int(listFromLine[-1])) #将最後一個資料，即第4個資料，轉換成int類型後存儲到classLabelVector最後面
index += 1
return returnMat, classLabelVector #returnMat存儲樣本前3列資料，classLabelVector存儲樣本對應的分類資訊
由于樣本中三個特征的機關不同，無法比較，需要将特征資訊歸一化。每個特征的歸一化按照這個公式來完成：newValue = (oldValue - min) / (max - min)
函數autoNorm()的輸入參數dataSet為Nx3的二維數組，存儲着N個樣本的特征值。通過函數min(0)/max(0)求得每一列，即每一種特征中最小值和最大值，然後算出特征範圍差。建立與參數dataSet結構完全一樣的數組并初始化為0，用來存儲歸一化結果。對二維數組dataSet中每一個減去該列的最小值，然後除以它們的特征範圍差，完成歸一化。
#對輸入數組進行歸一化數值處理，也叫特征縮放，用于将特征縮放到同一個範圍内
#本例的縮放公式為： newValue = (oldValue - min) / (max - min)
def autoNorm(dataSet): #輸入數組dataSet為Nx3的二維數組
minVals = dataSet.min(0) #擷取數組中每一列的最小值，minVals為1x3的數組；max(0)擷取每一行的最小值
maxVals = dataSet.max(0) #擷取數組中每一列的最大值，maxVals為1x3的數組；max(1)擷取每一行的最大值
ranges = maxVals - minVals #擷取特征範圍差，ranges也是1x3的數組
normDataSet = zeros(shape(dataSet)) #建立與dataSet的維數、類型完全一樣的數組，并初始化為0，用于存儲歸一化後的結果
m = dataSet.shape[0] #擷取輸入數組的行數
#tile(minVals, (m, 1))建立mx1的數組，數組元素為1x3的最小值數組，其傳回值為mx3的數組
#從原始數組的各個元素中，減去對應列的最小值
normDataSet = dataSet - tile(minVals, (m, 1))
#tile(ranges, (m, 1))建立mx1的數組，數組元素為1x3的特征範圍差，其傳回值為mx3的數組
#原始數組的各個元素除以對應列的特征範圍差，完成歸一化
normDataSet = normDataSet / tile(ranges, (m, 1))
return normDataSet, ranges, minVals #傳回歸一化後Nx3的數組、1x3的特征範圍差數組和1x3的每列最小值數組
歸一化後的資料就可以進行測試了。函數datingClassTest()完成測試工作。在該函數中，選擇所有樣本的前一半為測試樣例，後一半為訓練樣例。先調用函數file2matrix()從樣本檔案datingTestSet2.txt中讀出所有樣例資料。然後調用函數autoNorm()對樣例資料進行歸一化。對測試樣本從頭到尾，調用函數kNN.knnClassify()依次判斷其類别，然後跟真實的類别進行比對，記錄錯誤情況，算出錯誤率。
#根據訓練樣本datingTestSet2.txt中資料對kNN分類算法進行測試
def datingClassTest():
hoRatio = 0.50 #用于分割樣本，将檔案中擷取的樣本前面一半作為測試樣例，後面一半作為訓練樣例
#從樣本檔案datingTestSet2.txt中讀取所有樣例資料及分類資訊
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
#将樣本資料進行歸一化處理
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0] #擷取歸一化後二維數組的行數，即所有樣本的數目
numTestVecs = int(m * hoRatio) #擷取測試樣本的數目，為所有樣本的一半
errorCount = 0.0 #記錄分類錯誤的次數
for i in range(numTestVecs): #依次循環，從前一半樣本中獲得每一個樣本，跟後面一半樣本進行比對，尋找最近鄰樣本
classifierResult = kNN.knnClassify(normMat[i, :], normMat[numTestVecs : m, :], datingLabels[numTestVecs : m], 3)
#print "the classifier case back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): #如果分類結果與從檔案中讀取的值不一緻，則判為分類錯誤
errorCount += 1.0
print "the classifier case back with: %d, the real answer is: %d, index: %d" % (classifierResult, datingLabels[i], i)
print "the total error rate is: %f" % (errorCount / float(numTestVecs)) #列印出錯誤率
print errorCount #傳回錯誤次數
2.4 手寫體識别
這裡建構的手寫識别系統隻能識别數字0到9。需要識别的數字已經使用圖形處理軟體，處理成具有相同色彩和大小：寬高是32像素x32像素的黑白圖像。盡管采用文本格式存儲圖像不能有效地利用記憶體空間，但是為了友善了解，我們還是将圖像轉換為文本格式。
該執行個體中有兩個檔案夾存儲樣本檔案，目錄trainingDigits中包含了大約2000個例子，每個數字大約有200個樣本；目錄testDigits中包含了大約900個測試資料。我們使用目錄trainningDigits中的資料訓練分類器，使用目錄testDigits中的資料測試分類器的效果。
首先，需要讀取樣本檔案，将其轉換為1x1024的數組。在樣本檔案中存儲了32行32列的數字，來模拟圖像資料。函數img2vector(filename)從文本檔案中讀取其前32行，每一行讀取32個字元，将其轉換為整型數字，存儲在1x1024的數組中。
#将檔案中讀取的數字字元轉換為整型數字，存儲在一維數組中
def img2vector(filename):
returnVect = zeros((1, 1024)) #建立1x1024的一維數組，并初始化為0
#打開檔案從中讀取32行資料，并将每一行的32個byte轉化為整型數字
fd = open(filename)
for i in range(32):
lineStr = fd.readline() #讀取一行資料
for j in range(32):
returnVect[0, 32 * i + j] = int(lineStr[j]) #每個byte轉換為整型數字
return returnVect
函數handwritingClassTest()完成手寫識别工作。它從訓練樣本目錄trainingDigits讀取所有的樣本檔案，從檔案名稱中解析出每個樣本的類别，即0-9。然後打開檔案，讀取32x32的字元轉換成1x1024的一維數組儲存起來。
讀取測試樣本目錄testDigits下的測試樣本，同樣擷取樣本的類别以及樣本的内容。将測試樣本從第一個開始，調用函數kNN.knnClassify()依次與訓練樣本進行分類測試。統計分類錯誤的情況，算出錯誤率。
def handwritingClassTest():
hwLabels = [] #定義存儲訓練樣本類别标記的清單變量
#listdir(): 傳回指定的檔案夾包含的檔案或檔案夾的名字的清單。這個清單以字母順序。 它不包括 '.' 和'..' 即使它在檔案夾中。
#目錄trainingDigits下面存放着所有的訓練樣本檔案，listdir擷取這些檔案名将其存儲在清單變量trainingFileList中
trainingFileList = listdir('trainingDigits')
m = len(trainingFileList) #擷取檔案清單中的檔案個數
trainingMat = zeros((m, 1024)) #建立mx1024的二維數組且初始化為0，存儲訓練樣本的内容；每個樣本1024個byte
for i in range(m): #逐個從樣本檔案中讀取内容轉換成整型存儲在二維數組trainingMat中
fileNameStr = trainingFileList[i] #擷取第i個樣本的檔案名0_3.txt，表示數字0的第3個樣本檔案
fileStr = fileNameStr.split('.')[0] #擷取樣本檔案名稱0_3
classNumStr = int(fileStr.split('_')[0]) #擷取該樣本對應的數字類别，即0
hwLabels.append(classNumStr) #将樣本的數字類别存儲在清單變量hwLabels中
#将檔案trainingDigits/0_3.txt讀取出來，并将其内容轉換為整型數字存儲在二維數組trainingMat第i個元素中
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = listdir('testDigits') #測試樣本存放在testDigits目錄下，擷取測試樣本的檔案名清單
errorCount = 0.0
mTest = len(testFileList) #擷取測試樣本的個數
for i in range(mTest): #對測試樣本，逐個進行檢測
fileNameStr = testFileList[i] #擷取第i個測試樣本，如0_1.txt
fileStr = fileNameStr.split('.')[0] #擷取檔案名0_1
classNumStr = int(fileStr.split('_')[0]) #擷取樣本的數字類别0
#将檔案testDigits/0_1.txt讀取出來，并将其内容轉換為整型數字存儲在1x1024的數組vectorUnderTest中
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
#将vectorUnderTest與之前的訓練樣本逐一進行比較，擷取最近鄰的3個樣本，
#傳回這3個樣本中類别最多的那個類别，作為該測試樣本的類别
classifierResult = kNN.knnClassify(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 classifier came back with: %d, the real answer is: %d" \
% (classifierResult, classNumStr)
print "\nthe total number of errors is: %d" % errorCount #列印出錯誤數量
print "\nthe total error rate is: %f" % (errorCount / float(mTest)) #列印出錯誤率
3、小結
K近鄰算法是分類資料最簡單最有效的算法，這裡通過三個例子講述了如何使用K近鄰算法構造分類器。K近鄰算法是基于執行個體的學習，使用算法時我們必須有接近實際資料的訓練樣本資料。K近鄰算法必須儲存全部資料集，如果訓練資料集很大，必須使用大量的存儲空間。此外，由于必須對資料集中的每個資料計算距離值，實際使用時可能非常耗時。
本文中涉及的所有code可以通路如下目錄擷取：
https://github.com/stevewang0/MLInAction
（完）
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)