[密度ベースのクラスター分析 (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)] は、最も高速なクラスター分析手法ですが、カットオフとして使用する検索距離が明確であり、その検索距離がすべてのクラスターに対して十分に機能する場合にのみ適しています。 このアルゴリズムを使用するには、すべての意味のあるクラスターが類似する密度を持っている必要があります。
自己調整 (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.