Aller au contenu

Remarque

On parle d'apprentissage automatique quand un programme construit lui-même, à partir d'exemples, une fonction qu'on ne sait pas écrire directement : reconnaître un chiffre manuscrit, prédire si un message est indésirable, regrouper des clients aux comportements proches... On présente ici les algorithmes au programme. Les codes sont en Python sans bibliothèque, ou en OCaml avec les mêmes noms de fonctions que dans les TP KNN, KNN avec arbres k-d et ID3, qui mettent ces algorithmes en œuvre sur des données réelles.

Apprentissage supervisé

Classification

On dispose d'un ensemble \(X\) d'objets, souvent \(X = \R^d\) où chaque coordonnée est un attribut mesuré sur l'objet, et d'un ensemble fini \(Y\) de classes (ou étiquettes). On suppose qu'il existe une fonction inconnue \(f : X \rightarrow Y\) qu'on cherche à approcher.

Définition

Un jeu de données étiqueté est une suite finie \(((x_1,y_1), \dots, (x_n,y_n))\) d'éléments de \(X \times Y\), où \(y_i\) est la classe de \(x_i\).

Un algorithme d'apprentissage supervisé construit à partir d'un tel jeu de données un classifieur \(\hat{f} : X \rightarrow Y\) qui doit prédire la classe d'objets qui ne sont pas dans le jeu de données.

Exemple

  • \(X\) est l'ensemble des images de \(28 \times 28\) pixels en niveaux de gris, vues comme des éléments de \(\R^{784}\), et \(Y = \range{0}{9}\) : on veut reconnaître des chiffres manuscrits.
  • \(X\) est l'ensemble des courriels et \(Y = \{ \text{indésirable}, \text{légitime} \}\).

Pour évaluer un classifieur, il ne faut pas le tester sur les données qui ont servi à le construire : un classifieur qui apprend par cœur le jeu de données serait parfait sur celui-ci et pourrait être très mauvais ailleurs. On sépare donc les données en un jeu d'entraînement, qui sert à construire \(\hat{f}\), et un jeu de test, qui sert à l'évaluer.

Dans les codes qui suivent, on utilise des points de \(\R^2\) répartis autour de trois centres, la classe d'un point étant l'indice de son centre.

import random

def genere(n, centres, sigma):
    """n points autour de chaque centre, étiquetés par l'indice du centre"""
    donnees = []
    for c, (cx, cy) in enumerate(centres):
        for _ in range(n):
            x = random.gauss(cx, sigma)
            y = random.gauss(cy, sigma)
            donnees.append(((x, y), c))
    random.shuffle(donnees)
    return donnees

Algorithme des \(k\) plus proches voisins

L'idée est très simple : deux objets proches ont sans doute la même classe. On munit \(X = \R^d\) de la distance euclidienne

\[ d(x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} \]

Définition

Soit \(k \in \N^*\). Le classifieur des \(k\) plus proches voisins associé au jeu de données \(((x_1,y_1), \dots, (x_n,y_n))\) associe à \(x \in X\) la classe majoritaire parmi les classes des \(k\) points \(x_i\) les plus proches de \(x\).

Il n'y a ici aucune phase d'entraînement : tout le travail est fait au moment de la prédiction. En cas d'égalité des votes, il faut fixer une règle ; ici, on garde la plus petite classe.

Comme dans le TP KNN avec arbres k-d, un vecteur est un tableau de flottants, les données d'entraînement sont un tableau de couples (vecteur, classe) et la distance est passée en paramètre.

type vector = float array

let distance_2 v1 v2 =
  let s = ref 0. in
  for i = 0 to Array.length v1 - 1 do
    s := !s +. (v1.(i) -. v2.(i)) *. (v1.(i) -. v2.(i))
  done;
  sqrt !s

(* élément le plus fréquent de l, le plus petit en cas d'égalité *)
let majority l =
  let occ = Hashtbl.create 16 in
  List.iter (fun c ->
    let o = try Hashtbl.find occ c with Not_found -> 0 in
    Hashtbl.replace occ c (o + 1)) l;
  let best = ref (List.hd l) in
  Hashtbl.iter (fun c o ->
    let ob = Hashtbl.find occ !best in
    if o > ob || (o = ob && c < !best) then best := c) occ;
  !best

(* les k plus proches voisins de v dans training *)
let k_nearest dist k training v =
  let a = Array.copy training in
  Array.sort (fun (v1, _) (v2, _) -> compare (dist v1 v) (dist v2 v)) a;
  Array.to_list (Array.sub a 0 (min k (Array.length a)))

let nearest_neighbors dist k training v =
  majority (List.map snd (k_nearest dist k training v))

from math import sqrt

def distance_2(x, y):
    return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))


def majority(classes):
    # en cas d'égalité, on renvoie la plus petite classe
    return min(set(classes), key=lambda c: (-classes.count(c), c))


def nearest_neighbors(dist, k, training, x):
    """training est une liste de couples (point, classe)"""
    voisins = sorted(training, key=lambda d: dist(d[0], x))[:k]
    return majority([c for _, c in voisins])

Une prédiction coûte \(O(nd)\) pour calculer les distances et \(O(n \log_2 n)\) pour le tri. On pourrait se contenter de sélectionner les \(k\) plus petites distances, par exemple avec un tas de taille \(k\), en \(O(n \log_2 k)\).

Remarque

  • Le choix de \(k\) est important. Avec \(k = 1\), le classifieur est très sensible aux points mal étiquetés ou atypiques. Avec \(k = n\), il renvoie toujours la classe majoritaire du jeu de données. On choisit \(k\) en comparant les résultats sur un jeu de test. Avec deux classes, un \(k\) impair évite les égalités de votes.
  • La distance euclidienne suppose que les attributs sont comparables. Si un attribut est une taille en mètres et un autre un revenu en euros, le second écrase le premier. On commence alors par normaliser les attributs, par exemple en les ramenant dans \([0,1]\) : si \(m\) et \(M\) sont les valeurs minimale et maximale d'un attribut, on remplace chaque valeur \(v\) par \(\frac{v-m}{M-m}\). C'est ce qui est fait dans le TP KNN avec arbres k-d, où l'on compare des statistiques de pokémons de natures très différentes.

Arbres k-dimensionnels

Quand le jeu d'entraînement est grand et la dimension \(d\) petite, on peut éviter de calculer les \(n\) distances à chaque prédiction en rangeant les points dans un arbre k-d (arbre \(k\)-dimensionnel ; ici le \(k\) désigne la dimension, notée \(d\), et n'a rien à voir avec le nombre de voisins). C'est l'objet du TP KNN avec arbres k-d, dont on reprend les notations.

Définition

Un arbre k-d sur des points de \(\R^d\) est un arbre binaire dont chaque nœud contient un point \(w\) et une dimension \(\mathrm{dim} \in \range{0}{d-1}\), tel que tous les points \(x\) du sous-arbre gauche vérifient \(x_{\mathrm{dim}} \le w_{\mathrm{dim}}\) et tous ceux du sous-arbre droit vérifient \(x_{\mathrm{dim}} \ge w_{\mathrm{dim}}\).

type 'a kd_tree =
  | Nil
  | Node of (vector * 'a) * int * 'a kd_tree * 'a kd_tree

Le type 'a est celui des données associées aux points, ici les classes.

Construction. Pour construire un arbre k-d à partir d'un tableau de points en partant de la dimension \(\mathrm{dim}\), on trie le tableau selon la coordonnée \(\mathrm{dim}\), on place l'élément médian à la racine et on construit récursivement les sous-arbres avec les éléments strictement à gauche et strictement à droite de la médiane, en passant à la dimension \((\mathrm{dim}+1) \bmod d\). L'arbre obtenu est équilibré : sa hauteur est \(\lfloor \log_2 n \rfloor + 1\). Avec un tri en \(O(m \log_2 m)\) pour un tableau de taille \(m\), la construction coûte \(O(n \log_2^2 n)\).

let rec kd_build a d n =
  let len = Array.length a in
  if len = 0 then Nil
  else begin
    let a = Array.copy a in
    Array.sort (fun (v1, _) (v2, _) -> compare v1.(d) v2.(d)) a;
    let m = len / 2 in
    let d' = (d + 1) mod n in
    Node (a.(m), d,
          kd_build (Array.sub a 0 m) d' n,
          kd_build (Array.sub a (m + 1) (len - m - 1)) d' n)
  end

Recherche des \(k\) plus proches voisins. On utilise une distance \(\mathrm{dist}\) telle que \(|x_i - y_i| \le \mathrm{dist}(x, y)\) pour toute coordonnée \(i\), ce qui est le cas des distances \(d_1\) et \(d_2\). Pour chercher les \(k\) plus proches voisins de \(v\) dans un nœud \((w, \mathrm{dim}, g, d)\) :

  • on cherche récursivement dans le sous-arbre du côté de \(v\) (\(g\) si \(v_{\mathrm{dim}} \le w_{\mathrm{dim}}\), \(d\) sinon), ce qui donne une liste vois1 ;
  • si vois1 contient \(k\) points tous à distance au plus \(|v_{\mathrm{dim}} - w_{\mathrm{dim}}|\) de \(v\), on renvoie vois1 ;
  • sinon, on cherche aussi dans l'autre sous-arbre, ce qui donne vois2, et on renvoie les \(k\) plus proches de \(v\) parmi vois1, vois2 et \(w\).
(* les k premiers éléments d'une liste *)
let rec prefix k l =
  match l with
  | x :: q when k > 0 -> x :: prefix (k - 1) q
  | _ -> []

let rec kd_search_knn dist k t v =
  match t with
  | Nil -> []
  | Node ((w, c), dim, g, d) ->
    let first, other = if v.(dim) <= w.(dim) then g, d else d, g in
    let vois1 = kd_search_knn dist k first v in
    let sep = abs_float (v.(dim) -. w.(dim)) in
    if List.length vois1 = k
       && List.for_all (fun (v', _) -> dist v v' <= sep) vois1
    then vois1
    else begin
      let vois2 = kd_search_knn dist k other v in
      let l = List.sort
          (fun (v1, _) (v2, _) -> compare (dist v1 v) (dist v2 v))
          ((w, c) :: vois1 @ vois2) in
      prefix k l
    end

Théorème

kd_search_knn dist k t v renvoie \(\min(k, |t|)\) points de \(t\) tels qu'aucun point de \(t\) non renvoyé ne soit strictement plus proche de \(v\) qu'un point renvoyé.

Preuve

Par induction sur l'arbre. C'est immédiat pour Nil. Pour un nœud, on suppose, par hypothèse d'induction, que vois1 est formée de \(k\) plus proches voisins de \(v\) dans le sous-arbre exploré (ou de tous ses points s'il en a moins de \(k\)), et de même pour vois2.

  • Si on explore les deux sous-arbres, tout point de \(t\) est \(w\), ou un point de vois1 ou de vois2, ou un point d'un sous-arbre qui est à distance au moins égale à celle de chacun des \(k\) points de la liste correspondante. En gardant les \(k\) plus proches de l'union, on obtient bien \(k\) plus proches voisins dans \(t\) (ou tous les points de \(t\) s'il y en a au plus \(k\)).
  • Sinon, vois1 contient \(k\) points à distance au plus \(s = |v_{\mathrm{dim}} - w_{\mathrm{dim}}|\) de \(v\). Supposons par exemple \(v_{\mathrm{dim}} \le w_{\mathrm{dim}}\) : tout point \(x\) du sous-arbre droit, ainsi que \(w\), vérifie \(x_{\mathrm{dim}} \ge w_{\mathrm{dim}}\), donc \(\mathrm{dist}(v, x) \ge x_{\mathrm{dim}} - v_{\mathrm{dim}} \ge s\). Ces points ne sont donc pas strictement plus proches que ceux de vois1, qui convient. Le cas \(v_{\mathrm{dim}} > w_{\mathrm{dim}}\) est symétrique.

On en déduit les \(k\) plus proches voisins en appliquant majority aux classes des points renvoyés. Dans le pire cas, on explore tout l'arbre et la recherche coûte \(O(n)\) calculs de distances, plus le coût des tris des listes. En pratique, en petite dimension, une grande partie des sous-arbres est éliminée : dans le TP, en dimension \(6\) avec \(750\) points d'entraînement, on évite environ deux tiers des calculs de distances pour \(k = 1\). Cet avantage disparaît quand la dimension augmente (pour les images MNIST, \(d = 784\)) : on parle de fléau de la dimension.

Matrice de confusion

Pour évaluer un classifieur sur un jeu de test, le taux de réussite ne suffit pas toujours : on veut savoir quelles classes sont confondues.

Définition

Soit \(Y = \{ c_1, \dots, c_p \}\). La matrice de confusion d'un classifieur \(\hat{f}\) sur un jeu de test \(((x_1,y_1), \dots, (x_m,y_m))\) est la matrice \(M \in \mathcal{M}_p(\N)\) où \(M_{i,j}\) est le nombre d'indices \(k\) tels que \(y_k = c_i\) et \(\hat{f}(x_k) = c_j\).

La somme des coefficients vaut \(m\), les coefficients diagonaux comptent les bonnes prédictions et le taux de réussite est \(\mathop{tr}(M) / m\). Un classifieur parfait a une matrice de confusion diagonale.

def matrice_confusion(k, training, test, nb_classes):
    m = [[0] * nb_classes for _ in range(nb_classes)]
    for x, c in test:
        m[c][nearest_neighbors(distance_2, k, training, x)] += 1
    return m

Exemple

Dans le TP KNN, on reconnaît des chiffres manuscrits de la base MNIST : des images de \(28 \times 28\) pixels, avec \(60\,000\) images d'entraînement et \(10\,000\) images de test. Avec la distance euclidienne et \(k = 3\), on obtient la matrice de confusion suivante (ligne : vraie classe, colonne : classe prédite).

0 1 2 3 4 5 6 7 8 9
0 974 1 1 0 0 1 2 1 0 0
1 0 1133 2 0 0 0 0 0 0 0
2 10 9 996 2 0 0 0 13 2 0
3 0 2 4 976 1 13 1 7 3 3
4 1 6 0 0 950 0 4 2 0 19
5 6 1 0 11 2 859 5 1 3 4
6 5 3 0 0 3 3 944 0 0 0
7 0 21 5 0 1 0 0 991 0 10
8 8 2 4 16 8 11 3 4 914 4
9 4 5 2 8 9 2 1 8 2 968

La trace vaut \(9705\), soit un taux de réussite de \(97{,}05\,\%\). Au-delà de ce taux global, on lit les confusions les plus fréquentes : \(21\) chiffres \(7\) classés comme des \(1\), \(19\) chiffres \(4\) classés comme des \(9\), \(16\) chiffres \(8\) classés comme des \(3\). Avec \(k = 1\), le taux de réussite est de \(96{,}91\,\%\).

Remarque

Pour deux classes, positive et négative, on parle de vrais positifs, faux positifs, vrais négatifs et faux négatifs. Selon l'application, les deux types d'erreurs n'ont pas la même gravité : pour un test médical de dépistage, un faux négatif est bien plus grave qu'un faux positif.

Arbres de décision et algorithme ID3

On considère maintenant des attributs qui prennent un nombre fini de valeurs : \(X = A_1 \times \dots \times A_d\) où chaque \(A_i\) est fini.

Définition

Un arbre de décision est un arbre dont chaque nœud interne est étiqueté par un attribut \(i\) et possède un fils pour chaque valeur de \(A_i\), et dont chaque feuille est étiquetée par une classe.

Pour classer \(x = (a_1, \dots, a_d)\), on part de la racine et, sur un nœud étiqueté par \(i\), on descend dans le fils correspondant à la valeur \(a_i\) jusqu'à atteindre une feuille, dont l'étiquette est la classe prédite.

Exemple

On veut prédire si on va jouer au tennis selon la météo, avec les attributs Ciel \(\in \{ \text{soleil}, \text{couvert}, \text{pluie} \}\), Température \(\in \{ \text{chaud}, \text{doux}, \text{frais} \}\), Humidité \(\in \{ \text{élevée}, \text{normale} \}\) et Vent \(\in \{ \text{faible}, \text{fort} \}\). On dispose de 14 exemples (jeu de données classique dû à Quinlan, l'auteur d'ID3) :

Ciel Température Humidité Vent Tennis
soleil chaud élevée faible non
soleil chaud élevée fort non
couvert chaud élevée faible oui
pluie doux élevée faible oui
pluie frais normale faible oui
pluie frais normale fort non
couvert frais normale fort oui
soleil doux élevée faible non
soleil frais normale faible oui
pluie doux normale faible oui
soleil doux normale fort oui
couvert doux élevée fort oui
couvert chaud normale faible oui
pluie doux élevée fort non

On peut toujours construire un arbre de décision qui classe correctement tous les exemples, s'ils ne sont pas contradictoires, mais on cherche un arbre petit, qui généralise mieux. Trouver un plus petit arbre est un problème difficile, et l'algorithme ID3 utilise une heuristique gloutonne : on place à la racine l'attribut qui sépare le mieux les exemples, puis on recommence dans chaque sous-arbre. Pour mesurer la qualité d'une séparation, on utilise l'entropie, qui mesure le désordre d'un ensemble d'exemples.

Définition

Soit \(S\) un ensemble fini et non vide d'exemples étiquetés et, pour chaque classe \(c\), \(p_c\) la proportion d'exemples de \(S\) de classe \(c\). L'entropie de \(S\) est

\[ H(S) = - \sum_{c,\ p_c > 0} p_c \log_2 p_c \]

Propriété

Si \(S\) contient des exemples de \(p\) classes, alors \(0 \le H(S) \le \log_2 p\). De plus, \(H(S) = 0\) si et seulement si tous les exemples de \(S\) ont la même classe, et \(H(S) = \log_2 p\) si et seulement si les \(p\) classes ont la même proportion.

Preuve

Comme \(0 < p_c \le 1\), chaque terme \(-p_c \log_2 p_c\) est positif, et nul si et seulement si \(p_c = 1\), d'où le premier point. Pour le second, on utilise la concavité stricte de \(\log_2\) (inégalité de Jensen) avec les poids \(p_c\) qui sont de somme \(1\) :

\[ H(S) = \sum_c p_c \log_2 \frac{1}{p_c} \le \log_2 \left( \sum_c p_c \frac{1}{p_c} \right) = \log_2 p \]

avec égalité si et seulement si tous les \(1/p_c\) sont égaux.

Remarque

Avec deux classes, si \(p\) est la proportion d'exemples de la première classe, on a \(H(S) = B(p)\) où

\[ B(p) = -p \log_2 p - (1-p) \log_2 (1-p) \]

en prolongeant par continuité \(B(0) = B(1) = 0\). C'est cette fonction qu'on utilise dans le TP ID3, où les classes sont les booléens true et false.

Définition

Soit \(S\) un ensemble d'exemples et \(i\) un attribut. Pour \(a \in A_i\), on note \(S_a\) l'ensemble des exemples de \(S\) dont l'attribut \(i\) vaut \(a\). Le gain d'information de \(i\) sur \(S\) est

\[ G(S, i) = H(S) - \sum_{a \in A_i,\ S_a \neq \emptyset} \frac{|S_a|}{|S|} H(S_a) \]

C'est la diminution de l'entropie moyenne obtenue en séparant \(S\) selon l'attribut \(i\). L'algorithme ID3 construit l'arbre récursivement à partir d'un ensemble d'exemples \(S\) et d'un ensemble d'attributs disponibles \(A\) :

  • si tous les exemples de \(S\) ont la même classe, on renvoie une feuille étiquetée par cette classe ;
  • si \(A\) est vide, on renvoie une feuille étiquetée par la classe majoritaire de \(S\) ;
  • sinon, on choisit l'attribut \(i \in A\) de gain \(G(S,i)\) maximal et on crée un nœud étiqueté par \(i\) dont les fils sont les arbres construits récursivement à partir des \(S_a\) et de \(A \setminus \{ i \}\).

Un ensemble \(S_a\) peut être vide quand aucun exemple n'a la valeur \(a\) pour l'attribut \(i\) : on renvoie alors une feuille étiquetée par la classe majoritaire de l'ensemble \(S\) du nœud parent. C'est le rôle du paramètre prec_s dans le TP. La version python ci-dessous ne crée pas ces fils et traite ce cas au moment de la prédiction.

L'algorithme termine car le nombre d'attributs disponibles diminue à chaque appel récursif, et les feuilles construites classent correctement les exemples dès qu'il n'y en a pas deux de mêmes attributs et de classes différentes.

Dans la version ocaml, qui est celle du TP ID3, les attributs sont booléens : un exemple est un couple (values, b) où values est un bool array et b la classe, et un nœud Node (i, t_yes, t_no) teste la valeur de l'attribut i. Dans la version python, un exemple est un couple (x, c) où x est un tuple de valeurs d'attributs quelconques, et un arbre est soit une classe, soit un couple formé d'un indice d'attribut et d'un dictionnaire associant à chaque valeur le sous-arbre correspondant.

type samples = (bool array * bool) list

type decision_tree =
    Node of int * decision_tree * decision_tree
  | Leaf of bool

let rec eval_tree t values =
  match t with
  | Leaf b -> b
  | Node (i, t_yes, t_no) ->
    if values.(i) then eval_tree t_yes values else eval_tree t_no values

(* classe majoritaire, true en cas d'égalité *)
let majority s =
  let n = List.length s in
  let p = List.length (List.filter snd s) in
  2 * p >= n

let b p =
  if p <= 1e-12 || p >= 1. -. 1e-12 then 0.
  else -. p *. Float.log2 p -. (1. -. p) *. Float.log2 (1. -. p)

let entropy s =
  let n = List.length s in
  let p = List.length (List.filter snd s) in
  if n = 0 then 0. else b (float_of_int p /. float_of_int n)

let gain s i =
  let s_yes, s_no = List.partition (fun (v, _) -> v.(i)) s in
  let n = float_of_int (List.length s) in
  entropy s
  -. float_of_int (List.length s_yes) /. n *. entropy s_yes
  -. float_of_int (List.length s_no) /. n *. entropy s_no

(* s : exemples courants, prec_s : exemples du parent,
   free : attributs disponibles *)
let rec id3_rec s prec_s free =
  if s = [] then Leaf (majority prec_s)
  else if List.for_all snd s then Leaf true
  else if not (List.exists snd s) then Leaf false
  else if free = [] then Leaf (majority s)
  else begin
    let best = List.fold_left
        (fun i j -> if gain s j > gain s i then j else i)
        (List.hd free) free in
    let s_yes, s_no = List.partition (fun (v, _) -> v.(best)) s in
    let free' = List.filter (fun j -> j <> best) free in
    Node (best, id3_rec s_yes s free', id3_rec s_no s free')
  end

let id3 s vars = id3_rec s s (List.init vars (fun i -> i))

from math import log2

def entropie(exemples):
    """exemples est une liste de couples (attributs, classe)"""
    n = len(exemples)
    effectifs = {}
    for _, c in exemples:
        effectifs[c] = effectifs.get(c, 0) + 1
    return -sum(e / n * log2(e / n) for e in effectifs.values())


def partition(exemples, a):
    """regroupe les exemples selon la valeur de l'attribut a"""
    parts = {}
    for x, c in exemples:
        parts.setdefault(x[a], []).append((x, c))
    return parts


def gain(exemples, a):
    n = len(exemples)
    parts = partition(exemples, a)
    return entropie(exemples) - sum(len(p) / n * entropie(p)
                                    for p in parts.values())


def majoritaire(exemples):
    classes = [c for _, c in exemples]
    return max(set(classes), key=classes.count)


def id3(exemples, attributs):
    """renvoie soit une classe (feuille),
    soit un couple (attribut, dictionnaire valeur -> sous-arbre)"""
    classes = set(c for _, c in exemples)
    if len(classes) == 1:
        return classes.pop()
    if attributs == []:
        return majoritaire(exemples)
    a = max(attributs, key=lambda b: gain(exemples, b))
    restants = [b for b in attributs if b != a]
    return (a, {v: id3(p, restants)
                for v, p in partition(exemples, a).items()})


def predit(arbre, x, defaut):
    while isinstance(arbre, tuple):
        a, fils = arbre
        if x[a] not in fils:  # valeur jamais vue à l'entraînement
            return defaut
        arbre = fils[x[a]]
    return arbre

Exemple

Sur les 14 exemples précédents, 9 sont positifs et 5 négatifs, donc \(H(S) = -\frac{9}{14} \log_2 \frac{9}{14} - \frac{5}{14} \log_2 \frac{5}{14} \approx 0{,}940\). Les gains des attributs sont environ :

Ciel Température Humidité Vent
0,247 0,029 0,152 0,048

L'attribut Ciel est placé à la racine. Les exemples où le ciel est couvert sont tous positifs. On obtient finalement l'arbre suivant, qui classe correctement les 14 exemples en n'utilisant pas la température :

  • Ciel = soleil : Humidité = élevée \(\rightarrow\) non, Humidité = normale \(\rightarrow\) oui ;
  • Ciel = couvert \(\rightarrow\) oui ;
  • Ciel = pluie : Vent = faible \(\rightarrow\) oui, Vent = fort \(\rightarrow\) non.

Remarque

  • Un arbre trop profond colle aux exemples, y compris à leurs erreurs, et généralise mal : on parle de sur-apprentissage. On peut limiter la profondeur de l'arbre ou élaguer les branches qui n'améliorent pas les résultats sur un jeu de test.
  • Si une valeur d'attribut n'apparaît jamais dans les exemples d'un nœud, la fonction predit renvoie une classe par défaut, par exemple la classe majoritaire du jeu d'entraînement.

Apprentissage non-supervisé

Partitionnement

On ne dispose plus des classes : on a seulement des points \(x_1, \dots, x_n \in \R^d\) et on cherche à les regrouper en groupes (ou clusters) de points proches. Par exemple, on peut vouloir regrouper des clients selon leurs achats sans savoir à l'avance quels profils existent.

Définition

Un partitionnement de \(\{ x_1, \dots, x_n \}\) en \(k\) groupes est une application \(c : \range{1}{n} \rightarrow \range{1}{k}\), \(c(j)\) étant le groupe du point \(x_j\).

Il n'y a pas ici de « bonne réponse » à laquelle se comparer : la qualité d'un partitionnement dépend d'un critère qu'on se fixe.

Algorithme des \(k\)-moyennes

On mesure la qualité d'un partitionnement \(c\) associé à des centres \(\mu_1, \dots, \mu_k \in \R^d\) par l'inertie

\[ J(c, \mu) = \sum_{j=1}^n \| x_j - \mu_{c(j)} \|^2 \]

qu'on cherche à minimiser. Minimiser exactement \(J\) est un problème difficile et on utilise l'heuristique suivante, due à Lloyd.

  • On choisit \(k\) centres initiaux, par exemple \(k\) points du jeu de données, et on affecte chaque point au centre le plus proche.
  • Tant que l'affectation change :
    • on remplace chaque centre \(\mu_i\) par le barycentre des points du groupe \(i\) ;
    • on affecte chaque point au centre le plus proche, en ne changeant le groupe d'un point que si un autre centre est strictement plus proche.

Comme dans le TP KNN avec arbres k-d, la fonction k_means dist data k prend la distance en paramètre et renvoie le couple (classes, centers) où classes.(j) est le groupe de data.(j).

let barycentre points =
  let n = List.length points in
  let dim = Array.length (List.hd points) in
  let b = Array.make dim 0. in
  List.iter (fun p ->
    Array.iteri (fun i v -> b.(i) <- b.(i) +. v /. float_of_int n) p) points;
  b

let plus_proche dist centers x =
  let meilleur = ref 0 in
  for i = 1 to Array.length centers - 1 do
    if dist centers.(i) x < dist centers.(!meilleur) x
    then meilleur := i
  done;
  !meilleur

(* on suppose 1 <= k <= Array.length data ; les k premiers points
   servent de centres initiaux *)
let k_means dist data k =
  let centers = Array.init k (fun i -> Array.copy data.(i)) in
  let classes = Array.map (plus_proche dist centers) data in
  let change = ref true in
  while !change do
    (* mise à jour des centres *)
    for i = 0 to k - 1 do
      let groupe = ref [] in
      Array.iteri (fun j x -> if classes.(j) = i then groupe := x :: !groupe)
        data;
      if !groupe <> [] then centers.(i) <- barycentre !groupe
    done;
    (* affectation de chaque point au centre le plus proche *)
    change := false;
    Array.iteri (fun j x ->
      let i = plus_proche dist centers x in
      if dist centers.(i) x < dist centers.(classes.(j)) x then begin
        classes.(j) <- i;
        change := true
      end) data
  done;
  classes, centers

def barycentre(points):
    n = len(points)
    return tuple(sum(p[i] for p in points) / n for i in range(len(points[0])))


def plus_proche(dist, centers, x):
    return min(range(len(centers)), key=lambda i: dist(centers[i], x))


def k_means(dist, data, k):
    # on suppose 1 <= k <= len(data) ; les k premiers points
    # servent de centres initiaux
    centers = list(data[:k])
    classes = [plus_proche(dist, centers, x) for x in data]
    change = True
    while change:
        # mise à jour des centres
        for i in range(k):
            groupe = [x for x, c in zip(data, classes) if c == i]
            if groupe != []:
                centers[i] = barycentre(groupe)
        # affectation de chaque point au centre le plus proche
        change = False
        for j, x in enumerate(data):
            i = plus_proche(dist, centers, x)
            if dist(centers[i], x) < dist(centers[classes[j]], x):
                classes[j] = i
                change = True
    return classes, centers

Remarque

Un groupe peut devenir vide. Dans ce cas, on conserve son ancien centre.

Lemme

Soit \(C\) un ensemble fini et non vide de points de \(\R^d\), de barycentre \(m\). Pour tout \(\mu \in \R^d\),

\[ \sum_{x \in C} \| x - \mu \|^2 = \sum_{x \in C} \| x - m \|^2 + |C| \, \| m - \mu \|^2 \]

En particulier, le barycentre minimise \(\mu \mapsto \sum_{x \in C} \| x - \mu \|^2\).

Preuve

On développe \(\| x - \mu \|^2 = \| (x - m) + (m - \mu) \|^2 = \| x - m \|^2 + 2 \langle x - m, m - \mu \rangle + \| m - \mu \|^2\), puis on somme sur \(x \in C\) : le terme central est nul car \(\sum_{x \in C} (x - m) = 0\) par définition du barycentre.

Théorème

L'algorithme des \(k\)-moyennes termine, et l'inertie décroît au cours de l'algorithme.

Preuve

Pour une affectation \(c\), on note \(m(c)\) les centres obtenus après la mise à jour à partir de \(c\) et \(I(c) = J(c, m(c))\). Considérons un tour de boucle qui commence avec l'affectation \(c\) et se termine avec l'affectation \(c'\).

  • Lors de l'affectation, chaque point qui change de groupe se rapproche strictement de son centre, et les autres termes ne changent pas. Donc si \(c' \neq c\), \(J(c', m(c)) < J(c, m(c)) = I(c)\).
  • Lors de la mise à jour suivante, d'après le lemme appliqué à chaque groupe non vide de \(c'\), \(I(c') = J(c', m(c')) \le J(c', m(c))\).

Ainsi, tant que l'affectation change, \(I\) décroît strictement. Une même affectation ne peut donc pas apparaître deux fois. Comme il n'y a que \(k^n\) affectations possibles, l'algorithme termine.

Remarque

  • Chaque tour de boucle coûte \(O(nkd)\). La borne \(k^n\) sur le nombre de tours est très pessimiste : en pratique, l'algorithme converge en peu de tours.
  • L'algorithme aboutit à un minimum local : aucun point ne gagne à changer de groupe, mais ce n'est pas forcément un minimum de \(J\). Le résultat dépend des centres initiaux, et on relance souvent l'algorithme avec plusieurs initialisations aléatoires en gardant le résultat de plus petite inertie.
  • Il faut choisir \(k\) à l'avance. On peut comparer les inerties obtenues pour plusieurs valeurs de \(k\), sachant que l'inertie optimale décroît quand \(k\) augmente.

Exemple

Sur 90 points générés autour de \((0,0)\), \((5,0)\) et \((2,5;4)\) avec un écart-type de \(0{,}7\), l'algorithme avec \(k = 3\) retrouve des centres proches de \((0{,}15;-0{,}01)\), \((4{,}87;-0{,}15)\) et \((2{,}57;4{,}32)\).

Classification hiérarchique ascendante

Plutôt que de fixer \(k\) dès le départ, on peut construire une hiérarchie de regroupements :

  • au départ, chaque point forme un groupe ;
  • tant qu'il reste plus d'un groupe, on fusionne les deux groupes les plus proches.

On obtient un arbre binaire, appelé dendrogramme, dont les feuilles sont les points et dont chaque nœud interne correspond à une fusion. En arrêtant les fusions quand il reste \(k\) groupes, on obtient un partitionnement en \(k\) groupes.

Il faut définir une distance entre groupes. Les choix classiques pour deux groupes \(G\) et \(G'\) sont :

  • le saut minimal : \(\min \enscomp{d(x,y)}{x \in G, y \in G'}\) ;
  • le saut maximal : \(\max \enscomp{d(x,y)}{x \in G, y \in G'}\) ;
  • la distance entre les barycentres de \(G\) et \(G'\).

Le code suivant utilise le saut minimal et s'arrête quand il reste \(k\) groupes.

def distance_min(g1, g2):
    return min(distance_2(x, y) for x in g1 for y in g2)


def cah(points, k):
    groupes = [[x] for x in points]
    while len(groupes) > k:
        # recherche des deux groupes les plus proches
        _, i, j = min((distance_min(groupes[i], groupes[j]), i, j)
                      for i in range(len(groupes))
                      for j in range(i + 1, len(groupes)))
        groupes[i] = groupes[i] + groupes[j]
        groupes.pop(j)
    return groupes

Cette implémentation directe est très coûteuse : chaque fusion recalcule toutes les distances entre points de groupes différents, soit \(O(n^2)\) calculs de distances, et il y a \(n - k\) fusions, d'où une complexité en \(O(n^3)\). On peut faire mieux en conservant une matrice des distances entre groupes et en la mettant à jour après chaque fusion.

Remarque

Avec le saut minimal, fusionner les deux groupes les plus proches revient à ajouter l'arête la plus courte entre deux groupes différents du graphe complet pondéré par les distances : c'est exactement l'algorithme de Kruskal, arrêté quand il reste \(k\) composantes connexes.

Recherche informée

L'algorithme A* est mis en œuvre sur le taquin dans le TP Résolution du 15-puzzle.