Probleme – Le dendrogramme : deux liens, et où couper

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.

2. Pourquoi $a$ et $d$ finissent ensemble. Le lien simple ne demande aucune proximité globale : il suffit qu'un point de $\{a,b\}$ soit proche d'un point de $\{c,d\}$. Ici $|b-c|=3$, et cette seule paire décide de la fusion, alors que $|a-d|=6$ est la plus grande distance interne du paquet obtenu. De proche en proche, la relation « être à moins de $3$ » propage l'appartenance le long de la chaîne $abcd$ : c'est l'effet de chaînage. Le lien complet, qui mesure au contraire la paire la plus éloignée, refuse cette fusion à la hauteur $3$ et ne l'accepte qu'à $9,5$.

3. La complexité. La boucle fait $n-1$ tours ; à chaque tour on examine $O(n^2)$ paires, et le calcul du lien d'une paire coûte $O(|a|\cdot |b|)$. Or la somme des $|a|\cdot |b|$ sur toutes les paires d'une même partition vaut au plus $n^2/2$ : un tour coûte donc $O(n^2)$, et le total $O(n^3)$. Pour descendre :

• on mémorise les distances entre paquets dans une matrice, et l'on ne met à jour que la ligne du paquet fusionné : la formule de Lance-Williams donne le nouveau lien en $O(1)$ par paquet, soit $O(n)$ par tour ;
• on range les paires dans un tas (chapitre chap:tas) au lieu de rechercher le minimum par un double parcours.

On obtient $O(n^2\log n)$, et $O(n^2)$ pour le lien simple, qui coïncide avec l'arbre couvrant minimal (chapitre chap:graphes-avances) : les fusions du lien simple sont exactement les arêtes que choisit Kruskal, et l'union des paquets est un unir-trouver (chapitre chap:unir).

4. Où couper. Il n'y a pas de règle, et c'est précisément l'avantage revendiqué par le cours : la coupe se décide après avoir vu l'arbre. Trois usages :

• on connaît le nombre de paquets voulu : on coupe juste au-dessus de la $(n-k)$-ième fusion ;
• on lit le dendrogramme et l'on coupe au plus grand saut de hauteur entre deux fusions consécutives — ici, entre $2$ et $4,5$ pour le lien complet, ce qui désigne trois paquets ;
• un critère métier fixe une distance maximale acceptable, et l'on coupe là.

Le contraste avec les $k$-moyennes est ici entier : on n'a pas eu à choisir $k$ avant de calculer, on n'a pas eu à relancer, et deux exécutions donnent le même arbre. Le prix est le $O(n^3)$, qui interdit ce procédé sur un million de points — et c'est pour cela que les deux méthodes coexistent.