臺灣博碩士論文加值系統

由於資訊科技的進步日新月異，且要在龐大的資料中整理並擷取出有意義的資訊，是一個很重要的課題，而近年來資料探勘技術已成功的應用在不同領域，因為資料探勘能將各種龐大的資料中的隱藏事實與資訊探勘出來，並在這些資料中歸納出有結構的模式，其中關聯法則為使用最廣泛且最實用的一種模式，主要用於找尋資料中屬性之間的關係，而最典型是應用於購物籃分析上。
在過去的文獻中，發現在關聯法則演算法上的改良研究，大多都是以提高搜尋效率為目的，也有些研究是針對關聯法則設定的最小支持度與最小信心度門檻值，因為客觀的設定最小門檻值得到的關聯規則是相當重要的。因此本研究將提出改善關聯法則整體效率與客觀設定門檻值的新演算法，其先透過二元資料型態轉換，再應用啟發式方法-粒子群最佳化演算法，搜尋最佳粒子之適應値，作為最小門檻值設定之建議；且利用Microsoft SQL Server 2000之內建資料庫做為此方法的模式驗證，並與基因演算法比較其探勘效率，其結果可得知，藉由粒子群最佳化演化應用確實能快速且客觀的提供最適的最小門檻值設定建議，來提升探勘關聯法則的品質與效率；另外也應用在實際證卷公司資料分析上，可以藉由本研究提出的關聯法則，探勘出投資者之行為對於購買股票之類股間的關聯性。

With the development of information technology (IT), how to find useful information existed in vast data has become an important issue. The most broadly discussed technique is Data-mining, which has been successfully applied to many fields as analytic tool. Data mining extracts implicit, previously unknown, and potentially useful information from data. Association rule is one of the most important and useful technologies in data mining methods. Association rule summarizes meaningful relations among items, and this technology is typically applied to basket analysis in supermarkets.
Most of previous researches focus on improving computational efficiency. However, there are also some other researches which emphasize on how to decide the threshold values of support and confidence parameters. The reason is that deciding suitable threshold values is critical to the quality of association rule mining. In this study, we propose a new algorithm for association rule mining in order to improve the whole efficiency and determine suitable threshold values. At first, transaction data are transformed into binary formats and then we apply Particle Swarm Optimization (PSO) algorithm to search the optimum fitness value of particle and find its corresponding support and confidence as minimum threshold. The proposed method is verified by applying FoodMart2000 database of Microsoft SQL Server 2000 and compared with genetic algorithm in efficiency. According to the results, it is found that particle swarm optimization algorithms can really suggest suitable threshold values and obtain the quality rules. We also apply real-world stock market database in order to mine association rule among investment behavior and stock category purchasing. The computational result is also very promising.

目錄
摘要..................................................i
ABSTRACT.............................................ii
誌謝.................................................iv
目錄..................................................v
表目錄..............................................vii
圖目錄.............................................viii
第一章 緒論...........................................1
1.1 研究背景與動機....................................1
1.2 研究目的..........................................2
1.3 研究範圍..........................................2
1.4 論文架構..........................................3
第二章 文獻探討......................................5
2.1 資料探勘(Data Mining).............................5
2.1.1 資料探勘之定義..................................5
表 2.1 資料探勘之定義.................................6
2.1.2 資料探勘之主要功能及模型........................7
2.2 關聯法則(Association rule)........................9
2.2.1 關聯法則之定義..................................9
2.2.2關聯法則演算法..................................10
2.2.3 關聯法則之相關應用.............................18
2.3 粒子群最佳化(Particle Swarm Optimization)........19
2.3.1 粒子群最佳化之發展背景.........................19
2.3.2 粒子群最佳化演算法.............................20
2.3.3 粒子群最佳化之相關應用.........................22
第三章 研究方法.....................................25
3.1 研究架構流程.....................................25
3.2 執行PSO關聯法則探勘之前處理......................26
3.2.1 二元資料型態轉換...............................26
3.2.2 計算IR值.......................................27
3.3 以PSO為模組之關聯探勘............................28
第四章 模式驗證與結果分析...........................33
4.1 實驗平台與資料庫.................................33
4.2 以粒子群最佳化關聯法則探勘之結果.................34
4.3 效能評估分析.....................................39
4.3.1 比較PSO與GA整體系統探勘關聯法則之效能..........39
4.3.2 針對PSO搜尋部份之效能評估......................40
第五章 實例應用與結果分析...........................43
5.1 應用案例說明.....................................43
5.2 第一階段執行PSO關聯法則探勘結果與分析............44
5.3 第二階段執行PSO關聯法則探勘結果與分析............46
5.4 結果分析.........................................49
第六章 結論與建議...................................51
6.1 結論.............................................51
6.2 未來研究與建議...................................51
參考文獻.............................................53
附錄 A FoodMart2000之三維度實驗結果.................57


表目錄
表2.1 資料探勘之定義................................. 6
表2.2 Apriori變化形式之演算法彙整表..................16
表2.3 粒子群最佳化之應用領域及研究內容...............24
表4.1 商品類別對照代號表 ............................34
表4.2 FoodMart2000資料庫二維度執行PSO關聯法則之結果..38
表4.3 PSO與GA比較表..................................40
表5.1 產業分類表.....................................44
表5.2 以產業分類之案例資料執行PSO關聯法則之結果......45
表5.3 股價分類表 ....................................46
表5.4 產業_股價分類表................................46
表5.5 以產業_股價分類之案例資料執行PSO關聯法則之結果.47
表5.6 產業_MSCI分類表................................48
表5.7 以產業_MSCI分類之案例資料執行PSO關聯法則之結果.49


圖目錄
圖1.1 論文架構流程圖 ...................................4
圖2.1 關聯法則探勘頻繁項目集合之Apriori演算法..........11
圖2.2 粒子群最佳化演算法步驟之虛擬碼...................21
圖3.1 系統流程架構圖...................................26
圖3.2 資料型態轉換圖...................................27
圖3.3 染色體編碼關係圖.................................29
圖3.4 染色體編碼之關聯法則型式.........................29
圖3.5 計算支持度之資料庫搜尋方式.......................30
圖3.6 調整粒子更新後位置概念圖.........................32
圖4.1 FoodMart2000資料庫中包含之資料表.................33
圖4.2 轉換二元型態資料之顯示畫面.......................35
圖4.3 交易包含之商品類別數量示意圖.....................35
圖4.4 計算IR值結果之顯示畫面...........................36
圖4.5 FoodMart2000資料庫二維度執行PSO關聯法則結果之顯示畫面......................................................37
圖4.6 最小支持度門檻值設定下之探勘高頻項目集合數量圖...39
圖4.7 FoodMart2000資料庫之母體粒子數對執行時間關係圖...39
圖4.8 演化世代數對執行時間關係圖.......................40
圖4.9 FoodMart2000資料庫之母體粒子數對執行時間關係圖...41
圖4.10 演化世代數對執行時間關係圖.......................41
圖5.1 投資者之證卷交易紀錄.............................43

參考文獻
[1]G.H.Grupe and M.M. Owrang, “Database Mining Discovering New Knowledge and Cooperative Advantage,” Information System Management, Vol 12,No. 4, 1995, pp.26-31.
[2]U. Fayyad, G. Piatetsky-shapiro and P. Smyth, “From data mining to knowledge discovery in databases,” AI Magazine, 1996, pp.37-54.
[3]M.J.A. Berry and G.S. Linoff, Data Mining Technique： For Marketing, Sales, and Customer Relationship Management, New York：Wiley Computer Publishing, 1997.
[4]P. Cabena, P. Hadjnian, R. Stadler, J. Verhees and A. Zanasi, Discovering Data Mining from Concept to Implementation, New Jersey：Pretice Hall, 1997.
[5]U. Fayyad, G. Piatetsky-shapiro and P. Smyth, “From data mining to knowledge discovery in databases,” AI Magazine, pp.37-54, 1996.
[6]M. J. Shaw, C. Subramaniam, G.W. Tan and M.E. Welge, “Knowledge management and data mining for marketing,” Decision Support Systems, Vol. 31, pp.127-137, 2001.
[7]周憲慶，應用資料採礦技術建構銀行風險管理模型之實證研究，碩士論文，國立台北科技大學商業自動化與管理研究所，碩士論文，台北，2004。
[8]Uinminer Data Mining 資料採礦介紹<http://www.uniminer.com/center01.htm>
[9]J. Han and M. Kamber, Data Mining: Concepts and Techniques, New York: Morgan Kaufmann, 2000.
[10]A. Savasere, E. Omiecinski and S. Navathe, “An efficient algorithm for mining association rules in large database,”Proceedings of the 21st VLDB Conference, 1995, pp.432-444.
[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,1995, pp.175-186.
[12]H. Toivonen, “Sampling large databases for association rules,” Proceedings of the 22nd VLDB Conference, 1996, pp.134-145.
[13]S. Birn, R. Motwani, J. D. Ullman and S. Tsur, “Dynamic itemset counting and implication rules for market basket data,” Proceedings of the ACM SIGMOD,1997, pp.255-264.
[14]D.I. Lin and Z.M. Kedem, “Pincer Search : A New Algorithm for Discovering the Maximum Frequent Set,” Proceeding of the 6th International Conference on Extending Database Technology: Advances in Database Technology, 1998, pp.105-119.
[15]B. Liu, W. Hsu and Y. Ma, “Mining Association Rules with Multiple Minimum Supports,” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, San Diego CA USA, 1999, pp.337-341.
[16]D.L. Yang, C.T. Pan, Y.C. Chung, “An Efficient Hash-Based Method for Discovering the Maximal Frequent Set” Proceeding of the 25th Annual International Conference on Computer Software and Applications, 2001, pp.551-516.
[17]范正坤，關聯法則與統計分析之探討，碩士論文，國立中央大學，桃園，2002。
[18]鄧安生，新式探勘方法在關聯法則門檻值制定之研究，碩士論文，大葉大學資訊管理學系，彰化，2003。
[19]龔書賢，應用基因演算法及權重項目法於關聯法則挖掘之研究，碩士論文，元智大學工業工程與管理學系，桃園，2002。
[20]羅閔隆，以經驗法則應用在關聯法則門檻值制定之研究，碩士論文，大葉大學資訊管理學系，彰化，2004。
[21]M. Saggar, A.K. Agrawal and A. Lad, “Optimization of Association Rule Mining using Improved Genetic Algorithms”, Proceeding of the IEEE International Conference on Systems Man and Cybernetics, Vol.4, 2004, pp.3725-3729.
[22]C. Li and M. Yang, “Association Rule Data Mining in Manufacturing Information System based on Genetic Algorithms,” Proceeding of the 3rd International Conference on Computational Electromagnetics and Its Applications, 2004, pp.153-156.
[23]施智文，應用螞蟻集群系統於多維限制條件下之資料探勘，碩士論文，國立台北科技大學工業工程與管理系碩士班，台北，2004。
[24]林思宇，整合集群分析與螞蟻理論於關聯法則之探勘，碩士論文，國立台北科技大學工業工程與管理系碩士班，台北，2005。
[25]NCR-Transforming Transactions into Relationships: <http://www.ncr.com/repository/case_studies/store_automation/sa_walmart7875scanner.htm>
[26]李秀梅，信用卡持卡者資料探勘之研究，碩士論文，輔仁大學應用統計學研究所，台北，2000。
[27]陳仕昇，以可重複序列挖掘網路瀏覽規則之研究，碩士論文，國立中央大學資訊管理學系，桃園，1998。
[28]李姿儀，醫院門診資料探勘—以虎尾若瑟醫院為例，碩士論文，南華大學資訊管理學系碩士班，嘉義，2000。
[29]Y. Lu and Q. Yuan, “Research on weather forecast based on neural network,” Proceedings of the 3rd world Congress on Intelligent Control and Automation, Vol. 2, 2000, pp.1069-1072.
[30]徐家馴，在教學網站的環境中發掘熱門學習路線，碩士論文，輔仁大學資訊工程學系，台北，2000。
[31]R.C. Eberhart and J. Kennedy, “Particle swarm optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, 1995, pp.1942-1948.
[32]Particle Swarm Optimization：Tutorial <http://www.swarmintelligence.org/tutorials.php>
[33]M.P. Song and G.C. Gu, “Research on particle swarm optimization: a review,” Proceedings of the IEEE International Conference on Machine Learning and Cybernetics, 2004, pp.2236-2241.
[34]R.C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” Proceedings of the 6th International Symposium on Micro Machine and Human Science, Nagoya Japan, 1995, pp.39-43.
[35]Y. Shi and R.C. Eberhart, “A modified particle swarm optimizer,” Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, 1998b, pp.69-73.
[36]M. Clerc, “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proceedings of the Congress of Evolutionary Computation, Washington, 1995, pp.1951-1957.
[37]R.C. Eberhart, and Y. Shi, “Particle swarm optimization: Developments, applications and resources,” Proceedings of the IEEE Congress on Evolutionary Computation, 2001, pp.81-86.
[38]C.Y. Chen and F. Ye, “Particle swarm optimization algorithm and its application to clustering analysis,” Proceedings of the IEEE International Conference on Networking, Sensing and Control, Taipei Taiwan, 2004, pp.21-23.
[39]葉思緯，應用粒子群最佳化演算法於多目標存貨分類之研究，碩士論文，元智大學工業工程與管理學系，桃園，2004。
[40]T. Sousa, A. Neves and A. Silva, “Swarm optimisation as a new tool for data mining,” Proceedings of the International Parallel and Distributed Processing Symposium, 2003.
[41]曾俊傑，一個智慧型指紋辨識系統的設計方法論，碩士論文，義守大學電機工程學系，高雄，2000。
[42]K.P. Wang, L. Huang, C.G. Zhou and W. Pang, “Particle swarm optimization for traveling salesman problem,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, 2003, pp.1583-1585.
[43]葉麗雯，供應商產能有限及價格折扣下多產品多供應商最佳化採購決策，碩士論文，元智大學工業工程與管理學系，桃園，2002。
[44]S.Y. Wur 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, pp.179-186.