国内国际新闻社会生活新闻采编中心.ppt

MiningAssociationRules,PartII,btbo精选网址,DataMiningOverview,DataMiningDatawarehousesandOLAP(OnLineAnalyticalProcessing.)AssociationRulesMiningClustering:HierarchicalandPartitionalapproachesClassification:DecisionTreesandBayesianclassifiersSequentialPatternsMiningAdvancedtopics:outlierdetection,webmining,ProblemStatement,I=i1,i2,im:asetofliterals,calleditemsTransactionT:asetofitemss.t.TIDatabaseD:asetoftransactionsAtransactioncontainsX,asetofitemsinI,ifXTAnassociationruleisanimplicationoftheformXY,whereX,YITheruleXYholdsinthetransactionsetDwithconfidencecifc%oftransactionsinDthatcontainXalsocontainYTheruleXYhassupportsinthetransactionsetDifs%oftransactionsinDcontainXYFindallrulesthathavesupportandconfidencegreaterthanuser-specifiedminsupportandminconfidence,ProblemDecomposition,1.Findallsetsofitemsthathaveminimumsupport(frequentitemsets)2.Usethefrequentitemsetstogeneratethedesiredrules,MiningFrequentItemsets:theKeyStep,Findthefrequentitemsets:thesetsofitemsthathaveminimumsupportAsubsetofafrequentitemsetmustalsobeafrequentitemseti.e.,ifABisafrequentitemset,bothAandBshouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok(k-itemset)Usethefrequentitemsetstogenerateassociationrules.,TheAprioriAlgorithm,Lk:Setoffrequentitemsetsofsizek(thosewithminsupport)Ck:Setofcandidateitemsetofsizek(potentiallyfrequentitemsets)L1=frequentitems;for(k=1;Lk!=;k+)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;,HowtoGenerateCandidates?,SupposetheitemsinLk-1arelistedinorderStep1:self-joiningLk-1insertintoCkselectp.item1,p.item2,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,p.itemk-2=q.itemk-2,p.itemk-1=10ComputeicebergqueriesefficientlybyApriori:Fir