Algorithme KNN

KNN = K Nearests Neighbours = K plus proches voisins

Principes de l'IA en général

L'algo KNN est un exemple d'IA

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.

Exemples d'aide au tri avec IA

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.

Un service bancaire en ligne pose une série de question à l'utilisateur. À partir des réponses, il produit une suggestion de placement adapté.
On fait des mesures biomédicales sur un patient, l'algorithme déduit un diagnostic.
Dans une entreprise, dans le cadre d'un système de sécurité, une caméra prend une image d'une personne qui se présente, l'algorithme décide de quel employé il s'agit.
…

Entraînement

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.

Décision

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.

base de tests

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.

cela peut être sans importance, par exemple si l'IA sert à cibler les clients d'une campagnes publicitaire,
cela peut être plus grave, par exemple si l'IA produit des diagnostics médicaux. Mais un médecin peut se tromper aussi. Il faut que l'IA fasse moins d'erreur que l'humain.
cela peut engendrer de grandes difficultés morales : drones militaires armés, voiture autonome en cas d'accident.

Cas particulier de l'algorithme KNN

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 :

de choisir K,
d'une base d'entraînement,
de choisir comment on calcule les distances entre les individus.