Метод Парзеновского окна (пример)

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

Версия 12:14, 24 мая 2009

Метод Парзеновского окна принадлежит к непараметрическим методам классификации и представляет собой одну из возможных реализаций байесовского подхода к решению задачи классификации.

Постановка задачи разделения классов методом парзеновского окна

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

В этой формуле - цена правильного ответа для каждого класса из

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

Чтобы найти ширину окна и наиболее подходящий нам тип ядра, мы воспользуемся принципом максимального правдоподобия и исключением объектов по одному leave-one-out:

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

#	ядро	формула
1	Епанечникова
2	Квартическое
3	Треугольное
4	Гауссовское
5	Прямоугольное

Получившееся выражение имеет достаточно понятный вид:

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

Вычислительный эксперимент был проведен на реальных и модельных данных. В качестве модельных данных были взяты точки из двух двумерных нормальных распределений с разными математическими ожиданиями и дисперсиями (соответственно, были получены два класса объектов). После запуска алгоритма порядка 30 раз были получены следующие результаты:

Код получения данных:

%NORMGENERATION generation of normal data in 2 classes with different
%parameteres to be described in V: V(1,1) V(1,2) parameters of normal
%distribution for first class; V(2,1) V(2,2) parameters of normal
%distribution for first class; V(1,3) - number of properties; V(1,4),
%V(2,4) - number of objects in first and second class
X1=random('normal',V(1,1),V(1,2),V(1,3),V(1,4));
X2=random('normal',V(2,1),V(2,2),V(1,3),V(2,4));
X=[X1 , X2];
Y=[ones(1,V(1,4)) , zeros(1,V(2,4))];

Для каждой ядерной функции был проведен отдельный эксперимент, но из-за небольшого различия в результатах, мы их здесь не приводим. В каждом случае была использована своя матрица параметров двухмерного распределения , где - математическое ожидание для -го класса, -дисперсия, - размерность пространства признаков, - количество элемнтов каждого класса

#
1	0	4	60	20	4	50
2	0	4	60	5	4	50
3	0	4	60	0	12	50

Мы видим, что при хорошо разделимых классах, наш алгоритм работает замечательно при правильно подобранном значение и любом ядре.

Во втором случае классы были сближены, что привело к некоторому неустранимому числу ошибок.

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

Исходный код

Скачать листинги алгоритмов можно здесь parzenclassification.m, crossvalidation.m, fqual.m, kgenerate.m

Смотри также

• Метод ближайших соседей
• Многомерная случайная величина
• Скользящий контроль
• Однослойный персептрон
• EM алгоритм
• EM-алгоритм с последовательным добавлением компонент

Литература

1. Воронцов К. В. Лекции по линейным алгоритмам классификации.
2. Christopher M. Bishop Pattern Recognition and Machine Learning. — Hardcover. — 2006. — 740 с.
3. Pascal Vincent, Yoshua Bengio Manifold Parzen Windows. — 2002.
4. Erik Mcdermott, Shigeru Katagiri A Parzen Window Based Derivation Of Minimum Classification Error From The Theoretical Bayes Classification Risk. — 2002.

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

Замечания