[PYTHON] Jusqu'à l'introduction et l'adoption de la proposition de recherche qui a remporté la première place à la KDD CUP 2019

Voici Ochiai de Docomo. Dans cet article, je présenterai les efforts [^ 1] qui ont remporté le championnat dans une catégorie de la Coupe KDD, qui est un concours d'analyse de données organisé à KDD2019. Je vais.

Vue d'ensemble de la KDD Cup 2019

Le contour de KDD a été présenté dans Article précédent, donc je vais me concentrer sur KDD Cup ici. Je vais expliquer. La KDD Cup est un concours de science des données rattaché à KDD, d'abord en 1997 et avec une tradition de plus de 20 ans. Jusqu'à l'année dernière, c'était une compétition dans laquelle des données et des tâches étaient données, des prédictions étaient faites et la précision était concurrencée, comme dans les compétitions ordinaires telles que Kaggle. J'ai défié la KDD Cup à Docomo R & D, et en 2016 je l'ai essayée pour la première fois et suis devenue finaliste. Dans KDD Cup 2019, la compétition conventionnelle pour la précision des prédictions se poursuivra en tant que tâche 1 de Regular ML Track, et en plus de cela, vous pouvez librement définir des tâches en utilisant des données données et proposer des recherches Regular ML Track Task 2, de l'apprentissage automatique AutoML Track, qui exécute automatiquement chaque processus (extraction de caractéristiques, construction de modèles de prédiction, vérification, etc.), et Humanity RL Track, qui est en concurrence pour des mesures visant à prévenir la propagation de l'infection palustre grâce à l'apprentissage par renforcement, ont été récemment créés. Chez Docomo, j'ai participé à toutes les pistes et j'ai pu remporter la 1ère place dans la tâche 2 régulière de la piste ML. https://www.kdd.org/kdd2019/docs/Winners_Regular_Baidu.pdf

Proposal Title: Simulating the Effects of Eco-Friendly Transportation Selections for Air Pollution Reduction Keiichi Ochiai, Tsukasa Demizu, Shin Ishiguro, Shohei Maruyama, Akihiro Kawana Film d'introduction à la recherche: https://www.powtoon.com/online-presentation/bugFjP07kIK/eco-friendly-transportation-selections

Détails de Regular ML Track

Le Regular ML Track a été parrainé par Baidu en Chine et a fourni un journal de recherche de transfert pour Baidu Maps. Il existe quatre types de journaux, mais nous n'expliquerons ici que les trois types utilisés dans Task2.

Description du journal fourni

Journal des requêtes de recherche (cité de la page officielle)

Dans le journal des requêtes de recherche, sid est l'ID de session, pid est l'ID d'utilisateur (en fait arrondi par des personnes ayant des profils similaires pour protéger la confidentialité), req_time est l'heure à laquelle la demande de recherche a été effectuée, o est la latitude et la longitude du point de départ, d Est la latitude et la longitude de la destination.

Journal des candidats d'itinéraire

Ceci est également une citation de la page officielle. Plusieurs itinéraires (transport, mode de transport) sont présentés pour une requête de recherche. Le mode de transport est un identifiant qui indique le transport, par exemple, 1 est un bus, 2 est un métro, etc. Cependant, comme il n'a pas été révélé quelle pièce d'identité correspond à quel transport, elle a été estimée à partir de diverses informations. Après cela, la distance correspond à la distance, l'ETA correspond au temps de trajet et le prix estimé correspond aux frais d'utilisation. Il existe plusieurs données de ce type pour une requête.

Cliquez sur le journal

Ceci est également une citation de la page officielle. Le journal des clics enregistre l'ID de session et le mode de trafic sélectionné. En utilisant Sid comme clé, vous pouvez lier les trois journaux décrits jusqu'à présent.

La tâche régulière de suivi ML1 était une tâche pour prédire le mode de trafic utilisé par l'utilisateur en fonction des journaux expliqués jusqu'à présent. Task2 utilise le journal ci-dessus pour définir librement des tâches et faire des propositions de recherche. La tâche 1 peut être évaluée avec une précision prédictive, mais la tâche 2 n'a pas un tel index, elle a donc été évaluée dans un format semblable à une soumission de papier normale dans laquelle un article de 4 pages est rédigé en anglais et le membre du comité évalue le contenu. ..

Contenu de la proposition

Notre équipe a fait une proposition liant les enjeux environnementaux du choix d'un mode de circulation et de la réduction de la pollution atmosphérique. J'expliquerai les détails d'ici.

Fond de recherche

Les problèmes environnementaux sont l'un des problèmes sociaux importants et des efforts de réduction du CO2 sont menés à l'échelle mondiale. En revanche, selon le Annonce de l'ONU, les émissions de CO2 en 2017 ont augmenté pour la première fois en quatre ans, et l'Accord de Paris 2 Il y a aussi une opinion selon laquelle l'objectif ℃ (maintenir l'élévation de température après la révolution industrielle à moins de 2 ℃) peut être difficile.

Sur la base de cette situation, je pense que non seulement les efforts au niveau national et au niveau de l’entreprise, mais aussi les efforts individuels sont importants. Une approche permettant aux individus de s'attaquer aux problèmes environnementaux consiste à choisir un transport respectueux de l'environnement dans leur vie quotidienne. Cependant, éviter simplement l'utilisation de transports émettant du CO2 nuirait à la vie des gens, de sorte que de telles actions ne seraient pas sélectionnées. En revanche, si cela n'interfère pas avec votre vie, il vous sera peut-être demandé de choisir un moyen de transport qui conduira à une réduction de CO2. On pense que les utilisateurs seront motivés à faire un choix s'ils savent à quel point ils peuvent contribuer à la réduction des émissions de CO2 lorsqu'ils changent de mode de transport. Cependant, pour montrer l'effet quantitativement, nous avons besoin d'un journal sur les moyens de transport des personnes.

Par conséquent, dans cette recherche, nous simulerons la réduction des émissions de CO2 lorsqu'un mode de transport respectueux de l'environnement est sélectionné en utilisant le journal du service de recherche de transfert et en supposant que le véhicule a réellement été déplacé par le mode de transport cliqué. .. De plus, comme on pense que l'augmentation de la marche et des déplacements à vélo aura un effet positif sur la santé, nous évaluerons quantitativement l'effet sur la santé.

approche

Idée basique

À partir du journal des candidats d'itinéraire présenté à un utilisateur, les émissions de CO2 lors de l'utilisation de chaque mode de trafic peuvent être calculées à l'aide de la formule suivante.

Émissions de CO2 = distance parcourue (km) x unité de distance / émissions de CO2 par personne (g / personne / km)

Étant donné que la distance parcourue est dans le journal des candidats d'itinéraire, vous pouvez calculer les émissions de CO2 si vous connaissez l'unité de distance et les émissions de CO2 par personne. Certaines des données sont publiquement par la Transportation Ecology and Mobility Foundation, et nous les utiliserons. .. Par exemple, si Bus et Cyclisme sont les journaux suivants des itinéraires candidats, le calcul peut être effectué comme indiqué dans le cadre rouge ci-dessous.

Vous pouvez également voir dans le journal des clics que cet utilisateur cliquait sur Bus. Nous définissons ici que des modes de trafic alternatifs sont acceptables:

** Temps de parcours alternatif (ETA) ≤ Temps de parcours cliqué ** ** Émissions de CO2 de l'itinéraire alternatif <Émissions de CO2 de l'itinéraire cliqué **

La première condition est que le temps de parcours soit inférieur ou égal au temps de parcours initialement sélectionné par l'utilisateur. Les modes de transport respectueux de l'environnement sont la marche et le vélo, mais même s'il y a un candidat pour marcher loin, il ne sera pas sélectionné. D'autre part, on suppose qu'ils seront acceptés si le temps de trajet du mode de trafic sélectionné à l'origine n'est pas dépassé. La deuxième condition est de réduire les émissions de CO2. Selon cette définition d'acceptabilité, le cyclisme est acceptable dans l'exemple précédent. Appliquez-le à tous les journaux de recherche. Dans le journal réel, étant donné que les moyens de transport qui satisfont aux conditions ci-dessus sont recherchés pour des centaines de milliers de requêtes de recherche, il peut être formulé comme un ** problème d'optimisation de combinaison **.

Formulation comme problème d'optimisation d'entiers

Formulez la sélection du mode de trafic comme un problème d'optimisation de 0 à 1 entier avec des contraintes de temps de trajet et d'émission de CO2 Les fonctions objectives et les contraintes à minimiser sont les suivantes.

Ici, $ P_ {i, j} $ est l'émission de CO2 lorsque l'utilisateur $ i $ sélectionne le mode de trafic $ j $, et $ Q_ {i, j} $ est l'utilisateur $ i $ est le mode de trafic $ j $. Temps de trajet lorsqu'il est sélectionné, $ Q \ prime_ {i, j} $ est le temps de trajet en mode trafic sur lequel l'utilisateur $ i $ a cliqué (en supposant qu'il ait réellement voyagé), $ X_ {i, j} $ est sélectionné C'est une valeur comme un vecteur One-hot où seul le mode de trafic est 1 et les autres sont 0. De plus, $ m $ indique le nombre d'identifiants de session et $ n $ indique le nombre de modes de trafic. Au moment du montage, les unités sont différentes pour les émissions de CO2 et le temps de trajet, les deux sont donc normalisées.

Le tutoriel du professeur Umetani de l'Université d'Osaka a été très utile pour la formulation en tant que problème d'optimisation.

Introduction à l'optimisation des combinaisons: de la planification linéaire à la planification entière https://www.slideshare.net/shunjiumetani/ss-17197023

S'il peut être formulé, il utilisera un solveur existant pour le résoudre. Cette fois, j'ai utilisé une bibliothèque appelée PuLP.

résultat

Nous avons comparé les résultats après optimisation avec le journal des clics de l'utilisateur comme base de référence. Les résultats sont présentés dans le tableau ci-dessous. Optimisé pour les journaux de recherche d'environ 400 000 requêtes.

Les émissions de CO2 semblent être réduites d'environ 9,23%. Étonnamment, le résultat a été que le temps de trajet pourrait être réduit de 9,96%. L'utilisateur ne clique pas nécessairement sur l'itinéraire le plus rapide.

Voyons ensuite comment les moyens de transport ont évolué en raison de l'optimisation. Dans le tableau ci-dessous, la gauche entre parenthèses est le mode de trafic sur lequel l'utilisateur a cliqué et la droite est le mode de trafic sélectionné par optimisation.

Étant donné que le journal publié se trouve dans le centre de Pékin, il semble qu'il y ait eu de nombreux cas de déplacements à courte distance en bus ou en métro, et il semble qu'il y ait eu de nombreux changements pour le changer en vélo (cadre rouge dans le tableau). Par contre, dans le cas des voitures particulières (conduite), le nombre de cas qui ont changé pour les vélos est faible, et la plupart sont des voitures privées (cadre bleu dans le tableau). Où voyager en voiture est loin et il n'y a peut-être pas d'alternative.

Je ne donnerai qu'un aperçu des effets sur la santé. Une étude de l'Université d'Oxford a analysé l'effet de la bicyclette sur la réduction de la mortalité (l'article est ceci). Selon cette étude, le taux de mortalité totale est réduit de 10% lorsque la quantité d'exercice recommandée par l'OMS (11,25 METh / semaine d'exercice physique, 150 minutes d'exercice aérobie modéré) est effectuée. À partir de cette simulation, les utilisateurs peuvent calculer qu'en moyenne, ils font du vélo pendant 23,04 minutes en moyenne (13,63% recommandé par l'OMS) par jour. Nous avons considéré que la combinaison des deux pourrait réduire le taux de mortalité total de 10 $ % \ fois 13,63 % = 1,36 % $.

Comme vous pouvez le voir d'après les résultats des changements dans les transports, le résultat de cette étude est que les vélos peuvent être remplacés par des vélos. Cependant, si vous essayez réellement de faire cela, il y a un problème avec l'espace de stationnement pour vélos, le mode de transport accepté change en fonction de la météo (je ne veux pas me déplacer à vélo s'il pleut), comment amener l'utilisateur à choisir un moyen de transport à faible émission de CO2 Il y a encore des problèmes tels que UI / UX jusqu'à une utilisation pratique. En outre, bien que l'on suppose que vous avez déménagé en fonction du mode de transport / de l'itinéraire sur lequel vous avez cliqué dans la recherche de transfert, il existe également une restriction fondamentale selon laquelle vous ne savez pas comment vous avez réellement déménagé.

la mise en oeuvre

Enfin, je voudrais vous présenter un peu la mise en œuvre. Pour la mise en œuvre, je me suis référé à l'article suivant. https://qiita.com/samuelladoco/items/703bf78ea66e8369c455 https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

Créez à l'avance un dictionnaire contenant les émissions de CO2 dans c_co2 [i, j] et le temps de trajet (utilisateur i, mode de trafic j) dans c_eta [i, j]. Par exemple, cela ressemble à ceci. c_eta[2,1] = 1976.0, c_eta[2,3] = 1146.0, c_eta[2,4] = 1446.0, c_eta[2,5] = 2246.0, c_eta[2,6] = 818.0 Dans cet exemple, on suppose que l'utilisateur avec l'ID d'utilisateur n ° 2 se voit présenter les modes de trafic 1, 3, 4, 5, 6 comme candidats, et le temps de trajet dans chaque mode de trafic est comme indiqué ci-dessus.

import pulp
problem = pulp.LpProblem("ETA-CO2 minimize", pulp.LpMinimize)
x = {}

# 0-1 Définir la variable(Contrainte 3 X_{i,j}Est 0,Correspond à la contrainte que 1 est 2 valeurs)
# define 0-1 variable
for i in I:
    for j in J:
        x[i,j] = pulp.LpVariable("x({:},{:})".format(i,j),  0, 1, pulp.LpBinary)

#Définissez la fonction objectif. Normaliser en divisant le temps de trajet et les émissions de CO2 par la valeur maximale.
# define objective function. ETA and CO2 emission are normalized by dividing max
max_co2 = max(c_co2.values())
max_eta = max(c_eta.values())
problem += pulp.lpSum( ((c_co2[i,j]/max_co2) * x[i,j]) + ((c_eta[i,j]/max_eta) * x[i,j]) for i in I for j in J if (i,j) in c_co2), "TotalCost"

#Contrainte 1:Un mode peut être attribué à l'utilisateur i
# constraint 1: each user can be assigned one mode
for i in I:
    problem += sum(x[i,j] for j in J if (i,j) in c_co2 ) == 1, "Constraint_leq_{:}".format(i)

#Contrainte 2:Plus court que le temps de trajet du mode trafic cliqué par l'utilisateur i
# click_log_Le journal des clics est inclus dans df en tant que dataframe pandas
# constraint 2: set "acceptable" condition
for n, t in click_log_df.iterrows():
    i = int(t["sid"])
    if (i,int(t["transport_mode"])) in c_co2:
        baseline = int(c_eta[i, int(t["transport_mode"])]*1.0)

    problem += sum(c_eta[i,j]*x[i,j] for j in J if (i,j) in c_co2 ) <= baseline, "Constraint_co2eq_{:}".format(i) 

#Spécifiez un solveur
# set solver
solver = pulp.solvers.PULP_CBC_CMD()
result = problem.solve(solver)
#Indique si l'optimisation était possible ou non et la valeur d'évaluation à ce moment-là
# output
print(pulp.LpStatus[result], pulp.value(problem.objective))

Chronologie

Le numéro de Regular ML Track of KDD Cup 2019 est sorti vers le 4/13. Après cela, j'ai soumis l'article selon le calendrier suivant.

4/19 Première réunion (rédaction de la méthode d'utilisation des données) 5/8 Réunion # 2 (Rédaction de la méthode d'utilisation des données et décision de la politique) 5/15 Réunion # 3 (Implémentation d'un programme d'optimisation, l'optimisation n'a pas convergé à ce stade) 5/31 Réunion n ° 4 (mise en œuvre de l'optimisation terminée) 6 / 3-10 Rédaction d'un article (4 pages en anglais) 6 / 11-12 calibrage anglais 6/13 Message 6/15 Date limite de soumission (la date limite sera prolongée à une date ultérieure d'ici la fin juin)

En 2019, il y a eu 10 jours fériés consécutifs pendant la Golden Week, et dans environ un mois et demi, nous avons décidé des thèmes de recherche, les avons mis en œuvre et écrit des articles.

finalement

Je ne connaissais pas moi-même les problèmes d'optimisation, mais un collègue avec lequel je travaillais m'a expliqué en détail la formulation, la mise en œuvre de Pulp et ce qu'il faut faire si l'optimisation ne fonctionne pas. En outre, un autre membre suggère de l'appliquer à des problèmes environnementaux, et où chaque mode de trafic est fourni uniquement par ID, quel ID est le mode de trafic publié sur le Web des tarifs et des données C'est une recherche que chaque membre de l'équipe a contribué à identifier en regardant les statistiques. J'aimerais continuer à faire des recherches intéressantes et sensibiliser à l'analyse des données de DoCoMo et aux domaines de l'IA grâce à des activités externes telles que des présentations lors de conférences, et je voudrais continuer à défier les grandes conférences telles que KDD.

Alors tout le monde, joyeux Noël et bonne année!

[^ 1]: A remporté la première place au monde au plus haut concours d'analyse de données au monde "KDD CUP 2019" https://www.nttdocomo.co.jp/binary/pdf/info/news_release/topics_190809_01.pdf