欢迎来到沃文网! | 帮助中心 分享知识,传播智慧!
沃文网
全部分类
  • 教学课件>
  • 医学资料>
  • 技术资料>
  • 学术论文>
  • 资格考试>
  • 建筑施工>
  • 实用文档>
  • 其他资料>
  • ImageVerifierCode 换一换
    首页 沃文网 > 资源分类 > PPT文档下载
    分享到微信 分享到微博 分享到QQ空间

    浙江大学《数据挖掘》课程-关联挖掘.ppt

    • 资源ID:1001605       资源大小:777KB        全文页数:57页
    • 资源格式: PPT        下载积分:20积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    三方登录下载: QQ登录 微博登录
    二维码
    微信扫一扫登录
    下载资源需要20积分
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP,下载更划算!
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    浙江大学《数据挖掘》课程-关联挖掘.ppt

    1、挖掘频繁模式、关挖掘频繁模式、关联和相关联和相关什么是频繁模式分析?n频繁模式是频繁的出现在数据集中的模式q如项集、子序或者子结构n动机:发现数据中蕴含的内在规律q那些产品经常被一起购买?-啤酒和尿布?q买了PC之后接着都会买些什么?q哪种DNA对这种新药敏感q我们能够自动的分类WEB文档吗?n应用q购物篮分析、WEB日志(点击流)分析、捆绑销售、DNA序列分析等频繁模式挖掘的重要性n揭示数据集的内在的、重要的特性n作为很多重要数据挖掘任务的基础q关联、相关和因果分析q序列、结构(e.g.子图)模式分析q时空、多媒体、时序和流数据中的模式分析q分类:关联分类q聚类分析:基于频繁模式的聚类q数据

    2、仓库:冰山方体计算购物篮分析n如果问题的全域是商店中所有商品的集合,则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买,则每个购物篮都可以用一个布尔向量表示;而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式,这些模式就可以用关联规则表示(e.g.0001001100,这种方法丢失了什么信息?)n关联规则的两个兴趣度度量q支持度q置信度q通常,如果关联规则同时满足最小支持度阈值和最小置信度阈值,则此关联规则是有趣的关联规则:基本概念n给定:q项的集合:I=i1,i2,.,inq任务相关数据D是数据库事务的集合,每个事务T则是项的集合,使得q每个事务由事务标识符TID标识;qA,

    3、B为两个项集,事务T包含A当且仅当n则关联规则是如下蕴涵式:q其中 并且 ,规则 在事务集D中成立,并且具有支持度s和置信度c规则度量:支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beerq支持度s是指事务集D中包含 的百分比q置信度c是指D中包含A的事务同时也包含B的百分比q假设最小支持度阈值为50%,最小置信度阈值为50%,则有如下关联规则nA C (50%,66.6%)nC A (50%,100%)q同时满足最小支持度阈值和最小置信度阈值的规则称作强规则P148 基本概念示例n项的集合 I=A,B,C,D,E,Fn每个事

    4、务T由事务标识符TID标识,它是项的集合 TID(2000)=A,B,Cn任务相关数据D是数据库事务的集合频繁项集n基本概念qk项集项集:包含k个项的集合n牛奶,面包,黄油是个3项集q项集的频率项集的频率是指包含项集的事务数,简称为项集的频率频率、支持度计数支持度计数或计数计数q项集的支持度有时称为相对支持度相对支持度,而出现的频率称作绝对支持度绝对支持度。如果项集I的频率大于(最小支持度阈值D中的事务总数),则称该项集I为频繁项频繁项集集。频繁k项集的集合通常记作Lk。关联规则挖掘 的两步过程n一般来说,关联规则的挖掘可以看作两步的过程:q找出所有频繁项集n该项集的每一个出现的频繁性 min

    5、_supq由频繁项集产生强关联规则n即满足最小支持度和最小置信度的规则n主要挑战:会产生大量满足min_sup的项集,尤其当min_sup设置得低的时候qE.g.一个长度为100的频繁项集a1,a2,a100包含的频繁项集的总个数为闭频繁项集和极大频繁项集n如果不存在真超项集Y使得Y与X在S中有相同的支持度计数,则称项集X在数据集S中是闭的。项集X是数据集S中的闭频繁项集,如果X在S中是闭的和频繁的。项集X是S中的极大频繁项集(或极大项集),如果X是频繁的,并且不存在超项集Y使得 并且Y在S中是频繁的。n设C是数据集S中满足min_sup的闭频繁项集的集合,令M是S中满足min_sup的极大频

    6、繁项集的集合。假定我们有C和M中每个项集的支持度计数,则C和他的计数信息可以用来导出频繁项集的完整集合(我们称C包含了关于频繁项集的完整信息)。nE.g.qDB中只有两个事务;,min_sup=1,则 C=:1;:2,M=:1(显然a1,a2,a100 有个频繁超集a1,a2,a100)。关联规则挖掘分类(1)n根据挖掘的模式的完全性分类:给定min_sup,可以挖掘频繁项集的完全集频繁项集的完全集,闭频繁项集闭频繁项集和极大大频繁项集频繁项集。也可以挖掘被约束的频繁项集被约束的频繁项集(即满足用户指定的一组约束的频繁项集)、近似的频近似的频繁项集繁项集(只推导被挖掘的频繁项集的近似支持度计数

    7、)、接近匹配的频繁项集接近匹配的频繁项集(即与接近或几乎匹配的项集的支持度计数符合的项集)、top-k频频繁项集繁项集n不同的应用对挖掘的模式的完全性有不同的要求,我们主要研究挖掘频繁项集的完全集频繁项集的完全集、闭频繁项闭频繁项集集和被约束的频繁项集被约束的频繁项集关联规则挖掘分类(2)n根据规则集所涉及的抽象层q单层关联规则q多层关联规则(挖掘的规则集由多层关联规则组成)nE.g.下例购买的商品涉及不同的抽象级n根据规则中设计的数据维q单维关联规则nE.g.(仅涉及buys这个维)q多维关联规则关联规则挖掘分类(3)n根据规则中所处理的值类型q布尔关联规则(规则考虑的关联为项是否出现)q量

    8、化关联规则(规则描述量化的项或属性间的关联)n根据所挖掘的规则类型分类q关联规则q相关规则q强梯度联系关联规则挖掘分类(4)n根据所挖掘的模式类型分类q频繁项集挖掘n从事务或关系数据集中挖掘频繁项集q序列模式挖掘n从序列数据集中搜索频繁子序列q结构模式挖掘n在结构化数据集中搜索频繁子结构由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘,即单维、单层、布尔关联规则的挖掘。最小支持度 50%最小置信度 50%n对规则A C,其支持度 =50%n置信度Apriori算法(1)nApriori算法是挖掘布尔关联规则频繁项集的算法nApriori算法利用频繁项集性质的先验知识(prior know

    9、ledge),通过逐层搜索的迭代方法,即将k-项集用于探察(k+1)-项集,来穷尽数据集中的所有频繁项集。q先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2,接着用L2找L3,直到找不到频繁k-项集,找每个Lk需要一次数据库扫描。Apriori算法(2)nApriori算法利用的是Apriori性质:频繁项集的所有非空子集也必须是频繁的。q 模式不可能比A更频繁的出现qApriori算法是反单调的,即一个集合如果不能通过测试,则该集合的所有超集也不能通过相同的测试。qApriori性质通过减少搜索空间,来提高频繁项集逐层产生的效率Apriori算法步骤nApriori算法由连接连

    10、接和剪枝剪枝两个步骤组成。n连接:连接:为了找Lk,通过Lk-1与自己连接产生候选k-项集的集合,该候选候选k项集项集记为Ck。qLk-1中的两个元素L1和L2可以执行连接操作 的条件是nCk是Lk的超集,即它的成员可能不是频繁的,但是所有频繁的k-项集都在Ck中(为什么?)。因此可以通过扫描数据库,通过计算每个k-项集的支持度来得到Lk。q为了减少计算量,可以使用Apriori性质,即如果一个k-项集的(k-1)-子集不在Lk-1中,则该候选不可能是频繁的,可以直接从Ck删除。Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd s

    11、canTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetA,B,CB,C,EItemsetsupB,C,E2使用Apiori性质由L2产生C3n1 连接:qC3=L2 L2=A,C,B,C,B,EC,E A,C,B,C,B,EC,E=A,B,C,A,C,E,B,C,En2使用Apriori性质剪枝:频繁项集的所有子集

    12、必须是频繁的,对候选项C3,我们可以删除其子集为非频繁的选项:qA,B,C的2项子集是A,B,A,C,B,C,其中A,B不是L2的元素,所以删除这个选项;qA,C,E的2项子集是A,C,A,E,C,E,其中A,E 不是L2的元素,所以删除这个选项;qB,C,E的2项子集是B,C,B,E,C,E,它的所有2项子集都是L2的元素,因此保留这个选项。n3这样,剪枝后得到C3=B,C,E由频繁项集产生关联规则n同时满足最小支持度和最小置信度的才是强关联规则,从频繁项集产生的规则都满足支持度要求,而其置信度则可由一下公式计算:n每个关联规则可由如下过程产生:q对于每个频繁项集l,产生l的所有非空子集;q

    13、对于每个非空子集s,如果 则输出规则“”提高Apriori算法的有效性(1)nApriori算法主要的挑战q要对数据进行多次扫描;q会产生大量的候选项集;q对候选项集的支持度计算非常繁琐;n解决思路q减少对数据的扫描次数;q缩小产生的候选项集;q改进对候选项集的支持度计算方法n方法1:基于hash表的项集计数q将每个项集通过相应的hash函数映射到hash表中的不同的桶中,这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高Apriori算法的有效性(2)n方法2:事务压缩(压缩进一步迭代的事务数)q不包含任何k-项集的事务不可能包含任何(k+1)-项集,这种事务在下一步的计

    14、算中可以加上标记或删除。n方法3:划分q挖掘频繁项集只需要两次数据扫描qD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。n第一次扫描:将数据划分为多个部分并找到局部频繁项集n第二次扫描:评估每个候选项集的实际支持度,以确定全局频繁项集提高Apriori算法的有效性(3)n方法4:选样(在给定数据的一个子集挖掘)q基本思想:选择原始数据的一个样本,在这个样本上用Apriori算法挖掘频繁模式q通过牺牲精确度来减少算法开销,为了提高效率,样本大小应该以可以放在内存中为宜,可以适当降低最小支持度来减少遗漏的频繁模式n可以通过一次全局扫描来验证从样本中发现的模式n可以通过第二此全局扫描来找

    15、到遗漏的模式n方法5:动态项集计数q在扫描的不同点添加候选项集,这样,如果一个候选项集已经满足最少支持度,则在可以直接将它添加到频繁项集,而不必在这次扫描的以后对比中继续计算。不产生候选频繁项集的算法FP树nApriori算法的主要开销:q可能要产生大量的候选项集n104个频繁1-项集会导致107个频繁2-项集n对长度为100的频繁模式,会产生2100个候选q重复扫描数据库,通过模式匹配模式匹配检查一个很大的候选集合n不产生候选频繁项集的算法FP-树频集算法q一种采用divide and conquer(分治策略)的方法n在经过第一遍扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tre

    16、e),同时依然保留其中的关联信息;n将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关,然后再对这些条件库分别进行挖掘。从数据库构建一个FP树nullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3min_sup=3TIDItems bought (ordered)frequent items100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,of,b400 b,c,k,s,pc,b,p500 a,f,c,e,l

    17、,p,m,nf,c,a,m,p步骤:1.扫描一次数据库,导出频繁项的集合(1-项集)2.将频繁项按降序排列3.再次扫描数据库,构建FP树FP树的构建(第二次扫描数据库)1.创建树的根节点,用null标记;2.将每个事务中的项按递减支持度计数排列,并对每个事务创建一个分枝;q比如为第一个事务f,c,a,m,p构建一个分枝3.当为一个事务考虑增加分枝时,沿共同前缀上的每个节点的计数加1,为跟随前缀后的项创建节点并连接q比如将第二个事务f,c,a,b,m加到树上时,将为f,c,a各增计数1,然后为b,m创建分枝4.创建一个项头表,以方便遍历,每个项通过一个节点链指向它在树中的出现。FP树结构的好处n

    18、完整性q不会打破任何事务数据中的长模式q为频繁模式的挖掘保留了完整的信息n紧凑性q减少了不相关的信息非频繁的项被删除q按频率递减排列使得更频繁的项更容易在树结构中被共享q数据量比原数据库要小FP树挖掘nFP树的挖掘步骤:q由长度为1的频繁模式(初始后缀模式)开始,构造它的条件模式基(一个“子数据库”,由FP树中与后缀模式一起出现的前缀路径集组成。q构造该初始后缀模式的条件FP树,并递归的在该树上实现挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。FP树挖掘从FP树到条件模式基n从项头表开始挖掘,由频率低的节点开始n沿循每个(频繁)项的链接来遍历FP树n通过积累该项的前缀路径来形成

    19、一个条件模式基Conditional pattern basesitemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1nullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3FP树挖掘构建条件FP树n对每个条件模式基q为基中的每一项累积计数q为模式基中的频繁项构建FP树m-条件模式基条件模式基:fca:2,fcab:1f:3c:3a:3m-条件条件FP-树树所有关于所有关于m的频繁模的频繁模式:式:m,fm,cm,am

    20、,fcm,fam,cam,fcamnullf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表项头表Item frequency head f4c4a3b3m3p3多层关联规则(1)n数据项中经常会形成概念分层n底层的数据项,其支持度往往也较低q这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTID ItemsT1IBM D/C,Sony

    21、 b/wT2 Ms.edu.Sw.,Ms.fin.Sw.T3 Logi.mouse,Ergoway wrist padT4IBM D/C,Ms.Fin.Sw.T5IBM D/CErgoway多层关联规则(2)n在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的n通常,事务数据库中的数据也是根据维和概念分层来进行储存的q这为从事务数据库中挖掘不同层次的关联规则提供了可能。n在多个抽象层挖掘关联规则,并在不同的抽象层进行转化,是数据挖掘系统应该提供的能力挖掘多层关联规则的方法n通常,多层关联规则的挖掘还是使用置信度支持度框架,可以采用自顶向下策略q请注意:概念分层中,一个节点的支持度肯定不小

    22、于该节点的任何子节点的支持度q由概念层1开始向下,到较低的更特定的概念层,对每个概念层的频繁项计算累加计数q每一层的关联规则挖掘可以使用Apriori等多种方法q例如:n先找高层的关联规则:computer-printer 20%,60%n再找较低层的关联规则:laptop-color printer 10%,50%多层关联一致支持度n一致支持度:对所有层都使用一致的最小支持度q优点:搜索时容易采用优化策略,即一个项如果不满足最小支持度,它的所有子项都可以不用搜索q缺点:最小支持度值设置困难n太高:将丢掉出现在较低抽象层中有意义的关联规则n太低:会在较高层产生太多的无兴趣的规则多层关联递减支持

    23、度n使用递减支持度,可以解决使用一致支持度时在最小支持度值上设定的困难n递减支持度:在较低层使用递减的最小支持度q每一层都有自己的一个独立的最小支持度q抽象层越低,对应的最小支持度越小Computer support=10%Laptopsupport=6%Desktopsupport=4%min_sup=5%min_sup=5%min_sup=3%多层关联基于分组的支持度n用户和专家清楚哪些分组比其他分组更加重要,在挖掘多层关联规则时,使用用户指定的基于项或者基于分组的最小支持度阈值qE.g.对laptop_computer或者flash_drives设置特别低的支持度阈值,以便特别关注这类商

    24、品的管理模式检查冗余的多层关联规则n挖掘多层关联规则时,由于项间的“祖先”关系,有些发现的规则将是冗余的q例如:ndesktop computer=b/w printer sup=8%,con=70%(1)nIBM desktop computer=b/w printer sup=2%,con=72%(2)n上例中,我们说第一个规则是第二个规则的“祖先”n如果规则(2)中的项用它在概念分层中的“祖先”代替,能得到(1),而且(1)的支持度和置信度都接近“期望”值,则(1)是冗余的。多维关联规则概念n单维关联规则:qbuys(X,“milk”)buys(X,“bread”)n多维关联规则:涉及两

    25、个或多个维或谓词的关联规则q维间关联规则:不包含重复的谓词nage(X,”19-25”)occupation(X,“student”)=buys(X,“coke”)q混合维关联规则:包含某些谓词的多次出现nage(X,”19-25”)buys(X,“popcorn”)=buys(X,“coke”)n在多维关联规则挖掘中,我们搜索的不是频繁项集,而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。q例如:age,occupation,buys是一个3-谓词集挖掘多维关联规则的技术n数据属性可以分为分类属性和量化属性q分类属性n具有有限个不同值,值之间无序q量化属性n数值类型的值,并且值之间有一个

    26、隐含的序n挖掘多维关联规则的技术可以根据量化属性的处理分为两种种基本方法:q1.量化属性的静态离散化n使用预定义的概念分层对量化属性进行静态地离散化q2.量化关联规则n根据数据的分布,将量化属性离散化到“箱”多维关联规则挖掘使用量化属性的静态离散化n量化属性使用预定义的概念分层,在挖掘前进行离散化n数值属性的值用区间代替n如果任务相关数据存在关系数据库中,则找出所有频繁的k-谓词集将需要k或k+1次表扫描n数据立方体技术非常适合挖掘多维关联规则qn-维方体的单元用于存放对应n-谓词集的计计数或支持度数或支持度,0-D方体用于存放任务相关数据的事务总数n如果包含感兴趣的维的数据立方体已经存在并物

    27、化,挖掘将会很快,同时可以利用Apriori性质:频繁谓词集的每个子集也必须频繁谓词集的每个子集也必须是频繁的是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)多维关联规则挖掘挖掘量化关联规则(1)n量化关联规则中,数值属性将根据某种挖掘标准,进行动态的离散化q例如:最大化挖掘规则的置信度和紧凑性n为了简化量化关联规则挖掘的讨论,我们将聚焦于类似以下形式的2-维量化关联规则维量化关联规则:Aquan1 Aquan2 Acatq(两个量化属性和一个分类属性间的关联)q例如:age(X,”30-

    28、39”)income(X,”42K-48K”)buys(X,”high resolution TV”)多维关联规则挖掘挖掘量化关联规则(2)n找出这类2-维量化关联规则的方法:关联规则聚类系统(ARCS)q一种源于图像处理的技术,该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上,然后通过搜索栅格点的聚类而产生关联规则关联规则聚类系统(ARCS)(1)nARCS过程中的步骤包括q1.分箱(根据不同分箱方法创建一个2-D数组),本步骤的目的在于减少量化属性相对应的巨大的值个数,使得2-D栅格的大小可控n等宽分箱n等深分箱n基于同质的分箱(每个箱中元组一致分布)q2.找出频繁谓词集n扫描分

    29、箱后形成的2-D数组,找出满足最小支持度和置信度的频繁谓词集关联规则聚类系统(ARCS)(2)q3.关联规则聚类n将上一步得到的强关联规则映射到2-D栅格上,使用聚类算法,扫描栅格,搜索规则的矩形聚类ARCS的局限性n所挖掘的关联规则左手边只能是量化属性n规则的左手边只能有两个量化属性(2-D栅格的限制)n一种不基于栅格的,可以发现更一般关联规则的技术,其中任意个数的量化属性和分类属性可以出现在规则的两端q等深分箱动态划分q根据部分完全性部分完全性的度量进行聚类关联规则的兴趣度度量n客观度量q两个流行的度量指标n支持度n置信度n主观度量q最终,只有用户才能确定一个规则是否有趣的,而且这种判断是

    30、主观的,因不同的用户而异;通常认为一个规则(模式)是有趣的,如果:n它是出人意料的n可行动的(用户可以使用该规则做某些事情)n挖掘了关联规则后,哪些规则是用户感兴趣的?强关联规则是否就是有趣的?对强关联规则的批评(1)n例1:(Aggarwal&Yu,PODS98)q在5000个学生中n3000个打篮球n3750个喝麦片粥n2000个学生既打篮球又喝麦片粥q然而,打篮球=喝麦片粥 40%,66.7%是错误的,因为全部学生中喝麦片粥的比率是75%,比打篮球学生的66.7%要高q打篮球=不喝麦片粥 20%,33.3%这个规则远比上面那个要精确,尽管支持度和置信度都要低的多对强关联规则的批评(2)n

    31、例1:(书P168)q上述数据可以得出buys(X,“computer games”)=buys(X,“videos”)40%,60%q但其实全部人中购买录像带的人数是75%,比60%多;事实上录像带和游戏是负相关的。q由此可见A=B的置信度有欺骗性,它只是给出A,B条件概率的估计,而不度量A,B间蕴涵的实际强度。由关联分析到相关分析n可以使用相关度量来扩充关联规则的支持度-置信度框架n我们需要一种度量事件间的相关性或者是依赖性的指标n当项集A的出现独立于项集B的出现时,P(AB)=P(A)P(B),即lift(A,B)1,表明A与B无关,lift(A,B)1表明A与B正相关,lift(A,B

    32、)buys(X,“office software)nY,W分别取赋给谓词变量P1,P2的属性值n一般,元规则形成一个用户希望探察的假定,而系统则寻找与该元规则匹配的规则,例如:qage(X,30-39)income(X,42K-60K)buys(X,“office software)关联规则的元规则制导挖掘(2)n“如何使用元规则指导挖掘过程”?假定我们希望挖掘的元规则形式为:qP1P2Pl=Q1Q2Qrn设元规则中谓词的个数为p=l+r,则找出符合该模板的关联规则需以下两步骤:q找出所有的频繁p-谓词集Lpq计算Lp中的l-谓词子集的支持度,然后计算由Lp导出的规则的置信度n数据立方体具有存

    33、放聚集维值的能力,适合多维关联规则的挖掘,在n维数据立方体中(n=p)挖掘上述规则可以用以下步骤:q扫描p-D方体,将每个单元中的计数和最小支持度计数比较,得到Lpq考察l-D方体,返回与元规则匹配的强关联规则挖掘过程中使用的规则约束n通常的数据挖掘中,知识类型和数据约束在挖掘前使用,其它约束在挖掘后用来过滤规则,但这使挖掘过程非常低效。n什么类型的规则约束可以在挖掘过程中使用,以缩小规则搜索空间?n对于频繁项集挖掘,在挖掘过程中使用的约束包括以下五种类型:q反单调的q单调的q简洁的q可转变的q不可转变的反单调的和单调的约束n如果一个项集不满足该规则约束,则它的任何一个超集都不可能满足该约束;

    34、具有这种性质的规则称为是反单调的反单调的。qe.g.Apriori性质就是反单调的(频繁项集的任何非空子集也必须是频繁的)n用于算法的每次迭代,以减少考察的候选项集的个数n如果一个项集满足该约束,则它的所有超集也满足该约束;具有这种性质的规则称为是单调单调的。的。qe.g.Count(I)=10简洁性约束n一个约束是简洁的,如果我们可以列出并仅仅列出所有确保满足该约束的集合q利用简洁性约束,我们可以在计数前进行剪枝,从而避免产生测试方式的过大开销。nE.g.min(J.price)500是简洁的,我们能明确无误的产生满足该约束的所有项集可转变的和不可转变的约束n有些约束不属于前面三类,但是如果项集中的项以特定的次序排列,则对于频繁项集挖掘的全过程,约束可能成为单调的或者是反单调的q例:avg(I.price),既非单调,也非反单调,但是如果事务中的项以价格递增的序添加到项集中,该约束就变成了反单调的n不可转变的约束是数据挖掘中较难处理的部分,但这种约束往往较少。q另外,大部分使用SQL内部聚集的简单SQL表达式都属于前面四类约束


    注意事项

    本文(浙江大学《数据挖掘》课程-关联挖掘.ppt)为本站会员(风****)主动上传,沃文网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知沃文网(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给沃文网发消息,QQ:2622162128 - 联系我们

    版权声明:以上文章中所选用的图片及文字来源于网络以及用户投稿,由于未联系到知识产权人或未发现有关知识产权的登记,如有知识产权人并不愿意我们使用,如有侵权请立即联系:2622162128@qq.com ,我们立即下架或删除。

    Copyright© 2022-2024 www.wodocx.com ,All Rights Reserved |陕ICP备19002583号-1

    陕公网安备 61072602000132号     违法和不良信息举报:0916-4228922