牛油貓的筆記

Friday, November 20, 2020

Principal Component Analysis (PCA) 初探

簡介
很多時候，當我們得到一大堆數據，要進行數據分析的時候，我們都會先篩選一些比較重要的變數，然後才把它們放進 Machine Learning 的算法當中，以節省電腦的運算時間。不過，當篩選出來的數據仍然很多，有時候就令人頭痛。到底有沒有方法，可以用一個變數去取代數個相似的變數呢？（例如「氣温」和「季節」很相近，可否結合成一個變數，例如「天氣」來代表呢？）

另一種情況，就是當我們得到一大堆數據，希望用 ML 做分辨系統，我們也會問：到底這個 project 的可行性有多高？數據之間是否存在著一些，可用 2D 或 3D 的圖表展示的規律？

面對這兩種情況，降維 (Dimensionality Reduction) 就能幫助我們達到以上的目的。這裏的「維度 (Dimension / Dimensionality)」是指變數（例如氣温、季節等）。而降低維度，正正就是指把 N 個變數，變成 K 個變數（當中 N >= K）。是次會以 PCA 算法作為例子，簡介一下到底大致原理是什麼，以及有什麼應用。

Principal Component Analysis (PCA) 的目的
顧名思義，這個算法的目的，就是要找出一大堆數據中最有代表性的 Vector（或者叫 Principal Component）。舉例來說，以下的 2D 例子中有五點，當中最有代表性的 vector 就是 (1/sqrt(2), 1/sqrt(2))，也就是藍色的箭頭：

算法的目的，就是從 2D 平面中，找出那條藍色箭頭，然後，以上五點大約的位置，就能以投影的方式，在 1D 的線上表示。正如下圖左下方的例子，原本 x(1) 需要以 2D (x2, x1) 的方法表示，但當找到藍色 vector 之後，就能以 1D，也就是 x(1) = m*(z1) 的方法表示（當中 m 代表長度）：

如此類推的話，即使原本變數有非常多個（例如 1600 個），只要使用 PCA 不斷投射，我們就可以將變數縮成數個（例如 2 個），然後用圖表去表示數據分布，如下圖所示，PCA 能找出一大堆國家，在 2D 平面下的分布情況：

PCA 的算法
既然 PCA 這麼實用，我們當然想了解它的原理與算法。不過由於它涉及到找出 eigenvectors 等等一大堆 linear algebra 的概念，以及一大堆數學證明，以下部分，只提到基本概念和步驟。詳細證明方法可以參考 CSDN 的文章。

基本概念：

PCA 的目的，在於找出所有投影平面／線中，可以產生最小總距離的兩支 vectors（正負）。
如下圖所示，世界中有超多的 vector，但我只想要 y=x 的那一支：

基本步驟（取自 Coursera）：

計算 covariance matrix，sigma = (1/m)*(x(i))*(x(i))^T
用 SVD 計算 eigenvector of matrix sigma，得出 [U, S, V]
抽取 U matrix 中的首 K 行，成為 U_reduced
得出 Z = U_reduced^T * x(i)

PCA 程式演示
由於 Python 中的 scikit 一早已經寫好了 PCA 的算法，我們可以直接使用，參見以下例子：
https://github.com/cmcvista/MLHelloWorld/blob/main/PCADimensionalityReduction.ipynb

---

參考：

[1] - Andrew Ng - Machine Learning Course in Coursera - https://www.coursera.org/learn/machine-learning/lecture/ZYIPa/principal-component-analysis-algorithm

[2] - https://zhuanlan.zhihu.com/p/37777074

[3] - https://medium.com/ai%E5%8F%8D%E6%96%97%E5%9F%8E/preprocessing-data-%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90-pca-%E5%8E%9F%E7%90%86%E8%A9%B3%E8%A7%A3-afe1fd044d4f

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])))
```
的原因。