FrequentMaxPatterns Succinct Expression of frequent patterns Let (a, b, c) be frequent Then, {a, b), {b, c), {a, c) must also be frequentThen (a), {b}, (c), must also be frequentBy writing down (a, b, c) once, we save lots ofcomputationMax Pattern If (a, b, c) is a frequent max pattern, then (a, b, c, x)is NoT a frequent pattern, for any other item x.Freguent-pattemminingmethods
Frequent-pattern mining methods Frequent Max Patterns ◼ Succinct Expression of frequent patterns ◼ Let {a, b, c} be frequent ◼ Then, {a, b}, {b, c}, {a, c} must also be frequent ◼ Then {a}, {b}, {c}, must also be frequent ◼ By writing down {a, b, c} once, we save lots of computation ◼ Max Pattern ◼ If {a, b, c} is a frequent max pattern, then {a, b, c, x} is NOT a frequent pattern, for any other item x
Find Freguent Max PatternsPlayOutlookHumidityTemperaturehothighMinimum support=2sunnynohothighsunnyno{(sunny, hot, no) ??hothighyesovercastmildhighrainyyescoolrainynormalyescoolrainynormalnocoolnormalyesovercastmildhighnosunnycoolnormalyessunnymildrainynormalyesmildnormalyessunnymildhighyesovercasthotnormalyesovercastmildhighrainynoFreguent-pattenminingmethods
Frequent-pattern mining methods Find Frequent Max Patterns 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} ??
ClosedPatternsAn itemset is closed if none of its immediatesupersets has the same support as theitemset. {a, b}, {a, b, d}, {a, b, c) are closedpatterns- But, a, b is not a max patternTIDItems See where changes happena, b, c Reduce # of patterns and rulesa, b, c N. Pasquier et al. In ICDT'99a, b, da, b, d,Freguent-pattemminingmethods
Frequent-pattern mining methods Closed Patterns An itemset is closed if none of its immediate supersets has the same support as the itemset • {a, b}, {a, b, d}, {a, b, c} are closed patterns ◼ But, {a, b} is not a max pattern ◼ See where changes happen ◼ Reduce # of patterns and rules ◼ N. Pasquier et al. In ICDT’99 TID Items a, b, c a, b, c a, b, d a, b, d, c, e, f