我需要根据特定标准选择或创建聚类算法的帮助。
想象一下，您正在管理送报人员。
所以……想法？
更新
如 Arachnid 的回答中所述，街道网络图不可用。
我用 Java 编写了一个低效但简单的算法，看看我可以多接近在一组点上进行一些基本的聚类，或多或少如问题中所述。
ps如果 (x,y) 坐标指定为ints ，则该算法适用于列表。它还需要三个其他参数：
r): 给定一个点，扫描附近点的半径是多少maxA）：每个集群的最大地址（点）数是多少？minA)：每个集群的最小地址设置limitA=maxA。
主迭代：
初始化空列表possibleSolutions。
外部迭代：对于p. ps初始化空列表pclusters。定义了一个点的工作清单wps=copy(ps)。工作点wp=p。
内部迭代： whilewps不为空。删除 中的点wp。wps确定距离 < fromwpsInRadius的所有点。根据与 的距离升序排列。将第一点保留在. 这些点形成一个新的集群（点列表）。添加到. 从中删除点。如果wpsrwpwpsInRadiuswpmin(limitA, sizeOf(wpsInRadius))wpsInRadiuspclusterpclusterpclusterspclusterwpswps不为空，wp=wps[0]继续内迭代。
结束内部迭代。
获得集群列表pclusters。将此添加到possibleSolutions.
结束外部迭代。
我们有一个集群列表中的p每一个。然后每一个都被加权。如果是（全局）中每个簇的平均点数，并且是每个（全局）中的平均簇数，那么这是使用这两个变量来确定权重的函数：pspclusterspossibleSolutionspclustersavgPCpossibleSolutionsavgCSizepclusters
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 个地址的集群。
（来源：sites.google.com 上的 paperboyalgorithm）
接下来，如果我们通过设置 减少每个集群的最小地址数minA=12，我们会找到 12/12/8 个点的 3 个集群。
（来源：sites.google.com 上的 paperboyalgorithm）
为了证明该算法远非完美，这里是输出maxA=7，但我们得到了 6 个集群，其中一些集群很小。所以在确定参数的时候还是要猜测太多。请注意，r这里只有 5 个。
（来源：sites.google.com 上的 paperboyalgorithm）
只是出于好奇，我在一组更大的随机选择的点上尝试了该算法。我添加了下面的图片。
结论？这花了我半天的时间，效率低下，代码看起来很难看，而且速度比较慢。但它表明在短时间内产生一些结果是可能的。当然，这只是为了好玩；把它变成真正有用的东西是困难的部分。
您所描述的是（多）车辆路由问题（VRP）。有很多关于这个问题的不同变体的学术文献，使用了各种各样的技术（启发式、现成的求解器等）。通常，作者试图为具体实例找到好的或最佳解决方案，这也意味着站点的聚类（一辆车路线上的所有站点）。
但是，集群可能会发生重大变化，实例略有不同，这是您要避免的。不过，VRP 论文中的某些内容可能会激发您的灵感……
如果您决定坚持显式聚类步骤，请不要忘记将您的分布包含在所有聚类中，因为它是每条路线的一部分。
使用街道网格的图形表示来评估集群可能会比连接白色地图上的点产生更真实的结果（尽管两者都是 TSP 变体）。如果图形模型不可用，您可以使用出租车度量 (|x_1 - x_2| + |y_1 - y_2|) 作为距离的近似值。
我认为你想要一种分层聚集技术而不是 k-means。如果您的算法正确，则可以在拥有正确数量的集群时停止它。正如其他人提到的，您可以使用以前的解决方案播种后续集群，这可能会给您带来显着的性能提升。
您可能需要仔细查看您使用的距离函数，尤其是当您的问题具有高维度时。欧几里得距离是最容易理解的，但可能不是最好的，请查看诸如 Mahalanobis 之类的替代方法。
我假设您的真正问题与送报纸无关...
您是否考虑过使用基于经济/市场的解决方案？将设置除以任意（但为避免随机效应而保持不变）分成偶数子集（由送货人员的数量决定）。
为每个点分配一个成本函数，根据它在图中增加多少，并给每个额外的点一个经济价值。
迭代允许每个人轮流拍卖他们最差的点，并给每个人一个最大的预算。
这可能非常符合人们在现实生活中的想法，因为人们会发现交换，或者会说“如果我不做这一两个，我的生活会容易得多。它也非常灵活（对于例如，将允许距离任何其他点数英里的点相当容易地获得溢价）。
我会以不同的方式处理它：将街道网络视为一个图形，每条街道的每一侧都有一条边，将图形划分为 n 个段，每个段不超过给定长度，这样每个报童可以骑一个从起点到终点的连续路径。这样，您就可以避免为人们提供需要他们重复骑行相同路段的路线（例如，当被要求覆盖街道两侧而不覆盖所有周围街道时）。
这是发现“集群”所在位置的一种非常快速而肮脏的方法。这是受到游戏“扫雷”的启发。
将您的整个交付空间划分为正方形网格。注意 - 需要对网格大小进行一些调整才能正常工作。我的直觉告诉我，一个与物理邻域块大小大致相同的正方形将是一个很好的起点。
循环遍历每个方块并存储每个街区内的送货地点（房屋）的数量。使用第二个循环（或第一次传递的一些巧妙方法）来存储每个相邻块的交付点数。
现在您可以使用与照片处理软件类似的方式在此网格上进行操作。您可以通过查找某些相邻块中没有交付点的块来检测集群的边缘。
最后，您需要一个系统，该系统结合了交付的数量以及行驶的总距离来创建和分配路线。可能有一些孤立的集群，只有少量的交付，以及一两个超级集群，其中许多家庭彼此非常接近，需要多个送货员在同一个集群中。必须访问每个家庭，这是您的第一个限制。
推导出任何一名送货员单次运行的最大允许距离。接下来对每人交付的数量执行相同的操作。
路由算法的第一次运行将分配一个送货员，将他们发送到任何未完成所有送货的随机集群，让他们送货，直到他们达到送货限制或他们已经送货到集群中的所有家庭。如果他们已达到交货限制，请将他们送回基地以结束路线。如果他们可以安全地前往最近的集群然后回家而不会达到他们的最大旅行距离，请这样做并重复上述操作。
为当前送货员完成路线后，检查是否有房屋尚未送货。如果是这样，请指定另一个送货员，并重复上述算法。
这将生成初始路线。我会存储所有信息——每个广场的位置和尺寸、一个广场内的房屋数量及其所有直接邻居、每个广场所属的集群、送货人及其路线——我会存储所有这些在数据库中。
我将把重新计算过程留给您 - 但是在数据库中拥有所有当前路线、集群等将使您能够保留所有历史路线，并尝试各种方案以了解如何最好地适应变化，从而产生最少的影响对现有路线的可能更改。
这是一个值得优化的解决方案而不是试图解决“最佳”问题的经典示例。它在某些方面类似于“旅行商问题”，但您还需要在优化期间对位置进行分段。
我使用了三种不同的优化算法来解决这样的问题：
使用优化算法，我认为您已经描述了以下“目标”：
希望这能让你开始！
* 编辑 *
如果您不关心路线本身，则可以消除上述目标 3 和 4，并可能使问题更适合您的奖金要求。
如果您考虑人口统计信息（例如人口密度、订阅采用率和订阅取消率），您可能可以使用上述优化技术来完全消除在订阅者采用或放弃您的服务时重新运行算法的需要。一旦集群被优化，它们将保持平衡，因为每个集群的速率与其他集群的速率相匹配。
唯一需要重新运行该算法的时间是外部因素（例如经济衰退/萧条）导致人口群体的行为发生变化。
我认为您确实想要 Set Covering location 模型的一些变体，而不是聚类模型，并带有一个额外的约束来覆盖每个设施所覆盖的地址数量。我在网上真的找不到很好的解释。您可以查看此页面，但他们正在使用面积单位解决它，您可能希望在欧几里得或网络空间中解决它。如果您愿意挖掘死树格式的内容，请查看 Daskin 的 Network and Discrete Location 的第 4 章。
对简单聚类算法的良好调查。还有更多：http: //home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html
我知道一种非常新颖的方法来解决这个问题，我已经看到它应用于生物信息学，尽管它适用于任何类型的聚类问题。这当然不是最简单的解决方案，但我认为它非常有趣。基本前提是聚类涉及多个目标。对于一个您想要最小化集群数量的人来说，简单的解决方案是一个包含所有数据的集群。第二个标准目标是最小化集群内的方差量，简单的解决方案是许多集群，每个集群只有一个数据点。当您尝试同时包含这两个目标并优化权衡时，就会出现有趣的解决方案。
所提出方法的核心是一种称为模因算法的东西，它有点像史蒂夫提到的遗传算法，但它不仅很好地探索了解决方案空间，而且还能够专注于有趣的区域，即解决方案。至少我建议阅读一些关于这个主题的论文，因为模因算法是一种不寻常的方法，尽管有一点警告；它可能会引导您阅读 The Selfish Gene 我还没有决定这是否是一件好事......如果您对算法不感兴趣，那么也许您可以尝试按照格式要求表达您的问题并使用源代码提供的代码。相关论文和代码可以在这里找到：多目标聚类
这与问题没有直接关系，但我听说过，如果这确实是您遇到的路线规划问题，应该考虑一下。这将影响分配给每个驱动程序的集合内地址的顺序。
UPS 的软件可以为他们的送货人员生成最佳路线。该软件试图最大限度地增加路线中右转的次数。这为他们节省了大量的交货时间。
对于不住在美国的人来说，这样做的原因可能不是很明显。在美国，人们在马路右侧开车，所以在右转时，如果绿灯，您不必等待迎面而来的车辆。此外，在美国，当红灯右转时，您（通常）不必等到绿灯才可以走。如果你总是右转，那么你永远不必等待灯。
这里有一篇关于它的文章： http ://abcnews.go.com/wnt/story?id=3005890
您可以通过使用先前的聚类作为聚类特征，使 K 均值或预期最大化保持尽可能不变。让每个集群拥有相同数量的项目似乎有点棘手。我可以考虑如何通过执行 k 方法将其作为后聚类步骤，然后将一些点改组直到事情平衡，但这似乎不是很有效。
一个没有任何奖励积分的简单答案：
每个地址一个送货员。
我承认这不一定会提供大小大致相等的集群：
数据聚类中目前最好的技术之一是证据积累。(Fred and Jain, 2005) 你要做的是：
给定具有 n 个模式的数据集。
在 k 的范围内使用类似 k-means 的算法。或者使用一组不同的算法，目标是产生一个分区集合。
创建一个大小为 nx n 的联合关联矩阵 C。
对于集成中的每个分区 p：
3.1 更新协关联矩阵：对于 p 中属于同一簇的每个模式对 (i, j)，设置 C(i, j) = C(i, j) + 1 /N。
使用聚类算法（例如 Single Link）并应用矩阵 C 作为邻近度度量。Single Link 给出了一个树状图作为我们选择具有最长生存期的聚类的结果。
如果您有兴趣，我将提供 SL 和 k-means 的描述。
- 您有一组街道地址，每个地址都经过地理编码。
- 您希望对地址进行集群，以便将每个集群分配给一名送货员。
- 送货人员或集群的数量不是固定的。如果需要，我总是可以雇佣更多的送货员，或者解雇他们。
- 每个集群应该有大约相同数量的地址。但是，如果集群的地址更加分散，则集群的地址可能会更少。（换种说法：最小数量的集群，其中每个集群包含最大数量的地址，并且集群内的任何地址必须相隔最大距离。）
- 对于奖励积分，当数据集被更改（添加或删除地址）并且算法重新运行时，如果集群尽可能保持不变（即，这排除了简单的 k-means 聚类，即随机性）。不然快递员会发疯的。
如前所述，车辆路线问题可能更适合......虽然严格设计时并未考虑到集群，但它会根据最近的地址进行优化分配。因此，您的集群实际上将是推荐的路线。
如果您提供最大数量的交付者并尝试达到最佳解决方案，这应该会告诉您所需的最小值。这涉及第 2 点。
可以通过对要访问的地址数量进行限制来获得相同数量的地址，基本上是分配一个库存值（现在它是一个受限制的车辆路线问题）。
如果地址更加分散（现在是时间窗口的人满为患的车辆路线问题），则添加送货人员工作的时间窗口或小时有助于减少负载。
如果您使用最近邻算法，那么您每次都可以获得相同的结果，删除单个地址不应该对您的最终结果产生太大影响，因此应该处理最后一点。
我实际上正在开发一个 C# 类库来实现这样的目标，并认为它可能是最好的方法，尽管它并不容易实现。
我将使用基本算法根据他们的居住地和订阅者的当前位置创建第一组报童路线，然后：
当报童是：
当位置是：
每季度一次，您可以重新计算整个事情并更改所有路线。
