ED-4.2-m03-1.0-Slajd3
Algorytm 1.3 Apriori
W opisie algorytmu zastosowano następującą notację: C_k oznacza rodzinę zbiorów kandydujących k-elementowych, L_k oznacza rodzinę zbiorów częstych k-elementowych, c.count oznacza licznik zliczający liczbę transakcji wspierających zbiór elementów c, apriori_gen () oznacza funkcję, opisaną na kolejnym slajdzie, która generuje zbiory kandydujące, natomiast subset() oznacza funkcję, która dla danej transakcji t zwraca wszystkie zbiory kandydujące wspierane przez t. W pierwszym kroku algorytm zlicza wystąpienia wszystkich elementów w bazie danych D w celu wyodrębnienia zbiorów częstych 1-elementowych (L_1). Każdy kolejny k-ty krok algorytmu składa się z dwóch faz. W pierwszej, funkcja apriori_gen(), w oparciu o zbiory częste należące do L_{k-1}, generuje zbiory kandydujące k-elementowe (C_k). W drugiej fazie k-tego kroku jest realizowany odczyt bazy danych D i dla każdego zbioru kandydującego c ze zbioru C_k jest obliczane wsparcie zbioru c w bazie danych D, {wsparcie}(c). W celu zapewnienia odpowiedniej efektywności procedury obliczania wsparcia zbiorów kandydujących, algorytm Apriori wykorzystuje strukturę danych postaci drzewa haszowego, która służy do przechowywania zbiorów kandydujących. Procedura subset() zwraca te zbiory kandydujące należące do C_k, które są wspierane przez transakcję t.
Jeżeli zbiór kandydujący c spełnia warunek minimalnego wsparcia, to jest, {wsparcie}(c)>= minsup, to zbiór ten jest dodawany do listy zbiorów częstych, w przeciwnym razie zbiór ten jest usuwany z listy zbiorów kandydujących. Podstawowe znaczenie dla efektywności działania algorytmu Apriori ma rozwiązanie dwóch problemów szczegółowych: jak zapewnić efektywność procedury generowania zbiorów kandydujących, oraz, jak zapewnić efektywność procedury obliczania wsparcia dla tych zbiorów. Pierwszy z wymienionych problemów dotyczy efektywności funkcji apriori_gen().
