封閉性跨交易頻繁項目集合之資料探勘

Abstract

跨交易關聯規則可代表不同交易中項目間的關係，而近年來有愈來愈多相關的探勘演算法被提出，然而這些演算法會產生相當多的跨交易頻繁項目集合。找尋封閉性跨交易頻繁項目集合可使探勘的過程更有效率。 因此，在本篇論文中我們提出了一個探勘演算法叫「ICMiner」，以找尋封閉性跨交易頻繁項目集合。我們的方法可分為兩個階段。第一階段，將原始的資料庫轉換成領域屬性集合，使得每一個頻繁項目的領域屬性形成一個集合。第二階段，利用ID-tree去列舉出所有的封閉性跨交易頻繁項目集合。藉由ID-tree進行資料探勘，我們可以避免產生候選樣式及重複計算支持度。因此，ICMiner可大幅提升了找尋跨交易頻繁項目集合的效率。實驗結果顯示，ICMiner比FITI與ClosedPROWL快上幾十倍。

Many algorithms have been proposed recently for finding inter-transaction association rules, which represent the relationships among itemsets across different transactions. Since numerous frequent inter-transaction itemsets will be generated, mining closed frequent inter-transaction itemsets can speed up the mining process. Therefore, in this thesis, we propose an algorithm, ICMiner (Inter-transaction Closed patterns Miner), to mine closed frequent inter-transaction itemsets. Our proposed algorithm consists of two phases. First, we convert the original transaction database into a set of domain attributes, datset, for each frequent item. Second, we enumerate closed frequent inter-transaction itemsets by using an itemset-datset tree, ID-tree. Mining closed frequent inter-transaction itemsets with an ID-tree, we can avoid costly candidate generation and repeatedly support counting. The experimental results show that our proposed algorithm outperforms the FITI and ClosedPROWL algorithms by one order of magnitude.