第八讲挖掘频繁模式关联和相关

厦门大学软件学院1第八讲挖掘频繁模式、关联和相关厦门大学软件学院2MiningFrequentPatterns,AssociationandCorrelations基本概念和线路图有效的和可伸缩的频繁项集挖掘方法挖掘各种类型的关联规则（自学）关联规则到相关分析基于约束的关联规则（自学）小结厦门大学软件学院3WhatIsFrequentPatternAnalysis?频繁模式（Frequentpattern）:频繁地出现在数据集中的模式（项集，子序列或子结构等）。提出：Agrawal,Imielinski,andSwami[AIS93]动机：寻找数据内部隐含的关联哪些商品频繁地被同时购买?—Beeranddiapers?!买了PC机之后客户经常还会购买哪些相关商品?哪种DNA对这种新病毒很敏感?我们能自动对Web上的文档进行分类吗?应用购物篮分析、交叉销售、目录设计、点击流分析、DNA序列分析……厦门大学软件学院4WhyIsFreq.PatternMiningImportant?挖掘数据集内在且重要的属性频繁模式是纵多数据挖掘基本任务的基础关联、相关与因果分析序列、结构（如“子图”）分析时空数据、多媒体数据、时间序列数据、流数据上的模式分析分类聚类分析:基于频繁模式的聚类数据仓库:冰山立方体基于语义的数据压缩……厦门大学软件学院5关联规则的分类方法根据规则中所处理的值类型布尔关联规则：考虑项的“在与不在”量化关联规则：量化的项或属性之间的关联Age(X,”30~39”)∧income(X,”42~48K”)=buys(X,”high_resolution_TV”)根据规则中所涉及的数据维(谓词)单维buys(X,”computer”)＝buys(X,”financial_management_software”)多维:见上例根据规则集所涉及的抽象层：单层、多层Age(X,“30~39”)=buys(X,”laptopcomputer”)Age(X,“30~39”)=buys(X,”computer”)厦门大学软件学院6根据挖掘模式的完全性频繁项集的完全集、闭频繁项集和极大频繁项集、被约束的频繁项集、近似频繁项集……根据挖掘的规则类型分类关联规则、相关规则、强梯度联系等根据挖掘的模式类型分类频繁项集挖掘、序列模式挖掘、结构模式挖掘厦门大学软件学院7基本概念项集：ItemsetX={x1,…,xk}找出满足规则XY的最小支持度与置信度support,s,probabilitythatatransactioncontainsXYconfidence,c,conditionalprobabilitythatatransactionhavingXalsocontainsYLetsupmin=50%,confmin=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}Associationrules:AD(60%,100%)DA(60%,75%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F厦门大学软件学院8关联规则形如A＝B的蕴涵式(AI,BI,AB=)D={t1,t2,..tk..tn}tk={i1,i2,…im..ip},im称为项目ItemI={i1,i2,..,im}是项的集合规则A＝B在数据集D中成立，具有支持度s和置信度c厦门大学软件学院9规则兴趣度的两个度量支持度(support):事务集中事务包含AB的百分比。——反映了规则的有用性Support(A＝B)=P(AB)最小支持度阈值min_sup支持度计数置信度(confidence)：事务集中包含A的事务同时也包含B的百分比——反映了规则的确定性Confidence(A＝B)=P(B|A)最小置信度阈值min_conf强规则：满足min_sup和min_conf的规则例如：Computer=financial_management_software[support=2%,confidence=60%]厦门大学软件学院10有关概念项集：项的集合。K-项集：包含k个项的项集项集的频率：包含项集的事务数频繁项集：支持度不小于min_sup的项集挖掘关联规则的过程找出所有频繁项集（中心问题）由频繁项集产生强关联规则厦门大学软件学院11MiningFrequentPatterns,AssociationandCorrelations基本概念和线路图有效的和可伸缩的频繁项集挖掘方法挖掘各种类型的关联规则关联规则到相关分析基于约束的关联规则小结厦门大学软件学院12ScalableMethodsforMiningFrequentPatternsThedownwardclosurepropertyoffrequentpatternsAnysubsetofafrequentitemsetmustbefrequentIf{beer,diaper,nuts}isfrequent,sois{beer,diaper}i.e.,everytransactionhaving{beer,diaper,nuts}alsocontains{beer,diaper}Scalableminingmethods:ThreemajorapproachesApriori(Agrawal&Srikant@VLDB’94)Freq.patterngrowth(FPgrowth—Han,Pei&Yin@SIGMOD’00)Verticaldataformatapproach(Charm—Zaki&Hsiao@SDM’02)厦门大学软件学院13Apriori:ACandidateGeneration-and-TestApproachAprioripruningprinciple:Ifthereisanyitemsetwhichisinfrequent,itssupersetshouldnotbegenerated/tested!(Agrawal&Srikant@VLDB’94,Mannila,etal.@KDD’94)Method:Initially,scanDBoncetogetfrequent1-itemsetGeneratelength(k+1)candidateitemsetsfromlengthkfrequentitemsetsTestthecandidatesagainstDBTerminatewhennofrequentorcandidatesetcanbegenerated厦门大学软件学院14TheAprioriAlgorithm—AnExampleDatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}2厦门大学软件学院15TheAprioriAlgorithm伪码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;厦门大学软件学院16ImportantDetailsofApriori如何产生候选?Step1:Lk的自连接Step2:剪枝（候选集的成员可能不是频繁的，剪枝原则？）候选生成的例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3abcdfromabcandabdacdefromacdandacePruning:acdeisremovedbecauseadeisnotinL3C4={abcd}厦门大学软件学院17HowtoGenerateCandidates?假设Lk-1中的项已按顺序排列Step1:Lk-1的自连接insertintoCkselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1q.itemk-1Step2:剪枝forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk厦门大学软件学院182.由频繁项集产生关联规则两个步骤对于每个频繁项集l，产生l的所有非空子集对于l的每个非空子集s,如果support_count(l)/support_count(s)≥min_conf则输出规则s=(l-s)厦门大学软件学院193ChallengesofFrequentPatternMining（自学）ChallengesMultiplescansoftransactiondatabaseHugenumberofcandidatesTediousworkloadofsupportcountingforcandidatesImprovingApriori:generalideasReducepassesoftransactiondatabasescansShrinknumberofcandidatesFacilitatesupportcountingofcandidates厦门大学软件学院20Partition:ScanDatabaseOnlyTwice（自学）AnyitemsetthatispotentiallyfrequentinDBmustbefrequentinatleastoneofthepartitionsofDBScan1:partitiondatabaseandfindlocalfrequentpatternsScan2:consolidateglobalfrequentpatternsA.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationinlargedatabases.InVLDB’95厦门大学软件学院21DHP:ReducetheNumberofCandidates（自学）Ak-itemsetwhosecorrespondinghashingbucketcountisbelowthethresholdcannotbefrequentCandidates:a,b,c,d,eHashentries:{ab,ad,ae}{bd,be,de}…Frequent1-itemset:a,b,d,eabisnotacandidate2-it