Прогнозирование временных рядов

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

Для начала вкратце о задаче и о самом алгоритме:


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

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

image

Теперь, перейдем непосредственно к решению задачи прогнозирования методом муравьиных колоний.
Первая проблема с которой мы сталкиваемся — необходимо представить временной ряд в виде графа, на котором будем запускать муравьиный алгоритм.
Было найдено два возможных решения:
1. Представить временной ряд в виде мультиграфа где из каждой точки временного ряда можно перейти в каждую набором определенных приростов. (Для облегчения задачи будем брать нормализованные значения на промежутке от -1 до 1). Это был первый подход, который мы попробовали. Он показал неплохой результат на временных рядах малой размерности, но с увеличением размерности стала резко падать как точность прогноза, так и производительность, поэтому от этого варианта отказались.
2. Представить временной ряд в виде набора сцепленых графов, где каждый граф отвечает за свою величину прироста значения временного ряда. иначе говоря, имеем граф который отвечает за прирост -1, -0,9… и так до 1. Шаг, естественно, можно уменьшить, или увеличить, что скажется на точности прогноза и ресурсоемкости задачи.(в конечном итоге этот вариант оказался наиболее удачным.)

На этом наборе сцепленных графов, запускался муравьиный алгоритм(на каждом графе свой), который откладывал феромон на ребрах, соответствующих известным значениям временного ряда. Причем, при откладывании феромона на графе i, феромон также откладывался на графах i-1и i+1, но в гораздо меньшем количестве(в нашем случае 1/10 от базового количества феромона) таким образом, муравьи выделяли наиболее часто встречающиеся последовательности прироста значения временного ряда, а за счет откладывания феромона на смежные графы, нивелировалась возможная погрешность и изначальная зашумленность временного ряда.

Данный алгоритм мы тестировали на искусственно подготовленных временных рядах с разным уровнем периодичности и шума. Результат получился двояким. С одной стороны, при уровнях шума до 0,3 алгоритм показывает высокие результаты прогноза, сравнимые с результатами ARIMA модели. На более высоких уровнях шума возникает большой разброс результатов: прогноз то очень точный, то совершенно неправильный.

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

Спасибо всем за внимание.

Upd: Постараюсь ответить на возникшие вопросы.
Мультиграф — это граф, каждая вершина которого соединена с каждой.

Хаотические ряды, как уже писали ниже, не случайны. Вы можете посмотреть на изображения ряда Лоренца в 3-х мерном пространстве и увидите цикличность движения. Просто определить эту цикличность сложно, и на первый взгляд ряд выглядит случайным.

Значения временного ряда нормализуются на промежутке -1...1 и записываются в граф. Граф — в данном случае таблица переходов из вершины в вершину. Феромон откладывается на ребра(в ячейки таблицы).

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

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

Алгоритм тестировали, преимущественно, на ряде Лоренца.

На данный момент рано говорить о том насколько он лучше или хуже. Похоже, что алгоритм подвержен нахождению псевдопериодов и с ростом уровня шума количество ложных периодов возрастает.
С другой стороны, при удачно подборе параметров точность прогноза достаточно высокая( отклонение до 7-10 процентов, что для хаотического ряда неплохо.)

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

Спасибо за внимание.
Поделиться публикацией

Комментарии 15

    0
    А как ведет себя алгоритм на случайных временных рядах?
    Еще на сколько мне известно, то для анализа способности прогнозировать временной ряд, используется временной ряд Лоренца, часто применяемый в задачах прогноза для исследования свойств алгоритма прогнозирования. Проводились ли испытания с данный временным рядом?
      0
      Собственно для анализа хаотических временных рядов этот алгоритм и предлагается.
      На данный момент алгоритм ведет себя нестабильно(результат прогнозирования то очень точный, то совершенно неправильный), но судя по всему, это вопрос правильного подбора параметров. Сейчас мы над этим работаем.
        0
        Одной из основных характеристик хаотического процесса – это невозможность долгосрочного прогнозирования рядов. На сколько точек вы предсказываете поведения ряда?
          0
          Прогноз строится в виде графика. Точности пытаемся добиться в диапазоне 10-50 шагов. Дальше идет накопление ошибки, что естественно.
            +2
            По определению хаотическим может быть назван только тот процесс, у которого последующее значение ВООБЩЕ не связано с предыдущим. А тут каким-то магическим образом оказывается возможным прогнозирование аж на 50 шагов?!?!
            Че-то вы напутали… Либо не хаотический, а как минимум псевдослучайный (и то сомневаюсь), либо не прогнозирование, а аппроксимация (по типу МНК или плавающего среднего).
            Что-то здесь не то.
              +1
              Хаотический процесс, это как раз тот процесс, у которого связь между i+1 и i-м шагом проявляется, только такие связи накладываются друг на друга из-за чувствительности к начальным условиям(аттрактор Лоренца и т.п. — не поленитесь почитать топик «Теория хаоса» в википедии)

              Хаотические данные не стоит путать со случайными. Как раз в случайных данных никакой зависимости между значениями нету.
              Хаотические модели — фрактальны. Случайные же — обладают только определённым набором характеристик(согласно своему предполагаемому распределению)

              Как отличить хаотические данные от случайных? Об этом, кому интересно, можно почитать у Бенуа Мандельброта — "(не)послушные рынки"

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

        Что это значит? Можно было нарисовать во что превращается временной ряд. Лично я вообще не понял сути метода… Превращаем как-то ряд в граф, а потом скачем туда-сюда с помощью «приростов»? Т.е. в зависимости от чего-то выбираем нужный узел в графе?
          +2
          Согласен с предыдущем оратором, непонятна суть метода, как именно временной ряд представляется в виде графа? И еще хотелось бы узнать больше подробностей про преимущества и недостатки алгоритма. На каких данных он хорош, на каких не очень.
            –1
            Я ничего не понял из этого описания, но когда я делал делал имитацию муравьёв на графе, то у меня у каждой мурашки был параметр «вонючесть», который падал на какой-то коэффициент (не помню, что-то типа 0.9) каждый ход. Та вонючесть, которая забиралась у муравья, уходила в «вонючесть ребра», которая так же выветривалась со временем.
              –2
              Действительно очень нерациональный метод. Какие-нибудь нейронные сети и то быстрее работать будут, мне кажется.
                0
                согласен с тремя предыдущими ораторами.
                суть метода непонятна. добавьте в пост слайды.

                чему именно соответствуют вершины графа?
                точкам в пространстве значений ряда?
                  +1
                  Присоединяюсь к коллегам — принцип решения поставленный задачи муравьиным алгоритмом ускользнул и от меня.

                  Пока суд да дело, поделюсь интересной информацией насчет пометкой муравьями пути феромоном.

                  antclub.ru/lib/reznikova-zh-i/analiz-yazyka-muravev-metodami-teorii-informatsii
                  Лабиринт монтировался из спичек и укреплялся в кювете с водой для того, чтобы муравьи не могли двигаться по «прямой». В начальную точку муравьи попадали по мостику. Муравьи, находящиеся на арене, не могли видеть происходящего в лабиринте. Для того чтобы исключить маркировку пути пахучим следом, спички, по которым проходили муравьи, периодически заменяли новыми… С «перспективными» разведчиками и их группами мы работали специально в течение нескольких сеансов. Они не только сразу запоминали дорогу, но и сравнительно легко переучивались, когда в ходе одного сеанса менялось направление пути к приманке. Группы, контактировавшие с такими разведчиками, двигаясь компактно, безошибочно направлялись к приманке. Отдельные муравьи, совершавшие ложные повороты, довольно быстро догоняли остальных фуражиров. При этом члены других групп, в том числе «опытные» разведчики, попавшие на установку случайно и не знакомые с координатами кормушки в данный момент, не находили ее в случае трехи более развилок. Это позволяет исключить действие каких-либо иных механизмов ориентации, кроме дистантного наведения, т. е. использования сведений, сообщенных разведчиком.


                  Согласно работе, информация о маршруте передается от муравья к муравью неким языком, а не пометкой следа феромонами.
                    0
                    Вот ссылки на т.н. «гринвичский» ряд уровня солнечных пятен:
                    Среднемесячные значения: solarscience.msfc.nasa.gov/greenwch/sunspot_area.txt
                    Ежедневные значения: solarscience.msfc.nasa.gov/greenwch/daily_area.txt

                    Пояснения: solarscience.msfc.nasa.gov/greenwch.shtml
                    solarscience.msfc.nasa.gov/SunspotCycle.shtml

                    Отрежьте с конца кусок данных лет так за 46 (два полных солнечных цикла с небольшим запасом) и попробуйте предсказать отрезанное. Затем сравните с оригиналом.
                      0
                      После прочтения у меня возникло несколько вопросов (не буду повторять те, что были отмечены в комментариях выше)

                      1. «прирост -1, -0,9… и так до 1». Прирост у вас по сути получается дискретной величиной. Правильно я понимаю, что по идеи, из исходного ряда (по видимому действительного) вы делаете дискретный со значениями прироста (v_i — v_{i-1}). И уже потом на основе этого ряда, «хитрым способом» получаете граф.

                      2. Чем этот метод лучше, по сравнению с другими известными способами, например, разными регрессиями или марковскими цепями.

                      3. «Данный алгоритм мы тестировали на искусственно подготовленных временных рядах с разным уровнем периодичности и шума». Не могли бы вы подробнее рассказать какие вы генерировали тестовые данные, шум с какими характеристиками использовали и т.д.?
                      • НЛО прилетело и опубликовало эту надпись здесь

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое