臺灣博碩士論文加值系統

資料挖掘為近年來客戶資源管理、行銷、醫學及其他許多領域中，將使用者有興趣的資料擷取出來的一門學科，而資料擷取的方式亦分為分群法、分類法、關聯法則擷取法等相關的方式。
在資料挖掘的學術領域中，最早被提出來的演算法即為Apriori演算法，它利用反覆讀取資料庫中關聯性資料的方式，將資料擷取出來，取得屬性之間的關聯法則，但對於現實生活中動態新增的資料庫而言，Apriori面臨了三個主要的問題，其一為大型資料庫挖掘曠日耗時，且無法即時更改支持度；二為無法有效解決資料庫中動態新增資料挖掘的問題，第三為相對於整體資料庫，較新時間點的敏感性資料無法做一個有效的擷取。
本篇論文提出兩種新的演算方式，其一為MUM (Multidimensional Update Mining)演算法，可在動態資料庫中即時挖掘出項目之間的關聯法則，以改善Apriori演算法在資料挖掘時效率不佳及無法動態挖掘新增資料庫的問題。另一種是SUM (Sensitivity Update Mining) 演算法，該演算法建立在MUM之上，用以即時挖掘敏感性資料的關聯法則，改進以往演算法必須批次處理大筆資料的問題。此兩種演算法對於目前動態新增的資料庫挖掘，提供了一個有效率的動態即時敏感性資料挖掘方式，避免敏感性資料因為無法在短期間內達到使用者設定的最小支持度而被捨棄的問題。

Data mining is the exploration and analysis of large quantities of data in order to discover meaningful patterns and rules. It is an important discipline that has widely applied in fields ranging from customer relationship management to marketing, and medicine.
The discovery of association rules is an important task in data mining. The Apriori algorithm is the most popularly and widely used technique for mining association rules. However, the Apriori algorithm must scan the databases many times to discover the large itemsets so that it has three main disadvantages: (1) it is time-consuming; (2) it is not suitable for mining of incrementally growing databases due to the need of rescanning the original databases; and (3) as databases grow, the sensitive information in the new transactions can not mined effectively.
In this thesis, we propose the Multidimensional Update Mining (MUM) algorithm, which does not need to rescan the original database, to mine the association rules for the incrementally growing databases. Based on the MUM algorithm, a Sensitivity Update Mining (SUM) algorithm is designed to mine sensitive information from the newly inserted transactions. Many experiments and related analysis are conducted to validate our proposed approaches.

書名頁……………………………………………………………………… i
博碩士論文授權書………………………………………………………… ii
論文指導教授推薦函 …………………………………………………… iii
論文口試合格証明 ……………………………………………………… iv
中文摘要…………………………………………………………………… v
英文摘要…………………………………………………………………… vi
誌謝 ……………………………………………………………………… vii
目錄 …………………………………………………………………… viii
表目錄 ……………………………………………………………………… x
圖目錄 …………………………………………………………………… xi
第一章 緒論 …………………………………………………………… 1
第一節 資料挖掘的定義 ……………………………………………… 1
第二節 資料挖掘的方法 ……………………………………………… 5
第三節 資料挖掘的應用 ……………………………………………… 6
第四節 研究動機與目的 ……………………………………………… 7
第五節 研究方法 ……………………………………………………… 8
第二章 相關研究 ……………………………………………………… 10
第一節 關聯法則資料挖掘的演算方式 …………………………… 10
2.1.1 Apriori演算法 …………………………………………………… 10
2.1.2 DHP 演算法 ……………………………………………………… 14
2.1.3 DIC演算法 ………………………………………………………… 16
2.1.4 Partition演算法 ………………………………………………… 18
2.1.5 Sampling 演算法 ………………………………………………… 20
第二節 動態資料庫挖掘相關演算方式 …………………………… 21
2.2.1 FUP演算法 ………………………………………………………… 21
2.2.2 Pre-Large Itemsets Mining …………………………………… 25
2.2.3 縮減項目集絡挖掘方式 ………………………………………… 27
第三節 其他資料挖掘相關的法則 …………………………………… 30
2.3.1 廣義性之關聯法則 ……………………………………………… 30
2.3.2 負面性之關聯法則 ……………………………………………… 31
2.3.3 Apriori法則與應用 ……………………………………………… 32
2.3.4 儲存空間與即時線上挖掘 ……………………………………… 33
第三章 動態資料挖掘演算法之研究 ………………………………… 35
第一節 MUM演算法技術之探討 ……………………………………… 35
第二節 MUM演算法之推導過程 ……………………………………… 37
第三節 MUM 演算法之實作研究 ……………………………………… 43
第四節 MUM 演算法與Apriori演算法之討論與比較………………… 45
第四章 敏感性資料挖掘演算法之研究 ……………………………… 48
第一節 SUM演算法技術之探討 ……………………………………… 49
第五章 實驗結果與討論 ……………………………………………… 55
第一節 實驗架構與實驗數據 ………………………………………… 55
第二節 實驗結果探討 ………………………………………………… 57
第三節 MUM演算法之後續探討 ……………………………………… 59
第六章 結論與未來研究方向 ………………………………………… 62
第一節 結論 …………………………………………………………… 62
第二節 未來研究之方向 ……………………………………………… 63
參考文獻 ………………………………………………………………… 66

1.M. S. Chen, J. Han, and P.S. Yu, "Data Mining: An Overview from a database Perspective", IEEE Transaction on Knowledge and Data Engineering, Vol. 8,No. 6,December 1996.
2.L. Kaufman and P. J. Rousseeuw, "Finding Groups in Data: an Introduction to Cluster Analysis", John Wiley & Sons, 1990.
3.S. M. Weiss and C. A. Kulikowski, "Computer System that Learn: Classification and Prediction Method from Statistics, Neural Nets, Machine Learning, and Expert System", Morgan Kaufman,1991.
4.R. Agrawal and R. Srikant, "Mining Sequential Patterns", IEEE ICDE, pp. 3-14, 1995.
5.R. Agrawal and R. Srikant, "Fast algorithm for mining association rules", the International Conference on Very Large Database, pp. 487-499, 1994.
6.R. Agrawal, R. Srikant, and Q. Vu, "Mining association rules with item constraints", in 3th International Conference on Knowledge Discovery in Database and Data Mining, Newport Beach, California, 1997.
7.M. S. Chen, J. S. Park, and P. S. Yu, "Efficient Data Mining for Path Traversal Patterns", IEEE Transactions on Knoeledge and Data Engineering, Vol. 10, No. 2, 1998.
8.R. Agrawal and R. Srikant, "Fast Algorithm for Mining Assoication Rule in Large Databases", In Proc. 1994 Int’l Conf. VLDB, pp. 487-499, Santiago, Chile, Sep. 1994.
9.Savasere, E. Omiecinski, and S. Navathe, "An Efficient Algorithm for Mining Association Rule in Large Database", Proc. 21th VLDB,pp. 432-444, 1995.
10.T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, "Mining optimized association rules for numeric attributes", the ACM SIGACT—SIGMOD -SIGART Symposium on Principles of Database Systems, pp. 182-191,1996.
11.D. W. Cheung, S. D. Lee, and B. Kao, "A general incremental technique for maintaining discovered association rules", in Proceedings of Database Systems for Advanced Applications, DASFAA’97, Melbourne, Australia, pp. 185-194, 1997.
12.H. Toivonen, "Sampling Large Database for association Rule", VLDB, pp. 134-145, 1996.
13.J. S. Park, M. S. Chen, and P. S. Yu, "An Effective Hash Based Algorithm for Mining Association Rules", Proc. ACM SIGMOD, pp. 175-186, 1995.
14.S. Brin, R. Motwani, J. D. Ullman, and S. Tsur, "Dynamic Itemset Counting and Implication Rules for Marketing Basket Data", 1997 ACM SIGMOD Conference on Management of Data, pp. 255-264, 1997.
15.B. Dunkel and N. Soparkar, "Data Organization and Access for Efficient Data Mining", ICDE 1999, Sydney, Australia.
16.D.Kenny and J. F. Marshall, "Contextal Marketing", Harvard Business Review, Nov-Dec, 2000.
17.R. Srikant and R. Agrawal, "Mining Generalized Association Rules", Proc. Of the 21st Int’l Conference on VLDB, pp. 407-419, Zurich, Switzerland, Sep 1995.
18.A. Savasere, E. Omiecinski and S. Navathe, "Mining for Strong Negative Associations in a Large Database of Customer Transactions", In Proc. of the IEEE 14th int. Conference. On Data Engineering, Orlando, FL, Feb 1998(forthcoming).
19.王慶堯，民國89年，利用準大項目集之漸進式挖掘，義守大學資訊工程研究所碩士論文。
20.許智豪，民國89年，在動態資料庫中作線上挖掘關聯式法則，國立中興大學資訊科學研究所碩士論文。