Python 密度クラスタリング アルゴリズム - DBSCAN の実践

この記事の主な内容:

1. 序文
2. DBSCAN クラスタリング アルゴリズム
3. パラメータ選択
4. DBSCANアルゴリズムの反復の視覚化
5. 共通評価方法：シルエット係数
6. Python で DBSCAN クラスタリング アルゴリズムを実装する

1. はじめに

昨年、R 言語でクラスタリング アルゴリズムを学習していたとき、階層的クラスタリング、体系的クラスタリング、K 平均法クラスタリング、K 中心クラスタリングを学び、最終的に DBSCAN クラスタリング アルゴリズムに魅了されました。

なぜでしょうか? まず、どんな形のクラスターでも見つけられるからです。次に、理論が比較的シンプルで理解しやすいと思います。今年は Python で DBSCAN を勉強する予定です。

公式の説明は次のとおりです。

• DBSCAN (ノイズを含むアプリケーションの密度ベースの空間クラスタリング) は、密度ベースの空間クラスタリング アルゴリズムです。
• このアルゴリズムは、十分な密度を持つ領域をクラスターに分割し、ノイズの多い空間データベース内で任意の形状のクラスターを見つけます。クラスターは、密度で接続されたポイントの最大セットとして定義されます。

2. DBSCANクラスタリングアルゴリズム

テキストの説明は分かりにくいので、まず次の図を見てください。

上記の点は、サンプル空間に分散された多数のサンプルです。ここでの目標は、サンプル空間内で距離が近いものを 1 つのカテゴリにまとめることです。

ポイント A 付近のポイント密度が比較的高いことがわかりました。赤い円は特定のルールに従ってここを転がり、最終的に A 付近の 5 つのポイントを集めます。これらのポイントは赤でマークされ、同じクラスターとして定義されます。

収集されていないその他のものも同じルールに従ってクラスター化されます。

比喩的に言えば、これはシステムが多数のサンプル ポイントから 1 つのサンプル ポイントをランダムに選択し、この選択したサンプル ポイントの周りに円を描き、円の半径と円内に含まれるサンプル ポイントの最小数を指定するものと考えることができます。指定された半径内に十分なサンプル ポイントがある場合、円の中心はこの内部のサンプル ポイントに転送され、ねずみ講のように他の近くのサンプル ポイントを回り続け、ダウンラインを展開し続けます。

回転する円は、円周するサンプル ポイントの数が事前に指定された値より少ないことがわかった時点で停止します。そして、開始点をコアポイント（A など）、停止する点を境界ポイント（B や C など）、転がる余地がない点を外れ値ポイント（N など）と呼びます。

密度に基づくこれの利点は何ですか?

kmeans クラスタリング アルゴリズムは、球状のクラスター、つまり固体のグループのみを処理できることがわかっています (これは、アルゴリズム自体が平均距離の計算に制限があるためです)。しかし、現実には、下の 2 つの図のように、リングや不規則な形状など、さまざまな形状が存在することがよくあります。このとき、従来のクラスタリング アルゴリズムは明らかに悲惨です。

そこで、サンプル密度の高いサンプルを 1 つのカテゴリにグループ化する必要があると考え、それが DBSCAN クラスタリング アルゴリズムです。

3. パラメータの選択

上記の赤い円が回転するプロセスには、DBSCAN アルゴリズムの 2 つのパラメータが含まれています。これらの 2 つのパラメータは指定が困難です。ここでは、一般的に受け入れられている指定方法を簡単に紹介します。

半径: 半径を指定するのが最も難しいです。半径が大きいと、囲まれる領域が多くなり、クラスターの数は少なくなります。逆に、クラスターの数が増えると、最終結果に影響します。このとき、K距離は半径rを設定すること、つまり突然変異点を見つけるのに役立ちます。例えば、上記の方法は受け入れられる方法ですが、面倒な場合もあります。ほとんどの人は、観察のために試してみるだけです。K距離を使用すると、観察するために多くの実験が必要になり、一度にこれらすべての値を選択するのは困難です。

MinPts: このパラメータは、囲まれたポイントの数であり、密度に相当します。通常、この値は小さいほど、複数回の試行が行われます。

4. DBSCANアルゴリズムの反復の可視化

海外には、DBSCAN 反復プロセスのグラフを動的に描画できる特に興味深い Web サイトがあります。

ウェブサイト: naftaliharris[1]

パラメータを設定したら、「GO!」をクリックするとクラスタリングが開始されます。

5. 一般的な評価方法：シルエット係数

クラスタリング アルゴリズムで最も一般的に使用される評価方法は、シルエット係数です。

サンプル i から同じクラスター内の他のサンプルまでの平均距離 ai を計算します。ai が小さいほど、サンプル i がクラスターにクラスター化される可能性が高くなります (ai はサンプル i とクラスター間の非類似度と呼ばれます)。

サンプル i から別のクラスター Cj 内のすべてのサンプルまでの平均距離 bij を計算します。これは、サンプル i とクラスター Cj 間の非類似度と呼ばれます。サンプル i のクラスター間非類似度として定義されます: bi=min(bi1,bi2,...,bik2);

例:

• siが1に近い場合、サンプルiのクラスタリングが妥当であることを意味します。
• si が -1 に近い場合、サンプル i は別のクラスターに分類される必要があることを意味します。
• siがほぼ0の場合、サンプルiは2つのクラスターの境界上にあることを意味します。

6. Python での DBSCAN クラスタリング アルゴリズムの実装

データをインポート:

 pandasをpdとしてインポートする
sklearn.datasetsからload_irisをインポートする
# データをインポートします。sklearn には iris データセットが付属しています
アイリス = load_iris().data
印刷(アイリス)

出力：

DBSCAN アルゴリズムの使用:

 sklearn.clusterからDBSCANをインポートする
 iris_db = DBSCAN(eps=0.6,min_samples=4).fit_predict(iris)
 # 半径を0.6、最小サンプルサイズを2に設定し、モデルをモデル化します
db = DBSCAN(eps=10, min_samples=2).fit(アイリス) 
  
 # 各カテゴリーの数を数える
カウント = pd.value_counts(iris_db,sort= True )
印刷(カウント)

視覚化：

 matplotlib.pyplot をpltとしてインポートします。
 plt.rcParams[ 'font.sans-serif' ] = [u'Microsoft YaHei' ] 
 
図、ax = plt.subplots(1,2、図のサイズ=(12,12)) 
 
 # クラスタリング後の結果を描画する
ax1 = ax[0]
 ax1.scatter(x=iris[:,0],y=iris[:,1],s=250,c=iris_db)
 ax1.set_title( 'DBSCAN クラスタリング結果' , fontsize=20) 
 
 # 実際のデータ結果を描画する
ax2 = ax[1]
 ax2.scatter(x=iris[:,0],y=iris[:,1],s=250,c=load_iris().target)
 ax2.set_title( '真の分類' 、フォントサイズ=20)
 plt.show()

上図からクラスタリング品質を観察することができますが、データ量が多い場合や指標の数が多い場合は観察が非常に面倒になります。

このとき、シルエット係数を使用して結果の品質を判断できます。クラスタリング結果のシルエット係数は S として定義され、クラスタリングが合理的かつ効果的であるかどうかを測る指標です。

クラスタリング結果のシルエット係数の値は[-1,1]の間です。値が大きいほど、同じ種類のサンプル同士が近くなり、異なる種類のサンプル同士が遠くなり、クラスタリング効果が高くなります。

シルエット係数とその他の評価関数は、sklearn.metrics モジュールで定義されています。sklearn の Silhouette_score() 関数は、すべてのポイントの平均シルエット係数を計算します。

 sklearnからメトリックをインポート
# 次の関数はシルエット係数を計算できます (sklearn は本当に強力なパッケージです)
スコア = metrics.silhouette_score(iris,iris_db)
スコア

結果: 0.364