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

t * / i , i i t i , J J t t > i i i i t

Введение

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

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

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

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

§4. Описание модели ШС^р,^) распознающих алгоритмов с представительными наборами

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

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

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

Нельсоновского типа (Н.типа)

§3. Формула для умножения трех уравнений Н.типа

§4. Формула для умножения четырех уравнений Н.типа

§5. Оптимальное разбиение системы уравнений Н.типа на пары

§6. Применение алгоритма Эдмондсона и Джонсона для разбиения системыуравнений Н.типа на.четверки

§7. О решении системы уравнении Н.типа

Глава III. Комплекс прикладных программ КПП и его применение.

§1. Принцип организации комплекса. Блок-схема.

§2. Описание программ комплекса.

§3. Применение комплекса■для решения■задачи идентификации авторства

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

В научной литературе дано описание нескольких семейств-моделей распознающих алгоритмов. Некоторые из них, в том числе алгоритмы типа "Кора", приспособлены лишь для работы со специальной обучающей информацией. Поэтому актуальным является построение расширений таких алгоритмов, позволяющее применять их для решения более широких классов прикладных задач. Именно такое расширение, позволяющее включать в обработку алгоритмами типа "Кора" градуированные признаки с большим, чем 2 числом значений, выполнено в настоящей работе.

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

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

Использование аналога метода Нельсона (Г451) для построения сокращенной д.н.ф. не всвду определенной функции к -значной логики позволяет свести эту задачу к решению системы логических уравнений - уравнений Нельсоновкого типа. Отметим, что традиционный метод решения системы - переход от конъюнктивной нормальной формы к дизъюнктивной нормальной форме с последующим применением к последней операций поглощения и склеивания - требует построения и перебора большого числа элементарных конъюнкций. Встает вопрос о сокращении числа рассматриваемых элементарных конъюнкций. При решении этого вопроса было получено обобщение на к -значный случай формулы свертки двух специальных дизъюнкций, выведенной С.В.Яблонским ([14]), которое позволило сощ)а-тить число уравнений вдвое, увеличив при этом сложность каждого минимальным образом. С использованием этого результата получены формулы экономного умножения левых частей двух, трех, четырех уравнений системы, которые позволили уменьшить первоначальное число уравнений в четыре раза.

Умея считать сложности произведения двух, трех, четырех уравнений системы, можно поставить вопрос о таком разбиении системы логических уравнений на четверки, чтобы суммарная сложность их произведений была бы минимальной. Эта задача решается сведением к задаче синтеза паросочетания с максимальным весом в соответствующем взвешенном графе ([23J).

В результате достигаемого сокращения числа рассматриваемых элементаных конъюнкций получаем не сокращенную д.н.ф. для не всюду определенной функции к -значной логики, а д.н.ф., реализующую ту же функцию, но состоящую в общем случае из меньшего числа простых элементарных конъюнкций. Следовательно, в общем случае получаем собственное подмножество множества тупиковых представительных наборов. Т.к. из построенной д.н.ф. можно методом, аналогичным методу Блейка ([14,36]), всегда построить сокращенную д.н.ф., то указанное подмножество несет в себе ту же информацию о разбиении множества допустимых объектов на классы, что и множество тупиковых представительных наборов.

На основе предложенного метода синтеза совокупности представительных наборов построена многопараметрическая модель распознающих алгоритмов с представительными наборами - алгоритмов типа "Кора". С помощью этих алгоритмов решена практическая задача идентификации авторства стихав поэтов-антифашистов группы Мусы Джалиля (список I). Тексты этих стихов дошли до нас в блокнотах военнопленных, и их точное авторство было неизвестно. Вместе о- тем сохранились произведения тех лет некоторых членов группы : Моабитские тетради М.Лжалиля (спивок 2), тетрадь А.Алиша.(список 3), одно стихотворение Г.Баттала, пять стихотворении А.Симая, три стихотворения Р.Нигмати, не вжодившего в группу, но находившегося в одних условиях с джалиловцами(список 4).

Наиболее интересной литературоведческой задачей было : установить какие из спорных произведений (список I) принадлежат М.Лжалилю и какие А.Алишу. Эта задача решается в диссертации.

Опишем содержание диссертации по главам.

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

Во второй главе предлагается метод синтеза тупиковых представительных наборов (&П, опиоьвается численный метод построения совокупности тупиковых представительных наборов (§§2—7).

Результаты второй главы являются основными.

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

В приложении приводятся тексты программ комплекса КПП.

Автор выражает глубокую благодарность своему научному руководителю Юрию Ивановичу Журавлеву за постановку задачи и постоянное внимание к работе, Рафаэлю Ахметовичу Мустафину, Канафи Габдельбаровичу Бадикову, Илиде Басыровне Башировой , принявшим деятельное участие в выработке признаков и обработке текстового материала.

1. Бак Хынг Кханг. О геометрических задачах, связанных с оценкой точности одного класса распознающих алгоритмов.-Журнал вычисл. матем. и матем. Физики,1974,т.14,$6,с.1571-1580.

2. Бонгард М.М. Проблемы узнавания.-М.:Наука,1967.-320с.

3. Зурдаков О.П.,Голиков А.И.,Евтушенко Ю.Г.,Жадан В.Г., Потапов М.А. Диалоговый комплекс программ ДОС0.Раздел нелинейного программирования.-В сб.:Депонированные рукописном;Д982, $9(131),реф.171,рукопись $2716-82 деп,88с.

4. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора".-В кн.:Алгоритмы обучения распознаванию образов.М.,1973,с.II0-II5.

5. Вапник В.Н.,Червоненкис А.Я. Теория распознавания образов.-М.:Наука,1974.-415с.

6. Веселов Е.Н.,Мазурик В.П.Диалоговая система оптимизации (инструкция пользователю).-М.:ВЦ АН СССР,1980,56с.

7. Губерман Ш.А.,Марипов Т.М. Оценка перспективности месторождений гидротермальных руд с применением ЭВМ.-Труды МИНХ и ГПим.Губкина,М.:Недра,I966,вып.62.

8. Гулямов Д.Х.,.^равлев Ю.И. Оценка качества экспертов, формирующих таблицу обучения в задаче распознавания образов.-Журнал вычисл. матем. и матем. физики,1972,т.12,$4,с.1066-1070.

9. Гулямов д.х. Опыт применения алгоритмов голосования для прогнозирования двойных неорганических соединений.-Труды Международного симпозиума по практическим применениям методов распознавания образов.М.:ВЦ АН СССР,1973,с.231-236.

10. Денисова Р.А. Метод синтеза тупиковых представительных наборов для к -значных таблиц.-М.:ВЦ АН СССР,1984,29с.

11. Денисова Р.А. Об одном классе функций к-значной логики.-Журнал вычисл. матем. и матем. физики,1984,т.24,Ж,с.167-169.

12. Дискретная математика и математические вопросы кибернетики/ Под общей редакцией С.В.Яблонского и О.Б.Лупанова.-М. :Наука, 1978.-312с.

13. Евтушенко Ю.Г. Методы решения экстремальных задал и их применение в системах оптимизации.-М.:Наука,Главная редакция физико-математической литературы,1982.-432с.

14. Гуравлев Ю.И. Алгоритмы распознавания, основанные на вычислении оценок.Содержательный смысл параметров, задающих алгоритм.-Труды Международного симпозиума по практическим применениям методов распознавания образов.М.:ВЦ АН СССР,1973,с.205-218.

15. Дуравлев Ю.И.,Камилов М.М.,Тулягансв Ш.Е. Алгоритмы вычисления оценок и.их применения."ФАН'\Ташкент,1974.

16. ЗЗуравлев Ю.И. ,Карчевски Е.,Михалевич М. Алгоритмы распознавания, задаваемые наборами качественных признаков.-Труды ВЦ Польской АН,Варшава,1974,вып.146.- 81

17. Журавлев Ю.И. ,Мирошник С.Н. ,ПЗвартин С.М. Об одном подходе к оптимизации в классе параметрических алгоритмов распознавания.-$урнал вычисл. матем. и матем. физики,1976,т.16,1,с.209-218.

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

19. Журавлев Ю.И. Об отделимости подмножеств вершин п -мерного единичного куба.-Труды Матем.ин-та АН СССР,1958,т.51,с.143-157.

20. Дуравлев Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур.-В сб."Проблемы прикладной математики и механики".М.:Наука,1971.

21. Журавлев Ю.И.,Юнусов Р. Об одном способе уточнения алгоритма таксономии при помощи распознающих методов типа голосования.-Журнал вычисл.матем. и матем. физтки,1971,т.1Г,1е5,с.1334-1347.

22. Исматова Х.Р. "Алгоритмы распознавания, основанные на выделении представительных наборов в обучающей информации.-Дис. канд. шиз.-матем. наук.-М.,1983.-92л.

23. Ищук В.И. О поиске оптимальных весов коэффициентов для одного класса алгоритмов вычисления оценок.-В сб.:Сб. работ по матем. кибернетике,М.:ВЦ АН СССР,1976,вып.1,с.186-194.

24. Катериночкина Н.Н. Поиск максимального верхнего нуля для одного класса монотонных функций к -значной логики.-Докл.АН СССР,1977,т.234,М,с.746-749.

25. Кольцов П.П. Задача распознавания при ограничениях во времени.-Парная вычисл. матем. и матем. физики,1974,т.14.$5,с.1292-1308.

26. Кристофидес Н. Теория графов.Алгоритмический подход.-М.:МирД978.-432с.

27. Леонович А.С. Построение алгоритма распознавания причин брака в сталеплавильном производстве.-Б сб.:Сборник работ по математической кибернетике,М.:ВЦ АН СССР,1976,вып.1,0.212-222.

28. Мазный Г.Л. Программирование на БЭСМ-6 в системе ".Пубна".-М.: Наука,1978.-272с.

29. Мирошник С.Н. Алгоритм голосования с непрерывной метрикой.-Кибернетика,I972,Ш.с.54-63.

30. Нурлыбаев А.Н. О нормальных формах k-значной логики.-Всб.гСб. работ по матем. кибернетике,М.:ВЦ АН СССР,1976,вып.1, с.56-68.

31. Пяатоненко И.М. О реализации алгоритмов типа "Кора" с помощью решения, системы булевых уравнений специального вида.-М.:ВЦ АН СССР,1983,21с.

32. Слуцкая Т.Л. Об эффективности алгоритмов голосования для одного класса бинарных таблиц.-Кибернетика,1973,$2,с.80-86.

33. Теренков В.Н. О точности алгоритмов вычисления оценок для таблиц, порождаемых монотонными булевыми функциями.-ItfypHaл вычисл. матем.и матем. Физики,1973,т.13,$6,с.1620-1625.

34. Теренков В.Н. О точности алгоритмов вычисления оценок для одного класса таблиц.-Кибернетика, 1974 ,$3, с .27-31.

35. Шауцукова Л.З. Оценка информативности функциональных показателей и их совокупностей в динамике лечения.-Журнал вычисл. матем. и матем. физики,1975,т.15,$3,с.803т806.

36. Шауцукова Л.З. Решение одной задачи классификации методом вычисления оценок.-И^рнал вычисл. матем. и матем. физики,1975,t.i5,js4, c.i020-1030.

37. Яблонский С.В. функциональные построения в -значной логике.-Труды Матем.ин-та АН СССР,М.,1958,т.51,с.5-142.