Вопросы Теги

Быстрый (

У меня есть 1 миллион пятимерных точек, которые мне нужно сгруппировать в k кластеров с k << 1 миллион. В каждом кластере не должно быть двух точек слишком далеко друг от друга (например, они могут ограничивать сферы с заданным радиусом). Это означает, что, вероятно, должно быть много кластеров размером 1.

Но! Мне нужно время работы, чтобы быть значительно ниже n ^ 2. n log n или около того должно быть в порядке. Причина, по которой я делаю эту кластеризацию, заключается в том, чтобы избежать вычисления матрицы расстояний для всех n точек (что занимает n ^ 2 времени или много часов), вместо этого я хочу чтобы просто вычислить расстояния между кластерами.

Я попробовал алгоритм pycluster k-means, но быстро понял, что он слишком медленный. Я также попробовал следующий жадный подход:

  1. Разделите пространство на 20 частей в каждом измерении. (так всего 20 ^ 5 частей). Я буду хранить кластеры в этих ячейках сетки в соответствии с их центроидами.

  2. Для каждой точки извлеките ячейки сетки, которые t находятся в пределах r (максимального радиуса ограничивающей сферы). Если имеется достаточно кластера, добавьте его в этот кластер, в противном случае создайте новый кластер.

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

Существуют ли какие-либо стандартные подходы к кластеризации быстрее, чем n ^ 2? Вероятностные алгоритмы в порядке.

25
задан Anony-Mousse 16 June 2015 в 21:16
поделиться