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

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

(Различия между версиями)

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

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

Содержание

1 Постановка задачи разделения классов методом парзеновского окна
2 Алгоритм отыскания оптимальных параметров
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература
7 Замечания

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

Пусть у нас задана выборка $\{(\mathbf{x}_i,y_i)\}_{i=1}^m$ , где $X^m$ = $\{\mathbf{x}_i\}_{i=1}^m$ - множество объектов, а $Y^m$ = $\{\mathbf{y}_i\}_{i=1}^m$ - множество ответов на этих объектах. Кроме того, задан объект $x_0$ , который небоходимо классифицировать с помощью алгоритма $a(x;X^{l},h)$ . Тогда если задана парзеновская оценка плотности $\hat{p}_{y,h}=\frac{1}{l_y V(h)}\sum_{i=1}^l {[}y_i = y{]} K\left(\frac{\ro{}(x,x_i)}{h}\right),$ где $V(h)$ - некоторая функция от ширины окна, а $l_y$ - дополнительный параметр, зависящий от класса, то задача состоит в том, что бы подобрать параметр $h$ , ширину окна, и $K$ , ядерную функцию, таким образом, что бы при классификации с помощью метода парзеновского окна функционал качества достигал бы своего максимума при работе алгоритма с заданными параметрами: $a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{\ro{}(x,x_i)}{h}\right).$

В этой формуле $\lambda_{y}$ - цена правильного ответа для каждого класса из $Y$

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

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

$h^{*}=\arg{ } \max_{h} \sum_{i=1}^l \log \hat{p}_h (x_i;X^{m}{/}x_i).$

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

#	ядро $K(r)$	формула
1	Епанечникова	$K_1(r)=E(r)=\frac{3}{4}(1-r^2){[}{\|}r{\|}<=1{]}$
2	Квартическое	$K_2(r)=Q(r)=\frac{15}{16}(1-r^2)^2{[}{\|}r{\|}<=1{]}$
3	Треугольное	$K_3(r)=T(r)=(1-{\|}r{\|}){[}{\|}r{\|}<=1{]}$
4	Гауссовское	$K_4(r)=G(r)=(2\pi)^{(-\frac{1}{2})}exp(-\frac{1}{2}r^2)$
5	Прямоугольное	$K_5(r)=\Pi(r)=\frac{1}{2}{[}{\|}r{\|}<=1{]}$

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

$(h^{*},K^{*}_s(r))=\arg{ } \max_{\small s\in\{1,2,3,4,5\}} \max_{h\in\delta{}H} \sum_{i=1}^l \log \hat{p}_h (x_i;X^{m}{/}x_i).$

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

Вычислительный эксперимент был проведен на реальных и модельных данных. В качестве модельных данных были взяты точки из двух двумерных нормальных распределений с разными математическими ожиданиями и дисперсиями (соответственно, были получены два класса объектов). После запуска алгоритма порядка 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))];

Для каждой ядерной функции был проведен отдельный эксперимент, но из-за небольшого различия в результатах, мы их здесь не приводим. В каждом случае была использована своя матрица параметров двухмерного распределения $V=\{M_1,\sigma_1^2,m,n_1{;}M_2,\sigma_2^2,m,n_2\}$ , где $M_i$ - математическое ожидание для $i$ -го класса, $\sigma_i^2$ -дисперсия, $m=2$ - размерность пространства признаков, $n_i$ - количество элемнтов каждого класса

#	$\sigma_1^2$	$n_1$	$M_2$	$\sigma_2^2$	$n_2$
1	4	60	20	4	50
2	4	60	5	4	50
3	4	60	0	12	50

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

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

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

Исходный код

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

Смотри также

Литература

Воронцов К. В. Лекции по линейным алгоритмам классификации.
Christopher M. Bishop Pattern Recognition and Machine Learning. — Hardcover. — 2006. — 740 с.
Pascal Vincent, Yoshua Bengio Manifold Parzen Windows. — 2002.
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 в учебном процессе.

Замечания

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9F%D0%B0%D1%80%D0%B7%D0%B5%D0%BD%D0%BE%D0%B2%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%BE%D0%BA%D0%BD%D0%B0_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категории: Непроверенные учебные задания | Классификация

@@ Строка 1: / Строка 1: @@
 '''Метод Парзеновского окна''' принадлежит к непараметрическим методам классификации и представляет собой одну из возможных реализаций байесовского подхода к решению задачи классификации.
 == Постановка задачи разделения классов методом парзеновского окна ==
-Пусть у нас задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^m</tex>, где <tex>X^m</tex> = <tex>\{\mathbf{x}_i\}_{i=1}^m</tex> - множество объектов, а <tex>Y^m</tex> = <tex>\{\mathbf{y}_i\}_{i=1}^m</tex> - множество ответов на этих объектах. Кроме того, задан объект <tex>x_0</tex>, который небоходимо классифицировать с помощью алгоритма <tex>a(x;X^{l},h)</tex>.
+Пусть у нас задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^m</tex>, где <tex>X^m</tex> = <tex>\{\mathbf{x}_i\}_{i=1}^m</tex> - множество объектов, а <tex>Y^m</tex> = <tex>\{\mathbf{y}_i\}_{i=1}^m</tex> - множество ответов на этих объектах. Кроме того, задан объект <tex>x_0</tex>, который небоходимо классифицировать с помощью алгоритма <tex>a(x;X^{l},h)</tex>. Тогда если задана парзеновская оценка плотности <center><tex>\hat{p}_{y,h}=\frac{1}{l_y V(h)}\sum_{i=1}^l {[}y_i = y{]} K\left(\frac{\ro{}(x,x_i)}{h}\right),</tex></center> где <tex>V(h)</tex> - некоторая функция от ширины окна, а <tex>l_y</tex> - дополнительный параметр, зависящий от класса, то задача состоит в том, что бы подобрать параметр <tex>h</tex>, ширину окна, и <tex>K</tex>, ядерную функцию, таким образом, что бы при классификации с помощью метода парзеновского окна функционал качества достигал бы своего максимума при работе алгоритма с заданными параметрами:
-Задача состоит в том, что бы подобрать параметр <tex>h</tex>, ширину окна, и <tex>K</tex>ядерную функцию, таким образом, что бы при классификации с помощью метода парзеновского окна функционал качества достигал бы своего максимума при работе алгоритма с заданными параметрами:
 <center><tex>a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{\ro{}(x,x_i)}{h}\right).</tex></center>
 В этой формуле <tex>\lambda_{y}</tex> - цена правильного ответа для каждого класса из <tex>Y</tex>

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

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

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

Содержание

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

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

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

Исходный код

Смотри также

Литература

Замечания

Просмотры

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

Навигация

Поиск

Инструменты