Сглаживающий сплайн

Сглаживающий сплайн (англ. smoothing spline) — оценка функции $\stackrel{^<!--\; ^\; -->}{f}(x)$${\hat {f}}(x)$, полученная из набора зашумлённых наблюдений $y_i$$y_{i}$ за исходными данными $f(x_i)$$f(x_{i})$ и используемая в дальнейших вычислениях для балансировки адекватности модели функции $\stackrel{^<!--\; ^\; -->}{f}(x_i)$${\hat {f}}(x_{i})$ к $y_i$$y_{i}$ с основанной на производной мере кривизной функции $\stackrel{^<!--\; ^\; -->}{f}(x)$${\hat {f}}(x)$. Иными словами, сглаживающий сплайн является важным средством при работе с зашумленными данными типа $x_i$$x_{i}$, $y_i$$y_{i}$. Наиболее известным видом сглаживающего сплайна является кубический сплайн.

Определение кубического сплайнаПравить

Пусть $(x_{i},Y_{i});x_{1}<x_{2}<\dots <x_{n},i\in \mathbb {Z}$  — последовательность наблюдений, порождённых выражением $Y_i=\mathrm{\mu <!--\; \mu \; -->}(x_i)$$Y_{i}=\mu (x_{i})$ . Приближение сглаживающими сплайнами $\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}$${\hat {\mu }}$  функции $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  определяется как функция (в классе дважды дифференцируемых функций), минимизирующая

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(Y_i-<!--\; -\; -->\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_i){)}^2+\mathrm{\lambda <!--\; \lambda \; -->}{\int <!--\; \int \; -->}_{x_1}^{x_n}{\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}}^{″}(x{)}^{2}dx.$$\sum _{i=1}^{n}(Y_{i}-{\hat {\mu }}(x_{i}))^{2}+\lambda \int _{x_{1}}^{x_{n}}{\hat {\mu }}''(x)^{2}\,dx.$ 

Замечания:

1. $\mathrm{\lambda <!--\; \lambda \; -->}\ge <!--\; \ge \; -->0$$\lambda \geq 0$  параметр сглаживания, контролирующий соотношение между точностью воспроизведения данных и «неровностью» аппроксимирующей функции.
2. интеграл вычисляется по всему диапазону $x_i$$x_{i}$ .
3. при $\mathrm{\lambda <!--\; \lambda \; -->}\to <!--\; \to \; -->0$$\lambda \to 0$  (нет сглаживания), сглаживающий сплайн превращается в интерполяционный сплайн.
4. при $\mathrm{\lambda <!--\; \lambda \; -->}\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$\lambda \to \infty$  (бесконечное сглаживание), штраф за неровность становится преобладающим и аппроксимация превращается в линейную МНК аппроксимацию.
5. наиболее часто в современной статистической литературе используется штраф за неровность на основе второй производной, однако метод может быть легко адаптирован к использованию штрафов на основе других производных.
6. в ранней литературе, с равноудалёнными $x_i$$x_{i}$ , для вычисления штрафа вместо производной использовались конечные разности второго и третьего порядка.
7. если сумму квадратов отклонений сплайна от исходных данных (первый член функционала) заменить на логарифм функции правдоподобия, получим оценку максимального правдоподобия со штрафной функцией. В такой постановке обычный сглаживающий сплайн представляет собой специальный случай, когда правдоподобие рассчитывается исходя из нормального распределения погрешности.

Вывод кубического сглаживающего сплайнаПравить

Разделим нахождение выражений, описывающих сглаживающий сплайн, на два этапа:

1. Сначала найдём значения $\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_i);i=1,\dots <!--\; \dots \; -->,n$${\hat {\mu }}(x_{i});i=1,\ldots ,n$ .
2. Из этих значений найдём $\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x)$${\hat {\mu }}(x)$  для всех x.

Начнём со второго этапа:

Дан вектор $\stackrel{^<!--\; ^\; -->}{m}=(\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_1),\dots <!--\; \dots \; -->,\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_n){)}^T$${\hat {m}}=({\hat {\mu }}(x_{1}),\ldots ,{\hat {\mu }}(x_{n}))^{T}$  «подогнанных» значений; сумма квадратов в критерии сплайна — константа. Требуется только минимизировать $\int <!--\; \int \; -->{\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}}^{″}(x{)}^{2}dx$$\int {\hat {\mu }}''(x)^{2}\,dx$ , и минимизация — натуральный кубический сплайн, интерполирующий точки $(x_i,\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_i))$$(x_{i},{\hat {\mu }}(x_{i}))$ . Данный интерполяционный сплайн — линейный оператор — может быть представлен в виде:

$\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}(x_i)f_i(x)$${\hat {\mu }}(x)=\sum _{i=1}^{n}{\hat {\mu }}(x_{i})f_{i}(x)$ ,

где $f_i(x)$$f_{i}(x)$  — набор базисных сплайн-функций. В результате штраф за отсутствие у функции признака гладкости имеет форму

$\int <!--\; \int \; -->{\stackrel{^<!--\; ^\; -->}{\mathrm{\mu <!--\; \mu \; -->}}}^{″}(x{)}^{2}dx={\stackrel{^<!--\; ^\; -->}{m}}^{T}A\stackrel{^<!--\; ^\; -->}{m}.$$\int {\hat {\mu }}''(x)^{2}dx={\hat {m}}^{T}A{\hat {m}}.$ 

где элементы A — $\int <!--\; \int \; -->f_i^{″}(x)f_j^{″}(x)dx$$\int f_{i}''(x)f_{j}''(x)dx$ . Базисные функции и матрица A зависят от конфигурации независимых переменных $x_i$$x_{i}$ , но не от $Y_i$$Y_{i}$  или $\stackrel{^<!--\; ^\; -->}{m}$${\hat {m}}$ .

Возвращаясь к первому этапу, взвешенная сумма квадратов может быть записана так:

$\Vert <!--\; \Vert \; -->Y-<!--\; -\; -->\stackrel{^<!--\; ^\; -->}{m}{\Vert <!--\; \Vert \; -->}^2+\mathrm{\lambda <!--\; \lambda \; -->}{\stackrel{^<!--\; ^\; -->}{m}}^{T}A\stackrel{^<!--\; ^\; -->}{m},$$\|Y-{\hat {m}}\|^{2}+\lambda {\hat {m}}^{T}A{\hat {m}},$ 

где $Y=(Y_1,\dots <!--\; \dots \; -->,Y_n{)}^T$$Y=(Y_{1},\ldots ,Y_{n})^{T}$ . минимизация по $\stackrel{^<!--\; ^\; -->}{m}$${\hat {m}}$  даёт

$\stackrel{^<!--\; ^\; -->}{m}=(I+\mathrm{\lambda <!--\; \lambda \; -->}A{)}^{-<!--\; -\; -->1}Y.$${\hat {m}}=(I+\lambda A)^{-1}Y.$ 

Создание многомерных сплайновПравить

Из приведённого ограничения на формулу из определения $x_{1}<x_{2}<\dots <x_{n}$  следует, что алгоритм не работает для произвольного набора данных. Если планируется использование алгоритма для произвольного набора точек в многомерном пространстве необходим алгоритм, в котором нет таких ограничений. Возможное решение заключается во введении параметра таким образом, что входные данные могут быть представлены как одномерные функции, зависящие от данного параметра; после можно применить сглаживание для каждой функции. В двумерном пространстве решение состоит в параметризации $x$$x$  и $y$$y$  как $x(t)$$x(t)$  and $y(t)$$y(t)$  где $t_{1}<t_{2}<\dots <t_{n}$ . Подходящее решение для $t$$t$  это накопленное расстояние $t_{i+1}=t_i+\sqrt{(x_{i+1}-<!--\; -\; -->x_i{)}^2+(y_{i+1}-<!--\; -\; -->y_i{)}^2}$$t_{i+1}=t_{i}+{\sqrt {(x_{i+1}-x_{i})^{2}+(y_{i+1}-y_{i})^{2}}}$  где $t_1=0$$t_{1}=0$ .

Более детальный анализ параметризации выполнен E.T.Y Lee.

Связанные методыПравить

Сглаживающие сплайны имеют отношение, но отличаются от:

• Регрессионных сплайнов (англ. Regression Splines). Метод, при использовании которого данные аппроксимируются с помощью набора базисных сплайн-функций с уменьшенным количеством узлов, в большинстве случаев при помощи метода наименьших квадратов. При этом в случае отсутствия у функции признака гладкости штрафы не используются.
• Штрафных сплайнов, сплайнов со штрафами (англ. Penalized Splines). Сочетают уменьшенное количество узлов регрессионных сплайнов со штрафом за отсутствие у функций сглаживающих сплайнов признака гладкости.
• Метод упругой карты. Метод, сочетающий штрафы по методу наименьших квадратов для ошибки аппроксимации со штрафами за кривизну и растяжение аппроксимирующего множества и использующий крупный шаг дискретизации для оптимизации проблемы.

Исходный кодПравить

Исходный код для сглаживающих сплайнов может быть взят из примеров к книге Carl de Boor’s A Practical Guide to Splines. Примеры написаны на Фортране. Обновлённые исходные коды также доступны на официальном сайте Carl de Boor’s [1].

ЛитератураПравить

• Wahba, G. (1990). Spline Models for Observational Data. SIAM, Philadelphia.
• Green, P. J. and Silverman, B. W. (1994). Nonparametric Regression and Generalized Linear Models. CRC Press.
• De Boor, C. (2001). A Practical Guide to Splines (Revised Edition). Springer.
• Березовский, М. В. Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы. Диссертация.