Python
ruptures
変化点検出

オフライン変化点検出の概要とPythonライブラリ"ruptures"の紹介

はじめに

時系列データにおいて、変化が生じた点を検出する「変化点検出」について備忘録としてまとめておきます。(ほぼ参考文献のまとめです)
また、ruptures というオフライン変化点検出のPythonパッケージがあったのでその紹介もします。(コードはrupturesのドキュメントを参考にしてください)

以下では分析したいデータがすでにある状態で後から変化点を検出するオフライン変化点検出について説明します。
(オンライン変化点検出はここでは扱いません。良さそうなライブラリがあれば教えてください…)

変化点検出の概要

変化点検出は以下の3つの要素で構成されています。

  • 損失関数
  • 探索方法
  • 変化点数が分かっているか

損失関数

何らかの基準を設定し、その基準と実測値との誤差が最小になる点を変化点とみなします。オフラインの変化点検出では基本的にすべての時点について誤差を求めていきます。

  • 黒:実測データ
  • 赤:損失関数での基準値
  • 青:分割点(変化点の候補) changegraph.png
  1. ある時点で分割する。(図の青線)
  2. ある時点の前後それぞれの範囲で誤差(図の赤線と黒線の差)を求め、合計する
  3. 2を繰り返し、全時点での誤差を求める(図の青線を左から右へ移動させるイメージです)
  4. 誤差が最小の点を変化点とする

主な損失関数の種類

  • L1
    • 中央値(もしくは平均値)と各実測データの差の絶対値の和
  • L2
    • 平均値と各実測データの差の二乗和
  • 直線回帰
    • 線形回帰モデルを立てて、その予測値と各実測データの差の二乗和
  • AR
    • 自己回帰モデルを立てて、その予測値と各実測データの差の二乗和

そのほかにもノンパラメトリックな方法や、複数データを一度に見るときにより適した方法などもあります(理解できていないのでここでは示しません…)

探索方法

最終的には全期間を対象としますが、誤差を求める範囲や方法はいくつか種類があります。

主な探索方法の種類

  • 2分岐
    • 誤差が最小の部分を第一の変化点とする。
    • さらに変化点が必要であれば、分割後の各範囲で誤差を求めていく。 BinarySeg 引用:ruptures: Binary segmentation
  • 力技
    • 全部の組み合わせを計算する。
  • Window

ほかにも剪定していく方法や、Windowとは逆に分割してから統合するBottom-upという方法もあります。

変化点数が分かっているか

変化点の数が分かっている/いないによって変化点とする方法を変えます。

  • 変化点数が分かっている場合や決めている場合
    • 変化点とするものを決めた個数まで計算します
  • 変化点の数が分かっていない場合
    • 閾値を設け、閾値を超えた点をすべて変化点とします

ruptures

オフライン変化点検出のパッケージはRを中心に存在しますが、用いることができる損失関数・探索方法・変化点数は決められたものしかありませんでした。

しかし、Pythonライブラリであるrupturesを使えば様々な種類の損失関数や探索方法を自由に組み合わせられることができます。
また、デフォルトで用意されている損失関数以外にも使いたいという場合はカスタムの損失関数を設定することもできるようです。

おおまかな流れ

  • データを読み込む(1次元でも多次元でも)
    • 適当なデータがなければrupturespw_constantで作ることもできます
  • 損失関数と探索方法を選ぶ
    • 損失関数としてARを選択する場合などはさかのぼる期間も指定
  • 計算する
    • 変化点数や閾値など指定するパラメーターがある場合は指定する
  • 結果を表示する
    • matplotlibで表示させたり、変化点の位置を表示させたり

コードについては、非常に理解しやすい&特に工夫することもないのでrupturesのドキュメントを参考にしてください。

さいごに

間違いがあるかと思いますので、ぜひ指摘してください。

参考

ruptures

その他