scikit-learnのクラスタリングアルゴリズムのDBSCAN

7036 ワード

アルゴリズムフロー


DBSCAN(Density-Based Spatial Clustering of Applications with Noise)アルゴリズムは、クラスタリングを低密度領域で区切られた高密度領域と見なす.コアサンプル:データセットのサンプルで、少なくともmin_が存在します.samplesの他のサンプルはeps距離範囲にあり、これらのサンプルはコアサンプルの隣接neighborsとして定められている.
1、すべてのコアサンプルを計算する;2、コアサンプルの集合の中でランダムに1つのコアサンプルを選択し、そのすべてのneighbors(隣接サンプル)のコアサンプルを検索し、それから彼ら(新しく取得したコアサンプル)のneighbors(隣接サンプル)のコアサンプルを検索し、この過程に戻る.3、ステップ2を経て、コアサンプルのセットとコアサンプルに近い非コアサンプルのセット(コアサンプルの隣接サンプル)を含むクラスタが得られた.すべてのコアサンプルがクラスクラスタに属するまで、手順2、3を繰り返します.
定義によれば、任意のコアサンプルはクラスタリングの一部であり、コアサンプルではなく、任意のコアサンプルとの距離がepsより大きいサンプルは異常値と見なされる.

アルゴリズムの長所と短所


利点:1、任意の形状の稠密なデータセットをクラスタリングすることができ、相対的に、K-Meansのようなクラスタリングアルゴリズムは一般的に凸データセットにしか適用されない.2、クラスタリングと同時に異常点を発見することができ、データセットの異常点に敏感ではない.欠点:1、サンプルセットの密度が不均一であれば、クラスタリング品質が悪い.2、サンプルセットが大きい場合、クラスタリング収束時間が長い場合、最近隣接している場合に確立されたKDツリーまたは球ツリーを検索する規模制限を改善することができる.3、パラメトリックパラメータは従来のK-Meansのようなクラスタリングアルゴリズムに比べてやや複雑で、主に距離閾値eps、近傍サンプル数閾値min_samples連合パラメータは、異なるパラメータの組み合わせが最後のクラスタリング効果に大きな影響を及ぼす.

sklearnのパラメータ


[class sklearn.cluster.DBSCAN] eps=0.5: float,ϵ-隣接領域の距離しきい値;min_samples=5:int、サンプルポイントがコアオブジェクトになるために必要なϵ-隣接領域のサンプル数のしきい値;以上の2つのパラメータは連合してパラメータを調整しなければならない.
metric=’euclidean’:string,or callable,最近隣接距離メトリックパラメータ,使用可能な距離メトリック;
metric_params=None:dict、距離メトリックのパラメータ;
Algorithm=’auto’:{‘auto’,‘ball_tree’,‘kd_tree’,‘brute’},最近隣接探索アルゴリズムパラメータ,‘brute’は強力に実現され,‘kd_tree’,‘brute’}tree’はKDツリー実装,‘ball_tree’は球樹で実現され、「auto」は上の3つのアルゴリズムの中でバランスをとり、最もフィットする最適なアルゴリズムを選択する.入力サンプルフィーチャーがまばらな場合、どのアルゴリズムを選択しても最後にscikit-learnは蛮力で「brute」を実現します.一般的にはデフォルトの「auto」を使えば十分ですが、データ量が大きい場合やフィーチャーが多い場合は「kd_tree'または「ball_tree’;
leaf_size=30:int,最近接探索アルゴリズムパラメータは,KDツリーやボールツリーを用いた場合に,サブツリーのリーフノード数を停止する閾値である.この値が小さいほど、生成されたKDツリーまたは球ツリーが大きくなり、層数が深くなるほど、樹立時間が長くなり、逆に、生成されたKDツリーまたは球ツリーが小さくなり、層数が浅くなり、樹立時間が短くなります.この値は一般的にアルゴリズムの実行速度と使用メモリサイズにのみ影響するため、一般的にはそれを無視することができます.
p=None:float、最近接距離メトリックパラメータは、ミンコフスキー距離と重み付きミンコフスキー距離のp値の選択にのみ使用され、p=1はマンハッタン距離、p=2はヨーロッパ距離であり、デフォルトのヨーロッパ距離を使用する場合はこのパラメータを管理する必要はありません.
n_jobs=1:int、マルチスレッド;-1:すべてのcpuを使用します.1:マルチスレッドを使用しない;-2:n_の場合jobs<0、(n_cpus+1+n_jobs)個のcpuが使用されるので、n_jobs=-2の場合、すべてのcpuのうち1つだけが使用されません.

サンプルコード


Demo of DBSCAN clustering algorithm
print(__doc__)

import numpy as np

from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler


# #############################################################################
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
                            random_state=0)

X = StandardScaler().fit_transform(X)

# #############################################################################
# Compute DBSCAN
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_

# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
      % metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
      % metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
      % metrics.silhouette_score(X, labels))

# #############################################################################
# Plot result
import matplotlib.pyplot as plt

# Black removed and is used for noise instead.
unique_labels = set(labels)
colors = [plt.cm.Spectral(each)
          for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        # Black used for noise.
        col = [0, 0, 0, 1]

    class_member_mask = (labels == k)

    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=14)

    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=6)

plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()