臺灣博碩士論文加值系統

挖掘關聯法則是資料探勘(Data Mining)極為重要的應用模式之一，藉由發掘不同商品組合出現頻率的重複性，來掌握顧客的消費習性並做為決策的參考，可以確實的掌握致勝的關鍵時機。
　　本研究希望能對關聯法則的探勘方法，提出可行的改善方案，我們提出了一個以多階層分群為主的新關聯運算演算法MCBAR(Multiple Clustering Based Association Rule)，在讀取資料庫後針對L1進行分群，在分群後可以有效率的在較小的資料群中快速尋找符合最小支持度的高頻項目並避免產生不必要的候選資料集，我們並利用布林矩陣的方式儲存分群後的資料，使用布林矩陣除了可以加速運算的速度外，更可以加速之後分群的速度，在產生L1分群後我們使用Mask的方式將矩陣做適度的篩減有效的減少儲存的內容，經由模擬實驗證明資料探勘結果的正確性，並且有效降低候選項目集的產生及需搜尋的範圍，達到提昇資料探勘效能之目標。

One of these important module of data mining is Association Rule.
Association Rule can generate valuable information for dicision makers by discovering frequent outcoming results from tracking purchases. In this research, we provide a possible solution to improve Association Rule which is MCBAR(Multiple Clustering Based Association Rule).MCBAR sorts L1 in different groups after every retrieving data from database. Every divided data group can be mined for frequent items effectively from limited matching results. By storing every group in Boolean Matrix, we can have not only the faster operationand even the sorting performance.It also sieves out records from each matrix by Mask after grouping L1 for saving capability. In Our experimentation demonstrate the Result is correctness. And it can reduce the candidate item and scope to search. Finally it achieve our goal to promote the performance in Data Mining.

中文摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VIII

1. 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究流程 4
1.4論文架構 5
2. 文獻探討 6
2.1 資料探勘 6
2.2 關聯法則 9
2.2.1關聯法則之意義 9
2.2.2關聯法則之演進 10
2.3 Apriori演算法 14
2.4 Partition演算法 18
2.5 DIC演算法 20
2.6 FP-Growth演算法 22
2.7布林演算法 29

3. 研究方法 36
3.1多階層分群為基礎之關聯法則(MCBAR) 38
3.2 MCBAR範例推演 42
3.3 MCBAR的資料結構與實作 48

4. 模擬實驗 54
4.1實驗平台與測試資料庫 54
4.2 實驗設計 56
4.3 實驗結果與分析 56
5. 結論與未來發展 66
5.1結論 66
5.2未來研究發展 69
參考文獻 69
作者簡介 72

[1]陳垂呈，應用布林運算快速分群化交易項目，TANET 2001(台灣區網際網路研討會)，民國90年。
[2]陳垂呈，以有效率分群化演算法發掘消費者最適性之產品項目，TANET 2002 (台灣區網際網路研討會)，民國91年。
[3]顏秀珍、何仁傑、邱鼎穎。從大型資料庫中挖掘感興趣的型樣，第五屆人工智慧與應用研討會，頁84-91, 民國89年。
[4]張簡雅文，矩陣與布林運算為基礎之關聯法則研究，國立屏東科技大學資訊管理研究所碩士論文, 民國90年。
[5]賴瓊惠，使用布林演算法找出在大型資料庫中多階層序列型樣，
國立台灣科技大學資訊管理系碩士論文, 民國89年。
[6] Agrawal, R. and T. Imielinski, and A. Swami, 1993, Mining Association Rules between Sets of Items in Very Large Database, Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 207-216.
[7] Agrawal, R. and Srikant, R., “Fast Algorithms for Mining Association Rules in Large Database,” Proceedings of the 20th International Conference on Very Large Data Bases, pp. 487-499, 1994.
[8] A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules,” Proceedings of the 21st Conference of Very Large Databases(VLDB), pp. 432-444 (1995).
[9] Bayardo Jr., R. J., "Efficiently Mining Long Patterns from Databases,
" In Proceedings of ACM SIGMOD Conf. on Management of Data, 1998,
pp: 85-93.
[10] Han, J., Pei, J. and Yin, Y., “Mining Frequent Patterns without Candidate Generation,” Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 1-12, 2000.
[11] J. S. Park, M. S. Chen, and P. S. Yu, “An effective hash based algorithm for mining association rules,” Proceedings of the ACM SIGMOD International Conference on Management of Data, San Jose, USA, pp. 175-186 {1995}.
[12] Srikant, R. and Agrawal, R., “Mining Generalized Association Rules,”
Proceedings of the 21th International Conference on Very Large Data Bases,pp. 407-419, 1995.
[13] Srikant, R. and Agrawal, R., “Mining Quantitative Association Rules in Large Relational Tables,” Proceedings of the 1996 ACM SIGMOD Conference on Management of Data, pp. 1-12, 1996.
[14] S. Brin, R. Motwai, J.D. Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data,” 1997 ACM SIGMOD Conference on Management of Data, pp. 265-276, 1997.
[15] Savasere, A. Omiecinski, E., and Navathe, S. “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proc. 21th VLDB, pp.432-444, 1995.
[16] Wang, K., Tang, L., Han, J. and Liu, J., "Top down FP-Growth for Association Rule Mining," In Proceedings of the 6th PAKDD, 2002.
[17] Wur, S.Y. and Leu, Y., “An Effective Boolean Algorithm for Mining
Association Rules in Large Databases,” DASFAA, pp. 179-186, 1999.
[18] Zhang, T., Ramakrishnan, R. and Livny, M. “BIRCH: An Efficient Data Clustering Method for Very Large Database,” SIGMOD Record Quarterly Publication of the Special Interest Group on Management Data Vol. 25, No. 2, pp. 103-144, 1996