# Data Mining Lab 1
## Read on HackMD
真心建議用這個連結看心情會比較好 :100:
[https://hackmd.io/@alankingdom/HkBTL-GBo](https://hackmd.io/@alankingdom/HkBTL-GBo)
## Author
311551044 徐煜倫
## Hardware & OS & Python
CPU｜ R7-3700X
Mem｜ DDR4 3600 48G
SSD｜ MX500
OS ｜ Ubuntu 22.04
Python ｜ 3.10.6
## How to run my code
1. 創建存放資料集的目錄，並將資料集生成後放到對應目錄
```bash
mkdir -p dataset/datasetA
mkdir -p dataset/datasetB
mkdir -p dataset/datasetC
```
你應該會看到下面這個結果
📦dataset
┣ 📂datasetA
┃ ┣ 📜datasetA.conf
┃ ┣ 📜datasetA.data
┃ ┗ 📜datasetA.pat
┣ 📂datasetB
┃ ┣ 📜datasetB.conf
┃ ┣ 📜datasetB.data
┃ ┗ 📜datasetB.pat
┗ 📂datasetC
┃ ┣ 📜datasetC.conf
┃ ┣ 📜datasetC.data
┃ ┗ 📜datasetC.pat
2. 創建虛擬環境並下載python相依套件
```bash
python3 -m venv dmhw1
```
```bash
. ./dmhw1/bin/activate
```
```bash
pip3 install -r requirements.txt
```
3. 執行`transform.py`以獲取清理後的`dataset.csv`
> 需要手動更改程式碼中對應的檔案名稱
```bash
python3 transform.py
```
你應該會看到`datasetA.csv`, `datasetB.csv`, `datasetC.csv`在當前目錄之下
4. 如果想要執行全部的資料集與各種`minSupport`，可以使用我撰寫好的`run.sh`
```bash
chmod +x run.sh && ./run.sh
```
5. 如果只需要執行單次python檔案，可以使用如下指令：
```bash
python3 apriori.py -f datasetA.csv -s 0.05
```
6. 執行完畢`./run.sh`之後會看到生成logs資料夾與`result{1,2}.txt`，而logs資料夾內會存放著時間的紀錄，格式如下：
```txt=
Task1 Elapsed 90.271710s
Task2 Elapsed 90.161009s
Step2 task2/task1 ratio: 99.877368%
Step3 Elapsed 3.927501s
Step3 (step2 - step3) / step2 ratio: 95.649245%
```
## Explaination
### Step 2 - Refactor
對於`Task1`和`Task2`，我選擇使用python作為本次開發的語言，而為了滿足spec上面的要求，我進行了一些更改。
首先，遇到的第一個問題是很容易混淆`step`與`task`，並且原先的程式碼難以進行自動化，所以我進行了重構，並且加上了`typing`，方便辨識。
可以看見對於同一個`dataset`，我將任務分為三個種類：
1. runFrequentItemset
2. runFrequentClosedItemset
3. runFPGrowthItemset
每一個函數內都有計時功能，並且在執行結束之後返回演算法執行時間，方便做後續計算時間的任務。
### Step 2 - Tasks
#### Task 1 - itemset list
為了能夠將Frequent Itemset寫入檔案，我們需要將`printResult`函數做一些修改，方便我們重複呼叫。
同樣為了避免混淆，我將`printResult`重新命名為`printItemsetList`，並且加上了`typing`。
其中比較重要的改動為：
* 將`print`改成寫入檔案
* 寫入檔案的名稱將根據`step`, `task`, `dataset`, `minSupport`而有所不同。
* 因為要根據`minSupport`由大到小來做排序，所以在sort函數內加上`reverse=True`
* 助教有在new E3上面發布`Itemset`的格式為大括號，內部為以逗號區隔開的數字列表，這就是`display`變數做的事情。
* 助教也有要求要四捨五入`support`到小數點第一位，但是發現python的`format`函數格式化預設是無條件捨去，所以最後只能用`round`去做四捨五入。
#### Task 1 - statistics file
另外，我們需要顯示出candidate在pruning前後的差異，所以我在`runApriori`函數裡面新增了一個`stats`陣列，用以儲存pruning前後的候選集大小變化。需要特別注意的是，在進入while迴圈之前是`k=1`的情況，所以也要記得再`append`一次。
至於寫入檔案的部份由於跟itemset list多有重疊，所以就不再贅述，這邊展示如何將陣列寫入檔案的主要邏輯。
#### Task 2 - frequent closed itemset
Task2的主要任務是計算`Frequent Closed Itemset`。顧名思義，要符合這個條件，我選擇先使用一次`runApriori`取得`Frequent Itemset`，之後再基於`Frequent Itemset`去找`Closed pattern`。
所謂`Closed pattern`，簡單以一句話來解釋就是 **「如果一個itemset增加任何一個item他的support都會變低，那他就是closed patterns 」**。所以基於這個原理，我們以一個$O(n^2)$的簡易算法去取得同時滿足`Frequent`且`Closed`的集合。
算法可以表示如下：
```pseudo=
// 先拿到frequent Itemset
items := getFrequentItemset()
for cur, curSupport in items:
flag = True
for superset, supersetSupport in items:
// 不是superset的子集，就跳過
if cur is not subset of superset:
continue
// 檢查是不是滿足任意一個超集的支持度都沒有比cur大
if curSupport <= supersetSupport:
flag = False
break
// 如果能進到這個if代表說
// 這個超集的每一個超集的support都比目前這個集合還低
// 那他就是frequent closed itemset
if flag is True:
add cur, curSupport to list
```
如果對應到python，則如下：
### Step2 - Anaylsis
以下我們針對不同的資料集與不同的最小支持度來做一些分析。
首先，我們看一下不同組合的運行時間：
* datasetA minSupport=5%
* datasetA minSupport=7.5%
* datasetA minSUpport=10%
* datasetB minSupport=2.5%
* datasetB minSupport=5%
* datasetB minSupport=7.5%
* datasetC minSupport=2.5%
* datasetC minSupport=5%
* datasetC minSupport=7.5%
**這時候，奇怪的事情發生了！**
:::warning
:warning: 由於Task2基本上就是基於Task1再多了額外的運算，理論上應該時間會更長，我們應該要預期看到的時間比例都會大於100%，怎麼會有很多數值出現低於100%的呢？
:::
這是因為，我把讀檔與寫檔的時間也一起計入了，由於`Frequent Closed Itemset`的數量總是會小於等於`Frequent Itemset`，所以寫入檔案的資料較少，所費的時間就顯著的降低了。
為了驗證這個說法，我更改了計時函數的位置，只去計算演算法本身所費的時間，結果如下：
* datasetA minSupport=5%
* datasetA minSupport=7.5%
* datasetA minSUpport=10%
* datasetB minSupport=2.5%
* datasetB minSupport=5%
* datasetB minSupport=7.5%
* datasetC minSupport=2.5%
* datasetC minSupport=5%
* datasetC minSupport=7.5%
從改動後的結果可以知道，除了兩個結果依然呈現小於100%，但現在大部分計算的時間比例和我們的預期大致相符。而依然會出現低於100%的因素眾多，可能是因為CPU排程導致的問題，但因為時間相差甚微，故不多做討論。
**從這幾個實驗，我們可以得到以下結論：**
1. 其實額外計算`Closed Pattern`的開銷並不會很大，整體計算時間相除的比例不會超過10%。
2. 隨著資料集的增加(A->B->C)，所需的時間也增加，但並不是隨著資料集大小線性的增加。
3. 越小的minSupport，代表越容易篩選出更多的`Frequent Itemset`，所以計算時間也越多。花費時間和support也並非線性成長的關係，需要視資料集的特性而定。
### Step3 - FP-Growth
:::success
在step3，我選擇使用**non-candidate base**的演算法`FP-Growth`。而我使用的是[MLXTEND(Machine Learning Extensions)](https://github.com/rasbt/mlxtend)所開源的FP-growth算法。
:::
為了跟`Step2`做整合，所以同樣將任務包在function裡面：
但值得注意的有幾個地方：
1. 不可以用`Generator Type`，也就是變數`inFile`當作encoder的input，必須要先將他變成`List`。因為`mlxtend`預設會將資料轉為`one-hot encoding`，這個過程中會需要取`len()`，方便整合到其他算法裡面，如果是普通的iterator是不能取`len()`的，所以必須先將`Generator Type`讀到一個陣列裡面。
3. 也是因為這個套件需要跟sklearn等整合，所以出來的結果通常會是`pandas.DataFrame`，我們需要利用`iterrows`將其轉回跟上面step2相同的items格式。
#### FP-growth 實現方法比較與解析
為了從根本上了解FP-growth的演算法，我去參考了這幾個網站的教學，獲益良多：
https://zhuanlan.zhihu.com/p/67653006
https://flashgene.com/archives/121585.html
https://blog.csdn.net/w20001118/article/details/125320485
https://github.com/lxtGH/MachineLearning-1/blob/python-2.7/docs/12.%E4%BD%BF%E7%94%A8FP-growth%E7%AE%97%E6%B3%95%E6%9D%A5%E9%AB%98%E6%95%88%E5%8F%91%E7%8E%B0%E9%A2%91%E7%B9%81%E9%A1%B9%E9%9B%86.md
https://www.cnblogs.com/fengfenggirl/p/associate_fpgowth.html
看完上面這些教學，我簡單整理一下`Apriori`和`FP-growth`的主要差別：
| Apriori | FP-growth |
| -------- | -------- |
| 資料結構使用k-itemset | 使用FP Growth算法生出FP-tree |
| 會生成候選集 | 會為每一個item生成conditional FP-Tree |
| 每一步都要掃完全部的資料，非常耗時 | 建立FP-tree只要掃描一次資料即可 |
| 使用廣度優先搜尋(把k-itemset算完才找k+1) | 使用深度優先搜尋 |
而根據MLXTEND的原始碼，我們可以將他們實做的算法分成三個步驟：
1. 給定`dataframe`，生成`fp_tree`
3. 使用遞迴算法執行`fpgrowth algorithm`
4. 生成itemsets
詳細流程如下
:::info
* 對於每一個數據集合，去計算他的`support`，如果`support`比`minSupport`來的小，那我們就把這個item丟棄。
* 先把item以`support`降序排序的方式，依序列出來
* 將數據集按照support大小順序重新排序一次，整理完之後丟棄那些`support`低於`minSupport`的。
* 讀取每一筆transaction，用一個header List來紀錄，裡面放著每一個1-itemset和他的support。
* 插入規則是，如果依序插入，而且順序相同，則每一個前綴節點的count+1，反之則創造一個新的子分支，count = 1。就像下面這個圖片中，我們讀入第二條記錄（z,x,y,s,t）,首元素z在FP樹中，FP樹中的結點z，count值增加，然後進行遞歸每次從當前的下一個元素開始訪問。由於第二個元素x不在FP樹中，在FP樹中創建對應的結點，然後在header中創建相應的指針。後續結點在x的結點分支後進行。指的注意的是r在訪問（z,r）時已經存在了，因此第一個r結點的next域指向這次的r結點。後續記錄以此類推直到構成完成FP-tree，也就是前面演算法裡面的`fpc.setup_tree`。
* 接下來我們要尋找Frequent Itemset，首先獲得頻繁項的前綴路徑，然後將前綴路徑作為新的數據集構建條件FP樹。然後在新的FP樹中獲得頻繁項並以此構建條件FP樹。如此反覆，直到條件FP樹中只有一個頻繁項為止，這個對應到算法裡面的`fpg_step`遞迴。
:::
### Step3 - Analysis
經過上面的解釋，我們可以了解到FP-growth是一個極具效率的演算法，只要掃描資料集兩次即可完成，我將以實際執行時間與speedup來展示其突出的效能：
* datasetA minSupport=5%
* datasetA minSupport=7.5%
* datasetA minSUpport=10%
* datasetB minSupport=2.5%
* datasetB minSupport=5%
* datasetB minSupport=7.5%
* datasetC minSupport=2.5%
* datasetC minSupport=5%
* datasetC minSupport=7.5%
這邊`speedup`百分比所代表的意義，就是這個數值越靠近100%，`FP-growth`的效能相比`Apriori`來說越突出。
**從這幾個實驗，我們可以得到以下結論：**
1. 當資料集較小時(datasetA)，帶來的性能提昇較為有限。
2. 跟`Apriori`算法類似，如果minSupport越小，所需要的計算時間也越多。
3. 以step2花費時間最多的`datasetC`+`minSupport=2.5%`來比較，`Apriori`花了442秒完成計算，而FP-growth只需要10秒左右。意味著這個算法省下了將近97.73%的計算時間，效果卓越。當資料集越大，我們越應該考慮使用`FP-growth`。
Sign in with Wallet
Connect another wallet