Перейти к основному содержимому

Обобщение метода K ближайших соседей с весами

В методе K ближайших соседей отклики ближайших соседей учитываются равномерно, с одинаковыми весами. Можно дополнительно немного повысить качество прогнозов, если позволить более близким ближайшим соседям влиять сильнее на прогноз, чем более далёким. Для этого равномерное усреднение по ближайшим соседям нужно заменить на взвешенное усреднение, где больший вес будет соответствовать более близким соседям.

В учебнике x1,x2,...,xN\mathbf{x}_1, \mathbf{x}_2,...,\mathbf{x}_N обозначают объекты обучающей выборки. Сейчас же пусть (x1,y1),(x2,y2),...(xK,yK)(\mathbf{x}_{1},y_{1}),(\mathbf{x}_{2},y_{2}),...(\mathbf{x}_{K},y_{K}) - ближайшие соседи в обучающей выборке для целевого объекта x\mathbf{x}, для которого мы строим прогноз. Причем эти соседи упорядочены по возрастанию расстояния до них:

ρ(x,x1)≤ρ(x,x2)≤...≤ρ(x,xK)\rho(\mathbf{x},\mathbf{x}_{1})\le\rho(\mathbf{x},\mathbf{x}_{2})\le...\le\rho(\mathbf{x},\mathbf{x}_{K})

Регрессионный прогноз базового метода строится простым усреднением по откликам ближайших соседей

y^(x)=1K∑k=1Kyk\widehat{y}(\mathbf{x})=\frac{1}{K}\sum_{k=1}^{K}y_{k}

Взвешенное обобщение строится уже взвешенным усреднением откликов:

y^(x)=∑k=1Kwkyk∑k=1Kwk\widehat{y}(\mathbf{x})=\frac{\sum_{k=1}^{K}w_k y_{k}}{\sum_{k=1}^{K}w_k}

Аналогично в задаче классификации базовым методом вероятности классов строятся по формуле:

1K(∑k=1KI[yk=1]∑k=1KI[yk=2]⋯∑k=1KI[yk=C])\frac{1}{K}\begin{pmatrix} \sum_{k=1}^{K}\mathbb{I}[y_{k}=1] \\ \sum_{k=1}^{K}\mathbb{I}[y_{k}=2] \\ \cdots \\ \sum_{k=1}^{K}\mathbb{I}[y_{k}=C] \\ \end{pmatrix}

Взвешенное обобщение учитывает каждого ближайшего соседа со своим весом:

1∑k=1Kwk(∑k=1KwkI[yk=1]∑k=1KwkI[yk=2]⋯∑k=1KwkI[yk=C])\frac{1}{\sum_{k=1}^K w_k}\begin{pmatrix} \sum_{k=1}^{K}w_k\mathbb{I}[y_{k}=1] \\ \sum_{k=1}^{K}w_k\mathbb{I}[y_{k}=2] \\ \cdots \\ \sum_{k=1}^{K}w_k\mathbb{I}[y_{k}=C] \\ \end{pmatrix}

О популярных методах расчета весов можно прочитать в следующей главе.