Reguły asocjacyjne

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.

Analiza koszykowa

Dane

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.

Support i Confidence

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ść)

Support

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 $\frac{3}{4}=75\%$, 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 

Confidence

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 $\frac{3}{3}=100\%$, 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

Frequent Itemsets

Patrząc na przykłady powyżej odnalezienie dobrych reguł asocjacyjnych sprowadza się tak naprawdę do wykonania dwóch kroków

  • wyszukania zbiorów elementów które mają support większy lub równy jakiemuś zadanemu supportowi progowemu - są tak zwanymi zbiorami częstymi (frequent itemsets)
  • wybrania spośród nich tych konfiguracji, których confidence przekracza jakiś zadany confidence progowy.

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.

Apriori

Na zasadzie opisanej powyżej działa najpopularniejszy algorytm wyszukujący reguły asocjacyjne - algorytm Apriori. Wykonuje on następujace krok:

  1. znajdź wszystkie 1-zbiory (1-itemsets)
  2. znajdź pośród wygenerowanych 1-zbiorów, częste 1-zbiory (frequent 1-itemsets $L_1$) - czyli takie, których support jest $\geq \epsilon$
  3. bazując na $L_1$ wygeneruj 2-zbiory (2-itemsets)
  4. znajdź pośród wygenerowanych 2-zbiorów, częste 2-zbiory $L_2$
  5. Powtarzaj proces, do momentu aż ostatni wygenerowany zbiór $L_{k-1}=\o$

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}$$

Implementacja

  1. Pobierz plik apriori.m.zip i przyjrzyj się funkcjom które zostały w nim zaimplementowane.
  2. Bazując na algorytmie powyżej, zaimplementuj nową funkcję o nagłówku poniżej:
    function FrequentKitemsets = apriori(OneItemsets, Transactions)
  3. Wyznacz reguły które mają $confidence \geq 60\%$ i $support \geq 50\%$
  4. Dla ułatwienia, poniżej znajduje się rysunek pokazujący jak powinien działać algorytm (Uwaga na rysunku nie są przedstawiane wszystkie k-zbiory częste).
  5. Uwaga Algorytm przedstawiony na rysunku poniżej zawiera pewną optymalizację polegająca na obserwacji, że zbiór 3-elementowy nie może być częsty jeśli zawiera w sobie zbiór dwuelementowy, który nie jest częsty.

Weka

  1. Na podstawie wiedzy zdobytej na poprzednim laboratorium przygotuj plik arff dla weki, opisujący dane z tabeli z początku strony. Jak powinien wyglądać plik? Spróbuj pomóc sobie patrząc na plik shopping.arff ze zbioru danych: data.tar.gz
  2. Po wczytaniu pliku do weki, przejdź do zakładki Associate i uruchom algorytm z domyślnymi parametrami. Jakie wyniki otrzymałeś(aś)? Dlaczego?
  3. Wczytaj plik shopping.arff i przeprowadź na nim wyszukiwanie reguł asocjacyjnych. Pobaw się parametrami algorytmu
pl/dydaktyka/ml/2014lab4.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0