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

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

Версия 10:31, 29 мая 2010

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

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

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

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

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

На множестве объектов задается некоторая функция расстояния, задаваемая пользовательской функцией Рассматривались следующие функции (ядра): евклидова

максимум модулей

сумма модулей

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

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

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

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

В рассматриваемом примере что соответствует методу ближайших соседей.

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

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

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

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

Пример 1

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

function demo_KMeans()
%% Set parameters 
%generating 3 sample normal classes
N = 100; 
% 1st class contains N objects
alpha = 1.5; % 2nd class contains alpha*N ones
sig2 = 1; % assume 2nd class has the same variance as the 1st
dist2 = 4; % distance from the 1st class
 
% parameters for the 3rd class
beta = 1.3;
sig3 = 1.5;
dist3 = 3;
%
% % later we move this piece of code in a separate file
% X - coordinates of educational sequence
% y - classes of elements in educatioanal sequence
[X, y] = loadModelData3(N, alpha, sig2, dist2, beta, sig3, dist3);
 
%% Section title 
%
% idx* - indexes of class * in X
idx1 = find(y == 0); % object indices for the 1st class
idx2 = find(y == 1);
idx3 = find(y == 2);
 
minErrors=0;
%% Main calculations
funcNorm = 'normEuc';
CalcAndPlot('normEuc', X, y, idx1,idx2,idx3)
 
funcNorm = 'normMax';
CalcAndPlot('normMax', X, y, idx1,idx2,idx3)
 
funcNorm = 'normAbs';
CalcAndPlot('normAbs', X, y, idx1,idx2,idx3)
 
end
 
function CalcAndPlot(funcNorm, X, y, idx1,idx2,idx3)
% RR - indexes of ordered educ. seq.
RR=GetBigIndices4(X, funcNorm);
% Kopt - optimal parameter for method
[Kopt,minErrors] = GetK3(RR,y) 
% draw results:
 
PlotClassification4(X,y,Kopt,idx1,idx2,idx3, funcNorm,minErrors)
end

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

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

Проведем проверку алгоритма на классической задаче: Ирисы Фишера Объектами являются три типа ирисов: setosa, versicolor, virginica

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

function xxx = PlotIris()
load 'iris.txt'
X = iris;
y=[zeros(50,1);ones(50,1);2*ones(50,1)];
idx1 = find(y == 0); % object indices for the 1st class
idx2 = find(y == 1);
idx3 = find(y == 2);
CalcAndPlot('normEuc', X, y, idx1,idx2,idx3)
 
CalcAndPlot('normMax', X, y, idx1,idx2,idx3)
 
CalcAndPlot('normAbs', X, y, idx1,idx2,idx3)
 
end
 
function CalcAndPlot(funcNorm, X, y, idx1,idx2,idx3)
% RR - indexes of ordered educ. seq.
RR=GetBigIndices4(X, funcNorm);
% Kopt - optimal parameter for method
[Kopt,minErrors] = GetK3(RR,y) 
% draw results:
 
PlotClassification4(X,y,Kopt,idx1,idx2,idx3, funcNorm,minErrors)
end

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

Исходный код

Скачать листинги алгоритмов можно здесь [1].

Смотри также

• Метрический классификатор
• Метод ближайших соседей
• Скользящий контроль

Литература

• К. В. Воронцов, Лекции по метрическим алгоритмам классификации
• Bishop C. - Pattern Recognition and Machine Learning. Springer. 2006.
• Abidin, T. and Perrizo, W. SMART-TV: A Fast and Scalable Nearest Neighbor Based Classifier for Data Mining. Proceedings of ACM SAC-06, Dijon, France, April 23-27, 2006. ACM Press, New York, NY, pp.536-540
• Wang, H. and Bell, D. Extended k-Nearest Neighbours Based on Evidence Theory. The Computer Journal, Vol. 47 (6) Nov. 2004, pp. 662-672.
• Yu, K. and Ji, L. Karyotyping of Comparative Genomic Hybridization Human Metaphases Using Kernel Nearest-Neighbor Algorithm, Cytometry 2002.
• Domeniconi, C., and Yan, B. On Error Correlation and Accuracy of Nearest Neighbor Ensemble Classifiers. Proceedings of the SIAM International Conference on Data Mining, Newport Beach, California, April 21-23, 2005
• UCI Machine Learning Repository, available on line at the University of California,Irvine http://www.ics.uci.edu/~mlearn/MLSum mary.html

Данная статья была создана в рамках учебного задания. Студент: Участник:Литвинов Игорь Преподаватель: Участник:В.В. Стрижов Срок: 16 июня 2009 В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.