(57)【特許請求の範囲】
【請求項１】
複数のイベントからなる系列データを格納する系列データ格納部と、
既に発見された特徴系列パターンを格納する特徴系列パターン格納部と、
前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成する候補系列パターン生成部と、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数を前記候補系列パターンの頻度として計算する系列パターン頻度計算部と、
前記特徴系列パターンにおける部分系列パターンの最大頻度を格納する部分系列パターン頻度格納部と、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの最大頻度に基づいて計算される評価値であって、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、前記候補系列パターンの評価値を計算する候補系列パターン評価部と、
前記評価値が閾値を超えるか否かを判定し、前記閾値を超える候補系列パターンの頻度を前記部分系列パターンの最大頻度として前記部分系列パターン頻度格納部に格納する候補系列パターン判定部と、を具備し、
前記候補系列パターン評価部は、ｓを系列パターン、ｓｐを系列パターンｓの部分系列パターン、ｆｓ（）を系列パターンの頻度、Ｎを系列データの個数とするとき、前記評価値に相当する興味度を次式（１）すなわち
【数１】
0004398907.tif 000010
に従って算出し、
前記閾値を超える候補系列パターンを新たな特徴系列パターンとして前記特徴系列パターン格納部に格納することを具備する特徴系列パターン発見装置。
【請求項２】
複数のイベントからなる系列データを格納する系列データ格納部と、
既に発見された特徴系列パターンを格納する特徴系列パターン格納部と、
前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成する候補系列パターン生成部と、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数を前記候補系列パターンの頻度として計算する系列パターン頻度計算部と、
前記特徴系列パターンにおける部分系列パターンの最大頻度を格納する部分系列パターン頻度格納部と、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの最大頻度に基づいて計算される評価値であって、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、前記候補系列パターンの評価値を計算する候補系列パターン評価部と、
前記評価値が閾値を超えるか否かを判定し、前記閾値を超える候補系列パターンの頻度を前記部分系列パターンの最大頻度として前記部分系列パターン頻度格納部に格納する候補系列パターン判定部と、を具備し、
前記候補系列パターン評価部は、ｓを系列パターン、ｓｐを系列パターンｓの部分系列パターン、ｆｓ（）を系列パターンの頻度、Ｎを系列データの個数とするとき、前記評価値に相当する興味度を次式（２）すなわち
【数２】
0004398907.tif 000011
に従って算出し、
前記閾値を超える候補系列パターンを新たな特徴系列パターンとして前記特徴系列パターン格納部に格納することを具備する特徴系列パターン発見装置。
【請求項３】
前記特徴系列パターンは、前記系列データから抽出され、時間順に並んだイベント集合からなる請求項１又は２に記載の特徴系列パターン発見装置。
【請求項４】
系列データ格納部に格納された複数のイベントからなる系列データと特徴系列パターン格納部に格納され、既に発見された特徴系列パターンとから新たな特徴系列パターンを発見する特徴系列パターン発見装置の作動方法であって、
候補系列パターン生成部が、前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成するステップと、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数を前記候補系列パターンの頻度として系列パターン頻度計算部が計算するステップと、
前記特徴系列パターンにおける部分系列パターンの最大頻度を部分系列パターン頻度格納部が格納するステップと、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの最大頻度に基づいて計算される評価値であって、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、候補系列パターン評価部が前記候補系列パターンの評価値を計算するステップと、
前記評価値が閾値を超えるか否かを候補系列パターン判定部が判定し、前記閾値を超える候補系列パターンの頻度を前記部分系列パターンの最大頻度として前記部分系列パターン頻度格納部に格納するステップとを具備し、
前記候補系列パターン評価部は、ｓを系列パターン、ｓｐを系列パターンｓの部分系列パターン、ｆｓ（）を系列パターンの頻度、Ｎを系列データの個数とするとき、前記評価値に相当する興味度を次式（３）すなわち
【数３】
0004398907.tif 000012
に従って算出し、
前記閾値を超える候補系列パターンが前記新たな特徴系列パターンとして前記特徴系列パターン格納部に格納されることを特徴とする特徴系列パターン発見装置の作動方法。
【請求項５】
系列データ格納部に格納された複数のイベントからなる系列データと特徴系列パターン格納部に格納され、既に発見された特徴系列パターンとから新たな特徴系列パターンを発見する特徴系列パターン発見装置の作動方法であって、
候補系列パターン生成部が、前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成するステップと、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数に相当する、を前記候補系列パターンの頻度をとして系列パターン頻度計算部が計算するステップと、
前記特徴系列パターンにおける部分系列パターンの最大頻度を部分系列パターン頻度格納部が格納するステップと、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの最大頻度からに基づいて計算される評価値であって、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、候補系列パターン評価部が前記候補系列パターンの評価値を計算するステップと、
前記評価値が閾値を超えるか否かを候補系列パターン判定部が判定し、前記閾値を超える候補系列パターンの頻度を前記部分系列パターンの最大頻度として前記部分系列パターン頻度格納部に格納するステップとを具備し、
前記候補系列パターン評価部は、ｓを系列パターン、ｓｐを系列パターンｓの部分系列パターン、ｆｓ（）を系列パターンの頻度、Ｎを系列データの個数とするとき、前記評価値に相当する興味度を次式（４）すなわち
【数４】
0004398907.tif 000013
に従って算出し、
前記閾値を超える候補系列パターンが前記新たな特徴系列パターンとして前記特徴系列パターン格納部に格納されることを特徴とする特徴系列パターン発見装置の作動方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ上に時間を追って蓄積される系列データ、例えば、小売り分野における日々の売上げデータ及び業務報告を記載した日報、健康管理分野における日々の血圧・脈拍等の生体データ及び個人の行動を記録した行動記録、金融分野における日々の株価データ及び新聞等に記載されているニュース等といった系列データに内在する特徴的な系列パターンを発見し、利用者の意思決定を支援するための装置及びその作動方法に関するものである。
【背景技術】
【０００２】
ＧＳＰ（Generalized Sequential Patterns）アルゴリズムでは、多数の要素から構成される系列データを入力とし、その系列データ集合の中において頻出する系列パターンを発見することができる。しかしながら、本手法において発見される頻出系列パターンは、分析者にとっては既知の系列パターンである場合が多く、必ずしも分析者に新たな知見を与えることができない。また、少ない頻度を指定して頻出系列パターンを発見する場合には、多数の頻出系列パターンを発見することになるため、すべての頻出系列パターンを発見するのに多くの時間が必要となるばかりか、新たな知見を与える特徴的な系列パターンが多数の頻出系列パターンの中に埋もれてしまう危険性がある。
【０００３】
下記特許文献１に記載の「意外性に基づく状態列パターンの評価装置」では、系列パターンに対して意外性を定義することにより、系列パターンの中から特徴的な系列パターンを発見することができる。しかしながら、本装置においては、意外性の有無の判定のための候補系列パターンが発見されていることを前提としており、意外性のある系列パターンを発見するには上記ＧＳＰなどの手法を利用して予め候補となる系列パターンを発見しなければならない。また、候補となる系列パターンの頻度の増減と意外性の値の増減との間には単調な関係が存在しないことから、低頻度の系列パターンをも候補として発見しなければ、すべての意外性のある系列パターンを発見することができない。このため、候補となる系列パターンを発見するのに多くの時間が必要である。
【０００４】
下記特許文献２に記載の「イベントデータに関する情報管理装置」では、対象となる問題領域において、時系列的に発生するイベントを利用することにより、問題領域における事例の重要度を更新し、現在の時間に合った重要度の高い事例を抽出することができる。しかしながら、本装置においては、問題領域に対応する事例の抽出の際に、時間を勘案して事例を抽出しているだけであり、時系列的なパターンを発見することはできない。
【特許文献１】特開２００４−１７８５１５号公報
【特許文献２】特開２００２−２０７７５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
近年、時間情報及び属性情報が付随したイベントを簡便に収集・蓄積できる環境が整備されており、これらのイベントデータを分析し、人間の意思決定に役立てたいとのニーズが高まっている。
【０００６】
イベントデータを分析する従来の手法では、まず、個々のイベントに付随する時間情報や属性情報に基づいてイベントをグループ化し、系列データを生成する。次に、この系列データの集合から、系列データ集合中に頻繁に現れる部分系列を頻出系列パターンとして抽出する。この頻出系列パターンは、与えられた系列データ集合を代表するパターンになっているものの、分析者にとっては、ありふれたパターンである場合が多い。このため、分析者に新たな知見を与える特徴的な系列パターンを発見するには、発見された頻出系列パターンの中から、他の基準（例えば信頼度）に基づいて特徴的な系列パターンを発見する必要がある。
【０００７】
ここで、「頻出」と判定する基準を高くすることにより最初に発見される頻出系列パターンの数を少なくし過ぎると、特徴的な系列パターンが見落とされる可能性があり、一方、「頻出」と判定する基準を低くし過ぎると、多数の頻出系列パターンの中に特徴的な系列パターンが埋もれてしまう可能性があるという問題点がある。したがって、このようなトレードオフの問題点を解決し、特徴的な系列パターンを効率よく発見するための新たな手法の確立が望まれている。
【０００８】
本発明は、かかる事情を考慮してなされたものであり、コンピュータ上に時間を追って蓄積される系列データの中から、出現頻度がそれ程多くないとしても、利用者にとって興味が高いと考えられるような特徴的な系列パターンを発見できる装置及びその作動方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一観点に係る特徴系列パターン発見装置は、複数のイベントからなる系列データを格納する系列データ格納部と、既に発見された特徴系列パターンを格納する特徴系列パターン格納部と、前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成する候補系列パターン生成部と、前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数に相当する、前記候補系列パターンの頻度を計算する系列パターン頻度計算部と、前記特徴系列パターンにおける部分系列パターンの頻度を格納する部分系列パターン頻度格納部と、前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの頻度から、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、前記候補系列パターンの評価値を計算する候補系列パターン評価部と、前記評価値が閾値を超えるか否かを判定する候補系列パターン判定部と、を具備し、前記閾値を超える候補系列パターンを新たな特徴系列パターンとして前記特徴系列パターン格納部に格納することを具備する特徴系列パターン発見装置である。
【発明の効果】
【００１０】
本発明によれば、コンピュータ上に時間を追って蓄積される系列データの中から、出現頻度がそれ程多くないとしても、利用者にとって興味が高いと考えられるような特徴的な系列パターンを効率的に発見できる装置及びその作動方法を提供することができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の実施形態を説明する。図１は、本発明の一実施形態に係る特徴系列パターン発見装置を示すブロック図である。本装置は、コンピュータ上に時間を追って蓄積される系列データ、例えば、小売り分野における日々の売上げデータ及び業務報告を記載した日報、健康管理分野における日々の血圧・脈拍等の生体データ及び個人の行動を記録した行動記録、金融分野における日々の株価データ及び新聞等に記載されているニュース等といった系列データに内在する特徴的な系列パターンを発見し、利用者の意思決定を支援するための装置に関する。同図に示されるように、本装置は系列データ格納部Ｂ１と、候補系列パターン生成部Ｂ２と、系列パターン頻度計算部Ｂ３と、部分系列パターン頻度格納部Ｂ４と、候補系列パターン評価部Ｂ５と、候補系列パターン判定部Ｂ６と、特徴系列パターン格納部Ｂ７とにより構成されている。本発明は、コンピュータをこのような構成の特徴系列パターン発見装置として機能させるプログラムとして実施することができる。この場合、本発明に係るプログラムは、コンピュータ内のプログラム記憶装置に格納される。プログラム記憶装置は、例えば不揮発性半導体記憶装置や磁気ディスク装置等からなる。上記プログラムが図示しないＣＰＵからの制御でランダムアクセスメモリ（ＲＡＭ）に読み込まれ、同ＣＰＵにより実行されることにより、コンピュータを本発明に係る特徴系列パターン発見装置として機能させることができる。なお、このコンピュータには、各種コンピュータ資源を管理し、グラフィカルユーザインタフェース（ＧＵＩ）等を提供するオペレーティングシステムも導入されている。
【００１２】
以下、図２、図３、図４に示すフローチャートに沿って、本実施形態に係る特徴系列パターン発見装置の処理の流れを説明する。
【００１３】
本実施形態に係る特徴系列パターン発見装置の系列データ格納部Ｂ１には、例えば図５に示すような系列データが格納されているものとする。ここでいう「系列データ」とは、複数のイベントからなるデータをいい、より具体的には、同一の時間帯に起こるイベントをまとめたイベント集合が時間順に並べられたデータのことである。図５に示す系列データにおいて、系列データの各行を構成するイベントＩＤ  ａ〜ｅは図６に示すイベント名に対応している。また、系列データＩＤ  Ｄ２の例の場合、ａ、（ｂｅ）、ｄ、ｂの４つの要素から１つの系列データ（セグメント）が構成されており、２番目の系列データの要素は、同一の時間帯に発生するふたつのイベントｂ、ｅから構成されている。すなわち、ＩＤにより識別される１つの系列データ（セグメント）は１つまたは複数の要素からなり、該要素は１つまたは複数のイベントからなる。
【００１４】
図２乃至図４に沿って本装置の処理の流れを説明するのに先立って、「系列データ」以外の他の用語についても定義しておく。
【００１５】
・「系列パターン」とはイベント集合が時間順に並んだものをいい、系列データの中から抽出されるものとする。
【００１６】
・「系列データが系列パターンを包含する」とは、次の条件が成り立つことをいう。すなわち、系列データをｅｄ１，ｅｄ２，…，ｅｄｍとし、系列パターンをｅｐ１，ｅｐ２，…，ｅｐｎとした場合、ｅｐｋ⊆ｅｄｉｋ，（ｋ＝１，２，…，ｎ），０＜ｉ１＜ｉ２＜…＜ｉｎとなる整数列｛ｉ１，ｉ２，…，ｉｎ｝が存在するという条件である。ただし、ｅｄｉ及びｅｐｊはイベント集合を表すものとする。
【００１７】
・系列パターンｐ１が系列パターンｐ２を包含する場合、系列パターンｐ２を系列パターンｐ１の「部分系列パターン」という。
【００１８】
・「系列パターンの頻度」とは系列パターンを包含する系列データの個数をいう。
【００１９】
先ず図２に示すようにステップＳ１では、系列データ格納部Ｂ１に格納されている系列データの中から、候補系列パターン生成部Ｂ２が順にひとつの系列データを読み込む。
【００２０】
ステップＳ２では、系列データ格納部から読み出す系列データが存在するかどうかを候補系列パターン生成部Ｂ２で判定し、存在しない場合にはステップＳ４に進む。一方、存在する場合にはステップＳ３に進む。図５の系列データの場合、６個の系列データが存在しているので、６回目まではステップＳ３に進み、７回目にステップＳ４に進むことになる。
【００２１】
ステップＳ３では、候補系列パターン生成部Ｂ２が読み込んだひとつの系列データをイベントに分解し、重複するイベントを取り除いてバッファ等に記憶しておく。図５の例の場合には、当該ステップの６回の実行により、図６に示す５つのイベントが抽出される。
【００２２】
ステップＳ４では、候補系列パターン生成部Ｂ２が上記バッファからイベントを順に取り出す。ここで、取り出すことのできるイベントがあるかどうかを候補系列パターン生成部Ｂ２が判定し、取り出すイベントがない場合にはステップＳ８に進む。一方、取り出すイベントがある場合には、ステップＳ５に進む。図６の場合、５つのイベントが存在するので、５回目まではステップＳ５に進み、６回目にステップＳ８に進むことになる。
【００２３】
ステップＳ５では、まず、取り出されたイベントの頻度を系列パターン頻度計算部Ｂ３が計算する。図５の系列データの場合、イベントＩＤがａとなるイベントは、すべての系列データに包含されているので、イベントＩＤ  ａの頻度は６と計算される。同様な計算を各回において実施することにより、イベントＩＤ  ｂ，ｃ，ｄ，ｅに対応した頻度は、５，３，４，３と計算される。
【００２４】
次に、候補系列パターン評価部Ｂ５は次の式（１）に基づいてイベントの興味度（評価値）を計算する。
【数３】
0004398907.tif 000002
【００２５】
ただし、ｓを系列パターン、ｓｐを系列パターンｓの部分系列パターン、ｆｓ（）を系列パターン又は部分系列パターンの頻度、Ｎを系列データの個数とする。また、イベントは系列パターンに含まれるイベントの個数が１となる場合であり、ｓ＝ｓｐとなる。一方、式（１）のように系列パターンの評価値を計算することにより、系列パターンの興味度をそのすべての部分系列パターンの興味度以下にすることができる。
【００２６】
図５の系列データに対して、イベントＩＤ  ａに対応する興味度を計算した場合、その値は次のようになる。
【数４】
0004398907.tif 000003
【００２７】
また、イベントＩＤ  ｂに対応する興味度の値は次のとおり計算される。
【数５】
0004398907.tif 000004
【００２８】
同様に、イベントＩＤ  ｃ，ｄ，ｅの興味度は図７に示すように計算することができる。
【００２９】
ステップＳ６では、候補系列パターン判定部Ｂ６がイベントの興味度の値と予め設定されている最小興味度（Ｔｈ１；閾値）の値とを比較し、最小興味度以上であればステップＳ８に進む。一方、最小興味度未満である場合にはステップＳ４に戻る。図５の系列データに対する最小興味度を０．２と設定した場合、すべてのイベントの興味度は０．２以上となるので、すべてのイベントについてステップＳ８に進むことになる。
【００３０】
ステップＳ７において、候補系列パターン判定部Ｂ６は、最小興味度以上となったイベント及びその頻度を、１次特徴イベント集合及びその最大頻度として特徴系列パターン格納部Ｂ７及び部分系列パターン頻度格納部Ｂ４に格納する。図５の系列データに対する最小興味度を０．２と設定した場合、図７のイベントの列及び最大頻度の列は、１次系列パターン及び最大頻度として特徴系列パターン格納部Ｂ７及び部分系列パターン頻度格納部Ｂ４に格納される。
【００３１】
次に図３に示すように、ステップＳ８では、特徴系列パターン格納部Ｂ７に格納されている（Ｌ−１）次特徴イベント集合の中から、イベント集合の前方（Ｌ−２）個のイベントが一致しているふたつのイベント集合を候補系列パターン生成部Ｂ２が抽出する。だだし、イベント集合は指定された順序（例えば、イベントＩＤの辞書順）で並んでいるものとする。（Ｌ−１）次特徴イベント集合とは（Ｌ−１）個のイベントによって構成された特徴的なイベントの集合のことである。次に、候補系列パターン生成部Ｂ２は抽出したふたつの（Ｌ−１）次特徴イベント集合を組み合わせることにより、Ｌ次イベント集合を生成する。
【００３２】
すなわち、共通する（Ｌ−２）個のイベントに、（Ｌ−１）次特徴イベント集合に残った各１個のイベントを加えることにより、Ｌ次イベント集合が生成される。このとき、Ｌ次イベント集合は指定された順序によって並べ替えておくことにする。この生成されたＬ次イベント集合を「Ｌ次特徴イベント集合候補」という。
【００３３】
例えば、１次特徴イベント集合から２次特徴イベント集合候補を生成する場合を考えてみる。このとき、候補系列パターン生成部Ｂ２は１次特徴イベント集合として、ａ，ｂを初めに選択する。ただし、Ｌ＝２の場合においては、イベント集合の前方に（Ｌ−２）個のイベントが存在していないので、本条件は考慮せずにイベント集合を抽出する。次に、このふたつのイベント集合から２次のイベント集合（ａｂ）を生成する。ただし、イベント集合はイベントＩＤのアルファベット順に並べられることとする。
【００３４】
同様に、２次特徴イベント集合から３次特徴イベント集合候補を生成する場合を考えてみる。詳細については後述するが、図５の例の場合、（ｂｃ）、（ｂｅ）が２次特徴イベント集合となる。当該２次特徴イベント集合の場合、前方に存在する１個のイベント集合がｂと共通しているため、当該イベント集合から３次特徴イベント集合候補を生成することができる。すなわち、（ｂｃｅ）といったイベント集合が３次特徴イベント集合候補として生成される。
【００３５】
ステップＳ９では、候補系列パターン生成部Ｂ２が生成するＬ次特徴イベント集合が存在するかどうかを判断し、存在しない場合にはステップＳ１３に進む。一方、存在する場合には、ステップＳ１０に進む。図５の例における２次特徴イベント集合候補の生成の場合、２次特徴イベント集合候補は図８の２次イベント集合の列に示す１０個存在するので、１０回目まではステップＳ１０に進み。１１回目にステップＳ１３に進むことになる。
【００３６】
ステップＳ１０では、生成されたＬ次特徴イベント集合候補の頻度を系列パターン頻度計算部Ｂ３が計算する。図５の例における２次特徴イベント集合候補の生成の場合、各イベント集合の頻度は図８の頻度の列のように与えられる。また、図５の例における３次特徴イベント集合候補の生成の場合、各イベント集合の頻度は図９の頻度の列のように与えられる。
【００３７】
次に、候補系列パターン評価部Ｂ５は、系列パターン頻度計算部Ｂ３で計算された頻度及び特徴系列パターン格納部Ｂ７に格納されている（Ｌ−１）次特徴イベント集合の最大頻度を式（１）に適用することにより、生成されたＬ次特徴イベント集合候補についての興味度を計算する。例として、２次特徴イベント集合（ｂｃ）の興味度を計算することを考えてみる。このとき、ｂ，ｃの最大頻度が５，３と与えられており、（ｂｃ）の頻度が３と与えられるので、興味度は次のように与えられる。
【数６】
0004398907.tif 000005
【００３８】
同様に、３次特徴イベント集合（ｂｃｅ）の興味度を計算することを考えてみる。このとき、後のステップＳ１２において説明する最大頻度の計算方法によれば、（ｂｃ）、（ｂｅ）の最大頻度は５，５と与えられるので、興味度は
【数７】
0004398907.tif 000006
【００３９】
と与えられる。上記の計算例において、２次の場合における（ｂｃ）、３次の場合におけるｂ，ｃ，ｅ，（ｃｅ），（ｂｃｅ）に対応する部分系列パターンの頻度を評価していないことに注意する必要がある。このような評価が可能であるのは、系列パターンに対応する最大頻度の設定方法に関連した性質を利用しているためであり、ステップＳ１２において最大頻度を設定する際に理由を説明する。
【００４０】
ステップＳ１１では、候補系列パターン判定部Ｂ６がＬ次特徴イベント集合に対応する興味度が最小興味度以上であるかを判定し、最小興味度以上である場合にステップＳ１２に進む。一方、最小興味度未満の場合にはステップＳ８に戻る。２次特徴イベント集合候補の判定の場合、（ｂｃ），（ｂｅ）の場合に最小興味度０．２以上となるので、ステップＳ１２に進み、（ａｂ），（ａｃ），（ａｄ），（ｂｄ），（ｃｄ），（ｃｅ），（ｄｅ）の場合にステップＳ８に戻ることになる。
【００４１】
ステップＳ１２では、興味度が最小興味度以上となるＬ次特徴イベント集合候補を、候補系列パターン判定部Ｂ６がＬ次特徴イベント集合として特徴系列パターン格納部Ｂ７に格納する。また、対応する最大頻度として、Ｌ次特徴イベント集合を生成する元になったふたつの（Ｌ−１）次特徴イベント集合の最大頻度の値を当該Ｌ次特徴イベント集合の最大頻度として部分系列パターン頻度格納部Ｂ４に格納する。系列パターンの頻度は、その部分系列パターンの頻度以下になるといった性質が存在する。このため、部分系列パターンの頻度の逆数を考えた場合には、より短い部分系列パターンに対応した逆数の中に最小値が存在する。したがって、最も短い部分系列パターンであるイベントに対応した逆数の中に最小値が存在する。このため、系列パターンを構成するイベントの頻度の最大値（最大頻度）を部分系列パターンの頻度として部分系列パターン頻度格納部Ｂ４に記憶しておくことにより、候補系列パターン評価部Ｂ５は、Ｌ次特徴イベント集合を構成するのに利用した（Ｌ−１）次イベント集合のふたつの最大頻度だけを評価して、興味度を計算することができる。
【００４２】
このステップＳ１２において、候補系列パターン生成部Ｂ２は、特徴系列パターン格納部Ｂ７に格納されている特徴イベント集合をすべて併合することにより１次特徴系列パターンを生成する。図５の例の場合、図７に記述されている５個の１次特徴イベント集合及び図８に最大頻度が与えられて記述されている２個の２次イベント集合が１次特徴系列パターンとなる。
【００４３】
次に図４に示すように、ステップＳ１４では、候補系列パターン生成部Ｂ２が系列の前方の（Ｌ−２）個のイベント集合が一致するふたつの（Ｌ−１）次系列パターンを抽出する。また、その取り出した順序を考慮して、抽出した系列パターンからＬ次特徴系列パターン候補を生成する。例として、１次系列パターンａ，（ｂｅ）が順次取り出されて、このふたつのパターンから２次特徴系列パターン候補を生成する場合を考えてみる。ただし、２次特徴系列パターン候補の生成の場合には、前方の（Ｌ−２）個のイベント集合は存在しないので当該条件は適用されていない。このとき、当該１次特徴系列パターンからａ（ｂｅ）といった２次特徴系列パターンを生成することができる。また、前方の１個のイベント集合が共通している２次系列パターンａ（ｂｅ），ａｂが順次取り出されて、このふたつのパターンから３次特徴系列パターン候補を生成する場合を考えてみる。ここで、当該のふたつの特徴系列パターンにおいては、前方の１個のイベント集合ａが共通しているため、ａ（ｂｅ）ｂといった３次の特徴系列パターン候補を生成することができる。
【００４４】
ステップ１５では、候補系列パターン生成部Ｂ２がＬ次特徴系列パターン候補が生成できたかどうかを判定し、生成できなかった場合にステップＳ１９に進む。一方、生成できた場合にステップＳ１６に進む。
【００４５】
ステップＳ１６では、系列パターン頻度計算部Ｂ３が当該特徴系列パターン候補の頻度を計算する。図５の例の場合、２次、３次、４次の各系列パターン候補に対して図１０、図１１、図１２の頻度の列に示す値が頻度として計算される。
【００４６】
ただし、各図においては、後に計算する興味度が最小興味度以上の興味度をもつ系列パターン候補に対してのみ、頻度を計算した結果を示している。
【００４７】
また、候補系列パターン評価部Ｂ５は、系列パターン頻度計算部Ｂ３により計算されたＬ次特徴系列パターン候補及び特徴系列パターン格納部Ｂ７に格納されている、対応する最大頻度を式（１）に適用することにより興味度を計算する。例として、２次特徴系列パターン候補ａ（ｂｅ）の興味度を計算してみると、興味度は、
【数８】
0004398907.tif 000007
【００４８】
と与えられる。
【００４９】
また、３次特徴系列パターン候補ａ（ｂｅ）ｂの興味度は、
【数９】
0004398907.tif 000008
【００５０】
と計算される。同様に、２次、３次、４次の各系列パターン候補に対して図１０、図１１、図１２に示すように興味度の値が計算される。ただし、興味度が最小興味度以上になる特徴系列パターン候補に対してのみ結果を示している。上記の計算において、Ｌ次特徴系列パターン候補の生成の際に利用した最大頻度に基づいて興味度を計算できる理由は、ステップＳ１２で説明したことと同様の理由による。
【００５１】
ステップＳ１７では、候補系列パターン判定部Ｂ６がＬ次特徴系列パターン候補の興味度が最小興味度以上であるかどうかを判定し、最小興味度以上の場合にステップＳ１８に進む。一方、最小興味度未満の場合には、ステップＳ１４に戻る。例えば、３次特徴系列パターン候補ａｂｂの場合には、最小興味度以上となるためステップＳ１８に進み、図１２に示す４次特徴系列パターン候補ａｂｂｂの場合には最小興味度未満となるためステップＳ１４に戻る。
【００５２】
ステップＳ１８では、候補系列パターン判定部Ｂ６が興味度以上となるＬ次特徴系列パターン候補を、Ｌ次特徴系列パターンとして特徴系列パターン格納部Ｂ７に格納する。また、当該特徴系列パターンを生成する際に利用したふたつの（Ｌ−１）次特徴系列パターンの最大頻度の最大値を当該パターンに対する最大頻度として、部分系列パターン頻度格納部Ｂ４に格納する。図５の例の場合、図１０、図１１の最大頻度の列に記載されている値が、対応する最大頻度として格納される。
【００５３】
ステップＳ１５では、特徴系列パターン格納部Ｂ７にひとつ以上のＬ次特徴系列パターン候補が格納されているかどうかを候補系列パターン生成部Ｂ２が判定する。このとき、Ｌ次特徴系列パターン候補がひとつ以上格納されている場合には、ステップＳ１４に進み、ひとつも格納されていない場合には本フローの処理を終了する。図５の例の場合、４次特徴系列パターン候補を生成した段階でひとつも４次特徴系列パターンを発見することができないので、本フローの処理を終了する。
【００５４】
ステップＳ１９では、系列を延伸可能であれば、候補系列パターン生成部Ｂ２が系列のサイズを１増やして、ステップＳ１４に戻る。
【００５５】
最終的には、図７に示される全てのイベント、図８に示される（ｂｃ）と（ｂｅ）、図１０および図１１に示される全てのパターンが、特徴系列パターンとして抽出される。
【００５６】
以上説明したように、本実施形態によれば、分析者に新たな知見を与えるような有用で特徴的な系列パターンを取りこぼすことなく発見することができる。また、系列パターンの評価値を系列パターンに含まれるイベントに対して単調減少するように定義していることから、特徴系列パターンに含まれるすべての部分系列パターンの評価値は当該特徴系列パターンの評価値以上となり、すべての部分系列パターンが特徴系列パターンとなる。したがって、部分系列パターンが特徴系列パターンにならない系列パターンを候補系列パターンとして評価する必要がなくなり、効率的に特徴系列パターンを発見することができる。
【００５７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【００５８】
例えば、特徴系列パターンの格納において、系列サイズごとに抽出されたすべての特徴系列パターンを系列パターン格納部Ｂ７に格納することにしているが、より長い系列サイズに含まれる特徴系列パターンは特徴系列パターン格納部Ｂ７から削除することにしてもよい。
【００５９】
また、Ｌ次特徴系列パターンの頻度を計算するにあたって、その元になった（Ｌ−１）次特徴系列パターンが含まれる系列データを記憶しておき、系列データの部分集合にアクセスすることによりＬ次特徴系列パターン候補の頻度を計算してもよい。
【００６０】
また、分析者が興味のある部分系列パターンを指定し、当該部分系列パターンを含む特徴系列パターンだけを最終的に抽出するようにしてもよい。
【００６１】
さらに、上記した式（１）は、下記の式（２）のように変形することができる。この場合、系列パターンの頻度が比較的高く（式（２）の第２項に相当）、系列パターンに含まれる特定のイベントとその系列パターンの間に高い関連性（式（２）の第１項に相当）がある系列パターンを特徴的な系列パターンとして発見することができる。
【数１０】
0004398907.tif 000009
【図面の簡単な説明】
【００６２】
【図１】本発明の一実施形態に係る特徴系列パターン発見装置を示すブロック図
【図２】上記特徴系列パターン発見装置が実行する頻出イベント抽出手順を示すフローチャート
【図３】上記特徴系列パターン発見装置が実行する特徴イベント集合抽出手順を示すフローチャート
【図４】上記特徴系列パターン発見装置が実行する特徴イベントパターン抽出手順を示すフローチャート
【図５】系列データ集合の一例を示す図
【図６】イベント名とイベントＩＤとの対応を示す図
【図７】図５の系列データから取り出される１次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図８】図５の系列データから取り出される２次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図９】図５の系列データから取り出される興味度が０．２以上となる２次特徴イベント集合から生成された、３次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図１０】図５の系列データから取り出される興味度が０．２以上となる２次系列パターンと、その頻度、興味度、および最大頻度との関係を示す図
【図１１】図５の系列データから取り出される興味度が０．２以上となる３次系列パターンと、その頻度、興味度、および最大頻度との関係を示す図
【図１２】図５の系列データから取り出される興味度が０．２以上となる３次系列パターンから生成された、４次系列パターン候補と、その頻度、興味度、および最大頻度との関係を示す図
【符号の説明】
【００６３】
Ｂ１…系列データ格納部；
Ｂ２…候補系列パターン生成部；
Ｂ３…系列パターン頻度計算部；
Ｂ４…部分系列パターン頻度格納部；
Ｂ５…候補系列パターン評価部；
Ｂ６…候補系列パターン判定部；
Ｂ７…特徴系列パターン格納部
【図１】
0004398907.tif 000014
【図２】
0004398907.tif 000015
【図３】
0004398907.tif 000016
【図４】
0004398907.tif 000017
【図５】
0004398907.tif 000018
【図６】
0004398907.tif 000019
【図７】
0004398907.tif 000020
【図８】
0004398907.tif 000021
【図９】
0004398907.tif 000022
【図１０】
0004398907.tif 000023
【図１１】
0004398907.tif 000024
【図１２】
0004398907.tif 000025