機械学習でGoogle map apiのように地点間移動時間を推論する

# Google map APIが高いから使いたくない！
google map apiって正直、高くないですか？1000requestで500円ぐらいなので0.5円/request。自作のサービスとかに使おうと思ったら、一瞬で10万円とかすぐに飛んじゃいます。
特に私は旅行の日程を立てるサービスを作ったり、移動時間を特徴量とした都市の地価予測などをしたことがありますが、１回の検索のために１００個ぐらいの移動時間を計算させなければならないため、すぐに破産しそうになりました。:angel_tone2:

そこで、今回は地点間の移動時間を推論する機械学習を作成した結果について話そうと思います。
対象としては車を使った移動に限定をして問題をときます。

# 機械学習による学習・推論
機械学習を使って地点間の移動時間を推論する仕組みは大して難しくはありません。
機械学習では入力の変数と出力の変数の関係を表す「モデル」を構築して推論に用います。「入力が○なら出力は×ね」という感じのことを学習させるわけです。
入力に使う変数は「説明変数」と呼ばれ、推論する出力の変数は「目的変数」と呼ばれます。

今回は車を使った移動時間を推論させたいので、説明変数として
- 出発地の緯度・経度
- 到着地の緯度・経度
- 出発時刻
- 曜日
- 高速道路の利用有無
を利用し、目的変数として、
- 移動時間（秒）
を使います。

また、特徴量として直線距離に相当する量を出発地と到着地の緯度経度の差分から作成して利用します。

## 学習用データの準備
機械学習モデルを作成するためにはデータが必要です。データはモデルを作るための学習用データと、作ったモデルの評価をするためのテストデータを用意しなければなりません。
単純にはGoogle map APIを何度も叩いて学習用データを貯めることが考えられますが、残念ながらGoogle map APIは規約によって結果を「保存」して利用することが禁止されています(違反すると何があるかはわかってないです）。

そこで、今回は独自のルートを用いて上記の説明変数と目的変数の揃ったデータを入手いたしました。

皆さんが同様のことをしたいと思った場合には、各API提供業者に個別で問い合わせをしてデータを売ってもらえないかを打診することになるかと思います。頑張ってみてください。

今回は旅行日程の計画などに使っていたコードがベースなので、だいぶ広い範囲から45129データを下記の範囲で収集しました。
- 緯度：35.50〜36.50
- 経度：137.50〜139.50
これはだいたい、岐阜、長野、埼玉、東京、山梨あたりの一部がそれぞれカバーされてるぐらいの範囲です。
この範囲からランダムに２点を選択し、説明変数にある条件をランダムに振りながら移動時間を収集しました。


## 解く
収集した45129データのうち、８割に相当する36103データを学習データに、残りを評価用のデータに用いて実際に解いてみます。機械学習はLightGBMと呼ばれる機械学習モデルがpythonのライブラリとして提供されているので、コレを利用します。機械学習のコンペティションであるKaggleなどでも最もよく利用されるモデルで手軽で非常に高い精度が他の機械学習モデルと比べて簡単に出せます。

```python:学習推論.py
# import libraries
import matplotlib.pyplot as plt
from lightgbm import LGBMRegressor 
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_absolute_error
import japanize_matplotlib

# load data from csv
df = pd.read_csv("map.csv")
# specify columns
x_columns = ["st_lat_pos", "st_lng_pos", "ed_lat_pos", "ed_lng_pos", "distance", "avoidance","day", "hour"]
# make training data, and test data
trainx, trainy = df.loc[:TX_N, x_columns], df.loc[:TX_N, "target"]
testx, testy = df.loc[TX_N:, x_columns], df.loc[TX_N:, "target"]
# making ML model
m = LGBMRegressor(n_estimators=3000, min_child_samples=20, importance_type="gain")
m.fit(trainx, trainy)

# show result
plt.title("平均絶対値誤差：{}".format(mean_absolute_error(testy, m.predict(testx)), mean(testy-m.predict(testx))))
plt.plot(trainy, m.predict(trainx), "b.", label="学習")
plt.plot(testy, m.predict(testx), "r.", label="テスト")
plt.plot([250, 40000], [250, 40000])
plt.xlabel("真値")
plt.ylabel("LightGBMの予測値")
plt.legend()
plt.show()
```

## 結果
結果は下記のようになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1140638/3a75f754-c1ea-2b26-a62f-a1f749174274.png)
グラフの見方は横軸が真値で縦軸が推論値となっており、推論がうまく言っていれば真値と推論値が同じ値になるため、傾き1の直線に近くなります。
平均絶対値誤差で558秒なので、長距離移動としてはよほどのことがない限り、利用には問題が無いように思われます。

この時、LightGBMがどの説明変数に大きく影響を受けていたかの特徴量重要度を可視化できます。その結果がこちらとなります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1140638/470cf1d2-b462-ff50-b481-3dbad1f75078.png)
まあ、擬似的な直線距離と、高速道路の利用有無の２つが一番きいていますね。当たり前な気もします。時刻が意外と聞いていないのは不思議です。

では次に、実際の移動をシミュレーションさせてみましょう。
まずは山梨の秘宝「富士山」から東京のシンボル「東京タワー」までの移動時間を出してみます。
移動は旅行をイメージして朝9時出発とします。

```python:推論.py
data = pd.DataFrame([{"day":1, "hour":9, "st_lat_pos":35.36, "st_lng_pos":138.726, "ed_lat_pos":35.658, "ed_lng_pos":139.746,}])
data["distance"] = np.sqrt(np.square(data["st_lat_pos"]-data["ed_lat_pos"]) + np.square(data["st_lng_pos"]-data["ed_lng_pos"]))
data["avoidance"] = 0
result = m.predict(data)
print("移動時間：{}時間{}分".format(int(result//3600), int(result%60)))
```
結果：
```移動時間：2時間29分
```
だいぶ移動かかりますね。この結果をgoogle map上で実際に移動時間を求めてみたいと思います
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1140638/3d1b75b7-9a4b-3ee5-ea09-f762a8feecc3.png)

２時間31分！
ほぼ合っていますね。
利用には問題なさそうです。


# まとめ
google map apiのように２点間の移動時間を出す機械学習モデルを作ることができました。複数回の呼び出しを必要とするケースなどでは利用が検討されるところになります。
データの収集方法がネックとなりますが、規約を破ってgoogleの法務部と戦う強い胆力があれば大丈夫でしょう（嘘です）。

一方、最近はOpenStreetMapなどを利用して、実際の道に沿った移動時間を計算できるソフトウェアやライブラリも登場しております。これらは使い分けをすると良いかと思われます。メリデメは下記のとおりです。

- LightGBMは移動の出発時間に応じた推論ができるが、OpenStreetMap由来はできない
- OpenStreetMap由来なら学習データを個別で用意する必要がない
- OpenStreetMap由来なら実際にどこの走るかのルートも出せる
- LightGBMのほうが動作速度的には経路最適問題を解かない分、圧倒的に早い

みんなもたくさん旅行日程を考えていきましょう。