(57)【要約】【課題】効率良く所定のパターンを抽出すること。【解決手段】抽出プログラム３３０ａは、コンピュータ３００に、イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、イベントの組合せに基づいて、次の処理を実行させる。すなわち、抽出プログラム３３０ａは、コンピュータ３００に、組合せに含まれる各イベントが第２のパターンに登場する数が閾値以下となる場合に、第２のパターンを生成する。抽出プログラム３３０ａは、コンピュータ３００に、複数のイベントを含むデータに基づいて、生成された１以上の第２のパターンがデータに登場する頻度を算出する処理を実行させる。抽出プログラム３３０ａは、コンピュータ３００に、頻度が所定の条件を満たす第２のパターンを抽出する処理を実行させる。抽出プログラム３３０ａは、コンピュータ３００に、抽出された第２のパターンに対して新たなイベントを追加する処理を実行させる。【選択図】図２９
2014099115.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下となる場合に、前記第２のパターンを生成し、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、生成された１以上の前記第２のパターンが前記データに登場する頻度を算出し、
前記頻度が所定の条件を満たす第２のパターンを抽出し、
抽出された第２のパターンに対して新たなイベントを追加する
各処理を実行させることを特徴とする抽出プログラム。
【請求項２】
前記データは、複数のイベントと各イベントの出現時刻とを対応付けた複数のデータを含むイベントデータであり、
前記第２のパターンを生成する処理は、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が所定のウィンドウ幅に基づいて定まる閾値以下となる場合に、前記第２のパターンを生成し、
前記頻度を算出する処理は、前記所定のウィンドウ幅内に含まれる前記出現時刻に対応付けられたイベントに基づいて、前記頻度を算出する
ことを特徴とする請求項１に記載の抽出プログラム。
【請求項３】
前記コンピュータに、更に、前記第２のパターンを生成する際に前記第１のパターンに追加されるイベントが該第１のパターンのイベントの先頭又は末尾に追加されるイベントである場合には、前記第１の閾値から、該第１のパターンに該追加されるイベント以外の該第１のパターンのイベントのうち前記組合せに含まれるイベントの数を減算した値を前記閾値とすることにより該閾値を更新する処理を実行させ、
前記第２のパターンを生成する処理は、前記閾値が更新された場合には、前記第１のパターンのイベントの前記先頭又は前記末尾にイベントを追加して前記第２のパターンを生成する際に、前記記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが、前記追加されるイベントに登場する数が前記更新された閾値以下となる場合に、前記第２のパターンを生成する、
ことを特徴とする請求項２に記載の抽出プログラム。
【請求項４】
前記コンピュータに、更に、前記頻度が前記所定の条件を満たさない第２のパターンから、該第２のパターンに最後に追加されたイベントを削除することで、前記第１のパターンを生成する処理を実行させ、
前記閾値を更新する処理は、前記第１のパターンが生成された際に削除された前記イベントが先頭又は末尾のイベントである場合には、前記更新された閾値に、前記第１のパターンのイベントのうち前記組合せに含まれるイベントの数を加算した値を前記閾値とすることにより該閾値を新たに更新し、
前記第２のパターンを生成する処理は、前記第１のパターンにイベントを追加して前記第２のパターンを生成する際に、前記組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が新たに更新された前記閾値以下となる場合に、前記第２のパターンを生成する
ことを特徴とする請求項３に記載の抽出プログラム。  
【請求項５】
イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下となる場合に、前記第２のパターンを生成するとともに、抽出された前記第２のパターンに対して新たなイベントを追加する生成部と、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、生成された１以上の前記第２のパターンが前記データに登場する頻度を算出し、前記頻度が所定の条件を満たす第２のパターンを抽出する抽出部と、
を有することを特徴とする抽出装置。
【請求項６】
コンピュータが、
イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下となる場合に、前記第２のパターンを生成し、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、生成された１以上の前記第２のパターンが前記データに登場する頻度を算出し、
前記頻度が所定の条件を満たす第２のパターンを抽出し、
抽出された第２のパターンに対して新たなイベントを追加する
各処理を実行することを特徴とする抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、抽出プログラム、抽出装置及び抽出方法に関する。
【背景技術】
【０００２】
イベントデータが示す実際に出現したイベントのパターンに含まれるパターンを抽出する抽出装置がある。イベントデータの一例としては、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すイベントデータが挙げられる。イベントデータが、「アンケートの回答者は男性である」というイベントＡ、「アンケートの回答者は、年齢が３０代である」というイベントＢ及び「アンケートの質問１に対する回答内容は、「Ａ１」である」というイベントＣを含む場合について説明する。この場合には、抽出装置は、次のようなパターンを抽出する。例えば、抽出装置は、イベントＡのパターン、イベントＡ及びＢのパターン、イベントＡ、Ｂ及びＣのパターン、イベントＢのパターン、イベントＢ及びＣのパターン、イベントＣのパターンを抽出する。これらのパターンが抽出装置により抽出された場合、抽出装置を使用するユーザは、男性で年齢が３０代の回答者は、質問１に対して「Ａ１」という内容を回答したということを把握することができる。
【０００３】
また、上記の抽出装置の一例としては、次のような抽出装置がある。例えば、列挙木における親から子を生成しつつ、生成した子が、イベントデータが示す実際に出現したイベントのパターンに出現するか否かを判定することで、イベントデータが示す実際に出現したイベントのパターンに含まれるパターンを抽出する抽出装置がある。かかる抽出装置は、親のパターンにイベントを追加することで、子のパターンを生成する。そして、抽出装置は、新たに生成された子のパターンを親のパターンとして、再び子のパターンを生成する。このようにして、抽出装置は、所定の条件を満たすまで、繰り返し子のパターンを生成する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平４−１２５７３４号公報
【特許文献２】特開２００９−１７３４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の抽出装置では、効率良くパターンを抽出することができないという問題がある。これを説明すると、かかる抽出装置は、抽出されるパターンとしてはあり得ないパターンを生成する。例えば、親のパターンに追加するイベントとして、上記のイベントＡ、Ｂ及びＣに加え、次のようなイベントがある場合について説明する。すなわち、「アンケートの回答者は女性である」というイベントＤ、「アンケートの回答者は、年齢が２０代である」というイベントＥ及び「アンケートの質問１に対する回答内容は、「Ａ２」である」というイベントＦがある場合について説明する。この場合、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すイベントデータが示すイベントのパターンに、イベントＡとイベントＤとが出現することはあり得ない。回答者の性別は、男性か女性のいずれかであるからである。また、かかるイベントのパターンに、イベントＢとイベントＥとが出現することはあり得ない。回答者の年齢の世代が、２０代及び３０代の両世代であることはあり得ないからである。また、アンケートの質問１に対する回答の形式が１つの回答内容を回答する形式である場合には、かかるイベントのパターンに、イベントＣとイベントＦとが出現することはあり得ない。
【０００６】
しかしながら、上記の抽出装置は、親のパターンがイベントＡを有するパターンであっても、かかる親のパターンにイベントＤを追加してイベントＡ及びイベントＤを有する子のパターンを生成する。同様に、上記の抽出装置は、親のパターンがイベントＢを有するパターンであっても、かかる親のパターンにイベントＥを追加してイベントＢ及びイベントＥを有する子のパターンを生成する。また、上記の抽出装置は、親のパターンがイベントＣを有するパターンであっても、かかる親のパターンにイベントＦを追加してイベントＣ及びイベントＦを有する子のパターンを生成する。すなわち、上記の抽出装置は、イベントデータが示すイベントに出現しないようなイベントの組み合わせ、すなわち、互いに排他的なイベントを含むパターンを生成する。そして、上記の抽出装置は、イベントデータが示すイベントのパターンに出現しないイベントの組み合わせを含むパターンであるにもかかわらず、かかるパターンが、イベントデータが示すイベントのパターンに出現するか否かを判定するような無駄な処理を行う。そのため、上記の抽出装置は、効率良くパターンを抽出することができないという問題がある。
【０００７】
１つの側面では、効率良くパターンを抽出することができる抽出プログラム、抽出装置及び抽出方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する抽出プログラムは、一つの態様において、コンピュータに、イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、次の処理を実行させる。すなわち、抽出プログラムは、コンピュータに、組合せに含まれる各イベントが第２のパターンに登場する数が閾値以下となる場合に、第２のパターンを生成する処理を実行させる。そして、抽出プログラムは、コンピュータに、記憶部に記憶された複数のイベントを含むデータに基づいて、生成された１以上の第２のパターンがデータに登場する頻度を算出する処理を実行させる。続いて、抽出プログラムは、コンピュータに、頻度が所定の条件を満たす第２のパターンを抽出する処理を実行させる。その後、抽出プログラムは、コンピュータに、抽出された第２のパターンに対して新たなイベントを追加する処理を実行させる。
【発明の効果】
【０００９】
抽出プログラム、抽出装置及び抽出方法の一つの態様によれば、効率良くパターンを抽出することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。
【図２】図２は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図３】図３は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図４】図４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図５】図５は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図６】図６は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図８】図８は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図９】図９は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１０】図１０は、実施例１に係る抽出処理の手順を示すフローチャートである。
【図１１】図１１は、実施例２に係る抽出装置の機能構成の一例を示す図である。
【図１２】図１２は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１３】図１３は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１４】図１４は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１５】図１５は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１６】図１６は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１７】図１７は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１８】図１８は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１９】図１９は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２０】図２０は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２１】図２１は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２２】図２２は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２３】図２３は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２４】図２４は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２５】図２５は、実施例２に係る抽出処理の手順を示すフローチャートである。
【図２６】図２６は、実施例３に係る抽出装置の機能構成の一例を示す図である。
【図２７】図２７は、実施例３に係る抽出装置が実行する処理の一例を説明するための図である。
【図２８】図２８は、実施例３に係る抽出処理の手順を示すフローチャートである。
【図２９】図２９は、抽出プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する抽出プログラム、抽出装置および抽出方法の各実施例を図面に基づいて詳細に説明する。なお、各実施例は開示の技術を限定するものではない。
【実施例１】
【００１２】
［抽出装置の構成］
実施例１に係る抽出装置について説明する。図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。図１に示すように、抽出装置１０は、入力部１１と、表示部１２と、記憶部１３と、制御部１４とを有する。
【００１３】
入力部１１は、制御部１４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、後述の抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、所定のサーバから後述のイベントデータ１３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部１４に、後述のイベント表１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００１４】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部１４ｆにより抽出されたパターンを後述の表示制御部１４ｇの制御により表示する。
【００１５】
記憶部１３は、制御部１４で実行される各種プログラムを記憶する。また、記憶部１３には、後述の取得部１４ａにより、イベントデータ１３ａ及びイベント表１３ｂが格納される。
【００１６】
イベントデータ１３ａについて説明する。イベントデータ１３ａは、実際に出現したイベントのパターンを示すデータである。以下、イベントデータ１３ａが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示す場合について説明するが、イベントデータ１３ａはこれに限られず、様々なイベントを含むデータを採用することができる。
【００１７】
イベントデータ１３ａが示すイベントのパターンには、識別子Ａが示す「アンケートの回答者は男性である」というイベント、識別子Ｂが示す「アンケートの回答者は女性である」というイベントが含まれる。また、イベントデータ１３ａが示すイベントのパターンには、識別子Ｃが示す「アンケートの回答者の情報及び回答内容が無回答である」というイベント、識別子Ｅが示す「アンケートの回答者は、年齢が３０代である」というイベントが含まれる。なお、イベントデータ１３ａが示すイベントのパターンには、後述の識別子Ｄが示す「アンケートの回答者は、年齢が２０代である」というイベントが含まれない。以下の説明では、識別子Ａが示すイベントを「イベントＡ」と表記する。また、同様に、識別子Ｂが示すイベントを「イベントＢ」と表記し、識別子Ｃが示すイベントを「イベントＣ」と表記し、識別子Ｄが示すイベントを「イベントＤ」と表記し、識別子Ｅが示すイベントを「イベントＥ」と表記する。また、イベントデータ１３ａが示すイベントのパターンには、イベントＡの次にイベントＢが出現するパターン、イベントＡの次にイベントＢ、イベントＢの次にイベントＣが出現するパターン、イベントＡの次にイベントＥが出現するパターンが含まれる。また、イベントデータ１３ａが示すイベントのパターンには、イベントＢの次にイベントＣが出現するパターン、イベントＢの次にイベントＥが出現するパターンが含まれる。
【００１８】
イベント表１３ｂについて説明する。イベント表１３ｂは、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組合せが登録されたものである。イベント表１３ｂは、ユーザによって生成される。図２は、イベント表の一例を示す図である。図２の例は、後述の初期化部１４ｂによって初期化されたイベント表１３ｂを示す。図２の例に示すイベント表１３ｂは、列方向に、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組合せが登録された場合を示す。図２の例のイベント表１３ｂでは、列方向に、イベントＡ、イベントＢ及びイベントＣの組合せが登録されている。また、図２の例のイベント表１３ｂでは、列方向に、「アンケートの回答者は、年齢が２０代である」というイベントＤ、イベントＥ及びイベントＣが登録されている。すなわち、イベント表１３ｂは、イベントＡ及びイベントＢの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。また、イベント表１３ｂは、イベントＡ及びイベントＣの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。また、イベント表１３ｂは、イベントＡ、イベントＢ及びイベントＣの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。また、イベント表１３ｂは、イベントＤ及びイベントＥの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。また、イベント表１３ｂは、イベントＤ及びイベントＣの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。また、イベント表１３ｂは、イベントＤ、イベントＥ及びイベントＣの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないことを示す。
【００１９】
また、イベント表１３ｂには、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組合せのそれぞれに対応するカウンタ２０ａ、２０ｂが設けられている。かかるカウンタ２０ａ、２０ｂに登録される数値の増減は、後述のカウンタ制御部１４ｅによって制御される。
【００２０】
記憶部１３は、例えば、フラッシュメモリなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部１３は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（Random  Access  Memory)、ＲＯＭ（Read  Only  Memory)であってもよい。
【００２１】
制御部１４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。図１に示すように、制御部１４は、取得部１４ａと、初期化部１４ｂと、生成部１４ｃと、バックトラック処理部１４ｄと、カウンタ制御部１４ｅと、抽出部１４ｆと、表示制御部１４ｇとを有する。
【００２２】
取得部１４ａは、各種の情報を取得する。例えば、取得部１４ａは、所定のサーバからイベントデータ１３ａを取得する指示が入力部１１から入力された場合には、かかる指示に基づいて、次のような処理を行う。すなわち、取得部１４ａは、図示しないネットワークを介して図示しない所定のサーバにアクセスし、所定のサーバからイベントデータ１３ａを取得する。そして、取得部１４ａは、取得したイベントデータ１３ａを記憶部１３に格納する。また、取得部１４ａは、イベント表１３ｂが入力部１１から入力された場合には、入力されたイベント表１３ｂを取得し、取得したイベント表１３ｂを記憶部１３に格納する。
【００２３】
また、取得部１４ａは、抽出処理を実行する指示が入力部１１から入力された場合には、記憶部１３からイベントデータ１３ａ及びイベント表１３ｂを取得する。
【００２４】
初期化部１４ｂは、各種の初期化を行う。例えば、初期化部１４ｂは、取得部１４ａによりイベントデータ１３ａ及びイベント表１３ｂが取得された場合には、空のパターン（空パターン）を列挙木における最初の親、すなわち、根に設定する。図３は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。図３の例に示すように、初期化部１４ｂは、根のパターン３０に空パターン４０を設定する。
【００２５】
そして、初期化部１４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う。続いて、初期化部１４ｂは、後述する生成部１４ｃが実行する、選択したイベントの候補ｅを含む列のカウンタが全て閾値未満であるか否かを判定する処理において用いられる閾値の値を「１」に設定する。
【００２６】
生成部１４ｃは、各種のパターンを生成する。生成部１４ｃの一態様について説明する。生成部１４ｃは、まず、根のパターン３０を選択する。
【００２７】
次に、生成部１４ｃは、選択したパターンに追加するイベントの候補があるか否かを判定する。この場合、生成部１４ｃは、所定のイベントＡ〜Ｅのうち、選択したパターンとの組合せにおいて未選択であるイベントがある場合には、選択したパターンに追加するイベントの候補があると判定する。なお、本実施例では、同一のイベントが同一のパターンに含まれないものとする。一方、生成部１４ｃは、所定のイベントＡ〜Ｅのうち、選択したパターンとの組合せにおいて未選択となるイベントがない場合には、選択したパターンに追加するイベントの候補がないと判定する。例えば、図３の例に示す場合では、根のパターン３０が選択されたときには、所定のイベントＡ〜Ｅのうち、パターン３０との組合せにおいて未選択であるイベントＡ〜Ｅがある。このため、生成部１４ｃは、選択したパターン３０に追加するイベントＡ〜Ｅがあると判定する。なお、生成部１４ｃは、表示制御部１４ｇによりパターンが表示されるように表示部１２の表示が制御された場合にも、同様に、選択したパターンに追加するイベントの候補があるか否かを判定する。また、生成部１４ｃは、カウンタ制御部１４ｅによりイベント表１３ｂの列のカウンタの値が１つデクリメントされた場合にも、同様に、選択したパターンに追加するイベントの候補があるか否かを判定する。
【００２８】
選択したパターンに追加するイベントの候補がある場合には、生成部１４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択する。例えば、図３の例において、選択したパターン３０に追加するイベントＡ〜Ｅがある場合には、生成部１４ｃは、イベントＡ〜Ｅのうち、識別子がアルファベット順で小さいイベントＡを１つ選択する。次に、生成部１４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満であるか否かを判定する。例えば、図３の例に示す場合において、イベントＡが選択された場合には、生成部１４ｃは、図２の例に示すイベント表１３ｂにおいて、選択したイベントＡを含む列のカウンタ２０ａの値「０」が、閾値「１」未満であると判定する。
【００２９】
選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満でない場合には、生成部１４ｃは、上述した、選択したパターンに追加するイベントの候補があるか否かを判定する処理を再び行い、かかる処理以降の処理を再び行う。一方、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満である場合には、生成部１４ｃは、選択したパターンに、選択したイベントの候補ｅを追加して、パターンを生成する。そして、生成部１４ｃは、生成したパターンを選択する。図４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。例えば、生成部１４ｃは、図４の例に示すように、選択したパターン３０に、選択したイベントの候補であるイベントＡを追加して、パターン３１を生成する。そして、生成部１４ｃは、生成したパターン３１を選択する。なお、パターンが生成された後に、後述のカウンタ制御部１４ｅにより、イベントの候補ｅを含む列のカウンタの値が１つインクリメントされる。
【００３０】
このように、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満である場合に、選択したパターンに、選択したイベントの候補ｅが追加されて、パターンが生成される。一方、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満でない場合には、パターンが生成されない。これは、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満でない場合には、選択したパターンに含まれるイベントと選択したイベントの候補ｅとの組合せが、次のような組合せだからである。すなわち、選択したパターンに含まれるイベントと選択したイベントの候補ｅとの組合せが、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組合せであるからである。このように、本実施例によれば、イベントデータ１３ａが示すイベントに出現しないようなイベントの組み合わせ、すなわち、互いに排他的なイベントを含むパターンが生成されない。そのため、本実施例では、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例は、効率良くパターンを抽出することができる。なお、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満でない場合に、パターンが生成されないことを、「枝刈り」と称する場合もある。
【００３１】
また、選択したパターンに追加するイベントの候補があるか否かを判定した結果、追加するイベントの候補がない場合には、生成部１４ｃは、枝刈りによって生成されなくなったパターンを除いた全てのパターンが生成されたか否かを判定する。枝刈りによって生成されなくなったパターンを除いた全てのパターンが生成された場合には処理が終了される。
【００３２】
バックトラック処理部１４ｄは、バックトラックを行う。例えば、抽出部１４ｆにより頻出でないと判別された場合に、バックトラック処理部１４ｄは、生成部１４ｃにより生成されたパターンから最後に追加されたイベントｅを削除したパターンを生成する。そして、バックトラック処理部１４ｄは、生成したパターンを選択する。また、バックトラック処理部１４ｄは、生成部１４ｃにより、枝刈りによって生成されなくなったパターンを除いた全てのパターンが生成されていないと判定された場合にも、同様の処理を行う。すなわち、バックトラック処理部１４ｄは、選択されたパターンから最後に追加されたイベントｅを削除したパターンを生成し、生成したパターンを選択する。
【００３３】
カウンタ制御部１４ｅは、生成部１４ｃによりパターンが生成された場合に、このパターンが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする。図５は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。例えば、生成部１４ｃにより図４に示すパターン３１が生成された場合には、カウンタ制御部１４ｅは、図５に示すように、パターン３１が生成された際に追加されたイベントＡを含むイベント表１３ｂの列のカウンタ２０ａの値を１つインクリメントする。
【００３４】
また、カウンタ制御部１４ｅは、バックトラック処理部１４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントする。
【００３５】
抽出部１４ｆは、カウンタ制御部１４ｅによりイベントの候補ｅを含む列のカウンタの値が１つインクリメントされた場合には、生成されたパターンの頻度を算出する。例えば、抽出部１４ｆは、生成されたパターンが、イベントデータ１３ａが示すイベントのパターンに出現する場合には「１」、出現しない場合には「０」の値を頻度として算出する。そして、抽出部１４ｆは、算出した頻度が「１」であるか否かを判定することにより、生成されたパターンが頻出であるか否かを判別する。そして、算出した頻度が「１」である場合には、抽出部１４ｆは、生成されたパターンが、頻出であると判別する。一方、算出した頻度が「１」でない場合、すなわち「０」である場合には、抽出部１４ｆは、生成されたパターンが、頻出でないと判別する。例えば、生成されたパターンが、図４の例に示す、イベントＡを含むパターン３１である場合には、上述したように、イベントＡは、イベントデータ１３ａが示すイベントのパターンに出現するため、抽出部１４ｆは、「１」の値を頻度として算出する。そして、抽出部１４ｆは、算出した頻度が「１」であるため、生成されたパターン３１が頻出であると判別する。
【００３６】
そして、抽出部１４ｆは、頻出であると判別されたパターンを表示するパターンとして抽出する。例えば、頻出であると判別された図４に示すパターン３１を表示するパターンとして抽出する。
【００３７】
表示制御部１４ｇは、各種の情報を表示するように表示部１２の表示を制御する。例えば、表示制御部１４ｇは、抽出部１４ｆにより抽出されたパターン、例えば、パターン３１を表示するように表示部１２の表示を制御する。
【００３８】
次に、抽出装置１０が実行する処理の具体例について、先の図４及び図５、並びに、図６〜図９を参照して説明する。図６〜図９は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【００３９】
例えば、パターン３１が表示部１２に表示された後に、抽出装置１０は、図４に示す場合において、選択したパターン３１に追加するイベントの候補であるイベントＢを選択する。そして、抽出装置１０は、選択したイベントＢを含むイベント表１３ｂの列に対応するカウンタ２０ａの値「１」が閾値「１」未満でないため、選択したパターン３１に追加するイベントの候補であるイベントＣを選択する。
【００４０】
そして、抽出装置１０は、選択したイベントＣを含むイベント表１３ｂの列に対応するカウンタ２０ａの値「１」が閾値「１」未満でないため、選択したパターン３１に追加するイベントの候補であるイベントＤを選択する。続いて、抽出装置１０は、選択したイベントＤを含むイベント表１３ｂの列に対応するカウンタ２０ｂの値が、図５に示すように「０」であり、閾値「１」未満であるため、次のような処理を行う。すなわち、抽出装置１０は、図６に示すように、選択したパターン３１に、イベントの候補であるイベントＤを追加してパターン３２を生成する。そして、抽出装置１０は、図７に示すように、イベントＤを列に含むイベント表１３ｂのカウンタ２０ｂの値を１つインクリメントする。
【００４１】
そして、抽出装置１０は、イベントＤを含むパターン３２が頻出でないため、図８に示すように、パターン３２からイベントＤを削除したパターン３１を生成し、図５に示すように、カウンタ２０ｂの値を１つデクリメントする。そして、抽出装置１０は、パターン３１に追加するイベントの候補であるイベントＥを選択する。そして、抽出装置１０は、選択したイベントＥを含むイベント表１３ｂの列に対応するカウンタ２０ｂの値「０」が、図５に示すように「０」であり、閾値「１」未満であるため、図９に示すように、パターン３１にイベントＥを追加してパターン３３を生成する。パターン３３に追加できるイベントはないので、抽出装置１０は、パターン３３からバックトラックをして処理を続ける。なお、図９に示す時点では、抽出装置１０は、イベントＡを含むパターン３１、並びに、イベントＡ及びＥを含むパターン３３を抽出している。
【００４２】
制御部１４は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。  
【００４３】
［処理の流れ］
次に、本実施例に係る抽出装置１０の処理の流れを説明する。図１０は、実施例１に係る抽出処理の手順を示すフローチャートである。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、制御部１４により実行される。
【００４４】
図１０に示すように、取得部１４ａは、記憶部１３からイベントデータ１３ａを取得する（Ｓ１０１）。そして、取得部１４ａは、記憶部１３からイベント表１３ｂを取得する（Ｓ１０２）。
【００４５】
続いて、初期化部１４ｂは、空パターンを列挙木における最初の親、すなわち、根に設定する（Ｓ１０３）。そして、初期化部１４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う（Ｓ１０４）。続いて、初期化部１４ｂは、Ｓ１０９での処理に用いられる閾値の値を「１」に設定する（Ｓ１０５）。
【００４６】
生成部１４ｃは、根のパターン３０を選択する（Ｓ１０６）。次に、生成部１４ｃは、選択したパターンに追加するイベントの候補があるか否かを判定する（Ｓ１０７）。
【００４７】
選択したパターンに追加するイベントの候補がある場合（Ｓ１０７肯定）には、生成部１４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択する（Ｓ１０８）。次に、生成部１４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満であるか否かを判定する（Ｓ１０９）。
【００４８】
選択したイベントの候補ｅを含む列のカウンタの少なくとも１つの値が閾値「１」以上である場合（Ｓ１０９否定）には、生成部１４ｃは、Ｓ１０７に戻る。一方、選択したイベントの候補ｅを含む列のカウンタが全て閾値「１」未満である場合（Ｓ１０９肯定）には、生成部１４ｃは、選択したパターンに、選択したイベントの候補ｅを追加して、パターンを生成する（Ｓ１１０）。そして、生成部１４ｃは、生成したパターンを選択する（Ｓ１１１）。
【００４９】
カウンタ制御部１４ｅは、選択されたパターンが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする（Ｓ１１２）。そして、抽出部１４ｆは、生成されたパターンの頻度を算出する（Ｓ１１３）。そして、抽出部１４ｆは、算出した頻度が「１」であるか否かを判定することにより、生成されたパターンが頻出であるか否かを判別する（Ｓ１１４）。算出した頻度が「１」である場合（Ｓ１１４肯定）には、抽出部１４ｆは、頻出であると判別されたパターンを表示するパターンとして抽出する（Ｓ１１５）。続いて、表示制御部１４ｇは、抽出部１４ｆにより抽出されたパターンを表示するように表示部１２の表示を制御し（Ｓ１１６）、Ｓ１０７に戻る。
【００５０】
一方、算出した頻度が「１」でない場合（Ｓ１１４否定）には、バックトラック処理部１４ｄは、生成部１４ｃにより生成されたパターンから最後に追加されたイベントｅを削除したパターンを生成する（Ｓ１１７）。そして、バックトラック処理部１４ｄは、生成したパターンを選択する（Ｓ１１８）。その後、カウンタ制御部１４ｅは、バックトラック処理部１４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントし（Ｓ１１９）、Ｓ１０７に戻る。
【００５１】
また、追加するイベントの候補がない場合（Ｓ１０７否定）には、生成部１４ｃは、枝刈りによって生成されなくなったパターンを除いた全てのパターンが生成されたか否かを判定する（Ｓ１２０）。枝刈りによって生成されなくなったパターンを除いた全てのパターンが生成された場合（Ｓ１２０肯定）には処理を終了する。枝刈りによって生成されなくなったパターンを除いた全てのパターンのうち、未生成のパターンがある場合（Ｓ１２０否定）には、Ｓ１１７へ進む。
【００５２】
上述してきたように、本実施例に係る抽出装置１０は、イベントを含むパターンにイベントを追加して新たなパターンを生成する際に、記憶部１３に記憶された互いに排他的であるイベントの組合せを示すイベント表１３ｂに基づいて、次の処理を行う。すなわち、抽出装置１０は、かかる組合せに含まれる各イベントが新たなパターンに登場する数が閾値「１」以下となる場合に、新たなパターンを生成する。そして、抽出装置１０は、記憶部１３に記憶された複数のイベントを含むイベントデータ１３ａに基づいて、生成された１以上のパターンがイベントデータ１３ａに登場する頻度を算出する。続いて、抽出装置１０は、頻度が所定の条件を満たす新たなパターンを抽出する。その後、抽出装置１０は、抽出された新たなパターンに対して新たなイベントを追加する。したがって、抽出装置１０によれば、イベントデータ１３ａが示すイベントに出現しないようなイベントの組み合わせ、すなわち、互いに排他的なイベントを含むパターンが生成されない。そのため、抽出装置１０によれば、イベントデータ１３ａが示すイベントのパターンに出現しないイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例に係る抽出装置１０によれば、効率良くパターンを抽出することができる。
【実施例２】
【００５３】
［抽出装置の構成］
次に、実施例２に係る抽出装置について説明する。図１１に示すように、抽出装置４０は、記憶部４３および制御部４４を有する。記憶部４３は、図１に示す実施例１に係る記憶部１３の記憶内容と比較して、イベントデータ１３ａに代えてイベントデータ４３ａを記憶する点が異なる。また、制御部４４は、図１に示す実施例１に係る制御部１４と比較して、初期化部４４ｂ、生成部４４ｃ、バックトラック処理部４４ｄ、カウンタ制御部４４ｅ、抽出部４４ｆを有する点が異なる。なお、以下では、上記の実施例１と同様の機能を果たす各部や機器については図１と同様の符号を付し、その説明を省略する場合がある。
【００５４】
入力部１１は、制御部４４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部４４に、抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部４４に、所定のサーバから後述のイベントデータ４３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部４４に、イベント表１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００５５】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部４４ｆにより抽出されたエピソードを後述の表示制御部１４ｇの制御により表示する。
【００５６】
記憶部４３は、制御部４４で実行される各種プログラムを記憶する。また、記憶部４３には、後述の取得部１４ａにより、イベントデータ４３ａ及びイベント表１３ｂが格納される。
【００５７】
イベントデータ４３ａについて説明する。イベントデータ４３ａは、実際に出現したイベントとイベントが出現した時刻とが対応付けられたデータである。以下、イベントデータ４３ａが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すデータを複数含む場合について説明するが、イベントデータ４３ａはこれに限られない。イベントデータ４３ａは、様々な種類のイベントを含むデータを採用することができる。具体例を挙げて説明すると、イベントデータ４３ａは、出現した時刻ごとに異なる複数のアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すデータを含む。そのため、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すイベントデータ１３ａにおいては、上述した排他的なイベントの組合せのパターンが出現しないが、イベントデータ４３ａでは出現しうる。
【００５８】
以下、イベントデータ４３ａが示すイベントのパターンには、イベントＡ、イベントＢ、イベントＣ、イベントＥが含まれ、イベントＤが含まれない。また、イベントデータ４３ａが示すイベントのパターンには、イベントＡの次にイベントＢが出現するパターン、イベントＡの次にイベントＢ、イベントＢの次にイベントＣが出現するパターン、イベントＡの次にイベントＥが出現するパターンが含まれる。また、イベントデータ４３ａが示すイベントのパターンには、イベントＢの次にイベントＣが出現するパターン、イベントＢの次にイベントＥが出現するパターンが含まれる。
【００５９】
記憶部４３は、例えば、フラッシュメモリなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部４３は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（Random  Access  Memory)、ＲＯＭ（Read  Only  Memory)であってもよい。
【００６０】
制御部４４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部４４は、取得部１４ａと、初期化部４４ｂと、生成部４４ｃと、バックトラック処理部４４ｄと、カウンタ制御部４４ｅと、抽出部４４ｆと、表示制御部１４ｇとを有する。
【００６１】
取得部１４ａは、各種の情報を取得する。例えば、取得部１４ａは、所定のサーバからイベントデータ４３ａを取得する指示が入力部１１から入力された場合には、かかる指示に基づいて、次のような処理を行う。すなわち、取得部１４ａは、図示しないネットワークを介して図示しない所定のサーバにアクセスし、所定のサーバからイベントデータ４３ａを取得する。そして、取得部１４ａは、取得したイベントデータ４３ａを記憶部４３に格納する。また、取得部１４ａは、イベント表１３ｂが入力部１１から入力された場合には、入力されたイベント表１３ｂを取得し、取得したイベント表１３ｂを記憶部４３に格納する。
【００６２】
また、取得部１４ａは、抽出処理を実行する指示が入力部１１から入力された場合には、記憶部４３からイベントデータ４３ａ及びイベント表１３ｂを取得する。
【００６３】
初期化部４４ｂは、各種の初期化を行う。例えば、初期化部４４ｂは、取得部１４ａによりイベントデータ４３ａ及びイベント表１３ｂが取得された場合には、空のエピソード（空エピソード）を列挙木における最初の親、すなわち、根に設定する。ここで、エピソードとは、イベントが出現する順番（出現順序）を有向グラフで表現したものである。例えば、エピソードは、複数のパートを有する。複数のパートのそれぞれには、イベントが含まれる。各パートには、順番が定められている。エピソードが有するＮ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係について説明する。Ｎ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係は、Ｎ番目のパートに含まれるイベントの全てのイベントが出現した後に、（Ｎ＋１）番目のパートに含まれるイベントが出現するという関係である。図１２は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。図１２の例に示すように、初期化部４４ｂは、根のエピソード６０に空エピソード５０を設定する。
【００６４】
そして、初期化部４４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う。続いて、初期化部４４ｂは、後述する生成部４４ｃが実行する、選択したイベントの候補ｅを含む列のカウンタが全て閾値未満であるか否かを判定する処理に用いられる閾値の値を、次のような値に設定する。すなわち、初期化部４４ｂは、かかる閾値の値を、エピソードを抽出する際に用いられ、イベントデータ４３ａのイベントパターンを探索する際の時間的な幅であるウィンドウ幅の値に設定する。ウィンドウ幅とは、例えば、時刻「２」から時刻「３」までの時間（２〜３）に発生したイベントパターンを抽出したい場合には、ウィンドウ幅は、「２」となる。以下、ウィンドウ幅が「２」である場合について説明するが、ウィンドウ幅の値はこれに限られない。
【００６５】
生成部４４ｃは、各種のエピソードを生成する。生成部４４ｃの一態様について説明する。生成部４４ｃは、まず、根のエピソード５０を選択する。
【００６６】
次に、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。なお、本実施例では、空エピソード５０が１番目のパート及び２番目のパートを有する場合について説明する。空エピソード５０が２つのパートを有するため、空エピソード５０の子孫のエピソードもこれらの２つのパートを有する。この場合、生成部４４ｃは、所定のイベントＡ〜Ｅのうち、選択したエピソードのいずれかのパートとの組合せにおいて未選択であるイベントがあるときに、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があると判定する。なお、本実施例では、同一のイベントが同一のパートに含まれないものとする。一方、生成部４４ｃは、所定のイベントＡ〜Ｅのうち、選択したエピソードのいずれのパートとの組合せにおいても未選択となるイベントがない場合には、選択したエピソードに追加するイベントの候補がないと判定する。例えば、図１２の例に示す根のエピソード６０が選択された場合には、所定のイベントＡ〜Ｅのうち、エピソード６０のいずれかのパートとの組合せにおいて未選択であるイベントＡ〜Ｅがある。このため、生成部４４ｃは、選択したエピソード６０のパートに追加するイベントＡ〜Ｅ、及び、イベントが追加されるパート（１番目のパート及び２番目のパート）があると判定する。なお、生成部４４ｃは、表示制御部１４ｇによりエピソードが表示されるように表示部１２の表示が制御された場合にも、同様に、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。また、生成部４４ｃは、カウンタ制御部によりイベント表１３ｂの列のカウンタの値が１つデクリメントされた場合にも、同様に、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがあるか否かを判定する。
【００６７】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合には、生成部４４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択するとともに、パートの候補を１つ選択する。例えば、図１２の例において、選択したエピソード６０に追加するイベントＡ〜Ｅ及びイベントが追加される１番目のパート及び２番目のパートがある場合には、生成部４４ｃは、イベントＡ〜Ｅのうち識別子がアルファベット順で小さいイベントＡを１つ選択する。これに加えて、生成部４４ｃは、イベントが追加することができる１番目のパート及び２番目のパートのうち、最も小さい順番の１番目のパートを選択する。次に、生成部４４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満であるか否かを判定する。例えば、図１２の例に示す場合において、イベントＡが選択された場合には、生成部４４ｃは、先の図２の例に示すイベント表１３ｂにおいて、選択したイベントＡを含む列のカウンタ２０ａの値「０」が、閾値「２」未満であると判定する。
【００６８】
選択したイベントの候補ｅを含む列のカウンタの少なくとも１つの値が閾値「２」以上である場合には、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する上述した処理を再び行う。そして、生成部４４ｃは、かかる処理以降の処理を再び行う。一方、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満である場合には、生成部４４ｃは、選択したエピソードの選択したパートの候補に、選択したイベントの候補ｅを追加して、エピソードを生成する。そして、生成部４４ｃは、生成したエピソードを選択する。図１３は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、生成部４４ｃは、図１３の例に示すように、選択したエピソード６０の選択したパートの候補に、選択したイベントの候補であるイベントＡを追加して、エピソード６１を生成する。そして、生成部４４ｃは、生成したエピソード６１を選択する。なお、エピソードが生成された後に、後述のカウンタ制御部４４ｅにより、イベントの候補ｅを含む列のカウンタの値が１つインクリメントされる。
【００６９】
このように、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満である場合に、選択したエピソードの選択したパートに、選択したイベントの候補ｅが追加されて、エピソードが生成される。また、本実施例では、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満でない場合には、新しいエピソードを生成しない。これは、上述したが、イベントデータ４３ａは、複数のアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すデータを含む。そのため、イベントデータ４３ａが示すイベントのパターンには、先のイベントデータ１３ａが示すイベントのパターンに出現しないイベントの組合せも出現する。そこで、本実施例では、イベントデータ４３ａが示すイベントに出現しないようなイベントの組み合わせ、すなわち、互いに排他的なイベントをウィンドウ幅の大きさよりも多く含むパターンを生成しない。そのため、本実施例では、イベントデータ４３ａが示すイベントのパターンに出現しないイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例は、効率良くパターンを抽出することができる。なお、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満でない場合に、エピソードが生成されないことを、「枝刈り」と称する場合もある。
【００７０】
また、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定した結果、追加するイベントの候補またはパートの候補がない場合には、生成部４４ｃは、次の処理を行う。すなわち、生成部４４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合には処理が終了される。
【００７１】
バックトラック処理部４４ｄは、バックトラックを行う。例えば、抽出部４４ｆにより頻出でないと判別された場合に、バックトラック処理部４４ｄは、生成部４４ｃにより生成されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成する。そして、バックトラック処理部４４ｄは、生成したエピソードを選択する。また、バックトラック処理部４４ｄは、生成部４４ｃにより、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていないと判定された場合にも、同様の処理を行う。すなわち、バックトラック処理部４４ｄは、選択されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成し、生成したエピソードを選択する。
【００７２】
カウンタ制御部４４ｅは、生成部４４ｃによりエピソードが生成された場合に、このエピソードが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする。図１４は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、生成部４４ｃにより図１３に示すエピソード６１が生成された場合には、カウンタ制御部４４ｅは、図１４に示すように、エピソード６１が生成された際に追加されたイベントＡを含むイベント表１３ｂの列のカウンタ２０ａの値を１つインクリメントする。
【００７３】
また、カウンタ制御部４４ｅは、バックトラック処理部４４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントする。
【００７４】
抽出部４４ｆは、カウンタ制御部４４ｅによりイベントの候補ｅを含む列のカウンタの値が１つインクリメントされた場合には、生成されたエピソードの頻度を算出する。例えば、抽出部４４ｆは、生成されたエピソードの極小出現が存在する場合には「１」、存在しない場合には「０」の値を頻度として算出する。ここで、極小出現とは、エピソードの先頭のパートのイベントから、末尾のパートのイベントまでのイベントがイベントデータ４３ａが示すイベントのパターンにおいて存在する最小の時間の区間である。かかる頻度は、「バイナリ頻度」とも称される。そして、生成部４４ｃは、算出した頻度が「１」であるか否かを判定する。そして、算出した頻度が「１」である場合には、生成部４４ｃは、エピソードは、頻出であると判別する。一方、算出した頻度が「１」でない場合、すなわち「０」である場合には、生成部４４ｃは、エピソードは、頻出でないと判別する。
【００７５】
以下、開示の装置が、頻度として「バイナリ頻度」を算出する場合について説明するが、開示の装置は、これに限定されるものではない。例えば、開示の装置は、列挙木における子の頻度が親の頻度以下となるような頻度であれば、バイナリ頻度以外の頻度を算出し、算出された頻度に基づいて、エピソードが頻出であるか否かを判別することができる。このような頻度の一例としては、「ウィンドウ頻度」が挙げられる。「ウィンドウ頻度」とは、予め定められた区間の集合に対して極小出現を含む区間の数、または、前後の区間で一部が重複するような複数の区間の集合に対して極小出現を含む区間の数を指す。頻度として「ウィンドウ頻度」を算出する場合には、抽出部４４ｆは、エピソードの「ウィンドウ頻度」が所定の閾値以上であるか否かを判定することにより、エピソードが頻出であるか否かを判別することができる。
【００７６】
また、他の例としては、「非重複極小出現頻度」が挙げられる。「非重複極小出現頻度」とは、時間がオーバーラップしていない（同じ時間を含まない）極小出現の最大数を指す。頻度として「非重複極小出現頻度」を算出する場合には、抽出部４４ｆは、エピソードの「非重複極小出現頻度」が所定の閾値以上であるか否かを判定することにより、エピソードが頻出であるか否かを判別することができる。抽出部４４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する。例えば、抽出部４４ｆは、頻出であると判別された図１３に示すエピソード６１を表示するエピソードとして抽出する。
【００７７】
表示制御部１４ｇは、各種の情報を表示するように表示部１２の表示を制御する。例えば、表示制御部１４ｇは、抽出部４４ｆにより抽出されたエピソード、例えば、エピソード６１を表示するように表示部１２の表示を制御する。
【００７８】
次に、抽出装置４０が実行する処理の具体例について、先の図１２〜図１４、及び、図１５〜図２４を参照して説明する。なお、図１５〜図２４は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、エピソード６１が表示部１２に表示された後に、抽出装置４０は、図１３に示す場合において、選択したエピソード６１に追加するイベントの候補であるイベントＢ、及び、イベントが追加されるパート（１番目または２番目）を選択する。ここで、選択したイベントＢを含むイベント表１３ｂの列に対応するカウンタ２０ａの値は、図１４に示すように、「１」であり、閾値「２」未満である。このため、抽出装置４０は、図１５に示すように、選択したエピソード６１の選択したパートに、イベントＢを追加してエピソード６２を生成する。そして、抽出装置４０は、図１６に示すように、イベントＢを含むイベント表１３ｂの列のカウンタ２０ａの値を１つインクリメントする。そして、抽出装置４０は、エピソード６２の頻度「１」を算出し、エピソード６２は、頻出であると判別する。続いて、抽出装置４０は、エピソード６２を抽出し、抽出したエピソード６２を表示するように表示部１２を制御する。その後、抽出装置４０は、エピソード６２に追加するイベントの候補であるイベントＣ、及び、イベントが追加されるパートを選択する。
【００７９】
しかしながら、図１６に示すように、イベントＣを含む列に対応するカウンタ２０ａの値「２」が閾値「２」未満でないため、抽出装置４０は、エピソード６２に追加するイベントの候補であるイベントＤ、及び、イベントが追加されるパートを選択する。そして、図１６に示すように、イベントＤを含む列に対応するカウンタ２０ｂの値「１」が閾値「２」未満であるため、抽出装置４０は、次の処理を行う。すなわち、抽出装置４０は、図１７に示すように、エピソード６２の選択したパートに、イベントＤを追加してエピソード６３を生成する。続いて、抽出装置４０は、図１８に示すように、エピソード６３が生成される際に追加されたイベントの候補Ｄを含むイベント表１３ｂの列のカウンタ２０ｂの値を１つインクリメントする。そして、抽出装置４０は、エピソード６３の頻度「０」を算出し、エピソード６３は、頻出でないと判別する。すると、図１９に示すように、抽出装置４０は、エピソード６３から最後に追加されたイベントＤを削除したエピソード６２を生成する。また、図１６に示すように、抽出装置４０は、削除されたイベントＤを含むイベント表１３ｂの列のカウンタ２０ｂの値を１つデクリメントする。
【００８０】
そして、抽出装置４０は、エピソード６２に追加するイベントの候補であるイベントＥ、及び、イベントが追加されるパートを選択する。そして、図１６に示すように、選択したイベントＥを含むイベント表１３ｂの列に対応するカウンタ２０ｂの値「０」が閾値「２」未満でないため、エピソード６２の選択したパートにイベントＥを追加して、図２０に示すように、エピソード６４を生成する。続いて、抽出装置４０は、図１８に示すように、エピソード６４を生成する際に追加されたイベントＥを含むイベント表１３ｂの列のカウンタ２０ｂの値を１つインクリメントする。そして、抽出装置４０は、エピソード６４の頻度「１」を算出し、エピソード６４は、頻出であると判別する。続いて、抽出装置４０は、エピソード６４を抽出し、抽出したエピソード６４を表示するように表示部１２を制御する。また、エピソード６４に追加されるイベントの候補がないため、抽出装置４０は、図２１に示すように、エピソード６４に最後に追加されたイベントＥを削除したエピソード６２を生成する。また、図１６に示すように、抽出装置４０は、削除されたイベントＥを含むイベント表１３ｂの列のカウンタ２０ｂの値を１つデクリメントする。
【００８１】
そして、抽出装置４０は、エピソード６２に追加されるイベントの候補がないため、図２２に示すように、エピソード６２からエピソード６２に最後に追加されたイベントＢを削除したエピソード６１を生成する。また、図１４に示すように、抽出装置４０は、削除されたイベントＢを含むイベント表１３ｂの列のカウンタ２０ａの値を１つデクリメントする。続いて、抽出装置４０は、エピソード６１に追加するイベントの候補であるイベントＣ、及び、イベントが追加されるパートを選択する。そして、図１４に示すように、選択したイベントＣを含むイベント表１３ｂの列に対応するカウンタ２０ａ、２０ｂの値「１」及び「０」が閾値「２」未満である。このため、抽出装置４０は、図２３に示すように、エピソード６１の選択したパートにイベントＣを追加して、エピソード６５を生成する。
【００８２】
続いて、抽出装置４０は、図１８に示すように、エピソード６５が生成される際に追加されたイベントＣを含むイベント表１３ｂの列に対応するカウンタ２０ａ、２０ｂのそれぞれの値を１つインクリメントする。そして、抽出装置４０は、エピソード６５の頻度「０」を算出し、エピソード６５は頻出でないと判別する。そして、抽出装置４０は、図２４に示すように、エピソード６５からエピソード６５に最後に追加されたイベントＣを削除したエピソード６１を生成する。そして、抽出装置４０は、図１４に示すように、削除されたイベントＣを含むイベント表１３ｂの列のカウンタ２０ａ、２０ｂのそれぞれの値を１つデクリメントする。そして、抽出装置４０は、以降も各種の処理を行う。
【００８３】
制御部４４は、ＡＳＩＣやＦＰＧＡなどの集積回路またはＣＰＵやＭＰＵなどの電子回路である。  
【００８４】
［処理の流れ］
次に、本実施例に係る抽出装置４０の処理の流れを説明する。図２５は、実施例２に係る抽出処理の手順を示すフローチャートである。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、制御部４４により実行される。
【００８５】
図２５に示すように、取得部１４ａは、記憶部４３からイベントデータ４３ａを取得する（Ｓ２０１）。そして、取得部１４ａは、記憶部４３からイベント表１３ｂを取得する（Ｓ２０２）。
【００８６】
続いて、初期化部４４ｂは、空エピソードを列挙木における最初の親、すなわち、根に設定する（Ｓ２０３）。そして、初期化部４４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う（Ｓ２０４）。続いて、初期化部４４ｂは、Ｓ２０９での処理に用いられる閾値の値をウィンドウ幅に設定する（Ｓ２０５）。
【００８７】
そして、生成部４４ｃは、根のエピソード６０を選択する（Ｓ２０６）。次に、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する（Ｓ２０７）。
【００８８】
選択したエピソードに追加するイベントの候補、及び、パートの候補がある場合（Ｓ２０７肯定）には、生成部４４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択するとともに、パートの候補を１つ選択する（Ｓ２０８）。次に、生成部４４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満であるか否かを判定する（Ｓ２０９）。
【００８９】
選択したイベントの候補ｅを含む列のカウンタの少なくとも１つの値が閾値「２」以上である場合（Ｓ２０９否定）には、生成部４４ｃは、Ｓ２０７に戻る。一方、選択したイベントの候補ｅを含む列のカウンタが全て閾値「２」未満である場合（Ｓ２０９肯定）には、生成部４４ｃは、選択したエピソードに、選択したイベントの候補ｅを追加して、エピソードを生成する（Ｓ２１０）。そして、生成部４４ｃは、生成したエピソードを選択する（Ｓ２１１）。
【００９０】
カウンタ制御部４４ｅは、選択されたエピソードが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする（Ｓ２１２）。そして、抽出部４４ｆは、生成されたエピソードの頻度を算出する（Ｓ２１３）。そして、抽出部４４ｆは、算出した頻度が「１」であるか否かを判定することにより、生成されたエピソードが頻出であるか否かを判別する（Ｓ２１４）。算出した頻度が「１」である場合（Ｓ２１４肯定）には、抽出部４４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する（Ｓ２１５）。続いて、表示制御部１４ｇは、抽出部４４ｆにより抽出されたエピソードを表示するように表示部１２の表示を制御し（Ｓ２１６）、Ｓ２０７に戻る。
【００９１】
一方、算出した頻度が「１」でない場合（Ｓ２１４否定）には、バックトラック処理部４４ｄは、生成部４４ｃにより生成されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成する（Ｓ２１７）。そして、バックトラック処理部４４ｄは、生成したエピソードを選択する（Ｓ２１８）。その後、カウンタ制御部４４ｅは、バックトラック処理部４４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントし（Ｓ２１９）、Ｓ２０７へ進む。
【００９２】
また、追加するイベントの候補、及び、イベントが追加されるパートの候補がない場合（Ｓ２０７否定）には、生成部４４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する（Ｓ２２０）。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合（Ｓ２２０肯定）には処理を終了する。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードのうち、未生成のエピソードがある場合（Ｓ２２０否定）には、Ｓ２１７へ進む。
【００９３】
上述してきたように、本実施例に係る抽出装置４０は、新たなエピソードを生成する際に、次の処理を行う。すなわち、抽出装置４０は、イベント表１３ｂが示す排他的なイベントの組合せに含まれる各イベントが新たなエピソードに登場する数が所定のウィンドウ幅に基づいて定まる閾値「２」以下となる場合に、新たなパターンを生成する。そして、抽出装置４０は、ウィンドウ幅内に含まれる出現時刻に対応付けられたイベントに基づいて、頻度を算出する。このように、抽出装置４０は、イベントデータ４３ａが示すイベントに出現しないようなイベントの組み合わせに含まれるイベントをウィンドウ幅の大きさよりも多く含むエピソードを生成しない。そのため、抽出装置４０では、イベントデータ４３ａが示すイベントのパターンに出現しないイベントの組み合わせを含むエピソードの頻度を算出する処理や、かかるエピソードが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、抽出装置４０によれば、効率良くエピソードを抽出することができる。
【実施例３】
【００９４】
［抽出装置の構成］
次に、実施例３に係る抽出装置について説明する。図２６に示すように、抽出装置７０は、制御部７４を有する。制御部７４は、図１１に示す実施例２に係る制御部４４と比較して、初期化部７４ｂ、生成部７４ｃ、バックトラック処理部７４ｄ、カウンタ制御部７４ｅ、抽出部７４ｆを有する点が異なる。なお、以下では、上記の実施例１、２と同様の機能を果たす各部や機器については図１、図１１と同様の符号を付し、その説明を省略する場合がある。
【００９５】
入力部１１は、制御部７４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部７４に、抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部７４に、所定のサーバから後述のイベントデータ４３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部７４に、イベント表１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００９６】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部７４ｆにより抽出されたエピソードを後述の表示制御部１４ｇの制御により表示する。
【００９７】
制御部７４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部７４は、取得部１４ａと、初期化部７４ｂと、生成部７４ｃと、バックトラック処理部７４ｄと、カウンタ制御部７４ｅと、抽出部７４ｆと、表示制御部１４ｇとを有する。
【００９８】
初期化部７４ｂは、各種の初期化を行う。例えば、初期化部７４ｂは、取得部１４ａによりイベントデータ４３ａ及びイベント表１３ｂが取得された場合には、空のエピソード（空エピソード）を列挙木における最初の親、すなわち、根に設定する。そして、初期化部７４ｂは、後述する確定部分を空に設定する。
【００９９】
そして、初期化部７４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う。続いて、初期化部７４ｂは、後述する生成部７４ｃが実行する、選択したイベントの候補ｅを含む列のカウンタが全て閾値未満であるか否かを判定する処理に用いられる閾値の値を、ウィンドウ幅の値に設定する。
【０１００】
生成部７４ｃは、各種のエピソードを生成する。生成部７４ｃの一態様について説明する。生成部７４ｃは、まず、先の図１２に示すような根のエピソード５０を選択する。
【０１０１】
次に、生成部７４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。ここで、本実施例では、確定部分よりも後または前にイベントを追加する。ここで、確定部分とは、自身のエピソードを起点とした子孫のエピソードに新たにイベントが追加されないイベント群またはパートを指す。以下の説明では、確定部分よりも後ろにイベントを追加する場合を例に挙げて説明する。なお、本実施例では、空エピソード５０が１番目〜３番目のパートを有する場合について説明する。また、本実施例では、同一のイベントが同一のパートに含まれないものとする。生成部７４ｃは、所定のイベントＡ〜Ｅのうち、選択したエピソードの確定部分よりも後ろのパートとの組合せにおいて未選択となるイベントがある場合には、選択したエピソードに追加するイベントの候補があると判定する。一方、生成部７４ｃは、所定のイベントＡ〜Ｅのうち、選択したエピソードの確定部分よりも後ろのパートとの組合せにおいて未選択となるイベントがない場合には、選択したエピソードに追加するイベントの候補がないと判定する。
【０１０２】
なお、生成部７４ｃは、表示制御部１４ｇによりエピソードが表示されるように表示部１２の表示が制御された場合にも、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。また、生成部７４ｃは、バックトラック処理部７４ｄにより、削除したイベントがエピソードの最後のイベントでないと判定された場合にも、同様に、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があるか否かを判定する。さらに、生成部７４ｃは、バックトラック処理部７４ｄにより、閾値にカウンタの最大値が加算された場合にも、同様に、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があるか否かを判定する。
【０１０３】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合には、生成部７４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択するとともに、パートの候補を１つ選択する。そして、生成部７４ｃは、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろであるか否かを判定する。図２７は、実施例３に係る抽出装置が実行する処理の一例を説明するための図である。図２７の例では、エピソード８０が選択されている場合に、追加するイベントとしてイベントＤが選択され、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、イベントＤの追加場所は次の位置となる。すなわち、選択されたイベントＤの追加場所が、エピソード８０に含まれるイベントＡ〜Ｃよりも後ろとなる。このような場合、生成部７４ｃは、選択したイベントの候補であるイベントＤの追加場所が、選択したエピソード８０に含まれる他のイベントＡ〜Ｃよりも後ろであると判定する。
【０１０４】
また、図２７の例において、エピソード８１が選択されている場合には、選択したイベントＣの追加場所が、エピソード８１に含まれるイベントＡ、Ｂよりも後ろである。そのため、図２７の例において、エピソード８１が選択されている場合には、生成部７４ｃは、選択したイベントの候補であるイベントＣの追加場所が、選択したエピソード８１に含まれる他のイベントＡ、Ｂよりも後ろであると判定する。
【０１０５】
選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろである場合には、生成部７４ｃは、カウンタの最大値が閾値未満であるか否かを判定する。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、カウンタ８０ａ（エピソード８０に対応するカウンタ）の最大値「１」が、符号「９０」が指す対応する閾値「３」未満であると判定する。また、図２７の例において、エピソード８１が選択されている場合には、生成部７４ｃは、カウンタ８１ａ（エピソード８１に対応するカウンタ）の最大値「２」が、符号「９１」が指す対応する閾値「５」未満であると判定する。
【０１０６】
閾値未満でない場合には、生成部７４ｃは、上述した、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがあるか否かを判定する処理を行い、かかる処理以降の処理を再び行う。
【０１０７】
閾値未満である場合には、生成部７４ｃは、閾値からカウンタの最大値を減算して、閾値を更新する。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、符号「９０」が示す閾値「３」からカウンタ８０ａの最大値「１」を減算して、符号「９２」が示す閾値「２」に閾値を更新する。また、図２７の例において、エピソード８１が選択されている場合には、生成部７４ｃは、符号「９１」が示す閾値「５」からカウンタ８１ａの最大値「２」を減算して、符号「９０」が示す閾値「３」に閾値を更新する。
【０１０８】
そして、生成部７４ｃは、全てのカウンタをスタックに保存した後、全てのカウンタを「０」に設定する。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、エピソード８１に対応する３つのカウンタ８０ａの値「１」、「１」、「１」をスタック８２ｂに保存した後、全てのカウンタ８２ａを「０」に設定する。また、図２７の例において、エピソード８１が選択されている場合には、生成部７４ｃは、エピソード８０に対応する３つのカウンタ８１ａの値「０」、「２」、「０」をスタック８０ｂに保存した後、全てのカウンタ８０ａを「０」に設定する。
【０１０９】
そして、生成部７４ｃは、追加されるイベントよりも前のイベントを確定部分とする。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、追加されるイベントＤよりも前のイベントＡ〜Ｃ（イベントＡ〜Ｃのパート）を確定部分とする。また、生成部７４ｃは、図２７の例において、エピソード８１が選択されている場合には、追加されるイベントＣよりも前のイベントＡ、Ｂ（イベントＡ、Ｂのパート）を確定部分とする。
【０１１０】
そして、生成部７４ｃは、選択したエピソードの選択したパートに、選択したイベントの候補ｅを追加して、エピソードを生成する。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＡ〜Ｃを含むパートよりも後ろのパートが、イベントが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、選択したエピソード８０の選択したパートに、イベントＤを追加して、エピソード８２を生成する。また、図２７の例において、エピソード８１が選択されている場合には、選択したエピソード８１の選択したパートに、イベントＣを追加して、エピソード８０を生成する。続いて、生成部７４ｃは、生成したエピソードを選択する。
【０１１１】
また、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定した結果、追加するイベントの候補またはパートの候補がない場合には、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合には処理が終了される。
【０１１２】
また、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろでない場合には、生成部７４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値未満であるか否かを判定する。全て閾値未満でない場合には、生成部７４ｃは、上述した、イベントの候補及びパートの候補があるか否かを判定する処理を行って、かかる処理以降の処理を再び行う。また、全て閾値未満である場合には、生成部７４ｃは、選択したエピソードの選択したパートに、選択したイベントの候補ｅを追加して、エピソードを生成する処理を行って、かかる処理以降の処理を再び行う。例えば、図２７の例において、エピソード８０が選択されている場合に、イベントＤが選択され、かつ、イベントＣを含むパートが、イベントＤが追加されるパートとして選択されたときには、生成部７４ｃは、次の処理を行う。すなわち、すなわち、生成部７４ｃは、選択したエピソード８０の選択したパートに、イベントＤを追加して、エピソード８２を生成する。
【０１１３】
バックトラック処理部７４ｄは、バックトラックを行う。例えば、生成部７４ｃにより頻出でないと判別された場合に、バックトラック処理部７４ｄは、生成部７４ｃにより生成されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成する。そして、バックトラック処理部７４ｄは、生成したエピソードを選択する。また、バックトラック処理部７４ｄは、生成部７４ｃにより、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていないと判定された場合にも、同様の処理を行う。すなわち、バックトラック処理部７４ｄは、選択されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成し、生成したエピソードを選択する。
【０１１４】
また、バックトラック処理部７４ｄは、カウンタ制御部７４ｅによりカウンタの値が１つデクリメントされた場合には、削除したイベントが、削除前のエピソードの最後のイベントであるか否かを判定する。例えば、図２７の例において、エピソード８０が選択され、削除前のエピソードがエピソード８２である場合には、バックトラック処理部７４ｄは、削除したイベントＤが、削除前のエピソード８２の最後のイベントであると判定する。また、図２７の例において、エピソード８０が選択され、削除前のエピソードがエピソード８３である場合には、バックトラック処理部７４ｄは、削除したイベントＣが、削除前のエピソード８３の最後のイベントではないと判定する。また、図２７の例において、エピソード８１が選択され、削除前のエピソードがエピソード８０である場合には、バックトラック処理部７４ｄは、削除したイベントＣが、削除前のエピソード８０の最後のイベントであると判定する。
【０１１５】
最後のイベントである場合には、バックトラック処理部７４ｄは、１つ前の確定部分を新たな確定部分として、確定部分を更新する。例えば、図２７の例において、エピソード８１が選択され、削除前のエピソードがエピソード８０である場合には、バックトラック処理部７４ｄは、確定部分を空エピソードに設定する。また、図２７の例において、エピソード８０が選択され、削除前のエピソードがエピソード８２である場合には、バックトラック処理部７４ｄは、イベントＡ、Ｂ（イベントＡ、Ｂのパート）を確定部分とする。
【０１１６】
そして、バックトラック処理部７４ｄは、全てのカウンタをスタックから復元する。例えば、図２７の例において、エピソード８１が選択され、削除前のエピソードがエピソード８０である場合には、バックトラック処理部７４ｄは、次の処理を行う。すなわち、バックトラック処理部７４ｄは、スタック８０ｂに格納された「０」、「２」、「０」を復元して、カウンタ８１ａの値「０」、「２」、「０」とする。また、図２７の例において、エピソード８０が選択され、削除前のエピソードがエピソード８２である場合には、バックトラック処理部７４ｄは、スタック８２ｂに格納された「１」、「１」、「１」を復元して、カウンタ８０ａの値「１」、「１」、「１」とする。
【０１１７】
続いて、バックトラック処理部７４ｄは、閾値にカウンタの最大値を加算して、閾値を更新する。例えば、図２７に示す場合において、エピソード８０が選択され、削除前のエピソードがエピソード８２である場合には、バックトラック処理部７４ｄは、次の処理を行う。すなわち、バックトラック処理部７４ｄは、符号「９２」が示す閾値「２」に、カウンタ８０ａの値「１」、「１」、「１」の最大値「１」を加算した値「３」を、符号「９０」が示す閾値に設定し、閾値を更新する。また、図２７に示す場合において、エピソード８１が選択され、削除前のエピソードがエピソード８０である場合には、バックトラック処理部７４ｄは、次の処理を行う。すなわち、バックトラック処理部７４ｄは、符号「９０」が示す閾値「３」に、カウンタ８１ａの値「０」、「２」、「０」の最大値「２」を加算した値「５」を、符号「９１」が示す閾値に設定し、閾値を更新する。
【０１１８】
カウンタ制御部７４ｅは、生成部７４ｃによりエピソードが生成された場合に、このエピソードが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする。また、カウンタ制御部７４ｅは、バックトラック処理部７４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントする。
【０１１９】
抽出部７４ｆは、カウンタ制御部７４ｅによりイベントの候補ｅを含む列のカウンタの値が１つインクリメントされた場合には、生成されたエピソードの頻度を算出する。そして、抽出部７４ｆは、エピソードの頻度に基づいて、エピソードが頻出であるか否かを判定する。そして、抽出部７４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する。
【０１２０】
表示制御部１４ｇは、各種の情報を表示するように表示部１２の表示を制御する。例えば、表示制御部１４ｇは、抽出部７４ｆにより抽出されたエピソードを表示するように表示部１２の表示を制御する。
【０１２１】
制御部７４は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。  
【０１２２】
［処理の流れ］
次に、本実施例に係る抽出装置７０の処理の流れを説明する。図２８は、実施例３に係る抽出処理の手順を示すフローチャートである。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、制御部７４により実行される。
【０１２３】
図２８に示すように、取得部１４ａは、イベントデータ４３ａを取得する（Ｓ３０１）。次に、取得部１４ａは、イベント表１３ｂを取得する（Ｓ３０２）。そして、初期化部７４ｂは、空エピソードを列挙木における最初の親、すなわち、根に設定する（Ｓ３０３）。続いて、初期化部７４ｂは、確定部分を空に設定する（Ｓ３０４）。
【０１２４】
そして、初期化部７４ｂは、イベント表１３ｂのカウンタ２０ａ、２０ｂの値を「０」に設定することで、カウンタ２０ａ、２０ｂの初期化を行う（Ｓ３０５）。続いて、初期化部７４ｂは、エピソードが頻出であるか否かを判定する際に用いられる閾値の値を、ウィンドウ幅の値に設定する（Ｓ３０６）。
【０１２５】
生成部７４ｃは、根のエピソード５０を選択する（Ｓ３０７）。次に、生成部７４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する（Ｓ３０８）。
【０１２６】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合（Ｓ３０８肯定）には、生成部７４ｃは、未選択のイベントをイベントの候補ｅとして１つ選択するとともに、パートの候補を１つ選択する（Ｓ３０９）。そして、生成部７４ｃは、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろであるか否かを判定する（Ｓ３１０）。
【０１２７】
選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろである場合（Ｓ３１０肯定）には、生成部７４ｃは、カウンタの最大値が閾値未満であるか否かを判定する（Ｓ３１１）。閾値未満でない場合（Ｓ３１１否定）には、生成部７４ｃは、Ｓ３０８に戻る。
【０１２８】
閾値未満である場合（Ｓ３１１肯定）には、生成部７４ｃは、閾値からカウンタの最大値を減算して、閾値を更新する（Ｓ３１２）。そして、生成部７４ｃは、全てのカウンタをスタックに保存する（Ｓ３１３）。そして、生成部７４ｃは、全てのカウンタを「０」に設定する（Ｓ３１４）。そして、生成部７４ｃは、追加されるイベントよりも前のイベントを確定部分とする（Ｓ３１５）。
【０１２９】
そして、生成部７４ｃは、選択したエピソードの選択したパートに、選択したイベントの候補ｅを追加して、エピソードを生成し、生成したエピソードを選択する（Ｓ３１６）。そして、カウンタ制御部７４ｅは、エピソードが生成される際に追加されたイベントの候補ｅを含むイベント表１３ｂの列のカウンタの値を１つインクリメントする（Ｓ３１７）。続いて、抽出部７４ｆは、生成されたエピソードの頻度を算出する（Ｓ３１８）。そして、抽出部７４ｆは、エピソードの頻度に基づいて、エピソードが頻出であるか否かを判定する（Ｓ３１９）。エピソードが頻出である場合（Ｓ３１９肯定）には、抽出部７４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する（Ｓ３２０）。続いて、表示制御部１４ｇは、抽出部７４ｆにより抽出されたエピソードを表示するように表示部１２の表示を制御し（Ｓ３２１）、Ｓ３０８へ戻る。
【０１３０】
また、追加するイベントの候補またはパートの候補がない場合（Ｓ３０８否定）には、生成部７４ｃは、次の処理を行う。すなわち、生成部７４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する（Ｓ３３０）。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合（Ｓ３３０肯定）には処理を終了する。
【０１３１】
また、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろでない場合（Ｓ３１０否定）には、生成部７４ｃは、次のような処理を行う。すなわち、生成部７４ｃは、イベント表１３ｂにおいて、選択したイベントの候補ｅを含む列のカウンタが全て閾値未満であるか否かを判定する（Ｓ３２２）。閾値未満である場合（Ｓ３２２肯定）には、Ｓ３１６へ進む。一方、閾値未満でない場合（Ｓ３２２否定）には、Ｓ３０８へ進む。
【０１３２】
一方、頻出でない場合（Ｓ３１９否定）、及び、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていない場合（Ｓ３３０否定）には、バックトラック処理部７４ｄは、次の処理を行う。すなわち、バックトラック処理部７４ｄは、生成部７４ｃにより生成されたエピソードから最後に追加されたイベントｅを削除したエピソードを生成する（Ｓ３２３）。そして、バックトラック処理部７４ｄは、生成したエピソードを選択する（Ｓ３２４）。続いて、カウンタ制御部７４ｅは、バックトラック処理部７４ｄにより削除されたイベントｅを含むイベント表１３ｂの列のカウンタの値を１つデクリメントする（Ｓ３２５）。
【０１３３】
続いて、バックトラック処理部７４ｄは、削除したイベントがエピソードの最後のイベントであるか否かを判定する（Ｓ３２６）。最後のイベントである場合（Ｓ３２６肯定）には、バックトラック処理部７４ｄは、１つ前の確定部分を新たな確定部分として、確定部分を更新する（Ｓ３２７）。そして、バックトラック処理部７４ｄは、全てのカウンタをスタックから復元する（Ｓ３２８）。続いて、バックトラック処理部７４ｄは、閾値にカウンタの最大値を加算して、閾値を更新し（Ｓ３２９）、Ｓ３０８に戻る。一方、最後のイベントでない場合（Ｓ３２６否定）にも、Ｓ３０８に戻る。
【０１３４】
上述してきたように、本実施例に係る抽出装置７０は、エピソードにイベントを追加して新たなエピソードを生成する際に、エピソードに追加されるイベントが、イベントの末尾に追加されるイベントである場合には、次の処理を行う。すなわち、抽出装置７０は、ウィンドウ幅の大きさを示す閾値から、追加されるイベント以外のエピソードのイベントのうち、イベント表１３ｂが示す排他的なイベントの組合せに含まれるイベントの数を減算した値を新たな閾値とすることにより閾値を更新する。そして、抽出装置７０は、閾値が更新された場合には、エピソードのイベントの末尾にイベントを追加して新たなエピソードを生成する際に、イベント表１３ｂが示す排他的なイベントの組合せに基づいて、次の処理を行う。すなわち、抽出装置７０は、かかる組合せに含まれる各イベントが、追加されるイベントに登場する数が更新後の閾値以下である場合に、新たなエピソードを生成する。したがって、抽出装置７０によれば、ウィンドウ幅を超えるような時間を有するエピソードの生成が抑制される。それゆえ、抽出装置７０によれば、ウィンドウ幅を超えるような抽出されないエピソードの頻度を算出する処理や、かかるエピソードが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、抽出装置７０によれば、効率良くエピソードを抽出することができる。
【０１３５】
また、本実施例に係る抽出装置７０は、頻度が所定の条件を満たさないような頻出でないエピソードから、エピソードに最後に追加されたイベントを削除することで、エピソードを生成する。また、抽出装置７０は、エピソードが生成された際に削除されたイベントが末尾のイベントである場合には、次の処理を行う。すなわち、抽出装置７０は、更新された閾値に、生成されたエピソードのイベントのうちイベント表１３ｂが示す排他的なイベントの組合せに含まれるイベントの数を加算した値を閾値とすることにより閾値を新たに更新する。そして、抽出装置７０は、新たに生成されたエピソードから更に新たなエピソードを生成する際に、イベント表１３ｂが示す排他的なイベントの組合せに基づいて、次の処理を行う。すなわち、抽出装置７０は、かかる組合せに含まれる各イベントが更に新たなエピソードに登場する数が新たに更新された閾値以下である場合に、更に新たなエピソードを生成する。したがって、抽出装置７０によれば、イベントを削除してエピソードを生成した場合に、生成されたエピソードに含まれるイベントに対応する値に閾値が更新される。それゆえ、抽出装置７０によれば、イベントを削除してエピソードを生成する場合であっても、ウィンドウ幅を超えるような時間を有するエピソードの生成が抑制される。それゆえ、抽出装置７０によれば、イベントを削除してエピソードを生成する場合であっても、次のような無駄な処理を行うことが抑制される。すなわち、抽出装置７０によれば、ウィンドウ幅を超えるような抽出されないエピソードの頻度を算出する処理や、かかるエピソードが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、抽出装置７０によれば、効率良くエピソードを抽出することができる。
【０１３６】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１３７】
例えば、開示の装置が、確定部分よりも後ろにイベントを追加し、また、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろであるか否かを判定する場合を例に挙げて説明したが、開示の装置は、これに限定されない。開示の装置は、確定部分よりも前にイベントを追加し、また、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも前であるか否かを判定することもできる。この場合、開示の装置は、上記で説明した内容と同様の処理を行うことができる。すなわち、開示の装置は、頻度が所定の条件を満たさないような頻出でないエピソードから、エピソードに最後に追加されたイベントを削除することで、エピソードを生成する。また、開示の装置は、エピソードが生成された際に削除されたイベントが先頭のイベントである場合には、次の処理を行う。すなわち、開示の装置は、更新された閾値に、生成されたエピソードのイベントのうちイベント表１３ｂが示す排他的なイベントの組合せに含まれるイベントの数を加算した値を閾値とすることにより閾値を新たに更新する。そして、開示の装置は、新たに生成されたエピソードから更に新たなエピソードを生成する際に、イベント表１３ｂが示す排他的なイベントの組合せに基づいて、次の処理を行う。すなわち、開示の装置は、かかる組合せに含まれる各イベントが更に新たなエピソードに登場する数が新たに更新された閾値以下である場合に、更に新たなエピソードを生成する。したがって、かかる開示の装置によれば、ウィンドウ幅を超えるような抽出されないエピソードの頻度を算出する処理や、かかるエピソードが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、かかる開示の装置によれば、効率良くエピソードを抽出することができる。
【０１３８】
また、実施例などにおいて説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。
【０１３９】
また、各種の負荷や使用状況などに応じて、実施例などにおいて説明した各処理の各ステップでの処理を任意に細かくわけたり、あるいはまとめたりすることができる。また、ステップを省略することもできる。
【０１４０】
また、各種の負荷や使用状況などに応じて、実施例などにおいて説明した各処理の各ステップでの処理の順番を変更できる。
【０１４１】
また、図示した装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１４２】
［抽出プログラム］
また、上記の抽出装置（１０、４０、７０）の抽出処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図２９を用いて、上記の抽出装置と同様の機能を有する抽出プログラムを実行するコンピュータの一例を説明する。
【０１４３】
図２９は、抽出プログラムを実行するコンピュータを示す図である。図２９に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３００〜３４０の各部は、バス３５０を介して接続される。
【０１４４】
ＨＤＤ３３０には、上記の実施例１で示す各部１４ａ〜１４ｇ、実施例２で示す各部１４ａ、４４ｂ〜４４ｆ、１４ｇ、または、実施例３で示す各部１４ａ、７４ｂ〜７４ｆ、１４ｇと同様の機能を発揮する抽出プログラム３３０ａが予め記憶される。なお、抽出プログラム３３０ａについては、適宜分離しても良い。
【０１４５】
そして、ＣＰＵ３１０が、抽出プログラム３３０ａをＨＤＤ３３０から読み出して実行する。
【０１４６】
そして、ＨＤＤ３３０には、イベントデータ及びイベント表が設けられる。
【０１４７】
そして、ＣＰＵ３１０は、イベントデータ及びイベント表を読み出してＲＡＭ３４０に格納する。さらに、ＣＰＵ３１０は、ＲＡＭ３４０に格納されたイベントデータ及びイベント表を用いて、抽出プログラム３３０ａを実行する。なお、ＲＡＭ３４０に格納される各データは、常に全てのデータがＲＡＭ３４０に格納されなくともよく、全てのデータのうち処理に用いられるデータのみがＲＡＭ３４０に格納されれば良い。
【０１４８】
なお、上記した抽出プログラム３３０ａについては、必ずしも最初からＨＤＤ３３０に記憶させなくともよい。
【０１４９】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。  
【０１５０】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１５１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１５２】
（付記１）コンピュータに、
イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下である場合に、前記第２のパターンを生成し、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、前記第２のパターンが前記データに登場する頻度を算出し、
前記頻度が所定の条件を満たす第２のパターンを抽出し、
抽出された第２のパターンに対してイベントを追加する
各処理を実行させることを特徴とする抽出プログラム。
【０１５３】
（付記２）前記データは、複数のイベントと各イベントの出現時刻とを対応付けた複数のデータを含むイベントデータであり、
前記第２のパターンを生成する処理は、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が所定のウィンドウ幅に基づいて定まる閾値以下である場合に、前記第２のパターンを生成し、
前記頻度を算出する処理は、前記所定のウィンドウ幅内に含まれる前記出現時刻に対応付けられたイベントに基づいて、前記頻度を算出する
ことを特徴とする付記１に記載の抽出プログラム。
【０１５４】
（付記３）前記コンピュータに、更に、前記第２のパターンを生成する際に前記第１のパターンに追加されるイベントが該第１のパターンのイベントの先頭又は末尾に追加されるイベントである場合には、前記第１の閾値から、該第１のパターンに該追加されるイベント以外の該第１のパターンのイベントのうち前記組合せに含まれるイベントの数を減算した値を前記閾値とすることにより該閾値を更新する処理を実行させ、
前記第２のパターンを生成する処理は、前記閾値が更新された場合には、前記第１のパターンのイベントの前記先頭又は前記末尾にイベントを追加して前記第２のパターンを生成する際に、前記記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが、前記追加されるイベントに登場する数が前記更新された閾値以下である場合に、前記第２のパターンを生成する、
ことを特徴とする付記２に記載の抽出プログラム。
【０１５５】
（付記４）前記コンピュータに、更に、前記頻度が前記所定の条件を満たさない第２のパターンから、該第２のパターンに最後に追加されたイベントを削除することで、前記第１のパターンを生成する処理を実行させ、
前記閾値を更新する処理は、前記第１のパターンが生成された際に削除された前記イベントが先頭又は末尾のイベントである場合には、前記更新された閾値に、前記第１のパターンのイベントのうち前記組合せに含まれるイベントの数を加算した値を前記閾値とすることにより該閾値を新たに更新し、
前記第２のパターンを生成する処理は、前記第１のパターンにイベントを追加して前記第２のパターンを生成する際に、前記組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が新たに更新された前記閾値以下である場合に、前記第２のパターンを生成する
ことを特徴とする付記３に記載の抽出プログラム。  
【０１５６】
（付記５）イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下である場合に、前記第２のパターンを生成するとともに、抽出された前記第２のパターンに対してイベントを追加する第１の生成部と、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、前記第２のパターンが前記データに登場する頻度を算出し、前記頻度が所定の条件を満たす第２のパターンを抽出する抽出部と、
を有することを特徴とする抽出装置。
【０１５７】
（付記６）前記データは、複数のイベントと各イベントの出現時刻とを対応付けた複数のデータを含むイベントデータであり、
前記第１の生成部は、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が所定のウィンドウ幅に基づいて定まる閾値以下である場合に、前記第２のパターンを生成し、
前記抽出部は、前記所定のウィンドウ幅内に含まれる前記出現時刻に対応付けられたイベントに基づいて、前記頻度を算出し、前記頻度が所定の条件を満たす第２のパターンを抽出する
ことを特徴とする付記５に記載の抽出装置。
【０１５８】
（付記７）前記第１の生成部は、前記第２のパターンを生成する際に前記第１のパターンに追加されるイベントが該第１のパターンのイベントの先頭又は末尾に追加されるイベントである場合には、前記閾値から、該第１のパターンに該追加されるイベント以外の該第１のパターンのイベントのうち前記組合せに含まれるイベントの数を減算した値を前記閾値とすることにより前記閾値を更新し、前記組合せに含まれる各イベントが、前記追加されるイベント数が前記更新された閾値以下であるときに、前記第２のパターンを生成することを特徴とする付記６に記載の抽出装置。
【０１５９】
（付記８）前記頻度が前記所定の条件を満たさない第２のパターンから、該第２のパターンに最後に追加されたイベントを削除することで、前記第１のパターンを生成し、前記第１のパターンが生成された際に削除された前記イベントが先頭又は末尾のイベントである場合には、前記更新された閾値に、前記第１のパターンのイベントのうち前記組合せに含まれるイベントの数を加算した値を前記閾値とすることにより該閾値を新たに更新する第２の生成部を更に有し、
前記第１の生成部は、前記第１のパターンにイベントを追加して前記第２のパターンを生成する際に、前記組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が新たに更新された前記閾値以下である場合に、前記第２のパターンを生成する
ことを特徴とする付記７に記載の抽出装置。
【０１６０】
（付記９）コンピュータが、
イベントを含む第１のパターンにイベントを追加して第２のパターンを生成する際に、記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が閾値以下である場合に、前記第２のパターンを生成し、
前記記憶部に記憶された複数のイベントを含むデータに基づいて、前記第２のパターンが前記データに登場する頻度を算出し、
前記頻度が所定の条件を満たす第２のパターンを抽出し、
抽出された第２のパターンに対してイベントを追加する
各処理を実行することを特徴とする抽出方法。
【０１６１】
（付記１０）前記データは、複数のイベントと各イベントの出現時刻とを対応付けた複数のデータを含むイベントデータであり、
前記第２のパターンを生成する処理は、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が所定のウィンドウ幅に基づいて定まる閾値以下である場合に、前記第２のパターンを生成し、
前記頻度を算出する処理は、前記所定のウィンドウ幅内に含まれる前記出現時刻に対応付けられたイベントに基づいて、前記頻度を算出する
ことを特徴とする付記９に記載の抽出方法。
【０１６２】
（付記１１）前記コンピュータが、更に、前記第２のパターンを生成する際に前記第１のパターンに追加されるイベントが該第１のパターンのイベントの先頭又は末尾に追加されるイベントである場合には、前記第１の閾値から、該第１のパターンに該追加されるイベント以外の該第１のパターンのイベントのうち前記組合せに含まれるイベントの数を減算した値を前記閾値とすることにより該閾値を更新する処理を実行し、
前記第２のパターンを生成する処理は、前記閾値が更新された場合には、前記第１のパターンのイベントの前記先頭又は前記末尾にイベントを追加して前記第２のパターンを生成する際に、前記記憶部に記憶されたイベントの組合せに基づいて、前記組合せに含まれる各イベントが、前記追加されるイベントに登場する数が前記更新された閾値以下である場合に、前記第２のパターンを生成する、
ことを特徴とする付記１０に記載の抽出方法。
【０１６３】
（付記１２）前記コンピュータが、更に、前記頻度が前記所定の条件を満たさない第２のパターンから、該第２のパターンに最後に追加されたイベントを削除することで、前記第１のパターンを生成する処理を実行し、
前記閾値を更新する処理は、前記第１のパターンが生成された際に削除された前記イベントが先頭又は末尾のイベントである場合には、前記更新された閾値に、前記第１のパターンのイベントのうち前記組合せに含まれるイベントの数を加算した値を前記閾値とすることにより該閾値を新たに更新し、
前記第２のパターンを生成する処理は、前記第１のパターンにイベントを追加して前記第２のパターンを生成する際に、前記組合せに基づいて、前記組合せに含まれる各イベントが前記第２のパターンに登場する数が新たに更新された前記閾値以下である場合に、前記第２のパターンを生成する
ことを特徴とする付記１０に記載の抽出方法。  
【符号の説明】
【０１６４】
１０      抽出装置
１３      記憶部
１３ａ    イベントデータ
１３ｂ    イベント表
１４ｃ    生成部
１４ｄ    バックトラック処理部
１４ｅ    カウンタ制御部
１４ｆ    抽出部
【図１】
2014099115.tif 000003
【図２】
2014099115.tif 000004
【図３】
2014099115.tif 000005
【図４】
2014099115.tif 000006
【図５】
2014099115.tif 000007
【図６】
2014099115.tif 000008
【図７】
2014099115.tif 000009
【図８】
2014099115.tif 000010
【図９】
2014099115.tif 000011
【図１０】
2014099115.tif 000012
【図１１】
2014099115.tif 000013
【図１２】
2014099115.tif 000014
【図１３】
2014099115.tif 000015
【図１４】
2014099115.tif 000016
【図１５】
2014099115.tif 000017
【図１６】
2014099115.tif 000018
【図１７】
2014099115.tif 000019
【図１８】
2014099115.tif 000020
【図１９】
2014099115.tif 000021
【図２０】
2014099115.tif 000022
【図２１】
2014099115.tif 000023
【図２２】
2014099115.tif 000024
【図２３】
2014099115.tif 000025
【図２４】
2014099115.tif 000026
【図２５】
2014099115.tif 000027
【図２６】
2014099115.tif 000028
【図２７】
2014099115.tif 000029
【図２８】
2014099115.tif 000030
【図２９】
2014099115.tif 000031