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

Обнаружение точки изменения (или CPD) обнаруживает резкие сдвиги в тенденциях временных рядов (т. Е. Сдвиги в мгновенных скоростях временного ряда), которые можно легко идентифицировать с помощью человеческого глаза, но их труднее определить с помощью традиционных статистических подходов. НПР применяется во многих отраслях, включая финансы, контроль качества производства, энергетику, медицинскую диагностику и анализ человеческой деятельности.

CPD отлично подходит для следующих случаев использования:

  1. Обнаружение аномальных последовательностей / состояний во временном ряду
  2. Определение средней скорости уникальных состояний во временном ряду
  3. Обнаружение внезапного изменения состояния временного ряда в реальном времени

Я считаю, что CPD особенно полезен при автоматизации процесса выявления и удаления аномальных последовательностей из временных рядов, как показано ниже:

Также замечательно, если я пытаюсь определить изменение скорости в системе, что позволяет мне сосредоточиться на средних скоростях в аналогичных последовательностях:

В этой статье содержится краткая и понятная информация об обнаружении точки изменения с пакетами для практической реализации на Python (включая пример кода!).

История алгоритма

Есть две разные категории CPD - офлайн и онлайн. В этом разделе я дам краткий обзор обоих.

Обнаружение точки изменения офлайн

Подходы к обнаружению точек изменения являются «автономными», когда они не используют данные потоковой передачи в реальном времени, и требуют полного временного ряда для статистического анализа. Поскольку автономные подходы анализируют весь временной ряд, они обычно более точны. Ниже приведены некоторые характеристики обнаружения точки изменения в автономном режиме (1):

  1. Все данные принимаются и обрабатываются одновременно
  2. Интересны все изменения, а не только самое последнее изменение в последовательности.

Обнаружение точки изменения в Интернете

В отличие от определения точки изменения в автономном режиме, обнаружение точки изменения в режиме онлайн используется во временных рядах потоковой передачи в реальном времени, обычно для целей постоянного мониторинга или немедленного обнаружения аномалий (1). Online CPD обрабатывает отдельные точки данных по мере их появления с целью обнаружения изменений состояния, как только они происходят (2). Есть несколько характеристик обнаружения точки онлайн-изменения:

  1. Быстрая обработка «на лету» для быстрой оценки сдвигов в тренде временных рядов
  2. Оценка только самого последнего изменения во временном ряду, а не предыдущих изменений

Пакеты Python для обнаружения точки изменения

В R есть отличный пакет для обнаружения точек изменения, называемый changepoint. Этот пакет позволяет пользователям использовать несколько методов поиска для выполнения анализа точек изменения временного ряда. К сожалению, нет прямого эквивалента Python пакета changepoint для R. Однако есть несколько других пакетов, которые предлагают обнаружение точки изменения, доступное через Python:

  1. Ruptures package, библиотека Python для определения точки изменения в автономном режиме.
  2. Вызов пакета R changepoint в Python с использованием пакета rpy2, интерфейса R-to-Python
  3. Пакет changefinder, библиотека Python для онлайн-обнаружения точек изменения

Из трех вариантов я считаю варианты №1 и №3 наиболее простыми для реализации, поскольку они не требуют загрузки и настройки R и rpy2 в среде Python. Функциональность пакета R changepoint на сегодняшний день является наиболее надежной, но его настройка требует много времени. Следовательно, в этом посте он не рассматривается.

Если вас интересуют более подробные сведения о вызове пакета R changepoint через Python с использованием rpy2, ознакомьтесь с этим руководством Стивена Рейтсма.

Давайте подробнее рассмотрим варианты №1 и №3.

Пакет разрывов

Чарльз Труонг адаптировал пакет разрывов из пакета R changepoint. В нем особое внимание уделяется обнаружению точек изменения в автономном режиме, когда анализируется вся последовательность. Из всех вариантов точки изменения Python он лучше всего документирован. Мы можем установить его, используя базовую команду установки pip:

pip install ruptures

Пакет предлагает множество методов поиска (двоичная сегментация, Pelt, обнаружение изменений на основе окон, динамическое программирование и т. Д.), А также несколько функций стоимости, с которыми можно поиграть. В этом руководстве мы уделяем особое внимание методам поиска.

Фон метода поиска

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

Метод поиска с сокращенным точным линейным временем (PELT). Метод PELT - это точный метод, который обычно дает быстрые и последовательные результаты. Он обнаруживает точки изменения за счет минимизации затрат (4). Вычислительная стоимость алгоритма составляет O (n), где n - количество точек данных (4). Для получения дополнительной информации о методе PELT ознакомьтесь с этой статьей.

Метод поиска динамического программирования:. Это точный метод, требующий значительных вычислительных затрат O (Qn²), где Q - максимальное количество точек изменения, а n - количество точек данных (4) . Более подробную информацию о методе поиска динамического программирования можно найти в этой статье.

Метод бинарной сегментации поиска: этот метод, пожалуй, самый распространенный в литературе (4). Двоичная сегментация - это приближенный метод с эффективными вычислительными затратами O (n log n), где n - количество точек данных (4). Алгоритм работает путем итеративного применения метода единственной точки изменения ко всей последовательности, чтобы определить, существует ли разделение. Если обнаружено расщепление, то последовательность разделяется на две подпоследовательности (5). Затем тот же процесс применяется к обеим подпоследовательностям и так далее (5). Для получения дополнительной информации о бинарной сегментации ознакомьтесь с этой статьей.

Метод поиска на основе окна. Это относительно простой приблизительный метод поиска. Метод поиска на основе окон вычисляет расхождение между двумя соседними окнами, которые движутся вместе с сигналом y (6). Когда два окна сильно различаются, возникает большое расхождение между двумя значениями, что указывает на точку изменения (6). После построения кривой невязки алгоритм находит оптимальные индексы точек изменения в последовательности (6). Более подробную информацию о методе оконного поиска можно найти в этой статье.

Пример кода

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

def retrieve_time_series(api, series_ID):
    """
    Return the time series dataframe, 
    based on API and unique Series   ID
    api: API that we're connected to
    series_ID: string. Name of the series that we want 
    to pull from the EIA API
    """
    #Retrieve Data By Series ID 
    series_search = api.data_by_series(series=series_ID)
    ##Create a pandas dataframe from the retrieved time series
    df = pd.DataFrame(series_search)
    return df

"""
Execution in main block
"""
#Create EIA API using your specific API key
api_key = 'YOUR API KEY HERE'
api = eia.API(api_key)
    
#Pull the oil WTI price data
series_ID='PET.RWTC.D'
price_df=retrieve_time_series(api, series_ID)
price_df.reset_index(level=0, inplace=True)
#Rename the columns for easier analysis
price_df.rename(columns={'index':'Date',
            price_df.columns[1]:'WTI_Price'}, 
            inplace=True)
#Format the 'Date' column 
price_df['Date']=price_df['Date'].astype(str).str[:-3]
#Convert the Date column into a date object
price_df['Date']=pd.to_datetime(price_df['Date'], format='%Y %m%d')
#Subset to only include data going back to 2014
price_df=price_df[(price_df['Date']>='2014-01-01')]
#Convert the time series values to a numpy 1D array
points=np.array(price_df['WTI_Price'])
    
#RUPTURES PACKAGE
#Changepoint detection with the Pelt search method
model="rbf"
algo = rpt.Pelt(model=model).fit(points)
result = algo.predict(pen=10)
rpt.display(points, result, figsize=(10, 6))
plt.title('Change Point Detection: Pelt Search Method')
plt.show()  
    
#Changepoint detection with the Binary Segmentation search method
model = "l2"  
algo = rpt.Binseg(model=model).fit(points)
my_bkps = algo.predict(n_bkps=10)
# show results
rpt.show.display(points, my_bkps, figsize=(10, 6))
plt.title('Change Point Detection: Binary Segmentation Search Method')
plt.show()
    
#Changepoint detection with window-based search method
model = "l2"  
algo = rpt.Window(width=40, model=model).fit(points)
my_bkps = algo.predict(n_bkps=10)
rpt.show.display(points, my_bkps, figsize=(10, 6))
plt.title('Change Point Detection: Window-Based Search Method')
plt.show()
    
#Changepoint detection with dynamic programming search method
model = "l1"  
algo = rpt.Dynp(model=model, min_size=3, jump=5).fit(points)
my_bkps = algo.predict(n_bkps=10)
rpt.show.display(points, my_bkps, figsize=(10, 6))
plt.title('Change Point Detection: Dynamic Programming Search Method')
plt.show()

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

Пакет changefinder

Пакет changefinder специально предназначен для онлайн-обнаружения точек изменения. Чтобы выполнить обнаружение точки изменения, пакет использует моделирование SDAR или моделирование временных рядов авторегрессии с последовательным дисконтом. SDAR - это именно то, на что это похоже - это расширение авторегрессионного (AR) моделирования, при котором более старые точки данных в последовательности «обесцениваются», т. Е. Менее важны, чем более свежие значения в последовательности. Поскольку последние данные имеют больший вес в модели SDAR, SDAR хорошо подходит для обнаружения точки изменения в режиме онлайн, которая фокусируется на обнаружении самых последних изменений в последовательности.

Авторегрессионное моделирование (AR) - одна из самых популярных форм моделирования временных рядов, где текущее значение прогнозируется на основе предыдущих значений в последовательности (3). Для получения дополнительной информации о моделях SDAR (а также многомерных моделях SDVAR) ознакомьтесь с этой статьей.

Пример кода

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

В этом примере мы собираемся автоматически сгенерировать данные с помощью пакетов random () и numpy ():

#Create a synthetic data set to test against
points=np.concatenate([np.random.rand(100)+5,
                       np.random.rand(100)+10,
                       np.random.rand(100)+5])

После того, как мы сгенерировали некоторые синтетические данные, мы обрабатываем данные с помощью функции ChangeFinder и генерируем оценку аномалии на основе SDAR для каждой точки данных:

#CHANGEFINDER PACKAGE
f, (ax1, ax2) = plt.subplots(2, 1)
f.subplots_adjust(hspace=0.4)
ax1.plot(points)
ax1.set_title("data point")
#Initiate changefinder function
cf = changefinder.ChangeFinder()
scores = [cf.update(p) for p in points]
ax2.plot(scores)
ax2.set_title("anomaly score")
plt.show()

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

На этом я завершаю свое краткое введение в определение точки изменения. Чтобы получить доступ к коду, который я использую в этом руководстве, ознакомьтесь с моим репозиторием на Github.

Как всегда, спасибо за чтение!

Ознакомьтесь с некоторыми из моих других статей и руководств по науке о данных:



Использование машинного обучения для прогнозирования наилучшего времени для продажи электроэнергии обратно в сеть - Tech Rando
С появлением новых технологий в отраслях возобновляемых источников энергии и хранения энергии появляется много новых возможности для… techrando.com





Анализ данных временных рядов цен на электроэнергию с помощью Python: декомпозиция временных рядов и цена…
Добро пожаловать в блог Tech Rando! В сегодняшнем посте я собираюсь перейти к использованию API Управления энергетической информации… techrando.com



Источники

  1. Киллик, Ребекка. 2017. Введение в оптимальные алгоритмы обнаружения точек изменения. Http://members.cbio.mines-paristech.fr/~thocking/change-tutorial/RK-CptWorkshop.html
  2. Аминихангахи, Самане и Кук, Дайан. Май 2017 г. Обзор методов обнаружения точек изменения временных рядов. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5464762/#R7
  3. Саид, Фатима; Нур, Дарфиана; Король, Роберт. 2012. Обнаружение точек изменения векторной авторегрессионной модели с использованием алгоритма SDVAR. https://pdfs.semanticscholar.org/c56d/4adad7ed3f504015bc6bbc663e21e55f174b.pdf
  4. Вамбуи, Гачомо Доркас; Вайтиту, Гичуи Энтони; Ванджоя, Энтони. Декабрь 2015. Тест мощности сокращенного точного линейного времени (PELT) в обнаружении множественных точек изменения. https://pdfs.semanticscholar.org/a7bc/09b7a73dc96be7cf844978014ad13cf0475a.pdf?_ga=2.100774593.1133001833.1565582238-1351709189.1562946956
  5. Рорбек, Кристиан. Обнаружение изменений дисперсии с помощью двоичной сегментации и оптимального разделения. Https://www.lancaster.ac.uk/pg/rohrbeck/ResearchTopicI.pdf
  6. Чыонг, Чарльз; Удре, Лоран; Ваятис, Николас. Январь 2019. Выборочный обзор методов определения автономных точек изменения. https://arxiv.org/pdf/1801.00718.pdf

Первоначально опубликовано на https://techrando.com 14 августа 2019 г.