Алгоритм LOWESS
Материал из MachineLearning.
(→Алгоритм) |
|||
Строка 54: | Строка 54: | ||
==== Алгоритм ==== | ==== Алгоритм ==== | ||
1: инициализация | 1: инициализация | ||
- | ::<tex>\gamma_i:=1, i=1,\ldots, | + | ::<tex>\gamma_i:=1, i=1,\ldots,m</tex> |
2: '''повторять''' | 2: '''повторять''' | ||
3: вычислить оценки скользящего контроля на каждом объекте: | 3: вычислить оценки скользящего контроля на каждом объекте: | ||
- | ::<tex>a_i:=a_h\( x_i;X^ | + | ::<tex>a_i:=a_h\( x_i;X^m\setminus\{x_i\} \)=\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</tex> |
4: вычислить коэффициенты <tex>\gamma_i</tex>: | 4: вычислить коэффициенты <tex>\gamma_i</tex>: | ||
- | ::<tex>\gamma_i:=\ | + | ::<tex>\gamma_i:=\bar{K}( \| a_i\;-\;y_i\| ) ,\;i=1,\ldots,m</tex>; |
5: '''пока''' коэффициенты <tex>\gamma_i</tex> не стабилизируются | 5: '''пока''' коэффициенты <tex>\gamma_i</tex> не стабилизируются | ||
Версия 21:47, 28 декабря 2009
Статья плохо доработана. |
Алгоритм LOWESS (locally weighted scatter plot smoothing) - локально взвешенное сглаживание.
Содержание |
Постановка задачи
Решается задача восстановления регрессии. Задано пространство объектов и множество возможных ответов . Существует неизвестная целевая зависимость , значения которой известны только на объектах обучающей выборки . Требуется построить алгоритм , аппроксимирующий целевую зависимость .
Непараметрическая регрессия
Непараметрическое восстановление регрессии основано на идее, что значение вычисляется для каждого объекта по нескольким ближайшим к нему объектам обучающей выборки.
В формуле Надарая–Ватсона для учета близости объектов обучающей выборки к объекту предлагалось использовать невозрастающую, гладкую, ограниченную функцию , называемую ядром:
Параметр называется шириной ядра или шириной окна сглаживания. Чем меньше , тем быстрее будут убывать веса по мере удаления от .
Оптимизация ширины окна
Чтобы оценить при данном или точность локальной аппроксимации в точке , саму эту точку необходимо исключить из обучающей выборки. Если этого не делать, минимум ошибки будет достигаться при . Такой способ оценивания называется скользящим контролем с исключением объектов по одному (leave-one-out, LOO):
Оценка Надарайя–Ватсона крайне чувствительна к большим одиночным выбросам. На практике легко идентифицируются только грубые ошибки, возникающие, например, в результате сбоя оборудования или невнимательности персонала при подготовке данных. В общем случае можно лишь утверждать, что чем больше величина ошибки
тем в большей степени прецедент является выбросом , и тем меньше должен быть его вес. Эти соображения приводят к идее домножить веса на коэффициенты , где — ещё одно ядро, вообще говоря, отличное от .
Алгоритм LOWESS
Вход
- обучающая выборка
Выход
Коэффициенты
Алгоритм
1: инициализация
2: повторять 3: вычислить оценки скользящего контроля на каждом объекте:
4: вычислить коэффициенты :
- ;
5: пока коэффициенты не стабилизируются
Коэффициенты , как и ошибки , зависят от функции , которая, в свою очередь, зависит от . Разумеется, это не "порочный круг", а хороший повод для организации итерационного процесса. На каждой итерации строится функция , затем уточняются весовые множители . Как правило, этот процесс сходится довольно быстро.
Литература
- Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
См. также
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
→