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

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

Перейти к: навигация, поиск

Содержание

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).

Вычислительный эксперимент

Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.

Пример 1

Пример 2

Пример на реальных данных: ирисы

Проведена проверка алгоритма на классической задаче: Ирисы Фишера Объектами являются три типа ирисов: setosa, versicolor, virginica

У каждого объекта есть четыре признака: длина лепестка, ширина лепестка, длина чашелистика, ширина чашелистика. Для удобства визуализации результатов будем использовать первые два признака. В качестве обучающей и контрольной выборок выбрано по 25 представителей каждого из типов ирисов.

%load data
load 'iris.txt';
S = iris;
S(:,1:2) = []; %eliminating first two attributes
XL = S([1:25,51:75,101:125],:);
X = S([26:50,76:100,126:150],:);
YL = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; %creating class labels
Y = [ones([25,1]);2*ones([25,1]);3*ones([25,1])];
 
%plotting data
plot(X(Y == 1,1),X(Y == 1,2),'*r');
hold on
plot(X(Y == 2,1),X(Y == 2,2),'*b');
plot(X(Y == 3,1),X(Y == 3,2),'*g');
 
%getting classification
Y = makeWeightedKNN(XL, YL, X);
 
%plotting resulting classification
plot(X(Y == 1,1),X(Y == 1,2),'or');
plot(X(Y == 2,1),X(Y == 2,2),'ob');
plot(X(Y == 3,1),X(Y == 3,2),'og');
title('Irises classification')
xlabel('petal width, cm');
ylabel('petal length, cm');
legend('Iris Setosa','Iris Versicolour','Iris Virginica','Location','NorthWest');
hold off;

Изображение:Ireses sorted.png

Алгоритм хорошо классифицировал ирисы, допустив 4% ошибок.

Исходный код

Смотри также

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Янович Юрий
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Замечания

Личные инструменты