Воронцов К.В. Лекции по статистическим алгоритмам классификации

Подождите немного. Документ загружается.

– 21 –

1.4 Непараметрические методы классификации

Непараметрические методы классификации основаны на локальном оценива-

нии плотностей распределения p

(x) в окрестности классифицируемой точки x ∈ X.

Такой подход не требует знания функционального вида плотностей. Но априорная

информация всё равно привлекается — в виде метрики ρ(x, x

), оценивающей степень

сходства объектов в пространстве X.

1.4.1 Непараметрические оценки плотности распределения

Одномерная оценка плотности В одномерном случае X = R оценка плотно-

сти p(x) по случайной независимой выборке {x

, . . . , x

} даётся формулой Парзена-

Розенблатта (1956):

ˆp

(x) =

i=1

x − x

, (1.8)

где K(z) — функция ядра, h — ширина окна. Ядро обязано быть чётной функцией

и удовлетворять условию нормировки

K(z) dz = 1. В этом случае

ˆp

(x) dx = 1,

то есть ˆp

(x) действительно является плотностью вероятности.

Если взять прямоугольное ядро K(z) =

|z| < 1

, то выражение (1.8) определя-

ет отношение доли точек выборки, попавших внутрь окна, к ширине окна. Непрямо-

угольные ядра, убывающие с ростом |z|, придают точкам, далёким от x, меньший вес.

Следующая теорема показывает, что для широкого класса ядер оценка ˆp

(x) сходит-

ся к истинному значению плотности в точке x.

Утв. 1.1 Пусть функция K(z) непрерывна и ограничена,

(z) dz < ∞, после-

довательность h

такова, что h

→ 0 и nh

→ ∞ при n → ∞. Тогда ˆp

(x) → p(x)

для почти всех x ∈ X. Скорость сходимости имеет порядок O(n

−2/5

Многомерная оценка плотности Если в пространстве X задана метрика ρ(x, x

то оценка плотности легко обобщается на многомерный случай. Выпишем её для

каждого из классов y ∈ Y :

(x) =

C(h)

i=1

= y] K

ρ(x, x

)

, (1.9)

где нормировка на C(h) гарантирует, что p

(x) — действительно плотность:

C(h) =

ρ(x, x

)

dx.

Вычисление нормирующего множителя C(h) может оказаться сложной задачей при

некоторых ρ и K, но, к счастью, его можно избежать. В байесовском решающем пра-

виле множители C(h) сокращаются, если потребовать, чтобы C(h) не зависел от x

и от y. Первое требование означает, что форма окна не зависит от того, в какую точку

пространства его помещают. Второе требование означает, что для всех классов ис-

пользуется одна и та же ширина окна. При этом ширина окна вполне может зависеть

от самой точки x, что позволяет применять окна переменной ширины, о полезности

которых речь пойдёт ниже.

– 22 –

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

Подставляя непараметрическую оценку плотности (1.9) в байесовское решаю-

щее правило ( 1.3), получаем алгоритм классификации

a(x) = arg max

y∈Y

i=1

= y] K

ρ(x, x

)

Это очень простой алгоритм. В нём мало параметров, подлежащих обучению — если

метрика ρ фиксирована, то остаётся подобрать только ширину окна h и вид ядра K.

Выбор ширины окна Ширина окна решающим образом влияет на точность ап-

проксимации. Именно выбором ширины окна устанавливается компромисс между

точностью и гладкостью.

Внешний критерий качества аппроксимации.

Оценка hold-out. Недостатки: не ясно, из каких соображений выбирать разбие-

ние; оценка качества в окрестности нескольких конкретных о бъе ктов явно недоста-

точна в силу локальности сглаживания. Хотелось бы учесть поведение аппроксими-

рующей функции на более представительном множестве объектов.

Выбор ширины окна для задачи восстановления регрессии. Оценка скользящего

контроля leave-one-out.

Выбор ширины окна для задачи восстановления плотности. Оценка скользяще-

го контроля для функции правдоподобия.

Выбор функции ядра Функционал качества аппроксимации плотности распре-

деления. Сравнение качества ядер. Ядро Епанечникова. Квартическое ядро. Тре-

угольное ядро. Гауссовское ядро. Прямоугольное ядро.

Выводы: Форма ядра практически не влияет на точность аппроксимации.

Степень гладкости аппроксимирующей функции полностью определяется степенью

гладкости ядра. Ядра с ограниченным носителем позволяют более эффективно вы-

числять суммы.

Проблема локальных сгущений Сглаживание с переменной ш ириной окна. Ме-

тод k ближайших соседей (kNN). Выбор параметра k производится аналогично вы-

бору ширины окна.

Проблема больших выбросов Непараметрические оценки крайне чувствитель-

ны к большим одиночным выбросам. Выход — применение робастных непараметри-

ческих методов.

Простая и практичная эвристика: отсев точек, «перевешивающих» свою соб-

ственную окрестность.

1.4.3 Связь параметрических и непараметрических методов

Итак, байесовское решающее правило (1.3) является оптимальным классифика-

тором, но требует знания функций правдоподобия (плотностей распределения) клас-

сов. Мы рассмотрели три подхода к восстановлению плотности по выборке.

– 23 –

Первый подход предполагает, что плотности классов принадлежат заданному

параметрическому семейству распределений p(x; θ) и отличаются только вектором

параметров θ

, y ∈ Y :

(x) = p(x; θ

Второй подход является обобщением первого. Когда «форму» класса не удаёт-

ся описать одним параметрическим распределением, делается попытка описать его

смесью распределений:

(x) =

j=1

p(x; θ

j=1

= 1,

где k

— число компонент в смеси.

Третий подход основан на локальном оценивании плотностей классов в окрест-

ности классифицируемого объекта. Этот подход называют непараметрическим, так

как он не предполагает знания функционального вида плотнос тей. Однако более пра-

вомерно было бы называть его метрическим, поскольку он существенно опирается

на знание метрики ρ(x, x

) в пространстве объектов:

(x) =

i=1

= y] K

ρ(x, x

)

где C — нормировочный коэффициент, от которого решающее правило (1.3) не за-

висит, h — ширина окна.

Сопоставление двух последних формул показывает, что третий подход является

предельным частным случаем второго, когда для каждого обучающего объекта x

строится ровно одна компонента с априорной вероятностью w

= 1/`

и сферическим

распределением, центр которого помещается в точку x

. Различие между вторым

и третьим подходом скорее количественное, чем качественное: при восстановлении

смеси число компонент k

обычно берут много меньше числа объектов `