I. Metryka odległości
Po pierwsze, liczba cech (kolumn) w zbiorze danych nie jest czynnikiem przy wyborze metryki odległości do użycia w kNN. Istnieje wiele opublikowanych badań skierowanych właśnie na to pytanie, a zwykłe podstawy porównania to:
podstawowy rozkład statystyczny Twoich danych;
związek między cechami, które składają się na Twoje dane (czy są one niezależne - tj. jak wygląda macierz kowariancji); i
przestrzeń współrzędnych, z której uzyskano dane.
Jeśli nie masz wcześniejszej wiedzy na temat dystrybucji, z których pobrano próbki, co najmniej jedno (dobrze udokumentowane i dokładne) badanie wykazało, że odległość euklidesowa jest najlepszym wyborem.
Metryka YEuklidesa stosowana w ogromnych mechanizmach rekomendacji internetowych, a także w bieżących badaniach naukowych. Odległości obliczane przez Euklidesa mają znaczenie intuicyjne, a skale obliczeniowe - tj. Odległość euklidesowa jest obliczana w ten sam sposób, niezależnie od tego, czy dwa punkty są w dwóch wymiarach, czy w dwudziestu dwóch wymiarach.
U mnie zawiodło tylko kilka razy, w każdym z tych przypadków odległość euklidesowa zawiodła, ponieważ podstawowy (kartezjański) układ współrzędnych był złym wyborem. Zwykle rozpoznajesz to, ponieważ na przykład długości ścieżek (odległości) nie są już sumowane - np. Gdy przestrzeń metryczna jest szachownicą, odległość Manhattanu jest lepsza niż euklidesowa, podobnie, gdy przestrzenią metryczną jest Ziemia, a twoje odległości są trans -loty kontynentalne, dobrym pomysłem jest miara odległości odpowiednia dla układu współrzędnych biegunowych (np. z Londynu do Wiednia to 2,5 godziny, z Wiednia do Sankt Petersburga to kolejne 3 godziny, mniej więcej w tym samym kierunku, ale z Londynu do St. . Petersburg nie trwa 5,5 godziny, zamiast tego jest nieco ponad 3 godziny).
Ale poza przypadkami, w których dane należą do niekartezjańskiego układu współrzędnych, wybór metryki odległości zwykle nie jest istotny. (Zobacz ten wpis na blogu od studenta CS, porównując kilka metryk odległości badając ich wpływ na KNN klasyfikatora - chi kwadrat daje najlepsze rezultaty, ale różnice nie są duże; Bardziej kompleksowe badanie jest w pracy naukowej, Studium porównawcze Funkcje odległości dla najbliższych sąsiadów - Mahalanobis (zasadniczo euklidesowy znormalizowany w celu uwzględnienia kowariancji wymiarów) był najlepszy w tym badaniu.
Jedno ważne zastrzeżenie: aby obliczenia metryki odległości miały sens, należy zmienić skalęTwoje dane - rzadko jest możliwe zbudowanie modelu kNN w celu wygenerowania dokładnych prognoz bez tego. Na przykład, jeśli budujesz model kNN do przewidywania wyników sportowych, a twoje oczekiwane zmienne to wzrost (cm), waga (kg), tłuszcz (%) i tętno spoczynkowe (uderzenia na minutę), typowy punkt danych może wyglądają mniej więcej tak: [180.4, 66.1, 11.3, 71]. Oczywiście obliczanie odległości będzie zdominowane przez wzrost, podczas gdy udział procentowej zawartości tłuszczu w organizmie będzie prawie nieistotny. Innymi słowy, gdyby zamiast tego dane były podawane w inny sposób, tak aby masa ciała była podawana w gramach, a nie w kilogramach, wówczas pierwotna wartość 86,1 wynosiłaby 86,100, co miałoby duży wpływ na Twoje wyniki, czyli dokładnie to, czego nie podajesz nie chcę.
X_new = (X_old - mu) / sigma
II. Struktura danych
Jeśli obawiasz się wydajności struktury drzewa kd, Tesselacja Voronoi jest koncepcyjnie prostym kontenerem, ale znacznie poprawi wydajność i skaluje się lepiej niż kd-Trees.
Nie jest to najczęstszy sposób utrwalania danych szkoleniowych kNN, chociaż zastosowanie VT w tym celu, a także wynikające z tego korzyści w zakresie wydajności, są dobrze udokumentowane (patrz np. Ten raport Microsoft Research ). Praktyczne znaczenie tego jest takie, że jeśli używasz języka „głównego nurtu” (np. W TIOBE Index ), powinieneś znaleźć bibliotekę do wykonywania VT. Wiem, że w Pythonie i R jest wiele opcji dla każdego języka (np. Pakiet voronoi dla R dostępny w CRAN )
Używanie VT dla kNN działa tak:
Ze swoich danych wybierz losowo punkty - to są twoje centra Woronoi. Komórka Voronoi zawiera wszystkie sąsiednie punkty, które są najbliżej każdego centrum. Wyobraź sobie, że przypisujesz inny kolor do każdego z ośrodków Woronoja, tak aby każdy punkt przypisany do danego środka był pomalowany na ten kolor. Dopóki masz wystarczającą gęstość, zrobienie tego ładnie pokaże granice każdego centrum Woronoja (jako granicę oddzielającą dwa kolory.
Jak wybrać centra Voronoi? Używam dwóch prostopadłych prowadnic. Po losowym wybraniu punktów w oblicz VT dla swoich danych treningowych. Następnie sprawdź liczbę punktów danych przypisanych do każdego centrum Voronoi - te wartości powinny być mniej więcej takie same (biorąc pod uwagę jednolitą gęstość punktów w całej przestrzeni danych). W dwóch wymiarach spowodowałoby to VT z płytkami tego samego rozmiaru. To jest pierwsza zasada, tutaj druga. Wybierz w przez iterację - uruchom algorytm kNN z parametrem zmiennym w i zmierz wydajność (czas wymagany do zwrócenia prognozy przez zapytanie VT).
Więc wyobraź sobie, że masz milion punktów danych ..... Gdyby punkty były utrwalone w zwykłej strukturze danych 2D lub w drzewie kd, wykonałbyś średnio kilka milionów obliczeń odległości dla każdegonowe punkty danych, których zmienną odpowiedzi chcesz przewidzieć. Oczywiście obliczenia te są wykonywane na jednym zestawie danych. W przypadku V / T wyszukiwanie najbliższego sąsiada jest przeprowadzane w dwóch krokach, jeden po drugim, na dwóch różnych populacjach danych - najpierw względem centrów Woronoja, a po znalezieniu najbliższego centrum punkty wewnątrz komórki odpowiadające to centrum jest przeszukiwane w celu znalezienia rzeczywistego najbliższego sąsiada (poprzez kolejne obliczenia odległości). W połączeniu te dwa wyszukiwania są znacznie szybsze niż pojedyncze wyszukiwanie siłowe. Łatwo to zauważyć: dla 1 mln punktów danych załóżmy, że wybierasz 250 centrów Voronoi do tesselacji przestrzeni danych. Średnio każda komórka Voronoi będzie miała 4000 punktów danych. Zamiast więc wykonywać średnio 500 000 obliczeń odległości (brutalna siła), wykonujesz znacznie mniej, średnio zaledwie 125 + 2000.
III. Obliczanie wyniku (przewidywana zmienna odpowiedzi)
Obliczanie przewidywanej wartości na podstawie zestawu danych szkoleniowych kNN obejmuje dwa kroki. Pierwszą jest identyfikacja n, czyli liczba najbliższych sąsiadów, których należy użyć do obliczenia. Drugi to sposób ważenia ich wkładu w przewidywaną wartość.
W / r / t pierwszej składowej, możesz określić najlepszą wartość n rozwiązując problem optymalizacji (bardzo podobny do optymalizacji metodą najmniejszych kwadratów). Taka jest teoria; w praktyce większość ludzi po prostu używa n = 3. W każdym razie łatwo jest uruchomić algorytm kNN na zestawie instancji testowych (w celu obliczenia przewidywanych wartości) dla n = 1, n = 2, n = 3 itd. I wykreślić błąd jako funkcję n. Jeśli chcesz, aby na początku pojawiła się wiarygodna wartość n, ponownie użyj n = 3.
Drugi składnik to sposób ważenia udziału każdego z sąsiadów (zakładając, że n> 1).
Najprostsza technika ważenia polega na pomnożeniu każdego sąsiada przez współczynnik ważenia, który jest po prostu 1 / (odległość * K) lub odwrotnością odległości od tego sąsiada do instancji testowej, często pomnożonej przez pewną empirycznie wyprowadzoną stałą K. nie jestem fanem tej techniki, ponieważ często przeciąża ona najbliższych sąsiadów (i jednocześnie niedocenia tych bardziej odległych); Znaczenie tego polega na tym, że dana prognoza może być prawie całkowicie zależna od pojedynczego sąsiada, co z kolei zwiększa wrażliwość algorytmu na szum.
Konieczną lepszą funkcją ważenia, która zasadniczo omija to ograniczenie, jest funkcja Gaussa , która w Pythonie wygląda następująco:
def weight_gauss(dist, sig=2.0) :
return math.e**(-dist**2/(2*sig**2))
Aby obliczyć przewidywaną wartość za pomocą kodu kNN, należy zidentyfikować n najbliższych sąsiadów punktu danych, których zmienną odpowiedzi chcesz przewidzieć („instancja testowa”), a następnie wywołać funkcję weight_gauss, raz dla każdego z n sąsiadów, przekazując w odległości między każdym sąsiadem a punktem testowym. Funkcja ta zwraca wagę każdego sąsiada, która jest następnie używana jako współczynnik tego sąsiada w obliczaniu średniej ważonej.