Файл: Журавлёв, Ю. И. Алгоритмы вычисления оценок и их применение [монография].pdf

меры

функций

/'(w5,

):

а)

/-(ш5, ю5? )

1,

если ш5 ~

ш5? ,

О,

если ш5 =j=шSq.

В этом примере-части строк считаются

похожими, если

они

совпадают:

б)

пусть

о5 = (<*,,

*)■

=

(Pi - Ра > - - Л )

И £I >“2 '

'к •

положительные'

числа.

'Обозначим через о (5,

5

)

число

невы­

полненных неравенств-

3

I

Jk

^

=V

■1I

Тогда можно принять,

что

г

1, если О(5,

5 9) <

з,

О, если р (5,

5 ? ) > е.

' ■ В 'данном случае-похожими

Считаются

части строк,- если

по

крайней мере k—е координат у них достаточно близки.

3.

Вычисление оценки

по строкам

фиксированного опорно­

го множества. На-третьем этапе

нахождения

алгоритма

А

за­

дается

числовая

характеристика,

называемая

оценкой.

Оценка

ленных на строках исходной, таблицы

Тпт1.

Например,

таким

внешним параметром-может быть

„степень важности"

или пред­

ставительности строки

5 . ■■

'

Пусть на строках

таблицы

Тпт[ заданы

параметры

(5 ) ,

Тогда оценка записывается в виде

^q \ ~ f [ Tf {-Sq ')>Т-2

’

Т; (S,

}, f (“5,

ш50 )].

шГ(S, Sfl) = г(ш5,

w-Sj;

б) задан внешний параметр

) — степень важности строки

S q, тогда

“ Г (5 >

)

= Ъ (5<?)

’ Г(

);

в)

кроме

параметра

f, (5? )

задан

параметр

Т з ) ~ ~ степень

достоверности S q ,

тогда

“ Г (i,. s , )

=

Y,(S,)-;! ( s e) r P s , ; s , ) .

В приведенных выше примерах для шГ (S,

выбраны

про­

стые зависимости. В принципе

возможно

построение

алгоритмов

с более сложными

способами

задания шГ (5, S q

однако

в дан­

ной работе более сложные зависимости

анализироваться

не

бу­

дут.

Вычисление оценки для класса

по фиксированному опор­

4.

ному множеству. Для простоты обозначений рассмотрим оценку

для класса К\ , в которую

входят строки

У,

, S , ,

, S

табли-

ЦЬ‘ ТптГ

Пусть вычислены величины шГ (5, 5,

),

шГ (5, S2 ),..., шГ(5,5т ) .

Оценкой для

класса

будем считать функцию

■I*&

[S. S: )■ “Г (S, 52 ),

... , шГ (5,

Г,

( ш).

Опишем примеры функций 6:

а)

/~\

т ‘

~

Г, W = 2 » r ( S , S , ) ;

q=l

б)

1,

если

^

шГ

(S,

) >

г,

9=1

г — заданный

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

здесь

параметр.

5.

Оценка для класса

1(и

по системе

опорных множеств.

Рассмотрим

систему опорных

множеств

9Д. Согласно п.

4 для

а)

Г . С Т -

2

Г .С 1;

М А

.6),

пусть для

каждого элемента

множества

из

задана чис­

ловая

функция

Г „ (5 ) -

^

Л1^_6‘2д

U)

Функция «

может

задавать,

например,

степень

BLaжнocти

(представительности)

опорного

множества М-

)

которая может

v v

/

г

быть,

например,

пропорциональна

числу элементов.

по опорной

системе

множеств и

строке вычислены

величины

Г, ( Я Г, ( Я

... , Г; ( Я

Решающее

правило алгоритма

представ­

функции /-'есть 0, 1, 2, ...

, /.

то строка 5 клас­

Если F

[Г, ( Я Г , (5),...

Г, (5)] = н, 1

сифицируется как строка,

принадлежащая

классу

Ки .

Если /-'[Г, (5),

Г, ( Я ..., Г;(5)]

= 0, то

алгоритм

не определя­

ет класс, к которому следует отнести строку S.

Примеры решающих правилТ

1)

и, если Г„ -

Г. > о ь

F [Г, ( Я

Г2 (S).......Г, (5)]

при У ==",

1

<У < /.

О,

во всех

остальных случаях;

|

1Т

/

и, если,

2) F [Г, (5), Г, ( Я

Г, (S)] =

2 Т „ / У г ; >

3-

/=*

О, если хотя бы одно

из ус­

ловий 1°, 2° не выполнено;

Оценки Г,Дш) и Гн(5) назовем числом голосов,

поданных

за

класс Ки , (и — 1,

2, ... , /) по фиксированному опорному

множе­

ству и по системе

опорных множеств соответственно.

Дадим интерпретацию описанных выше этапов,

применитель­

но к задаче распознавания образов.

первого

5, , S2 ,..., St

Пусть заданы

объекты двух

классов:

и второго

, с-2 , ... ,

ог . Каждый из объектов характеризуется

набором

значений

п

бинарных

признаков. Требуется

отнести

предъявленную строку S длины п к одному из классов.

Зададим длину

опорного множества «>,

равную k и

выделим

все наборы столбцов длины k (предполагается, что

все множест­

во объектов с п признаками сведено в таблицу

Тп т2).

Берем

первый

по порядку набор, составленный

из столбцов с

ш мерами

1, 2,...,

к,

В предъявленной

строке и строках 5, ,S2, ...

..., St ; а,

, з ,, ... ,

аг

выделим

только

первые

к

столбцов

(это

приводит к потере

информативности

заданных

описаний). Полу­

ченные после такой операции строки

обозначим

через SX, S 2,...

..., St ; з, , з,

,..., зг ; 5 . Обозначим

через

Г|

2...... ь

число строк

из S , , S.2 ,...,

5 1 ,

совпадающих

с

S , а через

ГД 2....k — число

строк из j , , з., ,..., зг , тоже совпадающих с5

.

Построим

вели­

чины Г‘(,

, ^ . 1 - I' ,2........ Я для

всех

наборов

й,

... , г‘Л

длины k (эги величины соответствуют оценкам Г,(ш) и Г2 (ш),

вве­

денным в п. 4 ).

величины

Теперь, естественно,

Г, (5) =

‘а

и

Г, (S) =

являющиеся оценками, полученными

по всем

наборам длины /г,

назвать ‘ целом голосов,

поданных

строкой

5

соответственно за

Кроме того,

npai ило отнесения

может быть построено

с по­

мощью рассмотрения удельного числа голосов.

Например,

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

Г (S)

Г

пазо-

величины —f— и ■~г '