Abstract
Finding interesting patterns is a challenging task in data mining. Constraint based mining is a well-known approach to this, and one for which constraint programming has been shown to be a well-suited and generic framework.
Dominance programming has been proposed as an extension that can capture an
even wider class of constraint-based mining problems, by allowing to compare
relations between patterns. In this paper, in addition to specifying a dominance
relation, we introduce the ability to specify an incomparability condition. Using
these two concepts we devise a generic framework that can do a batch-wise search
that avoids checking incomparable solutions. We extend the ESSENCE language
and underlying modelling pipeline to support this. We use generator itemset mining problem as a test case and give a declarative specification for that. We also
present preliminary experimental results on this specific problem class with a CP
solver backend to show that using the incomparability condition during search
can improve the efficiency of dominance programming and reduces the need for
post-processing to filter dominated solutions.
Dominance programming has been proposed as an extension that can capture an
even wider class of constraint-based mining problems, by allowing to compare
relations between patterns. In this paper, in addition to specifying a dominance
relation, we introduce the ability to specify an incomparability condition. Using
these two concepts we devise a generic framework that can do a batch-wise search
that avoids checking incomparable solutions. We extend the ESSENCE language
and underlying modelling pipeline to support this. We use generator itemset mining problem as a test case and give a declarative specification for that. We also
present preliminary experimental results on this specific problem class with a CP
solver backend to show that using the incomparability condition during search
can improve the efficiency of dominance programming and reduces the need for
post-processing to filter dominated solutions.
| Original language | English |
|---|---|
| Title of host publication | The 18th workshop on Constraint Modelling and Reformulation (ModRef 2019), Proceedings |
| Number of pages | 14 |
| Publication status | Published - 30 Sept 2019 |
| Event | 25th International Conference on Principles and Practice of Constraint Programming (CP 2019) - Stamford, United States Duration: 30 Sept 2019 → 4 Oct 2019 Conference number: 25 http://cp2019.a4cp.org |
Conference
| Conference | 25th International Conference on Principles and Practice of Constraint Programming (CP 2019) |
|---|---|
| Abbreviated title | CP 2019 |
| Country/Territory | United States |
| City | Stamford |
| Period | 30/09/19 → 4/10/19 |
| Internet address |
Keywords
- Constraint programming
- Constraint modelling
- Data mining
- Itemset mining
- Pattern mining
- Dominance programming