Материал из MachineLearning.
Алгоритм LOWESS (locally weighted scatter plot smoothing) - локально взвешенное сглаживание.
Постановка задачи
Решается задача восстановления регрессии. Задано пространство объектов 
и множество возможных
ответов 
. Существует неизвестная целевая зависимость 
,
значения которой известны только на объектах обучающей выборки }_{i=1}^m)
.
Требуется построить алгоритм 
, аппроксимирующий целевую зависимость 
.
Непараметрическая регрессия
Непараметрическое восстановление регрессии основано на идее, что значение )
вычисляется
для каждого объекта 
по нескольким ближайшим к нему объектам обучающей выборки.
В формуле Надарая–Ватсона для учета близости объектов 
обучающей выборки к объекту
предлагалось использовать невозрастающую, гладкую, ограниченную функцию
 \rightarrow [0,\infty))
, называемую ядром:
 = K\left( \frac{\rho(x, x_i)}{h}\right))
Параметр 
называется шириной ядра или шириной окна сглаживания. Чем меньше ,
тем быстрее будут убывать веса )
по мере удаления от .
В общем случае зависит от объекта , т.е. )
. Тогда веса вычисляются по формуле
 = K\left( \frac{\rho(x, x_i)}{h(x)}\right))
Оптимизация ширины окна
Чтобы оценить при данном или 
точность локальной аппроксимации в точке ,
саму эту точку необходимо исключить из обучающей выборки. Если этого не делать, минимум ошибки будет
достигаться при 
. Такой способ оценивания называется скользящим контролем
с исключением объектов по одному (leave-one-out, LOO):
 = \sum_{i=1}^m{\left(a_h(x_i;X^m\setminus\{x_i\}) - y_i \right)^2} \rightarrow min\limits_h)
Оценка Надарайя–Ватсона  = \frac{\sum_{i=1}^m{y_iw_i}}{\sum_{i=1}^m{w_i}})
крайне чувствительна к большим одиночным выбросам. На практике легко идентифицируются только грубые ошибки,
возникающие, например, в результате сбоя оборудования или невнимательности персонала при подготовке данных.
В общем случае можно лишь утверждать, что чем больше величина ошибки
 -y_i \right |)
тем в большей степени прецедент )
является выбросом , и тем меньше должен быть его вес.
Эти соображения приводят к идее домножить веса на коэффициенты
)
, где 
— ещё одно ядро, вообще говоря,
отличное от .
Алгоритм LOWESS
Вход
- обучающая выборка
Выход
Коэффициенты 
Алгоритм
1: инициализация
2: повторять
3: вычислить оценки скользящего контроля на каждом объекте:
=\frac{\sum_{j=1,j\ne i}^m y_j\gamma_j K\(\frac{\rho(x_i,x_j)}{h(x_i)}\)}{\sum_{j=1,j\ne i}^m \gamma_jK\(\frac{\rho(x_i,x_j)}{h(x_i)}\)},\;i=1,\ldots,m)
4: вычислить новые значения коэффициентов 
:
 ,\;i=1,\ldots,m)
;
5: пока коэффициенты не стабилизируются
Коэффициенты , как и ошибки 
, зависят от функции 
, которая,
в свою очередь, зависит от . На каждой итерации строится функция ,
затем уточняются весовые множители . Как правило, этот процесс сходится довольно быстро.
Он называется локально взвешенным сглаживанием (locally weighted scatter plot smoothing, LOWESS).
Литература
- Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
См. также
| Данная статья является непроверенным учебным заданием.
- Студент: Участник:Валентин Голодов
- Преподаватель: Участник:Vokov
- Срок: 31 декабря 2009
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru.
По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.
См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.
|
→
