Сгруппировать список географических c точек по расстоянию и ограничениям

Question

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

Для групповой близости я использовал DBSCAN

coordinates = [[lat,lng],[lat,lng]],[lat,lng]],[lat,lng]],[lat,lng]]]
distance_matrix = squareform(pdist(coordinates, (lambda u,v: haversine(u,v))))

#eps=0.1 => 100m radius, 50m linear
db = DBSCAN(eps=0.1, min_samples=2, metric='precomputed')
results = db.fit(distance_matrix)

Как я могу добавить ограничения в эту функцию?

Есть ли способ сделать это, используя что-то еще, кроме DBSCAN или HDBSCAN?

Answer 1

Это интересный вопрос. Я полагаю, это может быть сделано разными способами. Вот одно из решений для вас:

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
import seaborn as sns; sns.set()
import csv


df = pd.read_csv('C:\\your_path\\properties_2017.csv')
# df.head(10)
df = df.head(10000)

df.shape


df.dropna(axis=0,how='any',subset=['latitude','longitude'],inplace=True)

# Variable with the Longitude and Latitude
X=df.loc[:,['parcelid','latitude','longitude']]
X.head(10)

K_clusters = range(1,10)
kmeans = [KMeans(n_clusters=i) 

for i in K_clusters]
Y_axis = df[['latitude']]
X_axis = df[['longitude']]
score = [kmeans[i].fit(Y_axis).score(Y_axis)

for i in range(len(kmeans))] # Visualize
plt.plot(K_clusters, score)
plt.xlabel('Number of Clusters')
plt.ylabel('Score')
plt.title('Elbow Curve')
plt.show()

kmeans = KMeans(n_clusters = 10, init ='k-means++')
kmeans.fit(X[X.columns[1:3]]) # Compute k-means clustering.X['cluster_label'] = kmeans.fit_predict(X[X.columns[1:3]])centers = kmeans.cluster_centers_ # Coordinates of cluster centers.labels = kmeans.predict(X[X.columns[1:3]]) # Labels of each pointX.head(10)

X['cluster_label'] = kmeans.fit_predict(X[X.columns[1:3]])
centers = kmeans.cluster_centers_ # Coordinates of cluster centers.
labels = kmeans.predict(X[X.columns[1:3]]) # Labels of each pointX.head(10)

X.head(5)

X = X[['parcelid','cluster_label']]
X.head(5)


clustered_data = df.merge(X, left_on='parcelid', right_on='parcelid')
clustered_data.head(5)

centers = kmeans.cluster_centers_
print(centers)


X=df.loc[:,['parcelid','latitude','longitude']]
X.plot.scatter(x = 'latitude', y = 'longitude', c=labels, s=50, cmap='viridis')
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.5)

data = X label = kmeans.labels_

plt.subplots_adjust(bottom = 0.1)
plt.scatter(data.iloc[:, 1], data.iloc[:, 2], c=kmeans.labels_, cmap='rainbow') 

for label, x, y in zip(labels, data.iloc[:, 1], data.iloc[:, 2]):
    plt.annotate(
        label,
        xy=(x, y), xytext=(-20, 20),
        textcoords='offset points', ha='right', va='bottom',
        bbox=dict(boxstyle='round,pad=0.5', fc='red', alpha=0.5),
        arrowprops=dict(arrowstyle = '->', connectionstyle='arc3,rad=0'))

plt.show()

# labels pointing to each data point (this is a big jumbled together; you should probably select fewer data points to analyze).

Ссылка:

https://levelup.gitconnected.com/clustering-gps-co-ordinates-forming-regions-4f50caa7e4a1

Источник данных:

https://www.kaggle.com/c/zillow-prize-1/data

Answer 2

К сожалению, я думаю, что модель, которую вы хотите, должна быть разработана с нуля.

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

Цель: минимизировать количество кластеров, K Ограничение (1) Размер каждого кластера равен или меньше S (параметр) (2) Количество порядков в каждом кластере равно или меньше O (параметр) (3) Для выборки x и ее кластера Ck, dist (x, Ck) - минимум среди dist (x, C1), dist (x, C2), ..., dist (x, CK).

Решение этой проблемы потребует больших усилий. ..