JP2018005624A - 決定木生成装置、決定木生成方法、決定木生成プログラム及び質問システム - Google Patents

Abstract

【課題】ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することが可能な決定木を生成することができる決定木生成装置を提供する。【解決手段】決定木生成装置は、分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、エントロピーの減少量と、属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、属性毎に当該属性の属性値により分割前のデータ集合を分割したときの情報ゲインを算出する情報ゲイン算出部１２と、属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに最も大きい情報ゲインを有する属性の属性値を順次割り当てる決定木作成部１１とを備える。【選択図】図１

Description

本開示は、対話によりユーザに質問を行って質問の回答結果から分類結果の候補を絞り込む際の質問の順序を決定するために使用される決定木を生成する決定木生成装置、決定木生成方法、及び決定木生成プログラム、並びに、この決定木生成装置により生成された決定木を用いて質問を行い、質問に対するユーザの回答から分類結果を生成する質問システムに関するものである。

対話によりユーザに質問を複数回行い、ユーザの回答結果に最も適合する分類結果を絞り込む際に、質問回数がなるべく少なくなるように、また、候補絞込みの誤りがなるべく少なくなるように、決定木を構成するための従来技術が存在する（例えば、特許文献１、特許文献２、特許文献３）。

具体的には、特許文献１では、決定木への入力が誤りを含む場合において、複数の決定木を生成し、それぞれの決定木により絞りこまれた複数の結果から、最も誤りが少ないと推定される絞り込み結果を採用する手法が開示されている。特許文献２では、決定木による絞込み結果が誤りであった場合の重大性を考慮して、決定木を生成する手法が開示されている。特許文献３では、決定木の入力が音声認識による誤りを含む可能性を考慮して、決定木を生成する手法が開示されている。

特開２０００−１１２９３６号公報 特開２００７−３３４５８９号公報 特開２００３−２５５９９２号公報

しかしながら、従来技術によると、質問に対するユーザ自身の回答が誤っている可能性を考慮して、決定木を生成することができないため、適切な質問順序を決定することができないという課題を有しており、さらなる改善が必要であった。

本開示は、上記の課題を解決するためになされたもので、対話によりユーザに質問を行って、質問の回答結果から分類結果の候補を絞り込む際に、ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することが可能な決定木を生成することができる決定木生成装置、決定木生成方法及び決定木生成プログラム、並びに、対話によりユーザに質問を行って質問の回答結果から分類結果又は検索結果の候補を絞り込む際に、ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することができる質問システムを提供することを目的とするものである。

本開示の一様態による決定木生成装置は、質問の順序を決定するために使用される決定木を生成する決定木生成装置であって、互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出する情報ゲイン算出部と、前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる決定木作成部とを備える。

本開示によれば、対話によりユーザに質問を行って、質問の回答結果から分類結果の候補を絞り込む際に、ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することが可能な決定木を生成することができる。

本開示の一実施の形態における決定木生成装置の構成の一例を示すブロック図である。 分類対象データの一例を示す図である。 図１に示す決定木生成装置のユーザ回答信頼度算出部が算出したユーザ回答の信頼度の一例を示す図である。 図１に示す決定木生成装置による、ユーザ回答の信頼度を考慮して決定木を生成する処理の一例を示すフローチャートである。 図４に示す決定木の生成処理の中で決定木のノードに割り当てる属性を決定する処理の一例を示すフローチャートである。 図１に示す決定木生成装置により生成された決定木の一例を示す図である。 ユーザ回答の信頼度を用いず、エントロピー減少量のみを用いて、情報ゲインを算出して生成した決定木の一例を示す図である。 本開示の一実施例の形態における決定木生成装置により生成された決定木を用いた問診対話システムの構成の一例を示す図である。 図８に示す問診対話システムの質問順序記憶部に記憶される決定木の一例を示す図である。 図９に示す決定木を図８に示す問診対話システムの質問順序記憶部に記憶するときの決定木のデータ構造の一例を示す図である。 図８に示す問診対話システムの動作の流れの一例を示すフローチャートである。 図８に示す問診対話システムで対話を行った際の表示部の表示内容の一例を示す図である。 本開示の一実施例の形態における決定木生成装置により生成された決定木を用いた他の問診対話システムの構成の一例を示す図である。 図１３に示す問診対話システムの決定木ノード履歴記憶部に記憶される決定木ノードの履歴情報の一例を示す図である。 図１３に示す問診対話システムの動作の流れの一例の一部を示すフローチャートである。 図１３に示す問診対話システムの動作の流れの一例の残部を示すフローチャートである。

（本開示の基礎となった知見）
前述した従来技術による質問順序の決定方法は、いずれも決定木による複数データの分類の考え方に基づくものである。決定木は、複数の分類対象データが複数の属性を持っており、分類対象データの各々の各属性に属性値が割り当てられている場合に、複数の属性をどのような順序でチェックし、属性値により分類していくかの順序を決定するために使用される。

ある属性の属性値としては、異なる複数の値が存在することが通常であるので、前述の属性による分類の順序は、木構造を構成する。このことから、属性による分類の順序を決定した結果は、決定木と呼ばれる。したがって、チェックする属性を質問と捉えることで、決定木を質問順序の決定に用いることができる。

また、決定木における属性チェックの順序を決めるために、情報ゲインという計算量が用いられる。情報ゲインとは、ある属性に関する属性値が何であるかに基づいて分類対象データ集合を部分集合に分割した場合に、分割前の分類対象データ集合のエントロピーから、分割後の各部分集合のエントロピーの和を引いたものと定義される。

ここで、分類対象データ集合のエントロピーとは、分類対象データ集合に含まれる分類対象データがどのカテゴリに分類されるかの確率分布に関する情報エントロピーを意味する。情報エントロピーの性質として、確率分布が一様な分布に近いほど、情報エントロピーの値は大きくなり、確率分布の偏りが大きい、言い換えると、特定の確率事象の確率が大きく、他の確率事象の確率が小さいほど、情報エントロピーの値は小さくなる。

したがって、分類対象データ集合のエントロピーは、その集合に含まれるデータの分類先カテゴリが一様に散らばっているほど大きくなり、分類先カテゴリが特定のカテゴリに偏っているほど小さくなる。このように、属性値によって分類対象データを分類することで、分類対象データ集合が特定のカテゴリへ絞り込まれる度合いが大きいほどエントロピーが小さくなることに対応する。

したがって、情報ゲインが最も大きくなる属性をチェックすることを、最優先で分類を行うように、決定木を構成することにより、少ない属性のチェック回数で分類対象データを分類することができる。すなわち、質問の回数が最も少なくなるように質問の順序を決定することができる。

例えば、後述する図２に示すｘ１、ｘ２、ｘ３、ｘ４の４つの属性について、０あるいは１の属性値が割り当てられたデータ数が８個の分類対象データ集合に関して、前述の情報ゲインに基づいて決定木を生成すると、後述する図７の決定木が得られる。

図７の○印で示すノードＮ１（符号のない○印で示すノードも同様）は、決定木のノードと呼ばれ、各ノードには、チェックする属性（ノードＮ１の場合は、ｘ１）が割り当てられている。図中の線分で示すエッジＥ１、Ｅ２（符号のない線分で示すエッジも同様）は、決定木のエッジと呼ばれ、エッジの上位に接続するノードの属性をチェックして得られる属性値の種類数に対応して配置される。例えば、エッジＥ１は、属性ｘ１の属性値１に対応するエッジであり、エッジＥ２は、属性ｘ１の属性値０に対応するエッジである。

また、決定木において、最上位にあるノード（根ノード）Ｎ１の属性が最初にチェックされる属性であり、チェックして得られた属性値によって、どのエッジを辿るかを選択し、選択したエッジの下位に接続するノードに割り当てられた属性について続けてチェックを行うことを繰り返す。

図中の○印のないノードＮ２（符号及び○印のないノードも同様）は、決定木の葉ノードと呼ばれ、各葉ノードには、分類されたカテゴリＣ１〜Ｃ８が割り当てられる。葉ノードに割り当てられたカテゴリは、根ノードから属性チェックを繰り返した結果として辿り着いた分類結果に対応する。

図７の決定木において、根ノードの属性として、ｘ１が選ばれた理由は、ｘ１，ｘ２、ｘ３、ｘ４の４つの属性のうち、属性ｘ１の属性値で分類対象データを分割したときの情報ゲインが最大となるからである。以降、下位ノードでは、上位ノードの属性値で分割された分類対象データ集合（部分集合）に対して、既にチェックした属性を除外した属性の中で情報ゲインが最大となる属性を当該ノードに割り当てるという操作を再帰的に繰り返し、チェック可能な属性が無くなるか、あるいは、分類対象データのカテゴリが１種類に定まるかの状況になるまで、上述の操作を行うのが、決定木の生成の流れである。

上述の流れによって生成された決定木で規定される属性チェックの順序は、与えられた分類対象データに対して最も属性チェック数が少なくなるものになる。言い換えれば、絞り込みが最も早く進む属性チェックの順序になっている。この分類が効率的に行われるという決定木の性質が、分類問題で決定木が用いられることが多い理由となっている。

しかしながら、従来技術による質問順序の決定方法は、質問に対するユーザ自身の回答が誤っている可能性を考慮して、決定木を生成することができないため、適切な質問順序を決定することができないという課題を有しており、さらなる改善が必要であった。

具体的には、特許文献１の手法は、複数の属性のうち属性チェックで誤る可能性のある属性を除外し、除外する属性を変化させて生成した複数の決定木を用いることにより、属性値の誤りがある状況でデータの分類の間違いを減少させる方式である。しかし、決定木が複数存在するため、対話処理における質問順序の決定に応用すると、質問を１つに決めることができないという課題を有している。

次に、特許文献２の手法は、決定木により分類誤りが起こった場合の重要性を考慮して情報ゲインを修正し、決定木を生成する方式である。しかし、決定木の入力は正しいことを前提としており、入力となる属性値が誤っている可能性は考慮していないという課題を有している。

次に、特許文献３の手法は、ユーザの回答の発話音声を音声認識した結果が誤る可能性を考慮して決定木を生成する方式である。しかし、ユーザの回答の発話音声を音声認識した結果が誤る可能性のみを考慮しており、ユーザ自身が質問に対して回答を誤る可能性を考慮できないという課題を有している。

このように、従来技術によれば、ユーザ自身の回答が誤っている可能性を考慮して、決定木を生成することができないため、適切な質問順序を決定することができないという課題が存在する。

このような課題を解決するために、本開示の一態様に係る決定木生成装置は、質問の順序を決定するために使用される決定木を生成する決定木生成装置であって、互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出する情報ゲイン算出部と、前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる決定木作成部とを備える。

このような構成により、質問に対するユーザの回答自身が誤っている可能性を考慮して質問の順序を決定することが可能になる。より具体的には、分類対象データを分割することによるデータ集合のエントロピーの減少量と、ユーザ回答の正確性又は不正確性を表す指標である信頼度とに基づいて、ユーザ回答の正確性又は不正確性を反映した情報ゲインを算出することによって、質問回数を少なくしつつ、ユーザの回答が誤ることにより、結果的に分類結果が誤る可能性を抑えるように質問順序を決定することができる。したがって、分類対象データを絞り込むのに必要な質問回数をなるべく少なくするためのエントロピーの減少分を考慮しつつ、ユーザの回答の信頼度を考慮して、絞込結果の間違いがなるべく少なくなるような質問を先に行うように質問順序を決定することができる。この結果、対話によりユーザに質問を行って、質問の回答結果から分類結果の候補を絞り込む際に、ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することが可能な決定木を生成することができる。

上記決定木生成装置は、前記属性を問う質問に対するユーザの回答の正答及び誤答の実例を含むユーザ回答実例データから前記信頼度を前記属性毎に算出する信頼度算出部をさらに備え、前記情報ゲイン算出部は、前記信頼度算出部により算出された信頼度と、前記エントロピーの減少量とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出するようにしてもよい。

このような構成により、属性を問う質問に対するユーザの回答の正答及び誤答の実例を含むユーザ回答実例データから信頼度が属性毎に算出され、算出された信頼度と、エントロピーの減少量とに基づいて、属性毎に当該属性の属性値により分割前のデータ集合を分割したときの情報ゲインを算出しているので、ユーザ回答実例データからユーザの回答の確からしさを正確に反映した信頼度を算出することができる。この結果、ユーザの回答の確からしさを正確に反映した情報ゲインを算出することができるので、質問回数を少なくしながら、分類結果が誤る可能性を抑える質問順序を決定することが可能な決定木を生成することができる。

前記信頼度は、前記属性を問う質問に対するユーザの回答の正答率を含み、前記情報ゲイン算出部は、前記エントロピーの減少量に前記正答率を乗算することにより前記情報ゲインを算出するようにしてもよい。

このような構成により、質問に対するユーザの回答の正答率をエントロピーの減少量に乗算して情報ゲインを算出しているので、ユーザの回答の正答率を反映した情報ゲインを算出することができ、質問回数をより少なくしながら、分類結果が誤る可能性をより抑える質問順序を決定することが可能な決定木を生成することができる。

前記ユーザ回答実例データは、ユーザが質問に回答するまでの回答時間をさらに含み、前記正答率は、前記回答時間と前記正答率との相関関係から求めたユーザの平均回答時間に対する正答率を含み、前記情報ゲイン算出部は、前記エントロピーの減少量に前記平均回答時間に対する正答率を乗算することにより前記情報ゲインを算出するようにしてもよい。

このような構成により、ユーザが質問に回答するまでの回答時間と正答率との相関関係からユーザの平均回答時間に対する正答率を求め、エントロピーの減少量に平均回答時間に対する正答率を乗算することにより情報ゲインを算出しているので、ユーザの回答の確からしさをより正確に反映した信頼度を算出することができる。この結果、ユーザの回答の確からしさをより正確に反映した情報ゲインを算出することができるので、質問回数をより少なくしながら、分類結果が誤る可能性をより抑える質問順序を決定することが可能な決定木を生成することができる。

前記信頼度は、所定の属性を問う質問に対して回答となる所定の属性値が得られるときの条件付きエントロピーを含み、前記情報ゲイン算出部は、前記エントロピーの減少量から前記条件付きエントロピーを減算することにより前記情報ゲインを算出するようにしてもよい。

このような構成により、所定の属性を問う質問に対して回答となる所定の属性値が得られるときの条件付きエントロピーをエントロピーの減少量から減算することにより情報ゲインを算出しているので、条件付きエントロピーによりユーザの回答の不確かさを正確に反映した情報ゲインを算出することができ、質問回数をより少なくしながら、分類結果が誤る可能性をより抑える質問順序を決定することが可能な決定木を生成することができる。

前記ユーザ回答実例データは、ユーザの属性を表すユーザ情報をさらに含み、前記信頼度算出部は、前記ユーザの属性毎に、前記ユーザ回答実例データから前記信頼度を前記属性毎に算出し、前記情報ゲイン算出部は、前記信頼度と、前記エントロピーの減少量とに基づいて、前記情報ゲインを前記ユーザの属性毎に算出するようにしてもよい。

このような構成により、信頼度とエントロピーの減少量とに基づいて情報ゲインをユーザの属性毎に算出しているので、ユーザの属性に適した情報ゲインを算出することができ、ユーザの属性に応じて、質問回数をより少なくしながら、分類結果が誤る可能性をより抑える質問順序を決定することが可能な決定木を生成することができる。

本開示の他の態様に係る質問システムは、質問に対するユーザの回答から分類結果を生成する質問システムであって、上記の決定木生成装置により生成された決定木を記憶する記憶部と、前記記憶部に記憶された決定木に応じた質問を出力する質問部と、前記質問部による質問に対するユーザの回答を取得する取得部と、前記取得部により取得された回答に応じた分類結果を生成する生成部とを備える。

このような構成により、対話によりユーザに質問を行って、質問の回答結果から分類結果の候補を絞り込む際に、ユーザ自身の回答が誤っている場合でも、ユーザに対する必要な質問回数を削減することができる。

上記質問システムは、前記質問部による質問の順序を表す質問順序情報と、前記質問部による質問に対応する属性を識別するための属性識別情報と、前記質問部による質問の回答となる属性値と、前記質問部による質問に対応する属性の信頼度とを記憶する履歴記憶部をさらに備え、前記生成部は、前記分類結果を生成した後、前記履歴記憶部を参照して所定値より正確性が低い信頼度を有する属性を問う質問を再度行うようにしてもよい。

このような構成により、一旦得られた分類結果に対して、ユーザ回答の正確性が所定の閾値より低い質問に関して、再度質問することができるので、得られる分類結果の正確性をより高めることができる。

また、本開示は、以上のような特徴的な構成を備える決定木生成装置として実現することができるだけでなく、決定木生成装置が備える特徴的な構成に対応する特徴的な処理を実行する決定木生成方法などとして実現することもできる。また、このような決定木生成方法に含まれる特徴的な処理をコンピュータに実行させるコンピュータプログラムとして実現することもできる。したがって、以下の他の態様でも、上記の決定木生成装置と同様の効果を奏することができる。

本開示の他の態様に係る決定木生成方法は、質問の順序を決定するために使用される決定木を生成する決定木生成装置における決定木生成方法であって、互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出し、前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる。

本開示の他の態様に係る決定木生成プログラムは、質問の順序を決定するために使用される決定木を生成する決定木生成装置として、コンピュータを機能させるための決定木生成プログラムであって、前記コンピュータに、互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出し、前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる、処理を実行させる。

そして、上記のようなコンピュータプログラムを、ＣＤ−ＲＯＭ等のコンピュータ読み取り可能な非一時的な記録媒体あるいはインターネット等の通信ネットワークを介して流通させることができるのは、言うまでもない。

また、本開示の一実施の形態に係る決定木生成装置の構成要素の一部とそれ以外の構成要素とを複数のコンピュータに分散させたシステムとして構成してもよい。

なお、以下で説明する実施の形態は、いずれも本開示の一具体例を示すためのものである。以下の実施の形態で示される数値、形状、構成要素、ステップ、ステップの順序などは、一例であり、本開示を限定する主旨ではない。また、以下の実施の形態における構成要素のうち、最上位概念を示す独立請求項に記載されていない構成要素については、任意の構成要素として説明される。また、全ての実施の形態において、各々の内容を組み合わせることもできる。
（実施の形態）
以下、本開示の実施の形態について、図面を参照しながら説明する。図１は、本開示の一実施の形態における決定木生成装置の構成の一例を表すブロック図である。図１に示す決定木生成装置は、決定木作成部１１、情報ゲイン算出部１２、ユーザ回答信頼度算出部１３、分類対象データ記憶部１４、ユーザ回答事例データ記憶部１５及び質問順序決定結果記憶部１６を備える。

分類対象データ記憶部１４は、互いに異なる複数の属性の各々に対して複数の属性値のうちの一つが割り当てられた複数の分類対象データを含む分類対象データを記憶する。分類対象データは、質問順序決定結果記憶部１６に格納される質問順序決定結果（決定木）を生成するためのデータであり、複数の分類対象データが、分類対象データ集合として記憶される。各分類対象データは、データを識別するためのデータＩＤ（識別情報）と、質問の内容に対応する属性毎に記憶される、質問に対する回答に対応する属性値と、分類結果に対応するカテゴリとを含む。

図２は、分類対象データ集合の内容の一例を示す図である。この例では、各分類対象データに対して、ｘ１、ｘ２，ｘ３、ｘ４の４つの属性毎に、属性値（１あるいは０）が付与されている。さらに、各分類対象データがどの分類カテゴリに分類されるべきかを示すカテゴリ（Ｃ１〜Ｃ８）が付与されている。このようなデータ構造を有する分類対象データが、分類対象データ記憶部１４に記憶されている。

なお、本実施の形態では、後述するように、問診に対する回答から診断結果を分類する処理を例に説明しているが、本開示が適用される処理は、この例に特に限定されず、電子商取引等の顧客管理システムや販売システムにおいて、対話によりユーザに質問を行って質問の回答結果から、食品、商品、音楽コンテンツ、映像コンテンツ等を検索した検索結果の候補を絞り込む処理に適用したり、メンテナンスシステムにおいて、車、機器等の不具合を診断するメンテナンス処理に適用したり、占い、性格判断等の種々のアプリケーション処理にも同様に適用することができる。

ユーザ回答事例データ記憶部１５は、分類対象データの属性を問う質問に対するユーザの回答の正答及び誤答の実例を含むユーザ回答事例データを記憶する。具体的には、ユーザ回答事例データは、分類対象データ記憶部１４に記憶されている分類対象データの各属性について、ユーザに対して質問を行って得た回答の結果を蓄積し、なおかつ、属性に関する質問に対してユーザから得られた回答がユーザの状態を正しく反映したものであったかの事例を収集したデータである。

例えば、ユーザ回答事例データは、問診のユースケースの場合、質問は「頭痛がありますか？」、「めまいがありますか？」といった、ユーザの自覚症状に関するものになるが、これに対して自覚症状についての回答が、ユーザの症状を正しく反映していたかを検証したデータである。頭痛の症状が無い場合に「頭痛がありますか？」に対して「ありません」と回答した場合は、正しく反映した事例（正答の事例）となり、「あります」と回答した場合は、正しく反映していない事例（誤答の事例）となる。

頭痛のように比較的自覚症状が明確に知覚できる場合は、ユーザは正しく回答できる割合が高くなり、めまいのように明確に知覚することがやや難しい場合は、ユーザは正しく回答できる割合が低くなると考えられる。

ユーザ回答信頼度算出部１３は、ユーザ回答事例データ記憶部１５のユーザ回答事例データを集計して、属性に関する質問に対してユーザの回答が正しく得られる割合（正答率）を、属性を問う質問に対するユーザの回答の正確性を表す指標である信頼度として属性毎に算出する。

図３は、ユーザ回答信頼度算出部１３が算出した属性毎のユーザ回答の信頼度の一例を示す図である。図３に示す例では、属性ｘ１の信頼度すなわち属性ｘ１を問う質問に対する回答の正答率は６０％であり、以下同様に、属性ｘ２、ｘ３、ｘ４の信頼度はそれぞれ８０％、９０％、７０％であり、属性ｘ３の正答率が最も高く、属性ｘ１の正答率が最も低くなっている。ユーザ回答信頼度算出部１３で算出した、属性に関する質問の回答の信頼度は、情報ゲイン算出部１２において、情報ゲインを算出する際の入力として用いられる。

情報ゲイン算出部１２は、互いに異なる複数の属性の各々に対して複数の属性値のうちの一つが割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる分類対象データの属性毎に、分割によるデータ集合のエントロピーの減少量を算出する。また、情報ゲイン算出部１２は、算出したエントロピーの減少量と、ユーザ回答信頼度算出部１３により算出された信頼度とに基づいて、属性毎に当該属性の各属性値により分割前のデータ集合を分割したときの情報ゲインを算出する。

決定木作成部１１は、分類対象データ記憶部１４に記憶されている分類対象データを入力とし、情報ゲイン算出部１２により算出された属性毎の情報ゲインを用いて、分類対象データを分類するための属性チェック（質問）の順序を決定木の形で生成する。具体的には、決定木作成部１１は、情報ゲイン算出部１２が属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の各属性値により分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当て、分類対象データから決定木を作成する。

質問順序決定結果記憶部１６は、決定木作成部１１によって作成された決定木である質問順序決定結果を記憶する。

なお、本実施の形態の決定木生成装置の構成は、上記の例に特に限定されず、分類対象データ記憶部１４、ユーザ回答事例データ記憶部１５及び質問順序決定結果記憶部１６の一部又はすべてを省略し、外部のサーバ等から分類対象データやユーザ回答事例データを取得したり、決定木作成部１１によって作成された決定木のデータを外部の記憶装置に記憶するようにしてもよい。また、ユーザ回答信頼度算出部１３を省略し、外部のサーバ等から信頼度を取得してもよい。

次に、上記のように構成された決定木生成装置により決定木を生成する処理について図４のフローチャートに沿って説明する。

図４において、まず、決定木作成部１１は、分類対象データ記憶部１４から全ての分類対象データを読み出し、分類対象データの全体を属性値の選択対象とするデータ集合Ｄの初期値として設定する（ステップＳ１０１）。

次に、決定木作成部１１は、データ集合Ｄに関して、決定木の終端の条件を満たしているかを判定する（ステップＳ１０２）。具体的には、決定木作成部１１は、データ集合Ｄに含まれる分類対象データのカテゴリが１種類に絞られている、あるいは、データ集合Ｄに含まれる分類対象データの属性がすべてノードに割り当て済みであり、新たにノードに割り当てるべき属性が無い、という条件を満たしている場合に、決定木の終端の条件を満たしていると判定する。

ステップＳ１０２の条件判定が「ＹＥＳ」の場合は、決定木作成部１１は、データ集合Ｄに含まれる分類対象データに付与されたカテゴリを葉ノードに割り当て（ステップＳ１０８）、その後、処理を終了する。

一方、ステップＳ１０２の条件判定が「ＮＯ」の場合は、決定木作成部１１は、データ集合Ｄに関して、各属性に関する情報ゲインを情報ゲイン算出部１２に算出させ、情報ゲインが最大となる属性を、データ集合Ｄを分割する属性（質問）ｘとして決定する（ステップＳ１０３）。

ここで、ステップＳ１０３の処理の詳細について、図５のフローチャートに沿って説明する。

図５において、まず、決定木作成部１１は、情報ゲインの最大値を保持する変数（Ｇ＿ｍａｘ）と、情報ゲインの最大値を与える属性を保持する変数（ｘ＿ｍａｘ）を、それぞれ、０、及び、空の値（φ）に初期化する（ステップＳ２０１）。

次に、決定木作成部１１は、データ集合Ｄで割り当て済みとマーキングされていない属性の中から、まだ情報ゲインを算出していない属性があるかを調べる（ステップＳ２０２）。

ステップＳ２０２で情報ゲインを算出していない属性が無い場合は、決定木作成部１１は、変数ｘ＿ｍａｘに保持されている属性を、データ集合を分割する属性として決定し（ステップＳ２０９）、図４に示すステップＳ１０４に戻る。

ステップＳ２０２で情報ゲインを算出していない属性がある場合は、決定木作成部１１は、情報ゲインを算出していない属性ｘを取り出す（ステップＳ２０３）。

次に、決定木作成部１１は、属性ｘの属性値の種類によりエントロピー減少量Ｈを算出するように情報ゲイン算出部１２に指示し、情報ゲイン算出部１２は、属性ｘの属性値の種類によりエントロピー減少量Ｈを算出する（ステップＳ２０４）。具体的には、情報ゲイン算出部１２は、下記の式（１）によりエントロピー減少量Ｈを算出する。

ここで、式（１）の右辺の前半の和は、属性ｘで分割する前のデータ集合Ｄのエントロピーであり、データ集合Ｄに含まれる分類対象データに付与されたカテゴリＣｉ（ここで、ｉはカテゴリーの添字）の出現確率の情報エントロピーの和をとったものである。また、式（１）の右辺の後半の和は、属性ｘの属性値ｘｊ（ここで、ｊは属性値の添字）で分割したデータ集合の各部分集合Ｄｊについてのエントロピーであり、部分集合Ｄｊ毎に、上述と同様にカテゴリＣｉの出現確率の情報エントロピーを求め、属性値ｘｊの出現確率を乗算した上で、和をとったものである。

次に、情報ゲイン算出部１２は、属性ｘを質問した場合のユーザ回答の信頼度Ｂを算出するようにユーザ回答信頼度算出部１３に指示し、ユーザ回答信頼度算出部１３は、属性ｘを質問した場合のユーザ回答の信頼度Ｂを算出して情報ゲイン算出部１２へ出力する（ステップＳ２０５）。

次に、情報ゲイン算出部１２は、エントロピー減少量Ｈと、信頼度Ｂとを用いて、
下記の式（２）により、情報ゲインＧを算出し、算出した情報ゲインＧを決定木作成部１１へ出力する（ステップＳ２０６）。

Ｇ＝Ｈ×Ｂ … （２）
次に、決定木作成部１１は、情報ゲインＧが最大の情報ゲインの値Ｇ＿ｍａｘよりも大きい値かを判定する（ステップＳ２０７）。

ステップＳ２０７でＧ＞Ｇ＿ｍａｘであれば、決定木作成部１１は、Ｇ＿ｍａｘを情報ゲインＧで更新するとともに、ｘ＿ｍａｘを属性ｘで更新し（ステップＳ２０８）、ステップＳ２０２に戻り、以降の処理を繰り返す。一方、ステップＳ２０７でＧ＞Ｇ＿ｍａｘでなければ、決定木作成部１１は、何もせず、ステップＳ２０２に戻り、以降の処理を繰り返す。

上記の処理により、データ集合Ｄに関して、各属性の情報ゲインを算出し、算出した情報ゲインから最大の情報ゲインを特定し、最大の情報ゲインを有する属性を、データ集合Ｄを分割する属性ｘとして決定することができる。

図４のフローチャートに戻って、決定木作成部１１は、ステップＳ１０３でデータ集合Ｄを分割する属性ｘを決定した後、属性ｘのノードを作成する（ステップＳ１０４）。

次に、決定木作成部１１は、属性ｘの各属性値ｘｊ（ｊ＝１，２，…）に基いてデータ集合Ｄを分割後のデータ集合である複数の部分集合Ｄｊ（ｊ＝１，２，…）に分割し、属性ｘの各属性値ｘｊをノードのエッジに割り当てる（ステップＳ１０５）。

次に、決定木作成部１１は、各部分集合Ｄｊについて、属性ｘを割り当て済みとしてマーキングする（ステップＳ１０６）。

次に、決定木作成部１１は、各部分集合Ｄｊについて、Ｄ＝Ｄｊと置き、ステップＳ１０２から以降の処理を再帰的に実行する（ステップＳ１０７）。

以上の処理により、決定木作成部１１は、分類対象データから質問順序決定結果となる決定木を生成し、質問順序決定結果記憶部１６に記憶する。

図６は、図２の分類対象データ集合を、上述の処理フローに沿って、図３のユーザ回答の信頼度を用いて、情報ゲインを算出することにより生成した決定木の一例を表す図であり、図７は、ユーザ回答の信頼度を用いず、エントロピー減少量のみを用いて、情報ゲインを算出して生成した決定木の一例を表す図である。なお、図６及び図７において、決定木のノード、エッジ、カテゴリ、属性及び属性値の表記方法は共通である。

図７に示す決定木では、ユーザ回答の信頼度を用いず、エントロピー減少量のみを用いて、情報ゲインを算出しているため、根ノードＮ１に割当られた属性は、属性ｘ１であるが、図６に示す決定木では、エントロピー減少量にユーザ回答の信頼度を乗算して求めた情報ゲインを用いているため、根ノードＮ１に割り当てられた属性は、属性ｘ３である。

これは、図３に示す例では、属性ｘ１に関する質問のユーザ回答の信頼度は６０％であり、他の属性に比べて低い値なので、属性ｘ１に関する情報ゲインが他の属性の情報ゲインよりも小さくなり、最大の情報ゲインを与える属性が属性ｘ３となるためである。このように、本実施の形態では、属性に関するユーザ回答の信頼度を考慮して決定木を生成することができるので、より質問回数の少ない質問の順序を決定することができる。

なお、本実施の形態においては、ユーザ回答の正答率を信頼度として用い、情報ゲインを式（２）により求めたが、ユーザ回答の信頼度を求める方法は、上記の例に特に限定されず、種々の変更が可能である。

例えば、問診において、質問してからユーザが回答するまでの時間と、回答が正解している率の相関を求め、質問をした際にユーザが回答するまでの時間の平均値からユーザの回答の正解率を求めることもできる。

この場合、ユーザ回答事例データ記憶部１５は、属性を問う質問に対するユーザの回答の正答及び誤答の実例と、ユーザが各質問に回答するまでの回答時間とを含むユーザ回答実例データを記憶し、ユーザ回答信頼度算出部１３は、ユーザ回答実例データから回答時間と正答率との相関関係を求め、求めた相関関係からユーザの平均回答時間に対する正答率を算出し、情報ゲイン算出部１２は、エントロピーの減少量に平均回答時間に対する正答率を乗算することにより情報ゲインを算出する。

また、ユーザ回答の信頼度は、ユーザの属性によって異なるものとして扱うことも可能である。例えば、年齢、性別、幼児、小学生、中学生、高校生、大学生、社会人、職業などの個人的属性でユーザ回答実例データを区別して、ユーザの属性毎にユーザ回答の信頼度を計算しておき、質問に回答するユーザの実際の属性でユーザ回答の信頼度を選択してもよい。

この場合、ユーザ回答事例データ記憶部１５は、属性を問う質問に対するユーザの回答の正答及び誤答の実例と、ユーザの属性を表すユーザ情報とを含むユーザ回答実例データを記憶し、ユーザ回答信頼度算出部１３は、ユーザの属性毎に正答率を算出し、情報ゲイン算出部１２は、エントロピーの減少量にユーザの属性毎に求められた正答率を乗算することによりユーザの属性毎に情報ゲインを算出する。

また、ユーザ毎に過去の問診時における回答状況からユーザ回答の信頼度をユーザ毎に計算して用いてもよい。

さらに、本実施の形態では、情報ゲインＧを式（２）により求めたが、エントロピー減少量と、ユーザ回答の信頼度とから求める情報ゲインの計算方法は、上記の例に特に限定されず、種々の変更が可能である。例えば、ユーザ回答の信頼度Ｂ’を、症状（属性）ｘに関する質問に対して回答（属性値）ｙが得られる時の条件付きエントロピーＨ（Ｙ｜Ｘ）として、式（３）に基づいて求め、求めた信頼度Ｂ’と、式（１）で求めたエントロピー減少量Ｈとを用いて、式（４）に基づいて情報ゲインＧ’を算出してもよい。

Ｇ’＝Ｈ−Ｂ’ … （４）
このときのユーザ回答の信頼度Ｂ’は、ユーザが症状ｘを実際に発症している確率をＰ（Ｘ）として、症状ｘを発症している場合、あるいは、発症していない場合に、症状ｘが「ある」あるいは「ない」と答える条件付き確率Ｐ（Ｙ｜Ｘ）のエントロピーを計算したものである。すなわち、ユーザ回答の信頼度Ｂ’は、ユーザ回答の不確かさ（不正確性）を情報量（エントロピー）の大小で表したものであり、属性を問う質問に対するユーザの回答の不正確性を表す指標である。この信頼度Ｂ’に基づけば、症状（属性）ｘを問う質問により得られる情報ゲイン、つまり、エントロピー減少量Ｈは、信頼度Ｂ’の分だけ割り引かれるとして、式（４）で表した計算によって得ることができる。

この場合、ユーザ回答信頼度算出部１３は、所定の属性を問う質問に対して回答となる所定の属性値が得られるときの条件付きエントロピーを信頼度Ｂ’として算出し、情報ゲイン算出部１２は、エントロピー減少量Ｈから条件付きエントロピーである信頼度Ｂ’を減算することにより情報ゲインＧ’を算出する。このように、属性を問う質問に対するユーザの回答の不正確性を表す指標である信頼度Ｂ’を用いた場合でも、属性を問う質問に対するユーザの回答の正確性を表す指標である信頼度Ｂを用いた場合と同様の効果を得ることができる。

次に、上記の決定木生成装置により生成された決定木を用いて、質問に対するユーザの回答から分類結果を生成する質問システムの一例である問診システムについて説明する。

図８は、本開示の一実施の形態における決定木生成装置により生成された質問順序決定結果（決定木）を組み込んだ音声対話による問診システムの構成を表すブロック図である。図８に示すように、問診システムは、音声入力部５０１、音声認識部５０２、言語理解部５０３、ユーザ回答結果処理部５０４、質問順序記憶部５０５、現在決定木ノード記憶部５０６、問診制御部５０７、言語生成部５０８、音声合成部５０９、音声出力部５１０及び表示部５１１を備える。

質問順序記憶部５０５は、図１に示す決定木生成装置により生成された決定木を記憶する。言語生成部５０８、音声合成部５０９及び音声出力部５１０は、質問順序記憶部５０５に記憶された決定木に応じた質問を出力する。音声入力部５０１、音声認識部５０２及び言語理解部５０３は、上記の質問に対するユーザの回答を取得する。ユーザ回答結果処理部５０４、現在決定木ノード記憶部５０６及び問診制御部５０７は、取得された回答に応じた分類結果を生成し、表示部５１１は、分類結果の説明文を表示する。

ここで、本問診システムでは、質問順序記憶部５０５が記憶部の一例に相当し、言語生成部５０８、音声合成部５０９及び音声出力部５１０が質問部の一例に相当し、音声入力部５０１、音声認識部５０２及び言語理解部５０３が取得部の一例に相当し、ユーザ回答結果処理部５０４、現在決定木ノード記憶部５０６及び問診制御部５０７が生成部の一例に相当する。

図９は、質問順序記憶部５０５の内容となる決定木の一例を示す図であり、図１０は、図９に示す決定木を質問順序記憶部５０５に記憶するときの決定木のデータ構造の一例を示す図である。図１に示す決定木生成装置により、例えば、図９に示す決定木が生成された場合、質問順序記憶部５０５は、図１０に示すデータ構造を用いて図９に示す決定木を記憶している。

ここで、質問順序を表す決定木の各ノードに記された記号がノードＩＤである。質問順序記憶部５０５では、この決定木のデータ構造が、ノード毎に、ノードＩＤと、ノードの属性に対応する質問であるか、又は、問診結果であるかを表すノード内容と、ノード内容が質問を表し、当該質問に対するユーザの回答が、ＹＥＳ回答の場合に次に進むべきノードのノードＩＤと、ノード内容が質問を表し、当該質問に対するユーザの回答が、ＮＯ回答の場合に次に進むべきノードのノードＩＤとを対応付けて格納したデータとして記憶される。

例えば、「ノードＩＤ」が「０」の場合、「ノード内容」にノードの属性を問う質問を表す「ＹＥＳ＿ＮＯ（頭痛）」が格納され、ＹＥＳ回答の場合に次に進むべきノードのノードＩＤを表す「ＹＥＳ」に「１」が格納され、ＮＯ回答の場合に次に進むべきノードのノードＩＤを表す「ＮＯ」に「２」が格納されている。また、「ノードＩＤ」が「３」の場合、「ノード内容」に問診結果を表す「ＤＩＡＧ（ＶＶＶ）」が格納され、ノードの内容が問診結果であるため、「ＹＥＳ」及び「ＮＯ」にデータは格納されていない。

図１１は、図８に示す問診システムの動作の流れを示すフローチャートである。ここでは、図１１のフローチャートに沿って、図８のブロック図の各構成部の動作を説明しつつ、問診システムの動作について説明する。

まず、問診制御部５０７は、現在決定木ノード記憶部５０６に保持されている現在決定木ノードのＩＤを、質問順序記憶部５０５の決定木の根ノードのノードＩＤに初期化する（ステップＳ３０１）。

次に、問診制御部５０７は、現在決定木ノード記憶部５０６に保持されている現在決定木ノードを参照してノードＩＤを取得する（ステップＳ３０２）。具体的には、問診制御部５０７は、ノードを識別するノードＩＤを取得する。

次に、問診制御部５０７は、取得したノードＩＤのノード内容を質問順序記憶部５０５から取得して、ノードが葉ノードかどうかを判定する（ステップＳ３０３）。ノード内容が質問（例えば、ＹＥＳ＿ＮＯ（ＡＡＡ）、「ＡＡＡ」は症状）の場合は、葉ノードではなく、ノード内容が問診結果（例えば、ＤＩＡＧ（ＺＺＺ）、「ＺＺＺ」は問診結果）の場合は、葉ノードである。

ステップＳ３０３で葉ノードの場合は、問診制御部５０７は、ノード内容である問診結果（例えば、「ＺＺＺ」）を言語生成部５０８に送り、言語生成部５０８は、問診結果を自然言語の説明文（例えば、「ＺＺＺという病気の可能性があります。」）に変換し、当該説明文を音声合成部５０９に送るとともに、表示部５１１に送り、表示部５１１は、説明文をテキスト表示する（ステップＳ３１２）。

次に、音声合成部５０９は、説明文を音声合成し（ステップＳ３１３）、音声出力部５１０は、音声合成部５０９で合成された音声信号を出力し（ステップＳ３１４）、ユーザが説明文を音声で聞き取れるようにし、処理を終了する。

ステップＳ３０３で葉ノードではない場合は、問診制御部５０７は、ノード内容である質問（例えば、「ＡＡＡ」）を言語生成部５０８に送り、言語生成部５０８は、質問を自然言語の質問文（例えば、「ＡＡＡ」はありますか）に変換し、表示部５１１に送るとともに、当該質問文を音声合成部５０９に送り、表示部５１１は、質問文をテキスト表示する（ステップＳ３０４）。

次に、音声合成部５０９は、当該質問文の読み上げ音声信号を合成し（ステップＳ３０５）、音声出力部５１０は、音声合成部５０９で合成された音声信号を出力し（ステップＳ３０６）、ユーザが質問文を音声で聞き取れるようにする。

ここで、ユーザは、音声出力された質問文に対して自身の自覚に基づき、回答を発話する。音声入力部５０１は、常に音声入力を待ち受けており（ステップＳ３０７）、ユーザ発話による音声入力を検知したかどうかを判定する（ステップＳ３０８）。

ステップＳ３０８で音声入力を検知しなかった場合は、音声入力部５０１は、ステップＳ３０７に戻り、引き続き音声入力の待受状態を継続する。一方、ステップＳ３０８で音声入力を検知した場合は、音声入力部５０１は、音声入力の終端部を検知して、終端部までの音声入力を音声信号として音声認識部５０２に送る。

次に、音声認識部５０２は、音声信号を音声認識処理により音声認識結果である文字列に変換するとともに、言語理解部５０３及び表示部５１１に送り、表示部５１１は、文字列を表示する（ステップＳ３０９）。

次に、言語理解部５０３は、音声認識結果の文字列を受け取り、文字列を言語解析し、ユーザ発話の意味情報に変換する（ステップＳ３１０）。本実施の形態に係る問診システムでは、ユーザの回答の発話は、自覚症状の有無を問う質問に対する回答になるので、質問された症状を自覚したと回答した場合の回答の意味情報「ＹＥＳ」、あるいは、質問された症状を自覚していないと回答した場合の回答の意味情報「ＮＯ」の２種類のみである。したがって、言語理解部５０３は、音声認識結果の文字列を「ＹＥＳ」、「ＮＯ」のいずれかの意味情報に変換する。

次に、ユーザ回答結果処理部５０４は、現在決定木ノード記憶部５０６に保持されている現在決定木ノードのＩＤを取得し、言語理解部５０３が変換した意味情報に従って、当該ノードＩＤのＹＥＳ回答の場合のノードＩＤ、あるいは、ＮＯ回答の場合のノードＩＤのいずれかをを選択し、次に進むべきノードＩＤを決定し、現在決定木ノード記憶部５０６の現在決定木ノードのＩＤを、決定したノードＩＤで更新し、ステップＳ３０２に戻る（ステップＳ３１１）。

以上の処理フローにより、ユーザは問診システムからの質問に回答していくことで、自覚症状から最も可能性の高い診断結果を知ることができる。

図１２は、図１０で例示した質問順序記憶部５０５の質問順序を表す決定木に従って、質問を生成し、ユーザが回答した際の表示部５１１に表示された、問診のやりとりの様子の一例である。

図１０の質問順序では、頭痛などの明確に自覚できる症状の質問が先にあり、めまいなどの明確に自覚しにくい症状の質問が後になるようになっている。したがって、ユーザが自覚症状を間違えて回答する可能性がある場合に、なるべく診断結果の誤りの可能性が小さくなるように問診を行うことができる。

さらに、本開示の一実施の形態における決定木生成装置により生成した質問順序決定結果を組み込んだ音声対話による問診システムにおいて、図１０の処理に従って問診結果を得た時点で、これまでに行った質問に関するユーザ回答の正確性が低いことを考慮して、再度、同じ質問を行い、二度目の質問に対してユーザ回答が変化するかどうかを確認し、得られた問診結果の確実性を高めることもできる。

図１３は、本開示の一実施例の形態における決定木生成装置により生成された決定木を用いた他の問診対話システムの構成の一例を示す図である。図１３に示す問診対話システムは、再度質問を行うことで問診結果の確実性を高める問診システムである。

ここで、図１３に示す問診対話システムが図８に示す問診対話システムと異なる点は、ユーザ回答結果処理部５０４及び問診制御部５０７がユーザ回答結果処理部５０４Ａ及び問診制御部５０７Ａに変更され、決定木ノード履歴記憶部５１２が追加された点であり、その他の点は図８に示す問診対話システムと同様であるので、詳細な説明は省略する。

図１４は、決定木ノード履歴記憶部５１２に記憶される決定木ノードの履歴情報の一例を示す図である。図１４に示す決定木ノードの履歴情報では、履歴テーブルの各行が１つの決定木ノードの履歴情報を表しており、最も左の欄は、問診における質問の順序番号、その右隣の欄は、決定木のノードＩＤ、その右隣の欄は、決定木のノードＩＤに対応する質問に対するユーザの回答結果、その右隣は、決定木のノードＩＤにより特定される属性を問う質問に対するユーザ回答の信頼度の値（正答率）である。

このように、決定木ノード履歴記憶部５１２は、質問の順序を表す質問順序情報となる質問の順序番号と、質問に対応する属性を識別するための属性識別情報となる決定木のノードＩＤと、質問の回答となる属性値を表すユーザの回答結果と、質問に対応する属性の信頼度とを記憶する。

問診制御部５０７Ａは、問診が進む過程で、決定木のどのノードが質問として使われたのかの履歴を決定木ノード履歴記憶部５１２に記録する。具体的には、現在決定木ノード記憶部５０６に記憶される決定木ノードが更新される度に、決定木ノード履歴記憶部５１２に記憶されている履歴テーブルの末尾に質問として使用された決定木ノードの履歴情報が記録される。

問診制御部５０７Ａは、問診結果が決定した後に、決定木ノード履歴記憶部５１２を参照し、所定値より正確性が低い信頼度を有する属性を問う質問を再度行う。また、問診制御部５０７Ａは、問診結果が決定した後に、決定木ノード履歴記憶部５１２を参照し、問診結果が確定した決定木ノード（一番末尾の決定木ノードの履歴情報）から遡る形で、再度質問を行うように動作してもよい。

ユーザ回答結果処理部５０４Ａは、再度の質問に対するユーザの回答と、決定木ノード履歴記憶部５１２の決定木ノードの履歴情報が示すユーザ回答結果とが一致するかどうかを判定する。

問診制御部５０７Ａは、再度の質問に対するユーザの回答と、決定木ノード履歴記憶部５１２の決定木ノードの履歴情報が示すユーザ回答結果とが一致しない場合、回答が一致しない質問から再度問診をやり直すように動作する。

ここで、本問診システムでは、質問順序記憶部５０５が記憶部の一例に相当し、言語生成部５０８、音声合成部５０９及び音声出力部５１０が質問部の一例に相当し、音声入力部５０１、音声認識部５０２及び言語理解部５０３が取得部の一例に相当し、ユーザ回答結果処理部５０４Ａ、現在決定木ノード記憶部５０６及び問診制御部５０７Ａが生成部の一例に相当し、決定木ノード履歴記憶部５１２が履歴記憶部の一例に相当する。

図１５は、図１３に示す問診対話システムの動作の流れの一例の一部を示すフローチャートであり、図１６は、図１３に示す問診対話システムの動作の流れの一例の残部を示すフローチャートである。

ここで、図１５及び図１６に示す処理が図１１に示す処理と異なる点は、ステップＳ３０１、Ｓ３０２がステップＳ３０１Ａ、Ｓ３０２Ａに変更され、ステップ３１４の後に、図１６に示す処理が追加された点であり、その他の点は図１１に示す処理と同様であるので、詳細な説明は省略する。

ステップＳ３０１Ａでは、問診制御部５０７Ａは、現在決定木ノード記憶部５０６の初期化に加えて、決定木ノード履歴記憶部５１２の初期化を行う。ステップＳ３０２Ａでは、問診制御部５０７Ａは、現在決定木ノード記憶部５０６の決定木ノードのＩＤを参照するとともに、参照した決定木ノードのＩＤの情報を決定木ノード履歴記憶部５１２の履歴テーブルの末尾に追加する。

以降、図１１に示す処理と同様の処理が実行され、問診結果が決定してステップＳ３１４の処理が実行された後、図１６に示すステップＳ４０１以降の処理が実行され、再質問処理が行われる。また、図１６に示す再質問処理において、ステップＳ３０５〜Ｓ３１０、Ｓ３１３〜Ｓ３１４の処理は、図１１に示すステップＳ３０５〜Ｓ３１０、Ｓ３１３〜Ｓ３１４の処理と同じ処理であるため、詳細な説明を省略する。

図１６に示す再質問処理において、まず、問診制御部５０７Ａは、質問順序変数Ｑを、決定木ノード履歴記憶部５１２の最も末尾の質問順序の番号で初期化する（ステップＳ４０１）。

次に、問診制御部５０７Ａは、決定木ノード履歴記憶部５１２を参照し、質問順序変数Ｑが示す位置の１つ前の質問順序の位置に決定木ノードの履歴情報があり、且つ、その決定木ノードの履歴情報内のユーザ回答の信頼度が所定の信頼度の値（所定の閾値）より低いかどうかを判定する（ステップ４０２）。

ステップ４０２において、上記の２つの条件の両者が満たされない場合は、再度問診をする必要がないので、問診制御部５０７Ａは、ユーザに問診結果の変更が無いことを通知するための問診結果変更無文を生成することを言語生成部５０８に指示し、言語生成部５０８は、問診結果変更無文を合成し、当該問診結果変更無文を音声合成部５０９に送るとともに、表示部５１１に送り、表示部５１１は、問診結果変更無文をテキスト表示する（ステップＳ４０６）。

その後、ステップＳ３１３〜Ｓ３１４までの処理が図１１と同様に実行され、音声合成部５０９は、問診結果変更無文を音声合成し（ステップＳ３１３）、音声出力部５１０は、音声合成部５０９で合成された音声信号を出力し（ステップＳ３１４）、ユーザが問診結果変更無文を音声で聞き取れるようにし、処理を終了する。

一方、ステップ４０２において、上記の２つの条件の両者が満たされた場合は、問診制御部５０７Ａは、質問順序変数Ｑを１マイナスする（ステップＳ４０３）。次に、問診制御部５０７Ａは、質問順序変数Ｑの位置にある決定木ノードの履歴情報のノードＩＤを有する属性に対応する質問を言語生成部５０８に送り、言語生成部５０８は、質問順序変数Ｑの位置にある決定木ノードの履歴情報のノードＩＤを有する属性を問う質問文を合成し、当該質問文を音声合成部５０９に送るとともに、表示部５１１に送り、表示部５１１は、質問文をテキスト表示する（ステップＳ４０４）。

その後、ステップＳ３０５〜Ｓ３１０までの処理が図１１と同様に実行され、ステップＳ３１０の処理結果（ユーザ発話の言語理解結果）を受け取ったユーザ回答結果処理部５０４Ａは、決定木ノード履歴記憶部５１２の質問順序変数Ｑの位置にある決定木ノードの履歴情報内のユーザの回答結果と、今受け取ったユーザ発話の言語理解結果とが一致するかどうかを判定する（ステップＳ４０５）。

ステップＳ４０５で、決定木ノード履歴記憶部５１２のユーザの回答結果と言語理解結果とが一致する場合は、ユーザに同じ質問をしても回答が変わらなかったので、当該の回答は確からしいとして、さらに１つ前の質問へ遡るために、ステップＳ４０２に戻る。

一方、ステップＳ４０５で、決定木ノード履歴記憶部５１２のユーザの回答結果と言語理解結果と一致しない場合は、ユーザが前回の回答を覆したので、再度、当該の質問を行った箇所から問診をやり直すために、問診制御部５０７Ａは、質問順序記憶部５０５を参照して、ユーザの回答結果に応じて、次に進むべきノードＩＤを決定し、決定したノードＩＤを現在決定木ノードのＩＤとして現在決定木ノード記憶部５０６に書き込む（ステップＳ４０７）。その後、図１５のステップＳ３０２Ａに戻り、問診のやり直しの動作に入る。

以上の処理により、本問診対話システムでは、一旦得られた問診結果に対して、ユーザ回答の信頼度が所定の閾値より低い質問に関して、再度質問することができるので、一度目のユーザ回答が確からしいかどうかを確認し、再質問に対するユーザの回答が一度目のユーザ回答と食い違う場合は、ユーザ回答が食い違った質問の時点から問診をやり直すことができ、得られる問診結果の確実性を高めることができる。

本開示にかかる決定木生成装置は、ユーザが知覚した現象に関する質問への回答を通じて、ユーザが知覚した現象を生じさせる可能性の高い原因を推定するアプリケーションに応用が有効である。例えば、ユーザ回答を通じての機器の故障診断や、占い、性格判断などのアプリケーションに応用が可能である。

１１ 決定木作成部
１２ 情報ゲイン算出部
１３ ユーザ回答信頼度算出部
１４ 分類対象データ記憶部
１５ ユーザ回答事例データ記憶部
１６ 質問順序決定結果記憶部
５０１ 音声入力部
５０２ 音声認識部
５０３ 言語理解部
５０４、５０４Ａ ユーザ回答結果処理部
５０５ 質問順序記憶部
５０６ 現在決定木ノード記憶部
５０７、５０７Ａ 問診制御部
５０８ 言語生成部
５０９ 音声合成部
５１０ 音声出力部
５１１ 表示部
５１２ 決定木ノード履歴記憶部

Claims (10)

1. 質問の順序を決定するために使用される決定木を生成する決定木生成装置であって、
   互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出する情報ゲイン算出部と、
   前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる決定木作成部とを備える、
   決定木生成装置。
2. 前記属性を問う質問に対するユーザの回答の正答及び誤答の実例を含むユーザ回答実例データから前記信頼度を前記属性毎に算出する信頼度算出部をさらに備え、
   前記情報ゲイン算出部は、前記信頼度算出部により算出された信頼度と、前記エントロピーの減少量とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出する、
   請求項１記載の決定木生成装置。
3. 前記信頼度は、前記属性を問う質問に対するユーザの回答の正答率を含み、
   前記情報ゲイン算出部は、前記エントロピーの減少量に前記正答率を乗算することにより前記情報ゲインを算出する、
   請求項１又は２記載の決定木生成装置。
4. 前記ユーザ回答実例データは、ユーザが質問に回答するまでの回答時間をさらに含み、
   前記正答率は、前記回答時間と前記正答率との相関関係から求めたユーザの平均回答時間に対する正答率を含み、
   前記情報ゲイン算出部は、前記エントロピーの減少量に前記平均回答時間に対する正答率を乗算することにより前記情報ゲインを算出する、
   請求項３記載の決定木生成装置。
5. 前記信頼度は、所定の属性を問う質問に対して回答となる所定の属性値が得られるときの条件付きエントロピーを含み、
   前記情報ゲイン算出部は、前記エントロピーの減少量から前記条件付きエントロピーを減算することにより前記情報ゲインを算出する、
   請求項１又は２記載の決定木生成装置。
6. 前記ユーザ回答実例データは、ユーザの属性を表すユーザ情報をさらに含み、
   前記信頼度算出部は、前記ユーザの属性毎に、前記ユーザ回答実例データから前記信頼度を前記属性毎に算出し、
   前記情報ゲイン算出部は、前記信頼度と、前記エントロピーの減少量とに基づいて、前記情報ゲインを前記ユーザの属性毎に算出する、
   請求項２〜５のいずれかに記載の決定木生成装置。
7. 質問に対するユーザの回答から分類結果を生成する質問システムであって、
   請求項１記載の決定木生成装置により生成された決定木を記憶する記憶部と、
   前記記憶部に記憶された決定木に応じた質問を出力する質問部と、
   前記質問部による質問に対するユーザの回答を取得する取得部と、
   前記取得部により取得された回答に応じた分類結果を生成する生成部とを備える、
   質問システム。
8. 前記質問部による質問の順序を表す質問順序情報と、前記質問部による質問に対応する属性を識別するための属性識別情報と、前記質問部による質問の回答となる属性値と、前記質問部による質問に対応する属性の信頼度とを記憶する履歴記憶部をさらに備え、
   前記生成部は、前記分類結果を生成した後、前記履歴記憶部を参照して所定値より正確性が低い信頼度を有する属性を問う質問を再度行う、
   請求項７記載の質問システム。
9. 質問の順序を決定するために使用される決定木を生成する決定木生成装置における決定木生成方法であって、
   互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出し、
   前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる、
   決定木生成方法。
10. 質問の順序を決定するために使用される決定木を生成する決定木生成装置として、コンピュータを機能させるための決定木生成プログラムであって、
    前記コンピュータに、
    互いに異なる複数の属性の各々に対して属性値が割り当てられた複数の分類対象データを含む分類対象データ集合を決定木の形式で階層的に部分集合に分割するときに、分割前のデータ集合に含まれる前記分類対象データの前記属性毎に、分割によるデータ集合のエントロピーの減少量を算出し、前記エントロピーの減少量と、前記属性を問う質問に対するユーザの回答の正確性又は不正確性を表す指標である信頼度とに基づいて、前記属性毎に当該属性の属性値により前記分割前のデータ集合を分割したときの情報ゲインを算出し、
    前記属性毎に算出した複数の情報ゲインのうち最も大きい情報ゲインを有する属性の属性値により前記分割前のデータ集合を分割する処理を再帰的に繰り返すことにより、前記最も大きい情報ゲインを有する属性を決定木のノードとして順次決定するとともに、当該ノードのエッジに前記最も大きい情報ゲインを有する属性の属性値を順次割り当てる、
    処理を実行させる決定木生成プログラム。

Images