Asszoci´aci´os szab´alyok keres´ese Csima Judit BME, VIK, Sz´ am´ıt´ astudom´ anyi ´ es Inform´ aci´ oelm´ eleti Tansz´ ek
2016. ´aprilis 29.
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
1 / 35
Alapfeladat
adottak v´as´arl´oi kosarak (tranzakci´ ok): miket v´as´aroltak egy¨ utt c´el: olyan szab´alyokat fel´all´ıtani, hogy ha valaki vesz X -et, akkor es´elyes, hogy vesz Y -t is X ´es Y lehet t¨obb elemb˝ ol ´all´ o halmaz is egy ilyen szab´aly nem jelent ok-okozati ¨ osszef¨ ugg´est! de egy ilyen szab´alyb´ol hasznot lehet h´ uzni: pl. ´arazzuk le X -et kicsit, emelj¨ uk meg Y ´ar´at jobban
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
2 / 35
Association Rule Mining Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction Market-Basket transactions TID
Items
1
Bread, Milk
2 3 4 5
Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke
© Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
Example of Association Rules
{Diaper} {Beer}, {Milk, Bread} {Eggs,Coke}, {Beer, Bread} {Milk},
Implication means co-occurrence, not causality!
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
2
3 / 35
Jel¨ol´esek, alapfogalmak
elem (item): amit lehet venni, pl. tej, pelenka tranzakci´o: amiket egy¨ utt vettek, egy v´as´arl´ oi kos´ar egyszer˝ u modell: darabsz´am nem sz´am´ıt, csak az, hogy szerepel-e egy adott term´ek a kos´arban c´el: X → Y szab´alyok tal´al´asa, ahol X , Y nem¨ ures, diszjunkt elemhalmazok (X ∩ Y = ∅) elnevez´es: ha |X | = k, akkor X -et k-elem˝ u elemhalmaznak (k-item set) h´ıvjuk
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
4 / 35
Mikor j´o egy szab´aly?
ha X ´es Y sok tranzakci´ oban szerepel egy¨ utt (k¨ ul¨onben nem ´erdekes, pl. Hello Kittys papucs ´es motorosf˝ ur´esz) ha az X -et tartalmaz´ o kosarak jelent˝ os r´esze tartalmaz Y -t is lesz m´eg valami m´as is, de el˝ osz¨ or n´ezz¨ uk ezeket
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
5 / 35
T´amogatotts´ag, support
X → Y abszol´ ut t´amogatotts´aga (support count): h´any kos´arban van X ´es Y is, jele σ(X ∪ Y ) X → Y t´amogatotts´aga (support): σ(X ∪ Y ) supp(X → Y ) = number of transactions csak olyan szab´alyokat akarunk, amikre a supp el´eg nagy (egy k¨ usz¨obn´el nagyobb, a k¨ usz¨ ob neve min sup) az´ert, mert ha kicsi a support, akkor arra nem lehet strat´egi´at ´ep´ıteni, az lehet, hogy v´eletlen egybees´es (Hello Kitty ´es f˝ ur´esz)
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
6 / 35
T´amogatotts´ag, support
supp(X → Y ) csak X ∪ Y -t´ ol f¨ ugg, att´ ol nem, hogy X ´es Y hogy oszlik el a szab´aly k´et oldal´ara ha supp(X → Y ) a k¨ usz¨ obn´el nagyobb, akkor X ∪ Y neve gyakori elemhalmaz (frequent item set) az persze k´erd´es, hogy mi a k¨ usz¨ ob ....
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
7 / 35
Definition: Frequent Itemset Itemset – A collection of one or more items
Example: {Milk, Bread, Diaper}
– k-itemset
An itemset that contains k items
Support count () – Frequency of occurrence of an itemset – E.g. ({Milk, Bread,Diaper}) = 2
Support
TID
Items
1
Bread, Milk
2 3 4 5
Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke
– Fraction of transactions that contain an itemset – E.g. s({Milk, Bread, Diaper}) = 2/5
Frequent Itemset – An itemset whose support is greater than or equal to a minsup threshold © Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
3
8 / 35
Megb´ızhat´os´ag, confidence
σ(X ∪ Y ) σ(X ) azaz: az X -et tartalmaz´ o kosarak mekkora r´esz´eben van Y is X → Y megb´ızhat´os´aga (confidence): conf (X → Y ) =
az a szab´aly ´erdekes, amin´el a conf egy k¨ usz¨ obn´el (jele min conf) nagyobb ez mutatja, hogy X elad´asai befoly´asolhatj´ak Y elad´asait
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
9 / 35
Definition: Association Rule Association Rule – An implication expression of the form X Y, where X and Y are itemsets – Example: {Milk, Diaper} {Beer}
Rule Evaluation Metrics – Support (s)
Measures how often items in Y appear in transactions that contain X
Csima Judit
Bread, Milk
2 3 4 5
Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke
{Milk, Diaper} Beer s c
© Tan,Steinbach, Kumar
Items
1
Example:
Fraction of transactions that contain both X and Y
– Confidence (c)
TID
Introduction to Data Mining
(Milk, Diaper, Beer) 2 0.4 |T| 5
(Milk, Diaper, Beer) 2 0.67 3 (Milk, Diaper ) 4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
4
10 / 35
Szab´alyok keres´ese
olyan szab´aly kell, ahol supp ≥ min sup ´es conf ≥ min conf supp mindig kisebb, mint conf egy adott szab´aly eset´en k´et k¨ ul¨on k¨ usz¨ob van, ez k´et k¨ ul¨ on felt´etel egy szab´aly el tud bukni mindk´et felt´etelen
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
11 / 35
Brute-force m´odszer
minden olyan X ´es Y elemhalmaz v´egign´ez´ese, amikre X ∩ Y = ∅ minden ilyenre supp ´es conf sz´amol´asa, rosszak kidob´asa d−1 X d ez sajnos t´ ul sok: nagyj´ab´ ol 2d−k , durv´an exponenci´alis (ahol k k=1 d darab lehets´eges item van)
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
12 / 35
Computational Complexity Given d unique items:
– Total number of itemsets = 2 d – Total number of possible association rules:
d d k R k j 3 2 1 d 1
d k
k 1
j 1
d
d 1
If d=6, R = 602 rules
© Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
10
13 / 35
´ Eszrev´ etel
egy X → Y szab´aly akkor j´ o, ha el´eg nagy a supp ´es a conf is supp csak X ∪ Y -t´ol f¨ ugg, el˝ osz¨ or ezt a l´ecet kell megugrania a potenci´alis szab´alynak ha supp(Z = X ∪ Y ) el´eg nagy, akkor j¨ on az, hogy hogyan legyen Z sz´etosztva a szab´aly k´et oldal´ara, hogy a conf is el´eg nagy legyen v´alasszuk sz´et a k´et ellen˝ orz´est: el˝ osz¨ or keress¨ unk gyakori elemhalmazokat (Z ), csak ilyenekb˝ol lehet j´o szab´aly n´ezz¨ uk meg, hogy egy gyakori elemhalmazb´ ol milyen nagy megb´ızhat´ os´ag´ u szab´aly gy´arthat´ o le
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
14 / 35
´ anos algo Altal´
el˝osz¨or legener´alom az ¨ osszes gyakori elemhalmazt (adott a min sup) ezut´an minden egyes gyakori elemhalmazb´ ol megcsin´alom a nagy megb´ızhat´os´ag´ u szab´alyokat
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
15 / 35
Brute-force m´odszer gyakori elemhalmazok keres´es´ere
minden nem-¨ ures r´eszhalmazt v´egign´ezek ez nem j´o, t´ ul sok van: 2d − 1 ´eszrev´etel: a r´eszhalmazok h´al´ o-strukt´ ur´at alkotnak s˝ot: ha M jel¨olt van a gyakori halmazra ´es N tranzakci´o, akkor minden jel¨oltet ¨ossze kell vetni minden tranzakci´ oval (benne van-e a jel¨olt az adott kos´arban) ez O(NMw ), ahol w a tranzakci´ ok nagys´aga (h´any elem van benne) d ´es m´ar csak M maga 2 − 1 a brute-force esetben
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
16 / 35
Frequent Itemset Generation null
A
B
C
D
E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
ACDE
ABCDE
© Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
BCDE
Given d items, there are 2d possible candidate itemsets 4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
8
17 / 35
Frequent Itemset Generation Brute-force approach: – Each itemset in the lattice is a candidate frequent itemset – Count the support of each candidate by scanning the database Transactions
N
TID 1 2 3 4 5
Items Bread, Milk Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke
List of Candidates
M
w
– Match each transaction against every candidate – Complexity ~ O(NMw) => Expensive since M = 2d !!! © Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
9
18 / 35
Hogyan lehetne gyors´ıtani?
cs¨okkents¨ uk M-et: ne az ¨ osszes r´eszhalmazt n´ezz¨ uk ´esz n´elk¨ ul, hanem sz˝ urj¨ unk valahogy miel˝ ott elkezdjk ˝ oket ¨ osszevetni a tranzakci´okkal cs¨okkents¨ uk N-t (a tranzakci´ ok sz´am´at) vagy a hosszukat (w -t) haszn´aljunk valami u ¨gyes adatszerkezetet a jel¨ oltek ´es a tranzakci´ok ¨osszevet´es´ere most el˝osz¨or az els˝o lehet˝ os´eget n´ezz¨ uk: M cs¨ okkent´ese
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
19 / 35
Jel¨oltek sz´am´anak cs¨okkent´ese
c´el: gyakori elemhalmazok keres´ese hogyan: a r´eszhalmazokb´ ol ´all´ o h´al´ ot u ´gy bej´arni, hogy min´el t¨obb elemhalmazt ki tudjunk z´arni, min´el el˝ obb k¨ovetelm´enyek: minden gyakorit gener´aljunk v´eg¨ ul egyet csak egyszer ne dolgozzunk t´ ul sokat a gener´al´as sor´an
egyszer˝ us´ıt´es: item-ek neve helyett sz´amokat haszn´alunk
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
20 / 35
Apriori-elv
Apriori-elv: ha X gyakori, akkor minden r´eszhalmaza gyakori mert ha Y ⊆ X , akkor supp(Y ) = tranzakci´ok sz´ama)
σ(Y ) N
≥
σ(X ) N
= supp(X ) (itt N a
ugyanez m´ashogy: ha Y nem gyakori, akkor senki se gyakori, aki Y -t tartalmazza ezt u ´gy is szokt´ak mondani, hogy a support f¨ uggv´eny anti-monoton
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
21 / 35
Apriori algo
haladjunk k szerint n¨ ov˝ oen k = 1-t˝ ol ha egy k elem˝ u elemhalmaz nem gyakori, akkor minden n´ala b˝ovebb elemhalmaz kiz´arhat´o (infrequent) egy k elem˝ u halmaz csak akkor lehet gyakori, ha minden k − 1 elem˝ u r´eszhalmaza gyakori
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
22 / 35
Illustrating Apriori Principle null
A
Found to be Infrequent
B
E
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCE
Pruned supersets
Csima Judit
D
AB
ABCD
© Tan,Steinbach, Kumar
C
Introduction to Data Mining
ABDE
ACDE
BCDE
ABCDE
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
13
23 / 35
Apriori algo 1
2
egyszer v´egign´ezek minden tranzakci´ ot ´es kigy˝ ujt¨ om az egy-elem˝ u gyakoriakat (ehhez minden x elemre kisz´amolom σ(x)-et), ez az F1 halmaz k=2 C2 = 2-elem˝ u es´elyesek: akiknek mindk´et tagja F1 -ben van F2 = C2 -beli jel¨ oltek ¨ osszevet´ese a tranzakci´ okkal, a gyakoriak F2
3
k=3 C3 = 3-elem˝ u es´elyesek: akiknek minden k´etelem˝ u r´eszhalmaza F2 -ben van F3 = C3 -beli jel¨ oltek ¨ osszevet´ese a tranzakci´ okkal, a gyakoriak F3
4
k ´altal´aban Ck = k-elem˝ u es´elyesek: akiknek minden k − 1-elem˝ u r´eszhalmaza Fk−1 -ben van Fk = Ck -beli jel¨ oltek ¨ osszevet´ese a tranzakci´ okkal, a gyakoriak Fk Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
24 / 35
Illustrating Apriori Principle Item Bread Coke Milk Beer Diaper Eggs
Count 4 2 4 3 4 1
Items (1-itemsets)
Minimum Support = 3
Itemset {Bread,Milk} {Bread,Beer} {Bread,Diaper} {Milk,Beer} {Milk,Diaper} {Beer,Diaper}
Csima Judit
Pairs (2-itemsets) (No need to generate candidates involving Coke or Eggs)
Triplets (3-itemsets)
If every subset is considered, 6C + 6C + 6C = 41 1 2 3 With support-based pruning, 6 + 6 + 1 = 13
© Tan,Steinbach, Kumar
Count 3 2 3 2 3 3
Introduction to Data Mining
Itemset {Bread,Milk,Diaper}
Count 3
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
14
25 / 35
´ Eszrev´ etelek
u ´gy k¨onny˝ u Fk−1 -b˝ol Ck k´epz´ese, ha az elemhalmazokban n¨ovekv˝o sorrendben vannak mert ekkor k¨onny˝ u Ck -ba tartoz´ o k-elem˝ u jel¨ olteket el˝o´all´ıtani u ´gy, hogy k´et olyan (rendezett) (k − 1)-elem˝ ut keresek Fk−1 -ben, amiknek az els˝o k − 2 tagja ugyanaz ´ıgy biztos, hogy minden k elem˝ u gyakori beker¨ ul Ck -ba, pontosan egyszer nem kell azzal foglalkozni, hogy Ck -b´ ol kisz˝ urj¨ uk a duplik´atumokat
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
26 / 35
Hogyan lesz teh´at Fk Fk−1 -b˝ol?
Fk−1 -ben minden elemhalmazban rendezetten vannak az elemek k´et Fk−1 -beli k − 1 elem˝ u elemhalmazb´ ol akkor csin´alok egy k elem˝ u jel¨oltet Ck -ba, ha az els˝ o k − 2 tagjuk ugyanaz az ´ıgy l´etrej¨ ott k elem˝ u elemhalmaz t¨ obbi k − 1 elem˝ u r´eszhalmaza is Fk−1 -ben van (ez m´eg k − 2 ellen˝ orz´es)
az ´ıgy kapott Ck minden elemhalmaz´at ¨ osszevetj¨ uk minden tranzakci´oval (t´enylegesen lesz´amoljuk a σ-kat)
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
27 / 35
Tov´abbi gyors´ıt´as
l´attuk, hogy a nagy mel´ o a jel¨ oltek ´es a tranzakci´ok ¨osszevet´ese (az egeyes jel¨oltek el˝ofordul´asainak kisz´amol´as´ahoz) eddig: miel˝ott ¨osszevetj¨ uk a jel¨ olteket a tranzakci´okkal, cs¨okkents¨ uk a jel¨oltek sz´am´at (minden k elem˝ u r´eszhalmaz helyett csak Ck -beliek) tov´abbi lehet˝os´egek: cs¨ okkents¨ uk a tranzakci´ ok hossz´at: a nem gyakori egy elem˝ ueket dobjuk ki az elej´en minden tranzakci´ ob´ ol cs¨ okkents¨ uk a tranzakci´ ok sz´am´at: Fk el˝ o´all´ıt´asa k¨ozben, akkor dobjunk ki minden k-n´al nem hosszabb tranzakci´ot
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
28 / 35
Szab´alyok gener´al´asa gyakori elemhalmazokb´ol
tegy¨ uk fel, hogy megvannak a gyakori elemhalmazok minden Z gyakori elemhalmazb´ ol le szeretn´enk gener´alni az ¨osszes olyan X → Y szab´alyt, ahol Z = X ∪ Y , X ´es Y sem u ¨res supp(X → Y ) ≥ min sup conf (X → Y ) ≥ min conf
a min sup-os dolog Z gyakoris´aga miatt megvan a conf -os felt´etelt k´ene teljes´ıteni
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
29 / 35
Brute-force algo
adott Z eset´en minden lehets´eges m´ odon X , Z \ X kiv´alaszt´asa minden v´alaszt´asra conf (X → Z \ X ) sz´amol´asa ehhez σ(X ) kell de 2|Z | -2 lehet˝os´eg van X -re, ez t´ ul sok
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
30 / 35
´ Eszrev´ etel
Ha adott egy Z ´es ennek egy X r´eszhalmaz´ab´ ol, mint baloldalb´ol sz´armaztatott szab´aly nem j´ o (conf-ja kisebb, mint min conf ), akkor az osszes olyan X 0 baloldalb´ol se lesz j´ ¨ o szab´aly, ahol X 0 ⊆ X . Biz. σ(Z ) σ(Z ) conf (X 0 → Z \ X 0 ) = σ(X 0 ) ≤ σ(X ) < min conf A k¨ oz´epen ´all´o egyenl˝otlens´eg az´ert igaz, mert X 0 ⊆ X miatt σ(X 0 ) ≥ σ(X ).
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
31 / 35
´ Eszrev´ etel m´ask´ent
ha egy adott Z -b˝ol gener´alok szab´alyokat ´es egy Y jobboldal´ u szab´aly rossz, akkor minden olyan szab´aly is rossz, ahol a jobboldal Y -n´al b˝ovebb ez hasonl´o az Apriori-elvhez csin´aljuk ugyanazt, amit az Apriori-algoban: adott Z eset´en el˝ osz¨ or legener´aljuk az 1-elem˝ u jobboldal´ u j´o szab´alyokat n¨ ovelj¨ uk a szab´alyok jobboldal´anak hossz´at, csak olyan jobboldalak j¨ onnek be, amiknek minden eggyel kisebb r´eszhalmaz´ahoz tartoz´o szab´aly j´ o volt
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
32 / 35
Rule Generation for Apriori Algorithm Lattice of rules Low Confidence Rule
CD=>AB
ABCD=>{ }
BCD=>A
ACD=>B
BD=>AC
D=>ABC
BC=>AD
C=>ABD
ABD=>C
AD=>BC
B=>ACD
ABC=>D
AC=>BD
AB=>CD
A=>BCD
Pruned Rules © Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
47
33 / 35
Rule Generation for Apriori Algorithm
Candidate rule is generated by merging two rules that share the same prefix in the rule consequent CD=>AB
join(CD=>AB,BD=>AC) would produce the candidate rule D => ABC
Prune rule D=>ABC if its subset AD=>BC does not have high confidence
© Tan,Steinbach, Kumar
Csima Judit
Introduction to Data Mining
BD=>AC
D=>ABC
4/18/2004
Asszoci´ aci´ os szab´ alyok keres´ ese
48
34 / 35
Apriori-elven m˝uk¨od˝o szab´alygener´al´as Z -b˝ol
egyelem˝ u jobboldal´ u szab´alyokra conf sz´amol´asa, csak a j´ok maradnak minden szab´aly jobboldal´an rendezve tartjuk az elemeket k − 1 hossz´ u jobboldalr´ ol k hossz´ u jobboldalra: ha van k´et olyan k − 1 hossz´ u jobboldal, akiknek az els˝o k − 2 tagja megegyezik, akkor ezekb˝ ol uni´ oval k hossz´ u jobboldalt k´epez¨ unk (ezt minden lehets´eges m´ odon megtessz¨ uk) leellen˝ orizz¨ uk, hogy a k´et, gener´al´ o k − 1 hossz´ u r´eszhalmazon k´ıv¨ uli t¨ obbi k − 2 darab k − 1 elem˝ u r´eszhalmazhoz is j´o szab´aly tartozott aki ezen a sz˝ ur˝ on is ´atmegy, arra conf -ot sz´amolok, aki ezt is t´ ul´eli az lesz j´ o, k hossz´ u jobboldal´ u szab´aly
Csima Judit
Asszoci´ aci´ os szab´ alyok keres´ ese
35 / 35
