在資料串流的環境下探勘高效益項目集

Mining High Utility Itemsets in a Data Stream

10.6188/JEB.201806_20(1).0004

顏秀珍(Show-Jane Yen)；李御璽(Yue-Shi Lee)

資料探勘 ； 高效益項目集 ； 資料串流 ； 交易資料庫 ； Data mining ； high utility itemset ； data stream ； transaction database

電子商務學報

20卷1期（2018 / 06 / 01）

99 - 123

繁體中文

探勘高效益項目集同時考慮每筆交易中各項目被購買的數量以及項目集可能帶給公司的利潤，以求出最有價值的商品組合。然而，交易資料會隨時間不斷改變。當資料新增或刪除時，高效益項目集也會有所改變。目前在資料串流的環境下探勘高效益項目集的演算法都需要花費很多時間再次掃描原始資料庫並搜尋候選高效益項目集，才能重新找出所有的高效益項目集，沒有利用到之前已找出的高效益項目集。因此，本篇論文提出一個在資料串流的環境下有效率的探勘高效益項目集的演算法。當資料新增或刪除時，我們的演算法不需要再掃描資料庫，也不需要搜尋候選高效益項目集，就可直接找出所有的高效益項目集。實驗結果也顯示我們的方法比之前的演算法更有效率。

Mining high utility itemsets considers the purchased quantities and the profits of the itemsets in the transactions, which can find the profible products. In addition, the transactions will be continuouslly changed over time. When the transactions are added or deleted, the original high utility itemsets will be changed. The previous proposed algorithms for mining high utility itemsets over data streams need to rescan the original database and search for the candidate high utility itemsets without using the previous high utility itemsets. Therefore, in this paper, we propose an algorithm for efficiently mining high utility itemsets in data streams, when the transaction are added or removed, our algorithms do not need to re-scan the transaction database and search for candidate high utility itemsets. Experimental results also show that our algorithm outperforms the previous approaches.

1. Agrawal, R.,Srikant, R.(1994).Fast algorithms for mining association rules in large database.Proceedings of the 20th International Conference on Very Large Data Bases(VLDB 1994),San Francisco, CA, USA:
2. Ahmed, C. F.,Tanbeer, S. K.,Jeong, B. S.,Lee, Y. K.(2009).Efficient tree structures for high utility pattern mining in incremental databases.IEEE Transactions on Knowledge and Data Engineering,21(12),1708-1721.
3. Han, J.,Pei, J.,Yin, Y.,Mao, R.(2004).Mining frequent patterns without candidate generation: A frequent-pattern tree approach.Data Mining and Knowledge Discovery,8(1),53-87.
4. Li, H. F.,Huang, H. Y.,Chen, Y. C.,Liu, Y. J.,Lee, S. Y.(2008).Fast and memory efficient mining of high utility itemsets in data streams.Proceedings of the 8th IEEE International Conference on Data Mining(ICDM 2008),Washington, DC, USA.:
5. Li, Y. C.,Yeh, J. S.,Chang, C. C.(2008).Isolated items discarding strategy for discovering high utility Itemsets.Data and Knowledge Engineering,64(1),198-217.
6. Lin, C. W.,Lan, G. C.,Hong, T. P.(2015).Mining high utility itemsets for transaction deletion in a dynamic database.Intelligent Data Analysis,19(1),43-55.
7. Liu, Y.,Liao, W. K.,Choudhary, A.(2005).A fast high utility itemsets mining algorithm.Proceedings of the 1st International Workshop on Utility-Based Data Mining(UBDM 2005),Chicago, IL, USA.:
8. Ryang, H.,Yun, U.(2016).High utility pattern mining over data streams with sliding window technique.Expert Systems with Applications,57,214-231.
9. Tseng, V. S.,Chu, C. J.,Liang, T.(2006).Efficient mining of temporal high utility itemsets from data streams.Proceedings of the Second International Workshop on Utility-Based Data Mining(UBDM 2006),Philadelphia, PA, USA.:
10. Tseng, V. S.,Shie, B. E.,Wu, C. W.,Yu, P. S.(2013).Efficient algorithms for mining high utility itemsets from transactional databases.IEEE Transactions on Knowledge and Data Engineering,25(8),1772-1786.
11. Tseng, V. S.,Wu, C. W.,Shie, B. E.,Yu, P. S.(2010).UP-growth: An efficient algorithm for high utility itemset mining.Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD 2010),Washington, DC, USA.:
12. Xu, Y.,Yu, J. X.,Liu, G.,Lu, H.(2002).From path tree to frequent patterns: A framework for mining frequent patterns.Proceedings of the 2002 IEEE International Conference on Data Mining(ICDM 2002),Maebashi, Japan:
13. Yen, S. J.,Chen, A. L. P.(2001).A graph-based approach for discovering various types of association rules.IEEE Transactions on Knowledge and Data Engineering,13(5),839-845.
14. Yen, S. J.,Chen, C. C.,Lee, Y. S.(2011).A fast algorithm for mining high utility Itemsets.Proceedings of International Workshop on Behavior Informatics(BI 2011),Shenzhen, China:
15. Yen, S. J.,Lee, Y. S.,Wu, C.W.,Lin, C. L.(2009).An efficient algorithm for maintaining frequent closed itemsets over data stream.Proceedings of the 22nd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems(IEA/AIE 2009),Tainan, Taiwan:
16. Yen, S. J.,Wang, C. K.,Ouyang, L. Y.(2012).A search space reduced algorithm for mining frequent patterns.Journal of Information Science and Engineering,28(1),177-191.
17. Yun, U.,Ryang, H.(2015).Incremental high utility pattern mining with static and dynamic databases.Applied Intelligence,42(2),323-352.
18. Zihayat, M.,An, A.(2014).Mining top-k high utility patterns over data streams.Information Sciences,285,138-161.