ED-4.2-m04-1.0-Slajd15

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Generowanie zbiorów częstych

Generowanie zbiorów częstych


Istnieje szereg wariantów nakreślonego powyżej ogólnego algorytmu odkrywania wielopoziomowych reguł asocjacyjnych o zmiennym progu minimalnego wsparcia. Warianty te różnią się przyjętą strategią przeszukiwania przestrzeni zbiorów kandydujących:

Strategia niezależnych poziomów jest strategią wyczerpującą, która zakłada, że poziomy taksonomii są wzajemnie niezależne. Oznacza to, że w fazie generowania zbiorów kandydujących każdy wierzchołek taksonomii jest analizowany niezależnie od swoich poprzedników lub następników. Innymi słowy, wszystkie wierzchołki taksonomii reprezentują ten sam poziom abstrakcji, to jest, reprezentują niezależne elementy (podobnie jak w przypadku odkrywania binarnych reguł asocjacyjnych). W konsekwencji, strategia niezależnych poziomów analizuje wsparcie każdego zbioru kandydującego niezależnie od tego, czy jego poprzednik w taksonomii elementów jest zbiorem częstym czy też nie. Niestety, prowadzi to do analizy wielu zbiorów kandydujących, które z definicji nie są zbiorami częstymi.

Strategia krzyżowej filtracji zbioru k-elementowego zakłada, że analizie poddawane są tylko te zbiory kandydujące, których elementy są następnikami zbiorów częstych k-elementowych. Przykładowo, jeżeli zbiór „piwo, pieczywo” jest zbiorem częstym, to zbiorami kandydującymi poddawanymi analizie są, na przykład, zbiory „piwo_żywiec, bułki_kajzerki” lub „piwo_lech, rogale”. Ta strategia, z kolei, prowadzi do automatycznego odrzucenia wielu interesujących częstych zbiorów kandydujących, takich, dla których poprzedniki elementów należących do tych zbiorów nie są częste. Przykładowo, załóżmy, że wsparcie nazwanej grupy elementów „piwo_żywiec”, występującej na i-tym poziomie taksonomii, jest większe od prógu minimalnego wsparcia zdefiniowanego dla tego poziomu taksonomii, natomiast wsparcie nazwanej grupy elementów "piwo"', występującej na i-1-tym poziomie taksonomii, jest mniejsze aniżeli próg minimalnego wsparcia dla poziomu i-1 taksonomii. Strategia krzyżowej filtracji zbioru k-elementowego automatycznie odrzuci zbiór częsty „piwo_żywiec, art. higieny”, który może być zbiorem częstym.

Strategia krzyżowej filtracji pojedynczego elementu jest próbą kompromisu pomiędzy wspomnianymi wcześniej strategiami przeszukiwania przestrzeni zbiorów kandydujących. Zbiór kandydujący jest analizowany na i-tym poziomie jeżeli jego poprzednik na poziomie i-1 jest zbiorem częstym. Innymi słowy, jeżeli zbiór x na poziomie i jest częsty, to analizie są poddawane jego następniki. Przykładowo, jeżeli zbiór „piwo” nie jest częsty, to w dalszej analizie pomija się zbiory „piwo_żywiec" oraz „piwo_lech”. Strategia ta posiada jednak podobną wadę jak strategia krzyżowej filtracji zbioru k-elementowego, to jest, może ona prowadzić do automatycznego odrzucenia interesujących częstych zbiorów kandydujących, takich, dla których poprzedniki elementów należących do tych zbiorów nie są częste. Próbą rozwiąania tego problemu było zaproponowanie zmodyfikowanej wersji strategii krzyżowej filtracji pojedynczego elementu, nazwanej kontrolowaną strategią krzyżowej filtracji pojedynczego elementu (ang. controlled level-cross filtering strategy by single item).


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