Klasyfikacja kNN

on

Jak działa klasyfikacja kNN?

Algorytm poszukuje najbliższego sąsiada punktu aby określić jego klasę.

Opis listingu dla klasyfikacji kNN

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter

Import trzech modułów. Numpy do obsługi tablic (macierzy), MatPlotLib do wizualizacji danych oraz podmodułu Counter z wbudowanego modułu collections odpowiadającego za liczenie elementów.

points = {"blue": [[2, 4], [1, 3], [2, 3], [3, 2], [2, 1]],
          "red": [[5, 6], [4, 5], [4, 6], [6, 6], [5, 4]]}

new_point = [4, 4]

W zmiennej point tworzony jest słownik dla koordynatów punktów czerwonych i niebieskich. Wartościami dla kluczy są listy z koordynatami. Poniżej zmienna point definiuje jako listę współrzędne punktu stanowiącego cel klasyfikacji kNN.

def euclidean_distance(p, q):
    np.sqrt(np.sum((np.array(p) - np.array(q)) ** 2))

Stworzenie funkcji odpowiadającej za obliczanie odległości w przestrzeni euklidesowej w przestrzeni dwuwymiarowej między dwoma punktami. Funkcja przyjmuje dwie wartości. Parametr p to koordynaty pierwszego punktu, natomiast parametr q to koordynaty drugiego punktu. Powyższy kod to implementacja tego wzoru.

Użyto biblioteki NumPy, ponieważ działania są na macierzach (2×1). Sqrt liczy pierwiastki kwadratowe, sum sumuje dwie macierze, zaś np.array tworzy macierz w formacie modułu NumPy.

Powyżej wizualna reprezentacja wzoru i kodu.

class KNN:
    def __init__(self, k=3):
        self.k = k
        self.point = None

    def fit(self, points):
        self.points = points

    def predict(self, new_point):
        distances = []

        for category in self.points:
            for point in self.points[category]:
                distance = euclidean_distance(point, new_point)
                distances.append([distance, category])

        categories = [category[1] for category in sorted(distances)[:self.k]]
        result = Counter(categories).most_common(1)[0][0]
        return result

Dla kontekstu przedstawiono powyżej listing całej klasy.

def __init__(self, k=3):
    self.k = k
    self.point = None

def fit(self, points):
    self.points = points

Na początku użyty został konstruktor klasy kNN__init__. Wywoływany jest automatycznie podczas tworzenia instancji. Konstruktor domyślnie posiada wartość 3 dla parametru k. Linijka self.point = None przypisuje atrybut instancji point wartość None.

Metoda fit jest odpowiedzialna za przekazywanie danych treningowych (słownika points) do klasyfikatora i przechowywanie ich w atrybucie instancji self.points.

def predict(self, new_point):
    distances = []

Dla klasy kNN zostaje stworzona metoda instancji o nazwie predict. Przyjmuje argument new_point, czyli punkt dla którego będzie przewidywana kategoria. Metoda tworzy pustą listę, która będzie zawierać odległości między każdym punktem, a punktem nowym wraz z odpowiadającą im kategorią.

for category in self.points:
     for point in self.points[category]:
          distance = euclidean_distance(point, new_point)
          distances.append([distance, category])

self.points to słownik w którym klucze stanowią kategorie (blue/red), a wartości koordynaty punktów. Pętla for iteruje po każdej kategorii (blue/red), a następnie po każdym punkcie znajdującym się w danej kategorii (xn, yn).

distance = euclidean_distance(point, new_point)

Kiedy już funkcja porusza się w obrębie wszystkich punktów wykonywana jest wcześniej stworzona funkcja euclidean_distance. Ta już jasno liczy odległość między każdym punktem a punktem nowym i zapisuje ją do zmiennej distance.

distances.append([distance, category])

Do wcześniej utworzonej listy zapisywana jest każda obliczona odległość wraz z odpowiadającą jej kategorią, czyli [distance, category].

categories = [category[1] for category in sorted(distances)[:self.k]]
result = Counter(categories).most_common(1)[0][0]

Funkcja sorted sortuje listę distances w odpowiedniej kolejności.

[:self.k]]

Powyższy fragment definiuje na podstawie jakiej ilości najbliższych sąsiadów ma być wykonany wybór (w tym przypadku 3). Fragment z pętlą tworzy listę kategorii (kolorów). Tak spreparowana lista jest gotowa do policzenia.

Counter(categories).most_common(1)[0][0]

Zlicza wystąpienia każdej kategorii i zwraca listę tupli, gdzie pierwszy element każdej tupli to kategoria, a drugi to liczba jej wystąpień. Indeksy [0][0] wybierają pierwszy element z pierwszej tupli, co odpowiada kategorii, która wystąpiła najczęściej wśród najbliższych sąsiadów.

Funkcja finalnie zwraca kategorię nowego punktu (czerwony lub niebieski).

clf = KNN()
clf.fit(points)
print(clf.predict(new_point))

Tworzona jest instancja klasy KNN. Następnie metoda fit wstrzykuje koordynaty punktów do klasy. Finalnie program zwraca wynik w postaci sklasyfikowanego punktu tzn. kategoria red lub blue.

Dalsza część programu to stworzenie wykresu.

Lista kroków

  1. Importowanie potrzebnych bibliotek
  2. Przygotowanie danych
  3. Definiowanie funkcji odległości euklidesowej
  4. Implementacja klasy KNN
  5. Tworzenie instancji klasy KNN i dopasowanie modelu
  6. Przewidywanie klasy nowego punktu
  7. Wizualizacja punktów i nowego punktu

Kod źródłowy

Pełny listing w formacie .py poniżej lub na GitHubie.

Kod
import numpy as np
import matplotlib.pyplot as plt
from collections import Counter

points = {„blue”: [[2, 4], [1, 3], [2, 3], [3, 2], [2, 1]],
„red”: [[5, 6], [4, 5], [4, 6], [6, 6], [5, 4]]}

new_point = [4, 4]

#funkcja do oblicznania odgleglosci miedzy punktami
def euclidean_distance(p, q):
np.sqrt(np.sum((np.array(p) – np.array(q)) ** 2))

class KNN:
#konstruktor klasy KNN
def __init__(self, k=3):
self.k = k
self.point = None

def fit(self, points):
self.points = points

def predict(self, new_point):
distances = []

for category in self.points:
for point in self.points[category]:
distance = euclidean_distance(point, new_point)
distances.append([distance, category])

categories = [category[1] for category in sorted(distances)[:self.k]] result = Counter(categories).most_common(1)[0][0] return result

clf = KNN()
clf.fit(points)
print(clf.predict(new_point))

ax = plt.subplot()
ax.grid(True, color=’#323232′)

ax.set_facecolor(’black’)
ax.figure.set_facecolor(’#121212′)
ax.tick_params(axis=’x’, colors=’white’)
ax.tick_params(axis=’y’, colors=’white’)

[ax.scatter(point[0], point[1], color=’#104DCA’, s=60) for point in points[’blue’]] [ax.scatter(point[0], point[1], color=’#FF0000′, s=60) for point in points[’red’]] [ax.plot([new_point[0], point[0]], [new_point[1], point[1]], color=’#104DCA’, linestyle=’–’, linewidth=1) for point in points[’blue’]] [ax.plot([new_point[0], point[0]], [new_point[1], point[1]], color=’#FF0000′, linestyle=’–’, linewidth=1) for point in points[’red’]]

plt.show()

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *