Моделирование систем и процессов защиты информации в условиях неполноты и недостоверности данных

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА МОДЕЛИРОВАНИЕ СИСТЕМ И ПРОЦЕССОВ ЗАЩИТЫ ИНФОРМАЦИИ В УСЛОВИЯХ НЕПОЛНОТЫ И НЕДОСТОВЕРНОСТИ ИСХОДНЫХ ДАННЫХ

Содержание Введение

1. Виды неопределенностей в исходных данных систем и процессов защиты информации

1.1 Понятие системы и процесса защиты информации

1.2 Полнота и достоверность исходных данных

1.3 Выводы по главе

2. Методы восстановления пропущенных значений и структурирование неопределенностей в исходных данных

2.1 Исследование методов восстановления пропусков в массивах данных

2.2 Обзор методов структурирования данных в условиях неопределенности

2.3 Структурирование данных при моделировании эволюционных дискретных процессов

2.3.1 Нечеткие данные, возникающие в процессе математического моделирования

2.3.2 Дискретные задачи с интервальными данными

2.3.3 Структурирование данных при моделировании эволюционных дискретных процессов

2.3.4 Структурирование данных на базе интеллектуальных инструментальных средств

2.4 Выводы по главе

3. Моделирование систем и процессов защиты информации в условиях неполноты и недостоверности исходных данных

3.1 Метод экспертного построения функций, принадлежности оценки уровня риска информационной системы

3.2 Задачи защиты информации, формализуемые как экстремальные задачи на графах с интервальными весами

3.3 Выводы по главе Заключение Список используемых источников моделирование данные информационная система

Введение

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

Объект исследования — системы и процессы защиты информации.

Предмет исследования — условия неполноты и недостоверности исходных данных в показателях процессов и систем защиты информации.

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

Задачи выпускной квалификационной работы:

— привести обзор возможных неопределенностей в исходных данных систем и процессов защиты информации;

— исследовать методы восстановления пропущенных значений и структурирования неопределенностей в исходных данных;

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

1. Виды неопределенностей в исходных данных систем и процессов защиты информации

1.1 Понятие системы и процесса защиты информации Задачи защиты информации характеризуются следующими основными особенностями:

— наличием большого числа факторов, влияющих на эффективность решения задачи;

— отсутствием количественных достоверных исходных данных об этих факторах;

— отсутствием формальных (математических) методов получения оптимальных результатов решения по совокупности исходных данных.

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

Система — совокупность элементов и связей между ними, обладающая определенной целостностью.

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

Система защиты информации — совокупность взаимосвязанных элементов, функционирование которых направлено на обеспечение безопасности информации.

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

Система защиты информации описывается следующими параметрами:

1) цели и задачи (конкретизированные в пространстве и во времени цели);

2) входы и выходы системы;

3) процессы внутри системы, обеспечивающие преобразование входов в выходы.

Цели представляют собой ожидаемые результаты функционирования системы защиты информации.

Задачи — необходимые действия для достижения системой поставленных целей.

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

Входами системы защиты информации являются угрозы информации.

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

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

На рисунке 1 приведена схема этих параметров.

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

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

Различают вербальные, физические и математические модели и соответствующее моделирование.

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

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

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

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

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

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

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

В результате этого этапа определяются:

1) модели объектов защиты с указанием всех источников информации с описанием факторов, влияющих на их безопасность;

2) цена защищаемой информации каждогого источника.

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

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

Значения характеристик при этом будут располагаться на пересечении соответствующих строк и столбцов. Совокупность всех ОХТ, необходимых для обеспечения решения всех задач объекта, называется его информационным кадастром. Для оценки полноты информации часто используют следующую методику.

Обозначим через элемент, находящийся вй строке им столбце интересующего нас компонента соответствующей ОХТ, причем:

Тогда в качестве коэффициента полноты информации в данной ОХТ можно принять величину:

где — число строк, а — число столбцов ОХТ.

Однако при этом не учитывается важность (значимость) различных элементов. В целях устранения этого недостатка положим, что есть коэффициент важности элементай строки иго столбца. Тогда очевидно, в качестве меры взвешенной полноты информации в рассматриваемой ОХТ можно принять величину:

.

Достоверность определяется как «уровень разумной уверенности в истинности некоего высказывания, который удовлетворяет некоторым правилам непротиворечивости и в соответствии с этими правилами формально может быть выражен числом».

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

Используя идею байесовского подхода, можно поставить вопрос о достоверности фрагментов информационной базы данных в более общем плане, рассматривая любой ее фрагмент как гипотезу, а фрагменты, с которыми он связан, как свидетельства относительно фрагмента-гипотезы. Под фрагментом информационной базы данных понимают часть содержания или структуры, обладающую свойством дискретности и независимости, т. е. некоторую совокупность данных или высказываний, имеющую самостоятельный смысл. Достоверность (Д) фрагмента поступающего в информационную базу данных, зависит от достоверности источника информации и методики ее получения. Каждый вновь поступающий в информационную базу данных фрагмент (НФЗ — новый фрагмент знаний) есть пара:

где — значение фрагмента; - достоверность информации.

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

2. Методы восстановления пропущенных значений и структурирование неопределенностей в исходных данных

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

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

Поэтому более перспективным является иной путь — заполнение пропусков перед анализом фактических данных. Можно выделить следующие преимущества данного подхода: ясное представление структуры данных; вычисление необходимых итоговых значений; уверенная интерпретация результатов анализа, так как можно опираться на традиционные характеристики и суммарные значения.

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

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

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

Поясним постановку задачи предсказания (восстановления) значений пропущенных элементов на примере обработки таблицы размером не содержащей пропусков.

Пусть в нашем распоряжении имеется набор различных методов (алгоритмов):

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

.

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

Методы из набора могут отличаться друг от друга лежащими в их основании эвристическими предположениями (гипотезами). Возможность использования методов разной степени сложности связана с тем, насколько простым или сложным является механизм, согласно которому данные оказываются пропущенными. Используя терминологию, предложенную в, будем называть пропуски в данных полностью случайными (data are missing completely at random — MCAR), если условная вероятность (пропущено/прочие) не зависит ни от, ни от прочих (то есть эта вероятность постоянна для всех наблюдений, и наблюдаемые являются случайной под выборкой тех, которые должны были получиться в эксперименте). Пропуски в данных называются случайными (missing at random — MAR), если вероятность (пропущено/прочие) не зависит от, но может зависеть от других X. Оказывается, что в этих случаях механизм пропусков несущественен (ignorable), и к данным применимы вариации методов восстановления пропусков. Наконец, если (пропущено/прочие) зависит от самого, то механизм пропусков является существенным (non-ignorable), и для корректного анализа данных необходимо знать этот механизм. Введенные понятия относятся к отдельным переменным, и в пределах одной и той же базы данных можно, в принципе, наблюдать все приведенные варианты. Можно построить тесты, отличающие MAR от MCAR, однако по данным невозможно отличить, являются ли они MAR, или же механизм пропусков существенен.

Характеристика известных методов восстановления пропусков по литературным данным. Первый возможный подход к обработке данных с пропусками — это просто исключение некомплектных объектов. Данный метод легко реализуется, но необходимым условием его применения является следование данных требованию MCAR. Кроме того, необходимо, чтобы количество пропусков было небольшим, иначе происходят сильные смещения, кроме того, как показывает практика, данный метод не очень эффективен.

Следующим подходом, реализованным в большом числе алгоритмов, является подход с заполнением пропусков. Наряду с очевидными преимуществами данного подхода ему присущи недостатки: «…Опасность этого подхода в том, что он не позволяет отличать ситуации, где задача не очень трудна и может быть корректно решена таким способом, от ситуаций, где обычные оценки по реальным и подставленным данным сильно смещены».

Выделяют следующие два принципиальных недостатка данного подхода.

1. Как правило, параметры для алгоритма заполнения пропусков вычисляются по присутствующим данным, что вносит зависимость между наблюдениями. Конечно, такой искусственной зависимости не возникает, если проводится заполнение константой или случайными значениями, не зависящими от присутствующих наблюдений в выборке, или методом подстановки без подбора. Но на практике эти методы представляют малую ценность. Зависимости можно также избежать, разделяя исходную выборку на две под выборки и вычисляя подстановки (например, средне выборочные значения) для анализируемой под выборки по значениям наблюдений во второй под выборке. При таком подходе приходится жертвовать частью информации, чтобы заполнить пропущенные значения.

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

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

Заполнение средними (средним по всей выборке или средними по группам) — применение имеет смысл только в случае следования данных условию MAR, данная группа методов легко реализуема; недостатки — искажение распределения данных, уменьшение дисперсии.

Методы заполнения с подбором — подобны методам заполнения средними, легко реализуемы, кроме того, при применении данных методов больше разброс дисперсии предсказанных значений пропусков, не искажается распределение. Недостаток — выявление распределения обрабатываемой генеральной совокупности данных по полученной выборке комплектных данных.

Заполнение по регрессии. В основу данной группы методов положены хорошо известные алгоритмы регрессионного анализа. Из условий применения данного метода можно выделить требование о следовании данных условию MAR (хотя для частных случаев возможно применение более слабых требований) и требования, относящиеся к выполнению предпосылок регрессионного анализа. Недостатки подобных методов очевидны: качество предсказания (восстановления пропусков) напрямую зависит от успешного выбора взятой за основу регрессионной модели.

Метод сплайн-интерполяции — обоснованный математически метод интерполяции, показывающий хорошие результаты. Для успешного применения необходимо, чтобы данные следовали условию MAR. Недостатки метода следуют из самой его идеи. Например, в случае восстановления группы пропусков, следующих подряд друг за другом, результат аппроксимации сплайном данной группы не всегда может дать оценки, приближающиеся с достаточной точностью к значениям, которые могли бы быть на месте пропусков.

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

МП-оценивание (EM-алгоритм) — относится к категории методов моделирования. Особенность данных методов — построение модели порождения пропусков с последующим получением выводов на основании функции правдоподобия, построенной при условии справедливости данной модели, с оцениванием параметров методами типа максимального правдоподобия. Отметим, что если другие методы восстановления пропусков требуют, чтобы данные отвечали условию MAR (или MCAR как более жесткому), то для данных методов возможно построение моделей, учитывающих конкретную специфику области, как следствие, возможна постановка более слабых условий к данным. Недостаток — необходимость построения модели порождения пропусков.

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

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

Локальные алгоритмы восстановления пропусков. Алгоритмы семейства Zet (Wanga), по сути, являются детально проработанной и апробированной технологией верификации экспериментальных данных, основанной на гипотезе их избыточности. Внешне они сходны с методом локального заполнения. Данные алгоритмы хорошо показали себя, но необходимость задания ряда важных параметров приводит к необходимости убедиться в правдоподобности восстановленных значений.

Существуют другие альтернативные подходы к восстановлению данных. В качестве примера отметим использование нейросетей. Несмотря на некоторую эквивалентность моделей статистики и нейросетевых парадигм, трудно выявить явные преимущества и недостатки применения нейросетевых технологий для восстановления данных.

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

Итоговые результаты по исследовавшимся методам таковы.

1. Метод замены пропущенного значения общим средним из присутствующих элементов.

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

2. Метод замены пропущенного значения средним из ближайших присутствующих элементов переменной.

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

Таким образом, этот метод можно использовать только для восстановления одиночных пропусков в рядах данных.

3. Метод восстановления пропущенного значения сплайн-интерполяцией по присутствующим элементам.

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

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

4. Метод восстановления пропущенного значения на основе использования Zet-алгоритма.

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

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

Конечно, у данного метода есть ограничения. Например, между данными должна прослеживаться причинно-следственная (вероятностная) связь, а количество существующих наблюдений, по которым восстанавливаются пропуски, не должно быть малым. Если данные сильно зашумлены и искажены, обладают большой долей пропусков, то результат восстановления, естественно, будет некорректен: здесь как нельзя более ясно работает правило «мусор на входе — мусор на выходе». Однако даже в такой ситуации описываемый алгоритм будет искать закономерности в присутствующих данных, и осуществлять восстановление пропусков, в отличие от других методов, для которых в подобной ситуации пропуск заполняется совершенно фантастическими значениями.

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

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

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

1) 82−84% - из-за неточности исходных данных,

2) 14−15% - из-за неточности математической модели,

3) 2−3% - из-за неточности применяемого метода.

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

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

— подавление влияния неточной информации с дальнейшим использованием обычных детерминированных алгоритмов;

— переход при наличии неточной информации на специальные алгоритмы (стохастические, нечеткие, интервальные).

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

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

— применение процедур сглаживания и отсечения может быть обоснованным только при непосредственном учете специфики наблюдаемого процесса;

— алгоритмы, используемые для реализации методов первой группы, являются достаточно сложными;

— говоря об адекватности допущений, положенных в основу методов первой группы, можно говорить об их эвристическом характере, т. е. отсутствии достаточно строгой обоснованности.

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

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

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

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

В условиях многокритериальности в выборе и принятии одного решения заложено противоречие, т. к. обязательно найдутся решения, которые по некоторым критериям являются лучше выбранного. Следовательно, указанных противоречий можно избежать лишь в случае, если говорить о нахождении множества «подходящих» решений. Этот тезис первым достаточно четко сформулировал итальянский экономист Вильфредо Парето еще в 1904 году в форме так называемого принципа Парето. Согласно Парето, возможные решения следует искать среди не улучшаемых альтернатив, т. е. альтернатив, улучшение которых по одним критериям приводит к ухудшению по другим критериям. Принцип этот достаточно очевидный и очень важный с чисто прикладной точки зрения: он позволяет, во-первых, сжать множество альтернатив, во-вторых, он демонстрирует те потери, которые имеет оперирующая сторона по тем или иным показателям, стремясь улучшить какой-то определенный показатель.

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

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

(1)

критерии, которой, могут принимать вид:

, (2)

Если фиксированы все параметры ВЦФ (1) и система условий, определяющих МДР, то принято говорить об индивидуальной задаче.

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

Перечислим наиболее известные типы МА.

— множество допустимых решений, которое рассматривается в качестве МА в случае, когда критерий выбора и принятия решения является очень сложным.

— паретовское множество, состоящее из всех паретовских оптимумов. Для данной индивидуальной задачи с ВЦФ (1) — (2), состоящей из максимизируемых критериев:

(в (2)),

решение называется паретовским оптимумом, если не существует такого элемента, который удовлетворяет неравенствам:

,

среди которых хотя бы одно является строгим. Эти неравенства заменяем на обратные, если в (1.2) значение .

— полное множество альтернатив, которое определяется как подмножество минимальной мощности и такое, что:

.

ПМА является обобщением понятия «оптимум», определенного для 1- критериальных, т. е. оптимизационных задач.

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

2.3 Структурирование данных при моделировании эволюционных дискретных процессов

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

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

Для преодоления трудностей представления неточных понятий, анализа и моделирования систем, в которых участвует человек, американским математиком Лотфи Заде в 1965 г. была предложена теория нечетких (размытых) множеств. Подход на основе теории нечетких множеств является, по сути дела, альтернативой общепринятым количественным методам анализа систем. Он имеет три основные отличительные черты:

— вместо или в дополнение к числовым переменным используются нечеткие величины и так называемые «лингвистические» переменные;

— простые отношения между переменными описываются с помощью нечетких высказываний;

— сложные отношения описываются нечеткими алгоритмами.

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

Для реальных сложных систем характерно наличие одновременно разнородной информации:

— точечных замеров и значений параметров;

— допустимых интервалов измерения;

— лингвистических критериев и ограничений, полученных от специалистовэкспертов и т. д.

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

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

2.3.2 Дискретные задачи с интервальными данными Применение интервального анализа и различных минимаксных (гарантированных) подходов обладает целым рядом преимуществ:

— не требуется знание вероятностных характеристик неопределенных факторов, которые редко бывают точно известны на практике;

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

— cтатистические характеристики не могут гарантировать определенный исход одного конкретного опыта;

— во всех случаях даются гарантированные двусторонние аппроксимации искомых решений.

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

1. Неопределенность в задании исходных данных.

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

3. Приближенный характер используемого численного метода.

4. Степень учета зависимостей между участвующими в вычислении интервальными объектами (переменными и константами).

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

Приведем интервальную арифметику.

Пусть — множество всех вещественных чисел. Под интервалом:

,

понимается замкнутый ограниченный отрезок на числовой оси.

Множество всех интервалов обозначим через. Элементы записываются прописными буквами. Если — элемент:

(),

то его левый и правый концы обозначим и, а также:

.

Символы и т. п. понимаются в обычном теоретико-множественном смысле, причем обозначает не обязательно строгое включение, т. е. соотношение допускает равенство интервалов.

Два интервала:

,

равны тогда и только тогда, когда:

.

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

является снова интервалом.

Для интервала симметричным, по определению, является интервал, у которого:

.

Шириной интервала называется величина:

.

Середина есть полу сумма его концов:

.

Абсолютная величина определяется как:

.

Нетрудно заметить, что, когда, причем, если и .

Расстояние между элементами вводится равенством:

.

Вырожденный интервал, т. е. интервал с совпадающими концами отождествляется с вещественным числом. Таким образом, имеем включение .

Арифметические операции над интервальными числами определяются следующим образом. Пусть, , тогда:

(3)

В случае деления .

Определение (3) эквивалентно соотношениям:

(4)

(5)

(6)

(7)

Операцию вычитания можно выразить через сложение и умножение, положив:

и .

Если и — вырожденные интервалы, то равенства (4) — (7) совпадают с обычными арифметическими операциями над вещественными числами. Из определения (3) непосредственно видно, что интервальные сложения и умножение ассоциативны и коммутативны, т. е. для имеют место равенства:

,

.

Роль нуля и единицы играют обычные 0 и 1, которые отождествляются с вырожденными интервалами и, т. е.:

.

Равенства (3) — (7) показывают, что если один из операндов является невырожденным интервалом, то и результат арифметической операции также невырожденный интервал. Исключение составляет умножение на. Отсюда следует, что для невырожденного интервала не существует обратных по сложению и умножению элементов, т.к. если, , то должны быть вырожденными, т. е. вычитание не является обратным сложению, деление не обратно умножению. Значит,, , когда. Всегда и .

Основная теорема интервальной арифметики отражает такое важное транзитивное свойство, как монотонность по включению. Это значит, что если, , то выполняются соотношения:

, , (если).

2.3.3 Структурирование данных при моделировании эволюционных дискретных процессов Пусть эволюционный процесс определяется векторным итерационным уравнением

(8)

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

(9)

Будем называть функцию «функцией наблюдателя». Временной ряд образует траекторию, которая является плотной на аттракторе.

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

(10)

Термин «фазовая траектория» обычно подразумевает, что соседние точки множества (9) для наглядности соединены отрезками прямой или кривой линии. Объективную информацию о характере поведения эволюционного процесса (10) исследователь может получить через наблюдения (9), опираясь на теорему Такенса: если система, которая порождает временной ряд, является — размерной, и обеспечено выполнение неравенства, тогда в общем случае фазовые траектории воссоздают динамику исследуемой системы. Существует диффеоморфизм между фазовыми траекториями и истинными данными, порождаемыми системой. Этот результат позволяет делать выводы о поведении системы, опираясь на данные наблюдений, и, более того, получать информацию для прогнозирования этого поведения.