人工智慧之K近鄰算法(KNN)

2020-12-12 電子產品世界

  前言:人工智慧機器學習有關算法內容,請參見公眾號「科技優化生活」之前相關文章。人工智慧之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下K近鄰(KNN)算法。 ^_^

本文引用地址:http://www.eepw.com.cn/article/201806/381808.htm

  K近鄰KNN(k-Nearest Neighbor)算法,也叫K最近鄰算法,1968年由 Cover 和 Hart 提出,是機器學習算法中比較成熟的算法之一。K近鄰算法使用的模型實際上對應於對特徵空間的劃分。KNN算法不僅可以用於分類,還可以用於回歸。

  KNN概念:

  K近鄰算法KNN就是給定一個訓練數據集,對新的輸入實例,在訓練數據集中找到與該實例最鄰近的K個實例(K個鄰居),這K個實例的多數屬於某個類,就把該輸入實例分類到這個類中。

  如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別。K近鄰算法使用的模型實際上對應於對特徵空間的劃分。

  通俗地講,就是「物以類聚,人以群分」。

  分類策略,就是「少數從屬於多數」。

  算法描述:

  KNN沒有顯示的訓練過程,在測試時,計算測試樣本和所有訓練樣本的距離,根據最近的K個訓練樣本的類別,通過多數投票的方式進行預測。具體算法描述如下:

  輸入:訓練數據集T={(x1,y1),(x2,y2),...,(xn,yn)},其中xi∈Rn,yi∈{c1,c2,...,cK}和測試數據x

  輸出:實例x所屬的類別

  1) 根據給定的距離度量,在訓練集T中找到與x距離最近的k個樣本,涵蓋這k個點的x的鄰域記作Nk(x)。

  2)在Nk(x)中根據分類規則(如多數表決)確定x的類別y:

  核心思想:

  當無法判定當前待分類點是從屬於已知分類中的哪一類時,依據統計學的理論看它所處的位置特徵,衡量它周圍鄰居的權重,而把它歸為到權重更大的那一類中。

  kNN的輸入是測試數據和訓練樣本數據集,輸出是測試樣本的類別。

  KNN算法中,所選擇的鄰居都是已經正確分類的對象。KNN算法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

  算法要素:

  KNN 算法有3個基本要素:

  1)K值的選擇:K值的選擇會對算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用,但容易發生過擬合;如果 K 值較大,優點是可以減少學習的估計誤差,但缺點是學習的近似誤差增大,這時與輸入實例較遠的訓練實例也會對預測起作用,使預測發生錯誤。在實際應用中,K 值一般選擇一個較小的數值,通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時,誤差率不會超過貝葉斯誤差率的2倍,如果K也趨向於無窮,則誤差率趨向於貝葉斯誤差率。

  2)距離度量:距離度量一般採用 Lp 距離,當p=2時,即為歐氏距離,在度量之前,應該將每個屬性的值規範化,這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。

  對於文本分類來說,使用餘弦(cosine)來計算相似度就比歐式(Euclidean)距離更合適。

  3)分類決策規則:該算法中的分類決策規則往往是多數表決,即由輸入實例的K個最臨近的訓練實例中的多數類決定輸入實例的類別。

  算法流程:

  1)準備數據,對數據進行預處理。

  2)選用合適的數據結構存儲訓練數據和測試元組。

  3)設定參數,如K。

  4)維護一個距離由大到小的優先級隊列(長度為K),用於存儲最近鄰訓練元組。隨機從訓練元組中選取K個元組作為初始的最近鄰元組,分別計算測試元組到這K個元組的距離,將訓練元組標號和距離存入優先級隊列。

  5)遍歷訓練元組集,計算當前訓練元組與測試元組的距離,將所得距離L與優先級隊列中的最大距離Lmax。

  6)進行比較。若L>=Lmax,則捨棄該元組,遍歷下一個元組。若L

  7)遍歷完畢,計算優先級隊列中K個元組的多數類,並將其作為測試元組的類別。

  8)測試元組集測試完畢後計算誤差率,繼續設定不同的K值重新進行訓練,最後取誤差率最小的K值。

  算法優點:

  1)KNN從原理上也依賴於極限定理,但在類別決策時,只與極少量的相鄰樣本有關。

  2)由於KNN方法主要靠周圍有限的鄰近的樣本,而不是靠判別類域的方法來確定所屬類別的,因此對於類域的交叉或重疊較多的待分樣本集來說,KNN方法較其他方法更為適合。

  3)算法本身簡單有效,精度高,對異常值不敏感,易於實現,無需估計參數,分類器不需要使用訓練集進行訓練,訓練時間複雜度為0。

  4)KNN 分類的計算複雜度和訓練集中的文檔數目成正比,即,如果訓練集中文檔總數為n,那麼KNN的分類時間複雜度為O(n)。

  5)適合對稀有事件進行分類。

  6)特別適合於多分類問題(multi-modal),對象具有多個類別標籤,kNN比SVM的表現要好。

  算法缺點:

  1)當樣本不平衡時,樣本數量並不能影響運行結果。

  2)算法計算量較大;

  3)可理解性差,無法給出像決策樹那樣的規則。

  改進策略:

  KNN算法因其提出時間較早,隨著其他技術的不斷更新和完善,KNN算法逐漸顯示出諸多不足之處,因此許多KNN算法的改進算法也應運而生。算法改進目標主要朝著分類效率和分類效果兩個方向。

  改進1:通過找出一個樣本的k個最近鄰居,將這些鄰居的屬性的平均值賦給該樣本,就可以得到該樣本的屬性。

  改進2:將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight),如權值與距離成反比(1/d),即和該樣本距離小的鄰居權值大,稱為可調整權重的K最近鄰居法WAKNN(weighted adjusted K nearestneighbor)。但WAKNN會造成計算量增大,因為對每一個待分類的文本都要計算它到全體已知樣本的距離,才能求得它的K個最近鄰點。

  改進3:事先對已知樣本點進行剪輯(editing技術),事先去除(condensing技術)對分類作用不大的樣本。該算法比較適用於樣本容量比較大的類域的自動分類,而那些樣本容量較小的類域採用這種算法比較容易產生誤分。

  考慮因素:

  實現 K 近鄰算法時,主要考慮的因素是如何對訓練數據進行快速 K 近鄰搜索,這在特徵空間維數大及訓練數據容量大時是非常必要的。

  應用場景:

  K 近鄰算法應用場景包括機器學習、字符識別、文本分類、圖像識別等領域。

  結語:

  K近鄰算法KNN,也叫K最近鄰算法,是機器學習研究的一個活躍領域。最簡單的暴力算法,比較適合小數據樣本。K近鄰算法使用的模型實際上對應於對特徵空間的劃分。KNN算法不僅可以用於分類,還可以用於回歸。KNN算法在人工智慧之機器學習、字符識別、文本分類、圖像識別等領域有著廣泛應用。

相關焦點

  • 分類算法之K近鄰算法(KNN)
    算法思路K最近鄰(k-Nearest Neighbor)算法是比較簡單的機器學習算法。它採用測量不同特徵值之間的距離方法進行分類。思路: 如果一個樣本在特徵空間中的k個最近鄰(最相似)的樣本中的大多數都屬於某一個類別,則該樣本也屬於這個類別。算法分析這裡我以javaml庫為例分析算法實現步驟。
  • 機器學習算法推導&實現——k近鄰和kd樹實現
    我們知道k近鄰法(k-nearest neighbor, KNN)是一種基本的機器學習算法,早在1968年就被提出。
  • AI產品經理必懂算法:k-近鄰(KNN)算法
    作為想在AI領域長期發展的PM同學來說,對算法有一個初步、通識的了解是非常有必要的。今天我們就從一個最為簡單、易懂的「k-近鄰(KNN)算法」聊起,KNN屬於監督學習算法,即可以用於分類,也可以用於回歸,後續還會逐步為大家介紹一些常用的其他算法。
  • 【機器學習基礎】數學推導+純Python實現機器學習算法3:k近鄰
    ,k 近鄰在眾多有監督機器學習算法中算是一種比較獨特的方法。說它獨特,是因為 k 近鄰不像其他模型有損失函數、有優化算法、有訓練過程。對於給定的實例數據和實例數據對應所屬類別,當要對新的實例進行分類時,根據這個實例最近的 k 個實例所屬的類別來決定其屬於哪一類。所以相對於其它機器學習模型和算法,k 近鄰總體上而言是一種非常簡單的方法。
  • 【陸勤踐行】用R做K近鄰(KNN)
  • R語言實現K最近鄰算法(KNN)
    文章目錄理解近鄰分類第一步收集數據第二步探索和準備數據第三步基於數據訓練模型第四步評估模型的性能
  • KNN算法中的K有多重要
    K-最近鄰(KNN)是一種有監督的機器學習算法,可用於解決分類和回歸問題。它基於一個非常簡單的想法,數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此,k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5,則檢查5個最近點的類別。也可以根據多數類進行回歸預測,同樣,KNN回歸取5個最近點的平均值。
  • R語言--鄰近算法KNN
    ❝KNN(k鄰近算法)是機器學習算法中常見的用於分類或回歸的算法。它簡單,訓練數據快,對數據分布沒有要求,使它成為機器學習中使用頻率較高的算法,並且,在深度學習大行其道的今天,傳統可解釋的簡單模型在工業大數據領域的應用更為廣泛。本文介紹KNN算法的基本原理和用R代碼實現。
  • 機器學習之KNN分類算法介紹: Stata和R同步實現(附數據和代碼)
    在Stata和R(knn3函數)中,默認的距離指歐式距離(Euclidean Distance,記為L2)。近年來計量經濟學也已經把KNN納入,當成一種非參估計的方法。KNN可看成一種基於實例的學習算法,通過局部近似及推遲所有計算到分類之後,故也被稱為「惰性學習算法」。KNN分類通過最近的k個近鄰樣本的類別,來推測目標樣本的類別。
  • 常見面試算法:k-近鄰算法原理與python案例實現
    近鄰(kNN, k-NearestNeighbor)算法是一種基本分類與回歸方法,我們這裡只討論分類問題中的 k-近鄰算法。k 近鄰算法的輸入為實例的特徵向量,對應於特徵空間的點;輸出為實例的類別,可以取多類。k 近鄰算法假設給定一個訓練數據集,其中的實例類別已定。分類時,對新的實例,根據其 k 個最近鄰的訓練實例的類別,通過多數表決等方式進行預測。因此,k近鄰算法不具有顯式的學習過程。k 近鄰算法實際上利用訓練數據集對特徵向量空間進行劃分,並作為其分類的「模型」。
  • 教你學Python26-knn臨近算法
    KNN 概述k-近鄰(kNN, k-NearestNeighbor)算法是一種基本分類與回歸方法,我們這裡只討論分類問題中的 k-近鄰算法。一句話總結:近朱者赤近墨者黑!輸入沒有標籤的新數據後,將新的數據的每個特徵與樣本集中數據對應的特徵進行比較,然後算法提取樣本最相似數據(最近鄰)的分類標籤。一般來說,我們只選擇樣本數據集中前k個最相似的數據,這就是k-近鄰算法中k的出處,通常k是不大於20的整數。最後,選擇k個最相似數據中出現次數最多的分類,作為新數據的分類。k近鄰算法的輸入為實例的特徵向量,對應於特徵空間的點;輸出為實例的類別,可以取多類。
  • 數據科學經典算法 KNN 已被嫌慢,ANN 比它快 380 倍
    在模式識別領域中,K - 近鄰算法(K-Nearest Neighbor, KNN)是一種用於分類和回歸的非參數統計方法。K - 近鄰算法非常簡單而有效,它的模型表示就是整個訓練數據集。就原理而言,對新數據點的預測結果是通過在整個訓練集上搜索與該數據點最相似的 K 個實例(近鄰)並且總結這 K 個實例的輸出變量而得出的。
  • 從零開始用Python實現k近鄰算法(附代碼、數據集)
    在本文中,我們將討論另一種被廣泛使用的分類技術,稱為k近鄰(KNN)。本文的重點主要集中在算法的工作原理以及輸入參數如何影響輸出/預測。目錄什麼情況下使用KNN算法?KNN算法如何工作?如何選擇因子K?
  • 實例最簡,帶你輕鬆進階機器學習K最近鄰算法
    不過網上關於K近鄰算法的大多數介紹都非常繁雜且缺乏簡單實用的代碼示例。這樣不免會增加學習負擔,在這篇文章中我們將針對這個問題以最簡單的實例,帶大家來輕鬆地進階掌握K近鄰算法。此外,k近鄰算法在實現時,要計算新樣本與訓練集中每一個實例的距離。這種線性搜索會大大增加時間的消耗,尤其是在數據量很大的情況下。為了提高效率,會使用KD樹的方法。KD樹是一種二叉樹,主要是按訓練集數據的不同維度的中位數來劃分區域。
  • 速度數百倍之差,有人斷言KNN面臨淘汰,更快更強的ANN將取而代之
    在模式識別領域中,K - 近鄰算法(K-Nearest Neighbor, KNN)是一種用於分類和回歸的非參數統計方法。K - 近鄰算法非常簡單而有效,它的模型表示就是整個訓練數據集。解決方案將最近鄰算法擴展至大規模數據的方法是徹底避開暴力距離計算,使用 ANN 算法。近似最近距離算法(ANN)嚴格地講,ANN 是一種在 NN 搜索過程中允許少量誤差的算法。但在實際的 C2C 市場中,真實的鄰居數量比被搜索的 K 近鄰數量要多。
  • 速度數百倍之差!有人斷言KNN面臨淘汰,更快更強的ANN將取而代之
    在模式識別領域中,K - 近鄰算法(K-Nearest Neighbor, KNN)是一種用於分類和回歸的非參數統計方法。K - 近鄰算法非常簡單而有效,它的模型表示就是整個訓練數據集。就原理而言,對新數據點的預測結果是通過在整個訓練集上搜索與該數據點最相似的 K 個實例(近鄰)並且總結這 K 個實例的輸出變量而得出的。KNN 可能需要大量的內存或空間來存儲所有數據,並且使用距離或接近程度的度量方法可能會在維度非常高的情況下(有許多輸入變量)崩潰,這可能會對算法在你的問題上的性能產生負面影響。這就是所謂的維數災難。
  • 共享·乾貨|機器學習之KNN鄰近算法
    事實上,k值選擇過小,得到的近鄰數過少,會降低分類精度,同時也會放大噪聲數據的幹擾;而如果k值選擇過大,並且待分類樣本屬於訓練集中包含數據數較少的類,那麼在選擇k個近鄰的時候,實際上並不相似的數據亦被包含進來,造成噪聲增加而導致分類效果的降低。在實際的使用中,K值的選擇通常小於訓練樣本數目的平方根。還常常對不同的K值進行多次實驗,找到最為合適的K值。
  • opencv|K 近鄰(k-Nearest Neighbour)
    所以檢測 k 個最近鄰居。誰在這 k 個鄰居中佔據多數,那新的成員就屬於誰那一類。如果 k 等於 3,也就是在上面圖像中檢測 3 個最近的鄰居。他有兩個紅的和一個藍的鄰居,所以他還是屬於紅色家族。但是如果 k 等於 7呢?他有 5 個藍色和 2 個紅色鄰居,現在他就會被分到藍色家族了。k 的取值對結果影響非常大。
  • 聚類(三):KNN算法(R語言)
    k最臨近(KNN)算法是最簡單的分類算法之一,屬於有監督的機器學習算法。
  • 《機器學習實戰》學習筆記:K-近鄰算法入門及實戰|萬字長文
    而k-近鄰算法也可以像我們人一樣做到這一點,不同的地方在於,我們的經驗更」牛逼」,而k-鄰近算法是靠已有的數據。比如,你告訴我這個電影打鬥鏡頭數為2,接吻鏡頭數為102,我的經驗會告訴你這個是愛情片,k-近鄰算法也會告訴你這個是愛情片。