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

Górnictwo reguł asocjacyjnych (Apriori)

Autor metody
Rakesh Agrawal & Ramakrishnan Srikant
Rok
1994
Typ
Unsupervised pattern discovery 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?

Górnictwo reguł asocjacyjnych to technika uczenia nienadzorowanego, która odkrywa wzorce współwystępowania między elementami w zbiorach danych transakcyjnych.

Formalnie wprowadzone przez Agrawala, Imielińskiego i Swami w 1993 roku, a udoskonalone dzięki przełomowemu algorytmowi Apriori przez Agrawala i Srikanta w 1994 roku, identyfikuje reguły postaci X ⇒ Y — co oznacza, że transakcje zawierające zbiór elementów X mają tendencję do zawierania również zbioru elementów Y — kwantyfikowane przez wsparcie, pewność i lift.

Intuicja stojąca za metodą

Wyobraźmy sobie dziennik paragonów z supermarketu: jeśli tysiące klientów, którzy kupują chleb i masło, kupuje również mleko, ten wzorzec zasługuje na uwagę. Górnictwo reguł asocjacyjnych działa jak skrupulatny bibliotekarz przeglądający każdy paragon, liczący, jak często kombinacje elementów pojawiają się razem, i wyszukujący kombinacje, które przekraczają minimalną częstotliwość. Po znalezieniu częstych grup algorytm pyta: biorąc pod uwagę, że już masz te elementy, jak wiarygodnie przewiduje to następny element? Ta dwuprzejściowa logika częstotliwości, a następnie pewności jest sercem algorytmu Apriori.

Historia

Podstawowy artykuł Agrawala, Imielińskiego i Swami (1993) zdefiniował problem reguł asocjacyjnych w kontekście danych transakcyjnych supermarketów. Artykuł Agrawala i Srikanta z 1994 roku z VLDB wprowadził algorytm Apriori i jego efektywną strategię przycinania, czyniąc górnictwo na dużą skalę praktycznym. Kolejne prace wyprodukowały FP-Growth (Han i in., 2000), który całkowicie unika generowania kandydatów, oraz ECLAT, który wydobywa dane w formacie pionowym — ustanawiając bogatą rodzinę algorytmów, obecnie centralną dla programów nauczania górnictwa danych.

Kiedy stosować

Górnictwo reguł asocjacyjnych nadaje się do dużych zbiorów danych transakcyjnych, gdzie celem jest odkrycie wzorców współwystępowania bez predefiniowanej zmiennej docelowej. Zakłada, że elementy są binarne (obecne/nieobecne) na transakcję. Jest odpowiednie do analizy koszyka zakupów, systemów rekomendacji, analizy strumieni kliknięć w sieci oraz odkrywania współdiagnoz medycznych. Nie nadaje się do danych ciągłych lub porządkowych, chyba że są wstępnie zdyskretyzowane, do zbiorów danych o bardzo wysokiej wymiarowości (wykładnicza przestrzeń kandydatów) lub gdy wymagane jest wnioskowanie przyczynowe, a nie asocjacyjne. Alternatywy obejmują FP-Growth dla szybszego wyliczania częstych zbiorów elementów i górnictwo sekwencyjne, gdy ważna jest kolejność czasowa.

Ograniczenia i uwagi

  • Wykładnicza przestrzeń kandydatów: liczba reguł rośnie kombinatorycznie wraz z liczbą różnych elementów.
  • Ramy wsparcia-pewności mogą prowadzić do mylących reguł, gdy bazowe wskaźniki elementów znacznie się różnią (wymagana jest korekta liftu).
  • Model transakcji binarnej wymaga dyskretyzacji zmiennych ciągłych, wprowadzając utratę informacji.
  • Wysokie minimalne progi wsparcia pomijają rzadkie, ale cenne reguły; niskie progi generują tysiące trywialnych reguł.

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

Mocne strony

  • W pełni nienadzorowane: nie są potrzebne dane oznaczone ani predefiniowany cel.
  • Interpretowalny wynik: reguły są czytelnymi dla człowieka stwierdzeniami typu jeśli-to z kwantyfikowanym wsparciem i pewnością.
  • Skalowalne dzięki przycinaniu Apriori; wariant FP-Growth całkowicie eliminuje powtarzające się skanowania bazy danych.
  • Niezależne od dziedziny: stosowane w handlu detalicznym, opiece zdrowotnej, analizie sieci i bioinformatyce.

Zastosowania

  • Handel detaliczny: rekomendacje dotyczące rozmieszczenia produktów i sprzedaży krzyżowej na podstawie dzienników transakcji z punktów sprzedaży.
  • Opieka zdrowotna: analiza współwystępowania diagnoz, procedur lub leków w elektronicznej dokumentacji medycznej.
  • Analiza sieci: odkrywanie wzorców strumieni kliknięć w celu rekomendacji stron i optymalizacji nawigacji.
  • Bioinformatyka: identyfikacja zestawów współekspresjonowanych genów i motywów interakcji białek.
  • Cyberbezpieczeństwo: wykrywanie skorelowanych zdarzeń sieciowych wskazujących na wzorce intruzji.

Jak to działa

Jak to działa

1

Algorytm skanuje bazę danych transakcyjnych D, aby policzyć, jak często pojawia się każdy zbiór elementów X. Zbiór elementów jest uznawany za częsty — i umieszczany w L_k — tylko wtedy, gdy jego wsparcie (frakcja transakcji go zawierających) osiąga lub przekracza zdefiniowany przez użytkownika minimalny próg wsparcia σ_min. Proces rozpoczyna się od pojedynczych elementów (k=1) i iteracyjnie buduje większe zbiory kandydatów.

Wzór
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

Własność anty-monotoniczności wsparcia stwierdza, że każdy podzbiór częstego zbioru elementów musi być sam w sobie częsty. Apriori wykorzystuje to, odrzucając każdy kandydat na zbiór k-elementowy, którego (k-1)-podzbiory nie znajdują się wszystkie w zweryfikowanym zbiorze częstych L_{k-1}. To dramatycznie redukuje przestrzeń poszukiwań, unikając kosztownych skanowań bazy danych dla zbiorów elementów, które z natury nie mogą być częste.

Wzór
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

Z każdego częstego zbioru elementów X ∪ Y, algorytm generuje reguły X ⇒ Y, gdzie X i Y są rozłącznymi podzbiorami. Reguła jest zachowywana tylko wtedy, gdy jej pewność — prawdopodobieństwo warunkowe Y przy danym X, obliczane jako wsparcie(X ∪ Y) / wsparcie(X) — osiąga lub przekracza minimalny próg pewności γ_min. Ten krok przekształca surowe współwystępowanie w kierunkowe stwierdzenia predykcyjne.

Wzór
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

Zachowane reguły są rangowane i filtrowane według liftu, który mierzy, jak znacznie bardziej prawdopodobne jest pojawienie się Y z X niż przypadkowo. Lift > 1 wskazuje na pozytywną korelację wykraczającą poza niezależność; lift = 1 wskazuje na niezależność; lift < 1 wskazuje na negatywną korelację. Dodatkowe miary interesowności, takie jak przekonanie (conviction) i dźwignia (leverage), mogą dalej udoskonalać zbiór reguł do praktycznego wdrożenia.

Wzór
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}

Częste pułapki

  • Ustawienie zbyt niskiego minimalnego wsparcia zalewa analityka fałszywymi regułami; wybór progu wymaga wiedzy dziedzinowej lub walidacji krzyżowej.
  • Mylenie związku statystycznego z przyczynowością: wysoki lift nie implikuje, że X powoduje Y.
  • Ignorowanie rozkładu częstotliwości elementów: powszechne elementy dominują w regułach i wypierają znaczące rzadkie powiązania elementów.
  • Traktowanie samej pewności jako metryki jakości; reguła o wysokiej pewności, ale niskim lifcie, może działać nie lepiej niż przypadek.

Najczęściej zadawane pytania

Jaka jest różnica między wsparciem, pewnością i liftem?

Wsparcie mierzy, jak często zbiór elementów pojawia się w całym zbiorze danych. Pewność mierzy prawdopodobieństwo warunkowe następnika przy danym poprzedniku. Lift normalizuje pewność przez marginalną częstotliwość następnika, ujawniając, czy współwystępowanie przekracza to, co można by oczekiwać przy niezależności. Wszystkie trzy metryki są potrzebne razem do rzetelnej oceny reguł.

Jak algorytm Apriori redukuje koszt obliczeniowy?

Apriori wykorzystuje własność anty-monotoniczności: jeśli zbiór elementów jest rzadki, wszystkie jego nadzbiory również muszą być rzadkie. Odrzucając każdego kandydata, którego podzbiory nie zostały w pełni zweryfikowane jako częste, algorytm przycina ogromne części przestrzeni poszukiwań przed zliczaniem, drastycznie redukując liczbę przejść przez bazę danych wymaganą w porównaniu do wyliczania metodą brute-force.

Kiedy powinienem użyć FP-Growth zamiast Apriori?

FP-Growth jest preferowany, gdy zbiór danych jest duży, a minimalny próg wsparcia jest niski, ponieważ kompresuje bazę danych transakcyjnych do zwartej struktury drzewa FP i wydobywa wzorce bezpośrednio, bez generowania jawnych kandydatów. Eliminuje to powtarzające się pełne skanowania bazy danych, czyniąc go znacznie szybszym niż Apriori na gęstych zbiorach danych z wieloma częstymi zbiorami elementów.

Pokrewne metody

Źródła

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    Otwórz odnośnik do publikacji
    Skopiowano.