Содержание к диссертации
Введение
Глава 1. Анализ методов оценки достоверности обработки информации в автоматизированных системах 11
1.1 Анализ характеристик качества данных 11
1.1.1 Общие характеристики качества данных 12
1.1.2 Особенности возникновения и распространения искажений в данных 14
1.1.3 Анализ существующих показателей достоверности 16
1.2 Анализ существующих моделей и методов поддержки принятия решений 17
1.2.1 Модели процесса принятия решений в организациях 17
1.2.2 Прогнозирование 20
1.2.3 Принципы построения систем поддержки принятия решений 24
1.2.4 Существующие типы моделей данных 30
1.3 Выводы по главе 1 48
Глава 2. Проблемы работы с искажениями данных в системах диспетчерского управления 50
2.1 Типы искажений в данных 50
2.1.1 Отсутствие значений 51
2.1.2 Аномальные значения (выбросы) в данных 52
2.2 Задачи моделирования искажений в данных обучающей выборки 53
2.2.1 Искажения, связанные с выбросами 55
2.2.2 Искажения по причине отсутствия значений 63
2.3 Обнаружение выбросов в данных 65
2.3.1 Степень локальной аномальности 67
2.3.2 Проблема выбора параметра MinPts 70
2.3.3 Вычисление расстояний между значениями категориального атрибута 71
2.3.4 Модель анализа выбросов в категориальных атрибутах 75
2.4 Повышение достоверности обработки данных 77
2.4.1 Обработка выбросов 78
2.4.2 Заполнение пропусков в данных 80
2.5 Выводы по главе 2 87
Глава 3. Прогнозная модель поддержки решения управленческих задач 88
3.1 Задача построения модели дерева решений 88
3.2 Методика оценки результатов анализа выбросов в данных 89
3.3 Проблема выбора стратегии повышения достоверности обработки данных 91
3.4 Использование алгоритмов повышения достоверности обработки данных при построении дерева решений 106
3.4.1 Алгоритм выбора стратегии и восстановления данных 106
3.4.2 Алгоритм ГОЗО 107
3.5 Выводы по главе 3 108
Глава 4. Программная реализация и интеграция системы поддержки принятия управленческих решений на основе разработанных механизмов 110
4.1 Разработка программной части системы поддержки принятия управленческих решений 110
4.1.1 Описание основных функций программы 111
4.1.2 Архитектура системы 112
4.1.3 Алгоритм построения дерева решений 116
4.1.4 Описание программы 117
4.2 Интеграция разработанной системы с технологическими процессами предприятия 122
4.2.1 Постановка производственной задачи 122
4.2.2 Описание предметной области решаемой задачи 122
4.2.3 Основные рассматриваемые параметры 123
4.3 Реализация методики тестирования разработанных механизмов анализа данных 124
4.3.1 Процедура тестирования механизмов анализа данных 124
4.3.2 Наборы данных для проведения экспериментов 125
4.3.3 Результаты проведения экспериментов 129
4.4 Итоги внедрения системы 131
4.5 Выводы по главе 4 132
Выводы по работе 133
Список литературы 135
Приложение 1. Фрагменты исходного кода 148
- Модели процесса принятия решений в организациях
- Искажения, связанные с выбросами
- Проблема выбора стратегии повышения достоверности обработки данных
- Результаты проведения экспериментов
Введение к работе
Актуальность работы связана с фактом бурного развития сетевых технологий, формирования единого информационного пространства, глобализацией в целом. Данные явления оказывают серьезное влияние на работу интеллектуальных систем и, в частности, систем поддержки принятия решений. Во-первых, доступ потребителя к информации в целом существенно упрощен, то есть минимально количество усилий для получения обширного объема информации в любой области. Во-вторых, для отдельного частного лица стали легко доступны механизмы создания и публикации информации, становящейся моментально доступной широкому кругу потребителей. Эти изменения невозможны без уменьшения или полной отмены ограничений на создание и публикацию информации, что неминуемо повлекло за собой резкое снижение доли качественной информации в общем информационном пространстве.
Объектом исследования являются системы диспетчерского управления, а именно системы поддержки принятия управленческих решений. Эти системы принадлежат к той категории интеллектуальных систем, в которых анализируются данные, созданные в процессе работы человека.
Предмет исследования. В данной работе исследуются прогностические модели, основанные на классификационных моделях решающих деревьев. В этой области весьма существенными являются работы многих российских и зарубежных авторов, таких как В. Н. Вагин, Д. А. Поспелов, Дж. Куинлан, П. Утгофф, М. Брюниг и другие. В области анализа и разработки управленческих решений важны работы Б. Г. Литвака, в области анализа качества данных -работы Р. Вонга, Дж. Олсона, К. Батини. Разработанные механизмы позволяют эффективно строить модели деревьев решений по наборам исходных данных. Крайне важным моментом при построении моделей является качество исходных данных обучающего множества, поскольку от него фактически зависит результат анализа новых данных.
Цель работы состоит в повышении достоверности обработки информации в диспетчерских системах за счет автоматизации процессов принятия управленческих решений, а именно, в разработке устойчивого к ошибкам в данных механизма работы систем поддержки принятия управленческих решений. Для достижения поставленной цели в ходе работы решаются следующие задачи:
-
Моделирование искажений в данных обучающей выборки с целью контроля точности работы алгоритмов анализа;
-
Обнаружение аномалий в данных. В том числе расчет расстояний между значениями категориального атрибута, а также интерпретация результатов процесса поиска аномалий;
-
Устранение шума в данных на основе анализа данных, не содержащих шум;
4. Выбор стратегии повышения качества данных в условиях ограниченности ресурсов с целью повышения эффективности процесса анализа данных и выработки рекомендаций для принятия управленческого решения.
Научная новизна исследования.
Разработаны процедуры генерации шума в обучающей выборке, позволяющие генерировать шум разного типа. В частности, шум типа «отсутствие значений» и шум типа «аномалии в данных».
Разработан алгоритм расчета степени аномальности значений атрибутов объектов данных на основе предложенной новой формулы расчета расстояний между этими значениями.
Разработана методика интерпретации результатов расчета степени аномальности значений атрибутов данных, позволяющая интерпретировать данные с учетом субъективной степени жесткости анализа, заданной экспертом.
Создана методика выбора стратегии повышения качества входных данных.
Разработан алгоритм построения прогнозной модели анализа данных, устойчивой к шуму двух типов в обучающей выборке.
Методика проведения исследований. Для достижения целей работы использовались методы теории вероятностей, математической статистики, теории машинного обучения, теории информации. Для разработки программной системы применялись современные технологии создания веб-приложений (JavaScript, РНР5) и визуализации (SVG). В процессе исследования использовались результаты современных трудов российских и иностранных авторов.
Достоверность результатов подтверждается теоретическими данными, результатами экспериментов, данными компьютерного моделирования, сравнением с результатами исследований, приведенными в научной литературе по рассматриваемой области.
Практическая значимость. Разработанные в ходе исследования алгоритмы и механизмы реализованы в программной системе, выполняющей анализ данных для организации, имеющей собственный автотранспортный парк. В частности, реализованы механизмы анализа данных по эффективности использования автотранспорта и построения модели дерева решений на основе проведенного анализа. Также реализован механизм поиска и устранения шума в исходных данных, позволяющий повысить точность классификации объектов средствами построенной прогнозной модели. Практическая значимость подтверждается успешным внедрением разработанной системы в качестве модуля корпоративной системы поддержки принятия решений в ООО «Компания РУС» г. Калуга, о чем свидетельствует акт о внедрении.
Апробация работы. Основные положения и научные результаты диссертационной работы докладывались:
на научных семинарах кафедры ИУ-5 МГТУ им. Баумана;
на XIII Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2011»;
на XIV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2012»;
на XV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2013».
Публикации. Материалы по теме исследования опубликованы в 7 печатных работах.
Объем работы. Диссертационная работа содержит 186 страниц, 21 рисунок и 20 таблиц, 1 копия акта о внедрении, список литературы из 122 наименований.
Модели процесса принятия решений в организациях
В [38] рассматривается понятие модели как упорядоченного набора предположений о сложной системе. Модель менее сложна, чем моделируемый объект, и позволяет руководителю лучше разобраться в конкретной ситуации и принять правильное решение. Ниже приводятся наиболее общепринятые классификации моделей процесса принятия управленческих решений [38].
Дескриптивные и нормативные модели. Дескриптивные модели применяются для описания свойств и параметров процесса принятия решений в целях прогнозирования его хода в будущем. Успех применения дескриптивных моделей в значительной степени зависит от точности описания законов и закономерностей функционирования объекта управления. Нормативные модели применяются для управления процессом принятия решений, для формирования его сущностных элементов и его развития. Нормативные модели предполагают активное участие в процессе принятия решений и его моделировании участников процесса принятия решений. Индуктивные и дедуктивные модели. Индуктивные модели строятся путем обобщения наблюдений по единичным частным фактам, которые являются важными для принятия управленческого решения. Качество индуктивной модели определяется тем, насколько, с одной стороны, удается упростить описание ситуации принятия решения, а с другой — насколько верно удается отразить основные свойства моделируемой ситуации.
При разработке дедуктивных моделей исходят не из анализа конкретных фактов, а из упрощенной системы гипотетических ситуаций. Здесь путь создания модели — от абстрактного представления управленческой ситуации к ее конкретной реальности.
Проблемно-ориентированные модели и модели решения. Проблемно-ориентированные модели строятся на внедрении новых методов моделирования применительно к конкретной проблемной ситуации принятия решения. Здесь основная задача состоит в адаптации новых методов для моделирования конкретного управленческого процесса. Модели решения разрабатываются с учетом возможностей проведения экспериментов с ними, а также возможностей современных управленческих технологий и направлены на решение важнейших управленческих задач. Алгоритмы, используемые в этих моделях, определяют специфические требования к условиям их применения и структуре моделей. К числу таких моделей относятся и модели, активно использующие экономико-математические методы решения управленческих задач.
Одноцелевые и многоцелевые модели. Нередко для оценки альтернативного варианта решения необходимо использовать несколько достаточно разнородных, независимых критериев, ориентированных на достижение различных, подчас трудно сопоставимых целей. Однако решение должно приниматься одно, и наиболее предпочтительный вариант решения должен быть обязательно определен. Одноцелевыми называются модели, когда имеется одна четко определенная цель, к достижению которой стремится организация, либо несколько целей, агрегированных в виде одной комплексной цели. В последнем случае степень достижения цели определяется с помощью специально разрабатываемого комплексного критерия. Многоцелевыми называются модели, в которых предполагается стремление к достижению нескольких независимых целей, несводимых к одной комплексной. Существуют методы, позволяющие сопоставлять альтернативные варианты по нескольким критериям и осуществлять их оптимизацию. В некоторых случаях часть целей (критериев) удается записать в виде ограничений соответствующей экономико-математической модели.
Однопериодные и многопериодные модели. Однопериодные модели исходят из предположения, что сумма оптимальных единичных решений в отдельные периоды принятия решений в целом за весь период принятия решений также дает оптимальное решение. Этот подход не всегда оправдан. Иногда выигрыш на отдельном этапе может приводить к большим потерям для организации, если рассматривать весь период, на котором принимаются решения. Многопериодные модели предполагают комплексное решение управленческой проблемы с учетом всего периода принятия управленческого решения. Однопериодные модели могут использоваться при разработке многопериодной модели с целью более адекватного представления ситуации принятия решения.
Детерминированные и стохастические модели. В детерминированных моделях все факторы, оказывающие влияние на развитие ситуации принятия решения, однозначно определены и их значения известны в момент принятия решения. Стохастические модели предполагают наличие элемента неопределенности, учитывают возможное вероятностное распределение значений факторов и параметров, определяющих развитие ситуации. Следует отметить, что детерминированные модели, с одной стороны, являются более упрощенными, поскольку не позволяют достаточно полно учитывать элемент неопределенности. С другой стороны, они позволяют учесть многие дополнительные факторы, зачастую недоступные стохастическим моделям.
Искажения, связанные с выбросами
Атрибуты объектов выборки могут содержать числовые (количественные) или категориальные (качественные) значения. Количественные значения могут быть дискретными или непрерывными. Качественные значения могут образовывать некоторую шкалу, позволяющую сравнивать их между собой, или не иметь подобной шкалы. Например, значения атрибут Скорость = {Низкая, Ниже среднего, Средняя, Выше среднего, Высокая} могут быть ассоциированы с некоторыми числовыми значениями, позволяющими сравнивать их: {Низкая = 0,2; Ниже среднего = 0,3; Средняя = 0,5; Выше среднего = 0,7; Высокая = 1}. Напротив, значения атрибута Цвет = {Красный, Белый, Синий, Зеленый, Желтый} не образуют подобной шкалы и не могут сравниваться подобным образом.
Значение атрибута, являющееся шумом, может принадлежать или не принадлежать к области допустимых значений D(Aj) атрибута А}. В случае, если значение-шум принадлежит к области допустимых значений данного атрибута, набор правил, построенный по результатам обучения модели, будет оценивать значения других атрибутов объекта для обнаружения не согласующегося значения, идентифицируемого как шум. В том случае, если значение-шум не принадлежит к области допустимых значений, для идентификации шума не требуется оценивать значения других атрибутов.
Необходимо учитывать ситуацию, когда область допустимых значений D(Aj) атрибута Aj заранее неизвестна и может расширяться в процессе работы модели. Например, атрибут «Цвет автомобиля» в обучающей выборке принимает значения {Красный, Белый, Желтый}. Компания решает расширить выбор цветов автомобилей, после чего в базу данных начинают поступать заявки, значение атрибута «Цвет автомобиля» в которых отличается от начального множества, например {Черный}. В случае, если количество объектов с новым значением атрибута становится существенным, их уже нельзя рассматривать как шум. Таким образом, будем рассматривать ситуацию, когда область допустимых значений атрибута заранее неизвестна, и все новые значения атрибута расширяют ее.
Непрерывные значения атрибута можно рассматривать как дискретные в рамках обучающей выборки, поскольку количество значений конечно. С учетом допущения об исключительности значений аномалий в данных требование к вносимому значению заключается в его достаточной «отдаленности» от исходного значения.
Для генерации аномального значения числового атрибута будем пользоваться математическими средствами, такими как умножение или деление исходного значения на случайную константу.
Пусть PAN(AJ) вероятность искажения значения числового атрибута Aj, где j = 1, к- порядковый номер атрибута объекта. В дальнейшем для упрощения будем записывать PAN О- CAN - случайная величина в диапазоне CAN Є [0,1]. Cjj - некоторая случайная величина, диапазон значений которой может задаваться пользователем. По умолчанию примем Сц Є [0,1) U (1, оо).
Категориальные значения атрибутов выражаются текстовым описанием, поэтому для внесения аномальных значений в такие атрибуты необходимо использовать механизм искажения строковых значений. Также возможно изменение значения атрибута на одно из списка заранее определенных аномальных значений.
Пусть PAT(AJ) - вероятность искажения значения категориального атрибута Aj. В дальнейшем для упрощения будем записывать РдтО)- САТ - случайная величина в диапазоне САТ Є [0,1]. SAT = {a J z = l,m] - множество аномальных значений, на которые может быть заменено очередное значение а . CSAT Є [l,z] - некоторая случайная целая величина, определяющая конкретное выбираемое значение шума из множества SAT.
Так как атрибут Aj является категориальным, то есть представлен в виде слова, он может быть представлен как Aj = {а.га2 ... ап], где aj - i-ый символ слова, п -длина слова. Тогда процедура искажения значения атрибута Aj может быть выполнена перестановкой некоторых подмножеств множества символов слова. Вообще говоря, количество таких подмножеств может быть п, если каждое подмножество состоит из единственной буквы. Количество возможных перестановок в таком случае будет равно п!. В рамках данной работы с учетом относительно небольшого размера обучающего множества достаточно разбить слово ajj на два упорядоченных подмножества букв: а = {aia 2}, где а г = {ах ...ак}, а2 = {ак+1 ...ап}, к выбирается произвольно. В этом случае искаженное значение, полученное в результате перестановки: (а ) = {a ai}.
Шум был внесен в значения атрибута «Диаметр» во второй и восьмой строках. Внесем шум в категориальный атрибут AN = {Цвет}. Зададим уровень шума равным NN = 10%. Выполним алгоритм два раза. Первый раз укажем множество возможных значений шума SAT = [желтый, зеленый}, второй раз алгоритм запускается без указания множества SAT. В таблице 3 приведены промежуточные значения, генерируемые и вычисляемые в процессе работы алгоритма. Сведены данные после двух прогонов алгоритма.
Проблема выбора стратегии повышения достоверности обработки данных
Для выбора стратегии повышения качества данных при построении дерева решений будем использовать принципы, описанные в [30-31, 34]. Процесс повышения качества данных начинается с профилирования исходного обучающего множества. Профилирование проходит по двум фильтрам f: проверка на аномалии в значениях атрибутов объектов и проверка на отсутствие значений атрибутов объектов.
На рисунке 3.1 представлено преобразование данных в процессе профилирования.
На вход процессу профилирования подаются данные и метаданные [104]. В общем случае как первые, так и вторые могут быть как корректными, так и некорректными. В результате профилирования формируются корректные метаданные, а также классы профилирования. В нашем случае входными данными является обучающее множество S, а метаданными - множество классов К. На выходе в качестве данных выступает обучающее множество S, объекты которого подверглись процедурам повышения качества данных в соответствии с выбранной стратегией W. Выходными метаданными является система правил Р и решающая функция RpQ- Объекты обучающего множества будем называть информационными элементами системы.
В процессе профилирования фильтры f рассматриваются как отдельные бизнес-задачи, несущие в себе смысловую нагрузку. Тогда производительность системы с точки зрения качества информации можно определять по количеству решаемых бизнес-задач, то есть по количеству успешно обрабатываемых фильтров.
При анализе фильтра данные делятся на несколько классов профилирования. Под данными подразумеваются объекты множества X, а под классами множество Sr = {Sj1, ...,Sk }, где k 2. Часть полученных классов считается проблемными, в них попадают объекты, не удовлетворяющие набору условий фильтра. Классы, содержащие объекты, удовлетворяющие условиям фильтра, назовем успешными классами. Подобный подход позволяет оценивать данные по многим фильтрам, которые в свою очередь могут разбивать данные на два и более классов. В данной работе рассматриваются вопросы анализа данных на предмет аномалий и отсутствующих значений. Будут использоваться два типа фильтров: «аномалии в данных» и «отсутствие значений атрибутов». Поскольку искажения могут проявляться в разных атрибутах объектов, а для их устранения потребуется анализ значений соответствующих атрибутов остальных объектов, количество фильтров целесообразно выбрать равным количеству атрибутов объектов для каждого типа фильтров. Соответственно, каждый фильтр разделяет объекты по двум классам. То есть, если каждый объект Xi = {ai:L,ai2, — ,aik} содержит к атрибутов, тогда общее количество фильтров будет равно j = 2 k.
В процессе повышения качества данных объекты из проблемных классов должны переместиться в успешные классы. Таким образом все данные в результате анализа фильтра fj попадут в успешный класс. В этом случае можно считать фильтр успешно обработанным, а систему - корректно работающей в рамках соответствующей бизнес-задачи.
Вводится CF(Xi) - количество проблемных классов, в которые попал объект Х4 по результатам обработки всех фильтров.
Соответственно, CT(Xj) - количество успешных классов, содержащих объект Xi Тогда общее количество классов по всем фильтрам рассчитывается как сумма успешных и проблемных классов.
В результате процесса профилирования будут обрабатываться в первую очередь те проблемные классы, которые имеют минимальное количество объектов. Объекты в свою очередь распределяются внутри класса таким образом, что сначала идут объекты, попавшие в наименьшее количество f. классов. После выравнивания всех объектов в текущем проблемном классе SkJ фильтра fj получается ситуация, когда по фильтру fj не осталось проблемных классов, то есть фильтр обработан успешно.
Значение оператора Тг можно вычислить как вероятность события, при котором в і-ом обрабатываемом элементе присутствует минимальное количество ошибок по всем фильтрам. Иными словами Тг - это вероятность такого события, когда рассматриваемый элемент принадлежит классу CF в условиях фильтра fj и не принадлежит никаким другим классам CF в условиях множества других фильтров.
Таким образом, если элемент содержит ошибки по всем фильтрам, оператор Тг для него будет равен нулю, т.е. «вес» элемента будет считаться минимальным, а элемент - наименее полезным с точки зрения смысловой нагрузки ввиду максимальной искаженное. Напротив, если элемент содержит ошибку только по данному фильтру, тогда Тг сводится к показателю q(vj h) из [28].
Специфика работы автоматизированных систем обработки информации такова, что искажение отдельных элементов данных не останавливает работу системы в целом. Оценка достоверности данных проводится внутри процессов функционирования системы. При этом важно оценивать данные, полученные в процессе анализа, по уровню критичности искажений, а также по степени распространения однотипных искажений между различными информационными элементами.
Результаты проведения экспериментов
На первом этапе проводились эксперименты над различными наборами данных, не содержащих шум.
Как показали эксперименты [32], алгоритмы IDTUV и ШЗО выдают результат, аналогичный результатам алгоритмов ID3 и С4.5 в случаях, когда в наборе данных содержатся только категориальные или только числовые атрибуты соответственно. В среднем по всем наборам данных алгоритмы IDTUV и ГОЗО показали лучшие результаты по сравнению с ID3 и С4.5, что говорит о целесообразности совместного использования этих алгоритмов при построении дерева решений на данных, содержащих категориальные и числовые атрибуты одновременно.
На втором этапе в наборы данных вносился шум типов «отсутствие значений атрибутов» и «аномальные значения атрибутов». На втором этапе сравнивались результаты работы алгоритмов IDTUV и ID30, поскольку они обрабатывают и корректируют шум в данных.
По итогам второго этапа экспериментов стало ясно, что предложенный в данной работе алгоритм ID30 имеет высокую устойчивость к искажениям в данных благодаря механизмам поиска и устранения аномалий в данных, а также заполнения пропущенных значений атрибутов. Так, при уровне шума в 5% средний результат по всем наборам данных всего на 0,02% ниже результата при отсутствии шума. А при шуме в 10% и 20% снижение точности классификации составило в среднем 0,57% и 2,79% соответственно, что существенно меньше, чем снижение точности классификации других рассмотренных алгоритмов при аналогичных уровнях шума.
Таким образом, предложенный алгоритм ID30 показал способность к эффективной работе с данными, содержащими шум.
Разработанная система поддержки принятия управленческих решений была успешно внедрена в производственный процесс организации, занимающейся уборкой территорий средствами собственного специализированного автопарка, о чем свидетельствует акт о внедрении. Также по просьбе руководства система дополнительно была внедрена в тестовом режиме в партнерской организации, предоставляющей услуги аренды коммерческой недвижимости.
Система показала свою эффективность при использовании в таких разных сферах, как уборка территорий и аренда недвижимости, что подтверждает фундаментальный характер исследования. Построенная прогнозная модель решающего дерева позволила эффективно вести анализ данных с учетом возможного появления аномалий и принимать управленческие решения.
В таблице 20 показаны практические результаты от внедрения системы в производственный процесс предприятия по уборке территорий.
Похожие диссертации на Автоматизация процессов повышения достоверности обработки информации и принятия решений в контуре систем диспетчерского управления
