DBSCAN (ノイズのあるアプリケーションの密度ベース空間クラスタリング)

DBSCAN とは何か? 

DBSCAN は Density-based Spatial Clustering of Applications with Noise の略で1996年にEster，Kriegel，Sander，Xuによって提案された．これは密度ベースのクラスタリング手法の中で最も広く使用されている教師なし学習手法である．この種の手法を使用することにはいくつかの利点がある: 未知のクラス数を作成する能力，非凸形状のクラスを作成する能力，および異常を取り扱う能力．

DBSCAN 法を使用するには，2個のパラメータが必要である:

• ϵ >0 ;
• 最小ポイントの数，MinPts > 0

複数の定義により，クラスがどのように作られるかを理解することができる．まず，我々は各ポイントの近傍を定義してカウントしなければならない．近傍は，ポイントqからの距離がϵ以下の訓練データセットのあらゆるポイントp として定義される．

定義によりポイントq はそれ自身の近傍であることに注意．

DBSCANアルゴリズムによって3種類のポイントが定義できる:

• コア・ポイント: 最小ポイントの数と同じ数以上の近傍を持つポイント．
• 境界ポイント: 最小ポイントの数よりも近傍が少ないが，コア・ポイントの近傍であるポイント．
• ノイズ・ポイント: コア・ポイントでも境界ポイントもない．

ポイントqがコア・ポイントであり，ポイントpがqの近傍であるなら、pはqから直接密度到達可能（directly density-reachable）である．前のポイントからの直接密度到達可能なポイントの順序づけされた複数のポイントがあるなら，ポイントpは密度到達可能（density-reachable ）である．ポイント p と q が両方ともoから密度到達可能であるようなポイントo があるなら，pとqは密度連結（density-connected ）である．

最後に，Esterらが2つの条件に適合するデータセットの部分集合として定義したクラス：

• p がクラス C に属し， q が p から密度到達可能であれば，q はCに属する．
• クラス C 内のすべてのポイントは，相互に密度連結である．

DBSCANアルゴリズムは

DBSCANアルゴリズムは，訓練データセットのすべてのポイントを訪問して，それらを訪問済みとしてマークする．

あるポイントがコア・ポイントであるなら，最初のクラスが始まる（クラス1と名付ける）．コア・ポイントとその近傍がクラス1に割り当てられる．そして，他のコア・ポイントを見つけて，それをクラス1に割り当てるために，その近傍を訪れて行く．このステップはクラスを拡張することを可能にする．すべての密度到達可能ポイントを訪れると，アルゴリズムはクラス1の拡張を停止する．

アルゴリズムは未訪問のポイントを訪問し続け，別のコア・ポイントを見付けると新しいクラスを開始する．このクラスもまた拡張されて…を繰り返す．

最後に，クラスに割り当てられていないがノイズ・ポイントとなる．

XLSTATでのDBSCANクラスタリングのオプション

DBSCAN による予測

DBSCAN は，新しいオブザベーションのクラスを予測することができる．

まず，訓練データセット内で新しい各オブザベーションの近傍を見つけなければならない．ある新しいオブザベーションが（訓練データセットの）コア・ポイントの近傍であるなら，新しいオブザベーションはコア・ポイントと同じクラスに割り当てられる．

新しいオブザベーションがその近傍内にコア・ポイントを持たないなら，それはノイズ・ポイントとみなされる．

訪問の順序が学習および予測の際に境界ポイントに割り当てられたクラスを変えるかもしれないことに注意．

K次元木（K-dimensional tree） 

データセットが量的変数のみを含む場合，K次元木（K-dimensional tree）を使用する (Bentley, 1975)．これは，半径のサイズイプシロン内のすべての近傍を見つけるためにすべての距離を計算しなくてもよい．

K次元木は，１次元からポイントを並べ替えて，中央値から空間を2つに分割することにより構築されるバイナリ・ツリーである．この次元で中央値以下の値を持つポイントは左の子ノードに格納され，中央値以上の値を持つポイントは右の子ノードに格納される．ノードにポイントが１個だけ残っているとツリーの構築が停止する．

距離メトリック 

さまざまな種類の変数での距離を計算するために，さまざまな距離メトリックがある.

量的変数のみが選択された場合，5つのメトリックがある:

• ユークリッド距離
• ミンコフスキー距離
• マンハッタン距離
• チェビシェフ距離
• キャンベラ距離．

質的変数のみでオブザベーションを記述する場合，オーバーラップ距離が使用される．

混合データでは，HEOM (Heterogeneous Euclidean Overlap Metric) が使用される．

XLSTATでのDBSCANクラスタリングの結果

記述統計: 記述統計の表は，すべての選択された変数の簡単な統計量を示す．欠損値の数，非欠損値の数，平均および標準偏差（不偏）が，量的変数ごとに表示される．質的変数については，従属変数，カテゴリがそれぞれの度数とパーセンテージとともに表示される．

相関行列: この表は，選択されたさまざまな変数間の相関の概観を提供するために表示される．

クラスごとのオブジェクトの数: この表は，各クラスのサイズとノイズ・ポイントの数の概観を提供するために表示される．

距離行列に関する結果: 予測オプションが有効な場合，１個または2個の距離行列が表示される．最初の行列は，訓練標本の各ポイント間の距離を示す．2番目の行列は，新しいオブザベーションと訓練標本のオブザベーションの間の距離を示す．

オブジェクトに関する結果: DBSCANアルゴリズムを用いて各オブザベーションに割り当てられたクラスが，訓練標本と予測標本について表示される．クラスが 0 の場合，それはそのオブザベーションがノイズ・ポイントとみなされることを意味する．さらに，各オブザベーションのシルエット・スコアが第2列に表示される（オプションが有効の場合）．

オプションが有効であれば，シルエット・スコアのグラフが表示される．オブザベーションが，シルエット・スコアで降順のクラスごとにグループ化される．

クラスで並べ替えされたオブジェクトに関する結果: この表は，クラスごとに並べ替えられたオブザベーションを示すために表示される．