臺灣博碩士論文加值系統

資料探勘是致力於資料分析和理解、揭示資料內部蘊藏知識的技術，經過多年努力，資料探勘發展出許多新概念和方法。特別是近年來，一些基本概念和方法趨於清晰，正朝向更深入的方向發展。從目前現狀來看，關聯規則是資料探勘中成果頗豐且較活躍的研究分支，留給研究者許多可更深入的課題。面對個人真實購物行為的原始資料庫，關聯規則在其中所扮演的角色及閾值設限所可能造成的分析結果仍不明確。因此，鑒於當前資料探勘技術和關聯規則研究的現狀和發展趨勢，本文選擇該課題開展相關研究工作。
本文的研究工作首先介紹資料探勘技術與關聯規則中Apriori演算模型的發展歷史與其相關應用。其次，本文設計出可適用於真實世界中的資料庫模板，針對個人在賣場內的真實購物行為進行詳盡記錄。然後，本文給出廣義關聯規則信賴度閾值設限的構想，在幾乎不對關聯規則信賴度閾值設限的情況下，取得有購買之商品組合的全部關聯規則進行預測正確度分析工作。此外，本文根據頻繁項集所產生的關聯規則信賴度走勢對商品組合購買變化進行深刻探討。結果表明，關聯規則的信賴度應設閾值將隨不同研究對象在不同購物環境下產生明顯差異，且信賴度走勢須配套觀察才可得知真正的商品組合購買結果。
本文在分析資料探勘技術之Apriori演算模型系統的基礎上，導入個人於賣場內的真實購物原始資料。在不對信賴度閾值設限的條件下，進行關聯規則預測正確度分析及信賴度走勢分析兩方面的研究，所得到的結論在可用性方面具有極佳的應用前景。

Data systems nowadays have been widely adopted in businesses. The massive data collected from business transactions have made entrepreneurs realize to use the data for supporting their business decision makings. Knowledge Discovery in Database (KDD) therefore becomes a wave of essential concept to extract useful and valid knowledge from data even though the knowledge is intuitive or previously unknown. The processes and algorithms of data mining aim to find patterns that describe underlying relationships in the data, for example, association rules (Agrawal, 1993) and clustering. Association rule mining looks for frequently occurring patterns in the data and is often used for market basket analysis. The famous result is the diaper-beer rule in the basket based on association rule. Benefits for retailers are better shelf managing, goods supplying, and market promotion.
Customization techniques, to accommodate differences between individuals, enable the dynamic insertion, personalization, or suggestion of contents in any format that is relevant to the individual user, based on the user’s implicit/explicit behavior and preferences. While customers are claimed to be beneficial from data mining, the purpose of this research is to forecast individual customer’s shopping behavior by adopting Apriori algorithm. In addition to suggest how to decide an interestingness index for producing association rules for individual customers, this study also provides various principles to interpret changes on each customer’s shopping goods in her/his shopping basket. Providing a reliable shopping list suggestion for individual customer before her/his entering the store, designing a better customized promotion for individual customer, and attracting customers visiting the store repeatedly would be on the corner for the retailers.

目 錄
中文摘要 ………………………………………...………………………………. I
Abstract …………………………………………………..……………..…….….. II
誌謝 ………………….……………………………...…………………………… III
目錄 ……………………………….…………………...………………………… VI
表目錄 ……………………..…………………………………………………….. VII
圖目錄 …………………………………………………………………………… VIII
第壹章 緒論 ………………………………………………………………..…… 1
第一節 研究背景…...…………………………………………………..…. 1
第二節 研究動機與目的 ……………………………………..………….. 3
第三節 研究內容 …………………………………………………..…….. 4
第貳章 文獻探討 ……………………………………………………………….. 5
第一節 資料探勘…………………………………………..………..…….. 5
第二節 關聯規則 (Association Rules,AR ) …............................................ 11
第三節 Apriori演算法 (Apriori Algorithm) …...………………………… 19
第四節 Apriori演算法的應用…………………………...………...……… 34
第參章 研究方法 ……………………………………………………………….. 38
第一節 資料庫設計 ……………………………………………………… 38
第二節 資料蒐集 ………………………………………………………… 40
第三節 資料分析 ………………………………………………………… 44
第肆章 研究結果 ……………………………………………………………….. 48
第一節 關聯規則的預測正確度分析 …..……………………………..… 48
第二節 關聯規則與其信賴度分析…………………………….................. 68
第伍章 結論與建議 ……………………………………………......…………… 86
第一節 研究結論 ………………………………………………………… 86
第二節 研究貢獻 …………………………..…………………………….. 91
第三節 研究限制與建議 …………………..…………..……………….. 92
參考文獻 ……………………………………………………………...…………. 95

表目錄
表2-1 購物籃資料之收付憑證紀錄形式......................................................... 12
表2-2 購物籃資料之二元變數紀錄形式......................................................... 12
表3-1 四名研究對象的個人背景資料............................................................. 40
表3-2 四名研究對象的個人購物行為............................................................. 42
表3-3 已預處理及品別類型分類的個人全程購物行為................................. 46
表3-4 已預處理及品別類型分類的個人半年購物行為................................. 46
表3-5 已預處理及品別類型分類的個人半年+1購物行為............................. 47
表3-6 四名研究對象的資料庫歷程分群表..................................................... 47
表4-1 利用關聯規則預購研究對象A之購物正確度...................................... 49
表4-2 正確率變化的判斷準則......................................................................... 53
表4-3 利用關聯規則預購研究對象B之購物正確度..................................... 58
表4-4 利用關聯規則預購研究對象C好市多之購物正確度.......................... 61
表4-5 利用關聯規則預購研究對象C於家樂福之購物正確度...................... 62
表4-6 利用關聯規則預購研究對象D之購物正確度...................................... 65
表4-7 信賴度值變化與購物次數相對應的關係............................................. 68
表4-8 商品是否再次購買的判斷準則............................................................. 70
表4-9 研究對象A重點關聯規則及其於不同購物時點的信賴度值.............. 71
表4-10 研究對象A於頻繁購買商品項的購物行為........................................ 73
表4-11 研究對象B經常購買商品的關聯法則及其信賴度............................. 74
表4-12 研究對象B於頻繁購買商品項的購物行為........................................ 75
表4-13 研究對象C於好市多經常購買商品的關聯法則及其信賴度............ 77
表4-14 研究對象C在好市多之頻繁購買商品項的購物行為........................ 78
表4-15 研究對象C於家樂福經常購買商品的關聯法則及其信賴度............ 78
表4-16 研究對象C在家樂福之頻繁購買商品項的購物行為........................ 79
表4-17 研究對象D經常購買商品的關聯法則及其信賴度............................ 81
表4-18 研究對象D於頻繁購買商品項的購物行為........................................ 82

圖目錄
圖2-1 項集點格結構圖..................................................................................... 19
圖2-2 事務集合產生候選項集圖..................................................................... 20
圖2-3 兩項所組成之頻繁項集點格結構圖..................................................... 21
圖2-4 三項所組成之頻繁項集點格結構圖..................................................... 22
圖2-5 非頻繁項集點格結構剪枝圖................................................................. 23
圖2-6 Apriori演算法產生部分頻繁項集圖................................................... 24
圖2-7 Apriori演算法產生頻繁項集之偽代碼............................................... 26
圖2-8 候選關聯規則點格結構剪枝圖............................................................. 30
圖2-9 約束條件分類圖..................................................................................... 33
圖4-1 利用關聯規則預測研究對象A之購物正確度...................................... 51
圖4-2 利用關聯規則預測研究對象B之購物正確度...................................... 60
圖4-3 利用關聯規則預測研究對象C於好市多之購物正確度...................... 62
圖4-4 利用關聯規則預測研究對象C於家樂福之購物正確度...................... 64
圖4-5 利用關聯規則預測研究對象D之購物正確度...................................... 66

參 考 文 獻
1. Anthony, K.H.T., et al., 2001, “Constraint-Based Clustering in Large Databases”, ICDT ‘01 Proceedings of the 8th International Conference on Database Theory, vol.1973, pp.405-419, London.
2. Baoqing, Jiang, Chong, Han, & Ling-Sheng Li, 2009, “Mining opened frequent itemsets to generate maximal Boolean association rules”, IEEE International Conference on Granular Computing, pp.274-277, Nanchang.
3. Chin-Chen, Chang, Yu-Chiang, Li, & Jung-San, Lee, 2005, “ An Efficient Algorithm for Incremental Mining of Association Rules”, RIDE ‘05 Proceedings of the 15th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications, pp.3-10, Washington DC.
4. Clifford, Lynch, 2008, “Big data: How do your data grow?”, Nature, vol.455, pp. 28-29, September.
5. Dongwon, Lee, Sung-Hyuk, Park, & Songchun, Moon, 2011, “High-Utility Rule Mining for Cross-Selling”, HICSS ‘11 Proceedings of the 2011 44th Hawaii International Conference on System Sciences, pp.1-10, Washington DC.
6. Doug, H., et al., 2008, “Big data: The future of biocuration”, Nature, vol.455, pp. 47-50, September.
7. Gilbert, T.L., 1955, “A Lagrangian Formulation of The Gyromagnetic Equation of The Magnetic Field”, Phys., Rev., vol.100, pp.1243.
8. Gregory, Piatetsky-Shapiro, 1991, “Discovery, Analysis, and Presentation of Strong Rules”, Knowledge Discovery in Databases, pp.229-248.
9. Gregory, Piateski, & William, Frawley, 1991, Knowledge Discovery in Databases, MIT Press, Cambridge.
10. Hand, D., Mannila, H., & Smyth, P., 2001, Principles of Data Mining, MIT Press, Cambridge.
11. Hui, S. C., & Jha, G.., 2000, “Data mining for customer service support”, Information & Management, vol.38, pp.1-13, October.
12. Jia-Wei, Han, & Yong-Jian, Fu, 1995, “Discovery of Multiple-Level Association Rules from Large Databases”, VLDB ‘95 Proceedings of the 21th International Conference on Very Large Data Bases, pp.420-431, San Francisco.
13. Jia-Wei, Han, & Kamber, M., 2001, Data Mining: Concepts and Techniques, Third Edition, Morgan-Kaufmann Academic Press, San Francisco.
14. Jian, Pei, & Jia-Wei, Han, 2000, “Can We Push More Constraints into Frequent Pattern Mining?”, KDD ‘00 Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining, pp.350-354, Boston.
15. Jian, Pei, Jia-Wei, Han, & Laks, V.S.L., 2001, “Mining frequent itemsets with convertible constraints”, ICDE ‘01 Proceedings of the 17th International Conference on Data Engineering, pp.433-442, Washington DC.
16. Jian, Pei, et al., 2001, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth”, ICDE ‘01 Proceedings of the 17th International Conference on Data Engineering, pp.215-224, Washington DC.
17. Jong, S.P., Ming-Syan, Chen, & Philip, S.Y., 1995, “An effective hash-based algorithm for mining association rules”, SIGMOD ‘95 Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, vol.24, pp.175-186, New York.
18. Jong, S.P., Ming-Syan, Chen, & Philip, S.Y., 1998, “Efficient Data Mining for Path Traversal Patterns”, IEEE Transactions on Knowledge and Data Engineering, vol.10, pp.209-220, March.
19. Kadel, P., & Ho-Jin, Choi, 2006, “Incremental algorithm for Distributed Data Mining”, CIT ‘06 Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, pp.72, Washington DC.
20. Ke, Wang, Yu, He, & Jia-Wei, Han, 2000, “Mining Frequent Itemsets Using Support Constraints”, VLDB ‘00 Proceedings of the 26th International Conference on Very Large Data Bases, pp.43-52, Cairo.
21. Khare, Neelu, Adlakha, Neeru, & Pardasani, K.R., 2010, “An Algorithm for Mining Multidimensional Association Rules Using Boolean Matrix”, ITC ‘10 Proceedings of the 2010 International Conference on Recent Trends in Information: Telecommunication and Computing, pp.95-99, Washington DC.
22. Landau, L.D., & Lifshitz, E.M., 1935, “Theory of The Dispersion of Magnetic Permeability in Ferromagnetic Bodies”, Phys., Z., Sowietunion, vol.8, pp.153-169.
23. Liqiang, Geng, & Howard, J.H., 2006, “Interestingness Measures for Data Mining: A Survey”, Computing Machinery, vol.38, pp.9-40, September.
24. Mary, M.W., & S.Prasad, Kantamneni, 2002, “POS and EDI in Retailing: An Examination of Underlying Benefits and Barriers”, Supply Chain Management: An International Journal, vol.7, pp.311-317.
25. Ming-Syan, Chen, Jong, S.P., & Philip, S.Y., 1996, “Data Mining for Path Traversal Patterns in A Web Environment”, ICDCS ‘96 Proceedings of the 16th International Conference on Distributed Computing Systems, pp.385-392, Washington DC.
26. Rakesh, Agrawal, & Ramakrishnan, Srikant, 1994, “Fast Algorithms for Mining Association Rules in Large Databases”, VLDB ‘94 Proceedings of the 20th International Conference on Very Large Data Bases, pp.487-499, San Francisco.
27. Rakesh, Agrawal, Tomasz, Imieliński, & Arun, Swami, 1993, “Mining association rules between sets of items in large databases”, SIGMOD ‘93 Proceedings of the 1993 ACM SIGMOD international conference on Management of data, vol.22, pp.207-216, New York.
28. Ramakrishnan, Srikant, & Rakesh, Agrawal, 1996, “Mining quantitative association rules in large relational tables”, SIGMOD ‘96 Proceedings of the 1996 ACM SIGMOD international conference on Management of data, vol.25, pp.1-12, New York.
29. Richard, Roiger, & Michael, Geatz, 2002, Data Mining: A Tutorial Based Primer, Addison-Wesley, Boston.
30. Shi-Jie, Chang, Peng-Rui, Shao, & Peng, Li, 2007, “Basic Problems and Development on Dynamics of Magnetization Reversal Process of Nano-Material”, Equipment Manufacturing Technology, vol.5, pp.18-20.
31. Sotiris, Kotsiantis, & Dimitris, Kanellopoulos, 2006, “Association Rules Mining: A Recent Overview”, GESTS International Transactions on Computer Science and Engineering, vol.32, pp.71-82.
32. Stoner, E.C., & Wohlfarth, E.P., 1948, “A Mechanism of Magnetic Hysteresis in Heterogeneous Alloys”, Philosophical Transactions of the Royal Society A, vol.240, pp.599-642.
33. Tang, Hewen, et al., 2008, “Using Data Mining to Accelerate Cross-Selling”, ISBIM ‘08 Proceedings of the 2008 International Seminar on Business and Information Management, vol.1, pp.283-286, Washington DC.
34. Theresia, W.A., & Beta, Noranita, 2012, “Apriori Application To Pattern Profile Creditor Relationships With Credit Ceiling In Rural Bank”, ICISBC ‘11 Proceedings of the 1st International Conference on Information Systems for Business Competitiveness, pp.75-80, Semarang.
35. Tom, Brijs, et al., 1999, “Using association rules for product assortment decisions: a case study”, KDD ‘99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, pp.254-260, New York.
36. Toon, Calders, & Jef, Wijsen, 2001, “On Monotone Data Mining Languages”, DBPL ''01 Revised Papers from the 8th International Workshop on Database Programming Languages, pp.119-132, London.
37. Usama, M. F., et al., 1996, Advances in Knowledge Discovery and Data Mining, American Association for Artificial Intelligence Menlo Park, California.
38. Wan-Zhong, Yang, et al., 2006, “Rough Set Model for Constraint-based Multi-dimensional Association Rule Mining”, Proceedings of the 2006 Conference on Advances in Intelligent IT: Active Media Technology 2006, pp.99-105, Amsterdam.
39. Wen-Juan, Li, & Shi-Min Wang, 2013, “Research on Assessment Method for Credit Risk in Commercial Banks of China Based on Data Mining”, Applied Mechanics and Materials, vol.303-306, pp.1361-1364, February.
40. Wenke, Lee, & Salvatore, J.S., 1998, “Data mining approaches for intrusion detection”, USENIXSS ‘98 Proceedings of the 7th Conference on USENIX Security Symposium, vol.7, pp.6, San Antonio.
41. Wenke, Lee, Salvatore, J.S., & Kui, W.M., 2002, “Algorithms for Mining System Audit Data”, Data Mining, Rough Sets and Granular Computing, vol.1, pp.166-189.
42. William, Frawley, Gregory, Piateski, & Matheus, C., 1992, “Knowledge Discovery in Databases: An Overview”, AI Magazine, vol.13, pp.57-70.
43. Xiu-Li, Yao, & Hua-Ying, Shu, 2009, “Study on Value-Added Service in Mobile Telecom Based on Association Rules”, SNPD ‘09 Proceedings of the 10th International Conference on Software Engineering: Artificial Intelligences, Networking and Parallel/Distributed Computing, pp.116-119, Daegu.
44. Xu, Liang, Cai-Xia, Xue, & Ming, Huang, 2010, “Improved Apriori Algorithm for Mining Association Rules of Many Diseases”, Communications in Computer and Information Science, vol.107, pp.272-279, January.