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

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

(Перенаправлено с Метод к ближайших соседей)
Перейти к: навигация, поиск

Содержание

Метод 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;

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

\rho(x,x') = \max_{i} |x_i-x'_i|;

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

\rho(x,x') = \sum_{i=1}^n |x_i-x'_i|.

Для произвольного объекта x\in X расположим объекты обучающей выборки 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] , что соответствует методу k ближайших соседей.

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

Оптимальные значения параметра K определяют по критерию скользящего контроля с исключением объектов по одному: (k^{*}) = \arg{ } \max_{k}\ LOO(k;X^\ell\), где LOO(k;X^\ell\)= \sum_{i=1}^l\[y_i = a(x_i;X^l \setminus x_i;k)].

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

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

Пример 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 в учебном процессе.

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