Узнать об объединении интервалов

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, правой конечной точки этого интервала. То же самое с 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-го интервала.