KNN = K Nearests Neighbours = K plus proches voisins
Il s'agit d'un algorithme d'intelligence artificielle permettant de trier, de catégoriser, des individus. L'algorithme KNN peut être utilisé dans des cas semblables à ceux des réseaux de neurones mais en étant plus simple à mettre en œuvre et à comprendre, mais moins performant.
L'algorithme KNN nous sert d'introduction à la notion d'intelligence artificielle.
Aujourd'hui on entend parler de l'intelligence artificielle dans tous les domaines. Mais l'un de domaines de prédilection de l'IA est la classification. On dispose d'individus riches de beaucoup de données et on souhaite mettre une étiquette sur chaque individu pour éventuellement prendre une décision.
Au sens statistique, un individu n'est pas forcément une personne.
On ne veut pas d'une IA dont on doit régler les paramètres à la main. Dans les cas qui nous intéressent, il y a trop de données, trop de réglages à faire. On veut que l'IA se règle toute seule.
Bien sûr, faire tous les réglages à la main prendrait trop de temps, mais ce n'est pas la seule raison. En laissant l'IA faire ses réglages automatiquement, elle peut aboutir à une solution à laquelle on n'aurait pas pensé. Ainsi on peut fournir à la machine une grande quantité de données, même des données qui nous semblent totalement inutiles pour le problème considéré. Il se peut que l'IA trouve un usage à ces données supplémentaires.
L'IA va se régler en utilisant une base de données d'entraînement.
Comme on l'a dit, l'IA a pour mission d'étiqueter des individus. On commence par lui présenter N individus déjà étiquetés.
Exemple : On veut que l'IA devine les préférences politiques d'un individu.
Pour l'entraîner, on va lui fournir une liste d'individus dotés d'attributs divers. Pour chacun d'eux, la préférence politique est déjà connue.
nom, prénom, age, taille, couleur préférée, adresse, emploi, salaire, nombre d'enfants, propriétaire/locataire, …, parti politique préféré.
L'exemple que je choisis est réaliste : on peut se souvenir par exemple du scandale autour de la société Cambridge Analytica.
Une fois l'IA entraînée, elle doit faire ce pourquoi on l'a conçue : On lui présente un individu, sans préciser sa catégorie, et l'IA doit décider seule de l'étiquette à mettre.
Exemple : On fournit à l'IA un individu avec tous ses attributs (nom, prénom, …) mais sans préciser celui que nous recherchons dans cet exemple : la préférence politique. L'IA, en se fondant sur les nombreux exemples qu'elle a vu lors de son entraînement, fournit une réponse.
Après l'entraînement, on s'attend à ce que l'IA donne toujours la bonne réponse pour les individus de sa base d'entraînement. En quelques sorte, elle les a appris par cœur.
Mais sera-t-elle capable de trouver la bonne réponse pour un individu nouveau ?
Pour le savoir, on constitue une base de tests. Il s'agit d'une base qui comme la base d'entraînement, contient toutes les informations. Mais on ne communique pas la réponse à l'IA. On laisse l'IA décider seule et on compare sa réponse avec la bonne réponse.
On peut ensuite évaluer le pourcentage de réussite de l'IA.
Sauf dans des cas très simples, on ne peut attendre de l'IA qu'elle ait 100 % de réussite. Il y a toujours des individus exceptionnels qui ne respectent pas les mêmes règles que les autres.
Notre base d'entraînement est constituée d'individus. On connaît toutes les informations utiles sur eux y compris leur étiquette.
Un individu se présente, appelons le N. On connaît toutes les informations sur lui, mais pas son étiquette. C'est justement cela que l'on cherche.
On cherche les K individus les plus proches de N. parmi ces K individus, on relève l'étiquette majoritaire. On attribut cette étiquette à N.
K est un paramètre de l'algorithme. On peut l'ajuster en fonction des besoins et des résultats obtenus. On choisi souvent K = 3.
Pour savoir qui est proche, on doit calculer des distances. Pour cela il faut encore choisir ce que signifie une distance entre deux individus. Choisir la façon dont on calcule ces distances est le deuxième paramètres important de l'algorithme.
Pour faire fonctionner l'algorithme KNN nous aurons donc besoin :