Содержание к диссертации
Введение
Глава 1. Обзор и анализ существующих эвристических методов принятия решений, методов корреляции и сбора статистики по трафику 18
1.1. Обзор существующих подходов к построению систем на основе знаний экспертов 18
1.2. Разработка подхода к построению систем принятия решений для рассматриваемых в работе областей 20
1.2.1. Разработка методики получения знаний от экспертов 22
1.2.2. Подход к генерации динамических функций риска для систем принятия решений 24
1.3. Обзор и анализ существующих эвристических методов принятия решений, методов корреляции и сбора статистики по трафику 27
1.3.1. Обзор и анализ методов принятия решения в задачах дискретной оптимизации 27
1.3.2. Обзор и анализ методов теории статистики 34
1.3.3. Обзор и характеристика методов сбора информации по трафику 36
1.4. Выводы 38
Глава 2. Модель анализа и оценки ситуаций. Метод функций риска 39
2.1. Разработка модели анализа и оценки ситуаций в прикладных задачах 39
2.2. Метод функций риска в функциональной модели 41
2.3. Разработка ситуационных моделей 46
2.3.1. Построение ситуационной модели для задачи области микробиологии 47
2.3.2. Построение ситуационной модели для задачи области анализа трафика 48
2.3.3. Построение ситуационной модели для задачи области неврологических заболеваний 49
2.4. Представление знаний, организация баз данных 50
2.5. Разработка алгоритма анализа и оценки стадий дисбиоза по количеству заданных видов бактерий 51
2.6. Разработка алгоритма анализа и оценки ситуаций в области анализа трафика 55
2.7. Разработка алгоритма анализа стадий энцефалопатии, определение корреляции параметров различных диагностических методик 58
2.8. Теоретический подход к решению задачи с анализом основных диагностических методик исследования в области кардиологии
2.9. Программный комплекс для анализа и оценки групп в рассматриваемых областях 62
2.9.1. Функциональное назначение программного комплекса, области применения, ограничения 62
2.9.2. Специальные условия применения и требования организационного, технического и технологического характера 64
2.10. Выводы 69
Глава 3. Экспериментальные исследования и практические результаты 70
3.1. Вычислительный эксперимент и практические результаты в области микробиологии 70
3.1.1. Проектирование базы данных, структура БД 70
3.1.2. Алгоритм анализа и оценки данных по дисбактериозу 71
3.1.3. Компоненты программного комплекса в области микробиологии 72
3.1.4. Результаты исследовательского эксперимента 74
3.2. Вычислительный эксперимент и практические результаты в
области анализа трафика 80
3.2.1. Сбор статистических данных по трафику 80
3.2.2. Первичная обработка данных 82
3.2.3. Проектирование базы данных, структура БД 83
3.2.4. Алгоритм анализа и оценки показателя трафика «дельта» 85
3.2.5. Компоненты программного комплекса в области анализа трафика 86
3.2.6. Результаты исследовательского эксперимента 88
3.3. Вычислительный эксперимент и практические результаты в области неврологических заболеваний 91
3.3.1. Проектирование базы данных, структура базы данных 91
3.3.2. Алгоритм анализа и оценки в области неврологических заболеваний 93
3.3.3. Компоненты программного комплекса в области неврологических заболеваний 94
3.3.4. Результаты экспериментальных исследований 96
3.4. Выводы по главе 102
Заключение 104
Список использованной литературы
- Разработка подхода к построению систем принятия решений для рассматриваемых в работе областей
- Обзор и анализ существующих эвристических методов принятия решений, методов корреляции и сбора статистики по трафику
- Разработка алгоритма анализа и оценки стадий дисбиоза по количеству заданных видов бактерий
- Компоненты программного комплекса в области микробиологии
Введение к работе
Актуальность темы
В работе рассматриваются вопросы применения специальных методов принятия решений в научно-технических областях. Эти методы ранее применялись в дискретных оптимизационных задачах. Рассматриваемые методы могут быть объединены в одну группу, поскольку они построены на основе функций риска.
Применение эвристических методов в построении систем принятия решений для развивающихся областей науки и техники - важная и трудоемкая задача. Такие системы, в частности, позволяют оценивать, анализировать, диагностировать конкретные случаи, конкретные ситуации -в зависимости от специфики рассматриваемой предметной области. Поэтому интерес к ним не угасает.
Наибольший эффект от применения систем принятия решений может достигаться при решении задач, обладающих следующими свойствами: неполнотой, нечеткостью, вероятностным характером исходных знаний о предметной области; большой размерностью пространства возможных решений, что делает практически невозможным поиск решения посредствам полного перебора всех имеющихся вариантов; динамическим изменением исходных данных в процессе решения задачи [109].
Во всех поставленных в работе задачах из разных научно-технических сфер присутствуют перечисленные аспекты. Для построения и реализации системы принятия решений для каждой из таких задач необходимо разработать подход, важнейшей составляющей которого являются правила для обработки ситуаций - их описание и реализация. Разработка таких правил в настоящей диссертационной работе заключается в исследовании и применении специальных эвристических методов принятия решений -прежде всего методов, построенных на основе функций риска.
Ранее данные методы применялись как одна из эвристик при решении различных задач дискретной оптимизации. При этом, прежде всего, рассматривалась задача выбора конкретного варианта ветвления в незавершенном методе ветвей и границ для построения так называемых апугіте-алгоритмов[101]: например, требовалось принять решение о выборе конкретного элемента матрицы стоимостей в задаче коммивояжера, или конкретного блока в задаче минимизации недетерминированных конечных автоматов. Имеется информация, данная разными программами-экспертами -т. е. разными эвристиками, т.н. «предикторами». При этом очень часто эксперты дают противоречивую информацию - и надо её каким-то образом «усреднять». В отличие от всех ранее опубликованных алгоритмов в нескольких проектах, выполненных ранее научным руководителем данной диссертации и его аспирантами, для этого использовались динамически генерируемые функции риска [6, 7, 53, 56, 58]. Например, эти функции применялись в задаче коммивояжера к результатам метода голосования применялись эти функции. Метод нашел свое применение и в области биржевых операций (в частности, на бирже «Форекс»)[54, 55].
Все эти задачи являются задачами дискретной оптимизации. Но, кроме перечисленных задач, существует множество научно-практических областей, в которых есть необходимость получения новых эффективных алгоритмов, учитывающих априорную информацию. В них метод функций риска, в совокупности с другими локальными методиками, характерными для анализа предметной области, также является весьма эффективным.
Актуальность разработки и использования новых эффективных алгоритмов анализа и оценки ситуаций отражена в проблематике областей.
Область анализа трафика.
Рост числа приложений, передающих данные в реальном времени, обусловлен возросшим интересом людей услугами передачи аудио-, видеоинформации средствами Интернета. Такая тенденция влечет рост трафика передачи подобной информации. Передача видеоданных связана с рядом возможных технических сложностей в рассматриваемой сети, решению которых и посвящена часть данной работы. Исследование относится к определенной структуре сети, на основании данных которой ставится эксперимент и осуществляется анализ (Приложение ПЛІ). В Приложении П.1. схематично представлена структура сети при проведении видеоконференций.
Для каналов с ограниченной полосой пропускания данных организация передачи голосовой и видео информации в хорошем качестве весьма проблематична, с учетом того, что все сервисы сети должны полноценно работать. Также могут возникнуть сложности, связанные с различными видами атак (такими как «флуд» и сканирование сети [18, 28, 45, 94]), которые могут привести к выходу из строя сервисов (deny of service). Смысл исследовательской работы в данном случае заключается в своевременном обнаружении таких ситуаций. В крупной рассредоточенной по городу структуре (такой как Ульяновский государственный университет), состоящей из нескольких корпусов, опорная сеть которых собрана на двух площадках -корпус УлГУ на ул. Пушкинская 4а, а также ГТС ул. Льва Толстого 95. На площадке ГТС установлено оборудование (CISCO 3725 с модулями WIC-2T и NM-16AS; CISCO Catalyst WS-2950T [64]). CISCO 3725 [23, 75] является корневым маршрутизатором который обслуживает внешние каналы связи, канал до корпуса УлГУ на ул.Пушкинская 4а, пиринговый канал с точкой обмена трафиком провайдеров Ульяновской области «SimX», а также другие клиентские подключения, которые осуществляются по портам RS-232 (NM-16AS) или Ethernet (WS-2950T). На площадке УлГУ (ул. Пушкинская, 4а) установлено следующее оборудование: CISCO 2621 с модулем WIC-2T, CISCO Catalyst WS-2950T [33] и два маршрутизатора CISCO 2511. CISCO 2621 обслуживает канал до корневого маршрутизатора (CISCO 3725), клиентские подключения, которые осуществляются по портам RS-232 (CISCO 2511) или Ethernet (WS-2950T), подключение к услуге КСПД (корпоративная сеть передачи данных [68, 91]), предоставляемой Ульяновским филиалом ОАО «Волгателеком». Приложение П.11.
В такой структуре невозможно на всех локальных участках одновременно контролировать работоспособность конечных, реальных серверов. Это обстоятельство некоторое время создавало проблемы передачи видеоданных, например, при проведении конференций.
В данной области было необходимо разработать эффективный алгоритм, входящий в состав системы принятия решений - для оценки ситуаций, рассматриваемых экспертами как наиболее значимых. Наибольший интерес в этой области представляют т.н. критические рабочие ситуации, характеризующие технические проблемы.
К отличительным свойствам этой задачи можно отнести неполноту исходных знаний о предметной области; большую размерность пространства исходных решений; динамическое изменение исходных данных в процессе решения задачи.
Область неврологических заболеваний.
В данной области рассмотрению подлежали сосудистые заболевания головного мозга - это является одной из самых актуальных проблем современной медицины. «В России инсульт занимает второе место среди причин смерти (после острых заболеваний сердца) и первое место по уровню резкой остаточной инвалидности (3,2 на 10000 населения)» ([52], стр. 4). В результате исследовательской работы экспертами были получены данные ультразвуковым методом и методом суточного мониторирования артериального давления по заболеванию гипертонической энцефалопатии. «Под термином дисциркулярной энцефалопатии (ДЭ) впервые применившие его ученые НИИ неврологии РАМН Г.А. Максудов и академик Е.В. Шмидт понимали прогрессирующее диффузное поражение головного мозга, обусловленное нарастающим ухудшением его кровоснабжения» ([52], стр.5). «В патогенезе и острых расстройствах церебрального кровообращения, так и хронических (ГЭ) важную роль играют два фактора: 1. Недостаточность притока крови к тканям мозга. 2. Недостаточность и замедление венозного оттока» ([52], стр. 14). Выделено 3 стадии дисциркулярной энцефалопатии.
В данной области было необходимо разработать эффективный алгоритм, входящий в состав системы принятия решений, для оценки ситуаций, рассматриваемых экспертами как наиболее значимых. Результаты работы этого алгоритма будут использованы для определения корреляционной связи между параметрами методов.
К свойствам задачи можно отнести неполноту исходных знаний о предметной области; возможность динамического изменения исходных данных в процессе решения задачи.
Область микробиологии.
В этой области рассматривалась проблема современной микробиологии, связанная с дисбиотическими изменениями кишечника. При физиологической норме организм содержит сотни видов бактерий, а также вирусы и простейшие, составляющие в сумме нормальный микробиоценоз. При воздействии дестабилизирующих факторов микрофлора реагирует количественными и качественными сдвигами в популяциях микроорганизмов. Современные представления о дисбактериозах требуют поиска новых подходов к их оценке и характеристике [11, 42].
В данной области было необходимо разработать эффективный алгоритм, входящий в состав системы принятия решений - для оценки групп, рассматриваемых экспертами как наиболее важных в задаче. К свойствам задачи можно отнести неполноту исходных знаний о предметной области; динамическое изменение исходных данных в процессе решения задачи.
Поставленные в настоящей работе задачи различных научно-практических областей требуют не только результата работы эвристического алгоритма определения объективной оценки, но и некоторых качественных подходов к полученным в итоге результатам, прежде всего, знания экспертов.
Таким образом, в вышеперечисленных сферах существуют важные и актуальные задачи анализа и оценки ситуаций необходимые для профессиональной деятельности людей и лучшей ориентации в специфичных областях.
Цели работы: разработка подхода к построению систем принятия решений как способа анализа и оценки значимых этапов изучаемого процесса для решения задач определенных на этапе идентификации, а именно: оценка этапов развития дисбактериоза, оценка рабочих ситуаций по количеству и типу трафика, оценка стадий заболевания энцефалопатии; разработка методики получения знаний от экспертов для создания ситуационной модели и анализа полученных результатов; разработка модели анализа и оценки ситуаций, включающей для каждой рассматриваемой прикладной области: - функциональную модель, представляющую собой записанные с помощью эвристического и математического аппаратов зависимости между параметрами (показателями) значимых этапов исследуемых процессов; соответствующее алгоритмическое обеспечение; программные средства, реализующие разработанные алгоритмы и выполняющие функцию анализа и оценки параметров, работу с базами данных в системе.
Для достижения целей в работе решены следующие задачи
Разработаны специальный подход к построению систем принятия решений и соответствующая методика получения знаний от экспертов.
Совместно с экспертами проведен анализ и группировка в предметных областях (микробиология, неврологические заболевания, анализ трафика), разработаны концептуальные основы построения ситуационных моделей. Спроектированы базы данных в каждой области.
Разработана функциональная модель на основе эвристического метода функций риска с учетом локальных методик, обеспечивающая алгоритмизацию решения задач и оценку ситуаций.
Разработаны системы принятия решений для анализа и оценки ситуаций в каждой из рассматриваемых прикладных областей. А именно, на основе эвристического метода функций риска разработаны алгоритмы: анализа и оценки ситуаций по показателю трафика - «дельта» (разности между входящим и исходящим числом пакетов); анализа и объективной оценки стадий дисбиоза по количеству заданных видов бактерий; анализа и оценки стадий энцефалопатии по заданным параметрам; определен коэффициент корреляции параметров.
На основе разработанных моделей и алгоритмов реализованы программные комплексы, компоненты систем принятия решений.
Совместно с экспертами проведена оценка полученных результатов.
Метод исследования
Главным при планировании исследования была постоянная проверка соответствия разработанных моделей и проводимых экспериментов, Для решения задач из перечисленных в работе областей в функциональной модели использовался эвристический метод функций риска, позволяющий разрабатывать алгоритмы решения задач.
В ходе исследовательской деятельности была разработана методика получения знаний от экспертов в каждой исследуемой задаче. В ее основу положен механизм извлечения экспертного знания путем сбора и обработки опыта всех участников по решению конкретной практической задачи. В основу опыта эксперта входят проведенные разработки с использованием локальных методов, характерных для данной области, а также принятые решения на различных этапах экспериментов.
Дальнейшая задача инженера по знаниям (автора диссертации) заключается в создании ситуационной модели по имеющимся экспертным фактам конкретной задачи и заполнении баз данных. А также в создании систем принятия решений для конкретной области с использованием эвристического метода функций риска для оценки стадий и выделения конкретных ситуаций.
Полученные в ходе экспериментальных исследований результаты должны быть согласованы с экспертами конкретной области. Эксперты, в свою очередь, сравнивают предоставленные результаты системным аналитиком с теми, которые они получали иными методами, например с помощью пакетов «Exel», «Статистика». Далее эксперты должны принять решение на основе опыта о целесообразности дальнейших исследований с использованием разработанной системы.
Для построения полноценной системы принятия решений будут необходимы новые эвристические методики, способные без участия экспертов оценивать ситуации и производить сопоставления с имеющимися в базе результатами предыдущих экспериментальных исследований. В качестве примера был озвучен метод эвристического сопоставления.
Однако подобной методикой может служить метод функций риска. В работе вводится понятие динамических функций риска.
На основе предварительной оценки групп, состоящей из статических оценок наиболее значимых параметров процесса (заболевания, рабочей ситуации), должна строиться оценка вновь появляющихся групп, предлагаемых к рассмотрению экспертами области.
Для предварительной оценки экспертом по оценке ситуаций был реализован программный комплекс, который в контексте эвристического метода представляет собой набор эвристик. К новым группам (наборам параметров) применяются уже разработанные эвристики, как для предварительной оценки, но все последующие шаги системы предполагают выбор функции в зависимости от предварительной оценки ситуации, и не программистом, а автоматически (2-3 параметра функции выбираются в зависимости от предварительной оценки).
Таким образом, динамические функции риска используются как эвристики для выбора функций определения весовых коэффициентов и для обучения систем принятия решений.
Алгоритмы разрабатывались на основе группировки данных и эмпирического подбора функций для определения весовых коэффициентов, а далее автоматического. Также в решении задач использовались корреляционный метод теории статистики - коэффициент Фехнера (в области неврологических заболеваний) и методика сбора информации по трафику - «flow-tools» (в области анализа трафика).
В ходе эксперимента были получены результаты по всем группам данных из перечисленных областей. Данные результаты подтвердили адекватность выбора методики анализа.
Научная новизна
В работе решается новая задача по разработке и применению подхода к построению систем принятия решений с использованием функций риска в различных областях научной и практической деятельности людей, в прикладных задачах. Данный подход можно рассматривать как альтернативу к возможному применению методов из других областей ~ например, мультиагентной оптимизации и нейросетевых алгоритмов. Основные результаты диссертации;
Разработан подход к построению систем принятия решений, а также методика получения знаний от экспертов. Разработаны ситуационные модели для каждой из поставленных в работе задач.
Разработана функциональная модель на основе эвристического метода функций риска, обеспечивающая алгоритмизацию решения задач, анализ и оценку ситуаций.
Разработаны алгоритмы анализа и оценки ситуаций (стадий) в каждой из рассматриваемых прикладных областей.
Разработаны информационные модели систем принятия решений анализа в каждой прикладной области. Получена экспертная оценка результатов.
Практическая ценность диссертации основана на результатах, полученных в ходе решения задач, поставленных различными сферами научно-технической деятельности. Разработанные модели, алгоритмы анализа и оценки ситуаций использовались при создании информационных систем принятия решений. В настоящее время разработанная автором информационная система анализа и оценки ситуаций в области анализа трафика успешно используется при реализации процесса мониторинга критичных точек в сети (ОГС ЦТКиТИ), а так же оценки заданных экспертами ситуаций, что позволяет в кратчайшие сроки локализовать проблемные участки.
Ценными с практической точки зрения являются результаты, к которым можно отнести информационную систему принятия решений в области микробиологии, позволяющую осуществлять подсчет и анализ количества видов бактерий на основе исходных статистических данных, предоставленных экспертами. Что способствует созданию базы данных, оценке групп по стадиям заболевания, а также «обучению» системы. Подход к оценке данных взят в разработку коллегами кафедры «Микробиологии».
Интерес также представляют результаты в области неврологических заболеваний, метод функций риска позволяет усовершенствовать корреляционный метод (коэффициент Фехнера использованием весовых коэффициентов), что дает возможность адекватной оценки стадии и определения связи между параметрами групп. В данной области автором создана информационная система анализа и оценки, которая способна к саморазвитию, а именно, пополнению информацией и получению более приемлемых результатов.
Применяемый в работе метод рассматривался с точки зрения прикладной и практической значимости. В результате проведенной работы можно говорить о необходимости метода для оценки групп данных различных научно-практических областей.
Достоверность результатов
Предоставленные экспериментальные данные получены с использованием достоверной методики, имевшей применение в области дискретной оптимизации, а также в области биржевых операций. Тема динамических функций риска в задачах дискретной оптимизации и интеллектуальных играх разрабатывалась научным руководителем Б.Ф. Мельниковым и его аспирантами: А.Н. Радионовым, Н.В. Романовым, М.В. Бузиным, В.А. Гумаюновым и получила свое отражение во множестве публикаций, в том числе телевизионных выступлениях [6, 7, 57, 58]. К работам, в котоых метод функций риска применяется как способ построения anytime-алгоритмов решения задач дискретной оптимизации, можно также отнести часть диссертации Белозеровой А. Р. [10].
Полученные автором в данной работе результаты исследований обсуждались на российских и международных конференциях:
Математика. Образование. Культура: международная конференция (Тольятти, 2003);
Всероссийская научно-техническая конференция «Искусственный интеллект в XXI веке» (г. Пенза, 2004);
Региональная научно-техническая конференция. Научные чтения для студентов и аспирантов (Тольятти, 2005);
Всероссийская научно-техническая конференция «Методы и средства обработки информации, 2005» (Москва, МГУ, октябрь, 2005, председатель программного комитета - акад. РАН Е.П. Велихов);
Международная конференция «Туполевские чтения» (Казань, ноябрь 2005);
Семинары кафедры «Теоретической информатики и компьютерной безопасности», «Микробиологии».
Личный вклад
Метод функций риска как составляющая подхода для решения первоначально поставленной автору задачи (в области анализа и классификации трафика) был предложен научным руководителем. Описание и реализация применения этого метода для задач, которые не принято называть задачами дискретной оптимизации, разработка подхода к построению систем принятия решений, описание и реализация методов сбора данных, разработки модели анализа и оценки, алгоритмов решения задач, а также создание соответствующих систем принятия решений принадлежат автору. Также автором проводились исследования в областях микробиологии и неврологических заболеваний. Аналитические разработки моделей, алгоритмов и программных реализаций на основе функций риска, а также апробация результатов, велись автором самостоятельно.
Основные положения, выносимые на защиту
Подход к построению систем принятия решений и методика получения знаний от экспертов;
Структура модели анализа и оценки ситуаций в прикладных задачах. Ситуационные модели каждой области. Основные положения метода принятия решений на основе функций риска применительно к конкретным практическим задачам (функциональная модель).
Основные этапы работы алгоритмов для решения задач, структуры систем принятия решений, программный комплекс.
Структура работы
Диссертация состоит из введения, трех глав, выводов по главам, заключения, приложений и списка использованной литературы. Диссертация изложена на 140 страницах, содержит 12 рисунков, 5 Утверждений, 5 Эвристик, 37 таблиц и список использованной цитируемой литературы из 112 наименований.
Во введении обосновывается актуальность темы, формулируются цели, ставятся задачи. Определены объект и предмет исследования. Отражена научная новизна и практическая значимость выполненной работы, личный вклад автора, достоверность полученных результатов и апробация. Перечислены коллеги, кому автор выражает благодарность за сотрудничество и помощь в работе.
В главе 1 представлены разработанные автором подход к построению систем принятия решений на основе эвристического метода (функций риска) и методика получения знаний от экспертов, в том числе обзоры существующих подходов к построению экспертных систем. Также рассмотрены и проанализированы некоторые эвристические методы принятия решений в задачах оптимизации, отмечены их достоинства и недостатки. Приведены некоторые сравнительные характеристики с используемым в работе методом. Рассмотрены статистические методы корреляции и структурные показатели, даны их характеристики. Дан обзор и анализ методов сбора статистики по трафику на основе двух коллекторов.
В главе 2 представлена разработка модели анализа и оценки ситуаций в прикладных задачах. В основу функциональной модели положен эвристический метод принятия решений, а именно, метод функций риска, который позволил дать объективную оценку событий (стадий) в трех различных областях: микробиологии, анализа трафика, неврологических заболеваний. Также представлены ситуационные модели; организация баз данных; разработка алгоритма анализа и оценки стадий дисбиоза по количеству заданных видов бактерий; разработка алгоритма анализа и оценки ситуаций в области анализа трафика; разработка алгоритма анализа стадий энцефалопатии и определения корреляции параметров различных диагностических методик. Обоснован выбор функций определения весовых коэффициентов во всех обозначенных областях. Кроме того, глава содержит техническое описание программного комплекса, позволяющего реализовать разработанные алгоритмы.
Кроме того, в главе содержится теоретическое описание возможности применения метода функций риска в системе принятия решений с анализом основных диагностических методик кардиологических исследований.
В главе 3 представлены вычислительные эксперименты и практические результаты по трем озвученным областям. Описано исследование, создание и результаты работы систем принятия решений, реализованных автором, для каждой прикладной задачи как инструмент систематизации, хранения, анализа и обработки данных. Приведена пошаговая работа программного комплекса в каждой области. В табличных отчетах изложен результат применения разработанных программных комплексов в системе для каждой области.
В заключении сделаны выводы по итогам выполненной работы.
В приложении П.1. приведена структурная схема сети при проведении видеоконференций.
В приложении П.2. таблично представлены бактериологические данные по дисбактериозу для каждого случая.
В приложении П.З. показана таблица функций для определения весовых коэффициентов в задаче области микробиологии.
В приложении П.4. приведена структура базы данных «Bakter».
В приложении П.5. таблично рассмотрены характеристики бактерий и их количественное содержание в нормальном биотопе.
В приложении П.6. приведена структура базы данных «Traf».
В приложении П.7. показана таблица функций для определения весовых коэффициентов в задаче области анализа трафика.
В приложении П.8. таблично представлены данные по трем стадиям дисциркулярной энцефалопатии полученные методом суточного мониторирования.
В приложении П.8.1. таблично представлены данные по трем стадиям дисциркулярной энцефалопатии полученные методом ультразвуковой диагностики.
В приложении П.9. приведена структура базы данных «Nevro».
В приложении П. 10. показана таблица функций для определения весовых коэффициентов в задаче области неврологических заболеваний.
В приложении П.11. приведена структура глобальных сетей УлГУ.
В приложении П. 12. приведены статистические данные по трафику для трех рассматриваемых рабочих ситуаций.
Апробация работы
Основные результаты настоящей работы опубликованы в 7 научных статьях, среди которых - публикация в издательстве МГУ. Результаты обсуждались на следующих научных конференциях и семинарах:
Математика. Образование. Культура: международная конференция (Тольятти, 2003);
Всероссийская научно-техническая конференция «Искусственный интеллект в XXI веке» (г. Пенза, 2004);
Региональная научно-техническая конференция. Научные чтения для студентов и аспирантов (Тольятти, 2005);
Международная конференция «Туполевские чтения» (Казань, ноябрь 2005);
Всероссийская научно-техническая конференция «Методы и средства обработки информации, 2005» (Москва, МГУ, октябрь, 2005, председатель программного комитета - акад. РАН Е.П. Велихов)
Основные результаты и выводы диссертационного исследования доведены до сведения экспертов и предложены к внедрению. Предложенные автором в работе подходы имеют универсальный характер, поэтому они могут быть применены в широком спектре практических задач, для объективной оценки показателей некоторых специальных параметров, являющихся важными для соответствующих конкретных задач.
Разработанная модель, алгоритм и система внедрены в отделе глобальных сетей Центра телекоммуникаций и технологий Интернет Ульяновского государственного университета (задача анализа трафика). Программный комплекс был успешно внедрен в рабочий процесс в отделе глобальных сетей Центра телекоммуникаций и технологий Интернет Ульяновского государственного университета; в процесс работы Интернет-провайдера «СимКом».
Кроме того, результаты предложены для использования на кафедрах неврологии и микробиологии Ульяновского государственного университета, где проводились исследования по анализу и оценке значимых параметров заболеваний и нахождения связей между ними. Практические результаты представлены в настоящей работе.
Публикации
1 .Мельников Б. Ф., Тарасова Е. Г. Функции риска в системах принятия решений для сетевой модели управления ISO // Математика. Образование. Культура: Международная научная конференция, 2003, Тольятти: ТГУ, 2004.- Ч.2.-С.23.
2.Тарасова Е. Г. Функции риска в системах принятия решений с анализом основных диагностических методик кардиологических исследований // Искусственный интеллект в 21 веке: научно-техническая конференция, 2004, Пенза/под ред. В. И. Левина. Пенза: «Приволжский дом знаний», 2004. - с.87.
Тарасова Е. Г. Функции риска в нетрадиционных задачах с анализом основных параметров, как показателей заболевания // Научные чтения для студентов и аспирантов: региональная научно-техническая конференция, 2005, Тольятти: ТСУ, 2005. - с. 43.
Тарасова Е. Г. Функции риска в системах принятия решений с анализом основных параметров модели // Ученые записки. Ульяновск: УлГУ, ФИТТ, 2004,-с. 39.
Тарасова Е. Г. Нетрадиционные методы принятия решений в области анализа и классификации трафика // Туполевские чтения. Тезисы к международной молодежной конференции секция «Телекоммуникации в средствах связи». Казань: КАИ, 2005, - Т.4, - с. 90 - 91.
Тарасова Е. Г. Нетрадиционные методы принятия решений на примере области анализа и классификации трафика // Методы и средства обработки информации. Труды второй Всероссийской научной конференции/ Под ред. Л. Н. Королева. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. - с. 188 — 193.
Тарасова Е.Г. Функции риска как составляющая специального подхода к анализу классификации трафика // Журнал Исследовано в России, октябрь 2005,
Благодарности
Автор выражает благодарность за помощь в работе научному руководителю доктору физико-математических наук, профессору Мельникову Б.Ф., а также признательность за сотрудничество коллегам: доктору биологических наук, профессору Нестеровой-Потатуркиной
Н.И., кандидату биологических наук Красноперовой Ю.Ю., начальнику отдела глобальных сетей ЦТКиТИ Гуськову П.А., доктору медицинских наук, профессору Машину В.В.
Основное содержание диссертации и достигнутых автором результатов отражено в автореферате. Вниманию оппонентов предложены основные теоретические выкладки и практические результаты с подробным описанием исследований.
Разработка подхода к построению систем принятия решений для рассматриваемых в работе областей
Важной задачей, поставленной в работе, является разработка подхода к построению систем принятия решений. В данной работе автор предлагает подход к построению систем принятия решений отличный от классических (рис 1.) тем, что в качестве основополагающего метода принятия решений (как механизма, создающего правила для анализа и оценки ситуаций) используется метод функций риска, который в перечисленных областях применяется впервые. Разработанный для данного исследования подход - это способ анализа и оценки ситуаций, основных этапов процесса, а также его изучение. Согласно подходу, в первую очередь выявляются и анализируются наиболее характерные и значимые этапы изучаемого процесса, определяющие дальнейшее функционирование и развитие системы принятия решений. При постановке и формулировке задач автору не ставилась задача построения законченной экспертной системы в каждой области, а требовалось создать систему принятия решений, позволяющую производить динамический анализ данных. Рассмотрим основные принципы предложенного автором подхода.
На этапе идентификации при разработке определяются задачи, которые подлежат решению. А именно, в настоящей диссертации были определены следующие задачи. 1. В области микробиологии необходима оценка стадий заболевания дисбактериоза. 2. При обработке трафика следует дать оценку рабочих ситуаций по количеству и типу трафика. 3. В области неврологических заболеваний требуется оценка стадий заболевания энцефалопатии и дальнейшее определение коэффициента корреляции параметров.
Выявляются цели разработки, состоящие в получении динамических систем принятия решений для анализа и оценки ситуаций в каждом случае. Определены вычислительные ресурсы и группы экспертов к каждой области. На этапе концептуализации производится анализ каждой проблемной области с участием экспертов, создаются ситуационные модели. Инженером по знаниям (автором) определяется метод решения задач (эвристический метод функций риска), проектируется структура баз данных для каждой задачи. На этапе формализации создается модель анализа и оценки ситуаций, содержащая:
1. Функциональную модель на основе эвристического метода функций риска и локальных методик области.
2. Ситуационные модели каждой области, представляющие собой группы данных требующие анализа и оценки.
3. Базы данных каждой области - структуры адекватного представления данных, участвующих в работе динамической системы.
4. Алгоритмы, реализующие функциональную модель области.
На этапе реализации выбираются язык программирования и платформа, происходит преобразование формальных знаний в работающие программы. Реализуется программа для работы системы по анализу и оценке ситуаций, а также программы, работающие с используемыми структурами данных. Осуществляется наполнение базы знаний системы.
На этапе тестирования осуществляется совместная с экспертом проверка работы созданного варианта системы на репрезентативных задачах. В процессе тестирования анализируются возможные источники ошибок.
Представим основные процедуры авторского подхода к построению систем принятия решений. 1. Разработка области спецификации, создание ситуационной модели. 2. Установление стандартных ситуаций, рассмотрение контрольной группы как эталонной (возможно нескольких групп). 3. Разработка правил и модулей анализа и оценки для стандартных случаев на основе функций риска. 4. Выполнение правил и модулей для стандартных случаев. 5. Определение и разработка правил анализа и оценки для возможных случаев при работе системы в будущем. 6. Выполнение правил и модулей для случаев, обозначенных в ситуационной модели. 7. Выполнение правил для новых случаев, добавленных в ходе работы системы.
На таких значимых этапах построения системы принятия решений, как идентификация, выполнение и тестирование, происходит непосредственное общение с экспертами областей - для получения знаний и экспертной оценки полученных результатов. Для этих целей автором разработана методика получения знаний от экспертов на основе существующих подходов с учетом специфики метода принятия решений, которая представлена в следующем разделе.
Обзор и анализ существующих эвристических методов принятия решений, методов корреляции и сбора статистики по трафику
Рассмотрим некоторые альтернативные эвристические методы принятия решений, которые могут быть применимы в задачах, представленных в работе, и приведем сравнительную характеристику.
Методы перебора
Методы перебора (проб и ошибок) какое-то время использовались для решения дискретных задач, в том числе задачи коммивояжера, но число возможных вариантов растет экспоненциально в зависимости от размеров задачи, и здесь мы получаем «п!» маршрутов. Подобный метод считается неэффективным [6]. Решение задачи зависит от способа организации перебора, а он в свою очередь может быть случайным, (что при хорошей программно реализации экономит и является самым простым способом) и последовательным. Методы слепого перебора, полного перебора или поиска в глубину являются исчерпывающими процедурами поиска путей к целевой вершине. В принципе эти методы обеспечивают решение задачи поиска пути, но часто эти методы невозможно использовать, поскольку при переборе придется раскрыть слишком много вершин, прежде чем нужный путь будет найден. Так как всегда имеются ограничения на время вычисления и объем памяти, то нужны другие методы, более эффективные, чем методы слепого перебора. В данном методе при допущении возможности перебора всех вариантов за разумно продолжительное время, можно предположить нахождение оптимального решения.
Для решения задачи можно сформулировать правила, позволяющие уменьшить объем перебора. Такие правила используются для ускорения поиска и зависят от специфической информации о задаче - эвристической информации, помогающей поиску решения. Методы и процедуры, использующие такую информацию, можно назвать эвристическими.
«Один из путей уменьшить перебор состоит в выборе более "информированного" оператора, который не строит много не относящихся к делу вершин. Этот способ применим как в методе полного перебора, так и в методе перебора в глубину. Другой путь состоит в использовании эвристической информации для модификации алгоритма перебора в глубину. Вместо того, чтобы размещать вновь построенные вершины в произвольном порядке в начале списка, их можно расположить в нем некоторым определенным образом, зависящим от эвристической информации. Так, при переборе в глубину в первую очередь будет раскрываться та вершина, которая представляется наилучшей. Более гибкий (и более дорогой) путь использования эвристической информации состоит в том, чтобы, согласно некоторому критерию, на каждом шаге переупорядочивать вершины списка. В этом случае перебор мог бы идти дальше в тех участках границы, которые представляются наиболее перспективными. Для того, чтобы применить процедуру упорядочения, нам необходима мера, которая позволяла бы оценивать "перспективность" вершин. Такие меры называют оценочными функциями» [29]. Оценочная функция должна обеспечивать возможность ранжирования вершин (кандидатов на раскрытие) чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели.
Метод перебора можно рассмотреть и в областях, рассматриваемых автором диссертации. Например - для решения задачи по определению оптимального значения количества различных видов бактерий в микрофлоре при анализе данных нескольких стадий дисбактериоза. В таком случае для улучшения метода и ускорения поиска стоит задача по определению правил для построения графа и оптимизации поиска. Согласно предложенным вариантам, описанным выше, необходимо воспользоваться услугами информированного эксперта, который смог бы отбросить ненужные вершины (значения в вариационном ряду по определенному типу бактерий) или располагать вновь построенные вершины не произвольно, а согласно имеющейся эвристической информации. Например, выбирается предположительное искомое объективное значение как вершина дерева поиска х, в левую вершину и последующие будут размещаться наибольшие по значению вершины и т.д., а в правую вершину и последующие наименьшие и так далее. Далее используя, например, тот же самый метод функций риска (возможны и другие варианты), мы определяем близкое к искомому значение в каждом направлении, и сравниваем его с вершиной. При этом для упорядочивания вершин на каждом шаге можно использовать оценочные функции.
Однако данный метод неудобен и неэффективен для решения поставленной задачи в связи с большими временными затратами на следующие действия: - Построение графа; - Перебор ненужных вариантов; - При больших объемах данных существенные временные и вычислительные затраты;
Характеристики метода перебора, а также других методов принятия решений в ЗДО представлены в Таблице 1. Сравнительные характеристики методов решения ЗДО, с. 33.
«Оптимальной стратегии организации перебора для многомерных задач нет, использование случайных точек приводит к проблеме хранения и обновления сложного множества заведомо не оптимальных точек». Для задач большой размерности предлагается метод ветвей и границ [60].
Метод ветвей и границ
Впервые метод ветвей и границ был предложен Лендом и Дойгом [99] в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его "второе рождение" связано с работой Литтла, Мурти, Суини и Кэрела [100], посвященной задаче коммивояжера [38]. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. Метод ветвей и границ применим как к полностью, так и частично целочисленным задачам.
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества, (стратегия "разделяй и властвуй"). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения того, насколько вероятно данное
подмножество содержит оптимальное решение. Например, для задачи анализа трафика проверка может осуществляться посредством вычисления оценки снизу для целевой функции на определенном подмножестве параметров трафика «дельта». Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы (а именно, объективной оценкой исследуемого показателя трафика).
Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из не отброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.[ 7, 43, 57].
Разработка алгоритма анализа и оценки стадий дисбиоза по количеству заданных видов бактерий
Первым шагом алгоритма является анализ данных каждой выделенной экспертом группы в задаче методом функций риска. Случай задан в контексте метода, если выбраны функции для определения весовых коэффициентов.
Выбор функций определения весовых коэффициентов для анализа стадий дисбиоза
На шаге алгоритма, где производится анализ определенных в задаче групп методом функций риска необходимо эвристически определить функции размещения весовых коэффициентов. Согласно методу функций риска, рассмотренному в функциональной модели анализа, автором предложен следующий подход.
Анализируя данные контрольной группы, для определения весовых коэффициентов следует выбирать убывающие функции. Такой подход позволит задать контрольную группу в функциональной модели и получить в итоге меньшую объективную оценку стадии. В переходной группе выбор функции для определения весовых коэффициентов производился аналогичным образом.
В критических группах функции определения весовых коэффициентов следует выбирать возрастающие, оценку количества бактерий, в таком случае, получим большую. Кроме того, действует разделение на подгруппы бактерий, следовательно, итоговая объективная оценка количества бактерий главной подгруппы приближена к большей границе (большее значение), а значения объективных оценок для остальных подгрупп приближены к меньшему значению.
При создании системы состояний в данной задаче алгоритм анализа и оценки групп реализует отбор объективной оценки по подгруппам бактерий. Среди общего числа бактерий идет разделение на подгруппы по видам флоры, что влияет на определение результативной оценки количества рассматриваемого вида бактерий.
Критерии отбора объективной оценки в задаче анализа этапов развития дисбиоза
Критерии отбора учитывают принадлежность рассматриваемой подгруппы бактерий (по флоре) к определенной группе (контрольная, переходная, критическая). Из полученных в ходе предварительного анализа оценок количества каждого вида бактерий отбирается одна объективная оценка. Отбор осуществлялся следующим образом. В контрольной и переходной группах итоговое значение оценки числа полезных бактерий (подгруппа главной флоры) выбиралось минимальное из полученных, а в подгруппах патогенных бактерий (сопутствующая и остаточная флора) максимальное из полученных на предыдущем шаге алгоритма. Рассмотрим следующие множества. Пусть, G - множество видов бактерий главной флоры (подгруппы), S - множество видов бактерий сопутствующей флоры (подгруппы), О - множество видов бактерий остаточной флоры (подгруппы). Х- числовые значения количества конкретного вида бактерий в единице микрофлоры. Если X. Є G характеризуют контрольную или переходную группу, то в результате применения метода функций риска (Эвристика 1), а именно функций у,,... у,, будет получен некоторый вектор оценок ЧЛ . Тогда результирующая объективная оценка количества бактерий в этом случае будет равна: Если X. Є S или X, Є О характеризуют контрольную или переходную группу, то итогом применения метода функций риска, а именно функций /j, ... /„, будет вектор оценок Ч л. Тогда результирующая объективная оценка количества бактерий в этом случае будет равна: Ч7 = тахЧЛі (Критерий к2.).
В критических группах итоговое значение для объективной оценки полезных бактерий (подгруппа главной флоры) выбиралось максимальное из полученных на предыдущем шаге, а в подгруппах патогенных бактерий (сопутствующая и остаточная флора) минимальное из полученных на предыдущем шаге алгоритма. Пусть, G — множество всех видов бактерий главной флоры (подгруппы), S - множество всех видов бактерий сопутствующей флоры (подгруппы), О - множество всех видов бактерий остаточной флоры (подгруппы). X. - числовые значения по конкретному виду бактерий.
Если X. Є G характеризуют критическую группу, то в результате применения метода функций риска (Эвристика 1), а именно функций z., ... 2, , будет получен некоторый вектор оценок Q, .
Тогда результирующая объективная оценка количества бактерий в этом случае будет равна: П = тахГ2л (Критерий кЗ.). Если X. Е S или X. Є О характеризуют критическую группу, то в результате применения метода функций риска (Эвристика 1), а именно функций /,,... fm, будет получен некоторый вектор оценок 1т. Тогда результирующая объективная оценка количества бактерий в этом случае будет равна: П = minQm (Критерий к4.). Подобный отбор обусловлен биологическими факторами, так как бактерии главной флоры в достаточно большом количестве сигнализируют о здоровом организме (в контрольном случае адекватнее их количество выбирать в меньшем значении, а в критическом случае - в большем). В малом количестве бактерии главной флоры сигнализируют о заболевании (норма по количеству рассматриваемых видов бактерий приведена Таблица П.).
Компоненты программного комплекса в области микробиологии
Для реализации алгоритма анализа и оценки групп в области микробиологии были разработаны следующие программы (как часть программного комплекса): программы анализа и оценки количественных данных рассматриваемых видов бактерий; элементы запросов к БД.
Программы анализа и запросов реализованы на языке программирования Perl v.5. Программы анализа и оценки реализуют метод функций риска применительно к данным ситуационной модели и формируют результат. Элементы запросов, встречающиеся в программах анализа данных, позволяют с помощью структурированного языка SQL добавлять промежуточные результаты в базу и получать результаты работы системы в удобном виде.
Структурная схема последовательности выполнения компонентов программного комплекса для решения задачи оценки групп, а также определения динамической оценки количества рассматриваемых видов бактерий в микрофлоре, приведена нарис 10.
Скрипт bdl.pl - программа анализа и оценки данных по дисбиозу, осуществляет работу эвристического метода и sql-запросы на заполнение таблицы «Оптимальные» базы данных «Bakter», Приложение П.4.
Скрипты sel_min.pl и sel_max.pl - являются частью программы анализа и оценки данных, осуществляют выборку объективного значения из полученных оценок, согласно критериям отбора на уровне подгрупп, а также создают запросы на добавление данных в таблицу «Диагноз» базы данных «Bakter», Приложение П.4.
Результатом работы части программного комплекса для области микробиологии может служить следующий пример. В Таблице 7. приведен случай инфицированного организма, данные по лактобактериям (подгруппа -главная флора) заболевание на 12 сутки, для определения весовых коэффициентов в методе использовались возрастающие функции (так как случай критический).
Из Таблицы 7. следует, что эвристическим методом получено несколько оценок количества данного вида бактерий Q, в группе с заболеванием на 12 сутки. Это объясняется использованием нескольких функций \, ... у, определения весовых коэффициентов для анализа этой стадии дисбиоза. Из всех значений оценок количества лактобактериЙ выбирается одно - объективное значение П, согласно критерию отбора по подгруппам (Критерий (кЗ)). Так как группа критическая, подгруппа -главная флора, то результатом является большее значение из представленных оценок (выделено жирным шрифтом в Таблице 7.). Этот показатель заносится в таблицу соответствий - «Диагноз» базы данных «Bakter», Приложение П.4.
В группах с заболеванием (критические группы), согласно критерию отбора, на любой стадии дисбиоза объективная оценка количества бактерий главной подгруппы выбирается большая (Критерий кЗ), а объективная оценка количества бактерий всех остальных подгрупп - меньшая (Критерий к4). В переходной или контрольной группе объективная оценка количества бактерий главной подгруппы выбирается меньшая (Критерий kl), а во всех остальных подгруппах - большая (Критерий к2). Норма по количеству бактерий в микрофлоре приведена в Таблице 10.
Рассмотрим результаты вычислительного эксперимента по определению объективных оценок по всем видам бактерий в контрольной группе. При их определении для каждого вида бактерий использовались функции с пометкой "dec" - убывающие (см. Приложение П.З).
Для бактерий вида "Протеи" в контрольной группе, с учетом критерия отбора по подгруппам, значение объективной оценки получено Х = 0.0743750000000001 Кед./г. Вид бактерий принадлежит к остаточной флоре, сигнализирующей в большом количестве о заболевании. Полученное значение оценки данного вида бактерий в группе максимальное предельно допустимое, которое характеризует эту группу как контрольную. Превышение этого показателя будет рассматриваться системой принятия решений, как случай, который можно отнести либо к переходной группе, либо к критической.
Для бактерий вида "Бактероиды" в контрольной группе, согласно критерию отбора по подгруппам, выбирается меньшее значение для объективной оценки. Вид бактерий принадлежит к подгруппе главной флоры, сигнализирующей о здоровом организме при достаточно большой численности (96% флоры). Полученное значение объективной оценки минимальное предельно допустимое, характеризует эту группу как контрольную. При получении меньших количественных характеристик, система будет рассматривать эти случаи, как относящиеся к переходной или критической группе.
Остальные бактерии подчиняются таким же правилам критерия отбора, согласно принадлежности определенному виду флоры (подгруппе).
Анализ видов бактерий, принадлежащих подгруппе сопутствующей флоры, проводился аналогично анализу видов бактерий подгруппы остаточной флоры, обе подгруппы сигнализируют о заболевании. Правила критерия отбора по подгруппам в переходной группе бактерий аналогичны правилам отбора в контроле.
Для критической группы строится обратная схема, руководствуясь правилами отбора по подгруппам,
В Таблице 16. приведены результаты поиска объективных оценок количества бактерий по каждой группе и по каждому виду бактерий. В записях «мед. 10» указаны значения, умноженные на п=10, обращая результат анализа к первоначальному порядку. Приложение П.2 (для анализа и оценки групп данных на отрезке [0,1] требовалось умножение всех значений на величину m = 0.1).
Окончательные результаты исследований сопоставлялись с данными нормального состава биотопа, Таблица 17. Норма, в которой приведены допустимые пределы количественных значений каждого вида бактерий для рассматриваемых случаев в грамме.
