VM-NSP

Wang, W; Cao, L

VM-NSP

Wang, W Cao, L

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: ACM Transactions on Information Systems, 2021, 39, (2), pp. 1-27
Issue Date:: 2021-03

Closed Access

	Filename	Description	Size
	TOIS_2020_0018-CR.pdf	Accepted version	1.22 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, W
dc.contributor.author	Cao, L https://orcid.org/0000-0003-1562-9429
dc.date.accessioned	2021-04-01T10:55:44Z
dc.date.available	2021-04-01T10:55:44Z
dc.date.issued	2021-03
dc.identifier.citation	ACM Transactions on Information Systems, 2021, 39, (2), pp. 1-27
dc.identifier.issn	1046-8188
dc.identifier.issn	1558-2868
dc.identifier.uri	http://hdl.handle.net/10453/147801
dc.description.abstract	<jats:p> Negative sequential patterns (NSPs) capture more informative and actionable knowledge than classic positive sequential patterns (PSPs) due to the involvement of both occurring and nonoccurring behaviors and events, which can contribute to many relevant applications. However, NSP mining is nontrivial, as it involves fundamental challenges requiring distinct theoretical foundations and is not directly addressable by PSP mining. In the very limited research reported on NSP mining, a negative element constraint (NEC) is incorporated to only consider the NSPs composed of specific forms of elements (containing either positive or negative items), which results in many valuable NSPs being missed. Here, we loosen the NEC (called <jats:italic>loose negative element constraint</jats:italic> (LNEC)) to include partial negative elements containing both positive and negative items, which enables the discovery of more flexible patterns but incorporates significant new learning challenges, such as representing and mining complete NSPs. Accordingly, we formalize the LNEC-based NSP mining problem and propose a novel <jats:italic>vertical NSP mining framework</jats:italic> , VM-NSP, to efficiently mine the complete set of NSPs by a vertical representation (VR) of each sequence. An efficient <jats:italic>bitmap-based vertical NSP mining algorithm</jats:italic> , bM-NSP, introduces a bitmap hash table--based VR and a prefix-based negative sequential candidate generation strategy to optimize the discovery performance. VM-NSP and its implementation bM-NSP form the first VR-based approach for complete NSP mining with LNEC. Theoretical analyses and experiments confirm the performance superiority of bM-NSP on synthetic and real-life datasets w.r.t. diverse data factors, which substantially expands existing NSP mining methods toward flexible NSP discovery. </jats:p>
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation	http://purl.org/au-research/grants/arc/DP190101079
dc.relation.ispartof	ACM Transactions on Information Systems
dc.relation.isbasedon	10.1145/3440874
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0806 Information Systems, 0807 Library and Information Studies
dc.subject.classification	Information Systems
dc.title	VM-NSP
dc.type	Journal Article
utslib.citation.volume	39
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/A/DRsch The Data Science Institute
utslib.copyright.status	closed_access	*
dc.date.updated	2021-04-01T10:55:42Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	39
utslib.citation.issue	2

Abstract:

Negative sequential patterns (NSPs) capture more informative and actionable knowledge than classic positive sequential patterns (PSPs) due to the involvement of both occurring and nonoccurring behaviors and events, which can contribute to many relevant applications. However, NSP mining is nontrivial, as it involves fundamental challenges requiring distinct theoretical foundations and is not directly addressable by PSP mining. In the very limited research reported on NSP mining, a negative element constraint (NEC) is incorporated to only consider the NSPs composed of specific forms of elements (containing either positive or negative items), which results in many valuable NSPs being missed. Here, we loosen the NEC (called loose negative element constraint (LNEC)) to include partial negative elements containing both positive and negative items, which enables the discovery of more flexible patterns but incorporates significant new learning challenges, such as representing and mining complete NSPs. Accordingly, we formalize the LNEC-based NSP mining problem and propose a novel vertical NSP mining framework , VM-NSP, to efficiently mine the complete set of NSPs by a vertical representation (VR) of each sequence. An efficient bitmap-based vertical NSP mining algorithm , bM-NSP, introduces a bitmap hash table--based VR and a prefix-based negative sequential candidate generation strategy to optimize the discovery performance. VM-NSP and its implementation bM-NSP form the first VR-based approach for complete NSP mining with LNEC. Theoretical analyses and experiments confirm the performance superiority of bM-NSP on synthetic and real-life datasets w.r.t. diverse data factors, which substantially expands existing NSP mining methods toward flexible NSP discovery.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/147801