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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 3: Строка 3:
== Постановка задачи ==
== Постановка задачи ==
-
Пусть <tex>X \in \mathbb{R}^n\</tex> - множество объектов; <tex>Y</tex> - множество допустимых ответов. Задана обучающая выборка <tex>\{(x_i,y_i)\}_{i=1}^\ell</tex>. Задано множество объектов <tex>\ X^m ={(x_i)\}_{i=1}^m</tex>.
+
Пусть <tex>X \in \mathbb{R}^n\</tex> - множество объектов; <tex>Y</tex> - множество допустимых ответов. Задана обучающая выборка <tex>\{(x_i,y_i)\}_{i=1}^\ell</tex>. Задано множество объектов <tex>\ X^m ={x_i}_{i=1}^m</tex>.
Требуется найти найти множество ответов <tex>\{y_i}_{i=1}^m</tex> для объектов <tex>\{x_i}_{i=1}^m</tex>.
Требуется найти найти множество ответов <tex>\{y_i}_{i=1}^m</tex> для объектов <tex>\{x_i}_{i=1}^m</tex>.
Строка 26: Строка 26:
В рассматриваемом примере <tex>w(i,x) = [i\leq k] q^i,</tex> что соответствует методу <tex>k</tex> экспоненциально взвешенных ближайших соседей, причем предполагается <tex>0.5 \leq q \leq 1</tex>.
В рассматриваемом примере <tex>w(i,x) = [i\leq k] q^i,</tex> что соответствует методу <tex>k</tex> экспоненциально взвешенных ближайших соседей, причем предполагается <tex>0.5 \leq q \leq 1</tex>.
-
== Алгоритм отыскания оптимальных параметров ==
+
=== Алгоритм отыскания оптимальных параметров ===
Оптимальные значения параметров <tex>K</tex> и <tex>q</tex> определяют по критерию скользящего контроля с исключением объектов по одному:
Оптимальные значения параметров <tex>K</tex> и <tex>q</tex> определяют по критерию скользящего контроля с исключением объектов по одному:
<tex>(k^{*};q^{*}) = \arg{ } \max_{k,q}\ LOO(k;q;X^\ell\),</tex> где
<tex>(k^{*};q^{*}) = \arg{ } \max_{k,q}\ LOO(k;q;X^\ell\),</tex> где
Строка 35: Строка 35:
=== Пример 1 ===
=== Пример 1 ===
 +
Рассмотрим пример на модельных данных. Выборка состоит из четырех классов, которые являются гауссовскими рапределением с диагональными матрицами ковариации. Классы легко разделимы.
 +
<source lang="matlab">
 +
%generating 4 sample normal classes
 +
XL1 = GetNormClass(50,[0,0],[1,1]);
 +
XL2 = GetNormClass(50,[6,6],[1,1]);
 +
XL3 = GetNormClass(50,[6,0],[1,1]);
 +
XL4 = GetNormClass(50,[0,6],[1,1]);
 +
 +
XL = [XL1; XL2; XL3; XL4];
 +
YL = [repmat(1,50,1);repmat(2,50,1);repmat(3,50,1);repmat(4,50,1)];
 +
 +
%generating control data with the same distribution
 +
X1 = GetNormClass(50,[0,0],[1,1]);
 +
X2 = GetNormClass(50,[6,6],[1,1]);
 +
X3 = GetNormClass(50,[6,0],[1,1]);
 +
X4 = GetNormClass(50,[0,6],[1,1]);
 +
 +
X = [X1; X2; X3; X4];
 +
Y = YL;
 +
 +
%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');
 +
 +
hold off
 +
</source>
 +
[[Изображение:WKNN_ex1.png|500px]]
 +
 +
На графике по осям отложены величины признаков объектов, различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующих цветов.
 +
Алгоритм не допустил при классификации ни одной ошибки.
 +
=== Пример 2 ===
=== Пример 2 ===
 +
В качестве второго примера возьмем четыре плохо разделимых класса. Классы обладают большой дисперсией. Можно наблюдать области, в которых элементы различны классов проникают в чужие классы.
 +
<source lang="matlab">
 +
%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
 +
</source>
 +
[[Изображение:WKNN_ex2.png|500px]]
 +
 +
На графике по осям отложены величины признаков объектов, различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующих цветов. Алгоритм допустил 10% ошибок при обучении и 9% ошибок на контрольной выборке.
 +
=== Пример на реальных данных: ирисы ===
=== Пример на реальных данных: ирисы ===
Строка 79: Строка 163:
[[Изображение:Ireses_sorted_by_WeightedKNN.png|500px]]
[[Изображение:Ireses_sorted_by_WeightedKNN.png|500px]]
-
Алгоритм хорошо классифицировал ирисы, допустив 4% ошибок.
+
На графике различные классы показаны крестиками различных цветов, а результат классификации показан кружочками соотвествующих цветов. Алгоритм хорошо классифицировал ирисы, допустив 4% ошибок.
== Исходный код ==
== Исходный код ==

Версия 09:28, 26 мая 2009

Содержание

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

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

%generating 4 sample normal classes
XL1 = GetNormClass(50,[0,0],[1,1]); 
XL2 = GetNormClass(50,[6,6],[1,1]);
XL3 = GetNormClass(50,[6,0],[1,1]);
XL4 = GetNormClass(50,[0,6],[1,1]);
 
XL = [XL1; XL2; XL3; XL4];
YL = [repmat(1,50,1);repmat(2,50,1);repmat(3,50,1);repmat(4,50,1)];
 
%generating control data with the same distribution
X1 = GetNormClass(50,[0,0],[1,1]); 
X2 = GetNormClass(50,[6,6],[1,1]);
X3 = GetNormClass(50,[6,0],[1,1]);
X4 = GetNormClass(50,[0,6],[1,1]);
 
X = [X1; X2; X3; X4];
Y = YL;
 
%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');
 
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% ошибок.

Исходный код

Смотри также

Литература

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

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

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


Замечания

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