* <b>Постоянное значение h</b>, примеры стратегий:
* <b>Постоянное значение h</b>, примеры стратегий:
** <math>h=\tfrac{1}{N}\cdot\sum_{i=1}^{N}d_{iK}, d_{iK}</math> — расстояние от <math>x_i</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно вычислять по скользящему контролю).
** <math>h=\tfrac{1}{N}\cdot\sum_{i=1}^{N}d_{iK}, d_{iK}</math> — расстояние от <math>x_i</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно вычислять по скользящему контролю).
−
** <math>h</math> вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений <nowiki><math>h</math></nowiki>).
+
** <math>h</math> вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений <math>h</math>).
* <b>Переменное значение <math>h(x)</math></b>, например: <math>h(x)</math> — расстояние от <math>x</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно найти по скользящему контролю).
* <b>Переменное значение <math>h(x)</math></b>, например: <math>h(x)</math> — расстояние от <math>x</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно найти по скользящему контролю).
Проблема: нужен непараметрический метод для оценки плотности.
Решение: метод будет основан на локальной оценке плотности в окрестности интересующей точки по известной выборке. Локальная оценка опирается на само определение плотности распределения: , где — вероятностная мера отрезка .
Так и родился на свет один из непараметрических способов оценки плотности распределения — ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю.
Общая формула KDE (для одномерного и многомерного случая) представлена ниже.
Два важных параметра метода: ядро и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к кросс-валидации, различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно.
Итак...
Условные обозначения
— количество объектов в выборке.
— размер признакового пространства, .
— количество классов.
— выборка, , . .
— ширина окна (bandwidth), .
— оценка плотности распределения .
условие — равняется 1, если условие выполнено, иначе равняется 0.
— оценка зависимости .
Гистограммы
Недостаток: необходимо фиксировать отрезки, на которые разбивается интервал. Проблема: выбор количества корзинок и ширины корзинок.
Ядерное сглаживание
Идея: каждый выборки будет центром блока.
Блок может иметь следующий вид: .
Одномерный случай
Kernel Density Estimation (KDE, локальная непараметрическая оценка Парзена-Розенблатта) — , — ядро, чётная и нормированная функция: . Следствие: обладает той же степенью гладкости, что и ядро .
Виды ядер
Прямоугольное ядро (tophat kernel): соответствует эмпирической оценке плотности (доля точек выборки, лежащих внутри отрезка ). Одно из простейших ядер, но не учитывает расстояние между объектами, а также итоговое распределение не будет являться непрерывным.
Гауссово ядро:
Ядро Епанечникова:
Треугольное ядро:
Косинусное ядро:
Экспоненциальное ядро:
Квартическое ядро:
Состоятельность оценки
Оценка состоятельна, если .
Достаточные условия состоятельности оценки :
,
, , ,
Многомерный случай
Виды ядер
Гауссово ядро:
Ядро Епанечникова:
Произведение одномерных ядер:
Зависящие от метрики ядра
Гауссово ядро:
Ядро Епанечникова:
Выбор ширины окна (bandwidth)
При плотность концентрируется вблизи точек выборки, претерпевает резкие скачки. При более гладкая плотность, происходит вырождение в константу. При построении KDE ширина окна важнее, чем функция ядра , так как тип ядра влияет на гладкость, а не на точность аппроксимации.
Стратегия выбора: чем более плотное распределение объектов выборки, тем меньше должно быть
Постоянное значение h, примеры стратегий:
— расстояние от до -го ближайшего соседа ( можно вычислять по скользящему контролю).
вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений ).
Переменное значение , например: — расстояние от до -го ближайшего соседа ( можно найти по скользящему контролю).
Метод Парзеновского окна
Метод Парзеновского окна — метод байесовской классификации, основанный на непараметрическом восстановлении плотности по имеющейся выборке.
Оценка условной плотности через KDE ():
— число объектов класса — метрика.
Байесовское решающее правило даёт следующий классификатор:
Оценим с помощью KDE, как :
Преобразование метода Парзеновского окна в метод ближайших соседей
Обозначим — индекс -го ближайшего соседа для , . Тогда: