臺灣博碩士論文加值系統

近年來資料探勘之研究愈來愈受到企業的重視，而資料探勘中關聯規則的研究，亦從原本的交易資料表延伸至關連式資料表上，目的即是讓關聯規則的應用能更多元化。本論文是以關連資料表中的階層式關聯規則為研究，針對資料表中的兩種屬性，數值性屬性與類別性屬性，分別提出數值性屬性的分群方法與概念性階層關聯規則的產生方法。在分群方法上，從使用者的觀點與資料偏斜上做考量，針對使用者心目中理想的分群數目與分群區間，可能會因為資料偏斜的問題導致無法產生關聯規則的情形，提出調整區間的分群方法，運用距離的觀念，對使用者理想的分群區間與分群數目做局部的調整，使數值性屬性產生關聯規則的機率提高，而且不會有複雜度過高的問題。而在類別性屬性方面則是運用概念性階層的觀念，希望能夠產生不同階層的關聯規則，我們是以布林演算法為基礎，研究如何將階層性的資料轉換成布林的形式，並進一步產生高頻項目組與關聯規則。最後我們以實驗來分析不同方法在規則數目、執行時間等方面的差異性。

As a useful business intelligence tool, data mining is gaining its popularity in many real life applications. Association rules is an important data mining technique developed for looking for the relationship among items bought by customers in a supermarket. To increase its applicability, some researchers have worked on mining association rules from relational databases. Mining association rules from relational databases is much more difficult than mining association rules from transactional databases, especially when numerical attributes are involved. This problem is further complicated if one tries to mine rules with concept hierarchy in the domains of the attributes. In this thesis, we study the problem of mining association rules with concept hierarchy in relational databases.
For a numerical attribute, we propose an effective clustering algorithm to partition the domain of the attribute such that meaningful association rules can be generated. In the algorithm, we allow the user to give an initial partition on the domain of an attribute. Then, by considering the effect of data skew, we adjust the partitions properly to enhance the chance of generating meaningful rules. For a categorical attribute, we encode the concept hierarchy among values of the attribute, and propose a Boolean- based algorithm for mining association rules with concept hierarchy. We implement the proposed algorithm, test it against different datasets, and study its performance in generating multilevel association rules.

第一章緒論......................................1
1.1　資料探勘簡介......................................1
1.2　研究動機與目的.............................2
1.3　論文架構......................................3
第二章文獻探討......................................5
2.1 關聯規則......................................5
2.2　數值性屬性......................................9
2.3 概念性階層......................................12
第三章分群......................................15
3.1 分群的剖析......................................15
3.2 調整區間的分群方法.............................16
3.2.1 分群的方法流程.............................16
3.2.2 分群演算法......................................20
第四章概念性階層的關聯規則....................21
4.1 概念性階層的剖析.............................21
4.2 高頻項目組的產生.............................22
4.2.1 高頻項目組產生的方法流程....................22
4.2.2 高頻項目組產生的演算法....................29
4.3 規則的產生......................................35
第五章研究成果與實驗.............................37
5.1 分群實驗結果......................................37
5.2 概念性階層的實驗結果.............................42
5.3 綜合分析與討論.............................44
第六章結論與未來發展.............................45
參考文獻...............................................46

1.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, Washington D.C., May 1993.
2.Raskesh Agrawal, Ramakrishnan Srikant, “Fast Algorithms for Mining Association Rules”, Proceedings of the 20th VLDB Conference Santiago. Chile, 1994.
3.Jong Soo Park, Ming-Syan Chen, Philip S. Yu, “Using a Hash-Based Method with Transaction Trimming for Mining Association Rules”, IEEE Transactions on Knowledge and Data Engineering, VOL. 9, NO. 5,SEP/OCT 1997, pp. 813-825
4.Ashok Savasere, Edward Omiecinski, Shamkant Navathe, “ An Efficient Algorithm for Mining Association Rules in Large Databases”, Proceedings of the 21st VLDB Conference, Zurich, Swizerland, 1995, pp. 432-444
5.Suh-Ying Wur and Yungho Leu, “An effective Boolean Algorithm for Mining Association Rules in Large Databases”, DASFAA 99, 1998.6.Ramakrishnan Srikant, Rakesh Agrawal, “Mining Quantitative Association Rules in Large Relational Tables”, Proceedings of the 20th International Conference on Management of Data, pp.1-12, June 1996.
6.Ramakrishnan Srikant, Rakesh Agrawal, “Mining Quantitative Association Rules in Large Relational Tables”, Proceedings of the 20th International Conference on Management of Data, pp.1-12, June 1996.
7.Jef Wijsen, Robert Meersman, “On the Complexity of Mining Quantitative Association rules”, Data Mining and Knowledge Discovery, 2, pp. 263-281, 1998.
8.Yonatan Aumann, Yehuda Lindell, “A Statistical Theory for Quantitative Association Rules”, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, 1999, pp. 261-270.
9.Rajeev Rastogi,Kyuseok Shim, “Mining Optimized Association Rules with Categorical and Numeric Attributes”, IEEE, 1998.
10.張志遠，“A Clustering Based Approach for Mining Association Rules in Relational Databases”,1999
11.Ramakrishnan Srikant, Rakesh Agrawal, “Mining generalized association rules”, Proceedings of the 21st Int’l Conference on Very Large Database, Zurich, Switzerland, 1995
12.Jiawei Han, Yongjian Fu, “Discovery of Multiple-Level Association Rules from Large Databases”,Proceedings of the 21st VLDB Conference, Zurich, Swizerland, 1995,pp. 420-431
13.Y.d. Cai, Nick Cercone, and Jiawei Han, “Attribute-Oriented Induction in Relational Databases”, KDD, AAAI Press/ The MIT Press, 1991
14.Jiawei Han, Yandong Cai, Nick Cercone, ”Data-Driven Discovery of Quantitative Rules in Relational Databases”, IEEE Transactions on Knowledge and Data Engineering, Vol 5, No 1, February 1993
15.Suk-Chung Yoon, E.K. Park, “An Approach to Intensional Query Answering at Multple Abstraction Levels Using Data Mining Approaches”, Proceedings of the 32nd Hawaii International Conference on System Sciences, 1999
16.Roberto Bayardo Jr., Rakesh Agrawal, Dimitrios Gunopulos, “Constraint-Based Rule Mining in Large, Dense Databases”, Proceeding of the 15’th int’l conf. On Data Engineering, 1999, pp. 188-197
17.Tomasz Imielinski, Aashu Virmani, “DMajor-Application Programming Interface for Database Mining”, Data Mining and Knowledge Discovery 3, 1999, pp. 347-372
18.Tomasz Imielinski, Aashu Virmani, “MSQL: A Query Language for Database Mining”, Data Mining and Knowledge Discovery 3, 1999, pp. 373-408
19.Roberto J. Bayardo Jr., Raskesh Agrawal, “Mining the Most Interesting Rules”, Proce. Of the fifth ACM SIGKDD Int’l Conf. On Knowledge Discovery and Data Mining, 1999, pp. 145-154
20.Data Wsrehousing with Microsoft SQL Server 7.0 Technical Reference