close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
Воронин Дмитрий Александрович
Метод, алгоритм и структурно-функциональная организация системы
поддержки принятия управленческих решений в трейдинговых компаниях на
основе секвенциального анализа
Специальность: 05.13.10 – Управление в социальных и экономических
системах
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
Курск 2013
Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Юго-Западный государственный университет»
Научный руководитель
доктор технических наук, профессор
Атакищев Олег Игоревич
Официальные оппоненты
Сизов Александр Семенович
доктор
технических
наук,
профессор,
заслуженный
деятель
науки
Российской
Федерации,
Научно-исследовательский центр (г. Курск)
ФГУП
«18
ЦНИИ»
МО
РФ,
главный научный сотрудник
Власенко Александра Владимировна
кандидат
технических
наук,
доцент,
Кубанский
государственный
технологический университет ФГБОУ ВПО
«КубГТУ», начальник управления аспирантуры
и докторантуры
Ведущая организация
ФГБОУ ВПО «Госуниверситет — УНПК»
(г. Орѐл)
Защита состоится «29» марта 2013 г. в 1400 часов на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: г.
Курск, ул. 50 лет Октября, 94 (конференц-зал).
С диссертацией можно ознакомиться в библиотеке университета.
Автореферат разослан «28» февраля 2013 г.
Ученый секретарь
диссертационного совета
Д 212.105.02
Титенко Евгений Анатольевич
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Развитие биржевой деятельности в России привело к появлению нового класса экономических систем – трейдинговых (торговых) компаний, ведущих операционную деятельность на валютных, сырьевых рынках и рынке ценных бумаг, а
также инвестирующие частных трейдеров (участников электронных торгов). Автоматизация электронной коммерции в совокупности с увеличением объемов торговых операций
привели к существенному увеличению количества сделок, возрастанию конкуренции и
возникновению большого количества данных, подлежащих анализу для принятия актуальных и обоснованных решений о покупке или продаже. Множество сделок, значительный объем обрабатываемых данных, временная и содержательная вариативность выделения существенных элементов экономических данных, быстрые изменения курсов, влияние
новостей в реальном времени на принятие решений по сделкам, в целом, порождают многомерные массивы данных, повышают неопределенность принятия решений. Комбинация
поисково-переборных и оптимизационных этапов в процессе анализа рыночной ситуации
и генерации управленческих решений создают большое количество возможных альтернатив развития ситуации, что требует применения аппаратно-программных систем поддержки принятия решений (СППР).
Среди различных моделей и методов прогнозирования развития экономической ситуации существенную роль играют методы интеллектуального анализа данных (ИАД, Data
Mining) для поиска скрытых закономерностей в неструктурированных данных. В номенклатуре методов Data Mining, подходящих для выявления скрытых закономерностей изменения экономической ситуации, метод секвенциального анализа является базовым для нахождения содержательно-временных повторений (шаблонов) в последовательностях событий, описываемых набором экономических показателей об электронных торгах. В традиционной постановке задача секвенциального анализа рассматривается как однократная
обработка единственного набора экономических параметров с последующей генерацией
одного набора шаблонов, используемых для управленческих решений. Вместе с тем характерные для систем электронных торгов большие объемы анализируемых данных, недетерминированный характер задачи выбора торговой стратегии приводят к тому, что необходимы повторные, снижающие актуальность принимаемых решений итерации обработки
данных в СППР с новыми параметрами поиска, приводящие в конечном итоге к получению множества решений не для одного параметра, а для интервала, задаваемого лицом,
принимающим решение (ЛПР).
Модели управления организациями и управление рисками рассматривались в работах Д.А. Новикова, С.А. Баркалова, В.Н. Буркова и др. Методы управления и принятия
решений рассматривались в работах А.Г. Чхартишвили, О.И. Ларичева и др. Теоретические и практические вопросы анализа, создания и использования СППР были рассмотрены
такими учеными, как Э.А. Трахтенгерц, В.А. Геловани, А.А. Башлыков, И.У. Ямалов, О.
М. Проталинский и др. Исследования методов Data Mining проводились в работах Р. Агравала, Р. Срикната, А.А. Багресяна, М.С. Куприянова, В.В. Степаненко, И.И. Холода и др.
Вместе с тем, вопросы генерации множества альтернатив в условиях интервального задания параметров нашли лишь частичное отражение в известных работах. Для выполнения
анализа данных и последующего принятия решений в трейдинговой деятельности созданы
пакеты прикладных программ: MetaTrader, Elwave, MetaStock. Для этих программных пакетов характерны слабые возможности анализа по интервалам входных параметров, огра3
ниченное количество генерируемых вариантов развития ситуации или недостаточно количество анализируемых макроэкономических факторов.
Объективные требования по обработке множества показателей (абсолютные и относительные значения изменений курсов, изменения макроэкономических показателей, изменения фондовых индексов и объемов торгов) приводят к необходимости выполнения
многократных итераций, на которых выполняется генерация и выбор альтернатив, что
требует избыточных временных затрат и вступает в противоречие с необходимостью оперативной поддержки управленческих решений в процессе трейдинговой деятельности.
Целью работы является повышение оперативности генерации альтернатив для
управленческих решений в условиях обработки больших массивов экономических данных, а также повышение обоснованности генерируемых альтернатив для управленческих
решений.
Научной задачей является разработка метода и алгоритма поддержки принятия
решений, обеспечивающего поиск скрытых закономерностей в экономических данных с
возможностью интервального задания параметров.
Объектом исследования являются процессы и информационные технологии
управления торговыми операциями в трейдинговых компаниях.
Предметом исследования являются методы и алгоритмы управления электронными торгами в трейдинговой компании и структурно-функциональная организация СППР
по торговым операциям для трейдинговой компании.
Задачи исследования. Достижение поставленной цели исследования обуславливает
необходимость решения следующих частных задач:
1.
Анализ современных инструментальных средств поддержки принятия решений для управления торговыми операциями в процессе трейдинговой деятельности. Обоснование направления диссертационных исследований.
2.
Разработка метода поддержки принятия решений на основе секвенциального
анализа, алгоритмизация метода с учетом специфики создания СППР для трейдинговых
компаний.
3.
Разработка структурно-функциональной организации системы поддержки
принятия решений, поддерживающей разработанный метод, а также важнейших блоков
обработки множеств и кортежей, составленных из экономических данных.
4.
Экспериментальная проверка разработанных метода и алгоритмов поддержки
принятия решений.
Методы исследования основываются на положениях теорий: управления в организационно-технических системах, принятия решений, теории систем, теории сложности,
а также методах интеллектуального анализа данных, математической статистики, комбинаторики, квалиметрии.
Достоверность и обоснованность результатов исследования подтверждается: соответствием практических результатов и оценок моделирования, программными экспериментами по применению разработанного метода поддержки принятия решений (ППР) к
данным о значениях курсов валют и акций; корректным использованием законов и положений теории множеств и положений конструктивной математики; рецензированием печатных работ, их обсуждением на научно-технических конференциях, семинарах кафедры
ПОВТ, а также патентной экспертизой разработанного устройства определения префиксно-суффиксных свойств последовательностей.
4
Положения, выносимые на защиту, и их научная новизна.
1.
Метод поддержки принятия решений, базирующийся на методе секвенциального анализа AprioriAll, обеспечивающий генерацию альтернатив для принятия решений в
условиях интервального задания параметров при поиске скрытых закономерностей в экономических данных. Существенными отличиями метода являются:
- наличие этапа ранжирования последовательных шаблонов, выполняющего отбор
приоритетных альтернатив для управленческих решений;
- использование различных пороговых значений для обработки множеств и кортежей
на различных этапах метода.
2.
Алгоритм поддержки принятия решений, основанный на разработанном методе. Отличиями алгоритма являются:
- сохранение промежуточных результатов обработки данных для оперативной актуализации результатов анализа и повторного использования промежуточных результатов
при многократном анализе исходных данных;
- представление промежуточных данных в виде деревьев, позволяющее сократить
время генерации альтернатив для управленческих решений в случае интервального задания параметров;
- использование параметра достоверности при ранжировании управленческих альтернатив, что упорядочив ает работу ЛПР в условиях неопределенности данных.
3.
Структурно-функциональная организация системы поддержки принятия решений для управления торговыми операциями в трейдинговых компаниях, отличающаяся
наличием:
- модуля актуализации промежуточных результатов анализа;
- информационных связей, позволяющих ЛПР задавать параметры анализа в виде интервалов значений;
- хранилища промежуточных результатов анализа, позволяющего обращаться к
структурированным промежуточным данным без избыточных временных затрат на повторную генерацию в случае многократных запусков алгоритма поддержки принятия решений;
- модуля максимизации последовательностей с аппаратной реализацией операции определения суффиксно-префиксных свойств.
Предложенная структурно-функциональная организация СППР позволяет раздельно настраивать пороговые количественные характеристики образующих результат множеств и кортежей, что обеспечивает доступ к бóльшему количеству наборов данных, необходимых для принятия решений. Структура СППР спроектирована с учетом возможных
итераций уточнения результатов с новыми значениями параметров анализа.
Практическая значимость работы.
1.
Разработаны метод и алгоритм поддержки принятия решений, позволяющие
выполнять поиск скрытых закономерностей в экономических данных с интервальным заданием параметров, и на основе обнаруженных закономерностей осуществлять генерацию
альтернатив для управленческих решений. Использование в алгоритме представления
данных в виде дерева позволило уменьшить временную сложность интервального анализа
благодаря исключению процедур генерации потенциально частых последовательностей и
поиска генерируемых последовательностей в базе транзакций. Разработанный алгоритм
позволяет ЛПР осуществлять интервальный анализ и генерацию альтернатив, а также по5
вышает достоверность генерируемых приоритетных альтернатив для управленческих решений благодаря использованию расширенного перечня параметров для ранжирования.
2.
На основе синтезированной структурно-функциональной организации СППР,
применяемой в управлении торговыми операциями трейдинговой компании, созданы программные модули выявления скрытых закономерностей в данных в виде последовательных шаблонов, интегрированные в существующие СППР и хранилища данных. Программные модули выполняют обработку ретроспективных данных об изменении курсовых значений на биржевых рынках, генерируют наборы последовательных шаблонов и
формируют альтернативы для управленческих решений для ЛПР в текущей ситуации, основываясь на количественных показателях и возможном финансовом результате от трейдинговой деятельности.
3.
Алгоритмизация разработанного метода поддержки принятия решений позволила создать программные модули, отличающиеся вложенными структурами представления и унификацией алгоритмов обработки экономических данных. Реализация модулей СППР позволила сократить время генерации последовательных шаблонов в среднем на 18,3% в случае заданий на анализ с интервалом параметров. Использование дополнительных параметров для ранжирования альтернатив повысило достоверность принимаемых решений на 7,3%.
4.
Разработано специализированное устройство параллельной обработки префиксно-суффиксных свойств последовательностей, которое позволяет сократить время
выполнения отдельных этапов обработки кортежей, составленных из наборов экономических данных. Устройство отличается параллельной обработкой всех диагоналей матрицы
совпадений, что позволяет уменьшить временные затраты на генерацию альтернатив для
управленческих решений; также возможно применение устройства в автономных системах электронных торгов, ориентированных на высокочастотный трейдинг. Разработанное
устройство имеет самостоятельную ценность для систем обработки символьной информации в рамках продукционной парадигмы.
Апробация работы. Основные научные результаты, полученные в диссертационной работе, докладывались и обсуждались на следующих конференциях: IX международная научно-техническая конференция «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г.
Курск, 2010 г.), IV Всероссийская научно-практическая конференция с международным
участием «Научное творчество XXI века» (г. Красноярск, 2011 г.), Всероссийская конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве НТ-2011» (г. Воронеж, 2011 г.), I региональная научно-практическая конференция «Информационные системы и технологии» (г. Курск, 2012 г.).
Реализация результатов работы. Основные результаты диссертационного исследования используются в процессе поддержки управленческой деятельности ЗАО "Финансовая компания "Жигули", г. Самара. Выполнено внедрение результатов научной работы в
учебный процесс кафедры программного обеспечения вычислительной техники ФГБОУ
ВПО «Юго-Западный государственный университет» при проведении занятий дисциплины «Теория принятия решений». Также результаты работы были внедрены в деятельность
компании по разработке программного обеспечения и интеллектуальных систем ЗАО
«Эврика». Результаты работы частично реализованы в рамках ФЦП "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса
России на 2007-2013 годы" по ГК 11.519.11.6004 от 18.08.2011 г., в НИР "Исследование и
6
разработка программного обеспечения понимания неструктурированной текстовой информации на русском и английском языках на базе создания методов компьютерного полного лингвистического анализа» ГК 07.514.11.4135, а также в НИР "Разработка методов и
алгоритмов систем поддержки принятия решений в научно-технической сфере на основе
визуального анализа многомерных слабоструктурированных данных и показателей" ГК
14.514.11.4039.
Соответствие паспорту специальности. Согласно паспорту специальности
05.13.10 – Управление в социальных и экономических системах, проблематика, рассмотренная в диссертации, соответствует пунктам 5 и 10 паспорта специальности (5 - Разработка специального математического и программного обеспечения систем управления и
принятия решений в социальных и экономических системах; 10 - Разработка методов и алгоритмов интеллектуальной поддержки принятия управленческих решений в экономических и социальных системах).
Публикации. По теме диссертационного исследования опубликовано 11 научных
работ, из них 6 статей – в изданиях, входящих в перечень ведущих рецензируемых научных журналов и изданий, рекомендуемых ВАК, и патент РФ № 2430408 на изобретение.
Личный вклад автора. Все выносимые на защиту научные результаты получены
соискателем лично. В работах, опубликованных в соавторстве, лично соискателем в [1]
предложена структура альтернатив и продукционных выражений для управленческих решений, в [4] предложено использование направленного дерева последовательностей для
хранения промежуточных результатов; в [5] предложено использование управляющей информации для стратегий обработки потока данных в транзакционных трейдинговых системах; в [6] предложено использование модуля локальных управляющих сигналов о готовности результата при поиске оптимальных управленческих решений; в [7] предложен
модифицированный способ поиска объектов в базе транзакций с использованием дополнительной информации об отказах; в [9] предложена модификация структуры базы событий путем введения дополнительного упорядочения структурных элементов; в [11] предложена модификация матрицы совпадений элементов последовательностей, обеспечивающая нахождение позиций пересечений двух последовательностей из набора данных о
продажах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (90 наименований) и приложения. Основной текст изложен
на 154 страницах машинописного текста, содержит 40 рисунков и 12 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении приводится обоснование актуальности темы диссертационной работы,
формулируется цель и научные задачи исследований, излагаются основные результаты,
включающие научную новизну и практическую значимость, приводятся основные научные положения, выносимые на защиту.
Первая глава посвящена анализу методов, используемых в СППР трейдинговых
компаний для управления процессами электронной коммерции. Показана важность в процессе управления поисково-расчетных действий по выявлению скрытых закономерностей
в экономических данных масштаба Big Data.
Трейдинговые компании используют транзакционные системы учета покупок, системы мониторинга рынка и субъектов экономики, влияющих на рынок, а также другие источники данных, сохраняя описания событий, что позволяет исследовать ретроспективные
7
экономические данные и приниматать актуализированные и обоснованные управленческие решения по торговым операциям.
Принятие решений о направлениях деятельности и использовании финансовых ресурсов принимается на различных уровнях иерархии трейдинговых компаний. Старший
менеджмент компании принимает стратегические решения об основных направлениях использования финансовых ресурсов (рынки, ценные бумаги, допустимый уровень риска).
Непосредственно трейдеры принимают текущие решения о выполнении торговых операций. При принятии решений трейдерами должны учитываться основные стратегические
направления, определяемые в рамках подсистемы стратегического управления, текущая
рыночная ситуация, набор ретроспективных данных о рыночной ситуации. Итоговый успех (финансовый результат) деятельности трейдинговой компании зависит от своевременности и обоснованности принимаемых трейдерами решений, поэтому большую важность
в общем цикле управления представляет анализ данных о рыночной ситуации, выбор
управленческих решений трейдером и учет эффектов от реализации выбранных управленческих альтернатив. Большие масштабы данных, недетерминированное развитие рыночной ситуации и неопределенность состояния рынка в будущем приводят к неопределенности в принятии решений трейдером. С целью снижения неопределенности принятия решений в трейдинговых компаниях используются СППР, выполняющие анализ ретроспективных данных и генерирующих приоритетные альтернативы управленческих решений с
учетом текущей рыночной ситуации. Место СППР в схеме деятельности трейдинговой
компании представлено на рисунке 1.
Рис. 1 Место СППР в схеме деятельности трейдинговой компании
8
Учет перечня факторов, влияющих на результаты принятия решений в трейдинге,
требует от СППР выполнения генерации альтернативных торговых стратегий, оценки
возможных финансовых результатов трейдинговой деятельности и снижения неопределенности в принятии решений. Использование СППР в управленческом цикле функционирования трейдинговой компании также позволяет осуществлять упреждающее выполнение комплекса этапов анализа данных и генерации вариантов решений на основе динамично выявляемых скрытых закономерностей из текущих и ретроспективных экономических данных.
С целью построения альтернативных прогнозов для обработки данных масштаба
Big Data в СППР трейдинговых компаний используются методы технического анализа,
what-if анализ, корреляционно-регрессионный анализ, различные методы Data Mining.
Широко используются предметно-ориентированные аналитические системы, основанные
на статистической обработке данных. Для принятия решений важны сведения о последовательности событий. Такая задача является подклассом задачи поиска ассоциативных
правил и носит название «секвенциальный анализ». Результатом секвенциального анализа
является информация для ЛПР в виде набора последовательных шаблонов (секвенций),
представляющих собой последовательность упорядоченных по времени событий, наблюдаемая не реже заданного порога, что позволяет утверждать о наличии связей между событиями.
Возможность использования последовательного шаблона как основания для расчета экономического результата операционной деятельности в условиях изменения рыночной ситуации в соответствии с событиями шаблона позволяет перейти от анализа рыночной ситуации к принятию решений о торговых операциях на основе альтернатив, получаемых в результате применения секвенциального анализа.
Наиболее известными коммерческими СППР, обеспечивающими анализ данных и
поддержку принятия решений для работы на электронных торговых площадках, являются:
MetaTrader компании MetaQuotes Software Corp. (Кипр), Elwave компании Elliot wave software (Нидерланды), MetaStock компании Equis International (США), QUIK компании
ARQA Technologies (Россия, Новосибирск). Основные возможности данных СППР представлены в таблице 1.
Таблица 1
Основные возможности СППР для электронного трейдинга
Возможности СППР
Объяснение результата
Автоматический учет макроэкономических факторов
Технический анализ
Автоматические уведомления о
новостях экономики и рынка
Программирование автоматических стратегий
Возможности
расширения
внешними модулями
MetaTrader
Частичное
Возможен
Elwave
Есть
Нет
MetaStock
Нет
Нет
QUIK
Нет
Возможен
Есть
Есть
Ограничен
Нет
Есть
Нет
Есть
Есть
Ограничено
Нет
Есть
Есть
Есть
Нет
Нет
Ограничено
У большинства представленных в таблице 1 СППР ограничены возможности по
учету макроэкономических параметров. В представленных СППР не реализуются
возможности анализа с интервальным заданием параметров, а также отсутствуют
элементы аппаратной акселерации обработки данных.
9
Использование выявленных шаблонов выступает как базовая фаза управления
электронными сделками, она позволяет ЛПР соотносить текущее развитие ситуации с
характерными для прошлых периодов времени последовательностями событий и
формировать управленческие решения из выявленных содержательно-временных закономерностей в исходных неструктурированных данных. Синтез приоритетных
альтернатив для управленческих решений осуществляется на основе отбора шаблонов, удовлетворяющих заданному ЛПР условию оптимизации.
Во второй главе решается задача разработки метода ППР на основе метода секвенциального анализа AprioriAll. Отличительная особенность разработанного метода - расширение его возможностей по интервальному заданию параметра поддержки,
а также повышение оперативности генерации альтернатив для управленческих решений.
В задаче секвенциального анализа задан алфавит свойств   {i1, i2 ,..., in} , где ik –
символ алфавита  , ik   , n |  | – мощность (размер) алфавита. Из символов  задаются наборы свойств (множества) I , I1  {i1} , …, I k  {ik } ,…, I k k  {ik , ik } , …,
I k ...k  {ik ,..., ik } , где ik   , {k1, k2 ,..., knI } - индексы свойств в множестве  , nI | I | . Так
же задан алфавит источников событий V  {v1, v2 ,..., vnV } , где vk – источник, nV |V | , причем V     , задано множество событий D  {d1, d2 ,..., dnD} , принадлежащих какомулибо из источников, где d k – событие, nD | D | – мощность множества событий. Каждое
событие d k есть набор элементов, dk  (v, t , I ) , где v – источник, t – время события, I набор свойств события d k . Поддержкой P(I ) набора свойств I называется отношение
количества источников событий, содержащих в событиях набор I , к общему количеству источников событий: P( I ) | V I | / | V | , где V I – множество источников, содержащих
набор I , V I  {vk1, vk 2 ,..., vkn } , где I  I kdv , I kdv – набор свойств события d k , принадлежащего источнику v .
Перед началом анализа ЛПР устанавливает значение минимальной поддержки
Pmin для уменьшения пространства поиска и получения последовательностей из практически значимых частых наборов. Набор свойств I называется частым, если его поддержка P(I ) не меньше установленной минимальной поддержки Pmin : P( I )  Pmin . Частый
набор свойств обозначается как f , а множество частых наборов как F , F  { f1, f 2 ,..., f nF } ,
nF – мощность множества F . В целях расширения возможностей генерации альтернатив на основе результатов секвенциального анализа вводится новый параметр, назыcon
ваемый минимальная поддержка последовательностей наборов Pmin
(или минимальная
s,
P con
поддержка последовательностей). Поддержка
последовательности
s  I k1, I k1,..., I kn  , определяется как отношение количества источников событий, содержащих последовательность s в общей последовательность событий, к количеству
источников событий: P(s) | V s | / | V | , где V s – множество источников, в последовательностях наборов которых содержится последовательность s .
Основная вычислительная нагрузка в традиционном методе AprioriAll определяется обработкой наборов свойств с возрастающим в процессе анализа количеством обрабатываемых элементов, а также необходимостью генерации кортежей на основе перебора комбинаций свойств исходных объектов.
1
l
m
l
m
10
1
1 2
1
2
Для генерации актуализированных решений разработан метод ППР на основе метода AprioriAll (таблица 2), типы обрабатываемых объектов разделяются на множества
(М) и кортежи (К).
Таблица 2
Шаги и характеристики разработанного метода ППР
Этап метода
Обрабатываемые объекты
Тип
объекта
Процесс
Входные данные
1.1 генерация
наборовкандидатов
1.2 выбор частых наборов
2.1 хеширование множества
частых наборов
2.2 построение
ориентированного дерева последовательностей
3.1 построение
частых последовательностей
3.2 максимизация частых последовательностей
3.3 ранжирование последовательных шаблонов
Наборы
свойств
М
Построение
пересечений и
объединений
Поиск вхождений
Хеширование
Частые наборы
свойств
Наборы
М
свойств
Частые наМ
боры свойств
Множество событий
Множество
частых наборов
Оценка вычислительной сложности частного
алгоритма
O(n )
O ( nD )
O ( nF )
Последовательности
исходного
множества
К
Генерация дерева последовательностей
Множество событий
O(l )
Последовательности
событий
Частые последовательности
К
Построение
конкатенаций
O ( nD )
К
Поиск вхождений
Трансформированное дерево событий
Множество
частых последовательностей
Частые последовательности
К
Сортировка
Управленчески
е альтернативы
O(nS )
O(ns ln(ns ))
Новизна метода ППР определяется добавлением этапа многомерного ранжирования последовательных шаблонов, что позволяет осуществить переход от параметрической генерации последовательных шаблонов к генерации альтернатив для управленческих решений, осуществляемой на основе упорядоченных по количественным показателям и возможным финансовым результатам от реализации торговой стратегии в соответствии с шаблоном. Также вместо единого порогового значения, применяется два пороговых значения: порог для наборов свойств и порог для последовательностей, что позволяет получать дополнительные варианты наборов последовательных шаблонов, а также
многократно использовать промежуточные результаты анализа для различных значений
поддержки последовательностей и выполнять построение последовательных шаблонов без
избыточных затрат времени на построение трансформированного множества событий.
Многократное использование промежуточных данных позволяет осуществлять их актуализацию, т.е. обновление структуры с темпом поступающих данных.
Для повышения обоснованности генерируемых альтернатив выполняется расширение списка параметров, используемых в ранжировании для определения приоритетных
альтернатив. Вводится показатель достоверности, используемый в смежном с секвенци11
альным анализом поиске ассоциативных правил. Для расчета применительно к последовательным шаблонам в методе поддержки принятия решений анализируемый кортеж
вида s  f1, f2 ,..., fk , fk 1,..., fn  B, N  представляется в виде ассоциативного правила
вида B  N , где B - префикс s длиной k, N - суффикс s длиной n-k, B  f1, f 2 ,..., f k  ,
N  f k 1,..., f n  , и вычисляется отношение поддержки префикса шаблона к поддержке
целого шаблона:
Conf ( B, N ) 
P( B, N )
,
P( B)
где Conf - показатель достоверности.
Получаемые значения достоверности позволяют упорядочить работу ЛПР при
использовании шаблонов с низкими значениями поддержки.
На основе метода был разработан алгоритм ППР, новизна которого заключается в
том, что на этапе построения ориентированного дерева последовательностей вместо
традиционной генерации множества последовательностей выполняется генерация
трансформированного набора последовательностей в виде дерева, в узлах которого находятся частые наборы и данные для определения поддержки последовательностей.
Схема алгоритма представлена на рисунке 2.
Рис. 2 Схема алгоритма ППР
В разработанном алгоритме используется следующая структура трансформированного множества: корнем дерева является набор, являющийся пустым множеством, а
в процессе построения в множество источников событий будут добавлены все представленные в исходном множестве источники событий. Структура полученного в результате трансформации дерева генерируется таким образом, чтобы в ней были отражены все последовательности, которые находятся в трансформируемом множестве со12
бытий. Структура модифицированного множества и дерево последовательностей для
источников событий {v1 , v2 } , последовательности событий которых содержат частые наборы {v1  {1},{2},{2},{3} , v2  {1},{2,3},{2} } , представлены на рисунке 3.
D:
f =ᴓ
f1
V={ v1 ,v2 ,…,vn}
{ Vf1}
f2
{ Vf2}
 {v1,v2}
…
fn
1 {v1,v2}
{ Vfn}
…
f1
f1
{ Vf1}
…
…
f2
…
fn
{ Vf2}
i2
f2
{ Vf2}
fn
v1
2 {v2}
2 {v1,v2}
3 { v1}
V:
in
v2
…
2 {v2}
2 {v1,v2} 3 { v1}
…
…
…
3 { v1,v2}
2 {v1,v2}
{ Vfn}
{ Vfn}
f:
i1
…
{ Vf1}
3 { v1,v2}
2 {v1,v2}
3 { v1}
3 { v1}
v nf
а)
б)
Рис. 3 Множество событий D после трансформации в дерево последовательностей, а) - структура, б) - пример
Генерация последовательных шаблонов осуществляется с использованием дерева
последовательностей для выбора и проверки поддержки частых последовательностей,
что позволяет выполнять генерацию альтернатив с помощью однократного обхода дерева последовательностей событий. Это позволяет уменьшить число итераций поиска в
результате отказа от шагов непродуктивной генерации последовательностей со значением поддержки ниже минимального.
В работе генерация последовательных шаблонов как конструктивный процесс
описывается продукционной системой вида: PM  {F , ,Y , D'} , где F – алфавит продукционной системы из частых наборов,  – стратегия построения последовательных
шаблонов, D' –дерево последовательностей событий, Y – набор ограничений, используемых при построении множества последовательных шаблонов.
Получаемые в результате работы алгоритма управленческие альтернативы представляют собой шаблоны, дополненные показателями для трейдинговой деятельности:
вариантом входа в позицию и вариантами выхода из позиции с прибылью или с убытком. Эти сведения в  представляются как множество продукционных выражений вида:
 Start  In, P  kstart , profit max  pr1 , profit min  pr2 , conf max  u;
 Start , Next   Out , P  k , profit  pr , conf  u ;
1
1
1
1

 Start , Next 2   Out , P  k2 , profit  pr2 , conf  u2 ;

,
...
 Start , Next   Out , P  k , profit  pr , conf  u ;
1
1
n
n

 Start , Next 2   Out , P  k2 , profit  prn1 , conf  un1;

...
(1)
где <Start> - кортеж событий, после которого возможно открытие позиции (покупка или продажа) с прибылью, является общим префиксом группы последовательных
шаблонов, In - открытие позиции, <Start,Nexti+> - кортеж событий, после которого рекомендуется выход из позиции с прибылью, <Start,Nexti–> - кортеж событий, после ко13
торого рекомендуется выход из позиции с убытком, P - поддержки кортежа левой части
импликации, k - значения поддержки, причем kstart ≥ ki±, profit - возможное значение финансового результата, profitmax и profitmin - экстремумы возможных значений финансового результата для обнаруженных последовательных шаблонов в рамках одной альтернативы, conf - значение достоверности, confmax - максимальное значение достоверности для последовательных шаблонов в рамках одной альтернативы.
Сравнение трудоѐмкости традиционного AprioriAll и разработанного алгоритма
дает сходные оценки в случае однократного анализа (для одного набора параметров):
линейная зависимость от размеров базы (на этапе генерации последовательностей) и
количества обнаруживаемых последовательностей (на этапе максимизации):
told (nD , ns )  O(nD  ns ) , tnew (nD , ns )  O(nD  ns ) , где t old - затраты времени для традиционного AprioriAll, t new - затраты времени для разработанного алгоритма. В случае интервального задания параметра поддержки последовательностей, когда количество отлиcon
min
чающихся значений параметра Pmin
составит nPcon
, для традиционного алгоритма необходимо
выполнение
генерации последовательностей
для
набора
min
min
min
con
значений Pmin : t old (nD , ns , nPcon )  O (nPcon * nD  nPcon * ns ) .
Для
разработанного
алгоритма с каждым новым значением параметра минимальной поддержки необходимо
min
min
выполнить только этап максимизации: t new (nD , ns , nPcon
)  O(nD  nPcon
* ns ) .
Разработанный алгоритм позволяет однократно выполнять вычислительно затратную предобработку данных. Для каждого элемента из набора входных параметров
однократно выполняется этап по выбору и максимизации последовательностей. Сокращение временной сложности в условиях диапазонного задания входных параметров
повышает актуальность генерируемых альтернатив для управленческих решений.
Третья глава диссертации посвящена разработке структуры СППР для управления торговыми операциями в трейдинговых компаниях с использованием разработанного метода ППР, выполняется детальная алгоритмизация шагов разработанного алгоритма, осуществляется введение в структуру СППР модуля для аппаратной поддержки вычислительно затратной операции по обработке пересечений последовательностей.
В результате использования модульной структуры достигается расширение
функциональности СППР путѐм введения новых модулей: хранилища промежуточных
результатов анализа, блока актуализации. Хранилище промежуточных результатов позволяет сохранять направленное дерево последовательностей для использования при
новых заданиях на анализ. Модуль актуализации позволяет сохранять соответствие
между базой транзакций и построенным деревом последовательностей при добавлении
новых транзакций в базу. Информационные связи обеспечивают возможности по заданию интервала параметров. Структурно-функциональная организация СППР представлена на рис. 4. Новые и подвергшиеся модификации модули и связи выделены цветом и
утолщенными линиями.
Структура модуля генерации последовательных шаблонов (МГПШ) в составе
компонента приобретения знаний представлена на рисунке 5.
Структура блоков анализа данных в МГПШ представлена на рисунке 6.
14
Рис. 4 Общая СФО СППР для трейдинговой компании
Рис. 5 Структура МГПШ в разработанной СППР
Для разработанного блока актуализации (рис. 4) создан алгоритм актуализации
дерева последовательностей, его использование позволяет поддерживать соответствие
между изменяющимися данными базы событий и многократно использовать дерево последовательностей без избыточных затрат на его построение.
Выявление скрытых закономерностей основывается на многократной обработке
массивов данных, при этом размер обрабатываемой единицы, как правило, имеет меняющиеся границы. Данные обстоятельства для экономических систем реального
уровня сложности (в которых выполняется обработка сотен показателей рыночной ситуации, обновление данных выполняется десятки раз в минуту) обуславливают необходимость перехода к аппаратным ускорителям отдельных шагов алгоритмов. Операция
поиска пересечений двух последовательностей используется на многих шагах анализа.
Аппаратная реализация этой операции возможна с использованием специализированного устройства параллельной обработки префиксно-суффиксных свойств последовательностей. Операция определения таких свойств используется на этапе максимизации
последовательностей в процессе определения совпадающих частей кортежей.
15
Рис. 6 Структура блоков анализа данных в МГПШ
Задача определения префиксно-суффиксных свойств последовательностей (слов)
x и y длиной n и m символов соответственно решается использованием матрицы совпадений элементов последовательностей, состоящей из поисковых ячеек, размер матрицы m n , а также k  m  n  1 позиций вхождений и 2(n  1) позиций пересечения последовательностей. Значения бинарных векторов в процессе вычисления позиций "1"
(позиций вхождений и пересечений двух последовательностей) осуществляется по
формуле: R j (k )  R j1 (k  1) & ( xk  y j ) , где R j (k ) - j -й бит k -го столбца вхождений префиксов последовательностей. Схема определения префиксно-суффиксных свойств
представлена на рисунке 7, на данную схему получен патент РФ №2430408.
Рис. 7 Определение префиксно-суффиксных свойств пары последовательностей
Практическая реализация МГПШ осуществлена путем создания модулей для
трейдинговой СППР MetaTrader в среде программирования Microsoft Visual Studio
2010.
Четвертая глава диссертации посвящена экспериментальной проверке работоспособности разработанных метода, алгоритма и СФО трейдинговой СППР на основе
реальных данных, используемых в деятельности типовой трейдинговой компании «ФК
«Жигули». В процессе моделирования временных зависимостей для алгоритма генерации альтернатив на практически значимых величинах входных параметров используются данные об изменениях курсов валютных пар евро/рубль, доллар/рубль, акций
16
ОАО «Газпром» и фьючерса РТС(RTS). Сравнение традиционного алгоритма с разработанным и проверка временной зависимости выполняется на годовом периоде изменений курсов с часовым интервалом измерений курсовых значений.
Примеры получаемых альтернатив в результате работы алгоритма ППР на данных об изменении курсов евро и рубля к доллару приведены в таблице 3, первая строка
- шаблон с рекомендацией об открытии позиции, левый столбец - рекомендации о закрытии с прибылью, правый - рекомендации о закрытии с убытком.
Таблица 3
Примеры приоритетных альтернатив для управленческих решений
<(EUR -5) (RUB -4) (EUR +2) (RUB -1) >→Buy(RUB) ; P=8,3%; profitmax=8; profitmin=-6;
confmax=42%
1. (EUR +2) (EUR -2) (RUB +6); profit=3; 1. (EUR +3) (EUR -4) (RUB -2); profit=-2;
conf=42%
conf=17,2%
2. (EUR -1) (RUB +1) (EUR -2) (RUB +2); prof- 2. (EUR -1) (RUB +1) (EUR +5) (RUB -7); profit=3; conf=15,3%
it=-6; conf=15,3%
3. (RUB +2) (EUR -2) (EUR -3) (RUB +3) (RUB 3. (RUB +2) (EUR -2) (EUR -3) (RUB +3) (RUB
+5);
-9);
profit=8; conf=12,8%
profit=-4; conf=12,8%
4. (RUB -1) (EUR -2) (RUB +6); profit=3;
conf=10,8%
Выполняется сравнение временных затрат на генерацию последовательных шаблонов для исходного и разработанного алгоритмов в зависимости от количества значеcon
ний минимальной поддержки с nPconmin значений параметра Pmin
. Результаты моделирования приведены на рисунке 8.
Результаты моделирования показывают снижение временных затрат в разработанном методе от 9,6% в случае анализа с единственным значением параметра и до
54,8% для случаев анализа с интервалом параметров, содержащим более 15 отличающихся значений, среднее значение сокращения временных затрат в деятельности ЛПР
для ЗАО "ФК "Жигули" составило 18,3%.
Рис. 8 Результаты моделирования для множества значений поддержки
Для сравнения достоверности генерируемых альтернатив выполняется моделирование двух вариантов ранжирования: по значению показателя поддержки и с расширенным набором показателей. Результаты представлены на рисунке 9.
17
Рис. 9 Результаты моделирования со сравнением достоверности
Сравнение получаемых альтернатив показало, что с использованием ранжирования с расширенным набором показателей средняя достоверность приоритетных альтернатив увеличивалась с 43,2% до 50,5% (выигрыш 7,3%).
По результатам экспертного оценивания, финансовым результатом использования разработанных модулей СППР в трейдинговой деятельности ЗАО "ФК "Жигули"
стало повышение прибыли от торговой деятельности на 5-6%.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В работе решена актуальная научная задача, заключающаяся в разработке метода
и алгоритма поддержки принятия решений, обеспечивающего поиск скрытых закономерностей в экономических данных с возможностью интервального задания параметров, и
достигнута поставленная цель по повышению достоверности и оперативности альтернатив для управленческих решений.
В ходе решения поставленной задачи получены следующие основные результаты:
1.
Создан метод поддержки принятия решений на основе метода секвенциального анализа данных. Новизна метода определяется добавлением этапа ранжирования последовательных шаблонов, что позволяет осуществить переход к генерации альтернатив
для управленческих решений на основе упорядоченных по количественным показателям и
возможным финансовым результатам. Также вместо единого порогового значения, применяется два пороговых значения: для наборов свойств и для последовательностей, что
позволяет получать дополнительные варианты наборов последовательных шаблонов, а
также многократно использовать промежуточные результаты для различных значений
поддержки последовательностей и выполнять построение шаблонов без избыточных затрат времени на построение трансформированного множества событий.
2.
Разработан алгоритм поддержки принятия решений на основе созданного метода. Реализуются возможности повторного использования промежуточных результатов
18
при многократном анализе исходных данных с интервалами параметров за счет применения модифицированной структуры хранения промежуточных данных, что позволяет
уменьшить время генерации альтернатив для управленческих решений. Расширение перечня параметров, по которым выполняется ранжирование альтернатив, позволило увеличить достоверность результатов и упорядочить работу ЛПР в условиях неопределенности
данных. Разработан алгоритм актуализации промежуточных результатов анализа, позволяющий добавлять в промежуточные результаты анализа новую информацию, сокращая
количество запусков генерации дерева последовательностей при обновлении данных.
3.
Разработана структурно-функциональная организация трейдинговой СППР,
еѐ особенностями являются наличие модуля для поддержки работы алгоритма поддержки
принятия решений, модуля актуализации промежуточных результатов анализа, модуля
максимизации последовательностей с аппаратной реализацией операции сравнения и определения префиксно-суффиксных свойств, позволяющего снизить затраты времени на
соответствующем этапе алгоритма, модуля генерации альтернатив, выполняющего ранжирование по расширенному списку параметров, а также информационных связей, позволяющих задавать параметры анализа в виде интервалов значений и обеспечивающих
функционирование модифицированных элементов системы.
4.
Разработано устройство определения префиксно-суффиксных свойств и
сравнения пары последовательностей, обрабатываемых в процессе анализа данных о трейдинговой деятельности, отличающееся безотступной параллельной обработкой всех диагоналей матрицы совпадений элементов последовательностей. Использование аппаратной
реализации отдельных шагов интеллектуального анализа позволяет сократить время генерации альтернатив для управленческих решений пропорционально длине обрабатываемого кортежа.
5.
Осуществлено моделирование разработанного алгоритма поддержки принятия решений с помощью наборов данных о значениях курсов акций и валют. Результаты
моделирования показывают увеличение показателя достоверности на 7,3% при ранжировании с расширенным списком параметров. Сравнительное моделирование генерации последовательных шаблонов традиционного AprioriAll и разработанного алгоритма подтверждает снижение затрат времени в случаях анализа с интервальным заданием параметров, в типовых условиях работы трейдинговой компании снижение в среднем составляет
18,3%.
СПИСОК ПУБЛИКАЦИЙ, СОДЕРЖАЩИХ ОСНОВНЫЕ
РЕЗУЛЬТАТЫ РАБОТЫ
Статьи в рецензируемых научных журналах и изданиях
1)
Воронин, Д.А. Метод и алгоритм интеллектуальной поддержки принятия
решений для трейдинговых компаний. / Д.А. Воронин, С.Г. Емельянов, О.И. Атакищев,
Е.А. Титенко // Известия ЮЗГУ. 2012. №6. С. 145-149.
2)
Воронин, Д.А. Структурно-функциональная организация системы поддержки принятия решений для трейдинговых компаний. // Известия ЮЗГУ. 2012. №6.
С. 149-153.
3)
Воронин, Д.А. Модифицированный алгоритм APRIORIALL поиска последовательных шаблонов [Текст] // В мире научных открытий. 2011. №8(20).
С. 136-145.
19
4)
Воронин, Д.А. Модифицированный метод секвенциального анализа данных.
[Текст] / Д.А. Воронин, Е.А. Титенко, М.А. Шевченко, В.А. Приходько, Е.А, Коломиец //
Известия ЮЗГУ. 2012. №2. С. 170-175.
5)
Воронин, Д.А. Продукционная модель для параллельной обработки знаний
[Текст] / Е.А. Титенко, Е.А. Петрик, Д.А. Воронин, И. В. Атакищева // Информационноизмерительные и управляющие системы. 2011. №11. С.81-86
6)
Воронин, Д.А. Структурно-функциональная организация арбитра параллельной обработки запросов [Текст] / Е.А. Титенко, Е.А. Семенихин, Е.А. Петрик, Д.А. Воронин // Информационно-измерительные и управляющие системы. 2010. №11. С. 30-34.
Статьи и материалы конференций
7)
Воронин, Д.А. Организация поиска ассоциативных правил в интеллектуальном анализе данных [Текст] / Е.А.Титенко, Д.А. Воронин, Д.Ю. Неклюдов // Оптикоэлектронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: труды IX международной научно-технической конференции, Курск: КГТУ, 2010. С. 108-109.
8)
Воронин, Д.А. Модификация обработки конструктивных объектов в методе
поиска периодических шаблонов [Текст] / Д.А. Воронин // Научное творчество XXI века:
материалы IV всероссийской научно-практической конференции с международным участием, Красноярск: Научно-инновационный центр, 2011. С.107-108.
9)
Воронин, Д.А. Модифицированный метод секвенциального анализа данных
[Текст] / Д.А. Воронин, Е.Б. Тутов // Новые технологии в научных исследованиях, проектировании, управлении, производстве НТ-2011: труды всероссийской конференции, Воронеж: ГОУВПО «Воронежский государственный технический университет», 2011. С. 152153.
10) Воронин, Д.А. Метод секвенциального анализа данных для систем управления потоками транзакций [Текст] / Д.А. Воронин // Информационные системы и технологии: труды I региональной научно-практической конференции, Курск: ГОУВПО «ЮгоЗападный государственный университет», 2012. С. 110-111.
Патент на изобретение
11) Патент 2430408 Российская Федерация, МПК G06F17/30. Устройство для параллельного поиска вхождений и пересечений слов [Текст] / Е.А. Титенко, Д.А. Воронин,
В.С. Евсюков, В.А. Семенихин, М.З. Набил Имхаммед, А.О. Атакищев, заявл. 29.03.2010,
опубл. 27.09.2011, бюл. № 27, 2011.
Подписано в печать 27.02.2013. Формат 60х84 1/16.
Печ. л. 1.0. Тираж 100 экз. Заказ __
Издательско-полиграфический центр
Юго-западный государственный университет
305040, г. Курск, ул. 50 лет Октября, 94
20
1/--страниц
Пожаловаться на содержимое документа