加权K均值与GPS数据

Question

目标

• 累计存储位置GPS信息(经度、纬度)
• 周围商店区的人口总数(例如1 000 000居民)
• 使用K-方法确定最佳配送中心，给定商店GPS数据和当地人口(即，由于需求较高，配送中心离城市商店和农村商店更近)。

发行

1. 我一直在讨论如何将加权变量添加到k-均值算法中，但我不确定对变量进行加权的实际过程。例如，如果我有lat，long，和人口(以千计)(例如"New York“= [40.713, 74.005, 8406])，这难道不构成三维空间中的向心力吗？如果是这样的话，那么距离不是不适当地倾斜并且错误地代表了仓库配送中心的最佳位置吗？
2. 附加的研究暗示UPGMA，“非加权对组方法”，其中考虑了集群的大小。然而，我还没有完全回顾这种方法和与此方法相关的复杂之处。

参考资料

参考1：http://cs.au.dk/~simina/weighted.pdf (第5页)

还可以证明一些类似k-均值的算法，即k-中值和k-中介也是权可分的。详情见附录。观察到所有这些流行的目标函数都对体重高度敏感。

参考2：https://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf (第39页：“处理不同集群大小的能力”)

Answer 1

1)您只想在(经度、纬度)空间中做k-表示。如果你把人口作为第三维空间，你会把你的重心偏向于大型人口中心之间的中点，而这个中心往往相距很远。

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

3) k均值可能不是作业的最佳聚类算法，因为旅行时间与距离不成线性关系。而且，你基本上保证在一个大的人口中心中间永远不会有一个配送中心，这可能不是你想要的。我将使用DBSCAN，对于DBSCAN，scikit-learn有一个很好的实现：http://scikit-learn.org/stable/modules/clustering.html。