Гипотеза компактности

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Гипотеза компактности''' — в задачах классификации предположение о том, что схожие объекты гораздо ...)
м (добавила Бравермана в литературу)
Строка 22: Строка 22:
{{stub}}
{{stub}}
[[Категория:Метрические алгоритмы классификации]]
[[Категория:Метрические алгоритмы классификации]]
 +
 +
== Литература ==
 +
# ''Аркадьев А. Г., Браверман Э. М. '' Обучение машины распознаванию образов. — М.: Наука, 1964.

Версия 18:48, 7 октября 2010

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

В математическом анализе компактными называются ограниченные замкнутые множества. Гипотеза компактности не имеет ничего общего с этим понятием и должна пониматься в «более бытовом» смысле этого слова.

Для формализации понятия «сходства» вводится функция расстояния или метрика \rho(x,x') в пространстве объектов X. Алгоритмы, основанные на анализе сходства объектов, часто называют метрическими, даже в тех случаях, когда функция \rho не удовлетворяет всем аксиомам метрики; в частности, далеко не всегда выполняется аксиома треугольника.

В задачах классификации введение метрики позволяет применять широкий класс метрических алгоритмов классификации. Наиболее простые из них:

Эти методы основаны на предположении, что эксперт уже построил достаточно адекватную метрику, для которой действительно выполняется гипотеза компактности. Однако выбор адекватной метрики является наиболее сложной и наименее исследованной подзадачей. В более «продвинутых» методах делается попытка автоматического подбора метрики.

Литература

  1. Аркадьев А. Г., Браверман Э. М. Обучение машины распознаванию образов. — М.: Наука, 1964.
Личные инструменты