K近鄰算法(KNN)原理小結

2021-02-19 深度學習初學者

目錄

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

相關焦點

  • 鳶尾花-k近鄰預測算法
    環境介紹散點圖源碼數據集數據結構散點圖k近鄰算法k近鄰源碼輸出結果結論注意環境
  • 復現經典:《統計學習方法》第 3 章 k 近鄰法
    代碼目錄代碼參考:,,第 3 章 k 近鄰法1.k 個最近鄰點。)): max_index = knn_list.index(max(knn_list, key=lambda x: x[0])) dist = np.linalg.norm(X - self.X_train[i], ord=self.p) if knn_list[max_index][0] > dist:
  • 從零開始學Python【33】--KNN分類回歸模型(實戰部分)
    >指定近鄰樣本的搜尋算法,如果為』ball_tree』,則表示使用球樹搜尋法尋找近鄰樣本;如果為』kd_tree』,則表示使用KD樹搜尋法尋找近鄰樣本;如果為』brute』,則表示使用暴力搜尋法尋找近鄰樣本。
  • 小白學數據:教你用Python實現簡單監督學習算法
    監督學習算法會從數據集中學習得出訓練樣本和其目標變量之間的關係,然後將學習到的關係對新樣本(未被標記的樣本)進行分類。為了闡明監督學習的工作原理,我們用根據學生學習時間預測其考試成績的例子來說明。為了獲得更高的精度,最好的方法是測試多個不同的算法,同時,對每個算法嘗試不同的參數。可以通過交互檢驗選擇最好的算法和參數。對於給定問題,在選取算法時,算法的精度、訓練時間、線性、參數數目以及特殊情況都要考慮在內。在IRIS數據集上實現sklearn中的KNN,並對給定的輸入進行花卉類型分類。首先,要應用機器學習算法,我們需要了解給定數據集的組成。
  • 怎麼使用k-fold cross validation(k-摺疊交叉驗證)
    介紹這個非常重要的概念,希望在訓練算法時能幫助各位。
  • 一個項目帶你進入機器學習算法--預測心臟病(二)
    訓練數據模型    sklearn.linear_model.LogisticRegression().fit(X_train, y_train)K-nearest neighbors(K-鄰值算法)在sklearn庫中,KNeighborsClassifier是實現K近鄰算法的一個類,一般都使用歐式距離進行測量
  • R VS Python —— KNN
    https://www.zhihu.com/people/wu-shu-hao-67/activities往期回顧本文的主要內容就是針對經典的Breast Cancer Wisconsin (Diagnostic)數據,分別通過R和Python兩種語言去實現KNN分類算法
  • 【Python破解九宮格數獨】:knn 數字識別
    4.把處理完的數字圖片保存到對應數字的文件夾中。(此為中間過程,可注釋掉)        number_path1 = "number\\%s\\%d" % (str(i+1),k) + '.jpg'        j = i+6        if j ==10:            j = 0        number_path2 = "number\\%s\
  • 雙邊濾波算法的原理、流程、實現及效果
    ];x=-T:T;y1=exp(-x.^2/(2*Delta*Delta));plot(x,y1,'--b','LineWidth',2);hold on;for k=2:7 y2= cos(Gamma .* x/ (Rho * sqrt(k))).
  • R語言時間序列預測模型:ARIMA vs KNN
    4KNN 回歸我們將使用tsfknn包,它可以用來預測R語言中的時間序列。KNN回歸過程由以下元素組成:下面是一個例子來理解這些組件和過程。library(tsfknn)pred = knn_forecasting(a10, h = 6, lags = 1:12, k = 3)autoplot(pred, highlight = "neighbors", faceting = TRUE)
  • 支持向量機(SVM)原理小結(1)線性支持向量機
    目錄SVM系列文章:支持向量機(SVM)原理小結(1)線性支持向量機 https://blog.csdn.net/u010366748/article/details/112852999支持向量機(SVM)原理小結(2)非線性支持向量機 https://blog.csdn.net/u010366748/article/details/113065986支持向量機(SVM)原理小結(3)支持向量回歸SVR https:
  • 機器學習算法一覽(附python和R代碼)
    我也會寫下對於各種機器學習算法的一些個人理解,並且提供R和Python的執行代碼。讀完這篇文章,讀者們至少可以行動起來親手試試寫一個機器學習的程序。不過,這篇文章並沒有闡述這些算法背後的統計學原理,有時候從實踐入手也是很好的學習路徑。如果你希望了解的是這些統計學原理,那麼這篇文章的內容可能並不適合你。一般說來,機器學習有三種算法:1.
  • 高斯混合模型與EM算法的數學原理及應用實例
    GMM是典型的概率圖模型  , GMM與其變種k-means(k均值)算法都是工業實踐中經常使用的聚類工具.EM算法通過迭代地構造似然函數下限的方式不斷地提升似然函數的取值, 從而完成對含有隱變量模型的參數估計, 其典型的應用包括GMM、HMM(Hidden Markov Model, 隱馬爾可夫模型)  的參數估計. 本文將從一個問題實例出發, 引出使用GMM和EM算法對問題進行解決的思路, 闡述其背後的數學原理, 最後給出完整的解決方案.
  • 技術乾貨 | 一文詳解高斯混合模型原理
    本文對該方法的原理進行了通俗易懂的講解,期望讀者能夠更直觀地理解方法原理。文本的最後還分析了高斯混合模型與另一種常見聚類算法K-means的關係,實際上在特定約束條件下,K-means算法可以被看作是高斯混合模型(GMM)的一種特殊形式(達觀數據 陳運文)。