李瑞庭Lee, Anthony J.T.臺灣大學:資訊管理學研究所王春笙Wang, Chen-ShengChen-ShengWang2010-05-052018-06-292010-05-052018-06-292007U0001-1812200714364300http://ntur.lib.ntu.edu.tw//handle/246246/179823在本論文中，我們針對探勘跨交易關聯規則，提出了二個有效率的演算法，稱為ITP-Miner (Inter-Transaction Patterns Miner)以及CITP-Miner (Closed Inter-Transaction Patterns Miner)。我們對這二個演算法設計了三種資料結構： ID-pair儲存跨交易樣式探勘所需的資訊； ITP-tree能夠列舉並找出所有的頻繁跨交易樣式；以及CITP-tree能夠列舉並找出所有的封閉式頻繁跨交易樣式。TP-Miner演算法使用ID-pair以及ITP-tree以探勘所有頻繁跨交易樣式。由於使用了ITP-tree，ITP-Miner只需讀取資料庫一遍並且將合併，修剪，及支持度的計算限定於少量的ID-pair。實驗結果顯示ITP-Miner演算法比FITI演算法快了數十倍。ITP-Miner演算法使用ID-pair以及CITP-tree以探勘所有封閉式頻繁跨交易樣式。由於使用了CITP-tree，CITP-Miner能夠使用有效的修剪策略以避免耗時的候選樣式產生以及重覆的支持度計算。實驗結果顯示CITP-Miner演算法比FITI以及ClosedPROWL演算法快了數十倍。外，我們比較ITP-Miner以及CITP-Miner演算法，由於CITP-Miner使用有效的修剪策略找出封閉式頻繁跨交易樣式，而封閉式頻繁跨交易樣式的數量通常少於ITP-Miner所找出所有的頻繁跨交易樣式，所以實驗結果顯示在大部份的情況下，CITP-Miner演算法執行時間較ITP-Miner演算法快，然而卻會消秏較多的記憶體。In this dissertation, we propose two efficient algorithms, called ITP-Miner (Inter-Transaction Patterns Miner) and CITP-Miner (Closed Inter-Transaction Patterns Miner), for mining inter-transaction association rules. We devise three data structures for both algorithms: an ID-pair stores the information used to find inter-transaction patterns; an ITP-tree enumerates and discovers frequent inter-transaction patterns; and a CITP-tree enumerates and discovers closed frequent inter-transaction patterns.he ITP-Miner algorithm uses the ID-pairs and the ITP-tree to mine all frequent inter-transaction patterns. By using the ITP-tree, the ITP-Miner requires only one database scan and can localize joining, pruning, and support counting to a small number of ID-pairs. The experiment results show that the ITP-Miner algorithm outperforms the FITI (First Intra Then Inter) algorithm by one order of magnitude.he CITP-Miner algorithm uses the ID-pairs and the CITP-tree to mine all closed frequent inter-transaction patterns. By using the CITP-tree, the CITP-Miner can embed effective pruning strategies to avoid costly candidate generation and repeated support counting. The experiment results show that the CITP-Miner algorithm outperforms the FITI and ClosedPROWL algorithms by one order of magnitude.e also compare the ITP-Miner and CITP-Miner algorithms. Since the CITP-Miner uses effective pruning strategies for mining all closed frequent inter-transaction patterns, and the number of patterns mined by the CITP-Miner may be much less than that mined by the ITP-Miner, the experiment results show that in most of the cases, the CITP-Miner algorithm outperforms the ITP-Miner algorithm in terms of execution time, but it consumes more amount of main memory.Table of Contents iist of Figures iiiist of Tables vhapter 1 Introduction 1.1 Motivations 4.2 Contributions 6.3 Dissertation Layout 7hapter 2 Background and Literature Survey 8.1 Association Rule Mining 8.2 Inter-transaction Association Rule Mining 10.3 Closed Pattern Mining 11hapter 3 Preliminaries and Problem Definitions 14hapter 4 Mining Frequent Inter-transaction Patterns 18.1 The ID-pair and ITP-tree 18.2 Main Concept 20.3 The ITP-Miner Algorithm 24.4 Memory Management of the ITP-Miner 27.5 Complexity Analysis of the ITP-Miner 28.6 Correctness of the ITP-Miner Algorithm 29.7 An Example 30hapter 5 Mining Closed Frequent Inter-transaction Patterns 34.1. CITP-tree and Joinable Class 34.2. Join Operation 35.3. Pruning Strategies 36.4. The CITP-Miner Algorithm 38.5. Memory Management of the CITP-Miner 41.6 Complexity Analysis of the CITP-Miner 42.7 Correctness of the CTIP-Miner Algorithm 43.8. An Example 44hapter 6 Performance Evaluation 47.1 Complexity Analysis of the Comparing Algorithms 47.2 Generation of Synthetic Datasets 49.3 Descriptions of Real Datasets 50.4 Descriptions of “Worst case” Datasets 51.5 Performance Analyses of the ITP-Miner and CITP-Miner Algorithms 51.5.1 Experiments on the synthetic data 53.5.2 Experiments on the real data 60.5.3 Experiments on the “worst case” data 63.5.4 Experiments on the disk-based algorithms 64hapter 7 Conclusions and Future Work 67eferences 72application/pdf611853 bytesapplication/pdfen-US關聯規則封閉項目集資料探勘跨交易關聯規則Association rulesClosed itemsetData miningInter-transaction association ruleshttp://ntur.lib.ntu.edu.tw/bitstream/246246/179823/1/ntu-96-D91725001-1.pdf