Menu

Algorytm wzrostu częstych wzorców (FP) w eksploracji danych

  • Główny
  • Inny
  • Algorytm wzrostu częstych wzorców (FP) w eksploracji danych

frequent pattern growth algorithm data mining

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Szczegółowy samouczek dotyczący algorytmu częstego wzrostu wzorców, który reprezentuje bazę danych w postaci drzewa FP. Obejmuje porównanie wzrostu PR z porównaniem Apriori:

Algorytm Apriori zostało szczegółowo wyjaśnione w naszym poprzednim samouczku. W tym samouczku dowiemy się o częstym wzroście wzorców - wzrost FP to metoda wydobywania częstych zestawów elementów.

podwójnie połączona lista w kodzie źródłowym C ++

Jak wszyscy wiemy, Apriori to algorytm do częstego eksploracji wzorców, który koncentruje się na generowaniu zestawów przedmiotów i odkrywaniu najczęstszych zestawów elementów. Znacznie zmniejsza rozmiar zestawu pozycji w bazie danych, jednak Apriori ma również swoje wady.

Przeczytaj nasze Cała seria szkoleń dotyczących eksploracji danych za pełną znajomość koncepcji.

Czego się nauczysz:

Wady algorytmu Apriori

  1. Korzystanie z Apriori wymaga wygenerowania zestawów pozycji kandydatów. Te zestawy elementów mogą być liczne, jeśli zestaw elementów w bazie danych jest ogromny.
  2. Apriori wymaga wielu skanów bazy danych, aby sprawdzić obsługę każdego wygenerowanego zestawu elementów, co prowadzi do wysokich kosztów.

Te niedociągnięcia można przezwyciężyć za pomocą algorytmu wzrostu FP.

Algorytm częstego wzrostu wzorców

Ten algorytm jest ulepszeniem metody Apriori. Generowany jest częsty wzorzec bez konieczności generowania kandydatów. Algorytm wzrostu FP przedstawia bazę danych w postaci drzewa zwanego częstym drzewem wzorców lub drzewem FP.

Ta struktura drzewa zachowa powiązanie między zestawami elementów. Baza danych jest podzielona na jeden częsty element. Ta fragmentaryczna część nazywana jest „fragmentem wzoru”. Analizowane są zestawy elementów tych fragmentarycznych wzorów. Tak więc w przypadku tej metody wyszukiwanie częstych zestawów przedmiotów jest stosunkowo ograniczone.

Drzewo FP

Drzewo częstych wzorców to struktura podobna do drzewa tworzona na podstawie początkowych zestawów elementów bazy danych. Celem drzewa FP jest wydobycie najczęstszego wzoru. Każdy węzeł drzewa FP reprezentuje element zestawu elementów.

Węzeł główny reprezentuje null, podczas gdy dolne węzły reprezentują zestawy elementów. Powiązanie węzłów z niższymi węzłami, czyli zestawami elementów z innymi zestawami elementów, jest zachowywane podczas tworzenia drzewa.

Częste kroki algorytmu wzorcowego

Metoda częstego wzrostu wzorców pozwala nam znaleźć częsty wzorzec bez generowania kandydatów.

Zobaczmy kroki, które należy wykonać, aby wydobyć częsty wzór przy użyciu algorytmu częstego wzrostu wzoru:

# 1) Pierwszym krokiem jest przeskanowanie bazy danych w celu znalezienia wystąpień zestawów elementów w bazie danych. Ten krok jest taki sam, jak pierwszy krok Apriori. Liczba zestawów 1 pozycji w bazie danych jest nazywana liczbą wsparcia lub częstotliwością zestawu 1 pozycji.

#dwa) Drugim krokiem jest skonstruowanie drzewa FP. W tym celu utwórz korzeń drzewa. Korzeń jest reprezentowany przez null.

# 3) Następnym krokiem jest ponowne przeskanowanie bazy danych i sprawdzenie transakcji. Zbadaj pierwszą transakcję i znajdź w niej zestaw przedmiotów. Zestaw przedmiotów z maksymalną liczbą jest brany na górze, następny zestaw przedmiotów z mniejszą liczbą i tak dalej. Oznacza to, że gałąź drzewa jest zbudowana z zestawów pozycji transakcji w malejącej kolejności liczenia.

# 4) Następna transakcja w bazie danych jest sprawdzana. Zestawy elementów są uporządkowane malejąco według liczebności. Jeśli jakikolwiek zestaw pozycji tej transakcji jest już obecny w innej gałęzi (na przykład w pierwszej transakcji), to ta gałąź transakcji będzie miała wspólny prefiks do katalogu głównego.

Oznacza to, że wspólny zestaw elementów jest połączony z nowym węzłem innego zestawu elementów w tej transakcji.

# 5) Ponadto liczba pozycji zestawu jest zwiększana, gdy występuje w transakcjach. Zarówno liczba wspólnych węzłów, jak i liczba nowych węzłów są zwiększane o 1 w miarę ich tworzenia i łączenia zgodnie z transakcjami.

# 6) Następnym krokiem jest wydobycie utworzonego drzewa FP. W tym celu najniższy węzeł jest badany jako pierwszy wraz z łączami najniższych węzłów. Najniższy węzeł reprezentuje długość wzorca częstotliwości 1. Następnie przejdź ścieżką w drzewie FP. Ta ścieżka lub ścieżki są nazywane warunkową podstawą szyku.

Warunkowa baza wzorców to sub-baza danych składająca się ze ścieżek przedrostków w drzewie FP występujących w najniższym węźle (sufiksie).

# 7) Skonstruuj warunkowe drzewo FP, które jest tworzone przez liczbę zestawów elementów w ścieżce. Zestawy przedmiotów spełniające wymagania progowe są uwzględniane w warunkowym drzewie PR.

# 8) Częste wzorce są generowane z warunkowego drzewa FP.

Przykład algorytmu wzrostu FP

Próg wsparcia = 50%, zaufanie = 60%

narzędzie do skanowania i naprawy komputera z systemem Windows 10

Tabela 1

TransakcjaLista rzeczy
Zużycie pamięci
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Rozwiązanie:

Próg wsparcia = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Liczba każdej pozycji

Tabela 2

PozycjaLiczyć
I14
I25
I34
I44
I5dwa

2. Posortuj zestaw pozycji w porządku malejącym.

Tabela 3

PozycjaLiczyć
I25
I14
I34
I44

3. Zbuduj drzewo FP

  1. Biorąc pod uwagę zerowy węzeł główny.
  2. Pierwszy skan transakcji T1: I1, I2, I3 zawiera trzy elementy {I1: 1}, {I2: 1}, {I3: 1}, gdzie I2 jest połączone jako dziecko z rootem, I1 jest połączone z I2 i I3 jest powiązany z I1.
  3. T2: I2, I3, I4 zawiera I2, I3 i I4, gdzie I2 jest połączone z rootem, I3 jest połączone z I2, a I4 jest połączone z I3. Ale ta gałąź będzie współdzielić węzeł I2 tak często, jak jest już używany w T1.
  4. Zwiększ liczbę I2 o 1, a I3 jest połączone jako dziecko z I2, I4 jest połączone jako dziecko z I3. Liczba to {I2: 2}, {I3: 1}, {I4: 1}.
  5. T3: I4, I5. Podobnie, nowa gałąź z I5 jest połączona z I4, gdy tworzone jest dziecko.
  6. T4: I1, I2, I4. Sekwencja będzie miała postać I2, I1 i I4. I2 jest już połączone z węzłem głównym, dlatego będzie zwiększane o 1. Podobnie I1 będzie zwiększane o 1, ponieważ jest już połączone z I2 w T1, a zatem {I2: 3}, {I1: 2}, {I4: 1}.
  7. T5: I1, I2, I3, I5. Sekwencja będzie miała postać I2, I1, I3 i I5. A zatem {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
  8. T6: I1, I2, I3, I4. Sekwencja będzie miała postać I2, I1, I3 i I4. Zatem {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

Drzewo FP

4. Wydobywanie drzewa FP podsumowano poniżej:

  1. Najniższy element węzła I5 nie jest brany pod uwagę, ponieważ nie ma minimalnej liczby podparć, dlatego jest usuwany.
  2. Następny niższy węzeł to I4. I4 występuje w 2 gałęziach, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Dlatego biorąc pod uwagę I4 jako przyrostek, ścieżki prefiksów będą miały postać {I2, I1, I3: 1}, {I2, I3: 1}. Tworzy to warunkową podstawę wzorca.
  3. Podstawa wzorca warunkowego jest traktowana jako baza danych transakcji, konstruowane jest drzewo FP. Będzie zawierać {I2: 2, I3: 2}, I1 nie jest brane pod uwagę, ponieważ nie spełnia minimalnej liczby wsparcia.
  4. Ta ścieżka wygeneruje wszystkie kombinacje częstych wzorców: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
  5. Dla I3, ścieżka prefiksu będzie wyglądać następująco: {I2, I1: 3}, {I2: 1}, to wygeneruje 2-węzłowe drzewo FP: {I2: 4, I1: 3} i generowane są częste wzorce: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
  6. Dla I1 ścieżka prefiksu będzie wyglądać następująco: {I2: 4} to wygeneruje pojedyncze drzewo FP: {I2: 4} i generowane są częste wzorce: {I2, I1: 4}.
PozycjaWarunkowa podstawa wzoruWarunkowe drzewo FPGenerowanie częstych wzorców
I4{I2, I1, I3: 1}, {I2, I3: 1}{I2: 2, I3: 2}{I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
I3{I2, I1: 3}, {I2: 1}{I2: 4, I1: 3}{I2, I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}
I1{I2: 4}{I2: 4}{I2, I1: 4}

Poniższy diagram przedstawia warunkowe drzewo FP powiązane z węzłem warunkowym I3.

drzewo warunkowe FP powiązane z węzłem warunkowym I3

Zalety algorytmu wzrostu FP

  1. Ten algorytm musi skanować bazę danych tylko dwa razy w porównaniu do metody Apriori, która skanuje transakcje dla każdej iteracji.
  2. W tym algorytmie nie odbywa się parowanie elementów, co przyspiesza.
  3. Baza danych jest przechowywana w kompaktowej wersji w pamięci.
  4. Jest wydajna i skalowalna do wydobywania zarówno długich, jak i krótkich częstych wzorców.

Wady algorytmu wzrostu FP

  1. Drzewo FP jest bardziej nieporęczne i trudniejsze do zbudowania niż Apriori.
  2. To może być kosztowne.
  3. Gdy baza danych jest duża, algorytm może nie zmieścić się w pamięci współdzielonej.

Wzrost FP vs Apriori

Wzrost FPApriori
Generowanie wzorców
Wzrost FP generuje wzorzec, konstruując drzewo FPApriori generuje wzór, łącząc elementy w pojedyncze, pary i trojaczki.
Pokolenie kandydatów
Nie ma pokolenia kandydatówApriori używa generowania kandydatów
Proces
Proces jest szybszy w porównaniu do Apriori. Czas działania procesu rośnie liniowo wraz ze wzrostem liczby zestawów elementów.Proces jest stosunkowo wolniejszy niż wzrost FP, czas wykonywania rośnie wykładniczo wraz ze wzrostem liczby zestawów elementów
Zapisywana jest kompaktowa wersja bazy danychKombinacje kandydatów są zapisywane w pamięci

BLASK

Powyższa metoda, wzrost Apriori i FP, pozwala eksplorować częste zestawy elementów przy użyciu poziomego formatu danych. ECLAT to metoda eksploracji częstych zbiorów pozycji przy użyciu pionowego formatu danych. Przekształci dane w formacie poziomym w format pionowy.

Na przykład,Zastosowanie Apriori i FP:

TransakcjaLista rzeczy
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Tabela ECLAT będzie miała format:

PozycjaZestaw transakcji
I1{T1, T4, T5, T6}
I2{T1, T2, T4, T5, T6}
I3{T1, T2, T5, T6}
I4{T2, T3, T4, T5}
I5{T3, T5}

Ta metoda utworzy zestawy 2 elementów, 3 zestawy elementów, k zestawów elementów w pionowym formacie danych. Ten proces z k jest zwiększany o 1, dopóki nie zostaną znalezione żadne zestawy pozycji kandydatów. Niektóre techniki optymalizacji, takie jak diffset, są używane wraz z Apriori.

Ta metoda ma przewagę nad Apriori, ponieważ nie wymaga skanowania bazy danych w celu znalezienia wsparcia dla k + 1 zestawów elementów. Dzieje się tak, ponieważ zbiór transakcji będzie zawierał liczbę wystąpień każdej pozycji w transakcji (wsparcie). Wąskie gardło pojawia się, gdy wiele transakcji wymaga dużej pamięci i czasu obliczeniowego na przecięcie zbiorów.

najlepszy sposób na konwersję filmów z YouTube na mp3

Wniosek

Algorytm Apriori jest używany do reguł asocjacji wyszukiwania. Działa na zasadzie: „niepuste podzbiory zbiorów częstych również muszą być częste”. Tworzy kandydatów na k-itemset z (k-1) itemsets i skanuje bazę danych w celu znalezienia częstych zestawów elementów.

Algorytm częstego wzrostu wzorców to metoda znajdowania częstych wzorców bez generowania kandydatów. Konstruuje drzewo FP zamiast używać strategii generowania i testowania Apriori. Głównym celem algorytmu wzrostu FP jest fragmentacja ścieżek elementów i eksploracja częstych wzorców.

Mamy nadzieję, że te samouczki z serii Data Mining wzbogaciły Twoją wiedzę o Data Mining !!

POPRZEDNIA samouczek | PIERWSZY samouczek

rekomendowane lektury

^