On Probabilistic Models for Uncertain Sequential Pattern Mining

摘要：

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. KDD09;Chui et al., PAKDD07,08 and probabilistic frequentness Bernecker et al., KDD09. 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.

关键词： Mining Uncertain Data Sequential Pattern Mining Probabilistic Databases Novel Algorithms for Mining Theoretical Foundations of Data Mining

作者: Muhammad Muzammal Rajeev Raman

作者单位: Department of Computer Science University of Leicester UK

会议类型: 国际会议

会议名称: 6th International Conference on Advanced Data Mining and Applications(第六届先进数据挖掘及应用国际会议 ADMA 2010)

会议地点: 重庆

会议语种:英文

页码: 60-72

在线出版日期: 2010-11-19（万方平台首次上网日期，不代表论文的发表时间）