Обрабатывать матрицу очень большого расстояния в C (или C ++, если это может помочь)
Я реализую этот алгоритм кластеризации http://www.sciencemag.org/content/344/6191/1492.full (бесплатная версия) в C в моем программном обеспечении, и мне нужно построить матрицу расстояний, но в некоторых случаях размер набора данных (после удаления избыточности) огромен (n> 1 500 000 и еще больше, доходя до 4 000 000 на более сложные случаи). Моя проблема, даже выделение верхней треугольной матрицы будет ( (1500000*1500000) - 1500000) * 0.5 * sizeof(float) =~ 5.5e12 Bytes, Таким образом, распределение памяти не выполняется (даже на наших вычислительных узлах с 256 ГБ ОЗУ), и запись на диск в этом случае невозможна.
Помимо сокращения размера (который я буду смотреть) набора данных для кластеризации, у кого-нибудь есть идея техники, которую я мог бы использовать для аппроксимации и хранения этого количества информации?
Нотабене Как я сказал в заголовке, я использую C, и я также могу использовать C ++. Кроме того, если у кого-то есть другой алгоритм кластеризации (где число кластеров определяется самим алгоритмом), пожалуйста, предложите его мне.
Спасибо заранее за ваше время,
Решение
Возможно, вам придется отступить и пересмотреть свой алгоритм.
Во-первых, возможно, вам не нужно иметь матрицу расстояний между всеми парами точек данных. Возможно, вы могли бы сгруппировать одинаковые точки данных в ячейки данных, а затем создать матрицу расстояний между ячейками.
То есть начните с вычисления попарных расстояний между точками, но сохраняйте только относительно небольшие расстояния и указатели на «другую» точку. Вид очень разреженной матрицы более коротких расстояний. Это просто сделать параллельно.
Затем создайте ячейки данных, которые содержат группы точек с взаимно малыми расстояниями между ними. Например, если вы ограничиваете «короткие» расстояния таким образом, чтобы ячейки в среднем содержали, скажем, 50 точек данных, вы получите 1500000/50 = 30000 корзин.
Затем снова просмотрите ваши данные и вычислите расстояния между лотками. Это даст 30000 ^ 2 расстояния, что составляет матрицу около 4 ГБ. Кроме того, у вас все еще есть 30000 с 50 ^ 2 расстояниями внутри бункеров, что составляет еще 300 МБ. Этот объем данных вполне управляем.
Если замена расстояния между точками данных на расстояние между соответствующими ячейками является достаточной точностью для вашего приложения, которое будет работать. Все зависит от типа данных, с которыми вы имеете дело, и требований к точности вашего приложения.
Другие решения