(57)【特許請求の範囲】
【請求項１】
予め登録されている検索条件と、検索対象である検索データからなるデータベースとによって構成され、上記検索条件についてＹｅｓ／Ｎｏで答えることによって上記検索データを絞り込むＹｅｓ／Ｎｏ型質問木を作成するＹｅｓ／Ｎｏ型質問木作成装置において、
上記検索対象である検索データを検索データ集合とするルートとなるノードを設定し、ノード処理手段を呼び出すルートノード処理手段と；
検索データ集合が与えられると、所定の関数に検索データ集合を入力して得られる評価値を当該ノードの最大評価値に設定するとともに、現在の階層数がＹｅｓ／Ｎｏ選択上限数以上であれば、上記最大評価値を呼び出し元に返し、現在の階層数がＹｅｓ／Ｎｏ選択上限数未満であれば、当該ノードに対応した検索データ集合を対象にそれぞれの検索条件について、検索条件を満たす検索データ集合と、検索条件を満たさない検索データ集合とに分割し、分割された２つの検索データ集合のそれぞれのノードを生成し、生成されたノードに対して再帰的に自身であるノード処理手段を呼び出して生成されたノードの評価値を取得し、検索条件を満たす検索データ集合のノードの評価値と、検索条件を満たさない検索データ集合のノードの評価値との和を求め、それぞれの検索条件の中で当該和が最大となる最大評価値を求め、その最大評価値を呼び出し元に返すノード処理手段と；
を有することを特徴とするＹｅｓ／Ｎｏ型質問木作成装置。
【請求項２】
請求項１において、
上記ノード処理手段は、
各検索条件が最大評価値を導く可能性を示す最適検索条件期待値を算出する最適検索条件期待値算出手段を有し、
上記最適検索条件期待値が上位である検索条件を対象に、最大評価値およびその検索条件を求めることを特徴とするＹｅｓ／Ｎｏ型質問木作成装置。
【請求項３】
請求項１において、
各検索条件が各検索データに適合する度合いを示す適合度を求める適合度算出手段を有し、
上記所定の関数は、与えられた検索データ集合の中で適合度が大きい所定件数の総和であることを特徴とするＹｅｓ／Ｎｏ型質問木作成装置。
【請求項４】
請求項２において、
各検索条件が各検索データに適合する度合いを示す適合度を求める適合度算出手段を有し、
上記最適検索条件期待値は、与えられた検索データ集合の中で検索条件に対する適合度が大きい所定件数の総和であることを特徴とするＹｅｓ／Ｎｏ型質問木作成装置。
【請求項５】
請求項１において、
上記所定の関数は、与えられた検索データ集合の個数が所定件数以下である場合には当該個数を評価値とし、個数が上記所定件数よりも多い場合は評価値を０とすることを特徴とするＹｅｓ／Ｎｏ型質問木作成装置。
【請求項６】
請求項１〜請求項５のいずれか１項に記載のＹｅｓ／Ｎｏ型質問木作成装置の各手段として、コンピュータを機能させるＹｅｓ／Ｎｏ型質問木作成プログラム。
【請求項７】
請求項６に記載のＹｅｓ／Ｎｏ型質問木作成プログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、予め登録されている検索条件を利用し、大量のデータベースからデータを検索する場合、入出力手段の乏しいインタフェースでも、効率よくデータを選択できるようにＹｅｓ／Ｎｏ型質問木を作成するＹｅｓ／Ｎｏ型質問木作成装置、Ｙｅｓ／Ｎｏ型質問木作成方法、プログラムおよび記録媒体に関する。
【０００２】
【従来の技術】
現在では、パソコンだけでなく、携帯電話、固定電話、テレビ、ラジオ等、あらゆる端末からインターネットに接続可能である。
【０００３】
パソコンは、解像度の高いディスプレイ（出力手段）を有し、また、単位時間当りに比較的大量の情報を入力可能なキーボードとマウスと（入力手段）を有する。そして、オフィスや家庭のデスクに向い、椅子に座り、上記入出力手段を操作するという安定した操作姿勢が、パソコン操作の前提である。
【０００４】
一方で、非パソコンによるインタフェースは、簡単に使える家庭電化製品の延長である反面、入出力手段が乏しい。たとえば、携帯電話は、端末が小型で簡易であるので、ディスプレイが小型であり解像度が低い。その入力手段は、テンキーと矢印キーとであり、パソコンに比べて、単位時間当りに入力可能な情報量が比較的少ない。また、操作姿勢は、立ったまま片手で携帯電話を持ち、親指で操作する等、かなり不安定である。上記入力手段が乏しい点は、テレビ、ラジオ、固定電話においても、共通する点である。
【０００５】
また、近年、電話の音声通話によるインターネットアクセスサービスも、台頭している。音声出力の一覧性はなく、時間軸に沿って情報が流れる。さらに、音声入力は、自由度が高いが、発話語彙を大量にすると、認識率が低下する。さらに、携帯電話等、周囲の騒音が大きい場合や、通話品質が低い場合には、発話語彙数を減らして認識率を保証することが想定される。また、音声インタフェースは、ハンズフリーであるので、自動車の車内での利用が想定される。この場合、操作姿勢としては、運転中であり、さらに不安定である。
【０００６】
つまり、非パソコン機器によるインタフェースでは、入出力手段の制約が大きい。このために、非パソコン機器によって、大量なデータベースから所望のデータを検索するために、想起したフリーキーワードのような情報量の多い検索条件を入力することが困難である場合が多いと考えられる。
【０００７】
そこで、予め登録されている複数の検索条件によって、装置がデータベースを検索し、その検索結果を上手に選択するような検索インタフェースが必要になる。
【０００８】
この点に関して、宮本らは、事前絞込み型メニューによる絞込み方法を、特願２０００−０４００９４（発明の名称：データ検索支援方法及び装置及びデータ検索支援プログラムを格納した記憶煤体）において提案している。
【０００９】
この従来の装置では、予め検索サービス提供者が用意したお勧め絞込み条件群に基づいて、お勧め絞込み条件同士の論理積による絞込み検索を、検索対象集合について、実行し、許容可能な程度の絞込み回数によって、携帯電話のような画面の小さい携帯端末でも、一覧可能な程度に絞り込むことができる検索条件を抽出し、メニューとして表示する。
【００１０】
許容可能な絞込み回数を、たとえば２回という極めて少ない回数に設定すれば、この絞込みメニューを用いて、検索サービス提供者のお勧め絞込み条件を、２回選択するだけで、携帯電話の狭い画面でも、検索結果を一覧できることを保証する。
【００１１】
【発明が解決しようとする課題】
しかし、上記事前絞込み型メニューでは、複数のメニュー項目から任意のメニュー項目を選択するメニュー（以下、複数項目型メニュー）を利用しているので、インタフェースは、一般的なメニューと同様である。
【００１２】
したがって、音声のように極端に一覧性が低い出力手段である場合、複数のメニュー項目を音声で聞きながら記憶し、選択する操作負荷は、従来のメニューと同等である。
【００１３】
そこで、情報を選択するためにユーザが逐次投入する情報量を、最小の１ｂｉｔに制約し、最もシンブルな選択手段を提供する。すなわち、ユーザに対して、Ｙｅｓ／Ｎｏの質問形式の質問木（以下、これを、「Ｙｅｓ／Ｎｏ型質問木」という）を提示し、Ｙｅｓ／Ｎｏで逐次回答することによって、１ｂｉｔずつ検索対象を絞り込むインタフェースを前提とする。これによって、非パソコンの簡易な入力手段でも、簡単に入力可能なインタフェースを提供することができる。
【００１４】
ここで、上記前提となる質問木による検索インタフェースは、図１に示す最適質問木９のように、２分木の構造を持つ。
【００１５】
各ノードは、各検索条件に対応し、提示された検索条件を採用する場合は、ノードの左側の子ノードに進み、上記検索式にヒットするデータが提示対象である。逆に、提示された検索条件を採用しない場合は、ノードの右側の子ノードに進み、上記検索式にヒットしないデータが提示対象である。
【００１６】
効率的に検索対象を絞り込むためには、各ノードに、どのような検索条件を割り当てるかが、重要なポイントになる。
【００１７】
しかし、予め登録されている検索条件に基づいて作成することができる質問木として、多くのパターンがあり、全てのパターンを闇雲に比較評価しようとすると、計算量が多くなるという問題がある。
【００１８】
本発明は、予め登録されている検索条件を利用し、大量のデータベースからデータを選択する場合、入出力手段の乏しいインタフェースでも、効率よくデータを選択できるようにＹｅｓ／Ｎｏ型質問木を作成することができるＹｅｓ／Ｎｏ型質問木作成装置、Ｙｅｓ／Ｎｏ型質問木作成方法、プログラムおよび記録媒体を提供することを目的とするものである。
【００１９】
また、検索対象のデータ数が増加した場合、または、考慮すべき検索条件の数が増加した場合に、処理時間が必然的に増加するという問題がある。
【００２０】
本発明は、全ての検索条件を再帰的に評価せずに、最適な質問木を得ることができる可能性が高い検索条件を選択的に評価し、処理時間を削減しつつ、作成質問木の精度を確保することができるＹｅｓ／Ｎｏ型質問木作成装置、Ｙｅｓ／Ｎｏ型質問木作成方法、プログラムおよび記録媒体を提供することを目的とするものである。
【００２１】
さらに、本発明は、各データに対する検索条件の適合度が、相互に比較可能な順序尺度である場合に、適合度が高いデータに優先的にアクセスする質問木を、自動的に作成することができ、また、処理速度が高速であるＹｅｓ／Ｎｏ型質問木作成装置、Ｙｅｓ／Ｎｏ型質問木作成方法、プログラムおよび記録媒体を提供することを目的とするものである。
【００２２】
そして、本発明は、ユーザがＹｅｓ／Ｎｏ型質問木を回答した後に、検索データ群を閲覧する上で、閲覧する端末の一覧性が低い場合でも、Ｙｅｓ／Ｎｏ選択上限以内分だけ、Ｙｅｓ／Ｎｏを回答すれば、閲覧する検索データ群を一覧できる件数に絞り込むことができ、したがって、質問を何度繰り返して絞り込んでも大量の検索緒果が残るという可能性を減少することができるＹｅｓ／Ｎｏ型質問木作成装置、Ｙｅｓ／Ｎｏ型質問木作成方法、プログラムおよび記録媒体を提供することを目的とするものである。
【００２３】
【課題を解決するための手段】
本発明は、予め登録されている検索条件と、検索対象である検索データからなるデータベースとによって構成され、上記検索条件についてＹｅｓ／Ｎｏで答えることによって上記検索データを絞り込むＹｅｓ／Ｎｏ型質問木を作成するＹｅｓ／Ｎｏ型質問木作成装置において、上記検索対象である検索データを検索データ集合とするルートとなるノードを設定し、ノード処理手段を呼び出すルートノード処理手段と、検索データ集合が与えられると、所定の関数に検索データ集合を入力して得られる評価値を当該ノードの最大評価値に設定するとともに、現在の階層数がＹｅｓ／Ｎｏ選択上限数以上であれば、上記最大評価値を呼び出し元に返し、現在の階層数がＹｅｓ／Ｎｏ選択上限数未満であれば、当該ノードに対応した検索データ集合を対象にそれぞれの検索条件について、検索条件を満たす検索データ集合と、検索条件を満たさない検索データ集合とに分割し、分割された２つの検索データ集合のそれぞれのノードを生成し、生成されたノードに対して再帰的に自身であるノード処理手段を呼び出して生成されたノードの評価値を取得し、検索条件を満たす検索データ集合のノードの評価値と、検索条件を満たさない検索データ集合のノードの評価値との和を求め、それぞれの検索条件の中で当該和が最大となる最大評価値を求め、その最大評価値を呼び出し元に返すノード処理手段とを有することを特徴とするＹｅｓ／Ｎｏ型質問木作成装置である。
【００２４】
【発明の実施の形態および実施例】
［第１の実施例］
図１は、本発明の第１の実施例であるＹｅｓ／Ｎｏ型質問木作成装置１００を示す図である。
【００２５】
Ｙｅｓ／Ｎｏ型質問木作成装置１００は、考えられる質問木構成パターンの全てを作成するのではなく、Ｙｅｓ／Ｎｏ型質問木のパターンを作成する前に、分割対象となる検索データ群に検索結果が存在しない検索条件を除外し、これによって、最適なＹｅｓ／Ｎｏ型質問木を、高速に作成する装置である。
【００２６】
Ｙｅｓ／Ｎｏ型質問木作成装置１００は、登録検索条件リスト１と、検索対象データベース２と、分割対象リスト３と、非分割対象リスト４と、分割対象リスト作成部５と、最適パターン表６と、最適パターン表作成部７と、最適質問木作成部８とを有し、後述する「一覧可能上限数」と、後述する「Ｙｅｓ／Ｎｏ選択上限数」とを入力として渡すと、最適なＹｅｓ／Ｎｏ型質問木９を出力する装置である。
【００２７】
登録検索条件リスト１は、予め登録されている検索条件のリストであり、この予め登録されている検索条件を、ユーザ毎に保持しているが、検索サービス提供者が勧める検索条件のリストであってもよい。
【００２８】
検索対象データベース２は、検索対象である検索データを格納しているデータベースであり、リレーショナルデータベースであってもよく、フルテキスト検索するテキストファイル群であってもよく、また、所定の検索条件に対して検索結果を返すデータベースであれば、他のデータベースであってもよい。
【００２９】
図２は、分割対象リスト３を示す図であり、検索データと、検索条件群（適合度）との関係を表す図である。
【００３０】
分割対象リスト３は、検索対象データベース２に基づいて、分割対象リスト作成部５が作成するリストであり、図２に示すように、検索データと、検索条件群と、検索条件とデータとの適合度とによって構成されている。
【００３１】
つまり、分割対象リスト３は、検索対象データベース２から、少なくとも１つの検索条件によって検索された検索結果に含まれている検索データである。検索対象データベース２のうちで、検索条件に対する検索結果が少ない場合、圧縮効率が高い。
【００３２】
非分割対象リスト４は、予め登録されている検索条件のうちで、いずれの検索条件の検索結果にも含まれない検索データを、検索対象データベース１の中から、抽出したリストであり、分割対象リスト作成部５が、非分割対象リスト４を作成する。この非分割対象リスト４は、検索条件毎に存在するリストではなく、１つのデータベースについて、１つだけ存在するリストである。
【００３３】
図３は、検索条件が各データに適合する度合いである適合度の例を示す図である。
【００３４】
分割対象リスト作成部５は、図３に示すように、検索条件が各データに適合する度合いを示す適合度を付与する。この適合度は、各検索条件の検索結果に含まれるか否かの２値データであることを基本とする。また、所定の検索データが、所定の検索条件の検索結果に含まれる場合、上記所定の検索データが上記所定の検索条件に適合する度合いを、ＴＦ／ＩＤＦ値等を用いた順序尺度として表現する。この順序尺度は、０〜１００の間の整数値である。検索データが検索条件に適合する度合いを示す尺度であれば、ＴＦ／ＩＤＦ値等を用いた順序尺度の代わりに、他の尺度を使用するようにしてもよい。
【００３５】
また、本実施例では、適合度が「０」よりも大きい検索データを、適合する検索データであると考えるので、適合度が付与されている検索データ対検索条件の表から、「０」よりも大きい適合度を持つデータと、検索条件との組合せだけを抽出し、データと、該当検索条件群（適合度）とによって構成される分割対象リスト３を、図２に示すように、作成する。
【００３６】
図４は、非分割対象リスト４の例を示す図である。
【００３７】
予め登録されている検索条件のうちで、いずれの検索条件の検索結果にも含まれないデータを、リストとして抽出したものを、図４に示すように、非分割対象リスト４として作成する。
【００３８】
図５は、最適パターン表６の内容例を示す図である。
【００３９】
なお、図５において、ノードＩＤが「２」である行が複数、記載されている。これは、親ノードが「ＡＢＣ」、「テロ」、……のそれぞれである場合に、ノードＩＤ「２」として、項目ラベルに記載されている内容を質問する場合があり、したがって、図５において、ノードＩＤが「２」である行が複数、記載されている。よって、図５において、ノードＩＤが「３」である行も、複数、記載されている。
【００４０】
最適パターン表６は、分割対象リスト３に基づいて、最適パターン表作成部７が作成する表であり、図５に示すように、Ｙｅｓ／Ｎｏ型質問木のノードＩＤと、親ノード検索条件リストと、分割対象リストの長さと、最大評価値と、枝／葉フラグと、項目ラベルとを有する表形式のデータが記載されている表である。
【００４１】
「親ノード検索条件リスト」は、当該ノードの親ノードにおける検索条件を表現するリストである。根（ノードＩＤ＝１）から親ノードまでのパスに存在する検索条件を、２重に評価しないために、この親ノード検索条件リストが利用されている。
【００４２】
「分割対象リストの長さ」は、当該ノードが分割しようとしている分割対象リストに含まれるデータ数である。つまり、分割対象リストの長さは、途中のＹｅｓ／Ｎｏの分岐のうちで、提示対象として残っている「データ、検索条件、適合度」の対の集合であり、その要素数である。
【００４３】
「最大評価値」は、当該ノードにおける最大評価値を示す関数である。この評価値は、どのような質問木が最適と考えるかによって変わり、つまり、質問木の作り方によって変わる。
【００４４】
「枝／葉フラグ」は、Ｙｅｓ／Ｎｏ質問木のうちで当該ノードが、質問を示すノード（枝）であれば、そのフラグは「１」であり、質問に回答した後に出現する検索データ群を示すノード（葉）であれば、そのフラグは「０」である。つまり、枝／葉フラグが１であれば、枝であることを示し、枝／葉フラグが０であれば、葉である。すなわち、質問木は、質問を示すノード（枝）と、検索データ群を示すノード（葉）とによって構成され、「枝／葉フラグ」は、枝であるかまたは、葉であるかを区別するフラグである。
【００４５】
「項目ラベル」は、枝のノードにおいて、質問を示す検索条件であり、葉のノードにおいて、Ｙｅｓ／Ｎｏの質問木に回答した後に出力される検索データ群である。
【００４６】
次に、Ｙｅｓ型質問木のノードＩＤを作成する規則について説明する。
【００４７】
図６は、質問木にノードＩＤが記入されている質問木の例を示す図である。
【００４８】
Ｙｅｓ型質問木のノードＩＤを作成する場合、図６に示すように、質問木の根のＩＤを「１」とし、ノードｉの子のノードのうちで左に記載される子のノードＩＤを、「２ｉ」とし、右に記載される子のノードＩＤを、「２ｉ＋１」とする。
【００４９】
図１に戻り、最適パターン表作成部７は、分割対象リスト３に基づいて、最適パターン表６を作成する。
【００５０】
最適質問木作成部８は、非分割対数リスト４と最適パターン表６とに基づいて、最適質問木９を作成する。最適パターン表６には、図５に示すように、各ノードＩＤにおいて、親ノード検索条件リストに依存する最適な検索条件（最大評価値を有する検索条件）が、項目ラベルに記録されている。
【００５１】
そして、質問木の根の親ノード検索条件リストと、項目ラベルとを組合せたものを、次の質問木の階層の親ノード検索条件リストにし、この親ノード検索条件リストを持つ最適な質問項目を、次の質問項目とし、このような処理を再帰的に実行する。
【００５２】
たとえば、質問木の根の親ノード検索条件リストが、「ｒｏｏｔ テロ」であり、その項目ラベルが、「韓国」である場合、「ｒｏｏｔ テロ」と「韓国」とを組合せたものは、「ｒｏｏｔ テロ、韓国」であり、この「ｒｏｏｔ テロ、韓国」を、次の質問木の階層の親ノード検索条件リストにし、この親ノード検索条件リストを持つ最適な質問項目（最大評価値を持つ検索条件）、つまり「韓国」を、次の質問項目とし、このような処理を再帰的に実行する。
【００５３】
このようにして、最適質問木９を抽出する。また、質問木に対して全てＮｏと回答した終端ノードを示す集合を、非分割対象リスト４に追加する。
【００５４】
図７は、最適質問木９が持つ表形式のデータを示す図である。
【００５５】
最適質問木９は、図７に示すように、Ｙｅｓ／Ｎｏ型質問木におけるノードＩＤと、分割対象リストの長さと、最大評価値と、枝／葉フラグと、項目ラベルとを持つ表形式のデータを持つ。
【００５６】
図７に示す最適質問木９が持つ表形式のデータは、図５に示す最適パターン表６の項目から、「親ノード検索条件リスト」を除去したものである。
【００５７】
次に、上記実施例において、Ｙｅｓ／Ｎｏ型質問木を作成する動作について説明する。
【００５８】
図８は、上記実施例において、Ｙｅｓ／Ｎｏ型質問木を作成する基本動作を示すフローチャートである。
【００５９】
まず、一覧上限可能数と、質問木選択上限数とを入力することによって、初期設定する（Ｓ１）。
【００６０】
「一覧上限可能数」は、情報を閲覧するインタフェースにおいて一覧することができる程度の件数である。たとえば、携帯端末や音声インタフェースの場合、一覧上限可能数は、３〜７件程度である。３〜７件以外の任意の件数を、一覧上限可能数として設定することができる。
【００６１】
「質問木選択上限数」は、ユーザがＹｅｓ／Ｎｏを選択する回数のうちで、ユーザが許容できる回数である。たとえば、２、３回である。２、３回以外の任意の回数を設定することができる。
【００６２】
そして、分割対象リスト３と、非分割対象リスト４とを作成する（Ｓ２）。つまり、分割対象リスト作成部５が、各データに対して、図３に示す任意の検索条件が適合する度合いを示す適合度を付与する。この適合度は、基本的には、各検索条件の検索結果に含まれるか否かを示す２値データである。
【００６３】
また、検索データが各検索条件の検索結果に含まれる場合（条件に適合する場合）に、上記検索データが各検索条件に適合する度合いを、ＴＦ／ＩＤＦ値等を用いた順序尺度として表現する。
【００６４】
この順序尺度は、０〜１００の間の整数値であるが、データが各検索条件に適合する尺度であれば、他の尺度を使用するようにしてもよい。また、本実施例では、適合度が「０」よりも大きい場合に、適合するデータとするので、図３に示す適合度を付与したデータ対検索条件の表から、「０」よりも大きい適合度を持つデータと、検索条件との組合せだけを抽出し、図２に示すように、データ、該当検索条件群（適合）との対によって構成される分割対象リスト３を作成する。
【００６５】
また、予め登録されている検索条件のうちで、いずれの検索条件の検索結果にも含まれないデータをリストとして抽出した非分割対象リスト４を、図４に示すように、作成する。
【００６６】
そして、図５に示す最適パターン表６を作成する（Ｓ３）。つまり、最適パターン表作成部７が、分割対象リスト３に基づいて、図５に示す最適パターン表６を作成する。最適パターン表６を作成する動作の詳細については、後述する。
【００６７】
その後、最適質問木９を抽出する（Ｓ４）。つまり、最適質問木作成部８が、非分割対象リスト４と最適パターン表６とに基づいて、最適質問木９を作成する。最適パターン表６には、各ノードＩＤにおいて、親ノード検索条件リストに依存する最適な検索条件が、項目ラベルに記録されている。
【００６８】
そして、質問木の根の親ノード検索条件リストと、項目ラベルとを組合せたものを、次の質問木の階層の親ノード検索条件リストにする。この親ノード検索条件リストを持つ最適な質問項目を、次の質問項目とする処理を、再帰的に実行することによって、最適質問木９を抽出する。また、質問木に対して、全てＮｏと回答した終端ノードを示す集合に、非分割対象リスト４を追加する。
【００６９】
図９は、最適パターン表６を作成する動作（Ｓ３）を詳細に示すフローチャートである。
【００７０】
最適パターン表９を作成する（Ｓ３）場合、再帰処理を行う。
【００７１】
まず、最適パターン表作成部７が、ノードＩＤ、分割対象リスト、親ノード検索条件リストを取得する（Ｓ３−１）。最適パターン表６を作成する場合、再帰処理を行うので、初期状態では、ノードＩＤとして、質問木の根のノードを示す「１」を与え、分割対象リストとして、文書データベースに含まれている検索データの全体を与え、親ノード検索条件リストに、根を示す「ｒｏｏｔ」という文字列を与える。
【００７２】
Ｓ３−２では、最適パターン表作成部７が、最適パターン表６へ追加するレコードのバッファとして、現在の分割対象リストに関する値を、分割対象リスト３の長さ、最大評価値、枝／葉フラグ、項目ラベルの項目に、それぞれ代入する。
【００７３】
「分割対象リストの長さ」は、分割対象リスト３中のデータ数である。分割対象リストを入力した場合における何らかの関数に基づいて得られる評価値を、最大評価値として代入する。この評価値は、質問木の精度を表現する値であれば、どのような値でもよく、枝／葉フラグとして、葉を示す０を代入する。また、項目ラベルとして、分割対象リストに含まれている検索データ群を、現ノードにおける適合度の高い順にリスト形式で代入する。
【００７４】
Ｓ３−３では、現在の階層数が、既に入力されているＹｅｓ／Ｎｏ選択上限数以上であれば、ステップＳ３−４に進み、現在の階層数が、Ｙｅｓ／Ｎｏ選択上限数未満であれば、ステップＳ３−５へ進む。
【００７５】
Ｓ３−４では、ステップＳ３−２またはＳ３−１４において、バッファとして保持しているデータを、新規レコードとして、最適パターン表６へ追加する。最大評価値を、本フローチャートの呼び出し元へ返し、処理を終了する。
【００７６】
Ｓ３−５では、分割対象リスト３の長さが、既に入力されている一覧可能上限数以下であれば、ステップＳ３−４に進み、一覧可能上限数よりも長ければ、ステップＳ３−６へ進む。
【００７７】
Ｓ３−６では、分割対象リスト３から、検索条件を抽出し、親ノード検索条件リストに含まれていない検索条件を、評価すべき検索条件として抽出する。
【００７８】
図１０は、データと検索条件群（適合度）との関係を示す表の例と、質問木の例とを示す図である。
【００７９】
たとえば、図１０（２）に示すように、ノードＩＤが１０であるノードにおいて、評価対象（検索データ）の検索条件を取得する場合、分割対象リスト３から、「テロ」、「横須賀」、「中国」の検索条件が抽出されたとする。しかし、この場合、検索条件「横須賀」は、図１０（２）に示すように親ノード検索条件リストに含まれているので、「横須賀？」という質問を再度実行することを阻止するために、「横須賀」の検索条件を除外し、「テロ」、「中国」が評価すべき検索条件として取得される。
【００８０】
Ｓ３−７では、評価すべき検索条件の数が０個であれば、ステップＳ３４に進み、０個以外であれば、ステップＳ３−８へ進む。
【００８１】
Ｓ３−８では、評価すべき検索条件を１つずつ評価する動作を繰り返す。全ての評価すべき検索条件を評価し終われば、ステップＳ３−４に進み、評価していない評価すべき検索条件があれば、評価する検索条件を抽出し、ステップＳ３−９へ進む。
【００８２】
Ｓ３−９では、ステップＳ３−８で評価対象として抽出された検索条件によって、分割対象リスト３を分割する。分割対象リスト３に含まれているデータのうちで、評価対象が検索条件に適合する適合度が０よりも大きいデータは、Ｙｅｓ側のリストとして抽出され、残りのデータが、Ｎｏ側のリストとして分割される。また、次階層の親ノード検索条件リストとして、現ノードの親ノード検索条件リストに、現在評価している検索条件を追加する。
【００８３】
Ｓ３−１０では、次階層のＹｅｓ側ノードの最大評価値を求めるために、現在のノードＩＤを２倍した値を、新たなノードＩＤとし、また、Ｙｅｓ側のリストを分割対象リスト３とし、さらに、ステップＳ３−９で取得した次階層の親ノード検索条件リストを、再帰的に呼び出す。
【００８４】
Ｓ３−１１では、次階層のＮｏ側ノードの最大評価値を求めるために、現在のノードＩＤを２倍した値に１を足した値を、新たなノードＩＤとし、また、Ｎｏ側のリストを、分割対象リスト３とし、さらに、ステップＳ３−９で取得した次階層の親ノード検索条件リストを、再帰的に呼び出す。
【００８５】
Ｓ３−１２では、ステップＳ３−１０で取得したＹｅｓ側の最大評価値と、Ｓ３−１１で取得したＮｏ側の最大評価値とを足したものを、現在評価している検索条件に対する「分割の評価値」に、代入する。
【００８６】
Ｓ３−１３では、ステップＳ３−１２で取得した分割の評価値が、上記フローチャートにおける最大評価値よりも大きければ、ステップＳ３−１４に進み、上記フローチャートにおける最大評価値以下であれば、ステップＳ３−８に進む。
【００８７】
Ｓ３−１４では、最適パターン表６へ追加するレコードのバッファとして、現在評価している検索条件による分割の情報を、最大評価値、枝／葉フラグ、項目ラベルに代入する。分割の評価値が最大評価値よりも大きい（Ｓ３−１３）ので、枝／葉フラグとして、枝を示す「１」を代入する。また、項目ラベルとして、現在評価している検索条件を代入する。分割対象リスト３の長さとして、ステップＳ３−２で代入した値をそのまま使う。
【００８８】
上記第１の実施例によれば、予め登録されている検索条件と、検索対象であるデータベースとが存在し、各データに対する各検索条件が適合する度合いを示す適合度を算出することができる場合に、検索条件をＹｅｓ/Ｎｏで選択する質問木によって、検索対象を絞り込み、表示するＹｅｓ/Ｎｏ型質問木を作成する場合、任意の検索条件で検索できる検索データ群を抽出し、この抽出された検索データ群を、任意の検索条件で検索可能な検索データ群と、検索できない検索データ群とに分割する処理の対象とする手段と、登録されている検索条件のうちで、分割の対象となる検索データ群に対して検索結果が存在する検索条件だけを、質問木を構成する検索条件として作成し、再帰的に分割する手段と、再帰的に検索データ群を分割する上で、当該検索データ群を入力した場合における評価値を、当該検索データ群の最大評価値とする手段と、再帰的に検索データ群を分割する検索条件によって検索可能な検索データ群の最大評価値と、検索できない検索データ群の最大評価値とを足し合わせたものを、当該検索条件における分割の最大評価値とする手段と、上記最大評価値が最も大きくなるように、検索条件で検索データを分割する質問木、または、分割の対象となる検索データ群を質問木として設定する質問木設定手段とを備えるので、考えられる質問木構成パターンを全て作成するのではなく、Ｙｅｓ/Ｎｏ型質問木のパターンを作成する前に、分割対象となる検索データ群に検索結果が存在しない検索条件を除外し、したがって、最適なＹｅｓ／Ｎｏ型質問木を、高速で作成することができる。
【００８９】
［第２の実施例］
図１１は、本発明の第２の実施例であるＹｅｓ／Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作を示すフローチャートである。
【００９０】
第２の実施例は、基本的には、第１の実施例と同じであり、図９に示すフローチャートにおいて、ステップＳ３−８の代わりに、ステップＳ３−１５−２とＳ３−８−２とを設け、検索対象のデータ数が増加した場合でも、考慮すべき検索条件の数が増加した場合でも、処理時間を削減しつつ、作成質問木の精度を確保することができる実施例である。
【００９１】
なお、ステップＳ３−１５−２、Ｓ３−８−２以外のステップは、第１の実施例におけるステップと同様であるので、その説明を省略する。
【００９２】
Ｓ３−１５−２では、ステップＳ３−６で取得した各評価すべき検索条件に対して、最適検索条件期待値を算出する。
【００９３】
「最適検索条件期待値」は、任意の検索条件を用いて分割対象リスト３を分割することによって、分割の評価値を最大化することができる尺度である
Ｓ３−８−２では、最適検索条件期待値が大きい順番に、評価すべき検索条件をソートし、最適検索条件期待値が上位である検索条件だけを、１つずつ評価することを繰り返す。
【００９４】
ここでは、上位から一定件数の検索条件を、最適検索条件期待値が上位であると判定してもよく、また、任意の期待値以上の検索条件を、最適検索条件期待値が上位であると判定するようにしてもよい。最適検索条件期待値が上位である検索条件の全てを評価したら、ステップＳ３−４に進み、全ての評価が終わっていなければ、評価する検索条件を抽出し、ステップＳ３−９へ進む。
【００９５】
上記第２の実施例によれば、登録されている検索条件のうちで、分割の対象となる検索データ群に対して検索結果が存在する検索条件だけを、質問木を構成する検索条件として作成し、再帰的に分割する場合に、各検索条件が最大評価値を導く可能性を示す最適検索条件期待値を算出する手段と、最適検索条件期待値が上位である検索条件のみを用いて、再帰的に検索データ群を分割する手段とを備えるので、検索対象のデータ数が増加した場合でも、考慮すべき検索条件の数が増加した場合でも、処理時間を削減しつつ、作成質問木の精度を確保することができる。
【００９６】
［第３の実施例］
図１２は、本発明の第３の実施例であるＹｅｓ／Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作を示すフローチャートである。
【００９７】
第３の実施例は、適合度が高いデータに、優先的にアクセスする質問木を作成することができる。
【００９８】
また、ステップＳ３−１６−３、Ｓ３−１７−３以外のステップは、第１の実施例と同様であるので、その説明を省略する。
【００９９】
Ｓ３−１６−３では、最適パターン表作成部７が、各データの現ノードにおける適合度を計算する。
【０１００】
「現ノードにおける適合度」は、現ノードの親ノード検索条件リストのうちで、Ｙｅｓと回答したキーワードに対する適合度の合計値である。
【０１０１】
図１３は、データと検索条件との関係の例を示す図と、質問木の例を示す図とである。
【０１０２】
たとえば、図１３に示すように、現ノードのノードＩＤが１０である場合に、現ノードにおけるデータｘの適合度を評価する。データｘが現在分類されているノードでは、「ＡＢＣ」と「横須賀」という検索条件が、Ｙｅｓであると回答されている。そして、これらの検索条件とデータｘとの適合度の合計値を、現ノードにおける適合度とする。
【０１０３】
なお、「ＩＳＤＮ」というキーワードに対しても回答しているが、Ｎｏと回答しているので、現ノードにおけるユーザの検索条件に「ＩＳＤＮ」が含まれず、除外している。これと同様に、分割対象リストに存在している文書全てに対して、この現ノードにおける適合度を評価する。
【０１０４】
Ｓ３−１７−３では、最適パターン表作成部７が、分割対象リスト３に含まれている各データのうちで、現ノードにおける適合度が上位であるデータを、一覧可能上限数以内分だけ抽出し、この値を合計したものを、分割対象リスト３の評価値として算出する。
【０１０５】
上記第３の実施例によれば、第１の実施例において、各検索条件が各データに適合する度合いを示す適合度が、相互に順序を比較可能な順序尺度である場合に、再帰的に検索データ群を分割する上で、質問木の親のノードでＹｅｓと回答し、選択した検索条件に対する任意データの適合度の合計値を、当該データの現ノードにおける適合度として算出する手段と、再帰的に検索データ群を分割する上で、分割対象となるデータのうち現ノードにおける連合度が上位であるデータを、一覧性の低い端末でも一覧できる程度の件数（所定件数）分だけ抽出し、現ノードにおける適合度を合計したものを分割の対象となる検索データ群の評価値とする手段とを備えるので、適合度が高いデータに優先的にアクセスする質問木を作成することができる。
【０１０６】
［第４の実施例］
図１４は、本発明の第４の実施例であるＹｅｓ/Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作（Ｓ３）を示すフローチャートである。
【０１０７】
第４の実施例は、検索対象のデータ数が増加した場合でも、考慮すべき検索条件の数が増加した場合でも、処理時間を削減しつつ、適合度が高いデータに優先的にアクセスする質問木の精度を確保することができる実施例である。
【０１０８】
また、図１４に示すフローチャートにおいて、ステップＳ３−１５−４、Ｓ３−８−４以外は、第３の実施例と同様であるので、その説明を省略する。
【０１０９】
Ｓ３−１５−４では、ステップＳ３−６で取得した各評価対象キーワードに対して、最適検索条件期待値を算出する。
【０１１０】
「最適検索条件期待値」は、分割対象リスト３の各データに対する適合度を、各キーワード毎に合計した値である。
【０１１１】
図１５は、データと検索条件との関係の例を示す図である。
【０１１２】
たとえば、図１５に示すように、２つのデータからなる分割対象リスト３が存在する場合、各検索条件のデータ１に対する適合度と、データ２に対する適合度とを合計した値が、最適検索条件期待値である。
【０１１３】
Ｓ３−８−４では、評価すべき検索条件を、最適検索条件期待値が大きい順番にソートし、最適検索条件期待値が上位の検索条件だけを１つずつ評価する動作を繰り返す。
【０１１４】
ここでは、上位からの一定件数の検索条件を、最適検索条件期待値が上位であると判定する場合があり、また、任意の期待値以上の検索条件を最適検索条件期待値が上位であると判定する場合もある。最適検索条件期待値が上位である検索条件の全てを評価したら、ステップＳ３−４に進む。最適検索条件期待値が上位である検索条件のうちで、評価していない検索条件が残っていれば、評価する検索条件を抽出し、ステップＳ３−９へ進む。
【０１１５】
上記第４の実施例によれば、登録されている検索条件のうちで、分割の対象となる検索データ群に対して検索結果が存在する適合度を保持する検索条件だけを、質問木を構成する検索条件として作成し、再帰的に分割する場合に、分割対象となる検索データ群に対する適合度を各検索条件毎に合計した値を、当該検索条件の最適検索条件期待値する手段を備えるので、検索対象のデータ数が増加した場合でも、考慮すべき検索条件の数が増加した場合でも、処理時間を削減しつつ、適合度が高いデータに優先的にアクセスする質問木の精度を確保することができる。
【０１１６】
［第５の実施例］
図１６は、本発明の第５の実施例であるＹｅｓ／Ｎｏ型質問木作成装置の最適パターン表６を作成する動作を示すフローチャートである。
【０１１７】
第５の実施例は、ユーザがＹｅｓ/Ｎｏ型質問木を回答した後に、検索データ群を閲覧する上で、閲覧する端末の一覧性が低い場合（所定の場合）でも、Ｙｅｓ／Ｎｏ選択上限以内分だけ、Ｙｅｓ/Ｎｏを回答すれば、閲覧する検索データ群を一覧することができる件数にまで絞り込まれるので、何度質問を繰り返して絞り込んでも大量の検索結果が残るという可能性が減少する実施例である。
【０１１８】
なお、図１６に示すフローチャートにおいて、ステップＳ３−１８−５、Ｓ３−１９−５、Ｓ３−２０−５以外のステップは、第１の実施例におけるステップと同様であるので、その説明を省略する。
【０１１９】
Ｓ３−１８−５では、分割対象リスト３の長さが、一覧可能上限数以下であれば、ステップＳ３−１９−５へ進み、一覧可能上限数よりも長ければ、ステップＳ３−２０−５に進む。
【０１２０】
Ｓ３−１９−５では、分割対象リスト３の評価値に、分割対象リスト３の長さを代入し、ステップＳ３−２へ進む。
【０１２１】
Ｓ３−１９−５では、分割対象リスト３の評価値に、０を代入し、ステップＳ３−２に進む。
【０１２２】
上記第５の実施例によれば、第１の実施例において、ユーザがＹｅｓ/Ｎｏ型質問木を回答し、検索データ群を閲覧する上で、閲覧する端末の一覧性が低い場合に、再帰的に検索データ群を分割する上で、分割対象となるデータ数が一覧性の低い端末でも、一覧可能な件数（所定件数）以下である場合に、分割対象となるデータ数を、分割の対象となる検索データ群の評価値とし、分割対象となるデータ数が一覧可能な件数（所定件数）よりも多い場合は、０を分割の対象となる検索データ群の評価値とする手段を備えるので、ユーザがＹｅｓ/Ｎｏ型質問木を回答した後に、検索データ群を閲覧する上で、閲覧する端末の一覧性が低い端末である場合でも、Ｙｅｓ/Ｎｏ選択上限以内分だけＹｅｓ／Ｎｏを回答すれば、閲覧する検索データ群が一覧できる件数に絞り込まれ、何度質問を繰り返して絞り込んでも、大量の検索結果が残るという可能性が減少する。
【０１２３】
なお、上記実施例を、プログラムの発明として把握することができる。すなわち、上記実施例は、予め登録されている検索条件と、検索対象である検索データによって構成されているデータベースとが存在し、上記検索条件についてＹｅｓ／Ｎｏで答えることによって上記検索データを絞り込むＹｅｓ／Ｎｏ型質問木を作成する場合、所定の検索条件によって検索データ群を抽出し、上記抽出された検索データ群を、任意の検索条件で検索できる検索データ群と、上記任意の検索条件では検索できない検索データ群とに分割するデータ分割手順と、上記登録されている検索条件のうちで、上記検索データ群について検索結果が在在する検索条件だけを、上記質問木を構成する検索条件として作成し、上記検索データ群を再帰的に分割する再帰的分割手順と、上記再帰的に検索データ群を分割する場合における当該検索データ群の評価値を、当該検索データ群における最大評価値という関数に代入する関数代入手順と、所定の検索条件で検索できる検索データ群の最大評価値と、上記所定の検索条件で検索できない検索データ群の最大評価値とを足し合わせた値を、当該検索条件における分割の最大評価値として決定する最大評価値決定手順と、上記最大評価値が最も大きくなるように、検索条件で検索データを分割する質問木、または、分割の対象となる検索データ群を質問木として設定する質問木設定手順とをコンピュータに実行させるプログラムの例である。
【０１２４】
また、上記プログラムをコンピュータ読み取り可能な記録媒体に記録するようにしてもよい。この場合、上記録媒体として、ＦＤ、ＣＤ、ＤＶＤ、ＨＤ、半導体メモリ等が考えられる。
【０１２５】
【発明の効果】
本発明によれば、全ての検索条件を再帰的に評価せずに、最適な質問木を得られる可能性が高い検索条件を選択的に評価し、処理時間を削減しつつ、作成質問木の精度を確保することができるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の第１の実施例であるＹｅｓ／Ｎｏ型質問木作成装置１００を示す図である。
【図２】分割対象リスト３を示す図であり、検索データと、検索条件群（適合度）との関係を表す図である。
【図３】検索条件が各データに適合する度合いである適合度の例を示す図である。
【図４】非分割対象リスト４の例を示す図である。
【図５】最適パターン表６の内容例を示す図である。
【図６】質問木にノードＩＤが記入されている質問木の例を示す図である。
【図７】最適質問木９が持つ表形式のデータを示す図である。
【図８】上記実施例において、Ｙｅｓ／Ｎｏ型質問木を作成する基本動作を示すフローチャートである。
【図９】最適パターン表６を作成する動作（Ｓ３）を詳細に示すフローチャートである。
【図１０】データと検索条件群（適合度）との関係を示す表の例と、質問木の例とを示す図である。
【図１１】本発明の第２の実施例であるＹｅｓ／Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作を示すフローチャートである。
【図１２】本発明の第３の実施例であるＹｅｓ／Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作を示すフローチャートである。
【図１３】データと検索条件との関係の例を示す図と、質問木の例を示す図とである。
【図１４】本発明の第４の実施例であるＹｅｓ/Ｎｏ型質問木作成装置において、最適パターン表６を作成する動作（Ｓ３）を示すフローチャートである。
【図１５】データと検索条件との関係の例を示す図である。
【図１６】本発明の第５の実施例であるＹｅｓ／Ｎｏ型質問木作成装置の最適パターン表６を作成する動作を示すフローチャートである。
【符号の説明】
１００…Ｙｅｓ／Ｎｏ型質問木作成装置、
１…登録検索条件リスト、
２…検索対象データベース、
３…分割対象リスト、
４…非分割対象リスト、
５…分割対象リスト作成部、
６…最適パターン表、
７…最適パターン表作成部、
８…最適質問木作成部、
９…最適質問木。
【図１】
0004020362.tif 000002
【図２】
0004020362.tif 000003
【図３】
0004020362.tif 000004
【図４】
0004020362.tif 000005
【図５】
0004020362.tif 000006
【図６】
0004020362.tif 000007
【図７】
0004020362.tif 000008
【図８】
0004020362.tif 000009
【図９】
0004020362.tif 000010
【図１０】
0004020362.tif 000011
【図１１】
0004020362.tif 000012
【図１２】
0004020362.tif 000013
【図１３】
0004020362.tif 000014
【図１４】
0004020362.tif 000015
【図１５】
0004020362.tif 000016
【図１６】
0004020362.tif 000017