[МРО] Методичка МРО

Т а б л и ц а 1.7

Таблица знаков

Номер

Образ

Номер плоскости

Т

II

IV

VI

VII

У

точки

Знак

точки

1

А

1

1

1

1

2

В

0

0

1

0

3

А

1

1

1

0

Н

4

С

0

1

0 1

5

С

0

й

0

1

1

Б

6

В

0

0

1

0

7

С

0

0

0

1

8

В

р

1

1

1

0

9

С

0

1

0

1

и

10

А

0

1

1

0

В этой таблице ес ь п лн стью совпадающие строки. Это

и

означает, что в пр с ранстве рецепторов есть многогранники,

содержащ е более чемоднуточку (см. рис. 1.14). Такие много-

гранники могли появться уже в первой части алгоритма, а после

чно

выбрасыван я плоскостей число их могло еще более возрасти.

Между тем для обозначения

каждого многогранника вполне

п

д стат здной точки. «Лишние» точки (т. е. «лишние» строки

таблицы знак в) можно исключить из памяти машины. Поэтому

е

роверки возможности исключить последний столбец

осле

Р

машина

ереходит к исключению лишних строк. Для этого все

Таблица знаков

Т

Номер

Образ

Номер плоскости

У

II

IV

VI

VII

точки

Н

Знак точки

1

А

1

1

Б

1

1

2

В

0

0

1

0

3

А

1

1

1

0

4

С

0

й

0

1

1

7

С

0

0

0

1

8

В

и

1

1

1

0

10

А

0

1

1

0

р

одной плоскос , за другойем

и т. д. Рассмотрим плоскость II

Исключение лишних кусков плоскостей

Ранее

т

сначала выбрасывать лишние

куски

мы условились

ками

з

(см. рис. 1.11). Л шн ми ее кусками являются границы между

многогранн

2 M , 3 и 10, 4 и N. Если выбросить эти

границы,

дн именные многогранники 3 и 10 будут объединены

в дну

бласть пространства,

многогранник M подсоединен к

мн г граннику2, амногограникN – кмногограннику4.

е

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

Р

кодами именованных многогранников. Цифры этих кодов

пуказывают,

по какую сторону от каждой плоскости лежит

многогранник и все заключенные в нем точки пространства.

Многогранники, разделенные только одним куском одной

плоскости, имеют коды, отличающиеся только одним

разрядом, причем этот разряд соответствует разделяющей их

плоскости. Это легко проследить по рис. 1.14 и табл. 1.8 на

примере многогранников 3 и 10, 10 и 8, 8 и 4, 4 и 7.

Забежим вперед и рассмотрим работу машины при распоз-

наванииновыхобъектов. Припоявленииновогообъектамашина,

очевидно, должна вычислить его знаки относительно всех плос-

Н

костей и сравнить полученный код со всеми строками таблицыУ

знаков. Если точка, соответствующая новому объекту, попадет,

например, в многогранник 2, ее код совпадает со второйТстрокой

Б

таблицы знаков и объект будет отнесен к образу В. Объект, точка

которого попадет в присоединенный к образу В многогранник M,

т. е. будет иметь код, отличающийся от кода многогранника 2

первым (соответствующим плоскости II) разрядом, также должен

ками

быть отнесен к образу В. Иными словами, выбрасывание куска

плоскости

II между

многогранн

2 и M эквивалентно

р

утверждению, что первый аз яд кодайвторого многогранника не

является существенным и может не учитываться при распоз-

ором

навании новых объект в. Д статочно совпадения остальных раз-

бъект

был тнесенкобразуВ.

рядовкода, чтобы

Выбрасывание

всех указанных выше кусков плоскости II

и

столбце таблицы знаков оказываются

означает, что во в

з

несущественными ц фры, лежащие в 2, 3, 4, 7 и 10-й строках.

Цифры 1-й 8-й строк – существенны, так как соответствующие

о

восьмой многогранники относятся к разным обра-

им первый

зам и ра деляющий их кусок плоскости II (см. рис. 14) выбросить

п

нельзя. Нев зможность исключения плоскости II видна и из

табл. 1.8. Если исключить из нее второй столбец, то относящиеся

Р

к разным образам многогранники 1 и 8 будут иметь одинаковые

коды, что, безусловно, недопустимо.

Из сказанного ясно, что выбрасывание лишних кусков

еплоскостей сводится к составлению таблицы существенных и

несущественных

разрядов для всех

строк таблицы знаков.

23

Н

таблице знаков, т. е. в сравнении остальных разрядов первойУ

строки с соответствующими разрядами других строк. Если про-

тиворечие, т. е. совпадение строк, относящихся к разнымТоб-

Б

разам, не найдено, машина переходит ко второй строке первого

столбца таблицы разрядов и заносит в нее единицу. Если

противоречие существует, перед переходом ко второй строке

единица в первой строке заменяется нулем. Затем машина возоб-

таблице

знаков и расстановку

новляет поиск противоречий в

нулейиединицвтаблице

.

йпоследующим

разрядов

столбцам

После перехода ко вто ому

каждая из двух сравниваемых

данный момент строк может

иметь несущественные (т. е. уже отмеченные единицами в

т

таблице разрядов) разряды. Поэтому сравнение ведется

только по разрядам,

дн временно существенным для обеих

и

сравниваемых с роко.

заполнен

я последней строки в последнем столбце

После

таблица ра рядов пр мет вид табл. 1.9.

о

Т а б л и ц а 1.9

Таблица разрядов

Номер

Номер плоскости

II

VI

VII

Р

пточки

Образ

IV

Разряд точки

е

1

2

3

4

5

6

18

А

0

1

0

0

24

Окончание табл. 1.19

4

1

2

3

5

6

2

В

1

0

1

0

3

А

1

0

1

0

4

С

1

1

0

0

У

7

С

1

1

0

0

8

В

0

1

0

Т

0

10

А

1

0

1

0

После заполнения таблицы разрядов в таблице знаков могут

оказаться строки, отличающиеся только несущественными раз-

рядами (т. е. совпадающие по существенным разрядам). Таким

строкам будут соответствовать полностью одинаковыеНстроки

й

таблицы разрядов. В нашем случае это строки 3 и 10, а также 4 и

7. Очевидно,

из каждой группы

сходныхБстрок

могут быть

и

исключены все строки, кроме одной, что и производится после

заполнения таблицы разрядов, но по ск совпадающих строк

здесь производится только по существенным разрядам. В нашем

о

случае из таблиц исключаются 3-я 4-я строки. Обе таблицы в

окончательном варианте п инимают вид табл. 1.10 и 1.11. Про-

т

р

цессобучениязакончен.

Т а б л и ц а 1.10

з

Таблица знаков

и

Н мер

Номер плоскости

Образ

II

IV

VI

VII

п

т чки

Знак точки

е

о1

А

1

1

1

1

Р

2

В

0

0

1

0

7

С

0

0

0

1

8

В

0

1

1

1

10

А

0

1

1

0

25

Т а б л и ц а 1.11

Таблица разрядов

Номер

Образ

Номер плоскости

II

IV

VI

VII

точки

Разряд точки

У

1

А

0

1

0

0

2

В

1

0

1

Т

0

7

С

1

1

0

0

8

В

0

1

0

0

10

А

1

0

1

0

Все пространство разбито на три области, соответствующие

образам А, В и С (см. рис. 1.15). В том, что разбиениемНохвачено

действительновсепространство, ивнемнеосталось«пустых» не

поименованныхобластей, можноубедитьсяБследующимобразом.

и

Перебрав все возможные четырехзначные коды от 0000 до 1111,

можно удостовериться в том, чтолюбой из этих кодов по

существенным разрядам совпадет с

одной

из строк

таблицы

знаков (см. табл.

о

означает,

что любая точка в

1.10). А это

пространстве рецепт р в п падет в одну из трех поименованных

вуют

областей, т. е. ч о

рассматриваемомр

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

областиотсутс

.

з

строками

Распознавание новых объектов

При предъявлениии

нового объекта машина вычисляет его

п

тн сительно всех плоскостей и полученный код поо-

знаки

чередно сравнивает по существенным разрядам со всеми

е

таблицы знаков (табл. 1.10). При совпадении строк

Р

машина относит новый объект к соответствующему образу.

26

Способы повышения надежности распознавания

Секущие плоскости проводятся случайно и независимо

друг от друга. Поэтому, если провести обучение несколько

раз на одном и том же материале (т. е. осуществить несколько

вариантов обучения), будет весьма маловероятным, что

ошибки в разбиении пространства рецепторов окажутся оди-

наковыми во всех вариантах. Следует ожидать, что в каждом

из вариантов машина будет ошибаться по-разному. Это дает

основание применить метод параллельных вариантов. ПриУ

использовании этого метода одновременно и независимо друг

от друга на одном и том же материале обучаются несколькоТ

машин. При узнавании новых объектов каждая машина будет

относить эти объекты к какому-то образу, может быть, не к

одному и тому же.

Окончательное

Н

решение принимается

«голосованием» машин – объект относится к тому образу, к

которому его отнесло большее

Б

машин. Эксперименты

показывают, что метод параллельных вариантов весьма эф-

фективен.

й

Другой

способ повышен я

надежности распознавания

число

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

плоскостей. Можно

ложить, что если проводить

секущие плоскос и

предп

к плоскости, проходящей через

середину прямой, соединяющей объект и оппонент и пер-

близко

, то результирующая разде-

пендикулярной к э ой прямой

т

ляющая поверхность будет ближе к истинной границе между

. Эксперименты подтверждают это предположение.

и

В экспериментах с «улучшенным» алгоритмом проведение

з

происходило

следующим образом.

секущих

плоскостей

образами

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

«объ кт – оппонент» и проходящие через ее середину, то для каждого на-

п

бора фигур обучение будет происходить строго определенным образом,

все варианты будут идентичными и метод параллельных вариантов ниче-

Р

го не даст. Поэтому, даже упорядочивая проведение секущих плоскостей,

нужно все же оставить элемент случайности при их выборе.

27

Выбиралось некоторое число k (его величина уточнялась

экспериментом), и после случайного выбора величин λi, и

вычисления σ(1) и σ(2) (см. первую часть алгоритма) модуль

разности σ(1) и σ(2) сравнивался с k. Если |σ(1) – σ(2)| > k,

выбранные λi считались пригодными и вводились в память

машины; если |σ(1) – σ(2)| ≤ k, то λi выбирались вновь до тех

пор, пока модуль разности σ(1) и σ(2) не превзойдет k. Кроме

2

Т

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

У

λn +1 =

σ(1 ) +σ

( 2 )

Н

.

Б

(1.6)

Геометрически эти условия означают, что секущая

плоскость SS проходит через середину прямой, соединяющей

объект и оппонент, и располагается внутри некоторого угла

АОВ вблизи перпендикуляра ОС к

прямой (рис. 1.16),

причем этот угол тем меньше, чем больше величина k.

р

В экспериментах с «улучшеннымэтой» алгоритмом при k = 2 и

при k = 5 средний п оцент п ав льно узнанных фигур

повысился почти до 80 % п

иk =2 и более чем до 85% при

т

k = 5. Один из вариант в при k = 5 дал надежность

распознавания поч и 90 %. Такое резкое повышение надеж-

и

ности распознаван оя за счет более организованного прове-

з

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

компактности справедлива, по крайней мере, в отношении

о

применявшихся образов. В противном случае разные методы

пр веденияплоскостейдавалибыпримерноодинаковыйэффект.

п

е

Р

28

У

Т

Б

Н

й

и

Рис. 1.16. Проведен е секущ х плоскостей

Метод

параллельных

ва антов позволяет еще больше

повысить

до

надежность

аспознавания. Применение этого

метода к вариантам пе в начального алгоритма позволило

двухсот

машине правильно узна

рь 88,5 % фигур, а когда метод был

применен к

ам улучшенного алгоритма, надежность

вариан

узнавания возросла 98,5 %, т. е. машина ошибалась только

з

з

.

в трех случаях

Таким обра ом, эксперименты показали, что метод се-

о

кущих пл скостей действительно позволяет обучить машину

наванию сложных фигур. А так как никакие сведения о

расп

св йствах фигур машине не сообщались, этот же алгоритм в

е

ринци е дает машине возможность обучиться распозна-

Р

ванию широкого класса иных образов, аналогичных по слож-

ности арабским цифрам.

29

Задание

1. Разработать систему распознавания объектов, реализу-

ющую алгоритм секущих плоскостей.

2. Выполнить обучение системы на примере объектов, пре-

дложенных преподавателем.

3. Для защиты работы предъявить результаты распознава-

ния системой новых объектов.

Н

У

Лабораторная работа № 2

АЛГОРИТМ ОПТИМАЛЬНОЙ ОБЪЕКТИВ

ТОЙ

Б

КЛАССИФИКАЦИИ

Краткие тео ет

ческобъективнойе сведения

Цель: изучение алгоритма

классификации,

выполнение с его помощью классификации объектов на неза-

данное число классов.

и

р

чно

Существует достат

б льшое количество практических

т

задач, в которых число классов неизвестно и должно быть

определено в ходе классификации. В этом случае возникает

решения необходимо

определить критерии оптимизации и

проблема выбора на лучшей в каком-то смысле классифика-

з

ции. В такой пос ановке задача классификации может быть

отнесена к группе оптимизационных задач. Поэтому для ее

о

параметры, варьируя которые можно будет из множества

п

в зм жных классификаций выбрать одну, наилучшую с точки

зрения критерия.

Р

Основываясь на гипотезе компактности образов, кажется

ст ственным считать, что при прочих равных условиях клас-

сификация тем лучше, чем ближе друг к другу точки внутри

екаждого класса. Вместе с тем классификация тем лучше, чем