informatique (MP2I/MPI) · Chapitre 26 · Application directe du cours

Problème — Le dendrogramme : deux liens, et où couper

Apprentissage automatique · niveau 3 (difficile)

Énoncé

Écrire la classification hiérarchique ascendante en OCaml, paramétrée par le lien.
Sur les cinq points de l'exercice 26.8, expliquer pourquoi le lien simple relie $a$ et $d$ alors qu'ils sont à distance $6$ .
Justifier la complexité $O (n^{3})$ annoncée par le cours, et dire comment on descend à $O (n^{2} lo g n)$ .
À quelle hauteur couper ?

Corrigé de la question 1

1. Le code.


type arbre = Feuille of string | Fusion of arbre * arbre * float

let rec noms = function
  | Feuille s -> [s]
  | Fusion (a, b, _) -> noms a @ noms b

(* Distance entre deux paquets. complet = true donne le lien complet
   (maximum), false le lien simple (minimum). Complexité : Theta(|a|·|b|). *)
let lien complet dist a b =
  let l = List.concat_map (fun u -> List.map (dist u) (noms b)) (noms a) in
  if complet then List.fold_left max neg_infinity l
  else List.fold_left min infinity l

(* Dendrogramme des points. Précondition : la liste est non vide.
   Terminaison : chaque tour réduit le nombre de paquets de 1.
   Complexité : O(n³). *)
let cha complet dist points =
  let paquets = ref (List.map (fun s -> Feuille s) points) in
  while List.length !paquets > 1 do
    let meilleur = ref None in
    List.iteri (fun i a -> List.iteri (fun j b ->
        if i < j then begin
          let d = lien complet dist a b in
          match !meilleur with
          | Some (_, _, dm) when dm <= d -> ()
          | _ -> meilleur := Some (a, b, d)
        end) !paquets) !paquets;
    match !meilleur with
    | None -> ()
    | Some (a, b, d) ->
        paquets := Fusion (a, b, d) :: List.filter (fun p -> p != a && p != b) !paquets
  done;
  List.hd !paquets

(* Les paquets obtenus en coupant le dendrogramme à la hauteur h. *)
let rec coupe h = function
  | Feuille s -> [[s]]
  | Fusion (a, b, hh) -> if hh <= h then [noms a @ noms b] else coupe h a @ coupe h b

Terminaison : le variant est le nombre de paquets, qui décroît de $1$ à chaque tour et reste positif ; la boucle fait exactement $n - 1$ tours. Le != de la dernière ligne est délibéré : c'est l'égalité physique, qui retire les deux paquets fusionnés et eux seuls. Avec <>, deux paquets structurellement égaux — deux feuilles de même nom, ou deux fusions identiques — seraient retirés ensemble, et l'algorithme perdrait des points en silence.

Question 2 : comment l'IA t'aide

2. Sur les cinq points de l'exercice 26.8, expliquer pourquoi le lien simple relie $a$ et $d$ alors qu'ils sont à distance $6$ .

Élève

Avec le lien simple, je pensais que $a$ et $d$ , à distance $6$ l'un de l'autre, ne pouvaient pas se retrouver dans le même paquet avant la hauteur $6$ . Pourtant le dendrogramme les réunit plus bas.

Reprends la définition : quelle distance entre deux paquets le lien simple retient-il ? Regarde la fusion qui réunit le paquet de $a$ et celui de $d$ .

Élève

C'est la plus petite distance entre un point de l'un et un point de l'autre. Donc $a$ et $d$ n'ont pas besoin d'être proches entre eux pour finir ensemble…

C'est cela. Quelle paire de points décide alors cette fusion, et à quelle hauteur ? Et que ferait le lien complet, qui retient l'autre extrême, face à ces deux mêmes paquets ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →