Знайти точки на карті, близькій до заданих точок

У мене є локус L точок (лат, довгий). І я хотів би знайти N = 10 балів (давайте назвемо їх складами) такими, що:

$$ loss = \ sum_ (l \ in L) max_ (w \ in W) (distance (l, w)) ^ 2 $$

мінімізовано

Чи є документований алгоритм чи підхід, який вирішує цю проблему? Зараз я думаю, що Excel може справлятися з цим завданням. Однак у мене є забагато даних для Excel, і це потрібно буде виконати в Python/Pandas.

3
Ви насправді не визначили, що ви маєте на увазі за дистанцією. Якщо точки розташовані близько один до одного, то, можливо, буде добре, використовуючи евклідову відстань, але технічно відстань на сферу (як і в лат., Lon) слід використовувати відстань Haversine .
додано Автор someonewithpc, джерело

2 Відповіді

Я можу сказати вам, як це зробити, але існує майже напевно більш швидка реалізація.

Припускаючи, що ви починаєте з кожної точки в $ L $ відстані до кожного складу, $ w \ in W $. Ці відстані слід розраховувати за формулою haversine .

Ви можете знайти відстань до найближчої точки $ N $ th в $ w $ за допомогою quickselect алгоритм. Це дуже схоже на алгоритм Quicksort, але лише для сортування тих деталей, які Ви турбуєтесь. Середній випадок для максимального вибору - $ O (N) $, але вам доведеться повторити для кожного $ l \ in L $.

Зауважте, що оскільки квадрат є монотонним для позитивних відстаней, вам потрібно лише звести до мінімуму

$ $ \ sum_ (l \ in L) max_ (w \ in W) (відстань (l, w)) $ $

I found a handy implementation of the quickselect algorithm on KoderDojo

2
додано
"вам потрібно лише звести до мінімуму ..." - але головна проблема тут - як згортати цей вираз?
додано Автор VividD, джерело
Просто зазначивши, що не варто квадратувати відстані haversine, що може заощадити трохи часу. Якщо б Ви використовували евклідову відстань, було б менш складно залишити їх як квадратну відстань, але я вважаю, що haversine дає вам відстань, а не квадрат відстані.
додано Автор someonewithpc, джерело
Швидкий вибір дуже приємний, дякую.
додано Автор William Entriken, джерело

Найчастіше у Scipy є інструменти для більшості з них.

locations = train[['latitude', 'longitude']].values
center = locations.mean(axis=0)
warehouses = np.repeat(np.expand_dims(center, 0), 20, 0)
warehouses = warehouses.flatten()

def Distances(warehouses):
    warehouses = np.reshape(warehouses, [20, 2])
    distances = scipy.spatial.distance.cdist(locations, warehouses)
    closests = distances.min(axis=1)
    other_way = distances.min(axis=0)
    return np.append(closests, other_way)

x = scipy.optimize.least_squares(Distances, warehouses, verbose=2)
1
додано
Приємно знайти Однак, я думаю, мінімакс та оптимізація найменших квадратів не дають такого ж результату.
додано Автор VividD, джерело
Якщо quickselect можна використовувати тут, це буде набагато швидше.
додано Автор William Entriken, джерело