大数据应用人才培养系列教材 数据挖掘基础 刘 鹏 张 燕 总主编 陶建辉 主编 姜才康 副主编.

Presentation on theme: "大数据应用人才培养系列教材 数据挖掘基础 刘 鹏 张 燕 总主编 陶建辉 主编 姜才康 副主编."— Presentation transcript:

1 大数据应用人才培养系列教材 数据挖掘基础 刘 鹏 张 燕 总主编 陶建辉 主编 姜才康 副主编

2 第四章 关联规则 4.1 关联规则的基本概念 4.2 关联规则的挖掘过程 4.3 关联规则的Apriori算法
大数据应用人才培养系列教材 第四章　关联规则 4.1　关联规则的基本概念 4.2　关联规则的挖掘过程 4.3　关联规则的Apriori算法 4.4　关联规则的FP-Growth算法 习题

3 4.1 关联规则的基本概念 第四章 关联规则 关联规则概念最早是由Agrawal等人在1993年首先提出的，最初的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。Agrawal等人于1993年提出了关联规则挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。

4 4.1 关联规则的基本概念 第四章 关联规则 More 应用市场：市场货篮分析、交叉销售（Crossing Sale）、部分分类（Partial Classification）、金融服务（Financial Service），以及通信、互联网、电子商务 ······

5 4.1 关联规则的基本概念 4.1.1 基本概念 1）项（Item）、项集（Itemset）、k-项集与事务
第四章 关联规则 4.1.1 基本概念 1）项（Item）、项集（Itemset）、k-项集与事务 项：是指数据库中不可分割的最小单位。 项集：是指多个项的集合，其中，空集是指不包含任何项的项集。 k-项集：是指由k个项构成的项集组合。 事务：是指用户定义的一个数据库操作序列，这些操作序列是一个不可分割的工作单位。 2）频繁项集（Frequent Itemset） 频繁项集：是指在所有训练元组中同时出现的次数，超过人工定义的阈值的项集。在关联规则的挖掘过程中，一般只保留候选项集中满足支持度条件的项集，不满足条件的舍弃。

6 4.1 关联规则的基本概念 4.1.1 基本概念 3）极大频繁项集（Frequent Large Itemset）
第四章 关联规则 4.1.1 基本概念 3）极大频繁项集（Frequent Large Itemset） 极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。 4）支持度（Support） 支持度：是指项集在所有训练元组中同时出现的次数，因此，支持度可以表述为Support(X->Y) = |X U Y|/ |N|。其中，X，YN，X∩Y=Ф，|X U Y|表示集合X与Y在一个事务中同时出现的次数，|N|表示数据记录的总个数。 5）置信度（Confidence） 置信度可以表述为：Confidence (X->Y)= |X U Y|/ |X| = Support(X->Y) / Support（X），其中，X，YN，X∩Y=Ф，|X U Y|表示集合X与Y在一个事务中同时出现的次数，|X|表示X出现的总次数。

7 4.1 关联规则的基本概念 第四章 关联规则 4.1.2 关联规则定义 关联规则（Association rule）：指从事务数据库、关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。 关联分析（Association analysis）：用于发现隐藏在大型数据集中的令人感兴趣的联系。所发现的联系可以用关联规则或者频繁项集的形式表示。关联规则挖掘就是从大量的数据中挖掘出描述数据项之间相互联系的有价值的有关知识。

8 4.1 关联规则的基本概念 4.1.2 关联规则定义 一般地，关联规则挖掘问题可以划分成两个子问题： 1）发现频繁项目集
第四章 关联规则 4.1.2 关联规则定义 一般地，关联规则挖掘问题可以划分成两个子问题： 1）发现频繁项目集 通过用户给定的Minsupport，寻找所有频繁项目集，即满足Support不小于Minsupport的项目集。事实上，这些频繁项目集可能具有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频繁大项集的集合。这些频繁大项集是形成关联规则基础。 2）生成关联规则 通过用户给定的Minconfidence，在每个最大频繁项目项目集中，寻找Confidence不小于Minconfidence的关联规则。这两个子问题主要在4.3节中进行介绍。

9 4.1 关联规则的基本概念 4.1.3 关联规则分类 1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。
第四章 关联规则 4.1.3 关联规则分类 1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 3）基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。

10 第四章 关联规则 4.1 关联规则的基本概念 4.2 关联规则的挖掘过程 4.3 关联规则的Apriori算法
大数据应用人才培养系列教材 第四章　关联规则 4.1　关联规则的基本概念 4.2　关联规则的挖掘过程 4.3　关联规则的Apriori算法 4.4　关联规则的FP-Growth算法 习题

11 4.2 关联规则的挖掘过程 图1 项集的格 4.2.1 频繁项集产生
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.1 频繁项集产生 格结构（Lattice Structure）常常被用来枚举所有可能的项集。 图1 项集的格

12 4.2 关联规则的挖掘过程 4.2.2 频繁项集的产生及其经典算法
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.2 频繁项集的产生及其经典算法 格结构（Lattice Structure）常常被用来枚举所有可能的项集。 查找频繁项目集 经典的查找策略 基于精简集的查找策略 基于最大频繁项集的查找策略 按照挖掘的策略不同 经典的挖掘完全频繁项集方法 基于广度优先搜索策略的关联规则算法 基于深度优先搜索策略的算法 Apriori算法、DHP算法 FP-Growth算法、ECLAT算法COFI算法 与经典查找不同方法 基于精简集的方法 基于最大频繁项目集的方法 A-close算法 MAFIA算法、GenMax算法 DepthProject算法

13 4.2　关联规则的挖掘过程 第四章 关联规则 4.2.3 强关联规则 生成关联规则是指通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于Minconfidence的关联规则。 得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、...k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷举效率显然很低。 假如对于一个频繁项目集f，可以生成下面这样的关联规则： （f-β）->β

14 4.2　关联规则的挖掘过程 第四章 关联规则 4.2.4 关联规则评价标准 在某些特定情况下，仅凭支持度和置信度来衡量一条规则，是完全不够的，对于数据的筛选力度也不足。因此，需要介绍更多的判断强关联规则的评价标准，来满足实际需求。 支持度和置信度并不能过成功滤掉那些我们不感兴趣的规则，因此我们需要一些新的评价标准，下面介绍六中评价标准：相关性系数，卡方指数，全置信度、最大置信度、Kulc、cosine距离。

15 4.2 关联规则的挖掘过程 4.2.4 关联规则评价标准 1）相关性系数lift
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.4 关联规则评价标准 1）相关性系数lift 引入正相关和负相关的机制，对于不是正相关的商品规则，可以用相关性系数lift过滤掉。对于规则A->B或者B->A，lift(A,B)=P(A∩B)/(P(A)*P(B))，如果lift(A,B)>1表示A、B呈正相关，lift(A,B)<1表示A、B呈负相关，lift(A,B)=1表示A、B不相关（独立）。实际运用中，正相关和负相关都是我们需要关注的，而独立往往是我们不需要的，两个商品都没有相互影响也就是不是强规则，lift(A,B)等于1的情形也很少，一般只要接近于1，便认为是独立了。

16 4.2 关联规则的挖掘过程 4.2.4 关联规则评价标准 2）卡方系数
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.4 关联规则评价标准 2）卡方系数 卡方分布是数理统计中的一个重要分布，利用卡方系数我们可以确定两个变量是否相关。卡方系数的定义：

17 4.2 关联规则的挖掘过程 4.2.4 关联规则评价标准 4）最大置信度max_confidence
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.4 关联规则评价标准 3）全置信度all_confidence 全置信度的定义如下： all_confidence(A,B)=P(A∩B) / max{P(A),P(B)}=min{P(B|A),P(A|B)} =min{confidence(A->B),confidence(B->A)} 4）最大置信度max_confidence 最大置信度则与全置信度相反，求的不是最小的支持度而是最大的支持度，max_confidence(A,B) = max{confidence(A->B),confidence(B->A)}，不过感觉最大置信度不太实用。

18 4.2 关联规则的挖掘过程 4.2.4 关联规则评价标准 6）cosine距离
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.4 关联规则评价标准 5）Kulc Kulc系数本质上是对两个置信度做一个平均处理，公式为： kulc(A,B)=(confidence(A->B)+confidence(B->A))/2。 6）cosine距离 cosine(A,B)=P(A∩B)/sqrt(P(A)*P(B))=sqrt(P(A|B)*P(B|A)) = sqrt(confidence(A->B)*confidence(B->A))

19 第四章 关联规则 4.1 关联规则的基本概念 4.2 关联规则的挖掘过程 4.3 关联规则的Apriori算法
大数据应用人才培养系列教材 第四章　关联规则 4.1　关联规则的基本概念 4.2　关联规则的挖掘过程 4.3　关联规则的Apriori算法 4.4　关联规则的FP-Growth算法 习题

20 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——1概念 Apriori算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁1项集开始，采用频繁k项集搜索频繁k+1项集，直到不能找到包含更多项的频繁项集为止。 Apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：

21 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——2核心思想 Apriori算法的核心思想主要体现在两个方面，即其两个关键步骤： 1) 连接步 为了找到频繁k项集Lk，首先将Lk-1与自身连接，产生候选k项集Ck，Lk-1的元素是可连接的。

22 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——2核心思想 Apriori算法的核心思想主要体现在两个方面，即其两个关键步骤： 2) 剪枝步 候选k项集Ck是Lk的超集，因此，Ck成员即可为频繁项集也可不是频繁的，但所有的频繁项集都包括在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的(k-1)项集都不可能是频繁k项集的子集。因此，如果一个候选k项集的(k-1)项集不在Lk中，则该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。

23 4.3 关联规则的Apriori算法 4.2 关联规则的挖掘过程 频繁项集的产生及其经典算法之一——Apriori算法 性能瓶颈
4.2　关联规则的挖掘过程 4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——3步骤 生成频繁1项集L1 性能瓶颈 连接步 剪枝步 Apriori算法是一个多趟搜索算法 可能产生庞大的候选项集 生成频繁k项集Lk 重复步骤（2）～（4），直到不能产生新的频繁项集的集合为止，算法中止。

24 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——4算法描述 算法4-1 Apriori——发现频繁项目集 (1) L1 = {large 1-itemsets}; (2) FOR (k=2; Lk-1; k++) DO BEGIN (3) Ck=apriori-gen(Lk-1); // Ck 是k个元素的候选集 (4) FOR all transactions tD DO BEGIN (5) Ct=subset(Ck,t); // Ct是所有t包含的候选集元素 (6) FOR all candidates c Ct DO (7) c.count++; (8) END (9) Lk={c Ck |c.countminsup_count} (10) END (11) Answer= kLk;

25 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——5改进 鉴于Apriori算法需要多次扫描数据库，在实际应用中，运行效率往往不能令人感到满意，尤其是当数据库较大时更为棘手。为了提高Apriori算法的性能和运行效率，许多专家对Apriori算法的改进展开了研究，形成了许多改进和扩展Apriori的方法。

26 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——5改进 改进算法的途径包括以下几个方面： ①通过减少扫描数据库的次数改进I/O的性能； ②改进产生频繁项集的计算性能； ③寻找有效的并行关联规则算法； ④引入抽样技术改进生成频繁项集的I/O和计算性能； ⑤扩展应用领域。比如展开定量关联规则、泛化关联规则及周期性的关联规则的研究。

27 4.3 关联规则的Apriori算法 频繁项集的产生及其经典算法之一——Apriori算法
第四章 关联规则 频繁项集的产生及其经典算法之一——Apriori算法 >>> Apriori算法——5改进 鉴于Apriori算法需要多次扫描数据库，在实际应用中，运行效率往往不能令人感到满意，尤其是当数据库较大时更为棘手。为了提高Apriori算法的性能和运行效率，许多专家对Apriori算法的改进展开了研究，形成了许多改进和扩展Apriori的方法。

28 第四章 关联规则 4.1 关联规则的基本概念 4.2 关联规则的挖掘过程 4.3 关联规则的Apriori算法
大数据应用人才培养系列教材 第四章　关联规则 4.1　关联规则的基本概念 4.2　关联规则的挖掘过程 4.3　关联规则的Apriori算法 4.4　关联规则的FP-Growth算法 习题

29 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>>FP-Growth算法——1概念 频繁模式树增长算法（Frequent Pattern Tree Growth）采用分而治之的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。

30 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>>FP-Growth算法——2构建FP树 FP-growth算法将数据集的特点以一种树结构的方式存储，称为FpTree。FpTree是一种用于编码数据集的有效方式，树结构定义如下： public class FpNode { String idName; // id号 List<FpNode> children; // 子结点 FpNode parent; // 父结点 FpNode next; // 下一个id号相同的结点 long count; // 出现次数 }

31 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>>FP-Growth算法——2构建FP树 树的每一个结点FpNode代表一个项，项的内容包括id号idName、子结点children、父结点parent、下一个id号相同的结点next以及该项的出现次数count。

32 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>>FP-Growth算法——3从FP树中挖掘频繁项集 （1）从header table的最下面的item开始，构造每个item的条件模式基（Conditional Pattern Base，CPB）。 （2）构造条件FP-tree（Conditional FP-tree） 累加每个CPB上的item的频繁度（计数），过滤低于阈值的item，构建FP-tree。 （3）FP-Growh：递归的挖掘每个条件FP-tree，累加后缀频繁项集，直到找到FP-tree为空或者FP-tree只有一条路径（只有一条路径情况下，所有路径上item的组合都是频繁项集）。可以证明（严谨的算法和证明在此不进行叙述），频繁项集即不重复也不遗漏。

33 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法 1 2 3 4
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>> FP-Growth算法——4步骤 FP-Growth算法由以下步骤组成： 1 扫描事务数据库D，生成频繁1项集L1 2 将频繁1项集L1按照支持度递减顺序排序，得到排序后的项集L1 3 构造FP树 4 通过后缀模式与条件FP树产生的频繁模式连接实现模式增长 图2 FP树的构造

34 4.4 关联规则的FP-Growth算法 频繁项集的产生及其经典算法之二——FP-Growth算法
4.2　关联规则的挖掘过程 第四章 关联规则 频繁项集的产生及其经典算法之二——FP-Growth算法 >>>FP-Growth算法——5对比 FpGrowth算法的平均效率远高于Apriori算法，但它并不能保证高效率，它的效率依赖于数据集。当数据集中的频繁项集的没有公共项时，所有的项集都挂在根结点上，不能实现压缩存储，而且Fptree还需要其他的开销，需要存储空间更大，使用FpGrowth算法前，首先需要对数据分析，在决策是否采用FpGrowth算法。

35 4.4 关联规则的FP-Growth算法 4.2.2 频繁项集的产生及其经典算法 TID 项目列表 T1 I1, I2, I5 T2
4.2　关联规则的挖掘过程 第四章 关联规则 4.2.2 频繁项集的产生及其经典算法 给定一个事务数据库，如表2所示，采用Apriori算法生成该事务数据库的关联规则。设置信度为2/3。 采用Apriori算法求出强关联规则？ TID 项目列表 T1 I1, I2, I5 T2 I2, I4 T3 I2, I3 T4 I1, I2, I4 T5 I3, I4 T6 I1, I3 T7 I1, I2, I3, I5 T8 I2, I3, I4 T9 I2, I3, I5 T10 I3, I5

36 第四章 关联规则 4.1 关联规则的基本概念 4.2 关联规则的挖掘过程 4.3 关联规则的Apriori算法
大数据应用人才培养系列教材 第四章　关联规则 4.1　关联规则的基本概念 4.2　关联规则的挖掘过程 4.3　关联规则的Apriori算法 4.4　关联规则的FP-Growth算法 习题

37 习题： 1．说明关联规则挖掘的目的和作用。 2．简要说明在频繁模式发现技术中，产生候选项集和不产生候选项集两种技术各自的特点和优缺点。
3．练习使用SQL Server 2005的关联规则挖掘模型。 4．如课本中表4-1所示，设定最小支持度s=10%和s=40%，置信度c=70%，试分别计算该示例数据库中的频繁项集和规则。

38 习题： TID 项目列表 T1 I1, I2, I5 T2 I2, I4 T3 I2, I3 T4 I1, I2, I4 T5 I3, I4
5．给定一个事务数据库，如表2所示，采用Apriori算法生成该事务数据库的关联规则（设置信度为2/3）。 分别采用Apriori算法和FP-Growth算法，求出强关联规则？ TID 项目列表 T1 I1, I2, I5 T2 I2, I4 T3 I2, I3 T4 I1, I2, I4 T5 I3, I4 T6 I1, I3 T7 I1, I2, I3, I5 T8 I2, I3, I4 T9 I2, I3, I5 T10 I3, I5

39 AIRack人工智能实验平台 ——一站式的人工智能实验平台 DeepRack深度学习一体机 ——开箱即用的AI科研平台 BDRack大数据实验平台——一站式的大数据实训平台

40 云创公众号推荐 刘鹏看未来 云计算头条 中国大数据 深度学习世界 云创大数据订阅号 云创大数据服务号 高校大数据与人工智能
微信号：lpoutlook 云计算头条 微信号：chinacloudnj 中国大数据 微信号：cstorbigdata 深度学习世界 微信号：dl-world 云创大数据订阅号 微信号：cStor_cn 云创大数据服务号 微信号：cstorfw 高校大数据与人工智能 微信号：data_AI

41 手机APP推荐 我的PM2.5 随时随地准确 查看身边的 PM2.5值 同声译 支持26种语言 互译的实时翻 译软件 我的南京
云创大数据为路 况大数据应用提 供技术支持 科技头条 汇聚前沿资讯 的科技情报站

42 网站推荐 万物云 智能硬件大数据免费托管平台 环境云 环境大数据开放共享平台

43 感谢聆听