浙江大学王灿《数据挖掘》课程PPT_关联挖掘

挖掘频繁模式、关联和相关什么是频繁模式分析？频繁模式是频繁的出现在数据集中的模式如项集、子序或者子结构动机：发现数据中蕴含的内在规律那些产品经常被一起购买？---啤酒和尿布？买了PC之后接着都会买些什么？哪种DNA对这种新药敏感我们能够自动的分类WEB文档吗？应用购物篮分析、WEB日志（点击流）分析、捆绑销售、DNA序列分析等频繁模式挖掘的重要性揭示数据集的内在的、重要的特性作为很多重要数据挖掘任务的基础关联、相关和因果分析序列、结构（e.g.子图）模式分析时空、多媒体、时序和流数据中的模式分析分类：关联分类聚类分析：基于频繁模式的聚类数据仓库：冰山方体计算购物篮分析如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（e.g.0001001100，这种方法丢失了什么信息？）关联规则的两个兴趣度度量支持度置信度通常，如果关联规则同时满足最小支持度阈值和最小置信度阈值，则此关联规则是有趣的%]60%,2[sup_confidenceportsoftwareantiviruscomputer关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度cITTA],[csBAIBIA,BABA规则度量：支持度和置信度TID购买的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度阈值为50%，最小置信度阈值为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)同时满足最小支持度阈值和最小置信度阈值的规则称作强规则BA)()(supBAPBAport)(/)()|()(APBAPABPBAconfidence基本概念——示例项的集合I={A,B,C,D,E,F}每个事务T由事务标识符TID标识，它是项的集合TID(2000)={A,B,C}任务相关数据D是数据库事务的集合TID购买的item2000A,B,C1000A,C4000A,D5000B,E,F频繁项集基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数，简称为项集的频率、支持度计数或计数项集的支持度有时称为相对支持度，而出现的频率称作绝对支持度。如果项集I的频率大于（最小支持度阈值×D中的事务总数），则称该项集I为频繁项集。频繁k项集的集合通常记作Lk。)(_sup)(_sup)(sup)(sup)|()(AcountportBAcountportAportBAportABPBAconfidence关联规则挖掘的两步过程一般来说，关联规则的挖掘可以看作两步的过程：找出所有频繁项集该项集的每一个出现的频繁性≥min_sup由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则主要挑战：会产生大量满足min_sup的项集，尤其当min_sup设置得低的时候E.g.一个长度为100的频繁项集{a1,a2,…,a100}包含的频繁项集的总个数为30100100100210011001027.112...CCC闭频繁项集和极大频繁项集如果不存在真超项集Y使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的。项集X是数据集S中的闭频繁项集，如果X在S中是闭的和频繁的。项集X是S中的极大频繁项集（或极大项集），如果X是频繁的，并且不存在超项集Y使得并且Y在S中是频繁的。设C是数据集S中满足min_sup的闭频繁项集的集合，令M是S中满足min_sup的极大频繁项集的集合。假定我们有C和M中每个项集的支持度计数，则C和他的计数信息可以用来导出频繁项集的完整集合（我们称C包含了关于频繁项集的完整信息）。E.g.DB中只有两个事务{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,…,a100}有个频繁超集{a1,a2,…,a100}）。YX关联规则挖掘分类(1)根据挖掘的模式的完全性分类：给定min_sup，可以挖掘频繁项集的完全集，闭频繁项集和极大频繁项集。也可以挖掘被约束的频繁项集（即满足用户指定的一组约束的频繁项集）、近似的频繁项集（只推导被挖掘的频繁项集的近似支持度计数）、接近匹配的频繁项集（即与接近或几乎匹配的项集的支持度计数符合的项集）、top-k频繁项集不同的应用对挖掘的模式的完全性有不同的要求，我们主要研究挖掘频繁项集的完全集、闭频繁项集和被约束的频繁项集关联规则挖掘分类(2)根据规则集所涉及的抽象层单层关联规则多层关联规则（挖掘的规则集由多层关联规则组成）E.g.下例购买的商品涉及不同的抽象级根据规则中设计的数据维单维关联规则E.g.（仅涉及buys这个维）多维关联规则)int_,()_,()int_,(),(erpHPXbuyscomputerlaptopXbuyserprHPXbuyscomputerXbuys)_,(),(softwareantivirusXbuyscomputerXbuys)_,()48...42,()39...30,(TVresolutionhighXbuyskkXincomeXage关联规则挖掘分类(3)根据规则中所处理的值类型布尔关联规则（规则考虑的关联为项是否出现）量化关联规则（规则描述量化的项或属性间的关联）根据所挖掘的规则类型分类关联规则相关规则强梯度联系%]60%,2[sup_confidenceportsoftwareantiviruscomputer)_,()48...42,()39...30,(TVresolutionhighXbuyskkXincomeXage关联规则挖掘分类(4)根据所挖掘的模式类型分类频繁项集挖掘从事务或关系数据集中挖掘频繁项集序列模式挖掘从序列数据集中搜索频繁子序列结构模式挖掘在结构化数据集中搜索频繁子结构由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。TransactionIDItemsBought2000A,B,C1000A,C4000A,D5000B,E,FFrequentItemsetSupport{A}75%{B}50%{C}50%{A,C}50%最小支持度50%最小置信度50%对规则AC，其支持度=50%置信度%6.66)(sup/)(sup)(/)()|()(AportCAportAPCAPACPCAconfidence)()(supCAPCAportApriori算法(1)Apriori算法是挖掘布尔关联规则频繁项集的算法Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori算法(2)Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。模式不可能比A更频繁的出现Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率BAApriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素L1和L2可以执行连接操作的条件是Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。])1[]1[(])2[]2[(...])2[]2[(])1[]1[(21212121klklklklllll21llApriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{A,B,C}{B,C,E}Itemsetsup{B,C,E}2使用Apiori性质由L2产生C31．连接：C3=L2L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E}不是L2的元素，所以删除这个选项；{B,C,E}的2项子集是{B,C},{B,E},{C,E}，它的所有2－项子集都是L2的元素，因此保留这个选项。3．这样，剪枝后得到C3={{B,C,E}}由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由如下过程产生：对于每个频繁项集l，产生l的所有非空子集；对于每个非空子集s，如果则输出规则“”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls提高Apriori算法的有效性(1)Apriori算法主要的挑战要对数据进行多次扫描；会产生大量的候选项集；对候选项集的支持度计算非常繁琐；解决思路减少对数据的扫描次数；缩小产生的候选项集；改进对候选项集的支持度计算方法方法1：基于hash表的项集计数将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高Apriori算法的有效性(2)方法2：事务压缩（压缩进一步迭代的事务数）不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。方法3：划分