野村総合研究所データサイエンティストによる
情報発信サイト

航空経路(ウェイポイント)の推定 ~SIGNATEコンペ~

はじめに ~分析の組み立てメインです~

みなさま初めまして。NRIの小川と申します。

先日、データ分析コンペサイトSIGNATEにて開催された「テクノプロ・デザイン社 飛行機の航空経路の推定チャレンジ」(https://signate.jp/competitions/721)に参加し、一般の部1位という結果をいただきました。

データサイエンスに出会ってから5年と、それほど長くはないのですが、はじめてコンペで素敵な賞をいただき、非常にうれしかったです。

 

このコンペで行った解法をブログ記事に書いていきますが、実は私の解法はそこまで技術レベルが高い部分はありません。

技術的には簡単な推定方法を、思いつく限り試してみて、組合わせた結果です。

そんなわけで、技術的な解説というより、どのように個々の分析を組み立てていったかをメインに、書いていこうと思います。

難しいことは書きません(書けません)ので、お気軽に読んでいただければ、ありがたいです。

 

 

コンペ課題 ~これはデータ分析コンペなの?~

まずはコンペ課題の説明から。

飛行機が運航する際の通過すべき地点の座標となるウェイポイントという目印が、海上を含む日本各地に約2,000箇所あります。

このウェイポイントは年々変わっており、「2017年時点のウェイポイントがどこにあったか?」を推定するのがコンペ課題。

評価基準は、「より近く正解位置の近くを推定したスコア」+「審査発表会での解法」による、総合評価でした。

 

提供されたデータとしては、以下のようなデータとなります。

  • 2017年時点の航跡データ     :時刻便名、緯度、経度、高度、型式
  • 2017年時点のウェイポイント一覧 :名称のみ
  • 2022年時点のウェイポイント一覧 :名称、緯度、経度

 

・・・お気づきでしょうか?

問題の2017年時点のウェイポイントの名称と緯度経度を紐づけられるデータが存在しないのです。

航跡からウェイポイントがありそうな位置は特定できそうですが、そこのウェイポイント名称が分かる情報が無い。

幸いウェイポイントの一部には、「ATAMI」=熱海、のような地名そのものの場合や、「RINGO」=リンゴ⇒青森、のように想像は出来るものはありますが、ほとんどは位置が分からないもの。

 

つまり、『解き方が分からない!!』。

 

コンペ参加者フォーラム上でも序盤から「どうやって解けばいいの?」「そもそもこれはデータ分析コンペなの?」と参加者の困惑の声が吹き荒れました。

私も悩みつつも、現実世界の問題は解き方が想像できるデータ分析の方が少ない気がしますから、こんな課題があってもいいかも?と思いながら取り組みました。

 

 

私の解法 ~手数と組み立てで勝負!~

さんざん悩んだ結果、たどり着いた解法が以下のような組み立てです。

つまり、

『ウェイポイントの名前から正確な位置は分からなくても、
おおまかな位置は推測できる』

し、それとは別に、

『航跡を見れば、名前は分からないけど、
ウェイポイントがありそうな正確な位置は推測できる』

のなら、別々に推定して、あとで組合せを考えよう、という組み立てです。

 

また、Step1の推定は、ともかく、思いつく限り多くの色々な推定法を試してみました。

 

ここから、Step毎に説明していきます。

 

Step1-1 フライトプランによる位置の推定

ウェイポイント名称からの位置推定は3種類の方法を組合わせました。

その中で、最も効果的だったのは、フライトプランからの位置推定です。

 

フライトプランは、「フライトプランデータベース」(https://flightplandatabase.com/)というサイトをスクレイピングして収集した外部データで、「どの空港から出発して、どのウェイポイントを通って、どの空港に着陸したか」というデータです。

今回の課題で知りたい位置不明なウェイポイントを通っているフライトプランを見つけ出し、そのウェイポイントを挟んでいる、空港、または位置が判明しているウェイポイントの位置が分かれば、その中心近くににあるものと推定します。

当然、同じウェイポイントが色々なフライトプランに登場するので、どれを使うかというところが、悩みどころ。

短い距離で挟まれている方が、大外しはしないのですが、多くのデータを使って中心地点を選んだ方が、正確な位置が推定できる場合もあります。

何パターンか試して精度変化を見た結果、同じウェイポイント挟んでいるフライトプランの中で、最短のものを選び、それと距離が近いフライトプランのみ、具体的には最短の1.4倍以内の距離までを含めて推定した結果が、最も精度が高くなりました。

 

実はこのフライトプランを使った推定方法はコンペ後半から取り入れた方法だったのですが、スコア的には導入前の20位近辺から1位にまで押し上げてくれるくらい、精度効果はチート級。

有効なデータを入手することって、やっぱり大事なんですね。

 

 

Step1-2 ご当地情報から位置の推定

2つ目の位置推定方法は、ウェイポイント名称と似たような地名や特産品などのご当地情報を探して紐づける方法。

多くの参加者が取り組まれいた方法ですが、技術的にはwikipediaで意味解釈をしたり、単語のベクトル変換されていたり、と様々で、他の方の審査発表を聞いていて非常に勉強になりました。

 

私が実施したのは、地名や特産品、有名企業などのご当地情報を集めて、ご当地情報の略称データベース作成し、ウェイポイント名称と一致するものを探索する、という方法です。

 

これをすると、ひとつのウェイポイント名称に対し、複数のご当地情報にマッチします。(例:「MIHARA」→東京伊豆大島の三原山と広島県三原市など)

このマッチング結果から、どれを採用するのを当初は人手で決めていましたが、最終的にはウェイポイント名称とご当地情報が一致している確率を予測する機械学習モデルを作成して、モデルの予測結果が最も高いご当地情報を採用することにしました。

特徴量としては、判定した元データの種類(市区町村名/字名/山/島)の他、山の標高や島の大きさ、企業の評価額など、そのご当地情報の認知度の高さにつながりそうな情報です。

技術的には、お手軽モデルの代名詞LightGBMによる非常に簡単な手法ではありますが、最初に人手で判断していたより精度も良くなりました。

また、モデル化したことで、

  • 「こっちの方が似てそう」みたいな人の感覚に依存した曖昧さを排除できた
  • 例えば、「2010年時点のウェイポイント位置は?」などの類題に対しても、
    再現性のある手法となった

という副次効果もあり、スコアとは別に、解法としても評価いただけた部分でした。

 

Step1-3 ウェイポイント名称の文字列から位置の推定

3つ目の位置推定方法は、ウェイポイント名称のアルファベットを2文字ずつの文字列に切って、同じ文字列があるウェイポイントの中心に配置する、という方法。

つまり、「似たような文字を使っているウェイポイントは近くにあるんじゃない?」という発想です。

 

…本当か?と思われると思います。

私もそれほど確信をもってはいません。

この部分は、正直、どうしても分からないウェイポイント全部を平均値補完するのが、諦めたみたいで嫌だったために捻りだした、言ってしまえば『悪あがき』です。

とりあえず、試してみたらスコアが少し上がりましたので、まあいいかと。

実際のデータ分析業務でも、「全く分かりません」ではなく、無理矢理にでも仮説を出してみる方が良い場面もありますからね。

そんな言い訳をしつつ、次に行きます。

 

Step1-4 各推定結果のマージ

ここまでのStep1-1~3から出た推定結果は、信頼性が大きく異なります。

Step1-3:文字パターン は言うまでもなく信頼性は低いですし、Step1-1:フライトプランと1-2:ご当地情報を比較するならStep1-1の方が大外しはしません。

ですので、Step1-1:フライトプランで分からなかったウェイポイントはStep1-2:ご当地情報の推定結果を採用、それでも分からない場合のみStep1-3:文字パターンを適用しました。

 

Step2 航跡よりウェイポイント候補地を選定

ここからは、話が変わって、航跡データからウェイポイントがあると想定される位置を特定する、というプロセス。

発想としては、飛行機が航跡を繋ぐように飛んでいるということは、逆に言えば『航跡が方向転換している位置にウェイポイントがあるはず』という仮説を立てました。

ただ、航跡データの記録には、計測機器の都合か、緯度経度の位置がずれてしまうことがあるようで、明らかに異常な航跡は、前処理で除外します。

また、そうしてクリーニングして見えた方向転換位置は航跡ごとに微妙にずれるので、近いものを集約する必要もあります。

 

大量の航跡データから、これらのジオメトリ処理をするにはpythonのライブラリですと、かなりの処理時間がかかるところ。

私の場合、ここでPostGISが大きく活躍しました。

PostGISはPostgreSQLベースでGIS処理をできるソフトで、大量データを処理するのに便利。

また、SQLベースなので、システムエンジニアの方には非常に相性が良い技術だと思います。

 

審査発表会で見れた範囲では、他の方はこの航跡データはあまり使われていなかった様で、GISデータを活用した私の解法は高い評価をいただけました。

 

Step3 ウェイポイント位置と候補地のマッチング

最後は、Step1で推定したウェイポイントをStep2で推定したウェイポイント候補地をマッチングして位置を補正。

マッチングはシンプルに一番近くの推定ウェイポイントと候補地同士を紐づけました。

シンプルではあるものの、この補正により、スコアもしっかり上がりましたので、GISデータを活用した効果はしっかりとあったようです。



 

 

長くなりましたが、以上が私の解法です。

 

最終的に評価いただけた点は以下の3点。

  • 航跡データを活用していること
  • 再現性が高いアプローチであること
  • 審査発表会での説明に一貫したストーリー性があったこと

 

いずれも、自身でも重視して取り込んだポイントでしたので、非常にうれしい評価でした。

 

 

コンペ感想 ~運も実力のうち~

コンペ後半で暫定スコア1位になりましたが、終盤になると、他の参加者の皆様もスコアをグングン上げてきました。

私もデータの追加収集やパラメータ調整して、ギリギリまで改善。

特に締め切り直前には、相手のスコアも気にしながら、日付変更近くまで修正したものを投稿したりして、何となくスポーツの試合終了直前の攻防の様な高揚感で、一人盛り上がっていました。

最後までやり切ってスコア1位になれたことは審査発表に向けて大きな自信となりました。

 

その自信を受けて、最終審査発表では解法と発表内容も評価をいただけたようで、最終審査でもそのまま1位となり、コンペを終えることができました。

発表の様子はYouTubeでも公開されていますので、よろしけばそちらもご覧いただければ。

https://www.youtube.com/watch?v=zoyhOUsj9FI (29分あたりから)

 

振り返ってみて、強いて勝因を上げるなら、

  • データ分析技術よりも、解法の組み立てが問われた課題だった
  • 私が比較的得意としている、GISデータを取り扱う課題だった
  • スコアに直結する外部データ(フライトプラン)を見つけることができた

と、課題との相性と幸運に支えられた部分は大きかったのかな、とは思いますね。

 

まあ、そんなラッキーも滅多に起こらないとは思いますが、非常に楽しい経験でしたので、今後もこうしたデータ分析コンペに取り組んでいければと思います。

最後まで読んでいただき、ありがとうございました。

 

 

※画像の一部に、本コンペで提供された航跡データ“国土交通省CARATS Open Data”を利用しています。