1、第第5章章 关联分析关联分析5.1 5.1 关联分析的概念关联分析的概念5.2 5.2 AprioriApriori算法算法5.3 5.3 频繁项集的紧凑表示频繁项集的紧凑表示5.4 FP-growth5.4 FP-growth算法算法5.5 5.5 多层关联规则的挖掘多层关联规则的挖掘5.6 5.6 其他类型的关联规则其他类型的关联规则5.7 5.7 挖掘关联规则的示例挖掘关联规则的示例关联分析是指关联规则挖掘，它是数据挖掘中一个关联分析是指关联规则挖掘，它是数据挖掘中一个重要的、高度活跃的分支。重要的、高度活跃的分支。目标：目标：发现事务数据库中不同项（如顾客购买的商发现事务数据库中不同项
2、（如顾客购买的商品项）之间的联系，这些联系构成的规则可以帮助用户品项）之间的联系，这些联系构成的规则可以帮助用户找出某些行为特征（如顾客购买行为模式），以便进行找出某些行为特征（如顾客购买行为模式），以便进行企业决策，企业决策， 在为某传统蜂蜜品牌做电商分销渠道分析时发现，电商平在为某传统蜂蜜品牌做电商分销渠道分析时发现，电商平台上蜂蜜产品非常多，低端市场难以快速打开局面，高端台上蜂蜜产品非常多，低端市场难以快速打开局面，高端市场又被进口品牌抢占，可以说电商蜂蜜市场竞争十分激市场又被进口品牌抢占，可以说电商蜂蜜市场竞争十分激烈。如果以直接销售的形式进入市场难以达到理想目标。烈。如果以直接销售的
3、形式进入市场难以达到理想目标。 如何解决这个问题呢？如何解决这个问题呢？ 转变思路，去做相关行业的分析挖掘。转变思路，去做相关行业的分析挖掘。 啤酒尿布案例。啤酒尿布案例。 获取淘宝全网数据，找出客户同时购买蜂蜜和其他产品的获取淘宝全网数据，找出客户同时购买蜂蜜和其他产品的交易数据，并依此建立事务数据库。依据设定的最小支持交易数据，并依此建立事务数据库。依据设定的最小支持度阈值，根据以下思路进行分析。度阈值，根据以下思路进行分析。 使用了使用了FP-growthFP-growth算法来进行关联分析。算法来进行关联分析。 1.1.频繁项集产生：其目标是发现满足最小支持度阈值的所频繁项集产生：其目
4、标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。有项集，这些项集称作频繁项集。 2.2.规则的产生：其目标是从上一步发现的频繁项集中提取规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则。所有高置信度的规则，这些规则称作强规则。 具体步骤为可分为：具体步骤为可分为： a.a.扫描一遍数据库，获取所有频繁项，删除频率小于最小扫描一遍数据库，获取所有频繁项，删除频率小于最小支持度的项。在此操作的过程中，还可以得到每个项的出支持度的项。在此操作的过程中，还可以得到每个项的出现频率，供后续步骤使用。现频率，供后续步骤使用。 b.b.第二次扫描数据库，在第
5、一次处理完成的结果基础上，第二次扫描数据库，在第一次处理完成的结果基础上，构建构建 FP-Tree FP-Tree。 c.c.得到了得到了 FP-Tree FP-Tree 树之后，再遍历整棵树获取满足一定树之后，再遍历整棵树获取满足一定置信度的关联规则。置信度的关联规则。 经过分析发现经过分析发现购买蜂蜜购买蜂蜜的客户的客户同时购买同时购买滋补营养品、美容滋补营养品、美容护肤、零食、保健品、个人护理等高达护肤、零食、保健品、个人护理等高达 70 70 多个类目多个类目的产的产品。也就是说，品。也就是说， 这这 70 70 多个类目的客户都是蜂蜜产品的多个类目的客户都是蜂蜜产品的潜在消费者。潜在
6、消费者。 其中其中茶饮类目关联最强茶饮类目关联最强，而在茶饮类目中，花茶在功效上，而在茶饮类目中，花茶在功效上与蜂蜜最搭。找到花茶类目之后，我们再分析了一下客群与蜂蜜最搭。找到花茶类目之后，我们再分析了一下客群的消费习惯，大概都是消费能力和消费观念都很前的年轻的消费习惯，大概都是消费能力和消费观念都很前的年轻人。有了这些数据支撑，我们再对产品进行价格和包装定人。有了这些数据支撑，我们再对产品进行价格和包装定位，卖花草茶的分销商在一个月销量就排在蜂蜜销售页面位，卖花草茶的分销商在一个月销量就排在蜂蜜销售页面前列了，这也大大带动了旗舰店的流量提升。前列了，这也大大带动了旗舰店的流量提升。5.1.1
7、 5.1.1 事务数据库事务数据库定义定义5.15.1 设设I=i1，i2，im是一个全局项的集合，其是一个全局项的集合，其中中ij（1jm）是项（）是项（item）的唯一标识，）的唯一标识，j表示项的序号。表示项的序号。事务数据库事务数据库（transactional databases）D=t1，t2，tn是一个事务（是一个事务（transaction）的集合，每个事务）的集合，每个事务ti（1in）都）都对应对应I上的一个子集，其中上的一个子集，其中ti是事务的唯一标识，是事务的唯一标识，i表示事务的表示事务的序号。序号。定义定义5.25.2 由由I I中部分或全部项构成的一个集合称为中
8、部分或全部项构成的一个集合称为项集项集（itemsetitemset），任何非空项集中均不含有重复项。），任何非空项集中均不含有重复项。如如I1=i1，i3，i4就是一个项集。就是一个项集。为了算法设计简单，本为了算法设计简单，本章中除特别声明外，假设所有项集中列出的各个项均按项序章中除特别声明外，假设所有项集中列出的各个项均按项序号或字典顺序有序排列。号或字典顺序有序排列。购物篮问题：购物篮问题：设设I是全部商品集合，是全部商品集合，D是所有顾客的购物是所有顾客的购物清单，每个元组即事务是一次购买商品的集合。清单，每个元组即事务是一次购买商品的集合。如表如表5.1所示是一个购物事务数据库的示
9、例，其中，所示是一个购物事务数据库的示例，其中，I=i1，i2，i3，i4，i5，D=t1，t2，t3，t4，t5，t6，t7，t8，t9，t1=i1，i2，i5，t9=i1，i2，i3。TIDTID购买商品的列表购买商品的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i3购物篮问题购物篮问题是关联分析的一个典型例子，每种商品有一是关联分析的一个典型例子，每种商品有一个布尔变量，顾客购买某商品，对应的布尔变量为个布尔变量，顾客购买某商品，对应的布尔变量为true，否，否则为则为fals
10、e，可以将一个事务看成是一个购物篮，购物篮可用，可以将一个事务看成是一个购物篮，购物篮可用一个为这些变量指定值的布尔向量表示。一个为这些变量指定值的布尔向量表示。例如，例如，t1=i1，i2，i5，表示对应，表示对应i1、i2、i5的变量取值为的变量取值为true，其余为，其余为false。可以分析这些布尔向量，得出反映商品。可以分析这些布尔向量，得出反映商品频频繁关联或同时购买繁关联或同时购买的购买模式。这些模式可以用关联规则的购买模式。这些模式可以用关联规则的形式表示。的形式表示。 但是我们如何定义这些关系呢？当寻找但是我们如何定义这些关系呢？当寻找频繁关联或同时购买模式时，频繁（时，频繁
11、（frequent）的定义是什么？）的定义是什么？ 支持度（支持度（support）：）：该数据集中包含该项集的记录所占该数据集中包含该项集的记录所占的比例的比例。从上面例子中可以得到：。从上面例子中可以得到：豆奶豆奶的支持度是的支持度是4/5，豆奶，尿布豆奶，尿布的支持度是的支持度是3/5。支持度是针对项集来说的，。支持度是针对项集来说的，只保留满足最小支持度的项集。只保留满足最小支持度的项集。 可信度（可信度（confidence）：是针对一条诸如）：是针对一条诸如尿布尿布-葡萄酒葡萄酒的关联规则来定义的。这条规则的可信度被定义为的关联规则来定义的。这条规则的可信度被定义为: “支持度支持
12、度(尿布，葡萄酒尿布，葡萄酒)/支持度支持度(尿布尿布)”5.1.2 5.1.2 关联规则及其度量关联规则及其度量1. 1. 关联规则关联规则关联规则表示项之间的关系，它是形如关联规则表示项之间的关系，它是形如XY的蕴涵表的蕴涵表达式，其中达式，其中X和和Y是不相交的项集，即是不相交的项集，即XY=，X称为规则称为规则的前件，的前件，Y称为规则的后件。称为规则的后件。例如，例如，cereal，milkfruit关联规则表示的含义是购关联规则表示的含义是购买谷类食品和牛奶的人也会购买水果，它的前件为买谷类食品和牛奶的人也会购买水果，它的前件为cereal，milk，后件为，后件为fruit，有时
13、也表示为，有时也表示为cereal，milkfruit或或cereal and milkfruit等形式。等形式。2. 2. 支持度支持度定义定义5.35.3 给定一个全局项集给定一个全局项集I和事务数据库和事务数据库D，一个项集，一个项集I1 I在在D上的支持度是包含上的支持度是包含I1的事务在的事务在D中所占的百分比，即中所占的百分比，即其中，其中，|表示表示集合的计数，即其中元素个数。对于形集合的计数，即其中元素个数。对于形如如XY的关联规则，其支持度定义为：的关联规则，其支持度定义为：采用概率的形式等价地表示为：采用概率的形式等价地表示为：support(XY)=P(XY)显然，显然，
14、support(XY)与与support(YX)是相等的。例如，是相等的。例如，在表在表5.1的事务数据库的事务数据库D中，总的元组数为中，总的元组数为9，同时包含，同时包含i1和和i2的的元组数为元组数为4，则，则support(i1i2)=support(i2i1)=4/9=0.44，这里，这里相当于相当于X=i1，Y=i2。TIDTID购买商品的列表购买商品的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i3支持度是一种重要性度量支持度是一种重要性度量，因为低支持度的规则可能，因
15、为低支持度的规则可能只是偶然出现。只是偶然出现。从实际情况看，低支持度的规则多半是没有意义的。从实际情况看，低支持度的规则多半是没有意义的。例如，顾客很少同时购买例如，顾客很少同时购买a、b商品，想通过对商品，想通过对a或或b商商品促销（降价）来提高另一种商品的销售量是不可能的。品促销（降价）来提高另一种商品的销售量是不可能的。3. 3. 置信度置信度定义定义5.45.4 给定一个全局项集给定一个全局项集I和事务数据库和事务数据库D，一个定，一个定义在义在I和和D上的关联规则形如上的关联规则形如XY，其中，其中X、YI，且，且XY=，它的置信度（或可信度、信任度）是指包含它的置信度（或可信度、
16、信任度）是指包含X和和Y的事务数与的事务数与包含包含X的事务数之比，即：的事务数之比，即：采用概率的形式等价地表示为：采用概率的形式等价地表示为：confidence(XY)=P(Y|X)其中其中P(Y|X)表示表示Y在给定在给定X下的条件概率。下的条件概率。置信度确定通过规则进行推理具有的可靠性置信度确定通过规则进行推理具有的可靠性。对于规则。对于规则XY，置信度越高，置信度越高，Y在包含在包含X的事务中出现的可能性越大。的事务中出现的可能性越大。显然显然confidence(XY)与与confidence(YX)不一定相等。不一定相等。例如例如，confidence(i2i1)=4/6=0
17、.67，support(i1i2)=4/7=0.57。TIDTID购买商品的列表购买商品的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i3对于形如对于形如XY关联规则，关联规则，support(XY)confidence(XY)总是成立的。总是成立的。一个规则的支持度总是不大于其置信度。一个规则的支持度总是不大于其置信度。定义定义5.55.5 给定给定D上的最小支持度（记为上的最小支持度（记为min_sup）和最小）和最小置信度（记为置信度（记为min_conf），分别称为最小支持度
18、阈值和最小置），分别称为最小支持度阈值和最小置信度阈值，同时满足最小支持度阈值和最小置信度阈值的关联信度阈值，同时满足最小支持度阈值和最小置信度阈值的关联规则称为规则称为强关联规则强关联规则。也就是说，某关联规则的最小支持度也就是说，某关联规则的最小支持度min_sup、最小置、最小置信度信度min_conf，则它为，则它为强关联规则强关联规则。说明：说明：由关联规则作出的推论并不必然蕴涵因果关系，由关联规则作出的推论并不必然蕴涵因果关系，它只表示规则前件和后件中的项明显地同时出现。它只表示规则前件和后件中的项明显地同时出现。5.1.3 5.1.3 频繁项集频繁项集定义定义5.65.6 给定全
19、局项集给定全局项集I和事务数据库和事务数据库D，对于，对于I的非空的非空子集子集I1，若其支持度大于或等于若其支持度大于或等于min_sup，则称，则称I1为频繁项为频繁项集（集（Frequent Itemsets）。）。若若I包含包含m个项，那么可以产生个项，那么可以产生2m个非空项集。个非空项集。例如，例如，I=i1，i2，i3，可以产生的非空项集为，可以产生的非空项集为i1，i2，i3，i1，i2，i1，i3，i2，i3，i1，i3，i1，i2，i3，共，共8个。个。 定义定义5.7 5.7 对于对于I的非空子集的非空子集I1，若某项集，若某项集I1中包含有中包含有I中中的的k个项，称个
20、项，称I1为为k-项集项集。若若k-项集项集I1是频繁项集，称为是频繁项集，称为频繁频繁k-项集项集。显然，一个。显然，一个项集是否频繁，需要通过事务数据库项集是否频繁，需要通过事务数据库D来判断。来判断。5.1.4 5.1.4 挖掘关联规则的基本过程挖掘关联规则的基本过程挖掘关联规则就是找出事务数据库挖掘关联规则就是找出事务数据库D D中的强关联规则，中的强关联规则，通常采用以下两个判断标准：通常采用以下两个判断标准：最小支持度（包含）最小支持度（包含）：表示规则中的所有项在事务数据：表示规则中的所有项在事务数据库库D D中同时出现的频度应满足的最小频度。中同时出现的频度应满足的最小频度。最
21、小置信度（排除）最小置信度（排除）：表示规则中前件项的出现暗示后：表示规则中前件项的出现暗示后件项出现的概率应满足的最小概率。件项出现的概率应满足的最小概率。挖掘强关联规则两个基本步骤如下：挖掘强关联规则两个基本步骤如下：找频繁项集：找频繁项集：通过用户给定最小支持度阈值通过用户给定最小支持度阈值min_supmin_sup，寻找，寻找所有频繁项集，即仅保留大于或等于最小支持度阈值的项集。所有频繁项集，即仅保留大于或等于最小支持度阈值的项集。生成强关联规则：生成强关联规则：通过用户给定最小置信度阈值通过用户给定最小置信度阈值min_confmin_conf，在频繁项集中寻找关联规则，即删除不满
22、足最小置信度阈值在频繁项集中寻找关联规则，即删除不满足最小置信度阈值的规则。的规则。其中是目前研究的重点。其中是目前研究的重点。支持度和可信度是用来量化关联分析是否成功的方法。假设支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于想找到支持度大于0.8的所有项集，应该如何去做？一个办法的所有项集，应该如何去做？一个办法就是生产一个物品所有可能组合的清单，然后对每一种组合就是生产一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度。统计它出现的频繁程度。找频繁项集最简单的算法如下：找频繁项集最简单的算法如下：输入：输入：全局项集全局项集I和事务数据库和事务数据库D，
23、最小支持度阈值，最小支持度阈值min_sup。输出：输出：所有的频繁项集集合所有的频繁项集集合L。方法：方法：其过程描述如下：其过程描述如下：n=|D|;for (I的每个子集的每个子集c) i=0; for (对于对于D中的每个事务中的每个事务t) if (c是是t的子集的子集) i+; if (i/nmin_sup) L=Lc;/将将c添加到频繁项集集合添加到频繁项集集合L中中;若若I的项数为的项数为m，则子项集数为，则子项集数为2m，为每一个子集扫描，为每一个子集扫描D中中n个事务，所以算法的时间复杂度为个事务，所以算法的时间复杂度为O(2mn)，它随着项的，它随着项的个数呈指数级的增长
24、。个数呈指数级的增长。 但是当物品成千上万时，上述做法非常非但是当物品成千上万时，上述做法非常非常慢。真对这个问题，我们引进常慢。真对这个问题，我们引进Apriori原原理。理。AprioriApriori算法是由算法是由AgrawalAgrawal等人于等人于19931993提出的，它采用逐提出的，它采用逐层搜索策略（层次搜索策略）产生所有的频繁项集。层搜索策略（层次搜索策略）产生所有的频繁项集。 原理内容：原理内容：AprioriApriori原理是说如果某个项集是频繁的，那原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。么它的所有子集也是频繁的。 也就是说：如果也就是说：如果0
25、,10,1是频繁的，那么是频繁的，那么00，11也一定是也一定是频繁的，反过来也就是说：频繁的，反过来也就是说：如果一个项集是非频繁集，那如果一个项集是非频繁集，那么它的所有超集也是非频繁的。么它的所有超集也是非频繁的。（这个很有用）（这个很有用） 例如：我么如果知道例如：我么如果知道2,32,3是非频繁的，那么是非频繁的，那么0,1,2,31,2,30,2,30,1,2,31,2,30,2,3也是非频繁的。也就是说一旦也是非频繁的。也就是说一旦计算出计算出2,32,3的支持度，知道他是非频繁的之后，就不需的支持度，知道他是非频繁的之后，就不需要在计算要在计算0,1,2,31,2,30,2,3
26、0,1,2,31,2,30,2,3的支持度了。的支持度了。 原理作用：原理作用：这个原理是针对计算支持度时候，要遍历所有的数据，这样会这个原理是针对计算支持度时候，要遍历所有的数据，这样会造成计算量过大，非常耗时，使用造成计算量过大，非常耗时，使用AprioriApriori原理，可以减少遍原理，可以减少遍历次数，减少时间。历次数，减少时间。5.2.1 Apriori5.2.1 Apriori性质性质Apriori性质：性质：若若A是一个频繁项集，则是一个频繁项集，则A的每一个子集都是的每一个子集都是一个频繁项集。一个频繁项集。证明：证明：设设n为事务总数，为事务总数，sup_count()表
27、示表示项集在项集在D中所有中所有事务中出现的次数，依题意有事务中出现的次数，依题意有support(A)min_sup。对于对于A的任何非空子集的任何非空子集B（B A），一定有），一定有sup_count(B)sup_count(A)则：则：support(B)=sup_count(B)/nsup_count(A)/n=support(A) min_sup。例如，若例如，若beer，diaper，nuts项集是频繁的，则项集是频繁的，则beer，diaper也一定是频繁的，但也一定是频繁的，但apple，beer，diaper，nuts不一不一定是频繁的。定是频繁的。定义定义5.85.8 一
28、个项集一个项集A的超集的超集C，是指，是指C满足满足A C，且，且|A|C|。也就是说，由。也就是说，由A项集添加任意多个其他项构成的项集项集添加任意多个其他项构成的项集都是都是A的超集。的超集。由项集由项集A仅添加一个项构成的项集仅添加一个项构成的项集C称为称为A的直接超集。的直接超集。注意这里在注意这里在A中添加的项默认都是不重复的项。中添加的项默认都是不重复的项。abcaba直接超集直接超集所有超集所有超集AprioriApriori性质具有反单调性：性质具有反单调性：如果一个项集不是频繁的，如果一个项集不是频繁的，则它的所有超集也一定不是频繁的。则它的所有超集也一定不是频繁的。证明：证
29、明：设设n为事务总数，为事务总数，A不是频繁的，即不是频繁的，即support(A)min_sup。对于。对于A的任一超集，由于的任一超集，由于A C，所以：，所以：sup_count(C)sup_count(A)则：则：support(C)=sup_count(C)/nsup_count(A)/n=support(A)min_sup。例如，若例如，若ac不是频繁的，则不是频繁的，则abc、acd也一定不是也一定不是频繁的，这里的频繁的，这里的ac是是a，c的一种简写的一种简写，在不影响二义性，在不影响二义性的条件下，后面均采用这种简写方式。的条件下，后面均采用这种简写方式。5.2.2 Apr
30、iori5.2.2 Apriori算法算法1. 1. 基本的基本的AprioriApriori算法算法Apriori算法的基本思路是采用层次搜索的迭代方法，由算法的基本思路是采用层次搜索的迭代方法，由候选候选(k-1)-项集来寻找候选项集来寻找候选k-项集，并逐一判断产生的候选项集，并逐一判断产生的候选k-项集是否是频繁的。项集是否是频繁的。 Apriori算法算法： 该算法的的输入参数分别是最小支持度和数据集。该算法的的输入参数分别是最小支持度和数据集。 该算法首先会生成所有单个物品的项集列表。该算法首先会生成所有单个物品的项集列表。 接着扫描交易记录查看哪些项集满足最小支持度要求，那些不满
31、接着扫描交易记录查看哪些项集满足最小支持度要求，那些不满足支持度的集合会被去掉。足支持度的集合会被去掉。 然后，对剩下来的集合进行组合以生成包含两个元素的项集。然后，对剩下来的集合进行组合以生成包含两个元素的项集。 接下来，在重新扫描交易记录，去掉不满足最小支持度的项集。接下来，在重新扫描交易记录，去掉不满足最小支持度的项集。 该过程重复进行直到所有项集都被去掉该过程重复进行直到所有项集都被去掉设设Ck是长度为是长度为k的候选项集的集合的候选项集的集合，Lk是长度为是长度为k的频的频繁项集的集合繁项集的集合。为了简单，设最小支持度阈值。为了简单，设最小支持度阈值min_sup为最为最小元组数，
32、即采用小元组数，即采用最小支持度计数最小支持度计数。 首先，找出频繁首先，找出频繁1-项集，用项集，用L1表示。表示。由由L1寻找寻找C2，由，由C2产生产生L2，即产生频繁，即产生频繁2-项集的集合。项集的集合。由由L2寻找寻找C3，由，由C3产生产生L3。以此类推，直至没有新的频繁以此类推，直至没有新的频繁k-项集被发现。求每个项集被发现。求每个Lk时都要对事务数据库时都要对事务数据库D作一次完全扫描。作一次完全扫描。基本的基本的Apriori算法如下：算法如下：输入：输入：事务数据库事务数据库D，最小支持度阈值，最小支持度阈值min_sup。输出：输出：所有的频繁项集集合所有的频繁项集集
33、合L。方法：方法：其过程描述如下：其过程描述如下：通过扫描通过扫描D得到得到1-频繁项集频繁项集L1;for (k=2;Lk-1!=;k+) Ck=由由Lk-1通过连接运算产生的候选通过连接运算产生的候选k-项集项集; for (事务数据库事务数据库D中的事务中的事务t) 求求Ck中包含在中包含在t中的所有候选中的所有候选k-项集的计数项集的计数;Lk=c | cCk and c.sup_countmin_sup;/求求Ck中满足中满足min_sup的候选的候选k-项集项集 return L=kLk;【例例5.15.1】对于表对于表5.1所示的事务数据库，设所示的事务数据库，设min_sup=
34、2，产生，产生所有频繁项集的过程如图所有频繁项集的过程如图5.1所示，最后所示，最后L4=，算法结束，产生的，算法结束，产生的所有频繁项集为所有频繁项集为L1L2L3。TID购买商品购买商品的列表的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i3上述算法需要解决以下问题：上述算法需要解决以下问题：如何由如何由Lk-1构建构建Ck如何由如何由Ck产生产生Lk2. 2. 自连接：自连接：由由Lk-1构建构建Ck在基本的在基本的Apriori算法中，由算法中，由Lk-1构建构建Ck可以通过
35、连接运可以通过连接运算来实现。连接运算是表的基本运算之一，如下图所示是两算来实现。连接运算是表的基本运算之一，如下图所示是两个表个表R、S按按R第第3列等于列等于S第第2列的条件进行条件连接的结果。列的条件进行条件连接的结果。采用自连接的方式由采用自连接的方式由Lk-1产生产生Ck时，连接关系是在时，连接关系是在Lk-1（用（用p表示）和表示）和Lk-1（用（用q表示）中，前表示）中，前k-2项相同，且项相同，且p的第的第k-1项小于项小于q的第的第k-1项值，项值，即：即：p.item1=q.item1 and p.item2=q.item2 and and p.itemk-2=q.item
36、k-2 and p.itemk-1q.itemk-1其中其中p.itemk-1q.itemk-1是为了保证是为了保证Ck中不含重复的项集。中不含重复的项集。如图如图5.3所示是由所示是由L3产生产生C4的过程的过程3. 3. 对对Ck进行剪枝操作进行剪枝操作对于由对于由Lk-1生成的生成的Ck，从，从Ck中删除明显不是频繁项集的中删除明显不是频繁项集的项集，这称为项集，这称为剪枝操作剪枝操作。这里。这里Lk-1包含所有的包含所有的(k-1)-频繁项集，频繁项集，也就是说，也就是说，利用利用Apriori性质的反单调性，对于性质的反单调性，对于Ck中的某个中的某个k-项集项集x，若它的任何若它的
37、任何(k-1)-子项集是非频繁项集，则子项集是非频繁项集，则x也是非频繁项集，也是非频繁项集，可以从可以从Ck中删除中删除x。而。而判断一个判断一个(k-1)-子项集是非频繁项集的子项集是非频繁项集的条件就是它不在条件就是它不在Lk-1中中。【例例5.25.2】设设L3=i1，i2，i3，i1，i2，i4，i1，i3，i4，i1，i3，i5，i2，i3，i4，通过自连接并剪枝构建，通过自连接并剪枝构建C4的过程如图的过程如图5.4所示。所示。又例如，某事务数据库又例如，某事务数据库D包含包含a，b，c，d共共4个项，采用个项，采用层次方法求所有的频繁项集，如图所示，图中每个带阴影框对层次方法求
38、所有的频繁项集，如图所示，图中每个带阴影框对应一个频繁项集。如果求出应一个频繁项集。如果求出1-频繁项集集合频繁项集集合L1=b，c，d，得出候选得出候选2-项集集合项集集合C2=bc，bd，cd，由于，由于1-项集项集a不是不是频繁的，所以不需考虑所有包含频繁的，所以不需考虑所有包含a的项集，见图中剪枝的项集，见图中剪枝1。 如果求出如果求出2-项集集合项集集合L2=bc，bd，由于，由于cd不是频繁项不是频繁项集，所以不需考虑所有包含集，所以不需考虑所有包含cd的项集，即不可能有频繁的项集，即不可能有频繁3-项集项集和频繁和频繁3-项集，见图中剪枝项集，见图中剪枝2。这样求的所有频繁项集集
39、合为。这样求的所有频繁项集集合为b，c，d，bc，bd。 4. 4. 项集的支持度计算项集的支持度计算在基本的在基本的Aprior算法中，求出剪枝后的算法中，求出剪枝后的Ck，由，由Ck产生产生Lk时，需要求出时，需要求出Ck中每个中每个k-项集的支持度计数，也就是说，项集的支持度计数，也就是说，若若Ck中有中有n个项集，需要个项集，需要n次扫描事务数据库次扫描事务数据库D，这是十分耗时，这是十分耗时的。的。改进的方法是，改进的方法是，扫描扫描D中一个事务中一个事务t时，如果时，如果t中包含的中包含的项数少于项数少于k，直接跳过它转向下一个事务，直接跳过它转向下一个事务，否则分解出所有，否则分
40、解出所有的的k-项集项集s，若，若sCk，则表示，则表示Ck中有一个等于中有一个等于s的项集，将的项集，将s的支持度计数增的支持度计数增1。这样只需扫描事务数据库。这样只需扫描事务数据库D一遍，便求一遍，便求出了出了Ck中所有项集的支持度计数。中所有项集的支持度计数。【例例5.35.3】对于表对于表5.1所示的事务数据库，设所示的事务数据库，设min_sup=2，利，利用前面介绍的各种改进方法产生所有频繁项集的过程如下图所示。用前面介绍的各种改进方法产生所有频繁项集的过程如下图所示。TIDTID购买商品的列表购买商品的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5
41、i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i3TIDTID购买商品购买商品的列表的列表t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i3，i5t9i1，i2，i35. 5. 改进的改进的AprioriApriori算法算法采用自连接和剪枝操作得到采用自连接和剪枝操作得到改进的改进的Apriori算法算法如下：如下：输入：输入：事务数据库事务数据库D，最小支持度阈值，最小支持度阈值min_sup。输出：输出：所有的频繁项集集合所有的频繁项集集合L。方法：方法：其过程描述如下：其过
42、程描述如下：通过扫描通过扫描D得到得到1-频繁项集频繁项集L1;for (k=2;Lk-1!=;k+) Ck=apriori_gen(Lk-1,min_sup); for (事务数据库事务数据库D中的事务中的事务t) for (t中每个中每个k-项集项集s); if (sCk) s.sup_count+; for (Ck中的每个项集中的每个项集c)if (c.sup_countmin_sup) Lk=Lkc;return L=kLk;procedure aprior_gen(Lk-1,min_sup)/由由Lk-1自连接并剪枝构建自连接并剪枝构建Ck for (Lk-1中的每个项集中的每个项集
43、l1Lk-1)for (Lk-1中中l1之后的每个项集之后的每个项集l2Lk-1) if (l11=l21 and and l1k-2=l2k-2 and l1k-1l2k-1) c=l1与与l2连接连接;if (has_infrequent_subset(c,Lk-1) delete c;else 将将c加入加入Ck; return Ck;procedure has_infrequent_subset(c,Lk-1)/剪枝：判断剪枝：判断c是否为非频繁项集是否为非频繁项集 for (c的每个的每个(k-1)-子项集子项集s)if (s不属于不属于Lk-1) /c中存在不属于中存在不属于Lk-
44、1的的(k-1)-子项集，子项集，c是非频繁的是非频繁的 return true; return false;5.2.3 5.2.3 由频繁项集产生关联规则由频繁项集产生关联规则1. 1. 产生关联规则的基本过程产生关联规则的基本过程因为由频繁项集的项组成的关联规则的支持度大于等因为由频繁项集的项组成的关联规则的支持度大于等于最小支持度阈值，所以规则产生过程是：于最小支持度阈值，所以规则产生过程是：在由频繁项集的项组成的所有关联规则中，找出所有在由频繁项集的项组成的所有关联规则中，找出所有置信度大于等于最小置信度阈值的强关联规则。置信度大于等于最小置信度阈值的强关联规则。对于形如对于形如lu(
45、l-lu)的规则，其置信度为的规则，其置信度为 因此，对于每个频繁项集因此，对于每个频繁项集l，求强关联规则的基本步骤如下：，求强关联规则的基本步骤如下：产生产生l的所有的所有非空真子集非空真子集。对于对于l的每个非空真子集的每个非空真子集lu，如果，如果l的支持度计数除以的支持度计数除以lu的的支持度计数大于等于最小置信度阈值支持度计数大于等于最小置信度阈值min_conf，则输出，则输出强关联规则强关联规则lu(l- -lu)。其中，因为。其中，因为l是频繁项集，根据是频繁项集，根据Apriori性质，性质，lu与与(l- -lu)都是频繁项集，所以，其支持计都是频繁项集，所以，其支持计数
46、在频繁项集产生阶段已经计算，在此不必重复计算。数在频繁项集产生阶段已经计算，在此不必重复计算。【例例5.45.4】对于表对于表5.1的事务数据库，有一个频繁项集的事务数据库，有一个频繁项集l=i1，i2，i5，由，由l产生关联规则如下：产生关联规则如下：l的所有非空真子集为的所有非空真子集为i1，i2，i5，i1，i2，i1，i5，i2，i5对于对于i1，产生的规则为，产生的规则为i1 i2 and i5，由图，由图5.1的计算的计算过程可知，过程可知，i1的支持度计数为的支持度计数为6，l=i1，i2，i5的支持度计数的支持度计数为为2，所以置信度，所以置信度=2/6=33%。类似地，计算其
47、他关联规则的置信度如下：类似地，计算其他关联规则的置信度如下：i1 and i2 i5，置信度，置信度=2/4=50%i1 and i5 i2，置信度，置信度=2/2=100%i2 and i5 i1，置信度，置信度=2/2=100%i2 i1 and i5，置信度，置信度=2/7=29%i5 i1 and i2，置信度，置信度=2/2=100%如果设置最小置信度阈值如果设置最小置信度阈值min_conf=70%，则产生的强，则产生的强关联规则如下：关联规则如下：i1 and i5 i2i2 and i5 i1i5 i1 and i22. 2. 通过剪枝提高效率通过剪枝提高效率对于频繁项集对于
48、频繁项集l及其两个非空真子集及其两个非空真子集lu和和lv，如果，如果lv lu，并且，并且规则规则lu(l- -lu)不是强关联规则，则规则不是强关联规则，则规则lv(l- -lv)也不是强关联规也不是强关联规则。则。证明：证明：因为因为lv lu，所以，所以lv.sup_countlu.sup_count由于由于lu(l- -lu)不是强关联规则，则：不是强关联规则，则：l.sup_count/lu.sup_countmin_conf。有：有：l.sup_count/lv.sup_countl.sup_count/lu.sup_countmin_conf，所以所以lv(l- -lv)不是强
49、关联规则。不是强关联规则。生成强关联规则的生成强关联规则的剪枝原则剪枝原则：由于由于lu和和lv是是l的两个非空真子集，所以的两个非空真子集，所以lv lu等价于等价于(l- -lv) (l- -lu)，也就是说，若，也就是说，若(l- -lv) (l- -lu)成立，并且规则成立，并且规则lu(l- -lu)不是强关联规则，则规则不是强关联规则，则规则lv(l- -lv)也不是强关联规则。也不是强关联规则。更简单地说，更简单地说，对于前面的例子，频繁项集对于前面的例子，频繁项集l=i1，i2，i5，产生所有强，产生所有强关联规则的过程如下图所示。关联规则的过程如下图所示。3. 3. 产生关联
50、规则的算法产生关联规则的算法输入：输入：Apriori算法的各项集的支持度计数，频繁项集集合算法的各项集的支持度计数，频繁项集集合L， 最小置信度阈值最小置信度阈值min_conf输出：输出：所有强关联规则的后件项集所有强关联规则的后件项集R。方法：方法：其过程描述如下：其过程描述如下：for (L中的每个频繁项集中的每个频繁项集l) for (l中的每个中的每个1-项集项集l1) if (l.sup_count/(l-l1).sup_countmin_conf) /l1满足置信度要求满足置信度要求 R1=R1l1; for (j=2;Rj-1!=;j+) for (Rj-1中每个后件中每个后
