(57)【要約】【課題】断続的に特徴が現れる時系列データについて時間フレームの間隔（ギャップ）を許容してパターンを抽出することができること。【解決手段】時系列パターン抽出装置１０は、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成し、作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する。【選択図】図４
2016153983.tif 000002
【特許請求の範囲】
【請求項１】
非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成部と、
前記作成部によって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出部と、
を有することを特徴とする時系列パターン抽出装置。
【請求項２】
前記抽出部は、同時に出現しやすいデータの集合を表す基底行列と前記パターンがどの時間フレームに出現しているかの重みを表す重み行列とを順に所定の更新式でそれぞれ更新する更新処理を、所定の回数分だけ繰り返し、該所定の回数を繰り返した後の基底行列および重み行列を前記パターンとして抽出することを特徴とする請求項１に記載の時系列パターン抽出装置。
【請求項３】
前記作成部は、各時間フレームに所定のデータが出現する回数または出現の有無が行列の要素となる行列であって、各行または各列のいずれか一方が所定のデータの種類、他方が時間フレームとなる行列を作成することを特徴とする請求項１または２に記載の時系列パターン抽出装置。
【請求項４】
時系列パターン抽出装置によって実行される時系列パターン抽出方法であって、
非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成工程と、
前記作成工程によって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出工程と、
を含んだことを特徴とする時系列パターン抽出方法。
【請求項５】
非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成ステップと、
前記作成ステップによって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出ステップと、
をコンピュータに実行させることを特徴とする時系列パターン抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列パターン抽出装置、時系列パターン抽出方法および時系列パターン抽出プログラムに関する。
【背景技術】
【０００２】
実世界には、文書データや購買ログ、音、画像など、行列で表現できる多くのデータや信号が存在する。それらは多くの場合、頻度や個数、スペクトログラム、画素値など、非負値で表現できるデータである。例えば、文書データであれば各文書における各単語の出現頻度を行列で表現することができ、音楽信号は各時間における各周波数成分の強さというかたちで表現できる。
【０００３】
このような０または正の値を持つ行列を解析する一手法として、非負値行列因子分解（ＮＭＦ:Non-negative  Matrix  Factorization）が知られている（例えば、非特許文献１）。ＮＭＦは、入力データを行列表現できれば、データの種類に関わらず適用できるため、幅広い種類のデータに応用できる。ＮＭＦによる解析結果で得られるのは、幾つかの頻出パターンであり、例えば、文書データからは共起しやすい単語のパターンを得ることで、「経済」や「スポーツ」などの潜在的なトピックを得ることができる（例えば、非特許文献２）。また、複数音源の信号が混在したスペクトログラムから各音源のパワースペクトルを抽出することによる雑音除去や音源分離への応用も提案されている（例えば、非特許文献３）。
【０００４】
ＮＭＦは、目的に合わせて拡張することでさらに幅広い様々な応用が提案されている。例えば、上述の文書データに時間情報も加えたような、３次元以上のデータを行列で表現すると、情報が失われてしまう。そこで、高次元のデータを行列ではなくテンソルとして扱い、ベクトルに分解する手法であるＮＴＦ（Non-negative  Tensor  Factorization）が提案されている(例えば、非特許文献４)。また、ネットワーク機器の各ログメッセージを、メッセージの種類（テンプレート）とホスト情報、時刻の３つの次元でテンソルとして表現し、２つの行列と１つのテンソルに分解するＬＴＦ（Log  Tensor  Factorization）を提案している（例えば、非特許文献５）。分解によって、単一ホストで同時に発生するテンプレートのグループと、同時に発生するテンプレートグループとそれが起きたホストの組の集合であるネットワークイベントを抽出する。
【０００５】
ならびにＮＭＦを時間的に遷移する基底も抽出できるように拡張したものとして、畳み込み非負値行列因子分解（ＣＮＭＦ：Convolutive  Non-negative  Matrix  Factorization）が提案されており、音響信号などの時系列データからのパターン抽出に応用されている（例えば、非特許文献６）。ＣＮＭＦは、各時間の観測データベクトルを並べることで行列の形式で表現された時系列データに対して、指定した数の時間推移を考慮した基底に分解することにより、時間的に連続するパターン抽出を実現した点が特徴的な手法である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Daniel  D.  Lee  &  H.  Sebastian  Seung,  “Learning  the  parts  of  objects  by  non-negative  matrix  factorization”,  Nature,  401,  pp.788-791,  1999
【非特許文献２】Wei  Xu,  Xin  Liu,  Yihong  Gong,  “Document  Clustering  Based  On  Non-negative  Matrix  Factorization”,  SIGIR'03,  pp.267-273,  2003
【非特許文献３】Paris  Smaragdis,  Judith  C.  Brown,  “Non-Negative  Matrix  Factorization  for  Polyphonic  Music  Transcription”,  In  Proc.  2003  IEEE  Workshop  on  Applications  of  Signal  Processing  to  Audio  and  Acoustics  (WASPAA2003),  pp.177-180,2003
【非特許文献４】Amnon  Shashua,  Tamir  Hazan,  “Non-Negative  Tensor  Factorization  With  Applications  to  Statistics  and  Computer  Vision”
【非特許文献５】Tatsuaki  Kimura,  Keisuke  Ishibashi,  Tatsuya  Mori,  Hiroshi  Sawada,  Tsuyoshi  Toyono,  Ken  Nishimatsu,  Akio  Watanabe,  Akihiro  Shimoda,  Kohei  Shiomoto,  “Spatio-temporal  Factorization  of  Log  Data  for  Understanding  Network  Events”,  IEEE  INFOCOM  2014-IEEE  Conference  on  Computer  Communications
【非特許文献６】Paris  Smaragdis,  “Non-negative  Matrix  Factor  Deconvolution;  Extraction  of  Multiple  Sound  Sources  from  Monophonic  Inputs”,  Independent  Component  Analysis  and  Blind  Signal  Separation,  Lecture  Notes  in  Computer  Science,  2004,  Volume  3195,  pp.494-499,  2004
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の従来技術では、音など連続した時間区切りで解析を行うものはＣＮＭＦの手法で問題ないが、機器のログなど断続的に特徴が現れる時系列データについては時間フレームの間隔（以降ギャップと表記）を許容してパターンを抽出することができないという課題がある。
【０００８】
つまり、ＣＮＭＦは基底としてＮ×Ｊ行列（ただし、Ｊは何フレームに亘るパターンを抽出するかを定めるパラメータであり、以降フレーム幅と呼ぶ）を想定することで、時間方向に変化していくパターンを捉えることができているが、ＣＮＭＦは音響信号など連続して特徴が現れるデータを扱うために拡張されたものであるため、機器のログなど断続的に特徴が現れるデータを扱う上では、任意のギャップを許容してパターンを抽出することができないという問題点を抱えている。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明の時系列パターン抽出装置は、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成部と、前記作成部によって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出部と、を有することを特徴とする。
【００１０】
また、本発明の時系列パターン抽出方法は、時系列パターン抽出装置によって実行される時系列パターン抽出方法であって、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成工程と、前記作成工程によって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出工程と、を含んだことを特徴とする。
【００１１】
また、本発明の時系列パターン抽出プログラムは、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する作成ステップと、前記作成ステップによって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する抽出ステップと、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、断続的に特徴が現れる時系列データについて任意のギャップを許容してパターンを抽出することができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】図１は、サーバのイベントログにＮＭＦを適用した場合におけるイベントログの行列表現とＮＭＦ分解後の基底行列および重み係数行列を示したイメージ図である。
【図２】図２は、ＣＮＭＦによって抽出される基底行列を示したイメージ図である。
【図３】図３は、本実施形態によって抽出される基底行列を示したイメージ図である。
【図４】図４は、本実施形態に係る時系列パターン抽出装置の構成を示すブロック図である。
【図５】図５は、可視化した２年分のログの一例を示す図である。
【図６】図６は、可視化した２時間分のログの一例を示す図である。
【図７】図７は、可視化した３０分分のログの一例を示す図である。
【図８】図８は、可視化した３０分分のログの一例を示す図である。
【図９】図９は、１列５分の行列から抽出されたパターンの一例を示す図である。
【図１０】図１０は、１列２分の行列から抽出されたパターンの一例を示す図である。
【図１１】図１１は、本実施形態に係る時系列パターン抽出装置における時系列パターン抽出処理の流れを示すフローチャートである。
【図１２】図１２は、時系列パターン抽出プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１４】
以下に、本願に係る時系列パターン抽出装置、時系列パターン抽出方法および時系列パターン抽出プログラムの実施形態を図面に基づいて詳細に説明する。なお、この実施形態により本願に係る時系列パターン抽出装置、時系列パターン抽出方法および時系列パターン抽出プログラムが限定されるものではない。
【００１５】
本願の実施形態の説明を行う前に既存のＮＭＦおよびＣＮＭＦについて説明する。ＮＭＦは、一般的な次元削減アルゴリズムで、パターン認識やデータマイニングに広く利用されている（非特許文献１）。まず、非負値の観測データベクトルを並べて行列で表現されたデータＹ＝［ｙ１，ｙ２，・・・，ｙＭ］∈ＲＮ×Ｍが与えられるとする。ここで、ＲＮ×Ｍは、Ｎ行Ｍ列で要素が実数値の行列全体の集合を表す。ＮＭＦでは、これらの観測データベクトルがＫ個の基底ベクトルの重み付き和によって表されたものとみなし、Ｋ個の基底ベクトルと重み係数ベクトルを推定する。すなわち、非負値の基底ベクトルを並べた行列をＨ＝［ｈ１，ｈ２，・・・，ｈＫ]∈ＲＮ×Ｋ、非負値の重み係数ベクトルを並べた行列をＵ＝［ｕ１，ｕ２，・・・，ｕＭ］∈ＲＫ×Ｍとすると、ＮＭＦは、下記（１）式となるように、近似的に分解するアルゴリズムである。
【００１６】
【数１】
2016153983.tif 000003
【００１７】
観測行列を２つの非負値行列の積で表すというＮＭＦの基本概念はＰａａｔｅｒｏらによって提案されている。Ｐａａｔｅｒｏらは誤差行列Ｅ＝Ｙ−ＨＵのＦｒｏｂｅｎｉｕｓノルム（下記（２）式参照）でＨＵのＹからの乖離度をコスト関数として定義し、その最小化問題を解くことで最適なＨとＵを求めることを提案している。
【００１８】
【数２】
2016153983.tif 000004
【００１９】
ＮＭＦの解法には幾つかの数学的解法があるが、補助関数とＪｅｎｓｅｎの不等式により導出した乗法的更新ルールは広く利用されている。ＤＥＵを最小化する乗法更新の式は下記（３）式のようになる。
【００２０】
【数３】
2016153983.tif 000005
【００２１】
ＮＭＦでは、ＨとＵをランダムな値で初期化し、更新式に従って更新する。更新を反復することで徐々にコスト関数を小さくしていき、最適な解を得る。図１にＮＭＦを例としてサーバのイベントログに適用したイメージを示す。まずログを一定の時間フレームで区切り、ログメッセージの種類数（Ｎ）、時間フレームの数（Ｍ）の形の行列Ｙで表現する。ここでは、各時間フレームにそれぞれのログメッセージが出現する回数が行列の要素になる。ただし、出現回数に１を足した値の対数や出現の有無のバイナリ値（出現すれば１、そうでなければ０）を要素に用いても構わない。この時、基底行列Ｈは同時に出現しやすいログメッセージの集合を意味し、重み係数行列Ｕはそのパターンがどの時間フレームに出現しているかの重みを表す。図１においては、Ｌ１，Ｌ２，Ｌ３，Ｌ６が同時に出現しやすく、これらが１つの基底となる。
【００２２】
次に、ＣＮＭＦについて説明する。ＮＭＦは、Ｎ×１行列を想定しているため、時系列データの基底を抽出するとき、時間的に遷移するような基底を抽出することができない。その点を克服するために、ＮＭＦを拡張した手法としてＣＮＭＦが提案されている。基底として非負のＮ×Ｊ行列（ただし、１＜Ｊ＜Ｋ）を想定することで、時間方向に連なったスペクトル構造のパーツが混合したモデルを立てることができる。すなわち、スペクトルが時間方向に変化していくパターン自体をパーツと捉え、観測データを構成しているスペクトログラムパーツを抽出し、それに基づく分解表現を得ることが出来るようになる。観測行列をＹとすると、下記（４）式となるように、Ｈ１・・・，ＨＴ−１とＵを求めるのがＣＮＭＦである。また、下記（４）式に示す演算子は、例えば、下記（５）式のように、行列の成分を全てｔ列分右にシフトし、値がなくなった列の要素を全て０で埋める演算子とする。
【００２３】
【数４】
2016153983.tif 000006
【００２４】
【数５】
2016153983.tif 000007
【００２５】
ここで、Ｔはパターンの時間フレームの数を表すパラメータであり、Ｔ＝１のときはＮＭＦと等しくなる。この時、Ｙの近似を下記（６）式のように定義すると、ＮＭＦの場合と同様に最小化する距離をＦｒｏｂｅｎｉｕｓノルムとすると、更新式は下記（７）式のように表される。
【００２６】
【数６】
2016153983.tif 000008
【００２７】
【数７】
2016153983.tif 000009
【００２８】
図２にＣＮＭＦによる３列に亘るパターンの抽出例を示す。左の行列では、１列目にＬ１，Ｌ３、２列目にＬ２，Ｌ４、３列目にＬ５，Ｌ６が出現しており、同じ傾向が６列目以降にも見られる。ＣＮＭＦはこのように連続する時間フレームに亘って順に出現するログメッセージ群をパターンとして捉える。結果、基底行列Ｈとして、パターンのフレーム幅（Ｊ）×パターン数（Ｋ）の行列が得られる。
【００２９】
ＣＮＭＦは基底としてＮ×Ｊの行列を想定することで、時間方向に変化していくパターンを捉えることができている。しかし、ＣＮＭＦは画像処理分野から生まれた手法を転用したＮＭＦを音響信号を扱うために拡張されたものであるため、他のデータを扱う上での問題点を抱えている。例えば、機器のログデータを行列やテンソルで表現するには、図３のようにログデータを一定の時間で区切るなどする必要がある。図３のように各行がログメッセージの種類、各列が時間フレームになるように行列化した場合、あるログが出現してから他のログが出現するパターンが潜在的に存在するとしても、これは必ずしもその行列で連続する列にそれらが出現するとは限らない。なお、図３は一列１０秒の行列でログデータを表現したものである。
【００３０】
例えば、ログＬ１，Ｌ３，Ｌ４が出現した２０秒後にＬ２，Ｌ４さらに２０秒後にＬ５，Ｌ６が出現するようなパターンがある。図３の例を用いて説明すると、１列目でＬ１，Ｌ３，Ｌ４が出現し、３列目でＬ２，Ｌ４が出現し、５列目でＬ５，Ｌ６が出現しており、６列目以降でも、例えば、７列目でＬ１，Ｌ３，Ｌ４が出現し、９列目でＬ２，Ｌ４が出現し、１１列目でＬ５，Ｌ６が出現している。図３に例示するように、一列１０秒の行列でログデータを表現した場合、これらが出現している列は隣接しない。この様な場合、従来のＣＮＭＦではこのパターンを捉えることができない。
【００３１】
本願では、ＣＮＭＦの課題を解消するため、時間フレームの間隔を任意に設定できるように、ＣＮＭＦによる分解の式を下記（８）式のように改良した。
【００３２】
【数８】
2016153983.tif 000010
【００３３】
ここで、ｓｔはシフト幅を任意に設定するためのパラメータである。ｓｔはｔ＋１番目の時間フレームに対応するシフト幅を表し、Ｔ個の時間フレームに対応させるために、パラメータベクトルｓ＝［ｓ0，ｓ1，・・・，ｓＴ−１］として設定するものである。例えば、図３の例では、ｓ＝［０，２，４］と設定しているものとする。この改良により、ｓの設定によって任意のギャップを許容できるようＣＮＭＦが拡張された。また、シフト幅を１つずつ変化するように設定すればＣＮＭＦと等しくなる。つまり、ｓ＝［０，１,・・・，Ｓ］と設定すれば、ＣＮＭＦでＴ＝Ｓと設定した場合に相当する。ここで、Ｙの近似であるＹ~を下記（９）式のように定義した場合、最小化する距離をＦｒｏｂｅｎｉｕｓノルムとすると更新式は以下の（１０）式のように表される。
【００３４】
【数９】
2016153983.tif 000011
【００３５】
【数１０】
2016153983.tif 000012
【００３６】
［実施形態］
以下の実施形態の説明では、実施形態に係る時系列パターン抽出装置の構成及び処理の流れを順に説明し、最後に実施形態による効果を説明する。
【００３７】
［時系列パターン抽出装置の構成］
まず、図４を用いて、時系列パターン抽出装置１０の構成を説明する。図４は、本実施形態に係る時系列パターン抽出装置の構成を示すブロック図である。図４に示すように、時系列パターン抽出装置１０は、作成部１１、抽出部１２および結果出力部１３を有する。以下に、これらの各部の処理を説明する。
【００３８】
作成部１１は、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成する。具体的には、作成部１１は、各時間フレームに所定のデータが出現する回数または出現の有無が行列の要素となる行列であって、各行または各列のいずれか一方が所定のデータの種類、他方が時間フレームとなる行列を作成する。
【００３９】
例えば、上記した図３の例では、各時間フレームにログデータが出現する回数が行列の要素となる行列であって、各行がログメッセージの種類、各列が時間フレームとなる行列である。また、一列が１０秒の時間フレームで区切られた行列である。作成部１１は、特に本発明に関連するものとして、入力データ行列化部１１ａおよび初期化部１１ｂを有する。
【００４０】
入力データ行列化部１１ａは、非負値データを格納したベクトルが時系列順に並んだ観測データを受け取って行列化する。初期化部１１ｂは、行列のサイズとして与えられる、取り出したいパターン数を表すパラメータＫと時間間隔を調整するパラメータｓとに基づいて基底行列と重み行列を初期化する。
【００４１】
例えば、行列化の際には、各時間の観測データベクトルのサイズをＮ、ベクトルの数をＭとすると、各時間のベクトルを並べてＮ×Ｍの行列とする。また、初期化の際には、基底行列は、ｓ＝［ｓ０，ｓ１，・・・，ｓＴ−１］とすると、Ｔ個のＮ×Ｋ行列のＨｓ０，Ｈｓ１，・・・，ＨｓＴ−１とＫ×Ｍの行列を作り、乱数を使ってランダムな数値を入れて初期化する。
【００４２】
抽出部１２は、作成部１１によって作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する。
【００４３】
例えば、図３の例を用いて説明すると、抽出部１２は、時間間隔として、シフト幅ｓ＝［０，２，４］が設定されているものとし、１列目と３列目と５列目とシフトして３つの時間フレームの組を取得し、７列目と９列目と１１列目とシフトして３つの時間フレームの組を取得する。１２列目以降も同様に時間フレームの組を取得する。
【００４４】
ここで、図３に例示するように、時間フレームについて、１列目でＬ１が「１」回、Ｌ３が「１」回、Ｌ４が「２」回出現し、３列目でＬ２が「１」回、Ｌ４が「２」回出現し、５列目でＬ５が「２」回、Ｌ６が「１」回出現している。また、６列目以降でも、例えば、７列目でＬ１が「１」回、Ｌ３が「１」回、Ｌ４が「１」回出現し、９列目でＬ２が「１」回、Ｌ４が「２」回出現し、１１列目でＬ５が「２」回、Ｌ６が「１」回出現している。このため、１列目と３列目と５列目とシフトして３つの時間フレームの組を取得し、７列目と９列目と１１列目とシフトして３つの時間フレームの組同士の間で現れるパターンとして、１フレーム目にＬ１，Ｌ３，Ｌ４が出現し、２フレーム目にＬ２，Ｌ４が出現し、３フレーム目にＬ５，Ｌ６が出現するというパターンを抽出する。
【００４５】
具体的には、抽出部１２は、同時に出現しやすいデータの集合を表す基底行列とパターンがどの時間フレームに出現しているかの重みを表す重み行列とを順に所定の更新式でそれぞれ更新する更新処理を、所定の回数分だけ繰り返し、該所定の回数を繰り返した後の基底行列および重み行列を前記パターンとして抽出する。抽出部１２は、特に本発明に関連するものとして、基底行列更新部１２ａ、重み行列更新部１２ｂおよび反復終了判定部１２ｃを有する。具体的には、抽出部１２は、基底行列と重み行列を順にそれぞれの更新式で更新し、指定された反復回数分だけ更新処理を繰り返す。
【００４６】
基底行列更新部１２ａは、上記（１０）式の左の式に基づき、基底行列の更新を行う。また、重み行列更新部１２ｂは、上記（１０）式の右の式に基づき、重み行列の更新を行う。
【００４７】
また、反復終了判定部１２ｃは、基底行列と重み行列を順にそれぞれの更新式で更新した後に、指定された反復回数分だけ更新処理を行ったか否かを判定する。そして、反復終了判定部１２ｃは、指定された反復回数分だけ更新処理を行っていないと判定した場合には、基底行列更新部１２ａおよび重み行列更新部１２ｂに対して、基底行列、重み行列の更新をそれぞれ指示する。また、反復終了判定部１２ｃは、指定された反復回数分だけ更新処理を行ったと判定した場合には、後述の分解行列出力部１３ａに対して、更新を反復回数分だけ繰り返した後の最終的な基底行列および重み行列を出力する。
【００４８】
結果出力部１３は、抽出部１２によって抽出されたパターンを出力する。結果出力部１３は、特に本発明に関連するものとして、分解行列出力部１３ａを有する。分解行列出力部１３ａは、更新を反復回数分だけ繰り返した後の最終的な基底行列および重み行列を出力する。
【００４９】
［適用例］
ここで、本発明の有効性を検証するために行った、実データを用いた実験の実験結果について説明する。検証用の実データとして、実運用されているサーバ約１０台構成のシステムから出力されたイベントログ約２年分を利用した。予め、ＩＰアドレスやホスト名など、メッセージ中のパラメータ部分以外が同じメッセージを１つのＩＤにまとめ、イベントログをＩＤ化した。その結果、６０７４９２件あったログは３０８種類のメッセージに集約された。また、図５〜図８は、横軸を時刻、縦軸をログメッセージの種類として、それぞれのログメッセージが出現した時間に点をプロットしたものである。図５は、可視化した２年分のログの一例を示す図であり、図６は、可視化した２時間分のログの一例を示す図であり、図７および図８は、可視化した３０分分のログの一例を示す図である。
【００５０】
図５〜図８では、すべて縦軸はログメッセージの種類、横軸はＵＮＩＸ（登録商標）時間であり、それぞれの時間に出現したログメッセージの座標に点をプロットしている。このシステムは毎日アプリケーションの起動、停止を行ったり、週に一度システムの再起動を行なったりといった、定期的な処理が行われており、それに付随してログも出力されている。
【００５１】
例えば、図５の下部に点が密集しているのは、毎日行われるアプリケーションの起動、
停止に起因するログメッセージが出力されているのを表しており、下部から中央あたりに何本も棒状に点が並んで見えるのは，週に一度再起動するときに大量のログメッセージが一度に出力されていることを示している。
【００５２】
図６〜図８に示されるログは、図５の一部を切り取ったものである。図６の例では、サーバ再起動が行われた時間のログ２時間分（５：００−７：００）を切り出してプロットしたものであり、ＩＤ６０から１２０のログが一斉に出力された後、ＩＤ１２５から１４５のログがまとまって出力される流れが２回確認できる。この流れは、図５では中央よりやや下の部分に見られ、２年を通じて毎週出力されている。
【００５３】
一方、図７および図８は、ある３０分（２３：３０−２４：００）を切り取ってプロットしたものであって、図７と図８はそれぞれ別の日の３０分のログであり、図７および図８の両者のログにおいては、ＩＤ１４から１９のログが出力された約５分後にＩＤ１４と１８，２０から２４のログメッセージが出力された流れが確認できる。こちらは図６では下部の部分に見られ、基本的に毎日出力されている部分である。
【００５４】
実験では、このデータを一列２分または５分に設定して行列化した。ログデータを２分毎に区切り、その２分内で出現すれば１、そうでなければ０という値が要素に入るように、ログメッセージの種類をＮ、時間フレームの数（約２年／２分）をＭとして、Ｎ×Ｍの行列を作成し、一列５分の行列も同様に作成した。
【００５５】
まず、基底数Ｋ＝１０、パラメータ更新反復回数を１００、シフト幅を定めるパラメータｓ＝［０，２］として実験を行った。この実験の結果、得られた基底の１つの中身を図９に示す。図９は、１列５分の行列から抽出されたパターンの一例を示す図である。ここでは、分解後の基底行列Ｔ０，Ｔ２の各基底の列ベクトルの中で重みの大きさの上位のメッセージ群を取り出している。なお、ここで挙げているメッセージ群はほぼ同じ重みをもっている。
【００５６】
１フレーム目ではＩＤ１５−１９のメッセージが出現し、２フレーム目にＩＤ１４，１８，２０−２４のメッセージが出力されるようなパターンが抽出されている。これは図７に示される、毎日行われているサーバ再起動に関するパターンである。
【００５７】
次に、１列２分の設定の行列にも本実施形態の処理を適用した。Ｋ＝１０、パラメータ更新反復回数を１００、シフト幅を定めるパラメータｓ＝［０，２］として実験を行った。この実験の結果、得られた基底の１つの中身を図１０に示す。この基底では、１フレーム目では、ＩＤ５９−１１３のメッセージが出現し、２フレーム目にＩＤ１３２−１３７のメッセージが出力されるようなパターンが抽出されている。これは、図６に示される、毎日行われているサーバ再起動に関するパターンである。
【００５８】
［時系列パターン抽出装置の処理の一例］
次に、図１１を用いて、時系列パターン抽出装置１０における処理の流れを説明する。図１１は、本実施形態に係る時系列パターン抽出装置における時系列パターン抽出処理の流れを示すフローチャートである。
【００５９】
図１１に示すように、時系列パターン抽出装置１０の入力データ行列化部１１ａは、非負値データを格納したベクトルが時系列順に並んだ観測データを入力データとして受け付けると（ステップＳ１０１）、該入力データを行列化する（ステップＳ１０２）。例えば、行列化の際には、各時間の観測データベクトルのサイズをＮ、ベクトルの数をＭとすると、各時間のベクトルを並べてＮ×Ｍの行列とする。
【００６０】
そして、初期化部１１ｂは、行列のサイズとして与えられる、取り出したいパターン数を表すパラメータＫと時間間隔を調整するパラメータｓとに基づいて基底行列と重み行列を初期化する（ステップＳ１０３）。例えば、初期化の際には、基底行列は、ｓ＝［ｓ０，ｓ１，・・・，ｓＴ−１］とすると、Ｔ個のＮ×Ｋ行列のＨｓ０，Ｈｓ１，・・・，ＨｓＴ−１とＫ×Ｍの行列を作り、乱数を使ってランダムな数値を入れて初期化する。
【００６１】
続いて、基底行列更新部１２ａは、上記（１０）式の左の式に基づき、基底行列の更新を行う（ステップＳ１０４）。そして、重み行列更新部１２ｂは、上記（１０）式の右の式に基づき、重み行列の更新を行う（ステップＳ１０５）。その後、反復終了判定部１２ｃは、基底行列と重み行列を順にそれぞれの更新式で更新した後に、指定された反復回数分だけ更新処理を行ったため反復を終了するか否かを判定する（ステップＳ１０６）。
【００６２】
そして、反復終了判定部１２ｃは、反復を終了しないと判定した場合には（ステップＳ１０６否定）、基底行列更新部１２ａおよび重み行列更新部１２ｂに対して、基底行列、重み行列の更新をそれぞれ指示し、ステップＳ１０４およびステップＳ１０５の処理を繰り返す。また、反復終了判定部１２ｃが反復を終了すると判定した場合には（ステップＳ１０６肯定）、分解行列出力部１３ａは、更新を反復回数分だけ繰り返した後の最終的な基底行列および重み行列を分解行列として出力する（ステップＳ１０７）。
【００６３】
［実施形態の効果］
このように、時系列パターン抽出装置１０は、非負値データを要素とする非負値ベクトルが時系列順に並べられた時系列データから、該時系列データが所定の時間フレームで区切られる行列を作成し、作成された行列における時間フレームのうち、任意に設定された時間間隔にシフトして取得される所定数の時間フレームの組を用いて、該時間フレームの組同士の間で現れる特徴であるパターンを抽出する。このため、断続的に特徴が現れる時系列データについて任意のギャップを許容してパターンを抽出することが可能である。
【００６４】
また、時系列パターン抽出装置１０によれば、行列分解に基づく時系列データからのパターン抽出を、時間フレームの間隔を制御して抽出することができる。なお、行列分解は、ログデータのみならず音声や映像、テキストデータなど様々な分野で発生する。本発明は、これら全ての分野に適用可能である。
【００６５】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。例えば、基底行列更新部１２ａと重み行列更新部１２ｂとを統合してもよい。
【００６６】
また、本実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６７】
［プログラム］
また、上記実施形態において説明した時系列パターン抽出装置１０が実行する処理について、コンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、実施形態に係る時系列パターン抽出装置１０が実行する処理について、コンピュータが実行可能な言語で記述した時系列パターン抽出プログラムを作成することもできる。この場合、コンピュータが時系列パターン抽出プログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかる時系列パターン抽出プログラムをコンピュータが読み取り可能な記録媒体に記録して、この記録媒体に記録された時系列パターン抽出プログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。以下に、図４に示した時系列パターン抽出装置１０と同様の機能を実現する時系列パターン抽出プログラムを実行するコンピュータの一例を説明する。
【００６８】
図１２は、時系列パターン抽出プログラムを実行するコンピュータ１０００を示す図である。図１２に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有し、これらの各部はバス１０８０によって接続される。
【００６９】
メモリ１０１０は、図１２に例示するように、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、図１２に例示するように、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、図１２に例示するように、ディスクドライブ１０４１に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブに挿入される。シリアルポートインタフェース１０５０は、図１２に例示するように、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、図１２に例示するように、例えばディスプレイ１１３０に接続される。
【００７０】
ここで、図１２に例示するように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、上記の時系列パターン抽出プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０９０に記憶される。
【００７１】
また、上記実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出し、実行する。
【００７２】
なお、時系列パターン抽出プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、時系列パターン抽出プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００７３】
１０  時系列パターン抽出装置
１１  作成部
１１ａ  入力データ行列化部
１１ｂ  初期化部
１２  抽出部
１２ａ  基底行列更新部
１２ｂ  重み行列更新部
１２ｃ  反復終了判定部
１３  結果出力部
１３ａ  分解行列出力部
【図１】
2016153983.tif 000013
【図２】
2016153983.tif 000014
【図３】
2016153983.tif 000015
【図４】
2016153983.tif 000016
【図６】
2016153983.tif 000017
【図７】
2016153983.tif 000018
【図８】
2016153983.tif 000019
【図９】
2016153983.tif 000020
【図１０】
2016153983.tif 000021
【図１１】
2016153983.tif 000022
【図１２】
2016153983.tif 000023
【図５】
2016153983.tif 000024