臺灣博碩士論文加值系統

關聯法則為資料探勘技術中最廣泛應用之技術。最具代表性之Apriori演算法，具有(1)產生大量候選項目集；(2)掃瞄資料庫次數過多之瓶頸，相關研究皆針對Apriori演算法之瓶頸進行改良。本研究以克服Apriori演算法之效能瓶頸為目標，提出兩個以矩陣及布林運算(AND)為基礎的新關聯法則演算法MABAR(Matrix_AND Based Association Rule)與MEBAR(Matrix_Equivalence Based Association Rule)，其中MABAR演算法具有只需一次資料庫掃瞄，無需產生大量候選項目集，無需經過資料庫掃瞄即可發掘所有高頻項目集(利用AND運算)以及一次運算程序中可發掘多種長度之高頻項目集等特性。MEBAR演算法具有只需一次資料庫掃瞄，無需產生大量C2即可直接發掘L2，無需逐層產生候選項目集即可產生所有潛在候選項目集(利用布林上三角矩陣、等價關係特性)以及無需經過資料庫掃瞄即可發掘所有高頻項目集(利用AND運算)等特性。本研究所提出之MABAR與MEBAR演算法，經由模擬實驗證實可確保資料探勘結果之正確性，並達到降低資料庫掃瞄次數與時間成本，降低記憶體使用需求與提昇資料探勘效能之目標。

Algorithms of association rules in techniques of data mining are used to find associations of products. Proposed association algorithms in the present studies contain weaknesses such as generating a lot of candidate itemsets, and repeated scanning over the database. In this paper, we present two new algorithms named Matrix_AND Based Association Rule (MABAR) and Matrix_Equivlence Based Association Rule (MEBAR) for efficient association rule mining to overcome these described drawbacks. MABAR is designed based on Matrix and AND Boolean expressions, and MEBAR is designed based on Matrix and Equivlence. Both of MABAR and MEBAR require scan database once, discover frequent itemsets without level by level, and require less memory under ensure the correctness of the mined results. Besides, the results of experiments with real-life database show that we can discover all frequent itemsets with MABAR algorithm and MEBAR algorithm faster than Apriori algorithm. Hence, both of MABAR and MEBAR outperform Apriori, and are also helpful for the decision makers to make a promoting policy and gain more profits for the company.

摘要 I
英文摘要 II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 IX
1、緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 3
1.4 研究流程 4
1.5論文架構 5
2、文獻探討 6
2.1 資料探勘 6
2.1.1資料探勘之定義 6
2.1.2資料探勘技術所面臨之困難與挑戰 7
2.1.3資料探勘技術之分類 8
2.1.4資料探勘技術介紹 8
2.1.5資料探勘之流程 10
2.1.6資料探勘技術之應用 11
2.2 關聯法則 13
2.2.1關聯法則之意義 13
2.2.2關聯法則之優點 14
2.2.3關聯法則之演進 15
2.3 Apriori演算法 19
2.4 Partition演算法 23
2.5 Dynamic Itemset Counting (DIC)演算法 25
2.6 Tree-Based Association Rule (TBAR)演算法 27
2.7矩陣法(Matrix Approach) 31
3、研究方法 35
3.1矩陣與AND運算為基礎之關聯法則(MABAR) 37
3.1.1 MABAR演算法 37
3.1.2 MABAR範例推演 41
3.2矩陣與等價關係為基礎之關聯法則(MEBAR) 45
3.2.1 MEBAR演算法 49
3.2.2 MEBAR範例推演 55
4、模擬實驗 59
4.1實驗平台與測試資料庫 59
4.2 實驗設計 61
4.3 實驗結果與分析 61
4.3.1 MABAR模擬實驗 61
4.3.2 MEBAR模擬實驗 68
5、結論與未來發展 76
5.1矩陣與AND運算為基礎之關聯法則(MABAR) 76
5.2矩陣與等價關係為基礎之關聯法則(MEBAR) 77
5.3 未來研究發展 78
參考文獻 79
作者簡介 84

[1] 王皓正，民國八十九年，時間序列資料之查詢與資料發掘－以台灣股市為例，國立台灣大學資訊管理研究所碩士論文。
[2] 李建億、潘冠良、吳政道，『運用矩陣運算策略來提昇關聯法則探勘效能之研究』，中華民國第九屆模糊理論及其應用會議，2001。
[3] 李秀梅，民國八十九年，信用卡持卡者資料探勘之研究，輔仁大學應用統計學研究所碩士論文。
[4] 李姿儀，民國八十九年，醫院門診資料探勘－以虎尾若瑟醫院為例，南華大學資訊管理研究所碩士論文。
[5] 李榮添，民國九十年，資料探勘技術應用於證券業關係行銷之研究，國立中正大學資訊管理研究所碩士論文。
[6] 吳恆睿，民國八十九年，中醫院揀藥儲位規劃之研究，逢甲大學工業工程研究所碩士論文。
[7] 林傑斌、劉明德，2002年五月，資料採礦與OLAP理論與實務，台北：文魁資訊。
[8] 花伴柱，民國九十年，資料探勘技術在藥品行銷應用之研究-以國內某製藥公司為例，國立中正大學資訊管理研究所碩士論文。
[9] 徐家馴，民國八十九年，在教學網站的環境中發掘熱門學習路線，輔仁大學資訊工程研究所碩士論文。
[10] 翁瑞峰，民國九十年，網頁瀏覽者行為之泛化分群分析，國立交通大學資訊科學研究所碩士論文。
[11] 黃子嘉，「離散數學」，二版，鼎茂圖書公司，台北，民國八十六年。
[12] 黃彥文，民國八十八年，資料探勘之應用－會員消費特徵之發掘，國立屏東科技大學資訊管理研究所碩士論文。
[13] 黃勝崇，民國八十九年，資料探勘應用於醫療院所輔助病患看診指引之研究，南華大學資訊管理研究所碩士論文。
[14] 陳必強，民國九十年，資料探勘技術中關聯法則於購物型網站的應用，中華大學科技管理研究所碩士論文。
[15] 潘瓊如，民國八十九年，時間性路徑追蹤樣式之資料挖掘，國立台灣大學資訊管理研究所碩士論文。
[16] 蘇詠翔，民國九十年，資料探勘應用於股票電子交易客戶之特性，國立成功大學統計學系碩博士班碩士論文。
[17] Agrawal, R., Imielinski, T. and Swami, A., " Database Mining: A Performance Perspective," IEEE Transactions on Knowledge and Data Engineering, Volume 5, 1993, pp: 914-925.
[18] Agrawal, R., Imielinski, T. and Swami, A., "Mining Association Rules between Sets of Items in Large Databases," In Proceedings of ACM SIGMOD Conference on Management of Data, May 1993, pp: 207-216.
[19] Agrawal, R. and Srikant, R., "Fast Algorithms for Mining Association Rules," In Proceedings of the 20th International Conf. on Very Large Databases, Sept. 1994.
[20] Agrawal, R. and Srikant, R., "Mining Sequential Patterns," In Proceedings of the International Conference on Data Engineering (ICDE), Taiwan, March 1995.
[21] Bayardo Jr., R. J., "Efficiently Mining Long Patterns from Databases," In Proceedings of ACM SIGMOD Conf. on Management of Data, 1998, pp: 85-93.
[22] Bayardo, R. J., Agrawal, R. and Gunopulos, D., "Constraint-based rule mining in large, dense databases," In Proceedings of 15th International Conference on Data Engineering, 1999, pp: 255-264.
[23] Berry, M. J. A. and Linoff G., Data Mining Technique for Marketing Sale, and Customer Support, Wiley Computer, New York, 1997.
[24] Berzal, F., Cubero, J.-C., Marin, N., and Serrano, J.-M., "TBAR: An efficient method for association rule mining in relational databases," Data & Knowledge Engineering Vol: 37, 2001, pp: 47-64.
[25] Brin, S., Motwani, R., Ullman, J. D. "Dynamic Itemset Counting and Implication Rules for Market Basket Data," ACM SIGMOD Conf. on Management of Data, 1997, pp: 255-264.
[26] Brin, S., Motwani, R. and Silverastein, C., "Beyond Market Baskets: Generalizing Association Rules to Correlations," ACM SIGMOD Conf. on Management of Data, 1997, pp: 265-276.
[27] Carter, C., Hamilton, H. and Cercone, N., "Share Based Measures for Itemsets," Principles of Data Mining and Knowledge Discovery, J. Komorowski and J. Zytkow (Eds.), 1997, pp: 14-24.
[28] Chen, M.-S., Han, J. and Yu, P. S., "Data Mining: An Overview from a Database Perspective," IEEE Transactions on Knowledge and Data Engineering, Volume: 8, 1996, pp: 866-883.
[29] Cheung, D. W., Han, J., Ng, V. T., Fu, A. W. and Fu, Y., "A Fast Distributed Algorithm for Mining Association Rules," In Proceedings of 1996 International Conference on PDIS''96, Dec.1996.
[30] Dunkel, B. and Soparkar, N., "Data Organization and Access for Efficient Data Mining," ICDE, 1999, pp: 522-529.
[31] Fayyad,U. M., Piatetsky-Shapiro, G., and Smyth, P., "The KDD process for extracting useful knowledge from volumes of data," Communications of the ACM, Vol. 39, 1996, pp: 27-34.
[32] Fu, Y., "Data mining task, technique and applications," IEEE Potentials, 1997.
[33] Frawley, W., Piatetsky-Shapiro, G., and Matheus, C. Knowledge Discovery in Databases: An Overview, AI Magazine, Fall 1992, pp: 213-228.
[34] Grupe, F. H. and Owrang, M. M., "Database mining discovering new knowledge and cooperative advantage," Information Systems Management, Vol. 12, 1995, pp: 26-31.
[35] Han, J. and Fu, Y., "Discovery of Multiple-Level Association Rules from Large Databases," 1995 Int. Conf. Very Large Databases, Sept 1995, pp: 400-431.
[36] Han J. and Kamber, M., "Data Mining: Concepts and Techniques," Morgan Kaufmann Publishers, 2000.
[37] Han, J., Pei, J. and Yin, Y., "Mining Frequent Patterns without Candidate Generation," In Proceedings of ACM SIGMOD International Conference on Management of Data, 2000.
[38] IBM Intelligent Miner For Data, IBM, 1998.
[39] Lin, D. -I. and Kedem, Z. M., "Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set," In Proceedings of the 6th Int''l Conference on Extending Database Technology (EDBT), 1998.
[40] Liu, B., Hsu, W. and Ma, Y., "Mining Association Rules with Multiple Minimum Supports," In Proceedings of 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1999.
[41] Park, J. S., Chen, M.-S. and Yu, P. S., "Using A Hash-Based Method with Transaction Trimming for Mining Association Rules," IEEE(TKDE) Transactions on Knowledge and Data Engineering, (9:5), 1997, pp: 813-825.
[42] Park, J. S., Yu, P. S. and Chen, M. -S., "Mining Association Rules with Adjustable Accuracy," In CIKM, 1997, pp: 151-160.
[43] Savasere, A., Omiecinski, E., and Navathe, S., "An Efficient Algorithm for Mining Association Rules in Large Databases," In Proceedings of 21th VLDB, 1995, pp: 432-444.
[44] Srikant, R. and Agrawal, R., "Mining Generalized Association Rules," In Proceedings of the 21st Int''l Conference on VLDB, 1995, pp: 407-419.
[45] Toivonen, H., "Sampling large databases for association rules," In 22nd VLDB Conference, 1996, pp: 134-145.
[46] Wang, K., Tang, L., Han, J. and Liu, J., "Top down FP-Growth for Association Rule Mining," In Proceedings of the 6th PAKDD, 2002.
[47] Zaki, M. J., Parthasarathy, S., Ogihara, M. and Li, W., "New Algorithms for Fast Discovery of Association Rules," In Proc. of the Third Int''l Conf. on Knowledge Discovery and Data Mining, 1997, pp: 283-286.