General algorithms for mining closed flexible patterns under various equivalence relations

Tomohiro I; Yuki Enokuma; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-642-33486-3_28

General algorithms for mining closed flexible patterns under various equivalence relations

Tomohiro I, Yuki Enokuma, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

Abstract

We address the closed pattern discovery problem in sequential databases for the class of flexible patterns. We propose two techniques of coarsening existing equivalence relations on the set of patterns to obtain new equivalence relations. Our new algorithm GenCloFlex is a generalization of MaxFlex proposed by Arimura and Uno (2007) that was designed for a particular equivalence relation. GenCloFlex can cope with existing, as well as new equivalence relations, and we investigate the computational complexities of the algorithm for respective equivalence relations. Then, we present an improved algorithm GenCloFlex+ based on new pruning techniques, which improve the delay time per output for some of the equivalence relations. By computational experiments on synthetic data, we show that most of the redundancies in the mined patterns are removed using the proposed equivalence relations.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings
Publisher	Springer Verlag
Pages	435-450
Number of pages	16
Edition	PART 2
ISBN (Print)	9783642334856
DOIs	https://doi.org/10.1007/978-3-642-33486-3_28
Publication status	Published - 2012
Event	2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012 - Bristol, United Kingdom Duration: Sept 24 2012 → Sept 28 2012

Publication series

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

Other

Other	2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012
Country/Territory	United Kingdom
City	Bristol
Period	9/24/12 → 9/28/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-33486-3_28

Cite this

I, T., Enokuma, Y., Bannai, H., & Takeda, M. (2012). General algorithms for mining closed flexible patterns under various equivalence relations. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings (PART 2 ed., pp. 435-450). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7524, No. PART 2). Springer Verlag. https://doi.org/10.1007/978-3-642-33486-3_28

General algorithms for mining closed flexible patterns under various equivalence relations. / I, Tomohiro; Enokuma, Yuki; Bannai, Hideo et al.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings. PART 2. ed. Springer Verlag, 2012. p. 435-450 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7524, No. PART 2).

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

I, T, Enokuma, Y, Bannai, H & Takeda, M 2012, General algorithms for mining closed flexible patterns under various equivalence relations. in Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 7524, Springer Verlag, pp. 435-450, 2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012, Bristol, United Kingdom, 9/24/12. https://doi.org/10.1007/978-3-642-33486-3_28

I T, Enokuma Y, Bannai H, Takeda M. General algorithms for mining closed flexible patterns under various equivalence relations. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings. PART 2 ed. Springer Verlag. 2012. p. 435-450. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-33486-3_28

I, Tomohiro ; Enokuma, Yuki ; Bannai, Hideo et al. / General algorithms for mining closed flexible patterns under various equivalence relations. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings. PART 2. ed. Springer Verlag, 2012. pp. 435-450 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{63f4d798d4774a6fbc1e7b799abc59e0,

title = "General algorithms for mining closed flexible patterns under various equivalence relations",

abstract = "We address the closed pattern discovery problem in sequential databases for the class of flexible patterns. We propose two techniques of coarsening existing equivalence relations on the set of patterns to obtain new equivalence relations. Our new algorithm GenCloFlex is a generalization of MaxFlex proposed by Arimura and Uno (2007) that was designed for a particular equivalence relation. GenCloFlex can cope with existing, as well as new equivalence relations, and we investigate the computational complexities of the algorithm for respective equivalence relations. Then, we present an improved algorithm GenCloFlex+ based on new pruning techniques, which improve the delay time per output for some of the equivalence relations. By computational experiments on synthetic data, we show that most of the redundancies in the mined patterns are removed using the proposed equivalence relations.",

author = "Tomohiro I and Yuki Enokuma and Hideo Bannai and Masayuki Takeda",

year = "2012",

doi = "10.1007/978-3-642-33486-3_28",

language = "English",

isbn = "9783642334856",

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

publisher = "Springer Verlag",

number = "PART 2",

pages = "435--450",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings",

address = "Germany",

edition = "PART 2",

note = "2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012 ; Conference date: 24-09-2012 Through 28-09-2012",

}

TY - GEN

T1 - General algorithms for mining closed flexible patterns under various equivalence relations

AU - I, Tomohiro

AU - Enokuma, Yuki

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2012

Y1 - 2012

N2 - We address the closed pattern discovery problem in sequential databases for the class of flexible patterns. We propose two techniques of coarsening existing equivalence relations on the set of patterns to obtain new equivalence relations. Our new algorithm GenCloFlex is a generalization of MaxFlex proposed by Arimura and Uno (2007) that was designed for a particular equivalence relation. GenCloFlex can cope with existing, as well as new equivalence relations, and we investigate the computational complexities of the algorithm for respective equivalence relations. Then, we present an improved algorithm GenCloFlex+ based on new pruning techniques, which improve the delay time per output for some of the equivalence relations. By computational experiments on synthetic data, we show that most of the redundancies in the mined patterns are removed using the proposed equivalence relations.

AB - We address the closed pattern discovery problem in sequential databases for the class of flexible patterns. We propose two techniques of coarsening existing equivalence relations on the set of patterns to obtain new equivalence relations. Our new algorithm GenCloFlex is a generalization of MaxFlex proposed by Arimura and Uno (2007) that was designed for a particular equivalence relation. GenCloFlex can cope with existing, as well as new equivalence relations, and we investigate the computational complexities of the algorithm for respective equivalence relations. Then, we present an improved algorithm GenCloFlex+ based on new pruning techniques, which improve the delay time per output for some of the equivalence relations. By computational experiments on synthetic data, we show that most of the redundancies in the mined patterns are removed using the proposed equivalence relations.

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

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

U2 - 10.1007/978-3-642-33486-3_28

DO - 10.1007/978-3-642-33486-3_28

M3 - Conference contribution

AN - SCOPUS:84866885602

SN - 9783642334856

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

SP - 435

EP - 450

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings

PB - Springer Verlag

T2 - 2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012

Y2 - 24 September 2012 through 28 September 2012

ER -

General algorithms for mining closed flexible patterns under various equivalence relations

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this