Недавно на работе мне дали список мест (около 70 тысяч+) с их лат и длинными координатами. Моя задача состояла в том, чтобы найти ближайшую точку из всех точек в списке.
Мой предшественник, который разработал первую версию, использовал самый простой и простые способы для этого вычисления – для каждой точки вычислить евклидовое расстояние со всеми другими точками. Это вычисление занимает около 30 минут, чтобы закончить, так как он включает в себя вычисление точек плавания 70K * 70K. Результаты хранятся в огромном вложенном списке, который также занимает много оперативной памяти.
Тем не менее, эта эффективность вычислений недопустима Следующий алгоритм был создан для повышения эффективности вычислений:
- Применить K-средние с кластерными центрами в этом наборе данных
- Для каждой точки, вместо того, чтобы вычислять парное расстояние со всеми другими точками, вычислить только парное расстояние с точками в одном кластере, а ближайшая точка в кластере будет ближайшей точкой в наборе данных.
Для каждого кластера вычисление выполняется ~ 700 * 700 раз. Поэтому в общей сложности выполняется вычисление 70 тыс. * 700 раз. Вычисление в 100 раз быстрее.
Фактически, кластеризация K-средних очень эффективна и эффективна по сравнению с парным расстоянием расстояния. После реализации этого алгоритма это заняло менее двух минут.
Впервые использование неконтролируемого обучения в домене не связанного с машинным обучением. Взволнован и хочу записать это. Однако в производстве эта методология не используется, поскольку технический лидер решает уменьшить количество местоположений кандидатов и пересказывать только тогда, когда в список добавлены новые точки местоположения.
Либо решить проблему, либо уменьшить проблему. Уроки на день
Оригинал: “https://dev.to/sunweiran1/unsupervised-clustering-for-faster-pairwise-distance-computation-52ae”