纸质男孩的聚类算法

我需要帮助根据特定标准选择或创建聚类算法.

想象一下,你正在管理报纸送货人员.

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

您希望对地址进行群集,以便将每个群集分配给传递人员.

交付人员或集群的数量不固定.如果需要,我总是可以雇用更多的送货人员,或者将他们分开.

每个群集应具有大约相同数量的地址.但是,如果群集的地址更加分散,则群集可能具有更少的地址.(另一种方式:每个群集包含最大地址数的最小群集数,群集中的任何地址必须以最大距离分隔.)

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

所以......想法？

UPDATE

如Arachnid的答案所述,街道网络图不可用.

我用Java编写了一个低效但简单的算法,看看我可以在一组点上做一些基本的聚类,或多或少如问题所述.

如果ps指定为ints的(x,y)坐标,则算法在列表上工作.它还需要三个其他参数:

radius(r):给定一个点,扫描附近点的半径是多少

max addresses(maxA):每个群集的最大地址数(点数)是多少？

min addresses(minA):每个群集的最小地址

设置limitA=maxA. 主要迭代: 初始化空列表possibleSolutions. 外部循环:为每一个点p在ps.初始化空列表pclusters.wps=copy(ps)定义了一个点工作清单.工作点wp=p. 内迭代:虽然wps不是空的.取出点wp在wps.确定所有的点wpsInRadius中wps是在<距离r从wp.wpsInRadius根据距离进行递增排序wp.保持第一min(limitA, sizeOf(wpsInRadius))点wpsInRadius.这些点形成一个新的集群(点列表)pcluster.添加pcluster到pclusters.pcluster从中删除点wps.如果wps不是空的,wp=wps[0]并继续内部迭代. 结束内部迭代.pclusters获得 聚类列表.将此添加到possibleSolutions. 结束外部迭代.

我们为每一个p在ps集群的列表pclusters中possibleSolutions.pclusters然后每个都加权.如果avgPC是possibleSolutions(全局)中每个群集avgCSize的平均点数,并且是每个pclusters(全局)的平均群集数,那么这是使用这两个变量来确定权重的函数:

  private static WeightedPClusters weigh(List pclusters, double avgPC, double avgCSize)
  {
    double weight = 0;
    for (Cluster cluster : pclusters)
    {
      int ps = cluster.getPoints().size();
      double psAvgPC = ps - avgPC;
      weight += psAvgPC * psAvgPC / avgCSize;
      weight += cluster.getSurface() / ps;
    }
    return new WeightedPClusters(pclusters, weight);
  }

现在最好的解决方案是pclusters重量最轻的.我们重复主要的迭代,只要我们能找到比之前最好的解决方案更好的解决方案(更轻的权重)limitA=max(minA,(int)avgPC).结束主要迭代.

请注意,对于相同的输入数据,此算法将始终产生相同的结果.列表用于保留顺序,并且不涉及随机.

为了了解该算法的行为,这是一个32点测试模式的结果图像.如果maxA=minA=16,那么我们找到2个16个地址的簇.

接下来,如果我们通过设置减少每个群集的最小地址数minA=12,我们找到3个12/12/8点的群集.

并且为了证明该算法远非完美,这里是输出maxA=7,但我们得到6个簇,其中一些很小.所以在确定参数时你仍然需要猜太多.请注意,r这里只有5个.

出于好奇,我在更大的随机选择点上尝试了算法.我添加了下面的图像.

结论？这花了我半天,它效率低下,代码看起来很丑,而且相对较慢.但它表明可以在短时间内产生一些结果.当然,这只是为了好玩; 将其变成实际有用的东西是困难的部分.

我认为你想要一种分层的集聚技术而不是k-means.如果您的算法正确,您可以在拥有正确数量的聚类时停止它.正如其他人提到的那样,您可以使用以前的解决方案为后续群集提供种子,这可能会给您带来显着的性能提升.

您可能需要仔细查看所使用的距离函数,尤其是在问题具有较高维度的情况下.欧几里德距离是最容易理解的,但可能不是最好的,看看马哈拉诺比斯等替代品.

我假设你真正的问题与提供报纸无关......

你所描述的是(多) - 车辆 - 路线问题(VRP).关于这个问题的不同变体有很多学术文献,使用了大量的技术(启发式,现成的求解器等).通常作者试图为具体实例找到好的或最佳的解决方案,这也意味着站点的聚类(一个车辆的路线上的所有站点).

但是,群集可能会受到重大更改,只有稍微不同的实例,这是您要避免的.不过,VRP-Papers中的某些内容可能会激发你的灵感......

如果您决定坚持使用显式聚类步骤,请不要忘记在所有聚类中包含您的分布,因为它是每个路径的一部分.

使用街道网格的图形表示来评估聚类可能比连接白色地图上的点(尽管两者都是TSP变体)产生更真实的结果.如果图表模型不可用,您可以使用出租车公制(| x_1 - x_2 | + | y_1 - y_2 |)作为距离的近似值.

您是否考虑过使用基于经济/市场的解决方案？将设置除以任意(但常数以避免随机效应)拆分为偶数子集(由交付人数确定).

为每个点分配一个成本函数,它将增加到图表的数量,并为每个额外点提供经济价值.

迭代允许每个人轮流拍卖他们的最差点,并给每个人一个最大的预算.

这可能与送货人们在现实生活中的想法非常吻合,因为人们会发现互换,或者会说"如果我不做这一两次,我的生活会变得那么容易.它也很灵活(对于例如,允许在距离任何其他地方一英里的地方相当容易地获得溢价).