Computational aspects of mining maximal frequent patterns

被引：19

作者：

Yang, Guizhen ^{[1
]}

机构：

[1] SRI Int, Ctr Artificial Intelligence, Menlo Pk, CA 94025 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 362卷 / 1-3期

关键词：

data mining; complexity; maximal frequent patterns; #P-complete;

D O I：

10.1016/j.tcs.2006.05.029

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we study the complexity-theoretic aspects of mining maximal frequent patterns, from the perspective of counting the number of all distinct solutions. We present the first formal proof that the problem of counting the number of maximal frequent itemsets in a database of transactions, given an arbitrary support threshold, is #P-complete, thereby providing theoretical evidence that the problem of mining maximal frequent itemsets is NP-hard. We also extend our complexity analysis to other similar data mining problems that deal with complex data structures, such as sequences, trees, and graphs. We investigate several variants of these mining problems in which the patterns of interest are subsequences, subtrees, or subgraphs, and show that the associated problems of counting the number of maximal frequent patterns are all either #P-complete or #P-hard. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：63 / 85

页数：23