权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Studies on Time Complexity for Computing Association Rules in Data Mining

数据挖掘中关联规则计算的时间复杂度研究

基本信息

批准号：
13680446
负责人：
ITO Minoru
金额：
$ 1.79万
依托单位：
NARA INSTITUTE OF SCIENCE AND TECHNOLOGY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680446/
关键词：
Data Mining Association Rule NP-complete problem NP完全

项目摘要

1. Computing association rules for market basket database is one of the most fundamental problems in data mining. An association rule is a statement of the form X⇒Y, whose intuitive meaning is that if a customer buys all the items in X, then he is also likely to buy all the items in Y. In order that the association rule is meaningful, it is necessary that (a) the itemset X∪Y is large, (b) the rule is confident, and (c) the left side Y contains enough items. The algorithm for computing association rules consists of the two parts: first, computing a large itemset Z, and then dividing the set Z into X and Y such that X⇒Y is meaningful.2. We introduced a rare itemset that is a dual concept for a large itemset, and proved that it is NP-complete to decide if there is a large itemset whose size is smaller than a given size.3. By transforming the rare itemset problem above into a problem for deciding if a meaningful association rule can be obtained from a given large itemset, we proved that the problem for computing a meaningful association rule is NP-complete.4. We obtained a sufficient condition to compute a rare itemset in polynomial time.5. Using the sufficient condition above, we obtained a subclass of databases in which a meaningful association rule can be computed in polynomial time.

1.购物篮数据库关联规则的计算是数据挖掘中最基本的问题之一。关联规则是一种形式为X Y的语句，其直观含义是，如果客户购买X中的所有商品，那么他也可能购买Y中的所有商品。为了关联规则是有意义的，需要（a）项目集X × Y是大的，（B）规则是可信的，以及（c）左侧Y包含足够的项目。计算关联规则的算法由两部分组成：首先计算一个大的项目集Z，然后将集合Z分成X和Y，使得X ≠ Y是有意义的.我们引入了一个稀疏项集，它是一个大项集的对偶概念，并证明了判定是否存在一个小于给定大小的大项集是NP完全的.通过将上述的稀有项集问题转化为一个判定从给定的大项集中是否能得到有意义的关联规则的问题，证明了计算有意义的关联规则的问题是NP-完全的。得到了在多项式时间内计算稀有项集的一个充分条件.利用上述充分条件，我们得到了一个数据库子类，其中一个有意义的关联规则可以在多项式时间内计算。