牛油貓的筆記

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/

Monday, November 9, 2020

LSTM 初探

簡介
傳統機器學習只找出每點數據中的規律，並不考慮時間相關性。例如，今天的天氣，其實很大機會會與明天的天氣相關（假設天氣突變並不常見）。又例如，在一句句子當中，若我們得到前面的句子，我們很容易會猜到下一句的內容（例如 Mary is a _，因為看到 Mary，我們能夠很快估計出，空格應該是 Girl 或者 Lady 等名詞）。而 LSTM (Long Short Term Memory)，正正利用了不同的函數，幫助我們找出這些數據的前後之間的關聯性。

LSTM 極簡（忽略數學公式）解說
LSTM 由以下不同部分組成，使它同時擁有「短暫記憶」及「長期記憶」：

Input Gate：也就是新數據的入口，大約就是正常的記憶入口
Forget Gate：大約制定忘記多少上一個記憶
Output Gate：大約制定殘餘去 hidden state 的數據量，並輸出 output state

由此可見，每一粒 LSTM Cell 都會有自己的長期記憶（儲存在 W），而且它也會輸出一些殘餘記憶去 Hidden State，供下一個 cycle 輸入，以至不會完全「忘記」掉。而隨著時間，這些殘餘記憶將會慢慢因為有更多新數據而被「溝淡」。詳細數學公式解釋，可參考此頁。

（有一個動畫演示 LSTM 的網站也十分值得看一下）

實例：股票預測例子
假設今天的股票波幅與將來相若的話，LSTM 就可以用來推算將來的價格。

以下用 TensorFlow 演示：
https://github.com/cmcvista/MLHelloWorld/blob/main/LSTMExample.ipynb

解說：

因為我們假定今天的股價會與明天相若，所以，資料排序的時候，採取了這種排法：
輸入 x1, x11, x21 ... x91，得出 x2, x12, x22 ... x92
輸入的數據組為 [x1, x11, x21 ... x91]，[x2, x12, x22 ... x92]，[x3, x13, x23 ... x93] ⋯
故此，同一 LSTM Cell 將會先輸入 x1，然後下一個 cycle 輸入 x2，
這樣才能運用 LSTM 表達數據間的關係。
TensorFlow 輸入數據中，可以做到一個 batch 入面，數據有時間關係。
假設數據組為 [x1, x2 ... x10]，[x11, x12 ... x20]，你也可以設定 time step 為 10，
但是次例子中，我們並沒有用到這個功能，所以設置了 time step 為 1。
這個就是
```
train_X_reshaped = np.reshape(train_X, (len(train_X), 1, len(train_X[0])))
```
的原因。

筆者暫時仍未掌握得很好。但總括而言，用法大致如此。
其實 MATLAB 的做法更加直觀，詳情參見此頁。

參考

[1] - https://www.datacamp.com/community/tutorials/lstm-python-stock-market

[2] - https://www.analyticsvidhya.com/blog/2017/12/fundamentals-of-deep-learning-introduction-to-lstm/

[3] - https://www.tensorflow.org/guide/keras/rnn

[4] - https://www.mathworks.com/help/deeplearning/ug/long-short-term-memory-networks.html

[5] - https://towardsdatascience.com/animated-rnn-lstm-and-gru-ef124d06cf45

Thursday, November 5, 2020

Q-Learning 初探

簡介
強化學習 (Reinforcement Learning) 是一種透過嘗試做不同決策，然後根據所獲取的奬勵 (Rewards) 或懲罰 (Punishment)，找出最佳解 (Optimized Solution) 的算法。由於它採用分數奬勵的形式訓練，所以它特別適合玩迷宮、小遊戲、甚至訓練機器人走路這類「未必有絕對答案，只需完成目的」的應用。

強化學習與監督學習 (Supervised Learning) 有所不同的是：監督學習需要集齊不同迷宮的最佳解，然後讓系統在訓練模式中找出 hidden pattern。相反，強化學習並不需要有最佳解的數據庫：系統只需透過選擇性地嘗試，然後採取最低風險（最高回報）的做法，最後就能找出接近最佳解。

以下會利用 Q-Learning 作為例子，講解算式，最後會用一個程式例子演示。

使用「類 Markov Matrix」表示奬勵積分
以下內容，節錄自 A Painless Q-Learning Tutorial [1]。

假設有五間房，我需要設計一個使用 Q-Learning 離開房間的程式的話，我可以假設每一間房為一個 state （state 0 - 4 共五個 state），而「房間外」則為「State 5」，所以一共有六個 state：

然後，為了鼓勵人離開房間，每當離開所有房間（也就是去到 State 5），我都會奬勵它 100 分，其餘行動則獲得 0 分：

最後，我們可以用矩陣去表達這個 Markov Decision Chain，當中不存在的事件，我們之後會忽略掉不計。為了整齊，這裏暫時會用 -1 代表：

例子：
如果我在 State 1，想跳去 State 5，將會得到 100 分奬勵。
如果我在 State 2，想跳去 State 3，將會獲得 0 分奬勵。
如果我在 State 4，想跳去 State 1，我們會忽略這個情況，因為並不合法。

簡化版 Q-Learning 算式
定好了 Reward Table，就可以開始 Q-Table 演算。Q-Table 是一個儲存經驗值的矩陣，經過一輪運算，這個 Table 中的數值，將會幫助系統找出最佳解。

以下例子，會用簡化版 (learning rate = 1) 去講解：
（正常版的數式在 Wikipedia 中有提及，但由於比較複雜，所以不在此詳述）

運算步驟：

首先選一個起點（例子：State 2）和一個終點（離開房間 = State 5）
重覆以下步驟，直至到達終點為止：

用 Q-Table Equation 更新 Q-Table:

任意取下一點 S，獲取奬勵 R，
基於 S 點，找出 Q-Table 中最大數值的點（若同樣則任意選一點）

將 S 變成現時點，繼續重覆上一步

例子（假設 gamma 為 0.8）：

初始值 Q-Table 全為零。

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，但 Q-Table 中去三點 (Q(5,1), Q(5,4), Q(5,5)) 均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 3，然後從 S=(1,2,4) 中任意選一點，S=1，
基於 S=1，可以去 (3,5) 兩點，而 Q-Table 中 Q(1,3)=0, Q(1,5)=100，因選最大，所以選 5。
然後更新 Q Table 值：Q(3,1) = R(3,1) + 0.8*100 = 0+80 = 80
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 0，然後從 S=(4) 中任意選一點，S=4，
基於 S=4，可以去 (3,5) 兩點，而 Q-Table 中 Q(4,3) 和 Q(4,5) 均為零，
所以任意選 3，並更新 Q Table 值： Q(0,4) = R(0,4) + 0.8*0 = 0，
最後，將 S=4 變成現時點，繼續運算：

選取起點 State 4，然後從 S=(3,5) 中任意選一點，S=3，
基於 S=3，可以去 (1,2,4) 三點，而 Q-Table (Q(3,1), Q(3,2), Q(3,4)) 中，
因 Q(3,1)=80 為最大，所以選 1，並更新 Q-Table 值：Q(4,3) = R(4,3) + 0.8*80 = 64，
最後，將 S=1 變成現時點，繼續運算：

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，而 Q-Table (Q(5,1), Q(5,4), Q(5,5)) 中，三點均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

經過以上幾輪計算，得出以下 Q-Table 值：
Q(1,5) = 100 / Q(3,1) = 80 / Q(0,4) = 0 / Q(4,3) = 64

若果經過更多輪計算，不同數值將會繼續更新，
但最後，均會大約在以下結果中，開始收歛 (convergence)：