機器學習實戰 - 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就越小）

機器學習實戰 - 機器學習的應用步驟 - 1

由於身邊很多朋友想要接觸機器學習，卻不知道如何開始與應用，所以撰寫簡易的入門文讓新手理解如何應用機器學習的演算法於現實世界的問題。也分享個人經驗。

根據Machine Learning in Action書裡面的講解，可分成下面步驟：

1. 收集數據
2. 準備輸入數據
3. 分析輸入數據
4. 訓練算法
5. 測試算法
6. 使用算法 

收集數據部分：個人是使用python透過scrapy框架撰寫網絡爬蟲程式，好用便捷。

準備輸入數據：可透過numpy或pandas裡面讀取文件的API，並確認Load資料正確無誤。

分析輸入數據：查看資料是否有異常值、分析特徵的數值分佈、使用matplotlib將資料視覺化

訓練算法：根據資料抽取知識跟信息後，根據資料特性來選擇適合的機器學習演算法。

測試算法：設計評估算法，透過accuracy與recall數值評分。

使用算法：如何設計整個應用的流程pipeline。

建議使用python語言，提供適用的字串處理、數值運算、文本分析工具、機器學習套件等。

下面是IEEE選出的TOP 10演算法，可先以這些算法著手學習：

scikit-learn 機器學習套件 - 分析 supervised machine learning algorithm 效率

參考資料： http://scikit-learn.org/

套件說明：

scikit-learn此python套件非常適合用於機器學習領域。

機器學習領域一般分為：監督式學習、非監督式學習、增強式學習等

在能拿過去資料並有相關特徵標籤的分析案例而言，一般採用監督式學習演算法。

由於過去研究SVM是當前分類accuracy比較高的算法， 這次透過scikit裡面的內容驗證監督式學習演算法的效率，分析各個算法的效率。

分析程式碼與資源：

相關程式碼參閱下面連結：

http://scikit-learn.org/stable/auto_examples/classification/plot_classifier_comparison.html#sphx-glr-auto-examples-classification-plot-classifier-comparison-py

裡面的程式碼片段可以看到所有羅列出來的算法。

names = ["Nearest Neighbors", "Linear SVM", "RBF SVM", "Gaussian Process",

         "Decision Tree", "Random Forest", "Neural Net", "AdaBoost",

         "Naive Bayes", "QDA"]

下面是分析結果示意圖，右下角數值為accuracy：

實驗結論：

實驗中採用三種特性的dataset，第一個是部分特徵數值混在一起的、第二個是線性不可分的資料集合、第三個是簡易可以線性分割的資料集。由圖可知RBF-SVM是在這次實驗當中表現最好的一個算法。

關鍵解析：

重點在於SVM採用的kernel function，解決的線性不可分的資料集合所產生的問題。

其中kernel function原理就是透過內積運算原理將較低維度的空間資料及轉換到高維度的空間，使其資料集合較能夠線性可分，下方示意圖為2維轉換到3維的空間轉換示意圖。

關於kernel function原理請參閱下面連結： https://ireneli.eu/2016/09/13/two-sample-problem2-kernel-function-feature-space-and-reproducing-kernel-map/

關於RBF kernel 請參考：https://read01.com/2xMOa4.html