Préface

Cet article est un mémo pris en étudiant la vidéo d'un grand programmeur, M. Sentdex. https://www.youtube.com/user/sentdex

Tout d'abord, qu'est-ce que K-NN? Selon WIKI: https://ja.wikipedia.org/wiki/K%E8%BF%91%E5%82%8D%E6%B3%95

La méthode k-voisinage est la plus simple de presque tous les algorithmes d'apprentissage automatique. La classification d'un objet est déterminée en votant sur ses voisins (c'est-à-dire en attribuant la classe la plus courante de k voisins les plus proches de cet objet). k est un entier positif, généralement petit. Si k = 1, il ne sera classé que dans la même classe que l'objet le plus proche. Dans le cas d'une classification binomiale, si k est mis à un nombre impair, le problème de ne pas pouvoir classer avec le même nombre de voix peut être évité.

Ouais, d'une manière très démocratique. Regardez d'abord le graphique ci-dessous. Il y a 6 points de données. Et si vous souhaitez grouper?

Ce sera peut-être comme ça. Alors pourquoi? Parce qu'ils sont proches les uns des autres. Ce que nous faisons s'appelle "Cluster".

D'accord. Cette fois, il y en a déjà + et groupés.

J'ai un point rouge maintenant. À quel groupe appartiendra ce point rouge? Vous serez probablement dans le groupe +. Mais pourquoi? Quel genre de circuit de réflexion avez-vous pensé dans votre esprit?

Le prochain point rouge sera probablement dans le groupe. Qu'est-ce qu'il y a encore?

Dernier point rouge Si vous êtes ici, de quel groupe s'agit-il? Cela dépend de l'algorithme de votre choix.

Revenons à l'histoire. Peut-être (du moins moi) ce point rouge est-il plus proche du groupe + que du groupe, donc le point rouge est le groupe +! J'aurais dû décider. Et nous appelons cette «idée» les K-plus proches voisins (K-NN). En japonais, je pense que c'est la méthode k-voisinage. Tout ce que j'ai à faire pour K-NN est de mesurer la distance entre les points que je souhaite grouper et les autres points, et de décider quel groupe rejoindre. Dans l'exemple ci-dessus, il n'y a que 2 groupes, mais que faire s'il y a 100 tâches? Et s'il y a un problème 1000? Ouais, je vais perdre la tête ...

Mais réfléchissez à deux fois. Dois-je vraiment mesurer tous les points? Je ne pense pas que ce soit nécessaire dans la plupart des cas. "K" est défini dans K-NN. Maintenant, posons K = 2.

Oui je vois. L'endroit où le cercle orange est écrit est probablement le plus proche du point rouge. Par conséquent, je juge que ce point rouge est + group.

Cette fois, une tache noire est apparue. Si K = 2, quel est le point le plus proche? Ouais, peut-être ces deux. J'ai un problème! C'était une égalité! Je ne peux pas juger ça. K-NN ne permet fondamentalement pas que ce k soit pair.

Réglez donc K = 3. Lorsque K = 3, nous avons besoin d'un autre point. Peut-être ... est plus proche? Ce point noir est un groupe.

Donc, selon le jugement précédent, il y a deux et un +. 2/3 = 66% Ce 66% est la confiance dans cette décision. Et la distance mesurée à l'avance est appelée Distance Euclidienne.

la mise en oeuvre

Décidons d'abord le flux.

Préparation des données

Implémentons-le en utilisant sklearn.

Tout d'abord, je dois préparer un ensemble de données, c'est donc celui que j'utiliserai cette fois: https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+%28original%29 Données sur le cancer du sein.

L'analyse des données

Je pense que celui téléchargé ressemblera à ceci.

Ouvrez breast-cancer-wisconsin.names pour obtenir une description des données. La "signification" de chaque valeur de donnée est écrite en 7. À partir de là, il semble que 1 à 10 sont des fonctionnalités et 11 sont des étiquettes. Il y a des données dans les données du cancer du sein-wisconsin. Cependant, l'étiquette importante n'est pas écrite. Vous pouvez l'ajouter par programme, mais pour l'instant, saisissez-le manuellement ...

Import de bibliothèque


import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd

Pré-traiter avec les pandas

L'identifiant ne semble pas avoir grand-chose à voir avec l'ensemble de données, alors supprimez-le. Il est écrit que "?" Est affiché dans la partie manquante de breast-cancer-wisconsin.names. Puisque NAN est un NG de base, nous le remplacerons ici par -99999.

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)

Préparer les données X et Y

En termes simples, X est des données non étiquetées. Y correspond aux données d'étiquette uniquement. Donc X met un DataFrame avec une "classe" supprimée. Y met un DataFrame avec uniquement "Class".

#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])

Données de test et de train séparées

80% des données de train et 20% des données de test sont séparées.

x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.2)

Préparer le classificateur

Depuis que j'utilise K-NN, c'est un classificateur K Neighbours.

clf=neighbors.KNeighborsClassifier()

Train

clf.fit(x_train,y_train)

Vérifier avec les données de test

Ouais, c'est environ 96%. C'est une bonne précision.

accuracy=clf.score(x_test,y_test)
print(accuracy)

>0.9642857142857143

Code général

import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)

#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])

x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.2)
clf=neighbors.KNeighborsClassifier()
clf.fit(x_train,y_train)
accuracy=clf.score(x_test,y_test)
print(accuracy)

Creusons profondément

À partir de maintenant, j'écrirai KNN par moi-même sans me fier à sklearn. Regardons à nouveau d'abord. En fait, c'est une distance pour décider quel groupe faire les points noirs. Cette distance est appelée "Distance Euclidienne".

une formule

La formule de calcul est la suivante. Désolé pour les vilains personnages ... ici, i＝Diemensions q = point p = différence

Par exemple, q = (1,3), p = (2,5). Euclidean Distance＝2.236

la mise en oeuvre

Écrivons d'abord cette formule en python.

from math import sqrt

plot1=[1,3]
plot2=[2,5]

euclidean_distance=sqrt( (plot1[0]-plot2[0])**2 + (plot1[1]-plot2[1])**2 )

print(euclidean_distance)

Créer une fonction

Avant de créer une fonction, réfléchissons d'abord à l'idée. Le code ci-dessous essaie d'abord de tracer le jeu de données et les nouvelles données. C'est juste pour la fonction de Function. données: Train_data. prédire: il s'agit de Test_data. k: Combien de points obtenez-vous, je pense que sklearn a une valeur par défaut de k = 5 ... Et à la fin, cela active un peu de magie et produit le résultat!

la mise en oeuvre

from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings

style.use('fivethirtyeight')

data_set={'k':[[1,2],[2,3],[3,1]]
          ,'r':[[6,5],[7,7],[8,6]]} 

new_features=[5,7]

[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1])

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    #?make some magic
    
    return vote_result

Pensez à un appareil magique

Cherchez-vous vraiment cette fonction? Comment comparer un point de données avec un autre et trouver le point le plus proche. KNN doit comparer les points de prédiction à tous les points, ce qui est un problème KNN. Certes, il est possible de gagner du temps de calcul en paramétrant Radius et en ne voyant qu'un certain nombre de points.

la mise en oeuvre

Calculez tout euclidean_distane dans For Loop et ajoutez-le au tableau.
Par exemple, [2.44, 'r'], [1.4, 'r'], [2.14, 'k'], [4.4, 'k'], [5.44, 'k'] ..
Triez ensuite le tableau appelé votes de petit à grand euclidean_distane calculé dans le tableau précédent.
Stockez l'étiquette correspondant à cet euclidean_distane.
Utilisez Counter (votes) .most_common (1) pour extraire les éléments les plus fréquents. C'est provisoirement [('r', 3)].
En utilisant Counter (votes) .most_common (1) [0] [0], «r» peut être récupéré davantage.
Enfin, renvoyez le résultat.

from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings

style.use('fivethirtyeight')

data_set={'k':[[1,2],[2,3],[3,1]]
          ,'r':[[6,5],[7,7],[8,6]]} 

new_features=[5,7]

[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1])

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    for group in data:
        #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
        #iterating  ^                       ^
        for features in data[group]:
            #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
            #iterating      ^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^
            
            #not fast and just for 2-dimensions
            #euclidean_distacnce=sqrt(  (features[0]-predict[0])**2 + features[1]-predict[1]**2 )
            
            #better
            #euclidean_distane=np.sqrt( np.sum((np.array(features)-np.array(predict))**2))
            
            euclidean_distane=np.linalg.norm( np.array(features)-np.array(predict)  )
            distance.append([euclidean_distane,group])
    
    votes=[i[1] for i in sorted(distance)[:k]]
    
    print(Counter(votes).most_common(1))
    
    vote_result=Counter(votes).most_common(1)[0][0]
            
    return vote_result

result=k_nearest_neighbors(data_set,new_features,k=3)
print(result)
[[plt.scatter(ii[0],ii[1],s=100,color=i) for ii in data_set[i]] for i in data_set]
plt.scatter(new_features[0],new_features[1],color=result)

Ouais, c'est le groupe rouge!

Allons un peu plus loin

Utilisons maintenant des données réelles et comparons scikit-learn avec laquelle est la plus précise.

Utilisez full_data = df.astype (float) .values.tolist () pour changer de manière aléatoire l'ordre des données.
Préparez un ensemble de données pour train_set et test_set. Dans le dictionnaire, utilisez 2 et 4 pour faire correspondre la classe dans les données précédentes sur le cancer du sein.
train_data = full_data [: -int (test_size * len (full_data))], par exemple, s'il y a 100 full_data, test_size vaut 0,2, donc 100 * 0,2 = 20. train_data = full_data [: -20] stocke 80 ensembles de données sous forme de train_data.
test_data = full_data [-int (test_size * len (full_data)):], par exemple, s'il y a 100 full_data, test_size vaut 0,2, donc 100 * 0,2 = 20. train_data = full_data [-20:] stocke test_data dans les 20 derniers ensembles de données.
La dernière boucle For utilise Train_data et test_set, et bien que test_set soit du groupe 2, on peut dire qu'il était erroné lorsque le vote a renvoyé 4, et inversement, test_set était le groupe 2 et qu'il était correct lorsque le vote a renvoyé 4. Réglez correct sur +1. Et le nombre exact / Total peut être considéré comme le taux de réponse correct.

Fonction d'auto-assistance

from math import sqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import style
from collections import Counter
import warnings
import pandas as pd
import random

style.use('fivethirtyeight')

def k_nearest_neighbors(data,predict,k=3):
    if len(data) >=k:
        warnings.warnings('K is set to a value less than total voting groups!')
    
    for group in data:
        #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
        #iterating  ^                       ^
        for features in data[group]:
            #data_set={'k':[[1,2],[2,3],[3,1]],'r':[[6,5],[7,7],[8,6]]} 
            #iterating      ^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^
            
            #not fast and just for 2-dimensions
            #euclidean_distacnce=sqrt(  (features[0]-predict[0])**2 + features[1]-predict[1]**2 )
            
            #better
            #euclidean_distane=np.sqrt( np.sum((np.array(features)-np.array(predict))**2))
            
            euclidean_distane=np.linalg.norm( np.array(features)-np.array(predict)  )
            distance.append([euclidean_distane,group])
    
    votes=[i[1] for i in sorted(distance)[:k]]
    
    print(Counter(votes).most_common(1))
    
    vote_result=Counter(votes).most_common(1)[0][0]
            
    return vote_result

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)
df.drop(['id'],1,inplace=True)
full_data=df.astype(float).values.tolist()

#random sort your data
random.shuffle(full_data)

test_size=0.2
train_set={2:[],4:[]}
test_set={2:[],4:[]}

train_data=full_data[:-int(test_size*len(full_data))]#first 80%
test_data=full_data[-int(test_size*len(full_data)):] #last 20%

'''
for i in train_data:
    #train_set[i[-1]] is the class data from train_set:2 or 4.
    #.append(i[:-1]) is the function to take all the data (unless the class) to the list 
    train_set[i[-1]].append(i[:-1])

for i in test_data:
    test_set[i[-1]].append(i[:-1])
'''
correct=0
total=0

for group in test_set:
    #loop the class'2' and '4'
    for data in test_set[group]:
        #take the data from set'2' and '4'
        vote=k_nearest_neighbors(train_set,data,k=5)
        if group == vote:
            correct+=1
        total+=1
        

print('Accuracy:',correct/total)

>Accuracy: 0.9640287769784173

sklearn Function

Codez comme d'habitude.

import numpy as np
from sklearn import preprocessing,model_selection,neighbors
import pandas as pd

df=pd.read_csv('Data/Breast_Cancer_Wisconsin/breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True)

df.drop(['id'],1,inplace=True)

#features
x=np.array(df.drop(['class'],1))
#label
y=np.array(df['class'])

x_train,x_test,y_train,y_test=model_selection.train_test_split(x,y,test_size=0.4)

clf=neighbors.KNeighborsClassifier()
clf.fit(x_train,y_train)

accuracy=clf.score(x_test,y_test)

>Accuracies: 0.9671428571428571

Conclusion

… Le taux de réponse correct ne change pas beaucoup, mais la vitesse de calcul est clairement plus rapide avec sklearn.

finalement

Eh bien, je pense qu'il existe encore de nombreuses autres façons de classer sans utiliser KNN. Par exemple, disons que vous disposez de ce type de données linéaires. Peut-être? Écrivez d'abord ces lignes ... Et un nouveau point rouge sortira. Est-il possible de faire des calculs avec Square Error? Supposons maintenant que vous ayez de telles données non linéaires. Si vous forcez une ligne, c'est peut-être comme ça? Dans ce cas, vous pouvez utiliser KNN pour le savoir immédiatement.