Гипотеза компактности
Материал из MachineLearning.
Гипотеза компактности — в задачах классификации предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму.
В математическом анализе и топологии есть понятие компактного множества (в некоторых случаях, например, в конечномерных пространствах, компактность равносильна замкнутости и ограниченности множества). Гипотеза компактности с этим понятием не имеет ничего общего и должна пониматься в «более бытовом» смысле этого слова.
Для формализации понятия «сходства» вводится функция расстояния или метрика в пространстве объектов
.
Алгоритмы, основанные на анализе сходства объектов, часто называют метрическими, даже в тех случаях, когда функция
не удовлетворяет всем аксиомам метрики;
в частности, далеко не всегда выполняется аксиома треугольника.
В задачах классификации введение метрики позволяет применять широкий класс метрических алгоритмов классификации. Наиболее простые из них:
- метод ближайших соседей
- метод парзеновского окна
- метод потенциальных функций (в простейшем классическом варианте)
Эти методы основаны на предположении, что эксперт уже построил достаточно адекватную метрику, для которой действительно выполняется гипотеза компактности. Однако выбор адекватной метрики является наиболее сложной и наименее исследованной подзадачей. В более «продвинутых» методах делается попытка автоматического подбора метрики.
Литература
- Аркадьев А. Г., Браверман Э. М. Обучение машины распознаванию образов. — М.: Наука, 1964.
