关联规则

关联规则算法目录基本概念及理论Apriori(先验)算法改进Apriori算法FP-Tree算法关联规则(AssociationRuleMining):最早是由Agrawal、R.Srikant提出（1994）发现事务数据库、关系数据或其它信息库中项或数据对象集合间的频繁模式,关联,相关,或因果关系结构频繁模式:在数据库中频繁出现的模式(项集,序列等)应用:发现数据中的规律性购物篮数据分析,交叉销售,分类设计,销售活动分析Web日志(点击流)分析,DNA序列分析等基本概念及理论支持度support规则AB在数据库D中具有支持度S，表示S是D中事务同时包含AB的百分比，它是概率P(AB)置信度confidence规则AB具有置信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P(B|A)，即：阈值，在事务数据库中找出有用的关联规则，需要由用户确定两个阈值：最小支持度阈值(min_sup)和最小置信度阈值(min_conf)强规则,同时满足最小支持度阈值和最小置信度阈值的规则|D||AB|P(AB)B)(AS|A||AB|)|()BA(ABPC基本概念及理论项集，项的集合称为项集(Itemset),包含k个项的项集称之为k-项集频繁项集L,项集L的相对支持度满足预定义的最小支持度阈值，如频繁K-项集的集合通常记作LK同时满足最小支持度（min_sup）和最小置信度（min_conf）的规则称之为关联规则，即闭项集,如果不存在真超项集Y使得Y与X在D中有相同的支持度计数，则X在D中是闭的.极大闭项集,如果X是频繁的，且不存在超项集Y使得X属于Y,并且Y在D中是频繁的.min_confB)(Amin_supB)(ACS且基本概念及理论提升度lift在已知某规则先验概率的情况下，某规则的提升度被定义为置信度和该先验概率的比率值。𝑙𝑖𝑓𝑡𝐴→𝐵值1，A与B负相关（互斥），值=1时A与B独立，值1时A与B正相关。例：假设体育类用品零售商调查了10000名顾客在购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则：篮球足球（支持度＝40%，置信度为66%），这条规则其实是错误的，因为购买足球的比例是75%，甚至大于66%其它：𝝌2分析、全置信度、最大置信度、Kulcynski和余弦等度量进行模式评估基本概念及理论𝑙𝑖𝑓𝑡𝐴→𝐵=𝐶(𝐴→𝐵)𝑃(𝐵)=𝑃(𝐴∪𝐵)𝑃𝐴𝑃(𝐵)𝑙𝑖𝑓𝑡篮球→足球=0.40.6∗0.75=0.891相关分析基本思想：使用一种称作逐层搜索的迭代方法，K-项集用于探索(K＋1)-项集。首先找出频繁1-项集的集合记为L1，L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去直到不能找到频繁K-项集LK。找每个LK需要一次数据库扫描。最后由频繁K－项集可直接产生强关联规则。过程分为两步：第一步：识别所有的频繁K-项集，并统计其频率;第二步：由频繁K-项集产生强关联规则。依据搜索到的频繁K-项集，导出满足给定阈值条件的关联规则。Apriori(先验)算法性质先验性质：频繁项集的所有非空子集都是频繁项集非频繁项集的所有超集都是非频繁项集（反单调性）例：如果｛啤酒，尿布，坚果｝是一个频繁的，则其子集｛啤酒，尿布｝、｛啤酒，坚果｝、｛尿布，坚果｝都是频繁的;如果｛啤酒，坚果｝是非频繁项集，则｛啤酒，尿布，坚果｝也是非频繁的.Apriori(先验)算法1.连接步：为找LK，通过LK-1与自己连接产生候选K-项集的集合。该候选K-项集的集合记为CK，CK中包含2K个可能的项集。从LK-1中取出f1和f2，fj[j]表示fj的第j项。如果两者的前（k-2）个项相同(如果f1[1]=f2[1]∧f1[2]=f2[2]∧…∧f1[k-2]=f2[k-2]∧f1[k-1]f2[k-1],则LK-1的元素f1和f2是可以连接的)，则进行连接f1⊕f2形成:{f1[1],f1[2],…,f1[k-2],f1[k-1],f2[k-1]}。L3={abc,abd,acd,ace,bcd}Self-joining:L3⊕L3abcdfromabcandabdacdefromacdandace例：Apriori(先验)算法2.剪枝步：Ck是Lk的超集，它的成员可以是频繁的，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选k-项集的计数，将计数值≥最小支持度计数的所有候选k-项集确定到Lk中。然而，Ck可能很大，这样所涉及到的计算量就很大。这时使用Apriori性质：如果一个候选k-项集的（k-1）-项集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除。Apriori(先验)算法例：L3={abc,abd,acd,ace,bcd}Pruning:acdeisremovedbecauseadeisnotinL3C4={abcd}例：设有一个Electronics的事务数据库(如图1示)。数据库中有9个事务，即｜D｜＝9。Apriori假定事务中的项按字典次序存放。我们使用图2解释Apriori算法寻找D中的频繁项集。TID项ID的列表T100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3（图1）Apriori(先验)算法项集支持度计数｛I1｝｛I2｝｛I3｝｛I4｝｛I5｝67622C1比较候选支持度计数与最小支持度计数扫描D，对每个候选计数项集支持度计数｛I1｝｛I2｝｛I3｝｛I4｝｛I5｝67622项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1产生候选C2项集支持度计数｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝4412422010扫描D，对每个候选计数C2项集支持度计数｛I1，I2｝｛I1，I3｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝442422比较候选支持度计数与最小支持度计数L2最小支持度为20%(计数为2)项集｛I1，I2，I3｝｛I1，I2，I5｝项集支持度计数｛I1，I2，I3｝｛I1，I2，I5｝22项集支持度计数｛I1，I2，I3｝｛I1，I2，I5｝22由L2产生候选C3C3C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数(图2续）L3L2⊕L2＝｛I1，I2，I3｝｛I1，I2，I5｝｛I1，I3，I5｝｛I2，I3，I4｝｛I2，I3，I5｝｛I2，I4，I5｝频繁项集｛I1，I2，I5｝产生的规则：子集：｛I1，I2｝,｛I1，I5｝,｛I2，I5｝,｛I1｝,｛I2｝,｛I5｝规则：｛I1，I2｝→I5，confidence=2/4=50%I1→｛I2，I5｝confidence=2/6=33%｛I1，I5｝→I2，confidence=2/2=100%I2→｛I1，I5｝confidence=2/7=29%｛I2，I5｝→I1，confidence=2/2=100%I1→｛I2，I5｝confidence=2/2=100%Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈:1．多次扫描事务数据库，需要很大的I/O负载对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁项集包含10个项的话，那么就至少需要扫描事务数据库10遍2．可能产生庞大的侯选集由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战Apriori(先验)算法改进Apriori:基本思想•减少事务数据库的扫描遍数•压缩候选数量•便于候选计数改进算法：1.基于散列技术（散列项集到对应的桶中）2.划分（为找候选集划分数据）3.事务压缩（压缩进一步迭代扫描的事务数）4.抽样（对给定数据的一个子集上挖掘）5.动态项集计数（在扫描的不同点添加候选项集）改进Apriori算法1.散列该算法由Park等在1995年提出。基本思想：当扫描数据库中每个事务，由C1中的候选1项集产生频繁1项集L1时，对每个事务产生所有的2项集，将它们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁2项集，可从候选2项集中删除，这样就可大大压缩了要考虑的2项集。改进Apriori算法桶地址0123456桶计数2242244桶内容{I1,I4}{I3,I5}{I1,I5}{I1,I5}{I2,I3}{I2,I3}{I2,I3}{I2,I3}{I2,I4}{I2,I4}{I2,I5}{I2,I5}{I1,I2}{I1,I2}{I1,I2}{I1,I2}{I1,I3}{I1,I3}{I1,I3}{I1,I3}H2由散列函数H（x,y）=[(orderofx)*10+(orderofy)]mod7创建散列表H22.划分D中事务将D划分成n部分找出局部中每一部分的频集(1次扫描)结合局部频集形成候选项集在候选项集中找出全局频集(1次扫描)D中频集第1遍第2遍通过划分挖掘项集在D中是频繁的,它必须至少在D的一个划分中是频繁的扫描1:划分数据库,并找出局部频繁模式扫描2:求出全局频繁模式改进Apriori算法3.事务压缩不包含任何K-项集的事务，不可能包含任何（K+1）-项集，可对这些事务加上删除标志,扫描数据库时不再考虑。改进Apriori算法基本思想是在给定数据的一个子集挖掘。先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。缺点：产生的结果不精确。4.抽样5.动态项集计数动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。思想:频繁模式增长递归地增长频繁模式借助模式和数据库划分，将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树方法对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树对每个新创建的条件FP-树重复上述过程直至结果FP-树为空,或者它仅包含一个单一路径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式FPGrowth算法步骤：按Apriori算法，扫描数据库一次生成1-频繁项目集，并按频度降序排序，放入L列表中创建FP-树的根,标注其为NULL对D中的每个事务进行以下操作:扫描数据库一次，当得到数据库的一个事务时，就把其中的项按L表中的次序排列，然后通过递归实现FP-Tree的增长FPGrowth算法频繁1-项集最小支持度为20%(计数为2)TIDItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2事务数据库支持度计数频繁1-项集FPGrowth算法ItemsetSupportcou