臺灣博碩士論文加值系統

由於智慧型科技產品的普及與行動支付的興起，越來越多消費者利用手機、平板、智慧型手錶等行動裝置來進行付款，所以了解在行動商務環境下的消費者行為，現今已成為資料探勘的一大熱題。已有學者提出研究，希望能找出行動商務環境中的消費者行為，然而就我們所知，目前應用在行動商務的演算法並沒有考慮到消費者的非連續的共同路徑，因此探勘出的樣式會忽略一些資訊。除此之外，在探討商品與商品之間的關聯性時，只考慮了商品被購買的頻率，但每樣商品都有不同的價格與利潤，傳統的頻繁樣式探勘可能找出高頻繁但低利潤的商品或是忽略了低頻率但高利潤的商品。
因此，本論文提出行動商務中高效益頻繁購買行為樣式之探勘（High Utility Frequent Purchase Behavior Mining，HUFPBM），同時考量非連續的共同移動路徑、商品項目集與商品購買順序三個面向，以及商品的頻率與效益（Utility）兩個因素。HUFPBM使用SID-list (Sequential ID-list)資料結構和樣式成長的概念，找出所有的行為樣式，首先找出頻繁非連續的共同移動路徑樣式，再找出其投影交易下能同時滿足頻率門檻與效益門檻的商品樣式。本論文所找出的行為樣式允許重複的路徑出現在樣式中，且不僅探討商品被購買的頻率，還有商品被購買的數量以及利潤，完整的找出消費者移動路徑且真正能為店家帶來效益的行為樣式。

Due to the rapid expansion of technology and electronic payment, people now pay with their mobile devices such as cell phones, pads, or smart watches, etc. Thus understanding the behaviors of customers becomes an important research issue in data mining. Previous researches have proposed many algorithms that considered both moving and purchase patterns. However, they did not take moving patterns into account. Therefore, it may lose some information about the mined patterns. In addition, it only considers the frequency of items, but each item has different price and profit. The problems for traditional frequent itemset mining are that finding the patterns may have high frequencies but low profits for business or may miss the patterns which have low purchase frequencies but high profits.
In this paper, we propose HUFPBM (High Utility Frequent Purchase Behavior Mining), which take non-consecutive moving path, items and purchasing order three factors into account. It also considers the frequency and utility of items in order to discover all high utility frequent purchase behavior. HUFPBM utilizes SID-list (sequential ID list) data structures and the concept of pattern growth to find the frequent moving patterns first. Then it finds all purchase patterns which satisfy the user-specified minimum support and user-specified minimum utility for the moving patterns. The behavior patterns we discovered include the information of forward and backward path. In addition, we take not only frequent pattern mining but also high utility pattern mining into consideration. The proposed method can discover complete moving patterns of customers as well as explore important and high profit behavior patterns in order to bring high profits to business.

論文摘要 I
ABSTRACT II
圖索引 V
表索引 VII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 3
第二章 文獻探討 4
2.1 關聯規則探勘（Association Rules Mining） 4
2.1.1 Apriori演算法 5
2.1.2 FP-Growth演算法 6
2.2 序列樣式探勘(Sequential Pattern Mining) 7
2.2.1 SPADE（Sequential Pattern Discovery using Equivalence Classes） 7
2.2.2 PrefixSpan（Prefix-projected Sequential Pattern Mining） 8
2.3 瀏覽路徑樣式探勘（Path Traversal Pattern Mining） 9
2.3.1 正向瀏覽序列（Forward Traversal Pattern） 9
2.3.2 非簡單瀏覽序列（Non-Simple Traversal Pattern） 10
2.4 行動樣式探勘（Mobile Pattern Mining） 11
2.4.1 行動序列樣式（Mobile Sequential Pattern） 11
2.5 高效益探勘（High Utility Mining） 14
第三章 研究方法 17
3.1 問題定義 17
3.2 HUFPBM演算法基本概念與流程 20
3.3 資料庫轉換 22
3.3.1 SID-List (Sequential ID-List) 資料結構 23
3.3.2 SID Join 24
3.4 HUFPBM演算法 29
3.4.1. WUFPB-Tree 29
3.4.2. 路徑樣式成長 31
3.4.3. 路徑下購買行為樣式成長 33
第四章 實驗設計與分析 41
4.1 實驗資料集摸擬方法 41
4.2 實驗結果 44
第五章 結論與未來展望 52
參考文獻 53

[1]T. S. Chen, Y. S. Chou and T. C. Chen, “Mining User Movement Behavior Patterns in a Mobile Service Environment.” IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 42, pp.87-101, 2012.
[2]T. M. T. Do and D. Gatica-Pereza, “Where and what: Using smartphones to predict next locations and applications in daily life.” Pervasive and Mobile Computing, Vol. 12, pp. 79-91, 2014.
[3]S. J. Evangeline1, K. M. Subramanianl, and K. Venkatachalam, “Efficiently Mining the Frequent Patterns in Mobile Commerce Environment.” International Journal of Innovation and Scientific Research, Vol. 5, No. 1, pp. 30-39, 2014.
[4]P. Fournier-Viger, C. W. Wu, S. Zida, and V. S. Tseng, “FHM: faster high-utility itemset mining using estimated utility co-occurrence pruning.” Lecture Notes in Computer Science, Vol. 8502, pp. 83-92, 2014.
[5]J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation.” Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 1-12, 2000.
[6]G. C. Lana, T. P. Hongb, and V. S. Tseng, “Applying the maximum utility measure in high utility sequential pattern mining.” Expert Systems with Applications, Vol. 41, No. 11, pp. 5071-5081, 2014.
[7]K. C. Lu, C. W. Hsu, and D. L. Yang, “A Novel Approach for Efficient and Effective Mining of Mobile User Behaviors.” Proceedings of the 4th International Conference on Multimedia and Ubiquitous Engineering, pp. 1-6, 2010.
[8]Y. Liu, W. K. Liao, and A. Choudhary, “A fast high utility itemsets mining algorithm.” Proceedings of the 1st international workshop on Utility-based data mining, pp. 90-99, 2005.
[9]K. C. Lin, I-En Liao, and Z. S. Chen, “An improved frequent pattern growth method for mining association rules.” Expert Systems with Applications, Vol. 38, No. 5, pp. 5154–5161, 2011.
[10]H. C. Lu, W. C. Lee, and V. S. Tseng, “A framework for personal mobile commerce pattern mining and prediction.” Knowledge and Data Engineering, Vol. 24, No. 5, pp. 769-782, 2012.

[11]M. Liu and J. Qu, “Mining high utility itemsets without candidate generation.” Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 55-64, 2012.
[12]Y. S. Lee, S. J. Yen and C. H. Wang, “Mining browsing and purchasing behaviors of web users.” Proceedings of IEEE International Conference on Machine Learning and Cybernetics, Vol. 5, pp. 2647-2652, 2010.
[13]C. H. Mooney and J. F. Roddick, “Sequential pattern mining--approaches and algorithms.” ACM Computing Surveys (CSUR), Vol. 45, No. 2, pp. 1-39, 2013.
[14]S. Nagalakshmi and R. Sumathi, “An efficient mobile commerce explorer for mobile user's behavior pattern mining and prediction.” Proceeding of the 2014 International Conference on Information Communication and Embedded Systems, pp. 1-7, 2014.
[15]J. Pei, J. Han, and B. Mortazavi-Asl, “Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth.” Proceedings of the 17th International Conference on Data Engineering, pp. 215–224, 2001.
[16]B. E. Shie, H. F. Hsiao, and V. S. Tseng, “Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments.” Knowledge and Information Systems, Vol.37, No.2, pp. 363-387, 2013.
[17]B. E. Shie, P. S. Yu, V. S. Tseng, “Mining interesting user behavior patterns in mobile commerce environments.” Applied Intelligence, Vol.38, No.3, pp. 418-435, 2013.
[18]V. S. Tseng and K. W. Lin, “Efficient mining and prediction of user behavior patterns in mobile web systems.” Information and software technology, Vol. 48, No. 6, pp. 357–369, 2006.
[19]V. S. Tseng, B. E. Shie, C. W. Wu, and P. S. Yu, “Efficient algorithms for mining high utility itemsets from transactional databases.” IEEE Transactions on Knowledge and Data Engineering, Vol. 25, No. 8, pp. 1772-1786, 2013.
[20]L. Vu and G. Alaghband, “A fast algorithm combining fp-tree and tid-list for frequent pattern mining.” Proceedings of IEEE Conference on Information and Knowledge Engineering, pp. 472-477, 2011.
[21]J. Z. Wang, J. L. Huang, and Y. C. Chen, “On efficiently mining high utility sequential patterns.” Knowledge and Information Systems, Vol.49, pp. 1-31, 2016.

[22]C. H. Yun and M. S. Chen, “Mining mobile sequential patterns in a mobile commerce environment.” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 37, No. 2, pp. 278-295, 2007.
[23]H. Yao, H. J. Hamilton, and C. J. Butz, “A Foundational Approach to Mining Itemset Utilities from Databases.” Proceedings of the 4th SIAM International Conference on Data Mining, pp. 482-486, 2004.
[24]J. Yan, Y. Qiao, J. Yang, and S. Gao, “Mining Individual Mobile User Behavior on Location and Interests.” Proceeding of IEEE International Conference on Data Mining Workshop, pp. 1262-1269, 2015.
[25]J. Yang, Y. Qiao, X. Zhang, H. He, F. Liu and G. Cheng, “Characterizing User Behavior in Mobile Internet.” IEEE Transactions on Emerging Topics in Computing, Vol. 3, pp.95-106, 2015.
[26]J. Yin, Z. Zheng, and L. Cao, “Uspan: an efficient algorithm for mining high utility sequential patterns.” Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 660-668, 2012.
[27]M. J. Zaki, “SPADE: An efficient algorithm for mining frequent sequences.” Machine Learning, Vol. 42, No. 1, pp. 31-60, 2001.
[28]S. Zida, P. Fournier-Viger, C. W. Wu, J. C. W. Lin, and V. S. Tseng, “Efficient mining of high-utility sequential rules.” Machine Learning and Data Mining in Pattern Recognition, Vol. 9166, pp. 157-171, 2015.
[29]吳彥欽, 張嘉惠, “非簡單瀏覽路徑之探勘與應用” 中央大學資訊工程研究所碩士論文, 2001.