Метод k взвешенных ближайших соседей (пример)
Материал из MachineLearning.
(→Пример 2) |
(→Пример на реальных данных: ирисы) |
||
Строка 153: | Строка 153: | ||
В качестве обучающей и контрольной выборок выбрано по 25 представителей каждого из типов ирисов. | В качестве обучающей и контрольной выборок выбрано по 25 представителей каждого из типов ирисов. | ||
<source lang="matlab"> | <source lang="matlab"> | ||
- | %load data | + | %% Example 'iris' |
+ | % Example with real data | ||
+ | |||
+ | %% data preparation | ||
+ | %% load data | ||
load 'iris.txt'; | load 'iris.txt'; | ||
S = iris; | S = iris; | ||
- | S(:,1:2) = []; % | + | %% eliminating first two attributes |
+ | S(:,1:2) = []; | ||
+ | %% divide data into training part and pert to classify | ||
XL = S([1:25,51:75,101:125],:); | XL = S([1:25,51:75,101:125],:); | ||
X = S([26:50,76:100,126:150],:); | X = S([26:50,76:100,126:150],:); | ||
- | YL = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; | + | %% creating class labels |
+ | YL = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; | ||
Y = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; | Y = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; | ||
- | %plotting | + | %% plotting real classes of objects |
plot(X(Y == 1,1),X(Y == 1,2),'*r'); | plot(X(Y == 1,1),X(Y == 1,2),'*r'); | ||
hold on | hold on | ||
Строка 168: | Строка 175: | ||
plot(X(Y == 3,1),X(Y == 3,2),'*g'); | plot(X(Y == 3,1),X(Y == 3,2),'*g'); | ||
- | %getting classification | + | %% getting classification |
- | + | %% features standardization | |
+ | [p, m] = size(X); | ||
+ | [n, m] = size(XL); | ||
+ | Z = [XL; X]; | ||
+ | Z =FeaturesStand(Z); | ||
+ | XL = Z(1:n, :); | ||
+ | X = Z(n+1:n+p, :); | ||
+ | %% choosing parametrs | ||
+ | PP = ParAdjust(XL, YL); | ||
+ | PP.XL = XL; | ||
+ | PP.YL = YL; | ||
+ | %% classification | ||
+ | Y = WeightKNN(X, PP); | ||
- | %plotting resulting classification | + | %% plotting resulting classification |
plot(X(Y == 1,1),X(Y == 1,2),'or'); | plot(X(Y == 1,1),X(Y == 1,2),'or'); | ||
plot(X(Y == 2,1),X(Y == 2,2),'ob'); | plot(X(Y == 2,1),X(Y == 2,2),'ob'); | ||
Строка 179: | Строка 198: | ||
ylabel('petal length, cm'); | ylabel('petal length, cm'); | ||
legend('Iris Setosa','Iris Versicolour','Iris Virginica','Location','NorthWest'); | legend('Iris Setosa','Iris Versicolour','Iris Virginica','Location','NorthWest'); | ||
+ | |||
hold off; | hold off; | ||
</source> | </source> |
Версия 10:40, 17 июня 2009
|
взвешенных ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Постановка задачи
Пусть - множество объектов; - множество допустимых ответов. Задана обучающая выборка . Задано множество объектов .
Требуется найти найти множество ответов для объектов .
Алгоритм взвешенных ближайших соседей
На множестве объектов задается евклидова функция расстояния
Для произвольного объекта расположим объекты обучающей выборки в порядке возрастания расстояний до :
где через обозначается тот объект обучающей выборки, который является -м соседом объекта . Аналогичное обозначение введём и для ответа на -м соседе: .
Таким образом, произвольный объект порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть
где — заданная весовая функция, которая оценивает степень важности -го соседа для классификации объекта .
В рассматриваемом примере что соответствует методу экспоненциально взвешенных ближайших соседей, причем предполагается .
Алгоритм отыскания оптимальных параметров
Оптимальные значения параметров и определяют по критерию скользящего контроля с исключением объектов по одному: где
Вычислительный эксперимент
Показана работа алгоритма в серии задач, основанных как на реальных, так и на модельных данных.
Пример 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
В качестве второго примера возьмем четыре плохо разделимых класса. Классы обладают большой дисперсией. Можно наблюдать области, в которых элементы различны классов проникают в чужие классы.
%% Example 2 % Classes cross each other in this example. Algorithm makes misstakes in % classification. %% generate training sample % 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)]; %% generate control data with the same distribution X1 = GetNormClass(100,[5,0],[10,2]); X2 = GetNormClass(100,[5,10],[10,2]); X3 = GetNormClass(100,[0,5],[4,4]); X4 = GetNormClass(100,[10,5],[4,4]); X = [X1; X2; X3; X4]; % X is going to be changed in getting classification. X0 is needed to plot data. X0 = X; %% getting classification %% features standardization [p, m] = size(X); [n, m] = size(XL); Z = [XL; X]; Z =FeaturesStand(Z); XL = Z(1:n, :); X = Z(n+1:n+p, :); %% 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'); plot(X3(:,1),X3(:,2),'*g'); plot(X4(:,1),X4(:,2),'*y'); %% plotting classification results plot(X0(Y == 1,1),X0(Y == 1,2),'or'); plot(X0(Y == 2,1),X0(Y == 2,2),'ob'); plot(X0(Y == 3,1),X0(Y == 3,2),'og'); plot(X0(Y == 4,1),X0(Y == 4,2),'oy'); %% count errors 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 представителей каждого из типов ирисов.
%% Example 'iris' % Example with real data %% data preparation %% load data load 'iris.txt'; S = iris; %% eliminating first two attributes S(:,1:2) = []; %% divide data into training part and pert to classify XL = S([1:25,51:75,101:125],:); X = S([26:50,76:100,126:150],:); %% creating class labels YL = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; Y = [ones([25,1]);2*ones([25,1]);3*ones([25,1])]; %% plotting real classes of objects 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 %% features standardization [p, m] = size(X); [n, m] = size(XL); Z = [XL; X]; Z =FeaturesStand(Z); XL = Z(1:n, :); X = Z(n+1:n+p, :); %% choosing parametrs PP = ParAdjust(XL, YL); PP.XL = XL; PP.YL = YL; %% classification Y = WeightKNN(X, PP); %% 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)
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |