ある概念によって分類された時系列データを区別することのできる時系列データベースから、それぞれの時系列データの分類を特徴づける時系列データの部分区間の変化を、特徴パタンとして抽出する装置。請求項1で抽出された特徴パタンを基にして、未分類の時系列データを適切な概念グループに分類するための分類ルールを抽出する機能をもつ請求項1の装置。請求項2で抽出された分類ルールに従って、実際に未分類の時系列データを適切な概念グループに分類する請求項2の装置。請求項1で抽出した特徴パタンを自動的に改良することで、請求項2で抽出される分類ルールの分類精度を向上させる機能を持つ請求項2の装置。本発明は、上記従来技術の抱える問題に鑑みてなされたものである、時系列データの分類を予測するための部分的な形状やその組み合わせを出力する機能を有することによって、ユーザの知識を使わずに動作し解析対象の時系列データに対して新たな知識発見が行える、汎用的な装置を提供することを目的とする。装置はまず時系列データから特徴パタンを発見する。時系列データに頻出する形状はそのデータを解析する際に重要であることは明白であるが、その一方で、複数の分類にわたって広く出現する形状はそれらを特定するためには役に立たない。本発明は時系列データの分類を目的として、分類間を特徴づけるパタン発見のためにTFIDFを時系列データに対して適用する。TFIDFはテキストマイニングの分野で用いられており、その値は単語の重要度の統計的な計測値として評価される。1つの文書は単語の集合であり、データベースは文書の集合である。ある単語の重要度は1つの文書内で頻出するほど増加し、データベースでその単語が出現する文書数が多いほど減少する。通常、単語の出現頻度TFは文書tjでの単語wiの出現確率とする。特定の文書に出現する単語はすべての文書に出現する単語よりも重要度が高い。これを逆文書頻度といい、Nを文書数、nを単語wiが少なくとも1つ含まれている文書の個数とするとき、TFIDFは下記の数式1で定義される。本発明はこのTFIDFの概念を拡張して時系列データに適用する。1つの時系列データを1つの文書とみなし、時系列データ中の一部分を部分時系列データと呼び、1つの単語として考える。この時、単純に時系列データから得られる固定長の部分を抽出すればその総数はとても多くなるため、代表的な部分時系列データの形状を発見する必要がある。この目的のために、提案装置は抽出された部分時系列データに対してクラスタリングを行う。時系列データに対してクラスタリングを行うことについては議論の余地があるが、抽出された多くの部分時系列データからいくつかの代表的な部分時系列データ、またはそれを示す形状を発見できればどのような手法を用いてもよく、本発明の本質ではないため言及しない。クラスタリングには、一般的な手法の1つであるkmeansを用いる。Mクラスタリングは与えられたデータセットに対して互いに素なM個のサブセットクラスタに分ける事を目的として、クラスタリングの基準を最適化する。クラスタリングの基準は各データxと、xiを含むサブセットXiであるところのクラスタの中心セントロイドciとの距離である。k個のセントロイドをc1ckとして、Dをデータpとqの距離を計算する関数としたとき、クラスタリングの基準Errは下記の数式2で定義される。距離関数Dとして最も広く使われる手法はユークリッド距離かその拡張である。図1にユークリッド距離の計算を行うための2つの時系列データのポイントの対応例を示す。図1のaの通り、ユークリッド距離は、同じ長さの時系列データのペアにしか適用できないうえに、人間の直感に反する結果を生じてしまう場合がある。人間は時系列データの形を柔軟に認識できるのに対し、この方法では時間方向の対応が固定化されるためと考えられる。DynamicTimeWarping以降、DTWでは2つの時系列データのポイント間を柔軟に対応づけ、人間の直感にあう距離計算を行う。時系列データ間の最適な類似度を計算するために、横軸と縦軸を拡縮することによって累積距離を最小化することで適切に対応付ける。図1のbにこの対応例を示す。長さiとjを持つ2つの時系列データA、B間のDTW距離gは下記の数式3で定義される。AとBはAとBの最後の値を取り除いたシーケンスである。数式3のqとrはシーケンスの拡縮に伴うコストであり、sは値の不一致によるコストである。類似しているペアは値が小さく、完全に一致する2つのシーケンスは0になる。分類ルールの抽出は特徴発見機能によって獲得された特徴パタンを用いて行われる。分類ルールの抽出には決定木学習を用いる。決定木学習は教師あり学習の一種で、トレーニングデータを入力することによって属性を枝とした木構造の意思決定モデルを作成する。図2のcにトレーニングデータの例を示す。P1からP3は特徴発見機能で発見された特徴パタンである。S1からS4はデータベース中のサブシーケンスである。全てのサブシーケンスと各特徴パタンとの距離についてDTWを用いて計算して属性値とする。トレーニングデータの各インスタンスはクラスラベルに関連付けられている。これらの距離とクラスラベルの組による1つの表がトレーニングデータである。このトレーニングデータを用いて決定木学習を行った結果として、図2のdに示すような知識を獲得できる。決定木学習を行った後の装置に対して未分類の時系列データを入力すると、分類ルールに従ってその分類を予測する。予測は次の手順で行われる。1.分類ルールに用いられているすべての特徴パタンとの距離についてDTWを用いて計算する。2.分類ルールの根ノードを調査ノードとする。3.調査ノードと未分類データとの比較をおこない、調査ノードで示された条件にしたがって次のノードに移動する。4.移動先が枝の場合は現在のノードを調査ノードとして、3から繰り返し実行する。5.葉の場合にはそのクラス値を出力する。本装置は、発見された特徴パタンを改良することによってさらに高い品質の分類ルールを提供するための機能を有する。特徴パタンを改良する手法については山登り法などの探索手法やQlearningなどの強化学習などのいくつかの手法が考えられるが、単純な探索や強化学習ではすぐに局所解に陥ってしまうためにこれを避ける必要がある。このため、本研究では遺伝的アルゴリズムGAを用いて改良を行う。GAは自然淘汰と遺伝という進化論のアイデアに基づいた発見的な探索アルゴリズムである。遺伝的アルゴリズムは多様で複雑な評価関数から近似解を求める場合に有効な方法で、最適化問題や探索問題などに適用されている。決定木の枝や葉を染色体として符号化して遺伝的操作である交差や突然変異を適用する手法があるが本発明は予測のための特徴的な時系列データの形状の発見も重要な目的である。従って、特徴パタンを改良することによって決定木の品質を高める手法を開発した。装置は最終的に、学習した決定木だけでなく、それに用いた改良後の特徴パタンもセットにして出力する。特徴パタンを改良する機能の動作概要は次のようになる。1.特徴抽出機能によって得られたパタンを、初期特徴パタンとする。2.特徴パタンを用いて決定木を作成する。3.作成した決定木を評価する。4.停止条件を充たしていたら、作成した決定木とそれに用いた特徴パタンを出力する。5.停止条件を充たしていなければ、GAを使って特徴パタンを改良する。6.改良した特徴パタンをもとに2から処理を繰り返す。GAを用いた特徴パタンの改良方法の説明は、まず特徴パタンとGAにおける染色体との対応について説明し、染色体の評価、交叉、そして突然変異について説明する。1つの染色体が1つの特徴パタンに対応しており、染色体の操作は特徴パタンの操作と同等である。特徴パタンの数値を変化率に正規化した値のシーケンスを染色体とする。つまり、個体は実数値から構成される長さnのシーケンスCとなる。図3に1つの特徴パタンに対応する染色体の例を示す。扱う遺伝子は離散的な変数ではなく実数値であるため、単純な0と1のビット列を扱う手法ではなく、実数値GAによって遺伝子改良を行う。染色体の評価値には、その染色体と対応する特徴パタンを用いたDTW距離によってトレーニングデータを分類した際の獲得情報量を用いる。獲得情報量Gainは次の数式4と数式5で計算できる。ここで、Tは分割前の集合であり、ある分割によってn個の部分集合Tiiは1より大きくn以下個に分割されるものとする。infoは情報エントロピーと呼ばれる量で次の数式6で定義される。Sは集合を示し、freqはクラスCjに属するSの要素数、kはクラス数である。選択ではルーレット選択を行う。この方法では適応度の高い染色体ほど選ばれる確率が大きくなるが、適応度の低い染色体でも次世代残される可能性があり、適応度が高い染色体だけが残ることによって局所解にとらわれやすくなるのを防ぐ。ルーレット選択は次の手順で行う。1.各染色体の評価値を基にして、ルーレットのスケーリングを行う。2.ルーレット選択によって選択した染色体を残す。3.手順2を繰り返し、あらかじめ定めておいた数になるまで次世代に残す染色体を選択する。実数値GAでは単純な交叉における限界として、図4のように2つの親X、Yの交叉による子X’、Y’が最適解Eに近づくとは限らないという問題があるため、本装置では平均交叉法を用いる。平均交叉法は、探索領域において2つの探索点の内分、外分となる点を生成する手法であり、2つの染色体ペアに対応する実数値ベクトルをX、Yとすると、それらの中心2と、2つの外分点2および2を生成し、それらのうち適応度の高い2つの染色体を選択する。交差点は二点交叉によって選択する。選択された2点の内部について、平均交叉法によって交叉を行う。図5に平均交叉法と二点交叉を組み合わせた交叉方法の概要を示す。突然変異では摂動幅Mを定義し、染色体からランダムに選択した遺伝子xiを最大Mの値だけ増減させる。染色体の遺伝子数をn、変化する遺伝子をxi、xiの上限をa、下限をbとすると次のようにして突然変異を行う。1.0以上n以下となるiを選択する。2.正負の方向をそれぞれ05の確率で選択する。3.正方向の時、上限をaとしてxiからxiMまで値をランダムに選択する。4.負方向の時、下限をbとしてxiMからxiまでの値をランダムに選択する。上述した通り、分類された時系列データの特徴パタンと、それを用いた分類ルール、または自動的に改良された特徴パタンとそれを用いた分類ルールを抽出するとともに、抽出した分類ルールを用いて未分類の時系列データの分類を予測する機能が提供される。分類ごとの時系列データの形状とそれを用いたルールを抽出するという目的のために、実際に装置を作成して実現した。提案装置の効果について1特徴パタンに基づいた決定木生成は有効か2有効な特徴パタンは抽出可能か3改良機能はどの程度有効かの3点について調査を行う。このために2種類の実験データを用いる。提案装置の想定する理想的なデータを人工的に作成することによって効果1を調査する。次に実際の医療データを用いて効果2、3について調査する。図6は装置全体の概要を示す。1社の株価、1人の患者などを単位とした1つの時系列データは、クラス値に関連付けられて保存されている。まず各時系列データに対して、すべての部分時系列データのセットを固定長のスライドウィンドウによって収集する。収集された全ての部分時系列データを用いてクラスタリングを行う。次に、いくつかの代表シーケンスはTFIDFによってフィルターされ、残ったシーケンスが特徴パタンとなる。各部分時系列データは特徴パタンとの距離を用いて表現される。これが決定木学習を使って特徴抽出する際のトレーニングデータとなる。特徴パタン抽出の際には部分時系列データ抽出のスライドウィンドウのサイズは20、スライド量を5とする。このとき、データの末端のスライドウィンドウのサイズに満たないデータは切り捨てる。DTWでは水平コスト時間軸のずれのコストを500、垂直コスト計測値のずれのコストを値の差の絶対値とした。決定木学習にはC45を用いた。パタン改良の効果を調査するために、遺伝的アルゴリズムで100世代分の計算し、各世代における予測精度を求める。決定木の分類精度は10分割交差検定によって測定する。まず、理想的な実験データの作成方法について説明する。まず優先度と未来状態と特徴パタンの組をあらかじめ5種類用意する。それらの特徴パタンと未来状態を設定していないランダムなパタン5種類をランダムに配置することで時系列データを作成する。図7に理想的な実験データの作成方法の概要を示す。作成した時系列データを20種類用意して実験を行う。停滞幅倍率は5とした。作成した時系列データから、単純に部分時系列データの各時刻の値を属性とした場合と、テストデータ作成に用いた特徴パタンを用いた場合と、ランダム生成した特徴パタンを用いた場合の3種類で決定木学習を行い比較する。精度と分散、そして決定木サイズの実験結果を表1に示す。Simpleは、単純に部分時系列データの各時刻の値を属性とした決定木である。Knownpatternsは、テストデータ作成に用いた特徴パタンを属性とした決定木である。GAKnownpatternsは、テストデータ作成に用いた特徴パタンを属性としたあと遺伝的アルゴリズムによって改良した決定木である。Randompatternsは、ランダム生成した特徴パタンを属性とした決定木である。GARandompatternsは、ランダム生成した特徴パタンを属性としたあと、遺伝的アルゴリズムによって改良した決定木である。特徴パタンを用いた手法では遺伝子の数を5、10、20と変えて測定する。表中の数値はすべて20種類のデータの平均値である。獲得した決定木の安定性を調べるために予測精度の分散も示す。表1から、SimpleとRandompatternsを比較するとそれほど予測精度に違いがなく、クラスタの詳細度が上がるごとに多少の精度向上があることが分かる。ただし、分散という点で従来手法よりもパタンを用いたほうが安定していることが分かる。また、Knownpatternsに関しては全ての設定で従来手法を上回る予測精度を得られた。こちらの実験でもクラスタの詳細度が上がるほど予測精度が上がることが分かる。GAを行う前と後では予測精度が数ポイント向上しており、大きな効果ではないが少なからず予測精度を高める効果があることが分かる。以下の実際の医療データを用いた実施結果でGAについての詳細な考察を行うが、人工的に作られたデータでは特徴パタン抽出によって高い予測精度を獲得できたため、GAによる精度向上が伸び悩んだと考えられる。提案した装置の有効性をさらに調査するために、実際の医療データを用いて実験を行った。使用するデータは千葉大学付属病院から提供されている慢性肝炎の検査データで、このデータは1982年から2001年までの20年間で771名についての検査の記録である。このデータから血小板の時系列データPLTのみを用いて慢性肝炎のタイプを予測する。慢性肝炎のタイプにはB型とC型の2種類があるが、C型肝炎については治療のためにインターフェロンの投与が行われた患者データもあるため、予測するクラスはB型肝炎C型肝炎インターフェロン投与無しC型肝炎インターフェロン投与有りの3種類とした。比較のために、従来手法としてC45、サポートベクタマシン以下SVM、ニューラルネットワーク以下、NNを用いてスライドウィンドウによって手に入れた部分時系列データの各時間を各属性値として使うことで分類予測を行う。これらの従来手法をダイレクトアプローチ以下、DAとして標記する。提案手法では特徴抽出でのクラスタ数を10、20、30、40、50の5種類で実験する。表2に予測精度の結果を示す。特徴パタン抽出だけを用いた場合、クラスタ数を40以上に設定することですべての既存手法よりも高い分類精度が得られた。しかし、GAによるパタン改良後の分類精度をみるとすべてのクラスタ数の設定において、すべての既存手法よりも高い分類精度を獲得できることが分かる。これらのことから、GAによるパタン改良機能は初期の分類精度が低い問題に対して有効に働くと考えられる。図8にGAによる世代ごとの分類精度の変化を示す。グラフで示す通り、5種類すべてのクラスタ数の設定が高い予測精度を得ていることがわかる。また、クラスタ数が低いほど最初の精度が悪いため、GAによる改良効果が高いと思われる。これらのことから、GAによる改良は、十分な特徴パタンの数を確保できずに精度が低くなる時ほど有効であり、最終的に安定して高い予測精度を出力する効果があるといえる。