Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ml:2014lab4 [2014/04/01 17:17] esimon [Frequent Itemsets] |
pl:dydaktyka:ml:2014lab4 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 10: | Linia 10: | ||
| |1000 | Jabłka, Seler, Pieluchy | | |1000 | Jabłka, Seler, Pieluchy | | ||
| |2000 | Piwo, Seler, Jajka | | |2000 | Piwo, Seler, Jajka | | ||
| - | |3000 | Jabłka, Piwo, Seler, Piwo | | + | |3000 | Jabłka, Jajka, Seler, Piwo | |
| |4000 | Piwo, Jajka | | |4000 | Piwo, Jajka | | ||
| Linia 38: | Linia 38: | ||
| **Pytanie** Jaki jest //support// dla reguły poniżej? <code> if Jabłka then Seler </code> | **Pytanie** Jaki jest //support// dla reguły poniżej? <code> if Jabłka then Seler </code> | ||
| ===Confidence=== | ===Confidence=== | ||
| - | Wskaźnik ten określa siłę implikacji w regule. Innymi słowy jest on definiowany jako stosunek ilości transakcji zawierających elementy wchodzące w skład reguły do wszystkich transakcji zawierających elementy z części warunkowej reguły. | + | 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. | 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. | ||
| Linia 48: | Linia 48: | ||
| </code> | </code> | ||
| ===== Frequent Itemsets ===== | ===== Frequent Itemsets ===== | ||
| - | Patrząc na przykłady powyżej odnalezienie dobrych reguł asocjacyjnych sprowadza się tak naprawdę do dwóch kroków | + | 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//) | * 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//. | * wybrania spośród nich tych konfiguracji, których //confidence// przekracza jakiś zadany //confidence progowy//. | ||
| Linia 65: | Linia 65: | ||
| Wykonuje on następujace krok: | Wykonuje on następujace krok: | ||
| - znajdź wszystkie 1-zbiory (//1-itemsets//) | - 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$ | + | - 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//) | - bazując na $L_1$ wygeneruj //2-zbiory// (//2-itemsets//) | ||
| - | - znajdź pośród wygenerowanych //2-zbiorów// częste //2-zbiory// $L_2$ | + | - 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$ | - Powtarzaj proces, do momentu aż ostatni wygenerowany zbiór $L_{k-1}=\o$ | ||
| Linia 78: | Linia 78: | ||
| &\qquad\qquad \mathrm{\textbf{while}}~ L_{k-1} \neq \ \emptyset \\ | &\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 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 \mathrm{\textbf{for}~transactions}~t \in T\\ | + | &\qquad\qquad\qquad L_k \gets \{ c \mid c \in C_k \land ~ \mathit{support}[c] \geq \epsilon \}\\ |
| - | &\qquad\qquad\qquad\qquad C_t \gets \{ c \mid c \in C_k \land c \subseteq t \} \\ | + | |
| - | &\qquad\qquad\qquad\qquad \mathrm{\textbf{for}~candidates}~c \in C_t\\ | + | |
| - | &\qquad\qquad\qquad\qquad\qquad \mathit{count}[c] \gets \mathit{count}[c]+1\\ | + | |
| - | &\qquad\qquad\qquad L_k \gets \{ c \mid c \in C_k \land ~ \mathit{count}[c] \geq \epsilon \}\\ | + | |
| &\qquad\qquad\qquad k \gets k+1\\ | &\qquad\qquad\qquad k \gets k+1\\ | ||
| &\qquad\qquad \mathrm{\textbf{return}}~\bigcup_k L_k | &\qquad\qquad \mathrm{\textbf{return}}~\bigcup_k L_k | ||
| \end{align}$$ | \end{align}$$ | ||
| - | ===== Weka ===== | ||
| + | ==== Implementacja ==== | ||
| + | - Pobierz plik {{:pl:dydaktyka:ml:apriori.m.zip|}} i przyjrzyj się funkcjom które zostały w nim zaimplementowane. | ||
| + | - Bazując na algorytmie powyżej, zaimplementuj nową funkcję o nagłówku poniżej: <code>function FrequentKitemsets = apriori(OneItemsets, Transactions)</code> | ||
| + | - Wyznacz reguły które mają $confidence \geq 60\%$ i $support \geq 50\%$ | ||
| + | - 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//). | ||
| + | - **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. | ||
| + | |||
| + | {{:pl:dydaktyka:ml:apriori.png?500|}} | ||
| + | |||
| + | |||
| + | ===== Weka ===== | ||
| + | - 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: {{: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 | ||
