臺灣博碩士論文加值系統

關聯規則演算法是資料探勘 (Data Mining)中一項相當重要且實用的技術。過去的文獻中，關聯規則大多應用於購物籃分析上，用以找出不同項目間的關聯性。故若能有效地利用關聯規則的技術，便能找出大量資料中所隱含的資訊，來提供決策者更好的決策依據及提高企業的競爭力。然而，大部分的關聯規則應用上，通常僅考慮不同項目組合所產生的關聯性，並未充分的利用資料庫中相關的項目屬性，來提昇挖掘出之關聯規則的品質。此外，管理者總要花費許多的時間來決定挖掘過程中，萃取出關聯規則所需的最小支持度與最小信心度門檻值的設定方式，故如何快速且客觀地設定最小門檻值來得到有意義的規則便相當重要。
本論文中將提出一挖掘關聯規則的新演算法，其透過暫存支持度與資料叢集索引的概念來挖掘二元型態交易資料的關聯規則。同時藉由權重項目法的概念來反映不同項目間的重要性，並將之應用在啟發式方法－基因演算法中適應度函數與目標規則函數上。透過基因演算法演算速度快且屬於廣域搜尋的特性，及目標規則函數與權重值為考量，來評估不同關聯規則間的價值，進而產生一客觀的最小門檻值設定方式建議，以期能快速地挖掘出重要且有意義的關聯規則，供企業管理者進行決策分析。
為了驗證本研究所提出之方法為一有效之關聯規則挖掘法，本研究透過數個範例資料，以及一實際的信用卡消費案例資料之應用分析，探討在實際應用上對關聯規則產生結果的影響。由此些應用中可知，將權重項目法應用在基因演算法之適應度函數與目標規則函數的方式，確實能有效的評估規則間的價值與重要性，且藉由基因演化應用確實能快速且客觀地提供一合適的最小門檻值設定建議，來提昇挖掘關聯規則的品質與效率。因此，由上述應用結果可證明本研究所提出的方法，應用在挖掘關聯規則上確實具有其實用性。

Association rule is one of the most important and useful technologies in data mining applications. Association rule technologies extract unknown information from large database and summarize meaningful relation among items to help business managers make better decision. Currently, most of the technologies are focused on basket analysis in supermarkets. Although the usage of the technologies does improve the understanding of item relationships, most of these works consider only buying or not-buying behavior. They did not consider important item properties such as profits to raise the quality of generated association rules. In addition, deciding suitable threshold values of support and confidence is critical to the quality of association rule technology. However, there is few researches focus on how to decide the threshold values.
In this thesis, a new association rule algorithm is introduced to solve the above limitations. In this algorithm we use the concepts of temporary support and data index to represent association rules that are transformed into binary formats. To emphases other important item properties, this research uses the weighted items to represent the importance of individual items. These weighted items are used into the fitness function of heuristic genetic algorithms (GA) to estimate the value of different rules. The genetic algorithms can generate suitable threshold values for association rule mining.
The method proposed in this thesis is successfully applied to several retailing transaction databases and one real-world credit card database. These applications show that weighted items apply in fitness function of a genetic algorithm can estimate the value of association rules efficiently. It is also found that genetic algorithms can really suggest suitable threshold values to get quality rules. These results demonstrate that the proposed algorithm is a practical method for increasing the quality of generated association rules.

中文摘要　…………………………………………………………i
英文摘要　…………………………………………………………iii
致謝　………………………………………………………………v
目錄　………………………………………………………………vi
圖目錄　……………………………………………………………ix
表目錄　……………………………………………………………xii
第一章　緒論
　　1-1　研究背景　………………………………………………1
　　1-2　問題描述　………………………………………………3
　　1-3　研究目的　………………………………………………4
　　1-4　論文架構　………………………………………………5
第二章　文獻探討
　　2-1　關聯規則　………………………………………………7
　　　　2-1-1　關聯規則的定義　………………………………7
　　　　2-1-2　關聯規則的應用　………………………………9
　　　　2-1-3　關聯規則的類型　………………………………10
　　　　2-1-4　關聯規則演算法　………………………………11
　　2-2　啟發式方法 ─ 基因演算法　…………………………15
　　2-3　結合關聯規則與基因演算法之研究探討　……………19
第三章　研究方法
　　3-1　研究架構流程　…………………………………………22
　　3-2　資料型態轉換　…………………………………………24
　　3-3　Itemset 支持度計算模組　……………………………26
　　3-4　權重式關聯規則與權重項目評估模式　………………31
　　3-5　基因演算法評估模組　…………………………………34
　　　　3-5-1　目標規則評估函數　……………………………35
　　　　3-5-2　基因演算法應用模式　…………………………38
　　　　3-5-3　染色體規則分界點設定　………………………42
　　　　3-5-4　最適門檻值設定　………………………………45
第四章　系統實作
　　4-1　系統建構方式　…………………………………………47
　　4-2　系統應用與說明簡例　…………………………………51
第五章　實例應用結果與分析
　　5-1　應用案例說明　…………………………………………64
　　　　5-1-1　案例資料轉換　…………………………………64
　　5-2　權重項目應用分析　……………………………………68
　　　　5-2-1　權重項目轉換函數分析　………………………68
　　　　5-2-2　不同屬性的權重項目分析　……………………70
　　5-3　基因演化應用分析　……………………………………72
　　　　5-3-1　演化世代數與母體數分析　……………………72
　　　　5-3-2　交配率分析　……………………………………74
　　　　5-3-3　突變率分析　……………………………………75
　　　　5-3-4　目標值分析　……………………………………76
　　5-4　結果分析　………………………………………………78
　　5-5　二段式挖掘方式　………………………………………81
第六章　結論與未來研究
　　6-1　結論　……………………………………………………84
　　6-2　未來研究　………………………………………………85

1.李效屏，「適用於靜態與動態資料庫的支持度導向關聯規則探勘方法之研究」，逢甲大學資訊工程學系，碩士論文，2001
2.楊文昇，「有效率的挖掘關聯規則之高頻物項集合演算法」，逢甲大學資訊工程學系，碩士論文，2001
3.賴志東，「資料挖礦中挖掘含有未知數值屬性之多屬性資料之研究」，國立中央大學資訊管理學系，碩士論文，2001
4.林琪淵，「在POS資料倉儲中挖掘關聯規則」，國立中央大學資訊管理學系，碩士論文，2000
5.淩俊青，「在包裹資料中挖掘數量關聯規則」，國立中央大學資訊管理學系，碩士論文，1999
6.陳家仁，「在限定項目個數與交易長度的資料庫中挖掘關聯規則」，國立中央大學資訊管理學系，碩士論文，2001
7.謝佳蓉，「市場資料中最佳關聯規則之探勘」，長榮管理學院經營管理研究所，碩士論文，2000
8.劉家燕，「交易間關聯規則的探勘與資料探勘問題的分類研究」，國立清華大學資訊工程學系，碩士論文，1999
9.詹光台，「一個以動態門檻值為基礎的多維關聯規則探勘方法之研究」，東吳大學商學院企業管理學系，碩士論文，2000
10.曾明正，「具多重支持度門檻的廣義關聯規則之採掘與維護」，義守大學資訊工程學系，碩士論文，2001
11.郭泯旬，「關聯規則最小支持度之研究--以零售業為例」，元智大學工業工程與管理學系，碩士論文，2000
12.陳仕昇，「以可重複序列挖掘網路瀏覽規則之研究」，國立中央大學資訊管理學系，碩士論文，1998
13.陳振東、戴偉勝，「網際網路環境中個人化資訊推薦系統實作之研究」，中華民國資訊管理學報，第九卷，第一期，第22-39頁
14.Agrawal, R. and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. 20th International Conference on Very Large Databases, pp. 487-499, 1994.
15.Chen, A.L.P. and S.J. Yen, “A graph-based approach for discovering various types of association rules,” IEEE Transactions on Knowledge and Data Engineering, Volume: 13, Issue: 5, Sept.-Oct., 2001, Page(s): 839 —845.
16.Cohen, E. et al., “Finding interesting associations without support pruning,” IEEE Transactions on Knowledge and Data Engineering, Volume: 13, Issue: 1, Jan.-Feb., 2001, Page(s): 64 —78.
17.Goulbourne, G; F. Coenen and P. Leng, “Algorithms for computing association rules using a partial-support tree,” Knowledge-Based Systems Volume: 13, Issue: 2-3, April, 2000, Page(s): 141-149.
18.Getta, J.R. and N. Denwattana, “A parameterised algorithm for mining association rules,” Database Conference, 2001., ADC 2001. Proceedings., 12th Australasian, 2001, Page(s): 45 —51.
19.Hong, T.P.; C.S. Kuo and S.C. Chi, “Mining association rules from quantitative data,” Intelligent Data Analysis Volume: 3, Issue: 5, November. 1999, Page(s): 363-376.
20.Holt, J.D. and S.M. Chung, “Mining association rules using inverted hashing and pruning,” Information Processing Letters Volume: 83, Issue: 4, August 31, 2002, Page(s): 211-220.
21.Kwong, W.W. et al., “Mining association rules with weighted items,” Database Engineering and Applications Symposium, 1998. Proceedings. IDEAS''98. International, Page(s): 68 —77.
22.Rastogi, R. and K. Shim, “Mining optimized support rules for numeric attributes,” Data Engineering, 1999. Proceedings., 15th International Conference on, Page(s): 206 —215.
23.Tseng, M.C.; W.Y. Lin and B.C. Chien, “Maintenance of generalized association rules with multiple minimum supports,” IFSA World Congress and 20th NAFIPS International Conference, 2001. Joint 9th, Volume: 3, Page(s): 1294 -1299 vol.3.
24.Taha, Y.; H.H. Aly and A.A. Amr, “Fast mining of association rules in large-scale problems,” Computers and Communications, 2001. Proceedings. Sixth IEEE Symposium on, 2001, Page(s): 107 —113.
25.NCR - Transforming Transactions into Relationships: http://www.ncr.com/ repository /case_studies/store_automation/sa_walmart7875scanner.htm
26.Savasere, A.; E. Omiecinski and S. Navathe, “An efficient algorithm for mining association rules in large database,” VLDB Cnference,1995. 21st.
27.Salton, G.., “Another Look At Automatic Text-Retrieval Systems,” Communications of the ACM (29:7), 1986, Page(s): 648-656.
28.Salton, G. and C. Buckley, “Parallel Text Search Methods,” Communications of the ACM (31:2), 1998, Page(s): 202-215.
29.Yen, S.J. and L.P. Chen, “An Efficient Approach to Discovering Knowledge from Large Databases,” PDIS, 1996, Page(s): 8-18.
30.Wur, S.Y. and Y. Leu, “An effective Boolean algorithm for mining association rules in large databases,” Proceedings of the 6th International Conference on Database Systems for Advanced Applications, 1998, Page(s): 179-186.
31.Song, H.S., “Mining the change of customer behavior in an Internet shopping mall,” Expert Systems with Applications Volume: 21, 2001, Page(s): 157-168.
32.Stein, R.M.; R.N. Bernard, “Data mining the future: Genetic discovery of food trading rules in agent-based financial market simulations,” Computational Intelligence for Financial Engineering (CIFEr), 1998. Proceedings of the IEEE/IAFE/INFORMS 1998 Conference on, 1998, Page(s): 171 -179
33.Niimi, A.; E. Tazaki, “Genetic programming combined with association rule algorithm for decision tree construction,” Knowledge-Based Intelligent Engineering Systems and Allied Technologies, 2000. Proceedings. Fourth International Conference on, Volume: 2, 2000, Page(s): 746 -749 vol.2
34.Wong, M.L.; L. Wai; K.S. Leung; P.S. Ngan; J.C.Y. Cheng, “Discovering knowledge from medical databases using evolutionary algorithms,” IEEE Engineering in Medicine and Biology Magazine , Volume: 19 Issue: 4 , July-Aug. 2000, Page(s): 45 -55
35.Melab, N.; E. Talbi, “A parallel genetic algorithm for rule mining,” Parallel and Distributed Processing Symposium., Proceedings 15th International , 2001, Page(s): 1347 —1352
36.Cattral, R.; F. Oppacher; D. Deugo, “Rule acquisition with a genetic algorithm,” Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, 1999 -129 Vol. 1
37.Yang, L.; D.H. Widyantoro; T. Ioerger; J. Yen, “An Entropy —based adaptive genetic algorithm for learning classification rules,” Evolutionary Computation, 2001. Proceedings of the 2001 Congress on, Volume: 2 , 2001, Page(s): 790 -796 vol. 2
38.Lu, Y.; Q. Yuan, “Research on weather forecast based on neural network,” Intelligent Control and Automation, 2000. Proceedings of the 3rd World Congress on, Volume: 2, 2000, Page(s): 1069-1072 vol.2
39.Knosala, R.; T. Wal, “A production scheduling problem using genetic algorithm,” Journal of Materials Processing Technology, Volume: 109, 2001, Page(s): 90-95