ГЛАВА 10 Задача кластеризации временных рядов

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

  • нахождение финансовых показателей со сходной динамикой,
  • объединение пациентов в однородные группы по форме электрокардиограммы,
  • классификация типов активности человека по показаниям “умных часов”,
  • обнаружение домов со сходными профилями потребления электроэнергии и т.п.

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

  1. мера расстояния, описывающая степень различий между рядами;
  2. алгоритм разбиения рядов на кластеры.

Существует большое количество алгоритмов для выполнения кластеризации, но чаще всего (по крайней мере, для относительно небольших объемов данных) на практике применяют иерархическую кластеризацию, метод \(k\)–средних и разбиение по медоидам (Partition Around Medoid, PAM). При этом выделяют следующие три подхода для вычисления мер расстояния между временными рядами (Liao 2005):

  1. По исходным данным (raw data–based approach): для вычисления меры расстояния используют исходные значения анализируемых временных рядов (во временной или частотной областях). Регистрация значений сравниваемых рядов, как правило, выполнятся через одинаковые промежутки времени, однако длина этих рядов не обязательно должна быть одинаковой.
  2. По описательным признакам (feature–based approach): в рамках этого подхода сначала выполняется снижение размерности путем вложения (embedding) анализируемых временных рядов в пространство, образованное их описательными признаками (например, как это было сделано в гл. 5). Вычисление расстояния между отдельными рядами далее выполняется по значениям этих признаков.
  3. По результатам подгонки моделей: в рамках этого подхода делается предположение, что анализируемые временные ряды были порождены процессом, который можно аппроксимировать моделью с определенным набором параметров. Похожими считаются ряды с близкими значениям оцененных параметров (например, коэффициентов) такой модели. Помимо параметров модели для расчета расстояния между отдельными рядами могут использоваться также остатки - либо в исходном виде, либо после снижения их размерности подобно описанному выше второму подходу.

В литературе можно встретить несколько десятков мер расстояния, используемых в кластерном анализе. К стандартным мерам относятся евклидово расстояние, манхэттенское расстояние, расстояние Минковского и коэффициент корреляции Пирсона. В случае с временными рядами важным является также т.н. DTW–расстояние — мера, название которой происходит от лежащего в ее основе алгоритма динамической трансформации временной шкалы (Dynamic Time Warping).

Поскольку кластерный анализ принадлежит к методам обучения без учителя (unsuprevised learning), то практически невозможно сделать объективное заключение о “правильности” получаемых с его помощью решений. Как правило, на практике выбирают тот результат, который “имеет смысл” с точки зрения решаемой задачи. Тем не менее, существует целый ряд метрик, пытающихся описать качество кластеризации количественно. Это дает возможность сравнить разные решения и выбрать наиболее “оптимальное” из них, в связи с чем расчет подобных метрик качества часто является одной из стадий кластерного анализа.

По аналогии с центроидами или медоидами, получаемыми при кластеризации других объектов, полезным результатом кластеризации временных рядов является выделение т.н. “прототипов” (prototypes), т.е. наиболее представительных рядов для каждой из найденных групп. Визуализация прототипов помогает наглядно представить наиболее типичную форму временных рядов в каждом кластере. Кроме того, прототипы можно использовать для классификации, т.е. для отнесения новых временных рядов к той или иной группе. Выбор способа вычисления прототипов тесно связан с выбором меры расстояния и алгоритма кластеризации. Существует несколько таких способов, однако чаще всего используется либо простое усреднение всех рядов в кластере по каждой временной отметке, либо выбор такого временного ряда из кластера, который максимально близок (согласно выбранной мере расстояния) ко всем остальным рядам в этом кластере. Последний подход применятся в случае с упомянутой выше кластеризацией по методу PAM.

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