Профиль компактности

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

Версия от 21:25, 22 сентября 2008; Vokov (Обсуждение | вклад)

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

Содержание

1 Определения
2 Связь с полным скользящем контролем
3 См. также
4 Литература

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

Определения

Рассматривается задача классификации. Имеется множество объектов $X$ и множество имён классов $Y$ . Задана обучающая выборка пар «объект—ответ» $X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \in X\times Y$ .

Пусть на множестве объектов задана функция расстояния $\rho(x,x')$ . Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта $x,x'$ .

Для произвольного объекта $u$ расположим объекты обучающей выборки $x_i$ в порядке возрастания расстояний до $u$ :

$\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u}),$

где через $x_{i; u}$ обозначается $i$ -й сосед объекта $u$ . Аналогичное обозначение введём и для ответа на $i$ -м соседе: $y_{i; u}$ . Каждый объект $u\in X$ порождает свою перенумерацию выборки.

Рассматривается метод ближайшего соседа, который относит классифицируемый объект $u$ к тому классу $y_i$ , которому принадлежит ближайший объект обучающей выборки $x_i$ :

$a(u) = y_{1;u}.$

Определение. Профиль компактности выборки $X^m$ есть функция

$R(j,X^m) = \frac1m \sum_{i=1}^L \left[ y_i \neq y_{j;x_i} \right].$

Профиль компактности является формальным выражением гипотезы компактности — предположения о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных. Чем проще задача, то есть чем чаще близкие объекты оказываются в одном классе, тем сильнее «прижимается к нулю» начальный участок профиля. В сложных задачах или при неудачном выборе функции расстояния ближайшие объекты практически не несут информации о классах, и профиль вырождается в константу, близкую к $0{.}5$, см. Рис.

Связь с полным скользящем контролем

Теорема.

См. также

Литература

Воронцов К. В. [www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов] // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
Воронцов К. В., Колосков А. О. [www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf Профили компактности и выделение опорных объектов в метрических алгоритмах классификации] // Искусственный Интеллект. — 2006. — С. 30–33.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D1%84%D0%B8%D0%BB%D1%8C_%D0%BA%D0%BE%D0%BC%D0%BF%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8»

Категории: Метрические алгоритмы классификации | Теория вычислительного обучения