数据挖掘关联规则课件

AssociationRules1内容提要

引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结2关联规则

关联规则表示了项之间的关系示例:cereal,milkfruit“买谷类食品和牛奶的人也会买水果.”商店可以把牛奶和谷类食品作特价品以使人们买更多的水果.3基本概念通常,数据包含:TIDBasket事务ID项的子集5

关联规则挖掘在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.频繁模式:数据库中出现频繁的模式(项集,序列,等等)6基本概念项集事务关联规则事务数据集(例如右图)事务标识TID：每一个事务关联着一个标识Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,F7度量有趣的关联规则可信度cD中同时包含A和B的事务数与只包含A的事务数的比值规则AB在数据集D中的可信度为c,

其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B|A)表示.confidence(A

B)=P(B|A)

条件概率P(B|A)表示A发生的条件下B也发生的概率.9度量有趣的关联规则关联规则根据以下两个标准(包含或排除):最小支持度

–表示规则中的所有项在事务中出现的频度最小可信度

-表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度10市场购物篮分析I是什么?事务IDB的T是什么?s(Chips=>Salsa)是什么?c(Chips=>Salsa)是什么?事务ID购物篮AChips,Salsa,Cookies,Crackers,Coke,BeerBLettuce,Spinach,Oranges,Celery,Apples,GrapesCChips,Salsa,FrozenPizza,FrozenCakeDLettuce,Spinach,Milk,Butter,Chips11Steptwo:强关联规则给定一个项集,容易生成关联规则.项集:{Chips,Salsa,Beer}Beer,Chips=>SalsaBeer,Salsa=>ChipsChips,Salsa=>Beer强规则是有趣的强规则通常定义为那些满足最小支持度和最小可信度的规则.13关联规则挖掘两个基本步骤Stepone:找出所有的频繁项集满足最小支持度Steptwo:找出所有的强关联规则由频繁项集生成关联规则保留满足最小可信度的规则14内容提要

引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结15生成频繁项集naïvealgorithm的分析I的子集:O(2m)为每一个子集扫描n个事务测试s为T的子集:O(2mn)随着项的个数呈指数级增长!我们能否做的更好?17Apriori性质定理(Apriori性质):若A是一个频繁项集,则A的每一个子集都是一个频繁项集.证明:设n为事务数.假设A是l个事务的子集,若A’A

,则A’为l’(l’l)个事务的子集.因此,l/n≥s(最小支持度),l’/n≥s也成立.18Apriori算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.思想:Apriori使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集. 首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描..19Apriori:一种候选项集生成-测试方法Apriori剪枝原理:若任一项集是不频繁的,则其超集不应该被生成/测试!方法:由频繁k-项集生成候选(k+1)-项集,并且在DB中测试候选项集性能研究显示了Apriori算法是有效的和可伸缩(scalablility)的.21TheApriori算法—一个示例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{B,C,E}Itemsetsup{B,C,E}222加权关联规则挖掘传统的关联规则挖掘算法通常都认为数据库里每个项目都有相同的重要性，没有主要、次要之分。但在实际中，往往存在一类这样的情况：用户对每个项目的看重程度不一样，有的项目是用户最看重、最关心的，有的项目是用户关注性不大，因此需要引进权重的概念。23加权关联规则的描述对于项目集X、Y，，X∩Y=φ，如果有wsup(X∪Y)≥wminsup，且conf(X→Y)≥minconf，则称X→Y是一条加权关联规则。25权值的设定加权支持度

(1)、平均值：

(2)、归一化：

(3)、最大值：

26Apriori算法JoinisgeneratecandidatessetofitemsetsCkfrom2itemsetsinLk-1Procedurejoin(p,q)insertintoCkselectp.item1,p.item2,...,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,...,p.itemk-2=q.itemk-2,p.itemk-1=q.itemk-129Apriori算法Procedurehas_infrequent_subset(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets;)//usepriorknowledge

foreach(k-1)-subsetsofcifs

Lk-1then

returnTRUE;returnFALSE.30Apriori算法的重要细节如何生成候选项集?步骤1:自连接Lk步骤2:剪枝如何计算候选项集的支持度?候选项庥生成的示例L3={abc,abd,acd,ace,bcd}自连接:L3*L3由abc

和abd

连接得到abcd由acd

和ace

连接得到acde剪枝:因为ade不在L3中acde被剪除C4={abcd}31如何生成候选项集?假定Lk-1中的项以一定顺序排列步骤1:自连接Lk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1步骤2:剪枝forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk32如何计算候选项集的支持度?为何候选项集的支持度的计算是一个问题?候选项集的总数可能是巨大的

一个事务可能包含多个候选项集方法:候选项集被存储在一个哈希树哈希树的叶子结点包含一个项集和计数的列表内部结点包含一个哈希表子集函数:找出包含在一个事务中的所有候选项集33频繁模式挖掘的挑战挑战多次扫描事务数据库巨大数量的候选项集繁重的计算候选项集的支持度工作改进Apriori:大体的思路减少事务数据库的扫描次数缩减候选项集的数量使候选项集的支持度计算更加方便34内容提要

引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结35频繁模式挖掘的瓶颈多次扫描数据库是高代价的长模式的挖掘需要多次扫描数据库以及生成许多的候选项集找出频繁项集i1i2…i100扫描次数:100候选项集的数量:(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶颈:候选项集-生成-测试我们能否避免生成候选项集?36不生成候选项集的频繁模式挖掘利用局部频繁的项由短模式增长为长模式“abc”是一个频繁模式得到所有包含“abc”的事务:DB|abc“d”是DB|abc的一个局部频繁的项abcd是一个频繁模式37FPGrowth算法(Han,Pei,Yin2000)Apriori算法的一个有问题的方面是其候选项集的生成指数级增长的来源另一种方法是使用分而治之的策略(divideandconquer)思想:

将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树38利用FP-树进行频繁模式挖掘思想:频繁模式增长递归地增长频繁模式借助模式和数据库划分方法对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树.对每个新创建的条件FP-树重复上述过程直至结果FP-树为空,或者它仅包含一个单一路径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式.39频繁1-项集最小支持度为20%(计数为2)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2{I6}1ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2事务数据库支持度计数频繁1-项集40FP-树构建ItemsetSupportcount{I1}6{I2}7{I3}6{I4}2{I5}2ItemsetSupportcount{I2}7{I1}6{I3}6{I4}2{I5}2按支持度降序排列41FP-树构建

创建根结点null

扫描数据库

事务1:I1,I2,I5

排序:I2,I1,I5

处理事务

以项的顺序增加结点

标注项及其计数(I2,1)(I1,1)(I5,1)1I50I40I31I11I2

维护索引表42FP-树构建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I343FP-树构建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3(I3,2)(I3,2)(I1,2)(I3,2)(I4,1)(I5,1)44FP-树构建扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.创建FP-树的根,标注其为NULL.对D中的每个事务进行以下操作:根据L中的次序对事务中的频繁项进行选择和排序.设事务中的已排序的频繁项列表为[p|P],其中p表示第一个元素,P表示剩余的列表.调用insert_Tree([p|P],T).45FP-树构建Insert_Tree([p|P],T)

IfThasachildNsuchthatN.item-name=p.item-name,

thenincrementN’scountby1;

elsecreateanewnodeN,andletitscountbe1,itsparentlinkbelinkedtoT,anditsnode-linktothenodeswiththesameitem-nameviathenode-linkstructure.

IfPisnonempty,callinsert_tree(P,N)recursively.46挖掘FP-tree从索引表中的最后一个项开始找到所有包含该项的路径沿着结点-链接(node-links)确定条件模式路径中符合频度要求的模式构建FP-treeC添加项至C中所有路径,生成频繁模式递归地挖掘C(添加项)从索引表和树中移除项47挖掘FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2)

前缀路径(I2I1,1)(I2I1I3,1)条件路径(I2I1,2)

条件FP-tree(I2I1I5,2),(I2I5,2),(I1I5,2)null(I2,2)(I1,2)48挖掘FP-Tree项条件模式基条件FP-tree生成的频繁模式I5{(I2I1:1),(I2I1I3:1)}<I2:2,I1:2>I2I5:2,I1I5:2,I2I1I5:2I4{(I2I1:1),(I2:1)}<I2:2>I2I4:2I3{(I2I1:2,(I2:2),(I1:2)}<I2:4,I1:2>,<I1:2>I2I3:4,I1I3:2,I2I1I3:2I1{(I2:4)}<I2:4>I2I1:449挖掘FP-TreeProcedureFP_growth(Tree,)IfTreecontainsasinglepathPthenforeachcombination(denoteas)ofthenodesinthepathPgeneratepatternwithsupport=minisupofnodesin;ElseforeachaiintheheaderofTree{generatepattern=aiwithsupport=ai.support;construct,sconditionalpatternbaseandthen’conditionalFP_treeTree;IFTreeøthencallFP_growth(Tree,);}

50由事务数据库构建FP-树{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 3min_support=3TID Itemsbought (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}扫描DB一次,找到频繁1项(单一项模式)按支持度降序对频繁项排序为F-list再次扫描DB,构建FP-treeF-list=f-c-a-b-m-p51划分模式和数据库频繁模式根据F-list可以被划分为若干子集F-list=f-c-a-b-m-p包含p的模式包含m但包含p的模式…包含c但不包含a,b,m,p的模式模式f完整性和非冗余性52从P的条件数据库找出包含P的模式从FP-tree的索引表的频繁项开始沿着每个频繁项p的链接遍历FP-tree累积项p的所有转换前缀路径来形成的p的条件模式基条件模式基项 条件模式基c f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf 4c 4a 3b 3m 3p 353递归:挖掘每个条件FP-tree{}f:3c:3a:3m-条件FP-tree“am”的条件模式基:(fc:3){}f:3c:3am-条件FP-tree“cm”的条件模式基:(f:3){}f:3cm-条件FP-tree“cam”的条件模式基:(f:3){}f:3cam-条件FP-tree54一个特例:FP-tree中的单一前缀路径假定(条件的)FP-treeT有一个共享的单一前缀路径P挖掘可以分为两部分将单一前缀路径约简为一个结点将两部分的挖掘结果串联a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1{}r1=55通过DB投影(Projection)使FP-growth可伸缩FP-tree不能全放入内存?—DB投影首先将一个数据库划分成一个由若干投影(Projected)数据库组成的集合然后对每个投影数据库构建和挖掘FP-treeParallelprojectionvs.Partitionprojection

技术Parallelprojectionisspacecostly56Partition-basedProjectionParallelprojection需要很多磁盘空间Partitionprojection节省磁盘空间Tran.DBfcampfcabmfbcbpfcampp-projDBfcamcbfcamm-projDBfcabfcafcab-projDBfcb…a-projDBfc…c-projDBf…f-projDB…am-projDBfcfcfccm-projDBfff…57改进途径使用哈希表存储候选k-项集的支持度计数移除不包含频繁项集的事务对数据采样划分数据若一个项集是频繁的,则它必定在某个数据分区中是频繁的.58FP-tree结构的优点完整性保持了频繁项集挖掘的完整信息没有打断任何事务的长模式紧密性减少不相关的信息—不频繁的项没有了项按支持度降序排列:越频繁出现,越可能被共享决不会比原数据库更大(不计结点链接和计数域)对Connect-4数据库,压缩比率可以超过10059FP-Growthvs.Apriori:支持度的可伸缩性DatasetT25I20D10K60FP-Growthvs.Tree-Projection:支持度的可伸缩性DatasetT25I20D100K61关联规则可视化:方格图(PaneGraph)62关联规则可视化:规则图(RuleGraph)63内容提要

引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结64挖掘多种规则或规律多层(Multi-level),量化(quantitative)关联规则,相关(correlation)和因果(causality),比率(ratio)规则,序列(sequential)模式,浮现(emerging)模式,temporalassociations,局部周期(partialperiodicity)分类(classification),聚类(clustering),冰山立方体(icebergcubes),等等.65多层关联规则项常常构成层次可伸缩的(flexible)支持度设置:在较低层的项预期有较低的支持度.事务数据库可以基于维度和层次编码探寻共享多层挖掘统一支持度Milk[support=10%]2%Milk[support=6%]SkimMilk[support=4%]Level1min_sup=5%Level2min_sup=5%Level1min_sup=5%Level2min_sup=3%减少的支持度66可伸缩的支持度约束的多层/多维(ML/MD)关联规则为什么设置可伸缩的支持度?实际生活中项的出现频率变化巨大在一个商店购物篮中的钻石,手表,钢笔统一的支持度未必是一个有趣的模型一个可伸缩模型较低层的,较多维的组合以及长模式通常具有较小的支持度总体规则应该要容易说明和理解特殊的项和特殊的项的组合可以特别设定(最小支持度)以及拥有更高的优先级67多维关联规则单维规则:buys(X,“milk”)buys(X,“bread”)多维规则:

2个维度或谓词(predicates)跨维度(Inter-dimension)关联规则(无重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维度(hybrid-dimension)关联规则(重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类(Categorical)属性有限的几个可能值,值之间不可排序数量(Quantitative)属性数值的,值之间有固有的排序68多层关联规则:冗余滤除根据项之间的”先辈”(ancestor)关系,一些规则可能是冗余的.示例milkwheatbread[support=8%,confidence=70%]2%milkwheatbread[support=2%,confidence=72%]我们说第1个规则是第2个规则的先辈.一个规则是冗余的,当其支持度接近基于先辈规则的”预期”(expected)值.69多层关联规则:逐步深化(ProgressiveDeepening)一个自上而下的,逐步深化的方法:

首先挖掘高层的频繁项:milk(15%),bread(10%)

然后挖掘它们的较低层”较弱”(weaker)频繁项:2%milk(5%),wheatbread(4%)多层之间不同的最小支持度阈值导致了不同的算法:如果在多个层次间采用了相同的最小支持度,若t的任何一个先辈都是非频繁的则扔弃(toss)t.如果在较低层采用了减少的最小支持度，则只检验那些先辈的支持度是频繁的／不可忽略的派生（descendents）即可．70多维关联规则挖掘的技术搜索频繁k-谓词集(predicateset):示例:{age,occupation,buys}是一个3-谓词集以age处理的方式,技术可以如下分类1.利用数量属性的统计离散(staticdiscretization)方法利用预先确定的概念层次对数量属性进行统计离散化2.量化关联规则基于数据的分布,数量属性被动态地离散化到不同的容器空间(bins)3.基于距离(Distance-based)的关联规则这是一个动态离散化的过程,该过程考虑数据点之间的距离71数量属性的统计离散化挖掘之前利用概念层次离散化数值被范围(ranges)替代.关系数据库中,找出所有的频繁k-谓词(predicate)集要求

k

或k+1次表扫描.数据立方体(datacube)非常适合数据挖掘.N-维立方体的cells与谓词集(

predicatesets)相对应.通过数据立方体挖掘会非常快速.(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)72量化关联规则age(X,”30-34”)income(X,”24K-48K”)buys(X,”highresolutionTV”)数值属性动态离散化这样挖掘的规则的可信度或紧密度最大化2-维量化关联规则:Aquan1

Aquan2Acat示例73量化关联规则ARCS:AssociationRuleClusteringSystem(关联规则聚类系统)

借鉴了图像处理中的思想.本质上,这种方法映射一对数量属性到满足给定的分类属性条件的2-维元组格.然后对栅格搜索找到聚类点,由其生成关联规则.ARCS步骤:装箱(Binning)找出频繁谓词集(predicatesets)聚类关联规则

74量化关联规则装箱(Binning):划分过程被认为是装箱,即称作间隔为箱柜(bins).三种常用装箱策略是:

Equiwidthbinning,wheretheintervalsizeofeachbinisthesameEquidepth:whereeachbinhasapproximatelythesamenumberoftuplesassignedtoitHomogeneity-basedbinning,wherebinsizeisdeterminedsothatthetuplesineachbinareuniformlydistributed.75量化关联规则找出频繁谓词集:Oncethe2-Darraycontainingthecountdistributionforeachcategoryissetup,thiscanbescannedinordertofindthefrequentpredicatesetsthatalsosatisfyminimumconfidence.聚类关联规则:age(X,”34-35”)income(X,”31K-50K”)buys(X,”highresolutionTV”)76ARCS(AssociationRulesClusteringSystem)ARCS1.Binning2.FrequentItemsSet3.Clustering4.Optimization77ARCS:成功的应用聚类的概念到分类中.但仅限于基于2-维规则的分类,如ABClassi

的格式所示利用装箱(Binning)方法将数据属性值离散化,因此ACRS的准确度与使用的离散化程度强烈相关.ARCS的特点78基于关联规则的分类(ClassificationBasedonAssociationrules,CBA)分类规则挖掘与关联规则挖掘目标一个小的规则集作为分类器所有规则依照最小支持度与最小可信度语法(Syntax)XyXY79为何及如何结合分类规则挖掘与关联规则挖掘都是实际应用中必需的.结合着眼于关联规则的一个特定子集,其右件限制为分类的类属性.CARs:ClassAssociationRules80CBA:三个步骤若有连续值,则离散化.生成所有的classassociationrules(CARs)构建一个若干生成的CARs的分类器.81CAR集生成完整的CARs的集合,其满足用户指定的最小支持度与最小可信度约束.由CARs构建一个分类器.82规则生成:基本概念规则项(Ruleitem)

<condset,y>:条件集condset是一个项集,y是一个类标签(classlabel)

每个规则项表示一个规则:condset->y条件集支持度(condsupCount)D中包含condset的事例(case)数规则支持度(rulesupCount)D中包含condset及标注类别y的事例(case)数支持度Support=(rulesupCount/|D|)*100%可信度Confidence=(rulesupCount/condsupCount)*100%83规则生成:基本概念(Cont.)频繁规则项(frequentruleitems)一个规则项是频繁的,当其支持度不小于最小支持度

minsup.精确规则(Accuraterule)一个规则是精确的,当其可信度不小于最小可信度

minconf.潜在规则(Possiblerule)对所有包含同样条件集condset的规则项,可信度最大的规则项为这一规则项集合的潜在规则.类别关联规则classassociationrules(CARs)包含所有的潜在规则possiblerules(PRs),其即是频繁的又是精确的.84规则生成:一个示例一个规则项:<{(A,1),(B,1)},(class,1)>假定条件集condset(condsupCount)

的支持度计数为3,规则项ruleitem(rulesupCount)

的支持度计数为2,|D|=10则(A,1),(B,1)->(class,1)[supt=20%(rulesupCount/|D|)*100%confd=66.7%(rulesupCount/condsupCount)*100%]85RG:算法1F1={large1-ruleitems};2CAR1=genRules(F1);3prCAR1=pruneRules(CAR1);//counttheitemandclassoccurrencestodeterminethefrequent1-ruleitemsandpruneit4for(k=2;Fk-1

Ø;k++)doCk

=candidateGen(Fk-1);//generatethecandidateruleitemsCkusingthefrequentruleitemsFk-16foreachdatacasedDdo//scanthedatabaseCd=ruleSubset(Ck

,d);//findalltheruleitemsinCkwhosecondsets

aresupportedbyd8foreachcandidatecCddo9c.condsupCount++;10ifd.class=c.classthen

c.rulesupCount++;//updatevarioussupportcountsofthecandidatesinCk11end12end86RG:算法(cont.)13Fk={cCk

|c.rulesupCount

minsup};//selectthosenewfrequentruleitemstoformFk14CARk=genRules(Fk

);//selecttheruleitemsbothaccurateandfrequent15prCARk

=pruneRules(CARk

);16end17CARs=

kCARk

;18prCARs=

kprCARk

;87分类构建器M1:基本概念给定两个规则riandrj,定义:ri

rj

当ri的可信度大于rj的,或者它们的可信度相同,但ri的支持度大于rj的,或者它们的可信度与支持度都相同,但ri

比rj生成的早.我们的分类器如下面格式所示:<r1,r2,…,rn,default_class>,whereriR,ra

rbifb>a88M1:三个步骤基本思想是选择R中一个优先规则(highprecedence)的集合来覆盖D.对生成的规则集R排序.根据已排好的序列从R中选择为分类所用的规则并放入C每个选择的规则必须正确分类至少一个增加的事例(case).并选择默认的属性和计算误差.抛弃C中的不能改进分类器的准备度的规则.保留那些最小误差的规则的位置,抛弃序列中的其余规则.89M1:Algorithm1R=sort(R);//Step1:sortRaccordingtotherelation“”2foreachruler

Rinsequencedo3temp=Ø;4foreachcased

Ddo//gothroughDtofindthosecasescoveredbyeachruler5ifdsatisfiestheconditionsofrthen6stored.idintempandmarkrifitcorrectlyclassifiesd;7ifrismarkedthen8insertrattheendofC;//rwillbeapotentialrulebecauseitcancorrectlyclassifyatleastonecased9deleteallthecaseswiththeidsintempfromD;10selectingadefaultclassforthecurrentC;//themajorityclassintheremainingdata11computethetotalnumberoferrorsofC;12end13end//Step214FindthefirstrulepinCwiththelowesttotalnumberoferrorsanddropalltherulesafterpinC;15AddthedefaultclassassociatedwithptoendofC,andreturnC(ourclassifier).//Step390M1:满足的两个条件Eachtrainingcaseiscoveredbytherulewiththehighestprecedenceamongtherulesthatcancoverthecase.EveryruleinCcorrectlyclassifiesatleastoneremainingtrainingcasewhenitischosen.91

MOUCLASAssumption:MOUCLASalgorithmassumesthattheinitialassociationrulescanbeagglomeratedintoclusteringregionsTheimplicationoftheformoftheMouclasPattern(socalledMP):Cluster(D)t

y

whereCluster(D)tisaclusterofD,t=1tom,andy

isaclasslabel.

92MOUCLASDefinitions:FrequencyofMouclasPatternsAccuracyofMouclasPatternsReliabilityofMouclasPatternsTaskofMouclas:

TodiscoverMPsthathavesupportandconfidencegreaterthantheuser-specifiedminimumsupportthreshold(calledminsup),andminimumconfidencethreshold(calledminconf)andminimumreliabilitythreshold(calledminR)respectively,andtoconstructaclassifierbaseduponMPs.

93TheMOUCLASalgorithm

Twosteps:Step1.Discoveryofthefrequentandaccurate

andreliable

MPs.Step2.Constructionofaclassifier,calledDe-MP,basedonMPs.94TheMOUCLASalgorithm

ThecoreofthefirststepintheMouclasalgorithmistofindall

cluster_rulesthatsatisfy

minsupandminconf

and

minR.LetCdenotethedatasetDafterdimensionalityreductionprocessing.Acluster_rulerepresentsaMP,namelyarule:cluset

y,

whereclusetisasetofitemsetsfromaclusterCluster(C)t,yisaclasslabel,y

Y.95TheMOUCLASalgorithmAlgorithmofthefirststep:MouclasMiningfrequentandaccurateandreliableMouclaspatterns(MPs)Input:Atrainingtransactiondatabase,D;minimumsupportthreshold(minsup);minimumconfidencethreshold(minconf);minimumreliabilitythreshold(minR)Output:Asetoffrequentandaccurate

andreliableMouclas

patterns(MPs)96TheMOUCLASalgorithmMethods:(1)

Reducethedimensionalityoftransactionsd,whichefficientlyreducesthedatasizebyremovingirrelevantorredundantattributes(ordimensions)fromthetrainingdata,and(2)

IdentifytheclustersofdatabaseCforalltransactionsdafterdimensionalityreductiononattributesAj

indatabaseC,basedontheMountainfunction,whichisafuzzysetmembershipfunction,andspeciallycapableoftransformingquantitativevaluesofattributesintransactionsintolinguisticterms,and(3)

GenerateasetofMPsthatarebothfrequentandaccurate,namely,whichsatisfytheuser-specifiedminimumsupport(calledminsup)andminimumconfidence(calledminconf)andminimumreliability(calledminR)

constraints.97TheMOUCLASalgorithm1X=reduceDim(I);//reducethedimensionalityonthesetofallitemsIofinD2Cluster(C)t=genCluster(C);//identifythecompleteclustersofC

3foreachCluster(C)tdo

E=genClusterrules(cluset,class);//generateasetofcandidatecluster_rules

4foreachtransactiond

C

do

5Ed=genSubClusterrules(E,d);//findallthecluster_rulesinEwhoseclusetaresupported

byd6foreache

Ed

do7e.clusupCount++;//accumulatetheclusupCountoftheclusetofcluster_rule

e8ifd.class=e.classthene.cisupCount++//accumulatethecisupCountofcluster_rule

e

supportedbyd9end10end11F={e

E

e.cisupCount

minsupi};//constructthesetoffrequentcluster_rules12MP=genRules(F);//generateMPusingthegenRulesfunctionbyminconfandminR13end14MPs=∪

MP;//discoverthefinalsetofMPs

98TheMOUCLASalgorithm

ThetaskofthesecondstepinMouclasalgorithm:Usingaheuristicmethodtogenerateaclassifier,namedDe-MP,wherethediscoveredMPscancoverDandareorganizedaccordingtoadecreasingprecedencebasedontheirconfidenceandsupport.SupposeRbethesetoffrequentandaccurateandreliableMPswhicharegeneratedinthepaststep,andMPdefault_classdenotesthedefaultclass,whichhasthelowestprecedence.WecanthenpresenttheDe-MPclassifierintheformof<MP1,MP2,…,MPn,MPdefault_class>,whereMPi

R,i=1ton,MPa

≻MPb

ifn

b>a

1anda,bi,C

∪clusetofMPi99TheMOUCLASalgorithmAlgorithm:Mouclas

constructingDe-MPClassifierInput:Atrainingdatabaseafterdimensionalityreduction,C;Thesetoffrequentandaccurateandreliable

Mouclaspatterns(MPs)Output:

De-MPClassifierMethods:(1)

IdentifytheorderofalldiscoveredMPsbasedonthedefinitionofprecedenceandsequencethemaccordingtodecreasingprecedenceorder.(2)

DeterminepossibleMPsforDe-MPclassifierfromRfollowingthedescendingsequenceofMPs.(3)

DiscardtheMPswhichcannotcontributetotheimprovementoftheaccuracyoftheDe-MPclassifierandkeepthefinalsetofMPstoconstructtheDe-MPclassifier.100TheMOUCLASalgorithm1R=sort(R);//sortMPsbasedontheirprecedence2foreachMPRinsequencedo3temp=;4foreachtransactiond

Cdo5ifdsatisfiestheclusetofMPthen6stored.IDintemp;7

if

MPcorrectlyclassifiesd

then

8insertMPattheendofL;9deletethetransactionwhohasIDintempfromC;10

selectingadefaultclassforthecurrentL;//determinethedefaultclassbasedonmajorityclassofremainingtransactionsinC11end12computethetotalnumberoferrorsofL;//computethetotalnumberoferrorsthataremadebythecurrentLandthedefaultclass13end14FindthefirstMP

inLwiththelowesttotalnumberoferrorsanddiscardalltheMPsaftertheMPinL;15AddthedefaultclassassociatedwiththeabovementionedfirstMPtoendofL;16De-MPclassifier=L

101ExampleofMOUCLASapplicationThewellloggingdatasetsincludeattributes(wellloggingcurves)ofGR(gammaray),RDEV(deepresistivity),RMEV(shallowresistivity),RXO(flushedzoneresistivity),RHOB(bulkdensity),NPHI(neutronporosity),PEF(photoelectricfactor)andDT(sonictraveltime).AhypotheticallyusefulMPmaysuggestarelationbetweenwellloggingdataandtheclasslabelofoil/gasformationsince.102MiningDistance-basedAssociationRulesBinningmethodsdonotcapturethesemanticsofintervaldataDistance-basedpartitioning,moremeaningfuldiscretizationconsidering:density/numberofpointsinaninterval“closeness”ofpointsinaninterval103InterestingnessMeasure:Correlations(Lift)playbasketball

eatcereal[40%,66.7%]ismisleadingTheoverallpercentageofstudentseatingcerealis75%whichishigherthan66.7%.playbasketball

noteatcereal[20%,33.3%]ismoreaccurate,althoughwithlowersupportandconfidenceMeasureofdependent/correlatedevents:liftBasketballNotbasketballSum(row)Cereal200017503750Notcereal10002501250Sum(col.)300020005000104内容提要

引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结105相关规则(CorrelationRules)“BeyondMarketBaskets,”Brinetal.假设执行关联规则挖掘ccrowt20525t70575col9010100tea=>coffee20%support80%confidencebut90%ofthepeoplebuycoffeeanyway!106相关规则一种度量是计算相关性若两个随机变量A和B是统计独立的对tea和coffee:107相关规则利用2

统计检验来测试独立性设n为购物篮的总数设k为考虑的项的总数设r为一个包含项(ij,ij)的规则设O(r)表示包含规则r的购物篮的数量(即频率)对单个项ij,设E[ij]=O(ij)(反过来即为n-E[ij])E[r]=n*E[r1]/n*…*E[rk]/n108相关规则2

统计量定义为LookupforsignificancevalueinastatisticaltextbookTherearek-1degreesoffreedomIftestfailscannotrejectindependence,otherwisecontigencytablerepresentsdependence.109示例BacktoteaandcoffeeE[t]=25,E[t]=75,E[c]=90,E[c]=10E[tc]=100*25/100*90/100=22.5O(tc)=20Contrib.to2=(20-22.5)2/22.5=0.278Calculatefortheresttoget2=2.204Notsignificantat95%level(3.84fork=2)Cannotrejectindependenceassumptionccrowt20525t70575col9010100110兴趣度（Interest）If2testshowssignificance,thenwanttofindmostinterestingcell(s)intableI(r)=O(r)/E[r]Lookforvaluesfarawayfrom1I(tc)=20/22.5=0.89I(tc)=5/2.5=2I(tc)=70/67.5=1.04I(tc)=5/7.5=0.66111