algorithm - 纸男孩的聚类算法

Question

我需要根据某些条件选择或创建聚类算法的帮助。

想象您正在管理报纸派递人员。

您有一组街道地址，每个街道地址都经过地理编码。

您想对地址进行聚类，以便将每个聚类分配给一个送货人员。

交付人数或集群的数量是固定的。如果需要，我可以随时雇用更多的送货人员，或解雇他们。

每个群集应具有大约相同数量的地址。但是，如果群集的地址散布得更多，则群集的地址可能会更少。 (换句话说:最小群集数，其中每个群集包含最大数量的地址，并且群集内的任何地址都必须以最大距离分隔。)

对于奖励积分，当更改数据集(添加或删除地址)并重新运行算法时，如果聚类保持尽可能不变就很好(即，这排除了简单的k均值聚类，本质上是随机的)。否则送货人员会发疯。

那么...想法？

更新

如Arachnid的答案所述，街道网络图不可用。

Answer 1

我认为您想要hierarchical agglomeration技术而不是k-means。如果您的算法正确，则可以在拥有正确数量的集群时将其停止。就像其他人提到的那样，您可以使用先前的解决方案为后续的群集提供种子，这可能会给您带来明显的性能改进。

您可能需要仔细查看所使用的距离函数，尤其是在问题具有高维的情况下。欧氏距离是最容易理解的，但可能不是最佳距离，请看诸如马哈拉诺比斯之类的替代方案。

我想您的真正问题与送报纸无关...