TY - GEN
T1 - On Minimal and Maximal High Utility Itemsets Mining using Propositional Satisfiability
AU - Hidouri, Amel
AU - Jabbour, Said
AU - Dlala, Imen Ouled
AU - Raddaoui, Badran
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - Computing high utility motifs is a fundamental data mining method for discovering useful itemsets yielding high utility values. Minimal and maximal high utility itemsets are two examples of compact representations used to reduce the output size due to the large and incomprehensible number of patterns. In this paper, we present a novel method for mining minimal and maximal high utility itemsets using propositional satisfiability. First, we show that minimal and maximal high utility patterns are X-minimal models of a CNF formula. Then, to improve the scalability issue of our method, we harness a decomposition paradigm that splits the transaction database into smaller and independent transaction sub-bases, allowing an efficient enumeration of minimal and maximal high utility itemsets. Finally, through extensive evaluation studies on various real-world datasets, we demonstrate that our approach is very competitive w.r.t. to the state-of-the-art specialized solutions.
AB - Computing high utility motifs is a fundamental data mining method for discovering useful itemsets yielding high utility values. Minimal and maximal high utility itemsets are two examples of compact representations used to reduce the output size due to the large and incomprehensible number of patterns. In this paper, we present a novel method for mining minimal and maximal high utility itemsets using propositional satisfiability. First, we show that minimal and maximal high utility patterns are X-minimal models of a CNF formula. Then, to improve the scalability issue of our method, we harness a decomposition paradigm that splits the transaction database into smaller and independent transaction sub-bases, allowing an efficient enumeration of minimal and maximal high utility itemsets. Finally, through extensive evaluation studies on various real-world datasets, we demonstrate that our approach is very competitive w.r.t. to the state-of-the-art specialized solutions.
KW - Data Mining
KW - High Utility Itemsets
KW - Minimal Models
KW - Propositional Satisfiability (SAT)
KW - Symbolic Artificial Intelligence
U2 - 10.1109/BigData52589.2021.9671422
DO - 10.1109/BigData52589.2021.9671422
M3 - Conference contribution
AN - SCOPUS:85125318967
T3 - Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021
SP - 622
EP - 628
BT - Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021
A2 - Chen, Yixin
A2 - Ludwig, Heiko
A2 - Tu, Yicheng
A2 - Fayyad, Usama
A2 - Zhu, Xingquan
A2 - Hu, Xiaohua Tony
A2 - Byna, Suren
A2 - Liu, Xiong
A2 - Zhang, Jianping
A2 - Pan, Shirui
A2 - Papalexakis, Vagelis
A2 - Wang, Jianwu
A2 - Cuzzocrea, Alfredo
A2 - Ordonez, Carlos
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Conference on Big Data, Big Data 2021
Y2 - 15 December 2021 through 18 December 2021
ER -