李瑞庭臺灣大學：資訊管理學研究所翁婉玉Weng, Wan-YuWan-YuWeng2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54361跨交易關聯規則可代表不同交易中項目間的關係，而近年來有愈來愈多相關的探勘演算法被提出，然而這些演算法會產生相當多的跨交易頻繁項目集合。找尋封閉性跨交易頻繁項目集合可使探勘的過程更有效率。 因此，在本篇論文中我們提出了一個探勘演算法叫「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.Table of Contents i List of Figures ii List of Tables iii Chapter 1 Introduction 1 Chapter 2 Problem Definition 3 Chapter 3 Mining Closed Frequent Inter-transaction Itemsets 6 3.1 Pruning Strategies 6 3.1.1 ID-tree and Joinable Class 6 3.1.2 Pruning Strategies 8 3.2 Join Operation 9 3.3 The ICMiner Algorithm 11 3.4 An Example 13 3.5 Diffsets for Optimization 16 Chapter 4 Performance Evaluation 19 4.1 Generation of Synthetic Data 19 4.2 Experiments on Synthetic Data 20 4.2.1 Basic Experiments 20 4.2.2 Scale-up Experiments 22 4.2.3 Effect of the Maximum Span 25 4.2 Experiments on Real Data 26 Chapter 5 Conclusions and Future Work 29 References 30474286 bytesapplication/pdfen-US資料探勘關聯規則跨交易項目集合封閉性項目集合data miningassociation rulesinter-transaction itemsetsclosed itemsetsotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54361/1/ntu-95-R93725018-1.pdf