Przejdź do treści
Wróć do wyników wyszukiwania

FP-Growth (algorytm wzrostu częstych wzorców)

Autor metody
Jiawei Han, Jian Pei & Yiwen Yin
Rok
2000
Typ
Frequent-itemset mining algorithm
Rodzina
Pattern mining

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

FP-Growth, wprowadzony przez Jiawei Han, Jian Pei i Yiwen Yin w 2000 roku, wyszukuje częste zbiory elementów z danych transakcyjnych bez generowania zbiorów kandydujących — kosztownego etapu, który spowalnia klasyczny algorytm Apriori.

Kompresuje bazę danych do drzewa częstych wzorców (FP-tree) w dwóch przebiegach, a następnie rekurencyjnie rozwija częste wzorce z tej struktury, co czyni go znacznie szybszym od Apriori na dużych, gęstych zbiorach danych.

Intuicja stojąca za metodą

Apriori znajduje częste zbiory elementów poprzez powtarzalne generowanie i testowanie kombinacji kandydujących — kosztowny proces wymagający wielu przebiegów, który eksploduje przy gęstych danych. FP-Growth podąża inną ścieżką: ściska całą bazę danych transakcyjnych w zwarte drzewo, gdzie wspólne prefiksy są przechowywane raz, dzięki czemu wspólne wzorce nakładają się i kompresują. Następnie, zamiast generować kandydatów, odczytuje częste wzorce bezpośrednio z drzewa, podążając ścieżkami prowadzącymi do każdego elementu i rekurencyjnie wyszukując mniejsze, „warunkowe” drzewa. Dwa przejścia przez dane i pomysłowa struktura danych zastępują wiele przejść Apriori i kombinatoryczny wybuch kandydatów.

Historia

Han, Pei i Yin przedstawili FP-Growth na SIGMOD 2000 jako alternatywę dla Apriori bez generowania kandydatów, z rozszerzonym opisem w artykule z 2004 roku w Data Mining and Knowledge Discovery. Idea drzewa częstych wzorców — kompresowania transakcji do wspólnej struktury prefiksowej i rekurencyjnego wyszukiwania w niej — stała się fundamentalną techniką w eksploracji wzorców, obok Apriori (opartego na kandydatach) i ECLAT (format pionowy). Pozostaje standardowym, wydajnym narzędziem do wyszukiwania zbiorów elementów w bibliotekach do eksploracji danych.

Kiedy stosować

Użyj FP-Growth do wyszukiwania częstych zbiorów elementów (a w dalszej kolejności reguł asocjacyjnych) z danych transakcyjnych — analizy koszyków zakupów, analizy użytkowania sieci i strumieni kliknięć, rekomendacji oraz współwystępowania w bioinformatyce — szczególnie na dużych lub gęstych zbiorach danych, gdzie generowanie kandydatów przez Apriori jest zbyt wolne. Wymaga tylko dwóch przebiegów bazy danych i zazwyczaj znacznie przewyższa Apriori. Jego koszty: FP-tree musi zmieścić się w pamięci (ograniczenie dla bardzo dużych lub ekstremalnie rzadkich danych, gdzie drzewo słabo się kompresuje), rekurencja może być skomplikowana w implementacji, a jak cała eksploracja oparta na wsparciu, jest wrażliwy na minimalny próg wsparcia (zbyt niski powoduje eksplozję wyników, zbyt wysoki pomija wzorce). ECLAT (pionowe przecięcie zbiorów identyfikatorów transakcji) jest alternatywą; dla samych reguł, połącz z generowaniem reguł asocjacyjnych.

Ograniczenia i uwagi

  • FP-tree musi zmieścić się w pamięci; bardzo duże zbiory danych mogą nie spełniać tego warunku.
  • Na rzadkich danych drzewo słabo się kompresuje, niwelując przewagę.
  • Rekurencyjna konstrukcja drzew warunkowych jest stosunkowo złożona w implementacji.
  • Czuły na minimalny próg wsparcia, jak cała eksploracja częstych zbiorów elementów.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Brak generowania kandydatów — znacznie szybszy od Apriori na dużych/gęstych danych.
  • Tylko dwa przebiegi bazy danych, niezależnie od długości wzorca.
  • FP-tree kompresuje wspólną strukturę, oszczędzając pamięć i czas na gęstych danych.
  • Skaluje się do długich częstych wzorców, które przytłaczają metody oparte na kandydatach.

Zastosowania

  • Analiza koszyków zakupów i eksploracja reguł asocjacyjnych w handlu detalicznym.
  • Eksploracja wzorców użytkowania sieci i strumieni kliknięć.
  • Rekomendacje poprzez często współwystępujące elementy.
  • Współwystępowanie i odkrywanie motywów w bioinformatyce.
  • Każde zadanie związane z częstymi zbiorami elementów na dużą skalę, gdzie Apriori jest zbyt wolne.

Jak to działa

Jak to działa

1

Pierwszy przebieg bazy danych zlicza wsparcie każdego elementu i odrzuca te poniżej minimalnego progu wsparcia. Pozostałe częste elementy są sortowane według malejącej częstości — to uporządkowanie pozwala transakcjom dzielić prefiksy drzewa i utrzymuje FP-tree w zwartej postaci.

Wzór
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Drugi przebieg wstawia każdą transakcję (jej częste elementy, w posortowanej kolejności) do FP-tree, zwiększając liczniki wzdłuż wspólnych ścieżek prefiksowych i dodając nowe gałęzie w razie potrzeby. Tabela nagłówkowa łączy wszystkie wystąpienia każdego elementu, dzięki czemu drzewo zwarcie reprezentuje częstą strukturę całego zbioru danych.

Wzór
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Dla każdego częstego elementu (przetwarzanego od najrzadszego do najczęstszego), algorytm zbiera jego bazę wzorców warunkowych — zbiór ścieżek prefiksowych w drzewie, które współwystępują z tym elementem, każda ważona jego liczbą. To wychwytuje kontekst, w którym element pojawia się często.

Wzór
\text{for each item: collect its conditional pattern base (prefix paths)}
4

Z każdej bazy wzorców warunkowych budowane jest mniejsze, warunkowe FP-tree, które jest rekurencyjnie przeszukiwane, rozwijając dłuższe częste zbiory elementów poprzez dodanie elementu do wzorców znalezionych w jego drzewie warunkowym. Rekurencja kończy się na drzewach o pojedynczych ścieżkach, których kombinacje zbiorów elementów są wyliczane bezpośrednio — dając wszystkie częste zbiory elementów bez generowania kandydatów.

Wzór
\text{build conditional FP-trees recursively to grow frequent patterns}

Częste pułapki

  • Ustawienie minimalnego wsparcia zbyt nisko, powodujące eksplozję zbiorów elementów.
  • Zakładanie, że zawsze pokonuje Apriori — na małych lub rzadkich danych zysk jest niewielki.
  • Zapominanie, że częste zbiory elementów to nie reguły; generowanie reguł jest osobnym krokiem.
  • Niedostrzeganie ograniczeń pamięciowych, gdy FP-tree nie może być przechowywany w pamięci RAM.

Najczęściej zadawane pytania

Jak FP-Growth jest szybszy od Apriori?

Apriori wielokrotnie generuje i testuje zestawy kandydujących elementów, przeglądając bazę danych wielokrotnie. FP-Growth całkowicie unika generowania kandydatów: kompresuje dane do FP-tree w dwóch przebiegach i wyszukuje wzorce rekurencyjnie z niego. Eliminuje to kombinatoryczny wybuch kandydatów, zapewniając duże przyspieszenie na gęstych danych.

Czym jest FP-tree?

Skompresowane drzewo prefiksowe częstych elementów bazy danych. Transakcje dzielące prefiks dzielą ścieżkę, z licznikami węzłów rejestrującymi wsparcie, a tabela nagłówkowa łączy wystąpienia każdego elementu. Kompaktowo przechowuje częstą strukturę zbioru danych, dzięki czemu wzorce można odczytać bez ponownego przeglądania danych.

Jak FP-Growth ma się do ECLAT i reguł asocjacyjnych?

FP-Growth, ECLAT i Apriori znajdują częste zbiory elementów; ECLAT używa podejścia pionowego przecięcia zbiorów identyfikatorów transakcji zamiast drzewa. Znajdowanie częstych zbiorów elementów to tylko pierwszy etap — reguły asocjacyjne (z ufnością/przyrostem (confidence/lift)) są generowane z tych zbiorów elementów w osobnym kroku.

Pokrewne metody

Źródła

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    Otwórz odnośnik DOI
    Skopiowano.