緯度・経度情報から営業アタックリストの順序を最適化する

この記事は
===

* 営業の人とかがよく営業先のアタックリストを作って回ったりすると思います
* １日あたりに回れる件数には限度がありますから、複数人とか複数日に渡る営業活動を網羅的かつ効率的に巡回できるように分割したいところです
* これを機械学習を使ってやってみたので備忘です

やりたいこと
===

対象データ
---

* 例えば東京の江戸川区のコンビニ一覧があるとします
    * [こちら](http://www.sinfonica.or.jp/kanko/estrela/refer/s29/index.html)に東京のコンビニ一覧が公開されていますので、ここから江戸川区部分だけを抜き出してデータを作ります
    * 全部で211件あるようです
* [このあたり](http://ktgis.net/gcode/lonlatmapping.html)の地図にマーカを立てるサービスを使って図示すると下記のような感じになります

![スクリーンショット 2019-01-21 10.47.01.png](https://qiita-image-store.s3.amazonaws.com/0/27361/69ed1bd2-2fa3-b557-c7ee-5d4e1af86c7b.png)

要件
---

* このピンを20の固まりに分割します
* 各固まりに含まれるピンの数は同じ数とします（211 / 20なので、10本か11本のピンが含まれるようにします)
* さらにその固まりどうしについて、隣接している順序で巡回できるようにします

つまり、こんな感じにしたいです。

![スクリーンショット 2019-01-21 10.54.12.png](https://qiita-image-store.s3.amazonaws.com/0/27361/9e928128-73e7-9c3d-2c2d-51e4a981fa05.png)

マーカの色・形で固まりが表現されていて、また下の凡例の順序通りにたどると隣接した固まりを辿れるようになっています。

方針
===

固まりを作る
---

* 固まりを作るにあたり、k-meansクラスタリングを使います
* ただし、通常のk-meansの場合クラスタあたりに含まれるマーカの数は不定になってしまいます
* なので、件数が揃うようにチューニングされたk-meansクラスタリングのアルゴリズムを利用する必要があります
* ちなみに[こちら](https://elki-project.github.io/tutorial/same-size_k_means)に件数が揃ったk-meansのアルゴリズムの解説があります

固まり同士を隣接させる
---

* 固まりを隣接させるにあたっては、TSP(セールスマン巡回問題)のソルバを利用します
* 固まりの中央地点(centroid)どうしを巡回点とみなしたセールスマン巡回問題を解けば、うまくやりたいことができます

コード
===

まずはコード
---

* こんな感じです

```python:same_size.py
import numpy as np
from sklearn.cluster import KMeans
from equal_groups import EqualGroupsKMeans
from tsp_solver.greedy import solve_tsp
from scipy.spatial import distance

# tsvファイルから緯度・経度を読み込み
latlngs = np.loadtxt('geos/edogawa_geos.tsv', delimiter='\t', dtype='float')

# 同一サイズ対応のk-meansクラスタリングを実施
kmeans = EqualGroupsKMeans(n_clusters=20, random_state=10)
kmeans.fit(latlngs)

# クラスタの中心座標を巡回セールス問題にあてはめてぐるっと回るように順序を決定
centroids = kmeans.cluster_centers_
# 巡回セールスマン問題の入力となる距離マトリックスを生成する
distance_mtx = distance.cdist(centroids, centroids, metric='euclidean')
path = solve_tsp(distance_mtx)

# 結果を適当TSVで出力
index = 1
labels = kmeans.labels_
for label, latlng in zip(labels, latlngs):
  print(str(index) + "\t" + str(latlng[0]) + "\t" + str(latlng[1]) + "\t" + str(path.index(label)))
  index += 1
```

利用技術
---

* python/numpy/scikit-learn/scipyを利用します
* インストールは適当にやってください。
* 今回は[このあたり](https://hub.docker.com/r/davidshen84/scikit-learn/)のdocker imageを使いました

クラスタリング
---

* クラスタリングには[Same-Size-K-Means](https://github.com/ndanielsen/Same-Size-K-Means)というコードを利用します
* pip化されていないので、適宜コードをコピペして利用します
    * [このコード](https://github.com/ndanielsen/Same-Size-K-Means/blob/master/clustering/equal_groups.py)を配置して適当にimportしました
* コード的には下記のとおりscikit-learnのAPIで普通に実行可能です

```python
kmeans = EqualGroupsKMeans(n_clusters=20, random_state=10)
kmeans.fit(latlngs)
```

TSP
---

* TSPのソルバとして[tsp-solver](https://github.com/dmishin/tsp-solver)を使います
* これは普通にpip化されているので```pip install tsp_solver2```とかやれば利用できます
* コードとしては下記

```python
# クラスタの中心座標を巡回セールス問題にあてはめてぐるっと回るように順序を決定
centroids = kmeans.cluster_centers_
# 巡回セールスマン問題の入力となる距離マトリックスを生成する
distance_mtx = distance.cdist(centroids, centroids, metric='euclidean')
path = solve_tsp(distance_mtx)
```

* やってることは下記です
    * クラスタの中心地点であるcentroidを取得
    * centroid同士の距離マトリックスを生成
        * これはcentroid x centroidの二次元表で、各centroid間の距離が格納されている
    * 距離マトリックスを```solve_tsp```に渡すと結果が得られる

⬇︎距離マトリックスのイメージ
![](https://github.com/dmishin/tsp-solver/blob/master/images/tsp-nodes.jpg?raw=true)

* ちなみにKMeansもTSPも、今回ユークリッド距離を使っていて、緯度経度だと地球が丸いことを考慮していないので不正確なんですが、今回くらいの狭い地域では問題ない精度がでていました

結果
===

* 数十秒くらい待つと下記の結果TSVが出力されます
    * 一番左の番号がマーカ番号(入力TSVの順序通り)で、一番右の列がクラスタ番号です
    * このクラスタ番号順にたどると隣接クラスタにつながるようになっています
    * Excelにはりつけてクラスタ番号順にソートをかければ最適なアタックリストの出来上がりです

```
# python same_size.py 
1	35.68598	139.8847	11
2	35.69014	139.87862	2
3	35.68634	139.87711	11
4	35.68679	139.88246	11
5	35.6835	139.87602	11
6	35.6852	139.88036	11
7	35.68668	139.88344	11
8	35.7217	139.87546	16
9	35.68671	139.90254	13
10	35.68419	139.89027	11
11	35.67305	139.883	11
12	35.67511	139.87158	10
13	35.7072	139.88937	15
14	35.70854	139.88989	15
15	35.7085	139.89484	15
16	35.71397	139.88843	15
17	35.71771	139.88431	15
18	35.70953	139.90437	14
19	35.7081	139.90387	14
20	35.70532	139.90741	14
21	35.70613	139.90475	14
22	35.70281	139.91396	13
23	35.69858	139.91153	13
24	35.70173	139.90819	13
25	35.70094	139.90848	13
26	35.70118	139.90399	14
27	35.70338	139.90176	14
28	35.70701	139.90213	14
29	35.70419	139.90468	14
30	35.70649	139.9032	14
31	35.70649	139.9032	14
32	35.69313	139.89015	12
33	35.69679	139.88792	12
34	35.67907	139.873	10
35	35.69007	139.84917	3
36	35.70175	139.86827	1
37	35.70217	139.873	2
38	35.70268	139.87474	2
39	35.69735	139.87238	2
40	35.69444	139.86855	2
41	35.69109	139.86824	3
42	35.68603	139.87114	3
43	35.70491	139.86725	1
44	35.70991	139.86304	1
45	35.71191	139.86371	1
46	35.71201	139.85947	1
47	35.71678	139.87509	16
48	35.72377	139.87047	16
49	35.7091	139.90268	14
50	35.70431	139.88922	15
51	35.69845	139.89299	12
52	35.69585	139.89806	12
53	35.69397	139.89777	12
54	35.69357	139.89661	12
55	35.69704	139.89388	12
56	35.69786	139.88126	2
57	35.69786	139.88126	2
58	35.69585	139.87611	2
59	35.69544	139.87279	2
60	35.66699	139.85379	4
61	35.6651	139.85831	5
62	35.66597	139.85558	5
63	35.66483	139.86189	5
64	35.66616	139.85956	5
65	35.66616	139.85956	5
66	35.66531	139.86128	5
67	35.66496	139.85936	5
68	35.66354	139.85915	5
69	35.66418	139.86057	5
70	35.66407	139.8622	6
71	35.66396	139.86353	6
72	35.6626	139.86061	6
73	35.6647	139.85826	5
74	35.66369	139.85788	5
75	35.65901	139.86063	6
76	35.66194	139.8593	6
77	35.71379	139.89351	15
78	35.73176	139.87892	17
79	35.73176	139.87892	18
80	35.73255	139.87897	18
81	35.73388	139.87935	18
82	35.73419	139.88023	18
83	35.73515	139.88428	19
84	35.73477	139.88249	18
85	35.735	139.87985	18
86	35.73481	139.87492	18
87	35.73907	139.87814	18
88	35.73556	139.88078	18
89	35.74152	139.88068	19
90	35.69256	139.89613	12
91	35.68702	139.89044	12
92	35.685	139.88976	11
93	35.68939	139.8927	12
94	35.67861	139.87994	11
95	35.67956	139.88034	11
96	35.68562	139.86121	3
97	35.686	139.86398	3
98	35.68377	139.86333	3
99	35.6825	139.86218	4
100	35.68166	139.86295	4
101	35.68237	139.86485	3
102	35.68381	139.86429	3
103	35.68189	139.86551	3
104	35.68519	139.86479	3
105	35.68559	139.86516	3
106	35.67797	139.86935	10
107	35.70767	139.88055	16
108	35.70734	139.87956	16
109	35.70202	139.90117	13
110	35.70385	139.86835	1
111	35.70592	139.86928	1
112	35.70819	139.8734	16
113	35.70359	139.87476	2
114	35.7114	139.87061	16
115	35.71138	139.87456	16
116	35.71246	139.86661	1
117	35.70898	139.8676	1
118	35.67208	139.86795	10
119	35.6692	139.86685	10
120	35.67356	139.87138	10
121	35.67107	139.86885	10
122	35.66436	139.868	9
123	35.66594	139.87263	9
124	35.6642	139.87131	9
125	35.66522	139.87265	9
126	35.66522	139.87265	9
127	35.66649	139.86852	10
128	35.66546	139.86563	9
129	35.66299	139.87192	9
130	35.66186	139.86646	9
131	35.65934	139.86444	6
132	35.65919	139.86713	6
133	35.66029	139.87022	9
134	35.65603	139.86418	6
135	35.65946	139.87143	9
136	35.65613	139.86925	7
137	35.65537	139.86922	7
138	35.67176	139.87614	10
139	35.66752	139.87656	8
140	35.67001	139.87509	10
141	35.66293	139.88235	8
142	35.66394	139.87448	8
143	35.66344	139.87862	8
144	35.66597	139.88145	8
145	35.66166	139.87592	8
146	35.66252	139.87354	9
147	35.66237	139.87724	8
148	35.65889	139.87389	8
149	35.65952	139.87508	8
150	35.65977	139.87331	8
151	35.65812	139.8817	8
152	35.72024	139.89117	15
153	35.7309	139.8903	19
154	35.73344	139.88892	19
155	35.69658	139.867	2
156	35.71808	139.88721	15
157	35.69129	139.89967	12
158	35.65392	139.87198	7
159	35.65394	139.87689	7
160	35.64932	139.86876	7
161	35.65152	139.87274	7
162	35.65151	139.87529	7
163	35.6473	139.87915	7
164	35.64436	139.8768	7
165	35.64756	139.87624	7
166	35.69545	139.90981	13
167	35.69391	139.90134	13
168	35.69318	139.90228	13
169	35.69726	139.90039	13
170	35.69122	139.90717	13
171	35.72294	139.88159	16
172	35.72554	139.88249	17
173	35.72296	139.88112	16
174	35.72998	139.88129	17
175	35.73107	139.8812	17
176	35.72778	139.88231	17
177	35.73132	139.88318	17
178	35.73273	139.8812	18
179	35.72804	139.88634	17
180	35.73367	139.88374	18
181	35.73272	139.88301	17
182	35.73085	139.88412	17
183	35.70084	139.84967	1
184	35.70271	139.84694	0
185	35.70441	139.84206	0
186	35.70456	139.84332	0
187	35.70516	139.84329	0
188	35.70617	139.84381	0
189	35.70728	139.84274	0
190	35.70883	139.84358	0
191	35.70796	139.84103	0
192	35.70988	139.84331	0
193	35.71434	139.84244	0
194	35.71403	139.83871	0
195	35.67814	139.85477	4
196	35.67293	139.85727	4
197	35.67463	139.85857	4
198	35.67445	139.85931	4
199	35.67195	139.86607	4
200	35.73703	139.88618	19
201	35.74097	139.8831	19
202	35.74062	139.89668	19
203	35.74335	139.88461	19
204	35.74274	139.8847	19
205	35.74414	139.89015	19
206	35.74941	139.88147	19
207	35.7163	139.86829	16
208	35.65245	139.85886	6
209	35.65174	139.86284	6
210	35.64728	139.86099	6
211	35.64502	139.87	7
```

* 再掲ですが、こんな感じに分割できました

![スクリーンショット 2019-01-21 10.54.12.png](https://qiita-image-store.s3.amazonaws.com/0/27361/9e928128-73e7-9c3d-2c2d-51e4a981fa05.png)

終わりに
===

* 技術を使って営業活動を捗らせるってソフトウェアで世界を飲み込んでる感あってなんかいいですね！