臺灣博碩士論文加值系統

隨著交易、文件、日常處理資料的電子化、各種型式的資料被大量的累積下來，也隨著資訊科技的進步，資料探勘的技術變得日益重要，並且已經廣泛的應用在商業上的預測以及決策的支援。而關聯規則探勘在資料探勘的領域中也扮演相當重要的地位。
首先本研究提出一個新的關聯規則演算法GSA (Gradational Scanning Algorithm)，GSA演算法主要是利用Ck+1=Ck*Ck的概念產生候選項目集，且加入階段搜尋的概念，並配合過濾機制，使得候選項目集之數量逼近高頻項目集之數量，有效增進探勘的效能，而且GSA演算法最少只需掃描4次資料庫，最多掃描6次資料庫便可完成所有探勘。
然而，GSA演算法也和探勘傳統關聯規則的演算法相同，在探勘上往往會得到大量高頻項目集和關聯規則，為了解決傳統關聯規則演算法的問題，本研究提出CC_GDA和CC_GSA演算法來探勘完全相關型樣（closed correlated pattern）。主要利用N. Pasquie所提出的探勘完全項目集的概念，加GDA和GDA演算法的優點，再配合all-confidence的判斷，可避免傳統完全項目集探勘所產生的資訊遺失問題，重要的是也能探勘出數量少且具關聯性之型樣 (patterns)。
接著將GSA演算法在計算支持度和信賴度上做了一些修改，使它成為適合用於連鎖商店的探勘演算法GSA_TP，以便能更精確及更有效率的在連鎖商店的資料庫下探勘出有用的資訊。

Due to transactions, documents and data are transformed into electronic types. The large number of data has been accumulated. Today, the science and technology make a great progress. Therefore, data mining technology becomes more important than before in recent years. It is generally applied in commerce and the decisions making. In data mining territory, mining association rules plays a quite important position.
First of all, we propose a new algorithm－GSA(Gradational Scanning Algorithm) for mining association rules. GSA basically use the concept of Ck+1=Ck*Ck to generate the candidates. It also utilizes the concept of gradational scanning and the filtration mechanisms to reduce the number of candidates. CSA uses filtration mechanisms to reduce a great number of candidates which are very possible to be frequent itemsets and improves the performance of the GDA. The GSA needs to scan the Database four times at least and at most six times to finish the mining process.
However, the GSA Algorithm is the same as general association mining algorithms which will often derive a large number of frequent itemsets and association rules. We propose new algorithms－CC_GDA and CC_GSA to mining closed correlated patterns for solving the traditional association mining problem. These algorithms use the concept of closed itemsets mining which is proposed by N. Pasquier. It also utilizes the advantages of GDA and GSA algorithm and uses concept of all-confidence to determine whether the frequent itemsets will be the useful information. The CC_GDA and CC_GSA algorithm can avoid losing information from mining closed itemsets; it is also very important to mine a small number of these patterns which are correlated.
Furthermore, we propose the GSA_TP (Gradational Scanning Algorithm for mining Time-Place association rules) by modifying the calculation on supports and confidences in order to mining useful information efficiently and accurately in chain of retail stores.

摘　　要
Abstract
誌　　謝
目　　次
表　目　錄
圖　目　錄
第一章　緒論
1.1 研究背景
1.2 研究動機與目的
1.3 研究流程
1.4 論文架構
第二章　文獻探討
2.1 資料探勘
2.1.1 知識探索與資料探勘
2.2 關聯規則
2.2.1 相關定義
2.2.2 相關演算法
2.2.2.1 Apriori演算法
2.2.2.2 FP-growth演算法
2.2.2.3 Opportunistic Projection (OP) 演算法
2.2.2.4 ICI演算法
2.2.2.5 QDI演算法
2.2.2.6 IDA演算法
2.2.2.7 GDA演算法
2.2.2.8 EFI演算法
2.3 完全相關型樣
2.3.1相關定義
2.3.2 相關演算法
2.3.2.1 CCMine演算法
2.4 在連鎖商店上的應用
2.4.1 相關定義
2.4.2 相關演算法
2.4.2.1 Apriori_TP演算法
2.4.2.1 GDA_TP演算法
第三章　研究方法
3.1 關聯規則探勘演算法－GSA演算法
3.1.1 GSA演算法流程
3.1.2 GSA演算法概念說明
3.1.3資料壓縮
3.1.4 縮短交易長度
3.1.5 項目集表
3.1.6 候選項目集之產生與階段搜尋
3.1.7 修剪候選項目集
3.1.8記憶體不足時之解決方法
3.1.9 GSA演算法運行於大型資料庫之方法
3.1.10 GSA演算法實例說明
3.2 完全相關型樣探勘演算法
3.2.1 CC_GDA演算法
3.2.1.1 CC_GDA演算法流程
3.2.1.2 CC_GDA演算法概念說明
3.2.1.3依交易長度分別存放
3.2.1.4 階段拆解
3.2.1.5包含之檢查
3.2.1.6 CC_GDA演算法運行於大型資料庫之方法
3.2.1.7 CC_GDA演算法實例說明
3.2.2 CC_GSA演算法
3.2.2.1 CC_GSA演算法流程
3.2.2.2 CC_GSA演算法概念說明
3.2.2.3 CC_GSA演算法運行於大型資料庫之方法
3.2.2.4 CC_GSA演算法實例說明
3.3 在連鎖商店上的應用－GSA_TP演算法
3.3.1 GSA_TP演算法流程
3.3.2 GSA_TP演算法概念說明
3.3.3 GSA_TP演算法實例說明
第四章　實驗模擬
4.1 實驗設備
4.1.1 實驗環境
4.1.2 資料庫參數說明
4.2 GSA演算法之效能評估
4.2.1 測試的演算法
4.2.1.1 Apriori及FP-growth 演算法效能驗證
4.2.1.1 OP 演算法效能驗證
4.2.2 實驗設計
4.2.3 測試結果與分析
4.3 CC_GDA與CC_GSA演算法之效能評估
4.3.1 測試的演算法
4.3.1.1 CCMine 演算法效能驗證
4.3.2 實驗設計
4.3.3 測試結果與分析
4.4 GSA_TP之效能評估
4.4.1 測試的演算法
4.4.2 實驗參數
4.4.3 實驗設計
4.4.4 測試結果與分析
第五章　結論與未來研究
5.1 結論
5.2 未來研究
參考文獻

1.沈仁傑，多商店下的關聯規則挖掘，國立中央大學資訊管理學系碩士論文，民91年6月。

2.黃仁鵬，藍國誠，高效率探勘關聯規則之演算法-EFI，資訊管理學報。(Acccepted)

3.黃仁鵬、錢依佩、吳聲弘，高效率之關聯規則探勘演算法，第十四屆國際資訊管理學術研討會，p155，民92年6月。

4.黃南傑，高效率拆解之關聯規則探勘，南台科技大學資訊管理系碩士論文，民93年6月。

5.熊浩志，快速資料探勘演算法與相關應用，南台科技大學 資訊管理系碩士論文，民94年。

6.Pieter Adriaans, Dolf Zantinge, Data Mining. Addison Wesley Longman, 1996

7.R. Agrawal, & R. Srikant, "Fast algorithms for mining association rules," Proceedings of 1994 International Conference on Very Large Data Bases, pp.487-499, 1994.

8.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, pp.207-216, 1993.

9.M. Antonie, O. R. Zaine, and A. Coman, "Application of Data Mining Techniques for Medical Image Classification," Proc. of Second Intl. Workshop on Multimedia Data Mining (MDM/KDD'2001) in conjunction with Seventh ACM SIGKDD, pp.94-101, San Francisco, CA, August 26, 2001.

10.K. Asanobu, "Data Mining for Typhoon Image Collection," Proceedings of the 2nd International Workshop on Multimedia Data Mining, pp.68-77, August 2001.

11.J. Basak, A. Sudarshan, D. Trivedi and M. S. Santhanam, "Weather Data Mining Using Independent Component Analysis," The Journal of Machine Learning Research, Volume 5, pp.239-253, December 2004.

12.S. Brin, R. Motwani, J. D. Ullman, and S. Tsur,"Dynamic Itemset Counting and Implication Rules for Market Basket Data," ACM SIGMOD Conf. Management of Data, 1997.

13.F. C. Tseng, and C. C. Hsu. "Creating frequent patterns with the frequent pattern list," Proc. Of the Asia Pacific Conference of Data Mining and Knowledge Discovery, Hong Kong, pp.376-386, 2001.

14.J. Han, and M. Kamber, "Data Mining: Concepts and Techniques," Morgan Kaufmann, August 2000.
15.J. Han, J. Pei, and Y. Yin, "Mining Frequent Patterns without Candidate Generation," Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.1-12, 2000.
16.D. Lin, and Z. M. Kedem, "Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set," Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, pp105-119, 1998.
17.J. Liu, Y. Pan, K. Wang, and J. Han, " Mining Frequent Item Sets by Opportunistic Projection '', Proc. 2002 Int. Conf. on Knowledge Discovery in Databases (KDD'02), Edmonton, Canada, July 2002.
18.M. Seno and G. Karypis, "LPMiner: An Algorithm for Finding Frequent Itemsets Using Length-Decreasing Support Constraint," Proceedings of the 2001 IEEE International Conference on Data Mining(ICDM), pp.505-512, 2001.

19.E. Omiecinski., "Alternative interest measures for mining associations, " IEEE Trans.Knowledge and Data Engineering,2003, 15:57–69.

20.N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal., "Discovering frequent closed itemsets for association rules, " In Proc. 7th Int. Conf. Database Theory (ICDT’99), 1999,pages 398–416.

21.J. Pei, J. Han, and R. Mao. , "CLOSET: An efficient algorithm for mining frequent closed itemsets, " In DMKD'00,2000.

22.O. R. Zaine, M. Antonie, and A. Coman, "Mammography Classification by an Association Rule-Based Classifier," Third Intl. ACM SIGKDD Workshop on Multimedia Data Mining (MDM/KDD'2002) in conjunction with Eighth ACM SIGKDD, pp.62-69, Edmonton, Alberta, Canada, 17-19 July 2002.

23.J. S. Park, M. S. Chen, and P. S. Yu, "An Effective hash-based Algorithm for Mining Association Rules," Proceddings of the ACM SIGMOD Conference on Management of Data － SIGMOD'95, pp.175-186, May 1995.

24.J. Wang, J. Han, and J. Pei, "CLOSET+: Searching for the Best Strategies for Mining Frequent Closed Itemsets", Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD'03) ,2003.

25.Brijs T., Swinnen G., Vanhoof K., and Wets G., "The use of association rules for product assortment decisions: a case study," in: Proceedings of the Fifth International Conference on Knowledge Discovery and Data Mining, San Diego (USA), August 15-18, pp. 254-260,1999.

26.X. Wu, "Data mining: artificial intelligence in data analysis," Intelligent Agent Technology (IAT 2004). Proceedings. IEEE/WIC/ACM International Conference on 2004, 2004.

27.W.-Y. Kim, Y.-K. Lee, and J. Han, "CCMine: Efficient Mining of Confidence-Closed Correlated Patterns," Proc. 2004 Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'04) ,2004

28.M. Zaki , C. Hsiao. ,“CHARM: An efficient algorithm for closed itemset mining,” In SDM'02. ,2002

29.Z. Zheng, R. Kohavi, and L. Mason, "Real World Performance of Association Rule Algorithms", Proceedings of the 7th International Conference on Knowledge Discovery and Data Mining (KDD), New York, 2001.

30.http://www.almaden.ibm.com/software/quest/Resources/datasets/syndata.html#assocSynData.

31.http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html.