《数据挖掘关联规则.ppt》由会员分享，可在线阅读，更多相关《数据挖掘关联规则.ppt（140页珍藏版）》请在三一办公上搜索。
1、1,关联规则 Association Rules,2,内容提要,引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结,3,关联规则,关联规则表示了项之间的关系示例:cereal,milk fruit“买谷类食品和牛奶的人也会买水果.”商店可以把牛奶和谷类食品作特价品以使人们买更多的水果.,4,市场购物篮分析,分析事务数据库表我们是否可假定?Chips=Salsa Lettuce=Spinach,5,基本概念,通常,数据包含:,事务 ID,项的子集,6,关联规则挖掘,在事务数据库,关系数据库和其它信息库中
2、的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.频繁模式:数据库中出现频繁的模式(项集,序列,等等),7,基本概念,项集事务关联规则事务数据集(例如右图)事务标识 TID：每一个事务关联着一个标识,8,度量有趣的关联规则,支持度sD中包含A和 B 的事务数与总的事务数的比值规则 AB 在数据集D中的支持度为s,其中s 表示D中包含AB(即同时包含A和B)的事务的百分率.,9,度量有趣的关联规则,可信度 cD中同时包含A和B的事务数与只包含A的事务数的比值,规则 AB 在数据集D中的可信度为c,其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B|A)表示.con
3、fidence(A B)=P(B|A)条件概率 P(B|A)表示A发生的条件下B也发生的概率.,10,度量有趣的关联规则,关联规则根据以下两个标准(包含或排除):最小支持度 表示规则中的所有项在事务中出现的频度最小可信度-表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度,11,市场购物篮分析,I是什么?事务ID B的T是什么?s(Chips=Salsa)是什么?c(Chips=Salsa)是什么?,12,Step one:频繁项集,项集 任意项的集合k-项集 包含k个项的项集频繁(或大)项集 满足最小支持度的项集若I包含m个项,那么可以产生多少个项集?,13,Step two:强关
4、联规则,给定一个项集,容易生成关联规则.项集:Chips,Salsa,BeerBeer,Chips=SalsaBeer,Salsa=ChipsChips,Salsa=Beer强规则是有趣的强规则通常定义为那些满足最小支持度和最小可信度的规则.,14,关联规则挖掘,两个基本步骤Step one:找出所有的频繁项集满足最小支持度Step two:找出所有的强关联规则由频繁项集生成关联规则保留满足最小可信度的规则,15,内容提要,引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结,16,生成频繁项集,Nav
5、e algorithmn-|D|for each subset s of I do l-0 for each transaction T in D do if s is a subset of T then l-l+1 if minimum support=l/n then add s to frequent subsets,17,生成频繁项集,nave algorithm的分析I 的子集:O(2m)为每一个子集扫描n个事务测试s为T的子集:O(2mn)随着项的个数呈指数级增长!我们能否做的更好?,18,Apriori 性质,定理(Apriori 性质):若A是一个频繁项集,则A的每一个子集都
6、是一个频繁项集.证明:设n为事务数.假设A是l个事务的子集,若 A A,则A 为l(l l)个事务的子集.因此,l/n s(最小支持度),l/n s也成立.,19,Apriori 算法,Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.思想:Apriori 使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集.首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描.,20,
7、生成频繁项集,中心思想:由频繁(k-1)-项集构建候选k-项集方法找到所有的频繁1-项集扩展频繁(k-1)-项集得到候选k-项集剪除不满足最小支持度的候选项集,21,Apriori:一种候选项集生成-测试方法,Apriori 剪枝原理:若任一项集是不频繁的,则其超集不应该被生成/测试!方法:由频繁k-项集生成候选(k+1)-项集,并且在DB中测试候选项集性能研究显示了Apriori算法是有效的和可伸缩(scalablility)的.,22,The Apriori 算法一个示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd sca
8、n,23,加权关联规则挖掘,传统的关联规则挖掘算法通常都认为数据库里每个项目都有相同的重要性，没有主要、次要之分。但在实际中，往往存在一类这样的情况：用户对每个项目的看重程度不一样，有的项目是用户最看重、最关心的，有的项目是用户关注性不大，因此需要引进权重的概念。,24,加权关联规则的描述,设 是项的集合，每个项都有一个权值与之对应。它们的权值分别是w1,w2,wk（wi 0,1）。事先指定最小加权支持度阈值为 wminsup和最小置信度阈值 minconf。对于项目集X，如果 wsup(X)wminsup，则 X 是加权频繁的。形如X Y 的关联规则的加权支持度为：置 信 度 的 定 义 仍
9、 然 沿 用 Apriori算 法 里 的 定 义，即：conf(X Y)=sup(X Y)/sup(X)。,25,加权关联规则的描述,对于项目集 X、Y，X Y=，如果有 wsup(X Y)wminsup，且 conf(XY)minconf，则称 XY 是一条加权关联规则。,26,权值的设定,加权支持度(1)、平均值：(2)、归一化：(3)、最大值：,27,Apriori 算法,Algorithm:Apriori输入:Database,D,of transactions;minimum support threshold,min_sup.输出:L,freuqent itemsets in D
10、.过程:Ck:Candidate itemset of size kLk:frequent itemset of size kL1=find_frequent_1_itemsets(D);for(k=2;Lk+1!=;k+)do begin Ck=apriori_gen(Lk-1,min_sup);for each transaction t in database D do/scan D for counts Ct=subset(Ck,t);/get the subsets of t that are candidates For each candidate c Ct c.count+;L
11、k=candidates in Ck with min_support endreturn L=k Lk;,28,Apriori 算法,Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets;min_sup:minimum support threshold)for each itemset l1 Lk-1 for each itemset l2Lk-1 if(l11=l21)(l12=l22)(l1k-1=l2k-1)Then c=join(l1,l2)/join step:generate candidates if has_infrequent
12、_subset(c,Lk-1)then delete c;/prune step:remove unfruitful candidate else add c to Ckreturn Ck,29,Apriori 算法,Join is generate candidates set of itemsets Ck from 2 itemsets in Lk-1Procedure join(p,q)insert into Ck select p.item1,p.item2,.,p.itemk-1,q.itemk-1 from Lk-1 p,Lk-1 q where p.item1=q.item1,.
13、,p.itemk-2=q.itemk-2,p.itemk-1=q.itemk-1,30,Apriori 算法,Procedure has_infrequent_subset(c:candidate k-itemset;Lk-1:frequent(k-1)-itemsets;)/use prior knowledge for each(k-1)-subset s of c if s Lk-1 then return TRUE;return FALSE.,31,Apriori算法的重要细节,如何生成候选项集?步骤 1:自连接 Lk步骤 2:剪枝如何计算候选项集的支持度?候选项庥生成的示例L3=ab
14、c,abd,acd,ace,bcd 自连接:L3*L3由abc 和abd 连接得到abcd 由acd 和ace 连接得到acde剪枝:因为ade 不在L3中acde 被剪除C4=abcd,32,如何生成候选项集?,假定Lk-1中的项以一定顺序排列步骤 1:自连接 Lk-1 insert into Ckselect p.item1,p.item2,p.itemk-1,q.itemk-1from Lk-1 p,Lk-1 qwhere p.item1=q.item1,p.itemk-2=q.itemk-2,p.itemk-1 q.itemk-1步骤 2:剪枝forall itemsets c in
15、Ck doforall(k-1)-subsets s of c doif(s is not in Lk-1)then delete c from Ck,33,如何计算候选项集的支持度?,为何候选项集的支持度的计算是一个问题?候选项集的总数可能是巨大的 一个事务可能包含多个候选项集方法:候选项集被存储在一个哈希树哈希树的叶子结点包含一个项集和计数的列表内部结点 包含一个哈希表子集函数:找出包含在一个事务中的所有候选项集,34,频繁模式挖掘的挑战,挑战多次扫描事务数据库巨大数量的候选项集繁重的计算候选项集的支持度工作改进 Apriori:大体的思路减少事务数据库的扫描次数缩减候选项集的数量使候选项
16、集的支持度计算更加方便,35,内容提要,引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结,36,频繁模式挖掘的瓶颈,多次扫描数据库是高代价的长模式的挖掘需要多次扫描数据库以及生成许多的候选项集找出频繁项集 i1i2i100扫描次数:100候选项集的数量:(1001)+(1002)+(110000)=2100-1=1.27*1030!瓶颈:候选项集-生成-测试我们能否避免生成候选项集?,37,不生成候选项集的频繁模式挖掘,利用局部频繁的项由短模式增长为长模式“abc”是一个频繁模式得到所有包含“abc
17、”的事务:DB|abc“d”是 DB|abc 的一个局部频繁的项 abcd 是一个频繁模式,38,FP Growth算法(Han,Pei,Yin 2000),Apriori算法的一个有问题的方面是其候选项集的生成指数级增长的来源另一种方法是使用分而治之的策略(divide and conquer)思想:将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树,39,利用FP-树进行频繁模式挖掘,思想:频繁模式增长递归地增长频繁模式借助模式和数据库划分方法 对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树.对每个新创建的条件FP-树重复上述过程直至结果FP-树为空,或者它仅包含一个单一路
18、径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式.,40,频繁 1-项集,最小支持度为20%(计数为 2),事务数据库 支持度计数 频繁1-项集,41,FP-树 构建,按支持度降序排列,42,FP-树 构建,扫描数据库 事务1:I1,I2,I5 排序:I2,I1,I5,处理事务 以项的顺序增加结点 标注项及其计数,43,FP-树 构建,null,(I2,2),(I4,1),44,FP-树 构建,null,(I2,7),(I4,1),(I3,2),(I3,2),(I1,2),(I3,2),(I4,1),(I5,1),45,FP-树 构建,扫描事务数据库D一次,得到频繁项的集合F及它
19、们的支持度.将F按支持度降序排列成L,L是频繁项的列表.创建FP-树的根,标注其为NULL.对D中的每个事务进行以下操作:根据 L中的次序对事务中的频繁项进行选择和排序.设事务中的已排序的频繁项列表为p|P,其中p表示第一个元素,P表示剩余的列表.调用insert_Tree(p|P,T).,46,FP-树 构建,Insert_Tree(p|P,T)If T has a child N such that N.item-name=p.item-name,then increment Ns count by 1;else create a new node N,and let its count
20、be 1,its parent link be linked to T,and its node-link to the nodes with the same item-name via the node-link structure.If P is nonempty,call insert_tree(P,N)recursively.,47,挖掘 FP-tree,从索引表中的最后一个项开始找到所有包含该项的路径沿着结点-链接(node-links)确定条件模式路径中符合频度要求的模式构建 FP-tree C添加项至C中所有路径,生成频繁模式递归地挖掘C(添加项)从索引表和树中移除项,48,挖
21、掘 FP-Tree,null,(I2,7),(I1,4),(I4,1),(I3,2),(I3,2),(I4,1),(I5,1),(I1,2),(I3,2),前缀路径(I2 I1,1)(I2 I1 I3,1)条件路径(I2 I1,2)条件 FP-tree(I2 I1 I5,2),(I2 I5,2),(I1 I5,2),null,(I2,2),(I1,2),49,挖掘 FP-Tree,50,挖掘 FP-Tree,Procedure FP_growth(Tree,)If Tree contains a single path P then for each combination(denote as
22、)of the nodes in the path P generate pattern with support=minisup of nodes in;Else for each ai in the header of Tree generate pattern=ai with support=ai.support;construct,s conditional pattern base and then conditional FP_tree Tree;IF Tree then call FP_growth(Tree,);,51,由事务数据库构建FP-树,min_support=3,TI
23、DItems 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,o,wf,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p,扫描DB一次,找到频繁1项(单一项模式)按支持度降序对频繁项排序为 F-list再次扫描DB,构建FP-tree,F-list=f-c-a-b-m-p,52,划分模式和数据库,频繁模式根据F-list可以被划分为若干子集F-list=f-c-a-b-m-p包含 p的模式包含 m 但包含 p的模
24、式包含 c 但不包含 a,b,m,p的模式模式 f完整性 和 非冗余性,53,从P的条件数据库找出包含P的模式,从 FP-tree的索引表的频繁项开始沿着每个频繁项p的链接遍历 FP-tree累积项p的所有转换前缀路径来形成的p的条件模式基,条件模式基项 条件模式基cf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1,54,递归:挖掘每个条件FP-tree,“am”的条件模式基:(fc:3),“cm”的条件模式基:(f:3),f:3,cm-条件 FP-tree,“cam”的条件模式基:(f:3),f:3,cam-条件 FP-tree,55,一个特例:
25、FP-tree中的单一前缀路径,假定(条件的)FP-tree T 有一个共享的单一前缀路径 P挖掘可以分为两部分将单一前缀路径约简为一个结点将两部分的挖掘结果串联,+,56,通过 DB 投影(Projection)使FP-growth可伸缩,FP-tree 不能全放入内存?DB 投影首先将一个数据库划分成一个由若干投影(Projected)数据库组成的集合然后对每个投影数据库构建和挖掘 FP-treeParallel projection vs.Partition projection 技术Parallel projection is space costly,57,Partition-bas
26、ed Projection,Parallel projection 需要很多磁盘空间Partition projection 节省磁盘空间,58,改进途径,使用哈希表存储候选k-项集的支持度计数移除不包含频繁项集的事务对数据采样划分数据若一个项集是频繁的,则它必定在某个数据分区中是频繁的.,59,FP-tree 结构的优点,完整性 保持了频繁项集挖掘的完整信息没有打断任何事务的长模式紧密性减少不相关的信息不频繁的项没有了项按支持度降序排列:越频繁出现,越可能被共享决不会比原数据库更大(不计结点链接和计数域)对 Connect-4 数据库,压缩比率可以超过100,60,FP-Growth vs.
27、Apriori:支持度的可伸缩性,Data set T25I20D10K,61,FP-Growth vs.Tree-Projection:支持度的可伸缩性,Data set T25I20D100K,62,关联规则可视化:方格图(Pane Graph),63,关联规则可视化:规则图(Rule Graph),64,内容提要,引言Apriori 算法Frequent-pattern tree 和FP-growth 算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结,65,挖掘多种规则或规律,多层(Multi-level),量化(quantitative)关联规则,相关(correlation)和
28、因果(causality),比率(ratio)规则,序列(sequential)模式,浮现(emerging)模式,temporal associations,局部周期(partial periodicity)分类(classification),聚类(clustering),冰山立方体(iceberg cubes),等等.,66,多层关联规则,项常常构成层次可伸缩的(flexible)支持度设置:在较低层的项预期有较低的支持度.事务数据库可以基于维度和层次编码探寻共享多层挖掘,67,可伸缩的支持度约束的多层/多维(ML/MD)关联规则,为什么设置可伸缩的支持度?实际生活中项的出现频率变化巨大
29、在一个商店购物篮中的钻石,手表,钢笔统一的支持度未必是一个有趣的模型一个可伸缩模型较低层的,较多维的组合以及长模式通常具有较小的支持度总体规则应该要容易说明和理解特殊的项和特殊的项的组合可以特别设定(最小支持度)以及拥有更高的优先级,68,多维关联规则,单维规则:buys(X,“milk”)buys(X,“bread”)多维规则:2 个维度或谓词(predicates)跨维度(Inter-dimension)关联规则(无重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维度(hybrid-dimension)关联规则(重复谓词)
30、age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类(Categorical)属性有限的几个可能值,值之间不可排序数量(Quantitative)属性数值的,值之间有固有的排序,69,多层关联规则:冗余滤除,根据项之间的”先辈”(ancestor)关系,一些规则可能是冗余的.示例milk wheat bread support=8%,confidence=70%2%milk wheat bread support=2%,confidence=72%我们说第1个规则是第2个规则的先辈.一个规则是冗余的,当其支持度接近基于先辈规则的”预期”(expecte
31、d)值.,70,多层关联规则:逐步深化(Progressive Deepening),一个自上而下的,逐步深化的方法:首先挖掘高层的频繁项:milk(15%),bread(10%)然后挖掘它们的较低层”较弱”(weaker)频繁项:2%milk(5%),wheat bread(4%)多层之间不同的最小支持度阈值导致了不同的算法:如果在多个层次间采用了相同的最小支持度,若t的任何一个先辈都是非频繁的则扔弃(toss)t.如果在较低层采用了减少的最小支持度，则只检验那些先辈的支持度是频繁的不可忽略的派生（descendents）即可,71,多维关联规则挖掘的技术,搜索频繁 k-谓词集(predic
32、ate set):示例:age,occupation,buys是一个 3-谓词集以age处理的方式,技术可以如下分类1.利用数量属性的统计离散(static discretization)方法 利用预先确定的概念层次对数量属性进行统计离散化2.量化关联规则基于数据的分布,数量属性被动态地离散化到不同的容器空间(bins)3.基于距离(Distance-based)的关联规则这是一个动态离散化的过程,该过程考虑数据点之间的距离,72,数量属性的统计离散化,挖掘之前利用概念层次离散化数值被范围(ranges)替代.关系数据库中,找出所有的频繁k-谓词(predicate)集要求 k 或 k+1次表
33、扫描.数据立方体(data cube)非常适合数据挖掘.N-维立方体的 cells 与谓词集(predicate sets)相对应.通过数据立方体挖掘会非常快速.,73,量化关联规则,age(X,”30-34”)income(X,”24K-48K”)buys(X,”high resolution TV”),数值属性动态离散化这样挖掘的规则的可信度或紧密度最大化2-维 量化关联规则:Aquan1 Aquan2 Acat示例,74,量化关联规则,ARCS:Association Rule Clustering System(关联规则聚类系统)借鉴了图像处理中的思想.本质上,这种方法映射一对数量属性
34、到满足给定的分类属性条件的2-维元组格.然后对栅格搜索找到聚类点,由其生成关联规则.ARCS 步骤:装箱(Binning)找出频繁谓词集(predicate sets)聚类关联规则,75,量化关联规则,装箱(Binning):划分 过程被认为是装箱,即称作间隔为箱柜(bins).三种常用装箱策略是:Equiwidth binning,where the intervalsize of each bin is the same Equidepth:where each bin has approximately the same number of tuples assigned to it H
35、omogeneity-based binning,where bin size is determined so that the tuples in each bin are uniformly distributed.,76,量化关联规则,找出频繁谓词集:Once the 2-D array containing the count distribution for each category is set up,this can be scanned in order to find the frequent predicate sets that also satisfy minimu
36、m confidence.聚类关联规则:,age(X,”34-35”)income(X,”31K-50K”)buys(X,”high resolution TV”),77,ARCS(Association Rules Clustering System),ARCS 1.Binning2.Frequent Items Set3.Clustering4.Optimization,78,ARCS:成功的应用聚类的概念到分类中.但仅限于基于2-维规则的分类,如A B Classi 的格式所示利用装箱(Binning)方法将数据属性值离散化,因此ACRS的准确度与使用的离散化程度强烈相关.,ARCS 的
37、特点,79,基于关联规则的分类(Classification Based on Association rules,CBA),分类规则挖掘与关联规则挖掘目标一个小的规则集作为分类器所有规则依照最小支持度与最小可信度语法(Syntax)X yX Y,80,为何及如何结合,分类规则挖掘与关联规则挖掘都是实际应用中必需的.结合着眼于关联规则的一个特定子集,其右件限制为分类的类属性.CARs:Class Association Rules,81,CBA:三个步骤,若有连续值,则离散化.生成所有的 class association rules(CARs)构建一个若干生成的CARs的分类器.,82,CA
38、R集,生成完整的CARs的集合,其满足用户指定的最小支持度与最小可信度约束.由 CARs构建一个分类器.,83,规则生成:基本概念,规则项(Ruleitem):条件集 condset 是一个项集,y 是一个类标签(class label)每个规则项表示一个规则:condset-y条件集支持度(condsupCount)D中包含condset的事例(case)数规则支持度(rulesupCount)D中包含condset 及标注类别 y的事例(case)数支持度Support=(rulesupCount/|D|)*100%可信度Confidence=(rulesupCount/condsupCo
39、unt)*100%,84,规则生成:基本概念(Cont.),频繁规则项(frequent ruleitems)一个规则项是频繁的,当其支持度不小于最小支持度 minsup.精确规则(Accurate rule)一个规则是精确的,当其可信度不小于最小可信度 minconf.潜在规则(Possible rule)对所有包含同样条件集condset的规则项,可信度最大的规则项为这一规则项集合的潜在规则.类别关联规则 class association rules(CARs)包含所有的潜在规则possible rules(PRs),其即是频繁的又是精确的.,85,规则生成:一个示例,一个规则项:假定条
40、件集 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%,86,RG:算法,1 F 1=large 1-ruleitems;2 CAR 1=genRules(F 1);3 prCAR 1=pruneRules(CAR 1);/count the item and class occurrences to dete
41、rmine the frequent 1-ruleitems and prune it4 for(k=2;F k-1;k+)doC k=candidateGen(F k-1);/generate the candidate ruleitems Ck using the frequent ruleitems Fk-16 for each data case d D do/scan the databaseC d=ruleSubset(C k,d);/find all the ruleitems in Ck whose condsets are supported by d8 for each c
42、andidate c C d do9 c.condsupCount+;10 if d.class=c.class then c.rulesupCount+;/update various support counts of the candidates in Ck11 end12 end,87,RG:算法(cont.),13 F k=c C k|c.rulesupCount minsup;/select those new frequent ruleitems to form Fk14 CAR k=genRules(F k);/select the ruleitems both accurat
43、e and frequent15 prCAR k=pruneRules(CAR k);16 end17 CARs=k CAR k;18 prCARs=k prCAR k;,88,分类构建器 M1:基本概念,给定两个规则 ri and rj,定义:ri rj 当ri的可信度大于 rj的,或者它们的可信度相同,但ri的支持度大于rj的,或者它们的可信度与支持度都相同,但 ri 比rj生成的早.我们的分类器如下面格式所示:,where ri R,ra rb if ba,89,M1:三个步骤,基本思想是选择R中一个优先规则(high precedence)的集合来覆盖 D.对生成的规则集R排序.根据已
44、排好的序列从R中选择为分类所用的规则并放入C每个选择的规则必须正确分类至少一个增加的事例(case).并选择默认的属性和计算误差.抛弃C中的不能改进分类器的准备度的规则.保留那些最小误差的规则的位置,抛弃序列中的其余规则.,90,M1:Algorithm,1 R=sort(R);/Step1:sort R according to the relation“”2 for each rule r R in sequence do3 temp=;4 for each case d D do/go through D to find those cases covered by each rule
45、r5 if d satisfies the conditions of r then6 store d.id in temp and mark r if it correctly classifies d;7 if r is marked then8 insert r at the end of C;/r will be a potential rule because it can correctly classify at least one case d9 delete all the cases with the ids in temp from D;10 selecting a de
46、fault class for the current C;/the majority class in the remaining data11 compute the total number of errors of C;12 end13 end/Step 214 Find the first rule p in C with the lowest total number of errors and drop all the rules after p in C;15 Add the default class associated with p to end of C,and ret
47、urn C(our classifier)./Step 3,91,M1:满足的两个条件,Each training case is covered by the rule with the highest precedence among the rules that can cover the case.Every rule in C correctly classifies at least one remaining training case when it is chosen.,92,MOUCLAS,Assumption:MOUCLAS algorithm assumes that
48、the initial association rules can be agglomerated into clustering regionsThe implication of the form of the Mouclas Pattern(so called MP):Cluster(D)t y where Cluster(D)t is a cluster of D,t=1 to m,and y is a class label.,93,MOUCLAS,Definitions:Frequency of Mouclas Patterns Accuracy of Mouclas Patter
49、ns Reliability of Mouclas PatternsTask of Mouclas:To discover MPs that have support and confidence greater than the user-specified minimum support threshold(called minsup),and minimum confidence threshold(called minconf)and minimum reliability threshold(called minR)respectively,and to construct a cl
50、assifier based upon MPs.,94,The MOUCLAS algorithm,Two steps:Step 1.Discovery of the frequent and accurate and reliable MPs.Step 2.Construction of a classifier,called De-MP,based on MPs.,95,The MOUCLAS algorithm,The core of the first step in the Mouclas algorithm is to find all cluster_rules that sat
