ED-4.2-m05-1.0-Slajd16

From Studia Informatyczne

Krok 3: transformacja

Krok 3: transformacja


Kolejnym krokiem algorytmu jest krok transformacji. Celem kroku transformacji jest zastąpienie każdego wyrazu T sekwencji S w uporządkowaną listę zbiorów częstych zawierających się w wyrazie T. W wyniku tej transformacji są usuwane z wyrazu T wszystkie te elementy, które nie są częste i które, tym samym, nie mogą wystąpić we wzorcach sekwencji. Jeżeli sekwencja nie zawiera żadnych zbiorów częstych, to nie wchodzi ona do transformowanej bazy danych. Brana jest ona jednak pod uwagę przy obliczaniu wsparcia wzorca sekwencji. Stąd, po zakończeniu kroku transformacji, każda sekwencja jest reprezentowana w bazie danych sekwencji DS w postaci uporządkowanej listy wyrazów będących zbiorami częstymi. Stąd dla naszego przykładu musimy wykonać następujące kroki: Przetransformuj każdy wyraz sekwencji w listę zbiorów częstych zawierających się w tym wyrazie, następnie przetransformuj każdy zbiór częsty w liczbę naturalną. Ma to na celu uproszczenie obliczeń. Dla ilustracji tego kroku rozważmy następujący przykład umieszczony na slajdzie. Załóżmy, że dane są następujące zbiory częste {{A},{B},{C},{BC}} znalezione w bazie sekwencji DS. Załóżmy, że przyjęliśmy następujące odwzorowanie – zbiór częsty {A} jest reprezentowany przez liczbę naturalną 1, zbiór częsty {B} jest reprezentowany przez liczbę naturalną 2, zbiór częsty {C} jest reprezentowany przez liczbę naturalną 3 oraz zbiór częsty {BC} reprezentowany przez liczbę 4. Dla podanej oryginalnej sekwencji postaci: {{D},{A},{(B E C)}}. Zauważmy, że wyraz pierwszy tej sekwencji zawiera element D, który nie jest zbiorem częstym – dlatego zostanie usunięty z naszej sekwencji. Kolejny wyraz A jest zbiorem częstym, pozostaje w naszej sekwencji, itd. W wyniku transformacji otrzymamy następującą sekwencję dwuwyrazową: {{(A)}, {(B), (C), (B C)}} oraz sekwencja po odwzorowaniu: {{1},{2, 3, 4}}.




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