Blogue du CRIM - Exploration de classification supervisée d’ensemble de trajectoires

Blogue du CRIM - Exploration de classification supervisée d’ensemble de trajectoires

Publié le 30/01/18

Exploration de classification supervisée d’ensemble de trajectoires

par Jean-François Rajotte
Texte publié sur Medium

J’explore ici une technique de classification de trajectoires. Voici le problème que je voudrais résoudre: supposons que j’ai enregistré quelques trajectoires pour deux utilisateurs ID1 et ID2 et je voudrais savoir si un nouvel utilisateur IDX correspond plus à ID1 ou ID2.

Introduction

Pour me familiariser avec le domaine, j’ai regardé rapidement quelques articles sur l’analyse des trajectoires, par exemple ce survol de data mining (en anglais) et cet autre survol (en anglais).

Pour les adeptes de l’apprentissage profond, il y a aussi cet article de classification de trajectoires (en anglais), bien qu’il ne m’ait pas inspiré pour cette exploration.

Après un survol rapide des outils ouverts, mon choix s’est arrêté sur le package R trajectories qui semble simple d’utilisation.

Données

Pour cette exploration, j’utiliserai le Geolife GPS Trajectory Dataset de Microsoft. Ces trajectoires ont été récoltées de 2007 à 2012 à partir de 182 utilisateurs dans les environs de Beijing. De ces utilisateurs, je n’en analyserai que 7. Voici toutes les trajectoires sur un graphique:

La plupart des trajectoires sont localisées autour de la position 40 N et 116 E. Un graphique rapproché sur ces coordonnées permet d’avoir une meilleure idée de la complexité et de la diversité des trajectoires.

Comparaison de trajectoires

Pour cette analyse, je détermine arbitrairement que l’utilisateur ID1 est une référence et je voudrais savoir lequel des autres ID lui ressemble le plus. Si chaque ID n’avait qu’une seule trajectoire, je pourrais faire une comparaison de trajectoires comme la distance de Fréchet (en anglais).

Voici la première trajectoire de l’ID1:

Voici d’autres trajectoires de l’ID1 et une de l’ID6:

Pour ces 4 trajectoires, les distances de Fréchet par rapport à la trajectoire de référence (la première de l’ID1) sont:

  • ID1 track 2 = 11.98
  • ID1 track 3 = 0.98
  • ID1 track 4 = 11.91
  • ID6 track 3 = 1051

Les unités de distances sont les mêmes que celles des trajectoires.

Sans surprise, l’ID1 track 3 a la distance de Fréchet la plus petite puisque la trajectoire est presque identique à la première trajectoire de l’ID1.

Comparaison des ID

Ce qui m’intéresse, c’est de comparer deux ID, pas deux trajectoires. Une option serait de comparer la moyenne des distances de toutes les paires de trajectoires possibles entre les deux ID, mais on perdrait de l’information. Une autre option est d’utiliser la distribution des distances pour chaque paire de trajectoires. Par exemple, si ID1 comporte 4 trajectoires et ID2 comporte 6 trajectoires, l’histogramme de comparaison possédera 4*6=24 paires de trajectoires. Pour diminuer le temps de calcul, je limite le nombre de trajectoires pour l’ID de référence (ID1) à ses 3 premières trajectoires. Voici la distribution des distances entre toutes les paires de trajectoires des ID1, ID2 et ID3 par rapport aux trois premières trajectoires de l’ID1:

Dans le premier cas, l’ID1 est comparé avec lui-même, du moins avec ses trois premières trajectoires. On peut considérer cette valeur comme une référence minimale, c’est-à-dire que tous les autres ID auront une distribution plus étendue. Clairement, les moyennes de ces distributions peuvent aider à distinguer les utilisateurs, en particulier pour l’ID3. Dans le cas de l’ID2, les quelques distances au-delà de 60 seront peut-être diluées dans la moyenne et une valeur de l’étendue de la distribution (par exemple la variance) pourra aider à distinguer de l’ID1.

Conclusion

La classification par comparaison de trajectoires avec les trajectoires de références semble prometteuse. La prochaine étape de cette analyse serait de déterminer la performance de classification basée sur la moyenne et d’autres attributs issus des distributions comme la variance. En utilisant cette technique seulement sur la moitié des trajectoires des utilisateurs, on pourrait alors vérifier si les trajectoires restantes peuvent être associées à leur ID d’origine.

Devenez membre du CRIM

Devenir membre du CRIM, c’est bénéficier du plus grand réseau d’entreprises en TI au Québec. C’est un accès privilégié à notre expertise en recherche et développement. Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

514 840-7993

Événement à venir

  • HASE 2019
    3/01/19 2019h00
    Hangzhou, China
    Le CRIM présentera deux articles à la 19e édition du IEEE International Symposium on High Assurance Systems Engineering, qui se déroulera du 3 au 5 janvier 2019 à Hangzhou, Chine
    +
  • Montréal International RT @MTLINTL: #DYK Montréal has one of the deepest #AI talent pools in the world ???? More details ???? https://t.co/R073su8k8z #NeurIPS #NeurIPS2…
  • Tom Landry RT @Tom_Landry_: Hey @opengeospatial and @CRIM_ca ! Poster is set up at #AGU18 to present (draft) work of #MachineLearning task of Testbed-…