Tuesday, November 10, 2020

kNN,DBSCAN 及 LOF 初探

簡介
機器學習其中一個最實用的功能,就是分門別類 (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 越大,它就越不屬於大類別中的成員:

計算方法:

假設新點為 a,首先計算 LRD (Local Reachability Density):

LRD = k / (sum of reachabilityDistances to from a to all points)

當中 reachabilityDistance(a,b) = max({distanceToKthNearestNeighbor(b), manhattanDistance(a,b)},而 manhattanDisance 可以轉換成 Euclidean Distance。

最後,計算 LOF (Local Outlier Factor):

LOF(a) = [(sum of LRD of all points) * (sum of reachabilityDistance of all points)] / k^2

(不必認真理解,當黑盒使用即可。如果想理解,建議看原論文,或博客解釋)

Python 應用可參考此頁

小結
是次介紹的三個算法,因為比較相關,而且頭兩個比較容易理解,所以在機器學習界的應用也甚廣。不過,這個世界實在有太多 clustering 的算法,而每個算法都有其好壞,所以有時間的話,不妨多試幾個,再決定是否適合自己的應用場景(反正 Python 實例太多,操作上也不難)。

---

參考:

[1] - https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

[2] - https://en.wikipedia.org/wiki/DBSCAN

[3] - https://medium.com/@doedotdev/local-outlier-factor-example-by-hand-b57cedb10bd1

[4] - https://en.wikipedia.org/wiki/Local_outlier_factor

[5] - https://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf

[6] - https://pyod.readthedocs.io/en/latest/