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

1、关联分析关联分析: 高级概念高级概念第第7章章关联分析关联分析: 高级概念高级概念关联分析处置事务数据关联分析处置事务数据Rules Discovered: Diaper - Beer处置分类属性处置分类属性我们能够发现关于因特网用户特征的有趣信息我们能够发现关于因特网用户特征的有趣信息: 网上购物网上购物=是是 关注隐私关注隐私=是是许多运用包含对称二元属性和标称属性。表许多运用包含对称二元属性和标称属性。表7-1显示的因特网调查显示的因特网调查数据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上数据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上购物和关注隐私；还包括标称属性，

2、如文化程度和州。购物和关注隐私；还包括标称属性，如文化程度和州。处置分类属性处置分类属性l为了提取这样的方式，我们需求将标称属性和对称二元属性转换成“项，使得已有的关联规那么发掘算法可以运用。l这种类型的变化可以经过为每个不同的属性-值对创建一个新的项来实现。l例如: 标称属性文化程度可以用三个二元项取代l 文化程度=大学l 文化程度=研讨生l 文化程度=高中l类似的，对称二元属性性别可以转换成一对二元项：性别=男、性别=女。处置分类属性处置分类属性l将关联分析用于二元化后的数据时，需求思索如下问题。l(1)有些属性值能够不够频繁，不能成为频繁方式的一部分。如：州名。l处理方法：将相关的属性值

3、分组，构成少数类别。例如，每个州名都可以用对应的地理区域取代。例如：分别用中西部、太平洋西北部、西南部和东海岸取代。处置分类属性处置分类属性l将关联分析用于二元化后的数据时，需求思索如下问题。l(2)某些属性值的频率能够比其他属性高很多。如：假定85%的被调查人都有家庭计算机，假设为每个频繁出如今数据中的属性值创建一个二元项，我们能够产生许多冗余方式。l 家庭计算机=是，网上购物=是 关注隐私=是l处理方法：运用途置具有宽支持度的极差数据集的技术。处置分类属性处置分类属性l将关联分析用于二元化后的数据时，需求思索如下问题。l(3)计算时间能够添加，特别是当新创建的项变成频繁项时。由于会产生更多

4、的候选项集。l处理方法：防止产生包含多个来自同一个属性的项的候选项集。例如：不用产生诸如州=X，州=Y，的候选项集，由于该项集支持度为零。处置延续属性处置延续属性l因特网调查数据能够还包含延续属性，如表7-3所示。l发掘延续属性能够提示数据的内在联络，如“年收入超越120k的用户属于45-60年龄组或“拥有超越3个email帐号并且每周上网超越15小时的用户通常关注个人隐私:l包含延续属性的关联规那么通常称作量化关联规那么quantiative association rule。l对延续数据进展关联分析的方法:l基于离散化的方法l非离散化方法l基于统计学的方法基于离散化的方法基于离散化的方法l

5、离散化是处置延续属性最常用的方法。这种方法将延续属性的临近值分组，构成有限个区间。例如：年龄属性可以划分为如下区间：l 12,16),16,20),20,24),56,60)l离散化技术：等宽、等频、聚类l表7-4显示了离散化和二元化后的因特网调查数据。l属性离散化的一个关键在于划分每个属性的区间个数和宽度。然而，确定正确的区间是困难的。l假设支持度阈值=5%，置信度阈值=65%。我们可以从表中推出年龄和网上聊天隐含强规那么：l 16,24) 网上聊天=是s=8.8%，c=81.5% 44,60) 网上聊天=否s=16.8%，c=70%l区间宽度对关联分析结果的影响。l1假设区间太宽，那么能够

6、由于缺乏置信度而失去某些规那么l例如：当区间宽度为24岁时，上面的两个规那么变为l 16,36) 网上聊天=是s=30%，57.7%l 36,60) 网上聊天=否s=28%，58.3%l区间宽度对关联分析结果的影响。l2假设区间太窄，那么能够由于缺乏支持度而失去某些规那么l例如：当区间宽度为4岁时，上面的两个规那么变为l 16,20) 网上聊天=是s=4.4%，84.6%l 20,24) 网上聊天=是s=4.4%，78.6%l3当区间宽度为8岁时，上面的两个规那么变为l 44,52) 网上聊天=否s=8.4%，70%l 52,60) 网上聊天=否s=8.4%，70%l 12,20) 网上聊天=

7、是s=9.2%，60.5%l 20,28) 网上聊天=是s=9.2%，60.0%非离散化方法非离散化方法l有一些运用，分析者更感兴趣的是发现延续属性之间的关系。例如，找出表7-6所示文本文档中词的关联。l在文本发掘中，分析者更感兴趣的是发现词之间的关联例如：数据和发掘。而不是词频区间例如,数据：1,4，发掘：2,3之间的关联。l一种方法是将数据变换成0/1矩阵；其中，假设规范化词频超越某个阈值t，那么值为1，否那么为0。l该方法缺陷是阈值难确定。l另一种方法是采用min-apriori方法。l S(word1, word2)=min(0.3, 0.6)+min(0.1 , 0.2)+l min

8、(0.4,0.2)+min(0.2, 0)l =0.6lMin-apriori中支持度s随着词的规范化频率添加而增大。随包含该词的文档个数添加而单调递增。处置概念分层处置概念分层l概念分层是定义在一个特定的域中的各种实体或概念的多层组织。l概念分层可以用有向无环图表示。l概念分层主要优点l1位于层次构造较下层的项如：AC适配器能够没有足够的支持度，但是，作为概念分层构造中它们的父母结点如：便携机配件具有较高支持度。l2在较低层发现的规那么倾向于过于特殊，能够不如较高层的规那么令人感兴趣。如：脱脂牛奶普通面包，脱脂牛奶白面包，等过于特殊l实现概念分层的方法l每个事务t用它的扩展事务t取代，其中，

9、t包含t中一切项和它们的对应祖先。如：事务DVD，普通面包可以扩展为DVD，普通面包，家电，电子产品，面包，食品l然后对扩展的数据库运用如Apriori等已有的算法来发现跨越多个概念层的规那么。l概念分层主要缺陷l1处于较高层的项比处于较低层的项趋向于具有较高的支持度计数。l2概念分层的引入添加了关联分析的计算时间。l3概念分层的引入能够产生冗余规那么。规那么X Y是冗余的，假设存在一个更普通的规那么X Y，其中X是X的祖先，Y是Y的祖先，并且两个规那么具有非常类似的置信度。例如：面包 牛奶，白面包 脱脂牛奶序列方式序列方式l购物篮数据经常包含关于商品何时被顾客购买的时间信息。可以运用这种信息

10、，将顾客在一段时间内的购物拼接成事务序列。l然而，迄今为止所讨论的关联方式概念都只强调同时出现关系，而忽略数据中的序列信息。l对于识别动态系统的重现特征，或预测特定事件的未来发生，序列信息能够是非常有价值的。序列方式序列方式l将与对象A有关的一切事件按时间增序陈列，就得到A的一个序列sequenceObjectTimestampEventsA102, 3, 5A206, 1A231B114, 5, 6B172B217, 8, 1, 2B281, 6C141, 8, 7Sequence Database:l普通地，序列是元素element的有序列表，可以记作s=, 其中每个ej是一个或多个事件的

11、集族，即ej=i1，i2，ik。SequenceE1E2E1E3E2E3E4E2Element (Transaction)Event (Item)序列数据的例子序列数据的例子子序列子序列 Subsequencel序列t是另一个序列s的子序列subsequence，假设t中每个有序元素都是s中一个有序元素的子集。Data sequenceSubsequenceContain?Yes NoYes序列方式发现序列方式发现Sequential Pattern Miningl设D是包含一个或多个数据序列的数据集: l序列s的支持度是包含s的一切数据序列所占的比例。假设序列s的支持度大于或等于用户指定的阈

12、值minsup，那么称s是一个序列方式或频繁序列。 l定义7.1 序列方式发现:l给定序列数据库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%ObjectTimestampEventsA11,2,4A22,3A35B11,2B22,3,4C11, 2C22,3,4C32,4,5D12D23, 4D34, 5E11, 3E22, 4, 5提

13、取序列方式：蛮力方法提取序列方式：蛮力方法l给定n个事件的集族: i1, i2, i3, , inl候选 1-序列: l, , , , l候选 2-序列:l , , , , , , , l候选 3-序列:l, , , , , ,l, , , , , l候选序列的个数比候选项集的个数大得多。产生更多候选的缘由有下面两个l一个项在项集中最多出现一次，但一个事件可以在序列中出现多次。给定两个项i1和i2，只能产生一个候选2-项集i1，i2，但却可以产生许多候选2-序列，如, , , 。l次序在序列中是重要的，但在项集中不重要。例如，1,2和2,1表示同一个项集，而和对应于不同的序列，因此必需分别产生

14、。l先验原理对序列数据成立。l包含特定k-序列的任何数据序列必然包含该k-序列的一切(k-1)-序列 。序列方式发现的类序列方式发现的类Apriori算法算法候选产生候选产生l一对频繁(k-1)-序列合并，产生候选k-序列。l为了防止反复产生候选，传统的Apriori算法仅当前k-1项一样时才合并一对频繁k-项集。类似的方法可以用于序列。l例子l经过合并和得到 。由于事件3和事件4属于第二个序列的不同元素，它们在合并后序列中也属于不同的元素。l经过合并和得到 。由于事件3和事件4属于第二个序列的一样元素，4被合并到第一个序列的最后一个元素中。l候选剪枝l一个候选k-序列被剪枝，假设它的(k-1

15、)-序列最少有一个是非频繁的。l例如，假设是一个候选4-序列。我们需求检查和能否是频繁3-序列。由于它们都不是频繁的，因此可以删除候选。l支持度计数l在支持度计数期间，算法将枚举属于一个特定数据序列的一切候选k-序列。l计数之后，算法将识别出频繁k-序列，并可以丢弃其支持度计数小于最小支持度阈值minsup的候选。图图7-6时限约束时限约束l方式的事件和元素都施加时限约束。l例子：学生A：l 学生B：l感兴趣的方式是，意思是说注册数据发掘课程的学生必需先选修数据库系统和统计学方面的课程。l显然，该方式被这两个学生支持，虽然他们都没有同时选修统计学和数据库系统。l相比之下，一个10年之前选修了统

16、计学课程的学生不能以为支持该方式，由于这些课程的时间间隔太长了。l图7-7解释了可以施加在方式上的某些时限约束。最大跨度约束最大跨度约束l最大跨度约束指定整个序列中所允许的事件的最晚和最早发生时间的最大时间差。l假定最大时间跨度maxspan=3，下面的表包含了给定的数据序列支持和不支持的序列方式。数据序列数据序列s序列方式序列方式tS支持支持t?是是 否l普通，maxspan越长，在数据序列中 检测到方式的能够性就越大。然而，较长的maxspan也能够捕获不真实的方式能够涉及陈旧事件。l最大跨度约束影响序列方式发现算法的支持度计数。施加最大时间跨度约束之后，有些数据序列就不再支持候选方式。最

17、小间隔和最大间隔约束最小间隔和最大间隔约束l时限约束也可以经过限制序列中两个相继元素之间的时间差来指定。l假设最大时间差maxgap是一周，那么元素中的事件必需在前一个元素的事件出现后的一周之内出现。l假设最小时间差mingap是0，那么元素中的事件必需在前一个元素的事件出现之后出现。l假定maxgap=3，mingap=1，下表给出了方式经过或未经过最大间隔和最小间隔约束的例子。数据序列数据序列s序列方式序列方式tmaxgapmingap经过经过经过未经过未经过经过 未经过未经过l与最大跨度一样，这些约束也影响序列方式发现算法的支持度计数，由于当最小间隔和最大间隔约束存在时，有些数据序列就不

18、再支持候选方式。l运用最大间隔约束能够违反先验原理。l为了解释这一点，思索图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%ObjectTimestampEventsA11,2,4A22,3A35B11,2B22,3,4C11, 2C22,3,4C32,4,5D

19、12D23, 4D34, 5E11, 3E22, 4, 5l定义7.2 邻接子序列l序列s是序列w=的邻接子序列(contiguous subsequence)，假设以下条件之一成立：l1s是从e1或ek中删除一个事件后由w得到。l2s是从至少包含两个事件的恣意eiw中删除一个 l 事件后由w得到。l3s是t的邻接子序列，而t是w的邻接子序列。数据序列数据序列s序列方式序列方式tt是是s的邻接子序列的邻接子序列是是是否 否l定义7.3 修订的先验原理l假设一个k-序列是频繁的，那么它的一切邻接(k-1)-子序列也一定是频繁的。l在候选剪枝阶段，并非一切的k-序列都需求检查，由于它们中的一些能够

20、违反最大间隔约束。例如，假设maxgap=1，那么不用检查候选的子序列能否是频繁的，由于元素2,3和5之间的时间差大于一个时间单位。l我们只需求调查的邻接子序列，包括，和。窗口大小约束窗口大小约束l最后，元素sj中的事件不用同时出现。可以定义一个窗口大小阈值ws来指定序列方式的恣意元素中事件最晚和最早出现之间的最大允许时间差。窗口大小为0阐明方式同一元素中的一切事件必需同时出现。l下面的例子运用ws=2，mingap=0，maxgap=3，maxspan=数据序列数据序列s序列方式序列方式tS支持支持t？是是否 否子图方式子图方式l关联分析方法运用到远比项集和序列更复杂实体。例子包括化学化合物

21、、3-D蛋白质构造、网络拓扑和树构造的XML文档。这些实体可以用图形表示建模。l在这种类型的数据上进展数据发掘的义务是，在图的集合中发现一组公共子构造。这样的义务称作频繁子图发掘DatabasesHomepageResearchArtificialIntelligenceData Mining图与子图图与子图l定义7.5 支持度l给定一个图的集族,子图g的支持度定义为包含它的一切图所占的百分比，即l例7.2 思索5个图G1到G5，如图7-10所示。右上角的图g1是G1，G3，G4，G5的子图，因此s(g1)=4/5=80%。类似地，我们由s(g2)=60%，由于g2是G1、G2和G3的子图；而

22、s(g3)=40%，由于g3是G1和G3的子图。| ,| |)(iiiGsGgGgs频繁子图发掘频繁子图发掘l定义7.6 频繁子图发掘l给定图的集合和支持度阈值minsup，频繁子图发掘的目的是找出一切使得s(g)=minsup的子图g。l本章的讨论主要关注无向连通图undirected，connected graph。l发掘频繁子图是一项计算量很大的义务，由于搜索空间是指数的。为了解释这项义务的复杂性，思索一个包含d个实体的数据集。在频繁项集发掘中，每个实体是一个项，待调查的搜索空间是2d，这是能够产生的候选项集的个数。l在频繁子图发掘中，每个实体是一个顶点，并且最多可以有d-1条到其他顶点

23、的边。假定顶点的标号是独一的，那么子图的总数是l 其中， 是选择i个顶点构成子图的方法数，而 是子图的顶点之间边的最大值。表7-8对不同的d比较了项集和子图的个数。diiiidC12/ )1(2idC2/ )1(2iil发掘频繁子图的一种蛮力方法是，产生一切的连通子图作为候选，并计算它们各自的支持度。l思索图7-11a中显示的图，假定顶点标号选自集合a，b，而边的标号选自集合p，q，那么具有一个到三个顶点的连通子图列在图7-11b中。l候选子图的个数比传统的关联规那么发掘中的候选项集的个数大得多，其缘由：l一个项在一个项集中至多出现一次，而一个顶点标号能够在一个图中出现多次。l一样的顶点标号对

24、可以有多种边标号选择。把事务转化为图把事务转化为图Transaction IdItems1A,B,C,D2A,B,E3B,C4A,B,D,E5B,C,DABCDETID = 1:把图转化为事务把图转化为事务频繁子图发掘算法的普通构造频繁子图发掘算法的普通构造l一种发掘频繁子图的类Apriori算法由以下步骤组成l候选产生：合并频繁(k-1)-子图对，得到候选k-子图。l候选剪枝：丢弃包含非频繁的(k-1)-子图的一切候选k-子图。l支持度计数：统计中包含每个候选的图的个数。l候选删除：丢弃支持度小于minsup的一切候选子图。候选产生候选产生l在候选产生阶段，一对频繁(k-1)-子图合并成一个

25、候选k-子图。l如何定义子图的大小k？l在图7-11显示的例子中，k是图中的顶点个数。经过添加一个顶点，迭代的扩展子图的方法称作顶点增长vertex growing。lK也可以是图中边的个数。添加一条边到已有的子图中来扩展子图的方法称作边增长edge growing。l为了防止产生反复的候选，可以对合并施加附加的条件：两个(k-1)-子图必需共享一个共同的(k-2)-子图。共同的(k-2)-子图称作核(core)。经过顶点增长产生候选经过顶点增长产生候选l用邻接矩阵表示图。l顶点增长方法可以看成合并一对(k-1) (k-1)的邻接矩阵，产生kk邻接矩阵的过程。l经过顶点增长合并子图的过程：l邻

26、接矩阵M1与另一个邻接矩阵M2合并，假设删除M1和M2的最后一行和最后一列得到的子矩阵一样。l结果矩阵是M1，添加上M2的最后一行和最后一列。l新矩阵的其他项或者为0，或者用衔接顶点对的合法的边标号交换。Vertex Growingararl结果图包含的边比原来的图多一条或两条。l(d,e)可以相连或不相连。l由于该边的标号未知，我们需求对(d,e)思索一切能够的边标号，从而大大添加了候选子图的个数。经过边增长产生候选经过边增长产生候选l在候选产生期间，边增长将一个新的边插入一个曾经存在的频繁子图中。l与顶点增长不同，结果子图的顶点个数不一定添加。l经过边增长产生候选子图的过程概括如下：l一个

27、频繁子图g1与另一个频繁子图g2合并，仅当从g1删除一条边得到的子图与从g2删除一条边得到的子图拓扑等价。合并后，结果子图是g1，添加g2的那条额外的边。al顶点拓扑等价topologically equivalent：参与一条新边到v1与参与该边到v2产生的图一样，那么v1和v2两顶点拓扑等价。l顶点拓扑等价的概念可以协助我们了解，在边增长时为什么可以产生多个候选子图。l假设a和c拓扑等价，我们将它们记作a=c。对于核外边的点，假设它们的标号一样，我们将它们记作b=d。l当与一对(k-1)-子图相关联的核有多个时，还能够产生多个候选子图。候选剪枝候选剪枝l产生候选k-子图后，需求剪去(k-1

28、)-子图非频繁的候选。l候选剪枝可以经过如下步骤实现：l相继从k-子图删除一条边，并检查对应的(k-1)-子图能否连通且频繁。l假设不是，那么该候选k-子图可以丢弃。l为了检查(k-1)-子图能否频繁，需求将它与其他频繁(k-1)-子图匹配。断定两个图能否拓扑等价称为图同构graph isomorphism问题。l为了解释图同构问题的困难性，思索图7-19中的两个图。同构图同构图处置图同构处置图同构l处置图同构问题的规范方法是，将每一个图都映射到一个独一的串表达式，称作代码code或规范标号canonical label。l规范标号具有如下性质：假设两个图是同构的，那么它们的代号一定一样。这个

29、性质使得我们可以经过比较图的规范标号来检查图同构。l构造图的规范标号的第一步是找出图的邻接矩阵表示。一个图可以有多种邻接矩阵表示，由于存在多种确定顶点次序的方法。l数学上讲，每个陈列都对应于初始邻接矩阵与一个对应的陈列矩阵的乘积，如下面的例子所示。l例子：思索下面的矩阵：l其中，P13是经过交换单位矩阵的第一行和第三行得到的。为了交换M的第一和第三行和列，陈列矩阵与M相乘16151413121110987654321M100000010010010013PlM右乘P13交换M的第一列和第三列，而M左乘P13交换M的第一行和第三行。l第二步是确定每个邻接矩阵的串表示。由于邻接矩阵是对称的，因此只

30、需求根据矩阵的上三角部分构造串表示就足够了。l在图7-21所示的例子中，代码是经过逐列衔接矩阵的上三角元素得到的。l最后一步是比较图的一切串表达式，并选出具有最小最大字典次序值的串。支持度计数支持度计数l支持度计数普通是开销很大的操作，由于对于每个G，必需确定包含在G中的一切候选子图。l加快该操作的一种方法是，维护一个与每个频繁(k-1)-子图相关联的图ID表。一旦一个新的候选k-子图经过合并一对频繁(k-1)-子图而产生，就对它们的对应图ID表求交集。最后，子图同构检查就在表中的图上进展，确定它们能否包含特定的子图。非频繁方式非频繁方式l迄今为止，关联分析都基于这样的前提：项在事务中出现比不

31、出现更重要。l因此，数据库中很少出现的方式不是令人感兴趣的，并运用支持度度量将其删除。这种方式称为非频繁方式。l定义7.7 非频繁方式l非频繁方式是一个项集或规那么，其支持度小于阈值minsup。l虽然绝大部分非频繁方式都是让人不感兴趣的，但是其中的一些能够对于分析是有用的，特别是涉及到数据中的负相关性。l例如：DVD和VCR一同销售的情况很少，由于购买DVD的人多半不会购买VCR，反之亦然。l这种负相关方式有助于识别竞争项competing item。l竞争项的例子包括茶与咖啡、黄油与人造黄油、普通与节食苏打、台式机与便携式计算机。l某些非频繁方式也能够暗示数据中出现了某些有趣的稀有事件或例

32、外情况。l例如：假设火灾=yes是频繁的，但火灾=yes，报警=on是非频繁的。而后者是一个有趣的非频繁方式，由于它能够指出警报系统的缺点。l为了检测这种不寻常情况，必需确定方式的期望支持度，使得假设一个方式的支持度明显低于期望支持度，那么可以声明它是一个有趣的非频繁方式。负方式负方式l设I=i1,i2,id是项的集合。负项ik表示项ik不在给定的事务中出现。例如，假设事务中不包含咖啡，那么咖啡是一个值为1的负项。l定义 7.8 负项集l负项集X是一个具有如下性质的项集：1X=AB，其中A是正项的集合，而B是负项的集合，|B|1; 2s(X) minsup。l定义 7.9 负关联规那么l负关联

33、规那么是一个具有如下性质的关联规那么：1规那么是从一个负项集提取的，2规那么的支持度大于或等于minsup，3规那么的置信度大于或等于minconfl本章中，负项集和负关联规那么统称负方式负相关方式负相关方式l定义7.10 负相关项集l项集X=x1,x2,xk是负相关的，假设l定义7.11 负相关关联规那么l关联规那么X Y是负相关的，假设s(XY)s(X)s(Y)，其中，X和Y是不相交的项集，即X Y=。l负相关的完全条件可以表述如下：)(.)()()()(211kkjjxsxsxsxsXsjjiiysxsYXs)()()(l负相关条件也可以用正项集和负项集的支持度表示。设 和 分别表示X和

34、Y的对应负项集，由于 l负相关条件可以表述如下：l负相关项集和负相关关联规那么统称负相关方式negatively correlated pattern Y()() ( )() ()() ()()()1()()() - () ()() ()() ()s XYs X s Ys XYs XYs XYs XYs XYs XYs XYs XYs XYs XY s XYs XY s XYs XY s XYX)()()()(YXsYXsYXsYXs非频繁方式、负方式和负相关方式比较非频繁方式、负方式和负相关方式比较l非频繁方式、负方式和负相关方式是三个亲密相关的概念。l虽然非频繁方式和负相关方式只涉及包含正

35、项的项集或方式，而负方式涉及包含正项和负项的项集或方式，但是这三个概念之间存在一定的共性，如图7-22所示l首先，许多非频繁方式有对应的负方式。l假设x y是非频繁的，那么除非minsup太高，否那么它很能够有对应的负项集。l例如：假定minsup0.25，假设x y是非频繁的，那么表中的其它几种组合至少有一种是频繁的。yyxS(xy)S(xy)S(x)xS(xy)S(xy)S(x)S(y)S(y)1发掘有趣的非频繁方式的技术发掘有趣的非频繁方式的技术l原那么上讲，非频繁项集是未被规范的频繁项集产生算法如Apriori和FP增长提取的一切项集。这些项集对应于图7-23所示的频繁项集边境之下的那

36、些项集。l由于非频繁方式的数量能够是指数级的，特别是对于稀疏的、高维的数据。l因此，为发掘非频繁方式而开发的技术着力于发现有趣的非频繁方式。l例如：负相关方式基于发掘负方式的技术基于发掘负方式的技术l一种方法是将每个项看作对称的二元变量。经过用负项增广，将事务数据二元化。然后运用Apriori算法等，可以导出一切的负项集。l仅当只需少量变量被视为对称的二元变量时，该方法才是可行的。假设每个项都必需视为对称的二元变量，那么能够导致计算复杂度添加。l(1)当每个项都用对应的负项增广时，项的个数就加倍。待探测的项集格比2d大得多。l(2)当添加进负项后，基于支持度的剪枝不再有效。对于每个变量x，x或 的支持度大于等于50%.因此，即使支持度阈值到达50%，仍有一半的项是频繁的。l(3)当添加进负项后，每个事务的宽度添加。当包含负项后，事务的宽度添加到d。xl另一种方法不是用负项增广数据，而是根据对应的正项集计算负项集的支持度。例如， 的支持度可以用如下方法计算：l ,rqp),(),(),()(),(rqpsrpsqpspsrqpsniiZYZiZXs