“1+X”(中级)05-关联规则

关联规则课程目录5.1.关联规则综述

5.1.1关联规则的基本概念

5.1.2关联规则提出的背景

5.1.3关联规则的原理

5.1.4关联规则的应用场景

5.1.5关联规则的分类5.2.关联规则挖掘常用算法5.3.关联规则实验5.4.本章小结5.5本章习题关联规则的基本概念数据集合关联分析全部或者某些元素之间的关联关系输入输出关联分析用于描述多个变量之间的关联，如果两个或者多个变量之间存在一定的关联，那么其中一个变量的状态就能通过其他变量进行预测。关联规则基本概念自然界中某种事物发生时其他事物也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。关联分析的目的是找出数据集合中隐藏的关联网，是离散变量因果分析的基础。牛奶和面包应该分别放在哪儿？才能使销售利润最大？市场组合分析套装产品分析目录设计交叉销售关联规则的基本概念课程目录5.1.关联规则综述

5.1.1关联规则的基本概念

5.1.2关联规则提出的背景

5.1.3关联规则的原理

5.1.4关联规则的应用场景

5.1.5关联规则的分类5.2.关联规则挖掘常用算法5.3.关联规则实验5.4.本章小结5.5本章习题关联规则提出的背景1993年，Agrawal等人首先提出关联规则概念，同时给出了相应的挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则最初提出的动机是针对购物篮分析(MarketBasketAnalysis)问题提出的。假设分店经理想更多的了解顾客的购物习惯。特别是，想知道哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营销策略。课程目录5.1.关联规则综述

5.1.1关联规则的基本概念

5.1.2关联规则提出的背景

5.1.3关联规则的原理

5.1.4关联规则的应用场景

5.1.5关联规则的分类5.2.关联规则挖掘常用算法5.3.关联规则实验5.4.本章小结5.5本章习题支持度与置信度设关联规则：A=>B，{A}或{B}为项集，项集{A}可以认为为前因，项集{B}可以认为为后果。支持度表示的是两个事件同时发生的概率，也就是表示同时包含A、B事务占总事务的百分比。置信度是预测性指标，是在前因发生的条件下，后果发生的概率，表示同时发生A、B事务的概率占事务A发生概率的百分比。支持度为对称指标，即{A,B}的支持度与{B,A}的支持度都

一样，而置信度为非对称指标，二者不同，即置信度(A=>B)与置信度(B=>A)不一样。支持度与置信度案例茶和咖啡的案例某调研机构，调查统计了1000个用户的喝茶及喝咖啡的情况，1000个调研对象中，喝茶的用户有200人，喝咖啡的用户有800人，喝茶且喝咖啡的用户有150人，不喝茶也不喝咖啡的用户有150人，基于此些数据，查看{喝茶}->{喝咖啡}的支持度、置信度。喝咖啡（A）不喝咖啡（－A）合计喝茶（B）15050200不喝茶（－B）650150800合计8002001000支持度（{喝茶}->{喝咖啡}）＝150/1000=15%；置信度（{喝茶}->{喝咖啡}）＝150/200=75%；即一个人喝茶那么他75%可能喝咖啡课程目录5.1.关联规则综述

5.1.1关联规则的基本概念

5.1.2关联规则提出的背景

5.1.3关联规则的原理

5.1.4关联规则的应用场景

5.1.5关联规则的分类5.2.关联规则挖掘常用算法5.3.关联规则实验5.4.本章小结5.5本章习题关联规则的应用场景关联规则应用场景类别价格预测类气象预测类精准营销类内容推荐类成因分析类其他类别穿衣搭配推荐地点推荐系统基于兴趣的实时新闻推荐电子商务搭配购买推荐交通事故成因分析互联网情绪指标和生猪价格的关联关系挖掘和预测依据用户轨迹的商户精准营销银行金融客户交叉销售分析气象关联分析银行营销方案推荐课程目录5.1.关联规则综述

5.1.1关联规则的基本概念

5.1.2关联规则提出的背景

5.1.3关联规则的原理

5.1.4关联规则的应用场景

5.1.5关联规则的分类5.2.关联规则挖掘常用算法5.3.关联规则实验5.4.本章小结5.5本章习题关联规则的分类关联规则类型可分为下列几种类型：基于规则中处理的变量的类别布尔型：学历=“本科”=>职业=“软件开发工程师”数值型：学历=“本科”=>平均收入=8000基于规则中数据的抽象层次单层关联规则：苹果笔记本电脑=>XGIMI投影仪多层关联规则：笔记本电脑=>XGIMI投影仪基于规则中涉及到的数据的维数单维：啤酒=>尿布多维：性别=“女”=>职业=“秘书”课程目录5.1.关联规则综述5.2.关联规则挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.关联规则实验5.4.本章小结5.5本章习题Apriori算法概述Apriori算法是一种以概率为基础的具有影响的挖掘布尔型关联规则频繁项集的算法。其利用循序渐进的方式，找出数据库中项目的关系，以形成规则。核心思想：项集的反单调性：如果一个项集是非频繁的，那么它的超集（superset）也一定是非频繁的。所谓频繁项集是指发生频率超过最小支持度的项集。Apriori算法的适用场景Apriori是一种‘先验’算法，通过该算法我们可以对数据集做关联分析，也就是可以在大规模的数据中寻找有趣关系的任务。这些关系可以有两种形式，分别是频繁项集和关联规则。频繁项集：经常出现在一块的物品的集合；关联规则：暗示两种物品之间可能存在很强的关系。从这些数据中能发现它们彼此之间有什么关系呢？Apriori算法原理及步骤Apriori的原理：如果某个项集是频繁项集，那么它所有的子集也是频繁的。即如果{0,1}是频繁的，那么{0},{1}也一定是频繁的。φ01230102031213230120130231230123230231230123非频繁图中给出了所有可能的项集，其中非频繁项集用灰色表示。由于集合{2,3}是非频繁的，因此{0,2,3}、{1,2,3}和{0,1,2,3}也是非频繁的，它们的支持度根本不需要计算。频繁项集的主要步骤：首先会生成所有单个物品的项集列表；

扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉；

对剩下的集合进行组合以生成包含两个元素的项集；

接下来重新扫描交易记录，去掉不满足最小支持度的项集，重复进行直到所有项集都被去掉。Apriori算法原理及步骤Apriori关联算法计算步骤计算步骤12345首先描述数据库，找出项数为1的频繁项集（即频繁的单项集），此时k=1从k频繁项集中生成k+1候选频繁项集扫描数据集，计算出每个候选频繁项集的支持度根据最小支持度要求，从中筛选出k+1频繁项集直到k+1达到用户指定的最大项数，或者k+1频繁项集为空迭代进行如果指定的最大项数为Kmax，则Apriori算法最多扫描数据集Kmax+1次Apriori算法python实现python实现算法示例：发现频繁项集找出关联规则阿里云DSW-Notebook建模环境的Apriori算法实现阿里云提供DSW-Notebook建模的环境，在这个环境里可以自己写python代码来实现Apriori算法。课程目录5.1.关联规则综述5.2.关联规则挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.关联规则实验5.4.本章小结5.5本章习题Partition算法概述虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。Partition算法——一种基于划分的方法Partition算法本质上是基于频集算法的一种优化方法Partition算法背景Apriori关联算法的特点对数据库的扫描次数过多

每次计算项集的支持度时，都对数据库中的全部记录进行了一遍扫描比较，这种扫描比较会大大增加计算机系统的I/O开销会产生大量的中间项集

在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素Partition算法原理及步骤几个基本概念项集：“属性-值”对的集合，一般情况下在实际操作中会省略属性。候选项集：用来获取频繁项集的候选项集，候选项集中满足支持度条件的项集保留，不满足条件的舍弃。频繁项集：在所有训练元组中同时出现的次数超过人工定义的阈值的项集称为频繁项集。极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。支持度：项集在所有训练元组中同时出现的次数。置信度：形如A->B，置信度为60%表示60%的A出现的同时也出现B。k项集：项集中的每个项有k个“属性-值”对的组合。Partition算法原理及步骤Partition算法的基本步骤（1）ACB先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集。对数据库从逻辑上进行划分例如划分为块A，生成块Ａ所有的频集例如划分为块B，生成块Ｂ所有的频集例如划分为块C，生成块Ｃ所有的频集Partition算法原理及步骤Partition算法的基本步骤（2）ACB对数据库从逻辑上进行划分把产生的频集合并，用来生成所有可能的频集块A的频集块Ｂ的频集块Ｃ的频集……所有可能的频集……Partition算法原理及步骤Partition算法的基本步骤（3）ACB对数据库从逻辑上进行划分所有可能的频集……最后计算这些项集的支持度计算这些项集的支持度课程目录5.1.关联规则综述5.2.关联规则挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.关联规则实验5.4.本章小结5.5本章习题DHP算法概述

DHP算法是Apriori算法的一种改进算法，其中使用的哈希算法选取很关键，一种简单的处理方法是将哈希表的大小设置为候选项集的数量，即每个候选项集都唯一对应一个哈希表地址，可以直接根据统计数判断候选项集是否为频繁项集。DHP算法背景尽管Partition算法相对Apriori有一定优化，但也存在一些不足：（1）由于各区段中产生频繁项集,并不表示在整个数据库中亦为频繁项集,因此会产生过多的频繁项集,导致第二次扫描数据库I/O次数频繁效率不佳。（2）为了减少在不同区段中重复产生频繁项集,而且为了能利用估计的方式提早结束挖掘,在系统做挖掘前必须先将数据库作排序。（3）由于分段对各区段数据库做挖掘,因此计算量会比Apriori算法更大。DHP算法原理及步骤算法设计思路

DHP算法描述算法描述1)D1=D;2)Addonecolumi_counttoD13)foreachtransactionst∈D14)t．i_count=countoft5)L1=search_frequent_l－itemset(D1);6)D2=apriori_d(D1);7)useDHPtogetL28)D3=apriori_d(D2);9)for(k=3;Lk－1≠φ;k++)10){Ck=new_apriori_gen(Dk);11)Lk={c∈Ck|c．countminsup;}12)Dk－1=apriori_d(Dk);}13)Answer=Uk;LkProcedureapriori_d(Dk)1)foreachtransactionst∈Dk2){ift．i_count＜kthen3){deletetfromDk}4)foreacht．item<>Lk5){deletet．itemfromt;6)t．i_count－－;}}7)returnDk;Procedurenew_apriori_gen(Dk)1)Ck=Φ2)foreachtransactionst∈Dk{3)forallksubsetscoft{4)ifc∈Ckthenc．count++;5)elsethen6){addctoCk;7)c．count=1;}}8)returnCk;}DHP算法特点优化了Apriori算法的性能瓶颈问题。

减少事务数据库的内容。减少数据库扫描，降低对磁盘的1/0访问。DHP算法减少了处理的候选集，是以附加一个Hash表的计算和数据库表的存储空间(为了进行数据库的修剪)为代价，换取执行时间的快速。生成候选集的个数，从而提高了查找每个事务中候选项目集的速度通过剪技技术减少整个数据库中事务的数量(即行数)和每个事务项中的个数(即每行包含的项目数量)，显著减少后面迭代计算量。候选集小可使更多内容在内存中进行，同时可以节省某些数据库扫描，通过推迟频繁项目集的确定减少磁盘1/0访问。课程目录5.1.关联规则综述5.2.关联规则挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.关联规则实验5.4.本章小结5.5本章习题MSApriori算法概述MsApriori算法是另一种优化办法。它的基本思想是设置多个支持度值，每个种类项都有一个最小支持度阈值，然后一个频繁项的最小支持度阈值取其中项集元素中的最小支持度值作为该项集的最小支持度值。这样，如果一个频繁项中出现了稀有项集，则这个项集的最小支持度值就会被拉低，如果又有某个项都是出现频率很高的项构成的话，则支持度阈值又会被拉高。当mis最小支持度阈值数组的个数只有1个的时候MSApriori算法就退化成了Apriori算法了。课程目录5.1.关联规则综述5.2.关联规则挖掘常用算法5.2.1Apriori算法5.2.2Partition算法5.2.3DHP算法5.2.4MSApriori算法5.2.5FP-Growth算法5.3.关联规则实验5.4.本章小结5.5本章习题FP-Growth算法概述FP-growth算法不产生候选集而直接生成频繁集的频繁模式增长算法，该算法采用分而治之的策略：第一次扫描数据库，把数据库中的频繁项目集压缩到一棵频繁模式树中，形成投影数据库，同时保留其中的关联信息；第二次扫描数据库，将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。FP-Growth算法原理及步骤FP树的构建交易编号所有购物项（排序后的）频繁项100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p其中，最小支持度阈值为3FP-tree的构建1.f,c,a,m,p2.f,c,a,b,m3.f,b4.c,b,p5.f,c,a,m,pnull{}c:1

b:1

p:1f:3b:1f:1c:1a:1m:1p:1f:4c:3a:3m:2p:2f:2c:2a:2b:1m:1项头表购物项

频率

f 4c 4a 3b 3m 3p 3FP-Growth算法原理及步骤创建树的根节点，用nul