Python
地図
組合せ最適化


これなに

日本地図を県別に色分けする Python3.5 用のライブラリ(japanmap)を作成したので紹介します。

実行例は、Jupyter notebook 上で確認しています。


インストール

pipでできます。numpy1が必要です。


bash

pip install japanmap



県コードとは

都道府県コード(以下、県コードと略す)は、JIS X 0401 により定められた、各都道府県ごとの01から47のコードです。

プログラムでは整数で扱いますので、頭の0は無視します。


県名確認

pref_namesで県コードごとの県名がわかります。


python3

from japanmap import *

pref_names[1]
>>>
'北海道'

pref_codeで県名に対する県コードがわかります。


python3

pref_code('京都'), pref_code('京都府')

>>>
(26, 26)

groupsで八地方区分ごとの県コードがわかります。


python3

groups['関東']

>>>
[8, 9, 10, 11, 12, 13, 14]


白地図

pictureで白地図(ラスタデータ)を取得できます。


python3

# 実行には、OpenCV, pillow, matplotlib が必要です。

%matplotlib inline
import matplotlib.pyplot as plt
plt.imshow(picture());

image

県を色で塗ることもできます。


python3

plt.imshow(picture({'北海道': 'blue'}));


image


隣接情報

is_faced2sea で県コードに対して、庁所在地を含むエリアが海に面しているかわかります。


python3

for i in [11, 26]:

print(pref_names[i], is_faced2sea(i))
>>>
埼玉県 False
京都府 True

is_sandwiched2sea で県コードに対して、庁所在地を含むエリアが海に挟まれているかわかります。(連続でない海辺が2つ以上あるか)


python3

for i in [2, 28]:

print(pref_names[i], is_sandwiched2sea(i))
>>>
青森県 False
兵庫県 True

adjacent で県コードに対して、庁所在地を含むエリアが隣接する県コードがわかります。


python3

for i in [2, 20]:

print(pref_names[i], ':', ' '.join([pref_names[j] for j in adjacent(i)]))
>>>
青森県 : 岩手県 秋田県
長野県 : 群馬県 埼玉県 新潟県 富山県 山梨県 岐阜県 静岡県 愛知県


境界線のベクトルデータ

get_data で各県の点リストと点のindexリストが取れます。これを使うと、pref_points で県の境界(index list)のリストが取れます。


python3

qpqo = get_data()

pnts = pref_points(qpqo)
pnts[0] # 北海道の境界座標(経度緯度)リスト
>>>
[[140.47133887410146, 43.08302992960164],
[140.43751046098984, 43.13755540826223],
[140.3625317793531, 43.18162745988813],
...

pref_map で境界線データを可視化できます。


python3

pref_map(range(1,48), qpqo=qpqo)


image

関東だけをグレースケールにする例。


python3

pref_map(groups['関東'], cols='gray', qpqo=qpqo)


image


県別データ(人口)を面積に変換

trans_area で県の面積を指定した比率に変換できます。

例えば、県ごとの変換比率を[2, 1, 1, 1, ...]とすると、北海道が元の面積の2倍、他県が元の面積と同じ比率になります。

人口比で変換してみましょう。総務省統計局から2014年の県別の人口2を取ってきましょう。


python3

# 実行には、pandas が必要です。

import pandas as pd
a = pd.read_excel('http://www.stat.go.jp/data/jinsui/2014np/zuhyou/05k26-2.xls',
skiprows=11, skip_footer=3, names='都道府県 男女計 男 女'.split(),parse_cols=[2,4,5,6])
a[:3]

都道府県
男女計

0
北海道
5400
2545
2855

1
青森県
1321
620
701

2
岩手県
1284
614
670

人口比の多い順に表示してみましょう。


python3

a['比'] = a.男女計 / a.男女計.mean()

a.sort_values('比', ascending=False)[:10]

都道府県
男女計


12
東京都
13390
6608
6782
4.95216

13
神奈川県
9096
4548
4548
3.36406

26
大阪府
8836
4256
4579
3.26791

22
愛知県
7455
3725
3731
2.75716

10
埼玉県
7239
3622
3617
2.67727

11
千葉県
6197
3082
3115
2.2919

27
兵庫県
5541
2645
2896
2.04928

0
北海道
5400
2545
2855
1.99714

39
福岡県
5091
2403
2688
1.88286

21
静岡県
3705
1824
1881
1.37026

可視化してみます。


python3

qpqo = get_data(True, True, True)

pref_map(range(1,48), qpqo=trans_area(a.男女計, qpqo))

image

なるべく、ラフにして歪みを減らしたのですが、なかなか厳しいです。


4色問題

隣接情報を使って4色問題を解いてみましょう。

1つの県を1色とし、隣接する県は異なるように、日本全体を4色で塗りましょう。このように隣り合うもの同士に違う色を割当てる問題を、頂点彩色問題とよびます。

頂点彩色問題とは、グラフ上で隣接する頂点が異なる色になるように、最小の色数で頂点に色を割り当てる問題です。

この応用としては、例えば、携帯電話の基地局ごとの周波数を決める問題があります。(異なる色→異なる周波数→電波が干渉しないので話せる)

area.png


4色問題を解く

どのような平面地図であっても隣接するエリアが異なるようにして、必ず4色以内で塗り分けられることが、数学的に証明されています。しかし、どのように塗り分けたらよいかは、自明ではありません。ここでは、数理最適化を解いて求めることにしましょう。

数理最適化は、コストの最小化などを解くときに使われますが、目的関数がない制約だけの問題でも解くことができます。数理最適化で用いるパッケージ pulpについては、最適化におけるPythonを見てください。


  • 数理モデル(1)で決めないといけないことは、変数表現、目的関数、制約条件の3つです。

  • 変数表現: 47都道府県×4色で188個の0または1しか取らない変数を用意します。このような変数は、バイナリ変数とよばれます。
    変数は、パッケージ pandasの表で管理します。この変数表(2)を使うことにより制約条件をわかりやすく書くことができます。

  • 目的関数: 今回は最大化などを行いませんので、設定しません。PuLPでは、目的関数を設定しなくても実行できます。

  • 制約条件: 1県ごとに1色とします(3)。隣接した県同士は、異なる色にします(4)。

  • 数理モデルができたら、ソルバーを実行するだけで解を求めることができます(5)。
    ソルバーは、数理モデルを解くソフトウェアで、pulpをインストールすると一緒にインストールされます。

  • 結果は、変数に対してvalueをよぶことで確認できます。ここでは、変数表に、新しい列"r"を追加し結果を設定しています(6)。
    この新しい列が0でない行を取得することにより、県に対する塗るべき色がわかります。

table.png


python3

from pulp import *

ad = [pref_names[j] for j in adjacent(i)]
m = LpProblem() # 数理モデル(1)
a = pd.DataFrame([(i, pref_names[i], j, LpVariable('x%d%d'%(i,j), cat=LpBinary))
for i in range(1,48) for j in range(4)], columns=['cd', '県', '色', 'x']) # 変数表(2)
for i in range(1,48):
m += lpSum(a[a.cd == i].x) == 1 # 1県1色(3)
for j in adjacent(i):
for k in range(4): # 隣接県を違う色に(4)
m += lpSum(a[((a.cd == i) | (a.cd == j)) & (a. == k)].x) <= 1
m.solve() # 求解(5)
a['r'] = a.x.apply(value) # 結果設定(6)
cols = a[a.r > 0]..apply(lambda i: ['red', 'blue', 'green', 'yellow'][i])
pref_map(range(1,48), cols=cols.tolist())

image





  1. numpyは、行列計算などの線形代数のライブラリです。同様のソフトとしては、MATLABなどがよく使われていました。numpyとMATLABは同じベースなので、性能的には大きな差はありません。しかし、MATLABは有料ですが、Python、numpyは無料で使えるというメリットがあります。 



  2. 第2表 都道府県,男女別人口及び人口性比―総人口,日本人人口(平成26年10月1日現在)(エクセル:41KB)