数据挖掘导论-ch7

关联分析:高级概念第7章关联分析:高级概念关联分析处理事务数据RulesDiscovered:{Diaper}--{Beer}TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke处理分类属性我们可能发现关于因特网用户特征的有趣信息:{网上购物=是}{关注隐私=是}许多应用包含对称二元属性和标称属性。表7-1显示的因特网调查数据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上购物和关注隐私；还包括标称属性，如文化程度和州。处理分类属性为了提取这样的模式，我们需要将标称属性和对称二元属性转换成“项”，使得已有的关联规则挖掘算法可以使用。这种类型的变化可以通过为每个不同的属性-值对创建一个新的项来实现。–例如:标称属性文化程度可以用三个二元项取代文化程度=大学文化程度=研究生文化程度=高中类似的，对称二元属性性别可以转换成一对二元项：性别=男、性别=女。处理分类属性将关联分析用于二元化后的数据时，需要考虑如下问题。–(1)有些属性值可能不够频繁，不能成为频繁模式的一部分。如：州名。–解决办法：将相关的属性值分组，形成少数类别。例如，每个州名都可以用对应的地理区域取代。例如：分别用中西部、太平洋西北部、西南部和东海岸取代。处理分类属性将关联分析用于二元化后的数据时，需要考虑如下问题。–(2)某些属性值的频率可能比其他属性高很多。如：假定85%的被调查人都有家庭计算机，如果为每个频繁出现在数据中的属性值创建一个二元项，我们可能产生许多冗余模式。{家庭计算机=是，网上购物=是}{关注隐私=是}–解决办法：使用处理具有宽支持度的极差数据集的技术。处理分类属性将关联分析用于二元化后的数据时，需要考虑如下问题。–(3)计算时间可能增加，特别是当新创建的项变成频繁项时。因为会产生更多的候选项集。–解决办法：避免产生包含多个来自同一个属性的项的候选项集。例如：不必产生诸如{州=X，州=Y，…}的候选项集，因为该项集支持度为零。处理连续属性因特网调查数据可能还包含连续属性，如表7-3所示。挖掘连续属性可能揭示数据的内在联系，如“年收入超过120k的用户属于45-60年龄组”或“拥有超过3个email帐号并且每周上网超过15小时的用户通常关注个人隐私”:包含连续属性的关联规则通常称作量化关联规则（quantiativeassociationrule）。对连续数据进行关联分析的方法:–基于离散化的方法–非离散化方法–基于统计学的方法基于离散化的方法离散化是处理连续属性最常用的方法。这种方法将连续属性的邻近值分组，形成有限个区间。例如：年龄属性可以划分为如下区间：[12,16),[16,20),[20,24),…,[56,60)离散化技术：等宽、等频、聚类表7-4显示了离散化和二元化后的因特网调查数据。属性离散化的一个关键在于划分每个属性的区间个数和宽度。然而，确定正确的区间是困难的。如果支持度阈值=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.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]）之间的关联。一种方法是将数据变换成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适配器）可能没有足够的支持度，但是，作为概念分层结构中它们的父母结点（如：便携机配件）具有较高支持度。–（2）在较低层发现的规则倾向于过于特殊，可能不如较高层的规则令人感兴趣。（如：脱脂牛奶普通面包，脱脂牛奶白面包，等过于特殊）实现概念分层的方法–每个事务t用它的扩展事务t’取代，其中，t’包含t中所有项和它们的对应祖先。如：事务{DVD，普通面包}可以扩展为{DVD，普通面包，家电，电子产品，面包，食品}–然后对扩展的数据库使用如Apriori等已有的算法来发现跨越多个概念层的规则。概念分层主要缺点–（1）处于较高层的项比处于较低层的项趋向于具有较高的支持度计数。–（2）概念分层的引入增加了关联分析的计算时间。–（3）概念分层的引入可能产生冗余规则。规则XY是冗余的，如果存在一个更一般的规则X’Y’，其中X‘是X的祖先，Y’是Y的祖先，并且两个规则具有非常相似的置信度。例如：{面包}{牛奶}，{白面包}{脱脂牛奶}序列模式购物篮数据常常包含关于商品何时被顾客购买的时间信息。可以使用这种信息，将顾客在一段时间内的购物拼接成事务序列。然而，迄今为止所讨论的关联模式概念都只强调同时出现关系，而忽略数据中的序列信息。对于识别动态系统的重现特征，或预测特定事件的未来发生，序列信息可能是非常有价值的。序列模式将与对象A有关的所有事件按时间增序排列，就得到A的一个序列（sequence）101520253035235611TimelineObjectA:ObjectB:ObjectC:4562781216178ObjectTimestampEventsA102,3,5A206,1A231B114,5,6B172B217,8,1,2B281,6C141,8,7SequenceDatabase:一般地，序列是元素（element）的有序列表，可以记作s=e1e2e3,…,en,其中每个ej是一个或多个事件的集族，即ej={i1，i2，…，ik}。SequenceE1E2E1E3E2E3E4E2Element(Transaction)Event(Item)序列数据的例子子序列（Subsequence）序列t是另一个序列s的子序列（subsequence），如果t中每个有序元素都是s中一个有序元素的子集。DatasequenceSubsequenceContain?{2,4}{3,5,6}{8}{2}{3,5}Yes{1,2}{3,4}{1}{2}No{2,4}{2,4}{2,5}{2}{4}Yes序列模式发现（SequentialPatternMining）设D是包含一个或多个数据序列的数据集:–序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于或等于用户指定的阈值minsup，则称s是一个序列模式（或频繁序列）。定义7.1序列模式发现:–给定序列数据库D和用户指定的最小支持度阈值minsup，序列模式发现的任务是找出支持度大于或等于minsup的所有序列。例子Minsup=50%ExamplesofFrequentSubsequences:{1,2}s=60%{2,3}s=60%{2,4}s=80%{3}{5}s=80%{1}{2}s=80%{2}{2}s=60%{1}{2,3}s=60%{2}{2,3}s=60%{1,2}{2,3}s=60%ObjectTimestampEventsA11,2,4A22,3A35B11,2B22,3,4C11,2C22,3,4C32,4,5D12D23,4D34,5E11,3E22,4,5提取序列模式：蛮力方法给定n个事件的集族:i1,i2,i3,…,in候选1-序列:{i1},{i2},{i3},…,{in}候选2-序列:{i1,i2},{i1,i3},…,{in-1}{in},{i1}{i1},{i1}{i2},…,{in-1}{in}候选3-序列:{i1,i2,i3},{i1,i2,i4},…,{i1,i2}{i1},{i1,i2}{i2},…,{i1}{i1,i2},{i1}{i1,i3},…,{i1}{i1}{i1},{i1}{i1}{i2},…候选序列的个数比候选项集的个数大得多。产生更多候选的原因有下面两个–一个项在项集中最多出现一次，但一个事件可以在序列中出现多次。给定两个项i1和i2，只能产生一个候选2-项集{i1，i2}，但却可以产生许多候选2-序列，如{i1,i2},{i1}{i2},{i2,i2},{i1,i1}。–次序在序列中是重要的，但在项集中不重要。例如，{1,2}和{2,1}表示同一个项集，而{i1}{i2}和{i2}{i1}对应于不同的序列，因此必须分别产生。先验原理对序列数据成立。–包含特定k-序列的任何数据序列必然包含该k-序列的所有(k-1)-序列。序列模式发现的类Apriori算法候选产生一对频繁(k-1)-序列合并，产生候选k-序列。为了避免重复产生候选，传统的Apriori算法仅当前k-1项相同时才合并一对频繁k-项集。类似的方法可以用于序列。例子–{1}{2}{3}{4}通过合并{1}{2}{3}和{2}{3}{4}得到。由于事件3和事件4属于第二个序列的不同元素，它们在合并后序列中也属于不同的元素。–{1}{5}{3,4}通过合并{1}{5}{3}和{5}{3,4}得到。由于事件3和事件4属于第二个序列的相同元素，4被合并到第一个序列的最后一个元素中。候选剪枝–一个候选k-序列被剪枝，如果它的(k-1)-序列最少有一个是非频繁的。–例如，假设{1}{2}{3}{4}是一个候选4-序列。我们需要检查{1}{2}{4}和{1}{3}{4}是否是频繁3-序列。由于它们都不是频繁的，因此可以删除候选{1}{2}{3}{4}。支持度计数–在支持度计数期间，算法将枚举属于一个特定数据序列的所有候选k-序列。–计数之后，算法将识别出频繁k-序列，并可以丢弃其支持度计数小于最小支持度阈值minsup的候选。图7-6{1}{2}{3}{1}{25}{1}{5}{3}{2}{3}{4}{25}{3}{3}{4}{5}{5}{34}{1}{2}{3}{4}{1}{25}{3}{1}{5}{34}{2}{3}{4}{5}{25}{34}{1}{25}{3}Frequent3-sequencesCandidateGenerationCandid