情節探勘（Episode Mining）是資料探勘領域中一門新興且重要的研究議題，其主要目標為，在複雜的事件序列（complex event sequences）中，探勘由事件（events）所組合之情節（episodes）的頻率超過用戶指定的最小支持度門檻值（minimum support threshold）的所有集合，情節探勘已經被廣泛運用在股市波動分析、訊號異常偵測、生理訊號分析等應用中。而效益情節探勘（utility-based episode mining）為其中的一個新興研究議題，與傳統情節探勘問題不同之處在於，不只考慮複雜事件序列中情節之發生頻率，同時還考慮事件本身的效益屬性（例如：權重、價值、利潤等），因此，效益情節探勘技術更適用於醫學、商業等領域的智慧型專家系統之建置。雖然近年已經有一些相關研究被提出，但仍有以下不足之處：(1)使用者通常需要利用情節規則（episode rules），才能輕易地建立預測模型。然而透過兩階段方式（即是先探勘效益情節再轉換成規則）探勘效益情節規則（utility-based episode rules），可能會產生低效益的情節規則，而且執行上也是較沒效率的。(2)另外，使用者可能只想直接獲取前k個最高效益情節，來對資料進行分析。然而，現有方法都必須設定一個合適的最小支持度門檻值，才能獲取前k個最高效益情節，可是對於使用者來說，往往是很困難的。若門檻值設定過高，將產生太少情節；反之，可能產生太多不重要情節並降低執行效率。(3)透過情節（頻繁情節、效益情節）所建構出來的預測模型，也必須針對相關參數（parameters）和子模型（subsets of models）的選擇，進行同步最佳化，否則，訓練出來的模型也可能在預測能力和準確性方面不夠強健。
為了解決上述議題，本論文探討一系列新穎的效益情節探勘問題：(1)高效益情節規則探勘（high utility episode rule mining）；(2)前k個高效益情節探勘（top-k high utility episode mining）；(3)結合高效益情節與基因演算法之最佳化模型建置法（construction of an optimized model using high utility episodes and genetic algorithms）。
本論文的第一個研究主題，率先提出一套名為UBER-Mine演算法與名為UR-Tree為壓縮樹形結構，能夠有效率地找出高效益情節規則。此外，我們也把預測股票波動的挑戰性問題作為一個高效益情節規則之延伸應用，我們先設計一個以頻繁情節為基礎的股票投資模式，來探勘出多事件所組合的情節和股價資料的關聯性，進而預測股價的波動，簡稱SISTEM。接著，再把高效益情節規則應用於股票投資模式，作為一個新的擴展版本名為IV-UBER。實驗結果顯示這個理念除了成功應用於預測股票波動的挑戰性問題外，而且IV-UBER投資效益也優於既存最優的幾種方法。
本論文的第二個研究主題中，我們提出了一個高效率演算法名為TKUE，可以直接從複雜事件序列中有效率地探勘出前k個高效益情節。我們也進一步將該方法用於分析一個城市的天氣和時間對於腳踏車租借率的影響。實驗結果顯示TKUE除了具有良好的可擴展性外，也非常有效率地找出天氣、時間、與腳踏車租借率的關聯性。
本論文的第三個研究主題中，我們提出了一個名為HUEM-GAO的方法，結合高效益情節規則與基因演算法（genetic algorithm）來建構一個最佳化模型，並且應用到預測股票波動上。實驗結果顯示HUEM-GAO在平均回報與準確性皆能優於幾個著名的機器學習方法。
本論文根據應用上之需求及現今方法不足處，提出一系列新穎之效益情節探勘演算法，能有效地提供使用者在建置智慧型專家系統之重要元件。三個研究主題，除了在理論上分析所提方法之優缺點與限制外，並從真實世界的應用情境中，闡述所提方法在實務上之重要性，並透過一系列嚴謹的實驗驗證來說明所提出方法之優越性。本論文在學術理論上，大幅推進效益情節探勘領域所產生的高度影響性；在實際應用中，也能廣泛適用於各種領域之智慧型專家系統的建置上，進而對人類生活產生助益。

Frequent episode mining is a fundamental research topic in data mining, which refers to discovering all episodes that appear in complex event sequences with frequencies no less than a user-specified minimum support threshold. Frequent episode mining has been applied to various kinds of domains such as finance analysis, anomaly detection, and vital sign analysis. One emerging research issue in this field is utility-based episode mining, which differs from frequent episode mining in that it considers not only the basic properties of items (i.e., frequency) but also its utility (e.g., weight, profit, and value). Hence, it is a more effective kind of technique through which deeper insights can be gained. Although some studies have been devoted to the issue of utility-based episode mining, the following deficiencies have been identified from the existing methods: First, simply deriving rules from the set of high utility episodes may not produce useful or meaningful utility-based episode rules for users. In addition, it may be computationally costly to generate the rules using current methods. Second, for users, it is very difficult to specify an appropriate minimum utility threshold and to directly obtain the most valuable high utility episodes. This is because the complexity of utility-based complex event sequences involves multiple factors, e.g., the distribution of the events and utilities, the density of the complex event sequences, and the lengths of the episodes. Third, the prediction models constructed by the episodes (e.g., frequent episodes, high utility episodes) do not consider simultaneous optimization on the parameters and selection of model subsets. Hence, they might be ineffective in terms of profitability and accuracy.
To resolve the issues as mentioned above, this dissertation addresses a series of novel utility-based episode mining problems, including (1) high utility episode rule mining, (2) top-k high utility episode mining and (3) construction of an optimized model using high utility episodes and genetic algorithms.
In the first research topic, we propose an algorithm called UBER-Mine and a compact tree structure called UR-Tree in order to efficiently discover the complete set of high utility episode rules in complex event sequences. Furthermore, in order to further demonstrate the effectiveness of our proposed method, we devise an episode-based investment model called SISTEM that is able to automatically determine multi-event episodes and associated profitable complex events embedded in stock price data. In addition, we further propose an extended version called IV-UBER constructed using high utility episode rules in the context of investment. The results show that high utility episode rules can be successfully applied to the challenging problem of predicting of stock movement, and IV-UBER outperforms several state-of-the-art methods.
In the second research topic, we propose an efficient algorithm called TKUE for efficiently discovering top-k high utility episodes from complex event sequences. Furthermore, in order to demonstrate the effectiveness and efficiency of our method in real-life applications, we also conduct an analysis on bike rentals in a city. Experiments show that the TKUE has good scalability and can effectively discover the key events affecting bike rentals.
Regarding the third research topic, we propose a novel method named HUEM-GAO to generate a prediction model of high utility episode rules and use genetic algorithms to optimize this model. The problem of stock movement prediction is employed as an example application. The results show that our HUEM-GAO method outperforms well-known machine learning methods in terms of average return and precision.
The above research topics are proposed to provide users with important and concise results, and this dissertation contributes to advancing the research in utility-based episode mining as well as providing an effective solution for high-potential applications.

[1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” in Proc. of Int'l Conf. on Very Large Data Bases (VLDB), pp. 487-499, 1994.
[2] C. F. Ahmed, S. K. Tanbeer, and B. Jeong, “A Novel Approach for Mining High Utility Sequential Patterns in Sequence Databases,” ETRI Journal, 32(5):676-686, 2010.
[3] C. F. Ahmed, S. K. Tanbeer, B. Jeong, and H. Choi, “Interactive Mining of High Utility Patterns over Data Streams,” Expert Systems with Applications, 39(15):11979-11991, 2012.
[4] X. Ao, P. Luo, C. Li, F. Zhuang, and Q. He, “Online Frequent Episode Mining,” in Proc. of IEEE Int'l Conf. on Data Engineering (ICDE), 2015.
[5] G. Appel, “Technical Analysis Power Tools for Active Investors,” Financial Times Prentice Hall, FT Press, 2005.
[6] W. Brock, J. Lakonishok, and B. LeBaron, “Simple Technical Trading Rules and the Stochastic Properties of Stock Returns,” Journal of Finance, 47(5):1731-1764, 1992.
[7] M. Caplan and Y. Becker, “Lessons Learned Using Genetic Programming in A Stock Picking Context,” in: U.-M. O'Reilly, T. Yu, R. Riolo, B. Worzel (Eds.), Genetic Programming Theory and Practice II, Springer, 6:87-102, 2004.
[8] R. Chan, Q. Yang, and Y. Shen, “Mining High-utility Itemsets,” in Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 19-26, 2003.
[9] T. C. Chu, C. T. Tsao, and Y. R. Shiue, “Application of Fuzzy Multiple Attribute Decision Making on Company Analysis for Stock Selection,” in Proc. of Soft Computing in Intelligent Systems and Information Processing, pp. 509-514, 1996.
[10] K. Chuang, J. Huang, and M. Chen, “Mining Top-K Frequent Patterns in the Presence of the Memory Constraint,” The VLDB Journal, 17(5):1321-1344, 2008.
[11] A. Dattasharma, P. K. Tripathi, and S. Gangadharpalli, “Identifying Stock Similarity Based on Episode Distances”, in Proc. of IEEE Int'l Conf. on Computer and Information Technology (ICCIT), pp. 28-35, 2008.
[12] A. Dattasharma, P. K. Tripathi, and G. Sridhar, “Identifying Stock Similarity Based on Multi-event Episodes,” in Proc. of the 7th Australasian Data Mining Conference (AusDM), 2008, pp. 153-162.
[13] H. Fanaee-T and J. Gama, “Event Labeling Combining Ensemble Detectors and Background Knowledge,” Progress in Artificial Intelligence, 2(2-3):1-15, 2014.
[14] P. Fournier-Viger and V. S Tseng, “Mining Top-K Sequential Rules,” in Proc. of Int’l Conf. on Advanced Data Mining and Applications, pp. 180-194, 2011
[15] P. Fournier-Viger and V. S Tseng, “TNS: Mining Top-K Non-redundant Sequential Rules,” in Proc. of Int’l Conf. on Annual ACM Symposium on Applied Computing, pp. 164-166, 2013.
[16] P. Fournier-Viger, C. W. Wu, and V. S. Tseng, “Mining Top-K Association Rules,” Advances in Artificial Intelligence, 61-73, 2012.
[17] J. M. Gandhi and K. S. Gayathri, “Activity Modeling in Smart Home using High Utility Pattern Mining over Data Streams,” Computing Research Repository, abs/1306.5982, 2013.
[18] D. E. Goldberg and K. Deb, “A Comparative Analysis of Selection Schemes Used in Genetic Algorithms,” Foundation of Genetic Algorithms 1:69-93, 1991.
[19] K. Gouda and M. J. Zaki, “Efficiently Mining Maximal Frequent Itemsets,” Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 163-170, 2001.
[20] G. Guo, L. Zhang, Q. Liu, E. Chen, F. Zhu, and C. Guan, “High Utility Episode Mining Made Practical and Fast,” in Proc. of Int’l Conf. on Advanced Data Mining and Applications, pp. 71-84, 2014.
[21] R. Gwadera, M. J. Atallah, and W. Szpankowski, “Reliable detection of episodes in event sequences,” Knowledge and Information Systems, 7(4):415-437, 2005.
[22] C.-F. Huang, “A Hybrid Stock Selection Model using Genetic Algorithms and Support Vector Regression,” Applied Soft Computing, 12(2):807-818, 2012.
[23] C.-F. Huang, B.-R. Chang, D.-W. Cheng, and C.-H. Chang, “Feature Selection and Parameter Optimization of a Fuzzy-based Stock Selection Model Using Genetic Algorithms,” International Journal of Fuzzy Systems, 14(1):65-75, 2012.
[24] K. Huang and C. Chang, “Efficient Mining of Frequent Episodes from Complex Sequences,” Information Systems, 33(1):96-114, 2008.
[25] V. Kecman, Learning and soft computing: support vector machines, neural networks, and fuzzy logic models, The MIT press, 2001.
[26] K. J. Kim and I. Han, “Genetic Algorithms Approach to Feature Discretization in Artificial Neural Networks for the Prediction of Stock Price Index,” Expert Systems with Applications, 19(2):125-132, 2000.
[27] S. Krishnamoorthy, “Pruning Strategies for Mining High Utility Itemsets,” Expert Systems with Applications, 42(5):2371-2381, 2015.
[28] J. L. Koh and I. C. Chiu, “An Efficient Approach for Mining Top-k High Utility Specialized Query Expansions on Social Tagging Systems,” in Proc. of Int’l Conf. on Database Systems for Advanced Applications, pp. 361-376, 2014.
[29] G.-C. Lan, T.-P. Hong, J.-P. Huang, and V. S. Tseng, “On-shelf Utility Mining with Negative Item Values,” Expert Systems with Applications, 41(7):3450-3459, 2014.
[30] G.-C. Lan, T.-P. Hong, V.-S. Tseng, and S. L. Wang, “Applying the Maximum Utility Measure in High Utility Sequential Pattern Mining,” Expert Systems with Applications, 41(11):5071-5081, 2014.
[31] G.-C. Lan, T.-P. Hong, and V.-S. Tseng, “An Efficient Projection-based Indexing Approach for Mining High Utility Itemsets,” Knowledge and Information Systems, 38(1):85-107, 2014.
[32] S. Laxman, P. S. Sastry, and K. P. Unnikrishnan, “A Fast Algorithm for Finding Frequent Episodes in Event Streams,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 410-419, 2007.
[33] H.-F. Li, “MHUI-max: An Efficient Algorithm for Discovering High-utility Itemsets from Data Streams,” Journal of Information Science, 37(5):532-245, 2011.
[34] Y. C. Li, J. S. Yeh, and C. C. Chang, “Isolated Items Discarding Strategy for Discovering High Utility Itemsets,” Data & Knowledge Engineering, 64(1):198-21, 2008.
[35] H.-F. Li, H.-Y. Huang, Y.-C. Chen, Y.-J. Liu, and S.-Y. Lee, “Fast and Memory Efficient Mining of High Utility Itemsets in Data Streams,” in Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 881-886, 2008.
[36] C.-W. Lin, T.-P. Hong, and W.-H. Lu, “An Effective Tree Structure for Mining High Utility Itemsets,” Expert Systems with Applications, 38(6):7419-7424, 2011.
[37] S. Lin, J. Qiao, and Y. Wang, “Frequent Episode Mining within the Latest Time Windows over Event Streams,” Applied Intelligence, 40(1):13-28, 2014.
[38] Y.-F. Lin, C.-F. Huang, and V. S. Tseng, “A Novel Methodology for Stock Investment using Episode Mining and Technical Indicators,” in Proc. of Int'l Conf. on Technologies and Applications of Artificial Intelligence (TAAI), pp. 5-10, 2012.
[39] Y.-F. Lin, C.-F. Huang, and V. S. Tseng, “A Novel Episode Mining Methodology for Stock Investment,” Journal of Information Science and Engineering, 30(3):571-585, 2014.
[40] Y.-F. Lin, C.-W. Wu, C-F. Huang, and V. S. Tseng. “Discovering Utility-based Episode Rules in Complex Event Sequences,” Expert Systems with Applications, 2015.
[41] Y.-F. Lin, H.-H. Shie, Y-C. Yang, and V. S. Tseng. “Design of a Real-Time and Continua-based Framework for Care Guideline Recommendation,” International Journal of Environmental Research and Public Health (IJERPH), 11(4): 4262-4279, 2014.
[42] J. Liu, K. Wang and B. Fung, “Direct Discovery of High Utility Itemsets without Candidate Generation,” in Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 984-989, 2012.
[43] Y. Liu, W. Liao, and A. Choudhary, “A Fast High Utility Itemsets Mining Algorithm,” in Proc. of ACM the 1st international workshop on Utility-based data mining, pp. 90-99, 2005.
[44] Y.-C. Liu, C.-P. Cheng, and Vincent S. Tseng, “Discovering Relational-Based Association Rules with Multiple Minimum Supports on Microarray Datasets,” Bioinformatics, 27(22):3142-3148, 2011.
[45] Y.-C. Liu, L.-C. Chen, C.-W. Liu, and Vincent S. Tseng, “Effective Peak Alignment for Mass Spectrometry Data Analysis Using Two-Phase Clustering Approach,” International Journal of Data Mining and Bioinformatics, 9(1):52-66, 2014.
[46] X. Ma, H. Pang, and K. L. Tan, “Finding Constrained Frequent Episodes using Minimal Occurrences,” in Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 471-474, 2004.
[47] H. Mannila, H. Toivonen, and A. I. Verkamo, “Discovery of Frequent Episodes in Event Sequences,” Data Mining and Knowledge Discovery, 1(3): 259-289, 1997.
[48] N. Meger, C. Leschi, N. Lucas, and C. Rigotti, “Mining episode rules in SLONG dataset,” in Proc. of the ECML/PKDD2004 Discovery Challenge, pp. 1-12, 2004.
[49] A. Mochón, D. Quintana, and Y. Sáez, “Soft Computing Techniques Applied to Finance,” Applied Intelligence, 29(2): 111-115, 2008.
[50] A. Ng and A. W. C. Fu, “Mining Frequent Episodes for Relating Financial Events and Stock Trends,” Advances in Knowledge Discovery and Data Mining, 27-39, 2003.
[51] D. Patnaik, P. Butler, N. Ramakrishnan, L. Parida, B. J. Keller, and A. Hanauer, “Experiences with Mining Temporal Event Sequences from Electronic Medical Records,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 360-368, 2011.
[52] J. Pisharath, Y. Liu, B. Ozisikyilmaz, R. Narayanan, and W. K. Liao, A. Choudhary and G. Memik, NU-MineBench Version 2.0 Dataset and Technical Report. Available at (http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html)
[53] T. S. Quah and B. Srinivasan, “Improving Returns on Stock Investment Through Neural Network Selection,” Expert Systems with Applications, 17(4):295-301, 1999.
[54] N. I. Sapankevych and R. Sankar, “Time Series Prediction using Support Vector Machines: A Survey,” IEEE Computational Intelligence Magazine, 4(2):24-38, 2009.
[55] B. A. Sensoy, “Performance Evaluation and Self-Designated Benchmark Indexes in the Mutual Fund Industry,” Journal of Financial Economics, 92(1):25-39, 2009.
[56] B. E. Shie, P. S. Yu, and V. S. Tseng, “Efficient Algorithms for Mining Maximal High Utility Itemsets from Data Streams with Different Models,” Expert Systems with Applications, 39(17):12947-12960, 2012.
[57] R. Shukla and S. Singh, “A Performance Evaluation of Global Equity Mutual Funds: Evidence from 1988-95,” Global Finance Journal, 8:279-293, 1997.
[58] N. Tatti and B. Cule, “Mining Closed Episodes with Simultaneous Events,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 1172-1180, 2012.
[59] N. Tatti and J. Vreeken, “The Long and the Short of It: Summarizing Event Sequences with Serial Episodes,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp.462-470, 2012.
[60] 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, 25(8):1772-1786, 2013.
[61] V. S. Tseng, C.-W. Wu, P. Fournier-Viger, and P. S. Yu, “Efficient Algorithms for Mining the Concise and Lossless Representation of Closed+ High Utility Itemsets,” IEEE Transactions on Knowledge and Data Engineering, 27(3):726-739, 2014.
[62] V. S. Tseng, C.-W. Wu, B. E. Shie, and P. S. Yu, “UP-Growth: An Efficient Algorithm for High Utility Itemset Mining,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 253-262, 2010.
[63] B. Vo, H. Nguyen, T. B. Ho, and B. Le, “Parallel Method for Mining High utility Itemsets from Vertically Partitioned Distributed Databases,” in Proc. of Int’l Conf. on Knowledge-based and Intelligent Information and Engineering Systems, pp. 251-260, 2009.
[64] L. Wan, J. Liao, and X. Zhu, “A Frequent Pattern Based Framework for Event Detection in Sensor Network Stream Data,” in Proc. of the Third International Workshop on Knowledge Discovery from Sensor Data (SensorKDD), pp. 87-96, 2009.
[65] H. White, “Economic Prediction using Neural Networks: The Case of IBM Daily Stock Returns,” in Proc. of the Second Annual IEEE Conference on Neural Networks, pp. 451-458, 1998.
[66] C.-W. Wu, B.-E. Shie, V. S. Tseng, and P. S. Yu, “Mining Top-K High Utility Itemsets,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 78-86, 2012.
[67] C.-W. Wu, Y.-F. Lin, P. S. Yu, and V. S. Tseng, “Mining High Utility Episodes in Complex Event Sequences,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 536-544, 2013.
[68] C. Wu, P. Fournier-Viger, P. S. Yu, and V. S. Tseng, “Efficient Mining of a Concise and Lossless Representation of High Utility Itemsets,” in Proc. of IEEE Int'l Conf. on Data Mining (ICDM), pp. 824-833, 2011.
[69] X. Xi, E. J. Keogh, L. Wei, and A. Mafra-Neto, “Finding Motifs in a Database of Shapes,” in Proc. of SIAM International Conference on Data Mining(SDM), pp. 249-260, 2007.
[70] J. Yin, Z. Zheng, and L. Cao, “USpan: An Efficient Algorithm for Mining High Utility Sequential Patterns,” in Proc. of ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp. 660-668, 2012.
[71] J. Yin, Z. Zheng, L. Cao, Y. Song, and W. Wei, “Efficiently Mining Top-K High Utility Sequential Patterns,” in Proc. of IEEE Int’l Conf. on Data Mining (ICDM), pp. 1259-1264, 2013.
[72] G. Yu, K. Li, and S. Shao, “Mining High Utility Itemsets in Large High Dimensional Data,” in Proc. of Int’l Workshop on Knowledge Discovery and Data Mining, pp. 17-20, 2008.
[73] M. Zihayat and A. An, “Mining Top-K High Utility Patterns over Data Streams,” Information Sciences, 285:138-161, 2014.
[74] A. Zimmermann, “Understanding episode mining techniques: Benchmarking on diverse, realistic, artificial data,” Intelligent Data Analysis, 18(5):761-791, 2014.
[75] Frequent itemset mining implementations repository. Available at (http://fimi.cs.helsinki.fi/)
[76] IBM Quest Data Mining Project, Quest Synthetic Data Generation Code. Available at (http://www.almaden.ibm.com/cs /quest/syndata.html)
[77] Microsoft Developer Network (2000). FoodMart2000. Retrieved July 06, 2014. Available at (http://technet.microsoft.com/en-us/library/aa217032%28v=sql.80%29.aspx)
[78] Bank of America (1784). Bank Account Interest Rates. Retrieved October 15, 2013. Available at (https://www.bankofamerica.com/deposits/bank-account-interest-rates.go)
[79] Taiwan Stock Exchange Corporation (1962). Historical Trading Info/Data. Retrieved July 06, 2013, Available at (http://www.twse.com.tw/en/trading/exchange/MI_INDEX/genpage/
Report201411/A11220141126MS.php)
[80] Capital Bike Share System: Capital bike sharing trip history data 2013. Available at (http://
www.capitalbikeshare.com/trip-history-data)
[81] Yahoo! Finance. Available at (http://finance.yahoo.com/)