Asociační pravidla
Asociační pravidla • hledání zajímavých asociací i korelací ve velkém množství dat • původně pro transakční data • obchodní transakce
• analýza nákupního košíku • podpora rozhodování
Analýza nákupního košíku MBA: Market Basket Analysis Analýza prodeje: Které položky jsou v košíku „pohromadě“? Výsledky: • vyjádřené formou pravidel • lze bezprostředně použít
Použití: • Plánování a rozvržení obchodu • nabídka kupónu,omezení slev • „balení”produktu
Asociační pravidla Jak spolu jednotlivé produkty navzájem souvisejí? • asociační pravidla by měla být • snadno pochopitelná – je-li nějaký vztah nalezen, lze ho snadno ověřit • použitelná – obsahují užitečné informace, které mohou vést k dalším intervencím
• asociační pravidla by neměla být: • triviální – výsledky už stejně každý zná • nevysvětlitelná – neexistuje k nim žádné vysvětlení a nevedou k žádné akci
MBA – jak se to dělá? • Položka – produkt nebo nabídka služeb • Transakce – obsahuje jednu nebo více položek • Tabulka četností • udává počet výskytu libovolných dvou položek v některé z provedených transakcí (tj. kolikrát byly tyto dva produkty zakoupeny najednou) • hodnoty na diagonále odpovídají počtu transakcí obsahujících příslušnou položku
Příklad MBA Nákupní transakce
Tabulka četností pečivo minerálsýr
máslo káva mléko suš.
Id
Položky
1
pečivo, káva, minerálka
pečivo
8
2
3
4
3
2
0
2
pečivo, sýr, minerálka
minerál
2
4
1
0
3
0
1
3
pečivo, sýr, máslo, káva
sýr
3
1
3
2
1
0
0
4
pečivo, máslo, sýr
5
pečivo, máslo, káva
máslo
4
0
2
4
2
1
0
6
pečivo, máslo, mléko
káva
3
3
1
2
6
0
2
7
pečivo, káva, sušenky
mléko
2
0
0
1
0
2
0
8
káva, minerálka
sušen.
0
1
0
0
2
0
2
9
pečivo, mléko
10
káva, minerálka, sušenky
pečivo se kupuje často s máslem, sýrem a kávou
káva se kupuje často s minerálkou a pečivem
MBA asociační pravidla Pravidlo IF Podmínka THEN Výsledek. Pravidlo_r IF Položka_i THEN Položka_j .
Otázky •
Jak dobrá jsou nalezená asociační pravidla? • podpora • spolehlivost • zlepšení
•
Jak hledat asociační pravidla automaticky?
Podpora a spolehlivost Podpora – jak často lze pravidlo použít
Podpora ( Pravidlo_r )
Pocet transakcí
obsahující ch i a j
Pocet všech transakcí
* 100 %
Spolehlivost – jak moc se můžeme na výsledky pravidla spolehnout?
Spolehlivo st ( Pravidlo_r )
Pocet transakcí Pocet transakcí
obsahující ch i a j obsahující ch i
* 100 %
Zlepšení pravidla Zlepšení – nakolik je lepší pravidlo při predikci použít než výsledek prostě předpokládat Zlepšení ( Pravidlo_r )
p (i _ a _ j ) p (i ) * p ( j )
je-li Zlepšení < 1 • pravidlo při predikci je horší než náhodná volba • negace výsledku může vést k lepšímu pravidlu IF podmínka THEN NOT výsledek
Hlavní kroky MBA • zvolit odpovídající položky na adekvátní úrovni • vytvořit pravidla na základe údajů z tabulky četností • spočítat (podmíněné) pravděpodobnosti výskytu položek a jejich kombinací v transakcích • omezit prohledávání prahovou hodnotou pro podporu • určit nejlepší pravidla analýzou vypočtených pravděpodobností • překonat omezení daná počtem položek a jejich kombinací v “zajímavých”transakcích
MBA analýza • jasné a srozumitelné výsledky IF-THEN – pravidla s bezprostředním použitím • dobývání znalostí (bez požad. výstupu) důležité při zpracovávání velkého množství dat bez dalších apriorních znalostí • zpracování dat s variabilní délkou
• snadné a srozumitelné výpočty Výpočetní nároky rostou exponenciálně s počtem položek!
Analýza log záznamu server www.einnews.com prezentace studentů MFF (Ševčíková, Zoulek)
Asociační pravidla • podobná klasifikačním pravidlům
• v důsledku pravidla muže být predikce jakéhokoliv atributu (i kombinace predikcí pro více atributu) Příklady: if teplota = chladno then vlhkost = normální if pohlaví = žena then tv_žánr = romantika if pohlaví = muž then tv_žánr = sport
klasifikační pravidla
if mouka then máslo and vajíčka if kolo then helma if brusle then helma and chrániče
implikace znamená společný výskyt, nikoliv příčinu a důsledek!!!
Využití asociačních pravidel • analýza nákupního košíku • podpora marketingu, inzerování produktu • umístění zboží regálech
• detekce chyb v telekomunikačních sítích • analýza bankovních služeb – kombinace nabízených produktů • analýza služeb mobilních operátorů
Asociační pravidla • Velké množství asociačních pravidel X => Y • Bereme v úvahu ty, které • pokrývají dostatečné množství instancí – podpora (support) • jsou dostatečně přesné - spolehlivost (confidence) Podpora - podíl těch instancí, které vyhovují pravidlu X Y oproti všem instancím (n) Spolehlivost - podíl těch instancí, které vyhovují pravidlu X Y oproti těm, na které se dá pravidlo aplikovat (X)
Příklad – volitelné předměty Studentský výběr předmětů
Možné skupiny položek
id
Kombinace
Skupiny
S1
ANK, ESV, LIS
ANK
90 %
S2
ANK, SPJ, DEG
IVT
30 %
S3
ANK, ESV, DEG
…
…
S4
ANK, LIS
ANK, DEG
20 %
S5
ANK, IVT
ANK, ESV
20 %
S6
ANK, IVT, MAS
ANK, MPC
10 %
S7
ANK, MAS,MPC
ANK, PRA
10 %
S8
ANK, MAS, PRA
ANK, SPJ
20 %
S9
PRA, LIS, NEK
ANK, LIS
20 %
S10
ANK, IVT,MPC
ANK, MAS
30 %
ANK, IVT, MPC
10 %
ANK, MAS, MPC
10 %
…
Podpora
…
Triviální algoritmus Je dána množina transakcí, máme najít všechna relevantní pravidla tj. taková, že podpora ≥ prahová hodnota sp spolehlivost ≥ prahová hodnota cp Hrubá síla: 1.
Nakombinujeme všechny dvojice, trojice, … položek a zjistíme seznam všech možných pravidel
2.
Určíme podporu a spolehlivost pro každé pravidlo
3.
Vyloučíme irelevantní pravidla
Triviální algoritmus Transakční tabulka s booleovskými daty A
B
C
D
E
t1
1
1
0
0
1
t2
0
1
0
1
0
t3
0
1
1
0
0
t4
1
1
0
1
0
t5
1
0
1
0
0
t6
0
1
1
0
0
t7
1
0
1
0
0
t8
1
1
1
0
1
t9
1
1
1
0
0
9 transakcí, 5 druhů zboží [1] B C => A (s=0.22 ; c= 0.5) [2] A B => E (s=0.22 ; c= 0.5) [3] B => E (s = 0.55 ; c = 0.71) [4] C => D (s = 0.67 ; c = 1) … Pro prahové hodnoty: sp = 0.2 ; cp = 0.75 jsou zjištěná pravidla 1-3 irelevantní, 4 je relevantní
Možné kombinace pro 5 položek null
5
A
B
C
D
E
1
5
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
2
5 3
5
ABCD
ABCE
ABDE
4 5 5
ABCDE
ACDE
BCDE
Příklad s 5 položkami • celkem 25 = 32 kombinací • celkem 180 pravidel
Počet pravidel 60000
d 1
R k 1
3
d
2
d
d k d 1
k
j 1
d
k j
50000 40000 30000
1
Výpočetně složité!!!
20000 10000 0 0
2
4
6
8
10
Dolování asociační pravidel TID
Položky
1
Chleba, Mléko
2
Chleba, Plenky, Pivo, Vejce
3
Mléko, Plenky, Pivo, Cola
4
Chleba, Mléko, Plenky, Pivo
5
Chleba, Mléko, Plenky, Cola
Příklady pravidel {Mléko, Plenky} {Pivo} (s=0.4, c=0.67) {Mléko, Pivo} {Mléko} (s=0.4, c=1.0) {Plenky, Pivo} {Mléko} (s=0.4, c=0.67) {Pivo} {Mléko, Plenky} (s=0.4, c=0.67) {Plenky} {Mléko, Pivo} (s=0.4, c=0.5) {Mléko} {Plenky, Pivo} (s=0.4, c=0.5)
Pozorování • položky všech uvedených pravidel jsou prvky téže množiny FIS: {Mléko, Plenky, Pivo} • pravidla vycházející ze stejné množiny mají stejnou podporu, ale různou spolehlivost • lze tedy oddělit požadavky na podporu a spolehlivost
21
Dolování asociačních pravidel • vytvoření klasifikačního pravidla pro každý možný důsledek pravidla – není efektivní • dvoufázový postup: 1. hledání frekventovaných množin položek (frequent itemsets) 2. generování pravidel z frekventovaných množin položek
Frekventované množiny položek • Frekventované množiny položek (frequent (large) itemsets) – množiny položek, které mají větší podporu než prahová hodnota sp
• Dolování asociačních pravidel (upřesnění): 1. hledání frekventovaných množin položek 2. generování pravidel z frekventovaných množin položek
Frekventované množiny položek • pro každé asociační pravidlo X => Y, musí platit, že X Y je frekventovaná množina položek • platí: podmnožina každé frekventované množiny je frekventovaná množina • nalézání frekventovaných množin položek • jednoduché, • časově náročné !!!
• pro m položek: 2m-1 kandidátu
Příklad: pro m = 30 počet kandidátu je 1073741823
Faktory ovlivňující složitost • Stanovení prahové podpory
• nižší hodnota vede k většímu počtu FIS • vyšší počet kandidátů a větší množiny frek. položek
• Dimenze (počet položek) množiny dat
• nutnost většího prostoru pro ukládání výsledků • delší výpočet a IO operace
• Velikost databáze
• Průměrná šířka (velikost) transakce
• transakční šířka se zvyšuje s vyšší hustotou datových množin • to může zvýšit max. délku FIS a průchod hash stromem
Strategie generování FIS • Redukce počtu kandidátů (M) • úplné vyhledávání: M=2d • redukce M s použitím prořezávacích technik • Redukce počtu transakcí (N) • redukce velikosti N, pokud narůstá velikost množin položek • použití DHP a vertikálně-založených dolovacích algoritmů • Redukce počtu porovnání (NM) • použití efektivních dat. struktur pro uložení kandidátů či transakcí • není nutné porovnávat každého kandidáta vůči každé transakci
Redukce počtu kandidátů • Apriori princip • je-li množina položek frekventovaná množina položek (FIS), pak i její podmnožiny jsou FIS
• Apriori princip platí díky následující vlastnosti podpory
X ,Y : ( X
Y)
s( X )
s (Y )
• podpora množiny položek nikdy nepřekročí podporu jejích podmnožin • tzv. antimonotónní vlastnost podpory
Příklad Apriori principu Jednoprvkové množiny Položka Chleba Cola Mléko Pivo Plenky Vejce
Počet 4 2 4 3 4 1
Dvojice Množina položek Chleba, Mléko Chleba, Pivo Chleba, Plenky Mléko, Pivo Mléko, Plenky Pivo, Plenky
Minimální podpora FIS je 3 Uvažujeme-li všechny kombinace, C1 (6) + C2(6) + C3(6) = 41 Vynecháním 2 položek (redukce), 6 + 4 + 1 = 11
Počet 3 2 3 3 2 3
Trojice Množina položek Chleba, Mléko, Pivo
Počet 2
Apriori algoritmus • nechť k=1 • generuj množiny frekventovaných položek délky 1 • opakuj, dokud už nelze určit žádnou FIS • z množin frekventovaných položek obsahující k položek generuj množiny o velikosti (k+1) položek (kandidátní množiny na FIS) • prořež kandidátní množiny položek obsahující podmnožiny velikosti k, které nejsou frekventované • spočti podporu pro každou kandidátní množinu • eliminuj kandidáty, které nepatří k často se vyskytujícím
Problémy získávání FIS • Problémy • Opakované procházení (prohledávání) transakční databáze • Obrovský počet kandidátů
• Otravný výpočet podpory pro kandidáty
• Vylepšení Apriori: základní myšlenky • Redukovat počet průchodů databází • Zmenšit počet kandidátů • Ulehčit výpočet podpory pro kandidáty
Kompaktní reprezentace FIS některé množiny položek jsou redundantní, neboť mají stejnou podporu jako jejich nadmnožiny TID A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
• Počet FIS
10
3 k 1
10 k
• Potřeba kompaktní reprezentace
Maximalní FIS Množina položek je maximální množina frekventovaných položek, pokud žádná její přímá nadmnožina není FIS null Maximální množina FIS
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
Množiny nefrekv. položek
ABCE
ABDE
ACDE
BCDE
Hranice ABCD E
Uzavřená množina položek Množina položek je uzavřená, pokud žádná její přímá nadmnožina nemá stejnou podporu TID 1 2 3 4 5
Položky {A,B} {B,C,D} {A,B,C,D} {A,B,D} {A,B,C,D}
MnožinyP Podpora {A} 4 {B} 5 {C} 3 {D} 4 {A,B} 4 {A,C} 2 {A,D} 3 {B,C} 3 {B,D} 4 {C,D} 3
MnožinyP Podpora {A,B,C} 2 {A,B,D} 3 {A,C,D} 2 {B,C,D} 3 {A,B,C,D} 2
Maximální versus uzavřené množiny položek Transakční Ids null
TID
Položky
1
ABC
2
ABCD
3
BCE
4
ACDE
5
DE
124
123
A
12
124
AB
12
24
AC
ABC
B
AE
24 ABD
ABE
2
345 D
2
3
BC
BD
4 ACD
245
C
123
4
AD
2
1234
BE
2
4 ACE
ADE
E
24
CD
ABCE
ABDE
Ne podporováno žádnou transakcí ABCDE
CE
3 BCD
ACDE
45
DE
4 BCE
4 ABCD
34
BCDE
BDE
CDE
Maximální versus uzavřené FIS Minimální podpora = 2 124
123
A
12
124
AB
12 ABC
24
AC
AD
ABD
ABE
1234
B
AE
345 D
2
3
BC
BD
4 ACD
245
C
123
4
24
2
Uzavřené, ale ne maximální
null
24 BE
2
4 ACE
E
ADE
CD
Uzavřené a zároveň maximální 34
CE
3 BCD
45
DE
4 BCE
BDE
CDE
4
2 ABCD
ABCE
ABDE
ACDE
BCDE
# Uzavřené = 9 # Maximální = 4
ABCDE
Maximální versus uzavřené FIS
Frequent Itemsets Closed Frequent Itemsets Maximal Frequent Itemsets
Alternativní metoda pro generování FIS • Reprezentace databáze • horizontální versus vertikální data layout Horizontal Data Layout TID 1 2 3 4 5 6 7 8 9 10
Items A,B,E B,C,D C,E A,C,D A,B,C,D A,E A,B A,B,C A,C,D B
Vertical Data Layout A 1 4 5 6 7 8 9
B 1 2 5 7 8 10
C 2 3 4 8 9
D 2 4 5 9
E 1 3 6
ECLAT Uložení seznamu transakcí pro každou položku Horizontal Data Layout TID 1 2 3 4 5 6 7 8 9 10
Items A,B,E B,C,D C,E A,C,D A,B,C,D A,E A,B A,B,C A,C,D B
Vertical Data Layout A 1 4 5 6 7 8 9
B 1 2 5 7 8 10
C 2 3 4 8 9
D 2 4 5 9
E 1 3 6
ECLAT Určit podporu pro každou k-množinu položek průnikem seznamů TID dvou (k-1) podmnožin
A 1 4 5 6 7 8 9
B 1 2 5 7 8 10
AB 1 5 7 8
FP-growth algoritmus • využití zhuštěné reprezentace databáze využitím FP-stromů • zkonstruuje se FP-strom a rekurzivně metodou rozděl-panuj se dolují FIS
FP-strom konstrukce null
Po přečtení TID=1:
TID 1 2 3 4 5 6 7 8 9 10
Items {A,B} {B,C,D} {A,C,D,E} {A,D,E} {A,B,C} {A,B,C,D} {B,C} {A,B,C} {A,B,D} {B,C,E}
A:1 B:1 Po přečtení TID=2:
null A:1 B:1
B:1
C:1 D:1
FP-Tree konstrukce TID 1 2 3 4 5 6 7 8 9 10
Items {A,B} {B,C,D} {A,C,D,E} {A,D,E} {A,B,C} {A,B,C,D} {B,C} {A,B,C} {A,B,D} {B,C,E}
Header Item Pointer table A B C D E
Transakční databáze
null B:3
A:7 B:5
C:1
C:3 D:1
C:3 D:1 D:1
D:1
D:1
E:1
E:1
E:1
FP-growth
C:1
Podmíněný základ pro D: P = {(A:1,B:1,C:1), (A:1,B:1), (A:1,C:1), (A:1), (B:1,C:1)}
D:1
Rekurzivně aplikuj FP-growth na P
null A:7 B:5
C:1
C:3
D:1
D:1 D:1
D:1
B:1
Nalezeny množiny FIS (podpora > 1): AD, BD, CD, ACD, BCD
Generování pravidel • Nechť L je FIS. Najdi všechny neprázdné podmnožiny f L takové, že f => L – f splňuje minimální požadavky spolehlivosti • je-li {A,B,C,D} množina FIS, kandidátní pravidla jsou: ABC => D, ABD => C, ACD => B, BCD => A, A => BCD, B => ACD, C => ABD, D => ABC AB => CD, AC => BD, AD => BC, BC => AD, BD => AC, CD => AB,
• Pokud |L| = k, pak existuje 2k – 2 kandidátních asociačních pravidel (ignorujme L and
L)
Generování pravidel Jak efektivně generovat pravidla z množin FIS? • obecně, podpora nemusí mít antimonotónní vlastnost c(ABC
D) může být větší či menší než c(AB
D)
• ale spolehlivost pravidle generovaných z téže množiny položek musí mít antimonotónní vlastnost tj. L = {A,B,C,D}:
c(ABC => D)
c(AB => CD)
c(A => BCD)
Generování pravidel Apriori algoritmem
ABCD=>{ }
Low Confide nce Rule CD=>AB
BCD=>A
BD=>AC
D=>ABC
Prořezávání pravidel
ACD=>B
BC=>AD
C=>ABD
ABD=>C
AD=>BC
B=>ACD
ABC=>D
AC=>BD
A=>BCD
AB=>CD
Generování pravidel Apriori algoritmem • Kandidátní pravidla jsou generována sloučením dvou pravidel, které sdílení stejný prefix v důsledku pravidla CD=>AB
• spojení (CD=>AB,BD=>AC) vytvoří kandidátní pravidlo D => ABC • prořež pravidlo D=>ABC pokud jeho podmnožina AD=>BC nemá vysokou spolehlivost
D=>ABC
BD=>AC
