臺灣博碩士論文加值系統

資訊科技的快速進步，已完全介入了我們的生活中。隨著資料量的迅速累積、資料探勘（data mining）的盛行，在龐大的資料庫中找出有用的資訊以供我們採取更好及正確的行動顯然是未來必然的趨勢。在資料探勘的應用中，關聯法則（association rules）是最常被用來做分析的技術。目前關聯法則的演算法可分為頻繁樣式樹（frequent-pattern tree）與類推理方法（apriori-like approach）兩大代表。此兩者最主要的差異在於前者避免多次的大量的資料庫掃瞄，並不產生候選項目集；而後者則是利用產生候選項目集的方法。
一般傳統的關聯法則挖掘著重於商品的交易數量，使得低銷售量但高利潤的商品往往被忽略。本文的目的在於提供一種演算法，以商品獲利性為依據，訂定出不同的支持度（support）門檻。並以頻繁樣式樹為基礎，提出一套新的演算法，能快速的找出多重支持度（multiple supports）的關聯法則，除可挖掘暢銷商品外，亦可處理高獲利但銷售量較低的商品之相關關聯法則挖掘。

Information technology progress fast, it has completely stepped in our life. According to the data accumulated rapidly and the prevalence of data mining(extracting useful information out of raw database), we realize finding the useful information for a better and correct decision from a huge database is the inevitable trend in the future. In various applications of data mining, association rules are the common technologies used for analysis. So far algorithms of association rules were classified into two major methods : frequent-pattern tree and apriori-like approach, the former can avoid a great deal of database repeated scanning that will not output the candidate itemsets; on the other hand, the latter approach needs to generate candidate itemsets during the process.
The traditional association rules in general pay more attention to mine the transactions of enormous volume of merchandise, thus the goods with low sales volume but high profit is usually ignored. The purpose of the thesis is going to provide a calculation model, in accordance with the profitability of merchandise by setting up different sort of supports. And base on a frequent-pattern tree, our model will enable to quickly search out the rules with multiple supports. Besides mining the well-sold merchandise, it also can deal with discovering association rules from database with high profit but low sales volume.

第一章 導論 1
一、 資料探勘 1
二、 資料探勘技術 3
1. 關聯式法則（Association Rule） 3
2. 時間序列分析（Time Sequence Analysis） 5
3. 分類式法則（Classification Rule） 6
4. 組群式法則（Clustering Rule） 7
5. 序列型樣（Sequential Pattern） 8
三、 研究背景與動機 8
四、 研究目的 9
五、 論文架構 10
第二章 文獻探討 11
一、 關聯法則 11
1. 關聯法則的意義及重要性 11
2. 關聯法則之定義及相關名詞介紹 11
3. 關聯法則之推導步驟 12
4. 關聯法則的相關應用 13
二、 類推理演算法（Apriori） 14
三、 夾擊搜尋演算法（Pincer-Search） 17
四、 頻繁樣式樹演算法（FP-growth） 18
五、 多重最小支持度相關規則 19
第三章 研究方法及步驟 22
一、 各商品支持度設定方法 22
二、 多重支持度之FP-growth演算法 25
1. 建樹流程 26
2. 頻繁項目集推導 29
第四章 實驗結果與討論 36
一、 實驗設備及說明 36
二、 實驗設計 36
三、 實驗結果與分析 39
第五章 結論與未來研究 41
一、 結論 41
二、 未來研究 41
第六章 參考文獻 42
一、 中文部分 42
二、 西文部分 42

一、中文部分
【1】郭文建(2002)，資料探勘技術簡介與應用，電信研究雙月刊，32(6)，p719 –728。
二、西文部分
[1]B. Liu, W. Hsu, L.F. Mun, and H.Y. Yan, “Finding Interesting Patterns Using User Expectations”, IEEE Transactions on Knowledge and Data Engineering, Vol. 11, No. 6, November/December 1999.
[2]B. Liu, W. Hsu, and Y. Ma, “Mining Association Rules with Multiple Minimum Supports”, Proc. 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.337-341, May 1999.
[3]D. Lin and Z. M. Kedem, “Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set,” Proc. VI Intl. Conf. on Extending Database Technology, 1998.
[4]E. H. Han, G. Karypis, and V. Kumar, “Scalable Parallel Data Mining for Association Rules,” ACM SIGMOD, pp. 277-288, 1997.
[5]H. Frigui and R. Krishnapuram, “A Robust Clustering Algorithm Based on Competitive Agglomeration and Soft Rejection of Outliers”, IEEE onComputer Vision and Pattern Recognition, pp.550-555, 1996.
[6]H. Mannila and P. Ronkainen, “Similarity of Event Sequences (Revised version)”, Proceedings of the Fourth International Workshop on Temporal Representation and Reasoning (TIME’97), Daytona Breach, Florida, USA, pp.136-139, May 1997.
[7]J. Elder IV and D. Pregibon, “A statistics perspective on knowledge discovery in databases”, In U.M. Fayyad, G.. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, Page83-115. AAAI/MIT Press, 1996.
[8]J. Han and M. Kamber, “Data Mining: Concepts and Techniques,” Morgan Kaufmann Publishers, 2001.
[9]J. Han, J. Pei, and Y. Yin, "Mining Frequent Patterns without Candidate Generation", Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD'00), Dallas, TX, May 2000, pp: 1-12.
[10]K. Ali, S. Manganaris, and R. Srikant, “Partial Classification using Association Rules,” Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, August 1997, Newport Beach, California.
[11]K. Alsabti, S. Ranka, and V. Singh, “An Efficient K-Means Clustering Algorithm,” PPS/SPDP Workshop on High performance Data Mining, 1997.
[12]L. Breiman, J. Friedman, R. Olshen, and C. Stone, “Classification of Regression Trees,” Wadsworth, 1984.
[13]L. Cristofor, http://www.cs.umb.edu/
[14]L. Kaufman and P. J. Rousseeuw, “Finding Groups in Data: an Introduction to Cluster Analysis,” John Wiley & Sons, 1990.
[15]M. S. Chen, J. Han, and P.S. Yu, “Data Mining: An Overview from a Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8,No. 6, December 1996.
[16]R. Agrawal and R. Srikant, “Fast Algorithm for Mining Association Rules in Large Databases”, Proc. 1994 Int'l Conf. VLDB, pp. 487-499, September 1994,Santiago, Chile.
[17]R. Agrawal and R. Srikant, “Mining sequential patterns”, Proc. of Eleventh International Conf. on Data Engineering, IEEE Computer Society Press, pp. 3-4,1995.
[18]R. Agrawal, T. Imilienski, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases”, Proceedings of the ACM SIGMOD Int'l Conf. on Management of Data, pp. 207-216, May 1993.
[19]R. Brause, T. Langsdort, and M. Hepp, “Neural Data Mining for Credit Card Fraud Detection,” Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, 1999.
[20]R. Stuart and P. Norvig, ” Learning Decision tree” , 1995
[21]R. Taouil, Y. Bastide, N. Pasquier, G. Stumme, and L. Lakhal, “Mining bases for association rules based on formal concept analysis,” 16th IEEE Intl. Conf. on Data Engineering, Feb. 2000.
[22]S. Brin, R. Motwani, and C. Silverstein, "Beyond Market Baskets: Generalizing Association Rules to Correlations", 1997 ACM SIGMOD Conference on Management of Data, pp. 265-276, 1997.
[23]S. M. Weiss and C. A. Kulikowski, “Computer System that Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert System,” 1991, Morgan Kaufman.