(57)【特許請求の範囲】
【請求項１】
適合性フィードバックによる類似データ検索方法において、
文書検索装置が、
検索条件として特徴量と前記特徴量の重みの組からなる第１の検索条件ベクトルを用いてデータベースを検索し、
前記検索により得られた第１の検索結果を記憶装置に格納し、
前記第１の検索結果に含まれる少なくとも一つのデータに対してユーザが入力した「所望する」あるいは「所望しない」の少なくとも一方の評価を受け取り、
前記第１の検索条件ベクトルの特徴量の重みを前記評価に基づき変更した第２の検索条件ベクトルを用いて前記データベースを再検索し、
前記再検索により得られた第２の検索結果を前記記憶装置に格納し、
前記検索結果に含まれる各データの順位に対する前記第２の検索結果に含まれる前記各データの順位の変動量若しくは類似度の変動量を算出し、
算出した前記変動量を合計することで検索を終了する判断指標となる終了判断指標情報を算出し、
算出した前記終了判断指標情報を出力することを特徴とする類似データ検索方法。
【請求項２】
請求項１に記載の類似データ検索方法において、
算出した前記終了判断指標情報に基づき検索の続行あるいは終了を促すための情報を、ユーザインタフェースを介して表示することを特徴とする類似検索方法。
【請求項３】
請求項１に記載の類似データ検索方法において、
算出した前記終了判断指標情報に基づき検索の続行を促すための情報の使用可否を制御することを特徴とする類似検索方法。
【請求項４】
適合性フィードバックによる類似データ検索装置において、
第１の検索条件ベクトルを用いてデータベースを検索する検索手段と、
前記検索により得られた第１の検索結果を格納する記憶手段と、
前記第１の検索結果に含まれる少なくとも一つのデータに対してユーザが入力した「所望する」あるいは「所望しない」の少なくとも一方の評価を受け取る評価受け取り手段と、
前記第１の検索条件ベクトルの特徴量の重みを前記評価に基づき変更した第２の検索条件ベクトルを用いて前記データベースを再検索する再検索手段と、
前記再検索により得られた第２の検索結果を記憶する再検索後情報記憶手段と、
前記検索結果に含まれる各データの順位に対する前記第２の検索結果に含まれる前記各データの順位の変動量若しくは類似度の変動量を算出し、該算出した前記変動量を合計することで検索を終了する判断指標となる終了判断指標情報を算出する終了判断指標算出手段と、
算出した前記終了判断指標情報を出力する出力手段と、
を有することを特徴とする類似データ検索装置。
【請求項５】
請求項４に記載の類似データ検索装置において、
前記出力手段は、算出した前記終了判断指標情報に基づき検索の続行あるいは終了を促すための情報を表示することを特徴とする類似検索装置。
【請求項６】
請求項４に記載の類似データ検索装置において、
前記出力手段は、算出した前記終了判断指標情報に基づき検索の続行を促すための情報の使用可否を制御することを特徴とする類似検索装置。
【請求項７】
請求項１乃至３に記載の適合性フィードバックによる類似データ検索方法をコンピュータに実行させるためのプログラムを格納したコンピュータ読み取り可能な可搬型記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書や画像等の電子データを格納するデータベースに対し検索を行う方法および装置に関し、その検索結果に対してユーザが与えた評価に基づいて再検索を行う方法および装置に関する。
【０００２】
【従来の技術】
近年の電子データの増加に伴い、これらの電子データをより効率的に検索したいという要求が高まっている。この要求に応えるための検索技術として類似検索と呼ばれる技術がある。類似検索には、検索条件に指定された文書に類似する文書を検索する類似文書検索や検索条件に指定された画像に類似する画像を検索する類似画像検索等がある。以下、類似検索を説明するにあたり、類似文書検索を例に取って説明する。
【０００３】
類似文書検索では、検索条件および検索対象の文書（以下、検索対象の文書を検索対象文書と呼ぶ）を、それぞれ自立語の可能性がある文字列（以下、特徴文字列と呼ぶ）の出現情報を要素とするベクトルとして表現する。文書の検索時には、検索条件のベクトル（以下、検索条件ベクトルと呼ぶ）と検索対象文書のベクトル（以下、登録文書ベクトルと呼ぶ）の内積を検索条件に対する検索対象文書の類似度として算出する。この結果、算出された類似度の高い順に検索対象文書を参照することで、目的とする文書を効率よく検索できる。
【０００４】
しかし、類似文書検索では、ユーザの意図を適切に表現した文書を検索条件として指定することができない場合には、ユーザの意図と異なる検索結果が得られるという問題がある。
【０００５】
これを解決する技術として、類似文書検索の検索結果に対する評価を検索条件にフィードバックすることで精度の高い検索を実現する適合性フィードバックがある。
【０００６】
適合性フィードバックは、検索結果に対してユーザが「所望する」文書であるか「所望しない」文書であるかの評価を行い、前記評価に基づいて検索条件を修正し、前記修正された検索条件を用いた再検索を行うことで精度の高い検索を実現する技術であり、例えば特開２００１−１１７９３７号公報（以下、従来技術１と呼ぶ）に示されている。
【０００７】
以下、従来技術１を例に取り、適合性フィードバックを用いた類似文書検索の処理例を説明する。
【０００８】
まず、従来技術１における類似文書検索方法の概要を図２を用いて説明する。
【０００９】
本説明における類似文書検索では、検索条件と検索対象文書を特徴文字列の出現頻度を要素とする検索条件ベクトル、登録文書ベクトルとしてそれぞれ表現し、検索条件ベクトルに対する登録文書ベクトルの類似度を算出する。類似度の算出式として、従来技術１では数１を用いている。
【００１０】
【数１】
0004003468.tif 000002
この式で、Ｓ（Ｄ）は検索条件ベクトルに対する登録文書ベクトルＤの類似度であり、Ｔは特徴文字列の異なり数（異なる特徴文字列の総数）であり、Ｆｒｑ(ｉ，Ｄ)は文書Ｄにおける特徴文字列ｉの出現頻度であり、ｗ（ｉ）は検索条件に指定される文書における特徴文字列ｉの出現頻度から決定される検索条件ベクトルの特徴文字列ｉに対する重みである。
【００１１】
図２に示す検索条件ベクトル２０１は特徴文字列Ａに対して３，特徴文字列Ｂに対して２，特徴文字列Ｃに対して２，特徴文字列Ｄに対して３，特徴文字列Ｅに対して１の重みをそれぞれ持っている。ここでは、検索条件ベクトル２０１を（３，２，２，３，１）と表す。また、データベース２０２には、特徴文字列Ａを１個、特徴文字列Ｂを１個、特徴文字列Ｃを１個、特徴文字列Ｅを１個含む文書１の登録文書ベクトル（１，１，１，０，１）、および特徴文字列Ａを１個、特徴文字列Ｂを１個、特徴文字列Ｃを１個含む文書２の登録文書ベクトル（１，１，１，０，０）、特徴文字列Ｂを１個、特徴文字列Ｄを１個、特徴文字列Ｅを１個含む文書３の登録文書ベクトル（０，１，０，１，１）が登録されているとする。
【００１２】
類似文書検索の実行時には、類似度算出・並べ替え処理２０３において、数１により検索条件ベクトル２０１に対するデータベース２０２内の登録文書ベクトルの類似度が算出され、類似度の高い順に文書が並び替えられる。
【００１３】
この結果、文書１の類似度が８、文書２の類似度が７、そして文書３の類似度が６となり検索結果２０４が得られる。
【００１４】
次に、従来技術１における適合性フィードバックの処理の概要を、類似文書検索の概要の説明と同様に図２を用いて説明する。本図に示した例は、検索結果２０４に対して、ユーザが文書３を「所望する」と評価した場合の処理例である。従来技術１では、検索条件ベクトルの特徴文字列の重みを以下の数２に従って修正する。
【００１５】
【数２】
0004003468.tif 000003
ここで、ｗ’（ｉ）は特徴文字列ｉに対するあらたな重み、ｗ（ｉ）はもとの重みであり、ＦＰ（ｊ）は「所望する」と評価されたｊ番目の文書に含まれている特徴文字列ｉの出現頻度、ＦＮ（ｋ）は「所望しない」と評価されたｋ番目の文書に含まれる特徴文字列ｉの出現頻度である。また、Ｐは「所望する」と評価された文書の数であり、Ｎは「所望しない」と評価された文書の数である。なお、α、βはパラメータであり、本処理例ではいずれも１としている。
【００１６】
まず、ユーザによる評価２０５においてユーザが文書３を「所望する」と評価すると、評価結果読み込み処理２０６において、評価結果が読み込まれる。
【００１７】
次に、登録文書ベクトル取得処理２０７により、評価結果に従ってデータベース２０２から文書３の登録文書ベクトル２０８が取得される。
【００１８】
次に、検索条件ベクトル修正処理２０９により、数２を用いて文書３の登録文書ベクトル２０８の各特徴文字列の重みが検索条件ベクトル２０１の各要素に加算され、検索条件ベクトル２０１が（３，３，２，４，２）の重みを持つ検索条件ベクトル２０１ａに修正される。
【００１９】
次に、類似度算出・並べ替え処理２１０により、検索条件ベクトル２０１ａに対するデータベース２０２内の登録文書ベクトルの類似度が算出され、文書１の類似度が１０、文書２の類似度が８、文書３の類似度が９となる。この結果、類似度の高い順に検索対象文書を並べ替えることで、「所望する」と評価した文書３の順位が上昇した適合性フィードバック後の検索結果（以下、再検索結果と呼ぶ）２１１が得られる。
【００２０】
このように、従来技術１のように、適合性フィードバックを用いることで検索精度の向上を図ることができる。しかし、適合性フィードバックには、検索をどの時点で終了すればよいのかをユーザが判断することが困難であるという問題がある。
【００２１】
上記問題を説明するために、適合性フィードバックにおいて、ユーザが検索の終了を判断する手順を示す。
【００２２】
まず、ユーザは再検索結果と前回の検索結果を比較する。次に、前記比較結果から再検索の前後における検索結果の変動の度合を推量する。最後に、検索結果の変動の度合が大きければ、さらに再検索を行うことで、目的とする文書を検索できるので検索を終了すべきでないと判断し、逆に検索結果の変動の度合が小さければ、これ以上再検索を行っても目的とする文書は検索されないので検索を終了すべきであると判断する。
【００２３】
【発明が解決しようとする課題】
このように、適合性フィードバックにおいては，再検索前後における検索結果の変動度合の推量、検索結果の変動の度合からの検索の終了判断はユーザが行う必要がある。このため、推量や判断におけるユーザの負担が大きい。また、誤った推量、判断を行った場合には、無駄な検索を繰り返してしまうことになったり、さらに検索を続行することで目的とする文書が検索される場合にもかかわらず、検索を終了してしまうという問題がある。
【００２４】
上記問題を具体的に説明するために、例えば図３に示すように検索結果３０１における文書５を「所望する」と評価して適合性フィードバックを行うことによる検索結果３０１から再検索結果３０２への順位変動が大きい場合、および検索結果３０１から再検索結果３０３への順位変動が小さい場合を考える。
【００２５】
以下に、それぞれの場合にユーザが行う検索の終了判断の手順を具体的に説明する。
【００２６】
検索結果３０１から再検索結果３０２への順位変動が大きい例では、ユーザは検索結果３０１と再検索結果３０２を見比べて、文書１は３位下降、文書２は３位下降、文書３は不変、文書４は２位上昇、文書５は４位上昇と変動していることを確認し、「順位の変動が大きいので、再検索を行うことで目的とする文書を検索できる」と判断し、検索を続行する。
【００２７】
また、検索結果３０１から再検索結果３０３への順位変動が小さい場合、ユーザは検索結果３０１と再検索結果３０３を見比べて、文書１は不変、文書２は不変、文書３は不変、文書４は１位下降、文書５は１位上昇と変動していることを確認し、「順位の変動が小さいので、これ以上検索を続行しても目的とする文書は検索できない」と判断し、検索を終了する。
【００２８】
なお、上記説明ではユーザは表示されている５件の文書の順位変動を確認するものとしているが、文書が１００件表示される場合には１００件分の文書の順位変動を確認した上で変動の度合を推量し、その変動の度合から検索の終了を判断する必要がある。
【００２９】
本発明の目的は、適合性フィードバックにおける再検索の終了の判断指標となる値を定量的に算出し、ユーザに提示することで、ユーザが適合性フィードバックにおける検索の終了を誤って判断するのを防ぐことにある。
【００３０】
【課題を解決するための手段】
上記目的を達成するために、本発明の適合性フィードバック方法は、検索処理として以下のステップを有する。
（１）ユーザが評価した文書を識別する識別情報および評価内容を読み込む評価内容読み込みステップ。
（２）適合性フィードバックによる再検索の前の検索結果や検索条件（以下、再検索前情報と呼ぶ）を記憶する再検索前情報記憶ステップ。
（３）前記評価内容読み込みステップで読み込まれた評価内容を用いて、予め定められた方法に従って適合性フィードバックによる再検索を行う再検索実行ステップ。
（４）前記再検索実行ステップによる再検索の後の検索結果や検索条件（以下、再検索後情報と呼ぶ）を記憶する再検索後情報記憶ステップ。
（５）前記再検索実行ステップで検索された再検索の検索結果を出力する再検索結果出力ステップ。
（６）前記再検索前情報記憶ステップで記憶された再検索前情報と、前記再検索後情報記憶ステップで記憶された再検索後情報を予め定められた方法で比較することで、検索終了の判断指標となる値（以下、終了判断指標と呼ぶ）を算出する終了判断指標値算出ステップ。
（７）前記終了判断指標算出ステップで算出された終了判断指標を出力する終了判断指標出力ステップ。
【００３１】
【発明の実施の形態】
まず、本発明の第一の実施例の構成について図１を用いて説明する。
【００３２】
本発明を適用した文書検索システムは、検索結果を表示するディスプレイ１０１、登録・検索コマンドおよび検索結果に対する評価を入力するキーボード１０２、登録処理および検索処理を行う中央演算処理装置（ＣＰＵ）１０３、各種データを格納する磁気ディスク装置１０４、フロッピディスク１０５から各種プログラムおよびデータを読み込むフロッピディスクドライブ（ＦＤＤ）１０６、登録処理および検索処理用のプログラムならびにデータを一時的に格納する主メモリ１０７およびこれらを結ぶバス１０８から構成される。
【００３３】
磁気ディスク装置１０４は二次記憶装置の一つであり、テキスト１０９が格納される。ＦＤＤ１０６を介してフロッピディスク１０５に格納されている情報が、主メモリ１０７あるいは磁気ディスク装置１０４に読み込まれる。また、本発明の類似検索方法を実行するためのプログラムをフロッピディスク１０５に格納し、これを読み込んで実行することもできる。
【００３４】
主メモリ１０７には検索システム全体を制御するシステム制御プログラム１１０、検索対象となる文書の登録処理を行う文書登録プログラム１１１、検索処理の制御を行う検索制御プログラム１１２が格納される。
【００３５】
検索制御プログラム１１２は初回の検索において検索条件ベクトルを生成する検索条件ベクトル生成プログラム１１３、前回の検索結果を保持する再検索前情報格納プログラム１１４、検索結果に対する評価に基づいて検索条件ベクトルを修正する検索条件ベクトル修正プログラム１１５、検索条件を用いて類似検索を実行する類似検索実行プログラム１１６、類似検索の結果を出力する検索結果出力プログラム１１７、終了判断指標を算出する検索結果利用終了判断指標算出プログラム１１８、及び算出された終了判断指標を出力する終了判断指標出力プログラム１１９から構成される。
【００３６】
さらに、類似検索の検索条件として用いられる特徴文字列とその重みの組からなる検索条件ベクトルを格納する検索条件ベクトル格納エリア１２０、前回の検索結果を格納する再検索前情報格納エリア１２１、および、その他の一時的なデータを格納するワークエリア１２２が確保される。
【００３７】
なお、本実施例では、二次記憶装置に磁気ディスク装置を用いるものとするが、光磁気ディスク装置など他の二次記憶装置を用いてもかまわないし、ＳＡＮ（Storage Area Network）などネットワークを介して接続された記憶装置を用いてもかまわない。
【００３８】
また、本実施例では、フロッピディスク１０５に格納されている情報を、ＦＤＤ１０６を介して読み込む構成としたが、ＣＤ−ＲＯＭとＣＤ−ＲＯＭドライブというように他の記憶媒体と対応する読み取り装置を用いる構成としてもかまわない。
【００３９】
また、本実施例では入力装置としてキーボードを利用しているが、マウスを用いてもかまわないし、携帯電話やＰＤＡ（Personal Digital Assistant）のような携帯端末を用いてもかまわないし、その他の入力装置を用いてもかまわない。
【００４０】
また、本実施例では情報をディスプレイに出力する構成にしているが、ネットワークを介した他のＰＣのディスプレイに出力する構成にしてもかまわないし、情報を電子メールとして送信する構成にしてもかまわないし、他の出力装置を用いる構成としてもかまわない。
【００４１】
以下に本実施例における各プログラムの処理手順について説明する。
【００４２】
まず、システム制御プログラム１１０の処理手順を説明する。
【００４３】
システム制御プログラム１１０は、キーボード１０２から入力されるコマンドを判定し、文書登録コマンドであった場合には、文書登録プログラム１１１を起動し、文書の登録処理を実行する。また、前記コマンドが文書検索コマンドであった場合には、検索制御プログラム１１２を起動し、文書の検索処理を実行する。
【００４４】
次に、システム制御プログラム１１０により起動される文書登録プログラム１１１の処理手順を説明する。
【００４５】
文書登録プログラム１１１は、フロッピディスク１０５に格納されている全ての検索対象文書に対して、全ての検索対象文書内で検索対象文書を一意に識別することができる任意の識別子（以下、文書識別子と呼ぶ）を割り当てた後、磁気ディスク装置１０４内のテキスト１０９として格納する。
【００４６】
次に、システム制御プログラム１１０により起動される検索制御プログラム１１２の処理手順について図４に示すＰＡＤ（Problem Analysis Diagram）図を用いて説明する。
【００４７】
まず、ステップ４０１において、検索制御プログラム１１２は検索条件ベクトル生成プログラム１１３を起動し、検索条件ベクトルを生成した後、該検索条件ベクトルを検索条件ベクトル格納エリア１２０に格納する。
【００４８】
次に、ステップ４０２において、キーボード１０２から検索終了のコマンドが入力されるまで、ステップ４０３からステップ４０８までの処理を繰り返し実行する。
【００４９】
まず、ステップ４０３において、再検索前情報格納プログラム１１４を起動し、適合性フィードバックによる検索が行われる前の検索結果を再検索前情報格納エリア１２１に格納する。次に、類似検索実行プログラム１１６を起動し、検索条件ベクトル格納エリア１２０に格納されている検索条件ベクトルを用いて類似検索を実行する。次に、検索結果出力プログラム１１７を起動し、類似検索実行プログラム１１６により実行された類似検索の結果をディスプレイ１０１に出力する。次に、検索結果利用終了判断指標算出プログラム１１８を起動し、適合性フィードバックの終了の判断指標となる終了判断指標を算出する。次に、終了判断指標出力プログラム１１９を起動し、検索結果利用終了判断指標算出プログラム１１８により算出された終了判断指標をディスプレイ１０１に出力する。
【００５０】
次に、ステップ４０４において、キーボード１０２から入力されるコマンドを読み込む。
【００５１】
次に、ステップ４０５において、前記ステップ４０４において入力されたコマンドを判定し、検索結果出力プログラム１１７によりディスプレイ１０１に出力された類似検索の検索結果に含まれる文書に対する「所望する」あるいは「所望しない」という評価のコマンドであった場合には、ステップ４０７において、検索条件ベクトル修正プログラム１１５を起動し、前記評価コマンドに基づいて検索条件ベクトルを修正する。
【００５２】
また、ステップ４０６において、前記ステップ４０４において入力されたコマンドを判定し、検索を終了するコマンドであった場合には、ステップ４０８において、検索条件ベクトル格納エリア１２０、再検索前情報格納エリア１２１、ワークエリア１２２の内容をクリアする。
【００５３】
なお、本実施例では「所望する」又は「所望しない」という評価コマンドが入力されるものとしたが、特開２００１−２２７８７で開示されているように、「所望する」という評価コマンドのみが入力されるものとしてもかまわないし、所望の度合を入力するなど他の方法で評価を行ってもかまわない。
【００５４】
次に、検索制御プログラム１１２により起動される検索条件ベクトル生成プログラム１１３の処理手順について説明する。検索条件を生成する方法には従来技術１に開示される方法がある。以下に従来技術１で開示されている検索条件生成の処理を例に取り、検索条件生成プログラム１１３の処理手順を説明する。
【００５５】
検索条件生成プログラム１１３は、類似検索の検索条件としてキーボード１０２から入力される文書（以下、種文書と呼ぶ）をワークエリア１２２に読み込み、読み込んだ種文書から特徴文字列を抽出する。次に、抽出した前記特徴文字列の種文書における出現頻度を計数し、この特徴文字列と出現頻度の組を、後述の類似検索実行プログラム１１６の処理において用いられる検索条件ベクトルとして検索条件ベクトル格納エリア１２０へ格納する。
【００５６】
特徴文字列の抽出方法としては、特開平６−３０１７２２で開示されているような形態素解析に基づく方法であってもかまわないし、特開２０００−２３１５６３で開示されているようなｎ−ｇｒａｍを用いた方法であってもかまわないし、その他の方法であってもかまわない。
【００５７】
また、本実施例では種文書から抽出する特徴文字列の種類数を制限していないが、メモリ使用量の削減のために種文書から抽出する特徴文字列の種類数を制限してもかまわない。
【００５８】
以下に、検索条件ベクトル生成プログラム１１３により生成される検索条件ベクトルの生成手順を図５を用いて具体的に説明する。
【００５９】
まず、種文書５０１が種文書読み込み処理５０２により、ワークエリア１２２に読み込まれ、種文書データ５０３として格納される。
【００６０】
次に、特徴文字列抽出・出現頻度計数処理５０４により、前記種文書読み込み処理５０２により読み込まれた種文書データ５０３から特徴文字列が抽出されるが、本例ではあらかじめ定められた手順に従って「car」、「accident」、「cellular」、「phone」の特徴文字列が抽出されるものとし、前記特徴文字列が抽出された後、この特徴文字列の種文書データ５０３内における出現頻度が計数され、「car」が１回、「accident」が１回、「cellular」が２回、「phone」が３回という形で特徴文字列と出現頻度の組５０５が得られ、ワークエリア１２２に格納される。
【００６１】
最後に、格納処理５０６により、前記特徴文字列抽出・出現頻度計数処理５０４により取得された特徴文字列と出現頻度の組５０５が検索条件ベクトル５０７として、検索条件ベクトル格納エリア１２０に格納される。
【００６２】
次に、検索制御プログラム１１２により起動される再検索前情報格納プログラム１１４の処理手順について説明する。
【００６３】
まず、再検索前情報格納プログラム１１４は再検索前情報格納エリア１２１の内容をクリアする。次に、後述の類似検索実行プログラム１１６の処理においてワークエリア１２２に格納された最新の検索結果に含まれる検索対象文書の順位と文書識別子の組を、適合性フィードバックによる再検索を行う前の検索結果として、再検索前情報格納エリア１２１に格納する。
【００６４】
なお、本実施例では再検索前情報格納エリア１２１の内容をクリアしているが、履歴を保持するために再検索前情報格納エリア１２１の内容をクリアしない構成にしてもかまわない。また、本実施例ではすべての文書の順位と文書識別子の組を格納するものとしているが、メモリ使用量の削減のために、格納する文書の順位と文書識別子の組の個数を制限するものとしてもかまわない。
【００６５】
次に、検索制御プログラム１１２により起動される検索条件ベクトル修正プログラム１１５について説明する。検索条件ベクトル修正プログラム１１５は、検索条件ベクトル格納エリア１２０に格納されている検索条件ベクトルを、ユーザの評価に基づき修正する。なお、本実施例における検索条件ベクトル修正プログラム１１５の処理は、従来技術１で提案されている方法等で実現可能である。
【００６６】
次に、検索制御プログラム１１２により起動される類似検索実行プログラム１１６の処理手順を説明する。
【００６７】
まず、類似検索実行プログラム１１６は、検索条件ベクトル格納エリア１２０内の検索条件ベクトルと、テキスト１０９に格納されているすべての検索対象文書から生成する登録文書ベクトルとの類似度を数１に示す類似度算出式を用いて算出し、類似度の降順にすべての検索対象文書の文書識別子を並び替えた後、前記文書識別子と順位の組を検索結果としてワークエリア１２２に格納する。
【００６８】
なお、本実施例では格納する検索結果の件数を制限していないが、メモリ使用量の削減のために件数を制限してもかまわない。また、本実施例では順位と文書識別子の組を検索結果として格納するものとしたが、類似度を検索結果に含めるなど、他の情報を検索結果に付与して格納するものとしてもかまわない。
【００６９】
また、本実施例では順位と文書識別子の組をワークエリア１２２に格納しているが、一時的に磁気ディスク１０４に格納してもかまわない。また、本実施例では類似度の算出には前述の数１を用いるものとしたが、他の類似度算出式を用いてもかまわない。
【００７０】
次に、検索制御プログラム１１２により起動される検索結果出力プログラム１１７の処理手順について説明する。
【００７１】
検索結果出力プログラム１１７は類似検索実行プログラム１１６によりワークエリア１２２に格納された検索対象文書の順位と文書識別子の組をディスプレイ１０１に表示する。なお、本実施例では検索結果をディスプレイ１０１に出力しているが、検索結果を磁気ディスク１０４に出力して他の処理に使用してもかまわない。
【００７２】
次に、検索制御プログラム１１２により起動される検索結果利用終了判断指標算出プログラム１１８の処理手順を図６に示すＰＡＤ図を用いて説明する。
【００７３】
まず、ステップ６０１において、ワークエリア１２２に格納されている終了判断指標をリセットする。
【００７４】
次に、ステップ６０２において、再検索前情報格納エリア１２１に格納されている文書の数だけ、ステップ６０３およびステップ６０４の処理を繰り返し実行する。
【００７５】
ステップ６０３においては、ワークエリア１２２に格納されている再検索結果に含まれる文書のうち、未処理文書の順位変動を算出し、重み付けを行なう。即ち、類似検索実行プログラム１１６によりワークエリア１２２に格納された再検索結果に含まれる文書の内、未処理の文書の順位と文書識別子の組を一つ選択する。次に、再検索前情報格納プログラム１１４により再検索前情報格納エリア１２１に格納された再検索前の検索結果に含まれる文書の内、選択した文書識別子に対応する文書の順位を参照する。次に、再検索前の検索結果における該検索対象文書の順位から、再検索結果における順位を減算する。次に、算出した順位の差を再検索結果における該検索対象文書の順位で除算する。
【００７６】
最後に、ステップ６０４において、前記ステップ６０３で算出した順位変動を終了判断指標に加算する。
【００７７】
なお、図６に示す終了判断指標算出の処理で算出される終了判断指標は数３で表現される。この式で、Ｍは再検索前情報格納数であり、Ｒ（Ｄ）は前回検索結果における文書Ｄの順位であり、Ｒ’（Ｄ）は再検索結果における文書Ｄの順位である。
【００７８】
【数３】
0004003468.tif 000004
数３は、検索結果の順位変動が大きいほど、大きい終了判断指標の値を算出するものであり、検索結果に順位変動が起こらない場合には、終了判断指標は０となる。
【００７９】
なお、本実施例では終了判断指標をワークエリア１２２に格納しているが、磁気ディスク１０４に出力するなど、他の方法で終了判断指標を格納してもかまわない。また、本実施例では終了判断指標算出に数３を用いているが、順位の差の絶対値を取る構成にしてもかまわないし、他の算出式を用いてもかまわない。また、本実施例では順位の差から終了判断指標を算出するものとしているが、類似度の差から終了判断指標を算出する構成にしてもかまわない。
【００８０】
以下、検索結果利用終了判断指標算出プログラム１１８の処理を図３を用いて具体的に説明する。
【００８１】
検索結果３０１において５位の文書５を「所望する」と評価して再検索を行った結果、検索結果３０１から順位が大きく変動した再検索結果３０２が得られた場合の例において、数３に示す終了判断指標算出式を用いて終了判断指標を算出した場合、数４に示すように終了判断指標３．６５が得られる。
【００８２】
【数４】
0004003468.tif 000005
また、検索結果３０１からの再検索により順位の変動が小さい再検索結果３０３が得られた場合の例では、数５に示すように終了判断指標０．０５が得られる。
【００８３】
【数５】
0004003468.tif 000006
この結果、終了判断指標を参照することで順位の変動の大小を判断できる。
【００８４】
次に、検索制御プログラム１１２により起動される終了判断指標出力プログラム１１９の処理手順を説明する。終了判断指標出力プログラム１１９は検索結果利用終了判断指標算出プログラム１１８によりワークエリア１２２に格納された終了判断指標をディスプレイ１０１に表示する。
【００８５】
なお、本実施例では終了判断指標を数値としてディスプレイ１０１に出力しているが、算出された終了判断指標を図７に示すようにメッセージ７０１として表示してもかまわないし、終了判断指標に応じたメッセージ７０２を表示してもかまわないし、過去からの終了判断指標の遷移のグラフ７０３として表示してもかまわない。また、上記の情報を同時に出力してもかまわない。また、本例では終了判断指標をディスプレイ１０１に表示しているが、終了判断指標をワークエリア１２２に格納して他の処理に使用してもかまわないし、磁気ディスク１０４に格納して他の処理に使用してもかまわない。また、終了判断指標に応じて検索を指示するユーザインタフェースの使用可及び使用不可を切り替えてもかまわない。
【００８６】
以下、本実施例の処理の流れを図８を用いて説明する。
【００８７】
まず、種文書８０１が入力され、検索条件ベクトル生成プログラム１１３により、検索条件ベクトル８０２が生成される。
【００８８】
次に、類似検索実行プログラム１１６により類似検索が実行され、検索結果８０３が出力される。
【００８９】
次に、ユーザが検索結果８０３に対して「所望する」、「所望しない」という評価を下すことで、検索条件ベクトル修正プログラム１１５により、検索条件ベクトル８０２はユーザの行った評価に基づき検索条件ベクトル８０２ａに修正される。
【００９０】
次に、類似検索実行プログラム１１６により類似検索が再度実行され、再検索結果８０４が出力される。
【００９１】
次に、検索結果利用終了判断指標算出プログラム１１８により検索結果８０３と再検索結果８０４から終了判断指標８０５が算出される。
【００９２】
最後に、終了判断指標出力プログラム１１９により、終了判断指標８０５がメッセージ８０６として出力される。
【００９３】
なお、本実施例は文書検索の形態をとっているが、検索対象は色情報等を特徴量とする画像であってもかまわないし、他の電子データであってもかまわない。さらに、本実施例では特徴文字列をテキストから随時抽出する構成としていたが、大規模データベースにおいては検索速度の低下が問題となる。その場合、特開平９−３０９０７８で開示されているように、文書の登録時にあらかじめ特徴文字列を計数した出現頻度を磁気ディスク１０４に格納しておき、検索時に当該ファイルを参照するという構成を取ることで高速な類似検索が実現できる。また、当該ファイルにインデクスを付加することで更に高速な検索が実現できる。
【００９４】
以上示したように本実施例によれば、終了判断指標を確認することで容易に検索の終了を判断できるようになり、ユーザが誤った判断をすることを防ぐことができる。
【００９５】
次に、第二の実施例について説明する。
【００９６】
適合性フィードバックを用いた検索において、ユーザが検索結果に含まれる文書の内、検索条件ベクトルに類似したベクトルを持つ文書を評価した場合、評価による検索条件ベクトルの向きの変動が少なく、再検索結果において順位の変動が無い場合がある。この場合、第一の実施例では、終了判断指標が０となるため、他の文書を評価して検索を続行することで目的とする文書が検索できる場合でもユーザが検索を終了してしまうという問題がある。
【００９７】
上記の問題を説明するために、第一の実施例に基づく適合性フィードバックの処理の例を図９および図１０に示す。
【００９８】
本例では、図９に示す検索条件ベクトル９０１により検索結果９０２が検索されているものとする。また、ユーザは「Car accident while using a cellular phone」に関する文書を検索したいと考え、前記検索結果９０２における文書Ｄ２を「所望する」と評価したものとする。
【００９９】
以下に、適合性フィードバックを行った際の処理例を図１０に示す。なお、本例に示す検索条件ベクトル修正処理では、従来技術１で開示されているように、「所望する」と評価された文書に含まれる特徴文字列の出現頻度が、検索条件ベクトルの重みに加算されるものとしている。
【０１００】
まず、類似検索実行プログラム１１６により検索条件ベクトル９０１に基づいて検索されている検索結果９０２に対して、ユーザは文書Ｄ２を所望するという評価１００１を下す。
【０１０１】
次に、検索条件ベクトル修正プログラム１１５により、前記評価１００１に基づいて検索条件ベクトル９０１が検索条件ベクトル９０１ａに修正される。
【０１０２】
次に、類似検索実行プログラム１１６により前記検索条件ベクトル９０１ａに基づいて検索対象文書の順位変動が無い再検索結果１００２が検索される。
【０１０３】
次に、検索結果利用終了判断指標算出プログラム１１８により終了判断指標１００３が数６に示すように０と出力される。
【０１０４】
【数６】
0004003468.tif 000007
このため、類似した内容を含む別の文書Ｄ３を「所望する」と評価することで、検索条件ベクトル９０１ａがさらに検索条件ベクトル９０１ｂへと修正され、検索条件ベクトル９０１ｂから検索される検索結果１００６（以下、再々検索結果と呼ぶ）において「所望する」と評価した文書の順位が上昇する場合であっても、ユーザは、ユーザによる評価１００４において終了判断基準１００３が０であることから、適合性フィードバックの終了処理１００５を指示してしまう。
【０１０５】
以上の問題を解決するために、第二の実施例では、終了判断指標を検索条件ベクトルから算出する。以下に、本発明の第二の実施例の構成を図１１を用いて説明する。
【０１０６】
本実施例では、図１に示す第一の実施例とほぼ同様の構成をとるが、検索結果利用終了判断指標算出プログラム１１８の代わりに検索条件ベクトル利用終了判断指標算出プログラム１２３が用いられる。また、再検索前情報格納プログラム１１４ａの処理手順が再検索前情報格納プログラム１１４と異なる。
【０１０７】
次に、再検索前情報格納プログラム１１４ａの処理手順について説明する。
【０１０８】
まず、再検索前情報格納プログラム１１４ａは再検索前情報格納エリア１２１の内容をクリアする。次に、検索条件ベクトル格納エリア１２０に格納されている最新の検索条件ベクトルに含まれる特徴文字列と重みの組を、再検索を行う前の検索条件ベクトルとして、再検索前情報格納エリア１２１に格納する。
【０１０９】
次に、検索条件ベクトル利用終了判断指標算出プログラム１２３の処理について説明する。
【０１１０】
まず、再検索前情報格納プログラム１１４ａにより再検索前情報保持エリア１２１に格納されている再検索前の検索条件ベクトルに含まれる特徴文字列と重みの組を読み込む。次に、検索条件ベクトル修正プログラム１１５により検索条件ベクトル格納エリア１２０に格納されている再検索後の検索条件ベクトルに含まれる特徴文字列と重みの組を読み込む。最後に、数７に示す終了判断指標算出式を用いて終了判断指標を算出し、ワークエリア１２２に格納する。
【０１１１】
【数７】
0004003468.tif 000008
ここで、ｗ’（ｉ）は再検索後における検索条件ベクトルに含まれる特徴文字列ｉに対する重みであり、ｗ（ｉ）は再検索前における検索条件ベクトルに含まれる特徴文字列ｉに対する重みであり、Ｔ１は再検索の前後における検索条件ベクトルで一致する特徴文字列の異なり数（異なる特徴文字列の総数）であり、Ｔ２は再検索後における検索条件ベクトルに含まれる特徴文字列の異なり数であり、Ｔ３は再検索前における検索条件ベクトルに含まれる特徴文字列の異なり数である。
【０１１２】
数７は、再検索前の検索条件ベクトルと再検索後の検索条件ベクトルとの内積を算出するものであり、検索条件ベクトルの向きが検索条件ベクトル修正プログラム１１５による処理によって全く変動しなかった場合には、終了判断指標は０となる。
【０１１３】
以下に、本実施例の具体例を図１２を用いて説明する。
【０１１４】
本例では、図１０で示した処理の流れと同様に再検索結果１００２が検索されているものとする。この時点で、検索条件ベクトルは、（２，１，４，３）の重みを持つ検索条件ベクトル９０１から（４，４，５，３）の重みを持つ検索条件ベクトル９０１ａへと修正されている。
【０１１５】
ここで、検索条件ベクトル利用終了判断指標算出プログラム１２３により数７に基づいて終了判断指標が算出されると、終了判断指標１２０１は数８に示すように０．０７８となる。
【０１１６】
【数８】
0004003468.tif 000009
この結果、ユーザは終了判断指標１２０１を参照することで、再検索結果１００２において検索対象文書の順位が変動していなくても、再検索を続行することができる。本例では、ユーザによる評価１２０２において類似の内容を含む文書Ｄ３を「所望する」と評価することで、検索条件ベクトル修正プログラム１１５により、検索条件ベクトル９０１ａは更に検索条件ベクトル９０１ｂに修正され、類似検索実行プログラム１１６により、前記検索条件ベクトル９０１ｂに基づき類似検索が実行されることで、「所望する」と評価した文書の順位が上昇した再々検索結果１００６が検索されている。
【０１１７】
なお、本実施例では、終了判断指標を算出する際に用いる検索条件ベクトルに含まれるすべての特徴文字列を用いる構成としたが、メモリ使用量の削減のために特徴文字列の個数を制限する構成としてもかまわない。また、本実施例では終了判断指標算出式に数７を用いたが、他の式を用いてもかまわない。
【０１１８】
以上説明したように本実施例によれば、再検索によって順位の変動が無い場合でも、終了判断指標を参照することで、誤った判断をせずに検索を続行することができる。
【０１１９】
次に、第三の実施例について説明する。
【０１２０】
適合性フィードバックにおいては、目的の文書を検索するために検索を繰り返すと、所望と評価される登録文書ベクトルの重みが検索を繰り返しても不変であるのに対し、検索条件ベクトルの重みは増加する。このため、検索を繰り返すほど登録文書ベクトルの重みと検索条件ベクトルの重みの格差は大きくなる。
【０１２１】
この結果、前記格差が大きくなると、適合性フィードバックを行っても検索条件ベクトルの向きが大きく変動せず検索結果が変化しない状態（以下、収束状態と呼ぶ）に至る。
【０１２２】
収束状態に至った場合、ユーザは適合性フィードバックを終了すべきであり、検索結果に不満がある場合には適合性フィードバックのやり直し、更には検索手法自体を検討する必要がある。
【０１２３】
第二の実施例においては、検索条件ベクトルの変動が無い場合に、収束状態に至ったので検索を終了すべきなのか、あるいは検索条件ベクトルに類似したベクトルを持つ検索対象文書を評価したので他の文書を評価して検索を続行すべきなのかを判断することができず、検索の終了を誤って判断してしまうという問題がある。
【０１２４】
上記問題を解決するために本実施例では、再検索を行った後に算出される終了判断指標を再検索実行前にあらかじめ算出しユーザに提示する。
【０１２５】
まず、本実施例の構成を図１３を用いて説明する。
【０１２６】
本実施例では、図１に示す第一の実施例とほぼ同じ構成をとるが、検索結果利用終了判断指標算出プログラム１１８の代わりに予測終了判断指標算出プログラム１２４が用いられる。また、新たに検索条件ベクトル修正予測プログラム１２５が追加される。また、新たに予測検索条件ベクトル格納エリア１２６が確保される。また、終了判断指標出力プログラム１１９ａの処理手順が終了判断指標出力プログラム１１９と異なる。
【０１２７】
次に、予測終了判断指標算出プログラム１２４の処理手順を図１４に示すＰＡＤ図を用いて説明する。
【０１２８】
まず、ステップ１４０１において、類似検索実行プログラム１１６によりワークエリア１２２に格納された検索対象文書の順位と文書識別子の組から、指定できる評価コマンドの組み合わせ（以下、評価パターンと呼ぶ）を取得し、ワークエリア１２２に格納する。
【０１２９】
以下に、評価パターン取得の具体例を図１５を用いて説明する。
【０１３０】
本例では二つの文書が検索結果１５０１に含まれている場合を想定している。検索結果内の二つの文書に対して、「所望する」、「所望しない」という二通りの評価コマンドが指定できる場合、コマンドを指定しない場合も含めて、取りうる評価パターン１５０２は計８通りとなる。
【０１３１】
次に、ステップ１４０２において、ワークエリア１２２に格納されている評価パターンの数だけ、ステップ１４０３からステップ１４０６までの処理を繰り返し実行する。
【０１３２】
ステップ１４０３においては、未処理の評価パターンを一つ選択する。
【０１３３】
次に、ステップ１４０４において、検索条件ベクトル修正プログラム１１５により修正された検索条件ベクトル格納エリア１２０の内容を予測検索条件ベクトル格納エリア１２６にコピーする。
【０１３４】
次に、ステップ１４０５において、検索条件ベクトル修正予測プログラム１２５を起動し、予測検索条件ベクトル格納エリア１２６内の検索条件ベクトルを、該検索パターンが指定された場合の再検索により得られる検索条件ベクトル（以下、予測検索条件ベクトルと呼ぶ）に修正する。
【０１３５】
最後に、ステップ１４０６において、数７における再検索後の検索条件ベクトルｗ’（ｉ）を、予測検索条件ベクトル格納エリア１２６内の予測検索条件ベクトル、再検索前の検索条件ベクトルｗ（ｉ）を、検索条件ベクトル格納エリア１２０内の検索条件ベクトルとすることで、評価コマンドに基づいて再検索が行われた場合の終了判断指標（以下、予測終了判断指標と呼ぶ）を数７に基づいて算出し、ワークエリア１２２に格納する。
【０１３６】
なお、本実施例では、検索結果に対するすべての評価コマンドの組み合わせを取得するものとしているが、メモリ使用量の削減のために、評価できる検索対象文書の数を制限するなどして組み合わせの数を制限するものとしてもかまわない。
【０１３７】
次に、予測終了判断指標算出プログラム１２４により起動される検索条件ベクトル修正予測プログラム１２５の処理について説明する。
【０１３８】
検索条件ベクトル修正予測プログラム１２５は、予測検索条件ベクトル格納エリア１２６に格納されている検索条件ベクトルを、前記予測終了判断指標算出プログラム１２４の処理において予測終了判断指標を参照して選択された評価パターンに基づいて図１２と同様に検索条件ベクトルを修正する。
【０１３９】
次に、終了判断指標出力プログラム１１９ａの処理について説明する。
【０１４０】
終了判断指標出力プログラム１１９ａは予測終了判断指標算出プログラム１２４によりワークエリア１２２に格納された予測終了判断指標を例えば図１５に示すように評価パターンごとの予測終了判断指標の表１５０３としてディスプレイ１０１に表示する。
【０１４１】
本実施例では、検索条件ベクトルから予測終了判断指標を算出しているが、検索される文書の順位から予測終了判断指標を算出してもかまわないし、他の情報から予測終了判断指標を算出してもかまわない。また、本実施例では評価パターンごとに予測終了判断指標を出力しているが、予測終了判断指標の平均を出力するなど、他の形式で出力する構成にしてもかまわない。また、本実施例では、すべての評価パターンに対する予測終了判断指標を出力する構成としているが、評価コマンドが入力されたタイミングで予測終了判断指標を出力する構成としてもかまわない。
【０１４２】
本実施例によれば、再検索を実行する前に、再検索による検索条件ベクトルの変動を予測できるため、検索結果および検索条件ベクトル共に変動がない場合でも、他の文書を評価することで再検索を続行できることを知ることができ、誤った判断をせずに再検索を続行できる。
【０１４３】
【発明の効果】
システムの提示する終了判断指標を参照することで、効率的に適合性フィードバックにおける検索の終了判断を行うことができ、ユーザは少ない負荷で検索を行うことができるようになる。
【図面の簡単な説明】
【図１】本発明による文書検索システムの第一の実施例の全体構成を示す図である。
【図２】従来技術１による類似文書検索、適合性フィードバックの処理の概要を示す図である。
【図３】適合性フィードバックによる順位変動が大きい場合、および順位変動が少ない場合の一例を示す図である。
【図４】本発明の第一の実施例における検索制御プログラムの処理手順を示すＰＡＤ図である。
【図５】本発明の第一の実施例における検索条件ベクトルの生成手順を示す図である。
【図６】本発明の第一の実施例における検索結果利用終了判断指標算出プログラムの処理手順を示すＰＡＤ図である。
【図７】本発明の第一の実施例における終了判断指標の表示例を示す図である。
【図８】本発明の第一の実施例における処理の流れを示す図である。
【図９】本発明の第二の実施例における類似文書検索の例を示す図である。
【図１０】本発明の第二の実施例における第一の実施例の適合性フィードバックの処理の例を示す図である。
【図１１】本発明の第二の実施例における検索サブシステムの構成を示す図である。
【図１２】本発明の第二の実施例における適合性フィードバックの処理の例を示す図である。
【図１３】本発明の第三の実施例における検索サブシステムの構成を示す図である。
【図１４】本発明の第三の実施例における予測終了判断指標算出プログラムの処理手順を示すＰＡＤ図である。
【図１５】本発明の第三の実施例における予測終了判断指標の表示手順を示す図である。
【符号の説明】
１０１ ディスプレイ
１０２ キーボード
１０３ 中央演算処理装置（ＣＰＵ）
１０４ 磁気ディスク装置
１０５  フロッピディスク
１０６  フロッピディスクドライブ（ＦＤＤ）
１０７  主メモリ
１０８  バス
１１０  システム制御プログラム
１１１  文書登録プログラム
１１２  検索制御プログラム
１１３  検索条件ベクトル生成プログラム
１１４  再検索前情報格納プログラム
１１５  検索条件ベクトル修正プログラム
１１６  類似検索実行プログラム
１１７  検索結果出力プログラム
１１８  検索結果利用終了判断指標算出プログラム
１１９  終了判断指標出力プログラム
１２０  検索条件ベクトル格納エリア
１２１  再検索前情報格納エリア
１２２  ワークエリア
１２３  検索条件ベクトル利用終了判断指標算出プログラム
１２４  予測終了判断指標算出プログラム
１２５  検索条件ベクトル修正予測プログラム
１２６  予測検索条件ベクトル格納エリア
【図１】
0004003468.tif 000010
【図２】
0004003468.tif 000011
【図３】
0004003468.tif 000012
【図４】
0004003468.tif 000013
【図５】
0004003468.tif 000014
【図６】
0004003468.tif 000015
【図７】
0004003468.tif 000016
【図８】
0004003468.tif 000017
【図９】
0004003468.tif 000018
【図１０】
0004003468.tif 000019
【図１１】
0004003468.tif 000020
【図１２】
0004003468.tif 000021
【図１３】
0004003468.tif 000022
【図１４】
0004003468.tif 000023
【図１５】
0004003468.tif 000024