Метод парзеновского окна

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

(Различия между версиями)
Перейти к: навигация, поиск
(Функция ядра (окна))
 
(6 промежуточных версий не показаны.)
Строка 4: Строка 4:
== Идея метода ==
== Идея метода ==
-
В основе подхода лежит идея о том, что плотность выше в тех точках, рядом с которыми находится большое колличество объектов выборки.
+
В основе подхода лежит идея о том, что плотность выше в тех точках, рядом с которыми находится большое количество объектов выборки.
Если мощность множества элементарных исходов много меньше размера выборки, то в качестве восстановленной по выборке плотности мы вполне можем взять и гистограмму значений выборки.
Если мощность множества элементарных исходов много меньше размера выборки, то в качестве восстановленной по выборке плотности мы вполне можем взять и гистограмму значений выборки.
Строка 18: Строка 18:
== Функция ядра (окна) ==
== Функция ядра (окна) ==
-
<math>K(z)</math> — произвольная четная функция, называемая функцией ядра или окна. Термин окно происходит из классического вида функции:<math>K(z) = /frac{[|z| < 1]}{2}</math>
+
<tex>K(z)</tex> — произвольная четная функция, называемая функцией ядра или окна. Термин окно происходит из классического вида функции:
 +
::<tex>K(z) = \frac12 [|z| < 1]</tex>
Восстановленная плотность имеет такую же степень гладкости, как и функция ядра. Поэтому на практике обычно используются все же более гладкие функции.
Восстановленная плотность имеет такую же степень гладкости, как и функция ядра. Поэтому на практике обычно используются все же более гладкие функции.
Строка 30: Строка 31:
== Возможные проблемы ==
== Возможные проблемы ==
-
'''Проблема локальных сгущений''' возникает в тех случаях, когда распределение объектов в пространстве сильно неравномерно, и одно и то же значение ширины окна h приводит к чрезмерному сглаживанию плотности в одних местах, и недостаточному сглаживанию в других. Проблему решают окна переменной ширины.
 
-
'''Проблема «проклятия размерности»''' — если число признаков велико и учитываются все они, то все объекты оказываются примерно на одинаковом расстоянии друг от друга. Выход заключается в понижении размерности с помощью преобразования пространства признаков, либо путём отбора информативных признаков.
+
===Проблема локальных сгущений===
 +
Возникает в тех случаях, когда распределение объектов в пространстве сильно неравномерно, и одно и то же значение ширины окна h приводит к чрезмерному сглаживанию плотности в одних местах, и недостаточному сглаживанию в других. Проблему решают окна переменной ширины.
 +
 
 +
===Проблема «проклятия размерности»===
 +
{{main|Проклятие размерности}}
 +
Если число признаков велико и учитываются все они, то все объекты оказываются примерно на одинаковом расстоянии друг от друга. Выход заключается в понижении размерности с помощью преобразования пространства признаков, либо путём отбора информативных признаков.
 +
 
 +
== См. также ==
 +
* [[Метод Парзеновского окна (пример)]]
== Литература ==
== Литература ==
-
# К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по статистическим (байесовским) алгоритмам классификации]], 2009
+
* К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по статистическим (байесовским) алгоритмам классификации]], 2009
-
# К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по метрическим алгоритмам классификации]], 2009
+
* К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по метрическим алгоритмам классификации]], 2009
-
# Дьяконов А. Г., [http://mmp1.nm.ru/prack.htm Учебные материалы для студентов кафедры ММП], 2009
+
* Дьяконов А. Г., [http://mmp1.nm.ru/prack.htm Учебные материалы для студентов кафедры ММП], 2009
 +
[[Категория:Байесовская теория классификации]]
 +
[[Категория:Метрические алгоритмы классификации]]
{{Задание|Amolchanov|Константин Воронцов|8 января 2010}}
{{Задание|Amolchanov|Константин Воронцов|8 января 2010}}

Текущая версия

Метод парзеновского окна — метод байесовской классификации, основанный на непараметрическом восстановлении плотности по имеющейся выборке.

После ввода метрики, метод парзеновского окна можно использовать, не опираясь на вероятностную природу данных.

Содержание

Идея метода

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

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

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

Формулы

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

p_{y,h}(x) = \frac{1}{l_y V(h)} \sum_{i=1}^l [y_i = y] K(\frac{\rho(x, x_i)}{h})

Соответствующее решающее правило, полученное после преобразований:

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

Функция ядра (окна)

K(z) — произвольная четная функция, называемая функцией ядра или окна. Термин окно происходит из классического вида функции:

K(z) = \frac12 [|z| < 1]

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

Вид функции окна не влияет на качество классификации определяющим образом.

Ширина окна

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

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

Возможные проблемы

Проблема локальных сгущений

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

Проблема «проклятия размерности»

Основная статья: Проклятие размерности

Если число признаков велико и учитываются все они, то все объекты оказываются примерно на одинаковом расстоянии друг от друга. Выход заключается в понижении размерности с помощью преобразования пространства признаков, либо путём отбора информативных признаков.

См. также

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Amolchanov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

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

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


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