JP6741203B2 - 分析装置 - Google Patents

Description

本発明は、分析装置にかかり、特に、データストリームを分析する分析装置に関する。

ネットワークの侵入検知装置（ＩＤＳ）や工場の温度センサーといったセンサー機器は、観測した状態や値（観測値）をその観測時刻などの情報（タイムスタンプ）と紐付けて時々刻々と生成している。これらの観測値とタイムスタンプを含むデータをストリーム形式で配信することで、ネットワークや工場などを常時監視することができる。このストリーム形式で配信される観測値とタイムスタンプを含むデータのシーケンスはデータストリームと呼ばれる。すなわち、前述の監視は、データストリームを取得し、観測することで行われる。

さらにデータストリームを分析することで、監視対象が正常であるかを判別したり、疑わしい挙動を発見したり、といった状態把握が可能となる。データストリームの例として、Ｔｗｉｔｔｅｒなどのミニブログ（つぶやき）や、プロキシサーバのログ、ＩＤＳのアラートログ、などがある。

データストリームには様々な事象が入り混じっている。そのため、データストリーム中で生じている事象を理解するためには、“よく発現する”、“異常である”などの“意味のある”１つ以上のデータ（観測値とタイムスタンプおよびそれ以外の情報）の組を抽出する必要がある。この“意味のある”１つ以上のデータの組を“イベント”と呼ぶ。

データストリームで生じるイベントは、常に同じ周期や時間で発現するわけではない。あるときは１時間以内であっても、あるときは１０分、１日を掛けて発現する場合もある。これらは対象とする機器に異常が生じる、ネットワークへのサイバー攻撃のようにパターンの発生時間を人間によって恣意的に歪められる、といった場合に生じ得る。

一方、データストリームは時間方向に対して無限長もしくは非常に長いといった特性を持つ。そのため、データストリームを分析する際には、ある時間Ｗで発現する事象に注目し、パターンを発見することが行われる。例えば、２４時間以内に生じる温度の変化などが該当する。さらにデータストリームをある時間Ｗで分割し、分割後の複数のサブシーケンスで共通に発現するパターンを発見することも行われる。例えば、Ｗ＝２４時間とすると、一日の温度変化の平均的なパターンや、特定の時間によく発現するネットワーク上の疑わしい挙動、を発見することができる。

Gaber, Mohamed Medhat, Arkady Zaslavsky, and Shonali Krishnaswamy. "Mining data streams: a review." ACM Sigmod Record 34.2 (2005): 18-26. Rakthanmanon, Thanawin. "Addressing Big Data Time Series: Mining Trillions of Time Series Subsequences Under Dynamic Time Warping". ACM Transactions on Knowledge Discovery from Data. 7 (3): 10:1-10:31 Sepp Hochreiter; Jurgen Schmidhuber (1997). "Long short-term memory". Neural Computation. 9 (8): 1735-1780.

しかしながら、上述のように時間的な歪みが生じている場合、時間Ｗを基にしたサブシーケンスを対象とする分析方法では、分割する時間Ｗを超える時間で完了するイベントを他の同一のイベントと同一視することができない、という問題がある。また、歪みがない場合であっても、分割する時間Ｗがどの程度であるかを事前に知っていることが求められる。

よって、既存のデータストリーム分析手法では、データストリームに関する事前知識を有さない場合に、データストリームから歪みが含まれ得るイベントを発見できない、または、本来同一視されるはずのイベントが同一視されない、といった問題がある。

ここで、非特許文献１には、データストリームを分析する様々な手法について記載されている。データストリームを分析する際には、ウィンドウまたはスライディングウィンドウ（滑走窓）を用いることが一般的であり、このウィンドウ長は、分析の精度等に大きな影響を与える。

時系列データ（波形形式のデータ）に対しては、非特許文献２などの文献にてｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇを用いた、時間的歪みを解消する方法が知られている。しかしながら、本発明が想定するデータストリームは、かならずしも波形形式をとらず、また複数のイベントが重なりあっているため、ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇの概念を適用することができない。同様に、ＡＲなどの線形モデルによる時系列モデルの適用も困難である。

また、自然言語処理で用いられるｎ−ｇｒａｍモデルは、近傍に含まれる前後の単語間のパターンを統計的なモデルで表現する手段として知られている。しかし、データストリームでは、イベントを成すタプルが非常に長い間隔を持って出現することがあるため、また複数のイベントが交じり合っているため、イベントを成すタプル間の前後関係を、近傍を考慮するｎ−ｇｒａｍで捉えることが難しい。同様に非特許文献３に示されたＬＳＴＭのようなメモリを用いた手法で解決することも困難である。

このため、本発明の目的は、上述した課題である、データストリームからイベントを検出できない、ということを解決することができる情報処理装置を提供することにある。

本発明の一形態である分析装置は、
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部と、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部と、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部と、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部と、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部と、
備え、
前記ウィンドウ長決定部は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
前記グラフ構築部は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
という構成をとる。

また、本発明の一形態であるプログラムは、
情報処理装置に、
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部と、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部と、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部と、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部と、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部と、
を実現させると共に、
前記ウィンドウ長決定部は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
前記グラフ構築部は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
ことを実現させる、
という構成をとる。

また、本発明の一形態である分析方法は、
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定し、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築し、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築し、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出し、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出し、
さらに、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築して、前記テンソルの構築、前記パターンの抽出、前記残差部分の抽出を繰り返す、
という構成をとる。

本発明は、以上のように構成されることにより、データストリームからイベントを検出することができる。

本発明における第１の実施形態における分析装置の構成を示すブロック図である。 本発明における第１の実施形態における処理手順を示すフローチャートである。 データストリームの一例を示す図である。 データストリームの一部から生成したグラフの一例を示す図である。 データストリームの一部から生成したグラフを行列表現した一例を示す図である。 図５に示した行列の集合から生成したテンソルを示す図である。 図６に示したテンソルから抽出したパターンの一例を示す図である。 図７に示したパターンをグラフ表現した図である。 図３に示したデータストリームと図７に示したパターンから導いた残差部分を示す図である。 図９に示したデータストリームの残差部分の一部から生成したグラフの一例を示す図である。 図１０に示したグラフを行列表現した図である。 図７に示したパターンと、図１１に示した行列から生成したテンソルと、から抽出したパターンを示す図である。 図３に示したデータストリームと図１２に示したパターンから導いた残差部分を示す図である。 図１３に示したデータストリームの残差部分の一部から抽出したグラフの一例を示す図である。 図１４に示したグラフを行列表現した図である。 図１２に示したパターンと、図１５に示した行列から生成したテンソルと、から抽出したパターンを示す図である。 図３に示したデータストリームと図１６に示したパターンから導いた残差部分を示す図である。 本発明における第２の実施形態における分析装置の構成を示すブロック図である。 本発明における付記１における分析装置の構成を示すブロック図である。

以下、本発明の実施形態について、図面を参照して詳細に説明する。なお、各図面は、本発明の実施形態を説明するものである。ただし、本発明は、各図面の記載に限定されるものではない。また、各図面の同様の構成には、同じ番号を付し、その繰り返しの説明を省略する場合がある。また、以下の説明に用いる図面において、本発明の説明に関係しない部分の構成については、記載を省略し、図示しない場合もある。

＜実施形態１＞
本発明の第１の実施形態を、図１乃至図１７を参照して説明する。図１は、実施形態１における分析装置の構成を説明するための図であり、図２は、分析処理の様子を示すフローチャートである。図３乃至図１７は、分析処理による各情報の一例を示す図である。

図１のブロック図に示すように、本発明における分析装置１００は、グラフ構築部１０１と、テンソル構築部１０３と、パターン抽出部１０５と、差分抽出部１０７と、収束判定部１０９と、ウィンドウ長決定部１１１と、パターン・グラフ変換部１１３と、を備えている。また、分析装置１００は、データストリーム２０１を入力可能となっており、グラフ構築ルール２０２と、残差グラフ２０３と、テンソル２０４と、パターン２０５と、残差２０６と、発見済みパターングラフ２０７と、を記憶可能なよう構成されている。

なお、本実施形態における分析装置１００が備える各部１０１〜１１１は、ハードウェア回路で構成されていてもよく、情報処理装置に装備されたＣＰＵ（Central Processing Unit）にプログラムが読み込まれることによって構築されてもよい。

はじめに、上述した各部１０１〜１１１の概要について説明する。なお、各部１０１〜１１１の詳細については、以下の動作説明時に詳述する。

まず、本発明における処理対象となるデータストリームは、後述するように、タイムスタンプと観測値とからなるタプルを含んで構成されている。

上記ウィンドウ長決定部１１１は、まず、次のイテレーションで利用するウィンドウ長Ｗ_ｉ＋１を、初期ウィンドウ長Ｗ_０、ウィンドウ長Ｗ_i、ウィンドウ長倍率β、を用いて決定する。例えば、Ｗ_ｉ＋１＝βＷ_ｉ＝β^ｉＷ_０、のように決定する。

上記グラフ構築部１０１は、入力されるデータストリーム（２０１）もしくはその一部（残差部分）に対して、それらをウィンドウ長Ｗｉで分割する。そして、データストリームもしくはその一部を分割した部分シーケンス（ウィンドウ）それぞれに対して、タプル間の予め設定された関係を表すグラフを構築する。具体的には、グラフ構築ルール（２０２）を参照してウィンドウ毎のタプルであるグラフを作成し、作成したグラフの列ＧΔ（２０３）を出力する。

また、グラフ構築部１０１は、後述するように、収束判定部１０９にてデータストリームに対する処理が収束しない場合には、差分抽出部１０７にて抽出した残差（２０６）（残差部分）に対して、上述同様にグラフを構築する。

上記テンソル構築部１０３は、グラフ構築部１０１でウィンドウ毎にそれぞれ構築した複数のグラフ列を積み重ねて、テンソルＺ２０４を構築して出力する。このとき、テンソル構築部１０３は、後述するように、過去にパターン・グラフ変換部１１３にて出力したパターンＰを変換したグラフＧＰ（２０７）と、グラフ構築部１０１にて直前に構築されたグラフ列ＧΔ（２０３）と、を積み重ねて、テンソルＺを構築する。または、テンソル構築部１０３は、グラフＧＰとグラフ列ＧΔとから、テンソルＺを行列化（Matricization，Unfolding）した当該テンソルＺと等価な行列Ｙを構築してもよい。

上記パターン抽出部１０５は、テンソル構築部１０３で構築したテンソルＺ（または行列Ｙ）から主要なパターンＰ（２０５）を抽出する。パターンの抽出は、例えば、テンソル因子分解（ｔｅｎｓｏｒ ｆａｃｔｏｒｉｚａｔｉｏｎ）などの所定のテンソルから一つ以上のパターン、もしくは代表的な特徴量を抽出するような任意の分析方法を用いることができる。例えば行列Ｙに対しては、主成分分析（Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ），特異値分解（Ｓｉｎｇｕｌａｒ Ｖａｌｕｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）などの行列分解（Ｍａｔｒｉｘ Ｆａｃｔｏｒｉｚａｔｉｏｎ），多様体学習（Ｍａｎｉｆｏｌｄ Ｌｅａｒｎｉｎｇ）などによって同様に一つ以上のパターン、もしくは代表的な特徴量を抽出するような任意の分析方法を用いることができる。

上記差分抽出部１０７は、入力されたデータストリームのうち、パターン抽出部１０５が抽出したパターンＰに該当しないデータストリームの部分集合である残差Δ（２０６）（残差部分）を抽出する。この残差Δは、データストリームに対する処理が収束しない場合に、上述したグラフ構築部１０１によって、次のイテレーションによるグラフ構築の対象となる。

上記収束判定部１０９は、分析装置１００による分析によってこれ以上パターンが抽出できないかどうかを判定する。つまり、データストリームに対する処理が収束したか否かを判定する。これ以上パターンが抽出できない場合には分析装置１００の動作を終了させる。一方で、残差Δが十分に残っており、まだパターンを抽出できると判定した場合、つまり、処理は収束していないと判定した場合には、上述したように、残差Δを用いて、次のイテレーションを実行する。

そして、上記ウィンドウ長決定部１１１は、収束判定部１０９で処理が収束していないと判定した場合には、次のイテレーションで利用するウィンドウ長Ｗ_ｉ＋１を、初期ウィンドウ長Ｗ_０、ウィンドウ長Ｗ_i、ウィンドウ長倍率β、を用いて決定する。例えば、Ｗ_ｉ＋１＝βＷ_ｉ＝β^ｉＷ_０、のように決定する。これにより、ウィンドウ長決定部１１１は、過去に決定したウィンドウ長とは異なる新たなウィンドウ長を決定する。この新たなウィンドウ長を用いて、グラフ構築部１０１は、データストリームの残差Δ（２０６）に対してグラフ構築を行う。

上記パターン・グラフ変換部１１３は、パターン抽出部１０５で抽出したパターンＰ（２０５）を１つ以上のグラフからなるグラフ列（２０７）に変換する。このとき、個々のグラフが独立したパターンを表す。

［動作］
次に、上述した構成である分析装置１００の動作を、図２のフローチャート及びその他の図面を参照して説明する。

まず、入力されたデータストリームを残差Δとし、残差Δに対してグラフ構築部１０１によるグラフの構築を行い、グラフ列ＧΔを生成する（ステップＳ１１）。ここで、図３は、入力されたデータストリームを示している。データストリームは、タイムスタンプである「time」と、観測値である「Alert type」、「src（送信元）」、「dst（宛先）」と、からなるタプルを複数含んでいる。

ここでは、ウィンドウ長Ｗ_０＝６（初期ウィンドウ長）、ウィンドウ長倍率β＝２とする。すると、図３のデータストリームは、属性ｔｉｍｅの値が、［１，６］、［７，１２］、［１３，１８］、［１９，２４］である部分シーケンス（ウィンドウ）に分割される。そして、各部分シーケンス内におけるタプル間の関係を表すグラフを構築する。

ここでは、グラフ構築ルールは予め設定され記憶されており、本実施形態では、以下の二つのルールを想定する。
（１）属性ｔｉｍｅにおいて、ｔｉ＜ｔｊであるタプル間に、ｔｉであるタプルの宛先ｄｓｔとｔｊであるタプルの送信元ｓｒｃが同一であるときに、ｔｉのａｌｅｒｔ ｔｙｐｅからｔｊのａｌｅｒｔ ｔｙｐｅに辺を張る。
（２）属性ｔｉｍｅにおいて、ｔｉ＜ｔｊであるタプル間に、ｔｉであるタプルの送信元ｓｒｃとｔｊであるタプルの送信元ｓｒｃが同一であるときにｔｉのａｌｅｒｔ ｔｙｐｅからｔｊのａｌｅｒｔ ｔｙｐｅに辺を張る。
なお、上述したグラフ構築ルールは一例であって、かかるルールに限定されず、いかなるルールであってもよい。

上述したグラフ構築ルールに合致するタプルを探索し、当該タプル間の時間的な前後関係を有向グラフによって表現すると、［１，６］、［７，１２］からは、それぞれ図４（ａ），（ｂ）に示す有向グラフを構築することができる。また、図４（ａ），（ｂ）のグラフは、それぞれ図５（ａ），（ｂ）で示した行列と等価である。この行列は、ある「ａｌｅｒｔ ｔｙｐｅ」から他の「ａｌｅｒｔ ｔｙｐｅ」に辺を１回張ることができるとき、当該セルに１を加える。値が空のセルは、辺が０を意味する。なお、図４（ａ），（ｂ）のグラフの辺上に、図５（ａ），（ｂ）のように辺を張ることができた回数を重みとして付与してもよい。

また、図４（ａ），（ｂ）、図５（ａ），（ｂ）が、辺上、セル内に格納する値は、辺を張ることができた回数に基づいて算出した計算値でもよい。例えば、ある「ａｌｅｒｔ ｔｙｐｅ」から出る辺の総数で除した値（出次数で正規化した値）を付与してもよい。

続いて、テンソル構築部１０３が、グラフ構築部１０１が出力したグラフ列ＧΔと、後述するようにパターン・グラフ変換部１１３が出力したグラフ列ＧＰとを、積み重ねて構築したテンソルＺを生成する（ステップＳ１３）。なお、パターンＰから変換したグラフ列ＧＰが存在しない空の場合は、グラフ構築部１０１が構築したグラフ列ＧΔだけを対象として、テンソルを生成する。

ここで、１回目のイテレーションでは、パターンＰをまだ抽出していないため、グラフ列ＧＰが存在しない。そこで、テンソル構築部１０３は、グラフ構築部１０１が生成した図５（ａ），（ｂ），（ｃ）を対象にテンソルを構築する。ここでは、ウィンドウ長で分割したウィンドウ毎のグラフ列（行列の列）を、ｔｉｍｅ属性の値が小さい順に並べて積み重ねて、図６に示すようなテンソルＺを生成する。

続いて、パターン抽出部１０５が、テンソル構築部１０３が生成したテンソルＺに対してテンソル分解などによるパターン抽出を行い、主要なパターンＰを抽出する。パターンＰを抽出すると、差分抽出部１０７が入力されたオリジナルのデータストリームとパターンＰを比較して、パターンＰに合致しないデータストリームの部分集合である残差Δを導出する（ステップＳ１５）。

ここで、パターン抽出部１０５のパターン抽出として、Ｐａｒａｆａｃ（ＣＰ分解）法によるテンソル因子分解を用いることができる。図７は、Ｐａｒａｆａｃで得られたパターンＰの一例を示している。図７中の行列は、図５（ａ），（ｂ），（ｃ）で共通もしくは複数回出現したパターンを示しており、図８の有向グラフと等価である。また、図７中の斜め方向に記載された１ｘ４のベクトルは、ウィンドウ長で分割したどの時間に当該パターンが出現したかを示している。図７では、１番目、２番目に１の値が格納されている。これは時間［Ｐ１，６］、［７，１２］に図７中の行列で示されたパターンが存在することを示している。

また、テンソル分解によって出力されたパターンＰを、主要なパターンに限定する方法として、得られるパターンＰがスパースに（０が多く）なるようにする方法であるスパース推定を導入したスパーステンソル分解を用いることができる。また、主要なパターンを構成する潜在因子（Ｌａｔｅｎｔ Ｃｏｍｐｏｎｅｎｔ）の数ｋは、ＭＤＬ理論やＢＩＣなどの情報量基準に基づいて決定してもよい。図７のパターンＰは、スパーステンソル分解によって得られたパターンの一例である。なお、実際のスパーステンソル分解で得られる値を正確に説明することよりも、説明としての分かりやすさを優先して、単純な値で例を示している。

ここで、図８に示した有向グラフは、パターン・グラフ変換部１１３が、パターンＰから生成したグラフ列ＧＰである。なお、パターンＰが空（サイズ０の列）の場合は、パターン・グラフ変換部１１３を用いたパターンＰからグラフ列ＧＰへの変換は行わない。

続いて、パターンＰを用いて、差分抽出部１０７がデータストリームからパターンＰに該当しないデータストリームの部分集合である残差Δを得る。ここでは、図３に示すデータストリームと図７に示すパターンＰから、図９に示す残差Δを得る。

そして、収束判定部１０９が、パターンＰが前回のパターン抽出から変化していない、残差Δが空である、などの条件によって、データストリームに対する処理が収束したか否か、つまり、分析装置１００の動作を停止するか否かを判定する（ステップＳ１７）。

動作を停止しない場合には、ウィンドウ長決定部１１１が次のイテレーションで利用するウィンドウ長Ｗ_ｉ＋１を導出する（ステップＳ１９）。ここでは、図９に示す残差Δに十分な量のタプルが残っているため、動作を停止しない。このとき、次のイテレーションにおける新たなウィンドウ長Ｗ_１は、Ｗ_０＝６、β＝２より、「１２」となる。そして、この新たなウィンドウ長Ｗ_１を用いて、上述同様に、グラフ構築部１０１、テンソル構築部１０３、パターン抽出部１０５、差分抽出部１０７、収束判定部１０９などによる処理を繰り返す。

２回目のイテレーションでは、図９に示す残差Δから、図１０に示すグラフが時間［１，１２］から生成され、図１１（ａ）の行列が生成される。同様に、時間［１３，２４］から図１１（ｂ）の行列が生成される。

さらにイテレーション１のパターンＰからΔＰとして図７に示すテンソルに変換したもの、もしくはグラフ列を生成する。図７をテンソルに変換したものは、図７の行列とベクトルの外積（ｏｕｔｅｒ ｐｒｏｄｕｃｔ）を取ったものと等価である。よって、２回目のイテレーションでは、テンソル構築部１０３は、図７の行列とベクトルの外積を取ったものと、図１１（ａ），（ｂ）の行列を積み重ねて生成したテンソルＺを生成する。

さらに、２回目のイテレーションでは、パターン抽出部１０５は、テンソルＺから図１２に示すパターンＰを抽出する。図１２に示すパターンＰは、二つの項の和でテンソルＺ中の主要なパターンを表している。第一項は、イテレーション１で抽出したパターンと同様のパターンが抽出され、１ｘ６のベクトルが付されている。この１ｘ６のベクトルは、イテレーション１でＷ_０＝６で分割された時間［１，６］、［７，１２］、［１３，１８］、［１９，２４］、さらにイテレーション１の後の残差Δに対してイテレーション２にてＷ_１＝１２のウィンドウによって分割された時間［１，１２］、［１３，２４］に、当該パターンがどの程度出現するかを示している。同様に第二項は、イテレーション２で新たに抽出されたパターンであり、［１，１２］、［１３，２４］にそれぞれ出現するＥ→Ｅなるパターンを示している。

その後、２回目のイテレーションでは、差分抽出部１０７によって図１３に示す残差Δを得る。すると、収束判定部１０９は、図１３に示す残差Δに十分なタプル数があるため、処理を継続する。

続いて、３回目のイテレーションでは、さらにウィンドウ長決定部１１１にて新たなウィンドウ長Ｗ_２＝２４を決定し、かかる新たなウィンドウ長を用いて、グラフ構築部１０１によって、図１３の残差Δから図１４に示すグラフを得て、図１５に示す行列を得る。続いて、テンソル構築部１０３が図１２に示す過去のパターンＰから得たテンソルと、図１５に示す行列を積み重ねたテンソルＺを生成し、パターン抽出部１０５が図１６に示すパターンＰを抽出する。

そして、差分抽出部１０７が図１７に示す残差Δを抽出する。収束判定部１０９は、図１７にパターン抽出に十分なタプル数がないため、動作を停止する。

以上のように、本発明によれば、データストリームから、発現時刻、間隔といった時間的歪みが生じている複数のイベントを、同一のパターンとして抽出できる。このとき、イベント毎にウィンドウ長を設定せずに、時間的歪みのある複数のイベントを同一のパターンとして抽出できる。

＜実施形態２＞
以上の説明した分析装置１００は、次のように構成される。例えば、分析装置１００の各構成部は、ハードウェア回路で構成されても良い。また、分析装置１００は、各構成部が、ネットワークを介して接続した複数の装置を用いて、構成されても良い。また、分析装置１００は、複数の構成部を１つのハードウェアで構成しても良い。

また、分析装置３００は、ＣＰＵ（Central Processing Unit）と、ＲＯＭ（Read Only Memory）と、ＲＡＭ（Random Access Memory）とを含むコンピュータ装置として実現してもよい。分析装置３００は、上記構成に加え、さらに、入出力接続回路（ＩＯＣ：Input / Output Circuit）と、ネットワークインターフェース回路（ＮＩＣ：Network Interface Circuit）とを含むコンピュータ装置として実現しても良い。

図１８は、実施形態２における分析装置３００の構成の一例を示すブロック図である。分析装置３００は、ＣＰＵ３１０と、ＲＯＭ３２０と、ＲＡＭ３３０と、内部記憶装置３４０と、ＩＯＣ３５０と、入力機器３６０と、表示機器３７０と、ＮＩＣ３８０とを含み、コンピュータ装置を構成している。

ＣＰＵ３１０は、ＲＯＭ３２０からプログラムを読み込む。そして、ＣＰＵ３１０は、読み込んだプログラムに基づいて、ＲＡＭ３３０と、内部記憶装置３４０と、ＩＯＣ３５０と、ＮＩＣ３８０とを制御する。そして、ＣＰＵ３１０を含むコンピュータは、これらの構成を制御し、図１に示す、グラフ構築部１０１と、テンソル構築部１０３と、パターン抽出部１０５と、差分抽出部１０７と、収束判定部１０９と、ウィンドウ長決定部１１１と、パターン・グラフ変換部１１３としての各機能を実現する。

ＣＰＵ３１０は、各機能を実現する際に、ＲＡＭ３３０又は内部記憶装置３４０を、プログラムの一時記憶として使用しても良い。

また、ＣＰＵ３１０は、コンピュータで読み取り可能にプログラムを記憶した記憶媒体（図示せず）が含むプログラムを、図示しない記憶媒体読み取り装置を用いて読み込んでも良い。あるいは、ＣＰＵ３１０は、ＮＩＣ３８０を介して、図示しない外部の装置からプログラムを受け取り、ＲＡＭ３３０に保存して、保存したプログラムを基に動作しても良い。

ＲＯＭ３２０は、ＣＰＵ３１０が実行するプログラム及び固定的なデータを記憶する。ＲＯＭ３２０は、例えば、Ｐ−ＲＯＭ（Programmable-ROM）又はフラッシュＲＯＭである。ＲＡＭ３３０は、ＣＰＵ３１０が実行するプログラム及びデータを一時的に記憶する。ＲＡＭ３３０は、例えば、Ｄ−ＲＡＭ（Dynamic-RAM）である。内部記憶装置３４０は、分析装置３００が長期的に保存するデータ及びプログラムを記憶する。また、内部記憶装置３４０は、ＣＰＵ３１０の一時記憶装置として動作しても良い。内部記憶装置３４０は、例えば、ハードディスク装置、光磁気ディスク装置、ＳＳＤ（Solid State Drive）又はディスクアレイ装置である。

ここで、ＲＯＭ３２０と内部記憶装置３４０は、不揮発性（non-transitory）の記憶媒体である。一方、ＲＡＭ３３０は、揮発性（transitory）の記憶媒体である。そして、ＣＰＵ３１０は、ＲＯＭ３２０、内部記憶装置３４０、又は、ＲＡＭ３３０に記憶されているプログラムを基に動作可能である。つまり、ＣＰＵ３１０は、不揮発性記憶媒体又は揮発性記憶媒体を用いて動作可能である。

ＩＯＣ３５０は、ＣＰＵ３１０と、入力機器３６０及び表示機器３７０とのデータを仲介する。ＩＯＣ３５０は、例えば、ＩＯインターフェースカード又はＵＳＢ（Universal Serial Bus）カードである。入力機器３６０は、分析装置３００の操作者からの入力指示を受け取る機器である。入力機器３６０は、例えば、キーボード、マウス又はタッチパネルである。表示機器３７０は、分析装置３００の操作者に情報を表示する機器である。表示機器３７０は、例えば、液晶ディスプレイである。

ＮＩＣ３８０は、ネットワークを介した図示しない外部の装置とのデータのやり取りを中継する。ＮＩＣ３８０は、例えば、ＬＡＮ（Local Area Network）カードである。

このように構成された分析装置３００は、ＣＰＵ６１０がプログラムに基づいて実施形態１で説明した分析装置１００と同様の機能を実現できるため、当該分析装置１００と同様の効果を得ることができる。

＜付記＞
上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明における分析装置（図１９参照）、プログラム、分析方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。

（付記１）
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部４１０と、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部４２０と、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部４３０と、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部４４０と、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部４５０と、
備え、
前記ウィンドウ長決定部４１０は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
前記グラフ構築部４２０は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
分析装置４００。

（付記２）
付記１に記載の分析装置であって、
前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定する収束判定部をさらに備え、
前記データストリームに対する処理が収束していないと判定された場合に、前記ウィンドウ長決定部、前記グラフ構築部、前記テンソル構築部、前記パターン抽出部及び前記差分抽出部がさらに作動する、
分析装置。

（付記３）
付記１又は２に記載の分析装置であって、
前記テンソル構築部は、過去に抽出された前記パターンと、直前に構築された前記グラフとから、前記テンソルまたは前記テンソルと等価な行列を構築する、
分析装置。

（付記４）
付記１乃至３のいずれかに記載の分析装置であって、
抽出した前記パターンを前記グラフに変換するパターン・グラフ変換部をさらに備えた、
分析装置。

（付記５）
付記１乃至４のいずれかに記載の分析装置であって、
前記パターン抽出部は、スパース推定を導入したテンソル分解を用いて、スパースなベクトル、行列及びテンソルとしてパターンを抽出する、
分析装置。

（付記６）
付記１乃至５のいずれかに記載の分析装置であって、
前記グラフ構築部は、前記タプル間の時間的な前後関係を有向グラフによって表現した前記グラフを構築する、
分析装置。

（付記７）
情報処理装置に、
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部と、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部と、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部と、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部と、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部と、
を実現させると共に、
前記ウィンドウ長決定部は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
前記グラフ構築部は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
ことを実現させるためのプログラム。

（付記８）
付記７に記載のプログラムであって、
前記情報処理装置に、
前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定する収束判定部をさらに実現させ、
前記データストリームに対する処理が収束していないと判定された場合に、前記ウィンドウ長決定部、前記グラフ構築部、前記テンソル構築部、前記パターン抽出部及び前記差分抽出部をさらに作動させる、
プログラム。

（付記９）
タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定し、
前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築し、
複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築し、
前記テンソルまたは前記テンソルと等価な行列からパターンを抽出し、
前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出し、
さらに、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築して、前記テンソルの構築、前記パターンの抽出、前記残差部分の抽出を繰り返す、
分析方法。

（付記１０）
付記９に記載の分析方法であって、
前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定し、前記データストリームに対する処理が収束していないと判定された場合に、前記新たなウィンドウ長の決定、前記グラフの構築、前記テンソルの構築、前記パターンの抽出、前記残差部分の抽出を繰り返す、
分析方法。

なお、上述したプログラムは、記憶装置に記憶されていたり、コンピュータが読み取り可能な記録媒体に記録されている。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。

以上、上記実施形態等を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解しうる様々な変更をすることができる。

１００ 分析装置
１０１ グラフ構築部
１０３ テンソル構築部
１０５ パターン抽出部
１０７ 差分抽出部
１０９ 収束判定部
１１１ ウィンドウ長決定部
１１３ パターン・グラフ変換部
３００ 分析装置
３１０ ＣＰＵ
３２０ ＲＯＭ
３３０ ＲＡＭ
３４０ 内部記憶装置
３５０ ＩＯＣ
３６０ 入力機器
３７０ 表示機器
３８０ ＮＩＣ
４００ 分析装置
４１０ ウィンドウ長決定部
４２０ グラフ構築部
４３０ テンソル構築部
４４０ パターン抽出部
４５０ 差分抽出部

Claims (10)

1. タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部と、
   前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部と、
   複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部と、
   前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部と、
   前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部と、
   備え、
   前記ウィンドウ長決定部は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
   前記グラフ構築部は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
   分析装置。
2. 請求項１に記載の分析装置であって、
   前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定する収束判定部をさらに備え、
   前記データストリームに対する処理が収束していないと判定された場合に、前記ウィンドウ長決定部、前記グラフ構築部、前記テンソル構築部、前記パターン抽出部及び前記差分抽出部がさらに作動する、
   分析装置。
3. 請求項１又は２に記載の分析装置であって、
   前記テンソル構築部は、過去に抽出された前記パターンと、直前に構築された前記グラフとから、前記テンソルまたは前記テンソルと等価な行列を構築する、
   分析装置。
4. 請求項１乃至３のいずれかに記載の分析装置であって、
   抽出した前記パターンを前記グラフに変換するパターン・グラフ変換部をさらに備えた、
   分析装置。
5. 請求項１乃至４のいずれかに記載の分析装置であって、
   前記パターン抽出部は、スパース推定を導入したテンソル分解を用いて、スパースなベクトル、行列及びテンソルとしてパターンを抽出する、
   分析装置。
6. 請求項１乃至５のいずれかに記載の分析装置であって、
   前記グラフ構築部は、前記タプル間の時間的な前後関係を有向グラフによって表現した前記グラフを構築する、
   分析装置。
7. 情報処理装置に、
   タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定するウィンドウ長決定部と、
   前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築するグラフ構築部と、
   複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築するテンソル構築部と、
   前記テンソルまたは前記テンソルと等価な行列からパターンを抽出するパターン抽出部と、
   前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出する差分抽出部と、
   を実現させると共に、
   前記ウィンドウ長決定部は、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、
   前記グラフ構築部は、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築する、
   ことを実現させるためのプログラム。
8. 請求項７に記載のプログラムであって、
   前記情報処理装置に、
   前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定する収束判定部をさらに実現させ、
   前記データストリームに対する処理が収束していないと判定された場合に、前記ウィンドウ長決定部、前記グラフ構築部、前記テンソル構築部、前記パターン抽出部及び前記差分抽出部をさらに作動させる、
   プログラム。
9. タイムスタンプと観測値とからなるタプルを含むデータストリームのウィンドウ長を決定し、
   前記データストリームから、決定された前記ウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築し、
   複数の前記ウィンドウ毎にそれぞれ構築された複数の前記グラフからテンソルまたは前記テンソルと等価な行列を構築し、
   前記テンソルまたは前記テンソルと等価な行列からパターンを抽出し、
   前記データストリームから、抽出した前記パターンに合致しない残差部分を抽出し、
   さらに、過去に決定した前記ウィンドウ長とは異なる新たなウィンドウ長を決定し、前記データストリームから抽出された前記残差部分から、決定された前記新たなウィンドウ長で分割されたウィンドウ内における前記タプル間の予め設定された関係を表すグラフを構築して、前記テンソルの構築、前記パターンの抽出、前記残差部分の抽出を繰り返す、
   分析方法。
10. 請求項９に記載の分析方法であって、
    前記データストリームから抽出した前記残差部分に基づいて、前記データストリームに対する処理が収束したか否かを判定し、前記データストリームに対する処理が収束していないと判定された場合に、前記新たなウィンドウ長の決定、前記グラフの構築、前記テンソルの構築、前記パターンの抽出、前記残差部分の抽出を繰り返す、
    分析方法。
    

Images