1

ELKI ライブラリを使用して DBSCAN クラスタリング テスト アプリケーションを実装しようとしています。私のデータセットは 6 次元で、約 100.000 個のオブジェクトで構成されています。

コード内で R*-Tree ELKI 最適化を使用しようとしましたが、コードをベンチマークすると、まだ O(n^2) で動作しているようです。

これは、アプリケーション内で使用するコードです。

ListParameterization dbscanParams = new ListParameterization();
dbscanParams.addParameter(DBSCAN.Parameterizer.EPSILON_ID, eps);
dbscanParams.addParameter(DBSCAN.Parameterizer.MINPTS_ID, minPts);
dbscanParams.addParameter(DBSCAN.DISTANCE_FUNCTION_ID, EuclideanDistanceFunction.class);

DBSCAN<DoubleVector, DoubleDistance> dbscan = ClassGenericsUtil.parameterizeOrAbort(DBSCAN.class, dbscanParams);

ArrayAdapterDatabaseConnection arrayAdapterDatabaseConnection = new ArrayAdapterDatabaseConnection(featuresMatrix, featuresLabels);

ListParameterization dbparams = new ListParameterization();
dbparams.addParameter(AbstractDatabase.Parameterizer.INDEX_ID, RStarTreeFactory.class);
dbparams.addParameter(RStarTreeFactory.Parameterizer.BULK_SPLIT_ID, SortTileRecursiveBulkSplit.class);
dbparams.addParameter(AbstractDatabase.Parameterizer.DATABASE_CONNECTION_ID, arrayAdapterDatabaseConnection);
dbparams.addParameter(AbstractPageFileFactory.Parameterizer.PAGE_SIZE_ID, pageSize);

Database db = ClassGenericsUtil.parameterizeOrAbort(StaticArrayDatabase.class, dbparams);

db.initialize();

Clustering<Model> result = dbscan.run(db);

上記のコードを実行すると、次の結果が得られます。

| NUM_OBJECTS |  TIME(ms)  |
|-------------|------------|
| 4444        |  1508      |
| 8887        |  5547      |
| 17768       |  23401     |
| 35536       |  103733    |
| 71040       |  426494    |
| 142080      |  1801652   |

時間は、dbscan.run(db) の周りで単純な System.currentTimeMillis() を使用してベンチマークされます。時間の列を見ると、n^2 のような傾向であり、nlog(n) のような傾向ではないことがわかりますが、R*-Tree 最適化で ELKI DBSCAN を使用するために何が欠けているのか理解できません。

助けや提案をありがとう。

4

1 に答える 1

1

大きすぎるクエリ半径イプシロンを選択すると、すべてのオブジェクトにO(n)隣接オブジェクトが作成されます。

その場合、インデックスがサポートされていても、ランタイムはO(n^2)悪化します。各クエリの回答サイズは ですO(n)。

オブジェクトの平均 10% がイプシロン半径内にあるようにイプシロンを選択した場合、実行時間は少なくともO(n * 10% * n)になりますO(n^2)。

O(n log n)これは、 の理論上のランタイムが実際には のランタイムを提供しない可能性があることをよく示していますO(n log n)。AR*-tree は、平均して半径または kNN クエリに答えることができますO(log n)- 答えセットのサイズが無視できる小さな答えセットの場合。より正確な分析では、おそらく の実行時間が得られますO(log n + |answer| log |answer|)(現在、回答を距離で並べ替えているためです。一部のアルゴリズムではこれを削除できます)。

多くの場合、すべてのオブジェクトについて他のすべてのオブジェクトを距離でソートするため、想定されるアルゴリズムはランタイムにO(n*n)コストがかかります。O(n*n log n)幸いなことに、並べ替えは十分に最適化されているため、余分なlog nものはあまり問題になりません。

于 2014-07-18T17:02:07.640 に答える