米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社東芝

発明の名称 特徴系列パターン発見装置及び特徴系列パターン発見装置の作動方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−11488(P2007−11488A)
公開日 平成19年1月18日(2007.1.18)
出願番号 特願2005−188453(P2005−188453)
出願日 平成17年6月28日(2005.6.28)
代理人 【識別番号】100058479
【弁理士】
【氏名又は名称】鈴江 武彦
発明者 櫻井 茂明
要約 課題
特徴的な系列パターンを効率的に発見できる装置及びその作動方法を提供する。

解決手段
系列データ格納部からイベントを取り出して候補系列パターンを生成する。系列データのうち候補系列パターンを包含する系列データの個数に相当する、系列パターンの頻度を計算する。計算された系列パターンの頻度及び既に発見された特徴系列パターンにおける部分系列パターンの頻度から、より多くのイベントを含む系列パターンに対して単調に減少する評価値を与える評価式に従い、候補系列パターンの評価値を計算する。この評価値が閾値を超えるか否かを判定し、閾値を超える候補系列パターンを特徴的な系列パターンとする。
特許請求の範囲
【請求項1】
複数のイベントからなる系列データを格納する系列データ格納部と、
既に発見された特徴系列パターンを格納する特徴系列パターン格納部と、
前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成する候補系列パターン生成部と、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数に相当する、前記候補系列パターンの頻度を計算する系列パターン頻度計算部と、
前記特徴系列パターンにおける部分系列パターンの頻度を格納する部分系列パターン頻度格納部と、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの頻度から、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、前記候補系列パターンの評価値を計算する候補系列パターン評価部と、
前記評価値が閾値を超えるか否かを判定する候補系列パターン判定部と、を具備し、
前記閾値を超える候補系列パターンを新たな特徴系列パターンとして前記特徴系列パターン格納部に格納することを具備する特徴系列パターン発見装置。
【請求項2】
前記特徴系列パターンは、前記系列データから抽出され、時間順に並んだイベント集合からなる請求項1に記載の特徴系列パターン発見装置。
【請求項3】
前記候補系列パターン評価部は、sを系列パターン、spを系列パターンsの部分系列パターン、fs()を系列パターンの頻度、Nを系列データの個数とするとき、前記評価値に相当する興味度を次式(1)すなわち
【数1】


に従って算出する請求項1に記載の特徴系列パターン発見装置。
【請求項4】
前記候補系列パターン評価部は、sを系列パターン、spを系列パターンsの部分系列パターン、fs()を系列パターンの頻度、Nを系列データの個数とするとき、前記評価値に相当する興味度を次式(2)すなわち
【数2】


に従って算出する請求項1に記載の特徴系列パターン発見装置。
【請求項5】
系列データ格納部に格納された複数のイベントからなる系列データと特徴系列パターン格納部に格納され、既に発見された特徴系列パターンとから新たな特徴系列パターンを発見する特徴系列パターン発見装置の作動方法であって、
候補系列パターン生成部が、前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成するステップと、
前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数に相当する、前記候補系列パターンの頻度を系列パターン頻度計算部が計算するステップと、
前記特徴系列パターンにおける部分系列パターンの頻度を部分系列パターン頻度格納部が格納するステップと、
前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの頻度から、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、候補系列パターン評価部が前記候補系列パターンの評価値を計算するステップと、
前記評価値が閾値を超えるか否かを候補系列パターン判定部が判定するステップとを具備し、
前記閾値を超える候補系列パターンが前記新たな特徴系列パターンとして前記特徴系列パターン格納部に格納されることを特徴とする特徴系列パターン発見装置の作動方法。
発明の詳細な説明
【技術分野】
【0001】
本発明は、コンピュータ上に時間を追って蓄積される系列データ、例えば、小売り分野における日々の売上げデータ及び業務報告を記載した日報、健康管理分野における日々の血圧・脈拍等の生体データ及び個人の行動を記録した行動記録、金融分野における日々の株価データ及び新聞等に記載されているニュース等といった系列データに内在する特徴的な系列パターンを発見し、利用者の意思決定を支援するための装置及びその作動方法に関するものである。
【背景技術】
【0002】
GSP(Generalized Sequential Patterns)アルゴリズムでは、多数の要素から構成される系列データを入力とし、その系列データ集合の中において頻出する系列パターンを発見することができる。しかしながら、本手法において発見される頻出系列パターンは、分析者にとっては既知の系列パターンである場合が多く、必ずしも分析者に新たな知見を与えることができない。また、少ない頻度を指定して頻出系列パターンを発見する場合には、多数の頻出系列パターンを発見することになるため、すべての頻出系列パターンを発見するのに多くの時間が必要となるばかりか、新たな知見を与える特徴的な系列パターンが多数の頻出系列パターンの中に埋もれてしまう危険性がある。
【0003】
下記特許文献1に記載の「意外性に基づく状態列パターンの評価装置」では、系列パターンに対して意外性を定義することにより、系列パターンの中から特徴的な系列パターンを発見することができる。しかしながら、本装置においては、意外性の有無の判定のための候補系列パターンが発見されていることを前提としており、意外性のある系列パターンを発見するには上記GSPなどの手法を利用して予め候補となる系列パターンを発見しなければならない。また、候補となる系列パターンの頻度の増減と意外性の値の増減との間には単調な関係が存在しないことから、低頻度の系列パターンをも候補として発見しなければ、すべての意外性のある系列パターンを発見することができない。このため、候補となる系列パターンを発見するのに多くの時間が必要である。
【0004】
下記特許文献2に記載の「イベントデータに関する情報管理装置」では、対象となる問題領域において、時系列的に発生するイベントを利用することにより、問題領域における事例の重要度を更新し、現在の時間に合った重要度の高い事例を抽出することができる。しかしながら、本装置においては、問題領域に対応する事例の抽出の際に、時間を勘案して事例を抽出しているだけであり、時系列的なパターンを発見することはできない。
【特許文献1】特開2004−178515号公報
【特許文献2】特開2002−207755号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
近年、時間情報及び属性情報が付随したイベントを簡便に収集・蓄積できる環境が整備されており、これらのイベントデータを分析し、人間の意思決定に役立てたいとのニーズが高まっている。
【0006】
イベントデータを分析する従来の手法では、まず、個々のイベントに付随する時間情報や属性情報に基づいてイベントをグループ化し、系列データを生成する。次に、この系列データの集合から、系列データ集合中に頻繁に現れる部分系列を頻出系列パターンとして抽出する。この頻出系列パターンは、与えられた系列データ集合を代表するパターンになっているものの、分析者にとっては、ありふれたパターンである場合が多い。このため、分析者に新たな知見を与える特徴的な系列パターンを発見するには、発見された頻出系列パターンの中から、他の基準(例えば信頼度)に基づいて特徴的な系列パターンを発見する必要がある。
【0007】
ここで、「頻出」と判定する基準を高くすることにより最初に発見される頻出系列パターンの数を少なくし過ぎると、特徴的な系列パターンが見落とされる可能性があり、一方、「頻出」と判定する基準を低くし過ぎると、多数の頻出系列パターンの中に特徴的な系列パターンが埋もれてしまう可能性があるという問題点がある。したがって、このようなトレードオフの問題点を解決し、特徴的な系列パターンを効率よく発見するための新たな手法の確立が望まれている。
【0008】
本発明は、かかる事情を考慮してなされたものであり、コンピュータ上に時間を追って蓄積される系列データの中から、出現頻度がそれ程多くないとしても、利用者にとって興味が高いと考えられるような特徴的な系列パターンを発見できる装置及びその作動方法を提供することを目的とする。
【課題を解決するための手段】
【0009】
本発明の一観点に係る特徴系列パターン発見装置は、複数のイベントからなる系列データを格納する系列データ格納部と、既に発見された特徴系列パターンを格納する特徴系列パターン格納部と、前記特徴系列パターン格納部に格納されている特徴系列パターンの組において一致するイベント又はイベント集合に対し、前記系列データ格納部から取り出したイベント又はイベント集合を加えることにより候補系列パターンを生成する候補系列パターン生成部と、前記系列データ格納部に格納された系列データのうち前記候補系列パターンを包含する系列データの個数に相当する、前記候補系列パターンの頻度を計算する系列パターン頻度計算部と、前記特徴系列パターンにおける部分系列パターンの頻度を格納する部分系列パターン頻度格納部と、前記系列パターン頻度計算部により計算された候補系列パターンの頻度及び前記部分系列パターン頻度格納部に格納されている部分系列パターンの頻度から、より多くのイベントを含む候補系列パターンに対して単調に減少する評価値を与える評価式に従い、前記候補系列パターンの評価値を計算する候補系列パターン評価部と、前記評価値が閾値を超えるか否かを判定する候補系列パターン判定部と、を具備し、前記閾値を超える候補系列パターンを新たな特徴系列パターンとして前記特徴系列パターン格納部に格納することを具備する特徴系列パターン発見装置である。
【発明の効果】
【0010】
本発明によれば、コンピュータ上に時間を追って蓄積される系列データの中から、出現頻度がそれ程多くないとしても、利用者にとって興味が高いと考えられるような特徴的な系列パターンを効率的に発見できる装置及びその作動方法を提供することができる。
【発明を実施するための最良の形態】
【0011】
以下、図面を参照しながら本発明の実施形態を説明する。図1は、本発明の一実施形態に係る特徴系列パターン発見装置を示すブロック図である。本装置は、コンピュータ上に時間を追って蓄積される系列データ、例えば、小売り分野における日々の売上げデータ及び業務報告を記載した日報、健康管理分野における日々の血圧・脈拍等の生体データ及び個人の行動を記録した行動記録、金融分野における日々の株価データ及び新聞等に記載されているニュース等といった系列データに内在する特徴的な系列パターンを発見し、利用者の意思決定を支援するための装置に関する。同図に示されるように、本装置は系列データ格納部B1と、候補系列パターン生成部B2と、系列パターン頻度計算部B3と、部分系列パターン頻度格納部B4と、候補系列パターン評価部B5と、候補系列パターン判定部B6と、特徴系列パターン格納部B7とにより構成されている。本発明は、コンピュータをこのような構成の特徴系列パターン発見装置として機能させるプログラムとして実施することができる。この場合、本発明に係るプログラムは、コンピュータ内のプログラム記憶装置に格納される。プログラム記憶装置は、例えば不揮発性半導体記憶装置や磁気ディスク装置等からなる。上記プログラムが図示しないCPUからの制御でランダムアクセスメモリ(RAM)に読み込まれ、同CPUにより実行されることにより、コンピュータを本発明に係る特徴系列パターン発見装置として機能させることができる。なお、このコンピュータには、各種コンピュータ資源を管理し、グラフィカルユーザインタフェース(GUI)等を提供するオペレーティングシステムも導入されている。
【0012】
以下、図2、図3、図4に示すフローチャートに沿って、本実施形態に係る特徴系列パターン発見装置の処理の流れを説明する。
【0013】
本実施形態に係る特徴系列パターン発見装置の系列データ格納部B1には、例えば図5に示すような系列データが格納されているものとする。ここでいう「系列データ」とは、複数のイベントからなるデータをいい、より具体的には、同一の時間帯に起こるイベントをまとめたイベント集合が時間順に並べられたデータのことである。図5に示す系列データにおいて、系列データの各行を構成するイベントID a〜eは図6に示すイベント名に対応している。また、系列データID D2の例の場合、a、(be)、d、bの4つの要素から1つの系列データ(セグメント)が構成されており、2番目の系列データの要素は、同一の時間帯に発生するふたつのイベントb、eから構成されている。すなわち、IDにより識別される1つの系列データ(セグメント)は1つまたは複数の要素からなり、該要素は1つまたは複数のイベントからなる。
【0014】
図2乃至図4に沿って本装置の処理の流れを説明するのに先立って、「系列データ」以外の他の用語についても定義しておく。
【0015】
・「系列パターン」とはイベント集合が時間順に並んだものをいい、系列データの中から抽出されるものとする。
【0016】
・「系列データが系列パターンを包含する」とは、次の条件が成り立つことをいう。すなわち、系列データをed1,ed2,…,edmとし、系列パターンをep1,ep2,…,epnとした場合、epk⊆edik,(k=1,2,…,n),0<i1<i2<…<inとなる整数列{i1,i2,…,in}が存在するという条件である。ただし、edi及びepjはイベント集合を表すものとする。
【0017】
・系列パターンp1が系列パターンp2を包含する場合、系列パターンp2を系列パターンp1の「部分系列パターン」という。
【0018】
・「系列パターンの頻度」とは系列パターンを包含する系列データの個数をいう。
【0019】
先ず図2に示すようにステップS1では、系列データ格納部B1に格納されている系列データの中から、候補系列パターン生成部B2が順にひとつの系列データを読み込む。
【0020】
ステップS2では、系列データ格納部から読み出す系列データが存在するかどうかを候補系列パターン生成部B2で判定し、存在しない場合にはステップS4に進む。一方、存在する場合にはステップS3に進む。図5の系列データの場合、6個の系列データが存在しているので、6回目まではステップS3に進み、7回目にステップS4に進むことになる。
【0021】
ステップS3では、候補系列パターン生成部B2が読み込んだひとつの系列データをイベントに分解し、重複するイベントを取り除いてバッファ等に記憶しておく。図5の例の場合には、当該ステップの6回の実行により、図6に示す5つのイベントが抽出される。
【0022】
ステップS4では、候補系列パターン生成部B2が上記バッファからイベントを順に取り出す。ここで、取り出すことのできるイベントがあるかどうかを候補系列パターン生成部B2が判定し、取り出すイベントがない場合にはステップS8に進む。一方、取り出すイベントがある場合には、ステップS5に進む。図6の場合、5つのイベントが存在するので、5回目まではステップS5に進み、6回目にステップS8に進むことになる。
【0023】
ステップS5では、まず、取り出されたイベントの頻度を系列パターン頻度計算部B3が計算する。図5の系列データの場合、イベントIDがaとなるイベントは、すべての系列データに包含されているので、イベントID aの頻度は6と計算される。同様な計算を各回において実施することにより、イベントID b,c,d,eに対応した頻度は、5,3,4,3と計算される。
【0024】
次に、候補系列パターン評価部B5は次の式(1)に基づいてイベントの興味度(評価値)を計算する。
【数3】


【0025】
ただし、sを系列パターン、spを系列パターンsの部分系列パターン、fs()を系列パターン又は部分系列パターンの頻度、Nを系列データの個数とする。また、イベントは系列パターンに含まれるイベントの個数が1となる場合であり、s=spとなる。一方、式(1)のように系列パターンの評価値を計算することにより、系列パターンの興味度をそのすべての部分系列パターンの興味度以下にすることができる。
【0026】
図5の系列データに対して、イベントID aに対応する興味度を計算した場合、その値は次のようになる。
【数4】


【0027】
また、イベントID bに対応する興味度の値は次のとおり計算される。
【数5】


【0028】
同様に、イベントID c,d,eの興味度は図7に示すように計算することができる。
【0029】
ステップS6では、候補系列パターン判定部B6がイベントの興味度の値と予め設定されている最小興味度(Th1;閾値)の値とを比較し、最小興味度以上であればステップS8に進む。一方、最小興味度未満である場合にはステップS4に戻る。図5の系列データに対する最小興味度を0.2と設定した場合、すべてのイベントの興味度は0.2以上となるので、すべてのイベントについてステップS8に進むことになる。
【0030】
ステップS7において、候補系列パターン判定部B6は、最小興味度以上となったイベント及びその頻度を、1次特徴イベント集合及びその最大頻度として特徴系列パターン格納部B7及び部分系列パターン頻度格納部B4に格納する。図5の系列データに対する最小興味度を0.2と設定した場合、図7のイベントの列及び最大頻度の列は、1次系列パターン及び最大頻度として特徴系列パターン格納部B7及び部分系列パターン頻度格納部B4に格納される。
【0031】
次に図3に示すように、ステップS8では、特徴系列パターン格納部B7に格納されている(L−1)次特徴イベント集合の中から、イベント集合の前方(L−2)個のイベントが一致しているふたつのイベント集合を候補系列パターン生成部B2が抽出する。だだし、イベント集合は指定された順序(例えば、イベントIDの辞書順)で並んでいるものとする。(L−1)次特徴イベント集合とは(L−1)個のイベントによって構成された特徴的なイベントの集合のことである。次に、候補系列パターン生成部B2は抽出したふたつの(L−1)次特徴イベント集合を組み合わせることにより、L次イベント集合を生成する。
【0032】
すなわち、共通する(L−2)個のイベントに、(L−1)次特徴イベント集合に残った各1個のイベントを加えることにより、L次イベント集合が生成される。このとき、L次イベント集合は指定された順序によって並べ替えておくことにする。この生成されたL次イベント集合を「L次特徴イベント集合候補」という。
【0033】
例えば、1次特徴イベント集合から2次特徴イベント集合候補を生成する場合を考えてみる。このとき、候補系列パターン生成部B2は1次特徴イベント集合として、a,bを初めに選択する。ただし、L=2の場合においては、イベント集合の前方に(L−2)個のイベントが存在していないので、本条件は考慮せずにイベント集合を抽出する。次に、このふたつのイベント集合から2次のイベント集合(ab)を生成する。ただし、イベント集合はイベントIDのアルファベット順に並べられることとする。
【0034】
同様に、2次特徴イベント集合から3次特徴イベント集合候補を生成する場合を考えてみる。詳細については後述するが、図5の例の場合、(bc)、(be)が2次特徴イベント集合となる。当該2次特徴イベント集合の場合、前方に存在する1個のイベント集合がbと共通しているため、当該イベント集合から3次特徴イベント集合候補を生成することができる。すなわち、(bce)といったイベント集合が3次特徴イベント集合候補として生成される。
【0035】
ステップS9では、候補系列パターン生成部B2が生成するL次特徴イベント集合が存在するかどうかを判断し、存在しない場合にはステップS13に進む。一方、存在する場合には、ステップS10に進む。図5の例における2次特徴イベント集合候補の生成の場合、2次特徴イベント集合候補は図8の2次イベント集合の列に示す10個存在するので、10回目まではステップS10に進み。11回目にステップS13に進むことになる。
【0036】
ステップS10では、生成されたL次特徴イベント集合候補の頻度を系列パターン頻度計算部B3が計算する。図5の例における2次特徴イベント集合候補の生成の場合、各イベント集合の頻度は図8の頻度の列のように与えられる。また、図5の例における3次特徴イベント集合候補の生成の場合、各イベント集合の頻度は図9の頻度の列のように与えられる。
【0037】
次に、候補系列パターン評価部B5は、系列パターン頻度計算部B3で計算された頻度及び特徴系列パターン格納部B7に格納されている(L−1)次特徴イベント集合の最大頻度を式(1)に適用することにより、生成されたL次特徴イベント集合候補についての興味度を計算する。例として、2次特徴イベント集合(bc)の興味度を計算することを考えてみる。このとき、b,cの最大頻度が5,3と与えられており、(bc)の頻度が3と与えられるので、興味度は次のように与えられる。
【数6】


【0038】
同様に、3次特徴イベント集合(bce)の興味度を計算することを考えてみる。このとき、後のステップS12において説明する最大頻度の計算方法によれば、(bc)、(be)の最大頻度は5,5と与えられるので、興味度は
【数7】


【0039】
と与えられる。上記の計算例において、2次の場合における(bc)、3次の場合におけるb,c,e,(ce),(bce)に対応する部分系列パターンの頻度を評価していないことに注意する必要がある。このような評価が可能であるのは、系列パターンに対応する最大頻度の設定方法に関連した性質を利用しているためであり、ステップS12において最大頻度を設定する際に理由を説明する。
【0040】
ステップS11では、候補系列パターン判定部B6がL次特徴イベント集合に対応する興味度が最小興味度以上であるかを判定し、最小興味度以上である場合にステップS12に進む。一方、最小興味度未満の場合にはステップS8に戻る。2次特徴イベント集合候補の判定の場合、(bc),(be)の場合に最小興味度0.2以上となるので、ステップS12に進み、(ab),(ac),(ad),(bd),(cd),(ce),(de)の場合にステップS8に戻ることになる。
【0041】
ステップS12では、興味度が最小興味度以上となるL次特徴イベント集合候補を、候補系列パターン判定部B6がL次特徴イベント集合として特徴系列パターン格納部B7に格納する。また、対応する最大頻度として、L次特徴イベント集合を生成する元になったふたつの(L−1)次特徴イベント集合の最大頻度の値を当該L次特徴イベント集合の最大頻度として部分系列パターン頻度格納部B4に格納する。系列パターンの頻度は、その部分系列パターンの頻度以下になるといった性質が存在する。このため、部分系列パターンの頻度の逆数を考えた場合には、より短い部分系列パターンに対応した逆数の中に最小値が存在する。したがって、最も短い部分系列パターンであるイベントに対応した逆数の中に最小値が存在する。このため、系列パターンを構成するイベントの頻度の最大値(最大頻度)を部分系列パターンの頻度として部分系列パターン頻度格納部B4に記憶しておくことにより、候補系列パターン評価部B5は、L次特徴イベント集合を構成するのに利用した(L−1)次イベント集合のふたつの最大頻度だけを評価して、興味度を計算することができる。
【0042】
このステップS12において、候補系列パターン生成部B2は、特徴系列パターン格納部B7に格納されている特徴イベント集合をすべて併合することにより1次特徴系列パターンを生成する。図5の例の場合、図7に記述されている5個の1次特徴イベント集合及び図8に最大頻度が与えられて記述されている2個の2次イベント集合が1次特徴系列パターンとなる。
【0043】
次に図4に示すように、ステップS14では、候補系列パターン生成部B2が系列の前方の(L−2)個のイベント集合が一致するふたつの(L−1)次系列パターンを抽出する。また、その取り出した順序を考慮して、抽出した系列パターンからL次特徴系列パターン候補を生成する。例として、1次系列パターンa,(be)が順次取り出されて、このふたつのパターンから2次特徴系列パターン候補を生成する場合を考えてみる。ただし、2次特徴系列パターン候補の生成の場合には、前方の(L−2)個のイベント集合は存在しないので当該条件は適用されていない。このとき、当該1次特徴系列パターンからa(be)といった2次特徴系列パターンを生成することができる。また、前方の1個のイベント集合が共通している2次系列パターンa(be),abが順次取り出されて、このふたつのパターンから3次特徴系列パターン候補を生成する場合を考えてみる。ここで、当該のふたつの特徴系列パターンにおいては、前方の1個のイベント集合aが共通しているため、a(be)bといった3次の特徴系列パターン候補を生成することができる。
【0044】
ステップ15では、候補系列パターン生成部B2がL次特徴系列パターン候補が生成できたかどうかを判定し、生成できなかった場合にステップS19に進む。一方、生成できた場合にステップS16に進む。
【0045】
ステップS16では、系列パターン頻度計算部B3が当該特徴系列パターン候補の頻度を計算する。図5の例の場合、2次、3次、4次の各系列パターン候補に対して図10、図11、図12の頻度の列に示す値が頻度として計算される。
【0046】
ただし、各図においては、後に計算する興味度が最小興味度以上の興味度をもつ系列パターン候補に対してのみ、頻度を計算した結果を示している。
【0047】
また、候補系列パターン評価部B5は、系列パターン頻度計算部B3により計算されたL次特徴系列パターン候補及び特徴系列パターン格納部B7に格納されている、対応する最大頻度を式(1)に適用することにより興味度を計算する。例として、2次特徴系列パターン候補a(be)の興味度を計算してみると、興味度は、
【数8】


【0048】
と与えられる。
【0049】
また、3次特徴系列パターン候補a(be)bの興味度は、
【数9】


【0050】
と計算される。同様に、2次、3次、4次の各系列パターン候補に対して図10、図11、図12に示すように興味度の値が計算される。ただし、興味度が最小興味度以上になる特徴系列パターン候補に対してのみ結果を示している。上記の計算において、L次特徴系列パターン候補の生成の際に利用した最大頻度に基づいて興味度を計算できる理由は、ステップS12で説明したことと同様の理由による。
【0051】
ステップS17では、候補系列パターン判定部B6がL次特徴系列パターン候補の興味度が最小興味度以上であるかどうかを判定し、最小興味度以上の場合にステップS18に進む。一方、最小興味度未満の場合には、ステップS14に戻る。例えば、3次特徴系列パターン候補abbの場合には、最小興味度以上となるためステップS18に進み、図12に示す4次特徴系列パターン候補abbbの場合には最小興味度未満となるためステップS14に戻る。
【0052】
ステップS18では、候補系列パターン判定部B6が興味度以上となるL次特徴系列パターン候補を、L次特徴系列パターンとして特徴系列パターン格納部B7に格納する。また、当該特徴系列パターンを生成する際に利用したふたつの(L−1)次特徴系列パターンの最大頻度の最大値を当該パターンに対する最大頻度として、部分系列パターン頻度格納部B4に格納する。図5の例の場合、図10、図11の最大頻度の列に記載されている値が、対応する最大頻度として格納される。
【0053】
ステップS15では、特徴系列パターン格納部B7にひとつ以上のL次特徴系列パターン候補が格納されているかどうかを候補系列パターン生成部B2が判定する。このとき、L次特徴系列パターン候補がひとつ以上格納されている場合には、ステップS14に進み、ひとつも格納されていない場合には本フローの処理を終了する。図5の例の場合、4次特徴系列パターン候補を生成した段階でひとつも4次特徴系列パターンを発見することができないので、本フローの処理を終了する。
【0054】
ステップS19では、系列を延伸可能であれば、候補系列パターン生成部B2が系列のサイズを1増やして、ステップS14に戻る。
【0055】
最終的には、図7に示される全てのイベント、図8に示される(bc)と(be)、図10および図11に示される全てのパターンが、特徴系列パターンとして抽出される。
【0056】
以上説明したように、本実施形態によれば、分析者に新たな知見を与えるような有用で特徴的な系列パターンを取りこぼすことなく発見することができる。また、系列パターンの評価値を系列パターンに含まれるイベントに対して単調減少するように定義していることから、特徴系列パターンに含まれるすべての部分系列パターンの評価値は当該特徴系列パターンの評価値以上となり、すべての部分系列パターンが特徴系列パターンとなる。したがって、部分系列パターンが特徴系列パターンにならない系列パターンを候補系列パターンとして評価する必要がなくなり、効率的に特徴系列パターンを発見することができる。
【0057】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【0058】
例えば、特徴系列パターンの格納において、系列サイズごとに抽出されたすべての特徴系列パターンを系列パターン格納部B7に格納することにしているが、より長い系列サイズに含まれる特徴系列パターンは特徴系列パターン格納部B7から削除することにしてもよい。
【0059】
また、L次特徴系列パターンの頻度を計算するにあたって、その元になった(L−1)次特徴系列パターンが含まれる系列データを記憶しておき、系列データの部分集合にアクセスすることによりL次特徴系列パターン候補の頻度を計算してもよい。
【0060】
また、分析者が興味のある部分系列パターンを指定し、当該部分系列パターンを含む特徴系列パターンだけを最終的に抽出するようにしてもよい。
【0061】
さらに、上記した式(1)は、下記の式(2)のように変形することができる。この場合、系列パターンの頻度が比較的高く(式(2)の第2項に相当)、系列パターンに含まれる特定のイベントとその系列パターンの間に高い関連性(式(2)の第1項に相当)がある系列パターンを特徴的な系列パターンとして発見することができる。
【数10】


【図面の簡単な説明】
【0062】
【図1】本発明の一実施形態に係る特徴系列パターン発見装置を示すブロック図
【図2】上記特徴系列パターン発見装置が実行する頻出イベント抽出手順を示すフローチャート
【図3】上記特徴系列パターン発見装置が実行する特徴イベント集合抽出手順を示すフローチャート
【図4】上記特徴系列パターン発見装置が実行する特徴イベントパターン抽出手順を示すフローチャート
【図5】系列データ集合の一例を示す図
【図6】イベント名とイベントIDとの対応を示す図
【図7】図5の系列データから取り出される1次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図8】図5の系列データから取り出される2次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図9】図5の系列データから取り出される興味度が0.2以上となる2次特徴イベント集合から生成された、3次特徴イベント集合候補と、その頻度、興味度、および最大頻度との関係を示す図
【図10】図5の系列データから取り出される興味度が0.2以上となる2次系列パターンと、その頻度、興味度、および最大頻度との関係を示す図
【図11】図5の系列データから取り出される興味度が0.2以上となる3次系列パターンと、その頻度、興味度、および最大頻度との関係を示す図
【図12】図5の系列データから取り出される興味度が0.2以上となる3次系列パターンから生成された、4次系列パターン候補と、その頻度、興味度、および最大頻度との関係を示す図
【符号の説明】
【0063】
B1…系列データ格納部;
B2…候補系列パターン生成部;
B3…系列パターン頻度計算部;
B4…部分系列パターン頻度格納部;
B5…候補系列パターン評価部;
B6…候補系列パターン判定部;
B7…特徴系列パターン格納部




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013