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

Górnictwo częstych zbiorów elementów ECLAT

Autor metody
Mohammed J. Zaki
Rok
2000
Typ
Frequent-itemset mining algorithm (vertical format)
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?

ECLAT, wprowadzony przez Mohammeda Zakiego w 2000 roku, wydobywa częste zbiory elementów przy użyciu pionowej reprezentacji danych: zamiast skanować transakcje, przechowuje dla każdego elementu zbiór identyfikatorów transakcji (zbiór TID), które go zawierają, i oblicza wsparcie dla dowolnego zbioru elementów poprzez przecięcie zbiorów TID.

To podejście oparte na przeszukiwaniu w głąb i przecięciach jest szybkie i oszczędne pod względem pamięci, stanowiąc alternatywę dla poziomych skanowań Apriori i drzewa FP-Growth.

Intuicja stojąca za metodą

Większość algorytmów wydobywania zbiorów elementów myśli wiersz po wierszu: które elementy znajdują się w danej transakcji? ECLAT odwraca tę perspektywę. Dla każdego elementu przechowuje listę transakcji, które go zawierają. Wsparcie dla pary elementów to po prostu rozmiar nakładania się ich list — proste przecięcie zbiorów — i nigdy nie trzeba ponownie skanować bazy danych. Aby znaleźć dłuższe częste zbiory elementów, należy przeciąć listy krótszych. Przechodzenie w głąb i przycinanie gałęzi, gdy przecięcie staje się zbyt małe, efektywnie wylicza wszystkie częste zbiory elementów.

Historia

Mohammed Zaki wprowadził ECLAT i pionowy paradygmat wydobywania w pracy, która zakończyła się jego artykułem w IEEE TKDE z 2000 roku na temat skalowalnego wydobywania asocjacji, później udoskonalając go o diffsety (dECLAT). Dołączył do Apriori (1994, generowanie kandydatów w poziomie) i FP-Growth (2000, oparte na drzewach) jako jedna z trzech kanonicznych rodzin algorytmów wydobywania częstych zbiorów elementów, z których każda inaczej równoważy skanowania, pamięć i gęstość danych. ECLAT pozostaje standardową opcją w zestawach narzędzi do eksploracji danych.

Kiedy stosować

Używaj ECLAT do wydobywania częstych zbiorów elementów, gdy pionowe podejście oparte na przecięciach pasuje do danych — jest często bardzo szybkie na gęstych zbiorach danych i unika powtarzania skanowania bazy danych, co czyni je silną alternatywą dla Apriori i konkurentem dla FP-Growth. Sprawdza się, gdy zbiory TID są umiarkowane pod względem rozmiaru i mieszczą się w pamięci, a wariant diffset dobrze radzi sobie z gęstymi danymi. Jego wady: zbiory TID dla częstych elementów mogą być duże i obciążające pamięć na dużych, rzadkich zbiorach danych, pośrednie przecięcia generują narzut, a podobnie jak wszystkie metody oparte na wsparciu, jest wrażliwy na minimalny próg wsparcia. Jak zawsze, częste zbiory elementów to tylko pierwszy etap; reguły asocjacyjne z miarami ufności/lift są generowane później. Wybieraj spośród ECLAT, FP-Growth i Apriori w zależności od gęstości danych i pamięci.

Ograniczenia i uwagi

  • Zbiory TID dla częstych elementów mogą być duże, co kosztuje pamięć na dużych zbiorach danych.
  • Pośrednie wyniki przecięć dodają narzut pamięciowy/czasowy.
  • Mniej intuicyjny niż poziome reprezentacje (Apriori).
  • Wrażliwy na minimalny próg wsparcia, jak wszystkie algorytmy wydobywania zbiorów elementów.

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

Mocne strony

  • Wsparcie obliczane przez szybkie przecięcia zbiorów TID — brak powtarzania skanowania bazy danych.
  • Przeszukiwanie w głąb z klasami równoważności prefiksów ponownie wykorzystuje pracę i lokalizuje pamięć.
  • Często bardzo wydajny na gęstych zbiorach danych, konkurencyjny z FP-Growth.
  • Optymalizacja diffset dodatkowo zmniejsza zużycie pamięci i koszt przecięć.

Zastosowania

  • Wydobywanie asocjacji w koszykach sklepowych i handlu detalicznym.
  • Analiza współwystępowania w sieci i strumieniach kliknięć.
  • Odkrywanie częstych współwystępowania w bioinformatyce.
  • Każde zadanie związane z wydobywaniem częstych zbiorów elementów faworyzujące pionowe podejście oparte na przecięciach.
  • Gęste zbiory danych transakcyjnych, gdzie ECLAT z diffsetami przoduje.

Jak to działa

Jak to działa

1

Baza danych jest transformowana raz do formatu pionowego: każdy element mapuje się na jego zbiór TID, czyli zbiór identyfikatorów transakcji, w których występuje. Jest to kluczowa struktura danych — wszystkie późniejsze operacje to operacje na zbiorach TID, a nie przejścia przez oryginalne transakcje.

Wzór
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

Wsparcie dla zbioru elementów to moc przecięcia zbiorów TID jego elementów — liczba transakcji zawierających wszystkie z nich. Zliczanie staje się przecięciem, co jest szybkie, a częste pojedyncze elementy (te, których zbiór TID jest wystarczająco duży) stanowią punkt wyjścia dla wyszukiwania.

Wzór
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Zbiory elementów są rozszerzane przez przecięcie zbiorów TID: zbiór TID dla X ∪ {y} to przecięcie zbiorów TID dla X i {y}. ECLAT eksploruje kratę zbiorów elementów w głąb w obrębie klas równoważności (zbiorów elementów o tym samym prefiksie), dzięki czemu przecięcia są ponownie wykorzystywane, a wyszukiwanie pozostaje lokalne.

Wzór
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

Rozszerzenie jest zachowywane tylko wtedy, gdy jego zbiór TID (a tym samym wsparcie) spełnia minimalny próg wsparcia; w przeciwnym razie dana gałąź jest przycinana (antymonotoniczność: żaden nadzbiór nie może być częsty). Różnicowe zbiory (Diffsets) — przechowujące tylko różnice między zbiorami TID — są powszechną optymalizacją, która dodatkowo zmniejsza zużycie pamięci i koszt przecięć.

Wzór
\text{keep extensions with } \text{support} \ge \text{minsup}

Częste pułapki

  • Wydobywanie bardzo dużych, rzadkich danych, gdzie zbiory TID pochłaniają pamięć — rozważ diffsety lub FP-Growth.
  • Ustawienie zbyt niskiego minimalnego wsparcia, co prowadzi do niezarządzalnej liczby zbiorów elementów.
  • Mylenie częstych zbiorów elementów z regułami asocjacyjnymi (reguły to osobny krok).
  • Ignorowanie wariantu diffset na gęstych danych, gdzie znacznie pomaga.

Najczęściej zadawane pytania

Czym ECLAT różni się od Apriori i FP-Growth?

Wszystkie trzy algorytmy znajdują częste zbiory elementów. Apriori używa formatu poziomego z generowaniem kandydatów i wieloma skanowaniami; FP-Growth kompresuje dane do drzewa i wydobywa rekurencyjnie; ECLAT używa pionowego formatu zbiorów TID i oblicza wsparcie poprzez przecięcie list identyfikatorów transakcji w głąb. ECLAT i FP-Growth unikają powtarzanych skanowań Apriori.

Czym jest zbiór TID?

Zbiór TID (zbiór identyfikatorów transakcji) to lista transakcji zawierających dany element lub zbiór elementów. ECLAT przechowuje je w sposób pionowy i oblicza wsparcie dla zbioru elementów jako moc przecięcia zbiorów TID jego elementów, zamieniając zliczanie na przecięcie zbiorów.

Czym są diffsety?

Diffsety przechowują tylko różnicę między zbiorem TID zbioru elementów a zbiorem TID jego rodzica, zamiast pełnego zbioru TID. Na gęstych danych drastycznie zmniejsza to zużycie pamięci i koszt przecięć, dając wariantowi dECLAT znaczną przewagę wydajnościową.

Pokrewne metody

Źródła

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    Otwórz odnośnik DOI
    Skopiowano.