论文标题
项目集挖掘中三个核心问题的计算复杂性
Computational Complexity of Three Central Problems in Itemset Mining
论文作者
论文摘要
项目集挖掘是知识发现中研究最多的任务之一。在本文中，我们分析了三个中央项目集挖掘问题的计算复杂性。我们证明，在头部给定物品的挖掘自信规则是NP-HARD。我们证明采矿高公用项目集是NP-HARD。我们最终证明，一旦用户可以对他们感兴趣的商品集规定限制，最大或封闭的物品集就会束缚。
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.
