臺灣博碩士論文加值系統

在資料探勘(Data Mining)技術中，關聯規則的應用是最為廣泛且最常被討論的，並被視為是適合應用於購物籃分析(Market Basket Analysis)，以展現顧客購買行為規律性的一種方法。然而，受限於資料型態的問題，過去研究所應用的資料型態大多為類別項目形式，使關聯規則探勘方法無法應用在有數值型態的資料中，為了解決上述之問題，本研究發展一個適合應用於數值型態資料的「最佳化之模糊關聯規則演算法」。

本研究所提出之最佳化模糊關聯規則演算法，是以基因染色體的觀念將資料的特徵屬性個數與期望產生的語意項目個數進行編碼，並且利用基因演算法尋找最佳解的長處，客觀且自動地產生各特徵屬性的模糊歸屬函數參數，找到適合於資料集合的模糊集合，改善以往模糊集合歸屬函數參數必須由人為設定，較不具客觀性的缺點；數值型態資料運用基因演化所產生的模糊集合進行模糊化後，可以衡量每筆數值型態資料對應於每個模糊語意項目區間的歸屬程度，並以FTDA(Fuzzy Transaction Data-mining Algorithm)演算法產生適當地模糊關聯規則，改善過去無法以數值型態資料進行關聯規則探勘的限制；最後，以測試資料驗證所挖掘到的模糊關聯規則是否具有預測準確性，並將結果做為基因演算法中染色體疊代的根據，以挖掘出適於使用者需求且預測準確性佳的模糊關聯規則。經過一系列的實驗分析後，我們發現模糊關聯規則演算法能夠順利的從數值型態資料中挖掘到適當地模糊關聯規則，所獲得的預測準確性也能有不錯的表現。

Association rule is one of the most often discussed data mining technology. It is used in market basket analysis to know the regularity of customer’s purchase behavior. Although association rule is popular, it is limited to the item with categorical value. To solve the difficulty, this research develops an optimal fuzzy association rule algorithm so that the items with numerical data values can also be applied. First, linguistic sets of each attribute are encoded as genes of a chromosome. The optimal fuzzy membership functions are generated automatically after a serous of genetic evolution. Then, the fuzzy transaction data-mining algorithm (FTDA) is used to produce fuzzy association rules. Finally, testing data is used to evaluate the accuracy of generated fuzzy association rules. Through a series of experiments, it is shown that the algorithm is suitable for items with numerical data and performs high forecast accuracy.

中文摘要 i
英文摘要 iii
致謝 iv
圖目錄 viii
表目錄 x

第一章 緒論 1

1.1. 研究動機與背景 1
1.2. 問題描述 3
1.3. 研究目的 5
1.4. 論文架構 6

第二章 文獻探討 8

2.1. 關聯規則 8
2.1.1. Apriori演算法 12
2.2. 模糊理論 17
2.2.1. 模糊集合的定義 18
2.2.2. 模糊集合運算 20
2.2.3. 模糊理論於關聯規則探勘的應用 21
2.3. 基因演算法 24
2.3.1. 基因演算法之演算流程 25
2.4. 關聯規則結果的評估 31

第三章 研究方法 35
3.1. 研究流程架構 35
3.2. 利用模糊集合進行資料模糊化 38
3.3. 基因演算法之參數設定 39
3.3.1. 設計適應度函數 41
3.3.2. 染色體編碼 43
3.3.3. 染色體的挑選、複製、交配與突變 47
3.4. 模糊關聯規則的挖掘 48
3.5. 規則預測準確性 52

第四章 實驗與結果討論 60

4.1. 實驗環境與實驗資料 60
4.2. 使用者介面之操作說明 62
4.3. 演算法各項參數設定結果分析 67
4.3.1. 支持度門檻值與信心度門檻值參數討論 69
4.3.2. 訓練率參數討論 74
4.3.3. 語意項目個數參數討論 76



第五章 實作案例說明 80

5.1. 應用案例說明 80
5.2. 模糊關聯規則探勘應用與分析 83
5.2.1. 模糊關聯規則演算實驗分析 83
5.2.2. 模糊關聯規則結果 86

第六章 結論與未來研究 93

6.1. 結論 93
6.2. 未來研究方向 94

參考文獻 95

1.Agrawal, R. and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proceedings 20th International Conference on Very Large Databases, Santiago, Chile, pp. 487-499, 1994.
2.Agrawal, R., T. Imielinsld, and A. Swami, “Mining Association Rules Between Sets of Items in Large Databases,” Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington DC, USA, pp. 207-216, 1993.
3.Carse, B., T. C. Fogarty and A. Munro, “Evolving Fuzzy Rule Based Controllers Using Genetic Algorithms,” Fuzzy Sets and System, Vol. 80, Issue. 3, pp. 273-293, 1996.
4.Fayyad, U. M., “Data Mining and Knowledge Discovery: Making Sense Out of Data,” IEEE Expert, Vol. 11, Issue. 5, pp. 20-25, 1996.
5.Ghosh, A. and B. Nath, “Multi-objective Rule Mining Using Genetic Algorithms,” Information Sciences, Vol. 163, Issue. 1~3, pp. 123–133, 2004.
6.Goulbourne, G., F. Coenen and P. Leng, "Algorithms for Computing Association Rules Using a Partial-support Tree," Knowledge-Based Systems, Vol. 13, pp.141-149, 2000.
7.Han, J. and M. Kamber, “Data Mining Concepts and Techeniques,” Morgan Kaufmann Publishers, 2001.
8.Han, J., J. Pei, and Y. Yin., “Mining Frequent Patterns without Candidate Generation,” In Proc. of the 2000 ACM SIGKDD International Conference on Management of Data, Dallas, Texas, United States, 2000.
9.Hoffmann, F. and G. Pfister, “Learning of a Fuzzy Control Rule Base Using Messy Genetic Algorithm,” Genetic Algorithm and Soft Computing (Studies in Fuzziness, Vol. 1, Issue. 8, pp. 279-305, 1996.
10.Holland, J., “Adaptation in Natural and Artificial Systems,” University of Michigan Press, 1975.
11.Hong, T. P, K. Y. Lin, B. C. Chien, “Mining Fuzzy Multiple-level Association Rules from Quantitative Data,” Applied Intelligence, Vol. 18, pp 79-90, 2003.
12.Hong, T. P, K. Y. Lin, S. L. Wang, “Fuzzy Data Mining for Interesting Generalized Association Rules,” Fuzzy Set and System, Vol. 138, Issue 2, pp. 255-269, 2003.
13.Hong, T. P., C. S. Kuo and S. C. Chi, “Mining Association Rules from Quantitative Data,” Intelligent Data Analysis, Vol. 3, Issue 5, pp. 363-376, 1999.
14.Hu, Y.C., R.S. Chen, G.H. Tzeng, “Discovering Fuzzy Association Rules Using Fuzzy Partition Methods,” Knowledge-Based Systems, Vol.16, Issue 3, pp. 137–147, 2003.
15.Hu, Y.C., R.S. Chen, G.H. Tzeng, “Mining Fuzzy Association Rules for Classification Problems,” Computers & Industrial Engineering Vol. 43, Issue 4, pp. 735-750, 2002.
16.Kim, M. W., J. G. Lee and C. Min, “Efficient Fuzzy Rule Generation Based on Fuzzy Decision Tree for Data Mining,” Proceedings of 1999 IEEE International Conference on Fuzzy Systems, Seoul, Korea ,Vol.3, pp. 1223-1228, 1999.
17.Kuncheva, L. I., “How Good are Fuzzy If-then Classifiers,” IEEE Trans. on System, Man, and Cybernetics-Part B, Vol.30, Issue 4, pp 501-509, 2000.
18.Li, J.,H. Shen and R. Topor, “Mining Informative Rule Set for Prediction,” Journal of Intelligent Information Systems, Vol.22, Issue 2, pp. 155-174, 2004.
19.Li, J.,H. Shen and R. Topor, “Mining the Optimal Class Association Rule Set,” Knowledge-Based Systems, Vol.15, Issue 7, pp. 399-405, 2002
20.Liu, B. D., C. Y. Chen and J. Y. Tsao, “Design of Adaptive Fuzzy Logic Controller Based on Linguistic-hedge Concepts and Genetic Algorithms,” IEEE Trans. on System, Man and Cybernetics, Vol.31, Issue 1, 32-53, 2001.
21.Liu, B., Y. Ma, and C. K. Wong “Scoring and Ranking the Data Using Association Rules,” Data Mining, Rough Sets and Granular Computing, Heidelberg, Germany, pp. 190-215, 2002.
22.Mannila, H., “Building an Association Rules Framework to Improve Product Assortment Decisions,” Data Mining and Knowledge Discovery, Vol. 8, No. 1, pp. 7-23, 2004.
23.Rastogi, R. and K. Shim, “Mining Optimized Support Rules for Numeric Attributes,” Information Systems, Sydney, Australia, Vol. 26, pp 425-444, 2001.
24.Savasere , A., E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proc. 21st International Conference on Very Large Databases, Zurich, Switzerland, pp. 432-444, 1995.
25.Scott, A., “An Introduction to Genetic Algorithms,” AI Expert, Vol.4, No.3, pp. 49-53, 1990.
26.Shimojima, K., T. Fukuda and Y. Hasegawa, “Virus-evolutionary Genetic Algorithm for Fuzzy Controller Optimization,” Genetic Algorithm and Soft Computing, Vol. 1, Issue 8, pp. 369-388, 1996.
27.Silberschatz, A. and A. Tuzhilin, “What Makes Patterns Interesting in Knowledge Discovery Systems,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8, Issue 6, pp. 970-974,1996.
28.Simoudis, E., “Reality Check for Data Mining,” IEEE Expert, Vol. 11, Issue 5, pp. 26-33, 1996.
29.Srinivas, M., and L. M. Patnaik, “Genetic Algorithms: A Survey,” IEEE Computer, Vol. 27, No. 6, pp. 17-26, 1994.
30.Tang, K. S., K. F. Man, Z. F Liu and S. Kwong, “Minimal Fuzzy Memberships and Rules Using Hierarchical Genetic Algorithms,” IEEE Trans. on Industrial Electronics, Vol. 45, Issue 1, pp. 162-169, 1998.
31.Tsay, Y. J. and Y. W. Chang-Chien, “An Efficient Cluster and Decomposition Algorithm for Mining Association Rules,” Information Sciences, Vol. 160, Issue 1-4, pp. 161–171, 2004.
32.Wang, Y. F, Y. L. Chuang, M. H. Hsu and H. C. Keh, “A Personalized Recommender System for the Cosmetic Business,” Expert Systems with Applications, Vol. 26, pp. 427-434, 2004.
33.Wur, S.Y. and Y. Leu, “An Effective Boolean Algorithm for Mining Association Rules in Large Databases, ” Proc. of 6th Int. Conf. Database Systems for Advanced Applications, Hsinchu, Taiwan, ROC, pp. 179-186, 1999.
34.Zadeh, L. A., “Fuzzy sets,” Information Control, Vol.8, pp.338-353, 1965.
35.心臟病數據庫說明，http://www.sgi.com/tech/mlc/db/cleveland.names
36.王文俊，認識Fuzzy，全華科技出版社，1997。
37.李允中、王小璠、蘇木春，模糊理論及其應用，全華科技出版社，2004。
38.林桂英，「從數值型資料挖掘模糊多層級關連規則及模糊順序性樣式」，義守大學資訊工程學系碩士論文，2000。
39.施衣喬，「適用於入侵偵測之模糊關聯法則機制研究」，大葉資訊管理研究所碩士論文，2002。
40.胡宜中，「模糊知識探勘之多屬性決策」，交通大學資訊管理研究所博士論文，2002。
41.郭展盛，「數量化資料模糊挖掘模式之研究」，義守大學管理科學研究所碩士論文，1998。
42.陳宏銘，「設計最佳化之演化式模糊決策樹」，逢甲大學資訊工程研究所碩士論文，2001。
43.陳俊豪，「利用遺傳演算法探勘隸屬函數與模糊關聯規則」，義守大學資訊管理學系碩士論文，2003。
44.陳泰康，「使用智慧型基因演算法設計高效能的模糊系統」，逢甲大學資訊工程研究所碩士論文，2000。
45.陳耀茂，模糊理論，五南出版社，2000。
46.黃博聞，「發展一個關聯分群方法於多物項存貨管理」，元智大學工業工程與管理研究所碩士論文，2004。
47.楊洸，「近似推論在模糊決策制定之研究」，台灣師範大學資訊教育研究所碩士論文，1999。
48.葉家妤，「應用最佳化模糊決策樹於顧客關係管理之研究」，元智大學工業工程與管理研究所碩士論文，2004。
49.劉泓郁，「建構一個以模糊關聯法則為基礎之產品開發系統」，元智大學工業工程與管理研究所碩士論文，2002。
50.蘇建源，「模糊邏輯與資料探勘技術為基礎在顧客關係管理上之研究與應用」，南華大學資訊管理研究所碩士論文，2003。