目錄
1. KNN算法原理
2. KNN算法三要素
3. KNN算法之暴力實現原理
4. KNN算法之KD樹實現原理
5. KNN算法之訓練樣本不平衡情況
6. 算法優缺點
KNN算法是選擇與輸入樣本在特徵空間內最近鄰的k個訓練樣本並根據一定的決策規則,給出輸出結果 。
決策規則:
分類任務:輸出結果為k個訓練樣本中佔大多數的類 。
回歸任務:輸出結果為k個訓練樣本值的平均值 。
如下圖的分類任務,輸出結果為w1類 。
K值的選擇、距離度量和分類決策規則是K近鄰算法的三個基本要素。當三個要素確定後,對於任何一個新的輸入實例,它所屬的Y值也確定了,本節介紹了三要素的含義。
1. 分類決策規則
KNN算法一般是用多數表決方法,即由輸入實例的K個鄰近的多數類決定輸入實例的類。這種思想也是經驗風險最小化的結果。
訓練樣本為(xi , yi)。當輸入實例為 x,標記為c,是輸入實例x的k近鄰訓練樣本集。
我們定義訓練誤差率是K近鄰訓練樣本標記與輸入標記不一致的比例,誤差率表示為:
因此,要使誤差率最小化即經驗風險最小,就要使(2.1)式右端的最大,即K近鄰的標記值儘可能的與輸入標記一致,所以多數表決規則等價於經驗風險最小化。
2. K值的選擇:
K取值較小時,模型複雜度高,訓練誤差會減小,泛化能力減弱;K取值較大時,模型複雜度低,訓練誤差會增大,泛化能力有一定的提高。
KNN模型的複雜度可以通過對噪聲的容忍度來理解,若模型對噪聲很敏感,則模型的複雜度高;反之,模型的複雜度低。為了更好理解模型複雜度的含義,我們取一個極端,分析K=1和K="樣本數"的模型複雜度。
由上圖可知,K=1時,模型輸出的結果受噪聲的影響很大。
由上圖可知,樣本數等於7,當K=7時,不管輸入數據的噪聲有多大,輸出結果都是綠色類,模型對噪聲極不敏感,但是模型太過簡單,包含的信息太少,也是不可取的。
通過上面兩種極端的K選取結果可知,K值選擇應適中,K值一般小於20,建議採用交叉驗證的方法選取合適的K值。
3. 距離度量
KNN算法用距離來度量兩個樣本間的相似度,常用的距離表示方法:
(1)、歐式距離
(2)、曼哈頓距離
(3)、閔可夫斯基距離
可以看出,歐式距離是閔可夫斯基距離在p=2時的特例,而曼哈頓距離是p=1時的特例 。
暴力搜索(brute-force search)是線性掃描輸入實例與每一個訓練實例的距離並選擇前k個最近鄰的樣本來多數表決,算法簡單,但是當訓練集或特徵維度很大時,計算非常耗時,故這種暴力實現原理是不可行的 。
kd樹是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構,構造kd樹相當於不斷用垂直於坐標軸的超平面將k維空間進行劃分,構成一系列的K維超矩形區域,kd樹省去了對大部分數據的搜索,大大的較少了計算量。
kd樹的KNN算法實現包括三部分:kd樹的構建,kd樹的搜索和kd樹的分類。
1. 構建kd樹
kd樹實質是二叉樹,其劃分思想與cart樹一致,即切分使樣本複雜度降低最多的特徵。kd樹認為特徵方差越大,則該特徵的複雜度亦越大,優先對該特徵進行切分 ,切分點是所有實例在該特徵的中位數。重複該切分步驟,直到切分後無樣本則終止切分,終止時的樣本為葉節點。
【例】給定一個二維空間的數據集:
構造kd樹的步驟:
(1)、數據集在維度和的方差分別為6.9和5.3,因此首先從維度進行切分。
(2)、 數據集在維度的中位數是7,以平面=7將空間分為左右兩個矩形。
(3)、分別對左右兩個矩形的樣本在維度的中位數進行切分。
(4)、重複步驟(2)(3),直到無樣本,該節點為葉子節點。
如下圖,綠色為葉子節點 ,紅色為節點和根節點。
2. KD樹搜索
(1)、搜索路徑從根節點到葉節點,在KD樹裡面找到包含目標點的葉子節點。
(2)、搜索路徑從葉節點到根節點,找到距離目標點最近的樣本實例點。過程不再複述,具體方法請參考李航博士《統計學習方法》。
3. KD樹預測
每一次搜尋與輸入樣本最近的樣本節點,然後忽略該節點,重複同樣步驟K次,找到與輸入樣本最近鄰的K個樣本 ,投票法確定輸出結果。
若正負樣本處於不平衡狀態,運用投票決策的KNN算法判斷輸入樣本的所屬類別:
結果顯示輸入樣本為綠色類 。原因是紅色類的個數遠遠小於綠色樣本,導致出現的分類錯誤 。
(1)若分類決策選擇限定半徑最近鄰法,即以輸入樣本為圓心,最大半徑R的圓內選擇出現次數最多的類做為輸入樣本的類 。如下圖,黑色樣本的分類結果正確。
(2)投票法是默認每個樣本的權重相等,我們假定權重與距離成反比,即距離越大,對結果的影響越小,那麼該樣本的權重也越小,反之,權重則越大,根據權重對輸入樣本進行分類 。這種思想與adaBoost算法相似,分類性能好的弱分類器給予一個大的權重 。
分類過程:
(1)、選擇與輸入樣本距離X0最近的K個訓練樣本Xi(i = 1,2,...,K),d(X0,Xi)表示輸入樣本和訓練樣本的距離。
(2)、根據距離與樣本成反比的性質將距離轉化成權重Wi,Wi表示輸入樣本X0與訓練樣本Xi的權重。
(3)、我們累加每一類的樣本權重,並認為該權重佔所有權重和的比例是該類的生成概率,概率最大的類就是輸入樣本的分類結果。
假設目標是二分類{C1,C2},表達式:
若,則分類結果為C1類,反之C2類。
回歸過程:
(1)(2)步驟與分類過程一直,第(3)步使用如下表達式得到回歸值:
其中,y為輸出結果,f(xi)為最近鄰樣本的值。若權重相同的話,則輸出結果為K個訓練樣本的平均值。
用權重思想重新對上例進行分類,可得輸入樣本為紅色類。
優點:
1)算法簡單,理論成熟,可用於分類和回歸。
2)對異常值不敏感。
3)可用於非線性分類。
4)比較適用於容量較大的訓練數據,容量較小的訓練數據則很容易出現誤分類情況。
5)KNN算法原理是根據鄰域的K個樣本來確定輸出類別,因此對於不同類的樣本集有交叉或重疊較多的待分樣本集來說,KNN方法較其他方法更為合適。
缺點:
1)時間複雜度和空間複雜度高。
2)訓練樣本不平衡,對稀有類別的預測準確率低。
3)相比決策樹模型,KNN模型可解釋性不強。
參考:
https://www.cnblogs.com/pinard/p/6061661.html