Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.PODSTAWOWYALGORYTMODKRYWANIAREGUŁ
cjipionowej,gdybazadanychskładasięzwielunmałych”transakcji.Algorytmy
eksploracjipionowejsąnatomiastbardziejefektywnewprzypadkudużychtrans-
akcji,tojesttransakcjizawierającychwieleelementów.
Przejdziemyobecniedoprzedstawienianajpopularniejszychinajbardziej
znanychalgorytmówodkrywaniazbiorówczęstychzgrupyalgorytmóweksplora-
cjipoziomejialgorytmóweksploracjipionowej.
Algorytmyeksploracjipoziomej:algorytmApriori
Pierwszymalgorytmemodkrywaniabinarnychregułasocjacyjnych,wktórymjest
wykorzystywanawłasnośćantymonotonicznościmiarywsparciadoograniczenia
przestrzeniposzukiwańzbiorówczęstych,byłwspomnianyjużwcześniejalgorytm
Apriori.Jesttoalgorytmiteracyjny,którywkolejnychkrokach(iteracjach)znajdu-
jezbioryczęsteorozmiarach1,2,...,k.Załóżmy,żeelementykażdejtransakcji
zezbioruDsąuporządkowaneleksykograficznie3).Pierwszymkrokiemalgorytmu
jestwyodrębnieniezbazydanychDwszystkichzbiorów1-elementowych,które
występująwtransakcjach,isprawdzenie,któreznichsączęste(mająwsparcieco
najmniejminsup).Następnie,opierającsięna1-elementowychzbiorachczęstych,
algorytmgeneruje2-elementowezbiorykandydujące(ang.candidateitemsets),
którepotencjalniemogąbyćzbioramiczęstymi.Dlakażdegowygenerowanego
zbiorukandydującegoobliczanejestjegowsparciewbaziedanychD.Jeżeliobli-
czonewsparciezbiorukandydującegowynosiconajmniejminsup,tojestondołą-
czanydolistyzbiorówczęstychiwkolejnymkrokuzostaniewykorzystanydoge-
neracji3-elementowychzbiorówkandydujących.Następnie3-elementowezbiory
częstesąwykorzystywanedogeneracji4-elementowychzbiorówkandydujących,
4-elementowezbioryczęstesąwykorzystywanedogeneracji5-elementowychzbio-
rówkandydującychitd.Wkażdymkolejnymkroku,opierającsięnazbiorachczę-
stychznalezionychwpoprzednimkroku,algorytmgenerujezbiorykandydujące
orozmiarzewiększymo1.Wceluobliczeniawsparciazbiorówkandydujących
wkażdymkrokualgorytmujestdokonywanyodczytbazydanychD.Działanie
algorytmusiękończy,gdyniemożnajużwygenerowaćkolejnychzbiorówkan-
dydujących.Wynikiemdziałaniaalgorytmujestsumak-elementowychzbiorów
częstych(k=1,2,...).Zbiorytesąnastępniewykorzystywanedogeneracjireguł
asocjacyjnychzgodniezalgorytmem2.2.
FormalnyopismetodyApriori,wczęścidotyczącejodkrywaniazbiorówczę-
stych,przedstawiapseudokodalgorytmu2.3.Wopisiealgorytmuzastosowanona-
stępującąnotację:Ckoznaczarodzinęk-elementowychzbiorówkandydujących,
Lk–rodzinęk-elementowychzbiorówczęstych,c.count–licznikzliczającyliczbę
transakcjiwspierającychzbiórelementówc,apriori_gen()–funkcję,któragene-
3)Jeżelinawettransakcjeniesąwewnętrznieposortowane,tokrokiemwstępnymalgorytmumoże
byćleksykograficzneuporządkowanieelementówtransakcji.
25
