K-means クラスタリングがあるのに、なぜ DBSCAN クラスタリングアルゴリズムが必要なのでしょうか?

クラスタリング分析は、データポイントを複数の特定のクラスターまたはグループに分割する教師なし学習手法です。これにより、ある意味では、同じグループ内のデータポイントは類似したプロパティを持ち、異なるグループ内のデータポイントは異なるプロパティを持ちます。

クラスター分析には、さまざまな距離メトリックに基づくさまざまな方法が含まれます。例えば。 K-means (ポイント間の距離)、Affinity propagation (グラフ間の距離)、平均シフト (ポイント間の距離)、DBSCAN (最近接ポイント間の距離)、ガウス混合 (中心までのマハラノビス距離)、スペクトルクラスタリング (グラフ間の距離) など。

2014 年、DBSCAN アルゴリズムは、主要なデータマイニングカンファレンス ACM SIGKDD で Test of Time Award (理論と実践の両方で広く注目を集めたアルゴリズムに授与される賞) を受賞しました。

すべてのクラスタリング方法では、最初に類似性を計算し、次に類似性を使用してデータポイントをグループまたはクラスターにクラスタ化するという同じアプローチが使用されます。この記事では、ノイズを含む密度ベースクラスタリング法 (DBSCAN) に焦点を当てます。

すでに K 平均法クラスタリングが存在しているのに、なぜ DBSCAN のような密度ベースのクラスタリングアルゴリズムが必要なのでしょうか?

K 平均法クラスタリングでは、関連性の低い観測値をクラスタ化できます。観測値がベクトル空間内で離れていても、すべての観測値は最終的に何らかのクラスターの一部になります。クラスタリングはクラスター要素の平均に依存するため、各データポイントはクラスターの形成に役割を果たします。

データポイントのわずかな変更がクラスタリングの結果に影響する可能性があります。 DBSCAN では、クラスターの形成方法により、この問題は大幅に軽減されます。奇妙な形状のデータに遭遇しない限り、これは通常大きな問題にはなりません。

K-means を使用する際のもう 1 つの難点は、使用するクラスターの数 (「k」) を指定する必要があることです。多くの場合、k の適切な値が何であるかは事前にわかりません。

DBSCAN の利点は、使用するためにクラスターの数を指定する必要がないことです。必要なのは、値間の距離を計算する関数と、特定の距離を「近い」と定義するためのいくつかの指示だけです。 DBSCAN は、さまざまな分布にわたって K-means よりも合理的な結果を生成します。次の図はこの事実を示しています。

密度ベースのクラスタリングアルゴリズム

密度ベースのクラスタリングは、データ空間内のクラスターが連続した高ポイント密度領域であり、連続した低ポイント密度領域によって他のクラスターから分離されているという仮定に基づいて、データ内の一意のグループ/クラスターを識別する教師なし学習方法です。

ノイズ付き密度ベースクラスタリング (DBSCAN) は、密度クラスタリングに基づく基本的なアルゴリズムです。ノイズや外れ値を含む大量のデータから、さまざまな形状やサイズのクラスターを検出できます。

DBSCAN アルゴリズムは次の 2 つのパラメータを使用します。

eps (ε): 任意の点の近傍内の点を特定するために使用される距離メトリック。
minPts: 領域を密集していると定義するために、クラスター化する必要があるポイントの最小数 (しきい値)。

これらのパラメータは、密度到達可能性と密度接続性という 2 つの概念を調べると理解できます。

密度の観点から見た到達可能性は、ある点が他の点から一定の距離 (eps) 以内にある場合、その点に別の点から到達できることを確立します。

接続性には、ポイントが特定のクラスター内に配置されているかどうかを判断するための推移性ベースのリンクメソッドが含まれます。たとえば、p->r->s->t->q の場合、p と q は接続できます。ここで、a->b は、b が a の近くにあることを意味します。

DBSCAN クラスタリングが完了すると、次の 3 種類のポイントが生成されます。

コアポイント (コア) - このポイントは、距離 n の範囲内に少なくとも m 個のポイントがあることを示します。
境界 - このポイントは、距離 n に少なくとも 1 つのコアがあることを示します。
ノイズポイント：コアポイントでも境界ポイントでもありません。そして、それ自体から n の範囲内に m 個未満の点があります。

DBSCANクラスタリングアルゴリズムの手順

このアルゴリズムは、データセット内のポイントをランダムに選択することによって機能します (すべてのポイントが訪問されるまで)。
この点の「ε」半径内に少なくとも「minPoint」個の点がある場合、これらすべての点は同じクラスターに属していると見なされます。
各隣接点の近傍計算を再帰的に繰り返してクラスターを拡張する

パラメータ推定

すべてのデータマイニングタスクにはパラメータの問題があります。各パラメータは特定の方法でアルゴリズムに影響を与えます。 DBSCAN にはパラメータ ε と minPts が必要です。

ε: ε の値は、最大から最小の順に並べられた k=minPts-1 近傍までの距離を表す k 距離グラフを使用して選択できます。このプロットが「エルボー」を示している場合、ε 値は適切です。ε が小さすぎると、データの大部分がクラスター化されません。ε 値が高すぎると、クラスターが結合され、ほとんどのオブジェクトが同じクラスターに含まれます。一般的に、ε の値は小さいほど望ましく、経験則として、この距離内に含まれるポイントはごく一部にする必要があります。
距離関数: 距離関数の選択は ε の選択と密接に関連しており、結果に重要な影響を与えます。通常、パラメータ ε を選択する前に、まずデータセットの適切な類似度尺度を決定する必要があります。このパラメータの推定値はありませんが、データセットに応じて距離関数を適切に選択する必要があります。
minPts: 経験によれば、最小の minPts はデータセットの次元数 D から導き出せます。つまり、minPts ≥ D+1 です。各ポイントは既にそれ自体がクラスターであるため、minPts=1 の低い値は意味がありません。 minPts≤2の場合、結果は単一リンクメトリックを使用した階層的クラスタリングと同じになり、デンドログラムは高さεでカットされます。したがって、少なくとも 3 つの minPt を選択する必要があります。

ただし、ノイズの多いデータセットの場合、一般に値が大きいほど良くなり、より有意なクラスターが生成されます。経験則としては、minPts=2·dim を使用できますが、非常に大きなデータ、ノイズの多いデータ、または重複を多く含むデータの場合は、より大きな値を選択することをお勧めします。

sklearn を使用して Python で DBSCAN を実装する

まず、DBSCAN を使用して球面データをクラスタ化します。

まず、対応するラベルを持つ 750 個の球状トレーニングデータポイントを生成します。次に、トレーニングデータの特徴が標準化され、最後に sklearn ライブラリの DBSCAN が適用されます。

球面データのクラスタリングにおける DBSCAN

黒いデータポイントは、上記の結果の外れ値を表します。次に、DBSCAN を使用して非球形データをクラスタ化します。

 numpyをnpとしてインポートする
           matplotlib.pyplot を plt としてインポートします。
           sklearn からメトリックをインポート
           sklearn.datasets から make_circles をインポートします
           sklearn.preprocessing から StandardScaler をインポートします
           sklearn.clusterimportDBSCAN から
           X, y = make_circles ( n_samples = 750 、係数= 0.3 、ノイズ= 0.1 )
 X =標準スケーラ().fit_transform(X)
 y_pred = DBSCAN ( eps = 0.3 、 min_samples = 10 ).fit_predict(X)
           plt.scatter(X[:,0], X[:,1], c = y_pred )の散布図
           print('クラスターの数: {}'.format(len(set(y_pred[np.where(y_pred !=-1)]))))
           print('均質性:{}'.format(metrics.homogeneity_score(y, y_pred)))
           print('完全性:{}'.format(metrics.completeness_score(y, y_pred)))
           print("V-measure:%0.3f"% metrics.v_measure_score(labels_true,labels))
           print("調整されたRandIndex: %0.3f"
                 % metrics.adjusted_rand_score(labels_true,labels))
           print("調整された相互情報: %0.3f"
                 % metrics.adjusted_mutual_info_score(labels_true、ラベル))
           print("シルエット係数: %0.3f"
                 % metrics.silhouette_score(X, ラベル))

非球面データのクラスタリングにおける DBSCAN

これはまさに完璧です。 K-means と比較すると、次のように完全に間違った出力が生成されます。

K平均法クラスタリングの結果

DBSCAN クラスタリングアルゴリズムの複雑さ

平均ケース: 最良/最悪のケースと同じですが、データとアルゴリズムの実装によって異なります。
最良のケース: インデックスシステムを使用してデータセットを保存し、近傍クエリを対数時間で実行できるようにすると、平均実行時複雑度 O(nlogn) を実現できます。
最悪の場合: インデックス構造を使用しない場合、または縮退データ (たとえば、すべてのポイントの距離が ε 未満) の場合、最悪の場合の実行時複雑度は依然として O(n²) です。

密度ベースのクラスタリングアルゴリズムは任意の形状のクラスターを学習できますが、レベルセットツリーアルゴリズムは密度が大きく異なるデータセット内のクラスターを学習できます。

画像ソース: unsplash

ただし、これらのアルゴリズムは、K-means などのパラメトリッククラスタリングアルゴリズムと比較すると、調整がやや難しいことに注意してください。 K-means のクラスタリングパラメータと比較すると、DBSCAN またはレベルセットツリーのイプシロンパラメータは直感的に理解しにくいため、これらのアルゴリズムに適した初期パラメータ値を選択することがより困難になります。

<<: 人工知能がチップのルネッサンスを推進

>>: 行列乗算の最適化と畳み込みにおけるその応用