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

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

Перейти к: навигация, поиск

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

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

Содержание

Идея метода

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

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

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

Формулы

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

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})

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

<math>K(z)</math> — произвольная четная функция, называемая функцией ядра или окна. Термин окно происходит из классического вида функции:<math>K(z) = /frac{[|z| < 1]}{2}</math>

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

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

Ширина окна

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

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

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

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

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

Литература

  1. К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации, 2009
  2. К. В. Воронцов, Лекции по метрическим алгоритмам классификации, 2009
  3. Дьяконов А. Г., Учебные материалы для студентов кафедры ММП, 2009


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

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

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