ED-4.2-m03-1.0-Slajd2
Algorytm Apriori
Pierwszym algorytmem odkrywania binarnych reguł asocjacyjnych, który wykorzystał własność monotoniczności miary wsparcia do ograniczenia przestrzeni poszukiwań zbiorów częstych, był algorytm Apriori. Algorytm ten jest algorytmem iteracyjnym, który w kolejnych krokach (iteracjach) znajduje zbiory częste o rozmiarach 1, 2, ..., k. Zakładamy, że elementy każdej transakcji ze zbioru D są uporządkowane leksykograficznie {Jeżeli nawet transakcje nie są wewnętrznie posortowane, to krokiem wstępnym algorytmu może być leksykograficzne uporządkowanie elementów transakcji.}. Pierwszym krokiem algorytmu jest wyodrębnienie z bazy danych D wszystkich zbiorów jednoelementowych, które występują w transakcjach, i sprawdzenie, które z nich są częste (posiadają wsparcie co najmniej minsup). Następnie, w oparciu o zbiory częste jednoelementowe algorytm generuje zbiory kandydujące (ang. candidate itemsets) dwuelementowe, które, potencjalnie mogą być zbiorami częstymi. Dla każdego wygenerowanego zbioru kandydującego obliczane jest jego wsparcie w bazie danych D. Jeżeli obliczone wsparcie zbioru kandydującego wynosi co najmniej minsup, to jest on dołączany do listy zbiorów częstych i w kolejnym kroku zostanie on wykorzystany do generacji zbiorów kandydujących trzyelementowych. Następnie, zbiory częste trzyelementowe są wykorzystywane do generacji zbiorów kandydujących czteroelementowych, zbiory częste czteroelementowe są wykorzystywane do generacji zbiorów kandydujących pięcioelementowych, itd. W każdym kolejnym kroku, w oparciu o zbiory częste znalezione w poprzednim kroku, algorytm generuje zbiory kandydujące o rozmiarze większym o 1. W celu obliczenia wsparcia zbiorów kandydujących, w każdym kroku algorytmu jest dokonywany odczyt bazy danych D. Działanie algorytmu się kończy, gdy nie ma można już wygenerować kolejnych zbiorów kandydujących. Wynikiem działania algorytmu jest suma k-elementowych zbiorów częstych (k=1, 2,...).
