Main Content

このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

DBSCAN

DBSCAN の紹介

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) は、任意の形状のクラスターおよびデータのノイズ (外れ値) を識別するアルゴリズムです。Statistics and Machine Learning Toolbox™ の関数 dbscan は、観測値間のペアワイズ距離または入力データ行列に対してクラスタリングを実行します。dbscan は、クラスターのインデックスと、コア点 (クラスター内の点) である観測値を示すベクトルを返します。k-means クラスタリングと異なり、DBSCAN アルゴリズムでは、クラスターの個数を事前に知る必要はなく、クラスターが球状である必要もありません。DBSCAN は、どのクラスターにも属していない点を識別するので、密度に基づく外れ値検出にも役立ちます。

点をクラスターに割り当てるには、最小数 (minpts) 以上の近傍点がイプシロン近傍 (epsilon) に含まれているという条件を満たさなければなりません。そうでない場合、点は epsilonminpts の条件を満たす別の点のイプシロン近傍内に存在する可能性があります。DBSCAN アルゴリズムでは、3 種類の点を識別します。

  • コア点 — minpts 個以上の近傍点がイプシロン近傍内にある、クラスター内の点

  • 境界点 — minpts 個より少ない近傍点がイプシロン近傍内にある、クラスター内の点

  • ノイズ点 — どのクラスターにも属さない外れ値

DBSCAN は広い範囲の距離計量で機能するので、特定の用途に応じてカスタム距離計量を定義できます。距離計量の選択により近傍の形状が決まります。

アルゴリズムの説明

関数 dbscan は、コア点に必要なイプシロン近傍 epsilon および最小近傍点数 minpts について指定された値に対して、以下のように DBSCAN を実装します。

  1. 入力データセット X から、ラベルが付いていない 1 番目の観測値 x1 を現在の点として選択し、1 番目のクラスター ラベル C を 1 に初期化します。

  2. 現在の点のイプシロン近傍 epsilon 内にある点の集合を求めます。これらの点は近傍点です。

    1. 近傍点数が minpts より小さい場合、現在の点にノイズ点 (つまり外れ値) のラベルを付けます。ステップ 4 に進みます。

      メモ

      X 内の他の点の epsilonminpts によって設定される制約を後にノイズ点が満たす場合、dbscan はノイズ点をクラスターに再割り当てする可能性があります。このように点を再割り当てする処理は、クラスターの境界点に対して発生します。

    2. それ以外の場合、クラスター C に属するコア点のラベルを現在の点に付けます。

  3. 現在のクラスター C に属しているというラベルを付けられる新しい近傍点が見つからなくなるまで、各近傍点 (新しい現在の点) に対してステップ 2 を繰り返します。

  4. X 内でラベルが付いていない次の点を現在の点として選択し、クラスター カウントに 1 を加算します。

  5. X 内のすべての点にラベルが付けられるまで、ステップ 2 ~ 4 を繰り返します。

DBSCAN のパラメーター値の決定

この例では、dbscanepsilon および minpts パラメーターの値を選択する方法を示します。データセットは、自動車の周囲にある物体の座標を含む 3 次元の点の集合として格納された LIDAR スキャンです。

データセットの読み込み、前処理および可視化を行う。

物体の x、y、z 座標を読み込みます。

load('lidar_subset.mat') 
X = lidar_subset;

自動車の周囲の環境を強調するため、道路表面の上部の領域で自動車の左右 20 メートルおよび前後 20 メートルにわたるように関心領域を設定します。

xBound  = 20; % in meters
yBound  = 20; % in meters
zLowerBound = 0; % in meters

指定した領域内の点のみが含まれるようにデータをトリミングします。

indices = X(:,1) <= xBound & X(:,1) >= -xBound ...
    & X(:,2) <= yBound & X(:,2) >= -yBound ...
    & X(:,3) > zLowerBound;
X = X(indices,:); 

2 次元散布図としてデータを可視化します。プロットに注釈を付けて、自動車を強調します。

scatter(X(:,1),X(:,2),'.');
annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')

Figure contains an axes. The axes contains an object of type scatter.

点集合の中心 (赤い丸の部分) には、自動車の屋根とボンネットが含まれています。他のすべての点は障害物です。

minpts の値を選択する。

minpts の値を選択するため、入力データの次元数に 1 を加算した値以上の値を考えます [1]。たとえば、np 列の行列 X の場合、P+1 以上の値を 'minpts' に設定します。

与えられたデータセットに対して、4 以上 (具体的には 50) を minpts の値として指定します。

minpts = 50; % Minimum number of neighbors for a core point

epsilon の値を選択する。

epsilon の値を推定する方法の 1 つは、入力データ X について k 距離グラフを生成することです。X の各点について、k 番目に近い点までの距離を求め、この距離に対して並べ替えた点をプロットします。このグラフには、折れ曲がる部分があります。点が外れ値 (ノイズ) 領域に近づき始める領域なので、折れ曲がる部分に対応する距離は一般に epsilon に適した選択肢です [1]。

k 距離グラフをプロットする前に、X 内の観測値についてペアワイズ距離を最小のものから minpts 個、昇順で求めます。

kD = pdist2(X,X,'euc','Smallest',minpts); % The minpts smallest pairwise distances

k 距離グラフをプロットします。

plot(sort(kD(end,:)));
title('k-distance graph')
xlabel('Points sorted with 50th nearest distances')
ylabel('50th nearest distances')
grid

Figure contains an axes. The axes with title k-distance graph contains an object of type line.

折れ曲がる部分は 2 の付近にあるので、epsilon の値を 2 に設定します。

epsilon = 2;

dbscan を使用してクラスタリングを行う。

前の手順で決定した minptsepsilon の値で dbscan を使用します。

labels = dbscan(X,epsilon,minpts);

クラスタリングを可視化し、Figure に注釈を付けて特定のクラスターを強調します。

gscatter(X(:,1),X(:,2),labels);
title('epsilon = 2 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

Figure contains an axes. The axes with title epsilon = 2 and minpts = 50 contains 12 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

dbscan は、11 個のクラスターと一連のノイズ点を識別します。さらに、このアルゴリズムは、点集合の中心にある自動車を独立したクラスターとして識別します。

dbscan は、(中心が (-6,18) 付近にある) 黒い丸のクラスターや (中心が (2.5,18) 付近にある) 青い丸のクラスターなど、独立したクラスターをいくつか識別します。また、この関数は、(中心が (3,–4) の付近にある) 赤い丸の点のグループをプロットの右下にある点のグループと同じクラスター (グループ 7) に割り当てています。これらのグループは別々のクラスターに属すると考えられます。

大きいクラスターを分断し、点をさらに分割するため、epsilon の値を小さくします。

epsilon2 = 1;
labels2 = dbscan(X,epsilon2,minpts);

クラスタリングを可視化し、Figure に注釈を付けて特定のクラスターを強調します。

gscatter(X(:,1),X(:,2),labels2);
title('epsilon = 1 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

Figure contains an axes. The axes with title epsilon = 1 and minpts = 50 contains 17 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16.

使用するイプシロンの値を小さくすることにより、dbscan は赤い丸の点のグループを異なるクラスター (グループ 13) に割り当てることができます。しかし、dbscan が正しく識別していたクラスターの一部が、クラスターの点と外れ値に分離するようになりました。たとえば、クラスター グループ 2 (黒い丸) とクラスター グループ 3 (青い丸) を確認してください。正しい epsilon の値は、1 と 2 の間にあります。

epsilon の値として 1.55 を使用してデータをクラスタリングします。

epsilon3 = 1.55;
labels3 = dbscan(X,epsilon3,minpts);

クラスタリングを可視化し、Figure に注釈を付けて特定のクラスターを強調します。

gscatter(X(:,1),X(:,2),labels3);
title('epsilon = 1.55 and minpts = 50')
grid
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue')
annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

Figure contains an axes. The axes with title epsilon = 1.55 and minpts = 50 contains 16 objects of type line. These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

epsilon1.55 に設定すると、dbscan によるクラスターの識別が改善されます。たとえば、赤い丸のクラスター (中心は (3,–4) 付近)、黒い丸のクラスター (中心は (-6,18) 付近)、および青い丸のクラスター (中心は (2.5,18) 付近) が独立したクラスターとして識別されています。

参照

[1] Ester, M., H.-P. Kriegel, J. Sander, and X. Xiaowei. “A density-based algorithm for discovering clusters in large spatial databases with noise.” In Proceedings of the Second International Conference on Knowledge Discovery in Databases and Data Mining, 226-231. Portland, OR: AAAI Press, 1996.

関連するトピック