Przejdź do treści

Koła w zbożu – algorytmy klasyfikacji

Jednym z głównych zagadnień w analizie danych jest klasyfikacja elementów do wybranych grup, na podstawie właściwości opisujących elementy. W pakiecie R i jego bibliotekach znajdziemy gotowe rozwiązania, pytanie tylko którego użyć?

Zanim jednak coś poklasyfikujemy – zastanówmy się do czego to może być potrzebne?

Zastosowań jest bardzo dużo:

  • zaszeregowanie gatunków roślin na podstawie parametrów typu długość liścia (bardzo popularny zestaw danych iris opisujący pąki irysów trzech odmian)
  • nieco ryzykowne – określanie czy grzyb jest jadalny czy też nie
  • filtrowanie spamu na podstawie nadawcy i zawartości maila
  • określanie autora tekstu na podstawie samego tekstu (w uproszczeniu na podstawie częstości występowania słów – pojedynczych jak i zbitek wyrazów)
  • wykrywanie nadużyć w bankach lub firmach ubezpieczeniowych – tutaj ilość cech (parametrów określających np. transakcję kartą kredytową) jest ogromna
  • podział klientów sklepu na określone grupy na podstawie zawartości koszyków
  • i tak dalej, i tak dalej

My będziemy testować algorytmy klasyfikujące. Narysujemy sobie pięć “rozedrganych” kółek (precyzyjniej: okręgów) nachodzących na siebie (jak generator losowy pozwoli :-) i później dla każdego narysowanego punktu określimy do którego kółka należy. Coś, co widać gołym ludzkim okiem na obrazku nie zawsze jest takie łatwe do zobaczenia dla maszyny.

Post jest stricte edukacyjny, chyba niewiele ciekawych wniosków z danych tutaj wysnujemy. Chcę pokazać jakie są algorytmy (bez wchodzenia w ich szczegóły – klikaj w linki jeśli chcesz zgłębić wiedzę) i jak w najprostszej wersji użyć ich w R.
Jeśli Cię to trochę zniechęciło, to skroluj dalej, pooglądaj kolorowe okręgi. I to bez wychodzenia na pole (w sensie “w zboże”)!

Zaczynamy od przygotowania kółek. Danych.

Powyżej standardowo – biblioteki, losowe położenie kółek, i zgodne z matematyką wyliczenie punktów na płaszczyźnie należących do koła o zadanym promieniu i środku. Z matematyki (ze szkoły średniej) oczywiście pamiętamy, że do koła (właściwie okręgu – koło jest pełne w środku) należą punkty spełniające równanie

    \[(x-x_0)^2+(y-y_0)^2 = r^2\]

z czego można dojść do

    \[\begin{cases} x = x_0 + r \cos \alpha \\ y = y_0 + r \sin \alpha \end{cases}\]

gdzie \alpha \in [0,\ 2\pi).

Ale dość szpanowania matematyką na poziomie matury (mam nadzieję… że maturzyści tego jeszcze się uczą).

Wybierzmy sobie 70% punktów z każdego okręgu (dlatego w pętli – żeby wybierać po 70% z każdego, a nie po prostu 70% danych) jako dane treningowe i narysujmy nasze okręgi (dalej zwane potocznie kołami :) – te z kompletnych danych oraz te “treningowe”.

Jak widać jedno (to z prawej) koło (okrąg! jak rany…) takie bardziej rzadkie niż drugie. Tak ma być.

k-średnich

W dużym uproszczeniu algorytm szuka n_kol punktów-środków, od których pozostałe punkty są jak najmniej oddalone (taki “środek skupienia”). Później dla wszystkich punktów i środków oblicza wzajemne odległości punkt-środek. Punkt zostaje przypisany do grupy (jednej z n_kol), do której środka ma najbliżej.

Zobaczmy co wyszło:

Kolorem oznaczone jest dopasowanie według zadanego algorytmu, symbolem – oryginalny okrąg. Jak widać k-średnich przypisało punkty po odległościach od jakiegoś środka, a nie po okręgach.

Możemy teraz sprawdzić ile punktów “przeszło” w modelu z jednego koła do drugiego. Im mniej tym lepiej oczywiście.

W tabelce poniżej w wierszach mamy koła wymodelowane, w rzędach – koła oryginalne. Liczba na przecięciu mówi o tym ile punktów okręgu oryginalnego zawiera okrąg powstały w wyniku klasyfikacji.

Takie operacje będziemy powtarzać też dla kolejnych modeli.

1 2 3 4 5
1 59 64 3 55 0
2 47 52 30 31 21
3 55 1 40 42 43
4 40 0 45 29 67
5 0 0 61 120 0

Policzmy na ile dobrze dopasowaliśmy naszym modelem dane. Bez takiego wskaźnika nie uda się stwierdzić czy model jest dobry oraz który jest lepszy. Metod jest wiele, w przypadku kategoryzacji najprostszy to sprawdzenie ile punktów zostało dobrze zaklasyfikowanych w stosunku do wszystkich punktów. Matematycznie jest to suma wartości na przekątnej w powyższej tabeli (sum(diag(cm))) podzielona przez sumę wszystkich elementów tabeli (sum(cm)).

Dokładność dopasowania jaką osiągamy w przypadku k-średnich to 19.9%. Nie powala, ale to widać już na obrazku.

Gdyby koła były mniejsze i ciaśniej (o zbliżonych środkach) byłoby jeszcze gorzej. To fajny i stosunkowo szybki algorytm dla danych, których grupy są mocno rozrzuconych od siebie i jednocześnie elementy grup są dobrze skupione w ramach samej grupy. Coś jak winogrona w kiściach – każda kiść jest “zbita” z pojedynczych winogron, a same kiście są na tyle daleko od siebie, że można je łatwo odróżnić od siebie.

Są metody (np. PCA – po polsku analiza głównych składowych), które pozwalają znaleźć przekształcenie punktów do innej płaszczyzny, na której już algorytm k-średnich zadziała zdecydowanie lepiej. Kiedyś się tym zajmiemy.

Naiwny Bayes

Jak widać stworzenie modelu jest zupełnie banalne, i identyczne z k-średnimi. Tak samo będzie dla kolejnych.

Na czym polega naiwny Bayes? Na prawdopodobieństwie – na podstawie warunkowego prawdopodobieństwa dla znanych uwarunkowań określamy prawdopodobieństwo dla czegoś nowego. Opisuje to twierdzenie Bayesa:

    \[ P(A \mid B) = \frac{P(B \mid A) \, P(A)}{P(B)} \]

Popularne przykłady (np. opisane w Wikipedii) mówią o grypie (jeśli ktoś ma gorączkę i ból głowy to czy ma grypę? Skoro ileś procent osób z gorączką ma grypę i analogicznie dla bólu głowy) albo rozpoznaniu owoców (po kształcie, kolorze i smaku).

Co jest ważne przy twierdzeniu Bayesa to fakt, że dana “kombinacja” czynników musi zdarzyć się co najmniej raz (aby prawdopodobieństwo nie było zerowe). Sam algorytm jest szybki – dla nauczonych danych właściwe wystarczy operować na stablicowanych wartościach. A jak się sprawdza?

I jeszcze tabelka:

1 2 3 4 5
1 110 4 36 0 31
2 76 36 52 8 9
3 45 0 37 60 39
4 8 0 36 111 26
5 0 0 0 0 181

Dokładność dopasowania jaką osiągamy to 52.5%

Jest zdecydowanie lepiej. Ale to tylko nieco ponad połowa trafnych przypadków – trochę jak w rzucie monetą.

SVM (Supported Vector Machine)

Polska nazwa to maszyna wektorów wspierających lub nośnych.

Algorytm polega na znalezieniu takiej płaszczyzny rozdzielającej, dla której uda się znaleźć maksymalny margines (odległość punktów od płaszczyzny), dla których przeprowadzamy klasyfikację. Wówczas punkty z jednej strony marginesu należą do jednej klasy, a z drugiej – do drugiej.

1 2 3 4 5
1 128 7 16 0 30
2 47 79 47 6 2
3 0 3 138 1 39
4 0 3 37 117 24
5 0 2 0 0 179

Dokładność dopasowania jakę osiągamy to 70.8%. Niesamowite prawda? I to dość szybkie – algorytm ten stosowany jest w aparatach fotograficznych do rozpoznawania twarzy, co jest przydatne przy autofokusie na twarz.

Drzewa decyzyjne

Drzewko możemy sobie narysować. Dlatego drzewa są fajne – łatwo je zobrazować. I łatwo wytłumaczyć.

Drzewa decyzyjne to najprościej mówiąc przejście przez kolejne kroki, w których możemy wybrać – idziemy w lewo albo w prawo (warunek, który badamy jest spełniony albo nie).

Biblioteka tree jest jeszcze z innego powodu fajna (poza rysowaniem drzewek). Nie dostajemy zero-jedynkowych klasyfikacji, a prawdopodobieństwo dopasowania do określonej grupy. Zobaczmy:

1 2 3 4 5
830 10.2 0.4 13.3 6.6 69.5
819 10.2 0.4 13.3 6.6 69.5
738 10.2 0.4 13.3 6.6 69.5
611 0.0 41.5 9.4 43.4 5.7
438 10.2 0.4 13.3 6.6 69.5
440 10.2 0.4 13.3 6.6 69.5
141 50.0 50.0 0.0 0.0 0.0
84 53.6 46.4 0.0 0.0 0.0
245 53.6 46.4 0.0 0.0 0.0
434 10.2 0.4 13.3 6.6 69.5

Liczby w tabeli to procent prawdopodobieństwa przynależności określonego punktu (w wierszach) do grupy (w kolumnach).

My jednak potrzebujemy dokładnie powiedzieć do którego okręgu należy punkt. Przygotujemy więc funkcję, która wybierze grupę z maksymalnym prawdopodobieństwem.

Co z tego wszystkiego wychodzi?

Jak dokładnie przyjrzycie się schematowi drzewa to za przypisane do konkretnego okręgu odpowiada położenie punktu – niżej niż Y = -50.8 to okrąg 1. Dla innych wartości zaczyna się to rozgałęziać. Ale koniec końców można wyznaczyć proste (zarówno na osi X jak i Y), które rozdzielą nasz obraz na kilka prostokątnych obszarów. I to tak naprawdę te obszary określają docelową grupę.

1 2 3 4 5
1 152 1 2 0 26
2 105 36 5 34 1
3 9 33 91 14 34
4 8 0 24 132 17
5 0 0 0 3 178

Dokładność dopasowania jaką osiągamy tym razem to 65.1%

Drzewa łatwo “przetrenować” – wyniki są zbyt dopasowane do próbek uczących. Można drzewa “przycinać” albo zbudować las drzew, wybierając losową ilość próbek i losową ilość parametrów określających grupę. A w dodatku powiedzieć, że decydujemy w skończonej liczbie kroków, a nie do samego końca. Coś takiego robi kolejna metoda.

Random Forest czyli Losowy las drzew decyzyjnych

Wow! Wreszcie mamy coś, co przypomina okręgi, już po podziale! I to nawet takie dość dobrze pasujące do danych źródłowych:

1 2 3 4 5
1 154 16 1 4 6
2 9 164 5 3 0
3 1 2 166 8 4
4 3 2 3 168 5
5 3 0 3 2 173

Dokładność dopasowania jaką osiągamy to 91.2%. Dlatego lubię metodę random forest :) Z jednej strony daje naprawdę dobre wyniki, a z drugiej – jest stosunkowo prosta to wyjaśnienia (ot, dużo drzew decyzyjnych, losowo wybieranych). Przy dodatkowych parametrach można wynik jeszcze trochę poprawić.

XGBoost czyli objawienie konkursów Kaggle.com

XGBoost to dość młoda biblioteka, która w dużym uproszczeniu działa na budowie drzew decyzyjnych w różnych ujęciach cech, a następnie składa te drzewa razem. Taki bardziej rozbudowany random forest.

Na pierwszy rzut oka wygląda świetnie, tak dobrze jak random forest. Jak to wygląda w szczegółach?

1 2 3 4 5
1 155 17 1 4 4
2 11 162 5 3 0
3 2 3 162 11 3
4 3 3 1 168 6
5 4 1 2 2 172

Dokładność dopasowania jaką osiągamy to 90.5% czyli blisko poprzedniej metody. I tak to zazwyczaj jest, chociaż pewnie przy bardziej skomplikowanych danych wypada różnie.

Dla naszego zadania “do którego okręgu należy punkt?” zrobiłem symulację różnej ilości okręgów (za każdym razem losowych) z różną “gęstością” punktów w okręgu obie metody dały podobne (najwyższe) wyniki, właściwie bez wskazania zwycięzcy. Jednak jestem gotów uwierzyć w to co widać po wynikach na Kaggle – dla bardziej skomplikowanych (większa ilość danych) zbiorów XGBoost daje lepsze efekty. Niewiele, ale jednak.

Podsumowanie metod

Dla przypomnienia wszystkie wyniki dokładności dopasowania:

  • kmeans – 19.9%
  • naive Bayes – 52.5%
  • SVM – 70.8%
  • Tree – 65.1%
  • Random Forest – 91.2%
  • XGBoost – 90.5%

K-średnich zdecydowanie najsłabiej, lasy losowe (XGBoost to w zasadzie ich odmiana) najlepiej.

Na koniec ciekawostka – wpis ten zacząłem pisać jeszcze w lutym, ale ciekawsze dane (między innymi Oscary) były bardziej na czasie niż teoria. Ostatnio trafiłem na blog Mateusza Grzyba, na którym możecie przeczytać znakomite uzupełnienie tego co już wiecie.

5 komentarzy do “Koła w zbożu – algorytmy klasyfikacji”

  1. Fajny artykuł. Wczytuję się w resztę treści bloga i… jest świetnie! :)
    Dodane do RSS, a więc będę zaglądać regularnie :)

  2. Pingback: Nowa Europa (według k-means) | Łukasz Prokulski

  3. Pingback: MNIST dataset – sieci neuronowe, część 1 | Łukasz Prokulski

  4. Fajny i rozbudowany artykuł! Zastanawia mnie natomiast, czy nie sensowniej było by użyć K najbliższych sąsiadów zamiast K-średnich ;) – no bo ten pierwszy nieco lepiej nadaje się do klasyfikacji. Ale w sumie to pewnie była kwestia wyboru :).

    Dzięki!

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *