Reguły asocjacyjne przypominają reguły decyzyjne omawiane na poprzednim wykładzie. Tym razem jednak decyzja (prawa strona implikacji) nie jest z góry określona, tzn. nie wiemy, na którym atrybucie ma się opierać. Jest to przykład nauki bez nauczyciela: algorytm nie ma określonej z góry prawidłowej odpowiedzi, zamiast tego ma opisać wewnętrzne zależności między atrybutami.
Mamy dane następujące informacje o transakcjach w jednym z hipermarketów:
| Numer paragonu | Kupione produkty |
|---|---|
| 1000 | Jabłka, Seler, Pieluchy |
| 2000 | Piwo, Seler, Jajka |
| 3000 | Jabłka, Jajka, Seler, Piwo |
| 4000 | Piwo, Jajka |
Zadaniem algorytmu odkrywającego reguły asocjacyjne będzie odpowiedź napytanie: Jakie są zależności pomiędzy kupowanymi produktami?
Pytanie Patrząc na zbiór uczący w tabeli powyżej wypisz reguły które będą określać jakie produkty są kupowane najczęściej razem.
Z powyższego zbioru uczącego możemy łatwo wywnioskować następujące reguły:
if Piwo then Jajka if Jajka then Piwo if Jabłka then Seler if Seler then Jabłka
Pozostałe reguły intuicyjnie odrzuciliśmy ponieważ ich częstotliwość w zbiorze uczącym jest niewielka, i w związku z tym mamy małą pewność co do ich prawdziwości. W celu automatycznego określenia tych parametrów stosuje się dwa wskaźniki: support (wsparcie) i confidence (wiarygodność)
Wskaźnik ten określa częstotliwość (prawdopodobieństwo) danej reguły w stosunku do wszystkich transakcji. Innymi słowy jest to stosunek ilości transakcji zawierających dane elementy wchodzące w skład reguły do wszystkich transakcji.
Dla przykładu z tabeli powyżej, support reguły
If Piwo then Jajka
jest równy 
, ponieważ 3 transakcje zawierają Piwo i Jajka, natomiast ilość wszystkich transakcji jest równa 4.
Pytanie Jaki jest support dla reguły poniżej?
if Jabłka then Seler
Wskaźnik ten określa siłę implikacji w regule. Innymi słowy jest on definiowany jako stosunek ilości transakcji zawierających wszystkie elementy wchodzące w skład reguły do transakcji zawierających elementy z części warunkowej reguły.
Dla przykładu z tabeli powyżej, confidence reguły
If Piwo then Jajka
jest równy 
, ponieważ 3 transakcje zawierają Piwo i Jajka, natomiast ilość transakcji zawierających elementy z części warunkowej tej reguły (czyli w tym wypadku Piwo) jest także równa 3.
Pytanie Jaki jest confidence dla reguł poniżej?
if Seler then Jabłka if Jabłka then Seler
Patrząc na przykłady powyżej odnalezienie dobrych reguł asocjacyjnych sprowadza się tak naprawdę do wykonania dwóch kroków
W przypadku reguł asocjacyjnych, zbiory które zawierają k elementów nazywane są k-zbiorami (k-temsets).
Pytanie Zakładając, ze bazujemy na danych z tabeli z początku strony, wyznacz wszystkie 1-zbiory i policz dla nich support. Przyjmując, że support progowy jest równy 50%, wyznacz 1-zbiór częsty.
Na zasadzie opisanej powyżej działa najpopularniejszy algorytm wyszukujący reguły asocjacyjne - algorytm Apriori. Wykonuje on następujace krok:
) - czyli takie, których support jest 
wygeneruj 2-zbiory (2-itemsets)
Poniżej znajduje się bardziej formalny opis algorytmu:
![$$\begin{align}
& \mathrm{Apriori}(T,\epsilon)\\
&\qquad L_1 \gets \{ \mathrm{1-item sets} \} \\
&\qquad k \gets 2\\
&\qquad\qquad \mathrm{\textbf{while}}~ L_{k-1} \neq \ \emptyset \\
&\qquad\qquad\qquad C_k \gets \{ a \cup \{b\} \mid a \in L_{k-1} \land b \in \bigcup L_{k-1} \land b \not \in a \}\\
&\qquad\qquad\qquad L_k \gets \{ c \mid c \in C_k \land ~ \mathit{support}[c] \geq \epsilon \}\\
&\qquad\qquad\qquad k \gets k+1\\
&\qquad\qquad \mathrm{\textbf{return}}~\bigcup_k L_k
\end{align}$$](/lib/exe/fetch.php?media=wiki:latex:/img70da14b3526a2ce158df8a1eded01e16.png "Equation")
orange-canvas
