ED-4.2-m06-1.0-Slajd16
Efektywność algorytmu PrefixSpan
Jak pokazały badania ewaluacyjne, algorytm PrefixSpan charakteryzuje się znacznie wyższą efektywnością aniżeli podstawowy algorytm odkrywania wzorców sekwencji. Wynika to z dwóch zasadniczych przyczyn: po pierwsze w przeciwieństwie do podstawowego algorytmu odkrywania wzorców sekwencji, opartego na idei algorytmu Apriori, algorytm PrefixSpan nie generuje sekwencji kandydujących, lecz buduje sekwencje częste w sposób przyrostowy w oparciu o wcześniej odkryte sekwencje częste, oraz po drugie w ramach kroku „sekwencjonowania”, to jest znajdowania sekwencji częstych, algorytm PrefixSpan analizuje projekcyjne bazy danych, które są znacznie mniejsze od wyjściowej, oryginalnej bazy danych. Co więcej, w kolejnych iteracjach algorytmu, rozmiary tych baz danych znacząco maleją. Łatwo zauważyć jednak, że główny koszt algorytmu PrefixSpan kryje się w koszcie konstrukcji projekcyjnych baz danych. Gdyby można było zredukować rozmiar i\lub liczbę projekcyjnych baz danych generowanych przez algorytm, wówczas znacząco poprawiłoby to efektywność algorytmu. Jednym ze sposobów redukcji liczby i rozmiarów projekcyjnych baz danych generowanych przez algorytm PrefixSpan jest zastosowanie dwupoziomowego schematu projekcji (ang. bi-level projection).
