「DBSCAN」について学ぶ（統計学 / 教師なし学習 / クラスター分析）

2023年5月13日

この記事では、統計学を初めて学ぶ筆者が、「教師なし学習」における「クラスター分析」の手法である「DBSCAN」について学んだ内容について記載しています。

学習には、Wikipediaの「DBSCAN」の記事を参考にし、Pythonのプログラミングにも触れ、理解を深めました。

プログラミングには、機械学習ライブラリのscikit-learnを使用しました。

この記事は、他の人が参考にできるよう、わかりやすく書くことを心がけました。

教師なし学習

教師なし学習は、データからパターンや構造を見つけ出すための機械学習の手法です。データにはラベルや目的変数がなく、機械自身が学習し、データの背後にある構造を抽出します。例えば、ある企業の顧客データを教師なし学習で解析することで、似たような傾向を持つグループや、注目すべき特徴を抽出することができます。

一方、教師あり学習は、データにラベルや目的変数がある場合に用いられます。目的変数と予測値との誤差を最小化するようにモデルを構築し、未知のデータに対して予測を行います。例えば、画像認識や音声認識などが教師あり学習の例です。

クラスター分析は、教師なし学習の一例で、似た特徴を持つデータをグループ化する手法です。例えば、ある商品を顧客がどのような特徴で分類しているかをクラスター分析で解析することで、市場セグメンテーションを行うことができます。

教師なし学習とは、機械学習の手法の一つである。「出力すべきもの」があらかじめ決まっていないという点で教師あり学習とは大きく異なる。データの背後に存在する本質的な構造を抽出するために用いられる。

教師あり学習は、その「出力すべきもの」も入力として与える手法であり、データの背後に存在する本質的な構造を抽出するよりむしろ、思い通りの出力を再現する機械の構成に用いられる。

具体的な例として以下のようなものがある。

・クラスター分析

・主成分分析

・ベクトル量子化

・自己組織化マップ

教師なし学習

クラスター分析

クラスター分析とは、データを自動的に分類する方法の一つです。例えば、マーケティング分野で、顧客のデータをクラスター分析することで、似たような傾向を持つ顧客をグループ化し、そのグループごとに商品の販売戦略を立てたり、顧客へのアプローチ方法を変えることができます。

クラスタリング、クラスタ解析、クラスター分析は、データ解析手法（特に多変量解析手法）の一種。教師なしデータ分類手法、つまり与えられたデータを外的基準なしに自動的に分類する手法。また、そのアルゴリズム。

データ・クラスタリング

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）は、密度に基づくクラスタリングアルゴリズムです。空間内に存在する点の集合が与えられた場合、密集している点はグループ化され、密度の低い領域にある点は外れ値として扱われます。つまり、同じグループに属する点はお互いに近く、密度が高く、別のグループに属する点とは距離が離れていることが期待されます。DBSCANは、最も一般的なクラスタリングアルゴリズムの1つです。

DBSCAN (Density-based spatial clustering of applications with noise ) は、1996 年に Martin Ester, Hans-Peter Kriegel, Jörg Sander および Xiaowei Xu によって提案されたデータクラスタリングアルゴリズムである。これは密度準拠クラスタリングアルゴリズムである。ある空間に点集合が与えられたとき、互いに密接にきっちり詰まっている点をグループにまとめ(多くの隣接点を持つ点、en:Fixed-radius_near_neighbors)、低密度領域にある点(その最近接点が遠すぎる点)を外れ値とする。DBSCAN は最も一般的なクラスタリングアルゴリズムのひとつであり、科学文献の中で最も引用されている。

DBSCAN

概要

DBSCANは、密度ベースのクラスタリングアルゴリズムで、空間内の点の集合が与えられたときに密集している点をグループ化し、密度の低い領域にある点を外れ値として扱います。

具体的には、距離ε以内に少なくともminPts個の点を持つ点をコア点として定義し、コア点から距離ε以内に到達可能な点を到達可能点としてクラスタリングします。コア点から到達可能な到達可能点も同じクラスタに含めます。一方、どのコア点からも到達できない点は外れ点として扱い、クラスターに属さないノイズとして扱います。

例えば、街の人口分布をDBSCANでクラスタリングすると、コア点は人口密集地となり、到達可能点は周辺地域となります。外れ点は、どの密集地からも遠く離れた住宅地や、人口が少ない田舎地などになります。

ある空間内にある、クラスタリングしたい点集合を考える。 ε はある点からの半径を表すパラメータとする。DBSCAN クラスタリングの目的として、点は、コア点(core points)、(密度)到達可能点、外れ値に分類される。以下のように行う。

・点 p を含め、点 p から距離 ε 以内に少なくとも minPts 個の点があれば、点 p はコア点である。

・点 q がコア点 p から距離 ε 以内にあれば、q は p から「直接到達可能」であるという。

・各 pi+1 が pi から直接到達可能であり、p1 = p かつ pn = q であるパス p1, …, pn があれば、q は p から「到達可能」である。ここでパス上のすべての点は、 q が例外である可能性があるが、コア点で無ければならない。

・他のどの点からも到達可能でないすべての点は外れ値である。

今、p がコア点であれば、点p から到達可能なすべての点(コア点または非コア点)と一緒にクラスタを形成する。各クラスタは少なくともひとつのコア点を含む。非コア点はあるクラスタの一部となるが、非コア点はその"端"を形成する。非コア点はより多くの点に到達するのに使用できないためである。

DBSCAN

DBSCANアルゴリズムにおいて、最も重要なパラメータの一つであるminPtsを4と設定した場合の例を説明します。点Aと他の赤い点はコア点であり、半径ε以内に少なくとも4つの点を持っています。点BとCはコア点ではありませんが、赤いコア点から距離ε以内にあり、到達可能な点であるため、A、B、Cは同じクラスタに属しています。一方、点Nはどのコア点からも距離ε以内にありません。そのため、Nは外れ値であり、クラスタに属さず、ノイズとして扱われます。

 

上図において、minPts = 4 である。点 A およびその他の赤点はコア点である。その理由は、半径 ε でこれらの点を囲んでいる領域は少なくとも(その点自身を含めて) 4 つの点を含んでいるからである。上図のコア点はすべて互いに到達可能であり、単一のクラスタを形成する。点 B および C はコア点ではない。しかし、A から(他のコア点を介して)到達可能であり、それゆえこのクラスタに属す。点 N はコア点でなければ密度到達可能点でもないので、ノイズ点である。

アルゴリズム

DBSCANは、密度ベースのクラスタリングアルゴリズムで、2つのパラメータである「ε(eps)」と「minPts」を使用します。

まず、まだ訪れたことのない任意の出発点から処理を開始します。この点がコア点であるかどうかを判断し、コア点として分類された場合には、クラスタリング処理を開始します。

コア点でない場合は、外れ点として分類しますが、後に別のコア点の到達可能点として再分類される可能性があります。

クラスタリング処理では、コア点から距離ε以内の点を探索し、クラスタに追加します。また、ε以内の点について、コア点か到達可能点かを判断し、コア点であればε以内の点を探索し、クラスタに追加します。

この処理を、クラスタに追加すべき点がすべて見つかるまで繰り返します。その後、まだ訪問していない新しい点についても、同様の処理を繰り返します。

外れ点はクラスターに属さず、ノイズとして扱います。

DBSCAN は 2 つのパラメータを必要とする。ε (eps) および密領域を形成するのに必要となる点の最小数である(minPts)。アルゴリズムでは、まだ訪れていない任意の開始点から処理を始める。この点の ε 近傍を検索し、それが十分に多くの点を含んでいるなら、クラスタが開始される。そうでなければ、その点はノイズ点とラベル付けされる。注意として、この点は後に、異なる点から見て閾値以上の点を含んだ ε 近傍の一部となり、それゆえあるクラスタの一部になるかもしれない。
ある点があるクラスタの密部分であることが判明した場合、その ε 近傍もまたそのクラスタの一部である。それゆえ、ε 近傍内にあるすべての点が加えられ、それらが稠密であるときにはそれら自身のε-近傍も同様に加算される。この過程は密度連結クラスタ(density-connected cluster)が完全に発見されるまで続く。そして、まだ訪問されていない新しい点が検索および処理され、さらなるクラスタまたはノイズが発見される。
アルゴリズムは以下の元々投稿された命名法に従う擬似コードのようにして導かれる。

DBSCAN(D, eps, MinPts) {
   C = 0
   for each point P in dataset D {
      if P is visited
         continue next point
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else {
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)
      }
   }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts { 
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster
         add P' to cluster C
   }
}

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

DBSCAN

利点

  • クラスタ数を事前に指定する必要がないこと。k-meansと異なり、クラスタ数を推測する必要がありません。
  • どんな形のクラスターも見つけることができます。他のクラスターに完全に囲まれているクラスターを見つけることも可能です。この点はk-meansと比較しても優れています。
  • ノイズの概念を持っており、外れ値を扱うことができます。このようなデータを扱う場合には非常に便利です。
  • 必要なパラメータは2つだけであり、処理の順番にも影響されません。このため、比較的シンプルなパラメータチューニングで良い結果を得ることができます。
  1. k平均法とは対照的に、DBSCAN は事前にデータのクラスタ数を明示的に指定する必要は無い。
  2. DBSCAN は任意の形状のクラスタを見つけることができる。DBSCAN は他のクラスタによって完全に囲まれた(しかし接続していない)クラスタさえ見つけることができる。MinPts パラメータのため、いわゆる single-link 効果(異なるクラスタが細い線によって結ばれてしまうこと)は減少している。
  3. DBSCAN はノイズという概念を持っており、外れ値に対してロバストである。
  4. DBSCAN に必要なパラメータは 2 つだけであり、たいていはデータ点の順序に影響を受けない。(しかし、2 つの異なるクラスタのどちらからも端に位置する点は、点の順序が変えられ、クラスタの割り当てが同型写像までしかユニークではないならば、どちらのクラスタに属するかが入れ替わるかもしれない。)
    DBSCAN は、たとえばR*木を使用するような region query を加速させることができるデータベースでの使用に対して設計されている。
  5. minPts および ε パラメータは、もしデータがよく理解されているならば、ドメインの専門家によって設定できる。

DBSCAN

欠点

  • εとminPtsによるクラスタリング結果が必ずしも1つに決まらないことがあるため、クラスタリングの処理順序によって、どちらかのクラスタになることがあります。ただし、このような状況はあまり起こらず、結果への影響も小さいです。コア点と外れ点については、結果は1つに決まります。
  • 密度の差が大きいデータをクラスタリングすることができないため、適切なεとminPtsの組み合わせを選択することができない場合があります。
  • クラスタリング対象とその間の距離がよくわからない場合、意味のある距離εを選択することが困難です。

DBSCAN は完全に決定論的というわけではない。ひとつよりも多くのクラスタから到達できる境界点は、データが処理される順序に依存して、どちらのクラスタにもなることができる。幸運にも、この状況は頻繁には起きない。また、クラスタリング結果に与える影響は小さい。コア点とノイズ点に関しては、DBSCAN は決定論的である。DBSCAN*は境界点をノイズとして扱う変種であり、この方法では、密度連結成分(density-connected components)のより一貫した統計的解釈と同様に、完全に決定論的な結果となる。
DBSCAN の質は、関数 regionQuery(P, ε) で使用される距離尺度に依存する。最も一般的に使用される尺度はユークリッド距離である。特に、高次元データに対しては、この尺度はいわゆる「次元の呪い」のために、ほとんど使えないものとなってしまい、ε の適切な値を見つけるのは困難となる。しかしこの欠点は、ユークリッド距離に基づく他のアルゴリズムにも当てはまる。
DBSCAN は密度に大きな違いのあるデータ集合をクラスタリングできない。すべてのクラスタに対して適切なminPts-εの組み合わせを選ぶことができないためである。
データおよびスケールがよく理解されていないならば、意味のある距離閾値 ε を選ぶことは困難である。

DBSCAN

Pythonプログラミング

「DBSCAN」をイメージしやすいようPythonでのプログラミングについても学びます。

scikit-learn トイデータセット

機械学習ライブラリscikit-learnに用意されている「トイデータセット」を使います。トイデータセットは、機械学習の問題を解くためのサンプルデータセットのことで、いくつかの種類が用意されています。例えば、Iris（アヤメ）の花の特徴から、その種類を分類する問題を解くための「irisデータセット」や、ボストン市の住宅価格に関するデータを用いて、住宅価格を予測する問題を解くための「bostonデータセット」などがあります。

Irisデータセットは、Setosa、Versicolour、Virginicaの3種類のアヤメの花のデータが含まれており、各種類について50個のサンプルがあります。このデータセットには、がく片の長さや幅、花びらの長さや幅、そしてアヤメの種類という4つの特徴量が含まれています。

アヤメの花の4つの特徴量（花弁の長さや幅、がく片の長さや幅）を使って、DBSCANを使い、アヤメをグループ（クラスター）に分けることができます。

scikit-learnにはいくつかの小さな標準データセットが付属しており、外部のウェブサイトからファイルをダウンロードする必要はありません。

これらは以下の関数を使って読み込むことができます。

load_boston()　:　load_boston は 1.0 で非推奨となり、1.2 で削除される予定である。

load_iris()　:　アヤメのデータセット(分類)をロードして返す。

load_diabetes()　:　糖尿病のデータセット(回帰)をロードして返す。

load_digits()　:　数字のデータセット(分類)をロードして返す。

load_linnerud()　:　身体運動のデータセットをロードして返す。

load_wine()　:　ワインのデータセット(分類)をロードして返す。

load_breast_cancer()　:　ウィスコンシン州の乳がんのデータセット（分類）をロードして返す。7.1. Toy datasetsts

関連記事

「アヤメのデータセット」について学ぶ（scikit-learn /トイデータセット）

「糖尿病のデータセット」について学ぶ（scikit-learn /トイデータセット）

「数字のデータセット」について学ぶ（scikit-learn /トイデータセット）

「身体運動のデータセット」について学ぶ（scikit-learn /トイデータセット）

「ワインのデータセット」について学ぶ（scikit-learn /トイデータセット）

「ウィスコンシン州の乳がんのデータセット」について学ぶ（scikit-learn /トイデータセット）

アヤメのデータセット

アヤメのデータセットは、機械学習における代表的なデータセットの1つであり、サンプルデータの中でも特に有名なものの1つです。

アヤメのデータセットには、ヒオウギアヤメ(Iris-Setosa)、アイリス・バージカラー(Iris Versicolour)、アイリス・ヴァージニカ(Iris Virginica)の3種類のアヤメが含まれており、各々50件のデータがあります。データには、「がく片の長さ」、「がく片の幅」、「花びらの長さ」、「花びらの幅」といった4つの属性があり、また3種のアヤメの分類に関するデータも含まれています。

Iris Setosa （ヒオウギアヤメ）

アラスカ、メイン、カナダ（ブリティッシュコロンビア、ニューファンドランド、ケベック、ユーコンなど）、ロシア（シベリアなど）、アジア北東部、中国、韓国、日本など北極海を越えて広く分布する根生葉の多年草です。

茎は高く伸び、葉は中緑色、花は紫、紫紺、青、ラベンダー色です。また、ピンクや白の花を咲かせる植物もあります。

Irissetosa1.jpg
Iris Setosa (ヒオウギアヤメ)

Iris Versicolour （アイリス・バージカラー）

北アメリカ、アメリカ東部とカナダ東部に自生するアヤメの一種です。スゲ草地や湿地、川岸や海岸に普通に見られます。

特異形質バージカラー(versicolor)は「様々な色彩の」という意味です。

Blue Flag, Ottawa.jpg
Iris Versicolour (アイリス・バージカラー)

Iris Virginica （アイリス・ヴァージニカ）

北アメリカ東部原産の多年草です。アメリカ南東部のフロリダ州からジョージア州にかけての海岸平野によく見られます。

Iris virginica 2.jpg
Iris Virginica (アイリス・ヴァージニカ)
関連記事

「アヤメのデータセット」について学ぶ（scikit-learn /トイデータセット）

プログラム

DBSCANを使ってアヤメのデータセットをクラスター分析し、アヤメの種類とクラスター分析の結果をピボットテーブルで比較します。

import pandas as pd
from sklearn.datasets import load_iris
from sklearn.cluster import DBSCAN

# アヤメのデータセットを読み込む
iris = load_iris()

# 特徴量データをDataFrameに変換する
df = pd.DataFrame(iris.data, columns=iris.feature_names)

# DBSCANでクラスタリングを行う
dbscan = DBSCAN(eps=0.5, min_samples=5).fit(df)

# クラスタリング結果をDataFrameに追加する
df['cluster'] = kmeans.labels_

# アヤメの種類情報をDataFrameに追加する
df['species'] = [iris.target_names[i] for i in iris.target]

# 結果をピボットテーブルで表示する
result = pd.pivot_table(df, values='sepal length (cm)', index='species', columns='cluster', aggfunc='count')

print(result)

実行結果

k-means法によって、アヤメの種類がsetosaに分類されるものはクラスタ-1とクラスタ0に、アヤメの種類がversicolorに分類されるものはクラスタ-1とクラスタ1に、アヤメの種類がvirginicaに分類されるものはクラスタ-1とクラスタ1に分類されたことがわかります。

cluster       -1     0     1
species                     
setosa       1.0  49.0   NaN
versicolor   6.0   NaN  44.0
virginica   10.0   NaN  40.0

プログラムの説明

import pandas as pd
from sklearn.datasets import load_iris
from sklearn.cluster import DBSCAN

pandasライブラリをpdという名前でインポートします。

sklearn.datasetsライブラリからirisデータセットをインポートします。

sklearn.clusterライブラリからDBSCANクラスをインポートします。

# アヤメのデータセットを読み込む
iris = load_iris()

# 特徴量データをDataFrameに変換する
df = pd.DataFrame(iris.data, columns=iris.feature_names)

irisデータセットを読み込み、iris変数に代入します。

irisの特徴量データをiris.dataから取得し、列名にiris.feature_namesを指定してDataFrameに変換し、df変数に代入します。

# DBSCANでクラスタリングを行う
dbscan = DBSCAN(eps=0.5, min_samples=5).fit(df)

# クラスタリング結果をDataFrameに追加する
df['cluster'] = kmeans.labels_

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）アルゴリズムを使用して、与えられたデータセットをクラスタリングします。DBSCANは、k-meansなどの他のクラスタリング手法とは異なり、クラスタ数を事前に指定する必要がありません。代わりに、密度に基づいてデータポイントをクラスタリングします。

引数のepsは、クラスタリングを行う際の半径の最大値。この半径内にあるデータポイントは同じクラスタに属します。適切な値を選択することが重要で、データセットによって異なります。min_samplesは、クラスタとして認めるための最小データポイント数。この数未満のデータポイントはノイズとして扱われます。適切な値を選択することが重要で、データセットによって異なります。

fit()関数は、引数で渡されたデータフレームをクラスタリングします。

クラスタリング対象のデータセットに複数の特徴量（花弁の長さや幅、がく片の長さや幅）がある場合は、各特徴量の値に基づいて距離を計算します。具体的には、ユークリッド距離（2つの点間の距離を表す方法の1つで、座標平面上において2つの点間を直線で結んだときの長さ）などの距離尺度を使用して、各データ点間の距離を計算します。そして、この距離に基づいて、クラスタの中心点を求めます。

つまり、各特徴量がデータポイントの座標軸となり、多次元空間上で距離を計算していると考えることができます。そのため、データセットに含まれる特徴量のスケールが異なる場合は、各特徴量に対して適切な前処理を行う必要があります。例えば、正規化や標準化を行うことで、異なるスケールの特徴量を均一化し、適切なクラスタリングを行うことができます。

クラスタリングが完了したら、各データポイントのラベル（所属するクラスタの番号）を取得できます。

dfデータフレームに、クラスター番号を表すcluster列を追加し、それにkmeans.labels_の値を代入します。

# アヤメの種類情報をDataFrameに追加する
df['species'] = [iris.target_names[i] for i in iris.target]

irisのターゲットデータをiris.targetから取得し、iris.target_namesからアヤメの種類を取得して、それらをリストとして作成し、dfデータフレームにspecies列として追加します。

# 結果をピボットテーブルで表示する
result = pd.pivot_table(df, values='sepal length (cm)', index='species', columns='cluster', aggfunc='count')

print(result)

dfデータフレームを使って、species列を行、cluster列を列として、’sepal length (cm)’列の値を集計してピボットテーブルを作成し、result変数に代入します。

pd.pivot_table()は、データフレームをピボットテーブルに変換する関数です。引数には以下のように指定します。

  • df: 変換するデータフレーム
  • values: 集計する値の列
  • index: 行にくる特徴量列
  • columns: 列にくる特徴量列
  • aggfunc: 集計関数

この場合、dfはDBSCANによってクラスタリングされた各サンプルに対して、アヤメの種類がどのクラスタに属するかを示すラベルとともに、各特徴量の値が含まれたデータフレームです。valuesには集計する値の列を指定しています。この場合、1つ目の特徴量であるsepal length (cm)列を指定しているため、resultは各アヤメの種類とクラスターの組み合わせにおけるsepal length (cm)の値の件数を示すピボットテーブルになります。indexには行にくる特徴量列を指定しています。この場合、アヤメの種類を指定しています。columnsには列にくる特徴量列を指定しています。この場合、クラスターのラベルを指定しています。aggfuncには集計関数を指定しています。この場合、countを指定しているため、各セルには該当するアヤメの種類とクラスターの組み合わせにおけるsepal length (cm)の値の件数が表示されます。

クラスタリングDBSCAN,Python,クラスター分析,クラスタリング,教師なし学習,統計学

Posted by Yamada