数据挖掘Chapter6

数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社第6章关联分析:基本概念和算法6.1问题定义2019年10月20日星期日数据挖掘导论4AssociationRuleMiningGivenasetoftransactions,findrulesthatwillpredicttheoccurrenceofanitemsetbasedontheoccurrencesofotheritemsinthetransactionMarket-BaskettransactionsTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExampleofAssociationRules{Diaper}{Beer},{Milk,Bread}{Eggs,Coke},{Beer,Bread}{Milk},Implicationmeansco-occurrence,notcausality!2019年10月20日星期日数据挖掘导论5Definition:FrequentItemsetItemsetAcollectionofoneormoreitemsExample:{Milk,Bread,Diaper}k-itemsetAnitemsetthatcontainskitemsSupportcount()FrequencyofoccurrenceofanitemsetE.g.({Milk,Bread,Diaper})=2SupportFractionoftransactionsthatcontainanitemsetE.g.s({Milk,Bread,Diaper})=2/5FrequentItemsetAnitemsetwhosesupportisgreaterthanorequaltoaminsupthresholdTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke2019年10月20日星期日数据挖掘导论6Definition:AssociationRuleAssociationRuleAnimplicationexpressionoftheformXY,whereXandYareitemsetsExample:{Milk,Diaper}{Beer}RuleEvaluationMetricsSupport(s)FractionoftransactionsthatcontainbothXandYConfidence(c)MeasureshowoftenitemsinYappearintransactionsthatcontainXTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExample:Beer}Diaper,Milk{4.052|T|)BeerDiaper,,Milk(s67.032)Diaper,Milk()BeerDiaper,Milk,(c2019年10月20日星期日数据挖掘导论7AssociationRuleMiningTaskGivenasetoftransactionsT,thegoalofassociationruleminingistofindallruleshavingsupport≥minsupthresholdconfidence≥minconfthresholdBrute-forceapproach:ListallpossibleassociationrulesComputethesupportandconfidenceforeachrulePrunerulesthatfailtheminsupandminconfthresholdsComputationallyprohibitive2019年10月20日星期日数据挖掘导论8MiningAssociationRulesObservations:Alltheaboverulesarebinarypartitionsofthesameitemset:{Milk,Diaper,Beer}RulesoriginatingfromthesameitemsethaveidenticalsupportbutcanhavedifferentconfidenceThus,wemaydecouplethesupportandconfidencerequirementsTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExampleofRules:{Milk,Diaper}{Beer}(s=0.4,c=0.67){Milk,Beer}{Diaper}(s=0.4,c=1.0){Diaper,Beer}{Milk}(s=0.4,c=0.67){Beer}{Milk,Diaper}(s=0.4,c=0.67){Diaper}{Milk,Beer}(s=0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)2019年10月20日星期日数据挖掘导论9MiningAssociationRulesTwo-stepapproach:1.FrequentItemsetGeneration–Generateallitemsetswhosesupportminsup2.RuleGeneration–Generatehighconfidencerulesfromeachfrequentitemset,whereeachruleisabinarypartitioningofafrequentitemsetFrequentitemsetgenerationisstillcomputationallyexpensive6.2频繁项集的产生2019年10月20日星期日数据挖掘导论11FrequentItemsetGenerationnullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEGivenditems,thereare2dpossiblecandidateitemsets2019年10月20日星期日数据挖掘导论12FrequentItemsetGenerationBrute-forceapproach:EachitemsetinthelatticeisacandidatefrequentitemsetCountthesupportofeachcandidatebyscanningthedatabaseMatcheachtransactionagainsteverycandidateComplexity~O(NMw)=ExpensivesinceM=2d!!!TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeNTransactionsListofCandidatesMw2019年10月20日星期日数据挖掘导论13FrequentItemsetGenerationStrategiesReducethenumberofcandidates(M)Completesearch:M=2dUsepruningtechniquestoreduceMReducethenumberofcomparisons(NM)UseefficientdatastructurestostorethecandidatesortransactionsNoneedtomatcheverycandidateagainsteverytransaction2019年10月20日星期日数据挖掘导论14ReducingNumberofCandidatesAprioriprinciple:Ifanitemsetisfrequent,thenallofitssubsetsmustalsobefrequentIfasubsetofanitemsetisinfrequent,thentheitemsetmustbeinfrequentAprioriprincipleholdsduetothefollowingpropertyofthesupportmeasure:SupportofanitemsetneverexceedsthesupportofitssubsetsThisisknownastheanti-monotonepropertyofsupport)()()(:,YsXsYXYX2019年10月20日星期日数据挖掘导论15IllustratingAprioriPrinciplenullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEPrunedsupersetsFoundtobeInfrequent2019年10月20日星期日数据挖掘导论16IllustratingAprioriPrincipleItemCountBread4Coke2Milk4Beer3Diaper4Eggs1ItemsetCount{Bread,Milk}3{Bread,Beer}2{Bread,Diaper}3{Milk,Beer}2{Milk,Diaper}3{Beer,Diaper}3Items(1-itemsets)Pairs(2-itemsets)Triplets(3-itemsets)MinimumSupport=3Ifeverysubsetisconsidered,Withsupport-basedpruning,6+6+1=1341362616CCCItemsetCount{Bread,Milk,Diaper}3(NoneedtogeneratecandidatesinvolvingCokeorEggs)TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke2019年10月20日星期日数据挖掘导论17AprioriAlgorithmMethod:(Algorithm6.1)Letk=1Generatefrequentitemsetsoflength1RepeatuntilnonewfrequentitemsetsareidentifiedGenerateCk+1:Generatelength(k+1)candidateitemsetsfromlengthkfrequentitemsets,Prune:prunecandidateitemsetscontainingsubsetsoflengthkthatareinfreque