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
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
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.
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}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
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}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
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 DOISkopiowano.Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.
ISBN: 978-0-13-312890-1Skopiowano.