Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZDZIAŁ2.ODKRYWANIEASOCJACJI
rujezbiorykandydujące,asubset()–funkcję,któradladanejtransakcjitzwra-
cawszystkiezbiorykandydującewspieraneprzezt(funkcjasubset()jestopisana
szczegółowowp.2.4.3).
Algorytm203FazaodkrywaniazbiorówczęstychalgorytmuApriori
Wejście:bazadanychD,prógminimalnegowsparcia.
Wyjście:wszystkiezbioryczęstezbazydanychD.
1:L1←1-elementowezbioryczęste;
2:for(k=2;Lk−1/=0;k++)do
3:
4:
5:
6:
7:
8:
9:
Ck←apriori_gen(Lk−1);
foralltransakcjitEDdo
endfor
Ct←subset(Ck,t);
endfor
c.count++;
forallzbiorówkandydującychcECtdo
10:
Lk←{cECk|c.count>minsup};
11:endfor
12:returnUkLk;
Wpierwszymkrokualgorytmzliczawystąpieniawszystkichelementów
wbaziedanychDwceluwyodrębnienia1-elementowychzbiorówczęstych(L1).
Każdykolejnyk-tykrokalgorytmuskładasięzdwóchfaz.Wpierwszejfaziefunk-
cjaapriori_gen(),napodstawiezbiorówczęstychnależącychdoLk−1,generuje
k-elementowezbiorykandydujące(Ck).Wdrugiejfaziek-tegokrokujestreali-
zowanyodczytbazydanychDidlakażdegozbiorukandydującegoczezbio-
ruCkjestobliczanewsparciezbiorucwbaziedanychD,wsparcie(c).Wcelu
zapewnieniaodpowiedniejefektywnościproceduryobliczaniawsparciazbiorów
kandydującychalgorytmAprioriwykorzystujestrukturędanychpostacidrzewa
haszowego,którasłużydoprzechowywaniazbiorówkandydujących.Procedura
subset()zwracatezbiorykandydującenależącedoCk,któresąwspieraneprzez
transakcjęt.Jeżelizbiórkandydującycspełniawarunekminimalnegowsparcia,
wsparcie(c)>minsup,tozbiórtenjestdodawanydolistyzbiorówczęstych.
Wprzeciwnymraziezbiórtenjestusuwanyzlistyzbiorówkandydujących.
PodstawoweznaczeniedlaefektywnościdziałaniaalgorytmuApriorimaroz-
wiązaniedwóchproblemówszczegółowych:jakzapewnićefektywnośćprocedu-
rygenerowaniazbiorówkandydującychorazjakzapewnićefektywnośćprocedury
obliczaniawsparciadlatychzbiorów.
Pierwszyzwymienionychproblemówwiążesięzzapewnieniemefektyw-
nościfunkcjiapriori_gen().Funkcjaapriori_gen()jestrealizowanawdwóchkro-
kach:
26
