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) = [(x0 − x1)T (x0 − x1)] 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) = [(x0 − xi)T Σ(x0 − xi)] 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ą