Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.3.ODKRYWANIEBINARNYCHREGUŁASOCJACYJNYCH
Zbiórsilnychbinarnychregułasocjacyjnych,któremożnaznaleźćwprzed-
stawionejwtab.2.3baziedanychsupermarketu,zakładającwartośćminimalnego
wsparciaminsup=0,4iminimalnejufnościminconf=0,5,jestnastępujący:
piwo→orzeszki
orzeszki→piwo
piwo∧pieluszki→orzeszki
pieluszki∧orzeszki→piwo
pieluszki→piwo∧orzeszki
pieluszki→piwo
pieluszki→orzeszki
piwo∧orzeszki→pieluszki
piwo→pieluszki∧orzeszki
piwo→pieluszki
coca_cola→orzeszki
orzeszki→piwo∧pieluszki
orzeszki→pieluszki
orzeszki→coca_cola
wsparcie=0,60
ufność=1,00,
wsparcie=0,60
ufność=0,75,
wsparcie=0,40
ufność=1,00,
wsparcie=0,40
ufność=1,00,
wsparcie=0,40
ufność=1,00,
wsparcie=0,40
ufność=1,00,
wsparcie=0,40
ufność=1,00,
wsparcie=0,40
ufność=0,67,
wsparcie=0,40
ufność=0,67,
wsparcie=0,40
ufność=0,67,
wsparcie=0,40
ufność=0,67,
wsparcie=0,40
ufność=0,50,
wsparcie=0,40
ufność=0,50,
wsparcie=0,40
ufność=0,50.
Weźmy,dlaprzykładu,jednązwymienionychwyżejreguł:piwo→orzeszki
(wsparcie=0,60,ufność=1,00).Interpretacjatejregułyjestnastępująca.Klienci,
którzykupująproduktpiwo,kupująrównież,zawsze,produktorzeszki.Takapara
produktówwystępujew60%wszystkichtransakcjiklienckich.Drugazeznalezio-
nychreguł,orzeszki→piwo,maidentycznąwartośćwsparciacoregułapierwsza,
aleinnąwartośćufności.
I
Trywialnepodejściedoproblemuodkrywaniabinarnychregułasocjacyjnych,
nazwijmyjepodejściemnaiwnym,polegałobynawygenerowaniudladanegozbio-
ruelementówLibazydanychDwszystkichmożliwychbinarnychregułasocjacyj-
nych,obliczeniuwsparciaiufnościwygenerowanychreguł,anastępnienaodrzu-
ceniutychreguł,któreniesąsilne,toznaczy,którychwsparcieiufnośćniespeł-
niająwarunkówminimalnegowsparciaiminimalnejufności.Wpraktycetakie
podejściejestnieakceptowalnezewzględunabardzodużąliczbęgenerowanych
regułasocjacyjnych,dlaktórychnależyobliczyćwartościmiarwsparciaiufności.
Należyzauważyć,żeobliczeniewartościmiarwsparciaiufnościdladanejregu-
ływymagakosztownegodostępudobazydanych.Liczbawszystkichmożliwych
podzbiorówzbioruelementówL,zktórychmożnawygenerowaćbinarneregu-
łyasocjacyjne,wynosi2|L|−1.Liczbawszystkichmożliwychregułasocjacyjnych,
któremożnawygenerowaćdlazbioruelementówL,wynosi3|L|−2|L|+1+1.Przypo-
mnijmy,żewprzypadkueksploracjirzeczywistychdanych,naprzykładeksploracji
bazydanychsiecisklepów,liczbaelementówzbioru|L|wynosi100000–300000
elementów.NawetdlaniewielkichzbiorówelementówLliczbawygenerowanych
19