Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZDZIAŁ2.ODKRYWANIEASOCJACJI
2.4.2.Algorytmyodkrywaniazbiorówczęstych
Jakjużwspomnieliśmywcześniej,problemodkrywaniabinarnychregułasocjacyj-
nychbyłbardzointensywnieanalizowanyod1993r.izaproponowanoszeregalgo-
rytmówodkrywaniasilnychbinarnychregułasocjacyjnychróżniącychsięgłównie
dwomaelementami:metodąodkrywaniazbiorówczęstychorazmetodąobliczania
wsparciazbiorówelementów.Algorytmytemożnapodzielićnadwiezasadnicze
grupywzależnościodorganizacjilogicznejeksplorowanychdanych:
(1)algorytmyeksploracjipoziomej,nazywanerównieżalgorytmamieksploracji
wierszowej(ang.horizontalminingalgorithmslubrow-wiseminingalgori-
thms);
(2)algorytmyeksploracjipionowej,nazywanerównieżalgorytmamieksploracji
kolumnowej(ang.verticalminingalgorithmslubcolumn-wiseminingalgo-
rithms).
Wprzypadkualgorytmóweksploracjipoziomejwierszebazydanychrepre-
zentujątransakcje,zktórychkażdajestzbioremelementówzezbioruL.Wprzy-
padkualgorytmóweksploracjipionowejwierszebazydanychreprezentująpo-
szczególneelementyzbioruL.Zkażdymelementemjestzwiązanyzbióriden-
tyfikatorówtransakcji,którezawierajądanyelement.Wymienionedwasposoby
logiczneorganizacjidanychsąprzedstawionewtab.2.4.
Tabela2040Organizacjadanych:(a)pozioma,(b)pionowa
trans_id
1
2
3
4
5
produkt
coca_cola,orzeszki
piwo,orzeszki,pieluszki
coca_cola
coca_cola,piwo,orzeszki
piwo,orzeszki,pieluszki
(a)
produkt
piwo
pieluszki
orzeszki
coca_cola
trans_id_list
2,4,5
2,5
1,2,4,5
1,3,4
(b)
Obiegrupyalgorytmówróżniąsię,pozaorganizacjąlogicznąeksplorowa-
nychdanych,równieżmetodamiobliczaniawartościwsparciazbiorówelemen-
tów.Walgorytmacheksploracjipoziomejdoobliczeniawartościwsparciazbioru
elementówXsąodczytywanekolejneblokibazydanychidlakażdejkrotkibazy
danych,opisującejtransakcję,jestsprawdzane,czydanatransakcjawspierazbiór
elementówX.ObliczeniewartościwsparciazbioruelementówXwymagazatem
pełnegoodczytuwszystkichtransakcjizbazydanych.Walgorytmacheksploracji
pionowejdoobliczeniawartościwsparciazbioruelementówXsąwykorzystywane
listyidentyfikatorówtransakcji(atrybuttrans_id_list).Obliczeniewartościwspar-
ciazbioruXpoleganaznalezieniuiloczynulogicznegozbiorówidentyfikatorów
transakcjizawierającychelementyzbioruXiobliczeniujegorozmiaru.Wykazano,
żealgorytmyeksploracjipoziomejsąbardziejefektywneniżalgorytmyeksplora-
24