Исследование и синтез эффективных алгоритмов вычисления оценок для задач распознавания и прогнозирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ Г€1СР ПО ДЕЛАМ НАУКИ И

ВЫСШЕЙ ШКОЛЫ

МОСКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ФШИКО-ТЕХШЧЕСКИИ ИНСТИТУТ

На правах рукописи УКД 519.714

ХИЛКОВ Андрей Владимирович

ИССЛЕДОВАНИЕ И СИНТЕЗ ЭФФЕКТИВНЫХ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ ОЦЕНОК ДЯЯ ЗАДАЧ РАСПОЗНАВАНИЯ И ПРОГНОЗИРОВАНИЯ

Специальность 01.01.09. - математическая кибернетика

Автореферат диссертации на сбискание ученой степени кандидата физико-математических наук.

МОСКВА - 1991

РяОота выполнена в Московском физико-техническом институте Научнвй руководитель : член-корреспондент АН СССР,

профессор 10.И. Журавлев

Официальные оппонента: доктор технических наук,

профессор Г.Д. Фролов кандидат физико-математических наук И.Т. Кадощук

Ведущая организация: Научно-исследовательский институт системных исследований АН СССР

Защита состоится "_"_1991 в _ час. _мин. на

васедании специализированного совете К.063.91.03 в Московском ордена трудового красного знамени физико-техническом институте по адресу: 141700 г.Долгопрудный, Московская обл., Институтский нер., д.9.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института.

Автореферат разослан **_"_1991

Ученый секретарь специализированного совета доктор физико-математических наук

А.И.Самшювский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

^Актуальность темы. В данной работе рассмотрена модель алгоритма типа вычисления оценок1. Конкретный алгоритм А определяется выбором системы оиорннх мноаэств 0д, функции близости В(ш,5,5'), весов признаков р^,р2,..., весов объектов обучающей информации 7(Б1),7(32),..и решающего правила. Оценка принадлежности объекта Б классу с номором J обычно вычисляется следующим образом.Распознаваема объект срав!швается с множеством эталонных, которые принадлежат данному классу, по всем подмножествам признаков (опорным множествам) из системы опорных подмножеств Пд . Если близость по некоторой совокупности признаков имеет место с объектом , то оценка принадлежности увеличивается на произведение веса этой совокупности не вес этого объекта обучающей информации. Оценка нормируется и усредняется по числу эталонных объектов, принадлежащих классу К^.

Эффективность работы алгоритма существенно зависит от возможности вычисления оценки принадлежности данного объекта каждому из классов К| , К^,...', К1 . Поэтому обычно используется переход от суммирования по отдельным множествам, принадлежащим системе опорных множеств алгоритма, к сложению количеств вхождения в данные множества (ври условии, что значение функции близости равно единице) для каждого признака, характеризующего объект.

1 Журавлев Ю.й. Об алгебраическом подходе к решению згдач распознавания и классификации.// Проблемы кибернетики. - М.: Наука, I978 г. - Был.33. - с.5-68.

Получены свертки для эф|вктивного вычисления оценок в

соотрчтствущем алгоритме для некоторых систем опорных *

множеств (для системы всех подмножеств мовдости к множества признаков, для системы всех непустых подмножеств множества признаков и др.) и доказано2, что при использовании пороговой функции.близости , значение которой определяется лишь числом выполненных и невыполненных неравенств вида е^ ,./=1,... ,Н, выражение для сверток принимает не более двух значений, если - это множество ■ всех непустых подмножеств т=С1,2.....ы).

В некоторых случаях известны признаки (или совокупности признаков), которые следует учитывать. Эти подмножества могут иметь произвольную конфигурацию. Тогда составляется ортогональная ДНФ характеристической функции3. Каждый интервал, соответствующий элементарной конъюнкции, рассматривается отдельно, после чего результаты суммируются. Однако, этот подход часто дает сложные формулы, ток как ортогональная ДНФ получается длинной. Поэтому получение эффективных сверток для новых систем опорных множеств делает возможным построение новых алгоритмов вычисления оценок.

Целью работы является исследование "и синтез новых эффективных алгоритмов вычисления оценок . для задач

2Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации.// Проблема кибернетики. - М.: Наука, 1978 г. - Вып.33. - с.5-68.

3Гуревич И.В., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания. // К'л^ернетнка. -1974г. -ИЗ. - с.16-20.

распознавания и прогнозирования.

Научная новизна. Автором получены аффективные формулы вычисления оценок для алгоритмов н которых характеристические функции опорных множеств ' являются логическими суммами хвммингойых шаров. Для этого впервые введено понятие атомарного множества и исследованы свойства таких множеств. Результаты распространены на случай задач с неполной информацией.

Исследована задача оптимизации по радиусам хемминговых шаров, соответствующих система опорных множеств. На основании указанных результатов сконструирован программный комплекс, реализованный на ПЭВМ PC AT/XT.

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

Публикации и апробация работы. Основные результаты диссертации докладывались на XXIV Научной конференции МФТИ (1990г.) и опубликованы в работах /1,2/.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложения, изложенных на 103 страницах машинописного текста, содержит

а

14 таблиц и 2 рисунка. Библиография включает 45 наименований.

Автор гшрпжвет глубокую признательность чл.-корр. АН в

СССР Журпьлеву Ю.И. за руководство и постоянное внимание в процесса работы над диссертацией.

СОДЕИШШЕ РАБОТЫ

Во введеыш содержится краткий обзор литературы, посвященной теории распознавания образов и методам распознавания. Обоснована актуальность темы диссертации и изложены основное результата работа.

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

Рассматривается модель алгоритма распознавания типа вычисления оценок. Объекты, подлежащие классификации, описываются некоторой совокупностью числовых признаков. Описания объектов, то есть числовые векторы, принадлежат множеству Р с •-•где Р{ - область определения

4-го признака с метрикой р{ , 1= I, 2.....и.

Существует покрытие атого множества:

г

К»* 1= 1, 2,. »..,1 - Р ~ и Кг .

1 1=1 1

Подмножества Кр ^....»Кг называются классами. Они заданы лишь частично, то есть известны описания объектов Б^, ...

Зт и, соответствующий каждому данному описанию информационный вектор оЦЗр = ( а|(8(), о^^),..., а^Б^) , где a.j{S^) равно единице, если объект с номером I принадлежит классу К^ , нулю,, если не принадлежит , Л - если отсутствует информация о принадлежности этого объекта данному классу. Такая информация называется обучающей.

Конкретный алгоритм А определяется выбором системы опорных множеств Ад , функции близости В( и,Б,Б'), весов признаков Pj.P2.---.Pjj . весов объектов обучающей информации 7(82.....7<Бд) и решающего правила.

Система опорных множеств Пд - 8то некоторое множество подмножеств N={1,2,..., N ). Пусть О е Пд , тогда и = ((<>]. ... ,(0^), в котором «¿=1 при £ с О И 0 при I £ П, называется характеристическим вектором, соответствующим множеству П.

Пусть 81=(а1,а2,....а^), Б^ф^.Ъ^.....&ы) - описания

объектов, принадлежащих Р; П-((...,1р) - опорное мно-

жа ст

:'во; фиксированы целое число О и вектор ^.ед,. ,ен) , где е( 5 0, I, 2,...,г? . Тогда

если в системе неравенств р. (а, , Ъ, ) Се,

Ч 11 11 Н

В( и, Бр Э2) =

О

V < %

V ' %

не выпоре но не более

В6НСТВ,

в противном случае.

е° нера-

Каждому признаку I с ш приписывается неотрицательное число р{,£=Г,2,...- вес признака. Вес опорного множества

С1-И *• • • определяется следующим образом:

у

р(и)=р11+Р(2+...+р{л . ;

Каждому объекту обучающей информации приписывается число 7(5() - вес объекта или его информационная ценность.

Пусть - множество описаний объектов обучающей

информации, принадлежащих J-v^y классу, J=l,2,...,l . Тогда эценка принадлежности объекта Б классу с номером } вычисляется следующим образом:

1уЗ)= с-

I

]Г 7(5')* ]Г Р( V )'в( «.Б,Б').

V?,

и<-»П <Е о.

г

где С - нормирующий 'множитель.

Во второй главе выводятся формулы начисления оценок для алгоритма распознавания с системой опорных множеств, являющейся объединением хэммингових адров. В § 2.1 вводится определение атомарного опорного множества на булевом кубе

А( И0; Яр ( Мр М2, &,);...;( ку))

V

Нт и Ял и ( и Ы( ), 1 и £ = I 1

М£ П М^ = Н{ П К0 = М{ П Иг = Ы0 П Иг - 0,

I * (=1,2.....V, ¿=1,2,...,и.

Какдому подмножеству М{ соответствует, целое число к(,

г - I, г,..., V , о < гг( ч | м( |.

Двоичный'набор х принадлежит данному атомарному множеству тогда и только тогда, когда х{ = О если I < I если { с

£ xt = kt , } = I,

и.

t € Hj

Теорема I. Справедлива формула вычисления оценок для атомарного множества Пд = A(U0;Iij; ( Mj, Mo, fo,

. . • ■ ( Му, Îiy ) )

N

г/ s > - с • T-jT ' I 7( s>)- I pi'Qt( s' s,)"

J S' € Vj i = I

Если t ( Kj, то Û{( S, S') - 8To выражение " e° k в0

Q( Щ. I) = У ГТ с u • cV ^

4 Л i d( v d(V £

: I < евф- < 1 >

и " I

0 * * тц ~ d( V' ки - d( Mu> 15 fiu «Vй"1'

Если / < Мр, I « р < V, то при 'öt<S,S') = I Qt(S,S')

это вирак&ние

К - eR JL рО ь _ Е0

<,<„,. I) . ГТ с • с Ч

1 (if М 1 1 1 я - .......

s

d< М_) i i га - d( ML) d(lL) 0 P u = I u u

: Y. e« ^ (2 >

u = I

О * mu - ci( Mu), eQp * kp - I, ' ku ~ d< V $ eu ku• u = *> 2.....u-

а при 0{( S, S'> =0 :

6P ГТ А" Eu

" О ь oO

Q( Wj, I) = V -—-- ПС*« 1

1 m - d( M_) ci< M,.) d(M )

~0p P ц = r ^ ^ u

v

: I 62 < <3 >

u = Г

0 < eu < "u - Mu), ej >Л,

Оценивается число слагаемых о. в формулах (I) - (3):

V

Sj

z

и - I

e

tL !$ S С

Зф J

U~ 1 ' + « - I

- а -

В § 2.2 рассматриваются два случая, когда объекты считаются "близкими" по опорному множеству О = { ¡2,...

____ } - при выполнении а) всех неравенств и б) всех,

кроме, быть мокет, одного неравенства вида

р. { а, , Ъ, ) «г>е, ,

Ч 11 Н ' 11 р, { а. , Ъ. ) 4 в, ,

Для этих случаев выводятся формулы вычисления оценок.

В § 2.3 вводится понятие сектора, то есть пересечения сферы Хэмминга и слоя N-мерного булева куба. Доказано, что каждый сектор является атомарным множеством. Следовательно сфера лредстввима как объединение непересекающихся атомарных множеств.

Разложение шара Хэмминга на атомарные множества сводится к последовательному разложению его сфер. Очевидно, что никакие два сектора шара, даже принадлежащие одному слою, не пересекаются.

Если шары, принадлежащие система опорных множеств, пересекаются, то выводится формула вычисления оценок для системы опорных множеств, являющейся пересечением двух или более шаров одновременно

ГЬ + ** й

ху Б, Од) . £ I £ Г,( Б. А{) + ... ,

Л £ = 1

к £

... -I )Р"1. X! 5 (3'А(1П п А1

вр-1 р I вр

... и -I >т"1

к

£ ^ (3,А{ П ... Л Аг ).

Здесь секторы в слое к нумеруются следующим образом: I, 2...., 11 - принадлежащие 1-му шару, 1^1,..., ~

2-му, и так далее.

Пусть секторы А^, А^,..., А{ принадлежат слою к и,

соответственно , шарам с центрами а^, а^,....я^. Если да^ишй слой пересекается не с каждым шаром, то, очевидно, ор не содержит ни одного двоичного набора о-, принадлежащего каадому шару, значит такие слои просто не рассматриваются.

т ~

Тогда М^ = С ,/ | J-я координата вектора а( равна единице }, = ш \ н], I = I, г,..., т.■ Для этих блоков" известны к^ и *0

Рассмотрим множества

, р - ( рр р2.....< {0,1), ( » I. 2.....т.

Рт Ро

II 1 (1 и

= М/ П Но П ... п м,

т

I " "2 «т

н

Пересечение секторов А{ А^ может быть

разложено в сумму атомарных множеств

А(( —;( Ю).

0 0 II

где 0 ^ ^ I М~| и

Р Р

у = к.

Р € ¡Ет

X:

.....

В этой системе из я +■ I независимых уравнений имеется

2т переменных. Каждое решение данной системы определяет

одно атомарное множество, и если С |М~! шш = 0, то

Р Р Р

М~ является подмнохеством N2 или соответственно.

Объединение этих атомарных множеств есть общая часть секторов Л. , А, .....А, .

1 :1 2 „ 5

Пусть а^, а^,-.., а^ - центры шаров В1, В,,..., Ви н булевом кубе еи, {а{1 = р, =0, I * У, I £ 1,5 А т.

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

2

Г,( Б, 0А) « т • 3, В1) - Ст . 2, В1 П В2) +...

<-1>""1' <С " В1 П П «V-

Разделим шары на секторы 5( (, Л, р) (I - номер шара, к - номер слоя, р - радиус сферы, в которых содержится данный сектор); другое обозначение того же сектора -

А(< М(, (К + р - р()/ 2);( и Ч (к - р + р4)/ 2)), где М£ = С 5 | ./-л координата вектора аг равна единице ). Тогда пересечение I шаров можно разложить на пересечение их секторов:

Р+Гг ,

ВТП...П В, = и и (Sd.fe.pf) П...Л 5(1,к,р,) . (I)

1 1 Й=0[ 0<Р(«Г 1 '

1=1,2,

Заметим, что пересечение в квадратных скобках не пусто тогда и только тогда, когда р = (р1,р2,...,р{) удовлетворяет условиям: к + р - р{ - четное положительное

число, £ = 1,2.....г и

г

ь + р - Р{

{= I

I

2

> к.

Если же условия нарушаются, то в объединение ( I ) вместо данного слагаемого берется 0 , в противном случав слагаемое является атомарным множеством

Л(( мт, (Ир - рг)/ 2);...;( мг, (Л + р - рг>/ 2);

I г

( N \ и 11(, к - - р + р£)/ 2)).

£ = I

Оценка по системе опорш.'х множеств и В^ В^

легко вычисляется

ПА) = и . В1) -р + г г

- X [ ' X ^) П Sn.fc.p2) * ...

й = О ррр2=0 г

... + <-1)п-*. <£ . £ (Б(1,А,Р1) П ... П 3(1,Л,рт)|. Рр.-.-.р^О

В § 2.4 выводится формула вычисления оценок для система опорных множеств, являющейся шаром Хэмминга:

г ( Б ) = С • -I— . У 7< 3')«

* I И/1 £-

n

X

Р1 ■ 0( ы^ ) • бг< Б, з1). а{ +

£ = I

+ Рг • оаф • ) . а{ + Р1 ' О(М^) • в^.Э') • *

+ Рг • 0( ) • б,( Б, Б') . а{

где

I „I л0 „О

I

1 I I - I I I М? I I

Р

р I м0 I - Ро - Ро € р[ + Р1 + Ро + Ро $ г:

I

Г I М1 I I мо1 - 1 I Щ I I «о1

Р

р : I «о I - Ро - Ро € е°- ?! + р] * Ро + Ро « г:

С3( м| ) = Г ср1 г . сро 1 . ср° п1 . сР° 0 , Г I М1 I I мо' I *1 I - 1 I но1

Р : I м0 I - Ро - Ро < р] + р? + Ро + Ро < г;

а( „I ) = у ср1 х . т - Ср? . ср° I1 ,

1 {г I М1 I I *о! ' ' I I мо'

р

™ т тпп т т о л

Р • I % I - Ро - Ро < е » Р1 * р| + Ро 4 Ро <

В § 2.Б рассматривается алгоритм вычисления оценок с неполной информацией. Описания объектов распознавания принадлежат множеству Р с <Р^и Ш)« (Р2и С А })»...■ (Р^и С Л}), где Р{ - область определения 1-го признака с метрикой р{;

Пд - система опорных множеств. Пусть ,Ор.....а^),

••~ описания объектов из Р,

П=Пр12> •••) - опорное множество , фиксированы целые

положительные числа е^, <р и дгэйстьителнп;й вектор ( Ер е3,..., ем), £г ? О, 1= I, 2,...,кт. Тогда

всы^^) =

I если в системе норгвенств •

р, (а, . Ь, ) £ е, ,

р< (а, , ь< ) < б, .

12 °

р, (а, , Ь{ ) $ е,

.0 .....

не выполнено не более е неравенств, и не определено не более О в противном случае.

Теорема 2 . Справедлива формула вычисления оценок для атомарного множества А(Н[);М1; (М1,й1); (М2.?г2)..; ).

Б ) = С

Ь-1 "»( з-). [£ рга(н1) +

; 3' £ I (

+ X X р«,сз< мгл> + X! X р1,<3( 1] +

4=1 ( € мг в((Б.5')=Л

1 = 1 е с и,

с^б.б'ы

I I 0)]

£ = i i € м^

с^б.б' )=0

где

N. ) = V ГТ оЧ . . с"" " ~ !/"

..... Ь 1 \ е< м„> <»( мц)

л., - е? -

и = i

и = i

0 « £ц < иц - V' 0 < Яи < Ж. ми),

~ l-i -

' Мц) « eg + 9Й < V- u= Г- 2.....«•

Q( Mp, I) = £

d( M_>

"0 ~0 p q .ь

.0 „0

Q(

. TT cE" . a9« . CÄ" ~ ~ \

1 i e( ыи> g(Mu) cî( Mu)

& £u 1 V e2 < е8ф • Z qu < •

u = I u = I

0 < « Шц - d( Mu), 0 < Í q( Mu),

- cJ( Mu) < + « hu., и = I, 2..... V,

E° » a

« o) « У —— • ГГ cE" . oq« -

P /L e{ к ) 1 1 e( Ы ) <j(M )

~0 ~0 P u = I u u

4

» С

te - p0 -Ги u ^u

d( V

и - I u = I

0 « tj] < Пц - d( Mu), 0 < S q( ии),

йц - d(.Mu) < e° + ku., u = I, 2.....v. e° > I.

Í Л a?

Л

CJ< N_, A), = У - • ГТ С u . С'

P q( M_) i 1 e( M ) q(ll )

™€t~0 P u=I

fe - e° - a° „ eu

. <*<Ии)

и

ви: Е 4 < езф - £

и = I и = I

0 * 5 '"и - *и>-° « * V-

Аи " <3( V * еи + ^ V* и = 2..... ^р ?

В § 2.6 рассматривается случай» когда объекты считаются "близкими" по опорному множеству О = { , ..., > при выполнении всех неравенств вида

р< (о, , Ь. ) < е, , Ч Н 1111

Р, (а, , £>, ) « Е, 1к 1к 1к

кроме, быть может, двух неравенств - одного неопределенного и

одного невыполненного. Для этого случая выводятся формулы

вычисления оценок.

В § 2.7 рассмотрен алгоритм с модифицированной функцией

близости:

В( и, 5, Б') = V б(( 3, Б").

г«

С € П «-»'О)

Система опорных множеств Од - втумарноа множество А( К0; ( Мх, й1); ( М2, ( Ьу)).

/г^ / | | - это аналог веса каждого признака, номер которого принадлежит М^.

В третьей главе поставлена задача поиска экстремального алгоритма вычисления оценок, система опорных "Множеств которого представляется объединением хэмминговых шаров с фиксированными центрами , радиусы которых являются параметрами алгоритма.

Алгоритмы выбора начальных значений центров предложены в .

§ 3.1.

Первый . использует метод, аналогичный методу

покоординатного спуска , для минимизации функционала "обобщенной" ошибки на мнокестве алгоритмов вычисления оценок по значениям радиусов в пределах , определяемых из задачи линейного программирования:

niax( ri + +___+ г^),

1rt + rj < И ai e>ä.j 5, г{ > О, I ^ t < J < t.

Второй способ более прост: определяется оптимальный относительно выбранного функционала радиус шара для каждого фкШсированвого центра. Причем этот радиус не превышает заданного максимального.

В § 3.2 изложен алгоритм нахождения локально-оптимальной конфигурации системы опорных множеств.

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

Пусть классы Kj,K2,...,Kj на пересекаются. Положим Fj+( St) = Sj | учитываются не более чем двойные пересечения); ^ ry~( St) = S^ | учитываются не более чем тройные пересечения хэмминговых шаров). Эти значения позволяют оценить принадлежность объекта S классу с покором

J, используя следующее решающее правило:

I если гу< Sl) > r^i S1), w t J. Л ( то есть отказ от классификации ) если Qß sJ) = найдется w :

ГSl) < Гш+( Sl) < VjU S() .

О если C2 > S ).

В 5 3.3 изложен способ выбора центров шаров (если они не заданы экспертом) на базе информационных весов признаков, полученных из других алгоритмов распознавания.

В четвертой главе содержится опипние комплекса программ и описывается решение (с использованием атого алгоритма) задачи анализа тахосцилографических кривых для выявления характеристик нормы и патологии сосудов.

Приложение содерхит таблицы результатов обработки.

Основные результата диссертации изложены в следующих работах:

1. Хияков A.B. Формулы вычислеаля оценок для алгоритмов распознавания с опорными множествами.// Журнал вычисл. матем. и матем. физики. -1989 г. -T.29.N Ю.- с. J565-I57I.

2. XiiJKJB A.B. Формулы вычисления оценок для алгоритмов распознавания с системой опорных множеств, являющейся атомарной.// Моделирование процессов обработки информации и управления: междувед. cö. М.: МФТИ, 1990 г.

с.83-07.

Ротапринт МОТИ. Зак. тир.100 29.9.91