Wykład 9

Schematy testowania klasyfikatorów.
Algorytm k najbliższych sąsiadów.

Streszczenie

Rozdział obejmuje ogólne informacje o zasadach weryfikowania jakości i testowania klasyfikatorów, służących predykcji, czy klasyfikacji nowych przypadków na podstawie wiedzy o przypadkach znanych. W dalszej części, wykład koncentruje się na przykładowym, stosunkowo prostym w zrozumieniu i implementacji, klasyfikatorze opartym na badaniu zachowania obiektów znanych (treningowych) pozostających w najbliższym sąsiedztwie z obiektami nowymi (testowymi).


Ogólny schemat

Rozpatrzmy zbiór danych, dla ktorego obiektów znane są zarówno wartości cech warunkowych jak i decyzyjnych. Możemy zatem powiedzieć, że zbiór podzielony jest na klasy decyzyjne i że dla każdego obiektu znamy jego przyporządkowanie do którejś z klas decyzyjnych. Rozpatrzmy następnie pewien algorytm klasyfikujący, który przypisuje nowe obiekty do klas decyzyjnych, poprzez analizę wartości tych obiektów dla cech warunkowych. Problem, który stawiamy w niniejszym rozdziale, to zbadać skuteczność algorytmu na tych danych. Jako kryterium skuteczności można zaś przyjąć liczbę (procent) prawidłowo rozpoznanych obiektów testowych, nie biorących poprzednio udziału w treningu.

Wybór próbki testowej

Testowanie algorytmu wykonujemy, gdy chcemy porównać jego wyniki z innymi, ale również podczas optymalizacji parametrów samego algorytmu, np. w celu wyboru właściwej opcji. Wielkość próbki testowej nie powinna być zbyt mała, jeśli np. chcemy uzyskać dokładność 0,1%, próbka powinna mieć ponad 1000 obiektów. Techniki statystyczne pomagają nam oszacować wielkość próbki do porównań na danym poziomie istotności. Możemy podzielić dane na część treningową (zwykle ok. 70%) i testową. Dane używane do testowania nie mogą być użyte do trenowania klasyfikatora. Niektóre dane referencyjne mają z góry zdefiniowaną część testową. Obiektów z tej części możemy użyć tylko raz, do określenia końcowej jakości naszego klasyfikatora.

Warto zauważyć, iż nie rozważamy tu problemu akwizycji danych, która poprzedza podział danych na próbki treningowe i testowe. Odpowiedni sposób zgromadzenia i przetworzenia danych to klucz do wytrenowania dobrego klasyfikatora. Zaś odpowiedni podział danych na treningowe i testowe zapewnia odpowiednią weryfikację jakości klasyfikatora przed jego użyciem w praktyce.

Schemat CV-n

Innym sposobem testowania klasyfikatora, szczególnie przydatnym jeśli sformułowaniu problemu klasyfikacyjnego nie towarzyszy naturalny podział na próbki treningowe i testowe, jest walidacja krzyżowa (ang. cross-validation). Przy danym parametrze n (który na ogół ustawiany jest jako 5 lub 10), dzielimy dane losowo na n równych podzbiorów. (Czasem też zakłada się, iż rozkłady występowania poszczególnych klas decyzyjnych w poszczególnych podzbiorach są zbliżone do siebie.) Następnie, w pętli, każdy z kolejnych n podzbiorów przyjmuje się jako testowy, zaś pozostałe podzbiory tworzą próbkę treningową. Zauważmy, że choć metoda ta jest bardziej kosztowna obliczeniowo, z powodu powtarzania fazy treningu i testowania klasyfikatora n razy, to uśrednione wyniki jakości stają sie bardziej stabilne i wiarygodne. Dzieje się tak dlatego, że wymienne traktowanie danych jako składowych treningowych i testowych obniża ryzyko otrzymania wyniku niezgodnego z rzeczywistością, spowodowanego niefortunnym losowym podziałem danych.

Metoda Leave-One-Out

W tej metodzie, zbiór treningowy jest wykorzystywany w całości jako zbiór testowy. Mianowicie, dla każdego obiektu o konstruujemy klasyfikator wykorzystujący wszystkie obiekty z wyjątkiem o. Obiekt o klasyfikujemy i zapamiętujemy wynik. Po przetestowaniu wszystkich obiektów sumujemy wyniki.

Metoda Leave-One-Out jest zwykle bardzo wolna, jednak można ją stosować w sytuacjach, gdy trening klasyfikatora jest czynnością bardzo prostą (np. naiwny klasyfikator bayesowski - wystarczy tak zmodyfikować prawdopodobieństwa, by ominąć obiekt o).

Leave-One-Out jest równoważne CV-n dla n równego liczbie obiektów w zbiorze. Intuicja podpowiada, że dla dużych n jakość klasyfikacji będzie lepsza, ponieważ w każym przebiegu wykorzystujemy więcej danych (a zatem informacji) do treningu. W niektórych przypadkach, Leave-One-Out nie jest więc uważany za wystarczająco „wymagający” sposób weryfikowania jakości klasyfikatorów. Z drugiej strony, jeśli obiektów w całych danych jest mało, to CV-n dla zbyt małych ustawień n przestaje mieć w praktyce sens.

Klasyfikacja oparta na odległości

Klasyfikacja obiektów testowych odbywa się poprzez ich analogie z danymi treningowymi. Analogie takie można rozumieć bezpośrednio, porównując obiekty ze sobą, lub pośrednio, ucząc się najpierw na podstawie danych treningowych pewnego modelu decyzyjnego, a następnie stosowanie go do klasyfikacji danych testowych w ustalony sposób.

Oba powyższe sposoby klasyfikacji są często oparte na odległościach (bliskościach) pomiędzy obiektami. Odległości są definiowane w oparciu o cechy warunkowe, znane zarówno dla przypadków treningowych jak i nowych. (W ten sposób możemy porównywać te dwa rodzaje obiektów w trakcie klasyfikacji.) Odległości mogą być definiowane na wiele sposobów, w zależności od typu cech. Oczywiście, najbardziej naturalną odległość uzyskuje się dla cech rzeczywistych. Załóżmy zatem, że analizowany zbiór danych zawiera obiekty opisane własnie wektorami liczb (cech) rzeczywistych:

Będziemy zakładać, że obiekty podobne z punktu widzenia wszystkich cech mają tę samą decyzję, co odpowiada w praktyce założeniu, że cechy warunkowe, na podstawie których dokonujemy klasyfikacji, są dobrze dobrane dla danego problemu. Podobieństwo obiektów określa odległość w przestrzeni Rm, czyli metryka. Przykładowo:

Problem klasyfikacji można sprowadzić do pytania: jaka jest najbardziej prawdopodobna decyzja w pewnym punkcie x* przestrzeni?

Metoda:

- ustalamy pewne otoczenie punktu x*,

- konstruujemy histogram decyzji,

- wybieramy największą wartość histogramu.

Algorytm k-NN

Ustalamy wartość k (najlepiej liczbę nieparzystą, zwykle ok. 5-15).

Dla każdego obiektu testowego o*:

-  wyznaczamy odległość r(o*,x) pomiędzy o* i każdym obiektem treningowym x,

-  znajdujemy k obiektów treningowych najbliższych o*,

-  wśród wartości decyzji odpowiadających tym obiektom wykonujemy głosowanie,

-  najczęściej występującą wartość decyzji przypisujemy obiektowi o*.

Uwagi techniczne:

Parametr k możemy dobrać eksperymentalnie. Licząc na próbce testowej wyniki dla pewnego k, otrzymujemy przy okazji wyniki dla wszystkich wartości mniejszych.

Czas uczenia (w wersji podstawowej algorytmu) jest bardzo krótki, gdyż nauka polega na zapamiętaniu całej próbki treningowej. Łatwo stosować metodę leave-one-out.

Klasyfikacja nowych przypadków jest dosyć powolna. Sposoby na przyspieszenie:

-  selekcja obiektów – wybór pewnego podzbioru dającego zbliżone wyniki klasyfikacji

-  podział zbioru obiektów na podzbiory i przeszukiwanie tylko niektórych z nich.

Przykład:

Powyższy rysunek pokazuje granice wyznaczone między klasami decyzyjnymi dla tych samych danych, generowane przez algorytm najbliższych sąsiadów dla k=1 i k=3. Pod tym linkiem znajduje się interaktywna wersja klasyfikatora k-NN pozwalająca porównać dla losowych danych i wielu klas decyzyjnych obszary klasyfikowane za pomoca tego algorytmu. (Aby wylosować punkty na nowo, kliknij pasek z liczbą obiektów. Może wymagać zezwolenia na zawartość aktywną.)

Modyfikacja metryki

Wadą algorytmu k-NN jest jednakowe (często nieuprawnione) traktowanie wszystkich wymiarów. Np. jeśli wśród cech będziemy mieli wiek pacjenta i temperaturę ciała, wówczas różnica między rówieśnikami z temperaturą 37°C i 41°C jest dla algorytmu diagnozującego mniejsza, niż między 45-latkiem a 50-latkiem o jednakowej temperaturze.

Sposób radzenia sobie z tym problemem polega na wprowadzeniu dodatkowych wag związanych z wymiarami:

Przykład:


Strona przygotowana przez Dominika Ślęzaka i Jakuba Wróblewskiego, 2006.