機器學習實戰 - kNN算法 - 2

kNN演算法

簡述：

kNN算法非常直覺，根據統計新的資料點離原本的k個最近的資料點的分類的出現數量與距離進行判斷，藉此分析新的資料所屬的分類。

主要應用：約會網站、手寫數字辨識系統

算法優點：精度高、對異常值不敏感、不假定輸入數據

適用資料範圍類型：數值型與標準型

參考來源：http://www.ifight.me/273/
kNN算法步驟：

kNN演算法的基本思路：在給定新資料后，考慮在訓練資料點中與該新資料點距離最近（最相似）的 K 個資料點，根據這 K 個資料點所屬的類別判定所屬的分類類別，具體的演算法步驟如下：

1. 計算已知類別資料及當中的點與當前點之間的距離
2. 按照距離遞增次序排列
3. 選取與當前點距離最小的k個點
4. 確定前k個點所在類別的出現頻率
5. 返回前k個點出現高頻的類別作為當前點的預測分類

距離公式可採用下面多種距離，一般建議Mahalanobis distance效果較佳。

關於更多Mahalanobis distance資訊： https://en.wikipedia.org/wiki/Mahalanobis_distance


下面附上常用的距離公式列表：

1. 歐氏距離 (各個維度距離重要度均等)
2. 曼哈頓距離 （Manhattan distance又稱city block distance，格子距離）
3. 切比雪夫距離 （Chebyshev Distance，等同國際象棋國王與棋子的行走距離）
4. 閔可夫斯基距離 （Minkowski Distance）
   
   當p=1時，就是曼哈頓距離
   當p=2時，就是歐氏距離
   當p→∞時，就是切比雪夫距離
5. 標準化歐氏距離 （根據傳統歐氏距離的每個維度標準差變量進行標準化）
6. 馬氏距離 （Mahalanobis Distance
   ＠解決思想：由於各維度權重相同所造成的分類誤判、排除變量之間的相關性的干擾
   ＠數學原理：距離近的加權高、距離遠的加權低、最後算總值。
7. 夾角餘弦（Cosine Similarity，衡量向量之間的差異）
8. 漢明距離 （Hamming distance，兩個等長字串的最小替換次數，應用在訊息編碼）
9. 傑卡德距離 & 傑卡德相似係數
   （Jaccard similarity coefficient，兩集合交集數除以聯集數，應用於集合相似度的計算）
   Jaccard distance = 1 - Jaccard similarity coefficient
10. 相關係數 & 相關距離 (Correlation coefficient, Correlation distance)
    可用於計算線性相關度。
11. 信息熵 （Information Entropy，用於衡量分布的分散程度的度量，分佈越集中entropy就越小）