kNN(K 鄰近算法)主要根據特征之間的距離來進行分類的。為監督學習算法。
工作原理：
訓練資料（tranningdata）：每條資料都有标簽（知道所屬的類），一個标簽代表一類。
測試資料（testingdata）：把新資料（無标簽）的每一個特征與樣本集中資料對應的特征進行比較，然後提取與訓練資料集最相似的（最鄰近）的分類标簽。
最後提取樣本資料集中前K個最相似的資料（kNN的出處）和K 一般小于20的整數。在K個資料中，出現最多的标簽作為該資料的标簽。
維基百科的解釋：
k近鄰算法例子。測試樣本（綠色圓形）應歸入要麼是第一類的藍色方形或是第二類的紅色三角形。如果k=3（實線圓圈）它被配置設定給第二類，因為有2個三角形和隻有1個正方形在内側圓圈之内。
如果k=5（虛線圓圈）它被配置設定到第一類（3個正方形與2個三角形在外側圓圈之内）。
步驟：
對于未知類屬性集中每一個點依次執行以下操作：
1 計算已知類中的點與目前點之間的距離
2 按照距離遞增的次序排序
3 選取與目前點距離最小的k個點
4 确定前k個點所在的類别出現的頻率
5 傳回前k個點中出現頻率最高的類作為目前點的預測分類
主要代碼：
def classify0(inX,dataSet,labels,k):
dataSetSize=dataSet.shape[0];
diffMat=tile(inX,(dataSetSize,1))-dataSet;
sqDiffMax=diffMat**2;
sqDistance=sqDiffMax.sum(axis=1);
distance=sqDistance**0.5;
sorteDistIndicies=distance.argsort();
classCount={};
print (sorteDistIndicies[1])
for i in range(k):
voteIlabel=labels[sorteDistIndicies[i]];
classCount[voteIlabel]=classCount.get(voteIlabel,0)+1;
sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True);
return sortedClassCount[0][0]; 效果判斷
分類器的錯誤率=分類器給出的錯誤結果的次數/測試實行的總數。例如有10資料，2個分錯了。錯誤率為: 2/10=0.2；完美分類器錯誤率為0.最差分類器效果為0.
結果讨論:
起初，随着k的增長，k近鄰分類器的效果逐漸提升;當k增大到某一個點後，随着k的增大，k近鄰分類器性能逐漸下降。還可以說，k的增大，偏差逐漸增大而方差逐漸減少。
K的選擇
在投票時使用距離權重(distanceweighting)可一定程度上回避給問題。訓練資料集與待分類執行個體的距離越近，其權重越大。
優點：
精度高，對異常值不敏感，無資料輸入假定。
注：
異常值（outlier）：一組測定值與平均值的偏差超過兩倍标準的測定值。與平均值超過三倍标準差的測定值為高度異常的異常值。
缺點：
計算複雜度高，空間複雜度高
必須儲存全部的資料集。如果資料集大将使用大量記憶體空間。
必須對資料集中每個資料計算距離值，耗時
無法給出任何資料的基礎結構資訊。
當維數比較多時産生維數災（feature selection和PCA可以解決）
計算距離的方法
1.歐式距離(Euclidean Distance)
歐氏距離是最易于了解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。
二維平面上兩點a（x1,y1）與b(x2,y2)之間的歐式距離：
兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離：
也可以變事成向量運算的形式:
2. 曼哈頓距離(Manhattan Distance)
從名字就可以猜出這種距離的計算方法了。想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區距離(City Block distance)。
(1)二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離
(2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的曼哈頓距離
3. 切比雪夫距離 ( Chebyshev Distance )
國際象棋玩過麼？國王走一步能夠移動到相鄰的8個方格中的任意一個。那麼國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會發現最少步數總是max( | x2-x1 | , | y2-y1 | ) 步。有一種類似的一種距離度量方法叫切比雪夫距離。
(1)二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離
(2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的切比雪夫距離
這個公式的另一種等價形式是
用放縮法和夾逼法則來證明兩個公式是等價的
4. 闵可夫斯基距離(Minkowski Distance)
闵氏距離不是一種距離，而是一組距離的定義。
(1) 闵氏距離的定義
兩個n維變量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的闵可夫斯基距離定義為：
其中p是一個變參數。
當p=1時，就是曼哈頓距離
當p=2時，就是歐氏距離
當p→∞時，就是切比雪夫距離
根據變參數的不同，闵氏距離可以表示一類的距離。
(2)闵氏距離的缺點
闵氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。
舉個例子：二維樣本(身高,體重)，其中身高範圍是150~190，體重範圍是50~60，有三個樣本：a(180,50)，b(190,50)，c(180,60)。那麼a與b之間的闵氏距離（無論是曼哈頓距離、歐氏距離或切比雪夫距離）等于a與c之間的闵氏距離，但是身高的10cm真的等價于體重的10kg麼？是以用闵氏距離來衡量這些樣本間的相似度很有問題。
簡單說來，闵氏距離的缺點主要有兩個：(1)将各個分量的量綱(scale)，也就是“機關”當作相同的看待了。(2)沒有考慮各個分量的分布（期望，方差等)可能是不同的。
5. 标準化歐氏距離 (Standardized Euclidean distance )
标準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。标準歐氏距離的思路：既然資料各維分量的分布不一樣，好吧！那我先将各個分量都“标準化”到均值、方差相等吧。均值和方差标準化到多少呢？這裡先複習點統計學知識吧，假設樣本集X的均值(mean)為m，标準差(standard deviation)為s，那麼X的“标準化變量”表示為（樣本集的标準化過程(standardization)用公式描述）：
标準化後的值 = ( 标準化前的值 －分量的均值 ) /分量的标準差（也叫歸一化）
經過簡單的推導就可以得到兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的标準化歐氏距離的公式：
如果将方差的倒數看成是一個權重，這個公式可以看成是一種權重歐氏距離(Weighted Euclidean distance)。
6. 馬氏距離(Mahalanobis Distance)
(1）馬氏距離定義
有M個樣本向量X1~Xm，協方差矩陣記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：
而其中向量Xi與Xj之間的馬氏距離定義為：
若協方差矩陣是機關矩陣（各個樣本向量之間獨立同分布）,則公式就成了：
也就是歐氏距離了。
若協方差矩陣是對角矩陣，公式變成了标準化歐氏距離。
(2)馬氏距離的優缺點：量綱無關，排除變量之間的相關性的幹擾。
7. 夾角餘弦(Cosine)
幾何中夾角餘弦可用來衡量兩個向量方向的差異，機器學習中借用這一概念來衡量樣本向量之間的差異。
(1)在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角餘弦公式：
(2) 兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角餘弦
類似的，對于兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用類似于夾角餘弦的概念來衡量它們間的相似程度。
即：
夾角餘弦取值範圍為[-1,1]。夾角餘弦越大表示兩個向量的夾角越小，夾角餘弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角餘弦取最大值1，當兩個向量的方向完全相反夾角餘弦取最小值-1。
8. 漢明距離(Hamming distance)
兩個等長字元串s1與s2之間的漢明距離定義為将其中一個變為另外一個所需要作的最小替換次數。例如字元串“1111”與“1001”之間的漢明距離為2。
應用：資訊編碼（為了增強容錯性，應使得編碼間的最小漢明距離盡可能大）。
9. 傑卡德相似系數(Jaccard similarity coefficient)
(1) 傑卡德相似系數
兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的傑卡德相似系數，用符号J(A,B)表示。
傑卡德相似系數是衡量兩個集合的相似度一種名額。
(2) 傑卡德距離
與傑卡德相似系數相反的概念是傑卡德距離(Jaccard distance)。傑卡德距離可用如下公式表示：
傑卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度。
(3) 傑卡德相似系數與傑卡德距離的應用
可将傑卡德相似系數用在衡量樣本的相似度上。
樣本A與樣本B是兩個n維向量，而且所有次元的取值都是0或1。例如：A(0111)和B(1011)。我們将樣本看成是一個集合，1表示集合包含該元素，0表示集合不包含該元素。
p ：樣本A與B都是1的次元的個數
q ：樣本A是1，樣本B是0的次元的個數
r ：樣本A是0，樣本B是1的次元的個數
s ：樣本A與B都是0的次元的個數
那麼樣本A與B的傑卡德相似系數可以表示為：
這裡p+q+r可了解為A與B的并集的元素個數，而p是A與B的交集的元素個數。
而樣本A與B的傑卡德距離表示為：
10. 相關系數 ( Correlation coefficient )與相關距離(Correlation distance)
(1) 相關系數的定義
相關系數是衡量随機變量X與Y相關程度的一種方法，相關系數的取值範圍是[-1,1]。相關系數的絕對值越大，則表明X與Y相關度越高。當X與Y線性相關時，相關系數取值為1（正線性相關）或-1（負線性相關）。
(2)相關距離的定義
11. 資訊熵(Information Entropy)
資訊熵是衡量分布的混亂程度或分散程度的一種度量。分布越分散(或者說分布越平均)，資訊熵就越大。分布越有序（或者說分布越集中），資訊熵就越小。
計算給定的樣本集X的資訊熵的公式：
參數的含義：
n：樣本集X的分類數
pi：X中第i類元素出現的機率
資訊熵越大表明樣本集S分類越分散，資訊熵越小則表明樣本集X分類越集中。。當S中n個分類出現的機率一樣大時（都是1/n），資訊熵取最大值log2(n)。當X隻有一個分類時，資訊熵取最小值0
文獻
機器學習經典算法詳解及Python實作--K近鄰(KNN)算法
機器學習（Peter Flach）