APPLICATION A LA TYPOLOGIE

APPLICATION A LA TYPOLOGIE

D’où dans ce qui suit nous considérons que les objets sont décrits comme des points dans un espace métrique. La relation entre deux objets utilise donc la notion de distance topologique de deux points. Une relation possible entre deux objets consiste alors à se fixer un seuil et à poser comme semblables deux objets dont la distance est inférieure au seuil. Une autre relation consiste à classer par ordre croissant toutes les distances entre les objets pris deux à deux. Par ailleurs, on peut opposer les méthodes qui calculent en utilisant des principes d’optimalité et que nous nommerons récurrentes à celles qui conduisent directement au résultat par un calcul séquentiel. Le croisement de ces deux critères de classification conduit au tableau suivant :

La recherche des cliques à partir des arêtes

Nous avons précisé plus haut que l’ensemble U des arêtes pouvait être doté d’une relation de pré ordre total fondée sur les distances calculées dans l’espace de départ. On peut transformer ce pré ordre en ordonnant arbitrairement les arêtes de même longueur. Si X est l’ensemble des sommets et Un l’ensemble formé des n premières arêtes, on peut donc créer une famille de graphes ordonnés : Gn (X, Un). Nous allons montrer que si l’on connaît l’ensemble Cn des cliques maximales du graphe Gn, on peut en déduire l’ensemble Cn+1 des cliques maximales du graphe Gn+1. Une autre procédure, s’appuyant exactement sur le même principe consiste à passer de l’étape n + 1 à l’étape n, c’est-à-dire à retirer les arêtes au lieu de les ajouter. chaque nouvelle clique, d’une part si elle est maximale, c’est-à-dire si elle n’est incluse dans une clique déjà obtenue ; d’autre part, si une clique déjà obtenue n’est pas incluse en elle. Nous allons voir comment ceci se trouve réalisé dans l’algorithme que nous allons décrire.

L’algorithme

Le schéma génaéral de cet algorithme est formé de deux boucles emboîtées :  bj + {A, B} est maximale à ce stade du calcul et que nous allons décrire maintenant. Appelons K l’étape où nous comparons ai et bj. Soit CMK-1 l’ensemble des cliques retenues provisoirement maximales à l’étape précédente, nous par ailleurs certains éléments de CMn+1 par exemple ceux de CMn ( AB ). A partir de {A, B} et de ai et bj on procède comme suit 1) Si ai bj + {A, B} ⊂ CL, on pose : – CMK = CMK-1 et on passe à l’étape K+1 sinon on pose : – CMK = CMK-1 + [ai Parmi les méthodes décrites précédemment, celles qui opèrent par récurrence sur les sommets opèrent avec un seuil fixe. La récurrence ou l’énumération sur les arêtes permet d’obtenir directement cette courbe par variation du Seuil.

C’est le cas pour cette méthode. Il est possible, chaque fois que l’on a augmenté de 10, 20, ou plus, le nombre d’arêtes de Un de calculer la couverture minimale de Gn à l’aide de CMn et de construire cette courbe. La figure 3 est un exemple d’un tel calcul. De A vers B, l’ajout d’arêtes fait croître le nombre de cliques très rapidement sans modifier le nombre de cliques de la couverture minimale. Il s’agit évidemment de la création de « ponts » entre des cliques existant à l’étape A, selon le schéma suivant figure 4. L’utilité d’une telle courbe est essentielle dans la pratique car elle permet de savoir si la solution trouvée correspond à un état stable du système et ceci d’autant plus que la relation de distance utilisée qui agglomère plusieurs dimensions n’a pas en général de signification intrinsèque.

Remarque. Les typologies utilisant les cliques procèdent en deux étapes : – Enumération des cliques maximales du graphe : pour un graphe donné l’énumération des cliques maximales est unique mais en général les cliques retenues ne forment pas une partition du graphe. – Détermination de la couverture minimale : plusieurs ensembles de cliques peuvent être retenus comme couverture du graphe.

Méthode par accumulation

On part d’une liste de sommets classés d’une manière aléatoire et de la donnée d’un seuil. On regarde si le second sommet est à une distance du premier inférieure au seuil fixé, si oui, on le met dans la classe du premier sommet sinon il constitue un second centre de classe. On continue ainsi pour l’ensemble des sommets ; on compare chacun d’eux, successivement, à chaque centre de classe et on l’ajoute à une classe déjà existante ou à la liste des centres de classes. Il est évident que cette technique où l’on classe les points d’une manière aléatoire peut conduire à autant de résultats qu’il y a de classements différents de points. Et ce n’est que dans le cas le plus favorable que les individus choisis aléatoirement pour former des centres de classe sont près des centres qui existent réellement dans la population.