ED-4.2-m05-1.0-Slajd13
Podstawowy algorytm odkrywania wzorców sekwencji GSP
Pierwszy algorytm odkrywania wzorców sekwencji przedstawiono w roku 1995. Algorytm ten, nazwaliśmy "podstawowym algorytmem odkrywania wzorców sekwencji", jest on rozszerzeniem klasycznego algorytmu Apriori dla danych sekwencyjnych i wykorzystuje własność monotoniczności miary wsparcia: jeżeli sekwencja X nie jest wzorcem sekwencji (tj. nie spełnia warunku minimalnego wsparcia), to żadna sekwencja Y, zawierająca sekwencję X, nie może być wzorcem sekwencji.
Algorytm składa się z pięciu następujących kroków:
Krok 1 – sortowanie. Posortuj bazę danych D w taki sposób, aby uzyskać bazę danych sekwencji DS.
Krok 2 - znajdowanie zbiorów częstych. Znajdź wszystkie zbiory częste w bazie danych sekwencji DS.
Krok 3 – transformacja. Przetransformuj każdy wyraz sekwencji w listę zbiorów częstych zawierających się w tym wyrazie.
Krok 4 – sekwencjonowanie. Znajdujemy wszystkie częste sekwencje.
Krok 5 – maksymalizacja. – jest krokiem opcjonalnym i polega na usunięciu wszystkich wzorców sekwencji, które nie są maksymalne.
