§ 13. Алгоритмы построения экстремальных кусочно-линейных решающих правил

В 50-х годах Фикс и Ходжес рассмотрели следующий алгоритм построения дискриминационного решающего правила [78].

Пусть заданы обучающая последовательность

и рабочий элемент . Пусть в пространстве  определена метрика .

Упорядочим элементы обучающей последовательности по близости к вектору  в метрике . Соответствующим образом перенумеруем эти векторы. Затем рассмотрим первые  элементов перенумерованной последовательности ( – параметр алгоритма; определение  и составляет предмет исследований теоретиков этого метода). Вектор  относится к первому классу, если среди  элементов преобладали элементы первого класса, и относится ко второму классу в противном случае.

Основная идея алгоритма Фикса – Ходжеса состоит в том, чтобы строить решающее правило не по всей выборке, а лишь по выборке, попадающей в окрестность дискриминируемой точки. Фикс и Ходжес рассмотрели самый простой тип «локального» решающего правила – константу и все внимание сконцентрировали на определении величины «окрестности».

Пользуясь оценками (6.19) и (6.21), можно определить величину экстремальной окрестности для локальных линейных решающих правил и тем самым строить не экстремальные кусочно-постоянные решающие правила, а более содержательные экстремальные кусочно-линейные решающие правила. Вот как это можно сделать.

Упорядочим элементы обучающей последовательности по близости к элементу . Затем последовательно рассмотрим  экстремальных гиперплоскостей, разделяющих соответственно  элементов упорядоченной обучающей последовательности. Качество каждой из  построенных разделяющих гиперплоскостей может быть оценено с помощью критериев (6.20') и (6.21) (соответственно для детерминистского и стохастического вариантов задачи). Вектор  относится к тому классу, к которому его относит гиперплоскость с наилучшей оценкой качества.

Таким образом, построение экстремальной кусочно-линейной разделяющей поверхности связано не только с минимизацией критериев (6.19), (6.21) по параметрам , , , , но и с минимизацией по параметру .