Machine Learning — Kaggle Competition

Reconnaissance de type de conduite

Par le biais de Kaggle, AXA nous a fourni un ensemble de données de plus de 50 000 voyages de pilotes anonymes. De nombreux paramètres furent à prendre en compte comme la durée des voyages, l’intensité des accélérations ou des freinages. Ces caractéristiques se combinent pour former un profil global qui rend potentiellement chaque pilote unique.

Pour cette compétition, nous devions trouver un classifieur capable de distinguer si un voyage a été conduit par un conducteur donné.

Début du concours: 2:00 pm, Lundi 15 Décembre 2014 UTC
Fin du concours: 11:59 pm, Lundi 16 Mars 2015 UTC (91 jours)

Participants :

I. EXPLICATIONS TECHNIQUES

Le but de ce challenge financé par AXA était de découvrir les trajets incorrects dans un ensemble de données de voyages. On nous a donné un total de 2 730 conducteurs, chacun avec 200 voyages. Quelques-uns de ces 200 voyages n’appartenaient pas au conducteur et la tâche était d’identifier lesquels.
Le trajet est l’ensemble des positions du véhicule prise chaque seconde.
Pour anonymiser le lieu du trajet :

  • le départ est à l’origine en (0,0)
  • les voyages ont été tournés au hasard
  • le début et la fin des voyages ont été supprimés

II. DÉVELOPPEMENT ET RÉSULTATS

Nous avons commencé par identifier les caractéristiques de base d’un trajet, comme sa longueur, sa durée et les centiles de vitesse et d’accélération. L’algorithme de machine learning retenu, car ayant de meilleurs résultats, fut le Random Forest[1] comprenant une forêt de 200 arbres et en prenant en compte tous les features. La plupart du temps, nous ne faisions qu’une forêt de 20 arbres pour amoindrir les temps de calcul. Ainsi, avec seulement les features les plus basiques nous avons obtenu un score de 83,8 %.

Nous avons ensuite tenté l’approche du taux de courbure. Pour cela, il a fallu interpoler le voyage avec splprep utilisant l’algorithme de Fitpack[2], puis calculer la courbure entre deux point. Notre score est monté à 86,1 % (+2,3 %)

Ensuite, nous nous sommes intéressé au taux de freinage à l’approche d’un arrêt, puis l’accélération lorsque la voiture repart. Si une voiture ne bouge que très peu durant trois secondes, nous estimions que la voiture était soit à l’arrêt, soit à une très faible vitesse (comme des bouchons). Cette feature met en évidence le caractère d’un individu (nerveux ou calme) et les caractéristiques de son véhicule (moteur puissant ou vieille voiture).

Pour aussi améliorer un peu les performances, nous avons détecté le nombre de points aberrants. Ceux-ci apparaissent lorsque le GPS perd la trace du conducteur. Dès qu’il le détecte à nouveau, le conducteur fait un bond dans l’espace qui ne dure que l’espace entre deux mesures, soit une seconde. Le nombre de pertes de signal d’un voyage peut indiquer une zone à faible couverture satellite ou la présence de tunnels. Pour ces deux features, l’amélioration n’aura été que de +0,3 % soit un total de 86,4 %.

Nous avons chercher toutes le rotations de routes possible d’un même conducteur pour chercher les parcours identiques. Dès qu’un voyage apparaissait au moins deux fois, on ne le considérait plus comme un faux voyage. Cette amélioration a fait monter notre score de 0,48 % (0,89% )

1. Tous les trajets (200 voyages)
2. Ceux étant très proches à une rotation près (38 voyages)
3. On fait une rotation pour mettre en évidence 2.

Nous avons testé quatre algorithmes de machine learning.

La régression logistique
Les meilleurs résultats étaient meilleurs avec C=1000 que C=1 (écart de 4%). La raison est simple, cette variable de régularisation permet d’autoriser des résidus plus élevés. Notre nombre élevé de features est en opposition avec la faible quantité d’informations qu’elles contiennent, car nous n’avons aucune certitude sur un couple voyage conducteur. Comme de nombreuses erreurs se glissent dans les données, un modèle qui est proche des données à des prédictions moindres. De plus, la régression logistique est modèle très linéaire qui fait des prédictions médiocres lors de nuages de points presque aléatoires.

SVM
Nous avons principalement testé cet algorithme avec le kernel par défaut : rbf. Ce modèle de prédiction aurait pu être bon avec notre jeu de données mais ce fut l’inverse. Nos meilleurs résultats furent avec la constante C=0.001, soit un nombre de résidu tout aussi élevé que la régression logistique. On peut imaginer la cause des mauvais résultats étant à la fois les données ayant trop d’erreurs, et aussi qu’un modèle quadratique ne s’applique potentiellement pas. Peut-être qu’il aurait dû augmenter la dimension de projection pour une prédiction plus fine, ou tenter le kernel polynomial.

Adaboost
C’est un méta-classifieur qui entraîne un « weak learner », comme le DecisionTreeCliassifier, en l’entraînant N fois sur un même jeu de données. Lorsqu’il obtient les résultats, il met un poids supérieur (ou Boots) aux éléments mal catégorisés pour que lors des N prochains entraînements les éléments plus durs à prédire aient plus d’attention. À l’inverse, les éléments bien catégorisés auront un poids plus faible. Ainsi, après M itérations, l’AdaBoost Classifier est plus performant que NxM itérations du « week learner » car il a une prédiction plus fine des éléments difficiles.
Dans notre challenge, il est compréhensible que se classifier ait eu un bon score, mais étonnant qu’il n’ait pas été encore meilleur. Peut-être que les challenges “difficiles” que l’Adaboost intensifie ne sont que du jerk (comme un trajet de 5 secondes à vitesse 0 m/s, impossible à prédire).

Random Forest
Le classifieur Random Forest est très similaire à l’Adaboost, à la différence que le vote n’est pas pondéré. Ainsi, la classe qui reçoit le plus de vote est choisi.
Le nombre de features utilisés par les arbres est égale au nombre de features (max_features=None) et on a choisi une forêt de 200 arbres pour un meilleur résultat (2000 a été essayé mais très peu supérieur). Le fait que le Random Forest a été meilleur que l’Adaboost indique sûrement que les voyages difficiles étaient très aléatoires et affaiblissaient les prédictions du classifieur.

Comparaison sur DecisionTree
Autres modèles non utilisés
- ExtraTreesClassifier
- Gradient Tree Boosting
- Réseaux de neurones

1ere Étape
On construit un jeu de données avec 200 de ses trajets choisis au hasard, que l’on suppose tous correct. On ajoute à ceux-là environ 70 trajets faux qui sont pris parmi des autres conducteurs.

Les 200 trajets sont labellisés ‘1’ (=correct), 60 des 70 faux trajets sont effectivement labellisés ‘0’ (=faux), et les 10 restants sont labellisés à tort ‘1’ pour introduire du “bruit”. Cette technique permet simuler le fait que nos données certains trajets sont labellisé ‘1’ à tord.

        Y_TRUE = 
(1,......,1,0,.....,0)
<---200---> <--~70--->
Y_NOISY =
(1,......,1,0,.,1,.,0)
<---200---> <--~70--->

2ème Étape
On entraîne le Random Forest sur ce jeu de données, en calculant pour chaque trajet les features présentés plus haut au nombre de 25.

3ème Étape
On itère les deux premières étapes 20 fois, de manière à avoir 20 classificateurs pour ce conducteur.

4ème Étape
On fait prédire sur un conducteur nos 20 classificateurs. On prend pour chaque trajet la moyenne des 20 classificateurs et on la considère comme notre meilleure prédiction.

III. RÉFÉRENCES

[1] Python Sklearn — ensemble : http://scikit-learn.org/stable/modules/ensemble.html
[2] Algorithme de courbure FITPACK utilisé par splprep : http://www.netlib.org/dierckx/readme
[3] Site de Kaggle : https://www.kaggle.com/
[4] Python Scipy — interpolate : http://docs.scipy.org/doc/scipy-0.14.0/reference/tutorial/interpolate.html