lapkin25 1 сен 2023 в 01:09

Множественная кусочно-постоянная регрессия

Средний

3 мин

2.9K

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

Мотивация

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

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

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

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

$J=\sum_{k=1}^m\sum_{i\in I_k}(y_i - c_k)^2,$

зависящую от диапазонов изменения величины , где в -й диапазон попадают точки с индексами из множества , и - это среднее арифметическое значений , где $i \in I_k$ . Здесь множество содержит индексы точек, попавших в диапазон значений величины : $I_k = \{i\colon x_i \in (t_{k-1}, t_k]\}$ , где - это границы диапазонов на оси . Таким образом, функция зависит от порядка следования индексов координат в упорядоченной последовательности чисел .

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

Алгоритм

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

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

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

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

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

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

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

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

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

Таким образом, чтобы оптимизировать значение целевой функции при заданных размерах диапазонов по коэффициентам , будем оптимизировать по очереди коэффициент в каждом слагаемом в наборе точек $x_i=w_1x_{i1}+\ldots+w_px_{ip}$ , беря остальные слагаемые в этой сумме в качестве свободного члена .

Теги:

Хабы:

Множественная кусочно-постоянная регрессия

Мотивация

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

Алгоритм

Публикации

Ближайшие события