機器學習——K最鄰近(KNN)算法詳解

2021-01-12 假程序猿

KNN算法全稱是：K-NearestNeighbor，中文翻譯就是：K最鄰近。它屬於機器學習中最簡單、最基本的分類和回歸算法。那麼什麼叫K最鄰近呢？說白了就是你有一個需要預測的實例，在訓練集中尋找K個與這個被預測實例最相似的訓練實例，那麼預測實例就與K個訓練實例中出現次數最多的那個元素屬於同一類。

下面通過圖一進行簡單說明：綠色的圓點就是預測實例，藍色和紅色元素就是訓練集中不同的類。

圖一

當K = 3時（即圖中黑色實線的圓），紅色三角形出現2次，藍色矩形出現1次，所以綠色圓實例與紅色三角形屬於同一類。

而當K = 5時（即圖中黑色虛線的圓），紅色出現2次，而藍色出現3次，所以綠色實例應該與藍色矩形屬於同一類。

說到這，我們就會拋出下面兩個問題：

因為你要知道每個實例之間的距離，所以實例與實例之間的距離是怎麼計算的？由上面的例子可以知道，當我們選取K不同的時候，相同的實例會有不同的分類結果，所以這個距離K是怎麼選取的？對於問題一，我們有兩種計算距離的方法：歐氏距離（歐幾裡得距離）和曼哈頓距離。相應的公式：

圖二，歐氏距離
圖三，曼哈頓距離

歐氏距離就是我們生活中所說的兩點之間的最短距離，而曼哈頓距離就是兩點之間每個維度的距離之和，我們用一張圖來解釋更明白：

圖四

如圖，在二維坐標中，兩個黑點之間綠色的線就是歐氏距離；而紅色、藍色、黃色的折線都是等長的，就是曼哈頓距離。用到多維坐標中也是如此。

而對於問題二就更簡單了，尋找K值的方法叫做交叉驗證法。一般K從3開始，然後取每個K都遍歷訓練集，尋找K為何值時，預測的準確度最高。那麼有人會說，K是不是越小越好？

當然不是，把圖一改造以下，如圖五所示：

圖五

現在我們假定綠色和紅色屬於一類，那麼如果當K = 1（綠色圈）或6（黑色虛線圈）時，這個算法會把綠色和藍色歸為一類，而當K = 3時，才是正確的結果。我們把K = 1時選取的那個藍色矩形稱為訓練集中的噪聲，我們應當避免這種幹擾項。而K = 6時，距離較遠的實例也會算進來，幹擾了預測。所以選取適當的K的值是十分必要的。

總結KNN算法：

計算預測實例和訓練集實例的歐式距離或者曼哈頓距離。用交叉驗證法確定K的取值。計算K個最鄰距離中出現次數最多的實例，既是結果。最後，我會寫一篇關於用KNN算法來預測手寫數字的文章，來了解KNN算法的實際用處。

圖一 ：https://upload.wikimedia.org/wikipedia/commons/e/e7/KnnClassification.svg

圖二： 百度百科 歐幾裡得距離

圖三：百度百科 曼哈頓距離

圖四https://upload.wikimedia.org/wikipedia/commons/0/08/Manhattan_distance.svg

相關焦點

  • 機器學習:基於Knn算法的用戶屬性判斷方案設計
    本文作者通過Knn算法進行了一次用戶判斷預測的流程，文章為作者根據自身經驗所做出的總結，希望通過此文能夠加深你對Knn算法的認識。knn算法簡介K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。
  • KNN算法中的K有多重要
    K-最近鄰（KNN）是一種有監督的機器學習算法，可用於解決分類和回歸問題。它基於一個非常簡單的想法，數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此，k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5，則檢查5個最近點的類別。也可以根據多數類進行回歸預測，同樣，KNN回歸取5個最近點的平均值。
  • k近鄰法(KNN)原理小結
    k-近鄰模型的三要素：k值的選擇、距離度量（作為"最鄰近"的衡量標準）、分類決策規則（例如」多數表決「）knn算法可總結為3個步驟：1.Choose the number of k and模型三要素：k值的選擇、距離度量（作為"最鄰近"的衡量標準）、分類決策規則（例如」多數表決「）2.1 k值的選擇k值的選擇會對k近鄰法的結果產生重大影響
  • 教你用OpenCV實現機器學習最簡單的k-NN算法
    這正是k-NN算法將要處理的問題。理解 k-NN 算法k-NN算法可以認為是最簡單的機器學習算法之一。原因是我們只需要存儲訓練數據集。指定k值，創建一個k-NN對象。找到想要分類的新數據點的k個最近鄰的點。使用多數投票來分配新數據點的類標籤。畫出結果圖。首先引入所有必需的模塊：使用k-NN算法的OpenCV、處理數據的NumPy、用於繪圖的Matplotlib。如果使用Jupyter Notebook，別忘了調用%matplotlib inline魔法命令。
  • KNN分類算法的python實現
    前言 K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：在特徵空間中，如果一個樣本附近的k個最近(即特徵空間中最鄰近)樣本的大多數屬於某一個類別，則該樣本也屬於這個類別。。
  • 教你學Python26-knn臨近算法
    KNN 概述k-近鄰（kNN, k-NearestNeighbor）算法是一種基本分類與回歸方法，我們這裡只討論分類問題中的 k-近鄰算法。一句話總結：近朱者赤近墨者黑！輸入沒有標籤的新數據後，將新的數據的每個特徵與樣本集中數據對應的特徵進行比較，然後算法提取樣本最相似數據(最近鄰)的分類標籤。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大於20的整數。最後，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。k近鄰算法的輸入為實例的特徵向量，對應於特徵空間的點；輸出為實例的類別，可以取多類。
  • AI產品經理必懂算法:k-近鄰(KNN)算法
    作為想在AI領域長期發展的PM同學來說，對算法有一個初步、通識的了解是非常有必要的。今天我們就從一個最為簡單、易懂的「k-近鄰（KNN）算法」聊起，KNN屬於監督學習算法，即可以用於分類，也可以用於回歸，後續還會逐步為大家介紹一些常用的其他算法。
  • 在機器學習的世界裡打怪升級——KNN算法篇
    「全文約2000字，閱讀時間約6分鐘」 來自機器學習世界裡的勇士，你剛走出新手村，還沒完全武裝自己，就碰到了旅途中第一個小boss——KNN算法。 不過也別害怕，這是入門機器學習zui簡單、也zui容易理解的一個算法。
  • 比KNN快380倍!我們有了新選擇
    KNN背景尋找與給定項目的K個相似項的做法在機器學習界被廣泛稱為「相似」搜索或「最近鄰」（NN）搜索。最廣為人知的最近鄰搜索算法便是K最近鄰（KNN）算法。它的用途很廣，在已有的物品集如手機電商目錄中，運用KNN,便可以從這一整個目錄中找到一個少數（Ｋ）最近鄰來發起新的搜索請求。
  • 機器學習算法一覽(附python和R代碼)
    這篇文章有可能是我寫的所有文章裡最有價值的一篇。 寫這篇文章的目的，就是希望它可以讓有志於從事數據科學和機器學習的諸位在學習算法的路上少走些路。我會在文章中舉例一些機器學習的問題，你們也可以在思考解決這些問題的過程中得到啟發。我也會寫下對於各種機器學習算法的一些個人理解，並且提供R和Python的執行代碼。
  • 常見的機器學習算法,你知道幾個?
    誕生於1956年的人工智慧，由於受到智能算法、計算速度、存儲水平等因素的影響，在六十多年的發展過程中經歷了多次高潮和低谷。最近幾年，得益於數據量的上漲、運算力的提升，特別是機器學習新算法的出現，人工智慧迎來了大爆發的時代。提到機器學習這個詞時，有些人首先想到的可能是科幻電影裡的機器人。
  • 基於KNN和Kmeans算法利用MNIST數據集實現手寫數字識別
    然而k最近鄰居法因為計算量相當的大，所以相當的耗時，Ko與Seo提出一算法TCFP（text categorization using feature projection），嘗試利用特徵投影法來降低與分類無關的特徵對於系統的影響，並藉此提升系統性能，其實驗結果顯示其分類效果與k最近鄰居法相近，但其運算所需時間僅需k最近鄰居法運算時間的五十分之一。
  • 機器學習算法的基本知識(使用Python和R代碼)
    今天，作為 數據科學 家，我可以每小時為幾個玩偶構建具有複雜算法的 數據 處理機。 但到達這裡並不容易，我已經度過了許多黑暗的日日夜夜。　　誰可以從本指南中獲益最多　　我今天發布的可能是我創造的最有價值的指南。　　創建本指南背後的理念是簡化全球有抱負的數據科學家和機器學習愛好者的旅程。
  • 機器學習之分類算法K-Means介紹與代碼分析(篇四)
    這個問題在計算上是NP困難的，不過存在高效的啟發式算法。一般情況下，都使用效率比較高的啟發式算法，它們能夠快速收斂於一個局部最優解。這些算法通常類似於通過迭代優化方法處理高斯混合分布的最大期望算法（EM算法）。而且，它們都使用聚類中心來為數據建模；然而k-平均聚類傾向於在可比較的空間範圍內尋找聚類，期望-最大化技術卻允許聚類有不同的形狀。
  • 流行的機器學習算法總結,幫助你開啟機器學習算法學習之旅
    定期將算法應用於新數據和新經驗的過程可提高機器學習的整體效率。機器學習算法對於與分類，預測建模和數據分析相關的各種任務至關重要。「機器學習方面的突破將價值十個微軟。」- Bill Gates機器學習算法的類型在本節中，我們將重點介紹現有的各種ML算法。
  • 標籤傳播算法(Label Propagation)及Python實現
    半監督學習算法有很多，下面我們介紹最簡單的標籤傳播算法(label propagation)，最喜歡簡單了，哈哈。還有個非常常用的圖構建方法是knn圖，也就是只保留每個節點的k近鄰權重，其他的為0，也就是不存在邊，因此是稀疏的相似矩陣。2.2、LP算法標籤傳播算法非常簡單：通過節點之間的邊傳播label。邊的權重越大，表示兩個節點越相似，那麼label越容易傳播過去。我們定義一個NxN的概率轉移矩陣P：
  • 機器學習初學者必須知道的十大算法
    還在為不知道學什麼算法入門機器學習感到頭疼？本文作者通過自身的學習向初學者介紹十大機器學習（ML）算法，並附有數字和實例以便於理解。哈佛商業評論稱數據科學家是21世紀最性感的工作。所以，對於那些ML剛剛開始的人來說，這篇博客機器學習算法工程師需要知道的十大算法是非常有用的。ML算法是可以從數據中學習並從中改進的算法，無需人工幹預。
  • 史上最全十大機器學習算法,入門必看!
    1介紹關於機器學習算法的研究已經獲得了巨大的成功，哈佛商業評論甚至將數據科學家稱為二十一世紀最具誘惑力的工作。機器學習算法是在沒有人為幹涉的情況下，從大量的數據和歷史經驗中學習數據的結構並提升對某一目標的估計的算法。
  • 數據科學家應該知道的頂級機器學習算法
    示例算法包括邏輯回歸和反向傳播神經網絡。無監督學習在此無監督機器學習中，輸入數據未標記並且沒有已知結果。我們必須通過推導輸入數據中存在的結構來準備模型。這可能是提取一般規則。可以通過數學過程來減少冗餘。示例問題包括聚類，降維和關聯規則學習。示例算法包括Apriori算法和k-Means。半監督學習輸入數據是帶標籤和未帶標籤的示例的混合。存在期望的預測問題。
  • 最好的Python機器學習庫
    引言毫無疑問，神經網絡和機器學習在過去幾年一直是高科技領域最熱門的話題之一。這一點很容易看出，因為它們解決了很多真正有趣的用例，如語音識別、圖像識別、甚至是樂曲譜寫。因此，在這篇文章，我決定編制一份囊括一些很好的Python機器學習庫的清單，並將其張貼在下面。