(57)【要約】【課題】イベントストリームから効率的にエピソードを得る。【解決手段】イベントシーケンスにおいて、ウィンドウ内のエピソードの出現回数をカウントし、ウィンドウをイベントシーケンスの所定方向に移動させるたびに、ウィンドウに追加されたイベント、または、ウィンドウに追加された各イベントを終点とするエピソードの出現回数をカウントし、ウィンドウから削除されたイベント、または、ウィンドウから削除されたイベントを始点とするエピソードの出現回数をカウントし、それにより頻度を加減し、所定の閾値以上の頻度であるエピソードを抽出する。【選択図】図１
2017004437.tif 000002
【特許請求の範囲】
【請求項１】
イベントの発生を時系列順に並べたイベントシーケンスにおいて、所定の範囲において発生したイベント、または、前記範囲において発生する所定のイベントを始点とし、所定のイベントを終点とするイベントの組合せの出現回数をカウントし、前記範囲を前記イベントシーケンスの所定方向に移動させるたびに、前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの出現回数である追加出現回数をカウントするとともに、前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの出現回数である削減出現回数をカウントするカウント部と、
前記カウント部によってカウントされたイベントまたはイベントの組合せの出現回数から前記追加出現回数の加算を行い、該追加出現回数が加算されたイベントまたはイベントの組合せの出現回数から前記削減出現回数の減算を行う加減部と、
イベントまたはイベントの組合せの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する抽出部と、
を有することを特徴とするパターン検出装置。
【請求項２】
前記イベントの種類の数をｍ、前記範囲に含まれるイベントの数をｎとするｍ×ｎ行列であって、ｉ番目の種類のイベントが前記範囲のｊ番目の位置に存在する場合は、前記行列の成分ａｉｊの値を１とし、存在しない場合は前記行列の成分ａｉｊの値を０とすることで各成分の値が決定される行列であるイベント位置ビットブロックを作成するイベント位置ビットブロック作成部と、
前記イベント位置ビットブロックの各イベントに対応する行ベクトルであるイベント位置ビットベクトルから、成分の値が１である位置を示す番号をｉｄとして取得し、長さがｎのベクトルであって、前記範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベント、または、該範囲に追加されたイベントのうち最初に発生したイベントから前記ｉｄが示す位置までの値が０、前記ｉｄが示す位置より先の値が１であるベクトルであるマスクビットベクトルを、前記イベントおよび前記ｉｄ毎に作成するマスク演算部と、
長さがｎのベクトルであって、前記ｉｄが示す位置から、前記範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベントから時系列と逆方向、または、該範囲に追加されたイベントのうち最初に発生したイベントから時系列順の方向かつ前記イベントシーケンスにおける所定の継続時間の範囲に含まれる位置の成分の値が１、それ以外の位置の値が０であるベクトルであるタイムビットベクトルを作成し、前記マスクビットベクトルと前記タイムビットベクトルの論理積であるタイムマスクビットベクトルを作成する継続時間符号化部と、
第１のイベントに基づいて作成された前記タイムマスクビットベクトルと、第２のイベントに基づいて作成された前記イベント位置ビットベクトルとの論理積の集合であるエピソード位置ビットブロックを作成するエピソード位置ビットブロック作成部と、
をさらに有し、
前記カウント部は、前記イベントに対応するエピソード位置ビットブロックにおける値が１である成分の数を、該イベントを始点または終点とするエピソードの出現回数としてカウントすることを特徴とする請求項１に記載のパターン検出装置。
【請求項３】
前記範囲が一定のスライド幅ずつ移動する場合に、前記イベント位置ビットブロックを前記スライド幅毎に時間ブロックに分割し、前記時間ブロックの桁数のビット列が取り得る各値に対して、正の整数で表されるＩＤを設定し、前記時間ブロック毎に、前記ＩＤの最大値より大きい素数であって、互いに異なる素数を割り当て、前記素数の積を法として、前記時間ブロック毎の前記ＩＤとペアになる解を中国の剰余定理に基づいて算出するスケッチ処理部をさらに有することを特徴とする請求項２に記載のパターン検出装置。
【請求項４】
前記加減部は、
前記カウント部が前記追加出現回数をカウントした前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの時刻の区間が、最後にカウントした前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの時刻の区間と重複しない場合に、前記追加出現回数の加算を行い、
前記カウント部が前記追加出現回数をカウントした前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの時刻の区間が、前記範囲を前記イベントシーケンスの所定方向に移動させた後最初にカウントした前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの時刻の区間と重複しない場合に、前記削減出現回数の減算を行うことを特徴とする請求項１から３のいずれか１項に記載のパターン検出装置。
【請求項５】
パターン検出装置で実行されるパターン検出方法であって、
イベントの発生を時系列順に並べたイベントシーケンスにおいて、所定の範囲において発生したイベント、または、前記範囲において発生する所定のイベントを始点とし、所定のイベントを終点とするイベントの組合せの出現回数をカウントし、前記範囲を前記イベントシーケンスの所定方向に移動させるたびに、前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの出現回数である追加出現回数をカウントするとともに、前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの出現回数である削減出現回数をカウントするカウント工程と、
前記カウント工程によってカウントされたイベントまたはイベントの組合せの出現回数から前記追加出現回数の加算を行い、該追加出現回数が加算されたイベントまたはイベントの組合せの出現回数から前記削減出現回数の減算を行う加減工程と、
イベントまたはイベントの組合せの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する抽出工程と、
を含んだことを特徴とするパターン検出方法。
【請求項６】
コンピュータを、請求項１から４のいずれか１項に記載のパターン検出装置として機能させるためのパターン検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン検出装置、パターン検出方法およびパターン検出プログラムに関する。
【背景技術】
【０００２】
ネットワークから収集されるログデータには、購買履歴やシステムログ等、イベントとそのイベントが起こった時刻が記録されたイベントシーケンスと呼ばれるデータが多数含まれている。このイベントシーケンスから有益なパターンを見つけるマイニング技術として、エピソードマイニングが知られている。エピソードマイニングにおいては、イベントシーケンスに繰り返し現れるエピソードと呼ばれる頻出パターンを検知する。
【０００３】
エピソードは、システムログにおけるマシンや機器間の処理の流れ、または購買ログにおけるユーザの購入した時系列アイテム等を表している。エピソードはデータのトレンドを知るための重要な指標であり、エピソードにより、イベントシーケンスを単純かつ簡単に解釈することができるようになり、データのトレンドを知ることができるようになる。
【０００４】
従来のエピソードマイニングとしては、全データのバッチ処理を行う方法が知られている（例えば、非特許文献１または２を参照）。また、リアルタイムのイベントストリームを対象としたエピソードマイニングとして、最新のデータを含む一定範囲にウィンドウを設け、ウィンドウを一定幅ずつスライドさせ、ウィンドウ内のエピソードを検出する方法が知られている。具体的には、前述のウィンドウ内のイベントシーケンスをバッチと呼ばれる単位に区切り、バッチ内のエピソードに対し、蓄積されたイベントシーケンスに対する手法を用いて、エピソードのカウンティングを実行し、さらにバッチ間で各エピソードの出現回数を合計し、上位のエピソードを頻出エピソードとして提示する方法が知られている（例えば、非特許文献３を参照）。また、ウィンドウ内の各時刻のイベントを最初の要素としたエピソードを保持することで、ウィンドウ内に含まれるminimal  occurrence-basedな頻出エピソードを出力する方法が知られている（例えば、非特許文献４を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】“Discovery  of  frequent  episodes  in  event  sequences”,  Data  Mining  and  Knowledge  Discovery,  Volume  1,  Issue  3,  pp  259-289,  1997
【非特許文献２】“Discovering  frequent  episodes  and  learning  hidden  Markov  models:  a  formal  connection”,  IEEE  Transactions  on  Knowledge  and  Data  Engineering,  Volume  17,  Issue  11,  pp.1505-1517,  2005
【非特許文献３】“Efficient  Episode  Mining  of  Dynamic  Event  Streams”,  10th  IEEE  International  Conference  on  Data  Mining,  pp.  605-614,  2012
【非特許文献４】“Online  Frequent  Episode  Mining”,  31th  IEEE  Inter  national  conference  on  Data  engineering,  2015
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のエピソードマイニングには、イベントストリームから効率的にエピソードを得ることができないという問題があった。
【０００７】
例えば、非特許文献１または２に記載された技術においては、イベントが削除されることは想定されていないため、新たなイベントが追加されるたびにウィンドウ内のすべての要素を１つのイベントシーケンスとして捉え、各手法を用いてエピソードを探す必要があった。この時、新たに追加される要素数よりもウィンドウの方が長いため、１度の処理に要する時間が長くなってしまうという問題が生じる。
【０００８】
また、非特許文献３に記載された技術においては、バッチにまたがるエピソードは検出できないため、ウィンドウ内の厳密なエピソードは把握できないという問題がある。また、非特許文献４に記載の技術においては、ウィンドウ内のすべてのイベントを最初の要素としたエピソードを保持する必要があるため、ウィンドウの長さや候補数に比例して必要なメモリや処理時間が増大してしまうという問題がある。
【課題を解決するための手段】
【０００９】
本発明のパターン検出装置は、イベントの発生を時系列順に並べたイベントシーケンスにおいて、所定の範囲において発生したイベント、または、前記範囲において発生する所定のイベントを始点とし、所定のイベントを終点とするイベントの組合せの出現回数をカウントし、前記範囲を前記イベントシーケンスの所定方向に移動させるたびに、前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの出現回数である追加出現回数をカウントするとともに、前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの出現回数である削減出現回数をカウントするカウント部と、前記カウント部によってカウントされたイベントまたはイベントの組合せの出現回数から前記追加出現回数の加算を行い、該追加出現回数が加算されたイベントまたはイベントの組合せの出現回数から前記削減出現回数の減算を行う加減部と、イベントまたはイベントの組合せの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する抽出部と、を有することを特徴とする。
【００１０】
本発明のパターン検出方法は、パターン検出装置で実行されるパターン検出方法であって、イベントの発生を時系列順に並べたイベントシーケンスにおいて、所定の範囲において発生したイベント、または、前記範囲において発生する所定のイベントを始点とし、所定のイベントを終点とするイベントの組合せの出現回数をカウントし、前記範囲を前記イベントシーケンスの所定方向に移動させるたびに、前記範囲に追加された各イベント、または、前記範囲に追加された各イベントを終点とする各イベントの組合せの出現回数である追加出現回数をカウントするとともに、前記範囲から削除された各イベント、または、前記範囲から削除された各イベントを始点とする各イベントの組合せの出現回数である削減出現回数をカウントするカウント工程と、前記カウント工程によってカウントされたイベントまたはイベントの組合せの出現回数から前記追加出現回数の加算を行い、該追加出現回数が加算されたイベントまたはイベントの組合せの出現回数から前記削減出現回数の減算を行う加減工程と、イベントまたはイベントの組合せの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する抽出工程と、を含んだことを特徴とする。
【発明の効果】
【００１１】
本発明によれば、イベントストリームから効率的にエピソードを得ることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、第１の実施形態に係るパターン検出装置の構成の一例を示す図である。
【図２】図２は、イベントシーケンスの一例を示す図である。
【図３】図３は、イベントシーケンスのカウンティング方法の例を示す図である。
【図４】図４は、イベントシーケンスの各カウンティング方法によるカウント結果の例を示す図である。
【図５】図５は、ウィンドウのスライドについて説明するための図である。
【図６】図６は、ウィンドウのスライドについて説明するための図である。
【図７】図７は、第１の実施形態に係るパターン検出装置によるイベントの位置ビットブロックの作成方法の一例を示す図である。
【図８】図８は、第１の実施形態に係るパターン検出装置によるマスク演算の一例を示す図である。
【図９】図９は、第１の実施形態に係るパターン検出装置によるタイムビットブロックの作成方法の一例を示す図である。
【図１０】図１０は、第１の実施形態に係るパターン検出装置によるエピソードの位置ビットブロックの作成方法の一例を示す図である。
【図１１】図１１は、第１の実施形態に係るパターン検出装置によるスケッチの作成方法の一例を示す図である。
【図１２】図１２は、第１の実施形態に係るパターン検出装置によるスケッチの更新方法の一例を示す図である。
【図１３】図１３は、第１の実施形態のエピソード拡張処理を示すフローチャートである。
【図１４】図１４は、第１の実施形態のスケッチ生成処理を示すフローチャートである。
【図１５】図１５は、第１の実施例の概要を示す図である。
【図１６】図１６は、第１の実施例におけるbackward操作を説明するための図である。
【図１７】図１７は、第１の実施例におけるbackward操作におけるエピソード拡張を説明するための図である。
【図１８】図１８は、第１の実施例におけるforward操作を説明するための図である。
【図１９】図１９は、第１の実施例の処理を示すフローチャートである。
【図２０】図２０は、第１の実施例のbackward操作の処理を示すフローチャートである。
【図２１】図２１は、第１の実施例のforward操作の処理を示すフローチャートである。
【図２２】図２２は、第２の実施例の概要を示す図である。
【図２３】図２３は、第２の実施例におけるbackward操作を説明するための図である。
【図２４】図２４は、第２の実施例におけるbackward操作を説明するための図である。
【図２５】図２５は、第２の実施例におけるforward操作を説明するための図である。
【図２６】図２６は、第２の実施例におけるforward操作を説明するための図である。
【図２７】図２７は、プログラムが実行されることにより、パターン検出装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願に係るパターン検出装置、パターン検出方法およびパターン検出プログラムの実施形態を図面に基づいて詳細に説明する。なお、この実施形態により本願に係るパターン検出装置、パターン検出方法およびパターン検出プログラムが限定されるものではない。
【００１４】
［第１の実施形態の構成］
まず、図１を用いて、第１の実施形態に係るパターン検出装置の構成について説明する。図１は、第１の実施形態に係るパターン検出装置の構成の一例を示す図である。図１に示すように、パターン検出装置１は、制御部２、記憶部３および抽出部４を有する。また、制御部２は、カウント部１０、スケッチ処理部２０および加減部３０を有する。なお、記憶部３は、各エピソードの頻度および後述するスケッチ等を記憶する。以降、制御部２の各部の構成について詳細に説明する。
【００１５】
パターン検出装置１のカウント部１０は、イベントの発生を時系列順に並べたイベントシーケンスにおいて、所定の範囲において発生したイベント、または、範囲において発生する所定のイベントを始点とし、所定のイベントを終点とするイベントの組合せの出現回数をカウントし、範囲をイベントシーケンスの所定方向に移動させるたびに、範囲に追加された各イベント、または、範囲に追加された各イベントを終点とする各イベントの組合せの出現回数である追加出現回数をカウントするとともに、範囲から削除された各イベント、または、範囲から削除された各イベントを始点とする各イベントの組合せの出現回数である削減出現回数をカウントする。そして、加減部３０は、カウント部１０によってカウントされたイベントまたはイベントの組合せの出現回数から追加出現回数の加算を行い、該追加出現回数が加算されたイベントまたはイベントの組合せの出現回数から削減出現回数の減算を行う。そして、抽出部４は、イベントまたはイベントの組合せの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する。
【００１６】
具体的に、以降の説明において、所定の範囲とはウィンドウのことを指し、イベントの組合せとはエピソードのことを指している。また、追加出現回数および削減出現回数は、backward操作により得られる出現回数およびforward操作によって得られる出現回数と対応している。
【００１７】
（エピソードマイニングの概要）
ここで、エピソードマイニングの概要について説明する。まず、パターン検出装置１の検出対象となるイベントシーケンスおよび検出の際に用いられるウィンドウについて説明する。図２を用いて、イベントシーケンスについて説明する。図２は、イベントシーケンスの一例を示す図である。図２に示すように、イベントシーケンスとは、イベントおよびそのイベントが起きた時刻を含んだデータを時系列に並べたものである。図２の例では、例えば11:20にａというイベントが発生し、11:21にｂというイベントが発生したことを示している。
【００１８】
なお、図２の例では、１つの時刻に対して１つのイベントが対応しているが、１つの時刻に対して複数のイベントが対応していてもよい。また、イベントシーケンスは必ずしも時刻を含んだものでなくてもよく、例えば、イベントのみが時刻順で並べられているものであってもよい。
【００１９】
具体的に、イベントとして扱う対象は、購買履歴やシステムログ等様々なものが考えられる。例えば、購買履歴をイベントとする場合は、「Ａという商品を買った」というイベントをａ、「Ｂという商品を買った」というイベントをｂとしてもよい。また、システムログをイベントとする場合は、「あるファイルを参照した」というイベントをａ、「あるファイルを削除した」というイベントをｂとすることもできる。
【００２０】
また、以降の説明においては、イベントシーケンスに含まれる順序を考慮したイベントの集合をエピソードと呼ぶ。なお、エピソードに含まれるイベントは１つであってもよい。また、エピソードに含まれるイベントの個数を長さとする。例えば、図２において、長さ３のエピソードとして、例えば＜ａ，ｃ，ｄ＞、＜ａ，ａ，ｃ＞等が存在する。エピソードは、イベントシーケンスの中に繰り返し出現する。そして、パターン検出装置１は、エピソードの出現回数をカウントする。
【００２１】
また、エピソードのとらえ方の違いにより、複数のカウンティング方法がある。ここで、図３および図４を用いて、各カウンティング方法について説明する。図３は、イベントシーケンスのカウンティング方法の例を示す図である。また、図４は、イベントシーケンスの各カウンティング方法によるカウント結果の例を示す図である。図３に示すように、まず、window-basedでは、ウィンドウ幅Txが与えられた時、エピソードαが少なくとも１回含まれている幅Txのウィンドウの数がカウントされる。また、minimal  occurrence-basedでは、エピソードαが時刻tsからteに存在し、その時間内に他のαが存在しない時、時刻tsからteはminimal  windowであり、このminimal  windowの数がカウントされる。
【００２２】
また、non-overlappedでは、長さNのエピソードα<ν1,  …  ,νN>が異なる位置にある時、それぞれの存在をh1，h2とすると、以下の式（１−１）または式（１−２）が成り立つ時、αの２つの存在はnon-overlappedであり、non-overlappedなαの存在が最大となるときの存在数がカウントされる。
【００２３】
【数１】
2017004437.tif 000003
【００２４】
また、distinct  occurrence-basedでは、長さNのエピソードα<ν1,  …  ,νN>が異なる位置にある時、それぞれの存在をh1，h2とすると、以下の式（２）が成り立つ時、αの２つの存在はdistinctであり、これらdistinctなαの存在が最大となる時の存在数がカウントされる。
【００２５】
【数２】
2017004437.tif 000004
【００２６】
また、head-basedでは、ウィンドウ幅Txが与えられた時、ウィンドウの左端が開始点であるエピソードαを含む幅Txのウィンドウ数がカウントされる。図４に示すようにこれらの方法によって＜Ａ，Ｂ，Ａ＞というエピソードをカウントすると、各方法によってカウントされる数が異なる。
【００２７】
第１の実施形態において、パターン検出装置１は、イベントストリームを対象としてウィンドウを一定幅ずつスライドさせることによりエピソードマイニングを行う。図５を用いてウィンドウを用いたエピソードマイニングについて説明する。図５は、ウィンドウのスライドについて説明するための図である。まず、一般的なエピソードマイニングにおいては、イベントシーケンス、長さの閾値lmin、頻度の閾値min_supが与えられた時、頻度がmin_sup以上かつ長さがlmin以上であるエピソードが全て検出される。なお、具体的なカウンティング方法については前述の各カウンティング方法のいずれかを用いるものであってよい。
【００２８】
これに対して、第１の実施形態においては、パターン検出装置１は、継続時間の閾値τ、ウィンドウサイズ、即ちウィンドウ内に含まれるイベントの数Wがさらに与えられる。そして、パターン検出装置１は、エピソードの継続時間がτ以内かつ頻度がmin_supおよび長さがlmin以上であるウィンドウ内のエピソードを検出する。なお、前述の通り、イベントシーケンスには時刻が含まれない場合もある。この場合は、τは継続数、即ちエピソードの検出範囲を示す連続するイベントの個数であるものとする。
【００２９】
さらに、この場合は、スライド幅Rが設定されており、最新データの到着等に合わせてウィンドウはRだけスライドする。そして、図５に示すように、スライドによってウィンドウの範囲に含まれなくなる古いイベント集合およびウィンドウの範囲に新たに含まれることとなる新しいイベント集合が発生する。以降の説明において、スライドによってウィンドウの範囲に含まれなくなったイベントを削除されたイベント、逆に、ウィンドウに新たに含まれるようになったイベントを追加されたイベントと呼ぶ。
【００３０】
図６を用いて、ウィンドウのスライドの具体例について説明する。図６は、ウィンドウのスライドについて説明するための図である。図６においては、ウィンドウサイズWを８、スライド幅Rを４とした場合に、ウィンドウがW1に示す位置からW2に示す位置に移動したものとする。この場合、11:20〜11:24のイベントは範囲外となるため、W1においてこれらのイベントは削除され、また、これらのイベントを含むエピソードはカウントされなくなる。逆に、11:36〜11:42のイベントは新たに範囲内となるため、これらのイベントが追加され、また、これらのイベントを含むエピソードがカウントされるようになる。
【００３１】
（カウント部）
引き続き図１を用いて、パターン検出装置１の構成について説明する。図１に示すように、カウント部１０は、エピソード拡張部１１を有する。さらに、エピソード拡張部１１は、イベント位置ビットブロック作成部１１１、マスク演算部１１２、継続時間符号化部１１３、およびエピソード位置ビットブロック作成部１１４を有する。
【００３２】
まず、エピソード拡張部１１の各部の概要について説明する。イベント位置ビットブロック作成部１１１は、イベントの種類の数をｍ、範囲に含まれるイベントの数をｎとするｍ×ｎ行列であって、ｉ番目の種類のイベントが範囲のｊ番目の位置に存在する場合は、行列の成分ａｉｊの値を１とし、存在しない場合は行列の成分ａｉｊの値を０とすることで各成分の値が決定される行列であるイベント位置ビットブロックを作成する。
【００３３】
また、マスク演算部１１２は、イベント位置ビットブロックの各イベントに対応する行ベクトルであるイベント位置ビットベクトルから、成分の値が１である位置を示す番号をｉｄとして取得し、長さがｎのベクトルであって、範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベント、または、該範囲に追加されたイベントのうち最初に発生したイベントからｉｄが示す位置までの値が０、ｉｄが示す位置より先の値が１であるベクトルであるマスクビットベクトルを、イベントおよびｉｄ毎に作成する。
【００３４】
また、継続時間符号化部１１３は、長さがｎのベクトルであって、ｉｄが示す位置から、範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベントから時系列と逆方向、または、該範囲に追加されたイベントのうち最初に発生したイベントから時系列順の方向かつイベントシーケンスにおける所定の継続時間の範囲に含まれる位置の成分の値が１、それ以外の位置の値が０であるベクトルであるタイムビットベクトルを作成し、マスクビットベクトルとタイムビットベクトルの論理積であるタイムマスクビットベクトルを作成する。
【００３５】
また、エピソード位置ビットブロック作成部１１４は、第１のイベントに基づいて作成されたタイムマスクビットベクトルと、第２のイベントに基づいて作成されたイベント位置ビットベクトルとの論理積の集合であるエピソード位置ビットブロックを作成する。そして、カウント部１０は、イベントに対応するエピソード位置ビットブロックにおける値が１である成分の数を、該イベントを始点または終点とするエピソードの出現回数としてカウントする。
【００３６】
カウント部１０は、全体としてイベントシーケンスのウィンドウ内に含まれるエピソードをカウントする。また、加減部３０は、カウント部１０がカウントした出現回数に基づく頻度を記憶部３に保存する。また、加算部３１は頻度の加算を行う。そして、減算部３２は頻度の減算を行う。エピソード拡張部１１は、所定の手順に従って、あるイベントに他のイベントを接続させ、エピソードの拡張を行う。以降、エピソード拡張部１１の各部について詳細に説明する。
【００３７】
エピソード拡張部１１のイベント位置ビットブロック作成部１１１は、図７に示すように、ウィンドウ内のイベントの位置をビットで符号化し、位置ビットブロックを作成する。図７は、第１の実施形態に係るパターン検出装置によるイベントの位置ビットブロックの作成方法の一例を示す図である。図７の例では、スライド幅Rを4としている。そして、位置ビットブロックには、例えば、イベントａが、ウィンドウ内のイベントシーケンスの１、８、９番目に存在していることが示されている。また、位置ビットブロックには、イベントｂが、ウィンドウ内のイベントシーケンスの２、１１番目に存在していることが示されている。
【００３８】
以降、イベント位置ビットブロック作成部１１１において作成された位置ビットブロックをイベント位置ビットブロックと呼ぶ。また、イベント位置ビットブロックのようにビット符号により構成されたブロックから、あるイベントについて１行を取り出したものをビットベクトルと呼ぶ。また、図中にビットベクトルとして例が示されている場合であっても、複数のイベントに拡張して考えることができる場合は、ビットブロックとして説明する場合もある。
【００３９】
エピソード拡張部１１のマスク演算部１１２は、位置ビットブロックに含まれるあるイベントの位置ビットベクトルに対してマスク演算を行う。マスク演算部１１２は、イベントｘのイベント位置ビットブロックにおける位置ビットベクトルP(x)と、P(x)におけるビットが１である要素の番号ｉｄが与えられた時に、式（３）に従ってマスク演算を行う。ここで、式（３）は、ｉｄまでの要素を０、以降の要素を１とすることを示している。
【００４０】
【数３】
2017004437.tif 000005
【００４１】
図８を用いて、マスク演算によって得られる結果について説明する。図８は、第１の実施形態に係るパターン検出装置によるマスク演算の一例を示す図である。この場合、図７に示すイベント位置ビットブロックから、イベントｂの位置ビットベクトルとして010000000010が得られる。そして、ｉｄを２としてマスク演算を行った結果、001111111111が得られる。同様に、各イベントおよび各ｉｄについてもマスク演算を行う。なお、イベントｂについては、２の他に１１がｉｄとなり得る。また、イベントａについては、１、８、９がｉｄになり得る。以降、マスク演算によって得られた結果のベクトルをマスクビットベクトルと呼ぶ。
【００４２】
エピソード拡張部１１の継続時間符号化部１１３は、まず、エピソードの継続時間をビット化し、タイムビットベクトルを作成する。そして、タイムビットベクトルとマスクビットベクトルの論理積をタイムマスクビットベクトルとして算出する。
【００４３】
タイムビットベクトルは、イベントｘの位置ビットベクトルにおけるビットが１である要素の番号ｉｄが与えられた時に、式（４）に従ってｉｄの時間から継続時間τの間のビットを１、それ以外を０で符号化することで得られる。
【００４４】
【数４】
2017004437.tif 000006
【００４５】
そして、式（５）に示すように、タイムビットベクトルとマスクビットベクトルの論理積を算出する。図９の例では、τを１０分に設定し、タイムビットベクトルとして011111100000が得られる。図９は、第１の実施形態に係るパターン検出装置によるタイムビットブロックの作成方法の一例を示す図である。また、タイムビットベクトルとマスクビットベクトルの論理積としてタイムマスクベクトル001111100000が得られる。
【００４６】
【数５】
2017004437.tif 000007
【００４７】
エピソード拡張部１１のエピソード位置ビットブロック作成部１１４は、エピソード単位の位置ビットブロックであるエピソード位置ビットブロックを作成する。図１０を用いて、イベントｂについて、長さ２のエピソードのエピソード位置ビットブロックを作成する場合の例について説明する。図１０は、第１の実施形態に係るパターン検出装置によるエピソードの位置ビットブロックの作成方法の一例を示す図である。イベントｂの位置ビットベクトルより、イベントｂのタイムマスクビットベクトルを作成する手順は前述の通りである。ここで、イベントｂのタイムマスクビットベクトルと、イベントｆの位置ビットベクトルの論理積を算出することで、＜ｂ，ｆ＞というエピソードの位置ビットブロックを得ることができる。
【００４８】
さらに、長さ３以上のエピソードに対しては、長さ２のエピソード位置ビットブロックに対し前述の手順を適用することにより、エピソードの拡張を行うことができ、長さ３のエピソード位置ビットブロックを得ることができる。同様に、長さｎのエピソード位置ブロックが得られれば、エピソード拡張による長さｎ＋１のエピソード位置ビットブロックを得ることができる。
【００４９】
そして、例えば、カウント部１０は、得られたエピソード位置ビットブロックにおいて、ビットが１である箇所をカウントすることで、各エピソードの出現回数をカウントする。また、エピソード拡張部１１は、各手順において所定の条件を満たさないイベントやエピソードをエピソード拡張の対象から除外することもできる。また、ウィンドウのスライドによって発生する追加イベントまたは削除イベントのみをエピソード拡張の対象としてもよい。
【００５０】
例えば、カウント部１０および加減部３０は、ウィンドウのスライドが発生した場合に下記のような処理を行ってもよい。即ち、エピソード拡張部１１は追加イベントを終点とするエピソードに対してエピソード拡張を行う。そして、加算部３１は得られたエピソードの数を基に頻度を加算する。また、エピソード拡張部１１は削除イベントを始点とするエピソードに対してエピソード拡張を行う。そして、減算部３２は、得られたエピソードの数を基に頻度を減算する。
【００５１】
スケッチ処理部２０は、ウィンドウが一定のスライド幅ずつ移動する場合に、イベント位置ビットブロックをスライド幅毎に時間ブロックに分割し、時間ブロックの桁数のビット列が取り得る各値に対して、正の整数で表されるＩＤを設定し、時間ブロック毎に、ＩＤの最大値より大きい素数であって、互いに異なる素数を割り当て、素数の積を法として、時間ブロック毎のＩＤとペアになる解を中国の剰余定理に基づいて算出する。
【００５２】
（スケッチ処理部）
スケッチ処理部２０の処理について具体例を挙げて説明する。スケッチ処理部２０は、カウント部１０で生成される位置ビットブロックを、式（６）に示す中国の剰余定理（ＣＲＴ:Chinese  Remainder  Theorem）に基づく圧縮構造、即ちスケッチに変換して記憶部３に保存する。そして、剰余演算により、スライド幅単位で位置ビットブロックを復元する。また、スケッチ処理部２０は、ウィンドウのスライドに伴い、追加イベントおよび削除イベントを反映させ、スケッチの更新を行う。
【００５３】
【数６】
2017004437.tif 000008
【００５４】
なお、中国の剰余定理は、全ての自然数は１つ以上の素数の積として表せ、その表し方は積の順序を除いてただ一通りに表すことができるという素因数分解の一意性（Unique  Factorization  Theorem）に基づいている。そして、スケッチ処理部２０は、各位置ビットベクトルを一の値で表す。
【００５５】
図１１に示すように、スケッチ生成部２１は、位置ビットブロックに基づいてスケッチを作成する。図１１は、第１の実施形態に係るパターン検出装置によるスケッチの作成方法の一例を示す図である。図１１の（１）に示すように、スケッチ生成部２１は、まずスライド幅単位で取り得るビット列に対してＩＤラベルを付与する。この場合、スライド幅が4であるので、取り得るビット列は0000〜1111の１６通りである。例えば、0000というビットブロックには１、0011というビットブロックには４が付与される。
【００５６】
次に、（２）に示すように、ウィンドウ内のイベントをスライド幅R単位で区切り、時間ブロックに分割し、それぞれに対してＩＤラベルの最大値より大きい値の素数を設定する。素数の値や割当てる順番は問わないが、計算の観点から小さい値から順番に割り当てることが望ましい。この場合は、ＩＤラベルの最大値が１６であり、１６より大きい素数である１７から始まり、１９、２３、…、４３と割り当てていく。
【００５７】
そして、（３）に示すように、ウィンドウ内の各イベントの位置ビットブロックを（１）で設定したＩＤラベルを基に変換する。そして、（４）に示すように、イベント毎に時間ブロックの素数で割った余りがその時間ブロックにおけるビットブロックのＩＤとなるような値Skを中国の剰余定理で求め、スケッチとして記憶部３に保存する。
【００５８】
そして、スケッチ更新部２２は、図１２に示すように、ウィンドウのスライドが発生した場合は、追加イベントの情報および削除イベントの情報によって記憶部３に保存されているスケッチを更新する。図１２は、第１の実施形態に係るパターン検出装置によるスケッチの更新方法の一例を示す図である。この場合、スケッチ更新部２２は、混合基数表記によるＣＲＴを用いる。
【００５９】
まず、Skは、混合基数表記によって式（７−１）のように表すことができる。なお、式（７−１）のSkは式（７−２）に示す合同式を満たす。また、c0,…,cr-2は式（７−３）に示す条件を満たす。
【００６０】
【数７】
2017004437.tif 000009
【００６１】
まず、スケッチ追加部２２１は、位置を表すビット列を変換したＩＤがbr、時間ブロックを表す素数がmrである追加イベントが与えられた場合、式（８−１）に従って新たなスケッチであるSk’を算出する。また、式（８−１）におけるCr-1は、式（８−２）の合同式を解くことで求められる。
【００６２】
【数８】
2017004437.tif 000010
【００６３】
また、削除イベントが生じた場合は、スケッチは、式（９−１）の合同式で示されるSkから、式（９−２）の合同式で示されるSk’に変化する。この時、スケッチ削除部２２２は、位置を表すビット列を変換したＩＤがbr、時間ブロックを表す素数がmrである削除イベントが与えられた場合、式（９−３）に従って新たなスケッチであるSk’を算出する。即ち、Sk’は、式（９−３）において、Skをm2…mrで割った余りである。
【００６４】
【数９】
2017004437.tif 000011
【００６５】
また、抽出部４は、出現回数が所定の閾値以上であるエピソードを頻出パターンとして、抽出する。
【００６６】
［第１の実施形態の処理］
図１３を用いて、エピソード拡張部１１の処理について説明する。図１３は、第１の実施形態のエピソード拡張処理を示すフローチャートである。まず、イベント位置ビットブロック作成部１１１は、イベント毎の位置ビットブロックを作成し、ビットブロック符号化を行う（ステップＳ１１）。次に、マスク演算部１１２は、各イベントのｉｄに基づいてマスク演算を行い、マスクビットブロックを作成する（ステップＳ１２）。
【００６７】
そして、継続時間符号化部１１３は、継続時間τに基づいてタイムビットブロックを作成し、マスクビットブロックとの論理積を取ることでタイムマスクビットブロックを作成する（ステップＳ１３）。最後に、エピソード位置ビットブロック作成部１１４は、タイムマスクビットブロックと、後に続くイベントのイベント位置ビットブロックの論理積を取ることで、エピソード位置ビットブロックを作成し、エピソード拡張を行う（ステップＳ１４）。
【００６８】
図１４を用いて、スケッチ生成部２１の処理について説明する。図１４は、第１の実施形態のスケッチ生成処理を示すフローチャートである。まず、スケッチ生成部２１は、スライド幅単位で取り得るビット列に対してＩＤラベルを付与する（ステップＳ２１）。次に、スケッチ生成部２１は、ウィンドウ内のイベントをスライド幅単位で区切り、それぞれに素数を設定する（ステップＳ２２）。そして、スケッチ生成部２１は、位置ビットブロックを、位置ビットブロックを構成するビット列に対して付与されたＩＤラベルを基に変換する（ステップＳ２３）。最後に、スケッチ生成部２１は、中国の剰余定理によりスケッチを算出し保存する（ステップＳ２４）。
【００６９】
［第１の実施例］
ここで、具体的な処理を例に挙げて、本発明の第１の実施形態の実施例である第１の実施例について説明する。まず、図１５を用いて、第１の実施例の概要について説明する。図１５は、第１の実施例の概要を示す図である。図１５に示すように、第１の実施例においては、min_supを３、lminを２、τを１０分と設定する。そして、この時（ａ−ｂ，３），（ａ−ｂ−ｆ，３），（ａ−ｃ，４），（ａ−ｃ−ｆ，３），（ａ−ｆ，３），（ｂ−ｃ−ｆ，３），（ｂ−ｆ，３），（ｃ−ｆ，４）が結果として得られる。なお、例えば（ａ−ｂ−ｆ，３）とは、エピソード＜ａ，ｂ，ｆ＞の頻度が３であることを示している。また、第１の実施例において、パターン検出装置１は、ウィンドウのスライドが発生した場合、追加イベントに対してはbackward操作を行い、削除イベントに対してはforward操作を行う。また、backward操作およびforward操作は、主にカウント部１０によって行われる。そして、加減部３０の加算部３１および減算部３２はカウント結果に基づいて頻度を更新する。
【００７０】
また、この時、τを継続時間ではなく継続数としてもよい。その場合、例えば、τ＝３個とすると、図１５の左端のイベントａから開始するエピソードは左から３個の範囲に含まれるａ，ｂ，ｃから構成されるエピソードとなる。この場合も同様に、各イベントから開始するエピソードのうち、頻度がmin_sup以上、長さがlmin以上となるエピソードおよびその頻度が結果として得られる。
【００７１】
（backward操作）
backward操作において、カウント部１０は、追加ブロックに含まれるイベントをそれぞれ単一のイベントから構成されるエピソードとして頻度をカウントし加算する。次に、スケッチ処理部２０は、各要素の位置ビットブロックのスケッチを更新する。そして、カウント部１０は、追加ブロックの各要素に対し、追加ブロックの要素および継続時間の逆方向の範囲内の要素をエピソードの先頭に追加するエピソード拡張を行い、その頻度をカウントし更新する。なお、追加ブロックとは、ウィンドウのスライドによって追加されたイベントの集合である。また、この場合、カウント部１０のエピソード拡張部１１は、第１の実施形態で説明したエピソード拡張と逆方向のエピソード拡張を行う。
【００７２】
図１６等を用いて、backward操作の具体的な手順を説明する。図１６は、第１の実施例におけるbackward操作を説明するための図である。また、図１７は、第１の実施例におけるbackward操作におけるエピソード拡張を説明するための図である。まず、エピソード拡張部１１は、追加ブロックに含まれるイベント｛ａ，ｃ，ｂ，ｆ｝のイベント位置ビットブロックを作成する。この時、加算部３１は、追加ブロックに含まれる各イベントのみで構成されるエピソード＜ａ＞，＜ｃ＞，＜ｂ＞，＜ｆ＞の頻度を加算する。また、スケッチ更新部２２は追加ブロックをスケッチに追加し更新する。この時、スケッチ更新部２２は、追加されたイベント以外のイベントのスケッチには０ビットブロックを追加し更新する。さらに、カウント部１０は、追加ブロックに含まれるイベントをＡＤＤに格納しておく。
【００７３】
そして、カウント部１０は、追加ブロックの最初の時刻から継続時間τ以内の位置に含まれる全てのイベントを、スケッチを基に探しＣＨＫに格納する。そして、エピソード拡張部１１は、ＡＤＤに含まれるイベントに対して、ＡＤＤまたはＣＨＫに含まれるイベントを前に追加するエピソード拡張を行う。そして、加算部３１は、各条件を満たすエピソードが存在する場合、頻度を加算する。さらに、エピソード拡張部１１は、これらの処理を、ＡＤＤに含まれる全てのイベントに対し、拡張したエピソードが存在しなくなるまで繰り返し行う。
【００７４】
ここで、逆方向のエピソード拡張について説明する。まず、図１６に示すように、＜ａ＞のマスクビットベクトルは、右端からａが現れる位置までを０、それ以降を１としている。また、＜ａ＞のタイムビットベクトルは、R2の４ビット目から、継続時間τ以内の左側の範囲が１となっている。このように、backward操作においては、エピソード拡張部１１は、図８および図９の例とは逆方向のエピソード拡張を行う。さらに図１７に示すように、例えば、逆方向のエピソード拡張によって得られた＜ａ＞のタイムビットマスクベクトルと＜ｆ＞のイベント位置ビットベクトルの論理積を取ることで、＜ｆ，ａ＞のエピソード位置ビットベクトルが得られる。さらに、図１７に示す手順により、＜ｃ，ｆ，ａ＞のエピソード位置ビットベクトルが得られる。
【００７５】
（forward操作）
forward操作において、カウント部１０は、削除ブロックに含まれるイベント｛ａ，ｂ，ｃ，ｄ｝をそれぞれ単一のイベントから構成されるエピソードとして頻度をカウントし減算する。そして、エピソード拡張部１１は、削除ブロックの各要素に対し、削除ブロックの要素および継続時間の順方向の範囲内の要素をエピソードの末尾に追加するエピソード拡張を行い、その頻度をカウントし更新する。最後に、スケッチ処理部２０は、各要素の位置ビットブロックのスケッチを更新する。なお、削除ブロックとは、ウィンドウのスライドによって削除されたイベントの集合である。
【００７６】
図１８等を用いて、forward操作の具体的な手順を説明する。図１８は、第１の実施例におけるforward操作を説明するための図である。まず、カウント部１０は、スケッチから、ゼロビットブロックでないイベントを探し、ＤＥＬに格納する。この時、減算部３２は、削除ブロックに含まれる各イベント、即ちＤＥＬに格納されたイベントのみで構成されるエピソード＜ａ＞，＜ｂ＞，＜ｃ＞，＜ｄ＞の頻度を減算する。
【００７７】
そして、カウント部１０は、追加ブロックの最初の時刻から継続時間τ以内の位置に含まれる全てのイベントを、スケッチを基に探しＣＨＫに格納する。そして、エピソード拡張部１１は、ＤＥＬに含まれるイベントに対して、ＤＥＬまたはＣＨＫに含まれるイベントを後に追加するエピソード拡張を行う。そして、減算部３２は、各条件を満たすエピソードが存在する場合、頻度を減算する。さらに、エピソード拡張部１１は、これらの処理を、ＤＥＬに含まれる全てのイベントに対し、拡張したエピソードが存在しなくなるまで繰り返し行う。なお、forward操作において、エピソード拡張部１１は、図８〜１０等で説明した順方向のエピソード拡張を行う。
【００７８】
（第１の実施例の処理）
図１９等を用いて、第１の実施例の処理について説明する。まず、図１９を用いて処理の全体的な流れについて説明する。図１９は、第１の実施例の処理を示すフローチャートである。図１９に示すように、まず、ウィンドウがスライドされる（ステップＳ３１）。そして、カウント部１０は、backward操作を行う（ステップＳ３２）。また、カウント部１０等は、forward操作を行う（ステップＳ３３）。なお、backward操作およびforward操作の順序は逆であってもよいし、また、同時に非同期で行われるようにしてもよい。以降、backward操作およびforward操作の処理について説明する。
【００７９】
図２０を用いてbackward操作について説明する。図２０は、第１の実施例のbackward操作の処理を示すフローチャートである。図２０に示すように、まず、カウント部１０は、追加ブロックに含まれるイベントをＡＤＤに格納し、イベント位置ビットブロックを作成し、該イベントのみからなるエピソードの頻度を更新する（ステップＳ３２１）。そして、スケッチ処理部２０は、追加されたイベントをスケッチに追加し更新する（ステップＳ３２２）。
【００８０】
そして、カウント部１０は、追加ブロックの最初の時刻から継続時間以内の位置に含まれるイベントを探索し、ＣＨＫに格納する（ステップＳ３２３）。この場合、時系列の逆方向に向かって探索が行われる。そして、エピソード拡張部１１は、ＡＤＤ∩ＣＨＫであるイベントのエピソード拡張を行い、存在する場合はエピソードリストに加算する（ステップＳ３２４）。なお、エピソードリストとは、エピソードおよびエピソードの頻度を一覧にしたリストであり、記憶部３に保存されるようにしてもよい。
【００８１】
そして、エピソード拡張部１１は、拡張エピソードがある場合（ステップＳ３２５、Ｙｅｓ）は、さらにエピソード拡張および加算を行う。そして、エピソード拡張部１１は、拡張エピソードがなくなるまで（ステップＳ３２５、Ｎｏ）エピソード拡張および加算を繰り返し、その後処理を終了する。
【００８２】
図２１を用いて、forward操作について説明する。図２１は、第１の実施例のforward操作の処理を示すフローチャートである。図２１に示すように、まず、カウント部１０は、削除ブロックに含まれるゼロビットでないイベントを探索し、ＤＥＬに格納し、該イベントのみからなるエピソードの頻度を更新する（ステップＳ３３１）。そして、カウント部１０は、削除ブロックの最後の時刻から継続時間以内の位置に含まれるイベントを探索し、ＣＨＫに格納する（ステップＳ３３２）。この場合、時系列方向に向かって探索が行われる。
【００８３】
そして、エピソード拡張部１１は、ＤＥＬに含まれるイベントを、ＤＥＬ∩ＣＨＫであるイベントでエピソード拡張を行い、存在する場合はエピソードリストを減算する（ステップＳ３３３）。
【００８４】
そして、エピソード拡張部１１は、拡張エピソードがある場合（ステップＳ３３４、Ｙｅｓ）は、さらにエピソード拡張および減算を行う。そして、エピソード拡張部１１は、拡張エピソードがなくなるまで（ステップＳ３３４、Ｎｏ）エピソード拡張および減算を繰り返し、その後スケッチの更新を行い（ステップＳ３３５）、処理を終了する。
【００８５】
［第２の実施例］
次に、第２の実施例について説明する。第２の実施例においては、図３に示す、non-overlappedなエピソードのカウンティングを行う。第２の実施例においては、基本的な構成および処理は第１の実施例と同様である。第２の実施例において、カウント部１０は、重複エピソードを排除するために、カウントしたエピソードの時間情報を保持し、保持した区間と重複するエピソードの頻度を更新しないようにする。
【００８６】
即ち、第２の実施例において、加減部３０は、カウント部１０が追加出現回数をカウントした追加されたイベントまたは追加されたイベントを終点とするエピソードの時刻の区間が、最後にカウントした追加されたイベントまたは追加されたイベントを終点とするエピソードの時刻の区間と重複しない場合に、追加出現回数の加算を行う。また、加減部３０は、カウント部１０が追加出現回数をカウントした削除されたイベントまたは削除されたイベントを始点とするエピソードの時刻の区間が、範囲をイベントシーケンスの所定方向に移動させた後最初にカウントしたイベントを始点とするエピソードの時刻の区間と重複しない場合に、削減出現回数の減算を行う。
【００８７】
なお、カウント部１０は、イベントの追加の場合は、最後にカウントしたエピソードの該当区間を保持し、イベントの削除の場合は、最初にカウントしたエピソードの該当区間を保持する。また、エピソード拡張部１１は、頻度を更新しなかったエピソードについても、エピソード拡張を行う。なぜなら、エピソードの開始点が前のマッチの開始点よりも後である場合、持続時間の関係で後から始まる方がより長いエピソードが見つかる可能性があるためである。
【００８８】
まず、図２２を用いて、第２の実施例の概要について説明する。図２２は、第２の実施例の概要を示す図である。図２２に示すように、第２の実施例においては、min_supを２、lminを２、τを１０分と設定する。そして、この時（ａ−ｂ，２），（ａ−ｂ−ｆ，２），（ａ−ｃ，２），（ａ−ｃ−ｆ，２），（ａ−ｆ，２），（ｂ−ｆ，２），（ｃ−ｆ，３），（ｆ−ｃ，２）が結果として得られる。
【００８９】
（backward操作）
図２３および図２４を用いて、backward操作の具体的な手順を説明する。図２３および２４は、第２の実施例におけるbackward操作を説明するための図である。まず、図２３に示すように、｛ｆ，ｃ，ｆ，ａ｝というイベントブロックが追加された場合、カウント部１０は、ＡＤＤに｛ｆ，ｃ，ａ｝を格納し、ＣＨＫに｛ａ，ｂ，ｃ，ｄ｝を格納する。この時、ＡＤＤ∩ＣＨＫには｛ａ，ｂ，ｃ，ｄ，ｆ｝が含まれることになる。そして、例えば、イベントａに対してイベントｃを追加するエピソード拡張を行うと、エピソード＜ｃ，ａ＞が得られる。これは、図２３に示す11:27のｃと11:35のａに対応しており、最後にカウントしたエピソードの該当区間として11:27-11:35が保持される。
【００９０】
次に、図２４に示すように、｛ａ，ｃ，ｂ，ｆ｝というイベントブロックがさらに追加された場合、カウント部１０は、ＡＤＤに｛ａ，ｃ，ｂ，ｆ｝を格納し、ＣＨＫに｛ｃ，ｆ，ａ｝を格納する。この時、ＡＤＤ∩ＣＨＫには｛ａ，ｂ，ｃ，ｆ｝が含まれることになる。そして、イベントａに対してイベントｃを追加するエピソード拡張を行うと、エピソード＜ｃ，ａ＞が得られる。これは、図２４に示す11:27のｃと11:36のａに対応しており、保持している区間11:27-11:35と重複するため、頻度の更新は行われない。その後、さらにエピソード拡張が行われる。
【００９１】
（forward操作）
図２５および図２６を用いて、forward操作の具体的な手順を説明する。図２５および２６は、第２の実施例におけるforward操作を説明するための図である。まず、図２５に示すように、｛ａ，ｂ，ｃ，ｄ｝というイベントブロックが削除された場合、カウント部１０は、ＤＥＬに｛ａ，ｂ，ｃ，ｄ｝を格納し、ＣＨＫに｛ｆ，ｃ｝を格納する。この時、ＤＥＬ∩ＣＨＫには｛ａ，ｂ，ｃ，ｄ，ｆ｝が含まれることになる。そして、例えば、イベントｃに対してイベントｆを追加するエピソード拡張を行うと、エピソード＜ｃ，ｆ＞が得られる。これは、図２５に示す11:23のｃと11:26のｆに対応しており、最初にカウントしたエピソードの該当区間として11:23-11:26が保持される。
【００９２】
次に、図２６に示すように、｛ｆ，ｃ，ｆ，ａ｝というイベントブロックがさらに削除された場合、カウント部１０は、ＤＥＬに｛ｆ，ｃ，ａ｝を格納し、ＣＨＫに｛ａ，ｃ，ｂ，ｆ｝を格納する。この時、ＤＥＬ∩ＣＨＫには｛ａ，ｂ，ｃ，ｆ｝が含まれることになる。そして、イベントｃに対してイベントｆを追加するエピソード拡張を行うと、エピソード＜ｃ，ａ＞が得られる。これは、図２６に示す11:27のｃと11:30のｆに対応しており、保持している区間11:23-11:26と重複しないため、頻度の更新が行われ、保持区間が11:27-11:30に更新される。
【００９３】
［効果］
カウント部１０は、イベントシーケンスにおいて、ウィンドウにおいて発生したイベントおよびエピソードの出現回数をカウントし、ウィンドウをイベントシーケンスの所定方向に移動させるたびに、追加されたイベントまたは追加されたイベントを終点とするエピソードの出現回数である追加出現回数をカウントし、削除されたイベントまたは削除されたイベントを始点とするエピソードの出現回数である削減出現回数をカウントする。加減部３０は、出現回数に追加出現回数の加算を行い、削減出現回数の減算を行う。また、抽出部４は、イベントまたはエピソードの出現回数が所定の閾値以上である場合、該イベントまたはイベントの組合せを抽出する。これにより、エピソードのリスト出現回数の差分更新が可能となり、イベントストリームから効率的にエピソードを得ることができる。
【００９４】
イベント位置ビットブロック作成部１１１は、イベントの種類の数をｍ、範囲に含まれるイベントの数をｎとするｍ×ｎ行列であって、ｉ番目の種類のイベントが範囲のｊ番目の位置に存在する場合は、行列の成分ａｉｊの値を１とし、存在しない場合は行列の成分ａｉｊの値を０とすることで各成分の値が決定される行列であるイベント位置ビットブロックを作成する。また、マスク演算部１１２は、イベント位置ビットブロックの各イベントに対応する行ベクトルであるイベント位置ビットベクトルから、成分の値が１である位置を示す番号をｉｄとして取得し、長さがｎのベクトルであって、範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベント、または、該範囲に追加されたイベントのうち最初に発生したイベントからｉｄが示す位置までの値が０、ｉｄが示す位置より先の値が１であるベクトルであるマスクビットベクトルを、イベントおよびｉｄ毎に作成する。
【００９５】
また、継続時間符号化部１１３は、長さがｎのベクトルであって、ｉｄが示す位置から、範囲が移動した場合において該範囲から削除されたイベントのうち最後に発生したイベントから時系列と逆方向、または、該範囲に追加されたイベントのうち最初に発生したイベントから時系列順の方向かつイベントシーケンスにおける所定の継続時間の範囲に含まれる位置の成分の値が１、それ以外の位置の値が０であるベクトルであるタイムビットベクトルを作成し、マスクビットベクトルとタイムビットベクトルの論理積であるタイムマスクビットベクトルを作成する。
【００９６】
また、エピソード位置ビットブロック作成部１１４は、第１のイベントに基づいて作成されたタイムマスクビットベクトルと、第２のイベントに基づいて作成されたイベント位置ビットベクトルとの論理積の集合であるエピソード位置ビットブロックを作成する。そして、カウント部１０は、イベントに対応するエピソード位置ビットブロックにおける値が１である成分の数を、該イベントを始点または終点とするエピソードの出現回数としてカウントする。これにより、ウィンドウの移動に対応した効率的な出現回数のカウントが可能となる。
【００９７】
スケッチ処理部２０は、ウィンドウが一定のスライド幅ずつ移動する場合に、イベント位置ビットブロックをスライド幅毎に時間ブロックに分割し、時間ブロックの桁数のビット列が取り得る各値に対して、正の整数で表されるＩＤを設定し、時間ブロック毎に、ＩＤの最大値より大きい素数であって、互いに異なる素数を割り当て、素数の積を法として、時間ブロック毎のＩＤとペアになる解を中国の剰余定理に基づいて算出する。これにより、位置ビットブロックの効率的な圧縮が可能となり、また、差分のみの更新が可能となる。
【００９８】
加減部３０は、カウント部１０が追加出現回数をカウントした追加されたイベントまたは追加されたイベントを終点とするエピソードの時刻の区間が、最後にカウントした追加されたイベントまたは追加されたイベントを終点とするエピソードの時刻の区間と重複しない場合に、追加出現回数の加算を行う。また、加減部３０は、カウント部１０が追加出現回数をカウントした削除されたイベントまたは削除されたイベントを始点とするエピソードの時刻の区間が、範囲をイベントシーケンスの所定方向に移動させた後最初にカウントしたイベントを始点とするエピソードの時刻の区間と重複しない場合に、削減出現回数の減算を行う。これにより、non-overlapped  basedなカウンティング方法によるカウントが可能となる。
【００９９】
［その他の実施形態］
Aprioriの性質が成り立つカウンティングに対してはさらに効率の良いカウンティングを行うことができる。Aprioriの性質とは、あるエピソードαがmin_supを満たすためには、αを構成するすべてのサブエピソードもmin_supを満たす、というものである。例えば、＜ａ，ｂ，ｃ＞というエピソードがmin_supである３を満たすためには、サブエピソード＜ａ＞，＜ｂ＞，＜ｃ＞，＜ａ，ｂ＞，＜ａ，ｃ＞，＜ｂ，ｃ＞の頻度も３以上でなければならない。
【０１００】
なお、第２の実施例のカウンティングにおいては、Aprioriの性質が成り立つため、min_supを超えたイベントのみでエピソード拡張を行うことで、所定の頻度以上のエピソードを抽出したい場合には、追加・削除される全てのイベントをチェックする必要がなくなる。
【０１０１】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）および当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１０２】
また、本実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１０３】
［プログラム］
図２７は、プログラムが実行されることにより、パターン検出装置が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【０１０４】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【０１０５】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、パターン検出装置の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、パターン検出装置における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【０１０６】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【０１０７】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【０１０８】
１  パターン検出装置
２  制御部
３  記憶部
４  抽出部
１０  カウント部
１１  エピソード拡張部
２０  スケッチ処理部
２１  スケッチ生成部
２２  スケッチ更新部
３０  加減部
３１  加算部
３２  減算部
１１１  イベント位置ビットブロック作成部
１１２  マスク演算部
１１３  継続時間符号化部
１１４  エピソード位置ビットブロック作成部
２２１  スケッチ追加部
２２２  スケッチ削除部
【図１】
2017004437.tif 000012
【図２】
2017004437.tif 000013
【図３】
2017004437.tif 000014
【図４】
2017004437.tif 000015
【図５】
2017004437.tif 000016
【図６】
2017004437.tif 000017
【図７】
2017004437.tif 000018
【図８】
2017004437.tif 000019
【図９】
2017004437.tif 000020
【図１０】
2017004437.tif 000021
【図１１】
2017004437.tif 000022
【図１２】
2017004437.tif 000023
【図１３】
2017004437.tif 000024
【図１４】
2017004437.tif 000025
【図１５】
2017004437.tif 000026
【図１６】
2017004437.tif 000027
【図１７】
2017004437.tif 000028
【図１８】
2017004437.tif 000029
【図１９】
2017004437.tif 000030
【図２０】
2017004437.tif 000031
【図２１】
2017004437.tif 000032
【図２２】
2017004437.tif 000033
【図２３】
2017004437.tif 000034
【図２４】
2017004437.tif 000035
【図２５】
2017004437.tif 000036
【図２６】
2017004437.tif 000037
【図２７】
2017004437.tif 000038