Méthodes de fouilles de données pour la prédiction de l’évolution du prix d’un billet

Yield Management

   Au sein d’une même cabine, la compagnie divise son avion en classes de réservation, ou classes tarifaires, ou encore classes de yield. C’est un découpage purement informatique, invisible pour le passager, et sans conséquence sur le positionnement des voyageurs à l’avant ou l’arrière de l’appareil. Il ne faut pas confondre ce découpage avec le découpage en classes de transport, que sont la première classe, la classe affaires et la classe économique. Les classes de réservation sont des sous-divisions de l’avion au sein même de ces cabines. Toutes ces classes sont emboîtées à la manière de poupées russes, de la classe la plus basse à la classe la plus haute. Chaque vol est décomposé en 10 à 20 classes de réservations. Elles sont désignées par des lettres de l’alphabet. En général, la première classe de transport contient les classes tarifaires P et F, la classe affairescontient les classes tarifaires J et C, et la classe économique contient le plus de classes tarifaires, dont la Y. L’IATA 1 recommande une certaine codification, mais chaque compagnie a ses propres habitudes. Ces classes sont emboîtées, au sens où une classe inférieure ne peut pas empiéter sur une classe supérieure, alors qu’une classe tarifaire supérieure peut préempter des sièges prévus pour une classe inférieure. Les compagnies low-cost2 appliquent pour la plupart les mêmes principes, mais d’une manière fortement simplifiée. Ainsi, le prix de leurs billets ne varie généralement que suivant deux facteurs : l’achat à l’avance, et l’état de remplissage de l’avion. À un instant donné, il n’existe qu’un seul prix pour le billet d’avion, valable pour tout le monde. Ce système est bien adapté à la clientèle plus homogène (essentiellement loisir) de ces compagnies, et présente également l’avantage d’être bien compris par les passagers, car il se résume par la formule simple “plus on achète tôt, moins c’est cher”. Dans la réalité, ce principe est infirmé quotidiennement par les algorithmes de revenue management qui doivent baisser les prix dans diverses situations : annulation de billet, augmentation de la taille de l’avion, retour de places allouées aux agences de voyages, etc. Nous allons d’ailleurs montrer dans la section “Pertinence”(1.5) de ce chapitre que nombre de lieux communs ne sont pas toujours vérifiés. Les algorithmes utilisés ont pour but essentiel de déterminer quelles classes de réservation seront ouvertes sur un vol, avec quel quota de sièges affecté à chacune. Il s’agit d’un contrôle de l’offre par ajustement des capacités disponibles. Par exemple, il faudra ouvrir beaucoup de sièges dans les basses classes de réservation et n’en garder que peu pour les passagers à haute contribution sur un vol en heure creuse, qui sinon ne sera pas rempli, alors que sur un vol en heures pleines il s’agira de procéder à l’inverse pour obtenir le revenu maximal. Exemple d’algorithme : Bid-Price Une des méthodes utilisées dans le domaine aérien pour maximiser les revenus est l’optimisation d’un vecteur représentant l’évolution du prix selon le remplissage de l’avion. Ces vecteurs nommés “bid-price vectors” sont des indications de modification de prix par cabine envoyées aux GDS3 afin qu’ils ajustent les prix annoncés au fur et à mesure du remplissage. Chaque cabine est divisée en classes associées à un tarif. Toutes les classes ayant un tarif inférieur au bid-price seront alors fermées à la vente. La création de ce vecteur se fait en plusieurs étapes et nécessite un certain nombre de paramètres d’entrée :
1. Les évolutions passées des demandes par cabine
2. Le type d’appareil permettant de connaître la capacité par cabine (première classe, business, économique)
3. Les divisions passées des cabines en classes : nombre de classes, capacité et tarifs de chaque classe
4. L’historique des présences des passagers (Entre 15 et 20% d’absence en moyenne)
5. L’historique des sièges alloués aux agences de voyages/brokers non vendus
6. Le seuil à partir duquel il est préférable de surclasser un passager plutôt que de lui changer son vol
Avec tous ces paramètres provenant de bases de données d’historiques, de nouvelles données sont calculées :
1. Le placement du rideau séparant la première de l’économique (pour les plus petits avions)
2. Le choix du nombre de sièges dépassant la capacité de l’appareil (surbooking)
3. La division des cabines en classes (capacité, tarif)
4. La prédiction de la demande sur l’ensemble des jours avant la date de départ
A partir de toutes ces données de sortie, il est alors possible de construire de manière certaine par des algorithmes d’optimisation, un vecteur de bid price optimal qui sera ensuite transmis au GDS pour qu’il puisse appliquer les règles de ventes de tous les vols en question (Figure 1.1). La modification des prix des classes peut se faire manuellement suite à la détection d’une trop grande différence entre la demande actuelle et la prévision, ou pour coller aux offres de la concurrence. Dans la majorité des cas ce processus d’optimisation est quotidien pour les vols dont la date de départ est proche et moins fréquent à mesure que l’on s’éloigne de celle-ci. La fluctuation des prix aura donc un comportement différent au fur et à mesure du temps et du remplissage. Nous allons voir dans la section suivante quelles sont les conséquences du yield management sur le comportement des séries de prix.

La longueur des séries temporelles

   Par l’évolution de la demande nous estimons la période à laquelle commencer l’étude des séries de prix. Le but est de couvrir le plus de demandes tout en conservant un jeu de données raisonnable et des séries consistantes. La ventilation représente l’évolution en pourcentage de la demande par rapport au nombre final de recherche. La Figure 1.9 représente les ventilations d’allers-retours pour différents types de destinations et différentes durées de séjours. Pour les long-courriers, la première moitié des recherches se fait entre un an et trois mois avant le départ et entre un an et 1 mois avant le départ pour les moyen-courriers. Dans notre exemple, nous couvrons avec les 28 derniers jours des séries temporelles 15% des utilisateurs pour les longcourriers et 50% pour les moyen-courriers, mais au global un tiers des usagers de liligo.com avec un nombre de recherches suffisant pour avoir des séries correctement échantillonnées. Par ailleurs, le mois précédant la date de départ correspond à une forte augmentation des sauts comme le montre la Figure 1.10 et donc de la volatilité des prix. C’est alors un moment crucial pour l’utilisateur qui voit les prix changer jusqu’à plusieurs fois par jour et où le conseil à l’achat s’avère déterminant. En accord avec les contraintes d’échantillonnage évoquées dans le chapitre précédent et au vu de la Figure 1.9, nous avons donc décidé de nous focaliser sur les 28 derniers jours des séries de prix, mais nous conservons toutes les informations précédant le dernier mois pour une application étendue à 90 jours de notre méthode. De la même manière, nous avons dans un premier temps restreint notre corpus de vols, mais pour une future extension de notre service, nous continuons d’enregistrer tous les résultats des recherches utilisateurs.

K-Means

   Nous voulons donc créer des groupes ayant des comportements similaires en appliquant l’algorithme de segmentation K-Means [28] en se basant sur les images pixélisées d’intensité Xbi pour i parcourant la base d’apprentissage. Les K-Means nécessitent une initialisation permettant d’enclencher la phase d’optimisation itérative. C’est une étape importante de l’algorithme qui peut être communément effectuée de deux manières différentes : par la méthode de Forgy et par les partitions aléatoires. La première méthode consiste à choisir aléatoirement C points de la base d’apprentissage comme étant les centroïdes puis d’attribuer aux autres vols le groupe correspondant au centroïde le plus proche. L’approche des partitions aléatoires consiste à attribuer à chaque vol un cluster aléatoirement. Empiriquement, Hamerly et al. [22] ont montré qu’il est préférable d’utiliser la méthode des partitions aléatoires pour les algorithmes de la famille des “k-harmonic means” et “fuzzy K-Means”. Pour les algorithmes d’Espérance-Maximisation et les K-Means standards l’approche de Forgy est conseillée. Les centroïdes sont ensuite construits en moyennant les vols de chaque groupe et l’algorithme suit alors le processus d’optimisation itératif en ré-attribuant son groupe le plus proche à tous les vols puis en calculant à nouveau les centroïdes. On obtient ainsi C classes d’indices I1, . . . , IC permettant de regrouper chaque vol i de la base d’apprentissage par comportements similaires d’évolution du prix. Ce nombre C de groupes est fixé arbitrairement et n’évolue pas avec les itérations. Il doit être choisi selon certains critères de performance tels que la densité des groupes ou le taux de bonne prédictions final. Cette étape est donc primordiale dans la construction de notre modèle, un mauvais choix de C pouvant dégrader rapidement l’étape de clustering et donc la prédiction. Il est possible de trouver le nombre optimal de classes en utilisant des critères tels que la statistique de GAP [48] ou l’indice de Calinski-Harabasz [11] que nous décrirons plus tard.

Adaboost

   Adaboost [19] est une technique de boosting basée sur la sélection itérative de classifieurs faibles (en l’occurence CART). L’idée est d’améliorer les compétences d’un faible classifieur c’est-à-dire celle d’un modèle de discrimination dont la probabilité de succès sur la prévision d’une variable qualitative est légèrement supérieure à celle d’un choix aléatoire. Introduit par Freund et Schapire, le boosting est une des méthodes d’ensemble les plus performantes à ce jour. Étant donné un échantillon d’apprentissage Vn et une méthode de prédiction faible (ici CART) qui construit un prédicteur hˆ(Vn). Un premier échantillon V1n est tiré aléatoirement (bootstrap), où chaque observation a une probabilité 1/n d’être tirée. Nous appliquons alors le classifieur de base à cet échantillon pour obtenir un premier prédicteur h(V1n). Ensuite, l’erreur de hˆ(V1n) sur l’échantillon Vn est calculé. Un deuxième échantillon bootstrap V2n est alors tiré en se basant sur les prédictions de hˆ(V1n). Le principe est d’augmenter la probabilité de tirer une observation mal prédite, et de diminuer celle de tirer une observation bien prédite. Nous réitérons alors le processus pour obtenir un ensemble de classifieur que nous agrégeons ensuite en faisant une moyenne pondérée. Le Boosting est donc une méthode séquentielle, chaque échantillon étant tiré en fonction des performances de la règle de base sur l’échantillon précédent. L’idée du Boosting est de se concentrer de plus en plus sur les observations mal prédites par la règle de base, pour essayer d’apprendre au mieux cette partie difficile de l’échantillon, en vue d’améliorer les performances globales.
Avantages : ce type d’algorithme permet de réduire sensiblement la variance mais aussi le biais de prévision comparativement à d’autres approches. Cet algorithme est considéré comme la meilleure méthode “off-the-shelf” [8], c’est-à-dire ne nécessitant pas un long pré-traitement des données ni un réglage fin de paramètres lors de la procédure d’apprentissage. Le boosting adopte le même principe général que le bagging : construction d’une famille de modèles qui sont ensuite agrégés par une moyenne pondéré des estimations ou un vote. Il diffère nettement sur la façon de construire la famille qui est dans ce cas récurrente : chaque modèle est une version adaptative du précédent en donnant plus de poids, lors de l’estimation suivante, aux observations mal ajustées ou mal prédites. Intuitivement, cet algorithme concentre donc ses efforts sur les observations les plus difficiles à ajuster tandis que l’agrégation de l’ensemble des modèles permet d’échapper au sur-ajustement. Les algorithmes de boosting existants diffèrent par différentes caractéristiques :
1. la façon de pondérer c’est-à-dire de renforcer l’importance des observations mal estimées lors de l’itération précédente
2. leur objectif selon le type de la variable à prédire Y : binaire, qualitative à k classes, réelles
3. la fonction perte, qui peut être choisie plus ou moins robuste aux valeurs atypiques, pour mesurer l’erreur d’ajustement
4. la façon d’agréger, ou plutôt pondérer, les modèles de base successifs.
La littérature sur le sujet présente donc de très nombreuses versions de cet algorithme et il est encore difficile de dire lesquelles sont les plus efficaces. Il est important de noter tout de même que dans le cas de forêts boostées, les arbres de décision doivent impérativement être élagués. En effet le boosting est réalisé sur la base des erreurs de prédiction en apprentissage des classifieurs faibles. Or, sans élagage, les arbres de décision sur-apprennent les données d’apprentissage jusqu’à avoir une erreur en apprentissage nulle dans la plupart des cas.

Table des matières

Introduction
1 Analyse exploratoire 
Introduction
1.1 Notations 
1.2 Yield Management 
1.3 Structure et description de nos données
1.3.1 Description des données
1.3.2 Structure de la base de données
1.4 Statistiques expliquant le choix des paramètres
1.4.1 Les trajets
1.4.2 La longueur des séries temporelles
1.5 Pertinence
1.5.1 Meilleur moment pour acheter
1.5.2 Proportion des baisses
1.5.3 Gain optimal
1.6 Conclusion et perspectives
2 Représentation des trajectoires 
Introduction
2.1 WorkFlow 
2.2 Notations
2.3 Séries temporelles
2.3.1 Problèmes d’échantillonnage
2.3.2 Comportements des trajectoires
2.3.3 Interpolation des trajectoires
2.4 Représentation par des processus ponctuels
2.5 Modélisation par de processus ponctuels poissonniens
2.5.1 Estimation de l’intensité – visualisation par niveaux de gris
2.5.2 Choix de la bande passante
2.6 Simulation
2.7 Conclusion et perspectives
3 Segmentation des données d’apprentissage 
Introduction
3.1 WorkFlow 
3.2 Notations 
3.3 Les algorithmes 
3.3.1 K-Means
3.3.2 Bagged K-Means
3.3.3 EM
3.4 Choix des paramètres 
3.4.1 Initialisation
3.4.2 Nombre de groupes
3.4.3 Dimensions des niveaux de gris
3.5 Conclusion et perspectives 
4 Apprentissage supervisé – Classification – Prédiction 
Introduction
4.1 WorkFlow 
4.2 Notations
4.3 Apprentissage
4.3.1 Arbres de décision : CART & C4.5
4.3.2 Adaboost
4.3.3 Forêts aléatoires (Random Forest)
4.4 Prédiction d’un comportement 
4.5 Prédiction directe
4.6 Approches séquentielles 
4.6.1 Classification uniquement par les premiers points
4.6.2 EM logit
4.7 Conclusion et perspectives 
5 Résultats expérimentaux 
Introduction
5.1 Mesures de performance 
5.1.1 Matrice de confusion
5.1.2 Évolution dans le temps
5.1.3 Courbe ROC
5.2 Résultats 
5.2.1 Segmentation
5.2.2 Classification
5.2.3 Influence de paramètres extérieurs
5.3 Autres approches 
5.3.1 Prédiction directe
5.3.2 Ajout des premières variations
5.4 Extensions
5.4.1 Évolution des performances dans le temps
5.4.2 Base étendue à 90 jours
5.5 Conclusion et perspectives
6 Implémentation 
Introduction
6.1 Collecte des données 
6.2 Construction du modèle 
6.2.1 Étapes menant à la création du modèle
6.2.2 Segmentation des étapes de calcul du modèle
6.3 Interface de comparaison des modèles
6.4 Implémentation du service web 
6.4.1 Rapidité
6.4.2 Clarté
6.4.3 Reproductibilité
6.5 Conclusion et perspectives

Télécharger le rapport complet