通过线性编程识别列和行簇 [英] Identifying column and row clusters with linear programming

问题描述

我相信问题在那里进行线性挖掘的好方法吗?但是我对此并不陌生，不知道将其最小化的最佳方法.

I believe that the question Is there a good way to do this type of mining? could be solved using linear programming techniques. But I am completely new to this and do not know the best way to frame this as a minimization.

以下方法可以吗?

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

还有更好的方法吗?是否有可能以某种方式将其构造为一个纯粹的约束问题(即没有最小化的问题)?我的术语正确吗?谢谢！

And is there a better way of doing this? Is it possible to somehow frame this as a pure constraint problem (ie without the minimisation)? Do I have my terminology correct? Thanks!

推荐答案

是的，您当然可以为此使用线性编程，但是这很困难，我认为您必须更精确地定义问题.我有太多问题要评论，希望您不要介意我将其写为答案...

Yes, you could definitely use linear programming for this, but it is hard and I think you have to define your problem more precisely. I have too many questions for a comment, I hope you don't mind I write this as an answer...

您的点可以在列组"中，也可以在行组"中.从上面的命题中，我了解到您知道提前的列组和行组的数量?

Your points can be either in the "column group" or in the "row group". From your proposition above, I understand that you know the number of column groups and row groups in advance?

因此，您知道组的组成，您只想对这些组中的点进行重新分配，以最大程度地减少成本总和，具体取决于:

So you know your groups composition, you just want to find a repartition of the points in those groups in order to minimise the sum of the costs, determined by:

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

• The vertical width of the horizontal clusters (c(H) = max (i,j in H) |yi - yj|)
• The horizontal width of the vertical clusters (c(V) = max (i,j in V) |xi - xj|)

在H水平集群中，V在垂直集群中，总成本为:

With H an horizontal cluster, V a vertical cluster, and the total cost will be:

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

预先已知

和n(水平簇的数量)和p(垂直簇的数量).这是正确的吗?

with n (number of horizontal clusters) and p (number of vertical clusters) known in advance. Is this correct?

对于水平组，您说不能有空洞".如果您可以量化孔的大小，我将其表示为您的问题的约束.例如:

For the horizontal groups, you say you can't have "holes". I would represent this as a constraint of your problem, if you can quantify the size of the holes. For instance:

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

将确保您在水平簇C中的差距不大于r.这是否是您想要的? r是固定数字吗?

will insure that you don't have a gap of more than r in the horizontal cluster C. Is this what you want? Is r a fixed number?

这是一个完整的问题，还是您有其他约束条件(每组的最小点数，或其他什么)?

Is this the complete problem, or do you have other constraints (minimal number of points per group, or something)?

您需要一个精确的最小解决方案，还是一个好的"解决方案就足够了?

Do you need an exact minimal solution, or a "good" solution would be enough?

最后，在技术方面，由于您之前的帖子被标记为"python"，而没有，因此您是否必须使用python来求解模型?

Finally, for the technical part, since your previous post was tagged 'python' and this one is not, do you have to use python to solve the model?

这篇关于通过线性编程识别列和行簇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！