(57)【特許請求の範囲】
【請求項１】
ランキング関数生成のための正解データベースを生成するために用いるクエリを選択するためのクエリ選択装置であって、
検索ログを元に入力クエリとユーザによってクリックされた文書の情報を格納するクリックログ記憶手段と、
前記クリックログ記憶手段に含まれるクエリのエントロピー記述量が短いほど高い値になるクエリスコアを求め、クエリスコア記憶手段に格納するクエリスコア計算手段と、
前記クエリスコア記憶手段からスコアが最大のクエリを取得し、該クエリを含むレコードを前記クリックログ記憶手段から取得して選択クリックログ記憶手段に格納するクエリ選択手段と、
を有することを特徴とするクエリ選択装置。
【請求項２】
前記クエリスコア計算手段は、
前記クリックログ記憶手段からクエリによって検索された文書数を取得し、文書空間内における情報量、該クエリの該クリックログ記憶手段における出現確率、及び該クエリによって文書がクリックされた頻度を該クエリにおけるクリック総数で除した値から求められたクリックエントロピーを用いて、前記クエリスコアを求める手段を含む
請求項１記載のクエリ選択装置。
【請求項３】
請求項１または２に記載のクエリ選択装置を構成する各手段としてコンピュータを機能させるためのクエリ選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ選択装置及びプログラムに係り、特に、ウェブ検索システムにおいて、検索結果のランキングを実現するためのスコアを算出するランキング関数を自動的に生成するためのクエリ選択装置及びプログラムに関する。
【背景技術】
【０００２】
図７は、従来のランキング関数生成システムの構成を示す。
【０００３】
従来技術の概要を簡単に述べる。
【０００４】
ランキング関数生成システムは、Ｗｅｂページデータベース（ＤＢ）１０、クリックログＤＢ１１０、正解ＤＢ３０、特徴ＤＢ４０、特徴抽出装置２０、正解抽出装置１２０、ランキング関数生成装置９０から構成される。
【０００５】
ＷｅｂページＤＢ１０には、図８に示すように、検索対象となるＷｅｂページの情報（ページ識別子、ＵＲＬ、本文）が格納されている。
【０００６】
クリックログＤＢ１１０には、図９に示すように入力されたクエリに対して提示された検索結果のうち、クリックされた文書の情報（ページ識別子）が格納されている。
【０００７】
正解データベース３０には、図１０に示すように、各クエリに対して、各ページのランキング情報が格納されている。
【０００８】
正解抽出装置１２０は、クリックログＤＢ１１０を入力として、正解ＤＢ３０を生成する。正解ＤＢ３０を生成する手法として、クエリ・文書ペアに対するクリックログを全て足しこむことによって得られる総クリック数を用いる（例えば、非特許文献２参照）。
【０００９】
特徴抽出装置２０は、正解ＤＢ３０とＷｅｂページＤＢ１０を入力として、特徴を抽出し（例えば、非特許文献２参照）、特徴ＤＢ４０を生成する。特徴ＤＢ４０の例を図１１に示す。具体的にはクエリが当該ウェブページに何回出現するか、という単語頻度 (Term Frequency; TF) や、当該ウェブページの重要度のようなものを特徴と呼び、その値を特徴値と呼ぶ。また、ある検索クエリにおいてウェブページが何回クリックされたかといったクリックログを用いた情報を用いることができる。ここで、クリックログとは検索システムのログのことで、ユーザが入力した検索クエリの検索結果に対して、ユーザのクリック情報を記録したものである。
【００１０】
特徴ＤＢ４０と正解ＤＢ３０を元に、ランキング関数生成装置９０において、ランキング関数を生成する。ランキング関数生成機能としては、非特許文献２などが挙げられ、その実装としては非特許文献３などが挙げられる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Z. Dou、 R. Song、 X. Yuan and J.-R. Wen: Are click-through data adequate for learning web search rankings? In Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM), pp.73-83, 2008.
【非特許文献２】T. Joachims、 Optimizing Search Engines Using Clickthrough Data、 Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD)、 ACM、 2002
【非特許文献３】svm_rank (http://www.cs.cornell.edu/People/tj/svm_light/svm_rank.html)
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記従来技術のクリックログＤＢ１１０の中には、アダルトクエリのように検索結果の適合性に関わらず多数の検索結果をクリックされるようなログが含まれており、このようなクリックログの情報はランキング関数生成に悪影響を与えると推察される。
【００１３】
本発明は、上記の点に鑑みなされたもので、ランキング関数生成に有益なクエリを選択することで、高精度なランキング関数生成が可能なクエリ選択装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
図１は、本発明の原理構成図である。
【００１５】
本発明（請求項１）は、ランキング関数生成のための正解データベースを生成するために用いるクエリを選択するためのクエリ選択装置であって、
検索ログを元に入力クエリとユーザによってクリックされた文書の情報を格納するクリックログ記憶手段１１０と、
クリックログ記憶手段１１０に含まれるクエリのエントロピー記述量が短いほど高い値になるクエリスコアを求め、クエリスコア記憶手段１６０に格納するクエリスコア計算手段１５０と、
クエリスコア記憶手段１６０からスコアが最大のクエリを取得し、該クエリを含むレコードをクリックログ記憶手段１１０から取得して選択クリックログ記憶手段１４０に格納するクエリ選択手段１３０と、を有する。
【００１６】
また、本発明（請求項２）は、請求項１のクエリスコア計算手段１５０は、
クリックログ記憶手段１１０からクエリによって検索された文書数を取得し、文書空間内における情報量、該クエリの該クリックログ記憶手段１１０における出現確率、及び該クエリによって文書がクリックされた頻度を該クエリにおけるクリック総数で除した値から求められたクリックエントロピーを用いて、クエリスコアを求める手段を含む。
【００１７】
本発明（請求項３）は、請求項１または２に記載のクエリ選択装置を構成する各手段としてコンピュータを機能させるためのクエリ選択プログラムである。
【発明の効果】
【００１８】
上記のように、クリックログＤＢに含まれるログ全てを用いるのではなく、クエリ選択装置により予めノイズとなるクエリを除去し、ランキング関数生成に有益なクエリを選択することで、高精度なランキング関数を生成することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の原理構成図である。
【図２】本発明の一実施の形態におけるシステム構成図である。
【図３】本発明の一実施の形態におけるクエリスコアＤＢの例である。
【図４】本発明の一実施の形態における選択クリックログＤＢの例である。
【図５】本発明の一実施の形態におけるクエリスコア計算分処理のフローチャートである。
【図６】本発明の一実施の形態におけるクエリ選択部の処理のフローチャートである。
【図７】従来のランキング関数生成技術におけるランキング関数生成システムの構成図である。
【図８】従来のランキング関数生成システムにおけるＷｅｂページＤＢの例である。
【図９】従来のランキング関数生成システムにおけるクリックログＤＢの例である。
【図１０】従来のランキング関数生成システムにおける正解ＤＢの例である。
【図１１】従来のランキング関数生成システムにおける特徴ＤＢの例である。
【発明を実施するための形態】
【００２０】
以下図面と共に、本発明の実施の形態を説明する。
【００２１】
図２は、本発明の一実施の形態におけるシステム構成を示す。
【００２２】
同図において、図７の構成と同一構成要素については同一符号を付し、その説明を省略する。
【００２３】
従来手法ではクリックログＤＢ１１０を正解抽出装置１２０の入力として正解ＤＢ３０を生成していたが、本発明では選択クリックログＤＢ１４０を用いて正解ＤＢ３０を生成する点が異なる。
【００２４】
まず、クエリ選択装置１００の概要を述べる。
【００２５】
クエリ選択装置１００は、クエリスコア計算部１５０、クエリ選択部１３０、クエリスコアＤＢ１６０を有する。
【００２６】
クエリスコアＤＢ１６０は、クエリがどれだけランキング関数生成に有益であるかという情報を保持しており、図３に示すように、クリックログＤＢ１１０に保持されたクエリ全てについてスコアを格納している。
【００２７】
クエリスコア計算部１５０は、クリックログＤＢ１１０を入力として、クエリ毎のスコアを算出してクエリスコアＤＢ１６０に出力する。詳細については後述する。
【００２８】
クエリ選択部１３０は、クエリスコアＤＢ１３０に格納されたスコア情報を元に、予め設定されたクエリ数のクリックログ情報を選択クリックログＤＢ１４０に出力する。選択クリックログＤＢ１４０に格納されるデータの例を図４に示す。選択クリックログＤＢ１４０が保持するデータ構造はクリックログＤＢ１１０と本質的に同じであるため、選択クリックログＤＢ１４０を用いて従来技術と同じ枠組みでランキング関数生成を行うことも可能である。
【００２９】
以下に、クエリスコア計算部１５０の詳細と処理の流れについて述べる。
【００３０】
図５は、本発明の一実施の形態におけるクエリスコア計算部の処理のフローチャートである。
【００３１】
ステップ１１）  クリックログＤＢ１１０に含まれる文書総数を取得し、これをDtotalとしメモリ（図示せず）に格納する。
【００３２】
ステップ１２）  クリックログＤＢ１１０に含まれるクエリ総数を取得し、これをQtotalとし、メモリ（図示せず）に格納する。
【００３３】
ステップ１３）  クリックログＤＢ１１０に未処理のクエリが含まれる場合は、ステップ１４に移行し、そうでない場合は処理を終了する。
【００３４】
ステップ１４）  クリックログＤＢ１１０から未処理のクエリｑを取得する。
【００３５】
ステップ１５）  クエリｑによって検索された文書数Ｄ（ｑ）を取得し、ステップ１１で取得した文書総数Dtotalを用いて、文書空間内における情報量ｈ（ｐ）を以下の式により計算し、メモリ（図示せず）に格納する。
【００３６】
【数１】
0005410359.tif 000002
で計算される。ここでｐは、
【００３７】
【数２】
0005410359.tif 000003
を用いて求めることができる。
【００３８】
ステップ１６）  クエリｑのクリックログＤＢ１１０における出現頻度｜ｑ｜を取得し、クエリ出現確率ｐｑを、ステップ１２で取得したQtotalを用いて次のように計算し、メモリ（図示せず）に格納する。
【００３９】
【数３】
0005410359.tif 000004
ステップ１７）  クエリｑの検索によってクリックされた文書集合を元にｐ（ｄ｜ｑ）を次のように計算する。
【００４０】
【数４】
0005410359.tif 000005
ここでfreq(d,q)はクエリｑによって文書ｄがクリックされた頻度を表している。分母はクエリｑにおけるクリック総数を表している。これを用いて、クリックエントロピーＨ（ｐ（ｑ））を
【００４１】
【数５】
0005410359.tif 000006
によって算出し、メモリ（図示せず）に格納する。
【００４２】
ステップ１８）  上記のステップ１５，１６，１７で得られ、メモリ（図示せず）に格納されているｐ，ｐｑ，Ｈ（ｐ（ｑ））を取得して、クエリｑの一文書あたりの記述長ＤＬ（ｑ）、すなわちクエリスコアを以下の式により求める。
【００４３】
【数６】
0005410359.tif 000007
上記の式で算出されたクエリスコアＤＬ（ｑ）をクエリスコアＤＢ１６０に書き出し、ステップ１３に移行する。
【００４４】
次に、クエリ選択部１３０の処理の流れについて説明する。
【００４５】
図６は、本発明の一実施の形態におけるクエリ選択部の処理のフローチャートである。
【００４６】
ステップ２１）  クエリ選択部１３０は、選択するクエリの総数Qselectを設定する。
【００４７】
ステップ２２）  選択済みのクエリ数S ＞ Qselectの場合、処理を終了する。それ以外の場合、ステップ２３に移行する。
【００４８】
ステップ２３）  クエリスコアＤＢ１６０から未選択であり、スコアが最大のクエリｑを取得する。
【００４９】
ステップ２４）  クリックログＤＢ１１０からクエリｑを含むレコードを取得し、選択クリックログＤＢ１４０に出力し、ステップ２２に移行する。
【００５０】
以上の処理によって、選択クリックログＤＢ１４０を生成することができるため、正解抽出装置１２０においてノイズとなるクエリを除去した有益なクエリを用いて正解ＤＢ３０を生成することが可能となる。これにより、ランキング関数生成装置９０では、当該正解ＤＢ３０を用いて効率のよいランキング関数を生成することが可能となる。
【００５１】
なお、上記のクエリ選択装置１００の動作をプログラムとして構築し、クエリ選択装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５２】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５４】
１０  ＷｅｂページＤＢ
２０  特徴抽出装置
３０  正解ＤＢ
４０  特徴ＤＢ
９０  ランキング関数生成装置
１００  クエリ選択装置
１１０  クロックログ記憶手段、クリックログＤＢ
１２０  正解抽出装置
１３０  クエリ選択手段、クエリ選択部
１４０  選択クリックログ記憶手段、選択クリックログＤＢ
１５０  クエリスコア計算手段、クエリスコア計算部
１６０  クエリスコア記憶手段、クエリスコアＤＢ
【図１】
0005410359.tif 000008
【図２】
0005410359.tif 000009
【図３】
0005410359.tif 000010
【図４】
0005410359.tif 000011
【図５】
0005410359.tif 000012
【図６】
0005410359.tif 000013
【図７】
0005410359.tif 000014
【図８】
0005410359.tif 000015
【図９】
0005410359.tif 000016
【図１０】
0005410359.tif 000017
【図１１】
0005410359.tif 000018