DBSCAN

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

2014 年、このアルゴリズムは主要なデータマイニングカンファレンスの KDD にて、the test of time award (理論および実践にてかなりの注目を集めたアルゴリズムに与えられる賞) を受賞した。[3]

準備[編集]

クラスタリングされるべきある空間の点集合を考える。DBSCAN クラスタリングの目的として、点は、コア点(core points)、(密度)到達可能点、外れ値に分類される。以下のように行う。

  • p がもし、p を含め、距離 ε(ε は p からの近傍の最大半径)以内に少なくとも minPts の点があれば、その点はコア点である。
  • q がもし、各 pi+1pi から直接到達可能(パス上のすべての点は、 q の可能な例外を持つ、コア点で無ければならない。)な、p1 = p かつ pn = q であるパス p1, ..., pn があれば、qp から到達可能である。
  • 他のどの点からも到達可能でないすべての点は外れ値である。

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

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

到達可能性は対称関係ではない。というのも、定義により、距離にかかわらず、非コア点から到達可能な点は存在しないためである(そして、非コア点は到達可能であってもよいが、それから到達されるものは無い)。それゆえ、DBSCAN によって発見されるクラスタの範囲を形式的に定義するために、連結性の新たな概念が必要とされる。点oから2点pとqへ密度到達可能(density-reachable)であるような点oが存在するとき、pとqは 密度連結(density-connected) である。密度連結(density-connected) は対称的である。 クラスタは、次の 2 つの特性を満たす。

  1. クラスタ内のすべての点は、相互に密度連結(density-connected) である。
  2. ある点がクラスタのどの点からも密度到達可能(density-reachable) ならば、それもまたクラスタの一部である。

アルゴリズム[編集]

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

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)

このアルゴリズムは、"expandCluster" サブルーチンの内容(これは 1 箇所からのみよばれる)のインライン化 および、点ごとの "すでに訪れた点" および "クラスタ C に所属する" ロジックを統合することによって、単純にすることができる。これらの単純化は、元々投稿されたバージョンを反映するために、上記の擬似コードでは省略されている。また、regionQuery関数は、ローカル密度推定でまだカウントされている限り、訪問されるべき点のリスト内でPを返す必要はない。

複雑性[編集]

DBSCAN はデータベースの各点を訪れる。複数回訪れることもある(たとえば、異なるクラスタへの候補として)。しかし、実践の考慮のため、時間計算量はたいてい regionQuery の呼び出しの回数によって支配される。DBSCAN は各点でそのようなクエリをまさに 1 度だけ実行し、O(log n) で近隣クエリ(en:Fixed-radius_near_neighbors)を実行するインデックス構造が使用されるならば、O(n log n) の全体平均のランタイム複雑性が獲得される(パラメータ ε が意味のある中で選ばれたならば。すなわち、平均して O(log n) の点が返される場合ならば)。加速させるようなインデックス構造を使用しない場合、または縮退データ(たとえばすべての点が ε より小さい距離内にある)の場合は、その最悪計算時間は O(n²) のままである。サイズ (n²-n)/2 の距離行列は距離の再計算を回避するために出現しうるが、これは O(n²) のメモリを必要とする。一方、DBSCAN の非行列に基づく実装はわずか O(n) のメモリを必要とする。

DBSCAN は非線形分離されるクラスタを見つけ出すことができる。このデータセットは、k-means や 混合ガウシアン EM アルゴリズムでは十分にクラスタリングされない。

利点[編集]

  1. k平均法とは対照的に、DBSCAN は事前にデータのクラスタ数を明確に指定する必要は無い。
  2. DBSCAN は任意の形状のクラスタを見つけることができる。DBSCAN は異なるクラスタによって完全に囲まれた(しかし接続していない)クラスタさえ見つけることができる。MinPts パラメータのため、いわゆる single-link 効果(異なるクラスタが点の細線によって結ばれる)は減少している。
  3. DBSCAN はノイズの考え方を持っており、外れ値に対してロバストである。
  4. DBSCAN はちょうど 2 つのパラメータを必要とし、たいていはデータ点の順序に影響を受けない。(しかし、もし点の順序が変えられ、クラスタの割り当てが同型写像までしかユニークではないならば、2 つの異なるクラスタのエッジに位置する点は、クラスタの関係を交換するかもしれない。)
  5. DBSCAN は、たとえばR*木を使用するような region query を加速させることができるデータベースでの使用に対して設計されている。
  6. minPts および ε パラメータは、もしデータがよく理解されているならば、ドメインエキスパートによって設定できる。

欠点[編集]

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

これらの問題を扱うためのアルゴリズムの修正に関する拡張については下記のセクションを参照すること。

パラメータ評価[編集]

どのデータマイニングタスクもパラメータの問題がある。どのパラメータも明確な方法でアルゴリズムに影響を与える。DBSCAN では、パラメータ ε および minPts が必要とされる。パラメータはユーザーによって指定されなければならない。理想的には、ε の値は解くべき問題によって与えられ(たとえば、物理的な距離)、minPts は望まれる最小クラスターサイズである。[注釈 1]

  • minPts - 大まかなやり方では、最小の minPts はデータセットの次元 D から引き出され、minPts ≥ D + 1 である。minPts = 1 の低い値は意味を成さない。どの点もそのままクラスタであるからである。minPts ≤ 2 では、結果は single link metric での階層クラスタリングと同じになり、デンドログラム(dendrogram)は高さ ε でカットされる。それゆえ、minPts は少なくとも 3 に選ばれなければならない。しかし、より大きい値はたいていの場合ノイズを持ったデータ集合に対してより有効であり、かなりのクラスタを生じるだろう。データ集合が大きくなれば、minPts の値はより大きく選ばれるべきである。
  • ε - ε の値は、k距離グラフ を用い、 k = minPts の最近傍への距離をプロットすることで選ばれる。ε が良い値であると、このプロットが強く結ばれている。ε が非常に小さい値に選ばれると、データの大部分はクラスタリングされない。一方、大きな値が選ばれると、クラスタは併合され、オブジェクトの大多数は同一のクラスタにあることになる。一般に、小さな ε 値が好ましく、大まかにいって点の小片がお互いにこの距離内にあるべきである。
  • 距離関数 - 距離関数の選択は ε の選択に密に結合しており、結果に大きな影響を与える。一般に、パラメータ ε が選ばれる前に、データセットに対する類似度の合理的な尺度を最初に特定することが必要である。

OPTICS は、パフォーマンスに大部分の影響を与える最大値で ε を置換した、DBSCAN の一般化と見なされる。minPts は、発見される最小のクラスターサイズとなる。このアルゴリズムは DBSCAN よりもずっとパラメータ化しやすい一方で、結果を使うのにはもうすこし困難がある。たいてい、DBSCAN が生成する単純なデータパーティショニングの代わりに、階層クラスタリングを生成するためである。 最近、DBSCAN の元々の著者の一人が DBSCAN と OPTICS を再訪し、階層 DBSCAN (HDBSCAN*)[4]の洗練バージョンを投稿した。これはもはや境界点の考え方をもっていない。

拡張[編集]

一般化 DBSCAN (GDBSCAN) [5][6] は同一著者による任意の"近隣"("neighborhood")および"密度"("dense")の述語に対する一般化である。ε および minPts パラメータは元々のアルゴリズムから除外され、述語(predicates)に移る。たとえば、ポリゴンデータでは、"近隣"は任意の交差するポリゴンである。一方、密度(density predicate)はオブジェクト数の代わりにポリゴンの領域を使用する。 DBSCAN アルゴリズムへの様々な拡張が提案されてきた。これには、並列化、パラメータ推定、不確かなデータのサポートに対する手法を含む。基本的な考え方は OPTICS アルゴリズム による階層クラスタリングに拡張されてきた。DBSCAN もまた PreDeConSUBCLU英語版 のような部分空間クラスタリングアルゴリズムの一部として使用されてきた。HDBSCAN [4] はOPTICS よりも高速なDBSCAN の階層バージョンである。そこから、最も卓越したクラスタを構成するフラットなパーティションがその階層から抽出される。[7]

利用性[編集]

このアルゴリズムの様々な実装があり、大きなパフォーマンスの違いが示されてきた。最も早いものでは 1.4 秒で終わるが、最も遅いものでは 13803 秒かかる。[8]この差異は実装の質、言語、コンパイラの違い、またアクセラレーションのためのインデックス(索引)の使用による。

  • Apache_Commons Math は 2 次のオーダーで動作するアルゴリズムの Java 実装を含む。
  • ELKI英語版 はGDBSCAN とその変異形と同様、DBSCAN の実装を提供している。この実装はほぼ 2 次の計算オーダーのための様々なインデックス(索引)構造を使用できる。また、任意の距離関数および任意のデータ型をサポートしている。しかし、小規模データに関する低レベルの最適化(および特殊化)実装が性能を上回るかもしれない。
  • Rfpc パッケージに DBSCAN を含み、距離行列を介した任意の距離関数をサポートしている。しかし、インデックス(索引)のサポートをしていない。(それゆえ、2 次の計算オーダーおよびメモリ消費の計算複雑性を持つ。) また、R インタープリタのため、かなり遅い。高速バージョンが kd木 を用いた C++ で実装されており、dbscan パッケージにある。
  • Scikit-learn は、任意のミンコフスキー距離英語版に対して、DBSCAN の Python 実装を含む。これはkd木およびen:Ball_treeを用いて高速化させることができるが、最悪な場合における 2 次オーダーのメモリ使用量となる。HDBSCAN* アルゴリズム が github で提供されている。
  • SPMFkd木をサポート(ただしユークリッド距離のみ)したDBSCAN アルゴリズムの GPL-V3 Java 実装を提供している。
  • Weka は 2 次オーダーの計算時間および線形メモリ使用量で動作するDBSCAN の基本的な実装を(最新バージョンのオプショナルパッケージとして)含む。

関連項目[編集]

  • OPTICS アルゴリズム - 複数レンジへの DBSCAN の一般化。パラメータ ε を最大探索半径に効率的に置き換える。
  • 連結成分
  • 素集合データ構造

脚注[編集]

  1. ^ a b minPts は直感的には最小クラスターサイズであるが、いくつかの場合では DBSCAN はより小さいクラスターを生成することができる。DBSCAN クラスタは少なくとも 1 コア点 から成る。ほかの点は 1 つよりも多いクラスタへの境界点であるかもしれないので、少なくとも minPts 点がどのクラスタにも含まれている保証は無い。

参考文献[編集]

  1. ^ a b Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M., eds (1996). “A density-based algorithm for discovering clusters in large spatial databases with noise”. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. ISBN 1-57735-004-9 
  2. ^ [1] Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24, when accessed on: 4/18/2010
  3. ^ 2014 SIGKDD Test of Time Award”. ACM SIGKDD (2014年8月18日). 2016年7月27日閲覧。
  4. ^ a b c Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (2015). “Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection”. ACM Transactions on Knowledge Discovery from Data 10 (1): 1–51. doi:10.1145/2733381. ISSN 15564681. 
  5. ^ Sander, Jörg; Ester, Martin; Kriegel, Hans-Peter; Xu, Xiaowei (1998). “Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications”. Data Mining and Knowledge Discovery (Berlin: Springer-Verlag) 2 (2): 169–194. doi:10.1023/A:1009745219419. http://www.springerlink.com/content/n22065n21n1574k6. 
  6. ^ Sander, Jörg (1998). Generalized Density-Based Clustering for Spatial Data Mining. München: Herbert Utz Verlag. ISBN 3-89675-469-6. 
  7. ^ Campello, R. J. G. B.; Moulavi, D.; Zimek, A.; Sander, J. (2013). “A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies”. Data Mining and Knowledge Discovery 27 (3): 344. doi:10.1007/s10618-013-0311-4. 
  8. ^ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). “The (black) art of runtime evaluation: Are we comparing algorithms or implementations?”. Knowledge and Information Systems. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. 

Further reading[編集]