§ 4. Алгоритм построения кусочно-линейной разделяющей поверхностиВо многих приложениях возникает необходимость разделить элементы обучающей последовательности с помощью гиперповерхности, образованной кусками гиперплоскостей. Известно, что если среди векторов обучающей последовательности нет двух тождественных векторов, принадлежащих разным классам, то всегда найдется такая разделяющая гиперповерхность, составленная из кусков гиперплоскостей, которая безошибочно разделит векторы обучающей последовательности. Однако желательно, чтобы разделяющая гиперповерхность состояла из минимального числа кусков гиперплоскостей. Принципиально можно предложить переборную схему, с помощью которой, в конце концов, удастся построить разделяющую гиперповерхность, образованную минимальным числом кусков гиперповерхностей. Однако ее реализация требует слишком большого объема вычислений. Поэтому при решении такой задачи также применяются эвристические приемы. В частности, используется тот же стандартный прием, что и в алгоритме ОП-2. Сначала строится одна, в некотором смысле «наилучшая», разделяющая гиперплоскость. Затем к ней достраивается еще одна «наилучшая» гиперплоскость и т. д. Алгоритм ОП-3 основан на том, что в качестве наилучшей гиперплоскости выбирается такая ориентированная гиперплоскость, которая делит обучающую последовательность с минимальным числом ошибок (гиперплоскость строится с помощью алгоритма ОП-2). Затем эта гиперплоскость фиксируется и к ней достраивается еще одна (также с помощью алгоритма ОП-2). Достраивается «наилучшая» разделяющая гиперплоскость по следующему правилу. Пусть к моменту времени Каждому вектору Полученное множество векторов Разделим теперь множество векторов
В пространстве размерности Если же и с помощью гиперповерхности, образованной кусками двух гиперплоскостей, безошибочное разделение невозможно, то обучающая последовательность делится с помощью гиперповерхности, образованной из кусков трех гиперплоскостей, для чего, аналогично предыдущему, образуется множество векторов размерности Классификация векторов с помощью построенной разделяющей поверхности, образованной кусками гиперплоскостей, происходит по следующему правилу. Сначала по вектору Алгоритм ОП-3 включает в себя как составную часть ОП-2.
|