Scikit-learnのDBSCANクラスによるクラスタリング

はじめに

DBSCANはk-means法と並んでよく用いられるクラスタリング手法です。DBSCANはDensity-Based Spatial Clustering of Applications with Noiseの略で、「ノイズ付きのデータに適用可能な密度ベースの空間的クラスタリング」という意味です。

DBSCANには以下の長所があります。

k-means法と比較して実行が遅いが、ある程度大規模なデータにも適用できる。
ユーザがクラスタリング数を決める必要がない。

この手法は、あるクラスタに属するデータは密集しており、クラスタ同士の空間は比較的空虚（スパース）であることを仮定しています。

また、この記事ではPythonとScikit-learnによるサンプルコードも示します。実行環境は以下の通りです。

Python: 3.9.7
NumPy: 1.20.3
sklearn: 0.24.2
matplotlib: 3.4.3

アルゴリズム

DBSCAN法のアルゴリズムは次の通りです。

適当にデータを1点選択する。
そのデータ点から距離$\epsilon$以内にあるデータ点数を数える。
2.のデータ点数がしきい値$N_{min}$未満であれば、そのデータを「ノイズ」に分類して8.に映る。
2.のデータ点数が$N_{min}$以上であれば、1.の点を「コア点」と呼び、新しいクラスタのラベルを割り当てる。
コア点から距離$\epsilon$以内にある未分類のデータに対して、4.と同じラベルを割り当て、同様に距離$\epsilon$以内にあるデータ点数を数える。
5.のデータ点数が$N_{min}$未満であれば「到達可能点」（または境界点）と呼ぶ。
5.のデータ点数が$N_{min}$以上あればコア点として、5.に戻ってさらに近傍のデータ点を調べる。
まだ調べていない点があれば、1.に戻る。全ての点を調べ終わると終了する。

データ点は、コア点、到達可能点、ノイズのいずれかに分類されます。また、クラスタは、その周囲$\epsilon$以内にコア点が存在しなくなるまで成長します。

dbscan algorithm

DBSCANを同じデータに対して実行すると、コア点とノイズは常に同じデータになります。一方、到達可能点がどのクラスタに属するか異なる場合があります。これは、到達可能点は複数のクラスタ同士の境界にあることが多く、形成されるクラスタの順番に依存するためです。

DBSCANでは、新たにデータが与えられた場合はクラスタの予測ができません（学習を最初からやり直す必要があります）。

scikit-learnのDBSCAN法

DBSCANクラス

scikit-learnではsklearn.cluster.DBSCANというクラスにDBSCAN法が実装されています。

1
2
3


class klearn.cluster.DBSCAN(eps=0.5, min_samples=5,
    metric='euclidean', metric_params=None, algorithm='auto',
    leaf_size=30, p=None, n_jobs=None)

主なパラメータの意味は以下の通りです。

eps (float): コア点から探索する距離（デフォルトは0.5）。
min_samples (int): コア点をクラスタとして判定する最小データ点数（デフォルトは5）。
n_jobs (int): 並列計算数を指定します。-1にすると全てのCPUコアを使用します。

また、主なメソッドは以下の通りです。

fit(X): 特徴量X（サンプル数×特徴量数の2次元配列）をクラスタリングする。
fit_predict(X): 特徴量Xをクラスタリングし、結果を返す。

使用例

DBSCANクラスの使用例を示します。X_trainは行がサンプル、列が特徴量の2次元配列です（PandasのDataFrameなどでも可）。DBSCANクラスのオブジェクトをdbscanという名前で作成し、fit_predictでクラスタリングを行います。ここで、分析するデータに合わせてパラメータeps, min_samplesを設定しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import numpy as np
from sklearn.cluster import DBSCAN

# 学習データ
X_train = np.array([[0, 0],
                    [0, 1],
                    [0, 2],
                    [2, 0],
                    [3, 0],
                    [4, 5],
                    [5, 4],
                    [2, 4]])

dbscan = DBSCAN(eps=1.5, min_samples=2)
cluster_pred = dbscan.fit_predict(X_train)

print(cluster_pred)

実行結果

クラスタリングの結果は以下になりました。1～3番目のデータはクラスタ0, 4, 5番目のデータはクラスタ1, …, に属することを示しています。また、ノイズに分類されたデータは-1となります。

1

[ 0  0  0  1  1  2  2 -1]

最後に、クラスタリングの結果をMatplotlibを使って図示します。

1
2
3
4
5
6
7
8


import matplotlib.pyplot as plt

fig, ax = plt.subplots()
for i in range(-1, max(cluster_pred)+1):
    x = X_train[cluster_pred==i]
    ax.scatter(x[:,0], x[:,1], s=50, label=i)
ax.legend()
plt.show()

実行結果

クラスタによって色が異なるようにしています。近くにあるデータ同士が同じクラスタに含まれることが分かります。

dbscan result

参考

sklearn.cluster.DBSCAN — scikit-learn documentation