概述
k近鄰（k nearest neighbor）算法是一種監督算法，用于分類。它基本思想是計算新實例和訓練集元素的**距離**，找出k個最接近的實例（neighbor），統計它們所屬分類，次數最多的類別作為新實例的類別。
原理與步驟
監督算法可大致分成兩個步驟：訓練（train）和分類（classify）。從實現考慮還需要算法初始化過程。
本節的代碼為python風格的示意代碼，不能直接運行，可運行代碼參考zxml。
示意代碼
?
class KNearestNeighbor:
def __init__(...): pass
def train(...): pass
def classify(...): pass
訓練（train）
理論上k近鄰算法不需要訓練，可直接使用原始數據進行分類。
歸一化
數據的分類的量綱差別較大時，小量綱分類在計算的權重將被削弱。使用歸一化消除這種影響。方法如下：
x??=?(x???xmin)/(xmax???xmin)
預處理
將數據進行某種形式的處理可加快尋找k近鄰的速度，常用的處理方式有KD-Tree和Ball-Tree，前者對低維歐氏距離有效，后者對所有距離有效。
示意代碼
?
def train(self, X, C):
'''X,C分別代表實例和類別'''
?
# 實例數據歸一化，并保留數據備份
(self.X, self.C) = (normalize(X), C.copy())
?
# 可選，如果需要，則構建KD-Tree()
self.tree = KDTree()
self.tree.create(self.X)
分類（classify）
分類的大致步驟：找出k個近鄰 和*統計類別的次數* 。 分類的部分處理與訓練的處理向對應，如：
- 訓練對數據進行歸一化，則分類是也需要歸一化。
- 訓練使用如KD-Tree等方式進行處理，則分類使用對應的方法尋找k個近鄰。
示意代碼
?
def classify(self, x):
?
_x = normalize(x) # 將x歸一化
nearest = self.find_neighbors(_x) # 找出k個近鄰
freq = frequency(nearests) # 統計每個類型的次數
return freq.sorted()[-1] # 排序后，返回次數最多的類別
?
def find_neighbors(self, x):
'''尋找與x最接近的k個點'''
?
if self.tree == None: # 判斷是否使用了kd-tree
ds = self.distance(x, self.X) # 計算所有點的距離
indices = ds.argsort()[0:k] # 排序后，取前面k個
?
else:
indices = self.tree.find_neighbors(x, self.k)
?
# indices是k個近鄰的索引位置
return self.C[indices]
初始化（init）
初始化需要設置算法參數，如k的值，距離公式。
距離
實例之間的距離一般采用歐氏距離，但不排除使用其它的距離計算方法。歐氏距離：
d?=?∥x???y∥?=?√(∑(xi???yi)2)?≥?∥xi???yi∥
?
def __init__(self, k, distance=euclidean ):
(self.k, self.distance) = (k, distance)
scikit-learn
下面使用scikit-learn中的k近鄰算法分類的例子。
?
import numpy as np
from sklearn import neighbors
?
# 準備數據，分成A B兩類。A類在[0,0]附近，B類在[1,1]附近。
X = np.array([[0, 0.1], [-0.1, 0],
[0.1, 0.1], [0, 0],
[1, 1], [1.1, 1],
[1, 1.1], [1.1, 1.1]])
?
C = ['A','A','A','A','B','B','B','B']
?
# 初始化
clf = neighbors.KNeighborsClassifier(n_neighbors=3, weights="uniform")
?
# 訓練
clf.fit(X, C)
?
# 分類
c = clf.predict(np.array([[0.9,0.8]]))
print(c)
上面的例子可以將k近鄰算法分成三步，初始化、訓練和分類。初始化可設置參數，本文涉及到的參數有：
- n_neighbors: 指參數k
- weights: 指定數據分類的權重，歸一化 是其中的一個方式。
- algorithm: 該參數可設定使用kd-tree等方法。
- metric: 距離計算公式
參考資料