臺灣博碩士論文加值系統

近年來，隨著科技不斷的創新與進步，電腦已被廣泛的使用在各行各業中，由於網際網路與全球資訊網的快速發展與普及化，使得資訊的獲得比以前更加方便，因此在資料量愈來愈多的情況下，許多組織藉由資料庫系統來儲存及管理資料。隨著資料庫日益龐大，要如何從這些大型資料中挖掘出有用但卻不易被發現的商業智慧，已成為一個重要的研究課題。資料探勘正是目前從資料庫中探索知識的重要技術，其中關聯式法則的探勘又是資料探勘中重要的技術之一，主要用來發掘各個物件項目之間的關係，以便找出具有價值的規則。然而，傳統的關聯式法則探勘演算法，都要求每一筆記錄中必須包含所有在規則中出現的項目，如{A}→{B,C}，記錄中必須同時包含A、B、C三個項目才會計算其出現次數，如此，一些潛在的規則便無法被發掘出來，例如在疾病的診斷上，往往因為患者並未完全出現該疾病的所有症狀，而延誤了早期發現早期治療的契機。為了解決此問題，於是有學者提出複合項關聯式法則的探勘。然而，為了找出有價值的複合項，卻使用了較為複雜的刪除方式，因此，在本論文中，將提出一個新的探勘方法，可以更簡單地找出所有的複合項。另外，原本的複合項為最基本的型態，僅限於具有單一OR關係，為了使查詢的結果更能符合使用者的需求，在本論文中，提供了其他布林運算式(如AND、NOT)和特殊型態(如XOR、XNOR)等複合項關聯式法則探勘的能力。

In recently years, as the technology innovates and progresses constantly, computers have been utilized in various walks of life. And, because of the rapid progress on Internet and on World Wide Web, it is more convenient for us to get the information. Consequently, in the case of more and more data, a lot of organizations begin to use database systems to store and manage the data they need. As the rapid growth in the size and number of the database, the technology of discovering useful knowledge hidden in the large database has become an important research topic. Data mining is the important task of knowledge discovery in databases. The mining of association rule has become one of the important data mining technology. Association rules can be used to express relationships between items of data. Mining association rules is to analyze the data in a database to discover interesting rules. However, existing algorithms require a record in the database contain all the data items in a rule. Such as the rule {A}→{B,C}, a transaction which contains A, B, and C will be counted. This requirement makes it difficult to discover certain useful rules in some applications. For example, a patient may not show all symptoms of a disease so that he does not keep the right time to cure. To solve the problem, a method which can support mining association rules with composite items was proposed. However, in order to find all interesting composite items, it uses a more complicated method to prune. There, in this thesis, we will propose a new mining strategy, which is called SimplePrune approach to reduce the overhead of pruning. In addition, we supports other Boolean operations(such as AND and NOT)and special types of binary operations(such as XOR and XNOR). Via our proposed method, various types of association rules between composite items can be discovered.

第一章　緒論
第一節　研究背景．．．．．．．．．．．．．．．．．．．．．1
第二節　研究動機．．．．．．．．．．．．．．．．．．．．．4
第三節　本論文的內容與架構．．．．．．．．．．．．．．．．7
第二章　文獻探討
第一節　AIS演算法．．．．．．．．．．．．．．．．．．．9
第二節　Aprori演算法．．．．．．．．．．．．．．．．．10
第三節　DHP演算法．．．．．．．．．．．．．．．．．．．12
第四節　DLG演算法．．．．．．．．．．．．．．．．．．．14
第五節　Boolean演算法．．．．．．．．．．．．．．．．．16
第六節　DIC演算法．．．．．．．．．． ．．．．．．．．．19
第七節　複合項關聯式法則探勘演算法．．．．．．．．．．．20
第三章　基本型複合項
第一節　ECIG演算法．．．．．．．．．．．．．．．．．．26
第二節　複合項的Trie架構．．．．．．．．．．．．．．．30
第三節　實驗及效能分析．．．．．．．．．．．．．．．．40
第四節　ECIG演算法模擬實驗結果．．．．．．．．．．．．42
第五節　複合項演算法實作 ．．．．．．．．．．．．．．44
第四章　其他其本型態的複合項
第一節　具有AND關係的複合項．．．．．．．．．．．．．50
第二節　具有AND、NOT關係的複合項．．．．．．．．．．．54
第三節　模擬實驗結果．．．．．．．．．．．．．．．．．59
第五章　特殊型態的複合項
第一節　XOR複合項．．．．．．．．．．．．．．．．．．63
第二節　XNOR複合項．．．．．．．．．．．．．．．．．．59
第三節　其它型態的XOR複合項和XNOR複合項．．．．．．．60
第四節　模擬實驗結果．．．．．．．．．．．．．．．．．62
第五節　討論．．．．．．．．．．．．．．．．．．．．．64
第六章　結論及未來研究方向
第一節　結論．．．．．．．．．．．．．．．．．．．．．74
第二節　未來研究方向．．．．．．．．．．．．．．．．．75
參考文獻．．．．．．．．．．．．．．．．．．．．．．．76

[1] R. Agrawal, T. Imiclinski, and A. Swami. Mining Association
Rules between Sets of Items in Large Databases. In
Proceedings of ACM SIGMOD, 1993, 207-216.
[2] R. Agrawal, and R. Srikant. Fast Algorithm for Mining
Association Rules. In Proceedings of International
Conference on Very Large Database, 1994, 487-499.
[3] R. Agrawal and R. Srikant. Mining Sequential Patterns.
Proc. Of 11th International Conference on Data Engineering,
1995.
[4] Michael J. A. Berry, and Gordon S. Linoff. Data Mining
Techniques For Marketing, Sales and Customer Support.
[5] S. Brin, R. Motwani, J. Ullman, and S. Tsur. Dynamic
Itemset Counting and Implication Rules for Market Basket
Data. SIGMOD-97, 1997, 255-264.
[6] Ming-Syan Chen, Jiawei Han, and Philps S. Yu. Data Mining:
An Overview from Database Perspective. IEEE Transactions on
Knowledge and Engineering, 1996, 8(6), 866-883.
[7] Jiawei Han, and Micheline Kamber. Data Mining : Concepts
and Techniques.
[8] Maurice Houstma, and Arun Swami. Set-Oriented Mining for
Association Rules in Relational Database. IEEE 11th
International Conference on Data Engineering, 1995, 25-33.
[9] Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo.
Efficient Algorithms for Discovering Association Rules. In
AAAI'94 Workshop on Knowledge Discovery in Database(KDD-
94), 1994, 181-192.
[10] Jong Soo Park, Ming-Syan Chen, and Philips S. Yu. An
Effective Hash-Based Algorithm for Mining Association
Rules. Proc ACM SIGMOD, 1995, 175-186.
[11] Jong Soo Park, Ming-Syan Chen, and Philips S. Yu. Using a
Hash-Base Method with Transaction Trimming for Mining
Association Rules. IEEE Transactions on Knowledge and Data
Engineering, 1997, 813-825.
[12] Ashok Savasere, Edward Omiecinski, and Shamkant Navathe.
An Efficient Algorithm for Mining Association Rules in
Large Database. Proceedings of the 21st VLDB Conference,
1995, 432-444.
[13] S. Y. Sung, K. Wang, B. I. Chua. Data mining in a large
database environment. Systems, Man and Cybernetics, 1996.
IEEE International Conference on Volume: 2, 1996, 988 —
993.
[14] Jian Tang. Using Incremental Pruning to Increase the
Efficiency of Dynamic Itemset Counting for Mining
Association Rules. CIKM-98, 1998, 273-280.
[15] Suh-Yin Wur, and Yungho Leu. An Effective Boolean
Algorithm for Mining Association Rules in Large Databases.
Proceedings, 6th International Conference on Database
Systems for Advanced Applications, 1999. 179-186.
[16] X. Ye, and J. A. Keane. Mining Association Rules with
Composite Items. Systems, Man, and Cybernetics, 1997.
Computational Cybernetics and Simulation., 1997. IEEE
International Conference on Volume : 2, 1997, Page(s) :
1367 - 1372.
[17] X. Ye, and J. A. Keane. Mining Association Rules in
Temporal Databases. Systems, Man, and Cybernetics, 1998.
IEEE International Conference on Volume : 3, 1998 , Page
(s): 2803 - 2808.
[18] Show-Jane Yen, and Arbee L. P. Chen. An Efficient Approach
to Discovering Knowledge from Large Database. Int'l
Conference on Parallel and Distributed Information System,
1996, 8-18.