Метод Парзеновского окна (пример)
Материал из MachineLearning.
(→Постановка задачи разделения классов методом парзеновского окна) |
(→Исходный код) |
||
(17 промежуточных версий не показаны.) | |||
Строка 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>\{(\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>, ядерную функцию, таким образом, что бы при классификации с помощью метода парзеновского окна функционал качества достигал бы своего максимума при работе алгоритма с заданными параметрами: |
- | + | <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> | |
- | <center><tex>a(x;X^{l},h)=\arg \max_{y\in Y} \lambda_{y} \sum_{i=1}^l {[}y_i = y{]} K\left(\frac{ | + | В этой формуле <tex>\lambda_{y}</tex> - цена правильного ответа для каждого класса из <tex>Y</tex> |
- | \ | + | |
== Алгоритм отыскания оптимальных параметров == | == Алгоритм отыскания оптимальных параметров == | ||
- | + | Чтобы найти ширину окна и наиболее подходящий нам тип ядра, мы воспользуемся принципом максимального правдоподобия и исключением объектов по одному [[Скользящий контроль|leave-one-out]]: | |
- | <center><tex>h^{*}=\arg{ } \max_{h} \sum_{i=1}^l \log \hat{p}_h (x_i;X^{m}{/}x_i) </tex></center> | + | <center><tex>h^{*}=\arg{ } \max_{h} \sum_{i=1}^l \log \hat{p}_h (x_i;X^{m}{/}x_i). </tex></center> |
- | То есть, мы будем восстанавливать значение класса для одного объекта из нашей выборки и максимизировать логарифм количества правильных ответов при исключении по очереди всех объектов выборки. | + | То есть, мы будем восстанавливать значение класса для одного объекта из нашей выборки и максимизировать логарифм количества правильных ответов при исключении по очереди всех объектов выборки. Максимизация этого значения происходит по двум параметрам - ширине окна <tex>h</tex> и типу ядерной функции. Ширину окна мы можем подобрать из некоторого диапазона <tex>\delta{}H</tex>, полученного из эмпирических предположений. Ядро выбирается из нижеприведенного набора ядер: |
{| class="wikitable" style="text-align: center;" | {| class="wikitable" style="text-align: center;" | ||
|- bgcolor="#cccccc" | |- bgcolor="#cccccc" | ||
Строка 16: | Строка 16: | ||
! width=50 % |формула | ! width=50 % |формула | ||
|- | |- | ||
- | | '''1''' || Епанечникова || <tex>E(r)=\frac{3}{4}(1-r^2){[}{|}r{|}<=1{]}</tex> | + | | '''1''' || Епанечникова || <tex>K_1(r)=E(r)=\frac{3}{4}(1-r^2){[}{|}r{|}<=1{]}</tex> |
|- | |- | ||
- | | '''2''' || Квартическое || <tex>Q(r)=\frac{15}{16}(1-r^2)^2{[}{|}r{|}<=1{]}</tex> | + | | '''2''' || Квартическое || <tex>K_2(r)=Q(r)=\frac{15}{16}(1-r^2)^2{[}{|}r{|}<=1{]}</tex> |
|- | |- | ||
- | | '''3''' || Треугольное || <tex>T(r)=(1-{|}r{|}){[}{|}r{|}<=1{]}</tex> | + | | '''3''' || Треугольное || <tex>K_3(r)=T(r)=(1-{|}r{|}){[}{|}r{|}<=1{]}</tex> |
|- | |- | ||
- | | '''4''' || Гауссовское || <tex>G(r)=(2\pi)^{(-\frac{1}{2})}exp(-\frac{1}{2}r^2)</tex> | + | | '''4''' || Гауссовское || <tex>K_4(r)=G(r)=(2\pi)^{(-\frac{1}{2})}exp(-\frac{1}{2}r^2)</tex> |
|- | |- | ||
- | | '''5''' || Прямоугольное || <tex>\Pi(r)=\frac{1}{2}{[}{|}r{|}<=1{]}</tex> | + | | '''5''' || Прямоугольное || <tex>K_5(r)=\Pi(r)=\frac{1}{2}{[}{|}r{|}<=1{]}</tex> |
|- | |- | ||
|} | |} | ||
Получившееся выражение имеет достаточно понятный вид: | Получившееся выражение имеет достаточно понятный вид: | ||
- | <center><tex>(h^{*},K(r))=\arg{ } \max_{ | + | <center><tex>(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). </tex></center> |
== Вычислительный эксперимент == | == Вычислительный эксперимент == | ||
- | Вычислительный эксперимент был проведен на реальных и модельных данных. В качестве модельных данных были взяты точки из двух нормальных распределений с разными математическими ожиданиями и дисперсиями (соответственно, были получены два класса объектов). После | + | Вычислительный эксперимент был проведен на реальных и модельных данных. В качестве модельных данных были взяты точки из двух двумерных нормальных распределений с разными математическими ожиданиями и дисперсиями (соответственно, были получены два класса объектов). После запуска алгоритма порядка 30 раз были получены следующие результаты: |
Код получения данных: | Код получения данных: | ||
Строка 37: | Строка 37: | ||
<source lang="matlab"> | <source lang="matlab"> | ||
%NORMGENERATION generation of normal data in 2 classes with different | %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 | + | %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(2, 1) V(2, 2) parameters of normal |
- | %distribution for first class; V(1,3) - number of properties; V(1,4), | + | %distribution for first class; V(1, 3) - number of properties; V(1, 4), |
%V(2,4) - number of objects in first and second class | %V(2,4) - number of objects in first and second class | ||
- | + | firstClass = random('normal', V(1, 1), V(1, 2), V(1, 3), V(1, 4)); | |
- | + | secondClass = random('normal', V(2, 1), V(2, 2), V(1, 3), V(2, 4)); | |
- | + | variables = [firstClass , secondClass]; | |
- | + | responses = [ones(1, V(1, 4)), zeros(1, V(2, 4))]; | |
</source> | </source> | ||
- | В | + | Для каждой ядерной функции был проведен отдельный эксперимент, но из-за небольшого различия в результатах, мы их здесь не приводим. |
- | + | В каждом случае была использована своя матрица параметров двухмерного распределения <tex>V=\{M_1,\sigma_1^2,m,n_1{;}M_2,\sigma_2^2,m,n_2\}</tex>, где <tex>M_i</tex> - математическое ожидание для <tex>i</tex>-го класса, <tex>\sigma_i^2</tex> -дисперсия, <tex>m=2</tex> - размерность пространства признаков, <tex>n_i</tex> - количество элемнтов каждого класса | |
- | + | ||
- | + | {| class="wikitable" style="text-align: center;" | |
+ | |- bgcolor="#cccccc" | ||
+ | ! width=10 % |# | ||
+ | ! width=15 % | <tex>M_1</tex> | ||
+ | ! width=15 % | <tex>\sigma_1^2</tex> | ||
+ | ! width=15 % | <tex>n_1</tex> | ||
+ | ! width=15 % | <tex>M_2</tex> | ||
+ | ! width=15 % | <tex>\sigma_2^2</tex> | ||
+ | ! width=15 % | <tex>n_2</tex> | ||
+ | |||
+ | |- | ||
+ | | '''1''' || 0 || 4 || 60 || 20 || 4 || 50 | ||
+ | |- | ||
+ | | '''2''' || 0 || 4 || 60 || 5 || 4 || 50 | ||
+ | |- | ||
+ | | '''3''' || 0 || 4 || 60 || 0 || 12 || 50 | ||
+ | |- | ||
+ | |} | ||
Мы видим, что при хорошо разделимых классах, наш алгоритм работает замечательно при правильно подобранном значение <tex>k</tex> и любом ядре. | Мы видим, что при хорошо разделимых классах, наш алгоритм работает замечательно при правильно подобранном значение <tex>k</tex> и любом ядре. | ||
[[Изображение:Parzen1.jpg|300px]] | [[Изображение:Parzen1.jpg|300px]] | ||
- | |||
- | |||
- | |||
- | |||
- | |||
Во втором случае классы были сближены, что привело к некоторому неустранимому числу ошибок. | Во втором случае классы были сближены, что привело к некоторому неустранимому числу ошибок. | ||
[[Изображение:Parzen3.jpg|300px]] | [[Изображение:Parzen3.jpg|300px]] | ||
- | |||
- | |||
- | |||
- | |||
- | |||
В третьем случае были взяты два класса с одинаковыми математическими ожиданиями, но разными дисперсиями. Алгоритм достаточно хорошо разделил и их. | В третьем случае были взяты два класса с одинаковыми математическими ожиданиями, но разными дисперсиями. Алгоритм достаточно хорошо разделил и их. | ||
[[Изображение:Parzen4.jpg|300px]] | [[Изображение:Parzen4.jpg|300px]] | ||
+ | |||
+ | Кроме того, в каждом случае был проведен эксперимент для различных ядерных функций. Результаты - в таблице ниже: | ||
+ | {| class="wikitable" style="text-align: center;" | ||
+ | |- bgcolor="#cccccc" | ||
+ | ! width=10 % |# | ||
+ | ! width=30 % | ядро <tex>K(r)</tex> | ||
+ | ! width=20 % | Эксперимент 1 | ||
+ | ! width=20 % | Эксперимент 2 | ||
+ | ! width=20 % | Эксперимент 3 | ||
+ | |- | ||
+ | | '''1''' || Епанечникова || 0% || 13,64% || 20,91% | ||
+ | |- | ||
+ | | '''2''' || Квартическое || 0% || 13,64% || 20,00% | ||
+ | |- | ||
+ | | '''3''' || Треугольное || 0% || 13,64% || 20,00% | ||
+ | |- | ||
+ | | '''4''' || Гауссовское || 0% || 13,64% || 17,27% | ||
+ | |- | ||
+ | | '''5''' || Прямоугольное || 0% || 12,73% || 21,82% | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | На пересечении строки с названием ядра и столба с номером эксперимента - процент ошибок для соответствующей ядерной функций и эксперимента. Как видно из таблицы, результаты для разных ядерных функций отличаются незначительно. | ||
+ | |||
+ | ===Работа алгоритма на реальных данных=== | ||
+ | |||
+ | [[Изображение:Red_Wine.jpg|thumb]] | ||
+ | |||
+ | В качестве реальной задачи была выбрана [http://archive.ics.uci.edu/ml/datasets/Wine задача классификации происхождения вина] (3 класса) по трем признакам: общее содержание [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D0%B1%D0%BE%D0%BB%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BA%D0%B8%D1%81%D0%BB%D0%BE%D1%82%D0%B0 фенолов] (Total phenols), содержание [http://ru.wikipedia.org/wiki/%D0%A4%D0%BB%D0%B0%D0%B2%D0%BE%D0%BD%D0%BE%D0%B8%D0%B4%D1%8B флавоноидных] (Flavanoids) и нефлавоноидных (Nonflavanoid phenols) фенолов. Данные хорошо разделимы по этим трем признакам. | ||
+ | |||
+ | [[Изображение:Parzen5.jpg|300px]] | ||
+ | |||
+ | |||
+ | Мы видим, что наш алгоритм достаточно хорошо разделил объекты на три класса, сделав очень небольшое число ошибок. | ||
== Исходный код == | == Исходный код == | ||
- | Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/ | + | Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Zaitsev2009Parzen/ ] |
== Смотри также == | == Смотри также == | ||
Строка 81: | Строка 122: | ||
* [[Метод ближайших соседей]] | * [[Метод ближайших соседей]] | ||
* [[Многомерная случайная величина]] | * [[Многомерная случайная величина]] | ||
- | + | * [[Скользящий контроль]] | |
+ | * [[Однослойный персептрон (пример)| Однослойный персептрон]] | ||
+ | * [[EM алгоритм (пример)|EM алгоритм]] | ||
+ | * [[EM-алгоритм с последовательным добавлением компонент (пример)| EM-алгоритм с последовательным добавлением компонент]] | ||
== Литература == | == Литература == | ||
- | + | # {{книга | |
+ | |автор = Воронцов К. В. | ||
+ | |заглавие = Лекции по линейным алгоритмам классификации | ||
+ | }} | ||
+ | # {{книга | ||
+ | |автор = Christopher M. Bishop | ||
+ | |заглавие = Pattern Recognition and Machine Learning | ||
+ | |издание = Hardcover | ||
+ | |год = 2006 | ||
+ | |страниц = 740 | ||
+ | }} | ||
+ | # {{книга | ||
+ | |автор = Pascal Vincent, Yoshua Bengio | ||
+ | |ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.8792 | ||
+ | |заглавие = Manifold Parzen Windows | ||
+ | |год = 2002 | ||
+ | }} | ||
+ | # {{книга | ||
+ | |автор = Erik Mcdermott, Shigeru Katagiri | ||
+ | |ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.8450 | ||
+ | |заглавие = A Parzen Window Based Derivation Of Minimum Classification Error From The Theoretical Bayes Classification Risk | ||
+ | |год = 2002 | ||
+ | }} | ||
+ | |||
+ | {{ЗаданиеВыполнено|Зайцев Алексей|В.В. Стрижов|28 мая 2009|Likz|Strijov|}} | ||
- | + | [[Категория:Байесовская теория классификации]] | |
- | + | [[Категория:Метрические алгоритмы классификации]] | |
- | [[Категория: | + | [[Категория:Практика и вычислительные эксперименты]] |
Текущая версия
Метод Парзеновского окна принадлежит к непараметрическим методам классификации и представляет собой одну из возможных реализаций байесовского подхода к решению задачи классификации. Он естественным образом возникает при предположении о байесовости вероятностных распределений объектов. В методе производится классификация объекта по находящимся на некотором расстоянии от него объектах с весом, зависящим от расстояния. Алгоритм имеет ряд параметров, которые будут более детально рассмотрены в последующих разделах.
Содержание |
Постановка задачи разделения классов методом парзеновского окна
Пусть у нас задана выборка , где = - множество объектов, а = - множество ответов на этих объектах. Кроме того, задан объект , который небоходимо классифицировать с помощью алгоритма . Тогда если задана парзеновская оценка плотностиВ этой формуле - цена правильного ответа для каждого класса из
Алгоритм отыскания оптимальных параметров
Чтобы найти ширину окна и наиболее подходящий нам тип ядра, мы воспользуемся принципом максимального правдоподобия и исключением объектов по одному 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 firstClass = random('normal', V(1, 1), V(1, 2), V(1, 3), V(1, 4)); secondClass = random('normal', V(2, 1), V(2, 2), V(1, 3), V(2, 4)); variables = [firstClass , secondClass]; responses = [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 |
Мы видим, что при хорошо разделимых классах, наш алгоритм работает замечательно при правильно подобранном значение и любом ядре.
Во втором случае классы были сближены, что привело к некоторому неустранимому числу ошибок.
В третьем случае были взяты два класса с одинаковыми математическими ожиданиями, но разными дисперсиями. Алгоритм достаточно хорошо разделил и их.
Кроме того, в каждом случае был проведен эксперимент для различных ядерных функций. Результаты - в таблице ниже:
# | ядро | Эксперимент 1 | Эксперимент 2 | Эксперимент 3 |
---|---|---|---|---|
1 | Епанечникова | 0% | 13,64% | 20,91% |
2 | Квартическое | 0% | 13,64% | 20,00% |
3 | Треугольное | 0% | 13,64% | 20,00% |
4 | Гауссовское | 0% | 13,64% | 17,27% |
5 | Прямоугольное | 0% | 12,73% | 21,82% |
На пересечении строки с названием ядра и столба с номером эксперимента - процент ошибок для соответствующей ядерной функций и эксперимента. Как видно из таблицы, результаты для разных ядерных функций отличаются незначительно.
Работа алгоритма на реальных данных
В качестве реальной задачи была выбрана задача классификации происхождения вина (3 класса) по трем признакам: общее содержание фенолов (Total phenols), содержание флавоноидных (Flavanoids) и нефлавоноидных (Nonflavanoid phenols) фенолов. Данные хорошо разделимы по этим трем признакам.
Мы видим, что наш алгоритм достаточно хорошо разделил объекты на три класса, сделав очень небольшое число ошибок.
Исходный код
Скачать листинги алгоритмов можно здесь [1]
Смотри также
- Метод ближайших соседей
- Многомерная случайная величина
- Скользящий контроль
- Однослойный персептрон
- EM алгоритм
- EM-алгоритм с последовательным добавлением компонент
Литература
- Воронцов К. В. Лекции по линейным алгоритмам классификации.
- 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.
Данная статья была создана в рамках учебного задания.
См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |