k近鄰算法的介紹

k近鄰算法是一種基本的分類和回歸方法，這里只實現分類的k近鄰算法。

k近鄰算法的輸入為實例的特征向量，對應特征空間的點；輸出為實例的類別，可以取多類。

k近鄰算法不具有顯式的學習過程，實際上k近鄰算法是利用訓練數據集對特征向量空間進行劃分。將劃分的空間模型作為其分類模型。

k近鄰算法的三要素

下面對三要素進行一下說明：

1.歐氏距離即歐幾里得距離，高中數學中用來計算點和點間的距離公式；

2.k值選擇：k值選擇會對k近鄰法結果產生重大影響，如果選擇較小的k值，相當于在較小的鄰域中訓練實例進行預測，這樣有點是“近似誤差”會減小，即只與輸入實例較近（相似）的訓練實例才會起作用，缺點是“估計誤差”會增大，即對近鄰的實例點很敏感。而k值過大則相反。實際中取較小的k值通過交叉驗證的方法取最優k值。

3.k近鄰法的分類決策規則往往采用多數表決的方式，這等價于“經驗風險最小化”。

k近鄰算法的實現：kd樹

實現k近鄰法是要考慮的主要問題是如何退訓練數據進行快速的k近鄰搜索，當訓練實例數很大是顯然通過一般的線性搜索方式效率低下，因此為了提高搜索效率，需要構造特殊的數據結構對訓練實例進行存儲。kd樹就是一種不錯的數據結構，可以大大提高搜索效率。

本質商kd樹是對k維空間的一個劃分，構造kd樹相當與使用垂直于坐標軸的超平面將k維空間進行切分，構造一系列的超矩形，kd樹的每一個結點對應一個這樣的超矩形。

kd樹本質上是一棵二叉樹，當通過一定規則構造是他是平衡的。

下面是過早kd樹的算法：

以下是kd樹的python實現

準備工作

#讀取數據準備def file2matrix(filename):  fr = open(filename)  returnMat = []     #樣本數據矩陣  for line in fr.readlines():    line = line.strip().split('/t')    returnMat.append([float(line[0]),float(line[1]),float(line[2]),float(line[3])])  return returnMat  #將數據歸一化，避免數據各維度間的差異過大def autoNorm(data):  #將data數據和類別拆分  data,label = np.split(data,[3],axis=1)  minVals = data.min(0)   #data各列的最大值  maxVals = data.max(0)    #data各列的最小值  ranges = maxVals - minVals  normDataSet = np.zeros(np.shape(data))  m = data.shape[0]  #tile函數將變量內容復制成輸入矩陣同樣大小的矩陣  normDataSet = data - np.tile(minVals,(m,1))      normDataSet = normDataSet/np.tile(ranges,(m,1))  #拼接  normDataSet = np.hstack((normDataSet,label))  return normDataSet