linear-programming - 使用线性规划识别列和行簇

Question

我相信这个问题是否有一种很好的方法来进行这种类型的挖掘？可以使用线性规划技术来解决。但我对此完全陌生，不知道将其视为最小化的最佳方法。

以下方法可以吗？

• 每一行和每一列都有一个连续变量，它是该行/列中所有成员跨越的“长度”
• 每个“点”（每个黑点）都有一个变量，表示它是行组还是列组的成员
• 最小化第一个变量的总和

有没有更好的方法来做到这一点？是否有可能以某种方式将此视为纯约束问题（即没有最小化）？我的术语正确吗？谢谢！

Answer 1

是的，您绝对可以为此使用线性规划，但这很难，我认为您必须更准确地定义您的问题。我有太多问题要评论，我希望你不介意我写这个作为答案......

您的点可以在“列组”或“行组”中。从你上面的命题，我了解到你提前知道了列组和行组的数量？

因此，您知道您的组组成，您只想找到这些组中点的重新分配，以最小化成本总和，由以下因素确定：

• 水平簇的垂直宽度 ( c(H) = max (i,j in H) |yi - yj|)
• 垂直簇的水平宽度 ( c(V) = max (i,j in V) |xi - xj|)

使用H水平集群，V垂直集群，总成本将是：

c(H1) + c(H2) + ... + c(Hn) + c(V1) + c(V2) + ... + c(Vp)

n预先知道（水平簇的数量）和（p垂直簇的数量）。它是否正确？

对于水平组，你说你不能有“洞”。如果您可以量化孔的大小，我会将其表示为您的问题的约束。例如：

for each i in C, ( min (j in C) |xi - xj|  ) < r

将确保您在水平集群 C 中没有超过 r 的间隙。这是您想要的吗？是r固定数字吗？

这是完整的问题，还是您有其他限制（每组的最少点数，或其他）？

你需要一个精确的最小解决方案，还是一个“好的”解决方案就足够了？

最后，关于技术部分，由于您之前的帖子被标记为“python”而这一篇没有，所以您必须使用python来解决模型吗？

Answer 2

我终于弄清楚了如何以线性形式表示这个问题。我在Is there a good way to do this type mining? 的回答中有完整的描述？但这里有一个简短的总结：

• 对一行中的每个相邻对使用二进制 (0/1) 变量F_i。当这对在同一组中时，这将为 1，否则为 0。

• 使用常数S_i来描述每对点之间的空间数。

• 最小化两项之和：

  • 的总和1 - F-i。将这一点最小化会将成对组合成更大的组。

  • 的总和F_i * S_i。最小化这将巴黎与大间距分开。

通过改变这两个术语的相对权重，您可以改变水平组之间间距的重要性。

这依赖于问题中的不对称性，其中水平组对间距敏感，而垂直组则不敏感。