Une implémentation Python simple de la méthode k-voisinage (k-NN)
Vue d'ensemble de la méthode k-voisinage
Le voisin k-Nearist est un algorithme d'apprentissage automatique qui est supervisé et utilisé pour les problèmes de classification. Un nom très similaire est k-means, mais k-means est utilisé pour la mise en cluster dans l'apprentissage non supervisé.
L'algorithme de k-voisinage lui-même est très simple. Calculez la distance entre les données que vous souhaitez classer et les données existantes, et déterminez la classe par la majorité des données à k points proches les uns des autres.
Par exemple, lorsque k = 1, il s'agit simplement du compagnon de données avec la distance la plus courte.
C'est plus facile à comprendre si vous regardez la figure.
k Exemple de méthode de voisinage. Les spécimens (cercles verts) appartiennent à la première classe (carrés bleus) et à la deuxième classe (triangles rouges). Si k = 3, les objets du cercle intérieur sont à proximité, ils sont donc classés dans la deuxième classe (plus de triangles rouges). Mais si k = 5, il s'inverse. Citation: wikipedia
D'après ce qui précède, les caractéristiques de la méthode k-near sont les suivantes.
- L'apprentissage non supervisé le plus simple
- Aucun apprentissage préalable requis pour l'identification
- La détermination prend du temps car la distance à toutes les données est calculée au moment de la détermination.
- Au fur et à mesure que la dimension devient plus grande, il y a un problème en termes de coût de calcul et de précision (la soi-disant malédiction dimensionnelle a tendance à créer une dépendance).
Implémentation de la méthode k-voisinage (Python)
Implémentation facile
import numpy as np
import scipy.spatial.distance as distance
import scipy.stats as stats
import numpy as np
import scipy.spatial.distance as distance
import scipy.stats as stats
class knn:
def __init__(self,k):
self.k = k
self._fit_X = None #Stocker les données existantes
self.classes = None #
self._y = None
def fit(self, X, label):
#X est le point de données d'origine, forme(data_num, feature_num)
print("original data:\n", X)
print("label:\n", label)
self._fit_X = X
#Extraire les classes des données d'étiquette et créer un tableau avec l'étiquette comme index
# self.classes[self.label_indices] ==Il peut être restauré comme une étiquette, alors retournez_appelé inverse
self.classes, self.label_indices = np.unique(label, return_inverse=True)
print("classes:\n", self.classes)
print("label_indices:\n", self.label_indices)
print("classes[label_indices]Vérifiez s'il peut être restauré avec:\n", self.classes[self.label_indices])
def neighbors(self, Y):
#Y est le point de données à prédire(Plusieurs)alors, shape(test_num, feature_num)
#Puisque la distance entre le point à prédire et le point de données est calculée, testez_num * data_Calculer la distance par num
dist = distance.cdist(Y, self._fit_X)
print("Distance entre les données de test et les données d'origine:\n", dist)
#dist est la forme(test_num, data_num)Devient
# [[1.41421356 1.11803399 2.6925824 2.23606798]Distance entre le point de test 1 et chaque point des données d'origine
# [3. 2.6925824 1.80277564 1.41421356]Distance entre le point de test 2 et chaque point des données d'origine
# [3.31662479 3.20156212 1.11803399 1.41421356]]Distance entre le point de test 3 et chaque point des données d'origine
#Après avoir mesuré la distance, trouvez l'indice inclus jusqu'au kth
#argpartition est une fonction qui divise les données jusqu'au kème et après cela
#Avec argsort, vous pouvez voir l'ordre de la distance, mais k-Puisque nn n'a pas besoin d'informations de classement de distance, utilisez la partition arg
neigh_ind = np.argpartition(dist, self.k)
# neigh_ind la forme est(test_num, feature_num)Devient
#K dans le dist ci-dessus=Résultat de la partition arg en 2
#Par exemple, sur la première ligne, index 2,1 représente les deux éléments supérieurs. En regardant la distance ci-dessus, 0.5 et 1.5 correspond
#La deuxième ligne est l'index 3,2 correspond aux 2 premiers éléments, 1.73 et 1.80 est équivalent
#[[1 0 3 2]
# [3 2 1 0]
# [2 3 1 0]]
#Extraire uniquement les informations jusqu'au kth
neigh_ind = neigh_ind[:, :self.k]
# neigh_ind la forme est(test_num, self.k)Devient
#[[1 0]Liste des index des points de données d'origine proches du point de test 1
# [3 2]Liste des index des points de données d'origine proches du point de test 2
# [2 3]]Liste des index des points de données d'origine proches du point de test 3
return neigh_ind
def predict(self, Y):
#Forme pour trouver l'index jusqu'au kème(test_num, self.k)Devient
print("test data:\n",Y)
neigh_ind = self.neighbors(Y)
# stats.Trouver la valeur la plus fréquente en mode. shape(test_num, 1) . _Est le décompte le plus fréquent
# self.label_indices est[0 0 1 1]Représente l'étiquette de chaque point dans les données d'origine
# neigh_ind est une liste d'index des données d'origine à proximité de chaque point de test, forme(est_num, k)Devient
# self.label_indices[neigh_ind]Vous pouvez obtenir une liste d'étiquettes à proximité de chaque point de test comme ci-dessous
# [[0 0]Liste des étiquettes pour les points de données d'origine proches du point de test 1
# [1 1]Liste des étiquettes pour les points de données d'origine proches du point de test 2
# [1 1]]Liste des étiquettes pour les points de données d'origine proches du point de test 3
#Direction des lignes des données ci-dessus(axis=1)Contre le mode(Valeur la plus fréquente)Et utilisez-le comme étiquette à laquelle appartient chaque point de test
# _Est le nombre de comptes
mode, _ = stats.mode(self.label_indices[neigh_ind], axis=1)
#le mode est un axe=Puisqu'il est totalisé par 1, forme(test_num, 1)Alors élevez(=flatten)Je vais le faire
# [[0]
# [1]
# [1]]
#Notez que np.intp est le type de données utilisé pour l'index
mode = np.asarray(mode.ravel(), dtype=np.intp)
print("Valeur la plus fréquente de chaque étiquette index des données de test:\n",mode)
#Passer de la notation d'index à la notation de nom d'étiquette. self.classes[mode]Pareil que
result = self.classes.take(mode)
return result
Essayez de prédire
K = knn(k=2)
#Définir les données et l'étiquette d'origine
samples = [[0., 0., 0.], [0., .5, 0.], [1., 2., -2.5],[1., 2., -2.]]
label = ['a','a','b', 'b']
K.fit(samples, label)
#Données que vous souhaitez prédire
Y = [[1., 1., 0.],[2, 2, -1],[1, 1, -3]]
p = K.predict(Y)
print("result:\n", p)
Résultat d'exécution
>>result
original data:
[[0.0, 0.0, 0.0], [0.0, 0.5, 0.0], [1.0, 2.0, -2.5], [1.0, 2.0, -2.0]]
label:
['a', 'a', 'b', 'b']
classes:
['a' 'b']
label_indices:
[0 0 1 1]
classes[label_indices]Vérifiez s'il peut être restauré avec:
['a' 'a' 'b' 'b']
test data:
[[1.0, 1.0, 0.0], [2, 2, -1], [1, 1, -3]]
Distance entre les données de test et les données d'origine:
[[1.41421356 1.11803399 2.6925824 2.23606798]
[3. 2.6925824 1.80277564 1.41421356]
[3.31662479 3.20156212 1.11803399 1.41421356]]
Valeur la plus fréquente de chaque étiquette index des données de test:
[0 1 1]
result:
['a' 'b' 'b']
Les références
- Analyse des données 10e "méthode k-voisinage" par Daiji Suzuki
- Définissons la classification, l'analyse de régression et la plage d'application du modèle \ (domaine d'application ) avec [k méthode du plus proche voisin \ (k \ -Nearest Neighbor, k \ -NN )! \ -Speaker Deck](https://speakerdeck.com/hkaneko/kzui-jin-bang-fa-k-nearest-nequart-k-nn-dekurasufen-lei-hui-gui-fen-xi-moderufalseshi-yong- fan-wei-shi-yong-ling-yu-falseshe-ding-wosiyou)
- Comprendre [méthode de voisinage k \ (k \ -Nearest Neighbor ) - documentation OpenCV \ -Python Tutorials 1](http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/ html / py_tutorials / py_ml / py_knn / py_knn_understanding / py_knn_understanding.html)
- Méthode d'apprentissage automatique \ _k voisinage \ _ théorie | Développeurs \ .IO