K plus proches voisins ou "knn"

machine-learning

Pour le premier post de l'année 2020, une implémentation d'un algo très simple de Machine Learning, les k plus proches voisins

knn_from_scratch_blog

Bonjour,

Dans ce post, rédigé incrémentalement, nous allons implémenter un algorithme de machine learning très simple, à savoir celui des k plus proches voisins.

Pour cela, nous allons utiliser le moins de librairie possible, et allons, à quelques exceptions près nous limiter à Python, Numpy et des librairies standard.

L'idée étant d'élaborer cet algorithme en TDD. Cependant, autant l'approche aura été incrémentale et baby-steps, autant la première version de l'implémentation n'a pas été tout à fait élaboré en respectant "parfaitement" cette méthode.

De plus, il est tard et pour respecter mon objectif d'écrire le code et un article en une journée, sachant que je travaille à plein temps hein, et je ne suis pas tout à fait un expert Python non plus. OK j'aurais pu attendre, mais dans le passé ça a mené à de la procrastination et des projets conséquents, presque-fini ... depuis 4 ans.

Ou alors un autre article en cours d'écriture, que j'avais pour objectif d'écrire en 1 semaine en y passant 15-20h, ça fait 1 semaine et demi et j'y ai passé plus de 40h. L'ambition a grandi mais une forme de perfectionnisme s'est glissé, ma motivation et mes réserves se sont épuisés avant d'avoir mis en ligne l'article.

Du coup je préfère une première version bancale qui va s'améliorer itérativement, que quelque chose qui risque de me mener à du perfectionnisme stérile ou à de l'épuisement. Déso pas déso c'est mon blog je fais ce que je veux :p

Sur ce passons au code!

In [2]:
import pandas as pd
import numpy as np
import numpy

import matplotlib.pyplot as plt

from sklearn.datasets import make_circles
from sklearn.neighbors import KNeighborsClassifier
In [17]:
import functools
from collections import Counter

Le premier import sert à utiliser la fonction "reduce". J'ai été surpris, autant il y a un "map" natif, autant j'aurais pensé qu'il y aurait un "reduce" natif, mais non.

Nous allons définir 2 fonctions "helper". Elles ont toutes les 2 été réutilisées à partir de ce cours.

La première sert à afficher un jeu de données 2D à 2 classes. Le second à afficher ce même jeu de données, avec une frontière de décision définie par un modèle.

Nous allons particulièrement utiliser la 2e fonction. Deja c'est utile et enrichissant si je puis dire de pouvoir visualiser une frontière de décision, visualiser son travail, vérifier qu'on n'a pas fait d'erreur, jouer avec différents paramètres, etc.

Mais aussi cela nous servira à valider visuellement que notre modèle est correct, en comparant ses résultats avec ceux obtenus en utilisant l'implémentation des k plus proches voisins de scikit-learn.

In [3]:
def plot_data(pl,X,y):
    pl.plot(X[y==0,0],X[y==0,1], 'ob', alpha=0.5)
    pl.plot(X[y==1,0],X[y==1,1], 'xr', alpha=0.5)
    pl.legend(['0','1'])
    return pl
In [11]:
def plot_decision_boundary(model, X,y):
    amin, bmin = X.min(axis=0) - 0.1
    amax, bmax = X.max(axis=0) + 0.1
    hticks = np.linspace(amin,amax,101)
    vticks = np.linspace(bmin,bmax,101)

    aa,bb = np.meshgrid(hticks, vticks)
    ab = np.c_[aa.ravel(), bb.ravel()]

    c = model.predict(ab)
    Z = c.reshape(aa.shape)
    plt.figure(figsize=(12,8))
    plt.contourf(aa,bb,Z,cmap='bwr', alpha=0.2)
    plot_data(plt,X,y)

Ces 2 méthodes feront certainement l'objet d'un article pour se les approprier, arriver à les écrire de manière autonome, et à réutiliser ailleurs l'insight gagné en les implémentant.

Ne serait-ce que pour moi !

Commençons par créer et visualiser le jeu de données que nous allons utiliser:

In [8]:
x, y = make_circles(n_samples=1000, factor=.7, noise=.1, random_state=42)
plot_data(plt,x,y)
Out[8]:
<module 'matplotlib.pyplot' from '/home/joseph/opt/anaconda3/lib/python3.7/site-packages/matplotlib/pyplot.py'>

On peut utliser la commande plt.show() pour ne pas voir s'afficher:\ <module 'matplotlib.pyplot' from '/home/joseph/opt/anaconda3/lib/python3.7/site-packages/matplotlib/pyplot.py'>

In [9]:
plot_data(plt,x,y)
plt.show()

Voyons maintenant la frontière de décision en utilisant le knn de scikit-learn:

In [12]:
knn = KNeighborsClassifier(n_neighbors=3)

knn.fit(x,y)
plot_decision_boundary(knn,x,y)

Passons maintenant à notre implémentation:

In [15]:
class KNN():
    def __init__(self, n_neighbors=3):
        self.n_neighbors = n_neighbors
        self.counter = 0

    def squared_dist(self, x1, x2):
        assert isinstance(x1, numpy.ndarray)
        assert isinstance(x2, numpy.ndarray)
        return functools.reduce(lambda x, y: x+y, map((lambda t: (t[1] - t[0])**2),zip(x1,x2)))

    def fit(self, x_train, y_train):
        self.data = list(zip(x_train, y_train))

    def predict(self, arg):
        self.counter = 0
        return np.array(list(map(self.predict_internal, arg)))

    def predict_internal(self, arg):
        distance_and_class_fun = lambda x: (self.squared_dist(x[0], arg), x[1])
        distance_and_class = map(distance_and_class_fun, (self.data))
        sorted_by_distance = sorted(distance_and_class, key=lambda x: x[0])
        n_first_sorted_by_distance = sorted_by_distance[:self.n_neighbors]
        classes_sorted_by_distance = map((lambda t: t[1]),n_first_sorted_by_distance)
        predicted_class = Counter(classes_sorted_by_distance).most_common(1)[0][0]
        return predicted_class

Et visualisons la frontière de décision en utilisant notre implémentation (attention notre implem n'est pas super opti, ça prend près d'une minute à calculer )

In [18]:
myknn = KNN(n_neighbors=3)
myknn.fit(x,y)
plot_decision_boundary(myknn,x,y)

Waouh, pas mal hein! En remontant on peut constater que la frontière de décision tracée est exactement la même!

Du coup ça valide que notre algo marche comme il se doit.

Rendez-vous dans un prochain post pour l'écrire en TDD, et dans un autre encore pour écrire le code affichant la frontière de décision.

A la prochaine

Previous Post Next Post