Кластеризация ~ 100 000 коротких строк в Python

Question

Я хочу сгруппировать ~ 100 000 коротких строк по чему-то вроде расстояния в q-грамм или простого «расстояния в мешке» или, возможно, расстояния Левенштейна в Python. Я планировал заполнить матрицу расстояний (100 000, выбрать 2 сравнения), а затем выполнить иерархическую кластеризацию с помощью pyCluster . Но я сталкиваюсь с некоторыми проблемами с памятью еще до того, как оторвусь от земли. Например, матрица расстояний слишком велика для numpy.

aa = numpy.zeros((100000, 100000))
ValueError: array is too big.

Это кажется разумным занятием? Или я обречен на проблемы с памятью в этой задаче? Спасибо за вашу помощь.

Answer 1

100 000 * 100 000 * 32 бит = 40 ГБ, что будет много ОЗУ, поэтому да, вам нужно найти другой способ. (И даже если бы вы могли поместить эти данные в память, вычисление заняло бы слишком много времени.)

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

Answer 2

10 миллиардов элементов - это очень много.Я не знаю по q-граммам, но если эта матрица разрежена, вы могли бы использовать элемент dict с 200 000 элементов.

Answer 3

1. В машинном обучении существует метод под названием «Встраивание», который в принципе может искать решение этой проблемы, используя O (n + m) памяти вместо O * 1006. * (n * m) (n = 10 ^ 5 элементов, m = 10 ^ 5 элементов). К сожалению, я не знаю доступного исходного кода, который реализован в O (m + n). Смотри:

   Евклидово вложение данных о вхождении. Амир Глоберсон, Гал Чечик, Фернандо Перейра и Нафтали Тишби. Журнал исследований машинного обучения, JMLR, 8 (октябрь), 2007. pdf / код Matlab

2. Могут быть и другие решения. Я думаю, что вы должны задать этот вопрос на форуме людей, обучающихся машинному обучению, например, https://stats.stackexchange.com/, или даже более конкретно для языковой обработки: http://metaoptimize.com/qa/.

Answer 4

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

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