python - 学习区间的并集

Question

假设我有 N 个一维点 xi 及其标签 yi = 1/0。我想学习一组 k 间隔，这样当标签 1 被赋予这些间隔中的所有点时，误差就会最小化。即如果数据集是:

1: 0
2: 0
3: 1
4: 1
5: 0
6: 1
7: 1
8: 1
9: 0
10: 0
11: 0

如果k=1，则最佳间隔为[3, 8]。随着 k 的增加，它会变得更加复杂。

在 scikit-learn 中是否有一些通用的算法可以做到这一点，或者对决策树算法进行了一些修改？仅直接决策树算法是行不通的，因为您无法控制 k，只能控制深度，并且分支的顺序可能会导致最终的间隔集次优。如果需要的话，scikit-learn 中没有的东西也可能没问题。

Answer 1

我相信您可以将其重新表述为整数规划问题。

让:

x_ij = 1 if interval i's left endpoint is at j
       0 otherwise

和:

y_ij = 1 if interval i's right endpoint is at j
       0 otherwise

最后:

a_k = Total # of 1's in the interval [0, k]
b_k = Total # of 0's in the interval [0, k]

那么以下内容相当于您的问题:

maximize sum_ijk (   a_j * y_ij - a_k - x_ik     # Ones inside 
                   - b_j * y_ij - b_k - x_ik     # Zeros inside
                   + b_j * x_ij - b_k - y_(i-1)k # Zeros outside
                   - a_j * x_ij - a_k - y_(i-1)k # Ones outside
         )
with respect to the constraints
    sum_j x_ij = 1 for each i
    sum_j y_ij = 1 for each i
    0 <= x_ij <= 1 for each i, j
    0 <= y_ij <= 1 for each i, j
    sum_j * y_ij - j * x_ij > 0 for each i
    sum_j * x_(i+1)j - j * y_ij > 0 for each i

由于每个 x_ij 和 y_ij 都是整数，这是一个整数规划问题。解除这个约束，你就会遇到一个线性规划问题，尽管这种情况下的结果很难解释。

对于:

maximize sum_ijk ( a_j * y_ij - a_k - x_ik )

i 的总和是所有间隔。每一项 a_j * y_ij 仅对于 j 的一个值(该区间的右端点)为“on”。与a_j * x_ij相同。那么差值就是一些a_k - a_r，即区间内1的总数。同样，其他三个术语统计正确和错误分类的出现次数。

对于约束:

sum_j x_ij = 1 for each i
sum_j y_ij = 1 for each i

假设间隔必须各有一个左端点和一个右端点，并且

sum j * y_ij - j * x_ij > 0 for each i
sum j * x_(i+1)j - j * y_ij > 0 for each i

表示左端点必须位于右端点的左侧，并且第 i+1 个区间的右端点必须位于右端点的左侧第 i 个间隔。