Учебная работа. Различия в распределениях степеней вершин нескольких MST
Различия в распределениях степеней вершин нескольких MST
Введение
В последнее время для анализа фондового рынка используется сетевая модель. Под сетевой моделью понимается полный взвешенный граф, в котором роль вершин исполняют акции, торгующиеся на рынке, а веса ребер высчитываются как коэффициенты корреляций доходностей каждой пары акций. Первой работой в этом направлении является работа Р.Мантегна (1998)[1]. В этой работе на основе сетевой модели обнаружена иерархическая структура. Для обнаружения этой структуры использовано минимальное остовное дерево (MST). MST представляет собой дерево, сумма весов которого минимальна. Каждое такое дерево имеет некоторую топологию.
В настоящей работе рассматривается задача сравнения топологии максимального остовного дерева, т.е. дерева с максимальной суммой весов, с течением времени. Топология MST оценивается с помощью степеней вершин. Под степенью вершин понимается число ребер, исходящих из этой вершины.
Цель и задачи исследования. Цель — выявить различия в распределениях степеней вершин нескольких MST.
В соответствии с поставленной целью исследования в работе поставлены следующие задачи:
построить и изучить статистическую процедуру проверки многих гипотез о сравнении степеней вершин в MST;
исследовать характеристики процедуры;
применить к реальным данным.
Структура работы: структура работы обусловлена целью и задачами исследования. Работа состоит из введения, двух глав, заключения, списка литературы и приложения.
Глава 1. Теоретическая часть
1.1 Основные понятия теории графов
Граф — упорядоченная пара конечного множества вершин и множества ребер.
Взвешенный граф — это граф, некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа.
Связный граф — граф, у которого между двумя любыми вершинами существует просто путь.
максимальное остовное дерево — ациклическое множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём максимальна.
Для решения задачи о максимальном каркасе известно несколько алгоритмов. рассмотрим два из них.
В алгоритме Прима на каждом шаге рассматривается частичное решение задачи, представляющее собой дерево. На первом шаге это дерево состоит из одной произвольно выбранной вершины. Затем к дереву последовательно добавляются ребра и вершины, пока не получится остовное дерево — каркас. Для того, чтобы из текущего дерева при добавлении нового ребра снова получилось дерево, новое ребро должно быть инцидентно вершине, уже содержащейся в дереве. При выполнении алгоритма Прима необходимо следовать определенному правилу выбора: на каждом шаге из всех подходящих ребер выбирается ребро наибольшего веса для построения максимального остовного дерева.
другой жадный алгоритм для задачи об MST известен как алгоритм Краскала, где на каждом шаге тоже рассматривается частичное решение. В отличие от алгоритма Прима частичное решение в алгоритме Краскала всегда представляет собой лес, состоящий из всех вершин исходного графа и некоторых ребер. Вначале новый граф состоит из изолированных вершин, т.е. текущее множество ребер устанавливается пустым. Затем к имеющемуся множеству последовательно добавляются ребра, появление которых не образует цикл, пока не будет построен каркас исходного графа. Для выбора добавляемого ребра применяется тот же «жадный» принцип, что и в алгоритме Прима — из всех ребер выбираются ребра с максимальным весом.
.2 Схема построения сетевой модели рынка
Как сказано выше, анализ фондового рынка, представленного графом, происходит на основе корреляционной связи акций друг с другом. каждая ценная бумага интерпретируется как одна вершина графа. Две вершины соединяются ребром, вес которого равен корреляции доходностей между этими ценными бумагами[2].
Для построения графа рынка будут использоваться стандартные характеристики финансовых активов.
Пусть Pi(t) — цена финансового актива i, i=1,…,N, в день t, t=1,…,n. Будем считать, что
определяет доходность ценной бумаги i за период, равный одному дню.
Обозначим среднюю доходность ценной бумаги i за n дней как
.
Дисперсия доходности ценной бумаги i за n дней рассчитывается по формуле:
.
Тогда коэффициент корреляции высчитывается по следующей формуле (для финансовых активов i и j):
.
.2 Метод Монте-Карло
методы Монте-Карло — единое название совокупности численных методов, базирующийся на получении внушительного количества реализаций стохастического процесса, который создается так, чтобы его вероятностные характеристики соответствовали подобным величинам рассматриваемой задачи.
.3 Статистический бутстрэп
С середины прошлого века на волне развития вычислительных технологий в свет стали выходить работы, рассказывающие о ресэмплинге — генерации вспомогательных выборок из уже имеющихся. одна из основных процедур ресэмплинга, бутстрэп, была предложена Брэдли Эфроном в 1979 году[3]. Основная идея бутстрэпа заключается в том, чтобы методом статистических испытаний Монте-Карло многократно извлекать повторные выборки из эмпирического распределения. То есть берется конечная совокупность из n членов исходной выборки x1, x2,…, xn-1, xn, откуда на каждом шаге из n последовательных итераций с помощью генератора псевдослучайных чисел «выуживается» произвольный элемент xk, который опять «возвращается» в исходную выборку.
Этот процесс обычно повторяется большое количество раз. По итогам легкого преобразования частотного распределения реализаций исходных данных можно полагать, что каждая следующая генерируемая псевдовыборка вернет значение параметра, которое будет слегка отличаться от вычисленного для исходной совокупности. На основе полученного в процессе имитации разбросе значений отслеживаемого показателя можно построить доверительные интервалы оцениваемого параметра[4].
Бутстреп-процедура выглядит следующим образом. Пусть имеется n наблюдений — первоначальная выборка:
… за случайным вектором .
Под выборкой, полученной бутстрэпом, понимается выборка размера n, полученная из первоначальной выборки следующим образом:
задается случайная величина .
Проводится n случайных экспериментов, результатами которых являются наблюдения за значениями . Пусть наблюденные значения имеют вид:. Тогда выборка, полученная бутстрэпом, имеет вид:
….
.5 Процедура сравнения распределения вершин двух выборочных MST
На входе: две последовательности по n наблюдений за двумя случайными векторами размерности N.
Описание процедуры:
Применить S раз процедуру статистического бутстрэпа к каждой последовательности векторов наблюдений.
Для каждого результата бутстрэпа вычислить MST и по найденному MST найти вектор распределения степеней вершин (k1, k2,…,kN-1), где ki — число вершин степени i. Получаются S векторов распределения степеней вершин.
построить гистограммы каждой координаты ki (по S наблюдениям) и выделить 5% доверительный интервал изменения координаты.
По окончании процедуры следует принять решение: если хотя бы для одного значения i доверительные интервалы первого и второго векторов наблюдений не пересекаются, то гипотеза о равенстве MST отвергается (имеется значимое различие в структуре MST).
необходимо выяснить, получаются ли MST разными в силу тенденции или случайных колебаний. С помощью бутстрэпа оцениваем степень разброса степеней вершин как топологическую характеристику. Распределение степеней вершин — слишком большая функция, поэтому переходим к распределению отдельных степеней.
Проверим процедуру на простом примере. Сгенерируем нормально распределенную независимую генеральную совокупность, где и.
Дважды составим выборку длины n=250 из . По наблюдениям построим MST алгоритмом Краскала.
Рис. 1. Распределение степеней вершин в первом и втором MST соответственно.
Пример приводится на основе MST вида «путь», отсюда по 2 вершины степени один (крайние), и 98 вершин степени два.
Проведем бутстрэп-процедуру и построим 10% доверительные интервалы. По графикам ниже видно, что интервалы для одних и тех же степеней совпадают, следовательно, гипотеза о равенстве MST верна, а реализованная процедура корректна.
Рис. 2. гистограмма распределения вершин степени «1» на основе первой и второй выборки соответственно.
Рис. 4. гистограмма распределения вершин степени «3» на основе первой и второй выборки соответственно.
Глава 2. Описание экспериментов
Эксперименты проводятся на основе реальных данных с фондовых рынков США и великобритании (NASDAQ и FTSE соответственно) за период с 01 января 2003 г. по 31 декабря 2014 г. Для каждой из рассматриваемых стран отобраны первые по объемам продаж активы, которые присутствовали на рынке весь период. Атрибут актива — логарифмические доходности.
задача: оценить неопределенность (достоверность) полученной информации о степенях вершин.
рассмотрим рынок США за 2003 и 2004 гг:
Активы количеством N=98, выборка размером n=250. Алгоритмом Краскала по матрице коэффициентов корреляции, полученной из матрицы доходностей, строится максимальное остовное дерево, затем считается количество различных степеней вершин полученного MST.
Рис. 5. Гистограмма распределения степеней вершин в MST, США, 2003 г.
Как видно по гистограмме, в «изначальном» MST больше всего вершин степени 1. Нельзя утверждать, что данная структура сохранится на протяжении всего рассматриваемого периода.
после проведения бутстрэп-процедуры и сопутствующих ей действий строятся гистограммы каждой координаты ki. рассмотрим гистограмму, показывающую, сколько раз степень «1», появляющаяся с определенной частотой в одном MST, встретится с такой же частотой при проведении ста таких экспериментов.
Рис. 6. Число вершин степени 1 в 100 экспериментах, США, 2003 г.
Границы найденного 10% доверительного интервала обозначены красными линиями. Оставшиеся гистограммы находятся в приложении.
Процедура повторяется для всех периодов наблюдений.
«Изначальное» MST за 2004 г.:
Рис. 7. гистограмма распределения степеней вершин в MST, США, 2004 г.
Рис. 8. Число вершин степени 1 из 100 экспериментов, США, 2004 г.
Значения доверительных интервалов векторов наблюдений за два года (2003 и 2004 гг.) в случае степени 1 пересекаются. Оставшиеся гистограммы находятся в Приложении 1.
после анализа всех гистограмм 2003 и 2004 гг. можно сделать вывод, что гипотеза о равенстве MST в рамках рынка США не отвергается, т.е. не имеется значимых различий в структуре MST — доверительные интервалы совпадают.
рассмотрим рынок Великобритании за 2003 и 2004 гг.:
Активы количеством N=91, выборка размером n=250.
Рис. 9. Гистограмма распределения степеней вершин в MST, Великобр., 2003 г.
Рис. 10. Число вершин степени 1 из 100 экспериментов, Великобр., 2003 г.
Рис. 11. Число вершин степени 1 из 100 экспериментов, Великобр., 2004 г.
Значения доверительных интервалов векторов наблюдений за два года (2003 и 2004 гг.) в случае степени «1» пересекаются. Оставшиеся гистограммы находятся в Приложении 2.
после анализа всех гистограмм 2003 и 2004 гг. можно сделать вывод, что гипотеза о равенстве MST в рамках рынка великобритании не отвергается, т.е. не имеется значимых различий в структуре MST — доверительные интервалы совпадают.
несмотря на кажущуюся приблизительно одинаковой частоту появления одних и тех же степеней вершин, их распределения не одинаковы, поэтому можно утверждать, что гипотеза о равенстве MST рынков США и великобритании отвергается, т.е. MST этих стран имеют разную топологию.
Заключение
В результате работы построены MST для рынков США и великобритании, построена и изучена статистическая процедура проверки многих гипотез о сравнении степеней вершин в MST. В частности, показано, что MST двух данных стран обладают разной топологией, а структура MST отдельно взятой страны сохраняется на протяжении рассматриваемого периода.
граф сетевой бутстрэп
список литературы
[1] Mantegna R.N. Hierarchical Structure in Financial Markets // The European Physical Journal B — Condensed Matter and Complex Systems. — 1999. — Volume 11, Issue 1. — P. 193-197.
[2] Визгунов А. Н., Гольденгорин Б. И., Замараев В. А. и др. Применение рыночных графов к анализу фондового рынка россии // Журнал новой экономической ассоциации. — 2012. — № 3(15). — С. 66-81.
[3] Efron B. Bootstrap Methods: Another look at the Jackknife // The Annals of Statistics. — 1979. — Vol. 7, no. 1. — P. 1-26.
[4] Шитиков В.К., Розенберг Г.С. Рандомизация и бутстреп: статистический анализ в биологии и экологии с использованием R. — Т.: Изд. дом «Кассандра», 2013. — 314 с.
Приложение
Гистограммы частоты встреч количества вершин различных степеней на рынке США за 2003 г.:
Степень 2Степень 3
Степень 4Степень 5
Степень 6Степень 7
Степень 8Степень 9