Материал: Учебное пособие Немирко Манило

Используя исходные данные, вычислим

Целевая функция (1.19) равна

L = 0,48x11 +0,1x13 +0,24x22 +0,6x31 +0,3x32 .

Ограничения (1.20) и (1.21) для данного примера имеют вид

будут базисными. Выразим базисные переменные через свободные:

Из условия неотрицательности базисных переменных получаем x31 ≤1; x32 ≤ −4x31 + 4,33;

21

x32 ≤1; x32 ≥ 0,3 −8x31; x32 ≤ 0,66 .

Графически эти условия изображены на рис. 1.4.

Функция цели, выраженная через свободные переменные, равна

L = 0,82 +0,12x31 +0,06x32 ;

L′= L −0,82 = 0,12x31 +0,06x32 ,

и основная прямая L' = 0 имеет вид x32 = −2x31.

L' = max

ОДР

L' = 0

x32 = –8x31 + 0,5

Рис. 1.4

Следовательно, при выбранной оптимальной схеме лечения относительное число выздоровевших больных максимально и составляет 97 %.

22

1.6. Определение линейных разделяющих функций

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

Определим распознаваемый объект как точку в m -мерном евклидовом

рицей-столбцом) Pj , который представлен в виде упорядоченного набора его координат Pj = (p1 j , p2 j , , pmj ). Здесь и далее используется именно такая

символическая запись матриц-столбцов. Предполагается, что для обучающей последовательности ( j L) известна принадлежность объектов к одному из

классов образов A ( j A) или B ( j B).

Основная идея распознавания образов заключена в следующем: если вектор Λ = λ1, λ2, , λm , представленный в виде матрицы-строки, и порог θ удовлетворяют условиям

θ> 0 ,

то можно предположить, что и для объектов с номерами j L соотношения (1.24) также сохраняют свою силу или выполняются с малым числом ошибок. Тогда по знаку линейной функции

ΛPj −θ = λ1 p1 j +λ2 p2 j + +λm pmj −θ

можно судить о принадлежности объекта j к тому или другому классу. Геометрическая интерпретация этого подхода такова: разделение объек-

тов из обучающей последовательности j L гиперплоскостью

ΛP−θ = 0

позволяет при достаточно большом числе точек эффективно разделять и точки распознаваемой последовательности j L . Основная проблема, возникающая при этом, заключена в нахождении вектора Λ (коэффициентов линей-

23

ного решающего правила), удовлетворяющего системе линейных неравенств

(1.24).

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

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

ΛP = λ +θ;

ΛP = −λ +θ,

что:

т. е. ставится задача о максимизации расстояния между полупространствами (1.25) и (1.26), содержащими все точки из множеств LA и LB соответственно.

Если в результате решения этой задачи окажется, что искомый максимум (1.27) является отрицательным, то очевидно, множества LA и LB , а следовательно, множества A и B являются неразделимыми выбором какой-либо гиперплоскости. В этом случае величина (1.27) дает меру неразделимости, устанавливаемую на базе обучающей последовательности. При установлении факта неразделимости целесообразно перейти к более полному описанию объектов, т. е. к увеличению размерности пространства признаков или к изменению их характера, либо к установлению правила неопределенности. Последнее может быть сформулировано в следующем виде: если для какой либо из распознаваемых точек ( j L ) одновременно выполняются неравенства (1.25) и (1.26), то эта точка не может быть отнесена к определенному классу.

Пример нахождения по критерию максимизации (1.27) вектора Λ и двух параллельных гиперплоскостей H1 и H2 , задающих области решений в одной из задач распознавания двух классов электрокардиосигналов (LA и LB ),

24

приведен на рис. 1.5. Здесь два класса сигналов заданы в пространстве спектральных признаков p1 и p2 . Расстояние между центрами классов обозначено ∆. Результирующее решающее правило (1.24), которое используется в линейном классификаторе, задается гиперплоскостью H . При этом удается минимизировать число ошибок при распознавании объектов, не входящих в обучающую последовательность ( j L ).

Рассмотрим методику решения задачи (1.25)–(1.27). В исходной формулировке она не является задачей линейного программирования, однако может быть к ней приведена в результате следующих преобразований.

Подчиним все коэффициенты уравнения разделяющей гиперплоскости условию нормировки:

Λ = λ12 +λ22 + +λ2m =1.

p2

ΛA

H1 H H2

ΛB

Λ

0

p1

Рис. 1.5

Тогда задача (1.25)–(1.27) может быть записана в виде

25