最近、時系列データのクラスタリングに興味を持っているので、k-Shapeというクラスタリング手法に関する論文を読みました。
なぜ興味を持っているかというと、サーバの各種メトリクス（CPU使用率・メモリ使用率など）を使って、似たような特徴を持っているサーバ群をクラスタリングできないかと考えいるためです。例えば、負荷の高いサーバ群と負荷の低いサーバ群などにグルーピングできると、面白いのではないかと考えています。
元論文はこちらです。
k-Shape: Efficient and Accurate Clustering of Time Series
この論文では、提案するk-Shapeのアルゴリズムの説明だけでなく、時系列データをクラスタリングする上での理論的な背景から説明されていて、時系列クラスタリング手法の全体像を把握するのに大変良い論文でした。
- 概要
- Time-Series Invariances
- Time-Series Distance Measures
- Shape-based distance（SBD）
- Shape-based Time-Series Clustering
- 感想
概要
本論文では、k-Shapeという時系列クラスタリング手法を提案しています。
k-Shapeの特徴は、
- 時系列データの形状に着目したshape-basedクラスタリングである
- データ間の距離尺度として、規格化した相互相関を用いている
- 高効率かつ高精度で、幅広いデータに適用できる
などが挙げられます。
以下、本論文の内容をまとめていきますが、理論の詳細に関しては、論文をご参照ください。
Time-Series Invariances
時系列データをクラスタリングする際には、何に着目してクラスタリングするか（何をもって似ているとするのか）というのが重要になります。
例えば、形状は似ているけど、時間軸に対してずれている2つの時系列を同一クラスと捉えるかどうかは、そのときの用途によって異なると思います。
k-Shapeの場合、ScalingとShiftingに対する不変性 (Invariances)に着目しています。
簡単に言うと、Scalingは軸に対してスケールした際にデータ同士の性質が似ているかどうか、Shiftingは時間軸（位相）に対してずらした場合にデータ同士の性質が似ているかどうかに着目しており、この特徴からk-Shapeはデータの形状に着目したshape-basedなクラスタリングであるとされています。
Time-Series Distance Measures
クラスタリングを行う際に、データ間の類似性は距離として表現されます。すなわち、距離が近いほど類似性が高く、距離が遠いほど類似性は低いということです。
このことから、前述の「何を持って似ているとするか」は、データ間の距離をどのように定義するかに強く依存するため、距離尺度の定義が極めて重要となってきます。論文中でも距離をどうやって決めるかが、クラスタリングのアルゴリズム自体より重要だと述べらていました。
時系列データの「形状」に着目したクラスタリングをするには、振幅と位相のずれをうまく扱う距離尺度が必要となります。
k-Shapeでは、一般的によく用いられるユークリッド距離や動的時間伸縮法ではなく、独自のShape-based distance（SBD）という距離尺度を用いています。
Shape-based distance（SBD）
SBDは、規格化した相互相関を用いています。
相互相関とは、信号処理や画像処理に広く使われている信号間の類似性の尺度です。
ざっくりいうとデータをずらしながら内積を計算していき、内積が一番大きくなった位置を探す感じです。
2つの時系列データxとyにおけるSBDは以下の式で表されます。
ただし、
Shape-based Time-Series Clustering
距離尺度が決まってしまえば、クラスタの重心が計算できます。（重心の計算方法は論文中の「3.2 Time-Series Shape Extraction」を参照）
あとのクラスタリングのアルゴリズムはk-meansとほぼ同じような感じで、以下のように反復的な処理を行います。
これを繰り返したのち、クラスタのメンバーに変更がないか、反復回数の最大値に達するまで上の手順を繰り返します。
感想
手持ちのデータをクラスタリングしたいときには、どの不変性に着目して、何を似ているとしたいのかを考えて、それに適したアルゴリズムを選定するかが重要だと思いました。
今回のアルゴリズムは、時間軸のずれや、伸縮に対して頑強なアルゴリズムである印象を受けました。サーバメトリクスの場合、scalingは重要な違いを表す要素だと思うので、サーバメトリクスのクラスタリングに対してはもっと適したアルゴリズムがあるかもなーと思いました。もっといろんな手法をサーベイしていきます。
k-Shapeに関しては、論文中に擬似コードが載っていたのでスクラッチで書けそうだし、tslearnというPythonライブラリもあるようなので試したい。
