Knn K Nearest Neighbor-machine learning 基礎最近鄰演算法

Home >> Blog >> Knn K Nearest Neighbor-machine learning 基礎最近鄰演算法

Knn K Nearest Neighbor-machine learning 基礎最近鄰演算法

k- K Nearest Neighbor最近鄰 (KNN) 算法是一種簡單、易於實現的監督機器學習算法，可用於解決分類和回歸問題。

打破它

有監督的機器學習算法（與無監督的機器學習算法相反）是一種依靠標記的輸入數據來學習一個函數，該函數在給定新的未標記數據時會產生適當的輸出。

想像一台電腦是一個孩子，我們是它的主管（例如父母、監護人或老師），我們希望孩子（電腦）了解豬的樣子。我們將向孩子展示幾張不同的圖片，其中一些是豬，其餘的可能是任何東西（貓、狗等）的圖片。

當我們看到一頭豬時，我們會喊“豬！” 當它不是豬時，我們會喊“不，不是豬！” 和孩子一起做了幾次之後，我們給他們看一張照片，問“豬？” 他們會（大多數時候）正確地說“豬！” 或“不，不是豬！” 取決於圖片是什麼。那就是有監督的機器學習。

監督機器學習算法用於解決分類或回歸問題。

分類問題有一個離散值作為其輸出。例如，“喜歡披薩上的菠蘿”和“不喜歡披薩上的菠蘿”是離散的。沒有迴旋的餘地。上面教孩子識別豬的類比是分類問題的另一個例子。

此圖像顯示了分類數據可能是什麼樣子的基本示例。我們有一個預測器（或一組預測器）和一個標籤。在圖像中，我們可能試圖根據某人的年齡（預測變量）來預測某人是否喜歡披薩上的菠蘿（1）（0）。

將分類算法的輸出（標籤）表示為整數（例如 1、-1 或 0）是標準做法。在這種情況下，這些數字純粹是代表性的。不應對它們執行數學運算，因為這樣做毫無意義。想一想。什麼是“喜歡菠蘿”+“不喜歡菠蘿”？確切地。我們不能添加它們，所以我們不應該添加它們的數字表示。

回歸問題有一個實數（帶小數點的數字）作為其輸出。例如，我們可以使用下表中的數據根據身高來估計某人的體重。

回歸分析中使用的數據看起來與上圖中顯示的數據相似。我們有一個自變量（或一組自變量）和一個因變量（給定自變量，我們試圖猜測的東西）。例如，我們可以說身高是自變量，體重是因變量。

此外，每一行通常稱為示例、觀察或數據點，而每一列（不包括標籤/因變量）通常稱為預測變量、維度、自變量或特徵。

無監督機器學習算法使用沒有任何標籤的輸入數據——換句話說，沒有老師（標籤）告訴孩子（電腦）什麼時候正確或什麼時候犯了錯誤，以便它可以自我糾正。

與試圖學習允許我們在給定一些新的未標記數據的情況下進行預測的函數不同的監督學習不同，無監督學習試圖學習數據的基本結構，以便讓我們更深入地了解數據。

K-最近鄰

KNN 算法假設相似的事物非常接近。換句話說，相似的事物彼此靠近。

請注意，在上圖中，大多數情況下，相似的數據點彼此靠近。KNN 算法取決於這個假設是否足夠真實，以使算法有用。KNN 使用我們童年時可能學過的一些數學來捕捉相似性（有時稱為距離、接近度或接近度）的概念——計算圖上點之間的距離。

注意：在繼續之前，有必要了解我們如何計算圖表上點之間的距離。如果您不熟悉或需要復習此計算的方法，請通讀“兩點之間的距離”全文，然後再回來。

還有其他計算距離的方法，根據我們正在解決的問題，一種方法可能更可取。但是，直線距離（也稱為歐幾里得距離）是一種流行且熟悉的選擇。

KNN 算法

1. 加載數據
2. 將 K 初始化為您選擇的鄰居數

3.對於數據中的每個例子

3.1 從數據中計算查詢示例與當前示例的距離。

3.2 將示例的距離和索引添加到有序集合中

4. 按距離從小到大（按升序）對距離和索引的有序集合進行排序

5. 從已排序的集合中挑選前 K 個條目

6. 獲取選中的K個條目的標籤

7. 如果回歸，返回 K 個標籤的平均值

8.如果分類，返回K個標籤的模式

KNN 實現（從頭開始）

為 K 選擇正確的值

為了選擇適合您的數據的 K，我們使用不同的 K 值多次運行 KNN 算法，並選擇可以減少我們遇到的錯誤數量的 K，同時保持算法在給定數據時準確做出預測的能力。

以下是一些需要注意的事項：

1. 隨著我們將 K 的值減小到 1，我們的預測變得不太穩定。想一想，想像一下 K=1，我們有一個被幾個紅色和一個綠色包圍的查詢點（我在想上面彩色圖的左上角），但綠色是最近的一個鄰居。合理地，我們會認為查詢點很可能是紅色的，但是因為 K=1，KNN 錯誤地預測查詢點是綠色的。
2. 相反，隨著我們增加 K 的值，由於多數投票/平均，我們的預測變得更加穩定，因此更有可能做出更準確的預測（直到某個點）。最終，我們開始看到越來越多的錯誤。正是在這一點上，我們知道我們將 K 的值推得太遠了。
3. 如果我們在標籤中進行多數投票（例如在分類問題中選擇模式），我們通常將 K 設為奇數以進行決勝局。

優點

1. 該算法簡單易實現。
2. 無需構建模型、調整多個參數或做出額外的假設。
3. 該算法是通用的。它可以用於分類、回歸和搜索（我們將在下一節中看到）。

缺點

1.隨著示例和/或預測變量/自變量數量的增加，該算法變得明顯變慢。

實踐中的 KNN

KNN 的主要缺點是隨著數據量的增加而顯著變慢，這使得它在需要快速進行預測的環境中成為不切實際的選擇。此外，還有更快的算法可以產生更準確的分類和回歸結果。

但是，只要您有足夠的計算資源來快速處理用於進行預測的數據，KNN 仍然可以用於解決具有依賴於識別相似對象的解決方案的問題。這方面的一個例子是在推薦系統中使用 KNN 算法，這是 KNN 搜索的一種應用。

推薦系統

從規模上看，這看起來像是在亞馬遜上推薦產品、在 Medium 上推薦文章、在 Netflix 上推薦電影或在 YouTube 上推薦視頻。儘管如此，我們可以肯定的是，由於他們處理的數據量巨大，他們都使用更有效的方法來提出建議。

但是，我們可以使用我們在本文中學到的知識在較小的規模上複製其中一個推薦系統，例如SEO優化方案由此系統分析後推薦一組最短路徑優化方式。抑或是也讓我們構建一個電影推薦系統的核心。

我們試圖回答什麼問題？

給定我們的電影數據集，與電影查詢最相似的 5 部電影是什麼？

收集電影數據

如果我們在 Netflix、Hulu 或 IMDb 工作，我們可以從他們的數據倉庫中獲取數據。由於我們不在這些公司工作，我們必須通過其他方式獲取數據。我們可以使用來自UCI 機器學習存儲庫、 IMDb 數據集的一些電影數據，或者煞費苦心地創建我們自己的。

探索、清理和準備數據

無論我們從哪裡獲得數據，都可能存在一些問題，我們需要對其進行糾正，以便為 KNN 算法做好準備。例如，數據可能不是算法期望的格式，或者可能存在缺失值，我們應該在將數據導入算法之前從數據中填充或刪除這些值。

我們上面的 KNN 實現依賴於結構化數據。它需要採用表格格式。此外，該實現假設所有列都包含數字數據，並且我們數據的最後一列具有我們可以執行某些功能的標籤。因此，無論我們從哪裡獲取數據，我們都需要使其符合這些約束。

下面的數據是我們清理後的數據可能類似於的示例。該數據包含三十部電影，包括七種類型的每部電影的數據及其 IMDB 評級。標籤列全為零，因為我們沒有將此數據集用於分類或回歸。

此外，在使用 KNN 算法時，電影之間的某些關係（例如演員、導演和主題）將不會被考慮在內，這僅僅是因為數據集中缺少捕獲這些關係的數據。因此，當我們對我們的數據運行 KNN 算法時，相似性將僅基於包含的類型和電影的 IMDB 評級。

使用算法

想像一下。我們正在瀏覽 MoviesXb 網站，這是一個虛構的 IMDb 衍生產品，我們遇到了The Post。我們不確定我們是否想看它，但它的類型很吸引我們；我們對其他類似的電影很好奇。我們向下滾動到“更像這樣”部分，看看 MoviesXb 會提出什麼建議，算法齒輪開始轉動。

MoviesXb 網站向其後端發送與The Post最相似的 5 部電影的請求。後端有一個和我們一模一樣的推薦數據集。它首先為The Post創建行表示（更好地稱為特徵向量），然後運行類似於下面的程序來搜索與The Post最相似的 5 部電影，最後將結果發送回MoviesXb 網站。

當我們運行這個程序時，我們看到 MoviesXb 推薦了《為奴十二年》、 《鋼鋸嶺》、《卡特維女王》、《起風了》和《美麗心靈》。現在我們完全了解了 KNN 算法的工作原理，我們能夠準確地解釋 KNN 算法是如何提出這些建議的。恭喜！

概括

k 最近鄰 (KNN) 算法是一種簡單的有監督機器學習算法，可用於解決分類和回歸問題。它很容易實現和理解，但有一個主要缺點是隨著使用的數據量的增長而顯著變慢。

KNN 的工作原理是找出查詢與數據中所有示例之間的距離，選擇最接近查詢的指定數量示例 (K)，然後投票給最頻繁的標籤（在分類的情況下）或平均標籤（在回歸的情況）。

在分類和回歸的情況下，我們看到為我們的數據選擇正確的 K 是通過嘗試幾個 K 並選擇效果最好的一個來完成的。

最後，我們查看瞭如何在推薦系統中使用 KNN 算法的示例，這是 KNN 搜索的一個應用。