先來一個簡單的例子，我們如何來區分動作類電影與愛情類電影呢？動作片中存在很多的打鬥鏡頭，愛情片中可能更多的是親吻鏡頭，所以我們姑且通過這兩種鏡頭的數量來預測這部電影的主題。簡單的說，k-近鄰算法採用了測量不同特徵值之間的距離方法進行分類。
優點：精度高、對異常值不敏感、無數據輸入假定 缺點：計算複雜度高、控件複雜度高 適用數據範圍：數值型和標稱型
首先我們來理解它的工作原理：
存在一個樣本數據集（訓練集），並且我們知道每一數據與目標變量的對應關係，輸入沒有標籤的新數據後，將新數據的每個特徵與樣本集中數據對應的特徵進行比較，然後算法提取樣本集中最相近的分類標籤，一般來說，我們只選擇樣本集中前k個最相似的數據，通常k為不大於20的整數，最後，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。
現在我們回到文章開頭所提到的電影的例子，根據下表如何確定未知的電影類型呢？
該如何計算電影7的電影類型呢？計算電影7與樣本集中其他電影的距離，然後我們假定k=3，看一下最近的3部電影是什麼類型即可預測出電影7的電影類型。
流程介紹
收集數據
準備數據：距離計算所需要的值，最好是結構化的數據格式
分析數據
測試算法：計算錯誤率
使用算法
開始工作
使用python導入數據
首先，創建名為kNN.py的Python模塊，在構造算法之前，我們還需要編寫一些通用的函數等，我們先寫入一些簡單的代碼：
from numpy import *import operatordef createDataSet(): group = array([ [1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1] ]) labels = ["A", "A", "B", "B"] return group, labels
然後將終端改變到代碼文件目錄，輸入命令python進入到交互界面：
>>> import kNN>>> group, labels = kNN.createDataSet()>>> group array([[ 1. , 1.1], [ 1. , 1. ], [ 0. , 0. ], [ 0. , 0.1]])>>> labels ['A', 'A', 'B', 'B']
這裡有4組數據，每組數據有2個我們已知的特徵值，上面的group矩陣每行為一條數據，對於每個數據點我們通常使用2個特徵（所以特徵的選擇很重要），向量labels包含了每個數據點的標籤信息，labels的維度等於矩陣的行數，這裡我們將[1, 1,1]定為類A，[0, 0.1]定為類B，接下來我們進行算法的編寫：
計算已知數據集中點到當前點之間的距離
按照距離遞增次序排序
選取與當前點距離最小的k個點
確定前k個點所在類別的出現頻率
返回前k個點中頻次最高的類別作為預測類別
接著定義函數：
# inX: 用於分類的輸入向量# dataSet：輸入的訓練集# labels：標籤向量# k：選擇近鄰項目的個數def classify0(inX, dataSet, labels, k) : dataSetSize = dataSet.shape[0] # 距離計算 diffMat = tile(inX, (dataSetSize, 1)) - dataSet sqDiffMat = diffMat ** 2 # python中, **2 代表2平方，**0.5代表開方 sqDistances = sqDiffMat.sum(axis=1) # 加入axis=1以後就是將一個矩陣的每一行向量相加 distances = sqDistances ** 0.5 sortedDistIndicies = distances.argsort() classCount = {} # 選擇距離最小的k個點 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) return sortedClassCount[0][0]
然後我們進行測試，重新打開python編譯環境：
>>> import kNN>>> group, labels = kNN.createDataSet()>>> kNN.classify0([0, 0], group, labels, 3)'B'>>> kNN.classify0([0.3, 0], group, labels, 3)'B'>>> kNN.classify0([0.8, 0.9], group, labels, 3)'A'
我們看到，一個簡單的分類器就這樣搞定了。這時，我們來將電影數據進行樣本寫入：
def createDataSet(): group = array([ [3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2] ]) labels = ["love", "love", "love", "action", "action", "action"] return group, labels
>>> import kNN>>> group, labels = kNN.createDataSet()>>> kNN.classify0([18, 90], group, labels, 3)'love'
我們看到預測結果為愛情片。這是一個簡單的分類器，當然，我們應該通過大量的測試，看預測結果與預期結果是否相同，進而得出錯誤率，完美的分類器錯誤率為0，最差的錯誤率為1，上邊電影分類的例子已經可以使用了，但是貌似沒有太大的作用，下邊我們來看一個生活中的實例，使用k-近鄰算法改進約會網站的效果，然後使用k-近鄰算法改進手寫識別系統。
改進約會網站的配對效果
有個姑娘，一直在使用某交友網站，但是推薦來的人總是不盡人意，她總結了一番，曾交往過3中類型的人：
不喜歡的人
魅力一般的人
極具魅力的人
她覺得自己可以在週一~週五約會那些魅力一般的人，週末與那些極具魅力的人約會，因為她希望我們可以更好的幫助她將匹配的對象劃分到確切的分類中，她還收集了一些約會網站未曾記錄過的數據信息，她認為這些數據信息會有幫助。這些數據存放在代碼文件夾下datingTestSet2.txt中，總共有1000行數據（妹的約了1000個人），主要包含以下特徵：
每年獲得的飛行常客里程數
玩視頻遊戲所消耗的時間百分比
每週消費的冰激凌公升數
我們看到，統計的東西都比較奇葩，我們先從文件中把這些數值解析出來，輸出訓練樣本矩陣和分類標籤向量。在kNN.py中繼續書寫代碼：
從文本中讀入數據
def file2matrix(filename) : fr = open(filename) arrayOfLines = fr.readlines() numberOfLines = len(arrayOfLines) # 得到文件行數 returnMat = zeros((numberOfLines, 3)) # 創建用0填充的矩陣，這裡為了簡化處理，我們將矩陣的另一個緯度設置為3，可以按照自己的需求增加數量。 classLabelVector = [] index = 0 # 解析文件 for line in arrayOfLines : line = line.strip() # 截取掉所有的回車字符 listFromLine = line.split('\t') returnMat[index, :] = listFromLine[0: 3] # range classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat, classLabelVector
>>> import kNN>>> mat, vector = kNN.file2matrix('datingTestSet2.txt')>>> mat, vector = kNN.file2matrix('datingTestSet2.txt')>>> mat array([[ 4.09200000e+04, 8.32697600e+00, 9.53952000e-01], [ 1.44880000e+04, 7.15346900e+00, 1.67390400e+00], [ 2.60520000e+04, 1.44187100e+00, 8.05124000e-01], ..., [ 2.65750000e+04, 1.06501020e+01, 8.66627000e-01], [ 4.81110000e+04, 9.13452800e+00, 7.28045000e-01], [ 4.37570000e+04, 7.88260100e+00, 1.33244600e+00]])>>> vec Traceback (most recent call last): File "<stdin>", line 1, in <module>NameError: name 'vec' is not defined>>> vector [3 ... 2]
現在我們已經從文文件中導入了數據，並將其格式化為想要的格式，接著我們需要了解數據的真是含義，我們可以直觀的瀏覽文本文件，但是這種方法非常不友好，一般來說，我們會採用圖形化的方式直觀的展示數據。下面我們就用Python圖形化工具來圖形化展示數據內容，以便辨識出一些數據模式。
分析數據，使用Matplotlib創建散點圖
pip install matplotlib
接下來打開python命令行，我們對剛才讀入的內容進行測試的展示
>>> from matplotlib import *>>> import matplotlib.pyplot as plt>>> import kNN>>> import numpy as np>>> mat, vec = kNN.file2matrix('datingTestSet2.txt')>>> fig = plt.figure()>>> ax = fig.add_subplot(111)>>> ax.scatter(mat[:, 1], mat[:, 2], 15.0*np.array(vec), 15.0*np.array(vec))<matplotlib.collections.PathCollection object at 0x1087cf0d0>>>> plt.show()
這個時候，我們展示的是數據集的第一列與第二列所繪製的圖，這裡我們很難看出來什麼端倪，所以我們嘗試使用第一列和第二列作為特徵來繪圖，重新書寫上邊代碼：
ax.scatter(mat[:, 0], mat[:, 1], 15.0*np.array(vec), 15.0*np.array(vec))
然後我們得到了以下數據圖：
這次，我們可以看到，圖中清晰的標識了3個不同的樣本分類區域。
準備數據，歸一化數值
我們隨便的抽取了4組差異比較大的數據
我們很容易發現，如果我們計算樣本3和樣本4之間的距離，可以使用下邊的方法
$\sqrt{(0-67)^2 + (20000 + 32000)^2 + (1.1-0.1)^2}$
但是這些大的值堆結果的影響比較大，因此，作為比較重要的特徵屬性，不應該如此的影響計算結果，所以在處理數據的時候，我們對數據進行歸一化處理，將取值的範圍處理到0 - 1或者-1 ~ -1之間，下面的公事，可以將任意範圍內的特徵值轉換為0-1區間內的值：
$newValue = (oldValue - min)/(max - min)$
其中，min和max分別為特徵值中最大和最小值，雖然改變數值範圍增加了分類器的複雜度，但是為了得到準確的結果，必須這樣做，所以我們在kNN.py中新增一個函數autoNorm()，用來將數字特徵值轉化為0-1的區間：
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)) return normDataSet, ranges, minvals
運行結果：
>>> import kNN>>> mat, vec = kNN.file2matrix('datingTestSet2.txt')>>> a, b, c = kNN.autoNorm(mat)>>> a array([[ 0.44832535, 0.39805139, 0.56233353], [ 0.15873259, 0.34195467, 0.98724416], [ 0.28542943, 0.06892523, 0.47449629], ..., [ 0.29115949, 0.50910294, 0.51079493], [ 0.52711097, 0.43665451, 0.4290048 ], [ 0.47940793, 0.3768091 , 0.78571804]])
這樣一來，我們把值處理成了我們預期的範偉內的值。
測試算法
通常我們把數據集的90%的數據當做訓練集，餘下的10%作為測試集，著10%的數據是隨機選擇的。 下面，我們來書寫測試程序，並通過datingTestSet.txt來測試程序：
def datingClassTest() : hoRatio = 0.10 # 設置抽取多少數據進行測試集 datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') # 讀入數據集 normMat, ranges, minVals = autoNorm(datingDataMat) # 轉化特徵值至 0 - 1 區間內 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], 3) # 使用近鄰算法得出結果 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))
然後我們在python環境中通過
reload(kNN)
來重新加載kNN.py模塊，然後調用
kNN.datingClassTest()
得到結果:
the classifier came back with: 3, the real answer is: 3 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 ... the classifier came back with: 3, the real answer is: 3 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 1 the total error rate is: 0.050000
所以我們看到，數據集的錯誤率是5%，這裡會有一定的偏差，因為我們隨機選取的數據可能會不同。
使用算法
我們使用上面建立好的分類器構建一個可用的系統，通過輸入這些特徵值幫她預測喜歡程度。我們來編寫代碼：
def classifyPerson() : resultList = ['not', 'small doses', 'large does'] percentTats = float(raw_input("percent of time spent on video games?")) miles = float(raw_input("flier miles per year?")) ice = float(raw_input("liters of ice-cream?")) datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') normMat, ranges, minVals = autoNorm(datingDataMat) inArr = array([miles, percentTats, ice]) classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3) print "you will like this person: ", resultList[classifierResult - 1]
這裡的代碼大家比較熟悉了，就是加入了raw_input用於輸入，我們來看結果：
>>> reload(kNN)
<module 'kNN' from 'kNN.py'>
>>> kNN.classifyPerson()
percent of time spent on video games?10
flier miles per year?10000
liters of ice-cream?0.5
you will like this person: small doses
我們在做近鄰算法的時候也發現，並沒有做訓練算法這一環節，因為我們不需要訓練，直接計算就好了。