機器學習中常常要用到分類算法，在諸多的分類算法中有一種算法名為k-近鄰算法，也稱為kNN算法。
一、kNN算法的工作原理
二、适用情況
三、算法執行個體及講解
---1.收集資料
---2.準備資料
---3.設計算法分析資料
---4.測試算法
一、kNN算法的工作原理
官方解釋：存在一個樣本資料集，也稱作訓練樣本集，并且樣本中每個資料都存在标簽，即我們知道樣本集中每一資料與所屬分類的對應關系，輸入沒有标簽的新資料後，将新資料的每個特征與樣本集中的資料對應的特征進行比較，然後算法提取樣本集中特征最相似的資料（最近鄰）的分類标簽。一般來說，我們隻選擇樣本集中前k個最相似的資料，這就是k-近鄰算法中k的出處，通常k是不大于20的整數，最後，選擇k個最相似的資料中出現次數最多的分類，作為新資料的分類。
我的了解：k-近鄰算法就是根據“新資料的分類取決于它的鄰居”進行的，比如鄰居中大多數都是榮民，那麼這個人也極有可能是榮民。而算法的目的就是先找出它的鄰居，然後分析這幾位鄰居大多數的分類，極有可能就是它本省的分類。
二、适用情況
優點：精度高，對異常資料不敏感（你的類别是由鄰居中的大多數決定的，一個異常鄰居并不能影響太大），無資料輸入假定；
缺點：計算發雜度高（需要計算新的資料點與樣本集中每個資料的“距離”，以判斷是否是前k個鄰居），空間複雜度高（巨大的矩陣）；
适用資料範圍：數值型（目标變量可以從無限的數值集合中取值）和标稱型（目标變量隻有在有限目标集中取值）。
三、算法執行個體及講解
例子中的案例摘《機器學習實戰》一書中的，代碼例子是用python編寫的（需要numpy庫），不過重在算法，隻要算法明白了，用其他語言都是可以寫出來的：
海倫一直使用線上約會網站尋找合适自己的約會對象。盡管約會網站會推薦不同的人選，但她沒有從中找到喜歡的人。經過一番總結，她發現曾交往過三種類型的人：1.不喜歡的人（以下簡稱1）；2.魅力一般的人（以下簡稱2） ；3.極具魅力的人（以下簡稱3）
盡管發現了上述規律，但海倫依然無法将約會網站推薦的比對對象歸入恰當的分類。她覺得可以在周一到周五約會哪些魅力一般的人，而周末則更喜歡與那些極具魅力的人為伴。海倫希望我們的分類軟體可以更好的幫助她将比對對象劃分到确切的分類中。此外海倫還收集了一些約會網站未曾記錄的資料資訊，她認為這些資料更有助于比對對象的歸類。
我們先提取一下這個案例的目标：根據一些資料資訊，對指定人選進行分類（1或2或3）。為了使用kNN算法達到這個目标，我們需要哪些資訊？前面提到過，就是需要樣本資料，仔細閱讀我們發現，這些樣本資料就是“海倫還收集了一些約會網站未曾記錄的資料資訊”。好的，下面我們就開始吧！
----1.收集資料
海倫收集的資料是記錄一個人的三個特征：每年獲得的飛行常客裡程數；玩視訊遊戲所消耗的時間百分比；每周消費的冰淇淋公升數。資料是txt格式檔案，如下圖，前三列依次是三個特征，第四列是分類（1：不喜歡的人，2：魅力一般的人，3：極具魅力的人），每一行代表一個人。
資料文檔的下載下傳連結是：http://pan.baidu.com/s/1jG7n4hS
----2.準備資料
何為準備資料？之前收集到了資料，放到了txt格式的文檔中了，看起來也比較規整，但是計算機并不認識啊。計算機需要從txt文檔中讀取資料，并把資料進行格式化，也就是說存到矩陣中，用矩陣來承裝這些資料，這樣才能使用計算機處理。
需要兩個矩陣：一個承裝三個特征資料，一個承裝對應的分類。于是，我們定義一個函數，函數的輸入時資料文檔（txt格式），輸出為兩個矩陣。
代碼如下：
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines())
returnMat = zeros((numberOfLines, 3))
classLabelVector = []
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
簡要解讀代碼：首先打開檔案，讀取檔案的行數，然後初始化之後要傳回的兩個矩陣（returnMat、classLabelsVector），然後進入循環，将每行的資料各就各位配置設定給returnMat和classLabelsVector。
----3.設計算法分析資料
k-近鄰算法的目的就是找到新資料的前k個鄰居，然後根據鄰居的分類來确定該資料的分類。
首先要解決的問題，就是什麼是鄰居？當然就是“距離”近的了，不同人的距離怎麼确定？這個有點抽象，不過我們有每個人的3個特征資料。每個人可以使用這三個特征資料來代替這個人——三維點。比如樣本的第一個人就可以用（40920， 8.326976， 0.953952）來代替，并且他的分類是3。那麼此時的距離就是點的距離：
A點(x1, x2, x3)，B點(y1, y2, y3)，這兩個點的距離就是：(x1-y1)^2+(x2-y2)^2+(x3-y3)^2的平方根。求出新資料與樣本中每個點的距離，然後進行從小到大排序，前k位的就是k-近鄰，然後看看這k位近鄰中占得最多的分類是什麼，也就獲得了最終的答案。
這個處理過程也是放到一個函數裡的，代碼如下：
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
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)
return sortedClassCount[0][0]
簡要解讀代碼：該函數的4個參數分别為新資料的三個特征inX、樣本資料特征集（上一個函數的傳回值）、樣本資料分類（上一個函數的傳回值）、k，函數傳回位新資料的分類。第二行dataSetSize擷取特征集矩陣的行數，第三行為新資料與樣本各個資料的內插補點，第四行取內插補點去平方，之後就是再取和，然後平方根。代碼中使用的排序函數都是python自帶的。
好了，現在我們可以分析資料了，不過，有一點不知道大家有沒有注意，我們回到那個資料集，第一列代表的特征數值遠遠大于其他兩項特征，這樣在求距離的公式中就會占很大的比重，緻使兩點的距離很大程度上取決于這個特征，這當然是不公平的，我們需要的三個特征都均平地決定距離，是以我們要對資料進行處理，希望處理之後既不影響相對大小又可以不失公平：
這種方法叫做，歸一化數值，通過這種方法可以把每一列的取值範圍劃到0~1或-1~1:，處理的公式為：
newValue = (oldValue - min)/(max - min)
歸一化數值的函數代碼為：
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
---4.測試算法
經過了格式化資料、歸一化數值，同時我們也已經完成kNN核心算法的函數，現在可以測試了，測試代碼為：
def datingClassTest():
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
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], 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))
通過測試代碼我們可以在回憶一下這個例子的整體過程：
- 讀取txt檔案，提取裡面的資料到datingDataMat、datingLabels；
- 歸一化資料，得到歸一化的資料矩陣；
- 測試資料不止一個，這裡需要一個循環，依次對每個測試資料進行分類。
代碼中大家可能不太明白hoRatio是什麼。注意，這裡的測試資料并不是另外一批資料而是之前的資料集裡的一部分，這樣我們可以把算法得到的結果和原本的分類進行對比，檢視算法的準确度。在這裡，海倫提供的資料集又1000行，我們把前100行作為測試資料，後900行作為樣本資料集，現在大家應該可以明白hoRatio是什麼了吧。
整體的代碼：
from numpy import *
import operator
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
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)
return sortedClassCount[0][0]
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines())
returnMat = zeros((numberOfLines, 3))
classLabelVector = []
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
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
def datingClassTest():
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
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], 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))
運作一下代碼，這裡我使用的是ipython：
最後的錯誤率為0.05。