Алгоритм LOWESS

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Пример)
(→Пример)
Строка 58: Строка 58:
!22
!22
!23
!23
-
!24 !25 !26 !27 !28 !29 !30
+
!24
 +
!25
 +
!26
 +
!27
 +
!28
 +
!29
 +
!30
|-
|-
|X
|X
-
|130 |225 |95 |100 |170 |65 |175| 130| 80| 150| 150| 107 |122| 110| 52|
+
|130
-
| 72 |110| 97| 92| 90 |70 |130| 130| 88| 48 |85 |139| 103| 110| 65
+
|225
 +
|95
 +
|100
 +
|170
 +
|65
 +
|175
 +
|130
 +
|80
 +
|150
 +
|150
 +
|107
 +
|122
 +
|110
 +
|52
 +
|72
 +
|110
 +
|97
 +
|92
 +
|90
 +
|70
 +
|130
 +
|130
 +
|88
 +
|48
 +
|85
 +
|139
 +
|103
 +
|110
 +
|65
|-
|-
-
|Y | 18| 14| 25| 19| 13| 31 |14 |13| 28| 14| 11| 21| 20| 16| 31 |
+
|Y
-
15| 21| 18| 25| 23| 32| 13| 15| 25| 43| 20| 18 |20| 21| 34
+
|18
-
+
|14
-
|}
+
|25
 +
|19
 +
|13
 +
|31
 +
|14
 +
|13
 +
|28
 +
|14
 +
|11
 +
|21
 +
|20
 +
|16
 +
|31
 +
|15
 +
|21
 +
|18
 +
|25
 +
|23
 +
|32
 +
|13
 +
|15
 +
|25
 +
|43
 +
|20
 +
|18
 +
|20
 +
|21
 +
|34
 +
}
[[Изображение:Loess_smooth.jpg||Рис. 1. Пример применения loess-сглаживания|400px]]
[[Изображение:Loess_smooth.jpg||Рис. 1. Пример применения loess-сглаживания|400px]]

Версия 20:59, 4 января 2010

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

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


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

Содержание

Введение

Данная методика была предложена Кливлендом(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 какая указывает доля данных используется в процедуре. Если 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*IQR, Если m > 100, где IQR - межквартильных размах(interquartile range).

С такими параметрами вычисления будут выполнены для примерно 100 точек.

Пример

Переменная 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
X 130 225 95 100 170 65 175 130 80 150 150 107 122 110 52 72 110 97 92 90 70 130 130 88 48 85 139 103 110 65
Y 18 14 25 19 13 31 14 13 28 14 11 21 20 16 31 15 21 18 25 23 32 13 15 25 43 20 18 20 21 34

} Рис. 1. Пример применения loess-сглаживания

Решается задача восстановления регрессии. Задано пространство объектов X и множество возможных ответов Y=R. Существует неизвестная целевая зависимость y^*: X \rightarrow Y, значения которой известны только на объектах обучающей выборки . Требуется построить алгоритм a: X \rightarrow Y , аппроксимирующий целевую зависимость y^*.

Непараметрическая регрессия

Непараметрическое восстановление регрессии основано на идее, что значение a(x) вычисляется

для каждого объекта x по нескольким ближайшим к нему объектам обучающей выборки.

В формуле Надарая–Ватсона для учета близости объектов x_i обучающей выборки к объекту a(x) предлагалось использовать невозрастающую, гладкую, ограниченную функцию K: [0,\infty) \rightarrow [0,\infty), называемую ядром:

w_i(x) = K\left( \frac{\rho(x, x_i)}{h}\right)

Параметр h называется шириной ядра или шириной окна сглаживания. Чем меньше h, тем быстрее будут убывать веса w_i(x) по мере удаления x_i от x. В общем случае h зависит от объекта x, т.е. h=h(x). Тогда веса вычисляются по формуле \textstyle w_i(x) = K\left( \frac{\rho(x, x_i)}{h(x)}\right)

Оптимизация ширины окна

Чтобы оценить при данном h и K точность локальной аппроксимации в точке x_i, саму эту точку необходимо исключить из обучающей выборки. Если этого не делать, минимум ошибки будет достигаться при h\rightarrow 0. Такой способ оценивания оптимальной ширины окна называется скользящим контролем с исключением объектов по одному (leave-one-out, LOO):

LOO(h,X^m) = \sum_{i=1}^m{\left(a_h(x_i;X^m\setminus\{x_i\}) - y_i \right)^2} \rightarrow min\limits_h

Проблема выбросов

Оценка Надарайя–Ватсона \textstyle a_h(x,X^m) = \frac{\sum_{i=1}^m{y_iw_i}}{\sum_{i=1}^m{w_i}}

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

\varepsilon_i = \left | a_h \left (x_i;X^m\setminus\{x_i\} \right) -y_i \right |

тем в большей степени прецедент (x_i,y_i) является выбросом , и тем меньше должен быть его вес. Эти соображения приводят к идее домножить веса w_i(x) на коэффициенты \gamma_i = \bar{K}(\varepsilon_i), где \bar{K} — ещё одно ядро, вообще говоря, отличное от K.

Алгоритм LOWESS

Вход

X^m - обучающая выборка;

w_i \, i=1,\ldots,m весовые функции;

Выход

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

Алгоритм

1: инициализация
\gamma_i:=1, i=1,\ldots,m
2: повторять
3: вычислить оценки скользящего контроля на каждом объекте:
a_i:=a_h\( x_i;X^m\setminus\{x_i\} \)=\frac{\sum_{j=1,j\ne i}^m y_j\gamma_j w_j}{\sum_{j=1,j\ne i}^m \gamma_j w_j },\;i=1,\ldots,m
4: вычислить новые значения коэффициентов \gamma_i:
\varepsilon_i = \left | a_i -y_i \right |
\gamma_i:=\bar{K}( \varepsilon_i ) ,\;i=1,\ldots,m;
5: пока коэффициенты \gamma_i не стабилизируются

Коэффициенты \gamma_i, как и ошибки \varepsilon_i, зависят от функции a_h, которая, в свою очередь, зависит от \gamma_i. На каждой итерации строится функция a_h, затем уточняются весовые множители \gamma_i. Как правило, этот процесс сходится довольно быстро. Он называется локально взвешенным сглаживанием (locally weighted scatter plot smoothing, LOWESS).

Выбор ядра \bar{K}

В качестве ядра \bar{K} большинство практических источников рекомендуют использовать следующее:

Пусть s - есть медиана коэффициентов \gamma_1,\ldots,\gamma_m, тогда \gamma_i = K(\frac{\varepsilon_i}{6s}), где

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

Более простой вариант, состоит в отбросе t коэффициентов, соответствующих объектам с максимальными \varepsilon_i. Это соотвествует ядру

K(z)=[z<\varepsilon^{(m-t)}], \, \, \\ K(z)=0, \,\, |z|>=\varepsilon^{(m-t)},

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

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

Литература

  1. Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
  1. A.I. McLeod Statistics 259b Robust Loess: S lowess. — 2004.
  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.

См. также


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

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

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


→

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