Association Rule MiningInstructorQiangYangSlides from Jiawei Han and Jian PeiAnd fromIntroduction to Data MiningByTan, Steinbach,Kumar
Association Rule Mining Instructor Qiang Yang Slides from Jiawei Han and Jian Pei And from Introduction to Data Mining By Tan, Steinbach, Kumar
What Is Frequent Pattern Mining?Frequent patterns: pattern (set of items,sequence, etc.) that occurs frequently in adatabase [AIS93]- Frequent pattern mining: findingregularities in dataWhat products were often purchased together?What are the subsequent purchases afterbuying a PC?Freguent-pattemminingmethods
Frequent-pattern mining methods What Is Frequent Pattern Mining? ◼ Frequent patterns: pattern (set of items, sequence, etc.) that occurs frequently in a database [AIS93] ◼ Frequent pattern mining: finding regularities in data ◼ What products were often purchased together? ◼ What are the subsequent purchases after buying a PC?
Why Is Frequent Pattern Miningan Essential Task in Data Mining? Foundation for many essential data mining tasksAssociation, correlation, causality Sequential patterns, temporal or cyclic association,partial periodicity, spatial and multimedia association Associative classification, cluster analysis, iceberg cubefascicles (semantic data compression)Broad applications Basket data analysis, cross-marketing, catalog designsale campaign analysis Web log (click stream) analysis, DNA sequence analysisetc.Frequent-pattemminingmethods
Frequent-pattern mining methods Why Is Frequent Pattern Mining an Essential Task in Data Mining? ◼ Foundation for many essential data mining tasks ◼ Association, correlation, causality ◼ Sequential patterns, temporal or cyclic association, partial periodicity, spatial and multimedia association ◼ Associative classification, cluster analysis, iceberg cube, fascicles (semantic data compression) ◼ Broad applications ◼ Basket data analysis, cross-marketing, catalog design, sale campaign analysis ◼ Web log (click stream) analysis, DNA sequence analysis, etc
Basic Concepts: Freguent Patternsand Association RulesItemset X={x1, ..., Xk]ItemsboughtTransaction-idFind all the rules XY with minA, B, Cconfidence and supportA, C support, s, probability that atransaction contains XuYA, D confidence, C, conditionalB, E, FCustonerCustomerprobability that a transactionDuySDOtnbuys diaperhaving X also contains Y.Let min support = 50%min conf = 50%:A →> C (50%, 66.7%)CustomerC →> A (50%, 100%)buys beerFreguent-pattemminingmethods
Frequent-pattern mining methods Basic Concepts: Frequent Patterns and Association Rules ◼ Itemset X={x1 , ., xk} ◼ Find all the rules X→Y with min confidence and support ◼ support, s, probability that a transaction contains XY ◼ confidence, c, conditional probability that a transaction having X also contains Y. Let min_support = 50%, min_conf = 50%: A → C (50%, 66.7%) C → A (50%, 100%) Customer buys diaper Customer buys both Customer buys beer Transaction-id Items bought A, B, C A, C A, D B, E, F
Concept: Freguent ItemsetsOutlook PlayHumidityTemperatureMinimum support=2hothighnosunny(sunny, hot, no)hothighsunnyno(sunny, hot, high, no)hothighovercastyes(rainy, normal)mildhighrainyyescoolnormalrainyyes Min Support =3coolnormalrainyno?coolnormalovercastyes How strong is {sunnymildhighnosunnynoy?coolnormalyessunnymildnormalrainyyesCount =mildnormalsunnyyesPercentage =mildhighyesovercasthotnormalyesovercastmildhighrainy1 Frequepattem mining methods
Frequent-pattern mining methods Concept: Frequent Itemsets Outlook Temperature Humidity Play sunny hot high no sunny hot high no overcast hot high yes rainy mild high yes rainy cool normal yes rainy cool normal no overcast cool normal yes sunny mild high no sunny cool normal yes rainy mild normal yes sunny mild normal yes overcast mild high yes overcast hot normal yes rainy mild high no ◼ Minimum support=2 ◼ {sunny, hot, no} ◼ {sunny, hot, high, no} ◼ {rainy, normal} ◼ Min Support =3 ◼ ? ◼ How strong is {sunny, no}? ◼ Count = ◼ Percentage =