《数据挖掘》课件 第6章 关联规则.pdf

数据挖掘高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则关联规则是一种描述性的而非预测性的方法，经常用于发现隐藏在大型数据集背后的.项集之间的有趣关联或相互关系。20世纪60年代,Hajek等人在早期研究中介绍了许多关联 规则学习的关键概念和方法，但是主要关注的是数学表达，而不是算法。20世纪90年代初，I BM公司Almaden研究中心的Agrawal等人将关联规则学习架构引入数据库社区,在超市内 的销售终端系统记录的客户交易大型数据库中寻找商品之间的联系规则，这些规则刻画了客 户购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则6.1 基本概念6.2 ApnoriM 法6.3 growth 算法6.4 其他关联规则算法6.5 实战：个人信用关联规则挖掘 习题6.1基本概念第六章关联规则6.1.1 购物篮分析：啤酒与尿布的经典案例早在20世纪80年代,沃尔玛超市就已经 将关联规则应用到了商品管理之中。沃尔玛 曾经对数据仓库中一年多的原始交易数据进 行了详细的分析，发现许多美国家庭都是妻 子在家照顾婴儿，丈夫去超市为婴儿买尿布。丈夫们在购买尿布时往往会顺便买两瓶啤酒 来犒劳自己。这一现象引起了沃尔玛的重视,沃尔玛调整了货架的位置，把尿布和啤酒摆 在相邻的位置，以便于年轻的爸爸们能顺利 地同时找到这两种商品。这一故事中的啤 酒与尿布的关系即为所谓的关联 性，而关联性的发掘和利用则是本章 所要讨论的关联规则挖掘。6.1基本概念第六章关联规则6.1.2 关联规则的概念关联规则挖掘是指从一个大型的数据集(dataset)中发现有趣的关联或相关关系，即从数据 集中识别出频繁出现的属性值集，也称为频繁项集，然后利用这些频繁项集创建描述关联关系规则 的过程。关联规则相关定义如下：1 项集(itemset)设I二国2，,im，是m个不同的项目的集合，每个ij称为一个项目。项目的集合I称为项集。其 元素的个数称为项集的长度，长度为k的项集称为k-项集。下表中每个商品就是一个项目，项集 I=面包，牛奶，尿布，啤酒，茶,I的长度川二6。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念2.关联规则(Association Rule)关联规则一般表示为X t Y的形式，左侧的项集X为先决条件，右侧项集Y为关联结 果，用于表示数据内隐含的关联性。例如：假定关联规则尿布一啤酒成立，则表 示购买了尿布的消费者往往也会购买啤酒这一商品。关联规则的有用性和可靠性，由规则的支持度(support),置信度(confidence)和提升度(lift)来度量。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念3.支持度(support)规则的支持度是指在所有项集中X,Y出现的可能性，即项集中同时含有X和Y的概率:support(X-Y)=P(X,Y)。该指标作为关联规则有用性的度量标准，衡量了所考察关 联规则在量上的多少。例如，如下表所示，当我们设置最小支持度阈值minsup=10%,关联规则尿布一啤酒的支持度support=看=40%,意味所分析的超市所有购买交易中的 40%显示尿布和啤酒被同时购买。由于关联规则尿布一啤酒的支持度大于最小支 持度阈值，因此，该规则是有效的。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念4.置信度(confidence)规则的置信度表示在关联规则的先决条件X发生的条件下，关联结果Y发生的概率,即含有X的项集中，同时含有Y的可能性：confidence-Y)=P(Y|X)=P(X,Y)/P(X)O o类似地，需要设置置信度最小阈值(mincon,Minimum Confidence)来 进一步筛选，最终生成满足需要的关联规则，即：confidence(X Y)mincone例如，如下表所示，当我们设置最小置信度阈值为50%,关联规则尿布一 啤酒的置信度confidence=：=66.7%,意味购买尿布的顾客中有66.7%也购买了啤 酒。由于关联规则尿布T啤酒的置信度大于最小置信度阈值，因此，该规则是可 靠的。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念5.提升度(lift)提升度表示在含有X的条件下同时含有Y的可能性，与没有这个条件下项集中含有 Y的可能性之比。即在Y自身出现可能性P(Y)的基础上，X的出现对于Y的出现P(Y/X)的 提升程度：lift(X t Y)=斗需=confidence(X-Y)/P(Y)。提升度与置信度同样用于 衡量规则的可靠性，可以看作是置信度的一种互补指标。例如：如果有2000个消费者，发现有1000人购买了茶叶，其中有900人同时购 买了咖啡，另100人没有，由于规则的置信度高达900/1000=90%,由此可能认为喜 欢喝茶的人同时也喜欢喝咖啡。但是，反过来观察，没有购买茶叶的另外1000人中同 样有900人购买了咖啡，因此可以得出结论，不爱喝茶的人也爱喝咖啡。这样看来，是否购买咖啡与有没有购买茶叶并没有关联，两者是相互独立的，其提升度为 90%/(900+900)/2000=1e由此可见，在某种程度上提升度弥补了置信度的缺陷，当 lift值为1时表示X与Y相互独立，X的出现对Y出现的可能性没有提升作用，而其值越大(1)则表明X对Y的提升程度越大，也即表明关联性越强。)6.1基本概念第六章关联规则6.1.2关联规则的概念5.提升度(lift)从下表中可以得出，lift(尿布-啤酒)=1.331。进一步说明了关联规则尿布 一啤酒”的可靠性。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶，茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念综上所述，一个关联规则的完整表示可以用以下关联规则表示：尿布 t 啤酒support=40%；confidence=66.7%表示购买了尿布的消费者往往也会购买啤酒这一商品，两个购买行为之间具有一 定的关联性。规则的支持度反映规则的有用性，支持度是指在所有项集中上述关联规 则的支持度为40%,意味所分析的超市所有购买交易中的40%显示尿布和啤酒被同时 购买。规则的置信度和提升度反映规则的确定性。本例中，置信度66.7%,意味购买 尿布的顾客66.7%也购买了啤酒。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶6.1基本概念第六章关联规则6.1.2关联规则的概念6.关联规则分类(1)布尔型和数值型关联规则(2)单层关联规则和多层关联规则(3)单维关联规则和多维关联规则本章重点讲解布尔型关联规则挖掘算法。7.关联规则挖掘步骤(1)找出所有的频繁项集(2)由频繁项集产生强关联规则对于事务数据库D中的任一频繁项集X,生成其所有的非空子集。对于每个非空子集x u X,若置信度confidence (X-x)mincon/那么 规则x-(X-x)是强关联规则。6.1基本概念第六章关联规则6.1.3频繁项集的产生格结构(lattice structure)常常用来表示所有可能的项集。一般来说，一个包含 k个项的数据集可能产生1个子集(不包括空集在内)，这些子集称为候选项集(candidate itemset)o例如：项集I=a,bed,e的项集格如下图所示，共有31个候选项集。6.1基本概念第六章关联规则6.1.3频繁项集的产生发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度计数，为 了完成这一任务，必须将每个候选项集与每个事务进行比较。如果候选项集包含在事 务中，则候选项集的支持度计数增加。假设事务数为N,事务的最大宽度为s,候选项 集数为M=2-1,该方法的时间复杂度为0(NMs),即需要进行O(NMs)次比较，开 销非常之大。为了降彳氐频繁项集产生的计算复杂度，可以有如下方法：(1)减少候选项集的数目。(2)减少比较次数。替代将每个候选项集与每个事务相匹配，可以使用更高级的 数据结构，或者存储候选项集或者压缩数据集，来减少比较次数。高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则6.1 基本概念612AprioriM6.3 P-gjowth 算;去6.4 其他关联规则算法6.5 实战：个人信用关联规则挖掘 习题6.2 Apriori算法第六章关联规则Apriori算法是Agrawal和R.Srikant于1994年提出的,为布尔关联规则挖掘频繁项 集的原创性算法。Apriori算法的核心是使用候选项集寻找频繁项集。621Apriori算法的频繁项集产生Apriori使用一种称为逐层搜索的迭代方法,k项集用于搜索(k+1)项集。首先,找出所有频繁1项集的集合L,然后用Li生成候选2项集的集合C2,最后，通过探查候选2 项集的集合来形成频繁2项集的集合1_2。以此类推，使用|_2寻找如此迭代,直至不能 找到频繁k项集为止。Apriori算法中提高频繁项集逐层搜索效率的方法是减少频繁项集产生时需要探查的 候选项集的个数,该方法基于先验性质(Apriori property),从而达到压缩搜索空间的 目的。6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生先验性质：频繁项集的所有非空子集也一定是频繁项集。该先验性质可引申出两个结论：结论1：若肪频繁项集，则并勺所有子集都是频繁项集。结论2:若肪非频繁项集,则并勺所有超集均为非频繁项集。6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生利用先验性质，我们在使用频繁(匕1)项集的集合Lg寻找频繁k项集的集合1_卜时分两个 过程：连接步和剪枝步。(1)连接步：L-与其自身进行连接,产生候选k项集的集合Cq L-中某个元素与其中另一个元素 可以执行连接操作的前提是它们中有(匕2)个项是相同的，也就是只有一个项是不同的。例 如：项集何上与匕地有共同的k，连接之后产生的项集是有不色，反之，项集01，场与。，坨，没有1个共同的项集，不能进行连接操作。(2)剪枝步：候选k项集的集合Ck中的元素可以是频繁项集，也可以不是。但所有的频繁k项集一定 包含在Ck中,所以,Ck是Lk的超集。扫描事务集D,计算Ck中每个候选k项集出现的次数,所有出现次数大于等于最小支持度计数的候选k项集的集合便组成频繁k项集的集合Lq最小支持度计数是最小支持度阈值与事务集D中事务总数的乘积，有些书上也称最小 支持度阈值为相对最小支持度，最小支持度计数为绝对最小支持度。)6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生例6.1 Apriori算法。以下表的某超市交易数据为例，用Apriori算法发现该超市交易的频 繁项集，设定最小支持度计数为3（相对支持度minsup=30%）。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒，牛奶，茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶&6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生例 6.1 Apriori 算法。(1)第一次迭代时，每个项都是候选1项集的集合a的成员。算法扫描一次所有的事务,对每个项的出现频次计数。(2)由满足最小支持度的候选1项集组成频繁1项集的集合Li。注意，由于候选项集茶 的支持度计数小于3,因此，生成的频繁1项集的集合L不包含候选项集茶。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒,牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶(1)J1项集支持度计数候选的支持度 计数与最小支 持度计数比 较，得到Li扫描D,对每个候 选计数面包件奶n尿布6啤酒5茶2(2)Li项集支持度计数面包5件奶7尿布6啤酒5&6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生例 6.1 Apriori 算法。(3)发现候选2项集的集合C2。首先是连接步，使用连接LixLi，产生候选2项集的集合 C2o其次是剪枝步，压缩候选项集空间，由于这些候选项集的每个子集都是频繁的，在剪 枝步，没有候选项集从C2中删除。最后，计算C2中每个候选项集的支持度计数。(4)确定频繁2项集的集合1_2。保留C2中支持度计数大于等于3的候选2项集，形成频繁2 项集的集合|_2。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒,牛奶,茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶(3)C2(4)L2由Li产生项集支持度计数候选的支持度 计数与最小支项集支持度计数面包,牛奶3面包,牛奶3候速C2，同时，候持度计数比 较，得到L2选C2计数面包,尿布3面包,尿布3面包,啤酒1牛奶,尿布4牛奶,尿布4牛奶,啤酒4牛奶,啤酒4尿布，啤酒4尿布，啤酒4)6.2 Apriori算法第六章关联规则621Apriori算法的频繁项集产生例 6.1 Apriori 算法。(5)发现候选3项集的集合C3。首先是连接步，使用连接L2 x L2,产生候选3项集的集 合C3。其次是剪枝步，压缩候选项集空间，其中，由频繁2项集面包，尿布,尿布，啤 酒进行连接生成的3项集面包，尿布，啤酒从候选项集的集合C3中删除，因为，其子集 面包，啤酒是非频繁的。最后，计算C3中每个候选项集的支持度计数。(6)确定频繁3项集的集合L3。保留C3中支持度计数大于等于3的候选3项集，形成频繁3 项集的集合到此为止，频繁3项集的集合只有一个频繁3项集，停止迭代。交易号TID顾客购买的商品交易号TID顾客购买的商品T1面包，牛奶，茶T6面包，牛奶，啤酒，尿布，茶T2面包，尿布，啤酒，茶T7啤酒,牛奶，茶T3牛奶，尿布，啤酒T8面包，茶T4面包，牛奶，尿布，茶T9面包，尿布，牛奶，啤酒，茶T5面包，尿布，牛奶T10面包，牛奶c3候选的支持度 计数与最小支 持度计数比 较，得到L3L3由L2产生 候选C3,同时，候 选C3计数-项集支持度计数项集支持度计数面包，牛奶，尿布面包，牛奶，啤泗牛奶，尿布，啤酒213牛奶,尿布,啤酒36.2 Apriori算法第六章关联规则622Apriori算法描述Apriori算法的具体实现如下：宽度优先搜索整个项集空间,从k=0开始,迭代产生 长度为k+1的候选项集的集合Ck+i。候选项集是其所有子集都是频繁项集的项集。J由I。中所有的项构成，在第k层产生所有长度为k+1的项集。这由两步完成：第一步，Lk自连 接。将1_卜中具有相同（匕1）前缀的项集连接成长度为k+1的（候选）项集。第二步是剪枝，如 果项集的所有长度为k的子集都在1_卜中，该项集才能作为候选项集被加入Ck+i中。为了计 算所有长度为k的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选k-项集的支持度计 数加L所有频繁k项集被加入1_卜中。此过程直至Ck+i等于空集时结束。对于海量数据，Apriori算法的时空复杂度都不容忽视。空间复杂度：如果L1数量达到 104的量级，那么C2中的候选项将达到I CT的量级。时间复杂度：每计算一次Ck就需要扫 描一遍数据库。高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则6工基本概念6.2 Apri Oi 算法63FT-growthM6.4 其他关联规则算法6.5 实战：个人信用关联规则挖掘 习题6.3 FP-growth算法第六章关联规则在许多情况下，Apriori算法显著地压缩了候选项集的规模,并产生很好的性能。但是,该算法存在以下不足：(1)可能产生大量频繁项集。例如，如果有I O4个频繁1项集，贝Spriori算法需要产 生多达107个候选2项集。(2)可能需要重复地扫描整个数据库，通过模式匹配检查一个很大的候选集合。检查 数据库中每个事务来确定候选项集支持度的开销很大。FP-growth算法采取分而治之的思路：首先,将代表频繁项集的数据库压缩到一棵频 繁模式树(Frequent Pattern tree,简称FP树)中,该树仍然保留项集的关联信息。然 后，把这种压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库)，每个 数据库关联一个频繁段或模式段，并分别挖掘每个条件数据库。对于每个模式片 段，只需要考察与它相关联数据集。因此，随着被考察的模式的增长，这种方法可 以显著地压缩被搜索的数据集的大小。由上可知，FP-growth算法包含两个步骤：第一步，构造FP树；第二步,在FP树上挖掘频繁项集。6.3 FP-growth算法第六章关联规则6.3.1构造FP树右表所示为某事务集合，以此小案例说明FP 树的生成过程。事务数据集排序：扫描该事务数据集，确定该 事务数据集中包含的所有项的集合I及每个项的支 持度计数I&S=a:3,b:3,c:4,d:l,e:l,f:4,g:l,h:l,i:l z j:l,k:l,1:2,m:3,n:l,o:2,p：3,s:lo针对得到的集合I,丢弃非频繁项，并 将频繁项按照支持度的递减排序，结果集或表记 为L,有L=f:4,c:4,a:3,b:3,m:3,p:3,1:2,o:2o最后，对事务数据集中的项集逐一扫描，每个项集剔除非频繁项后，余下的频繁项按照L的 降序重新排列（见右表第三列）。TID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,cl 皿 of,c,a,b,m,l,o300b,fhj、of,b,o400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,l)6.3 FP-growth算法第六章关联规则6.3.1构造FP树接下来开始构建FP树，先设定FP树的根节点 为null。对事务数据集进行第二次扫描，不断构 建FP树的分支：(1)读入第一个事务 f,c,a,m,p,创建标记 为f,c,a,m,p的节点，然后形成nullTf c t a t m t p路径，对该事务编码。该路径上的 所有结点的频度计数为1。TID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,tm,of,c,a,b,m,l?o300；b,f,hj,o；f,b,o)400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,lnullc：lOAm:lC JP：16.3 FP-growth算法第六章关联规则6.3.1构造FP树(2)读入第二个事务 f，c,a,b,m,l,o,第二个事务与第 一个事务共享前缀,所以第二个事务的路径 null TfCTa bTrn lT o与第一个事务的路径 nW t f-c t a部分重叠。所以结点f,c,a的频度计数 增加为2,新创建的b,m,I,。结点的频度计数等于1。TID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,tm,of,c,a,b,m,l?o300；b,f,hj,o；f,b,o)400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,lnulld的川卜m啕嘲1 出礴脚渊0：16.3 FP-growth算法第六章关联规则6.3.1构造FP树(3)读入第三个事务f,b,o,第三个事务与前两个 事务共享前缀,所以第三个事务的路径nun T fT b T。与第一个和第二个事务的路径nun T倍B分重叠。所以结点f的频度计数增加为3,新创建的b,。结点的频 度计数等于1。TID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,tm,of,c,a,b,m,l?o300；b,f,hj,o；f,b,o)400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,l6.3 FP-growth算法第六章关联规则6.3.1构造FP树(4)读入第四个事务 c,b,p,该事务与前三个事务 无共享前缀，所以创建标记为c,b,p的结点，然后形 成null-c-b-p路径，对该事务编码。该路径上的所 有结点的频度计数为1。TID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,tm,of,c,a,b,m,l?o300；b,f,hj,o；f,b,o)400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,l)6.3 FP-growth算法第六章关联规则6.3.1 构造FP树(5)读入第五个事务 f，c,a,m,p,1,该事务与第一个 事务共享前缀,所以第五个事务的路径 null TfCTaTm pT 1与第一个事务的路径null t fTCTa mT p重叠。故路径null Tfc aTmT P上的结点f,c,a,m,p的频度次数各增1。新创建的I 结点的频度计数等于1 OTID项集删除非频繁1项 并重新排序后的项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,tm,of,c,a,b,m,l?o300；b,f,hj,o；f,b,o)400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p,l6.3 FP-growth算法第六章关联规则6.3.2 挖掘FP树FP树的挖掘过程为：从长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一 个子数据库，由FP树中与该后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。)6.3 FP-growth算法第六章关联规则6.3.2挖掘FP树(1)对FP树的项头表从表尾向表头逆序逐一扫描，当扫描到某个频繁1项磔寸，由其结点链得 至(J F P树中以i 结尾的前修殳路径。例如，节向中,城学赢表的频繁1项。，由FP树可得到以。结尾的前缀路径。见图(a)op:lC：1b:lnul 1f:4c:3a:3b:1o:1b:lm:11:1o：1(a)以。结尾的前缀路径6.3 FP-growth算法第六章关联规则6.3.2挖掘FP树(2)以频繁项ij在该路径上的支持度计数为依据，更新前缀路径上结点的支持度计数。根据已 更新支持度计数的箭缀路径，可以得到频繁项ij的条件模式基。如图(b)所示，首先依据结点。在该 路径上的支持度更新前缀路径上结点的支持度计数。在此基础上，得到结点。的条件模式基(3)构建条件FP树。对频繁项的条件模式基,按照上一节的构造FP树的方法来构造条件FP 树。如图所示，得到结点。的条件FP树。该树只有一条路径。(a)以。结尾的前缀路径a:1|生成条件、I模式产/，的条件模式基:f,C,a,b,m,1f:2m:1(b)以结点0的支持度计数为依据，更新前缀路径上的支持度计数，在此基础上得到条件模()箝点0的条件FP树b:l构建条n 2 2)6.3 FP-growth算法第六章关联规则6.3.2挖掘FP树(4)构建频繁项集。如果该条件FP树有多条路径,则继续迭代,构造条件FP树(详细说明 见步骤(5)。否则，如果该条件FP树只有一条路径，则直接求以该结点结尾的频繁项集。如 图(c)所示，结点。的条件FP树只有一条路径f:2,b:2。由结点。与f,b进行连接,产生频繁 模式代。:2,b,o:2，他。：20(a)以。结尾的前缀路径f,C,a,b,m,1)If,b).(b)以结点0的支持度计数为依据，更新前缀 路径上的支持度计数，在此基础上得到条件模 式基(c)结点0的条件FP树6.3 FP-growth算法第六章关联规则6.3.2挖掘FP树(5)如果该条件FP树有多条路径,则继续迭代,构造条件FP树。以结点b为例，其条件FP树有路径null-f-c和null-,需要继续迭代。迭代思路如下：采 用分治策略将一个问题划分为较小的子问题，从而发现某个特定后缀结尾的所有频繁项集。对于 结点b,则分别考虑以cb为后缀的条件FP树和以fb为后缀的条件FP树。以cb为后缀的条件FP树构造如下：以结点b的FP树为基础，考虑以cb为后缀的前缀路径，如 图(d)。处理c的前缀路径后,只发现项集c,b是频繁的,也即cb为后缀的条件FP树为空。以fb为后缀的条件FP 树构造如下：以结点b的 FP树为基础，考虑以fb为 后缀的前缀路径，如图6-7(e)。处理f的前缀路 径后,只发现项集f,b是 频繁的，也即fb为后缀的 条件FP树为空。(C)以fb结尾的前缀路径(d)以cb结尾的前缀路径(c)结点b的条件FP树6.3 FP-growth算法第六章关联规则6.3.3 FP-growth算法(1)构造项头表：扫描数据库 一遍，得到频繁项的集合F和每个频 繁项的支持度。把F按支持度递降排 席，记为L。(2)构造原始FP-Tree:把数据 库中每个事务的频繁项按照L中的顺 序进行重排。并按照重排之后的顺序 把每个事务的每个频繁项插入以nu 11 为根的FP-Tree中。如果插入时频繁 项节点已经存在了，则把该频繁项节 点支持度加1；如果该节点不存在，则创建支持度为1的节点，并把该节 点链接到项头表中。(3)调用FP-growth(Tree,null)开始进行挖掘。伪代码如下：procedure FP_growth(7c a)if ee含单个略径Pthenfor路径冲结点的每个组合(记作。)产生模式ala,其支持度supportb 中结点的最小支持度；elsefor each y在勺头部(按照支持度 由低到高顺序进行扫描乂产生一个模式。=dUd,其支持度 support=a,sup port;构造加勺条件模式基,然后构造华勺 条件FP-tree;if ee不为空then调用 FP-growth Tree.b;高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则6工基本概念6.2 Apri Oi6.3 FP-growth 算法6.4 其他关联规则算法6.5 实战：个人信用关联规则挖掘 习题，6.4其它关联规则算法第六章关联规则641约束性关联规则 1相关概念及定义设i=ii，i2J 3，,ij是所有项目（items）的集合,设D为一个事务数据库,其中的每个务T为一个项集,且Tu lo定义：基于项约束条件C的关联规则就是形如X2Y的蕴涵式,其中Xul,Yul,XPI Y=，且X2Y成 立的条件是：1）它具有支持度s,即交易数据库中至少有s%的记录包含XUY;2）它具有置信度c,即在交易数据库中包含X的记录至少有c%同时也包含Y;3）它必须满足项约束条件C。设C为I上的一个布尔表达式，将C转化为DNF形式，形如：dlvd2vd3v.vdm,其中每个di形如：di=ailAai2A.Aaim,aijelo，6.4其它关联规则算法第六章关联规则641约束性关联规则 2.相关算法及改进Multiplejoins.Recorder和Direct算法是最早提出的项约束算法，这些算法在生成频繁项集 的过程中，利用项的约束条件对项集进行筛选，得出关联规则。在此基础上，后来的研究者利用 频繁项集和非频繁项集的性质，将项约束条件划分为单调性约束、反单调性约束以及简洁约束等 几类，运用递归的思想进行剪枝得出所需的频繁项集，如ElcatA9、AMMC吸CSARQ等算法。随着项约束算法研究的深入，更多的约束方法和思想加入了项约束算法中,如 DFTFHA、VCMU4、mSEB等算法。这些算法利用FP-tree或概念格的思想，采用垂直数据形 式表示数据集和深度优先的挖掘策略得出关联规则以6-1刀。止匕外，还有基于二进制约束的关联规则 算法、基于权重和时序约束的关联规则算法a-19等。&6.4其它关联规则算法第六章关联规则642增量式关联规则1相关概念及定义根*居实际维需求,关联规则的更新问题可以分为以下几种情况：Q)事务数据库不变，最小支持度发生变化时，关联规则的高效更新问题；(2)最小支持度不变，一个事务数据集小。添加到事务数据库D中去时，如何生成最新事务数据库 DUdi中的关联规则；(3)最小支持度不变，从事务数据库D中删除一个事务数据集d22uD)后,如何高效地生成事务数 据库D-cl2中的关联规则。至于其它情况，可由上述三种情况组合而成，因此，这三种情况是更新问题的基础和核心。&6.4其它关联规则算法第六章关联规则642增量式关联规则2.相关算法及改进Cheung提出了 FUP算法，在此基础上Cheung又提出了改进算法FUP2算法,可以处理数据集 减少是的频繁项挖掘，而面向增量数据集时，算法和FUP相似。UWEP算法mi与FUP算法类似，但 此算法采用提前对原频繁项集剪枝的策略，在k频繁项集挖掘时，候选集在增量数据集上产生。而 针对在每个时间节点，都有新数据产生的问题，文献田提出了YAMI算法。针对支持度变小时，频 繁模式也将增加，冯玉才内提出了I UA算法。周海岩”最早论证了I UA算法存在误剪枝问题，提出 了改进算法NEWI UA。以上这些算法都是基于Apriori算法提出的,还有一些算法则是基于FP-growth算法。比较典型的 有Koh25提出的AFPI M算法，对增加的数据集调整树的结构。朱玉全团提出基于FP树的,面向支 持度变化的FI UA1算法和数据量增加的FI UA2算法。易彤2刀提出的I FP-Growth算法整合了支持度 变化和数据集变化情况，提出的I FP树在调整时通过调整子树来完成。I ACAI算法冏采用提前缩减 数据集的策略，即将不含任何频繁项的空事务提前剪去。&6.4其它关联规则算法第六章关联规则6.4.3多层关联规则1.多层关联规则的定义设仁0正，,设是由称作项(I tem)的ik(k=l,2，,m)构成的项的集合,项的集合上的概括层 次关系用概念层次树T表示，结点表示项或项的概括。若从结点P到Q之间有弧，则称P是 Q的祖先(P是Q的概括)，Q是P的子孙。祖先、子孙关系具有传递性，如果B是D的祖先，A是B的祖先,贝蛆是D的祖先。&6.4其它关联规则算法第六章关联规则6.4.3多层关联规则2.多层关联规则挖掘步骤给定一个事务数据库D和项集合上的概括层次树T,多层关联规则挖掘的任务就是产生支持度和置 信度分别大于用户给定的最小支持度(minsup)和最小可信度(minconf)的关联规则。多层关联规则挖掘一般包含三个基本的步骤：(1)根据事务数据库D和D上的概念层次树T,挖掘出所有的频繁模式FP=X|Xcl/support(X)minsup;(2)由频繁模式产生强关联规则，由频繁模式产生关联规则的方法如下：对于每个频繁项集t,产生t的所有非空子集。对于t的每个非空子集s,如果support(t)/support(s)2minconf,则输出规则s=(t-s)二其中,m i n co nf是最小置信度阈值。(3)从所有的多层关联规则中删除用户不感兴趣的、冗余的规则。在这三个步骤中，第二步和第三步相对容易，多层关联规则挖掘的总体性能由第一步决定。&6.4其它关联规则算法第六章关联规则6.4.3多层关联规则3.常用算法及改进在用于多层关联规则挖掘的经典算法中，以Cumulate的和ML-T2L13。最为著名。Cumulate算法 能进行多层及跨层次频繁模式的挖掘，但该算法仅是将源数据放在同一层次级别上考虑的普遍化 关联规则挖掘算法；ML-T2L1算法采用自顶向下方式进行逐层挖掘，但不支持跨层次的挖掘。这2 种算法都基于Apriori算法思想，因此存在着与Apriori算法相同的缺陷。MLAR-FPR算法是以FP-growth算法为基础而构建的，通过把每个事务中每个项的全部祖先加入 到该条事务中，并删除重复的祖先，从而保证了算法能够发现多层关联规则。Ada-FPB2是基于 FP-growth算法的多层多维频繁模式挖掘算法，采用了多支持度约束。但如果原始数据只是最低 抽象层的项，则无法挖掘出隐藏在层间的关联规则。研究者们还提出了许多其他的改进算法，文 献阳提出了一种多支持度挖掘算法；文献34提出了一种加权的关联规则挖掘方法；文献35提出了 基于遗传算法的多层关联规则改进算法；文献36则提出了一种并行化挖掘多层关联规则的算法。高级大数据人才培养丛书之一，大数据挖掘技术与应用第六章关联规则6工基本概念6.2 Apri Oi6.3 FP-growth 算法6.4 其他关联规则算法6.5 实战：个人信用关联规则挖掘习题&6.5实战：个人信用关联规则搀掘第六章关联规则6.5.1 背景与挖掘目标面对激烈的市场竞争，各大银行为了挖掘更多有用的 客户信息，对现有银行客户关系管理系统中存有大量的客 户数据进行客户细分，客户细分需要采用专门的方法对这 些数据进行合理的处理，挖掘有用的客户信息。本次案例通过数据挖掘工具Weka，结合机器学习中 的关联规则Apriori算法,有效的挖掘个人信用数据中各个 属性之间的关联规则。&6.5实战：个人信用关联规则搀掘第六章关联规则6.5.2 分析方法与过程本案例数据来源于www.tipdm.org,银行客户关系管理系统中存有大量的客户数据,数据抽取、数据预处理、数据转换等步骤省略。包含的数据属性有：年龄、性别、地区、收 入、婚姻状态、是否生育、是否有车、按揭时是否有抵押、是否有股权计划。对个人信用数 据讲行相关性分析，利用Aoriori算法挖掘个人信用数据中各个属性之间的关联蜘则0agesexregionincomemarriedchi 1 cr encarmortgagepep48FEMALEINNER_CITY17546 NOYESNONOYES40MALETOWN30085.1YESYESYESYESNO51FEMALEINNER_CITY16575.4YESNOYESNONO23F