目錄
-
- 1.什麼是KNN(k-nearest neighbor)?
- 2. 基本思想
- 3.算法詳述
- 4. 例子
- 5. K值選取對歸類的影響
- 6. 小結
1.什麼是KNN(k-nearest neighbor)?
K最近鄰(K-Nearest Neighbor,KNN)算法，是著名的模式識别統計學方法，在機器學習分類算法中占有相當大的地位。它是一個理論上比較成熟的方法。既是最簡單的機器學習算法之一，也是基于執行個體的學習方法中最基本的，又是最好的文本分類算法之一。
2. 基本思想
如果一個執行個體在特征空間中的K個最相似（即特征空間中最近鄰）的執行個體中的大多數屬于某一個類别，則該執行個體也屬于這個類别。所選擇的鄰居都是已經正确分類的執行個體。
該算法假定所有的執行個體對應于N維歐式空間Ân中的點。通過計算一個點與其他所有點之間的距離，取出與該點最近的K個點，然後統計這K個點裡面所屬分類比例最大的，則這個點屬于該分類。
一張圖助你了解：
該算法涉及3個主要因素：執行個體集、距離或相似的衡量、k的大小。
一個執行個體的最近鄰是根據标準歐氏距離定義的。更精确地講，把任意的執行個體x表示為下面的特征向量：
3.算法詳述
1.為了判斷未知執行個體的類别，以所有已知類别的執行個體作為參照
2.選擇參數K
3.計算某未知執行個體與已知執行個體的距離
4.選擇K個最近的已知執行個體
5.根據少數服從多數的投票法則(majority-voting),讓未知執行個體歸類為K個最近臨近樣本中最多數的類别
4. 例子
以下由打鬥次數和接吻次數的資料集以及對應的電影類型，預知在某一打鬥次數和接吻次數條件下應該歸為哪一類 ：
把訓練集虛拟成向量（點集）：
計算G點與所有點的距離：
若給定的K值為3，則選擇最小的3個距離 的點：a,b,c
在a,b,c中投票選取最大機率出現的類型：Romance
是以G的歸類應該是Romance
5. K值選取對歸類的影響
根據K值的不同讨論綠色點的歸類：
- K=1：最近的1個是藍色，且距離的結果集中隻有一個（1：0），歸類為藍色
- K=4：最近的4個為内實圈中的4個，投票結果是紅色（3：1），歸類為紅色
- k=9：最近的9個為外虛圈内的9個，投票結果為紅色（6：3），歸類為紅色
選取不同的K值對歸類結果存在影響，可以通過增大K值減少噪音（最好選取奇數）
6. 小結
優點：簡單，易于了解，容易實作，通過對K的選擇可具備丢噪音 資料的健壯性
缺點：需要大量的空間來存儲所有已知的 執行個體；算法複雜度高（需要比較所有已知的執行個體和要分類的執行個體）；當樣本分布不平衡時，比如其中一類樣本過大占主導的時候，新的執行個體可能被歸為這個主導樣本，因為這類樣本執行個體的數量過大，但是這個新的未知執行個體并未接近目标樣本：
上圖Y本屬于紅類，單由于 藍色的樣本數量過大，結果将Y歸為藍色（主導地位）
改進：考慮距離，增權重重，即距離小的權重比較大
更多文章：https://blog.csdn.net/qq_33208851/article/details/95230847