纸质男孩的聚类算法

Question

纸质男孩的聚类算法

car*_*ier 32 language-agnostic algorithm cluster-analysis

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

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

您有一组街道地址,每个地址都经过地理编码.
您希望对地址进行群集,以便将每个群集分配给传递人员.
交付人员或集群的数量不固定.如果需要,我总是可以雇用更多的送货人员,或者将他们分开.
每个群集应具有大约相同数量的地址.但是,如果群集的地址更加分散,则群集可能具有更少的地址.(另一种方式:每个群集包含最大地址数的最小群集数,群集中的任何地址必须以最大距离分隔.)
对于奖励积分,当数据集被更改(地址被添加或删除),并且算法被重新运行时,如果群集保持尽可能不变将是好的(即,这排除了简单的k均值聚类,这是随机性质).否则送货人会发疯.

所以......想法？

UPDATE

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

Answer 1

elj*_*nso 20

我用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<Cluster> 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);
  }

Run Code Online (Sandbox Code Playgroud)

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

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

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

替代文字