DBSCANとは何ですか？

DBSCANは、ノイズのあるアプリケーションの密度ベースの空間クラスタリングの略です。これは、密度ベースのクラスタリングアルゴリズムです。アルゴリズムは、十分に高密度の領域をクラスターに増やし、ノイズのある空間データベースで任意のアーキテクチャのクラスターを見つけます。これは、クラスターを密度接続ポイントの最大グループとして表します。

密度ベースのクラスタリングの概念には、次のようないくつかの新しい定義が含まれています-

• 特定のオブジェクトの半径ε内の近傍は、オブジェクトのε近傍として知られています。

• オブジェクトのε近傍に少なくとも最小数のMinPtsが含まれている場合、そのオブジェクトはコアオブジェクトと呼ばれます。

• オブジェクトのセットDが与えられた場合、pがqのε近傍内にあり、qがコアオブジェクトである場合、オブジェクトpはオブジェクトqから直接密度到達可能であると言えます。

• オブジェクトpは、オブジェクトのチェーンp ₁ がある場合、オブジェクトのグループDのεとMinPtsに関してオブジェクトqから密度到達可能です。 、...、p _n 、ここでp ₁ =qおよびp_n =p _iを含むp +1は、p _iから直接密度に到達できます。 εとMinPtsに関して、1≤i≤nの場合、p _i εD。

• オブジェクトpとqの両方がεとMinPtsに関してoから密度到達可能であるようなオブジェクトoεDが存在する場合、オブジェクトpはオブジェクトのグループD内のεとMinPtsに関するオブジェクトqに密度リンクされます。

  >

密度到達可能性は、直接密度到達可能性の推移閉包であり、この接続は非対称です。相互に密度到達可能なコアオブジェクトのみがあります。密度の接続性は対称的な関係です。

密度ベースのクラスターは、密度到達可能性に関して最大​​の密度接続オブジェクトのグループです。どのクラスターにも含まれていない各オブジェクトは、ノイズとして扱われます。

DBSCANは、データベース内のすべてのポイントのε近傍をテストすることにより、クラスターを検索します。点pのε近傍にMinPtsを超えるものが含まれている場合、コアオブジェクトとしてpを持つ新しいクラスターが作成されます。 DBSCANは、これらのコアオブジェクトから直接密度到達可能なオブジェクトを繰り返し収集します。これには、いくつかの密度到達可能なクラスターのマージを含めることができます。どのクラスターにも新しいポイントを挿入できない場合、プロセスは削除されます。

空間インデックスを使用する場合、DBSCANの計算の複雑さはO（nlogn）です。ここで、nはデータベースオブジェクトの数です。したがって、O（n ² ）。ユーザーが表すパラメーターεとMinPtsを適切に設定すると、アルゴリズムは任意の形状のクラスターを効率的に検出できます。