# 時系列データのクラスタリング: サーベイ(Clustering of time series data - a survey) > [!abstract] 概要 > 時系列クラスタリングは、さまざまな分野で有用な情報を与えることが示されている。時間的データマイニングの取り組みの一部として、時系列クラスタリングへの関心は高まっているように見える。概観を与えるため、本論文は、さまざまな応用分野で時系列データのクラスタリングを調べた過去の研究を調査し、要約する。時系列クラスタリングの基礎として、時系列クラスタリングの研究で一般に使われる汎用のクラスタリングアルゴリズム、クラスタリング結果の性能を評価する基準、および生データ・抽出した特徴・モデルパラメータのいずれかの形で比較される二つの時系列の類似度・非類似度を決める尺度を示す。過去の研究は、時間領域または周波数領域の生データを直接扱うか、生データから抽出した特徴を介して間接的に扱うか、生データから構築したモデルを介して間接的に扱うかに応じて、三つの群に整理される。過去の研究の独自性と限界を論じ、今後の研究課題の候補をいくつか挙げる。加えて、時系列クラスタリングが応用された分野も、使われたデータの出所を含めて要約する。本サーベイが、この分野の研究を進めたい人々の足がかりになることを期待する。 ## 論文情報 - 著者: [[T. Warren Liao]](ルイジアナ州立大学 産業・製造システム工学科) - 掲載: Pattern Recognition, 38(11), 1857-1874, 2005(受理 2005-01-07) - DOI: 10.1016/j.patcog.2005.01.025 - 種別: サーベイ(18 ページ。章構造ではなく 5 節 + 付録の単一論文として取り込む) ## 概要 時系列クラスタリングの研究を、(1) 生データを直接クラスタリングする手法、(2) 特徴抽出を挟む手法、(3) モデルのパラメータや残差を介する手法の 3 群に整理し、各群の代表研究を距離尺度・アルゴリズム・評価基準・応用の 4 軸で表にまとめたサーベイである。時系列クラスタリングの要点は「二つの系列の類似度をどう測るか」であり、類似度さえ決まれば汎用のクラスタリングアルゴリズムを使えると結論する。 ## 問題設定 - クラスタリングの既存手法(分割・階層・密度・格子・モデルの 5 類型)は、ほぼすべて静的データ(特徴値が時間で変わらないデータ)を対象にしてきた。時系列を扱う研究は相対的に少なく、増加傾向にある。 - 時系列の性質は、離散値か実数値か、等間隔か不均一か、単変量か多変量か、系列長が等しいか異なるかで分かれる。不均一サンプリングの系列は、単純な間引きから高度なモデリングまでの方法で等間隔に直してから扱う必要がある。 - 目的は、これらの研究を一つの枠組みで整理し、各研究の独自性・限界・今後の課題を明らかにすることである。 ## 提案手法 新手法の提案ではなく、整理の枠組みが貢献である。 ### 三つのアプローチ ![[wiki/sources/_attachments/2005__Pattern-Recognit__Clustering-of-time-series-data-a-survey/fig01-three-approaches.png]] 図1(Figure 1)は 3 群の処理の流れである。(a) 生データ基盤は、静的データ用の類似度・距離を時系列用のものに置き換えるだけで既存のクラスタリングを使う。(b) 特徴基盤は、低次元の特徴ベクトルに変換してから従来の手法を適用する。(c) モデル基盤は、系列ごとにモデルを当てはめ、そのパラメータや残差をクラスタリングするか、モデルを直接学習して(別のクラスタリングを使わず)クラスタとする。 ### 汎用のクラスタリングアルゴリズム(§2.1) - 再配置クラスタリング: 初期クラスタから、一般化 Ward 基準が改善する限りメンバーの移動・交換を繰り返す。系列長が等しい場合に限る。 - 凝集型階層クラスタリング: 単連結・完全連結・Ward 法。併合後に調整できない弱点があるが、動的時間伸縮(DTW)のような距離を使えば長さの異なる系列にも適用できる。 - k-means とファジィ c-means: 目的関数(式 1〜5)の最小化を反復する。クラスタ中心の定義が曖昧になるため、系列長が異なる場合には向かない。 - 自己組織化マップ(SOM): 近傍を保つ写像を学習する。重みベクトルの次元を決めにくいため、系列長が異なる場合には向かない。 ### 類似度・距離尺度(§2.2) - ユークリッド距離・二乗平均平方根距離・ミンコフスキー距離 - ピアソン相関係数に基づく距離(2 種の相互相関ベース距離) - 短時系列(STS)距離: 区分線形関数とみなし、傾きの差の二乗和で不均一サンプリングを扱う。 - DTW 距離: 動的計画法で 2 系列を整列し、境界・連続・単調の 3 制約の下で経路距離を最小化する(式 15, 16)。 - 誤差付きデータ向けの確率ベース距離、カルバック・ライブラー(KL)距離、J ダイバージェンスと対称チェルノフ情報ダイバージェンス、相互相関関数に基づく非類似度指標、音声単語間の非類似度 ### 評価基準(§2.3) - 正解ありの場合: 正解クラスタ集合との類似度(式 26, 27。2|G∩C|/(|G|+|C|) の最大一致の平均)。 - 正解なしの場合: クラスタ数が既知なら一般化 Ward 基準などを用いる。クラスタ数が未知なら妥当性指標や AIC・BIC・ICL などの情報量基準を用いる。調査した時系列クラスタリング研究のいずれも、クラスタ数決定に妥当性指標を使っていない。 ## 新規性 - 時系列クラスタリングの 3 群分類(生データ・特徴・モデル)を立て、アルゴリズム・距離尺度・評価基準の 3 要素で各研究を整理した。同時期の時間的知識発見のサーベイ(Roddick ら)が時系列クラスタリングに割いたのは 2 ページ未満で、本論文はそれより詳細な概観を目指す。 - 応用領域(事業・工学・科学・医療・芸術)と用いられたデータの出所を付録にまとめた。 ## 実験設定 実験はない。調査対象は、既存の時系列クラスタリング研究のうち、公開文献で確認できた 2003 年前後までのもの(表1〜表3 に整理された生データ基盤・特徴基盤・モデル基盤の研究)である。 ## 実験結果 各群の代表研究を表にまとめる(論文の表1〜表3の要点)。 ### 生データ基盤(表1、Table 1) | 研究 | 距離 | アルゴリズム | 応用 | |---|---|---|---| | Golay ら | ユークリッド・2 種の相互相関ベース | ファジィ c-means | 機能的 MRI の脳活動地図 | | Kakizawa ら | J ダイバージェンス・対称チェルノフ | 凝集型階層 | 地震と鉱山爆発 | | Košmelj と Batagelj | ユークリッド | 修正再配置 | 商業エネルギー消費 | | Kumar ら | データ誤差のガウスモデル | 凝集型階層 | 小売の季節性パターン | | Liao | ユークリッド・対称 KL | k-means・ファジィ c-means | 戦闘シミュレーション | | Liao ら | DTW | k-メドイド遺伝的クラスタリング | 戦闘シミュレーション | | Möller-Levet ら | STS 距離 | 修正ファジィ c-means | DNA マイクロアレイ | | Policker と Geva | ユークリッド | Gath-Geva ファジィ | 睡眠脳波 | | Shumway | KL 判別情報 | 凝集型階層 | 地震と鉱山爆発 | | van Wijk と van Selow | 二乗平均平方根 | 凝集型階層 | 日次電力消費 | ### 特徴基盤(表2、Table 2) | 研究 | 特徴 | 距離 / アルゴリズム | 応用 | |---|---|---|---| | Fu ら | 知覚的重要点(PIP) | 修正 SOM | 香港株式市場 | | Goutte ら | 相互相関関数 | ユークリッド / 階層・k-means | 機能的 MRI | | Owsley ら | 過渡領域の時間周波数表現 | 修正 k-means(系列クラスタ精緻化) | 工具状態監視 | | Shaw と King | 正規化スペクトル(PCA で選択) | ユークリッド / 階層 | 風洞の流速 | | Vlachos ら | Haar ウェーブレット変換 | I-k-means | 非特定 | | Wilpon と Rabiner | LPC 係数 | 板倉距離ベース / 修正 k-means | 孤立単語認識 | 特徴抽出が系列長の違いを吸収するため、特徴基盤の手法はいずれも長さの異なる系列を扱える。 ### モデル基盤(表3、Table 3) | 研究 | モデル | 距離 / アルゴリズム | |---|---|---| | Baragona | ARMA(残差) | 相互相関ベース / タブー探索・遺伝的アルゴリズム・焼きなまし | | Beran と Mazzola | 階層平滑化モデル | 凝集型階層(音楽演奏) | | Biernacki ら | ガウス混合 | 対数尤度 / EM(ICL 基準) | | Kalpakis ら | AR の LPC ケプストラム | ユークリッド / PAM(メドイド分割) | | Li と Biswas / Li ら | 連続 HMM | 対数尤度 / 4 層入れ子探索(BIC 系) | | Maharaj | AR 係数 | 仮説検定の p 値 / 凝集型階層 | | Oates ら | 離散 HMM | 対数尤度 / DTW で初期化して固定点反復 | | Piccolo | AR(∞) | ユークリッド / 凝集型階層 | | Ramoni ら | マルコフ連鎖 | 対称 KL / 凝集型(ベイズ的クラスタリング BCD) | | Tran と Wagner | ガウス混合 | 修正ファジィ c-means(話者照合) | | Wang ら | 離散 HMM | EM(工具摩耗監視) | | Xiong と Yeung | ARMA 混合 | 対数尤度 / EM | 主な個別の知見: Golay らでは相互相関ベース距離の一つがユークリッド距離より良かった。Kalpakis らでは、AR 係数から導く LPC ケプストラムが、DFT・DWT・PCA・自己相関の DFT の先頭係数を用いたユークリッド距離より高い識別力を示した。Baragona ではタブー探索が他の探索より優れた。Goutte らでは ICL が最も倹約的で、AIC はクラスタ数を過大に推定する傾向があった。 ## 考察 - 論文が挙げる特徴として、離散値系列は Ramoni らの 2 件のみ、データ誤差を考慮するのは Kumar らのみ、不均一サンプリングを扱うのは Möller-Levet らのみである。Maharaj と Baragona は定常系列に限る。系列長が変数ごとに異なる多変量系列を扱う研究は皆無である。 - Košmelj と Batagelj、Kumar らは、系列の T 個の標本が互いに独立であると仮定し、時間相関を無視する。一次マルコフ連鎖は 1 時点前にのみ依存すると仮定し、隠れマルコフモデルはより豊かな表現を与える。HMM を多次元に使う 2 件も時間特徴の独立を仮定している。長い記憶を持つ系列には高次のマルコフ連鎖・HMM を検討すべきだとする。 - 時系列クラスタリングと静的データのクラスタリングの違いは、二つのデータ対象の類似度の計算法にほぼ尽きる。鍵は、対象データの特性を理解して適切な類似度・非類似度を設計することである。 - 変化点検知で系列の開始時点を自動特定してから比較する補完(Shumway の指摘)。遺伝的アルゴリズムの利用は Baragona のみで検討の余地がある。手法を選んだ根拠の説明が乏しく、手法間の比較研究も欠けている。 - 静的データで有効とされる教師なしクラスタリングと教師あり分類の統合や、クラスタリングのアンサンブルを時系列に試す価値がある。ただしアンサンブルにはクラスタラベルが不定になる問題がある。 - 大規模データへの拡張は静的データ向け(CLARA・CLARANS など)に偏り、時系列ではセグメンテーションによる表現の圧縮が主である。 ## 強み / 弱点・課題 - 強み: 3 群 × 3 要素の分類が明快で、各研究を距離・アルゴリズム・評価・応用の表で引ける。付録の応用とデータ出所は再現の出発点になる。 - 弱点・課題: 2003 年前後までの文献に限られ、深層学習以前である。手法間の定量比較は行わず、性能の優劣は個別研究の報告に依る。クラスタ数決定や評価は各研究の特殊な基準に依存し、比較可能な枠組みはない(後続の PVLDB 2025 のサーベイが大規模な比較評価で埋めている: [[@2025__PVLDB__Time-Series Clustering - A Comprehensive Study of Data Mining, Machine Learning, and Deep Learning Methods]])。 ## 関連 - 概念: [[時系列クラスタリング]] / [[クラスタリング]] / [[時系列類似度検索]] - エンティティ: [[T. Warren Liao]] - ソース: [[@2025__PVLDB__Time-Series Clustering - A Comprehensive Study of Data Mining, Machine Learning, and Deep Learning Methods]] / [[@2016__SIGMOD Record__k-Shape - Efficient and Accurate Clustering of Time Series]] ## 出典 - 原本: [[.raw/papers/2005__Pattern-Recognit__Clustering-of-time-series-data-a-survey.pdf]]