Алгоритм LOWESS

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Алгоритм)
(Алгоритм)
Строка 81: Строка 81:
Коэффициенты <tex>\delta_t, \,\,\, t=1,\ldots,m</tex>
Коэффициенты <tex>\delta_t, \,\,\, t=1,\ldots,m</tex>
-
==== Алгоритм ====
+
==== Алгоритм 1====
-
:'''1''' Построить линеиную регрессию во всех <tex>t=1,\ldots,t=m</tex> точках, используя весовые функции <tex>w_t</tex>, тем самым получим оценки для параметров модели <tex>\hat{\alpha_t}, \hat{\beta_t}</tex>.
+
:'''1.''' Построить линеиную регрессию во всех <tex>t=1,\ldots,t=m</tex> точках, используя весовые функции <tex>w_t</tex>, тем самым получим оценки для параметров модели <tex>\hat{\alpha_t}, \hat{\beta_t}</tex>.
:А также приближения <tex>\hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t</tex>.
:А также приближения <tex>\hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t</tex>.
-
:'''2''' Инициализируем остатки <tex>\hat{\varepsilon_t}= \| \hat{y_t} - y_t \|</tex>. Вычислим робастные веса <tex>\delta_t</tex>
+
:'''2.''' Инициализируем остатки <tex>\hat{\varepsilon_t}= \| \hat{y_t} - y_t \|</tex>. Вычислим робастные веса <tex>\delta_t</tex>
-
:'''3''': '''повторять'''
+
:'''3.''' '''повторять'''
-
::'''4''' Построить линеиную регрессию во всех <tex>t=1,\ldots,t=m</tex> точках, используя весовые функции <tex>\delta_t w_t</tex>, тем самым получим оценки для параметров модели <tex>\hat{\alpha_t}, \hat{\beta_t}</tex>.
+
::'''4.''' Построить линеиную регрессию во всех <tex>t=1,\ldots,t=m</tex> точках, используя весовые функции <tex>\delta_t w_t</tex>, тем самым получим оценки для параметров модели <tex>\hat{\alpha_t}, \hat{\beta_t}</tex>.
-
::'''5''' По новому набору значений <tex>\hat{\varepsilon_t}= \| \hat{y_t} - y_t \|</tex> вычислить новые значения коэффициентов <tex>\delta_t</tex>. А также приближения <tex>\hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t</tex>.
+
::'''5.''' По новому набору значений <tex>\hat{\varepsilon_t}= \| \hat{y_t} - y_t \|</tex> вычислить новые значения коэффициентов <tex>\delta_t</tex>. А также приближения <tex>\hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t</tex>.
-
:'''6''' '''пока''' веса <tex>\delta_t</tex> не стабилизируются
+
:'''6.''' '''пока''' веса <tex>\delta_t</tex> не стабилизируются
-
При использовании ядровых функций для оценки весов объектов алгоритм можно модифицировать следующим образом
+
При использовании ядровых функций для оценки локальных весов объектов и робастных весов алгоритм модифицируется следующим образом:
 +
 
 +
==== Алгоритм 1‘====
 +
:'''1.''' Инициализировать <tex>\delta_1:=\ldots=\delta_m:=1</tex>
 +
:'''2.''' '''повторять'''
 +
::'''3.''' Вычислить оценки скользящего контроля на каждом объекте
 +
:: <tex> a_t:=a(x_t; X\setminus\{ x_t\}) = \frac{ \sum_{i=1, i\neq t }^{m} {y_i \delta_i K\left( \frac{\rho(x_i,x_t)}{h(x_t)}\right)} } {\sum_{i=1, i\neq t }^{m} {y_i K\left( \frac{\rho(x_i,x_t)}{h(x_t)}\right)} }</tex>
 +
::'''4.''' По новому набору значений <tex>\hat{\varepsilon_t}= \| \hat{y_t} - y_t \|</tex> вычислить новые значения коэффициентов <tex>\delta_t</tex>. А также приближения <tex>\hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t</tex>.
 +
:'''5.''' '''пока''' веса <tex>\delta_t</tex> не стабилизируются

Версия 15:11, 5 января 2010

Статья плохо доработана.

Имеются указания по её улучшению:


Алгоритм LOWESS (locally weighted scatter plot smoothing) - локально взвешенное сглаживание.

Содержание

Введение

Рис. 1. Пример применения lowess-сглаживания
Рис. 1. Пример применения lowess-сглаживания
Данная методика была предложена Кливлендом(Cleveland) в 1979 году для моделирования и сглаживания двумерных данных  X^m={(x_i, y_i)}_{i=1}^m. Эта техника предоставляет общий и гибкий подход для приближения двумерных данных.
Локально-линейная модель loess(lowess) можеть быть записана в виде:
 y_t=\alpha_t+\beta_t x_t + \varepsilon_t.
Эта модель может быть расширена на случай локально-квадратичной зависимости и на модель с бо‘льшим числом независимых переменных.
Параметры \alpha_t и \beta_t локально линейной модели оцениваются, с помощью локально взвешенной регрессии, которая присваивает объекту тем больший вес, чем более близок он близким к объекту t.
Степень сглаживания определяется параметром сглаживания f, который выбирает пользователь.
Параметр f указывает какая доля(fraction) данных используется в процедуре. Если f = 0.5, то только половина данных используется для оценки и влияет на результат, и тогда мы получим умеренное сглаживание. С другой стороны, если f = 0.8, то используются восемьдесят процентов данных, и сглаживание намного сильнее. Во всех случаях веса данных тем больше чем они ближе к объекту t.
Процедура оценки использует не метод наименьших квадратов, а более устойчивый(робастный) метод, который принимает меры против выбросов.
График приближенных значений
 y_t=\hat{\alpha_t}+\hat{\beta_t}x_t
от x_t полезен для принятия решения о характере связи между y_t и x_t. Для проверки качества приближения полученного с помощью процедуры устойчивого loess полезно посмотреть на график остатков обычной регресссии, то есть в осях (i) остатки от числа наблюдения (ii) остатки от прибли‘женных значений, (iii) остатки от значений независимой переменной. Как показал Кливленд, может быть предпочтительно использовать график в осях модули остатков от полученных приближенных значений вместо графика (ii) для устойчивого loess сглаживания, чтобы проверить наличие тренда или других систематических особенностей.
Когда m > 100 вычисления могут быть слишком долгими, в этом случае можно сократить количество вычислений оценивая \hat{\alpha_t} и \hat{\beta_t} только в точках отстоящих друг от друга как минимум на \delta единиц, где параметр \delta может задаваться либо приниматься по умолчанию. Рекомендуемые значения
\delta=0, Если m <= 100
\delta=0.03*IQR, Если m > 100, где IQR — [межквартильный размах](Interquartile range).
С такими параметрами вычисления будут выполнены для примерно 100 точек.

Примеры

Рис. 2. Задание параметра сглаживания
Рис. 2. Задание параметра сглаживания f
На Рис. 2. Приведена иллюстрация уровня сглаживания в зависимости от значения параметра f
Сглаживание также может быть локально квадратичным, в этом случае модель для y_t имеет вид
 y_t=\alpha_t+\beta_t x_t +\gamma_t x_t^2+ \varepsilon_t.

Примеры сглаживания с квадратичным локальным приближением показаны на Рис. 3.

Рис. 3. Локально квадратичное сглаживание
Рис. 3. Локально квадратичное сглаживание

Технические детали алгоритма

Базовое предположение состоит в следующем

y_t=g(x_t)+\varepsilon_t , t=1,\ldots,m

где g(x) - функция глаживания, остатки \varepsilon_t имеют нулевое математическое ожидание и фиксированную дисперсию. Затем сглаживание g мы приближаем локально-линейной(локально квадратичной, в случае нелинейной модели) функцией, чтобы получить

 y_t=\alpha_t + \beta_t x_t + \varepsilon_t.

Для четкого определения агоритма поясним концепцию локальных весов w(x_t) и робастных весов \delta(x_t).

Локальные веса

Рассмотрим один из широко распространенных примеров – функцию
W(z)=(1-|z|^3)^3, \, \, |z|<=1 \\ W(z)=0, \,\, |z|>1
Для заданного параметра 0 < f < 1 пусть r - ближайшее целое число к произведению  f*m. Пусть  h_t расстояние до r-того ближайшего соседа объекта x_t. Тогда локальный вес для любого объекта x в окрестности x_t есть
w(x)=W\left(\frac{x-x_t}{h_t}\right).

Замечание

Более общий подход к определению локальных весов состоит в выборе ширины окна h, в общем случае h=h(x_t), то есть зависящей от объекта x_t, и ядровой функции K(x)=K\left(\frac{\rho(x,x_t)}{h(x_t)} \right ). Тогда локальные веса вычисляются по формулам
w(x)=K \left( \frac{\rho(x,x_t)}{h(x_t)} \right ).
В этом случае отпадает необходимость задания параметра сглаживания f и его смысл эквивалентен выбору ширины окна h=h(x_t).

Робастные веса

Пусть

X^m\setminus\{x_t\} – обучающая выборка за исключением элемента x_i,
a_t:=a\( x_t;X^m\setminus\{x_t\} \) – ответ алгоритма a, обученного на выборке X^m\setminus\{x_t\} при работе на объекте x_t.
\hat{\varepsilon_t}= \|a_t-y_t \| – ошибка алгоритма на объекте x_i(ошибка скользящего контроля).

Пусть s - есть медиана величин\hat{\varepsilon_1},\ldots,\hat{\varepsilon_m}. тогда \delta_t = \bar{K}(\frac{\varepsilon_t}{6s}), где

\bar{K}(z)=(1-|z|^2)^2, \, \, |z|<=1 \\ \bar{K}(z)=0, \,\, |z|>1

Замечание

Возможны и другие варианты выбора весов \delta_t, например, занулить p штук, соответствующих наибольшим \hat{\varepsilon_t}. Это соотвествует ядру
\bar{K}(z)=[z<\hat{\varepsilon}^{(m-p)}],

где \hat{\varepsilon}^{(m-p)} –- (m-p) - тый член вариационного ряда \hat{\varepsilon}^{(1)}<=\ldots<=\hat{\varepsilon}^{(m)}

В весовой ядерной функции можно взять функцию Хубера (Huber, 1964) на которой основаны [M-оценки]

Алгоритм LOWESS

Вход

X^m - обучающая выборка;
w_t, \,\,\, t=1,\ldots,m весовые функции;

Выход

Коэффициенты \delta_t, \,\,\, t=1,\ldots,m

Алгоритм 1

1. Построить линеиную регрессию во всех t=1,\ldots,t=m точках, используя весовые функции w_t, тем самым получим оценки для параметров модели \hat{\alpha_t}, \hat{\beta_t}.
А также приближения \hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t.
2. Инициализируем остатки \hat{\varepsilon_t}= \| \hat{y_t} - y_t \|. Вычислим робастные веса \delta_t
3. повторять
4. Построить линеиную регрессию во всех t=1,\ldots,t=m точках, используя весовые функции \delta_t w_t, тем самым получим оценки для параметров модели \hat{\alpha_t}, \hat{\beta_t}.
5. По новому набору значений \hat{\varepsilon_t}= \| \hat{y_t} - y_t \| вычислить новые значения коэффициентов \delta_t. А также приближения \hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t.
6. пока веса \delta_t не стабилизируются

При использовании ядровых функций для оценки локальных весов объектов и робастных весов алгоритм модифицируется следующим образом:

Алгоритм 1‘

1. Инициализировать \delta_1:=\ldots=\delta_m:=1
2. повторять
3. Вычислить оценки скользящего контроля на каждом объекте
 a_t:=a(x_t; X\setminus\{ x_t\}) = \frac{ \sum_{i=1, i\neq t }^{m} {y_i \delta_i K\left( \frac{\rho(x_i,x_t)}{h(x_t)}\right)} } {\sum_{i=1, i\neq t }^{m} {y_i K\left( \frac{\rho(x_i,x_t)}{h(x_t)}\right)} }
4. По новому набору значений \hat{\varepsilon_t}= \| \hat{y_t} - y_t \| вычислить новые значения коэффициентов \delta_t. А также приближения \hat{y_t}=\hat{\alpha_t}+\hat{\beta_t}x_t.
5. пока веса \delta_t не стабилизируются


Коэффициенты \delta_t, как и ошибки \varepsilon_t, зависят от функции a, которая, в свою очередь, зависит от \delta_t. На каждой итерации строится функция a, затем уточняются весовые множители \delta_t. Как правило, этот процесс сходится довольно быстро. Однако в практических реализациях имеет смысл вводить ограничение на количество итераций, как правило это 2-3 итерации.

Примеры применения

Рис. 3. Пример для модельных данных
Рис. 3. Пример для модельных данных

Литература

  1. A.I. McLeod Statistics 259b Robust Loess: S lowess. — 2004.
  1. Хардле В. Прикладная непараметрическая регрессия.. — Мир, 1993.
  1. Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
  1. John A Berger, Sampsa Hautaniemi, Anna-Kaarina Järvinen, Henrik Edgren, Sanjit K Mitra and Jaakko Astola Optimized LOWESS normalization parameter selection for DNA microarray data. — BMC Bioinformatics, 2004.


  1. Maronna, A., R. Martin, V. Yohai Robust Statistics: Theory and Methods.. — Wiley, 2006.

См. также


Данная статья является непроверенным учебным заданием.
Студент: Участник:Валентин Голодов
Преподаватель: Участник:Vokov
Срок: 31 декабря 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Личные инструменты