🧺 Analizator koszyka zakupowego — algorytm Apriori na żywo

Apriori to klasyczny algorytm (Agrawal i Srikant, 1994) do wydobywania częstych zbiorów produktów i reguł asocjacyjnych z danych transakcyjnych, takich jak koszyki zakupowe. Buduje częste zbiory poziom po poziomie: najpierw licząc pojedyncze produkty, potem pary, potem trójki i tak dalej, odrzucając na każdym poziomie wszystko poniżej progu minimalnego wsparcia, zanim zostanie to wykorzystane do budowy większych kandydatów. To odcinanie poziom po poziomie pozwala algorytmowi skalować się do dużych katalogów produktów bez konieczności jawnego wyliczania każdej możliwej kombinacji.

Wsparcie(X) to po prostu odsetek wszystkich transakcji zawierających zbiór X — miara tego, jak powszechny jest ten zbiór. Pewność(A→B) = wsparcie(A∪B) / wsparcie(A) to prawdopodobieństwo warunkowe, że koszyk zawiera B, jeśli zawiera już A. Lift(A→B) = pewność(A→B) / wsparcie(B) porównuje to prawdopodobieństwo warunkowe z bazową częstością B: lift większy niż 1 oznacza, że A czyni B bardziej prawdopodobnym niż przypadkowo, lift bliski 1 oznacza, że są one zasadniczo niezależne, a lift poniżej 1 oznacza, że A faktycznie czyni B mniej prawdopodobnym.

Apriori opiera się na właściwości domknięcia w dół: jeśli zbiór jest częsty, każdy jego podzbiór również musi być częsty, ponieważ każda transakcja zawierająca pełny zbiór zawiera też każdy jego podzbiór. Kontrapozycja tego stwierdzenia jest regułą odcinania — jeśli którykolwiek (k−1)-elementowy podzbiór kandydującego k-elementowego zbioru nie jest częsty, kandydat również nie może być częsty, więc zostaje odrzucony, zanim jeszcze zostanie przeskanowana choć jedna transakcja. Bez tego odcinania liczba kandydujących zbiorów rosłaby kombinatorycznie wraz z rozmiarem katalogu; dzięki niemu testowane są tylko kombinacje zbudowane z już częstych elementów.

Gdy znaleziony zostanie częsty zbiór o rozmiarze dwa lub większym, każdy sposób podzielenia go na niepusty poprzednik A i pozostały następnik B tworzy kandydującą regułę A→B. Jej wsparcie to po prostu wsparcie samego zbioru; jej pewność i lift są obliczane na podstawie wsparć A i B, które zostały już zmierzone podczas wydobywania. Reguły są następnie filtrowane, aby zachować tylko te spełniające próg minimalnej pewności, ponieważ częsty zbiór nie gwarantuje, że jakikolwiek konkretny jego podział jest silną regułą predykcyjną.

Minimalne wsparcie kontroluje, jak daleko sięgnie wzrost zbiorów poziom po poziomie: podnieś je, a na każdym poziomie przetrwają tylko najsilniejsze, najczęstsze kombinacje, więc wydobywanie kończy się po jednym lub dwóch poziomach; obniż je, a przetrwają rzadsze kombinacje, eksplorowane są głębsze poziomy, a zarówno czas działania, jak i sama liczba kandydujących zbiorów gwałtownie rosną. Minimalna pewność jest stosowana później, wyłącznie jako filtr reguł wyprowadzonych z odnalezionych zbiorów — podniesienie jej odrzuca słabe lub przypadkowe podziały A→B, zachowując tylko najbardziej jednostronne, predykcyjne kierunki danego zbioru.

Wydobywanie jest prawdziwe. Symulator generuje zbiór syntetycznych transakcji zakupowych z rzeczywistą strukturą współwystępowania (niektóre produkty są celowo tworzone tak, by prawdopodobnie występowały razem), a następnie liczy wystąpienia produktów i zbiorów bezpośrednio na tej liście transakcji, stosuje standardową procedurę Apriori łączenia i odcinania poziom po poziomie oraz oblicza pewność i lift na podstawie rzeczywiście zmierzonych wsparć — nic nie jest zaskryptowane ani sfałszowane. Przesunięcie suwaków ponownie uruchamia cały algorytm od zera na tych samych transakcjach.