(57)【要約】【課題】利用者の行動に関するログ情報などから、ログ情報の順序性を考慮して特定の行動パターンを効率よくかつノイズに対してロバストに検出することができるようにする。【解決手段】所定の行動パターンによって生成される検出対象パターン及びログデータに含まれる非数値情報を、数値情報に変換する数値変換部１３と、数値情報に変換されたログデータのなかから、数値情報に変換された検出対象パターンに類似する部分シーケンスを、両者の類似度を用いて検出する、類似部分シーケンス検出部１５とを備える。【選択図】図１
2011138422.tif 000002
【特許請求の範囲】
【請求項１】
非数値情報を含んで時系列に生成されるログデータのなかから、所定の行動パターンによって生成されるイベントログシーケンスを規定する検出対象パターンに類似する類似部分シーケンスを検出することによって、前記所定の行動パターンに類似した行動パターンを検出する行動パターン検出装置であって、
前記検出対象パターン及び前記ログデータに含まれる非数値情報を、その非数値情報の種類毎に定められた所定の変換手続きによって数値情報に変換する数値変換部と、
数値情報に変換された前記ログデータのなかから、数値情報に変換された前記検出対象パターンに類似する類似部分シーケンスを、両者の類似度を用いて検出する、類似部分シーケンス検出部と
を備えることを特徴とする行動パターン検出装置。
【請求項２】
前記類似部分シーケンス検出部は、
前記数値情報に変換された前記検出対象パターンのなかの部分シーケンスと、前記数値情報に変換された前記ログデータのなかの部分シーケンスとを対応づけた部分シーケンスペアの類似度を、動的計画法に基づく単一のスコア行列を用いて算出し、
前記算出した類似度と、その類似度の算出に用いた前記検出対象パターンと前記ログデータの適合部分の開始位置及び終了位置と、を対応づけて前記スコア行列に記憶し、
前記スコア行列に記憶された前記類似度を用いて、前記検出対象パターンに類似する前記ログデータのなかの前記類似部分シーケンスを検出する
ことを特徴とする請求項１に記載の行動パターン検出装置。
【請求項３】
非数値情報を含んで時系列に生成されるログデータのなかから、所定の行動パターンによって生成されるイベントログシーケンスを規定する検出対象パターンに類似する類似部分シーケンスを検出することによって、前記所定の行動パターンに類似した行動パターンを検出する行動パターン検出装置によって実行される行動パターン検出方法であって、
前記行動パターン検出装置が、前記検出対象パターン及び前記ログデータに含まれる非数値情報を、その非数値情報の種類毎に定められた所定の変換手続きによって数値情報に変換する数値変換ステップと、
前記行動パターン検出装置が、数値情報に変換された前記ログデータのなかから、数値情報に変換された前記検出対象パターンに類似する類似部分シーケンスを、両者の類似度を用いて検出する、類似部分シーケンス検出ステップと
を備えることを特徴とする行動パターン検出方法。
【請求項４】
前記類似部分シーケンス検出ステップにおいて、前記行動パターン検出装置は、
前記数値情報に変換された前記検出対象パターンのなかの部分シーケンスと、前記数値情報に変換された前記ログデータのなかの部分シーケンスとを対応づけた部分シーケンスペアの類似度を、動的計画法に基づく単一のスコア行列を用いて算出し、
前記算出した類似度と、その類似度の算出に用いた前記検出対象パターンと前記ログデータの適合部分の開始位置及び終了位置と、を対応づけて前記スコア行列に記憶し、
前記スコア行列に記憶された前記類似度を用いて、前記検出対象パターンに類似する前記ログデータのなかの前記類似部分シーケンスを検出する
ことを特徴とする請求項３に記載の行動パターン検出方法。
【請求項５】
コンピュータを、請求項１または請求項２に記載の行動パターン検出装置として機能させるための行動パターン検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列に生成されるログデータを分析して所定の行動パターンを検出する、行動パターン検出装置、行動パターン検出方法及び行動パターン検出プログラムに関する。
【背景技術】
【０００２】
コンピュータシステムの高度化、高性能化により、例えば、利用者の行動に関する様々なログ情報を取得し、保持することが可能となり、これらのログ情報を分析することで、利用者の行動パターンを把握したいという要求が高まっている。例えば、サーバのアクセスログや端末の操作ログをチェックすることにより、利用者の不正な行動を検出したり、利用者が既定のルールに則って作業を行っていることを検証したいといったニーズがある。
【０００３】
そのために利用可能な従来技術として、例えば、検出したいイベントの系列を正規表現によって記述し、取得したログ情報とマッチングを行う方法が考えられるが、正規表現ではノイズイベントや同一イベントの繰返しの取扱いに膨大な計算量を要するため、現実的ではない。
【０００４】
また、取得したログ情報のなかから、特定の条件に該当するイベントの発生を検出する方法（例えば、特許文献１）、通常とは異なる操作パターンを検出する方法（例えば、非特許文献１）が開示されているが、これらはいずれもログ情報の順序性を考慮して特定の行動パターンを検出するものではない。
【０００５】
一方、単一のスコア行列を用いて、２つの数値データストリームの時間軸を伸縮させて動的マッチングを行い、類似する部分シーケンスのペアを効率よく検出する類似部分シーケンス検出技術が、特許文献２及び非特許文献２に開示されている。これらの技術によれば、データストリーム（連続的に与えられ、時間順に整列されているデータであって、その更新頻度や間隔は一定ではない場合があり、逐次入力される情報である。）のなかに含まれるノイズの影響を減らして、類似する部分シーケンスペアをロバスト（頑健）に検出することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−１４８９４６号公報
【特許文献２】特開２００９−１９９５０７号公報
【非特許文献】
【０００７】
【非特許文献１】K.Yamanishi：”Dynamic Syslog Mining for Network Failure Monitoring”，Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2005), pp.499-508, 2005.
【非特許文献２】豊田真智子，櫻井保志，市川俊一：”データストリームのための部分シーケンスマッチング”, DEIM Forum 2009 Web論文集, E8-5, 2009年3月
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前記のように、従来技術では、ログ情報（ログデータ）のなかから、ログ情報の順序性を考慮して特定の行動パターンを効率よくかつノイズに対してロバストに検出することができないという問題点があった。本発明は、前記の問題点を解消するためになされたものであり、ログ情報のなかから、ログ情報の順序性を考慮して特定の行動パターンを効率よくかつノイズに対してロバストに検出することができる、行動パターン検出装置、行動パターン検出方法及び行動パターン検出プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００９】
前記の課題を解決するために、本発明の行動パターン検出装置は、非数値情報を含んで時系列に生成されるログデータのなかから、所定の行動パターンによって生成されるイベントログシーケンスを規定する検出対象パターンに類似する類似部分シーケンスを検出することによって、前記所定の行動パターンに類似した行動パターンを検出する行動パターン検出装置であって、前記検出対象パターン及び前記ログデータに含まれる非数値情報を、その非数値情報の種類毎に定められた所定の変換手続きによって数値情報に変換する数値変換部と、数値情報に変換された前記ログデータのなかから、数値情報に変換された前記検出対象パターンに類似する類似部分シーケンスを、両者の類似度を用いて検出する、類似部分シーケンス検出部とを備えることを特徴とする。
【００１０】
また、前記類似部分シーケンス検出部は、前記数値情報に変換された前記検出対象パターンのなかの部分シーケンスと、前記数値情報に変換された前記ログデータのなかの部分シーケンスとを対応づけた部分シーケンスペアの類似度を、動的計画法に基づく単一のスコア行列を用いて算出し、前記算出した類似度と、その類似度の算出に用いた前記検出対象パターンと前記ログデータの適合部分の開始位置及び終了位置と、を対応づけて前記スコア行列に記憶し、前記スコア行列に記憶された前記類似度を用いて、前記検出対象パターンに類似する前記ログデータのなかの前記類似部分シーケンスを検出することを特徴とする。
【００１１】
また、本発明の行動パターン検出方法は、非数値情報を含んで時系列に生成されるログデータのなかから、所定の行動パターンによって生成されるイベントログシーケンスを規定する検出対象パターンに類似する類似部分シーケンスを検出することによって、前記所定の行動パターンに類似した行動パターンを検出する行動パターン検出装置によって実行される行動パターン検出方法であって、前記行動パターン検出装置が、前記検出対象パターン及び前記ログデータに含まれる非数値情報を、その非数値情報の種類毎に定められた所定の変換手続きによって数値情報に変換する数値変換ステップと、前記行動パターン検出装置が、数値情報に変換された前記ログデータのなかから、数値情報に変換された前記検出対象パターンに類似する類似部分シーケンスを、両者の類似度を用いて検出する、類似部分シーケンス検出ステップとを備えることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、ログ情報（ログデータ）のなかから、ログ情報の順序性を考慮して特定の行動パターンを効率よくかつノイズに対してロバストに検出することができる、行動パターン検出装置、行動パターン検出方法及び行動パターン検出プログラムを提供することができる。また、本発明によれば、ログデータのなかの行動パターンの検出に必要なデータをすべて数値化するので、２つの数値データストリームのなかから類似部分シーケンスペアを検出する従来技術の適用が可能となり、効率よくかつノイズに対してロバストな行動パターンの検出が可能となる。また、本発明によれば、類似部分シーケンスペアを検出するために必要な計算量を大幅に減らすことができ、高速処理が可能となる。
【図面の簡単な説明】
【００１３】
【図１】行動パターン検出装置の構成を示したブロック図である。
【図２】行動パターン検出装置における基本的なデータの流れを示した説明図である。
【図３】行動パターン検出方法の手順を示したフローチャートである。
【図４】実施例１の行動パターン検出についての説明図である。
【図５】ファイル操作イベントを数値に変換するための変換テーブルの例である。
【図６】実施例１の検出対象パターンと利用者ログデータとを数値化した結果を示したものである。
【図７】実施例２の行動パターン検出についての説明図である。
【図８】ドライブ名を数値に変換するための変換テーブルの例である。
【図９】実施例３の検出対象パターンについての説明図である。
【図１０】実施例３の利用者ログデータについての説明図である。
【図１１】実施例３の属性値を数値に変換するための変換テーブルの例である。
【図１２】実施例３の検出対象パターンと利用者ログデータとを数値化した結果を示したものである。
【図１３】実施例３におけるスコア行列の計算例である。
【発明を実施するための形態】
【００１４】
以下、本発明を実施するための形態（以下、「本実施形態」という。）について、適宜図面を参照して詳細に説明する。本実施形態では、利用者の行動に関するログ情報のなかから、特定の行動パターンを検出する場合の例について説明するが、ログ情報はこれに限定されるものではなく、例えば、装置の動作に関するログ情報などであってもよい。
【００１５】
＜行動パターンの検出に望まれる要件＞
ログ情報のなかから、特定の行動パターンを検出するときに望まれる要件には、次のようなものがある。
（要件１）計算量が小さく高速処理が可能であること。特に、リアルタイムでのログ解析が必要な場合には、ログ情報の収集速度よりも高い処理速度が要求される。
（要件２）ログ情報には複数の属性値が含まれるため、多次元のログデータを扱えること。
（要件３）ノイズイベントに対してロバストであること。特定の行動パターンであっても、例えば、利用者の操作などは常に同一とは限らず、途中に別の操作が行われる場合があるため、途中にノイズイベントが含まれていても的確に検出できることが要求される。
（要件４）ログ情報の順序性を扱えること。特定の行動パターンは順序性を持った複数のイベントとして観測されるためである。
（要件５）イベントの繰返しに対してロバストであること。例えば、利用者は複数の対象について同一の操作を連続して行う場合があるため、同種イベントの繰返し回数に依存することなく的確に検出できることが要求される。
【００１６】
＜行動パターン検出装置の構成＞
図１は、本実施形態の行動パターン検出装置の構成を示したブロック図である。図１に示すように、行動パターン検出装置１は、検出対象パターン登録部１１と、ログデータ取得部１２と、数値変換部１３と、記憶部１４と、類似部分シーケンス検出部１５とを備えて構成される。これらの機能は、コンピュータに所定のプログラムを実行させることによって具現化することができる。
【００１７】
検出対象パターン登録部１１は、ログデータのなかから検出したい行動パターンを規定するイベントログシーケンスである検出対象パターンの入力を受け付け、検出対象パターンの登録を行う。ログデータ取得部１２は、例えば、利用者の行動に伴って時系列に生成されるログデータの入力を受け付け、それを取得する。ログデータは、例えばネットワーク接続された端末などからリアルタイムに取得してもよいし、記録媒体などに記録されたデータファイルからまとめて取得するようにしてもよい。
【００１８】
数値変換部１３は、検出対象パターン及びログデータを構成する各種属性値からなる文字列群などの非数値情報を、その非数値情報の種類毎に用意される所定の変換テーブルを参照したり、所定の変換手続きを実行することによって、それぞれ数値に変換する。このとき、数値変換部１３は、必要に応じて、検出対象パターンとは無関係なイベントログのデータを除去するフィルタリングを行うとともに、検出しようとする特定の検出対象パターンを規定している属性値だけを抽出して数値に変換する。
【００１９】
記憶部１４には、数値変換部１３によって数値化された検出しようとする特定の検出対象パターン１４１と、ログデータの部分シーケンスとの類似度の計算に使用する検出パラメータ１４２とが記憶される。
【００２０】
類似部分シーケンス検出部１５は、数値変換部１３によって数値化されたログデータのなかから、記憶部１４に記憶された数値化された検出対象パターン１４１と類似する類似部分シーケンスを、検出パラメータ１４２を利用して計算される類似度に基づいて検出する。検出された類似部分シーケンスのリストは、不図示のディスプレイ、プリンタ、外部記録媒体などに出力される。
【００２１】
＜行動パターン検出装置の動作＞
図２は、本実施形態の行動パターン検出装置における基本的なデータの流れを示した説明図である。図２に示すように、ログデータ取得部１２によって所定の形式で取得されるログデータを、イベントログｘ１、イベントログｘ２、・・・とし、検出対象パターン登録部１１によって所定の形式で登録される複数の検出対象パターン１、検出対象パターン２、・・・のなかから選択された１つのパターンを、検出イベントログｙ１、検出イベントログｙ２、・・・とする。
【００２２】
これらの検出イベントログは、取得されるログデータに含まれる各種属性値のなかから抽出される任意の数の属性値によって指定することができる。そして、各検出イベントログは、数値変換部１３によってそれぞれの属性値が数値に変換され、多次元の数値データのシーケンスとして記憶部１４に記憶される。
【００２３】
一方、取得されたログデータのなかには、検出対象の検出イベントログを構成する属性値を１つも含まないイベントのデータや、類似性の判断には使用されないデータが混在する場合があるため、そのような場合には、数値変換部１３は、それら不要なデータを除去するフィルタリング処理を行ったのち、数値化を行うことが好ましい。図２の例は、イベントログｘ１，ｘ３，ｘ７，ｘ８がフィルタリング処理によって除去され、残ったイベントログｘ２，ｘ４，ｘ５，ｘ６，ｘ９，・・・が数値化された場合を示している。
【００２４】
このように、検出対象パターンとログデータとを、ともに多次元の数値データのシーケンスに変換することで、前記の（要件２）〜（要件５）を満たす公知の動的マッチング技術の適用が可能となる。これにより、類似部分シーケンス検出部１５は、それら公知の動的マッチング技術を利用して、ログデータのなかから、検出対象パターンに類似する類似部分シーケンスを検出して、検出結果を出力する。なお、かかる公知の動的マッチング技術としては、高速処理が可能で前記の（要件１）をも満たすことができる類似部分シーケンス検出技術（特許文献２、非特許文献２参照）を適用することが好ましい。
【００２５】
図３は、本実施形態の行動パターン検出装置によって実行される行動パターン検出方法の手順を示したフローチャートである。まず始めに、検出対象パターン登録部１１は、ユーザからの指示にしたがって、予め登録された複数の検出対象パターンのなかから、検出したい検出対象パターンを１つ選択し、それを数値変換部１３が数値化して記憶部１４に数値化された検出対象パターン１４１として格納する（ステップＳ１）。
【００２６】
次に、ログ取得部１２は、ログデータを取得する（ステップＳ２）。ここでは、ログデータをまとめて取得するものとしているが、個々のログデータが発生する都度ネットワーク経由でリアルタイムに取得してもよく、その場合には、新たにデータを取得する度に、以下のステップＳ３〜Ｓ５を繰り返せばよい。
【００２７】
次に、数値変換部１３は、取得したログデータのなかから、選択した検出対象パターンとは無関係なデータを除去するフィルタリング処理を行ったのち、検出対象パターンを規定する属性値だけを抽出して数値化することにより、取得したログデータを多次元の数値データのシーケンスに変換する（ステップＳ３）。
【００２８】
次に、類似部分シーケンス検出部１５は、数値化されたログデータのなかから、ステップＳ１にて記憶部１４に格納した数値化された検出対象パターン１４１に類似する類似部分シーケンスを検出し（ステップＳ４）、最後に、検出された類似部分シーケンスのリストを出力して（ステップＳ５）、処理を終了する。
【００２９】
なお、前記では、１つの検出対象パターンだけを検出する場合を説明したが、同時に２つ以上の検出対象パターンを選択して検出するようにしてもよいし、登録済みのすべての検出対象パターンをすべて同時に検出するようにしてもよい。また、検出された類似部分シーケンスの最初のデータと最後のデータのそれぞれに該当するインデックス情報（図示しない）のみ、または日時情報のみを出力してもよい。
【００３０】
以上説明したように、本発明は、文字列等の非数値情報を含んで生成される複数の属性値から構成される時系列のログデータを、多次元の数値データに変換することによって、公知の数値データストリーム用の動的マッチング技術を適用可能とするものである。それにより、ログ情報のなかから、特定の行動パターンを検出するときに望まれる、前記の（要件１）〜（要件５）をすべて満たした行動パターン検出装置、行動パターン検出方法及び行動パターン検出プログラムを提供することができる。
【実施例１】
【００３１】
利用者の端末操作ログを分析して情報漏洩の可能性がある行動パターンを検出する場合の実施例について説明する。この実施例１では、行動パターンの検出に使用する属性は、ファイル操作の種類を識別するファイル操作イベントの１属性のみとし、図４（ａ）に示す「リネーム」→「コピー」→「削除」という３つのファイル操作のシーケンスを、図４（ｂ）に示した利用者ログデータのなかから検出するものとする。
【００３２】
図５は、数値変換部１３が保持しており、ファイル操作イベントを数値に変換するときに参照される変換テーブルの例を示したものである。単に、操作の一致／不一致を判定する場合には、図５のように、それぞれのイベントの種類に対して異なる数値を割り当てればよい。このような場合には、例えば、類似度を計算するときに、数値が一致すればスコア値に所定のプラスの値を加算し、数値が不一致であればスコア値から所定値を減算するようにすれば、数値の大小が類似度の計算結果に影響しないようにすることができる。
【００３３】
図６は、図４に示した検出対象パターンと利用者ログデータとを、図５の変換テーブルを用いて数値化した結果を示したものであり、図６（ａ）が数値化された検出対象パターンであり、図６（ｂ）が数値化された利用者ログデータである。また、（）内に記した数値により、検出対象パターンを構成するデータとの対応関係を表している。
【００３４】
このような、２つの数値データシーケンス（ここでは、検出対象パターンと利用者ログデータのそれぞれを数値化した情報であり、蓄積されたデータまたはデータストリームであってもよい。）に対して公知の動的マッチング技術を適用することによって、途中に検出対象パターンとは不一致となるノイズデータ（例えば、図６（ｂ）の「３」が２つ連続する部分）を含んでいても、図６（ｂ）に示したような類似部分シーケンスを的確に検出することができる。
【００３５】
さらに、ノイズデータの影響を減らして類似部分シーケンスの検出精度を向上させるためには、図６（ｃ）に示すように、同一の検出イベントログを複数繰り返した検出対象パターンを用いるとよい。これにより、２つのパターンの間の数値の一致回数が増える分だけ類似度のスコア値が大きくなるので、その分ノイズデータによるスコア値の減少の影響を減らし、ノイズデータに対するロバスト性を高めることができる。図６（ｃ）の例では、同一の検出イベントログを３回ずつ繰り返しているが、繰返し回数は検出精度と処理時間とを勘案して適切に設定することが望ましい。
【実施例２】
【００３６】
利用者の端末操作ログを分析して情報漏洩の可能性がある行動パターンを検出する場合の他の実施例について説明する。この実施例２では、行動パターンの検出に使用する属性は、ファイル操作の種類を識別するファイル操作イベントと、操作対象となったファイルのファイル名と、そのファイルが格納されるドライブ名との３属性とし、図７（ｂ）に示した利用者ログデータのなかから、図７（ａ）に示す「ファイルａの読込」→「ファイルａの書込」→「ファイルａのリネーム」→「外部メディアにコピー」という４つのファイル操作のシーケンスを検出するものとする。
【００３７】
図８は、数値変換部１３が保持しており、ドライブ名を数値に変換するときに参照される変換テーブルの例を示したものである。この例のように、ファイルの格納先が外部メディアであるか否かを判定する場合には、外部メディアであるＡ（ＦＤＤ）（Flexible Disk Drive）ドライブ、Ｅ（ＣＤ−ＲＷ）（Compact Disk-ReWritable）ドライブ、Ｆ（ＵＳＢ）（Universal Serial Bus）ドライブの３つに同じ数値または近い数値を割り当てることによって、外部メディア以外のＣ（ローカル）ドライブ、Ｄ（ローカル）ドライブ、Ｈ（ネットワーク）ドライブ、Ｉ（ネットワーク）ドライブとの識別性を高めることができる。
【００３８】
なお、図８の例は、外部メディアには、１〜３のいずれかの数値を、ローカルドライブには１１または１２の数値を、ネットワークドライブには２１以降の数値を割り当てることによって、それら３グループを識別する場合を示している。ファイルの格納先が外部メディアであることを検出するための検出対象パターンを設定する場合には、外部メディアに割り当てられるすべての数値の中央値または平均値を使用するとよい。例えば、図８の例では、外部メディアには、「１」，「２」，「３」の３つの数値が割り当てられるので、それらの中央値でもあり平均値でもある「２」を使用するのが好ましい。
【実施例３】
【００３９】
利用者のインターネット閲覧ログを分析して、情報漏洩につながる可能性があるＷｅｂメールによるファイル送信操作を検出する場合の実施例について説明する。この実施例３では、行動パターンの検出に使用する属性は、インターネット閲覧ログの種類を示すログ種別と、アクティブなウィンドウのウィンドウタイトルと、アプリケーション名と、閲覧先ページの識別情報であるＵＲＬ（Uniform Resource Locator）との４属性とし、例えば、図１０に示した利用者ログデータのなかから、図９に示すようなＷｅｂメールによって添付ファイルを送信するときの６シーケンスの検出イベントログのパターンを検出するものとする。
【００４０】
なお、Ｗｅｂメールでファイルを添付する場合には、その前にＷｅｂメールサービスを提供しているポータルページを開く操作と、そのなかからＷｅｂメールサービスを選択して起動する操作とに対応するイベントログも生成されるが、これら２つの操作は初回にのみ行われる操作であるため、検出の対象とはせずに、ファイルを添付する操作によって生成される検出イベントログのシーケンス（図９の（１）〜（４））と、メール送信操作によって生成される検出イベントログのシーケンス（図９の（５）〜（６））とを検出対象とする。
【００４１】
図１１は、数値変換部１３が保持しており、検出対象パターンと利用者ログデータとに含まれる各属性値を数値に変換するときに参照される変換テーブルの例を示したものである。図１１（ａ）〜（ｄ）は、順にログ種別、ウィンドウタイトル、アプリケーション名、ＵＲＬに対応する変換テーブルである。ウィンドウタイトル及びＵＲＬを数値に変換するときには、それぞれ図１１（ｂ）及び図１１（ｄ）に示されている文字列が含まれる場合に対応する数値に変換し、それらの文字列が含まれない場合には、数値０に変換する。なお、図内の「＋」記号は、２つの文字列の両方を含むことを表している。
【００４２】
図１２は、図９に示した検出対象パターンと図１０に示した利用者ログデータとを、図１１（ａ）〜（ｄ）の各変換テーブルを用いて数値化した結果を示したものであり、図１２（ａ）が数値化された検出対象パターンであり、図１２（ｂ）が数値化された利用者ログデータである。また、（）内に記した数値により、検出対象パターンを構成する検出イベントログとの対応関係を表している。
【００４３】
次に、このような、２つの数値データシーケンスのなかから類似部分シーケンスのペアを検出するための、動的計画法に基づく単一のスコア行列を用いた動的マッチング処理の例について説明する。２つの数値データシーケンスのうち、利用者ログデータをＸ＝（ｘ１，ｘ２，・・・，ｘｎ）、検出対象パターンをＹ＝（ｙ１，ｙ２，・・・，ｙｍ）としたとき、Ｘの部分シーケンスＸ［ｉｓ：ｉｅ］とＹの部分シーケンスＹ［ｊｓ：ｊｅ］とからなる部分シーケンスペアの類似度を表す類似度スコアＳ（Ｘ［ｉｓ：ｉｅ］，Ｙ［ｊｓ：ｊｅ］）を、以下の式（１）〜式（４）によって計算して、スコア行列を生成する。ここで、ｉｓ及びｊｓは、部分シーケンスの開始点（開始位置）を、ｉｅ及びｊｅは部分シーケンスの終了点（終了位置）を示すインデックスである。
【００４４】
Ｓ（Ｘ［ｉｓ：ｉｅ］，Ｙ［ｊｓ：ｊｅ］）＝ｓ（ｉｅ，ｊｅ）          （式１）
ｓ（ｉ，ｊ）＝ｍａｘ｛０，
１／２ε＋ｓ（ｉ，ｊ−１）−‖ｘｉ−ｙｊ‖，
１／２ε＋ｓ（ｉ−１，ｊ）−‖ｘｉ−ｙｊ‖，
ε＋ｓ（ｉ−１，ｊ−１）−‖ｘｉ−ｙｊ‖｝    （式２）
‖ｘｉ−ｙｊ‖＝０（ｘｉ＝ｙｊのとき）                              （式３ａ）
‖ｘｉ−ｙｊ‖＝１（ｘｉ≠ｙｊのとき）                              （式３ｂ）
ｓ（０，０）＝ｓ（ｉ，０）＝ｓ（０，ｊ）＝０                        （式４）
【００４５】
ここで、εは、データシーケンスの特性に応じて予め設定される検出パラメータの１つであり、以下の計算においては、ε＝０．８とする。また、検出する部分シーケンスペアの最小長さのパラメータｌについては、ｌ＝４とする。この２つのパラメータにより、検出する部分シーケンスペアの最小スコア値が決定され、この例では、ε×ｌ＝３．２以上のスコア値を持つ部分シーケンスペアが検出される。また、これらのパラメータは、シーケンスデータの特性に応じてユーザが任意に設定可能である。
【００４６】
具体的な処理手順としては、まず始めに、利用者ログデータＸの先頭データｘ１と検出対象パターンＹの先頭データｙ１との類似度スコア値（以下、「スコア値」とも略記。）であるｓ（１，１）を計算する。次に、ｘ１と、検出対象パターンＹのデータを順番に１つずつ付加した部分シーケンスとの類似度であるｓ（１，２）〜ｓ（１，ｍ）を計算する。続いて、利用者ログデータＸのデータを１つ付加した部分シーケンスＸ［１：２］について同様にｓ（２，１）〜ｓ（２，ｍ）を計算し、以後順番に利用者ログデータＸのデータを１つずつ付加していくことによって、最終的にスコア行列のすべてのセルのスコア値を求めることができる。このように、動的計画法に基づく単一のスコア行列に記憶される既知の部分シーケンスペアの類似度スコア値を用いて、次のログデータを付加したときの部分シーケンスペアの類似度スコア値を算出するので、ログデータがリアルタイムに取得される場合でも、類似度スコア値を効率的に算出することができる。
【００４７】
なお、この例では、スコア値を計算するための距離‖ｘｉ−ｙｊ‖として、一致したときに０、不一致のときに１となるエディットディスタンスを用いているが、これに限らず、例えば、ユークリッド距離やマンハッタン距離など任意のものを利用することができる。
【００４８】
（式１）〜（式４）によって生成されるスコア行列の各セルには、任意の開始点からそのセルに至るすべての部分シーケンスペアのなかで、最大のスコア値を持つ部分シーケンスペアのスコア値が順次計算されて保持される。また、各セルには、そのスコア値を持つ部分シーケンスペアの開始点（開始位置）の座標が保持され、（式２）によって次のセルのスコア値を計算するときに選択された元のセルが保持していた開始点の座標が引き継がれる。ただし、計算したスコア値が０となったときには、新たな部分シーケンスペアの開始点として自身のセルの座標を保持する。
【００４９】
これにより、各セルには、そのセルに至る（そのセルを終了点とする）すべての部分シーケンスペアのなかで、最大のスコア値を有して最も類似度が高い部分シーケンスペアのスコア値とともに、その部分シーケンスペアの開始点の座標が保持されることになる。
【００５０】
図１３は、図１２（ａ）と図１２（ｂ）とに示した２つの数値データシーケンス（ｎ＝１４，ｍ＝６）について生成されたスコア行列の計算例を示したものである。行列の各セル内には、上側にそのセルに至る部分シーケンスペアの最大スコア値が、下側にその部分シーケンスペアの開始点の座標が記されている。このスコア行列から、最小スコア値が３．２以上である部分シーケンスペア（図１３の網かけ部）が抽出され、図１２（ｂ）に示した類似部分シーケンスを検出することができる。
【００５１】
このように、途中に検出対象パターンとは不一致となるノイズデータ（図１２（ｂ）の（１）と（２）との間の２つのデータや、（４）と（５）との間のデータ）を含んでいても、所望の類似部分シーケンスを的確に検出することができる。なお、検出精度をさらに高めたい場合には、図６（ｃ）にて説明したように、同一の検出イベントログを複数繰り返した検出対象パターンを用いるとよい。
【００５２】
以上にて、本実施形態及び実施例の説明を終えるが、これらに限らず、本発明の趣旨を逸脱しない範囲内で各種の変更が可能である。また、検出する行動パターンは、時系列のログデータが取得できるものであれば何でもよく、例えば、各種センサによって利用者の位置や動作を監視するシステムや、それをさらに勤怠管理システムと連携させたシステムなどにも適用することができる。
【符号の説明】
【００５３】
１    行動パターン検出装置
１１  検出対象パターン登録部
１２  ログデータ取得部
１３  数値変換部
１４  記憶部
１４１  数値化された検出対象パターン
１４２  検出パラメータ
１５  類似部分シーケンス検出部
【図１】
2011138422.tif 000003
【図２】
2011138422.tif 000004
【図３】
2011138422.tif 000005
【図４】
2011138422.tif 000006
【図５】
2011138422.tif 000007
【図６】
2011138422.tif 000008
【図７】
2011138422.tif 000009
【図８】
2011138422.tif 000010
【図９】
2011138422.tif 000011
【図１０】
2011138422.tif 000012
【図１１】
2011138422.tif 000013
【図１２】
2011138422.tif 000014
【図１３】
2011138422.tif 000015