划分区域以使距离之和最小化的算法

Question

假设我们在平面的有界区域中有n个点。问题是将其划分为4个区域（具有水平线和垂直线），使得每个区域中的度量的总和被最小化。

度量例如可以是每个区域中点之间的距离的总和;或关于点的扩展性的任何其他措施。见下图。

我不知道是否有聚类算法可以帮助我解决这个问题，或者例如它可以被配制成一个简单的优化问题。其中决策变量是“轴”。

Answer 1

注 - 可能不正确。我会尝试添加另一个答案

最小化差分平方和的一维版本是凸的。如果从最左侧的线开始并将其移到右侧，那么线所穿过的每个点将停止累积与其右侧的点之间的差异，并开始累积差异到其左侧的点。当你遵循这一点时，左边的差异会增加，右边的差异会减小，所以你会得到单调的减少，可能是单一点，可能在线的两边，然后单调增加。

我认为一条线上聚类点的一维问题是凸的，但我不再相信在最佳位置绘制单条垂直线的问题是凸的。我担心y坐标变化的点集合使得左手点大部分高，右手点大部分低点，中点在高点和低点之间交替。如果这不是凸的，则试图扩展到两个维度的答案的部分失败。

因此，对于问题的一维版本，您可以选择任意一点，并及时制定出O（n）该点是否应该位于最佳分界线的左侧或右侧。因此，通过二元印章，您可以找到最佳时间线O（n log n）。

我不知道二维版本是凸的还是不是，但是您可以尝试所有可能的水平线位置，并且对于每个位置，使用类似方法求解垂直线的位置一维问题（现在你有两个凸函数的总和值得担心，但这仍然是凸的，所以没关系）。因此，您最多可以解决O（n）一维问题，给出成本O（n^2 log n）。

如果这些点的分布并不是很奇怪，我希望通过使用前一次迭代中的一维问题的解作为下一次解决方案位置的第一次估计，可以节省大量时间迭代。给定一个起点x，你会发现这是否在解决方案的左侧或右侧。如果它位于解决方案的左侧，则执行1,2,4,8 ...步骤以找到解决方案右侧的一个点，然后运行二元印章。希望这个两阶段切换比从头开始整个阵列的二进制切换更快。

Answer 2

我相信这可以被公式化为MIP（混合整数规划）问题。

让我们引入4个象限A，B，C，D。 A是正确的，上面的，B是正确的，下面的，等等。然后定义一个二元变量

delta(i,k) = 1 if point i is in quadrant k 
       0 otherwise 

和连续变量

Lx, Ly : coordinates of the lines 

显然，我们有：

sum(k, delta(i,k)) = 1 
xlo <= Lx <= xup 
ylo <= Ly <= yup 

其中xlo,xup是最小和最大的x坐标。接下来，我们需要实现像含义：

delta(i,'A') = 1 ==> x(i)>=Lx and y(i)>=Ly 
delta(i,'B') = 1 ==> x(i)>=Lx and y(i)<=Ly 
delta(i,'C') = 1 ==> x(i)<=Lx and y(i)<=Ly 
delta(i,'D') = 1 ==> x(i)<=Lx and y(i)>=Ly 

这些可以通过所谓的指示器约束来处理或写为线性不等式，例如

x(i) <= Lx + (delta(i,'A')+delta(i,'B'))*(xup-xlo) 

与其他类似。最终目标是

min sum((i,j,k), delta(i,k)*delta(j,k)*d(i,j)) 

其中d(i,j)是点i和点j之间的距离。这个目标也可以线性化。

应用了一些技巧后，我可以使用Cplex在大约40秒内证明100个随机点的全局最优性。这种方法并不适用于大型数据集（当点数变大时，计算时间会迅速增加）。

我怀疑这不能成为凸出问题的鞋子。另外我不确定这个目标是否真的是你想要的。它会尝试使所有群集的大小相同（向大群集添加一个点会引入很多要添加到目标的距离;向小群集添加点很便宜）。可能是每个群集的平均距离是一个更好的衡量标准（但这会使线性化变得更加困难）。

Answer 3

这是另一个尝试。布局一个网格，除了关系的情况外，每个点是其列中唯一的一点，也是其行中唯一的点。假设任何方向都没有关系，这个网格有N行，N列和N^2个单元格。如果有关系，网格更小，这使生活更轻松。

用水平线和垂直线分隔单元格几乎挑选出一个网格单元格，并说单元格就在单元格的正上方和正好在这些线条交叉的右侧，因此大致有O（N^2）可能的这种划分，我们可以计算每个这种划分的度量。我声称，当度量是群集中点间距离的平方和时，这个成本几乎是O（N^2）问题中的一个常数因子，因此检查每种可能性的全部成本是O（ N^2）。

由分割线形成的矩形内的度量是SUM_i，j [（X_i-X_j）^ 2 +（Y_i-Y_j）^ 2]。我们可以分别计算X贡献和Y贡献。如果你做了一些代数（如果你首先减去一个常数，使得所有事物总和为零），你会发现来自坐标的度量贡献在该坐标的方差中是线性的。所以我们要计算每个分区形成的矩形内X和Y坐标的方差。 https://en.wikipedia.org/wiki/Algebraic_formula_for_the_variance给了我们一个身份，告诉我们可以计算出每个矩形给出的SUM_i Xi和SUM_i Xi^2的方差（以及y坐标的相应信息）。由于浮点四舍五入错误，此计算可能不准确，但我将在此忽略。

给定一个与网格中每个单元格相关的值，我们希望能够很容易计算矩形内这些值的总和。我们可以沿着每一行创建部分和，将0 1 2 3 4 5转换为0 1 3 6 10 15，这样一行中的每个单元格都包含所有单元格的左边和它自身的总和。如果我们取这些值并对每列进行部分总和计算，那么对于每个单元格，我们已经计算出其右上角位于该单元格内并延伸至网格底部和左侧的矩形的总和。这些在最右边一列的计算值为我们提供了与该单元格相同并在其下面的所有单元格的总和。如果我们减去矩形，我们知道如何计算，我们可以找到位于网格右侧和网格底部的矩形的值。类似的减法允许我们首先计算出我们选择的任何垂直线左右两边的矩形的值，然后完成由网格中的任意单元格交叉的两条线组成的一组四个矩形。其中昂贵的部分是计算部分款项，但我们只需要这样做一次，而且只需花费O（N^2）。用于计算出任何特定度量的减法和查找只具有恒定的成本。我们必须为每个O（N^2）单元执行一次，但仍然只有O（N^2）。 （因此我们可以通过计算与O（N^2）时间内所有可能聚类相关的度量并选择最佳值）在O（N^2）时间中找到最佳聚类。