決定木を比較する決定木比較装置、決定木比較方法及び決定木比較プログラム
【課題】決定木をその木構造の違いによらず詳細に比較するための技術を提供すること。
【解決手段】データセット格納部は、各々同種の目的属性を有する複数のインスタンスの集合である、複数のデータセットを格納する。決定木情報格納部は、異なるデータセットからそれぞれ生成された複数の決定木を格納する。目的属性決定部は、決定木の各ノードに、該ノードに決定木を生成する過程で分類されるインスタンス数の多い目的属性の値を該ノードのラベルとして決定する。基本頻度算出部は、各ノードについて、該ノードのラベルと同じ目的属性を有するインスタンスが決定木を生成する過程で分類される頻度を算出する。適用頻度算出部は、決定木に、他の決定木を生成する基となったインスタンスを分類させ、決定木の各ノードについて、該ノードのラベルと同じ目的属性を有するインスタンスが分類される頻度を算出する。出力部は決定木の比較結果として２つの頻度の比較結果を出力する。
【解決手段】データセット格納部は、各々同種の目的属性を有する複数のインスタンスの集合である、複数のデータセットを格納する。決定木情報格納部は、異なるデータセットからそれぞれ生成された複数の決定木を格納する。目的属性決定部は、決定木の各ノードに、該ノードに決定木を生成する過程で分類されるインスタンス数の多い目的属性の値を該ノードのラベルとして決定する。基本頻度算出部は、各ノードについて、該ノードのラベルと同じ目的属性を有するインスタンスが決定木を生成する過程で分類される頻度を算出する。適用頻度算出部は、決定木に、他の決定木を生成する基となったインスタンスを分類させ、決定木の各ノードについて、該ノードのラベルと同じ目的属性を有するインスタンスが分類される頻度を算出する。出力部は決定木の比較結果として２つの頻度の比較結果を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、決定木を比較する技術に関し、特に、決定木をその木構造の違いによらずノードレベルで詳細に比較するための決定木の比較技術に関する。
【背景技術】
【０００２】
多くの分野で、時系列に変化するデータストリームの分析は重要な研究テーマとなっている。例えば、購買履歴情報の分析において、購買動向のモデルの時間的な変化や、店舗ごとの購買動向の違いなどを知ることは、企業にとって死活問題である。このような問題を扱うため、一般的には、収集したデータストリームをいくつかのデータセットに分割し、各データセットについて何らかのモデル化を行う。そして時間的に隣接するモデル間の比較により、トレンドの変化の検出を行う。データマイニングの分野では、トレンドの変化は、コンセプトドリフトと呼ばれ、変化を検出するための技法が数多く提案されている。
【０００３】
非特許文献１及び２は、アンサンブル分類器を用いて、コンセプトドリフトをもつデータストリームを分析する技術を開示する。
【０００４】
非特許文献３は、動的に変化する決定木を用いる手法として知られているVFDT(Very Fast Decision Tree)とその評価結果を開示する。VFDTでは、データはノードを分割するごとに捨てられ、ストリームからの新たなデータを使ってその後の学習が行われる。
【０００５】
非特許文献４は、マルコフモデルを利用した過学習を防ぐ技術を開示する。
【０００６】
非特許文献５は、コンセプト間の類似性を判定する技術を開示する。ここでは新しく学習されたコンセプトとそれ以前のコンセプトとが用意され、現在のデータセットを使って両方のコンセプトに予測を行わせる。そして、予測した結果が一致した場合は＋１のポイントを与え、不一致の場合はー１のポイントを与える。データセットの全インスタンスについての合計ポイントが大きいほど、両コンセプトは類似していると判断される。
【０００７】
【非特許文献１】P. S. Yu, H. Wang, W. Fan and J. Han,“Mining concept-drifting data stream using ensemble classifiers.” inProceedings of the 9th ACMSIGKDD International Conference onKnowledge Discovery and Data Mining, pp.226-235, 2003年
【非特許文献２】K. Tumerand J. Ghosh, ”Error correlation and error reductionin ensemble classifiers.”, Connection Science, vol.8, pp.385-403, 1996年
【非特許文献３】P. Domingosand G. Hulten, ”Mining high-speed data streams.”, inSIGKDD, pp.71-80, 2000年
【非特許文献４】H. Wang, J. Yin, J. Pei, P. S. Yu and J. X. Yu, ”Suppressing model overfitting in mining concept-drifting data stream.” , inSIGKDD, pp.736-741, 2006年
【非特許文献５】Y. Yang, X. Wu and X. Zhu, “Combining proacive andreactive predictions for data streams.”, in Proceedingof the eleventh ACM SIGKDD international conference on Knowledge Discovery in DataMining, pp. 710-715, 2005年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記非特許文献１乃至５は、いずれも、コンセプトドリフトの有無を問題としている。即ち、上記非特許文献１乃至５は、どのようなコンセプトの変化があったのか、コンセプトドリフトの詳細を検討することについて言及するものではない。そこで、コンセプトドリフトの詳細を検討するために、説明能力が高いとされる決定木を分類器として利用することが考えられる。即ち、決定木の変化をコンセプトドリフトの変化とみなすのである。
【０００９】
しかし、一般にその木構造が互いに異なる２つの決定木の比較は難しい。また、例えば決定木を用いて非特許文献５に開示されるコンセプトの類似性の判断を行っても、決定木が提供し得る説明能力はポイントの合計値の中に隠蔽されてしまい、得られるのは結局コンセプトドリフトの有無の判別である。
【００１０】
この発明は、上記の問題点を解決するためになされたものであって、木構造の違いによらず、２つの決定木を詳細に比較する技術を提供することを目的とする。また、決定木の比較により、コンセプトドリフトの発生を詳細に検討するための技術を提供することを他の目的とする。
【課題を解決するための手段】
【００１１】
一般に決定木を使ってモデル化を行うと、その決定木に入力される複数のインスタンスは、それぞれ決定木のルートノードからスタートして、中間ノードを経て、最終的にいずれかのリーフノードに分類される。本発明では、このインスタンスの流れ、即ち、インスタンスの分布の様子がモデルを表していると考え、このインスタンスの分布の様子の違いによって、コンセプトドリフトの有無を判断する。ここで、各インスタンスは、分類や法則化を行う対象となる目的属性と、該目的属性の変動を説明する説明属性を有する。目的属性は、決定木を機械学習により生成するときに使われるもので、一般には複数の値を取ることが可能なものである。
【００１２】
例えば時系列データをいくつかのデータセットに分割し、各データセットから対応する決定木を生成するとする。そして、時系列の変化を捉えるという観点から、時刻Tのデータセットから生成した決定木と時刻T＋１のデータセットから生成された決定木を比較することを考える。上述したように、本発明では２つの決定木を比較するために、決定木同士を直接比較するのではなく、決定木を流れるインスタンスの様子を比較する。そのため本発明では、時刻Tのデータセットのインスタンスを、時刻T+1の決定木に入力として与え分類させる。
【００１３】
もし２つの決定木が同じ木構造を持っているならば、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と同じになるはずである。また、２つの決定木の木構造が一部異なる場合は、その異なる部分において、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と異なるはずである。そして２つの決定木が全く異なる木構造を持っている場合は、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と全く異なるはずである。
【００１４】
このように本発明では、比較する２つの決定木の一方の決定木を生成する基となったデータセットを、他方の決定木に入力として与えて分類させ、そのインスタンスが辿る様子を調べる。そして本発明では、インスタンスが辿る様子から、２つの決定木がどの部分でどの程度異なっているかを詳細に把握する。なお、一方の決定木のどのノードに分類されたインスタンスの集合も、他方の決定木の入力とすることができる。従って、一方の決定木の任意のノードが表すコンセプトについて、他方の決定木における変化を見ることが可能となる。
【００１５】
即ち、上記目的を達成する本発明に係る決定木比較装置は、複数のデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する、データセット格納部と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、複数の決定木のそれぞれの各ノードについて、上記決定木を生成する過程で上記ノードに分類されたインスタンスの数が最も多い目的属性の値を上記ノードの目的属性として決定する目的属性決定部と、複数の決定木のそれぞれの各ノードについて、上記決定木を生成する過程で上記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、上記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部から読み出す読出し部と、読み出した各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて、該ノードに分類され、かつ上記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、上記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を、２つの決定木の比較結果として出力する出力部とを含む。
【００１６】
好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を一定期間観測して得られた時系列データセットを所定時間間隔で分割して得られる複数のデータセットである。
【００１７】
また好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットである。
【００１８】
また好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットである。
【００１９】
また好ましくは、上記出力部は、関係情報として、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部を含む。
【００２０】
また好ましくは、上記出力部は、関係情報として、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する、第１決定木グラフ作成部を含む。
【００２１】
また好ましくは、上記出力部は、関係情報として、他方の決定木の各ノードを示す図形の色、模様及び形状の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標にノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する、第２決定木グラフ作成部を含む。
【００２２】
また好ましくは、複数の決定木は、所定の基準に従って順に並べることが可能であり、読出し部及び適用頻度算出部による処理は、所定の基準に従って複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われる。そして上記出力部は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、上記関係情報として、決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含む。なお、所定の基準は、決定木を生成する基となったデータセットの各要素であるインスタンスの属性、例えば、時間属性、場所属性、及び年代属性等に基づく基準であってよい。
【００２３】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のルートノードに分類された要素であるインスタンスの集合である。
【００２４】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のある中間ノードに分類された要素であるインスタンスの集合である。
【００２５】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるリーフノードに分類された要素であるインスタンスの集合である。
【００２６】
また、本発明に係る決定木比較装置は、ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する前記データセット格納部と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を上記ノードの目的属性として決定する目的属性決定部と、複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、上記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部から読み出す読出し部と、読み出した各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて、該ノードに分類され、かつ上記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、上記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に、他方の決定木の各ノードの基本頻度と適用頻度の各値をマップした２次元グラフを、２つの前記決定木の比較結果として出力する出力部とを含む。
【００２７】
以上、決定木比較装置として本発明を説明したが、本発明は、情報処理装置において実行される、決定木比較方法、及び決定木比較プログラムとして把握することもできる。
【発明の効果】
【００２８】
本発明によれば、同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有するインスタンスの異なる集合から生成された２つの決定木を、それら木構造の違いによらず、詳細に比較することが可能となる。即ち従来技術のように単に２つの決定木が異なるか否かというだけでなく、２つの決定木がどの部分でどの程度異なるのか、詳細にその違いを理解することが可能となる。
【００２９】
また、決定木の説明能力やその階層構造を利用することで、例えばルートノード近くにある判断ルールでは２つの決定木の間に変化は見られないが、ある中間ノードまで辿ると判断ルールに変化が見られる等、どのレベルのどの判断ルールに変化が生じたか、変化の詳細を知ることが可能となる。その結果として、コンセプトドリフトの発生の詳細を考察することが可能となる。本発明のその他の効果については、各実施の形態の記載から理解される。
【発明を実施するための最良の形態】
【００３０】
以下、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００３１】
本発明では、２つの決定木を比較するために、決定木同士を直接比較するのではなく、決定木を流れるインスタンスの様子を比較する。そのため本発明では、比較する２つの決定木の一方の決定木を生成する基となったデータセットを、他方の決定木に入力として与えて分類させる。そして、他方の決定木の各ノードについて、該ノードに分類される他方の決定木を生成する基となった本来のインスタンスの数と、該ノードに分類される一方の決定木を生成する基となったインスタンスの数とを比較する。
【００３２】
但し比較を適切に行うため、各ノードに分類されるインスタンス数の正規化を行う。正規化の具体的な方法は後述するが、正規化されたインスタンス数を以下では、他方の決定木を生成する基となった本来のインスタンスについては「基本頻度」と呼ぶ。また、一方の決定木を生成する基となったインスタンスについては、他方の決定木に適用するものであることから「適用頻度」と呼ぶ。決定木の各ノードはコンセプトとみなせるため、他方の決定木の各ノードに分類されるインスタンス数の変化、即ち他方の決定木の各ノードの基本頻度と適用頻度の違いが、コンセプトドリフトの有無を示すと考えることができる。以下では、本発明に係る決定木比較装置の機能構成を説明する。
【００３３】
図１は、本発明の一実施形態に係る決定木比較装置１００の機能構成の一例を示す図である。本発明の実施形態に係る決定木比較装置１００は、データセット格納部１１０、決定木情報格納部１１５、目的属性決定部１２０、基本頻度算出部１２５、読出し部１３０、適用頻度算出部１３５、出力部１４０を含む。
【００３４】
データセット格納部１１０は、複数のデータセットを格納するデータセット格納部である。ここで、各データセットの要素であるインスタンスは、各々、同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する。好ましくは、複数のデータセットは、ある事象を一定期間観測して得られた時系列データを、所定時間間隔で分割して得られる複数のデータセットである。あるいは、複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットであってもよい。更には、複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットであってもよい。
【００３５】
本実施例に係る複数のデータセットは、ある事象を一定期間観測して得られた時系列データを、所定時間間隔で分割して得られる複数のデータセットD(1),D(2),…,D(N)であるとする。また、データセットの要素であるインスタンスを次のように定義する。X={x1,x2,…,xn,y}。即ち、本実施例に係るインスタンスは、１つの目的属性yと、n個の説明属性xiを有するとする。なお、目的属性は複数の値を取ることが可能であるが、説明を簡単にするため本実施例に係る目的属性はyesとnoのいずれか一方の値を取るものとする。
【００３６】
図２(a)に、データセット格納部１１０に格納される、任意のデータセットのテーブルの一例を示す。図２(a)に示す例では、説明属性xiの数はdata0、data1、data2、data3の４つであり、目的属性ｙは上述したとおりyesとnoのいずれか一方の値を取る。なお、本実施例では、データセット毎にテーブルを設ける構成としたが、かかる構成に限定されず、例えばデータセットIDの欄を設けることにより、１つのテーブルに全てのデータセットを格納する構成を採用してもよい。また、１つのデータセットに含まれるインスタンスの数は任意である。
【００３７】
決定木情報格納部１１５は、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する。なお以下では、複数の決定木をM(1), M(2), …, M(N)と表記する。ここで任意の決定木M (i)はデータセットD(i)に対応する。即ち、決定木M(i)はデータセットD(i)から生成されたものである。なお、決定木の生成方法は公知であり、一例として、C4.5の決定木生成アルゴリズムを実装したWekaのJ48を利用することができる。
【００３８】
図２(b) 及び(c)に、図２(a)を参照して説明したのと同じ構造をもつデータセットから生成された決定木のグラフの一例を示す。図２(b)は、時刻TのデータセットD(i)から生成された決定木M(i)である。また、図２(c)は、時刻T+1のデータセットD(i+1)から生成された決定木M(i+1)である。いずれの図においても、ノードを示す円の中の数字はノードIDを示す。また、ノードとノードを結ぶエッジの横に記載する式は、上位のノードから下位のノードへ分類されるための条件式、すなわち判断ルールである。例えば、図２(b)において、あるインスタンスがルートノードのノードID=0からノードID=1に分類されるためには、その説明属性data0の値がA1である必要がある。このdata0=A1が、ノードID=0からノードID=1に分類されるため判断ルールである。
【００３９】
また、図２(b)及び(c)に示されるような決定木は、一例として図３及び図４に示すようなテーブル構造により決定木情報として決定木情報格納部１１５に格納される。図３は時刻Tの決定木M(i)の、図４は時刻T+1の決定木M(i+1)の決定木情報の一例を示す。本実施例では、決定木は、決定木の階層ごとに用意されたテーブルにその情報を登録される。そこで次に図３を参照して、決定木情報格納部１１５に格納される決定木情報を具体的に説明する。図４については、図３と同じであるためその説明を省略する。
【００４０】
図３(a)は、時刻Tの決定木M(i)のルートノードのテーブルの一例を示す。いずれの階層のテーブルも、「テーブル名」、「ノードID」、「判断ルール」、「目的属性」、「基本インスタンス」、「下位層テーブル名」の各フィールドを有する。ここで「判断ルール」フィールドには、該ノードに分類されるための判断ルールが登録される。しかしルートノードは全てのインスタンスが入力される出発地点であるため、図３(a)に示すテーブルでは該フィールドは空欄となる。「目的属性」及び「基本インスタンス」の各フィールドについては後述する。「下位層テーブル名」フィールドには、当該ノードが属する階層より１つ下の階層のテーブル名が登録される。従って、決定木をルートノードからリーフノードまで順に辿っていくには、現在のノードの「下位層テーブル名」フィールドの値を参照し、その値を「テーブル名」フィールドに有するテーブルを取得するという操作を繰り返せばよい。
【００４１】
図３(b)は、時刻Tの決定木M(i)のルートノードより１つ下の階層に属するノード群のテーブルの一例を示す。図２(b)から分かるように、ルートノードの下にはノードID=1〜5の５つのノードが存在する。従って、図３(b)に示す第１テーブルには、この５つのノードの情報が登録される。また、図２(b)から分かるように、ノードID=1〜5の５つのノードのうち子ノードをもつのはノードID=3のノードみである。従って、第１テーブルの「下位層テーブル名」フィールドは、ノードID=3のエントリのみ値（第２テーブル）が登録され、他のノードIDのエントリの同フィールドは空欄となる。
【００４２】
図３(c)は、時刻Tの決定木M(i)のノードID=3のノードより１つ下の階層に属するノードのテーブルの一例を示す。図２(b)から分かるように、ノードID=3のノードの下にはノードID=6〜10の５つのノードが存在する。従って、図３(c)に示す第２テーブルには、この５つのノードの情報が登録される。また、図２(b)から分かるように、ノードID=6〜10の５つのノードはいずれも子ノードをもたない。従って、第２テーブルの「下位層テーブル名」フィールドは、いずれのノードについても空欄となる。
【００４３】
目的属性決定部１２０は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、該ノードに決定木を生成する過程で分類されるインスタンスの数が最も多い目的属性の値を、そのノードの目的属性として決定する。即ち、目的属性決定部１２０は、処理対象の決定木に、該決定木を生成する基となったデータセットを入力として分類させる。そして、目的属性決定部１２０は、決定木の各ノードについて、該ノードを経由するインスタンスの数をインスタンスの目的属性の値別にカウントし、カウントしたインスタンスの数が最も大きい目的属性の値を、そのノードの目的属性として決定する。決定された各ノードの目的属性の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。なお、ノードの目的属性は、詳細は後述するが、基本頻度及び適用頻度を算出する際に利用される。
【００４４】
図２(b)及び図３に示す時刻Tの決定木M(i)を例に、ノードの目的属性を決定する方法を具体的に説明する。図３を参照して説明したように、決定木情報の各テーブルには、「基本インスタンス」の「yes 」と「no」のフィールド、及び「目的属性」のフィールドが用意されている。「yes」のフィールドには、該ノードを経由するインスタンスであって、目的属性がyesであるインスタンスの数が登録される。同様に、「no」のフィールドには、該ノードを経由するインスタンスであって、目的属性がnoであるインスタンスの数が登録される。そして「目的属性」のフィールドには、該ノードに対して決定された目的属性が登録される。図３ (a)のルートノードのテーブルの場合、「yes」のフィールドは４１の値が、「no」のフィールドには５９の値が登録されている。従って、ルートノードの目的属性は、インスタンス数が最も多い目的属性の値noが登録される。図３ (b)、(c)の残りのテーブル、及び図４の全テーブルについても、同様にして目的属性の値が登録される。
【００４５】
基本頻度算出部１２５は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて基本頻度を算出する。ここで、ノードの基本頻度は、該ノードに決定木を生成する過程で分類された１以上のインスタンスのうち、該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、該ノードに分類された全インスタンスの数で割った値として定義される。算出された各ノードの基本頻度の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。
【００４６】
図２(b)及び図３に示す時刻Tの決定木M(i)を例に、ノードの基本頻度の算出方法を具体的に説明する。図３の各テーブルの「目的属性」フィールド、及び「基本インスタンス」フィールドの「yes 」と「no」の各フィールドには、既に値が登録されているものとする。基本頻度算出部１２５は、各テーブルのエントリ毎に次の処理を行う。基本頻度算出部１２５はまず、「yes 」フィールドと「no」のフィールドの値を足し合わせてその合計を求める。そして、「yes 」及び「no」の各フィールドのうち、「目的属性」フィールドの値に等しい方のフィールドの値を、先に求めた合計で割ることにより、ノードの基本頻度を算出する。例えば、図３(b)のノードID=1のノードの場合、目的属性はNOであることから、「no」フィールドの値14を、「yes 」フィールド及び「no」フィールドの値の和16で割って、ノードID=1のノードの基本頻度0.875を算出する。算出された基本頻度の値は、基本インスタンスの「基本頻度」フィールドに登録される。
【００４７】
読出し部１３０は、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部１１０から読み出す。ここで、一方の決定木のあるノードとは、一方の決定木の任意のノードであってよく、即ち、ルートノード、中間ノード、リーフノードのいずれであってもよい。即ち、読出し部１３０は、一方の決定木を生成する基となったデータセットのインスタンスの集合のうち、他の決定木における変化を調べることを希望するコンセプトを表すノードに分類されるインスタンスの集合をデータセット格納部１１０から読み出す。
【００４８】
ノードの選択は、マウスやキーボード等の入力デバイスによりユーザによって指定されてもよく、或いはデフォルトとして、ルートノードを予め指定し、または全ノードが順次読み出し部１３０により選択されるよう設定しておいてもよい。なお本実施例では、比較する２つの決定木は、時刻Tの決定木M(i)と時刻T+1の決定木M(i+1)である。そこで、図２及び図３を参照して、読出し部１３０によるデータセット格納部１１０からのインスタンスの読出し方法の一例を具体的に説明する。
【００４９】
例えば、比較対象のノードとして、時刻Tの決定木M(i)のノードID=10のノードが選択されたとする。この場合、時刻T+1の決定木M(i+1)への入力とするため、時刻Tの決定木M(i)を生成する基となったインスタンスの集合のうち、ノードID=10のノードに分類されたインスタンスの集合をデータセット格納部１１０から読み出す必要がある。そのためにまず、決定木情報格納部１１５に格納される、時刻Tの決定木M(i)に対応する複数のテーブルから、「ノードID」フィールドの値が10であるエントリを読出し、「判断ルール」フィールドの値data2=C5と「テーブル名」フィールドの値第２テーブルを抽出する。
【００５０】
次に、時刻Tの決定木M(i)に対応する複数のテーブルから、「下位層テーブル名」フィールドの値が第２テーブルであるエントリを読出し、該エントリの「判断ルール」フィールドの値data0=A3と「テーブル名」フィールドの値第１テーブルを抽出する。かかる処理を、「判断ルール」が読み出せなくなるまで、またはテーブル名がルートノードのテーブルであることを示すまで繰り返す。最後に、それまで読み出した判断ルールを全て満たすインスタンスを、即ち上記例ではdata2=C5かつdata0=A3を満たす全てのインスタンスを、データセット格納部１１０の時刻Tの決定木M(i)に対応するデータセットから読み出す。読み出されたインスタンスの集合は、時刻Tの決定木M(i)を生成する基となったインスタンスの集合のうち、ノードID=10のノードに分類されたインスタンスの集合である。
【００５１】
適用頻度算出部１３５は、読出し部１３０により読み出された各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて適用頻度を算出する。ここで各ノードの適用頻度は、読出し部１３０により読み出された複数のインスタンスのうち、該ノードに分類され、かつ該ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、該ノードに分類される全インスタンスの数で割った値として定義される。算出された各ノードの適用頻度の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。
【００５２】
次に、具体例を用いてノードの適用頻度の算出方法の一例を説明する。ここでは、図２(b)に示す時刻Tの決定木M(i)を生成する基となったインスタンスであって、かつ時刻Tの決定木M(i)のノードID＝５のノードに分類されたインスタンスの集合Mを、図２(c)に示す時刻T+1の決定木M(i+1)の入力として分類する場合を考える。まず、図４(a)、(b)、(c)、(d)に示す時刻T+1の決定木M(i+1)の各テーブルに、新たに「適用インスタンス」のフィールドを追加して各テーブルを更新する。「適用インスタンス」フィールドは、「yes」、「no」、及び「適用頻度」の各フィールドを有し、いずれも初期値として０を設定する（図５(a)、(b)、(c)、(d)を参照）。
【００５３】
次に集合Mから１つインスタンスを取り出し、時刻T+1の決定木M(i+1)のルートノードに入力する。そして、入力したインスタンスが時刻T+1の決定木M(i+1)のいずれかのノードを経由する度、その経由されたノードの「適用インスタンス」フィールドの「yes」及び「no」フィールドのうち、入力インスタンスの目的属性の値と同じフィールドの方の値を１増加する。これを集合Mの全インスタンスに対して行う。
【００５４】
例えば入力インスタンスが、data0=A1, data2=C3, YESの属性値を有するとする。まず、第２ルートノード・テーブルを取得して、「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(a)参照）。次に、第２ルートノード・テーブルの「下位層テーブル名」フィールドの値を参照して、１つ下の階層のテーブル、第３テーブルを取得する（図５(b)参照）。そして、第３テーブルから、入力インスタンスがその判断ルールを満たすエントリを検索し、検索したエントリ、即ちノードID=3の「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(b)参照）。
【００５５】
次に、ノードID=3の「下位層テーブル名」フィールドの値を参照して、１つ下の階層のテーブル、第５テーブルを取得する（図５(d)参照）。そして、第５テーブルから、入力インスタンスがその判断ルールを満たすエントリを検索し、検索したエントリ、即ちノードID=11の「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(d)参照）。
【００５６】
集合Mの全インスタンスについて上述した一連の処理を終えると、適用頻度算出部１３５は、図５(a)、(b)、(c)、及び(d)の各テーブルのエントリ毎に次の処理を行う。即ち、まず「適用インスタンス」フィールドの「yes 」フィールド及び「no」のフィールドの値を足し合わせてその合計を求める。そして、「適用インスタンス」フィールドの「yes 」及び「no」の各フィールドのうち、「目的属性」フィールドの値に等しい方のフィールドの値を、先に求めた合計で割ることにより、ノードの適用頻度を算出する。算出された基本頻度の値は、「適用インスタンス」フィールドの「適用頻度」フィールドに登録される。
【００５７】
出力部１４０は、２つの決定木、即ち一方の決定木と他方の決定木の比較結果として、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を出力する。好ましくは、出力部１４０は、関係情報として、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部１４５を含む。これに代えて出力部１４０は、関係情報として、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する、第１決定木グラフ作成部１５０を含んでもよい。
【００５８】
あるいは出力部１４０は、関係情報として、他方の決定木の各ノードを示す図形の色、模様、及び形状の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に上記ノードの基本頻度と適用頻度の値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する、第２決定木グラフ作成部１５５を含んでもよい。更に出力部１４０は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含んでもよい。
【００５９】
この場合、読出し部１３０及び適用頻度算出部１３５による処理は、所定の基準に従って複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われる。なお、所定の基準に従って複数の決定木を並べるとは、例えば決定木を生成する基となったデータセットが時系列データを分割したものである場合は、複数の決定木を時間順に並べることを意味する。同様に、決定木を生成する基となったデータセットが年代別の複数のデータセットである場合は、複数の決定木を年代順に並べることを意味する。また、決定木を生成する基となったデータセットが場所別の複数のデータセットである場合は、複数の決定木を場所の近い順に並べることを意味する。以下では、第１の２次元グラフ作成部１４５、第１決定木グラフ作成部１５０、第２決定グラフ木作成部１５５、及び第２の２次元グラフ作成部１６０により作成されるそれぞれのグラフを順に説明する。
【００６０】
図６は、第１の２次元グラフ作成部１４５により作成される第１の２次元グラフの一例を示す。ここで、X軸は基本頻度、Y軸は適用頻度を表す。図６を参照して、２次元座標にマップされるデータの分布から、一方の決定木と他方の決定木の間にどのようなコンセプトドリフトが起きているかを読み取る方法を以下に説明する。まず、一方の決定木は、時刻Tのデータセットから生成されたものとし、そのノードの数をmとする。また、他方の決定木は、時刻T+1のデータセットから生成されたものとし、そのノードの数をnとする。そして、時刻Tの決定木のノードID＝j（jは0からm-1の整数）のノードに分類されたインスタンスの集合を、時刻T+1の決定木に入力として与え分類させたとする。このとき、目的属性がyesとnoいずれか一方の値をとる本実施例においては、他方の決定木のノードID=i（iは0からn-1の整数）のノードの基本頻度をx(i)とすると、0.5≦x(i)≦1が成り立つ。
【００６１】
これは、目的属性と基本頻度x(i)の定義から明らかである。即ち、ノードの目的属性は、該ノードに決定木を生成する過程で分類されるインスタンスの数が最も多い目的属性の値である。また、ノードの基本頻度は、該ノードに決定木を生成する過程で分類された１以上のインスタンスのうち、該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、該ノードに分類された全インスタンスの数で割った値である。
【００６２】
一方、時刻T+1の決定木のノードID=iのノードの適用頻度をy(j,i)とすると、0≦y(j,i)≦1が成り立つ。これは、時刻T+1の決定木の各ノードの適用頻度は、時刻Tの決定木のあるノードに分類されたインスタンスの集合を入力とし分類させた場合に、該ノードに分類され、かつ該ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、該ノードに分類される全インスタンスの数で割った値であるということから、明らかである。即ち本発明では、時刻T+1の決定木への入力として、時刻T+1の決定木を生成する基となったインスタンスの集合を入力する場合と、時刻Tの決定木を生成する基となったインスタンスの集合を入力する場合とで、インスタンスの頻度の計算が同じ目的属性について行われるよう、基本頻度及び適用頻度を定義している。
【００６３】
（コンセプトの持続）時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、入力されたインスタンスの集合が時刻T+1の決定木のあるノードに分類される場合がある。このようなケースは、時刻Tの決定木のあるノードに分類された各インスタンスとそれぞれ同じ属性を有するインスタンスの集合が時刻T+1においても存在し、該インスタンスの集合によって、時刻T+1の決定木が、時刻Tの決定木のあるノードに相当するあるノードを持つ場合に起こると考えられる。
【００６４】
この場合、時刻Tの決定木のあるノードにより表されるコンセプトは、時刻T+1において持続しているといえ、また時刻T+1の決定木のあるノードの基本頻度と適用頻度の値はほぼ同じになる。従って、コンセプトドリフトが全く起こっていない場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=X上に分布すると言える（図６の番号２０５参照）。逆に、時刻T＋１の決定木のあるノードの基本頻度と適用頻度の値が、Y=X上にマップされない場合、当該ノードではコンセプトドリフトが起きていると言える。以下に、コンセプトが継続しない場合を更に場合分けして詳細に説明する。
【００６５】
（コンセプトの消滅）時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、インスタンスの集合が時刻T+1の決定木のノード全体に散らばる場合がある。この場合は、時刻Tにおいて存在していたコンセプトが、時刻T+1では失われてしまい、特定のコンセプトとして同定できなくなったと解釈できる。つまり、時刻T+1の決定木がそのインスタンスの集合を説明する能力を失っている場合には、インスタンスの集合は時刻T+1の決定木の各ノードに約1/2の割合で散らばっていくと考えられる。従って、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において消滅している場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=0.5上に分布する（図６の番号２１０参照）。
【００６６】
（コンセプトの絞込み）次に時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、時刻T＋１の決定木のいくつかのノードの基本頻度と適用頻度の値が、Y=１上にマップされる場合を考える。この場合は、時刻Tのインスタンスの一部が絞込みを受けて時刻T+1のあるノードの条件を満たすインスタンスのみが、時刻T+1のノードに集中する場合である。それがY=1上にマップされたと考えることができる。従って、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において絞込みを受けた場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=1上に分布する（図６の番号２１５参照）。
【００６７】
（新しいコンセプトの出現）時刻Tの全インスタンスを時刻T＋１の入力としても、時刻T＋１の決定木のノードの中に辿られない、あるいはほとんど辿られないノードが存在し得る。このような場合には、時刻Tのインスタンスでは表現されていなかった新しいノードが時刻T+1で発生していると考えられる。従って、時刻T+1で新たに発生した各ノードの基本頻度と適用頻度の値は、Y=0上に分布する（図６の番号２２０参照）。なお、時刻Tのあるノードに分類されたインスタンスの集合を時刻T＋１の入力とした場合にも、時刻T＋１の決定木のノードの中に、辿られない、あるいはほとんど辿られないノードが存在し得る。しかしこの場合は、入力が、時刻Tの決定木のあるノードによって表されるコンセプトに制限されたためと考えるのが適当である。従って、時刻T+1の決定木において新しいコンセプトが発生しているか否かを判断するためには、時刻Tの決定木を生成する基となった全インスタンスを入力する必要がある。
【００６８】
なお、上記説明した２つの決定木の比較を利用することにより、決定木のあるノードに分類されるインスタンスが少ない場合に、当該インスタンスが誤差であるのか、またはコンセプトドリフトがピンポイントで発生していることを示すのか、見分けることが可能となる。このことを、具体例を用いて説明する。時刻Tの決定木において、２つのインスタンスが同じ１つのノードに分類されているとする。但し、２つのインスタンスは互いに異なる目的属性を有するとする。この場合、そのノードは説明能力を持っておらず、通常は２つのインスタンスはノイズであると解釈される。しかし、この２つインスタンスを時刻T+1の決定木に与え分類させた場合に、一方のインスタンスが当該インスタンスのみを含むノードに分類されたとする。この場合は、そのノードは明らかに説明能力があり、そのインスタンスは誤差ではなく、コンセプトドリフトがピンポイントで発生していることを示していることが分かる。
【００６９】
次に図２乃至図５に示した時刻Tと時刻T+1の決定木を比較した場合を例に、第１の２次元グラフ作成部１４５より作成される２次元グラフを説明する。先に図２乃至図５に示される時刻Tと時刻T+1の決定木をそれぞれ生成する基となった人工データの生成方法をここで説明しておく。本実施例では、図２(a)に示されるようなデータセットを、moving hyper planeと呼ばれるシミュレーション手法により作成した（非特許文献１及び４参照）。
【００７０】
本シミュレーション手法では、d次元空間上（本実施例ではd=4）に一様分布するデータをデータセットの各インスタンスとみなす。データはベクトルとして表され、その成分はそれぞれランダムな値（x1、x2、x3、x4）を取り、それぞれ説明属性data0、data1、data2、data3の値を示すものとする。なお、説明を容易にするため、本実施例では４次元空間の各軸をそれぞれ５つの領域[0, 0.2]、[0.2, 0.4]、[0.4, 0.6]、[0.6, 0.8]、[0.8, 1.0]に分割し、軸ごと各領域に１つの値を割り当てる。
【００７１】
即ち、data0の場合、上記５つの領域に対して順に’A1’、 ’A2’、 ’A3’、 ’A4’、 ’A5’の値を割り当てる。同様に、data1の場合、上記５つの領域に対して順に’B1’、 ’ B 2’、 ’ B 3’、 ’ B 4’、 ’ B 5’の値を割り当てる。同様に, data2の場合、上記５つの領域に対して順に’C1’、 ’ C 2’、 ’ C 3’、 ’ C 4’、 ’ C 5’の値を割り当てる。同様に, data3の場合、上記５つの領域に対して順に’D1’、 ’ D 2’、 ’ D 3’、 ’ D 4’、 ’ D 5’の値を割り当てる。従って、x1成分が[0, 0.2]の範囲の値をとるデータの場合、該データの説明属性data0の値はA1となる。また、x2成分が[0.6, 0.8]の範囲の値をとるデータの場合、該データの説明属性data1の値はB4となる。
【００７２】
一方、データの目的属性の値は、ベクトル長Σaixi(ここでΣは、添え字i=1〜4の総和を示す）により決定される。ここでaiは、該データの成分xiの重みであり、ランダムな値を取る。Σaixi= a0により決定されるhyper planeは4変数xiが作る4次元の空間に対して、一つの条件式を与えている。したがって
Σaixi= a0を満たす４変数xiは一つ次元が少ない3次元 hyper planeを表す。4次元空間が一つの3次元空間を挟んで二つの部分空間に分離されることになる。その二つの空間はそれぞれ、Σaixi< a0とΣaixi> a0で表すことが出来る。その二つの部分空間にYesとNoを割り振る。これを次元の少ない簡単な2次元の例で説明する。2次元空間に一つの条件式a1x1+a2x2=a0を与えることで、一次元の直線を定義することが出来る。2次元空間は1次元空間の直線で二つの半平面に分割されることになる。その2つの半平面は
a1x1+a2x2<a0とa1x1+a2x2> a0を満たす領域として定義できる。そしてその二つの領域にそれぞれYes Noを割り振ることになる。
【００７３】
目的属性の値は、ベクトル長Σaixiが所定の値a0よりも小さい場合はyesを、それ以外の場合はnoをとるとする。なお、所定の値a0はhyper planeが空間を２分するよう、a0=(1/2)Σai(ここでΣは、添え字i=1〜4の総和を示す）と定義する。かかる定義により、データの約半分が、目的属性をyesとし、残り半分が目的属性をnoとする。所定の値a0は、hyper planeの動きによって変化し、従って、hyper planeを動かすことでコンセプトドリフトの発生をシミュレーションすることが可能となる。hyper planeを動かしながら、時系列データを取得し、時系列データを１００件単位でデータセットに分割する。なお本実施例では、データ全体に対して５％の誤差を入れている。
【００７４】
このようにして作成した人工データを用いて生成された時刻Tの決定木が図２(b)及び図３に示される決定木であり、時刻T+1の決定木が図２(c)、図４及び図５に示される決定木である。まず初めに、時刻Tの決定木のルートノードに分類されるインスタンスの集合、即ち、時刻Tの全インスタンスを、時刻T+1の決定木の入力として２つの決定木を比較した場合に得られる２次元グラフを図７(a)に示す。図７(a)のグラフ中示される番号は、時刻T+1の決定木のノードIDを表している。
【００７５】
図７(a)を見ると、Y=X上またはその周辺にマップされているノードが存在することが分かる（ノードID=0,1,2,4,5,14)。これらノードについては、時刻Tと時刻T+1の間でコンセプトが継続しているといえる。一方その他のノードについては、いずれもコンセプトドリフトが起きているといえる。特に、Y=0上にマップされているノードについては（ノードID=3,7,9〜13)、時刻Tのインスタンスが全く辿り着いていないことから、いずれも時刻T+1において新たに生じたコンセプトを示すノードであるといえる。
【００７６】
次に、時刻Tの決定木のノードID=5のリーフノードに分類されるインスタンスの集合を、時刻T+1の決定木の入力として２つの決定木を比較した場合に得られる２次元グラフを図７(b)に示す。図７(a)と同様に、図７(b)のグラフ中示される番号は、時刻T+1の決定木のノードIDを表している。図７(b)をみると、時刻T+1のノードID=8のノードのデータから、時刻Tの決定木のノードID=5のリーフノードに分類されるインスタンスの一部が絞込みを受けてY=1上にマップされているのが分かる。即ち、(0.5,1)にマップされる時刻T+1のノードID=8のノードは、時刻Tにおいてもっていた説明能力を時刻T+1において失っており、ノードID=8のノードにおいて絞込みのコンセプトドリフトが起きていることが分かる。
【００７７】
次に第１決定木グラフ作成部１５０及び第２決定木グラフ作成部１５５がそれぞれ作成するグラフを、図８に示す決定木を例として説明する。図８(a)及び(b)は、天気と気温によってテニスを行うかどうかを決める決定木を示す。図８(a)に示す時刻Tの決定木は、季節が秋のときに得られたデータセットから生成された決定木である。一方図８(b)に示す時刻T+1の決定木は、季節が冬のときに得られたデータセットから生成された決定木である。いずれの図においても、ノードを示す円の中の数字はノードIDを示す。また、ノードID=0のノード近くに記載される「Yes, 10/2, 0.8」において、「Yes」はノードの目的属性を示す。また、「10/2」は、該ノードに分類された全インスタンス数/ノードの目的属性と異なる目的属性を有するインスタンス数を示す。更に「0.8」は、式 (10-2)/10より求められる該ノードの基本頻度を示す。他のノードについても同様である。
【００７８】
ここで、本発明の比較方法を用いて時刻Tと時刻T+1の決定木を比較してみる。即ち、時刻Tの決定木のノードID=0のルートノードに分類されるインスタンスを時刻T+1の決定木に与えて分類させる。その結果を図８(c)に示す。図８(c) においても、ノードを示す円の中の数字はノードIDを示す。また、ノードID=0のノード近くに記載される「Yes, 10/2, 0.8」において、「Yes」はノードの目的属性を示す。また、「10/2」は、該ノードに分類された全インスタンス数/ノードの目的属性と異なる目的属性を有するインスタンス数を示す。更に「0.8」は、式(10-2)/10より求められる該ノードの適用頻度を示す。図８(b)と図８(c)を比較することで、時刻T+1の冬のデータセットの各インスタンスと時刻Tの秋のデータセットの各インスタンスが、それぞれ時刻T+1の決定木を辿る様子を見比べることができる。
【００７９】
比較の結果、ノードID=0〜3のノードでは、基本頻度と適用頻度が同じであることからコンセプトドリフトは起きていないことが分かる。一方、ノードID=4のノードでは、基本頻度と適用頻度が異なっていることから、コンセプトドリフトが起きていることが分かる。この様子を上述した第１の２次元グラフ作成部１４５により作成される２次元グラフで表したものを図９に示す。図９をみると、ノードID=0〜3のノードのデータはY=X上にマップされていることから、これらノードではコンセプトドリフトは起きていないことが分かる。一方、ノードID=4のノードのデータはY=Xの直線から外れていることから、該ノードではコンセプトドリフトが起きていることが分かる。
【００８０】
しかしながら、図９に示す２次元グラフでは、階層構造をもつ決定木のどの階層レベルでコンセプトドリフトが起きているかを知ることは難しい。そこで、第１決定木グラフ作成部１５０は、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する。図１０(b)に、上記様子を第１決定木グラフ作成部１５０が作成する決定木のグラフにより表したものを示す。但し、図１０(b)では、基本頻度と適用頻度が等しい場合のノードの大きさをゼロとせず、他のどのノードよりも小さい所定の大きさをもつノードとして表している。図１０(b)によれば、ノードID=2のノードレベルまではコンセプトドリフトは起きておらず、その下のより詳細な判断ルールで指定されるノードID=4においてコンセプトドリフトが起きていることが分かる。
【００８１】
このように、第１決定木グラフ作成部１５０が作成する決定木のグラフによれば、コンセプトドリフトが起こっている場合に、決定木のもつ階層構造のどのレベルでコンセプトドリフトが起こっているか、また、どの程度の大きさのコンセプトドリフトが起こっているのか、コンセプトドリフトの内容を詳細に知ることが可能となる。なお、決定木のノードを表す図形の大きさに代えて、決定木のノードを表す図形の色、模様、形状等を利用して、コンセプトドリフトの内容の詳細を視覚的に表すことも可能である。第２決定木グラフ作成部１５５は、決定木の各ノードを示す図形の色、模様、形状の少なくとも１つが、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標にノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する。本実施例に係る第２決定木グラフ作成部１５５は、決定木のノードを示す図形の色及び模様を利用する。
【００８２】
図１０(a)に、第２決定木グラフ作成部１５５が利用する、X軸を基本頻度及びY軸を適用頻度とした２次元座標の領域の色分けの一例を示す。領域の色分けは、該領域にマップされるノードについて起きているとされるコンセプトドリフトの種類に基づいて行う。図６を参照して説明したように、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の各値は、２次元座標の0.5≦X≦1かつ0≦Y≦1の範囲内にマップされる。
【００８３】
コンセプトドリフトが全く起きていない場合、各ノードの基本頻度と適用頻度の値は、Y=X上に分布する。そこで、図１０(a)に示す例では、|Y-X|<h、X=0.5、X=1、Y=1で囲まれた領域を白で色分けする。そして、決定木のグラフにおいてノードの色が白の場合、該ノードではコンセプトドリフトが起こっていないことを示すようにする。なお、上記定義された領域の境界のうち境界値Y=X-h 及びY=X+hは、この領域に含まれないものとする。
【００８４】
また、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において消滅している場合、時刻T+1の決定木のいくつかのノードの基本頻度と適用頻度の値は、Y=0.5上に分布する。そこで、図１０(a)に示す例では、Y=0.5、Y=X-h、X=1で囲まれた領域を緑で色分けする。これにより、決定木のグラフにおいてノードの色が緑の場合、該ノードではコンセプトが消滅していることを示すようにする。なお、上記定義された領域の境界値Y=0.5、Y=X-h、X=1は全てこの領域に含まれるものとする。
【００８５】
また、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において絞込みを受けた場合、時刻T＋１の決定木のいくつかのノードの基本頻度と適用頻度の値は、Y=1上に分布する。そこで、図１０(a)に示す例では、Y=1、Y=X+h、X=0.5で囲まれた領域を青で色分けする。そして、決定木のグラフにおいてノードの色が青の場合、該ノードではコンセプトの絞込みがあったことを示すようにする。なお、上記定義された領域の境界値Y=1、Y=X+h、X=0.5は全てこの領域に含まれるとする。
【００８６】
更に、時刻T+1で新たなコンセプトが現れた場合、該コンセプトを表す時刻T+1の決定木の新たに追加された各ノードの基本頻度と適用頻度の値は、Y=0上に分布する。そこで、図１０(a)に示す例では、Y=0.5、Y=X-h、X=1、X=0.5, Y=0で囲まれた領域を赤で色分けする。そして、決定木のグラフにおいてノードの色が赤の場合、該ノードが示すコンセプトは時刻T+1で新しく発生したものであることを示すようにする。なお、上記定義された領域の境界のうち境界値Y=0.5は、この領域に含まれないものとする。なお図１０(a)に示す色分けはあくまでも説明のための一例であり、色分けの境界は図１０に示す例に限定されないことに留意されたい。
【００８７】
図１０(b)はまた、図８(b)と図８(c)の比較結果の様子を、第２決定木グラフ作成部１５５が図１０(a)に示す色分けを利用して作成した決定木のグラフでもある。このように、第２決定木グラフ作成部１５５が作成する決定木のグラフによれば、コンセプトドリフトが起こっている場合に、決定木のもつ階層構造のどのレベルで、どのような種類のコンセプトドリフトが起こっているか、コンセプトドリフトの内容を詳細にかつ視覚的に知ることが可能となる。
【００８８】
次に第２の２次元グラフ作成部１６０が作成するグラフを、図１１乃至図１３を参照して説明する。図１１(a)、(b)及び 図１２(a)、(b)に示す各２次元グラフは、上述した第１の２次元グラフ作成部１４５により作成されたグラフである。それぞれの２次元グラフで比較されている２つの決定木は、上述したmoving hyper planeにより生成した人工の時系列データを複数に分割してできたデータセットを基にそれぞれ生成された、時間的に隣接した２つの決定木である。
【００８９】
即ち、図１１(a)の２次元グラフは、時刻T=0とT=1の決定木を比較して得られた２次元グラフである。同様に、図１１ (b) の２次元グラフは、時刻T=1とT=2の決定木を、図１２ (a) の２次元グラフは、時刻T=2とT=3の決定木を、図１２ (b) の２次元グラフは、時刻T=3とT=4の決定木を、それぞれ比較して得られた２次元グラフである。いずれにおいても、先の時刻の決定木のルートノードに分類されたインスタンスの集合を、後の時刻の決定木の入力としている。
【００９０】
これら４つの２次元グラフを見比べると、２つのタイプの２次元グラフがあることに気づく。１つは図１２(a)のグラフが示す２次元グラフである。即ち図１２ (a)のグラフには、Y=０上に分布するデータが複数観察される。特に、(X,Y)=(1,0)の点には複数のデータが重なってか表示されており、この点がコンセプトドリフトの発生を表している。もう１つは、図１１(a)、(b)及び 図１２ (b)のグラフが示す２次元グラフである。これらグラフでは、Y=XまたはY=0.5の近くにデータが集まっている様子が見られる。従って、これら２次元グラフの各々におけるデータの分布、偏りから、コンセプトドリフトは時刻T=3で起きたことが分かる。実際、人工の時系列データは、時刻T=3においてコンセプトドリフトが発生するよう生成したものである。
【００９１】
このように第１の２次元グラフ作成部１４５により作成される２次元グラフにおけるデータの分布、偏り具合を検討することで、コンセプトドリフトが発生した時間を見つけることができる。しかしながら、時系列に並んだ２次元グラフの数が増えると、その作業も容易ではなくなる。そこで、本発明では、このような２次元グラフにおけるデータの偏りを、分散を使って表す。ここで平均はY-Xに対して定義する。なぜならば、Y-Xは決定木の各ノードの基本頻度と適用頻度の差を表しており、まさのその差がコンセプトドリフトの大きさを表すからである。本発明に係る第２の２次元グラフ作成部１６０は、比較対象となった一方の決定木と他方の決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフを作成する。
【００９２】
図１３(a)は、第２の２次元グラフ作成部１６０により作成される２次元グラフの一例を示す。ここでX軸は時間を、Y軸は分散を表す。グラフ上にマップされている分散データは、時刻T=0〜９の決定木から、隣接する決定木の組を取り出して比較して得られた値である。例えば、時刻T=1のデータは、図１１(a)に示すグラフに対応し、時刻T=1の決定木の基本頻度と適用頻度の差の分散である。図１３から明らかなように、第２の２次元グラフ作成部１６０により作成される２次元グラフによれば、コンセプトドリフトが発生した時刻を容易に知ることが可能となる。なお、図１１(a)、(b)及び 図１２(a)、(b)に示す時系列に並んだ複数の２次元グラフは、新たに時間の次元を追加することで、図１３(b)に示すように、１つの３次元グラフにまとめて表示することも可能である。
【００９３】
次に図１４乃至図１５を参照して、本発明の一実施形態に係る決定木比較処理の流れを説明する。図１４は、決定木比較装置１００において実行される、決定木を比較する決定木比較処理の全体の流れの一例を示すフローチャートである。なお、上述したように、決定木比較装置１００は、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部１１０と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部１１５とを有する。なおデータセット格納部１１０が格納するデータセット、及び決定木情報格納部１１５が格納する決定木情報は、図２を参照して説明したデータセット、及び図３乃至図５を参照して説明した決定木情報と、それぞれ同じデータ構造を有するものとする。
【００９４】
図１４において処理はステップ４００で開始し、決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、決定木を生成する過程で該ノードに分類されたインスタンスの数が最も多い目的属性の値を該ノードの目的属性として決定し、決定した目的属性の値を、そのノードに関連付けて決定木情報格納部１１５に登録する（ステップ４００）。
【００９５】
そして決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、決定木を生成する過程で該ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、そのノードに分類された全インスタンスの数で割った値である基本頻度を算出する（ステップ４０５）。
【００９６】
次に決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木の中から比較する２つの決定木を選択する（ステップ４１０）。また決定木比較装置１００は、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合を、他方の決定木への入力として選択する。
【００９７】
選択は、マウスやキーボード等の入力デバイスによりユーザによって指示されてよい。或いはデフォルトとして、所定の基準に従って決定木を並べた場合に隣接する決定木の全ての組み合わせを、比較する２つの決定木として順次選択するよう構成してもよい。同様に、一方の決定木のあるノードとして、ルートノードを予めデフォルトとして設定し、または全ノードが順次選択されるよう設定しておいてもよい。
【００９８】
比較する２つの決定木を選択すると、決定木比較装置１００は、他方の決定木への入力として選択したインスタンスの集合をデータセット格納部１１０から読み出し、他方の決定木に分類させる。そして、決定木比較装置１００は、他方の決定木の各ノードについて、該ノードに分類され、かつノードの目的属性と同じ値の目的属性を有するインスタンスの数を、ノードに分類される全インスタンスの数で割った値である適用頻度を算出する（ステップ４１５）。なお、適用頻度の算出処理の詳細は、図１５を参照して後述する。
【００９９】
最後に、決定木比較装置１００は、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を、２つの決定木の比較結果として出力する（ステップ４２０）。そして処理は終了する。なお関係情報は、上述したように、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の各値をマップした２次元グラフであってもよい。また、関係情報は、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフであってもよい。
【０１００】
また、関係情報は、他方の決定木の各ノードを示す図形の色、形状、及び模様の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木のノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフであってもよい。更に、関係情報は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフであってもよい。
【０１０１】
関係情報としてどのようなグラフを出力するかは、マウスやキーボード等の入力デバイスによりユーザによって指示されてよい。その際ユーザは、複数のグラフを選択してもよい。また比較結果の出力は、表示画面やプリンタ等に出力させてもよく、あるいはネットワークを介して他の情報処理装置へ送信してもよい。なお、ここでは繰り返しを避けるため、各グラフの詳細な説明は省略する。
【０１０２】
図１５は、図１４のステップ４１５の適用頻度の算出処理の流れの一例を示すフローチャートである。処理はステップ５００で開始し、決定木比較装置１００は、図１４のステップ４１０で選択した、一方の決定木のノードのうち比較対象のノードのノードIDの値nを取得する。そして決定木比較装置１００は、他方の決定木への入力となる比較対象のノードに分類されたインスタンスの集合をデータセット格納部１１０から読み出すために、以下のステップ５０５乃至ステップ５２５の処理を行う。
【０１０３】
即ち、決定木比較装置１００はまず、決定木情報格納部１１５に格納される一方の決定木の決定木情報である階層別の複数のテーブルから、ノードID=nのエントリを取得する（ステップ５０５）。そして決定木比較装置１００は、取得したエントリから、判断ルールの値と、該エントリが登録されているテーブルのテーブル名Mを取得する（ステップ５１０）。次に決定木比較装置１００は、一方の決定木の階層別の複数のテーブルから、下位層テーブル名がMであるエントリを取得する（ステップ５１５）。そしてステップ５２０において、決定木比較装置１００は、下位層テーブル名がMであるエントリを取得できたか否か判定する。
【０１０４】
下位層テーブル名がMであるエントリを取得できた場合（ステップ５２０：YES)、処理はステップ５１０へ戻り、決定木比較装置１００は、ステップ５１０乃至ステップ５２０の処理を繰り返す。一方下位層テーブル名がMであるエントリを取得できなかった場合（ステップ５２０：NO)、処理はステップ５２５へ進み、決定木比較装置１００は、データセット格納部１１０を検索して、ステップ５１０において取得した判断ルール全てを満たす、一方の決定木を生成する基となったS個のインスタンスを全て取得する。
【０１０５】
次に決定木比較装置１００は、決定木情報格納部１１５に格納される一方の決定木の決定木情報である階層別の複数のテーブルの各々に、「適用インスタンス」のフィールドを新たに追加し、初期値として０を設定する（ステップ５３０）。なお、「適用インスタンス」フィールドは、「yes」、「no」、及び「適用頻度」の３つのフィールドからなり、各フィールドを値０で初期化するものとする。また、決定木比較装置１００は、他方の決定木へ入力する入力インスタンスのカウンタiを値1で初期化する（ステップ５３５）。
【０１０６】
処理はステップ５４０へ進み、決定木比較装置１００は、ステップ５２５で取得したインスタンスの集合からi番目のインスタンスを取得し、他方の決定木への入力とする。そして決定木比較装置１００はまず、決定木情報格納部１１５に格納される他方の決定木の決定木情報である階層別の複数のテーブルから、ルートノードのエントリを取得する（ステップ５４５）。そして、i番目のインスタンスの目的属性がyesの場合、決定木比較装置１００は、ルートノードのエントリの「適用インスタンス」フィールドの「yes」フィールドの値を１増加する（ステップ５５０、５５５）。一方、i番目のインスタンスの目的属性がnoの場合、決定木比較装置１００は、ルートノードのエントリの「適用インスタンス」フィールドの「no」フィールドの値を１増加する（ステップ５５０、５６０）。
【０１０７】
次に決定木比較装置１００は、現在取得しているエントリの下位層テーブル名Nを取得する（ステップ５６５）。そして決定木比較装置１００は、下位層テーブル名Nを取得できたか否か判定し（ステップ５７０）、取得できた場合、決定木比較装置１００は、決定木情報格納部１１５に格納される他方の決定木の決定木情報である階層別の複数のテーブルから、テーブル名＝Nのテーブルを検索し、該テーブルから、i番目のインスタンスがその判断ルールを満たすエントリを取得する（ステップ５７５）。そして決定木比較装置１００は、ステップ５７５においてエントリを取得できたか否か判定する（ステップ５８０）。
【０１０８】
エントリを取得できた場合（ステップ５８０：YES）、処理はステップ５５０へ戻る。一方ステップ５７０またはステップ５８０においてNOの場合、処理はステップ５８５へ進み、決定木比較装置１００は、入力インスタンスのカウンタiを１増加し、iがステップ５２５で取得した全インスタンス数Sより大きいか否か判定する（ステップ５８５）。iがSより以下の場合、処理はステップ５４０へ戻り、ステップ５４０乃至ステップ５８５の一連の処理を繰り返す。
【０１０９】
一方、iがSより大きい場合、処理はステップ５９５へ進み、決定木比較装置１００は、他方の決定木の各テーブルの「適用インスタンス」のフィールド値を使って、他方の決定木の各ノードの適用頻度を算出する。即ち、決定木比較装置１００は、他方の決定木の各テーブルの各エントリについて、「適用インスタンス」フィールドの「yes」フィールドと「no」フィールドの値を足して、該エントリが示すノードに分類されたインスタンスの合計を求める。そして、決定木比較装置１００は、各エントリの「適用インスタンス」フィールドの「yes」フィールドと「no」フィールドのうち、該エントリの「目的属性」フィールドの値と等しい方のフィールドの値を、先に求めた合計で割って、該エントリが示すノードの適用頻度を算出する。算出された適用頻度は「適用頻度」フィールドに登録される。そして処理は終了する。
【０１１０】
図１６は、本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。情報処理装置は、バス２に接続されたＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、およびＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【０１１１】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、決定木比較装置１００としての情報処理装置の上記説明した数々の記憶装置には、本発明に係る決定木比較プログラムと、上記説明したデータセット格納部１１０及び決定木情報格納部１１５に含まれるデータを格納できる。そして複数のコンピュータ・プログラムはメインメモリ４にロードされることによって実行される。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる
【０１１２】
情報処理装置は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。情報処理装置は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。情報処理装置は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。情報処理装置は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【０１１３】
以上の説明により、本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、または、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【０１１４】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【０１１５】
【図１】本発明の実施の形態に係る決定木比較装置１００の機能構成の一例を示す図である。
【図２】（ａ）は、データセット格納部１１０に格納されるデータセットのデータ構造の一例を示す。（ｂ）は、図２(a)に示すデータ構造をもった時刻Tのデータセットから生成された決定木のグラフの一例を示す。（ｃ）は、図２(a)に示すデータ構造をもった時刻T+1のデータセットから生成された決定木のグラフの一例を示す。
【図３】（ａ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のルートノードの情報を登録する階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻Tの決定木の中間ノードの情報を登録する階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のリーフノードの情報を登録する階層テーブルの一例を示す。
【図４】（ａ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のルートノードの情報を登録する階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木の中間ノードの情報を登録する階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する階層テーブルの一例を示す。（ｄ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する階層テーブルの一例を示す。
【図５】（ａ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のルートノードの情報を登録する、更新された階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻Tの決定木の中間ノードの情報を登録する、更新された階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のリーフノードの情報を登録する、更新された階層テーブルの一例を示す。（ｄ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する、更新された階層テーブルの一例を示す。
【図６】本発明の実施形態に係る第１の２次元グラフ作成部１４５により作成される２次元グラフの一例を示す。
【図７】（ａ）は、時刻Ｔの決定木のルートノードを経由したインスタンスの集合を入力とした場合の、決定木の比較結果を示す２次元グラフを示す。（ｂ）は、時刻Ｔの決定木のＩＤ＝５のリーフノードに分類されたインスタンスの集合を入力とした場合の、決定木の比較結果を示す２次元グラフを示す。
【図８】（ａ）は、天気と気温によってテニスを行うかどうかを決める、時刻Tの決定木のグラフの一例を示す。（ｂ）は、天気と気温によってテニスを行うかどうかを決める、時刻T+1の決定木のグラフの一例を示す。（ｃ）は、時刻Ｔの決定木の全インスタンスを入力とした場合の、時刻T+1の決定木のグラフを示す。
【図９】図８（ｃ）に示す決定木グラフに対応する、本発明の実施形態に係る第１の２次元グラフ作成部１４５により作成される２次元グラフを示す。
【図１０】（ａ）はされた、第１軸を基本頻度及び第２軸を適用頻度とする２次元グラフの領域ごと色分け方法の一例を示す。（ｂ）は、本発明の実施形態に係る第１決定木グラフ作成部１５０及び第２決定木グラフ作成部１５５によって作成される決定木グラフの一例を示す。
【図１１】（ａ）は、時刻ｔ＝１のコンセプトドリフトの解析結果を示す。（ｂ）は、時刻ｔ＝２のコンセプトドリフトの解析結果を示す。
【図１２】（ａ）は、時刻ｔ＝３のコンセプトドリフトの解析結果を示す。（ｂ）は、時刻ｔ＝４のコンセプトドリフトの解析結果を示す。
【図１３】（ａ）は、本発明の実施形態に係る第２の２次元グラフ作成部１６０により作成される２次元グラフの一例を示す。（ｂ）は、コンセプトドリフトの解析結果を示す３次元グラフの一例を示す。
【図１４】本発明の実施形態に係る、決定木比較処理の流れの一例を示すフローチャートである。
【図１５】本発明の実施形態に係る、適用頻度算出処理の流れの一例を示すフローチャートである。
【図１６】本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。
【技術分野】
【０００１】
本発明は、決定木を比較する技術に関し、特に、決定木をその木構造の違いによらずノードレベルで詳細に比較するための決定木の比較技術に関する。
【背景技術】
【０００２】
多くの分野で、時系列に変化するデータストリームの分析は重要な研究テーマとなっている。例えば、購買履歴情報の分析において、購買動向のモデルの時間的な変化や、店舗ごとの購買動向の違いなどを知ることは、企業にとって死活問題である。このような問題を扱うため、一般的には、収集したデータストリームをいくつかのデータセットに分割し、各データセットについて何らかのモデル化を行う。そして時間的に隣接するモデル間の比較により、トレンドの変化の検出を行う。データマイニングの分野では、トレンドの変化は、コンセプトドリフトと呼ばれ、変化を検出するための技法が数多く提案されている。
【０００３】
非特許文献１及び２は、アンサンブル分類器を用いて、コンセプトドリフトをもつデータストリームを分析する技術を開示する。
【０００４】
非特許文献３は、動的に変化する決定木を用いる手法として知られているVFDT(Very Fast Decision Tree)とその評価結果を開示する。VFDTでは、データはノードを分割するごとに捨てられ、ストリームからの新たなデータを使ってその後の学習が行われる。
【０００５】
非特許文献４は、マルコフモデルを利用した過学習を防ぐ技術を開示する。
【０００６】
非特許文献５は、コンセプト間の類似性を判定する技術を開示する。ここでは新しく学習されたコンセプトとそれ以前のコンセプトとが用意され、現在のデータセットを使って両方のコンセプトに予測を行わせる。そして、予測した結果が一致した場合は＋１のポイントを与え、不一致の場合はー１のポイントを与える。データセットの全インスタンスについての合計ポイントが大きいほど、両コンセプトは類似していると判断される。
【０００７】
【非特許文献１】P. S. Yu, H. Wang, W. Fan and J. Han,“Mining concept-drifting data stream using ensemble classifiers.” inProceedings of the 9th ACMSIGKDD International Conference onKnowledge Discovery and Data Mining, pp.226-235, 2003年
【非特許文献２】K. Tumerand J. Ghosh, ”Error correlation and error reductionin ensemble classifiers.”, Connection Science, vol.8, pp.385-403, 1996年
【非特許文献３】P. Domingosand G. Hulten, ”Mining high-speed data streams.”, inSIGKDD, pp.71-80, 2000年
【非特許文献４】H. Wang, J. Yin, J. Pei, P. S. Yu and J. X. Yu, ”Suppressing model overfitting in mining concept-drifting data stream.” , inSIGKDD, pp.736-741, 2006年
【非特許文献５】Y. Yang, X. Wu and X. Zhu, “Combining proacive andreactive predictions for data streams.”, in Proceedingof the eleventh ACM SIGKDD international conference on Knowledge Discovery in DataMining, pp. 710-715, 2005年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記非特許文献１乃至５は、いずれも、コンセプトドリフトの有無を問題としている。即ち、上記非特許文献１乃至５は、どのようなコンセプトの変化があったのか、コンセプトドリフトの詳細を検討することについて言及するものではない。そこで、コンセプトドリフトの詳細を検討するために、説明能力が高いとされる決定木を分類器として利用することが考えられる。即ち、決定木の変化をコンセプトドリフトの変化とみなすのである。
【０００９】
しかし、一般にその木構造が互いに異なる２つの決定木の比較は難しい。また、例えば決定木を用いて非特許文献５に開示されるコンセプトの類似性の判断を行っても、決定木が提供し得る説明能力はポイントの合計値の中に隠蔽されてしまい、得られるのは結局コンセプトドリフトの有無の判別である。
【００１０】
この発明は、上記の問題点を解決するためになされたものであって、木構造の違いによらず、２つの決定木を詳細に比較する技術を提供することを目的とする。また、決定木の比較により、コンセプトドリフトの発生を詳細に検討するための技術を提供することを他の目的とする。
【課題を解決するための手段】
【００１１】
一般に決定木を使ってモデル化を行うと、その決定木に入力される複数のインスタンスは、それぞれ決定木のルートノードからスタートして、中間ノードを経て、最終的にいずれかのリーフノードに分類される。本発明では、このインスタンスの流れ、即ち、インスタンスの分布の様子がモデルを表していると考え、このインスタンスの分布の様子の違いによって、コンセプトドリフトの有無を判断する。ここで、各インスタンスは、分類や法則化を行う対象となる目的属性と、該目的属性の変動を説明する説明属性を有する。目的属性は、決定木を機械学習により生成するときに使われるもので、一般には複数の値を取ることが可能なものである。
【００１２】
例えば時系列データをいくつかのデータセットに分割し、各データセットから対応する決定木を生成するとする。そして、時系列の変化を捉えるという観点から、時刻Tのデータセットから生成した決定木と時刻T＋１のデータセットから生成された決定木を比較することを考える。上述したように、本発明では２つの決定木を比較するために、決定木同士を直接比較するのではなく、決定木を流れるインスタンスの様子を比較する。そのため本発明では、時刻Tのデータセットのインスタンスを、時刻T+1の決定木に入力として与え分類させる。
【００１３】
もし２つの決定木が同じ木構造を持っているならば、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と同じになるはずである。また、２つの決定木の木構造が一部異なる場合は、その異なる部分において、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と異なるはずである。そして２つの決定木が全く異なる木構造を持っている場合は、時刻Tのデータセットのインスタンスの分布の様子は、時刻T＋１のデータセットを入力とした場合のインスタンスの分布の様子と全く異なるはずである。
【００１４】
このように本発明では、比較する２つの決定木の一方の決定木を生成する基となったデータセットを、他方の決定木に入力として与えて分類させ、そのインスタンスが辿る様子を調べる。そして本発明では、インスタンスが辿る様子から、２つの決定木がどの部分でどの程度異なっているかを詳細に把握する。なお、一方の決定木のどのノードに分類されたインスタンスの集合も、他方の決定木の入力とすることができる。従って、一方の決定木の任意のノードが表すコンセプトについて、他方の決定木における変化を見ることが可能となる。
【００１５】
即ち、上記目的を達成する本発明に係る決定木比較装置は、複数のデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する、データセット格納部と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、複数の決定木のそれぞれの各ノードについて、上記決定木を生成する過程で上記ノードに分類されたインスタンスの数が最も多い目的属性の値を上記ノードの目的属性として決定する目的属性決定部と、複数の決定木のそれぞれの各ノードについて、上記決定木を生成する過程で上記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、上記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部から読み出す読出し部と、読み出した各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて、該ノードに分類され、かつ上記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、上記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を、２つの決定木の比較結果として出力する出力部とを含む。
【００１６】
好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を一定期間観測して得られた時系列データセットを所定時間間隔で分割して得られる複数のデータセットである。
【００１７】
また好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットである。
【００１８】
また好ましくは、上記データセット格納部に格納される複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットである。
【００１９】
また好ましくは、上記出力部は、関係情報として、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部を含む。
【００２０】
また好ましくは、上記出力部は、関係情報として、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する、第１決定木グラフ作成部を含む。
【００２１】
また好ましくは、上記出力部は、関係情報として、他方の決定木の各ノードを示す図形の色、模様及び形状の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標にノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する、第２決定木グラフ作成部を含む。
【００２２】
また好ましくは、複数の決定木は、所定の基準に従って順に並べることが可能であり、読出し部及び適用頻度算出部による処理は、所定の基準に従って複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われる。そして上記出力部は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、上記関係情報として、決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含む。なお、所定の基準は、決定木を生成する基となったデータセットの各要素であるインスタンスの属性、例えば、時間属性、場所属性、及び年代属性等に基づく基準であってよい。
【００２３】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のルートノードに分類された要素であるインスタンスの集合である。
【００２４】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のある中間ノードに分類された要素であるインスタンスの集合である。
【００２５】
また好ましくは、上記データセット格納部から読み出されたインスタンスの集合は、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるリーフノードに分類された要素であるインスタンスの集合である。
【００２６】
また、本発明に係る決定木比較装置は、ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する前記データセット格納部と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を上記ノードの目的属性として決定する目的属性決定部と、複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、上記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部から読み出す読出し部と、読み出した各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて、該ノードに分類され、かつ上記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、上記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に、他方の決定木の各ノードの基本頻度と適用頻度の各値をマップした２次元グラフを、２つの前記決定木の比較結果として出力する出力部とを含む。
【００２７】
以上、決定木比較装置として本発明を説明したが、本発明は、情報処理装置において実行される、決定木比較方法、及び決定木比較プログラムとして把握することもできる。
【発明の効果】
【００２８】
本発明によれば、同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有するインスタンスの異なる集合から生成された２つの決定木を、それら木構造の違いによらず、詳細に比較することが可能となる。即ち従来技術のように単に２つの決定木が異なるか否かというだけでなく、２つの決定木がどの部分でどの程度異なるのか、詳細にその違いを理解することが可能となる。
【００２９】
また、決定木の説明能力やその階層構造を利用することで、例えばルートノード近くにある判断ルールでは２つの決定木の間に変化は見られないが、ある中間ノードまで辿ると判断ルールに変化が見られる等、どのレベルのどの判断ルールに変化が生じたか、変化の詳細を知ることが可能となる。その結果として、コンセプトドリフトの発生の詳細を考察することが可能となる。本発明のその他の効果については、各実施の形態の記載から理解される。
【発明を実施するための最良の形態】
【００３０】
以下、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００３１】
本発明では、２つの決定木を比較するために、決定木同士を直接比較するのではなく、決定木を流れるインスタンスの様子を比較する。そのため本発明では、比較する２つの決定木の一方の決定木を生成する基となったデータセットを、他方の決定木に入力として与えて分類させる。そして、他方の決定木の各ノードについて、該ノードに分類される他方の決定木を生成する基となった本来のインスタンスの数と、該ノードに分類される一方の決定木を生成する基となったインスタンスの数とを比較する。
【００３２】
但し比較を適切に行うため、各ノードに分類されるインスタンス数の正規化を行う。正規化の具体的な方法は後述するが、正規化されたインスタンス数を以下では、他方の決定木を生成する基となった本来のインスタンスについては「基本頻度」と呼ぶ。また、一方の決定木を生成する基となったインスタンスについては、他方の決定木に適用するものであることから「適用頻度」と呼ぶ。決定木の各ノードはコンセプトとみなせるため、他方の決定木の各ノードに分類されるインスタンス数の変化、即ち他方の決定木の各ノードの基本頻度と適用頻度の違いが、コンセプトドリフトの有無を示すと考えることができる。以下では、本発明に係る決定木比較装置の機能構成を説明する。
【００３３】
図１は、本発明の一実施形態に係る決定木比較装置１００の機能構成の一例を示す図である。本発明の実施形態に係る決定木比較装置１００は、データセット格納部１１０、決定木情報格納部１１５、目的属性決定部１２０、基本頻度算出部１２５、読出し部１３０、適用頻度算出部１３５、出力部１４０を含む。
【００３４】
データセット格納部１１０は、複数のデータセットを格納するデータセット格納部である。ここで、各データセットの要素であるインスタンスは、各々、同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する。好ましくは、複数のデータセットは、ある事象を一定期間観測して得られた時系列データを、所定時間間隔で分割して得られる複数のデータセットである。あるいは、複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットであってもよい。更には、複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットであってもよい。
【００３５】
本実施例に係る複数のデータセットは、ある事象を一定期間観測して得られた時系列データを、所定時間間隔で分割して得られる複数のデータセットD(1),D(2),…,D(N)であるとする。また、データセットの要素であるインスタンスを次のように定義する。X={x1,x2,…,xn,y}。即ち、本実施例に係るインスタンスは、１つの目的属性yと、n個の説明属性xiを有するとする。なお、目的属性は複数の値を取ることが可能であるが、説明を簡単にするため本実施例に係る目的属性はyesとnoのいずれか一方の値を取るものとする。
【００３６】
図２(a)に、データセット格納部１１０に格納される、任意のデータセットのテーブルの一例を示す。図２(a)に示す例では、説明属性xiの数はdata0、data1、data2、data3の４つであり、目的属性ｙは上述したとおりyesとnoのいずれか一方の値を取る。なお、本実施例では、データセット毎にテーブルを設ける構成としたが、かかる構成に限定されず、例えばデータセットIDの欄を設けることにより、１つのテーブルに全てのデータセットを格納する構成を採用してもよい。また、１つのデータセットに含まれるインスタンスの数は任意である。
【００３７】
決定木情報格納部１１５は、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する。なお以下では、複数の決定木をM(1), M(2), …, M(N)と表記する。ここで任意の決定木M (i)はデータセットD(i)に対応する。即ち、決定木M(i)はデータセットD(i)から生成されたものである。なお、決定木の生成方法は公知であり、一例として、C4.5の決定木生成アルゴリズムを実装したWekaのJ48を利用することができる。
【００３８】
図２(b) 及び(c)に、図２(a)を参照して説明したのと同じ構造をもつデータセットから生成された決定木のグラフの一例を示す。図２(b)は、時刻TのデータセットD(i)から生成された決定木M(i)である。また、図２(c)は、時刻T+1のデータセットD(i+1)から生成された決定木M(i+1)である。いずれの図においても、ノードを示す円の中の数字はノードIDを示す。また、ノードとノードを結ぶエッジの横に記載する式は、上位のノードから下位のノードへ分類されるための条件式、すなわち判断ルールである。例えば、図２(b)において、あるインスタンスがルートノードのノードID=0からノードID=1に分類されるためには、その説明属性data0の値がA1である必要がある。このdata0=A1が、ノードID=0からノードID=1に分類されるため判断ルールである。
【００３９】
また、図２(b)及び(c)に示されるような決定木は、一例として図３及び図４に示すようなテーブル構造により決定木情報として決定木情報格納部１１５に格納される。図３は時刻Tの決定木M(i)の、図４は時刻T+1の決定木M(i+1)の決定木情報の一例を示す。本実施例では、決定木は、決定木の階層ごとに用意されたテーブルにその情報を登録される。そこで次に図３を参照して、決定木情報格納部１１５に格納される決定木情報を具体的に説明する。図４については、図３と同じであるためその説明を省略する。
【００４０】
図３(a)は、時刻Tの決定木M(i)のルートノードのテーブルの一例を示す。いずれの階層のテーブルも、「テーブル名」、「ノードID」、「判断ルール」、「目的属性」、「基本インスタンス」、「下位層テーブル名」の各フィールドを有する。ここで「判断ルール」フィールドには、該ノードに分類されるための判断ルールが登録される。しかしルートノードは全てのインスタンスが入力される出発地点であるため、図３(a)に示すテーブルでは該フィールドは空欄となる。「目的属性」及び「基本インスタンス」の各フィールドについては後述する。「下位層テーブル名」フィールドには、当該ノードが属する階層より１つ下の階層のテーブル名が登録される。従って、決定木をルートノードからリーフノードまで順に辿っていくには、現在のノードの「下位層テーブル名」フィールドの値を参照し、その値を「テーブル名」フィールドに有するテーブルを取得するという操作を繰り返せばよい。
【００４１】
図３(b)は、時刻Tの決定木M(i)のルートノードより１つ下の階層に属するノード群のテーブルの一例を示す。図２(b)から分かるように、ルートノードの下にはノードID=1〜5の５つのノードが存在する。従って、図３(b)に示す第１テーブルには、この５つのノードの情報が登録される。また、図２(b)から分かるように、ノードID=1〜5の５つのノードのうち子ノードをもつのはノードID=3のノードみである。従って、第１テーブルの「下位層テーブル名」フィールドは、ノードID=3のエントリのみ値（第２テーブル）が登録され、他のノードIDのエントリの同フィールドは空欄となる。
【００４２】
図３(c)は、時刻Tの決定木M(i)のノードID=3のノードより１つ下の階層に属するノードのテーブルの一例を示す。図２(b)から分かるように、ノードID=3のノードの下にはノードID=6〜10の５つのノードが存在する。従って、図３(c)に示す第２テーブルには、この５つのノードの情報が登録される。また、図２(b)から分かるように、ノードID=6〜10の５つのノードはいずれも子ノードをもたない。従って、第２テーブルの「下位層テーブル名」フィールドは、いずれのノードについても空欄となる。
【００４３】
目的属性決定部１２０は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、該ノードに決定木を生成する過程で分類されるインスタンスの数が最も多い目的属性の値を、そのノードの目的属性として決定する。即ち、目的属性決定部１２０は、処理対象の決定木に、該決定木を生成する基となったデータセットを入力として分類させる。そして、目的属性決定部１２０は、決定木の各ノードについて、該ノードを経由するインスタンスの数をインスタンスの目的属性の値別にカウントし、カウントしたインスタンスの数が最も大きい目的属性の値を、そのノードの目的属性として決定する。決定された各ノードの目的属性の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。なお、ノードの目的属性は、詳細は後述するが、基本頻度及び適用頻度を算出する際に利用される。
【００４４】
図２(b)及び図３に示す時刻Tの決定木M(i)を例に、ノードの目的属性を決定する方法を具体的に説明する。図３を参照して説明したように、決定木情報の各テーブルには、「基本インスタンス」の「yes 」と「no」のフィールド、及び「目的属性」のフィールドが用意されている。「yes」のフィールドには、該ノードを経由するインスタンスであって、目的属性がyesであるインスタンスの数が登録される。同様に、「no」のフィールドには、該ノードを経由するインスタンスであって、目的属性がnoであるインスタンスの数が登録される。そして「目的属性」のフィールドには、該ノードに対して決定された目的属性が登録される。図３ (a)のルートノードのテーブルの場合、「yes」のフィールドは４１の値が、「no」のフィールドには５９の値が登録されている。従って、ルートノードの目的属性は、インスタンス数が最も多い目的属性の値noが登録される。図３ (b)、(c)の残りのテーブル、及び図４の全テーブルについても、同様にして目的属性の値が登録される。
【００４５】
基本頻度算出部１２５は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて基本頻度を算出する。ここで、ノードの基本頻度は、該ノードに決定木を生成する過程で分類された１以上のインスタンスのうち、該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、該ノードに分類された全インスタンスの数で割った値として定義される。算出された各ノードの基本頻度の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。
【００４６】
図２(b)及び図３に示す時刻Tの決定木M(i)を例に、ノードの基本頻度の算出方法を具体的に説明する。図３の各テーブルの「目的属性」フィールド、及び「基本インスタンス」フィールドの「yes 」と「no」の各フィールドには、既に値が登録されているものとする。基本頻度算出部１２５は、各テーブルのエントリ毎に次の処理を行う。基本頻度算出部１２５はまず、「yes 」フィールドと「no」のフィールドの値を足し合わせてその合計を求める。そして、「yes 」及び「no」の各フィールドのうち、「目的属性」フィールドの値に等しい方のフィールドの値を、先に求めた合計で割ることにより、ノードの基本頻度を算出する。例えば、図３(b)のノードID=1のノードの場合、目的属性はNOであることから、「no」フィールドの値14を、「yes 」フィールド及び「no」フィールドの値の和16で割って、ノードID=1のノードの基本頻度0.875を算出する。算出された基本頻度の値は、基本インスタンスの「基本頻度」フィールドに登録される。
【００４７】
読出し部１３０は、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合をデータセット格納部１１０から読み出す。ここで、一方の決定木のあるノードとは、一方の決定木の任意のノードであってよく、即ち、ルートノード、中間ノード、リーフノードのいずれであってもよい。即ち、読出し部１３０は、一方の決定木を生成する基となったデータセットのインスタンスの集合のうち、他の決定木における変化を調べることを希望するコンセプトを表すノードに分類されるインスタンスの集合をデータセット格納部１１０から読み出す。
【００４８】
ノードの選択は、マウスやキーボード等の入力デバイスによりユーザによって指定されてもよく、或いはデフォルトとして、ルートノードを予め指定し、または全ノードが順次読み出し部１３０により選択されるよう設定しておいてもよい。なお本実施例では、比較する２つの決定木は、時刻Tの決定木M(i)と時刻T+1の決定木M(i+1)である。そこで、図２及び図３を参照して、読出し部１３０によるデータセット格納部１１０からのインスタンスの読出し方法の一例を具体的に説明する。
【００４９】
例えば、比較対象のノードとして、時刻Tの決定木M(i)のノードID=10のノードが選択されたとする。この場合、時刻T+1の決定木M(i+1)への入力とするため、時刻Tの決定木M(i)を生成する基となったインスタンスの集合のうち、ノードID=10のノードに分類されたインスタンスの集合をデータセット格納部１１０から読み出す必要がある。そのためにまず、決定木情報格納部１１５に格納される、時刻Tの決定木M(i)に対応する複数のテーブルから、「ノードID」フィールドの値が10であるエントリを読出し、「判断ルール」フィールドの値data2=C5と「テーブル名」フィールドの値第２テーブルを抽出する。
【００５０】
次に、時刻Tの決定木M(i)に対応する複数のテーブルから、「下位層テーブル名」フィールドの値が第２テーブルであるエントリを読出し、該エントリの「判断ルール」フィールドの値data0=A3と「テーブル名」フィールドの値第１テーブルを抽出する。かかる処理を、「判断ルール」が読み出せなくなるまで、またはテーブル名がルートノードのテーブルであることを示すまで繰り返す。最後に、それまで読み出した判断ルールを全て満たすインスタンスを、即ち上記例ではdata2=C5かつdata0=A3を満たす全てのインスタンスを、データセット格納部１１０の時刻Tの決定木M(i)に対応するデータセットから読み出す。読み出されたインスタンスの集合は、時刻Tの決定木M(i)を生成する基となったインスタンスの集合のうち、ノードID=10のノードに分類されたインスタンスの集合である。
【００５１】
適用頻度算出部１３５は、読出し部１３０により読み出された各インスタンスを他方の決定木に分類させ、他方の決定木の各ノードについて適用頻度を算出する。ここで各ノードの適用頻度は、読出し部１３０により読み出された複数のインスタンスのうち、該ノードに分類され、かつ該ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、該ノードに分類される全インスタンスの数で割った値として定義される。算出された各ノードの適用頻度の値は、対応する決定木の対応するノードに関連付けて、決定木情報格納部１１５に保持される。
【００５２】
次に、具体例を用いてノードの適用頻度の算出方法の一例を説明する。ここでは、図２(b)に示す時刻Tの決定木M(i)を生成する基となったインスタンスであって、かつ時刻Tの決定木M(i)のノードID＝５のノードに分類されたインスタンスの集合Mを、図２(c)に示す時刻T+1の決定木M(i+1)の入力として分類する場合を考える。まず、図４(a)、(b)、(c)、(d)に示す時刻T+1の決定木M(i+1)の各テーブルに、新たに「適用インスタンス」のフィールドを追加して各テーブルを更新する。「適用インスタンス」フィールドは、「yes」、「no」、及び「適用頻度」の各フィールドを有し、いずれも初期値として０を設定する（図５(a)、(b)、(c)、(d)を参照）。
【００５３】
次に集合Mから１つインスタンスを取り出し、時刻T+1の決定木M(i+1)のルートノードに入力する。そして、入力したインスタンスが時刻T+1の決定木M(i+1)のいずれかのノードを経由する度、その経由されたノードの「適用インスタンス」フィールドの「yes」及び「no」フィールドのうち、入力インスタンスの目的属性の値と同じフィールドの方の値を１増加する。これを集合Mの全インスタンスに対して行う。
【００５４】
例えば入力インスタンスが、data0=A1, data2=C3, YESの属性値を有するとする。まず、第２ルートノード・テーブルを取得して、「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(a)参照）。次に、第２ルートノード・テーブルの「下位層テーブル名」フィールドの値を参照して、１つ下の階層のテーブル、第３テーブルを取得する（図５(b)参照）。そして、第３テーブルから、入力インスタンスがその判断ルールを満たすエントリを検索し、検索したエントリ、即ちノードID=3の「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(b)参照）。
【００５５】
次に、ノードID=3の「下位層テーブル名」フィールドの値を参照して、１つ下の階層のテーブル、第５テーブルを取得する（図５(d)参照）。そして、第５テーブルから、入力インスタンスがその判断ルールを満たすエントリを検索し、検索したエントリ、即ちノードID=11の「適用インスタンス」フィールドの「yes」フィールドの値を１増分する（図５(d)参照）。
【００５６】
集合Mの全インスタンスについて上述した一連の処理を終えると、適用頻度算出部１３５は、図５(a)、(b)、(c)、及び(d)の各テーブルのエントリ毎に次の処理を行う。即ち、まず「適用インスタンス」フィールドの「yes 」フィールド及び「no」のフィールドの値を足し合わせてその合計を求める。そして、「適用インスタンス」フィールドの「yes 」及び「no」の各フィールドのうち、「目的属性」フィールドの値に等しい方のフィールドの値を、先に求めた合計で割ることにより、ノードの適用頻度を算出する。算出された基本頻度の値は、「適用インスタンス」フィールドの「適用頻度」フィールドに登録される。
【００５７】
出力部１４０は、２つの決定木、即ち一方の決定木と他方の決定木の比較結果として、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を出力する。好ましくは、出力部１４０は、関係情報として、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部１４５を含む。これに代えて出力部１４０は、関係情報として、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する、第１決定木グラフ作成部１５０を含んでもよい。
【００５８】
あるいは出力部１４０は、関係情報として、他方の決定木の各ノードを示す図形の色、模様、及び形状の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に上記ノードの基本頻度と適用頻度の値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する、第２決定木グラフ作成部１５５を含んでもよい。更に出力部１４０は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含んでもよい。
【００５９】
この場合、読出し部１３０及び適用頻度算出部１３５による処理は、所定の基準に従って複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われる。なお、所定の基準に従って複数の決定木を並べるとは、例えば決定木を生成する基となったデータセットが時系列データを分割したものである場合は、複数の決定木を時間順に並べることを意味する。同様に、決定木を生成する基となったデータセットが年代別の複数のデータセットである場合は、複数の決定木を年代順に並べることを意味する。また、決定木を生成する基となったデータセットが場所別の複数のデータセットである場合は、複数の決定木を場所の近い順に並べることを意味する。以下では、第１の２次元グラフ作成部１４５、第１決定木グラフ作成部１５０、第２決定グラフ木作成部１５５、及び第２の２次元グラフ作成部１６０により作成されるそれぞれのグラフを順に説明する。
【００６０】
図６は、第１の２次元グラフ作成部１４５により作成される第１の２次元グラフの一例を示す。ここで、X軸は基本頻度、Y軸は適用頻度を表す。図６を参照して、２次元座標にマップされるデータの分布から、一方の決定木と他方の決定木の間にどのようなコンセプトドリフトが起きているかを読み取る方法を以下に説明する。まず、一方の決定木は、時刻Tのデータセットから生成されたものとし、そのノードの数をmとする。また、他方の決定木は、時刻T+1のデータセットから生成されたものとし、そのノードの数をnとする。そして、時刻Tの決定木のノードID＝j（jは0からm-1の整数）のノードに分類されたインスタンスの集合を、時刻T+1の決定木に入力として与え分類させたとする。このとき、目的属性がyesとnoいずれか一方の値をとる本実施例においては、他方の決定木のノードID=i（iは0からn-1の整数）のノードの基本頻度をx(i)とすると、0.5≦x(i)≦1が成り立つ。
【００６１】
これは、目的属性と基本頻度x(i)の定義から明らかである。即ち、ノードの目的属性は、該ノードに決定木を生成する過程で分類されるインスタンスの数が最も多い目的属性の値である。また、ノードの基本頻度は、該ノードに決定木を生成する過程で分類された１以上のインスタンスのうち、該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、該ノードに分類された全インスタンスの数で割った値である。
【００６２】
一方、時刻T+1の決定木のノードID=iのノードの適用頻度をy(j,i)とすると、0≦y(j,i)≦1が成り立つ。これは、時刻T+1の決定木の各ノードの適用頻度は、時刻Tの決定木のあるノードに分類されたインスタンスの集合を入力とし分類させた場合に、該ノードに分類され、かつ該ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、該ノードに分類される全インスタンスの数で割った値であるということから、明らかである。即ち本発明では、時刻T+1の決定木への入力として、時刻T+1の決定木を生成する基となったインスタンスの集合を入力する場合と、時刻Tの決定木を生成する基となったインスタンスの集合を入力する場合とで、インスタンスの頻度の計算が同じ目的属性について行われるよう、基本頻度及び適用頻度を定義している。
【００６３】
（コンセプトの持続）時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、入力されたインスタンスの集合が時刻T+1の決定木のあるノードに分類される場合がある。このようなケースは、時刻Tの決定木のあるノードに分類された各インスタンスとそれぞれ同じ属性を有するインスタンスの集合が時刻T+1においても存在し、該インスタンスの集合によって、時刻T+1の決定木が、時刻Tの決定木のあるノードに相当するあるノードを持つ場合に起こると考えられる。
【００６４】
この場合、時刻Tの決定木のあるノードにより表されるコンセプトは、時刻T+1において持続しているといえ、また時刻T+1の決定木のあるノードの基本頻度と適用頻度の値はほぼ同じになる。従って、コンセプトドリフトが全く起こっていない場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=X上に分布すると言える（図６の番号２０５参照）。逆に、時刻T＋１の決定木のあるノードの基本頻度と適用頻度の値が、Y=X上にマップされない場合、当該ノードではコンセプトドリフトが起きていると言える。以下に、コンセプトが継続しない場合を更に場合分けして詳細に説明する。
【００６５】
（コンセプトの消滅）時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、インスタンスの集合が時刻T+1の決定木のノード全体に散らばる場合がある。この場合は、時刻Tにおいて存在していたコンセプトが、時刻T+1では失われてしまい、特定のコンセプトとして同定できなくなったと解釈できる。つまり、時刻T+1の決定木がそのインスタンスの集合を説明する能力を失っている場合には、インスタンスの集合は時刻T+1の決定木の各ノードに約1/2の割合で散らばっていくと考えられる。従って、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において消滅している場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=0.5上に分布する（図６の番号２１０参照）。
【００６６】
（コンセプトの絞込み）次に時刻Tの決定木のあるノードに分類されたインスタンスの集合を時刻T+1の決定木に与えた場合に、時刻T＋１の決定木のいくつかのノードの基本頻度と適用頻度の値が、Y=１上にマップされる場合を考える。この場合は、時刻Tのインスタンスの一部が絞込みを受けて時刻T+1のあるノードの条件を満たすインスタンスのみが、時刻T+1のノードに集中する場合である。それがY=1上にマップされたと考えることができる。従って、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において絞込みを受けた場合、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の値は、Y=1上に分布する（図６の番号２１５参照）。
【００６７】
（新しいコンセプトの出現）時刻Tの全インスタンスを時刻T＋１の入力としても、時刻T＋１の決定木のノードの中に辿られない、あるいはほとんど辿られないノードが存在し得る。このような場合には、時刻Tのインスタンスでは表現されていなかった新しいノードが時刻T+1で発生していると考えられる。従って、時刻T+1で新たに発生した各ノードの基本頻度と適用頻度の値は、Y=0上に分布する（図６の番号２２０参照）。なお、時刻Tのあるノードに分類されたインスタンスの集合を時刻T＋１の入力とした場合にも、時刻T＋１の決定木のノードの中に、辿られない、あるいはほとんど辿られないノードが存在し得る。しかしこの場合は、入力が、時刻Tの決定木のあるノードによって表されるコンセプトに制限されたためと考えるのが適当である。従って、時刻T+1の決定木において新しいコンセプトが発生しているか否かを判断するためには、時刻Tの決定木を生成する基となった全インスタンスを入力する必要がある。
【００６８】
なお、上記説明した２つの決定木の比較を利用することにより、決定木のあるノードに分類されるインスタンスが少ない場合に、当該インスタンスが誤差であるのか、またはコンセプトドリフトがピンポイントで発生していることを示すのか、見分けることが可能となる。このことを、具体例を用いて説明する。時刻Tの決定木において、２つのインスタンスが同じ１つのノードに分類されているとする。但し、２つのインスタンスは互いに異なる目的属性を有するとする。この場合、そのノードは説明能力を持っておらず、通常は２つのインスタンスはノイズであると解釈される。しかし、この２つインスタンスを時刻T+1の決定木に与え分類させた場合に、一方のインスタンスが当該インスタンスのみを含むノードに分類されたとする。この場合は、そのノードは明らかに説明能力があり、そのインスタンスは誤差ではなく、コンセプトドリフトがピンポイントで発生していることを示していることが分かる。
【００６９】
次に図２乃至図５に示した時刻Tと時刻T+1の決定木を比較した場合を例に、第１の２次元グラフ作成部１４５より作成される２次元グラフを説明する。先に図２乃至図５に示される時刻Tと時刻T+1の決定木をそれぞれ生成する基となった人工データの生成方法をここで説明しておく。本実施例では、図２(a)に示されるようなデータセットを、moving hyper planeと呼ばれるシミュレーション手法により作成した（非特許文献１及び４参照）。
【００７０】
本シミュレーション手法では、d次元空間上（本実施例ではd=4）に一様分布するデータをデータセットの各インスタンスとみなす。データはベクトルとして表され、その成分はそれぞれランダムな値（x1、x2、x3、x4）を取り、それぞれ説明属性data0、data1、data2、data3の値を示すものとする。なお、説明を容易にするため、本実施例では４次元空間の各軸をそれぞれ５つの領域[0, 0.2]、[0.2, 0.4]、[0.4, 0.6]、[0.6, 0.8]、[0.8, 1.0]に分割し、軸ごと各領域に１つの値を割り当てる。
【００７１】
即ち、data0の場合、上記５つの領域に対して順に’A1’、 ’A2’、 ’A3’、 ’A4’、 ’A5’の値を割り当てる。同様に、data1の場合、上記５つの領域に対して順に’B1’、 ’ B 2’、 ’ B 3’、 ’ B 4’、 ’ B 5’の値を割り当てる。同様に, data2の場合、上記５つの領域に対して順に’C1’、 ’ C 2’、 ’ C 3’、 ’ C 4’、 ’ C 5’の値を割り当てる。同様に, data3の場合、上記５つの領域に対して順に’D1’、 ’ D 2’、 ’ D 3’、 ’ D 4’、 ’ D 5’の値を割り当てる。従って、x1成分が[0, 0.2]の範囲の値をとるデータの場合、該データの説明属性data0の値はA1となる。また、x2成分が[0.6, 0.8]の範囲の値をとるデータの場合、該データの説明属性data1の値はB4となる。
【００７２】
一方、データの目的属性の値は、ベクトル長Σaixi(ここでΣは、添え字i=1〜4の総和を示す）により決定される。ここでaiは、該データの成分xiの重みであり、ランダムな値を取る。Σaixi= a0により決定されるhyper planeは4変数xiが作る4次元の空間に対して、一つの条件式を与えている。したがって
Σaixi= a0を満たす４変数xiは一つ次元が少ない3次元 hyper planeを表す。4次元空間が一つの3次元空間を挟んで二つの部分空間に分離されることになる。その二つの空間はそれぞれ、Σaixi< a0とΣaixi> a0で表すことが出来る。その二つの部分空間にYesとNoを割り振る。これを次元の少ない簡単な2次元の例で説明する。2次元空間に一つの条件式a1x1+a2x2=a0を与えることで、一次元の直線を定義することが出来る。2次元空間は1次元空間の直線で二つの半平面に分割されることになる。その2つの半平面は
a1x1+a2x2<a0とa1x1+a2x2> a0を満たす領域として定義できる。そしてその二つの領域にそれぞれYes Noを割り振ることになる。
【００７３】
目的属性の値は、ベクトル長Σaixiが所定の値a0よりも小さい場合はyesを、それ以外の場合はnoをとるとする。なお、所定の値a0はhyper planeが空間を２分するよう、a0=(1/2)Σai(ここでΣは、添え字i=1〜4の総和を示す）と定義する。かかる定義により、データの約半分が、目的属性をyesとし、残り半分が目的属性をnoとする。所定の値a0は、hyper planeの動きによって変化し、従って、hyper planeを動かすことでコンセプトドリフトの発生をシミュレーションすることが可能となる。hyper planeを動かしながら、時系列データを取得し、時系列データを１００件単位でデータセットに分割する。なお本実施例では、データ全体に対して５％の誤差を入れている。
【００７４】
このようにして作成した人工データを用いて生成された時刻Tの決定木が図２(b)及び図３に示される決定木であり、時刻T+1の決定木が図２(c)、図４及び図５に示される決定木である。まず初めに、時刻Tの決定木のルートノードに分類されるインスタンスの集合、即ち、時刻Tの全インスタンスを、時刻T+1の決定木の入力として２つの決定木を比較した場合に得られる２次元グラフを図７(a)に示す。図７(a)のグラフ中示される番号は、時刻T+1の決定木のノードIDを表している。
【００７５】
図７(a)を見ると、Y=X上またはその周辺にマップされているノードが存在することが分かる（ノードID=0,1,2,4,5,14)。これらノードについては、時刻Tと時刻T+1の間でコンセプトが継続しているといえる。一方その他のノードについては、いずれもコンセプトドリフトが起きているといえる。特に、Y=0上にマップされているノードについては（ノードID=3,7,9〜13)、時刻Tのインスタンスが全く辿り着いていないことから、いずれも時刻T+1において新たに生じたコンセプトを示すノードであるといえる。
【００７６】
次に、時刻Tの決定木のノードID=5のリーフノードに分類されるインスタンスの集合を、時刻T+1の決定木の入力として２つの決定木を比較した場合に得られる２次元グラフを図７(b)に示す。図７(a)と同様に、図７(b)のグラフ中示される番号は、時刻T+1の決定木のノードIDを表している。図７(b)をみると、時刻T+1のノードID=8のノードのデータから、時刻Tの決定木のノードID=5のリーフノードに分類されるインスタンスの一部が絞込みを受けてY=1上にマップされているのが分かる。即ち、(0.5,1)にマップされる時刻T+1のノードID=8のノードは、時刻Tにおいてもっていた説明能力を時刻T+1において失っており、ノードID=8のノードにおいて絞込みのコンセプトドリフトが起きていることが分かる。
【００７７】
次に第１決定木グラフ作成部１５０及び第２決定木グラフ作成部１５５がそれぞれ作成するグラフを、図８に示す決定木を例として説明する。図８(a)及び(b)は、天気と気温によってテニスを行うかどうかを決める決定木を示す。図８(a)に示す時刻Tの決定木は、季節が秋のときに得られたデータセットから生成された決定木である。一方図８(b)に示す時刻T+1の決定木は、季節が冬のときに得られたデータセットから生成された決定木である。いずれの図においても、ノードを示す円の中の数字はノードIDを示す。また、ノードID=0のノード近くに記載される「Yes, 10/2, 0.8」において、「Yes」はノードの目的属性を示す。また、「10/2」は、該ノードに分類された全インスタンス数/ノードの目的属性と異なる目的属性を有するインスタンス数を示す。更に「0.8」は、式 (10-2)/10より求められる該ノードの基本頻度を示す。他のノードについても同様である。
【００７８】
ここで、本発明の比較方法を用いて時刻Tと時刻T+1の決定木を比較してみる。即ち、時刻Tの決定木のノードID=0のルートノードに分類されるインスタンスを時刻T+1の決定木に与えて分類させる。その結果を図８(c)に示す。図８(c) においても、ノードを示す円の中の数字はノードIDを示す。また、ノードID=0のノード近くに記載される「Yes, 10/2, 0.8」において、「Yes」はノードの目的属性を示す。また、「10/2」は、該ノードに分類された全インスタンス数/ノードの目的属性と異なる目的属性を有するインスタンス数を示す。更に「0.8」は、式(10-2)/10より求められる該ノードの適用頻度を示す。図８(b)と図８(c)を比較することで、時刻T+1の冬のデータセットの各インスタンスと時刻Tの秋のデータセットの各インスタンスが、それぞれ時刻T+1の決定木を辿る様子を見比べることができる。
【００７９】
比較の結果、ノードID=0〜3のノードでは、基本頻度と適用頻度が同じであることからコンセプトドリフトは起きていないことが分かる。一方、ノードID=4のノードでは、基本頻度と適用頻度が異なっていることから、コンセプトドリフトが起きていることが分かる。この様子を上述した第１の２次元グラフ作成部１４５により作成される２次元グラフで表したものを図９に示す。図９をみると、ノードID=0〜3のノードのデータはY=X上にマップされていることから、これらノードではコンセプトドリフトは起きていないことが分かる。一方、ノードID=4のノードのデータはY=Xの直線から外れていることから、該ノードではコンセプトドリフトが起きていることが分かる。
【００８０】
しかしながら、図９に示す２次元グラフでは、階層構造をもつ決定木のどの階層レベルでコンセプトドリフトが起きているかを知ることは難しい。そこで、第１決定木グラフ作成部１５０は、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフを作成する。図１０(b)に、上記様子を第１決定木グラフ作成部１５０が作成する決定木のグラフにより表したものを示す。但し、図１０(b)では、基本頻度と適用頻度が等しい場合のノードの大きさをゼロとせず、他のどのノードよりも小さい所定の大きさをもつノードとして表している。図１０(b)によれば、ノードID=2のノードレベルまではコンセプトドリフトは起きておらず、その下のより詳細な判断ルールで指定されるノードID=4においてコンセプトドリフトが起きていることが分かる。
【００８１】
このように、第１決定木グラフ作成部１５０が作成する決定木のグラフによれば、コンセプトドリフトが起こっている場合に、決定木のもつ階層構造のどのレベルでコンセプトドリフトが起こっているか、また、どの程度の大きさのコンセプトドリフトが起こっているのか、コンセプトドリフトの内容を詳細に知ることが可能となる。なお、決定木のノードを表す図形の大きさに代えて、決定木のノードを表す図形の色、模様、形状等を利用して、コンセプトドリフトの内容の詳細を視覚的に表すことも可能である。第２決定木グラフ作成部１５５は、決定木の各ノードを示す図形の色、模様、形状の少なくとも１つが、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標にノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフを作成する。本実施例に係る第２決定木グラフ作成部１５５は、決定木のノードを示す図形の色及び模様を利用する。
【００８２】
図１０(a)に、第２決定木グラフ作成部１５５が利用する、X軸を基本頻度及びY軸を適用頻度とした２次元座標の領域の色分けの一例を示す。領域の色分けは、該領域にマップされるノードについて起きているとされるコンセプトドリフトの種類に基づいて行う。図６を参照して説明したように、時刻T＋１の決定木の各ノードの基本頻度と適用頻度の各値は、２次元座標の0.5≦X≦1かつ0≦Y≦1の範囲内にマップされる。
【００８３】
コンセプトドリフトが全く起きていない場合、各ノードの基本頻度と適用頻度の値は、Y=X上に分布する。そこで、図１０(a)に示す例では、|Y-X|<h、X=0.5、X=1、Y=1で囲まれた領域を白で色分けする。そして、決定木のグラフにおいてノードの色が白の場合、該ノードではコンセプトドリフトが起こっていないことを示すようにする。なお、上記定義された領域の境界のうち境界値Y=X-h 及びY=X+hは、この領域に含まれないものとする。
【００８４】
また、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において消滅している場合、時刻T+1の決定木のいくつかのノードの基本頻度と適用頻度の値は、Y=0.5上に分布する。そこで、図１０(a)に示す例では、Y=0.5、Y=X-h、X=1で囲まれた領域を緑で色分けする。これにより、決定木のグラフにおいてノードの色が緑の場合、該ノードではコンセプトが消滅していることを示すようにする。なお、上記定義された領域の境界値Y=0.5、Y=X-h、X=1は全てこの領域に含まれるものとする。
【００８５】
また、時刻Tの決定木のあるノードによって表されるコンセプトが時刻T+1において絞込みを受けた場合、時刻T＋１の決定木のいくつかのノードの基本頻度と適用頻度の値は、Y=1上に分布する。そこで、図１０(a)に示す例では、Y=1、Y=X+h、X=0.5で囲まれた領域を青で色分けする。そして、決定木のグラフにおいてノードの色が青の場合、該ノードではコンセプトの絞込みがあったことを示すようにする。なお、上記定義された領域の境界値Y=1、Y=X+h、X=0.5は全てこの領域に含まれるとする。
【００８６】
更に、時刻T+1で新たなコンセプトが現れた場合、該コンセプトを表す時刻T+1の決定木の新たに追加された各ノードの基本頻度と適用頻度の値は、Y=0上に分布する。そこで、図１０(a)に示す例では、Y=0.5、Y=X-h、X=1、X=0.5, Y=0で囲まれた領域を赤で色分けする。そして、決定木のグラフにおいてノードの色が赤の場合、該ノードが示すコンセプトは時刻T+1で新しく発生したものであることを示すようにする。なお、上記定義された領域の境界のうち境界値Y=0.5は、この領域に含まれないものとする。なお図１０(a)に示す色分けはあくまでも説明のための一例であり、色分けの境界は図１０に示す例に限定されないことに留意されたい。
【００８７】
図１０(b)はまた、図８(b)と図８(c)の比較結果の様子を、第２決定木グラフ作成部１５５が図１０(a)に示す色分けを利用して作成した決定木のグラフでもある。このように、第２決定木グラフ作成部１５５が作成する決定木のグラフによれば、コンセプトドリフトが起こっている場合に、決定木のもつ階層構造のどのレベルで、どのような種類のコンセプトドリフトが起こっているか、コンセプトドリフトの内容を詳細にかつ視覚的に知ることが可能となる。
【００８８】
次に第２の２次元グラフ作成部１６０が作成するグラフを、図１１乃至図１３を参照して説明する。図１１(a)、(b)及び 図１２(a)、(b)に示す各２次元グラフは、上述した第１の２次元グラフ作成部１４５により作成されたグラフである。それぞれの２次元グラフで比較されている２つの決定木は、上述したmoving hyper planeにより生成した人工の時系列データを複数に分割してできたデータセットを基にそれぞれ生成された、時間的に隣接した２つの決定木である。
【００８９】
即ち、図１１(a)の２次元グラフは、時刻T=0とT=1の決定木を比較して得られた２次元グラフである。同様に、図１１ (b) の２次元グラフは、時刻T=1とT=2の決定木を、図１２ (a) の２次元グラフは、時刻T=2とT=3の決定木を、図１２ (b) の２次元グラフは、時刻T=3とT=4の決定木を、それぞれ比較して得られた２次元グラフである。いずれにおいても、先の時刻の決定木のルートノードに分類されたインスタンスの集合を、後の時刻の決定木の入力としている。
【００９０】
これら４つの２次元グラフを見比べると、２つのタイプの２次元グラフがあることに気づく。１つは図１２(a)のグラフが示す２次元グラフである。即ち図１２ (a)のグラフには、Y=０上に分布するデータが複数観察される。特に、(X,Y)=(1,0)の点には複数のデータが重なってか表示されており、この点がコンセプトドリフトの発生を表している。もう１つは、図１１(a)、(b)及び 図１２ (b)のグラフが示す２次元グラフである。これらグラフでは、Y=XまたはY=0.5の近くにデータが集まっている様子が見られる。従って、これら２次元グラフの各々におけるデータの分布、偏りから、コンセプトドリフトは時刻T=3で起きたことが分かる。実際、人工の時系列データは、時刻T=3においてコンセプトドリフトが発生するよう生成したものである。
【００９１】
このように第１の２次元グラフ作成部１４５により作成される２次元グラフにおけるデータの分布、偏り具合を検討することで、コンセプトドリフトが発生した時間を見つけることができる。しかしながら、時系列に並んだ２次元グラフの数が増えると、その作業も容易ではなくなる。そこで、本発明では、このような２次元グラフにおけるデータの偏りを、分散を使って表す。ここで平均はY-Xに対して定義する。なぜならば、Y-Xは決定木の各ノードの基本頻度と適用頻度の差を表しており、まさのその差がコンセプトドリフトの大きさを表すからである。本発明に係る第２の２次元グラフ作成部１６０は、比較対象となった一方の決定木と他方の決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフを作成する。
【００９２】
図１３(a)は、第２の２次元グラフ作成部１６０により作成される２次元グラフの一例を示す。ここでX軸は時間を、Y軸は分散を表す。グラフ上にマップされている分散データは、時刻T=0〜９の決定木から、隣接する決定木の組を取り出して比較して得られた値である。例えば、時刻T=1のデータは、図１１(a)に示すグラフに対応し、時刻T=1の決定木の基本頻度と適用頻度の差の分散である。図１３から明らかなように、第２の２次元グラフ作成部１６０により作成される２次元グラフによれば、コンセプトドリフトが発生した時刻を容易に知ることが可能となる。なお、図１１(a)、(b)及び 図１２(a)、(b)に示す時系列に並んだ複数の２次元グラフは、新たに時間の次元を追加することで、図１３(b)に示すように、１つの３次元グラフにまとめて表示することも可能である。
【００９３】
次に図１４乃至図１５を参照して、本発明の一実施形態に係る決定木比較処理の流れを説明する。図１４は、決定木比較装置１００において実行される、決定木を比較する決定木比較処理の全体の流れの一例を示すフローチャートである。なお、上述したように、決定木比較装置１００は、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部１１０と、異なるデータセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部１１５とを有する。なおデータセット格納部１１０が格納するデータセット、及び決定木情報格納部１１５が格納する決定木情報は、図２を参照して説明したデータセット、及び図３乃至図５を参照して説明した決定木情報と、それぞれ同じデータ構造を有するものとする。
【００９４】
図１４において処理はステップ４００で開始し、決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、決定木を生成する過程で該ノードに分類されたインスタンスの数が最も多い目的属性の値を該ノードの目的属性として決定し、決定した目的属性の値を、そのノードに関連付けて決定木情報格納部１１５に登録する（ステップ４００）。
【００９５】
そして決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木のそれぞれの各ノードについて、決定木を生成する過程で該ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、そのノードに分類された全インスタンスの数で割った値である基本頻度を算出する（ステップ４０５）。
【００９６】
次に決定木比較装置１００は、決定木情報格納部１１５に格納される複数の決定木の中から比較する２つの決定木を選択する（ステップ４１０）。また決定木比較装置１００は、比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ一方の決定木のあるノードに分類された要素であるインスタンスの集合を、他方の決定木への入力として選択する。
【００９７】
選択は、マウスやキーボード等の入力デバイスによりユーザによって指示されてよい。或いはデフォルトとして、所定の基準に従って決定木を並べた場合に隣接する決定木の全ての組み合わせを、比較する２つの決定木として順次選択するよう構成してもよい。同様に、一方の決定木のあるノードとして、ルートノードを予めデフォルトとして設定し、または全ノードが順次選択されるよう設定しておいてもよい。
【００９８】
比較する２つの決定木を選択すると、決定木比較装置１００は、他方の決定木への入力として選択したインスタンスの集合をデータセット格納部１１０から読み出し、他方の決定木に分類させる。そして、決定木比較装置１００は、他方の決定木の各ノードについて、該ノードに分類され、かつノードの目的属性と同じ値の目的属性を有するインスタンスの数を、ノードに分類される全インスタンスの数で割った値である適用頻度を算出する（ステップ４１５）。なお、適用頻度の算出処理の詳細は、図１５を参照して後述する。
【００９９】
最後に、決定木比較装置１００は、他方の決定木の各ノードの基本頻度と適用頻度とが満たす関係を示す関係情報を、２つの決定木の比較結果として出力する（ステップ４２０）。そして処理は終了する。なお関係情報は、上述したように、第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木の各ノードの基本頻度と適用頻度の各値をマップした２次元グラフであってもよい。また、関係情報は、他方の決定木の各ノードを示す図形の大きさが該ノードの基本頻度と適用頻度の差の絶対値に比例する他方の決定木のグラフであってもよい。
【０１００】
また、関係情報は、他方の決定木の各ノードを示す図形の色、形状、及び模様の少なくとも１つが第１軸を基本頻度及び第２軸を適用頻度とした２次元座標に他方の決定木のノードの基本頻度と適用頻度の各値をマップした際のマップされた領域に応じて異なる他方の決定木のグラフであってもよい。更に、関係情報は、比較対象となった決定木の各ペアに対して、他方の決定木の各ノードの基本頻度と適用頻度の差の分散を求め、決定木のペア毎の分散を示すグラフであってもよい。
【０１０１】
関係情報としてどのようなグラフを出力するかは、マウスやキーボード等の入力デバイスによりユーザによって指示されてよい。その際ユーザは、複数のグラフを選択してもよい。また比較結果の出力は、表示画面やプリンタ等に出力させてもよく、あるいはネットワークを介して他の情報処理装置へ送信してもよい。なお、ここでは繰り返しを避けるため、各グラフの詳細な説明は省略する。
【０１０２】
図１５は、図１４のステップ４１５の適用頻度の算出処理の流れの一例を示すフローチャートである。処理はステップ５００で開始し、決定木比較装置１００は、図１４のステップ４１０で選択した、一方の決定木のノードのうち比較対象のノードのノードIDの値nを取得する。そして決定木比較装置１００は、他方の決定木への入力となる比較対象のノードに分類されたインスタンスの集合をデータセット格納部１１０から読み出すために、以下のステップ５０５乃至ステップ５２５の処理を行う。
【０１０３】
即ち、決定木比較装置１００はまず、決定木情報格納部１１５に格納される一方の決定木の決定木情報である階層別の複数のテーブルから、ノードID=nのエントリを取得する（ステップ５０５）。そして決定木比較装置１００は、取得したエントリから、判断ルールの値と、該エントリが登録されているテーブルのテーブル名Mを取得する（ステップ５１０）。次に決定木比較装置１００は、一方の決定木の階層別の複数のテーブルから、下位層テーブル名がMであるエントリを取得する（ステップ５１５）。そしてステップ５２０において、決定木比較装置１００は、下位層テーブル名がMであるエントリを取得できたか否か判定する。
【０１０４】
下位層テーブル名がMであるエントリを取得できた場合（ステップ５２０：YES)、処理はステップ５１０へ戻り、決定木比較装置１００は、ステップ５１０乃至ステップ５２０の処理を繰り返す。一方下位層テーブル名がMであるエントリを取得できなかった場合（ステップ５２０：NO)、処理はステップ５２５へ進み、決定木比較装置１００は、データセット格納部１１０を検索して、ステップ５１０において取得した判断ルール全てを満たす、一方の決定木を生成する基となったS個のインスタンスを全て取得する。
【０１０５】
次に決定木比較装置１００は、決定木情報格納部１１５に格納される一方の決定木の決定木情報である階層別の複数のテーブルの各々に、「適用インスタンス」のフィールドを新たに追加し、初期値として０を設定する（ステップ５３０）。なお、「適用インスタンス」フィールドは、「yes」、「no」、及び「適用頻度」の３つのフィールドからなり、各フィールドを値０で初期化するものとする。また、決定木比較装置１００は、他方の決定木へ入力する入力インスタンスのカウンタiを値1で初期化する（ステップ５３５）。
【０１０６】
処理はステップ５４０へ進み、決定木比較装置１００は、ステップ５２５で取得したインスタンスの集合からi番目のインスタンスを取得し、他方の決定木への入力とする。そして決定木比較装置１００はまず、決定木情報格納部１１５に格納される他方の決定木の決定木情報である階層別の複数のテーブルから、ルートノードのエントリを取得する（ステップ５４５）。そして、i番目のインスタンスの目的属性がyesの場合、決定木比較装置１００は、ルートノードのエントリの「適用インスタンス」フィールドの「yes」フィールドの値を１増加する（ステップ５５０、５５５）。一方、i番目のインスタンスの目的属性がnoの場合、決定木比較装置１００は、ルートノードのエントリの「適用インスタンス」フィールドの「no」フィールドの値を１増加する（ステップ５５０、５６０）。
【０１０７】
次に決定木比較装置１００は、現在取得しているエントリの下位層テーブル名Nを取得する（ステップ５６５）。そして決定木比較装置１００は、下位層テーブル名Nを取得できたか否か判定し（ステップ５７０）、取得できた場合、決定木比較装置１００は、決定木情報格納部１１５に格納される他方の決定木の決定木情報である階層別の複数のテーブルから、テーブル名＝Nのテーブルを検索し、該テーブルから、i番目のインスタンスがその判断ルールを満たすエントリを取得する（ステップ５７５）。そして決定木比較装置１００は、ステップ５７５においてエントリを取得できたか否か判定する（ステップ５８０）。
【０１０８】
エントリを取得できた場合（ステップ５８０：YES）、処理はステップ５５０へ戻る。一方ステップ５７０またはステップ５８０においてNOの場合、処理はステップ５８５へ進み、決定木比較装置１００は、入力インスタンスのカウンタiを１増加し、iがステップ５２５で取得した全インスタンス数Sより大きいか否か判定する（ステップ５８５）。iがSより以下の場合、処理はステップ５４０へ戻り、ステップ５４０乃至ステップ５８５の一連の処理を繰り返す。
【０１０９】
一方、iがSより大きい場合、処理はステップ５９５へ進み、決定木比較装置１００は、他方の決定木の各テーブルの「適用インスタンス」のフィールド値を使って、他方の決定木の各ノードの適用頻度を算出する。即ち、決定木比較装置１００は、他方の決定木の各テーブルの各エントリについて、「適用インスタンス」フィールドの「yes」フィールドと「no」フィールドの値を足して、該エントリが示すノードに分類されたインスタンスの合計を求める。そして、決定木比較装置１００は、各エントリの「適用インスタンス」フィールドの「yes」フィールドと「no」フィールドのうち、該エントリの「目的属性」フィールドの値と等しい方のフィールドの値を、先に求めた合計で割って、該エントリが示すノードの適用頻度を算出する。算出された適用頻度は「適用頻度」フィールドに登録される。そして処理は終了する。
【０１１０】
図１６は、本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。情報処理装置は、バス２に接続されたＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、およびＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【０１１１】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、決定木比較装置１００としての情報処理装置の上記説明した数々の記憶装置には、本発明に係る決定木比較プログラムと、上記説明したデータセット格納部１１０及び決定木情報格納部１１５に含まれるデータを格納できる。そして複数のコンピュータ・プログラムはメインメモリ４にロードされることによって実行される。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる
【０１１２】
情報処理装置は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。情報処理装置は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。情報処理装置は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。情報処理装置は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【０１１３】
以上の説明により、本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、または、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【０１１４】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【０１１５】
【図１】本発明の実施の形態に係る決定木比較装置１００の機能構成の一例を示す図である。
【図２】（ａ）は、データセット格納部１１０に格納されるデータセットのデータ構造の一例を示す。（ｂ）は、図２(a)に示すデータ構造をもった時刻Tのデータセットから生成された決定木のグラフの一例を示す。（ｃ）は、図２(a)に示すデータ構造をもった時刻T+1のデータセットから生成された決定木のグラフの一例を示す。
【図３】（ａ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のルートノードの情報を登録する階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻Tの決定木の中間ノードの情報を登録する階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のリーフノードの情報を登録する階層テーブルの一例を示す。
【図４】（ａ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のルートノードの情報を登録する階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木の中間ノードの情報を登録する階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する階層テーブルの一例を示す。（ｄ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する階層テーブルの一例を示す。
【図５】（ａ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のルートノードの情報を登録する、更新された階層テーブルの一例を示す。（ｂ）は、決定木情報格納部１１５に格納される、時刻Tの決定木の中間ノードの情報を登録する、更新された階層テーブルの一例を示す。（ｃ）は、決定木情報格納部１１５に格納される、時刻Tの決定木のリーフノードの情報を登録する、更新された階層テーブルの一例を示す。（ｄ）は、決定木情報格納部１１５に格納される、時刻T+1の決定木のリーフノードの情報を登録する、更新された階層テーブルの一例を示す。
【図６】本発明の実施形態に係る第１の２次元グラフ作成部１４５により作成される２次元グラフの一例を示す。
【図７】（ａ）は、時刻Ｔの決定木のルートノードを経由したインスタンスの集合を入力とした場合の、決定木の比較結果を示す２次元グラフを示す。（ｂ）は、時刻Ｔの決定木のＩＤ＝５のリーフノードに分類されたインスタンスの集合を入力とした場合の、決定木の比較結果を示す２次元グラフを示す。
【図８】（ａ）は、天気と気温によってテニスを行うかどうかを決める、時刻Tの決定木のグラフの一例を示す。（ｂ）は、天気と気温によってテニスを行うかどうかを決める、時刻T+1の決定木のグラフの一例を示す。（ｃ）は、時刻Ｔの決定木の全インスタンスを入力とした場合の、時刻T+1の決定木のグラフを示す。
【図９】図８（ｃ）に示す決定木グラフに対応する、本発明の実施形態に係る第１の２次元グラフ作成部１４５により作成される２次元グラフを示す。
【図１０】（ａ）はされた、第１軸を基本頻度及び第２軸を適用頻度とする２次元グラフの領域ごと色分け方法の一例を示す。（ｂ）は、本発明の実施形態に係る第１決定木グラフ作成部１５０及び第２決定木グラフ作成部１５５によって作成される決定木グラフの一例を示す。
【図１１】（ａ）は、時刻ｔ＝１のコンセプトドリフトの解析結果を示す。（ｂ）は、時刻ｔ＝２のコンセプトドリフトの解析結果を示す。
【図１２】（ａ）は、時刻ｔ＝３のコンセプトドリフトの解析結果を示す。（ｂ）は、時刻ｔ＝４のコンセプトドリフトの解析結果を示す。
【図１３】（ａ）は、本発明の実施形態に係る第２の２次元グラフ作成部１６０により作成される２次元グラフの一例を示す。（ｂ）は、コンセプトドリフトの解析結果を示す３次元グラフの一例を示す。
【図１４】本発明の実施形態に係る、決定木比較処理の流れの一例を示すフローチャートである。
【図１５】本発明の実施形態に係る、適用頻度算出処理の流れの一例を示すフローチャートである。
【図１６】本発明の実施の形態による決定木比較装置１００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。
【特許請求の範囲】
【請求項１】
決定木を比較する決定木比較装置であって、
複数のデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する、前記データセット格納部と、
異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されるインスタンスの数が最も多い目的属性の値を、前記ノードの目的属性として決定する目的属性決定部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち前記ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出す読出し部と、
読み出した各インスタンスを他方の決定木に分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力する出力部と
を含む決定木比較装置。
【請求項２】
前記データセット格納部に格納される複数のデータセットは、ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項３】
前記データセット格納部に格納される複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項４】
前記データセット格納部に格納される複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項５】
前記出力部は、前記関係情報として、第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項６】
前記出力部は、前記関係情報として、前記他方の決定木の各ノードを示す図形の大きさが該ノードの前記基本頻度と前記適用頻度の差の絶対値に比例する前記他方の決定木のグラフを作成する、第１決定木グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項７】
前記出力部は、前記関係情報として、前記他方の決定木の各ノードを示す図形の色、形状、及び模様のうち少なくとも１つが第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に前記ノードの前記基本頻度と前記適用頻度の値をマップした際のマップされた領域に応じて異なる前記他方の決定木のグラフを作成する、第２決定木グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項８】
前記複数の決定木は、所定の基準に従って順に並べることが可能であり、前記読出し部及び前記適用頻度算出部による処理は、前記所定の基準に従って前記複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われ、前記出力部は、前記関係情報として、比較対象となった決定木の各ペアに対して、前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の差の分散を求め、前記決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項９】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のルートノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１０】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のある中間ノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１１】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のあるリーフノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１２】
決定木を比較する決定木比較装置であって、
ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する前記データセット格納部と、
異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として決定する目的属性決定部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出す読出し部と、
読み出した各インスタンスを他方の決定木に分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、
第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に、前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の各値をマップした２次元グラフを、前記２つの前記決定木の比較結果として出力する出力部と
を含む決定木比較装置。
【請求項１３】
決定木を比較する決定木比較方法であって、前記決定木比較方法は、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部と、異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部とを有する情報処理装置によって実行され、前記情報処理装置において、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として前記ノードに関連付けて前記決定木情報格納部に登録するステップと、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出するステップと、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出すステップと、
読み出した各インスタンスを他方の決定木に当該他方の決定木の決定木情報に従って分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出するステップと、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力するステップと
を含む決定木比較方法。
【請求項１４】
決定木を比較する決定木比較プログラムであって、前記決定木比較プログラムは、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部と、異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部とを有する情報処理装置に、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として前記ノードに関連付けて前記決定木情報格納部に登録するステップと、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出するステップと、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出すステップと、
読み出した各インスタンスを他方の決定木に当該他方の決定木の決定木情報に従って分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出するステップと、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力するステップと
を実行させる、決定木比較プログラム。
【請求項１】
決定木を比較する決定木比較装置であって、
複数のデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する、前記データセット格納部と、
異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されるインスタンスの数が最も多い目的属性の値を、前記ノードの目的属性として決定する目的属性決定部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち前記ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出す読出し部と、
読み出した各インスタンスを他方の決定木に分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力する出力部と
を含む決定木比較装置。
【請求項２】
前記データセット格納部に格納される複数のデータセットは、ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項３】
前記データセット格納部に格納される複数のデータセットは、ある事象を複数の場所で観測して得られた場所別の複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項４】
前記データセット格納部に格納される複数のデータセットは、ある事象を年代別に観測して得られた年代別の複数のデータセットである、請求項１に記載の決定木比較装置。
【請求項５】
前記出力部は、前記関係情報として、第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の値をマップした２次元グラフを作成する、第１の２次元グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項６】
前記出力部は、前記関係情報として、前記他方の決定木の各ノードを示す図形の大きさが該ノードの前記基本頻度と前記適用頻度の差の絶対値に比例する前記他方の決定木のグラフを作成する、第１決定木グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項７】
前記出力部は、前記関係情報として、前記他方の決定木の各ノードを示す図形の色、形状、及び模様のうち少なくとも１つが第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に前記ノードの前記基本頻度と前記適用頻度の値をマップした際のマップされた領域に応じて異なる前記他方の決定木のグラフを作成する、第２決定木グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項８】
前記複数の決定木は、所定の基準に従って順に並べることが可能であり、前記読出し部及び前記適用頻度算出部による処理は、前記所定の基準に従って前記複数の決定木を並べた場合に隣接する２つの決定木の各組に対して行われ、前記出力部は、前記関係情報として、比較対象となった決定木の各ペアに対して、前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の差の分散を求め、前記決定木のペア毎の分散を示すグラフを作成する第２の２次元グラフ作成部を含む、請求項１に記載の決定木比較装置。
【請求項９】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のルートノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１０】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のある中間ノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１１】
前記データセット格納部から読み出されたインスタンスの集合は、前記一方の決定木を生成する基となった前記データセットの要素であって、かつ前記一方の決定木のあるリーフノードに分類された要素であるインスタンスの集合である、請求項１に記載の決定木比較装置。
【請求項１２】
決定木を比較する決定木比較装置であって、
ある事象を一定期間観測して得られた時系列データを所定時間間隔で分割して得られる複数のデデータセットを格納するデータセット格納部であって、各データセットの要素であるインスタンスは各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する前記データセット格納部と、
異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として決定する目的属性決定部と、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出する基本頻度算出部と、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出す読出し部と、
読み出した各インスタンスを他方の決定木に分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出する適用頻度算出部と、
第１軸を前記基本頻度及び第２軸を前記適用頻度とした２次元座標に、前記他方の決定木の各ノードの前記基本頻度と前記適用頻度の各値をマップした２次元グラフを、前記２つの前記決定木の比較結果として出力する出力部と
を含む決定木比較装置。
【請求項１３】
決定木を比較する決定木比較方法であって、前記決定木比較方法は、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部と、異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部とを有する情報処理装置によって実行され、前記情報処理装置において、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として前記ノードに関連付けて前記決定木情報格納部に登録するステップと、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出するステップと、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出すステップと、
読み出した各インスタンスを他方の決定木に当該他方の決定木の決定木情報に従って分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出するステップと、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力するステップと
を含む決定木比較方法。
【請求項１４】
決定木を比較する決定木比較プログラムであって、前記決定木比較プログラムは、各々同種の目的属性と当該目的属性の変動を説明する同種の説明属性を有する複数のインスタンスの集合であるデータセットを複数格納するデータセット格納部と、異なる前記データセットからそれぞれ生成された複数の決定木の決定木情報を格納する決定木情報格納部とを有する情報処理装置に、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類されたインスタンスの数が最も多い目的属性の値を前記ノードの目的属性として前記ノードに関連付けて前記決定木情報格納部に登録するステップと、
前記複数の決定木のそれぞれの各ノードについて、前記決定木を生成する過程で前記ノードに分類された１以上のインスタンスのうち該ノードの目的属性の値と同じ目的属性を有するインスタンスの数を、前記ノードに分類された全インスタンスの数で割った値である基本頻度を算出するステップと、
比較する２つの決定木のうち、一方の決定木を生成する基となったデータセットの要素であって、かつ前記一方の決定木のあるノードに分類された要素であるインスタンスの集合を前記データセット格納部から読み出すステップと、
読み出した各インスタンスを他方の決定木に当該他方の決定木の決定木情報に従って分類させ、前記他方の決定木の各ノードについて、該ノードに分類され、かつ前記ノードの目的属性と同じ値の目的属性を有するインスタンスの数を、前記ノードに分類される全インスタンスの数で割った値である適用頻度を算出するステップと、
前記他方の決定木の各ノードの前記基本頻度と前記適用頻度とが満たす関係を示す関係情報を、前記２つの前記決定木の比較結果として出力するステップと
を実行させる、決定木比較プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１０−４４６４９（Ｐ２０１０−４４６４９Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０９０６６（Ｐ２００８−２０９０６６）
【出願日】平成２０年８月１４日（２００８．８．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 第１６０回 ソフトウエア工学・第９回 組込みシステム 合同研究発表会、社団法人 情報処理学会、平成２０年６月１９日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１４日（２００８．８．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 第１６０回 ソフトウエア工学・第９回 組込みシステム 合同研究発表会、社団法人 情報処理学会、平成２０年６月１９日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]