時系列クラスタリングの研究サーベイ論文を読んだ

Time-series clustering – A decade review」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

背景

近年、ストレージの増加や計算性能の向上により、バイオロジー、ファイナンス、気象などなど様々な分野でデータが大量に蓄積されてきている。それらのデータは必然的に時系列データとして扱うことができ、データマイニングの研究ターゲット(例えば可視化、分類、要約、トレンド解析など)とされてきた。

時系列データのクラスタリングの課題として、一般的に時系列データは大規模なものになりやすくメモリに乗りきらない場合がある、高次元になりやすい、類似度の計算が(時系列データはノイズや外れ値が入っていることが多く、系列ごとに長さが異なることが一般的なため)複雑なものになる、といった点がある。

ほとんどの時系列クラスタリングは3カテゴリーに分類できる。一つ目は Whole time-series clustering。これは個別の時系列データに対してのクラスタリング。二つ目は Subsequence clustering。単一の時系列からスライディングウィンドウなどにより部分系列を複数取り出して、クラスタリングするカテゴリー。三つ目は Time point clustering。これは時間的な近さと値の関係をもとにしてクラスタリングするパターン。

多くの研究では Whole time-series clusteringのパターンがとられており、著者らの分類によると Whole time-series clusteringはさらに3つの特徴で細かく分類できる。shape-basedアプローチは古典的なクラスタリングアルゴリズムを時系列データそのものに対して利用する。feature-basedアプローチはいったん生の時系列データを低次元の特徴量のベクトルに落とし込んでからクラスタリングを行う。model-basedの手法は一つの時系列データを1組のパラメトリックなモデルのパラメータに変換して、複数のパラメータに対してクラスタリング手法を用いてクラスタリングする。

時系列クラスタリングにおいて重要な要素の一つは次元削減である。時系列データはノイズも多く、系列長が長くなるとクラスタリングの計算コストが増えるために適切な次元削減を施してから、クラスタリングする場合がある。
近年よく使われるデータの表現方法は、Data adaptive(任意の長さのセグメントに対してデータを圧縮できる), Non-data adaptive(固定長のデータに適する), Model-based(マルコフモデルのようにモデルでデータを表現する), Data dictated(Model-basedとは対照的に圧縮率はデータに応じて決定される)の4種類に分類できる。それぞれの分類ごとにデータを表現するアルゴリズムがいくつか挙げられている。
そのほかにもclipped seriesと呼ばれる、データの値を平均より上か下かで0/1のbit列として扱うような形式でも、時系列の変化の形をクラスタリングするのには十分であるという研究結果もある。

類似度について

時系列データの類似度はクラスタリングにおいて重要な役割を果たす。何をもとに2つの時系列が似ているとするのかは様々な手法が提案されている。
ノイズが乗っているだけの系列どうしは似ていると判断してほしいし、増幅されているものや、間が途切れていたりする場合も似ている時系列と判断したいかもしれない。
一般的に類似度計算の手法が重視する観点が3つあり、それぞれ異なったアプローチが要求される。

  1. 時間の観点で似ている時系列を見つける。
    単純なユークリッド距離による類似度が用いられる。生の時系列データに対して計算すると高コストのことがあるため、フーリエ変換などを施してから計算されることが多い。
  2. 形状の観点で似ている時系列を見つける。
    いつパターンが起こったのかよりも、形が似ているかどうかを重要視する類似度計算手法。Dynamic time Warpingのような手法が使われる。
  3. 変化の観点で似ている時系列を見つける。
    隠れマルコフモデルやARMA系列のようなモデルが使われる。例えば自己回帰のパターンが似ているモデルどうしは同じタイミングで変化するので似ていることになる。長期間の時系列データに適している。

様々な類似度が提案されているが、計算量と精度のトレードオフの関係もあったり、ユークリッド距離でも十分な精度が得られるといった研究もあるそうなので、どれを使うべきかはケースバイケースなのかもしれない。

4章 Time-series cluster prototype

クラスタを代表する時系列(prototype)をどのように表すかにも大きく分けて3通りある。

  1. medoidをprototypeとする。要するにクラスタ内の分布の中で一番中央値的な時系列を代表とする。
  2. 平均値を使う。固定長の場合は単純に平均値を取れば良い。Dynamic Time WarpingやLongest Common Sub-Sequenceのように可変長の時系列をクラスタリングする距離を用いている場合にも、平均的なprototypeを作成する手法が提案されている。
  3. local searchを使う。medoidを求めて、warping pathで平均prototypeを求める。その後平均prototypeに対して、新しいwarping pathを計算する。この手法がほかの手法よりも精度の良いprototypeが得られるのかは分かってはいないようだ。

5章 時系列クラスタリングアルゴリズム

6種類に分けられる。

  1. 階層クラスタリング
    agglomerative(bottom-up)やdivisive(top-down)な手法によって階層クラスタリングできる。細かい調整ができないため、一般的には他の手法と組み合わせて使われることも多い。
    結果を可視化して分類の理解に役立つことや、事前にクラスタ数を決めなくても良いことなどが、時系列クラスタリングであっても長所である。弱点として計算量が系列数の2乗のオーダーなので小さなデータセットに適用先が限定されることがある。
  2. Partitioning clustering

  3. 事前に設定されたクラスタ数kにより、k個のクラスタに分類する手法。k-Meansがよく知られた手法であるが、時系列データに対してはk-Medoidsアルゴリズムが使われることが多い。
    クラスタに属するか否かを分ける手法に対して、ある度合いでどのクラスタに属するか、という指標でクラスタリングするFCM(Fuzzy c-Means)というような手法も提案されており、話者特定のようなタスクに応用された事例がある。
  4. Model-based clustering
    クラスタごとに1つのモデルを作って、クラスタ内のデータはそのモデルに誤差のノイズが加わって得られたと考えるクラスタリング手法。統計的なアプローチやニューラルネットワークの手法が用いられる。
    一般的にモデルベースのクラスタリングは2つの欠点がある。1つはパラメータを設定する必要があるが、そのパラメータはユーザのある仮定(間違っている可能性がある)に基づいており、低い精度につながる場合があることだ。2点目は大規模データセットに対してモデルの構築に時間がかかり遅い。
  5. Density-based clustering
    DBSCANが有名な手法であるが、データの密度が高い近くの空間に向けてクラスタを拡大していく手法。
    時系列データについては多変量の場合複雑度が高くなるため、あまり使われない。
  6. Grid-based clustering
    データをグリッドセルに分けてからグリッドのクラスタリングを行う手法。時系列データに使われた例は今のところないらしい。
  7. Multi-step clustering
    数は少ないがいくつかの研究では複数の手法を組み合わせて時系列クラスタリングを行っている。例えば、形状の類似度でクラスタリングしてから、時間的な類似度でクラスタリングをかける、といったような今まで挙げた手法を組み合わせて、精度向上や速度向上を目指した手法が提案されている。

6章 時系列クラスタリングの評価手法

時系列クラスタリングの評価手法としては例えば以下のような点に従うことが推奨されている。
・アルゴリズムの評価にはデータセットの複数区間を用いること
・実験を注意深く設計することでバイアスの混入を防ぐこと
・可能ならばデータとアルゴリズムを自由に入手可能とすること
・新しい類似度の指標は簡単で安定しているユークリッド距離のような指標と比較可能であること

大きく分けて可視化と数量的な指標による評価方法が存在する。
数値的なクラスタリング指標にはGround Truthなどとの比較によるExternal indexと、クラスタ内だけの情報によるInternal indexに二分される。

7章 Conclusion

時系列クラスタリングの研究はいろいろと行われているが、一般的なクラスタリング手法が上手く働くのを阻害するような要因が存在している。例えば高次元なデータやノイズ、高い相関などが阻害要因である。

様々な研究は高次元なデータを低次元に落とし込む手法と距離をどのように設定するかをターゲットとして行われている。時系列クラスタリングの研究には図に挙げられている通り4種類の課題が存在しており、それらに対する研究成果がサーベイとして本論文では示されていた。著者らは今後の研究の方向性としては、これらの課題に対して既存の手法もしくは新規手法を組み合わせたハイブリッドなクラスタリングアルゴリズムを考えてい方向に進んでいくだろうと、展望を述べている。

機械学習による化合物テストツールの論文:「PrePeP – A Tool for the Identification and Characterization of Pan Assay Interference Compounds」

PrePeP – A Tool for the Identification and Characterization of Pan Assay Interference Compounds
Maksim Koptelov (University of Caen Normandy); Albrecht Zimmermann (University of Caen Normandy); Pascal Bonnet (University of Orléans); Ronan Bureau (University of Caen Normandy); Bruno Crémilleux (University of Caen Normandy)
https://www.kdd.org/kdd2018/accepted-papers/view/prepep-a-tool-for-the-identification-and-characterization-of-pan-assay-inte

KDD2018の論文読み3本目。Applied Data Science Trackの続き。

製薬分野における機械学習を応用した論文。製薬などの分野で新たな化合物を作った際に、所望の性質を満たしているかを確認する作業がある。
対象物質が増えるとこの作業に非常に多くの時間とリソースがとられてしまう。そこで著者らは化学者向けのツールであるPrePePを作成し、専門家たちがビジュアル的に化合物の様子を探索し、テストの結果予測やその理由などをわかるようにした。

結果としてはiFH(infrequent hitters)と呼ばれるテストに成功しない多数派のクラスをうまく分類が出来ておらず、今後の改良が必要と述べられている。

具体的な機械学習モデルとしては解釈性を持たせるために決定木ベースでランダムフォレストのような形で、予測モデルを作成した。
また、化学の専門家が簡易に使えるように、その界隈で有名なツールを拡張する形でGUI付きのソフトウェアを開発している。

化学の専門知識が足りないためか、なかなかイメージが理解しづらいが、機械学習部分は基本的な内容だった。こういった分野でも機械学習の応用が進みつつあるのだと実感した。

機械学習によるユーザ離脱率の予測論文:「I Know You’ll Be Back: Interpretable New User Clustering and Churn Prediction on a Mobile Social Application」

I Know You’ll Be Back: Interpretable New User Clustering and Churn Prediction on a Mobile Social Application
Carl Yang (University Of Illinois, Urbana Champaign); Xiaolin Shi (Snap Inc.); Jie Luo (Snap Inc.); Jiawei Han (University of Illinois, Urbana Champaign)
https://www.kdd.org/kdd2018/accepted-papers/view/i-know-youll-be-back-interpretable-new-user-clustering-and-churn-prediction

KDD2018の論文読み2本目。産業界の応用事例を集めたApplied Data Science Trackのほうが自分の興味に近いのでそちらにシフトして上から読み始めた。

Snapchatの大規模なデータを集めて、ユーザタイプをクラスタリングにより6種類に分類して、その中の3種類のユーザタイプが平均よりも登録2週間後の離脱率が高いということが分かった。
このクラスタリング結果をもとにして、著者らはユーザ登録後の2週間のデータをもとにして離脱予測のモデルを作成した。

予測モデル作成において、いくつかの課題がある。
データが非常にノイズが多く、変動が大きいため、隠れマルコフモデルのような典型的な時系列モデルでは上手くいかない。また、データは非常にスパースであり、activityの数も非常に偏った(一部のユーザが非常に多くのactivityを行っている)データのため予測が難しいといえる。また、ユーザタイプによって離脱率が異なってくるが、最初の2週間のデータが少ない状態でユーザタイプの情報はそろっていないため、今までのモデルではユーザタイプの情報を使うことはできていなかった。

これらの課題を解決するために、複数のLSTMを組み合わせた予測モデルを用いて離脱率の予測を行っている。具体的には、活動をEmbeddingするレイヤーをLSTMの前に持たせてスパースなデータに対応し、2週間のデータからユーザタイプをクラスタリングシステムで予測し、そのユーザタイプを予測するようなK個のLSTMをトレーニングして、Attentionで着目するLSTMを決めて離脱率を予測するモデルを構築している。

この論文で書かれている離脱率予測のモデルはClusChurnというシステムとして、Snap Inc.のリアルタイム予測システムに組み込まれている。
機械学習による離脱率予測モデルの一例として参考となる論文であると思う。

[KDD2018 論文読み] Smoothed Dilated Convolutions for Improved Dense Prediction

Smoothed Dilated Convolutions for Improved Dense Prediction
Zhengyang Wang (Washington State University); Shuiwang Ji (Washington State University)
https://www.kdd.org/kdd2018/accepted-papers/view/smoothed-dilated-convolutions-for-improved-dense-prediction

KDD2018の論文読みを始めた。1本目。

Image Segmentationの分野でよく使われているdilated convolutionという手法はグリッド状のアーチファクトがでるという課題があった。
Dilated Convolutionは周期的なサンプリングをしてそこに畳み込みフィルターをかけて、並びなおすという操作を行う。並べなおされた後は、隣のピクセルは離れたピクセルの畳み込み後の値なのでアーチファクトが出てしまう。

これを解消するために、著者らはSmoothed Dilated Convolutionsという手法を提案し、公開データセットにて通常のDilated Convolutionに比べて精度が向上していることと、実際にグリッド状のアーチファクトが軽減されていることを確かめた。

具体的には、Group Interaction Layerという各Dilated Convolutionフィルタ間の全結合ネットワークを用いて、各フィルタ間の関係性を学習させている。

また、Dilated Convolutionをかける前に、Separable and Shared Convolutionという各チャネルごとにフィルタをかける形の処理を行うことで、Dilated Convolution処理の前に関係性を学習することができる。

PSCAL VOC2012データセットを用いて評価しており、全体的に過去の高性能モデルよりも良い結果が出ている。また、ERF可視化という方法でグリッド状のアーチファクトが軽減されていることを確認している。

Batch Normalization と Dropout は併用しない方が良いという話

Deep Learningのモデルを訓練していたところ、思うようにvalidation lossが下がらないことがあった。色々と調べた結果、Batch NormalizationとDropoutを併用していたのが原因であったので、誰かの為に書いておく。

この論文その解説にある通り、Batch NormalizationとDropoutを併用するとパフォーマンスが悪化することがある。原因は、「Dropoutを行うことで学習時と評価時で分散が変わってしまう一方、Batch Normalizationは学習で得られた分散を評価時もキープしてしまうため齟齬が生じることが原因」とあり、言われてみればなるほどという感じである。

結論としては、DropoutかBatch Normalizationのどちらか一方だけで試してみてvalidation lossを下げようとするのが良さそう。Deep Learningを使えばすべて解決するわけではなく、パラメータチューニングやモデル構造のチューニングが良いパフォーマンスを出すためには必要だと分かる事例の一つ。

ニューラルネットワークを利用した決定木:Deep Neural Decision Trees

引き続き、機械学習の解釈性についての論文を読んだ。今回読んだのは、「Deep Neural Decision Trees (WHI ’18)」。著者による実装のページはここ

決定木とニューラルネットワークを用いる他の論文などと同様に、決定木の解釈性とニューラルネットワークの精度の高さの両立を狙っている。特に表形式データの分類に有効と著者らは述べている。

この論文では、微分可能なsoft binningという関数を入力データにかませて、学習を重ねることでsoft binningのバイアス項の値を見ることで、各フィーチャーに対してどこで決定木を分岐すれば良いかが分かるという手法を提案している。soft binningで決定木の分岐を表現して、そのあとにクロネッカー積を取ることですべての分岐の組み合わせを網羅的に調べることが出来る。すべての層は微分可能なため、通常のバックプロパゲーションによりネットワークの学習を行うことが出来る。

著者らは複数の表形式データセットに対して、決定木、ニューラルネットワーク、Deep Neural Decision Tree、の三手法で精度評価を行っている。結果はデータセットによってまちまちだが、基本的にニューラルネットワークと同等程度の精度が出ている。実験の結果、DNDTでは全く推論に使われない特徴が検出できるなどの副次的な成果も述べられている。

GPUによる速度性能の確認も行われており、フィーチャー数が増えた場合でもCPUと比較して、あまり実行時間が増えないようになっている。

今後も機械学習の解釈性関連の論文を色々と読んでいく予定。

GPSデータによる交通事故リスク予測:Learning Deep Representation from Big and Heterogeneous Data for Traffic Accident Inference

読んだ論文のメモ。Learning Deep Representation from Big and Heterogeneous Data for Traffic Accident Inference (AAAI ’06)という論文を読んだ。

内容はGPSデータから交通事故のリスクレベルを予測するというもの。GPSデータには東京のデータが用いられている。GPSデータは精度自体やビルの陰や建物の中にいるなどの理由でノイズが乗っていると考えられる。この研究ではauto encoderを利用してGPSデータからノイズ除去を行ってからロジスティクス回帰に入力して事故リスクの予測をしている。

実験では、単純な決定木・ロジスティクス回帰・SVMと提案手法を比較して、提案手法がリスクレベルをよく予測出来ていることを確認している。また、主観評価として夜になると事故リスクがさがる、昼間は都心部の事故リスクが高い、東京・横浜間の道路が他に比べて事故リスクが高い、など我々の感覚に近い結果が出ていることも確認している。

スマートフォンの普及によりGPSデータは簡単に取得できるようになっているため、こういったタイプの研究やアプリケーションは今後増えていくだろうと考えられる。

 

機械学習によるメモリアクセス予測:Learning Memory Access Patterns

ICML 2018の論文リストを眺めていて、目についたタイトルの論文を読み始めた。まず最初に「Learning Memory Access Patterns」という論文を読んだ。この論文はRNNを用いてメモリアクセスパターンを予測することで、プリフェッチの精度を上げてパフォーマンス向上を目的としている。ある種の調査によると、CPUサイクルの50%以上はメモリからのデータを待っているともいわれており、プリフェッチの精度を上げることはコンピュータの性能向上に寄与する可能性が高い。

アイデアとしては、メモリアドレス空間をvocabralyとして扱う。これは、アドレス空間は非常に広大だが、実際にプロセスによってアクセスされる個所は局所的であり、これを予測しようとすると非常に疎なデータであるため正規化した際に有用な情報が失われてしまうためである。また、現在アクセスされているアドレスと次の時間にアクセスされるアドレスの差分(デルタ)を正解ラベルとして用いることで、デルタは通常小さいため、訓練が上手くいくというアイデアが用いられている。

また、単純にLSTMを使うだけでなく、前処理としてクラスタリングを行ってからLSTMにかけることで、プログラムのローカル構造(例えば構造体のアクセスや配列の走査)などの特徴を掴みやすくなったと述べている。

著者らは様々なデータセットを用いて、既存のメモリプリフェッチ機構とprecision/recallを比較しているが、クラスタリング+LSTMが良い性能が出ることを確認している。

Hit/Missの性能が良いのは理解できなくもないが、気になるのはやはり速度性能である。これは推測だが、おそらく既存のメモリプリフェッチ機構を置き換えるにはLSTMの推論は処理が重いのではないかという気がする。著者らは実際にH/W実装はまだ行っておらず、速度性能については今後の課題だと述べている。今後TPUのようなAIプロセッサの技術革新が進んでいけば、将来的には既存のプリフェッチ機構を置き換える可能性を秘めているかもしれない。

論文では、以前話題になったB-treeよりも高速なインデックス構造を機械学習で作成した「The Case for Learned Index Structures」という論文があったが、今後は既存のコンピュータアーキテクチャ分野にも機械学習が進出する未来がやってくるのかもしれない。

機械学習の解釈性とパフォーマンスの両立を目指して:Human-in-the-Loop Interpretability Prior

機械学習、特にニューラルネットワークなどのアルゴリズムを使った場合、出力された結果は何万・何十万次元のベクトル演算の結果であり、人間が直接解釈することは難しい。ニューラルネットワークの解釈性については近年様々な研究が行われている。一般的に解釈性の低いモデルは高い精度を出すことが多く、適度な解釈性と適度な精度のバランスが取れたモデルが必要なケースが考えられる。

この論文「Human-in-the-Loop Interpretability Prior」は機械学習モデルに対して人間がある尺度(論文ではHIS:Human Interpretability Scoreという、人間がモデルに従って入力から出力を予測するのにかかった時間の逆数)を事前確率として、データXが与えられた際にそのデータを最も適切に説明できるモデルMをp(M|X)をMAP推定することにより選択するという手法を用いている。著者らは4種類のデータセットで実験を行っており、タスクごとにreasonableな解釈性を持ったモデルを選択できていることを確かめている。

読んだ感想としてはHISの決め方が果たして、人間がかかった時間の逆数という尺度を使うのは解釈性の尺度として適切なのか?といった疑問や、新しいモデルを作るたびにユーザの評価が必要になり汎用性は低そうに思った。HISを何らかの尺度(例えば計算時間や消費メモリ)によって算出することが出来れば、この手法を人の手を介さずに適用することも可能なのではないかと考える。

大規模データのクラスタリングには Mini Batch K-Means を使うべきという話

タイトルの通りですが、大規模データをクラスタリングする際には単純なK-Means法ではなく、Mini Batch K-Means法を使うべきという話です。

とある大規模データ(150万件ほどの文章ベクトル)をクラスタリングしたいことがあったのですが、単純にScikit-learnのK-Means法に投げてクラスタリングを走らせていたところ、数時間経っても一向に終わる気配がありませんでした。色々と調べていると、大規模データのクラスタリングにはMini Batch K-Means法を使うべきという記述を見つけました。公式ドキュメントによると、大体1万件を超えるデータをクラスタリングする場合にはMini Batch K-Meansを使うべきとのことです。

APIとしては単純にKMeansをMiniBatchKMeansに置き換えれば動きます。理論的な背景としては、論文 “Web Scale K-Means clustering” D. Sculley, Proceedings of the 19th international conference on World wide web (2010)に書かれており、ざっと読んだところランダムサンプリングしてクラスタの中心を計算していくのですが、KMeansとは異なり、各点ごとに中心を逐次的にアップデートしていくことで計算量を減らしています。

論文に載っていた速度比較ですが、圧倒的にMiniBatchKMeansが高速です。図の青がMiniBatchKMeans、赤がKMeans、横軸が時間。

この手法を使ったところ、KMeansでは数時間経っても終わらなかったクラスタリングが、MiniBatchKMeansでは数分程度で終わりました。ということで、大規模データのクラスタリングにはMIniBatchKMeansを使うべきということを学んだという話でした。