On efficiently mining high utility sequential patterns

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2016-11

期刊名稱

KNOWLEDGE AND INFORMATION SYSTEMS

卷期與頁次

第 49 卷第 2 期,頁 597–627

ISSN

0219-1377

語言

英文

摘要

High utility sequential pattern mining is an emerging topic in pattern mining, which refers to identify sequences with high utilities (e.g., profits) but probably with low frequencies. To identify high utility sequential patterns, due to lack of downward closure property in this problem, most existing algorithms first generate candidate sequences with high sequence-weighted utilities (SWUs), which is an upper bound of the utilities of a sequence and all its supersequences, and then calculate the actual utilities of these candidates. This causes a large number of candidates since SWU is usually much larger than the real utilities of a sequence and all its supersequences. In view of this, we propose two tight utility upper bounds, prefix extension utility and reduced sequence utility, as well as two companion pruning strategies, and devise HUS-Span algorithm to identify high utility sequential patterns by employing these two pruning strategies. In addition, since setting a proper utility threshold is usually difficult for users, we also propose algorithm TKHUS-Span to identify top-k high utility sequential patterns by using these two pruning strategies. Three searching strategies, guided depth-first search (GDFS), best-first search (BFS) and hybrid search of BFS and GDFS, are also proposed to improve the efficiency of TKHUS-Span. Experimental results on some real and synthetic datasets show that HUS-Span and TKHUS-Span with strategy BFS are able to generate less candidate sequences and thus outperform other prior algorithms in terms of mining efficiency.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Wang, J.-Z., Huang, J.-L., & Chen, Y.-C. (2016). On efficiently mining high utility sequential patterns. KNOWLEDGE AND INFORMATION SYSTEMS, 49(2), 597–627. https://doi.org/10.1007/s10115-015-0914-8

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/132623