(57)【要約】  決定木の構造を規定する制約条件が保存された制約条件ＤＢを参照し、複数の属性に対する値及び結論が関連付けられた事例集合から、制約条件により規定される決定木の構造を満たすように決定木を生成する。このため、例えば、事例集合に新たな事例が追加されても、制約条件により決定木の基本的な構造が承継されることから、作業者が決定木を大幅に修正しなければならないという事態が回避される。従って、作業者による決定木の修正作業を軽減させることができる。
2010116450.tif 000002
【特許請求の範囲】
【請求項１】
決定木の構造を規定する制約条件が記憶された外部記憶装置を有するコンピュータに、
複数の属性に対する値及び結論が関連付けられた事例集合を読み込む事例入力部と、
前記外部記憶装置から制約条件を読み込み、該制約条件により規定される決定木の構造を満たすように、前記事例入力部により読み込まれた事例集合から決定木を生成する決定木生成部と、
を実現させることを特徴とする決定木生成プログラム。
【請求項２】
前記コンピュータに、
作業者の指示に従って、前記決定木生成部により生成された決定木を編集する決定木編集部と、
前記決定木編集部による決定木の修正履歴から制約条件を生成し、前記外部記憶装置に生成した制約条件を保存する制約条件生成部と、
を更に実現させることを特徴とする請求項１記載の決定木生成プログラム。
【請求項３】
前記制約条件は、少なくとも、無視する属性を規定する第１の制約条件、属性が他の属性よりも下位にあることを規定する第２の制約条件、及び、属性が他の属性よりも上位にあることを規定する第３の制約条件から構成されることを特徴とする請求項２記載の決定木生成プログラム。
【請求項４】
前記制約条件生成部は、前記決定木から削除された属性があった場合、その属性を無視する第１の制約条件を生成し、前記決定木のルートから遠い位置に移動された属性があった場合、その属性が他の属性よりも下位にあることを規定する第２の制約条件を生成し、前記決定木に追加された属性があった場合、又は、前記決定木のルートに近い位置に移動された属性があった場合、その属性が他の属性よりも上位にあることを規定する第３の制約条件を生成することを特徴とする請求項３記載の決定木生成プログラム。
【請求項５】
前記第２の制約条件及び前記第３の制約条件における他の属性は、集合で表されることを特徴とする請求項３記載の決定木生成プログラム。
【請求項６】
前記コンピュータに、前記決定木生成部により生成された最新の決定木とその直前の決定木との差分を抽出し、該差分を表示装置に表示する差分表示部を更に実現させることを特徴とする請求項１記載の決定木生成プログラム。
【請求項７】
決定木の構造を規定する制約条件が記憶された外部記憶装置を有するコンピュータが、
複数の属性に対する値及び結論が関連付けられた事例集合を読み込むステップと、
前記外部記憶装置から制約条件を読み込み、該制約条件により規定される決定木の構造を満たすように、前記読み込まれた事例集合から決定木を生成するステップと、
を実行することを特徴とする決定木生成方法。
【請求項８】
前記コンピュータが、
作業者の指示に従って、前記生成された決定木を編集するステップと、
前記決定木の修正履歴から制約条件を生成し、前記外部記憶装置に生成した制約条件を保存するステップと、
を更に実行することを特徴とする請求項７記載の決定木生成方法。
【請求項９】
決定木の構造を規定する制約条件を記憶する外部記憶装置と、
複数の属性に対する値及び結論が関連付けられた事例集合を読み込む事例入力手段と、
前記外部記憶装置から制約条件を読み込み、該制約条件により規定される決定木の構造を満たすように、前記事例入力手段により読み込まれた事例集合から決定木を生成する決定木生成手段と、
を含んで構成されたことを特徴とする決定木生成装置。
【請求項１０】
作業者の指示に従って、前記決定木生成手段により生成された決定木を編集する決定木編集手段と、
前記決定木編集手段による決定木の修正履歴から制約条件を生成し、前記外部記憶装置に生成した制約条件を保存する制約条件生成手段と、
を更に備えたことを特徴とする請求項９記載の決定木生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、事例集合から決定木を自動生成する決定木生成技術に関する。
【背景技術】
【０００２】
統計的決定理論，人工知能，機械学習，データマイニングなどの分野において、予想モデル構築，意思決定分析・最適化，分類問題の解決，概念・知識の記述，ルールの抽出・生成などに決定木が利用されることがある。決定木は、分岐の繰り返しを階層化して樹形図で表現したものである。決定木の自動生成技術として、事例集合における各事例の平均情報量（エントロピー）などから、決定木を自動生成する技術が提案されている。
【特許文献１】特開平９−３３０２２４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、事例集合に新規事例が次々と追加される場合には、それまで利用していた決定木が新規事例に適合しなくなるおそれがあるため、定期的に、事例集合から決定木を再生成する必要がある。また、従来提案技術で自動生成された決定木は、必ずしも事例集合に適合しているといえないため、管理者などの作業者が自動生成された決定木を確認し、これを必要に応じて適宜修正しなければならない。そして、新規事例が追加された事例集合から自動生成された決定木には、作業者が修正した内容が反映されていないことから、作業者は再度同一の修正を行わなければならず、決定木の修正作業時間が増加してしまうおそれがあった。【０００４】
そこで、このような問題点に鑑み、決定木の構造を規定する制約条件を導入して、事例集合から決定木を自動生成することで、作業者による決定木の修正作業を軽減した決定木自動生成技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
この決定木生成技術では、決定木の構造を規定する制約条件を新たに導入する。そして、複数の属性に対する値及び結論が関連付けられた事例集合から、制約条件により規定される決定木の構造を満たすように決定木を生成する。
【発明の効果】
【０００６】
この決定木生成技術によれば、例えば、事例集合に新たな事例が追加されても、制約条件により決定木の基本的な構造が承継されることから、作業者が決定木を大幅に修正しなければならないという事態が回避される。このため、作業者による決定木の修正作業を軽減させることができる。
【図面の簡単な説明】
【０００７】
【図１】本技術を具現化した決定木生成装置の一実施形態を示す構成図である。
【図２】事例ＤＢに保持される事例集合の説明図である。
【図３】修正履歴ＤＢに保持される編集前の決定木の説明図である。
【図４】修正履歴ＤＢに保持される編集後の決定木の説明図である。
【図５】事例入力部が実行する事例入力処理のフローチャートである。
【図６】決定木生成部が実行する決定木生成処理のフローチャートである。
【図７】決定木生成部が実行する決定木生成処理のフローチャートである。
【図８】特定の事例集合から決定木を生成するまでの処理において、最初に生成される決定木の説明図である。
【図９】特定の事例集合から決定木を生成するまでの処理において、中間で生成される決定木の説明図である。
【図１０】特定の事例集合から決定木を生成するまでの処理において、最終的に生成される決定木の説明図である。る。
【図１１】差分表示部が実行する差分表示処理のフローチャートである。
【図１２】決定木編集部が実行する決定木編集処理のフローチャートである。
【図１３】決定木出力部が実行する決定木出力処理のフローチャートである。
【図１４】修正履歴保存部が実行する修正履歴保存処理のフローチャートである。
【図１５】制約条件生成部が実行する制約条件生成処理のフローチャートである。
【符号の説明】
【０００８】
１０    決定木生成装置
１２    事例ＤＢ
１２Ａ  事例集合
１４    修正履歴ＤＢ
１４Ａ  修正履歴
１６    決定木ＤＢ
１６Ａ  決定木
１８    制約条件ＤＢ
１８Ａ  制約条件
２０    事例入力部
２２    決定木生成部
２４    差分表示部
２６    決定木編集部
２８    決定木出力部
３０    修正履歴保存部
３２    制約条件生成部
【発明を実施するための最良の形態】
【０００９】
以下、添付された図面を参照して本技術を詳述する。
図１は、本技術を具現化した決定木生成装置の一実施形態を示す。なお、この決定木生成装置は、本実施形態では、情報システムのトラブル解決手順を階層化した決定木を生成することを目的とするが、この目的に限定されるものではない。
決定木生成装置１０は、ハードディスクなどの外部記憶装置を備えた汎用コンピュータを用いて構築される。決定木生成装置１０の外部記憶装置には、事例ＤＢ（データベース）１２、修正履歴ＤＢ１４、決定木ＤＢ１６及び制約条件ＤＢ１８が夫々記録される。事例ＤＢ１２には、情報システムのトラブルに関する事例集合１２Ａとして、図２に示すように、各事例（事例１〜４）について、決定木の属性（分岐条件ａ1〜ａ3）に対する値及び原因（結論）を関連付けたレコードの集合が保持される。修正履歴ＤＢ１４には、作業者による決定木の修正履歴１４Ａとして、図３及び図４に示すように、編集前の決定木（図３）及び編集後の決定木（図４）が保持される。なお、決定木の修正履歴１４としては、図３及び図４に示すような決定木そのものではなく、編集前の決定木からの変更箇所を特定可能な情報を用いるようにしてもよい。決定木ＤＢ１６には、各種決定木１６Ａとして、自動生成された最新及びその直前の決定木、並びに、作業者による修正又は確認を経た決定木が保持される。制約条件ＤＢ１８には、次のように、決定木の構造を規定するための制約条件１８Ａが保持される。【００１０】
ここでは、制約条件１８Ａの一例として、少なくとも、属性Ａを無視することを規定するIgnore(A)、属性Ａが属性Ｂ，Ｃ，Ｄの下位にあることを規定するAcceptAfter(A,{B,C,D})、属性Ａが属性Ｂ，Ｃ，Ｄの上位にあることを規定するAcceptBefore(A,{B,C,D})を適用する。なお、中括弧{}は、属性の集合を表している。ここで、Ignore(A)、AcceptAfter(A,{B,C,D})及びAcceptBefore(A,{B,C,D})は、夫々、第１の制約条件、第２の制約条件及び第３の制約条件に該当する。【００１１】
また、決定木生成装置１０では、外部記憶装置に記憶された決定木生成プログラムを実行することで、事例入力部２０、決定木生成部２２、差分表示部２４、決定木編集部２６、決定木出力部２８、修正履歴保存部３０及び制約条件生成部３２が夫々具現化される。なお、決定木生成装置１０の外部記憶装置には、決定木生成プログラムが記録されたＣＤ−ＲＯＭなどのコンピュータ読取可能な記録媒体から、決定木生成プログラムがインストールされる。【００１２】
事例入力部２０は、事例ＤＢ１２から事例集合１２Ａを読み込む。決定木生成部２２は、制約条件ＤＢ１８に保持される制約条件１８Ａを参照し、事例入力部２０により読み込まれた１２Ａから決定木を自動生成する。差分表示部２４は、決定木ＤＢ１６を参照し、決定木生成部２２により自動生成された最新の決定木とその直前の決定木との差分を、モニタなどの表示装置に表示する。決定木編集部２６は、表示装置及びマウスなどのポインティングデバイスと協働したインタラクティブ環境で、決定木生成部２２により自動生成された決定木を適宜編集する編集機能を提供する。なお、決定木の編集内容としては、属性の削除，追加，移動などが想定される。決定木出力部２８は、決定木編集部２６により編集された決定木１６Ａ（確認のみ行われた決定木１６Ａも含む）を決定木ＤＢ１６に保存する。修正履歴保存部３０は、決定木編集部２６により編集された決定木の修正履歴を修正履歴ＤＢ１４に保存する。制約条件生成部１８は、修正履歴ＤＢ１４に保持された修正履歴１４Ａを参照しつつ、修正履歴１４Ａから制約条件１８Ａを自動生成し、制約条件ＤＢ１８に自動生成した制約条件１８Ａを保存する。【００１３】
ここで、事例入力部２０が、事例集合を読み込むステップ及び事例入力手段に夫々該当すると共に、決定木生成部２２が、決定木を生成するステップ及び決定木生成手段に夫々該当する。また、決定木編集部２６が、決定木を編集するステップ及び決定木編集手段に夫々該当すると共に、制約条件生成部３２が、制約条件を生成・保存するステップ及び制約条件生成手段に夫々該当する。【００１４】
図５は、事例入力部２０が、作業者により決定木生成指示があったことを契機として実行する事例入力処理を示す。
ステップ１（図では「Ｓ１」と略記する。以下同様。）では、事例入力部２０が、事例ＤＢ１２から事例集合１２Ａを読み込む。
ステップ２では、事例入力部２０が、決定木生成部２２に対して決定木の生成依頼を送信する。【００１５】
図６及び図７は、決定木生成部２２が、事例入力部２０から決定木の生成依頼があったことを契機として実行する決定木生成処理を示す。なお、決定木を生成する詳細処理については、公知のＣ４．５を説明する、Quinlan, J.R “induction of decision Trees” Machine Learning, vol.1, No.1, pp81-106(1986) (http://www.springerlink.com/content/ku63wm5513224245/fulltext.pdf)などを参照されたし。【００１６】
ステップ１１では、決定木生成部２２が、事例入力部２０により読み込まれた事例集合１２Ａから属性を抽出し、メモリ上の候補リストに全ての属性を登録する。
ステップ１２では、決定木生成部２２が、制約条件ＤＢ１８から制約条件１８Ａを読み込む。
ステップ１３では、決定木生成部２２が、メモリ上に制約条件１８Ａをコピーした制約条件インスタンスを生成する。【００１７】
ステップ１４では、決定木生成部２２が、制約条件Ignore(X)（Ｘ：属性）について、候補リストから属性Ｘを削除すると共に、制約条件インスタンスからIgnore(X)そのものを削除する。なお、制約条件Ignore(X)が存在しない場合には、候補リスト及び制約条件インスタンスには何ら変更がなされない。
ステップ１５では、決定木生成部２２が、候補リストから、制約条件AcceptAfter(A,{A1,A2,…,An})（Ａ,Ａ1,Ａ2,…,Ａn：属性）の属性Ａを削除する。なお、制約条件AcceptAfter(A,{A1,A2,…,An})が存在しない場合には、候補リストには何ら変更がなされない。【００１８】
ステップ１６では、決定木生成部２２が、ルートノードＮを作成し、全ての事例をルートノードＮに所属させる。
ステップ１７では、決定木生成部２２が、ルートノードＮに所属する各事例の原因Ｙが全て同一か否かを判定する。そして、決定木生成部２２が、各事例の原因Ｙが全て同一でなければ処理をステップ１８へと進む一方（Ｎｏ）、各事例の原因Ｙが全て同一であれば処理をステップ２６へと進める（Ｙｅｓ）。【００１９】
ステップ１８では、決定木生成部２２が、事例集合Ｃをある属性ａiの値で分割し、確率分布の偏りを表す平均情報量（エントロピー）の減少量を演算する。平均情報量の代わりに、Giniインデックス、Information gain等の他の指標を用いてもよい。
ステップ１９では、決定木生成部２２が、平均情報量の減少量が一番大きい属性ａkを選択する。【００２０】
ステップ２０では、決定木生成部２２が、各制約条件AcceptBefore(B,{B1,B2,…,Bn})の属性集合{B1,B2,…,Bn}に属性ａkが含まれているか否かを判定する。そして、決定木生成部２２が、属性集合{B1,B2,…,Bn}に属性ａkが含まれていなければ処理をステップ２１へと進める一方（Ｎｏ）、属性集合{B1,B2,…,Bn}に属性ａkが含まれていれば処理をステップ２４へと進める（Ｙｅｓ）。【００２１】
ステップ２１では、決定木生成部２２が、各制約条件AcceptAfter(A,{A1,A2,…,An})の属性集合{A1,A2,…,An}に属性ａkが含まれているか否かを判定する。そして、決定木生成部２２が、属性集合{A1,A2,…,An}に属性ａkが含まれていなければ処理をステップ２２へと進める一方（Ｎｏ）、属性集合{A1,A2,…,An}に属性ａkが含まれていれば処理をステップ２５へと進める（Ｙｅｓ）。【００２２】
ステップ２２では、決定木生成部２２が、候補リストから属性ａkを削除する。
ステップ２３では、決定木生成部２２が、ルートノードＮのラベルを属性ａkとして、ルートノードＮの子ノードＮjを作成し、各子ノードＮjに事例Ｃkを所属させる。その後、決定木生成部２２が、各子ノードＮjについて、ルートノードＮ＝子ノードＮj、事例集合Ｃ＝事例Ｃkとしてステップ１７以降の処理を再帰的に実行すべく、処理をステップ１７へと戻す。【００２３】
ステップ２４では、決定木生成部２２が、制約条件AcceptBefore(B,{B1,B2,…,Bn})の属性Ｂが採用されていなければ、その属性Ｂに属性ａkを設定し、処理をステップ２２へと進める。
ステップ２５では、決定木生成部２２が、制約条件AcceptAfter(A,{A1,A2,…,An})の属性集合{A1,A2,…,An}から属性ａkを削除し、処理をステップ２２へと進める。なお、属性集合が空になった場合には、決定木生成部２２が、候補リストに属性Ａを追加すると共に、制約インスタンスから制約条件AcceptAfter()を削除する。【００２４】
ステップ２６では、決定木生成部２２が、ルートノードに原因Ｙをラベル付ける。
ステップ２７では、決定木生成部２２が、全ての再帰処理が終了したか否かを判定する。そして、決定木生成部２２が、全ての再帰処理が終了したならば処理をステップ２７へと進める一方（Ｙｅｓ）、全ての再帰処理が終了していなければ処理をステップ１７へと戻す（Ｎｏ）。【００２５】
ステップ２８では、決定木生成部２２が、ステップ１１〜ステップ２７の処理で自動生成された決定木を決定木ＤＢ１６に保存する。
ステップ２９では、決定木生成部２２が、差分表示部２４に対して決定木の差分表示依頼を送信する。
ここで、決定木生成処理の理解を容易ならしめることを目的として、図２の事例集合から決定木を生成するまでの処理を説明する。なお、制約条件ＤＢ１８には、図４に示す決定木の構造を規定するための制約条件１８Ａとして、Ignore(遅延している処理)、AcceptBefore(遅くなった時期，{負荷の高低による影響})が保持されているものとする。【００２６】
決定木生成処理の実行が開始されると、候補リストに、「遅延している処理」，「遅くなった時期」及び「負荷の高低による影響」が夫々登録される。また、制約条件ＤＢ１８から制約条件１８Ａが読み込まれ、これをコピーした制約条件インスタンス、即ち、Ignore(遅延している処理)、AcceptBefore(遅くなった時期，{負荷の高低による影響})が生成される。制約条件インスタンスが生成されると、そこに制約条件Ignore(遅延している処理)が存在するため、候補リストから「遅延している処理」が削除されると共に、制約条件インスタンスからIgnore(遅延している処理)が削除される。この結果、候補リストには、「遅くなった時期」及び「負荷の高低による影響」が登録される一方、制約条件インスタンスには、AcceptBefore(遅くなった時期，{負荷の高低による影響})が保持されることとなる。制約条件インスタンスには制約条件AcceptAfter(A,{A1,A2,…,An})が存在していないので、ルートノードＮを作成して、事例１〜４をルートノードＮに所属させる（Ｎ＝{事例１，事例２，事例３，事例４}）。【００２７】
ルートノードＮに所属する事例１〜４の原因が同一でないので、これを候補リストに登録された「遅くなった時期」及び「負荷の高低による影響」で夫々分割し、その平均情報量の減少量を演算する。「遅くなった時期」と「負荷の高低による影響」では、「遅くなった時期」の方が平均情報量の減少量が大きいので、属性ａkとして「遅くなった時期」が選択される。また、制約条件インスタンスAcceptBefore(遅くなった時期，{負荷の高低による影響})の属性集合{負荷の高低による影響}に「遅くなった時期」が含まれておらず、かつ、制約条件インスタンスにAcceptAfter()が保持されていないので、候補リストから「遅くなった時期」が削除される。この結果、候補リストには、「負荷の高低による影響」のみが登録されることとなる。そして、図８に示すように、ルートノードＮのラベルを「遅くなった時期」として、その分岐条件数に応じた２つの子ノードＮjに、分岐条件に適合した事例集合Ｃkを夫々従属させる。その後、各子ノードＮjについて、ルートノードＮ＝Ｎj、事例集合Ｃ＝Ｃkとして再帰処理が実行される。【００２８】
遅くなった時期が特定の時期からの場合、ルートノードＮ＝{事例２}となり、その原因Ｙ（業務量増加に伴うＣＰＵ負荷）が全て同一であるので、ルートノードＮに「業務量増加に伴うＣＰＵ負荷」がラベル付けられる。一方、遅くなった時期が稼動当初からの場合、ルートノードＮ＝{事例１，事例３，事例４}となり、その原因Ｙが全て同一ではない。このため、ルートノードＮに所属する事例１、事例３及び事例４を候補リストに登録された「負荷の高低による影響」で夫々分割し、その平均情報量の減少量を演算する。平均情報量の減少量が一番大きい属性は「負荷の高低による影響」であるので、属性ａkとして「負荷の高低による影響」が選択される。また、制約条件インスタンスAcceptBefore(遅くなった時期，{負荷の高低による影響})の属性集合{負荷の高低による影響}に「負荷の高低による影響」が含まれているが、これは採用されているため制約条件インスタンスを変更せず、候補リストから「負荷の高低による影響」が削除される。この結果、候補リストは空になる。そして、図９に示すように、ルートノードＮのラベルを「負荷の高低による影響」として、その分岐条件数に応じた２つの子ノードＮjに、分岐条件に適合した事例集合Ｃkを夫々従属させる。その後、各子ノードＮjについて、ルートノードＮ＝Ｎj、事例集合Ｃ＝Ｃkとして再帰処理が実行される。【００２９】
負荷の高低による影響が単体でも遅いの場合、ルートノードＮ＝{事例１，事例４}となり、その原因Ｙ（ウイルススキャンによる遅延）が全て同一であるので、ルートノードＮに「ウイルススキャンによる遅延」がラベル付けられる。一方、負荷の高低による影響が単体では速いの場合、ルートノードＮ＝{事例３}となり、その原因Ｙ（大量ログ出力によるレスポンス遅延）が全て同一であるので、ルートノードＮに「大量ログ出力によるレスポンス遅延」がラベル付けられる。そして、全ての再帰処理が終了したため、最終的に図１０に示すような決定木が生成される。【００３０】
図１１は、差分表示部２４が、決定木生成部２２から差分表示依頼があったことを契機として実行する差分表示処理を示す。
ステップ３１では、差分表示部２４が、決定木ＤＢ１６から最新の決定木とその直前の決定木を読み込む。
ステップ３２では、差分表示部２４が、最新の決定木とその直前の決定木の差分を抽出する。【００３１】
ステップ３３では、差分表示部２４が、差分により特定される決定木の変更箇所を可視的に表示する。ここで、「可視的に表示」とは、作業者が目視可能なように、イメージをモニタなどの表示装置に出力することをいう。
ステップ３４では、差分表示部２４が、決定木編集部２６に対して決定木の編集開始依頼を送信する。なお、編集開始依頼は、作業者により差分表示を終了することが指示されたときに、決定木編集部２６に対して送信される。【００３２】
図１２は、決定木編集部２６が、差分表示部２４から編集開始依頼があったことを契機として実行する決定木編集処理を示す。
ステップ４１では、決定木編集部２６が、作業者の指示に従って、決定木生成部２２により生成された決定木を適宜編集する。
ステップ４２では、決定木編集部２６が、例えば、作業者により編集終了指示がなされたか否かを介して、編集処理を終了すべきか否かを判定する。そして、決定木編集部２６が、編集処理を終了するならば処理をステップ４３へと進める一方（Ｙｅｓ）、編集処理を終了しないのであれば処理をステップ４１へと戻す（Ｎｏ）。【００３３】
ステップ４３では、決定木編集部２６が、決定木出力部２８及び修正履歴保存部３０に対して、各処理を開始すべきことを通知する開始依頼を夫々送信する。
図１３は、決定木出力部２８が、決定木編集部２６から開始依頼があったことを契機として実行する決定木出力処理を示す。
ステップ５１では、決定木出力部２８が、決定木編集部２６により編集された決定木を決定木ＤＢ１６に保存する。【００３４】
図１４は、修正履歴保存部３０が、決定木編集部２６から開始依頼があったことを契機として実行する修正履歴保存処理を示す。
ステップ６１では、修正履歴保存部３０が、決定木編集部２６による編集前の決定木を修正履歴ＤＢ１４に保存する。編集前の決定木としては、修正履歴ＤＢ１４に保存されている編集後の決定木を用いてもよい。【００３５】
ステップ６２では、修正履歴保存部３０が、決定木編集部２６による編集後の決定木を修正履歴ＤＢ１４に保存する。
ステップ６２では、修正履歴保存部３０が、制約条件生成部３２に対して制約条件の生成依頼を送信する。
図１５は、制約条件生成部３２が、修正履歴保存部３０から生成依頼があったことを契機として実行する制約条件生成処理を示す。【００３６】
ステップ７１では、制約条件生成部３２が、修正履歴ＤＢ１４から編集前の決定木と編集後の決定木を夫々読み込む。
ステップ７２では、制約条件生成部３２が、編集前の決定木と編集後の決定木との差分を抽出する。ここで、編集前の決定木と編集後の決定木との差分としては、例えば、編集前の決定木において削除された属性、追加された属性、ルートに近い位置に移動された属性及びルートから遠い位置に移動された属性が抽出される。【００３７】
ステップ７３では、制約条件生成部３２が、編集前の決定木において削除された属性があった場合、制約条件Ignore(削除された属性)を生成する。
ステップ７４では、制約条件生成部３２が、編集前の決定木において追加された属性があった場合、制約条件AcceptBefore(追加された属性，{その下位に位置する属性集合})を生成する。【００３８】
ステップ７５では、制約条件生成部３２が、編集前の決定木においてルートに近い位置に移動された属性があった場合、制約条件AcceptBefore(移動された属性，{その下位に位置する属性集合})を生成する。
ステップ７６では、制約条件生成部３２が、編集前の決定木においてルートから遠い位置に移動された属性があった場合、制約条件AcceptAfter(移動された属性，{その上位に位置する属性集合})を生成する。【００３９】
ステップ７７では、制約条件生成部３２が、ステップ７３〜ステップ７６で生成した制約条件を制約条件ＤＢ１８に保存する。
ここで、制約条件生成処理の理解を容易ならしめることを目的として、図３及び図４に示す編集前後の決定木から、制約条件を生成するまでの処理を説明する。
制約条件生成処理の実行が開始されると、修正履歴ＤＢ１４から、編集前の決定木（図３）及び編集後の決定木（図４）が夫々読み込まれる。また、編集前の決定木と編集後の決定木との差分として、「遅延している理由」が削除されたこと、及び、「遅くなった時期」が「負荷の高低による影響」の前に追加されたことが抽出される。そして、「遅延している理由」が削除されたことから、制約条件Ignore(遅延している理由)が生成される一方、「遅くなった時期」が「負荷の高低による影響」の前に追加されたことから、制約条件AcceptBefore(遅くなった時期，{負荷の高低による影響})が夫々生成される。その後、これらの制約条件が制約条件ＤＢ１８に保存される。【００４０】
かかる決定木生成装置１０によれば、作業者による決定木の修正履歴１４Ａから、決定木の構造を規定する制約条件１８Ａが生成される。そして、制約条件１８Ａにより規定される決定木の構造を満たすように、事例集合１２Ａから決定木が生成される。このため、事例集合１２Ａに新たな事例が追加されても、決定木の基本的な構造が承継されることから、作業者が決定木を大幅に修正しなければならないという事態が回避される。従って、作業者による決定木の修正作業を軽減させることができる。【００４１】
このとき、決定木の構造を規定する制約条件１８Ａは、決定木の修正履歴１４Ａから自動的に生成されるため、その作成に要する労力を省くことができる。また、決定木の構造を規定する制約条件１８Ａは、少なくとも、Ignore(A)、AcceptAfter(A,{B,C,D})及びAcceptBefore(A,{B,C,D})の３つで表現されるため、制御が複雑となることを防止することができる。さらに、AcceptAfter(A,{B,C,D})及びAcceptBefore(A,{B,C,D})において、第２引数は集合で表現されるため、複雑な決定木であってもその構造を規定することができる。その他、決定木の編集を開始する前に、最新の決定木とその直前の決定木との差分が表示装置に表示されるため、作業者は、どこを修正すべきかを容易に判断することができる。【００４２】
なお、決定木の構造を規定する制約条件１８Ａは、決定木を編集する作業者などが作成し、制約条件ＤＢ１８に保存するようにしてもよい。この場合には、修正履歴ＤＢ１４、修正履歴保存部３０及び制約条件生成部３２は不要である。また、差分表示部２４は、かならずしも実装しなくともよい。さらに、事例ＤＢ１２及び決定木ＤＢ１６は、決定木生成装置１０の外部にある外部記憶装置に記録されていてもよい。
【図１】
2010116450.tif 000003
【図２】
2010116450.tif 000004
【図３】
2010116450.tif 000005
【図４】
2010116450.tif 000006
【図５】
2010116450.tif 000007
【図６】
2010116450.tif 000008
【図７】
2010116450.tif 000009
【図８】
2010116450.tif 000010
【図９】
2010116450.tif 000011
【図１０】
2010116450.tif 000012
【図１１】
2010116450.tif 000013
【図１２】
2010116450.tif 000014
【図１３】
2010116450.tif 000015
【図１４】
2010116450.tif 000016
【図１５】
2010116450.tif 000017
【国際調査報告】
2010116450.tif 000018
2010116450.tif 000019
2010116450.tif 000020
2010116450.tif 000021