数据挖掘原理、算法及应用第3章关联规则挖掘

《数据挖掘原理、算法及应用第3章关联规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章　关联规则挖掘3.1基本概念3.2关联规则挖掘算法3.3Apriori改进算法3.4不候选产生挖掘频繁项集3.5使用垂直数据格式挖掘频繁项集3.6挖掘闭频繁项集3.7挖掘各种类型的关联规则3.8相关分析3.9基于约束的关联规则3.10矢量空间数据库中关联规则的挖掘3.1基本概念交易数据库又称为事务数据库，尽管它们的英文名词一样，但是事务数据库更具有普遍性。例如，病人的看病记录、基因符号等用事务数据库更贴切。因此，下面的叙述更多使用事务数据库这一名词，而不用交易数据库这个名词。一个事务数据库中的关联规则挖掘可以描述如下：设I={i1,i2,…,im}是一个

2、项目集合，事务数据库D={t1,t2,…,tn}是由一系列具有惟一标识的TID事务组成。每一个事务ti(i=1,2,…,n)都对应I上的一个子集。定义3.1设I1I，项目集(Itemsets)I1在数据集D上的支持度(Support)是包含I1的事务在D中所占的百分比，即式中：

3、

4、·

5、

6、表示集合中元素数目。(3.1)定义3.2对项目集I，在事务数据库D中所有满足用户指定的最小支持度(Minsupport)的项目集，即不小于Minsupport的I的非空子集，称为频繁项目集(FrequentItemsets)或大项目集(LargItemsets)。定义3.3

7、一个定义在I和D上，形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来定义的。所谓规则的可信度，是指包含I1和I2的事务数与包含I1的事务数之比，即(3.2)定义3.4D在I上满足最小支持度和最小置信度(Minconfidence)的关联规则称为强关联规则(StrongAssociationRules)。通常所说的关联规则一般是指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。(1)发现频繁项目集：通过用户给定的

8、最小支持度，寻找所有频繁项目集，即满足支持度Support不小于Minsupport的所有项目子集。发现所有的频繁项目集是形成关联规则的基础。(2)生成关联规则：通过用户给定的最小可信度，在每个最大频繁项目集中，寻找置信度不小于Minconfidence的关联规则。3.2关联规则挖掘算法3.2.1项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集空间理论。理论的核心为：频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。这个理论一直作为经典的数据挖掘理论被应用。定理3.1如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目

9、集。证明设X是一个项目集，事务数据库D中支持X的元组(记录)数为S。设X的任一非空子集YX，事务数据库D中支持Y的元组(记录)数为S1。根据项目集支持度的定义，很容易知道支持X的元组一定支持Y，所以S1≥S，即support(Y)≥support(X)按假设，项目集X是频繁项目集，即support(X)≥minsupport所以support(Y)≥support(X)≥minsupport，因此Y是频繁项目集。定理3.2如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明设事务数据库D中支持X的元组数为S。设X的任一超

10、集ZX，事务数据库D中支持Z的元组数为S2。根据项目集支持度的定义，很容易知道支持Z的元组一定支持X，所以S2≤S，即support(Z)≤support(X)按假设，项目集X是非频繁项目集，即support(X)

11、是在此基础上进行改进的。3.2.2经典的发现频繁项目集算法Apriori算法是R.Agrawal和R.Strikant于1994年提出的布尔关联规则挖掘频繁项集的原创性算法。算法的基本思想：基于频繁项目集性质的先验知识，使用由下到上逐层搜索的迭代方法，k项集用于搜索k+1项集。首先，扫描数据库，统计每一个项发生的数目，找出满足最小值支持度的项，找出频繁1项集，计作L1；然后，基于L1找出频繁2项集的集合L2，基于L2找出频繁3项集的集合L3，如此下去，直到不能找到频繁k项集Lk。找每一个Lk需要一次数据库全扫描。Apriori算法的核心由连接步和剪枝步组成。

12、(1)连接步：为找频繁