On probabilistic models for uncertain sequential pattern mining

Muhammad Muzammal; Rajeev Raman

doi:10.1007/978-3-642-17316-5_6

On probabilistic models for uncertain sequential pattern mining

Muhammad Muzammal^*, Rajeev Raman

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings
Pages	60-72
Number of pages	13
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-17316-5_6
Publication status	Published - 2010
Externally published	Yes
Event	6th International Conference on Advanced Data Mining and Applications, ADMA 2010 - Chongqing, China Duration: 19 Nov 2010 → 21 Nov 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6440 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Conference on Advanced Data Mining and Applications, ADMA 2010
Country/Territory	China
City	Chongqing
Period	19/11/10 → 21/11/10

Keywords

Mining Uncertain Data
Novel Algorithms for Mining
Probabilistic Databases
Sequential Pattern Mining
Theoretical Foundations of Data Mining

Access to Document

10.1007/978-3-642-17316-5_6

Cite this

Muzammal, M., & Raman, R. (2010). On probabilistic models for uncertain sequential pattern mining. In Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings (PART 1 ed., pp. 60-72). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6440 LNAI, No. PART 1). https://doi.org/10.1007/978-3-642-17316-5_6

@inproceedings{bab540b4e857459eb2ba5ddc76f610db,

title = "On probabilistic models for uncertain sequential pattern mining",

abstract = "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.",

keywords = "Mining Uncertain Data, Novel Algorithms for Mining, Probabilistic Databases, Sequential Pattern Mining, Theoretical Foundations of Data Mining",

author = "Muhammad Muzammal and Rajeev Raman",

year = "2010",

doi = "10.1007/978-3-642-17316-5_6",

language = "English",

isbn = "3642173152",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "60--72",

booktitle = "Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings",

edition = "PART 1",

note = "6th International Conference on Advanced Data Mining and Applications, ADMA 2010 ; Conference date: 19-11-2010 Through 21-11-2010",

}

Muzammal, M & Raman, R 2010, On probabilistic models for uncertain sequential pattern mining. in Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6440 LNAI, pp. 60-72, 6th International Conference on Advanced Data Mining and Applications, ADMA 2010, Chongqing, China, 19/11/10. https://doi.org/10.1007/978-3-642-17316-5_6

On probabilistic models for uncertain sequential pattern mining. / Muzammal, Muhammad; Raman, Rajeev.
Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings. PART 1. ed. 2010. p. 60-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6440 LNAI, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On probabilistic models for uncertain sequential pattern mining

AU - Muzammal, Muhammad

AU - Raman, Rajeev

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Mining Uncertain Data

KW - Novel Algorithms for Mining

KW - Probabilistic Databases

KW - Sequential Pattern Mining

KW - Theoretical Foundations of Data Mining

UR - http://www.scopus.com/inward/record.url?scp=78650184230&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17316-5_6

DO - 10.1007/978-3-642-17316-5_6

M3 - Conference contribution

AN - SCOPUS:78650184230

SN - 3642173152

SN - 9783642173158

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 60

EP - 72

BT - Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings

T2 - 6th International Conference on Advanced Data Mining and Applications, ADMA 2010

Y2 - 19 November 2010 through 21 November 2010

ER -

Muzammal M, Raman R. On probabilistic models for uncertain sequential pattern mining. In Advanced Data Mining and Applications - 6th International Conference, ADMA 2010, Proceedings. PART 1 ed. 2010. p. 60-72. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-17316-5_6

On probabilistic models for uncertain sequential pattern mining

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this