кластеризации большие данные с ELKI

Question

Я использую ELKI's AnderbergHierarchicalClustering для моих наборов данных с более чем 150000 наблюдений и для каждого наблюдения, я использую три переменные: lat, lng и price, и все они являются double.

У меня есть следующие проблемы:

• мой набор данных больше, чем принято одно (< = 65535 наблюдений)
• этот алгоритм также делает right shift для Agnes triangle - (size * (size - 1)) >>> 1 - это приходит до больших RAM нуждаются

для того, чтобы решить эту проблему, я решил разделить набор данных в перекрывающиеся подмножества 20000 obs.

Для 20000 obs Мне понадобится ~4.8GB RAM.

Я не знаю, какой был бы наилучший подход для разделения данных таким образом, чтобы результат кластера, примененный к подмножествам, был как можно ближе к результату кластеризации всего набора.

Answer 1

Если вы используете single-linkage, вы можете использовать SLINK, которому необходимо только O(n).

По-прежнему необходимо O(n^2) раз.

Hierarchical clustering не очень масштабируемый.

CLINK может сделать complete linkage с O(n) памяти, но качество результата, как правило, не очень хорошо (как правило, хуже, чем Anderberg с complete linkage).

Все остальные алгоритмы, которые у нас есть, O(n^2) в памяти, к сожалению.

Таким образом, около 65535 экземпляров вы попадете в стену с Java.

У меня есть один алгоритм в моем списке задач, который должен иметь возможность запускать в O(n log n), если я не ошибаюсь с index support. Но мне еще не удалось изучить его подробно - неясно, какой linkage strategies он может поддерживать, кроме single-linkage.

Если у вас есть много дубликатов, обязательно объедините их первым!