具有R*-树的ELKI DBSCAN
我正在尝试使用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 |时间使用简单的System.currentTimeMillis()在dbscan.run(db)周围进行基准测试。查看“时代”专栏，您可以看到趋势类似于n^2，而不是nlog(n)，但我无法理解使用带有R*-Tree优化的ELKI DBSCAN所缺少的内容。
谢谢您的帮助或建议。
回答 1
Stack Overflow用户
发布于 2014-07-18 17:02:07
如果您选择查询半径epsilon太大，每个对象都会有O(n)邻居。
那么运行时将是O(n^2)或者更糟，即使有索引支持；因为每个查询的答案大小都是O(n)。
如果选择epsilon，使平均10%的对象位于epsilon半径内，那么您的运行时将至少是O(n * 10% * n)，即O(n^2)。
这很好地说明了O(n log n)的理论运行时在实践中可能不会给您提供O(n log n)的运行时。对于小的答案集，R*-树平均可以在O(log n)中回答radius或O(log n)查询，其中答案集的大小可以忽略。更精确的分析可能会产生O(log n + |answer| log |answer|)的运行时(因为我们目前根据距离对答案进行排序；对于某些算法，我们可以删除这一点)。
通常情况下，假设为O(n*n)的算法将花费您的O(n*n log n)运行时，因为对于每个对象，您按距离对所有其他对象进行排序。幸运的是，排序得到了很好的优化，所以额外的log n并不重要。
https://stackoverflow.com/questions/24828093
复制相似问题
腾讯云开发者
