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. knn.jpg 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

Recommended Posts

Essayez d'implémenter k-NN par vous-même
Essayez d'installer OpenCV 3.0 sur l'AMI
Remarque sur la création de votre propre environnement Miniconda
[Python] Enregistrez votre propre bibliothèque dans PyPI
Importez vos propres fonctions avec AWS Glue
Essayez de créer votre propre AWS-SDK avec bash
Essayez de créer votre propre CorDapp. (Jusqu'à la création des États)
Prenez votre propre utilisation maximale de la mémoire sous Linux et Python
Essayez d'améliorer votre propre quiz d'introduction avec Python
Essayez de mettre des LED dans votre propre PC (légèrement)
Essayez FEniCS sur Windows!
Essayez Poerty sur Windows
Essayez deepdream sur Mac
Essayez de trier vos propres objets avec des files d'attente prioritaires en Python
Installer Linux sur Chromebox
Essayez d'implémenter RBM avec chainer.
Essayez StyleGAN avec Google Colaboratory
Essayez d'utiliser OpenCV sur Windows
Essayez d'implémenter XOR avec PyTorch
Installez numba sur Mac
Essayez «100 coups sur la science des données» ①
Créez votre propre middleware Django
Installez Django sur Mac
Implémentons Yuma dans Python 3
Essayez d'implémenter le parfum avec Go
Compilation croisée pour Raspberry Pi Zero sur Debian - Créez votre propre bibliothèque partagée
Essayez docker: créez votre propre image de conteneur pour une application Web Python
Essayez de vous connecter automatiquement à Netflix en utilisant python sur votre PC
Introduction au Deep Learning (2) - Essayez votre propre régression non linéaire avec Chainer-