PrefixSpan (Prefix Projected Sequential Pattern Mining)

Czym jest PrefixSpan?

PrefixSpan (Prefix Projected Sequential Pattern Mining) to wydajny algorytm analizy sekwencji, który identyfikuje wzorce sekwencyjne poprzez eksplorację prefiksów w danych. Zamiast generować kandydatów, jak w algorytmie GSP, PrefixSpan dzieli zbiór danych na mniejsze „projekcje” w oparciu o wspólne prefiksy, co znacząco redukuje koszty obliczeniowe.

Kluczowe koncepcje:

1. Prefiks:

   • Fragment sekwencji rozpoczynający się od pierwszego zdarzenia i zawierający kolejne elementy, np. prefiks sekwencji \([A \rightarrow B \rightarrow C]\) to \([A]\), \([A \rightarrow B]\), \([A \rightarrow B \rightarrow C]\).

2. Projekcja:

   • Podzbiór danych zawierający tylko te części sekwencji, które zaczynają się od określonego prefiksu.

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}} \]

Jak działa PrefixSpan?

1. Inicjalizacja:

   • Znajdź wszystkie jednoelementowe sekwencje (\(k = 1\)) i oblicz ich wsparcie. Zidentyfikuj te, które spełniają próg minimalnego wsparcia (\(min\_support\)).

2. Podział na projekcje:

   • Dla każdego prefiksu utwórz jego „projekcję” danych – podzbiór zawierający sekwencje, które zaczynają się od danego prefiksu.

3. Rekursywne rozszerzanie prefiksów:

   • Dla każdej projekcji znajdź kolejne elementy, które można dodać do prefiksu, tworząc nowe wzorce. Oblicz wsparcie dla tych rozszerzonych prefiksów.

4. Przycinanie:

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

5. Powtórzenie:

   • Powtarzaj proces, aż żadne nowe wzorce nie będą mogły zostać wygenerowane.

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 (\(k = 1\)):

   • Znajdź wszystkie jednoelementowe wzorce i oblicz wsparcie:
     • \(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\), wzorzec \(D\) jest odrzucony.

2. Krok 2: Projekcja dla \(A\):

   • Dla prefiksu \(A\) utwórz projekcję:
     • \([B \rightarrow C], [C], [B \rightarrow D], [B \rightarrow C \rightarrow D]\).
   • Znajdź nowe wzorce, np. \(A \rightarrow B\), \(A \rightarrow C\).

3. Krok 3: Rekursywne rozszerzanie:

   • Dla prefiksu \(A \rightarrow B\) utwórz kolejną projekcję i znajdź rozszerzenia:
     • Projekcja: \([C], [D], [C \rightarrow D]\).
     • Wzorce: \(A \rightarrow B \rightarrow C\), \(A \rightarrow B \rightarrow D\).

4. Zakończenie:

   • Kontynuuj proces dla kolejnych prefiksów, aż wszystkie możliwe wzorce spełniające \(min\_support\) zostaną znalezione.

Rezultat: Zidentyfikowane wzorce częste to np. \(A \rightarrow B\), \(A \rightarrow C\), \(A \rightarrow B \rightarrow C\).

Zalety PrefixSpan:

• Unikanie generowania kandydatów:
  • Algorytm działa na zasadzie podziału zbioru danych na projekcje, co eliminuje konieczność generowania wszystkich możliwych wzorców.
• Efektywność:
  • PrefixSpan jest szybszy i bardziej skalowalny niż algorytmy takie jak GSP, zwłaszcza w dużych zbiorach danych.
• Kompresja danych:
  • Projekcje pozwalają na analizę mniejszych podzbiorów danych, co zmniejsza zapotrzebowanie na pamięć.

Wady PrefixSpan:

• Skomplikowana implementacja:
  • Algorytm jest bardziej złożony w implementacji niż prostsze metody, takie jak GSP.
• Problemy z dużą liczbą wzorców:
  • Dla niskich wartości \(min\_support\) liczba generowanych wzorców może być bardzo duża.

Zastosowania:

1. Analiza logów:
   • Analiza ścieżek nawigacyjnych użytkowników na stronach internetowych.
2. Handel detaliczny:
   • Identyfikacja wzorców zakupowych klientów w czasie.
3. Bioinformatyka:
   • Odkrywanie wzorców w sekwencjach genetycznych.
4. Bezpieczeństwo IT:
   • Analiza sekwencji zdarzeń w logach systemowych w celu wykrywania ataków.

PrefixSpan to nowoczesne podejście do analizy sekwencji, które dzięki wykorzystaniu prefiksów i projekcji znacząco poprawia wydajność w porównaniu do starszych algorytmów. Jego zdolność do efektywnego odkrywania wzorców sprawia, że jest popularnym narzędziem w wielu dziedzinach.