资源描述：
《数据挖掘原理、算法及应用第3章关联规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
第3章 关联规则挖掘3.1基本概念3.2关联规则挖掘算法3.3Apriori改进算法3.4不候选产生挖掘频繁项集3.5使用垂直数据格式挖掘频繁项集3.6挖掘闭频繁项集3.7挖掘各种类型的关联规则3.8相关分析3.9基于约束的关联规则3.10矢量空间数据库中关联规则的挖掘 3.1基本概念交易数据库又称为事务数据库，尽管它们的英文名词一样，但是事务数据库更具有普遍性。例如，病人的看病记录、基因符号等用事务数据库更贴切。因此，下面的叙述更多使用事务数据库这一名词，而不用交易数据库这个名词。 一个事务数据库中的关联规则挖掘可以描述如下：设I={i1,i2,…,im}是一个项目集合，事务数据库D={t1,t2,…,tn}是由一系列具有惟一标识的TID事务组成。每一个事务ti(i=1,2,…,n)都对应I上的一个子集。定义3.1设I1I，项目集(Itemsets)I1在数据集D上的支持度(Support)是包含I1的事务在D中所占的百分比，即式中：||·||表示集合中元素数目。(3.1) 定义3.2对项目集I，在事务数据库D中所有满足用户指定的最小支持度(Minsupport)的项目集，即不小于Minsupport的I的非空子集，称为频繁项目集(FrequentItemsets)或大项目集(LargItemsets)。定义3.3一个定义在I和D上，形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来定义的。所谓规则的可信度，是指包含I1和I2的事务数与包含I1的事务数之比，即(3.2) 定义3.4D在I上满足最小支持度和最小置信度(Minconfidence)的关联规则称为强关联规则(StrongAssociationRules)。通常所说的关联规则一般是指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。 (1)发现频繁项目集：通过用户给定的最小支持度，寻找所有频繁项目集，即满足支持度Support不小于Minsupport的所有项目子集。发现所有的频繁项目集是形成关联规则的基础。(2)生成关联规则：通过用户给定的最小可信度，在每个最大频繁项目集中，寻找置信度不小于Minconfidence的关联规则。 3.2关联规则挖掘算法3.2.1项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集空间理论。理论的核心为：频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。这个理论一直作为经典的数据挖掘理论被应用。 定理3.1如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。证明设X是一个项目集，事务数据库D中支持X的元组(记录)数为S。设X的任一非空子集YX，事务数据库D中支持Y的元组(记录)数为S1。根据项目集支持度的定义，很容易知道支持X的元组一定支持Y，所以S1≥S，即support(Y)≥support(X)按假设，项目集X是频繁项目集，即support(X)≥minsupport所以support(Y)≥support(X)≥minsupport，因此Y是频繁项目集。 定理3.2如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明设事务数据库D中支持X的元组数为S。设X的任一超集ZX，事务数据库D中支持Z的元组数为S2。根据项目集支持度的定义，很容易知道支持Z的元组一定支持X，所以S2≤S，即support(Z)≤support(X) 按假设，项目集X是非频繁项目集，即support(X)2)THENgenerateRules(lk∈L,xm-1∈X,minConfidence);(7)} 利用频繁项目集生成关联规则就是逐一测试在所有频繁项集中可能生成的关联规则、对应的支持度、置信度参数。算法3.5实际上采用深度优先搜索方法来递归生成关联规则，当然，同样也可以使用广度优先搜索方法来递归生成关联规则，读者可以自己尝试来完成。 【例3.2】对于例3.1事务数据库D，假定发现的频繁项集l={I1,I2,I5}，试找出由l产生的所有关联规则。频繁项集l={I1,I2,I5}的所有非空子集为{I1,I2}、{I1,I5}、{I2,I5}、{I1}、{I2}、{I5}则其对应的关联规则和置信度如下：(1)I1∧I2I5，confidence=2/4=50%;(2)I1∧I5I2，confidence=2/2=100%;(3)I2∧I5I1，confidence=2/2=100%; (4)I1I2∧I5，confidence=2/6=33%;(5)I2I1∧I5，confidence=2/7=29%;(6)I5I1∧I2，confidence=2/2=100%。如果最小置信度阈值为70％，则只有(2)、(3)和(6)为强关联规则。由频繁项目集生成关联规则的优化问题主要集中在减少不必要的规则生成尝试方面。 定理3.3设有频繁项目集l，项目集Xl，X1为X的一个子集，即X1X。如果关联规X(l-X)不是强关联规则，那么X1(l-X1)一定不是强关联规则。证明由支持度的定义可知，X1的支持度support(X1)一定大于X的支持度support(X)，即support(X1)≥support(X)所以confidence(X1(l-X1))=support(l)/support(X1)≤confidence(X(l-X))=support(l)/support(X) 由于X(l-X)不是强关联规则，即confidence(X(l-X))2&confidence(xm-1(l-xm-1))≥minConfidence)作为递归结束的判断条件，读者可以自己尝试来完成。 定理3.4设有项目集X，X1是X的一个子集，即X1X，如果规则YX是强规则，那么规则YX1一定是强规则。证明由支持度定义可知，一个项目集的子集的支持度一定大于等于它的支持度，即support(X1∪Y)≥support(X∪Y)所以confidence(YX)=support(X∪Y)/support(Y)≤support(X1∪Y)/support(Y)=support(X1∪Y) 由于YX是强规则，即confidence(YX)≥minConfidence所以corfidence(X1∪Y)≥confidence(YX)≥minConfidence因此，“YX1”也是强规则。由定理3.4可知，在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定是强规则的尝试。这个定理也保证把测试的注意点放在判断最大频繁项目集的合理性上。实际上，只要从所有最大频繁项目集出发去测试可能的关联规则即可，因为其他频繁项目集生成的规则的右项一定包含在对应的最大频繁项目集生成的关联规则右项中。 3.3Apriori改进算法3.3.1Apriori算法的瓶颈Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。但是随着研究的深入，它的缺点也暴露出来。Apriori算法有两个致命的性能瓶颈。(1)多次扫描事务数据库，需要很大的I／O负载。对每次k循环，候选集Ck中的每个元素都必须通过扫描一次数据库来验证其是否加入Lk。假如一个频繁大项目集包含10个项，那么就至少需要扫描事务数据库10遍。 (2)可能产生庞大的候选集。由Lk-1产生k候选集Ck是呈指数增长的，例如104个1频繁项目集,Apriori算法能产生多达107个2候选集。如此大的候选集对时间和主存空间都是一种挑战。因此，包括Agrawal在内的许多学者提出了Apriori算法的改进方法。 3.3.2改进算法1.基于散列的技术(散列项集到对应的桶中)一种基于散列的技术可以用于压缩候选k项集Ck(k>1)。例如，当扫描数据库中的每个事务，由C1中的候选1项集产生频繁1项集L1时，可以对每个事务产生所有的2项集，将它们散列(即映射)到散列表结构的不同桶中，并增加对应的桶计数(如图3-2所示)。在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁的，因而应当从候选项集中删除。这种基于散列的技术可以显著压缩要考察的候选k项集。 图3-2候选2项集的散列表 2.事务压缩不包含任何频繁k项集的事务不可能包含任何频繁(k+1)项集。因此，这种事务在其后考虑中，可以加上标记或删除，因为产生j(j>k)项集的数据库扫描不再需要它们。 3.划分使用划分技术只需要两次数据库扫描，以挖掘频繁项集(如图3-3所示)。它包含两个阶段。在阶段Ⅰ，算法将D中的事务分成n个非重叠的划分。如果D中事务的最小支持度阈值为min_sup，则一个划分的最小支持度计数为min_sup乘以该划分中的事务数。对每个划分，找出该划分内的所有频繁项集。这些称做局部频繁项集(LocalFrequentItemset)。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。对于k=1，2，…，n找出所有的局部频繁项集只需要扫描一次数据库。 图3-3通过划分数据进行挖掘 局部频繁项集可能是也可能不是整个数据库D的频繁项集。D的任何频繁项必须作为局部频繁项集至少出现在一个划分中。这样，所有的局部频繁项集是D的候选项集。所有划分的频繁项集的集合形成D的全局候选项集。在阶段Ⅱ，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。划分的大小和划分的数目以每个划分能够放入内存为原则来确定，这样每阶段只需要读一次。 4.抽样抽样方法的基本思想：选取给定数据D的随机样本S，然后在S中搜索频繁项集。用这种方法，虽然牺牲了一些精度但换取了有效性。样本S的大小选取使得可以在内存中搜索S的频繁项集。这样，总共只需要扫描一次S中的事务。由于搜索S中而不是D中的频繁项集，可能丢失一些全局频繁项集。为减少这种可能性，使用比最小支持度低的支持度阈值来找出S中局部的频繁项集(记作LS)。然后，数据库的其余部分用于计算LS中每个项集的实际频率。使用一种机制来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，则只需要扫描一次D。否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须频繁运行时，抽样方法特别合适。 5.动态项集计数动态项集计数技术将数据库划分为用开始点标记的块。不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已计数的所有项集的支持度，如果一个项集的所有子集已确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。 3.4不候选产生挖掘频繁项集频繁模式增长(FrequentPatternGrowth)，或简称FP增长，试图设计一种方法，挖掘全部频繁项集而不产生候选。它采取如下分治策略：首先，将提供频繁项的数据库压缩到一棵频繁模式树(或FP树)，但仍保留项集关联信息。然后，将压缩后的数据库划分成一组条件数据库(一种特殊类型的投影数据库)，每个与一个频繁项或“模式段”关联，并分别挖掘每个条件数据库。 【例3.3】FP增长(发现频繁项集而不产生候选)。使用频繁模式增长方法，重新考察例3.1中表3-1的事务数据库D的挖掘。数据库的第一次扫描与Apriori相同，它导出频繁项(1项集)的集合和支持度计数(频率)。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或列表记作L，L=［I2:7,I1:6,I3:6,I4:2,I5:2］。 FP树构造：首先，创建树的根节点，用“null”标记。第二次扫描数据库D。每个事务中的项按L中的次序处理(即按递减支持度计数排序),并对每个事务创建一个分枝。例如，扫描第一个事务“T100:I1,I2,I5”包含三项(按L的次序I2，I1，15)，导致构造树包含这三个节点的第一个分枝〈I2:1〉,〈I1:1〉,〈I5:1〉，其中，I2作为根的子女链接到根，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀I2。这样，将节点I2的计数增加1，并创建一个新节点〈I4:1〉作为〈I2:2〉的子女链接。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数增加1，为在前缀之后的项创建节点和链接。 为方便树遍历，创建一个项头表，使每项通过一个节点链指向它在树中的位置。扫描所有的事务之后得到的树如图3-4所示，带有相关的节点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP树问题。 图3-4存放压缩的频繁模式信息的FP树 FP树的挖掘过程：由每个长度为1的频繁模式(初始后缀模式)开始，构造它的条件模式基(一个“子数据库”由FP树中与后缀模式一起出现的前缀路径集组成)，然后，构造它的条件FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。 该FP树的挖掘总结在表3-2中，细节如下。首先考虑I5，它是L中的最后一项，而不是第一个。从表的后端开始的原因随着解释FP树挖掘过程就会清楚。I5出现在图3-3的FP树的两个分枝(I5的出现沿它的节点链容易找到)。这些分枝形成的路径是〈I2,I1,I5:1〉和〈I2,I1,I3,I5：1〉。因此，考虑I5为后缀，它的两个对应前缀路径是〈I2,I1:1〉和〈I2,I1,I3:1〉，形成I5的条件模式基。它的条件FP树只包含单个路径〈I2:2,I1:2〉；不包含I3，因为它支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}。 表3-2通过创建条件子模式基挖掘FP树 I4的两个前缀路径形成条件模式基{I2I1:1},{I2:1},产生单节点的条件FP树〈I2:2〉，并导出一个频繁模式{I2,I4:2}。注意，尽管I5跟在第一个分枝中的I4之后，也没有必要在此分析中包含I5，因为涉及I5的频繁模式在考察I5时已经分析过。 与以上分析类似，I3的条件模式基是{(I2I1:2)，(I2:2)，(I1:2)}。它的条件FP树有两个分枝〈I2:4,I1:2〉和〈I1:2〉，如图3-5所示，它产生模式集：{I2I3:4,I1I3:4,I2I1I3:2}。最后，I1的条件模式基是{(I2:4)}，它的FP树只包含一个节点〈I2:4〉，产生一个模式{I2I1:4}。挖掘过程总结在算法3.6中。 图3-5具有条件节点I3的条件FP树 算法3.6FP增长。使用FP树，通过模式段增长挖掘频繁模式。输入：事务数据库D；最小支持度计数阈值min_sup。 输出：频繁模式的完全集。方法：(1)按以下步骤构造FP树：①扫描事务数据库D一次。收集频繁项的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。②创建FP树的根节点，以“null”标记它。对于D中每个事务Trans，执行： 选择Trans中的频繁项，并按L中的次序排序。设排序后的Trans中频繁项列表为［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非空，递归地调用inserttree(P,N)。 (2)FP树的挖掘通过调用FP_growth(FP-tree，null)实现。该过程实现如下：procedureFP_growth(Tree，α)①IFTree含单个路径Pthen②FOReach路径P中节点的每个组合(记作β)③产生模式β∪α，其支持度计support_count等于β中节点的最小支持度计数；④ELSE⑤FORTree的头表中的每个αi{ ⑥产生模式β=αi∪α，其支持度计数support_count=αi.support_count;⑦构造β的条件模式基，然后构造β的条件FP树Treeβ，⑧IFTreeβ≠Φthen⑨调用FP-growth(Treeβ,β)；⑩} FP增长方法将发现长频繁模式的问题转换成递归地搜索一些较短模式，然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP树有时是不现实的。一种有趣的可选方案是首先将数据库划分成投影数据库的集合，然后在每个投影数据库构造FP树并挖掘它。如果投影数据库的FP树还不能放进内存，该过程可以递归地用于投影数据库。 对FP增长方法的性能研究表明：对于挖掘长和短的频繁模式，它都是有效的和可规模化的，并且比Apriori算法快约一个数量级。它也比树一投影算法快。树一投影算法递归地将数据库投影到投影数据库树。 3.5使用垂直数据格式挖掘频繁项集Apriori和FP增长方法都从TID项集格式(即{TID:itemset})的事务集挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品集。这种数据格式称做水平数据格式(horizontaldataformat)。另处，数据也可以用项TID集格式(即{item:TID_set})表示，其中item是项的名称，而TID_set是包含item的事务的标识符的集合。这种格式称做垂直数据格式(verticaldataformat)。 【例3.4】使用垂直数据格式挖掘频繁项集。考虑例3.1中表3-1的事务数据库D的水平数据格式。扫描一次该数据集可以将它转换成表3-3所示的垂直数据格式。通过取每对频繁单个项的TID集的交，可以对该数据集进行挖掘。最小支持度计数为2。由于表3-3的每个项都是频繁的，总共进行10次交运算，导致8个非空2项集，如表3-4所示。注意，项集{I1,I4}和{I3,I5)各只包含一个事务，因此它们都不属于频繁2项集的集合。 根据Apriori性质，一个给定的3项集是候选3项集，仅当它的每一个2项集子集都是频繁的。通过取这些候选3项集任意两个对应的2项集的TID集的交，得到表3-5，其中只有两个频繁3项集{I1,I2,I3:2}和{I1,I2,I5:2}。 表3-3表3-1的事务数据库D的垂直数据格 表3-4垂直数据格式的2项集 表3-5垂直数据格式的3项集 例3.4解释了通过探查垂直数据格式挖掘频繁项集的过程。首先，通过扫描一次数据集将水平格式的数据转换成垂直格式。项集的支持度计数直接是项集的TID集的长度。从k=1开始，根据Apriori性质，使用频繁k项集来构造候选(k+1)项集。通过取频繁k项集的TID集的交计算对应的(k+1)项集的TID集。重复该过程，每次k增值1，直到不能再找到频繁项集或候选项集。 除了由频繁k项集产生候选(k+1)项集时利用Apriori性质之外，这种方法的另一优点是不需要扫描数据库来确定(k+1)项集(对于k≥1)的支持度。这是因为每个k项集的TID集携带了计算该支持度所需的完整信息。然而，TID集可能很大，需要大量空间，同时求大集合的交也需要大量计算时间。 为了进一步降低存储长TID集合的开销以及求交的计算开销，可以使用一种称做差集(diffset)的技术。该技术仅记录(k+1)项集的TID集与一个对应的k项集的TID集之差。例如，在例3.4中，有{I1}={T100,T400,T500,T700,T800,T900)和{I1,I2}={T100,T400,T800,T900}。二者的差集为diffset({I1,I2},{I1})={T500,T700}。这样，不必记录构成{I1}和{I2)交集的4个TID，可以使用差集仅记录代表{I1}和{I1,I2)差的两个TID。实验表明，在某些情况下，如当数据集包含许多稠密和长模式时，该技术可以显著地降低频繁项集垂直格式挖掘的总开销。 3.6挖掘闭频繁项集频繁项集挖掘可能产生大量频繁项集，特别是当最小支持度阈值min_sup设置较低或数据集中存在长模式时尤其如此。闭频繁项集可以显著减少频繁项集挖掘所产生的模式数量，而且保持关于频繁项集的完整信息。也就是说，从闭频繁项集的集合可以很容易地推出频繁项集的集合和它们的支持度。这样，在许多实践中，更希望挖掘闭频繁项集的集合，而不是所有频繁项集的集合。 1999年，Pasquier等人提出闭合项目集挖掘理论，并给出了基于这种理论的Close算法。他们给出了闭合项目集的概念，并讨论了这个闭合项目集格空间上的基本操作算子。定义3.5设I={i1,i2,…,im}是一个项目集合，项集XI、YI。如果项集X是项集Y的真子集，亦XY，则称项集Y是项集X的真超项集。换而言之，X的每一项集包含在Y中，但是Y至少有一个项不在X中。 定义3.6设S为一事务数据集，如果项集X不存在真超集Y使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。如果项集X在数据集S中是闭的和频繁的，则项集X是数据集S中的闭频繁集。定义3.7如果X是频繁的，并且不存在超项集YX在S中是频繁的，项集X是数据集S中的极大频繁项集(极大项集)。 设C是数据集S中满足最小支持度阈值min_sup的闭频繁项集的集合，令M是S中满足min_sup的极大频繁项集的集合。假定有C和M中的每个项集的支持度计数。注意，C和它的计数信息可以用来导出频繁项集的完整集合。因此，称C包含了关于频繁项集的完整信息。另一方面，M只存储了极大项集的支持度信息。通常，它并不包含其对应的频繁项集的完整的支持度信息。用下面的例子解释这些概念。 【例3.5】假定事务数据库只有两个事务：{〈a1,a2,…,a100〉;〈a1,a2,…,a50〉}。设最小支持度计数阈值min_sup=1。发现两个闭频繁项集和它们的支持度，即C={{a1,a2,…,a100}:1;{a1,a2,…,a50}:2}。只有一个极大频繁项集：M={{a1,a2,…,a100}:1}。({a1,a2,…,a50}不能包含在极大频繁项集中，因为它有一个频繁超集{a1,a2,…,a100})，与上面相比，那里确定了2100-1个频繁项集，数量太大，根本无法枚举! 闭频繁项集的集合包含了频繁项集的完整信息。例如，可以从C推出：(1){a2,a45:2}，因为{a2,a45}是{a1,a2,…,a50}的子集；(2){a8,a55:1}，因为{a8,a55}不是{a1,a2,…,a50}的子集，而是{a1,a2,…,a100}的子集。然而，从极大频繁项集只能断言两个项集({a2,a45}和{a8,a55})是频繁的，但是不能断言它们的实际支持度计数。 挖掘闭频繁项集的一种朴素方法是首先挖掘频繁项集的完全集，然后删除这样的频繁项集，即每个与现有的频繁项集有相同支持度的真子集。然而，这种方法的开销太大，如例3.5所示，为了得到一个长度为100的频繁项集，在开始删除冗余项集之前，这种方法首先必须导出2100-1个频繁项集。这是不能容忍的高开销。事实上，例3.5的数据集中的闭频繁项集的数量非常少。挖掘闭频繁项集(Close)算法的描述： (1)generatorsinFCCl=(1-itemsets)；//候选频繁闭合1项目集(2)FOR(i=1；FCCi.generators=Φ；i++){(3)doswresinFCCi=Φ;(4)supportsinFCCi=0;(5)FCCi=Gen_Closure(FCCi)；//计算FCC的闭合(6)FORallcandidatecloseditemsetsc∈FCCiD0BEGIN(7)IF(c.support≥minsupport)THENFCi=FCi∪{C}；//修剪小于最小支持度的项 (8)FCGi+1=Gen_enerator(FCi)；//连接生成FCGi+1(9)}(10)FC=∪FCi(FCi.closure，FCi.support)；//返回FC(11)Derivingfrequentitemsets(FC，L)； 在Close算法中，使用了迭代的方法：利用频繁闭合i项目集记为FCi，生成频繁闭合(i+1)项目集，记为FCi+1(i≥1)。首先找出候选1项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1中，再将它与自身连接，以得到候选频繁闭合2项目集FCC2，再经过修剪得出FC2，再用FC2推出FC3，如此继续下去，直到有某个值r使得候选频繁闭合r项目集FCCr为空，这时算法结束。 在Close算法中调用了三个关键函数：Gen_Closure(FCCi)，Gen_Generator(FCi)和Derivingfrequentitemsets，它们分别描述如下：Gen_Closure(FCCi)函数(1)FORalltransactionst∈D{(2)Go=Subset(FCCi.generator，t)；(3)FORallgeneratorsp∈Go{(4)IF(P.closure=Φ)THENP.closure=t； (5)ELESP.closure=P.closure∩t；(6)P.support++；(7)}(8)}(9)Answer=∪{c∈FCCi|C.closure≠Φ}； 函数Gen_Closure(FCCi)产生候选的闭合项目集，以用于频繁项目集的生成。设要查找FCCi的闭合，查找闭合的方法是：取出数据库的一项，记为t。如果FCCi的某一项对应的产生式p是t的子集而且它的闭合为空，则把t的闭合记为p的闭合。如果不为空，则把它的闭合与t的交集作为它的闭合。在此过程中也计算了产生式的支持度。最后将闭合为空的产生式从FCCk中删除。 例如，数据库的某一项t={ABCD}，又有FCC2的某个产生式为{AC}，此时如果{AC}的闭合为空，则由于{AC}是{ABCD}的子集，则{AC}的闭合就是{ABCD}。再如，数据库中的一项t={ABC}。由于{AC}也是{ABC}的子集，而且已经知道{AC}的闭合为{ABCD}，所以计算出{ABC}就是{AC}的闭合(因为{ABCD}与{ABC}的交集为{ABC})。如果还存在其他数据库中的项，{AC}是它的子集，则继续计算交集，直到数据库的最后一项。 Gen_Generator函数(1)FORallgeneratorsp∈FCCi+1{(2)Sp=Subset(FCi.generator，p)；//取得p的所有i项子集(3)FORalls∈Sp(4)IF(p∈s.closure)THEN//如果p是它的i项子集闭合的子集(5)deletepfromFCCi+1.generator；//将它删除(6)}(7)Answer=∪{c∈FCCi+1}； 在该算法中，也使用了Apriori算法的两个重要步骤：连接和修剪。在由FCCi生成FCCi+1时，前面的连接和删除非频繁子集与Apriori算法虽然是相同的，但是它增加了一个新步骤，就是对于FCCi+1的每个产生式p，将FCi的产生式中是p的子集的产生式放到Sp中(因为这时已经进行了非频繁子集的修剪，所以p的所有i项子集都存在于FCi中)。对于Sp的每一项s，如果p是s的闭合的子集，则p的闭合就等于s的闭合，此时需要把它从FCCi+1中删除。 例如，FCC2的某一个产生式为{AB}，若将FC2的产生式中{AB}的子集挑选出来，记为Sp，则Sp={{A}{B}}。如果{AB}既不在A的闭合集中，也不在B的闭合集中，就应该保留，否则就应该从FCCi+1中删除。Derivingfrequentitemsets(FC，L)函数 (1)k=０；(2)FORallfrequentcloseditemsetsc∈FC{(3)L‖c‖=L‖c‖∪{c}；//按项的个数归类(4)IF(k<‖c‖)THENk=‖c‖；//记下项目集包含的最多的个数(5)}(6)FOR(i=k；i>l；i--)(7)FORallitemsetsc∈Li(8)FORall(i-1)subsetssofc//分解所有(i-1)项目集(9)IF(sLi-1)THEN{//不包含在Li-1中(10)s.support=c.support；//支持度不变(11)Li-1=Li-1∪{s}；//添加到Li-1中(12)}(13)L=∪Li；//返回所有的Li Close算法最终需要通过频繁闭合项目集得到频繁项目集。首先对FC中的每个闭合项目集计算它的项目个数，把所有项目个数相同的归入相应的Li中。例如，闭合项目集{AB}，它的个数为2，则把它加入L2中。依此类推，将所有闭合项目集分配到相应的Li中，同时得到最大的个数记为k。然后从k开始，对每个Li中的所有项目集进行分解，找到它的所有的(i-1)项子集。对于每个子集，如果它不属于Li-1，则把它加入Li-1，直到i=2，就找到了所有的频繁项目集。为了能直观地了解Close算法的思想和具体技术，下面给出一个应用的实例。 【例3.6】示例数据库如表3-6所示，然后跟踪算法的执行过程(其中最小支持度为2)。(1)计算FCC1各个产生式的闭合集和支持度。首先得到FCC1的产生式：FCC1的产生式为{A}、{B}、{C}、{D)、{E}。然后计算闭合集。 例如，计算{A}的闭合。数据库中第一项{ABE}包含{A}，这时{A}的闭合首先得到{ABE}；第四项{ABD}包含{A}，所以取{ABD}和{ABE}的交集{AB}作为{A}的闭合集；第五项{AC}包含{A}，则取{AB}和{AC}的交集得到{A}作为{A}的闭合集；第7项是{AC}，交集为{A}；第8项{ABCE}与{A}的交集是{A}；第9项{ABC}与{A}的交集是{A}。这时到了最后一项，计算完成，得到{A}的闭合是{A}，并同时计算出{A}的支持度为6(可通过对出现的A的超集进行计数得到)。同样可以得到FCC1所有的闭合集与支持度(见表3-7)。 表3-6用于Close算法的示例数据库TIDItemsetTIDItemset1ABC6BC2BD7AC3BC8ABCE4ABD9ABC5AC 表3-7示例数据库中FCC1所有的闭合集与支持数GeneratorClosureSupport{A}{A}6{B}{B}7{C}{C}6{D}{BD}2{E}{ABE}2 (2)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC1。本例得到的FC1与FCC1相同。(3)利用FCl的Generator生成FCC2。先用Apriori相同的方法生成2项目集。然后将FC1中是FCC2中的某个候选项的子集的项选出来，记为Sp。如果FCC2的这一项是Sp的项的闭合的子集则删除，得到FCC2。对于本例，FC1自身连接后得到候选项为：{AB}、{AC}、{AD}、{AE}、{BC}、{BD}、{BE}、{CD}、{CE}和{DE}，均不含有非频繁子集。再利用FC1筛选：由于{AE}是子集{E}的闭合{ABE}的子集，{BE}是子集{E}的闭合{ABE}的子集，所以将这两项删除，得到的候选项FCC2={{AB},{AC},AD}，{BC},{BD}，{CD},{CE},{DE}}。 (4)计算各产生式的闭合集和支持度。由于FCC2非空，{CD}和{DE}的闭合为空，所以将它们从FCC2中删除，且得到各产生式的支持度。表3-8给出了所有非空2项目集对应的闭合和支持数。 表3-8所有非空2项集的闭合与支持数GeneratorClosureSupport{AB}{AB}4{AC}{AC}4{AD}{ABD}1{BC}{BC}4{BD}{BD}2{CE}{ABCE}1 (5)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC2，这时{AD}和{CE}的支持度为1，被删除。FC2={{AB},{AC},{BC},{BD}}。(6)利用FC2的Generator生成FCC3，并进行裁减。FC2连接后得到：{{ABC},{BCD}}，其中的{BCD}有非频繁子集{CD}，所以将这项删除，剩下为{ABC}，得到的候选项FCC3={ABC}。(7)FCC3不为空，计算各产生式的闭合集和支持度。ABC的闭合为{ABC}，支持度为2。(8)进行修剪。将支持度小于最小支持度的候选闭合项删除，得到FC3。对于本例，FCC3只有一项，支持度为2，保留。 (9)利用FC3生成FCC4。FCC4为空，算法结束。将所有的不重复的闭合加入到FC中，得到FC={{A},{B},{ABE},{BD},{C},{AB},{AC},{BC},{ABC}}。 以下步骤为生成频繁项目集。(10)统计项目集元素数。将所有的闭合项目集按元素个数统计，得到L3={{ABC},{ABE}}；L2={{AB},{AC},{BC},{BD}}；L1={{A}，{B}，{C}}。最大个数为3。 (11)将L3的频繁项分解。先分解{ABC}的所有2项子集为{AB}、{AC}和{BC}。这三项均在L2中；再分解{ABE}的所有2项子集为{AB}、{AE}和{BE}，后两项不存在，将它们加入到L2中，它们的支持度等于{ABE}的支持度。最后得L2={{BD},{AB},{AC},{BC},{AE},{BE}}。(12)将L2的频繁项分解。方法同上，得L1={{A},{B},{C},{D},{E}}。 3.7挖掘各种类型的关联规则3.7.1挖掘多层关联规则对于许多应用，由于数据的稀疏性，在低层或原始抽象层的数据项之间很难找出强关联规则；在较高的抽象层发现的强关联规则可能提供常识知识，而且，对一个用户代表常识的知识，对另一个用户可能是新颖的。因此，数据挖掘系统应当提供一种能力，能在多个抽象层挖掘关联规则，并有足够的灵活性，易于在不同的抽象空间转换。 【例3.7】挖掘多层关联规则。假定给定表3-9事务数据的任务相关集合，它是AllElectronics商店的销售数据，每个事务给出了购买的商品。商品的概念分层在图3[CD*2]6中给出。概念分层定义了由低层概念集到高层更一般概念的映射序列，可以通过将数据中的低层概念用概念分层中的高层概念(或祖先)替换，对数据进行泛化。图3-6的概念分层有5层，分别指层0～层4，从根节点all为层0(最一般的抽象层)开始。这里，层1包括computer、software、printer&camera、computeraccessory；层2包括laptopcomputer，deskopcomputer，officesoftware，antivirussoftware,…；而层3包括IBMdesktopcomputer,…，Microftofficesoftware，等等；层4是该分层结构的最具体的抽象层，由原始数据值组成。 表3-9任务相关数据TID购买的商品T100IBM-TinkPad-R40/2373,HP-photosmart-76600T200Microsoft-office-Professional-2003,Microsoft-Plus-Digital-mediaT300Logitrch-MX700-Cordless-Mouse,Fellowes-Wrist-RestT400Dell-Dimension-xps,Canon-PowerShot-S400T500IBM-ThinkPad-R40/P4M,Symantec-Norton-Anffvirus-2003 表3-9中的商品在图3-6概念分层的最低层。在这种原始层数据中很难发现有趣的购买模式。例如，如果“IBMTinkPadR40/P4M”和“SymantecNortonAnffvirus2003”每个都在很少一部分事务中出现，则可能很难找到涉及这些指定商品的强关联规则。很少有人同时购买它们，使得它不太可能是满足最小支持度的项集。然而，在这些商品的泛化抽象概念之间，如在“IBMlaptopcomputer”和“antivirussoftware”之间，可望更容易发现强关联。 图3-6AllElectronics计算机商品的概念分层 在多个抽象层上挖掘数据产生的关联规则称为多层关联规则。在支持度—置信度框架下，使用概念分层可以有效地挖掘多层关联规则。一般地，可以采用自顶向下策略，由概念层1开始，向下到较低的更特定的概念层，在每个概念层累积计数计算频繁项集，直到不能再找到频繁项集。对于每一层，可以使用发现频繁项集的任何算法，如Apriori或它的变形。这种方法有许多变形在下面介绍，其中每种变形都涉及以稍微不同的方式“使用”支持度阈值。这些变形用图3-7和图3-8解释，其中节点指出项或项集已被考察，粗边框的节点表示已考察的项或项集是频繁的。 图3-7具有一致支持度的多层挖掘 图3-8具有递减支持度的多层挖掘 (1)对于所有层使用一致的最小支持度(称做一致支持度)：在每一抽象层挖掘时使用相同的最小支持度阈值。例如，在图3-7中，整个使用最小支持度阈值5％（例如，由“computer”向下挖掘到“laptopcomputer”)。“computer”和“laptopcomputer”都是频繁的，但“desktopcomputer”不是。使用一致的最小支持度阈值时，搜索过程被简化，用户只需要指定一个最小支持度阈值。根据祖先是其后代的超集的知识，可以采用类似于Apriori的优化策略，搜索时避免考察其祖先不满足最小支持度的项。然而，一致支持度方法有一些困难。较低抽象层的项不大可能像较高抽象层的项出现得那么频繁。如果最小支持度阈值设置太高，可能错失出现在较低抽象层中有意义的关联规则。如果阈值设置太低，可能会产生出现在较高抽象层的无意义的关联规则。 (2)在较低层使用递减的最小支持度(称做递减支持度)：每个抽象层有自己的最小支持度阈值。抽象层越低，对应的阈值越小。例如，在图3-8中，层1和层2的最小支持度阈值分别为5％和3％。用这种方法，“computer”、“laptopcomputer”和“desktopcomputer”都是频繁的。 (3)使用基于项或基于分组的最小支持度(称做基于分组的支持度)：由于用户或专家通常清楚哪些分组比其他分组更重要，在挖掘多层规则时，有时更希望建立用户指定的基于项或基于分组的最小支持度阈值。例如，用户可以根据产品价格或根据感兴趣的商品设置最小支持度阈值。如对laptopcomputers和flashdrives设置特别低的支持度阈值，以便特别关注包含这类商品的关联模式。挖掘多层关联规则的一种严重的副作用是由于项之间的“祖先”关系，可能产生一些多抽象层之间的冗余规则。例如，考虑下面的规则，其中，根据图3-6的概念分层，“laptopcomputer”是“IBMlaptopcomputer”的祖先，而X是变量，代表在AllElectronics事务中购买商品的顾客。 (]buys(X,“laptopcomputer”)buys(X，“HPprinter”)［support=8%,confidence=70%］(3.3)buys(X,“IBMlaptopcomputer”)buys(X，“HPprinter”)［support=2%,confidence=72%］(3.4) 规则R1是规则R2的祖先，如果R1能够通过将R2中的项用它在概念分层中的祖先替换得到。例如，规则(3.3)是规则(3.4)的祖先，因为“laptopcomputer”是“IBMlaptopcomputer”的祖先。根据这个定义，规则(3.4)被认为是冗余的，如果根据该规则的祖先，它的支持度和置信度都接近于“期望”值。例如，假定规则(3.3)具有70％的置信度和8％的支持度，并且大约1/4的“laptopcomputer”销售的是“IBMlaptopcomputer”。可以期望规则(3.4)具有大约70％的置信度(由于所有的“IBMlaptopcomputer”样本也是“laptopcomputer”样本)和2％(即，8％×1/4)的支持度。如果确实是这种情况，则规则(3.4)不是有趣的，因为它不提供任何附加的信息，并且它的一般性不如规则(3.3)。 3.7.2多维关联规则挖掘前面研究了蕴涵单个谓词，即谓词buys的关联规则。例如，在挖掘AllEleclronics数据库时，可能发现布尔关联规则：buys(X，“digitalcamera”)buys(X，“HPprinter”)(3.5)沿用多维数据库使用的术语，把每个不同的谓词称做维。这样，称规则(3.5)为单维(SingleDimensional)或维内关联规则(IntradimensionalAssociationRule)，因为它们包含单个不同谓词(如buys)的多次出现(即谓词在规则中出现多次)。这种规则通常从事务数据中挖掘。 然而，假定不使用事务数据库，销售和相关数据存放在关系数据库或数据仓库中。根据定义，这种存储是多维的。例如，在销售事务中除记录购买的商品之外，关系数据库可能记录与商品有关的其他属性，如购买数量或价格，或销售的分店地址。另外，关于购物顾客的信息，如顾客的年龄、职业、信誉度、收入和地址等也可能存储。将每个数据库属性或数据仓库的维看做一个谓词，可以挖掘包含多谓词的关联规则，如(age(X,“20…29”)∧occupation(X,“student”)buys(X,“laptop”)(3.6) 涉及两个或多个维或谓词的关联规则称为多维关联规则(MultidimensionalAssociationrule)。规则(3.6)包含三个谓词(age，occupation和buys)，每个谓词在规则中仅出现一次。因此，称它具有不重复谓词。具有不重复谓词的多维关联规则称做维间关联规则(InterdimensionalAssociationRule)。也可以挖掘具有重复谓词的多维关联规则，它包含某些谓词的多次出现。这种规则称做混合维关联规则(HybridDimensionalAssociationRule)。这种规则的一个例子如下，其中谓词buys是重复的：(age(X,“20…29”)∧buys(X,“laptop”)buys(X，“HPprinter”)(3.7) 注意，数据库属性可能是分类的或量化的。分类(Categorical)属性具有有限个可能值，值之间无序(例如occupation，brand，color)。分类属性也称标称(Nominal)属性，因为它们的值是“事物的名称”。量化(Quantitative)属性是数值的，并在值之间有蕴涵的序(例如age，income，price)。挖掘多维关联规则的技术可以根据量化属性的处理分为两种基本方法。 第一种方法使用预定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行。例如，可以使用income的概念分层，用区间标记“0…20K”、“21…30K”、“31…40K”等替换属性原来的数值。这里，离散化是静态的和预先确定的。离散化的数值属性具有区间标记，可以像分类属性一样处理(其中，每个区间看做一类)。这种方法称为使用量化属性的静态离散化挖掘多维关联规则。第二种方法，根据数据的分布将量化属性离散化或聚类到“箱”。这些箱可能在挖掘过程中进一步组合。离散化的过程是动态的，以满足某种挖掘标准，如最大化所挖掘的规则的置信度。由于该策略将数值属性的值处理成量，而不是预定义的区间或类，由这种方法挖掘的关联规则称为(动态)量化关联规则。 下面逐个研究这些挖掘多维关联规则的方法。为简明起见，将讨论限于维间关联规则。1.使用量化属性的静态离散化挖掘多维关联规则在这种情况下，使用预定义的概念分层或数据离散化技术，在挖掘之前将量化属性离散化，其中数值属性的值用区间标号替换。如果需要，分类属性还可以泛化到较高的概念层。如果任务相关的结果数据存放在关系表中，则前面讨论过的任何频繁项集挖掘算法都容易修改，以找出所有的频繁谓词集，而不是频繁项集。特殊地，将每个属性-值对看做一个项集，需要搜索所有的相关属性，而不是仅搜索一个属性(如buys)。 作为选择，变换后的多维数据可以用来构造数据立方体。数据立方体非常适合挖掘多维关联规则，它们在多维空间存储聚集信息(如计数)，这对于计算多维关联规则的支持度和置信度是很重要的。 2.挖掘量化关联规则量化关联规则是多维关联规则，其中在挖掘过程中数值属性动态离散化，以满足某种挖掘标准，如最大化所挖掘的规则的置信度或紧凑性。如何挖掘左部有两个量化属性，右部有一个分类属性的量化关联规则,即Aquan1∧Aquan2Acat 其中，Aquan1和Aquan2对量化属性的区间(其中区间动态地确定)测试，Acat测试任务相关数据的分类属性。这种规则称做2维量化关联规则，因为它们包含两个量化维。例如，假定关心像顾客的年龄和收入这样的量化属性对顾客喜欢买的电视机类型(如高分辨率电视，即HTV)之间的关联关系，如下所示即是这种2-D量化关联规则的一个例子：(Age(X,“30…39”)∧income(X,“42k…48k”)buys(X,“HDTV”)(3.8)该方法将量化属性映射到满足给定分类属性条件的2-D元组栅格上，然后，搜索栅格发现点簇，由此产生关联规则。 3.8相关分析3.8.1强关联规则不一定有趣的例子规则是否有趣可以主观或客观地评估。最终，只有用户能够确定规则是否有趣，并且这种判断是主观的，因用户而异。然而，根据数据“背后”的统计，客观兴趣度度量可以用于清除无趣的规则，而不向用户提供。 【例3.8】一个误导的“强”关联规则。假定对分析涉及购买计算机游戏和录像的AllElectronics的事务感兴趣。设game表示包含计算机游戏的事务，而video表示包含录像的事务。在所分析的10000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务同时包含计算机游戏和录像。假定发现关联规则的数据挖掘程序对该数据运行，使用最小支持度为30％，最小置信度为60％，将发现下面的关联规则：(buys(X，“computergames”)buys(X，“videos”)［support=40％，confidence=66％］(3.9) 规则(3.9)是强关联规则，因而提出报告，因为其支持度的值为4000/10000=40％，置信度的值为4000/6000=66％，分别满足最小支持度和最小置信度阈值。然而，规则(3.9)是误导，因购买录像的概率是75％，比66％还大。事实上，计算机游戏和录像是负相关的，因为买一种实际上减少了买另一种的可能性。不完全理解这种现象的话，容易根据规则(3.9)作出不明智的商务决定。上面的例子也表明规则AB的置信度有一定的欺骗性，它只是给定项集A、项集B的条件概率的估计。它并不度量A和B之间相关和蕴涵的实际强度。因此，寻求支持度-置信度框架的替代，对挖掘有趣的数据联系可能是有用的。 3.8.2从关联分析到相关分析支持度和置信度度量不足以过滤掉无趣的关联规则。为了解决这个问题，可以使用相关度量来扩充关联规则的支持度-置信度框架。有如下形式的相关规则：AB［support,confidence,correlation］(3.10)也就是说，相关规则不仅用支持度和置信度度量，而且还用项集A和B之间的相关度量。有许多不同的相关度量可供选择。 1.提升度提升度(lift)是一种简单的相关度量，有定义如下：如果P(A∪B)=P(A)P(B)，项集A的出现独立于项集B的出现；否则作为事件项集A和B是依赖的(dependent)和相关的(correlated)。这个定义容易推广到多于两个项集。A和B的出现之间的提升度可以通过计算下式得到：(3.11)如果式(3.11)的值小于1，则A的出现和B的出现是负相关的。如果结果值大干1，则A和B是正相关的，意味着一个的出现蕴涵另一个的出现。如果结果值等于1，则A和B是独立的，它们之间没有相关性。 式(3.11)等价于P(A|B)/P(B)或conf(AB)/sup(B)，也称关联(或相关)规则AB的提升度。换言之，它评估一个的出现“提升”另一个出现的程度。例如，如果A对应于计算机游戏的销售，B对应于录像的销售，则给定当前行情，游戏的销售将录像的销售增加或“提升”程度因子。 【例3.9】使用提升度的相关分析。为了帮助过滤掉从例3.7的数据得到的形如AB的误导“强”关联，需要研究两个项集A和B如何相关。设表示例3.7中不包含计算机游戏的事务，表示不包含录像的事务。事务可以汇总在一个相依表(contingencytable)中，如表3-10所示。由该表可以看出，购买计算机游戏的概率P({game})=0.60，购买录像的概率P({video})=0.75，而购买二者的概率P({game,video})=0.40。根据式(3.11)，得规则(3.9)的提升度为 P({game,video})/P({game})/P({video})=0.40/0.75/0.60=0.89由于该值比1小，{game}和{video}的出现之间存在负相关，分子是顾客购买二者的可能性，而分母是两个购买是完全独立的可能性。这种负相关不能由支持度－置信度框架识别。 表3-10汇总关于购买计算机游戏和录像事物的2×2相依表 2.检验对于分类(离散)数据，两个属性A和B之间的相关联系可以通过(卡方)检验发现。设A有c个不同值a1,a2,…,ac；B有r个不同值b1,b2,…,br。A和B描述的数据元组可以用一个相依表显示，其中A的c个值构成列，B的r个值构成行。令(Ai,Bj)表示属性A取值ai、属性B取值bj的事件，即(A=ai，B=bj)。每个可能的(Ai，Bj)联合事件都在表中有自己的单元(或位置)。值(又称皮尔逊统计量)可以按式(3.12)计算(3.12) 其中，Oij是联合事件(Ai，Bj)的观测频度(即实际计数)，而eij是联合事件(Ai，Bj)的期望频度，可以用下式计算:(3.12)其中，N是数据元组的个数，count(A=ai)是A具有ai值的元组个数，而count(B=bi)是B具有值bi的元组个数。式(3.12)中的和在所有r×c个单元上计算。注意，对χ2值贡献最大的单元是其实际计数与期望计数很不相同的单元。 χ2统计检验假设A和B是独立的。检验基于显著水平，具有(r-1)×(c-1)自由度。用下面的例子解释该统计量的使用。如果可以拒绝该假设，则说A和B是统计相关的或关联的。【例3.10】使用χ2值进行相关分析。为了使用χ2值计算相关，需要相依表每个位置上的观测值和期望值(显示在括号内)，如表3-11所示。 表3-11表3-10的2×2相依表 使用式(3.13)，可以计算每一单元(Ai，Bj)的期望频度。例如，单元(game,video)的期望频度是由表3-11得χ2值的计算过程如下： 对于2×2的表，自由度为(2-1)×(2-1)=1。对于自由度为1，在0.001的置信水平，拒绝假设的χ2值为10.828(取自χ2分布的上百分点表)。由于χ2的值大于10.828，并且位置(game，video)上的观测值等于4000，小于期望值4500，因此购买游戏与购买录像是负相关的，这与提升度度量分析得到的结果一致。 3.全置信度给定项集X={i1,i2,…,ik}，X的全置信度定义为：(3.14)其中，是X中所有项的最大(单个)项支持度，因此称做项集X的最大项支持度。X的全置信度是规则集的最小置信度，其中ij∈X。 4.余弦度量给定两个项集A和B，A和B的余弦度量定义为(3.15)余弦度量可以看做调和的提升度度量，两个公式类似，不同之处在于余弦度量对A和B的概率乘积取平方根。这是一个重要区别，因为通过取平方根，余弦值仅受A、B和A∪B的支持度影响，而不受事务总个数的影响。 概括地说，仅使用支持度和置信度度量来挖掘关联导致产生大量规则，其中大部分用户是不感兴趣的。可以用相关度量来扩展支持度-置信度框架，导致相关规则的挖掘。附加的度量显著地减少了所产生的规则数量，并且导致更有意义的规则的发现。然而，一些研究案例表明不存在对所有情况都能很好处理的单个相关度量。除了本节介绍的相关度量外，相关文献中还研究了许多其他兴趣度量。不幸的是，大部分度量都不具有零不变性。由于大型数据集常常具有许多零事务，因此在做相关分析选择合适的兴趣度量时，考虑零不变性是很重要的。分析表明，对于大型应用，全置信度和余弦都是很好的相关度量，尽管当检测结果不是十分确定时，使用附加的检测(如提升度)加以补充是明智的。 3.9基于约束的关联规则数据挖掘过程可以从给定的数据集中发现数以千计的规则，其中大部分规则与用户不相关或用户不感兴趣。通常，用户具有很好的判断能力，知道沿什么“方向”挖掘可能导致有趣的模式，知道他们想要发现什么“形式”的模式或规则。这样，一种好的启发式方法是以用户的直觉或期望作为限制搜索空间的约束条件。这种策略称做基于约束的挖掘(constraintbasedmining)。这些约束包括： (1)知识类型约束：指定要挖掘的知识类型，如关联规则或相关规则。(2)数据约束：指定任务相关的数据集。(3)维/层约束：指定挖掘所期望的数据维(或属性)，或概念分层结构的层次。(4)兴趣度约束：指定规则兴趣度统计度量阈值，如支持度、置信度和相关。(5)规则约束：指定要挖掘的规则形式。这种约束可以用元规则(规则模板)表示，出现在规则前件或后件中谓词的最大或最小个数，或属性、属性值和/或聚集之间的联系。 以上约束可以用高级数据挖掘查询语言和用户界面说明。此处，讨论使用规则约束对挖掘任务聚焦。这种基于约束的挖掘形式允许用户说明他们想要挖掘的规则，因此使得数据挖掘过程更有功效。此外，可以使用复杂的挖掘查询优化程序利用用户指定的约束，从而使得挖掘过程的效率更高。为了简化讨论，假定用户正搜索关联规则，采用支持度-置信度-兴趣度框架挖掘相关规则。 3.9.1关联规则的元规则制导挖掘元规则使用用户感兴趣的规则的语法形式。规则的形式可以作为约束，帮助提高挖掘过程的效率。元规则可以根据分析者的经验、期望或对数据的直觉或者根据数据库模式自动产生。 【例3.11】元规则制导的挖掘。假定作为AllElectronics的市场分析员，你已经访问了描述顾客的数据(如，顾客的年龄、地址和信誉等级等)以及顾客事务的列表。你对找出顾客的特点和顾客购买的商品之间的关联感兴趣。然而，不是要找出反映这种联系的所有关联规则，你只对确定两种什么样的顾客特点促进办公软件的销售特别感兴趣。可以使用一个元规则来说明你感兴趣的规则形式的信息。这种元规则的一个例子是P1(X,Y)∧P2(X,W)buys(X,“officesoftware”)(3.16)其中，P1和P2是谓词变量，在挖掘过程中为给定数据库的属性；X是变量，代表顾客；Y和W分别取赋给P1和P2的属性值。在典型情况下，用户要说明一个例示P1和P2需考虑的属性列表；否则，将使用默认的属性集。 一般地，元规则形成一个关于用户感兴趣探查或证实的假定。然后，数据挖掘系统可以搜索与给定元规则匹配的规则。例如，规则(3.17)匹配或遵守元规则(3.16)。age(X，“30…39”)∧income(X,“41K…60K”)buys(X,“officesoftware”)(3.17)假设希望挖掘维间关联规则，如上例所示。元规则是形如P1∧P2∧…∧PlQ1∧Q2∧…∧Qr(3.18)的规则模板。其中Pi(i=1，2，…，l)和Qi(i=1，2，…，r)是例示谓词或谓词变量。设元规则中谓词的个数为p=l+r。为找出满足该模板的维间关联规则，需要找出所有的频繁P谓词集Lp，还必须有Lp中的l谓词子集的支持度或计数，以便计算由Lp导出的规则的置信度。 3.9.2规则约束制导的挖掘规则约束说明所挖掘的规则中的变量的期望的集合/子集联系、变量的常量初始化和聚集函数。用户通常使用他们的应用或数据的知识来说明挖掘任务的规则约束。这些规则约束可以与元规则制导挖掘一起使用，作为它的替代。本节考察规则约束，看看怎样使用它们，使得挖掘过程更有效。研究一个例子，其中规则约束用于挖掘混合维关联规则。 【例3.12】进一步考察规则约束制导的挖掘。假定AllElectronics有一个销售多维数据库，包含以下相互关联的关系：sales(customer_name，item_name，TID)lives_in(customer_name，region，city)item(item_name，group，price)transaction(TID，day，month，year)其中lives_in、itern和transation是三个维表，通过三个码customer_name、item_name[JP]和TID分别连接到事实表sales。 关联挖掘查询的目的是“找出2004年对于Chicago的顾客，什么样的便宜商品(价格和低于100美元)能够促进同类贵商品(最低价为500美元)的销售?”可以用DMQL数据挖掘查询语言表达如下，为方便讨论，查询的每一行已经编号。(1)mineassociationsas(2)lives_in(C，-，“Chicago”)∧sales+(C，?[KG-*2]{I},{S})sales+(C，?{J}，{T})(3)fromsales(4)whereS.year=2004andT.year=2004andI.group=J.group(5)groupbyC，I.group(6)havingsum(I.price)<100andmin(J.price)≥500(7)withsupportthreshold=1％(8)withconfidencethreshold=50％ 行(1)是知识类型约束，说明要发现的关联模式；行(2)说明了元规则。数据约束在元规则的“lives_in(C，-，“Chicago”)”部分指定住在Chicago的所有顾客，并在行(3)指出只有事实表sales需要显式引用。在这个多维数据库中，变量的引用被简化。例如，“S.year=2004”等价于SQL语句“fromsalesS，transactionTwhereS.TID=T.TIDandT.year=2004”。使用了所有三维(lives_in，item和transaction)。层约束如下：对于lives_in，只考虑customer_name，并且不涉及region，并且选择中只使用city=“Chicago”；对于item，考虑item_name和group层，因为它们在查询中使用；对于transaction，只考虑TID，因为day和month未引用，而year只在选择中使用。 规则约束包括where(行（4）)和having(行（6）)子句部分，如“S．year=2004”、“T．year=[JP]2004”、“I.group=J.group”、“sum(I.price)≤100”和“min(J.price)≥500”。最后，行(7)和行(8)说明两个兴趣度约束(即阈值)：1％的最小支持度和50％的最小置信度。对于频繁项集挖掘，规则约束可以分为五类：反单调的、单调的、简洁的、可转变的、不可转变的。对于每一类，将使用一个例子展示它的特性，并解释如何将这类约束用在挖掘过程中。 (1)反单调性约束。考虑例3.12的规则约束“sum(I.price)≤100”。假定使用Apriori框架，在每次迭代k，探查长度为k的项集。如果一个项集中项的价格和不小于100，则该项集可以从搜索空间中剪枝，因为向该项集中进一步添加项将会使它更贵，因此不可能满足约束。换句话说，如果一个项集不满足该规则约束，它的任何超集也不可能满足该规则约束。如果一个规则约束具有这种性质，则称它是反单调的。根据反单调规则约束剪枝可以用于类Apriori算法的每一次迭代，以帮助提高整个挖掘过程的效率，而保证数据挖掘任务的完全性。 反单调约束的其他例子包括“min(J.price)≥500”和“count(I)≤10”等。任何违反这些约束的项集都可以丢弃，因为向这种项集中添加更多的项不可能满足约束。注意，诸如“avg(I.price)≤100”的约束不是反单调的。对于一个不满足该约束的给定项集，通过添加一些(便宜的)项得到的超集可能满足该约束。因此，将这种约束推进到挖掘过程之中，将不保证数据挖掘任务的完全性。 第二类约束是单调的。如果例3.12中的规则约束是“sum(I.price)≥100”，则基于约束的处理方法将很不相同。如果项集I满足该约束，即集合中的价格之和不小于100，进一步添加更多的项到将增加开销，并且总是满足该约束。因此，对项集I进一步检查该约束是冗余的。换言之，如果一个项集满足这个规则约束，那么它的所有超集也满足。如果一个规则约束具有这种性质，则称它是单调的(monotonic)。类似的规则单调约束包括“min(I.price)≤10”，“count(I)≥10”等。 第三类是简洁性约束。对于这类约束，可以枚举并且仅仅枚举确保满足该约束的集合。也就是说，如果一个规则约束是简洁的(Succinct)，甚至可以在支持计数开始之前直接精确地产生满足它的集合。这避免了产生-测试方式的过大开销。换言之，这种约束是计数前可剪枝的。例如，例3.10中的约束“min(J.price)≥500”是简洁的，因为能够明确无误地产生满足该约束的所有项集。具体地说，这种集合必须至少包含一项，其价格不低于500美元。它是这种形式：S1∪S2，其中S1≠Φ是集合中价格不低于500美元的所有项的子集；而S2可能为空，是集合中价格不超过500美元的所有项的子集。因为有一个精确“公式”产生满足简捷约束的所有集合，在挖掘过程中不必迭代地检验规则约束。 第四类约束是可转变的约束(ConvertibleConstraint)。如果项集中的项以特定的次序安排，则对于频繁项集挖掘过程，约束可能成为单调的或反单调的。例如，约束“avg(I.price)≤100”既不是反单调的，也不是单调的。然而，如果事务中的项以价格递增顺序添加到项集中，则该约束就变成了反单调的，因为如果项集I违反了该约束(即平均价格大于100美元)，则更贵的商品进一步添加到该项集中不会使它满足该约束。类似地，如果事务中的项以价格递减顺序添加到项集中，则该约束就变成了单调的，因为如果项集I满足该约束(即平均价格不超过100美元)，添加更便宜的商品到当前项集将使平均价格不大于100美元。 3.10矢量空间数据库中关联规则的挖掘3.10.1问题的提出在当前空间数据挖掘和知识发现领域，存在着如下倾向：(1)忽视了GIS在空间知识发现过程中的作用。GIS是空间数据采集、管理、处理、分析、建模和可视化的工具。空间数据处理、空间分析是GIS特有的功能。尽管人们研究和建立空间数据库的初衷与空间数据挖掘的目标截然不同，但是在空间知识发现的过程中，同样需要GIS和空间数据库技术的支持。 (2)大多数空间据挖掘算法是一般数据挖掘算法直接移植过来的，未考虑空间数据存储、处理及数据本身的特点。不同于关系数据库，空间数据带有拓扑、方向和距离等空间信息，通常用复杂的、多维的空间索引结构组织数据，有特有的空间数据访问方法。目前大多GIS空间数据库以矢量和栅格两种数据模型及相应的数据结构来组织和管理空间数据。关系型数据采掘的算法往往假定数据是独立的，而在空间数据库中一个对象可能会受其邻近若干个对象的影响，数据之间是相互依赖。因此，必须扩展传统的数据采掘技术，以便更好地分析复杂的空间现象和空间对象。 关联规则是KDD研究中的一个重要的研究课题，是由R.Agrawal等人提出的，目的是要在交易数据库中发现各项目之间的关系。最著名的算法是R.Agrawal等人提出的Apriori算法。其他大多数算法都是在该算法的基础上加以改进或扩展，基本框架没有变化。它隐含如下前提假设：(1)数据库中各项目具有相同的性质和作用，即重要性相同。(2)数据库中各项目的分布是均匀的。(3)数据库中每个事务的代表性和重要性是相同的。 (1)、(2)两种假设国内外已展开了相应的研究工作。在矢量空间数据库中，把空间对象抽象为点、线和多边形这三种类型，每个空间对象所代表的空间区域或空间范围是不同的，假设条件(3)与此不符。本文以矢量空间数据库为数据挖掘对象，以GIS的空间数据处理和空间分析为工具，首先探讨了空间知识发现过程中的数据选择、预处理和转换方法；其次提出矢量空间数据库中关联规则的挖掘算法；最后以某一地区生态空间数据库为例，挖掘与土壤侵蚀相关的关联规则。 3.10.2面向空间数据挖掘的数据准备1.矢量空间数据的组织GIS管理和存储空间数据的方法是将它们抽象为带有分类属性的几何对象，以层(Layer)为概念组织、存储、修改和显示它们。空间数据组织有两个前提条件：(1)同一层中的对象具有相同的空间维数，如：点、线、面的一种。(2)GIS层中的对象一般都是同一地形或地物类型，整个层构成了具有某一地理性质的专题地图。 以Arc/info基于矢量数据模型的系统为例，为了将空间数据存入计算机，首先，从逻辑上将空间数据抽象为不同的专题或层，如：土地利用、地形、道路、居民区、土壤单元，森林分布等，一个专题层包含区域内地理要素的位置和属性数据。其次，将一个专题层的地理要素或实体分解为点、线、面目标，每个目标的数据由定位数据、属性数据和拓扑数据组成。图3-9中的(a)和(b)就是由属性1和属性2组成的两个面要素图层，其中的表(a)和表(b)是与其对应的属性表。 图3-9空间迭加运算 2.面向关联规则挖掘的空间数据准备空间数据挖掘和知识发现可分为三个阶段：数据准备、数据挖掘、结果的评价与表达。数据的准备是空间数据挖掘的基础，它关系到空间数据挖掘能否实现和效率，包括数据的选择、预处理和变换等步骤。面向关联规则挖掘的空间数据准备步骤如下：(1)数据选择。根据数据挖掘的目标和背景知识，选择感兴趣的对象。如要挖掘地理要素1与地理要素2间的关联规则，在空间数据库中就要选择要素1图层和要素2图层及其相应的属性表。 (2)属性值的离散化。空间数据库中关联规则的挖掘要求属性值使用(如整型、字符串型、枚举型)数据表达。如果某些属性的值域为连续值(如浮点型数表达)，则在数据挖掘前必须进行离散化处理。(3)对要素层进行空间叠加。利用GIS的空间叠加功能，将要素1图层和要素2图层进行叠加，得到综合图层及其相应的综合属性表。图3-9中的表(c)即综合属性表是关联规则挖掘的目标数据。 3.10.3矢量空间数据库中关联规则挖掘1.关联规则定义假设I={i1,i2,…,im}是项的集合。设任务相关的数据D是数据库中事务的集合，其中每个事务T是项的集合，使得。每个事务有一个标识符，称为TID。设A是一个项集，事务T包含A当且仅当，关联规则是形如A=>B的蕴含式，其中,，并且A∩B=Φ。规则A=>B在事务集D中成立，具有支持度S，其中S是D中包含A∪B的事务的百分比，亦概率P(A∪B)。规则A=>B在事务集D中具有置信度C，如果事务集D中包含A的事务同时也包含B的百分比，亦条件概率P(A|B)。即 (3.19)针对事务数据库，为了便于计算，(3.19)式可改写为：(3.20)式中：num(A∪B)——事务数据库中包含项集A∪B的记录数；num(A)——事务数据库中包含项集A的记录数；num(true)——事务数据库中的记录总数。 2.矢量空间数据库中关联规则的挖掘方法1)支持度(support)和置信度(confidence)的定义对于元组的重要性和代表性不同的事务数据库，如：矢量空间数据库,式(3.20)显然不再适用，可以为每一个元组赋以相应的权重。这样式(3.20)可写为(3.21) 式中：——满足项集A的一个一维数组；——满足项集B的一个一维数组；W——数据库D中各元组权重数组；——点乘符号。两个维数和元素个数相同的数组的点乘等于其对应元素的乘积的一个数组；sum（*）——数组元素的求和函数。和可按(3.22)、(3.23)式进行计算： (3.23)(3.24)式中的n为数据库中元组的个数或总记录数。 2)关联规则的挖掘关联规则的挖掘就是在综合图层属性表中找出具有用户给定的最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的关联规则。关联规则挖掘问题可分解为以下两个子问题:(1)找出综合图层属性表中所有大于等于用户指定最小支持度(minsup)的项目集。具有最小支持度的项目集称为频繁项目集。(2)利用频繁项目集生成所需要的关联规则。对每一个频繁项目集A，找到A的所有非空子集a，如果比率support(A)/support(a)≥min_conf，就生成关联规则a=>(A-a)。support(A)/support(a)，即规则a=>(A-a)的置信度。 3.10.4应用实例由于地表特征是由多种因素综合影响的结果。“环境单元”即地理空间上的一片区域，该区域的状态或发展趋势是由地形、地质、土壤、植被、水文等自然因子和社会经济因子综合作用的结果。黄河皇埔川流域是我国及世界上罕见的多沙、粗沙、强烈水土流失的区域。本文采用该流域的地形、气候和侵蚀强度等生态环境因子数据，选用ArcView3.2地理信息软件作为空间数据库管理软件。首先将它们的属性值进行离散化(如表3-12所示)，分别作为一个图层输入空数据库中。再使用GIS的空间叠加功能进行，将坡度、沟密度、切割裂度、降水、气温、风速和侵蚀强度图层进行空间叠加，得到综合图层和综合属性表，共664个多边形，亦就是664个记录。 将生态环境空间数据库中综合属性表输出为*.txt文件。按照矢量空间数据库中关联规则的挖掘方法，编写相应的Matlab程序，并读取*.txt文件作为数据源。规则的支持度(support)和置信度(confidence)按照式(3.21)计算，权重代入各个多边形的面积。在min_sup=7%和min_conf=65%约束下，关联规则挖掘结果见表3-13、表3-14。表中的第三列、第四列括号内的数字为不考虑多边形权重的支持度和置信度。 表3-14的规则Rule2：风速(2)and沟密度(2)==>侵蚀强度(3)(12.8%，77.0%)表示占该区域面积的12.8%、风速为第二等级的子区域中有77.0%面积的侵蚀强度为3级。这一规则可以通过GIS进行可视化表达：满足条件风速＝2and沟密度＝2and侵蚀强度＝3的多边形如图3-10所示(深色区域)。满足条件风速＝2and沟密度＝2多边形如图3-11所示(浅色区域)，它占整个区域的面积的百分比即为该关联规则的支持度。在满足条件风速＝2and沟密度＝2的区域中，满足条件侵蚀强度＝3的子区域所占该区域面积百分比即为该关联规则的置信度，即深色区域在浅色区域中所占百分比。 表3-12生态因子属性值离散化 表3-13二维关联规则表3-14三维关联规则 图3-10风速=2and沟谷密度=2and侵蚀强 图3-11风速=2and沟谷密度=2区域
