牛油貓的筆記: 11/10/20

簡介
機器學習其中一個最實用的功能，就是分門別類 (Classification / Clustering)。用家只需將數據放入模型當中，算法就能告訴你該數據所屬的類型、或者是所屬的群組。這種算法十分受歡迎，因為它除了可以用來分類垃圾郵件、了解用戶類型、更能幫助找出一堆亂數中的潛在規律。

分類算法，大致上來講，包含了以下兩大類：

Supervised Clustering: 訓練數據中不但包含數據本身，也包含了數據的標註 (Labels)。這種算法的目標，是找出輸入數據與標註之間的關係，從而判斷未來數據的標註。例子包括運用 CNN 作 MNIST 數字辯認等等。
Unsupervised Clustering: 訓練數據中，並不包含標註。這種情況，用家並不清楚數據中的特徵，並希望透過算法，找出其特徵，然後將數據自動分類。例子包括用 SOM / SVM 找出數據之間的邊界等。

由於近年機器學習成為熱潮，分類算法自 2000 年起，幾乎每天都有新的變種。即使傳統算法，也多得不可細數（SOM, SVM, OCSVM, kNN, DBSCAN, OPTICS, LOF, CBLOF ...）。這篇文章本來只打算講其中一種 Unsupervised Clustering 算法（也就是 LOF），但筆者發現，原來 LOF 與 kNN 及 DBSCAN 又有很大關係。所以今天會簡單筆錄一下這三種常見，關係卻十分密切的算法。

kNN (K Nearest Neighbor) ：「K 個最近鄰居」
顧名思義，這種算法的目的，是找出鄰近 K 點所屬的類別，從而決定自己屬於那一類別。

以下會用這個例子示範：

假設 k=3 的話，並已知 a, b 均為甲組，c, d 為乙組。

如果有一個新點 d = (2, 0)，它的最近 3 個鄰居為 a, c, d。
當中因大多數屬乙組，所以 d 點也屬於乙組。

如果有一個新點 e = (1, 1)，它的最近 3 個鄰居為 a, b, c。
當中因大多數屬甲組，所以 e 點會算作甲組。

Python 應用可參考此頁。

DBSCAN (Density-based spatial clustering of applications with noise)：「聚類分析」
聚類分析屬於 Unsupervised Learning，它並不需要任何 Labels 或類別。
它只需要兩個變數，距離值 (ε epsilon) 和最低點數 (minSample)，就能把數據分類。

以維基百科的圖片作例子：eps = r，minSample = 4:

在這個例子中，假設以 A 點出發，
A 點在它的 r 圓周範圍內找到 4 點（包括自己），所以該四點與 A 為同一類別；
然後該四點會開始以 nested loop 方式，用同一方法再算。

隨機先選 A 點左邊的一點，它的圓周範圍內找到 5 點，所以該五點也屬 A 類；
然後該五點會開始以 nested loop 方式，用同一方法再算。

隨機先選五點中最左一點，該點的圓周內找到 4 點，所以該四點也屬 A 類；
然後該四點會開始以 nested loop 方式，用同一方法再算。

再向左出發，B 點的圓周範圍內只找到 2 點，
所以它屬非核心點 (non-core point)，但仍屬 A 類。

至於 N 點，由於它的 r 圓周範圍內一點也找不到，它就變成另一個類別。

故此，只要每一點都順序運算最少一次，理應就能找到所有點所屬的類別。

Python 應用可參考此頁。

LOF (Local Outlier Factor) 「本地異常值」
LOF 是三種算法之中，最複雜的一種算法。與 DBSCAN 相似的是，它同樣屬於 Unsupervised Learning 的算法。但與 kNN 也相似的是，它在計算過程中，需要輸入 K 個鄰居值。

簡單來講，它混合了 kNN、LRD 等一大堆運算。只要你給出一個新點，經過計算，就會得出一個相對應的 LOF 值。若果它少於或等於 1，該點很大機會屬於模型中的某一類別，反之，該點則很大機會是異類 (outlier / anomaly)。以下圖片來自維基百科，可見當 LOF 越大，它就越不屬於大類別中的成員：