Algorytm Apriori
- Autor metody
- Agrawal, R. & Srikant, R.
- Rok
- 1994
- Typ
- Frequent itemset and association rule mining algorithm
- Rodzina
- Machine learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm Apriori, wprowadzony przez Agrawala i Srikanta w 1994 roku, jest fundamentalną metodą odkrywania częstych zbiorów elementów i reguł asocjacyjnych w bazach danych transakcyjnych.
Wykorzystuje on przeszukiwanie wszerz, poziom po poziomie, kierując się anty-monotoniczną własnością wsparcia (support), aby efektywnie wyliczyć wszystkie kombinacje elementów, które współwystępują powyżej ustalonego przez użytkownika progu minimalnego, a następnie wydobywa zrozumiałe reguły typu „jeśli-to” z tych wzorców.
Intuicja stojąca za metodą
Rozważmy bazę danych paragonów supermarketowych. Wgląd Apriori polega na własności anty-monotonicznej: jeśli para produktów jest rzadko kupowana razem, żaden większy zbiór zawierający tę parę nie może być częsty. Pozwala to algorytmowi przycinać wykładniczo dużą przestrzeń poszukiwań możliwych kombinacji elementów poprzez budowanie kandydatów poziom po poziomie — zaczynając od pojedynczych elementów, następnie par, potem trójek — i odrzucając każdego kandydata, którego podzbiory są już znane jako nieczęste, zanim jeszcze zostanie on zliczony w danych.
Historia
Rakesh Agrawal i Ramakrishnan Srikant wprowadzili algorytm Apriori na konferencji VLDB w 1994 roku, opierając się na sformułowaniu problemu miningu reguł asocjacyjnych przez Agrawala i in. z 1993 roku. Nazwa odzwierciedla jego kluczową ideę: wykorzystanie wcześniejszej wiedzy o częstych (k)-zbiorach elementów do przycinania kandydatów na poziomie k+1. Stał się on kanonicznym punktem odniesienia, względem którego mierzone są wszystkie kolejne algorytmy do znajdowania częstych zbiorów elementów — w tym FP-Growth (2000) i Eclat — i pozostaje standardowym rozdziałem w podręcznikach do data mining i uczenia maszynowego.
Kiedy stosować
Używaj Apriori, gdy celem jest odkrycie wzorców współwystępowania lub relacji typu „jeśli-to” w danych transakcyjnych lub danych o obecności elementów binarnych — analiza koszyka zakupów, współwystępowanie poparcia dla pozycji w ankiecie, współwystępowanie diagnoz medycznych lub asocjacja terminów w tekście. Jest odpowiedni dla zbiorów danych o umiarkowanej wielkości, gdzie priorytetem jest przejrzystość i zrozumiałość wyników. Nie używaj Apriori, gdy baza danych transakcyjnych jest bardzo duża (miliony wierszy z szerokim katalogiem elementów), ponieważ jego powtarzające się pełne skanowanie bazy danych czyni go wolnym w porównaniu z FP-Growth; w takich przypadkach preferowany jest FP-Growth. Jest również nieodpowiedni dla ciągłych danych liczbowych bez wcześniejszej dyskretyzacji i nie modeluje kierunkowości ani przyczynowości.
Ograniczenia i uwagi
- Powtarzające się pełne skanowanie bazy danych czyni go wolnym na dużych zbiorach danych — FP-Growth jest często preferowany na dużą skalę.
- Obniżenie progu wsparcia może prowadzić do wykładniczej liczby kandydackich zbiorów elementów i reguł, utrudniając interpretację.
- Nie wychwytuje kolejności czasowej, kierunkowości ani związków przyczynowych między elementami.
- Wyniki są wrażliwe na wybór progów wsparcia i pewności, które wymagają wiedzy dziedzinowej lub systematycznego dostrajania.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Generuje w pełni zrozumiałe reguły typu „jeśli-to” z kwantyfikowanym wsparciem, pewnością i liftem.
- Własność przycinania anty-monotonicznego sprawia, że inaczej wykładnicze poszukiwania stają się wykonalne.
- Nie wymaga wcześniejszego etykietowania danych; jest całkowicie nienadzorowany.
- Parametry progowe (wsparcie, pewność) dają analitykowi bezpośrednią kontrolę nad granularnością reguł.
- Wynikowe reguły są użyteczne i mogą być komunikowane interesariuszom nietechnicznym bez zaplecza algorytmicznego.
- Fundamentalny, mocno cytowany i zaimplementowany w praktycznie każdej głównej bibliotece do data mining.
Zastosowania
- Analiza koszyka zakupów: odkrywanie, które produkty są często kupowane razem, aby kierować układem półek i promocjami.
- Informatyka medyczna: identyfikacja współwystępujących objawów, diagnoz lub recept w kartach pacjentów.
- Mining użycia sieci: znajdowanie, które strony lub funkcje użytkownicy zazwyczaj odwiedzają lub aktywują razem.
- Analiza ankiet i kwestionariuszy: wykrywanie, które pozycje lub odpowiedzi w skali są systematycznie współpopierane.
- Uruchamianie systemów rekomendacyjnych: generowanie kandydackich asocjacji elementów przed wdrożeniem filtrowania kolaboracyjnego.
- Wykrywanie oszustw: ujawnianie nietypowych wzorców współwystępowania w logach transakcji, które odbiegają od normalnych koszyków.
Jak to działa
Jak to działa
Analityk wybiera dwa progi przed uruchomieniem algorytmu: minimalne wsparcie (support) (odsetek transakcji, które muszą zawierać dany zbiór elementów, aby został uznany za częsty) oraz minimalną pewność (confidence) (wymagane prawdopodobieństwo warunkowe, aby reguła typu „jeśli-to” została zachowana). Te dwie wartości kontrolują objętość i specyfikę wyników i powinny być kalibrowane za pomocą wiedzy dziedzinowej lub przebiegów eksploracyjnych.
Algorytm wykonuje jedno pełne skanowanie bazy danych transakcyjnych, aby zliczyć, jak często pojawia się każdy pojedynczy element. Zachowywane są tylko te elementy, których wsparcie spełnia lub przekracza minimalny próg wsparcia; pozostałe są odrzucane. Ten zbiór częstych pojedynczych elementów tworzy pierwszy poziom kandydatów.
Wzór
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}Częste zbiory elementów znalezione na poziomie k są łączone parami, tworząc kandydackie zbiory elementów o rozmiarze k+1. Łączone są tylko pary, które dzielą te same pierwsze k-1 elementów, co jest regułą utrzymującą zbiór kandydatów w zwartym stanie. Nowe skanowanie bazy danych zlicza wsparcie każdego kandydata.
Przed zliczeniem każdy kandydat o rozmiarze k+1 jest sprawdzany pod kątem wszystkich jego (k)-podzbiorów. Jeśli jakikolwiek podzbiór nie był częsty na poprzednim poziomie, kandydat jest natychmiast przycinany bez odczytywania danych, wykorzystując własność anty-monotoniczną do zmniejszenia obliczeń. Ocalałe z tego kroku przycinania tworzą następny poziom częstych zbiorów elementów.
Z każdego częstego zbioru elementów o rozmiarze dwa lub więcej, generowane są wszystkie możliwe reguły typu „jeśli-to” poprzez podział elementów na poprzednik (antecedent) i następnik (consequent). Każda reguła jest oceniana pod kątem pewności (confidence) — odsetka transakcji z poprzednikiem, które zawierają również następnik. Reguły poniżej minimalnej pewności są odrzucane.
Wzór
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}Ocalałe reguły są rangowane według liftu, który porównuje zaobserwowaną pewność z bazowym prawdopodobieństwem wystąpienia następnika. Lift powyżej 1 sygnalizuje, że poprzednik i następnik współwystępują częściej niż przypadkowo; lift bliski 1 wskazuje na niezależność; lift poniżej 1 wskazuje na negatywną asocjację. Reguły o najwyższym lifcie są najbardziej użytecznymi odkryciami.
Wzór
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}Częste pułapki
- Ustawienie minimalnego wsparcia zbyt nisko i utonięcie w tysiącach reguł niskiej jakości bez filtrowania według liftu.
- Interpretowanie wysokiej pewności jako przyczynowości, a nie współwystępowania — reguła o wysokiej pewności, ale lifcie bliskim 1, jest trywialna.
- Stosowanie Apriori do cech ciągłych bez wcześniejszej dyskretyzacji, co zwiększa przestrzeń elementów i pogarsza wyniki.
- Raportowanie reguł bez sprawdzenia, czy wielkości próbek zbiorów elementów są wystarczająco duże, aby ufać oszacowaniom wsparcia.
- Zaniedbanie usuwania nieinformacyjnych reguł (np. reguł obejmujących powszechnie kupowane przedmioty, takie jak karta lojalnościowa sklepu).
Najczęściej zadawane pytania
Jaka jest różnica między wsparciem (support), pewnością (confidence) i liftem?
Wsparcie to odsetek wszystkich transakcji zawierających dany zbiór elementów — mierzy jego powszechność. Pewność to prawdopodobieństwo warunkowe, że następnik wystąpi, pod warunkiem wystąpienia poprzednika — mierzy niezawodność reguły. Lift to stosunek zaobserwowanej pewności do bazowego prawdopodobieństwa wystąpienia następnika; lift powyżej 1 pokazuje rzeczywistą pozytywną asocjację, a nie zbieg okoliczności wynikający z popularności elementu.
Kiedy powinienem wybrać FP-Growth zamiast Apriori?
FP-Growth kompresuje bazę danych do struktury drzewa i przeszukuje ją bez powtarzających się pełnych skanowań, co czyni go znacznie szybszym na dużych zbiorach danych lub gdy minimalne wsparcie jest niskie. Apriori jest łatwiejszy do zrozumienia i zaimplementowania i działa dobrze na małych i średnich zbiorach danych, gdzie czas wykonania nie jest wąskim gardłem.
Jak wybrać minimalne wsparcie i pewność?
Nie ma uniwersalnej zasady. Powszechną praktyką jest uruchamianie algorytmu przy kilku poziomach wsparcia, rysowanie liczby częstych zbiorów elementów w funkcji wsparcia i wybieranie wartości w punkcie załamania krzywej. Pewność jest następnie ustawiana w zależności od pytania biznesowego lub badawczego — wyższa pewność dla reguł krytycznych dla misji, niższa dla odkryć eksploracyjnych. Zawsze weryfikuj najlepsze reguły pod kątem wiedzy dziedzinowej.
Czy Apriori może obsługiwać dane liczbowe lub ciągłe?
Apriori wymaga danych binarnych o obecności elementów. Zmienne ciągłe muszą zostać zdyskretyzowane na przedziały (np. wiek na niski/średni/wysoki) przed zakodowaniem jako elementy. Słaba dyskretyzacja może poważnie zniekształcić odkryte reguły, dlatego strategia podziału na przedziały zasługuje na staranne przemyślenie.
Czy Apriori implikuje przyczynowość między elementami?
Nie. Reguły asocjacyjne wychwytują współwystępowanie, a nie przyczynowość ani kierunkowość. Reguła „chleb → masło” oznacza, że często pojawiają się one w tym samym koszyku; nie oznacza to, że kupno chleba powoduje kupno masła, ani że związek jest asymetryczny w jakimkolwiek sensie przyczynowym.
Pokrewne metody
Źródła
Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.
Otwórz odnośnik do publikacjiSkopiowano.Apriori algorithm. Wikipedia.
Otwórz odnośnik do publikacjiSkopiowano.