У меня есть 2 000 000 точек в 100-мерном пространстве.Как я могу кластеризовать их в K (например, 1000) кластеров?

Question

Проблема заключается в следующем. У меня есть M изображений и я извлекаю N объектов для каждого изображения, а размерность каждого объекта равна L. Таким образом, у меня есть M * N объектов (2 000 000 для моего случая), и у каждого объекта есть L размерность (100 для моего случая). Мне нужно сгруппировать эти функции M * N в K кластеров. Как мне это сделать? Спасибо.

Answer 1

Хотите ли вы 1000 кластеров изображений, или объектов, или пар (изображений, объектов)?
В любом случае это звучит так, как будто вам придется уменьшить данные и использовать более простые методы.

Одна возможность - двухпроходный K-кластер:
а) разделить 2 миллиона точек данных на 32 кластера,
б) разделить каждый из них на 32 больше.
Если это работает, результирующие кластеры 32 ^ 2 = 1024 могут быть достаточно хороши для вашей цели.

Тогда вам действительно нужны 100 координат? Можете ли вы угадать 20 самых важных, или просто попробуйте случайные подмножества из 20?

Существует огромная литература: Google +image "dimension reduction" дает ~ 70000 показов.

Answer 2

Хорошая хитрость при кластеризации миллионов точек - это выборка их, кластеризация выборки, а затем добавление оставшихся точек к существующей выборке

Answer 3

Алгоритмы EM-дерева и K-дерева в проекте LMW-tree могут кластеризовать проблемы, такие большие и большие. Наш последний результат - кластеризация 733 миллионов веб-страниц в 600 000 кластеров. Существует также потоковый вариант EM-дерева, в котором набор данных передается с диска для каждой итерации.

Answer 4

Вы пометили вопрос "k-means". Почему вы не можете использовать K-средства? Это вопрос эффективности? (лично я использовал k-средних в двух измерениях) Или это вопрос о том, как кодировать алгоритм k-средних?

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