Czy FPGrowth jest nadal uważany za „najnowocześniejszy” w częstym wydobywaniu wzorów?

O ile wiem rozwój algorytmów do rozwiązania problemu Frequent Pattern Mining (FPM), droga ulepszeń ma kilka głównych punktów kontrolnych. Po pierwsze, algorytm Apriori został zaproponowany w 1993 r. Przez Agrawal i in. wraz z sformalizowaniem problemu. Algorytm był w stanie usunąć niektóre zestawy z 2^n - 1zestawów (powerset) za pomocą sieci do przechowywania danych. Wadą tego podejścia była konieczność ponownego odczytu bazy danych w celu obliczenia częstotliwości każdego rozszerzonego zestawu.

Później, w roku 1997, Zaki i in. zaproponował algorytm Eclat , który wstawiał wynikową częstotliwość każdego zestawu do sieci. Dokonano tego poprzez dodanie, w każdym węźle sieci, zestawu identyfikatorów transakcji, które miały elementy z katalogu głównego do wskazanego węzła. Główny wkład polega na tym, że nie trzeba ponownie czytać całego zestawu danych, aby poznać częstotliwość każdego zestawu, ale pamięć wymagana do utrzymania takiej struktury danych może przekraczać rozmiar samego zestawu danych.

W 2000 r. Han i in. zaproponował algorytm o nazwie FPGrowth wraz ze strukturą danych drzewa prefiksów o nazwie FPTree. Algorytm był w stanie zapewnić znaczną kompresję danych, jednocześnie zapewniając, że uzyskiwane byłyby tylko częste zestawy przedmiotów (bez generowania zestawu przedmiotów kandydujących). Dokonano tego głównie poprzez sortowanie pozycji każdej transakcji w malejącej kolejności, tak aby najczęstszymi pozycjami były te z najmniejszą liczbą powtórzeń w strukturze danych drzewa. Ponieważ częstotliwość maleje tylko podczas dogłębnego przemierzania drzewa, algorytm jest w stanie usunąć rzadkie zestawy przedmiotów.

Edytuj :

O ile mi wiadomo, można uznać to za najnowocześniejszy algorytm, ale chciałbym wiedzieć o innych proponowanych rozwiązaniach. Jakie inne algorytmy dla FPM są uważane za „najnowocześniejsze”? Jaka jest intuicja / główny wkład takich algorytmów?

Czy algorytm FPGrowth jest nadal uważany za „najnowocześniejszy” w częstym wydobywaniu wzorów? Jeśli nie, to jaki algorytm (algorytmy) może wydajniej wyodrębniać częste zestawy przedmiotów z dużych zestawów danych?

Najnowocześniejszy jak w: stosowany w praktyce czy pracował w teorii?

APRIORI jest używany wszędzie, z wyjątkiem opracowywania nowych algorytmów częstych zestawów przedmiotów. Jest łatwy do wdrożenia i wielokrotnego użytku w bardzo różnych domenach. Znajdziesz setki implementacji APRIORI o różnej jakości. Właściwie łatwo jest pomylić APRIORI.

Rozwój FP jest znacznie trudniejszy do wdrożenia, ale także o wiele bardziej interesujący. Tak więc z akademickiego punktu widzenia wszyscy starają się poprawić FPgrowth - uzyskanie pracy opartej na APRIORI będzie do tej pory bardzo trudne.

Jeśli masz dobrą implementację, każdy algorytm ma swoją dobrą i moim zdaniem złe sytuacje. Dobra implementacja APRIORI będzie musiała tylko przeskanować bazę danych k razy, aby znaleźć wszystkie częste zestawy elementów o długości k . W szczególności, jeśli dane mieszczą się w głównej pamięci, jest to tanie. Tym, co może zabić APRIORI, jest zbyt wiele częstych zestawów 2 przedmiotów (w szczególności, gdy nie używasz Trie i podobnych technik przyspieszania itp.). Działa najlepiej w przypadku dużych danych z małą liczbą częstych zestawów przedmiotów.

Eclat działa na kolumnach; ale musi czytać każdą kolumnę znacznie częściej. Jest trochę pracy nad diffsetami, aby ją zmniejszyć. Jeśli twoje dane nie mieszczą się w głównej pamięci, Eclat cierpi prawdopodobnie bardziej niż Apriori. Po przejściu w głąb głębokości będzie mógł również zwrócić pierwszy interesujący wynik znacznie wcześniej niż Apriori i możesz użyć tych wyników do dostosowania parametrów; więc potrzebujesz mniej iteracji, aby znaleźć dobre parametry. Ale z założenia nie może wykorzystywać przycinania tak starannie, jak zrobił to Apriori.

FPGrowth kompresuje zestaw danych do drzewa. Działa to najlepiej, gdy masz dużo zduplikowanych rekordów. Prawdopodobnie mógłbyś czerpać całkiem spore korzyści dla Apriori i Eclata, jeśli potrafisz przetłumaczyć swoje dane i połączyć duplikaty w wektory ważone. FPGrowth robi to na ekstremalnym poziomie. Wadą jest to, że wdrożenie jest znacznie trudniejsze; a gdy to drzewo nie pasuje już do pamięci, robi się bałagan do zaimplementowania.

Jeśli chodzi o wyniki wydajności i testy porównawcze - nie ufaj im. Jest tak wiele rzeczy do nieprawidłowego wdrożenia. Wypróbuj 10 różnych implementacji, a otrzymasz 10 bardzo różnych wyników. W szczególności w przypadku APRIORI mam wrażenie, że większość implementacji jest zepsuta w sensie pominięcia niektórych głównych wkładów APRIORI ... a tych, które mają odpowiednie części, jakość optymalizacji jest bardzo różna.

Istnieją nawet dokumenty na temat efektywnego wdrażania tych algorytmów:

Skuteczne wdrożenia Apriori i Eclat.
Christian Borgelt
Workshop of Frequent Set Set Mining Implementations (FIMI 2003, Melbourne, Floryda, USA).

Możesz także przeczytać te ankiety w tej domenie:

• Goethals, Bart. „Badanie częstego wydobywania wzorów”. Univ. z Helsinek (2003).

• Ferenc Bodon, Ankieta na temat częstego wydobywania przedmiotów, Raport techniczny, Politechnika Budapeszteńska i Ekonomiczna, 2006,

• Częsty zestaw przedmiotów Mining
  Christian Borgelt
  Wiley Recenzje interdyscyplinarne: Data Mining and Knowledge Discovery 2 (6): 437-456. 2012

Większość najnowszych podejść do częstych wzorców, które widziałem w literaturze, opiera się na optymalizacji FPGrowth. Muszę przyznać, że od wielu lat nie widziałem wielu zmian w literaturze dotyczącej FPM.

Ta wikibook opisuje wiele dostępnych wariantów FPGrowth.