ELKI DBSCAN с R*-деревом

Я пытаюсь реализовать тестовое приложение кластеризации DBSCAN с использованием библиотеки ELKI. Мой набор данных 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), но я не могу понять, чего мне не хватает, чтобы использовать ELKI DBSCAN с оптимизацией R*-Tree.

Спасибо за любую помощь или предложения.


performance dbscan r-tree elki
person samuele.forconi    schedule 18.07.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если вы выберете эпсилон радиуса запроса слишком большим, каждый объект будет иметь O(n) соседей.

Тогда время выполнения будет O(n^2) или хуже, даже с поддержкой индексов; потому что размер ответа на каждый запрос равен O(n).

Если вы выберете эпсилон таким образом, что в среднем 10% объектов будут находиться в пределах эпсилон-радиуса, тогда время выполнения будет не менее O(n * 10% * n), то есть O(n^2).

Что хорошо показывает, как теоретическое время выполнения O(n log n) может не дать вам время выполнения O(n log n) на практике. R*-дерево может отвечать на запросы radius или kNN в среднем за O(log n) — для небольших наборов ответов, где размером набора ответов можно пренебречь. Более точный анализ, вероятно, даст время выполнения O(log n + |answer| log |answer|) (поскольку в настоящее время мы сортируем ответы по расстоянию; мы могли бы удалить это для некоторых алгоритмов).

Чаще всего алгоритм, который считается O(n*n), будет стоить вам O(n*n log n) времени выполнения, потому что для каждого объекта вы сортируете все остальные по расстоянию. К счастью, сортировка хорошо оптимизирована, поэтому лишние log n не имеют большого значения.

person Erich Schubert    schedule 18.07.2014
comment
Спасибо за Ваш ответ. Проблема заключалась именно в том, что у меня есть набор данных с точками, сгруппированными в небольшой области, и я использовал значение eps, которое было слишком большим, чтобы оптимизация R-Tree работала. Уменьшив значение eps, заработала оптимизация R-Tree и алгоритм стал намного быстрее. Спасибо за четкое объяснение проблемы. - person samuele.forconi; 04.08.2014