Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations
Abstract
This article introduces the problem of searching locally optimal patterns within a set of patterns constrained by some anti-monotonic predicate: given some pattern scoring function, a locally optimal pattern has a maximal (or minimal) score locally among neighboring patterns. Some instances of this problem have produced patterns of interest in the framework of knowledge discovery since locally optimal patterns extracted from datasets are very few, informative and non-redundant compared to other pattern families derived from frequent patterns. This article then introduces the concept of variation consistency to characterize pattern functions and uses this notion to propose GALLOP, an algorithm that outperforms existing algorithms to extract locally optimal itemsets. Finally it shows how GALLOP can generically be applied to two classes of scoring functions useful in binary classification or clustering pattern mining problems.
Cite
Text
Pennerath. "Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15939-8_3Markdown
[Pennerath. "Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/pennerath2010ecmlpkdd-fast/) doi:10.1007/978-3-642-15939-8_3BibTeX
@inproceedings{pennerath2010ecmlpkdd-fast,
title = {{Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations}},
author = {Pennerath, Frédéric},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {34-49},
doi = {10.1007/978-3-642-15939-8_3},
url = {https://mlanthology.org/ecmlpkdd/2010/pennerath2010ecmlpkdd-fast/}
}