close

Вход

Забыли?

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

?

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

код для вставкиСкачать
Программные продукты и системы
12. Espejo P.G., Ventura S., Herrera F. A survey on the
application of genetic programming to classification, IEEE:
Transactions on Systems, Man and Cybernetics, 2009, Vol. 40, no.
2, pp. 121–144.
13. Frank A., Asuncion A. UCI Machine Learning Repository.
University of California, School of Information and Computer
Science, Irvine, CA, 2010. URL: http://archive.ics.uci.edu/ml (дата
обращения: 06.07.2011).
References
1. Hansen L.K., Salamon P., IEEE Transactions on Pattern
Analysis and Machine Intelligence, 1990, no. 12, pp. 993–1001.
2. Rastrigin L.A., Erenshtein R.H., Metod kollektivnogo
raspoznavanija [Method of collective recognition], Moscow,
Energoizdat, 1981.
3. Javadi M., Ebrahimpour R., Sajedin A., Faridi S., Zakernejad S., PLoS ONE, 2011, Vol. 6.
4. Perrone M.P., Cooper L.N., Artificial Neural Networks
for Speech and Vision, New York, Chapman & Hall, 1993,
pp. 126–142.
УДК 51–77+330.4
№ 4, 2012 г.
5. Shimshoni Y., Intrator N., IEEE Transactions on Signal
Processing, 1998, Vol. 46, pp. 1194–1201.
6. Wolpert D.H., Neural Networks, 1992, no. 5, pp. 241–259.
7. Jacobs R.A., Jordan M.I., Nowlan S.J., Hinton G.E.,
Neural Computation, 1991, no. 3, pp. 79–87.
8. Plumpton C.O., Kuncheva L.I., Proc. of Multiple Classifier Systems (MCS'10), Cairo, Egypt, LNCS 5997, 2010, pp. 54–63.
9. Kuncheva L.I., Combining Pattern Classifiers. Methods
and Algorithms, Wiley, 2004.
10. Bukhtoyarov V., Semenkina O., Proc. of 2010 IEEE
World Congress on Computational Intelligence, Barcelona, 2010,
pp. 1640–1645.
11. Sergienko R.B., Semenkin E.S., Proc. of 2011 IEEE
Congress on Evolutionary Computation, New Orleans, LA, USA,
2011.
12. Espejo P.G., Ventura S., Herrera F., IEEE: Transactions
on Systems, Man and Cybernetics, 2009, Vol. 40, no. 2, pp. 121–
144.
13. Frank A., Asuncion A. UCI Machine Learning Repository,
Available at: http://archive.ics.uci.edu/ml (accessed 06 July 2011).
КОМПЛЕКС ПРОГРАММ И АЛГОРИТМ
РАСЧЕТА ФРАКТАЛЬНОЙ РАЗМЕРНОСТИ
И ЛИНЕЙНОГО ТРЕНДА ВРЕМЕННЫХ РЯДОВ
О.И. Крылова, аспирант; И.В. Цветков, д.т.н., доцент
(Тверской государственный университет,
ул. Желябова, 33, г. Тверь, 170100, Россия, mancu@mail.ru)
Одним из перспективных направлений моделирования сложных систем является использование метода мультифрактальной динамики. В основу моделей мультифрактальной динамики положено описание динамики поведения
процессов, представленных мультифрактальными кривыми. Весь промежуток времени наблюдения разбивается на
интервалы с определенными значениями линейного тренда, который характеризует тенденцию изменения исследуемой величины. На каждом интервале для значений временного ряда определяется фрактальная размерность D.
В работе предлагается новый алгоритм расчета фрактальной размерности D огибающей временного ряда в виде
кусочно-линейной функции. Расчет фрактальной размерности огибающей временного ряда основан на вычислении
длины огибающей временного ряда с различной степенью группирования исходных данных. Для повышения точности расчета в алгоритме используются процедура построения трендовых каналов и нормирование значений первично
рассчитанной фрактальной размерности по результатам, полученным для специально сформированного стохастического временного ряда внутри трендового канала.
Предложенный в данной работе алгоритм расчета фрактальной размерности временных рядов использует процедуру построения трендовых каналов, которая является основным элементом классического технического анализа
финансовых рынков. Это повышает точность расчета фрактальной размерности и говорит о сближении фрактальной
теории и практики трейдерской деятельности, что повышает практическую значимость предложенного алгоритма.
Ключевые слова: фрактальная размерность, временной ряд, тренд, нормирование, программирование, алгоритм.
COMPLEX OF THE PROGRAMS AND ALGORITHM OF CALCULATION
OF THE FRACTAL DIMENSIONS AND A LINEAR TREND OF THE TIME SERIES
Krylova O.I., Postgraduate; Tsvetkov I.V., Ph.D., Associate Professor
(Tver State University, 33, Zhelyabova St., Tver, 170100, Russia, mancu@mail.ru)
Аbstract. One of the upcoming trends of modeling of complex systems is application of a multifractal dynamics method.
The multifractal dynamics models are based on the description of the dynamics of processes represented by multifractal
curves. The whole observation time period is got into intervals with defined values of a linear trend characterizing the trend
of the value of interest. On each interval, for time series values, a fractal dimension D should be defined.
This work offers a new algorithm of computation of a fractal dimension D of the time series envelope in the form of a
piece linear function. Computation of the fractal dimension of the time series envelope is based on calculation of the time
series envelope length while grouping initial data by different ways. In order to improve computation accuracy, the algorithm
uses a trend channel development procedure and rationing of first-calculated fractal dimension values based on the results
obtained for the specially generated stochastic time series inside the trend channel.
106
Программные продукты и системы
№ 4, 2012 г.
The time series fractal dimension computation algorithm offered in this work uses the trend channel development
procedure which is the main element of the classical technical financial market analysis. This improves the fractal dimension
computation accuracy and tells of approach of a fractal theory and a trader function practice thus improving the practical
relevance of the algorithm offered.
Keywords: fractal dimension, time series, trend, normalizing, programming, algorithm.
Одним из перспективных направлений моделирования сложных систем является использование метода мультифрактальной динамики. В настоящее время разработаны фрактальные подходы
для анализа поведения цен финансовых активов на
валютных и фондовых биржах, прогнозирования
изменения численности населения Земли и для
решения многих других задач [1–3].
В основу данных моделей положено описание
динамики поведения процессов представленных
мультифрактальных кривых. Для этого весь промежуток времени наблюдения разбивается на интервалы с определенными значениями линейного
тренда, который характеризует тенденцию изменения исследуемой величины. На каждом интервале для значений временного ряда определяется
фрактальная размерность D и устанавливается зависимость тангенса угла наклона линейного тренда и фрактальной размерности исследуемых кривых. В данных моделях учитываются различные
параметры, характеризующие устойчивость систем и протекающих в них процессов.
Классический (прямой) способ измерения
фрактальной размерности может быть реализован
клеточным методом. Однако, как и во всяком методе, связанном с дискретизацией, для повышения
точности вычисления фрактальной размерности
необходимо существенно увеличивать объем вычислений, поэтому в ряде случаев клеточный метод неудобен для использования.
Разработанный авторами алгоритм предназначен для расчета фрактальной размерности на основе оценки зависимости длины кривой от временного масштаба. Такой способ обеспечивает
определение фрактальной размерности с приемлемой точностью и небольшими вычислительными затратами и требует создания соответствующих алгоритмов и комплекса программ.
Описание алгоритма расчета
Пусть заданы: временной ряд Y – упорядоченное множество значений {yi}, i=1, …, N, с временным дискретом ∆T; критерии изменения тренда –
пересечение скользящих средних p-го и q-го
порядков, а также длительность тренда, не менее
заданной – ∆Tтр; требуемая точность оценки
фрактальной размерности – ε; допустимая вычислительная сложность.
Необходимо провести мультифрактальный
анализ заданного временного ряда: разбить множество {yi} на непересекающиеся подмножества
{yij} с различными трендами и для каждого подмножества рассчитать фрактальную размерность с
требуемой точностью ε и допустимой вычислительной сложностью алгоритма.
В алгоритме при разбиении множества {yi} на
непересекающиеся подмножества {yij} границы
соседних подмножеств определяются по изменению знака разности скользящих средних p-го и
q-го порядков.
В предлагаемом алгоритме используется способ расчета фрактальной размерности на основе
оценки зависимости длины фрактальной кривой
от временного масштаба. Для этого исходный
временной ряд представляется в графическом виде
– строится график, на котором по оси абсцисс откладываются временные дискреты i*∆T, а по оси
ординат значения yi.
На рисунке 1 приведен пример колебания цены
на нефть в период со 2.01 по 31.12.2008 г.
Для каждого подмножества yij строится ломаная линия, соединяющая значения соседних элементов ряда zi(t), а также линейный тренд ziтр(t).
Линейный тренд представляет собой уравнение
регрессии на множестве yij:
zi(t) = ziтр(t) + ziотк(t),
(1)
где ziотк(t) – функция отклонения значения ломаной zi(t) от линейного тренда.
На рисунке 2 представлено построение линейных трендов для графика изменения цены на
нефть в период со 2.01 по 31.12.2008 г.
Как известно, фрактальная размерность характеризует изрезанность кривых линий. В частности,
для временного ряда это ломаная линия на временном графике, соединяющая соседние (по времени) значения элементов массива входных данных. Обозначим ее Lo.
Длина ломаной кривой является одним из параметров, косвенно характеризующих изрезанность.
Для уменьшения изрезанности кривой можно
использовать процедуру сглаживания, суть которой в замене фактических исходных данных их
средними значениями, вычисляемыми с учетом
соседних значений временного ряда.
Назовем множество соседних точек, участвующих в одной процедуре усреднения, группой
усреднения.
Существуют два основных способа группирования данных для усреднения: группы пересекаются между собой (так, например, в техническом
анализе – вычисление скользящих средних) и
группы не пересекаются между собой.
В предлагаемом алгоритме используется второй способ. В этом случае можно перейти к групповому описанию входного массива данных.
Группу данных можно заменить на одного пред107
Программные продукты и системы
№ 4, 2012 г.
ставителя (со средними значениями) – групповой
элемент и получать ломаную линию, соединяющую групповые элементы, а также использовать
длину этой ломаной (lгруп.) в качестве косвенного
параметра изрезанности.
На рисунке 3 показаны ломаные линии, отражающие цену на нефть в период со 2.01 по
7.07.2008 г. при степени группирования 2, 4, 6.
В данной задаче для оценки фрактальной размерности выбирают не непосредственно этот показатель, а скорость его изменения при увеличении степени группирования входных данных.
долл./барр.
155,00
для графика изменения цены на нефть в период со
2.01 по 7.07.2008 г.
Ln(Lk)
5,80
5,70
5,60
5,50
5,40
5,30
5,20
0,00
0,69
1,10
1,39
1,61
1,79
Ln(k)
Рис. 4
135,00
115,00
95,00
75,00
55,00
35,00
1
46
91
136
181
226
271
316
361
сутки
Рис. 1
долл./барр.
155,00
135,00
y = 0,2981x + 82,944
115,00
y = -0,6103x + 254,4
95,00
75,00
55,00
35,00
1
46
91
136
181
226
271
316
361
сутки
Рис. 2
долл./барр.
150
140
130
120
110
100
90
80
1
16
31
46
61
76
91
106
121
136
151
166
181
сутки
Рис. 3
Таким образом, для расчета фрактальной размерности изрезанной кривой необходимо на основе группового усреднения задать процедуру ее
распрямления и проанализировать скорость, с которой происходит это распрямление, то есть изменяется длина кривой в зависимости от степени
группирования.
Для этого строится гистограмма L для степени
группирования 1, 2, …, k. Обычно гистограмма
представляет собой нелинейную убывающую
функцию. На рисунке 4 показан вид этой функции
108
Учитывая вид гистограммы, а также то, что
при расчете фрактальной размерности используется экспонента (логарифм натуральный), гистограмму целесообразно аппроксимировать функцией вида L′=Lo*e-α (α определяется из критерия
min(L′–Lфакт.)).
Опыт показывает, что во многих рассматриваемых случаях коэффициент связан с фрактальной размерностью D простой зависимостью α=2–
D.
Таким образом, L=Lo* e2-D. Или, прологарифмировав, получим D=lnLo–lnL+2.
При реализации такого подхода к определению
фрактальной размерности требуется нормирование значений первично рассчитанной фрактальной
размерности по результатам, полученным для
специально сформированного стохастического
временного ряда. Обычно это осуществляется
следующим образом.
Пусть задан временной ряд на i-м временном
участке yi(t). Для исследуемого временного ряда
определяются минимальное ymini, максимальное
ymaxi, а также на основе оценки зависимости длины
фрактальной кривой от временного масштаба первичная фрактальная размерность D0i. Далее формируется специальный временной стохастический
(нормировочный) ряд со значениями, лежащими в
интервале (Ymini; Ymaxi), и для него на основе оценки зависимости длины фрактальной кривой от
временного масштаба определяется фрактальная
размерность Dстохi.
На рисунке 5 показан стохастический ряд для
данных цены на нефть в период со 2.01 по
7.07.2008 г.
Фактическая фрактальная размерность (после
нормировки) заданного временного ряда определяется [5] по формуле
Di=D0i–∆Di,
(2)
где ∆Di=Dстохi–1,5.
Часто исследуемые временные ряды имеют ярко выраженный линейный тренд и область изменения значений данных рядов можно описать системой
Программные продукты и системы
№ 4, 2012 г.
ymin(t)=ymin0+k*t;
ymax(t)=ymax0+k*t,
(3)
где k=const – тангенс угла наклона линейного
тренда.
В этом случае нормировочный временной ряд
должен также формироваться в области (3), а не в
интервале (Ymin; Ymax). В противном случае в расчете фрактальной размерности могут возникнуть
существенные ошибки.
долл./барр.
96,00
94,00
92,00
90,00
88,00
86,00
1
16
31
46
61
76
91
106 121 136 151 166 181
сутки
Рис. 5
Автоматически определять область (3) и формировать непосредственно в ней нормировочный
ряд затруднительно, поэтому предлагается следующий новый алгоритм, учитывающий необходимость приведения в соответствие областей изменения заданного и специально сформированного стохастического ряда.
Сначала во временном ряду выявляется линейный тренд yтрi(t), то есть значения временного ряда на каждом i-м участке yi(t) представляются в
виде двух составляющих – линейной (трендовой)
yтрi(t) и отклонением yотi(t). Как известно, фрактальная размерность характеризует изрезанность
кривой, то есть фрактальная размерность временного ряда в основном содержится в отклонении
yотi(t). Поэтому для расчета фрактальной размерности далее линейный тренд yтрi(t) исключается.
Затем определяются максимальное ymax от и минимальное ymin от значения отклонения yотi(t) согласно (3), и в этом интервале формируются значения
стохастического нормировочного временного ряда. На следующем этапе вычисляется фрактальная
размерность с использованием выражений (1)
и (2).
Представим алгоритм данной задачи.
1. Задание исходных данных:
– входные данные (массив значений временного ряда);
– условно постоянные (временная дискрета
(масштаб), порядок скользящей средней, допустимое изменение скользящей средней, допустимая
длина тренда, степень группирования).
2. Последовательное определение трендовых
участков (разбиение исходного множества на
трендовые участки):
– проверка первого критерия: изменение наклона скользящей средней p-го порядка для двух
соседних элементов массива больше заданной величины;
– проверка второго критерия: длина предварительно определенного (вычисленного) тренда
больше допустимой длины временного интервала;
– расчет параметров линии тренда: определение границ линейного тренда; вычисление коэффициентов линейного тренда y=kt+b; вычисление
ширины трендового канала.
3. Формирование стохастического ряда внутри трендового канала.
4. Расчет фрактальной размерности:
– расчет длин огибающих временного ряда
для различных степеней группирования для исходного и стохастического рядов;
– расчет первичной фрактальной размерности: логарифмирование длин огибающих и степеней группирования исходного и стохастического
рядов; расчет угла наклона линии регрессии для
множества логарифмических длин огибающих исходного и стохастического временных рядов при
различных степенях группирования;
– нормировка первичной фрактальной размерности исходного временного ряда.
5. Вывод полученного результата.
Данный алгоритм реализован в среде Delphi в
виде комплекса программ.
При исключении линейного тренда точность
расчета фрактальной размерности возрастает от
0 до 15–20 % в зависимости от угла наклона тренда, соотношения ширины ценового канала ymax от–
–ymin от и размаха временного ряда Ymin–Ymax.
Подводя итог, отметим, что предложенный в
данной работе алгоритм расчета фрактальной размерности временных рядов использует процедуру
построения трендовых каналов, которая является
основным элементом классического технического
анализа финансовых рынков. С одной стороны,
это делает более точным расчет фрактальной размерности, с другой – говорит о сближении фрактальной теории и практики трейдерской деятельности, что повышает практическую значимость
данного алгоритма.
Литература
1. Holder M., Tsvetkov I. Analysis of the Dow-Jones
Idustrial Average (DJIA): Index Dynamics by Fractal Analysis
Methods. Proc. of Vth Intern. Congr. of math. modeling. Dubna.
2002. Vol. 2. 150 p.
2. Кудинов А.Н., Сажина О.И., Цветков В.П., Цветков
И.В. Фрактальная модель роста народонаселения // Вестн.
РУДН. 2010. № 2 (2). С. 132–138 (Математика. Информатика.
Физика).
3. Kudinov A.N., Tsvetkov V.P. and Tsvetkov I.V. Catastrophes in the Multi-Fractal Dynamics of Social-Economic Systems.
Russian Journ. of Math. Phys., 2011, Vol. 18, no. 2, pp. 149–155.
4. Кудинов А.Н., Михеев С.А., Цветков В.П., Цветков
И.В. Нелинейная фрактальная модель валютного кризиса //
Программные продукты и системы. 2008. № 4. С. 117–119.
109
Программные продукты и системы
5. Гуляева О.С., Цветков И.В. Определение фрактальной
размерности на основе измерения длин графиков временных
рядов в различных временных масштабах // Вестн. ТГУ. 2007.
№ 17 (45). С. 155–160 (Прикладная математика).
References
1. Holder M., Tsvetkov I., Proc. of V Interm. congress of
mathematical modeling, Vol. 2, Dubna, 2002, 150 p.
№ 4, 2012 г.
2. Kudinov A.N., Sazhina O.I., Tsvetkov V.P., Tsvetkov I.V.,
Vestnik RUDN, 2010, no. 2 (2), pp. 132–138.
3. Kudinov N., Tsvetkov V.P. and Tsvetkov I.V., Russian
Journ. of Math. Physics, 2011, Vol. 18, no. 2, pp. 149–155.
4. Kudinov A.N., Miheev S.A., Tsvetkov V.P., Tsvetkov
I.V., Programmnye produkty i sistemy, 2008, no. 4, pp. 117–119.
5. Gulyaeva O.S., Tsvetkov I.V., Vestnik Tverskogo Gos.
Univ., 2007, № 17 (45), pp. 155–160.
УДК 004.75
ЭКСПЕРИМЕНТАЛЬНАЯ СРЕДА ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ
В ИНСТИТУТЕ МАТЕМАТИКИ И МЕХАНИКИ УрО РАН
Д.Г. Ермаков, к.ф.-м.н., с.н.с.; Д.А. Усталов, ст. программист
(Институт математики и механики УрО РАН, ул. Софьи Ковалевской, 16, г. Екатеринбург,
620990, Россия, Ermak@imm.uran.ru, dau@imm.uran.ru)
Рассматривается задача предоставления масштабируемой вычислительной инфраструктуры для консолидации
компьютерного оборудования, используемого в целях разработки, отладки и развертывания ПО, а также дидактической поддержки образовательных курсов. Сформулированы требования к ПО и выполнен обзор существующих решений: Eucalyptus, OpenNebula, OpenStack, Nimbus. В результате их сравнения принято решение об экспериментальном развертывании средств OpenNebula на основе гипервизора KVM и ОС GNU/Linux.
Среда OpenNebula – это свободное ПО, предназначенное для управления облачной инфраструктурой класса «инфраструктура как услуга». Гипервизор виртуальных машин KVM разрабатывается компанией Red Hat и поддерживается средой OpenNebula в качестве решения для виртуализации по умолчанию. Описаны вычислительные ресурсы
Института математики и механики (ИММ) УрО РАН и выделенные серверные узлы для запуска экспериментальной среды облачных вычислений. Приведена конфигурация типового узла среды облачных вычислений на основе
ОС Scientific Linux 6.1 (x86_64) с использованием технологий LVM, KVM и libvirt. Описано представление облачной
среды как на логическом, так и на физическом уровнях. Обозначены проблемы функционирования системы безопасности SELinux и обеспечения отказоустойчивости системы. Сформулирован дальнейший план работ по таким направлениям, как интеграция с доменной системой Active Directory, применение сетевого хранилища (NAS) для хранения образов виртуальных машин, миграция на клиент-серверную БД MySQL и необходимость апробации и предоставления масштабируемых Web-сервисов для конечных пользователей среды облачных вычислений ИММ УрО
РАН.
Ключевые слова: виртуализация, гипервизор виртуальных машин, облачные вычисления, инфраструктура как
услуга (сервис), KVM, OpenNebula, IaaS.
THE EXPERIMENTAL CLOUD COMPUTING ENVIRONMENT
IN INSTITUTE OF MATHEMATICS AND MECHANICS URAL BRANCH OF RAS
Ermakov D.G., Ph.D., Senior Researcher; Ustalov D.A., Senior Programmer
(Institute of Mathematics and Mechanics Ural Branch of the Russian Academy of Sciences,
16, Sofi Kovalevskoy St., Ekaterinburg, 620990, Russia, Ermak@imm.uran.ru, dau@imm.uran.ru)
Аbstract. This paper considers the problem of providing a scalable computing infrastructure to consolidate computing
equipment used for developing and debugging software as well as for the didactic support of educational courses. Software
specifications are formulated and the following existent solutions are reviewed and compared: Eucalyptus, OpenNebula,
OpenStack, and Nimbus. A decision is made to perform an experimental deployment of the OpenNebula suite based on the
KVM hypervisor and the GNU/Linux operating system.
OpenNebula is an open source software designed to control the cloud environment of the Infrastructure-As-a-Service
class. The KVM hypervisor was developed by Red Hat and is supported by OpenNebula as a default virtualization solution.
The available computational resources of the Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy
of Sciences, and dedicated backend nodes for the experimental cloud computing environment are described. The
configuration of a typical cloud computing node under the Scientific Linux 6.1 (x86_64) operating system with the LVM,
KVM, and libvirt technologies is presented. The cloud environment architecture is presented at both logical and physical
levels. Some difficulties concerning the SELinux security system and the fault-tolerance performance are described. A plan
of further work in the following directions is suggested: integration with the Active Directory domain system, application of
the network-attached storage to keep the images of virtual machines, migration to the MySQL relational database, and the
testing and presentation of scalable Web services to cloud computing end users at the IMM UrB RAS.
Keywords: virtualization, virtual machine hypervisor, cloud computing, Infrastracture-as-a-Service, IaaS, KVM,
OpenNebula.
110
Документ
Категория
Без категории
Просмотров
26
Размер файла
369 Кб
Теги
комплекс, алгоритм, программа, временные, фрактальная, рядом, расчет, размерность, линейного, тренды
1/--страниц
Пожаловаться на содержимое документа