大数据时代算法关联规则简介 数据挖掘与关联规则 PPT

= {{A,B,C},{A,C,E},{B,C,E}}
• 2．使用Apriori性质剪枝：频繁项集的所有子集必须是频 繁的，对候选项C3，我们可以删除其子集为非频繁的选项：
– {所A,以B,删C}的除2这项个子选集项是；{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，
–
{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E} 所以删除这个选项；
confidence( A B) P( A | B) sup port _ count( A B) sup port _ count( A)
• 每个关联规则可由如下过程产生：
– 对于每个频繁项集l，产生l的所有非空子集；
– 对于每个非空子集s，如果
则输出规则“
” sup port _ count(l) min_ conf
• 关联规则的两个兴趣度度量
– 支持度 buys ( X , "computer") buys ( X , "software") – 置信度 [sup port 2%, confidence 60%]
第五页，共36页。
• 关联（association）：两个或多个变量的取值之间存 在某种规律性。
集c’，使得每个包含c的事务也包含c’）
• （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项 集）
第十八页，共36页。
由事务数据库挖掘单维布尔关联规则
• 最简单的关联规则挖掘，即单维、单层、布尔关联
规则的挖掘。
Transaction ID Items Bought
最小支持度 50%
2000 A,B,C
关联规则与关联分析
第一页，共36页。

• 如：规则{尿布}—>{啤酒}表示尿布和啤酒的销售之间存在关联—— “啤酒与尿布”的故事。
• 关联分析用以发现事物间存在的关联性，除了购物篮分析外，有广泛应用， 如：辅助决策——挖掘商场销售数据、发现商品间的联系；医疗诊断—— 用于发现某些症状与某种疾病之间的关联；网页挖掘——用于发现文档集 合中某些词之间的关联，发现主题词演化模式、学科发展趋势；电子商 务——进行产品的关联推荐等。
频繁项集
支持度不小于最小支持度阈值的项集
强关联规则
根据用户预先定义的支持度和置信度阈值，支持度不小于最小支持度阈值 并且置信度不小于最小置信度阈值的规则
5.2.1 基本概念(4)
关联分析挖掘的关联规则分类 根据处理值分类
布尔关联规则 量化关联规则
根据涉及维度分类
单维关联规则 多维关联规则
支持度 (support)
事务数据库D中包含项A和B的事务占所有 事务的百分比
可表示为：support(A,B ) P(A B ) (A B )/ N
5.2.1 基本概念(3)
置信度
事务数据库D中同时包含项A和B的事务占包含项A的事务的百分比
条件概率表示为： confindence(A,B ) P(B | A) (A B )/ (A)
根据数据抽象层次分类
单层关联规则 多层关联规则
【例5-1】 设有事务集合如表5-1，计算规则{bread,milk tea} 的支持度、置信度。
交易号TID
顾客购买的商品
ห้องสมุดไป่ตู้
交易号TID
T1
bread, cream, milk, tea
T6
T2
bread, cream, milk
T7

第7章
大数据分析挖掘—关联规则
主要内容
01
关联规则的概念
02
关联规则挖掘的一般过程
03
Apriori算法
04
FP-Growth算法
05
关联模式评估
大数据分析挖掘——关联规则
7.1基本概念
• 设 I {x1, x2,xm}是项目的集合，其中的元素称为项目 (item),一个集合被称为一个项集，包含k个项的集合称为 k-项集。
项集 支持度计数
{I1,I2} 1
{I1,I3} 2
{I1,I5} 1
{I2,I3} 2
{I2,I5} 3
{I3,I5} 2
4.比较候选项支持度计数与最小支持度min_sup，产生2维最大项目集：
项集 支持度计数
{I1,I3} 2
{I2,I3} 2
{I2,I5} 3
{I3,I5} 2
5.由L2 产生候选项集 C3，比较候选项支持度计数与最小支持度 min_sup，产生3维最大项目集 L3 ，至此算法终止。
• FP-Growth算法（Frequent Pattern-Growth）是另一种 找出频繁项集的方法，与先生成规则再筛选的Apriori算 法不同，FP-Growth算法是将数据库中符合频繁1-项集规 则的事务映射在一种图数据结构中，即FP树，而后据此 再生成频繁项集，整个过程只需要扫描两次数据集。
表7.1 某商店购物清单 Item 2
Item 3
1
香草华夫
香蕉
狗粮
2
香蕉
3
香蕉
4
香草华夫
5
面包
6
牛奶
7
香草华夫
8
酸奶
9

3.多层关联规则挖掘算法
对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强 关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规 则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所 以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。
(1)
如 ：if A then B。则它的支持度Support=P(A and B) 2. Confidence（可信度）：它是针对规则而言的。
Confidence=p(condition and result)/p(condition)。
(2)
如：If B and C then A。则它的可信度Confidence=p(B and C and A)/p(B and C)。 把满足最小支持度阈值和最小置信度阈值的规则成为强规则。项的集合称
多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层 间关联规则。
多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题 上有一些要考虑的东西。
4.多维关联规则挖掘算法
对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如：年龄（X， “20…30”） 职业（X，“学生”）==> 购买（X，“笔记本电脑”）在这里我们就涉及到三个 维上的数据：年龄、职业、购买。
该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和 预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小 支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集 合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定 义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被 留下来。为了生成所有频集，使用了递推的方法。