第五章：关联规则方法

1、第五章第五章关联规则方法关联规则方法李晋宏北方工业大学信息工程学院北方工业大学信息工程学院北方工业大学信息工程学院北方工业大学信息工程学院内容内容关联规则的概念和分类Apriori算法FP-Growth算法利用SQL Server 2005进行关联规则挖掘北方工业大学信息工程学院北方工业大学信息工程学院概述概述数据挖掘中许多常用的传统模式发现技术，如决策树、分类规则和聚类技术，都属于机器学习领域的研究成果关联规则的出现，极大扩展了数据挖掘的研究从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究领域中的一个热点北方工业大学信息工程学院北方工业大学信息工程学院概述概述由于实际应用目标的差异

2、，在关联规则大的理论框架下，有许多面向应用目标的理论和方法等待探索和创新北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则（association rules）概念产生于1993年，目的是为了寻找大量商务数据库中项集之间的有趣联系由Agrawal 、Imielinski、Swami提出北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的概念关联规则：用来发现在同一事件中出现的不同项的相关性，即找出事务中频繁发生的项或属性的所有子集，以及项目之间的相互关联性北方工业大学信息工程学院北方工业大学信息工程学院

3、关联规则的概念和分类关联规则的概念和分类关联规则的概念D：事务数据库I：项目(item)集合I=i1,i2,im，其中， i1,i2,im为数据库中的项目T：数据库中的事务（transaction）X：项集(itemset)，即项目的集合北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的概念k项集：包含k个项目的集合支持度s(X): 项集X的支持度，表示数据库中包含项集X的交易数据的条数频繁项集：也称为频繁模式，指支持度大于用户指定的最小支持度的项集频繁k-项集：长度为k的频繁项集北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分

4、类关联规则的概念和分类关联规则的概念设项目集合I=i1,i2,im由m个不同的项目组成，D为事务数据库，D中的每一个事务T是I的一个子集，即T I一个项目的集合称为项集包含k个项目的集合称为k项集项集X的支持度，记为s(X),表示包含该项集的交易数据的条数北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的概念如果一个项集的支持度大于用户指定的最小支持度(min_sup)，称它是频繁的长度为k的频繁项集称为频繁k-项集关联规则是形如A=B的蕴涵式，其中A I，B I，并且AB=O北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关

5、联规则的概念和分类关联规则的概念规则A=B的支持度s(A=B)定义为D中包含AB的事务所占的百分比，表示项集AB在D中出现的概率 | T: AB |S(A=B)=- |D|北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的概念规则A=B的置信度c(min_con)定义为D中包含项集AB的事务数和包含项集A的事务数的比值，表示当项集A出现时，项集B出现的概率 s(AB)c(A=B)=- s(A)置信度大于用户指定的最小置信度值的规则是可信的北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的概念关联规则

6、挖掘的任务：找到事务数据库D中支持度和置信度分别满足用户指定的最小支持度min_sup和最小置信度min_con的规则A=B 找出D中所有的频繁项集 从频繁项集中产生关联规则北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的分类基于规则中处理的变量类别 布尔型：离散的，可枚举的，种类化的 性别=“男”=职业=“网络工程师” 数值型：原始的数据 性别=“男”=收入=3500北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的分类基于规则中数据的抽象层次 单层：变量不考虑层次 三星数码相机=三星手机 多层

7、：考虑数据的多层性 数码相机=三星手机北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的分类基于规则中涉及的数据维数 单维：只涉及数据的一个维/单个属性 啤酒=尿布 多维：处理多个属性之间的关系 性别=“男”=职业=“网络工程师”北方工业大学信息工程学院北方工业大学信息工程学院关联规则的概念和分类关联规则的概念和分类关联规则的分类基于模式与规则之间的相互关系 完全频繁模式挖掘 最大频繁模式挖掘 闭合频繁模式挖掘挖掘研究基础（一维、单层、布尔）北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法概述一维单层布尔型关联规则产生候选项

8、集不产生候选项集Apriori算法FP-Growth北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法概述Apriori性质：频繁项集的所有非空子集也都必须是频繁的这是频繁项集的先验知识可以减少候选频繁项集的数量北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法概述Step1：通过迭代，检索出源数据中的所有频繁项集，即支持度不低于用户设定阈值的项集Step2：利用第一步检索出的频繁项集构造出满足用户最小置信度的规则北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集算法 k=1 由(k-1)项集产生候选k-项集 依据Apri

9、ori性质，对候选k-项集进行剪枝 扫描数据库，统计各个项目的出现次数 依据最小支持度，由候选k-项集中产生频繁k-项集 K=k+1 转,直到k=n为止北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集约定Ck：第k次迭代产生的候选项集为候选k项集Lk：第k次迭代产生的频繁项集为频繁k项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集1.求频繁1项集L1l 以项目集合I作为候选1项集C1，扫描数据库1次，统计各个项目的出现次数，根据设定的最小支持度得出频繁1

10、项集L1 北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集2.求频繁k+1项集Lk+1l对前k-1个项目相同的每两个k频繁模式执行join操作，得到候选k+1项集Ck+1l根据Apriori性质，对Ck+1进行剪枝北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集3.扫描数据库一遍，确定每个cCk+1的支持计数，据此得出频繁k+1项集Lk+1北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集分析每产生第K级的频繁项集，需要扫描数据库1次(计算支持度)如何从k频繁项集得到候选k+1项集？ a,b+a

11、,c=a,b,c a,b+b,c=通过k次迭代，可以产生长度从1到k的所有频繁项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例数据库D事务T项目I1、 I2、 I3、 I4、 I5项目集合I=I1，I2，I3，I4，I5用户要求的最小支持度阈值s=20%规则置信度c=60%北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例1.第一次迭代，产生频繁1-项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例2.第二次迭代，产生频繁2-项集l 在Apriori算法中，使用L1*L1

12、产生候选项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例2.第二次迭代，产生频繁2-项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例3.第三次迭代，产生频繁3-项集l I1，I2，I3l I1，I2，I5l I1，I3，I5l I2，I3，I4l I2，I3，I5l I2，I4，I5l I3，I4，I5北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例3.第三次迭代，产生频繁3-项集北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法产生频繁项集的实例

13、l分析l 先进行Apriori剪枝，再通过支持度删除l 负边界：所有非频繁，但符合Apriori性质的候选项集的集合l 负边界中的项集是非频繁的，但每个项集的所有子集都是频繁的l 负边界在改进算法中更为重要北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法从频繁项集产生关联规则1.计算每一个频繁项集的子集l 如I1，I2，I5l I1，I2和I5l I1，I5和I2l I2，I5和I12.得到规则l I1，I2 I5l I1，I5 I2l I2，I5 I1北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法从频繁项集产生关联规则3.计算规则的置信度4.置信

14、度c大于给定的阈值的规则为强关联规则北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法北方工业大学信息工程学院北方工业大学信息工程学院Apriori算法算法从频繁项集产生关联规则l分析l 如何拆分并产生频繁项集的子集？l a,b,c,dl a,b,c dl a b,c,d ?l a,b c,d ?l 并不是所有被挖掘出的强关联规则都有意义北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法概述FP-tree频繁模式树为了存储与频繁模式相关的关键信息而设计的一棵压缩的、扩展前缀树结构FP-Growth算法构成FP-tree从FP-tree得到频繁模式北方

15、工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法概述构造FP-tree扫描一遍数据库统计事务中所有项的出现次数按照出现次数的大小排序形成一个列表列表中保存了项目在树中出现位置的指针扫描第二遍数据库构建FP-tree根结点为空其余结点为数对（项目名：支持数）同一项目在树中的多次出现形成一个结点链北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法概述不产生候选项集比Apriori大约快一个数量级不擅长处理长模式、稀疏数据构建FP-tree的时间和空间代价较高在应用领域上有所限制是最杰出的关联规则挖掘算法北方工业大学信息工程学院北方工业大学信息工程学院F

16、P-Growth算法算法FP-Growth算法计算过程FP-tree的构建过程1. 扫描事务数据库一次，得到频繁项的集合F及其支持度，对F按支持度降序排列，生成频繁项列表L12. 创建FP-tree的根结点T，以null标记，对于数据库中的每条事务，执行操作353. 将事务中的频繁项目按L1中的次序排列，排序后的频繁项表表示为p|P,其中p是第一个频繁项，P是剩余项目列表北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法FP-Growth算法计算过程FP-tree的构建过程4. 调用insert-tree(p|P,T)，即由根节点T开始，如果T有子结点N满足N.item-name=p.item-name则结点N的计数增1；否则创建一个新结点N，将其计数置为1，连接到其父结点T，并且通过结点链结构将其连接到具有相同item-name的结点5. 如果频繁项表P非空，递归地调用 insert-tree (p|P,T)北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法FP-Growth算法计算过程FP-Growth: 从FP-tree挖掘频繁模式北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法FP-Growth算法示例北方工业大学信息工程学院北方工业大学信息工程学院FP-Growth算法算法FP-Grow