Алгоритм LOWESS

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

Версия от 16:11, 5 января 2010; Валентин Голодов (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

Введение

Рис. 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)= \left{ (1-|z|^2)^2, \, \, |z|<=1 \\ 0, \,\, |z|>1 \right.$

Замечание

Возможны и другие варианты выбора весов $\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-оценки]

$K(z)= \left{ z^2, \, \, \, |z|<=c\\ 2c|z|-c_2, \, \, \, |z|>c \right.$

Алгоритм LOWESS

Вход

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

$w_t, \,\,\, t=1,\ldots,m$ весовые функции;

Выход

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

Алгоритм 1.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.2

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$ .

5. пока веса $\delta_t$ не стабилизируются

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

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

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

На рисунке 4 представлен пример робастного локально-линейного сглаживания с помощь алгоритма LOWESS. С числом итераций цикла равным 2 и параметром сглаживания $f=0.5$ , то есть для приближения используется $k=\left\lfloor n/2 \right\rfloor$ ближайших точек выборки.

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

Литература

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

Срок: 6 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта 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»

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

Алгоритм LOWESS

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

Содержание

Введение

Примеры

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

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

Замечание

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

Замечание

Алгоритм LOWESS

Вход

Выход

Алгоритм 1.1

Алгоритм 1.2

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

Литература

См. также

Просмотры

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

Навигация

Поиск

Инструменты