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

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

(Различия между версиями)
Перейти к: навигация, поиск

Vokov (Обсуждение | вклад)
(Новая: {{TOCright}} '''Профиль компактности''' выборки в метрических алгоритмах [[клас...)
К следующему изменению →

Версия 21:25, 22 сентября 2008

Содержание

Профиль компактности выборки в метрических алгоритмах классификации — функция 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$, см. Рис.

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

Теорема.


См. также

Литература

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