最近ある時系列データの因果関係が分析できればと、手始めに時系列データの相関解析やクラスタリングの手法を調査しています。

今回は、時系列データクラスタリング手法の動向と、2015年に論文が発表された正規化相互相関手法を用いた形状ベース(Shape-based)の時系列クラスタリング手法であるk-Shape[3]についてまとめてみます。

Table of Contents

クラスタリングとは？

クラスタリングとは、対象となるグループに対する高度な知識がなくとも、類似のデータを関連するグループや同種のグループに分割するデータマイニングの手法です。クラスタリングは、科学的データの探査、情報検索とテキストマイニング、CRMやマーケティング、医療診断などの、データマイニングの手法として実用的に用いられています [1]。

研究的な観点からも、クラスタリングは、統計、パターン認識、機械学習などの分野で、現在も活発に研究されています。機械学習的な観点では、クラスタリングは一般的には教師なし学習であり、クラスタリングは、多様な属性を持つ膨大なデータセットを分類したり、潜在するパターンの発見に役立ちます[1] [2]。

k-meansとは

k-means(k-平均法)は、現在、科学および産業分野で最も広く使用されているクラスタリングアルゴリズムです。名称は、クラスタの平均（または加重平均）を用いてk個のクラスタに分類する手法に由来しています[3]。

クラスタリングにおいて、すべての可能な組み合わせを確認することは計算上実行不可能(NP困難)な問題です。k-meansは、貪欲法的に局所的最適解を求めて、それを反復して最適化する手法です。

具体的には、k-meansは対象データを表す点を、最初にランダムにk個のクラスタに割り当てます。各クラスタに含まれる点の平均を計算した後に、各クラスタのメンバーが不変になるまで、以下の2つのステップを反復して実行します。

STEP1 : 各対象データを、その重心に最も近い重心のクラスタに移動
STEP2 : 各クラスタの平均を再計算

反復による最適化は、各クラスタのメンバーに移動がなくなり収束した場合、または最大反復回数に達した場合に終了します。

時系列クラスタリングとは

クラスタリングの手法は、時系列データの解析にも用いられており、主に時系列データセット内の潜在的、興味深いパターンの発見に利用されます。解析事例としては、株価などの時系列間の相関検出、天気予報などの関数近似と組み合わせた予測、店舗などのアイテム間の関連性の検出などがあります [2]。

時系列クラスタリングの手法

時系列クラスタリング手法を大別すると、モデルベース(Model-based)、特徴ベース(Feature-based)、形状(Shape-based)ベース手法および、その組み合わせの手法に大別されます。以下の図に、各手法に用いられるコンポーネントを示します [2]。

モデルベース(Model-based)

モデルベースの手法は、時系列データを対象のモデルデータのパラメータに変換し、モデルで定義されている距離関数および(通常は従来の)クラスタリングアルゴリズムにを用いています。一般的に、モデルベースの手法はクラスタが接近している場合に性能が劣化するなど、スケーラビリティの問題が指摘されています [2]。

特徴ベース(Feature-based)

特徴ベースの手法は、時系列データが低次元の特徴ベクトルに変換され、、従来のクラスタリングアルゴリズムが適用されます。一般的に特徴ベクトルは正規化されており、ユークリッド距離などを用いたクラスタリング手法が用いられます [2]。

形状(Shape-based)ベース

先の２つの手法と異なり、形状(Shape-based)ベースは元の時系列データと形状的特徴と直接的に連動しているため、RAWデータベースのアプローチとも呼ばれます。形状ベースのクラスタリングアルゴリズムは、従来の静的データに用いられるクラスタリングアリゴリズムが用いられますが、その距離や類似度を測定する、時系列に適した様々な関数が提案されています [2]。

k-Shapeとは?

k-Shape[3]は、時系列データの分析とマイニングを目的に、2015年に発表された形状(Shape-based)ベースの時系列クラスタリングアルゴリズムです。k-Shapeは、汎用的な時系列データクラスタリングアルゴリズムとして、従来手法と比較しても精度が良く、その最適化処理でも性能が劣化しにくい手法として提案されています。

k-Shapeは、端的に言えば、時系列データを対象とした形状(Shape-based)ベースのクラスタリング手法であり、k-meansとおなじく反復してクラスタを最適化する手法となります。以下に、k-Shapeの主要となる提案をピックアップしてみます。

距離測定 - Shape-based distance (SBD)

k-Shapeの距離関数はShape-based distance (SBD)と名付けられ、2つの時系列データの相関関係の最大値も用います。現在主流となる時系列データ比較手法であるDTW(Dynamic Time Warping)[4]系のアルゴリズムではなく、以下の式に示す画像認識にも用いられる正規化相互相関手法であるNCC(Normalized Cross-Correlation)[5]ベースの手法を用いて距離を測定しているのが特徴的なアルゴリズムです。

時系列データでは、比較する時系列データの位相が異なったり(Shift invariance)、その時間軸の長さが異なったりする場合がありますが(Uniform scaling invariance)、k-Shapeではそれらを補正し、スケーリングの相違についてはz正規化(z-normalize)した上で相関関係の距離をしています。

形状抽出 - 最小二乗距離による重心計算

時系列クラスタの類似性には、(k-meansで用いられる)単純な算術平均の重心ではなく、k-Shapeでは他のすべての時系列データに対する最小二乗距離による重心計算が用いられています。k-Shapeの重心計算と、従来の算術平均を比べたものが以下の図となります。

青線の算術平均では特徴が丸め込まれていますが、k-Shapeの重心計算が効果的に各クラスの特徴が取り込めているのが分かります。

クラスタリング - 反復による最適化

k-Shapeのクラスタリングは、k-meansと同じく反復による最適化によるクラスタリング手法を用います。k-Shapeは、k-meansと同じく、指定されたk個のクラスターに、対象の時系列集合をランダムに各クラスタに割り当てます。その後、k-Shapeは以下の2つのSTEPを繰り返し実行します。

STEP1 : 各時系列データを、その重心に最も近い重心のクラスタに移動
STEP2 : 各クラスタの重心を再計算

繰り返しは、k-meansと同じく、時系列割り当ての更新が発生せずに収束した場合、または規定されている最大反復関数に達するまで実行されます。

k-Shapeを試す - tslearn

k-Shapeの論文では、UCR(University of California, Riverside)から公開されている全時系列データサンプル[6]を用いて、先行研究との比較をしています。

その評価結果によると、k-Shapeアルゴリズムは前述のDTW系の既存の主流である時系列データクラスタリングアルゴリズムと精度的には遜色なく、高速かつ反復処理による性能劣化が少ない、新しい時系列クラスタリングアルゴリズムとして結論づけられています。

tslearnとは

tslearn[7]は、機械学習による時系列分析のためのPythonパッケージです。 tslernは、前回紹介した形状ベース(Shape-based)時系列クラスタリングのアルゴリズムである、k-Shape[3]の他にも、色々な時系列の分析アルゴリズムが網羅されています。

今回はtslearnを用いて、k-Shapeアルゴリズムを評価してみました。このパッケージは、scikit-learnをベースとしているため、一般的な機械学習パッケージの知識があれば、k-Shapeアルゴリズムを簡単に評価できます。

セットアップ

評価前の準備方法については、tslearnの公式ドキュメント[7]に記載されている通りです。自分の環境では、以下のコマンドにある通り、PyPIでセットアップを用いました。

 pip install --user tslearn

基本的にはUbuntuメインでの評価を実施しましたが、その他、MacOSX/CentOSのPython標準の2.7系でも問題なく評価ができました。

データセットの準備

tsleanは、3次元テンソルの時系列データセットを分析の対象としているため、まずはk-Shapeで解析の対象となる時系列のデータセットを準備します。具体的には、numpy.ndarrayとしての時系列データセットの準備が必要ですが、元データをfloat型の2次元配列として保持している場合には、tslearn.utilsにあるto_time_series_dataset()を用いるのが簡便でしょう。

from tslearn.utils import to_time_series_dataset

ts_rawdata = [[10, 20,30], [100, 400, 300]]
ts_dataset = to_time_series_dataset(ts_rawdata)

to_time_series_dataset()は、標準ではfloat型の2次元配列が対象ですが、任意の型の指定も可能です。また、ソースコードの注釈などを確認すると入力時系列データの欠損も補完してくれるようですが、元データはあらかじめ整形しておくのが無難です。

時系列データの分析

評価対象の時系列データセットの準備ができたのであれば、あとはtsleanのKShapeクラスを用いて、以下のように実行するだけです。

from tslearn.clustering import KShape

ks = KShape(n_clusters=10)
rs = ks.fit_predict(ts_dataset)

上記の例では、KShapeのコンストラクタにはクラスタ数のみを指定していますが、最大反復数などその他の指定できる引き数については、公式ドキュメントを確認して下さい。

また、KShape::fit_predict()はクラリタリングの結果を、1次元のfloat配列として返却します。一般的にはその結果をintに変換すれば、目的となるクラスタリング結果が得られます。

k-Shapeを試してみて

今回、k-Shapeの論文を紹介したのは、ある時系列データの因果関係を解析してみようというのが動機でした。ただし、実際にその時系列データをk-Shapeによりクラスタリングしてみたものの、論文に記載されているような結果を得るのは難しい印象を持ちました。

色々試行錯誤する中で、試しに、単純なDTW系のアルゴリズムを実装し比較してみたところ、自分の時系列データ的には、明らかにDTW系のほうが良い結果が得られる感触です。

原因として推測されるのは、k-Shapeの論文で用いられているUCR時系列データ[6]が、自分の対象となる時系列データセットより1桁規模が小さいのと、論文での評価が平均値のみの言及であるため、実際にはUCR時系列データの範囲内でも、得手不得手があるのかもしれません。

また、k-Shape論文とおなじく、自分も初期のクラスタ割り当てはランダム割当での評価でした。k-means系では初期値のクラスタ割り当てに関する論文もあり、実務的にはtslearnで初期割り当てを明示するなど、いろいろ工夫できる余地はありそうです。

k-Shapeのアプローチによる改善については、機会があれば今後試してみたいと思っています。

時系列データクラスタリングとk-Shape