ED-4.2-m02-1.0-Slajd27

Algorytm naiwny

Naiwny algorytm odkrywania zbiorów częstych składa się z trzech głównych kroków.

1. Dany jest zbiór elementów I i baza danych D.
2. Wygeneruj wszystkie możliwe podzbiory zbioru I i następnie, dla każdego podzbioru oblicz wsparcie tego zbioru w bazie danych D.
3. Dla każdego zbioru, którego wsparcie jest większe/równe minsup, wygeneruj regułę asocjacyjną – dla każdej otrzymanej reguły oblicz ufność reguły.

Trywialna metoda znajdowania zbiorów częstych mogłaby polegać na wygenerowaniu wszystkich podzbiorów zbioru I i, następnie, na obliczeniu, dla każdego podzbioru Li wartości wsparcia tego podzbioru. W praktyce takie rozwiązanie jest nieakceptowalne ze względu na ilość potencjalnych zbiorów częstych. Liczba wszystkich możliwych podzbiorów zbioru I wynosi 2^|I| - 1, gdzie |I|, w zastosowaniach praktycznych (np. analizie koszyka), może sięgać nawet 300 000 elementów.

<< Poprzedni slajd | Spis treści | Następny slajd >>