臺灣博碩士論文加值系統

隨著資訊科技的進步、電腦的普及，蒐集資料變得更容易、快速而且方便。但長時間之下，資料庫累積了大量且有隱藏性的資料。所以，如何將這些被隱藏的資料，做正確又有效率地探勘，成為一個重要的議題。因此，資料探勘的技術便應運而生。當中，被廣為使用的技術為關聯法則之探勘。關聯法則探勘主要是探討如何從龐大資料庫中找出頻繁項目集組合，進而發掘有效且有用的知識。而在關聯規則中最常被使用的方法為Apriori演算法。雖然此方法可以找出關聯法則，但是它有二個最大的缺點：第一點為在找頻繁項目集組合時，會產生大量的候選項目集；第二點為執行時必須經常掃瞄整個資料庫，造成執行效率不佳。後續有許多研究皆針對此缺點做改進，但皆未跳脫Apriori演算法的整體架構，以致於其執行效率並無很大的進展。
本研究提出兩個解決的演算法，也就是ICI演算法以及QDT演算法。而且本研究提出的兩個演算法皆脫離Apriori演算法的架構，在產生頻繁項目集組合時，皆只需掃描資料庫一次，因此可以有效率地降低I/O的存取時間。而且不會隨著最小門檻值的變動來影響到執行效率，所以執行效率十分平穩。如此，可快速地找出符合使用者需求的關聯法則，使得資料探勘更有效率。

Due to the improvement of information technologies and popularization of computers, collecting information becomes easier, rapider and more convenient than before. As the time goes by, database cumulates huge and hiding information. Therefore, how to correctly uncover and efficiently mining from those hiding information becomes a very important issue. Hence the technology of data mining becomes one of the solutions. In the technologies of data mining, association rules mining is one of the most popular technology to be used. Association rule mining explores the approaches to extract the frequent itemsets from large database. Further, derives the knowledge behind implicitly. The Apriori algorithm is one of the most frequently used algorithms. Although the Apriori algorithm can successful derive the association rules from database, the Apriori algorithm has two major defects: First, the Apriori algorithm will produce large amounts of candidate itemsets during extracting the frequent itemsets from large database. Second, frequently scanning whole database lead to inefficient performance. Many researches try to improve the performance of the Apriori algorithm, but still not escape from the frame of the Apriori algorithm and lead to a little improvement of the performance.
In this paper we propose QDT and ICI which escape the frame of Apriori algorithm, and it only needs to scan whole database once during extracting the frequent itemsets from large database. Therefore, the QDT and ICI algorithm can efficiently reduce the I/O time, and rapidly extract during extracting the frequent itemsets from large database, and make data mining more efficient than before.

摘 要---------------------------------------------------------------------------------------------i
英文摘要--------------------------------------------------------------------------------------------ii
致 謝-------------------------------------------------------------------------------------------iii
目 次--------------------------------------------------------------------------------------------iv
表 目 錄--------------------------------------------------------------------------------------------vi
圖 目 錄-------------------------------------------------------------------------------------------vii
第一章 緒論 1
1.1 資料探勘之探討 1
1.1.1資料探勘的定義 1
1.1.2資料探勘的技術與應用 3
1.1.3 關聯法則的探討 6
1.2 提出改良演算法 8
1.2.1 研究動機及目的 8
1.2.2 研究流程 9
1.3 論文架構 9
第二章 文獻探討 10
2.1 APRIORI演算法 10
2.2 ALL-SUBSET TREE演算法 14
2.3 AIM演算法 17
2.4 STD演算法 20
第三章 QDT演算法與ICI演算法 24
3.1 QDT(QUICK DECOMPOSITION TREE)演算法 25
3.1.1 QDT演算法實作 25
3.1.1.1 演算法流程圖說明 26
3.1.1.2 演算法說明 27
3.1.1.3 演算法拆解圖示說明 29
3.1.2 QDT實例說明 33
3.2 ICI(INCREMENTAL COMBINATION ITEMSETS)演算法 37
3.2.1 ICI演算法實作 38
3.2.1.1 ICI演算法流程圖說明 38
3.2.1.2 ICI演算法說明 40
3.2.1.3 ICI模組產生方式實例說明 42
3.2.1.4 ICI對映方式實例說明 45
3.2.2 ICI實例說明 46
第四章 實驗結果與討論 51
4.1 實驗設備及實驗說明 51
4.2實驗設計、數據分析及效能評估 52
第五章 結論與未來研究 58
參考文獻 61

1. 陳彥良、陳家仁，在限定項目個數與交易長度的資料庫中挖掘關聯規則，國立中央大學資訊管學系碩士論文，民國90年。
2. 楊東麟、許振華，從限定項目個數及交易長度的資料中有效地找出關聯規則之研究，逢甲大學資訊工程學系碩士論文，民國91年。
3. 楊東麟、楊文昇，有效率的挖掘關聯法則之高頻物項集合演算法，逢甲大學資訊工程學系碩士論文，民國90年。
4. A.Savasere, E.Omiecinski, and S.Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases”, Proc. of 21st VLDB, pp.432-444, 1995.
5. B.Dunkel and N.Soparkar, “Data Organization and Access for Efficient Data Mining”, ICDE, 1999.
6. C.Ming-Syan, H.Jiawei, and S.Yu Philip, “Data mining : An Overview from a Database Perspective”, IEEE Transactions on Knowledge and Data Enginerring, 1996, Vol.8-No.6.
7. H.Mannila, and P.Ronkainen, “Similarity of Event Sequences”, Procedings of the Fourth International Workshop on Temporal Representation and Reasoning(TIME’97),1997, pp.136-139.
8. H.Toivonen, “Sampling Large Databases for Association Rules”, Proc. of 23st VLDB, 1996, pp.134-145.
9. J.Elder IV, and D.Pregibon , “A statics perspective on knowledge discovery in databases”, AAAI/MIT Press,1996, pp.83-115.
10. J.Han and Fu.Yongjian, “Mining Multiple-Level Association Rules in Large Database”, IEEE Trans. On Knowledge and Data Engineering, 1999, Vol.11,No.5, pp.798-805.
11. J.Han and J.pei, and Y.Yin, “Mining Frequent Patterns without Candidate Generation”, Proc. of 2000 ACM Int. Conf. On Management of Data, 2000, pp.1-12.
12. J.Hipp, A.Myka, R.Wirth, and U.Guntzer, “A New Algorithm for Faster Mining of Generalized Association Rules”, Technischer Bericht des Wilhelm-Schickard-Instituts, WSI-98-4, 1998.
13. J.R.Quilan, “C4.5 : Programs for Machine Learning”, Morgan Kaufmann, 1993.
14. J.R.Quilan, “Induction of decision trees”, Machine Learning, 1986, pp.81-106.
15. J.S Park, C.Ming-Syan, and S.Yu.Philip, “An Effective Hash Based Algorithm for Mining Association Rules”, Proc. of ACM SGMOD, 1995, pp.175-185.
16. K.Alsabti, S.Ranka, and V.Singh, “An Efficient K-Means Clustering Algorithm”, PPS/SPDP Workshop on High performance Data Mining, 1997.
17. L.Breiman, J.Friedman, R.Olshen, and C.Stone, “Classification of Regression Trees”, Wadsworth, 1984.
18. L.Kaufman, and P.J. Rousseeuw, “Finding Groups in Data : An Introduction to Cluster Analysis”, 1990.
19. M.J.Zaki, “Scalable Algorithms for Association Mining”, IEEE Trans. On Knowledge and Data Engineering, 2000, pp.372-390.
20. M.J.Zaki, S.Parthasarathy, M.Ogihara, and W.Li, “New Algorithms for Fast Discovery of Association Rules”, American Association for Artificial Intelligence, 1997.
21. M.J.Zaki, S.Parthasarathy, M.Ogihara, and W.Li, “New Algorithms for Fast Discovery of Association Rules”, The 3rd Int’l. Conf. On Knowledge Discovery & Data Mining(KDD), 1997.
22. R.Agrawal, and R.Srikant, “Fast Algorithms for Mining Association Rules”, Proc. of the 20th VLDB Conference Santiago, 1994.
23. R.Agrawal, and R.Srikant, “Mining Sequential Patterns”, Proc. of the Int’l Conference on Data Engineering(ICDE), 1995.
24. R.Agrawal, T.Imielinski, and A.Swami, “Mining Association Rules Between Sets of Items in Large Databases”, In proc. of the ACM SIGMOD Conference on Management of Data, 1993, pp.207-216.
25. R.J. Bayardo, “Efficiently Mining Long Patterns from Databases”, Proc. of ACM SIGOD Conf. On Management of Data, 1998, pp.85-93.
26. R.Ng, and J.Han,”Efficient and Effective Clustering Method for Spatial Data Mining”, Proc. Int’l Conf. Very Large Data Bases, 1994, pp.144-155.
27. R.Srikant, and R.Agrawal, “Mining Generalized Association Rules”, Proc.of the 21st Int’l Conference on VLDB, 1995, pp.407-419.
28. S.Brin, R.Motwai, J.D.Ullman, and S.Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data”, ACM SIGMOD Conference on Management of Data, 1997, pp.265-276.
29. S.M.Weiss and, C.A.Kulikowski, “Computer System that Learn : Classification and Predicition Methods form Statistics, Neural Net, Machine Learning, and Expert System”, Morgan Kaufman, 1991.
30. U.Fayyad, G.Piatetsky-Shapiro and P.smyth, “From Data Mining to Knowledge Discovery in Database”, Cambridge, AAAI/MIT Press,1996.
31. W.J.Frawley, G.Paitetsky-Shapiro, and C.J.Matheus, “Knowledge Discovery in Databases : An Overview Knowledge Discovery in Databases”, edited by G.Piatetsky-Shapiro and W.J.Frawley, California, AAAI/MIT Press,1991, pp.1-30.