Spis treści

LAB: Uczenie nienadzorowane

Laboratorium kontynuuje poprzednie zajęcia rozszerzając wiedzę dotyczącą sposobów nabywania wiedzy przez inteligentnych agentów o wybrane metody uczenia nienadzorowanego.

Laboratorium zostało przygotowane w oparciu o materiały z kursów: Data Mining with Weka, More Data Mining with Weka i Machine Learning oraz w oparciu o materiały udostępniane z podręcznikiem Artificial Intelligence: Foundations of Computational Agents.

1 Do przygotowania

2 Reguły asocjacyjne

Reguły asocjacyjne przypominają reguły decyzyjne omawiane na jednym z poprzednich laboratoriów. 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 [15 minut]

Dane

Mamy dane następujące informacje o transakcjach w jednym z hipermarketów:

Numer paragonu Kupione produkty
1000 Ananas, Chleb, Drożdże
2000 Banan, Chleb, Eukaliptus
3000 Ananas, Eukaliptus, Chleb, Banan
4000 Banan, Eukaliptus

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 Banan then Eukaliptus
if Eukaliptus then Banan
if Ananas then Chleb
if Chleb then Ananas

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 Banan then Eukaliptus

jest równy $\frac{3}{4}=75\%$, ponieważ 3 transakcje zawierają Banan i Eukaliptus, natomiast ilość wszystkich transakcji jest równa 4.

Pytanie Jaki jest support dla reguły poniżej? 

if Ananas then Chleb
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 Banan then Eukaliptus

jest równy $\frac{3}{3}=100\%$, ponieważ 3 transakcje zawierają Banan i Eukaliptus, natomiast ilość transakcji zawierających elementy z części warunkowej tej reguły (czyli w tym wypadku Banan) jest także równa 3.

Pytanie Jaki jest confidence dla reguł poniżej? 

if Chleb then Ananas 
if Ananas then Chleb

Frequent Itemsets

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-itemsets).

Pytanie Zakładając, ze bazujemy na danych z tabeli na początku sekcji Analiza koszykowa, wyznacz wszystkie 1-zbiory i policz dla nich support.
Przyjmując, że support progowy jest równy 50%, wyznacz 1-zbiór częsty.

Algorytm Apriori [10 minut]

Na zasadzie opisanej powyżej działa najpopularniejszy algorytm wyszukujący reguły asocjacyjne - algorytm Apriori. Wykonuje on następujące 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}$$

Dla ułatwienia, poniżej znajduje się rysunek pokazujący jak powinien działać algorytm na danych z tabeli na początku sekcji Analiza koszykowa1)
Uwaga 1: Na rysunku nie są przedstawione wszystkie k-zbiory częste.
Uwaga 2: 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.

Apriori i Weka

Weka zawiera implementację algorytmu Apriori, którą teraz przetestujemy na następującym zestawie transakcji:

Paragon Zakupy
1 A,B,C,D,G,H
2 A,B,C,D,E,F,H
3 B,C,D,E,H
4 B,E,G,H
5 A,B,D,E,G,H
6 A,C,F,G,H
7 B,D,E,G,H
8 A,C,D,E,G,H
9 B,C,D,E,H
10 A,C,E,F,H
11 C,E,H
12 A,D,E,F,H
13 B,C,E,F,H
14 A,B,C,F,H
15 A,B,E,F,H

Zadania:

  1. Na początek należy przygotować odpowiedni plik Weki
    1. jak myślisz, w jaki sposób najlepiej zakodować informacje?
    2. możesz wzorować się na plikach z poprzedniego laboratorium data.tar.gz
    3. Możesz skorzystać z gotowego pliku umieszczonego tutaj: apriori-zakupy.arff.zip
  2. Wczytaj plik do Weki, przejdź do zakładki Associate i uruchom algorytm z domyślnymi ustawieniami. Jakie wyniki się pojawiły?
  3. Pobaw się ustawieniami algorytmu (aby wejść w ustawienia kliknij w wiersz z nazwą algorytmu i jego parametrami): Czy wiesz jak wyświetlić informację o znalezionych k-zbiorach? Czy wiesz jak zmienić oczekiwany poziom supportu i confidence? Czy rozumiesz pozostałe parametry? Sprawdź jak one wpływają na otrzymywane wyniki.

Duży przykład [15 minut]

W zestawie danych data.tar.gz znajduje się plik supermarket.arff – zawiera informacje o prawdziwych zakupach z jednego z supermarketów w Nowej Zelandii. Otwórz go w Wece i odpowiedz na następujące pytania:

  1. Ile jest atrybutów i co one reprezentują?
  2. Ile jest instancji i co one reprezentują?
  3. W zakładce Preprocess kliknij Edit… i przyjrzyj się danym: jakie wartości przyjmują atrybuty? Czy wszystkie wartości są uzupełnione?
  4. Jakie są 3 produkty najczęściej kupowane w tym sklepie? Jak to sprawdzić w zakładce Preprocess, a jak to sprawdzić za pomocą algorytmu Apriori wbudowanego w Wekę?
  5. Uruchom algorytm Apriori przy domyślnych ustawieniach. Następnie uruchom algorytm Apriori przy domyślnych ustawieniach dla tego samego zbioru danych, w którym zamiast brakujących wartości są wartości n: supermarket-nonmiss.arff.zip. Porównaj otrzymane wyniki.
  6. Następnie zrób takie samo porównanie dla danych z tabeli w sekcji Apriori i Weka. Jeden plik został przygotowany przez Ciebie już wcześniej - do porównania należy przygotować jeszcze drugi plik tak, aby jeden z nich zawierał wartości nie/fałsz, a drugi nieokreślone. Porównaj otrzymane wyniki.
  7. Po zapoznaniu się z wynikami, podaj co najmniej jeden argument za stosowaniem wartości nieokreślonej i co najmniej jeden za stosowaniem wartości nie/fałsz.

Pytania:

  1. W ramach laboratorium rozważaliśmy tworzenie reguł asocjacyjnych w analizie koszykowej, czyli ustalaliśmy jakie produkty są ze sobą najczęściej łączone w trakcie zakupów. Do czego może się przydać taka wiedza? Wymyśl dwa zastosowania.
  2. Do czego innego może przydać się tworzenie reguł asocjacyjnych? Wymyśl dwa problemy / pytania (niezwiązane z zakupami), na które można znaleźć dzięki nim odpowiedź.

3 Klasteryzacja

Klasteryzacja to przykład klasyfikacji. Podobnie jak w drzewach decyzyjnych z poprzedniego laboratorium, podejmujemy decyzję o określeniu przynależności elementu do jednej z grup. Tutaj jednak nie mamy z góry określonych kategorii, a są one tworzone na podstawie dostępnego zbioru danych uczących.

Istnieją różne rodzaje klastrów:

  1. Klastry rozłączne (np. algorytm K-Means/X-Means w dalszej części laboratorium):
  2. Klastry nachodzące na siebie (np. algorytm EM w dalszej części laboratorium):
  3. Klastry probabilistyczne (np. algorytm EM w dalszej części laboratorium):
  4. Klastry hierarchiczne:

Algorytm K-Means [20 minut]

Algorytm K-Means to prosty algorytm bez nauczyciela dzielący zbiór uczący na K klastrów zawierających podobne elementy (podobieństwo jest tutaj określone jako bliskość w przestrzeni elementów). Każdy z klastrów reprezentowany jest przez punkt (centroid) określający położenie środka klastra. Wyznaczanie centroidów przebiega zgodnie z następującymi krokami:

  1. Wylosuj K punktów (centroidów) w przestrzeni elementów.
  2. Oblicz odległość każdego z elementów od centroidów i przypisz ten element do najbliższego z nich.
  3. Zaktualizuj położenie każdego centroidu ustawiając go jako średnią wszystkich punktów, które są do niego przypisane.
  4. Powtarzaj kroki 2-3 aż do uzyskania zbieżności (przesunięcie centroidów w kroku 3 będzie mniejsze od ustalonego progu).

Nie ma tutaj zewnętrznego nauczyciela, wobec tego należy przyjąć inną strategię oceny poprawności rozwiązania – jedną z najprostszych możliwości jest tutaj policzenie sumy kwadratów odległości pomiędzy elementami i ich centroidami. W ten sposób promowane są rozwiązania, w których odległości są mniejsze, a co za tym idzie – elementy rzeczywiście są (względnie) blisko siebie.

Działanie algorytmu zaobserwuj w praktyce przy użyciu narzędzia http://krzysztof.kutt.pl/didactics/psi/kmeans/. Dokonaj klasteryzacji kilka razy (losowanie nowych danych za pomocą New points, losowanie nowych centroidów za pomocą New centroids, kolejne kroki za pomocą przycisku Find closest centroid/Update centroid) w różnych warunkach:

Pytania:

Jeżeli chcesz się jeszcze pobawić algorytmem K-Means, możesz skorzystać z apletu http://www.naftaliharris.com/blog/visualizing-k-means-clustering/, który pozwala między innymi na ręczne zaznaczanie początkowych położeń centroidów. Have fun :-)

K-Means i Weka

Otwórz w Wece plik iris.arff z zestawu danych data.tar.gz. Wykorzystywaliśmy już ten plik na poprzednim laboratorium - opisuje on parametry kwiatów należących do trzech gatunków Irysów:

Zadania:

  1. Przypomnij sobie jak zbudowany jest ten plik: ile jest atrybutów, jakich są typów, ile jest instancji. Zapoznaj się z budową zboru uczącego: kliknij Edit… w zakładce Preprocess. Zauważ, że dane są podzielone względem klas: najpierw 50 instancji jednej klasy, następnie 50 instancji drugiej i na końcu 50 instancji trzeciej klasy.
  2. Przejdź na zakładkę Visualize i zapoznaj się z rozkładem danych:
    • Są to trójwymiarowe wykresy bazujące na trzech wybranych atrybutach ze zbioru danych: oś X, oś Y i różne kolory - upewnij się, że kolorem oznaczony jest atrybut class (domyślnie).
    • Kliknięcie na wykres pozwala na jego powiększenie (na powiększeniu można manipulować atrybutami położonymi na osiach).
  3. Wyobraź sobie sytuację, w której znika atrybut class (znikają kolory) – czy jesteś w stanie ponownie pogrupować te dane w pierwotne klasy?
  4. Spróbujmy to zrobić za pomocą algorytmu K-Means zaimplementowanego w Wece:
    1. Przejdź do zakładki Cluster.
    2. Zostaw domyślną wartość Cluster mode = Use training set
    3. Wybierz algorytm SimpleKMeans, w ustawieniach zmień liczbę klastrów na 3 i uruchom go.
    4. Zapoznaj się z wynikami:
      • Z wyświetlonym raportem
      • Z wizualizacją: kliknij prawym na wynik klasteryzacji w Result list i z menu wybierz Visualize cluster assignments
      • Przede wszystkim zapoznaj się z wizualizacją: X = Class, Y = Cluster. Możesz jeszcze pobawić się suwakiem Jitter, który rozrzuca dane (bo wiele punktów znajduje się w tym samym miejscu).
      • Czy dane zostały poprawnie zaklasyfikowane? Jaki błąd popełniliśmy?
  5. Spróbujmy to zrobić po raz kolejny:
    1. Kliknij przycisk Ignore attributes, zaznacz odpowiedni atrybut (który?) i kliknij Select. Uruchom ponownie klasteryzację.
    2. Zapoznaj się z wynikami i porównaj je z uzyskanymi wcześniej. Jaka teraz była skuteczność klasyfikacji?
    3. Czy wiesz który z trzech gatunków Irysów został w 100% poprawnie zaklasyfikowany przez ten algorytm? Możesz to odczytać z wykresu wizualizującego wyniki klasyfikacji, jak również możesz w Cluster mode zaznaczyć opcję Classes to clusters evaluation. Po wybraniu tej opcji i wyświetleniu wizualizacji możesz zobaczyć na wykresie krzyżyki (poprawne trafienia) i kwadraty (niepoprawne klasyfikacje).
  6. Przeprowadź klasteryzację po raz trzeci. Tym razem nie zmieniaj żadnych ustawień. Czy pojawiły się dokładnie takie same wyniki?
    • Jak to było wcześniej powiedziane, algorytm K-Means losuje początkowe położenie centroidów, więc wyniki powinny się od siebie różnić. Tutaj jednak są takie same…
    • W jaki sposób sprawić aby wylosowały się inne wyniki?

Inne algorytmy klasteryzacji [10 minut]

Algorytm X-Means

Algorytm K-Means jest bardzo popularny, ale ma kilka wad, m.in. nie jest w pełni automatyczny – użytkownik musi samodzielnie określić liczbę klastrów. Co jednak w sytuacji kiedy nie chcemy albo nie możemy tego zrobić (po prostu nie wiemy ile takich klastrów będzie)? Przygotowane zostało rozszerzenie algorytmu K-Means o m.in. automatyczne wyznaczanie ilości klastrów (w przedziale określonym przez użytkownika). Algorytm ten to X-Means i działa on wykonując następujące kroki:

  1. Rozpoczęcie algorytmu z najmniejszym dozwolonym przez użytkownika K.
  2. Ulepszanie parametrów – wykonywanie algorytmu K-Means dla aktualnego K aż do uzyskania zbieżności.
  3. Ulepszanie struktury – podzielenie wybranego centroidu na dwa centroidy i wykonanie kroku 2 aż do uzyskania zbieżności. Jeżeli wynik jest lepszy (zgodnie z przyjętą metryką) to go akceptujemy i zwiększamy K o 1. Jeśli nie – próbujemy podzielić inny centroid.
  4. Wykonujemy kroki 2-3 aż do momentu kiedy podział nie ulepsza rozwiązania / K osiągnie maksymalną dozwoloną wartość.

Zadania:

  1. Wczytaj ponownie plik iris.arff do Weki.
  2. W zakładce Cluster wybierz algorytm XMeans i uruchom go na domyślnych ustawieniach.
    • Algorytm XMeans operuje tylko i wyłącznie na atrybutach numerycznych. Dlatego aby go włączyć należy: (a) albo w Ignore attributes wybrać class, (b) albo wybrać opcję Classes to clusters evalutaion.
  3. Zapoznaj się z otrzymanymi wynikami:
    • Ile klastrów pojawiło się w wynikowym modelu?
    • Przeanalizuj wizualizację wyników.
    • Porównaj otrzymane wyniki z wynikami z K-Means.
  4. Zapoznaj się z dostępnymi opcjami i ich znaczeniem. Poeksperymentuj z różnymi ustawieniami.

Algorytm EM

Algorytmy K-Means i X-Means jednoznacznie dzielą przestrzeń przykładów na odpowiednią liczbę klastrów. Każdy z klastrów reprezentowany jest przez położenie centroidu, a element należy do tego klastru, którego centroid znajduje się najbliżej.

W algorytmie EM (Expectation-Maximization) klastry reprezentowane są przez średnie (będące odpowiednikami centroidów) oraz odchylenia standardowe. Dzięki temu możliwe jest określenie prawdopodobieństwa przynależności elementu do każdego klastru i wybranie tego o największej wartości (nie jest to więc „sztywny” jednoznaczny podział jak w K-Means tylko „miękki”).

Działanie algorytmu może być różne w zależności od implementacji, ale w ogólnym wypadku wygląda analogicznie jak w przypadku algorytmu K-Means i zostało zobrazowane na poniższym gifie:

Zadania:

  1. Wczytaj ponownie plik iris.arff do Weki.
  2. W zakładce Cluster wybierz algorytm EM i uruchom go na domyślnych ustawieniach.
  3. Zapoznaj się z otrzymanymi wynikami:
    • Ile klastrów pojawiło się w wynikowym modelu? Na domyślnych ustawieniach algorytm EM sam ustala optymalną liczbę klastrów - czy wiesz jak to zmienić?
    • Przeanalizuj wizualizację wyników.
    • Porównaj otrzymane wyniki z wynikami z K-Means i X-Means.
  4. Zapoznaj się z dostępnymi opcjami i ich znaczeniem. Poeksperymentuj z różnymi ustawieniami.

4 Poprawność klasyfikacji [10 minut]

Pytania:

  1. Załaduj plik credit-g.arff do Weki. Zawiera on dane uczące dla systemu, który na podstawie atrybutów zawartych w pliku powinien określać czy dany zestaw wartości atrybutów wskazuje na wiarygodnego klienta banku, czy też nie - czy można przyznać mu kredyt, czy jest to ryzykowne.
  2. Przejdź do zakładki Classify i wybierz algorytm J48.
  3. W obszarze Test options wybierz opcje Percentage split z wartością 66% Oznacza to, ze 66% danych posłuży do uczenia, a 34% do walidacji. Jakie to ma znaczenie?
  4. Uruchom algorytm. Ile procent przypadków zostało poprawnie zaklasyfikowanych? Czy to dobry wynik?
  5. Zmień klasyfikator na ZeroR z gałęzi rules. Jakie są wyniki?
  6. Wybierz trzy inne klasyfikatory i je wypróbuj. Jakie dają wyniki?
  7. Przejdź do zakładki Preprocess i zobacz jak wygląda rozkład atrybutu określającego czy danych zestaw jest dobry czy zły. Jaka byłaby skuteczność algorytmu który niezależnie od wartości atrybutów „strzelałby” że użytkownik jest wiarygodny?
  8. Dlaczego przed przystąpieniem do klasyfikacji, warto wcześniej przyjrzeć się danym? :-P

5 Większy zbiór danych [10 minut] (o ile wystarczy czasu)

Wybierz jeden zbiór danych:

Ściągnij go i pobaw się nim z użyciem metod, które pojawiły się na aktualnym i poprzednim laboratorium, np.:

Chcesz wiedzieć więcej?

Machine Learning ogólnie

2019/03/05 15:14
1)
A - Ananas, B - Banan, C - Chleb, D - Drożdże, E - Eukaliptus