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

Поделись знанием:
Перейти к: навигация, поиск

Сглаживающий сплайн (англ. smoothing spline) это метод сглаживания (аппроксимации кривой набора зашумлённых исходных данных) с использованием сплайн-функций.





Определение

Пусть <math>(x_i,Y_i);x_1<x_2<\dots<x_n, i \in \mathbb{Z} </math> последовательность наблюдений, порождённых выражением <math>Y_i = \mu(x_i)</math>. Приближение сглаживающими сплайнами <math>\hat\mu</math> функции <math>\mu</math> определяется как функция (в классе дважды дифференцируемых функций), минимизирующая[1]

<math>

\sum_{i=1}^n (Y_i - \hat\mu(x_i))^2 + \lambda \int_{x_1}^{x_n} \hat\mu(x)^2 \,dx. </math>

Замечания:

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

Вывод сглаживающего сплайна

Для удобства разделим нахождение выражений, описывающих сглаживающий сплайн, на два этапа

  1. Для начала найдём значения <math>\hat\mu(x_i);i=1,\ldots,n</math>.
  2. Из этих значений найдём <math>\hat\mu(x)</math> для всех x.

Начнём со второго шага.

Дан вектор <math>\hat{m} = (\hat\mu(x_1),\ldots,\hat\mu(x_n))^T</math> «подогнанных» значений, сумма квадратов в критерии сплайна — константа. Требуется только минимизировать <math>\int \hat\mu(x)^2 \, dx</math>, и минимизация — натуральный кубический сплайн, интерполирующий точки <math>(x_i,\hat\mu(x_i))</math>. Данный интерполяционный сплайн это линейный оператор, и он может быть представлен в форме:

<math>
 \hat\mu(x) = \sum_{i=1}^n \hat\mu(x_i) f_i(x)

</math> где <math>f_i(x)</math> набор базисных сплайн-функций. В результате штраф за негладкость имеет форму

<math>

\int \hat\mu(x)^2 dx = \hat{m}^T A \hat{m}. </math> где элементы A — <math>\int f_i(x) f_j(x)dx</math>. Базисные функции и матрица A зависят от конфигурации независимых переменных <math>x_i</math>, но не от <math>Y_i</math> или <math>\hat m</math>.

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

<math>

\|Y - \hat m\|^2 + \lambda \hat{m}^T A \hat m, </math> где <math>Y=(Y_1,\ldots,Y_n)^T</math>. минимизация по <math>\hat m</math> даёт

<math>

\hat m = (I + \lambda A)^{-1} Y. </math>

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

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

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

Связанные методы

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

  • Регрессионных сплайнов. В этом методе данные апроксимируются набором базисных сплайн-функций с уменьшенным количеством узлов, как правило по МНК. Штрафы за негладкость не используются.
  • Penalized Splines. Сочетают уменьшенное количество узлов регрессионных сплайнов с штрафом за негладкость сглаживающих сплайнов.[5]
  • Метод упругой карты. Данный метод сочетает МНК-штрафы для ошибки аппроксимации со штрафами за кривизну и растяжение аппроксимирующего множества и использует крупный шаг дискретизации для оптимизации проблемы.

Исходный код

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

Напишите отзыв о статье "Сглаживающий сплайн"

Примечания

  1. ↑ Hastie T. J. Generalized Additive Models. — Chapman and Hall, 1990. — ISBN 0-412-34390-8.
  2. ↑ Robert E. Smith Jr., Joseph M Price and Lona M. Howser. [www.pdas.com/refs/tnd7397.pdf A Smoothing Algorithm Using Cubic Spline Functions]. Проверено 31 мая 2011. [www.webcitation.org/6JdQprRu1 Архивировано из первоисточника 15 сентября 2013].
  3. ↑ N. Y. Graham. [www.alcatel-lucent.com/bstj/vol62-1983/articles/bstj62-1-101.pdf Smoothing With Periodic Cubic Splines]. Проверено 31 мая 2011. [www.webcitation.org/6JdQrLori Архивировано из первоисточника 15 сентября 2013].
  4. ↑ E.T.Y. Lee. [www.cs.bgu.ac.il/~leonid/na105/Splines/Lee.pdf Choosing nodes in parametric curve interpolation]. Проверено 28 июня 2011. [www.webcitation.org/6JdQs0g4x Архивировано из первоисточника 15 сентября 2013].
  5. ↑ Ruppert David. Semiparametric Regression. — Cambridge University Press, 2003. — ISBN 0-521-78050-0.

Литература

  • 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.
  • [www.dissercat.com/content/sglazhivayushchie-izogeometricheskie-i-robastnye-splainy-metody-i-algoritmy Березовский, М. В. Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы. Диссертация.]