Есть набор из миллиона векторов в виде матрицы размерности (1000000, 100)
, нужно найти те пары, где расстояние по косинусу меньше определенного порога, но если решать в лоб: считать расстояние между каждой парой, то на задачу уйдет порядка 70 дней, даже с задействованием всех потоков процессора. Есть ли какой-то более оптимальный способ?
2 ответа
Вдруг кому пригодится. Сейчас появилось множество библиотек, которые очень быстро (но немного приблизительно) считают разные виды расстояний, в том числе и косинусные, на довольно больших наборах данных. Например: NMSLIB
, Annoy
, FAISS
.
Список актуальных библиотек (со ссылками) и тесты их производительности на разных датасетах можно посмотреть здесь.
-
-
@MaxU Да вообще удивительно, что библиотеки эти так то уже несколько лет как активно стали развиваться, а при этом довольно мало людей о них знают, я и сам тоже не так давно случайно наткнулся :) – CrazyElf 7 авг '20 в 12:08
Смените алгоритм. Вам ведь нужно найти не все расстояния, а только те, которые малы. Насколько мал угол, между векторами которые вам нужны? Если порог по углу меньше 1.e-4 (радиан) могу предложить следующее:
- Отнормируем все вектора на 1.
- Для каждого вектора вектора ищем максимальный по модулю элемент. На основе номера элемента и его знака распределяем вектор в одну из 200 групп. Составляем список векторов для каждой группы.
- Повторно пробегаем список векторов: Для каждого вектора ищем максимальный (по модулю) элемент X[max], а также элементы X[i], удовлетворяющие условию
|X[i]| > |X[max]| - α
где α - ваш порог отсечения по евклидовой норме (с учетом того, что вектора нормированы). Таким образом, при поиске близких векторов, можно проверить только те группы, которые соответствуют этим элементам (прошедшим порог).
Понятно, что можно группировать вектора бОльшее число групп (например по двум максимальным векторам), просто формула вычисления отсечения будет сложнее.
big-data
- вы работаете в кластере? Какой кластер? – MaxU 15 ноя '18 в 11:58scipy.spatial.distance.pdist(..., metric='cosine')
. Для 1.000.000 это займет в 10.000 раз дольше. Т.е. приблизительно 16 часов на простеньком ноутбуке. Главная проблема с памятью - все векторизированные методы работают со всей матрицей целиком. Для хранения вектора расстояний в вашем случае понадобится ~1.8 TB памяти - такие расчеты я бы делал на распределенном Spark кластере – MaxU 15 ноя '18 в 14:35