数据关联分析.pptx

《数据关联分析.pptx》由会员分享，可在线阅读，更多相关《数据关联分析.pptx（75页珍藏版）》请在课桌文档上搜索。

1、,第7章 数据关联分析,7.1,基 本 概 念,7.2,频繁项集产生,7.3,规则产生,7.4,频繁项集的紧凑表示,7.5,产生频繁项集的其他方法,7.6,FP-growth算法,7.7,关 联 评 估,1,7.1,基本概念,关联分析（association analysis）用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则（association rule）或频繁项集的形式表示。关于关联规则的几个概念：项集：项目的集合，包含k个项的项集称为k-项集；支持度（support）：数据库中含有这个项集的所有项目在事务集中所占的比例。置信度（confidence）：出现项集A

2、的事务集D中，项集B出现的概率。频繁项集：支持度大于或等于min_sup的项集。,2,关联规则挖掘的两个步骤：频繁项集产生（支持度测试）。其目标是发现满足最小支持度阈值的所有项集，即频繁项集。规则产生（置信度测试）。其目标是从上一步发现的频繁项集中提取所有高置信度（大于等于最小置信度阈值）的关联规则，即强关联规则。在上述两个步骤中，第一步骤是关键，它将影响整个关联规则挖掘算法的效率。因此，关联规则挖掘算法的核心是频繁项集产生。,7.1,基本概念,3,格结构（lattice structure）常常被用来枚举所有可能的项集。图中显示的是I=a，b，c，d，e的项集格。包含k个项的数据集最多产生2

3、k-1 个频繁项集，不包括空集。,7.2,频繁项集产生,4,发现频繁项集的一种原始方法是确定格结构中每个候选项集的支持度计数。这必须比较每个候选项集与每个事务。如候选项集包含在事务中，则候选项集的支持度计数增加。如，由于项集 Milk，Bread 出现在事务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。这样，如

4、果c，d，e是频繁的，则它的所有子集一定也是频繁的。反之，如项集是非频繁的，则它的所有超集也一定是非频繁的。,7.2,频繁项集产生,6,7.2.1,先验原理,如图所示，一旦发现a，b是非频繁的，则整个包含a，b超集的子图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝。,7.2,频繁项集产生,7,7.2.2,Apriori算法的频繁项集产生,Apriori算法是一种最具影响力的挖掘布尔关联规则频繁项集的算法。Apriori的命名由来是因为使用了频繁项集性质的先验知识，即Apriori性质。Apriori性质的内容是：频繁项集的所有非空子集也必须是频繁的。该性质通过减

5、少搜索空间来提高频繁项集逐层产生的效率。Apriori算法利用Apriori性质，通过逐层搜索的迭代方法，将k-项集用于探索（k+1）-项集，来穷尽数据集中的所有频繁项集。,7.2,频繁项集产生,8,7.2.2,Apriori算法的频繁项集产生,特点：它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层。先找到频繁1-项集集合Ll，然后用Ll找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描；它使用产生-测试策略来发现频繁项集。在每次迭代之后，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最

6、小支持度阈值进行比较。该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大长度。,7.2,频繁项集产生,9,7.2.2,Apriori算法的频繁项集产生,Apriori算法的主要步骤由连接步和剪枝步组成。连接步。为找出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）.（l1k-2l2k-

7、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中每个候选的支持度计数，从而确定Lk（即根据定义，计数值不小于最小支持度计数的所有候选都是频繁的，从而属于Lk）。然而，Ck可能很大，因此所涉及的计算量就很大。为了压缩Ck，可以用Apriori性质，即非频繁的（k-1）-项集都不是频繁k-项集的子集

8、，如候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而从Ck中删除。这种子集测试可使用所有频繁项集的散列树快速完成。,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算法的频繁项集产生,挖掘布尔关联规则发现频繁项集的Apriori算法如下

9、。算法：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）；/得到t的子集，它们是候选 for each 候选cCt c.count+；Lk=cCk|c.countmin_sup；return L=k Lk；,7.2,频繁项集产生,14,7.2.2,Apriori算法的频繁项集产生,procedur

10、e 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；/连接步：产生候选 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)-

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

12、.3,支持度计数,如图显示的是枚举事务t中所有3-项集的系统的方法。假定每个项集中的项都以递增的字典次序排列，则项集可以这样枚举：先指定最小项，其后跟随较大的项。,7.2,频繁项集产生,17,7.2.3,支持度计数,如，给定t=1，2，3，5，6，所有3-项集一定以项1、2或3开始。不必构造以5或6开始的3-项集。图中第一层的前缀结构描述了指定包含在事务t中的3-项集的第一项的方法。如1 2 3 5 6的3-项集，以1开始，后随两个取自集合2，3，5，6的项。确定第一项后，第二层的前缀结构表示选择第二项的方法。如：1 2 3 5 6表示以1，2为前缀，后随项3、5或6的项集。最后，第三层的前缀

13、结构显示了事务t包含的所有的3-项集。如，以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树中。在支持度计数期间，包含在事务中的项集也散列到相应的桶中。这种方法不是将事务中的每个项集与所有的候选项集进行比较，而是将它与同一桶内候选项集进行匹配。,7.2,频繁项集产生,19,7.2.3,支持度计数,上图是一棵Hash树结构的例子。树的每个内部结点都使用Hash函数h(p)=p mod 3来确定应当沿着当前结点的哪个

14、分支向下。如，项1，4和7应当散列到相同的分支（即最左分支），因为除以3之后它们都具有相同的余数。所有的候选项集都存放在Hash树的叶结点中。图中显示的Hash树包含15个候选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-项集的叶结点至少访问一次。例如，在根结点

15、散列项1之后，散列事务的项2，3和5。项2和5散列到中间子女，而3散列到右子女，如图所示。继续该过程，直至到达Hash树的叶结点。,7.2,频繁项集产生,21,7.2.4,计算复杂度,Apriori算法的计算复杂度受如下因素影响：支持度阈值。支持度阈值影响频繁项集数量。项数（维数）。随着项数的增加，需要更多的空间来存储项的支持度计数。如频繁项集的数目也随着数据项数增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加。事务数。算法反复扫描数据集，运行时间随着事务数增加而增加。事务的平均宽度。对于密集数据集，事务的平均宽度可能很大，这将影响Apriori算法的复杂度。,7.2,频繁项

16、集产生,22,7.2.4,计算复杂度,7.2,频繁项集产生,23,因为由频繁项集的项组成的关联规则的支持度大于等于最小支持度阈值，所以规则产生过程就是在由频繁项集的项组成的所有关联规则中，找出所有置信度大于等于最小置信度阈值的强关联规则。计算关联规则的置信度并不需要再次扫描事务数据库。每个频繁k-项集能产生最多2k-2个关联规则。,7.3,规则产生,24,7.3.1,基本步骤,规则产生的基本步骤如下：（1）对于每个频繁项集l，产生l的所有非空子集；（2）对于l的每个非空子集s，如果则输出规则“”。其中min_conf是最小置信度阈值。,7.3,规则产生,25,7.3.1,基本步骤,例如，All

17、Electronics事务数据库，包含频繁项集X=I1，I2，I5，可由X产生6个候选关联规则，即X的非空子集：I1，I2，I1，I5，I2，I5，I1，I2和I5。结果关联规则如下，每个都列出置信度。如果最小置信度阈值为70，则只有2、3和最后一个规则可以输出，因为只有这些是强的。,7.3,规则产生,26,7.3.1,Apriori算法中规则的产生,Apriori算法使用一种逐层方法来产生关联规则，其中每层对应于规则后件中的项数。首先，提取规则后件只含一个项的所有高置信度规则，其次使用这些规则来产生新的候选规则。,7.3,规则产生,27,7.3.1,Apriori算法中规则的产生,例如，ac

18、db和abdc是两个高置信度的规则，则通过合并这两个规则的后件产生候选规则adbc。图中显示了由频繁项集产生关联规则的格结构。如果格中的任意结点具有低置信度，则可立即剪掉该结点生成的整个子图。假设规则bcda具有低置信度，则可以丢弃后件包含a的所有规则，包括cdab，bdac，bcad和dabc等。Apriori算法中规则产生过程与频繁项集产生过程类似，二者唯一的不同是，在规则产生时，不必再次扫描数据集计算候选规则的置信度，而使用频繁项集产生时计算的支持度计数来确定规则的置信度。,7.3,规则产生,28,实践中，由事务数据集产生的频繁项集的数量可能非常大。因此，从中识别出可以推导出其他所有的频

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

20、，d，e都是非频繁的；相反，项集a，c不是最大的，因为它的一个直接超集a，c，e是频繁的。最大频繁项集有效地提供了频繁项集的紧凑表示。最大频繁项集形成了可导出所有频繁项集的最小的项集的集合。,7.4,频繁项集的紧凑表示,31,7.4.2,闭频繁项集,闭项集：直接超集都不具有和它相同的支持度计数。闭频繁项集：支持度大于或等于最小支持度阈值的闭项集。,7.4,频繁项集的紧凑表示,32,7.4.2,闭频繁项集,闭频繁项集示例如上图。为了更好地解释每个项集的支持度计数，格中每个结点（项集）都标出了与它相关联的事务的ID。例如，由于结点b，c与事务ID 1，2和3相关联，因此它的支持度计数为3。从给定的

21、事务可以看出，包含b的每个事务也包含c，因此，由于b和b，c的支持度是相同的，所以b不是闭项集。同样，由于c出现在所有包含a和d的事务中，所以项集a，d不是闭的。另一方面，b，c是闭项集，因为它的支持度计数与它的任何超集都不同。,7.4,频繁项集的紧凑表示,33,Apriori算法通过使用先验原理对指数搜索空间进行剪枝，成功地处理了频繁项集产生的组合爆炸问题。虽然显著提高了性能，但该算法还是会导致不可低估的I/O开销，因为它需要多次扫描事务数据集。此外，对于稠密数据集，由于事务数据宽度的增加，Apriori算法的性能显著降低。为了克服这些局限性和提高Apriori算法的效率，已开发了一些替代方

22、法。,7.5,产生频繁项集的其它方法,34,7.5.1,项集格遍历,概念上，可以将频繁项集的搜索看作遍历项集格。算法使用的搜索策略指明了频繁项集产生过程中如何遍历格结构。根据频繁项集在格中的布局，某些搜索策略优于其他策略。一般到特殊与特殊到一般,7.5,产生频繁项集的其它方法,35,7.5.1,项集格遍历,Apriori算法使用了“一般到特殊”的搜索策略，合并两个频繁（k-1）-项集得到候选k-项集。使用这种策略效果最好的频繁项集的布局显示在上图（a）中，其中较黑的结点代表非频繁项集。相反，“特殊到一般”的搜索策略在发现更一般的频繁项集之前，先寻找更特殊的频繁项集。这种策略对于发现稠密事务中的

23、最大频繁项集是有用的。稠密事务中频繁项集的边界靠近格的底部，如上图（b）所示。可以使用先验原理剪掉最大频繁项集的所有子集。另一种策略是结合“一般到特殊”和“特殊到一般”的搜索策略，尽管这种双向搜索方法需要更多的空间存储候选项集，但是上图（c）所示的布局，该方法有助于加快确定频繁项集边界。,7.5,产生频繁项集的其它方法,36,7.5.1,项集格遍历,等价类 该方法是先将格划分为两个不相交的结点组（或等价类）。频繁项集产生算法依次在每个等价类内搜索频繁项集。,7.5,产生频繁项集的其它方法,37,7.5.1,项集格遍历,Apriori算法采用的逐层策略可以看作根据项集的大小划分格，即在处理较大项

24、集之前，首先找出所有的频繁1-项集。等价类也可以根据项集的前缀或后缀来定义。在这种情况下，两个项集属于同一个等价类，如果它们共享长度为k的相同前缀或后缀。在基于前缀的方法中，算法首先搜索以前缀a开始的频繁项集，然后是以前缀b等开始的频繁项集，然后中c，如此下去。基于前缀和基于后缀的等价类都可以使用上图中所示的类似于树的结构来演示。,7.5,产生频繁项集的其它方法,38,7.5.1,项集格遍历,宽度优先与深度优先 Apriori算法采用宽度优先的方法遍历格，如图（a）所示。它首先发现所有频繁1-项集，接下来是频繁2-项集，如此下去直到没有新的频繁项集产生为止。也可以以用深度优先的方式遍历项集格，

25、如图（b）所示。,7.5,产生频繁项集的其它方法,39,7.5.1,项集格遍历,比如说，算法可以从图中的结点a开始，计算其支持度计数并判断它是否频繁。如果是，算法渐增地扩展下层结点，即ab，abc，等等，直到到达一个非频繁结点，如abcd。然后，回溯到下一个分支，比如说abce，并且继续搜索。,7.5,产生频繁项集的其它方法,40,7.5.1,项集格遍历,通常，深度优先搜索方法用于发现最大频繁项集。比宽度优先更快地检测到频繁项集边界。一旦发现一个最大频繁项集，就可在它的子集上剪枝。如，上图中的结点bcde是最大频繁项集，则算法就不必访问以bd，be，c，d和e为根的子树，因为它们不可能包含任何

26、最大频繁项集。然而，如abc是最大频繁项集，则只有ac和bc这样的结点不是最大频繁项集，但以它们为根的子树还可能包含最大频繁项集。深度优先方法还允许使用不同的基于项集支持度的剪枝方法。如，假定项集 a，b，c和a，b具有相同的支持度，则可跳过以abd和abe为根的子树，不包含最大频繁项集。,7.5,产生频繁项集的其它方法,41,7.5.2,事务数据集的表示,表示购物篮事务的两种不同方法。左边的表示法称作水平数据布局，许多关联规则挖掘算法（包括Apriori）都采用这种表示法；右边的表示法是存储与每一个项相关联的事务标识符列表（TID列表），这种表示法称作垂直数据布局。候选项集的支持度通过取其子

27、项集TID列表的交得到。,7.5,产生频繁项集的其它方法,42,7.6,FP-growth算法,FP-growth（Frequent-Pattern growth，频繁模式增长）算法的基本思想是采用分治策略：首先，将代表频繁项集的数据库压缩到一棵FP树（Frequent-Pattern tree，频繁模式树），该树仍保留项集的关联信息。其次，将这种压缩后的数据库划分成一组条件数据库（一种特殊类型的投影数据库），每个数据库关联一个频繁项或“模式段”，并分别挖掘每个条件数据库。对于每个“模式片段”，只需要考察与它相关联数据集。随着被考察的模式的“增长”，可以显著地压缩被搜索的数据集的大小。,43,

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

29、个项I2，I1，I5，导致构造树的第一个分枝。该分枝具有3个结点，其中I2作为根的子女链接到根，I1链接到I2，I5链接到I1，如图所示。,7.6,FP-growth算法,45,7.6.1,FP树构造,第二个事务T200按L的次序包含I2和I4，它导致一个分枝，其中I2链接到根，I4链接到I2。然而，该分枝应与T100已存在的路径共享前缀。因此将结点I2的计数增加1，并创建一个新结点（I4:1），它作为（I2:2）子女链接，如图所示。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个结点的计数增加1，为随在前缀之后的项创建结点并链接。,7.6,FP-growth算法,46,7.6.1,FP

30、树构造,为了方便树的遍历，创建一个项头表，使每项通过一个结点链指向它在树中的位置。扫描所有的事务后得到的树如图所示，带有相关的结点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP树的问题。,7.6,FP-growth算法,47,7.6.2,频繁项集产生,FP树的挖掘过程为：由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树中与该后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP树，并递归地在该树上进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。,7.6,FP-growth算法,48,7.6.2,频繁项集产生,该FP树的挖掘过

31、程总结如上表所示。首先考虑I5，它是L中的最后一项，而不是第一项。I5出现在FP树的两个分枝中（I5的出现容易通过沿它的结点链找到）。这些路径由分枝和形成。因此，考虑以I5为后缀，它的两个对应前缀路径是和，形成I5的条件模式基。使用这些条件模式基作为事务数据库，构造I5的条件FP树，它只包含单个路径；不包含I3，因为它的支持度1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2 I5:2，I1 I5:2，I2 I1 I5:2。对于I4，它的两个前缀形成条件模式基(I2 I1:1）,（I2:1)，产生一个单结点的条件FP树，并导出一个频繁模式I2 I4:2。,7.6,FP-growth

32、算法,49,7.6.2,频繁项集产生,类似于以上分析，I3的条件模式基是(I2 I1:2）,（I2:2）,（I1:2)。它的条件FP树有两个分枝和，如图所示，它产生模式集：I2 I3:4，I1 I3:4，I2 I1 I3:2。最后，I1的条件模式基是(I2:4)，它的FP树只包含一个结点，只产生一个频繁模式I2 I1:4。,7.6,FP-growth算法,50,7.6.2,频繁项集产生,7.6,FP-growth算法,51,7.6.2,频繁项集产生,优点：FP-growth算法仅仅遍历了2次数据库，第一次是为了产生L1，第二次是为了对项目排序。由于不用多次扫描数据库，因而大大节省了扫描数据库的

33、时间；选用了分治策略，把挖掘的长频繁模式转换成递归地挖掘短模式的问题，再与后缀相连；挖掘长频繁模式与短的频繁模式时，有效性与可伸缩性都是该算法的特点，所用挖掘时间会比Apriori算法的挖掘时间少得多。,7.6,FP-growth算法,52,7.6.2,频繁项集产生,缺点：建立FP树时，会占用大量的内存空间。如果数据库的规模很大，要建立的FP树也会很巨大；在递归构建FP树时，每生成一个频繁模式就会出现一个条件树。当生成与释放海量的条件树时，该算法将占用很多的运算时间与计算机空间。,7.6,FP-growth算法,53,7.7,关联评估,在实际情况中，商业数据库的数据量和维数都非常大，运用关联分

34、析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的。第一组标准可通过统计论据建立。涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。第二组标准可通过主观论据建立，即模式被主观地认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。,54,7.7.1,兴趣度客观度量,客观度量常常基于列联表中列出的频度计数来计算。一对二元变量A和B的列联表如表所示。使用记号 A（B）表示A（B）不在事务中出现。在这个22的表中，每个fij都代表一个频度计数。如，f11表示A和B同时出现

35、在一个事务中的次数，f01表示包含B但不包含A的事务的个数。行和f1+表示A的支持度计数，而列和f+1表示B的支持度计数。,7.7,关联评估,55,7.7.1,兴趣度客观度量,支持度置信度框架的局限性。现有关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。支持度的缺点在于许多潜在的有意义的模式由于包含支持度小的项而被删去。置信度的缺点更微妙，最适合用下面的例子进行说明。假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总在表中。,7.7,关联评估,56,7.7.1,兴趣度客观度量,7.7,关联评估,57,7.7.1,兴趣度客观度量,兴趣因子。茶和咖啡的例子

36、表明，由于置信度度量忽略了规则后件中出现的项集的支持度，高置信度的规则有时存在误导。解决这个问题的一种方法是使用称作提升度（lift）的度量：它计算规则置信度和规则后件中项集的支持度之间的比率。对于二元变量，提升度等价于兴趣因子的客观度量：对于相互独立的两个变量，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%的文档中，但

37、它们的兴趣因子接近1，表明二者是相互独立的；另一方面，r,s 的兴趣因子比p,q 高，尽管r和s很少同时出现在同一个文档中。这种情况下，置信度可能是更好的选择，因为置信度表明p和q之间的关联（94.6%）远远强于r和s之间的关联（28.6%）。,7.7,关联评估,59,7.7.1,兴趣度客观度量,7.7,关联评估,60,7.7.1,兴趣度客观度量,7.7,关联评估,61,7.7.1,兴趣度客观度量,IS度量。IS是另一种度量，用于处理非对称二元变量。定义如下：如，前面表中显示的词对p,q和r,s的IS值分别是0.946和0.286。IS度量暗示p,q之间的关联强于r,s，这与期望的文档中词的关

38、联一致。可以证明IS数学上等价于二元变量的余弦变量：IS度量也可以表示为从一对二元变量中提取出的关联规则的置信度的几何平均值：,7.7,关联评估,62,7.7.1,兴趣度客观度量,IS度量的局限性。一对相互独立的项集A和B的IS值是：因为IS值取决于 S(A)和 S(B)，所以IS存在与置信度度量类似的问题即使是不相关或负相关的模式，度量值也可能相当大。例如，尽管表中所显示的项p和q之间的IS值相当大（0.889），当项统计独立时它仍小于期望值（IS indep=0.9）。,7.7,关联评估,63,7.7.1,兴趣度客观度量,7.7,关联评估,64,7.7.1,兴趣度客观度量,客观度量的一致性

39、。给定各种各样的可用度量后，产生的一个合理问题是：当这些度量应用到一组关联模式时是否会产生类似的有序结果。如果这些度量是一致的，那么就可以选择它们中的任意一个作为评估度量。否则的话，为了确定哪个度量更适合分析某个特定类型的模式，了解这些度量之间的不同点是非常重要的。,7.7,关联评估,65,7.7.1,兴趣度客观度量,7.7,关联评估,66,7.7.1,兴趣度客观度量,缩放性。客观度量M在行/列缩放操作下是不变的，如M（T）=M（T），其中T是频度计数为f11；f10；f01；f00的列联表。T是频度计数为k1k3f11；k2k3f10；k1k4f01；k2k4f00的列联表，而k1，k2，k

40、3，k4是正常量。,7.7,关联评估,67,7.7.2,多个二元变量的度量,使用多维列联表，可以扩展到多个变量。a，b和c的3维列联表如表所示。表中每个表目fijk都表示包含项a，b和c的某种组合的事务数。比如，f101表示包含a和c但不包含b的事务数。另一方面，边缘频率f1+1表示包含项a和c而不管是否包含项b的事务数。,7.7,关联评估,68,7.7.3,倾斜支持度分布的影响,许多关联分析算法的性能受输入数据的性质的影响。例如，Apriori算法的计算复杂度依赖于数据中的项数和事务的平均长度等性质。具有倾斜支持度分布的数据集，其中大多数项具有较低或中等频率，但是少数项具有很高的频率。,7.

41、7,关联评估,69,7.7.3,倾斜支持度分布的影响,上图显示了一个呈现这种分布的实际数据集的例子。该数据取自PUMS人口普查数据。它包含49046条记录和2113个非对称的二元变量。尽管数据集中超过80的项的支持度小于1，但是少数项的支持度大于90。为了解释倾斜支持度分布对频繁项集挖掘的影响，将所有的项按照支持度分为3组，G1，G2和G3。表中显示了每一组中包含项的数量。,7.7,关联评估,70,7.7.3,倾斜支持度分布的影响,选择合适的支持度阈值较难：如果阈值太高，则可能遗漏涉及G1中较低支持度项的模式。如：在购物篮数据中，顾客很少买的昂贵商品：珠宝等。如果阈值太低，已有的关联分析算法所

42、需的计算量和内存需求都将显著增加；提取出的关联模式的数量大幅增加；可能提取出大量的高频率项（如“牛奶”）与低频率项（如“鱼子酱”）相关联的虚假模式，这样的模式称为交叉支持（cross-support）模式。,7.7,关联评估,71,7.7.3,倾斜支持度分布的影响,交叉支持模式是一个项集X=i1,i2,ik，它的支持度比率：这一比率小于用户指定的阈值hc。假设牛奶的支持度是70%，糖的支持度是10%，鱼子酱的支持度是0.04%。给定hc=0.01，频繁项集牛奶，糖，鱼子酱是一个交叉支持模式，因为它的支持度比率为：,7.7,关联评估,72,7.7.3,倾斜支持度分布的影响,现有的度量（如支持度和

43、置信度），都不足以消除交叉支持模式。如图所示，当hc=0.3时，项集p,q、p,r和p,q,r是交叉支持模式，因为它们的支持度比率为0.2，小于阈值0.3。虽然可以采用较高的支持度阈值（如20）来消除交叉支持模式，但是，这样却损失了其他有趣的模式，如强关联项集q,r，它的支持度为16.7。,7.7,关联评估,73,7.7.3,倾斜支持度分布的影响,7.7,关联评估,74,7.7.3,倾斜支持度分布的影响,通过确保模式的h置信度值超过hc就可以消除交叉支持模式。使用h置信度的好处不仅是消除交叉支持模式，这种度量也是反单调的，即：从而可以将它直接并入挖掘算法。此外，h置信度能够确保项集中的项之间是强关联的，即超团模式（hyperclique pattern）。,7.7,关联评估,75,