k 近鄰法 (k-NN) 是一種基於實例的學習方法，無法轉化為對參數空間的搜索問題（參數最優化 問題）。它的特點是對特徵空間進行搜索。除了k近鄰法，本章還對以下幾個問題進行較深入的討 論:
- 切比雪夫距離 的計算
- "近似誤差" 與“估計誤差" 的含義
- k-d樹搜索算法圖解
一、算法
輸入：訓練集 為實例特徵向 為實例的類別,
輸出：實例 所屬的類
設在給定距離度量下，涵蓋最近k個點的鄰域為
其中示性函數 為真為假
尋找使得函數 取得最大值的變量 也就是說, 看看距離 最近的k個點裡面哪一類別最多，以此作為輸出。
二、模型
根據模型的分類, k-NN模型屬於非概率模型。
觀察 可發現它與感知機不同的之處, 作為決策函數, 它並不需要任何未知參數（感知機需要確定W和b），直接從訓練集的數據得到輸出。
1. 距離度量
k-NN的基本思想是，特徵空間中的距離反映了兩個點的相似程度, 因此 “距離" 是作出分類判斷 的基本依據。向量空間 的距離有多種度量方式：
(1) 不同距離度量
一般形式是閔可夫斯基距離（ 範數）：
當p=1時, 稱為曼哈頓距離（ 範數）：
當p=2時，稱為歐幾里得距離（ 範數），也就是最常用的距離：:
<code>import math from itertools import combinations def L(x, y, p=2): # x1 = [1, 1], x2 = [5,1] if len(x) == len(y) and len(x) > 1: sum = 0 for i in range(len(x)): sum += math.pow(abs(x[i] - y[i]), p) return math.pow(sum, 1 / p) else: return 0 /<code>
下圖表示平面上A、B兩點之間不同的距離：
- 只允許沿著座標軸方向前進, 就像曼哈頓街區的出租車走過的距離
- 兩點之間直線最短, 通過勾股定理計算斜邊的距離
- 只剩下一個維度, 即最大的分量方向上的距離
可見p取值越大，兩點之間的距離越短。
(2) 問題：為什麼切比雪夫距離
其實這個問題等價於：為什麼 即 空間中的向量 它的切比雪 夫長度等於它的最大分量方向上的長度。
證明: 設
不妨設 即
注意：最大分量的長度唯一, 但最大分量可能並不唯 一,設有x^{(1)}, x^{(2)}, \ldots x^{(k)}等個分量的長度都等於\left|x^{(1)}\right|$
當 即 為 時
當 即 為非最大長度分量時
計算 的切比雪夫長度:
由於已知 等於0或1，且有k個分量結果為1, 所以
因此
即 得證。
以上證明參考
(3) 平面上的圓
在平面上的圖像:
如果圓形的定義是 “到某一點距離相等的曲線圍成的圖形" ，那麼在不同的距離度量下，圓形的形 狀可以完全不同。為何 正則化在平面上的等高線為同心正方形, 不就很容易理解嗎?
- k值選擇
李航老師書中引入了“近似誤差”和“估計誤差”兩個概念，但沒有給出具體定義。
這裡簡單總結一下：
右側兩項分別是 "估計誤差" 和 "近似誤差"
- 估計誤差：訓練集與無限數據集得到的模型的差距
- 近似誤差：限制假設空間與無限制假設空間得到的模型的差距 k值越小 單個樣本影響越大 模型越複雜 假設空間越大 近似誤差越小 (估計誤差 越大），容易過擬合;k值越大 單個樣本影響越小 模型越簡單 假設空間越小 近似誤差越大（估計誤差 越小），容易欠擬合。
一般通過交叉驗證來確定最優的 k 值。
- 決策規則
k 近鄰的決策規則就是 “多數表決" ，即少數服從多數, 用數學表達式表示為
等號左側為誤分類率，要是誤分類率最小，就要使得 最大, 即選擇集合 中最多的一類。
三、kd樹
kd 樹的結構
kd樹是一個二叉樹結構，它的每一個節點記載了 [特徵座標, 切分軸, 指向左枝的指針, 指向右枝的指針] 。 其中, 特徵座標是線性空間 中的一個點
切分軸由一個整數 表示, 這裡 是我們在 維空間中沿第 維進行一次分割。 節點的左枝和右枝分別都是 kd 樹, 並且滿足：如果 是左枝的一個特徵座標, 那麼 並且如果 是右 枝的一個特徵座標，那麼
給定一個數據樣本集 和切分軸 以下遞歸算法將構建一個基於該數據集的 kd 樹, 每一次循環制作一 個節點:
- 如果 記錄 中唯一的一個點為當前節點的特徵數據, 並且不設左枝和右枝。 指集合 中元素 . 的數量) 如果
- 如果 將 S 內所有點按照第 個座標的大小進行排序;選出該排列後的中位元素 (如果一共有偶數個元素, 則選擇中位左邊或右邊的元素, 左或右並無影響)，作為當前節點的特徵座標, 並且記錄切分軸 將 設為在 中所有排列在中位元素之前的元素; 設為在 中所有排列在中位元素後的元素;當前節點的左枝設為以 為數據集並且 為切分軸製作出的 樹; 當前節點的右枝設為以 為數據集並且 為切分軸製作出 的 kd 樹。再設 這裡, 我們想輪流沿著每一個維度進 行分割; 是因為一共有 個維度, 在 沿著最後一個維度進行分割之後再重新回到第一個維度。)
構造 kd 樹的例子
上面抽象的定義和算法確實是很不好理解，舉一個例子會清楚很多。首先隨機在 中隨機生成 13 個點作為我們的數據集。起始的切分軸 這裡 對應 軸, 而 對應 軸。
首先先沿 x 座標進行切分，我們選出 x 座標的中位點，獲取最根部節點的座標
並且按照該點的x座標將空間進行切分，所有 x 座標小於 6.27 的數據用於構建左枝，x座標大於 6.27 的點用於構建右枝。
在下一步中對應軸左右兩邊再按照軸的排序進行切分，中位點記裁於左右枝的節點。得到下面的樹，左邊的x 是指這該層的節點都是沿 x 軸進行分割的。
空間的切分如下
下一步中 對應 軸, 所以下面再按照 除標進行排序和切分,有
最後每一部分都只剩一個點，將他們記在最底部的節點中。因為不再有未被記錄的點，所以不再進行切分。
就此完成了 kd 樹的構造。
kd 樹上的 kNN 算法
給定一個構建於一個樣本生的 kd 樹, 下面的算法可以尋找距離某個點 最近的 個樣本。
- 設 為一個有 個空位的列表, 用於保存已搜尋到的最近點.
- 根據 的座標值和每個節點的切分向下搜素（也就是選，如果樹的節點是按照 進行切分，並且 的 座標小於 則向左枝進行搜索: 反之則走右枝）。
- 當達到一個底部節點時，將其標記為訪問過. 如果 裡不足 個點. 則將當前節點的特徵座標加人 如 果 L不為空並且當前節點 的特徵與 的距離小於 裡最長的距離，則用當前特徵音換掉 中離 最遠的點
- 如果當前節點不是整棵樹最頂而節點, 執行 下（1）：反之. 輸出 算法完成. （1） . 向上爬一個節點。如果當前 (向上爬之後的) 節點未管被訪問過, 將其標記為被訪問過, 然後執行 1和2：如果當前節點被訪 問過, 再次執行 (1)。 如果此時 裡不足 個點, 則將節點特徵加入 如果 中已滿 個點, 且當前節點與 的距離小於 裡最長的距離。 則用節點特徵豐換掉 中帝最遠的點。計算 和當前節點切分綫的距離。如果該距離大於等於 中距離 最遠的距離井且 中已有 個點。則在切分線另一邊不會有更近的點, 執行3: 如果該距離小於 中最遠的距離或者 中不足 個點, 則切分綫另一邊可能有更近的點, 因此在當前節點的另一個枝從 開始執行.
來看下面的例子：
首先執行1，我們按照切分找到最底部節點。首先，我們在頂部開始
和這個節點的 x軸比較一下，
ppp 的 x 軸更小。因此我們向左枝進行搜索：
這次對比 y 軸，
p 的 y 值更小，因此向左枝進行搜索：
這個節點只有一個子枝，就不需要對比了。由此找到了最底部的節點 (−4.6,−10.55)。
在二維圖上是
此時我們執行2。將當前結點標記為訪問過, 並記錄下 訪問過的節點就在二叉樹 上顯示為被劃掉的好了。
然後執行 3，不是最頂端節點。執行 (1)，我爬。上面的是 (−6.88,−5.4)。
執行 1，因為我們記錄下的點只有一個，小於k=3，所以也將當前節點記錄下，有 L=[(−4.6,−10.55),(−6.88,−5.4)]。再執行 2，因為當前節點的左枝是空的，所以直接跳過，回到步驟3。3看了一眼，好，不是頂部，交給你了，(1)。於是乎 (1) 又往上爬了一節。
1 說，由於還是不夠三個點，於是將當前點也記錄下，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)。當然，當前結點變為被訪問過的。
2又發現，當前節點有其他的分枝，並且經計算得出 p 點和 L 中的三個點的距離分別是 6.62,5.89,3.10，但是 p 和當前節點的分割線的距離只有 2.14，小於與 L 的最大距離：
因此，在分割線的另一端可能有更近的點。於是我們在當前結點的另一個分枝從頭執行 1。好，我們在紅線這裡：
要用 p 和這個節點比較 x 座標:
p 的x 座標更大，因此探索右枝 (1.75,12.26)，並且發現右枝已經是最底部節點，因此啟動 2。
經計算，(1.75,12.26)與 p 的距離是 7.48，要大於 p 與 L 的距離，因此我們不將其放入記錄中。
然後 3 判斷出不是頂端節點，呼出 (1)，爬。
1出來一算，這個節點與 p 的距離是 4.91，要小於 p 與 L 的最大距離 6.62。
因此，我們用這個新的節點替代 L 中離 p 最遠的 (−4.6,−10.55)。
然後 2又來了，我們比對 p 和當前節點的分割線的距離
這個距離小於 L 與 p 的最小距離，因此我們要到當前節點的另一個枝執行 1。當然，那個枝只有一個點，直接到 2。
計算距離發現這個點離 p 比 L 更遠，因此不進行替代。
3發現不是頂點，所以呼出 (1)。我們向上爬，
這個是已經訪問過的了，所以再來（1），
好，（1）再爬，
啊！到頂點了。所以完了嗎？當然不，還沒輪到 3 呢。現在是 1的回合。
我們進行計算比對發現頂端節點與p的距離比L還要更遠，因此不進行更新。
然後是 2，計算 p 和分割線的距離發現也是更遠。
因此也不需要檢查另一個分枝。
然後執行 3，判斷當前節點是頂點，因此計算完成！輸出距離 p 最近的三個樣本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)].
python
<code>class kdtree(object): # 創建 kdtree # point_list 是一個 list 的 pair，pair[0] 是一 tuple 的特徵，pair[1] 是類別 def __init__(self, point_list, depth=0, root=None): if len(point_list)>0: # 輪換按照樹深度選擇座標軸 k = len(point_list[0][0]) axis = depth % k # 選中位線，切 point_list.sort(key=lambda x:x[0][axis]) median = len(point_list) // 2 self.axis = axis self.root = root self.size = len(point_list) # 造節點 self.node = point_list[median] # 遞歸造左枝和右枝 if len(point_list[:median])>0: self.left = kdtree(point_list[:median], depth+1, self) else: self.left = None if len(point_list[median+1:])>0: self.right = kdtree(point_list[median+1:], depth+1, self) else: self.right = None # 記錄是按哪個方向切的還有樹根 else: return None # 在樹上加一點 def insert(self, point): self.size += 1 # 分析是左還是右，遞歸加在葉子上 if point[0][self.axis]/<code>
