Как вписать матрицу огромного расстояния в память?

Question

У меня огромная матрица расстояний размером aroud 590000 * 590000 (тип данных каждого элемента float16). Это будет соответствовать в памяти для алгоритма кластеризации ?? Если нет, то кто-нибудь может дать представление об использовании его в алгоритме кластеризации DBSCAN ??

Answer 1

590000 * 590000 * 2 байта (размер float16) = 696,2 ГБ ОЗУ

Он не помещается в память со стандартным компьютером. Кроме того, float16 преобразуется в float32 для выполнения вычислений (см. Python-numpy операции типа данных float16 и float8? ), поэтому он может использовать намного больше 700 ГБ ОЗУ.

Почему у вас квадратная матрица? Разве вы не можете использовать сжатую матрицу ? Он будет использовать половину памяти, необходимой для квадратной матрицы.

Answer 2

DBSCAN нужны только соседи каждой точки.

Так что, если бы вы знали соответствующие параметры (в чем я сомневаюсь), вы могли бы читать огромную матрицу по одной строке за раз и строить список соседей в пределах вашего порога расстояния. Предполагая, что менее 1% являются соседями (при таких огромных данных вы, вероятно, захотите пойти еще ниже), что уменьшит потребность в памяти в 100 раз.

Но обычно вы хотите вообще избегать вычисления такой матрицы !

Answer 3

Кластеризация (создание чанков) для уменьшения размера проблемы для DBSCAN может быть выполнена, например, при наличии областей с перекрывающимися регионами.

Размер перекрывающихся областей должен соответствовать вашей проблеме.

Найдите разумный размер для кусков вашей проблемы и перекрывающейся области.

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

Необходимо проверить, присутствуют ли элементы в одном кластере и в других чанках.

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

Я только что видел this :

Очевидно, проблема в нестандартной реализации DBSCAN в scikit-learn.DBSCAN не нужна матрица расстояний.

Но это, вероятно, было исправлено лет назад.

Какую реализацию вы используете?