k 近鄰法（K-Nearest Neighbors Algorithm，k-NN）是一種基本分類與回歸方法，通過多數(shù)表決等方式進行預測，因此不具有顯式的學習過程。

k 近鄰算法

輸入：訓練數(shù)據(jù)集，其中是實例的特征向量，是實例的類別，；實例特征向量 ；

輸出：實例所屬的類

1. 根據(jù)給定的距離度量，在訓練集中找出與最近鄰的個點，涵蓋這點的的鄰域記作；

2. 在中根據(jù)分類決策規(guī)則決定的類別：
   

k 近鄰模型

k 近鄰法使用的模型實際上對應于特征空間的劃分。模型由三個基本要素——距離度量、k值的選擇和分類決策規(guī)則決定。

特征空間中，對每個訓練實例點，距離該點比其他點更近的所有點組成一個區(qū)域，叫做單元。下圖是二維特征空間劃分的一個例子。

距離度量

設特征空間是維實數(shù)向量空間，，的距離定義為

其中，。當時，稱為歐氏距離，即

當時，稱為曼哈頓距離，即

當時，是各個坐標距離的最大值，即

下圖給出了二維空間中取不同值時，與原點的距離為1的點的圖形：

k 值的選擇

如果選擇較小的k值：

• 學習的近似誤差減小，但學習的估計誤差增大
• 噪聲敏感
• 整體模型變復雜，容易發(fā)生過擬合

如果選擇較大的k值：

• 學習的估計誤差減小，但學習的近似誤差增大
• 整體模型變簡單

分類決策規(guī)則

多數(shù)表決規(guī)則：如果分類的損失函數(shù)為0-1損失函數(shù)，分類函數(shù)為

則誤分類的概率是

對給定的實例，其最近鄰的個訓練實例點構成的集合。如果涵蓋的區(qū)域的類別是，則誤分類率是

要使誤分類率最小即經(jīng)驗風險最小，就要使最大，所以多數(shù)表決規(guī)則等價于經(jīng)驗風險最小化。

k 近鄰法的實現(xiàn)：kd 樹

構造 kd 樹

平衡kd樹構造算法：
輸入：維空間數(shù)據(jù)集，其中；
輸出：kd樹

1. 開始：構造根結點，根結點對應于包涵的維空間的超矩形區(qū)域。
   選擇為坐標軸，以中所欲實例的坐標的中位數(shù)為切分點，將根結點對應的超矩形區(qū)域切分成兩個子區(qū)域。切分由通過切分點并與坐標軸垂直的超平面實現(xiàn)。
   由根結點生成深度為1的左、右子結點：坐子結點對應坐標小于切分點的子區(qū)域，右子結點對應于坐標大與切分點的子區(qū)域。
   將落在切分超平面上的實例點保存在跟結點。
2. 重復：對深度為j的結點，選擇為切分坐標軸，，以該結點的區(qū)域中所由實例的坐標的中位數(shù)為切分點，將該結點對應的超矩形區(qū)域切分為兩個子區(qū)域。切分由通過切分點并與坐標軸垂直的超平面實現(xiàn)。
   由根結點生成深度為的左、右子結點：坐子結點對應坐標小于切分點的子區(qū)域，右子結點對應于坐標大與切分點的子區(qū)域。
   將落在切分超平面上的實例點保存在跟結點。
3. 直到兩個子區(qū)域沒有實例存在時停止。

下面給出一個例子：

搜索 kd 樹

kd樹的最近鄰搜索算法：
輸入：kd樹；目標點；
輸出：的最近鄰。

1. 在kd樹中找出包含目標點的葉結點：從跟結點出發(fā)，遞歸地向下訪問kd樹。若目標點當前維的坐標小于切分點的坐標，則移動到左子結點，否則移動到右子結點。直到子結點為葉結點為止。
2. 以此葉結點為“當前最近點”。
3. 遞歸地向上回退，在每個結點進行以下操作：
   3.1 如果該結點保存的實例點比當前最近點距離目標點更近，則以該實例點為“當前最近點”。
   3.2 當前最近點一定存在于該結點一個子結點對應的區(qū)域。檢查該子結點的父結點的另一子結點對應的區(qū)域是否有更近的點。具體地，檢查另一子結點對應的區(qū)域是否與以目標點為球心、以目標點與“當前最近點”間的距離為半徑的超球體相交。
   如果相交，可能在另一個子結點對應的區(qū)域內存在距目標點更近的點，移動到另一個子結點。接著，遞歸地進行最近鄰搜索；
   如果不相交，向上回退。
4. 當回退到根結點時，搜索結束。最后的“當前最近點”即為的當前最近鄰點。

下面給出一個例子：