DBScan

DBScanという技をラーニング

論文
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1980
簡単な説明
http://ibisforest.org/index.php?DBSCAN

x-means
http://d.hatena.ne.jp/m-a-o/20100610#p1
などと同じく、クラスタ数を指定する必要がないクラスタリング手法

具体的には、点集合が与えられた時、点を二種類に分類する。データ間の距離が与えられているとして、距離eps以内にN個以上の点があるような点をcore pointと呼び、N個未満しかないような点をborder pointと呼ぶ。ただし、epsとNはクラスタリング時に指定するパラメータ。つまり大雑把には、ある程度高密度にデータが集積してる点と、そうでない例外的な点を分ける。互いに距離eps以内にあるcore point同士を同じクラスターに入れるようにすると、core pointのクラスタリングができる。

一方、border pointについては、次の3つの状況
がありえる
(1)距離eps以内にあるcore pointがない
(2)距離eps以内にあるcore pointは全て同一のクラスターに属する
(3)距離eps以内にあるcore pointが複数のクラスターに属する
(1)の場合、そのborder pointはNoiseとして扱われる。(2)の場合は、近くのcore pointが属するクラスターに入れてやればよい。(3)の場合は、どうすればよいか。論文では、このケースを考慮し忘れている気がする。(3)のようなことが起きると、一意にクラスタリングできない。

(3)のようなことが起きる例として、例えば

S0 = [(0.0 , 0.0)]
S1 = [(0.99+0.1*n , 0) for n in xrange(10)]
S2 = [(-0.99-0.1*n , 0) for n in xrange(10)]
S=S0+S1+S2

のような点集合を考えて、(eps,N)=(1.0 , 3)とすればよい。距離は、普通にユークリッド距離で測る。もし、S1とS2の点が(論文Definition5の意味で)同じクラスターに入るとすると、S1の点とS2の点は互いにdensity-connectiveにならない。一方、これらがそれぞれ別のクラスターに入るとすると、S0の点は、どちらからもdensity-reachableなので、クラスターの極大性に反する。

まあ、こういうことは些細なケースであると言えなくもない。論文にあるアルゴリズムをそのまま実装すると、上記のようなケースで、S0がS1のクラスターに含まれるか、S2のクラスターに含まれるかは、点集合についてのループで最初に出現するcore pointがS1に属するかS2に属するかで決まる。些細なこととは言いつつ、(3)のような、どっちつかずが一番タチが悪くて、これがなければ別にN=1でよいともいえる。こうすれば、単に距離epsを閾値として、データを分類するだけ。実際にクラスタリングすると、大体は(3)のような奴のせいで、分かれてほしいクラスターがくっついたり、それを避けようとすると、くっついてほしいとこが分かれるジレンマに陥る。

x-meansなんかだと、各クラスターがある点の周りにランダムに分布するような時はうまくいって、クラスターの形状は超球状になるのだと思う。現実問題としては、各クラスターがある点の周りに正規分布しているものの、分散が方向に依存して、クラスター形状は超楕円的になる場合が多そうだけれど、分散が非等方的な場合は、どうすればよいのか知らない

一方で、距離関数の作り方の都合とかから、各クラスターがある点の周りに正規分布してくれるとは言えないようなケースも多々あると思う。DBScanは、そういう場合に有効であることを期待されている。

Nとepsをどう決定するのかというのは、当然の疑問で、論文にも最後の方に怪しいことが書いてあるが、とりあえず、自動的に決定できないらしい。

とりあえず、適当に実装

def dbscan(Pts , distance , eps , minPts):
  visited = set([])
  Noise = set([])
  clusters = []
  for P in Pts:
    if P in visited:continue
    visited.add(P)
    seeds = [q for q in Pts if distance(P,q)<eps and P!=q]
    if len(seeds)<minPts:
       Noise.add(P)
    else:
       cluster = [P]
       while 1:
         if len(seeds)==0:break
         Q = seeds.pop()
         if not (Q in visited):
            N = [q for q in Pts if distance(Q,q)<eps and Q!=q]
            if len(N)>=minPts:
               seeds += N
         if not (Q in visited) or (Q in Noise):
            cluster.append(Q)
            visited.add(Q)
            if Q in Noise:Noise.remove(Q)
       clusters.append( cluster )
  return (clusters,Noise)

if__name__=="__main__":
   sqrt = __import__("math").sqrt
   S0 = [(0.0 , 0.0)]
   S1 = [(0.99+0.1*n , 0) for n in xrange(10)]
   S2 = [(-0.99-0.1*n , 0) for n in xrange(10)]
   S=S0+S1+S2
   dbscan(S , lambda x,y:sqrt((x[0]-y[0])**2+(x[1]-y[1])**2) , 1.0 , 3)