Fire Engine

消防士→ITエンジニア→研究者

Dynamic Time Warping（動的時間伸縮法）で時系列データをクラスタリングする

Golang データサイエンス

最近時系列データのクラスタリングに興味を持ち始めて、いくつか論文読んだり、アルゴリズムについて調べていたら、実装してみたくなったので勉強のために作ってみました。
実装の言語にはGolangを用いていて、クラスタリングのアルゴリズムは、Dynamic Time Warping（以下、DTW）とk-medoids法を組み合わせたものです。

作ったもの

github.com

tsclusterはtime series clusteringの略です。 今回は作ったのは、特定のアルゴリズムのみですが、今後興味があるアルゴリズムがあれば、ここに実装していきます。

使い方

func main() {
    var dataset [][]float64
    dataset = append(dataset, []float64{1, 1, 1, 1, 1, 1})
    dataset = append(dataset, []float64{1, 1, 1, 1, 1, 1, 1})
    dataset = append(dataset, []float64{2, 2, 2, 2, 2})
    dataset = append(dataset, []float64{2, 2, 2, 2, 2, 2, 2})

    tc := tscluster.NewTscluster(tscluster.DTW) // 引数：距離関数
    labels, err := tc.Kmedoids(dataset, 2, 20)  // 引数：データ, クラスタ数, 最大反復回数
    if err != nil {
    log.Fatal(err)
    }
    fmt.Println(labels)
}

#=>
[0 0 2 2]

いくつか補足すると、与えるデータセットの型は[][]float64であり、1次元時系列データ（[]float64）のスライスです。
また、出力結果labelsは、与えたデータセットのスライスに対してクラスタリングした結果のラベルを返しています。ラベルの値として、データが所属するクラスタのmedoids（後述するがクラスタの代表点のようなもの）のindex番号を返しています。
すなわち、[0 0 2 2] とは与えたデータセットの0番目と1番目は同じクラスタに属しており、datasetの0番目が代表点であるということです。

検証

それでは、もう少し実践的なデータで試してみます。
用いたデータとプログラムは、tsclusterのリポジトリのexamplesディレクトにおいています。
1次元の時系列データを30個用意してグラフを描いたものが、以下になります。このデータは意図的に、上昇トレンド・停滞トレンド・下降トレンドそれぞれを持つものを10個ずつプログラムで用意しました。

f:id:hirotsuru314:20190217160343p:plain

これらのデータセットをDTW + k-medoidsでクラスタリングして、クラスタごとに色分けして描いたグラフが以下になります。

f:id:hirotsuru314:20190217160405p:plain

グラフを見るとそれぞれのトレンドごとにきれいにクラスタリングできているように見えます。
今回のような単純な線形のトレンドごとにクラスターに分けるにはもっと単純な手法もありそうです。本来DTWという距離尺度を用いていると、形状は似ているけど時間軸に対してずれているといったデータの類似性が高くなるような特徴を持つため、そういったデータをクラスタリングしてみるのも良いかもしれません。

実装したアルゴリズム

時系列クラスタリングの概要を把握するには、下のサーベイ論文が非常に情報がまとまっていました。

Time-series clustering – A decade review

Dynamic Time Warping（DTW）

DTWの特徴としては、

  • 時系列のデータ長がそろっていなくても計算可能
  • 時間・位相のずれていても形状が似ていれば類似度が高くなる

などが挙げられます。
DTWについてはこちらのブログに直感的に大変わかりやすいアニメーションがあったので、見てみるとイメージが湧きやすいと思います。

データ長がmとnの時系列データのDTW距離を求めるアルゴリズムは以下のステップで構成されます。

  1. 各データ点に対して総当たりで距離を計算し、要素がデータ点同士の距離となる行列D（m × n）を作成
  2. D[0][0] からD[m][n]までに通るパスのうち、行列の要素の合計が最小となるパスを探索する。その際のパスの要素の合計がDTW距離となる

k-medoids

k-medoidsはクラスタリングの手法で大変メジャーなk-meansと非常に似た手法です。
両者の大きな違いはクラスタの代表点をcentroid（重心）ではなくmedoidを選択するという点です。
medoidとは、クラスタ内のデータ点で、同一クラスタ内の他の全ての点までの距離の総和が最小になる点のことを言います。
Wikipediaには、k-meansと比較したk-medoidsの特徴が以下のように表現されていました。

It is more robust to noise and outliers as compared to k-means because it minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances. （https://en.wikipedia.org/wiki/K-medoids より引用）

k-meansよりノイズや外れ値に強いとのことでした。また、k-medoidsはクラスタの代表点を実際のデータの中から選ぶため、一度データ同士の距離を全て計算してしまえば（距離行列を作成すれば）、k-meansのような重心の計算や重心からのデータ点までの距離の計算などといった処理がないため、計算量も少なくなると思います。

アルゴリズムとしては以下の通りです。

  1. データセットの中からk個のデータをランダムに選択する（modoid）
  2. 全てのデータを一番近いmedoidのクラスタに割り当てる
  3. それぞれのクラスタ内において、クラスタ内の他のすべての点との距離の合計が最小になる点を新たにmedoidとする
  4. 2と3を繰り返す。ただし、3においてmedoidに変化がない、もしくは指定した最大の反復回数に到達すれば終了する

さいごに

今回のようなデータのクラスタリングは教師なし学習で、データがあればすぐに適用できるというメリットはあるものの、当然ながら出てきたクラスター群に対する解釈は人間が与えないといけないですし、そもそも何個のクラスターに分けるかはある程度事前知識が必要だと思います（クラスタ数を最適化する方法はあるものの）
また何か気になるものがあれば実装してみたいと思います！

現場ですぐ使える時系列データ分析 ~データサイエンティストのための基礎知識~

現場ですぐ使える時系列データ分析 ~データサイエンティストのための基礎知識~