§ 5. Алгоритмы построения разделяющей гиперплоскости в пространстве минимального числа признаков

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

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

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

Таким образом, поиск минимального подпространства определяется введенным понятием «наименее информативный признак». Определим его следующим образом. Пусть в пространстве  ( признаков) заданы два множества векторов обучающей последовательности – множество векторов  и множество векторов . В пространстве  могут быть построены выпуклая оболочка множества  и выпуклая оболочка множества . Пусть расстояние между выпуклыми оболочками будет .

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

Рассмотрим теперь величину . Эта величина показывает, насколько уменьшится расстояние между выпуклыми оболочками векторов в пространстве  (с исключением -го признака). Будем считать тот признак наименее информативным, с удалением которого расстояние между выпуклыми оболочками уменьшается на минимальную величину.

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

Расстояние между выпуклыми оболочками определяется по формуле

,

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

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

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

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

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

Программа ОП-4 использует как составную часть программу ОП-1.

Алгоритм ОП-5 используется для поиска минимальной размерности, в котором разделяющая гиперплоскость делит обучающую последовательность, совершая не более  ошибок ( – параметр алгоритма). Структура алгоритма ОП-5 аналогична структуре алгоритма ОП-4. Разница заключается лишь в том, что алгоритм ОП-4 прекращает поиск соответствующего подпространства, когда выясняется, что построение разделяющей гиперплоскости становится невозможным, в то время как алгоритм ОП-5 исключает  векторов, «препятствующих» построению разделяющей гиперплоскости, и только после этого прекращает поиск минимального подпространства.

В соответствии с этим алгоритм ОП-5 использует в качестве составной части не алгоритм ОП-1, а ОП-2.