[Clustering] DBSCAN(Density-Based Clustering of Application with Noise)

こんにちは!
今日は、クラスタアルゴリズムでのDBSCANの学習を記録します.データを分析して使用しましたが、Wikipediaをより正確に理解し、再記録します.
DBSCANは、2014年のデータマイニング大会ACM SIKDDでTest of Time Awardを取得することで性能認証を取得するアルゴリズムです!複雑な名前とは異なり、非常に直感的で簡単なアルゴリズムです.我々の目標は,基本概念から逐次漸進し,簡単な例に適用しようとすることである.

Preliminary

DBSCANを紹介する前に、いくつかの必要な概念を紹介します.
まず.ϵ\epsilonϵパラメータと呼ばれ、ある点で隣接する領域の半径を指定します.また、minPtsminPtsminPtsは、構成コアの最小点数である.△今スキップして、後で説明します.

コアポイント:任意のポイントpppϵ\epsilonϵ 距離内に存在する点には少なくとも1つのminptsminptsminpts点がある.(ポイントpppを含む数.)

直接pppから:コアポイントpppϵ\epsilonϵ ストリートポイント

ppp:p 1(=p)p 1(=p)p 1(=p)からpn(=q)pn(=q)pn(=q)pn(=q)pn(=q)の経路が(pi+1 p i+1}pi+1)pip ipiから直接到達する場合、qqはppp到達と呼ぶ.

Noise:どこにも行けません.(Core Pointは常に可能です.)

Density-Based Clustering

ポイントpppがコアポイントである場合、ポイントpppの到達可能なポイントを含むクラスタが作成されます.各クラスタは、少なくとも1つのコアポイントと1つの到達可能ポイントから構成されます.ここで,非コアポイントは他のポイントに接続されなくなり,クラスタの「edge」となる.(クラスタ内の最コーナーポイント)
上図はWikipediaが提供した図で、DBSCANクラスタの様子をよく示しています!

Aで示す赤い点はCore Pointです

BとCは各コアポイントではなく、コアポイントに到達できる「edge」である.

NはNoiseになります.

赤い点と黄色い点が群れになっている.
これらの密度ベースのクラスタリングは、比較的自由な形状のクラスタをよりよくキャプチャするのに役立ちます.次の図は、さまざまなタイプのクラスタをうまくキャプチャできるDBSCANで検索した例を示しています.

まとめると、コアポイントを構成する半径と最小点の数です.ϵ,  minPts\epsilon,\; minPtsϵ,minptsは、距離を計算する距離メトリックを与えるだけでDBSCANを実行できます.
従来のクラスタアルゴリズムとは異なり、DBSCANの利点は、クラスタの数を決定する必要がないことです.個人的にはϵ\epsilonϵ 選択してminPtsminPtsminPtsを使用すると、クラスタの数が変更されます.ϵ\epsilonϵ とminptsminptsminptsの選択がクラスタ数の選択に取って代わっていると思います.
また、他のクラスタアルゴリズムとは異なり、Noiseが検索されているため、Outlierを検出するためにも使用されます.

Example

DBSCANをiris dataに使用する非常に簡単なPythonコードです.

from sklearn.cluster import DBSCAN 
from sklearn import datasets
import numpy as np
import matplotlib.pyplot as plt

iris = datasets.load_iris()

data = iris["data"]

labels = iris["target"]

DBSCAN_clust  = DBSCAN(eps = 0.4, min_samples = 4)
DBSCAN_clust.fit(data)

fig, ax = plt.subplots(1, 2)
fig.set_size_inches((12, 4)) 
ax[0].scatter(data[:,2], data[:,3], c = labels)
ax[1].scatter(data[:,2], data[:,3], c = DBSCAN_clust.labels_)

右側の図の紫色の点はNoise点です.
気になるところや間違ったところがあればメッセージをお願いします!良い一日をお過ごしください.