Кластеризация на большом наборе данных

Question

Я пытаюсь кластеризовать большой (гигабайтный) набор данных. Чтобы кластеризовать, вам нужно расстояние каждой точки до каждой другой точки, так что вы получите матрицу расстояний размером N ^ 2, которая в случае моего набора данных будет порядка эксабайт. Pdist в Matlab, конечно, мгновенно взрывается;)

Есть ли способ сначала кластеризовать подмножества больших данных, а затем, возможно, объединить похожие кластеры?

Я не знаю, помогает ли это кому-нибудь, но данные представляют собой двоичные строки фиксированной длины, поэтому я рассчитываю их расстояния, используя расстояние Хэмминга (Distance = string1 XOR string2).

Answer 1

Упрощенная версия метода nice от Tabei et al., Одинарная или множественная сортировка во всех парах Поиск сходства , скажем, для пар с Hammingdist 1:

• sort allбитовые строки в первых 32 битах
• смотрят на блоки строк, в которых первые 32 бита одинаковы;эти блоки будут относительно небольшими
• pdist для каждого из этих блоков для Hammingdist (слева 32) 0 + Hammingdist (остальные) <= 1. </li>

Это пропускает долю, например, 32/ 128 из соседних пар, у которых есть Hammingdist (слева 32) 1 + Hammingdist (остальные) 0. Если вы действительно хотите это, повторите это с «first 32» -> «last 32».

метод может быть расширен.Возьмем, к примеру, Hammingdist <= 2 для 4 32-битных слов;несоответствия должны быть разделены как одно из 2000 0200 0020 0002 1100 1010 1001 0110 0101 0011, поэтому 2 слова должны быть 0, сортировать одинаково. </p>

(Кстати, sketchsort-0.0.7.tar равен 99%src / boost /, build /, .svn /.)

Answer 2

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

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

Answer 3

Как насчет сортировки в первую очередь? Может быть, что-то вроде модифицированной сортировки слиянием? Вы можете начать с фрагментов набора данных, которые поместятся в памяти для выполнения нормальной сортировки.

Как только у вас есть отсортированные данные, кластеризацию можно выполнять итеративно. Возможно, оставьте вращающийся центроид N-1 точек и сравните его с N-й точкой, которую вы читаете. Затем, в зависимости от порогового значения расстояния вашего кластера, вы можете объединить его в текущий кластер или создать новый.