Метод Парзеновского окна (пример)
Материал из 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> - множество объектов на этих ответах. Кроме того, задан объект <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{Переписать.} объектов на этих ответах. Кроме того, задан объект <tex>x_0</tex>, который небоходимо классифицировать. |
| - | Задача состоит в том, что бы подобрать параметр <tex>h</tex> - ширину окна и тип ядра таким образом,что бы при классификации с помощью метода парзеновского окна ошибок было бы как можно меньше: | + | Задача состоит в том, что бы подобрать параметр <tex>h</tex> - ширину окна и тип ядра\ref{Ввести определение ядра и класс, из которого оно выбирается.} таким образом,что бы при классификации с помощью метода парзеновского окна \ref{Переписать.}ошибок было бы как можно меньше: |
| - | <center><tex>a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K(\frac{p(x,x_i)}{h})</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{Описать все используемые переменные.} | |
== Алгоритм отыскания оптимальных параметров == | == Алгоритм отыскания оптимальных параметров == | ||
Версия 07:04, 21 мая 2009
Метод Парзеновского окна принадлежит к непараметрическим методам классификации и представляет собой одну из возможных реализаций байесовского подхода к решению задачи классификации.
Содержание |
Постановка задачи разделения классов методом парзеновского окна
Пусть у нас задана выборка , где
=
- множество объектов, а
=
- множество\ref{Переписать.} объектов на этих ответах. Кроме того, задан объект
, который небоходимо классифицировать.
Задача состоит в том, что бы подобрать параметр
- ширину окна и тип ядра\ref{Ввести определение ядра и класс, из которого оно выбирается.} таким образом,что бы при классификации с помощью метода парзеновского окна \ref{Переписать.}ошибок было бы как можно меньше:
\ref{Описать все используемые переменные.}
Алгоритм отыскания оптимальных параметров
Для того, чтобы найти ширину окна и наиболее подходящий нам тип ядра, мы воспользуемся принципом максимального правдоподобия и исключением объектов по одному (leave-one-out,LOO):
То есть, мы будем восстанавливать значение класса для одного объекта из нашей выборки и максимизировать логарифм количества правильных ответов при исключении по очереди всех объектов выборки. Мы можем максимизоровать это значение по двум параметрам - ширине окна и типу ядра. Ширину окна мы можем подобрать из некоторого диапазона, полученного из эмпирических предположений. Ядро можно выбрать из набора общеизвестных ядер. В моей работе рассматривались несколько основных типов ядер:
| # | ядро | формула |
|---|---|---|
| 1 | Епанечникова | |
| 2 | Квартическое | |
| 3 | Треугольное | |
| 4 | Гауссовское | |
| 5 | Прямоугольное | |
Получившееся выражение имеет достаточно понятный вид:
Вычислительный эксперимент
Вычислительный эксперимент был проведен на реальных и модельных данных. В качестве модельных данных были взяты точки из двух нормальных распределений с разными математическими ожиданиями и дисперсиями (соответственно, были получены два класса объектов). После проведения рядка экспериментов были получены следующие результаты:
Код получения данных:
%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]
Мы видим, что при хорошо разделимых классах, наш алгоритм работает замечательно при правильно подобранном значение и любом ядре.
Матрица параметров распределения:
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
Смотри также
Литература
- К. В. Воронцов, Лекции по линейным алгоритмам классификации
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
