Разработка оптимальных структурно-аналитических моделей и алгоритмов для распознавания объектов по разнотипным экспериментальным данным Дискант, Владимир Алексеевич

Содержание к диссертации

Введение

Глава I. Обзор и анализ существующих методов распознавания объектов. формулировка задач исследования .

1.1. Особенности задач распознавания сложных объектов в условиях априорной неопределенности 10

1.2. Анализ существующих методов распознавания образов. 14

1.3. Структурно-аналитический метод классификации. Формулировка задач исследования 28

1.4. Выводы 35

Глава 2. Разработка и исследование структурно-анажтических моделей распознавания объектов. алгоритмы минимизации таблиц истинности предикатов .

2.1. Разработка структурно-аналитических моделей распознавания объектов. Постановка задач оптимизации 37

2.2. Исследование критериев качества правил классификации 45

2.3. Исследование связи между свойствами таблиц истинности предикатов и структурой правила классификации 57

2.4. Разработка и исследование алгоритмов минимизации таблиц истинности предикатов 65

2.5. Выводы 70

Глава 3. Разработка и исследование алгоритмов построения правил классификации .

3.1. Постановка задачи 71

3.2. Алгоритм БДРІ построения правила классификации с минимальным числом вершин 73

3.3. Алгоритм БДР2 построения правил классификации с максимальным быстродействием 85

3.4. Экспериментальное исследование алгоритмов построения правил классификации 91

3.5. Выводы 98

Глава 4. Применение разработанных алгоритмов для решения задач распознавания объектов

4.1. Разработка пакета прикладных программ для автоматизации процесса решения задач распознавания объектов 100

4.2. Решение задачи диагностики технических средств АСУТП , 108

4.3. Построение правил классификации в задаче назначения плавок 117

4.4. Применение разработанных алгоритмов для решения задач классификации зернобобовых 121

4.5. Выводы 126

Заключение 127

Литература 129

• Особенности задач распознавания сложных объектов в условиях априорной неопределенности
• Разработка структурно-аналитических моделей распознавания объектов. Постановка задач оптимизации
• Алгоритм БДРІ построения правила классификации с минимальным числом вершин
• Разработка пакета прикладных программ для автоматизации процесса решения задач распознавания объектов

Введение к работе

В настоящее время необходимым условием постоянного повышения эффективности общественного производства в СССР является комплексная механизация и автоматизация производственных процессов на базе широкого использования ЭВМ. В решениях ХХУІ съезда КПСС подчеркивается необходимость решения проблемы "... усовершенствования вычислительной техники, ее элементной базы и математического обеспечения, средств и систем передачи и обработки информации, повышение эффективности автоматизированных систем управления."

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

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

Большой вклад в решение задач распознавания объектов по разнотипным данным внесли Н.Г. Загоруйко, Ю.И. Журавлев, Ю.А. Воронин, В.В. Александров, В.П. Гладун, К.С. Фу, B.C. Майзель и др. Эффективные методы построения правил классификации, основанные на логических решающих функциях, рассмотрены в работах Г.С. Лбова, А.Н. Манохина, В.И. Котюкова.

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

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

Тема диссертационной работы связана с научно-исследовательской работой, выполненной по постановлению ГКНТ от 15.07.80 г. №326, совместному постановлению ГКНТ, Госплана СССР и АН СССР от 12.12.80 г. № 475/25I/I3I в соответствии с программой работ по проблеме 0.80.14 и заданием 33.14 "Разработать пакет прикладных программ построения структурно-аналитических моделей для АСУ ТП и САПР с целью оптимизации параметров объектов новой техники при их разработке и производстве" (№ГР 0182.8005471), включенной в план важнейших работ Минвуза СССР (приказ Минвуза СССР от 29.08.80 г., №965).

В соответствии с поставленной целью решались следующие основные задачи:

- математическая постановка задачи оптимизации грамматик образов;

- выбор и обоснование критериев качества правил классификации;

- разработка и исследование алгоритмов минимизации таблиц истинности предикатов;

- разработка и исследование алгоритмов построения оптимальных правил классификации;

- разработка пакета прикладных программ для автоматизации процесса построения правил классификации;

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

Научная новизна. Разработаны постановка, теоретическое обоснование и методика решения задачи оптимизации грамматики образов как экстремальной комбинаторной задачи минимизации функции стоимости дерева решений, связанного с грамматикой.

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

Предложена декомпозиция оптимизационной задачи на две подзадачи: минимизацию таблиц истинности предикатов и построение оптимального правила классификации.

Для минимизации таблиц истинности предикатов использован модифицированный метод первичных событий. Показано, что метод позволяет получать локально-оптимальные решения.

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

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

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

-статистики, алгебры логики и элементы эвристики.

По результатам исследований опубликовано II работ.

Основные положения диссертационной работы доложены и обсуждены на:

- У Всесоюзном совещании "Статистические методы в процессах управления", г. Алма-Ата, сентябрь 1981 г.;

- ІУ Всесоюзном симпозиуме по машинным методам обнаружения закономерностей (М03-ІУ), г. Новосибирск, ноябрь 1983 г.;

- Республиканской школе-семинаре "Автоматизация проектирования радиоэлектронных систем", г. Харьков, октябрь 1981 г.;

- Региональной научно-технической конференции "Методы и практика математического моделирования при разработке месторождений в сложных геолого-гидрогеологических условиях", г. Белгород, июнь 1982 г.;

- Республиканской школе-семинаре "Автоматизация проектирования и управления производством РЭА", г. Харьков,декабрь 1982 г.

- Областной научно-практической конференции "Важнейшие направления развития АСУ и ВТ в свете решений ХХУІ съезда КПСС", г. Харьков, октябрь 1981 г.;

- заседаниях семинара Научного совета АН УССР по проблеме "Кибернетика" "Математические методы в задачах автоматизации проектирования и изготовления систем летательных аппаратов", г. Харьков, I98I-I982 г.г.;

- научно-технических конференциях профессорско-прподава-тельского состава Харьковского ордена Ленина авиационного института им. Н.Е. Жуковского, г. Харьков, 1979-1983 г.г.

Разработанные алгоритмы реализованы в пакете прикладных программ КОД-2, внедренном на ряде предприятий народного хозяйства. Годовой экономический эффект от внедрения результатов работы составляет 44 тыс. рублей.

- 8 Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 121 странице машинописного текста, содержит 15 рисунков, 8 таблиц, библиографию из 135 наименований отечественной и зарубежной литературы и два приложения.

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

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

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

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

Приложение I содержит листинги решения некоторых задач распознавания объектов.

Приложение 2 включает в себя документы о внедрении результатов работы.

Автор выражает глубокую благодарность научному руководителю, доценту, кандидату технических наук СИРОДЖА Игорю Борисовичу за большую помощь и внимание, оказанные при выполнении диссертационной работы.  

Особенности задач распознавания сложных объектов в условиях априорной неопределенности

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

Можно выделить следующие основные задачи, для решения которых применяются методы РО / 74,85,94 / : классификационная обработка больших массивов информации, оценка состояния систем и подсистем АСУ, сжатие данных, повышение надежности и быстродействия систем переработки информации, управление показателями эффективности, упрощение взаимодействия операторов и пользователей АСУ с системой.

Одним из распространенных типов задач является классификационная обработка данных (КОД). Особенности задачи КОД заключаются в том, что экспериментальные данные, по которым строятся

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

Распознавание состояния технической системы (техническая диагностика) /10,96/ основано на построении диагностических моделей и правил классификации неисправностей по экспериментальным данным и направлено на повышение надежности и ресурса технических систем. Одна из актуальных задач технической диагностики - диагностика технических средств АСУТП, поскольку отказ в системах управления комплексами больших мощностей может нанести значительный ущерб. Наиболее существенным требованием в подобных задачах является быстродействие алгоритма распознавания неисправностей.

Одна из наиболее важных областей применения методов РО -использование в контуре управления АСУТП для оценки текущего состояния объекта /1,85,96/. На основе измерения набора параметров система РО распознает производственные ситуации и корректирует значение управляющего воздействия на объект. При реализации алгоритмов распознавания в АСУТП наиболее существенный фактор - ограничение на объем оперативной памяти, занимаемый процедурой классификации.

Учитывая эти особенности задач распознавания объектов, рассмотрим основные требования к методам РО.

I. Разнотипность экспериментальных данных. При обработке данных, измеренных в различных шкалах, результаты классификации не должны зависеть от числового представления информации об объекте. Для формализации этого требования вводятся понятия шкалы и группы допустимых преобразований шкал /?6 /. Пусть заданы эмпирическая система с отношениями "; = &$7 , где О множество объектов, О J - эмпирическое отношение на множестве В для признака 3Q ; числовая система с отношениями Е - N Л/ R. , где Л/ - множество действительных чисел, - числовое отношение на множестве /V . Задана функция & , гомоморфно отображающая систему Ел в Е . Тогда шкалой называется тройка Ej, Е у j У . Если заданы шкалы Ей E,f и KEj,E, Q , то всякое преобразование такое, 4ToQ=YJf, называется допустимым. Допустимые преобразования определены для всех типов шкал, встречающихся в практических задачах РО. Так, для шкалы наименований допустимы взаимо-однозначные преобразования, позволяющие определять только отношение эквивалентности объектов; для шкалы интервалов допустимо линейное преобразование Ч (Х)=ах+в, Q- 0 , где Q. и О -действительные числа /76/. При разработке методов РО для обработки разнотипных данных необходимо, чтобы преобразование значений измеряемых признаков входило в группу допустимых преобразований для выбранного признака.

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

3. Ограничения на объем машинной памяти и время вычислений.

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

Таким образом, проведенный анализ особенностей задач распознавания сложных объектов позволяет сформулировать следующие основные требования к системам РО:

- инвариантность модели по отношению к допустимым преобразованиям шкал измерения признаков;

- возможность компактного описания многоклассовых ситуаций;

- высокое быстродействие и малый объем занимаемой машинной памяти при классификации новых объектов;

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

Разработка структурно-аналитических моделей распознавания объектов. Постановка задач оптимизации

Структурно-аналитическую модель, как и любую известную модель распознавания, можно охарактеризовать с помощью множественной пары априорного Ни и эмпирического (Ju) факторов (по систематизации Ю.И. Журавлева /33/). Априорный фактор Ни) определяется множеством постулируемых гипотез о характере закономерностей относительно распознаваемых образов. Для СА моделей в качестве Ни) используется гипотеза структурного образа (см. п. 1.3.). Эмпирический фактор определяется заданием обучающей выборки (ОВ) и параметрического семейства отображений (1.4.) и (1.5.).

Рассмотрим методику построения СА моделей. Обучающая выборка задается в виде таблицы экспериментальных данных (ТЭД), представляющей собой таблицу типа "объект-свойство" /36/.

Информация о принадлежности любого объекта из ТЭД к определенному классу формируется в виде вектора указаний учителя

. Y = / U)[ 5 U) = / У, Z . KJ- СА модели строятся на основе описания существующих в ТЭД эмпирических закономерностей с помощью свойств предикатов.

Определение 2.1. Свойством-предикатом (СП) называется любое обобщенное или локальное свойство L є. iff распознаваемых образов, описываемое предикатным уравнением где I (Xf L) - аналитическое выражение закономерности / , которой подчинены все, либо часть реализаций X образа U/ j . Структурно-аналитическая модель определяется в виде отображения - 39 Ф: F, —Y (2.3.) В отличие от известных моделей распознавания в модели (2.3.) осуществляется двухступенчатое преобразование исходного признакового пространства. Эта особенность позволяет обеспечить инвариантность модели относительно допустимых преобразований шкал признаков, поскольку отображения основаны на использовании предикатов вида (2.2.), определенных для всех типов шкал измерений.

Правило классификации Ф(х) формируется в виде бесконтекстной с конечным числом состояний программной грамматики /90/.

Определение 2.2. Грамматикой образов называется пятерка (VN5 Vx,J,n,6) (2.4.)

где VN И VT - соответственно вспомогательный и основной словарь; о - множество меток правил подстановки; П - правила вывода; Ь - начальный символ.

Вспомогательный словарь содержит имена областей для описания структуры распознаваемых классов

Vr/={G,(0L/Le{lf2J... M]] (2.5.) где: - начальный символ, соответствующий предметной области структурного образа 14 ; - подмножества, соответствующие подобразам (фрагментам) структурного образа К и образованные разбиением исходного пространства признаков с помощью системы предикатов вида (2.2.);

Алгоритм БДРІ построения правила классификации с минимальным числом вершин

Пусть задана структурно-полная система S(f7l0 Q+1) с/7?0 фрагментами. В общем виде задача построения оптимального БДР ставится как экстремальная комбинаторная задача поиска дерева, для которого достигается минимум целевой функции (3.5.). Наиболее эффективным подходом к решению подобных задач является метод ветвей и границ /52/, разработанный для решения ряда комбинаторных задач дискретного программирования. Основная трудность при практическом- применении метода ветвей и границ заключается в нахождении рациональных способов ветвления множества возможных решений на подмножества и вычислении оценок, определяющих выбор перспективных подмножеств.

Задача построения оптимальных ПК как экстремальная комбинаторная задача в литературе не изучалась. Наиболее близкая по постановке задача построения оптимальных бинарных деревьев поиска по таблицам решений рассматривалась Л.Т. Рейнвальдом и P.M. Со-ландом /125,126/. В этих работах предложен алгоритм, основанный на методе ветвей и границ, для критериев максимального быстродействия и минимальной памяти. СПС можно интерпретировать как таблицу решений с ограниченным входом. В работе /126/ рассматривались таблицы решений общего вида, для которых определение оценок нижней границы связано с громоздкими вычислениями. Особенность рассматриваемой нами задачи заключается в том, что для СПС построено минимальное число фрагментов 0 , входящих в определяющее множество. Это позволяет строить простые оценки нижней границы пожмножества вариантов решения. Используя способ ветвления, предложенный в работе /125/, построим следующую процедуру поиска оптимального решения.

Любое возможное БДР можно рассматривать как относящееся к одному из О подмножеств: подмножеству JJ і БДР с корнем Jl , подмножеству J)z БДР с корнем S 2. и т. д. Если для любого СП Jj можно определить минимальное число фрагментов

# C//J » (соответствующих терминальным вершинам дерева), порождаемое подстановкой ТІ в корень дерева, Тогда, выбирая по определенному правилу подмножество JJj и проводя дальнейшее его разбиение, можно построить последовательность подмножеств соответственно СП j-1 , J і ,..., определяющих ветвь БДР, заканчивающейся терминальной вершиной. Совокупность таких ветвей определит дерево решений. При выборе

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

Рассмотрим основные построения, определяющие алгоритм ветвей и границ для решения задачи построения БДР с минимальным числом вершин.

Заметим, что мощность подмножеств -О определяется номером уровня бинарного дерева, на котором проводится разбиение. Так, для корневой вершины, находящейся на нулевом уровне, \Ъд \- О, для 1-го уровня \j)i I-Q-1 и т. д. Поэтому для О -го уровня множество _/) і будет содержать один элемент (терминальную вершину). Вместе с тем некоторые из Q - и предикатов могут быть исключены из рассмотрения, если для всех фрагментов они имеют одинаковое значение истинностили J В этом случае соответствующему подмножеству і) ; приписывается ҐТ\Ю\ значение нижней границы Г 1 ;го - 77 Вычисление нижней границы. Поскольку целевая функция (3.5.) определяет число фрагментов JUL- К+1 , то в качестве оценки нижней границы необходимо выбрать величину, учитывающую приращение фрагментов Л/ - для любого isco i\(0) подмножества Jji . Исходное множество J) включает в себя fTl фрагментов (терминальных вершин) БДР. Очевидно, что увеличение числа фрагментов происходит только тогда, когда в вершину выбирается СП, имеющий значение " й. " для L- -го фрагмента. В этом случае фрагмент 0 і входит в правое Djl и левое JJjo поддерево, образованные подстановкой СП//. Поэтому общее число фрагментов для выбранногоjl , и связанного с ним подмножества 7\U) JJI равно При последовательном ветвлении подмножеств, начиная с корня и заканчивая терминальной вершиной, оценка (3.7) вычисляется с помощью следующего рекуррентного соотношения

Разработка пакета прикладных программ для автоматизации процесса решения задач распознавания объектов

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

В литературе описаны программные комплексы, реализующие различные методы распознавания: логические решающие функции /30, 37/, тестовые методы и алгоритмы вычисления оценок /17,43,47/, структурный метод /6/. Кроме того, известны многоцелевые системы, включающие в себя комплекс алгоритмов РО /4,42,81,86/, а также интерактивные программные комплексы /45,104,109/. По мнению большинства авторов /4,5,40,42,81/, наиболее эффективным и удобным для пользователя видом реализации методов распознавания являются пакеты прикладных программ, позволяющие упростить общение пользователя с системой РО и автоматизировать процесс построения правил классификации.

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

Разработанные алгоритмы реализованы в пакетах прикладных программ (ППП) К0Д-І /69/ и КОД-2 /70/. Пакет К0Д-І функционирует под управлением операционной системы ДОС ЕС и ключает в себя программные модули, обеспечивающие решение задач распознавания с обучением /49/ и самообучением /48/.

Пакет КОД-2 разработан по постановлению ГКНТ, принят межведомственной комиссией, прошел опытную эксплуатацию, передан в УкрФАП иГосФАП. В целм ППП КОД-2 предназначен для автоматизации процесса построения структурно-аналитических правил классификации объектов по разнотипным экспериментальным данным в задачах распознавания и классификации. Пакет ориентирован на ЕС ЭВМ с операционной системой ОС ЕС (варсия 4.1 и выше). Настоящая версия ППП КОД-2 позволяет обрабатывать ТЭД с числом объектов

ГП ЗОО, признаков и ЕО и классов К 20 . Для нормального функционирования пакета в режиме обучения (построения ПК) требуется 256 К байт оперативной памяти. Время решения существенно зависит оттструктуры входных данных (число признаков, объектов и классов) и находится в пределах 1-20 минут.

Объем занимаемой оперативной памяти и затратл времени в режиме классификации новых объектов определяется структурой ПК и не превышают I К байт и 0,01 сек. (для ТЭД с числом классов К-2В , объектов т -Ъ00 и признаков п =20 ).

Функциональная схема ППП КОД-2 с особенностями его системной реализации приведена на рис. 4.1. Подробное описание ППП приведено в работах /70,71/. В настоящей работе рассматриваются только блоки пакета, которые реализуют методы построения ПК в режимах обучения и классификации новых объектов.

Для решения указанных задач в состав пакета включены главный диспетчер (шаг РІ ), общий для всех подсистем ЇЇПП, а также управляющая программа и билиотека обрабатывающих модулей, объединенные в подсистему "Классификатор" (шаг и реализующие: алгоритмы построения ПК (см. рис. 4.1).

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