Метод 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 ={ | + | Пусть <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
|
взвешенных ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Постановка задачи
Пусть - множество объектов;
- множество допустимых ответов. Задана обучающая выборка
. Задано множество объектов
.
Требуется найти найти множество ответов для объектов
.
Алгоритм
взвешенных ближайших соседей
На множестве объектов задается евклидова функция расстояния
Для произвольного объекта расположим
объекты обучающей выборки
в порядке возрастания расстояний до
:
где через обозначается
тот объект обучающей выборки, который является
-м соседом объекта
.
Аналогичное обозначение введём и для ответа на
-м соседе:
.
Таким образом, произвольный объект порождает свою перенумерацию выборки.
В наиболее общем виде алгоритм ближайших соседей есть
где — заданная весовая функция,
которая оценивает степень важности
-го соседа для классификации объекта
.
В рассматриваемом примере что соответствует методу
экспоненциально взвешенных ближайших соседей, причем предполагается
.
Алгоритм отыскания оптимальных параметров
Оптимальные значения параметров и
определяют по критерию скользящего контроля с исключением объектов по одному:
где
Вычислительный эксперимент
Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.
Пример 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% ошибок.
Исходный код
Смотри также
Литература
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |