このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

dbscan

Density-based spatial clustering of applications with noise (DBSCAN)

構文

idx = dbscan(X,epsilon,minpts)

idx = dbscan(X,epsilon,minpts,Name,Value)

idx = dbscan(D,epsilon,minpts,'Distance','precomputed')

[idx,corepts] = dbscan(___)

説明

idx = dbscan(X,epsilon,minpts) は、DBSCAN アルゴリズム (アルゴリズムを参照) を使用して、n 行 p 列のデータ行列 X 内の観測値をクラスターに分割します。dbscan は、コア点の識別に必要な近傍探索半径 epsilon および最小近傍点数 minpts のしきい値に基づいて、観測値 (または点) をクラスター化します。この関数は、各観測値のクラスター インデックスが格納されている n 行 1 列のベクトル (idx) を返します。

idx = dbscan(X,epsilon,minpts,Name,Value) では、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。たとえば、'Distance','minkowski','P',3 を指定すると、DBSCAN アルゴリズムで指数 3 のミンコフスキー距離計量を使用できます。

idx = dbscan(D,epsilon,minpts,'Distance','precomputed') は、事前計算済みの観測値間のペアワイズ距離 D に対するクラスター インデックスのベクトルを返します。D には、pdist または pdist2 の出力を指定するか、pdist または pdist2 の出力形式にそれぞれ従う、より一般的な非類似度ベクトルまたは行列を指定できます。

[idx,corepts] = dbscan(___) は、前の構文におけるいずれかの入力引数の組み合わせを使用して、dbscan が識別したコア点が格納されている logical ベクトル corepts も返します。

例

入力データに対する DBSCAN の実行

既定のユークリッド距離計量で DBSCAN を使用して、2 次元の円状データセットをクラスター化します。また、2 乗ユークリッド距離計量で DBSCAN と k-means クラスタリングを使用してデータセットをクラスター化した結果を比較します。

ノイズがある 2 つの円が含まれている人工的なデータを生成します。

rng('default') % For reproducibility

% Parameters for data generation
N = 300;  % Size of each cluster
r1 = 0.5; % Radius of first circle
r2 = 5;   % Radius of second circle
theta = linspace(0,2*pi,N)';

X1 = r1*[cos(theta),sin(theta)]+ rand(N,1); 
X2 = r2*[cos(theta),sin(theta)]+ rand(N,1);
X = [X1;X2]; % Noisy 2-D circular data set

データセットを可視化します。

scatter(X(:,1),X(:,2))

プロットには、2 つの異なるクラスターがデータセットに含まれていることが示されています。

データに対して DBSCAN クラスタリングを実行します。epsilon の値として 1 を、minpts の値として 5 を指定します。

idx = dbscan(X,1,5); % The default distance metric is Euclidean distance

クラスタリングを可視化します。

gscatter(X(:,1),X(:,2),idx);
title('DBSCAN Using Euclidean Distance Metric')

ユークリッド距離計量を使用した場合、DBSCAN はデータセット内の 2 つのクラスターを正しく識別します。

2 乗ユークリッド距離計量を使用して、DBSCAN を実行します。epsilon の値として 1 を、minpts の値として 5 を指定します。

idx2 = dbscan(X,1,5,'Distance','squaredeuclidean');

クラスタリングを可視化します。

gscatter(X(:,1),X(:,2),idx2);
title('DBSCAN Using Squared Euclidean Distance Metric')

2 乗ユークリッド距離計量を使用した場合、DBSCAN はデータセット内の 2 つのクラスターを正しく識別します。

2 乗ユークリッド距離計量を使用して、k-means クラスタリングを実行します。k = 2 クラスターを指定します。

kidx = kmeans(X,2); % The default distance metric is squared Euclidean distance

クラスタリングを可視化します。

gscatter(X(:,1),X(:,2),kidx);
title('K-Means Using Squared Euclidean Distance Metric')

2 乗ユークリッド距離計量を使用した場合、k-means クラスタリングはデータセット内の 2 つのクラスターを正しく識別できません。

ペアワイズ距離に対する DBSCAN の実行

関数 dbscan に対する入力として観測値間のペアワイズ距離の行列を使用して DBSCAN クラスタリングを実行し、外れ値とコア点の個数を求めます。データセットは、自動車の周囲にある物体の座標を含む 3 次元の点の集合として格納された LIDAR スキャンです。

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

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

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

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

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

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

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

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

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

関数 pdist2 を使用して、観測値間のペアワイズ距離の行列 D を事前計算します。

D = pdist2(loc,loc);

ペアワイズ距離で dbscan を使用して、データをクラスター化します。epsilon の値として 2 を、minpts の値として 50 を指定します。

[idx, corepts] = dbscan(D,2,50,'Distance','precomputed');

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

numGroups = length(unique(idx));
gscatter(loc(:,1),loc(:,2),idx,hsv(numGroups));
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
grid

散布図に示されているように、dbscan は 11 個のクラスターを識別し、自動車を別個のクラスターに配置しています。

関数 dbscan は、(中心が (3,–4) の付近にある) 赤い丸の点のグループをプロットの右下にある点のグループと同じクラスター (グループ 7) に割り当てています。これらのグループは別々のクラスターに属すると考えられます。大きいクラスターを分断し、点をさらに分割するため、小さい値の epsilon を試すことができます。

また、データ内の外れ値 (idx の値が –1) もいくつか識別されています。dbscan が外れ値として識別した点の個数を求めます。

sum(idx == -1)

ans = 412

dbscan は、19,070 個の観測値から 412 個の外れ値を識別しました。

dbscan がコア点として識別した点の個数を求めます。corepts の値の 1 は、コア点を示します。

sum(corepts == 1)

ans = 18446

dbscan は、18,446 個の観測値をコア点として識別しました。

より幅広い例については、DBSCAN のパラメーター値の決定を参照してください。

入力引数

X — 入力データ

数値行列

入力データ。n 行 p 列の数値行列を指定します。X の行は観測値 (点) に、列は変数に対応します。

データ型: single | double

D — ペアワイズ距離

数値行ベクトル | 数値正方行列 | logical 行ベクトル | logical 正方行列

観測値間のペアワイズ距離。pdist が出力した数値行ベクトル、pdist2 が出力した数値正方行列、logical 行ベクトル、または logical 正方行列を指定します。D は、pdist または pdist2 の出力形式にそれぞれ従う、より一般的な非類似度ベクトルまたは行列にすることもできます。

前述した指定に関して、n 個の観測値 (行) と p 個の次元 (列) がある入力行列 X に対して D で使用できる形式を次の表で説明します。

指定	形式
数値行ベクトル (pdist(X) の出力)	X 内の観測値のペアに対応する、長さ n(n – 1)/2 の行ベクトル (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1)) という順序で並んでいる距離
数値正方行列 (pdist2(X,X) の出力)	n 行 n 列の行列。D(i,j) は X 内の観測値 i および j の間の距離 対角要素がゼロに等しい対称行列
logical 行ベクトル	X 内の観測値のペアに対応する、長さ n(n – 1)/2 の行ベクトル 距離が epsilon 以下であるかどうかを各要素が示す、logical 行ベクトル (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1)) という順序で並んでいる D の要素
logical 正方行列	n 行 n 列の行列。D(i,j) は X 内の観測値 i および j の間の距離が epsilon 以下であるかどうかを示す

メモ

D が logical ベクトルまたは logical 行列である場合、epsilon の値は空でなければなりません。たとえば、dbscan(D,[],5,'Distance','precomputed')。

データ型: single | double | logical

epsilon — イプシロン近傍

数値スカラー | []

点のイプシロン近傍。点の周囲の近傍探索半径を定義する数値スカラーを指定します。ある点のイプシロン近傍に minpts 個以上の近傍点が含まれている場合、dbscan はその点をコア点として識別します。

D が logical ベクトルまたは logical 行列である場合、epsilon の値は空 ([]) でなければなりません。

例: dbscan(X,2.5,10)

例: dbscan(D,[],5,'Distance','precomputed')、logical 行列または logical ベクトル D の場合

データ型: single | double

minpts — コア点に必要な最小近傍点数

正の整数

コア点に必要な最小近傍点数。正の整数を指定します。クラスター内で、コア点のイプシロン近傍には minpts 個以上の近傍点が含まれていなければなりませんが、境界点のイプシロン近傍に含まれる近傍点の個数は minpts より少なくなる可能性があります。

例: dbscan(X,2.5,5)

データ型: single | double

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名、Value は対応する値です。名前と値の引数は他の引数の後ろにする必要がありますが、ペアの順序は関係ありません。

R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name を引用符で囲みます。

例: dbscan(D,2.5,5,'Distance','precomputed') は、事前計算済みの観測値間のペアワイズ距離の行列 D、イプシロン近傍 2.5、および最小近傍点数 5 を使用する DBSCAN クラスタリングを指定します。

Distance — 距離計量

文字ベクトル | string スカラー | 関数ハンドル

距離計量。'Distance' と次の表で説明されている文字ベクトル、string スカラーまたは関数ハンドルから構成されるコンマ区切りのペアとして指定します。

値	説明
'precomputed'	事前計算済みの距離。dbscan に対する 1 番目の入力がペアワイズ距離のベクトルまたは行列 D である場合、このオプションを指定しなければなりません。
'euclidean'	ユークリッド距離 (既定)
'squaredeuclidean'	2 乗ユークリッド距離(効率向上のみを目的に提供されているオプション。三角不等式は満たさない)。
'seuclidean'	標準化されたユークリッド距離。観測値間の各座標差は、標準偏差 S = std(X,'omitnan') の対応する要素で除算することによりスケーリングされます。S について別の値を指定するには、Scale を使用します。
'mahalanobis'	X の標本共分散を使用したマハラノビス距離、C = cov(X,'omitrows')。C について別の値を指定するには、Cov を使用します。ここで、行列 C は対称な正定値です。
'cityblock'	市街地距離
'minkowski'	ミンコフスキー距離。既定の指数は 2 です。異なる指数を指定するには、P を使用します。P は正のスカラー値です。
'chebychev'	チェビシェフ距離 (最大座標差)
'cosine'	1 から、ベクトルとして扱われる点の間の夾角の余弦を引いた値
'correlation'	1 から、値の系列として扱われる点の間の標本相関を引いた値
'hamming'	ハミング距離 (異なる座標の比率)
'jaccard'	1 からジャカード係数 (異なる非ゼロ座標の比率) を減算
'spearman'	1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理)
@distfun	カスタム距離関数のハンドル。距離関数の形式は次のようになります。 function D2 = distfun(ZI,ZJ) % calculation of distance ... ここで、 ZI は、単一の観測値が含まれている 1 行 n 列のベクトルです。 ZJ は、複数の観測値が含まれている m2 行 n 列の行列です。distfun は、任意の個数の観測値が含まれている行列 ZJ を受け入れなければなりません。 D2 は m2 行 1 列の距離のベクトルであり、D2(k) は観測値 ZI と ZJ(k,:) の間の距離です。 データがスパースでない場合、通常は関数ハンドルではなく組み込みの距離を使用する方が高速に距離を計算できます。

定義については、距離計量を参照してください。

'seuclidean'、'minkowski' または 'mahalanobis' 距離計量を使用する場合、追加の名前と値のペアの引数 'Scale'、'P' または 'Cov' をそれぞれ指定して、距離計量を制御することができます。

例: dbscan(X,2.5,5,'Distance','minkowski','P',3) は、クラスタリング アルゴリズムを実行するときに、イプシロン近傍として 2.5、クラスターを成長させるための最小近傍点数として 5、および指数 3 のミンコフスキー距離計量を使用するよう指定します。

P — ミンコフスキー距離計量の指数

2 (既定値) | 正のスカラー

ミンコフスキー距離計量の指数。'P' と正のスカラー値をコンマで区切って指定します。

この引数は、'Distance' が 'minkowski' である場合のみ有効です。

例: 'P',3

データ型: single | double

Cov — マハラノビス距離計量の共分散行列

cov(X,'omitrows') (既定値) | 数値行列

マハラノビス距離計量の共分散行列。'Cov' と対称な正定値行列である数値行列から構成されるコンマ区切りのペアとして指定します。

この引数は、'Distance' が 'mahalanobis' である場合のみ有効です。

データ型: single | double

Scale — 標準化されたユークリッド距離計量のスケール係数

std(X,'omitnan') (既定値) | 正の値の数値ベクトル

標準化されたユークリッド距離計量のスケール係数。'Scale' と正の値の数値ベクトルから構成されるコンマ区切りのペアとして指定します。

X の各次元 (列) には対応する 'Scale' の値があるので、'Scale' の長さは p (X の列数) です。dbscan は、X の各次元について、'Scale' 内の対応する値を使用して、X とクエリ点の差を標準化します。

この引数は、'Distance' が 'seuclidean' である場合のみ有効です。

データ型: single | double

出力引数

idx — クラスター インデックス

数値列ベクトル

クラスター インデックス。数値列ベクトルとして返されます。idx の行数は n であり、idx の各行は X 内の対応する観測値のクラスター割り当てを示します。–1 に等しいインデックスは、外れ値 (またはノイズ点) を示します。

メモ

DBSCAN アルゴリズムを使用するクラスター割り当ては、観測値の順序に依存します。したがって、X の行を並べ替えると、観測値のクラスター割り当てが異なる結果になる可能性があります。詳細は、アルゴリズムを参照してください。

データ型: double

corepts — コア点のインジケーター

logical ベクトル

コア点のインジケーター。dbscan が識別したコア点のインデックスを示す n 行 1 列の logical ベクトルとして返されます。corepts のいずれかの行の値 1 は、X 内の対応する観測値がコア点であることを示します。それ以外の場合、コア点ではない観測値に対応する corepts の行の値は 0 になります。

データ型: logical

詳細

コア点

クラスターのコア点は、イプシロン近傍 (epsilon) 内に最小数 (minpts) 以上の近傍点がある点です。各クラスターには、少なくとも 1 つのコア点が含まれていなければなりません。

境界点

クラスターの境界点は、イプシロン近傍 (epsilon) 内の近傍点の個数がコア点に必要な最小数 (minpts) より少ない点です。一般に、境界点のイプシロン近傍には、コア点のイプシロン近傍より大幅に少ない個数の点が含まれます。

ノイズ点

ノイズ点は、どのクラスターにも属さない外れ値です。

ヒント

• 多数の epsilon の値に対して反復処理を行うときの速度を向上させるには、dbscan に対する入力として D を渡すことを検討してください。このようにすると、すべての反復で距離を計算する必要がなくなります。

• pdist2 を使用して D を事前計算する場合、pdist2 の名前と値のペアの引数 'Smallest' または 'Largest' による D の列の選択または並べ替えは行わないでください。dbscan は D が正方行列であると想定するので、n 個未満の距離を選択するとエラーが発生します。D の各列で距離を並べ替えると、D の解釈が不十分になり、関数 dbscan で使用したときに無意味な結果が生成される可能性があります。

• 効率的にメモリを使用するため、D が大きい場合は D を数値行列ではなく logical 行列として dbscan に渡すことを検討してください。既定では、MATLAB^® は数値行列の各値の格納に 8 バイト (64 ビット) を使用しますが、logical 行列の各値の格納には 1 バイト (8 ビット) を使用します。

• minpts の値を選択するには、入力データの次元数に 1 を加算した値以上の値を検討してください [1]。たとえば、n 行 p 列の行列 X の場合、p + 1 以上の値を 'minpts' に設定します。

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

アルゴリズム

• DBSCAN は、データ内のクラスターとノイズを検出するように設計されている、密度に基づくクラスタリング アルゴリズムです。このアルゴリズムでは、コア点、境界点およびノイズ点という 3 種類の点を識別します [1]。関数 dbscan は、指定された epsilon および minpts の値に対して、以下のようにアルゴリズムを実装します。

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

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

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

        メモ

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

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

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

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

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

• 2 つのクラスターの密度が異なっており、互いに近い場合、つまり、2 つの境界点の距離 (各クラスターからの距離) が epsilon 未満である場合、dbscan は 2 つのクラスターを 1 つに結合する可能性があります。

• すべての有効なクラスターに minpts 個以上の観測値が含まれるとは限りません。たとえば、dbscan は、互いに近い 2 つのクラスターに属する境界点を識別する可能性があります。このような場合、最初に検出されたクラスターに境界点が割り当てられます。この結果、2 番目のクラスターは有効なクラスターのままですが、観測値の個数が minpts より少なくなる可能性があります。

参照

[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.

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意事項および制限事項:

• 距離の入力引数 (Distance) の値は、コンパイル時の定数でなければなりません。たとえば、ミンコフスキー距離を使用するには、coder.Constant("Minkowski") を codegen (MATLAB Coder) の -args の値に含めます。

• 距離の入力引数 (Distance) の値をカスタム距離関数にすることはできません。

• dbscan では、高速ユークリッド距離計算、つまり名前が fast から始まる距離計量 ("fasteuclidean" など) のコード生成はサポートされていません。

• 名前と値の引数に含まれる名前はコンパイル時の定数でなければなりません。たとえば、生成されたコードで名前と値の引数 P を使用するには、{coder.Constant("P"),0} を codegen の -args の値に含めます。

• dbscan に対して生成されるコードでは、parfor (MATLAB Coder) を使用して、サポートされる共有メモリ マルチコア プラットフォームで並列実行されるループが作成されます。コンパイラが Open Multiprocessing (OpenMP) アプリケーション インターフェイスをサポートしない場合、または OpenMP ライブラリを無効にした場合、MATLAB Coder™ は parfor ループを for ループとして扱います。サポートされるコンパイラについては、サポートされるコンパイラを参照してください。OpenMP ライブラリを無効にするには、構成オブジェクトの EnableOpenMP プロパティを false に設定します。詳細については、coder.CodeConfig (MATLAB Coder) を参照してください。

• dbscan は、生成されたスタンドアロン C/C++ コードにおいて、整数型 (int32) のインデックスを返します。そのため、関数は、単精度の入力を使用する場合、厳密な単精度のサポートを可能にします。MEX コード生成では、関数は依然として MATLAB の動作に一致する倍精度のインデックスを返します。

バージョン履歴

R2019a で導入

参考

clusterdata | kmeans | kmedoids | linkage | pdist | pdist2

トピック

• DBSCAN の紹介