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

На правах рукописи

Орлов Антон Олегович

АВТОМАТИЗАЦИЯ ПРОЦЕССОВ ПОВЫШЕНИЯ ДОСТОВЕРНОСТИ ОБРАБОТКИ ИНФОРМАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ В КОНТУРЕ СИСТЕМ ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ

Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность)

005533296 /

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

19 СЕН 2013

Москва-2013

005533296

Работа выполнена на кафедре автоматизированных систем обработки информации и управления в Московском государственном техническом университете имени Н. Э. Баумана.

Научный руководитель: Кузовлев Вячеслав Иванович

кандидат технических наук, доцент кафедры «Системы обработки информации и управления» МГТУ им. Н. Э. Баумана, г. Москва

Официальные оппоненты:

Юрчик Петр Францевич

доктор технических наук, профессор

кафедры АСУ МАДИ, г. Москва

Максаков Алексей Александрович кандидат технических наук, главный специалист отдела разработки и управления информационными

технологиями НПФ «Телеком-Союз», г. Москва

Ведущая организация:

ОАО «НИИ Систем автоматизации», г. Москва

Защита диссертации состоится «09» октября 2013 года в 10 ч. 00 мин. на заседании диссертационного совета Д 212.126.05 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский автомобильно-дорожный государственный технический университет (МАДИ)» по адресу: 125319, г. Москва, Ленинградский проспект, д.64.

С диссертацией можно ознакомиться в библиотеке МАДИ.

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

Автореферат разослан 6 сентября 2013 г.

Ученый секретарь // / I/

диссертационного совета, Михайлова Н. В.

кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Предмет исследования. В данной работе исследуются прогностические модели, основанные на классификационных моделях решающих деревьев. В этой области весьма существенными являются работы многих российских и зарубежных авторов, таких как В. Н. Вагин, Д. А. Поспелов, Дж. Куинлан, П. Утгофф, М. Брюниг и другие, В области анализа и разработки управленческих решений важны работы Б. Г. Литвака, в области анализа качества данных -работы Р. Вонга, Дж. Олсона, К. Батини. Разработанные механизмы позволяют эффективно строить модели деревьев решений по наборам исходных данных. Крайне важным моментом при построении моделей является качество исходных данных обучающего множества, поскольку от него фактически зависит результат анализа новых данных.

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

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

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

3. Устранение шума в данных на основе анализа данных, не содержащих шум;

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

Научная новизна исследования.

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

Разработан алгоритм расчета степени аномальности значений атрибутов объектов данных на основе предложенной новой формулы расчета расстояний между этими значениями.

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

Создана методика выбора стратегии повышения качества входных данных.

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

Методика проведения исследований. Для достижения целей работы использовались методы теории вероятностей, математической статистики, теории машинного обучения, теории информации. Для разработки программной системы применялись современные технологии создания веб-приложений (JavaScript, РНР5) и визуализации (SVG). В процессе исследования использовались результаты современных трудов российских и иностранных авторов.

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

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

Апробация работы. Основные положения и научные результаты диссертационной работы докладывались:

- на научных семинарах кафедры ИУ-5 МГТУ им. Баумана;

- на XIII Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы — 2011»;

- на XIV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2012»;

- на XV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2013».

Публикации. Материалы по теме исследования опубликованы в 7 печатных работах.

Объем работы. Диссертационная работа содержит 186 страниц, 21 рисунок и 20 таблиц, 1 копия акта о внедрении, список литературы из 122 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений.

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

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

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

- подготовка данных;

- построение и оценка модели;

- применение модели.

Процесс принятия управленческого решения

Бизнес процессы

ж

Процессы в СППР

Анализ проблемы Формулирование целей и задач

N

Определение критериев оценки альтернатив

±

Определение зависимых и независимых переменных

Определение классов зависимых переменных

БД

Построение множеств значений независимых переменных

Попадание шума в множества значений переменных.

Появление искажений в критериях оценки _альтернатив_

Формирование альтернатив

Анализ альтернатив

Построение прогнозной модели

Анализ

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

Формирование организационных воздействий , і /1 ► Выпуск решения

' і '

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

Интерфейс

Рисунок 1. Процесс принятия управленческого решения

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

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

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

Модели данных делятся на несколько основных типов: классификационные, регрессионные, модели кластеризации.

Классификационные модели позволяют отнести элементы данных к определенным заранее известным классам. Таким образом, классификационные

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

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

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

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

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

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

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

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

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

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

Алгоритм внесения выбросов в значения числового атрибута Вход: множество объектов X = {ХцХг, ...,ХП} без шума в данных; множество значений атрибутов объектов А = {а^ 11 = 1, п; ] = 1, к}; числовой атрибут, подлежащий искажению Ам £ А; уровень шума

Выход: обучающее множество с выбросами 5 = {Х| 11 = 1, п}, где Х[ = {ац,щ2, ...,аКр_1)>а;р,а1(р+1), ...,а,к}, а-р - атрибут с шумом. Начало алгоритма.

Шаг 1. Принять ] - индекс атрибута Ам. Принять РАМ0) =

Шаг 2. Начало цикла по А). Выбрать следующий элемент а^ под индексом 1 из

столбца ].

Шаг 2.1. Сгенерировать случайное число САМ 6 [0,1]. Если САЫ < РЛмШ, тогда положить П(9 = 1 и перейти к шагу 2.2, иначе положить а) а^ = а^; б) ПО) = 0 и перейти к шагу 2.3.

Шаг 2.2. Сгенерировать случайное число С £ [0,1) и (1, оо). Положить _а'ц = ац ' С. _

Шаг 2.3. Положить а^ = {а^'.ПО)}. Шаг 3. Конец цикла по А).

Конец алгоритма._

Алгоритм внесения выбросов в значения категориального атрибута Вход: множество объектов X = {Х^Хг,...,ХП} без шума в данных; множество значений атрибутов объектов А = {а^ 11 = 1, п^ = 1, к}; категориальный атрибут, подлежащий искажению Аы 6 А; множество возможных значений шумов для категориального атрибута Бдт = | г = 1, ш}; уровень шума Выход: обучающее множество с выбросами 5 = {Х| 11 = 1, п}, где Х[ = {аи<а12' — <аЦр-1>а1р>аКр+1)< ■••/а[р - атрибуте шумом. Начало алгоритма.

Шаг 1. Принять] - индекс атрибута Ам. Принять РдтО) = N7.

Шаг 2. Начало цикла по А). Выбрать следующий элемент а;) под индексом I из

столбца

Шаг 2.1. Сгенерировать-случайное число САТ £ [0,1]. Если САТ < РдтО), тогда положить П(]) = 1 и перейти к шагу 2.2, иначе положить а) а|| = ац; б) ПО) = 0 и перейти к шагу 2.5.

Шаг 2.2. Если множество 5ДТ = {А^ | г = 1, ш} непустое мощности ш, тогда сгенерировать случайное целое число СЗАТ С [1, ш] и перейти к шагу 2.3, иначе перейти к шагу 2.4.

Шаг 2.3. Положить а|- = где aJ - случайным образом выбранный элемент множества 5ДТ. Перейти к шагу 2.5.

Шаг 2.4. Разбить слово а^ = {а1а2 ...ап} случайным образом на два подмножества, выполнить перестановку подмножеств. Положить а|] = {а'га'х}, где а'г и а'2 - подмножества исходного слова а^. Шаг 2.5. Положить а^ = {а||, ПО)}. Шаг 3. Конец цикла по А).

Конец алгоритма._

Алгоритм внесения пустых значений атрибута

Вход: множество объектов X = {Х1(Х2> ...,ХП} без шума в данных; множество значений атрибутов объектов А = {а^ 11 = 1, п; ] = 1, к}; атрибут, подлежащий искажению 6 А; уровень шума N.

Выход: обучающее множество с пустыми значениями Б = {Х{ 11 = 1, п}, где

X,' = {ал, а,2, .••,акр-1>а;р,аКр+1).....а1к}, а\р - атрибут с шумом.

Начало алгоритма.

Шаг 1. Принять] - индекс атрибута Ам. Принять РмО) = N.

Шаг 2. Начало цикла по А,-. Выбрать следующий элемент ац под индексом 1 из

столбца)._

Шаг 2.1. Сгенерировать случайное число CN Е [0,1]. Если CN < PN(j), тогда положить f!(j) = 1 и перейти к шагу 2.2, иначе положить a) ajf = а^; б) fl(j) = 0 и перейти к шагу 2.3. Шаг 2.2. Положить ajj = null. Шаг 2.3. Положить а'ц = {a^flQ)}. Шаг 3. Конец цикла по Aj.

Конец алгоритма._

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

сч

о,

■В ."1

Рисунок 2. Механизм LOF. Случай областей с разной плотностью

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

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

Метод LOF работает следующим образом. Для рассматриваемого объекта (точки) определяются расстояния достижимости объектов в к-окрестности данной точки, где к - количество объектов, попадающих в окрестность.

Пусть D - множество всех объектов, тогда для любого объекта р 6 D расстояние до k-го из ближайших объектов задается формулой:

Dk(p) = d(p,o), (1)

где d(p, о) - расстояние между объектом р и объектом о £ D таким, что:

а) существует хотя бы к объектов о' Е D\{p}, для которых выполняется d(p,o')<d(p,o);

б) существует не более (к — 1) объектов о' Е D\{p), для которых выполняется d(p, о') < d(p, о).

К-окрестностью Nk(p) объекта р £ D называется область, содержащая любой объект q, расстояние от р до которого не больше Dk(p). То есть

Ык(р) = {Ч е 0\{р} | с1(р, я) < Рк(р) }. (2)

Объекты из Мк(р) называются к ближайшими соседями для р. Стоит заметить, что количество объектов в 1Чк(р) может быть больше к, то есть |Мк(р)| > к. Расстоянием достижимости объекта р из объекта о называется расстояние от объекта о до к-го ближайшего объекта, если р принадлежит -окрестности объекта о. В противном случае расстоянием достижимости является непосредственное расстояние между о и р.

рк(о) — если р £ Мк(о),

с!(р, о) — иначе. (3)

RD,

сСр. О) = {Е

С учетом определения расстояния до к-го из ближайших объектов расстояние достижимости можно переписать в более компактном виде:

1Шк(р, о) = шах{Ок(о), сі(р, о)}. ^

\

/ Щ \ RDk(p1,o) = Dk(o)

ф , RDk(p2.o) = d(p2,o)

Рисунок 3. Расстояние достижимости в k-окрестности точки и вне ее

Локальная плотность Ird (local reachability density) в точке р определяется следующим образом:

. , , , , ;/SoeNu(p)RDk(p,o)

lrdk(p) = 1/(-Ш-(5)

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

С учетом вышесказанного показатель LOF аномальности объекта р вычисляется следующим образом (для упрощения опустим индекс к):

у 1гс1(о)

То есть степень аномальности объекта р определяется как среднее отношение локальных плотностей точек из к-окрестности точки р к локальной плотности в самой точке р.

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

Пусть имеется некоторый категориальный атрибут Ап, принимающий значения 0(АП) = {х^ ...,хр}. Тогда расстояние между значениями XI и X) О,] < р) при условии, что xi X), обозначается как (^^(х^) и вычисляется следующим образом:

N

ЪМ + «пОО

(7)

,где ^(х) равно количеству объектов, атрибут А; которых принимает значение х.

(1, если а» = х;

при А; =

С 0, иначе.

(8)

1=1

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

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

Показан выигрыш от использования предложенной формулы по сравнению с известными ранее подходами, заключающийся в том, что для работы не требуется вычислять мощность всего множества объектов, что ведет к существенному выигрышу в производительности в случае добавления новых объектов к исходному множеству X. При добавлении новых объектов изменятся расстояния только между теми значениями атрибутов, которые были добавлены. Поэтому пересчету при использовании сИ51:Ап(Х),Х)) подвергнется (р — 1) расстояний, в то время как при использовании существующих формул пересчитать необходимо будет расстояния между всеми атрибутами, таким

образом будет сделано пересчетов.

Рисунок 4. Дистанция между значениями категориального атрибута Обработка выбросов данных происходит в два этапа. На первом этапе выбросы в данных необходимо идентифицировать. Для идентификации аномалий применяется механизм LOF. Поскольку механизм LOF чувствителен к величине k-окрестности, необходимо ввести некоторые правила или рекомендации по выбору значения данного параметра. Для решения этой задачи разработана аналитическая модель оценки результатов метода LOF. Модель предназначена для интерпретации значений показателя LOF, а также гибкого выбора значения параметра к на основе субъективных ожиданий эксперта. Все объекты генеральной совокупности G имеют одинаковый набор атрибутов А = {А1; А2,..., Ап}. Каждый атрибут имеет некоторое количество уникальных значений D(Aj) = {xil,xi2, ...,xim}. В построенной модели объектами анализа являются значения отдельно взятого категориального атрибута. Формула (7) называется формулой инверсной гравитации. Если представить объекты анализа как сферические тела, то частота fn(x) появления значения х атрибута Ап среди объектов генеральной совокупности является массой сферы. Введем параметр р, характеризующий плотность объектов. Будем считать плотность всех объектов одинаковой. Тогда, изменяя р, можно регулировать объем тел и, соответственно, занимаемую ими площадь. Если пересечение объектов Xj, Xj в некотором пространстве W: Xj П Xj Ф 0, тогда Xj £ С и Xj £ С. Множество С всех объектов, имеющих пересечения,

называется ядром в пространстве W.

к к

с = {хх, Х2.....xk|(|JU (Xi п Xj)) ф 0}, (9)

i=i j=i

Если представить множество С на плоскости, то S(C) - есть площадь фигуры С. Работа построенной модели состоит из трех этапов. На первом этапе по формуле (7) рассчитываются расстояния между всеми объектами анализа. Также вычисляются показатели локальной аномальности LOF для каждого объекта. На втором этапе происходит автоматический анализ среднего

показателя LOF среди объектов ядра, а также отношения площади фигуры ядра к общей площади фигур объектов:

Параметр плотности объектов р уменьшается с заданным шагом, который автоматически корректируется по мере продвижения процесса анализа. При уменьшении плотности площадь объектов увеличивается, новые объекты попадают в пересечения, становясь частью ядра. Снова рассчитывается средний показатель LOF по формуле (10) и отношение площадей по формуле (11). Плотность р уменьшается до тех пор, пока все объекты не попадут в ядро, то есть станет справедливо равенство Srei = 1.

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

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

при помощи метода ближайших соседей._.

Алгоритм обработки выбросов в данных (А2.1)

Вход: множество объектов X = {Х1(Х2> — #ХП}, содержащих выбросы в данных; атрибут Aj,j = 1, к, по которому проводится проверка; параметр MinPts, определяющий количество ближайших объектов проверки; параметр Restore = {0,1), определяющий действие над найденными аномалиями._

(10)

Srel " S(D(An))

S(C)

(И)

Выход: множество объектов, содержащих аномалии X' = {Х'1(...,X'm},m < п; множество весов значения атрибута Aj объектов с аномалиями V = {Vt,..., Vm}, причем Vi = {0,1}. Начало алгоритма.

Шаг 1. Положить X' = {0} пустое множество. Сформировать множество

значений атрибута D(Aj) = {а1( ...,ak}, 1 < к < п.

Шаг 2. Для каждого aj из D(Aj) вычислить LOFMinPts(ai).

Шаг 3. Вычислить LOF как среднее арифметическое полученных ранее

burMinPts (а,)-

Шаг 4. Добавить в X' объекты из X такие, что V Xz е X : LOFMinPts(Xz(Aj)) > LOF, где Xz(Aj) - значение атрибута Aj объекта Xz. Шаг 5. Если значение параметра Restore равно 1, значит значения шума подлежат корректировке. Перейти к шагу 6. Если значение Restore равно О, перейти к шагу 8.

Шаг 6. Положить значения атрибута Aj для всех объектов из X' равными пустому значению V Xz G X : Xz(Aj) = null.

Шаг 7. Положить веса V = 1 для всех объектов из X'. Перейти к шагу 9. Шаг 8. Положить веса V = 0 для всех объектов из X'. Шаг 9. Конец.

Конец алгоритма._

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

Для заполнения пропущенного значения атрибута некоторого объекта проводится поиск наиболее близких объектов, после чего пропущенное значение восстанавливается на основе значений найденных объектов. Для нахождения ближайших объектов необходимо ввести метрику, позволяющую рассчитывать расстояния между объектами. Если имеются два объекта Xi(Xj из множества объектов X, тогда расстояние между объектами определяется следующим образом:

к

p=i

где к - количество атрибутов объектов, d(Xjp<Xjp) - расстояние между значениями р-го атрибута объектов, V(-) — вес соответствующего значения атрибута объекта. V(xip) = 1 в том случае, если значение атрибута xip не помечено как аномальное, в противном случае V(xip) = 0.

Расстояние d(Xjp,Xjp) для непрерывных признаков определяется следующим образом:

d(x- х- ^ = |Xip~Xjpl

ul*ip'xjpj I- _ а . I' П31

ldpmax "pminl ylJ'

где |apmax — apmjn| - разница между максимальным и минимальным

значениями р-го атрибута среди всех объектов.

Если одно из значений непрерывного атрибута неизвестно (xjp = null), то

расстояние определяется по известному значению следующим образом:

,, ч _ max((xip — apmax).Cxip apmin)) d^xip,xjpj - ¡- — -: . il4->

ldpmax "pminl K '

Если оба значения неизвестны, расстояние максимально и равно единице d(xip,xjp) = 1.

Для дискретных атрибутов расстояние вычисляется при условии, что

Xip ^ Xjp.

d(xip,xip) = distAp(Xi,Xj) • V(xip) ■ V(Xjp). (15)

Если xip = xjp, тогда d(xip,xjp) = 0. Если одно из значений дискретных атрибутов неизвестно (Xj = null), тогда расстояние рассчитывается следующим образом:

d(xjp,xjp) = distAp(xi,xmaxp), (16)

где xmaxp- наиболее частое значение р-го атрибута, то есть fA(xmaxp) = max(fA(xz)),z = l,k, где k - количество различных значений атрибута Ар. Если оба значения дискретных атрибутов неизвестны, тогда d(xjp>xjp) = 1,5, что является округленным в большую сторону максимальным расстоянием.

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

h

х'. = У^

,Р lab' (17)

i=l

где h — количество наиболее близких объектов.

В случае качественного атрибута значение выбирается как наиболее часто встречающееся среди соответствующих значений атрибутов наиболее близких

объектов._

Алгоритм заполнения пропусков в данных (А2.2)

Вход: множество объектов X = {Х1,Х2. — <ХП}, содержащих пустые значения и выбросы в данных; множество объектов, содержащих аномалии X' = {Х'1(..., Х'т}, т < п; множество весов значения атрибута А) объектов с аномалиями V = {У1(..., Ут}, причем V; = {0,1}; параметр К, определяющий количество искомых ближайших объектов.

Выход: множество объектов X" = {Х"1(Х"2, ...,Х"П}, не содержащих пустых значений атрибутов. Начало алгоритма.

Шаг 1. Начало цикла по X. Выбрать следующий объект X; е X.

Шаг 2. Если Х1 не содержит пустых значений атрибутов, то добавить этот

объект в выходное множество X" = X" и {Х1} и перейти к шагу 1. Иначе

перейти к шагу 3.

Шаг 3. Сформировать множество

0(Х0 = {0(Х„ХД..., ОСХ^.Д 0(Х„Х1+1),..., 0(Х,,Хп)} расстояний от объекта Х| до остальных объектов из X.

Шаг 4. Из множества Э(Х|) выбрать К наиболее близких объектов к Х1 и сформировать из них множество = {Х^, ...,Хкк}.

Шаг 5. Заполнить пустые значения атрибутов объекта X; на основании значений атрибутов объектов из Ок.

Шаг 6. Добавить объект в выходное множество X" = X" и {Х[}. Шаг 7. Конец цикла по X.

Конец алгоритма._

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

Б = {Х1,Х2, ...,ХП}

Каждый объект имеет набор атрибутов:

= {ац, а12,

Все объекты делятся на два непересекающихся класса: примеры и контрпримеры.

К = К+ и К"

Необходимо построить дерево решений и систему правил Р = {Pi,...,Pm}> где каждое правило Pj € Р отображает отдельный путь от корня к листу дерева решений. Также необходимо сформировать функцию Rp(0 такую, что для любого объекта X' функция Rp(X') на основе системы правил Р определяется следующим образом:

р fYiN _ il, если X' е К+;

Кр(-Л;~10,еслиХ'еК-. (18)

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

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

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

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

Шаг 4. Шаги 2-3 повторяются несколько раз для разных значений параметра к в диапазоне [1, р —1], где р - количество уникальных значений рассматриваемого категориального атрибута. Таким образом, будет получен набор графиков зависимости среднего LOF ядра от его относительной площади. Шаг 5. В зависимости от требуемой априори «жесткости» анализа выбрать значение параметра к, исходя из тех соображений, что чем выше значение к, тем более «мягким» будет анализ, то есть меньшее количество значений категориального атрибута будут идентифицированы как выбросы.

Шаг 6. В графике, соответствующем выбранному значению параметра к,

определить точку X начала роста функции.

Шаг 7. Выбросами считать точки, не вошедшие в ядро в точке X.

Решается проблема выбора оптимальной стратегии повышения качества данных в условиях ограниченности ресурсов. Описывается процесс профилирования исходных данных. Профилирование проходит по двум фильтрам f: проверка на аномалии в значениях атрибутов объектов и проверка на отсутствие значений атрибутов объектов. В процессе профилирования фильтры f рассматриваются как отдельные бизнес-задачи, несущие в себе смысловую нагрузку. Тогда производительность системы с точки зрения качества информации можно определять по количеству решаемых бизнес-задач, то есть по количеству успешно обрабатываемых фильтров. При анализе фильтра данные делятся на несколько классов профилирования. Под данными подразумеваются объекты множества X, а под классами — множество Sfi = {sj1, где k > 2. Часть полученных классов считается проблемными, в

них попадают объекты, не удовлетворяющие набору условий фильтра. Классы, содержащие объекты, удовлетворяющие условиям фильтра, назовем успешными классами. Подобный подход позволяет оценивать данные по многим фильтрам, которые в свою очередь могут разбивать данные на два и более классов. Предложен новый показатель оценки качества данных Тг. Значение оператора Тг можно вычислить как вероятность события, при котором в i-ом обрабатываемом элементе присутствует минимальное количество ошибок по всем фильтрам. Иными словами Тг - это вероятность такого события, когда рассматриваемый элемент принадлежит проблемному классу в условиях фильтра fj и не принадлежит никаким другим проблемным классам в условиях множества других фильтров. Tr=q(vi.h)-(l-q(Li/vi,h))

= [1- П (1 - Чи)] • [1 - (1 - YI (1"Чи)] =

Ii,z 6 vi,h li,z е Li/vi,h ^jj-j

= П (i-qu)-П(1_qiz)-

li,z 6 Li/vi,h Ii,z 6Li

Проведен сравнительный анализ предложенного оператора с показателем q(vi h), характеризующим вероятность появления ошибки h-ro класса

искажений в i-ом элементе. q(v№) = 1 - FlzeviCl ~ qi,z) = 1 _ FlzsviCl ~ где |z| - количество ошибок класса vh в информационных элементах, N — общее количество информационных элементов.

Предложен алгоритм выбора стратегии повышения качества данных в условиях ограниченности ресурсов.

Алгоритм выбора стратегии и восстановления данных (А3.1) Вход: обучающее множество объектов X = {Х1,Х2< ••■ Дп); стоимости уточнения данных С = {С1(С2, — .С^} по всем атрибутам из множества атрибутов объектов А = {А1,Аг,..., Ак}; максимальные затраты на повышение качества данных Стах.

Выход: множество объектов X" = {Х"1,Х"2, ...,Х"П}, не содержащих пустых значений в выбранных в соответствии со стратегией атрибутах. Начало алгоритма.

Шаг 1. Выполнить алгоритм обработки выбросов в данных А2.1. Шаг 2. Принять количество классов искажений равным количеству фильтров {, которое в свою очередь равно количеству атрибутов объектов к. V = {V!,..., у^}. Шаг 3. Рассчитать ТГ(У() для каждого класса искажений. Принять суммарные затраты равными нулю С5ШП = 0.

Шаг 4. Рассчитать вероятностный вес возникновения единственной ошибки для каждого класса искажений = ТГ(Ч^) • где У| = ^г - вес ошибки из

V,.

Шаг 5. Выбрать стратегию повышения качества данных \У(Тг(у)) = (шах(У(Тг(У1)))} среди всех классов искажений V. Прибавить затраты С| к суммарным затратам С5ит = С31дт + С(.

Шаг 6. Выполнить алгоритм заполнения пропусков в данных А2.2 для выбранных в соответствии со стратегией \/У(Тг(\>)) классов искажений. Шаг 7. Если суммарные затраты меньше установленного максимума С5ит < Стах, перейти к шагу 5. Иначе перейти к шагу 8. Шаг 8. Конец алгоритма.

Конец алгоритма._

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

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

1. Построение прогнозной модели дерева решений на основе анализа исходных данных, введенных пользователем;

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

3. Возможность поиска аномальных данных среди объектов исходных данных и ранжирования объектов по степени аномальности;

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

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

6. Классификация новых объектов данных с использованием построенной прогнозной модели дерева решений;

7. Возможность многократного использования построенной модели без необходимости повторного построения;

8. Возможность работы посредством сетевого доступа со стационарных или мобильных устройств.

Рисунок 5. Алгоритм ШЗО

Описывается процедура тестирования разработанной прогнозной модели.

Рисунок 6. Методика тестирования прогнозной модели

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

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

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

Таблица 1

Точность классификации на данных без шума. _

ID3 C4.5 IDTUV ID30

Autopark 23 67 67 67

ClientStat 20 65 65 65

Monks 94,4 90,3 94,4 94,4

Iris 0 92,7 92,7 92,7

Flags 47,8 73,9 69,6 69,6

StatlogHeart 0 77,3 83,3 83,3

Среднее 30,87% 77,70% 78,67% 78,67%

На втором этапе в наборы данных вносился шум типов «отсутствие значений атрибутов» и «аномальные значения атрибутов». На втором этапе сравнивались результаты работы алгоритмов ГОТОУ и ШЗО, поскольку они обрабатывают и корректируют шум в данных.

Таблица 2

Точность классификации на данных с шумом.

Шум 5%

IDTUV ID30

Autopark 65 67

ClientStat 64 65

Monks 93,6 94,4

Iris 90,3 92,7

Flags 68,5 69,6

StatlogHeart 77,7 83,2

Среднее 76,52% 78,65%

Шум 10%

IDTUV ID30

Autopark 62 66

ClientStat 62 65

Monks 92,8 94,1

Iris 88,8 92,6

Flags 66,3 69,1

StatlogHeart 76,3 81,8

Среднее 74,70% 78,10%

Шум 20%

IDTUV ID30

Autopark 59 63

ClientStat 61 64

Monks 90,7 92,8

Iris 87,9 92,2

Flags 64,2 65,2

StatlogHeart 74,2 78,1

Среднее 72,83% 75,88%

В заключении диссертационной работы приведены основные результаты, достигнутые в процессе исследования.

В приложении приведены наиболее значимые части кода реализованной программной системы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Исследованы принципы построения и функционирования систем поддержки принятия решений. Выделены особенности, характерные для систем поддержки принятия управленческих решений;

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

3. Исследовано влияние искажений (шума) в исходных данных на вид построенного дерева как результат работы модели. Рассмотрен шум двух типов: отсутствие значений атрибутов объектов данных и аномальные значения;

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

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

6. Разработаны модель и методика выбора параметров и интерпретации результатов анализа выбросов в категориальных атрибутах данных;

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

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

вероятности возникновения искажений по минимальному количеству фильтров;

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

10.Разработана программная система для анализа и повышения эффективности использования ресурсов автомобильного парка организации. Разработанная система внедрена в качестве модуля автоматизированной системы поддержки принятия решений в ООО «Компания РУС», о чем свидетельствует акт о внедрении.

Основное содержание диссертации отражено в 7 работах:

1. Кузовлев В. И., Орлов А. О. Прогнозный анализ данных методом ГОЗО // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон, журн. 2012. № 10. DOI: http://dx.doi.org/10.7463/1012.0483286

2. Кузовлев В. И., Орлов А. О. Метод выявления аномалий в исходных данных при построении прогнозной модели решающего дерева в системах поддержки принятия решений // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон, журн. 2012. № 09. DOI: http://dx.doi.org/10.7463/0912.0483269

3. Орлов А. О. Проблема поиска расстояний между значениями категориальных атрибутов при обнаружении выбросов в данных // В мире научных открытий. Красноярск, 2012. № 8.1. С. 142-155.

4. Кузовлев В. И., Орлов А. О. Учет взаимосвязей между объектами результатов профилирования // Инженерный вестник. МГТУ им. Н. Э. Баумана. Электрон. журн. 2012. № 08. URL. http://technomag.edu.ru/pdf7482766.html?_s=l

5. Кузовлев В. И., Орлов А. О. Вероятностный подход к оценке показателя достоверности элементов результатов профилирования // Вестник МГТУ им. Н. Э. Баумана. Сер. «Приборостроение». М„ 2012. № 4. 10 с.

6. Кузовлев В. И., Орлов А. О. Анализ взаимосвязей результатов профилирования // Сб. статей студентов и аспирантов каф. ИУ-5 МГТУ им. Н. Э. Баумана. М., 2012. 8 с.

7. Кузовлев В. И., Орлов А. О. Методика выбора параметров и интерпретации результатов анализа выбросов в данных систем поддержки принятия решений // Вестник МГТУ им. Баумана. Сер. «Приборостроение». № 3. М. 2013. 10 с.

Подписано в печать: 06.09.2013 Объем: 1,0 п.л. Тираж: 100 экз. Заказ № 129 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495)363-78-90; www.reglet.ru

Московский государственный технический университет имени Н. Э. Баумана

На правах рукописи

04201361744 Орлов Антон Олегович

АВТОМАТИЗАЦИЯ ПРОЦЕССОВ ПОВЫШЕНИЯ ДОСТОВЕРНОСТИ ОБРАБОТКИ ИНФОРМАЦИИ И ПРИНЯТИЯ РЕШЕНИЙ В КОНТУРЕ СИСТЕМ ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ

Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

кандидат технических наук, доцент Кузовлев Вячеслав Иванович

Москва-2013

СОДЕРЖАНИЕ

Стр.

Введение.......................................................................................................................5

Глава 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 Проблема выбора параметра МЫЧэ........................................................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 Использование алгоритмов повышения достоверности обработки данных при построении дерева решений........................................................................105

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

Введение

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

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

Предмет исследования. В данной работе исследуются прогнозные модели, основанные на классификационных моделях решающих деревьев. В этой области весьма существенными являются работы многих российских и зарубежных авторов, таких как В. Н. Вагин [5-9], Д. А. Поспелов [51], Дж. Куинлан [105-106], П. Утгофф [112], М. Брюниг [74] и другие. В области анализа и разработки управленческих решений важны работы Б. Г. Литвака [38], в области анализа качества данных - работы Р. Вонга [117-119], Дж. Олсона [104], К. Батини [71]. Разработанные механизмы позволяют эффективно строить модели деревьев решений по наборам исходных данных. Крайне важным моментом при построении моделей является качество исходных

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

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

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

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

3. Устранение шума в данных на основе анализа данных, не содержащих шум;

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

Научная новизна исследования.

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

Разработан алгоритм расчета степени аномальности значений атрибутов объектов данных на основе предложенной новой формулы расчета расстояний между этими значениями.

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

Создана методика выбора стратегии повышения качества входных данных.

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

Методика проведения исследований. Для достижения целей работы использовались методы теории вероятностей, математической статистики, теории машинного обучения, теории информации. Для разработки программной системы применялись современные технологии создания веб-приложений (JavaScript, РНР5) и визуализации (SVG). В процессе исследования использовались результаты современных трудов российских и иностранных авторов.

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

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

Апробация работы. Основные положения и научные результаты диссертационной работы докладывались:

- на научных семинарах кафедры ИУ-5 МГТУ им. Баумана;

- на XIII Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2011»;

- на XIV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2012»;

- на XV Молодежной международной научно-технической конференции учащихся, студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы - 2013».

Материалы по теме исследования опубликованы в 7 печатных работах.

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

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

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

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

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

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

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

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

В приложении приведены наиболее значимые части кода реализованной программной системы.

и

Глава 1. Анализ методов оценки достоверности обработки информации в автоматизированных системах

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

1.1 Анализ характеристик качества данных

Информационные системы на всех этапах своей работы оперируют данными. Данные делятся на входные, внутренние и выходные.

Рисунок 1.1. Обобщенная технология обработки информации в автоматизированных информационных системах

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

1.1.1 Общие характеристики качества данных

Понятие качества данных включает себя ряд основных характеристик. Характеристики качества данных подробно описываются и обсуждаются в ряде работ [71, 104, 113-116]. В разных работах предлагаются разные классификации характеристик качества данных, однако большинство авторов сходятся в выделении основных характеристик качества данных:

- точность;

- полнота;

- актуальность;

- непротиворечивость.

Точность

Под точностью понимается близость между значениями V и У\ где V" - объект реального мира, а V - объект информационной системы, отображающий объект V" [71]. Вообще говоря, объект реального мира V" может являться произвольной сущностью, а объект V в свою очередь может содержать как структурированную, так и неструктурированную информацию. К примеру, объект информационной системы может быть текстом, изображением, видео или аудио файлом. Он может соответствовать какому-либо формату данных или же быть просто массивом данных. Вопросы анализа неструктурированной информации я�