0

DBSCAN アルゴリズムを実装する必要があります。この疑似コードから開始すると仮定します

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      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
         add P' to cluster C

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

私のコードは、Ubuntu Linux 64 ビットのAmazon EC2インスタンスで実行する必要があります。

関数regionQueryは、 MongoDBデータベースにクエリを実行して、P の eps 近傍内のすべてのポイントを取得します。

それで、あなたによると、パフォーマンスを向上させるために実装するのに最適なプログラミング言語は何ですか? C、PHP、Java (とは思いません)?

4

3 に答える 3

4

あなたはたくさんのポイントを持っていて、すぐに結果が必要だと思います。それ以外の場合は、ほとんど何でも使用できます。

私にとってはmap-reduceの仕事のようです

マップ部分は「未訪問のポイントごとに」ループになり、近隣、候補クラスターなどを含むデータ構造を出力する必要があります。ポイントがノイズとして分類される場合、何も放出しないはずです。

クラスターの拡張は部分を削減し、場合によってはファイナライズする必要があります-また、言語の選択はjavascriptであり、すべてがmongo内で行われます

于 2012-05-27T15:58:25.140 に答える
3

「並列 DBSCAN」を Google で検索すると、このアルゴリズムを並列化する方法について説明している記事が多数見つかります。通常、アルゴリズムはかなり変更されます。たとえば、クラスターのマージが必要になります。

Canopy の事前クラスタリングも、DBSCAN の適切な前処理ステップになる可能性があります。

于 2012-06-02T09:55:27.743 に答える
1

自分の質問に答えるのを忘れていました。最終的に DBSCAN アルゴリズムの MapReduce バージョンを実装しました。ここで見つけることができます(Hadoop)。

これは、どのように機能するかの擬似コードです。

function map(P, eps, MinPts)
    if P is unvisited then
        mark P as visited
        NeighborPts = regionQuery(P, eps)
        if sizeof(NeighborPts) < MinPts then
            do nothing
        else
            mark P as clusterized
            prepare the key
            create new cluster C
            C.neighborPoints = NeighborPts
            C.points = P
            emit(key, C)

function reduce(key, clusters, eps, MinPts)
    finalC is the final cluster
    for all C in clusters do
        finalC.points = finalC.points ∪ C.points
        for all P in C.neighborPoints do
            if P′ is not visited then
                mark P′ as visited
                NeighborPts′ = regionQuery(P′,eps)
                if sizeof(NeighborPts′) ≥ MinPts then
                    NeighborPts = NeighborPts ∪ NeighborPts′
                end if
            end if
            if P′ is not yet member of any cluster then
                add P′ to cluster C
            end if
于 2012-10-05T15:16:59.353 に答える