Построение статистического правила для решения задачи построения MST - Анализ статистических свойств процедуры построения минимального остовного дерева

Минимальное остовное дерево в связанном взвешенном неориентированном графе-это остовное дерево данного графа, в котором сумма весов, входящих в него ребер, минимальна.

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

Данное расстояние высчитывается по следующей формуле:

),

Где, а

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

,

Определяет среднюю доходность ценной бумаги I за N дней,

,

Определяет дисперсию доходности ценной бумаги I за n дней.

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

    1. Полагаем множество ребер остовного дерева пустым. 2. Определяем множество, состоящее из множества вершин дерева. 3. Сортируем множество ребер E исходного графа в порядке возрастания их весов. 4. Формируем очередь Q, элементы которой-ребра графа G. 5. Если множество содержит более одной вершины и очередь не пуста, переходим на шаг 6, иначе -- на шаг 8. 6. Извлекаем из очереди ребро. Если концы ребра е принадлежат различным множествам вершин и из, то переходим на шаг 7, если иначе, то отбрасываем извлеченное ребро и возвращаемся на шаг 5. 7. Объединяем множества вершин и (полагая ), удаляем множества и из множества и добавляем в множество. Добавляем ребро в множество. Возвращаемся на шаг 5. 8. Прекращаем работу. Множество - это и есть множество ребер полученного остовного дерева.

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

,

После построения истинной структуры, сгенерируем наблюдения из нормального многомерного закона и построим структуру по наблюдениям за доходностями акций для выбранного индекса (sample-структуру), найдем значение. Для определения зависимости статистической неопределенности от, проведем данные сравнения 100 раз и подсчитаем частоту не более некорректно включенных ребер, где частота находится по формуле:

(

В данной главе была поставлена проблема измерения статистической неопределенности минимального остовного дерева и подробно описан предлагаемый алгоритм. Главная идея предложенного метода была основана на работе Калягина В. А., Колданова А. П., Колданова П. А., Замараева В. А. [8] и заключалась в том, что для определения статистической неопределенности минимального остовного дерева предъявляются слишком высокие требования.

Похожие статьи




Построение статистического правила для решения задачи построения MST - Анализ статистических свойств процедуры построения минимального остовного дерева

Предыдущая | Следующая