[機器學習首部曲]K-近鄰演算法 KNN

今天，我們來聊聊機器學習裡面最簡單的演算法，KNN (k-nearest neighbors)! 望文生義，就是物以類聚，你跟你的鄰居都是同類啦! 那K是什麼呢? K代表著一個常數，也就是多少個鄰居算一類。

什麼是KNN?

簡單來說，就是物以類聚的概念。如果你的鄰居10戶有8戶是有錢人，那你十之八九也是有錢人! KNN用途很廣，適用於離散型資料，也適用於連續型資料。

KNN的運作模式

找到距離最近的K個鄰居→進行投票→決定類別

主要運作模式分為3步驟:
步驟1. 計算每個點之間的距離
步驟2. 用K值決定鄰居數目，並進行投票 (在連續型資料中，則是計算平均數)
步驟3. 以投票結果決定類別

距離計算

點與點之間的距離，除了我們直觀用尺量以外，數學上其實還有很多種符合距離定義的其他計算方式，以下我們簡單分享幾種。

歐基里德距離 (Euclidean distance)

這其實就是我們平時最熟悉的距離計算模式:

$$D= \sqrt{(x_1-y_1)^2+(x_2-y_2)^2+…+(x_n-y_n)^2} $$

$$ =\sqrt{\sum_{i=1}^{n} (x_i-y_i)^2} $$

曼哈頓距離 (Manhattan distance)

曼哈頓距離的計算方式是將所有特徵的個別距離加總在一起:

$$D=|x_1-y_1|+|x_2-y_2|+…+|x_n-y_n|$$

$$=\sum_{i=1}^{n} |x_i-y_i|$$

明氏距離 (Minkowski distance)

有點像是歐基里德距離與曼哈頓距離的推廣，仔細對照公式會發現，當p=1時其實就是曼哈頓距離，而當p=2時則為歐基里德距離。在這邊，p為任意常數。

$$ D=(\sum_{i=1}^{n}|x_i-y_i|^p)^{\frac{1}{p}} $$

決定K值，並進行投票

計算完距離以後，我們可以決定常數K，也就是有多少個鄰居被我們視為最接近的鄰居。舉例來說，如果我們選擇K=3，那我們就會以距離最接近的3個點當作鄰居，並看這3個鄰居當中有多少個鄰居是屬於哪一種類別，並以數量最多的類別取勝。以下圖來說，當K=3時，因為藍色水滴有2個，黃色倒藍水滴只有1個，因此我們會判定星星為藍色水滴。

而當K=5時，我們則會判定星星為黃圈倒藍水滴，因為黃圈倒藍水滴有3個，大於藍水滴的2個。

聰明的你可能已經想到，如果是4個，那怎麼辦呢?

所以，一般來說，我們會盡量選擇K為奇數，以避免平手的情況。當然，這並不會完全無法決定。除了一人一票票票等值的投票法外，我們還有另外一種投票法叫做加權投票法，意即距離愈近的權重愈高。以上面這個例子為例，因為2個藍水滴距離星星較近，因此最後會星星會被判定為屬於藍色水滴類別!

到了這邊，相信您已經完全掌握了KNN的運作模式，更了解到K值選擇的重要性! K值太大，很可能包含了很多非相關的樣本點，而K值太小，卻又容易受到噪音的影響。有個經驗法則是，我們會盡量讓K值低於樣本數的平方根。實務上，我們也可以透過不斷拆分訓練集與測試集的交叉驗證找到較為穩定的K值。

總結

KNN是個非常簡單易懂的模型，用途廣，且資料型態不受限，在多種類別分類時表現更是優異。然而，缺點就是計算量相當龐大，畢竟每個點之間的距離都要計算! 另外，當樣本不平衡時(某一類特多)，也相對容易產生預測錯誤的情況。