(57)【要約】【課題】効率良く所定のパターンを含むパターンを抽出すること。【解決手段】抽出プログラム３３０ａは、一つの態様において、コンピュータに、記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けたイベントデータに基づいて、次のような処理を実行させる。すなわち、抽出プログラム３３０ａは、コンピュータに、複数のイベントと各イベントの出現順序とが対応付けられた第１のパターンに対してイベントを順に追加する。これにより、抽出プログラム３３０ａは、コンピュータに、第１のパターンを含み、かつ、イベントデータに出現する第２のパターンを順に生成する処理を実行させる。そして、抽出プログラム３３０ａは、コンピュータに、生成された第２のパターンから所定条件を満たすパターンを抽出する処理を実行させる。【選択図】図１９
2014085729.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けたイベントデータに基づいて、複数のイベントと各イベントの出現順序とが対応付けられた第１のパターンに対してイベントを順に追加することで、前記第１のパターンを含み、かつ、前記イベントデータに出現する第２のパターンを順に生成し、
生成された第２のパターンから所定条件を満たすパターンを抽出する
各処理を実行させることを特徴とする抽出プログラム。
【請求項２】
前記コンピュータに、更に、
前記第２のパターンから前記第１のパターンを除いたパターンにおいて、存在するイベントのうち末尾のイベントに対応する前記出現順序を算出する処理を実行させ、
前記第２のパターンを順に生成する処理は、前記第１のパターンの、算出された前記出現順序よりも大きい出現順序に対応するイベントに、前記第１のパターンの、該算出された出現順序よりも大きい該出現順序に対応するイベントに含まれないイベントを順に追加することで、前記第２のパターンを順に生成する
ことを特徴とする請求項１に記載の抽出プログラム。
【請求項３】
前記コンピュータに、更に、
前記第２のパターンから前記第１のパターンを除いたパターンにおいて、前記末尾のイベントのうち所定の順番のルールに従って定められた順番が最も大きいイベントを特定する処理を実行させ、
前記第２のパターンを順に生成する処理は、前記第１のパターンの、算出された前記出現順序に対応するイベントに、前記第１のパターンの、該算出された出現順序に対応するイベントに含まれないイベントであって、特定された前記イベントよりも順番が大きいイベントを順に追加することで、前記第２のパターンを順に生成する
ことを特徴とする請求項１又は請求項２に記載の抽出プログラム。
【請求項４】
前記コンピュータに、更に、
親と子の関係を有する２つの前記第２のパターンのうち、親のパターンの先頭のイベントから、該親のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する親のパターンのイベントまでのイベントが前記イベントデータにおいて出現する第１の時間、子のパターンが生成される際に追加されたイベントが前記イベントデータにおいて出現する第２の時間、及び、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記第１のパターンのイベントが前記イベントデータにおいて出現する第３の時間に基づいて、前記子のパターンの先頭のイベントから、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントまでのイベントが前記イベントデータにおいて出現する第４の時間を算出し、
前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントが、前記子のパターンの末尾のイベントである場合には、前記第４の時間を、前記子のパターンの先頭のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第５の時間として算出する
各処理を実行させることを特徴とする請求項２に記載の抽出プログラム。
【請求項５】
前記コンピュータに、更に、
前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントが、前記子のパターンの末尾のイベントでない場合には、前記第４の時間、及び、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記第１のパターンのイベントの次のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第６の時間に基づいて、前記第５の時間を算出する
処理を実行させることを特徴とする請求項４に記載の抽出プログラム。
【請求項６】
前記コンピュータに、更に、
親と子の関係を有する２つの前記第２のパターンのうち、子のパターンが生成される際に追加されたイベントが前記イベントデータにおいて出現する第１の時間、及び、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記第１のパターンのイベントが前記イベントデータにおいて出現する第２の時間に基づいて、前記子のパターンの先頭のイベントから、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントまでのイベントが前記イベントデータにおいて出現する第３の時間を算出し、
前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントが、前記子のパターンの末尾のイベントである場合には、前記第３の時間を、前記子のパターンの先頭のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第４の時間として算出する
各処理を実行させることを特徴とする請求項２に記載の抽出プログラム。
【請求項７】
前記コンピュータに、更に、
前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントが、前記子のパターンの末尾のイベントでない場合には、前記第３の時間、及び、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記第１のパターンのイベントの次のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第５の時間に基づいて、前記第４の時間を算出する
処理を実行させることを特徴とする請求項６に記載の抽出プログラム。
【請求項８】
前記コンピュータに、更に、
親と子の関係を有する２つの前記第２のパターンのうち、親のパターンの先頭のイベントから、該親のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する該親のパターンのイベントまでのイベントが前記イベントデータにおいて出現する第１の時間、及び、子のパターンが生成される際に追加されたイベントと、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序とが対応付けられた前記親の兄弟のパターンの先頭のイベントから、該出現順序に対応するイベントまでのイベントが前記イベントデータにおいて出現する第２の時間に基づいて、前記子のパターンの先頭のイベントから、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントまでのイベントが前記イベントデータにおいて出現する第３の時間を算出し、
前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序に対応する前記子のパターンのイベントの次のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第４の時間を算出し、
前記第３の時間、及び、前記第４の時間に基づいて、前記子のパターンの先頭のイベントから末尾のイベントまでのイベントが前記イベントデータにおいて出現する第５の時間を算出する
各処理を実行させることを特徴する請求項３に記載の抽出プログラム。
【請求項９】
前記コンピュータに、更に、
親と子の関係を有する２つの前記第２のパターンのうち、親のパターンの先頭のイベントから、末尾のイベントまでのイベントが前記イベントデータにおいて出現する第１の時間、及び、子のパターンが生成される際に追加されたイベントと、前記子のパターンが生成される際に追加されたイベントに対応する前記出現順序とが対応付けられた前記親の兄弟のパターンの先頭のイベントから、末尾のイベントまでのイベントが前記イベントデータにおいて出現する第２の時間に基づいて、前記子のパターンの先頭のイベントから、末尾のイベントまでのイベントが前記イベントデータにおいて出現する第３の時間を算出する
処理を実行させることを特徴とする請求項３に記載の抽出プログラム。
【請求項１０】
前記第２の時間及び前記第３の時間は、予め記憶手段に記憶されており、
前記第４の時間を算出する処理は、前記記憶手段に記憶された前記第２の時間及び前記第３の時間を取得し、取得した前記第２の時間及び前記第３の時間、並びに、前記第１の時間に基づいて、前記第４の時間を算出する
ことを特徴とする請求項４又は請求項５に記載の抽出プログラム。
【請求項１１】
前記第６の時間は、予め記憶手段に記憶されており、
前記第５の時間を算出する処理は、前記記憶手段に記憶された前記第６の時間を取得し、取得した前記第６の時間、及び、前記第４の時間に基づいて、前記第５の時間を算出する
ことを特徴とする請求項５に記載の抽出プログラム。
【請求項１２】
前記第１の時間及び前記第２の時間は、予め記憶手段に記憶されており、
前記第３の時間を算出する処理は、前記記憶手段に記憶された前記第１の時間及び前記第２の時間を取得し、取得した前記第１の時間及び前記第２の時間に基づいて、前記第３の時間を算出する
ことを特徴とする請求項６又は請求項７に記載の抽出プログラム。
【請求項１３】
前記第５の時間は、予め記憶手段に記憶されており、
前記第４の時間を算出する処理は、前記記憶手段に記憶された前記第５の時間を取得し、取得した前記第５の時間、及び、前記第３の時間に基づいて、前記第４の時間を算出する
ことを特徴とする請求項７に記載の抽出プログラム。
【請求項１４】
複数のイベントと各イベントの出現時刻とを対応付けたイベントデータが記憶された記憶部と、
記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けたイベントデータに基づいて、複数のイベントと各イベントの出現順序とが対応付けられた第１のパターンに対してイベントを順に追加することで、前記第１のパターンを含み、かつ、前記イベントデータに出現する第２のパターンを順に生成する生成部と、
生成された第２のパターンから所定条件を満たすパターンを抽出する抽出部と、
を有することを特徴とする抽出装置。
【請求項１５】
コンピュータが、
記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けたイベントデータに基づいて、複数のイベントと各イベントの出現順序とが対応付けられた第１のパターンに対してイベントを順に追加することで、前記第１のパターンを含み、かつ、前記イベントデータに出現する第２のパターンを順に生成し、
生成された第２のパターンから所定条件を満たすパターンを抽出する
ことを特徴とする抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、抽出プログラム、抽出装置及び抽出方法に関する。
【背景技術】
【０００２】
実際に出現したイベントとイベントが出現した時刻とが対応付けられたイベントデータが示すイベントのパターンの中から、イベントとイベントが出現する順番とが対応付けられた所定のパターンを含むパターンを抽出する抽出装置がある。なお、イベントとイベントが出現する順番とが対応付けられたパターンは、エピソードとも称される。よって、以下の説明では、かかるパターンをエピソードと表記する場合がある。エピソードの一例としては、次のようなエピソードが挙げられる。例えば、「人物Ａが薬Ａを服用した」というイベントＡ、及び、「人物Ａが薬Ｂを服用した」というイベントＢの出現の後に「人物Ａが発熱した」というイベントＣが出現するというエピソードが挙げられる。抽出装置は、かかるエピソードを用いて、上記の抽出を行った場合、上記のイベントＡ及びＢの出現の後に上記のイベントＣが出現するというエピソードを含むエピソードを抽出することができる。例えば、抽出装置は、上記のイベントＡ及びＢの出現とともに「人物Ａが薬Ｃを服用した」というイベントＤが出現し、イベントＡ、Ｂ及びＤの出現後に上記のイベントＣが出現するというエピソードを抽出することができる。このようなエピソードが抽出装置により抽出された場合、抽出装置のユーザは、人物Ａが発熱する前に、薬Ａ及び薬Ｂとともに薬Ｃを服用していたことを把握することができる。
【０００３】
また、上記の抽出装置の一例としては、次のような抽出装置がある。例えば、列挙木における親から子を生成しつつ、生成した子が、イベントデータが示すイベントのパターンに出現し、かつ、所定のエピソードを含むか否かを判定することで、所定のエピソードを含むエピソードを抽出する抽出装置がある。かかる抽出装置は、まず、列挙木の根となる親のエピソードに、イベントが何も設定されていない空のエピソードを設定した上で、次のような処理を行って列挙木を生成する。すなわち、抽出装置は、親のエピソードに、イベントデータに含まれるイベントを追加したエピソードを子のエピソードとすることで、子のエピソードを生成する。そして、抽出装置は、新たに生成された子のエピソードを親のエピソードとして、再び子のエピソードを生成する。このようにして、抽出装置は、所定の条件を満たすまで、繰り返し子のエピソードを生成する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−５２２０９５号公報
【特許文献２】特開平４−１２５７３４号公報
【特許文献３】特開平８−６９５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の抽出装置では、効率良く所定のエピソードを含むエピソードを抽出することができないという問題がある。これを説明すると、かかる抽出装置は、所定のエピソードを含まないような子のエピソードを生成する場合がある。このため、上記の抽出装置では、抽出されないような子のエピソードが生成されてしまう場合がある。それゆえ、上記の抽出装置では、無駄な子のエピソードが生成される。したがって、上記の抽出装置では、効率良くエピソードを抽出することができない。
【０００６】
１つの側面では、効率良く所定のパターンを含むパターンを抽出することができる抽出プログラム、抽出装置及び抽出方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本願の開示する抽出プログラムは、一つの態様において、コンピュータに、記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けたイベントデータに基づいて、次のような処理を実行させる。すなわち、抽出プログラムは、コンピュータに、複数のイベントと各イベントの出現順序とが対応付けられた第１のパターンに対してイベントを順に追加する。これにより、抽出プログラムは、コンピュータに、第１のパターンを含み、かつ、イベントデータに出現する第２のパターンを順に生成する処理を実行させる。そして、抽出プログラムは、コンピュータに、生成された第２のパターンから所定条件を満たすパターンを抽出する処理を実行させる。
【発明の効果】
【０００８】
抽出装置及び抽出方法の一つの態様によれば、効率良く所定のパターンを含むパターンを抽出することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。
【図２】図２は、イベントデータのデータ構成の一例を示す図である。
【図３】図３は、制約パターンの一例を示す図である。
【図４】図４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図５】図５は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図６】図６は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図７】図７は、図４の例に示す親エピソードに対して、直列拡張処理部により拡張処理が１回実行され、第２の算出部により第１の極小出現算出処理が１回実行された場合の算出結果の一例を示す図である。
【図８】図８は、部分極小出現の算出方法の一例を説明するための図である。
【図９】図９は、図８の例に示す場合において、子エピソードに対して実行された第１の極小出現算出処理の算出結果の一例を示す図である。
【図１０】図１０は、図９の例に示す場合において、親エピソードに対して並列拡張処理が実行された場合の一例を示す図である。
【図１１】図１１は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１２】図１２は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１３】図１３は、実施例に係る抽出処理の手順を示すフローチャートである。
【図１４】図１４は、実施例に係る直列拡張処理の手順を示すフローチャートである。
【図１５】図１５は、実施例に係る第１の極小出現算出処理の手順を示すフローチャートである。
【図１６】図１６は、実施例に係る並列拡張処理の手順を示すフローチャートである。
【図１７】図１７は、実施例に係る第２の極小出現算出処理の手順を示すフローチャートである。
【図１８】図１８は、変形例に係る抽出装置が実行する処理の一例を説明するための図である。
【図１９】図１９は、抽出プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１０】
以下に、本願の開示する抽出プログラム、抽出装置及び抽出方法の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例１】
【００１１】
［抽出装置の構成］
実施例１に係る抽出装置について説明する。図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。図１に示すように、抽出装置１０は、入力部１１と、表示部１２と、記憶部１３と、制御部１４とを有する。
【００１２】
入力部１１は、制御部１４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、後述の抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、所定のサーバから後述のイベントデータ１３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部１４に、後述の制約パターン１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００１３】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部１４ｃにより抽出された後述の制約パターン１３ｂを含むエピソードを後述の表示制御部１４ｄの制御により表示する。
【００１４】
記憶部１３は、制御部１４で実行される各種プログラムを記憶する。また、記憶部１３には、後述の取得部１４ａにより、イベントデータ１３ａ及び制約パターン１３ｂが格納される。
【００１５】
イベントデータ１３ａについて説明する。イベントデータ１３ａは、実際に出現したイベントとイベントが出現した時刻とが対応付けられたデータである。図２は、イベントデータのデータ構成の一例を示す図である。図２の例に示すイベントデータ１３ａは、時刻「１」に識別子Ａが示すイベントが出現したことを示す。また、図２の例に示すイベントデータ１３ａは、時刻「２」に識別子Ａが示すイベント及び識別子Ｂが示すイベントが出現したことを示す。また、図２の例に示すイベントデータ１３ａは、時刻「３」に識別子Ｃが示すイベントが出現したことを示す。また、図２の例に示すイベントデータ１３ａは、時刻「４」に識別子Ｂが示すイベントが出現したことを示す。また、図２の例に示すイベントデータ１３ａは、時刻「５」に識別子Ｂが示すイベント及び識別子Ｃが示すイベントが出現したことを示す。ここで、以下の説明では、識別子Ａが示すイベントを「イベントＡ」と表記する。また、同様に、識別子Ｂが示すイベントを「イベントＢ」と表記し、識別子Ｃが示すイベントを「イベントＣ」と表記する。
【００１６】
制約パターン１３ｂについて説明する。制約パターン１３ｂは、抽出されるエピソードに含まれるエピソードである。エピソードとは、イベントが出現する順番（出現順序）を有向グラフで表現したものである。例えば、制約パターン１３ｂは、複数のパートを有する。複数のパートのそれぞれには、イベントが含まれる。各パートには、順番が定められている。制約パターン１３ｂが有するＮ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係について説明する。Ｎ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係は、Ｎ番目のパートに含まれるイベントの全てのイベントが出現した後に、（Ｎ＋１）番目のパートに含まれるイベントが出現するという関係である。図３は、制約パターンの一例を示す図である。図３に示す制約パターン１３ｂは、１番目のパートにイベントＡが含まれ、２番目のパートにイベントＢが含まれる場合を示す。図３に示す制約パターン１３ｂは、１番目のパートに含まれるイベントのイベントＡが出現した後に、２番目のパートに含まれるイベントのイベントＢが出現することを示す。
【００１７】
ここで、図３に示す制約パターン１３ｂが、図２に示すイベントデータ１３ａが示すイベントパターンで出現する時間は、（１，２）、（１，４）、（１，５）、（２，４）、（２，５）で表される。ここで、制約パターン１３ｂが、イベントデータ１３ａが示すイベントパターンで出現する極小（最小）の時間は、（１，２）となる。以下の説明では、このような、エピソードやイベント単体などがイベントデータ１３ａ上で出現する極小の時間を、「極小出現」と表記する。ここで、（Ｔ１，Ｔ２）は、時刻Ｔ１から開始して、時刻Ｔ２に終了するまでの時間を示す。
【００１８】
記憶部１３は、例えば、フラッシュメモリなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部１３は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（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）３４０を有する。これら３００〜３４０の各部は、バス３５０を介して接続される。
【０１００】
ＨＤＤ３３０には、上記の実施例で示す各部１４ａ〜１４ｉと同様の機能を発揮する抽出プログラム３３０ａが予め記憶される。なお、抽出プログラム３３０ａについては、適宜分離しても良い。
【０１０１】
そして、ＣＰＵ３１０が、抽出プログラム３３０ａをＨＤＤ３３０から読み出して実行する。
【０１０２】
そして、ＨＤＤ３３０には、イベントデータ及び制約パターンが設けられる。
【０１０３】
そして、ＣＰＵ３１０は、イベントデータ及び制約パターンを読み出してＲＡＭ３４０に格納する。さらに、ＣＰＵ３１０は、ＲＡＭ３４０に格納されたイベントデータ及び制約パターンを用いて、抽出プログラムを実行する。なお、ＲＡＭ３４０に格納される各データは、常に全てのデータがＲＡＭ３４０に格納されなくともよく、全てのデータのうち処理に用いられるデータのみがＲＡＭ３４０に格納されれば良い。
【０１０４】
なお、上記した抽出プログラムについては、必ずしも最初からＨＤＤ３３０に記憶させなくともよい。
【０１０５】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。  
【０１０６】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１０７】
１０      抽出装置
１４ｃ    抽出部
１４ｆ    直列拡張処理部
１４ｇ    第２の算出部
１４ｈ    並列拡張処理部
１４ｉ    第３の算出部
【図１】
2014085729.tif 000003
【図２】
2014085729.tif 000004
【図３】
2014085729.tif 000005
【図４】
2014085729.tif 000006
【図５】
2014085729.tif 000007
【図６】
2014085729.tif 000008
【図７】
2014085729.tif 000009
【図８】
2014085729.tif 000010
【図９】
2014085729.tif 000011
【図１０】
2014085729.tif 000012
【図１１】
2014085729.tif 000013
【図１２】
2014085729.tif 000014
【図１３】
2014085729.tif 000015
【図１４】
2014085729.tif 000016
【図１５】
2014085729.tif 000017
【図１６】
2014085729.tif 000018
【図１７】
2014085729.tif 000019
【図１８】
2014085729.tif 000020
【図１９】
2014085729.tif 000021