Exploration de classification supervisée d’ensemble de trajectoires
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.
