Содержание к диссертации
Введение
1 Исследование состояния задачи распознавания образов 14
1.1 Место методов распознавания образов в задачах оценивания и управления 14
1.2 Общая постановка задачи распознавания 17
1.2.1 Типы решаемых задач 20
1.2.2 Типы обрабатываемой информации 23
1.3 Концепция обучения 25
1.4 Классы алгоритмов распознавания 31
1.4.1 Структура алгоритмов распознавания 31
1.4.2 Способы задания распознающих операторов 32
1.5 Коллективные решающие правила 37
1.5.1 Логическая и геометрическая интерпретация комитетов в задаче распознавания образов 39
1.5.2 Критерии оптимальности коллективных решающих правил 44
1.5.3 Алгоритмы построения комитетов 46
1.6 Цель и задачи диссертационного исследования 49
2 Модель адаптации классификатора к источнику априорной информации 52
2.1 Формы представления обучающей информации и ее неопределенности в задаче распознавания 52
2.2 Организация процесса адаптации 55
2.3 Преобразование коррекции обучающей информации 58
2.4 Преобразование коррекции матрицы алгоритмических оценок параметра качества 60
Выводы 66
3 Алгоритмы построения адаптивного классификатора .. 68
3.1 Выбор меры несогласованности алгоритмических оценок для кусочно-линейных комитетных решающих правил . 68
3.2 Алгоритм адаптации комитетного решающего правила к априорной классификации 71
3.2.1 Базовая операция изменения рангов объектов 71
3.2.2 Организация итерационного процесса перемещения комитета
в пространстве параметров состояния 75
3.2.3 Использование эвристических процедур при поиске решающего правила 78
3.2.4 Алгоритм линейной коррекции для проверки линейной разделимости множеств 79
3.2.5 Анализ сходимости итерационного процесса 83
3.3 Алгоритм адаптивной кластеризации для построения немонотонной
меры близости в пространстве параметров состояния 86
3.3.1 Связь с проблемой неопределенности априорной информации. 86
3.3.2 Алгоритм кластеризации 88
Выводы 92
4 Организация системы распознавания в условиях неопределенности априорной информации различных видов 93
4.1 Задача дискриминантного анализа 93
4.2 Выбор информативных параметров состояния 97
4.3 Схемы построения системы распознавания при решении задач классификации 101
4.4 Проверка работоспособности алгоритмов на модельных примерах... 103
4.4.1 Базовый алгоритм адаптации 105
4.4.2 Алгоритм решения задачи дискриминантного анализа 109
4.4.3 Алгоритм кластеризации 111
Выводы 112
5 Численное решение задач классификации на основе алгоритмов адаптации 114
5.1 Задача контроля качества кристаллов искусственного кварца 115
5.1.1 Постановка задачи неразрушающего контроля качества 115
5.1.2 Организация системы распознавания 116
5.1.3 Результаты работы системы распознавания 117
5.2 Задача оценивания тяжести гипертрофической кардиомиопатии 121
5.2.1 Постановка задачи оценивания 121
5.2.2 Организация системы распознавания 122
5.2.3 Классификация объектов обучающей выборки 126
5.2.4 Выбор информативного подпространства и построение решающих правил 128
Выводы 132
- Место методов распознавания образов в задачах оценивания и управления
- Формы представления обучающей информации и ее неопределенности в задаче распознавания
- Выбор меры несогласованности алгоритмических оценок для кусочно-линейных комитетных решающих правил
- Схемы построения системы распознавания при решении задач классификации
Введение к работе
Диссертация посвящена разработке и практическому применению методов и алгоритмов распознавания образов, позволяющих решать задачи классификации в условиях неопределенности. Под неопределенностью понимается использование в ходе обучения системы распознавания неточной, неполной и противоречивой априорной информации о классифицируемых объектах. Предполагается также отсутствие информации о статистических законах распределения значений параметров классифицируемых объектов.
Актуальность темы. В настоящее время экспертные системы (системы поддержки принятия решений) получают широкое применение в разнообразных прикладных областях при решении задач оценивания и управления [10, 11, 17, 26, 60, 74, 85]. Задача таких систем - выявить и формализовать знания и правила, которые используют эксперты из какой-либо прикладной области при принятии решения о выборе оптимального управления, либо оптимальных оценок для объекта управления, а затем применить полученную информацию для автоматизации принятия аналогичных решений.
Методы распознавания образов являются одним из основных средств, используемых при построении экспертных систем [26, 74]. Задача распознавания, в общем виде, представляется как задача наилучшего, с точки зрения выбранных целей, разбиения на классы какого-либо множества объектов. Классы при этом соответствуют различным возможным управлениям (оценкам) для объектов. Систематическая постановка задачи распознавания образов впервые рассмотрена в работах Р.Фишера, А.Н.Колмогорова, А.Я.Хинчина, Ф.Розенблатта. В 1960-е г.г. широкое развитие получил вероятностный подход к задачам распознавания в работах В.М.Глушкова, Я.З.Цыпкина, А.Г.Ивахненко, Ю.И.Журавлева, М.А.Айзермана, Э.М.Бравермана, М.М.Бонгарда, Л.И.Розоноэра, Н.Г.Загоруйко, В.Н.Вапника, А.Я.Червоненкиса, Г.С.Себастиана. В дальнейшем были предложены постановки задачи распознавания, позволяющие использовать различные виды априорной информации о классифицируемых объектах: числовые и логические признаки объектов, логические закономерности (в т.ч. с использованием аппарата нечеткой логики) [33, 83, 84, 93-95, ПО, 118, 123], регулярные свойства классов объектов [19, 107, 116], вероятностные законы распределения значений признаков [1, 12-15, 70, 88, 120] и т.д.
В настоящее время разработка методов обработки нечетких, неполных и противоречивых знаний составляет основное содержание работ в области создания экспертных систем [74]. Такие системы должны обнаруживать противоречия между имеющимися и вновь поступающими данными и обладать средствами согласования этих противоречий. В рамках задачи распознавания образов это свойство обуславливает необходимость разработки методов, позволяющих решать задачи классификации при наличии недостаточного количества достоверной информации об объектах исследования. Во многих случаях разработка систем распознавания затрудняется именно тем, что эксперты не обладают достаточным количеством информации для принятия гарантированно безошибочных решений. Поэтому актуальной представляется разработка методов, позволяющих решать задачи классификации в условиях, когда информация, описывающая возможные состояния объектов и соответствующие им управления (оценки), может содержать ошибки.
В диссертации рассматривается случай, когда в качестве априорной обучающей информации используются результаты некоторых инструментальных измерений, проводимых над объектами исследования, а также суждения экспертов относительно классов некоторых из обследованных объектов. В этом случае, как правило, используются некоторые предположения относительно статистических законов распределения значений параметров, характеризующих состояние объектов [1, 10, 62, 89]. При этом решения, принимаемые системой классификации, также носят статистический характер, а недостаток априорной информации компенсируется сведениями, полученными за счет сделанных вероятностных допущений. В то же время существует широкий класс практических задач, в которых никаких предположений о статистических характеристиках распределения значений параметров объектов сделать невозможно. Это обуславливает необходимость разработки соответствующих методов для случая статистической неопределенности параметров объектов.
В данной ситуации система распознавания образов должна компенсировать недостаток достоверной априорной информации об объектах за счет интерактивного взаимодействия с экспертами. При этом задача методов распознавания заключается в том, чтобы оценить достоверность каждого элемента априорной информации, т.е. его согласованность со всем объемом доступной априорной информации. На основе этих оценок эксперты должны иметь возможность целенаправленно уточнять отдельные элементы априорного описания объектов, в результате чего качество работы системы распознавания при построении классификации будет возрастать. Это обуславливает необходимость разработки методов, которые объединяли бы используемые в системах распознавания процедуры обучения (для использования априорных экспертных оценок) и самообучения (для построения оценок достоверности априорной информации). Такой подход позволяет расширить смысл понятия "обучающая выборка" и придает системе распознавания динамические свойства, т.е. возможность постепенного улучшения своих характеристик в процессе эксплуатации за счет целенаправленного уточнения априорной информации в ходе взаимодействия с экспертами.
Для реализации процедур распознавания в диссертации используется подход, основанный на использовании коллективных решающих правил (комитетов) [51, 68]. Использование коллективного решения позволяет формировать решающие правила, сложность которых оказывается адекватной сложности задачи при изменении сложности предоставляемых для обработки данных. Наибольшее развитие получили вопросы применения коллективных решений для построения кусочно-линейных комитетных решающих правил, в первую очередь в рамках научной школы В.Д. Мазурова: в работах В.Д.Мазурова, М.Ю.Хачая, НГ.Белецкого, В.С.Казанцева и др. [7-9, 31, 32, 50-57, 71-73, 96-99, 103-106]. В рамках научной школы Ю.И.Журавлева, исследованию свойств комитетов, как частного случая алгебраического подхода к задаче распознавания [22-24], посвящены работы В.В.Рязанова, Ю.А. Зуева, К.В.Рудакова и др. [27-29, 64-68, 85, 99, 112, 113, 115]. Алгоритмическая база построения комитетных решающих правил имеет некоторые принципиальные ограничения [73, 96, 98]. Эти ограничения заставляют искать компромисс между качеством работы системы распознавания и ее практической реализуемостью на вычислительных средствах. Используемый в диссертации принцип объединения процедур обучения и самообучения позволяет предложить новую формулировку задачи построения коллективного решающего правила - как задачи оптимизации относительно критерия согласованности коллективного решения. Это дает возможность использовать для построения комитетных решающих правил процедуры оптимизационного поиска, имеющие полиномиальную вычислительную сложность и при этом обеспечивающие максимально достижимое на данном уровне неопределенности качество решения задачи классификации.
Об актуальности работы свидетельствует также ее поддержка грантами Российского фонда фундаментальных исследований (грант № 04-01-96078) и Министерства образования РФ (грант № Е02-2.1-23).
Цель и задачи работы. На основе методов распознавания образов необходимо разработать процедуры использования и коррекции априорной обучающей информации и алгоритмы построения решающих правил для решения задачи классификации при наличии неполной, неточной и противоречивой информации о значениях параметров состояния и классах объектов и при отсутствии информации о статистической природе измеряемых параметров объектов.
Для достижения цели диссертационного исследования необходимо решить следующие задачи.
1. Построить модель и разработать метод адаптации системы распознавания к цели решения задачи оценивания (управления), т.е. итеративного изменения и дополнения всего объема априорной информации о классах и параметрах состояния объектов заданной выборки, позволяющего согласовать противоречивые априорные данные при заданном допустимом уровне изменений, вносимых в априорную информацию.
2. Разработать, в рамках предлагаемого метода адаптации, алгоритмы построения коллективных решающих правил, обеспечивающие построение оценок достоверности каждого элемента априорной информации и классификацию объектов на основе этих оценок.
3. Разработать процедуру взаимодействия эксперта с системой распознавания, обеспечивающую итеративное согласование классификации, параметров состояния объектов предоставленной выборки, алфавита классов и словаря параметров состояния объектов, получаемых от эксперта и достигаемых при построении решающих правил.
4. Разработать программное обеспечение, реализующее предлагаемый метод и алгоритмы и использовать его для решения прикладных задач классификации в условиях неопределенности.
Методы исследования. Теоретические исследования основывались на применении методов распознавания образов и математической статистики, теории оптимизации, методов вычислительной геометрии, теории математического моделирования.
Научная новизна
1. Построена модель адаптации системы распознавания к неопределенной априорной информации, объединяющая процедуры обучения и самообучения и обеспечивающая целенаправленную коррекцию данных обучающей выборки на основе итеративного взаимодействия с экспертом.
2. Разработаны алгоритмы построения кусочно-линейных комитетных решающих правил: алгоритм коррекции классификации объектов, алгоритм кластеризации, алгоритм решения задачи дискриминантного анализа, алгоритм ускоренного построения комитета, обеспечивающие решение задачи классификации в рамках построенной модели адаптации.
3. Предложены процедуры совместного использования разработанных алгоритмов при взаимодействии с экспертами. Они позволяют решать задачи классификации с неточной, неполной и противоречивой априорной информацией о параметрах состояния, классах объектов, алфавите классов и словаре параметров состояния и при отсутствии информации о статистических законах распределения значений параметров распознаваемых объектов.
Практическая ценность и внедрение. Разработанные метод и алгоритмы позволяют решать задачи классификации при наличии неточной, неполной и противоречивой априорной информации. Это дает возможность существенно расширить область применения методов распознавания для поддержки принятия решений в системах управления и оценивания различного назначения. Алгоритмы построения комитетных решающих правил, использующие предложенную постановку задачи обучения в форме задачи адаптации к неопределенной априорной информации, имеют линейную вычислительную сложность. Это позволяет использовать их для решения задач оценивания и управления в режиме реального времени.
Создан пакет прикладных программ для программного комплекса Math Works Matlab, реализующих предложенный метод и алгоритмы. Предложенные в работе метод адаптации системы распознавания, алгоритмы построения решающих правил и их программная реализация были использованы при решении практических задач классификации:
1) в ОАО «Южноуральский завод «Кристалл» - для организации неразрушающего контроля качества кристаллов искусственного кварца на основе данных электромагнитного зондирования контрольных образцов, в условиях неточных измерений откликов кристаллов на зондирующие сигналы.
2) в Челябинской государственной медицинской академии и Челябинской городской клинической больнице №1 - для оценивания тяжести заболевания гипертрофической кардиомиопатией по данным электрокардиографического и эхокардиографического исследования пациентов при отсутствии достоверных априорных экспертных суждений о тяжести заболевания.
3) в лечебной практике неврологического отделения для больных с нарушениями мозгового кровообращения городской клинической больницы №3 г. Челябинска - для прогнозирования переходящих нарушений мозгового кровообращения у больных с дисциркуляторной энцефалопатией.
4) в ООО «Южно-Уральский сотовый телефон» - для прогнозирования спроса на услуги сотовой связи, с учетом влияния на него социально экономического состояния региона сбыта и информации 6 развитии рынка сотовой связи и социально-экономическом состоянии в других регионах. Апробация работы. Основные результаты работы докладывались на:
1) 31-й и 34-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2000, 2003);
2) 2-й Международной конференции молодых ученых «Актуальные проблемы современной науки» (Самара, 2001);
3) Междисциплинарной научной конференции «Новые биокибернетические и телемедицинские технологии 21 века для диагностики и лечения заболеваний человека» (Петрозаводск, 2002);
4) 12-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2003);
3) 15-й Международной научно-технической конференции «Экстремальная робототехника» (С.-Петербург, 2004).
Доклады по теме диссертации были приняты на:
1) Международную конференцию «Modeling & Simulation in Technical and Social Sciences» (Жирона, Испания, 2002);
2) Международную научно-техническую конференцию «Искусственный интеллект-2002» (Таганрог, 2002);
3) 2-ю Международную научно-практическую конференцию «Фундаментальные и прикладные исследования в системе образования» (Тамбов, 2004).
Публикации. По теме диссертации опубликованы 17 работ, в том числе 4 статьи в ведущих научных журналах, рекомендованных ВАК РФ. Материалы диссертации были использованы в 6 отчетах по НИР.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы (125 наименований), шести приложений. Основной текст диссертации изложен на 146 страницах и содержит 32 иллюстрации.
Место методов распознавания образов в задачах оценивания и управления
К постановке задачи распознавания образов прибегают в тех случаях, когда применение классических методов оценивания состояния и управления объектами той или иной природы оказывается затруднено. При этом сложности могут возникать в силу одной из следующих причин. 1. Уровень формализации соответствующей предметной области и доступная информация об объектах управления таковы, что не могут составить основу для синтеза математической модели, определяемой функциональными зависимостями, и, соответственно, допускающей применение стандартных аналитических или численных методов решения. . 2. Математическая модель, в принципе, может быть построена, однако ее синтез и изучение связаны с затратами, существенно превышающими выигрыш, приносимый искомым решением, либо выходят за пределы существующих технических возможностей.
Задача управления при использовании методов распознавания рассматривается как задача принятия решения о выборе одной из возможных стратегий управления объектом управления. Множество возможных стратегий управления при этом определяется множествами возможных значений управляющих параметров или оценок параметров состояния и возмущений, действующих на систему. Решение задачи распознавания соответствует определению класса возможных решений, в рамках которого конкретное решение уже может быть найдено с использованием других математических методов. При этом процесс принятия решения может быть многоступенчатым и включать в себя несколько процедур распознавания, уточняющих класс, содержащий решение (рис. 1.1).
Таким образом, методы распознавания образов могут использоваться в самых разнообразных задачах оценивания и управления, обладающих следующими свойствами: - существует некоторое множество объектов одинаковой природы (социально-экономические субъекты, конкурентные товары на рынке, группа больных с близкими формами заболевания, технические изделия с дорогостоящей производственной технологией и т.п.); - состояние каждого объекта можно достаточно полно описать совокупностью значений некоторых измеряемых параметров (параметров состояния); - для всех объектов существуют некоторые общие цели управления (оптимальное развитие, достижение наилучшего качества, излечение от болезни); при этом правило выбора оптимального управления или оптимальной оценки не удается сформулировать в виде единой целевой функции от значений параметров состояния; - вместо прямой функциональной зависимости между параметрами состояния и оптимальными управлениями (оценками) заданы некоторые экспертные оценки для конкретных объектов или конкретных реализаций их состояния. Указанные оценки качества, как правило, могут быть представлены в форме суждений экспертов о принадлежности каждого объекта к одному из нескольких возможных классов. Это позволяет перейти от задачи управления или оценивания к задаче определения классов объектов на основе информации об их параметрах состояния.
В исследованиях по теории задач распознавания [6,17,26,74] система распознавания рассматривается не как самостоятельная процедура, а как элемент системы управления (оценивания), связанный с различными другими ее элементами. При этом важно учитывать, что сложные системы распознавания, в общем случае, состоят не только из совокупности технических средств получения и переработки информации, но также и из групп высококвалифицированных специалистов (ЛПР), предназначенных для анализа промежуточных решений подзадач распознавания и выходных решений системы управления (оценивания). Можно выделить следующие особенности многоуровневых систем, позволяющих им выступать в качестве универсальных систем распознавания образов.
Во-первых, характер связей системы распознавания с другими распознающими устройствами (или с другими элементами системы управления) может быть самым различным, т.е. эти связи могут образовывать циклы, включающие различные элементы системы управления (в том числе и собственно объект управления). Это означает интерактивный характер взаимодействия системы распознавания с объектами, включенными в систему управления.
Во-вторых, в качестве распознающего устройства могут выступать эксперты. Это дает возможность, с одной стороны, постепенно увеличивать качество работы системы распознавания, привлекая все новые и новые знания экспертов, в том числе неформализованные. С другой стороны, появляется возможность "дообучения" самих экспертов. Тогда система распознавания становится источником новых знаний в той прикладной области, в которой она применяется.
В силу этих двух обстоятельств, понятие системы распознавания образов в последнее время стало рассматриваться шире, чем ранее. Система распознавания должна предусматривать возможность получения априорной информации различными способами:
Формы представления обучающей информации и ее неопределенности в задаче распознавания
Поскольку задача классификации всегда решается в рамках более общей задачи управления (оценивания) объектом (или объектами), обязательным атрибутом процесса управления является наличие цели управления. Роль этой цели в задаче классификации играет априорная информация о классах объектов обучающей выборки, полученная от экспертов. Т.е. классификация существенно зависит от того, как в дальнейшем будут использоваться решения, принятые системой классификации. Использование такой информации позволяет поставить задачу адаптации комитетного решающего правила к цели классификации в условиях неполной, неточной и противоречивой априорной информации и ее статистической неопределенности.
Рассмотренные выше формализации коллективных решающих правил и алгоритмы их построения обладают следующими особенностями. 1. Как следует из определения комитетных конструкций, в методе комитетов используется следующий принцип построения коллективного решения задачи с противоречивой системой ограничений: подмножества априорной информации, на которые разбивается 1 при выделении совместных подсистем в исходной системе ограничений, должны максимально равномерно покрывать множество всех возможных подсистем. Т.е. классификации, задаваемые отдельными членами комитета, должны иметь минимальное перекрытие, еще обеспечивающее существование корректной классификации при их объединении логикой согласования решений. Это позволяет минимизировать количество членов комитета в соответствии с критерием оптимальности (1.31). В данной работе будем использовать другой принцип: подзадачи должны быть такими, чтобы их решения как можно больше удостоверяли друг друга, т.е. доставляли минимум критерию (1.28). При этом комитет, доставляющих минимум такому целевому критерию, будет содержать уже возможно больше членов, чем это возможно. 2. В рамках алгебраического подхода, частным случаем которого является метод комитетов, модель распознавания должна обладать свойствами, гарантирующими существование алгоритма, правильно классифицирующего все объекты произвольной выборки. Это условие существенно ограничивает возможности алгебраического подхода. Если априорная информация содержит неопределенность и не позволяет строить корректный критерий качества классификации, выбор соответствующего индуктивного принципа обобщения информации делает процесс построения оптимального алгоритма условным относительно этого принципа. Целесообразно было бы параметризовать сам индуктивный принцип относительно неопределенности априорных данных и использовать возможность оптимизации его параметров в ходе построения распознающего алгоритма. Таким образом, адаптация решающего правила к неопределенной априорной информации может рассматриваться как процесс построения обобщенного комитетного решения. Под обобщением здесь понимается введение в критерий оптимальности комитета характеристик достоверности каждого элемента обучающей информации. Эти характеристики должны зависеть не только от априорного уровня неопределенности (неточности, неполноты) элементов априорной информации, но и от достигнутого уровня согласованности решений, принимаемых членами комитета, на этих элементах информации. Далее рассмотрим формализацию рассмотренного принципа на основе определения типов информации, обрабатываемых системой распознавания и возможных форм ее априорной неопределенности. Наряду с рассмотренными ранее (см. (1.2), (1.4)) типами априорной информации Х = {хт, т = 1, М}, V0 = {v , т = 1, М} (параметры состояния объекта управления в m-й реализации, и его класс), введем совокупность оценок значения {v , m = 1, М} для каждого объекта: Эти оценки формируются алгоритмом распознавания в результате построения распознающих операторов Ч А)(Х ,У,Х ), g = l,G из заданного класса (А). В рамках алгебраического подхода матрица (2.1) соответствует совокупности G информационных матриц вида (1.18). В случае комитетного решающего правила G=Q и значение v = v1 (xm) представляет собой класс, задаваемый m-му объекту і-м членом комитета. Далее также будем использовать для обозначения информации вида (2.1) термин «алгоритмические оценки параметра качества». При этом {v (xm), m = 1, М} можно также рассматривать как априорные оценки параметра качества.
Выбор меры несогласованности алгоритмических оценок для кусочно-линейных комитетных решающих правил
Если при проверке условия (3.12) пересчитывать ранги объектов после перемещения каждой гиперплоскости, то изменение положения комитета будет в значительной степени зависеть от порядка выбора гиперплоскостей, подлежащих перемещению. Поэтому целесообразно на каждой итерации алгоритма перемещать все гиперплоскости, а уже потом рассчитывать новые значения рангов объектов.
С учетом сделанных замечаний, алгоритм адаптации кусочно-линейного комитетного решающего правила к неопределенной априорной информации определяется следующей последовательностью действий.
Алгоритм адаптации решающего правила к неопределенной априорной информации, использующий в качестве решающих правил члены аффинного комитета большинства (АА-КРП). 1. Задать начальное положение комитета (случайным образом, по формулам (3.17), или с помощью какого-либо алгоритма построения комитета, оптимального по критерию (1.28)). 2. Рассчитать ранги всех объектов обучающей выборки по формуле (3.7). 3. Выбрать для обработки очередную гиперплоскость-член комитета. 4. Попытаться найти еще не рассмотренную пару правильно и неправильно классифицированных ею объектов, удовлетворяющих условиям (3.8), (3.9), (3.12). 5. Если объекты с требуемыми свойствами не найдены, то перейти к шагу 7, иначе попытаться изменить положение гиперплоскости так, чтобы обеспечить выполнение условия (3.13). 6. Если положение гиперплоскости удалось изменить, то перейти к шагу 7, иначе перейти к шагу 4. 7. Если все гиперплоскости уже рассмотрены, то перейти к шагу 8, иначе перейти к шагу 3. 8. Если хотя бы одна из гиперплоскостей изменила свое положение, то перейти к шагу 2, иначе искомый комитет найден. Соответствие между шагами общего алгоритма адаптации (АА), алгоритма коррекции матрицы алгоритмических оценок (АК) и рассмотренной его реализацией для случая комитетных решающих правил (АА-КРП) следующее. Шаг (1) АА соответствует шагу (1) АА-КРП. Шаг (2) АА соответствует шагам (1)-(5) АК и шагу (8) АА-КРП. Соответствие между шагами (1)-(5) АК и шагами (1)-(7) АА-КРП следующее: - шаг (1) АК соответствует определению функционала несогласованности Я (У)вформе(3.6); - шаги (2)-(3) АК соответствуют шагам (2)-(4) АА-КРП; - шаг (4) АК соответствует шагу (5) АА-КРП; - шаг (5) АК соответствует шагам (6)-(7) АА-КРП; Шаг (3) АА соответствует применению формулы (3.4). Шаг (4) АА выполняется автоматически, за счет использования формулы (3.4) при расчете значений элементов матрицы V. На каждой итерации алгоритма необходимо многократно проводить две вычислительных операции, определяющие реализацию алгоритма АК в классе аффинных комитетов большинства: выбор активного подмножества, т.е. поиск пары объектов х и хи - кандидатов на изменение рангов, и проверку возможности перемещения гиперплоскости, такого, что будет выполняться условие (3.13). Вычислительная сложность этих операций будет определять аналогичный показатель для алгоритма в целом. Рассмотрим их реализацию. 3.2.3 Процедура выбора активного подмножества при поиске решающего правила Для поиска пар объектов хр и хи, участвующих в базовой операции изменения рангов объектов, необходимо организовать перебор всех возможных сочетаний (р,и): р є I(s), иє{1, ...,M}\I(s), удовлетворяющих условиям (3.8), (3.9), (3.12). С целью сокращения перебора объекты, удовлетворяющие условию (3.8) и удовлетворяющие условию (3.9), соответственно, необходимо представить в виде двух упорядоченных списков: первые - в порядке возрастания рангов, вторые - в порядке убывания. Тогда порядок выбора пар объектов, реализующий шаги (4)-(6) алгоритма АА-КРП следующий: 1. Из первого списка выбрать очередной объект-кандидат на исключение из множества I. 2. Если для пары, состоящей из выбранного объекта первого списка и объекта, стоящего первым во втором списке, условие (3.12) уже не выполняется, то прекратить перебор. 3. Из второго списка выбрать очередной объект, номер которого мог бы быть присоединен к множеству I. 4. Если для выбранной пары объектов еще выполняется условие (3.12), то производится попытка перемещения гиперплоскости, иначе перейти к шагу 7. 5. Если удалось изменить положение гиперплоскости так, что выполнены условия (3.15), то искомая пара объектов найдена и перебор завершается, иначе перейти к шагу 6. 6. Если достигнут конец второго списка, то перейти к шагу 7, иначе перейти к шагу 3. 7. Если достигнут конец первого списка, то перебор завершается и данная гиперплоскость остается в исходном положении, иначе перейти к шагу 1. В ходе перебора пар объектов необходимо использовать специальный элемент- фиктивный объект. Он считается правильно классифицированным любой гиперплоскостью, но при этом имеет ранг -со. Таким образом, первый список всегда начинается с этого объекта и в паре с любым элементом второго списка он удовлетворяет условию (18). Такой элемент необходим для того, чтобы обеспечить увеличение рангов объектов, когда это возможно без уменьшения рангов других объектов. Указанный порядок рассмотрения объектов обеспечивает также снижение количества итераций самого алгоритма перемещения комитета. Согласно описанию процесса перебора, из всего множества пар объектов будут выбраны такие объекты хр и хи, что величина (ru -г ) будет иметь максимально возможное значение. Это, в свою очередь, обеспечивает максимальное уменьшение значения функционала несогласованности R (V) на данной итерации алгоритма адаптации.
Схемы построения системы распознавания при решении задач классификации
В соответствии с рассмотренной общей постановкой задачи распознавания образов (1.1), необходимо, чтобы система распознавания обеспечивала систему управления такой информацией, которая могла бы быть использована с наибольшей эффективностью. В качестве входных и выходных данных для системы распознавания можно рассматривать алфавит классов, словарь параметров состояния объектов, классификацию объектов и построенные ранее решающие правила. Рассмотренные выше алгоритмы обеспечивают обработку всех указанных видов информации и позволяют построить единую систему распознавания. Рассмотрим возможности каждого из предложенных алгоритмов по обработке неточной, неполной и противоречивой априорной информации.
Базовый алгоритм адаптации (АА-КРП). Входной и выходной информацией для алгоритма являются классификации объектов и комитетные решающие правила. Согласно (2.13), коррекции в ходе работы алгоритма подвергается только классификация, а параметры состояния объектов остаются неизменными. Как было отмечено в гл. 2, вопрос о коррекции значений X, либо , либо их совместной коррекции при выполнении преобразования Y(X,V) не может быть решен однозначно в пользу одного из типов информации. Измененные значения классов объектов могут нести дополнительную информацию для экспертов. При этом эксперты могут соглашаться или не соглашаться с отдельными коррективами в классификации. Таким образом, можно организовать итерационный процесс взаимодействия между экспертами и системой распознавания. В ходе этого процесса они обмениваются информацией, выраженной в форме классификаций объектов обучающей выборки. Если эксперт не соглашается с решением системы распознавания о коррекции классов каких-либо объектов, он может совершить очередную итерацию взаимодействия с системой распознавания. Для этого необходимо возобновить выполнение алгоритма АА-КРП, предварительно выполнив относительно каждого из «спорных» объектов одно из следующих действий: - исключить объект из выборки; - провести дополнительное исследование объекта для уточнения его класса; - изменить значения некоторых параметров состояния объекта; - провести измерение некоторых параметров состояния объекта (если на предыдущей итерации взаимодействия с системой распознавания значения этих параметров не включались в априорную информацию); - зафиксировать классы некоторых объектов, как это указано ниже. Такой порядок применения алгоритма адаптации позволяет предоставлять принятие соответствующих решений об изменении классов объектов, либо их параметров состояния, эксперту. При этом решающее правило постепенно приближается к неизвестной истинной границе между классами, и качество работы системы распознавания при классификации новых объектов возрастает. 2. Алгоритм кластеризации. Он задает разбиение одного класса объектов на подклассы, соответствующие последовательным поддиапазонам значений параметра качества. Как показано выше, эту процедуру можно рассматривать как процесс выделения нескольких подклассов в пределах одного из априорно заданных классов. Т.е. входными данными для алгоритма являются априорный алфавит классов, классификация объектов и соответствующее ей комитетное решающее правило. Выходные данные - это новый алфавит классов и решающие правила, классифицирующие объекты обучающей выборки в этом алфавите. 3. Алгоритм решения задачи дискриминантного анализа. Он имеет значение не как самостоятельная процедура, а как совокупность дополнительных ограничений, которые можно использовать в других алгоритмах. Возможен вариант постановки задачи обучения, когда эксперты способны выделить в обучающей выборке два подмножества: объекты, классы которых определены безошибочно и объекты, в отношении классов которых есть сомнения. Такое разделение может возникнуть в силу различных причин: - объекты из разных подмножеств априорно классифицировались экспертами на основе разной информации (одни по результатам более полного обследования, чем другие); - объекты из разных подмножеств классифицировались разными экспертами (имеющими разный уровень квалификации); - часть объектов имеет ярко выраженные признаки (не используемые в наборе параметров) принадлежности к определенному классу; - для одних классов принадлежность к ним объектов принципиально можно определить точно, а для других - нет. В этом случае целесообразно использовать смешанный алгоритм обучения, т.е. ранги всех объектов вычислять по формуле (4.4), а ограничения вида (4.5) „ наложить только на объекты из первого подмножества. С учетом рассмотренных особенностей предложенных алгоритмов, система распознавания может функционировать в следующих двух режимах. 1. Режим извлечения информации об образах из данной предметной области. Все рассмотренные алгоритмы могут обмениваться информацией и выполняться многократно и в произвольном порядке. Как указано выше, при работе системы распознавания в таком режиме постепенно увеличивается достоверность информации всех типов: алфавита классов, словаря параметров, классификации объектов обучающей выборки. В результате работы системы распознавания строятся решающие правила, приближающиеся к истинным зависимостям классов объектов от значений их параметров. 2. Режим автоматической классификации. В этом режиме использование способностей экспертов не требуется. На вход системы распознавания поступают данные о параметрах новых объектов, а выходные данные - это определенные автоматически, в соответствии с решающими правилами, классы этих объектов. При практическом использовании системы распознавания возможно и желательно одновременное ее функционирование в обоих режимах. Пусть в некоторый момент времени задача распознавания уже решена для заданной выборки, т.е. построены решающие правила, определяющие классификацию объектов. Тогда классификация этими решающими правилами любого нового объекта обеспечивает получение информации двух видов: сведений для экспертов о классе объекта и сведений для системы распознавания о положении объекта в пространстве параметров относительно решающих правил.
