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

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

Версия 22:25, 25 мая 2009

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

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

Пусть - множество объектов; - множество допустимых ответов. Задана обучающая выборка . Задано множество объектов .

Требуется найти найти множество ответов для объектов .

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

На множестве объектов задается евклидова функция расстояния

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

где через обозначается тот объект обучающей выборки, который является -м соседом объекта . Аналогичное обозначение введём и для ответа на -м соседе: .

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

где — заданная весовая функция, которая оценивает степень важности -го соседа для классификации объекта .

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

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

Оптимальные значения параметров и определяют по критерию скользящего контроля с исключением объектов по одному: где

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

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

Пример 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 в учебном процессе.

Замечания