L. Gueguen
Le Jeudi 15 Juin 2000 à 14h30
Salle de Conférences du LIX, École Polytechnique
L. Gueguen
(LRI)
Segmentation de séquences par partitionnement maximalement
prédictif
Résumé/Abstract :
La segmentation par partitionnement maximalement prédictif a pour but
de partager des séquences d'objets qualitatifs en segments homogènes,
selon une approche liée à la classification.
Notre but est, sur la donnée d'une séquence et d'un ensemble fini de
propriétés de composition de sous-séquences, de partager au mieux
cette séquence de telle sorte que chaque segment ainsi formé réponde
au mieux à une propriété ad hoc. Pour cela, on
se munit pour chaque propriété d'un prédicteur; et à
chaque prédicteur on associe une fonction -- la prédiction -- à
valeurs réelles sur les objets de la séquence. Un segment est
évalué par la somme des prédictions de tous ses éléments par un
même prédicteur ad hoc. Par exemple, on peut
vouloir qu'un segment soit prédit uniformément par une lettre simple
de telle sorte qu'il sera évalué par le nombre d'occurrences de sa
lettre la plus fréquente.
Une partition de la séquence est évaluée par la somme des
prédictions sur ses segments. Sur la base de cette évaluation on veut
pouvoir, grâce au prédicteur de chaque segment d'une partition, disposer
d'une redescription de haut niveau de la séquence qui mette en relief une
éventuelle structure de cette séquence. Il faut alors estimer le
nombre de segments en lequel il est le plus judicieux d'opérer cette
partition.
Nous présentons un algorithme qui, sur la donnée d'une séquence, d'un
ensemble de prédicteurs et d'un entier k, construit l'ensemble des
partitions optimales en i segments de la séquence pour tout i
entre 1 et k. C'est ce que nous appelons un partitionnement. Ceci
permet aussi d'observer l'évolution des partitions en fonction de leurs
nombres de classes. Ces observations peuvent aider à estimer un << bon >>
nombre de segments pour partager cette séquence.
L'algorithme présenté a une complexité en temps linéaire avec la
longueur de la séquence, la taille de l'ensemble des prédicteurs et le
nombre maximum de segments. On peut alors opérer le partitionnement
sur de très grandes séquences, et les séquences biologiques en
constituent un domaine naturel d'expérimentation.
Un programme a ete conçu sur ce modèle, avec un langage de déclaration
de prédicteurs qui autorise une très vaste gamme de prédicteurs, et
ceci nous a permis de faire quelques applications biologiques.