臺灣博碩士論文加值系統

近年來，資料倉儲與資料採掘的結合已成為進行知識發掘最主要的平台。然而自資料倉儲中發掘知識需要經由深入且多方面的分析。為達此目的，許多資料採掘過程所涉及的頻繁計算與資訊必須有系統地先予處理與建置，且需具備可供使用者進行線上採掘的環境。在這篇論文中，我們提出了一個線上關聯規則採掘系統的架構。此系統是建立在前置處理及視域實體化的觀念，結合了OLAP及我們所制定的OLAM資料方體及輔助方體。根據OLAM資料方體的概念，我們定義了一個具有維度階層性的OLAM晶格，可協助建構所有可能樣式的OLAM資料方體。此外，我們更提出了兩個演算法稱為CBWoff及CBWon。前者可用以建置OLAM資料方體及輔助方體，後者則可於線上及時產生頻繁項目集。最後，我們分別對CBWoff及CBWon作了幾個實驗。實驗結果顯示，CBWoff的速度遠優於其他兩種以Apriori為基礎的演算法。實驗亦顯示CBWon方法可滿足線上關聯規則的環境。

Recently, the integration of data warehouses and data mining has been recognized as the primary platform for facilitating knowledge discovery. Effective data mining from data warehouses, however, needs exploratory data analysis. A user often needs to investigate the data warehouse data from various perspectives and analyze them at different granularities levels of abstraction. To this end, comprehensive information processing and data analysis have to be systematically constructed surrounding data warehouses, and an on-line mining environment should be provided. In this thesis, we propose a system framework to facilitate on-line association rules mining, called OMARS, which is based on the idea of integrating the OLAP service and our proposed OLAM cubes and auxiliary cubes. According to the concept of OLAM cubes, we define the OLAM lattice framework to model all possible OLAM data cubes that involve arbitrary hierarchies of dimensions. Moreover, we propose two algorithms, called CBWoff and CBWon, to construct the OLAM cubes and auxiliary cubes off-line and to generate frequent itemsets on-line respectively. Experimental evaluations show that CBWoff outperforms two leading Apriori-like methods. Experiments also show that our CBWon algorithm is well suitable for on-line association mining environment.

ABSTRACT V
誌謝 VII
Chapter 1 1
Introduction 1
1.1 Motivation 2
1.2 Contributions 3
1.3 Thesis organization 4
Chapter 2 6
Background and Related Work 6
2.1 Data Warehouse and OLAP 6
2.2 Data Warehouse Data Model 7
2.1.1 Star Schema Data Model 8
2.1.2 Snowflake Data Model 9
2.3 Data Cubes and Precomputation 11
2.4 Data Mining and Association Rules 13
2.4.1 Association Rules 13
2.4.2 Multi-Dimensional Association Rules 14
2.5 Off-Line Associations Mining 18
2.6 On-line Associations Mining 25
2.7 Mining with Concept Hierarchy 30
Chapter 3 33
The OMARS Framework 33
3.1 Panorama 33
3.1.1 Cube Manager 35
3.1.2 OLAM Mediator and OLAM Engine 36
3.2 OLAM Cube and OLAM Lattice 37
3.3 Auxiliary Cube 48
Chapter 4 51
OLAM Cube Computation 51
4.1 OLAM Cube Construction 51
4.1.1 The Specification of prims 51
4.1.2 Algorithm OLAML_Const 53
4.2 Off-Line Preprocessing 56
4.2.1 Basic Idea 56
4.2.2 Off-Line Cut-Both-Ways Algorithm (CBWoff) 59
4.3 On-Line Mining 64
4.3.1 Motivation 64
4.3.2 On-Line Cut-Both-Ways Algorithm (CBWon) 65
Chapter 5 71
Experiments 71
5.1 Performance Study of Algorithm CBWoff 72
5.1.1 Foodmart2000 Database 72
5.1.2 Synthetic Database 74
5.2 Performance Study of Algorithm CBWon 78
Chapter 6 82
Conclusions and Future Work 82
6.1 Conclusions 82
6.2 Future Work 83
References 85
Publication Lists 89

[1] C. C. Aggarwal and P.S. Yu, “Online generation of association rules,” IEEE Transactions on Knowledge and Data Engineering, pp. 402-411, 1998.
[2] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” in Proceedings of the 20th VLDB Conference, pp. 487-499, 1994.
[3] K.S. Beyer and R. Ramakrishnan, “Bottom-Up Computation of Sparse and Iceberg CUBEs,” in Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, pp. 359-370, 1999.
[4] S. Brin, R. Motwani, J. D. Ullman and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Baseket Data,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, volume 26,2 of SIGMOD Record, pp. 255-264, New York, May 13th-15th 1997. ACM Press.
[5] M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani and J.D. Ullman, “Computing Iceberg Queries Efficiently,” in Proceedings of the 24th VLDB Conference, pp. 299-310, 1998.
[6] C. Hidber, “Online Association Rule Mining,” in Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, pp. 145-156, 1999.
[7] J. Han, “OLAP Mining: An Integration of OLAP with Data Mining,” in Proceedings of the 7th IFIP 2.6 Working Conference on Database Semantics (DS-7), pp. 1-9, 1997
[8] J. Han, S. Chee, and J. Chiang, “Issues for On-Line Analytical Mining of Data Warehouse,” in Proceedings of the 1998 ACM SIGMOD, Workshop on Research Issues on Data Mining and Knowledge Discovery, 1998.
[9] J. Han and Y. Fu, “Discovery of multiple-level association rules from large databases,” in Proceedings of the 21st VLDB Conference, Zurich, Switzerland, pp. 420-431, 1995.
[10] J. Han and M. Kamber, “Data Mining:Concepts and Techniques,” MORGAN KAUFMANN PUBLISHERS, 2000.
[11] J. Han, ”Towards On-Line Analytical Mining in Large Databases, SIGMOD Record,“ Volume 27, No 1, 1998.
[12] J. Hipp, A. Myka, R. Wirth and U. Guntzer, “A New Algorithm for Faster Mining of Generalized Association Rules,” in Proceedings of the 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD '98), pp. 74-82, 1998.
[13] J. Hipp, U. Guntzer and G. Nakhaeizadeh, “Mining Association Rules: Deriving a superior Algorithm by Analyzing Today’s Approaches,” in Proceedings of 4th European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD’00), pp. 159-168, 2000.
[14] M. Houtsma and A. Swami, “Set-Oriented Mining of Association Rules,” Research Report RJ 9567, IBM Almaden Research Center, San Jose, California, USA, 1993.
[15] W.H. Inmon and C. Kelley (1993) Rdb/VMS: Developing the Data Warehouse, QED Publishing Group, Boston, Massachussetts.
[16] H. M. Jamil, “On the Equivalence of Top-down and Bottom-up Data Mining in Relational Databases,” Data Warehousing and Knowledge Discovery, Third International Conference, DaWaK 2001, Munich, Germany, September 5-7, 2001, Proceedings, Lecture Notes in Computer Science 2114 Springer 2001, pp. 41-52, 2001.
[17] R. Kimball, “The Data Warehouse Toolkit Practical For Building Dimensional Data Warehouses,” JOHN WILEY & SONS, INC. 1996.
[18] W.Y. Lin, M. C. Tseng and J.H. Su, “A Confidence-Lift Support Specification for Interesting Association Mining,” in Proceedings of 6th Pacific Area Conference on Knowledge Discovery and Data Mining (PAKDD-2002), 2002.
[19] R. Meo, G. Psaila and S. Ceri, “A new SQL-like operator for mining association rules,” in Proceedings of 22nd VLDB Conference, pp. 122-133, 1996.
[20] J.S. Park, M.S. Chen, P.S. Yu, “Effective Hash-Based Algorithm for Mining Association Rules,” in Proceedings of ACM SIGMOD’95, San Jose, CA, USA, pp. 175-186, 1995.
[21] G. Psaila and P.L. Lanzi, “Hierarchy-based Mining of Association Rules in Data Warehouse,” in Proceedings of ACM’00, pp. 307-312, 2000.
[22] C. Perng, H. Wang, S. Ma and J. L. Hellerstein, ” FARM: A Framework for Exploring Mining Spaces with Multiple Attributes,” IEEE International Conference on Data Mining, pp. 449-456, 2001.
[23] R. Srikant and R. Agrawal, “Mining Generalized Association Rules,” in Proceedings of the 21st VLDB Conference, pp. 407-419, 1995.
[24] A. Savasere, E. Omiecinski and S. Navathe, “An Efficient Algorithm for Mining Association Rules in large Databases,” in Proceedings of the 24th VLDB Conference, pp. 432-444, 1995.
[25] H. Toivoneo, “Sampling Large Databases for Association Rules,” in Proceedings of the 22nd VLDB Conference Munbai, India, pp. 134-145, 1996.
[26] M. Wojciechowski and M. Zakrzewicz, “Itemset Materializing for Fast Mining of Association Rules,” Advances in Databases and Information Systems, Second East European Symposium, ADBIS'98, Poznan, Poland, Spetember 7-10, 1998, Proceedings. Lecture Notes in Computer Science 1475 Springer 1998, ISBN 3-540-64924-7.
[27] S.J. Yen and A.L.P. Chen, “An efficient data mining technique for discovering interesting association rules,” in Proceedings of IEEE Eighth International Workshop on Database and Expert Systems Applications, pp. 664-669, 1997.
[28] H. Zhu, “On-Line Analytical Mining of Association Rules,” SIMON FRASER UNIVERSITY, December 1998.
[29] M. J. Zaki, “Scalable Algorithms for Association Mining,” IEEE Transactions on Knowledge and Data Engineering, pp.372-390, 2000.