DBSCANアルゴリズムの詳細

原文住所:http://blog.csdn.net/star_dragon/article/details/50728972
DBSCANアルゴリズムの詳細と実装
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)アルゴリズムは、空間密度に基づくクラスタリングアルゴリズムであり、他の従来のクラスタリングとは異なり、空間密度の高い領域をクラスタリングし、生成されたクラスタには固定形状(これに対してkmeansクラスタ形状が円、emクラスタ形状が楕円)がなく、偏りがない.DBSCANアルゴリズムはクラスタ効果を実現できるほか、データ中のノイズを探すためにも使用できる.これは従来のクラスタアルゴリズムではできないことであり、以下に関連概念を紹介する.

アルゴリズムパラメータ

dbscanアルゴリズムは密度クラスタリングに基づくアルゴリズムであり,密度の直感的な理解はある単位範囲内にどれだけのものが含まれているかであり,本アルゴリズムでは2つのパラメータrとminPtsを定義している.いずれのデータ点についても、r近傍に含まれるデータ点の数(それ自体を含む)は密度であり、minPtsはアルゴリズムで使用されるしきい値である.

コアコンセプトコアポイント:あるポイントの密度がアルゴリズム設定のしきい値に達すると(すなわち、r近傍内の点の数がminPtsより小さくない)は、コア点である.直接密度は、ある点pが点qのr近傍内にあり、qがコア点である場合、pはqから直接密度に達するという.密度は、ある点のシーケンスq 0、q 1、...qkがあり、任意のqiに対してqi-1から直接密度に達する場合、q 0からqkまでの密度に達するというが、実際には直接密度の高い「伝播」.密度接続:あるコア点pから点qと点kが密度に達すると、点qと点kは密度接続と呼ばれる.

以上の概念は下図(画像はウィキペディアから)から直観的に見ることができ、円はr近傍を表し、赤色点は核心点であり、点AからB、Cはいずれも密度が達成でき、B、Cは密度が接続され、B、Cは境界点であり、Nはノイズ点である(境界点、ノイズ点の概念はアルゴリズム部分で詳細に述べている).

アルゴリズム思想

dbscanアルゴリズムは本質的にクラスクラスタを探し、クラスクラスタを絶えず拡張するプロセスであり、クラスクラスタを形成するにはまずデータ密度が要求を満たす必要がある.任意の点pに対して、それがコア点であれば、pを中心としてrを半径として1つのクラスクラスタCを形成することができ、クラスクラスタを拡張する方法はクラスタ中の点を遍歴し、点qがコア点であれば、qのr近傍内の点もクラスCに分類し、Cがこれ以上拡張できないまで再帰的に実行する.以上の図を例として、minPtsが3、rが図中の円の半径であると仮定し、アルゴリズムはAから始まり、それを核心点として計算する.すると、点Aとその近傍内のすべての点(計4つ)をクラスQとし、次にクラスQの拡張を試みる.クエリから、クラスQ内のすべての点がコア点であることがわかる(赤点)なので、いずれも拡張能力があり、点CもクラスQに分類される.再帰的に拡張する過程で、Cはコア点ではなく、クラスQは点Cから拡張できないことが分かり、Cを境界点と呼ぶ.境界点はあるクラスに属する非コア点と定義される.数回拡張するとクラスQは拡張できなくなり、このとき形成されるクラスは図中Nを除くすべての点であり、点Nはノイズとなる点、すなわちクラスクラスタに属さない点であり、等価な点は、いずれのコア点からも密度が達成できないと定義することができる.上の図のデータポイントは1つのクラスにしか集約できません.実際の使用では、あるクラスの拡張が完了した後、分類されていないコアポイントを選択して新しいクラスクラスタを形成し、拡張することがよくあります.アルゴリズムの終了フラグは、すべてのポイントが1つのクラスまたはノイズに分類され、すべてのクラスが拡張できないことです.アルゴリズムの偽コードは次のとおりです.ウィキペディアから抜粋します.

DBSCAN(D, eps, MinPts) {//  eps    r
   C = 0
   for each point P in dataset D {//     
      if P is visited
         continue next point
      mark P as visited
      NeighborPts = regionQuery(P, eps)//  p        
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE//         ，         ，                
      else {
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)//     ，     
      }
   }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts {//        ，           
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts//     ，             
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster//        ，     ，      C
         add P' to cluster C
   }
}

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

アルゴリズム分析1.プライマリ・ループでどの点からループを開始するかは定義されていません.これは、異なる開始点が異なるクラスタリング結果をもたらす可能性があることを強調します.  2.一方の境界点がクラスクラスタ1に分割されてもよいし、クラスクラスタ2に分割されてもよい場合、その最終的なクラスクラスタは遍歴時の順序に関係し、これも上述の第1の理由である.  3.時間的複雑度では,各点に対してその近傍内のすべての点が要求され,複雑度はO(n 2)であるが,低次元空間でkdツリー,rツリーなどのデータ構造を用いればO(nlogn)に低減できる.拡張関数では2つの集合を結合する必要があり,複雑度はO(mn),m,nはそれぞれ2つの集合の大きさである.同時に,拡張関数では各コアポイントに対して集合集計操作が行われるため,アルゴリズムのほとんどの時間が拡張関数に費やされ,アルゴリズム完了時間も2つのアルゴリズムパラメータ,特にrに高度に依存することに気づいた.

アルゴリズム実装

dbscanの勉強を始めてから、本人は前後に複数のバージョンのアルゴリズムを実現し、最初の最適化されていないdbscanから、kdツリー、rツリーなどのデータ構造のバージョンを後に加え、wekaと互換性のためにwekaソースコードで修正された様々なバージョンまで、前後のバージョンは6、7つ以上あり、ここでは一つ一つリストされません.以下にkdツリー実装のバージョンを示す.private void cluster(List list){ dataSource = copyList(list);// ， init(dataSource);// ， kd ， r initNeibors();// r ， ， for(Point p : dataSource){ // if(p.getCls() == -1){ // List neibors = p.getNeibros(); // r if(neibors.size() < minPts){ // continue; } expandCluster(p, neibors, cls++); // } } } private void expandCluster(Point p, List neibors, int cls){ int size = neibors.size(); for(int i = 0; i < size; i++){ Point neibor = neibors.get(i); if(neibor.getCls() == -1){ // neibor.setCls(cls); } else { continue; } List neiList = neibor.getNeibros(); if(neiList.size() < minPts){ continue; } for(Point pp : neiList){ // ， r if(!list.contains(object2) &&(seed.getCls() == DataObject.NOISE || seed.getCls() == DataObject.NOTVISITED)){// list.add(object2); size++; } } } } // r private void initNeibors(){ for(Point p : dataSource){ List neibors = new ArrayList(); scanNeibor(p, tree, neibors);// tree kd p.setNeibros(neibors); } } // p r ，root ， private void scanNeibor(Point p, Point root, List neibors){ if(root == null){ return; } if(getDest(p, root) <= r){ neibors.add(root);// p } if(root.getType() == KDNode.LEAVE){ return;// } int axis = root.getAxis();// ， kd double[] attr1 = p.getAttr(); double[] attr2 = root.getAttr(); if(attr1[axis] <= attr2[axis]){// p ， scanNeibor(p, (Point)root.getLeft(), neibors); if(Math.abs((attr1[axis] - attr2[axis])) <= r){ // p r ， scanNeibor(p, (Point)root.getRight(), neibors); } } else {// scanNeibor(p, (Point)root.getRight(), neibors); if(Math.abs((attr1[axis] - attr2[axis])) <= r){ //p r scanNeibor(p, (Point)root.getLeft(), neibors); } } }