Метрические методы

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

Версия от 18:27, 19 июля 2026; Danial Zhumabekov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Д. Жумабеков 21:27, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Метод потенциальных функций
3 Восстановление плотности
4 Метод парзеновского окна для классификации
5 Метод ядерного сглаживания (Надарая — Ватсона) для регрессии
6 Выбор ядра и ширины окна
7 Метрическое обучение и отбор эталонов
8 Связь с алгоритмами вычисления оценок (АВО) и RBF
9 Проблематика метода
- 9.1 Проклятие размерности
- 9.2 Вычислительная сложность
10 Практическое применение: ирисы Фишера и метод парзеновского окна
11 Литература

Введение

В основании всего семейства метрических (непараметрических) методов лежит гипотеза компактности: предполагается, что объекты, близкие в некотором заданном на множестве $X$ смысле — то есть с малым значением функции расстояния $\rho(x, x')$ , — как правило, принадлежат одному классу, тогда как объекты разных классов разделены областями пространства с низкой плотностью объектов. В отличие от параметрических моделей, восстанавливающих зависимость $y(x)$ подбором конечного набора числовых параметров по всей обучающей выборке сразу, метрические методы формируют ответ для конкретного объекта $x$ локально — по сходству $x$ с ближайшими к нему объектами обучающей выборки $X^{\ell} = (x_i, y_i)_{i=1}^{\ell}$ , не строя при этом никакой явной глобальной модели зависимости.

Простейшая реализация этой идеи — метод ближайшего соседа (nearest neighbor): объекту $x$ приписывается метка класса того объекта обучающей выборки, который оказался ближайшим к нему по расстоянию $\rho$ :

$a(x) = y_{(1)}(x)$

где объекты выборки упорядочены по возрастанию расстояния до $x$ : $\rho(x, x_{(1)}) \leq \rho(x, x_{(2)}) \leq \dots \leq \rho(x, x_{(\ell)})$ , а $y_{(i)}(x)$ — метка класса $i$ -го соседа объекта $x$ в этом упорядочении^[1]. Ответ по единственному соседу неустойчив к шуму в разметке и выбросам, что мотивирует естественное обобщение — метод $k$ ближайших соседей ( $k$ NN), в котором ответ определяется голосованием по $k$ ближайшим соседям:

$a(x) = \arg\max_{y \in Y} \sum_{i=1}^{k} [y_{(i)}(x) = y]$

Увеличение $k$ сглаживает ответ алгоритма, снижая чувствительность к отдельным шумовым объектам ценой огрубления локальности оценки — простейшее проявление общего компромисса между смещением и разбросом, детально рассматриваемого ниже применительно к ширине окна.

Метод потенциальных функций

Обобщение голосования по $k$ ближайшим соседям на взвешенное голосование по всей выборке было предложено М. А. Айзерманом, Э. М. Браверманом и Л. И. Розоноэром по аналогии с представлением о поле точечных электрических зарядов в физике^[1]. Каждому объекту обучающей выборки $x_i$ сопоставляется потенциал — функция $\gamma_i\, K\big(\rho(x,x_i)/h_i\big)$ , убывающая с расстоянием от $x_i$ , где $\gamma_i > 0$ — вес («заряд») объекта $x_i$ , $h_i$ — радиус его действия, $K(r)$ — функция ядра (потенциальная функция), не возрастающая по $r \geq 0$ . Итоговая классификация нового объекта $x$ производится взвешенным голосованием по суммарному потенциалу, создаваемому объектами каждого класса в точке $x$ :

$a(x) = \arg\max_{y \in Y} \sum_{i:\, y_i = y} \gamma_i\, K\big(\rho(x,x_i)/h_i\big)$

Эта формула — частный случай общей схемы восстановления зависимости, основанной на взвешенном голосовании по функции сходства $f(x) = S(x, x_i)$ между объектами: здесь $S(x,x_i) = \gamma_i K(\rho(x,x_i)/h_i)$ . Веса $\gamma_i$ в исходном методе Айзермана — Бравермана — Розоноэра настраиваются итеративно, по правилу, аналогичному правилу коррекции ошибок в персептроне: если текущая композиция ошибается на объекте $x_i$ , его вес $\gamma_i$ увеличивается, что усиливает влияние проблемного объекта на последующие ответы алгоритма.

Восстановление плотности

Прежде чем перейти к методу парзеновского окна, рассмотрим более общую задачу непараметрического восстановления плотности распределения $p(x)$ по выборке $x_1, \dots, x_\ell$ , не привязанную к разметке классов. Оценка Парзена — Розенблатта восстанавливает плотность как сумму «размазанных» вкладов от каждого наблюдения:

$\widehat{p}(x) = \frac{1}{\ell h^n} \sum_{i=1}^{\ell} K\left( \frac{\rho(x, x_i)}{h} \right)$

где $n$ — размерность признакового пространства, $h > 0$ — ширина окна, $K(r)$ — функция ядра. К функции ядра предъявляются следующие требования: неотрицательность $K(r) \geq 0$ ; невозрастание на $[0, +\infty)$ (более далёкие точки вносят не больший вклад, чем близкие); убывание к нулю при $r \to \infty$ (или, для ядер с ограниченным носителем, обращение в нуль при $|r| > 1$ ); нормировка $\int K(\|u\|)\, du = 1$ , обеспечивающая, что $\widehat{p}(x)$ является корректной плотностью распределения. При $\ell \to \infty$ и согласованном стремлении $h \to 0$ (с определённой скоростью относительно $\ell$ ) оценка Парзена — Розенблатта состоятельно сходится к истинной плотности^[1].

Метод парзеновского окна для классификации

Применим оценку Парзена — Розенблатта раздельно к каждому классу, восстанавливая условную плотность $p(x \mid y)$ по подвыборке объектов класса $y$ объёма $\ell_y$ :

$\widehat{p}(x \mid y) = \frac{1}{\ell_y h^n} \sum_{i:\, y_i = y} K\left( \frac{\rho(x, x_i)}{h} \right)$

и подставим полученные оценки, вместе с эмпирической оценкой $\widehat{P}(y) = \ell_y/\ell$ , в правило классификации по максимуму апостериорной вероятности $a(x) = \arg\max_y \widehat{P}(y)\, \widehat{p}(x\mid y)$ . Множители $1/(\ell h^n)$ , общие для всех классов, не влияют на положение максимума и сокращаются, что даёт классификатор метода парзеновского окна:

$a(x) = \arg\max_{y \in Y} \sum_{i:\, y_i = y} K\left( \frac{\rho(x, x_i)}{h} \right)$

Сопоставление с формулой метода потенциальных функций показывает, что метод парзеновского окна — его частный случай при $\gamma_i \equiv 1$ (все объекты имеют равный, не настраиваемый по ошибкам вес) и $h_i \equiv h$ (единая ширина окна для всех объектов вместо индивидуального радиуса действия каждого объекта). Таким образом, метод $k$ ближайших соседей, метод потенциальных функций и метод парзеновского окна образуют последовательность всё более общих реализаций одной и той же схемы взвешенного голосования по сходству.

Метод ядерного сглаживания (Надарая — Ватсона) для регрессии

Для задачи регрессии ( $y_i \in \mathbb{R}$ ) та же идея локального взвешивания приводит к формуле Надарая — Ватсона^[1]^[1]. Рассмотрим локальную аппроксимацию зависимости константой $c$ в окрестности точки $x$ , взвешивая вклад каждого обучающего объекта его близостью к $x$ :

$c^*(x) = \arg\min_{c \in \mathbb{R}} \sum_{i=1}^{\ell} K\left( \frac{\rho(x,x_i)}{h} \right) (y_i - c)^2$

Приравнивая производную по $c$ к нулю, получаем оптимальный ответ как взвешенное среднее откликов соседних объектов:

$a(x) = \frac{\sum_{i=1}^{\ell} y_i\, K\left( \frac{\rho(x,x_i)}{h} \right)}{\sum_{i=1}^{\ell} K\left( \frac{\rho(x,x_i)}{h} \right)}$

Вывод в точности повторяет вывод оптимального ответа в листе дерева CART (минимизация квадратичной ошибки константой), с единственным отличием: вместо равномерного усреднения по объектам, попавшим в лист, здесь используется плавное, убывающее с расстоянием взвешивание всех объектов выборки. Это показывает, что метод парзеновского окна для классификации и метод Надарая — Ватсона для регрессии — два проявления единой схемы $f(x) = S(x,x_i)$ , различающиеся лишь типом решаемой задачи (голосование по дискретным меткам против взвешенного усреднения непрерывного отклика).

Выбор ядра и ширины окна

Каталог типовых ядер

Прямоугольное (равномерное): $K(r) = \frac{1}{2}\, [\, |r| \leq 1\,]$ — все объекты внутри окна учитываются с равным весом.
Треугольное: $K(r) = (1 - |r|)\, [\, |r| \leq 1\,]$ .
Ядро Епанечникова (квадратичное): $K(r) = \frac{3}{4}(1 - r^2)\, [\, |r| \leq 1\,]$ — минимизирует среднеквадратичную ошибку оценки плотности среди ядер с ограниченным носителем.
Квартическое (биквадратное): $K(r) = \frac{15}{16}(1 - r^2)^2\, [\, |r| \leq 1\,]$ — более гладкое, чем ядро Епанечникова, за счёт обнуления не только значения, но и производной на границе носителя.
Гауссовское: $K(r) = \exp(-r^2/2)$ — ядро с неограниченным носителем, придающее положительный, хотя и экспоненциально малый, вес сколь угодно удалённым объектам.

Фиксированная и адаптивная ширина окна

При фиксированной ширине $h$ радиус окна не зависит от точки $x$ и от локальной плотности объектов вокруг неё. Выбор $h$ определяет компромисс между смещением и разбросом оценки:

при малом $h$ окно охватывает малое число ближайших объектов; оценка становится высокочувствительной к конкретной реализации выборки (высокий разброс) и склонна к переобучению — классификатор точно подстраивается под шум в обучающих данных, образуя изрезанную, локально «прилипающую» к отдельным точкам разделяющую границу;
при большом $h$ в формирование ответа вовлекается много удалённых, зачастую принадлежащих другому классу объектов; оценка становится излишне сглаженной (высокое смещение) — разделяющая граница «размывается», теряя чувствительность к локальной структуре данных, вплоть до вырождения классификатора в константу при $h \to \infty$ .

Адаптивная (переменная) ширина окна устраняет часть этой проблемы, определяя радиус окна для каждой точки $x$ индивидуально — как расстояние до $k$ -го ближайшего соседа $x$ в обучающей выборке: $h(x) = \rho(x, x_{(k+1)})$ . В этом случае окно расширяется в разреженных областях пространства и сужается в плотных, что делает адаптивный метод парзеновского окна фактически параметризованным числом соседей $k$ вместо абсолютной ширины $h$ , — конструкция, промежуточная между методом $k$ NN и методом парзеновского окна с фиксированным $h$ .

Подбор ширины окна скользящим контролем

Оптимальное значение $h$ (или $k$ для адаптивного варианта) в подавляющем большинстве практических реализаций подбирается не аналитически, а по скользящему контролю по схеме leave-one-out: для сетки значений $h$ вычисляется функционал

$\mathrm{LOO}(h) = \sum_{i=1}^{\ell} \big[ a_h(x_i;\, X^{\ell} \setminus \{x_i\}) \neq y_i \big]$

то есть число ошибок классификатора при поочерёдном исключении каждого объекта $x_i$ из обучающей выборки и классификации его оставшимися $\ell - 1$ объектами, и выбирается $h^* = \arg\min_h \mathrm{LOO}(h)$ . Существенное вычислительное преимущество метода парзеновского окна при таком подборе состоит в том, что удаление одного объекта не требует полного переобучения модели — достаточно исключить его вклад из суммы взвешенного голосования, что делает полный перебор по сетке $h$ вычислительно приемлемым.

Метрическое обучение и отбор эталонов

Качество метрических методов напрямую определяется тем, насколько используемая функция расстояния $\rho(x,x')$ согласована с гипотезой компактности на конкретной задаче: если признаки измерены в несопоставимых шкалах или часть признаков нерелевантна целевой зависимости, стандартное евклидово расстояние может плохо отражать содержательное сходство объектов. Метрическое обучение (metric learning) выделяет настройку функции расстояния в отдельную задачу оптимизации — например, обучение параметрической метрики Махаланобиса

$\rho_A(x,x') = \sqrt{(x-x')^{T} A\, (x-x')}$

где симметричная положительно полуопределённая матрица $A$ подбирается минимизацией функционала, штрафующего большие расстояния между объектами одного класса и малые — между объектами разных классов, вместо того чтобы фиксировать $A$ равной единичной матрице (что соответствует обычному евклидову расстоянию) до начала обучения.

Отдельная практическая проблема метрических методов — вычислительная стоимость классификации, растущая с объёмом обучающей выборки (см. раздел «Проблематика метода»). Отбор эталонов (условно — сжатие выборки, prototype selection) частично решает эту проблему, выделяя из $X^{\ell}$ компактное подмножество эталонных объектов $X^{*} \subset X^{\ell}$ , $|X^{*}| \ll \ell$ , при классификации по которому качество существенно не уступает классификации по полной выборке. Типичная стратегия — итеративное удаление объектов, надёжно классифицируемых оставшимися эталонами (внутренних, «неинформативных» точек классов), и сохранение объектов, лежащих вблизи границы между классами, наиболее ценных для формирования разделяющей поверхности.

Связь с алгоритмами вычисления оценок (АВО) и RBF

Метрические методы — частный случай более общей схемы алгоритмов вычисления оценок (АВО), предложенной Ю. И. Журавлёвым^[1]: в общей схеме АВО ответ строится по системе опорных множеств признаков (не обязательно совпадающих с отдельными объектами), для каждого из которых вычисляется степень сходства с эталонными представителями класса, а итоговая оценка получается взвешенным суммированием этих сходств по всем опорным множествам и всем классам. Метрические методы, рассмотренные в этой статье, отвечают частному случаю АВО, в котором каждое опорное множество состоит из единственного объекта обучающей выборки, а функция сходства — это ядро от расстояния $K(\rho(x,x_i)/h)$ .

Формальное сходство связывает метрические методы также с сетью радиальных базисных функций (RBF-сетью) и с методом опорных векторов (SVM) с радиальным ядром. Скрытый слой RBF-сети вычисляет для каждого объекта набор активаций $\varphi_i(x) = K(\rho(x,c_i)/h_i)$ относительно набора центров $c_1, \dots, c_m$ , а выходной слой строит их линейную комбинацию $a(x) = \sum_i w_i \varphi_i(x)$ — формально та же схема взвешенного голосования по сходству, что и в методе потенциальных функций, где роль центров $c_i$ играют (все или часть) объекты обучающей выборки. Решающая функция SVM с радиальным ядром $K(x,x') = \exp(-\|x-x'\|^2 / 2h^2)$ имеет вид

$a(x) = \mathrm{sign}\Big( \sum_{i=1}^{\ell} \alpha_i\, y_i\, K(x,x_i) + b \Big)$

и отличается от классического метода потенциальных функций не структурой (обе формулы — взвешенная сумма ядерных функций расстояния до объектов выборки), а способом настройки весов $\alpha_i$ : в SVM веса находятся решением задачи выпуклой оптимизации, максимизирующей зазор между классами, а не итеративной коррекцией ошибок, при этом решение оказывается разреженным ( $\alpha_i \neq 0$ лишь для опорных объектов, лежащих вблизи разделяющей границы) — что можно рассматривать как разновидность отбора эталонов, встроенную непосредственно в процедуру обучения.

Проблематика метода

Проклятие размерности

Эффективность метрических методов существенно опирается на содержательность понятия «близости» в признаковом пространстве, что систематически нарушается с ростом размерности $n$ — явление, известное как Проклятие размерности. При росте $n$ объём $n$ -мерного шара радиуса $r$ , вписанного в единичный гиперкуб, стремительно убывает относительно объёма самого куба, из-за чего для покрытия фиксированной доли объектов выборки радиус окна $h$ должен расти со скоростью, приближающейся к масштабу всего пространства признаков, — окно перестаёт быть «локальным» в содержательном смысле. Одновременно попарные расстояния между случайными точками в пространствах высокой размерности статистически концентрируются вокруг общего среднего значения, так что относительная разница между расстоянием до ближайшего и до самого далёкого соседа стремится к нулю, что подрывает саму содержательность ранжирования объектов по близости, на которой основано взвешенное голосование.

Вычислительная сложность

Прямое вычисление ответа $a(x)$ по формуле взвешенного голосования требует вычисления расстояний от $x$ до всех $\ell$ объектов обучающей выборки, то есть $O(\ell n)$ операций на один классифицируемый объект, — при большом $\ell$ и необходимости классифицировать множество новых объектов эта стоимость становится доминирующей. Практические способы её снижения: построение пространственных индексных структур (KD-деревьев, шаровых деревьев), позволяющих находить точных или приближённых ближайших соседей быстрее полного перебора при умеренной размерности $n$ ; методы приближённого поиска ближайших соседей (в частности, основанные на локально-чувствительном хешировании), допускающие управляемую потерю точности ради существенного ускорения; и рассмотренный выше отбор эталонов, напрямую сокращающий число объектов, по которым производится голосование.

Практическое применение: ирисы Фишера и метод парзеновского окна

Рассмотрим классическую выборку ирисов Фишера — 150 объектов трёх видов (Iris setosa, Iris versicolor, Iris virginica) по 50 на класс, ограниченную двумя признаками: длиной лепестка $f_1$ и шириной лепестка $f_2$ ^[1]. В отличие от решающего дерева, дающего кусочно-постоянную разделяющую границу, выровненную по осям координат, метод парзеновского окна с гауссовским ядром строит плавную, непрерывно меняющуюся границу, форма которой определяется шириной окна $h$ .

Iris setosa практически линейно отделима от двух других видов уже при небольших значениях $f_1$ (длина лепестка ниже приблизительно 2 см), и её классификация методом парзеновского окна устойчива к выбору $h$ в широком диапазоне значений: плотная, обособленная группа объектов этого класса создаёт доминирующий потенциал независимо от умеренных изменений ширины окна. Содержательные различия проявляются в области перекрытия Iris versicolor и Iris virginica, где значения $f_1$ и $f_2$ у объектов разных классов частично совпадают:

при малой ширине окна ( $h$ , сопоставимой с типичным расстоянием до одного-двух ближайших соседей) классификатор образует в переходной зоне между versicolor и virginica изрезанную, локально огибающую отдельные точки границу — отдельные пограничные объекты противоположного класса создают локальные «карманы» неверной классификации в окрестности своего положения, типичный симптом переобучения при заниженной ширине окна;
при чрезмерно большой ширине окна голосование в переходной зоне начинает учитывать объекты, удалённые от классифицируемой точки на расстояние, сопоставимое с разбросом обоих классов; граница между versicolor и virginica становится гладкой почти прямой линией, но одновременно на неё начинает влиять и удалённая группа Iris setosa, что при достаточно большом $h$ способно сместить границу и ухудшить качество классификации даже в исходно хорошо разделимой области;
значение $h$ , минимизирующее ошибку скользящего контроля leave-one-out на этой выборке, оказывается промежуточным между двумя описанными крайностями: оно достаточно мало, чтобы не вовлекать в голосование объекты Iris setosa при классификации пограничных versicolor/virginica объектов, но достаточно велико, чтобы усреднить локальный шум разметки на границе этих двух классов.

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

Литература

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B»

Категории: Метрические методы | Энциклопедия анализа данных | Непараметрическая статистика | Методы классификации