(57)【要約】【課題】本発明は、時系列から基準系列と類似するサブ時系列を抽出するための方法及び装置に関する。【解決手段】時系列及び基準系列の変化傾向のそれぞれに基づいて、時系列及び基準系列を変換するステップと、変換された時系列を複数のサブ時系列に分割するステップと、複数のサブ時系列のうちの各サブ時系列に対して、各サブ時系列と変換された基準系列との編集距離を算出するステップと、算出された編集距離に基づいて、複数のサブ時系列から基準系列と類似するサブ時系列を抽出するステップと、を含む。【選択図】図１
2013025805.tif 000002
【特許請求の範囲】
【請求項１】
時系列から基準系列と類似するサブ時系列を抽出する方法であって、コンピュータが、
前記時系列及び前記基準系列を、それぞれ前記時系列及び前記基準系列の変化傾向を表す系列に変換し、
変換された時系列を複数のサブ時系列に分割し、
前記複数のサブ時系列のうちの各サブ時系列と変換された基準系列との間の編集距離を算出し、
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出することを特徴とする方法。
【請求項２】
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ前または複数前の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ前または複数前の要素に対する変化を表す系列である、
請求項１に記載の方法。
【請求項３】
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ後または複数後の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ後または複数後の要素に対する変化を表す系列である、
請求項１に記載の方法。
【請求項４】
前記編集距離は、重み付け編集距離であり、以下の要求のうちの一つまたは複数のこと、即ち、
挿入操作について、異なる要素の挿入に対して異なる重みの付与が許可されること、
削除操作について、異なる要素の削除に対して異なる重みの付与が許可されること、及び／又は、
置換操作について、異なる要素ペアの置換に対して異なる重みの付与が許可されることを満たす、
請求項１に記載の方法。
【請求項５】
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出する処理は、
前記複数のサブ時系列から、所定の閾値より小さい編集距離を有する一つまたは複数のサブ時系列を、前記基準系列と類似するサブ時系列として抽出することを含む、請求項１に記載の方法。
【請求項６】
変換された時系列を複数のサブ時系列に分割する処理によって分割された各サブ時系列は所定の長さを有し、分割された各サブ時系列の先頭間の間隔は所定のステップ長さであり、前記所定の長さおよび前記所定のステップ長さは前記基準系列の長さと同じであっても異なっていてもよい、請求項１乃至５のいずれか一項に記載の方法。
【請求項７】
時系列から基準系列と類似するサブ時系列を抽出する装置であって、
前記時系列及び前記基準系列を、それぞれ前記時系列及び前記基準系列の変化傾向を表す系列に変換するように構成される系列変換手段と、
変換された時系列を複数のサブ時系列に分割するように構成されるサブ時系列分割手段と、
前記複数のサブ時系列のうちの各サブ時系列と変換された基準系列との間の編集距離を算出するように構成される編集距離算出手段と、
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出するように構成される類似時系列抽出手段と、を含む装置。
【請求項８】
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ前または複数前の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ前または複数前の要素に対する変化を表す系列である、
請求項７に記載の装置。
【請求項９】
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ後または複数後の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ後または複数後の要素に対する変化を表す系列である、
請求項８に記載の装置。
【請求項１０】
コンピュータに、請求項1乃至６のいずれか一項に記載の方法の手順を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列処理の分野に関し、具体的には、時系列から基準系列と類似するサブ時系列を抽出するための方法及び装置に関する。
【背景技術】
【０００２】
類似なサブ時系列の抽出とは、与えられた基準と類似するサブ系列を抽出することを意味している。類似なサブ時系列の抽出は、時系列の予測、クラスタリング、異常検出などのジョブに応用される基礎技術である。例えば、時系列の予測には、トレーニングに用いられるように類似なサブ系列を抽出する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
一般的には、類似なサブ系列の抽出は二つのステップに関わる。１番目のステップは、時系列の分割、即ち、時系列を複数の部分に分割するものである。２番目のステップは、類似性算出に基づいて類似するサブ系列を抽出するものである。従来の類似サブ系列の抽出技術には、主に以下の三つの問題が存在する。（１）融通のきかない分割なので、候補集合が小さくなること。（２）記憶空間及び処理時間を消費すること。（３）物理的意義を余り考慮しないこと。
【課題を解決するための手段】
【０００４】
従って、上記問題を解決できる技術の提案が希望されている。
【０００５】
以下、本発明の幾つかの面に関する基本的な理解を提供するように、本発明についての簡単な概述を提供する。この概述は本発明に対する網羅的な記述ではないことを理解すべきである。本発明の鍵または要部を特定することを意図しておらず、本発明の範囲を限定することも意図していない。その目的は単に簡略化した形式で、ある概念を提供することだけであり、これをその後の論述のより詳しい記述の序文とする。
【０００６】
本発明の一つの目的は、時系列から基準系列と類似するサブ時系列を抽出するための方法及び装置を提供することにある。
【０００７】
本発明の一つの側面によれば、時系列から基準系列と類似するサブ時系列を抽出するための方法が提供される。本方法は、時系列及び基準系列それぞれの変化傾向に基づいて、時系列及び基準系列を変換するステップと、変換された時系列を複数のサブ時系列に分割するステップと、前記複数のサブ時系列のうちの各サブ時系列に対して、各サブ時系列と変換された基準系列との編集距離を算出するステップと、算出された編集距離に基づいて、前記複数のサブ時系列から基準系列と類似するサブ時系列を抽出するステップと、を含む。
【０００８】
本発明の他の側面によれば、時系列から基準系列と類似するサブ時系列を抽出するための装置が提供される。本装置は、時系列及び基準系列それぞれの変化傾向に基づいて、時系列及び基準系列を変換する系列変換手段と、変換された時系列を複数のサブ時系列に分割するサブ時系列分割手段と、複数の時系列のうちの各時系列に対して、各時系列と変換された基準系列との編集距離を算出する編集距離算出手段と、算出された編集距離に基づいて、前記複数のサブ時系列から基準系列と類似するサブ時系列を抽出する類似時系列抽出手段と、を含む。
【０００９】
また、本発明の実施例は、上記方法を実現するためのコンピュータプログラムを提供した。
【００１０】
また、本発明の実施例は少なくともコンピュータによる読み取り可能な媒体の形式のコンピュータプログラム製品をさらに提供した。該コンピュータプログラム製品に上記方法を実現するためのコンピュータプログラムコードが記憶されている。
【００１１】
図面との関連で以下に述べる本発明を実施するための最良の形態によって、本発明のこれらの及びその他のメリットがより明らかになる。
【図面の簡単な説明】
【００１２】
図面との関連で以下に与える本発明の実施例に対する記述を参照すれば、本発明の上記及び他の目的、特徴及びメリットをより容易に理解できるであろう。図面における各部はただ本発明の原理を示すためのものである。図面において、同一又は類似な技術的特徴又は部分は、同一又は類似の符号で示す。
【図１】本発明の実施例による、時系列から基準系列と類似するサブ時系列を抽出する方法を示すフローチャートである。
【図２】一週間の間の負荷時系列を示すグラフである。
【図３】二つの負荷サブ時系列及び一つの基準系列を示すグラフである。
【図４】本発明の実施例による、時系列から基準系列と類似するサブ系列を抽出するための装置のブロック図である。
【図５】本発明の時系列から基準系列と類似するサブ時系列を抽出する方法及び装置を実施するためのコンピューティング装置の例示的な構造を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら本発明の実施例を説明する。本発明の一図面または一実施例に記載の要素及び特徴は、一つまたは複数の他の図面または実施例に示される要素及び特徴と結合することができる。明確のため、図面及び明細書では、本発明と直接関係しない、当業者にとって既知の部品及び処理の表示及び記載は省略した。
【００１４】
図１を参照しながら、本発明の実施例による、時系列から基準系列と類似するサブ時系列を抽出するための方法１００を説明する。
【００１５】
図１に示すように、ステップＳ１０２において、時系列及び基準系列それぞれの変化傾向に基づいて時系列及び基準系列を変換することができる。
【００１６】
具体的には、時系列における現在要素の一つ前の要素または複数前の要素に対する変化に基づいて時系列を変換することができる。また、基準系列における現在要素の一つ前の要素または複数前の要素に対する変化に基づいて基準系列を変換することができる。
【００１７】
代わりに、時系列における現在要素の一つ後の要素又は複数後の要素に対する変化に基づいて時系列を変換することができる。また、基準系列における現在要素の一つ後の要素または複数後の要素に対する変化に基づいて基準系列を変換することができる。
【００１８】
ここで、時系列及び基準系列の変換に対して同じ変換規則を採用する。なお、時系列と基準系列の変換は以上の方式に限定されず、当業者が想到できるいずれの他の方式で時系列及び基準系列を変換してもよく、このような変換は系列の変化傾向を反映することができればよい。
【００１９】
次に、ステップＳ１０４において、変換後の時系列を複数のサブ時系列に分割することができる。
【００２０】
好ましくは、基準系列の長さと異なっていてもよい所定の分割ステップ長さに従って、変換された時系列を複数のサブ時系列に分割することができる。また、基準系列の長さと異なっていてもよい所定の分割する長さに従って、変換された時系列を複数のサブ時系列に分割することができる。時系列に対してこのような柔軟な分割を行うことによって、時系列をより能動的に分割することができ、必要に応じて相応の分割結果が得られ、必要する類似なサブ系列が取得される。例えば、基準系列と類似するが、長さが基準系列と異なる類似サブ系列を取得することができる。
【００２１】
次に、ステップＳ１０６において、分割された複数のサブ時系列のうちの各サブ時系列に対して、各サブ時系列と変換された基準系列との編集距離を算出することができる。
【００２２】
好ましくは、上記算出において、各サブ時系列と変換された基準系列との重み付け編集距離を算出する。尚、以下の要求うちの一つまたは複数を満足することができる。即ち、挿入操作について、異なる要素の挿入に対して異なる重みの付与が許可されること、削除操作について、異なる要素の削除に対して異なる重みの付与が許可されること、及び、置換操作について、異なる要素ペアの置換に対して、異なる重みの付与が許可されることを含む。重みを利用しない伝統的な方法と比べると、各サブ時系列と変化後の基準系列との重み付け編集距離を算出することによって、基準系列とより類似するサブ時系列が基準系列までのより短い編集距離を有し得るようになる。
【００２３】
ステップＳ１０８において、算出された編集距離に基づいて複数のサブ時系列から基準系列と類似するサブ時系列を抽出する。
【００２４】
具体的には、複数のサブ時系列から所定の閾値より小さい編集距離を有する一つまたは複数のサブ時系列を基準系列と類似するサブ時系列として抽出する。
【００２５】
好ましくは、複数のサブ時系列から最小編集距離を有するサブ時系列を所定の数だけ基準系列と類似するサブ時系列として抽出する〔つまり、編集距離が小さい順に所定の数だけ抽出する〕。
【００２６】
もちろん、基準系列と類似するサブ時系列を抽出するのは、上記の方式で行うことに限定されず、当業者が想到できるいずれの方式で実行してもよい。
【００２７】
以下、図２及び３を参照し、負荷時系列から基準系列と類似するサブ時系列を抽出する方法を説明する。なお、図２は一週間の負荷時間系列を示すグラフであり、図３は、二つの負荷サブ時系列及び一つの基準系列を示すグラフである。しかし、負荷と関連する時系列はただ一つの例に過ぎないことを理解すべきである。実際は、本発明により処理される時系列はいかなる時系列であってもよく、図２及び図３の形式に限定されない。
【００２８】
まず、時系列と基準系列それぞれの変化傾向に基づいて、時系列と基準系列を変換する、即ち、現在要素と、その一つ前の要素または複数前の要素との変化を比較することによって多種の変換を行う。例えば、時系列はc1,c2,c3,……,cnであり、ｎは１より大きい整数である。基準系列はb1,b2,……,bmであり、ｍは１より大きい整数である。通常、ｍはｎより小さい。もちろん、ｎより大きい場合も排除されない。
【００２９】
例えば、以下の（１）式により時系列を変換する一方、以下の（２）式により基準系列を変換してもよい。
【数１】
2013025805.tif 000003
ただし、必要に応じて予めeを設定しておく、またはパラメータ・トレーニングによってeを取得してもよい。
【００３０】
または、以下の（３）式により時系列を変換する一方、以下の（４）式により基準系列を変換することができる。
【数２】
2013025805.tif 000004
ただし、必要に応じて予めgを設定しておく、またはパラメータ・トレーニングによってgを取得してもよい。
【００３１】
（１）式及び（２）式または（３）式及び（４）式は、例示的な変換方式に過ぎず、実際は、必要に応じて当業者が想到できる他のいかなる変換方式を採用してもよく、当該方式は時系列と基準系列との変化傾向を反映できるものであればよい。
【００３２】
次に、式（１）を例として図２に示された負荷時系列の変換を説明する。式（１）により、図２におけるグラフを次の形に変換することができる。
【００３３】
20022222212000012222100001222222200000002221000000222222000000012222100000222222000000002222000000022222200000002220000000002222200000002220000000222222000000000220000。
【００３４】
そして、（２）式により基準系列（図示せず）を変換する。
【００３５】
次に、上記の時系列に対して分割を行うことができる。
【００３６】
好ましくは、柔軟な分割方式、即ち、基準系列の長さと異なっていてもよい所定のステップの長さ及び所定の長さに従って、変換された時系列を複数のサブ時系列に分割する。
【００３７】
仮に変換された基準系列の長さは８とする。基準系列の長さと同じ所定のステップの長さ及び所定の長さに従って時系列を分割する場合、即ち、分割処理に使用される所定のステップ長さ及び所定の長さのいずれも８である場合に、上記時系列は、例えば、以下のように分割される。
20022222,21200001,22221000,01222222……
同様に、仮に変換後の基準系列の長さは８とする。基準系列の長さと異なる所定のステップ長さに従い、かつ、基準系列の長さと同一の所定の長さに従って時系列を分割する場合、例えば、分割処理に使用される所定のステップ長さは６であり、所定の長さは８である場合、上記時系列は以下のように分割することができる。〔つまり、分割された（互いに重複する）各サブ系列の長さは８であり、各サブ系列の先頭の間のステップ（間隔）の長さは６である。〕
20022222,22212000,00012222,22100001……
引き続き変換後の基準系列の長さは８とする。基準系列の長さと同一の所定のステップ長さに従い、かつ、基準系列の長さと異なる所定の長さに従って時系列を分割する場合、例えば、分割処理に使用される所定のステップ長さは8であり、所定の長さは6である場合に、上記時系列は以下のように分割することができる。〔つまり、分割された各サブ系列の長さは６であり、各サブ系列の先頭の間のステップ（間隔）の長さは８であり、各サブ系列の末尾と次のサブ系列の先頭との間に長さ２のギャップがある。〕
200222,212000,222210,012222……
引き続き変換後の基準系列の長さは８とする。基準系列の長さと異なる所定のステップ長さに従い、かつ、基準系列の長さと異なる所定の長さに従って時系列を分割する場合、例えば、分割処理に使用される所定のステップ長さは6であり、所定の長さは6である場合、上記時系列は以下のように分割することができる。
200222,222120,000122,221000……
ここでの６及び８といった長さおよびステップ長さは例示的なものであり、本発明を限定するものではないことを理解しておくべきである。
【００３８】
複数のサブ時系列のうち各時系列と変換された基準系列との重み付け編集距離を算出する。例えば、変換されたサブ時系列Ｘ{c1,c2,…,ci}と基準系列Y{b1,b2,…,bj}との編集距離D(i,j)は、以下の式で算出することができる。
【数３】
2013025805.tif 000005
【００３９】
二つの系列の間の編集距離とは、幾つかの操作により一方の系列を他方の系列に変換するのに必要な最小コストを意味する。なお、wiは挿入操作のコストであり、wdは削除操作のコストであり、wrは置換操作のコストである。実際には、上述したように、挿入操作について、異なる要素の挿入に対して異なる重みの付与を許可し、削除操作について、異なる要素の削除に対して異なる重みの付与を許可し、置換操作について、異なる要素ペアに対して異なる重みの付与を許可することができる。
【００４０】
以下では、挿入操作について、異なる要素の挿入に同一重みを付与し、削除操作について、異なる要素の削除に対して同一重みを付与し、及び置換操作について、異なる要素ペアの置換に対して異なる重みを付与する。（6）-（8）（式）により、wi，wd及びwrを特定してもよい。
【数４】
2013025805.tif 000006
ただし、xi及びyiは距離を算出すべき二つの系列中の対応する要素である。
【００４１】
（5）-（8）式により編集距離を算出した後に、重み付け編集最小距離の所定の閾値よりも小さいサブ時系列、又は距離の最も小さい一定数のサブ系列を、類似なサブ時系列として抽出する。
【００４２】
図３は、二つの負荷サブ時系列及び一つの基準系列を示すグラフである。図３に示すように、Ａ及びＢはそれぞれサブ時系列を示し、Ｃは基準系列を示す。図２の時系列に対応するサブ時系列を与えるわけではなく、（5）-（8）式を説明するために、任意にサブ系列Ａ及びサブ時系列Ｂを与えている。図２の時系列に分割を行ってサブ時系列を取得し、そして、取得したサブ時系列と基準系列Ｃとの編集距離を算出してもよいことを理解すべきである。
（１）式により、サブ時系列Ａを以下のように変換することができる。00112222111000122221000。
（１）式により、サブ時系列Ｂを以下のように変換することができる。00112222222000122221000。
（２）式により、サブ時系列Ｃを以下のように変換することができる。00112222000200122221000。
【００４３】
伝統的な編集距離の算出方法、即ち、重みが導入されていない場合、サブ時系列Ａと基準時系列Ｃの間の編集距離D(A,C)＝4となり、サブ時系列Ｂと基準時系列Ｃの間の編集距離D(B,C)＝4となる。
【００４４】
（5）-（8）式により算出される重み付け編集距離は以下の通りであり、サブ時系列Ａと基準時系列Ｃの間の編集距離D’(A,C)＝2.5となり、サブ時系列Ｂと基準時系列Ｃの間の編集距離D’(B,C)＝4となる。
【００４５】
図３から、時系列Ａ、時系列Ｂ及び基準系列Ｃの大部分が重なっており、これらの中間部分のみが異なることが分かる。サブ時系列Ｂの中間部分が上に位置し、サブ時系列Ａの中間部分が中間に位置し、基準系列Ｃの中間部分が下に位置するため、サブ時系列Ａのほうが基準Ｃにより近い。重み付け編集距離の算出方法で算出された結果は、図３の実際の状況により合っており、サブ時系列Ａと基準系列Ｃとの編集距離D’(A,C)＝2.5、サブ時系列Ｂと基準時系列Ｃの間の編集距離D’(B,C)＝4から、D’(A,C)＜D’(B,C)となる。これに比べて、重み付けが導入されていない伝統的な編集方法においては、サブ時系列Ａと基準系列Ｃとの編集距離D(A,C)＝4、サブ時系列Ｂと基準時系列Ｃの間の編集距離D(B,C)＝4から、D(A,C)＝D(B,C)となるが、このような結果は図３の実際の状況を反映することができない。
【００４６】
以下、図４を参照しながら本発明の実施例である、時系列から基準系列と類似するサブ時系列を抽出する装置４００を説明する。なお、上記方法と対応する部分と重複しない、装置４００の基本的な枠組のみを説明する。
【００４７】
図４に示すように、装置４００は、系列変換手段４０２と、サブ時系列分割手段４０４と、編集距離算出手段４０６と、類似サブ時系列抽出手段４０８とを含むことができる。
【００４８】
なお、系列変換手段４０２は、時系列及び基準系列それぞれの変化傾向により、時系列及び基準系列を変換するように構成されてもよい。
【００４９】
系列変換手段４０２は、時系列変換サブ手段と、基準系列変換サブ手段と（いずれも図示せず）を含んでもよい。時系列変換サブ手段は、時系列における現在要素の一つ前の要素または複数前の要素に対する変化に基づいて時系列を変換する。基準系列変換手段は、基準系列における現在要素の一つ前の要素または複数前の要素に対する変化に基づいて基準系列を変換することができる。
【００５０】
好ましくは、時系列変換サブ手段は、時系列における現在要素の一つ後の要素または複数後の要素に対する変化に基づいて、時系列を変換することができる。基準系列変換サブ手段は、基準系列における現在要素の一つ後の要素または複数後の要素に対する変化に基づいて、基準系列を変換することができる。
【００５１】
サブ時系列分割手段４０４は、変換された時系列を複数のサブ時系列に分割するように構成されてもよい。
【００５２】
サブ時系列分割手段４０４は、さらに、基準系列の長さと異なっていてもよい所定の分割ステップの長さ及び/又は基準系列の長さと異なっていてもよい所定の分割長さに従って、変換された時系列を複数のサブ時系列に分割するように構成されてもよい。
【００５３】
編集距離算出手段４０６は、複数のサブ時系列のうちの各時系列に対して、各時系列と変換された後の基準系列との編集距離を算出するように構成されてもよい。
【００５４】
なお、編集距離算出手段４０６は各時系列と変換された基準系列との間の重み付け編集距離を算出することができる。なお、以下の要求のうちの一つ又は複数を満たしている。挿入操作について、異なる要素の挿入に対して異なる重みの付与を許可すること、削除操作について、異なる要素の削除について異なる重みの付与を許可すること、置換操作について、異なる要素ペアの置換に対して異なる重みの付与を許可すること。
【００５５】
類似サブ時系列抽出手段４０８は、算出された編集距離に基づいて、複数の時系列から、基準系列と類似するサブ時系列を抽出するように構成されてもよい。
【００５６】
類似サブ時系列抽出手段４０８は、複数のサブ時系列から、所定の閾値より小さい編集距離を有する一つ又は複数のサブ時系列を、基準系列と類似するサブ時系列抽出するように構成されてもよい。
【００５７】
代わりに、類似サブ時系列抽出手段４０８は、さらに、複数のサブ時系列から一定数の、最小編集距離を有するサブ時系列を、基準系列と類似するサブ時系列抽出するように構成されてもよい。〔つまり、編集距離が小さいほうから一定数を抽出する。〕
本発明の実施例によれば、より迅速に類似なサブ時系列を抽出することができ、時系列の柔軟な分割を実現するとともに、実用に応じて系列の物理的な意義により、類似な時系列を抽出することができる。
【００５８】
上記の具体的な実施例との関連で本発明の基本原理を説明したが、当業者にとって、本発明の方法及び装置のすべてまたは任意のステップまたは部品は、任意のコンピューティング装置（プロセッサや記憶媒体などを含む）またはコンピューティング装置のネットワークにおいて、ハードウェア、ファームウェア及びソフトウェアまたはこれらの組み合わせにより実現されることを理解すべきである。これは、本発明の明細書を読んだ当業者の基本なプログラミング技能で実現可能なものである。
【００５９】
したがって、本発明の目的は、任意のコンピューティング装置において一つのプログラムまたは一組のプログラムを実行することによって実現されてもよい。上記コンピューティング装置は公知の汎用装置であってもよい。したがって、本発明の目的は、さらに、前記方法または装置を実現するためのプログラムコードを含むプログラム製品を提供することによって実現されてもよい。つまり、このようなプログラム製品も本発明を構成することができ、かつこのようなプログラムを記憶する製品も本発明を構成することがきることが分かる。明らかなように、前記記憶媒体は任意の公知の記憶媒体または将来に開発される任意のものであってもよい。
【００６０】
本発明の実施例は、ソフトウェア及び／又はファームウェアにより実現される場合に、記憶媒体又はネットワークから、専用ハードウェア構造を有するコンピュータ（例えば、図５に示される汎用コンピュータ５００）へ当該ソフトウェアを構成するプログラムをインストールする。当該コンピュータは、各種のプログラムがインストールされた時に、各種機能の実行等が可能である。
【００６１】
図５において、中央処理手段(ＣＰＵ)５０１は、読取専用メモリ(ＲＯＭ)５０２に記憶されたプログラム、又は記憶部５０８からランダムアクセスメモリ(ＲＡＭ)５０３にロードされたプログラムに基づいて、各種の処理を実行する。ＲＡＭ５０３において、必要に応じ、ＣＰＵ５０１が各種の処理等を実行するときに必要されるデータも記憶される。ＣＰＵ５０１、ＲＯＭ５０２及びＲＡＭ５０３は、バス５０４を経由して互いに接続される。入力/出力インターフェース５０５もバス５０４に接続される。
【００６２】
以下の部品が入力/出力インターフェース５０５に接続される。入力部５０６（キーボード、マウス等を含む）と、出力部５０７（ブラウン管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）等のようなディスプレイ及びスピーカ等を含む）と、記憶部５０８（ハードディスク等を含む）と、通信部５０９（ＬＡＮカードのようなネットワークインターフェースカード、モデム等を含む）とを含む。必要に応じて、通信部５０９が入力/出力インターフェース５０５に接続されてもよい。取り外し可能な媒体５１１、例えば磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等が必要に応じてドライブ５１０に取り付けられ、これによりその中から読み出されたコンピュータプログラムが必要に応じて記憶部５０８にインストールされる。
【００６３】
ソフトウェアにより上記の一連の処理を実現する場合は、ネットワーク、例えばインターネット、または記憶媒体、例えば取り外し可能媒体５１１からソフトウェアを構成するプログラムをインストールする。
【００６４】
このような記憶媒体は、図５に示された、その中にプログラムが記憶されており、デバイスから離れて配送されてユーザにプログラムを提供する取り外し可能な媒体５１１に限定されないことを、当業者は理解するはずである。取り外し可能な媒体５１１としては、例えば、磁気ディスク（フロッピー（登録商標）ディスクを含む）、光ディスク（コンパクトディスクリードオンリーメモリ（CD−ROM）やディジタルヴァーサタイルディスク（DVD）を含む）、光磁気ディスク（ミニディスク(MD)（登録商標）を含む）及び半導体メモリを含む。または、記憶媒体は、ＲＯＭ５０２、記憶部５０８に含まれるハードディスクであって、プログラムが記憶されており、かつそれらを含むデバイスと一緒にユーザに配送されるハードディスクなどであってもよい。
【００６５】
本発明は、さらに、機器による読み取り可能な命令コードが記憶されているプログラム製品を提供する。命令コードは、機器に読み取られて実行される際に、上記の本発明の実施例による方法を実行することができる。
【００６６】
相応に、上記の機器による読み取り可能な命令コードが記憶されているプログラム製品を搭載するための記憶媒体も本発明の開示に含まれる。記憶媒体はフロッピーディスク、光ディスク、光磁気ディスク、メモリカード、メモリスティックなどを含むが、これらに限定されない。
【００６７】
当業者は、ここで与えられた例は、例示的なものであり、これらに限定されないことを理解すべきである。
【００６８】
明細書において、「１番目」、「２番目」及び「Ｎ番目」の記載は、説明した特徴を区別し、本発明を明瞭に説明するためのものである。したがって、これらをいかなる限定性意味と見なすべきでもない。
【００６９】
一つの例として、上記方法の各ステップ及び上記装置の各構成モジュール及び/または手段は、ソフトウェア、ファームウェア及びハードウェアまたはこれらの組み合わせとして実現されてもよく、かつ相応する装置における一部にする。上記装置における各構成モジュール、手段を、ソフトウェア、ファームウェア及びハードウェアまたはこれらの組み合わせの方式で構成するときに使用される具体的な手段または方式は、当業者に熟知されるものであるため、ここでくだくだと説明はしない。
【００７０】
一つの例示として、ソフトウェアまたはファームウェアで実現された場合に、記憶媒体またはネットワークから、専用なハードウェア構造を有するコンピュータ（例えば、図５に示す汎用コンピュータ５００）へ当該ソフトウェを構成するプログラムをインストールしてもよい。当該コンピュータは、各種のプログラムがインストールされた場合に、各種の機能などを実行することができる。
【００７１】
上記の本発明を実施するための形態に対する説明において、一実施形態で説明及び/又は図示された特徴は、相同または類似する方式で、一つまたは複数のほかの実施形態に使用されてもよく、他の実施形態における特徴と組み合わせ、又は他の実施形態中の特徴を置換してもよい。
【００７２】
用語「含む／有する」とは、本稿に使用されるときには、特徴、要素、ステップまたはコンポーネントの存在を意味しているが、一つまたは複数のほかの特徴、要素、ステップまたはコンポーネントの存在または付加を排除するものではない。
【００７３】
また、本発明の方法は明細書に説明した時間順に従って実行することに限定されない。他の時間順に従って、並行して又は互いに独立に実行してもよい。したがって、本明細書に説明した方法の実行順序は、本発明の技術範囲を限定しない。
【００７４】
本発明の具体的な実施形態に対する説明で本発明を開示したが、当業者が特許請求の範囲の精神及び範囲内で、各種の修正、改善又は同等なものを設計することができる。これらの修正、改善又は同等なものも本発明の保護範囲内にカーバされると考えられる。
【００７５】
上記の実施例を含む実施形態について、以下の付記も含まれている。
付記：
（付記１）
時系列から基準系列と類似するサブ時系列を抽出する方法であって、コンピュータが、
前記時系列及び前記基準系列を、それぞれ前記時系列及び前記基準系列の変化傾向を表す系列に変換し、
変換された時系列を複数のサブ時系列に分割し、
前記複数のサブ時系列のうちの各サブ時系列と変換された基準系列との間の編集距離を算出し、
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出することを特徴とする方法。
（付記２）
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ前または複数前の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ前または複数前の要素に対する変化を表す系列である、
付記１に記載の方法。
（付記３）
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ後または複数後の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ後または複数後の要素に対する変化を表す系列である、
付記１に記載の方法。
（付記４）
前記編集距離は、重み付け編集距離であり、以下の要求のうちの一つまたは複数のこと、即ち、
挿入操作について、異なる要素の挿入に対して異なる重みの付与が許可されること、
削除操作について、異なる要素の削除に対して異なる重みの付与が許可されること、及び／又は、
置換操作について、異なる要素ペアの置換に対して異なる重みの付与が許可されることを満たす、
付記１に記載の方法。
（付記５）
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出する処理は、
前記複数のサブ時系列から、所定の閾値より小さい編集距離を有する一つまたは複数のサブ時系列を、前記基準系列と類似するサブ時系列として抽出することを含む、付記１に記載の方法。
（付記６）
変換された時系列を複数のサブ時系列に分割する処理によって分割された各サブ時系列は所定の長さを有し、分割された各サブ時系列の先頭間の間隔は所定のステップ長さであり、前記所定の長さおよび前記所定のステップ長さは前記基準系列の長さと同じであっても異なっていてもよい、付記１乃至５のいずれか一項に記載の方法。
（付記７）
時系列から基準系列と類似するサブ時系列を抽出する装置であって、
前記時系列及び前記基準系列を、それぞれ前記時系列及び前記基準系列の変化傾向を表す系列に変換するように構成される系列変換手段と、
変換された時系列を複数のサブ時系列に分割するように構成されるサブ時系列分割手段と、
前記複数のサブ時系列のうちの各サブ時系列と変換された基準系列との間の編集距離を算出するように構成される編集距離算出手段と、
算出された編集距離に基づいて、前記複数のサブ時系列から前記基準系列と類似するサブ時系列を抽出するように構成される類似時系列抽出手段と、を含む装置。
（付記８）
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ前または複数前の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ前または複数前の要素に対する変化を表す系列である、
付記７に記載の装置。
（付記９）
前記時系列の変化傾向を表す系列は、前記時系列における現在要素の一つ後または複数後の要素に対する変化を表す系列であり、
前記基準系列の変化傾向を表す系列は、前記基準系列における現在要素の一つ後または複数後の要素に対する変化を表す系列である、
付記８に記載の装置。
（付記１０）
前記編集距離は重み付け編集距離であり、以下の要求のうちの一つまたは複数のこと、即ち、
挿入操作について、異なる要素の挿入に対して異なる重みの付与が許可されること、
削除操作について、異なる要素の削除に対して異なる重みの付与が許可されること、及び／又は、
置換操作について、異なる要素ペアの置換に対して異なる重みの付与が許可されることを満たす、付記７に記載の装置。
（付記１１）
前記類似サブ時系列抽出手段は、
前記複数のサブ時系列から、所定の閾値より小さい編集距離を有する一つまたは複数のサブ時系列を、前記基準系列と類似するサブ時系列として抽出するように構成される、付記７に記載の装置。
（付記１２）
前記サブ時系列分割手段は、前記分割を、分割された各サブ時系列が所定の長さを有し、分割された各サブ時系列の先頭間の間隔が所定のステップ長さとなるように行うよう構成されており、前記所定の長さおよび前記所定のステップ長さは前記基準系列の長さと同じであっても異なっていてもよい、付記７乃至１１のいずれか一項に記載の装置。
（付記１３）
コンピュータに、付記1乃至6のいずれか一項に記載の方法の手順を実行させるプログラム。
（付記１４）
コンピュータに、付記1乃至6のいずれか一項に記載の方法の手順を実行させるプログラムを記録したコンピュータ読み取り可能な記憶媒体。
【図１】
2013025805.tif 000007
【図２】
2013025805.tif 000008
【図３】
2013025805.tif 000009
【図４】
2013025805.tif 000010
【図５】
2013025805.tif 000011