可快速探勘封閉頻繁物品集且毋需產生中繼物之演算法

Abstract

探勘封閉頻繁物品集在資料探勘的領域中已經被廣泛的研究。自從關聯規則被提出後，探勘頻繁物品集就成為了重要的研究課題，而探勘頻繁物品集的問題在於使用記憶體的空間太多，為了減少記憶體的使用量，探勘封閉頻繁物品集的研究也就問世了。 封閉頻繁物品集不僅能夠保留完整的頻繁物品集的資訊，還能減少記憶體的使用量，此外封閉頻繁物品集也能提供完整且無累贅的關聯規則結果。在本篇論文中提出了CLOFI，一個快速探勘封閉頻繁物品集的演算法。CLOFI運用不同條件下的子資料庫保留必要的資訊來產生封閉頻繁物品集，並且使用了two-way extension check技術來檢查找到的物品集是否為封閉頻繁物品集，因為以上兩種技術，CLOFI得以產生封閉頻繁物品集而不用產生中繼物。 在評估實驗的部份會拿CLOFI和之前論文的演算法CLOSET+來做比較，我們用了幾個資料庫來做實驗，其中包含真實和合成的資料庫。最後將實驗結果的時間和記憶體使用量做分析，並且發現其中代表的含義。

Closed frequent itemsets mining has been widely studied in data mining research. Since association rules mining proposed, frequent itemsets mining became an important research issue. The problem of frequent itemsets mining is that the memory consumption is too high. In order to reduce the memory consumption, closed frequent itemsets mining has proposed. Closed frequent itemsets can not only keep the complete information like frequent itemsets but also reduce the consumption of memory. Furthermore, it provides complete and non-redundant results for mining association rules. In this thesis we present CLOFI, a fast algorithm for mining closed frequent itemsets. It uses conditional databases to keep the necessary information for enumerating closed frequent itemsets. It also uses two-way extension check technology to check the finding itemset is closed frequent itemset or not. According to above two techniques, CLOFI can mine closed frequent itemsets without candidate generation. The performance which CLOFI compares with previous work CLOSET+ shows in experiment evaluation. We use several databases including both real and synthetic databases in the experiments. Finally we have shown the significance of the experiment results, including time and memory consumptions.