Apriori

Czym jest algorytm Apriori?

Apriori to klasyczny algorytm analizy asocjacyjnej, który służy do identyfikacji zbiorów częstych i generowania reguł asocjacyjnych na ich podstawie. Wykorzystuje on zasadę „jeśli podzbiór jest częsty, to wszystkie jego podzbiory również muszą być częste”, co pozwala na efektywne ograniczenie liczby analizowanych kombinacji.

Kluczowe koncepcje:

  1. Zbiory częste:

    • Zbiory elementów, które występują w danych z częstością większą niż określony próg wsparcia (\(min\_support\)).

  2. Kandydaci:

    • Kombinacje elementów, które są potencjalnymi zbiorami częstymi. Są generowane w każdej iteracji algorytmu.

  3. Wsparcie (support):

    • Odsetek transakcji, w których występuje dany zbiór elementów: \[ support(X) = \frac{\text{liczba transakcji zawierających } X}{\text{całkowita liczba transakcji}} \]

  4. Ufność (confidence):

    • Prawdopodobieństwo, że wystąpienie jednego zbioru pociąga za sobą wystąpienie drugiego: \[ confidence(X \rightarrow Y) = \frac{support(X \cup Y)}{support(X)} \]

  5. Podniesienie (lift):

    • Miara zależności między \(X\) i \(Y\), pokazująca, jak bardzo wystąpienie \(X\) zwiększa prawdopodobieństwo wystąpienia \(Y\): \[ lift(X \rightarrow Y) = \frac{confidence(X \rightarrow Y)}{support(Y)} \]

Jak działa algorytm Apriori?

  1. Inicjalizacja:

    • Zidentyfikuj wszystkie zbiory jednoelementowe (\(k = 1\)) spełniające minimalny próg wsparcia.

  2. Generowanie kandydatów:

    • Dla każdej iteracji (\(k > 1\)), twórz zbiory kandydatów (\(C_k\)) poprzez łączenie zbiorów częstych (\(L_{k-1}\)) z poprzedniej iteracji.

  3. Obliczanie wsparcia:

    • Dla każdego kandydata w \(C_k\), sprawdź jego wsparcie, licząc liczbę transakcji, które go zawierają.

  4. Przycinanie:

    • Usuń kandydatów, których wsparcie jest mniejsze niż \(min\_support\).

  5. Powtórzenie:

    • Iteruj, aż żadne nowe zbiory częste nie zostaną znalezione.

  6. Generowanie reguł asocjacyjnych:

    • Na podstawie zbiorów częstych wygeneruj reguły asocjacyjne i oceń je za pomocą miar takich jak ufność i podniesienie.

Przykład działania:

Załóżmy, że mamy następujący zbiór transakcji:

Transakcja Produkty
T1 {A, B, C}
T2 {A, C}
T3 {A, B}
T4 {B, C}
T5 {A, B, C}

Kroki:

  1. Krok 1: Zbiory jednoelementowe (\(k = 1\)):

    • Oblicz wsparcie dla każdego elementu:
      • \(support(A) = \frac{4}{5} = 0.8\)
      • \(support(B) = \frac{4}{5} = 0.8\)
      • \(support(C) = \frac{4}{5} = 0.8\)
    • Wszystkie elementy są częste (\(min\_support = 0.6\)).

  2. Krok 2: Zbiory dwuelementowe (\(k = 2\)):

    • Kandydaci: \(\{A, B\}, \{A, C\}, \{B, C\}\).
    • Oblicz wsparcie:
      • \(support(A, B) = \frac{3}{5} = 0.6\)
      • \(support(A, C) = \frac{3}{5} = 0.6\)
      • \(support(B, C) = \frac{3}{5} = 0.6\)
    • Wszystkie zbiory dwuelementowe są częste.

  3. Krok 3: Zbiory trójelementowe (\(k = 3\)):

    • Kandydat: \(\{A, B, C\}\).
    • Oblicz wsparcie:
      • \(support(A, B, C) = \frac{2}{5} = 0.4\).
    • Zbiór \(\{A, B, C\}\) nie jest częsty (\(support < 0.6\)).

  4. Generowanie reguł asocjacyjnych:

    • Dla zbioru \(\{A, B\}\):
      • \(confidence(A \rightarrow B) = \frac{support(A, B)}{support(A)} = \frac{0.6}{0.8} = 0.75\).

Zalety algorytmu Apriori:

Wady algorytmu Apriori:

Zastosowania:

  1. Analiza koszyka zakupowego:
    • Znajdowanie produktów często kupowanych razem.
  2. Systemy rekomendacyjne:
    • Rekomendowanie produktów na podstawie wzorców zakupowych.
  3. Medycyna:
    • Identyfikacja współwystępujących objawów lub leków.
  4. Marketing:
    • Tworzenie kampanii na podstawie wzorców zachowań klientów.

Algorytm Apriori to jedno z podstawowych narzędzi w analizie asocjacyjnej, szczególnie przydatne w eksploracji dużych zbiorów transakcyjnych.