License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08471.4
URN: urn:nbn:de:0030-drops-20087
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2008/
|
Go to the corresponding Portal |
Vaisman, Alejandro ;
Gómez, Leticia I. ;
Kuijpers, Bart
Temporal Support of Regular Expressions in Sequential Pattern Mining
Abstract
Classic algorithms for sequential pattern discovery,return all frequent sequences present in a database. Since, in general, only a few ones are interesting from a user's point of view, languages based on regular expressions (RE) have been proposed to restrict frequent sequences to the ones that satisfy
user-specified constraints.
Although the support of a sequence is computed as the number of data-sequences satisfying a pattern with respect to the total number of data-sequences in the database, once regular expressions come into play, new approaches to the concept of support are needed. For example, users may be interested in computing the support of the RE as a whole, in addition to the one of a particular pattern.
As a simple example, the expression $(A|B).C$ is satisfied by sequences like A.C or B.C. Even though the semantics of this RE suggests that both of them are
equally interesting to the user, if neither of them verifies a minimum support although together they do), they would not be retrieved.
Also, when the items are frequently updated, the traditional way of counting support in sequential pattern mining may lead to incorrect (or, at least incomplete), conclusions. For example, if we are looking for the support of the sequence A.B, where A and B are two items such that A was created after B, all sequences in the database that were completed before A was created, can never produce a match. Therefore, accounting for them would underestimate the support of the sequence A.B.
The problem gets more involved if we are interested in categorical sequential patterns. In light of the above, in this paper we propose to revise the classic notion of support in sequential pattern mining, introducing the concept of temporal support of regular expressions, intuitively defined as
the number of sequences satisfying a target pattern, out of the total number of
sequences that could have possibly matched such pattern, where the pattern is
defined as a RE over complex items (i.e., not only item identifiers,
but also attributes and functions).
We present and discuss a theoretical framework for these novel notion of support.
BibTeX - Entry
@InProceedings{vaisman_et_al:DagSemProc.08471.4,
author = {Vaisman, Alejandro and G\'{o}mez, Leticia I. and Kuijpers, Bart},
title = {{Temporal Support of Regular Expressions in Sequential Pattern Mining}},
booktitle = {Geographic Privacy-Aware Knowledge Discovery and Delivery},
pages = {1--15},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2009},
volume = {8471},
editor = {Bart Kuijpers and Dino Pedreschi and Yucel Saygin and Stefano Spaccapietra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2009/2008},
URN = {urn:nbn:de:0030-drops-20087},
doi = {10.4230/DagSemProc.08471.4},
annote = {Keywords: Temporal support, sequential pattern mining}
}
|
Keywords: |
|
Temporal support, sequential pattern mining |
|
Collection: |
|
08471 - Geographic Privacy-Aware Knowledge Discovery and Delivery |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
13.05.2009 |
