python - 带 GPS 数据的加权 K 均值

Question

目标

• 汇总商店位置 GPS 信息(经度、纬度)

• 商店周围区域的人口总数(例如 1,000,000居民)

• 使用 K-means 确定最佳配送中心，给定商店 GPS 数据和本地人口(即配送中心与农村商店相比，由于较高的成本，它们距离城市商店更近需求)。

问题

1. 我去过researching关于如何将加权变量添加到 k 均值算法，但我不确定加权变量的实际过程。例如，如果我有[纬度、经度和人口(以千为单位)](例如“纽约”= [40.713, 74.005, 8406])，这不会在 3 中构造质心吗维空间？如果是这样，距离是否会不正确地倾斜并错误地表示仓库配送中心的最佳位置？
2. 附加research提到 UPGMA，“未加权配对方法”，其中考虑了簇的大小。但是，我还没有完全审查此方法以及与此方法相关的复杂性。

引用文献

引用文献1:http://cs.au.dk/~simina/weighted.pdf (第 5 页)

It can also be shown that a few other algorithms similar to k-means, namely k-median and k-mediods are also weight-separable. The details appear in the appendix. Observe that all of these popular objective functions are highly responsive to weight.

引用文献2:https://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf (第 39 页:“处理不同簇大小的能力”

Answer 1

1) 您只想在(经度，纬度)空间中进行 k 均值。如果将人口添加为第三个维度，您的质心将偏向大型人口中心之间的中点，而这些中心通常相距很远。

2) 在 k 均值中加入权重的最简单方法是根据其人口权重重复一个点(经度、纬度)。

3) k-means 可能不是该工作的最佳聚类算法，因为行进时间不随距离线性缩放。此外，基本上可以保证您永远不会在大型人口中心中间设立一个配送中心，这可能不是您想要的。我会使用 DBSCAN，scikit-learn 有一个很好的实现: http://scikit-learn.org/stable/modules/clustering.html