# 密度ベースクラスタリング ## 定義 密度ベースクラスタリング（density-based clustering）は、データ空間中の密度が閾値を超える領域をクラスタとして同定し、低密度領域をノイズとして分離する教師なしクラスタリング手法の総称である。分割型（k-means 等）や階層型のアルゴリズムとは異なり、クラスタ数の事前指定を必要とせず、任意形状のクラスタを発見できる点を最大の特徴とする。 Ester+ 1996 による形式的定義では、以下の概念が段階的に導入される（[[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]]）: - **Eps 近傍**: 点 p から距離 Eps 以内にある全点の集合 NEps(p) - **核点（core point）**: Eps 近傍に MinPts 個以上の点を含む点。クラスタの内部に位置する - **境界点（border point）**: 核点の Eps 近傍に含まれるが、自身は核点条件を満たさない点。クラスタの外縁に位置する - **直接密度到達可能（directly density-reachable）**: 点 p が核点 q の Eps 近傍に含まれる関係。核点同士では対称だが、核点と境界点の間では非対称 - **密度到達可能（density-reachable）**: 直接密度到達可能の推移的閉包。点の連鎖を経由して到達できる関係 - **密度接続（density-connected）**: ある共通の点から双方が密度到達可能である関係。対称関係である - **クラスタ**: 密度接続された点の極大集合（密度到達可能性に関する極大性と密度接続による接続性を満たす） - **ノイズ**: いずれのクラスタにも属さない点の集合 この定義により、事前にクラスタ数を知らなくとも、データ中の密度分布からクラスタとノイズを自然に分離できる。 ## 代表的手法 - **DBSCAN**（Ester+ 1996）: 密度ベースクラスタリングの原型。グローバルな Eps と MinPts を用い、R*-tree による O(n log n) の効率を達成する。MinPts=4 の固定と sorted k-dist グラフによる対話的パラメータ決定を提案した - **OPTICS**（Ankerst+ 1999）: DBSCAN のグローバルパラメータ制約を緩和し、到達可能性プロット（reachability plot）により異なる密度のクラスタを単一実行で発見する - **DENCLUE**（Hinneburg & Keim 1998）: カーネル密度推定に基づくアプローチ。密度関数の勾配を利用してクラスタを同定する - **HDBSCAN**（Campello+ 2013）: 階層的密度ベースクラスタリング。DBSCAN* を再定義して境界点を排除し、相互到達可能距離（mutual reachability distance）を導入して単リンケージ法との等価性を示した。全ての $\varepsilon$ 値に対する DBSCAN* の解を最小全域木（MST）から階層的に構築し、有意なクラスタのみからなる簡約化ツリーを生成する。相対超過質量に基づく[[クラスタ安定性]]尺度と $O(\kappa)$ の動的計画法で最適なフラット分割を抽出する。唯一のパラメータは $m_{pts}$（密度推定の平滑化因子）。(Source: [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) ## 横断的知見 - DBSCAN のグローバルな密度閾値（単一の Eps）の限界を、HDBSCAN は階層化と安定性尺度で解決した。DBSCAN では異なる密度のクラスタを同時に発見できなかったが、HDBSCAN は全ての $\varepsilon$ 値に対する解を階層的に列挙し、クラスタ安定性に基づく最適抽出で異なる密度レベルのクラスタを同時に抽出する。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) - 境界点（border point）の扱いが DBSCAN と DBSCAN* で根本的に異なる。DBSCAN は境界点をクラスタに含めるが、DBSCAN* では排除する。DBSCAN* での境界点排除は密度レベルセットとの理論的整合性を改善し、HDBSCAN 階層との正確な対応関係を可能にした。一方で DBSCAN における境界点包含は、元論文で定理 1（クラスタ = 核点の密度接続 + 境界点）として示されているとおり、クラスタの「実用的な外縁」を与える設計判断でもあった。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) - Ester+ 1996 はパラメータ Eps の決定に sorted k-dist グラフとドメイン専門家の対話的判断を提案したが、HDBSCAN は $m_{pts}$ のみを残し Eps の選択を不要にした。$m_{pts}$ は密度推定の古典的平滑化因子であり挙動がよく理解されているため、パラメータ設定の負荷が大幅に軽減された。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]]) - 密度ベースクラスタリングと[[カーネル密度推定]]（KDE）には理論的な接続がある。Chen 2017 のチュートリアルでは、KDE の局所モードに基づくモードクラスタリング（Chacón+ 2015; Chen+ 2016）がミーンシフトアルゴリズムの統計的根拠として位置づけられている。DENCLUE は KDE の勾配を直接利用する密度ベース手法であり、KDE の帯域幅選択がクラスタリング結果を左右する。一方 HDBSCAN は相互到達可能距離による階層化で帯域幅の明示的選択を回避しており、KDE ベースの手法とは異なる設計判断である。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]], [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances]]) ## 未解決の問い - 高次元特徴空間において Eps 近傍の概念はどこまで有効か。Ester+ 1996 は 2 次元のユークリッド空間でのみ実験しており、高次元での k-dist グラフの形状調査を将来課題として挙げている - ~~グローバルパラメータ（単一の Eps/MinPts）による異なる密度のクラスタの統合問題は OPTICS/HDBSCAN でどの程度解決されたか~~ → HDBSCAN が $m_{pts}$ のみで全密度レベルを階層的に列挙し、安定性に基づく最適抽出で解決した（Campello+ 2013）。ただしスケーラビリティ（$O(dn^2)$）は大規模データへの適用を制約する - 密度ベース手法は時系列クラスタリングにおいてどの程度有効か。[[時系列クラスタリング]]の Paparrizos+ 2025 の評価では密度ベースは生データベース手法の 5 クラスの 1 つに分類されるが、k-Shape 等の分割型手法と比較した優位性は不明 - ストリーミングデータや逐次到着するデータへの密度ベースクラスタリングの適用（インクリメンタル DBSCAN 等）の実用的性能はどの程度か - HDBSCAN の半教師あり拡張とサブスペースクラスタリングへの統合は Campello+ 2013 で将来課題として言及されているが、未対応である - HDBSCAN の $O(dn^2)$ の計算量は MST 構築がボトルネックであり、大規模データに対する近似・並列化手法の有効性は検証が必要である ## 関連 - ソース: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]]、[[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]] - エンティティ: [[Martin Ester]]、[[Hans-Peter Kriegel]]、[[Jörg Sander]]、[[Ricardo J.G.B. Campello]]、[[Davoud Moulavi]] - 接続概念: [[時系列クラスタリング]]（密度ベースは生データベース手法の 1 クラス）、[[クラスタ安定性]]（HDBSCAN の最適化基準）、[[カーネル密度推定]]（DENCLUE は KDE ベース、モードクラスタリングは KDE の局所モードに基づく） - MOC: [[structures/時系列分析.MOC|時系列分析 MOC]]（存在する場合） ## 出典 - [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]] - [[@2013__PAKDD__Density-Based Clustering Based on Hierarchical Density Estimates]] - [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances]]