Описан алгоритм построения кусочно-постоянной зависимости переменной от взвешенной суммы , минимизирующей сумму квадратов отклонений от средних значений на диапазонах изменения величины .

Мотивация

Задача восстановления зависимости некоторой величины от ряда признаков распространена в анализе данных. Кусочно-постоянная регрессия будет полезна, если требуется выделить характерные диапазоны изменения интегрального признака (взвешенной суммы признаков), чтобы рассмотреть отдельно точки, принадлежащие этим диапазонам. Таким образом, получив информацию о распределении точек внутри каждого из них и исследовав зависимость от прочих факторов, можно сделать выводы о сегментированных данных.

Формальная постановка

Входные данные - множество точек и количество диапазонов .

Определим целевую функцию

зависящую от диапазонов изменения величины , где в -й диапазон попадают точки с индексами из множества , и - это среднее арифметическое значений , где .

1. Требуется оптимальным образом разбить точки на диапазоны и найти такое разбиение, при котором минимально.

2. Требуется найти такие весовые коэффициенты , при которых указанный минимум, найденный при заданных , будет наименьшим.

Алгоритм

Первая задача решается методом динамического программирования. Упорядочим точки по возрастанию координаты . Выделим подзадачи с параметрами - разбить точки с индексами от до на диапазонов. Зная решение подзадачи , пытаемся улучшить решение подзадач для , заполняя матрицы - минимум целевой функции, - размер последнего диапазона в оптимальном разбиении. Окончательно будет равно минимуму целевой функции, а само разбиение можно будет восстановить по значениям .

Вторая задача является дискретной, и поскольку значение целевой функции зависит только от порядка следования точек , то в зависимости от аргументов целевая функция носит кусочно-постоянный характер, поэтому стандартные нелинейные оптимизаторы здесь неприменимы.

Для подбора коэффициентов предлагается следующий итерационный метод. В качестве начального приближения выбираются коэффициенты , вычисленные из множественной линейной регрессии. Затем на каждой итерации алгоритма будем вычислять оптимальное разбиение при найденных весовых коэффициентах, после чего зафиксируем размеры диапазонов разбиения и оптимизируем весовые коэффициенты при заданных размерах диапазонов.

Таким образом, приходим к следующей подзадаче:

3. Требуется найти коэффициенты , при которых целевая функция будет минимальна среди всех разбиений на диапазоны, имеющих заданный размер.

Эту задачу предлагается решать наискорейшим покоординатным спуском по каждой переменной . Итак, определим функции . Требуется найти такое , при котором значение целевой функции (при заданных размерах диапазонов), вычисленный для точек , окажется наименьшим.

Последняя задача относится к вычислительной геометрии и может быть решена по-разному. Наивный метод состоит в переборе всех точек пересечения графиков функций и и вычислении для каждой точки значения целевой функции с последующим выбором наилучшего . Сложность алгоритма составит .

Другой способ похож на алгоритм заворачивания подарка для выпуклой оболочки. Этот метод строит графики порядковых статистик множеств по нарастанию . Нас интересует всё множество событий, когда при постепенном увеличении содержимое диапазонов изменится вследствие перестановки точки на границе диапазонов с точкой из соседнего диапазона. Поскольку таких событий не более , то сложность алгоритма составит .

И наконец, можно, как в алгоритме Грэхема, упорядочить все точки по возрастанию координаты и добавлять точки по одной, обновляя каждый раз решение подзадачи построения графиков порядковых статистик в зависимости от для уже рассмотренных точек. Поскольку порядковых статистик можно построить за время , то нахождение минимума целевой функции займет такое же время.

Таким образом, чтобы оптимизировать значение целевой функции при заданных размерах диапазонов по коэффициентам , будем оптимизировать по очереди коэффициент в каждом слагаемом в наборе точек , беря остальные слагаемые в этой сумме в качестве свободного члена .