115
правок
Изменения
→Постановка задачи
Пусть задано пространство объектов X и множество возможных ответов <math>Y = \mathbb{R}</math>. Существует неизвестная зависимость <math>y^*:X \rightarrow Y</math>, значения которой известны только на объектах обучающией выборки <math>X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i)</math>. Требуется построить алгоритм <math>a:\ X\rightarrow Y</math>, аппроксимирующий неизвестную зависимость <math>y^*</math>. Предполагается, что на множестве X задана метрика <math>\rho(x,x')</math>. <br>
Также стоит определить следующее. Для вычисления <math>a(x) = \alpha</math> при <math>\forall x \in X</math>, воспользуемся методом наименьших квадратов:
<math>Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}</math>, где <math>\omega_i</math> - это вес i-ого объекта. Веса <math>\omega_i </math> разумно задать так, чтобы они убывали по мере увеличения расстояния <math>\rho(x,x_i)</math>. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию <math>K:[0, \infty) \rightarrow [0, \infty)</math>, называемую ядром, и представить <math>\omega_i</math> в следующем виде :
<math>\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )</math>, где h — ширина окна.
Приравняв нулю производную <math>\frac{\partial Q}{\partial \alpha} = 0</math>, и, выразив <math>\alpha</math>,получаем формулу Надарая-Ватсона :
<math>a_h(x;X^l) = \frac{\sum_{i=1}^{l} y_i\omega_i(x)}{\sum_{i=1}^{l} \omega_i(x)} = \frac{\sum_{i=1}^{l} y_iK\left(\frac{\rho(x,x_i)}{h} \right )}{\sum_{i=1}^{l} K\left(\frac{\rho(x,x_i)}{h} \right )}</math>
====Псевдокод====
ВХОД: <math>X^\ell</math> - обучающая выборка;
