Reguła najbliższego sąsiada. Analiza skupień najbliższego sąsiedztwa.

meto1

 

Reguła najbliższego sąsiada

Metoda najbliższego sąsiada jest jedną z metod rozpoznawania obrazów, która znalazła zastosowanie w sprawdzaniu wiarygodności kredytowej. Reguła ta klasyfikuje przy pomocy określonej miary odległości między obiektami. Badany obiekt przyporządkowujemy do klasy, do której należy jego k najbliższych są-siadów (odległości mierzymy za pomocą wybranej miary metrycznej). Jest to metoda nieparametryczna ponieważ nie estymujemy tutaj żadnych parametrów a o tym, do której grupy zakwalifikować nowego klienta, wnioskujemy na podstawie zebranego zbioru treningowego.

Zacznijmy od zdefiniowania odległości Euklidesowej między dwoma wektorami na płaszczyźnie. Załóżmy, że mamy dane dwa wektory x0 i x1. Odległość między nimi jest dana następującym wzorem:

1 (1)
d(x0, x1) = [(x0x1)T (x0x1)] 2

Załóżmy że w zbiorze treningowym mamy dane n punktów x1, x2, …, xn, którym odpowiadają wartości y1, y2, …yn. Naszym zadaniem jest wyznaczenie wartości y0 dla badanego punktu x0 o podanych współrzędnych. Przyjmijmy oznaczenie: d1 = d(x0, x1), d2 = d(x0, x2),…,dn = d(x0, xn) i niech dn > dn−1 > … > d2 > d1. Wtedy estymator y0 przedstawia się następująco:

yˆ0 = y1 gdy K=1 (2)
yˆ0 = y1 + y2 gdy K=2 (3)
 2
yˆ0 =  1k ∑yi gdy K=k (4)
 k

i=1

Załóżmy, że zbiór treningowy {(y1, x1), (y2, x2), .., (yn, xn)} możemy podzielić na J podzbiorów ze względu na wartość yi. Zadanie będzie polegało na zakwalifikowaniu (y0, x0) do jednego z tych podzbiorów. W 1996 roku T.Hastie i R.Tibshirani opisali w swojej pracy metodę zwaną DANN. Polega ona na uwzględnieniu w odległości euklidesowej dodatkowej macierzy uwzględniającej położenia punktów względem poszczególnych wybranych wcześniej j klas. W tej metodzie di jest następującej postaci:

1 (5)
d(x0, xi) = [(x0xi)T Σ(x0xi)] 2

Z badań przeprowadzonych przez Hastie i Tibshirani wynika, że jedna iteracja ich algorytmu jest już wystarczająca, kolejne nie poprawiają wyniku. W 2002 roku C.C.Holmes i N.M.Adams wprowadzili metodę zwaną BANN, która do estymacji wartości zmiennej y0 wykorzystywała statystykę Bayesowską (metodę MCMC oraz algorytm Metropolisa-Hastingsa). Autorzy R.Guo i S.Chakraborty porównali metody standardową k-NN, DANN oraz BANN i na podstawie wielu przeprowadzonych eksperymentów doszli do wniosku, że najlepsze wyniki daje metoda BANN. Jest to zapewne spowodowane w dużej mierze jej elastycznością – zmienne k i km nie są dobierane na sztywno. Wyznacza się je maksymalizując rozkład a posteriori metodą MCMC. Metody bayesowskie znalazły w ostatnich latach szerokie zastosowanie (m.in. w medycynie i genetyce) i mimo swojej złożoności są kuszącą alternatywną dla statystyki klasycznej.

Autorem tekstu jest Marta Mrozek.

Więcej info na:

Analiza skupień. Segmentacja i grupowanie.
10 algorytmów uczenia maszynowego

Analiza skupien najblizszego sasiedztwa k- nearest neighbors

Propensity score matching statystyczny wpływ netto zmiennej niezależnej na zmienna zalezną