3

いくつかの地理空間データをクラスター化しようとしていますが、以前にWEKAライブラリーを試しました。このベンチマークを見つけて、 ELKIを試してみることにしました。

ELKI を Java ライブラリとして使用しないようにというアドバイス(UI よりもメンテナンスが少ないと思われます) にもかかわらず、私は ELKI をアプリケーションに組み込みました。その結果には非常に満足していると言えます。データを保存するために使用する構造は、Weka が使用するものよりもはるかに効率的であり、空間インデックスを使用するオプションがあるという事実は、明らかにプラスです.

しかし、Weka の DBSCANの結果とELKI の DBSCANの結果を比較すると、少し戸惑います。実装が異なるとわずかに異なる結果が生じる可能性があることは認めますが、これらの違いの大きさから、アルゴリズムに(おそらく私のコードに)何か問題があると思います。クラスタの数とそのジオメトリは、2 つのアルゴリズムで大きく異なります。

記録のために、ELKI の最新バージョン (0.6.0) を使用しています。シミュレーションに使用したパラメーターは次のとおりです。

minpts=50 イプシロン=0.008

2 つの DBSCAN 関数 (Weka と ELKI 用) をコーディングしました。ここで、「エントリ ポイント」はポイントを含む csv であり、両方の「出力」も同じです: ポイント セットの凹包を計算する関数 (クラスタごとに 1 つ）。csvファイルをELKI「データベース」に読み込む機能は比較的単純なので、私の問題は次のようになると思います。

a) アルゴリズムのパラメータ化。b) 結果の読み取り (ほとんどの場合)。

DBSCAN をパラメーター化しても問題は発生しません。以前に UI でテストした 2 つの必須パラメーターを使用します。

ListParameterization params2 = new ListParameterization();
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.MINPTS_ID,        minPoints);
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.EPSILON_ID, epsilon);

クラスターを格納する構造の構成を完全には理解していないため、結果を読み取るのは少し難しいです。私の考えは、ポリゴンを生成するために、各クラスターを反復処理し、ポイントのリストを取得し、それを凹包を計算する関数に渡すことです。

    ArrayList<Clustering<?>> cs = ResultUtil.filterResults(result, Clustering.class);
    for (Clustering<?> c : cs) {
        System.out.println("clusters: " + c.getAllClusters().size());
      for (de.lmu.ifi.dbs.elki.data.Cluster<?> cluster : c.getAllClusters()) {
              if (!cluster.isNoise()){
                 Coordinate[] ptList=new Coordinate[cluster.size()];
                 int ct=0;
                    for (DBIDIter iter = cluster.getIDs().iter(); iter.valid(); iter.advance()) {
                        ptList[ct]=dataMap.get(DBIDUtil.toString(iter));
                        ++ct;
                    }                   
                //there are no "empty" clusters
                assertTrue(ptList.length>0);

                GeoPolygon poly=getBoundaryFromCoordinates(ptList);
                if (poly.getCoordinates().getGeometryType()==
                        "Polygon"){

                    try {
                        out.write(poly.coordinates.toText()+"\n");
                    } catch (IOException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }           

                }else
                    System.out.println(
                            poly.getCoordinates().getGeometryType());

              }//!noise
      }
    }

「ノイズ」がクラスターとして発生していることに気付いたので、このクラスターを無視しました (描画したくありません)。多くの例が見つからないため、これがクラスターを読み取る正しい方法であるかどうかはわかりません。また、いくつかの質問がありますが、まだ答えが見つかりません。

  • getAllClusters() と getTopLevelClusters() の違いは何ですか?
  • DBSCAN クラスターは「ネスト」されていますか?つまり、同時に多くのクラスターに属するポイントを持つことができますか? なんで？
  • ELKI の内部使用のため、ポイントを識別するためにデータベース ID を使用すべきではないことをどこかで読みましたが、各クラスター内のポイントのリストを取得する他の方法はありますか? ラベルにリレーションを使用できると読みましたが、実際にこれを実装する方法がわかりません...

私を正しい方向に導くことができるコメント、または ELKI の DBSCAN の結果セットを反復処理するためのコードの提案は、本当に歓迎されます! また、コードで ELKI の OPTICSxi を使用しました。これらの結果についてさらに質問がありますが、それは別の投稿に譲ると思います。

4

2 に答える 2

3

これは主に、かなり完全な回答を提供した @Anony-Mousse へのフォローアップです。

  • getTopLevelClusters()DBSCAN は階層クラスターを生成しgetAllClusters()ないため、DBSCAN についても同じことを行います。
  • DBSCAN クラスターはばらばらです。クラスターをisNoise()==trueシングルトン オブジェクトとして扱うことは、ノイズを処理するための最良の方法である可能性があります。実装によって返されるクラスターOPTICSXiも互いに素ですが、すべての子クラスターのメンバーを外側のクラスターの一部と見なす必要があります。凸包の場合、最初に子クラスターの凸包を計算するのが効率的な方法です。次に、親について、追加オブジェクトの凸包 + すべての子の凸包ポイントを計算します。
  • RangeDBIDs@Anony-Mousse が言及したアプローチは、静的データベースではかなりクリーンです。動的データベースでも機能するクリーンなアプローチは、オブジェクトを識別する追加の関係を持つことです。CSV ファイルを入力として使用する場合、行番号の一貫性に頼る代わりに、ラベルを含む非数値の列を追加しますobject123。論理的な観点からは、これが最善のアプローチです。オブジェクトを識別できるようにする場合は、オブジェクトに一意の識別子を付けます。;-)
  • ELKI を教育に使用し、その DBSCAN アルゴリズムを非常に慎重に検証しました ( DBSCAN のステップバイステップのデモはこちらで確認でき、ELKI の結果はこれと完全に一致します)。Weka の DBSCAN および OPTICS コードは、かなり前に学生によって提供されたものであり、同じ範囲で検証されたことはありません。簡単なチェックから、Weka はクラスの演習データ セットで正しい結果を生成しません。
  • 演習データ セットは各次元で同じ10 の拡張を持っているため、イプシロン パラメーターを 1/10 で調整でき、Weka の結果は解と一致するように見えます。したがって、@ Anony-Mousses の発見は正しいようです。Weka の実装では、データに [0;1] スケーリングが適用されます。
于 2014-05-14T09:36:22.817 に答える
2

DBIDs割り当て方法に注意すれば、ELKIの にアクセスできます。

静的データベースの場合、 はオブジェクトgetDBIDs()を返し、RangeDBIDsデータベースへのオフセットを与えることができます。これは非常に信頼できます。ただし、常にプロセスを再起動すると、DBIDs決定論的に割り当てられます (MiniGUI を使用している場合のみ、ジョブを再実行すると異なります!)

これも より効率的になりDBIDUtil.toStringます。

DBSCAN の結果は階層的ではないため、すべてのクラスターが最上位のクラスターである必要があります。

Weka に関しては、自動正規化を行う場合があります。次に、イプシロン値が歪められます。地理データについては、とにかく測地距離を好むでしょう。緯度と経度のユークリッド距離は意味がありません。

Wekas コードのこの部分を確認してください: EuclideanDataObject で使用される "norm" 関数。これは、Wekas DBSCAN がデータセットに正規化を強制しているように見えます! その後、結果が同じである場合は、データを [0:1] にスケーリングしてみてください (ELKI にこのためのフィルターがあると確信しています)。

このコード スニペットから判断すると、私は Weka のせいだと思います。上記のコードも、私には少し非効率に見えます。フィルター アプローチは、データ オブジェクトでこの強制的なフィルター処理よりも理にかなっています。

于 2014-05-13T18:50:21.190 に答える