文档介绍：第3章关联规则挖掘
基本概念
关联规则挖掘算法
Apriori改进算法
不候选产生挖掘频繁项集
使用垂直数据格式挖掘频繁项集
挖掘闭频繁项集
挖掘各种类型的关联规则
相关分析
基于约束的关联规则
矢量空间数据库中关联规则的挖掘
基本概念
交易数据库又称为事务数据库, 尽管它们的英文名词一样, 但是事务数据库更具有普遍性。例如,病人的看病记录、基因符号等用事务数据库更贴切。因此,下面的叙述更多使用事务数据库这一名词,而不用交易数据库这个名词。
一个事务数据库中的关联规则挖掘可以描述如下:
设I= {i1, i2, …, im} 是一个项目集合, 事务数据
库D= {t1, t2, …, tn} 是由一系列具有惟一标识的TID事务组成。每一个事务ti (i=1, 2, …, n)都对应I上的一个子集。
设I1 I,项目集(Itemsets)I1在数据集D上的支持度(Support)是包含I1的事务在D中所占的百分比,即
式中: ||·||表示集合中元素数目。
()
对项目集I,在事务数据库D中所有满足用户指定的最小支持度(Minsupport) 的项目集,即不小于Minsupport的I的非空子集,称为频繁项目集(Frequent Itemsets) 或大项目集(Larg Itemsets)。
一个定义在I和D上,形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来定义的。所谓规则的可信度,是指包含I1和I2的事务数与包含I1的事务数之比, 即
()
D在I上满足最小支持度和最小置信度(Minconfidence)的关联规则称为强关联规则(Strong Association Rules)。
通常所说的关联规则一般是指强关联规则。
一般地,给定一个事务数据库,关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。
如果项目集X是频繁项目集,那么它的所有非空子集都是频繁项目集。
证明设X是一个项目集,事务数据库D中支持X的元组(记录)数为S。设X的任一非空子集YX,事务数据库D中支持Y的元组(记录)数为S1。
根据项目集支持度的定义,很容易知道支持X的元组一定支持Y,所以S1≥S, 即
support (Y)≥support (X)
按假设,项目集X是频繁项目集, 即
support(X)≥minsupport
所以support (Y)≥support (X)≥minsupport, 因此Y是频繁项目集。
如果项目集X是非频繁项目集,那么它的所有超集都是非频繁项目集。
证明设事务数据库D中支持X的元组数为S。设X的任一超集Z X, 事务数据库D中支持Z的元组数为S2。
根据项目集支持度的定义, 很容易知道支持Z的元组一定支持X,所以S2≤S,即
support(Z)≤support(X)
按假设, 项目集X是非频繁项目集, 即
support(X)<minsupport
所以support (Z)≤support (X)<minsupport,因此Z不是频繁项目集。
1993年,Agrawal等人在提出关联规则概念的同时,给出了相应的挖掘算法AIS,但性能较差。1994年,他们依据上述两个定理,提出了著名的Apriori算法, Apriori算法至今仍然作为关联规则挖掘的经典算法,其他算法均是在此基础上进行改进的。