Профиль компактности
Материал из MachineLearning.
|
Профиль компактности выборки в метрических алгоритмах классификации — функция , выражающая долю объектов выборки, для которых правильный ответ не совпадает с правильным ответом на
-м соседе.
Определения
Рассматривается задача классификации.
Имеется множество объектов и множество имён классов
.
Задана обучающая выборка пар «объект—ответ»
.
Пусть на множестве объектов задана функция расстояния .
Эта функция должна быть достаточно адекватной моделью сходства объектов.
Чем больше значение этой функции, тем менее схожими являются два объекта
.
Для произвольного объекта расположим
объекты обучающей выборки
в порядке возрастания расстояний до
:
где через обозначается элемент обучающей выборки, который является
-м соседом объекта
.
Аналогичное обозначение введём и для ответа на
-м соседе:
.
Каждый объект
порождает свою перенумерацию выборки.
Рассматривается метод ближайшего соседа, который относит классифицируемый объект к тому классу
, которому принадлежит ближайший объект обучающей выборки
:
Определение.
Профиль компактности выборки есть функция
Профиль компактности является формальным выражением гипотезы компактности — предположения о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных. Чем проще задача, то есть чем чаще близкие объекты оказываются в одном классе, тем сильнее «прижимается к нулю» начальный участок профиля. В сложных задачах или при неудачном выборе функции расстояния ближайшие объекты практически не несут информации о классах, и профиль вырождается в константу, близкую к 0.5.
На рисунке показаны профили компактности для серии плоских модельных задач классификации с двумя классами. Чем ниже проходит начальный участок профиля, тем выше обобщающая способность метода ближайшего соседа.
Связь с полным скользящем контролем
Выборка разбивается всевозможными
способами на две непересекающиеся подвыборки:
,
где
— обучающая подвыборка длины&nbps;m,
— контрольная подвыборка длины
,
— номер разбиения.
Для каждого разбиения n строится алгоритм .
Функционал полного скользящего контроля (complete cross-validation, CCV)
определяется как средняя (по всем разбиениям) ошибка на контроле:
Функционал полного скользящего контроля характеризует обобщающую способность метода ближайшего соседа
Теорема. Справедлива формула для эффективного вычисления CCV через профиль компактности:
где
Комбинаторный множитель быстро убывает с ростом
.
Поэтому для минимизации функционала CCV достаточно, чтобы при малых j профиль принимал значения, близкие к нулю.
Но это и означает, что близкие объекты должны лежать преимущественно в одном классе.
Таким образом, профиль действительно является формальным выражением гипотезы компактности.
См. также
Литература
- Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
- Воронцов К. В., Колосков А. О. Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30–33.
- Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. — 2000.