资源描述:
《bigdata数据挖掘培训1》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据挖掘DataMining2021/7/23三、数据挖掘技术11.基本概念2.有效的和可伸缩的频繁项集挖掘方法3.挖掘各种类型的关联规则4.由关联挖掘到相关分析5.分类与预测基本概念6.决策树技术挖掘动机什么产品经常被一同购买?啤酒和尿布?!买了PC后接下来会买什么?哪类DNA对新药敏感?能否对web文档自动分类?频繁项集、闭项集和关联规则概率论基本知识P(AB)发生A或发生B的概率P(B
2、A)A条件下B发生的概率事件相关性相互独立事件©datamining33.1基本概念:频繁模式与关联规则项集X={x1,…,xk}每个事务T是项
3、的集合关联规则是形如XY的蕴涵式,满足最小支持度和置信度支持度s,事务中同时包含项XY的概率置信度c,事务包含项X时也包含项Y的条件概率CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F关联规则挖掘的一般步骤(1)找出所有的频繁项集。support(X)≥supmin(2)由频繁项集产生强关联规则从大型数据库中挖掘频繁项集的主要困难在于将产生大量的频繁项集频
4、繁k项集:含k个频繁项一个长项集包含大量的频繁子项集的组合:n个频繁1项集,可能组合出的频繁项集C1n+C2n+…+Cnn=2n-1基本概念:闭项集和极大项集解决办法:挖掘闭项集和极大项集闭(频繁)项集:若不存在真超项集Y(YכX),使得Y与X在数据集S中有相同的支持度计数,则称项集X在S中是闭的。极大(频繁)项集:如果X是频繁的,并且不存在频繁的超项集Y使得YכX,称X是极大项集。闭项集包含了频繁项集的完整信息减少了频繁项集和规则的数量关联规则挖掘—一个例子对于规则AC:support=support({AC})=50%confi
5、dence=support({AC})/support({A})=66.6%Min.support50%Min.confidence50%思考:怎样编程提取关联规则?步骤?基本概念:闭项集和极大项集练习:min_sup为4数据库TIDitem1abc2abcd3bce4acde5de频繁项集:{b,c}3.2挖掘方法:Apriori使用候选项生成频繁项集Apriori算法是最有影响的挖掘关联规则频繁项集的算法。使用逐层搜索的迭代方法找到1到K项频繁项集;即由k项集搜索生成(k+1)项集。为提高频繁项集逐层产生的效率,利用Apriori
6、性质。Apriori性质、反单调性Apriori性质:频繁项集的所有非空子集也必须是频繁的。i.e.,如果{AB}是频繁项集,{A}和{B}都应该是频繁项集反单调性:如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试。Apriori算法思想(1)扫描数据库,累积每个项的支持度计数,生成频繁1项集集合L1;(2)扫描数据库,由L1构造、搜索频繁2项集L2;(3)同理,生成L3,…,直到不能生成频繁k项集。注:每次搜索都要扫描一遍数据库。TheAprioriAlgorithm算法伪码:Ck:Candidateitemsetofs
7、izekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;Apriori算法怎样产生候选项?连接步:为找Lk,通过将
8、Lk-1与其自身连接产生候选k项集集合Ck。例如,设l1和l2是Lk-1中的项集,如果它们的前(k-2)个项相同的话,则是可连接的。剪枝步:Ck是Lk的超集,即Ck中的成员可能是频繁的,也可能不是,但所有的频繁k项集都包含在Ck中。为压缩Ck,剪枝:任何非频繁的(k-1)-项集都不是频繁k项集的子集。产生候选项的例子设L3={abc,abd,acd,ace,bcd}自连接:L3*L3abcdfromabcandabdacdefromacdandace剪枝:删acde,因为ade不在L3中,即非频繁C4={abcd}Apriori算法示例
9、DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD怎样产生候选项?假设Lk-1中的项集都按序排列第一步:自连接Lk-1insertintoCkselectp.item1,p.ite