2.5.2. Дихотомии

Одной из характеристик разделяющей мощности решающей функции является число способов классификации заданного множества объектов, осуществимых с ее помощью. Обратимся, в частности, к рис. 2.7, на котором представлен набор, состоящий из четырех двумерных образов . Каждая прямая на рисунке соответствует определенному варианту разбиения образов на два класса.

Рис. 2.7. Линейная дихотомия для четырех «хорошо» размещенных образов в двумерном случае.

Прямая 1, например, выделяет две группы: образ и образы Поскольку образ можно отнести как к классу так и к классу прямая 1 определяет две возможные классификации. В данном случае общее число разбиений на два класса или дихотомий равно 14. Интересно сопоставить эту оценку с общим числом возможных способов распределения четырех объектов по двум классам (24). Очевидно, что 2 из этих 16 дихотомий линейио реализовать нельзя.

Количество линейных дихотомий точек в n-мерном евклидовом пространстве равно удвоенному числу способов разделения этих точек -мерной гиперплоскостью. Можно

показать, что при «хорошем» размещении точек число линейных дихотомий для N образов размерности определяется следующим выражением:

где . Множество, состоящее из точек -мерного пространства, называют хорошо размещенным), если ни одно из его подмножеств, состоящее из точек, не лежит на -мерной гиперплоскости. Так, например, двумерных точек хорошо размещены, если никакие три точки не лежат на одной прямой (одномерной гиперплоскости).

Величины для различных вариантов сочетаний числа точек и размерности приведены в табл. 2.2. Обратите внимание на чрезвычайно бурный рост числа линейных, дихотомий при сравнительно умеренном увеличения значений

Таблица 2.2. (см. скан) Оценка числа линейных дихотомий в зависимости от числа образов и их размерности

Интересно установить связь оценки (2.5.12) с числом выпуклых многогранных конусов, обсуждавшихся при рассмотрении пространства весов в § 2.4 Обратимся снова к рис. 2.5, в. Любой

вектор расположенный внутри одного из выпуклых конусов, соответствует определенному варианту классификации заданной совокупности образов Поскольку число линейных дихотомий определяется оценкой (при условии правильного размещения образов), следует сделать вывод, что в пространстве весов, соответствующем N образам размерности , должно размещаться такое же количество выпуклых многогранных конусов.

Результаты проведенного анализа легко продолжить на случай обобщенных решающих функций, рассмотренных в § 2.3. Поскольку введение этих функций приводит к образам новой размерности, следует просто заменить размерностью полученных образов. Пусть, например, задано 10 двумерных образов и эта выборка хорошо размещена. Тогда общее количество возможных дихотомий равно При использовании полиномиальной решающей функции второго порядка размерность новых образов равна что приводит к потенциально возможным дихотомиям.

Так как число дихотомий используется в качестве меры классификационной мощности, должно быть очевидным, что чем больше дихотомий для заданных образов может быть реализовано, тем более вероятно, что мы найдем решение заданных неравенств. Это обстоятельство, естественно, согласуется с тем фактом, что вероятность успешного разделения двух групп образов с помощью дихотомической процедуры увеличивается по мере того, как растет степень нелинейности испытываемых разделяющих границ.