Introduction à l'intelligence artificielle

Pr. EL HADIQ Zouhair

Apprentissage automatique : KNN & K-means — CPGE MP / PSI

1 / 13

Qu'est-ce que l'IA ?DÉFINITION

Branche de l'informatique visant à doter les machines de capacités d'intelligence : percevoir, raisonner, décider, apprendre.

Programmation classiqueApprentissage automatique
données + programme ⇒ résultatdonnées + résultats ⇒ modèle
Intérêt. Pour les tâches trop complexes à coder à la main (reconnaître un chiffre, filtrer un spam), on apprend les règles à partir des données.
2 / 13

Les sous-domaines de l'IAPANORAMA

Sous-domaineExemple courant
Apprentissage automatique (ML)Recommandations, anti-spam
Vision par ordinateurReconnaissance faciale
Traitement du langage (NLP)Traduction, assistants vocaux
RobotiqueVéhicules autonomes
Systèmes expertsAide au diagnostic médical
Au programme. Le ML, avec KNN (classification) et K-means (segmentation).
3 / 13

Les trois familles d'apprentissageML

TypeDonnéesBut
Superviséétiquetéesprédire l'étiquette (KNN)
Non supervisénon étiquetéesdécouvrir des groupes (K-means)
Par renforcementrécompensesapprendre une stratégie

Chaque donnée est un vecteur de caractéristiques (features).

4 / 13

Classification superviséeSUPERVISÉ

Jeu de données étiqueté : couples $(x, y)$, $x$ = caractéristiques, $y$ = classe connue. On apprend $x \to y$ pour prédire de nouvelles données.

Idée clé. Prédire la classe de nouvelles données à partir d'exemples déjà étiquetés.
5 / 13

L'algorithme KNNk-NN

Un point ressemble à ses voisins. Pour classer un point $x$ :

  1. Calculer la distance de $x$ à tous les points étiquetés.
  2. Garder les $k$ plus proches.
  3. Voter : classe majoritaire parmi eux.

Distance euclidienne : $d(a,b)=\sqrt{\sum_{i=1}^{n}(a_i-b_i)^2}$

Astuce. Pour comparer des distances, inutile de prendre la racine : comparer les distances au carré.
6 / 13

KNN en PythonCODE

from collections import Counter def distance(a, b): return sum((a[i]-b[i])**2 for i in range(len(a)))**0.5 def knn(donnees, etiq, x, k): d = [(distance(x, donnees[i]), etiq[i]) for i in range(len(donnees))] d.sort(key=lambda c: c[0]) voisins = [c for (_, c) in d[:k]] return Counter(voisins).most_common(1)[0][0]

KNN = apprentissage « paresseux » : aucun entraînement, tout se calcule à la prédiction.

7 / 13

La matrice de confusionÉVALUATION

Prédit +Prédit −
Réel +VPFN
Réel −FPVN
Piège. 95 % de mails légitimes ⇒ « toujours non-spam » = 95 % d'exactitude, mais inutile. D'où précision & rappel.
8 / 13

Bien choisir kRÉGLAGE

On teste plusieurs $k$, on compare les matrices de confusion, on garde le meilleur. $k$ impair à 2 classes pour éviter les égalités.

9 / 13

Segmentation non superviséeCLUSTERING

Données non étiquetées : on cherche une structure cachée. La segmentation regroupe les éléments en clusters homogènes.

Exemples. Profils de clientèle, regroupement d'articles, réduction du nombre de couleurs d'une image.
10 / 13

L'algorithme K-meansk-moyennes

Partitionner en $k$ clusters, chacun représenté par son centre (centroïde).

  1. Initialiser $k$ centres.
  2. Affecter chaque point au centre le plus proche.
  3. Recalculer chaque centre = moyenne de ses points.
  4. Répéter jusqu'à stabilisation.

Minimise l'inertie : $I=\sum_{C}\sum_{x\in C} d(x,\,\mu_C)^2$

11 / 13

K-means : convergenceCODE

def kmeans(donnees, centres, iter_max=100): for _ in range(iter_max): groupes = [[] for _ in centres] for x in donnees: j = plus_proche(x, centres) groupes[j].append(x) nouveaux = [moyenne(g) if g else centres[j] for j, g in enumerate(groupes)] if nouveaux == centres: break centres = nouveaux return centres
Minimum local. L'inertie décroît à chaque étape ⇒ convergence, mais le résultat dépend de l'initialisation. On relance plusieurs fois.
12 / 13

RécapitulatifBILAN

13 / 13