GSP (Generalized Sequential Pattern)

Czym jest GSP?

GSP (Generalized Sequential Pattern) to klasyczny algorytm analizy sekwencji, który służy do identyfikacji wzorców sekwencyjnych w dużych zbiorach danych. GSP opiera się na generowaniu kandydatów i iteracyjnym wyszukiwaniu wzorców spełniających zadany minimalny próg wsparcia (\(min\_support\)). Algorytm jest rozwinięciem metody Apriori, ale został dostosowany do analizy danych sekwencyjnych.

Kluczowe pojęcia:

1. Sekwencja:

   • Zbiór elementów uporządkowanych chronologicznie, np. \([A \rightarrow B \rightarrow C]\).

2. Wzorzec sekwencyjny:

   • Sekwencja, która spełnia minimalny próg wsparcia.

3. Wsparcie (support):

   • Procentowy udział sekwencji zawierających dany wzorzec w całym zbiorze danych: \[ support(S) = \frac{\text{liczba sekwencji zawierających } S}{\text{liczba wszystkich sekwencji}} \]

4. Generowanie kandydatów:

   • Proces tworzenia możliwych wzorców sekwencyjnych na podstawie istniejących wzorców częstych.

Jak działa GSP?

1. Inicjalizacja:

   • Oblicz wsparcie dla wszystkich jednoelementowych sekwencji i wybierz te, które spełniają próg \(min\_support\).

2. Generowanie kandydatów:

   • Na podstawie częstych sekwencji z poprzedniej iteracji (\(L_k\)), wygeneruj kandydatów (\(C_{k+1}\)) poprzez łączenie wzorców o długości \(k\).

3. Obliczanie wsparcia:

   • Dla każdego kandydata w \(C_{k+1}\), sprawdź, ile sekwencji w zbiorze danych go zawiera.

4. Przycinanie:

   • Usuń kandydatów, którzy nie spełniają progu wsparcia (\(support < min\_support\)).

5. Powtórzenie:

   • Powtarzaj kroki 2–4, aż nie będzie możliwe wygenerowanie nowych kandydatów.

6. Zakończenie:

   • Wszystkie zidentyfikowane wzorce częste to wynik algorytmu.

Przykład działania:

Załóżmy następujący zbiór sekwencji:

Sekwencja	Zdarzenia
S1	\([A \rightarrow B \rightarrow C]\)
S2	\([A \rightarrow C]\)
S3	\([B \rightarrow C]\)
S4	\([A \rightarrow B \rightarrow D]\)
S5	\([A \rightarrow B \rightarrow C \rightarrow D]\)

Kroki:

1. Krok 1: Jednoelementowe wzorce:

   • Oblicz wsparcie dla każdego zdarzenia:
     • \(A: 4/5 = 0.8\), \(B: 4/5 = 0.8\), \(C: 4/5 = 0.8\), \(D: 2/5 = 0.4\).
   • Przyjmując \(min\_support = 0.6\), zdarzenie \(D\) jest odrzucone.

2. Krok 2: Dwuelementowe wzorce:

   • Wygeneruj kandydatów:
     • \([A \rightarrow B], [A \rightarrow C], [B \rightarrow C]\).
   • Oblicz wsparcie:
     • \(A \rightarrow B: 3/5 = 0.6\), \(A \rightarrow C: 3/5 = 0.6\), \(B \rightarrow C: 3/5 = 0.6\).
   • Wszystkie wzorce są częste.

3. Krok 3: Trójelementowe wzorce:

   • Wygeneruj kandydata:
     • \([A \rightarrow B \rightarrow C]\).
   • Oblicz wsparcie:
     • \(A \rightarrow B \rightarrow C: 2/5 = 0.4\).
   • Wzorzec nie spełnia progu \(min\_support\) i jest odrzucony.

Rezultat: Wzorce częste to \([A], [B], [C], [A \rightarrow B], [A \rightarrow C], [B \rightarrow C]\).

Zalety GSP:

• Prostota:
  • Algorytm jest łatwy do zrozumienia i implementacji.
• Wszechstronność:
  • Obsługuje dane z ograniczeniami czasowymi, np. maksymalna długość sekwencji lub minimalny odstęp czasowy między zdarzeniami.
• Efektywność w małych zbiorach danych:
  • GSP dobrze radzi sobie z małymi i średnimi zbiorami danych.

Wady GSP:

• Generowanie dużej liczby kandydatów:
  • Dla dużych zbiorów danych liczba potencjalnych kandydatów może być ogromna, co wpływa na wydajność.
• Koszt obliczeniowy:
  • Sprawdzanie wsparcia dla każdego kandydata wymaga wielokrotnego przechodzenia przez zbiór danych.

Zastosowania:

1. Handel detaliczny:
   • Identyfikacja wzorców zakupowych klientów w czasie.
2. Analiza logów:
   • Analiza sekwencji działań użytkowników na stronach internetowych.
3. Medycyna:
   • Analiza sekwencji zdarzeń medycznych, takich jak objawy czy terapie.
4. Bioinformatyka:
   • Odkrywanie wzorców w sekwencjach DNA lub RNA.

GSP to fundament analizy sekwencji, szczególnie w sytuacjach, gdy chcemy odkrywać często występujące wzorce w danych uporządkowanych czasowo. Jego prostota i skuteczność czynią go jednym z najpopularniejszych algorytmów w tej dziedzinie.