Как применить иерархическую кластеризацию к временным рядам

Практические руководства

Как применить иерархическую кластеризацию к временным рядам

Как кластеризовать временные ряды в python - быстрее и гибче, чем k-means!

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

В предыдущей статье я объяснил, как алгоритм кластеризации k-средних может быть адаптирован к временным рядам с помощью Dynamic Time Warping, который измеряет сходство между двумя последовательностями вместо стандартных мер, таких как евклидово расстояние.

К сожалению, алгоритм кластеризации k-средних для временных рядов может быть очень медленным!

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

Иерархическая кластеризация может создавать очень разные кластеры, чем кластеризация k-средних. В отсутствие целевых меток или «истины» трудно сказать, что один алгоритм делает кластеры «лучше», чем другой.

В этой статье я рассмотрю следующие моменты:

• Почему временные ряды требуют особого внимания
• Описание иерархической кластеризации
• Код Python для применения иерархической кластеризации к временным рядам

Зачем нужны специальные подходы к кластеризации для временных рядов?

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

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

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

Краткое описание иерархической кластеризации

Иерархическая кластеризация сначала использует матрицу расстояний. Матрица расстояний содержит расстояние между каждой парой наблюдений - в данном случае сериями.

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

Метрика несходства измеряет разницу между двумя кластерами в соответствии с расстояниями между членами кластера. Общие показатели несходства:

• Полная связь - это максимальное расстояние между наблюдениями по всем парам наблюдений в двух кластерах. В результате полная связь имеет тенденцию создавать кластеры с похожими элементами.
• Одна связь - это минимальное расстояние между наблюдениями по всем парам наблюдений в двух кластерах. Одиночная связь может создавать кластеры, содержащие разрозненные элементы.
• Средняя связь - это среднее расстояние между наблюдениями по всем парам наблюдений в двух кластерах. Средняя связь - это компромисс между сильными и слабыми сторонами методов одиночной и полной связи.
• Метод Уорда сводит к минимуму сумму квадратов внутри кластера. Он производит кластеры, подобные K-средним.

Дендрограмма

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

Иерархическая кластеризация не требует предварительного указания количества кластеров.

На дендрограмме ниже вы можете визуально определить различное количество кластеров, сдвинув горизонтальную линию отсечения вверх или вниз. Кластеры разделяются там, где горизонтальные линии пересекаются с вертикальными линиями. Например, если вы выберете порог 800, будет возвращено 2 кластера. Значение отсечки 600 дает 3 кластера.

Учебное пособие по иерархической кластеризации временных рядов

В этом руководстве мы будем использовать набор данных по мощности Италии из пакета sktime. Он содержит 1096 серий по 24 наблюдения в каждой. В целях этого упражнения по кластеризации мы проигнорируем два помеченных класса.

Быстрый взгляд на данные: каждая строка представляет собой наблюдение, которое содержит массив временных рядов в dim_0 и значение класса (игнорируемое позже) в столбце class_val.

Шаг 1. Вычислите матрицу расстояний

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

Есть несколько показателей расстояния для временных рядов, которые вы можете использовать. Здесь мы рассмотрим только два: расстояние корреляции и динамическое искажение времени.

Показатель расстояния: расстояние корреляции. Просто возьмите корреляцию между каждой парой серий как показатель расстояния.

• Серии должны быть одинаковой длины.
• Серии выровнены по фазе / временному шагу

Метрика расстояния: динамическое искажение времени. DTW - это метод измерения сходства между двумя временными последовательностями, которые не совпадают точно по времени, скорости или длине.

• Серии могут быть разной длины
• Серии могут не быть выровнены по времени

Шаг 2: Постройте матрицу связей

Пакет scipy предоставляет методы иерархической кластеризации в модуле scipy.cluster.hierarchy.

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

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

Шаг 3: Создайте кластеры

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

В этом примере я передаю матрицу связывания методу scipy.cluster.hierarchy.fcluster с параметрами, определяющими, как вы хотите назначать кластеры.

fcluster Метод выбора кластеров на основе матрицы связи довольно гибкий. Для более подробной информации и опций смотрите scipy documentation.

Последнее слово

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

Спасибо за чтение!

использованная литература

Практическая статистика для специалистов по данным Питера Брюса, Эндрю Брюса. Май 2017 г. O’Reilly Media, Inc. https://www.oreilly.com/library/view/practical-statistics-for/9781491952955/

Если вам понравилась эта статья…

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