Algorytm aprioryczny

Apriori to algorytm do częstego eksplorowania zestawów elementów i uczenia się reguł asocjacyjnych w relacyjnych bazach danych . Polega na identyfikowaniu częstych pojedynczych elementów w bazie danych i rozszerzaniu ich na coraz większe zestawy elementów, o ile te zestawy elementów pojawiają się w bazie danych wystarczająco często. Częste zestawy pozycji określone przez Apriori mogą być wykorzystane do określenia reguł asocjacji , które podkreślają ogólne trendy w bazie danych : ma to zastosowanie w dziedzinach takich jak analiza koszyka rynkowego .

Przegląd

Algorytm Apriori został zaproponowany przez Agrawala i Srikanta w 1994 roku. Apriori jest przeznaczony do operowania na bazach danych zawierających transakcje (np. kolekcje przedmiotów kupionych przez klientów, szczegóły dotyczące odwiedzania strony internetowej lub adresy IP ). Inne algorytmy są przeznaczone do znajdowania reguł asocjacyjnych w danych, które nie zawierają transakcji ( Winepi i Minepi) lub nie mają znaczników czasu (sekwencjonowanie DNA). Każda transakcja jest postrzegana jako zestaw pozycji ( zestaw pozycji ). Biorąc pod uwagę próg do ${\ displaystyle C$ $podzbiorami$ co najmniej transakcji w bazie danych.

Apriori stosuje podejście „oddolne”, w którym częste podzbiory są rozszerzane po jednym elemencie na raz (krok znany jako generowanie kandydatów ), a grupy kandydatów są testowane pod kątem danych. Algorytm kończy działanie, gdy nie zostaną znalezione dalsze udane rozszerzenia.

Apriori wykorzystuje przeszukiwanie wszerz i strukturę drzewa Hash do efektywnego liczenia zestawów elementów kandydujących. Generuje kandydujące zestawy pozycji o długości $displaystyle$ zestawów pozycji o długości $k-1}$ . Następnie przycina kandydatów, którzy mają rzadki wzór podrzędny. Zgodnie z lematem domknięcia w dół, zbiór kandydujący zawiera wszystkie częste zestawy przedmiotów o długości ${\ displaystyle k} .$ Następnie skanuje bazę danych transakcji w celu określenia częstych zestawów pozycji wśród kandydatów.

Poniżej podano pseudokod algorytmu dla bazy danych transakcji $displaystyle$ progu wsparcia wynoszącego $\ varepsilon}$ . Stosowana jest zwykła notacja teorii mnogości, chociaż należy zauważyć, $że$ to multiset . $\ displaystyle C_ {k}}$ jest kandydatem ustawionym na poziom ${\ displaystyle k}$ . Zakłada się, że na każdym kroku algorytm generuje zestawy kandydujące z dużych zestawów pozycji z poprzedniego poziomu, uwzględniając lemat o zamknięciu w dół. $\ Displaystyle \ operatorname {liczba} [c]} uzyskuje$ $dostęp$ do pola struktury danych reprezentującej zbiór kandydujący który początkowo zakłada się, że wynosi zero. Poniżej pominięto wiele szczegółów, zwykle najważniejszą częścią implementacji jest struktura danych używana do przechowywania zestawów kandydujących i zliczania ich częstotliwości.

  Apriori  (T, ε) L ₁ ← {duża 1 - zbiory pozycji} k ← 2  podczas gdy  L _k−1 nie jest  pusta C _k ← Apriori_gen(L _k−1 , k)  dla  transakcji t  w  T D _t ← {c w C _k : c ⊆ t}  dla  kandydatów c  w  D _t liczba [c] ← liczba [c] + 1 L _k ← {c w C _k : liczba [c] ≥ ε} k ← k + 1  return  Suma(L _k )  Apriori_gen  (L, k) wynik ← lista()  dla wszystkich  p ∈ L, q ∈ L  gdzie  p ₁ = q ₁ , p ₂ = q ₂ , ..., p _k-2 = q _{k -2} i p _k-1 < q _k-1 do = p ∪ {q _k-1 }  jeśli  u ∈ L  dla wszystkich  u ⊆ c  gdzie  |u| = k-1 wynik.add(c)   zwróć  wynik

Przykłady

Przykład 1

Rozważ następującą bazę danych, w której każdy wiersz jest transakcją, a każda komórka jest pojedynczą pozycją transakcji:

alfa	beta	epsilon
alfa	beta	teta
alfa	beta	epsilon
alfa	beta	teta

Reguły powiązania, które można określić na podstawie tej bazy danych, są następujące:

100% zestawów z alfa zawiera również beta
50% zestawów z alfa, beta ma również epsilon
50% zestawów z alfa, beta ma również theta

możemy to również zilustrować różnymi przykładami.

Przykład 2

Załóżmy, że duży supermarket śledzi dane sprzedaży według jednostek magazynowych (SKU) dla każdej pozycji: każda pozycja, taka jak „masło” lub „chleb”, jest identyfikowana przez numeryczną jednostkę SKU. Supermarket ma bazę danych transakcji, w której każda transakcja jest zbiorem jednostek SKU, które zostały kupione razem.

Niech baza danych transakcji składa się z następujących zestawów pozycji:

Zestawy przedmiotów
{1,2,3,4}
{1,2,4}
{1,2}
{2,3,4
} {2,3}
{3,4}
{2,4}

Użyjemy Apriori do określenia częstych zestawów pozycji w tej bazie danych. W tym celu powiemy, że zestaw pozycji jest częsty, jeśli występuje w co najmniej 3 transakcjach w bazie danych: wartość 3 to próg wsparcia .

Pierwszym krokiem Apriori jest policzenie liczby wystąpień, zwanych podporami, każdego elementu składowego z osobna. Skanując bazę danych po raz pierwszy, uzyskujemy następujący wynik

Przedmiot	Wsparcie
{1}	3
{2}	6
{3}	4
{4}	5

Wszystkie zestawy przedmiotów o rozmiarze 1 mają wsparcie co najmniej 3, więc wszystkie są częste.

Kolejnym krokiem jest wygenerowanie listy wszystkich par częstych pozycji.

Na przykład, w odniesieniu do pary {1,2}: pierwsza tabela przykładu 2 pokazuje pozycje 1 i 2 występujące razem w trzech zestawach pozycji; dlatego mówimy, że element {1,2} ma poparcie trzech.

Przedmiot	Wsparcie
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

Pary {1,2}, {2,3}, {2,4} i {3,4} spełniają lub przekraczają minimalne wsparcie 3, więc są częste. Pary {1,3} i {1,4} nie są. Teraz, ponieważ {1,3} i {1,4} nie są częste, żaden większy zbiór zawierający {1,3} lub {1,4} nie może być częsty. W ten sposób możemy przycinać zestawy: będziemy teraz szukać częstych trójek w bazie danych, ale możemy już wykluczyć wszystkie trójki, które zawierają jedną z tych dwóch par:

Przedmiot	Wsparcie
{2,3,4}	2

w przykładzie nie ma częstych trojaczków. {2,3,4} jest poniżej minimalnego progu, a pozostałe trojaczki zostały wykluczone, ponieważ były superzbiorami par, które już znajdowały się poniżej progu.

W ten sposób określiliśmy częste zestawy elementów w bazie danych i zilustrowaliśmy, jak niektóre elementy nie zostały policzone, ponieważ jeden z ich podzbiorów był już poniżej progu.

Ograniczenia

Apriori, choć ma znaczenie historyczne, cierpi z powodu wielu nieefektywności lub kompromisów, które zrodziły inne algorytmy. Generowanie kandydatów generuje dużą liczbę podzbiorów (algorytm próbuje załadować zbiór kandydatów z jak największą liczbą podzbiorów przed każdym skanowaniem bazy danych). Eksploracja podzbioru od dołu do góry (zasadniczo przechodzenie wszerz siatki podzbioru) znajduje dowolny maksymalny podzbiór S dopiero po wszystkim ${\ Displaystyle 2 ^ {| S |} -1}$ jego właściwych podzbiorów.

Algorytm skanuje bazę danych zbyt wiele razy, co zmniejsza ogólną wydajność. Z tego powodu algorytm zakłada, że baza danych jest na stałe w pamięci.

Również złożoność czasowa i przestrzenna tego algorytmu jest bardzo wysoka: ${\ Displaystyle O \ lewo (2 ^ {| D|} \ prawo)}$ , a więc wykładniczy, gdzie ${\ displaystyle | D |}$ to pozioma szerokość (całkowita liczba elementów) obecna w bazie danych.

Późniejsze algorytmy, takie jak Max-Miner, próbują zidentyfikować maksymalne częste zestawy elementów bez wyliczania ich podzbiorów i wykonują „skoki” w przestrzeni wyszukiwania zamiast podejścia czysto oddolnego.

Linki zewnętrzne

ARtool , aplikacja do eksploracji reguł asocjacji GPL Java z graficznym interfejsem użytkownika, oferująca implementacje wielu algorytmów do wykrywania częstych wzorców i wydobywania reguł asocjacji (w tym Apriori)
SPMF oferuje otwarte implementacje Java Apriori i kilka odmian, takich jak AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID i inne bardziej wydajne algorytmy, takie jak FPGrowth i LCM.
Christian Borgelt zapewnia implementacje C dla Apriori i wielu innych algorytmów eksploracji wzorców (Eclat, FPGrowth itp.). Kod jest rozpowszechniany jako wolne oprogramowanie na licencji MIT .
Reguły pakietu R zawierają Apriori i Eclat oraz infrastrukturę do reprezentowania, manipulowania i analizowania danych i wzorców transakcji .
Efficient-Apriori to pakiet Pythona z implementacją algorytmu, jak przedstawiono w oryginalnym artykule.