- K-Nearest Neighbor to jeden z najprostszych algorytmów Machine Learning bazujący na technice Supervised Learning.
- Algorytm K-NN zakłada podobieństwo nowego przypadku/danych do dostępnych przypadków i umieszcza nowy przypadek w kategorii najbardziej podobnej do dostępnych kategorii.
- Algorytm K-NN przechowuje wszystkie dostępne dane i klasyfikuje nowy punkt danych na podstawie podobieństwa. Oznacza to, że gdy pojawią się nowe dane, można je łatwo zaklasyfikować do odpowiedniej kategorii za pomocą algorytmu K-NN.
- Algorytm K-NN może być używany zarówno do regresji, jak i klasyfikacji, ale głównie jest używany do problemów klasyfikacyjnych.
- K-NN to a algorytm nieparametryczny , co oznacza, że nie przyjmuje żadnych założeń na temat danych bazowych.
- Nazywa się to również A algorytm leniwego ucznia ponieważ nie uczy się od razu na podstawie zbioru szkoleniowego, zamiast tego przechowuje zbiór danych i w momencie klasyfikacji wykonuje akcję na zbiorze danych.
- Algorytm KNN na etapie uczenia po prostu przechowuje zbiór danych, a gdy otrzyma nowe dane, klasyfikuje je w kategorii bardzo podobnej do nowych danych.
Dlaczego potrzebujemy algorytmu K-NN?
Załóżmy, że istnieją dwie kategorie, tj. kategoria A i kategoria B, i mamy nowy punkt danych x1, więc ten punkt danych będzie należeć do której z tych kategorii. Aby rozwiązać tego typu problem, potrzebujemy algorytmu K-NN. Za pomocą K-NN możemy łatwo zidentyfikować kategorię lub klasę konkretnego zbioru danych. Rozważ poniższy diagram:
Jak działa K-NN?
Działanie K-NN można wyjaśnić na podstawie poniższego algorytmu:
Załóżmy, że mamy nowy punkt danych i musimy umieścić go w wymaganej kategorii. Rozważ poniższy obraz:
typy drzew binarnych
- Najpierw wybierzemy liczbę sąsiadów, więc wybierzemy k=5.
- Następnie obliczymy Odległość euklidesowa pomiędzy punktami danych. Odległość euklidesowa to odległość między dwoma punktami, którą badaliśmy już w geometrii. Można to obliczyć jako:
- Obliczając odległość euklidesową, otrzymaliśmy najbliższych sąsiadów, czyli trzech najbliższych sąsiadów w kategorii A i dwóch najbliższych sąsiadów w kategorii B. Rozważmy poniższy obrazek:
- Jak widzimy 3 najbliższych sąsiadów należy do kategorii A, dlatego ten nowy punkt danych musi należeć do kategorii A.
Jak wybrać wartość K w algorytmie K-NN?
Poniżej znajduje się kilka punktów, o których należy pamiętać przy wyborze wartości K w algorytmie K-NN:
- Nie ma szczególnego sposobu określenia najlepszej wartości „K”, dlatego musimy wypróbować niektóre wartości, aby znaleźć najlepszą z nich. Najbardziej preferowaną wartością K jest 5.
- Bardzo niska wartość K, taka jak K=1 lub K=2, może powodować zakłócenia i prowadzić do wystąpienia w modelu efektów wartości odstających.
- Duże wartości K są dobre, ale mogą powodować pewne trudności.
Zalety algorytmu KNN:
- Jest to proste do wdrożenia.
- Jest odporny na zaszumione dane treningowe
- Może być bardziej skuteczny, jeśli dane szkoleniowe są duże.
Wady algorytmu KNN:
- Zawsze trzeba określić wartość K, która może być złożona w pewnym momencie.
- Koszt obliczeń jest wysoki ze względu na obliczenie odległości między punktami danych dla wszystkich próbek uczących.
Implementacja algorytmu KNN w Pythonie
Aby wykonać implementację algorytmu K-NN w Pythonie, użyjemy tego samego problemu i zbioru danych, których użyliśmy w regresji logistycznej. Ale tutaj poprawimy wydajność modelu. Poniżej znajduje się opis problemu:
Problem dla algorytmu K-NN: Istnieje firma produkująca samochody, która wyprodukowała nowy samochód typu SUV. Firma chce wyświetlać reklamy użytkownikom zainteresowanym kupnem tego SUV-a. W przypadku tego problemu mamy zbiór danych zawierający informacje o wielu użytkownikach za pośrednictwem sieci społecznościowej. Zbiór danych zawiera wiele informacji, ale Szacowane wynagrodzenie I Wiek rozważymy zmienną niezależną i Zakupiona zmienna dotyczy zmiennej zależnej. Poniżej znajduje się zbiór danych:
Kroki wdrożenia algorytmu K-NN:
- Etap wstępnego przetwarzania danych
- Dopasowanie algorytmu K-NN do zbioru uczącego
- Przewidywanie wyniku testu
- Sprawdź dokładność wyniku (Tworzenie macierzy zamieszania)
- Wizualizacja wyniku zestawu testowego.
Etap wstępnego przetwarzania danych:
Etap wstępnego przetwarzania danych pozostanie dokładnie taki sam, jak w przypadku regresji logistycznej. Poniżej znajduje się jego kod:
# importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd #importing datasets data_set= pd.read_csv('user_data.csv') #Extracting Independent and dependent Variable x= data_set.iloc[:, [2,3]].values y= data_set.iloc[:, 4].values # Splitting the dataset into training and test set. from sklearn.model_selection import train_test_split x_train, x_test, y_train, y_test= train_test_split(x, y, test_size= 0.25, random_state=0) #feature Scaling from sklearn.preprocessing import StandardScaler st_x= StandardScaler() x_train= st_x.fit_transform(x_train) x_test= st_x.transform(x_test)
Wykonując powyższy kod, nasz zbiór danych zostaje zaimportowany do naszego programu i dobrze wstępnie przetworzony. Po skalowaniu funkcji nasz testowy zbiór danych będzie wyglądał następująco:
Z powyższego obrazu wyjściowego widzimy, że nasze dane zostały pomyślnie przeskalowane.
Teraz dopasujemy klasyfikator K-NN do danych uczących. W tym celu zaimportujemy plik Klasyfikator KNeighbors klasa Sklearn Sąsiedzi biblioteka. Po zaimportowaniu klasy utworzymy plik Klasyfikator obiekt klasy. Parametrem tej klasy będzie
#Fitting K-NN classifier to the training set from sklearn.neighbors import KNeighborsClassifier classifier= KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2 ) classifier.fit(x_train, y_train)
Dane wyjściowe: Wykonując powyższy kod, otrzymamy dane wyjściowe w postaci:
Out[10]: KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski', metric_params=None, n_jobs=None, n_neighbors=5, p=2, weights='uniform')
#Predicting the test set result y_pred= classifier.predict(x_test)
Wyjście:
Dane wyjściowe powyższego kodu będą następujące:
Teraz utworzymy macierz zamieszania dla naszego modelu K-NN, aby sprawdzić dokładność klasyfikatora. Poniżej znajduje się jego kod:
#Creating the Confusion matrix from sklearn.metrics import confusion_matrix cm= confusion_matrix(y_test, y_pred)
W powyższym kodzie zaimportowaliśmy funkcję zamieszanie_matrix i wywołaliśmy ją przy użyciu zmiennej cm.
Wyjście: Wykonując powyższy kod otrzymamy macierz jak poniżej:
Na powyższym obrazku widzimy, że jest 64+29= 93 prawidłowych przewidywań i 3+4= 7 błędnych przewidywań, podczas gdy w regresji logistycznej było 11 błędnych przewidywań. Można zatem powiedzieć, że wydajność modelu poprawia się dzięki zastosowaniu algorytmu K-NN.
Teraz zwizualizujemy wynik zbioru uczącego dla modelu K-NN. Kod pozostanie taki sam, jak w przypadku regresji logistycznej, z wyjątkiem nazwy wykresu. Poniżej znajduje się jego kod:
#Visulaizing the trianing set result from matplotlib.colors import ListedColormap x_set, y_set = x_train, y_train x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN Algorithm (Training set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show()
Wyjście:
różnica między lodem a śniegiem
Wykonując powyższy kod otrzymamy poniższy wykres:
Wykres wyjściowy różni się od wykresu, który otrzymaliśmy w ramach regresji logistycznej. Można to zrozumieć w poniższych punktach:
- Jak widzimy, wykres pokazuje czerwony i zielony punkt. Zielone punkty dotyczą zmiennej „Kupione” (1), a punkty czerwone – „Nie Kupione” (0).
- Wykres pokazuje nieregularną granicę zamiast pokazywać prostą lub jakąkolwiek krzywą, ponieważ jest to algorytm K-NN, czyli znajdowanie najbliższego sąsiada.
- Wykres sklasyfikował użytkowników we właściwych kategoriach, ponieważ większość użytkowników, którzy nie kupili SUV-a, znajduje się w obszarze czerwonym, a użytkownicy, którzy kupili SUV-a, znajduje się w obszarze zielonym.
- Wykres pokazuje dobry wynik, ale nadal jest kilka zielonych punktów w czerwonym obszarze i czerwonych punktów w zielonym obszarze. Ale nie jest to duży problem, ponieważ dzięki temu modelowi zapobiega się problemom związanym z nadmiernym dopasowaniem.
- Dlatego nasz model jest dobrze wyszkolony.
Po wytrenowaniu modelu przetestujemy teraz wynik umieszczając nowy zbiór danych, czyli Test dataset. Kod pozostaje taki sam, z wyjątkiem kilku drobnych zmian: takich jak x_train i y_train zostanie zastąpiony przez x_test i y_test .
Poniżej znajduje się jego kod:
#Visualizing the test set result from matplotlib.colors import ListedColormap x_set, y_set = x_test, y_test x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN algorithm(Test set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show()
Wyjście:
Powyższy wykres przedstawia dane wyjściowe dla zestawu danych testowych. Jak widać na wykresie, przewidywane wyniki są dobre, ponieważ większość czerwonych punktów znajduje się w obszarze czerwonym, a większość punktów zielonych znajduje się w obszarze zielonym.
Istnieje jednak kilka zielonych punktów w obszarze czerwonym i kilka czerwonych punktów w obszarze zielonym. Są to więc błędne obserwacje, które zaobserwowaliśmy w macierzy zamieszania (7 Nieprawidłowe dane wyjściowe).