臺灣博碩士論文加值系統

序列式樣跟以往的頻繁項目集不同的地方在於序列式樣加入了時間點的概念，成為了一項重要的話題，不論是在靜態的資料庫或是串流環境中都有相當多的研究討論。
然而大部分的研究並沒有考慮到購買商品的數量與單位利潤，但是在現實生活中卻是個重要的議題。於是效益序列探勘(Utility sequential mining)為近年來新的研究領域，效益序列探勘考慮了項目的數量與單位利潤，其目標是在於找到高收益的商品組合。
本篇論文，所探討的是如何在連續不斷的資料湧進中找出高效益序列式樣，我們以滑動視窗模型(Sliding window-based method)提出HUUS(Mining High Utility Sequential Patterns in the Data Stream Environments)演算法，並設計一系列的實驗，來驗證我們的演算法是有效率的。

Sequential patterns mining problem is a major topic in many researches and has become an interesting topic that is continuously discussed. However, most of the studies only consider the purchasing of good without evaluating the amount of the purchase of goods that often happens in real life. To cope with this drawback, the concept of utility mining is proposed. Utility sequential mining is a new area of research that has been widely study in recent years. By considering the benefits of mining sequential number and unit profit item, the goal is to find a combination of high-yield commodity.
In this research, the problem of how to find high utility sequential patterns in a data stream environment is discussed. A novel algorithm, called HUSS (Mining High Utility Sequential Patterns in the Data Stream Environments) was proposed to deal with this problem. Moreover, a set of experiments was performed to show the benefit of the proposed approach. According to the experimental results, HUSS algorithm can mine high utility sequential patterns in the stream environment effectively.

第一章 緒論
第二章 背景知識與相關研究
2.1 背景知識
2.2 相關研究
2.2.1 靜態環境下探勘序列式樣
2.2.2資料串流環境下探勘序列式樣
2.2.3靜態環境下探勘高效益序列式樣
第三章 HUSS演算法
3.1 初步定義與反轉資料庫
3.2建立Bitmap矩陣
3.3建立字母排序樹與找出高效益序列式樣
3.4 Sliding Window
第四章 實驗結果
4.1 執行時間
4.2 記憶體使用量
4.3 執行時間與記憶體的比較
第五章 結論與未來展望
參考文獻

[1] J. Ayres, J. Gehrke, T. Yiu, and J. Flannick, “Sequential Pattern Mining using A Bitmap Representation,” in: Proc. ACM International Conference on Knowledge Discovery and Data Mining, 2002, pp. 429-435.
[2] Agrawal, R., & Srikant, R., “Fast algorithms for mining association rules.” In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), pp. 487–499, 1994.
[3] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proc.11th Int. Conf. Data Eng., 1995, pp. 3-14.
[4] C. F. Ahmed, S. K. Tanbeer and B. Jeong, A Novel Approach for Mining High-Utility Sequential Patterns in Sequence Databases, ETRI Journal, 2010, vol.32,
no.5, pp.676-686.
[5] Ahmed, C. F., Tanbeer, S. K., Jeong, B.-S., Choi, H.-J., “Interactive mining of high utility patterns over data streams.” Expert Systems Applications, 39 (15), pp. 11979–11991, 2012.
[6]Lei Chang, Tengjiao Wang, Dongqing Yang, Hua Luan, "SeqStream: Mining Closed Sequential Patterns over Stream Sliding Windows," icdm, pp.83-92, 2008 Eighth IEEE International Conference on Data Mining, 2008.
[7] G. Chen, X. Wu, and X. Zhu. “Sequential Pattern Mining in Multiple Streams,” The 5th IEEE International Conference on Data Mining, Washington. 2005 Nobember 27-30.
[8] Chan, R. Yang,, Q., & Shen, Y.D., “Mining High Utility Itemsets,” Proc. Third IEEE Int’l Conf. Data Mining (ICDM ), pp. 19-26, 2003.
[9] C.I. Ezeife and Min Chen, “Incremental Mining of Web Sequential Patterns Using PLWAP Tree on Tolerance MinSupport,” in: Proc. IEEE International Database Engineering and Applications Symposium, 2004, pp. 465-469.
[10] C.I. Ezeife and Mostafa Monwar, “SSM: A Frequent Sequential Data Stream Patterns Miner” in: Proc. IEEE Symposium on Computational Intelligence and Data Mining, 2007, pp.120-126.
[11]Guanling Lee, Kuo-Che Hung, Yi-Chun Chen.“PTree: Mining Sequential Patterns Efficiently in Multiple Data Streams Environment,” Journal of Information Science & Engineering;Nov2013, Vol. 29 Issue 6, p1151.
[12]Chin-Chuan Ho, Hua-Fu Li, Fang-Fei Kuo, Suh-Yin Lee. “Incremental Mining of Sequential Patterns over a Stream Sliding Window,” Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), 18-22 December 2006.
[13] Li, H. –F, “MHUI-max: an efficient algorithm for discovering high-utility itemsets from data streams.” J Inf Sci 37(5):532–545, 2011.
[14] H. Li and H. Chen. “GraSeq: A Novel Approximate Mining Approach of Sequential Patterns over Data Stream,” The 3rd International conference on Advanced Data Mining and Applications. 2007 May 401-411; Harbin, China.
[15] Li, H. -F., Huang, H. -Y., Chen, Y. -C., Liu, Y. -J., & Lee, S. -Y., “Fast and memory efficient mining of high utility itemsets in data streams.” In Proceedings of the 8th IEEE international conference on data mining (ICDM), pp. 881–886, 2008.
[16]Guo-Cheng Lan, Tzung-Pei Hong, Jen-Peng Huang, and I-Wei Lin “Discovery of High Utility Sequential Patterns with Consideration of On-shelf Time Periods of Products,” The 31st Workshop on Combinatorial Mathematics and Computation Theory., 2014.[LLC05] Liu, Y., Liao, W. -K., & Choudhary, A., “A fast high-utility itemsets mining algorithm.” In Proc. of the Utility-Based Data Mining Workshop, 2005.
[17] Liu,M. and Qu, J., “Mining High Utility Itemsets without Candidate Generation.” In Proc. Of the ACM Int'l Conf. on Information and Knowledge Management (CIKM), pp. 55-64, 2012.
[18] Li, Y.-C., Yeh, J. -S., & Chang, C. -C., “Isolated items discarding strategy for discovering high utility itemsets.” Data & Knowledge Engineering, 64, 198–217, 2008.
[19] M. J. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences,” in: Proc. ACM Machine Learning, 2001, pp. 31-60.
[20] J. Pei, J. Han, B Mortazavi-Asl, and H. Pinto, “PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth,” in: Proc. IEEE International Conference on Data Engineering, 2001, pp. 215-224.
[21] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations and Performance Improvements,” in: Proc. IEEE International Conference on Extending Database Technology, 1996, pp. 3-17.
[22] C. Raissi, P. Poncelet, and M. Teisseire. “SPEED: Mining Maximal Sequential Patterns over Data Streams,” The 3rd IEEE International Conference on Intelligent Systems. 2006 September 546-552.
[23] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations and Performance Improvements,” Proc. 5th Int. Conf. Extending Database Technol., 1996, pp. 3-17.
[24] Tseng, V. S., Chu, C.-J., & Liang, T., “Efficient mining of temporal high utility itemsets from data streams.” Proceedings of the second ACM international workshop on utility-based data mining (UBDM). Philadelphia, USA: Pennsylvania, 2006.
[25] Tseng, V. S., Wu, C. -W., Shie, B. -E, & Yu, P. S., “Up-growth: An efficient algorithm for high utility itemset mining.” In Proc. ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, pp. 253–262, 2010.
[26] Tseng, V. S.,Shie, B.-E.,Wu, C.-W., &Yu, P. S., ”Efficient algorithms for mining high utility itemsets from transactional databases.” IEEE Transactions on Knowledge and Data Engineering, 2012, doi: 10.1109/TKDE.2012.59.
[27] Wu, C. -W., Shie, B. -E, Yu, P. S., Tseng, V. S., “Mining top-K high utility itemsets.” In Proc. of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 78-86, 2012.
[28] Wu, C. W., P. Fournier-Viger, Yu, P. S., & Tseng, V. S., “Efficient mining of a concise and lossless representation of high utility itemsets.” In Proc. IEEE Int'l Conf. Data Mining, pages 824 –833, 2011.
[29]Yang, Shih-Yang; Chao, Ching-Ming; Chen, Po-Zung; Sun, Chu-Hao. “Incremental Mining of Across-streams Sequential Patterns in Multiple Data Streams,” Journal of Computers. 2011, Vol. 6 Issue 3, pp.449.
[30]Junfu Yin, Zhigang Zheng, and Longbing Cao, “USpan: An Efficient Algorithm for Mining High Utility Sequential Patterns,”Knowledge-Discovery in Databases., 2012 ,pp. 660-668.
[31] M.J. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences,” Mach. Learning, vol. 42, no. 1-2, Jan. 2001, pp. 31-60.