K-meansクラスタリング―任意の距離を持つデータに対する応用―

Index

概要
動機
本文

概要

空間内の点をいくつかのグループに分割することを考え、データにK-meansクラスタリングアルゴリズムを適用する。応用例として、MDSを用いて点同士の距離が任意となる場合（直線距離でなく道のりが与えられる等）の最適化手法についても考える。最後に、クラスター同士が均等な大きさとなるような場合の手法についても考える。

なお、当記事のコードはすべてPythonで実装されている。実装したコードは

GitHub - doraneko94/water_supply: Jupyter notebook (Python) for water supply station optimization.

Jupyter notebook (Python) for water supply station optimizat...

にJupyter Notebookとしてまとめてある。

動機

2021年2月のすべての土日を使って、総務省主催のGeospatial Hackers Program、すなわち地理空間情報技術を活用したプロダクト開発ハッカソンに技術メンターとして参加した。その際、「災害時の避難所を地図上に表示し、位置・標高・人口等をもとに、最適な給水所の配置計画について考える」というプロジェクトが立った。Pythonの機械学習ライブラリを使えば、給水所のクラスタリングくらいは簡単にできるのではないかと思ったので、ここに手法をまとめることにした。

本文

必要なもの

Python3 (ver. 3.8 以上が望ましい)

加えて、以下のライブラリを必要とする。pip等を使ってインストールしてほしい。

numpy
matplotlib
scikit-learn

また、以下のようなデータ分析は

Jupyter Notebook

上で行うと便利である。

ライブラリのインポート

import numpy as np
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

N次元配列を扱うためのnumpy, グラフ表示用のmatplotlibに加え、3D表示用のmpl_toolkitsの必要な機能をインポートする。

ダミーデータの準備

# generate data
cov = np.eye(3)
np.random.seed(42)
c0 = np.random.multivariate_normal([0.0, 0.0, 0.0], cov, size=10)
c1 = np.random.multivariate_normal([2.0, 2.0, 0.0], cov, size=10)
c2 = np.random.multivariate_normal([2.0, 2.0, 3.0], cov, size=10)
data = np.vstack((c0, c1, c2))

3つの異なる中心を持つ、3つの塊のデータ点を生成し、これを避難所の位置に見立てる。このとき、c1, c2の中心は平面上では同じ座標を持つが、標高が異なる。

# plot data to 3D space
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter3D(c0[:, 0], c0[:, 1], c0[:, 2])
ax.scatter3D(c1[:, 0], c1[:, 1], c1[:, 2])
ax.scatter3D(c2[:, 0], c2[:, 1], c2[:, 2])
ax.set_title("3D-data")
plt.savefig("3d_data.png")
plt.show()

塊ごとに、3次元空間にプロット。

# plot data to 2D plane
plt.scatter(c0[:, 0], c0[:, 1])
plt.scatter(c1[:, 0], c1[:, 1])
plt.scatter(c2[:, 0], c2[:, 1])
plt.title("2D-data")
plt.savefig("2d_data.png")
plt.show()

標高の情報を無視して2次元空間にプロットすると、c1, c2の塊は重なっていることがわかる。

2次元データに対する K-means クラスタリング

まずは標高の情報を無視して、2次元のデータでK-meansクラスタリングを試す。

from sklearn.cluster import KMeans

機械学習ライブラリのscikit-learnから必要なものをインポートし、

# initialize KMeans class
km = KMeans(n_clusters=3, random_state=42)

K-meansクラスタリングのためのクラス（ややこしいが、ここでは構造体のこと）を初期化する。クラスの引数の説明と合わせて、ここでK-meansクラスタリングの原理について解説しておこう。

K-meansクラスタリングでは、最初にK個の点をランダムにばらまく。この点はクラスターの「中心点」と呼ばれる。そして、以下の操作を変化が起こらなくなるまで繰り返す。

各データ点を、最も距離が近い中心点のクラスターに割り当てる
各クラスターに属するデータ点との距離の合計が最も小さくなる位置に、各中心点を移動する

この結果、各データ点はK個のクラスターにいい感じに分類される。したがって、K-meansクラスタリングを行う際には事前にKの値を決めて置く必要があり、ここではn_clusters=3を指定している。また、初期値はランダムとなるため、再現性を持たせるために乱数シードをrandom_state=42に固定した。

# predict cluster from 2D data
label = km.fit_predict(data[:, :2])

これに3つ目の次元を除いたデータを与えることで、それぞれのデータ点がどのクラスターに含まれるかを予測して返してくれる。

# plot result to 2D plane
plt.scatter(data[:, 0][label==0], data[:, 1][label==0])
plt.scatter(data[:, 0][label==1], data[:, 1][label==1])
plt.scatter(data[:, 0][label==2], data[:, 1][label==2])
plt.title("KMeans for 2D-data")
plt.savefig("2d_data_km_2d.png")
plt.show()

その結果、2次元平面上では綺麗に3つのクラスターに分類されていることがわかる。しかし

# plot result to 3D space
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter3D(data[:, 0][label==0], data[:, 1][label==0], data[:, 2][label==0])
ax.scatter3D(data[:, 0][label==1], data[:, 1][label==1], data[:, 2][label==1])
ax.scatter3D(data[:, 0][label==2], data[:, 1][label==2], data[:, 2][label==2])
ax.set_title("KMeans for 2D-data")
plt.savefig("2d_data_km_3d.png")
plt.show()

当然といえば当然だが、標高の情報を無視したので、3次元空間上では青とオレンジのクラスターが混ざってしまっている。

3次元データに対する K-means クラスタリング

続いて3次元データに対するK-meansクラスタリングの適用を考える。結論からいうと、K-meansクラスに3次元データを与えれば、3次元空間上でクラスタリングを行ってくれる。

# predict cluster from 3D data
label = km.fit_predict(data)

結果をプロットすると

# plot result to 3D space
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d