这是我其他帖子的后续问题。
具有大小约束的聚类算法 https://stackoverflow.com/questions/30112428/algorithm-for-clustering-with-size-constraints
我正在研究聚类算法，
经过一些重新聚类后，现在我有了这组点，它们都不在最佳聚类中，但无法单独重新分配，因为它会违反约束。
我试图使用图形结构来解决问题，但在实现过程中遇到了一些问题。
我是初学者，如有错误请指出。
根据 @Kittsil 的回答
构建一个以簇为节点的有向图，这样，如果全局解决方案通过 A 中的某个点移动到 B 来最小化，则存在边 (A,B)。在该图中查找循环将允许您找到潜在的移动（其中移动包括移动循环中的每个顶点）。
我修改了图表，将权重添加为从 A 移动到 B 的点数之和。
以下是一些我不确定如何决定重新分配哪个点的情况。
场景1。对于一个循环如下。有两个点可以从A移动到B，三个点可以从B移动到C。在这种情况下，我应该选择哪一个点来重新分配呢？
场景2。对于一个循环如下。令所有边权重为 1。对于簇 A 中的点，可以将其重新分配给簇 B 或 D。在这种情况下。我该如何进行重新分配？
场景3与场景2类似，设所有边权重为1。大循环中有两个小循环。簇 A 中的点可以重新分配给 B 和 E，在这种情况下我如何决定重新分配？
欢迎提出有关任一场景的想法！
考虑到上述情况，还有关于实现算法的建议吗？如果使用伪代码就更好了。谢谢！
如果边权重与重新聚类点所获得的收益成正比，那么一个不错的启发式方法是选择总权重最高的循环。我认为这解决了您的所有三种情况：每当您有选择时，请选择最有好处的一个。
讨论：
中描述的算法具有大小约束的聚类算法 https://stackoverflow.com/questions/30112428/algorithm-for-clustering-with-size-constraints是一种寻找局部最小值的贪心算法。因此，无论您在这些场景中如何选择，都不能保证您会找到最佳解决方案，并且任何选择都会使您更接近局部最小值。
由于与类似的带约束排序问题的关系，我的直觉是最小问题将是 NP 困难的。如果情况并非如此，那么就存在一种比我之前描述的算法更好的算法。然而，这种贪心算法似乎是解决最小问题的快速解决方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
