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

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

Версия от 20:29, 25 мая 2008; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

Личные инструменты