Python : 최소 평균 거리

Question

나는 사용자 위도 및 경도 집합과 사무실 위치 위도 경도 집합을 가지고 있습니다.

모든 사용자에게 최소 평균 거리가있는 사무실 위치를 찾아야합니다.

파이썬에서이 작업을 수행하는 효율적인 방법은 무엇입니까?

입력 : 사용자 1 (X1, Y1)
사용자 2 (X2, Y2)
오피스 1 (X3, Y3) 나는

예를 들어

3K 사용자와 40K 사무실 위치를 가지고 ...
Office 2 (x4, y4)

모든 사용자로부터 최소 평균 거리를 가진 사무실 위치를 파악해야합니다.

오피스 1 300m

오피스 2 = 모든 사용자로부터 150m

사용자 2. 평균 거리에서 사용자 1 및 200m에서 100m이다 = 유저 1 ~ 200m 모든 사용자로부터 사용자 2. 평균 거리로부터 400m이고

Office 2가 가장 적합한 위치입니다.

Answer 1

다음은 django의 geodjango 부분을 사용한 예입니다. shapely과 pyproj을 사용하여 동일한 작업을 수행 할 수 있습니다. (이 설치하는 약간의 고통이 될 수 있지만, 당신이 모든 설정을했으면, 이런 종류의 작업은 매우 간단하다.를)

from django.contrib.gis.geos import Point, MultiPoint 

WGS84_SRID = 4326 
office1 = Point(x1, y1, srid=WGS84_SRID) 
office2 = Point(x2, y1, srid=WGS84_SRID) 

# load user locations 
user_locations = [] 
with open("user_locations.csv", "r") as in_f: 
    # assuming wgs84 decimal degrees 
    # one location per line in format, 'lon, lat' 
    for line in in_f: 
     x, y = [float(i.strip()) for i in line.split(",")] 
     user_locations.append(Point(x, y, srid=WGS84_SRID)) 

# get points in a meters projection 
GOOGLE_MAPS_SRID = 3857 
office1_meters = office1.transform(GOOGLE_MAPS_SRID, clone=True) 
office2_meters = office2.transform(GOOGLE_MAPS_SRID, clone=True) 
user_locations_meters = [user_loc.transform(GOOGLE_MAPS_SRID, clone=True) for user_loc in user_locations] 

# centroid method 
mp = MultiPoint(user_locations, srid=4326) 
centroid_distance_from_office1 = mp.centroid.distance(office1_meters) 
centroid_distance_from_office2 = mp.centroid.distance(office1_meters) 

print "Centroid Location: {}".format(mp.centroid.ewkt) 
print("centroid_distance_from_office1: {}m".format(centroid_distance_from_office1) 
print("centroid_distance_from_office2: {}m".format(centroid_distance_from_office2) 

# average distance method 
total_user_locations = float(len(user_locations)) 
office1_user_avg_distance = sum(user_loc.distance(office1_meters) for user_loc in user_locations_meters)/total_user_locations 
office2_user_avg_distance = sum(user_loc.distance(office2_meters) for user_loc in user_locations_meters)/total_user_locations 

print "avg user distance OFFICE-1: {}".format(office1_user_avg_distance) 
print "avg user distance OFFICE-2: {}".format(office2_user_avg_distance) 

Answer 2

대부분 코드, http://en.wikipedia.org/wiki/Geometric_median#Computation 의 알고리즘을 구현 및 제공 당신은 무작위 점들의 집합에 기초한 사용의 예입니다.

NB : 이것은 두 개의 구 좌표가 어떻게 합쳐져야 하는지를 결정할 수 없기 때문에 평면상의 점에 대한 것입니다. 따라서 평면 투영으로 구 좌표를 미리 매핑해야하지만이 점은 이미 이전 답변에서 다루었습니다.

코드

from math import sqrt 
from random import seed, uniform 
from operator import add 
seed(100) 

class Point(): 
    """Very basic point class, supporting "+", scalar "/" and distances.""" 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 
    def __repr__(self): 
     return "("+repr(self.x)+","+repr(self.y)+")" 
    def __add__(self, P): 
     return Point(self.x+P.x, self.y+P.y) 
    def __div__(self, scalar): 
     return Point(self.x/float(scalar), self.y/float(scalar)) 
    def delta(self, P): 
     dx = self.x - P.x 
     dy = self.y - P.y 
     return sqrt(dx*dx+dy*dy) 

def iterate(GM,points): 
    "Simple implementation of http://en.wikipedia.org/wiki/Geometric_median#Computation" 
    # distances from the tentative GM 
    distances = [GM.delta(p) for p in points] 
    normalized_positions = [p/d for p,d in zip(points,distances)] 
    normalization_factor = sum(1.0/d for d in distances) 
    new_median = reduce(add, normalized_positions)/normalization_factor 
    return new_median 

# The "clients" 
nclients = 10 
points = [Point(uniform(-3,3),uniform(-3,3)) for i in range(nclients)] 

# Centroid of clients and total of distances 
centroid = reduce(add,points)/nclients 
print "Position of centroid:",centroid 
print "Sum of distances from centroid:", 
print reduce(add,[centroid.delta(p) for p in points]) 


print 
print "Compute the Geometric Median using random starting points:" 
nstart = 10 
for P0 in [Point(uniform(-5,5),uniform(-5,5)) for i in range(nstart)]: 
    p0 = P0 
    for i in range(10): 
     P0 = iterate(P0, points) 
    print p0,"-->",P0 

print 
print "Sum of distances from last Geometric Median:", 
print reduce(add,[P0.delta(p) for p in points]) 

출력

Position of centroid: (-0.4647467432024398,0.08675910209912471) 
Sum of distances from centroid: 22.846445119 

Compute the Geometric Median using random starting points: 
(1.2632163919279735,4.633157837008632) --> (-0.8739691868669638,-0.019827884361901298) 
(-2.8916600791314986,4.561006461166512) --> (-0.8929310891388812,-0.025857080003665663) 
(0.5539966580106901,4.011520429873922) --> (-0.8764828849474395,-0.020607834485528134) 
(3.1801819335743033,-3.395781900250662) --> (-0.8550062003820846,-0.014134334529992666) 
(1.48542908120573,-3.7590671941155627) --> (-0.8687797019011291,-0.018241177226221747) 
(-4.943549141082007,-1.044838193982506) --> (-0.9066276248482427,-0.030440865315529194) 
(2.73500702168781,0.6615770729288597) --> (-0.8231318436739281,-0.005320464433689587) 
(-3.073593440129266,3.411747144619733) --> (-0.8952513352350909,-0.026600471220747438) 
(4.137768422492282,-2.6277493707729596) --> (-0.8471586848200597,-0.011875801531868494) 
(-0.5180751681772549,1.377998063140823) --> (-0.8849056106235963,-0.02326386487180884) 

Sum of distances from last Geometric Median: 22.7019120091 

내 자신의 위치 (GM 대 중심이) 매우 다른이 경우 코멘트

,하지만 결과 비슷합니다. 나는 의 중요한 차이점 인 두 지점과 평균 거리 주변에 클러스터링이 있거나 몇 가지 기능이 라인 (도로)이라고 말하면 평균 거리가됩니다.

결국, 속도를 높일 수 있습니다 numpy을 사용하여 작업을 수행 한 결과, 제한된 시간의 리소스로 인해 numpy을 피할 수있었습니다 :)