### 一、KNN算法描述
KNN（K-nearest neighbor algorithm），也就是K近鄰算法，顧名思義，可以形象的理解為求K個最近的鄰居。當K=1時，KNN算法就成了最近鄰算法，即尋找最近的那個鄰居。
所謂K近鄰算法，就是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例（就是上面提到的K個鄰居），如果這K個實例的多數屬于某個類，就將該輸入實例分類到這個類中，如下圖所示。
在上圖中，有兩類不同的樣本數據，分別用正方形和三角形表示，而圖正中間的那個圓標示的數據則是待分類的數據。換句話說就是，我們不知道中間那個圓標示的數據是從屬于哪一類（是正方形還是三角形）？下面我們就要解決這個問題：給這個圓分類。
我們常說“物以類聚，人以群分”。判別一個人是一個什么樣品質特征的人常常可以從他身邊的朋友入手，所謂“觀其友，而識其人”。要判別上圖中那個圓是屬于哪一類數據？好，從它的鄰居下手。但是一次看多少個鄰居呢？
從圖中還能看出：如果K=3，圓的最近的3個鄰居是2個三角形和1個正方形，少數從屬于多數，基于統計的方法，判定圓標示的這個待分類數據屬于三角形一類。但是如果K=5，圓的最近的5個鄰居是2個三角形和3個正方形，還是少數從屬于多數，判定圓標示的這個待分類數據屬于正方形這一類。
由此我們可以看到，當無法判定當前待分類數據從屬于已知分類中的哪一類時，可以看它所處的位置特征，衡量它周圍鄰居的權重，而把它歸為權重更大的一類，這就是K近鄰算法分類的核心思想。
### 二、Python代碼實現
算法步驟：
（1）計算已知類別數據集中的點與當前點之間的距離；
（2）按照距離遞增依次排序；
（3）選取與當前點距離最小的K個點；
（4）確定前k個點所在類別的出現頻率；
（5）返回前k個點出現頻率最高的類別作為當前點的預測分類
~~~
kNN: k Nearest Neighbors
Input: inX: vector to compare to existing dataset (1xN)
dataSet: size m data set of known vectors (NxM)
labels: data set labels (1xM vector)
k: number of neighbors to use for comparison (should be an odd number)
Output: the most popular class label
from numpy import *
import operator
from os import listdir
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet #將inX重復成dataSetSize行1列，tile(A,n)，功能是將數組A重復n次，構成一個新的數組
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1) #sum(axis=1)就是將矩陣的每一行向量相加
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort() #argsort()得到的是排序后數據原來位置的下標
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]#確定前k個距離最小元素所在的主要分類labels
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#計算各個元素標簽的出現次數(頻率)，當voteIlabel在classCount中時，classCount.get()返回1，否則返回0
#operator.itemgetter(1)表示按照第二個元素的次序對元組進行排序，reverse=True表示為逆序排序，即從大到小排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0] #最后返回發生頻率最高的元素標簽
~~~
新建一個kNN.py文件，將上面的KNN的核心代碼加到里面，同時加入創建數據集函數createDataSet():
~~~
#創建數據集和標簽
def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
return group, labels
~~~
K-近鄰算法：帶有四個數據點的簡單例子
上圖的實現代碼是Matlab實現的，因為是Python新手，繪制帶標簽A，B的圖還不會，所以只要用強大的Matlab來實現了。
~~~
x=[1,1,0,0];
y=[1.1,1,0,0.1];
L={'A','A','B','B'}; %4個標注
plot(x,y,'.'); %畫4個點
axis([-0.2 1.2 -0.2 1.2])
for ii=1:4
text(x(ii)+0.01,y(ii)+0.01,L{ii}); %利用4個點的坐標添加對應標注
%適當增加一些距離，讓文字和點分開會美觀一些
end
figure(gcf);
~~~
預測數據所在分類的測試：
~~~
>>> kNN.classify0([0,0],group,labels,3)
'B'
>>> kNN.classify0([1,0],group,labels,3)
'B'
>>> kNN.classify0([2,2],group,labels,3)
'A'
~~~
參考文獻：
1.July.《編程之法.面試和算法心得》
2.Peter Harrington.《Machine Learning in Action》
