algorithm - 如何将二维点划分为间隔(仅使用垂直线)？

Question

所以我有一个充满点 (x,y) 的二维散点图。我想画k条竖线(x_1 = a, x_2 = b, ..., x_k = k)，把点分成k组。

最优解会最小化每组 y_value 的平均方差。

什么是合适的算法？这听起来像 k 均值，但我有限制，即线条必须是垂直的。

Answer 1

这里有一个基于动态规划的思路。
使用以下符号: (x_1, y_1), ..., (x_n, y_n)点，与x_1 <= x_2 <= ... <= x_n切入K团体。
Var(i, j) y 的方差的:y_i, ..., y_j .
F_K((x_1,y_1), ..., (x_n, y_n)) = F_k(1,n)问题最佳解决方案的值(value)。

然后我们有以下内容:
F_k(i,j) = min for l in i...j-k+1 of (Var(i,l) + F_(k-1)(l+1, j)和
F_1(i,j) = Var(i,j) .

上面的属性只是意味着将点分成“k”组的最佳方法是选择最左边的切割(选择 l )，并且最佳选择 k-1削减剩余的点。

从那里您可以选择一个动态程序。你需要一个 3D 数组 A尺寸n*n*K为所有 i,j,k 存储 F_k(i,j) 的值.该程序看起来像:

function get_value(P: points, A: 3D array, i, j, k){
  if A[i][j][k] is defined{
    result = A[i][j][k]
  } else if k == 1 {
    A[i][j][k] = get_var(P, i, j)
    result = A[i][j][k] 
  } else {
    result = +INF
    for l in i ... j-k+1 {
      tmp = get_value(P, A, i, l, 1) + get_value(P, A, l+1, j, k-1)
      if tmp < result {
        result = tmp
      }
    }
  }
  return result
}

注意:我对 l 的迭代范围有点快，这可能是值得研究的问题。