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