---
# System prepended metadata

title: Data Mining Lab 1
tags: [FP-Growth, Apriori, Mining]

---

# Data Mining Lab 1

## Author
313581037 許哲瑜

## How to run my code in Step Ⅱ and Ⅲ.
1. run my code in Step Ⅱ

```sh
python step2.py -f datasetA.data -s 0.3 -p Step2_task1
```

* `-f` : dataset path。 預設值為 `datasetA.data`。
* `-s` : minimum support (%)。 預設值為 `0.1`。
* `-p` : output file dir path。 預設值為 ```./Step2_task1```。

2. 執行完上述指令後，會在 Step2_task1 資料夾中分別看到 `Step2_task1_datasetA_0.3_result1.txt` 、 `Step2_task1_datasetA_0.3_result2.txt` 、`Step2_task2_datasetA_0.3_result1.txt` 三個執行結果檔案，並在與 `step2.py` 同資料夾下的 `Step2_datasetA_0.3_log.txt` 檔案，是記錄**Task 1**與**Task 2**的執行時間與比例。

3. run my code in Step Ⅲ.
```sh
python step3.py -f datasetA.data -s 0.3 -p Step3_task1
```
* `-f` : dataset path。 預設值為 `datasetA.data`。
* `-s` : minimum support (%)。 預設值為 `0.1`。
* `-p` : output file dir path。 預設值為 ```./Step3_task1```。

4. 執行完上述指令後，會在 Step3_task1 資料夾中分別看到 `Step3_task1_datasetA_0.3_result1.txt` 執行結果檔案，並在與 `step2.py` 同資料夾下的 `Step3_datasetA_0.3_log.txt` 檔案，是記錄**FP-Growth Computation Time**的資訊。

5. 判斷正確性與分析執行時間 
```shell 
python correctness_analysis.py -r Step2_task1 -s Step3_task1
```
* `-r` : Step2 dirname。 預設值為 `Step2_task1`。
* `-s` : Step3 dirname。 預設值為 `Step3_task1`。
* `-l` : log dirname。 預設值為 ```log```。

6. 上述指令會將兩個資料夾中的 xxx_task1_datasetA_0.9_result1.txt檔案進行 Frequent Itemset的比較看是否正確，正確結果如下方圖1。5 之後會將log資料夾中的檔案進行效能分析（可以將第2步與第4步的xxx_log.txt檔案移到log資料夾中），並在與`correctness_analysis.py`檔案同資料夾下產生`Analysis_log.txt`，裡面記錄 Step2 與 Step3 分別運行的時間與比率，如圖2。
執行結果圖如下：
圖1:<img src=https://hackmd.io/_uploads/BJr8bn0gye.png/>
圖2:
<img src=https://hackmd.io/_uploads/ByPFZnAgJl.png/>



## Step II. - Mining the datasets generated in Step I using Apriori algorithm:

### Sept II. The modifications you made for Task 1 and Task 2 : 

#### 1. 修改讀取資料的函式 `dataFromFile` ：
> 由於 datasetA.data 的資料中，每一列的前三筆分別代表、第幾列、第幾列、ITEMS數量，因此在讀取資料時要記得過濾。
    
```py
def dataFromFile(fname):
    """Function which reads from the file and yields a generator"""
    with open(fname, "r") as file_iter:
        for line in file_iter.readlines():
            line = line.strip().split(" ")[3:] # 以空格切分資料，並過濾前三筆 SID TID NITEMS 不需要的欄位資訊
            record = frozenset(line) # frozenset可以將重複的資料刪除，且回傳一個無法再更動的集合
            yield record # yield是節省記憶體空間的用法
```
>[!Tip]
> * file_iter.readlines()： 可以將檔案內容根據\n讀取成一行一行的串列，可以用for迴圈取出每一行內容。
> * line.strip().split(" ")[3:] : 將每一行的內容去除換行符號後以空格切分，並過濾出前三筆資料。

#### 2. 新增計算運行時間的程式碼：
> 在Task1與Task2中都需要計算運行的時間：Count and show the whole computation time for this task (task independent)，因此在 ```if __name__ == "__main__"``` 中做了以下修改
```py
### Task 1 Mining all Frequent Itemset ###
start_task1 = time.time()
largeSet, candidate_counts, items = runApriori(inFile, minSupport)
end_task1 = time.time()
task1_time = end_task1 - start_task1
# Count the computation time for this task (task independent).
print(f"Task 1 Computation Time: {task1_time:.4f} seconds")

### Task 2 Mining all Frequent Closed Itemset ###
start_task2 = time.time()
# The aim for this task is to mine all Frequent Closed Itemset with computation as fast as possible.
closed_itemsets = find_closed_itemsets(items)
end_task2 = time.time()
task2_time = task1_time + end_task2 - start_task2
print(f"Task 2 Computation Time: {task2_time:.4f} seconds")

# how the ratio of computation time compared to that of Task 1: Task2 / Task1 * 100%
time_ratio = (task2_time / task1_time) * 100
print(f"Task 2 to Task 1 Time Ratio: {time_ratio:.2f}%")

# 將結果儲存起來
fname = options.input.split("/")[-1].split('.')[0]
with open('Step2_'+fname+'_'+str(options.minS)+'_log.txt', 'w') as file:
    # Print out the total number of frequent closed itemset.
    file.write(f"Task 1 Computation Time: {task1_time:.4f} seconds\n")
    file.write(f"Task 2 Computation Time: {task2_time:.4f} seconds\n")
    file.write(f"Task 2 to Task 1 Time Ratio: {time_ratio:.2f}%")
```
>[!Tip]
> * time.time():可以取得當下的時間，再進行相減後便可以得到運行時間。
> * task2_time = task1_time + end_task2 - start_task2：Task2 是使用 Task1 的結果在進行運算取得**Frequent Closed Itemset** ，因此要加上Task1的運行時間

#### 3. 修改一些 Apriori algorithm 相關的函式以符合作業需求 : 
* `returnItemsWithMinSupport` : 為計算輸入的項目集分別的 support 支持度，並篩選出那些滿足 minSupport 最小支持度要求的項目集 -> Frequent Itemsets
    ```py
    # 計算項目集的 support 支持度，並篩選出那些滿足 minSupport 最小支持度要求的項目集 -> Frequent Itemsets
    def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet):
        """calculates the support for items in the itemSet and returns a subset
        of the itemSet each of whose elements satisfies the minimum support"""
        _itemSet = set()
        localSet = defaultdict(int)
        minSupport = round(float(minSupport) / 100,3) # 輸入為 ％，因此要除 100
        for item in itemSet:
            for transaction in transactionList:
                if item.issubset(transaction): # 如果此 item 出現在這筆交易 transaction 中
                    freqSet[item] += 1
                    localSet[item] += 1

        for item, count in localSet.items():
            support = float(count) / len(transactionList) # 計算每一筆 item 的 support 支持度(出現的頻率)

            if support >= minSupport: # 如果大於設定的 minSupport (最小支持度)則保留起來，即為 Frequent Itemsets (頻繁項目集）
                _itemSet.add(item) 
        return _itemSet
    ```
    >[!Caution] 注意！！！
    > * **minSupport = round(float(minSupport) / 100,3)** : 由於指令輸入的 **minSupport** 是百分比的格式（％），因此要將數值處以100才會正確。
    > * 我一開始只有單純寫 minSupport = float(minSupport) / 100，在 datasetA_0.9的數據中會出現 minSupport 為 0.0090000002 的值！
    > 會導致 support 為 0.009 的 item 全部被刪除，進而出現錯誤的數量，因此要記得使用round進行浮點數的處理！

* `joinSet` : 為得到下一次的itemset的組合（ 擴展 ），沒有進行修改
    ```py
    # 得到下一次的itemset的組合（ 擴展 ）
    def joinSet(itemSet, length):
    """Join a set with itself and returns the n-element itemsets"""
    return set(
        [i.union(j) for i in itemSet for j in itemSet if len(i.union(j)) == length]
    )
    ```
* `getItemSetTransactionList` : 從輸入資料中取得每個集合中只有一個值的 itemSet，與所有的交易筆數 transactionList，並回傳 1-itemSets及所有的transactions，沒有進行修改
    ```py
    # 取得每個集合中只有一個值的 itemSet，與所有的交易筆數 transactionList
    def getItemSetTransactionList(data_iterator):
        transactionList = list()
        itemSet = set() # 集合的資料結構，不會出現重複的 item
        for record in data_iterator:
            transaction = frozenset(record)
            transactionList.append(transaction)
            for item in transaction:
                itemSet.add(frozenset([item]))  # Generate 1-itemSets 

        return itemSet, transactionList
    ```

* `runApriori` : 根據 Task 1: Mining all Frequent Itemset 中 (b) Result file 2 (statistics file)的需求，需要紀錄 apriori algorithm 中每一次運算的前後候選的itemset數量，因此我做了以下修改：
    > 1. ```candidate_counts = []``` : 用來記錄作業需求，方便後續寫檔案使用
    > 2. ```returnItemsWithMinSupport```：是 apriori algorithm 的核心，即將輸入的候選 itemset 根據 minSupport 來判斷是否符合頻繁項目集 Frequent Itemset，因次要在此函式前後紀錄 itemset 的數量。
    > 3. 另外作業有要求：The index of iteration starts from 1，因此我在 進入`while` 迴圈前有做一次紀錄: **`candidate_counts.append((1, num_candidates_before, num_candidates_after))`**
    ```py
    def runApriori(data_iter, minSupport):
        """
        run the apriori algorithm. data_iter is a record iterator

        apriori algorithm 是根據以下兩個性質來運作：
            1. 如果一個項目集是符合 minSupport 的 頻繁項目集，則他的所有子集合也是頻繁項目集。
            2. 相反來說，如果一個項目集不符合（就不是頻繁項目集）的話，即可以刪除不用再看（透過剪枝可以大幅減少計算）

        Return toRetItems:
         - items (tuple, support)
        """
        # 步驟一：生成候選項目集，從每個items只有一個開始。
        itemSet, transactionList = getItemSetTransactionList(data_iter)

        freqSet = defaultdict(int)
        largeSet = dict()
        candidate_counts = []

        num_candidates_before = len(itemSet)
        # which satisfy minSupport
        oneCSet= returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet)
        num_candidates_after = len(oneCSet)
        candidate_counts.append((1, num_candidates_before, num_candidates_after))

        currentLSet = oneCSet

        # 步驟二：逐步擴展候選項目集，直到計算完所有的可能，產生符合 minSupport 的 frequent itemsets
        k = 2
        while currentLSet != set([]):    
            largeSet[k - 1] = currentLSet

            # Generate next candidates by joining the current frequent itemsets
            currentLSet = joinSet(currentLSet, k)
            num_candidates_before = len(currentLSet)

            currentCSet= returnItemsWithMinSupport(
                currentLSet, transactionList, minSupport, freqSet
            )
            currentLSet = currentCSet
            num_candidates_after = len(currentLSet)

            # 儲存每一次修剪前後的itemset數量
            candidate_counts.append((k, num_candidates_before, num_candidates_after))
            #print("candidate_counts:",candidate_counts)
            k = k + 1


        def getSupport(item):
            """local function which Returns the support of an item"""
            return float(freqSet[item]) / len(transactionList)

        # 處理回傳結果，toRetItems 中包含每一個 frequent itemsets 與 該項目集的支持度 Support
        toRetItems = []
        for key, value in largeSet.items():
            toRetItems.extend([(tuple(item), getSupport(item)) for item in value])

        return largeSet, candidate_counts, toRetItems
    ```
    >[!Tip] 函式輸出：
    > * largeSet : 是所有 frequence Itemset，可以用len(largeSet)，來取得該資料集符合 minSupport 的筆數。
    > * candidate_counts : 即為 Result file 2 (statistics list)要求所需要的內容。
    > * toRetItems : 是根據 Result file 1 (itemset list) 要求所需要的內容，裡面會包含所有的frequence Itemset以及對應的Support數值

* `find_closed_itemsets` : 是根據 Task 2: Mining all Frequent Closed Itemset 中的需求，所額外建立的函式。
    > 1. 將 Task 1 所得到的`frequent Itemset`作為輸入。
    > 2. 裡用雙層迴圈遍歷所有Itemset，並判斷當前`item` 是否為其他`other_item`的**超集的子集**，並且該`item`的`support`與`other_item`的`other_support`相同，則當前項集**不是閉合的**。
    > 3. 最後判斷是否任然為閉合的，是則將其添加到閉合項集中。
    > 4. 作業要求：Please sort those frequent closed itemsets according to support (from large to small).所以要將**closed_itemsets**根據support進行排序，設定reverse=True可以由大到小排序。
    ```py
    # Task 2 - Frequent Closed Itemset
    # mine all Frequent Closed Itemset with computation
    def find_closed_itemsets(freq_items):
        closed_itemsets = []
        freq_dict = {frozenset(item): support for item, support in freq_items}

        for item, support in freq_dict.items():
            is_closed = True
            for other_item, other_support in freq_dict.items():
                # 該 item 是其他 freq_items的子集合，或有相同的支持度，則此 item 就不是 Frequent Closed Item
                if item != other_item and item.issubset(other_item) and support == other_support:
                    is_closed = False
                    break
            if is_closed:
                closed_itemsets.append((item, support))

        # Please sort those frequent closed itemsets according to support (from large to small).
        closed_itemsets.sort(key=lambda x: x[1], reverse=True)

        return closed_itemsets
    ```
    >[!Tip] 函式輸出：
    > * closed_itemsets : 包含了所有的 Frequent Closed Itemset，並且根據support值由大到小排序。

#### 4. 將上述的結果寫成檔案：

> 為了確保檔案名稱的一致性，我將數入參數進行以下處理，以取得資料集名稱與最小支持度
```py
fname = options.input.split('.')[0] # 取得輸入的資料及名稱
minSupport = options.minS 
```

* `weitefile_itemset` : 將```runApriori```函式的結果 toRetItems 與 fname、minSupport輸入，注意要求的suooort要以百分比表示。
    ```py
    # Task 1 / Result 1 / 
    # Print out all frequent itemsets with support (take percentage % and round to the first decimal place)
    def weitefile_itemset(items,fname,minSupport): 
        with open(options.path + '/Step2_task1_'+fname+'_'+str(minSupport)+'_result1.txt','w') as outfile:
            # sort those frequent itemsets according to support (from large to small).
            for item, support in sorted(items, key=lambda x: x[1], reverse=True):
                temp = ','.join(list(item))
                # take percentage % and round to the first decimal place
                support = round(support*100,1) 
                # File format (each frequent itemset): [support]\t[item_set]\n
                outfile.write("{:.1f}".format(support)+'\t{'+temp+'}\n') 
    ```
    >[!Note] 使用方式：
    > ``` weitefile_itemset(items,fname,minSupport) ```
    
* `save_statistics` : 將```runApriori```函式的結果 largeSet、candidate_counts 與 fname、minSupport輸入。
    ```py
    # Task 1 / Result 2 / 
    # the number of candidates generated before and after pruning
    def save_statistics(largeSet, candidate_counts,fname,minSupport):
        total_freq_itemsets = sum(len(v) for v in largeSet.values())
        with open(options.path + '/Step2_task1_'+fname+'_'+str(minSupport)+'_result2.txt', 'w') as file:
            # Print out the total number of frequent itemsets.
            file.write(f"{total_freq_itemsets}\n")

            # Print out the number of candidates generated before and after pruning, respectively, in each iteration of Apriori.
            for iteration, num_candidates_before, num_candidates_after in candidate_counts:
                # [index_of_iteration]\t[the number of candidates (before pruning)]\t[the number of candidates (after pruning)]\n
                file.write(f"{iteration}\t{num_candidates_before}\t{num_candidates_after}\n")
    ```
    >[!Note] 使用方式：
    > ``` save_statistics(largeSet, candidate_counts,fname,minSupport) ```

* `save_closed_itemsets` : 將```find_closed_itemsets```函式的結果 closed_itemsets 與 fname、minSupport輸入，，注意要求的suooort要以百分比表示。
    ```py
    # Task 2 / Mining all Frequent Closed Itemset
    def save_closed_itemsets(closed_itemsets,fname,minSupport):
        fname = options.input.split('.')[0]
        with open(options.path + '/Step2_task2_'+fname+'_'+str(minSupport)+'_result1.txt', 'w') as file:
            # [total number of frequent closed itemsets]\n
            file.write(f"{len(closed_itemsets)}\n")

            # [support]\t[item_set]\n
            for item, support in closed_itemsets:
                support_percentage = round(support * 100,1) #take percentage % and round to the first decimal place
                item_list = '{'+','.join(item)+'}'
                file.write(f"{support_percentage}\t{item_list}\n")
    ```
    >[!Note] 使用方式：
    > ``` save_closed_itemsets(closed_itemsets,fname,minSupport)```

    
### Sept II. Computation time and Anaylsis : 

以下針對不同的資料集與不同的最小支持度來做一些分析，其中冒號後方的數字為Frequent Itemset的總數量。

- In datasetA with minimum support 0.3% : 7776
<img src=https://hackmd.io/_uploads/HkWreA0xke.png/>
- In datasetA with minimum support 0.6% : 909
<img src=https://hackmd.io/_uploads/BJXwlARlkg.png/>
- In datasetA with minimum support 0.9% : 414
<img src=https://hackmd.io/_uploads/rybYeARgkg.png/>
- In datasetB with minimum support 0.2% : 5820
<img src=https://hackmd.io/_uploads/Sk3se0Aeke.png/>

- In datasetB with minimum support 0.4% : 1445
<img src=https://hackmd.io/_uploads/B1bTxA0xJg.png/>

- In datasetB with minimum support 0.6% : 667
<img src=https://hackmd.io/_uploads/H1cClARg1g.png/>

- In datasetC with minimum support 0.5% : 991
<img src=https://hackmd.io/_uploads/Sk31b00xJx.png/>

- In datasetC with minimum support 1.0% : 356
<img src=https://hackmd.io/_uploads/B16gWARgke.png/>

- In datasetC with minimum support 1.5% : 247
<img src=https://hackmd.io/_uploads/ByC-ZRRgJl.png/>

以上的時間計算皆不包含寫入檔案所花費得時間。

### Sept II. observations/discoveries :
1. 根據上述的實驗結果顯示，Task 2 利用 Task 1的結果再進行額外的運算，花費的時間會根據Frequent Itemset的總數量來增加，不過所額外花費的時間非常少，兩者運行時間的比例都接近100%左右。
2. 在同一份資料集中，可以發現 minimum support 的數值設定越小，符合的Itemset越多，在 apriori演算法下每次迭代得量也越多，因次花飛的時間也大幅增加。
3. 隨著資料集的筆數增加(datasetA->datasetB->datasetC)，所需的時間也會大幅增加，但也是要根據資料集的特性、分佈而定，並不是線性成長的關係。
4. 另外如上方紅色注意區塊顯示，minimum support數值計算中浮點數位元的問題，造成結果根本依據不是我們所設定的minimum support。這是我在做完sept3後回去對照時才發現！前前後後花費了不少時間成本重新計算，下次要更加小心才行。




## Step III. - Mining the datasets generated in Step I using Apriori algorithm:

我採用了**FP-Growth** 演算法來mining 頻繁項目集 Frequent Itemset。
FP-Growth 是一種非候選集生成（Non-Candidate-based）的演算法，通過構建 **頻繁模式樹（FP-Tree）** 來壓縮交易數據並進行模式挖掘。

我根據下方的網頁來學習並建立 FP-Growth algorithm：
> 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://medium.com/@tinahuang_4101/associating-rule-%E9%97%9C%E8%81%AF%E5%BC%8F%E6%B3%95%E5%89%87%E6%87%89%E7%94%A8-apriori-fp-growth-3ab46deeeb77

### FP-Growth algorithm 的 基本流程：
> FP-Growth 主要分成兩大步驟，首先是建立 FP-Tree，再來就是從建立好的FP-Tree計算得到Frequent Itemset，於是我便照著流程寫出對應的函式。
1. 首先計算每個項目的支持度，並保留那些支持度超過最小支持度閾值的項目。
    ```py
    # 預處理交易數據
    def preprocess_transactions(data_iterator, min_support):
        transactionList = list()
        item_counts = defaultdict(int)
        for record in data_iterator:
            transaction = frozenset(record)
            transactionList.append(transaction)
            for item in transaction:
                item_counts[item] += 1 # 計算該 item 出現在交易數據中的次數

        # 計算 最小支持度的閾值 ( min_support(%) / 100 * 交易數據比數)
        min_support = round(min_support / 100 * len(transactionList),3)

        # 過濾掉低於最小支持度的項目
        items = set(item for item, count in item_counts.items() if count >= min_support)

        # 移除非頻繁項目，並對剩下的項目進行排序
        # 將所有交易中的項目按照支持度從高到低進行排序（高頻項目先排序），這樣具有相同前綴的交易可以共享樹中的節點。
        processed_transactions = []
        for transaction in transactionList:
            processed_transaction = [item for item in transaction if item in items]
            processed_transaction.sort(key=lambda item: (-item_counts[item], item), reverse=True)
            if processed_transaction:
                processed_transactions.append(processed_transaction)
        return processed_transactions, len(transactionList)
    ```
    >[!Important] 設定穩定排序
    > * processed_transaction.sort(key=lambda item: (-item_counts[item], item), reverse=True)
    > 
    > 在相同的support數值下，根據項目名稱的數字順序進行次要排序，這樣可以穩定FP-Tree 的建立。
    > 如果沒有這樣處理，會導致每次執行的結果都不相同！
2. 構建 FP-Tree：對每筆交易進行排序，將頻繁項目按支持度排序後插入 FP-Tree。
    > 這裡根據作業要求對開源的 FP-Growth 基礎程式碼 `fpgrowth.py` 進行了以下修改：

    * **表頭鏈結改進**：在 `FPTree` 類別中，添加了 `headers` 字典來記錄每個項目的節點鏈接，便於快速建立條件模式基。
    * 穩定排序：在多處排序中增加了穩定排序的條件，確保多次執行結果的一致性 : `items = sorted(tree.headers.items(), key=lambda x: (sum(node.count for node in x[1]),x[0]))`
    * **輸出結果格式**：作業要求，並增加了支持度百分比的計算，並且存取和調整需要的輸出資料 : `frequent_patterns[tuple(new_pattern)] = support`。
    ```py
    from collections import defaultdict, namedtuple
    from itertools import chain, combinations

    # 建立 FP Tree 的節點：
    # 可以表示每個節點的計數
    class FPTreeNode:
        def __init__(self, item, count, parent):
            self.item = item
            self.count = count
            self.parent = parent
            self.children = {}
            self.link = None  # 用於節點間的鏈接

        def increment(self, count):
            self.count += count

    # 建立 FP Tree：     
    class FPTree:
        def __init__(self):
            self.root = FPTreeNode(None, 1, None)
            self.headers = defaultdict(list)  # 每個項目的表頭

        # insert 將交易資料輸入到樹的資料結構中 
        def add_transaction(self, transaction, count):
            current_node = self.root
            for item in transaction:
                if item not in current_node.children:
                    # 創建新節點
                    new_node = FPTreeNode(item, count, current_node)
                    current_node.children[item] = new_node
                    # 更新表頭鏈接
                    self.headers[item].append(new_node)
                else:
                    current_node.children[item].increment(count)
                current_node = current_node.children[item]

        def is_single_path(self, node=None):
            if node is None:
                node = self.root
            while len(node.children) == 1:
                node = next(iter(node.children.values()))
            return len(node.children) == 0

    # FP-Growth 遞歸挖掘
    def get_fpgrowth(tree, min_support, suffix, frequent_patterns):
        items = sorted(tree.headers.items(), key=lambda x: (sum(node.count for node in x[1]),x[0]))
        for item, nodes in items:
            # 計算支持度
            support = sum(node.count for node in nodes)

            if support >= min_support:
                # print("support",support)
                # 發現頻繁項目集
                new_pattern = suffix + [item]
                frequent_patterns[tuple(new_pattern)] = support

                # 構建條件模式基
                conditional_tree = FPTree()
                for node in nodes:
                    path = []
                    parent = node.parent
                    while parent and parent.item is not None:
                        path.append(parent.item)
                        parent = parent.parent
                    path.reverse()

                    if path:
                        conditional_tree.add_transaction(path, node.count)

                # 遞歸查找子樹的頻繁模式
                if conditional_tree.root.children:
                    get_fpgrowth(conditional_tree, min_support, new_pattern, frequent_patterns)

    ```
    使用以下程式碼，將欲處理好的交易資料加入到 FP-Tree 中
    對於每筆交易，逐項插入 FP-Tree，並使用 `headers` 字典鏈接每個相同項目的節點。
    ```py
    # 構建 FP-Tree
    tree = FPTree()
    for transaction in processed_transactions:
        tree.add_transaction(transaction, 1)
    ```
3. 使用條件模式基（Conditional Pattern Base）來生成條件 FP-Tree，並遞歸地從子樹中挖掘頻繁模式。
    - 針對每個項目生成條件模式基，並構建子 FP-Tree。
   - 遞歸地對條件 FP-Tree 進行頻繁項目集挖掘，直到所有頻繁項目集均被找到。
   - 透過上方定義好的 `get_fpgrowth` 函式進行。
    ```py
    # 挖掘頻繁模式
    min_support = int(min_support / 100 * lengh)
    frequent_patterns = {}
    get_fpgrowth(tree, min_support, [], frequent_patterns)
    ```

4. **結果輸出**：
   - 將所有頻繁項目集及其支持度以指定格式輸出。
   ```py
    # Task 3 / Result 1 / all frequent itemsets 
    def weitefile_itemset(items,lengh,fname,minSupport): 
        # fname = "T10I6001M"
        with open(options.path + '/Step3_task1_'+fname+'_'+str(minSupport)+'_result1.txt','w') as outfile:
            for item, support in sorted(items.items(), key=lambda item: item[1], reverse=True):
                temp = ','.join(list(item))
                support = round(support/lengh*100,1) # take percentage % and round to the first decimal place
                outfile.write("{:.1f}".format(support)+'\t{'+temp+'}\n')   
    ```

### FP-Growth 演算法的改進與優勢（Differences/Improvements compared to Apriori）

FP-Growth 比 Apriori 更高效的原因

- **無需生成候選項目集**：FP-Growth 無需生成候選項目集，而是使用 FP-Tree 直接在壓縮後的樹結構中進行模式挖掘，極大地減少了內存和計算資源的消耗。
- **條件模式基的遞歸挖掘**：FP-Growth 的條件模式基（Conditional Pattern Base）和遞歸結構允許它針對頻繁模式進行逐層分解和處理，從而避免了重複計算。
- **空間利用率更高**：FP-Tree 通過壓縮交易資料來節省內存，特別是當多筆交易具有相同或部分重疊的項目時，FP-Tree 可以顯著降低空間複雜度。

- **效率提升**：FP-Growth 避免了在每一階段產生大量候選項目集的計算開銷，特別是在數據量大的情況下效率更高。


>FP-Growth 在處理大數據集方面的擴展性良好，但依然會受制於記憶體資源。以下是演算法在數據集規模擴展時的效能變化：

- **計算時間隨數據量的變化**：FP-Growth 的運行時間隨數據量增加而增加，尤其在頻繁項目較多的情況下。但相較於 Apriori，FP-Growth 的時間增長更為平緩，對大數據的擴展性更優。
- **支持的最大數據集大小**：在典型的 16 GB 記憶體環境下，FP-Growth 可處理數百萬條交易記錄的大型數據集。當數據集規模繼續擴大時，可以考慮分散式 FP-Growth 以處理更大的數據集。

>FP-Growth 透過 FP-Tree 壓縮數據並進行高效的遞歸模式挖掘，適合於大規模數據分析。

### Sept III. Computation time and Anaylsis : 

以下針對不同的資料集與不同的最小支持度來做一些分析，其中冒號後方的數字為Frequent Itemset的總數量。

- In datasetA with minimum support 0.3% : 7776
<img src=https://hackmd.io/_uploads/HklRVkkWyl.png/>

- In datasetA with minimum support 0.6% : 909
<img src=https://hackmd.io/_uploads/S1-xHk1Wyg.png/>

- In datasetA with minimum support 0.9% : 414
<img src=https://hackmd.io/_uploads/SyIbBykZ1e.png/>

- In datasetB with minimum support 0.2% : 5820
<img src=https://hackmd.io/_uploads/HJ3GHk1Wyx.png/>


- In datasetB with minimum support 0.4% : 1445
<img src=https://hackmd.io/_uploads/B10QB11W1g.png/>


- In datasetB with minimum support 0.6% : 667
<img src=https://hackmd.io/_uploads/B1_BHkk-Jx.png/>

- In datasetC with minimum support 0.5% : 991
<img src=https://hackmd.io/_uploads/ry1wH1y-yx.png/>


- In datasetC with minimum support 1.0% : 356
<img src=https://hackmd.io/_uploads/rye_rk1Wyl.png/>


- In datasetC with minimum support 1.5% : 247
<img src=https://hackmd.io/_uploads/r1ZFSkyWJe.png/>


以上的時間計算皆不包含寫入檔案所花費得時間。

從這些結果中可以看出，**FP-Growth 演算法（Step 3）在處理大型數據集時相比 Apriori（Step 2）所花費的時間大幅減少，但跟Apriori算法類似，如果minimum Support越小，所需要的計算時間也越多。**


#### 分析結果

- **Dataset A**：FP-Growth 在 `datasetA` 中加速達 96.3% 到 98.7% 不等，尤其在較低支持度（0.3%）的情況下達到最大加速效果。
- **Dataset B**：FP-Growth 在 `datasetB` 中的加速比也顯著，在 0.2% 的支持度下加速達 99%，隨著支持度增加，加速比稍微下降，但仍在 97% 以上。
- **Dataset C**：對於更大的數據集 `datasetC`，FP-Growth 的加速效果依然穩定，保持在 96.4% 到 97.7% 之間。
 


- **隨著數據集規模擴大**，FP-Growth 依然能夠保持高效的計算速度。從 `datasetA` 到更大的 `datasetB` 和 `datasetC`，FP-Growth 的加速效果仍穩定在 96%-99% 之間。
- **支持的最大數據集大小**：FP-Growth 在處理百萬級以上的交易數據時表現良好，但在數據集更大時可能需要更大的內存空間，特別是當頻繁項目集增多時。若數據集進一步增大，可以考慮分散式 FP-Growth 演算法以支持更大規模的數據集。
