# Time-series clustering – A decade review > [!abstract] 概要 > クラスタリングは、事前にクラスの知識が無いときに膨大なデータを分類する解決策である。クラウドコンピューティングやビッグデータといった新しい概念とその広範な応用が現れた近年、この大量のデータから知識を抽出するために、クラスタリングアルゴリズムのような教師なしの解決策に関する研究が増えている。時系列データのクラスタリングは、複雑で大規模なデータセットから価値ある情報を引き出すデータ分析者を助けるパターン発見のために、多様な科学分野で用いられてきた。巨大なデータセットでは教師あり分類の解決策を使うことはほぼ不可能だが、クラスタリングは教師なしの手法でこの問題を解決できる。本研究は、遺伝子発現データから株式市場分析まで幅広く使われる、クラスタリング問題で人気のあるデータ型の 1 つである時系列データに焦点を当てる。このレビューは時系列クラスタリングの 4 つの主要構成要素を明らかにし、過去 10 年間の時系列クラスタリング手法における効率・品質・複雑さの改善傾向に関する最新の調査を示し、今後の研究の新しい道筋を照らすことを目指す。 ## 論文情報 - タイトル: Time-series clustering – A decade review - 著者: Saeed Aghabozorgi、Ali Seyed Shirkhorshidi、Teh Ying Wah(マラヤ大学 情報システム学科) - 媒体: Information Systems 53(2015) 16–38。受理 2015-04-27、オンライン公開 2015-05-06 - DOI: 10.1016/j.is.2015.04.007 - 既存の詳細メモ: [[papers/2015__Information Systems__Time-series clustering – A decade review|papers 側の旧ノート]] ## 概要 時系列クラスタリングを、表現・距離尺度・プロトタイプ・クラスタリングアルゴリズム・評価の要素に分解して過去 10 年の文献を整理したサーベイである。全系列クラスタリングを主対象に、各要素で代表手法の長所短所を比較し、研究の重心が表現・距離尺度・プロトタイプにあってアルゴリズム自体の改良が少ないことを指摘する。将来課題として、品質とコストの均衡をとるハイブリッド(多段)アルゴリズムを挙げる。 ## 問題設定 - 定義 1: n 本の時系列の集合 D = {F1, …, Fn} を、ある類似度尺度に基づき同質な系列が同じ群に入るよう、教師なしで C = {C1, …, Ck} に分割する処理を時系列クラスタリングと呼ぶ。D = ∪Ci かつ i≠j で Ci ∩ Cj = ∅ である。 - 系列は実数値の連続系列であり、名義記号の列(時間的系列)と区別される。系列の特徴値は時間の関数として変化する動的データである。 - 難しさは 3 点ある。第 1 に系列がメモリより大きくディスク上に置かれるため速度が指数的に低下する。第 2 に高次元でありアルゴリズムの処理が難しく遅くなる。第 3 に類似度尺度であり、雑音・外れ値・ずれを含み長さも異なる系列全体を比べる「全系列照合」が複雑になる。 - 応用: 異常・新規・不一致(ディスコード)の検知、時系列間の相関など動的変化の認識、予測と推薦、パターン発見。Table 1 に領域別の例を示す。 **Table 1: 領域別の時系列クラスタリングの目的の例** | 領域 | 応用 | 文献 | |---|---|---| | 航空・天文 | 天体の光度曲線 — 外れ値検知の前処理 | [41] | | 生物 | マイクロアレイ時系列での複数遺伝子発現プロファイルの整列 | [42] | | 生物 | 時系列遺伝子発現の機能的クラスタリング | [43] | | 生物 | 機能的に関連する遺伝子の同定 | [44–46] | | 気候 | 気候指数の発見 | [47,48] | | 気候 | ニュージーランド沿岸での PM10・PM2.5 濃度の解析 | [49] | | エネルギー | エネルギー消費パターンの発見 | [50,51] | | 環境・都市 | 海面極値の地域変動の解析 | [52] | | 環境・都市 | 地震 — 包括的核実験禁止条約(CTBT)違反の可能性の解析、パターン発見と予測 | [53,54] | | 環境・都市 | ユタ州ソルトレーク郡での 1 日の人口分布変化の解析 | [55] | | 環境・都市 | 気候指数と、クラスタリングで検出した群・傾向の関係の調査 | [56] | | 金融 | 季節性パターン(小売パターン)の発見 | [57] | | 金融 | 個人所得パターン | [58] | | 金融 | 効率的なポートフォリオの作成 | [59] | | 金融 | 株価時系列からのパターン発見 | [60] | | 金融 | 企業とその収益変動の解析によるリスク低減ポートフォリオ | [61] | | 金融 | 株価時系列からのパターン発見 | [29,62] | | 金融 | ヘッジ期間と金融時系列の性能の相関の調査 | [63] | | 医療 | 脳活動の検出 | [64,65] | | 医療 | MS 臨床試料からの病理事例の探索・同定・判別 | [66] | | 心理 | 心理領域での人間行動の解析 | [67] | | ロボット | ロボットの経験の典型的な表現の形成 | [68,69] | | 音声 | 話者照合 | [70] | | 音声 | 階層クラスタリングによる生体音声分類 | [71] | | ユーザー解析 | SNS 利用者の多変量感情行動の解析(感情の観点から利用者を分類) | [72] | (Table 1. 領域別の時系列クラスタリングの目的の例。) ## 分類体系 時系列クラスタリングを 3 分類する。全系列クラスタリング(個々の時系列集合を類似度でクラスタ化)、部分系列クラスタリング(長い 1 本の系列から窓で切り出した断片のクラスタ化)、時点クラスタリング(時間的近接と値の類似の組み合わせで時点をクラスタ化。一部は雑音として未割り当て)である。部分系列クラスタリングは Keogh と Lin が「無意味」(出力が入力に依らない)と示したため、本レビューは全系列クラスタリングに焦点を当てる。 **Figure 1: 時系列クラスタリングの分類体系** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig01-taxonomy.png]] (Figure 1. 時系列クラスタリングを全系列・部分系列・時点の 3 つに分ける分類体系。) 全系列クラスタリングの手法は大別して 3 種の方針を取る。(1) 既存の従来型アルゴリズムを時系列向けに改造(主に距離尺度の変更)、(2) 系列を単純な静的オブジェクトへ変換して従来型に入力、(3) 多重解像度を入力とする多段方式である。手法の系統は 3 種ある。形状ベース(生データを非線形な時間軸の伸縮で合わせる)、特徴ベース(低次元の特徴ベクトルへ変換。通常は等長ベクトルにユークリッド距離)、モデルベース(系列をモデルパラメータへ変換し、モデル距離で比較)である。モデルベースは規模拡大に問題があり、クラスタが近いと性能が下がる。 **Figure 2: 時系列クラスタリングの 3 系統** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig02-approaches.png]] (Figure 2. 形状ベース・特徴ベース・モデルベースの時系列クラスタリング手法の概観。) 過去の文献から、全系列クラスタリングは 4 つの構成要素(次元削減または表現手法、距離尺度、クラスタリングアルゴリズム、プロトタイプ定義)と評価から成る。一般に系列を表現でメモリに収め、距離尺度を用いてクラスタリングアルゴリズムを適用し、要約のためにプロトタイプを求め、最後に評価指標で検証する。 **Figure 3: 全系列クラスタリングの 4 構成要素の概観** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig03-four-components.png]] (Figure 3. 全系列時系列クラスタリングの 4 つの構成要素の概観。) ## 表現手法(次元削減) 定義 2: 系列 Fi = {f1, …, fT} を、x < T となる次元削減ベクトルへ変換する。元の空間で似た 2 系列は変換後も似ていなければならない。削減が重要な理由は 3 つある。メモリ要件を下げる、距離計算を速くする、生系列では歪みに敏感な尺度により形状でなく雑音の類似で分類してしまうことを避ける、である。削減率の選択は速度と品質の妥協である。Ding らは 8 種の表現手法を 38 データセットで比較し(下限の緊密さで評価)、近年の表現手法の間の差はごくわずかであると示した。 分類は 4 種である。 **Figure 4: 表現手法の階層** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig04-representation-hierarchy.png]] (Figure 4. 表現手法をデータ適応・非データ適応・モデルベース・データ支配の 4 種に分ける階層。) - データ適応: 全系列に対し、任意長(不等)の区間で全体の再構成誤差を最小化する。PLA、PCA(区分定数近似)、APCA、SVD、SAX・iSAX など。個々の近似は良いが複数系列の比較は難しい。 - 非データ適応: 固定長(等長)分割向けで、複数系列の表現の比較が簡単である。ウェーブレット、DFT、チェビシェフ多項式、PAA、IPLA など。 - モデルベース: 系列を確率的に表す。マルコフモデル・HMM、統計モデル、時系列ビットマップ、ARMA。 - データ支配: 圧縮率を生系列から自動で決める。クリップド表現(各点が平均より上かを 1 ビットで表す)は、形状でなく変化の類似に基づく分類には理論的にも実験的にも十分である。 **Table 2: 時系列の表現手法** | 表現手法 | 計算量 | 型 | コメント | 導入 | |---|---|---|---|---| | DFT | O(n log n) | 非データ適応・スペクトル | 自然信号向け。偽陰性なし。時間伸縮クエリ非対応 | [20,108] | | DWT | O(n) | 非データ適応・ウェーブレット | 定常信号向け。DFT より良好。結果が不安定で長さが 2 の冪必須 | [85,108,109] | | SVD | 非常に高い O(Mn²) | データ適応 | テキスト処理分野で使用。データの基礎構造を得る | [20,97] | | DCT | 記載なし | 非データ適応・スペクトル | – | [97] | | PLA | ボトムアップで O(n log n)、他は O(n²N) | データ適応 | 自然信号・生体医学向け。(当時)索引不可で高価 | [86] | | PAA | 極めて高速 O(n) | 非データ適応 | – | [24,90] | | APCA | O(n) | データ適応 | 非常に効率的。実装が複雑 | [87] | | PIP | 記載なし | 非データ適応 | 金融向け | [110] | | CHEB | 記載なし | 非データ適応・ウェーブレット・直交 | – | [99] | | SAX | O(n) | データ適応 | 文字列処理・生物情報学向け。下限評価と個数削減が可能。離散化とアルファベットサイズが欠点 | [111] | | クリップド | 記載なし | データ支配 | ハードウェア向け。超コンパクト | [83] | | IPLA | 記載なし | 非データ適応 | – | [101] | (Table 2. 主な表現手法。記載なしは著者が示していないもの。) 考察: 多くは高速化と索引に主眼を置き、表現の質を扱うものは少ない。離散値系列、不均一標本、データ誤差、長さの異なる変数を持つ多変量系列を扱う研究は僅少または皆無である。 ## 距離尺度 時系列クラスタリングは距離尺度に大きく依存する。従来のクラスタリングは静的対象の厳密一致に基づくが、時系列では近似で計算する。目的に応じて 3 種に分かれる。 **Figure 5: 距離尺度の分類軸** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig05-distance-approaches.png]] (Figure 5. 距離尺度を水準(形状・構造)、目的(時間・形状・変化の類似)、型(形状・比較・特徴・モデル)の 3 軸で整理する。) - 時間での類似: 各時刻で近い系列を探す。相関系列やユークリッド距離が適し、生系列では高価なため変換後(フーリエ・ウェーブレット・PAA)で計算する。株価が連動する企業の探索など。 - 形状での類似: 出現時刻が問題でなく、DTW などの弾性尺度で共通の形を持つ系列をまとめる。形状類似は時間類似より優れるという報告があり、時間類似は形状類似の特殊例である。 - 変化(構造)での類似: HMM や ARMA を当てはめ、モデルパラメータ上で類似度を測る。長い系列向けで、短い系列には不適である。 水準の観点では、形状水準は短い系列(遺伝子発現プロファイルや 1 拍の心拍)、構造水準は長い系列(1 時間の ECG や年次気象)に用いる。型は 4 種で、形状ベース(ED、DTW、LCSS、MVM。短い系列向け)、圧縮ベース(CDM、自己相関、STS など。短長どちらも可)、特徴ベース(統計・係数。長い系列向け)、モデルベース(HMM、ARMA。長い系列向け)である。 **Table 3: 文献の類似度尺度** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/table3-similarity-measures.png]] (Table 3. 距離尺度を特性・手法分類・定義元とともに比較した表。DTW、Pearson 相関、ED、KL 距離、HMM、LCSS、ERP、EDR、CDM、三角類似度など多数の尺度を含む。) 考察の要点は次のとおり。動的計画法に基づく尺度が最も効果的かつ正確だが二次の計算量で、制約を付けて緩和するには調整が要る。大規模データでどの程度有効かは、対象文献の多くが小規模データを用いるため文献から分からない。距離尺度と表現手法の不整合(周波数領域では値に基づく差を出しにくい等)が大きな課題である。分類精度では ED が驚くほど競争力を持つ一方、DTW にも強みがある。 ## プロトタイプ クラスタのプロトタイプ Rj は、クラスタ内の全系列との距離を最小にする系列(Steiner 系列)で、E(Ci, Rj) = (1/n) Σ dist(Fx, Rj) を最小化する(式 4.1)。分割型アルゴリズム(k-Means、k-Medoids、FCM)や階層型の一部でクラスタ品質はプロトタイプの品質に強く依存する。正しさを証明した手法はほとんど無い。3 種の定義がある。 - メドイド: クラスタ内で二乗誤差和が最小の実系列。最も一般的で、非弾性距離ではセントロイドに最も近い系列である。 - 平均: 等長かつ非弾性距離(ED)のときに各時点の平均で得る。弾性距離(DTW・LCSS)や長さが異なる場合は 1 対 1 対応のため形状の平均を捉えられず避けられる。DTW を使った形状平均(系列を階層的または逐次に組み合わせる方法。順序依存が欠点)、CWRT(メドイドへ全系列を DTW で整列して平均。順序に不変)、大域平均、LCSS による平均(不等長・弾性距離を支える)がある。 - 局所探索: メドイドを求め、ワーピング経路に基づき平均プロトタイプを作り直す。Hautamaki らは、局所探索プロトタイプがメドイドや平均より高いクラスタリング精度を示し、k-Medoids を最も改善したと報告した。ただし他のメドイド平均法に比べた改善幅は不明である。 不正確なプロトタイプは収束にも影響し、低品質なクラスタにつながる。 ## アルゴリズム 分類は 6 群である。分割型、階層型、格子ベース、モデルベース、密度ベース、多段。 **Figure 6: クラスタリング手法の分類** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig06-clustering-approaches.png]] (Figure 6. クラスタリングアルゴリズムの 6 群への分類。) - 階層型: 凝集型・分割型。一度の統合や分割を修正できず品質が弱いため、他手法と併用しやすい(Chameleon、CURE、BIRCH)。ペアごとの距離行列から入れ子の階層を作り、可視化力が強く、クラスタ数が不要で、弾性距離と組み合わせて不等長も扱える。二次の計算量のため大規模データは苦手である。DTW 併用は Oates らが 150 試行の実ロボットデータに、SAX の評価は階層クラスタリングを使った。 - 分割型: k-Means、k-Medoids(PAM、CLARA、CLARANS)、ファジィ(FCM、Fuzzy c-Medoids)。k の事前指定が必須で、時系列ではデータが巨大なため診断が難しい。階層型より速いため多用される(k-Means は平均ベクトル)。プロトタイプ依存のため「時間で類似」かつ等長の系列に向く。 - モデルベース: 統計(COBWEB)やニューラル(ART、SOM)。SOM は重みベクトルの次元を決める必要があり不等長に弱い。パラメータ設定とユーザー仮定への依存、処理の遅さが弱点である。 - 密度ベース: DBSCAN、OPTICS。Chandrakala と Chandra が多変量・不等長向けにカーネル特徴空間での手法を提案した稀な例で、複雑さのためほとんど使われない。 - 格子ベース: STING、WaveCluster。著者の知る限り時系列への適用例は無い。 **Table 4: 全系列クラスタリングアルゴリズムの一覧(前半)** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/table4a-whole-clustering-algorithms.png]] (Table 4. 表現手法・距離尺度・クラスタリングアルゴリズムと長所(P)・短所(N)のコメントを付した既存研究の一覧。) **Table 4(続き): 一覧(後半)** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/table4b-whole-clustering-algorithms-cont.png]] (Table 4 続き。Gullo らの DSA + DTW + k-Means、Aghabozorgi の DWT + LCSS + FCM、Zakaria のシェイプレット + k-Means など。) ### 多段クラスタリング 従来手法をそのまま使う研究が多いが、これは科学的理論には十分でも実世界では遅いか不正確である。実務では時系列向けに調整した手法が要る。表現・距離・プロトタイプの改善に比べ、アルゴリズム自体の改良は少なく、多くはハイブリッドや多段である。 1. Lai ら: 全系列(SAX + CAST)と部分系列(DTW または ED)の 2 段。第 1 段の距離尺度が不明、CAST の閾値が敏感、部分系列クラスタリングは無意味という Keogh と Lin の指摘に抵触、標準データセットでない、と批判される。 2. Zhang ら: 1-最近傍ネットワークから候補系列を選び階層型を適用、DTW でずれを扱い、データを約 1 割へ縮小する。ネットワーク構築が O(n²) で、k-Means の事前クラスタリングでも高価。実験は合成データ 2 種のみ。最終クラスタの品質は標準指標で未評価。 3. 増分型: Vlachos らは Haar ウェーブレット分解の解像度ごとに k-Means を段階適用し、前段の中心を倍にして次段の初期値とする。Lin らは k-Means と EM の anytime 版へ一般化し、MPAA 版も示した。終了点が不明、解像度ごとに全系列を再クラスタ化して雑音が全体に響く、分割型にしか使えない、DTW の高コストとプロトタイプ定義が未解決である。 4. Aghabozorgi と Wah の 3PTC: (1) 事前クラスタリング、(2) 精製と要約(プロトタイプ化)、(3) 統合。形状類似でクラスタを作り、株式の共動を局所的なずれがあっても把握する。 5. Aghabozorgi らの TTC: まず時間類似で副クラスタを作り、次に k-Medoids で形状類似に基づき統合する 2 段。従来手法・ハイブリッド手法より精度が高く、形状類似を低い複雑さで求められると報告する。 ## 評価指標 Keogh と Kasetty は時系列マイニングの評価に守るべき規律を示す。多様なデータセットで検証する(公開データを使う)、実装バイアスを避ける、可能ならデータとアルゴリズムを公開する、新しい類似度は ED のような単純で安定した尺度と比べる。ラベル無しでのクラスタ評価は未解決問題で、クラスタの定義は利用者・領域に依存する主観である。 **Figure 7: 新しいモデル(MTC)の実験的評価の流れ** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig07-evaluation-process.png]] (Figure 7. 時系列クラスタリングの新しいモデルの評価過程。) 評価は可視化と、スカラー精度指標に大別する(Figure 8)。 **Figure 8: 文献で用いられる評価指標の階層** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig08-evaluation-hierarchy.png]] (Figure 8. 評価指標の階層。外部指標に purity、CSM、FM、Rand Index、ARI、F-measure、NMI、Entropy、Jaccard、内部指標に SSE を挙げる。) - 外部指標: 正解ラベルとの一致を測る。Purity(クラスタ数が多いと高くなる欠点)、CSM、FM、Jaccard、Rand Index、ARI(Rand を偶然補正)、F-measure、NMI(クラスタ数の違う手法も比較可)、Entropy。0 から 1 の範囲で大きいほど良い(Entropy は反転させた cEntropy)。どの指標が優れるかの合意は無い。 - 内部指標: 正解を使わずクラスタ構造の良さを測る。SSE、Silhouette、Davies-Bouldin、Calinski-Harabasz、Dunn ほか。同じモデルや尺度で作った結果の間でしか比較できない。 - 実運用では正解が無く、内部指標が必要だが、外部指標が最も普及している。 ## 新規性 時系列クラスタリングの比較実験に焦点を当てたサーベイ・レビューは既にあるが、本レビューほど包括的なものは無いと著者は主張する。本レビューは時系列クラスタリングの構造(4 構成要素 + 評価)を全体として整理し、過去 10 年の効率・品質・複雑さの改善傾向を示す。同じ系統の先行サーベイとして [[@2005__Pattern-Recognit__Clustering of time series data - a survey]] が wiki にある(本論文の比較対象として明示されたものではなく、主題が近いため関連付ける)。 ## 考察 **Figure 9: 時系列クラスタリングを改善する 4 側面** ![[_attachments/2015__Information-Systems__Time-series-clustering-A-decade-review/fig09-four-aspects.png]] (Figure 9. 時系列クラスタリング研究の 4 側面。研究の大半は表現・距離尺度・プロトタイプの改善であり、アルゴリズム自体の改良は他に比べ約 10% 未満である。) - 表現: データ適応は個々を良く近似するが複数系列で不利、非データ適応は固定長向け。 - 距離: 最も人気は ED と DTW。動的計画法系は高コストで調整が要る。多くの提案尺度は ED を上回らず、[6] の実験では誤り率がむしろ悪い。精度の高い尺度の必要性は満たされていない。 - プロトタイプ: メドイドと平均を超えるものは出ていないと言いつつ、比較では局所探索が最良だった。 - アルゴリズム: 分割型は速いがクラスタ数の指定が要り実務向きでない。階層型は数の指定が不要で評価に適するが小規模に限る。モデルベースと密度ベースは遅く複雑で稀。 - 今後: 不等長の多変量系列、不均一標本、離散値系列の表現が未開拓。最大の機会は、既存または新規のクラスタリング手法を組み合わせ、品質とコストを均衡させるハイブリッドである。 ## 強み / 弱点・課題 - 強み: 表現・距離・プロトタイプ・アルゴリズム・評価を 1 本の枠組みで整理し、Table 1〜4 で手法を横断比較できる。各手法の弱点を個別に指摘している。 - 弱点: 手法間の実験比較は無く、優劣の判断は文献の報告に依る(「ED は驚くほど競争的」等は引用である)。深層学習以前の 2015 年時点の整理で、ニューラル表現学習は対象外である。多段クラスタリングの節で紹介される事例に著者ら自身の手法(3PTC、TTC)が含まれる。 - 注記: 部分系列クラスタリングの「無意味」判定は Keogh と Lin の主張の引用であり、本論文が検証したものではない。