(57)【特許請求の範囲】
【請求項１】
データストリームから、繰り返し現れるトレンドを、そのデータストリームの中から切り取った比較パターンと前記データストリームの部分シーケンスとの類似度スコアを示したタイムワーピング行列を用いて検出するトレンド検出方法であって、
記憶部に前記タイムワーピング行列を記録し、前記比較パターンと類似したパターンである類似パターンをトレンドとして検出し、出力するトレンド検出装置が、
前記データストリームの受信を開始し、
前記受信したデータストリームから、前記比較パターンとして、所定のシーケンス長のシーケンスを切り取り、この切り取ったシーケンスを前記記憶部のパターン記憶部に予め記録し、
前記パターン記憶部に記録された前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算し、
前記計算した類似度スコアと、その類似度スコアを計算するときに用いた部分シーケンスの開始位置ｔｓおよび前記比較パターンの開始位置ｉｓを、前記部分シーケンスの終了位置ｔｅおよび前記比較パターンの終了位置ｉｅと対応付けた前記部分シーケンスの情報を前記タイムワーピング行列に記録し、
（１）前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、
前記部分シーケンスの情報を、前記類似パターンの情報として前記パターン記憶部に記録し、
（２）前記計算した類似度スコアが所定の閾値εよりも低く、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、
前記部分シーケンスを新たな比較パターンとして、前記パターン記憶部に記録し、
前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力することを特徴とするトレンド検出方法。
【請求項２】
前記トレンド検出装置は、
前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算するとき、
前記比較パターンＹ［ｉｓ：ｉｅ］と、前記部分シーケンスＸ［ｔｓ：ｔｅ］との類似度スコアＳ（Ｘ［ｔｓ：ｔｅ］,Ｙ［ｉｓ：ｉｅ］）を、以下の式（１）により計算し、
【数１】
0004939349.tif 000006
Ｎ：部分シーケンスの長さの下限値、ｔ＝１,…,ｎ、ｉ＝１,…,ｍ、‖ｘｔ−ｙｉ‖：ｘｔとｙｉとの間の距離
前記タイムワーピング行列に記録される部分シーケンスＸ［ｔｓ：ｔｅ］の開始位置ｔｓと、前記比較パターンの開始位置ｉｓとを示すｐ（ｔ,ｉ）は、以下の式（２）により計算し、
【数２】
0004939349.tif 000007
前記開始位置ｔｓ,ｉｓは、以下の式（３）により計算することを特徴とする請求項１に記載のトレンド検出方法。
（ｔｓ,ｉｓ）＝ｐ（ｔｅ,ｉｅ）…式（３）
【請求項３】
前記トレンド検出装置は、
前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、
前記部分シーケンスの情報を、類似パターン候補の情報として前記記憶部のパターン候補記憶部に記録し、
（１）前記パターン候補記憶部に記録された前記類似パターン候補のうち、その開始位置ｔｓから終了位置ｔｅまでの区間に重複がないとき、
前記類似パターン候補の情報を、前記比較パターンに対する類似パターンの情報として前記パターン記憶部に記録し、
（２）前記パターン候補記憶部に記録された前記類似パターン候補のうち、その開始位置ｔｓから終了位置ｔｅまでの区間の少なくとも一部に重複しているものがあるとき、前記区間が重複している類似パターン候補の中から、前記類似度スコアの値が最も大きい類似パターン候補を選択し、
前記類似度スコアを計算した部分シーケンスの開始位置ｔｓが、前記類似度スコアの値が最も大きい類似パターン候補の終了位置ｔｅよりも後であるとき、
前記類似度スコアの値が最も大きい類似パターン候補の情報を、前記比較パターンに対する類似パターンの情報として前記パターン記憶部に記録し、
前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力することを特徴とする請求項１または請求項２に記載のトレンド検出方法。
【請求項４】
前記トレンド検出装置は、
前記パターン記憶部に記録された比較パターンとこの比較パターンに対する前記類似パターンからなるグループのうち、当該グループに属するパターンの数が所定の値ｋ以上のグループがあったとき、
当該グループにおける前記比較パターンおよびこの比較パターンに対する前記類似パターンの情報を前記トレンドとして出力することを特徴とする請求項１ないし請求項３のいずれか１項に記載のトレンド検出方法。
【請求項５】
前記トレンド検出装置は、
前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算するとき、
前記比較パターンおよびこの比較パターンに対する前記類似パターンそれぞれを用いて、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算することを特徴とする請求項１ないし請求項４のいずれか１項に記載のトレンド検出方法。
【請求項６】
前記トレンド検出装置は、
前記パターン記憶部に、当該グループに属するパターンの数が所定の値ｌ以上のグループがあったとき、
前記グループ内のパターンごとに、同じグループ内の他のパターンそれぞれとの前記類似度スコアを計算して、その合計値を求め、
前記類似度スコアの合計値が最大となったパターンの情報を出力することを特徴とする請求項１ないし請求項５のいずれか１項に記載のトレンド検出方法。
【請求項７】
前記トレンド検出装置は、
前記類似度スコアの合計値が最大となったパターンが、そのパターンの属するグループにおける前記比較パターンではないとき、
前記グループにおける前記比較パターンを、前記類似度スコアの合計値が最大となったパターンと置き換え、
前記置き換え後の比較パターンを用いて、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算することを特徴とする請求項６に記載のトレンド検出方法。
【請求項８】
請求項１ないし請求項７のいずれか１項に記載のトレンド検出方法を、コンピュータである前記トレンド検出装置に実行させることを特徴とするトレンド検出プログラム。
【請求項９】
データストリームから、繰り返し現れるトレンドを、そのデータストリームの中から切り取った比較パターンと前記データストリームの部分シーケンスとの類似度スコアを示したタイムワーピング行列を用いて検出するデータストリーム処理部を備えるトレンド検出装置であって、
前記タイムワーピング行列の計算に用いる比較パターンを記憶するパターン記憶部と、
前記タイムワーピング行列を記憶するタイムワーピングデータ記憶部と、
前記データストリームの入力を受け付ける入力部と、
前記データストリームから、前記比較パターンとして、所定のシーケンス長のシーケンスを切り取り、この切り取ったシーケンスを前記記憶部のパターン記憶部に予め記録し、前記パターン記憶部に記録された前記比較パターンと、前記データストリームの部分シーケンスとの前記類似度スコアを計算し、前記計算した類似度スコアと、その類似度スコアを計算するときに用いた部分シーケンスの開始位置ｔｓおよび前記比較パターンの開始位置ｉｓを、前記部分シーケンスの終了位置ｔｅおよび前記比較パターンの終了位置ｉｅと対応付けた前記部分シーケンスの情報を前記タイムワーピング行列に記録し、（１）前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を、前記類似パターンの情報として前記パターン記憶部に記録し、（２）前記計算した類似度スコアが所定の閾値εよりも低く、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を新たな比較パターンとして、前記パターン記憶部に記録する前記データストリーム処理部と、
前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力する出力部とを備えることを特徴とするトレンド検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストリームマイニング技術に関する。
【背景技術】
【０００２】
従来、ネットワークから高速に送られてくるデータストリームの中から、役に立つ情報を素早く見つけ出すストリームマイニング技術がある。このストリームマイニング技術は、単にデータベースに蓄えられた大規模データを分析するのではなく、時々刻々増え続けるデータをリアルタイムに分析し、監視する技術である。このように増え続けるデータをリアルタイムに分析し、また利用者に情報をリアルタイムに提供するため、ストリームマイニング技術には処理の高速化と省メモリ化が要求される。
【０００３】
例えば、ストリーム監視において、データストリームの部分シーケンスマッチング技術が必要とされるが、各データストリームのサンプリングレートが異なる場合や、周期が変化する場合があるため、時間軸方向のずれに柔軟性を持たせるタイムワーピングを考慮することが重要である。このタイムワーピングを考慮するとき、距離関数として、ダイナミックタイムワーピング（ＤＴＷ：Dynamic Time Warping）が広く用いられている。このＤＴＷに基づいてシーケンス同士の距離を計算するタイムワーピング行列を作成することで、２つのシーケンス間の距離であるＤＴＷ距離を計算することができる。なお、ＤＴＷ距離はその距離が小さいほど、２つのシーケンスが類似していることを示す。
【０００４】
ストリーム監視を行うためのアルゴリズムは数多く提案されているが、その多くは事前に用意された問い合わせパターンに類似する部分シーケンスを検出するものに過ぎない。このようなアルゴリズムは、ストリーム監視対象が明確である場合に有効な手段であるが、増え続けるストリームの中から、常にトレンド（頻繁に登場するパターン）を検出することも必要である。しかし、このようなトレンド検出技術については未だ提案されていない。
【０００５】
例えば、非特許文献１には、ＤＴＷに基づくストリーム監視技術が開示されているが、これは用意された問い合わせパターンに類似する部分シーケンスを検出するものに過ぎない。また、非特許文献２には、データの中から繰り返し現れるパターンを検出する技術が開示されているが、この技術は蓄積されたデータ集合のための手法であり、データストリームには適していない。さらに、非特許文献３,４には、ストリーム監視技術や、そのデータストリームにおけるトレンド検出に関する技術が開示されているが、前記したタイムワーピングを考慮したものではない。
【０００６】
ここで、従来技術であるＤＴＷを応用してデータストリームからトレンドの検出を行おうとすると、データストリームの長さをｎ、比較パターンの長さをｍとしたとき、Ｏ（ｎｍ２）で計算量やメモリの使用量が増大してしまうという問題がある。
【０００７】
この問題を、図１１を用いて説明する。図１１（ａ）および（ｂ）は、比較例となるＤＴＷによるタイムワーピング行列を例示した図である。図１１（ａ）および（ｂ）において、シーケンスＹは、固定長ｍのデータであり、シーケンスの類似判断の元となるデータである。データストリームであるシーケンスＸは、時々刻々と伸張している（データ量が増えている）シーケンスであり、シーケンスＹの類似判断の対象となるデータである。２つのシーケンス間のＤＴＷ距離とは、２つのシーケンスを、全体的あるいは部分的に時間軸方向に伸縮の調整を行った後の距離のことである。このＤＴＷ距離は、タイムワーピング行列に基づいて計算することができる。ここで長さｍのシーケンスＹ＝（ｙ１，ｙ２，…，ｙｍ）と長さｎのシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）の間のＤＴＷ距離Ｄ（Ｘ，Ｙ）は、以下の式（５）〜（８）により求めることができる。なお、ｔ＝（１，２，…，ｎ）、ｉ＝（１，２，…，ｍ）とする。
【０００８】
Ｄ（Ｘ，Ｙ）＝ｆ（ｎ，ｍ）…式（５）
ｆ（ｔ，ｉ）＝||ｘｔ−ｙｉ||＋ｍｉｎ｛ｆ（ｔ，ｉ−１），ｆ（ｔ−１，ｉ），
ｆ（ｔ−１，ｉ−１）｝…式（６）
ｆ（０，０）＝０…式（７）
ｆ（ｔ，０）＝ｆ（０，ｉ）＝∞…式（８）
【０００９】
式（５）は、ＤＴＷ距離の定義である。式（６）は、具体的な計算式である。式（６）において、||ｘｔ−ｙｉ||は、２つの数値（ｘｔとｙｉ）の距離を表す。例えば、||ｘｔ−ｙｉ||として、ユークリッド距離の二乗の値を使用する。また、式（６）において、ｍｉｎ｛ｆ（ｔ，ｉ−１），ｆ（ｔ−１，ｉ），ｆ（ｔ−１，ｉ−１）｝は、｛｝内の値のうち、最小のものを採用する、という意味である。なお、式（７）および式（８）は、この３つの値を計算する際に使用する、タイムワーピング行列における境界条件である。タイムワーピング行列は、ＤＴＷの関数の値、すなわち、前記式（６）におけるｆ（ｔ，ｉ）の値を保持するものである。つまり、このＤＴＷ距離を用いたタイムワーピング行列によれば、シーケンスにおける自身の値の１つ前の値とのつながりを考慮して、シーケンスＹの類似パターンを検出することができる。
【００１０】
例えば、シーケンスＹ＝（１１，６，９，４）と、シーケンスＸ＝（１２,６,１０,６,５,１,…）それぞれとのＤＴＷ距離を計算すると、図１１（ａ）のタイムワーピング行列に示す値となる。ここで、図１１（ａ）のタイムワーピング行列のハッチング部分は、ＤＴＷ距離「６」を計算するために辿ってきたルート（タイムワーピングパス）であり、このルートを辿ることで、ＤＴＷ距離の計算の開始位置が分かる。つまり、このＤＴＷ距離の値が比較的小さいものが連なったタイムワーピングパスを見つけることで、シーケンスＸ＝（１２,６,１０,６,５,１,…）から、シーケンスＹ＝（１１，６，９，４）に類似する部分シーケンスを検出することができる。
【非特許文献１】Y.Sakurai,C.Faloutsos,and M.Yamamuro:”Stream Monitoring under the Time Warping Distance,”In Proceedings of IEEE 23rd International Conference on Data Engineering(ICDE 2007),pp.1046-1055,2007.
【非特許文献２】B.Chiu,E.Keogh,and S.Lonardi:”Probabilistic discovery of time series motifs,”n Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Descovery and Data Mining (KDD’03),pp.493-498,2003.
【非特許文献３】Y.Zhu,and D.Shasha：”Staｔｓtream:Statistical Monitoring of Thousands of Data Streams of Data Stream in Real Time”, In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB 2002),pp.358-498,2002.
【非特許文献４】P.Indyk,N.Koudas,and S.MuthuKrishnan:”Identyfyig representative trends in massive time series data sets using sketches,” In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB 2000),pp.363-372,2000.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ここで、前記したＤＴＷ距離を用いて、伸張している長さｎのシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）のトレンドを検出しようとした場合、以下の様になる。すなわち、シーケンスＸに対し、シーケンス長がＮ以上、Ｎ´以下である部分シーケンスＹを比較パターンとする。そして、この比較パターンＹの少なくとも一部に類似する部分シーケンスＸ［ｔｓ：ｔｅ］を検出する。なお、［：］は、シーケンスの開始位置と終了位置とを示す記号である。このとき、前記したＤＴＷ距離を計算するため、図１１（ｂ）に示すようなタイムワーピング行列を作成する必要がある。つまり、シーケンスＸから取り出した部分シーケンスＹ＝（ｙ１，ｙ２，…，ｙｍ）について、シーケンス長をＮ以上、Ｎ´以下の範囲で変化させ、そのシーケンス長ごとに、タイムワーピング行列を作成する必要がある。
【００１２】
例えば、図１１（ｂ）の符号９３０に示すように、ｙ１からスタートする部分シーケンスＹ［１：ｍ］,…,部分シーケンスＹ［１：ｉ］それぞれとのＤＴＷ距離を示したタイムワーピング行列、符号９２０に示すｙｉ１からスタートする部分シーケンスＹ［ｉ１：ｍ］,…,部分シーケンスＹ［ｉ１：ｉ２］それぞれとのＤＴＷ距離を示したタイムワーピング行列、というようにタイムワーピング行列を作成する。そして、最終的にｙｍ-Ｎ+１からスタートする部分シーケンスＹ［ｍ-Ｎ+１：ｍ］とのＤＴＷ距離を示したタイムワーピング行列を作成する。そして、各タームワーピング行列においてＤＴＷ距離の値が小さいタイムワーピングパス（符号９２１に示すタイムワーピングパスや、符号９３１に示すタイムワーピングパス参照）を検出することで、このシーケンスＸに対するトレンドである部分シーケンスＹ［ｉｓ：ｉｅ］およびその部分シーケンスＹに類似する部分シーケンスＸ［ｔｓ：ｔｅ］を検出することができる。
【００１３】
このように、従来の手法を用いる場合、データストリームからトレンドを検出するとき、あらゆるパターンの部分シーケンスとの比較を行う必要があるので、Ｏ（ｎｍ２）個のタイムワーピング行列を用いる必要がある。また、ｎが増えるたび、つまり時刻が経過してデータストリームのデータが到着するたびにタイムワーピング行列を追加していく必要もある。このように、シーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）のトレンド検出のため、部分シーケンスＹの少なくとも一部に類似する部分シーケンスＸ［ｔｓ：ｔｅ］を検出しようとした場合、データストリームの増加とともに計算量やメモリ使用量が増大するという問題があった。
【００１４】
本発明は、前記した課題を解決し、データストリームからトレンドを検出するときの計算量やメモリ使用量の増大を抑制する手段を提供することを目的とする。
【課題を解決するための手段】
【００１５】
前記した課題を解決するため、請求項１に記載の発明は、データストリームから、繰り返し現れるトレンドを、そのデータストリームの中から切り取った比較パターンと前記データストリームの部分シーケンスとの類似度スコアを示したタイムワーピング行列を用いて検出するトレンド検出方法であって、記憶部に前記タイムワーピング行列を記録し、前記比較パターンと類似したパターンである類似パターンをトレンドとして検出し、出力するトレンド検出装置が、前記データストリームの受信を開始し、前記受信したデータストリームから、前記比較パターンとして、所定のシーケンス長のシーケンスを切り取り、この切り取ったシーケンスを前記記憶部のパターン記憶部に予め記録し、前記パターン記憶部に記録された前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算し、前記計算した類似度スコアと、その類似度スコアを計算するときに用いた部分シーケンスの開始位置ｔｓおよび前記比較パターンの開始位置ｉｓを、前記部分シーケンスの終了位置ｔｅおよび前記比較パターンの終了位置ｉｅと対応付けた前記部分シーケンスの情報を前記タイムワーピング行列に記録し、（１）前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を、前記類似パターンの情報として前記パターン記憶部に記録し、（２）前記計算した類似度スコアが所定の閾値εよりも低く、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスを新たな比較パターンとして、前記パターン記憶部に記録し、前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力することを特徴とするトレンド検出方法とした。
【００１６】
請求項９に記載の発明は、データストリームから、繰り返し現れるトレンドを、そのデータストリームの中から切り取った比較パターンと前記データストリームの部分シーケンスとの類似度スコアを示したタイムワーピング行列を用いて検出するデータストリーム処理部を備えるトレンド検出装置であって、前記タイムワーピング行列の計算に用いる比較パターンを記憶するパターン記憶部と、前記タイムワーピング行列を記憶するタイムワーピングデータ記憶部と、前記データストリームの入力を受け付ける入力部と、前記データストリームから、前記比較パターンとして、所定のシーケンス長のシーケンスを切り取り、この切り取ったシーケンスを前記記憶部のパターン記憶部に予め記録し、前記パターン記憶部に記録された前記比較パターンと、前記データストリームの部分シーケンスとの前記類似度スコアを計算し、前記計算した類似度スコアと、その類似度スコアを計算するときに用いた部分シーケンスの開始位置ｔｓおよび前記比較パターンの開始位置ｉｓを、前記部分シーケンスの終了位置ｔｅおよび前記比較パターンの終了位置ｉｅと対応付けた前記部分シーケンスの情報を前記タイムワーピング行列に記録し、（１）前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を、前記類似パターンの情報として前記パターン記憶部に記録し、（２）前記計算した類似度スコアが所定の閾値εよりも低く、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を新たな比較パターンとして、前記パターン記憶部に記録する前記データストリーム処理部と、前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力する出力部とを備えることを特徴とするトレンド検出装置とした。
【００１７】
このようにすることで、トレンド検出装置は、データストリームからトレンドを検出するとき、あらゆるパターンの部分シーケンスとの比較を行う必要がなくなるので、トレンドの検出を効率的に行うことができる。また、タイムワーピング行列は、各部分シーケンスの類似度スコアおよびその部分シーケンスの終了位置ｔｅ、比較パターンの終了位置ｉｅとともに、その類似度スコアを計算した部分シーケンスの開始位置ｔｓと、比較パターンの開始位置ｉｓとを記録する。このようにすることで、どの開始位置ｔｓから始まる部分シーケンスＸが比較パターンＹのどの部分と類似しているかを、過去に遡ることなく把握することができる。また、このタイムワーピング行列において、部分シーケンスの開始位置ｔｓ、終了位置ｔｅの情報を保持することにより、トレンド検出装置は、新たに到着した要素の類似度スコアを計算する場合、１つ前の要素の情報が分かればよいので、計算に使用するタイムワーピング行列は２列でよく、これらを更新することで類似度スコアを計算することができる。これにより、データストリームからトレンドを検出するときの計算量やメモリ使用量の増大を抑制することができる。なお、ここでのトレンドとは、データストリームのうち、比較パターンに類似する部分シーケンス（類似パターン）を示し、トレンド検出装置がトレンドを出力するときには、この類似パターンと、この類似パターンの検出に用いた比較パターンとを含めるものとする。
【００１８】
請求項２に記載の発明は、請求項１に記載のトレンド検出方法において、前記トレンド検出装置は、前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算するとき、前記比較パターンＹ［ｉｓ：ｉｅ］と、前記部分シーケンスＸ［ｔｓ：ｔｅ］との類似度スコアＳ（Ｘ［ｔｓ：ｔｅ］,Ｙ［ｉｓ：ｉｅ］）を、以下の式（１）により計算し、
【数１】
0004939349.tif 000002
Ｎ：部分シーケンスの長さの下限値、ｔ＝１,…,ｎ、ｉ＝１,…,ｍ、‖ｘｔ−ｙｉ‖：ｘｔとｙｉとの間の距離
前記タイムワーピング行列に記録される部分シーケンスＸ［ｔｓ：ｔｅ］の開始位置ｔｓと、前記比較パターンの開始位置ｉｓとを示すｐ（ｔ,ｉ）は、以下の式（２）により計算し、
【数２】
0004939349.tif 000003
前記開始位置ｔｓ,ｉｓは、以下の式（３）により計算することを特徴とするトレンド検出方法とした。
（ｔｓ,ｉｓ）＝ｐ（ｔｅ,ｉｅ）…式（３）
【００１９】
このような方法によれば、トレンド検出装置は、タイムワーピング行列を計算するとき、類似度スコアが高ければその類似度スコアを加算していき、類似度スコアが低ければその類似度スコアを減算していく。また、式（１）に示すように、ｓ（ｔ,ｉ）を計算する場合において、ε／Ｎ−‖ｘｔ−ｙｉ‖＋ｓｂｅｓｔの値が０より小さくなったときには、ｓ（ｔ,ｉ）＝０とする。このようにすることで、この部分シーケンスの類似度スコアが０より小さくなった場合でも、その次の部分シーケンスの類似度スコアに影響を与えないようにできる。つまり、トレンド検出装置は、より類似度スコアの高い部分シーケンス同士のつながりを反映した類似度スコアの計算を行うことができる。
【００２０】
請求項３に記載の発明は、請求項１または請求項２に記載のトレンド検出方法において、前記トレンド検出装置は、前記計算した類似度スコアが所定の閾値ε以上であり、かつ、前記部分シーケンスのシーケンス長が、所定の長さであるとき、前記部分シーケンスの情報を、類似パターン候補の情報として前記記憶部のパターン候補記憶部に記録し、（１）前記パターン候補記憶部に記録された前記類似パターン候補のうち、その開始位置ｔｓから終了位置ｔｅまでの区間に重複がないとき、前記類似パターン候補の情報を、前記比較パターンに対する類似パターンの情報として前記パターン記憶部に記録し、（２）前記パターン候補記憶部に記録された前記類似パターン候補のうち、その開始位置ｔｓから終了位置ｔｅまでの区間の少なくとも一部に重複しているものがあるとき、前記区間が重複している類似パターン候補の中から、前記類似度スコアの値が最も大きい類似パターン候補を選択し、前記類似度スコアを計算した部分シーケンスの開始位置ｔｓが、前記類似度スコアの値が最も大きい類似パターン候補の終了位置ｔｅよりも後であるとき、前記類似度スコアの値が最も大きい類似パターン候補の情報を、前記比較パターンに対する類似パターンの情報として前記パターン記憶部に記録し、前記パターン記憶部に記録された前記比較パターンおよびこの比較パターンに対する類似パターンの情報を前記トレンドとして出力することを特徴とするトレンド検出方法とした。
【００２１】
このような方法によれば、トレンド検出装置は、類似度スコアが閾値ε以上となる類似パターン候補を、同じ区間に重複して検出する可能性があるが、その中で最も類似度スコアが大きいものを類似パターンとして選択する。従って、トレンド検出装置は、同じ様な区間から同じ様なトレンドを重複して出力することがなくなる。つまり、トレンド検出装置は、このトレンド検出装置の利用者に冗長な情報を与えることがなくなる。
【００２２】
請求項４に記載の発明は、請求項１ないし請求項３のいずれか１項に記載のトレンド検出方法において、前記トレンド検出装置は、前記パターン記憶部に記録された比較パターンとこの比較パターンに対する前記類似パターンからなるグループのうち、当該グループに属するパターンの数が所定の値ｋ以上のグループがあったとき、当該グループにおける前記比較パターンおよびこの比較パターンに対する前記類似パターンの情報を前記トレンドとして出力することを特徴とするトレンド検出方法とした。
【００２３】
このような方法によれば、トレンド検出装置は、データストリームにおいて、類似パターンが所定の回数以上登場したことを確認した上で、その類似パターンをトレンドとして出力する。従って、トレンド検出装置は、より信頼度の高いトレンドを出力することができる。
【００２４】
請求項５に記載の発明は、請求項１ないし請求項４のいずれか１項に記載のトレンド検出方法において、前記トレンド検出装置は、前記比較パターンと、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算するとき、前記パターン記憶部に記憶された前記比較パターンおよびこの比較パターンに対する前記類似パターンそれぞれを用いて、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算することを特徴とするトレンド検出方法とした。
【００２５】
このような方法によれば、トレンド検出装置は、新たに検出された比較パターンの類似パターンもトレンドとして検出することができる。つまり、データストリームから様々なパターンのトレンドを検出することができる。
【００２６】
請求項６に記載の発明は、請求項１ないし請求項５のいずれか１項に記載のトレンド検出方法において、前記トレンド検出装置は、前記パターン記憶部に、当該グループに属するパターンの数が所定の値ｌ以上のグループがあったとき、前記グループ内のパターンごとに、同じグループ内の他のパターンそれぞれとの前記類似度スコアを計算して、その合計値を求め、前記類似度スコアの合計値が最大となったパターンの情報を出力することを特徴とするトレンド検出方法とした。
【００２７】
このような方法によれば、トレンド検出装置は、類似パターンのうち、どのパターンとも類似している代表パターン（重心に近いパターン）を、トレンドとして出力することができる。
【００２８】
請求項７に記載の発明は、請求項６に記載のトレンド検出方法において、前  前記トレンド検出装置は、前記類似度スコアの合計値が最大となったパターンが、そのパターンの属するグループにおける前記比較パターンではないとき、前記グループにおける前記比較パターンを、前記類似度スコアの合計値が最大となったパターンと置き換え、前記置き換え後の比較パターンを用いて、前記受信したデータストリームの部分シーケンスとの前記類似度スコアを計算することを特徴とするトレンド検出方法とした。
【００２９】
このような方法によれば、トレンド検出装置は、データストリームからトレンドを検出するとき、すべての類似パターンを用いて比較を行う必要がなくなるので、計算量やメモリ使用量を削減することができる。
【００３０】
請求項８に記載の発明は、請求項１ないし請求項７のいずれか１項に記載のトレンド検出方法を、コンピュータである前記トレンド検出装置に実行させることを特徴とするトレンド検出プログラムとした。
【００３１】
このようなプログラムによれば、請求項１ないし請求項７のいずれか１項に記載のトレンド検出方法を、一般的なコンピュータに実行させることができる。
【発明の効果】
【００３２】
本発明によれば、データストリームからトレンドを検出するときの計算量やメモリ使用量の増大を抑制することができる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明を実施するための最良の形態（以下、実施の形態という）を、第１の実施の形態ないし第３の実施の形態に分けて説明する。図１は、各実施の形態のトレンド検出装置によるトレンドの検出を概念的に説明した図である。各実施の形態のトレンド検出装置は、図１に示すように、データストリームＸ＝（ｘ１，ｘ２，…，ｘｎ,…）において繰り返し現れる部分シーケンスであるトレンドを検出することを特徴とする。
【００３４】
各実施の形態のトレンド検出装置がトレンドの検出に用いるタイムワーピング行列は、以下のようなものである。図２（ａ）は、各実施の形態のタイムワーピング行列を概念的に示した図であり、図２（ｂ）は、（ａ）のタイムワーピング行列の具体例を示した図である。
【００３５】
トレンド検出装置は、図２（ａ）に例示するように比較パターンＹ＝（ｙ１，ｙ２，…，ｙｍ）について１つのタイムワーピング行列を記憶する。このタイムワーピング行列は、部分シーケンスＸの類似度スコア（計算式の詳細は後記）と、この類似度スコアを計算するときに用いた部分シーケンスＸの開始位置ｔｓおよび比較パターンＹの開始位置ｉｓを、この部分シーケンスＸの終了位置ｔｅおよび比較パターンＹの終了位置ｉｅと対応付けて記録したものである。なお、図２（ａ）および（ｂ）では、受信したデータストリームのすべての要素のタイムワーピング行列を示しているが、タイムワーピングデータ記憶部（詳細は後記）に用意されるタイムワーピング行列は、１つの比較パターンＹに対して、少なくとも現在の要素と１つ前の要素との２列分の情報を保持すればよい。
【００３６】
図２（ｂ）は、Ｘ＝（５,１２,６,１０,６,５,１,１３,１８,２,１４,１８,３）、シーケンス長の下限値Ｎ＝２とし、閾値ε＝５０とし、長さ２Ｎ（＝４）の部分シーケンスＹ［１：４］＝（１１,６,９,４）を比較パターンとしたときのタイムワーピング行列を示す。各行列における値は、部分シーケンスの類似度スコアとその部分シーケンスの開始位置（ｔｓ,ｉｓ）とを示す。
【００３７】
ここで、図２（ｂ）を用いて、トレンド検出装置が、タイムワーピング行列の各値を計算する手順を説明する。図２（ｂ）のｔ＝１１において、ｘ１１＝１,ｙ１＝１１の類似度スコアｓ（１１,１）は、後記する類似度スコアの計算式（式（１）参照）により「０」となる。また、この類似度スコアの計算において、ｓｂｅｓｔとして、ｓ（１０,１）の値を用いたので、このｓ（１０,１）の値の開始位置（ｔｓ,ｉｓ）である「（６,１）」を、この部分シーケンスＸの開始位置（ｔｓ,ｉｓ）としてタイムワーピング行列に記録する。以下、ｘ１１＝１,ｙ２＝６、ｘ１１＝１,ｙ３＝９、ｘ１１＝１,ｙ４＝４についても同様に計算し、図２（ｂ）に示すような計算結果を得る。
【００３８】
なお、図２（ｂ）のｔ＝５〜１１のハッチング部分は、前記したようなタイムワーピング行列の計算をｔ＝１８まで実行することにより得られた最適部分シーケンス（最も類似度スコアが高い部分シーケンス）を示すタイムワーピングパスである。つまり、ｔ＝１８まで類似度スコアを計算したところ、終了位置（ｔｅ,ｉｅ）＝（１１,４）である部分シーケンスの類似度スコア「１６６」は類似度スコアの最大値であるので、この部分シーケンスが最適部分シーケンスであると判断する。また、その「１６６」という値は、ｔ＝５〜１１のハッチング部分の経路を辿って計算したことを示す。
【００３９】
なお、図２（ｂ）に示したように、本実施の形態のタイムワーピング行列によれば、類似度スコアの最大値「１６６」である最適部分シーケンス発見した後、その値に付された開始位置（ｔｓ,ｉｓ）を参照することで、その部分シーケンス（終了位置（ｔｅ,ｉｅ）の部分シーケンス）に対する開始位置（ｔｓ,ｉｓ）が分かる。つまり、タイムワーピング行列において、当該比較パターンに類似する部分シーケンスの開始位置（ｔｓ,ｉｓ）を、過去に遡ることなく求めることができる。
【００４０】
トレンド検出装置は、このようなタイムワーピング行列を用いることで、データストリームから、部分シーケンスＹ［２：４］＝（６,９,４）と、この部分シーケンスＹ［２：４］＝（６,９,４）に対応する部分シーケンス、つまり、トレンドである部分シーケンスＸ［５：１１］＝（５,１２,６,１０,６,５,１）を検出することができる。
【００４１】
このように、本実施の形態のトレンド検出装置は、１つの比較パターンあたり、１つのタイムワーピング行列を用いればよいので、トレンドの検出のためメモリ使用量や計算量を大幅に削減できる。
【００４２】
なお、詳細は後記するが、トレンド検出装置は、データストリームと、所定長（例えば、２Ｎ）の部分シーケンスと、比較パターンとを比較しても、類似度スコアが閾値ε以上となる部分シーケンスを検出できなかったとき、その所定長の部分シーケンスを新たな比較パターンとして検出する。そして、データストリーム処理部１２１は、その検出した新たな比較パターンに関するタイムワーピング行列により、その新たな比較パターンに対する類似パターンを検出する。なお、この新たな比較パターンの検出は、既に複数の比較パターンを検出済みの場合には、そのいずれの比較パターンにも類似しない（つまり、類似度スコアが閾値ε以上とならない）部分シーケンスを検出することにより行われる。トレンド検出装置は、このようにして新たな比較パターンを検出していくことで、トレンドとなるパターンの検出を効率的に行うことができる。
【００４３】
≪第１の実施の形態≫
図３は、各実施形態のトレンド検出装置の構成図である。トレンド検出装置１は、コンピュータ装置であり、入力部１１、処理部１２、記憶部１３および出力部１４を備える。
【００４４】
入力部１１は、外部装置（不図示）やセンサ（不図示）からインターネットやＬＡＮ（Local Area Network）経由でデータストリームの入力を受け付けたり、キーボードやマウス等の入力装置（不図示）からトレンド検出のためのトレンド検出条件の入力を受け付けたりする。このトレンド検出条件は、例えば、データストリームから類似パターンを検出するときのシーケンス長の下限値Ｎ、上限値Ｎ´、類似度スコアの閾値ε等（詳細は後記）である。この入力部１１は、インターネットやＬＡＮ経由でデータの送受信を行うための通信インタフェースや、入力装置等の外部装置との各種データの入出力を行うための入出力インタフェースにより実現される。
【００４５】
このような入力部１１は、データストリームからトレンドを検出するときに用いるトレンド検出条件の入力を受け付けるトレンド検出条件入力部１１１と、データストリームの入力を受け付けるデータストリーム入力部１１２とを含んで構成される。
【００４６】
処理部１２は、データストリームからのトレンド検出のための各種演算処理を行うものであり、例えば、ＣＰＵ（Central Processing Unit）が記憶部１３のプログラムを実行することで実現される。この処理部１２は、データストリーム処理部１２１を備え、データストリーム入力部１１２で受信したデータストリームに関して、記憶部１３のタイムワーピングデータ記憶部１３３のタイムワーピング行列を用いて、トレンドを検出し、出力部１４のトレンド出力部１４１（後記）経由で外部へ出力する。なお、このデータストリーム処理部１２１は、データストリームと比較パターンとの類似度スコアを計算するとき、スコアリング関数を用いる。
【００４７】
このスコアリング関数は、データストリームＸ＝（ｘ１，ｘ２，…，ｘｎ,…）と、比較パターンＹ＝（ｙ１，ｙ２，…，ｙｍ）との類似度スコアを計算するための関数である。データストリーム処理部１２１は、データストリームのデータが１つ到着するたびに、このスコアリング関数により、比較パターンＹと、データストリームＸの部分シーケンスＸ［ｔｓ：ｔｅ］との類似度スコアを計算する。なお、このスコアリング関数により計算される類似度スコアは、式（１）に示すように、類似度が高ければ加算され、類似度が低ければ減算される仕組みになっており、類似度スコアが閾値ε以上となる部分シーケンスが、この比較パターンＹに類似する部分シーケンスであることを意味する。この類似度スコアは、データストリーム処理部１２１が、タイムワーピング行列（図２（ａ）および（ｂ）参照）を用いて、比較パターンＹと部分シーケンスＸの各要素同士を対応させて計算する。
【００４８】
比較パターンＹ＝（ｙ１，ｙ２，…，ｙｍ）に類似する部分シーケンスＸ［ｔｓ：ｔｅ］の類似度スコアＳ（Ｘ［ｔｓ：ｔｅ］,Ｙ［ｉｓ：ｉｅ］）は以下の式（１）により計算される。
【００４９】
【数１】
0004939349.tif 000004
【００５０】
εは、閾値であり、Ｎは、部分シーケンスの長さの下限値であり、ｔ＝１,…,ｎ、ｉ＝１,…,ｍ、‖ｘｔ−ｙｉ‖は、ｘｔとｙｉとの間の距離である。ここでの距離は、例えば、ユークリッド距離の二乗とする。
【００５１】
ここで、部分シーケンスＸ［ｔｓ：ｔｅ］と比較パターンＹ［ｉｓ：ｉｅ］とが類似するとき、（ｔｓ,ｉｓ）をこのマッチングにおける開始位置、（ｔｅ,ｉｅ）をこのマッチングにおける終了位置と呼ぶ。なお、式（１）に示すように、ｓ（ｔ,ｉ）を計算する場合において、ε／Ｎ−‖ｘｔ−ｙｉ‖＋ｓｂｅｓｔの値が０より小さくなったときには、ｓ（ｔ,ｉ）＝０とする。このようにすることで、この部分シーケンスＸの類似度スコアが０より小さくなった場合でも、その次の部分シーケンスの類似度スコアに影響を与えないようにすることができる。つまり、類似度スコアのより高い部分シーケンス同士のつながりを反映した類似度スコアの計算を行うことができる。
【００５２】
なお、このタイムワーピング行列は、各部分シーケンスの類似度スコアおよびその部分シーケンスの終了位置ｔｅ、比較パターンの終了位置ｉｅとともに、その類似度スコアを計算した部分シーケンスの開始位置ｔｓと、比較パターンの開始位置ｉｓとを保持する。このようにすることで、どの開始位置ｔｓから始まる部分シーケンスＸ［ｔｓ：ｔｅ］が比較パターンＹと類似しているかを、過去に遡ることなく把握することができる。
【００５３】
また、タイムワーピング行列に記録されるＸ［ｔｓ：ｔｅ］の開始位置情報と、比較パターンの開始位置ｉｓとを示すｐ（ｔ,ｉ）は、以下の式（２）により求めることができる。
【数２】
0004939349.tif 000005
【００５４】
さらに、開始位置ｔｓ,ｉｓは、以下の式（３）により求めることができる。
（ｔｓ,ｉｓ）＝ｐ（ｔｅ,ｉｅ）…式（３）
【００５５】
なお、データストリーム処理部１２１は、所定長（例えば、２Ｎ）の部分シーケンスを比較パターンと比較しても、類似度スコアが閾値ε以上となる部分シーケンスを検出できなかったとき、その所定長の部分シーケンスを新たな比較パターンとして検出する。そして、データストリーム処理部１２１は、その検出した新たな比較パターンに関するタイムワーピング行列により、新たな比較パターンに対する類似パターンを検出する。なお、この新たな比較パターンの検出は、既にパターン記憶部１３２に複数の比較パターンがある場合には、そのいずれの比較パターンにも類似しない（つまり、類似度スコアが閾値ε以上とならない）部分シーケンスを検出することにより行われる。データストリーム処理部１２１は、このようにして新たな比較パターンを検出していくことで、トレンドとなるパターンの検出を効率的に行うことができる。また、データストリーム処理部１２１は、新たな比較パターンを検出するとき、パターン記憶部１３２（後記）に記憶されたいずれの類似パターン、比較パターンにも類似しない（つまり、類似度スコアが閾値ε以上とならない）所定長の部分シーケンスを検出することにより行うようにしてもよい。
【００５６】
記憶部１３は、データストリームからトレンド検出を行うための各種データを記憶する。この記憶部１３は、例えば、ＲＡＭ（Random Access Memory）と、ＨＤＤ（Hard Disk Drive）とにより実現される。この記憶部１３は、検出条件記憶部１３１と、パターン記憶部１３２と、タイムワーピングデータ記憶部１３３とを含んで構成される。なお、破線で示した類似パターン候補記憶部１３４については、別途、第２の実施の形態で説明する。
【００５７】
検出条件記憶部１３１は、トレンド検出条件を記憶する。このトレンド検出条件は、データストリームから類似パターンを検出するときのシーケンス長の下限値Ｎ、上限値Ｎ´、類似度スコアの閾値ε等を示した情報である。
【００５８】
パターン記憶部１３２は、データストリームの各部分シーケンスとの比較に用いる比較パターンを記憶する。この比較パターンは、最初は、データストリームから所定のシーケンス長（例えば、２Ｎ）のシーケンスを切り取ったものを用い、その後、新たな比較パターンが検出されたときは、その新たな比較パターンが追加される。また、このパターン記憶部１３２は、データストリームから、この比較パターン（追加された新たな比較パターンを含む）に対する類似パターンが検出されると、その類似パターンが追加される。このようにパターン記憶部１３２において、比較パターンやその類似パターン、新たな比較パターンが検出されたときは、その新たな類似パターンが蓄積されていく。なお、パターン記憶部１３２において、比較パターンと、この比較パターンに対する類似パターンとは対応付けて記録される。
【００５９】
タイムワーピングデータ記憶部１３３は、前記したタイムワーピング行列（図２（ａ）および（ｂ）参照）を記憶する。なお、図２（ａ）および（ｂ）では、受信したデータストリームのすべての要素のタイムワーピング行列を示しているが、このタイムワーピングデータ記憶部１３３に用意されるタイムワーピング行列は、１つの比較パターンＹに対して少なくとも２列あればよい。
【００６０】
出力部１４は、データストリーム処理部１２１で検出されたトレンドを出力するトレンド出力部１４１を含んで構成される。この出力部１４は、前記した通信インタフェースや、出力装置等の外部装置との各種データの入出力を行うための入出力インタフェースにより実現される。
【００６１】
次に、図２および図３を参照しつつ、図４を用いて、トレンド検出装置１の処理手順を説明する。図４は、図３のトレンド検出装置の処理手順を示したフローチャートである。なお、トレンド検出装置１には、予めトレンド検出条件入力部１１１経由で、トレンド検出条件（類似度スコアの計算に用いる閾値ε、トレンドとして検出すべきシーケンス長の下限値Ｎおよび上限値Ｎ´等）の入力を受け付け、検出条件記憶部１３１に記憶しておくものとする。
【００６２】
トレンド検出装置１のデータストリーム処理部１２１は、データストリーム入力部１１２経由で、データストリームの入力を受け付けると、まず、時刻１からｔ２Ｎまでのシーケンスを比較パターンとして検出する（Ｓ３０１）。つまり、データストリーム処理部１２１は、データストリームのうち時刻１からｔ２Ｎまでのシーケンスを比較パターンとして切り取り、パターン記憶部１３２に記録する。
【００６３】
次に、データストリーム処理部１２１は、時刻ｔにおいて、ｘｔ（部分シーケンスｘｔ）を受信する（Ｓ３０２）。そして、パターン記憶部１３２に記録された比較パターンと、受信した部分シーケンスｘｔとの類似度スコアを計算する（Ｓ３０３）。この類似度スコアは、前記した式（１）を用いて求める。
【００６４】
次に、データストリーム処理部１２１は、その計算した類似度スコアと、その類似度スコアを計算するときに用いた部分シーケンスの開始位置ｔｓおよび比較パターンの開始位置ｉｓを、この部分シーケンスの終了位置ｔｅおよび比較パターンの終了位置ｉｅと対応付けた部分シーケンスの情報をタイムワーピング行列に記録する（Ｓ３０４）。なお、開始位置（ｔｓ,ｉｓ）は前記した式（２）および式（３）により求める。
【００６５】
ここで、データストリーム処理部１２１は、Ｓ３０３で計算した類似度スコアが閾値ε以上であれば（Ｓ３０５のＹｅｓ）、その部分シーケンスのシーケンス長がＮ以上、Ｎ´以下か否かを判断する（Ｓ３０６）。ここで、部分シーケンスのシーケンス長がＮ以上、Ｎ´以下であれば（Ｓ３０６のＹｅｓ）、データストリーム処理部１２１は、その部分シーケンスの情報（類似度スコアと、部分シーケンスの開始位置ｔｓおよび終了位置ｔｅと、その比較パターンの開始位置ｉｓおよび終了位置ｉｅ）を、この比較パターンに対する類似パターンの情報としてパターン記憶部１３２に記録する（Ｓ３０７）。そして、Ｓ３２１へ進む。
【００６６】
一方、Ｓ３０５において、Ｓ３０３で計算した類似度スコアが閾値ε未満であり（Ｓ３０５のＮｏ）、この地点をスタートとして類似度スコアが閾値ε未満のシーケンスが所定長（例えば、２Ｎ＝４）続いたとき（Ｓ３１１のＹｅｓ）、データストリーム処理部１２１は、その部分シーケンスが、既にパターン記憶部１３２に記録されたいずれかの比較パターンと類似しているか否かを判断する（Ｓ３１２）。ここで、その部分シーケンスが、既にパターン記憶部１３２に記録されたいずれの比較パターンとも類似していないとき（Ｓ３１２のＮｏ）、その部分シーケンスの情報を新たな比較パターンの情報として、パターン記憶部１３２に記録する（Ｓ３１３）。そして、Ｓ３２１へ進む。
【００６７】
一方、Ｓ３１２において、その部分シーケンスが、既にパターン記憶部１３２に記録されたいずれか比較パターンと類似しているとき（Ｓ３１２のＹｅｓ）、Ｓ３０２へ戻る。なお、Ｓ３１２において、部分シーケンスが、既にパターン記憶部１３２に記録されたいずれかのパターンと類似しているか否かは、前記した式（１）に基づき、それぞれのパターンの類似度スコアを計算し、その値が閾値ε以上か否かにより判断する。
【００６８】
データストリーム処理部１２１は、パターン記憶部１３２に記憶された比較パターンおよびこの比較パターンに対する類似パターンの情報を、トレンドのリストとして、トレンド出力部１４１経由で出力する（Ｓ３２１）。
【００６９】
そして、トレンド検出装置１においてデータ受信が終了すると（Ｓ３２２のＹｅｓ）、処理を終了する。一方、まだデータ受信が終了していなければ（Ｓ３２２のＮｏ）、Ｓ３０２へ戻り、部分シーケンスｘｔを受信する。
【００７０】
なお、Ｓ３０６において部分シーケンスのシーケンス長がＮ以上、Ｎ´以下でないとき（Ｓ３０６のＮｏ）、つまり、実際には未だシーケンス長がＮ未満であるとき、Ｓ３０２へ戻る。また、Ｓ３１１において部分シーケンスのシーケンス長が所定の長さ（例えば、２Ｎ）ではないとき（Ｓ３１１のＮｏ）、つまり、部分シーケンスのシーケンス長が所定の長さ（例えば、２Ｎ）未満のとき、Ｓ３０２へ戻る。
【００７１】
ここで具体例を用いて前記の処理を説明する。例えば、トレンド検出条件として、Ｎ＝２、ε＝５０を設定し、データストリーム処理部１２１が、前記した図２（ｂ）に例示したタイムワーピング行列を用いてトレンドの検出を行った場合、以下のようになる。すなわち、データストリーム処理部１２１は、図２（ｂ）に例示したタイムワーピング行列のｔ＝７において、部分シーケンスのシーケンス長≧Ｎ、ｓ（７,４）＝８６≧εとなる部分シーケンスを検出する。よって、データストリーム処理部１２１は、この部分シーケンスの情報（類似度スコア「８６」と、部分シーケンスの開始位置ｔ５および終了位置ｔ7と、その比較パターンの開始位置ｉ２および終了位置ｉ４）をトレンドとして検出する。また、同じくｔ＝７において、部分シーケンスのシーケンス長≧Ｎ、ｓ（７,３）＝６５≧εとなる部分シーケンスを検出する。よって、データストリーム処理部１２１は、この部分シーケンスの情報（類似度スコア「６５」と、部分シーケンスの開始位置ｔ５および終了位置ｔ7と、その比較パターンの開始位置ｉ２および終了位置ｉ３）をトレンドとして検出し、出力する。
【００７２】
また、図２（ｂ）に例示したタイムワーピング行列のｔ＝１５において、部分シーケンスｘｔと比較パターンＹとの類似度スコアが閾値ε未満となり、この地点をスタートとして類似度スコアが閾値ε未満のシーケンスが所定長（例えば、２Ｎ＝４）続いたとき、つまり、ｔ＝１８まで来たとき、データストリーム処理部１２１は、この部分シーケンスが、パターン記憶部１３２に記憶されたいずれの比較パターンとも類似していないと判断して、この部分シーケンス（開始位置ｔ１５から終了位置ｔ１８までの部分シーケンス）を新たな比較パターンとして検出する。そして、データストリーム処理部１２１がトレンドを出力するときには、この検出した新たな比較パターンの情報も含めて出力する。
【００７３】
また、図２（ｂ）では説明のために、トレンド検出装置１が受信したデータストリームのすべての要素のタイムワーピング行列を記述しているが、計算に使用するタイムワーピング行列は少なくとも２列（ｔ−１とｔ）あればよい。例えば、ｔ＝８において、トレンド検出装置１がｘｔ＝１０を受信した場合、タイムワーピング行列のｔ−１番目にはｔ＝７の要素と比較パターンＹとの情報が記録されており、この情報を用いてタイムワーピング行列のｔ番目にｔ＝８の要素と比較パターンＹとの情報を計算して記録する。次に、ｔ＝９においてトレンド検出装置１がｘｔ＝６を受信した場合、タイムワーピング行列のｔ−１番目にはｔ＝８の情報が記録され、ｔ＝７の情報は破棄される。そして、タイムワーピング行列のｔ番目にｔ＝９の要素と比較パターンＹの情報を計算して記録する。これにより、トレンド検出装置１は、タイムワーピングデータ記憶部１３３において、タイムワーピング行列は少なくとも２列（現在と、その１つ前）の情報を保持すれば、類似度スコアの計算が可能となる。
【００７４】
なお、トレンド検出装置１が、トレンドを出力するタイミングは、例えば、Ｓ３１３においてパターン記憶部１３２に新たな比較パターンが記録され、その新たな比較パターンを用いて所定期間、データストリームとの比較を行った後でもよい。このようにすることで、トレンド検出装置１は、新たに検出された比較パターンに対する類似パターンを検出し、出力することができる。
【００７５】
≪第２の実施の形態≫
図２〜図４を参照しつつ、図５を用いて、本発明の第２の実施の形態を説明する。第２の実施の形態のトレンド検出装置１Ａは、類似度スコアが所定の閾値ε以上である類似パターンを発見したとき、その中で最も類似度スコアの高い類似パターンの情報をトレンドとして検出し、出力することを特徴とする。前記した第１の実施の形態と同様の構成要素は同じ符号を付して、説明を省略する。
【００７６】
トレンド検出装置１Ａは、図３に示すように類似パターン候補記憶部１３４を備える。この類似パターン候補記憶部１３４は、類似度スコアが所定の閾値ε以上であり、かつ、そのシーケンス長が、所定の長さ（Ｎ≦シーケンス長≦Ｎ´）である部分シーケンス（以下、類似パターン候補と呼ぶ）の情報を記録（蓄積）する。
【００７７】
このようなトレンド検出装置１Ａの処理手順を、図５を用いて説明する。図５は、第２の実施の形態のトレンド検出装置の処理手順の一部を示したフローチャートである。トレンド検出装置１Ａは、前記した図４のＳ３０１〜Ｓ３０６と同様の処理を行った後、以下のような処理を行う。
【００７８】
トレンド検出装置１Ａのデータストリーム処理部１２１は、部分シーケンスの類似度スコアが閾値ε以上であり、かつ、その部分シーケンスのシーケンス長がＮ以上、Ｎ´以下であると判断したとき（図４のＳ３０５のＹｅｓ→Ｓ３０６のＹｅｓ）、その部分シーケンスの情報（類似度スコアと、部分シーケンスの開始位置ｔｓおよび終了位置ｔｅと、その比較パターンの開始位置ｉｓおよび終了位置ｉｅ）を、この比較パターンに対する類似パターン候補の情報として類似パターン候補記憶部１３４に記録（蓄積）する（Ｓ４０１）。
【００７９】
次に、データストリーム処理部１２１は、この類似パターン候補記憶部１３４に記録された類似パターン候補のうち、その開始位置ｔｓから終了位置ｔｅまでの区間の少なくとも一部が重複しているものがあるか否かを判断し（Ｓ４０２）、区間の少なくとも一部が重複しているものがあるとき（Ｓ４０２のＹｅｓ）、その類似パターン候補の中から、類似度スコアが最も大きい類似パターン候補を選択する（Ｓ４０３）。例えば、類似パターン候補記憶部１３４に、図２（ｂ）の符号２０１に示す部分シーケンス（類似度スコア「１６６」、Ｘ［５：１１］）の情報と、符号２０２に示す部分シーケンス（類似度スコア「１１６」、Ｘ［６：１２］）の情報とが類似パターン候補として記録されていたとき、これらは区間が重複している。従って、データストリーム処理部１２１は、これらの類似パターンの中から、類似度スコアが最も大きい符号２０１に示す部分シーケンス（Ｘ［５：１１］）の情報を選択する。
【００８０】
そして、データストリーム処理部１２１は、図４のＳ３０３で類似度スコアを計算した部分シーケンスの開始位置ｔｓが、Ｓ４０３で選択した類似パターン候補の終了位置ｔｅよりも後であるか否かを判断し（Ｓ４０４）、その部分シーケンスの開始位置ｔｓが、Ｓ４０３で選択した類似パターン候補の終了位置ｔｅよりも後であるとき（Ｓ４０４のＹｅｓ）、Ｓ４０３で選択した類似パターン候補の情報をこの比較パターンに対する類似パターンの情報としてパターン記憶部１３２に記録する（Ｓ４０５）。つまり、データストリーム処理部１２１は、部分シーケンス同士の区間の重複がなくなった時点で、その類似パターン候補のうち、最も類似度スコアが高いものを類似パターン候補記憶部１３４からパターン記憶部１３２に移し変える。そして、その後、図４のＳ３２１と同様の処理を行う。
【００８１】
例えば、図４のＳ３０３で類似度スコアを計算した部分シーケンスの開始位置ｔｓが「１７」の場合、図２（ｂ）のタイムワーピング行例において、このすべての要素の開始位置ｔｓが、符号２０１に示す部分シーケンス（Ｘ［５：１１］）の終了位置「１１」よりも後になっている。従って、データストリーム処理部１２１は、このｔ＝１７の時点で、符号２０１に示す部分シーケンス（類似度スコア「１６６」、Ｘ［５：１１］）の情報を、この比較パターンに対する類似パターンの情報としてパターン記憶部１３２に記録する。
【００８２】
つまり、類似度スコアが閾値ε以上となる類似パターン候補は、同じ区間に重複して存在する可能性があるが、データストリーム処理部１２１は、その中で最も類似度スコアが大きいものを類似パターンとして選択する。これにより、トレンド検出装置１Ａは、同じ様なトレンドを重複して出力することがなくなる。つまり、このトレンド検出装置１Ａの利用者に冗長な情報を与えることがなくなる。
【００８３】
なお、Ｓ４０２において、データストリーム処理部１２１は、この類似パターン候補記憶部１３４に記録された類似パターン候補に、その開始位置ｔｓから終了位置ｔｅまでの区間の重複がないと判断したとき（Ｓ４０２のＮｏ）、Ｓ４０１で記録した類似パターン候補の情報を、この比較パターンに対する類似パターンの情報としてパターン記憶部１３２に記録する（Ｓ４０６）。そして、その後、図４のＳ３２１と同様の処理を行う。
【００８４】
また、このトレンド検出装置１Ａ（１）が、トレンドを出力するタイミングは、例えば、比較パターンのうち、当該比較パターンとこの比較パターンに対する類似パターンの数の合計が所定の値ｋ以上になったときであってもよい。このようにすることで、トレンド装置は、ｋ回以上、類似パターンが検出されたときに、トレンドを出力することができる。つまり、トレンド検出装置１,１Ａは、その比較パターンの類似パターンがｋ回以上で登場することを確認した上で、その比較パターンの類似パターンをトレンドとして出力するので、トレンド検出装置１,１Ａは、より信頼度の高いトレンドを出力することができる。なお、ここでの所定値ｋは、事前に検出条件記憶部１３１に設定しておくものとする。また、このとき出力するトレンドの情報は、比較パターンとこの比較パターンに対する類似パターンの情報（類似度スコアと、部分シーケンスの開始位置ｔｓおよび終了位置ｔｅと、比較パターンの開始位置ｉｓおよび終了位置ｉｅ）とを含むものである。
【００８５】
また、このトレンド検出装置１,１Ａが、トレンドを出力するタイミングは、新たな類似パターンが追加され、その新たな類似パターンを用いて所定期間、データストリームとの比較を行った後でもよい。このようにすることで、トレンド検出装置１は、新たに検出された類似パターンに類似する類似パターンを含むトレンドを出力することができる。なお、ここでは説明を省略したがトレンド検出装置１Ａも、トレンド検出装置１と同様に図４のＳ３１１〜Ｓ３１３と同様の処理により、新たな比較パターンの検出を行う。
【００８６】
なお、前記した第２の実施の形態において、トレンド検出装置１Ａのデータストリーム処理部１２１は、比較パターンに対する類似パターン候補の情報を、順次類似パターン候補記憶部１３４に蓄積することとしたが、これに限定されない。例えば、その類似パターン候補の区間が重複していて、より類似度スコアが高い類似パターン候補を検出したとき、その類似パターン候補の情報を上書きして記録するようにしてもよい。このようにすることで、類似パターン候補記憶部１３４に要するメモリ容量を削減することができる。
【００８７】
≪第３の実施の形態≫
次に、図２〜図５を参照しつつ、図６を用いて、本発明の第３の実施の形態を説明する。第３の実施の形態のトレンド検出装置１Ｂは、比較パターンとその比較パターンに対する類似パターンを１つのグループとしたとき、そのグループ内のパターンの数の合計が所定の値ｌ以上になったとき、そのパターンの中から代表となるパターンを選択する。そして、その選択したパターンをトレンドとして出力することを特徴とする。前記した第１,第２の実施の形態と同じ構成要素は同じ符号を付して、説明を省略する。
【００８８】
このようなトレンド検出装置１Ｂの処理手順を、図６を用いて説明する。図６は、第３の実施の形態のトレンド検出装置の処理手順の一部を示したフローチャートである。トレンド検出装置１Ｂは、事前に所定値ｌを検出条件記憶部１３１に設定しておくものとする。そして、トレンド検出装置１Ｂは、前記した前記した図４のＳ３０１〜Ｓ３０７、Ｓ３１１〜Ｓ３１３と同様の処理を行った後、以下のような処理を行う。
【００８９】
トレンド検出装置１Ｂのデータストリーム処理部１２１は、パターン記憶部１３２に記録された比較パターンのうち、当該比較パターンとその類似パターンの数の合計が所定の値ｌ以上のグループがあるか否かを判断する（Ｓ５０１）。ここで、当該比較パターンの数とその類似パターンの数の合計が所定の値ｌ以上のグループがあるとき（Ｓ５０１のＹｅｓ）、そのグループ内のパターンごとに、同じグループ内の他のパターンそれぞれとの類似度スコアを計算して、その合計値を求める（Ｓ５０２）。
【００９０】
例えば、このトレンド検出装置１Ｂに、前記した所定値ｌとして「３」が設定され、グループ内おいて、比較パターンＡに対し、類似パターンａ,ｂ,ｃという３つのパターンがあったとき、データストリーム処理部１２１は、比較パターンＡと、類似パターンａ,ｂ,ｃそれぞれとの類似度スコアを計算し、その合計値を求める。例えば、比較パターンＡと、類似パターンａ,ｂ,ｃとの類似度スコアがそれぞれ「５０」、「６０」、「７０」であれば、これらの合計値である「１８０」を求める。また、同様に、類似パターンａについても、この類似パターンａと比較パターンＡおよび類似パターンｂ,ｃそれぞれとの類似度スコアを計算し、これらの合計値を求める。データストリーム処理部１２１は、このような計算を、グループ内のすべてのパターンについて行う。
【００９１】
そして、データストリーム処理部１２１は、その合計値が最大のパターンの情報をトレンドとして出力し（Ｓ５０３）、その後、図４のＳ３２２と同様の処理を行う。
【００９２】
なお、パターン記憶部１３２に記録された比較パターンのうち、当該比較パターンとその類似パターンの数の合計が所定の値ｌ以上のグループがなかったとき（Ｓ５０１のＮｏ）、図４のＳ３０２へ戻る。
【００９３】
このようにすることで、トレンド検出装置１Ｂは、同じグループに属するパターンのうち、どのパターンとも類似している重心に近いパターン（代表パターン）を、トレンドとして選択し、出力することができる。なお、このような代表パターンの選択は、例えば、トレンド検出装置１Ｂにおいて新たな類似パターンが検出されるたびに行う。なお、この１グループに含まれるパターンの数の上限値を設けてもよい。この場合、データストリーム処理部１２１は、グループ内のパターンのうち、類似度スコアの合計値が最も小さいものを新たに検出された類似パターンと入れ替えるようにする。
【００９４】
また、データストリーム処理部１２１は、類似度スコアの合計値が最大となったパターンが、そのパターンの属するグループにおける比較パターンではないとき、その合計値が最大となった類似パターンを、パターン記憶部１３２に記録されたそのグループにおける比較パターンと置き換える。そして、データストリーム処理部１２１は、この置き換え後の比較パターンを用いて、部分シーケンスとの比較を行うようにしてもよい。このようにすることで、トレンド検出装置１Ｂは、データストリームからトレンドを検出するとき、すべての類似パターンを用いて比較を行う必要がなくなるので、計算量やメモリ使用量を削減することができる。
【００９５】
本実施の形態に係るトレンド検出装置１,１Ａ,１Ｂは、前記したような処理を実行させるトレンド検出プログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記憶媒体（ＣＤ−ＲＯＭ等）に記憶して提供することも可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。
【００９６】
≪実験結果≫
次に、トレンド検出装置１Ａ,１Ｂを用いた実験結果を説明する。まず、データストリームに人工データを用いた場合の実験結果を説明する。図７は、本実験で用いたデータストリームと、そのデータストリームから検出されたトレンドとを示した図である。図７の符号６１０に示すデータストリームは異なる２つのパターンが交互に現れ、このうち半円形のパターンは異なる周期で現れるものである。グラフの縦軸は、データストリームのデータの値を示し、横軸は、時刻を示す。このようなデータストリームに対し、トレンド検出装置１ＢにＮ＝１５００を設定してトレンドを検出したところ、符号６１１に示すパターンと、符号６１２に示すパターンとを別個のパターンとして検出することができた。つまり、このトレンド検出装置１Ｂによれば、データストリームについてタイムワーピングを考慮してトレンドを検出することができることが示された。
【００９７】
また、同じＮ＝１５００を設定したトレンド検出装置１Ａにより、符号６１０に示すデータストリームからトレンドを検出したところ、比較パターン７１０,７２０に対し図８に示すような類似パターンが検出された。図８は、図７のデータストリームから検出されたトレンドのグループを示した図である。すなわち、符号７１０に示す比較パターンに対し、符号７１１〜７１４に示す４つの類似パターンが検出された（グループ１）。また、符号７２０に示す比較パターンに対し、符号７２１,７２２,７２３,７２４に示す類似パターンが検出された（グループ２）。つまり、このトレンド検出装置１Ａによれば、比較パターンに対する類似パターンも検出することができることが示された。
【００９８】
次に、データストリームとして、実際の測定データを用いた場合の実験結果を説明する。図９は、本実験で用いたデータストリームと、そのデータストリームから検出されたトレンドとを示した図である。図９の符号８１０に示すデータストリームは、被験者の各部位にマーカを取り付け、その取り付けた部位の角速度を１秒間に１２０回というサンプリング周期で測定したモーションキャプチャデータである。このデータには、被験者の二の腕、肘下、太もも、ふくらはぎの各部位に左右対称に取り付けられた１６個の角速度データが含まれている。この実験では、被験者が「walking−squats−running−standing−stretching−walking−jumping-drinking-quenches-walking」という順に８つのモーションを行っている。このようなデータストリームに対し、Ｎ＝２５０を設定したトレンド検出装置１Ｂによりトレンドを検出したところ、符号８１１〜８２１に示す１１個のパターンがトレンドとして検出された。また、これらのトレンドのうち最も高い頻度で登場するパターン、つまり類似パターンが最も多く検出されたパターンは、符号８１１に示すパターンであった。図１０は、図９の符号８１１に示すパターンと同じグループに属する類似パターンを示した図である。図１０に示すように、符号８１１に示すパターンに対する類似パターンとして、符号９１２〜９１５に示す４つのパターンが検出された。これらのパターンはすべて被験者が「walking」モーションを行った区間から検出されており、本実施の形態のトレンド検出装置１Ａ,１Ｂによれば、データストリームにおけるモーションごとのトレンドを正確に検出したことが示された。
【図面の簡単な説明】
【００９９】
【図１】各実施の形態のトレンド検出装置によるトレンドの検出を概念的に説明した図である。
【図２】（ａ）は、各実施の形態のタイムワーピング行列を概念的に示した図であり、（ｂ）は、（ａ）のタイムワーピング行列の具体例を示した図である。
【図３】各実施形態のトレンド検出装置の構成図である。
【図４】図３のトレンド検出装置の処理手順を示したフローチャートである。
【図５】第２の実施の形態のトレンド検出装置の処理手順の一部を示したフローチャートである。
【図６】第３の実施の形態のトレンド検出装置の処理手順の一部を示したフローチャートである。
【図７】本実験で用いたデータストリームと、そのデータストリームから検出されたトレンドとを示した図である。
【図８】図７のデータストリームから検出されたトレンドのグループを示した図である。
【図９】本実験で用いたデータストリームと、そのデータストリームから検出されたトレンドとを示した図である。
【図１０】図９の符号８１１に示すパターンと同じグループに属する類似パターンを示した図である。
【図１１】（ａ）および（ｂ）は、比較例となるＤＴＷによるタイムワーピング行列を例示した図である。
【符号の説明】
【０１００】
１,１Ａ,１Ｂ      トレンド検出装置
１１    入力部
１２    処理部
１３    記憶部
１４    出力部
１１１  トレンド検出条件入力部
１１２  データストリーム入力部
１２１  データストリーム処理部
１３１  検出条件記憶部
１３２  パターン記憶部
１３３  タイムワーピングデータ記憶部
１３４  類似パターン候補記憶部
１４１  トレンド出力部
【図１】
0004939349.tif 000008
【図２】
0004939349.tif 000009
【図３】
0004939349.tif 000010
【図４】
0004939349.tif 000011
【図５】
0004939349.tif 000012
【図６】
0004939349.tif 000013
【図１１】
0004939349.tif 000014
【図７】
0004939349.tif 000015
【図８】
0004939349.tif 000016
【図９】
0004939349.tif 000017
【図１０】
0004939349.tif 000018