[PYTHON] Versuchen Sie, k-NN selbst zu implementieren

Motivation

Ich bestätigte mein Wissen über maschinelles Lernen erneut und nachdem ich die grundlegendste Methode, die k-NN-Methode (k-Methode für den nächsten Nachbarn), studiert hatte, versuchte ich, sie selbst zu implementieren.

Was ist die k-NN-Methode?

Lassen Sie uns zunächst den Umriss von k-NN überprüfen. Es ist ein sehr einfacher und leicht verständlicher Algorithmus, so dass Sie ihn leicht verstehen können. Dieser Algorithmus ist in der folgenden Abbildung dargestellt. Die Daten von Interesse sind der zentrale Stern. Berechnen Sie zunächst für die angegebenen Daten den Abstand zwischen allen Daten. Wenn beispielsweise k = 3 ist, sehen Sie sich die Beschriftungen der Top-3-Daten an, die den interessierenden Daten am nächsten liegen. In diesem Fall wird es, da es zwei Klassen 1 und eine Klasse 2 gibt, in Klasse 1 klassifiziert, die den häufigsten Wert annimmt. Wenn andererseits k = 6 ist, gibt es 2 Klassen 1 und 6 Klassen 2, so dass diese Daten als Klasse 2 klassifiziert werden. Die auf diese Weise angegebenen Daten werden mit Stimmenmehrheit auf den Etiketten ähnlicher Daten festgelegt. Wenn k = 1 ist, wird es übrigens auch die Methode des nächsten Nachbarn genannt. Eine Technik mit einem ähnlichen Namen ist die k-means-Methode. Dies ist eine nicht überwachte Clustering-Methode, die sich von der überwachten Klassifizierungsmethode, der k-NN-Methode, unterscheidet.

Implementierung

Dann möchte ich es tatsächlich in Python implementieren.

Datensatz

Der Datensatz verwendet den berühmten Iris-Datensatz. Laden Sie iris.data herunter und laden Sie die Daten.

knn.py

data = np.loadtxt('iris.data', delimiter=',', dtype='float64',usecols=[0, 1, 2, 3])
labels = np.loadtxt('iris.data', delimiter=',', dtype='str',usecols=[4])
print(data.shape)
print(labels.shape)

(150, 4)
(150,)

Dieser Datensatz besteht aus 150 Daten mit 4 Merkmalen und deren Bezeichnungen (3 Klassen).

Nächste Suche

Dieses Mal werden wir diese Bibliotheken verwenden.

knn.py

import numpy as np
from sklearn import model_selection
from scipy.spatial import distance
from sklearn.metrics import accuracy_score
from statistics import mean, median,variance

Berechnen Sie zunächst den Abstand zu den einzelnen Daten für einen bestimmten Punkt.

knn.py

distance_matrix = distance.cdist(test_data, train_data)
indexes = np.argsort(distance_matrix, axis=1)

Als nächstes zählen Sie, wie viele Daten welcher Klasse für k Daten in der Nähe der angegebenen Daten vorhanden sind.

knn.py

class_dict = {}
for label in labels:
    class_dict[label] = 0
class_dict_list = []
for data_num, index in enumerate(indexes[:,:self.k]):
    class_dict_list.append(class_dict.copy())
    for i in index:
        class_dict_list[data_num][self._labels[i]] += 1

Identifizieren Sie abschließend das am häufigsten verwendete Klassenlabel.

knn.py

predict_class = []
for d in class_dict_list:
    max_class = max(d, key=d.get)
    predict_class.append(max_class)

Das ist alles für den k-NN-Algorithmus selbst.

Lauf

Dieses Mal wird jede Klasse zufällig in zwei Hälften geteilt, und der Lern- und Ausführungsfluss wird 20 Mal wiederholt. Das tatsächliche Ausführungsergebnis ist wie folgt. (Da die Daten zufällig aufgeteilt werden, gibt es einen kleinen Unterschied in der Genauigkeit.)

training number 1 ...
knn accuracy : 0.9466666666666667
training number 2 ...
knn accuracy : 0.9333333333333333
training number 3 ...
knn accuracy : 0.9466666666666667
training number 4 ...
knn accuracy : 0.9466666666666667
training number 5 ...
knn accuracy : 0.9333333333333333
training number 6 ...
knn accuracy : 0.92
training number 7 ...
knn accuracy : 0.9466666666666667
training number 8 ...
knn accuracy : 0.9466666666666667
training number 9 ...
knn accuracy : 0.8933333333333333
training number 10 ...
knn accuracy : 0.9466666666666667
training number 11 ...
knn accuracy : 0.96
training number 12 ...
knn accuracy : 0.96
training number 13 ...
knn accuracy : 0.96
training number 14 ...
knn accuracy : 0.96
training number 15 ...
knn accuracy : 0.92
training number 16 ...
knn accuracy : 0.96
training number 17 ...
knn accuracy : 0.92
training number 18 ...
knn accuracy : 0.9866666666666667
training number 19 ...
knn accuracy : 0.9333333333333333
training number 20 ...
knn accuracy : 0.96
=================================================
knn accuracy mean : 0.944
knn accuracy variance : 0.00042292397660818664

Auf diese Weise können Sie sehen, dass eine hohe Genauigkeit erreicht wurde.

Impressionen

Es gab nur einen einfachen Algorithmus und er war sehr einfach zu implementieren. Es ist sehr effektiv, wenn die Dimension klein ist und die Anzahl der Daten wie diese Daten klein ist. In Wirklichkeit gilt für hochdimensionale Daten jedoch [Dimensional Curse](https://ja.wikipedia.org/wiki/%E6%AC%A1%E5%85%83%E3%81%AE%E5% Der Effekt von 91% AA% E3% 81% 84) macht den euklidischen Abstand bedeutungslos und ist sowohl für zeitliche als auch für räumliche Berechnungen in großen Datensätzen nicht praktikabel. Für solche Probleme haben Methoden zum Hashing und Quantisieren von Vektoren Methoden zur Reduzierung des Speicherverbrauchs und der Berechnung vorgeschlagen. Ich werde. Sie können den tatsächlichen Quellcode auf github überprüfen. https://github.com/kotaYkw/machine_learning