統計學習方法 李航---第3章 k近鄰法
第3章 k近鄰法
k近鄰法(k-nearest neighbor, k-NN)是一種基本分類與迴歸方法。
k近鄰法假設給定一個訓練數據集，其
中的實例類別己定。分類時，對新的實例，根據其k個最近鄰的訓練實例的類別
經過多數表決等方式進行預測。k近鄰
法實際上利用訓練數據集對特徵向量空間進行劃分，並做爲其分類的「模型」。k
值的選擇、距離度量及分類決策規則是k近鄰法的三個基本要素。
3.1 k近鄰算法
3.2 k近鄰模型
k近鄰法三個基本要素：距離度量、k值的選擇和分類決策規則
距離度量:
經常使用
歐氏距離，其餘距離
Lp
距離(與distance)
當p=2時，稱爲歐氏距離(Euclidean distance)
當p=1時，稱爲曼哈頓距離(Manhattan distance )
Minkowski距離
k值的選擇
若是選擇較小的k值，「學
習」的近似偏差( approximation ertor)會減少，只有與輸入實例較近的(類似的)
訓練實例纔會對預測結果起做用。但缺點是「學習」的估計偏差(estimarion ertor)
會增大，預測結果會對近鄰的實例點很是敏感。若是鄰近的實例點恰巧是噪聲，
預測就會出錯.換句話說，k值的減少就意味着總體模型變得複雜，容易發生過
擬合。
若是選擇較大的k值，正好相反，
k值的增大
就意味着總體的模型變得簡單.
若是k=N，那麼不管輸入實例是什麼，都將簡單地預測它屬於在訓練實例
中最多的類。這時，模型過於簡單，徹底忽略訓練實例中的大量有用信息，是不
可取的.
在應用中，k值通常取一個比較小的數值.一般採用
交叉驗證法來選取最優
的k值.
分類決策規則
經常使用：多數表決規則(majority voting rule)：0-1
損失函數下
經驗風險最小化.
3.3 k近鄰法的實現:kd樹
kd樹
是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形
數據結構。kd樹是二叉樹，表示對k維空間的一個劃分(partition)。構造kd樹相
當於不斷地用垂直於座標軸的超平面將k維空間切分，構成一系列的k維超矩形區
域。kd樹的每一個結點對應於一個k維超矩形區域.
構造kd樹:
- 輸入：k維空間數據集
- 構造根結點，使根結點對應於k維空間中包含全部實
例點的超矩形區域；
-
經過下面的遞歸方法，不斷地對k維空間進行切分，生成子結點。在超矩形區域(結點)上選擇一個座標軸和在此座標軸上的一個切分點，確定一個超平面。這個超平面經過選定的切分點並垂直於選定的座標軸，將當前超矩形區域切分爲左右兩個子區域(子結點)；這時，實例被分到兩個子區域。
-
temp這個過程直到子區域內沒有實例時終止(終止時的結點爲葉結點)。在此過程當中，將實例保存在相應的結點上。
平衡kd樹構造
：
步驟 2中，
座標軸選擇：
對深度爲j的結點，選擇x(i)爲切分的座標軸，i = j(modk)+1；
切分點
選擇：選定座標軸上的中位
數(median)爲切分點。
平衡的kd樹搜索時
的效率未必是最優的.
搜索kd樹：
算法3.3(用kd樹的最近鄰搜索)
輸入: 已構造的kd樹:目標點x;
輸出x的最近鄰.
- 在kd樹中找出包含目標點x的葉結點:從根結點出發，遞歸地向下訪問kd樹.若目標點x當前維的座標小於切分點的座標，則移動到左子結點，不然移動到右子結點.直到子結點爲葉結點爲止.
- 以此葉結點爲「當前最近點」.
- 遞歸地向上回退，在每一個結點進行如下操做:
- 若是該結點保存的實例點比當前最近點距離目標點更近，則以該實例點爲「當前最近點「
- 當前最近點必定存在於該結點一個子結點對應的區域。檢查該子結點的父結點的另外一子結點對應的區域是否有更近的點。具體地，檢查另外一子結點對應的區域是否與以目標點爲球心、以目標點與「當前最近點」間的距離爲半徑的超球體相交。若是相交，可能在另外一個子結點對應的區域內存在距目標點更近的點，移動到另外一個子結點。接着，遞歸地進行最近鄰搜索。 若是不相交，向上回退。
- 當回退到根結點時，搜索結束最後的「當前最近點」即爲x的最近鄰點..
若是實例點是隨機分佈的，kd樹搜索的平均計算複雜度是O(log N)，這裏N
是訓練實例數。kd樹更適用於訓練實例數遠大於空間維數時的k近鄰搜索。當空
間維數接近訓練實例數時，它的效率會迅速降低，幾乎接近線性掃描。