第三章 k近鄰法
文章目錄
- 第三章 k近鄰法
-
- 3.1 k近鄰算法
- 3.2 k近鄰模型
-
- 3.2.1 模型
- 3.2.2 距離度量
- 3.2.3 K值的選擇
- 3.2.4 分類決策規則
- 3.3 k近鄰法的實作：kd樹
-
- 3.3.1 構造 k d kd kd樹
- 3.3.2 搜尋 k d kd kd 樹
k近鄰法(k-nearnest neighbor, K-NN)是一種基本分類與回歸方法.
- 對于輸入的執行個體，k近鄰法通過多數表決等方式進行預測，故其不具有顯式的學習過程;
- 三個基本要素是：K值的選擇、距離度量及分類決策準則.
3.1 k近鄰算法
算法 3.1(k近鄰法)
輸入: 訓練資料集
T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} T=(x1,y1),(x2,y2),...,(xN,yN)
其中， x i ∈ X ⊆ R n x_i \in X \subseteq \mathbb{R}^n xi∈X⊆Rn 為執行個體的特征向量， y i ∈ Y = c 1 , c 2 , . . . , c k y_i \in Y = {c_1,c_2,...,c_k} yi∈Y=c1,c2,...,ck 為執行個體的類别， i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N , 執行個體特征向量 x x x.
輸出: 執行個體 x x x所屬的類 y y y.
(1) 根據給定的距離度量，在訓練集 T T T中找出與 x x x最鄰近的 k k k個點，涵蓋這個點的 x x x的鄰域記作 N k ( x ) N_k(x) Nk(x):
(2) 在 N k ( x ) N_k(x) Nk(x)中根據分類規則(如多數表決)決定 x x x的類别 y y y：
y = a r g max c j ∑ x i ∈ N k ( x ) I ( y i = c j ) , i = 1 , 2 , . . . , N ; j = 1 , 2 , . . . , K y=arg \max \limits_{c_j} \sum \limits_{x_i \in N_k(x)}I(y_i=c_j), i=1,2,...,N; j=1,2,...,K y=argcjmaxxi∈Nk(x)∑I(yi=cj),i=1,2,...,N;j=1,2,...,K
其中， I I I為訓示函數，即當 y i = c j y_i=c_j yi=cj 時 I = 1 I=1 I=1，否則 I = 0 I=0 I=0.
3.2 k近鄰模型
k近鄰法使用的模型實際上對應于特征空間的劃分
3.2.1 模型
- k近鄰法中，當其三要素基本确定後，對于一個新的輸入執行個體，它所屬的類唯一地确定.
- k近鄰法分類類似于将特征空間劃分為一些子空間，确定子空間的每個點所屬的類
3.2.2 距離度量
特征空間中兩個執行個體點的距離是兩個執行個體點相似程度的反映.距離計算有以下幾種方法:
- 歐氏距離
- L p L_p Lp距離( L p L_p Lp distance)
- Minkowski距離(Minkowski distance)
L p L_p Lp距離
L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p , ( p ≥ 1 ) L_p(x_i,x_j)=(\sum \limits_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}},(p \geq 1) Lp(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣p)p1,(p≥1)
- p = 2 p=2 p=2時，稱為歐氏距離(Euclidean distance)
- 當 p = 1 p=1 p=1時，稱為曼哈頓距離(Manhattan distance)
- 當 p = ∞ p=\infty p=∞時，它是各個坐标距離的最大值
3.2.3 K值的選擇
k值的選擇會對k近鄰法的結果産生重大影響.
- k值較小，相當于選擇較小的鄰域中的訓練執行個體進行預測，學習的近似誤差(approximation error)會減小，但是估計誤差(estimation error)會增大.即k值的減小就意味着整體模型變的複雜，容易發生過拟合;
- k值較大，相當于用較大的訓練執行個體進行預測，可以減少學習的估計誤差，但是近似誤差會增大.即k值的增大意味着整體的模型變的簡單.
在應用中，k值一般取一個比較小的數值.通常采用交叉驗證法來選取最優的k值.
3.2.4 分類決策規則
一般是多數表決，即由輸入執行個體的k個鄰近的訓練執行個體中的多數類決定輸入執行個體的類.
3.3 k近鄰法的實作：kd樹
實作k近鄰法時，主要考慮的問題是如何對訓練資料進行快速k近鄰搜尋
- 簡單地實作方法是線性掃描(linear scan)，計算輸入執行個體與每一個訓練執行個體的距離. 在訓練集很大時，計算十分耗時
- k d kd kd 樹( k d kd kd tree)方法
3.3.1 構造 k d kd kd樹
k d kd kd 樹是一種對 k k k維空間中的空間進行存儲以便對其進行快速檢索的樹形資料結構，是一種二叉樹
構造 k d kd kd 樹的算法如下所示：
算法3.2 (構造平衡 k d kd kd樹)
輸入: k k k 維空間資料集 T = x 1 , x 2 , . . . , x N T={x_1,x_2,...,x_N} T=x1,x2,...,xN, 其中 x 1 = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( k ) ) , i = 1 , 2 , . . . , N x_1=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)}), i=1,2,...,N x1=(xi(1),xi(2),...,xi(k)),i=1,2,...,N
輸出: k d kd kd 樹
(1) 開始：構造根節點，根節點對應于包含 T T T 的 k k k 維空間的矩形區域.
選擇 x ( i ) x^{(i)} x(i) 為坐标軸，以 T T T 中所有執行個體的 x ( i ) x^{(i)} x(i) 坐标的中位數為切分點，将根節點對應的超矩形區域切分為兩個子區域.切分由通過切分點并與坐标軸 x ( i ) x^{(i)} x(i) 垂直的超平面實作.
由根節點生成深度為1的左、右子節點；左子節點對應坐标 x ( l ) x^{(l)} x(l) 小于切分點的子區域，右子節點對應與坐标 x ( i ) x^{(i)} x(i) 大于切分點的值區域.
将落在切分超平面上的執行個體點儲存在根節點.
(2) 重複：對深度為 j j j的結點，選擇 x ( i ) x^{(i)} x(i) 為切分的坐标軸， l = j ( m o d k ) + 1 l=j(mod k)+1 l=j(modk)+1，以該結點的區域中所有執行個體的 x ( i ) x^{(i)} x(i) 坐标的中位數為切分點，将該結點對應的超矩形區域切分為兩個子區域.切分由通過切分點并與坐标軸 x ( i ) x^{(i)} x(i) 垂直的超平面實作.
由該結點生成深度為 j + 1 j+1 j+1的左、右子結點，左子結點對應于坐标 x ( i ) x^{(i)} x(i)小于切分點的子區域，右子結點對應坐标 x ( i ) x^{(i)} x(i)大于切分點的子區域.
将落在切分超平面上的執行個體點儲存在該結點.
(3) 直到兩個子區域沒有執行個體存在時停止，進而形成 k d kd kd樹的區域劃分.
3.3.2 搜尋 k d kd kd 樹
使用 k d kd kd樹可以省去對大部分資料點的搜尋，進而減少搜尋的計算量.