《数据挖掘原理与应用 第2版 》课件 第5章 关联分析

关联分析关联分析原理啤酒与尿布2购物篮分析啤酒与尿布3关联分析应用在美国国会投票记录中发现关联规则在一个国会投票记录的数据集中发现议案投票的相关性，使用分析结果来为政治竞选活动服务，或者预测选举官员会如何投票。4关联分析应用发现毒蘑菇的相似特征这里只对包含某个特定元素（有毒性）的项集感兴趣，从中寻找毒蘑菇中的一些公共特征，利用这些特征来避免吃到那些有毒蘑菇。5关联分析应用在Twitter源中发现一些共现词对于给定搜索词，发现推文中频繁出现的单词集合。6关联分析应用从网站点击流中挖掘流行趋势，挖掘哪些广泛被用户浏览到搜索引擎推荐，在用户输入查询词时推荐同相关的查询词项7关联分析应用从数据海洋中抽取的知识，可以用于商品定价、市场促销、库存管理等环节。8关联分析定义关联分析(又称关联挖掘)在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。或者说，关联分析是发现交易数据库中不同商品（项）之间的联系。9简单关联关系序列关联关系关联分析定义10简单关联关系没有共同属性的事物的组合，组合元素会较大概率同时出现；购买面包的顾客中80%会购买牛奶。面包和牛奶作为一种早餐的搭配是大家所接受的，二者没有共同属性，但是二者搭配后就是一顿美味早餐。商场购买时，如果你把这两样摆在一起时，就会刺激顾客的潜意识联系了二者的关系，并刺激购买。这是一种简单的关联关系。11序列关联关系事物的出现，很大概率上，会在时间上以一定的先后顺序发生12比如买了iphone手机的顾客中80%会选择购买iphone手机保护壳这是序列关联关系存在先后的时间上的顺序数码相机存储卡笔记本电脑照片打印机关联分析基于购物篮事务，进行关联挖掘13基于购物篮事务的关联挖掘14基于购物篮事务的关联挖掘{鸡蛋}的支持度计数=1{尿布啤酒}的支持度计数=3{面包牛奶尿布}的支持度计数=2{鸡蛋}的支持度=1/5{尿布啤酒}的支持度=3/5{面包牛奶尿布}的支持度=2/5N=5概念：支持度计数支持度项集15基于购物篮事务的关联挖掘支持度太低，不能说明问题项集越大，支持度越低{尿布啤酒}的支持度=3/5{牛奶尿布啤酒}的支持度=2/5{面包牛奶尿布啤酒}的支持度=1/516基于购物篮事务的关联挖掘TID面包牛奶鸡蛋啤酒可乐尿布11110002111100311101041111015111010支持度高也不一定有价值常识性的发现没有价值17基于购物篮事务的关联挖掘怎样才算“关联”？1）支持度高，足够高≥支持度阈值minSup置信度2）同时出现的概率大出现{尿布}的事务中，有多少出现了{尿布，啤酒}=3/4≥置信度阈值minConf

18基于购物篮事务的关联挖掘{尿布}支持度=4/5如果根据本例中的业务和数据的特性和规律，认为支持度3/5和置信度3/4已足够建立关联规则，则认为规则{尿布}

{啤酒}存在：即，购买了尿布的购物单中，很大程度上也购买了啤酒。商家便可就此探究成果进行针对性的营销。{尿布}

{啤酒}{尿布，啤酒}支持度=3/519

基于购物篮事务的关联挖掘1）计算支持度：{牛奶，尿布}支持度=3/52）计算置信度：{牛奶，尿布}

{啤酒}

{牛奶，尿布，啤酒}支持度=2/5如果根据本例中的业务和数据的特性和规律，认为支持度2/5=0.4和置信度2/3=0.67已足够建立关联规则，则认为规则{牛奶，尿布}

{啤酒}是关联的，也就是说，购买了牛奶和尿布的购物单中，很大程度上也购买了啤酒。商家便可就此探究成果进行针对性的营销。20

基于购物篮事务的关联挖掘在无目标关联的情况下，需要对每一种可能的组合进行检验，发现其中的关联关系21基本概念项集(Itemset）令

I={i1，i2，……，in}是购物篮数据中的所有项的集合，T={t1，t2，……，td}是所有事务的集合。每个事务ti包含的项集都是I的子集。包含0个或多个项的集合称为项集。k-项集如果一个项集包含k个项，称其为k-项集。例如：{牛奶，面包，尿布}、{牛奶，尿布}、{牛奶}均为项数不同的项集。例如：{牛奶，面包，尿布}就为3-项集。22基本概念支持度计数(Supportcount)包含特定项集的事务个数为支持度计数，用

表示。在数学上，项集X的支持度计数

(X)可以表示为：支持度(Support）包含某项集的事务数与总事务数的比值称为该项集的支持度，用s

表示。支持度衡量的是某项集（即构成该项集的各个事件）同时出现的概率。例如，表5‑2所示的数据中，有：

({牛奶，面包，尿布})=2。例如，s({牛奶，面包，尿布})=2/5。23基本概念频繁项集(FrequentItemSet）是指能够满足支持度阈值(minSup）的所有项集支持度阈值是人为指定的一个数值候选项集未经支持度检验的项集24候选项集频繁项集≥支持度阈值minSup候选项集频繁项集基本概念置信度(confidence)置信度揭示了

X出现时，Y是否一定会出现，如果出现则其大概有多大的可能出现。如果置信度为100%，则说明了

X

出现时，Y

一定出现那么，对这种情况而言，假设

X

和

Y

是市场上的两种商品，就没有理由不进行捆绑销售了25基本概念关联规则关联规则(AssociationRule)是形如

X→Y的蕴含表达式，其中X

和Y

是不相交的项集，即有X∩Y=Ø关联规则的强度可以用它的支持度s和置信度c来度量支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y

在包含X

的事务中出现的频繁程度26蕴含表达式设

p、q为两个命题。复合命题“如果p，则q”称为p与q的蕴含式，记作

p→q。称

p为蕴含式的前件，

q为后件。并规定

p→q为假当且仅当

p为真

q为假。其真值表为：pqp→q100011111001其逻辑关系是：q是

p

的的必要条件，或

p是

q的充分条件。复合命题“只要p就q”、“p仅当q”、“只有q才p”等，都可以符号化为

p→q的形式。27基本原理

规则

事务

关联规则

频繁项集

28关联分析由候选项集产生频繁项集产生候选项集由项产生候选项集A，B，C，D，E五个Item产生25=32个项集30暴力破解(Brute-force)法算法过程：候选项集支持度计数444…332…21…11………{面包，牛奶}3{面包，尿布}3………{面包，牛奶}3{面包，尿布}3{面包，啤酒}2………{面包，牛奶，尿布}2………minSup=3/NminSup=2/N事务……31根据购物篮事务数据产生项列表产生候选项集计算每个项集的支持度(/计数)确定阈值，得到频繁项集暴力破解(Brute-force)法事务候选项集……算法的时间复杂度为O(NMW)N为事务的项数W为事务中项集的维度M为候选项集的项数支持度计数444…332…21…11………MN算法过程：W32根据购物篮事务数据产生项列表产生候选项集计算每个项集的支持度(/计数)确定阈值，得到频繁项集产生频繁项集改进的：先验算法AprioriFP-Growth算法33先验算法AprioriApriori算法是一种基于Apriori原理的，最有影响的挖掘单维布尔关联规则频繁项集的算法该算法能较大程度上降低算法复杂度34先验原理Apriori如果一个项集是频繁的，则它的所有子集一定也是频繁的；对于一个项集{CDE}，其子集为{CD}、{CE}或{DE}，也可以是{C}、{D}或{E}。35先验原理Apriori相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。对于项集{AB}，其超集为{A

B

C}、{A

BD}、{ABE}，或{ABCD}、{ABCE}、{ABDE}、{ABCDE}。根据先验原理，图中若AB项集是非频繁的，则在虚线包围中的所有AB项集的超集都是非频繁的，可以将这些项集剪除，称其为剪枝。36支持度度量的单调性例1：产生频繁项集利用先验原理，产生频繁项集。提取频繁1-项集：共有6个项，即候选1-项集。其中，{可乐}和{鸡蛋}的支持度(计数)不满足阈值要求，所以被剪除。得到频繁1-项集：设定支持度阈值minSup=60%，也就是最小支持度计数为3。37例1：产生频繁项集利用先验原理，产生频繁项集。提取频繁2-项集：其中，{面包，啤酒}和{牛奶，啤酒}的支持度（计数）不满足阈值要求，被剪枝得到频繁2-项集：由频繁1-项集中的4个项，可以组合出共6个候选2-项集：计算支持度计数38设定支持度阈值minSup=60%，也就是最小支持度计数为3。例1：产生频繁项集利用先验原理，产生频繁项集。产生频繁2-项集时，对支持度不满足要求的

{面包

啤酒}和{牛奶

啤酒}项集进行了剪除处理，按照先验原理，也可以将候选3-项集中的这些项集所在的项集剪除。提取频繁3-项集：获取频繁2-项集中的4个项组合出共4个候选3-项集：计算支持度计数其中，{面包，牛奶，尿布}的支持度（计数）不满足阈值要求，被剪枝得到频繁3-项集：39设定支持度阈值minSup=60%，也就是最小支持度计数为3。例1：产生频繁项集利用先验原理，产生频繁项集。枚举法产生候选项集：先验法产生候选项集：40设定支持度阈值minSup=60%，也就是最小支持度计数为3。

+++++++

先验算法Apriori算法函数apriori_gen()来产生候选项集subset()来识别属于事务t的候选项集σ(c)为候选项集的支持度计数41i：某数据项I：数据集中数据项集合

t：事务项T：事务项的集合N：事务集合中事务项的数量Ck：候选k-项集的集合c：候选项集Fk：频繁k-项集的集合先验算法Apriori

规则

事务

关联规则

频繁项集

候选项集

Apriori原理频繁1-项集候选1-项集

候选2-项集

频繁2-项集……候选k-项集

频繁k-项集

42

练习1TIDItemsT1I1，I2，I5，I7T2I2，I4，I6T3I2，I3，I6T4I1，I2，I4T5I1，I3，I6T6I2，I3T7I1，I2，I3，I6，I7T8I1，I2，I3，I5，I7T9I1，I3T10I1，I2，I3，I5，I6，I7T11I1，I2，I3，I7求所有的频繁项集（设支持度计数阈值为4，即支持度阈值为4/11）43TIDI1I2I3I4I5I6I7T1TT

T

TT2

T

T

T

T3

TT

T

T4TT

T

T5T

T

T

T6

TT

T7TTT

TTT8TTT

T

TT9T

T

T10TTT

TTTT11TTT

T练习144扫描数据，对每项计数选择候选支持度计数≥支持度计数阈值，产生频繁1-项集F1由F1组合产生候选2-项集C2。再次扫描数据，计算C2各项集支持度计数

根据支持度阈值确定频繁2-项集F2由F2中各项组合产生候选3-项集。因其中{I1，I6}、{I6，I7}是非频繁的，可对其超集进行基于非频繁子集的剪枝。

再次扫描数据，计算各3-项集支持度计数由F3中的各项组合产生候选4-项集C4

再次扫描数据，计算各4-项集支持度计数根据支持度阈值确定频繁3-项集F3产生频繁4-项集F4

几个问题改进组合产生候选项集的方法Fk-1

F1方法Fk-1

Fk-1方法45产生候选项集计算支持度产生候选项集Fk-1

F1方法利用已经得到的频繁1-项集和频繁(k-1)-项集，组合产生候选k-项集，在经过剪枝，得到频繁k-项集。每个频繁k-项集都由一个频繁(k-1)-项集和一个频繁1-项集组成的，方法是完备的。46产生候选项集Fk-1

F1方法47将产生|Fk-1|×|F1|个候选k-项集复杂度产生候选项集Fk-1

F1方法难以避免重复比蛮力方法改进明显，但仍产生大量不必要的候选项集。例如，通过合并{啤酒，尿布}和{牛奶}而得到的候选是不必要的。因为它的子集{啤酒，牛奶}是非频繁的。确保每个频繁项集中的项以字典序存储，每个频繁(k-1)-项集X只用字典序比X中所有的项都大的频繁项进行扩展（如：项集{面包，尿布}可以用项集{牛奶}扩展，因为“牛奶”(milk)在字典序下比“面包”(bread)和“尿布”(diaper)都大）。48产生候选项集Fk-1

Fk-1方法合并一对频繁(k-1)-项集，仅当它们的前k-2个项(经排序)都相同例如：算法不会合并项集{啤酒，尿布}和{尿布，牛奶}，因为它们的第一个项不相同。{面包，尿布}{面包，牛奶}{面包，尿布，牛奶}49+产生候选项集Fk-1

Fk-1方法合并一对频繁(k-1)-项集，仅当它们的前k-2个项(经排序)都相同频繁2-项集项集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}频繁2-项集项集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}候选产生项集{面包，尿布，牛奶}候选剪枝项集{面包，尿布，牛奶}由于每个候选都由一对频繁(k-1)-项集合并而成，因此，需要附加的候选剪枝步骤来确保该候选的其余k-2个子集是频繁的。50产生候选项集算法51join()：合并组合l1、l2前k-2个项has….()：检验候选项集中是否有非频繁项练习2TIDItemsT1I1，I2，I5，I7T2I2，I4，I6T3I2，I3，I6T4I1，I2，I4T5I1，I3，I6T6I2，I3T7I1，I2，I3，I6，I7T8I1，I2，I3，I5，I7T9I1，I3T10I1，I2，I3，I5，I6，I7T11I1，I2，I3，I7求所有的频繁项集（设支持度计数阈值为4，即支持度阈值为4/11）52使用Fk-1

Fk-1方法TIDI1I2I3I4I5I6I7T1TT

T

TT2

T

T

T

T3

TT

T

T4TT

T

T5T

T

T

T6

TT

T7TTT

TTT8TTT

T

TT9T

T

T10TTT

TTTT11TTT

T练习253扫描数据，对每项计数选择候选支持度计数≥支持度计数阈值，产生频繁1-项集F1由F1组合产生候选2-项集C2。再次扫描数据，计算C2各项集支持度计数

根据支持度阈值确定频繁2-项集F2由F2中各项按Fk-1×Fk-1方法产生候选3-项集。因其中{I6，I7}是非频繁的，可对其超集进行基于非频繁子集的剪枝。

再次扫描数据，计算各3-项集支持度计数由F3中的各项按Fk-1×Fk-1方法产生候选4-项集C4

再次扫描数据，计算各4-项集支持度计数根据支持度阈值确定频繁3-项集F3产生频繁4-项集F4几个问题产生候选项集计算支持度用事务去逐个统计候选项集枚举各事务中的项集并计数利用Hash树计数54关联分析计算支持度计数关联分析原理

规则

事务关联规则频繁项集56关联分析原理

规则

事务关联规则频繁项集

候选项集

57几个问题产生候选项集计算支持度用事务去逐个统计候选项集枚举各事务中的项集并计数利用Hash树计数58用事务去逐个统计候选项集事务候选项集支持度计数NWM59枚举各事务中的项集并计数

60

枚举各事务中的项集并计数61利用Hash树计算支持度Hash树7807%2=1插入249%2=1冲突，249%3=0插入1073%2=1冲突，1073%3=2插入658%2=0插入930%2=0冲突，930%3=0插入2272%2=0冲突，2272%3=1插入8544%2=0冲突，8544%3=0冲突，8544%5=4插入1878%2=0冲突，1878%3=0冲突，1878%5=3插入8923%2=1冲突，8923%3=1插入8709%2=1冲突，8709%3=0冲突，8709%5=4插入root0101023441658780793018788544892387091073249227262散列树n%2n%3n%5Hash树原理【质数分辨定理】选取任意n个互不相同的质数：P1<P2<……<Pn-1<Pn(n∈N)，定义设m≤k1<k2<m+M

（m，k1，k2∈N

），那么对于任意的i∈[1，n]，(k1

modPi)=(k2modPi)不可能总成立。简单地说就是：n

个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。例如：从2起的连续质数，连续10个质数就可以分辨大约M(10)=2

3

5

7

11

13

17

19

23

29=6464693230个数，已经超过计算机中常用整数（32bit）的表达范围。63根据频繁项集（例如F2）产生候选3-项集（Fk-1xFk-1）建立起候选项集Hash树遍历事务T在树中散列事务项t匹配的候选项集支持度计数+1计算支持度64候选项集

-{

-{

}

-{

}

-{

}

-{

}

-{

}123237137127267236

-{

}

-{

}

-{

}367{

}候选项集Hash树计算支持度【例】利用Hash树计算支持度计数65候选4-项集:{1235},{1236},{1256},{1356},{2356}候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}计算支持度【例】利用Hash树计算支持度计数66Hash树1,4,72,5,83,6,9Hash函数：h(p)=p

mod3事务中，项集为{1,2,3,4,5,6}计算支持度【例】利用Hash树计算支持度计数1231-{23}{123}12-{3}候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}{1

23}由候选3-项集生成Hash树结构67Hash树1,4,72,5,83,6,9计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}125候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{1

25}68计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}1251-{26}{126}12-{6}126候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{126}69计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231251-{26}{126}12-{6}1261-{35}{135}13-{5}135候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{135}70{135}{136}1-{35}计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231251261-{35}13513-{5}12-{6}1-{36}13-{6}136候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{136}71计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,8

3,6,92-{3456}3-{456}35-{6}356 12323-{456}1-{23456}{123456}23525623625-{6}12-{3456}13-{456}12613512513615615-{6}候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{356}72计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,923-{456}1-{23456}root2-{3456}3-{456}12-{3456}13-{456}123235135125136 156256 23612615-{6}25-{6}35-{6}356 {13

46}事务数据项t按照同样的规则进行散列，如果能够到达叶结点中的候选项集，则对其支持度计数加1。1-{3

46}13-{46}136 {3

46}3-{46}{46}73计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,92-{3456}3-{456}345项{1},{2},{3},{4},{5},{6}构成3-项集的Hash树结构34-{56}346 35-{6}356 45-{6}45612323-{456}4-{56}1241-{23456}{123456}13423525623614-{56}14523424-{56}24524625-{6}12-{3456}13-{456}12613512513615614615-{6}74计算支持度【例】利用Hash树计算支持度计数123613561235Hash树1,4,72,5,83,6,91256123-{456}2356235-{6}135-{6}125-{6}12-{3456}13-{456}23-{456}1-{23456}{123456}2-{3456}候选4-项集:{1235},{1236},{1256},{1356},{2356}由候选4-项集生成Hash树结构75计算支持度【例】利用Hash树计算支持度计数123613561235Hash树1,4,72,5,83,6,91256123-{456}2356235-{6}135-{6}125-{6}12-{3456}13-{456}23-{456}1-{23456}2-{3456}root{12356}{2356}123612352356事务数据项t按照同样的规则进行散列，如果能够到达叶结点中的候选项集，则对其支持度计数加1。{356}76计算支持度【例】利用Hash树计算支持度计数12361356123523451245Hash树1,4,72,5,83,6,9项{1},{2},{3},{4},{5},{6}构成的4-项集Hash树结构123412461256123-{456}134513461456234623562456235-{6}134-{56}135-{6}145-{6}245-{6}124-{56}125-{6}234-{56}12-{3456}13-{456}14-{56}24-{56}23-{456}1-{23456}{123456}2-{3456}3-{456}3

4-{56}345-{6}345677

K-候选项集Hash树Hash树1,4,72,5,83,6,9781236135612351256123-{456}2356235-{6}135-{6}125-{6}12-{3456}13-{456}14-{56}24-{56}23-{456}1-{23456}{123456}2-{3456}3-{456}3

5-{6}356-{}

候选项集小结能够采取措施，高效地处理支持度计数的计算问题，是提高关联算法算法效率的关键一环79关联分析FP-Growth算法Apriori算法缺陷81计算量大冗余高占用内存FP增长(FP-growth)算法采用完全不同的方法来发现频繁项集使用称作FP树的紧凑数据结构组织数据直接从该结构中提取频繁项集FP树是一种输入数据的压缩表示，逐个读入事务，并将其映射到FP树中的一条路径82Apriori算法：产生-测试范型算法过程构建FP树提取频繁项集83Trie树84NullLOWKOAW字符串“L”字符串“LA”字符串“LAW”字符串“LOOK”字符串“LO”字符串“LOO”字符串“LOW”Trie树存放单词（字符串）的结构Trie树存放数据的结构FP-Tree，是以Trie树为基础的一种用于发现频繁项集的数据结构。Trie树也被称为字典树或单词查找树，是Hash树的一种变种。Trie树Trie树的优点利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较查询效率比Hash树更高Trie树的基本性质根节点不包含字符，其他每一个节点都只包含一个字符从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串每个节点的所有子节点包含的字符都不相同85算法过程构建FP树提取频繁项集86构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}扫描数据集（一次），确定每个项的支持度计数丢弃非频繁项，而将频繁项按照支持度的递减排序扫描数据集（二次），构建FP树87构造FP树读入第1个事务{A,B}创建标记为A和B的结点；形成null->A->B路径；该路径上的所有结点的频度计数为1。TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}88构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}读入第2个事务{B,C,D}图中只有以A为起点的路径，无法重叠借用，只能另起一个路径：null->B->C->D来代表该事务。路径上每个结点的频度计数加1。尽管与前一个事务有一个共同项B，但两个事务没有共同的前缀，路径不相交。89构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}读入第3个事务{A,C,D,E}与第1个事务共享一个共同的前缀项A，所以事务路径null->A->C->D->E与第一个事务的路径null->A->B部分重叠……路径上的每个结点的频度计数加1。90构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}读入第4个事务{A,D,E}与第1个事务共享一个共同的前缀项A，所以事务路径null->A->D->E与第1、3个事务的路径部分重叠……路径上的每个结点的频度计数加1。91构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}继续该过程，直到每个事务都映射到FP树的一条路径。92构造FP树TIDItems1{A,B}2{B,C,D}3{A,C,D,E}4{A,D,E}5{A,B,C}6{A,B,C,D}7{A}8{A,B,C}9{A,B,D}10{B,C,E}11{A,B,C,D,E}通常，FP树的大小比未压缩的数据小，因为购物篮数据的事务常常共享一些共同项。如果共同项较少，FP树对存储空间的压缩效果将不明显。FP树的大小也依赖于项如何排序。一般按照支持度计数递减序可以导致较小的FP树。但也有一些例外。FP树还包含一个连接相同项的结点的指针列表。这些指针有助于方便快捷地访问树中的项。93算法过程构建FP树提取频繁项集94提取频繁项集每一个事务都映射为FP树中的一条路径，因而通过仅考察包含特定结点（例如E）的路径，就可以发现以其（如E）结尾的频繁项集。以D结尾的子树以E结尾的子树按照此法分别处理Headertable中的每个项，可以拆解FP树，发现每个频繁项集。95提取频繁项集FP-Growth是一种以自底向上方式探索树，由FP树产生频繁项集的算法。以A结尾的子树以B结尾的子树以C结尾的子树使用与某结点相关联的指针，可以快速访问这些路径。96提取频繁项集{DE}=3{CE}=3{BE}=2{AE}=3以E结尾的子树E的条件树例：提取以E结尾的频繁项集①更新E各父结点频次②省略E项97去除非以E结尾提取频繁项集例：提取以E结尾的频繁项集E的条件树{DE}的条件树{CDE}=2{BDE}=1{ADE}=3{CE}的条件树{BCE}=2{ACE}=2{BE}的条件树{ABE}=198提取频繁项集例：提取以E结尾的频繁项集E的条件树{DE}的条件树{CE}的条件树{BE}的条件树{CDE}的条件树{BDE}的条件树{BCDE}的条件树{BCE}的条件树提取过程100提取过程101生成的条件树提取频繁项集同样方法：提取以D结尾的频繁项集D的条件树{CD}的条件树{BD}的条件树{BCD}的条件树102提取频繁项集同样方法：提取以C结尾的频繁项集C的条件树{BC}的条件树同样方法：提取以B结尾的频繁项集103条件树基于支持度剪枝minSup=3104频繁的{E}的条件树{E}的条件树条件树基于支持度剪枝minSup=3105频繁的{DE}的条件树{DE}的条件树FP-Growth算法（演示软件）106小结FP-Growth算法在数据项相对集中的情况下，可以有效地降低产生频繁项集的计算时间复杂度107关联分析产生频繁项集算法复杂度Apriori算法复杂度影响Apriori算法的计算复杂度的因素支持度阈值降低支持度阈值通常会导致产生更多的频繁项集，计算复杂度增加数据项个数随着数据项个数增加，需要更多的空间来存储项的支持度计数候选项集、频繁项集的数目也随之增加，计算量和I/O开销将随之增加109Apriori算法复杂度影响Apriori算法的计算复杂度的因素事务数运行时间随着事务数增加而增加事务的平均宽度频繁项集的最大长度随事务平均宽度增加而增加随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数110Apriori算法复杂度111Apriori算法复杂度112FP-Growth算法的复杂度FP-Growth算法分为几个步骤：遍历事务数据计算数据项出现频次并排序遍历每一事务数据排序后散列入FP-Tree发现频繁项集113FP-Growth算法的复杂度

事务数据集T数量为N宽度为w数据项的数量为b114小结在关联分析的过程中，需要采取措施，高效的处理支持度计数的计算问题，提高关联算法的计算效率115关联分析产生关联规则关联规则

117关联规则产生事务TIDITEMS1I1,I2,I32I2,I3,I43I1,I3,I5,...………关联规则{I1,I2}{I3}{Ii,Ij}{Ik}……c≥minConf“候选”关联规则{I1,I2}{I3}{I1,I3}{I2}

{I1,I5}

{I2}{Ii,Ij}{Ik}……频繁项集+支持度{I1}，7

{I2}，6{I3}，5{I1,I2}，5{I1,I3}，4{I1,I2,I3}，4……，…s≥minSup118方法：对于频繁k-项集Z，

将集合Z

划分为

X

和Y

两个不重叠子集，

由X

和Y

生成“候选”的关联规则。

若候选规则X

Y

的置信度满足阈值，

则X

Y

为关联规则。

Z

X

Y

这样的规则必然已经满足支持度阈值，因为它们是由频繁项集产生的那么产生关联规则，是对于所产生出的频繁k-项集Z，关联规则产生从频繁项集产生候选的关联规则例：频繁项集{ABCD}，候选规则有：{ABC}{D}，{ABD}{C}，{ACD}{B}，{BCD}{A}{AB}{CD}，{AC}{BD}，{AD}{BC}，{BC}{AD}，{BD}{AC}，{CD}{AB}{A}{BCD}，{B}{ACD}，{C}{ABD}，{D}{ABC}119前件3，后件1前件2，后件2前件1，后件3还可以产生ABCD、关联规则产生关联规则X

Y的强度的度量指标：支持度

s：确定规则可以用于给定数据集的频繁程度置信度c：确定

Y在包含

X的事务中出现的频繁程度计算关联规则的置信度并不需要再次扫描事务数据集120

生成“候选”规则121暴力破解法基于Apriori的方法暴力破解法(Brute-forceapproach）

计算代价过高122fk

h

fk-h

h

fk-hApriori原理123支持度度量的单调性按照Apriori原理置信度也遵循“先验”规则被剪枝的规则低置信度规则124

按照Apriori原理如果规则X

Y

不满足置信度阈值，则形如X-

Y+

的规则一定也不满足置信度阈值，其中

是X

的子集。例如：125

大家可以看到，前件中项的数量逐渐变少，后件中项的数量逐渐变多…算法针对每一个不同大小的频繁项集，依次处理。根据频繁项集

fk和后件Sm，计算规则(fk-Sm)→Sm的置信度，若满足阈值要求，则确认该规则并输出；基于后件Sm，产生增加了一个项的后件Sm+1的集合{Sm+1}，对其中的每各后件Sm+1，结合频繁项集fk，递归调用gen_rules()，处理所有的规则组合。126如果它满足阈值要求，则确认该规则并输出{1237}

{}{123}{7}{127}{3}{137}{2}{12}

{37}{13}

{27}{23}{17}{1}-{237}{7}-{123}{3}-{127}{17}{23}{27}-{13}{237}{1}{37}-{12}{2}-{137}127{I7I3I2I1}

{}{I7I3I2}{I1}{I7I3I1}{I2}{I7I2I1}{I3}{I7I3}{I2I1}{I7I2}{I3I1}{I3I2}{I7I1}{I7}-{I3I2I1}{I1}-{I7I3I2}{I2}-{I7I3I1}{I7I1}{I3I2}{I3I1}-{I7I2}{I3I2I1}{I7}{I2I1}-{I7I3}{I3}-{I7I2I1}128【例】购物篮分析支持度计数≥4转换为二元数据去除非频繁项组合产生候选2-项集，并计数按列求和，统计各数据项计数去除非频繁项129【例】购物篮分析支持度计数≥4组合产生候选3-项集（Fk-1

Fk-1）去除非频繁2-项集超集和非频繁项组合产生候选4-项集（Fk-1

Fk-1）去除非频繁2-项集超集和非频繁项130【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取关联规则131从频繁2-项集和频繁1-项集以及它们的支持度计数，【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取时，可先提取前件为2-项集，后件为1-项集的规则，如果置信度不满足要求，则不再提取前件为1-项集后件为2-项集的规则。132【例】购物篮分析支持度计数≥4置信度≥0.85生成规则提取时，可先提取前件为3-项集，后件为1-项集的规则，若置信度满足要求，才继续提取22形式的规则，否则向下剪枝；如果22形式的规则满足要求，才继续提取13形式的规则。133【例】购物篮分析支持度计数≥4置信度≥0.85134{I1,I2,I3,I7}{I1,I2,I3}→{I7}{I1,I2,I7}→{I3}{I1,I3,I7}→{I2}{I2,I3,I7}→{I1}{I3,I7}→{I1,I2}{I2,I7}→{I1,I3}{I1,I7}→{I2,I3}{I2,I3}→{I1,I7}{I1,I3}→{I2,I7}{I1,I2}→{I3,I7}{I7}→{I1,I2,I3}{I3}→{I1,I2,I7}{I2}→{I1,I2,I7}{I1}→{I2,I3,I7}

在格结构中，由这些关联规则向下衍生出来的规则，需要进行置信度阈值检验；【例】购物篮分析支持度计数≥4置信度≥0.85关联规则：

{I7}{I1}，1.0

{I7}{I2}，1.0{I1I2I3}

{I7}，1.0{I1I3I7}{I2}，1.0{I3I7}{I1I2}，1.0{I2I3I7}{I1}，1.0{I1I7}

{I2}，1.0{I7}

{I1I2}，1.0{I2I7}

{I1}，1.0{I3I7}

{I1}，1.0{I3I7}

{I2}，1.0135【例】购物篮分析WEKA运行结果1.I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)2.I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)3.I2/I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)4.I1/I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)5.I7/5==>I1/I2/5<conf:(1)>lift:(1.83)lev:(0.21)[2]conv:(2.27)6.I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)7.I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)8.I2/I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)9.I1/I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)10.I1/I2/I3/4==>I7/4<conf:(1)>lift:(2.2)lev:(0.2)[2]conv:(2.18)11.I3/I7/4==>I1/I2/4<conf:(1)>lift:(1.83)lev:(0.17)[1]conv:(1.82)136关联规则的强度关联规则X

Y的强度的度量指标：支持度

s：确定规则可以用于给定数据集的频繁程度置信度c：确定

Y在包含

X的事务中出现的频繁程度其他度量137小结从频繁项集中提取关联规则，是关联分析的重要一环运用Apriori原理生成规则，可以大大降低计算复杂度用计算机编程实现这一过程时，可以通过嵌套调用的方法来递归生成完备的关联规则138关联分析关联模式评估关联模式的评估关联分析算法往往产生大量的规则有一部分可能会具有相对较高的支持度和置信度，但可能由于某些原因，其强关联关系并不一定能成立或很大一部分可能是不感兴趣的。因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的140关联规则评估标准统计论据判定主观论据判定前件、后件统计上相互独立覆盖少量事务的模式反映的是伪关联客观兴趣度度量主观认为是无趣的提升度（Lift）杠杆率（Leverage）确信度（Conviction）兴趣因子（interestfactor）可视化基于模板的方法主观兴趣度量

141主观论据判定模式由主观认为是否为有趣的{黄油}

{面包}无趣，它表示的关系显而易见。尽管支持度和置信度都会很高{尿布}{啤酒}是有趣的，因为这种联系十分出乎意料，并且可能为零售商提供新的交叉销售机会。利用主观知识对模式评估较为困难，因需要来自领域专家的大量先验信息142客观兴趣度度量支持度-置信度框架的局限性忽略了规则后件中项集的支持度高置信度的规则有时存在误导143客观兴趣度度量【例】分析喝咖啡和喝茶的人之间的关系，收集一组饮料偏爱的数据，并汇总到表格。1000人的饮料偏好Coffee合计Tea15050200650150800合计8002001000规则支持度

=15%，置信度s=75%，都相当高，似乎规则成立。评估关系规则{茶}{咖啡}。然而，在没有任何前提条件时，喝咖啡的人的比例为80%；这意味着，喝茶这个条件，反而降低了喝咖啡的概率（由80%降到了75%），说明两个情况是互斥的。置信度的缺点在于该度量忽略了规则中后件项集的支持度。相依表144相依表（contingencytable）给定随机变量X、Y，可以构建一个相依表给定关联规则XY：ContingencytableforX，Y

Y

Xf11f10f1+f01f00f0+

f+1f+0NContingencytableforX

Y

Y

Xf11f10f1+f01f00f0+

f+1f+0|T|

145客观兴趣度度量客观兴趣度度量使用数据的统计量，来确定模式是否确实关联提升度（Lift）杠杆率（Leverage）确信度（Conviction）兴趣因子（interestfactor）相关度IS度量146提升度提升度：对于事件

X和

Y，提升度表示含有

X的条件下，同时含有

Y的概率，与

Y发生