Probleme – $k$-moyennes : le paquet vide, le minimum local, les relances

1. Le paquet vide donne nan. Le barycentre est une somme divisée par un effectif ; sur un paquet vide, c'est $0/0$, et en flottants IEEE cela vaut nan. Le cas se produit vraiment : sur les points $0,1,10,11$ avec $k=3$ et les centres initiaux $0$, $1$, $100$, l'affectation est $[0;1;1;1]$ — le troisième centre ne reçoit personne — et son barycentre vaut nan.

Ce qui suit est pire que l'arrêt : nan contamine tout. Toute distance à ce centre vaut nan, et toute comparaison avec nan est fausse : $\mathtt{nan}<1,0$ est faux, et $\mathtt{nan}=\mathtt{nan}$ est faux aussi. Le centre vide n'est donc jamais choisi comme « plus proche », il reste vide, et le programme tourne en rendant $k-1$ paquets sans le dire.

(* Barycentre du paquet c. Si le paquet est vide, on RELANCE le centre sur
   un point tiré au hasard plutôt que de rendre nan. *)
let barycentre points aff c defaut =
  let s = ref 0.0 and n = ref 0 in
  Array.iteri (fun i x -> if aff.(i) = c then (s := !s +. x; incr n)) points;
  if !n = 0 then defaut else !s /. float_of_int !n

La règle : une division dont le dénominateur peut être nul se traite avant de diviser, pas après. En C, $0/0$ sur des entiers plante ; en flottants, il ne plante pas — et c'est plus dangereux.

2. Deux départs, deux résultats. Mesuré :

La seconde partition est stable : aucun point ne veut changer de paquet, aucun centre ne veut bouger. C'est bien un minimum local, et il est $25$ fois pire que l'optimum. Le mécanisme est visible : deux centres se sont posés dans le paquet de droite, aucun dans celui du milieu, et l'unique centre restant a dû couvrir les deux paquets de gauche à la fois. Une fois cette division faite, aucun pas local ne la défait.

3. Le compte. Sur les $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$ façons de choisir trois points distincts comme centres initiaux, $65$ atteignent $J=6$ et $19$ échouent — soit près d'un départ sur quatre. La pire inertie atteinte est $154,5$, celle du tableau ci-dessus.

4. La stratégie : relancer, et garder le meilleur.

(* Meilleure partition sur r exécutions indépendantes.
   Précondition : r >= 1. Complexité : r fois celle de k_moyennes. *)
let k_moyennes_relance points k r =
  let meilleur = ref None in
  for _ = 1 to r do
    let (aff, centres, cout) = k_moyennes points (tirer points k) in
    match !meilleur with
    | Some (_, _, c) when c <= cout -> ()
    | _ -> meilleur := Some (aff, centres, cout)
  done;
  !meilleur

Avec une probabilité d'échec de $19/84\approx 0,226$ par départ et des départs indépendants, la probabilité que $r$ relances échouent toutes vaut $0,226^r$ : $5\%$ pour $r=2$, $1\%$ pour $r=3$, $10^{-4}$ pour $r=6$. Trois relances suffisent ici à ramener le risque au centième, pour trois fois le temps de calcul.

Le statut de cet algorithme. C'est un Las Vegas dégradé, au sens du chapitre chap:probabilistes : le résultat rendu est toujours valide — une partition stable —, seul son coût dépend du hasard. On ne peut pas savoir si l'on a l'optimum ; on peut seulement rendre l'échec improbable, et c'est exactement ce que fait la relance. Un raffinement classique, $k$-moyennes++, tire les centres initiaux loin les uns des autres au lieu de les tirer uniformément, et réduit fortement les $19$ cas.