時系列パターン発見装置、方法およびプログラム
【課題】時系列パターンを効率良く高速に発見する。
【解決手段】与えられている時系列制約条件を、当該時系列制約条件を構成するイベントを組み合わせることにより生成される部分時系列制約条件に分解し、時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、部分時系列制約条件が成立するかどうかを判定し、部分時系列制約を満たす候補イベント、候補イベント集合、候補時系列パターンに対してのみ、与えられている時系列データにおける出現頻度を計算し、出現頻度に基づいた評価値が予め指定されている閾値以上となる候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する。
【解決手段】与えられている時系列制約条件を、当該時系列制約条件を構成するイベントを組み合わせることにより生成される部分時系列制約条件に分解し、時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、部分時系列制約条件が成立するかどうかを判定し、部分時系列制約を満たす候補イベント、候補イベント集合、候補時系列パターンに対してのみ、与えられている時系列データにおける出現頻度を計算し、出現頻度に基づいた評価値が予め指定されている閾値以上となる候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列データから時系列パターンを発見する時系列パターン発見装置、方法およびプログラムに関する。
【背景技術】
【０００２】
特定の主体やその行動及び印象を表すイベントの集合が、時系列的に並べられた時系列データが多数存在している。これら時系列データの中には、特定のイベント集合の発生に引き続いて、他のイベント集合の発生を予見する時系列パターンが埋もれており、時系列パターンを発見する必要性が高まっている。
【０００３】
例えば、従来では、小さな時系列パターンの発見から開始して、小さな時系列パターンを組み合わせていくことにより、候補時系列パターンを生成、評価して、時系列パターンを効率的に発見することができる（例えば、非特許文献１参照）。
【０００４】
しかしながら、時系列データを構成するイベントの数が大きな場合、生成される候補時系列パターンの数が大きくなり過ぎるため、実用的な時間内で時系列パターンを発見するには、候補時系列パターンの数を削減する必要がある。
【非特許文献１】“Mining Sequential Patterns”, (R. Agrawal and R. Srikant, Proc. of the 11th Int. Conf. Data Engineering, 3-14, 1995)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の手法に基づいた発見の場合、対象とするイベントを予め制限したり、候補時系列パターンの評価に利用する評価値を厳しく設定したりすることにより、候補時系列パターンの数を削減する必要がある。また、複数の属性間の変化を追随する時系列パターンを発見することはできない。
【０００６】
この発明は、上述した事情を考慮してなされたものであり、対象とするイベントを制限したり、評価値を小さく設定したりしなくても、複数の属性間の変化を追随する時系列パターンを効率良く高速に発見する時系列パターン発見装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述の課題を解決するため、本発明の時系列パターン発見装置は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段と、を備えている。
【０００８】
また、本発明の時系列パターン発見装置は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、前記時系列データの１つから第１イベントを抽出する抽出手段と、前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段を備え、前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする。
【発明の効果】
【０００９】
本発明の時系列パターン発見装置、方法およびプログラムによれば、対象とするイベントを制限したり、評価値を小さく設定したりしなくても、複数の属性間の変化を追随する時系列パターンを効率良く高速に発見することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら本発明の実施形態に係る時系列パターン発見装置、方法およびプログラムについて詳細に説明する。
本実施形態の時系列パターン発見装置は、図１に示すように、時系列制約条件格納部１０１、時系列制約条件分解部１０２、時系列データ格納部１０３、候補時系列パターン生成部１０４、部分時系列制約条件判定部１０５、候補時系列パターン評価部１０６、候補時系列パターン判定部１０７、時系列パターン格納部１０８を備えている。
【００１１】
時系列制約条件格納部１０１は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している。時系列制約条件の一例は後に図４を参照して説明する。
【００１２】
時系列制約条件分解部１０２は、時系列制約条件格納部１０１に格納されている時系列制約条件から未抽出の時系列制約条件を１つ取り出し、取り出した時系列制約条件を分解して、この時系列制約条件に含まれるより小さな部分時系列制約条件を生成する。また、生成された部分時系列制約条件を、未抽出の時系列制約条件として、時系列制約条件格納部１０１に格納する。例えば、未抽出の時系列制約条件が２つ以上の要素から構成されている場合には、時系列制約条件を最後の２つの要素からなる要素集合と残りの要素集合に分割し、残りの要素と最後の２つの要素の１つを順に並べた部分時系列制約と、残りの要素と最後の２つの要素のもう一方の要素を順に並べた部分時系列制約とを生成して、当該２つの部分時系列制約を未抽出な時系列制約条件として、時系列制約条件格納部１０１に格納する。また、未抽出の時系列制約が１つの要素から構成されている場合には、時系列制約条件を最後の２つのイベントからなるイベント集合と残りのイベント集合に分割し、残りのイベント集合と最後の２つのイベント集合に含まれる１つのイベントを組み合わせた部分時系列制約と、残りのイベント集合と２つのイベント集合に含まれるもう一方のイベントを組み合わせた部分時系列制約とを生成して、当該２つの部分時系列制約を未抽出な時系列制約条件として、時系列制約条件格納部１０１に格納する。
【００１３】
時系列データ格納部１０３は、要素間の時系列的な関係を示すデータである時系列データを複数格納している。
【００１４】
候補時系列パターン生成部１０４は、時系列データ格納部１０３に格納されている時系列データの中から、時系列データを１つ取り出し、取り出した時系列データの中から未抽出のイベントを１つ取り出して、候補イベントとする。
【００１５】
また、候補時系列パターン生成部１０４は、時系列パターン格納部１０８に格納されている特徴イベントの集合の中から、指定されたイベント数に一致し、未抽出のイベント集合の組み合わせである、２つのイベント集合をイベント集合対として取り出し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成し、そうでない場合には、当該イベント集合対からは候補特徴イベント集合を生成できないと判定する。候補時系列パターン生成部１０４は、例えば、抽出されたイベント集合対が指定されている後述する条件１、条件２を満足するかどうかを判定し、満足する場合には、このイベント集合対の一方のイベント集合に、もう一方のイベント集合の最後に位置するイベントを追加することにより、候補特徴イベント集合を生成する。
【００１６】
さらに、候補時系列パターン生成部１０４は、指定されたイベント数に一致する未抽出のイベント集合対が存在しない場合に、時系列パターン格納部１０８に格納されている時系列パターンの中に、指定されたイベント数より１だけ大きなイベントからなる、要素数が１の時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されたイベントの個数に１を加算する。
【００１７】
またさらに、候補時系列パターン生成部１０４は、指定された要素数を持つ時系列パターンの中から、未抽出の時系列パターンの組を時系列パターン対として取り出し、候補時系列パターン生成部１０４は、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する。候補時系列パターン生成部１０４は、例えば、時系列パターン対が指定されている後述する条件３、条件４を満足しているかどうかを判定し、満足している場合には、時系列パターンの第１の時系列パターンに、第２の時系列パターンの最後の要素を付け加えることにより、候補時系列パターンを生成する。そして、候補時系列パターン生成部１０４は、指定された要素数に一致する未抽出の時系列パターン対が存在しない場合に、指定された要素数よりも１だけ大きな要素からなる時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されている要素数に１を加算する。
【００１８】
部分時系列制約条件判定部１０５は、抽出された候補イベントを時系列制約条件分解部１０２に設定されている部分時系列制約条件に適用することにより、候補イベントに一致する属性値が設定されているかどうかを判定する。
【００１９】
また、部分時系列制約条件判定部１０５は、生成した候補イベント集合を、部分時系列制約条件に適用し、この候補イベント集合に一致する部分時系列制約条件が存在するかどうかを判定する。
【００２０】
さらに、部分時系列制約条件判定部１０５は、時系列制約条件分解部１０２に設定されている部分時系列制約条件を参照することにより、生成された候補時系列パターンがこの部分時系列制約条件に一致するかどうかを判定する。
【００２１】
候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補イベントを、時系列データ格納部１０３に格納されている時系列データに適用することにより、この候補イベントを含む時系列データの個数を計算し、この候補イベントの出現頻度とする。ただし、時系列データが同一のイベントを複数含んでいるとしても、その個数は１個と計算することにする。また、式に基づいて、このイベントの支持度（評価値）を計算する。
【００２２】
また、候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補イベント集合を時系列データに適用することにより、候補イベント集合を含む時系列データの個数を出現頻度として計算する。また、式によりこの候補イベント集合の支持度を計算する。
【００２３】
さらに、候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補時系列パターンを時系列データに適用することにより、この候補時系列パターンを含む時系列データの個数を出現頻度として求め、後述する式により、この候補時系列パターンの支持度を計算する。
【００２４】
候補時系列パターン判定部１０７が、部分時系列制約条件を満たすイベントの支持度と予め指定されている最小支持度（閾値）を比較することにより、指定した最小支持度以上になるかどうかを判定する。このとき、最小支持度以上になる場合には、この候補イベントを特徴イベントとし、候補時系列パターン判定部１０７が特徴イベントを時系列パターン格納部１０８に格納する。
【００２５】
また、候補時系列パターン判定部１０７が、候補イベント集合の支持度が指定した最小支持度以上になるかどうかを判定し、支持度が最小支持度以上となる場合に、この候補イベント集合を特徴イベント集合とし、候補時系列パターン判定部１０７が、特徴イベント集合を時系列パターン格納部１０８に格納する。
さらに、候補時系列パターン判定部１０７が、候補時系列パターンの支持度が最小支持度以上になっているかどうかを判定し、支持度が最小支持度以上になっている場合に、この候補時系列パターンを時系列パターンとし、候補時系列パターン判定部１０７が時系列パターンを時系列パターン格納部１０８に格納する。
【００２６】
次に、図１の処理の流れの一例について図２を参照して説明する。
（ステップＳ２０１）時系列制約条件分解部１０２が、時系列制約条件格納部１０１に格納されている時系列制約条件から未抽出の時系列制約条件を１つ取り出して設定する。このとき、取り出す時系列制約条件が存在しない場合には、ステップＳ２０５へと進み、一方、取り出す時系列制約条件が存在する場合には、ステップＳ２０２へと進む。
【００２７】
（ステップＳ２０２）時系列制約条件分解部１０２は、取り出した時系列制約条件を分解して、この時系列制約条件に含まれる、より小さな部分時系列制約条件を生成する。このとき、部分時系列制約条件の生成に成功する場合には、ステップＳ２０３へと進み、一方、生成に失敗した場合には、ステップＳ２０４へと進む。
【００２８】
例えば、時系列データを構成するイベントが図３に示すように与えられているとする。ただし、これらのイベントにおいて、“／”で区切られた前側の部分が属性、後ろ側の部分が属性値を表すものとし、属性と属性値の組によって各イベントが構成されているとする。属性とはデータの特徴を表す性質のことであり、属性値とは特定のデータの性質の値を示す。例えば、「血圧／正常」のイベントでは、属性が血圧であり、属性値が正常である。このイベントは血圧のデータは正常であることを示している。
【００２９】
また、図４に示すような時系列制約条件が与えられているとする。ただし、“（）”で括られたイベントは同一の単位時間帯において発生したイベントを表すとし、“→”によって時間が経過したことを表すとする。したがって、図４の例の場合、３単位時間に跨った時系列制約条件が与えられている。一方、ｘ，ｙは与えられている属性のうちの異なる属性を表しているとする。したがって、図３のようなイベントが与えられている場合には、ｘ，ｙは「血圧」、「塩分」、「糖分」のうちのいずれかの属性に対応することになる。
【００３０】
このとき、時系列制約条件分解部１０２は、時間的に後方に位置する１以上の要素を時系列制約条件から取り出す。また、時系列制約条件分解部１０２は、取り残された要素に、取り出した一方の要素を付加した部分時系列制約条件と、取り出したもう一方の要素を付加した部分時系列制約条件とを生成する。具体例を挙げる。図４の時系列制約条件の場合、３要素からなっているため、共通する要素は１番目の要素だけである。したがって、時系列制約条件分解部１０２は、図５に示すような１番目の要素と２番目の要素、１番目の要素と３番目の要素からなる２つの部分時系列制約条件を生成して、ステップＳ２０３へと進む。
【００３１】
また、図５の上位に示すように時系列制約条件が与えられているとする。このとき、共通する要素は存在しないため、時系列制約条件分解部１０２は図６に示すような１番目の要素と２番目の要素からなる部分時系列制約条件を生成して、ステップＳ２０３へと進む。同様に、図５の下位に示す時系列制約条件からは、図７に示す部分時系列制約条件を生成する。
【００３２】
さらに、図６の上位に示すように時系列制約条件が与えられているとする。このとき、この時系列制約条件には、１つの要素しか含まれていないため、時系列制約条件分解部１０２は、辞書順に並べられたイベントの中からその後方にある２つのイベントを取り出し、残りのイベントと取り出したイベントのそれぞれからなる２つの部分要素を生成する。図６の上位に示す時系列制約条件の要素の場合、２つのイベントしか含まれていないため、各イベントに対応する部分要素「ｘ／正常」、「ｙ／正常」を生成する。これらの部分要素の場合、部分要素に含まれるイベントの個数が１個となり、属性の違いを考慮する必要がないため、属性の違いを表現するために導入されている変数ｘ、ｙを部分要素から取り除く。したがって、この場合には図８に示すような部分要素が部分時系列制約条件として抽出されて、ステップＳ２０３へと進む。同様に、図６の下位に示す時系列制約条件からは、時系列制約条件分解部１０２は図９に示すような部分時系列制約条件を抽出する。また、図７の下位に示す時系列制約条件からは、時系列制約条件分解部１０２は図１０に示すような部分時系列制約条件を抽出する。
【００３３】
一方、１つのイベントからなる時系列制約条件を選択した場合、時系列制約条件分解部１０２は、この時系列制約条件をこれ以上分解することができないため、時系列制約条件の分解に失敗したと判定して、ステップＳ２０４へと進む。
【００３４】
（ステップＳ２０３）時系列制約条件分解部１０２が、生成された部分時系列制約条件が既に抽出されているかどうかを判定し、抽出されていない場合に、この部分時系列制約条件を未処理の部分時系列制約条件として設定する。
【００３５】
例えば、図４に示す時系列制約条件を分解しているとすれば、図５に示す部分時系列制約条件が生成されている。このとき、各部分時系列制約条件はまだ抽出されていない部分時系列制約条件であるため、時系列制約条件分解部１０２は各部分時系列制約条件を未処理の部分時系列制約条件として設定する。
【００３６】
一方、図５の下位に示す時系列制約条件を分解しているとすれば、図７に示す部分時系列制約条件が生成されている。このとき、図５の上位に示す部分時系列制約条件が既に処理済みであるとすれば、図７に示す部分時系列制約条件のうち、上位に示す部分時系列制約条件「（ｘ／正常，ｙ／正常）」は既に設定済みである。このため、時系列制約条件分解部１０２は下位に示す部分時系列制約条件「（ｘ／異常，ｙ／要注意）」だけを未処理の部分時系列制約条件として設定する。
【００３７】
（ステップＳ２０４）時系列制約条件分解部１０２が、設定されている未処理の部分時系列制約条件の中から、部分時系列制約条件に含まれている要素の数が最も多い部分時系列制約条件を１つ取り出して、ステップＳ２０２へと戻る。一方、取り出す未処理の部分時系列制約条件が存在しない場合には、ステップＳ２０１へと進む。
【００３８】
例えば、図１１に示すように未処理の部分時系列制約条件が設定されている場合には、時系列制約条件分解部１０２は、要素数が多い部分時系列制約条件「（ｘ／正常，ｙ／正常）→（ｘ／異常，ｙ／要注意）」を取り出して、ステップＳ２０２へと戻る。
【００３９】
（ステップＳ２０５）候補時系列パターン生成部１０４が、時系列データ格納部１０３に格納されている時系列データの中から、時系列データを１つ取り出し、ステップＳ２０６に進み、一方、時系列データ格納部１０３に格納されている時系列データを全て取り出した場合にはステップＳ２１１に進む。
【００４０】
（ステップＳ２０６）候補時系列パターン生成部１０４が、取り出した時系列データの中から未抽出のイベントを１つ取り出して、候補イベントとする。このとき、取り出す候補イベントが存在する場合には、ステップＳ２０７へと進み、一方、取り出すイベントが存在しない場合には、ステップＳ２０５へと処理を戻す。
【００４１】
例えば、図１３のｄ１の時系列データが候補時系列パターン生成部１０４によって読み込まれているとする。このとき、時系列データの左側から右側にイベントを順に取り出すことにすれば、候補イベント「血圧／正常」を最初に取り出すことになり、ステップＳ２０７へと進む。また、最後のイベント「糖分／異常」を取り出した後で、ステップＳ２０６を実施する場合に、ステップＳ２０５へと進むことになる。
【００４２】
（ステップＳ２０７）部分時系列制約条件判定部１０５が、抽出された候補イベントを時系列制約条件分解部１０２に設定されている部分時系列制約条件に適用することにより、この候補イベントに一致する属性値が設定されているかどうかを判定する。このとき、このイベントが部分時系列制約条件に設定されている場合には、ステップＳ２０８へと進み、一方、設定されていない場合には、ステップＳ２０５へと処理を戻す。
【００４３】
例えば、部分時系列制約条件として、図１２に示す部分時系列制約条件が設定されているとし、イベントとして、「血圧／正常」が取り出されているとする。このとき、属性値「正常」はこの部分時系列制約条件に設定されているため、ステップＳ２０８へと進み、一方、イベントとして、「糖分／未検査」が取り出されているとすれば、属性値「未検査」はこの部分時系列制約条件に設定されていないため、ステップＳ２０５へと戻る。
【００４４】
（ステップＳ２０８）候補時系列パターン評価部１０６が、部分時系列制約条件を満たす候補イベントを、時系列データ格納部１０３に格納されている時系列データに適用することにより、この候補イベントを含む時系列データの個数を計算し、この候補イベントの出現頻度とする。ただし、時系列データが同一のイベントを複数含んでいるとしても、その個数は１個と計算することにする。また、次式（１）に基づいて、このイベントの支持度を計算する。
【００４５】
支持度＝イベントの出現頻度／時系列データの個数・・・（１）
例えば、図１３に示す時系列データが時系列データ格納部１０３に格納されているとし、部分時系列制約条件を満たすイベントとして「血圧／正常」が与えられているとする。このとき、各時系列データは、このイベントを含んでいるため、このイベントの出現頻度は３となる。また、時系列データの個数は３であるため、このイベントの支持度は１．０（＝３／３）となる。
【００４６】
一方、部分時系列制約条件を満たすイベントとして「塩分／異常」が与えられているとすれば、このイベントを含む時系列データは存在しないため、このイベントの出現頻度は０となる。したがって、このイベントの支持度は０．０（＝０／３）となる。
【００４７】
（ステップＳ２０９）候補時系列パターン判定部１０７が、部分時系列制約条件を満たすイベントの支持度と予め指定されている最小支持度を比較することにより、指定した最小支持度以上になるかどうかを判定する。このとき、最小支持度以上になる場合には、この候補イベントを特徴イベントとして、ステップＳ２１０へと進み、一方、最小支持度より小さい場合には、ステップＳ２０５へと戻る。
【００４８】
例えば、最小支持度として０．９が与えられており、部分時系列制約条件を満たすイベントとして「血圧／正常」が与えられているとすれば、このイベントの支持度は１．０であり０．９以上となるため、この候補イベントを特徴イベントとしてステップＳ２１０へと進む。一方、部分時系列制約条件を満たすイベントとして「塩分／異常」が与えられているとすれば、このイベントの支持度は０であり０．９よりも小さくなるため、ステップＳ２０５へと戻る。
【００４９】
（ステップＳ２１０）候補時系列パターン判定部１０７が特徴イベントを時系列パターン格納部１０８に格納する。例えば、図１４に示す特徴イベントが、イベント数が１個からなる時系列パターンとして時系列パターン格納部１０８に格納される。
【００５０】
（ステップＳ２１１）候補時系列パターン生成部１０４がイベント数の初期値として例えば１を設定する。
【００５１】
（ステップＳ２１２）候補時系列パターン生成部１０４が、時系列パターン格納部１０８に格納されている特徴イベントの集合の中から、指定されたイベント数に一致し、未抽出のイベント集合の組み合わせである、２つのイベント集合をイベント集合対として取り出す。ただし、同一のイベント集合を取り出すことも可能とする。このとき、イベント集合対が抽出される場合には、ステップＳ２１３へと進み、一方、抽出されない場合には、ステップＳ２１８へと進む。
【００５２】
（ステップＳ２１３）候補時系列パターン生成部１０４が、抽出されたイベント集合対が下記の条件１及び条件２を満足するかどうかを判定し、満足する場合には、このイベント集合対の一方のイベント集合に、もう一方のイベント集合の最後に位置するイベントを追加することにより、候補イベント集合を生成して、ステップＳ２１４へと進む。一方、満足しない場合には、ステップＳ２１２へと戻る。
条件１．イベント集合の最後に位置付けられているイベントを除いた残りのイベント部分集合が一致している。
条件２．最後に位置付けられているイベントの属性が一致していない。
【００５３】
ただし、イベント集合に含まれる各イベントの属性は、辞書順などの基準に基づいて整列されているとし、１個のイベントからなる特徴イベントは特徴イベント集合の特殊な例であるとする。
【００５４】
例えば、属性が、「血圧、塩分、糖分」といった順に整列されているとする。このとき、イベント数として１が与えられているとし、１つのイベントからなるイベント集合「血圧／正常」、「塩分／正常」が、イベント集合対として与えられているとする。イベント数が１の場合、条件１は常に成立している。加えて、このイベント集合対に対しては、属性が「血圧」、「塩分」と異なっているため、条件２も成立している。このため、「（血圧／正常，塩分／正常）」が候補イベント集合として生成され、ステップＳ２１４へと進む。
また、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／正常，糖分／正常）」が、イベント集合対として与えられているとする。このイベント集合対においては、２番目のイベントを除いたイベント集合が「血圧／正常」と一致しているとともに、２番目のイベントの属性が「塩分」、「糖分」と異なっているため、条件１、条件２が成立する。このため、「（血圧／正常，塩分／正常，糖分／正常）」が候補イベント集合として得られ、ステップＳ２１４へと進む。
【００５５】
一方、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／要注意，塩分／正常）」が、与えられているとする。このイベント集合対においては、２番目のイベントを除いたイベント集合が「血圧／正常」、「血圧／要注意」と一致しておらず、条件１が成立していない。このため、候補イベント集合を生成することができず、ステップＳ２１２へと戻る。
また、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／正常，塩分／正常）」が、与えられているとする。このイベント集合対においては、２番目のイベントにおける属性がともに「塩分」となっているため、条件２が成立していない。このため、候補イベント集合を生成することができず、ステップＳ２１２へと戻る。
【００５６】
（ステップＳ２１４）部分時系列制約条件判定部１０５は、生成された候補イベント集合を、部分時系列制約条件に適用し、この候補イベント集合に一致する部分時系列制約条件が存在するかどうかを判定する。このとき、この部分時系列制約条件が存在する場合には、ステップＳ２１５へと進み、一方、存在しない場合には、ステップＳ２１２へと戻る。
【００５７】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合には、図１２に示す部分時系列制約条件「（ｘ／正常，ｙ／正常）」に一致しているため、ステップＳ２１５へと進む。
【００５８】
一方、「（血圧／正常，糖分／異常）」が候補イベント集合として与えられている場合には、一致する部分時系列制約条件が図１２の中に存在しないため、ステップＳ２１２へと戻る。また、「（血圧／正常，塩分／正常，糖分／正常）」が候補イベント集合として与えられている場合には、一致する部分時系列制約条件が図１２の中に存在しないため、ステップＳ２１２へと戻る。
【００５９】
（ステップＳ２１５）候補時系列パターン評価部１０６が、生成された候補イベント集合を時系列データに適用することにより、候補イベント集合を含む時系列データの個数を出現頻度として計算する。また、式（１）によりこの候補イベント集合の支持度を計算する。
【００６０】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合、図１３に示す各時系列データは、この候補イベント集合を含んでいるため、出現頻度は３となる。また、その支持度は１．０（＝３／３）となる。
【００６１】
一方、「（血圧／要注意，糖分／異常）」が候補イベント集合として与えられている場合、図１３に示す各時系列データは、この候補イベント集合を含んでいないため、出現頻度は０となる。また、その支持度は０．０（＝０／３）となる。
【００６２】
（ステップＳ２１６）候補時系列パターン判定部１０７が、候補イベント集合の支持度が指定した最小支持度以上になるかどうかを判定し、最小支持度以上となる場合に、この候補イベント集合を特徴イベント集合として、ステップＳ２１７へと進み、一方、最小支持度よりも小さくなる場合には、ステップＳ２１２へと戻る。
【００６３】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合、ステップＳ２０９での計算と同様にして、その支持度は１．０となり、最小支持度である０．９以上となるため、この候補イベント集合を特徴イベント集合として、ステップＳ２１７へと進む。
【００６４】
一方、「（血圧／要注意，糖分／異常）」が候補イベント集合として与えられている場合、ステップＳ２０９での計算と同様にして、その支持度は０．０となり、最小支持度である０．９よりも小さくなるため、ステップＳ２１２へと戻る。
【００６５】
（ステップＳ２１７）候補時系列パターン判定部１０７が、特徴イベント集合を時系列パターン格納部１０８に格納する。
例えば、図１５に示す特徴イベント集合が、要素数が１で、その中に含まれるイベント数が２である時系列パターンとして、時系列パターン格納部１０８に格納される。
【００６６】
（ステップＳ２１８）候補時系列パターン生成部１０４が、時系列パターン格納部１０８に格納されている時系列パターンの中に、指定されたイベント数より１だけ大きなイベントからなる、要素数が１の時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されたイベントの個数に１を加算し、ステップＳ２１２へと戻り、一方、存在しない場合には、ステップＳ２１９へと進む。
【００６７】
（ステップＳ２１９）候補時系列パターン生成部１０４が要素数の初期値として例えば１を設定する。
【００６８】
（ステップＳ２２０）候補時系列パターン生成部１０４が、指定された要素数を持つ時系列パターンの中から、未抽出の時系列パターンの組を時系列パターン対として取り出す。このとき、取り出す時系列パターン対が存在しない場合には、ステップＳ２２６へと進み、一方、存在する場合には、ステップＳ２２１へと進む。ただし、取り出される２つの時系列パターンは同一の時系列パターンであってもよいとする。また、時系列パターンが取り出される順序が異なる時系列パターンの組は、異なる時系列パターンの組であるとする。
【００６９】
（ステップＳ２２１）候補時系列パターン生成部１０４が、時系列パターン対が下記の条件３、条件４を満足しているかどうかを判定し、満足している場合には、時系列パターンの第１の時系列パターンに、第２の時系列パターンの最後の要素を付け加えることにより、候補時系列パターンを生成して、ステップＳ２２２へと進み、一方、満足していない場合には、ステップＳ２２０へと戻る。
条件３．最後の要素を除いた部分時系列パターンが一致している。
条件４．最後の要素に含まれるイベントの属性集合が一致している。
【００７０】
例えば、要素数が１である時系列パターン対として、「（血圧／正常，塩分／正常）」、「（血圧／要注意，塩分／正常）」が取り出されているとする。要素数が１の場合、条件３は常に成立している。加えて、最後の要素に含まれるイベントの属性集合が「血圧、塩分」と一致しているため、条件４が成立する。このため、この時系列パターン対から候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」を生成して、ステップＳ２２２へと進む。
【００７１】
また、要素数が２である時系列パターン対として、「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」、「（血圧／正常，塩分／正常）→（血圧／異常，塩分／要注意）」が取り出されているとする。この時系列パターンにおいては、最後の要素を除いた部分時系列パターン「（血圧／正常，塩分／正常）」が一致しており、条件３が成立するとともに、最後の要素に含まれるイベントの属性集合が「血圧、塩分」と一致しているため、条件４が成立する。このため、この時系列パターン対から候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）→（血圧／異常，塩分／要注意）」を生成して、ステップＳ２２２へと進む。
【００７２】
一方、要素数が１である時系列パターン対として、「（血圧／正常，塩分／正常）」、「（血圧／要注意，糖分／正常）」が取り出されているとする。この時系列パターンにおいては、最後の要素に含まれるイベントの属性集合がそれぞれ「血圧、塩分」、「血圧、糖分」となり、一致していないため、条件４が成立していない。このため、ステップＳ２２０へと戻る。
【００７３】
（ステップＳ２２２）部分時系列制約条件判定部１０５が時系列制約条件分解部１０２に設定されている部分時系列制約条件を参照することにより、生成された候補時系列パターンがこの部分時系列制約条件に一致するかどうかを判定する。このとき、一致する部分時系列制約条件が存在する場合には、ステップＳ２２３へと進み、一方、存在しない場合には、ステップＳ２２０へと戻る。
【００７４】
例えば、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」が生成されている場合、この候補時系列パターンは、図１２に示す部分時系列制約条件のうち、「（ｘ／正常，ｙ／正常）→（ｘ／要注意，ｙ／正常）」に一致しているため、ステップＳ２２３へと進む。
【００７５】
一方、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／正常，塩分／正常）」が生成されている場合、この候補時系列パターンに一致する部分時系列制約条件は、図１２の中には存在しないため、ステップＳ２２０へと戻る。
【００７６】
（ステップＳ２２３）候補時系列パターン評価部１０６が、候補時系列パターンを含む時系列データの個数を出現頻度として求め、式（１）により、この候補時系列パターンの支持度を計算する。
【００７７】
例えば、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」が与えられている場合、この候補時系列パターンは図１３の各時系列データに含まれているため、その出現頻度は３となる。また、その支持度は１．０（＝３／３）となる。
【００７８】
また、候補時系列パターンとして「（血圧／正常，糖分／正常）→（血圧／要注意，糖分／正常）」が与えられている場合、この候補時系列パターンは図１３のｄ１，ｄ３の時系列データに含まれているため、その出現頻度は２となる。また、その支持度は０．６７（＝２／３）となる。
【００７９】
（ステップＳ２２４）候補時系列パターン判定部１０７が候補時系列パターンの支持度が最小支持度以上になっているかどうかを判定する。このとき、この候補時系列パターンの支持度が最小支持度以上になっている場合に、この候補時系列パターンを時系列パターンとして、ステップＳ２２５へと進み、一方、最小支持度よりも小さくなっている場合に、ステップＳ２２０へと戻る。
【００８０】
例えば、候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」の場合、その支持度が１．０であり、最小支持度である０．９以上となるため、この候補時系列パターンを時系列パターンとして、ステップＳ２２５へと進む。
【００８１】
一方、候補時系列パターン「（血圧／正常，糖分／正常）→（血圧／要注意，糖分／正常）」の場合、その支持度が０．６７であり、最小支持度である０．９よりも小さくなるため、ステップＳ２２０へと戻る。
【００８２】
（ステップＳ２２５）候補時系列パターン判定部１０７が時系列パターンを時系列パターン格納部１０８に格納し、ステップＳ２２０へと戻る。
【００８３】
例えば、要素数が２となる時系列パターンとして、図１６に示す時系列パターンが格納される。また、要素数が３となる時系列パターンとして、図１７に示す時系列パターンが格納される。
【００８４】
（ステップＳ２２６）候補時系列パターン生成部１０４が、指定されている要素数よりも１だけ大きな要素からなる時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されている要素数に１を加算し、ステップＳ２２０へと戻る一方、存在しない場合には、本処理を終了する。
【００８５】
このような処理を実施することにより、指定された時系列制約条件を満たす、最小支持度以上の支持度となる、すべての時系列パターンを発見することができる。すなわち、例えば、図１３の時系列データから、図４の時系列制約条件を満たす、最小支持度である０．９以上の支持度を持つ時系列パターンとして、図１７に示す時系列パターンを発見することができる。
【００８６】
このように、属性と属性値によって特徴付けられるイベントによって構成される時系列データから時系列パターンを発見する方法において、利用者の興味のある構造を含んだ時系列パターンを効率よく高速に発見することができる。
【００８７】
なお、本時系列制約条件に基づいた時系列パターン発見装置は、上述した実施形態に限定するものではない。例えば、候補イベント、候補イベント集合、候補時系列パターンを、特徴イベント、特徴イベント集合、時系列パターンとみなすかどうかを判定するのに、本実施形態では支持度を利用しているが、参考文献“Sequential Mining Method based on a New Criterion”, (Shigeaki Sakurai, Youichi Kitahara, and Ryohei Orihara, Proc. the 10th IASTED Int. Conf. on Artificial Intelligence and Soft Computing, 544-045, 2006）に記載の系列興味度を利用してもよい。
【００８８】
また、実施形態においては、時系列制約条件格納部１０１に格納されている時系列制約条件を１つに限定しているが、複数の時系列制約条件を設定することもできる。また、時系列制約条件における要素数や各要素に含まれるイベント数を、それぞれ３、２としているが、この要素を任意の自然数とすることができる。加えて、イベントを構成する各属性の属性値を、すべて同一の値としているが、一部の属性値だけを同一の値にしたり、特定の属性に関しては全く異なる属性値を指定したりすることもできる。この他、本発明の趣旨を逸脱しない範囲において、種々変形して時系列制約条件に基づいた時系列パターン発見装置を構成することができる。
【００８９】
以上に示した実施形態によれば、部分時系列制約条件に基づいた判定を行うことにより、候補時系列パターンに対して実施する必要があった、時系列データを用いた出現頻度の評価回数を大幅に削減することができ、実用的な時間内で時系列パターンを発見することができる。また、複数の属性における属性値間の時系列的な関係を考慮しているため、複数の属性の属性値間の関係を内在する時系列パターンを発見することができる。加えて、利用者が注目していた構造を持った時系列パターンだけを発見することができるため、利用者にとって興味のない時系列パターンが多数発見されることを回避することができる。
【００９０】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の時系列パターン発見装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の時系列パターン発見装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合又は読み込む場合はネットワークを通じて取得又は読み込んでもよい。
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【００９１】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【００９２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９３】
【図１】実施形態の時系列パターン発見装置のブロック図。
【図２】図１の時系列パターン発見装置の動作の一例を示すフローチャート。
【図３】時系列データを構成するイベントの一例を示す図。
【図４】時系列制約条件の一例を示す図。
【図５】ステップＳ２０２で図１の時系列制約条件分解部が図４から生成する部分時系列制約条件の一例を示す図。
【図６】ステップＳ２０２で図１の時系列制約条件分解部が図５の上位から生成する部分時系列制約条件の一例を示す図。
【図７】ステップＳ２０２で図１の時系列制約条件分解部が図５の下位から生成する部分時系列制約条件の一例を示す図。
【図８】ステップＳ２０２で図１の時系列制約条件分解部が図６の上位から生成する部分時系列制約条件の一例を示す図。
【図９】ステップＳ２０２で図１の時系列制約条件分解部が図６の下位から生成する部分時系列制約条件の一例を示す図。
【図１０】ステップＳ２０２で図１の時系列制約条件分解部が図７の下位から生成する部分時系列制約条件の一例を示す図。
【図１１】未処理の部分時系列制約条件の一例を示す図。
【図１２】図１の時系列制約条件分解部に設定されている部分時系列制約条件の一例を示す図。
【図１３】図１の時系列データ格納部に格納されている時系列データの一例を示す図。
【図１４】図１の時系列パターン格納部に格納されている時系列パターンの一例を示す図。
【図１５】ステップＳ２１７で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【図１６】ステップＳ２２５で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【図１７】ステップＳ２２５で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【符号の説明】
【００９４】
１０１・・・時系列制約条件格納部、１０２・・・時系列制約条件分解部、１０３・・・時系列データ格納部、１０４・・・候補時系列パターン生成部、１０５・・・部分時系列制約条件判定部、１０６・・・候補時系列パターン評価部、１０７・・・候補時系列パターン判定部、１０８・・・時系列パターン格納部。
【技術分野】
【０００１】
本発明は、時系列データから時系列パターンを発見する時系列パターン発見装置、方法およびプログラムに関する。
【背景技術】
【０００２】
特定の主体やその行動及び印象を表すイベントの集合が、時系列的に並べられた時系列データが多数存在している。これら時系列データの中には、特定のイベント集合の発生に引き続いて、他のイベント集合の発生を予見する時系列パターンが埋もれており、時系列パターンを発見する必要性が高まっている。
【０００３】
例えば、従来では、小さな時系列パターンの発見から開始して、小さな時系列パターンを組み合わせていくことにより、候補時系列パターンを生成、評価して、時系列パターンを効率的に発見することができる（例えば、非特許文献１参照）。
【０００４】
しかしながら、時系列データを構成するイベントの数が大きな場合、生成される候補時系列パターンの数が大きくなり過ぎるため、実用的な時間内で時系列パターンを発見するには、候補時系列パターンの数を削減する必要がある。
【非特許文献１】“Mining Sequential Patterns”, (R. Agrawal and R. Srikant, Proc. of the 11th Int. Conf. Data Engineering, 3-14, 1995)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の手法に基づいた発見の場合、対象とするイベントを予め制限したり、候補時系列パターンの評価に利用する評価値を厳しく設定したりすることにより、候補時系列パターンの数を削減する必要がある。また、複数の属性間の変化を追随する時系列パターンを発見することはできない。
【０００６】
この発明は、上述した事情を考慮してなされたものであり、対象とするイベントを制限したり、評価値を小さく設定したりしなくても、複数の属性間の変化を追随する時系列パターンを効率良く高速に発見する時系列パターン発見装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述の課題を解決するため、本発明の時系列パターン発見装置は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段と、を備えている。
【０００８】
また、本発明の時系列パターン発見装置は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、前記時系列データの１つから第１イベントを抽出する抽出手段と、前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段を備え、前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする。
【発明の効果】
【０００９】
本発明の時系列パターン発見装置、方法およびプログラムによれば、対象とするイベントを制限したり、評価値を小さく設定したりしなくても、複数の属性間の変化を追随する時系列パターンを効率良く高速に発見することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら本発明の実施形態に係る時系列パターン発見装置、方法およびプログラムについて詳細に説明する。
本実施形態の時系列パターン発見装置は、図１に示すように、時系列制約条件格納部１０１、時系列制約条件分解部１０２、時系列データ格納部１０３、候補時系列パターン生成部１０４、部分時系列制約条件判定部１０５、候補時系列パターン評価部１０６、候補時系列パターン判定部１０７、時系列パターン格納部１０８を備えている。
【００１１】
時系列制約条件格納部１０１は、データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している。時系列制約条件の一例は後に図４を参照して説明する。
【００１２】
時系列制約条件分解部１０２は、時系列制約条件格納部１０１に格納されている時系列制約条件から未抽出の時系列制約条件を１つ取り出し、取り出した時系列制約条件を分解して、この時系列制約条件に含まれるより小さな部分時系列制約条件を生成する。また、生成された部分時系列制約条件を、未抽出の時系列制約条件として、時系列制約条件格納部１０１に格納する。例えば、未抽出の時系列制約条件が２つ以上の要素から構成されている場合には、時系列制約条件を最後の２つの要素からなる要素集合と残りの要素集合に分割し、残りの要素と最後の２つの要素の１つを順に並べた部分時系列制約と、残りの要素と最後の２つの要素のもう一方の要素を順に並べた部分時系列制約とを生成して、当該２つの部分時系列制約を未抽出な時系列制約条件として、時系列制約条件格納部１０１に格納する。また、未抽出の時系列制約が１つの要素から構成されている場合には、時系列制約条件を最後の２つのイベントからなるイベント集合と残りのイベント集合に分割し、残りのイベント集合と最後の２つのイベント集合に含まれる１つのイベントを組み合わせた部分時系列制約と、残りのイベント集合と２つのイベント集合に含まれるもう一方のイベントを組み合わせた部分時系列制約とを生成して、当該２つの部分時系列制約を未抽出な時系列制約条件として、時系列制約条件格納部１０１に格納する。
【００１３】
時系列データ格納部１０３は、要素間の時系列的な関係を示すデータである時系列データを複数格納している。
【００１４】
候補時系列パターン生成部１０４は、時系列データ格納部１０３に格納されている時系列データの中から、時系列データを１つ取り出し、取り出した時系列データの中から未抽出のイベントを１つ取り出して、候補イベントとする。
【００１５】
また、候補時系列パターン生成部１０４は、時系列パターン格納部１０８に格納されている特徴イベントの集合の中から、指定されたイベント数に一致し、未抽出のイベント集合の組み合わせである、２つのイベント集合をイベント集合対として取り出し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成し、そうでない場合には、当該イベント集合対からは候補特徴イベント集合を生成できないと判定する。候補時系列パターン生成部１０４は、例えば、抽出されたイベント集合対が指定されている後述する条件１、条件２を満足するかどうかを判定し、満足する場合には、このイベント集合対の一方のイベント集合に、もう一方のイベント集合の最後に位置するイベントを追加することにより、候補特徴イベント集合を生成する。
【００１６】
さらに、候補時系列パターン生成部１０４は、指定されたイベント数に一致する未抽出のイベント集合対が存在しない場合に、時系列パターン格納部１０８に格納されている時系列パターンの中に、指定されたイベント数より１だけ大きなイベントからなる、要素数が１の時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されたイベントの個数に１を加算する。
【００１７】
またさらに、候補時系列パターン生成部１０４は、指定された要素数を持つ時系列パターンの中から、未抽出の時系列パターンの組を時系列パターン対として取り出し、候補時系列パターン生成部１０４は、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する。候補時系列パターン生成部１０４は、例えば、時系列パターン対が指定されている後述する条件３、条件４を満足しているかどうかを判定し、満足している場合には、時系列パターンの第１の時系列パターンに、第２の時系列パターンの最後の要素を付け加えることにより、候補時系列パターンを生成する。そして、候補時系列パターン生成部１０４は、指定された要素数に一致する未抽出の時系列パターン対が存在しない場合に、指定された要素数よりも１だけ大きな要素からなる時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されている要素数に１を加算する。
【００１８】
部分時系列制約条件判定部１０５は、抽出された候補イベントを時系列制約条件分解部１０２に設定されている部分時系列制約条件に適用することにより、候補イベントに一致する属性値が設定されているかどうかを判定する。
【００１９】
また、部分時系列制約条件判定部１０５は、生成した候補イベント集合を、部分時系列制約条件に適用し、この候補イベント集合に一致する部分時系列制約条件が存在するかどうかを判定する。
【００２０】
さらに、部分時系列制約条件判定部１０５は、時系列制約条件分解部１０２に設定されている部分時系列制約条件を参照することにより、生成された候補時系列パターンがこの部分時系列制約条件に一致するかどうかを判定する。
【００２１】
候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補イベントを、時系列データ格納部１０３に格納されている時系列データに適用することにより、この候補イベントを含む時系列データの個数を計算し、この候補イベントの出現頻度とする。ただし、時系列データが同一のイベントを複数含んでいるとしても、その個数は１個と計算することにする。また、式に基づいて、このイベントの支持度（評価値）を計算する。
【００２２】
また、候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補イベント集合を時系列データに適用することにより、候補イベント集合を含む時系列データの個数を出現頻度として計算する。また、式によりこの候補イベント集合の支持度を計算する。
【００２３】
さらに、候補時系列パターン評価部１０６は、部分時系列制約条件を満たす候補時系列パターンを時系列データに適用することにより、この候補時系列パターンを含む時系列データの個数を出現頻度として求め、後述する式により、この候補時系列パターンの支持度を計算する。
【００２４】
候補時系列パターン判定部１０７が、部分時系列制約条件を満たすイベントの支持度と予め指定されている最小支持度（閾値）を比較することにより、指定した最小支持度以上になるかどうかを判定する。このとき、最小支持度以上になる場合には、この候補イベントを特徴イベントとし、候補時系列パターン判定部１０７が特徴イベントを時系列パターン格納部１０８に格納する。
【００２５】
また、候補時系列パターン判定部１０７が、候補イベント集合の支持度が指定した最小支持度以上になるかどうかを判定し、支持度が最小支持度以上となる場合に、この候補イベント集合を特徴イベント集合とし、候補時系列パターン判定部１０７が、特徴イベント集合を時系列パターン格納部１０８に格納する。
さらに、候補時系列パターン判定部１０７が、候補時系列パターンの支持度が最小支持度以上になっているかどうかを判定し、支持度が最小支持度以上になっている場合に、この候補時系列パターンを時系列パターンとし、候補時系列パターン判定部１０７が時系列パターンを時系列パターン格納部１０８に格納する。
【００２６】
次に、図１の処理の流れの一例について図２を参照して説明する。
（ステップＳ２０１）時系列制約条件分解部１０２が、時系列制約条件格納部１０１に格納されている時系列制約条件から未抽出の時系列制約条件を１つ取り出して設定する。このとき、取り出す時系列制約条件が存在しない場合には、ステップＳ２０５へと進み、一方、取り出す時系列制約条件が存在する場合には、ステップＳ２０２へと進む。
【００２７】
（ステップＳ２０２）時系列制約条件分解部１０２は、取り出した時系列制約条件を分解して、この時系列制約条件に含まれる、より小さな部分時系列制約条件を生成する。このとき、部分時系列制約条件の生成に成功する場合には、ステップＳ２０３へと進み、一方、生成に失敗した場合には、ステップＳ２０４へと進む。
【００２８】
例えば、時系列データを構成するイベントが図３に示すように与えられているとする。ただし、これらのイベントにおいて、“／”で区切られた前側の部分が属性、後ろ側の部分が属性値を表すものとし、属性と属性値の組によって各イベントが構成されているとする。属性とはデータの特徴を表す性質のことであり、属性値とは特定のデータの性質の値を示す。例えば、「血圧／正常」のイベントでは、属性が血圧であり、属性値が正常である。このイベントは血圧のデータは正常であることを示している。
【００２９】
また、図４に示すような時系列制約条件が与えられているとする。ただし、“（）”で括られたイベントは同一の単位時間帯において発生したイベントを表すとし、“→”によって時間が経過したことを表すとする。したがって、図４の例の場合、３単位時間に跨った時系列制約条件が与えられている。一方、ｘ，ｙは与えられている属性のうちの異なる属性を表しているとする。したがって、図３のようなイベントが与えられている場合には、ｘ，ｙは「血圧」、「塩分」、「糖分」のうちのいずれかの属性に対応することになる。
【００３０】
このとき、時系列制約条件分解部１０２は、時間的に後方に位置する１以上の要素を時系列制約条件から取り出す。また、時系列制約条件分解部１０２は、取り残された要素に、取り出した一方の要素を付加した部分時系列制約条件と、取り出したもう一方の要素を付加した部分時系列制約条件とを生成する。具体例を挙げる。図４の時系列制約条件の場合、３要素からなっているため、共通する要素は１番目の要素だけである。したがって、時系列制約条件分解部１０２は、図５に示すような１番目の要素と２番目の要素、１番目の要素と３番目の要素からなる２つの部分時系列制約条件を生成して、ステップＳ２０３へと進む。
【００３１】
また、図５の上位に示すように時系列制約条件が与えられているとする。このとき、共通する要素は存在しないため、時系列制約条件分解部１０２は図６に示すような１番目の要素と２番目の要素からなる部分時系列制約条件を生成して、ステップＳ２０３へと進む。同様に、図５の下位に示す時系列制約条件からは、図７に示す部分時系列制約条件を生成する。
【００３２】
さらに、図６の上位に示すように時系列制約条件が与えられているとする。このとき、この時系列制約条件には、１つの要素しか含まれていないため、時系列制約条件分解部１０２は、辞書順に並べられたイベントの中からその後方にある２つのイベントを取り出し、残りのイベントと取り出したイベントのそれぞれからなる２つの部分要素を生成する。図６の上位に示す時系列制約条件の要素の場合、２つのイベントしか含まれていないため、各イベントに対応する部分要素「ｘ／正常」、「ｙ／正常」を生成する。これらの部分要素の場合、部分要素に含まれるイベントの個数が１個となり、属性の違いを考慮する必要がないため、属性の違いを表現するために導入されている変数ｘ、ｙを部分要素から取り除く。したがって、この場合には図８に示すような部分要素が部分時系列制約条件として抽出されて、ステップＳ２０３へと進む。同様に、図６の下位に示す時系列制約条件からは、時系列制約条件分解部１０２は図９に示すような部分時系列制約条件を抽出する。また、図７の下位に示す時系列制約条件からは、時系列制約条件分解部１０２は図１０に示すような部分時系列制約条件を抽出する。
【００３３】
一方、１つのイベントからなる時系列制約条件を選択した場合、時系列制約条件分解部１０２は、この時系列制約条件をこれ以上分解することができないため、時系列制約条件の分解に失敗したと判定して、ステップＳ２０４へと進む。
【００３４】
（ステップＳ２０３）時系列制約条件分解部１０２が、生成された部分時系列制約条件が既に抽出されているかどうかを判定し、抽出されていない場合に、この部分時系列制約条件を未処理の部分時系列制約条件として設定する。
【００３５】
例えば、図４に示す時系列制約条件を分解しているとすれば、図５に示す部分時系列制約条件が生成されている。このとき、各部分時系列制約条件はまだ抽出されていない部分時系列制約条件であるため、時系列制約条件分解部１０２は各部分時系列制約条件を未処理の部分時系列制約条件として設定する。
【００３６】
一方、図５の下位に示す時系列制約条件を分解しているとすれば、図７に示す部分時系列制約条件が生成されている。このとき、図５の上位に示す部分時系列制約条件が既に処理済みであるとすれば、図７に示す部分時系列制約条件のうち、上位に示す部分時系列制約条件「（ｘ／正常，ｙ／正常）」は既に設定済みである。このため、時系列制約条件分解部１０２は下位に示す部分時系列制約条件「（ｘ／異常，ｙ／要注意）」だけを未処理の部分時系列制約条件として設定する。
【００３７】
（ステップＳ２０４）時系列制約条件分解部１０２が、設定されている未処理の部分時系列制約条件の中から、部分時系列制約条件に含まれている要素の数が最も多い部分時系列制約条件を１つ取り出して、ステップＳ２０２へと戻る。一方、取り出す未処理の部分時系列制約条件が存在しない場合には、ステップＳ２０１へと進む。
【００３８】
例えば、図１１に示すように未処理の部分時系列制約条件が設定されている場合には、時系列制約条件分解部１０２は、要素数が多い部分時系列制約条件「（ｘ／正常，ｙ／正常）→（ｘ／異常，ｙ／要注意）」を取り出して、ステップＳ２０２へと戻る。
【００３９】
（ステップＳ２０５）候補時系列パターン生成部１０４が、時系列データ格納部１０３に格納されている時系列データの中から、時系列データを１つ取り出し、ステップＳ２０６に進み、一方、時系列データ格納部１０３に格納されている時系列データを全て取り出した場合にはステップＳ２１１に進む。
【００４０】
（ステップＳ２０６）候補時系列パターン生成部１０４が、取り出した時系列データの中から未抽出のイベントを１つ取り出して、候補イベントとする。このとき、取り出す候補イベントが存在する場合には、ステップＳ２０７へと進み、一方、取り出すイベントが存在しない場合には、ステップＳ２０５へと処理を戻す。
【００４１】
例えば、図１３のｄ１の時系列データが候補時系列パターン生成部１０４によって読み込まれているとする。このとき、時系列データの左側から右側にイベントを順に取り出すことにすれば、候補イベント「血圧／正常」を最初に取り出すことになり、ステップＳ２０７へと進む。また、最後のイベント「糖分／異常」を取り出した後で、ステップＳ２０６を実施する場合に、ステップＳ２０５へと進むことになる。
【００４２】
（ステップＳ２０７）部分時系列制約条件判定部１０５が、抽出された候補イベントを時系列制約条件分解部１０２に設定されている部分時系列制約条件に適用することにより、この候補イベントに一致する属性値が設定されているかどうかを判定する。このとき、このイベントが部分時系列制約条件に設定されている場合には、ステップＳ２０８へと進み、一方、設定されていない場合には、ステップＳ２０５へと処理を戻す。
【００４３】
例えば、部分時系列制約条件として、図１２に示す部分時系列制約条件が設定されているとし、イベントとして、「血圧／正常」が取り出されているとする。このとき、属性値「正常」はこの部分時系列制約条件に設定されているため、ステップＳ２０８へと進み、一方、イベントとして、「糖分／未検査」が取り出されているとすれば、属性値「未検査」はこの部分時系列制約条件に設定されていないため、ステップＳ２０５へと戻る。
【００４４】
（ステップＳ２０８）候補時系列パターン評価部１０６が、部分時系列制約条件を満たす候補イベントを、時系列データ格納部１０３に格納されている時系列データに適用することにより、この候補イベントを含む時系列データの個数を計算し、この候補イベントの出現頻度とする。ただし、時系列データが同一のイベントを複数含んでいるとしても、その個数は１個と計算することにする。また、次式（１）に基づいて、このイベントの支持度を計算する。
【００４５】
支持度＝イベントの出現頻度／時系列データの個数・・・（１）
例えば、図１３に示す時系列データが時系列データ格納部１０３に格納されているとし、部分時系列制約条件を満たすイベントとして「血圧／正常」が与えられているとする。このとき、各時系列データは、このイベントを含んでいるため、このイベントの出現頻度は３となる。また、時系列データの個数は３であるため、このイベントの支持度は１．０（＝３／３）となる。
【００４６】
一方、部分時系列制約条件を満たすイベントとして「塩分／異常」が与えられているとすれば、このイベントを含む時系列データは存在しないため、このイベントの出現頻度は０となる。したがって、このイベントの支持度は０．０（＝０／３）となる。
【００４７】
（ステップＳ２０９）候補時系列パターン判定部１０７が、部分時系列制約条件を満たすイベントの支持度と予め指定されている最小支持度を比較することにより、指定した最小支持度以上になるかどうかを判定する。このとき、最小支持度以上になる場合には、この候補イベントを特徴イベントとして、ステップＳ２１０へと進み、一方、最小支持度より小さい場合には、ステップＳ２０５へと戻る。
【００４８】
例えば、最小支持度として０．９が与えられており、部分時系列制約条件を満たすイベントとして「血圧／正常」が与えられているとすれば、このイベントの支持度は１．０であり０．９以上となるため、この候補イベントを特徴イベントとしてステップＳ２１０へと進む。一方、部分時系列制約条件を満たすイベントとして「塩分／異常」が与えられているとすれば、このイベントの支持度は０であり０．９よりも小さくなるため、ステップＳ２０５へと戻る。
【００４９】
（ステップＳ２１０）候補時系列パターン判定部１０７が特徴イベントを時系列パターン格納部１０８に格納する。例えば、図１４に示す特徴イベントが、イベント数が１個からなる時系列パターンとして時系列パターン格納部１０８に格納される。
【００５０】
（ステップＳ２１１）候補時系列パターン生成部１０４がイベント数の初期値として例えば１を設定する。
【００５１】
（ステップＳ２１２）候補時系列パターン生成部１０４が、時系列パターン格納部１０８に格納されている特徴イベントの集合の中から、指定されたイベント数に一致し、未抽出のイベント集合の組み合わせである、２つのイベント集合をイベント集合対として取り出す。ただし、同一のイベント集合を取り出すことも可能とする。このとき、イベント集合対が抽出される場合には、ステップＳ２１３へと進み、一方、抽出されない場合には、ステップＳ２１８へと進む。
【００５２】
（ステップＳ２１３）候補時系列パターン生成部１０４が、抽出されたイベント集合対が下記の条件１及び条件２を満足するかどうかを判定し、満足する場合には、このイベント集合対の一方のイベント集合に、もう一方のイベント集合の最後に位置するイベントを追加することにより、候補イベント集合を生成して、ステップＳ２１４へと進む。一方、満足しない場合には、ステップＳ２１２へと戻る。
条件１．イベント集合の最後に位置付けられているイベントを除いた残りのイベント部分集合が一致している。
条件２．最後に位置付けられているイベントの属性が一致していない。
【００５３】
ただし、イベント集合に含まれる各イベントの属性は、辞書順などの基準に基づいて整列されているとし、１個のイベントからなる特徴イベントは特徴イベント集合の特殊な例であるとする。
【００５４】
例えば、属性が、「血圧、塩分、糖分」といった順に整列されているとする。このとき、イベント数として１が与えられているとし、１つのイベントからなるイベント集合「血圧／正常」、「塩分／正常」が、イベント集合対として与えられているとする。イベント数が１の場合、条件１は常に成立している。加えて、このイベント集合対に対しては、属性が「血圧」、「塩分」と異なっているため、条件２も成立している。このため、「（血圧／正常，塩分／正常）」が候補イベント集合として生成され、ステップＳ２１４へと進む。
また、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／正常，糖分／正常）」が、イベント集合対として与えられているとする。このイベント集合対においては、２番目のイベントを除いたイベント集合が「血圧／正常」と一致しているとともに、２番目のイベントの属性が「塩分」、「糖分」と異なっているため、条件１、条件２が成立する。このため、「（血圧／正常，塩分／正常，糖分／正常）」が候補イベント集合として得られ、ステップＳ２１４へと進む。
【００５５】
一方、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／要注意，塩分／正常）」が、与えられているとする。このイベント集合対においては、２番目のイベントを除いたイベント集合が「血圧／正常」、「血圧／要注意」と一致しておらず、条件１が成立していない。このため、候補イベント集合を生成することができず、ステップＳ２１２へと戻る。
また、イベント数が２と与えられているとし、２つのイベントからなるイベント集合「（血圧／正常，塩分／正常）」、「（血圧／正常，塩分／正常）」が、与えられているとする。このイベント集合対においては、２番目のイベントにおける属性がともに「塩分」となっているため、条件２が成立していない。このため、候補イベント集合を生成することができず、ステップＳ２１２へと戻る。
【００５６】
（ステップＳ２１４）部分時系列制約条件判定部１０５は、生成された候補イベント集合を、部分時系列制約条件に適用し、この候補イベント集合に一致する部分時系列制約条件が存在するかどうかを判定する。このとき、この部分時系列制約条件が存在する場合には、ステップＳ２１５へと進み、一方、存在しない場合には、ステップＳ２１２へと戻る。
【００５７】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合には、図１２に示す部分時系列制約条件「（ｘ／正常，ｙ／正常）」に一致しているため、ステップＳ２１５へと進む。
【００５８】
一方、「（血圧／正常，糖分／異常）」が候補イベント集合として与えられている場合には、一致する部分時系列制約条件が図１２の中に存在しないため、ステップＳ２１２へと戻る。また、「（血圧／正常，塩分／正常，糖分／正常）」が候補イベント集合として与えられている場合には、一致する部分時系列制約条件が図１２の中に存在しないため、ステップＳ２１２へと戻る。
【００５９】
（ステップＳ２１５）候補時系列パターン評価部１０６が、生成された候補イベント集合を時系列データに適用することにより、候補イベント集合を含む時系列データの個数を出現頻度として計算する。また、式（１）によりこの候補イベント集合の支持度を計算する。
【００６０】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合、図１３に示す各時系列データは、この候補イベント集合を含んでいるため、出現頻度は３となる。また、その支持度は１．０（＝３／３）となる。
【００６１】
一方、「（血圧／要注意，糖分／異常）」が候補イベント集合として与えられている場合、図１３に示す各時系列データは、この候補イベント集合を含んでいないため、出現頻度は０となる。また、その支持度は０．０（＝０／３）となる。
【００６２】
（ステップＳ２１６）候補時系列パターン判定部１０７が、候補イベント集合の支持度が指定した最小支持度以上になるかどうかを判定し、最小支持度以上となる場合に、この候補イベント集合を特徴イベント集合として、ステップＳ２１７へと進み、一方、最小支持度よりも小さくなる場合には、ステップＳ２１２へと戻る。
【００６３】
例えば、「（血圧／正常，塩分／正常）」が候補イベント集合として与えられている場合、ステップＳ２０９での計算と同様にして、その支持度は１．０となり、最小支持度である０．９以上となるため、この候補イベント集合を特徴イベント集合として、ステップＳ２１７へと進む。
【００６４】
一方、「（血圧／要注意，糖分／異常）」が候補イベント集合として与えられている場合、ステップＳ２０９での計算と同様にして、その支持度は０．０となり、最小支持度である０．９よりも小さくなるため、ステップＳ２１２へと戻る。
【００６５】
（ステップＳ２１７）候補時系列パターン判定部１０７が、特徴イベント集合を時系列パターン格納部１０８に格納する。
例えば、図１５に示す特徴イベント集合が、要素数が１で、その中に含まれるイベント数が２である時系列パターンとして、時系列パターン格納部１０８に格納される。
【００６６】
（ステップＳ２１８）候補時系列パターン生成部１０４が、時系列パターン格納部１０８に格納されている時系列パターンの中に、指定されたイベント数より１だけ大きなイベントからなる、要素数が１の時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されたイベントの個数に１を加算し、ステップＳ２１２へと戻り、一方、存在しない場合には、ステップＳ２１９へと進む。
【００６７】
（ステップＳ２１９）候補時系列パターン生成部１０４が要素数の初期値として例えば１を設定する。
【００６８】
（ステップＳ２２０）候補時系列パターン生成部１０４が、指定された要素数を持つ時系列パターンの中から、未抽出の時系列パターンの組を時系列パターン対として取り出す。このとき、取り出す時系列パターン対が存在しない場合には、ステップＳ２２６へと進み、一方、存在する場合には、ステップＳ２２１へと進む。ただし、取り出される２つの時系列パターンは同一の時系列パターンであってもよいとする。また、時系列パターンが取り出される順序が異なる時系列パターンの組は、異なる時系列パターンの組であるとする。
【００６９】
（ステップＳ２２１）候補時系列パターン生成部１０４が、時系列パターン対が下記の条件３、条件４を満足しているかどうかを判定し、満足している場合には、時系列パターンの第１の時系列パターンに、第２の時系列パターンの最後の要素を付け加えることにより、候補時系列パターンを生成して、ステップＳ２２２へと進み、一方、満足していない場合には、ステップＳ２２０へと戻る。
条件３．最後の要素を除いた部分時系列パターンが一致している。
条件４．最後の要素に含まれるイベントの属性集合が一致している。
【００７０】
例えば、要素数が１である時系列パターン対として、「（血圧／正常，塩分／正常）」、「（血圧／要注意，塩分／正常）」が取り出されているとする。要素数が１の場合、条件３は常に成立している。加えて、最後の要素に含まれるイベントの属性集合が「血圧、塩分」と一致しているため、条件４が成立する。このため、この時系列パターン対から候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」を生成して、ステップＳ２２２へと進む。
【００７１】
また、要素数が２である時系列パターン対として、「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」、「（血圧／正常，塩分／正常）→（血圧／異常，塩分／要注意）」が取り出されているとする。この時系列パターンにおいては、最後の要素を除いた部分時系列パターン「（血圧／正常，塩分／正常）」が一致しており、条件３が成立するとともに、最後の要素に含まれるイベントの属性集合が「血圧、塩分」と一致しているため、条件４が成立する。このため、この時系列パターン対から候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）→（血圧／異常，塩分／要注意）」を生成して、ステップＳ２２２へと進む。
【００７２】
一方、要素数が１である時系列パターン対として、「（血圧／正常，塩分／正常）」、「（血圧／要注意，糖分／正常）」が取り出されているとする。この時系列パターンにおいては、最後の要素に含まれるイベントの属性集合がそれぞれ「血圧、塩分」、「血圧、糖分」となり、一致していないため、条件４が成立していない。このため、ステップＳ２２０へと戻る。
【００７３】
（ステップＳ２２２）部分時系列制約条件判定部１０５が時系列制約条件分解部１０２に設定されている部分時系列制約条件を参照することにより、生成された候補時系列パターンがこの部分時系列制約条件に一致するかどうかを判定する。このとき、一致する部分時系列制約条件が存在する場合には、ステップＳ２２３へと進み、一方、存在しない場合には、ステップＳ２２０へと戻る。
【００７４】
例えば、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」が生成されている場合、この候補時系列パターンは、図１２に示す部分時系列制約条件のうち、「（ｘ／正常，ｙ／正常）→（ｘ／要注意，ｙ／正常）」に一致しているため、ステップＳ２２３へと進む。
【００７５】
一方、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／正常，塩分／正常）」が生成されている場合、この候補時系列パターンに一致する部分時系列制約条件は、図１２の中には存在しないため、ステップＳ２２０へと戻る。
【００７６】
（ステップＳ２２３）候補時系列パターン評価部１０６が、候補時系列パターンを含む時系列データの個数を出現頻度として求め、式（１）により、この候補時系列パターンの支持度を計算する。
【００７７】
例えば、候補時系列パターンとして「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」が与えられている場合、この候補時系列パターンは図１３の各時系列データに含まれているため、その出現頻度は３となる。また、その支持度は１．０（＝３／３）となる。
【００７８】
また、候補時系列パターンとして「（血圧／正常，糖分／正常）→（血圧／要注意，糖分／正常）」が与えられている場合、この候補時系列パターンは図１３のｄ１，ｄ３の時系列データに含まれているため、その出現頻度は２となる。また、その支持度は０．６７（＝２／３）となる。
【００７９】
（ステップＳ２２４）候補時系列パターン判定部１０７が候補時系列パターンの支持度が最小支持度以上になっているかどうかを判定する。このとき、この候補時系列パターンの支持度が最小支持度以上になっている場合に、この候補時系列パターンを時系列パターンとして、ステップＳ２２５へと進み、一方、最小支持度よりも小さくなっている場合に、ステップＳ２２０へと戻る。
【００８０】
例えば、候補時系列パターン「（血圧／正常，塩分／正常）→（血圧／要注意，塩分／正常）」の場合、その支持度が１．０であり、最小支持度である０．９以上となるため、この候補時系列パターンを時系列パターンとして、ステップＳ２２５へと進む。
【００８１】
一方、候補時系列パターン「（血圧／正常，糖分／正常）→（血圧／要注意，糖分／正常）」の場合、その支持度が０．６７であり、最小支持度である０．９よりも小さくなるため、ステップＳ２２０へと戻る。
【００８２】
（ステップＳ２２５）候補時系列パターン判定部１０７が時系列パターンを時系列パターン格納部１０８に格納し、ステップＳ２２０へと戻る。
【００８３】
例えば、要素数が２となる時系列パターンとして、図１６に示す時系列パターンが格納される。また、要素数が３となる時系列パターンとして、図１７に示す時系列パターンが格納される。
【００８４】
（ステップＳ２２６）候補時系列パターン生成部１０４が、指定されている要素数よりも１だけ大きな要素からなる時系列パターンが存在するかどうかを判定する。このとき、この時系列パターンが存在する場合には、指定されている要素数に１を加算し、ステップＳ２２０へと戻る一方、存在しない場合には、本処理を終了する。
【００８５】
このような処理を実施することにより、指定された時系列制約条件を満たす、最小支持度以上の支持度となる、すべての時系列パターンを発見することができる。すなわち、例えば、図１３の時系列データから、図４の時系列制約条件を満たす、最小支持度である０．９以上の支持度を持つ時系列パターンとして、図１７に示す時系列パターンを発見することができる。
【００８６】
このように、属性と属性値によって特徴付けられるイベントによって構成される時系列データから時系列パターンを発見する方法において、利用者の興味のある構造を含んだ時系列パターンを効率よく高速に発見することができる。
【００８７】
なお、本時系列制約条件に基づいた時系列パターン発見装置は、上述した実施形態に限定するものではない。例えば、候補イベント、候補イベント集合、候補時系列パターンを、特徴イベント、特徴イベント集合、時系列パターンとみなすかどうかを判定するのに、本実施形態では支持度を利用しているが、参考文献“Sequential Mining Method based on a New Criterion”, (Shigeaki Sakurai, Youichi Kitahara, and Ryohei Orihara, Proc. the 10th IASTED Int. Conf. on Artificial Intelligence and Soft Computing, 544-045, 2006）に記載の系列興味度を利用してもよい。
【００８８】
また、実施形態においては、時系列制約条件格納部１０１に格納されている時系列制約条件を１つに限定しているが、複数の時系列制約条件を設定することもできる。また、時系列制約条件における要素数や各要素に含まれるイベント数を、それぞれ３、２としているが、この要素を任意の自然数とすることができる。加えて、イベントを構成する各属性の属性値を、すべて同一の値としているが、一部の属性値だけを同一の値にしたり、特定の属性に関しては全く異なる属性値を指定したりすることもできる。この他、本発明の趣旨を逸脱しない範囲において、種々変形して時系列制約条件に基づいた時系列パターン発見装置を構成することができる。
【００８９】
以上に示した実施形態によれば、部分時系列制約条件に基づいた判定を行うことにより、候補時系列パターンに対して実施する必要があった、時系列データを用いた出現頻度の評価回数を大幅に削減することができ、実用的な時間内で時系列パターンを発見することができる。また、複数の属性における属性値間の時系列的な関係を考慮しているため、複数の属性の属性値間の関係を内在する時系列パターンを発見することができる。加えて、利用者が注目していた構造を持った時系列パターンだけを発見することができるため、利用者にとって興味のない時系列パターンが多数発見されることを回避することができる。
【００９０】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の時系列パターン発見装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の時系列パターン発見装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合又は読み込む場合はネットワークを通じて取得又は読み込んでもよい。
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【００９１】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【００９２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９３】
【図１】実施形態の時系列パターン発見装置のブロック図。
【図２】図１の時系列パターン発見装置の動作の一例を示すフローチャート。
【図３】時系列データを構成するイベントの一例を示す図。
【図４】時系列制約条件の一例を示す図。
【図５】ステップＳ２０２で図１の時系列制約条件分解部が図４から生成する部分時系列制約条件の一例を示す図。
【図６】ステップＳ２０２で図１の時系列制約条件分解部が図５の上位から生成する部分時系列制約条件の一例を示す図。
【図７】ステップＳ２０２で図１の時系列制約条件分解部が図５の下位から生成する部分時系列制約条件の一例を示す図。
【図８】ステップＳ２０２で図１の時系列制約条件分解部が図６の上位から生成する部分時系列制約条件の一例を示す図。
【図９】ステップＳ２０２で図１の時系列制約条件分解部が図６の下位から生成する部分時系列制約条件の一例を示す図。
【図１０】ステップＳ２０２で図１の時系列制約条件分解部が図７の下位から生成する部分時系列制約条件の一例を示す図。
【図１１】未処理の部分時系列制約条件の一例を示す図。
【図１２】図１の時系列制約条件分解部に設定されている部分時系列制約条件の一例を示す図。
【図１３】図１の時系列データ格納部に格納されている時系列データの一例を示す図。
【図１４】図１の時系列パターン格納部に格納されている時系列パターンの一例を示す図。
【図１５】ステップＳ２１７で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【図１６】ステップＳ２２５で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【図１７】ステップＳ２２５で図１の時系列パターン格納部に格納される時系列パターンの一例を示す図。
【符号の説明】
【００９４】
１０１・・・時系列制約条件格納部、１０２・・・時系列制約条件分解部、１０３・・・時系列データ格納部、１０４・・・候補時系列パターン生成部、１０５・・・部分時系列制約条件判定部、１０６・・・候補時系列パターン評価部、１０７・・・候補時系列パターン判定部、１０８・・・時系列パターン格納部。
【特許請求の範囲】
【請求項１】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段と、を備えることを特徴とする時系列パターン発見装置。
【請求項２】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、
前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、
前記時系列データの１つから第１イベントを抽出する抽出手段と、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、
前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段を備え、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見装置。
【請求項３】
前記候補イベント集合生成手段は、２つの集合で、各集合の最後に位置付けられているイベントを除いた残りのイベント部分集合が一致し、かつ、最後に位置付けられているイベントの属性が一致していない場合に、一方の集合に他方の集合の最後に位置するイベントを追加する集合を、候補特徴イベント集合として生成することを特徴とする請求項２に記載の時系列パターン発見装置。
【請求項４】
前記候補パターン生成手段は、２つの時系列パターンで、最後の要素を除いた部分時系列パターンが一致し、かつ、最後の要素に含まれるイベントの属性集合が一致する場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加える時系列パターンを、候補時系列パターンとして生成することを特徴とする請求項２または請求項３に記載の時系列パターン発見装置。
【請求項５】
前記第１計算手段は、前記第１割合として、
（前記第１イベントを含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項４のいずれか１項に記載の時系列パターン発見装置。
【請求項６】
前記第２計算手段は、前記第２割合として、
（前記候補特徴イベント集合を含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項５のいずれか１項に記載の時系列パターン発見装置。
【請求項７】
前記第３計算手段は、前記第３割合として、
（前記候補時系列パターンを含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項６のいずれか１項に記載の時系列パターン発見装置。
【請求項８】
前記候補イベント集合生成手段は、前記あるイベント数が１である場合から候補特徴イベント集合を生成することを特徴とする請求項２から請求項７のいずれか１項に記載の時系列パターン発見装置。
【請求項９】
前記ある要素数は１であることを特徴とする請求項２から請求項８のいずれか１項に記載の時系列パターン発見装置。
【請求項１０】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解し、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定し、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算し、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出することを特徴とする時系列パターン発見方法。
【請求項１１】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段を用意し、
前記時系列制約条件を時系列的により短い部分制約条件に分解し、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段を用意し、
前記時系列データの１つから第１イベントを抽出し、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算し、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段を用意し、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成し、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算し、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段を用意し、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定し、
含まれていると判定された場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成し、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算することを特徴とし、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して、前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定し、
含まれていると判定された場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成し、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算して、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見方法。
【請求項１２】
コンピュータを、
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段として機能させるための時系列パターン発見プログラム。
【請求項１３】
コンピュータを、
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、
前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、
前記時系列データの１つから第１イベントを抽出する抽出手段と、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、
前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段として機能させるためのプログラムであり、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見プログラム。
【請求項１】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段と、を備えることを特徴とする時系列パターン発見装置。
【請求項２】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、
前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、
前記時系列データの１つから第１イベントを抽出する抽出手段と、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、
前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段を備え、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見装置。
【請求項３】
前記候補イベント集合生成手段は、２つの集合で、各集合の最後に位置付けられているイベントを除いた残りのイベント部分集合が一致し、かつ、最後に位置付けられているイベントの属性が一致していない場合に、一方の集合に他方の集合の最後に位置するイベントを追加する集合を、候補特徴イベント集合として生成することを特徴とする請求項２に記載の時系列パターン発見装置。
【請求項４】
前記候補パターン生成手段は、２つの時系列パターンで、最後の要素を除いた部分時系列パターンが一致し、かつ、最後の要素に含まれるイベントの属性集合が一致する場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加える時系列パターンを、候補時系列パターンとして生成することを特徴とする請求項２または請求項３に記載の時系列パターン発見装置。
【請求項５】
前記第１計算手段は、前記第１割合として、
（前記第１イベントを含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項４のいずれか１項に記載の時系列パターン発見装置。
【請求項６】
前記第２計算手段は、前記第２割合として、
（前記候補特徴イベント集合を含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項５のいずれか１項に記載の時系列パターン発見装置。
【請求項７】
前記第３計算手段は、前記第３割合として、
（前記候補時系列パターンを含む時系列データの数）／（前記データ格納手段に格納されている時系列データの数）
を計算することを特徴とする請求項２から請求項６のいずれか１項に記載の時系列パターン発見装置。
【請求項８】
前記候補イベント集合生成手段は、前記あるイベント数が１である場合から候補特徴イベント集合を生成することを特徴とする請求項２から請求項７のいずれか１項に記載の時系列パターン発見装置。
【請求項９】
前記ある要素数は１であることを特徴とする請求項２から請求項８のいずれか１項に記載の時系列パターン発見装置。
【請求項１０】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解し、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定し、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算し、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出することを特徴とする時系列パターン発見方法。
【請求項１１】
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段を用意し、
前記時系列制約条件を時系列的により短い部分制約条件に分解し、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段を用意し、
前記時系列データの１つから第１イベントを抽出し、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算し、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段を用意し、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成し、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算し、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段を用意し、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定し、
含まれていると判定された場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成し、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算することを特徴とし、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して、前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定し、
含まれていると判定された場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成し、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算して、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見方法。
【請求項１２】
コンピュータを、
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を示す時系列制約条件を、該イベントを組み合わせることにより生成される部分時系列制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データの１つから抽出した候補イベント、特徴的なイベント集合から生成されるより多くのイベントから構成される候補特徴イベント集合、および、時系列パターンから生成されるより多くの要素から構成される候補時系列パターンのそれぞれに対して、前記部分時系列制約条件が成立するかどうかを判定する判定手段と、
前記部分時系列制約条件を満たす、候補イベント、候補特徴イベント集合、候補時系列パターンに対してのみ、前記時系列データにおける出現頻度を計算する計算手段と、
前記出現頻度に基づいた評価値が閾値以上となる、候補イベント、候補イベント集合、候補時系列パターンを、時系列パターンとして抽出する抽出手段として機能させるための時系列パターン発見プログラム。
【請求項１３】
コンピュータを、
データの特徴を示す性質である属性と、該属性の属性値とからなるイベントを１以上含んでいるものと定義される要素での複数の要素間の時系列的な関係を時系列制約条件として格納している制約条件格納手段と、
前記時系列制約条件を時系列的により短い部分制約条件に分解する分解手段と、
要素間の時系列的な関係を示すデータである時系列データを複数格納しているデータ格納手段と、
前記時系列データの１つから第１イベントを抽出する抽出手段と、
前記第１イベントに含まれる属性値が前記部分制約条件に含まれている場合に、前記時系列データ１つ当たりに該第１イベントが含まれている第１割合を計算する第１計算手段と、
前記第１割合が閾値以上である場合には、前記第１イベントを特徴イベントとして抽出し、全ての部分制約条件、前記データ格納手段に格納されている全ての時系列データについて抽出された全ての特徴イベントを格納する特徴イベント格納手段と、
あるイベント数を含む特徴イベントの集合を２つ選択し、２つの該集合の部分が一致していて、かつ、２つの該集合が完全一致でない場合に、前記２つの集合に含まれる特徴イベントを全て含む候補特徴イベント集合を生成する候補イベント集合生成手段と、
前記時系列データ１つ当たりに前記候補特徴イベント集合が含まれている第２割合を計算する第２計算手段と、
前記第２割合が閾値以上である場合には、前記候補特徴イベント集合を時系列パターンとして抽出し格納するパターン格納手段と、
前記イベント数より１つ大きい、ある要素数の時系列パターンが前記パターン格納手段に含まれていない場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンが複数個前記パターン格納手段に含まれているかを判定する判定手段と、
前記判定手段が含まれていると判定した場合には、前記イベント数に１を加算したイベント数で前記ある要素数である時系列パターンを２つ選択し、２つの該時系列パターンの部分が一致していて、かつ、完全一致でない場合に、一方の時系列パターンに他方の時系列パターンの最後の要素を付け加えた候補時系列パターンを生成する候補パターン生成手段と、
前記候補時系列パターンが前記部分制約条件に一致する場合には、前記時系列データ１つ当たりに前記候補時系列パターンが含まれている第３割合を計算する第３計算手段として機能させるためのプログラムであり、
前記第３割合が閾値以上である場合には、前記候補時系列パターンを時系列パターンとして抽出し前記パターン格納手段に該時系列パターンを格納し、
要素数を１つ加算して前記判定手段、候補パターン生成手段、第３計算手段の処理を行い、全ての要素数について時系列パターンを前記パターン格納手段に格納することを特徴とする時系列パターン発見プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００８−２２０５１１（Ｐ２００８−２２０５１１Ａ）
【公開日】平成２０年９月２５日（２００８．９．２５）
【国際特許分類】
【出願番号】特願２００７−６０６６６（Ｐ２００７−６０６６６）
【出願日】平成１９年３月９日（２００７．３．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２０年９月２５日（２００８．９．２５）
【国際特許分類】
【出願日】平成１９年３月９日（２００７．３．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]