§ 4. Алгоритм построения кусочно-линейной разделяющей поверхности

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

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

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

Поэтому при решении такой задачи также применяются эвристические приемы. В частности, используется тот же стандартный прием, что и в алгоритме ОП-2. Сначала строится одна, в некотором смысле «наилучшая», разделяющая гиперплоскость. Затем к ней достраивается еще одна «наилучшая» гиперплоскость и т. д.

Алгоритм ОП-3 основан на том, что в качестве наилучшей гиперплоскости выбирается такая ориентированная гиперплоскость, которая делит обучающую последовательность с минимальным числом ошибок (гиперплоскость строится с помощью алгоритма ОП-2). Затем эта гиперплоскость фиксируется и к ней достраивается еще одна (также с помощью алгоритма ОП-2).

Достраивается «наилучшая» разделяющая гиперплоскость по следующему правилу.

Пусть к моменту времени  построена (с помощью ОП-2) разделяющая гиперплоскость, которая на части векторов обучающей последовательности делает ошибки. Образуем с помощью построенной разделяющей гиперплоскости и векторов обучающей последовательности новый массив векторов размерности  по следующему правилу.

Каждому вектору  обучающей последовательности становится в соответствие вектор  в пространстве размерности , у которого первые  координат совпадают с координатами вектора , а  и  координаты суть соответственно 1,0, если вектор  лежит по одну сторону от построенной гиперплоскости (т. е. ), или 0,1, если вектор  лежит по другую от нее сторону .

Полученное множество векторов  проиндексируем по правилу: вектор  относится к первому классу, если соответствующий ему вектор  принадлежал первому классу, вектор  относится ко второму классу, если вектор  принадлежал ко второму классу.

Разделим теперь множество векторов  на два класса с помощью гиперплоскости

.

В пространстве размерности  этому разделению соответствует разделение векторов  с помощью гиперповерхности, составленной из кусков гиперплоскостей с направляющими векторами  и  (вектор  коллинеарен -мерному вектору, образованному первыми  координатами вектора ).

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

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

Сначала по вектору  и первой разделяющей гиперплоскости вычисляется вектор . Затем в новом пространстве  с помощью второй разделяющей гиперплоскости строится вектор  и т. д. Наконец, вектор относится к первому классу, если , и ко второму, если .

Алгоритм ОП-3 включает в себя как составную часть ОП-2.