Computational Complexity of Three Central Problems in Itemset Mining

2020-12-04 · Christian Bessiere, Mohamed-Bachir Belaid, Nadjib Lazaar

Itemset mining is one of the most studied tasks in knowledge discovery. In this paper we analyze the computational complexity of three central itemset mining problems. We prove that mining confident rules with a given item in the head is NP-hard. We prove that mining high utility itemsets is NP-hard. We finally prove that mining maximal or closed itemsets is coNP-hard as soon as the users can specify constraints on the kind of itemsets they are interested in.

📄 PDF Abstract BibTeX arXiv:2012.02619

Code (0)

등록된 구현이 없습니다.

Decomposable Families of Itemsets

2020-06-16 · Nikolaj Tatti, Hannes Heikinheimo

The problem of selecting a small, yet high quality subset of patterns from a larger collection of itemsets has recently attracted lot of research. Here we discuss an approach to this problem using the notion of decomposa…

Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace

2012-12-09 · Georg Gottlob

The monotone duality problem is defined as follows: Given two monotone formulas f and g in iredundant DNF, decide whether f and g are dual. This problem is the same as duality testing for hypergraphs, that is, checking w…

Problem Decomposition

An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints

2022-03-21 · Soufia Bennai, Kamala Amroun, Samir Loudni, Abdelkader Ouali

Constraint Programming is a powerful paradigm to model and solve combinatorial problems. While there are many kinds of constraints, the table constraint is perhaps the most significant-being the most well-studied and has…

Generic Itemset Mining Based on Reinforcement Learning

2021-05-17 · Kazuma Fujioka, Kimiaki Shirahama

One of the biggest problems in itemset mining is the requirement of developing a data structure or algorithm, every time a user wants to extract a different type of itemsets. To overcome this, we propose a method, called…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Vocal Bursts Type Prediction

Hybrid ASP-based Approach to Pattern Mining

2018-08-22 · Sergey Paramonov, Daria Stepanova, Pauli Miettinen

Detecting small sets of relevant patterns from a given dataset is a central challenge in data mining. The relevance of a pattern is based on user-provided criteria; typically, all patterns that satisfy certain criteria a…

Graph Mining