Association Rule Mining(ARM) notes for class

ARM slideshow notes

1. Association Rule Mining

2. Association Rule Mining (ARM)
•Theclassicalproblemofassociationpatternminingisdefinedinthecontextof
supermarketdatacontainingsetsofitemsboughtbycustomers,whichare
referredtoastransactions.
•Thegoalistodetermineassociationsbetweengroupsofitemsboughtby
customers.
•Themostpopularmodelforassociationpatternminingusesthefrequenciesof
sets.
•Thediscoveredsetsofitemsarereferredtoaslargeitemsets,frequentitemsets,or
frequentpatterns.
•ApplicationofARM -Supermarketdata,Textmining,Generalizationto
dependency-orienteddatatypes,MarketBasketAnalysis.

3. Association Rule Mining (ARM)
•FrequentitemsetscanbeusedtogenerateassociationrulesoftheformX⇒Y,
whereXandYaresetsofitems.
•This rule suggests that buying of X makes it more likely that Y will also be
bought.
•Givenasetoftransactions,findrulesthatwillpredicttheoccurrenceofanitem
basedontheoccurrencesofotheritemsinthetransaction.
•ExampleofAssociationRules
{Diaper}→{Beer},
{Milk,Bread}→{Eggs,Coke},
{Beer,Bread}→{Milk},

4. Association Rule Mining (ARM)
•Itemset
•Acollectionofoneormoreitems,eg;{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
•Anitemsetwhosesupportisgreaterthanorequaltoaminsupthreshold

5. Association Rule Mining (ARM)
•RuleEvaluationMetrics
•Support(s)
•FractionoftransactionsthatcontainbothXandY
•ThesupportofanitemsetIisdefinedasthefractionofthe
transactionsinthedatabaseT={T1...Tn}thatcontainIasasubset.
•Confidence(c)
•MeasureshowoftenitemsinYappearintransactionsthatcontainX.
•Theconfidenceconf(X∪Y)oftheruleX∪Yistheconditional
probabilityofX∪Yoccurringinatransaction,giventhatthe
transactioncontainsX.Therefore,theconfidenceconf(X⇒Y)is
definedasfollows–
•AssociationRuleMiningTask
•GivenasetoftransactionsT,thegoalofassociationrule
miningistofindallruleshaving
•support≥minsupthreshold
•confidence≥minconfthreshold

6. Association Rule Mining Task
•Brute-forceapproach:
•Listallpossibleassociationrules
•Computethesupportandconfidenceforeachrule
•Prunerulesthatfailtheminsupandminconfthresholds.
•ComputationallyExpensive
•StrategiestoreduceComputationalComplexity:
•Reducethenumberofcandidates(M)
•Reducethenumberoftransactions(N)
•Reducethenumberofcomparisons(NM)

7. Association Rule Mining Task
•AprioriPrinciple:Ifanitemsetisfrequent,thenallofitssubsetsmustalsobe
frequent.
•Aprioriprincipleholdsduetothefollowingpropertyofthesupportmeasure:
•Supportofanitemsetneverexceedsthesupportofitssubsets.
•Thisisknownastheanti-monotonepropertyofsupport.
•Apriorialsousesthedownwardclosureproperty.
•Apriorialgorithm generates candidates with smaller length k first and counts their
supports before generating candidates of length (k+1).
•The resulting frequent k-itemsetsare used to restrict the number of (k + 1)-
candidates with the downward closure property.

8. Association Rule Mining Task