Advertisement
Published in:
2010 | OriginalPaper | Chapter
On Probabilistic Models for Uncertain Sequential Pattern Mining
Authors : Muhammad Muzammal, Rajeev Raman
Published in: Advanced Data Mining and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study uncertainty models in
sequential pattern mining
. We consider situations where there is uncertainty either about a
source
or an
event
. We show that both these types of uncertainties could be modelled using probabilistic databases, and give possible-worlds semantics for both. We then describe ”interestingness” criteria based on two notions of frequentness (previously studied for frequent itemset mining) namely
expected support
[C. Aggarwal et al. KDD’09;Chui et al., PAKDD’07,’08] and
probabilistic frequentness
[Bernecker et al., KDD’09]. We study the interestingness criteria from a complexity-theoretic perspective, and show that in case of source-level uncertainty, evaluating probabilistic frequentness is #P-complete, and thus no polynomial time algorithms are likely to exist, but evaluate the interestingness predicate in polynomial time in the remaining cases.