[PYTHON] Bis zur Einführung und Annahme des Forschungsvorschlags, der beim KDD CUP 2019 den ersten Platz belegte

Das ist Ochiai von Docomo. In diesem Artikel werde ich die [^ 1] Bemühungen vorstellen, die die Meisterschaft in einer Kategorie des KDD Cup gewonnen haben, bei dem es sich um einen Datenanalyse-Wettbewerb handelt, der bei KDD2019 stattfindet. Ich werde.

Übersicht über den KDD Cup 2019

Der Umriss von KDD wurde in Vorheriger Artikel vorgestellt, daher werde ich mich hier auf den KDD Cup konzentrieren. Ich werde erklären. Der KDD Cup ist ein datenwissenschaftlicher Wettbewerb, der 1997 an KDD angeschlossen wurde und eine Tradition von mehr als 20 Jahren hat. Bis zum letzten Jahr war es ein Wettbewerb, bei dem Daten und Aufgaben angegeben, einige Vorhersagen getroffen und die Genauigkeit wie bei normalen Wettbewerben wie Kaggle überprüft wurden. Ich habe den KDD Cup bei Docomo R & D herausgefordert und 2016 habe ich ihn zum ersten Mal ausprobiert und bin Finalist geworden. Im KDD Cup 2019 wird der konventionelle Wettbewerb um Vorhersagegenauigkeit als Aufgabe 1 des regulären ML-Tracks fortgesetzt. Darüber hinaus können Sie anhand der angegebenen Daten frei Aufgaben festlegen und die reguläre ML-Track-Aufgabe 2 des maschinellen Lernens vorschlagen AutoML Track, das jeden Prozess automatisch ausführt (Merkmalsextraktion, Erstellung von Vorhersagemodellen, Verifizierung usw.), und Humanity RL Track, das um Maßnahmen zur Verhinderung der Ausbreitung von Malariainfektionen durch verstärktes Lernen konkurriert, wurden neu eingerichtet. Bei Docomo nahm ich an allen Strecken teil und konnte den 1. Platz in der regulären ML-Streckenaufgabe 2 gewinnen. 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 Forschungseinführungsfilm: https://www.powtoon.com/online-presentation/bugFjP07kIK/eco-friendly-transportation-selections

Details zur regulären ML-Strecke

Der reguläre ML-Track wurde von Baidu in China gesponsert und lieferte ein Transfersuchprotokoll für Baidu Maps. Es gibt vier Arten von Protokollen, aber hier werden nur die drei in Task2 verwendeten Typen erläutert.

Beschreibung des bereitgestellten Protokolls

Suchanfrageprotokoll (zitiert von der offiziellen Seite)

Im Suchabfrageprotokoll ist sid die Sitzungs-ID, pid die Benutzer-ID (tatsächlich gerundet durch Personen mit ähnlichen Profilen zum Schutz der Privatsphäre), req_time ist der Zeitpunkt, zu dem die Suchanforderung gestellt wurde, o ist der Breiten- und Längengrad des Abfahrtspunkts, d Ist der Breiten- und Längengrad des Ziels.

Routenkandidatenprotokoll

Dies ist auch ein Zitat von der offiziellen Seite. Für eine Suchabfrage werden mehrere Routen (Transport, Transportmodus) angezeigt. Der Transportmodus ist eine ID, die den Transport angibt, z. B. 1 ist ein Bus, 2 ist eine U-Bahn und so weiter. Da jedoch nicht bekannt gegeben wurde, welche ID welchem Transport entspricht, wurde sie anhand verschiedener Informationen geschätzt. Danach ist Entfernung die Entfernung, ETA die Reisezeit und der geschätzte Preis die Nutzungsgebühr. Es gibt mehrere solcher Daten für eine Abfrage.

Klicken Sie auf Protokoll

Dies ist auch ein Zitat von der offiziellen Seite. Das Klickprotokoll zeichnet die Sitzungs-ID und den ausgewählten Verkehrsmodus auf. Mit sid als Schlüssel können Sie die drei bisher beschriebenen Protokolle verknüpfen.

Die reguläre ML-Track-Aufgabe1 war eine Aufgabe, den vom Benutzer verwendeten Verkehrsmodus anhand der bisher erläuterten Protokolle vorherzusagen. Task2 verwendet das obige Protokoll, um Aufgaben frei festzulegen und Forschungsvorschläge zu machen. Task1 kann mit Vorhersagegenauigkeit bewertet werden, Task2 verfügt jedoch nicht über einen solchen Index. Daher wurde er in einem Format wie einer normalen Papiereinreichung bewertet, in dem ein 4-seitiges Papier in englischer Sprache verfasst ist und das Ausschussmitglied den Inhalt bewertet. ..

Angebotsinhalt

Unser Team hat einen Vorschlag gemacht, der die Umweltprobleme der Wahl eines Verkehrsmodus und der Reduzierung der Luftverschmutzung miteinander verbindet. Ich werde die Details von hier aus erklären.

Forschungshintergrund

Umweltprobleme sind eines der wichtigsten sozialen Probleme, und es werden weltweit Anstrengungen zur Reduzierung des CO2-Ausstoßes unternommen. Auf der anderen Seite stiegen laut der UN-Ankündigung die CO2-Emissionen im Jahr 2017 zum ersten Mal seit vier Jahren und im Pariser Abkommen 2 Es gibt auch eine Meinung, dass das ℃-Ziel (den Temperaturanstieg nach der industriellen Revolution innerhalb von 2 ℃ zu halten) schwierig sein könnte.

Angesichts dieser Situation denke ich, dass nicht nur Anstrengungen auf nationaler und Unternehmensebene, sondern auch individuelle Anstrengungen wichtig sind. Ein Ansatz für Einzelpersonen zur Bewältigung von Umweltproblemen besteht darin, in ihrem täglichen Leben umweltfreundliche Transportmittel zu wählen. Die bloße Vermeidung der Verwendung von Transportmitteln, die CO2 ausstoßen, würde jedoch das Leben der Menschen behindern, sodass solche Maßnahmen nicht ausgewählt würden. Wenn es Ihr Leben jedoch nicht beeinträchtigt, werden Sie möglicherweise aufgefordert, ein Transportmittel zu wählen, das zu einer CO2-Reduzierung führt. Es wird davon ausgegangen, dass Benutzer motiviert sind, eine Entscheidung zu treffen, wenn sie wissen, wie viel sie bei der Änderung der Transportmethoden zur CO2-Reduzierung beitragen können. Um den Effekt quantitativ darzustellen, benötigen wir jedoch ein Protokoll über die Transportmittel der Menschen.

Daher werden wir in dieser Studie das Ausmaß der Reduzierung der CO2-Emissionen simulieren, wenn eine umweltfreundliche Transportmethode ausgewählt wird, indem wir das Protokoll des Transfersuchdienstes verwenden und davon ausgehen, dass sich das Fahrzeug tatsächlich mit der angeklickten Transportmethode bewegt hat. .. Da davon ausgegangen wird, dass sich eine zunehmende Bewegung beim Gehen und Radfahren positiv auf die Gesundheit auswirkt, werden wir die Auswirkungen auf die Gesundheit quantitativ bewerten.

Ansatz

Grundidee

Aus dem einem Benutzer vorgelegten Routenkandidatenprotokoll können die CO2-Emissionen bei Verwendung jedes Verkehrsmodus mithilfe der folgenden Formel berechnet werden.

CO2-Emissionen = Fahrstrecke (km) x Einheitsentfernung / CO2-Emissionen pro Person (g / Person / km)

Da sich die Fahrstrecke im Routenkandidatenprotokoll befindet, können Sie die CO2-Emissionen berechnen, wenn Sie die Einheitsentfernung und die CO2-Emissionen pro Person kennen. Einige der Daten werden öffentlich von der Transportation Ecology and Mobility Foundation verwendet und werden von uns verwendet. .. Wenn beispielsweise Bus und Radfahren die folgenden Protokolle von Routenkandidaten sind, kann die Berechnung wie im roten Rahmen unten gezeigt durchgeführt werden.

Sie können auch aus dem Klickprotokoll ersehen, dass dieser Benutzer auf Bus geklickt hat. Hier definieren wir, dass alternative Verkehrsträger akzeptabel sind:

** Alternative Routenfahrzeit (ETA) ≤ Angeklickte Routenfahrzeit ** ** CO2-Emissionen der alternativen Route <CO2-Emissionen der angeklickten Route **

Die erste Bedingung ist, dass die Reisezeit kleiner oder gleich der ursprünglich vom Benutzer ausgewählten Reisezeit ist. Die umweltfreundlichen Verkehrsträger sind Wandern und Radfahren, aber selbst wenn es einen Kandidaten gibt, der weit laufen kann, wird er nicht ausgewählt. Andererseits wird davon ausgegangen, dass sie akzeptiert werden, wenn die Fahrzeit des ursprünglich ausgewählten Verkehrsmodus nicht überschritten wird. Die zweite Bedingung ist die Reduzierung der CO2-Emissionen. Nach dieser akzeptablen Definition ist Radfahren im vorherigen Beispiel akzeptabel. Wenden Sie dies auf alle Suchprotokolle an. Da im Transportprotokoll die Transportmittel, die die oben genannten Bedingungen erfüllen, nach Hunderttausenden von Suchanfragen durchsucht werden, kann dies als ** Kombinationsoptimierungsproblem ** formuliert werden.

Formulierung als ganzzahliges Optimierungsproblem

Formulieren Sie die Auswahl des Verkehrsmodus als ein 0-1-Integer-Optimierungsproblem mit Einschränkungen hinsichtlich Fahrzeit und CO2-Emissionen. Die zu minimierenden Zielfunktionen und Einschränkungen sind wie folgt.

Hier ist $ P_ {i, j} $ die CO2-Emission, wenn Benutzer $ i $ den Verkehrsmodus $ j $ auswählt, und $ Q_ {i, j} $ ist der Benutzer $ i $ ist der Verkehrsmodus $ j $. Wenn die Reisezeit ausgewählt ist, ist $ Q \ prime_ {i, j} $ die Reisezeit im Verkehrsmodus, auf die der Benutzer $ i $ geklickt hat (vorausgesetzt, er ist tatsächlich gereist). $ X_ {i, j} $ ist ausgewählt Es ist ein Wert wie ein One-Hot-Vektor, bei dem nur der Verkehrsmodus 1 und die anderen 0 sind. Außerdem gibt $ m $ die Anzahl der Sitzungs-IDs und $ n $ die Anzahl der Verkehrsmodi an. Zum Zeitpunkt der Montage unterscheiden sich die Einheiten hinsichtlich CO2-Emissionen und Fahrzeit, sodass beide normalisiert sind.

Das Tutorial von Professor Umetani von der Universität Osaka war sehr hilfreich für die Formulierung als Optimierungsproblem.

Einführung in die Kombinationsoptimierung: von der linearen Planung zur ganzzahligen Planung https://www.slideshare.net/shunjiumetani/ss-17197023

Wenn es formuliert werden kann, wird es einen vorhandenen Löser verwenden, um es zu lösen. Dieses Mal habe ich eine Bibliothek namens PuLP verwendet.

Ergebnis

Wir haben die Ergebnisse nach der Optimierung mit dem Klickprotokoll des Benutzers als Basis verglichen. Die Ergebnisse sind in der folgenden Tabelle aufgeführt. Optimiert für Suchprotokolle mit ca. 400.000 Abfragen.

Die CO2-Emissionen scheinen um ca. 9,23% reduziert zu sein. Überraschenderweise konnte die Reisezeit um 9,96% reduziert werden. Der Benutzer muss nicht unbedingt auf die schnellste Route klicken.

Als nächstes wollen wir sehen, wie sich die Transportmittel aufgrund der Optimierung geändert haben. In der folgenden Tabelle ist links in Klammern der vom Benutzer angeklickte Verkehrsmodus und rechts der durch Optimierung ausgewählte Verkehrsmodus.

Da sich das veröffentlichte Protokoll im Zentrum von Peking befindet, gab es anscheinend viele Fälle, in denen eine kurze Strecke mit dem Bus oder der U-Bahn zurückgelegt wurde, und es gab anscheinend viele Änderungen, um es in ein Fahrrad umzuwandeln (roter Rahmen in der Tabelle). Auf der anderen Seite ist bei Privatwagen (Fahren) die Anzahl der Fälle, die auf Fahrräder umgestellt wurden, gering, und die meisten davon sind Privatwagen (blauer Rahmen in der Tabelle). Wohin man mit dem Auto reisen kann, ist weit weg und es gibt möglicherweise keine Alternative.

Ich werde nur einen Überblick über die Auswirkungen auf die Gesundheit geben. Eine Studie der Universität Oxford analysierte die Auswirkung des Fahrradfahrens auf die Verringerung der Sterblichkeit (das Papier lautet this). Laut dieser Studie wird die Gesamtmortalität um 10% gesenkt, wenn die von der WHO empfohlene Menge an Bewegung (11,25 METh / Woche körperliche Bewegung, 150 Minuten mäßige Aerobic-Übungen) durchgeführt wird. Aus dieser Simulation können Benutzer berechnen, dass sie durchschnittlich 23,04 Minuten (13,63%, von der WHO empfohlen) pro Tag Fahrrad fahren. Wir waren der Ansicht, dass die Kombination der beiden Faktoren die Gesamtmortalität um 10% mal 13,63% = 1,36 USD senken könnte.

Wie Sie den Ergebnissen von Änderungen im Transportwesen entnehmen können, ist das Ergebnis dieser Studie, dass Fahrräder durch Fahrräder ersetzt werden können. Wenn Sie dies jedoch tatsächlich versuchen, gibt es ein Problem mit dem Fahrradabstellplatz. Die akzeptierte Transportmethode ändert sich je nach Wetterlage (ich möchte nicht mit dem Fahrrad fahren, wenn es regnet) und wie Sie den Benutzer dazu bringen, eine Transportmethode mit geringem CO2-Ausstoß zu wählen Es gibt noch Probleme wie UI / UX bis zur praktischen Anwendung. Obwohl davon ausgegangen wird, dass sich der Benutzer gemäß dem in der Übertragungssuche angeklickten Transportmittel / der angeklickten Route bewegt hat, gibt es eine grundlegende Einschränkung, dass er nicht weiß, wie er sich tatsächlich bewegt hat.

Implementierung

Abschließend möchte ich noch etwas zur Implementierung vorstellen. Für die Implementierung habe ich auf den folgenden Artikel verwiesen. https://qiita.com/samuelladoco/items/703bf78ea66e8369c455 https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

Erstellen Sie im Voraus ein Wörterbuch, das die CO2-Emissionen in c_co2 [i, j] und die Reisezeit (Benutzer i, Verkehrsmodus j) in c_eta [i, j] enthält. Zum Beispiel sieht es so aus. 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 In diesem Beispiel wird angenommen, dass dem Benutzer mit der Benutzer-ID Nr. 2 die Verkehrsmodi 1,3,4,5,6 als Kandidaten präsentiert werden und die Reisezeit in jedem Verkehrsmodus wie oben gezeigt ist.

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

# 0-1 Variable definieren(Einschränkung 3 X._{i,j}Ist 0,Entspricht der Einschränkung, dass 1 2 Werte ist)
# 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)

#Definieren Sie die Zielfunktion. Normalisieren Sie durch Teilen der Reisezeit und der CO2-Emissionen durch den Maximalwert.
# 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"

#Einschränkung 1:Für Benutzer i kann ein Modus zugewiesen werden
# 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)

#Einschränkung 2:Kürzer als die Reisezeit des vom Benutzer angeklickten Verkehrsmodus i
# click_log_Das Klickprotokoll ist in df als Pandas-Datenrahmen enthalten
# 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) 

#Geben Sie einen Löser an
# set solver
solver = pulp.solvers.PULP_CBC_CMD()
result = problem.solve(solver)
#Gibt aus, ob eine Optimierung möglich war oder nicht, und den Bewertungswert zu diesem Zeitpunkt
# output
print(pulp.LpStatus[result], pulp.value(problem.objective))

Zeitleiste

Die Ausgabe des regulären ML Track des KDD Cup 2019 wurde um den 13. April veröffentlicht. Danach reichte ich das Papier gemäß dem folgenden Zeitplan ein.

4/19 Erstes Treffen (Entwurf der Datennutzungsmethode) 5/8 Meeting Nr. 2 (Entwurf der Datennutzungsmethode und Festlegung der Richtlinien) 5/15 Meeting # 3 (Implementierte ein Optimierungsprogramm, die Optimierung konvergierte zu diesem Zeitpunkt nicht) 5/31 Meeting # 4 (Implementierung der Optimierung abgeschlossen) 6 / 3-10 Schreiben einer Arbeit (4 Seiten in Englisch) 6 / 11-12 Englische Kalibrierung 6/13 Post 6/15 Einreichungsfrist (die Frist wird zu einem späteren Zeitpunkt bis Ende Juni verlängert)

Im Jahr 2019 gab es während der Goldenen Woche 10 aufeinanderfolgende Feiertage, und in ungefähr anderthalb Monaten haben wir uns für Forschungsthemen entschieden, diese umgesetzt und Artikel geschrieben.

Schließlich

Ich war selbst nicht mit Optimierungsproblemen vertraut, aber ein Kollege, mit dem ich zusammengearbeitet habe, erzählte mir ausführlich über die Formulierung, die Pulp-Implementierung und was zu tun ist, wenn die Optimierung nicht funktioniert. Darüber hinaus schlägt ein anderes Mitglied vor, es auf Umweltprobleme anzuwenden, und wenn jeder Verkehrsmodus nur durch eine ID bereitgestellt wird, welche ID welcher Verkehrsmodus ist, der im Web von Tarif und Daten veröffentlicht wird Es ist eine Untersuchung, die jedes Teammitglied bei der Betrachtung von Statistiken zur Identifizierung beigetragen hat. Ich möchte weiterhin interessante Forschungsarbeiten durchführen und das Bewusstsein für die Datenanalyse- und KI-Bereiche von DoCoMo durch externe Aktivitäten wie Präsentationen auf Konferenzen schärfen, und ich möchte weiterhin Top-Konferenzen wie KDD herausfordern.

Dann alle zusammen, Frohe Weihnachten und ein gutes neues Jahr!

[^ 1]: Gewann den weltweit ersten Platz beim weltweit höchsten Datenanalyse-Wettbewerb "KDD CUP 2019" https://www.nttdocomo.co.jp/binary/pdf/info/news_release/topics_190809_01.pdf