Un coude, sinon rien

Commençons par un exemple que tout le monde peut se figurer. Une boutique en ligne veut ranger ses clients en groupes qui se ressemblent : les chasseurs de promotions, les fidèles du dimanche, les gros paniers. Un algorithme sait faire ce tri, à condition qu'on lui dise d'avance combien de groupes former. Deux groupes ? Le tri reste grossier. Dix ? Chaque groupe devient si petit qu'il ne veut plus rien dire. Quelque part entre les deux se cache le bon nombre.

Pour le trouver, on trace une courbe. En abscisse, le nombre de groupes essayé ; en ordonnée, une mesure du désordre qui reste à l'intérieur des groupes. Cette courbe descend vite au début, chaque groupe ajouté absorbe beaucoup de désordre, puis elle s'aplatit : les groupes supplémentaires n'apportent presque plus rien. La même silhouette de rendements décroissants apparaît quand on se demande quand arrêter d'entraîner un modèle, ou à partir de quel budget une campagne publicitaire sature. Le point où la courbe cesse de payer porte un nom d'anatomie : le coude¹. Avant lui, chaque unité investie rapporte ; après lui, on s'obstine.

Trouver ce point semble facile et c'est bien là le piège : un algorithme de détection de coude répond toujours quelque chose, même sur une droite parfaite ou sur du bruit pur. elbow-helper pose une question plus dure : ce candidat est-il fort, unique, persistant, reproductible, improbable sous un modèle sans coude ? Si une seule de ces conditions échoue, il s'abstient et dit pourquoi. La chaîne complète tourne à deraison.ai/elbow-helper, dans votre navigateur : collez une courbe, vous aurez la réponse et ses preuves avant d'avoir fini de lire cet article.

Motivation

Les heuristiques existantes, à commencer par l'algorithme Kneedle qui fait référence², excellent à proposer un emplacement. Elles ne portent en revanche aucune notion de confiance : un point, sans marge d'erreur, sans probabilité, sans droit de retrait. Sur une courbe bruitée, ce point isolé n'est que trop facile à surinterpréter : on choisit quatre groupes, on dimensionne un cache, on arrête une expérience, sur la foi d'un artefact du bruit.

Un radiologue devant un cliché flou ne diagnostique pas ; il écrit que l'examen ne permet pas de conclure et prescrit un second cliché. Une procédure statistique devant une courbe bruitée mérite la même retenue : conclure seulement ce que la donnée supporte. Le parallèle a sa limite : le radiologue engage un jugement, la procédure applique des seuils calibrés une fois pour toutes, ce qui la rend plus prévisible et moins fine à la fois.

La priorité de conception d'elbow-helper est donc explicite : minimiser les faux coudes, quitte à s'abstenir plus souvent. Le contrat de sortie l'impose au code appelant : soit un ClearKnee avec position, intervalle bootstrap à 90 % (une fourchette qui vise à contenir la vraie position dans environ neuf cas sur dix, sans qu'une étude de couverture l'ait encore établi hors du banc d'essai synthétique) et preuves chiffrées, soit un NoClearKnee avec un code de raison lisible en machine. Aucun repli silencieux vers une estimation douteuse, encore moins vers une valeur de complaisance : l'abstention se gère, elle ne se contourne pas.

Les outils qui existent déjà se partagent en trois camps. Les localisateurs de coude, kneed³, kneebow⁴, le visualiseur de Yellowbrick⁵, répondent toujours par un point, sans jamais pouvoir dire « il n'y a rien ici ». Les bibliothèques de détection de ruptures, ruptures⁶ en tête, sont excellentes mais traitent une autre question : combien de ruptures dans un signal, sans notion de rendements décroissants. Le troisième camp délègue le jugement à un humain, à l'œil ou à un modèle de langage, ce qui n'est pas reproductible. Le parent le plus proche d'elbow-helper n'est finalement pas un localisateur de coude mais le paquet segmented de R⁷, qui partage la même intuition : une affirmation de coude doit venir avec une incertitude, pas seulement avec une coordonnée. L'abstention explicite, elle, reste rare chez tous : c'est l'apport principal. Cette comparaison est chiffrée : le tableau de notes et la carte qui en résume les onze critères sont en fin d'article.

Quant à l'ampleur, elle se vérifie plutôt qu'elle ne se proclame. Le paquet est publié sur PyPI, l'entrepôt public d'où pip install va chercher les bibliothèques Python, en huit versions successives de v0.1.0 à v0.1.7. Chaque envoi de code est bloqué tant que les 85 tests automatiques ne passent pas sur Python 3.12 et que le vérificateur de style ne rend pas un verdict propre ; un balayage hebdomadaire rejoue la même suite sur les quatre versions de Python supportées, de 3.10 à 3.13. Ces 85 tests exécutent 96 % des lignes du paquet.

La même chaîne s'atteint par quatre portes : la bibliothèque Python, une ligne de commande, une interface web sur laquelle d'autres programmes viennent poser leurs questions (une API HTTP) et un serveur qui expose les mêmes opérations à un assistant conversationnel, par le protocole d'appel d'outils dit Model Context Protocol ou MCP. Les quatre sont de minces adaptateurs posés sur un cœur unique, si bien qu'aucune ne peut dériver par rapport à ce que renvoie la bibliothèque. S'y ajoutent l'application web qui fait tourner la chaîne entière dans le navigateur et une note mathématique en LaTeX qui dérive chaque formule du paquet, exemple travaillé à l'appui : ELBOW.pdf, complétée par LIKELIHOOD.pdf pour la partie vraisemblance reprise plus bas. Les documents d'accompagnement existent en français comme en anglais, tenus à jour avec le code.

Comment ça marche

Avant de chercher quoi que ce soit, la courbe est mise en ordre : points non finis écartés, abscisses triées et dédoublonnées, échelles ramenées au carré unité. Cette mise à l'échelle prend une précaution. Plutôt que de caler les bornes sur le point le plus bas et le point le plus haut, elle les cale sur les 5^e et 95^e centiles : les valeurs au-dessous desquelles tombent respectivement 5 % et 95 % des points. Un seul point aberrant ne peut donc pas écraser tout le reste de la courbe contre le bord.

Un premier examen de forme suit. La courbe est-elle monotone, c'est-à-dire monte-t-elle ou descend-elle sans jamais changer de sens ? La corrélation de Spearman⁸ répond à cette question en ne regardant que l'ordre des valeurs, jamais leur amplitude ; un contrôle de monotonie pondéré par les écarts la double. Une courbe sans tendance nette est écartée d'emblée, avant même qu'on cherche un coude.

Le sens de la courbe n'a pas à être déclaré, sauf à vouloir l'imposer. La direction se lit dans le signe de la tendance. La convexité se lit en comparant la courbe à la corde qui joint son premier et son dernier point : au-dessus de la corde, elle est concave, bombée comme un dôme ; en dessous, convexe, creusée comme un bol. Les quatre combinaisons, concave ou convexe croisées avec croissante ou décroissante, sont ainsi couvertes sans que l'appelant ait à nommer la forme. Une forme donnée explicitement l'emporte toujours sur la forme devinée.

La courbe est propre, son sens est connu ; reste à dire ce que l'on cherche, à commencer par le mot « coude », qui mérite une définition honnête. Prenez une courbe en \(\sqrt{x}\), qui monte vite puis se calme et soustrayez-lui la diagonale qui relie ses deux extrémités : il reste une bosse, nulle aux deux bouts, maximale là où la courbe s'écarte le plus d'une droite. Ce sommet est le coude. Après normalisation des données dans le carré unité, la courbe de différence s'écrit :

Ses maxima locaux, les points plus hauts que leurs voisins immédiats, sont les candidats. Un seuil de sensibilité décide ensuite si un sommet est un vrai coude ou une simple ondulation : le candidat doit dominer son voisinage d'une marge proportionnelle à un paramètre \(S\) :

où la barre désigne l'espacement moyen entre abscisses consécutives. Plus \(S\) est grand, plus la marge exigée est large. Cette recherche est rejouée sur toute une grille de lissages et de sensibilités ; seuls survivent les candidats qui reviennent au même endroit à travers les échelles : un coude réel tient la route quand on floute un peu la courbe, là où un accident de bruit disparaît.

Cette recherche de sommets porte un nom et des auteurs : c'est l'algorithme Kneedle², décrit par Satopää, Albrecht, Irwin et Raghavan en 2011, réimplémenté ici de zéro en NumPy. La logique de parcours, la table des orientations et le seuil de sensibilité suivent de près les choix de la bibliothèque kneed de Kevin Arvai³, sous licence BSD à trois clauses, créditée comme telle dans le dépôt ; elbow-helper n'en dépend pas à l'exécution. Ce que ce paquet ajoute tient donc ailleurs : dans ce qu'on exige d'un candidat avant d'accepter de le nommer.

La confirmation par modèle vient ensuite. Première exigence : la pente doit changer et changer d'une façon que trois points aberrants ne suffisent pas à fabriquer. C'est ce que mesure un estimateur de Theil-Sen⁹. La méthode des moindres carrés cherche la droite qui rend la somme des carrés des écarts la plus petite possible ; une valeur folle y pèse donc très lourd. Theil-Sen procède autrement. Il calcule la pente de toutes les paires de points, puis prend la médiane de ces pentes, la valeur du milieu une fois qu'on les a rangées. Quelques points fous ne décident plus du verdict.

Reste à écrire le modèle lui-même. Un vrai coude est un changement de pente : une ligne droite, puis une autre pente après le point \(k\). La fonction charnière \(\max(0, x - k)\), exactement nulle avant \(k\) et linéaire après, fabrique cette ligne brisée d'un seul tenant, sans saut :

Le coefficient \(c\) porte toute l'histoire du coude : \(c = 0\) redonne une droite sans coude et plus \(c\) s'éloigne de zéro, plus la pente casse fort en \(k\). Ce modèle brisé doit ensuite battre la droite simple sur deux tableaux. D'abord en validation croisée par blocs¹⁰. L'exercice consiste à cacher une partie des données, puis à regarder si le modèle devine ce qu'on lui a caché. Ici, on retire des tronçons contigus entiers de la courbe, jamais des points isolés : un point isolé se devine bien trop facilement d'après ses voisins immédiats. Ensuite sur un score qui compare les deux modèles en tenant compte de leur complexité ; ce score demande qu'on dise d'abord ce que « mieux ajusté » signifie.

Ce que « mieux ajusté » veut dire : la vraisemblance

Un modèle ajuste bien les données lorsque, sous ce modèle, les données observées ne sont pas surprenantes. C'est l'idée de vraisemblance. Pour la rendre calculable, on se donne un modèle du hasard. Chaque point observé s'écarte de la courbe théorique d'un bruit gaussien, ce hasard en courbe en cloche que produisent de petites erreurs qui s'additionnent. Chaque écart est tiré indépendamment des autres, avec un écart typique noté \(\sigma\), dont le carré \(\sigma^2\) est la variance. Chaque observation reçoit alors une densité de probabilité, le nombre qui dit à quel point cette valeur était attendue, d'autant plus grand que le point tombe près de la courbe proposée.

La définition des manuels multiplie ces densités sur les \(n\) points. Ce produit pose un problème pratique : multiplier \(n\) nombres plus petits que un donne une quantité qui s'effondre exponentiellement avec \(n\), si bien qu'une courbe de 80 points et une courbe de 800 ne se comparent plus. elbow-helper prend donc la vraisemblance par observation : la moyenne géométrique des \(n\) densités. Cette moyenne-là se calcule en multipliant les \(n\) nombres, puis en prenant la racine \(n\)-ième du résultat. Le nombre de points cesse ainsi de peser sur cette quantité :

Sous le modèle gaussien, tout se simplifie d'un coup : un produit d'exponentielles est l'exponentielle d'une somme et cette somme divisée par \(n\) est une moyenne. Il reste l'erreur quadratique moyenne \(\mathrm{EQM}(\theta)\), la moyenne des carrés des écarts entre points observés et courbe ajustée :

Prendre le logarithme n'introduit aucune base ici : cela défait celle que la densité gaussienne portait déjà.

Cette ligne contient une petite révélation. À variance fixée, minimiser l'erreur quadratique moyenne revient exactement à maximiser \(\ell\) : la méthode des moindres carrés, apprise comme une recette géométrique et le maximum de vraisemblance, appris comme un principe statistique, sont une seule et même procédure. En remplaçant \(\sigma^2\) par sa valeur la mieux soutenue par les données, \(\hat\sigma^2 = \mathrm{EQM}\), puis en exponentiant \(-2\ell\), on retombe sur une quantité que la théorie de l'information appelle perplexité. Le mot vient des modèles de langage, où la perplexité se lit comme le nombre de mots entre lesquels le modèle hésite à chaque pas. Ici, sur des nombres plutôt que sur des mots, elle mesure la même chose : l'étendue des valeurs que le modèle juge plausibles. Plus elle est basse, moins il hésite :

Ramenée à l'échantillon entier, elle donne la log-vraisemblance négative \(\mathrm{NLL}\), écrite avec la somme des carrés des résidus \(\mathrm{SCR}\), c'est-à-dire l'erreur quadratique moyenne avant division par \(n\) :

Comparer deux modèles sur leur seul ajustement serait truqué d'avance : un modèle qui a plus de réglages colle toujours mieux aux données, jusqu'à épouser le bruit lui-même. Il faut donc faire payer les réglages. Toutes les variantes du BIC (Bayesian Information Criterion)¹¹ commencent par cette \(\mathrm{NLL}\) et y ajoutent une pénalité proportionnelle au nombre de paramètres dépensés. Le coude coûte des paramètres et il doit les rembourser en ajustement, faute de quoi la droite simple l'emporte.

Reste à rendre la qualité d'ajustement lisible pour un humain. Le réflexe serait le \(R^2\), le score d'ajustement des manuels. Il compare l'erreur du modèle à celle qu'on commettrait en répondant toujours la même valeur, la moyenne \(\bar y\) des observations : 1 pour un ajustement parfait, 0 pour « pas mieux que de répondre la moyenne ». Mauvaise référence : \(\bar y\) est la constante qui minimise l'erreur, donc le meilleur prédicteur trivial qui soit. C'est pourquoi un \(R^2\) peut devenir négatif. elbow-helper se compare plutôt à un adversaire délibérément mauvais, le point observé depuis lequel il est le plus difficile de prédire tous les autres :

Ce score vaut 1 pour un ajustement parfait et 0 pour un ajustement aussi mauvais que cette pire constante. Comme cette référence est toujours plus mauvaise que la moyenne, la barre à franchir pour tomber en négatif est bien plus haute qu'avec un \(R^2\). C'est ce nombre qui s'affiche dans la légende de la figure de diagnostic. Trois autres l'accompagnent : la probabilité de détection ; la valeur \(p\), c'est-à-dire la probabilité que le hasard seul fasse aussi bien, définie à la section suivante ; et un poids de modèle dérivé du BIC. Ce dernier est la cote entre les deux modèles, que l'écart de BIC fournit par l'approximation de Kass et Raftery¹². Le mot compte : cette cote vaut sous des hypothèses asymptotiques, c'est-à-dire valables à la limite d'un grand nombre d'observations. La lire comme une probabilité a posteriori demanderait en plus des probabilités a priori sur les deux modèles, qu'aucune donnée ne fournit ici. On la prend donc pour ce qu'elle est, un poids qui compare deux modèles sans prétendre à une probabilité.

Les épreuves de robustesse

Un modèle peut gagner ce duel sur les données observées et n'être qu'un caprice du bruit. Deux épreuves s'en assurent. Le bootstrap¹³ : on rejoue la recherche entière sur des copies de la courbe obtenues en rebrassant le bruit résiduel. Le nom vient d'une expression anglaise, se hisser en tirant sur ses propres lacets : faute d'autres jeux de données, on en fabrique à partir de celui qu'on a. On retire à la courbe le modèle ajusté, ce qui laisse les écarts ; on rebat ces écarts au hasard, puis on les recolle sur le modèle. Chaque copie est une courbe qu'on aurait pu observer si le hasard avait tiré autrement. Pour passer, le coude doit revenir dans au moins 90 % des rejeux, au même endroit, avec un intervalle serré. Le test du modèle nul, enfin : on simule des milliers de droites pures portant le même niveau de bruit et l'on mesure la probabilité \(p\) qu'une droite sans aucun coude produise, par hasard, une preuve aussi forte que celle observée.

Ce nombre mérite qu'on s'y arrête, car c'est la quantité la plus souvent mal lue de toute la statistique. La valeur \(p\) ne dit pas la probabilité qu'il n'y ait pas de coude. Elle dit l'inverse : en supposant qu'il n'y en ait aucun, à quelle fréquence le hasard seul fabriquerait une preuve aussi convaincante que celle qu'on a sous les yeux. Une valeur \(p\) de 0,01 signifie qu'une droite pure y parviendrait une fois sur cent. C'est peu, donc on retient le coude ; ce n'est pas zéro, donc on peut se tromper une fois sur cent. Ce détour par la simulation n'est pas un luxe : sous l'hypothèse « pas de coude », la position \(k\) n'existe tout simplement pas ; les tests classiques perdent alors la loi de référence sur laquelle ils s'appuient d'ordinaire¹⁴. Il faut :

Seul un candidat qui franchit toutes les portes devient un ClearKnee. La figure de diagnostic résume ce dossier de preuves à côté de la courbe ; en cas d'abstention, elle bascule vers un état honnête, courbe grisée et raison affichée, jamais un marqueur qui suggérerait plus de certitude que les données n'en contiennent.

La figure suivante montre la même courbe, la même cassure en dessous, avec un bruit plus fort et rien d'autre de changé.

Ce que « s'abstenir » veut dire

Une abstention n'est pas un échec silencieux : c'est une valeur de retour, avec un nom. La fonction renvoie toujours l'un de deux types, jamais autre chose ; le code appelant est obligé de regarder lequel avant de continuer. Voici les deux réponses telles qu'elles s'affichent, sur la même courbe à deux niveaux de bruit :

>>> from elbow_helper import robust_knee

>>> robust_knee(x, y)            # bruit d'écart-type 0,02
ClearKnee(knee_x=0.3038, ci90=(0.3038, 0.3418), detection_rate=0.98, null_p=0.00498)

>>> robust_knee(x, y_bruite)     # même coude, bruit dix fois plus fort
NoClearKnee(reason='INCOMPATIBLE_GLOBAL_SHAPE')

La première ligne se lit sans documentation : coude en 0,304, intervalle bootstrap à 90 % allant de 0,304 à 0,342, coude redétecté dans 98 % des rejeux, probabilité qu'une droite sans coude fasse aussi bien : cinq pour mille. La seconde ne donne pas de position du tout ; c'est voulu : à ce niveau de bruit, la courbe ne passe même plus l'examen de forme, la tendance n'étant plus assez nette pour qu'on ose la qualifier.

Chaque refus porte un code stable, lisible par une machine autant que par un humain. Ces codes forment un vocabulaire arrêté d'avance, quinze motifs et pas un de plus, sur lequel un tableau de bord peut compter ses abstentions et savoir si ses courbes sont trop courtes, trop bruitées ou simplement ambiguës.

Les quinze façons de dire non, dans l'ordre où la chaîne peut les rencontrer.

Cette granularité a une conséquence pratique : un refus est actionnable. INSUFFICIENT_DATA demande d'allonger la grille ; BOOTSTRAP_MULTIMODAL suggère qu'il y a peut-être deux coudes plutôt qu'aucun et invite à la recherche au pluriel décrite plus bas ; NULL_NOT_REJECTED dit que la courbe est jolie mais que le bruit suffirait à l'expliquer.

Cinq portes, un seul verdict

Un détecteur ne sert que s'il s'appelle depuis l'endroit où l'on travaille. elbow-helper expose donc la même chaîne par cinq surfaces. La bibliothèque Python pour un carnet d'analyse ; la ligne de commande pour un script ou une chaîne d'intégration continue (les vérifications automatiques rejouées à chaque modification du code) ; l'API HTTP pour un service écrit dans un autre langage que Python ; le serveur MCP pour un assistant conversationnel ; l'application web pour qui ne veut rien installer du tout. Les quatre premières partagent le même cœur et exposent les quatre mêmes opérations : knee (un coude avec son incertitude), elbow (le raccourci convexe et décroissant du k-means), diagnostics (la figure de diagnostic, rendue en SVG, un format de dessin vectoriel qui reste net à toute taille) et locator (le localisateur nu, sans dossier de preuves). Ce que l'une renvoie, les autres le renvoient aussi, au format près.

Installer, c'est choisir sa porte. Le cœur ne dépend que de NumPy ; les surfaces réseau sont des options, entre crochets, que l'on n'installe que si l'on s'en sert :

$ pip install elbow-helper            # bibliothèque + ligne de commande
$ pip install "elbow-helper[api]"     # + l'API HTTP
$ pip install "elbow-helper[mcp]"     # + le serveur MCP (qui embarque l'API)

La bibliothèque

Deux fonctions suffisent. robust_knee prend une courbe et devine sa forme ; robust_elbow est le raccourci du cas k-means, où la forme est connue d'avance, convexe et décroissante. Les abscisses sont facultatives : passer les seules ordonnées revient à les numéroter de zéro à n moins un.

from elbow_helper import robust_knee, robust_elbow, RobustKneeConfig

res = robust_knee(x, y)                     # forme et sens devinés
res = robust_elbow(k_values, inerties)      # le cas k-means, forme imposée
res = robust_knee(y)                        # x implicite : 0, 1, 2, ...

# Plus de rejeux : plus lent, plus sûr.
res = robust_knee(x, y, config=RobustKneeConfig(bootstrap_replicates=500,
                                                null_replicates=1000,
                                                random_seed=0))

if res.is_clear:
    print(res.knee_x, res.ci90, res.detection_rate, res.null_p_value)
else:
    print("pas de coude net :", res.reason)

Tous les seuils vivent dans RobustKneeConfig, une structure figée : on n'en modifie pas un champ, on en fabrique une copie par config.with_(...). Les réglages livrés visent la seconde plutôt que la décimale, cent rejeux de bootstrap et deux cents tirages sous le modèle nul ; les valeurs ci-dessus sont celles d'une validation sérieuse, cinq à dix fois plus lentes.

La ligne de commande

Elle suit les quatre mêmes opérations et répond en JSON, un format de texte structuré que les programmes relisent sans ambiguïté, ce qui l'enchaîne directement aux outils habituels. Les données entrent au choix en valeurs séparées par des virgules, en fichier NumPy ou en colonne d'un CSV désignée par son indice :

$ elbow-helper knee --y-values 0,0.1,0.3,0.6,0.85,0.9,0.92,0.93,0.94,0.95
{
  "reason": "INSUFFICIENT_DATA",
  "diagnostics": {
    "curve": "auto",
    "direction": "auto",
    "n": 10,
    "min_samples": 20
  },
  "is_clear": false
}

$ elbow-helper elbow --x-npy k.npy --y-npy inertie.npy
$ elbow-helper knee --y-csv mesures.csv:2 --config-json '{"bootstrap_replicates": 500}'
$ elbow-helper diagnostics --x-npy k.npy --y-npy inertie.npy > diagnostic.svg

La première commande mérite qu'on s'y arrête. La courbe qu'elle reçoit a la silhouette qu'il faut ; n'importe quel détecteur classique aurait rendu un chiffre. Dix points ne suffisent pas à étayer une affirmation de coude : la réponse est un refus documenté, qui dit combien de points ont été fournis et combien il en faudrait, plutôt qu'une estimation de complaisance. Le contrat de sortie traverse les portes intact.

L'API HTTP

Un serveur se lance en une ligne et écoute quatre routes du même nom que les opérations. La courbe voyage en JSON, les réglages aussi, dans un objet config_overrides ; la route diagnostics renvoie le SVG lui-même, pas un emballage JSON autour.

# uvicorn : le serveur qui fait tourner l'application Python.
$ uvicorn elbow_helper.api:app --port 8000

$ curl -s -X POST localhost:8000/knee -H 'Content-Type: application/json' \
       -d '{"x": [0, 0.0127, ...], "y": [0.0043, 0.0361, ...],
            "config_overrides": {"random_seed": 0}}'
{"reason": "CLEAR_KNEE", "knee_x": 0.3038, "ci90": [0.3038, 0.3418],
 "detection_rate": 0.98, "null_p_value": 0.00498, "is_clear": true,
 "diagnostics": {...}}                       # réponse abrégée

Le serveur MCP

Le serveur MCP est cette même application HTTP, avec les quatre opérations déclarées comme outils qu'un assistant conversationnel peut découvrir et appeler, servies sur /mcp :

$ uvicorn elbow_helper.mcp_server:app --port 8021
# L'assistant se connecte à http://127.0.0.1:8021/mcp et y découvre
# quatre outils : knee, elbow, diagnostics, locator.

L'intérêt dépasse le confort. Un assistant à qui l'on montre une courbe produira volontiers un coude plausible, sans rien pour le contredire. Branché sur cet outil, il obtient un verdict calculé, avec intervalle et valeur \(p\) ou un refus nommé qu'il ne peut pas paraphraser en certitude.

L'application web

La dernière surface ne demande rien : deraison.ai/elbow-helper fait tourner la chaîne entière dans le navigateur, sur vos données, sans les téléverser nulle part. On y colle une courbe, on récupère le même verdict et la même figure de diagnostic que par les quatre autres portes, en français ou en anglais.

Plusieurs coudes : la programmation dynamique

Une courbe change parfois plusieurs fois de régime, trois paliers de prix sur une courbe de demande par exemple. La question devient alors : combien de cassures et où ? C'est ce que répond robust_knees, au pluriel ; le changement de question impose un changement de modèle. On découpe la courbe en morceaux et l'on ajuste à chacun sa propre droite, de façon indépendante, en tolérant un saut à la jointure. C'est un renoncement assumé à la charnière continue de tout à l'heure : dès que plusieurs cassures peuvent bouger, un ajustement continu ne se décompose plus en coûts indépendants morceau par morceau, puisque déplacer une cassure change la condition que ses voisines doivent respecter. Or c'est exactement cette décomposition en sous-problèmes indépendants qui rend la recherche efficace.

Premier ingrédient : le coût d'un morceau, calculable d'un coup. Ajuster une droite sur \(m\) points et mesurer son erreur semble exiger de repasser sur chaque point. Il n'en est rien : six totaux cumulés suffisent,

d'où la pente et l'ordonnée à l'origine des moindres carrés, puis l'erreur du morceau :

La dernière égalité vient des équations normales des moindres carrés ; elle dit que le coût de n'importe quelle tranche de la courbe se lit dans les totaux, sans jamais retoucher aux points. Calculer ces totaux une fois coûte \(O(n)\), un temps proportionnel au nombre de points ; chaque coût de morceau coûte ensuite \(O(1)\), un temps constant, aussi long que la courbe soit.

Deuxième ingrédient : la recherche elle-même. Essayer toutes les façons de placer \(k\) cassures parmi \(n\) points est hors de portée : le nombre de façons de choisir \(k\) emplacements parmi \(n\) se chiffre vite en milliards dès que la courbe s'allonge. La programmation dynamique contourne l'obstacle en construisant la réponse à partir de sous-réponses déjà connues. Notons \(C[k][t]\) le coût total minimal pour expliquer les \(t\) premiers points avec \(k+1\) segments :

La formule se lit ainsi : pour chaque position possible \(s\) de la dernière coupe, on additionne deux termes : le meilleur coût d'explication des \(s\) premiers points avec une cassure de moins, déjà calculé et simplement relu, puis le coût du dernier segment de \(s\) à \(t\) ; on garde le minimum.

Pourquoi a-t-on le droit de relire une sous-réponse au lieu de tout recalculer ? Par l'absurde. Supposons que le meilleur découpage des \(t\) premiers points ait sa dernière coupe en \(s^\ast\), mais que son début, les \(s^\ast\) premiers points, ne soit pas le meilleur découpage possible de ce début. Alors, en y substituant le découpage moins cher et en gardant le dernier segment intact, on obtiendrait un découpage valide strictement moins coûteux que le meilleur. Contradiction. Le début d'une solution optimale est donc optimal pour son propre sous-problème, ce qu'on appelle le principe d'optimalité de Bellman¹⁵.

Remplir toutes les cases coûte \(O(k_{\max} \cdot n^2)\) opérations, un nombre raisonnable là où l'énumération brute en demandait un nombre astronomique ; des flèches mémorisées dans chaque case servent à remonter le tableau pour retrouver les positions des coupes. C'est la récursion classique de la détection de ruptures. L'algorithme PELT¹⁶ repose sur elle et l'accélère, en élaguant en cours de route les découpages devenus sans espoir. Elle est vérifiée ici contre une énumération exhaustive sur de petits jeux de données, plutôt que tenue pour acquise.

Troisième ingrédient : choisir le nombre de cassures. Plus on en ajoute, mieux on ajuste, jusqu'à l'absurde d'un segment par point. Un BIC modifié¹⁷ tranche, en ajoutant à la log-vraisemblance négative une pénalité qui charge chaque cassure et surveille en plus la longueur \(\ell_j\) de chaque segment :

Ce signe moins devant la somme mérite une anecdote, parce qu'elle dit comment ce projet travaille. La littérature écrit ce terme en addition. Testé tel quel, il produit l'effet inverse de celui qu'on lui prête : le terme étant toujours négatif, l'additionner récompense les découpages déséquilibrés au lieu de les pénaliser. La forme soustractive, elle, pénalise bien les segments courts et inégaux, conformément à l'intention déclarée. La convention retenue ici est donc celle que les tests confirment ; l'écart est documenté plutôt que dissimulé. Reste à dire ce qui n'est pas tranché : un signe qui paraît inversé vient parfois d'une définition différente de la vraisemblance, d'un score minimisé au lieu d'être maximisé, ou d'une longueur normalisée autrement. Établir la correspondance terme à terme avec la paramétrisation d'origine demanderait une annexe que le dépôt n'a pas encore écrite. On parle donc ici d'un désaccord mesuré, pas d'une correction de la littérature.

Le vainqueur est enfin confirmé par un test de permutation : des milliers de rebrassages de la courbe, dont aucun ne porte de vraie cassure, doivent presque tous faire moins bien que l'ajustement réel. Comme multiplier les tests multiplie les occasions d'avoir de la chance, une correction de Bonferroni resserre la barre de chaque test en proportion de leur nombre¹⁸.

Une nuance sépare le singulier du pluriel ; elle compte. Au pluriel, une réponse vide n'est pas une abstention mais une conclusion : cette courbe n'a aucune cassure réelle, verdict qui a franchi exactement les mêmes portes qu'une réponse non vide aurait dû franchir. Seul un échec de préparation, entrée invalide, données trop courtes, plage nulle, renvoie un objet d'erreur au lieu d'une liste de cassures.

Ces choix, la programmation dynamique plutôt que le glouton, le signe soustractif, la confirmation par permutation, ont été tranchés par la mesure. Dix combinaisons ont été mises en concurrence. D'un côté, deux façons de chercher : la programmation dynamique, qui examine tous les découpages et l'approche gloutonne, qui pose ses cassures une par une sans jamais revenir dessus. De l'autre, cinq façons de choisir le nombre de cassures, du BIC nu à la porte par permutation. Deux fois cinq. Chaque méthode a traité trois cents courbes synthétiques : cent points chacune, vingt-cinq répliques pour chaque combinaison de quatre nombres de cassures vrais, de zéro à trois et de trois niveaux de bruit. Les étiquettes des deux figures qui suivent se lisent ainsi : DP pour la programmation dynamique et Greedy pour le glouton ; BIC pour le critère nu, mBIC_add et mBIC_sub pour les deux signes du terme de longueur de segment, ICL pour un critère bayésien voisin qui pénalise en plus l'incertitude du découpage¹⁹, FWER pour la porte par permutation corrigée à la Bonferroni.

Deux enseignements se lisent directement sur ce classement. La recherche exhaustive bat sa jumelle gloutonne à chaque fois et de loin : 0,85 contre 0,60 pour le même critère. Le mécanisme est celui que décrit la littérature sur la segmentation binaire²⁰ : le glouton s'engage tôt sur une coupe imparfaite. Les coupes suivantes servent ensuite à réparer cette erreur plutôt qu'à décrire la courbe. Le signe du terme de longueur de segment, l'anecdote racontée plus haut, se chiffre lui aussi : 0,85 pour la forme soustractive contre 0,77 pour la forme additive de la littérature.

Reste le péché qui intéresse le plus ce projet : inventer une cassure là où il n'y en a aucune. La seconde figure mesure exactement cela, sur des courbes tirées plates exprès.

La limite, elle, est commune à toutes les méthodes et mérite d'être dite : à fort bruit avec trois cassures vraies, aucune ne les retrouve toutes, la meilleure tournant autour de 1,8 cassure annoncée en moyenne. L'erreur va donc vers moins de coudes, jamais vers plus, ce qui est exactement la direction dans laquelle ce paquet accepte de se tromper. Ces chiffres valent pour cette famille de courbes synthétiques et pour elle seule ; le protocole complet est publié dans le dépôt, avec le tableau détaillé par niveau de bruit²².

Le tout tient avec une seule dépendance de calcul, NumPy : l'algorithme de localisation est réécrit de zéro ; la figure de diagnostic est du SVG écrit à la main, sans bibliothèque graphique. Chaque formule de cette chaîne, de la normalisation au test de permutation, est dérivée pas à pas dans la note mathématique du dépôt, ELBOW.pdf²³, écrite intuition d'abord, avec un exemple travaillé avant chaque formule. Le socle de vraisemblance repris plus haut est traité à part, dans LIKELIHOOD.pdf²⁴, parce qu'il ne doit rien à l'ajustement de courbes.

Ce que ça ne fait pas

Un projet qui se réclame de la prudence doit énoncer ses propres limites, sous peine de commettre l'excès de confiance qu'il reproche aux autres.

Le lissage suppose des abscisses régulièrement espacées ou presque : une courbe échantillonnée n'importe comment le mettrait en défaut. La position rendue est discrétisée sur les points fournis. À effectif modeste, le coude peut donc tomber à quelques échantillons de la vérité. Sur la famille de courbes synthétiques qui sert de banc d'essai, l'erreur médiane reste au-dessous de 5 % environ de la plage des abscisses. Le modèle nul en droite et le bootstrap sur résidus font une autre hypothèse : un bruit à peu près homoscédastique, c'est-à-dire de variance constante d'un bout à l'autre de la courbe et sans corrélation d'un point au suivant. Les variantes qui s'affranchissent de cette hypothèse restent à écrire.

Enfin, les seuils sont des valeurs calibrées sur une famille de courbes documentée, pas des constantes universelles : 90 % de redétections et une valeur \(p\) à 1 % sont des choix défendables, pas des lois de la nature. Le paquet est en v0.1.x ; son auteur le dit : à recalibrer sur votre propre famille de courbes et de bruits si votre décision en dépend. Aucune méthode travaillant sur des données finies n'est infaillible ; celle-ci se contente de rendre ses hypothèses vérifiables.

Conclusion

Un détecteur qui s'abstient rend un meilleur service qu'un détecteur qui répond toujours. « Pas de coude net » est une vraie information : elle évite de dimensionner un système, d'arrêter une expérience ou de trancher un budget sur un pli du hasard. La confiance affichée se paie, nonobstant, en abstentions ; c'est un échange que je revendique.

elbow-helper s'installe en une ligne, pip install elbow-helper et s'essaie sans rien installer dans le bac à sable en ligne, où la chaîne complète tourne dans votre navigateur sans téléverser vos données. Le code, les exemples, le comparatif des outils voisins et les notes mathématiques sont réunis sur le dépôt GitHub. Apportez une courbe ; vous repartirez avec un coude défendable ou avec une bonne raison de ne pas y croire.

Le paysage, outil par outil

Reste à situer tout cela. Le dépôt note huit façons de chercher un coude sur onze critères ; la note porte sur le travail que fait ce paquet, rapporter un coude seulement quand la preuve l'appuie : aucun outil n'est pénalisé pour exceller à un autre métier.

Les onze critères du dépôt, de une à cinq étoiles. La ligne surlignée est celle du paquet dont parle cet article.

• elbow-helper : le seul du lot qui puisse refuser de répondre : persistance à travers les lissages, bootstrap, test du modèle nul, puis un coude avec son intervalle ou un motif d'abstention nommé.
• kneed : l'implémentation de référence de Kneedle, déterministe et immédiate. Un point, toujours, sans marge d'erreur ni porte de sortie.
• kneebow : la même idée géométrique, obtenue en faisant tourner la courbe. Très léger en dépendances, mais il s'engage à chaque appel.
• KElbowVisualizer : la façon la plus répandue de lire un coude de k-means : on trace, on regarde. Un outil de visualisation, taillé pour une seule forme de courbe, qui hérite de scikit-learn et de matplotlib.
• ruptures : l'outil juste quand la question est « combien de ruptures et où », avec PELT et la segmentation binaire déjà en place. La notion de rendements décroissants lui est étrangère.
• Paquet R segmented : le plus rigoureux statistiquement : régression en ligne brisée, erreurs types, test de Davies, cassures multiples. Il demande R et une réelle aisance statistique.
• Estimation visuelle manuelle : un œil averti sait dire « je ne vois rien de net ici », ce que la plupart des outils ne savent pas. Mais le jugement ne se reproduit ni d'une personne à l'autre, ni à l'échelle.
• Demander à un LLM : décrit une forme en mots avec aisance, sait nuancer si on le lui demande ; sans incertitude calibrée, sans dérivation vérifiable, jamais deux fois la même réponse.

Bibliographie

Voici les travaux dont ce paquet dépend, rangés dans l'ordre où l'article s'en sert. Chaque notice dit ce que la source établit et à quel endroit elle sert ici ; les classiques y sont cités pour le résultat standard qu'ils fondent, les notes du dépôt pour les dérivations et les mesures qu'elles portent.

1. Thorndike, R. L. (1953). « Who belongs in the family? », Psychometrika, 18(4), 267-276. 10.1007/BF02289263 Adresse présidentielle à la Psychometric Society, couramment donnée comme la première formulation du critère du coude : on trace une mesure de dispersion contre le nombre de groupes et l'on cherche le pli. Elle pose la question dont vit cet article, sans proposer de règle de décision.
2. Satopää, V., Albrecht, J., Irwin, D. et Raghavan, B. (2011). « Finding a Kneedle in a Haystack: Detecting Knee Points in System Behavior », ICDCSW, IEEE. Définit le coude comme le maximum de l'écart à la corde après normalisation, avec un seuil de sensibilité : c'est l'algorithme de localisation réécrit ici. Sa limite est dans son énoncé même : il propose un emplacement, il ne dit pas si ce coude existe.
3. Arvai, K. kneed, bibliothèque Python, licence BSD à trois clauses. github.com/arvkevi/kneed L'implémentation de référence de Kneedle en Python. Sa logique de parcours, sa table d'orientations et son seuil de sensibilité ont guidé la réécriture NumPy d'elbow-helper, qui n'en dépend pas à l'exécution.
4. kneebow, bibliothèque Python, licence MIT. github.com/georg-un/kneebow Fait tourner la courbe puis prend l'extremum de la courbe tournée. Représentatif du camp qui répond toujours par un point, sans jamais pouvoir se taire.
5. Bengfort, B. et Bilbro, R. (2019). « Yellowbrick: Visualizing the Scikit-Learn Model Selection Process », Journal of Open Source Software, 4(35), 1075. 10.21105/joss.01075 Bibliothèque de diagnostics visuels pour scikit-learn, dont le KElbowVisualizer qui trace l'inertie et marque un coude. L'outil vise la lecture à l'œil, pas la décision chiffrée.
6. Truong, C., Oudre, L. et Vayatis, N. (2020). « Selective review of offline change point detection methods », Signal Processing, 167, 107299. arxiv.org/abs/1801.00718 Revue qui range la détection de ruptures en trois briques, une fonction de coût, une méthode de recherche, une contrainte sur le nombre de ruptures ; elle accompagne la bibliothèque ruptures. C'est le cadre dont la partie multi-coudes de cet article hérite, sur une question voisine mais distincte de celle des rendements décroissants.
7. Muggeo, V. M. R. (2003). « Estimating regression models with unknown break-points », Statistics in Medicine, 22(19), 3055-3071. 10.1002/sim.1545 Estime la position d'une cassure par linéarisations successives et en donne une erreur type, donc un intervalle. C'est le parent le plus proche d'elbow-helper sur l'idée qu'une affirmation de coude doit venir avec son incertitude ; le paquet R segmented en est la mise en œuvre.
8. Spearman, C. (1904). « The Proof and Measurement of Association between Two Things », American Journal of Psychology, 15(1), 72-101. Corrélation calculée sur les rangs plutôt que sur les valeurs. Elle sert ici d'examen de forme, insensible à l'échelle et peu troublée par quelques points extrêmes.
9. Theil, H. (1950). « A Rank-Invariant Method of Linear and Polynomial Regression Analysis », Proceedings of the Royal Netherlands Academy of Sciences, 53 ; Sen, P. K. (1968). « Estimates of the Regression Coefficient Based on Kendall's Tau », Journal of the American Statistical Association, 63(324), 1379-1389. Les deux articles fondent l'estimateur de pente par médiane des pentes de toutes les paires de points. C'est lui qui permet d'exiger un changement de pente sans qu'une poignée de valeurs aberrantes décide du verdict.
10. Arlot, S. et Celisse, A. (2010). « A survey of cross-validation procedures for model selection », Statistics Surveys, 4, 40-79. 10.1214/09-SS054 Revue qui sépare soigneusement ce qui est démontré de ce qui n'est qu'observé en validation croisée et montre que la forme des blocs retirés doit épouser la dépendance des données. C'est la justification du retrait par tronçons contigus employé ici.
11. Schwarz, G. (1978). « Estimating the Dimension of a Model », The Annals of Statistics, 6(2), 461-464. Fonde le BIC : une pénalité égale au nombre de paramètres multiplié par le logarithme du nombre d'observations, obtenue comme approximation de la vraisemblance marginale. C'est le score que la ligne brisée doit battre pour mériter son coude.
12. Kass, R. E. et Raftery, A. E. (1995). « Bayes Factors », Journal of the American Statistical Association, 90(430), 773-795. Donne l'approximation par laquelle un écart de BIC se lit comme une cote entre deux modèles et l'échelle de lecture qui va avec. C'est la probabilité a posteriori affichée dans la légende de la figure de diagnostic.
13. Efron, B. (1979). « Bootstrap Methods: Another Look at the Jackknife », The Annals of Statistics, 7(1), 1-26. Introduit le rééchantillonnage comme substitut à une loi d'échantillonnage qu'on ne sait pas écrire. Ici, c'est le bruit résiduel qu'on rebrasse, pour mesurer à quelle fréquence et à quel endroit le coude revient.
14. Davies, R. B. (1977). « Hypothesis testing when a nuisance parameter is present only under the alternative », Biometrika, 64(2), 247-254. 10.1093/biomet/64.2.247 Traite exactement la difficulté du coude : un paramètre qui n'existe que si l'hypothèse alternative est vraie, ici la position \(k\). Le test du rapport de vraisemblance y perd sa loi asymptotique usuelle, ce qui explique le recours à une valeur \(p\) simulée plutôt que lue dans une table.
15. Bellman, R. (1957). Dynamic Programming, Princeton University Press. Source canonique du principe d'optimalité : le début d'une solution optimale est optimal pour son propre sous-problème. C'est ce qui autorise la récursion utilisée ici pour placer plusieurs cassures.
16. Killick, R., Fearnhead, P. et Eckley, I. A. (2012). « Optimal Detection of Changepoints With a Linear Computational Cost », Journal of the American Statistical Association, 107(500), 1590-1598. PELT : la même récursion exacte, accélérée par un élagage qui écarte définitivement les découpages devenus sans espoir, d'où un coût linéaire sous certaines conditions sur la pénalité.
17. Zhang, N. R. et Siegmund, D. O. (2007). « A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data », Biometrics, 63(1), 22-32. Introduit le BIC modifié dont le terme supplémentaire surveille la longueur des segments. C'est la référence dont le signe, repris tel quel d'abord, a dû être corrigé ici après mesure de son effet réel.
18. Dunn, O. J. (1961). « Multiple Comparisons Among Means », Journal of the American Statistical Association, 56(293), 52-64. 10.1080/01621459.1961.10482090 Établit et met en pratique l'inégalité qui porte en statistique le nom de Bonferroni : diviser le seuil par le nombre de tests borne le risque de se tromper au moins une fois. Employée ici dès que plusieurs nombres de cassures sont mis à l'épreuve.
19. Biernacki, C., Celeux, G. et Govaert, G. (2000). « Assessing a Mixture Model for Clustering with the Integrated Completed Likelihood », IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(7), 719-725. Le critère ICL, qui ajoute au BIC une pénalité sur l'incertitude du classement. Concurrent testé dans le comparatif, où il atteint 0,82 d'exactitude et 4 % de faux positifs.
20. Fryzlewicz, P. (2014). « Wild Binary Segmentation for Multiple Change-Point Detection », The Annals of Statistics, 42(6), 2243-2281. Analyse le défaut des recherches gloutonnes, qui s'engagent trop tôt sur une coupe et propagent l'erreur et propose d'y remédier par des intervalles tirés au hasard. Le comparatif de cet article retrouve ce défaut : chaque méthode gloutonne reste sous sa jumelle exhaustive.
21. Yao, Y.-C. (1988). « Estimating the number of change-points via Schwarz' criterion », Statistics and Probability Letters, 6(3), 181-189. Étudie le BIC appliqué au nombre de ruptures et documente sa tendance à en retenir trop. Les 27 % de faux positifs mesurés ici en sont une illustration sur des courbes linéaires par morceaux.
22. Harchaoui, W. (2026). Multi-knee method comparison: results, note de recherche du dépôt elbow-helper. research/multiknee/RESULTS.md Le protocole complet du comparatif cité plus haut : dix méthodes, trois cents courbes chacune, résultats détaillés par nombre de cassures et par niveau de bruit, temps de calcul et les six conclusions qui en sont tirées.
23. Harchaoui, W. (2026). ELBOW: Noise-Robust Knee and Elbow Detection, note technique du dépôt elbow-helper, en anglais. doc/ELBOW-en.pdf Dérive pas à pas chaque formule du paquet, de la normalisation au test de permutation, intuition et exemple travaillé avant chaque formule. C'est la version longue de tout ce que cet article résume.
24. Harchaoui, W. (2026). LIKELIHOOD, note technique du dépôt elbow-helper, en anglais. doc/LIKELIHOOD-en.pdf Le socle de vraisemblance repris plus haut : pourquoi la vraisemblance par observation, moyenne géométrique des densités, plutôt que le produit brut et comment la même construction se lit sur un modèle de classification.

Pour finir, trois lectures plus agréables qu'un article de revue. Mes livres préférés en IA donnent le panorama commenté dont sont tirés les deux suivants. The Elements of Statistical Learning de Hastie, Tibshirani et Friedman couvre la sélection de modèles et la validation croisée en général. Information Theory, Inference and Learning Algorithms de MacKay éclaire le lien, esquissé ici, entre vraisemblance, codage et perplexité.