18
市场购物篮分析
事务 ID A B C D 购物篮 Chips, Salsa, Cookies, Crackers, Coke, Beer Lettuce, Spinach, Oranges, Celery, Apples, Grapes Chips, Salsa, Frozen Pizza, Frozen Cake Lettuce, Spinach, Milk, Butter, Chips
36
生成频繁项集
naïve algorithm的分析

I 的子集: O(2m)
为每一个子集扫描n个事务 测试s为T的子集: O(2mn)
随着项的个数呈指数级增长! 我们能否做的更好?
37
Apriori 性质
定理(Apriori 性质): 若A是一个频繁项集,则A 的每一个子集都是一个频繁项集. 证明:设n为事务数.假设A是l个事务的子集,若 A’ ⊂ A , 则A’ 为l’ (l’ ≥ l )个事务的子集.因此, l/n ≥s(最小支持度), l’/n ≥s也成立.
关联规则的最小支持度也就是衡量频繁 集的最小支持度 (Minimum Support) ， 记为supmin，它用于衡量规则需要满足 的最低重要性。 规 则 的 最 小 可 信 度 (Minimum Confidence )记为confmin，它表示关 联规则需要满足的最低可靠性。
32
定义9 强关联规则
35
生成频繁项集
Naïve algorithm
n <- |D| for each subset s of I do l <- 0 for each transaction T in D do if s is a subset of T then l <- l + 1 if minimum support <= l/n then add s to frequent subsets
支持度s 是数据库中包含 X ∪ Y 的事务占全部事务的百分比
support ( X ⇒ Y ) = P ( X ∪ Y )
X ⇒Y
s, c
置信度c是包含 X ∪ Y 的事务数与包含X 的事务数的比值
confidence( X ⇒ Y ) = P (Y | X )
频繁项集
用户预先定义最小支持度阈值（min_sup）和 最小置信度阈值（min_conf ）。 如果某个项集的支持度大于等于设定的最小支 持度阈值min_sup ，称这个项集为“频繁项集” （也称为“大项集”，LargeItemsets），所 有的“频繁k -项集”组成的集合通常记作L k 。

满足最小支持度 找出所有的强关联规则 由频繁项集生成关联规则 保留满足最小可信度的规则
22
2 使用候选项集找频繁项集
从频繁项集产生关联规则
引例
假定某超市销售的商品包括：bread、bear、 cake、cream、milk和tea
交易号TID T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 顾 客 购 买 商 品Items bread cream milk tea bread cream milk cake milk milk tea bread cake milk bread tea beer milk tea bread tea bread cream milk tea bread milk tea
29
定义6 关联规则的支持度
对于关联规则 R ： X⇒Y ，其中 X⊂I,Y⊂I ， 并 且 X∩Y=Φ ， 规 则 R 的 的 支 持 度 (Support)是交易集中同时包含X和Y的交 易数与所有交易数之比。
count(X ∪ Y) support(X ⇒ Y) = |D|
30
定义7 关联规则的可信度
每笔交易T(Transaction)是项集I上的一 个子集，即T⊆I，但通常T⊂I。 对应每一个交易有一个唯一的标识 —— 交易号，记作TID 交易的全体构成了交易数据库D，或称交 易记录集D，简称交易集D。 交易集D中包含交易的个数记为|D|。
26
定义3 项集的支持度
对于项集X，X⊂I，设定count(X⊆T)为交易集 D中包含X的交易的数量
confidence(A ⇒ B )=P(B|A) 条件概率 P(B|A) 表示A发生的条件下B也发生的概率.
17
关联规则的度量
关联规则根据以下两个标准(包含或排 除):

最小支持度 – 表示规则中的所有项在事
务中出现的频度

最小可信度 - 表示规则中左边的项(集)
的出现暗示着右边的项(集)出现的频度
如果规则X⇒Y满足： support(X⇒Y)≥supmin 且confidence(X⇒Y)≥confmin， 称关联规则 X⇒Y 为强关联规则，否则称 关联规则X⇒Y为弱关联规则。

在挖掘关联规则时，产生的关联规则要经过 supmin 和 confmin 的衡量，筛选出来的强关联规 则才能用于指导商家的决策。 33
Apriori AprioriTid AprioriHybrid FP-growth Eclat H-Mine
深度优先算法

关联规则
关联规则 (Association Rule Mining) 挖 掘是数据挖掘中最活跃的研究方法之一 最早是由R.Agrawal等人提出的 其目的是为了发现超市交易数据库中不同 商品之间的关联关系。 一个典型的关联规则的例子是： 70% 购买 了牛奶的顾客将倾向于同时购买面包。 经典的关联规则挖掘算法：Apriori 算法和 FP-growth算法 1第一阶段先从数据集中找出所有的频繁项集，它们 的支持度均大于等于最小支持度阈值min_sup 第二阶段由这些频繁项集产生关联规则，计算它们 的置信度，然后保留那些置信度大于等于最小置信 度阈值min_conf 的关联规则。

关联规则挖掘算法
广度优先算法

count(X ⊆ T) support(X) = |D|
项集 X 的支持度 support(X) 就是项集 X 出现的 概率，从而描述了X的重要性。
27
定义4 项集的最小支持度与频繁集
发现关联规则要求项集必须满足的最小支持阈 值 ， 称 为 项 集 的 最 小 支 持 度 (Minimum Support)，记为supmin。

项集: {Chips, Salsa, Beer}
Beer, Chips => Salsa Beer, Salsa => Chips Chips, Salsa => Beer
强规则是有趣的

强规则通常定义为那些满足最小支持度和最小可信 度的规则.
21
关联规则挖掘
两个基本步骤

找出所有的频繁项集
关联规则 --及其分析方法
杨文川 2014.2
内容
1 关联规则 2 Apriori 算法 3 其它关联分析算法
1 关联规则概述
数据关联是数据库中存在的一类重要的可被发 现的知识。若两个或多个变量的取值之间存在 某种规律性，就称为关联。 关联规则挖掘的一个典型例子是购物篮分析。

啤酒与尿布的故事
关联可分为简单关联、时序关联、因果关联。 关联分析的目的是找出数据库中隐藏的关联， 并以规则的形式表达出来，这就是关联规则。
市场购物篮分析
分析事务数据库表
Person A B C D Basket Chips, Salsa, Cookies, Crackers, Coke, Beer Lettuce, Spinach, Oranges, Celery, Apples, Grapes Chips, Salsa, Frozen Pizza, Frozen Cake Lettuce, Spinach, Milk, Butter
对于关联规则 R ： X⇒Y ，其中 X⊂I,Y⊂I ，并且 X∩Y=Φ ，规则 R 的可信度 (Confidence) 是指 包含X和Y的交易数与包含X的交易数之比
support(X ∪ Y) confidence (X ⇒ Y) = support(X)
31
定义8 关联规则的最小支持度 和最小可信度

从统计意义上讲，它表示用户关心的关联规则必须 满足的最低重要性。只有满足最小支持度的项集才 能产生关联规则。
支持度大于或等于supmin的项集称为频繁项 集，简称频繁集，反之则称为非频繁集。 通常k-项集如果满足supmin，称为k-频繁集， 记作Lk。
28
定义5 关联规则
关联规则(Association Rule)可以表示为一个 蕴含式： R：X⇒Y
3 Apriori算法
单维布尔关联分析
Apriori算法
IBM公司Almaden研究中心的R.Agrawal 等 人在1993年提出的AIS和SETM。 在1994年提出Apriori和AprioriTid。 Apriori和AprioriTid算法利用前次过程中的 数据项目集来生成新的候选数据项目集，减少 了中间不必要的数据项目集的生成，提高了效 率
基本概念
一个样本称为一个“事务” 每个事务由多个属性来确定，这里的属性我们称为“项” 多个项组成的集合称为“项集”
k-项集
由k个项构成的集合

{牛奶}、{啤酒}都是1-项集； {牛奶，果冻}是2-项集； {啤酒，面包，牛奶}是3-项集。
每个事务其实就是一个项集
关联规则的表示
X 和Y 是项集 X 称为规则前项（或者前件，antecedent） Y 称为规则后项（或者后件，consequent）
14
项集 事务 关联规则
基本概念
I = {i1 , i2 ,..., im }
T⊆I
A⇒ B A ⊂ I, B ⊂ I, A∩ B = ∅