第4章 关联规则1.ppt

1、2020/10/11,1,数据仓库与数据挖掘技术,五邑大学计算机学院 2009.05,何国辉 教授,2020/10/11,2,关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一 最早是由R.Agrawal等人提出的 其目的是为了发现超市交易数据库中不同商品之间的关联关系。 一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。 经典的关联规则挖掘算法：Apriori算法和FP-growth算法,第4章 关联规则挖掘 ,4.1关联规则挖掘的基本概念,2020/10/11,3,1. 购物篮分析引发关联规则挖掘的例子 问题：“什么商品组或

2、集合顾客多半会在一次购物中同时购买？” 购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。,2020/10/11,4,例购买计算机与购买财务管理软件的关联规则可表示为： computer financial_management_software support=2%,confidence=60% support为支持度，confidence为置信度。 该规则表示：在所分析的全部

3、事务中，有2的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60也购买了财务管理软件。,2020/10/11,5,2. 关联规则 关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性。 项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。,2020/10/11,6,以商场超市的市场数据库为例，形式化地描述关联规则。 定义41 设I=i1，i2，,im是项的集合，表示各种商品的集合；D= t1，t2，,tn为交易集，表示每笔交易的集合（是全体事务的集合）

4、。其中每一个事务T都是项的集合，且有TI。每个事务都有一个相关的唯一标识符和它对应，也就是事务标识符或TID。 设X为一个由项目构成的集合，称为项集，当且仅当XT时我们说事务T包含X。 项集X在在事务数据库DB中出现的次数占总事务的百分比叫做项集的支持度。 如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。,2020/10/11,7,关联规则是形如XY的蕴含式，其中XI，YI且XY=，则X称为规则的条件，Y称为规则的结果。 如果事务数据库DB中有s%的事务包含XY，则称关联规则XY的支持度为s%。支持度是一个概率值。,2020/10/11,8,表4-1,2020/

5、10/11,9,定义42关联规则 XY对事物集D的支持度（support）定义为D中包含有事务X和Y的百分比。关联规则XY对事务集合D的置信度（confidence）定义为D中包含有X的事务数与同时包含Y的百分比。即： lsupport(XY)(包含X和Y的事务数/事务总数)100 lconfidence(XY)(包含X和Y的事务数/包含X的事务数)100,2020/10/11,10,定义43置信度和支持度均大于给定阈值（即最小置信度阈值和最小支持度阈值）。即： support(XY) min_sup confidence(XY) min_conf 的关联规则称为强规则；否则称为弱规则。 数据

6、挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。,2020/10/11,11,强规则XY对应的项集（XY）必定是频繁集。因此，可以把关联规则挖掘划分为以下两个子问题： 根据最小支持度找出事务集D中的所有频繁项集。核心 根据频繁项集和最小置信度产生关联规则。较易,2020/10/11,12,3. 关联规则挖掘 关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。,例 购买商品事务如下表所示，设最小支持度为50%, 最小可信度为 50%, 则可得到以下关联规则： A C (50%,

7、 66.6%) C A (50%, 100%),支持度,可信度,表4-2,2020/10/11,13,4.关联规则挖掘的分类 （1）基于规则中处理的变量的类别 基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。 布尔型关联规则：如果规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。 量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。,2020/10/11,14,例如： 以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age 和income已经离散化）： age(X,“3039”)income(“

8、42K48K”) buys(X,“high_resolution_TV”) 量化型关联规则中也可以包含多种变量。例如： 性别=“女”=职业=“秘书” ，是布尔型关联规则； 性别=“女”=avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。,2020/10/11,15,（2）基于规则中数据的抽象层次 基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。 单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。 例如： buys(X, “computer”) buys(X, “printer”) 顾客X购买的商品不涉及不同抽象层次（“computer” 和“pr

9、inter”在同一个抽象层），因此是单层关联规则。 多层的关联规则：变量涉及不同抽象层次的项或属性。 例如： age(X,“3039”)buys(X, “laptop computer”) age(X,“3039”)buys(X, “computer”) 顾客X购买的商品涉及不同抽象层次（“computer” 在比“laptop computer”高的抽象层），因此是多层关联规则。,2020/10/11,16,（3）基于规则中涉及到的数据的维数 基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。 单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。

10、例如：用户购买的物品：“咖啡=砂糖”，这条规则只涉及到用户的购买的物品。 多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。 例如：性别=“女”=职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则。,2020/10/11,17,给出了关联规则的分类之后，就可以考虑某个具体的关联规则挖掘算法适用于哪一类规则的挖掘，某类关联规则又可以用哪些不同的方法进行处理。 最简单的是单维、单层、布尔型的关联规则。,2020/10/11,18,1. 术语 关联规则挖掘即给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别

11、大于用户给定的最小置信度和最小支持度。,4.2关联规则挖掘的过程,2020/10/11,19,定义44在关联规则挖掘算法中，把项目的集合称为项集（itemset），包含有k个项目的项集称为k-项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或等于最小支持度s与D中事务总数的乘积，则称该项集满足最小支持度s。如果项集满足最小支持度，则称该项集为频繁项集（frequent itemset）。,2020/10/11,20,例一个食品连锁店保留着每周的事务记录，其中每一条事务表示在一项收款机业务中卖出的项目。连锁店的管理会收到一个事务汇总报告，报告表明了每

12、种项目的销售量是多少。此外，他们要定期了解哪些项目经常被顾客一起购买。他们发现顾客购买了花生酱后，100%地会购买面包。而且，顾客购买了花生酱后，有33%也购买果冻。不过，所有事务中大约只有50%包含花生酱。 被用于在其中寻找关联规则的数据库可以看作为一个元组集合，每个元组包含一组项目。一个元组可能是： 花生酱、面包、果冻 包含三个项目：花生酱、面包、果冻 每个项目表示购买的一种产品 一个元组是一次购买的产品列表,2020/10/11,21,表4-3,2020/10/11,22,项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）,表4-4,2020/10/11,23,2关联规

13、则的挖掘过程,最常用的关联规则挖掘方法被分解为下面两步： 第1步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1到k递归查找k-频繁项集。 第2步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关联规则。,找出满足定义的大项目集,从大项目集（频繁项目集）生成关联规则,2020/10/11,24,定义45大（频繁）项目集是出现次数大于阈值S的项目集。用符号L表示大项目集组成的整个集合，用表示一个特定的大项目集。 一旦找出大项目集，则对于任何有趣的关联规则XY，在频繁项目集的集合中一定有XY。,任何大项目集的子集也是大的,4.3 大项目集,2020

14、/10/11,25,关联规则中使用了大量的符号，这些符号汇总如下。 一个特定符号所带的下标表示所考虑的集合的大小，例如，lk表示一个大小为k的项目集。 一些算法将事务集合分为若干个分区，在这种情况下，用p表示分区的数目，用上标表明分区的编号。例如，Di表示D的第i个分区。,表10-5,2020/10/11,26,找出大项目集的算法可以很简单，但代价很高。 简单的方法是：对出现在事务中的所有项目集进行计数。 给定一个大小为m的项目集合，共有2m个子集，去掉空集，则潜在的大项目集数为2m - 1。随着项目数的增多，潜在的大项目集数成爆炸性增长。（当m=5，为31个；当m=30，变成10737418

15、23个） 解决问题的难点：如何高效确定所有大项目集。,大部分关联规则算法都利用巧妙的方法来减少要计数的项目集。,2020/10/11,27,几个概念： 潜在的大项目集称为候选。 所有被计数的（潜在大的）项目集的集合称为候选项目集C。 关联规则使用的一个性能度量指标是C的大小。,找出所有大项目集以后，关联规则的生成变得非常直接。,2020/10/11,28,有关算法： 改自AS94，用support返回输入项目集的支持度。 输入： D/事务数据库 I/项目集合 L/大项目集 s/支持度 /可信度（置信度） 输出: R/满足s和的关联规则集合 ARGen算法： R = ； for each lL

16、do for each x l such that x do if support(l)/support(x) then R = R x (l-x)；,2020/10/11,29,有关算法演示：参考表4-3、4-4 假定输入的支持度和可信度分别为s=30%和 =50%。利用该s值得到如下大项目集的集合： L=啤酒,面包,牛奶，花生酱, 面包、花生酱 查看最后一个大项目集可以生成的关联规则,其中： l = 面包、花生酱 有两个非空子集： 面包和花生酱 对于第一个非空子集，可得： support(面包、花生酱)/support(面包) = 60/80 = 0.75 意味着关联规则：“面包花生酱”的

17、置信度为75%，因为其置信度高于，所以是一条有效的关联规则。,2020/10/11,30,对于第二个非空子集，可得： support(面包、花生酱)/support(花生酱) = 60/60 = 1 意味着关联规则：“花生酱面包”的置信度为100%， 也是一条有效的关联规则。,2020/10/11,31,4.4 关联规则挖掘的Apriori算法,4.4.1 Apriori算法的基本思想 Apriori算法是一种最有影响的挖掘布尔关联规则大（频繁）项目集的算法。它使用一种称作逐层搜索的迭代算法，通过k-项集用于探索（k+1）-项集。已经为大部分商业产品所使用。,2020/10/11,32,Apr

18、iori算法的基本思想是： 首先，通过扫描数据集，产生一个大的候选数据项集,并计算每个候选数据项发生的次数，然后基于预先给定的最小支持度生成频繁1-项集的集合，该集合记作 ； 然后基于 和数据集中的数据，产生频繁2-项集 ； 用同样的方法，直到生成频繁n-项集，其中已不再可能生成满足最小支持度的（N+1）项集 。 最后，从大数据项集中导出规则。,在第一次迭代的第一步中，产生的候选集包含所有1-项集，实为数据库中所有的项，再计算各自的支持度。,2020/10/11,33,1. 大项目集的性质,大项目集的任一子集也一定是大的。 大项目集也称作是向下封闭的，如果一个项目集满足最小支持度的要求，其所有

19、的子集也满足这一要求。 其逆命题：如果知道一个项目集是小的，就不需要生成它的任何超集来作为它的候选集，因为它们也一定是小的。 Apriori性质基于如下事实：根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即sup（I） min_sup。如果将项A添加到I，则结果项集（即IA）不可能比I更频繁出现。因此，IA也不是频繁的，即sup（IA） min_sup。 频繁项集的Apriori性质用于压缩搜索空间（剪枝），以提高逐层产生频繁项集的效率。,Apriori算法利用了大项目集的这些性质,2020/10/11,34,用图表示上述性质，例子中有四个项目A，B，C，D，格中的线

20、表示子集关系，大项目集的性质表明：如果原来的项目集是大的，则在路径中位于其上的任何集合也一定是大的。,A，B，C，D项目集的格结构,项目ACD的非空子集是： AC，AD，CD，A，C，D,2020/10/11,35,如果A，C，D是大的，则其每一个子集也是大的，如果其任何一个子集是小的，则 A，C，D也是小的。,A，C，D的子集,项目ACD的非空子集是： AC，AD，CD，A，C，D,2020/10/11,36,按照Apriori算法： 在第i趟扫描的过程中，对Ci进行计数，只有那些大的候选集被用于生成下一趟扫描的候选集，即用Li生成Ci+1。 只有一个项目集的所有子集都是大的，它才被认为是候

21、选。 为了生成大小为i+1的候选，要对前一趟扫描发现的大项目集进行连接运算。 表示：Lk*Lk = XY 其中 X，Y Lk，|XY|=k 1 例：对表4-3进行演算，其中s=30%， =50%,2020/10/11,37,表4-3,回忆,2020/10/11,38,对表4-3采用Apriori算法,为了组合出下一级候选，每个项目集除了一个项目之外，其它的项目都相同。,因为只有一个大小为2的大项目集，所以没有大小为3的候选,2020/10/11,39,4.4.2 Apriori算法中的关键步骤,Apriori算法中的关键步骤是由Lk-1找Lk，该步骤可分为两步： 第1步（连接）：为找Lk，通过

22、Lk-1与自己连接产生候选K-项集的集合。将该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集，记号lij表示li的第j项。执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-2）项不同（为简单计，设l1k-1l2k-1），即： l11= l21 l12=l22l1k-2=l2k-2 l1k-1l2k-1 则Lk-1的元素l1和l2是可连接的。连接l1和l2产生的结果的项集是l11l12l1k-1l2k-1。,2020/10/11,40,第2步（剪枝）：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描

23、数据库，确定Ck中每个候选的计数，从而确定Lk。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。,2020/10/11,41,一个称为Apriori-Gen的算法： 用于生成除第一趟之外的每一趟扫描的候选项目集。 所有的单元素项目集在第一趟时作为候选使用。 前一趟发现的大项目集的集合Li-1与自身进行连接运算以确定候选。 为了组合出下一级候选，每个项目集除了一个项目之外，其它的项目都

24、相同。,2020/10/11,42,Apriori-Gen算法实例：一个女士服装店在一天中有20个收款机事务记录，如表：,2020/10/11,43,2020/10/11,44,Apriori-Gen算法处理过程： 第一趟扫描得到6个候选项目集，其中5个候选是大的。 对该5个候选应用Apriori-Gen算法，将每一个候选与另外4个进行组合，得到第二趟扫描：4+3+2+1=10个候选，其中7个候选是大的。 在7个候选中再应用Apriori-Gen算法，将每一个项目集与另外一个与之具有一个公共成员的项目集进行连接运算，第三趟扫描后得到4个大项目集。 第四趟扫描后只剩下一个大项目集，也不存在下一趟

25、计数为5个的新项目集。,2020/10/11,45,为了对大数据库中的项目集进行高效计数，可以对数据库进行抽样。 最初的抽样算法在最理想的情况下可将数据库的扫描趟数减少到1，在最坏的情况下将扫描趟数减少到2。 数据库抽样的大小要保证它能驻留在内存中。 知识准备： 大项目集被看作是潜在大的（Potentially Large，PL）项目集，并作为候选用整个数据库对其进行计数。 另外的候选则通过作用于样本中大项目集的负边界函数BD-来确定。 因此整个候选集为：C = BD-(PL)(PL),4.4.3 抽样算法,2020/10/11,46,负边界函数是Apriori-Gen算法的一种推广，它的定义

26、是： 本身不在PL中但其子集都在PL中的项目集的最小集合 负边界函数在一些Apriori的改进算法中很重要，例如生成大项集或导出负关联规则时提高了有效性。,2020/10/11,47,例子：假定项目集合是A，B，C，D，从数据库样本中发现的大项目集集合是PL = A，C，D，CD。第一趟扫描整个数据库生成下面的候选集： C = BD-(PL)(PL) = B，AC，AD A，C，D，CD 加入理由： 加入了AC，因为A和C都在PL中； 加入了AD，同理，因为A和D都在PL中； 没有加入ACD，因为AC和AD都不在PL中； 加入了B，因为其所有子集都为空，故可以认为其子集也在PL中。,2020/

27、10/11,48,有关格结构表示：,大项目集,2020/10/11,49,BD-(PL)(PL),2020/10/11,50,抽样算法的实现： 具体措施： 在扫描整个数据库时，大项目集的集合被用作候选集。 如果一个项目集在抽样中是大的，则它被认为在整个数据库中可能是大的，因此抽样中的大项目集集合被称为PL。 为了在第一趟扫描时获得所有的大项目集，用PL的负边界对其进行扩充，因此整个候选集为：C = BD-(PL)(PL),补充说明： Apriori算法用来发现样本中的大项目集，也可以使用任何其它大项目集发现方法。 可以使用任意的数据库抽样算法。,2020/10/11,51,抽样算法实现过程：

28、在第一趟扫描数据库时，对C中的所有候选进行计数。如果所有大的候选都在PL中（没有在BD-(PL)中），那么发现了所有的大项目集。但如果有一些大项目集在负边界中，则需要进行第二趟扫描。所有项目集的集合被分到4个区域： 已知为大的部分 已知为小的部分 已知为大的项目集的负边界 以及其它部分,可以认为负边界是大项目集边界的一个缓冲区，代表有可能为大的的项目集的最小集合。,2020/10/11,52,第二趟扫描时，生成其它候选，并进行计数，这样一来做能保证找出所有大项目集。用缺失大项目集（Missing Large Itemset，ML）表示那些在L中，但却不在PL中的项目集。 为了在第二趟扫描中发现

29、所有剩余的大项目集，抽样算法将重复应用负边界函数，直到可能的候选集合不再进一步扩大为止。,2020/10/11,53,抽样算法： 输入： I/项目集合 D/事务数据库 S/支持度 输出： L/大项目集 抽样算法： Ds=Sample draw from D； PL=Apriori(I,Ds,smalls)； C = BD-(PL)(PL) L = ； for each IiC do Ci = 0；/每个项目集的初始计数设为0； for each tjD do /第一趟扫描计数； for each IiC do if Ii tj then Ci = Ci + 1；,2020/10/11,54,f

30、or each IiC do if Ci(s|D|) then L = LIi ； ML = x|xBD-(PL) xL；/缺失的大项目集 if ML then C = L；/将候选设置为大项目集 repeat C = C BD-(C)；/用负边界对候选集进行扩充 until no new itemsets are added to C； for each IiC do Ci = 0；/每个项目集的初始计数设为0； for each tjD do /第二趟扫描计数； for each IiC do if Ii tj then Ci = Ci + 1； for each IiC do if Ci

31、(s|D|) then L = LIi ；,2020/10/11,55,算法中应用了一个称为smalls的支持度，smalls可以是比s小的任意支持度值。 基本思路：发现抽样中的大项目集时通过减小支持度，能从完整数据库中发现更多真正的大项目集。,2020/10/11,56,例：使用抽样算法发现食品店数据中的所有大项目集，其中s=20%。假定抽样数据库包括前两个事务： Ds = t1 = 面包，果冻，花生酱， t2 = 面包，生酱 如果将s减小到smalls = 10%，那么对于一个在抽样中为大的项目集来说，它必须在至少0.12个事务中出现，也就是必须在其中一个事务中出现。 对Ds应用Aprio

32、ri算法可以得到： PL = 面包，果冻，花生酱， 面包，果冻，面包，花生酱， 果冻，花生酱， 面包，果冻，花生酱 计算负边界： BD-(PL) = 啤酒，牛奶 在第一趟数据库扫描时，对以下候选集计数： C = 面包，果冻，花生酱， 面包，果冻，面包，花生酱， 果冻，花生酱， 面包，果冻，花生酱， 啤酒，牛奶 ,2020/10/11,57,扫描时使用s=20%，并应用于整个数据库的5个事务。因此对于一个大的项目集来说，必须至少在0.25个或1个事务中出现。 可以发现啤酒和牛奶是大的，ML=啤酒，牛奶，根据算法，首先令C=L，也即PL。 计算负边界可得： C = BD-(C) = 啤酒，面包，

33、啤酒，果冻，啤酒，牛奶， 啤酒，花生酱， 面包，牛奶， 果冻，牛奶， 牛奶，花生酱 由于发现了新的项目集，重复上述过程，并发现所有大小为3的项目集。 最后一趟将发现所有大小为4的项目集，并针对剩余的不知是否为大的项目集扫描数据库。,2020/10/11,58,基于抽样的方法的本质是选取给定事务集D的随机样本S，在S中找出频繁项集，即以牺牲精度换取效率。 Mannila等先考虑了这一点，他们认为抽样是发现规则的一个有效途径。 随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。 由于是从样本中分析大

34、项目集，故对样本采用了比最小支持度阈值更低的支持阈值来获得潜在大项目集。 Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。,2020/10/11,59,该方法只需对事务数据库进行两次扫描。 数据库被划分成若干个非重叠的分区。 每个分区都按可以小到适合内存的大小。 主要优点： 提高了算法的效率 突破了内存限制 很容易构造并行和/或分布式算法 通过将数据库的当前状态作为一个分区，而将新的数据条目作为第二个分区，更容易实现增量挖掘关联规则。,4.4.4 基于划分的Apriori方法,2020/10/11,60

35、,具体思路： 第一趟扫描数据库，发现所有分区中的大项目集。Li代表从分区Di中发现的大项目集。 在第二趟扫描时，只有那些至少在一个分区中为大项目集被用作候选并进行计数，以确定它们在整个数据库中是否为大。,2020/10/11,61,该算法可以高度并行，即可以把每一分区分别分配给某一个处理器生成频繁集。产生频繁集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。 通常通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频繁集的时间也是一个瓶颈。,2020/10/11,62,实例,D1,D2,2020/10/11,63,划分算法在购物篮中的应用：数据库被划分成两个分区，

36、第一个分区包含两个事务，第二个分区包含三个事务， 采用10%的支持度计算出的大项目集L1和L2为： L1 = 面包，果冻，花生酱， 面包，果冻， 面包，花生酱， 果冻，花生酱， 面包，果冻，花生酱 L2 = 啤酒，面包，牛奶，花生酱， 啤酒，面包， 啤酒，牛奶，面包，牛奶，面包，花生酱， 牛奶，花生酱， 面包，牛奶，花生酱 如果项目分布均匀分布在各个分区中，则大部分局部大项目集在全局都是大的，如果数据分布是不均匀的，则错误候选的比例就会大。,2020/10/11,64,4.5 频繁模式增长（FP）算法,由于Apriori算法和Apriori算法的变形都需要产生大量的候选项集，Apriori算法

37、的变形虽然使其得到一定程度的改善，但并未根本改观。 例如：如果生成一个长度为100的频繁模式，如a1,a2,a100，那么产生的候选集的数量至少为： 100 ( ) = 2100 1 1030 i=1 计算的复杂性成指数增长。 Han等人引入“频繁模式增长”（简称FP-增长）的概念，可以不产生候选就能够找出所有的频繁项集。,i,100,2020/10/11,65,4.5.1 FP-增长算法的基本思想,FP-增长算法的基本思想是： 采用分治策略，将提供频繁项集的数据库压缩到一棵频繁模式树，但还是保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库，每个关联一个频繁项，并分别挖掘每个数据

38、库。 即：首先进行数据库投影，得到频繁项，然后通过构造一个压缩的数据库结构FP树来对它进行挖掘。,2020/10/11,66,例使用频繁模式增长的方法，来考虑下面的例子。,2020/10/11,67,第一遍扫描数据库D的结果与Apriori相同，它导出频繁1-项集的集合，并得到它们的支持度计数。设最小支持度计数为2。频繁项的集合按照支持度计数的递减顺序排序。即： L=I2：7，I1：6，I3：6，I4：2，I5：2。 构造FP-树：首先，创建树的根节点，用“null”标记。第二遍扫描数据库D。每个事务中的项按照L中的次序处理并对每个事务创建一个分枝。,2020/10/11,68,例如：第一个事

39、务“T100：I1，I2，I5”按L的次序包含三个项I2，I1，I5，导致构造树的第一个分枝（I2：1），（I1：1），（I5：1）。该分枝具有三个节点，其中，I2作为根的子女链接，I1链接到I2，I5链接到I1。 第二个事务T002按L的次序包含I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀I2。这样，将节点I2的计数增加1，并创建一个新节点（I4：1），它作为（I2：2）的子女链接。一般地，当为一个事务考虑增加分枝时，沿着共同前缀上的每个节点的计数增加1，为跟随在前缀之后的项创建节点并链接。,2020/10/11,69,存放压

40、缩的频繁模式信息的FP树,2020/10/11,70,为方便树的遍历，创建一个项头表，使得每个项通过一个节点链指向它在树中的出现位置（节点）。扫描所有的事务之后得到的树，带有相关节点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-树的问题。 FP-树挖掘：由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基，然后构造FP树，并递归地在该树上进行挖掘。通过后缀模式与由FP树产生的频繁模式连接实现模式增长。 注：条件模式基是一个子数据集，由FP树中与后缀模式一起出现的前缀路径集组成。,2020/10/11,71,FP-树挖掘总结：L中的最后一项，而不是第一项开始。通过上述方法我们可以知

41、道：,对于I5有两个分枝。这些路径由分枝,形成。这样，考虑I5为后缀，它的两个对应的前缀路径是,它们形成I5的条件模式基。它的条件FP-树只包含单个路径;不包含I3，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2 I5：2，I1 I5：2，I2 I1 I5：2。,2020/10/11,72,例通过创建条件模式基挖掘FP-树。 Item 条件模式基 条件FP=数 产生的频繁模式 I5 （I2 I1：1），（I2 I1 I3：1） I2：2，I1：2 I2 I5：2，I2 I1 I5：2 I4 （I2 I1：1），（I2：1） I2：2 I2 I4：2 I3 （

42、I2 I1：2），（I2：2），（I1：2） I2：4，I1：2 I2 I3：4 I2 I1：2 I1 （I2：4） I2：4 I2 I1：4,对于I4，它的两个前缀形成条件模式基（I2 I1：1），（I2：1），产生一个单节点的条件FP-树I2：2，并导出一个频繁模式I2 I4：2。 注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁模式在I5的考察时已经分析过。这就是我们为什么在L的后端，而不是在前端开始处理的原因。,2020/10/11,73,与以上分析类似，I3的条件模式基是（I2 I1：2），（I2：2），（I1：2）。它的条件FP-树有两个分

43、枝,.它产生模式集：I2 I3：4，I1 I3：2，I2 I1：2。 最后，I1的条件模式基是（I2：4），它的FP-树包含一个节点I2：4，产生一个频繁模式I2 I1：4。,2020/10/11,74,算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。 输入：事务数据库D；最小支持度阈值min_sup. 输出：频繁模式的完全集,4.5.2 FP-增长算法的描述,2020/10/11,75,方法： 按以下步骤构造FP-树： 扫描事务数据库D 一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。 创建FP-树的根节点，以：“null”标记它。对于D每个事务

44、Trans，执行： 选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表示为p/P，其中p是第一个元素，而P是剩余元素的表。调用insert_tree(p/P,T).该过程执行情况如下。如果T有子女N使得N.item_name=p.item_name，则N节点的计数增加1；否则创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链接结构将其链接到具有相同item_name的节点。如果P非空，就递归地调用insert_tree（P，N）。,2020/10/11,76,方法(续）： FP树的挖掘：通过调用FP_growth（FP_tree,null）实现。 该过程实现如

45、下： Procedure FP_growth（Tree， ） if Tree 含单个路径P then for each 路径P中节点的每个组合（记作） 产生模式U，拥有支持度为节点中的最小支持度； else for each 树的头部列表节点ai 产生一个模式=aiU ，其支持度support=ai.support； 构造的条件模式基，然后构造的条件FP-树Tree if Tree then 调用FP_growth（Tree，）,2020/10/11,77,对FP-树方法的性能的研究表明：对于挖掘长的和短的频繁模式，它都是有效的和可伸缩的，并且大约比Apriori算法快一个数量级。,4.5.3

46、 FP-增长算法的评价,2020/10/11,78,有关技术能用于产生比基本规则更复杂的关联规则。,4.6 高级关联规则技术,2020/10/11,79,概念层次表明了不同项目之间的集合关系。 泛化关联规则利用概念层次产生不同层次的关联规则。 利用概念层次，可以在任何层次以及所有层次上生成关联规则。,4.6.1 泛化关联规则技术,2020/10/11,80,图中表示了食品的部分概念层次，该层次表明小麦面包是面包的一种。 关联规则“面包花生酱”比“谷物花生酱”具有更低的支持度和阈值。也很显然，包含任何一种谷物的事务比包含面包的事务多。 要在初级概念层次上找到高支持的购买模式是困难的。 泛化关联规

47、则的表示与常规关联规则类似（X Y），但要求Y中不存在比X中任何项目更高层次的项目。,2020/10/11,81,泛化关联规则的一个变种是多层关联规则。 对于多层关联规则，项目集可以出现在概念层次的任何层次上。 利用Apriori算法的一个变种，可以用自顶向下的方式遍历概念层次，并生成大项目集。 发现层次i的大项目集后，可以生成层次i+1的大项目集。 概念层次中某一层次的k阶大项目集可以用作候选，以便生成下一层次中孩子节点的k阶大项目集。 概念层次中越高层的项目集的支持度也越高，关联规则所需的最小支持度会随着不同的层次而变化。应用规则： 概念层次中处于同一层次的所有结点的最小支持度是一样的。

48、如果用ai表示概念层次中层次i的最小支持度，用ai-1表示层次i-1的最小支持度，则ai-1ai。,4.6.2 多层关联规则,2020/10/11,82,迄今讨论的关联规则算法假定数据是类别型的。 数量关联规则涉及了类别型和数量型数据。 一个数量关联规则的例子是： 顾客买3050美元一瓶的白酒他也买鱼子酱 不同于传统关联规则，如： 顾客买白酒他也买鱼子酱 消费数量被划分到一个区间（像聚类或分类中处理数值数据一样），项目可能是(面包：01),(面包：(12), (面包：(2), (果冻：01.5), (果冻：(1.5) 因为将一个大项目分成了几个项目，需要降低用于数量关联规则的最小支持度或最小置

49、信度。 当存在大量区间时，最小支持度问题会显著恶化。,4.6.3 数量关联规则,2020/10/11,83,4.7 由频繁项集产生关联规则,一旦从数据库D的事务中找出了频繁项集，由它们产生强关联规则是直截了当的。置信度使用下式计算：,Confidence(A B)=support_count(AB)/support_count(A) 其中：support_count(AB) 是包含AB的事务数， support_count(A) 是包含A的事务数。,2020/10/11,84,关联规则产生的步骤： 第1步：对于每一个频繁项集I，产生I的所有非空子集。 第2步：对于I的每一个非空子集s，如果 s

50、upport_count(I)/support_count(s) = min_conf 则输出关联规则“s （I-s）” ，其中min_conf为最小置信度阈值。,2020/10/11,85,例假设数据包含频繁项集I=I1，I2，I5： 第1步：对于频繁项集I=I1，I2，I5，产生I的所有非空子集:I1,I2,I1,I5,I2,I5,I1,I2,I5 第2步：对于I的每一个非空子集s，输出关联规则“s （I-s）” I1I2I5 confidence=2/4=50% I1I5I2 confidence=2/2=100% I2I5I1 confidence=2/2=100% I1I2I5 co

51、nfidence=2/6=33% I2I1I5 confidence=2/7=29% I5I1I2 confidence=2/7=100%,2020/10/11,86,如果最小置信度设定为70，则只有以下三个关联规则输出： I1I5I2 confidence=2/2=100% I2I5I1 confidence=2/2=100% I5I1I2 confidence=2/7=100%,2020/10/11,87,当用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些规则对于用户来说是有用的、有价值的，这里有两个层面： 用户主观的层面 系统客观的层面。,4.8 关联规则价值衡量的方法,20

52、20/10/11,88,很多的算法都使用“支持度-可信度”的框架。 并不是所有被挖掘出的强关联规则都有意义或都有用。 这样的结构有时会产生一些错误的结果。,4.8.1 系统客观层面,2020/10/11,89,例如下是从一个有5000名学生的学校的调查结果中进行挖掘的实例。提供早餐的零售商对这些学生每天早上所从事的活动进行了一次调查。数据表明：60%的学生（3000名学生）打篮球，75%的学生（3750名学生）吃这种早餐，40%的学生（2000名学生）既打篮球，也吃这种早餐。那么如果设minsup为40%，minconf为60%挖掘关联规则，我们可以得到如下的关联规则： 打篮球吃早餐（1） 这

53、条规则相应的置信度为2000/3000=0.66，是错误的关联规则，因为吃早餐的学生的比例是75%，大于66%。打篮球和吃早餐实际上是负关联的。,只凭支持度和置信度阈值未必总能找出符合实际的规则,2020/10/11,90,为了消除这种误导的规则，应该在关联规则AB的置信度超过某个特定的度量标准时，定义它为有意义的。 因此有如下关联规则S（A，B）/S（A） - S（B） d或者：S（A，B）- S（A）*S（B） k 式中d和k是适当的量。,从而提出了兴趣度的概念,2020/10/11,91,为了删掉一些无趣的规则，即避免生成“错觉”的关联规则，人们定义了兴趣度的度量值，通过兴趣度来修剪无趣

54、的规则 。 今后确定关联规则可以采用三个度量值：支持度、置信度、兴趣度。,兴趣度的定义,2020/10/11,92,引入如下计算公式： InterestR = (CR - SRH)/maxCR , SRH 其中：CR为规则R的置信度， SRH为原始记录中支持该规则推出的信息，即规则右部H的比例。 早餐问题的兴趣度计算： InterestR = (CR - SRH)/maxCR , SRH =（0.66 0.75）/0.75 = -0.12,（一）面向差异思想的兴趣度定义,2020/10/11,93,（二）已有的几种兴趣度的定义,除了把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作重新认

55、识项集，如Brin等考虑的相关规则中，讨论了蕴涵（暗示）规则(implication rule)，规则的蕴涵强度在0,之间变化，其中蕴涵强度为1表示完全无关的规则，表示完备的规则，如果蕴涵强度大于1则表示更大的期望存在性。 另一个度量值“收集强度”(collective strength)被定义，他们设想使用“大于期望值”来发现有意义的关联规则。项集的“收集强度”是0,之间的一个数值，其中0表示完备的否定相关性，而值表示完备的正相关性。,2020/10/11,94,结论： 一条规则的兴趣度越大于0，说明我们对这条规则越感兴趣，即实际利用价值越大。 一条规则的兴趣度越小于0，说明我们对这条规则的

56、反面规则越感兴趣，即其反面规则的实际利用价值越大。 另外一个事实：兴趣度门限值定得越高，挖掘出的规则越少，反之，挖掘出的规则越多。,（三）兴趣度的实际意义,2020/10/11,95,以上讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于用户的感觉。只有用户可以决定规则的有效性、可行性。所以应该将用户的需求和系统更加紧密的结合起来。,4.8.2 用户主观层面,提出了一种基于约束的挖掘,2020/10/11,96,具体约束的内容可以有： 数据约束。用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。 指定挖掘的维和层次。用户可以指定对数据在哪些维以及在这些维上哪些层次进行挖掘。 规则

57、约束。可以指定哪些类型的规则是我们所需要的。引入一个模板的概念，用户使用它来确定哪些规则是令人感兴趣的而哪些则不然：如果一条规则匹配一个包含的模板，则是令人感兴趣的，然而如果一条规则匹配一个限制的模板，则被认为是缺乏兴趣的。,2020/10/11,97,在算法中结合约束条件： 提高了效率 使挖掘的目的更加明确化 具体方法： Kleinberg等人引入并研究了一个新的优化问题分段问题，这个框架包含了一些标准的组合分类问题。这个模型根据基本的目标函数，对“被挖掘的数据”的价值提供一个特殊的算法的视角，显示了从这方面导出的具体的优化问题的广泛的应用领域。 Korn等就利用猜测误差(使用“均方根”来定

58、义)来作为一些从给定的数据集中对所发现规则的“好处”的度量，他们所定义的比例规则就是如下的规则：顾客大多数分别花费 1 : 2 : 5的钱在“面包”:“牛奶”:“奶油”上。,2020/10/11,98,通过确定未知的(等价的，被隐藏的，丢失的)值，比例规则可以用来作决策支持。如果数据点线性地相关的话，那么比例规则能达到更紧凑的描述，即关联规则更好地描述了相关性,2020/10/11,99,在客户关系管理（CRM）理论中有一个经典的2/8原则，即80%利润来自20%客户。那么，这20%的客户都有什么特征呢？ 调查发现，大部分企业每年有20%50%的客户是变动的。企业一方面在挖空心思争取新客户，另

59、一面却不断失去老客户。有没有办法找出，失去的是哪一类型的客户，得到的又是哪种类型的客户。在竞争激烈的商业时代，资源占有成为决定企业生死成败的关键。在客户关系方面，企业总希望建立与客户最稳固的关系，并最有效率地把这种关系转化为利润，即留住老顾客、发展新顾客并锁定利润率最高的客户，这也就是CRM要重点研究的问题。 为了实现这个目标，企业就需要尽可能地了解客户的行为，但这种了解不可能通过与客户接触直接获得，因为企业不可能挨个与客户交谈，而且他们所需要的信息单个客户往往无法提供。,4.9 关联规则挖掘在CRM中的应用,4.9.1 CRM简介,2020/10/11,100,企业所能做的，就是尽可能收集顾客的信息，借助各种分析方法，透过无序的、表层的信息挖出内在的知识和规律，这就当前十分流行的数据挖掘技术所研究的。 在挖出大量信息之后，企业就可以根据这些规律或用这些信息设计数学模型，对未发生行为做出结果预测，为企业的综合经营决策、市场策划提供依据。 在CRM中，数据挖掘是从大量的有关客户的数据中挖掘出隐含的、先前未知的、对企业决策有潜在价值的知识和规则。,2020