GeeksforGeeks (Polski)

K-Nearest Neighbors to jeden z najbardziej podstawowych, ale niezbędnych algorytmów klasyfikacji w uczeniu maszynowym. Należy do nadzorowanej domeny uczenia się i znajduje intensywne zastosowanie w rozpoznawaniu wzorców, eksploracji danych i wykrywaniu włamań.

Jest powszechnie używany w rzeczywistych scenariuszach, ponieważ jest nieparametryczny, co oznacza, że nie powoduje wszelkie podstawowe założenia dotyczące dystrybucji danych (w przeciwieństwie do innych algorytmów, takich jak GMM, które zakładają rozkład Gaussa podanych danych).

Mamy pewne wcześniejsze dane (zwane również danymi treningowymi), które klasyfikuje współrzędne w grupy identyfikowane przez atrybut.

Jako przykład rozważ poniższą tabelę punktów danych zawierającą dwie cechy:

Teraz, biorąc pod uwagę inny zestaw punktów danych ( zwane również danymi testowymi), przypisz te punkty do grupy, analizując zbiór uczący. Zwróć uwagę, że niesklasyfikowane punkty są oznaczone jako „białe”.

Intuicja
Jeśli narysujemy te punkty na wykresie, być może uda nam się zlokalizować pewne skupienia lub grupy. Teraz, mając niesklasyfikowany punkt, możemy przypisać go do grupy, obserwując, do jakiej grupy należą jego najbliżsi sąsiedzi. Oznacza to, że punkt znajdujący się blisko grupy punktów sklasyfikowanych jako „Czerwony” ma większe prawdopodobieństwo, że zostanie sklasyfikowany jako „Czerwony”.

Intuicyjnie widzimy, że pierwszy punkt (2,5, 7) powinien być sklasyfikowany jako „zielony”, a drugi punkt (5.5, 4.5) powinien być zaklasyfikowany jako „czerwony”.

Algorytm
Niech m będzie liczbą próbek danych uczących. Niech p będzie nieznanym punktem.

1. Przechowuj próbki uczące w tablicy punktów danych arr. Oznacza to, że każdy element tej tablicy reprezentuje krotkę (x, y).

2. for i=0 to m: Calculate Euclidean distance d(arr, p).

3. Utwórz zbiór S K najmniejszych uzyskanych odległości . Każda z tych odległości odpowiada już sklasyfikowanemu punktowi danych.
4. Zwróć etykietę większości wśród S.

K może być utrzymane jako liczba nieparzysta, abyśmy mogli obliczyć zdecydowana większość w przypadku, gdy możliwe są tylko dwie grupy (np. czerwona / niebieska). Wraz ze wzrostem K otrzymujemy gładsze, bardziej zdefiniowane granice w różnych klasyfikacjach. Ponadto dokładność powyższego klasyfikatora wzrasta wraz ze wzrostem liczby punktów danych w zbiorze uczącym.

Przykładowy program
Załóżmy, że 0 i 1 to dwa klasyfikatory (grupy).

Wynik:

The value classified to unknown point is 0.

Ten artykuł jest autorstwa Anannya Uberoi. Jeśli podoba Ci się GeeksforGeeks i chciałbyś wnieść swój wkład, możesz również napisać artykuł za pomocą contrib.geeksforgeeks.org lub wysłać swój artykuł na adres [email protected]. Zobacz swój artykuł pojawiający się na stronie głównej GeeksforGeeks i pomóż innym Geekom.