关联算法简介 apriori算法，fp-tree算法

《关联算法简介 apriori算法，fp-tree算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据挖掘:概念和技术—Chapter6—2001-11-61数据挖掘：概念和技术第6章：从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-62数据挖掘：概念和技术什么是关联挖掘?关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计、loss-leaderanalysi

2、s、聚集、分类等。举例：规则形式：“Body®Head[support,confidence]”.buys(x,“diapers”)®buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)®grade(x,“A”)[1%,75%]2001-11-63数据挖掘：概念和技术关联规则：基本概念给定:(1)交易数据库(2)每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则E.g.,98%ofpeoplewhopurchasetir

3、esandautoaccessoriesalsogetautomotiveservicesdone应用*护理用品(商店应该怎样提高护理用品的销售？)家用电器*(其他商品的库存有什么影响?)在产品直销中使用附加邮寄Detecting“ping-pong”ingofpatients,faulty“collisions”2001-11-64数据挖掘：概念和技术规则度量：支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,包含{X、Y}的交易中也包含Z的条件概率设最小

4、支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户2001-11-65数据挖掘：概念和技术关联规则挖掘：路线图布尔vs.定量关联(基于处理数据的类型)buys(x,“SQLServer”)^buys(x,“DMBook”)®buys(x,“DBMiner”)[0.2%,60%]age(x,“30..39”)^income(x,“42..48K”)®buys(x,“PC”)[1%,75%]单维vs.多维关联(例子同上)单层vs.多层分析那个品种牌子

5、的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小东西”的销售促发了“大家伙”的买卖？2001-11-66数据挖掘：概念和技术第6章：从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-67数据挖掘：概念和技术关联规则挖掘—一个例子对于AC：support=support({A、C})=50%confiden

6、ce=support({A、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的最小值尺度50%最小可信度50%2001-11-68数据挖掘：概念和技术关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如,如果{AB}是频繁集，则{A}{B}也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则2001-11-69数据挖掘：概念和技术Apriori算法连接:用Lk-1自连接得到Ck修剪:一个k-项集，如果他的一个k-1项集（他的

7、子集）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin

8、_supportendreturnkLk;2001-11-610数据挖掘：概念和技术Apriori算法—例子数据库D扫描DC1L1L2C2C2扫描DC3L3扫描D2001-11-611数据挖掘：概念和技术如何生成候选集假定Lk-1中的项按顺序排列