报童聚类算法

Question

我需要帮忙根据特定标准选择或创建一个聚类算法。

想象一下，您正在管理报纸投递员。

• 您有一组街道地址，每个地址都有地理编码。
• 您希望将地址进行聚类，以便每个聚类分配给一个投递员。
• 投递员或聚类的数量不固定。如果需要，我可以随时雇用更多投递员或解雇他们。
• 每个聚类应该具有大约相同数量的地址。但是，如果一个聚类的地址更为分散，则其中可能会有更少的地址。(换句话说：每个聚类包含最大数量的地址的最小聚类数，并且聚类内任何地址之间必须相互分开一定距离。)
• 额外加分项：当数据集发生改变（添加或删除地址）并重新运行算法时，最好让聚类尽可能保持不变（即排除简单的k均值聚类，因为它是随机的）。否则投递员会发疯。

那么... 有什么想法吗？

更新

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

- carrier

---

那么你真的想要均衡每个集群的交付时间（这可能对应于旅行时间）吗？ - ctd

我一直在想作业，直到看到那个“疯狂”的词。这让它闻起来像是“过度工作的程序员” :) - alphadogg

@alphadogg 哪一行是疯狂的？ - carrier

@carrier：是的，最后一个。老师不会关心假设的送货人... :) - alphadogg

@Alphadog 不知道你的老师怎么样，但我的老师会这样做（尤其是作为额外学分）...不过我的老师有点虐待狂... - Omar Kooheji

Answer 1

我用Java编写了一个低效但简单的算法，以查看我能够多接近对一组点进行基本聚类的描述。该算法适用于指定为int的(x,y)坐标列表ps。它还需要其他三个参数：

1. 半径（r）：给定一个点，扫描附近点的半径是多少？
2. 最大地址数（maxA）：每个簇中的最大地址（点）数是多少？
3. 最小地址数（minA）：每个簇中的最小地址数是多少？

将limitA设置为maxA。 主迭代： 初始化空列表possibleSolutions。 外部迭代：对于ps中的每个点p。 初始化空列表pclusters。 定义一个点工作列表wps=copy(ps)。 工作点wp=p。 内部迭代：当wps不为空时。 从wps中删除点wp。确定在距离wp小于r的wps中的所有点wpsInRadius。按照与wp的距离升序排序wpsInRadius。保留wpsInRadius中前min(limitA, sizeOf(wpsInRadius))个点。这些点形成一个新的聚类（点列表）pcluster。将pcluster添加到pclusters中。从wps中删除pcluster中的点。如果wps不为空，则wp=wps[0]并继续内部迭代。 结束内部迭代。 获得聚类列表pclusters。将其添加到possibleSolutions中。 结束外部迭代。

我们对于每个在ps中的p，都有一个possibleSolutions中pclusters列表。每个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);
  }

最佳解决方案现在是具有最小权重的pclusters。只要我们可以找到比先前最佳解决方案（较小的权重）更好的解决方案（限制为limitA=max(minA,(int)avgPC)），我们就会重复主要迭代。 结束主要迭代。 请注意，对于相同的输入数据，此算法将始终产生相同的结果。列表用于保留顺序，并且没有涉及任何随机性。

为了查看此算法的行为，这是一个由32个点的测试模式生成的结果图像。如果maxA=minA=16，那么我们会发现2个具有16个地址的聚类。
_{(来源：paperboyalgorithm at sites.google.com)} 接下来，如果我们通过设置minA=12来减少每个聚类的最小地址数，我们会发现3个点的12/12/8聚类。

_{(来源：paperboyalgorithm at sites.google.com)}

为了说明该算法远非完美，这里展示了maxA=7的输出结果，但我们得到了6个簇，其中一些很小。因此，在确定参数时仍需要进行太多的猜测。请注意，这里的r只有5。

_{(来源：paperboyalgorithm at sites.google.com)}

出于好奇，我尝试对一组更大的随机选择点运行该算法。我添加了下面的图片。

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

_{(来源：paperboyalgorithm at sites.google.com)}

_{(来源：paperboyalgorithm at sites.google.com)}

- eljenso

---

我将提交一个元请求，让我可以投两次票，以表彰你在这里的出色工作。 - SqlRyan

Answer 2

您所描述的是一个（多）车辆路径问题（VRP）。关于这个问题有很多学术文献，使用了各种各样的技术（启发式算法、现成的求解器等）。通常作者会尝试为具体实例找到好的或最优的解决方案，这也意味着站点的聚类（所有在一个车辆路线上的站点）。

然而，聚类可能会因为略微不同的实例而发生重大变化，这正是您想要避免的。但是，VRP论文中的一些内容可能会给您带来灵感...

如果您决定坚持明确的聚类步骤，请不要忘记将您的分配包括在所有聚类中，因为它是每条路线的一部分。

使用街道网格的图形表示来评估聚类可能会产生比在白色地图上连接点更真实的结果（虽然两者都是TSP变体）。如果没有图形模型可用，您可以使用出租车距离度量（|x_1 - x_2| + |y_1 - y_2|）作为距离的近似值。

- Christoph

Answer 3

我认为你需要一种分层凝聚技术，而不是k-means。如果算法正确，可以在获得正确的聚类数时停止它。正如其他人提到的，您可以使用以前的解决方案作为后续聚类的种子，这可能会显着提高性能。

如果您的问题具有高维度，请仔细查看您使用的距离函数，特别是欧几里德距离虽然最容易理解，但可能不是最好的选择，可以考虑其他替代方法，例如马氏距离。

我假设您真正的问题与投递报纸无关...

- Simon

Answer 4

你考虑过使用经济/市场化的解决方案吗？将设置分成均匀子集（由送货人数量确定），并为每个点分配一个代表其对图形的贡献程度的成本函数，并赋予每个额外的点一个经济价值。轮流允许每个人拍卖他们最差的点，并给每个人一个最大预算。这可能与送货人在现实生活中的思维方式相当吻合，因为人们会找到交换，或者会说“如果我不做这一两个点，我的生活会变得更轻松”。它也非常灵活（例如，可以很容易地为远离其他任何点的一个点提供溢价）。

- Nick Fortescue

Answer 5

我会采取不同的方法：将街道网络视为一个图形，每条街道的每一侧都有一条边，找到一个将该图形分割成n个部分的方案，每个部分的长度不超过给定长度，以便每个报童可以沿着单一连续路径从起点骑行到终点。这样，您就可以避免让人们走相同的路线（例如，在要求覆盖街道两侧而不覆盖周围所有街道时）。

- Arachnid

---

这很好，但正如问题所述，地址已进行地理编码，这是唯一可用的信息。 没有街道网络图。 - carrier

Answer 6

这是一种快速而不精确的方法，可以发现你的“集群”位置。这个方法的灵感来自于游戏“扫雷”。

将整个交付空间划分为一个方格网格。注意 - 在这个方法能够有效之前，需要调整网格大小。我的直觉告诉我，一个大致与物理社区街区相同大小的正方形将是一个好的起点。

循环遍历每个正方形，并存储每个块中交货地点（房屋）的数量。使用第二个循环（或第一次循环的一些巧妙方法）存储每个相邻块的交货点数。

现在，您可以以类似于照片处理软件的方式操作此网格。通过找到某些相邻块中没有交货点的块，可以检测到集群的边缘。

最后，您需要一个系统，结合交付数量和总行驶里程来创建和分配路线。可能会有一些孤立的集群只需要进行几次交付，还有一两个超级集群，其中许多家庭非常靠近彼此，需要在同一集群中派出多个交付人员。必须访问每个家庭，这是您的第一个限制条件。

推导出任何一个交付人员单次运行允许行驶的最大距离。接下来，对每个人的交付次数也做同样的处理。

路由算法的第一次运行将分配一个单个的交付人员，将他们发送到任何未完成所有交付的随机集群，让他们进行交付，直到达到他们的交付限制或他们已经向集群中的所有家庭交付。如果他们达到了交付限制，则通过将他们送回基地结束路线。如果他们可以安全地前往最近的集群然后回家而不超过最大旅行距离，请重复以上步骤。

一旦当前交付人员的路线完成，检查是否有尚未进行交付的家庭。如果是这样，请分配另一个交付人员，并重复上述算法。

这将生成初始路线。我会将所有信息 - 每个正方形的位置和尺寸，每个正方形内的房屋数量及其所有直接邻居，每个正方形所属的集群，交付人员及其路线 - 存储在数据库中。

我将把重新计算的程序留给您 - 但是，将所有当前路线、集群等信息存储在数据库中，将使您能够保留所有历史路线，并尝试各种情况，以了解如何最好地适应变化，从而对现有路线进行最少的更改。

- Bork Blatt

Answer 7

这是一个典型的问题，值得采用优化解决方案而不是试图解决“最优解”。它在某些方面类似于“旅行商问题”，但您还需要在优化过程中对位置进行分段。

我已经成功地使用了三种不同的优化算法来解决此类问题：

1. 模拟退火算法
2. 大洪水算法
3. 遗传算法

使用优化算法，我认为您已经描述了以下“目标”：

1. 每个报童负责的地理区域应该尽量小。
2. 每个报童服务的订户数量应该大致相等。
3. 每个报童行驶的距离应该大致相等。
4. (你没有提到，但可能很重要的一点)路线应该以起点为终点。

希望这能让你有所启发！

* 编辑 *

如果你不关心路线本身，那么可以消除上述第3和第4个目标，也许可以更加符合你的奖励要求。

如果你考虑人口统计信息(如人口密度、订阅采用率和退订率)，你可以使用上述优化技术，从而消除了需要在订户采用或取消你的服务时重新运行算法的必要性。一旦集群被优化，它们就会保持平衡，因为每个集群的速率都与其他集群的速率匹配。

唯一需要重新运行算法的情况是当外部因素(如经济衰退/萧条)导致某个人口群体的行为发生变化时。

- Steve Moyer

---

在我的情况下，“路线应该结束于起点”的规则并不适用。事实上，我并不关心分配路线，只关心地址集合。它们可以自行处理路由。 - carrier

路由与实际路径无关，只是路线1是A->B-C，路线2是E->D->G。 - Jonke

+1 表示该问题是一个 OR（运筹学）问题。 - Jonke

@carrier...如果集群被一条主要的州际公路分成两半怎么办？仅仅在任何地方放置一个集群并不能保证有可路由的解决方案...请查看我的编辑，基于这些标准的缺失。 - Steve Moyer

@steve moyer...我没有人口密度、订阅采纳/取消率等人口统计信息...我所拥有的，就是我在问题描述中所陈述的。 - carrier

@carrier ... 你有当前的列表 ... 它包含了每个地区的起始订阅密度 ... 你可以随着时间收集其他的统计数据。 - Steve Moyer

Answer 8

与其使用聚类模型，我认为你真正想要的是一种Set Covering位置模型的变体，其中还有一个额外的限制条件来覆盖每个设施所覆盖的地址数量。我在网上找不到一个好的解释。你可以看一下this page，但他们是使用面积单位解决的，而你可能想要在欧几里得空间或网络空间中解决它。如果你愿意找到一些纸质书籍，可以查阅Daskin的《网络和离散位置》第4章。

- Chris Upchurch

Answer 9

很好的简单聚类算法调查。不过还有更多： http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html

- alphadogg

Answer 10

也许需要对客户进行最小生成树分组，根据与报童所在位置的地区进行划分。使用 Prim 或者 Kruskal 算法并将房屋之间的距离作为权重来获取最小生成树。

- sfossen