xiangze's sparse blog

機械学習、ベイズ統計、コンピュータビジョンと関連する数学について

A Brief Survey on Sequence Classification(系列データの分類)の要約

時系列 datascience

 

最近時系列データの解析を専門とする人たちのお話をきいたり、ブログを読んだりする機会が多くなっています。工学の枠を超えてビジネスでの応用が盛んになっているようなのですが、今まで制御理論などで得られた理論、知見とは大きな隔たりがあります。

 

そこで系列データの分類(sequence classiffcation)に関して簡潔にまとめられたドキュメントであるA Brief Survey on Sequence Classification (pdf) を読みました。表題の通り実質６ページで構成された短いドキュメントですが、自分の理解の為にその内容を簡単ではありますが以下にまとめます。

 

 1. INTRODUCTION

まず系列データ(sequence data)を以下のように分類しています。

 

  • simple symbolic sequence　アルファベットなどの記号を単純に並べたもの。DNA  seqenceが代表例
  • complex symbolic sequence 順序のあるベクトルのリスト　ベクトルの各要素は商品の名称などになります。
  • simple time series 時刻と値の組　間欠的に起こる現象の記録に有利
  • multivariate time series　時刻とベクトルの組simple time seriesのベクトル版
  • complex event sequence さらに複雑なデータ構造*1

系列全体、あるいはその一部がclass labelを持ちます。例としては心電図(ECG)のデータでは健康か異常か、DNA sequenceでは蛋白質をコーディングしている領域かそうでないかなどです。

伝統的な系列データ分類(conventional  sequence classiffation)は系列全体のデータを用いてそのクラスを判別するものですが、そうでない例を本論文の3.では挙げています。

2. SEQUENCE CLASSIFICATION METHODS

系列データの分類の手法として以下のような４種類を挙げています。   

 2.1 Feature Based Classification

決定木やニューラルネットなどの機械学習のメジャーな手法はベクトル値を入力とするようになっています。このため系列データもそのような形式に変換できれば高度な判別手法を使い分類することが出来るでしょう。系列データの特性(feature)をベクトルの要素とする手法として以下のものが挙げられています。

  • k-gram
  • pattern-based feature selection
k-gram法

自然言語処理ではk個の連続する単語をk-gramと呼ぶのはよく知られています。symbolic sequenceに対してはこの手法は有効で、系列データ内のあるk-gramの出現頻度が対応するベクトル要素の値とすることが出来ます。

kとしてとる値が大きければfeatureの特異性は増しますが、その頻度は減少してしまい、またベクトルの次元は増大してしまいます。kが小さければベクトルの次元は少なくなりますが、ベクトルがクラスを表す表現力は低下してしますでしょう。

要素の間に別のデータが挟まっているk-gram (gapped k-gram)にも言及しており、挿入型の突然変異があるゲノムのみならず、自然言語の構文の点でも有用なようです。ChuzhanovaらによるGamma testと呼ばれる手法で最適なkを求める研究が紹介されています*2。

k-gramを用いた手法のサマリー論文も挙げられています。

pattern-based feature selection法 

全ての連続列を対象とするk-gram法に対して、代表的な特徴を抽出するpattern-based feature selectionはLeshらによって提唱されました(pdf)。   

ここでfeatureとなるのは短い系列で

  1. 少なくとも１つのクラスでは頻出する
  2. 少なくとも１つのクラスを識別することが出来る。
  3. 冗長でない

という条件を満たす必要があります。pattern-based feature法の要点は如何に有用なfeatureを抽出するかにあります*3。系列データのfeature抽出を自動化(mining)する手法も挙げられています。

時系列データに対してはk-gram法は困難であり、feature selectionをするにも通常はデータを離散化することが必要です。離散化を行わない方法としてshapletと呼ばれる特徴を抽出する方法が挙げられています*4。

wavelet変換の結果をfeatureとして使う方法も提唱されています。

最後に上記手法の相違点を

  • どの特性をfeatureとすべきか(識別性、頻度、長さなど)
  • データの特徴は局所的なものか、大域的なものか
  • (featureの)マッチングにおいてgapは考慮すべきか
  • 特徴選択は識別器に統合されるべきか、分離したプロセスにスべきか

とまとめています。

 2.2 Sequence Distance Based Classification

系列データをベクトル化するのではなく、系列データの間に距離を定義し、その上でk nearest neighbor法で分類するという手法です。

もっとも単純なものとしてはユークリッド距離

d(s,s')=\sum_{i=1}^L(s[i-s'[i])^2]

(s[i],s'[i]は異なる２つの系列データ)

を用いる方法があります。これはゆがみに対して弱く、また長さの異なるデータには使えないのでDynamic time warping(DTW)と呼ばれる手法が使われます。Dynamic time warpingは系列データの各点に対してその前後にWindowを定義し、その範囲内で類似度を計算するというものです。素朴な方法では計算量がデータ長の２次になり、時間がかかりますが、高速化手法も提案されているそうです*5。

時系列が周期的な場合には、その位相を無視したクラスタリングを行うと無意味なクラスター中心が得られてしまう「正弦波問題」という問題が知られているそうです。これを回避する為にモデルベースの方法などが提案されています(参考)。

DNA sequencesの相同性解析ではsequence間の距離がそのまま変異の量であり、系統的、時間的距離を表すものなのでよく使われます。global alignment algorithmとしてNeedleman-Wunsch法、local alignment algorithmとして Smith-Waterman法、BLASTなどが挙げられています。

2.3 Support Vector Machine(SVM)

１つの項目として挙げられていますが、SVMは上記の２つの手法と組み合わせて用いることが出来ます。特徴空間、編集距離の空間それぞれに対応したカーネル(RBFカーネル、k-spectralカーネル、stringカーネル)を用いることで達成できます。カーネルを用いることで高い識別能力を得ることが出来ますが、直感的理解が困難になってしまうという欠点があります。この欠点を補うものとして簡単で解釈可能なカーネルの線形和を用いるmultiple kernel learningがあります*6。

2.4 Model Based Classification

SVMを用いた手法はデータの識別に主眼を置いたものですが、得られたデータを生成する過程を推論しようと言う生成モデルの方法があります。最も単純なものとしてここでは以下の３種類

  • naive bayes (系列を構成するデータの出現確率は互いに独立)
  • k-order Markov Model(データの出現確率はk個前のものに依存)
  • Hidden Markov Model(データの出現確率は隠れた変数に依存する)

を挙げています。より複雑なモデルはグラフィカルモデルとして表現することが出来るでしょう。

3. extension

上で挙げたような伝統的なクラス分類手法の拡張として以下のようなものが挙げられています。

3.1 Early Classification

 異常検知の分野において重要です。心電図のデータ、ネットワークのトラフィックが例としてあげられています。識別器としてはAda-boostを使った事例や異常検知においてcase based reasoning(事例ベース推論)といった手法を使った研究が紹介されています*7。

早さと正確さがトレードオフになるのは想像できますが、定められた正確さに対して可能な限り早く判別を行う手法があるそうで興味深いです。

3.2 Semi-Supervised Sequence Classification

 テキスト分類におけるNaive Bayes, 時系列データに対してのHMM(Hidden Markov Model)を用いた手法 が紹介されています*8。系列データ間の距離でカーネルを作り、クラスタ内にラベルづけられたデータを含むようにクラスタリングし、SVMをかけるという手法も興味深いです。

3.3 Sequence Classification with A Sequence of Labels

 系列データの一部に対してラベルを付与するような問題で、自然言語処理における品詞付与などのラベリング問題がこれに相当します。モデルとしては条件付き確率場(CRF)が通常用いられます。

4. APPLICATIONS OF SEQUENCE CLASSIFICATION

系列データの実例として

  • 4.1 Genomic Data
  • 4.2 Time Series Data
  • 4.3 Text Data

の３つが代表例としてあげられ、参考文献が豊富に紹介されています。

5. CONCLUSION

まとめです。

  • 系列データのうちよく対象とされるのはsimple symbolic sequences とsimple time series dataであり、その他の複雑なデータ形式はまだあまり手がつけられていない。
  • 手法に関しても上で紹介した伝統的なものでないstreaming sequence classification, early classification, semi-supervised classificationは将来に向けての課題となっている

Reference

著者の1人Eamonn Keoghのページ

Rで系列パターンマイニング

 

*1:元論文のリンクが切れています Data Mining Contest - INFORMS コメントで教えていただきました。ありがとうございます。

*2:自然言語処理の分野ではSuffix tree上の確率過程として可変長なk-gramを表現する研究がなされています(Pitman-Yor過程に基づく可変長n-gram言語モデル)。

*3:この辺りは画像認識と共通するものがあります

*4:余談ですが論文では葉っぱ、矢じり、紋章など系列データというより形状データへの適用がされていて興味深いです

*5:Making Time-series Classification More Accurate Using Learned Constraints, Fast Time Series Classification Using Numerosity Reduction 

*6:実装としては複数の言語から呼び出せるライブラリSHOGUNが有名です

*7:Early Fault Classification in Dynamic Systems Using Case-Based Reasoning

*8:半教師ありHMMの実装はStan reference manual(pdf)にも例があります