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

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

(Различия между версиями)

Версия 10:35, 17 июня 2009

Содержание

1 Постановка задачи
2 Алгоритм взвешенных ближайших соседей
- 2.1 Алгоритм отыскания оптимальных параметров
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература
7 Замечания

$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^l/x_i;k;q)].$

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

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

Пример 1

Рассмотрим пример на модельных данных. Выборка состоит из четырех классов, которые являются гауссовскими рапределением с диагональными матрицами ковариации. Классы легко разделимы.

%% Example 1
% Example, which is simply classifed by WeightedKNN. It seems like XOR
% problem.
 
%% generate training sample
% generate 2 groups of normal classes. Each group consistes of 2 simple
% normal classes
XL1 = [GetNormClass(50,[0,0],[1,1]); GetNormClass(50,[6,6],[1,1])];
XL2 = [GetNormClass(50,[6,0],[1,1]); GetNormClass(50,[0,6],[1,1])]; 
XL = [XL1; XL2];
YL = [repmat(1,100,1);repmat(2,100,1)];
 
%% generate control data with the same distribution
X1 = [GetNormClass(50,[0,0],[1,1]); GetNormClass(50,[6,6],[1,1])];
X2 = [GetNormClass(50,[6,0],[1,1]); GetNormClass(50,[0,6],[1,1])];
X = [X1; X2];
Y = [repmat(1,100,1);repmat(2,100,1)];
 
%% get classification
%% choosing parametrs
PP = ParAdjust(XL, YL);
PP.XL = XL;
PP.YL = YL;
%% classification
Y = WeightKNN(X, PP);
 
%% results visuaisation
%% plotting real classes of objects
plot(X1(:,1),X1(:,2),'*r');
hold on
plot(X2(:,1),X2(:,2),'*b');
 
%% plotting classification results
plot(X(Y == 1,1),X(Y == 1,2),'or');
plot(X(Y == 2,1),X(Y == 2,2),'ob');
hold off

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

Пример 2

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

%generating 4 sample normal classes
XL1 = GetNormClass(100,[5,0],[10,2]); 
XL2 = GetNormClass(100,[5,10],[10,2]);
XL3 = GetNormClass(100,[0,5],[4,4]);
XL4 = GetNormClass(100,[10,5],[4,4]);
 
XL = [XL1; XL2; XL3; XL4];
YL = [repmat(1,100,1);repmat(2,100,1);repmat(3,100,1);repmat(4,100,1)];
 
%generating control data with the same distribution
X1 = GetNormClass(300,[5,0],[10,2]); 
X2 = GetNormClass(300,[5,10],[10,2]);
X3 = GetNormClass(300,[0,5],[4,4]);
X4 = GetNormClass(300,[10,5],[4,4]);
X = [X1; X2; X3; X4];
 
%getting classification
Y = makeWeightedKNN(XL, YL, X)
 
%plotting control data
plot(X1(:,1),X1(:,2),'*r');
hold on
plot(X2(:,1),X2(:,2),'*b');
plot(X3(:,1),X3(:,2),'*g');
plot(X4(:,1),X4(:,2),'*y');
 
%plotting classified data
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');
plot(X(Y == 4,1),X(Y == 4,2),'oy');
errors = sum([Y(1:100) == 1; Y(101:200) == 2; Y(201:300) == 3; Y(301:400) == 4])
 
hold off

На графике по осям отложены величины признаков объектов, различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующих цветов. Алгоритм допустил 10% ошибок при обучении и 9% ошибок на контрольной выборке.

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

Проведем проверку алгоритма на классической задаче: Ирисы Фишера Объектами являются три типа ирисов: 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;

На графике различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующих цветов. Алгоритм хорошо классифицировал ирисы, допустив 4% ошибок.

Исходный код

Скачать листинги алгоритмов можно здесь makeWeightedKNN.m, FeaturesStand.m, ParAdjust.m, WeightKNN.m, GetNormClass.m.

Смотри также

Литература

К. В. Воронцов, Лекции по метрическим алгоритмам классификации
Bishop C. - Pattern Recognition and Machine Learning (Springer, 2006)

Данная статья является непроверенным учебным заданием.

Студент: Участник:Янович Юрий

Преподаватель: Участник:В.В. Стрижов

Срок: 28 мая 2009

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

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

Замечания

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_k_%D0%B2%D0%B7%D0%B2%D0%B5%D1%88%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B5%D0%B9_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категория: Непроверенные учебные задания

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

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

Версия 10:35, 17 июня 2009

Содержание

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

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

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

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

Пример 1

Пример 2

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

Исходный код

Смотри также

Литература

Замечания

Просмотры

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

Навигация

Поиск

Инструменты

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

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

Версия 10:35, 17 июня 2009

Содержание

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

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

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

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

Пример 1

Пример 2

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

Исходный код

Смотри также

Литература

Замечания

Просмотры

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

Навигация

Поиск

Инструменты

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