Содержание к диссертации
Введение
1 Обзор подходов к решению задачи классификации объектов в условиях параметрической неопределенности классов 19
1.1 Общая структура и задача системы классификации объектов 19
1.1.1 Структура системы классификации объектов 19
1.1.2 Задача распознавания классов объектов
1.2 Постановка задачи классификации объектов в условиях параметрической неопределенности и пересечения классов 22
1.3 Способы представления классов объектов в каталоге эталонных значений 26
1.4 Детерминистский подход к решению задачи классификации
1.4.1 Метод построения эталонов 29
1.4.2 Метод дробящихся эталонов
1.5 Классификация методом кластерного анализа 32
1.6 Использование нечеткой логики при классификации объектов 34
1.7 Нейросетевой подход к классификации объектов 36
1.8 Статистический подход к классификации объектов 39
1.9 Классификация методом Г.В. Шелейховского. Принцип максимизации энтропии 42
1.10 Проблема сходимости решения задачи классификации методом Г.В. Шелейховского 49
1.11 Транспортная задача 54
1.12 Выводы 60
2 Разработка комбинированного метода и алгоритмов классификации с системной максимизацией энтропии в условиях параметрической неопределенности классов 64
2.1 Разработка комбинированного метода классификации 64
2.2 Анализ качественной характеристики достоверности классификации при выполнении процедуры последовательного нормирования 78
2.3 Разработка способа и алгоритма предварительного анализа входных данных 81
2.4 Проблема сходимости и ее решение в задаче классификации объектов при использовании процедуры последовательного нормирования 86
2.5 Исследование возможности сокращения вычислительной трудоемкости процедуры последовательного нормирования и разработка алгоритма сокращения классификационной матрицы 93
2.6 Разработка алгоритма списочного представления классификационной матрицы 103
2.7 Анализ результатов классификации при формировании новых классов и разработка алгоритма 107
2.8 Выводы 110
3 Разработка программы реализации комбинированного метода классификации 114
3.1 Функциональные возможности программы 114
3.2 Структурная схема программы реализации комбинированного метода 117
3.3 Программа анализа параметров объектов 120
3.3.1 Представление четырехмерного параметрического пространства . 121
3.3.2 Режим анализа расположения объектов относительно классов 124
3.3.3 Режим группового анализа расположения объектов относительно классов 124
3.3.4 Режим динамического анализа информации о новых объектах 126
3.3.5 Представление результатов работы программы 127
3.4 Программа реализации работы процедуры последовательного нормирования 128
3.4.1 Основные режимы работы программы 130
3.4.2 Представление результатов работы программы
3.5 Программная реализация спискового представления классификационной матрицы 135
3.6 Выводы 137
4 Экспериментальные исследования разработанного метода классификации на основе компьютерного моделирования 139
4.1 Методика проведения экспериментальных исследований 139
4.2 Исследование эффективности алгоритма предварительного анализа входных данных 141
4.3 Анализ эффективности применения списочного алгоритма представления классификационной матрицы 146
4.4 Оценка влияния сокращения классификационной матрицы на решение задачи классификации 151
4.5 Проверка работоспособности алгоритма анализа информации о новых объектах 154
4.6 Исследование проблемы сходимости задачи классификации при использовании процедуры последовательного нормирования 156
4.7 Пример комплексной реализации комбинированного метода при компьютерном моделировании 158
4.8 Итоговая сравнительная оценка общей вычислительной трудоемкости комбинированного метода 166
4.9 Выводы 168
Заключение 170
Список сокращений и условных обозначений 174
Список источников 175
- Постановка задачи классификации объектов в условиях параметрической неопределенности и пересечения классов
- Проблема сходимости решения задачи классификации методом Г.В. Шелейховского
- Исследование возможности сокращения вычислительной трудоемкости процедуры последовательного нормирования и разработка алгоритма сокращения классификационной матрицы
- Оценка влияния сокращения классификационной матрицы на решение задачи классификации
Введение к работе
Актуальность темы исследования. При современном уровне развития техники использование ЭВМ в автоматизированных системах управления (АСУ) не ограничивается лишь организацией сбора, накопления и первичной переработки информации. Работа АСУ может происходить в условиях, затрудняющих оценку состояния объекта управления. При оценке состояния объекта управления для принятия решения часто используются алгоритмы классификации объектов, реализованные в виде экспертной системы поддержки принятия решений, интегрированной в состав АСУ. На практике решение задач классификации объектов проходит в условиях различного рода ограничений в представлении исходных данных, требований к алгоритмической реализации функциональных возможностей и вычислительным средствам.
Одним из видов ограничений представления исходных данных является
отсутствие достоверной информации о параметрах известных классов. В таких случаях параметры классов в каталоге эталонных значений известных классов (базе знаний экспертной системы) представлены в виде допустимых интервалов, при этом функция распределения вероятности внутри интервала неизвестна. Попадание параметров объекта классификации в соответствующие интервалы говорит о существовании некоторой вероятности отнесения текущего объекта к известному классу из каталога. При таком представлении данных не исключена ситуация пересечения классов вследствие перекрытия допустимых интервалов. Каталог может содержать неполный перечень всех существующих классов объектов.
С учетом описанной выше неопределенности необходимо определять вероятность принадлежности объекта классификации к конкретному классу, из каталога известных классов или к классу «новых» (неопознанных) объектов.
Подобная задача возникает, например, при классификации радиотехнических
объектов – источников излучений. Классификация радиотехнических объектов
представляет собой один из важнейших компонентов систем управления и обработки
информации, автоматизированных систем и систем принятия решений. Актуальной
проблемой является классификация радиотехнических объектов в информационных
конфликтах противоборствующих сторон, где одна сторона формирует
радиотехнические объекты на входе АСУ, а вторая обеспечивает селекцию и распознавание (классификацию) этих объектов с целью оперативного формирования решения в виде реакции на выявленную окружающую обстановку. Особенностями систем такого рода являются: прием входной информации в реальном времени и необходимость предельно возможного сокращения времени реакции АСУ.
На практике группу одновременно наблюдаемых объектов составляют не только «полезные» объекты классификации, но и объекты, появление которых связано со сложной помехонасыщенной обстановкой.
Формирование методологии решения рассматриваемой задачи классификации
осуществлялось в процессе творческой работы, сочетающейся с активным
взаимодействием со специалистами в данной области и с апробацией получаемых
результатов на различных профильных конференциях. Среди ученых, работы
которых в наибольшей степени относятся к решению рассматриваемых в данной
диссертационной работе проблем, следует выделить Брэгмана Л.М.,
Шелейховского Г.В., Кряковского Б.С., Волкова В.В., Шпака В.Ф., Синкхорн Р. В работах Вильсона А.Дж., Трухаева Р. И., Куренкова Н. И., Дженсена Р. Торккола К. приводятся методы, учитывающие энтропию при решении информационных задач.
Наибольший интерес для использования в решении поставленной задачи классификации представляет известный метод Г.В. Шелейховского. В работе Шпака В.Ф. приведено описание применения данного метода в радиотехнических системах при решении задачи классификации радиотехнических объектов. Этот метод, основанный на принципе максимизации энтропии, предполагает проводить классификацию одновременно наблюдаемых объектов как на основе сравнения параметров объектов классификации с параметрами известных классов, так и на
основе сравнения набора параметров всех одновременно наблюдаемых объектов между собой. Метод позволяет получить наименее сомнительное распределение вероятностей принадлежности объектов классификации к известным классам из каталога. Прямое решение поставленной задачи с использованием данного метода требует большого объема вычислений, так как метод является итерационным. Одной из наиболее значимых проблем данного метода является сходимость задачи классификации, рассмотренная в диссертационной работе. В связи с отмеченным выше, исследование возможности решения задачи классификации объектов в условиях параметрической неопределенности и пересечения классов, нацеленное на повышение качественных характеристик классификации, является актуальным.
Целью работы является разработка и исследование высокопроизводительных метода и алгоритмов классификации объектов в условиях параметрической неопределенности и пересечения классов на основе методологии с системной максимизацией энтропии, обеспечивающих минимизацию временных затрат при динамическом решении задачи классификации в реальном масштабе времени и устойчивость к входным данным.
Объектом исследования является экспертная система поддержки принятия решений о классификации объектов.
Предметом исследования являются методы и алгоритмы классификации объектов в условиях параметрической неопределенности и пересечения классов.
Научная задача, решаемая в диссертационной работе, - разработка и
исследование обладающего повышенными характеристиками метода классификации
объектов на основе совокупностей характерных признаков в условиях
параметрической неопределенности и пересечения классов.
Для достижения поставленной цели в диссертации были решены следующие задачи:
- анализ известных подходов к классификации объектов в условиях
параметрической неопределенности классов;
- исследование математической постановки задачи в методе Г.В. Шелейховского
и разработка комбинированного метода классификации, позволяющего применить
параметрическое пространство в качестве основы для проведения анализа взаимного
расположения объектов классификации относительно классов из каталога эталонных
значений;
- решение проблемы сходимости задачи классификации, формулировка и
доказательство теоремы о существовании особых (проблемных) объектов
классификации и их влиянии на процесс сходимости;
исследование качественной характеристики достоверности классификации при выполнении процедуры последовательного нормирования;
разработка способа и алгоритма предварительного анализа входных данных, позволяющего оценить параметры входных данных на подготовительном этапе работы метода классификации и принять решение относительно целесообразности применения процедуры классификации;
- исследование возможности сокращения вычислительной трудоемкости
процедуры последовательного нормирования и разработка алгоритма сокращения
классификационной матрицы;
- разработка и исследование алгоритма представления классификационной
матрицы в виде циклически связанных ортогональных списков, позволяющего
увеличить скорость доступа к данным и сократить необходимый объем памяти ЭВМ
при выполнении процедуры классификации;
- разработка и исследование алгоритма анализа результатов классификации при
формировании новых классов;
- разработка программных средств, позволяющих экспериментально решать
задачу классификации объектов в условиях параметрической неопределенности и
пересечения классов;
- проведение исследований на основе компьютерного моделирования,
подтверждающих повышение характеристик комбинированного метода
классификации по отношению к известным методам.
Методы исследования. Исследование проведено с использованием таких методов, как энтропийные методы классификации, детерминистские методы и алгоритмы распознавания, логика кластерного анализа, классификация объектов в условиях неопределенности, статистический анализ.
Достоверность и обоснованность результатов диссертационной работы подтверждается полнотой и корректностью теоретических обоснований, совпадением теоретических и экспериментальных результатов компьютерного моделирования, публикациями, апробацией работы на международных и всероссийских научно-технических конференциях.
Научная новизна работы заключается в следующем:
1. Разработан комбинированный метод классификации объектов при
параметрической неопределенности и пересечении классов, базирующийся на
принципе максимума энтропии. Предложенный метод позволяет снизить
вычислительную трудоемкость при решении задачи классификации по сравнению с
известным методом в среднем в два раза и отличается от известного тем, что с целью
снижения вычислительной трудоемкости и обеспечения работоспособности
предложены и используются способы выполнения предварительного анализа входных
данных и решения вопроса о целесообразности применения процедуры
классификации, сокращения классификационной матрицы, дополнения каталога
эталонных значений информацией о новых классах, выявления и предотвращения
проблемы сходимости итерационного процесса.
-
Впервые разработаны способ и алгоритм предварительного анализа входных данных, позволяющие на подготовительном этапе работы решать вопрос о целесообразности применения процедуры последовательного нормирования по отношению к данным, поступившим на обработку. Данный алгоритм позволяет сократить количество операций сравнения и, соответственно, вычислительную трудоемкость на подготовительном этапе работы метода классификации по статистическим оценкам в среднем в два раза.
-
Выявлено условие и предложен способ устранения несходимости решения задачи классификации при параметрической неопределенности и пересечении классов. Предложенный способ устранения несходимости обеспечивает также минимизацию вычислительной трудоемкости, соответствующую решению данной задачи при отсутствии проблемы сходимости. Сформулирована и доказана теорема о существовании особых (проблемных) объектов классификации и их влиянии на процесс сходимости.
4. Впервые разработаны способ и алгоритм сокращения классификационной
матрицы, позволяющие уменьшить ее размерность и, соответственно, снизить
вычислительную трудоемкость при выполнении процедуры последовательного
нормирования в предложенном комбинированном методе приблизительно в два раза.
Снижение вычислительной трудоемкости варьируется в пределах от максимально
необходимой при отсутствии возможности сокращения до полного исключения
выполнения процедуры классификации и, соответственно, вычислительных затрат в
случае вырождения классификационной матрицы.
5. Впервые разработаны способ и алгоритм анализа результатов классификации,
обладающие возможностью автоматического (автоматизированного) дополнения
каталога эталонных значений актуальной информацией о новых классах, что
существенно облегчает работу персонала по сбору и обработке новой информации
(формированию эмпирического знания).
Основные положения, выносимые на защиту:
- комбинированный метод классификации объектов при параметрической
неопределенности и пересечении классов, базирующийся на принципе максимума
энтропии и реализуемый на основе выполнения предварительного анализа входных
данных, сокращения классификационной матрицы, дополнения каталога эталонных значений информацией о новых объектах, выявления и предотвращения проблемы сходимости итерационного процесса, обеспечивающий минимизацию временных затрат при динамическом решении задачи классификации в реальном масштабе времени и устойчивость к входным данным;
- условия несходимости итерационного процесса в задаче классификации при
использовании процедуры последовательного нормирования и способ решения
проблемы сходимости.
Научная значимость полученных результатов:
1. В основу решения задачи классификации объектов в диссертационной работе
положен оригинальный математический аппарат, разработанный ученым
Г.В. Шелейховским и известный как метод Г.В. Шелейховского. Важной
особенностью данного аппарата является возможность решения поставленной в
диссертации задачи классификации с получением оптимизированной оценки
вероятности отнесения объектов к определенным классам на основе критерия -
максимума энтропии.
В диссертации проведен глубокий анализ данного математического аппарата, выявлены закономерности и особенности взаимосвязей между признаками объектов в исходной расчетной матрице. На основе данных исследований в рамках разработанного комбинированного метода предложены методики, нацеленные на сокращение вычислительной трудоемкости решения задачи классификации.
В итоге получена модифицированная математическая реализация метода
Г.В. Шелейховского, воплощенная в предложенном комбинированном методе,
отличающаяся возможностью существенного сокращения вычислительной
трудоемкости при решении рассматриваемой задачи классификации.
2. Исследована имеющая место при решении поставленной задачи
классификации на основе метода Г.В. Шелейховского проблема – несходимость
итерационного процесса. Выявлены условия несходимости (наличие проблемных
объектов). Сформулирована и доказана теорема о существовании и единственности
условий, приводящих к несходимости. Предложен способ обеспечения
работоспособности комбинированного метода, основанный на выявлении и
устранении условий несходимости (проблемных объектов).
Практическая ценность. Предложенные метод и алгоритмы имеют значимость
для решения практических задач, например, при классификации радиотехнических
объектов в информационных конфликтах противоборствующих сторон, а также
зондировании поверхности земли, диагностике в биологии и медицине (например, на
фоне эпидемий) и т.д. Представленная и реализованная в диссертации постановка
задачи ориентирована, в первую очередь, на классификацию радиотехнических
объектов. Особый интерес представляет использование предлагаемого метода для
реализации экспертной системы поддержки принятия решений, интегрированной в
АСУ, при решении задач большой размерности в условиях реального масштаба
времени. Разработанный комбинированный метод позволяет снизить
вычислительную трудоемкость в среднем в два раза по сравнению с аналогом и благодаря этому существенно сократить время реакции АСУ на окружающую обстановку. Новый метод обеспечивает сходимость реализуемого итерационного процесса при любых наборах входных данных в соответствии с постановкой задачи. Кроме того, обеспечивается возможность анализа информации о новых объектах и формирования новых классов. Низкая требовательность метода к вычислительным ресурсам обуславливает перспективные возможности его практического применения.
Реализация и внедрение результатов работы. Практические и теоретические результаты работы внедрены:
- на предприятии АО «Таганрогский научно-исследовательский институт связи»;
- в учебном процессе на кафедре математического обеспечения и применения
ЭВМ института компьютерных технологий и информационной безопасности
федерального государственного автономного образовательного учреждения высшего образования «Южный федеральный университет».
Апробация работы.
Основные результаты работы докладывались и обсуждались на международных,
всероссийских научно-технических конференциях, в том числе на: Конгрессе по
интеллектуальным системам и информационным технологиям «IS&IT’16», пос.
Дивноморское, 2016г.; Научно-технической конференции «Состояние, проблемы и
перспективы создания корабельных информационно-управляющих комплексов.», г.
Москва, 2013г.; 19 международной научно-технической конференции «Радиолокация,
навигация, связь», г. Воронеж, 2013г.; Всероссийской научно-технической
конференции «Теоретические и прикладные проблемы развития и совершенствования
автоматизированных систем управления военного назначения», г. Санкт-Петербург,
2014г.; 21 международной научно-технической конференции «Радиолокация,
навигация, связь», г. Воронеж, 2015г.; Межведомственной научно-технической
конференции «Неделя военной науки», г. Санкт-Петербург, 2015г.; Всероссийской
научно-технической конференции "Студенческая наука для развития
информационного общества", г. Ставрополь, 2015г.; Второй всероссийской научно-
технической конференции «Теоретические и прикладные проблемы развития и
совершенствования автоматизированных систем управления военного назначения», г.
Санкт-Петербург, 2015г.; Всероссийской научно-практической конференции
«Радиоэлектронная борьба: этапы, методология, направления развития», г. Воронеж, 2015г.
На 21-й международной научно-технической конференции «Радиолокация, навигация, связь» в г. Воронеж, доклад на тему «Комбинированный подход, как путь повышения производительности при решении задач классификации» был признан лучшим докладом.
Публикации. Результаты работы отражены в 21 публикации, из них 4 статьи в изданиях, рекомендованных ВАК, 8 статей в прочих изданиях и 9 докладов в материалах конференций.
Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка источников и четырех приложений. Материалы работы изложены на 212 страницах машинописного текста, содержат 34 таблицы, 48 рисунков, 98 библиографических источников и 27 страниц приложений.
Постановка задачи классификации объектов в условиях параметрической неопределенности и пересечения классов
Задача классификации объектов в условиях параметрической неопределенности и пересечения классов характеризуется следующими особенностями: 1) на вход классификатора в реальном времени с определенной периодичностью поступает множество N векторов признаков одновременно наблюдаемых объектов X; каждый объект характеризуется значениями признаков xi, i=1,…,N (вектор признаков); количество разновидностей объектов - десятки-сотни; 2) эталонные значения известных классов характеризуются параметрической неопределенностью, которая обусловлена отсутствием достоверной информации о значениях параметров известных классов объектов, неполным перечнем всех возможных классов, а также ограниченной точностью измерения параметров объектов; поэтому в каталоге эталонных значений известных классов для каждого параметра любого класса вводится допустимый интервал; 3) попадание всех параметров объекта классификации в соответствующие допустимые интервалы класса из каталога говорит о возможности отнесения анализируемого объекта к данному классу с некоторой вероятностью. Причем эту вероятность невозможно оценить исходя из места попадания параметра в интервал относительно границ или центра данного допустимого интервала, так как интервал является следствием отсутствия достоверной информации о значениях параметров известных классов объектов. Таким образом, можно предположить лишь равномерное распределение вероятностей в указанных интервалах; 4) в связи с тем, что классы в каталоге эталонных значений представлены допустимыми интервалами, существует возможность их пересечения, а следовательно, не исключена ситуация отнесения объекта классификации к более, чем одному классу; 5) используемая методология решения задачи классификации должна характеризоваться возможностью оптимизации в получаемых оценках вероятностей принадлежности объектов к соответствующим классам; 6) каталог эталонных значений классов содержит неполный перечень всех возможных классов, в связи с чем необходимо в непрерывном процессе выявлять закономерности возникновения неизвестных (новых) объектов с целью дополнения указанного каталога (например, в автоматизированном режиме работы системы с привлечением оператора-эксперта).
Необходимость решения задачи классификации, соответствующей указанным требованиям, возникает при классификации радиотехнических объектов [17]. Также подобная задача может решаться, например, при зондировании поверхности земли, диагностике в биологии и медицине (например, на фоне эпидемий) и т.д. [12, 14, 23, 24]. Обычно задачи подобного рода возлагаются на АСУ и относятся к рангу задач оценки состояния объекта управления [25]. Обобщенная схема цикла управления АСУ приведена на рисунке 1.2. АСУ , Измерение параметров текущего состояния СОУ s Идентификация состояния СОУ и формирование эмпирического знания Ф Прогнозирование поведения СОУ и корректировка работы АСУ оператором Выработка управляющего воздействия Оказание управляющего воздействия на СОУ і Сложный объект s Окружающая среда управлен ия (СО У) ч Рисунок 1.2 - Обобщенная схема цикла управления АСУ.
Объект управления представляет собой сложную систему [25]. Цикл управления АСУ - повторяющийся цикл, состоящий из следующих видов работ [26]: - измерение параметров текущего (исходного) состояния сложного объекта управления (СОУ); - идентификация состояния СОУ и формирование эмпирического знания; - прогнозирование поведения СОУ при условии отсутствия управляющего воздействия (изучение тенденций) и корректировка работы АСУ оператором; - выработка управляющего воздействия; - оказание управляющего воздействия на СОУ. Каждая функция АСУ реализуется совокупностью задач и операций. Функции АСУ подразделяют на простые и составные [27]. Операции, составляющие цикл управления АСУ, условно можно разделить на три основные группы, формирующие функции АСУ: 1) оценка состояния - к данной группе относятся операции измерения параметров текущего состояния СОУ и идентификация состояния СОУ; 2) принятие решения - прогнозирование поведения СОУ и выработка управляющего воздействия; 3) исполнение решений - оказание управляющего воздействия на СОУ. Многие АСУ предъявляют жесткие временные требования к выполнению цикла управления. Из этого следует, что вопрос минимизации вычислительной нагрузки методов, в реальном времени решающих задачи, составляющие цикл управления, является актуальным и очень важным. При этом задача классификации объектов (часто это задача большой размерности) обычно входит в состав группы задач оценки состояния. Чем быстрее выполняются операции, составляющие группу оценки состояния, тем большее пространство для маневра имеют группы операций принятия и исполнения решений в пределах жестких временных рамок. Исходя из этого, а также принимая во внимание особенности постановки задачи классификации, целесообразно возложить функции АСУ по идентификации состояния СОУ и формированию эмпирического знания на динамическую экспертную систему, интегрированную в состав АСУ с целью поддержки принятия решений. Экспертные системы позволяют, используя знания специалистов о некоторой конкретной узкоспециализированной предметной области и в пределах этой области, принимать решения на уровне эксперта-профессионала. Наибольшее внимание сегодня привлечено к экспертным системам, способным принимать решения в масштабе времени, близком к реальному, т.е. к динамическим системам. [2]. По мнению специалистов, в недалекой перспективе динамические экспертные системы будут играть ведущую роль во всех фазах проектирования, разработки, производства, распределения, продажи, поддержки и оказания услуг [7]. В приложении к решению поставленной задачи представляют интерес следующие характерные особенности экспертной системы: способность принимать решения в условиях неопределенности; четкое разделение декларативных и процедурных знаний; способность пополнять базу знаний; результат выдается в виде конкретных рекомендаций для действий в сложившийся ситуации [8]. Также важно отметить, что степень участия персонала в работе АСУ может быть различной, однако предоставление оператору средств настройки работы в процессе эксплуатации с целью повышения общей функциональности системы на основе формирования эмпирического знания является важной задачей.
Проблема сходимости решения задачи классификации методом Г.В. Шелейховского
Одним из примеров практического применения алгоритмов классификации в условиях параметрической неопределенности классов является задача классификации радиотехнических объектов [17]. Эта задача относится к рангу задач распознавания [48 - 51] и является одной из задач, возлагаемых на радиотехнические АСУ. Такие АСУ выполняют многочисленные операции, составляющие цикл управления, в пределах ограниченного интервала времени (см. разд.1.2). Задача классификации объектов входит в состав группы оценки состояния из цикла управления АСУ (разд.1.2), а следовательно, от качества и времени решения данной задачи во многом зависит вся последующая работа АСУ.
Измерительная аппаратура, входящая в состав АСУ, предназначена для сбора информации о внешней обстановке и параметрах объектов классификации [52]. Необходимо определить вероятность принадлежности объекта классификации к конкретному классу (или нескольким классам), занесенному в каталог эталонных значений, или к классу «новых» (неопознанных) объектов.
Каталог эталонных значений является основой для классификации обнаруженного объекта по значениям его параметров, представленных в виде совокупности входных признаков. Данный каталог хранится в памяти АСУ [17].
Общепринятые подходы к решению задачи классификации предполагают сравнение параметров обнаруженного объекта с аналогичными параметрами, характеризующими известные классы объектов из каталога. Однако возможны ситуации, когда в одном и том же каталоге для одного объекта классификации существует несколько классов [17]. Это объясняется тем, что зачастую реальный процесс классификации объектов протекает в условиях неопределенности, отличающейся: - отсутствием достоверной информации о значениях параметров известных классов объектов; - неполным перечнем всех возможных классов объектов; - ограниченной точностью измерения.
Для более полного учета информации о группе одновременно наблюдаемых объектов предлагается производить их классификацию, как на основе сравнения замеренных параметров с параметрами известных классов, так и на основе сравнения набора параметров всех объектов классификации между собой [17, 13].
В каталоге эталонных значений для каждого i-го параметра любого j-го класса объектов вводится некоторый допустимый интервал [Путіп; Путах]. Данный интервал гарантирует допустимые пределы изменения параметра объекта с некоторой вероятностью. Таким образом, конечный результат классификации напрямую будет зависеть от качества информации, представленной в каталоге эталонных значений. Каждому наблюдаемому к- му объекту классификации можно поставить в соответствие его классификационный образ [17, 53]: Ак = {SkJ}, представляющий собой вектор - строку, состоящую из нулей и единиц: «0», если хотя бы один 1-й параметр к- го объекта не попадает в интервал изменения данного параметрау-го класса объектов. (1.7) 8k,j = «1», если все измеренные параметры к- го объекта попадают в интервал изменения данного параметра
Таким образом, 0 означает невозможность отнесения данного к-го объекта к у-му классу, а 1 не исключает такой возможности. Так как все объекты обнаруживаются и наблюдаются одновременно одним и тем же измерительным устройством, различие классификационных образов объектов (1.7) свидетельствует об их принадлежности к разным классам, а все объекты с одинаковым классификационным образом Ак для наблюдателя неразличимы и могут быть объединены в одну к-ю группу объектов. На данном этапе алгоритма каждому объекту классификации приписывается перечень возможных классов, к которым объект может быть отнесен. При этом тип «новый» приписывается как возможный к каждому объекту для дополнения результатов классификации до полной группы событий.
Предположим, что измерительной аппаратурой одновременно наблюдается V групп объектов с различными классификационными образами, а в каталоге эталонных значений приведено W классов. Для проведения обработки информации и определения вероятности принадлежности к-й группы объектов к у-му классу составим начальную классификационную матрицу А размерностью: (V W): А= 5kj k = 1…V; j = 1…W, (1.8) Каждой k-й группе объектов с классификационным образом Лк ставится в соответствие строка матрицы А (1.8), состоящая из нулей и единиц. Можно предположить равновероятность принадлежности к-й группы объектов ко всем классам, представленным единицами в соответствующей строке матрицы, однако такой подход к оценке вероятности носит субъективный характер.
В [17, 13] показано, что для классификации в качестве решающего правила может быть использован метод классификации Г.В. Шелейховского. В 1946 г. ленинградский архитектор Г.В. Шелейховский решал задачу прогнозирования транспортных потоков в городе - транспортную задачу с линейными ограничениями [14]. Он предложил [15] метод балансирования, заключающийся в последовательном преобразовании строк и столбцов матрицы смежности графа транспортных потоков (классификационную матрицу) умножением и делением на подходящие множители. Л. М. Брэгман нашел доказательство сходимости метода балансировки [13] и обобщил [16] метод Г.В. Шелейховского для решения произвольных задач линейного программирования.
Применение метода Г.В. Шелейховского для решения задачи классификации объектов в условиях параметрической неопределенности и пересечения классов является частным случаем задачи линейного программирования (транспортной задачи). Классическая постановка транспортной задачи [54] и наиболее известный метод ее решения приведен в разд. 1.11 данной работы. Метод Г.В. Шелейховского исключает элемент субъективизма при решении задачи классификации. Сущность метода раскрыта в [17, 13]. Данный метод предлагает следующую итерационную процедуру, которая позволяет преобразовать классификационную матрицу А в матрицу:
Исследование возможности сокращения вычислительной трудоемкости процедуры последовательного нормирования и разработка алгоритма сокращения классификационной матрицы
Сущность разработанного комбинированного метода классификации состоит во введении в базовый метод понятия параметрического пространства и представления в нем объектов классификации и классов из каталога эталонных значений [77-80]. Далее, на каждом из основных этапов работы комбинированного метода анализируется друг относительно друга взаимное расположение объектов, участвующих в обработке, а также относительно классов из каталога эталонных значений. В рамках диссертационной работы решение задачи классификации рассматривается на примере четырехмерного параметрического пространства. Данное пространство может быть представлено в виде двух двумерных графиков, представленных на рисунке 2.2. Рисунок 2.2 – Пример графического представления четырехмерного параметрического пространства
На рисунке 2.2 представлены графики X0Y и K0Z, соответствующие приведенной в таблице 2.1 строке из каталога эталонных значений и приведенной в таблице 2.2 строке с описанием параметров (признаков) объекта классификации. Оси X соответствует параметр 1, Y – параметр 2, K – параметр 3 и Z – параметр 4 пространства. Точки А на данных графиках отображают эталонные значения (центры) допустимых интервалов из каталога эталонных значений. Допустимые интервалы изменения каждого параметра из каталога эталонных значений представлены в виде прямоугольников с центрами А. Таким образом, совокупность прямоугольников с центрами в точке А представляет собой гиперпараллелепипед (область) в четырехмерном параметрическом пространстве, соответствующий строке из каталога эталонных значений таблицы 2.1.
Представление в параметрическом пространстве классов из каталога эталонных значений в виде областей, а объектов классификации в виде точек позволяет оценить наличие пересечений классов и места попаданий точек (объектов классификации) в области (классы) или пересечения областей. Так, например, при составлении классификационного вектора нет необходимости сравнивать параметры объекта классификации с параметрами всех классов из каталога эталонных значений, достаточно лишь обнаружить первое попадание точки в область и дополнительно оценить принадлежность данной точки только тем областям, которые имеют пересечения с обнаруженной областью. Попадание в параметрическом пространстве точки в область является критерием установки соответствующей единицы в классификационном векторе объекта (п.1.9), представленного данной точкой. Если точка попадает в пересечение областей, это говорит о том, что соответствующий объект классификации будет иметь несколько единиц в своем классификационном векторе. Появляется возможность оценки взаимного влияния объектов на результат классификации. Представление каталога эталонных значений в виде совокупности областей в параметрическом пространстве позволяет проанализировать состав данного каталога и положение объектов классификации на предмет выявления в группе одновременно наблюдаемых объектов независимых подгрупп взаимозависимых объектов. Объекты, входящие в состав независимой подгруппы взаимозависимых объектов, характеризуются тем, что попадают в совокупность пересекающихся областей, которые не имеют пересечений с областями из других подгрупп. Частным случаем такой подгруппы являются объекты, попавшие в одну область, не имеющую пересечений с другими областями. Указанные выше особенности взаимного расположения точек и областей в параметрическом пространстве могут быть учтены при формировании классификационной матрицы. Построение классификационной матрицы и применение процедуры последовательного нормирования для каждой подгруппы в отдельности может существенно сократить вычислительную трудоемкость по сравнению с применением данной процедуры к общей классификационной матрице.
Становится возможным расширение функциональных возможностей метода при решении задачи классификации путем построения новых областей для объектов классификации, не попавших ни в одну область из каталога эталонных значений (новые объекты). Последующая информация о новых объектах может либо подтверждать существование новой, созданной ранее области, уточняя ее параметры, либо опровергать ее существование. В результате, от измерения к измерению формируется временный каталог новых классов (формирование эмпирического знания), который в дальнейшем может быть использован для корректировки каталога эталонных значений.
Комбинированный метод классификации должен решать следующие задачи: 1. Оценка взаимного расположения объектов классификации и областей, характеризующих классы из каталога эталонных значений. По результатам данной оценки - построение классификационных образов (векторов) объектов (предварительный анализ данных). 2. Сокращение классификационной матрицы на основе анализа взаимного влияния объектов. 3. Решение проблемы сходимости при использовании процедуры последовательного нормирования. 4. Преобразование представления классификационной матрицы с целью минимизации машинных ресурсов на ее хранение и обработку. 5. Анализ информации о новых объектах с помощью построения и подтверждения областей в параметрическом пространстве. С учетом решения поставленных задач работу комбинированного метода можно представить в виде представленной на рисунке 2.3 блок-схемы.
Оценка влияния сокращения классификационной матрицы на решение задачи классификации
Применение базового метода (см. разд.1.9), использующего процедуру последовательного нормирования для решения задачи классификации в условиях параметрической неопределенности классов, является частным случаем задачи линейного программирования (транспортной задачи). Известны ситуации возникновения вырожденности транспортной задачи [54]. Описание транспортной задачи и один из методов ее решения, в котором заложен механизм отслеживания и решения проблемы вырожденности, приведены в подразд.1.11 данной работы. Здесь проблема вырожденности (сходимости) возникает в том случае, если в процессе решения транспортной задачи число базисных (занятых перевозками) ячеек транспортной таблицы меньше m + n - 1 (где m и n — число поставщиков и потребителей, соответственно). В данном случае алгоритм решения впадает в бесконечный цикл или завершается с ошибкой. Базовый метод лишен указанных выше недостатков, которые приводят к проблеме сходимости транспортной задачи, так как правила формирования классификационной матрицы (разд.1.9) исключают наличие в матрице нулевых строк либо столбцов, а также обязательно наличие единичного столбца с именем «Новый». Таким образом, количество занятых ячеек матрицы никогда не будет меньше m + n – 1, где m и n – количество строк и столбцов матрицы соответственно. Однако базовый метод обладает собственным недостатком, способным вызывать проблему сходимости, о чем отмечалось в разд.1.10 данной работы.
Существуют разные пути решения проблемы сходимости, описанной в разд.1.10. Известен подход [64-66], который может использоваться для решения проблемы сходимости. Автор данного подхода предлагает заменить нулевые элементы матрицы малыми величинами, однако он не дает качественную оценку как решения проблемы сходимости, так и возможности получения достоверного результата. Сам автор не рекомендует применение данного подхода: «Подход, когда матрица с нулевыми наблюдениями аппроксимируется строго положительной матрицей в надежде, что получится приближенная переходная матрица, является плохой практикой, если только нет хороших аргументов для конкретного выбора» [64].
Анализ возникновения проблемы сходимости показывает, что данная проблема вызвана наличием в группе одновременно наблюдаемых объектов, участвующих в эксперименте, хотя бы одного неоднозначно определенного объекта, не имеющего объектов, которые могут повлиять на распределение вероятностей данного объекта. То есть ситуация несходимости возникает в том случае, если существует такой объект, который можно отнести к более, чем одному классу из каталога эталонных значений, но нет такого объекта в группе одновременно наблюдаемых, который относился бы хотя бы к одному из этих классов. В таблице 2.6 такой объект представлен в строке №4.
В данной диссертационной работе предлагается решение указанной проблемы путем выявления «проблемных» объектов при использовании комбинированного метода классификации. Наличие таких «проблемных» объектов может быть выявлено путем представления объектов классификации и классов из каталога эталонных значений в параметрическом пространстве в виде точек (2.6) и областей (2.4). «Проблемный» объект будет характеризоваться попаданием в пересечение нескольких областей, и являться при этом единственным объектом, попавшим в данное подмножество пересекающихся областей. Так как «проблемные» объекты не имеют объектов в группе одновременно наблюдаемых, на распределение вероятностей которых они могут повлиять, для них строятся результирующие векторы с равномерным распределением вероятностей. Такие объекты не принимают участия в процессе формирования классификационной матрицы. Таким образом, предложенный способ решения проблемы сходимости задачи классификации не только не замедляет выполнение процедуры последовательного нормирования, как другие известные ранее способы, но, наоборот, сокращает вычислительную трудоемкость до предельно минимального уровня, соответствующего решению задачи при отсутствии проблемы сходимости. Для «проблемного» объекта предполагается равномерное распределение вероятностей среди классов, представленных единицами в его классификационном образе.
Рассмотренные выше положения иллюстрируют сущность выявленной проблемы сходимости адаптированного к решению поставленной задачи в рамках данной диссертационной работы метода классификации. Однако изложение данного материала не является обобщающим для произвольного набора объектов, а также не гарантирует возможности проявления других источников (условий) несходимости. В связи с отмеченным, ниже излагается строгое рассмотрение проблемы сходимости с учетом особенностей постановки (разд.1.2) и алгоритмической реализации (разд.1.9) исходной задачи классификации на основе метода, использующего процедуру последовательного нормирования.
Утверждение 1. Пусть в соответствии с алгоритмом реализации метода классификации (разд.1.9) сформирована квадратная классификационная матрица А, в которой существуют проблемные объекты. Такая матрица имеет размерность (U U), U6, и в ней могут существовать два и более столбцов, содержащих нули во всех соответствующих строках, кроме одной, содержащей проблемные объекты.
Размерность матрицы U6 обусловлена особенностью формирования классификационной матрицы на начальном этапе работы метода (разд. 1.9). При размерности U6 матрица может содержать несколько столбцов, имеющих единицы только в одной строке и при этом оставаться квадратной. При размерности U 6 в случае возникновения в матрице проблемного объекта, в соответствии с правилами соблюдения квадратности матрицы, она будет дополнена единичными строками, что нарушит условие существования проблемного объекта.