close

Вход

Забыли?

вход по аккаунту

?

Алгоритмы коррекции многомерной линейной разделяющей поверхности.

код для вставкиСкачать
УДК 615.47
АЛГОРИТМЫ КОРРЕКЦИИ МНОГОМЕРНОЙ ЛИНЕЙНОЙ РАЗДЕЛЯЮЩЕЙ
ПОВЕРХНОСТИ
Е.Б. Рябкова, Т.Н. Говорухина, Н.А. Кореневский
В работе рассматриваются вопросы коррекции положения линейной разделяющей поверхности в многомерном
пространстве признаков с целью улучшения показателей качества классификации в задачах распознавания образов
со структурой классов, не удовлетворяющей гипотезе об их нормальном распределении
Ключевые слова: теория распознавания, линейная разделяющая поверхность, настраиваемые параметры, ошибка классификации, многомерное пространство признаков
В классической теории распознавания образов для разделения различных классов состояний в
многомерном пространстве признаков достаточно
широкой популярностью пользуется линейная
разделяющая поверхность (ЛРП) вида:
n
∑а x
i
i
+ a0 = 0
(1)
i =1
где хi – вектор информативных признаков, а0,
а1,…, аn – вектор настраиваемых параметров, определяющих ориентацию гиперплоскости (1) в
пространстве информативных признаков.
Существует множество способов выбора вектора настраиваемых параметров, обеспечивающих
оптимальное или квазиоптимальное положение
гиперплоскости (1), обеспечивающее разделение
альтернативных классов ω l и ω r в пространстве
информативных признаков. [1,2,3] Однако, при
выборе методов построения линейных разделяющих поверхностей следует иметь ввиду, что большинство из них реализуются для известных законов распределения классов в многомерном пространстве признаков (в основном для нормативных законов распределения). В условиях неполного и нечеткого представления данных, получаемые ЛРП чаще всего дают результаты далекие от
оптимальных. Это может вызываться, например,
неоднородностью распределения объектов обучающей выборки классов, наличием казуистических ситуаций и т.д. В связи с этим нами предлагается способ уточнения положения для ЛРП в
пространстве признаков использующий гистограммы hωl и hωr распределения классов ω l и ω r
строящихся на шкале, характеризующей расстояние от объектов исследуемых классов до разделяющей гиперплоскости (1) [3].
Числовое значение этой шкалы определяется
выражением:
Рябкова Елена Борисовна – ЮЗГУ, аспирант, тел.
(4712) 58-70-98
Говорухина Татьяна Николаевна – ЮЗГУ, студент, тел.
(4712) 58-70-98
Кореневский Николай Алексеевич - ЮЗГУ, д-р техн.
наук, профессор, тел. (4712) 58-70-98
n
Y = ∑ аi xi
(2)
i =1
Предлагаемый способ реализуется с помощью
следующего алгоритма вычисления настраиваемых параметров.
Определяется стартовое (начальное) положение линейной разделяющей поверхности (ЛРП)
любым из доступных способов, например методами
линейного дискриминантного анализа из стандартного пакета прикладных программ. В простейшем
случае стартовое положение ЛРП может быть определено путем построения гиперплоскости перпендикулярной линии соединяющей геометрические центры исследуемого класса ω l и альтернативного класса ω 0 . В качестве альтернативного
класса может быть выбран один класс, если решается задача разделения двух классов или объединение множества классов противопоставляемых классу ω l .
Настраиваемые параметры аi такой гиперплоскости определяются выражением вида:
аi = mi ,ω − mi ,ω ,
(3)
1
2
где mi ,ω - i -ая координата «центра тяжести» класса
1
ω1 ; mi ,ω - класса ω 2 .
2
1. Используя выражение 2 как шкалу интервалов строим на ней гистограммы hωl и hωr распределения классов ω l и ω r (рис.1).
На оси Y выберем координату у0 относительно которой предполагается осуществлять принятие
классификационных решений по классам ω 0 и ω l .
С целью упрощения вычислительных процедур
рекомендуется координату у0 расположить так,
чтобы гистограмма одного из классов лежала целиком по одну сторону от этой координаты.
В примере рис. 1 у0 выбрана так, что вся гистограмма класса ω l находится слева от этой точки
с некоторым «запасом». Это означает, что при
Y = у 0 разделяющая гиперплоскость выделяет объекты класса ω l без ошибок, поскольку весь этот
класс в пространстве признаков располагается по
одну сторону от ЛРП. По классу ω 0 полученная
разделяющая поверхность будет «совершать ошиб-
ки» для всех объектов сформировавших левую
часть гистограммы hω лежащей левее координаты
0
у0 .
hωl
hω0 (hωr )
Z
hω0 (hωr )
hωl
у0/
•
у j ,0 ( у j ,r ) у0
Y
Рис.1. Вариант выбора у0 относительно гистограмм альтернативных классов.
Задачу уточнения положения ЛРП можно рассматривать как процесс изменения стартовых значений параметров аi ( i = 1, ,n )таким образом,
чтобы число ошибочно классифицируемых объектов было уменьшено.
Для описания реализации этого процесса введем ряд обозначений.
Объекты (точки) многомерного пространства
признаков принадлежащие классу ω l обозначим
вектором Х j ,ω = {x1l j ,..., xnjl } , объекты принадлежа-
щие классу ω0 − X j ,ω = {x10j ,...xnj0 }. С помощью праl
0
вила (2) каждому многомерному объекту пространства размерностью n ставится в соответствии точка у j ,l (для класса ω l ) и у j ,0 (для класса ω 0 ) на
шкале Y . Назовем координаты у j ,l и у j ,0 отображениями объектов Х j ,ω и Х j ,ω на шкалу Y .
l
0
В приведенных обозначениях количество ошибок классификации ЛРП будет уменьшаться, если
при изменении аi количество отображений объектов класса ω 0 «смещающихся» из левой относительностью у0 области в правую будет превышать
количество отображений объектов класса ω l
«смещающихся» правее у0 . Причем качество классификации будет тем больше, чем больше будет это
превышение.
Для примера, приведенного на рисунке 1 очевидно, что если к первоначально заданным коэффициентам аi добавлять положительный шаг ∆аi ,
то все значения перемещаются вправо по оси Y.
Обозначим через S 0 число объектов класса ω 0 ,
отображения которых лежащие слева от у0 перемещаются так, что начинают располагаться справа
от у0 после выполнения операции присваивания
типа аi = аi + ∆аi . Через S l обозначим число объектов класса ω l , отображения которых перемещаются так, что находятся справа от у0 . Тогда, если
S 0 > S l классификационная способность правила
(2) улучшается и эта способность будет тем больше, чем больше будет разность ∆S = S 0 − S l .
Аналогичные рассуждения будут справедливы
если у0′ разместить слева от гистограммы класса
ω 0 и начать процедуру уменьшения первоначально
заданных параметров аi в соответствии с выражением аi = аi − ∆аi . В этом случае задача заключается в поиске такого шага ∆аi , который обеспечивает
максимальную разность вида ∆S ′ = S l′ − S 0′ , где S l′ число отображений объектов из ω l перешедших из
правой, относительно у0′ части в левую, а S 0′ - число отображений объектов из ω 0 размещающихся
левее «границы» у0′ .
2. Определяется шаг ∆аi изменения настраиваемых параметров аi с учетом знака, обеспечивающий максимальное значение ∆S ( ∆S ′ ) .
В предлагаемой работе процедура выбора шага
∆аi производится исходя из следующих соображений.
Рассмотрим вначале вариант расчета ∆аi для
границы у0 , начиная с положительного шага ∆аi .
Пусть объекту Х j ,ω соответствует отображе0
ние с координатой у j ,0 (рис. 1). Очевидно, что если
изменить аi на ∆аi так, что отображение у j ,0 сместится вправо так, что дойдет до «границы»
у0 , и
при этом не одно из отображений объектов класса
ω l не дойдет до этой границы, то ошибка классификации уменьшится на единицу.
Перемещение у j ,0 до границы у0 может быть
определено исходя из выражения:
у 0 − у j ,0 = а1 х1 + Y * − (а1 + ∆а10, j ) ⋅ х1 + Y * ,
[
]
(4)
n
где Y * = ∑ аi ⋅ xi - неизменная часть выражения (2)
i=2
при изменении а1 .
Из выражения 4 следует, что искомый шаг коррекции положения гиперплоскости (2) определяется выражением
∆а10, j = ( у0 − у j ,0 ) / х1 ,
(5)
где верхний индекс у ∆а10, j означает, что расчеты
выполняются для класса ω 0 , для объекта с номером
j.
Выполнив расчеты по 5 по всем объектам класса ω 0 получаем массив каждый из элементов, которых
при
реализации
формулы
а1 = а1 + ∆а10, j
уменьшает ошибку классификации правила 2. Если
из полученных величин ∆а1 , выбрать максимальное значение и пересчитать параметр а1 по формуле а1 = а1 + ∆а10, j , рассматривая знак = как оператор
присваивания, то все отображения объектов класса
ω 0 окажутся, либо на границе у0 , либо правее нее.
То есть объекты класса ω 0 будут классифицироваться относительно границы у0 без ошибок.
При этом при следует иметь ввиду, что при изменении а1 на любой положительный шаг ∆а10, j
при х1 ≠ 0 отображения объектов класса ω l будут
перемещаться к границе у0 и возможно начнут
пересекать ее приводя к увеличению ошибок классификации. Величина шага, приводящая к ошибкам
классификации для объектов класса ω l может быть
рассчитана из 4 по формуле:
(6)
∆а1l, j = ( у1 − у j ,l ) / х1
Для выбора наилучшего, с точки зрения минимума ошибок классификации, шага ∆а1 для обоих
классов ω 0 и ω l произведем сортировку шагов
∆а1l, j и ∆а10 по возрастанию от меньшего шага к
большему. Если будут встречаться одинаковые значения шагов, то их расположения в новом массиве
∆а1 ,q будем производить произвольно, но при этом
каждый из новых элементов массива должен содержать информацию о том для какого из классов
он был рассчитан.
Ошибку классификации R(q ) будем рассчитывать исходя из следующего простого алгоритма.
Начальная ошибка классификации определяется количеством отображений объектов класса ω 0
«лежащих» слева от у 0 ( R( q ) = nω ) .
0
Далее при просмотре элементов массива ∆а1 ,q
от меньшего элемента ошибка будет корректироваться следующим образом.
Если встречается элемент из класса ω 0 , то
R( q ) = R( q ) − 1 , если из класса
ω l , то
R( q ) = R( q ) + 1 . Полученные величины ошибок
для каждого элемента q запоминаются и после
просмотра всего массива выбираем тот шаг + ∆а1 ,
который обеспечивает минимальную ошибку классификации.
Аналогично создается упорядоченный по возрастанию модулей массив отрицательных шагов
∆а1 ,q относительно левой разделяющей границы
ошибка сравнивается с величиной ошибки полученной для положительного шага и из пары шагов
+ ∆а1 и −∆а1 выбирается тот который обеспечивает
минимальную ошибку.
Аналогичная процедура проводится для всех
настраиваемых параметров с расчетом шагов по
формулам:
∆аil, j = ( у0 − у j ,l ) / хi
(7)
∆аi0, j = ( у 0 − у j ,0 ) / хi
(8)
− ∆а = ( у j ,l − у ) / хi
(9)
− ∆аi0, j = ( у j ,0 − у 0/ ) / хi
(10)
l
i,j
/
0
После перебора всех настраиваемых параметров, процедура расчетов может быть повторена с
а1 до аn с анализом величины ошибки классификации. Если при повторном переборе ошибка
уменьшается, то рекомендуется повторить перебор
всех аi до тех пор пока величина ошибки не перестает уменьшаться .
Описанный способ коррекции положения разделяющей поверхности с базовым уравнением вида
(2) реализуется алгоритмом блок, схема которого
приведена на рис. 2.
В реальных задачах классы ω 0 и ω l относительно начала координат могут располагаться, так
как показано на рисунке 1, а может быть и наоборот. Для придания свойств общности алгоритму
обозначим класс гистограмма которого располагается слева от оси Y через ω l , а справа – через ω r .
Для описания работы алгоритма введем несколько
дополнительных обозначений: t - идентификатор
знака у шага ∆a (t=1-для положительного шага,
t = 0 -для отрицательного шага); Rt ( q ) - количество ошибок совершаемых решающим правилам при
использовании корректирующего шага ∆а q с номером q с идентификатором знака t ; nr - количество
ошибок совершаемых решающим правилом (2) по
классу ω r для зафиксированного значения правой
границы у0 до начала этапа коррекции аi ; nl количество ошибок совершаемых решающим правилом (2) по классу ω l для фиксированного значения левой границы у 0/ до начала этапа коррекции
аi ; уlmax - координата правой границы гистограммы
у0′ . Для этого массива стартовая ошибка определя-
hω ; у rmin - координата левой границы гистограммы
ется количеством отображений класса ω l «лежащих» справа от у0′ ( R( q ) = nω ) . Далее при про-
hω ; Z - поправка для разделяющей границы по
l
смотре элементов массива | −∆а1,q | от меньшего
элемента, ошибка R(q ) корректируется следующим
образом. Если встречается элемент из класса
ω 0 R( q ) = R( q ) + 1 , если из класса ω l , то
R( q ) = R( q ) − 1 . После просмотра всего массива
выбирается тот шаг - ∆а1 ,q , который обеспечивает
минимальную ошибку классификации. Полученная
l
r
шкале Y ; ∆аt ( q ) - массивы поправок к настраиваемым параметрам с номером q и идентификатором знака t; Q1 - число элементов в отсортированном массиве для t = 1 ; Q2 - число элементов в отсортированном массиве для t = 0 ; f - количество
корректирующих действий по изменению положения гиперплоскости (2) в многомерном пространстве признаков с полным перебором всех аi ; R( f ) число ошибок после f корректирующих действий.
Н
1
i = 1; f = 1
2
Построение гистограмм hωl , hω r
3
В
Определение у lmax , у rmin ,
расчет у0 , у0′
4
Вычисление nr , nl
5
R1 (1) = n r ; R0 (1) = nl
6
Вычисление ∆аil, j ; ∆аir, j
− ∆аil, j ; − ∆аir, j
7
Сортировка корректирующих
шагов в массивы ∆аt (q )
8
9
1
1
10
11
1
17
0
t =1
1
∆ аt ( q ) ∈ ω r
12
R1 ( q ) = R1 ( q ) − 1
16
q = 1; t = 1
R1 ( q ) = R1 ( q ) + 1
∆аt (q ) ∈ ωl
14
R0 ( q ) = R0 ( q ) − 1
19
q = q +1
q ≤ Q1
0
1
Рис. 2. Схема алгоритма коррекции ЛРП
15
R0 ( q ) = R0 ( q + 1)
q = q +1
20
18
t = 0; q = 1
0
q ≤ Q0
0
А
А
21
R1 (q) > R0 ( q)
22
23
Выбор min R1 (q)
и ∆ai ; ai = ai + ∆ai
R ( f ) = min( R1(q ))
Выбор min R0 (q )
и − ∆ ai ; ai = ai − ∆ai
R ( f ) = min( R0 (q))
24
0
i = i +1
25
1
i ≤1
1
27
i = 1; f = f + 1
26
Повторить
коррекцию (2.5)
0
К
В
Рис. 2. Схема алгоритма коррекции ЛРП (Продолжение)
Предлагаемый алгоритм работает следующим
образом. Для корректировки выбирается первый
настраиваемый параметр и переменная определяющая количество корректировок всего правила 2
устанавливается в значении 1 (блок 1). В соответствии с рекомендациями п. 1 строятся гистограммы
hω и hω , по ним определяются правая граница
l
r
класса ω l и левая граница класса ω r с вычислением координат у0 = уlmax + Z и у 0′ = у rmin − Z (блок 2,
.., 4).
Относительно координаты у0 вычисляется
ошибка классификации для класса ω r − nr , а относительно границы у0′ - ошибки классификации nl
для класса ω l , которые присваиваются соответствующим переменным Rt ( q ) (блоки 4, 5). Далее для
всех объектов классов ω l и ω r по формулам 7, …,
10 по выбранным объектам обучающих выборок
определяется массив шагов по выбранному настраиваемому параметру.
С целью сокращения объема вычислений относительно границы у0 при определении ∆аi j из обучающей выборки можно исключить объекты класса
ω r отображающихся на Y правее у0 . Аналогично
могут быть исключены объекты класса ω l , отображающиеся левее у0 , поскольку их «перемещения» по оси Y при изменении аi будут только
улучшать качество классификации (блок 6).
Вычисленные значения шагов разделяются на
два массива (отдельно для t = 1 и t = 0 ) и сортируются в них по возрастанию элементов (блок 7).
Элементы массивов просматриваются от
меньшего к большему (блоки 9, 16, 17, 12, 20) с
вычислением величин ошибок для каждого из этих
элементов (блоки 11, 12, 14, 15).
Условия просмотров всех элементов двух анализируемых массивов отделяются блоками 17, 18,
20. После просмотра всех элементов обеих массивов из них выбираются те ∆аi j и −∆аi j , которые
дают минимальную ошибку классификации. Из
этих двух значений выбирается то, которое обеспечивает минимум ошибки (блоки 21, 22 и 23).
После этого осуществляется переход к следующему настраиваемому параметру и обеспечивается повторение работы алгоритма (блоки 24, 25).
Когда все настраиваемые параметры будут
скорректированы (блок 25) на основе анализа полученных ошибок и последнего варианта гистограмм hω и hω , принимается решение либо о преl
r
кращении коррекции (блок 26) или о повторной
коррекции настраиваемых параметров начиная с
первого (блок 26, 27).
Работа была выполнена в рамках реализации
федеральной целевой программы «Научные и научно-педагогические кадры инновационной России»
на 2009-2013 годы. Государственный контакт
№П424.
Литература
1. Горелик, А.Л. Методы распознавания [Текст] /
А.Л. Горелик, Скрипкин. М.: Высшая школа, 1984.258с.
2. Дуда, Р. Распознавание образов и анализ сцен.
[Текст] / Р.Дуда, П. Харт // М.: Мир, 1976.-511с.
3. Кореневский Н.А. Проектирование систем
принятия решений на нечетких сетевых моделях в
задачах медицинской диагностики и прогнозирования [Текст]: Н.А. Кореневский // Вестник новых
медицинских технологий, 2006. Т. XIII, №2. С.6-10.
Юго-Западный государственный университет, г. Курск
CORRECTION ALGORITHMS OF MULTIDIMENSIONAL LINEAR SEPARATING
SURFACE
E.B. Ryabkova, T.N. Govorukhina, N.A. Korenevsky
In the article the questions position correction of linear separating surface in many-dimensional space of characteristics with the purpose of improvement of quality classification in pattern recognition problems with the structure
classes, not satisfying the hypothesis of normal distribution
Key words: the theory of recognition, the line dividing the surface, customizable settings, error-ka classification,
multi-dimensional space of attributes
Документ
Категория
Без категории
Просмотров
5
Размер файла
256 Кб
Теги
коррекции, алгоритм, линейной, разделяющих, поверхности, многомерная
1/--страниц
Пожаловаться на содержимое документа