(57)【要約】  本発明は、時系列データから生成した複数の部分時系列をクラスタリングすることで時系列データ中の特徴的なパターンを自動的に生成するにあたり、パターンが正弦波に類似した形状にならずに、特徴的なパターンを生成可能とする装置および方法を提供する。部分時系列を生成する手段２０１と、生成された部分時系列の位相を整列する手段２０２と、位相を整列した部分時系列をクラスタリングする手段２０３と、クラスタリングから得られるパターンを記憶する装置２０４と、記憶されたパターンを出力する装置２０５を備える。
2008102840.tif 000002
【特許請求の範囲】
【請求項１】
時系列データの部分時系列をクラスタリングすることで前記時系列データからパターンを自動的に生成する装置であって、
前記部分時系列の位相を整列する手段と、
位相を整列した前記部分時系列をクラスタリングする手段と、
を含む、ことを特徴とするパターン生成装置。
【請求項２】
入力装置より入力された時系列データから前記部分時系列を生成する手段と、
前記クラスタリングで得られたパターンを記憶する記憶装置と、
前記記憶装置に記憶されたパターンを出力する出力装置と、
をさらに含む、ことを特徴とする請求項１記載のパターン生成装置。
【請求項３】
前記部分時系列の位相を整列する手段が、
前記部分時系列を基底関数の展開による表現に変換し、
前記変換の結果得られた前記部分時系列の表現に関して、最も寄与の高い基底関数に応じて、前記基底関数をある基準に基づき、シフトし、
前記基底関数がシフトされた前記部分時系列の表現に対して、前記変換の逆変換を施すことで、位相を整列した前記部分時系列を導出する、ことを特徴とする請求項１記載のパターン生成装置。
【請求項４】
前記変換が、前記基底関数が三角関数よりなるフーリエ変換を含み、
前記部分時系列の位相を整列する手段は、
前記フーリエ変換の結果得られた、前記部分時系列の周波数領域での表現に関して、振幅の絶対値が最大の成分の位相に対応する値にて各成分の位相をシフトし、
前記各成分の位相がシフトされた前記部分時系列の周波数領域での表現に対して、逆フーリエ変換を施すことで、位相を整列した前記部分時系列を得る、ことを特徴とする請求項３記載のパターン生成装置。
【請求項５】
前記部分時系列の位相を整列する手段が、
前記部分時系列のスペクトル成分のうちパワーが最大の成分の位相に対応する値にて、前記部分時系列をシフトする、ことを特徴とする請求項１記載のパターン生成装置。
【請求項６】
時系列データの部分時系列をクラスタリングすることで前記時系列データからパターンを自動的に生成する方法であって、
前記部分時系列の位相を整列する工程と、
位相を整列した部分時系列をクラスタリングする工程と、
を含む、ことを特徴とするパターン生成方法。
【請求項７】
入力された時系列データから前記部分時系列を生成する工程と、
前記クラスタリングで得られたパターンを記憶装置に記憶する工程と、
前記記憶装置に記憶されたパターンを出力する工程と、
を含む、ことを特徴とする請求項６記載のパターン生成方法。
【請求項８】
前記部分時系列の位相を整列する工程が、
前記部分時系列を基底関数の展開による表現に変換する工程と、
前記変換の結果得られた前記部分時系列の表現に関して、最も寄与の高い基底関数に応じて、前記基底関数をある基準に基づき、シフトする工程と、
前記基底関数がシフトされた、前記部分時系列の表現に対して、前記変換の逆変換を施すことで、位相を整列した前記部分時系列を導出する工程と、
を含む、ことを特徴とする請求項６記載のパターン生成方法。
【請求項９】
前記変換は、前記基底関数が三角関数よりなるフーリエ変換を含み、
前記部分時系列の位相を整列する工程は、
前記フーリエ変換の結果得られた、前記部分時系列の周波数領域での表現に関して、振幅の絶対値が最大の成分の位相に対応する値にて各成分の位相をシフトし、
前記各成分の位相がシフトされた前記部分時系列の周波数領域での表現に対して、逆フーリエ変換を施すことで、位相を整列した前記部分時系列を得る、ことを特徴とする請求項８記載のパターン生成方法。
【請求項１０】
前記部分時系列の位相を整列する工程が、
前記部分時系列のスペクトル成分のうちパワーが最大の成分の位相に対応する値にて、前記部分時系列をシフトする、ことを特徴とする請求項６記載のパターン生成方法。
【請求項１１】
時系列データの部分時系列をクラスタリングすることで前記時系列データからパターンを自動的に生成するコンピュータに、
前記部分時系列の位相を整列する処理と、
位相を整列した部分時系列をクラスタリングする処理と、
を実行させるプログラム。
【請求項１２】
入力装置より入力された時系列データから前記部分時系列を生成する処理と、
前記クラスタリングで得られたパターンを記憶装置に記憶する処理と、
前記記憶装置に記憶されたパターンを出力装置に出力する処理と、
を前記コンピュータに実行させるプログラムをさらに含む、ことを特徴とする請求項１１記載のプログラム。
【請求項１３】
前記部分時系列の位相を整列する処理が、
前記部分時系列を基底関数の展開による表現に変換し、
前記変換の結果得られた前記部分時系列の表現に関して、最も寄与の高い基底関数に応じて、前記基底関数をある基準に基づき、シフトし、
前記基底関数がシフトされた、前記部分時系列の表現に対して、前記変換の逆変換を施すことで、位相を整列した前記部分時系列を導出する、ことを特徴とする請求項１１記載のプログラム。
【請求項１４】
前記変換が、前記基底関数が三角関数よりなるフーリエ変換を含み、
前記部分時系列の位相を整列する処理が、
前記フーリエ変換の結果得られた、前記部分時系列の周波数領域での表現に関して、振幅の絶対値が最大の成分の位相に対応する値にて各成分の位相をシフトし、
前記各成分の位相がシフトされた前記部分時系列の周波数領域での表現に対して、逆フーリエ変換を施すことで、位相を整列した前記部分時系列を得る、ことを特徴とする請求項１３記載のプログラム。
【請求項１５】
前記部分時系列の位相を整列する処理が、
前記部分時系列のスペクトル成分のうちパワーが最大の成分の位相に対応する値にて、前記部分時系列をシフトする、ことを特徴とする請求項１１記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の記載］
本発明は、日本国特許出願：特願２００７−０４１１２５号（２００７年２月２１日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、パターン生成方法及びパターン生成装置に関し、特に、データマイニング等に適用して好適とされる、時系列データに対するパターン生成方法及びパターン生成装置とプログラムに関する。
【背景技術】
【０００２】
時系列データの解析は、過去に周波数領域、時間領域からさまざまな解析方法が提案されてきたが、近年、データマイニングの観点から、特徴的なパターンをもって変動をする時系列データからパターンを抽出するための技術が必要とされている。【０００３】
時系列データからのパターン生成は、代表的には、元々の長さＷの時系列から長さｗ（ｗ＜＜Ｗ）の部分時系列（subsequent time-series）を複数生成し、その部分時系列をクラスタリングという処理で行われ、このような手順に従う時系列からのパターン生成方法やパターン生成装置が幾つか提案されている（例えば非特許文献１）。【０００４】
【非特許文献１】G. Das, K. I. Lin, H. Mannila, G. Renganathan, and P. Smyth. Rule discovery from time series. In Proceedings of the 4th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 16-22, 1998.
【非特許文献２】E. Keogh, J. Lin, and W. Truppel. Clustering of time series subsequences is meaningless: implications for previous and future research. In Proceedings of the 3rd IEEE International Conference on Data Mining, 2003.
【非特許文献３】T. Ide. Why does subsequence time-series clustering produce sine waves? In Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases(PKDD 06), 2006.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
以上の非特許文献１〜３の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。
非特許文献２に指摘されているように、特徴的なパターンをもって変動する時系列データに関して、部分時系列を複数生成し、その部分時系列をクラスタリングという処理によってパターンを生成した場合に、元の時系列に依存せずに生成されたパターンが正弦波とよく似た形状になる（これを正弦波効果（Sinusoid Effect）という）。【０００６】
その理由は、本質的にはこの現象が未解決問題のため、パターンが正弦波となることを本質的に防ぐ事ができないためである。【０００７】
非特許文献３では、ｋ平均クラスタリングがクラスタ中心間に直交制約を課すと、データハンケル行列の左特異ベクトルと一致することから、理論的に正弦波が出てくることを示しているが、その回避策に関しては言及されていない。【０００８】
本発明の目的は、部分時系列をクラスタリングすることで時系列データ中の特徴的なパターンを自動的に生成するにあたり、パターンが正弦波に類似した形状にならずに、特徴的なパターンを生成可能とする装置及び方法を提供することである。
【課題を解決するための手段】
【０００９】
本願で開示される発明は、前記課題を解決するため、概略以下の構成とされる。【００１０】
本発明に係るパターン生成装置は、時系列データの部分時系列をクラスタリングすることで前記時系列データから特徴的なパターンを自動的に生成する装置であって、前記部分時系列の位相を整列する手段と、位相を整列した前記部分時系列をクラスタリングする手段と、を含む。【００１１】
本発明に係るパターン生成装置においては、入力装置より入力された時系列データから前記部分時系列を生成する手段と、前記クラスタリングで得られたパターンを記憶する記憶装置と、前記記憶装置に記憶されたパターンを出力する出力装置と、をさらに備えた構成としてもよい。【００１２】
本発明に係るパターン生成方法は、時系列データの部分時系列をクラスタリングすることで前記時系列データから特徴的なパターンを自動的に生成するにあたり、前記部分時系列の位相を整列する工程と、位相を整列した部分時系列をクラスタリングする工程と、を含む。【００１３】
本発明に係るコンピュータ・プログラムは、時系列データの部分時系列をクラスタリングすることで前記時系列データから特徴的なパターンを自動的に生成するコンピュータに、前記部分時系列の位相を整列する処理と、位相を整列した部分時系列をクラスタリングする処理と、を実行させるプログラムよりなる。【００１４】
本発明において、前記部分時系列の位相を整列するにあたり、前記部分時系列を基底関数の展開による表現に変換し、前記変換の結果得られた前記部分時系列の表現に関して、最も寄与の高い基底関数に応じて、前記基底関数をある基準に基づき、シフトし、前記基底関数がシフトされた前記部分時系列の表現に対して、前記変換の逆変換を施すことで、位相を整列した前記部分時系列を導出する、ようにしてもよい。
【発明の効果】
【００１５】
本発明によれば、特徴的なパターンをもって変動をする時系列データから、自動的に特徴的なパターンを抽出することを可能としている。その理由は、以下の通りである。部分時系列をクラスタリングする際に、パターンが正弦波に類似した形状になる現象（正弦波効果）は、位相の異なる部分時系列の重ね合わせによる、スペクトルの変化に起因する。このため、本発明にしたがって、位相を整列してクラスタリングを行うことによって、パターンが正弦波に類似した形状とはならず（正弦波効果の回避を実現）、特徴的なパターンを生成することを可能としている、ためである。
【図面の簡単な説明】
【００１６】
【図１】本発明を一実施の形態の構成を示す図である。
【図２】本発明の一実施の形態の動作手順を説明するためのフローチャートである。
【符号の説明】
【００１７】
１００  入力装置
２００  パターン生成装置
２０１  部分時系列生成手段
２０２  位相整列手段
２０３  クラスタリング手段
２０４  記憶装置
２０５  出力装置
【発明を実施するための最良の形態】
【００１８】
次に、本発明の実施の形態について図面を参照して詳細に説明する。図１は、本発明の一実施の形態のパターン生成装置２００の構成を示す図である。パターン生成装置２００は、部分時系列生成手段２０１と、位相整列手段２０２と、クラスタリング手段２０３と、記憶装置２０４と、出力装置２０５を備えている。【００１９】
部分時系列生成手段２０１は、入力された時系列データから適当な長さの部分時系列を生成する。【００２０】
位相整列手段２０２は、部分時系列生成手段２０１で生成された部分時系列の位相を整列する。【００２１】
クラスタリング手段２０３は、位相整列手段２０２で位相を整列された部分時系列に対して、クラスタリングを行う。【００２２】
記憶装置２０４は、クラスタリング手段２０３で生成されたパターンを記憶する装置である。【００２３】
出力装置２０５は、記憶装置２０４に記憶されたパターンを出力する装置である。なお、図１のパターン生成装置２００における各手段（部分時系列生成手段２０１と、位相整列手段２０２と、クラスタリング手段２０３等）の処理・機能は、パターン生成装置２００を構成するコンピュータ上で実行されるプログラムによって実現してもよいことは勿論である。【００２４】
図２は、図１のパターン生成装置２００の動作手順を説明するためのフローチャートである。【００２５】
図１のパターン生成装置２００は以下のように動作する。【００２６】
まず、入力装置１００から時系列データを読み込む（ステップＳ２０１）。【００２７】
次に、入力された時系列データから、部分時系列生成手段２０１によって部分時系列を生成する（ステップＳ２０２）。【００２８】
これは、例えば固定長ｗの窓をスライド長ｓでスライドさせ、部分時系列を生成する、スライディングウィンドウ方式（固定サイズの滑走窓方式）や、入力時系列からランダムに長さｗの部分時系列をサンプリングする方式などを用いてもよい。【００２９】
次に、位相整列手段２０２によって生成された部分時系列の位相を整列する（ステップＳ２０３）。【００３０】
部分時系列の位相の整列方法は幾つか考えられるが、以下で具体的な一例を説明する。【００３１】
長さｗの部分時系列をｙ（ｔ）とすると、ｙ（ｔ）をフーリエ変換した時のフーリエ係数は式（１）で表される。
2008102840.tif 000003
【００３２】
ただし、Ｔ及びλはそれぞれ式（２）及び（３）で表される。
2008102840.tif 000004
2008102840.tif 000005
【００３３】
このとき、｜ｆｙ（λ）｜が最大となる周波数（スペクトルパワーが最大の周波数成分）を式（４）で表す。
2008102840.tif 000006
【００３４】
式（４）であらわされる周波数に関するフーリエ係数（フーリエ成分）は式（５）で与えられる。
2008102840.tif 000007
【００３５】
ここで、ｌｙ＊は、一般には整数にならないため、ｌｙ＊に最も近い整数をｌｙとする。【００３６】
次に、位相をｌｙだけずらしてから、フーリエ逆変換を行うことで位相を整列する。【００３７】
ｙ（ｔ）の位相を整列した部分時系列をｚ（ｔ）とすると、ｚ（ｔ）は式（６）で表される。
2008102840.tif 000008
【００３８】
フーリエ変換がＤＦＴ（離散フーリエ変換）の場合、上式（６）の右辺はｙ（ｔ＋ｌｙ）と表すことができる。すなわち、式（６）のｚ（ｔ）は、元の部分時系列ｙ（ｔ）をｌｙ個時計回りに循環シフト（circular shift）したものである。なお、本発明において、部分時系列に対する変換は、部分時系列を、正規直交基底関数（三角関数）の重ね合わせとして展開するフーリエ変換に限定されるものでなく、ウェーブレット変換等の任意の直交変換、あるいは、任意の線形変換等を適用してもよいことは勿論である。【００３９】
次に、位相を整列した部分時系列に対して、任意のクラスタリングアルゴリズムを適用する。例えばｋ平均クラスタリングや階層的クラスタリングなどがある。特に制限されないが、パターンは、例えばｋ平均クラスタリングや階層的クラスタリング等の場合、同一クラスタに含まれる部分時系列の重ね合わせとして表される（ステップＳ２０４）。【００４０】
次に、生成されたパターンを記憶装置２０４に記憶する（ステップＳ２０５）。【００４１】
次に、出力装置２０５は、記憶装置２０４に記憶されたパターンを出力する（ステップＳ２０６）。【００４２】
本発明の実施の形態において入力される時系列データは、特徴的なパターンを生成するという目的においては、応用分野への依存性はない。以下では、その幾つかの実施例に関して述べる。
【実施例】
【００４３】
まず、本発明の第１の実施例を説明する。本実施例では、株価や経済時系列データを入力装置１００から入力する。このデータをパターン生成装置２００に入力することによって、株価データの変動パターンなどを自動的に生成し、株価の変動の理解を補助することが可能である。【００４４】
本発明の第２の実施例を説明する。本実施例では、自動車のエンジン回転数や電流値など複数属性に関する時系列データを各々入力装置１００から入力する。このデータをそれぞれパターン生成装置２００に入力し、各時系列データの特徴的なパターンを生成する。【００４５】
複数属性にまたがるパターンの共起やパターン間の時間的関係を、人間またはデータマイニング技術によってルール化することが可能である。例えば、このルールによって自動車に関する複数属性のデータを監視し、自動車に起こる障害を診断することが可能である。【００４６】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2008102840.tif 000009
【図２】
2008102840.tif 000010
【国際調査報告】
2008102840.tif 000011
2008102840.tif 000012