Материал из MachineLearning.

Версия 17:01, 16 октября 2011

Построение экспериментального стенда для исследования задачи классификации временных рядов с целью повышения качества прогнозирования

Введение

Временной ряд — это собранный в разные моменты времени статистический материал о значении каких-либо параметров. Временные ряды являются одиним из самых важных объектов в области машинного обучения. Прогнозирование временных рядов широко используется в самых разных областях человеческой деятельности.

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

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

Постановка задачи

Главная цель исследования — повысить качество прогнозирования временных рядов. Имеется алгоритм или композиция алгоритмов для прогнозирования временных рядов. Ряды имеют экономическую природу, поэтому у них довольно много характерных особенностей: недельная, месячная и годовая сезонность, обычно выделяется тренд. Данные сильно зашумлены, и имеют много пропусков.

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

На вход классификатору подаются два множества: временные ряды в общем случае произвольной длины и алгоритмы прогнозирования. Рядов имеется порядка ста, алгоритмов порядка тридцати. На выходе классификатор определяет, какие модели лучше подходят для прогнозирования этих рядов, или дает отказ от классификации. Исследуемые объекты — временные ряды — случайно разбиваются на два множества: обучение и контроль. Для того чтобы сформировать на обучающей выборке вектор из правильных ответов, полным перебором ищется алгоритм из семейства на входе с наилучшим качеством прогнозирования. Но поступить таким же образом с конрольной выборкой нельзя, потому что время работы основного алгоритма прогнозирования, в который впоследствии будет интегрирован разрабатываемый модуль, будет неприемлемо большим. Для сокращения времени работы формируется признаковое пространство, на основе которого проводится классификация.

Актуальность

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

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

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

Описание работы классификатора

Входные данные: временные ряды

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

Пример временных рядов с недельной пилообразной сезонностью и полиномиальным трендом и без тренда, но с недельной сезонностью.

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

Входные данные: алгоритмы прогнозирования

Исследуемые алгоритмы загружаются в классификатор из отдельного файла, где они хранятся в виде массива структур. Для каждой модели прогнозирования, например, Тейла-Вейджа, экспоненциального среднего, Брауна, могут быть несколько алгоритмов классификации, различающихся только параметрами. Первичная информация об алгоритмах (имя, параметры, указатель на функцию и количество) хранится в структуре AlgList:

AlgList =
    name: {'My_Exp'  'My_Exp'  'My_Holt'}
    param: {[1x1 struct]  [1x1 struct]  [1x1 struct]}
    hand: {[@(x,y)My_Exp(x,y)]  [@(x,y)My_Exp(x,y)]   [@(x,y)My_Holt(x,y)]}
    amount: 3

Для каждого алгоритма и для каждого временного ряда строится матрица оценок качества прогнозирования алгоритмов на исходных временных рядах. Качество прогнозирования рассчитывается двумя способами: как средний модуль отклонения и как среднее квадратичное отклонение от истинного значения.

Обучение и классификация

Из рядов случайным образом формируется обучающая и контрольная выборка. Для обучающей выборки правильная метка — номер наиболее удачного алгоритма — рассчитывается по матрице оценок, для каждой строки ищется минимум ошибок относительно выбранного функционала качества:

[~, Classes.classif(train)] = min(Quality(train, :), [], 2);

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

Сезонность выделялась непараметрически. Будем считать, что исходный ряд можно представить y(t) = x(t) + s(t), где x – тренд, а s – сезонность. Сезонность на каждом периоде характеризуется логичными допущениями, что значения на концах периода совпадают, а интеграл по периоду равен 0. Тогда если каким-то образом удастся выделить сезонность, тренд получится ее вычитанием из исходного ряда с возможным сглаживанием впоследствии. Пусть имеются измерения на каждом из периодов. Введем оценочную функцию, определенную на том же множестве, что и наш временной ряд. В каждой точке она равна экспоненциальному среднему из имеющихся значений ряда для аналогичных сдвигов относительно периода (так как в ряде могут быть пропуски, суммировать будем только то, что есть). Вторая производная этой функции совпадает со второй производной прогнозируемой сезонности, поэтому s(t) есть сумма введенной функции и еще двух слагаемых a+b*t, где a и b — константы. Найти их можно из определения сезонности, данного выше. Единственный параметр алгоритма — константа регуляризации, как и в экспоненциальном сглаживании показывает значимость измерений, лежащих в соседних слева и справа периодах.

Сравнительная оценка качества классификаторов

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

Самый простой путь решения — в спорных ситуациях использовать один и тот же универсальный алгоритм, например, экспоненциально среднее. Но во многих случаях его усовершенствования, такие как модель Хольта и прочие, будут работать гораздо лучше, что подтверждается экспериментами.

Другой путь решения — выбирать нужный алгоритм, сравнивая качество классификации с остальными алгоритмами. В реальности использовать такой алгоритм возможности нет, но для того, чтобы оценить, дает ли построенный классификтор какие-то приемущества перед одной фиксированной моделью, может быть полезен. Метки, которые раздает такой «идеальный» классификатор, получаются из уже найденной матрицы оценок взятием минимума по строкам. Также модель можно выбирать по скользящему контролю.

Последняя модель для сравнения — созданный классификатор.

Поскольку каждая из моделей может давать очень хорошие результаты на каком-то классе рядов и очень плохие на других, логично для каждой модели брать среднее по всем функциям потерь на контрольной выборке. Сейчас для подсчета объективной оценки средней ошибки сравниваемых моделей бралось среднее арифметическое, но в общем случае это может быть и более сложная конструкция.

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

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

В программе для каждой модели хранится вектор для ее классификации Classes и вектор функций потерь Res:

   classif: [50x1 double]
     apost: [50x1 double]
    onealg: [50x1 double]
    crossv: [50x1 double]

Заключение

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

Было изучено поведение многих адаптивные модели для краткосрочного прогнозирования, написаны реализации этих моделей. На модельных данных сравнивалось качество прогнозирования при разной степени зашумления, при данных, не соответствующих модели.

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

Список литературы

1. Лукашин Ю. П., Адаптивные методы краткосрочного прогнозирования временных рядов
2. Губанов В. А., Непараметрическое выделение динамических сезонных циклов
3. Цыплаков А. А., Основы прогнозирования временных рядов