数据关联分析

1、第7章 数据关联分析 7.1基 本 概 念 7.2频繁项集产生 7.3规则产生 7.4频繁项集的紧凑表示 7.5 产生频繁项集的 其他方法 7.6FP-growth算法 7.7关 联 评 估 1 7.1 基本概念 关联分析关联分析（association analysis）用于发现隐藏在大型数据集中的令人）用于发现隐藏在大型数据集中的令人 感兴趣的联系，所发现的模式通常用关联规则（感兴趣的联系，所发现的模式通常用关联规则（association rule）或频繁）或频繁 项集的形式表示项集的形式表示。关于。关于关联规则的几个概念：关联规则的几个概念： 项集项集：项目：项目的集合，包含的集合，包

2、含k个项的项集称为个项的项集称为k-项集；项集； 支持度（支持度（support）：数据库：数据库中含有这个项集的所有项目在中含有这个项集的所有项目在事事务务集中集中 所占的比例。所占的比例。 置信度（置信度（confidence）：出现：出现项集项集A的事务集的事务集D中，项集中，项集B出现出现的概率。的概率。 频繁项集频繁项集：支持：支持度大于或等于度大于或等于min_sup的的项集。项集。 2 关联规则挖掘的两个步骤：关联规则挖掘的两个步骤： 频繁项集产生（支持度测试）。其目标是发现满足最小支持度阈频繁项集产生（支持度测试）。其目标是发现满足最小支持度阈 值的所有项集，即频繁项集。值的所

3、有项集，即频繁项集。 规则产生（置信度测试）。其目标是从上一步发现的频繁项集中规则产生（置信度测试）。其目标是从上一步发现的频繁项集中 提取所有高置信度（大于等于最小置信度阈值）的关联规则，即提取所有高置信度（大于等于最小置信度阈值）的关联规则，即 强关联规则。强关联规则。 在上述两个步骤中，第一步骤是关键，它将影响整个关联规则挖掘在上述两个步骤中，第一步骤是关键，它将影响整个关联规则挖掘 算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生。算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生。 7.1 基本概念 3 格结构（格结构（lattice structure）常常被用来枚举所有

4、可能的项集。图）常常被用来枚举所有可能的项集。图中中显示显示 的的是是I=a，b，c，d，e的项集格的项集格。包含。包含k个项的数据个项的数据集最多产生集最多产生2k-1 个频繁个频繁 项集，不包括项集，不包括空集。空集。 7.2 频繁项集产生 4 发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度 计数计数。这必须这必须比较每个比较每个候选项集与每个候选项集与每个事务。如候选事务。如候选项集包含在事务中，项集包含在事务中， 则候选项集的支持度计数增加则候选项集的支持度计数增加。如。如，由于项集，由于项集 Milk，Brea

5、d 出现在事务出现在事务 1，4，5中，其支持度计数将增加中，其支持度计数将增加3次次。这种比较开销大。这种比较开销大。 7.2 频繁项集产生 5 7.2.1 先验原理 先验原理先验原理是减少候选项集的数量（是减少候选项集的数量（M）的方法之一。）的方法之一。 其基本思想是其基本思想是：如果一个项集是频繁的，则它的所有子集一定也是：如果一个项集是频繁的，则它的所有子集一定也是 频繁的。例如，频繁的。例如，假定假定 c，d，e是频繁项是频繁项集，显然任何包含项集集，显然任何包含项集c，d， e的事务一定包含它的子集的事务一定包含它的子集c，d ， c，e ， d，e， c ， d和和 e。这样，

6、如果。这样，如果c，d，e是频繁的，则它的所有子集一定也是频繁是频繁的，则它的所有子集一定也是频繁 的。的。 反之，反之，如项集如项集是非频繁的，则它的所有超集也一定是非频繁的。是非频繁的，则它的所有超集也一定是非频繁的。 7.2 频繁项集产生 6 7.2.1 先验原理 如图所示，一旦发现如图所示，一旦发现a，b是非频繁的，则整个包含是非频繁的，则整个包含a，b超集的子超集的子 图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基 于支持度的剪枝。于支持度的剪枝。 7.2 频繁项集产生 7 7.2.2 Apriori算

7、法的频繁项集产生 Apriori算法算法是一种最具影响力的挖掘布尔关联规则频繁项集的算是一种最具影响力的挖掘布尔关联规则频繁项集的算 法。法。Apriori的命名由来是因为使用了频繁项集性质的先验知识，即的命名由来是因为使用了频繁项集性质的先验知识，即Apri ori性质。性质。Apriori性质的内容是：频繁项集的所有非空子集也必须是频繁性质的内容是：频繁项集的所有非空子集也必须是频繁 的。该性质通过减少搜索空间来提高频繁项集逐层产生的效率。的。该性质通过减少搜索空间来提高频繁项集逐层产生的效率。 Apriori算法利用算法利用Apriori性质，通过逐层搜索的迭代方法，将性质，通过逐层搜索

8、的迭代方法，将k-项集用项集用 于探索（于探索（k+1）-项集，来穷尽数据集中的所有频繁项集。项集，来穷尽数据集中的所有频繁项集。 7.2 频繁项集产生 8 7.2.2 Apriori算法的频繁项集产生 特点特点： 它是一个逐层算法，即从频繁它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍项集到最长的频繁项集，它每次遍 历项集格中的一层。先找到频繁历项集格中的一层。先找到频繁1-项集集合项集集合Ll，然后用，然后用Ll找到频繁找到频繁2- 项集集合项集集合L2，接着用，接着用L2找找L3，直到找不到频繁，直到找不到频繁k-项集，找每个项集，找每个Lk需要需要 一次数据库扫描；一次数

9、据库扫描； 它使用产生它使用产生-测试策略来发现频繁项集。在每次迭代之后，新的候选测试策略来发现频繁项集。在每次迭代之后，新的候选 项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度 进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次 数是数是kmax+1，其中，其中kmax是频繁项集的最大长度。是频繁项集的最大长度。 7.2 频繁项集产生 9 7.2.2 Apriori算法的频繁项集产生 Apriori Apriori算法的主要步骤由连接步和剪枝步组成。算法的主

10、要步骤由连接步和剪枝步组成。 连接步连接步。为找出为找出Lk，通过，通过Lk-1与自身连接产生候选与自身连接产生候选k-项集的项集的集合集合，记记 作作Ck。设。设l1和和l2是是Lk-1中的项集中的项集。lij表示表示li的第的第j项。假定项。假定事务或项集中事务或项集中 的项按字典次序的项按字典次序排序，排序，使得使得li1li2.lik-1。执行连接。执行连接Lk-1 Lk-1； 其中其中Lk-1的元素是可连接的，的元素是可连接的，如它们如它们前（前（k-2）个项相同）个项相同，即即Lk-1的元的元 素素l1和和l2是可连接的，是可连接的，如（如（l11=l21） （l12=l22） .

11、 （l1k-2 l2k-2） （l1k-1l2k-1）。条件）。条件l1k-1l2k-1是简单地确保不产生是简单地确保不产生 重复。连接重复。连接l1和和l2产生的结果项集是产生的结果项集是l11，l12，.l1k-1，l2k-1。 7.2 频繁项集产生 10 7.2.2 Apriori算法的频繁项集产生 剪枝步。剪枝步。 Ck是是Lk的超集的超集，即即Ck的成员可以是频繁的，也可以不是频的成员可以是频繁的，也可以不是频 繁的，但所有频繁繁的，但所有频繁k-项集都包含在项集都包含在Ck中。扫描数据库，确定中。扫描数据库，确定Ck中每中每 个候选的支持度计数，从而确定个候选的支持度计数，从而确定

12、Lk（即根据定义，计数值不小于最（即根据定义，计数值不小于最 小支持度计数的所有候选都是频繁的，从而属于小支持度计数的所有候选都是频繁的，从而属于Lk）。然而，）。然而，Ck可可 能很大，因此所涉及的计算量就很大。为了压缩能很大，因此所涉及的计算量就很大。为了压缩Ck，可以，可以用用Apriori 性质，性质，即即非非频繁的（频繁的（k-1）-项集都不是频繁项集都不是频繁k-项集的项集的子集，如候选子集，如候选k- 项集的（项集的（k-1）-子集不在子集不在Lk-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的，从而从而 从从Ck中删除。这种子集测试中删除。这种子集测试可使用可使用

13、所有频繁项集的散列树快速完成。所有频繁项集的散列树快速完成。 7.2 频繁项集产生 11 7.2.2 Apriori算法的频繁项集产生 下面下面举举一个具体例子。该例基于表中的一个具体例子。该例基于表中的AllElectronics的事务数据库的事务数据库 D。该数据库有该数据库有9个事务个事务，假定事务中的项按字典次序存放。假定事务中的项按字典次序存放。 7.2 频繁项集产生 12 7.2.2 Apriori算法的频繁项集产生 使用图使用图来来解释解释Apriori算法发现算法发现D中的频繁项集。中的频繁项集。 7.2 频繁项集产生 13 7.2.2 Apriori算法的频繁项集产生 挖掘布

14、尔关联规则发现频繁项集的挖掘布尔关联规则发现频繁项集的AprioriApriori算法如下。算法如下。 算法算法：Apriori。使用逐层迭代方法基于候选产生找出频繁项集。使用逐层迭代方法基于候选产生找出频繁项集。 输入输入：事务数据库：事务数据库D；最小支持度阈值；最小支持度阈值min_sup。 输出输出：D中的频繁项集中的频繁项集L。 方法方法： L1=find_frequent_1_itemsets（D）；）； for（k=2；Lk-1；k+） Ck=apriori_gen（Lk-1）；）； for each 事务事务tD /扫描扫描D，进行计数，进行计数 Ct=subset（Ck，t）

15、；）； /得到得到t的子集，它们是候选的子集，它们是候选 for each 候选候选cCt c.count+； ； Lk=cCk | c.countmin_sup； return L=k Lk； 7.2 频繁项集产生 14 7.2.2 Apriori算法的频繁项集产生 procedure apriori_gen（Lk-1：frequent（k-1）-itemsets） for each 项集项集l1 Lk-1 for each 项集 项集l2 Lk-1 if（ （l11=l21） . （l1k-2l2k-2） （l1k-1l2k-2） then c= l1 l2； /连接步：产生候选连接步：产

16、生候选 if has_infrequent_subset（c，Lk-1） then delete c； /剪枝步：删除非频繁的候选剪枝步：删除非频繁的候选 else add c to Ck； return Ck； procedure has_infrequent_subset(c：candidate k-itemsets；Lk- 1： ：frequent(k-1)-itemsets) /使用使用Apriori知识知识 for each（k-1）-subset s of c if s Lk-1 then return TRUE； return FALSE； 7.2 频繁项集产生 15 7.2.3

17、 支持度计数 支持度计数用以支持度计数用以确定在确定在apriori-gen函数的候选项剪枝步骤保留下来的函数的候选项剪枝步骤保留下来的 每个候选项集出现的频繁程度。每个候选项集出现的频繁程度。 计算支持度的主要方法有计算支持度的主要方法有两种两种： 一是一是将每个事务与所有候选项集进行比较，并且更新包含在事务中的将每个事务与所有候选项集进行比较，并且更新包含在事务中的 候选项集的支持度计数。这种方法的计算候选项集的支持度计数。这种方法的计算成本很高成本很高，尤其当事务和候，尤其当事务和候 选项集的数目都很大时。选项集的数目都很大时。 或或枚举枚举每个每个事务包含事务包含的项集，的项集，并利用

18、并利用其其更新更新对应的候选项集的支持度。对应的候选项集的支持度。 7.2 频繁项集产生 16 7.2.3 支持度计数 如图显示的是枚举事务如图显示的是枚举事务t中所有中所有3-项集的系统的方法。假定每个项集项集的系统的方法。假定每个项集 中的项都以递增的字典次序排列，则项集可以这样枚举：先指定最小项，中的项都以递增的字典次序排列，则项集可以这样枚举：先指定最小项， 其后跟随较大的项。其后跟随较大的项。 7.2 频繁项集产生 17 7.2.3 支持度计数 如如，给定，给定t=1，2，3，5，6，所有，所有3-项集一定以项项集一定以项1、2或或3开始。不开始。不 必构造以必构造以5或或6开始的开

19、始的3-项集。项集。图中第一层的前缀结构描述了指定包含在事图中第一层的前缀结构描述了指定包含在事 务务t中的中的3-项集的第一项的方法项集的第一项的方法。如。如1 2 3 5 6的的3-项集项集，以，以1开始，后随两个开始，后随两个 取自集合取自集合2，3，5，6的项的项。确定第一项后。确定第一项后，第二层的前缀结构表示选择，第二层的前缀结构表示选择 第二项的方法第二项的方法。如。如：1 2 3 5 6表示以表示以1，2为前缀，后随项为前缀，后随项3、5或或6的项集。的项集。 最后，第三层的前缀结构显示了事务最后，第三层的前缀结构显示了事务t包含的所有的包含的所有的3-项集项集。如。如，以，以

20、1，2 为前缀的为前缀的3-项集是项集是1，2，3，1，2，5和和1，2，6；而以；而以2，3为前缀为前缀 的的3-项集是项集是2，3，5和和2，3，6。 7.2 频繁项集产生 18 7.2.3 支持度计数 在在Apriori算法中，候选项集划分为不同的桶，并存放在算法中，候选项集划分为不同的桶，并存放在Hash树中。树中。 在支持度计数期间，包含在事务中的项集也散列到相应的桶中。这种方在支持度计数期间，包含在事务中的项集也散列到相应的桶中。这种方 法不是将事务中的每个项集与所有的候选项集进行比较，而是将它与同法不是将事务中的每个项集与所有的候选项集进行比较，而是将它与同 一桶内候选项集进行匹

21、配一桶内候选项集进行匹配。 7.2 频繁项集产生 19 7.2.3 支持度计数 上图是一棵上图是一棵Hash树结构的例子。树的每个内部结点都使用树结构的例子。树的每个内部结点都使用Hash函数函数 h(p)=p mod 3来确定应当沿着当前结点的哪个分支向下来确定应当沿着当前结点的哪个分支向下。如。如，项，项1，4和和7 应当散列到相同的分支（即最左分支），因为除以应当散列到相同的分支（即最左分支），因为除以3之后它们都具有相之后它们都具有相 同的余数。所有的候选项集都存放在同的余数。所有的候选项集都存放在Hash树的叶结点中。图中显示的树的叶结点中。图中显示的 Hash树包含树包含15个候选

22、个候选3-项集，即项集，即1，4，5，1，2，4，4，5，7，1， 2，5，4，5，8，1，5，9，1，3，6，2，3，4，5，6，7，3， 4，5，3，5，6，3，5，7，6，8，9，3，6，7，3，6，8，分，分 布在布在9个叶结点中。个叶结点中。 7.2 频繁项集产生 20 7.2.3支持度计数 考虑一个事务考虑一个事务t=1，2，3，5，6。为了更新候选项集的支持度计数，。为了更新候选项集的支持度计数， 必须这样遍历必须这样遍历Hash树：所有包含属于事务树：所有包含属于事务t的候选的候选3-项集的叶结点至少访项集的叶结点至少访 问一次。例如，在根结点散列项问一次。例如，在根结点散列项

23、1之后，散列事务的项之后，散列事务的项2，3和和5。项。项2和和5散散 列到中间子女，而列到中间子女，而3散列到右子女，如图所示。继续该过程，直至到达散列到右子女，如图所示。继续该过程，直至到达 Hash树的叶结点。树的叶结点。 7.2 频繁项集产生 21 7.2.4 计算复杂度 AprioriApriori算法的计算复杂度受如下因素影响：算法的计算复杂度受如下因素影响： 支持度阈值支持度阈值。支持。支持度度阈值阈值影响影响频繁项集数量。频繁项集数量。 项数（维数）。随着项数的增加，需要更多的空间来存储项的支持项数（维数）。随着项数的增加，需要更多的空间来存储项的支持 度计数。度计数。如频繁如

24、频繁项集的数目也随着数据项数增加而增长，则由于算项集的数目也随着数据项数增加而增长，则由于算 法产生的候选项集更多，计算量和法产生的候选项集更多，计算量和I/O开销将增加。开销将增加。 事务数事务数。算法。算法反复扫描数据集反复扫描数据集，运行时间，运行时间随着事务数增加而增加。随着事务数增加而增加。 事务的平均宽度。对于密集数据集，事务的平均宽度可能很大，这事务的平均宽度。对于密集数据集，事务的平均宽度可能很大，这 将影响将影响Apriori算法的复杂度。算法的复杂度。 7.2 频繁项集产生 22 7.2.4 计算复杂度 7.2 频繁项集产生 23 因为由频繁项集的项组成的关联规则的支持度大

25、于等于最小支持度因为由频繁项集的项组成的关联规则的支持度大于等于最小支持度 阈值，所以规则产生过程就是在由频繁项集的项组成的所有关联规则阈值，所以规则产生过程就是在由频繁项集的项组成的所有关联规则 中，找出所有置信度大于等于最小置信度阈值的强关联规则。中，找出所有置信度大于等于最小置信度阈值的强关联规则。 计算关联规则的置信度并不需要再次扫描事务数据库。每个频繁计算关联规则的置信度并不需要再次扫描事务数据库。每个频繁k- 项集能产生最多项集能产生最多2k-2个关联规则。个关联规则。 7.3 规则产生 24 7.3.1 基本步骤 规则产生的基本步骤如下：规则产生的基本步骤如下： （1）对于每个频

26、繁项集）对于每个频繁项集l，产生，产生l的所有非空子集；的所有非空子集； （2）对于）对于l的每个非空子集的每个非空子集s，如果，如果 则输出规则则输出规则“ ”。其中。其中min_conf是最小置信度阈值。是最小置信度阈值。 7.3 规则产生 25 7.3.1 基本步骤 例如例如，AllElectronics事务事务数据库数据库，包含包含频繁项集频繁项集X=I1，I2，I5，可可 由由X产生产生6个候选关联规则，即个候选关联规则，即X的非空子集：的非空子集：I1，I2，I1，I5，I2， I5，I1，I2和和I5。结果关联规则如下，每个都列出置信度。结果关联规则如下，每个都列出置信度。 如果

27、最小置信度阈值为如果最小置信度阈值为70，则只有，则只有2、3和最后一个规则可以输出，和最后一个规则可以输出， 因为只有这些是强的因为只有这些是强的。 7.3 规则产生 26 7.3.1 Apriori算法中规则的产生 Apriori算法使用一种逐层方法来产生关联规则，其中每层对应于规算法使用一种逐层方法来产生关联规则，其中每层对应于规 则后件中的项数。则后件中的项数。首先首先，提取规则后件只含一个项的所有高置信度规则，提取规则后件只含一个项的所有高置信度规则， 其次其次使用这些规则来产生新的候选规则。使用这些规则来产生新的候选规则。 7.3 规则产生 27 7.3.1 Apriori算法中规

28、则的产生 例如，例如， acdb和和abdc是两个高置信度的规则，则通过合并是两个高置信度的规则，则通过合并 这两个规则的后件产生候选规则这两个规则的后件产生候选规则adbc。图。图中中显示了由频繁项集产生显示了由频繁项集产生 关联规则的格结构。如果格中的任意结点具有低置信度，则关联规则的格结构。如果格中的任意结点具有低置信度，则可立即可立即剪掉剪掉 该结点生成的整个子图。假设规则该结点生成的整个子图。假设规则bcda具有低置信度，则可以丢弃具有低置信度，则可以丢弃 后件包含后件包含a的所有规则，包括的所有规则，包括cdab，bdac，bcad和和 dabc等等。Apriori算法中规则产生过

29、程与频繁项集产生过程类似，二算法中规则产生过程与频繁项集产生过程类似，二 者唯一的不同是，在规则产生时，不必再次扫描数据者唯一的不同是，在规则产生时，不必再次扫描数据集计算集计算候选规则的候选规则的 置信度，置信度，而使用而使用频繁项集产生时计算的支持度计数来频繁项集产生时计算的支持度计数来确定规则确定规则的置信度的置信度。 7.3 规则产生 28 实践中，由事务数据集产生的频繁项集的数量可能非常大。因此，实践中，由事务数据集产生的频繁项集的数量可能非常大。因此， 从中识别出可以推导出其他所有的频繁项集的、较小的、具有代表性的从中识别出可以推导出其他所有的频繁项集的、较小的、具有代表性的 项集

30、是非常有用的。项集是非常有用的。 下面介绍两种具有代表性的项集：下面介绍两种具有代表性的项集： 最大频繁项集最大频繁项集 闭频繁项集闭频繁项集 7.4 频繁项集的紧凑表示 29 7.4.1 最大频繁项集 最大频繁项集：直接超集都不是频繁的。 7.4 频繁项集的紧凑表示 30 7.4.1 最大频繁项集 上上图所示是图所示是项集格。格中的项集分为两组：频繁项集和非频繁项集。项集格。格中的项集分为两组：频繁项集和非频繁项集。 虚线表示频繁项集的边界。位于边界上方的每个项集都是频繁的，而位于虚线表示频繁项集的边界。位于边界上方的每个项集都是频繁的，而位于 边界下方的项集（阴影结点）都是非频繁的。在边界

31、边界下方的项集（阴影结点）都是非频繁的。在边界附近结点附近结点中，中，a，d， a，c，e和和b，c，d，e都是最大频繁项集，因为它们的直接超集都是非频都是最大频繁项集，因为它们的直接超集都是非频 繁的繁的。如。如，项集，项集a，d是最大频繁的，因为它的所有直接超集是最大频繁的，因为它的所有直接超集a，b，d ， a，c，d和和a，d，e都是非频繁的；相反，项集都是非频繁的；相反，项集a，c不是最大的，因为不是最大的，因为 它的一个直接超集它的一个直接超集a，c，e是频繁的是频繁的。最大。最大频繁项集有效地提供了频繁项频繁项集有效地提供了频繁项 集的紧凑表示集的紧凑表示。最大。最大频繁项集形成

32、了频繁项集形成了可导出可导出所有频繁项集的最小的项集的所有频繁项集的最小的项集的 集合。集合。 7.4 频繁项集的紧凑表示 31 7.4.2 闭频繁项集 闭项集闭项集：直接：直接超集都不具有和它相同的支持度计数超集都不具有和它相同的支持度计数。闭闭频繁项集频繁项集：支：支 持持度大于或等于最小支持度度大于或等于最小支持度阈值阈值的闭项集的闭项集。 7.4 频繁项集的紧凑表示 32 7.4.2 闭频繁项集 闭频繁项集示例如闭频繁项集示例如上上图。为了更好地解释每个项集的支持度计数，格图。为了更好地解释每个项集的支持度计数，格 中每个结点（项集）都标出了与它相关联的事务的中每个结点（项集）都标出了

33、与它相关联的事务的ID。例如，由于结点。例如，由于结点b， c与与事务事务ID 1，2和和3相关联，因此它的支持度计数为相关联，因此它的支持度计数为3。从给定的事务可以。从给定的事务可以 看出，包含看出，包含b的每个事务也包含的每个事务也包含c，因此，由于，因此，由于b和和b，c的支持度是相同的支持度是相同 的，所以的，所以b不是闭项集。同样，由于不是闭项集。同样，由于c出现在所有包含出现在所有包含a和和d的事务中，所的事务中，所 以项集以项集a，d不是闭的。另一方面，不是闭的。另一方面， b，c是闭项集，因为它的支持度计是闭项集，因为它的支持度计 数与它的任何超集都不同。数与它的任何超集都不

34、同。 7.4 频繁项集的紧凑表示 33 Apriori算法通过使用先验原理对指数搜索空间进行剪枝，成功地处理算法通过使用先验原理对指数搜索空间进行剪枝，成功地处理 了频繁项集产生的组合爆炸问题。虽然显著提高了性能，但该算法还是会了频繁项集产生的组合爆炸问题。虽然显著提高了性能，但该算法还是会 导致不可低估的导致不可低估的I/O开销，因为它需要多次扫描事务数据集。此外，对于稠开销，因为它需要多次扫描事务数据集。此外，对于稠 密数据集，由于事务数据宽度的增加，密数据集，由于事务数据宽度的增加，Apriori算法的性能显著降低。为了算法的性能显著降低。为了 克服这些局限性和提高克服这些局限性和提高A

35、priori算法的效率，已开发了一些替代方法。算法的效率，已开发了一些替代方法。 7.5 产生频繁项集的其它方法 34 7.5.1 项集格遍历 概念上，可以将频繁项集的搜索看作遍历项集格。算法使用的搜索策概念上，可以将频繁项集的搜索看作遍历项集格。算法使用的搜索策 略指明了频繁项集产生过程中如何遍历格结构。根据频繁项集在格中的布略指明了频繁项集产生过程中如何遍历格结构。根据频繁项集在格中的布 局，某些搜索策略优于其他策略。局，某些搜索策略优于其他策略。 一般到特殊与特殊到一般一般到特殊与特殊到一般 7.5 产生频繁项集的其它方法 35 7.5.1 项集格遍历 Apriori算法使用了算法使用了

36、“一般到特殊一般到特殊”的搜索策略，合并两个频繁（的搜索策略，合并两个频繁（k-1） -项集得到候选项集得到候选k-项集。使用这种策略效果最好的频繁项集的布局显示在上项集。使用这种策略效果最好的频繁项集的布局显示在上 图（图（a）中，其中较黑的结点代表非频繁项集。相反，）中，其中较黑的结点代表非频繁项集。相反，“特殊到一般特殊到一般”的搜的搜 索策略在发现更一般的频繁项集之前，先寻找更特殊的频繁项集。这种策索策略在发现更一般的频繁项集之前，先寻找更特殊的频繁项集。这种策 略对于发现稠密事务中的最大频繁项集是有用的。稠密事务中频繁项集的略对于发现稠密事务中的最大频繁项集是有用的。稠密事务中频繁项

37、集的 边界靠近格的底部，如上图（边界靠近格的底部，如上图（b）所示。可以使用先验原理剪掉最大频繁项）所示。可以使用先验原理剪掉最大频繁项 集的所有子集。另一种策略是结合集的所有子集。另一种策略是结合“一般到特殊一般到特殊”和和“特殊到一般特殊到一般”的搜的搜 索策略，尽管这种双向搜索方法需要更多的空间存储候选项集，但是上图索策略，尽管这种双向搜索方法需要更多的空间存储候选项集，但是上图 （c）所示的布局，该方法有助于加快确定频繁项集边界。）所示的布局，该方法有助于加快确定频繁项集边界。 7.5 产生频繁项集的其它方法 36 7.5.1 项集格遍历 等价类等价类 该方法是先将格划分为两个不相交的

38、结点组（或等价类）。频繁项该方法是先将格划分为两个不相交的结点组（或等价类）。频繁项 集产生算法依次在每个等价类内搜索频繁项集。集产生算法依次在每个等价类内搜索频繁项集。 7.5 产生频繁项集的其它方法 37 7.5.1 项集格遍历 Apriori算法采用的逐层策略可以看作根据项集的大小划分格，即在算法采用的逐层策略可以看作根据项集的大小划分格，即在 处理较大项集之前，首先找出所有的频繁处理较大项集之前，首先找出所有的频繁1-项集。等价类也可以根据项集项集。等价类也可以根据项集 的前缀或后缀来定义。在这种情况下，两个项集属于同一个等价类，如的前缀或后缀来定义。在这种情况下，两个项集属于同一个等

39、价类，如 果它们共享长度为果它们共享长度为k的相同前缀或后缀。在基于前缀的方法中，算法首先的相同前缀或后缀。在基于前缀的方法中，算法首先 搜索以前缀搜索以前缀a开始的频繁项集，然后是以前缀开始的频繁项集，然后是以前缀b等开始的频繁项集，然后等开始的频繁项集，然后 中中c，如此下去。基于前缀和基于后缀的等价类都可以使用，如此下去。基于前缀和基于后缀的等价类都可以使用上上图中所示的图中所示的 类似于树的结构来演示。类似于树的结构来演示。 7.5 产生频繁项集的其它方法 38 7.5.1 项集格遍历 宽度优先与深度优先宽度优先与深度优先 Apriori算法采用宽度优先的方法遍历格，如图（算法采用宽度

40、优先的方法遍历格，如图（a）所示。它首先发）所示。它首先发 现所有频繁现所有频繁1-项集，接下来是频繁项集，接下来是频繁2-项集，如此下去直到没有新的频繁项项集，如此下去直到没有新的频繁项 集产生为止。也可以以用深度优先的方式遍历项集格，如图（集产生为止。也可以以用深度优先的方式遍历项集格，如图（b）所示。）所示。 7.5 产生频繁项集的其它方法 39 7.5.1项集格遍历 比如说，算法可以从图中的结点比如说，算法可以从图中的结点a开始，计算其支持度计数并判断它是开始，计算其支持度计数并判断它是 否频繁。如果是，算法渐增地扩展下层结点，即否频繁。如果是，算法渐增地扩展下层结点，即ab，abc，

41、等等，直到到达，等等，直到到达 一个非频繁结点，如一个非频繁结点，如abcd。然后，回溯到下一个分支，比如说。然后，回溯到下一个分支，比如说abce，并且继，并且继 续搜索。续搜索。 7.5 产生频繁项集的其它方法 40 7.5.1 项集格遍历 通常，深度优先搜索方法用于发现最大频繁项集通常，深度优先搜索方法用于发现最大频繁项集。比宽度优先更。比宽度优先更快快 地检测到频繁项集边界。一旦发现一个最大频繁项集，就地检测到频繁项集边界。一旦发现一个最大频繁项集，就可在可在它的子集它的子集 上剪枝。如上剪枝。如，上图中的结点，上图中的结点bcde是最大频繁项集，则算法就不必访问以是最大频繁项集，则算

42、法就不必访问以bd， be，c，d和和e为根的子树，因为它们不可能包含任何最大频繁项集。然而，为根的子树，因为它们不可能包含任何最大频繁项集。然而， 如如abc是最大频繁项集，则只有是最大频繁项集，则只有ac和和bc这样的结点不是最大频繁项集，但这样的结点不是最大频繁项集，但 以它们为根的子树还可能包含最大频繁项集。深度优先方法还允许使用以它们为根的子树还可能包含最大频繁项集。深度优先方法还允许使用 不同的基于项集支持度的剪枝方法不同的基于项集支持度的剪枝方法。如。如，假定项集，假定项集 a，b，c和和a，b具具 有相同的支持度，则有相同的支持度，则可跳可跳过以过以abd和和abe为根的子树为

43、根的子树，不，不包含最大频繁项集。包含最大频繁项集。 7.5 产生频繁项集的其它方法 41 7.5.2 事务数据集的表示 表示表示购物篮事务的两种不同方法。左边的表示法称作购物篮事务的两种不同方法。左边的表示法称作水平数据布局水平数据布局，许多，许多 关联规则挖掘算法（包括关联规则挖掘算法（包括Apriori）都采用这种表示法；）都采用这种表示法；右右边的表示法是存边的表示法是存 储与每一个项相关联的事务标识符列表（储与每一个项相关联的事务标识符列表（TID列表），这种表示法称作列表），这种表示法称作垂直垂直 数据布局数据布局。候选项集的支持度通过取其子项集。候选项集的支持度通过取其子项集TI

44、D列表的交得到。列表的交得到。 7.5 产生频繁项集的其它方法 42 7.6FP-growth算法 FP-growth（Frequent-Pattern growth，频繁模式增长）算法的，频繁模式增长）算法的基本思基本思 想想是是采用分采用分治策略：首先，将代表频繁项集的数据库压缩到一棵治策略：首先，将代表频繁项集的数据库压缩到一棵FP树（树（F requent-Pattern tree，频繁模式树），该树仍保留项集的关联信息。，频繁模式树），该树仍保留项集的关联信息。其其 次次，将这种压缩后的数据库划分成一组条件数据库（一种特殊类型的投影，将这种压缩后的数据库划分成一组条件数据库（一种特殊

45、类型的投影 数据库），每个数据库关联一个频繁项或数据库），每个数据库关联一个频繁项或“模式段模式段”，并分别挖掘每个条，并分别挖掘每个条 件数据库。对于每个件数据库。对于每个“模式片段模式片段”，只需要考察与它相关联数据集，只需要考察与它相关联数据集。随着。随着 被考察的模式的被考察的模式的“增长增长”，可以，可以显著地压缩被搜索的数据集的大小。显著地压缩被搜索的数据集的大小。 43 7.6.1 FP树构造 利用利用FP-growthFP-growth算法构造频繁模式树的过程如下：算法构造频繁模式树的过程如下： （1）按）按Apriori算法，第一次扫描事务数据库算法，第一次扫描事务数据库D，

46、导出频繁，导出频繁1-项集，并项集，并 得到它们的支持度计数（频度）。设最小支持度计数为得到它们的支持度计数（频度）。设最小支持度计数为2 ，频繁项的集合，频繁项的集合 按支持度计数的降序排序。结果集或表记作按支持度计数的降序排序。结果集或表记作L。这样有。这样有L=I2:7，I1:6， I3:6，I4:2，I5:2，如图所示。，如图所示。 7.6FP-growth算法 44 7.6.1 FP树构造 （2）创建树的根结点，并标记为）创建树的根结点，并标记为“null”。第二次扫描数据库。第二次扫描数据库D。每个。每个 事务中的项都按事务中的项都按L中的次序处理（即按支持度计数降序排序），并对每

47、个事中的次序处理（即按支持度计数降序排序），并对每个事 务创建一个分枝。例如，第一个事务务创建一个分枝。例如，第一个事务“T100：I1，I2，I5”按按L的次序包含的次序包含 三个项三个项I2，I1，I5，导致构造树的第一个分枝，导致构造树的第一个分枝。该分枝具有。该分枝具有3个结点，其中个结点，其中I2作为根的子女链接到根，作为根的子女链接到根，I1链接到链接到I2，I5链链 接到接到I1，如图所示。，如图所示。 7.6FP-growth算法 45 7.6.1 FP树构造 第二个事务第二个事务T200按按L的次序包含的次序包含I2和和I4，它导致一个分枝，其中，它导致一个分枝，其中I2链链

48、 接到根，接到根，I4链接到链接到I2。然而，该分枝。然而，该分枝应与应与T100已存在的路径共享前缀已存在的路径共享前缀。 因此将因此将结点结点I2的计数增加的计数增加1，并创建一个新结点（，并创建一个新结点（I4:1），它作为（），它作为（I2:2） 子女链接，如图所示。一般地，当为一个事务考虑增加分枝时，沿共同前子女链接，如图所示。一般地，当为一个事务考虑增加分枝时，沿共同前 缀上的每个结点的计数增加缀上的每个结点的计数增加1，为随在前缀之后的项创建结点并链接。，为随在前缀之后的项创建结点并链接。 7.6FP-growth算法 46 7.6.1 FP树构造 为了方便树的遍历，创建一个项头

49、表，使每项通过一个结点链指向它为了方便树的遍历，创建一个项头表，使每项通过一个结点链指向它 在树中的位置。扫描所有的事务后得到的树在树中的位置。扫描所有的事务后得到的树如图所示如图所示，带有相关的结点链。，带有相关的结点链。 这样，数据库频繁模式的挖掘问题就转换成挖掘这样，数据库频繁模式的挖掘问题就转换成挖掘FP树的问题。树的问题。 7.6FP-growth算法 47 7.6.2 频繁项集产生 FP FP树的挖掘过程为：树的挖掘过程为： 由长度为由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基的频繁模式（初始后缀模式）开始，构造它的条件模式基 （一个（一个“子数据库子数据库”，由，

50、由FP树中与该后缀模式一起出现的前缀路径集组树中与该后缀模式一起出现的前缀路径集组 成）。然后，构造它的（条件）成）。然后，构造它的（条件）FP树，并递归地在该树上进行挖掘。模式树，并递归地在该树上进行挖掘。模式 增长通过后缀模式与条件增长通过后缀模式与条件FP树产生的频繁模式连接实现。树产生的频繁模式连接实现。 7.6FP-growth算法 48 7.6.2 频繁项集产生 该该FP树的挖掘过程总结如树的挖掘过程总结如上上表所示。首先考虑表所示。首先考虑I5，它是，它是L中的最后一项，中的最后一项， 而不是第一项而不是第一项。I5出现在出现在FP树的两个分枝中（树的两个分枝中（I5的出现容易通

51、过沿它的结的出现容易通过沿它的结 点链找到）。这些路径由分枝点链找到）。这些路径由分枝和和形成。因此，形成。因此， 考虑以考虑以I5为后缀，它的两个对应前缀路径是为后缀，它的两个对应前缀路径是和和，形，形 成成I5的条件模式基。使用这些条件模式基作为事务数据库，构造的条件模式基。使用这些条件模式基作为事务数据库，构造I5的条件的条件 FP树，它只包含单个路径树，它只包含单个路径；不包含；不包含I3，因为它的支持，因为它的支持度度1，小，小 于最小支持度计数。该单个路径产生频繁模式的所有组合：于最小支持度计数。该单个路径产生频繁模式的所有组合：I2 I5:2，I1 I5:2， I2 I1 I5:

52、2。对于。对于I4，它的两个前缀形成条件模式基，它的两个前缀形成条件模式基(I2 I1:1）,（I2:1)，产，产 生一个单结点的条件生一个单结点的条件FP树树，并导出一个频繁模式，并导出一个频繁模式I2 I4:2。 7.6FP-growth算法 49 7.6.2 频繁项集产生 类似于以上分析，类似于以上分析，I3的条件模式基是的条件模式基是(I2 I1:2）,（I2:2）,（I1:2)。它。它 的条件的条件FP树有两个分枝树有两个分枝和和，如图所示，它产生模式集：，如图所示，它产生模式集： I2 I3:4，I1 I3:4，I2 I1 I3:2。最后，。最后，I1的条件模式基是的条件模式基是(

53、I2:4)，它的，它的FP树树 只包含一个结点只包含一个结点，只产生一个频繁模式，只产生一个频繁模式I2 I1:4。 7.6FP-growth算法 50 7.6.2 频繁项集产生 7.6FP-growth算法 51 7.6.2 频繁项集产生 优点：优点： FP-growth算法仅仅遍历了算法仅仅遍历了2次数据库，第一次是为了产生次数据库，第一次是为了产生L1，第二，第二 次是为了对项目排序。由于不用多次扫描数据库，次是为了对项目排序。由于不用多次扫描数据库，因而因而大大节省了扫大大节省了扫 描数据库的时间；描数据库的时间； 选用了分治策略，把挖掘的长频繁模式转换成递归地挖掘短模式的问选用了分治

54、策略，把挖掘的长频繁模式转换成递归地挖掘短模式的问 题，再与后缀相连；题，再与后缀相连； 挖掘长频繁模式与短的频繁模式时，有效性与可伸缩性都是该算法的挖掘长频繁模式与短的频繁模式时，有效性与可伸缩性都是该算法的 特点，特点，所用所用挖掘时间会比挖掘时间会比Apriori算法的挖掘时间少得多。算法的挖掘时间少得多。 7.6FP-growth算法 52 7.6.2 频繁项集产生 缺点：缺点： 建立建立FP树时，会占用大量的内存空间。如果数据库的规模很大，要树时，会占用大量的内存空间。如果数据库的规模很大，要 建立的建立的FP树也会很巨大；树也会很巨大； 在递归构建在递归构建FP树时，每生成一个频繁

55、模式就会出现一个条件树。当树时，每生成一个频繁模式就会出现一个条件树。当 生成与释放海量的条件树时，生成与释放海量的条件树时，该算法该算法将占用很多的运算时间与计算将占用很多的运算时间与计算 机空间。机空间。 7.6FP-growth算法 53 7.7关联评估 在实际情况中，商业数据库的数据量和维数都非常大，运用关联分析在实际情况中，商业数据库的数据量和维数都非常大，运用关联分析 算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。因此，算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。因此， 建立一组广泛接受的评价关联模式质量的标准是非常重要的。建立一组广泛接受的评价关联模式质

56、量的标准是非常重要的。 第一组标准第一组标准可通过可通过统计论据建立。涉及相互独立的项或覆盖少量事务统计论据建立。涉及相互独立的项或覆盖少量事务 的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。 第二组标准第二组标准可通过可通过主观论据建立，即模式被主观地认为是无趣的，除主观论据建立，即模式被主观地认为是无趣的，除 非它能够揭示料想不到的信息或提供导致有益的行动的有用信息非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。 54 7.7.1 兴趣度客观度量 客观度量常常基于列联表中列出的频度计数来计算。一对二元变

57、量客观度量常常基于列联表中列出的频度计数来计算。一对二元变量A和和 B的列联表的列联表如表所示如表所示。使用记号。使用记号 A（B）表示）表示A（B）不在事务中出现。在这）不在事务中出现。在这 个个22的表中，每个的表中，每个fij都代表一个频度计数都代表一个频度计数。如。如，f11表示表示A和和B同时出现在一同时出现在一 个事务中的次数，个事务中的次数，f01表示包含表示包含B但不包含但不包含A的事务的个数。行和的事务的个数。行和f1+表示表示A的支的支 持度计数，而列和持度计数，而列和f+1表示表示B的支持度计数。的支持度计数。 7.7关联评估 55 7.7.1 兴趣度客观度量 支持度置信

58、度框架的局限性支持度置信度框架的局限性。现有关联规则的挖掘算法依赖于支持。现有关联规则的挖掘算法依赖于支持 度和置信度来除去没有意义的模式。支持度的缺点在于许多潜在的有意义度和置信度来除去没有意义的模式。支持度的缺点在于许多潜在的有意义 的模式由于包含支持度小的项而被删去。置信度的缺点的模式由于包含支持度小的项而被删去。置信度的缺点更微妙更微妙，最适合用，最适合用 下面的例子进行说明下面的例子进行说明。假定。假定希望分析爱喝咖啡和爱喝茶的人之间的关系。希望分析爱喝咖啡和爱喝茶的人之间的关系。 收集一组人关于饮料偏爱的信息，并汇总在表中。收集一组人关于饮料偏爱的信息，并汇总在表中。 7.7关联评

59、估 56 7.7.1 兴趣度客观度量 7.7关联评估 57 7.7.1 兴趣度客观度量 兴趣因子兴趣因子。茶和咖啡的例子表明，由于置信度度量忽略了规则后件中。茶和咖啡的例子表明，由于置信度度量忽略了规则后件中 出现的项集的支持度，高置信度的规则有时存在误导。解决这个问题的一出现的项集的支持度，高置信度的规则有时存在误导。解决这个问题的一 种方法是使用称作提升度（种方法是使用称作提升度（lift）的度量）的度量： 它计算规则置信度和规则后件中项集的支持度之间的比率。对于二元它计算规则置信度和规则后件中项集的支持度之间的比率。对于二元 变量，提升度等价变量，提升度等价于兴趣于兴趣因子的客观因子的客

60、观度量：度量： 对于相互独立的两个变量，对于相互独立的两个变量，I(A,B)=1 ；如果如果A和和B是正相关的，则是正相关的，则 I(A,B)1；如果；如果A和和B是负相关的是负相关的，则，则 I(A,B)1 。 7.7关联评估 58 7.7.1 兴趣度客观度量 兴趣因子的局限性兴趣因子的局限性。两个词两个词 p,q和和r,s 出现的频率出现的频率如表所示如表所示。使用公。使用公 式式得出得出p,q和和r,s 的兴趣因子分别为的兴趣因子分别为1.02和和4.08。这些结果有点。这些结果有点问题：虽然问题：虽然 p和和q同时出现在同时出现在88%的文档中，的文档中，但它们但它们的兴趣因子的兴趣因