Технологические карты разработки библиотеки алгоритмов

on

\section{Метаописание временных рядов} %\author % {А.\,Н.~Фирстенко} %\email % {, } %\organization % {Москва, Вычислительный Центр РАН} %\abstract {Исследуется возможность метаописания временных рядов с целью последующей их классификации. Под метаописанием ряда понимается некоторый набор признаков, характеризующих временной ряд. В качестве метки класса для некоторого временного ряда выступает название того алгоритма из наперед заданного множества алгоритмов прогнозирования, который прогнозирует этот ряд наилучшим образом.} %\maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Введение} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Для прогнозирования временных рядов существует большое количество алгоритмов \cite{Kalaba, McNamesPhD}. Результат работы каждого алгоритма зависит от свойств прогнозируемого ряда, поэтому возникает задача автоматического выбора наилучшего алгоритма из некоторого заданного семейства. Данную задачу можно рассматривать как задачу классификации. Объектами классификации являются временные ряды. Для метаописания временного ряда создается набор признаков. В качестве признаков были использованы длина ряда, число вспомогательных рядов, максимальное и минимальное значения ряда, число пропущенных данных, среднее значение временного ряда. Метками классов являются названия алгоритмов прогнозирования. Временной ряд относится к некоторому классу, если соответствующий этому классу алгоритм работает на временном ряде наилучшим образом по заданному функционалу качества. Для классификации был использован алгоритм $k$ взвешенных ближайших соседей \cite {vorontsov}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \paragraph{Постановка задачи метоописания временных рядов.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Задано множество многомерных временных рядов $S = \{s_i\}_{i=1}^{n}$. Задано множество алгоритмов прогнозирования $A = \{a_k\}_{k=1}^{l}$. Задан функционал качества работы алгоритма $L(s,a)$. Требуется построить алгоритм классификации, который выбирает для нового временного ряда $s$ алгоритм $a_{\footnotesize\mbox {opt}}$, такой что: \[ a_{\footnotesize\mbox {opt}} = \arg \min_{a\in A} L(s,a). \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\paragraph{Описание алгоритма.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Алгоритм решения поставленной задачи. \begin{enumerate} \item Для каждого ряда $s_i \in S$ составить его признаковое описание ${\mathbf x_i} = (x_{i1},…,x_{im}) $. \item Для каждого ряда $s_i \in S$ определить метку $y_i=k$, где $a_k = \arg \min_{a\in A} L(s_i,a)$. \item Настроить классификатор по $X$, ${\mathbf y}$. \item Классифицировать $s$ по его признаковому описанию. \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \paragraph{Вычислительный эксперимент.} Был проведен вычислительный эксперимент на выборке из 120 рядов, по результатам прогнозирования их тремя алгоритмами — SSA, ARIMA, локальными методами прогнозирования. Исходные данные доступны здесь\cite{dataref}. По результатам прогнозирования каждый ряд был отнесен к классу, соответствующему алгоритму, который на данном ряде работает наилучшим образом. Было проведена 1000 экспериментов, в ходе каждого из которых выборка случайным образом делилась на тестовую и обучающую с сохранением пропорций по классам. Результаты эксперимента приведены в таблице. \begin{table} \caption{Результаты сравнения алгоритмов} \centering{\begin{tabular}{|c|lll|} \hline SSA ARIMA LOCAL \\ \hline Ряды в исходной выборке, шт. 14 49 57 \\ Ряды в обучающей выборке, шт. 4 16 19 \\ Ряды в тестовой выборке, шт. 10 33 38 \\ В среднем неправильно классифицировано, шт. 9.7 20.7 24.1 \\ \hline \end{tabular}} \end{table} %\section {Выводы} Исходя из результатов вычислительного эксперимента, можно утверждать, что для более успешного автоматического выбора алгоритмов прогнозирования требуется более тщательный выбор признаков для метаописания рядов, а также, возможно, следует использовать другие алгоритмы классификации. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\title % \section{Визуализация прогноза временных рядов} %\author % {Д.\,С.~Кононенко} %\email % {} %\organization % {Москва, кафедра Интеллектуальные системы , ФУПМ МФТИ} %\abstract {Целью данной технологической карты является описание работы функции визуализации PlotTS.} %\maketitle %\section{Описание возможностей} \begin{figure} \centering{\includegraphics{Figures/sample.eps}} \caption{Пример работы PlotTS} \label{sample} \end{figure} Реализованы следующие опции: \begin{enumerate} \item Построение графика истории временного ряда. \item Построение графика прогноза. \item Форматирование диапазонов по осям. \item Вывод легенды. \item Отображение заданного в параметрах значения функции оценки качества прогноза. \item Вывод на дополнительном графике вспомогательных временных рядов, использованных при прогнозе. \item Сохранения графика в файл. \end{enumerate} Для детального описания входных и выходных параметров функции и примеров работы см. файл PlotTS.m. Формат входных параметров стандартный, все параметры построения графика передаются в структуре plotOptions. В одной папке с файлом PlotTS.m должны лежать файлы defaultPlotOptions.mat and uniteStructures.m. В файле defaultPlotOptions.mat можно посмотреть пример задания параметров построения графика, также оттуда подгружаются параметры, не указанные пользователем. Пример выводимого графика — рис. \eqref{sample}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Стилевая правка кода} %\author % {М.\,П.~Кузнецов, А.\,А.~Морозов, Д.\,С.~Сунгуров} %[Этот необязательный аргумент задает список авторов, выводимый на печать; %он нужен только в~том случае, когда есть отличия от основного списка, например, %когда надо пронумеровать авторов и соответствующие организации: Автор~И.\,О.$^1$] % если есть грант, можно убрать следующие строчки из-под комментов %\thanks % {Работа выполнена при финансовой поддержке РФФИ, проект \No\,00-00-00000.} %\email % {mikhail., , } %\organization % {Москва, Вычислительный Центр РАН} %\abstract {Целью данной технологической карты является указание последовательности действий при проверке кода корректором и основные ошибки руководителей проектов. } %\maketitle %\section{ Порядок работы. \begin{enumerate} \item Открыть код, посмотреть основную функцию программы. В ней должно быть немного строк, вызовы некоторых процедур, связанных с подбором параметров. После просмотра функции должно стать понятно понятно, как работает алгоритм, и на какие блоки разбит. Если это непонятно, то, скорее всего, программа спроектирована криво. \item Смотреть каждую функцию, следуя логике работы программы. \item Посмотреть на входные/выходные параметры. Если выходных параметров много, это подозрение на то, что функция, скорее всего, должна быть разбита на несколько маленьких. Каждая из подфункций должна выполнять свою работу. \item Прочитать документацию и example. Из них, опять же, должно быть понятно, как будет работать функция. Если пункты 1-4 выполнены добросовестно, то это сильно облегчит дальнейшую проверку кода. \item Приступить к проверке конкретной функции. Основная задача корректора — сделать так, чтобы код стал понятным. Соответственно, если код понятен корректору сразу, скорее всего, грубых замечаний в нем не будет, и наоборот. Ниже приведены стандартные замечания, на которые следует обращать внимание при написании и проверке кода. \end{enumerate} \paragraph{Стандартные замечания} \begin{enumerate} \item Названия переменных: надо придумывать переменной название, содержащее в себе ее смысл, не боясь перегромоздить код словами. Даже если эта переменная ~— просто индекс небольшого цикла. \item В случае, когда переменная — индекс, следует приписывать ей префикс i или j , например, iFunction. Если переменная обозначает количество (размер) ч.-либо, следует приписывать ей префикс n . Например, for iFunction = 1:nFunctions \item Все операторы типа = , == , ,… следует выделять пробелами. \item Не должно быть булевских переменных с названиями типа flag . Название любого флага должно передавать его смысл. Лучше ставить префикс is , например, isFound . \item В описание всех функций надо вставлять example. \item Большую функцию всегда лучше разделить на несколько маленьких, каждая из которых выполняет конкретное действие. Если так не делать, то следует вставлять в тело функции комментарии, раскрывающие смысл каждого отдельного куска. \item Цифр в коде должно быть по минимуму, они должны выноситься в начало функции константами. Константы следует писать с большой буквы, через подчеркивание, например, NUMBER\_OF\_ELEMENTS. \item Названия структур должны начинаться с заглавной буквы. \item При перечислении аргументов функции, следует ставить пробелы после запятых: result = Function(arg1, arg2, …, argN); \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\title % [Технологическая карта по поиску временных рядов, Н.~А.~Савинов] \section{Создание базы данных многомерных временных рядов для задач прогнозирования} %\author % {Н.~А.~Савинов} %[Этот необязательный аргумент задает список авторов, выводимый на печать; %он нужен только в~том случае, когда есть отличия от основного списка, например, %когда надо пронумеровать авторов и соответствующие организации: Автор~И.\,О.$^1$] % если есть грант, можно убрать следующие строчки из-под комментов %\thanks % {Работа выполнена при финансовой поддержке РФФИ, проект \No\,00-00-00000.} %\email % {savinov.} %\organization % {Москва, Вычислительный Центр РАН} %\abstract % {Целью данной работы является объяснение принципов поиска временных рядов в Интернете. Приводится также технологический отчет о создании базы данных и средств автоматического скачивания.} %\maketitle %\section{Задача поиска временных рядов} Временные ряды бывают 2 основных типов: природные и финансово-экономические. {\itshape Требуется найти ряды обоих типов, желательно организовать автоматическое скачивание}. Наибольший объем информации можно получить от следующих информационно-финансовых систем (они являются главными мировыми поставщиками этих данных): \begin{enumerate} \item Yahoo finance \item Google finance \item Bloomberg \item Datastream Thomson Reuters \item World Bank \end{enumerate} Начинать поиск таких систем нужно хотя бы с одного крупного источника финансовой информации. Вводим google finance в Wikipedia, получаем ссылки на yahooFinance, Bloomberg, Reuter (в разделе См. Также Wiki-статьи). Это почти полный список всех крупных информационных источников в Интернете. При этом бесплатные данные предоставляют только 1, 2, 5. Для скачивания данных в этих системах выбираем индекс/акцию, historical prices, download to spreadsheet. Данные сохраняются в формате .csv. Можно организовать автоматическом скачивание, задавая соответствующий запрос в адресной строке. Также для автоматического скачивания можно использовать Matlab, в состав которого включен Datafeed Toolbox. В toolbox/datafeed/f9320.html разобран пример с подключением к базе Bloomberg (есть возможность работать с бесплатными данными через Yahoo finance). Имеется аналог UCI для временных рядов: UCR Classification/Clustering Page by Eamonn Keogh (22 ряда). Однако для скачивания оттуда требуется регистрация с указанием личных данных . Другие источники информации можно найти с помощью Google. При этом могут быть полезны следующие запросы: \begin{enumerate} \item time series db (time series database) \item time series repository \item time series download \item time series data library \item (time series) + subject area (meteorology, weather, precipitation, quakes, tide, wind, temperature, solar radiation) — природные временные ряды \end{enumerate} Однако данные, полученные из большого числа разнородных источников, могут различаться по формату и способу доступа к ним, поэтому организовать автоматическое скачивание таких рядов затруднительно. %\section{Задача создания базы данных в заданном формате} При создании системы прогнозирования важно использовать определенный формат данных, с которым будут работать все участники проекта. Поэтому необходимо {\itshape создать процедуру, приводящую ряды из формата скачивания в установленный формат} (в данном случае, формат ts). %\section{Работа технолога} %Выполнение пунктов, выделенных курсивом. После создания базы данных остальные участники проекта тестируют свои алгоритмы на этих данных, при необходимости объединяя ряды из базы, следуя стандарту хранения данных. %\section{Результаты работы технолога} %\begin{enumerate} % \item Написана программа, позволяющая скачивать ряды с Yahoo Finance по заданному в текстовом файле набору индексов (в заданном промежутке времени): % % \item Вручную собран список из 210 индексов (потому что нет открытых источников индексов на данном ресурсе): % % % \item Написана программа, приводящая ряды, скачанные с ресурса, к установленному формату ts: % % % \item В результате получены 210 многомерных временных рядов в нужном формате ts. Они загружены на Source Forge: % % % \item Создана база в формате .csv, которая включает 16 рядов из разных предметных областей. В базе находится сам ряд и описание в формате .txt. В описании есть ссылка на источник, что может быть полезно для дальнейшего поиска информации. %\end{enumerate} %\paragraph{Подробная классификация временных рядов (с примерами из базы на ML)} \paragraph{Типичные синтетические (слабозашумленные) временные ряды} \begin{itemize} \item Константа \item Синус \item 2 синуса \item Пила \item Трапеция \end{itemize} \paragraph{Высокопериодичные временные ряды} \begin{itemize} \item Потребление электроэнергии \item Работа машин и механизмов \item Звук \item Музыка \end{itemize} \paragraph{Периодичные зашумленные временные ряды} \begin{itemize} \item Цены на электроэнергию \item Цены на потребительские товары \item Объем сбыта товаров \item Цены на сахар \item Цены на хлеб \item Объем потребления напитков \item Погода: температура, влаж