数据挖掘导论第7章精品版ppt课件

1、关联分析: 高级概念,第7章 关联分析: 高级概念,关联分析处理事务数据,Rules Discovered: Diaper - Beer,处理分类属性,我们可能发现关于因特网用户特征的有趣信息: 网上购物=是 关注隐私=是,许多应用包含对称二元属性和标称属性。表7-1显示的因特网调查数据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上购物和关注隐私；还包括标称属性，如文化程度和州,处理分类属性,为了提取这样的模式，我们需要将标称属性和对称二元属性转换成“项”，使得已有的关联规则挖掘算法可以使用。 这种类型的变化可以通过为每个不同的属性-值对创建一个新的项来实现。 例如: 标称属性文化程度

2、可以用三个二元项取代 文化程度=大学 文化程度=研究生 文化程度=高中 类似的，对称二元属性性别可以转换成一对二元项：性别=男、性别=女,处理分类属性,将关联分析用于二元化后的数据时，需要考虑如下问题。 (1)有些属性值可能不够频繁，不能成为频繁模式的一部分。如：州名。 解决办法：将相关的属性值分组，形成少数类别。例如，每个州名都可以用对应的地理区域取代。例如：分别用中西部、太平洋西北部、西南部和东海岸取代,处理分类属性,将关联分析用于二元化后的数据时，需要考虑如下问题。 (2)某些属性值的频率可能比其他属性高很多。如：假定85%的被调查人都有家庭计算机，如果为每个频繁出现在数据中的属性值创建

3、一个二元项，我们可能产生许多冗余模式。 家庭计算机=是，网上购物=是 关注隐私=是 解决办法：使用处理具有宽支持度的极差数据集的技术,处理分类属性,将关联分析用于二元化后的数据时，需要考虑如下问题。 (3)计算时间可能增加，特别是当新创建的项变成频繁项时。因为会产生更多的候选项集。 解决办法：避免产生包含多个来自同一个属性的项的候选项集。例如：不必产生诸如州=X，州=Y，的候选项集，因为该项集支持度为零,处理连续属性,因特网调查数据可能还包含连续属性，如表7-3所示。 挖掘连续属性可能揭示数据的内在联系，如“年收入超过120k的用户属于45-60年龄组”或“拥有超过3个email帐号并且每周上

4、网超过15小时的用户通常关注个人隐私”: 包含连续属性的关联规则通常称作量化关联规则（quantiative association rule）。 对连续数据进行关联分析的方法: 基于离散化的方法 非离散化方法 基于统计学的方法,基于离散化的方法,离散化是处理连续属性最常用的方法。这种方法将连续属性的邻近值分组，形成有限个区间。例如：年龄属性可以划分为如下区间： 12,16),16,20),20,24),56,60) 离散化技术：等宽、等频、聚类 表7-4显示了离散化和二元化后的因特网调查数据,属性离散化的一个关键在于划分每个属性的区间个数和宽度。然而，确定正确的区间是困难的,如果支持度阈值=

5、5%，置信度阈值=65%。我们可以从表中推出年龄和网上聊天隐含强规则： 16,24) 网上聊天=是（s=8.8%，c=81.5%） 44,60) 网上聊天=否（s=16.8%，c=70%） 区间宽度对关联分析结果的影响。 （1）如果区间太宽，则可能因为缺乏置信度而失去某些规则 例如：当区间宽度为24岁时，上面的两个规则变为 16,36) 网上聊天=是（s=30%，57.7%） 36,60) 网上聊天=否（s=28%，58.3,区间宽度对关联分析结果的影响。 （2）如果区间太窄，则可能因为缺乏支持度而失去某些规则 例如：当区间宽度为4岁时，上面的两个规则变为 16,20) 网上聊天=是（s=4.

6、4%，84.6%） 20,24) 网上聊天=是（s=4.4%，78.6%） （3）当区间宽度为8岁时，上面的两个规则变为 44,52) 网上聊天=否（s=8.4%，70%） 52,60) 网上聊天=否（s=8.4%，70%） 12,20) 网上聊天=是（s=9.2%，60.5%） 20,28) 网上聊天=是（s=9.2%，60.0,非离散化方法,有一些应用，分析者更感兴趣的是发现连续属性之间的关系。例如，找出表7-6所示文本文档中词的关联,在文本挖掘中，分析者更感兴趣的是发现词之间的关联（例如：数据和挖掘）。而不是词频区间（例如,数据：1,4，挖掘：2,3）之间的关联。 一种方法是将数据变换成

7、0/1矩阵；其中，如果规范化词频超过某个阈值t，则值为1，否则为0。 该方法缺点是阈值难确定,另一种方法是采用min-apriori方法。 S(word1, word2)=min(0.3, 0.6)+min(0.1 , 0.2)+ min(0.4,0.2)+min(0.2, 0) =0.6 Min-apriori中支持度s随着词的规范化频率增加而增大。随包含该词的文档个数增加而单调递增,处理概念分层,概念分层是定义在一个特定的域中的各种实体或概念的多层组织。 概念分层可以用有向无环图表示,概念分层主要优点 （1）位于层次结构较下层的项（如：AC适配器）可能没有足够的支持度，但是，作为概念分层结

8、构中它们的父母结点（如：便携机配件）具有较高支持度。 （2）在较低层发现的规则倾向于过于特殊，可能不如较高层的规则令人感兴趣。（如：脱脂牛奶普通面包，脱脂牛奶白面包，等过于特殊,实现概念分层的方法 每个事务t用它的扩展事务t取代，其中，t包含t中所有项和它们的对应祖先。如：事务DVD，普通面包可以扩展为DVD，普通面包，家电，电子产品，面包，食品 然后对扩展的数据库使用如Apriori等已有的算法来发现跨越多个概念层的规则,概念分层主要缺点 （1）处于较高层的项比处于较低层的项趋向于具有较高的支持度计数。 （2）概念分层的引入增加了关联分析的计算时间。 （3）概念分层的引入可能产生冗余规则。规

9、则X Y是冗余的，如果存在一个更一般的规则X Y，其中X是X的祖先，Y是Y的祖先，并且两个规则具有非常相似的置信度。例如：面包 牛奶，白面包 脱脂牛奶,序列模式,购物篮数据常常包含关于商品何时被顾客购买的时间信息。可以使用这种信息，将顾客在一段时间内的购物拼接成事务序列。 然而，迄今为止所讨论的关联模式概念都只强调同时出现关系，而忽略数据中的序列信息。 对于识别动态系统的重现特征，或预测特定事件的未来发生，序列信息可能是非常有价值的,序列模式,将与对象A有关的所有事件按时间增序排列，就得到A的一个序列（sequence,Sequence Database,一般地，序列是元素（element）的

10、有序列表，可以记作s=, 其中每个ej是一个或多个事件的集族，即ej=i1，i2，ik,Sequence,E1E2,E1E3,E2,E3E4,E2,Element (Transaction,Event (Item,序列数据的例子,子序列（ Subsequence,序列t是另一个序列s的子序列（subsequence），如果t中每个有序元素都是s中一个有序元素的子集,序列模式发现（Sequential Pattern Mining,设D是包含一个或多个数据序列的数据集: 序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于或等于用户指定的阈值minsup，则称s是一个序列模式（

11、或频繁序列）。 定义7.1 序列模式发现: 给定序列数据库D和用户指定的最小支持度阈值minsup，序列模式发现的任务是找出支持度大于或等于minsup的所有序列,例子,Minsup = 50% Examples of Frequent Subsequences: s=60% s=60% s=80% s=80% s=80% s=60% s=60% s=60% s=60,提取序列模式：蛮力方法,给定n个事件的集族: i1, i2, i3, , in 候选 1-序列: , , , , 候选 2-序列: , , , , , , , 候选 3-序列: , , , , , , , , , , ,候选序列

12、的个数比候选项集的个数大得多。产生更多候选的原因有下面两个 一个项在项集中最多出现一次，但一个事件可以在序列中出现多次。给定两个项i1和i2，只能产生一个候选2-项集i1，i2，但却可以产生许多候选2-序列，如, , , 。 次序在序列中是重要的，但在项集中不重要。例如，1,2和2,1表示同一个项集，而和对应于不同的序列，因此必须分别产生。 先验原理对序列数据成立。 包含特定k-序列的任何数据序列必然包含该k-序列的所有(k-1)-序列,序列模式发现的类Apriori算法,候选产生,一对频繁(k-1)-序列合并，产生候选k-序列。 为了避免重复产生候选，传统的Apriori算法仅当前k-1项相

13、同时才合并一对频繁k-项集。类似的方法可以用于序列。 例子 通过合并和得到 。由于事件3和事件4属于第二个序列的不同元素，它们在合并后序列中也属于不同的元素。 通过合并和得到 。由于事件3和事件4属于第二个序列的相同元素，4被合并到第一个序列的最后一个元素中,候选剪枝 一个候选k-序列被剪枝，如果它的(k-1)-序列最少有一个是非频繁的。 例如，假设是一个候选4-序列。我们需要检查和是否是频繁3-序列。由于它们都不是频繁的，因此可以删除候选。 支持度计数 在支持度计数期间，算法将枚举属于一个特定数据序列的所有候选k-序列。 计数之后，算法将识别出频繁k-序列，并可以丢弃其支持度计数小于最小支持

14、度阈值minsup的候选,图7-6,时限约束,模式的事件和元素都施加时限约束。 例子：学生A： 学生B： 感兴趣的模式是，意思是说注册数据挖掘课程的学生必须先选修数据库系统和统计学方面的课程。 显然，该模式被这两个学生支持，尽管他们都没有同时选修统计学和数据库系统。 相比之下，一个10年之前选修了统计学课程的学生不能认为支持该模式，因为这些课程的时间间隔太长了,图7-7解释了可以施加在模式上的某些时限约束,最大跨度约束,最大跨度约束指定整个序列中所允许的事件的最晚和最早发生时间的最大时间差。 假定最大时间跨度maxspan=3，下面的表包含了给定的数据序列支持和不支持的序列模式,一般，maxs

15、pan越长，在数据序列中 检测到模式的可能性就越大。然而，较长的maxspan也可能捕获不真实的模式可能涉及陈旧事件。 最大跨度约束影响序列模式发现算法的支持度计数。施加最大时间跨度约束之后，有些数据序列就不再支持候选模式,最小间隔和最大间隔约束,时限约束也可以通过限制序列中两个相继元素之间的时间差来指定。 如果最大时间差（maxgap）是一周，则元素中的事件必须在前一个元素的事件出现后的一周之内出现。 如果最小时间差（mingap）是0，则元素中的事件必须在前一个元素的事件出现之后出现,假定maxgap=3，mingap=1，下表给出了模式通过或未通过最大间隔和最小间隔约束的例子,与最大跨度

16、一样，这些约束也影响序列模式发现算法的支持度计数，因为当最小间隔和最大间隔约束存在时，有些数据序列就不再支持候选模式。 使用最大间隔约束可能违反先验原理。 为了解释这一点，考虑图7-5中的数据集。如果没有最小间隔或最大间隔约束，和的支持度都是60%。然而，如果mingap=0，maxgap=1，则的支持度下降至40%，而的支持度仍然是60%。这与先验原理相违背,例子,Minsup = 50% Examples of Frequent Subsequences: s=60% s=60% s=80% s=80% s=80% s=60% s=60% s=60% s=60,定义7.2 邻接子序列 序列

17、s是序列w=的邻接子序列(contiguous subsequence)，如果下列条件之一成立： （1）s是从e1或ek中删除一个事件后由w得到。 （2）s是从至少包含两个事件的任意eiw中删除一个 事件后由w得到。 （3）s是t的邻接子序列，而t是w的邻接子序列,定义7.3 修订的先验原理 如果一个k-序列是频繁的，则它的所有邻接(k-1)-子序列也一定是频繁的。 在候选剪枝阶段，并非所有的k-序列都需要检查，因为它们中的一些可能违反最大间隔约束。例如，如果maxgap=1，则不必检查候选的子序列是否是频繁的，因为元素2,3和5之间的时间差大于一个时间单位。 我们只需要考察的邻接子序列，包括

18、，和,窗口大小约束,最后，元素sj中的事件不必同时出现。可以定义一个窗口大小阈值（ws）来指定序列模式的任意元素中事件最晚和最早出现之间的最大允许时间差。窗口大小为0表明模式同一元素中的所有事件必须同时出现。 下面的例子使用ws=2，mingap=0，maxgap=3，maxspan,子图模式,关联分析方法应用到远比项集和序列更复杂实体。例子包括化学化合物、3-D蛋白质结构、网络拓扑和树结构的XML文档。这些实体可以用图形表示建模。 在这种类型的数据上进行数据挖掘的任务是，在图的集合中发现一组公共子结构。这样的任务称作频繁子图挖掘,图与子图,定义7.5 支持度 给定一个图的集族,子图g的支持度

19、定义为包含它的所有图所占的百分比，即 例7.2 考虑5个图G1到G5，如图7-10所示。右上角的图g1是G1，G3，G4，G5的子图，因此s(g1)=4/5=80%。类似地，我们由s(g2)=60%，因为g2是G1、G2和G3的子图；而s(g3)=40%，因为g3是G1和G3的子图,频繁子图挖掘,定义7.6 频繁子图挖掘 给定图的集合和支持度阈值minsup，频繁子图挖掘的目标是找出所有使得s(g)=minsup的子图g。 本章的讨论主要关注无向连通图（undirected，connected graph）。 挖掘频繁子图是一项计算量很大的任务，因为搜索空间是指数的。为了解释这项任务的复杂性，

20、考虑一个包含d个实体的数据集。在频繁项集挖掘中，每个实体是一个项，待考察的搜索空间是2d，这是可能产生的候选项集的个数,在频繁子图挖掘中，每个实体是一个顶点，并且最多可以有d-1条到其他顶点的边。假定顶点的标号是唯一的，则子图的总数是 其中， 是选择i个顶点形成子图的方法数，而 是子图的顶点之间边的最大值。表7-8对不同的d比较了项集和子图的个数,挖掘频繁子图的一种蛮力方法是，产生所有的连通子图作为候选，并计算它们各自的支持度。 考虑图7-11a中显示的图，假定顶点标号选自集合a，b，而边的标号选自集合p，q，则具有一个到三个顶点的连通子图列在图7-11b中。 候选子图的个数比传统的关联规则挖

21、掘中的候选项集的个数大得多，其原因： 一个项在一个项集中至多出现一次，而一个顶点标号可能在一个图中出现多次。 相同的顶点标号对可以有多种边标号选择,把事务转化为图,把图转化为事务,频繁子图挖掘算法的一般结构,一种挖掘频繁子图的类Apriori算法由以下步骤组成 候选产生：合并频繁(k-1)-子图对，得到候选k-子图。 候选剪枝：丢弃包含非频繁的(k-1)-子图的所有候选k-子图。 支持度计数：统计中包含每个候选的图的个数。 候选删除：丢弃支持度小于minsup的所有候选子图,候选产生,在候选产生阶段，一对频繁(k-1)-子图合并成一个候选k-子图。 如何定义子图的大小k？ 在图7-11显示的例

22、子中，k是图中的顶点个数。通过添加一个顶点，迭代的扩展子图的方法称作顶点增长（vertex growing）。 K也可以是图中边的个数。添加一条边到已有的子图中来扩展子图的方法称作边增长（edge growing）。 为了避免产生重复的候选，可以对合并施加附加的条件：两个(k-1)-子图必须共享一个共同的(k-2)-子图。共同的(k-2)-子图称作核(core,通过顶点增长产生候选,用邻接矩阵表示图。 顶点增长方法可以看成合并一对(k-1) (k-1)的邻接矩阵，产生kk邻接矩阵的过程。 通过顶点增长合并子图的过程： 邻接矩阵M1与另一个邻接矩阵M2合并，如果删除M1和M2的最后一行和最后一列

23、得到的子矩阵相同。 结果矩阵是M1，添加上M2的最后一行和最后一列。 新矩阵的其余项或者为0，或者用连接顶点对的合法的边标号替换,Vertex Growing,a,r,a,r,结果图包含的边比原来的图多一条或两条。 (d,e)可以相连或不相连。 由于该边的标号未知，我们需要对(d,e)考虑所有可能的边标号，从而大大增加了候选子图的个数,通过边增长产生候选,在候选产生期间，边增长将一个新的边插入一个已经存在的频繁子图中。 与顶点增长不同，结果子图的顶点个数不一定增加。 通过边增长产生候选子图的过程概括如下： 一个频繁子图g1与另一个频繁子图g2合并，仅当从g1删除一条边得到的子图与从g2删除一条

24、边得到的子图拓扑等价。合并后，结果子图是g1，添加g2的那条额外的边,a,顶点拓扑等价（topologically equivalent）：加入一条新边到v1与加入该边到v2产生的图相同，则v1和v2两顶点拓扑等价,顶点拓扑等价的概念能够帮助我们理解，在边增长时为什么能够产生多个候选子图。 如果a和c拓扑等价，我们将它们记作a=c。对于核外边的点，如果它们的标号相同，我们将它们记作b=d,当与一对(k-1)-子图相关联的核有多个时，还可能产生多个候选子图,候选剪枝,产生候选k-子图后，需要剪去(k-1)-子图非频繁的候选。 候选剪枝可以通过如下步骤实现： 相继从k-子图删除一条边，并检查对应的

25、(k-1)-子图是否连通且频繁。 如果不是，则该候选k-子图可以丢弃。 为了检查(k-1)-子图是否频繁，需要将它与其他频繁(k-1)-子图匹配。判定两个图是否拓扑等价称为图同构（graph isomorphism）问题。 为了解释图同构问题的困难性，考虑图7-19中的两个图,同构图,处理图同构,处理图同构问题的标准方法是，将每一个图都映射到一个唯一的串表达式，称作代码（code）或规范标号（canonical label）。 规范标号具有如下性质：如果两个图是同构的，则它们的代号一定相同。这个性质使得我们可以通过比较图的规范标号来检查图同构。 构造图的规范标号的第一步是找出图的邻接矩阵表示。

26、一个图可以有多种邻接矩阵表示，因为存在多种确定顶点次序的方法,数学上讲，每个排列都对应于初始邻接矩阵与一个对应的排列矩阵的乘积，如下面的例子所示。 例子：考虑下面的矩阵： 其中，P13是通过交换单位矩阵的第一行和第三行得到的。为了交换M的第一和第三行（和列），排列矩阵与M相乘,M右乘P13交换M的第一列和第三列，而M左乘P13交换M的第一行和第三行。 第二步是确定每个邻接矩阵的串表示。由于邻接矩阵是对称的，因此只需要根据矩阵的上三角部分构造串表示就足够了。 在图7-21所示的例子中，代码是通过逐列连接矩阵的上三角元素得到的。 最后一步是比较图的所有串表达式，并选出具有最小（最大）字典次序值的串

27、,支持度计数,支持度计数一般是开销很大的操作，因为对于每个G，必须确定包含在G中的所有候选子图。 加快该操作的一种方法是，维护一个与每个频繁(k-1)-子图相关联的图ID表。一旦一个新的候选k-子图通过合并一对频繁(k-1)-子图而产生，就对它们的对应图ID表求交集。最后，子图同构检查就在表中的图上进行，确定它们是否包含特定的子图,非频繁模式,迄今为止，关联分析都基于这样的前提：项在事务中出现比不出现更重要。 因此，数据库中很少出现的模式不是令人感兴趣的，并使用支持度度量将其删除。这种模式称为非频繁模式。 定义7.7 非频繁模式 非频繁模式是一个项集或规则，其支持度小于阈值minsup,尽管绝

28、大部分非频繁模式都是让人不感兴趣的，但是其中的一些可能对于分析是有用的，特别是涉及到数据中的负相关性。 例如：DVD和VCR一起销售的情况很少，因为购买DVD的人多半不会购买VCR，反之亦然。 这种负相关模式有助于识别竞争项（competing item）。 竞争项的例子包括茶与咖啡、黄油与人造黄油、普通与节食苏打、台式机与便携式计算机,某些非频繁模式也可能暗示数据中出现了某些有趣的罕见事件或例外情况。 例如：如果火灾=yes是频繁的，但火灾=yes，报警=on是非频繁的。而后者是一个有趣的非频繁模式，因为它可能指出警报系统的故障。 为了检测这种不寻常情况，必须确定模式的期望支持度，使得如果一

29、个模式的支持度明显低于期望支持度，则可以声明它是一个有趣的非频繁模式,负模式,设I=i1,i2,id是项的集合。负项ik表示项ik不在给定的事务中出现。例如，如果事务中不包含咖啡，则咖啡是一个值为1的负项。 定义 7.8 负项集 负项集X是一个具有如下性质的项集：（1）X=AB，其中A是正项的集合，而B是负项的集合，|B|1; （2）s(X) minsup。 定义 7.9 负关联规则 负关联规则是一个具有如下性质的关联规则：（1）规则是从一个负项集提取的，（2）规则的支持度大于或等于minsup，（3）规则的置信度大于或等于minconf 本章中，负项集和负关联规则统称负模式,负相关模式,定义

30、7.10 负相关项集 项集X=x1,x2,xk是负相关的，如果 定义7.11 负相关关联规则 关联规则X Y是负相关的，如果s(XY)s(X)s(Y)，其中，X和Y是不相交的项集，即X Y=。 负相关的完全条件可以表述如下,负相关条件也可以用正项集和负项集的支持度表示。设 和 分别表示X和Y的对应负项集，由于 负相关条件可以表述如下： 负相关项集和负相关关联规则统称负相关模式（negatively correlated pattern,非频繁模式、负模式和负相关模式比较,非频繁模式、负模式和负相关模式是三个密切相关的概念。 尽管非频繁模式和负相关模式只涉及包含正项的项集或模式，而负模式涉及包含

31、正项和负项的项集或模式，但是这三个概念之间存在一定的共性，如图7-22所示,首先，许多非频繁模式有对应的负模式。 如果x y是非频繁的，则除非minsup太高，否则它很可能有对应的负项集。 例如：假定minsup0.25，如果x y是非频繁的，则表中的其它几种组合至少有一种是频繁的,挖掘有趣的非频繁模式的技术,原则上讲，非频繁项集是未被标准的频繁项集产生算法（如Apriori和FP增长）提取的所有项集。这些项集对应于图7-23所示的频繁项集边界之下的那些项集,由于非频繁模式的数量可能是指数级的，特别是对于稀疏的、高维的数据。 因此，为挖掘非频繁模式而开发的技术着力于发现有趣的非频繁模式。 例如：负相关模式,基于挖掘负模式的技术,一种方法是将每个项看作对称的二元变量。通过用负项增广，将事务数据二元化。然后使用Apriori算法等，可以导出所有的负项集,仅当只有少量变量被视为对称的二元变量时，该方法才是可行的。如果每个项都必须视为对称的二元变量，则可能导致计算复杂度增加。 (1)当每个项都用对应的负项增广时，项的个数就加倍。待探测的项集格比2d大得多。 (2)当增加进负项后，基于支持度的剪枝不再有效。对于每个变量x，x或 的支持度大于等于50%.因此，即使支持度阈值达到50%，仍有一半的项是频繁的。 (3)当增加进负项后，每个事务的宽度