Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:ml:2018lab9 [2018/06/04 21:47] esimon utworzono |
pl:dydaktyka:ml:2018lab9 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | |||
| - | ====== 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 | ||
| - | |||
| - | |||
| - | |||
