# 密度ベースクラスタリング ## 定義 密度ベースクラスタリング（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]], [[A Tutorial on Kernel Density Estimation and Recent Advances]]) - **DBSCAN の Eps 近傍密度と、異常検知の LOF(Local Outlier Factor)の局所密度は、同じ「点を中心とした近傍で密度を推定する」操作を、大域固定閾値か相対比較かで対極的に使う**: DBSCAN([[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]])は、全データに共通する単一の Eps・MinPts を用いて核点・境界点・ノイズを分類し、Eps 近傍内の点数が MinPts 以上かどうかという**大域固定閾値**でクラスタとノイズを分ける。これに対し [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 5 Nearest Neighbor-Based Anomaly Detection Techniques]] が整理する LOF([Breunig et al. 1999, 2000])は、あるインスタンスの局所密度(k 近傍を含む最小超球の体積で k を割った値)を、その k 近傍の**平均局所密度との比**として異常スコアを計算する——DBSCAN の「密度が MinPts/Eps 以上か」という絶対判定に対し、LOF は「近傍と比べて密度が低いか」という相対判定である。この違いは、密度が場所によって異なるデータ集合(章の Figure 7: 疎な大クラスタ C1 と密な小クラスタ C2 が共存する例)で顕在化する——DBSCAN も k 番目近傍距離ベースの大域的異常検知技法と同様、単一の Eps では疎なクラスタ C1 内の正常点と密なクラスタ C2 近傍の異常点 p2 を判別できない。DBSCAN のクラスタリング文脈での「密度の異なるクラスタを同時に扱えない」という限界(本ページの HDBSCAN が解決した課題、上記)と、異常検知文脈での「大域的な密度ベース技法が密度の異なる領域で失敗する」という限界は、同一の設計制約——単一の大域密度尺度への依存——が2つの異なるタスク(クラスタリング/異常検知)で独立に指摘された表れであるという点で符合する。ただし解法は異なる: HDBSCAN は全 Eps 値に対する階層的な解の列挙とクラスタ安定性で対処するのに対し、LOF は近傍ごとの相対密度比という局所化で対処する。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 5 Nearest Neighbor-Based Anomaly Detection Techniques]] §5.2) - **DBSCAN のノイズ点定義は、Chandola 2009 が言うクラスタリングベース異常検知の第1カテゴリの仮定そのものであり、かつ同章はその欠点(クラスタ発見への最適化であって異常発見への最適化ではない)を DBSCAN 自身の設計意図から説明できる**: DBSCAN([[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]])は、Eps 近傍と MinPts による核点・境界点・ノイズの分類を提案した時点で「いずれのクラスタにも属さない点の集合」をノイズとして明示的に定義している(本ページ「定義」節)。[[@2009__CSUR__Anomaly Detection - A Survey - Chapter 6 Clustering-Based Anomaly Detection Techniques]] は、クラスタリングベース異常検知の第1カテゴリの仮定を「正常はクラスタに属し、異常はどのクラスタにも属さない」と定式化し、DBSCAN・ROCK・SNN clustering をこの仮定に基づく代表技法として直接名指しする(§6)。すなわち DBSCAN のノイズ点は、クラスタリング側の設計語彙では「クラスタから漏れた点」だが、異常検知側の語彙では「異常」と同一視される——1996年のクラスタリング論文が定義した概念が、2009年のサーベイでは異常検知の技法カテゴリの仮定そのものとして再解釈されている。ただし Chandola 2009 は同時に、この転用に伴う欠点を明示する:この種の技法は「基盤とするクラスタリングアルゴリズムの主目的があくまでクラスタの発見であり、異常の発見に最適化されていない」(§6)。DBSCAN の目的関数(R*-tree による効率的なクラスタ抽出、本ページ「代表的手法」節)はノイズ点の異常性を評価する基準を一切含まないため、この欠点は DBSCAN の設計そのものから直接説明できる。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 6 Clustering-Based Anomaly Detection Techniques]] §6) - **DBSCAN の核点条件は、一様カーネルによる KDE のレベルセットと数式レベルで一致する——密度到達可能性という手続き的定義と、モード/レベルセットという解析的定義は、同じ「密度が高い領域をクラスタとする」直観の2つの形式化である**: DBSCAN([[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]])の核点条件「Eps 近傍 $N_{\mathrm{Eps}}(p)$ に含まれる点数が MinPts 以上」は、$N_{\mathrm{Eps}}(p)$ の点数を体積 $V_d \cdot \mathrm{Eps}^d$ で割ったものが半径 Eps の一様(球状)カーネルによる KDE $\hat p(x)$ の値そのものであることから、$\hat p(x) \ge \lambda$($\lambda = \mathrm{MinPts}/(n V_d \mathrm{Eps}^d)$)という**レベルセット条件**に書き換えられる。これは [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]] §4.2 が定義するレベルセット推定量 $\hat L_\lambda=\{x:\hat p_n(x)\ge\lambda\}$ と数式上一致する。さらに DBSCAN のクラスタ(密度接続された点の極大集合)は、単一の $\lambda$ における $\hat L_\lambda$ の連結成分であり、これは同章 §4.5 のクラスタツリーが「$\lambda$ を連続的に動かしたときの $\hat L_\lambda$ の連結成分の生成・消滅」を追跡する構造の、**1つの $\lambda$ での断面**に相当する。本ページが既に指摘する「DBSCAN の単一 Eps・単一 MinPts の限界を HDBSCAN が階層化で解決した」という知見(上記)は、Chen (2017) の言葉で言えば「DBSCAN は1断面しか見ないが、クラスタツリーは全ての $\lambda$ を階層的に保持する」ことと同じ現象を、独立したコミュニティ(空間データベース/統計)が別々の語彙で定式化していたことを意味する。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]] §4.2, §4.5) - **モードクラスタリング(勾配上昇流による分割)と DBSCAN の密度連結性による分割は、同じ密度関数から出発しても異なる原理でクラスタ境界を引く**: [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]] §4.1 のモードクラスタリング(mean shift)は、各データ点を密度勾配の上昇流に沿って対応する局所モード $M=\{x:g(x)=0,\lambda_1(x)<0\}$ まで移動させ、同じモードに到達した点を1つのクラスタとする(基底吸引域による分割)。これに対し DBSCAN のクラスタは、Eps 近傍を介した点同士の密度到達可能性の推移閉包で定義され、勾配やモードの概念を一切使わない。前者は密度関数の微分構造(§4.4 の Morse-Smale複体と同じ勾配フームの考え方)に基づき、後者は近傍グラフの連結性のみに基づく。同じ2峰性のデータ(本ページ図7: 2つの高密度クラスタと低密度クラスタ)に対して、両者が常に同じクラスタ境界を与えるとは限らない。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]] §4.1) ## 未解決の問い - 高次元特徴空間において 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 構築がボトルネックであり、大規模データに対する近似・並列化手法の有効性は検証が必要である - DBSCAN の大域固定閾値と LOF の局所相対密度は独立に「密度の異なる領域」問題へ対処してきたが、両者を接続する定量的な比較(同一データセットで DBSCAN のノイズ判定と LOF の異常スコアがどの程度一致・乖離するか)は本ページ・[[異常検知]]のいずれにも見当たらない。クラスタリングのノイズ点検出と異常検知の異常スコアは概念的に近いが、この2つのコミュニティの手法を直接比較した実証はどこまで存在するか。(Source: [[@1996__KDD__A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise]], [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 5 Nearest Neighbor-Based Anomaly Detection Techniques]]) - DBSCAN の核点条件を一様カーネル KDE のレベルセットとして定式化した場合(上記横断的知見)、[[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]] §4.2・§4.5 が与えるレベルセット・クラスタツリーの収束保証や信頼集合構成法(Mammen and Polonik, 2013; Chen et al., 2015c; Jisu et al., 2016)は、DBSCAN/HDBSCAN のクラスタ推定にそのまま転用できるか。この理論的橋渡しは本ページの既存ソース群のどこにも明示されていない。 - モードクラスタリング(勾配上昇流による分割)と密度連結性による分割(DBSCAN)は、いつ同じクラスタ境界に一致し、いつ乖離するか。両者を同一データセットで比較した実証は本ページのソース群に見当たらない。 ## 関連 - ソース: [[@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 - Chapter 4 Geometric and Topological Features]]（局所モード・レベルセット・クラスタツリーという解析的なクラスタ定義）、[[@2009__CSUR__Anomaly Detection - A Survey - Chapter 5 Nearest Neighbor-Based Anomaly Detection Techniques]]（LOF の局所密度比との対比）、[[@2009__CSUR__Anomaly Detection - A Survey - Chapter 6 Clustering-Based Anomaly Detection Techniques]]（DBSCAN のノイズ点を異常検知の第1カテゴリとして再解釈） - エンティティ: [[Martin Ester]]、[[Hans-Peter Kriegel]]、[[Jörg Sander]]、[[Ricardo J.G.B. Campello]]、[[Davoud Moulavi]] - 接続概念: [[時系列クラスタリング]]（密度ベースは生データベース手法の 1 クラス）、[[クラスタ安定性]]（HDBSCAN の最適化基準）、[[カーネル密度推定]]（DENCLUE は KDE ベース、モードクラスタリングは KDE の局所モードに基づく）、[[異常検知]]（LOF は本概念の Eps 近傍密度と対照的な相対密度設計を異常スコアに用いる） - 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]] - [[A Tutorial on Kernel Density Estimation and Recent Advances]] - [[@2017__arXiv__A Tutorial on Kernel Density Estimation and Recent Advances - Chapter 4 Geometric and Topological Features]](§4.1 モードクラスタリング、§4.2 レベルセット、§4.5 クラスタツリー) - [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 5 Nearest Neighbor-Based Anomaly Detection Techniques]](§5.2 相対密度ベース技法・LOF の定義) - [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 6 Clustering-Based Anomaly Detection Techniques]](§6 クラスタリングベース異常検知の第1カテゴリ・DBSCAN)