臺灣博碩士論文加值系統

關聯規則主要是要從交易資料庫中找尋物品間的關聯性。自Apriori演算法被提出後，時常有人提出新的演算法來改進。這些改進找尋關聯規則的演算法大多將重點放在兩方面：(1)減少搜尋與計算的時間(2)減少掃描交易資料庫的次數。過去某些研究為了有效達到這兩個目的，使用的方法會浪費很多記憶體，因此雖然在執行時間上的效能很好，但所需的記憶體空間甚至大到讓程式無法執行。所以我們提出新的觀念來加快尋找關聯規則的速度，並且不會浪費太大的記憶空間。我們觀察到找尋關聯規則的真正瓶頸是在於對交易的拆解次數，因此我們提出了一個能大量減少交易拆解次數的演算法-延遲交易拆解(Delay Transaction Disassemble，DTD)。其精神在於每一筆交易，只有當它所包含的交易項目有可能是我們所感興趣的項目時，我們才執行交易的拆解，因此其架構全然不同於Apriori演算法，我們使用模擬資料庫來進行實驗，以驗證在實際執行上的效能，而實驗的結果顯示，我們大量減少交易拆解的次數，的確能加快演算法的執行速度。另外，加權(Weighted)的關聯規則比一般的關聯規則多考慮了物品的在交易中的重要性，因此能比一般的關聯規則找出更多有利的資訊。但過去有關的加權的關聯規則的研究相當少且執行效能很差，因此我們提出一個權值延遲交易拆解(Weighted Delay Transaction Disassemble，WDTD)的演算法及高度平衡索引樹(AVL-index tree)來解決這方面的問題，並利用相同交易重疊處理的觀念來大幅加快演算法的執行速度和節省記憶體空間。我們從理論上分析我們的演算法與過去的演算法在執行速度與所需的記憶體空間的差異，並以模擬的資料庫進行實驗，證明我們的方法在執行速度上較過去的方法快很多。

Mining association rules is to find associations among items from large transaction databases. Weighted association rule is also to describe the associations among items, and the importance of each item is considered. Hence, weighted association rules can provide more information than that of association rules. There are many researchers that have proposed their algorithms for mining association rules. Apriori algorithm needs to scan database many times and cost much search time for mining association rules, which is very inefficient. Many other algorithms improved the efficiency of Apriori algorithm, but a lot of memory space need to be taken. There are few approached proposed for mining weighted association rules. The previous approaches also take a lot of time to scan database and search for the needed information.
In this thesis, we propose two new algorithms --- delay transaction disassemble (DTD) and Weighted Daley Transaction Disassembled (WDTD) for mining association rules and weighted association rules, respectively, which is very efficient and need not take much memory space. We observe that most of time spent for scanning the database is to disassemble each transaction in the database. The main idea of DTD and WDTD algorithms are that the transaction is not disassembled until it needs to be used. For mining weighted association rules, we also propose an AVL-index tree to store the transactions and the transaction overlap technique to further reduce the execution time and the memory space. The experimental results show that our algorithms outperform other algorithms for mining association rules and weighted association rules.

目錄
第一章緒論…………………………………………………….2
第一節研究動機………………………………………………………………..2
第二節研究目的………………………………………………………………..3
第三節論文架構………………………………………………………………..3
第二章問題說明與文獻探討………………………………….6
第一節問題說明………………………………………………………………..6
第二節文獻探討………………………………………………………………..7
第三章關聯規則演算法………………………………………16
第一節與DTD相關的定義…………………………………………………..16
第二節DTD演算法的主要架構……………………………………………...18
第三節DTD的資料結構………………………………………………………29
第四節DTD執行速度的理論分析與實驗結果………………………………31
第四章加權之關聯規則演算法………………………………36
第一節WDTD演算法的基本概念……………………………………………36
第二節WDTD演算法的相關定義……………………………………………37
第三節WDTD演算法的主要架構……………………………………………38
第四節WDTD儲存交易資料的資料結構……………………………………45
第五節交易疊合……………………………………………………………….48
第六節實驗結果……………………………………………………………….50
第五章多限制條件的關聯規則演算法………………………52
第六章結論……………………………………………………53

[1] R. Agrawal and et al.: Mining Association Rules Between Sets of Items in Large Databases. In Proceedings of ACM SIGMOD, page 207-216,1993
[2] R. Agrawal and et al.: Fast Algorithm for Mining Association Rules. In Proceedings of International Conference on Very Large Data Bases, pages 487-499, 1994.
[3] R. Agrawal and et al.: Database Mining: A Performance Perspective. In IEEE
Transactions on Knowledge and Data Engineering, page 914-925,1993.
[4] Rakesh Agrawal, and et al.: Mining Sequential Patterns. In Proceedings of International
Conference on Data Engineering, pages 3-14,1995.
[5] M.S. Chen , X.M. Huang, I.Y. Lin ” Capturing User Access Patterns in the Web for Data Mining.” In IEEE International Conference 1999.
[6] Ming-Syan Chen, Jong Soo Park, Philip S. Yu:Efficient Data Mining for Path Traversal
Patterns. Transactions on Knowledge and Data Engineering. IEEE 1998
[7] M.S. Chen,C.H. Yun, “Mining Web Transaction Patterns in an Electronic Commerce
Environment.” Proc. of the 4th Pacific-Asia Conf. on Knowledge Discovery and Data
Mining, pp. 216-219, April 18-20, 2000.
[8] C.H. Cai, Ada W.C. Fu, C.H. Cheng and W.W. Kwong: Mining Association Rules with Weighted Items. IDEAS 1998 : 68-77
[9] Y. Chi, P. Hadingham. “Tracking frequent Traversal Areas in a Web site via Log Analysis. “ In IEEE 7th International Conference on Parallel and Distributed Systems 2000.
[10] Jiawei Han, Jian Pei, Yiwen Yin: Mining Frequent Patterns without Candidate
Generation. ACM SIGMOD 2000, pages 1-12, 2000
[11] J. Han , J. Pei , M.A. Behzad. ”Frequent Pattern-Projected Sequential Pattern Mining.”
In ACM SIGMOD 2000.
[12] J. Han , J. Pei , M.A. Behzad , H. Zhu. “Mining Access Patterns Efficiently from Web
Logs” In PAKDD 2000.
[13] Ian H. Witten, Zane Bray, Malika Mahoui, W. J. Teahan:Text Mining：A New Frontier
for Lossless Compression. Data Compression Conference 1999:198-207
[14] R. Meo, G. Psaila, and S. Ceri: A New SQL-like Operator for Mining Association Rules. In Proceedings of the International Conference on Very Large Data Bases, pages 122-133, 1996.
[15]Ramakrishnan Srikant and Rakesh Agrawal: Mining Generalized Association Rules. In Proc. of the 21st Int’l Conference on Very Large Databases, Zurich, Switzerland, September 1995.
[16]Ramakrishnan Srikant and Yinghui Yang: Mining Web Logs to Improve Website Organization. To appear in Proc. of the Tenth International World Wide Web Conference, May 2001.
[17]J.S. Park, M.S. Chen, and P.S. Yu: An Effective Hash-Based Algorithm for Mining Association Rules. In Proceedings of ACM SIGMOD,24(2):175-186, 1995
[18]Ashok Savasere, Edward Omiecinski, Shamkant Navathe:An Efficient Algorithm for Mining Association Rules in Large Database. VLDB:432-444, 1995
[19]Wei. Wang, Jiong Yang, Philip. S. Yu: Efficient Mining of Weighted Association Rules (WAR). KDD 2000:270-274
[20]Show-Jane Yen and Arbee L.P. Chen: An Efficient Approach to Discovering Knowledge from Large Databases. In PDIS, page 8-18,1996
[21]Show-Jane Yen, Arbee L. P. Chen: An Efficient Data Mining Technique for Discovering Interesting Association Rules. DEXA Workshop 1997: 664-669
[22]Show-Jane Yen, Chung-Wen Cho:An Efficient Approach to Discovering Sequential Patterns in Large Database. PKDD, pages 685-690, 2000
[23]謝清佳、吳琮璠：資訊管理理論與實務 智勝出版社