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

В этом разделе мы перенесем некоторые факты, справедливые для восстановления значений функции, на восстановление функции. Рассмотрим методы построения кусочно-линейных разделяющих поверхностей. При построении кусочно-линейной разделяющей поверхности пространство векторов X делится на непересекающихся областей, в каждой из которых строится своя разделяющая гиперплоскость. Классификация векторов с помощью

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

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

Согласно теории упорядоченной минимизации риска структура пространства должна быть задана априори, т. е. задано пространство X, разделение этого пространства на две области, разделение на три области и т. п.

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

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

На множестве (11.33) мы определим таксонную структуру, т. е. различные способы разделения конечного множества (11.33) на подмножества, а для каждого разделения множества на подмножества

определим разбиение пространства X на областей по правилу:

вектор относится к области если из чисел

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

Алгоритм 11-4 использует алгоритм построения таксонной структуры на конечном множестве векторов описанный в приложении к главе Алгоритм строит последовательность векторов путем перенумерации исходной последовательности.

1. В качестве первого вектора х берется произвольный вектор исходного множества. Этот вектор из исходной выборки удаляется.

2. Пусть построена последовательность и эти векторы удалены из исходной последовательности.

В оставшемся множестве векторов находится вектор, ближайший к множеству т. е. такой, для которого величина

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

3. Так продолжается до тех пор, пока вся последовательность (11.33) не будет переупорядочена.

4. Одновременно с построением новой последовательности определим последовательность чисел

Эти числа равны расстоянию между членом новой последовательности и первыми ее членами.

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

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

и образуют искомые таксоны.

Меняя константу с, получим требуемую таксонную структуру.

При построении кусочно-линейного решающего правила выбирается такой элемент таксонной структуры (11.34), на котором кусочно-линейное решающее правило минимизирующее эмпирический риск, доставит минимум функционалу