Lab6: Klasyfikacja

Klasyfikator kNN

Klasyfikator kNN jest jednym z najprostszych klasyfikatorów, ale w wielu zastosowaniach daje całkiem niezłe wyniki. Polega on na przypisaniu danej obserwacji takiej klasy, jaka pojawia się najczęściej wśród jej $k$ najbliższych sąsiadów. Użytkownik decyduje, jak ustawić parametr $k$ oraz jaką miarę odległości wykorzystać. Szczegóły dotyczące tego klasyfikatora zostały omówione na wykładzie piątym.

Zadanie 2. Zadanie przykładowe. Korzystając z klasyfikatora kNN, spróbuj przewidzieć jakość wina o parametrach 0.42, 0.03, -0.90, 0.15, -1.25, -0.15, -0.01, 0.73, 0.90, -0.82, -0.69. Parametry odpowiadają wycentrowanym i wyskalowanym danym.

Rozwiązanie. Ponieważ w treści zadania nie ma podanej wartości $k$, wybierzemy sobie $k=3$.

W pierwszym kroku tworzymy wektor wartości predyktorów.

x <- c(0.42, 0.03, -0.90, 0.15, -1.25, -0.15, -0.01, 0.73, 0.90, -0.82, -0.69)

Następnie obliczamy odległość wektora x od wszystkich obserwacji w danych wine.
Wykorzystamy w tym celu funkcję apply() przyłożoną do macierzy wine[,-1], czyli danych wine z usuniętą pierwszą kolumną.

distances <- apply(wine[,-1], 1, function(y) sqrt(sum((x-y)^2)))

Wewnątrz apply stworzyliśmy funkcję wewnętrzną, która przyjmuje zmienną y, następnie najpierw oblicza wektor różnic x-y, podnosi każdą współrzędną do kwadratu, (x-y)^2, sumuje kwadraty różnic, sum((x-y)^2), i bierze pierwiastek z sumy kwadratów różnic, sqrt(sum((x-y)^2)). Krótko mówiąc, oblicza odległość euklidesową pomiędzy wektorami x i y.

Teraz musimy znaleźć k wierszy z wine o najmniejszych odległościach od x. W tym celu wykorzystamy funkcję order(v), która przyjmuje wektor v i zwraca indeksy odpowiadające rosnącym wartościom z v. Innymi słowy, order(v)[1] to indeks najmniejszej wartości z v, order(v)[2] to indeks drugiej z kolei wartości z v i tak dalej.

k <- 3
najblizsze_wiersze <- order(distances)[1:k]

Numery k wierszy najbliższych x to 2, 9, 2077. Trzeba teraz wybrać klasy odpowiadające tym wierszom:

najblizsze_klasy <- wine[najblizsze_wiersze, 1]

Najbliższe klasy to 6, 6, 5. Jako klasę obserwacji x przypisujemy na ogół najczęstszą spośród k najbliższych klas. W tym celu musimy policzyć, ile razy zaobserwowaliśmy każdą z klas. Wykorzystamy do tego funkcję table(), która oblicza macierze kontyngencji:

czestosc_klas <- table(najblizsze_klasy)
czestosc_klas

## najblizsze_klasy
## 3 4 5 6 7 8 9 
## 0 0 1 2 0 0 0

W pierwszym wierszu widzimy kolejne jakości wina, a w drugim - częstości ich wystąpień wśród wierszy najbliższych do x.
Żeby otrzymać powyższy wynik, kluczowe jest, żeby kolumna Quality była typu factor.
W przeciwnym wypadku funkcja table() weźmie pod uwagę wyłącznie te wartości, które wystąpiły w wektorze najblizsze_klasy. To oznacza że wektor czestosc_klas będzie miał długość 2, a nie 6. Dzięki użyciu factora długość wektora czestosc_klas nie zależy od wartości wektora czestosc_klas, a w szczególności od wartości k.

Najczęstszą klasę wybierzemy za pomocą funkcji which.max():

najczestsza_klasa <- which.max(czestosc_klas)
najczestsza_klasa

## 6 
## 4

Najczęściej wystąpiła klasa odpowiadająca czwartemu poziomowi factora wine$Quality, który odpowiada jakości 6.
Żeby otrzymać ostateczną klasyfikację, wybierzemy odpowiedni poziom naszego factora. Wektor zawierający wszystkie poziomy otrzymujemy komendą levels(wine$Quality). Z tego wektora następnie wybieramy wartość o indeksie najczestsza_klasa, i przypisujemy ją na zmienną o tej samej nazwie:

najczestsza_klasa <- levels(wine$Quality)[najczestsza_klasa]

Klasyfikator kNN zaklasyfikował wektor x do klasy 6. Żeby sprawdzić wyniki dla różnych wartości parametru k, wystarczy zmienić jego wartość i wywołać komendy ponownie. Nie trzeba w tym celu obliczać na nowo macierzy odległości.

Gotowa implementacja klasyfikatora kNN znajduje sie w funkcji knn w bibliotece class.

Błąd treningowy, błąd testowy

W kontekście klasyfikacji, dane wine zawierające prawdziwe klasy nazywają się danymi treningowymi, a dane które chcemy zaklasyfikować, czyli wektor x, nazywają się danymi testowymi. Jaka jest skuteczność klasyfikatora kNN dla k=1, jeśli klasyfikujemy dane ze zbioru treningowego?

Oczywiście jest równa 100%, ponieważ każdy wektor jest najbliższy samemu sobie. Jeśli wybierzemy wektor ze zbioru treningowego i puścimy klasyfikator kNN dla k=1, to najmniejszą odległość osiągniemy dla tego samego wektora, więc zostanie on zaklasyfikowany poprawnie.

Trochę mało nam to mówi o skuteczności naszego klasyfikatora w ogólnym przypadku.
Dlatego, żeby ocenić jakość klasyfikatora, nigdy nie używamy zbioru treningowego (chyba że absolutnie nie mamy innej możliwości).
Zamiast tego wykorzystujemy zbiór testowy, który ma inny zestaw obserwacji niż zbiór treningowy.

Typowym podejściem jest podzielenie całego zbioru danych w stosunku 1:9 na zbiór testowy i treningowy (czyli wybranie 10% obserwacji do zbioru testowego). Ważne jest, żeby do zbioru testowego wybrać losowe wiersze - w przeciwnym wypadku, jeśli dane są w jakiś sposób posortowane, to ryzykujemy, że wybierzemy bardzo nietypowy zbiór testowy (na przykład złożony wyłącznie z jednej klasy).

Żeby wybrać wiersze do zbioru testowego, wykorzystamy funkcję sample. Jest to bardzo ważna funkcja, więc zapoznaj się z jej dokumentacją. Stworzymy zbiór testowy o 480 elementach, a pozostałe przypiszemy do zbioru treningowego.

indeksy_testowe <- sample(1:nrow(wine), 480, replace=F)
zbior_testowy <- wine[indeksy_testowe, ]
zbior_treningowy <- wine[-indeksy_testowe, ]  # Indeksowanie ujemne wiele ułatwia!

Możemy teraz sprawdzić, jak klasyfikator kNN poradzi sobie na zbiorze testowym. Wykorzystamy w tym celu funkcję knn.

library(class)
wynik <- knn(zbior_treningowy[,-1], zbior_testowy[,-1], zbior_treningowy[,1], k=3)

W zmiennej wynik mamy klasy przypisane kolejnym wierszom ze zbioru testowego. Możemy teraz obliczyć miarę accuracy, czyli proporcję poprawnie zaklasyfikowanych obserwacji:

mean(wynik==zbior_testowy[,1])

## [1] 0.53125

Jak widać, 53.12% obserwacji zostało zaklasyfikowanych poprawnie.

Zadanie 3. Wykorzystując funkcję sapply() i bibliotekę ggplot2, przedstaw na wykresie punktowym zależność accuracy od wartości parametru k dla k od 1 do 15. Wykorzystaj w tym celu zbiór testowy i treningowy stworzony w powyższym przykładzie.
Wskazówka: Postaraj się, aby kod służący do otrzymania wektora zawierającego accuracy dla różnych wartości $k$ zajął jedynie jedną linijkę.

Oczywiście w praktyce podzielenie danych na zbiór treningowy i testowy tylko raz nie wystarczy, żeby otrzymać dokładne wyniki.
To, że sprawdziliśmy 10% losowych wierszy, nie daje nam pełnej informacji o jakości klasyfikatora.
Dlatego na ogół taką operację powtarza się kilkukrotnie, tworząc kilka zbiorów testowych, tak aby każda obserwacja znalazła się w jednym z nich. Taka procedura nazywa się walidacją krzyżową. Zajmiemy się nią na jednym z następnych laboratoriów.

Problem z accuracy

W przypadku niezbalansowanych klas miara accuracy nie oddaje dobrze jakości klasyfikatora. Żeby zobaczyć, dlaczego tak jest, wyobraź sobie dane rozmiaru 100 w których 99 obserwacji jest typu A, a jedna typu B. Klasyfikator, który w ogóle nie korzysta z danych, a po prostu przypisuje wszystkim obserwacjom klasę A, będzie miał 99% skuteczności!

Przydatnym narzędziem do dokładniejszego zbadania klasyfikatora jest tzw. macierz konfuzji (ang. confusion matrix), w której kolejne wiersze odpowiadają prawdziwym klasom, a kolejne kolumny - klasom zwróconym przez klasyfikator. Komórka $m_{i,j}$ macierzy konfuzji $M$ zawiera liczbę obserwacji z klasy $i$ zaklasyfikowanych jako klasa $j$.

Miarami, które lepiej radzą sobie z niezbalansowanymi danymi, jest precision oraz recall. To pierwsze jest miarą tego, na ile możemy wierzyć klasyfikatorowi jeśli zwraca on określoną klasę. To drugie mierzy, jak dobrze klasyfikator wychwytuje daną klasę z danych. Korzystając z macierzy konfuzji, możemy obliczyć precision dla klasy $i$ jako $$p_i = \frac{m_{i, i}}{\sum_{j = 1}^k m_{j, i}},$$ wartość recall dla klasy $i$ obliczamy natomiast jako $$r_i = \frac{m_{i, i}}{\sum_{j=1}^k m_{i, j}}.$$

Zadanie 4. Rozpatrz klasyfikator, który przypisuje wszystkim obserwacjom z przykładu klasę A, oraz taki, który przypisuje wszystkim klasę B. Jakie wartości $r_A, r_B, p_A, p_B$ będą miały oba klasyfikatory?

Zadanie 5. Utwórz macierz konfuzji dla wyników klasyfikatora kNN na zbiorze testowym z danych wine. Skorzystaj z funkcji table. Następnie oblicz precision oraz recall dla każdej klasy. Porównaj wyniki dla 3 wybranych wartości parametru $k$. Na podstawie otrzymanych wyników spróbuj oszacować odpowiedzi na następujące pytania:

• Jeśli klasyfikator twierdzi, że wino ma jakość 7, to jakie jest prawdopodobieństwo, że wino rzeczywiście ma taką jakość?
• Jeśli wino ma jakość 5, to jakie jest prawdopodobieństwo, że klasyfikator zaklasyfikuje je poprawnie?
• Czy klasyfikator lepiej klasyfikuje wina o rzadkich, czy o powszechnych jakościach? Która jakość wina jest poprawnie klasyfikowana najczęściej? Która klasa zwrócona przez klasyfikator jest najbardziej wiarygodna?
• Jaka jest szansa, że w rzeczywistości wino jest lepsze, niż twierdzi klasyfikator? A jaka, że gorsze?

Wskazówka. Do obliczenia precision oraz recall przydadzą się funkcje diag(), rowSums() oraz colSums(). Na przykład, mając macierz konfuzji w zmiennej C, do obliczenia precision dla każdej klasy wystarczy napisać diag(C)/colSums(C).