dans les deux sens entre points voisins compte double (la matrice d'incidence des K plus proches voisins n'est pas symétrique). Pour le choix de la mesure des liens, nous avons opté pour le cosinus dans l'espace distributionnel [cf. (Lelu 2003)], lié à la distance de Hellinger [cf. (Domengès, Volle 1979), 
(Bacelar-Nicolau 2002)] ; les vecteurs-documents xt sont normalisés comme suit : 

$$\mathbf{x}_{t}:\left\{x_{i t}\right\}\to\mathbf{y}_{t}:\left\{{\sqrt{\frac{x_{i t}}{x_{.t}}}}\right\}$$

où .t x est la somme des composantes it x du vecteur xt De bonnes propriétés en découlent, en particulier : . équivalence distributionnelle (invariance de la représentation au regard de la fusion de descripteurs de mêmes profils relatifs), . incrémentalité : la normalisation des vecteurs-documents évite que l'arrivée d'un nouveau document perturbe les similarités déjà calculées ; mais aussi le caractère très « creux » de ces vecteurs permet l'incrémentalité pour les descripteurs : le nombre de dimensions de l'espace des descripteurs peut croître au fur et à mesure que de nouveaux descripteurs (par ex. des termes) sont rencontrés dans les documents. . extension aisée aux données négatives. 

. les cosinus sont liés à la distance D de Hellinger : ( ) () ( ) ' , ' 2 1 cos ,t t D t t y y

$$D\bigl(t,t^{\dagger}\bigr)^{2}=2\bigl(1-\cos\bigl({\bf y}_{t},{\bf y}_{t^{\dagger}}\bigr)\bigr)$$

## 3.2. Algorithme Opérant Sur Un Graphe Orienté Valué

Le partitionnement du graphe valué et orienté des K plus proches voisins peut être vu 1) comme le repérage de nœuds-germes principaux, ou « chefs de classe », nœuds localement plus denses que leur entourage, puis 2) comme l'extension de leur zone d'influence par rattachement unique ou partagé de leurs voisins de plus en plus éloignés. Nous avons publié et expérimenté sur des données documentaires [cf. (Lelu, François 2003)] un algorithme de percolation modifié, aboutissant à extraire 1) les points isolés, 2) les noyaux stricts exclusifs d'une classe, 3) les points ambivalents appartenant à plusieurs classes, tous ces points se projetant à des hauteurs diverses sur chaque axe de classe. Mais cet algorithme n'a pas la propriété d'incrémentalité. Dans notre présente optique incrémentale, nous nous donnons l'état d'un graphe à l'instant t, dont les nœuds ont pu être caractérisés par leur densité, ainsi que par leur « couleur », c'est-àdire par leur rattachement à un éventuel nœud « chef de classe », dont le numéro constitue l'étiquette. L'arrivée d'un nouveau nœud va perturber localement cet état : un certain nombre de nœuds dans le voisinage direct ou indirect du nouvel arrivant vont voir leur densité changer - ce changement du paysage de densité induisant à son tour un réajustement des zones d'influence des chefs de classe, voire des changements de chefs de classe, ou l'apparition de nouvelles classes. De façon imagée, des changements tectoniques locaux dans un massif montagneux peuvent redessiner des lignes de partage des eaux, voire créer ou fusionner des bassins versants. De nombreuses règles d'héritage du numéro du (ou des) chef(s) de classe sont possibles. Mais dans tous les cas nous avons affaire à la mise à jour des « couleurs » d'un paysage de densité sous l'effet 1) de l'arrivée d'un nouveau point (changement structurel), 2) d'un changement localisé des densités (changement quantitatif). 