[密度ベースのクラスター分析 (Density-based Clustering)] ツールは、ポイントが集中しているエリアおよび空または疎なエリアによって分離されているエリアを検出することによって機能します。 クラスターに含まれないポイントには、ノイズとしてラベルが付けられます。 必要に応じて、ポイントの時間を使用し、空間および時間でクラスタリングするポイントのグループを検索できます。
このツールは、教師なし機械学習クラスタリング アルゴリズムを使用します。このアルゴリズムは、空間位置および指定された近傍数までの距離のみに基づいてパターンを自動的に検出します。 このアルゴリズムは、クラスターになることが何を意味しているかに関するトレーニングを必要としないため、教師なしであると見なされています。
ヒント:
クラスタリング、グループ化、および分類手法は、機械学習で最も広く使用されている方法です。 [多変量クラスター分析 (Multivariate Clustering)] ツールおよび [空間的に制限された多変量クラスター分析 (Spatially Constrained Multivariate Clustering)] ツールも、教師なし機械学習方法を使用してデータ内の自然なクラスターを決定します。 これらの分類方法は、データ内のクラスターを見つけるように誘導またはトレーニングするために、事前に分類されたフィーチャのセットを必要としないため、教師なしであると見なされています。
適用例
このツールの適用例には、以下のようなものがあります。
- 市街地の配水網は、重要な隠れ地下資産です。 パイプの断裂および破裂のクラスタリングは、迫り来る問題を示す場合があります。 エンジニアは、[密度ベースのクラスター分析 (Density-based Clustering)] ツールを使用して、これらのクラスターが存在する場所を見つけ、配水網内の危険性の高いゾーンに対して予防措置を講じることができます。
- NBA の選手のすべての成功したシュートおよび失敗したシュートに関する位置データが存在すると仮定します。 [密度ベースのクラスター分析 (Density-based Clustering)] ツールは、選手ごとに成功したシュートと失敗したシュートの位置のさまざまなパターンを示すことができます。 その後、この情報を使用して、ゲーム戦略に関する情報を提供することができます。
- たとえば、害虫が運ぶ特定の病気を調査しており、分析範囲内の世帯を表しているポイント データセットが存在し、それらの世帯の一部が感染していて、その他の世帯が感染していないとします。 [密度ベースのクラスター分析 (Density-based Clustering)] ツールを使用することによって、感染した世帯の最大のクラスターを決定し、害虫の処理および駆除を開始する必要のあるエリアを正確に示すことができます。
- 自然災害またはテロ攻撃の後のジオロケートされたツイートをクラスタリングすることができ、識別されたクラスターのサイズおよび位置に基づいて、救助および避難の必要性に関する情報を提供することができます。
クラスター分析方法
[密度ベースのクラスター分析 (Density-based Clustering)] ツールの [クラスター分析方法] パラメーターには、ポイント データ内のクラスターを見つけるための 3 種類のオプションが用意されています。
- [指定距離 (DBSCAN)] - 指定された距離を使用して、密なクラスターを疎なノイズから分離します。 DBSCAN アルゴリズムは、最も高速なクラスター分析手法ですが、使用する [検索距離] が非常に明確であり、その検索距離がすべての潜在的なクラスターに対して十分に機能する場合にのみ適しています。 このアルゴリズムを使用するには、すべての意味のあるクラスターが類似する密度を持っている必要があります。 この方法では、[時間フィールド] および [時間間隔の検索] パラメーターを使用して、空間および時間内のポイントのクラスターを見つけることもできます。
- [自動調整 (HDBSCAN)] - 距離の範囲を使用して、さまざまな密度のクラスターを疎なノイズから分離します。 HDBSCAN アルゴリズムは、最高のデータ駆動型のクラスター分析方法であるため、最小限のユーザー入力で済みます。
- [マルチスケール (OPTICS)] - 近傍のフィーチャ間の距離を使用して、到達可能性プロットを作成します。その後、このプロットは、さまざまな密度のクラスターをノイズから分離するために使用されます。 OPTICS アルゴリズムは、検出されるクラスターの微調整において最も高い柔軟性を備えていますが、特に大きい [検索距離] を使用した場合、計算負荷が大きくなります。 この方法では、[時間フィールド] および [時間間隔の検索] パラメーターを使用して、空間および時間内のポイントのクラスターを見つけることもできます。
このツールは、[入力ポイント フィーチャ]、[出力フィーチャ] のパス、およびクラスターと見なされるために必要なフィーチャの最小数を表す値を受け取ります。 ここで選択した [クラスター分析方法] に応じて、下で説明されているように、その他のパラメーターを指定する必要があります。
クラスターあたりの最小フィーチャ数
このパラメーターは、ポイントのグループをクラスターと見なすために必要な最小フィーチャ数を決定します。 たとえば、10 個のポイントから 100 個のポイントまでのサイズの複数のクラスターが存在し、20 の [クラスターあたりの最小フィーチャ数] を選択した場合、20 個のポイントよりも少ないすべてのクラスターは、(クラスターと見なすことができるほど十分に大きいグループを形成しないため) ノイズと見なされるか、必要なフィーチャの最小数を満たすために近くのクラスターとマージされます。 これに対して、最も小さい意味のあるクラスターと見なすサイズよりも小さい [クラスターあたりの最小フィーチャ数] を選択すると、意味のあるクラスターがさらに小さいクラスターに分割される場合があります。 言い換えると、[クラスターあたりの最小フィーチャ数] が小さいほど、より多くのクラスターが検出されます。 [クラスターあたりの最小フィーチャ数] が大きいほど、より少ないクラスターが検出されます。
ヒント:
理想的な [クラスターあたりの最小フィーチャ数] は、得ようとしていること、および解析問題によって変わります。 この値は、意味のあるクラスターと見なしたい最小のサイズのグループに設定する必要があります。 [クラスターあたりの最小フィーチャ数] を増やすと、小さいクラスターの一部が一緒にマージされる場合があります。
[クラスターあたりの最小フィーチャ数] パラメーターは、クラスターを見つけるために 3 つの方法すべてによって使用される計測値である、中心距離の計算においても重要になります。 概念的には、中心距離または各ポイントは、各ポイントから、定義された最小数のフィーチャまで移動するために必要になる距離の計測値です。 そのため、大きい [クラスターあたりの最小フィーチャ数] が選択された場合、対応する中心距離は大きくなります。 小さい [クラスターあたりの最小フィーチャ数] が選択された場合、対応する中心距離は小さくなります。 中心距離は、[指定距離 (DBSCAN)] 方法および [マルチスケール (OPTICS)] 方法の両方によって使用される [検索距離] パラメーターに関連しています。
検索距離 (DBSCAN and OPTICS)
[指定距離 (DBSCAN)] では、特定のポイントからの [検索距離] の範囲内で [クラスターあたりの最小フィーチャ数] を見つかった場合、そのポイントには中心ポイントとしてマークが付けられ、中心距離の範囲内のすべてのポイントとともにクラスターに追加されます。 境界ポイントとは、中心ポイントの検索距離内にあるものの、そのポイント自体の検索距離の範囲内には最小フィーチャ数が存在しないポイントのことを指します。 生成される各クラスターは、中心ポイントと境界ポイントで構成され、中心ポイントはクラスターの中央に、境界ポイントはクラスターの外側に位置する傾向があります。 ポイントの検索距離の範囲内に最小フィーチャ数が存在せず、他の中心ポイントの検索距離の範囲内にも存在しない場合 (つまり、中心ポイントでも境界ポイントでもない場合)、そのポイントにはノイズとしてマークが付けられ、どのクラスターにも追加されません。
[マルチスケール (OPTICS)] の場合、[検索距離] 値は中心距離と比較される最大距離として扱われます。 [マルチスケール (OPTICS)] は、最小到達可能性距離の概念を使用します。この距離は、あるポイントから、検索によってまだ訪問されていない最も近いポイントまでの距離です (注意: OPTICS は、ID が最小のフィーチャから開始し、そのポイントから次のポイントまで進んでプロットを作成する順序付けられたアルゴリズムです。 ポイントの順序が、結果にとって重要になります)。[マルチスケール (OPTICS)] は、指定された [検索範囲] 内のすべての近傍フィーチャの距離を検索し、それらの距離を中心距離と比較します。 いずれかの距離が中心距離よりも小さい場合、そのフィーチャには到達可能性距離としてその中心距離が割り当てられます。 すべての距離が中心距離よりも大きい場合、それらの距離のうちの最小の距離が到達可能性距離として割り当てられます。 検索距離の範囲内にそれ以上のポイントが存在しない場合は、それまでに訪問されていない新しいポイントから処理が再開されます。 各反復で、到達可能性距離は再計算され、並べ替えられます。 各ポイントの最終的な到達可能性距離には、それらの距離のうちの最小の距離が使用されます。 その後、それらの到達可能性距離は、到達可能性プロットの作成に使用されます。到達可能性プロットは、クラスターの検出に使用される到達可能性距離の順序付けられたプロットです。
[指定距離 (DBSCAN)] および [マルチスケール (OPTICS)] の両方とも、距離が指定されない場合、デフォルトの [検索距離] は、データセット内で検出された中心距離のうち、上位 1% を除く (言い換えると、最も極端な中心距離を除く) 最大の中心距離になります。
空間および時間でのクラスタリング (DBSCAN and OPTICS)
2 つのクラスター分析方法では、各ポイントの時間を [時間フィールド] パラメーターで指定できます。 指定した場合、ツールは空間および時間で互いに近いポイントのクラスターを見つけます。 [検索時間間隔] パラメーターは、検索距離と同様で、このパラメーターを使用して、時空間クラスターの中心ポイント、境界ポイント、ノイズ ポイントが決定されます。
[指定距離 (DBSCAN)] では、クラスター メンバーを検索する際、時空間クラスターの中心ポイントとなるには、[検索距離] および [検索時間間隔] 内に [クラスターあたりの最小フィーチャ数] が見つかる必要があります。
次の画像では、検索距離は 1 マイル、検索時間間隔は 3 日、最小フィーチャ数は 4 です。 ポイント P は、検索距離および時間間隔内に (そのポイント自身も含めて) 4 つのポイントが存在するため、中心ポイントです。 ポイント Q は、検索距離および時間間隔内に 3 つのポイントしか存在せず、クラスターの中心点 (タイムスタンプ 1/5/2021 のポイント) の検索距離および時間間隔の範囲内に含まれているため、境界ポイントです。 ポイント C および D は、クラスターの中心ポイントでも境界ポイントでもなく、他のすべてのポイント (P と Q を含む) が 1 つのクラスターを形成しているため、ノイズ ポイントです。
[マルチスケール (OPTICS)] では、ポイントが中心距離を計算し、指定した [検索距離] 値の範囲内にあるすべての近隣の距離を検索して、到達可能性距離を計算する際に、そのポイントの [検索時間間隔] の範囲外にあるすべてのポイントが除外されます。
次の画像では、検索距離は 2 マイル、検索時間間隔は 3 日、最小フィーチャ数は 4 です。 ポイント P の中心距離は、ポイント q3 が検索時間間隔の範囲外にあるため、ポイント q3 をスキップして計算されます。 この場合、P の中心距離は、P の到達可能性距離と等しくなります。
次の画像は、いくつかの近傍ポイントがすでに訪問されている場合の到達可能性距離の計算を示しています。 ポイント q1、q2、q4 は以前に訪問されているためスキップされ、ポイント q3、q5 は検索タイム ウィンドウの範囲外にあるためスキップされました。
到達可能性プロット (OPTICS)
データセット全体に対して、すべての到達可能性距離が計算された後に、各距離を順序付けし、各ポイントのクラスタリング構造を明らかにする到達可能性プロットが構築されます。
![[到達可能性チャート] の例](GUID-E5ACACBD-173B-42B5-9243-E7CC6320A32B-web.png "[到達可能性チャート] の例")
到達可能性プロット内の谷は、1 つのポイントから次のポイントまで、短い距離を移動する必要があることを意味しています。 したがって、各谷は、プロット パターン内の異なるクラスターを表しています。 クラスターの密度が高いほど、到達可能性距離が短くなり、プロット上の谷が低くなります (たとえば上の例では、ピンク色のクラスターの密度が最も高くなっています)。 クラスターの密度が低いほど、到達可能性距離が長くなり、プロット上の谷が高くなります (たとえば上の例では、濃い緑色のクラスターの密度が最も低くなっています)。 ピークは、ポイントのセットの構成に応じて、クラスター間で (つまり、クラスターからノイズを経て再びクラスターへ) 移動する必要のある距離を表しています。
[検索距離] が最大中心距離よりも短い場合、到達可能性プロットでプラトーが発生する可能性があります。 OPTICS クラスター分析方法を使用する場合の重要な側面は、到達可能性プロットからクラスターを検出する方法を決定することです。この決定は、[クラスター感度] パラメーターを使用して行います。
[クラスター感度] (OPTICS)
[クラスター感度] パラメーターは、到達可能性プロット内のピークの形状 (傾斜角および高さの両方) がクラスターの分離にどのように使用されるかを決定します。 非常に高い (100 に近い) [クラスター感度] は、最小のピークでさえ、クラスター間の分離として扱い、多くのクラスターを生成します。 非常に低い (0 に近い) [クラスター感度] は、最も急勾配の最高のピークのみを、クラスター間の分離として扱い、少ないクラスターを生成します。
デフォルトの [クラスター感度] は、それ以上クラスターを追加しても情報が追加されない閾値として計算されます。この計算は、元の到達可能性プロットとクラスタリング後に得られるスムージングされた到達可能性プロットの間で、Kullback-Leibler Divergence を使用して行われます。
方法の比較
[マルチスケール (OPTICS)] のみが到達可能性プロットを使用してクラスターを検出しますが、このプロットを使用して、各方法が互いにどのように異なっているかを概念的に説明することができます。 説明の目的で下の到達可能性プロットを使用して、3 つの方法の違いについて説明します。 このプロットは、さまざまな密度のクラスターおよび分離距離を明らかにします。 この図のデータに対して各クラスター分析手法を使用した結果を調べます。
[指定距離 (DBSCAN)] の場合、指定された [検索距離] で到達可能性プロットを横切るラインを描画することを想像することができます。 [検索距離] の下の領域はクラスターを表し、[検索距離] の上のピークはノイズ ポイントを表しています。[指定距離 (DBSCAN)] は、最も高速なクラスター分析手法ですが、カットオフとして使用する [検索距離] が非常に明確であり、その [検索距離] がすべてのクラスターに対して十分に機能する場合にのみ適しています。 このアルゴリズムを使用するには、すべての意味のあるクラスターが類似する密度を持っている必要があります。
![DBSCAN アルゴリズムでの [検索距離] の図](GUID-08CF501C-D57C-4C56-8875-2B2BAC601973-web.png "DBSCAN アルゴリズムでの [検索距離] の図")
自己調整 (HDBSCAN) の場合、到達可能性距離は、クラスターのネストされたレベルであると考えることができます。 各レベルのクラスタリングでは、異なるクラスターのセットが検出されます。 自己調整 (HDBSCAN) は、ノイズを含まずにできるだけ多くのメンバーを含んでいる最も安定したクラスターを最適に作成する、一連のネストされたクラスター内のクラスターのレベルを選択します。 このアルゴリズムの詳細については、HDBSCAN の作成者が提供している素晴らしいドキュメントをご参照ください。 自己調整 (HDBSCAN) は、最高のデータ駆動型のクラスター分析方法であるため、最小限のユーザー入力で済みます。
[マルチスケール (OPTICS)] の場合、クラスターを検出する機能は、特定の距離に基づくのではなく、代わりにプロット内のピークおよび谷に基づきます。 各ピークのレベルが小、中、または大のいずれかであるとします。
非常に高い [クラスター感度] を選択することは、本質的に、小から大までのすべてのピークがクラスター間の分離として機能する (より多くのクラスターが得られる) ことを意味しています。
中程度の [クラスター感度] を選択すると、中および大の両方のピークが使用されますが、小のピークは使用されません。
非常に低い [クラスター感度] を選択すると、大のピークのみが使用され、最も少ない数のクラスターが検出されます。
[マルチスケール (OPTICS)] は、検出されるクラスターの微調整において最も高い柔軟性を備えていますが、3 つのクラスター分析方法のうちで最も低速でもあります。
結果
このツールは、各フィーチャがどのクラスターのメンバーになっているかを示す新しい整数フィールド CLUSTER_ID を含んでいる出力フィーチャクラスを生成します。 デフォルトのレンダリングは COLOR_ID フィールドに基づきます。 複数のクラスターに、それぞれ色が割り当てられます。 各クラスターが隣接するクラスターと視覚的に区別されるように色が割り当てられ繰り返されます。
選択された [クラスター分析手法] が [自動調整 (HDBSCAN)] だった場合、出力フィーチャクラスには、割り当てられたグループにフィーチャが属している確率であるフィールド PROB、フィーチャがそのクラスター内の外れ値である可能性があることを示す OUTLIER (フィーチャが外れ値である可能性が高まるほど、値が大きくなる場合)、および各クラスターの最も典型的または代表的なフィーチャを示す EXEMPLAR も含まれます。
このツールでは、特定されたクラスターの特性を理解するのに役立つメッセージとチャートも作成されます。 このメッセージにアクセスするには、進行状況バーにマウス カーソルを合わせ、[別ウィンドウに表示] ボタンをクリックして、[ジオプロセシング] ウィンドウの [メッセージ] セクションを展開します。 ジオプロセシング履歴を介して、以前に実行した [密度ベースのクラスター分析 (Density-based Clustering)] ツールのメッセージにアクセスすることもできます。 作成されたチャートには、[コンテンツ] ウィンドウからアクセスできます。
[マルチスケール (OPTICS)] を選択したときに作成される到達可能性プロットに加えて、すべてのクラスター分析方法は、すべての一意のクラスター ID を表示するバー チャートも作成します。 このチャートを使用して、指定したクラスターに含まれるすべてのフィーチャを簡単に選択すること、および各クラスターのサイズを調べることができます。
参考資料
DBSCAN の詳細については、次をご参照ください。
- Birant, D. & Kut, A. (2007, January). "ST-DBSCAN: An algorithm for clustering spatial–temporal data." In Data & Knowledge Engineering (Vol 60, No. 1, pp. 208-221). https://doi.org/10.1016/j.datak.2006.01.013
- Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). "A density-based algorithm for discovering clusters in large spatial databases with noise." In Kdd (Vol. 96, No. 34, pp. 226-231).
HDBSCAN の詳細については、次をご参照ください。
- Campello, R. J., Moulavi, D., & Sander, J. (2013, April). "Density-based clustering based on hierarchical density estimates." In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 160-172). Springer, Berlin, Heidelberg.
OPTICS の詳細については、次をご参照ください。
- Agrawal, K. P., Garg, S., Sharma, S., & Patel, P. (2016, November). "Development and validation of OPTICS based spatio-temporal clustering technique." In Information Sciences (Vol 369, pp. 388-401). https://doi.org/10.1016/j.ins.2016.06.048.
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999, June). "OPTICS: ordering points to identify the clustering structure." In ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.