====== Laboratorium 11 -- 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:
<code>
if Piwo then Jajka
if Jajka then Piwo
if Jabłka then Seler
if Seler then Jabłka
</code>

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 <code>If Piwo then Jajka </code> 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? <code> if Jabłka then Seler </code>
===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 <code>If Piwo then Jajka </code> 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? 
<code> 
if Seler then Jabłka 
if Jabłka then Seler
</code>
===== 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:
  - znajdź wszystkie 1-zbiory (//1-itemsets//)
  - 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$
  - bazując na $L_1$ wygeneruj //2-zbiory// (//2-itemsets//)
  - znajdź pośród wygenerowanych //2-zbiorów//, //częste 2-zbiory// $L_2$
  - 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}$$


===== Weka =====
  - Na podstawie wiedzy zdobytej na poprzednich laboratoriach 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: {{:pl:dydaktyka:ml:data.tar.gz|}}
  - Po wczytaniu pliku do weki, przejdź do zakładki //Associate// i uruchom algorytm z domyślnymi parametrami. Jakie wyniki otrzymałeś(aś)? Dlaczego?
  - Wczytaj plik //shopping.arff// i przeprowadź na nim wyszukiwanie reguł asocjacyjnych. Pobaw się parametrami algorytmu

===== Orange =====
  - Zainstaluj Orange: [[https://orange.biolab.si/download/linux/|HWOTO]]
  - Uruchom: <code>orange-canvas</code>
  - Zainstaluj Add-on o nazwie Associate
  - Przejrzyj tutorial: [[https://blog.biolab.si/2016/04/25/association-rules-in-orange/|Association rule mining with Orange]]