Abstract FR:

Le partitionnement maximalement predictif sous contrainte d'ordre total est une methode de classification qui cherche a partager des sequences d'objets qualitatifs en segments homogenes. L'homogeneite est definie selon un critere base sur la notion de prediction. Pour un probleme donne, on se munit d'un ensemble fini de predicteurs possibles. A chaque predicteur, on associe une fonction - la prediction - a valeurs reelles sur les objets de la sequence. Un segment est evalue par la somme des predictions de tous ses elements par un meme predicteur ad-hoc. L'evaluation est ainsi un critere d'homogeneite. Une partition de la sequence est evaluee par la somme des predictions sur ses segments. Sur la base de cette evaluation on veut pouvoir, grace au predicteur de chaque segment d'une partition, disposer d'un resume de la sequence qui mette en relief une eventuelle structure de cette sequence. Il faut alors estimer le nombre de segments en lequel il est le plus judicieux d'operer cette partition. Nous presentons un algorithme qui, sur la donnee d'une sequence, d'un ensemble de predicteurs et d'un entier k, construit l'ensemble des partitions optimales en i segments de la sequence pour tout i entre 1 et k. C'est ce que nous appelons un partitionnement. Ceci permet aussi d'observer l'evolution des partitions en fonction de leurs nombres de classes. De ces observations, on propose des criteres d'estimation du bon nombre de segments pour partager cette sequence. L'algorithme presente a une complexite en temps lineaire avec la longueur de la sequence, la taille de l'ensemble des predicteurs et le nombre maximum de segments. On peut alors operer le partitionnement sur de tres grandes sequences, et les sequences biologiques en constituent un domaine naturel d'experimentation. Nous presentons ainsi quelques applications du partitionnement maximalement predictif sur des sequences genetiques.