ED-4.2-m06-1.0-Slajd7
PrefixSpan (1)
W przypadku niektórych dziedzin zastosowań metody odkrywania wzorców sekwencji, takich jak analiza łańcuchów DNA czy też analiza akcji giełdowych, liczba odkrywanych wzorców sekwencji może być relatywnie bardzo duża. Co więcej, również odkrywane sekwencje mogą być bardzo długie. Stąd, pojawiła się potrzeba opracowania nowych skalowalnych algorytmów odkrywania wzorców sekwencji, które wykorzystując podstawową własność ogólnego algorytmu odkrywania wzorców sekwencji (monotoniczność miary wsparcia), redukowałyby kosztowność etapu sekwencjonowania i gwarantowałyby tym samym znacznie większą efektywność i skalowalność procesu odkrywania wzorców sekwencji. Powstały nowe pomysły i algorytmy, które rozwiązywałyby te problemy. Algorytm o nazwie FreeSpan, który w procesie odkrywania wzorców sekwencji wykorzystuje ideą projekcji bazy danych na osobne partycje w celu zredukowania czasu generowania sekwencji kandydujących i obliczania wsparcia tych sekwencji. Ogólna idea algorytmu polega na wykorzystaniu zbiorów częstych do rekursywnej dekompozycji bazy danych na mniejsze partycje i generowaniu sekwencji kandydujących w ramach każdej partycji. W konsekwencji, algorytm generuje znacznie mniejszy zbiór sekwencji kandydujących i uzyskuje istotną poprawę efektywności w stosunku do przedstawionego podstawowego algorytmu odkrywania wzorców sekwencji. Rozwinięciem algorytmu FreeSpan jest algorytm PrefixSpan. Ogólna idea algorytmu PrefixSpan polega na analizie prefiksów sekwencji kandydujących i rekursywnym partycjonowaniu bazy danych w oparciu o postfiksy generowanych sekwencji. Algorytm PrefixSpan uzyskuje dodatkową poprawę efektywności w stosunku do algorytmu FreeSpan poprzez redukcję rozmiarów partycjonowanych baz danych i zmniejszenie liczby analizowanych sekwencji kandydujących. Algorytm PrefixSpan generuje rekursywnie wzorce sekwencji o rozmiarze k w oparciu o wzorce sekwencji o rozmiarze (k-1), i, de facto, nie generuje ani też nie analizuje sekwencji kandydujących. Algorytm PrefixSpan składa się z trzech kroków. W pierwszym kroku następuje znajdowanie wzorców sekwencji o rozmiarze 1. W drugim kroku dzielimy przestrzeń poszukiwań na partycje. Krok trzeci to analiza podzbiorów sekwencji przechowywanych w partycjach.
