[PYTHON] Essayez d'implémenter k-NN par vous-même

Motivation

Je reconfirmais mes connaissances liées à l'apprentissage automatique, et après avoir étudié la méthode la plus basique, la méthode k-NN (méthode k plus proche voisin), j'ai essayé de la mettre en œuvre moi-même.

Quelle est la méthode k-NN?

Tout d'abord, passons en revue les grandes lignes de k-NN. C'est un algorithme très simple et facile à comprendre, vous pouvez donc le comprendre facilement. Cet algorithme est tout dans la figure ci-dessous. Les données d'intérêt sont l'étoile centrale. Tout d'abord, pour les données données, calculez la distance entre toutes les données. Par exemple, lorsque k = 3, regardez les étiquettes des 3 premières données les plus proches des données d'intérêt. Dans ce cas, comme il y a deux classe 1 et une classe 2, elle est classée en classe 1 qui prend la valeur la plus fréquente. Par contre, si k = 6, il y aura 2 classes 1 et 6 classes 2, donc ces données seront classées en classe 2. Les données ainsi données seront décidées par un vote majoritaire sur les étiquettes de données similaires. À propos, lorsque k = 1, on l'appelle aussi la méthode du plus proche voisin. Une technique portant un nom similaire est la méthode k-means. , Il s'agit d'une méthode de classification non supervisée, différente de la méthode de classification supervisée, la méthode k-NN.

la mise en oeuvre

Ensuite, je voudrais l'implémenter en Python.

base de données

L'ensemble de données utilise le fameux Iris Data Set. Téléchargez iris.data et chargez réellement les données.

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,)

Cet ensemble de données se compose de 150 données avec 4 caractéristiques et leurs étiquettes (3 classes).

Recherche la plus proche

Cette fois, nous utiliserons ces bibliothèques.

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

Tout d'abord, calculez la distance entre chaque donnée pour un point donné.

knn.py

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

Ensuite, pour k données à proximité des données données, comptez le nombre de données de quelle classe.

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

Enfin, identifiez l'étiquette de classe la plus courante.

knn.py

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

C'est tout pour l'algorithme k-NN lui-même.

Courir

Cette fois, chaque classe est divisée en deux au hasard et le flux d'apprentissage et d'exécution est répété 20 fois. Le résultat réel de l'exécution est le suivant. (Étant donné que les données sont divisées au hasard, il y aura une légère différence de précision.)

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

De cette façon, vous pouvez voir qu'une grande précision a été obtenue.

Impressions

Il n'y avait qu'un algorithme simple et très facile à mettre en œuvre. C'est très efficace si la dimension est petite et le nombre de données est petit comme ces données. Cependant, en réalité, pour les données de grande dimension, [Dimensional Curse](https://ja.wikipedia.org/wiki/%E6%AC%A1%E5%85%83%E3%81%AE%E5% L'effet de 91% AA% E3% 81% 84) rend la distance euclidienne dénuée de sens, et il n'est pas pratique pour les calculs temporels et spatiaux dans les grands ensembles de données. Pour de tels problèmes, Méthodes de hachage et de quantification des vecteurs ont proposé des méthodes pour réduire la consommation de mémoire et le calcul. Je vais. Vous pouvez vérifier le code source réel sur github. https://github.com/kotaYkw/machine_learning