知識を活用する情報システム装置
【課題】時系列データの分類を予測するための部分的な形状やその組み合わせを出力する機能を有することによって、ユーザの知識を使わずに動作し解析対象の時系列データに対して新たな知識発見が行える、汎用的な装置を提供することを目的とする。
【解決手段】装置は特徴パタン発見機能、分類ルール抽出機能、分類予測機能、そして特徴パタン改良機能の４つを持つ。特徴パタン発見機能によって分類ごとの特徴となる時系列データの形状を発見し、分類ルール抽出機能によってその特徴パタンを用いた分類ルールを抽出する。特徴パタン改良機能によって特徴パタンの形状を改良し、改良後のパタンを用いて品質の高い分類ルールを抽出する。このように抽出された分類ルールは、未分類のデータを入力することによって活用され、時系列データの分類を予測できる。
【解決手段】装置は特徴パタン発見機能、分類ルール抽出機能、分類予測機能、そして特徴パタン改良機能の４つを持つ。特徴パタン発見機能によって分類ごとの特徴となる時系列データの形状を発見し、分類ルール抽出機能によってその特徴パタンを用いた分類ルールを抽出する。特徴パタン改良機能によって特徴パタンの形状を改良し、改良後のパタンを用いて品質の高い分類ルールを抽出する。このように抽出された分類ルールは、未分類のデータを入力することによって活用され、時系列データの分類を予測できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は時系列データの分類を予測するための知識を自動的に発見し、蓄積、活用するための情報システムの装置に関する。
【背景技術】
【０００２】
データマイニングによってデータベース内の大量のデータから発見的な知識獲得が可能となった。本発明で扱う時系列データとは時間の経過にそって記録した数値データのシーケンスで、データマイニング技術を適用することで、新たな知識の発掘を目的としている。実社会においてこのような形式のデータは様々な分野で頻出し、これらを解析することで、突然の降水量の急増、大地震の発生、株価の暴落などの変動が予測できると考えられ、重要なテーマとなっている。
【０００３】
非特許文書１では時系列データからの効率的な頻出パタンの発見方法を提案しており、この手法は頻出パタンを特徴的なパタンとしている。しかし、単純に頻出パタンを抽出する手法は多くの解析者にとって既知であるか、どのようなデータにおいても共通的な形を抽出する場合が多く、興味深いパタンを発見できない場合が多い。本発明ではデータ間の違いを表すためのパタンの抽出を目指す。
【０００４】
非特許文書２では, 抽出すべき時系列データの部分的な形状をユーザが指定することによって解析を行う。ユーザの知識を用いることによって、解析者の興味に従ったパタンを抽出できるが、解析者の想像しない形状を獲得するためには多くの試行錯誤を要する。さらに、このように背景知識に依存した手法は知識のないユーザにとっては使いづらい手法といえる。
【０００５】
非特許文書３では株価データに対して、さまざまな株価データに付随する18種類の指標をクラスタリングすることによって決定木学習に使用する属性を抽出している。この手法で作られた決定木とトレーニングデータから、未来予測に有効なパタンを抽出できると考えられるが、この手法は株価の特徴に依存し、汎用的な解析手法といえない。また株価データと違い、気温や湿度のように多くの指標がない時系列データに対して適用できない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Agrawal, R. and Srikant, R.: Mining sequential patterns, in Data Engineering, 1995. Proceedings of the Eleventh International Conference on, pp. 3-14, IEEE (2002)
【非特許文献２】Haigh, K., Foslien, W., and Guralnik, V.: Visula Query Language: Finding patterns in and relationships among time series data, in Proceedings of the seventh Workshop on Mining Scientific and Engineering Datasets, Citeseer (2004)
【非特許文献３】Abe, H., Hirabayashi, S., Ohsaki, M., and Yamaguchi, T.: Evaluating a Trading Rule Mining Method based on Temporal Pattern Extraction, in The Third International Workshop on Mining Complex Data (MCD2007) In Conjunction with ECML/PKDD 2007, pp. 49-58 (2007)
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、上記従来技術の抱える問題に鑑みてなされたものである、時系列データの分類を予測するための部分的な形状やその組み合わせを出力する機能を有することによって、ユーザの知識を使わずに動作し解析対象の時系列データに対して新たな知識発見が行える、汎用的な装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
装置はまず時系列データから特徴パタンを発見する。時系列データに頻出する形状はそのデータを解析する際に重要であることは明白であるが、その一方で、複数の分類にわたって広く出現する形状はそれらを特定するためには役に立たない。本発明は時系列データの分類を目的として、分類間を特徴づけるパタン発見のためにTF*IDFを時系列データに対して適用する。
【０００９】
TF*IDFはテキストマイニングの分野で用いられており、その値は単語の重要度の統計的な計測値として評価される。1つの文書は単語の集合であり、データベースは文書の集合である。ある単語の重要度は1つの文書内で頻出するほど増加し、データベースでその単語が出現する文書数が多いほど減少する。通常、単語の出現頻度TFは文書tjでの単語wiの出現確率とする。特定の文書に出現する単語はすべての文書に出現する単語よりも重要度が高い。これを逆文書頻度といい、Nを文書数、nを単語wiが少なくとも1つ含まれている文書の個数とするとき、TF*IDFは下記の数式１で定義される。
【数１】
【００１０】
本発明はこのTF*IDFの概念を拡張して時系列データに適用する。１つの時系列データを１つの文書とみなし、時系列データ中の一部分を部分時系列データと呼び、１つの単語として考える。この時、単純に時系列データから得られる固定長の部分を抽出すればその総数はとても多くなるため、代表的な部分時系列データの形状を発見する必要がある。この目的のために、提案装置は抽出された部分時系列データに対してクラスタリングを行う。時系列データに対してクラスタリングを行うことについては議論の余地があるが、抽出された多くの部分時系列データからいくつかの代表的な部分時系列データ、またはそれを示す形状を発見できればどのような手法を用いてもよく、本発明の本質ではないため言及しない。
【００１１】
クラスタリングには、一般的な手法の１つであるk-meansを用いる。Mクラスタリングは与えられたデータセットに対して互いに素なM個のサブセット（クラスタ）に分ける事を目的として、クラスタリングの基準を最適化する。クラスタリングの基準は各データxと、xiを含むサブセットXiであるところのクラスタの中心（セントロイド）ciとの距離である。k個のセントロイドをc1, ..., ckとして、D(p,q)をデータpとqの距離を計算する関数としたとき、クラスタリングの基準Errは下記の数式２で定義される。
【数２】
【００１２】
距離関数D(p,q)として最も広く使われる手法はユークリッド距離かその拡張である。図１にユークリッド距離の計算を行うための２つの時系列データのポイントの対応例を示す。図１の（ａ）の通り、ユークリッド距離は、同じ長さの時系列データのペアにしか適用できないうえに、人間の直感に反する結果を生じてしまう場合がある。人間は時系列データの形を柔軟に認識できるのに対し、この方法では時間方向の対応が固定化されるためと考えられる。
【００１３】
Dynamic Time Warping（以降、DTW）では2つの時系列データのポイント間を柔軟に対応づけ、人間の直感にあう距離計算を行う。時系列データ間の最適な類似度を計算するために、横軸と縦軸を拡縮することによって累積距離を最小化することで適切に対応付ける。図１の（ｂ）にこの対応例を示す。
【００１４】
長さiとjを持つ2つの時系列データA、B間のDTW距離g(A,B)は下記の数式３で定義される。A(i-1)とB(j-1)はA(i)とB(j)の最後の値を取り除いたシーケンスである。数式３のqとrはシーケンスの拡縮に伴うコストであり、sは値の不一致によるコストである。類似しているペアは値が小さく、完全に一致する2つのシーケンスは0になる。
【数３】
【００１５】
分類ルールの抽出は特徴発見機能によって獲得された特徴パタンを用いて行われる。分類ルールの抽出には決定木学習を用いる。決定木学習は教師あり学習の一種で、トレーニングデータを入力することによって属性を枝とした木構造の意思決定モデルを作成する。図２の（ｃ）にトレーニングデータの例を示す。P1からP3は特徴発見機能で発見された特徴パタンである。S1からS4はデータベース中のサブシーケンスである。全てのサブシーケンスと各特徴パタンとの距離についてDTWを用いて計算して属性値とする。トレーニングデータの各インスタンスはクラスラベルに関連付けられている。これらの距離とクラスラベルの組による1つの表がトレーニングデータである。このトレーニングデータを用いて決定木学習を行った結果として、図２の（ｄ）に示すような知識を獲得できる。
【００１６】
決定木学習を行った後の装置に対して未分類の時系列データを入力すると、分類ルールに従ってその分類を予測する。予測は次の手順で行われる。
１．分類ルールに用いられているすべての特徴パタンとの距離についてDTWを用いて計算する。
２．分類ルールの根ノードを調査ノードとする。
３．調査ノードと未分類データとの比較をおこない、調査ノードで示された条件にしたがって次のノードに移動する。
４．移動先が枝の場合は現在のノードを調査ノードとして、３から繰り返し実行する。
５．葉の場合にはそのクラス値を出力する。
【００１７】
本装置は、発見された特徴パタンを改良することによってさらに高い品質の分類ルールを提供するための機能を有する。特徴パタンを改良する手法については山登り法などの探索手法やQ-learningなどの強化学習などのいくつかの手法が考えられるが、単純な探索や強化学習ではすぐに局所解に陥ってしまうためにこれを避ける必要がある。このため、本研究では遺伝的アルゴリズム（GA）を用いて改良を行う。GAは自然淘汰と遺伝という進化論のアイデアに基づいた発見的な探索アルゴリズムである。遺伝的アルゴリズムは多様で複雑な評価関数から近似解を求める場合に有効な方法で、最適化問題や探索問題などに適用されている。決定木の枝や葉を染色体として符号化して遺伝的操作である交差や突然変異を適用する手法があるが本発明は予測のための特徴的な時系列データの形状の発見も重要な目的である。従って、特徴パタンを改良することによって決定木の品質を高める手法を開発した。装置は最終的に、学習した決定木だけでなく、それに用いた改良後の特徴パタンもセットにして出力する。
【００１８】
特徴パタンを改良する機能の動作概要は次のようになる。
１．特徴抽出機能によって得られたパタンを、初期特徴パタンとする。
２．特徴パタンを用いて決定木を作成する。
３．作成した決定木を評価する。
４．停止条件を充たしていたら、作成した決定木とそれに用いた特徴パタンを出力する。
５．停止条件を充たしていなければ、GAを使って特徴パタンを改良する。
６．改良した特徴パタンをもとに２から処理を繰り返す。
【００１９】
GAを用いた特徴パタンの改良方法の説明は、まず特徴パタンとGAにおける染色体との対応について説明し、染色体の評価、交叉、そして突然変異について説明する。
【００２０】
1つの染色体が1つの特徴パタンに対応しており、染色体の操作は特徴パタンの操作と同等である。特徴パタンの数値を変化率に正規化した値のシーケンスを染色体とする。つまり、個体は実数値から構成される長さnのシーケンスC = (x1, … xn )となる。図３に1つの特徴パタンに対応する染色体の例を示す。扱う遺伝子は離散的な変数ではなく実数値であるため、単純な0と1のビット列を扱う手法ではなく、実数値GAによって遺伝子改良を行う。
【００２１】
染色体の評価値には、その染色体と対応する特徴パタンを用いたDTW距離によってトレーニングデータを分類した際の獲得情報量を用いる。獲得情報量Gain(X)は次の数式４と数式５で計算できる。ここで、Tは分割前の集合であり、ある分割によってn個の部分集合Ti（iは1より大きくn以下）個に分割されるものとする。info (S)は情報エントロピーと呼ばれる量で次の数式６で定義される。 Sは集合を示し、 freq(Cj,S)はクラスCjに属するSの要素数、kはクラス数である。
【数４】
【数５】
【数６】
【００２２】
選択ではルーレット選択を行う。この方法では適応度の高い染色体ほど選ばれる確率が大きくなるが、適応度の低い染色体でも次世代残される可能性があり、適応度が高い染色体だけが残ることによって局所解にとらわれやすくなるのを防ぐ。ルーレット選択は次の手順で行う。
１．各染色体の評価値を基にして、ルーレットのスケーリングを行う。
２．ルーレット選択によって選択した染色体を残す。
３．手順２を繰り返し、あらかじめ定めておいた数になるまで次世代に残す染色体を選択する。
【００２３】
実数値GAでは単純な交叉における限界として、図４のように2つの親X、Yの交叉による子X’、Y’が最適解Eに近づくとは限らないという問題があるため、本装置では平均交叉法を用いる。平均交叉法は、探索領域において2つの探索点の内分、外分となる点を生成する手法であり、2つの染色体ペアに対応する実数値ベクトルをX、Yとすると、それらの中心(X+Y)/2と、2つの外分点(3X-Y)/2および(-X+3Y)/2を生成し、それらのうち適応度の高い２つの染色体を選択する。交差点は二点交叉によって選択する。選択された2点の内部について、平均交叉法によって交叉を行う。図５に平均交叉法と二点交叉を組み合わせた交叉方法の概要を示す。
【００２４】
突然変異では摂動幅Mを定義し、染色体からランダムに選択した遺伝子xiを最大Mの値だけ増減させる。染色体の遺伝子数をn、変化する遺伝子をxi、xiの上限をa、下限をbとすると次のようにして突然変異を行う。
１．0以上n以下となるiを選択する。
２．正負の方向をそれぞれ0.5の確率で選択する。
３．正方向の時、上限をaとしてxiからxi + Mまで値をランダムに選択する。
４．負方向の時、下限をbとしてxi - Mからxiまでの値をランダムに選択する。
【発明の効果】
【００２５】
上述した通り、分類された時系列データの特徴パタンと、それを用いた分類ルール、または自動的に改良された特徴パタンとそれを用いた分類ルールを抽出するとともに、抽出した分類ルールを用いて未分類の時系列データの分類を予測する機能が提供される。
【図面の簡単な説明】
【００２６】
【図１】ユークリッド距離とDTW距離の違い。
【図２】トレーニングデータの例と抽出される決定木。
【図３】特徴パタンと染色体の対応例。
【図４】単純な交叉の問題。
【図５】二点交叉と平均交叉。
【図６】装置全体。
【図７】理想的な実験データ作成方法。
【図８】遺伝的アルゴリズムによるパタン改良の効果。
【発明を実施するための形態】
【００２７】
分類ごとの時系列データの形状とそれを用いたルールを抽出するという目的のために、実際に装置を作成して実現した。提案装置の効果について（１）特徴パタンに基づいた決定木生成は有効か？（２）有効な特徴パタンは抽出可能か？（３）改良機能はどの程度有効か？の3点について調査を行う。このために2種類の実験データを用いる。提案装置の想定する理想的なデータを人工的に作成することによって効果（１）を調査する。次に実際の医療データを用いて効果（２）、（３）について調査する。
【実施例】
【００２８】
図６は装置全体の概要を示す。1社の株価、1人の患者などを単位とした1つの時系列データは、クラス値に関連付けられて保存されている。まず各時系列データに対して、すべての部分時系列データのセットを固定長のスライドウィンドウによって収集する。収集された全ての部分時系列データを用いてクラスタリングを行う。次に、いくつかの代表シーケンスはTF*IDFによってフィルターされ、残ったシーケンスが特徴パタンとなる。各部分時系列データは特徴パタンとの距離を用いて表現される。これが決定木学習を使って特徴抽出する際のトレーニングデータとなる。
【００２９】
特徴パタン抽出の際には部分時系列データ抽出のスライドウィンドウのサイズは20、スライド量を5とする。このとき、データの末端のスライドウィンドウのサイズに満たないデータは切り捨てる。DTWでは水平コスト（時間軸のずれのコスト）を50.0、垂直コスト（計測値のずれ）のコストを値の差の絶対値とした。決定木学習にはC4.5を用いた。パタン改良の効果を調査するために、遺伝的アルゴリズムで100世代分の計算し、各世代における予測精度を求める。決定木の分類精度は10分割交差検定によって測定する。
【００３０】
まず、理想的な実験データの作成方法について説明する。まず優先度と未来状態と特徴パタンの組をあらかじめ5種類用意する。それらの特徴パタンと未来状態を設定していないランダムなパタン５種類をランダムに配置することで時系列データを作成する。図７に理想的な実験データの作成方法の概要を示す。作成した時系列データを20種類用意して実験を行う。停滞幅倍率は5%とした。
【００３１】
作成した時系列データから、単純に部分時系列データの各時刻の値を属性とした場合と、テストデータ作成に用いた特徴パタンを用いた場合と、ランダム生成した特徴パタンを用いた場合の3種類で決定木学習を行い比較する。
【００３２】
精度と分散、そして決定木サイズの実験結果を表１に示す。Simpleは、単純に部分時系列データの各時刻の値を属性とした決定木である。Known patternsは、テストデータ作成に用いた特徴パタンを属性とした決定木である。GA ＋ Known patternsは、テストデータ作成に用いた特徴パタンを属性としたあと遺伝的アルゴリズムによって改良した決定木である。Random patternsは、ランダム生成した特徴パタンを属性とした決定木である。GA ＋ Random patternsは、ランダム生成した特徴パタンを属性としたあと、遺伝的アルゴリズムによって改良した決定木である。特徴パタンを用いた手法では遺伝子の数を5、10、20と変えて測定する。表中の数値はすべて20種類のデータの平均値である。獲得した決定木の安定性を調べるために予測精度の分散も示す。
【表１】
【００３３】
表１から、SimpleとRandom patternsを比較するとそれほど予測精度に違いがなく、クラスタの詳細度が上がるごとに多少の精度向上があることが分かる。ただし、分散という点で従来手法よりもパタンを用いたほうが安定していることが分かる。また、Known patternsに関しては全ての設定で従来手法を上回る予測精度を得られた。こちらの実験でもクラスタの詳細度が上がるほど予測精度が上がることが分かる。
【００３４】
GAを行う前と後では予測精度が数ポイント向上しており、大きな効果ではないが少なからず予測精度を高める効果があることが分かる。以下の実際の医療データを用いた実施結果でGAについての詳細な考察を行うが、人工的に作られたデータでは特徴パタン抽出によって高い予測精度を獲得できたため、GAによる精度向上が伸び悩んだと考えられる。
【００３５】
提案した装置の有効性をさらに調査するために、実際の医療データを用いて実験を行った。使用するデータは千葉大学付属病院から提供されている慢性肝炎の検査データで、このデータは1982年から2001年までの20年間で771名についての検査の記録である。このデータから血小板の時系列データ（PLT）のみを用いて慢性肝炎のタイプを予測する。慢性肝炎のタイプにはＢ型とＣ型の2種類があるが、Ｃ型肝炎については治療のためにインターフェロンの投与が行われた患者データもあるため、予測するクラスは「Ｂ型肝炎」「Ｃ型肝炎インターフェロン投与無し」「Ｃ型肝炎インターフェロン投与有り」の3種類とした。
【００３６】
比較のために、従来手法としてC4.5、サポートベクタマシン（以下SVM）、ニューラルネットワーク（以下、NN）を用いてスライドウィンドウによって手に入れた部分時系列データの各時間を各属性値として使うことで分類予測を行う。これらの従来手法をダイレクトアプローチ（以下、DA）として標記する。提案手法では特徴抽出でのクラスタ数を10、20、30、40、50の5種類で実験する。表２に予測精度の結果を示す。
【表２】
【００３７】
特徴パタン抽出だけを用いた場合、クラスタ数を40以上に設定することですべての既存手法よりも高い分類精度が得られた。しかし、GAによるパタン改良後の分類精度をみるとすべてのクラスタ数の設定において、すべての既存手法よりも高い分類精度を獲得できることが分かる。これらのことから、GAによるパタン改良機能は初期の分類精度が低い問題に対して有効に働くと考えられる。
【００３８】
図８にGAによる世代ごとの分類精度の変化を示す。グラフで示す通り、5種類すべてのクラスタ数の設定が高い予測精度を得ていることがわかる。また、クラスタ数が低いほど最初の精度が悪いため、GAによる改良効果が高いと思われる。これらのことから、GAによる改良は、十分な特徴パタンの数を確保できずに精度が低くなる時ほど有効であり、最終的に安定して高い予測精度を出力する効果があるといえる。
【産業上の利用可能性】
【００３９】
本発明で対象としている時系列データは経済、医療、科学など、現在様々な分野で頻出する基礎的なデータであるため、幅広い分野において適用可能な技術である。
【符号の説明】
【００４０】
（ａ） ユークリッド距離のポイント対応例。
（ｂ） Dynamic Time Warpingのポイント対応例。
（ｃ） 特徴パタンを基にしたトレーニングデータの例。
（ｄ） 出力される決定木の例。
（ｅ） 変化率に正規化した特徴パタン。
（ｆ） 特徴パタンに対応する染色体。
（ｇ） 選択された２つの親染色体。
（ｈ） 交叉の結果作成された子染色体。
（ｉ） 優先度と未来状態を組にした特徴パタン。
（ｊ） 特徴パタンを基にして作成された理想的な実験データ。
【技術分野】
【０００１】
本発明は時系列データの分類を予測するための知識を自動的に発見し、蓄積、活用するための情報システムの装置に関する。
【背景技術】
【０００２】
データマイニングによってデータベース内の大量のデータから発見的な知識獲得が可能となった。本発明で扱う時系列データとは時間の経過にそって記録した数値データのシーケンスで、データマイニング技術を適用することで、新たな知識の発掘を目的としている。実社会においてこのような形式のデータは様々な分野で頻出し、これらを解析することで、突然の降水量の急増、大地震の発生、株価の暴落などの変動が予測できると考えられ、重要なテーマとなっている。
【０００３】
非特許文書１では時系列データからの効率的な頻出パタンの発見方法を提案しており、この手法は頻出パタンを特徴的なパタンとしている。しかし、単純に頻出パタンを抽出する手法は多くの解析者にとって既知であるか、どのようなデータにおいても共通的な形を抽出する場合が多く、興味深いパタンを発見できない場合が多い。本発明ではデータ間の違いを表すためのパタンの抽出を目指す。
【０００４】
非特許文書２では, 抽出すべき時系列データの部分的な形状をユーザが指定することによって解析を行う。ユーザの知識を用いることによって、解析者の興味に従ったパタンを抽出できるが、解析者の想像しない形状を獲得するためには多くの試行錯誤を要する。さらに、このように背景知識に依存した手法は知識のないユーザにとっては使いづらい手法といえる。
【０００５】
非特許文書３では株価データに対して、さまざまな株価データに付随する18種類の指標をクラスタリングすることによって決定木学習に使用する属性を抽出している。この手法で作られた決定木とトレーニングデータから、未来予測に有効なパタンを抽出できると考えられるが、この手法は株価の特徴に依存し、汎用的な解析手法といえない。また株価データと違い、気温や湿度のように多くの指標がない時系列データに対して適用できない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Agrawal, R. and Srikant, R.: Mining sequential patterns, in Data Engineering, 1995. Proceedings of the Eleventh International Conference on, pp. 3-14, IEEE (2002)
【非特許文献２】Haigh, K., Foslien, W., and Guralnik, V.: Visula Query Language: Finding patterns in and relationships among time series data, in Proceedings of the seventh Workshop on Mining Scientific and Engineering Datasets, Citeseer (2004)
【非特許文献３】Abe, H., Hirabayashi, S., Ohsaki, M., and Yamaguchi, T.: Evaluating a Trading Rule Mining Method based on Temporal Pattern Extraction, in The Third International Workshop on Mining Complex Data (MCD2007) In Conjunction with ECML/PKDD 2007, pp. 49-58 (2007)
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、上記従来技術の抱える問題に鑑みてなされたものである、時系列データの分類を予測するための部分的な形状やその組み合わせを出力する機能を有することによって、ユーザの知識を使わずに動作し解析対象の時系列データに対して新たな知識発見が行える、汎用的な装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
装置はまず時系列データから特徴パタンを発見する。時系列データに頻出する形状はそのデータを解析する際に重要であることは明白であるが、その一方で、複数の分類にわたって広く出現する形状はそれらを特定するためには役に立たない。本発明は時系列データの分類を目的として、分類間を特徴づけるパタン発見のためにTF*IDFを時系列データに対して適用する。
【０００９】
TF*IDFはテキストマイニングの分野で用いられており、その値は単語の重要度の統計的な計測値として評価される。1つの文書は単語の集合であり、データベースは文書の集合である。ある単語の重要度は1つの文書内で頻出するほど増加し、データベースでその単語が出現する文書数が多いほど減少する。通常、単語の出現頻度TFは文書tjでの単語wiの出現確率とする。特定の文書に出現する単語はすべての文書に出現する単語よりも重要度が高い。これを逆文書頻度といい、Nを文書数、nを単語wiが少なくとも1つ含まれている文書の個数とするとき、TF*IDFは下記の数式１で定義される。
【数１】
【００１０】
本発明はこのTF*IDFの概念を拡張して時系列データに適用する。１つの時系列データを１つの文書とみなし、時系列データ中の一部分を部分時系列データと呼び、１つの単語として考える。この時、単純に時系列データから得られる固定長の部分を抽出すればその総数はとても多くなるため、代表的な部分時系列データの形状を発見する必要がある。この目的のために、提案装置は抽出された部分時系列データに対してクラスタリングを行う。時系列データに対してクラスタリングを行うことについては議論の余地があるが、抽出された多くの部分時系列データからいくつかの代表的な部分時系列データ、またはそれを示す形状を発見できればどのような手法を用いてもよく、本発明の本質ではないため言及しない。
【００１１】
クラスタリングには、一般的な手法の１つであるk-meansを用いる。Mクラスタリングは与えられたデータセットに対して互いに素なM個のサブセット（クラスタ）に分ける事を目的として、クラスタリングの基準を最適化する。クラスタリングの基準は各データxと、xiを含むサブセットXiであるところのクラスタの中心（セントロイド）ciとの距離である。k個のセントロイドをc1, ..., ckとして、D(p,q)をデータpとqの距離を計算する関数としたとき、クラスタリングの基準Errは下記の数式２で定義される。
【数２】
【００１２】
距離関数D(p,q)として最も広く使われる手法はユークリッド距離かその拡張である。図１にユークリッド距離の計算を行うための２つの時系列データのポイントの対応例を示す。図１の（ａ）の通り、ユークリッド距離は、同じ長さの時系列データのペアにしか適用できないうえに、人間の直感に反する結果を生じてしまう場合がある。人間は時系列データの形を柔軟に認識できるのに対し、この方法では時間方向の対応が固定化されるためと考えられる。
【００１３】
Dynamic Time Warping（以降、DTW）では2つの時系列データのポイント間を柔軟に対応づけ、人間の直感にあう距離計算を行う。時系列データ間の最適な類似度を計算するために、横軸と縦軸を拡縮することによって累積距離を最小化することで適切に対応付ける。図１の（ｂ）にこの対応例を示す。
【００１４】
長さiとjを持つ2つの時系列データA、B間のDTW距離g(A,B)は下記の数式３で定義される。A(i-1)とB(j-1)はA(i)とB(j)の最後の値を取り除いたシーケンスである。数式３のqとrはシーケンスの拡縮に伴うコストであり、sは値の不一致によるコストである。類似しているペアは値が小さく、完全に一致する2つのシーケンスは0になる。
【数３】
【００１５】
分類ルールの抽出は特徴発見機能によって獲得された特徴パタンを用いて行われる。分類ルールの抽出には決定木学習を用いる。決定木学習は教師あり学習の一種で、トレーニングデータを入力することによって属性を枝とした木構造の意思決定モデルを作成する。図２の（ｃ）にトレーニングデータの例を示す。P1からP3は特徴発見機能で発見された特徴パタンである。S1からS4はデータベース中のサブシーケンスである。全てのサブシーケンスと各特徴パタンとの距離についてDTWを用いて計算して属性値とする。トレーニングデータの各インスタンスはクラスラベルに関連付けられている。これらの距離とクラスラベルの組による1つの表がトレーニングデータである。このトレーニングデータを用いて決定木学習を行った結果として、図２の（ｄ）に示すような知識を獲得できる。
【００１６】
決定木学習を行った後の装置に対して未分類の時系列データを入力すると、分類ルールに従ってその分類を予測する。予測は次の手順で行われる。
１．分類ルールに用いられているすべての特徴パタンとの距離についてDTWを用いて計算する。
２．分類ルールの根ノードを調査ノードとする。
３．調査ノードと未分類データとの比較をおこない、調査ノードで示された条件にしたがって次のノードに移動する。
４．移動先が枝の場合は現在のノードを調査ノードとして、３から繰り返し実行する。
５．葉の場合にはそのクラス値を出力する。
【００１７】
本装置は、発見された特徴パタンを改良することによってさらに高い品質の分類ルールを提供するための機能を有する。特徴パタンを改良する手法については山登り法などの探索手法やQ-learningなどの強化学習などのいくつかの手法が考えられるが、単純な探索や強化学習ではすぐに局所解に陥ってしまうためにこれを避ける必要がある。このため、本研究では遺伝的アルゴリズム（GA）を用いて改良を行う。GAは自然淘汰と遺伝という進化論のアイデアに基づいた発見的な探索アルゴリズムである。遺伝的アルゴリズムは多様で複雑な評価関数から近似解を求める場合に有効な方法で、最適化問題や探索問題などに適用されている。決定木の枝や葉を染色体として符号化して遺伝的操作である交差や突然変異を適用する手法があるが本発明は予測のための特徴的な時系列データの形状の発見も重要な目的である。従って、特徴パタンを改良することによって決定木の品質を高める手法を開発した。装置は最終的に、学習した決定木だけでなく、それに用いた改良後の特徴パタンもセットにして出力する。
【００１８】
特徴パタンを改良する機能の動作概要は次のようになる。
１．特徴抽出機能によって得られたパタンを、初期特徴パタンとする。
２．特徴パタンを用いて決定木を作成する。
３．作成した決定木を評価する。
４．停止条件を充たしていたら、作成した決定木とそれに用いた特徴パタンを出力する。
５．停止条件を充たしていなければ、GAを使って特徴パタンを改良する。
６．改良した特徴パタンをもとに２から処理を繰り返す。
【００１９】
GAを用いた特徴パタンの改良方法の説明は、まず特徴パタンとGAにおける染色体との対応について説明し、染色体の評価、交叉、そして突然変異について説明する。
【００２０】
1つの染色体が1つの特徴パタンに対応しており、染色体の操作は特徴パタンの操作と同等である。特徴パタンの数値を変化率に正規化した値のシーケンスを染色体とする。つまり、個体は実数値から構成される長さnのシーケンスC = (x1, … xn )となる。図３に1つの特徴パタンに対応する染色体の例を示す。扱う遺伝子は離散的な変数ではなく実数値であるため、単純な0と1のビット列を扱う手法ではなく、実数値GAによって遺伝子改良を行う。
【００２１】
染色体の評価値には、その染色体と対応する特徴パタンを用いたDTW距離によってトレーニングデータを分類した際の獲得情報量を用いる。獲得情報量Gain(X)は次の数式４と数式５で計算できる。ここで、Tは分割前の集合であり、ある分割によってn個の部分集合Ti（iは1より大きくn以下）個に分割されるものとする。info (S)は情報エントロピーと呼ばれる量で次の数式６で定義される。 Sは集合を示し、 freq(Cj,S)はクラスCjに属するSの要素数、kはクラス数である。
【数４】
【数５】
【数６】
【００２２】
選択ではルーレット選択を行う。この方法では適応度の高い染色体ほど選ばれる確率が大きくなるが、適応度の低い染色体でも次世代残される可能性があり、適応度が高い染色体だけが残ることによって局所解にとらわれやすくなるのを防ぐ。ルーレット選択は次の手順で行う。
１．各染色体の評価値を基にして、ルーレットのスケーリングを行う。
２．ルーレット選択によって選択した染色体を残す。
３．手順２を繰り返し、あらかじめ定めておいた数になるまで次世代に残す染色体を選択する。
【００２３】
実数値GAでは単純な交叉における限界として、図４のように2つの親X、Yの交叉による子X’、Y’が最適解Eに近づくとは限らないという問題があるため、本装置では平均交叉法を用いる。平均交叉法は、探索領域において2つの探索点の内分、外分となる点を生成する手法であり、2つの染色体ペアに対応する実数値ベクトルをX、Yとすると、それらの中心(X+Y)/2と、2つの外分点(3X-Y)/2および(-X+3Y)/2を生成し、それらのうち適応度の高い２つの染色体を選択する。交差点は二点交叉によって選択する。選択された2点の内部について、平均交叉法によって交叉を行う。図５に平均交叉法と二点交叉を組み合わせた交叉方法の概要を示す。
【００２４】
突然変異では摂動幅Mを定義し、染色体からランダムに選択した遺伝子xiを最大Mの値だけ増減させる。染色体の遺伝子数をn、変化する遺伝子をxi、xiの上限をa、下限をbとすると次のようにして突然変異を行う。
１．0以上n以下となるiを選択する。
２．正負の方向をそれぞれ0.5の確率で選択する。
３．正方向の時、上限をaとしてxiからxi + Mまで値をランダムに選択する。
４．負方向の時、下限をbとしてxi - Mからxiまでの値をランダムに選択する。
【発明の効果】
【００２５】
上述した通り、分類された時系列データの特徴パタンと、それを用いた分類ルール、または自動的に改良された特徴パタンとそれを用いた分類ルールを抽出するとともに、抽出した分類ルールを用いて未分類の時系列データの分類を予測する機能が提供される。
【図面の簡単な説明】
【００２６】
【図１】ユークリッド距離とDTW距離の違い。
【図２】トレーニングデータの例と抽出される決定木。
【図３】特徴パタンと染色体の対応例。
【図４】単純な交叉の問題。
【図５】二点交叉と平均交叉。
【図６】装置全体。
【図７】理想的な実験データ作成方法。
【図８】遺伝的アルゴリズムによるパタン改良の効果。
【発明を実施するための形態】
【００２７】
分類ごとの時系列データの形状とそれを用いたルールを抽出するという目的のために、実際に装置を作成して実現した。提案装置の効果について（１）特徴パタンに基づいた決定木生成は有効か？（２）有効な特徴パタンは抽出可能か？（３）改良機能はどの程度有効か？の3点について調査を行う。このために2種類の実験データを用いる。提案装置の想定する理想的なデータを人工的に作成することによって効果（１）を調査する。次に実際の医療データを用いて効果（２）、（３）について調査する。
【実施例】
【００２８】
図６は装置全体の概要を示す。1社の株価、1人の患者などを単位とした1つの時系列データは、クラス値に関連付けられて保存されている。まず各時系列データに対して、すべての部分時系列データのセットを固定長のスライドウィンドウによって収集する。収集された全ての部分時系列データを用いてクラスタリングを行う。次に、いくつかの代表シーケンスはTF*IDFによってフィルターされ、残ったシーケンスが特徴パタンとなる。各部分時系列データは特徴パタンとの距離を用いて表現される。これが決定木学習を使って特徴抽出する際のトレーニングデータとなる。
【００２９】
特徴パタン抽出の際には部分時系列データ抽出のスライドウィンドウのサイズは20、スライド量を5とする。このとき、データの末端のスライドウィンドウのサイズに満たないデータは切り捨てる。DTWでは水平コスト（時間軸のずれのコスト）を50.0、垂直コスト（計測値のずれ）のコストを値の差の絶対値とした。決定木学習にはC4.5を用いた。パタン改良の効果を調査するために、遺伝的アルゴリズムで100世代分の計算し、各世代における予測精度を求める。決定木の分類精度は10分割交差検定によって測定する。
【００３０】
まず、理想的な実験データの作成方法について説明する。まず優先度と未来状態と特徴パタンの組をあらかじめ5種類用意する。それらの特徴パタンと未来状態を設定していないランダムなパタン５種類をランダムに配置することで時系列データを作成する。図７に理想的な実験データの作成方法の概要を示す。作成した時系列データを20種類用意して実験を行う。停滞幅倍率は5%とした。
【００３１】
作成した時系列データから、単純に部分時系列データの各時刻の値を属性とした場合と、テストデータ作成に用いた特徴パタンを用いた場合と、ランダム生成した特徴パタンを用いた場合の3種類で決定木学習を行い比較する。
【００３２】
精度と分散、そして決定木サイズの実験結果を表１に示す。Simpleは、単純に部分時系列データの各時刻の値を属性とした決定木である。Known patternsは、テストデータ作成に用いた特徴パタンを属性とした決定木である。GA ＋ Known patternsは、テストデータ作成に用いた特徴パタンを属性としたあと遺伝的アルゴリズムによって改良した決定木である。Random patternsは、ランダム生成した特徴パタンを属性とした決定木である。GA ＋ Random patternsは、ランダム生成した特徴パタンを属性としたあと、遺伝的アルゴリズムによって改良した決定木である。特徴パタンを用いた手法では遺伝子の数を5、10、20と変えて測定する。表中の数値はすべて20種類のデータの平均値である。獲得した決定木の安定性を調べるために予測精度の分散も示す。
【表１】
【００３３】
表１から、SimpleとRandom patternsを比較するとそれほど予測精度に違いがなく、クラスタの詳細度が上がるごとに多少の精度向上があることが分かる。ただし、分散という点で従来手法よりもパタンを用いたほうが安定していることが分かる。また、Known patternsに関しては全ての設定で従来手法を上回る予測精度を得られた。こちらの実験でもクラスタの詳細度が上がるほど予測精度が上がることが分かる。
【００３４】
GAを行う前と後では予測精度が数ポイント向上しており、大きな効果ではないが少なからず予測精度を高める効果があることが分かる。以下の実際の医療データを用いた実施結果でGAについての詳細な考察を行うが、人工的に作られたデータでは特徴パタン抽出によって高い予測精度を獲得できたため、GAによる精度向上が伸び悩んだと考えられる。
【００３５】
提案した装置の有効性をさらに調査するために、実際の医療データを用いて実験を行った。使用するデータは千葉大学付属病院から提供されている慢性肝炎の検査データで、このデータは1982年から2001年までの20年間で771名についての検査の記録である。このデータから血小板の時系列データ（PLT）のみを用いて慢性肝炎のタイプを予測する。慢性肝炎のタイプにはＢ型とＣ型の2種類があるが、Ｃ型肝炎については治療のためにインターフェロンの投与が行われた患者データもあるため、予測するクラスは「Ｂ型肝炎」「Ｃ型肝炎インターフェロン投与無し」「Ｃ型肝炎インターフェロン投与有り」の3種類とした。
【００３６】
比較のために、従来手法としてC4.5、サポートベクタマシン（以下SVM）、ニューラルネットワーク（以下、NN）を用いてスライドウィンドウによって手に入れた部分時系列データの各時間を各属性値として使うことで分類予測を行う。これらの従来手法をダイレクトアプローチ（以下、DA）として標記する。提案手法では特徴抽出でのクラスタ数を10、20、30、40、50の5種類で実験する。表２に予測精度の結果を示す。
【表２】
【００３７】
特徴パタン抽出だけを用いた場合、クラスタ数を40以上に設定することですべての既存手法よりも高い分類精度が得られた。しかし、GAによるパタン改良後の分類精度をみるとすべてのクラスタ数の設定において、すべての既存手法よりも高い分類精度を獲得できることが分かる。これらのことから、GAによるパタン改良機能は初期の分類精度が低い問題に対して有効に働くと考えられる。
【００３８】
図８にGAによる世代ごとの分類精度の変化を示す。グラフで示す通り、5種類すべてのクラスタ数の設定が高い予測精度を得ていることがわかる。また、クラスタ数が低いほど最初の精度が悪いため、GAによる改良効果が高いと思われる。これらのことから、GAによる改良は、十分な特徴パタンの数を確保できずに精度が低くなる時ほど有効であり、最終的に安定して高い予測精度を出力する効果があるといえる。
【産業上の利用可能性】
【００３９】
本発明で対象としている時系列データは経済、医療、科学など、現在様々な分野で頻出する基礎的なデータであるため、幅広い分野において適用可能な技術である。
【符号の説明】
【００４０】
（ａ） ユークリッド距離のポイント対応例。
（ｂ） Dynamic Time Warpingのポイント対応例。
（ｃ） 特徴パタンを基にしたトレーニングデータの例。
（ｄ） 出力される決定木の例。
（ｅ） 変化率に正規化した特徴パタン。
（ｆ） 特徴パタンに対応する染色体。
（ｇ） 選択された２つの親染色体。
（ｈ） 交叉の結果作成された子染色体。
（ｉ） 優先度と未来状態を組にした特徴パタン。
（ｊ） 特徴パタンを基にして作成された理想的な実験データ。
【特許請求の範囲】
【請求項１】
ある概念によって分類された時系列データを区別することのできる時系列データベースから、それぞれの時系列データの分類を特徴づける時系列データの部分区間の変化を、特徴パタンとして抽出する装置。
【請求項２】
請求項１で抽出された特徴パタンを基にして、未分類の時系列データを適切な概念グループに分類するための分類ルールを抽出する機能をもつ請求項１の装置。
【請求項３】
請求項２で抽出された分類ルールに従って、実際に未分類の時系列データを適切な概念グループに分類する請求項２の装置。
【請求項４】
請求項１で抽出した特徴パタンを自動的に改良することで、請求項２で抽出される分類ルールの分類精度を向上させる機能を持つ請求項２の装置。
【請求項１】
ある概念によって分類された時系列データを区別することのできる時系列データベースから、それぞれの時系列データの分類を特徴づける時系列データの部分区間の変化を、特徴パタンとして抽出する装置。
【請求項２】
請求項１で抽出された特徴パタンを基にして、未分類の時系列データを適切な概念グループに分類するための分類ルールを抽出する機能をもつ請求項１の装置。
【請求項３】
請求項２で抽出された分類ルールに従って、実際に未分類の時系列データを適切な概念グループに分類する請求項２の装置。
【請求項４】
請求項１で抽出した特徴パタンを自動的に改良することで、請求項２で抽出される分類ルールの分類精度を向上させる機能を持つ請求項２の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−７７１９４（Ｐ２０１３−７７１９４Ａ）
【公開日】平成２５年４月２５日（２０１３．４．２５）
【国際特許分類】
【出願番号】特願２０１１−２１７１８３（Ｐ２０１１−２１７１８３）
【出願日】平成２３年９月３０日（２０１１．９．３０）
【出願人】（７１１０１０２４２）
【公開日】平成２５年４月２５日（２０１３．４．２５）
【国際特許分類】
【出願日】平成２３年９月３０日（２０１１．９．３０）
【出願人】（７１１０１０２４２）
[ Back to top ]