ED-4.2-m06-1.0-Slajd6
Wady algorytmów Apriori-Like
Przedstawiony podstawowy algorytm odkrywania wzorców sekwencji, pomimo, że znacznie redukuje przestrzeń analizowanych sekwencji kandydujących, cechuje się jednak bardzo wysoką złożonością obliczeniową. Algorytm posiada trzy istotne wady:
Potencjalnie bardzo duża liczba sekwencji kandydujących . Zbiór sekwencji kandydujących zawiera wszystkie możliwe permutacje elementów z powtórzeniami, co prowadzi do generacji bardzo dużych zbiorów sekwencji. Przykładowo, dla zbioru sekwencji częstych o długości 1 zawierającego 1000 sekwencji, liczba 2-sekwencji kandydujących wynosi 1000 x 1000 = 1,000,000. Liczba 3-sekwencji kandydujących, w najgorszym przypadku, może wynosić 1000^3 = 1,000,000,000. Ogólnie mówiąc, liczba możliwych wzorców sekwencji o długości k jest rzędu O(m^k 2^{k-1}), gdzie m oznacza liczbę wszystkich zdarzeń w bazie danych.
Wielokrotne odczyty bazy danych . Dla każdego wygenerowanego zbioru sekwencji kandydujących należy wykonać pełen odczyt bazy danych w celu wyliczenia wsparcia sekwencji kandydujących. Oznacza to, że aby znaleźć wzorzec sekwencji o długości 20 należy wykonać 20 odczytów bazy danych.
Problemy z odkrywaniem bardzo długich wzorców sekwencji . Jak wspomnieliśmy już wcześniej, liczba sekwencji kandydujących zależy wykładniczo od długości sekwencji odkrywanych w bazie danych. Oznacza to, że aby znaleźć w bazie danych wzorzec sekwencji o długości 100, liczba sekwencji kandydujących wygenerowanych przez algorytm jest rzędu 2^{100}.
