General method for construction of a piecewise-linear separating surface for sets of objects defined by points in a feature space

Abstract

The article presents a general method for construction of separating surface for sets of points in a feature space. The method is based on using of hyperplanes normal to intercenter vectors of sets.

Full Text

Геометрическая интерпретация объектов из некоторого однотипного набора реализуется при помощи задания точек в многомерных пространств значений характеристических признаков объектов. В общем случае сложной задачей является не только построение разделяющих поверхностей для произвольных множеств точек-прецедентов, но и получение алгоритмов разделения, эффективных в вычислительном плане, т.е. не требующих больших вычислительных затрат при классификации новых точек. Для упрощения вида получаемых условий разделения вместо обычного вектора координат точек`х в пространстве признаков использованы однородные координаты вида` хр = (1,`х ), у которых на начальной позиции к`х добавлена единица. Условие отделения для отдельной точки с однородными координатами`хр принимает вид: (`С i1k,`хр) ³ 0. (1) Предложено строить разделяющие поверхности в виде совокупностей гиперплоскостей – простейших поверхностей в рассматриваемых пространствах. Поскольку в общем случае проблема построения оптимальной разделяющей плоскости является сложной переборной задачей, то для упрощения данной задачи для пары множеств точек предложено использовать гиперплоскости фиксированного вида – нормальные по отношению к межцентровому вектору множеств. Получаемая в итоге построения графо-аналитическая структура названа нормальным классификатором (НК). Для каждого отделяемого множества Аi итоговый НК содержит две основные компоненты. 1. Бинарное дерево Тi, задающее структуру множества Аi, в котором узлам nti (1£ nti £nЕi) дерева Тi, практически соответствуют подмножества Аij исходного множества Аi (в частности, корню (nti =0) соответствует все Аi), а программная модель узла может содержать 0,1 или 2 ссылки на левый и правый потомки узла. Пустые ссылка в узле дерева обозначаются значением (-1). 2. Каждому узлу nti дерева Тi, (и соответствующему подмножеству Аnti ÎАi) может соответствовать одна гиперплоскость Нnti, заданная множеством ее коэффициентов`С = (С0,С1,…,Сn) и описывающая геометрическое условие, проверяемое для подмножества Аnti для его отделения. Если узлу дерева Тi соответствует своя гиперплоскость, его назовем разделяющим. В противном случае проходным. В процессе построения НК двух множеств А1 и А2 необходимо использовать дополнительную промежуточную информацию и структуры для ее эффективного хранения и преобразования. Для подмножеств Аnt1 и Аnt2, используемых при разделении обоих исходных множеств А1 и А2 предложено дополнительно использовать массивы координат точек, длин подмножеств, координат их центров тяжести, радиусов, а также номеров подмножеств Фактически, в процессе построения НК1 {nE1, T1, ТT1, Н 1} и НК2{ nE2,T2, TТ2, Н2} используется общая структура S={T,ТT1,TТ2,Н1,Н2,AS1,AS2,L1,L2, C1,C2,R1,R2, N1, N2}, включающая в себя общее дерево T. После завершения разделения по ней строятся искомые НК1и НК2. Обозначим координаты центров тяжести классов А1,А2 через`С1 и`С2, радиусы их (расстояния от центра до максимально удаленной точки) – через R1, R2. Межцентровым назван вектор``С12, соединяющий `С1 и`С2:`С12 =`С2 -`С1. Длина вектора`С12 (межцентровое расстояние множеств А1,А2) обозначена r12. Гиперплоскости, нормальные к вектору `С1С2. Для краткости они названы нормальными. Уравнение нормальной плоскости имеет простой вид: N12(`x , С0) = (`С12,`x1 ) + С0 = 0. (2) Нормально разделимыми названа такая пара классов А1,А2, для которых существует единственная разделяющая их нормальная гиперплоскость. Условием разделения точек классов А1 и А2 гиперплоскостью Н12 с вектором коэффициентов `С является следующая пара неравенств: Н12(`xр , `С) ³ 0, если `xÎ А1 , Н12(`xр , `С) < 0, если `xÎ А2 . (3) Для нормально разделимых классов доказаны две теоремы. Теорема 1. Если для классов А1,А2, имеющих радиусы R1, R2, а также межцентровое расстояние r12, выполняется условие r12 ³ R1 + R2, (4) то данные классы нормально разделимы и, в частности, классификатором будет являться опорная нормальная гиперплоскость Н12(`xр,`С), у которой свободный коэффициент С0 принимает следующее значение: `Р0 = `С1 +`С12 × R1 /( R1 + R2), С0 =(`С12,`Р0) = (`С12,`С1 +`С12 × R1 /( R1 + R2)). (5) Теорема 1 задает простейшее по форме достаточное, но не являющееся необходимым, условие нормальной разделимости классов. Для краткости такой вариант разделимости назовем шаровым. Введя безразмерный параметр, названный степенью разделимости l=r12 /( R1 + R2), условие (4) можно представить в эквивалентной форме как: l ³ 1. Для исследования более сложных случаев нормальной разделимости введены вспомогательные понятия. Рассмотрим плоскость p(`P0,`Vj), проходящую через точку`P0 перпендикулярно вектору`Vj. Позицией точки`х(а1i) из класса А1 c центром`С1 относительно плоскости p(`P0,`Vj) названа величина р(`х(а1i),`С1, p(`P0,`Vj)) = r(`х(а1i),p(`P0,`Vj))×sign(F(`х(а1i),p(`P0,`Vj))) sign(F(`С1,p(`P0,`Vj))). (6) Позицией множества А1 c центром`С1 относительно плоскости p(`P0,`Vj) назовем величину р(А1, p(`P0,`Vj)) = min{ р(`х(а1i),`С1, p(`P0,`Vj)) }, где а1i Î А1. Доказан критерий нормальной разделимости в следующей форме. Теорема 2. Классы А1,А2 с межцентровым вектором`С12 нормально разделимы тогда и только тогда, когда относительно какой-либо опорной нормальной плоскости p(`P0,`С12) для их позиций d1 = р(А1, p(`P0,`С12)), d2 = р(А2, p(`P0,`С12)) выполняется условие: d1 + d2 ³ 0. (7) Поскольку полная нормальная разделимость не всегда возможна, то для обеспечения практического решения задачи разделения пары множеств произвольного вида в дополнение к полному нормальному разделению предложено использовать две дополнительные операции: 1) отсечение (частичное разделение) и 2) бинарную кластеризацию (внутреннее разделение множества). Рассмотрим практическую реализацию отсечения. Зафиксируем некоторую опорную нормальную плоскость p(`P0,`С12) и рассмотрим крайнюю точку`х2кр множества А2 (рисунок 1), в которой достигается минимум позиций всех точек А2, т.е. позиция d2 всего А2. Поскольку множества А1 и А2 полностью нормально не разделимы, то из множества А1 выделим только то подмножество точек А1о ÌА1, которые отделяются точкой `х2кр . По Теореме 2 для всех точек подмножества А1о должно выполняться условие: р(`х(а1i),`С1, p(`P0,`Vj)) + d2 ≥ 0. Рисунок 1 В том числе данное условие выполняется для крайней точки`х1кр(о) из подмножества А1о. Ее позицию обозначим как d1о. Она равна минимуму всех позиций точек из подмножества А1о. По Теореме 2 для того, чтобы промежуток между крайними точками множеств А1о и А2 был разделен пропорционально радиусам множеств, в качестве нормально разделяющей плоскости p¢ (`P¢0,`С12)) между А1о и А2 примем нормальную плоскость p12 = N12(`x, С0), у которой точка пересечения`P01 сдвинута относительно крайней точки`х1кр(о) подмножества А1о по вектору`С12 на расстояние d12 : d12 = (d1о + d2) R1/(R 1+R2). Данную гиперплоскость назовем отсекающей для множества А1, а подмножество А1о отсекаемым. Координаты точки пересечения`P01 : `P01 =`Р0 + (d12-d1о) ×`С12/r12 . Аналогично по крайней точке`х1кр множества А1 можно рассмотреть отсекаемое подмножество точек А2оÌА2, для позиций которых относительно p(`P0,`С12) выполняется условие: d1 + р(`х(а2i),`С1, p(`P0,`Vj)) ≥ 0. Затем определяем крайнюю точку`х2кр(о) из подмножества А2о, ее позицию обозначим как d2о (минимум всех позиций точек из А2о). По Теореме 2 в качестве нормально разделяющей должна быть принята нормальная плоскость p21, у которой точка пересечения`P02 сдвинута относительно крайней точки `х1кр множества А1 по вектору`С12 на расстояние d21: d21 = (d1 + d2о) R1/(R 1+R2). Координаты точки пересечения`P02: `P0 2 =`Р0 + (d21-d1) ×`С12/r12 . Знаки коэффициентов в уравнении для плоскости p21 необходимо взять со знаком минус, для того, чтобы на подмножестве А2о оно принимало неотрицательные значения. Плоскости p1 и p2 при отсутствии полной нормальной разделимости задают частичное разделение множеств А1 и А2.. Принимая N12(`x ) = p12, N21(`x ) = p21, получаем выполнение условий их частичного нормального разделения. Часть пространства, лежащая между гиперплоскостями p12 и p21, назовем промежуточным слоем. В нем одновременно выполняется совокупность двух условий: N12(`x ) < 0, N21(`x ) < 0. Обозначим совокупность элементов множества А1, входящих в промежуточный слой, через А1п, а набор элементов множества А2 в промежуточном слое через А2п. Назовем их промежуточными подмножествами исходных множеств. Очевидно, для отсекаемых и промежуточных подмножеств выполняются соотношения: А1 = А1о È А1п, А2 = А2о È А2п. При этом исследование разделимости исходных множеств А1 и А2 сведено к исследованию разделимости их более простых промежуточных подмножеств А1п и А2п. Обозначим числа точек в отсекаемых множествах А1о и А2о как n1о и n2о. Отсечение множеств будем называть результативным, если выполняется условие n1о+n2о > 0. Операция бинарной кластеризации означает такое внутреннее разделение множества точек в пространстве признаков гиперплоскостью, при котором достигается максимум условия оптимальности получаемого разбиения {А1, А2}, которое имеет вид: l (А1, А2) = r12/( R1 + R2) ® max (А1, А2). (8) В общем случае глобальный экстремум задачи (8) может достигаться не на единственной паре возможных подмножеств {А1, А2}.Точное решение задачи можно найти перебором всех возможных вариантов разбиения множества на пары непустых подмножеств А1, А2 и вычислением для них значения l(А1, А2). Однако расчет на вычислительных устройствах средней производительности позволяет практически решать такие задачи размерности не выше 15-18 точек. Разработаны приближенные алгоритмы, позволяющие получать решения, совпадающие либо достаточно близкие к оптимальным, но значительно сокращающие перебор за счет замены требования глобальной оптимальности на локальную [2]. Для того, чтобы общий алгоритм разделения множеств не содержал повторных фрагментов кода, в нем выделен вспомогательный алгоритм BinClast2Set функции кластеризации большего из двух множеств A1T и A2T с записью результатов во все массивы структуры S. На основе рассмотренных выше трех базовых операций полного и частичного нормального внешнего разделения множеств и их бинарной кластеризации (внутреннего разделения), реализованного в алгоритме BinClast2Set, предложен следующий общий алгоритм разделения двух множеств. 1. Исходные данные: – n – размерность пространства U, – n1,n2,nmax – числa точек в исходных множествах А1,А2 и максимум из (n1,n2), – векторы A1Т[n1*n],A2Т[n2*n] координат точек исходных множеств А1,А2, – векторы координат центров тяжести текущих множеств C1N, C2N, – радиусы текущих множеств R11;R22. 2. Решаемые задачи. Определение: – общего числа nE узлов в общем дереве Т, – векторы Т1[V*2],Т2[V*2], задающие структуру деревьев Т1,Т2 множеств А1,А2, – векторы TT1[V]; TT2[V], задающие типы узлов в деревьях Т1,Т2, – итоговые массивов H1[V*(n+1)],H2[V*(n+1)] коэффициентов разделяющих гиперплоскостей для узлов деревьев Т1,Т2. 3. Вспомогательная информация: – массивы векторов NТ1[V];NТ2[V],задающие номера подмножеств А1,А2, соответствующие узлам в общем дереве Т, – массивы AS1[V*nmax*n]; AS2[V*nmax*n] координат всех подмножеств из А1,А2, – массивы длин L1[V];L2[V] подмножеств множеств А1,А2, – массивы координат центров тяжести всех множеств С1[V*n];С2[V*n], – массивы радиусов всех множеств R1[V];R2[V], – V – начальная оценка возможного числа узлов общегодерева Т, – номер nt текущeго узлa Т и текущие номера nА1, nА2 подмножеств из А1,А2. Общий алгоритм разделения двух множеств Separate2Set. Шаг 1. Начальные присваивания: Шаг 1.1. Расчет вспомогательныхвеличин: CR1=0.001*RMIN; CR5=0.5*RMIN; nmax=max(n1;n2); V=2nmax. Шаг 1.2. Начальные засылки в массивы NT1[0]=0;NT2 и числа подмножеств: NT1[0]=0;NT2[0]=0;nA1=1;nA2=1. Шаг 1.3. Начальные засылки в массивы AS1; AS2: Помещение координат точек множества А1 в начало массива AS1; Помещение координат точек множества А2 в начало массива AS2. Шаг 1.4. Расчет параметров новых помножеств A21[n21], A22[n22]: CalcParam(2,n,n21,A21,C1N,R1N); if(R1N<CR1)R1N=CR5; CalcParam(2,n,n22,A22,C2N,R2N); if(R2N<CR1)R2N=CR5. Шаг 1.5. Запись параметров A21[n21], A22[n22] в массивы SA2,R2,L2,С2. Шаг 1.6. Запись пустых ссылок в узел 0 дерева Т, начальных значений числа его узлов, текущего узла и ключа для перебора узлов Т: T[0]=-1;T[1]=-1; nE=1; nt=-1; keyw=true. Шаг 2. Цикл while (keyw)по узлам дерева T. Шаг 2.1. Проверка начала обработки: Если (nt=-1), то {nt=0; STnA1=-1; STnA2=-1;}, иначе {если (nt<nE-1), то nt+=1;иначе{keyw=false;continue;};}; Шаг 2.2. Определение длины анализируемых подмножеств: n1=L1[NT1[nt]]; n2=L2[NT2[nt]]; Шаг 2.3. Проверка необходимости и изъятие координат и основных параметров очередного подмножества A1[nt] : Если (NT1[nt]!=STnA1), то {переписывание подмножества с номером NT1[nt] в массив A1T, его центра тяжести в массив C1N, радиуса в переменную R11}. Шаг 2.4. Проверка необходимости и изъятие координат и основных параметров очередного подмножества A2[nt] : Если (NT2[nt]!=STnA2), то {переписывание подмножества с номером NT2[nt] в массив A2T, его центра тяжести в массив C2N, радиуса в переменную R22}. Шаг 2.5. Cохранение прежних номеров множеств для узлов в Т: STnA1=NT1[nt]; STnA2=NT2[nt]. Шаг 2.6. Рачет вектора С12, расстояния R12 и степени разделимости l: RQ=0;for(j=0;j<n;j++){Cd=C2N[j]-C1N[j];C12[j]=Cd;RQ=RQ+Cd*Cd;}; R12=sqrt(RQ); l=R12/(R11+R22). Шаг 2.7. Обработка вложенных множеств А1 и А2: Если (l£0.2),то { 1) применение алгоритма BinClast2Set выборочной бинарной кластеризации для пары множеств A1T,A2T с записью результатов в массивы структуры S; 2) continue; }; Шаг 2.8. Обработка множеств с шаровой разделимостью: 1) применение алгоритма SphereSeparate к паре множеств A1T,A2T с расчетом опорной плоскости CH и ее точки пересечения P0с межцентровым вектором, 2) если (l³1),то { a)запись векторов коэффициентовразделяющих плоскостей в массивы Н1,Н2, b) TT1[nt]=true;TT2[nt]=true; c) continue; }; Шаг 2.9. Обработка множеств с промежуточным типом разделения: 1) если (0,2<l<1),то проверка нормальной разделимости A1T,A2T при помощи алгоритма NormSeparate с расчетом позиций PS1,PS2 их точек относительно опорной плоскости (key=NormSeparate), 2) если есть нормальная разделимость запись ее результатов: if(key=true){ a) Запись коэф.разделяющих плоскостей в массивы Н1,Н2, b) TT1[nt]=true;TT2[nt]=true; c) continue; }; 3) если нет нормальной разделимости – попытка выполнения отсечения: a) if(key==false), то {проверка выпронения результативного отсечения подмножеств A1T,A2T при помощи алгоритма SetCut с использованием массивов позиций PS1,PS2 (key1= SetCut), b) если отсечение A1T,A2T результативно (key1= true), то { запись коэф.разделяющих плоскостей в массивы Н1,Н2, присваивание: TT1[nt]=true; TT2[nt]=true; формирование узлов T, соответствующих промежуточным множествам: T[nt*2+1]=nE; T[nE*2]=-1;T[nE*2+1]=-1; если (n1M<n1), то {NT1[nE]=nA1; Запись координат точек промежуточного множества A1M в элемент nA1 массива AS1; расчет основных параметров A1M и запись из на места nA1в массивы структуры S; nA1:= nA1+1}; если (n1M=n1), то {NT1[nE]=NT1[nt];T[nE*2]=-2;}; если (n2M<n2), то {NT2[nE]=nA2; Запись координат точек промежуточного множества A2M в элемент nA2 массива AS2; расчет основных параметров A2M и запись их на места nA2в массивы структуры S; nA2:= nA2+1}; если (n2M=n2), то {NT2[nE]=NT2[nt];T[nE*2]=-3;}; continue; }; с) если отсечение A1T,A2T нерезультативно (key1= false), то { применение алгоритма BinClast2Set выборочной бинарной кластеризации для пары множеств A1T,A2T с записью результатов в массивы структуры S; continue; }; };//Завершение цикла while (keyw) Шаг 3. Формирование НК1 и НК2: Шаг 3.1. Формирование деревьевТ1 и Т2 – запись в цикле по i от 0 до nE-1: {T1[2*i]= T[2*i]; T2[2*i]= T[2*i]; если (T1[2*i]=-2), то {T1[2*i]=0; T2[2*i]=-1;}; T1[2*i+1]= T[2*i+1]; T2[2*i+1]= T[2*i+1]; }; }// Завершение работы алгоритма Separate2Set. Пример 1. Рассмотрим разделение пары множеств точек в двухмерном пространстве, показанных на рисунке 2 ( n1 = 10; n2 = 3; А1[10] = {(1,0;1,0), (1,0;2,0), (1,0;3,0), (2,0;1,0), (2,0;4.0), (3,0;1,0), (3,0;4,0), (4,0;1,0), (5,0;2,0), (5,0;3,0)}; А2[3] = {(2,0;2,0), (3,0;2,0), (2,0;3,0)}). Разделение осложняется тем, что одно множество лежит внутри другого. Рисунок 2 Рисунок 3 Применение вышеизложенного алгоритма дает в итоге следующие НК1 и НК2: НК1 {nE1, T1, ТT1, Н 1}: nE1=6, nt=0;T1[0;L]=1;T1[0;R]=2; TT1[0]=1; H1[0]=(16.51; -3.75; -0.75); nt=1; T1[1;L]=3; T1[1;R]=4; TT1[1]=1; H1[1]=(10.59; -0.75; -2.75); nt=2; T1[2;L]=-1; T1[2;R]=-1; TT1[2]=1; H1[2]=( -10.884; 2.67; 0.17); nt=3; T1[3;L]=-1; T1[3;R]=5; TT1[3]=1; H1[3]=(2.29;-0.33;-0.83); nt=4; T1[4;L]=-1; T1[4;R]=-1; TT1[4]=1; H1[4]=(-6.39;-0.00;2.00); nt=5; T1[5;L]=-1; T1[5;R]=-1; TT1[5]=1; H1[5]=(0.13; -1.50;1.00). НК2{ nE2,T2, TТ2, Н 2}: nE1=6, nt=0; T2[0;L]=1; T2[0;R]=2; TT2[0]=0; H2[0] = Æ; nt=1; T2[1;L]=3; T2[1;R]=4; TT2[1]=0; H2[1] = Æ; nt=2; T2[2;L]=-1; T2[2;R]=-1; TT2[2]=1; H2[2] = (10.884; -2.67; -0.17); nt=3; T2[3;L]=-1; T2[3;R]=5; TT2[3]=1; H2[3] =(-0.08;0.33; 0.83); nt=4; T2[4;L]=-1; T2[4;R]=-1; TT2[4]=1; H2[4] = (6.39;0.00;-2.00); nt=5; T2[5;L]=-1; T2[5;R]=-1; TT2[5]=1; H2[5] = (-0.13;1.50; -1.00). Положение разделяющих гиперплоскостей (при n =2 – прямых) показано на рисунке 3. Стрелками дополнительно указаны положительные полуплоскости. Построенный общий алгоритм разделения пары множеств может быть применен к решению задачи классификации произвольного числа множеств, заданных наборами своих характерных объектов прецедентов. Данный алгоритм не требует выполнения большого числа циклов обучения и эффективно за один проход решает довольно сложные задачи разделения, аналогичные рассмотренному выше примеру. Созданная библиотека расчетных программ практически позволяет применять разработанный метод классификации к любым множествам точек в многомерных пространствах признаков.