Classification non supervisée de données spatio-temporelles multidimensionnelles

Ce travail de thèse a été motivé par des questions posées autour d’une pathologie particulière, la sclérose en plaques  et le rôle de l’imagerie IRM pour la compréhension des mécanismes physiopathologiques sous-jacents, comme pour le suivi et la prise en charge des patients. Le but est d’identifier comment suivre, caractériser, comprendre des phénomènes variables dans l’espace et dans le temps à partir de données issues d’images. Ces problématiques nous ont amené à nous positionner sur la classification non supervisée de données spatio-temporelles multidimensionnelles et de ses applications en imagerie. L’objectif de ces méthodes de fouille de données est d’identifier des groupes d’observations similaires ; i.e. en traitement d’images grouper les pixels (en 2D) ou les voxels (en 3D) qui se ressemblent par rapport à une mesure de (dis)similarité donnée. L’objectif revient à maximiser la similarité des observations appartenant à un même groupe tout en maximisant la dissimilarité entre différents groupes, sans a priori sur le nombre ou la constitution des groupes à retrouver. Nous avons donc choisi de nous positionner sur des méthodes de classification non supervisée/clustering/groupement de données spatiotemporelles, car la sclérose en plaques est encore très méconnue des spécialistes de la santé. Sa génèse, l’origine des symptômes dont souffrent les patients ainsi que les traitements qui permettraient de la soigner sont des sujets qui suscitent beaucoup d’interrogations. Nous sommes donc dans le cas d’études prospectives de phénomènes encore méconnus, par conséquent l’introduction d’a priori dans les méthodes d’analyse n’est pas approprié car ils pourraient biaiser les conclusions obtenues.

Le clustering, ou groupement, de séries temporelles nécessite de faire face à deux grandes problématiques. Dans un premier temps, il faut choisir une mesure de comparaison des séquences à analyser en fonction des invariances nécessaires par rapport à l’application : facteur d’échelle en amplitude ou en temps, décalage en amplitude, déphasage temporel global ou distorsions temporelles locales, occultations de mesures ou complexité des séries temporelles [1]. Dans un second temps, il faut choisir un algorithme de groupement des séries temporelles afin de retrouver les différents ensembles constituant les données étudiées.

Les mesures de plus longue sous-séquence commune (PLSC) et de dynamic time warping (DTW) sont toutes deux issues de la distance de Levenshtein [6], ou plus communément appelée distance d’édition. Cette dernière formalise la notion de distance entre deux chaines de caractères comme le nombre minimal d’insertions, de suppressions ou de changements de caractères nécessaires pour les rendre identiques.  les raisons seront détaillées dans les paragraphes suivants. Néanmoins, comme la distance d’édition, elles prennent toutes deux en compte l’ordonnancement temporel des séquences pour déterminer la valeur de la mesure et sont robustes aux distorsions sur l’axe temporel pour le calcul de (dis)similarité.

Brièvement, l’analyse de la complexité en temps de la DTW est identique à celle présentée pour la PLSC. Elle est de l’ordre de Θ(δ.max(Tu, Tv)) ou Θ(δT) si Tu = Tv (Petitjean [8]) pour le calcul de la valeur de la DTW et de l’ordre Θ(Tu +Tv) pour la reconstruction du chemin d’alignements (Cormen et al. [9]). D’autres formes géométriques contraignant la zone de recherche du chemin d’alignements optimal ont été proposées, réduisant toujours la complexité calculatoire de la DTW, comme par exemple le parallélogramme d’Itakura [14]. Les contraintes sur les zones de recherche, i.e. sur les appariements autorisés et leurs importances dans le calcul de la DTW, sont définis via des valeurs de poids wl spécifiques à l’approche choisie.

La mesure DTW, comme la PLSC, ne contient pas de normalisation en amplitude des séries temporelles dans son formalisme permettant d’être invariant aux facteurs d’échelle en amplitude. Par conséquent, bien qu’insensibles aux déphasages temporels, ces mesures ne seront pas robustes en cas de trop fortes dissimilarités entre les dynamiques en amplitude des séries temporelles. Cette limitation peut être surmontée par une pré-normalisation des données temporelles ou bien par l’utilisation de métriques incluant une normalisation dans leurs formalismes .

Les mesures permettant de trouver des alignements élastiques entre les séries temporelles ont ensuite été abordées. Elles permettent d’imaginer que les séries temporelles puissent avoir des comportements similaires mais avec des évolutions étirées ou raccourcies. La PLSC, contrairement à la DTW, a pour particularité de pouvoir passer outre certains évènements en « sautant » des éléments dans les séries temporelles. Néanmoins, le fait d’ignorer certaines parties des évolutions de manière non maîtrisée, car considérées comme non informatives aux yeux de la PLSC, pourrait s’avérer problématique avec un but exploratoire et de compréhension des phénomènes évolutifs étudiés. Dans cette optique la DTW pourrait se présenter comme le choix le plus judicieux : les appariements retournés alignent tous les éléments d’une série u à au moins un élément de la série v et inversement. De plus, contrairement à la PLSC, elle ne nécessite pas de déterminer un seuil pour définir la similarité entre les séries, ce qui fait économiser le réglage d’un paramètre. Ces deux mesures sont capables de trouver des alignements élastiques mais restent sensibles aux dissimilarités en amplitude entre deux séquences. Les mesures basées sur la corrélation temporelle permettent quant à elles de surmonter cette limitation.