© Copyright StatSoft, Inc., 1984-2011
Przeszukaj Internetowy Podręcznik Statystyki
K-najbliższych sąsiadów


Klasyfikacja

Zobaczmy jak działa metoda K-najbliższych sąsiadów na przykładzie zadania polegającego na zaklasyfikowaniu nowego obiektu, pośród pewnej liczby obiektów znanych. Sytuację taką ilustruje poniższy rysunek, gdzie mamy przypadki dodatnie i ujemne oraz nowy punkt, oznaczony na czerwono. Zadanie polega na zaklasyfikowaniu nowego obiektu do plusów lub minusów, na bazie tego, z kim sąsiaduje.

Zacznijmy od rozpatrzenia przypadku jednego, najbliższego sąsiada. Widać, że najbliżej czerwonego punktu jest plus, tak więc nowy przypadek zostanie zaklasyfikowany do plusów. Zwiększmy teraz liczbę najbliższych sąsiadów do dwóch. Niestety, jest kłopot, drugi sąsiad to minus, więc plusy i minusy występują w tej samej ilości, nikt nie ma przewagi. Zwiększmy dalej liczbę najbliższych sąsiadów, do pięciu. Są to przypadki znajdujące się wewnątrz kółka na rysunku. Jest tam przewaga minusów, więc nowy przypadek oceniamy jako minus.

Regresja

Uogólnijmy koncepcję K-najbliższych sąsiadów tak, by można się było zająć również regresją. W regresji przewidujemy wartość ciągłej zmiennej zależnej na bazie znanych wartości zmiennych niezależnych. Zacznijmy od pokazanego wyżej wykresu. Jest tam kilka punktów zaznaczonych zielonymi kwadratami odpowiadających zależności funkcyjnej zmiennej zależnej y od zmiennej niezależnej x. Funkcję tę ilustruje czerwona linia (sinusoida). Mamy więc danych kilka "przykładowych" punktów, a podać musimy wartość y dla dowolnego x.

Zacznijmy znowu od pojedynczego najbliższego sąsiada. Najbliżej nowego X znajduje się punkt o odciętej x4. Tak więc, jako wartość dla nowego X przyjęta będzie wartość (rzędna) odpowiadająca x4, czyli y4. Oznacza to, że dla jednego najbliższego sąsiada wynikiem jest

Y = y4

Rozpatrzmy dalej metodę dwóch najbliższych sąsiadów. W tym wypadku szukamy dwóch punktów mających najbliżej do X. Są to punkty o wartościach rzędnych y3 i y4. Biorąc średnią z dwóch wartości, otrzymujemy:

W podobny sposób postępujemy przy dowolnej liczbie K najbliższych sąsiadów. Wartość Y zmiennej zależnej otrzymujemy jako średnią z wartości zmiennej zależnej dla K punktów o wartościach zmiennych niezależnych X najbliższych nowemu X-owi.


Indeks

Szczegóły techniczne

Metoda K-najbliższych sąsiadów stosuje pamięciowy (memory-based) model zdefiniowany przez zestaw "przykładowych" przypadków o znanych wartościach zmiennej wyjściowej (i, oczywiście zmiennych wejściowych). Zarówno zmienne zależne jak i niezależne mogą być ciągłe i skategoryzowane. Przy ciągłej zmiennej wyjściowej wykonujemy regresję, przy skategoryzowanej, klasyfikację. Metoda K-najbliższych sąsiadów realizuje więc oba zadania.

Wartość zmiennej wyjściowej (zależnej) dla nowego punktu oceniamy na podstawie zestawu K "przykładowych" punktów. Metoda K-najbliższych sąsiadów poszukuje tych K "przykładów" w najbliższym sąsiedztwie nowego punktu, stąd nazwa metody. W przypadku regresji jako wynik bierze się średnią z K przykładowych punktów, przy klasyfikacji decyduje, do której klasy należy większość punktów (głosowanie).

Wybór liczby K ma duże znaczenie. Jest to podstawowy parametr metody decydujący o jakości predykcji. Parametr ten może być traktowany jak pewna miara stopnia wygładzania danych. Przy małym K będziemy mieli dużą zmienność predykcji. Jednak przy dużym K możemy otrzymywać znaczące, systematyczne przesunięcia wartości predykcji. Tak więc, K powinno być na tyle duże by minimalizować prawdopodobieństwo błędnych klasyfikacji, ale na tyle małe, by K najbliższych sąsiadów było dostatecznie bliskimi sąsiadami nowego punktu. Jak zawsze przy wygładzaniu, istnieje pewne optimum - złoty środek pomiędzy nadmierną zmiennością a systematycznymi, istotnymi odchyleniami. Metoda K-najbliższych sąsiadów proponuje optymalną wartość K na bazie metody sprawdzianu krzyżowego (Bishop, 1995).


Indeks

Sprawdzian krzyżowy

Sprawdzian krzyżowy jest szeroko stosowaną techniką, pozwalającą oszacować nieznane wartości parametrów modelu. Obecnie przedyskutujemy stosowalność tej techniki do znajdowania optymalnej wartości K.

Główna idea polega na tym, że dzieli się dane na v rozłącznych części (wybranych losowo). Dla ustalonego wstępnie K wykonuje się analizę, by znaleźć predykcję dla v-tej grupy danych (używając pozostałych v-1 części danych jako przypadków "przykładowych"). Ponieważ, w istocie, dysponujemy wartościami zmiennej zależnej w grupie danych, dla których wykonano predykcję, możemy obliczyć błąd predykcji. W przypadku regresji obliczamy sumę kwadratów reszt, przy klasyfikacji obliczamy dokładność, czyli procent przypadków zaklasyfikowanych poprawnie. Powtarzamy procedurę dla wszystkich v segmentów danych. Na końcu v cykli uśredniamy błędy, otrzymując miarę jakości modelu. Powyższe powtarzamy dla różnych K, wybierając jako najlepsze to K, dla którego otrzymujemy najlepszą jakość modelu. Zauważmy, że algorytm sprawdzianu krzyżowego wymaga sporo obliczeń i musimy być przygotowani, że zajmie on trochę czasu, szczególnie przy większych zbiorach danych. Zawsze możemy jednak samodzielnie wybrać K, na podstawie wcześniej zdobytego doświadczenia, z podobnymi danymi.

Indeks

Miara odległości

Jak to już było omawiane, wynik otrzymujemy na bazie K najbliższych sąsiadów nowego punktu. Potrzebujemy więc jakiejś miary bliskości punktów, czyli miary odległości pomiędzy dwoma przypadkami danych. Jedną z najprostszych jest miara Euklidesowa. Inne to: kwadrat miary euklidesowej, Manhattan (miejska) i Czebyszewa:

gdzie x i p to, odpowiednio nowy przypadek i jeden z przypadków "przykładowych".

Predykcja metodą K-najbliższych sąsiadów

Po wybraniu K, gotowi jesteśmy do wykonania predykcji metodą K-najbliższych sąsiadów. W wypadku regresji obliczamy średnią dla K-najbliższych sąsiadów.

gdzie yi jest wartością zmiennej wyjściowej dla i-tego przypadku "przykładowego", a y jest wartością zmiennej wyjściowej dla nowego przypadku. Inaczej niż przy regresji, w wypadku klasyfikacji predykcja bazuje na większościowym "głosowaniu" nad kategorią.

Uwaga. W przypadku klasyfikacji binarnej, nieparzystych wartości y = 1,3,5 używa się do rozstrzygania remisów, czyli równowagi dwóch klas.

Jak dotąd, metodę K-najbliższych sąsiadów rozpatrywaliśmy w najprostszym przypadku, w którym wszystkie K punkty mają taki sam wpływ na wynik. Tym czasem, niektóre z nich są bliższe nowemu punktowi, a inne dalsze. Te bliższe powinny mieć większe znaczenie. Tak więc, alternatywnie (Shepard 1968) możemy użyć dużej liczby K, albo i użyć wszystkich punktów, jednak większą wagę nadając punktom bliższym. Zatosować możemy więc wagi zależne od odległości.

Ważenie odległościami

Metoda K-najbliższych sąsiadów bazuje na intuicyjnym założeniu, że bliskie obiekty są podobne. Sensowne więc będzie różne traktowanie K najbliższych sąsiadów, zależnie od ich odległości od zadanego nowego, interesującego nas punktu. Oczywiście te bliższe powinny mieć większy wpływ. Osiągnąć to można wprowadzając wagi W, zależne od wzajemnej odległości punktów danych, mierzonej miarą D:

gdzie D(x, pi ) jest miarą odległości pomiędzy nowym punktem x, a punktem pi - i-tym punktem "przykładowym". Powyżej określone wagi spełniają warunek:

Tak więc, w wypadku regresji:

Przy klasyfikacji, szuka się maksimum wartości dla wszystkich klas.

Z powyższego wynika, że przy K>1, odchylenie standardowe predykcji, przy regresji, obliczyć można wg wzoru:

Indeks






© Copyright StatSoft, Inc., 1984-2011
STATISTICA is a trademark of StatSoft, Inc.