Brevet FR3088113A1 — publié le 20200508

PROCÉDÉ DE PRÉDICTION DU PROCHAIN TRAJET D'UNE PERSONNE Domaine de l'invention La présente invention concerne le domaine des services basés sur la localisation, en particulier dans le domaine du traitement des données de géolocalisation en grande masse. L'invention consiste en un système informatique capable d'apprendre, de modéliser les habitudes de déplacement d'une personne et de prédire de son futur déplacement, c'est-à-dire la prochaine destination, le prochain trajet, le temps de départ et le temps d'arrivée. État de la technique La mobilité humaine peut être approximée par le biais de multiples types de données : la géolocalisation par satellite (Global Positioning System ou GPS, Galileo), les données de signalisation du réseau mobile (Cali Data Record ou CDR), la triangulation de réseau (WiFi et/ou 3G, 4G), les enquêtes, etc. La technique inventée peut s'appliquer à n'importe quel type de données, tant qu'il contient une suite de positions ou adresses horodatées. Dans une réalisation particulière, on peut utiliser deux types de données de géolocalisation pouvant être directement collectées sur la plupart des téléphones mobiles d'aujourd'hui : les données issues du capteur GPS et les données de géolocalisation issue de la triangulation de réseau. La mobilité humaine est un sujet de recherche très actif. En effet, la modélisation et l'analyse de la mobilité humaine ont un grand impact sur nombreuses applications, comme par exemple les systèmes de recommandation, la gestion de trafic, la gestion du réseau de transport, la surveillance de la santé, la publicité et marketing digitale, le tourisme, etc. En effet, pour ces applications, la capacité d'apprendre les habitudes de mobilité des utilisateurs et de prédire leurs futurs déplacements les rend proactifs aux demandes des utilisateurs, ce qui permet de planifier intelligemment à l'avance les ressources, et ainsi de maximiser le rendement. Ces derniers années, grâce à la montée en flèche du nombre d'appareils personnels connectés à l'Internet et une large volumétrie de données de géolocalisation collectées via ces appareils, ce type prédiction devient possible. 2 Néanmoins, la prédiction de mobilité humaine reste encore un grand défi en raison de la grande complexité de la mobilité humaine. En effet, la mobilité humaine présent une certaine corrélation spatio-temporelle mais aussi un facteur non négligeable d'exploration et d'aléa. A cela viennent s'ajouter les multiples aléas de toutes natures, que ce soit au niveau 5 matériel que logiciel des systèmes mobiles. Par conséquent, les données collectées sont en réalité très imprécises, irrégulières et éparses. Ces complexités et ces natures des données réelles sont souvent négligées par les techniques existantes, mitigent leurs performances. Il y a plusieurs formulations de la prédiction de la mobilité humaine, parmi elles deux formulations suivantes sont les plus étudiées : 10 - La prédiction de l'endroit où se trouvera la personne au prochain créneau horaire. Cela se base sur une discrétisation du temps en créneaux horaires. - La prédiction de la prochaine destination. Il a été montré que le premier problème est beaucoup plus facile que le deuxième (« Understanding predictability and exploration in human mobility », Cuttone et. al.). Nous 15 nous intéressons ici au deuxième problème. En plus, notre solution prédit non seulement la prochaine destination, mais également le chemin probablement emprunté, l'heure de départ et l'heure d'arrivée. Le brevet US8392116B2 décrit un procédé pour prédire le prochain point d'arrivée d'un trajet à partir des paramètres du départ. Cette technique fonctionne avec les 20 données de géolocalisation de haute qualité, comme dans le cas de celles issues du système GPS. D'ailleurs, la solution se base sur une approche supervisée, en particulier les réseaux de neurone, ce qui nécessite un jeu de données d'entrainement, c'est-à-dire les données préalablement labélisées. Notre solution est plus adaptée pour les données irrégulières, imprécises et éparses, et ne nécessite pas des données labélisées. 25 Il est noté qu'il existe un ensemble de travaux existants sur la prédiction du trafic agrégé, c'est-à-dire., le déplacement d'une masse, tels que les brevets US870029682, US20060004511A1, US20110161261A1. Nous nous intéressons ici plutôt à la prédiction du prochain trajet d'un individu. Le brevet US20140358437A1 décrit un système capable de prédire le prochain trajet d'un utilisateur et de recommander la meilleure route en se basant sur son comportement observé dans le passé. La méthode présentée utilise directement les données de géolocalisation brutes, soit les adresses rentrées par l'utilisateur, soit mesurées par le biais 3 du système GPS ou la triangulation de réseau. Ceci rend la solution imprécise face aux données avec très forte incertitude. Notre technique intègre un module de recalage des données de géolocalisation sur une carte numérique, ce qui rend les trajets beaucoup plus précis. Le brevet US7233861B2 décrit un système informatique capable de prédire 5 le prochain trajet d'un véhicule. Cette technique utilise également les données GPS de très faible granularité et haute précision et donc ne convient pas aux données éparses. Encore une fois, les techniques de recalage sur carte numérique ne sont pas utilisées. D'ailleurs, cette solution capture le patron des déplacements de l'utilisateur grâce à un modèle basé sur des règles, ce qui limite sa performance face aux changements d'habitudes et d'explorations. Notre 10 solution se base sur un modèle bayésien hiérarchique qui converge intrinsèquement vers les habitudes les plus observées. Par conséquent, il est capable de s'adapter aux changements d'habitude. Beaucoup de techniques ont été inventées dans le domaine des systèmes de recommandation, notamment pour la recommandation de route. Le brevet US8855901B2 15 décrit un système informatique fournissant des recommandations de route pour les appareils mobiles. La technique exploite de multiples sources de données pour prédire des évènements qui auront probablement lieu sur les routes les plus probables. La technique présentée dans l'invention US9310211B1 permet d'extraire des modèles de déplacements basés sur un historique de géolocalisation. Plus précisément, le 20 brevet présente un procédé de regroupement de points de géolocalisation et un procédé de regroupement de trajets. Dans le brevet US20160321555A1, les auteurs présentent une technique de prédiction d'une destination probable proche de la position actuelle, utilisant un serveur de recherche de lieu géographique. Chaque lieu est associé à un score, qui est calculé en fonction 25 de plusieurs critères (la distance, la pertinence, le nombre de visites, etc.). Les données sont discrétisées par créneaux horaires dont la granularité est d'une heure. Un vecteur d'observations est défini (par exemple, mardi à 16h, place A, mardi à 17h, place B, etc.). La prédiction est basée sur un modèle Markovien. Il est connu que la mobilité humaine expose un caractère « à queue lourde », 30 c'est-à-dire que les gens ont tendance à se déplacer régulièrement entre très peu de points d'intérêt (par exemple, le déplacement maison-travail), et de temps en temps, ils réalisent des « sauts » vers une nouvelle destination (par exemple, un voyage à l'étranger). Ce caractère 4 statistique ressemble à celle du langage naturel. Une approche pour l'apprentissage des habitudes des déplacements humains se base donc sur des modèles utilisés pour le traitement du langage naturel (« Lossless Compression Based on the Sequence Memoizer », Gasthaus et. al, « Hierarchical Bayesian Nonparametric Approach to Modeling and Learning the Wisdom of 5 Crowds of Urban Traffic Route Planning Agents », Yu et. al). Solution apportée par l'invention L'invention concerne, selon son acception la plus générale, un procédé d'apprentissage automatique des habitudes de déplacements et de prédiction du prochain déplacement d'une personne à partir de l'enregistrement sur un serveur d'une succession de 10 données de géolocalisation horodatées. L'invention vise à apporter une solution technique pour la prédiction de la mobilité humaine, pour fournir les informations numériques correspondant à la prochaine destination ainsi que l'heure de départ vers cette destination de la personne, afin de commander des équipements matériels tels que des afficheurs, ou des équipements mobiles 15 autonomes, ou des équipements de gestion de flux d'équipements mobiles. Le but de l'invention n'est pas seulement conceptuel ou intellectuel. Le but est de fournir une information numérique, de manière automatique et sans intervention humaine, par une succession de traitements informatiques permettant de commander des équipements « intelligents » dans le domaine de la mobilité et de la gestion de véhicules et 20 autres engins autonomes, ainsi que dans le domaine de la gestion de flux de personnes. Dans le contexte des services basés sur la géolocalisation, ceci permet de résoudre le problème d'optimisation de ressources (capacité de mémoire, de calcul) car le système est capable de réagir proactivement aux demandes des utilisateurs en allouant préalablement des ressources nécessaires. Par conséquent, le système obtient un meilleur rendement tout en fournissant 25 une meilleure qualité de service. L'invention concerne une combinaison de moyens techniques (équipements connectés portés par les personnes et serveurs informatiques et de traitement informatique des données) pour fournir une information numérique prédictive qui peut ensuite commander une interface physique ou un équipement informatique. 5 L'invention concerne en particulier un système informatique distribué et un procédé de prédiction du prochain trajet d'une personne à partir de l'enregistrement sur un serveur d'une succession de données de géolocalisation horodatées transmise par un équipement connecté porté par la personne, comprenant les étapes suivantes : 5 - une première étape de détection et reconstruction des trajets réalisés par un procédé de détection de points stationnaires suivi par un procédé de recalage cartographique, - une deuxième étape de détection des points d'intérêt consistant à appliquer un algorithme de regroupement sur les points stationnaires détectés précédemment, - une troisième étape de regroupement de trajets similaires, 10 - une quatrième étape d'apprentissage des habitudes de déplacement par le biais d'un procédé qui utilise une arborescence pour enregistrer tous les enchainements observés des trajets, et un système de comptage afin de calculer les probabilités des enchainements, - une cinquième étape de prédiction consistant à apparier un contexte observé avec un 15 enchainement dudit arbre et de choisir un prochain trajet en fonction des probabilités précédemment calculées. Avantageusement, ladite étape de détection et reconstruction des trajets réalisés comporte un traitement informatique consistant en une identification des points stationnaires, une segmentation des données de géolocalisation en trajets et un recalage sur 20 une carte numérique de ces trajets, et un enregistrement de ces trajets avec leurs points stationnaires de départ et d'arrivée. De préférence, ladite étape de détection de points stationnaires comporte un traitement informatique itératif consistant à calculer la distance et l'écart temporel entre toutes les données de géolocalisation consécutives, à incrémenter un marquage visant à 25 détecter le début d'une stationnarité, et à appliquer une classification des données en 3 classes (mobile, ralentie et stationnaire) selon un indicateur de point stationnaire : la distance est inférieure à une valeur-seuil, et l'écart temporel supérieur à une valeur-seuil. Selon une variante, ladite étape de recalage cartographique comporte un traitement informatique consistant à appliquer un modèle de Markov caché dans lequel les 30 états correspondent aux positions probables des données de géolocalisation sur les routes, et les transitions correspondent aux probabilités de transitions entre les candidats, à effectuer une recherche des candidats d'une manière adaptative selon la précision des données de 6 géolocalisation, et à effectuer un calcul de probabilité de transition prenant en compte à la fois la distance et le nombre de tournants. Selon un mode de réalisation avantageux, ladite deuxième étape de détection de points d'intérêt comporte un traitement informatique consistant à appliquer un 5 algorithme de regroupement basé sur la densité des points stationnaires détecté et projeté sur une carte numérique dans la première étape. De préférence, ladite troisième étape de détection de trajets similaires comporte un traitement informatique consistant à regrouper les trajets avec les points de départ et points d'arrivée appartenant aux mêmes points d'intérêt. 10 Selon une variante, ladite étape d'apprentissage des habitudes de déplacement comporte un traitement informatique consistant à compresser tous les enchainements observés de trajet par le biais d'une arborescence dans laquelle chaque branche correspond à un enchainement. Selon une autre variante, ladite étape d'apprentissage des habitudes de 15 déplacement comporte un traitement informatique consistant à discrétiser l'heure de départ d'un trajet, à classifier les trajets selon leur heure et dates de départ, et à grouper les trajets selon une structure temporelle. Selon un mode de mise en oeuvre particulier, une arborescence est construite pour chaque élément de la structure temporelle. 20 Selon un autre mode de réalisation particulier, le comptage est effectué pour chaque enchainement de l'arbre. Avantageusement, ladite étape de prédiction comporte un traitement informatique consistant dans un premier temps à effectuer une recherche sur l'arbre l'enchainement le plus similaire à un contexte observé, et dans un second temps à trouver le 25 trajet ayant la plus forte probabilité de réalisation à partir de l'enchainement. Selon un mode de réalisation particulier, la recherche de l'enchainement comporte un traitement informatique consistant en un algorithme de calcul d'un score de similarité. 30 Ce procédé est notamment adapté aux données éparses et irrégulières. En outre, le procédé peut être appliqué aussi bien pour un traitement de données incrémentales qu'un traitement en masse. 7 Le procédé présenté en dessous, quand exécuté sur une machine, ou une ferme de calcul, comporte les étapes suivantes . La première étape consiste à reconstruire le trajet à partir des données de géolocalisation horodatées. Un trajet peut être considéré comme une entité composée de 3 5 parties : le lieu de départ (un point stationnaire), le déplacement (la partie mobile) et le lieu d'arrivé (un point stationnaire). Ce trajet est approximé, ou discrétisé, par une série temporelle de points de géolocalisation horodatés. La détection d'un trajet commence par la détection des points stationnaires pour retrouver ses extrémités. Plusieurs algorithmes peuvent être appliqués pour détecter ces points stationnaires. Selon un mode d'implémentation particulier, 10 un point peut être considéré stationnaire si sa distance à son prédécesseur est plus petit qu'un certain seuil et la durée depuis l'enregistrement de son prédécesseur dépasse un certain seuil. Une fois les points stationnaires détectés, on peut séparer les séquences de points en différents trajets. Ensuite, pour chaque trajet détecté, il s'agit de projeter les points de géolocalisation sur une carte numérique, afin de reconstruire la suite de routes suivies par la personne. Encore 15 une fois, plusieurs algorithmes de recalage automatique sur une carte numérique peuvent être appliqué. Avantageusement, cette étape permet d'avoir une estimation très précise du trajet. A la fin de cette étape, on obtient une série temporelle de trajets. A partir des trajets détectés et reconstruits, la deuxième étape consiste à détecter les points d'intérêt de la personne, c'est-à-dire les endroits les plus fréquentés par la 20 personne comme son lieu de résidence, son lieu de travail, la crèche où elle cherche son enfant tous les jours, etc. L'idée est de regrouper les points stationnaires précédemment détectés qui sont proches et ont une fréquence d'occurrence élevée. Pour cela, on peut appliquer différents algorithmes de partitionnement sur les points stationnaires détectés précédemment. La connaissance des points d'intérêt permet d'associer à chaque point de 25 départ et point d'arrivée à un point d'intérêt, ce qui permet de donner le sens de chaque trajet. Afin de reconstruire les habitudes de déplacement, l'étape suivante consiste à regrouper les trajets similaires. D'abord, une mesure de similarité est définie. Ensuite, plusieurs algorithmes de partitionnement peuvent être appliqués sur la base de cette similarité pour regrouper les trajets similaires. Selon un mode de réalisation particulier, on peut implémenter un simple 30 algorithme consistant à regrouper les trajets avec les points de départ et points d'arrivée appartenant aux mêmes points d'intérêt. On obtient donc à la fin de cette étape une série 8 temporelle de trajets réalisés dans laquelle chaque trajet a : son cluster correspondant, l'heure et la date de départ. A partir de la suite de trajets clustérisés, la quatrième étape consiste en la construction d'un modèle capable de capturer les habitudes de déplacement de la personne. 5 La série temporelle de trajets est d'abord divisée en plusieurs courtes séquences. Dans un mode de réalisation particulier, une séquence peut correspondre à une suite de trajets réalisés pendant une journée complète. Une arborescence sera construite d'une manière itérative pour capturer tous les enchainements possibles observés dans ces séquences de trajets. Chaque branche de l'arbre correspond à un enchainement observé. Pour chaque enchainement 10 observé, on effectue un comptage de son occurrence. Les enchainements les plus observés seront renforcés par ce comptage. Intuitivement, le tronc et les branches principale de l'arbre correspondent aux habitudes de déplacements les plus observés, tant dis que les petites branches correspondent aux déplacements irréguliers. Dans un mode de réalisation particulier, on peut construire plusieurs arbres correspondant à plusieurs jours de la semaine. Cette 15 structure de données permet de capturer finement la corrélation spatio-temporelle des déplacements. Surtout, elle est très flexible en cas de changement d'habitude. L'arbre va naturellement faire pousser de nouvelles branches, qui seront renforcées au fur et à mesure, et les anciennes branches vont « mourir ». Cela permet au modèle de s'adapter et de converger vers la nouvelle habitude. 20 Après l'apprentissage des habitudes, la prédiction du prochain trajet utilisant ledit modèle consiste à parcourir l'arbre pour trouver la branche qui correspond le mieux à un contexte donné. Un contexte peut être simplement l'heure actuelle, ou le dernier trajet observé, ou la séquence des trajets observés pour aujourd'hui. Le comptage réalisé à la construction de l'arbre permet d'obtenir une distribution de probabilité sur les enchainements 25 de trajets possibles à partir de la branche détectée. Selon un mode d'implémentation particulier, la prédiction peut correspondre à choisir l'enchainement de trajets avec la plus forte probabilité de réalisation. Ces étapes sont illustrées par FiG. 1. 30 9 Description détaillée d'un exemple non limitatif de l'invention La présente invention sera mieux comprise à la lecture de la description qui suit, concernant un exemple non limitatif de réalisation illustré par les dessins annexés où : - la FIG. 1 représente l'architecture matérielle du système pour la mise en oeuvre de 5 l'invention, - la FIG. 2 représente l'architecture fonctionnelle du système pour la mise en oeuvre de l'invention, - la FIG. 3 représente l'algorithme de classification automatique permettant de détecter les points stationnaires, 10 - la FIG. 4 représente le procédé de détection des points d'intérêt, - la FIG. 5 montre un exemple des points stationnaires, - la FIG. 6 illustre un procédé de recalage cartographique basé sur un modèle de Markov caché, - la FIG. 7 illustre le regroupement des points stationnaires pour la détection de 15 points d'intérêt, - la FIG. 8 illustre un mode de réalisation particulier de l'apprentissage automatique des habitudes de déplacement. Contexte général de l'exemple de réalisation décrit L'invention concerne un système informatique distribué et un procédé, exécuté sur un serveur 20 ou une ferme de calcul, pour fournir à une application tierce une information prédictive concernant le prochain trajet d'une personne ainsi que de son heure de départ, son point de départ, point d'arrivée, et le chemin probablement emprunté. Notons que nous nous intéressons ici seulement au niveau macroscopique de la mobilité, c'est-à-dire les déplacements entre les lieux dans la vie sociale d'une personne comme la maison, le lieu de 25 travail, le supermarché. 10 Architecture générale du système mis en oeuvre par l'invention Le système inclut un serveur ou une ferme de calcul (5), un ou plusieurs serveurs de stockage de données de géolocalisation (4), une application mobile apte à être installée et exécutée sur un équipement mobile (1) disposant d'un module de géolocalisation tel qu'un téléphone 5 portable, une tablette ou un ordinateur portable. Il inclut également un ou plusieurs serveurs web (3) pour recevoir des données de géolocalisation provenant des équipements mobiles et transmettre aux applications tierces des prédictions. La communication entre l'équipement mobile et le serveur web se fait via l'Internet (2) par le biais des réseaux 3G, 4G et/ou des réseaux Wi-Fi. 10 L'application mobile communique via le système d'exploitation mobile avec le module de géolocalisation pour recevoir des données de géolocalisation, qui contient en général des coordonnées de la position estimée, l'heure de la mesure ainsi que sa précision. La géolocalisation peut être réalisée via différentes méthodes : la triangulation satellitaire (système GPS, Galileo) (7), ou la triangulation réseau Wi-Fi (6), 36/4G (8). Un inconvénient pour 15 le GPS est qu'il demande beaucoup d'énergie. Pour minimiser la consommation de batterie de l'équipement mobile, un mode de réalisation consiste à combiner intelligemment lesdites deux méthodes de localisation, en espaçant les appels GPS par multiples localisations par la triangulation de réseau, qui consomme beaucoup moins d'énergie. Les données de géolocalisation sont ensuite stockées par les moyens de 20 stockage internes disponibles sur le téléphone. L'application mobile communique avec le module de communication pour transmettre périodiquement les données de géolocalisation horodatées au serveur web, qui les envoie par la suite aux serveurs de stockage. Pour pouvoir stocker les données provenant d'un grand nombre d'équipements, les données peuvent être distribuées sur un cluster de serveurs de stockage disposant de capacité d'auto-adaptation. 25 Les serveurs de calcul vérifient périodiquement s'il y a des nouvelles données disponibles. S'il y en a, la base de données est chargée de distribuer intelligemment les nouvelles données aux multiples serveurs de calcul. Chaque serveur traite indépendamment ses données et sauvegarde ses prédictions sur les bases de données, qui notifient le serveur web pour transmettre ces prédictions aux applications tierces. Ce mode d'implémentation 30 particulier est très avantageux car il permet de passer à l'échelle facilement en rajoutant des serveurs en fonction de la volumétrie de données à traiter (passage à l'échelle horizontale). 11 Traitements effectués par le serveur de calcul Le processus de prédiction se compose de cinq composantes principales : 1. la détection et reconstruction des trajets, 2. la détection des points d'intérêt, 5 3. la clusterisation des trajets, 4. l'apprentissage des habitudes et 5. la prédiction du prochain trajet. Au sens du présent brevet, on désignera par dt une donnée de géolocalisation (101) qui correspond à une position horodatée pour un équipement mobile 10 donné. Le serveur de calcul reçoit donc en entrée, pour chaque équipement mobile, une série temporelle D = (d1, c12, - - - , di). Détection et reconstruction de trajet (103) La première phase du traitement consiste à transformer la séquence D en une séquence de trajets, qu'on désignera T = (traj1,traj2,--- ,traji). Chaque trajet traj 15 contient trois parties : le lieu de départ, le déplacement et le lieu d'arrivée. Les lieux de départ et d'arrivée sont des endroits auxquels la personne passe un certain temps, par exemple la maison, le lieu de travail, le supermarché. On désignera par point stationnaire un tel lieu. Notons qu'un point stationnaire peut correspondre à un mouvement, comme dans le cas d'un supermarché. 20 La détection d'un trajet implique une détection des points stationnaires (102) afin de déterminer le début et la fin d'un trajet. Cette détection doit être incrémentale car les données arrivent en temps réel sur les serveurs de calcul. Pour cela, on applique une classification basée sur 2 métriques : la distance Ad et du temps écoulé At entre les données consécutives di, di+1. L'idée vient du constat que lorsque la personne est sur un point 25 stationnaire, les données sont clustérisées fortement au tour d'un point et la durée est longue. Trois classes sont définies : mobile, ralentie, stationnaire. On définit également un point d'encrage dencrage pour détecter le début d'une stationnarité. Ce point est initialisé à la première donnée reçue et mis à jour à chaque nouvelle donnée arrivée. Si la distance est plus grande qu'un seuil Ad Dmax, la donnée est qualifiée comme mobile et le 12 point d'encrage est mis à jour d -encrage = di. Au contraire si ad po ia = Poid,Poin = Poibr. L'algorithme de regroupement de trajet consiste donc à parcourir la liste de trajets et de regrouper les trajets avec les même POI de départ et POI. Les trajets venant ou arrivant à un point d'intérêt inconnu sont considérés comme bruits et ne sont pas utilisés pour 10 l'apprentissage des habitudes. Dans un autre mode de réalisation, on peut implémenter d'autres algorithmes de regroupement de trajectoires, tels que celui basé sur une similarité géographique décrit dans l'article J.-G. Lee, J. Han, and K.-Y. Whang, "Trajectory clustering," in Proceedings of the 2007 ACM SIGMOD international conference on Management of data - SIGMOD '07, 2007, p. 593. Avantageusement, le simple mode de réalisation décrit ci-dessus 15 permet d'extraire les habitudes les plus récurrentes et filtrer des explorations, ce qui est une bonne approche pour atteindre une bonne performance de prédiction, comme spéculé par l'étude de Cuttone et. al. « Understanding predictability and exploration in human mobility ». En plus, il est particulièrement avantageux en cas des données éparses et imprécises car on ne doit pas avoir recours à des critères géométriques, ce qui est beaucoup plus complexe à traiter 20 à cause de la dispersion des données. Apprentissage des habitudes (106) Une fois que les trajets sont regroupés (105), on obtient une séquence de trajets caractérisés par leurs heures de départ et leurs clusters correspondants. Le coeur de l'invention consiste en un modèle capable d'ingérer cette séquence afin de détecter/apprendre 25 les habitudes de déplacement. Dans un mode de réalisation particulier, les trajets sont d'abord regroupés selon les jours de la semaine. Dans un autre mode de réalisation particulier, on peut optionnellement considérer : jour moyen, jour de semaine/weekend, jour férié, etc. Pour chaque groupe on divise les trajets selon leurs dates. Par conséquent pour chaque groupe, on 30 obtient pour chaque jour de la semaine un vecteur Tfr,'r = (Tioçeur-,77oçeur, --- 7;50"eurnri, dans 16 lequel les éléments rsemi représentent les déplacements réalisés les mêmes jours des JOUI" semaines consécutives. Chaque élément correspond donc à une série temporelle des trajets caractérisé par leurs clusters et leurs heures de départ 5 jour = (C2Ih2),..., (cNIhN)) La minute de départ sont discrétisées par tranches de 10, 15, ... 30, ...,60 minutes. Par exemple, si la granularité choisie est de 30 minutes, on aura 2 tranches numéroté 0 et 1. Si l'heure de départ est 17h17, il sera 17h+0 alors que si l'heure de départ est 17h48, il 10 sera 17h-F1. Le choix de cette granularité dépend de l'application et de la précision requise. Si la granularité est faible, par exemple, 1 minute, la combinatoire des réalisations possibles augmentera significativement la durée d'apprentissage. Au contraire, si la granularité est grande, on aura une plus faible précision mais la durée d'apprentissage sera plus courte. Le modèle d'apprentissage consiste en un arbre de suffixe qui est une 15 structure de données sous forme d'une arborescence dans laquelle tous les enchainements possibles observées dans les séquences T.Selrii sont « compressés » et représentées par les jour branches. Sur ces branches, on effectue un comptage afin d'obtenir une statistique sur l'occurrence de différents enchainements possibles, qu'on appelle contextes. Pour chaque enchainement observé, un calcul de sa probabilité est également effectué. La FIG. 8 montre un 20 exemple d'un tel procédé. La construction de l'arbre se fait d'une manière dynamique selon le procédé décrit dans Algorithme 1. Avantageusement, ce modèle permet d'être flexible aux changements d'habitudes. En effet, quand la personne change son habitude, de nouvelles branches vont pousser. Les nouvelles données renforceront ces nouvelles branches et les branches 25 correspondant à l'ancienne habitude vont « disparaître » progressivement. L'arbre va converger vers les nouvelles habitudes. Prédiction du prochain trajet (107) La construction dynamique de l'arbre de suffixe et le système de comptage décrits précédemment permet de calculer la probabilité d'un enchainement à partir d'un 17 quelconque contexte déjà observé dans le passé. On obtient donc une distribution de probabilité à postériori des enchainements, qu'on désigne par P (traj = er'rral OÙ CT,traj et CT correspondent respectivement au nombre d'enchainement observé d'un trajet 5 traj suivi par une séquence de trajet T, et au nombre total de séquences T observées. Pour -une nouvelle observation Tsemr= (( 1110, (C2Ih2), (CaN)), jour Pour k de 1 à Ti ConLexLe Tisce'rfr = (c21112), - -- Ihk)) Parcourir l' arbre pour chercner le noeud T' parLageanL le plus long suffixe avec TisZtk. Si T' es L an suffixe du Tsem'M m,k Insérer Tiose', à l' arbre en tant qu'un fils de T' Si non T" étant la plus longue suffixe de T' et Tisotin`k Remplacer T' par T" Insérer T eL TZni)k en LanL que fils de T" Fin pour Algorithme 1 Construction de l'arbre de suffixe pour l'apprentissage des habitudes de déplacement 10 Selon l'invention, la prédiction consiste, dans un premier temps, à parcourir l'arbre pour trouver l'enchainement qui ressemble le plus au contexte actuel. Dans un mode d'implémentation particulier, on calcul pour chaque enchainement possible un score qui mesure le niveau de sa similarité avec le contexte observé. On définit le système de points 15 suivant : pour 2 trajets (ci khi), (ci I hi) {SpatialMatch ci = ci TemporalMatch hi = h1 . Temporal1HMatch = 'hi - h11 = 1 heure 10 18 Toujours dans ce mode de réalisation particulier, le calcul du score de similarité entre 2 séquences de trajet est effectué par Algorithme 2. On sélectionne ensuite l'enchainement avec le score de similarité le plus fort. Dans un autre mode de réalisation, au cas où un enchainement n'est pas 5 trouvé, un mécanisme de « back-off » peut être utilisé. Ceci consiste à réduire progressivement la dimension du contexte à apparier, jusqu'à ce qu'on trouve un enchainement. Selon l'invention, la prédiction du prochain trajet consiste à choisir le trajet avec la probabilité. En effet, trajprochain = argmax P(trajlT). traj EnLrées : Tôt,''é = ((Ce Mil, (CeS hr), (ces hvibs)), -Teontexte = score = -man - noir i de n à 1 pour j de jmak à 1 si ci°bs = Cs"' score - score + SpatialMatch s i hrs = ihcont score - score + TemporalMatch jmak = j - 1 - nreak si - lheure score - score + TemporallHMatch jmak = j - 1 break si i =n eL score REVENDICATIONS1 -Procédé de prédiction du prochain trajet d'une personne à partir de l'enregistrement sur un serveur d'une succession de données de géolocalisation horodatées transmises par un équipement connecté porté par la personne, comprenant les étapes suivantes : - une première étape de détection et reconstruction des trajets réalisés par un procédé de détection de points stationnaires suivi par un procédé de recalage cartographique, - une deuxième étape de détection des points d'intérêt consistant à appliquer un algorithme de regroupement sur les points stationnaires détectés précédemment, - une troisième étape de regroupement de trajets similaires, - une quatrième étape d'apprentissage des habitudes de déplacement par le biais d'un procédé qui utilise une arborescence pour enregistrer tous les enchainements observés des trajets, et un système de comptage afin de calculer les probabilités des enchainements, - une cinquième étape de prédiction consistant à apparier un contexte observé avec un enchainement d'un arbre et à choisir un prochain trajet en fonction des probabilités précédemment calculées. 2 - Procédé de prédiction du prochain trajet selon la revendication 1 caractérisé en ce que ladite étape de détection et reconstruction des trajets réalisés comporte un traitement informatique consistant en une identification des points stationnaires, une segmentation des données de géolocalisation en trajets et un recalage sur une carte numérique de ces trajets et une étape d'enregistrement de ces trajets avec leurs points stationnaires de départ et d'arrivée. 3 - Procédé selon la revendication 2 caractérisé en ce que ladite étape de détection de points stationnaires comporte un traitement informatique itératif consistant à calculer la distance et l'écart temporel entre toutes les données de géolocalisation consécutives, à incrémenter un marquage visant à détecter le début d'une stationnarité, et à appliquer une classification des données en 3 classes (mobile, ralentie et stationnaire) selon un indicateur de point stationnaire tel que la distance est inférieure à une valeur-seuil, et/ou l'écart temporel est supérieur à une valeur-seuil. 20 4 - Procédé selon la revendication 2 caractérisé en ce que ladite étape de recalage cartographique comporte un traitement informatique consistant à appliquer un modèle de Markov caché dans lequel les états correspondent aux positions probables des données de géolocalisation sur les routes, et les transitions correspondent aux probabilités de 5 transitions entre les candidats, à effectuer une recherche des candidats d'une manière adaptative selon la précision des données de géolocalisation, et à effectuer un calcul de probabilité de transition prenant en compte à la fois la distance et le nombre de tournants. 5 - Procédé de prédiction du prochain trajet selon la revendication 1 10 caractérisé en ce que ladite deuxième étape de détection de points d'intérêt comporte un traitement informatique consistant à appliquer un algorithme de regroupement basé sur la densité des points stationnaires détectés et projetés sur une carte numérique dans la première étape. 15 6 - Procédé de prédiction du prochain trajet selon la revendication 1 caractérisé en ce que ladite troisième étape de détection de trajets similaires comporte un traitement informatique consistant à regrouper les trajets avec les points de départ et points d'arrivée appartenant aux mêmes points d'intérêt. 20 7 - Procédé de prédiction du prochain trajet selon la revendication 1 caractérisé en ce que ladite étape d'apprentissage des habitudes de déplacement comporte un traitement informatique consistant à compresser tous les enchainements observés de trajet par le biais d'une arborescence dans laquelle chaque branche correspond à un enchainement. 25 8 - Procédé de prédiction du prochain trajet selon la revendication 1 caractérisé en ce que ladite étape d'apprentissage des habitudes de déplacement comporte un traitement informatique consistant à discrétiser l'heure de départ d'un trajet, à classifier les trajets selon leur heure et dates de départ, et à grouper les trajets selon une structure temporelle. 30 9 - Procédé selon la revendication 7 et la revendication 8 caractérisé en ce qu'une arborescence est construite pour chaque élément de la structure temporelle. 21 10 - Procédé selon la revendication 7 caractérisé en ce qu'un comptage est effectué pour chaque enchainement de l'arbre. 11 - Procédé de prédiction du prochain trajet selon la revendication 1 5 caractérisé en ce que ladite étape de prédiction comporte un traitement informatique consistant dans un premier temps à effectuer une recherche sur l'arbre l'enchainement le plus similaire à un contexte observé, et dans un second temps à trouver le trajet ayant la plus forte probabilité de réalisation à partir de l'enchainement. 10 12 - Procédé de prédiction du prochain trajet selon la revendication 11 caractérisé en ce que la recherche de l'enchainement comporte un traitement informatique consistant en un algorithme de calcul d'un score de similarité. 13 - Système de prédiction du prochain trajet d'une personne constitué par 15 un serveur et une pluralité d'équipements connectés, pour l'enregistrement sur ledit serveur d'une succession de données de géolocalisation horodatées transmises par au moins un équipement connecté porté par une personne, le système étant commandé par un programment réalisant un traitement comprenant les étapes suivantes : - une première étape de détection et reconstruction des trajets réalisés par un procédé de 20 détection de points stationnaires suivi par un procédé de recalage cartographique, - une deuxième étape de détection des points d'intérêt consistant à appliquer un algorithme de regroupement sur les points stationnaires détectés précédemment, - une troisième étape de regroupement de trajets similaires, - une quatrième étape d'apprentissage des habitudes de déplacement par le biais d'un 25 procédé qui utilise une arborescence pour enregistrer tous les enchainements observés des trajets, et un système de comptage afin de calculer les probabilités des enchainements, - une cinquième étape de prédiction consistant à apparier un contexte observé avec un enchainement d'un arbre et à choisir un prochain trajet en fonction des probabilités 30 précédemment calculées.