Algorytm GSP - GSP algorithm

Algorytm GSP (ang. Generalized Sequential Pattern Algorytm) to algorytm używany do eksploracji sekwencji . Algorytmy rozwiązywania problemów eksploracji sekwencji są w większości oparte na algorytmie apriori (poziomowym). Jednym ze sposobów wykorzystania paradygmatu opartego na poziomach jest odkrycie wszystkich częstych elementów w sposób uwzględniający poziomy. Oznacza to po prostu zliczanie wystąpień wszystkich pojedynczych elementów w bazie danych. Następnie transakcje są filtrowane poprzez usunięcie nieczęstych pozycji. Na końcu tego kroku każda transakcja składa się tylko z częstych elementów, które pierwotnie zawierała. Ta zmodyfikowana baza danych staje się danymi wejściowymi do algorytmu GSP. Ten proces wymaga jednego przejścia przez całą bazę danych .

Algorytm GSP wykonuje wiele przejść do bazy danych. W pierwszym przebiegu liczone są wszystkie pojedyncze pozycje (1-sekwencje). Z częstych pozycji tworzony jest zestaw kandydujących 2-sekwencji i wykonywana jest kolejna passa w celu określenia ich częstotliwości. Częste 2-sekwencje są wykorzystywane do generowania kandydujących 3-sekwencji i ten proces jest powtarzany, aż nie zostaną znalezione częstsze sekwencje. Algorytm składa się z dwóch głównych kroków.

  • Pokolenie kandydatów. Mając zbiór częstych (k-1)-częstych sekwencji F k-1 , kandydaci do następnego przebiegu są generowane przez połączenie F(k-1) ze sobą. Faza przycinania eliminuje każdą sekwencję, przynajmniej jedna z podsekwencji nie występuje często.
  • Liczenie wsparcia. Zwykle do wydajnego zliczania wsparcia stosuje się wyszukiwanie oparte na drzewie haszującym . Wreszcie niemaksymalnie częste sekwencje są usuwane.

Algorytm

   F1 = the set of frequent 1-sequence
   k=2,
   do while Fk-1 != Null;
       Generate candidate sets Ck (set of candidate k-sequences);
       For all input sequences s in the database D
       do
           Increment count of all a in Ck if s supports a
       End do
       Fk = {a ∈ Ck such that its frequency exceeds the threshold}
       k = k+1;
   End do
   Result = Set of all frequent sequences is the union of all Fk's

Powyższy algorytm wygląda jak algorytm Apriori . Jedną z głównych różnic jest jednak generowanie zestawów kandydujących. Załóżmy, że:

A → B i A → C

to dwie częste sekwencje 2 . Pozycje biorące udział w tych sekwencjach to odpowiednio (A, B) i (A, C). Pokolenie kandydatów w zwykłym stylu Apriori dałoby (A, B, C) jako zestaw 3-elementowy, ale w obecnym kontekście otrzymujemy następujące 3-sekwencje w wyniku połączenia powyższych 2-sekwencji

A → B → C, A → C → B i A → BC

Uwzględnia to faza generowanie kandydatów. Algorytm GSP wykrywa częste sekwencje, pozwalając na ograniczenia czasowe, takie jak maksymalna przerwa i minimalna przerwa między elementami sekwencji. Co więcej, wspiera koncepcję przesuwającego się okna, tj. przedziału czasu, w którym przedmioty są obserwowane jako należące do tego samego zdarzenia, nawet jeśli pochodzą z różnych zdarzeń.

Zobacz też

Bibliografia

Zewnętrzne linki

  • SPMF zawiera implementację algorytmu GSP o otwartym kodzie źródłowym, a także PrefixSpan , SPADE, SPAM, ClaSP, CloSpan i BIDE.