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
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
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}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}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)}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
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
Otwórz odnośnik DOISkopiowano.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 DOISkopiowano.