この記事は
- 営業の人とかがよく営業先のアタックリストを作って回ったりすると思います
- １日あたりに回れる件数には限度がありますから、複数人とか複数日に渡る営業活動を網羅的かつ効率的に巡回できるように分割したいところです
- これを機械学習を使ってやってみたので備忘です
やりたいこと
対象データ
- 例えば東京の江戸川区のコンビニ一覧があるとします
- こちらに東京のコンビニ一覧が公開されていますので、ここから江戸川区部分だけを抜き出してデータを作ります
- 全部で211件あるようです
- このあたりの地図にマーカを立てるサービスを使って図示すると下記のような感じになります
要件
- このピンを20の固まりに分割します
- 各固まりに含まれるピンの数は同じ数とします（211 / 20なので、10本か11本のピンが含まれるようにします)
- さらにその固まりどうしについて、隣接している順序で巡回できるようにします
つまり、こんな感じにしたいです。
マーカの色・形で固まりが表現されていて、また下の凡例の順序通りにたどると隣接した固まりを辿れるようになっています。
方針
固まりを作る
- 固まりを作るにあたり、k-meansクラスタリングを使います
- ただし、通常のk-meansの場合クラスタあたりに含まれるマーカの数は不定になってしまいます
- なので、件数が揃うようにチューニングされたk-meansクラスタリングのアルゴリズムを利用する必要があります
- ちなみにこちらに件数が揃ったk-meansのアルゴリズムの解説があります
固まり同士を隣接させる
- 固まりを隣接させるにあたっては、TSP(セールスマン巡回問題)のソルバを利用します
- 固まりの中央地点(centroid)どうしを巡回点とみなしたセールスマン巡回問題を解けば、うまくやりたいことができます
コード
まずはコード
- こんな感じです
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を利用します
- インストールは適当にやってください。
- 今回はこのあたりのdocker imageを使いました
クラスタリング
- クラスタリングにはSame-Size-K-Meansというコードを利用します
- pip化されていないので、適宜コードをコピペして利用します
- このコードを配置して適当にimportしました
- コード的には下記のとおりscikit-learnのAPIで普通に実行可能です
kmeans = EqualGroupsKMeans(n_clusters=20, random_state=10)
kmeans.fit(latlngs)
TSP
- TSPのソルバとしてtsp-solverを使います
- これは普通にpip化されているので
pip install tsp_solver2とかやれば利用できます - コードとしては下記
# クラスタの中心座標を巡回セールス問題にあてはめてぐるっと回るように順序を決定
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に渡すと結果が得られる
⬇︎距離マトリックスのイメージ
- ちなみに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
- 再掲ですが、こんな感じに分割できました
終わりに
- 技術を使って営業活動を捗らせるってソフトウェアで世界を飲み込んでる感あってなんかいいですね！