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

• Автор: Денисова, Рахиля Аглеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 124 c. : ил

Глава I. Модель алгоритмов распознавания с представительными наборами для к -значных таблиц

§1. Представительные наборы

§2. Тупиковые представительные наборы

§3. Геометрическая интерпретация

§4. Описание модели Ш. С<5~, р распознающих

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

Глава II. Метод синтеза тупиковых.представительных.наборов.

для к -значных таблиц

§1. О синтезе тупиковых представительных

наборов для . к -значных таблиц

§2. Формула для умножения двух уравнений

Нельсоновского типа (Н.типа)
§3. Формула для умножения трех уравнений Н.типа
§4. Формула для умножения четырех уравнений Н.типа
§5. Оптимальное разбиение системы уравнений Н.типа на пары
§6. Применение алгоритма Эдмондсона и Джонсона для
разбиения системыуравнений Н.типа на четверки
§7. О решении системы уравнений Н.типа
Глава III. Комплекс прикладных программ КПП
и его применение
§1. Принцип организации комплекса..Блок-схема
§2. Описание программ комплекса
§3. Применение комплекса - для решения•задачи
идентификации авторства
Приложение

Задача синтеза классификаций или задача распознавания образов является одной из важнейших задач современной математической кибернетики. Методы ее решения образуют самостоятельное направление в рамках этой науки. Большой интерес к задачам распознавания определяется тем, что, во-первых, они являются весьма общими в плане математической постановки и, во-вторых, находят широкое применение при решении важных практических задач, таких как прогнозирование в естествознании и технике, автоматическое чтение текстов и т.д. При этом задача прогнозирования решается на основе ограниченного накопленного опыта. Данное обстоятельство определяет актуальность работ по математической теории распознавания, созданию численных методов и программ для решения прикладных задач распознавания. Особенно следует отметить, что в настоящее время не существует других математических подходов к решению задач классификации и прогнозирования, отличных от методов распознавания образов, если исходная информация о процессе или явлении ограничена.
В научной литературе дано описание нескольких семейств-моделей распознающих алгоритмов. Некоторые из них, в том числе алгоритмы типа "Кора", приспособлены лишь для работы со специальной обучающей информацией. Поэтому актуальным является построение расширений таких алгоритмов, позволяющее применять их для решения более широких классов прикладных задач. Именно такое расширение, позволяющее включать в обработку алгоритмами типа "Кора" градуированные признаки с большим, чем 2 числом значений, выполнено в настоящей работе.
Цель работы состоит в создании нового класса алгоритмов распознавания, предназначенного для обработки информации с многозначны-
- - 4 - , .
ми признаками, разработке для них эффективных численных методов, позволяющих решать прикладные задачи на ЭВМ в приемлемое время, создании соответствующего программного обеспечения и решении прикладной задачи идентификации авторства.
Алгоритм "Кора" ([4,6,7,9]) появился в середине 60-х годов и предназначался для обработки объектов с бинарными признаками.
На бинарной таблице обучения выделялись так называемые представительные наборы. Для каждой двойки, а впоследствии тройки признаков в каждом классе искались объекты, значения которых по этим признакам были бы отличны от соответствующих значений объектов других классов. Найденные поднаборы в паре соответственно с двойкой или тройкой признаков назывались представительными наборами данного класса. В случае когда рассматривались двойки признаков, задача выделения представительных наборов решалась переборем всех пар признаков. В случае когда рассматривались тройки признаков, задача выделения представительных наборов решалась перебором трехбуквенных конъюнкций. При таком подходе рассмотрение опорных множеств большей мощности вызывает необходимость просмотра всех элементарных конъюнкций соответствующего ранга.
При решении практических задач этот просмотр требует значительного времени даже при использовании современных ЭВМ. С другой стороны такое ограничение опорных множеств приводит к талу, что при достаточно больших объемах обучающей информации вероятность распознавания любого нового объекта равна почти О (С28I). Если рассматривать представительные наборы произвольной длины, то задача выделения их для каждого класса сводится к задаче построения сокращенной дизъюнктивной нормальной формы (д.н.ф.) для не всюду определенной функции алгебры логики (С377). Если же перейти от бинарных признаков к градуированным, то задача выделения представительных наборов для каждого класса становится эквива-

& ' вес с ^ = гпс) х { А* г ] .
Рассмотрим ребро ( X£' , УО/_р0^ ; , 5 £> -,/'#'7}
Тогда Х3' соответствует паре СУС£/с^) УСУ' ;;
а соответствует . Пусть /р
мацность множества
^ для ьр р,-„ . , ,у> ; и
^ ”7 7 ££
Т'Г ) , определенного в § 3, Нч - мощность множества $ч и для 7 Гл7^ , (5^ и У Г £7 5£ 7 ,
- мощность и &з. для У С£7^ ; ^/-^+у 9 и
- вычисляются по Формуле (14). Припишем ребру
СХз'.Хф" ) вес ^#7м= '”»* ^',АЦ.
Применим к графу О- 1 алгоритм Эдмондсона и Джонсона для поиска паросочетания с максимальным весом.
§ 7. 0 решении системы уравнений Нельсоновского
типа
Предположим, что алгоритм Эдмондсона и Джонсона, примененный к графу 7 ' ., дал паросочетание Р ' . Используя пароссочетание Р ' , построим новую систему логических уравнений.
Рассмотрим элемент паросочетания Р ' :
ОГу'.СГ*;, 2, і є /У, г, ...,[#]}
Ему соответствует четверка УС), УСУСЯ; )
У ( Если с'£і_ - , то построим перестановки
ср ид?4- , как описано в §4, для УСУ7?
и У С У/ ,У. 1 соответственно. Выпишем
6т£ 7 ’ ^ с±£'
У СУ1:5 £ , ^ ^ по формуле . (15). Аналогично
поступим, если ' или а^±=г^1г • Тогда построим
и V* К"1