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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Постановка задачи разделения классов методом парзеновского окна)
Строка 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> - множество\ref{Переписать.} объектов на этих ответах. Кроме того, задан объект <tex>x_0</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> - множество<ref>Переписать.</ref> объектов на этих ответах. Кроме того, задан объект <tex>x_0</tex>, который небоходимо классифицировать.
-
Задача состоит в том, что бы подобрать параметр <tex>h</tex> - ширину окна и тип ядра\ref{Ввести определение ядра и класс, из которого оно выбирается.} таким образом,что бы при классификации с помощью метода парзеновского окна \ref{Переписать.}ошибок было бы как можно меньше:
+
Задача состоит в том, что бы подобрать параметр <tex>h</tex> - ширину окна и тип ядра<ref>Ввести определение ядра и класс, из которого оно выбирается.</ref> таким образом,что бы при классификации с помощью метода парзеновского окна <ref>Переписать.</ref>ошибок было бы как можно меньше:
<center><tex>a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{p(x,x_i)}{h}\right).</tex></center>
<center><tex>a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{p(x,x_i)}{h}\right).</tex></center>
-
\ref{Описать все используемые переменные.}
+
<ref>Описать все используемые переменные.</ref>
== Алгоритм отыскания оптимальных параметров ==
== Алгоритм отыскания оптимальных параметров ==
Строка 86: Строка 86:
{{Задание|Зайцев Алексей|В.В. Стрижов|28 мая 2009}}
{{Задание|Зайцев Алексей|В.В. Стрижов|28 мая 2009}}
-
== Замечания ==
 
[[Категория:Классификация]]
[[Категория:Классификация]]
 +
== Замечания ==
 +
<references/>

Версия 09:55, 21 мая 2009

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

Содержание

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

Пусть у нас задана выборка \{(\mathbf{x}_i,y_i)\}_{i=1}^m, где X^m = \{\mathbf{x}_i\}_{i=1}^m - множество объектов, а Y^m = \{\mathbf{y}_i\}_{i=1}^m - множество[1] объектов на этих ответах. Кроме того, задан объект x_0, который небоходимо классифицировать. Задача состоит в том, что бы подобрать параметр h - ширину окна и тип ядра[1] таким образом,что бы при классификации с помощью метода парзеновского окна [1]ошибок было бы как можно меньше:

a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{p(x,x_i)}{h}\right).

[1]

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

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

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

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

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

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

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

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

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

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

%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=[0 4 2 60; 20 4 2 50]

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

Матрица параметров распределения:

V=[0 4 2 60; 5 4 2 50]

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

Матрица параметров распределения:

V=[0 4 2 60; 0 12 2 50]

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

Исходный код

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

Смотри также

Литература

  • К. В. Воронцов, Лекции по линейным алгоритмам классификации


Данная статья является непроверенным учебным заданием.
Студент: Участник:Зайцев Алексей
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2009

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

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Замечания

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