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

Reguły asocjacyjne

Autor metody
Agrawal, R., Imielinski, T., & Swami, A.
Rok
1993
Typ
Unsupervised pattern discovery
Rodzina
Machine learning

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

Rozmiar czcionki

Do czego służy?

Uczenie się reguł asocjacyjnych jest techniką nienadzorowaną, która odkrywa wzorce współwystępowania – implikacje typu „jeśli X, to Y” – w dużych zbiorach danych transakcyjnych.

Pierwotnie sformalizowane przez Agrawala, Imielińskiego i Swami (1993) na potrzeby analizy koszyków sklepowych, obecnie jest szeroko stosowane w rekomendacjach w handlu elektronicznym, informatyce medycznej, bioinformatyce i badaniach behawioralnych.

Intuicja stojąca za metodą

Wyobraźmy sobie skanowanie milionów paragonów sklepowych i zadawanie pytania: jakie kombinacje produktów mają tendencję do pojawiania się razem? Wydobywanie reguł asocjacyjnych odpowiada na to pytanie, zliczając, jak często zestawy elementów współwystępują (wsparcie), jak wiarygodnie jeden element przewiduje drugi (pewność) i czy współwystępowanie jest silniejsze niż przypadek (wzmocnienie). Reguły typu „pieluchy → piwo” o wysokiej pewności i wzmocnieniu ujawniają rzeczywiste wzorce zachowań, a nie zbiegi okoliczności, co czyni je potężnym narzędziem eksploracyjnym, gdy nie ma zmiennej wynikowej do nadzorowania.

Historia

Uczenie się reguł asocjacyjnych zostało formalnie wprowadzone przez Agrawala, Imielińskiego i Swami na konferencji ACM SIGMOD w 1993 roku, motywowane wyzwaniem wydobywania danych z baz danych transakcji supermarketów. Ich późniejszy artykuł z 1994 roku wprowadził algorytm Apriori, zapewniając wydajną metodę obliczeniową. Dziedzina szybko rozwijała się w latach 90. i 2000., a FP-growth (Han i in., 2000) później zaoferował dalsze usprawnienia prędkości. Reguły asocjacyjne pozostają fundamentalną techniką w programach nauczania data mining i są rutynowo stosowane w analizie sprzedaży detalicznej, opieki zdrowotnej i analizie internetowej.

Kiedy stosować

Stosuj reguły asocjacyjne, gdy Twoim celem jest eksploracyjne odkrywanie wzorców współwystępowania w danych transakcyjnych lub zakodowanych binarnie – koszyki zakupowe, współwystępowanie diagnoz klinicznych, strumienie kliknięć, zestawy pytań ankietowych lub profile ekspresji genów. Metoda jest nienadzorowana i nie wymaga etykiety wyniku, co czyni ją idealną do generowania hipotez. Nie używaj jej, gdy masz zdefiniowaną zmienną wynikową i chcesz ją przewidzieć (zamiast tego użyj klasyfikacji lub regresji nadzorowanej); gdy Twoje dane są ciągłe i nie zostały sensownie zdyskretyzowane; gdy wielkość próby jest mała (rzadkie zestawy elementów dają niewiarygodne oszacowania wsparcia); lub gdy wynikowe reguły będą mylone z wnioskowaniem przyczynowym – reguły asocjacyjne są czysto korelacyjne.

Ograniczenia i uwagi

  • Wymaga, aby dane były transakcyjne lub zdyskretyzowane binarne; zmienne ciągłe wymagają grupowania, co wprowadza arbitralne wybory.
  • Liczba reguł może być ogromna; obowiązkowe jest filtrowanie i szeregowanie post-hoc według wzmocnienia lub innych miar interesowności.
  • Należy ustawić minimalne wsparcie i pewność przez badacza; wyniki są wrażliwe na te wybory.
  • Reguły są czysto korelacyjne – twierdzenia o przyczynowości wymagają dodatkowego projektu badania (np. eksperymentu lub quasi-eksperymentu).
  • Obliczeniowo kosztowne na zbiorach danych z bardzo dużymi zestawami elementów, nawet z przycinaniem.

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

Mocne strony

  • W pełni nienadzorowana: nie wymaga etykietowanej zmiennej wynikowej, umożliwiając otwarte odkrywanie wzorców.
  • Interpretowalny wynik: każda reguła to czytelne dla człowieka stwierdzenie JEŚLI–WTEDY z kwantyfikowanym wsparciem, pewnością i wzmocnieniem.
  • Skalowalność do bardzo dużych baz danych transakcyjnych dzięki heurystykom przycinania (Apriori, FP-growth).
  • Zastosowanie w różnych dziedzinach, gdzie współwystępowanie w zapisach zakodowanych binarnie ma znaczenie.
  • Generowanie hipotez: uwypukla nieoczekiwane współwystępowania, które mogą kierować dalszą analizą potwierdzającą.

Zastosowania

  • Analiza koszyków sklepowych: identyfikacja produktów często kupowanych razem w celu ukierunkowania rozmieszczenia produktów i promocji.
  • Rekomendacje w handlu elektronicznym: generowanie sugestii typu „klienci, którzy kupili X, kupili również Y”.
  • Odkrywanie współwystępowania chorób: znajdowanie zestawów diagnoz, leków lub objawów, które współwystępują w dokumentacji pacjentów.
  • Bioinformatyka: wykrywanie współwystępujących genów lub współwystępujących wariantów genetycznych w próbkach.
  • Wydobywanie danych z użytkowania sieci: odkrywanie wspólnych wzorców strumieni kliknięć i sekwencji nawigacji na stronach internetowych.
  • Badania ankietowe i behawioralne: znajdowanie zestawów pytań ankietowych lub zachowań, które współwystępują u respondentów.

Jak to działa

Jak to działa

1

Zbiór danych jest reprezentowany jako binarna macierz transakcji: każdy wiersz to transakcja, a każda kolumna to możliwy element, gdzie 1 oznacza obecność elementu. Ta rzadka, szeroka reprezentacja jest podstawowym formatem wejściowym; elementy niebinarne lub ilościowe muszą zostać zdyskretyzowane przed tym krokiem.

2

Identyfikowane są wszystkie kombinacje elementów (zestawy elementów), których częstotliwość w bazie danych transakcyjnych spełnia ustawiony przez użytkownika minimalny próg wsparcia. Zasada Apriori – każdy podzbiór częstego zestawu elementów jest również częsty – drastycznie przycina przestrzeń poszukiwań kombinatorycznych, czyniąc enumerację wykonalną nawet przy dużych katalogach.

Wzór
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}
3

Dla każdego częstego zestawu elementów generowane są wszystkie możliwe podziały na poprzednik–następnik (X → Y, gdzie X i Y są rozłącznymi, niepustymi podzbiorami) jako kandydaci na reguły. Liczba kandydatów może być duża, dlatego kolejny krok filtrowania jest kluczowy.

Wzór
X \Rightarrow Y, \quad X \cap Y = \emptyset
4

Każda kandydacka reguła jest oceniana pod względem jej pewności: warunkowego prawdopodobieństwa, że Y jest obecne, gdy X jest obecne. Zachowywane są tylko reguły przekraczające minimalny próg pewności, filtrując poprzedniki, które przewidują następnik tylko nieznacznie lepiej niż podstawowa częstość.

Wzór
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}
5

Zachowane reguły są szeregowane według wzmocnienia, czyli stosunku zaobserwowanego wspólnego wsparcia do wsparcia oczekiwanego przy założeniu niezależności. Wzmocnienie większe od 1 sygnalizuje rzeczywistą pozytywną asocjację; wzmocnienie bliskie 1 oznacza, że elementy współwystępują nie częściej niż przypadkiem; wzmocnienie poniżej 1 wskazuje na negatywną asocjację. Sortowanie według wzmocnienia uwypukla najbardziej użyteczne i nietrywialne reguły.

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

Częste pułapki

  • Ustawienie zbyt niskiego minimalnego wsparcia, co zalewa wynik fałszywymi regułami o niskiej częstotliwości, które nie generalizują.
  • Ignorowanie wzmocnienia i raportowanie wszystkich reguł o wysokiej pewności, z których wiele może po prostu odzwierciedlać elementy o wysokiej podstawowej częstości.
  • Traktowanie odkrytych reguł jako przyczynowych bez dalszej walidacji (np. mylenie „piwo i pieluchy współwystępują” z „piwo powoduje zakup pieluch”).
  • Stosowanie reguł asocjacyjnych do danych ciągłych bez zasadniczej dyskretyzacji, co prowadzi do reguł zależnych wyłącznie od arbitralnych granic przedziałów.
  • Przeoczenie kwestii wielokrotnych porównań, gdy generowane i selektywnie podkreślane są tysiące reguł.

Najczęściej zadawane pytania

Jak wybrać minimalne progi wsparcia i pewności?

Nie ma uniwersalnej zasady. Zacznij od zbadania rozkładu wsparcia dla poszczególnych elementów, a następnie ustaw minimalne wsparcie na tyle nisko, aby objąć interesujące wzorce, ale na tyle wysoko, aby zapewnić, że zestawy elementów pojawią się w co najmniej znaczącej bezwzględnej liczbie transakcji. Minimalna pewność w zakresie 0,6–0,8 jest powszechnym punktem wyjścia, ale wiedza dziedzinowa i szeregowanie oparte na wzmocnieniu powinny kierować ostatecznym wyborem.

Jaka jest różnica między pewnością a wzmocnieniem i którym z nich należy nadać priorytet?

Pewność mierzy, jak często Y następuje po X w transakcjach zawierających X, ale ignoruje podstawową częstość Y. Wzmocnienie koryguje to, dzieląc pewność przez marginalne wsparcie Y. Reguła o wysokiej pewności, ale ze wzmocnieniem bliskim 1, dodaje niewiele informacji poza wiedzą, że Y jest powszechne. Priorytetem powinno być wzmocnienie przy filtrowaniu dla rzeczywiście nietrywialnych asocjacji.

Czy reguły asocjacyjne mogą być używane do przewidywania?

Są one przede wszystkim opisowe i eksploracyjne, a nie predykcyjne. Chociaż możliwe jest użycie reguł ze stałym następnikiem (pojedynczym elementem docelowym) do klasyfikacji – technika zwana klasyfikacją asocjacyjną – standardowe uczenie się reguł asocjacyjnych nie optymalizuje funkcji straty predykcyjnej i nie powinno zastępować modeli nadzorowanych, gdy dostępny jest etykietowany wynik.

Mój zbiór danych zawiera zmienne ciągłe. Czy nadal mogę używać reguł asocjacyjnych?

Tylko po dyskretyzacji. Zmienne ciągłe muszą zostać pogrupowane w przedziały kategoryczne (np. grupy wiekowe, kwantyle) przed zakodowaniem jako elementy binarne. Wybór granic przedziałów znacząco wpływa na to, które reguły się pojawią, dlatego decyzje dotyczące dyskretyzacji powinny być motywowane teoretycznie i przejrzysto raportowane.

Czym reguły asocjacyjne różnią się od analizy korelacji?

Korelacja (np. r Pearsona) mierzy liniowy związek między dwiema zmiennymi ciągłymi. Reguły asocjacyjne odkrywają wzorce współwystępowania między zestawami elementów binarnych – dowolnej wielkości kombinacji – w danych transakcyjnych. Metryki (wsparcie, pewność, wzmocnienie) opierają się na częstotliwości, a nie na momentach, a wynik to zestaw czytelnych dla człowieka reguł JEŚLI–WTEDY, a nie pojedynczy współczynnik liczbowy.

Pokrewne metody

Źródła

  1. Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.

    ISBN: 978-0-13-312890-1
    Skopiowano.