Алгоритм LOWESS

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

(Различия между версиями)

Перейти к: навигация, поиск

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

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

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

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

Содержание

1 Введение
- 1.1 Примеры
2 Технические детали алгоритма
3 Примеры применения
4 Литература
5 См. также

Введение

Рис. 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. Задание параметра сглаживания $f$

На Рис. 2. Приведена иллюстрация уровня сглаживания в зависимости от значения параметра $f$

Сглаживание также может быть локально квадратичным, в этом случае модель для $y_t$ имеет вид

$y_t=\alpha_t+\beta_t x_t +\gamma_t x_t^2+ \varepsilon_t.$

Примеры сглаживания с квадратичным локальным приближением показаны на Рис. 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. Пример для модельных данных

Литература

A.I. McLeod Statistics 259b Robust Loess: S lowess. — 2004.

Хардле В. Прикладная непараметрическая регрессия.. — Мир, 1993.

Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.

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.

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

См. также

Непараметрическая регрессия
Регрессионный анализ
Local regression
Расин, Джеффри (2008) «Непараметрическая эконометрика: вводный курс», Квантиль, №4, стр. 7–56.

Данная статья является непроверенным учебным заданием.

Студент: Участник:Валентин Голодов

Преподаватель: Участник:Vokov

Срок: 31 декабря 2009

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

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

→

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LOWESS»

Категории: Регрессионный анализ | Непроверенные учебные задания

@@ Строка 81: / Строка 81: @@
 Коэффициенты <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>.
-:'''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> не стабилизируются

Алгоритм LOWESS

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

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

Содержание

Введение

Примеры

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

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

Замечание

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

Замечание

Алгоритм LOWESS

Вход

Выход

Алгоритм 1

Алгоритм 1‘

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

Литература

См. также

Просмотры

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

Навигация

Поиск

Инструменты