Метод k взвешенных ближайших соседей (пример)

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

Версия от 21:56, 25 мая 2009; Yanovich (Обсуждение | вклад)

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

Содержание

1 Постановка задачи
2 Алгоритм взвешенных ближайших соседей
3 Алгоритм отыскания оптимальных параметров

$K$ взвешенных ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

Постановка задачи

Пусть $X \in \mathbb{R}^n\$ - множество объектов; $Y$ - множество допустимых ответов. Задана обучающая выборка $\{(x_i,y_i)\}_{i=1}^\ell$ . Задано множество объектов $\ X^m ={(x_i)\}_{i=1}^m$ .

Требуется найти найти множество ответов $\{y_i}_{i=1}^m$ для объектов $\{x_i}_{i=1}^m$ .

Алгоритм $K$ взвешенных ближайших соседей

На множестве объектов задается евклидова функция расстояния $\rho(x,x'):$

$\rho(x,x') = \sum_{i=1}^n (x_i-x'_i)^2.$

Для произвольного объекта $x\in \{x_i}_{i=1}^m$ расположим объекты обучающей выборки $x_i$ в порядке возрастания расстояний до $x$ :

$\rho(x,x_{1; x}) \leq \rho(x,x_{2; x}) \leq \cdots \leq \rho(x,x_{m; x}),$

где через $x_{i; x}$ обозначается тот объект обучающей выборки, который является $i$ -м соседом объекта $x$ . Аналогичное обозначение введём и для ответа на $i$ -м соседе: $y_{i; x}$ .

Таким образом, произвольный объект $x$ порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть

$a(x) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; x}=y \bigr] w(i,x),$

где $w(i,x)$ — заданная весовая функция, которая оценивает степень важности $i$ -го соседа для классификации объекта $u$ .

В рассматриваемом примере $w(i,x) = [i\leq k] q^i,$ что соответствует методу $k$ экспоненциально взвешенных ближайших соседей, причем предполагается $0.5 \leq q \leq 1$ .

Алгоритм отыскания оптимальных параметров

Оптимальные значения параметров $K$ и $q$ определяют по критерию скользящего контроля с исключением объектов по одному: $(k^{*};q^{*}) = \arg{ } \max_{k,q}\ LOO(k;q;X^\ell\),$ где $LOO(k;q;X^\ell\)= \sum_{i=1}^{\l}\[y_i = a(x_i;X^{m}{\}x_i;k;q).$