Torkamani, S., & Lohweg, V. (2017) Survey on time series motif discovery. WIRES Data Mining and Knowledge Discovery, 7(2).

　仕事の都合で読んだ奴。時系列モチーフ発見についての短い解説。この分野について全然知らんので、まずは易しそうなやつから目を通した。でも、数式が全く出てこないというのも、それはそれで怖いなあ…

1. イントロダクション
　時系列分析の課題はいろいろある。クラスタリング、分類、内容によるクエリー、異常検出、モチーフ発見。
　モチーフ発見っていうのは、事前情報なしで、時系列から未知の頻出パターンを見つけることである。モチーフということばは遺伝学から来ている。2002年に導入された。
　モチーフを見つけてなにが嬉しいかというと、モチーフは問題についてのインサイトを与えてくれるし、ルール発見や要約やそのほかのパターン認識の役にも立つ。

2. 時系列モチーフの定義
　先行研究でのモチーフの定義は2種類ある。トップ\(K\)-頻度モチーフ(\(K \in \mathbb{N}\))と最近隣モチーフである。最近隣モチーフというのは、モチーフ間の距離が最小であるようなモチーフを見つけることである(マッチする数が多い下位系列を見つけることではない)。この定義には事前の閾値\(\tau \in \mathbb{R}^+\)が登場しない。
　時系列に出てくるモチーフは、ふつう時間スケールが違うし、強度軸でもずれていたりするし、ノイズが乗っていることもある(こういうのをill-knownであるという)。モチーフ発見の手法の研究は山ほどあるが、ill-knownなモチーフを発見できる手法は少ない。

3. 時系列モチーフ検出アルゴリズム
　詳しくはMueen(2011, Wiley Interdicop.Rev.Data.Min.Knowl.Dicov.)をみてね。
　共通した課題は、モチーフの長さの定義、データストリーミングの扱い、長さが違うモチーフをどうみつけるか、時間的複雑性[このあとを読むと、どうやら計算量のことらしい]、そしてill-knownモチーフの発見である。
　検出アルゴリズムは要するに2ステップからなる。類似性指標と時系列表現である。本項では、時間的複雑性とill-knownモチーフの検出能の観点からレビューしよう。

4. 時間的複雑性の比較

• Patel et al.(2002 Proc.): 時系列の長さを\(N \in \mathbb{N}\)として時間的複雑性は\(N^4\)のオーダー。彼らは改善のためにEMMAというのを提案している。Efficient MOEN(Mueen, 2013 Proc.)というのもある。[以下、計算量についてはメモを省略する。また以下のリファレンスは、工学系だけあって出典もたいてい国際会議のproceedingで、どうせ読みゃしないだろうから省略する]
• Chiu et al.(2003): ランダム・プロジェクション。データをSAX法でシンボル系列に変換する[あー！これ前に時系列クラスタリングの話で読んでさっぱりわかんなかったやつだ！]。
• Li, et al.(2012): Haarウェーブレット分解によるクラスタリング・アプローチ。任意の時点で検討を開始したりやめたりできる。
• Serra & Acros(2016): 粒子swarm最適化を使う方法()。これもany-time手法である。
• Mueen et al.(2009): MKアルゴリズム。
• Mueen et al.(2009): DAME。
• Nunthanid, et al. (2012): k-最良モチーフ発見(kBMD)。いろんな幅の窓を何回か滑らせていろんな長さのモチーフを定義する。MKアルゴリズムを使う。
• Lin, et al.(2010): 文法ベース法。繰り返し出現するシンボル系列を見つける。
• Yingchareonthawornchai, et al. (2013): MDL原理でもって最良のモチーフ長を見つける。
• Yankov et al. (2007): 一様スケーリングテクニック。長さをできるだけ伸ばさずに済むようにモチーフを決める。

ここからは多変量データ。

• Tanaka, et.al. (2005): PCAしてモチーフを見つける。より効率の良い方法も提案されている(Anh & van Nhat, 2005 MachineLearn.)。
• Lin, et al.(2003): SAXとランダム・プロジェクションをそれぞれの次元でやる。
• Balasubramanian, et al.(2020): Liらの方法でそれぞれの次元で検出する。
• Castro and Azevedo(2000): 強度multiresolution法。iSAXというのを使う。
• Vespier et al.(2023): 複数の時間スケールにおけるモチーフをMDL原理でみつける。

5. ill-knownモチーフの検出。
　詳しくはBatista et al.(2014 Data.Min.Knowl.Discov.)　をみてね。
　強度のシフトの問題に対してはなんらか基準化が必要になる。距離の選択がとても重要になる。一番使われているのはユークリッド距離なんだけど、時間シフトが起きていたら正しい距離はわからない。SAXみたいな表現をした場合はフーリエ変換となんらかのウェーブレット変換が使える。しかし、SAXというのはすべての規準された時系列が正規分布ないし等確率という仮定があるし、スパイクみたいな情報は失われてしまう。
　局所的なスケーリングの問題ならdynamic time warping距離がつかえる。上述の一様スケーリングテクニックでも異なる長さのモチーフを検出できる。
　[…という感じで、たくさんの手法がどんどん紹介されるんだけど、疲れたのでメモ省略]

6. モチーフ検出ツール
　オンラインツールとしてはDAME, MK, Mr.Motif, kMOTIF, Enumeration MOENなどがある。Mueenらの手法についてはこのURLをみよ。[全部リンク切れだよ、もう…]
　SAX方面ではVizTree, GrammerViz2というのもある。

6. 今後の課題
　[本論文で言及された手法の星取表が載っている。モチーフ長を最初に決めないといけないか、シンボル表現化、周波数領域の分析か、類似性指標、等しい長さのモチーフを見つけられるか、可変長のモチーフを見つけられるか、マルチスケールか、ストリーミング対応可、計算量、anytimeか。類似性指標って、要するにユークリッド距離か相関かDTWみたいだ…]

• 他の類似性指標を使う
• SAX以外の表現を使う
• ストリーミングへの対応
• ill-knownデータの扱い
• significantなモチーフの検出

———-
　ふーん。いろんな研究があるもんですね…
　読み終えてから不意に思い出したのだが、このテーマについて、人工知能学会誌の「私のブックマーク」に以前まとめが載っていたような気がしてきた。まずそっちを探せばよかった。なにやってんだかなあ。

　ま、しがないシモジモのパッケージユーザとしては、ソフトがないと身動き取れないわけで、みなさんソフト作ってくださいと祈るばかりである。
　検索したところ、RにはSTMotifパッケージ(時空間系列のモチーフ発見だそうだ)、jmotifパッケージ(SAXに基づく)、tsmpパッケージ(よくわからんがmatrix profileアルゴリズムというのに基づくらしい)、TSMining(CRANからは2022年に消されている)、というのがあるようだ。他に、CRAN Task ViewsのTime Seriesを眺めていたら(かのHyndmanさんがメインテナなのね、知らんかった)、PSFパッケージというのがあった。Pattern Sequence-Based Forecasting (PSF) アルゴリズムによる単変量時系列予測だそうである。これもモチーフ発見なの？ 今度調べてみよう。
　恥をさらすようだが、似た話に時系列のordinal patternっていうのがあるじゃないですか。Rだとotsfeaturesパッケージとかordinalpatternパッケージとか。あれとモチーフ発見との関係もよくわからない。わからないことばかりで頭が痛い。というか、やっぱし働くの向いてない。一日中猫のように寝て過ごすわけにはいかないものだろうか。