(57)【特許請求の範囲】
【請求項１】
検索エンジンのキーワード辞書の構築に供されるユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算装置であって、
ユーザが入力したクエリの頻度情報を格納したユーザクエリデータベースと、
前記ユーザが選択したリソースの選択頻度情報を格納したユーザリソースデータベースと、
前記クエリが入力された際に選択されたリソースの選択頻度情報を格納したクエリリソースデータベースと、
特徴スコアの計算対象であるユーザが入力したクエリのリソースを格納したシードデータベースと、
前記対象でないユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとそのリソースを格納した逆シードデータベースと、
前記ユーザクエリデータベースと前記ユーザリソースデータベースと前記クエリリソースデータベースと前記シードデータベースと前記逆シードデータベースとに基づき前記対象のユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算手段と
を備えたこと
を特徴とする特徴スコア計算装置。
【請求項２】
前記特徴スコア計算手段は、
前記シードデータベースに基づきシード用のユーザ初期ベクトルとクエリ初期ベクトルとリソース初期ベクトルとを作成し、前記逆シードデータベースに基づき逆シード用のユーザ初期ベクトルとクエリ初期ベクトルとリソース初期ベクトルとを作成する手段と、
前記ユーザクエリデータベースに基づきユーザからクエリへの遷移確率を示す要素を格納したユーザクエリ遷移行列とクエリからユーザへの遷移確率を示す要素を格納したクエリユーザ遷移行列とを作成し、前記ユーザリソースデータベースに基づきユーザからリソースへの遷移確率を示す要素を格納したユーザリソース遷移行列とリソースからユーザへの遷移確率を示す要素を格納したリソースユーザ遷移行列とを作成し、前記クエリリソースデータベースに基づきクエリからリソースへの遷移確率を示す要素を格納したクエリリソース遷移行列とリソースからクエリへの遷移確率を示す要素を格納したリソースクエリ遷移行列とを作成する手段と、
前記シード用のユーザ初期ベクトルと前記クエリユーザ遷移行列と前記リソースユーザ遷移行列との線形演算によりシード用のユーザスコアベクトルを作成し、前記シード用のクエリ初期ベクトルと前記ユーザクエリ遷移行列と前記リソースクエリ遷移行列との線形演算によりシード用のクエリスコアベクトルを作成し、前記シード用のリソース初期ベクトルと前記ユーザリソース遷移行列と前記クエリリソース遷移行列との線形演算によりシード用のリソーススコアベクトルを作成する手段と、
前記逆シード用のユーザ初期ベクトルと前記クエリユーザ遷移行列と前記リソースユーザ遷移行列との線形演算により逆シード用のユーザスコアベクトルを作成し、前記逆シード用のクエリ初期ベクトルと前記ユーザクエリ遷移行列と前記リソースクエリ遷移行列との線形演算により逆シード用のクエリスコアベクトルを作成し、前記逆シード用のリソース初期ベクトルと前記ユーザリソース遷移行列と前記クエリリソース遷移行列との線形演算により逆シード用のリソーススコアベクトルを作成する手段と、
前記シード用のユーザスコアベクトルと前記逆シード用のユーザスコアベクトルとの線形演算により前記対象のユーザの特徴スコアを算出し、前記シード用のクエリスコアベクトルと前記逆シード用のクエリスコアベクトルとの線形演算により前記対象のクエリの特徴スコアを算出し、前記シード用のリソーススコアベクトルと前記逆シード用のリソーススコアベクトルとの線形演算により前記対象のリソースの特徴スコアを算出する手段と
を備えたこと
を特徴とする請求項１に記載の特徴スコア計算装置。
【請求項３】
前記特徴スコア計算手段は、
前記シード用のユーザスコアベクトル，クエリスコアベクトル，リソーススコアベクトルを当該シード用のユーザスコアベクトル，クエリスコアベクトル，リソーススコアベクトルを算出する線形演算に供して更新し、
前記逆シード用のユーザスコアベクトル，クエリスコアベクトル，リソーススコアベクトルを当該逆シード用のユーザスコアベクトル，クエリスコアベクトル，リソーススコアベクトルを算出する線形演算に供して更新すること
を特徴とする請求項２に記載の特徴スコア計算装置。
【請求項４】
前記シードデータベースは、前記対象であるユーザとこのユーザが入力したクエリとこのクエリのリソースとが重み付けされて格納され、
前記逆シードデータベースは、前記対象でないユーザとこのユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとこのクエリのリソースとが重み付けされて格納されたこと
を特徴とする請求項１から３のいずれか１項に記載の特徴スコア計算装置。
【請求項５】
前記シードデータベースはリソースよりもユーザ及びクエリが高く重み付けされ、前記逆シードデータベースはリソースよりもユーザ及びクエリが低く重み付けされたこと
を特徴とする請求項４に記載の特徴スコア計算装置。
【請求項６】
検索エンジンのキーワード辞書の構築に供されるユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算装置が実行する特徴スコア計算方法であって、
ユーザが入力したクエリの頻度情報を格納したユーザクエリデータベースと、前記ユーザが選択したリソースの選択頻度情報を格納したユーザリソースデータベースと、前記クエリが入力された際に選択されたリソースの選択頻度情報を格納したクエリリソースデータベースと、特徴スコアの計算対象であるユーザが入力したクエリのリソースを格納したシードデータベースと、前記対象でないユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとそのリソースを格納した逆シードデータベースとに基づき前記対象のユーザとクエリとリソースの特徴スコアを算出するステップを有すること
を特徴とする特徴スコア計算方法。
【請求項７】
前記特徴スコアを算出するステップは、
前記シードデータベースに基づきシード用のユーザ初期ベクトルとクエリ初期ベクトルとリソース初期ベクトルとを作成し、前記逆シードデータベースに基づき逆シード用のユーザ初期ベクトルとクエリ初期ベクトルとリソース初期ベクトルとを作成するステップと、
前記ユーザクエリデータベースに基づきユーザからクエリへの遷移確率を示す要素を格納したユーザクエリ遷移行列とクエリからユーザへの遷移確率を示す要素を格納したクエリユーザ遷移行列とを作成し、前記ユーザリソースデータベースに基づきユーザからリソースへの遷移確率を示す要素を格納したユーザリソース遷移行列とリソースからユーザへの遷移確率を示す要素を格納したリソースユーザ遷移行列とを作成し、前記クエリリソースデータベースに基づきクエリからリソースへの遷移確率を示す要素を格納したクエリリソース遷移行列とリソースからクエリへの遷移確率を示す要素を格納したリソースクエリ遷移行列とを作成するステップと、
前記シード用のユーザ初期ベクトルと前記クエリユーザ遷移行列と前記リソースユーザ遷移行列との線形演算によりシード用のユーザスコアベクトルを作成し、前記シード用のクエリ初期ベクトルと前記ユーザクエリ遷移行列と前記リソースクエリ遷移行列との線形演算によりシード用のクエリスコアベクトルを作成し、前記シード用のリソース初期ベクトルと前記ユーザリソース遷移行列と前記クエリリソース遷移行列との線形演算によりシード用のリソーススコアベクトルを作成するステップと、
前記逆シード用のユーザ初期ベクトルと前記クエリユーザ遷移行列と前記リソースユーザ遷移行列との線形演算により逆シード用のユーザスコアベクトルを作成し、前記逆シード用のクエリ初期ベクトルと前記ユーザクエリ遷移行列と前記リソースクエリ遷移行列との線形演算により逆シード用のクエリスコアベクトルを作成し、前記逆シード用のリソース初期ベクトルと前記ユーザリソース遷移行列と前記クエリリソース遷移行列との線形演算により逆シード用のリソーススコアベクトルを作成するステップと、
前記シード用のユーザスコアベクトルと前記逆シード用のユーザスコアベクトルとの線形演算により前記対象のユーザの特徴スコアを算出し、前記シード用のクエリスコアベクトルと前記逆シード用のクエリスコアベクトルとの線形演算により前記対象のクエリの特徴スコアを算出し、前記シード用のリソーススコアベクトルと前記逆シード用のリソーススコアベクトルとの線形演算により前記対象のリソースの特徴スコアを算出するステップとを有すること
を特徴とする請求項６に記載の特徴スコア計算方法。
【請求項８】
コンピュータを請求項１から５のいずれか１項に記載の特徴スコア計算装置を構成する各手段として機能させることを特徴とする特徴スコア計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報検索分野において特定カテゴリのキーワード辞書の構築に供されるシード情報の特徴スコアを獲得する技術に関するものである。
【背景技術】
【０００２】
ユーザが入力したキーワードと当該ユーザがクリックしたＵＲＬの情報を格納した検索ログなどを用いて、特定のカテゴリのキーワードを収集するにあたり、例えば非特許文献１に開示された方法が知られている。
【０００３】
非特許文献１の方法では、検索ログからクエリ、ＵＲＬの二部グラフを構築し、クエリからＵＲＬへの遷移確率、ＵＲＬからクエリへの遷移確率に基づいてスコアを伝播する。この際、予め選択された特定カテゴリのクエリに対応した初期ベクトルを用意し、この値を伝播することで、当該クエリから遷移確率が高いＵＲＬが高いスコアを獲得し、同様に高いスコアを獲得したＵＲＬから遷移確率が高いクエリが高いスコアを獲得する。この仕組みを利用することにより、高いスコアを獲得したクエリを特定カテゴリのキーワードとして利用することが可能となる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Deng, H.; Lyu, M. R. King, I., "A generalized Co-HITS algorithm and its application to bipartite graphs", In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28 - July 1 , 2009 ,Paris ,France , pp. 239-248
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術においてはユーザとクエリとの関連性，ユーザとＵＲＬとの関連性に基づいた特徴スコアの計算を行うことができないという課題があった。また、特定カテゴリのキーワードのシードを用いると、当該キーワードと関連性の高く、かつ特定カテゴリではないキーワードが高い特徴スコアを得るという課題があった。これらの課題により、従来技術においては特定カテゴリのキーワード辞書を構築する際にシード情報の特徴スコアの推定精度が低下するおそれがあった。
【０００６】
本発明は上記の課題を解決して検索エンジンのキーワード辞書の構築に供されるシード情報の特徴スコアを精度よく獲得することを目的とする。
【課題を解決するための手段】
【０００７】
そこで、本発明の特徴スコア計算装置は、検索エンジンのキーワード辞書の構築に供されるユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算装置であって、ユーザが入力したクエリの頻度情報を格納したユーザクエリデータベースと、前記ユーザが選択したリソースの選択頻度情報を格納したユーザリソースデータベースと、前記クエリが入力された際に選択されたリソースの選択頻度情報を格納したクエリリソースデータベースと、特徴スコアの計算対象であるユーザが入力したクエリのリソースを格納したシードデータベースと、前記対象でないユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとそのリソースを格納した逆シードデータベースと、前記ユーザクエリデータベースと前記ユーザリソースデータベースと前記クエリリソースデータベースと前記シードデータベースと前記逆シードデータベースとに基づき前記対象のユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算手段とを備える。
【０００８】
また、本発明の特徴スコア計算方法は、検索エンジンのキーワード辞書の構築に供されるユーザとクエリとリソースの特徴スコアを算出する特徴スコア計算装置が実行する特徴スコア計算方法であって、ユーザが入力したクエリの頻度情報を格納したユーザクエリデータベースと、前記ユーザが選択したリソースの選択頻度情報を格納したユーザリソースデータベースと、前記クエリが入力された際に選択されたリソースの選択頻度情報を格納したクエリリソースデータベースと、特徴スコアの計算対象であるユーザが入力したクエリのリソースを格納したシードデータベースと、前記対象でないユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとそのリソースを格納した逆シードデータベースとに基づき前記対象のユーザとクエリとリソースの特徴スコアを算出するステップを有する。
【０００９】
尚、本発明は上記装置の手段としてコンピュータを機能させるプログラムまたは上記方法のステップをコンピュータに実行させるプログラムの態様とすることもできる。
【発明の効果】
【００１０】
以上の発明によれば検索エンジンのキーワード辞書の構築に供されるシード情報の特徴スコアを精度よく獲得できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態における特徴スコア計算装置のブロック構成図。
【図２】同実施形態におけるログ解析の手順を説明したフローチャート図。
【図３】同実施形態における特徴スコア計算の手順を説明したフローチャート図。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら本発明の実施の形態について説明するが本発明はこの実施形態に限定されるものではない。
【００１３】
［概要］
検索エンジンにおける特定カテゴリのキーワード辞書を構築する際、従来はクリックログのクエリとＵＲＬ（当該クエリのリソース）の関係に着目してクエリの特徴スコアを算出していた。これに対して、本実施形態の特徴スコア計算装置は、ユーザとの関係にも着目し、クエリとＵＲＬとの関係に加えて、ＵＲＬとユーザの関係、ユーザとクエリの関係も考慮することにより、特定カテゴリのキーワード辞書の構築に供されるシード情報（本実施形態ではユーザ，クエリ，ＵＲＬ）の特徴スコアの推定精度を向上させる。
【００１４】
［装置の構成］
図１に示された本実施形態の特徴スコア計算装置１はログ解析部２０，特徴スコア計算部７０を備える。ログ解析部２０，特徴スコア計算部７０はコンピュータのハードウェアリソースによって実現される。すなわち、同装置１は、少なくとも、演算装置（ＣＰＵ）、記憶装置（メモリ、ＨＤＤ等）、通信インタフェース等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソース（ＯＳ、アプリケーション等）と協働することによりログ解析部２０，特徴スコア計算部７０が実装される。
【００１５】
ログ解析部２０は、クリックログＤＢ（データベース）１０に基づき、ユーザクエリＤＢ３０，ユーザＵＲＬＤＢ４０，クエリＵＲＬＤＢ５０の作成、更新を行う（図２のＳ１０１〜Ｓ１０６）。
【００１６】
クリックログＤＢ１０のデータ構造の例を表１に示す。クリックログＤＢ１０は、ログのタイムスタンプ，ユーザＩＤ，入力クエリ，当該クエリによってクリック（選択）されたウェブページのＵＲＬの情報から構成される。クリックログＤＢ１０は例えば検索エンジンのクリックログを用いて用意することができる。ここでカラムが１つだけ空であるレコードが存在してもよい。
【００１７】
【表１】
0006040136.tif 000002
【００１８】
ユーザクエリＤＢ３０のデータ構造の例を表２に示す。ユーザクエリＤＢ３０はユーザＩＤ，クエリと頻度情報から構成され、当該ユーザによって入力されたクエリの頻度情報を格納している。
【００１９】
【表２】
0006040136.tif 000003
【００２０】
ユーザＵＲＬＤＢ４０のデータ構造の例を表３に示す。ユーザＵＲＬＤＢ４０はユーザＩＤ，ＵＲＬと頻度情報から構成され、当該ユーザによってクリックされたＵＲＬ（本発明におけるリソースに相当）のクリック頻度情報（本発明における選択頻度情報に相当）を格納している。
【００２１】
【表３】
0006040136.tif 000004
【００２２】
クエリＵＲＬＤＢ５０のデータ構造の例を表４に示す。クエリＵＲＬＤＢ５０はクエリ，ＵＲＬと頻度情報から構成され、当該クエリが入力された際にクリックされたＵＲＬのクリック頻度情報を格納している。
【００２３】
【表４】
0006040136.tif 000005
【００２４】
特徴スコア計算部７０は、ユーザクエリＤＢ３０，ユーザＵＲＬＤＢ４０，クエリＵＲＬＤＢ５０，シードＤＢ６０，逆シードＤＢ６１に基づき、ユーザスコアＤＢ８０，クエリスコアＤＢ９０，ＵＲＬスコアＤＢ１００の作成、更新を行う（図３のＳ２０１〜Ｓ２１０）。
【００２５】
シードＤＢ６０のデータ構造の例を表５に示す。シードＤＢ６０は、特徴スコアの計算対象であるユーザが入力したクエリのリソース（本事例ではＵＲＬ）を格納している。このＤＢ６０のタイプカラムには、シード情報のタイプ情報が格納され、値カラムに対応する情報そのものが格納される。表５ではユーザやＵＲＬのシード情報の例を示している。例えば、タイプカラムが「クエリ」で値カラムが「バルス」の場合には、「バルス」クエリに対して重み１．０が初期値として与えられている。また、シードＤＢ６０においてユーザ及びクエリはＵＲＬよりも高く重み付けされている。尚、シード情報はユーザ、クエリ、ＵＲＬ以外にも指定することが可能である。
【００２６】
【表５】
0006040136.tif 000006
【００２７】
逆シードＤＢ６１のデータ構造の例を表６に示す。逆シードＤＢ６１は特徴スコアの計算対象でないユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとそのリソース（本事例ではＵＲＬ）を格納している。逆シードＤＢ６１は、シードＤＢ６０と同様の形式となっているが、ユーザ及びクエリはＵＲＬよりも低く重み付けされている。尚、シードＤＢ６０と同様にシード情報はユーザ、クエリ、ＵＲＬ以外にも指定することが可能である。
【００２８】
【表６】
0006040136.tif 000007
【００２９】
後述するがユーザスコアＤＢ８０はユーザＩＤとそのスコアを格納する（例えば表７）。クエリスコアＤＢ９０はクエリとそのスコアを格納する（例えば表８）。ＵＲＬスコアＤＢ１００はＵＲＬとそのスコアを格納する（例えば表９）。
【００３０】
上記のＤＢ１０，３０〜５０，６０，６１，８０〜１００は特徴スコア計算装置１の記憶部（例えばＨＤＤ等）若しくはこの装置１とネットワークで繋がるサーバに構築される。
【００３１】
［処理手順の説明］
本実施形態の処理手順について事例を参照しながら説明する。
【００３２】
先ず、図２を参照しながらログ解析部２０が実行するステップ（Ｓ１０１〜Ｓ１０６）について説明する。
【００３３】
Ｓ１０１：クリックログＤＢ１０から未処理のレコードを選択する。
【００３４】
Ｓ１０２：前記選択したレコードからユーザＩＤ，クエリ，クリックＵＲＬを取得する。
【００３５】
Ｓ１０３：前記取得したユーザＩＤとクエリについて、ユーザクエリＤＢ３０のユーザＩＤとクエリが同一のレコードの頻度カラムに対して頻度を加算する。但し、ユーザクエリＤＢ３０において該当するレコードが存在しない場合には新たにレコードを追加し、頻度を１とする。
【００３６】
Ｓ１０４：前記取得したユーザＩＤとＵＲＬについて、ユーザＵＲＬＤＢ４０のユーザＩＤとＵＲＬが同一のレコードの頻度カラムに対して頻度を加算する。但し、該当するレコードが存在しない場合には新たにレコードを追加し、頻度を１とする。
【００３７】
Ｓ１０５：前記取得したクエリとＵＲＬについて、クエリＵＲＬＤＢ５０のクエリとＵＲＬが同一のレコードの頻度カラムに対して頻度を加算する。但し、該当するレコードが存在しない場合には新たにレコードを追加し、頻度を１とする。
【００３８】
Ｓ１０６：未処理のレコードがある場合、Ｓ１０１に戻る。未処理のレコードがない場合には処理を終了する。
【００３９】
次いで、図３を参照しながら特徴スコア計算部７０が実行するステップ（Ｓ２０１〜Ｓ２１０）について説明する。
【００４０】
Ｓ２０１：シードＤＢ６０の情報に基づき、シード用のユーザ初期ベクトルｐ0，クエリ初期ベクトルｑ0，ＵＲＬ初期ベクトルｒ0を作成する。また、逆シードＤＢ６１の情報に基づき、逆シード用のユーザ初期ベクトルｐ’0，クエリ初期ベクトルｑ’0，ＵＲＬ初期ベクトルｒ’0を作成する。
【００４１】
シード用のベクトルｐ0，ｑ0，ｒ0の長さはそれぞれユニークユーザ数Ｕ，ユニーククエリ数Ｑ，ユニークＵＲＬ数Ｖであり、予め与えられているものか、またはユーザクエリＤＢ３０，ユーザＵＲＬＤＢ４０，クエリＵＲＬＤＢ５０から計算される。ユーザ初期ベクトルｐ0の構築には、シードＤＢ６０のうちタイプがユーザのレコードを全て取得し、値カラムに格納されたユーザＩＤに該当する要素を重みカラムに格納された値とする。尚、ベクトルは要素の総和が１になるように正規化を行う。クエリ初期ベクトルｑ0，ＵＲＬ初期ベクトルｒ0についても同様にシードＤＢ６０に設定された値を利用する。
【００４２】
逆シード用のベクトルｐ’0，ｑ’0，ｒ’0の長さはそれぞれユニークユーザ数Ｕ，ユニーククエリ数Ｑ，ユニークＵＲＬ数Ｖであり、予め与えられているものか、またはユーザクエリＤＢ３０，ユーザＵＲＬＤＢ４０，クエリＵＲＬＤＢ５０から計算される。ユーザ初期ベクトルｐ’0の構築には、逆シードＤＢ６１のうちタイプがユーザのレコードを全て取得し、値カラムに格納されたユーザＩＤに該当する要素を重みカラムに格納された値とする。尚、逆シードＤＢ６１から構築されたベクトルｐ’0，ｑ’0，ｒ’0についてもベクトルは要素の総和が１になるように正規化を行う。クエリ初期ベクトルｑ’0，ＵＲＬ初期ベクトルｒ’0についても同様に逆シードＤＢ６１に設定された値を利用する。
【００４３】
Ｓ２０２：ユーザクエリＤＢ３０の情報に基づき、ユーザクエリ遷移行列Ｍpq，クエリユーザ遷移行列Ｍqpを作成する。
【００４４】
行列ＭpqはＵ×Ｑ行列であり、（ｉ，ｊ）要素がユーザｉからクエリｊへの遷移確率を表す。ユーザクエリＤＢ３０におけるユーザ，クエリに該当する頻度を行列Ｍpqの要素として格納する。行列Ｍpqはその各行の総和が１になるように正規化される。
【００４５】
行列ＭqpはＱ×Ｕ行列であり、（ｉ，ｊ）要素がクエリｉからユーザｊへの遷移確率を表す。行列Ｍpqと同様にユーザクエリＤＢ３０におけるユーザ，クエリに該当する頻度を行列Ｍqpの要素として格納する。行列Ｍqpはその各行の総和が１になるように正規化される。
【００４６】
Ｓ２０３：ユーザＵＲＬＤＢ４０に基づき、ユーザＵＲＬ遷移行列Ｍpr，ＵＲＬユーザ遷移行列Ｍrpを作成する。
【００４７】
行列ＭprはＵ×Ｖ行列であり、（ｉ，ｊ）要素がユーザｉからＵＲＬｊへの遷移確率を表す。ユーザＵＲＬＤＢ４０におけるユーザ，ＵＲＬに該当する頻度が行列Ｍprの要素として格納される。行列Ｍprはその各行の総和が１になるように正規化される。
【００４８】
行列ＭrpはＶ×Ｕ行列であり、（ｉ，ｊ）要素がＵＲＬｉからユーザｊへの遷移確率を表す。行列Mprと同様にユーザＵＲＬＤＢ４０におけるユーザ，ＵＲＬに該当する頻度が行列Ｍrpの要素として格納される。行列Ｍrpはその各行の総和が１になるように正規化される。
【００４９】
Ｓ２０４：クエリＵＲＬＤＢ５０の情報に基づき、クエリＵＲＬ遷移行列Ｍqr，ＵＲＬクエリ遷移行列Ｍrqを作成する。
【００５０】
行列ＭqrはＱ×Ｖ行列であり、（ｉ，ｊ）要素がクエリｉからＵＲＬｊへの遷移確率を表す。クエリＵＲＬＤＢ５０におけるクエリ，ＵＲＬに該当する頻度が行列Ｍqrの要素として格納される。行列Ｍqrはその各行の総和が１になるように正規化される。
【００５１】
行列ＭrqはＶ×Ｑ行列であり、（ｉ，ｊ）要素がＵＲＬｉからクエリｊへの遷移確率を表す。行列Ｍqrと同様にクエリＵＲＬＤＢ５０におけるクエリ，ＵＲＬに該当する頻度が行列Ｍrqの要素として格納される。行列Ｍrqはその各行の総和が１になるように正規化される。
【００５２】
Ｓ２０５：ユーザスコアベクトルｐ＝（１／Ｕ，１／Ｕ，…，１／Ｕ）T，クエリスコアベクトルｑ＝（１／Ｑ，１／Ｑ，…，１／Ｑ）T，ＵＲＬスコアベクトルｒ＝（１／Ｖ，１／Ｖ，…，１／Ｖ）Tとしてベクトルの初期化を行う。
【００５３】
同様に逆シードから得られたユーザスコアベクトルｐ’＝（１／Ｕ，１／Ｕ，…，１／Ｕ）T，クエリスコアベクトルｑ’＝（１／Ｑ，１／Ｑ，…，１／Ｑ）T，ＵＲＬスコアベクトルｒ’＝（１／Ｖ，１／Ｖ，…，１／Ｖ）Tとしてベクトルの初期化を行う。
【００５４】
Ｓ２０６：カウント変数ｃｏｕｎｔを０に初期化する。
【００５５】
Ｓ２０７：前記作成された遷移行列Ｍpq，Ｍqp，Ｍpr，Ｍrp，Ｍqr，Ｍrqに基づきユーザスコアベクトルｐ，ｐ’、クエリスコアベクトルｑ，ｑ’、ＵＲＬスコアベクトルｒ，ｒ’を更新する。
【００５６】
ユーザスコアベクトルｐの更新は、式（１）で示したクエリスコアベクトルからの伝播スコアＳqpとＵＲＬスコアベクトルからの伝播スコアＳrpの線形和によって行う。
【００５７】
【数１】
0006040136.tif 000008
【００５８】
式（１）のαpは予め任意に設定されたもので例えばαp＝０．５と設定される。
【００５９】
ｐ(t+1)の（ｔ＋１）は更新後のベクトルという意味を表し、伝播スコア計算のためには更新前のベクトルを利用するため、この記法を用いる。
【００６０】
伝播スコアＳqpはクエリスコアベクトルからユーザスコアベクトルに対する伝播スコアであり、式（２）によって算出される。ｑ(t)は更新前のクエリスコアベクトルを表す。
【００６１】
【数２】
0006040136.tif 000009
【００６２】
伝播スコアＳrpは式（３）によって算出される。ｒ(t)は更新前のＵＲＬスコアベクトルを表す。
【００６３】
【数３】
0006040136.tif 000010
【００６４】
式（２）（３）のλpは予め任意に設定されたもので例えばλp＝０．５と設定される。
【００６５】
クエリスコアベクトルｑとＵＲＬスコアベクトルｒの更新も同様の方法で行う。
【００６６】
すなわち、クエリスコアベクトルｑの更新は、式（４）で示したユーザスコアベクトルからの伝播スコアＳpqとＵＲＬスコアベクトルからの伝播スコアＳrqの線形和によって行う。αqは予め任意に設定されたもので例えばαq＝０．５と設定される。
【００６７】
【数４】
0006040136.tif 000011
【００６８】
伝播スコアＳpqはユーザスコアベクトルからクエリスコアベクトルに対する伝播スコアであり、式（５）によって算出される。ｐ(t)は更新前のユーザスコアベクトルを表す。
【００６９】
【数５】
0006040136.tif 000012
【００７０】
伝播スコアＳrqは式（６）によって算出される。ｒ(t)は更新前のＵＲＬスコアベクトルを表す。
【００７１】
【数６】
0006040136.tif 000013
【００７２】
式（５）（６）のλqは予め任意に設定されたもので例えばλq＝０．５と設定される。
【００７３】
ＵＲＬスコアベクトルｒの更新は、式（７）で示したユーザスコアベクトルからの伝播スコアＳprとクエリスコアベクトルからの伝播スコアＳqrの線形和によって行う。αrは予め任意に設定されたもので例えばαr＝０．５と設定される。
【００７４】
【数７】
0006040136.tif 000014
【００７５】
伝播スコアＳprはユーザスコアベクトルからＵＲＬスコアベクトルに対する伝播スコアであり、式（８）によって算出される。ｐ(t)は更新前のユーザスコアベクトルを表す。
【００７６】
【数８】
0006040136.tif 000015
【００７７】
伝播スコアＳqrは式（９）によって算出される。ｑ(t)は更新前のクエリスコアベクトルを表す。
【００７８】
【数９】
0006040136.tif 000016
【００７９】
式（８）（９）のλrは予め任意に設定されたもので例えばλr＝０．５と設定される。
【００８０】
そして、更新後のユーザスコアベクトルｐ，クエリスコアベクトルｑ，ＵＲＬスコアベクトルｒを正規化する。すなわち、以下の式（１０）（１１）（１２）による処理を行う。
【００８１】
【数１０】
0006040136.tif 000017
【００８２】
逆シードから得られたユーザスコアベクトルｐ’，クエリスコアベクトルｑ’，ＵＲＬスコアベクトルｒ’についてもシードを用いた更新方法と同様の手順で行うことができる。
【００８３】
具体的には式（１）〜（３）においてｐ0の代わりにｐ0’を用い、式（４）〜（６）においてq0の代わりにｑ0’を用い、式（７）〜（９）においてｒ0の代わりにｒ0’を用いることで更新できる。この際、式（１）〜（９）のαp，αq，αr，λp，λq，λrに相当するパラメータには前記設定された値と異なる値を代入できる。
【００８４】
Ｓ２０８：カウント変数をインクリメントする。
【００８５】
Ｓ２０９：ｃｏｕｎｔ＜Ｔの場合、Ｓ２０７に戻り処理を続ける。ｃｏｕｎｔ＜Ｔでない場合はＳ２１０に進む。
【００８６】
Ｓ２１０：以上のＳ２０１〜Ｓ２０９によってシードＤＢ６０から得られたユーザスコアベクトルｐと逆シードＤＢ６１から得られたユーザスコアベクトルｐ’とから算出されたユーザスコアをユーザスコアＤＢ８０に出力する。ユーザスコアは予め設定したγpを用いた式（１３）で示した線形和によって算出される。尚、この式（１３）以外にｐ／ｐ’に例示される線形演算よってスコアを算出できる。
【００８７】
【数１１】
0006040136.tif 000018
【００８８】
また、Ｓ２０１〜Ｓ２０９のシードＤＢ６０から得られたクエリスコアベクトルｑと逆シードＤＢ６１から得られたクエリスコアベクトルｑ’とから算出したクエリスコアをクエリスコアＤＢ９０に出力する。スコアはユーザスコアベクトルｐ，ｐ’と同様に予め設定したパラメータγqを用いた以下の式（１４）によって算出される。尚、この式（１４）以外にｑ／ｑ’に例示される線形演算によってスコアを算出できる。
【００８９】
【数１２】
0006040136.tif 000019
【００９０】
さらに、Ｓ２０１〜Ｓ２０９によってシードＤＢ６０から得られたＵＲＬスコアベクトルｒと逆シードＤＢ６１から得られたＵＲＬスコアベクトルｒ’とから算出されたＵＲＬスコアをＵＲＬスコアＤＢ１００に出力する。スコアはユーザスコアベクトルｐ，ｐ’と同様に予め設定したパラメータｒを用いた以下の式（１５）によって算出される。尚、この式（１５）以外にｒ／ｒ’に例示される線形演算によってスコアを算出できる。
【００９１】
【数１３】
0006040136.tif 000020
【００９２】
Ｓ２１０で得られたユーザスコアＤＢ８０の一例を以下の表７に示した。
【００９３】
【表７】
0006040136.tif 000021
【００９４】
Ｓ２１０で得られたクエリスコアＤＢ９０の一例を以下の表８に示した。
【００９５】
【表８】
0006040136.tif 000022
【００９６】
Ｓ２１０で得られたＵＲＬスコアＤＢ１００の一例を以下の表９に示した。
【００９７】
【表９】
0006040136.tif 000023
【００９８】
以上のユーザ，クエリ，ＵＲＬの特徴スコアは検索エンジンにおける特定カテゴリのキーワード辞書、例えば、検索エンジンのインデクサにおける辞書ファイルの構築に供される。
【００９９】
［本実施形態の効果］
以上の説明から明らかなように特徴スコア計算装置１によればクエリとＵＲＬとの関連性に加えてユーザとクエリの関連性、ユーザとＵＲＬとの関連性に基づく遷移情報を利用したユーザ，クエリ，ＵＲＬの特徴スコアが得られる。
【０１００】
また、シード情報のみでは不適切に高いスコアが獲得されてしまうクエリに対しては、シード情報に加えて逆シード情報を考慮したスコア計算によって、特徴スコアの値を下げることが可能となる。
【０１０１】
したがって、特定カテゴリのキーワード辞書の構築に供される計算対象のシード情報の特徴スコアの推定精度が向上する。
【０１０２】
また、Ｓ２０１〜Ｓ２１０の説明から明らかなように、シード用，逆シード用のユーザスコアベクトル，クエリスコアベクトル，ＵＲＬスコアベクトルが更新可能であるので、最新のシード情報の特徴スコアを取得できる。
【０１０３】
さらに、シードＤＢ６０において特徴スコアの計算対象であるユーザとこのユーザが入力したクエリとこのクエリのＵＲＬとが重み付けされて格納されている。一方、逆シードＤＢ６１においては前記対象でないユーザとこのユーザが入力した当該対象のクエリとはカテゴリが異なるクエリとこのクエリのＵＲＬとが重み付けされて格納されている。これにより、シードＤＢ６０，逆シードＤＢ６１の各要素の重みに依存したシード情報の特徴スコアの計算が行える。
【０１０４】
特に、表５，６に示したようにシードＤＢ６０においてＵＲＬよりもユーザ及びクエリが高く重み付けされる一方で逆シードＤＢ６１においてＵＲＬよりもユーザ及びクエリが低く重み付けされることで、計算対象であるユーザとこのユーザが入力したクエリの特徴スコアと、当該対象でないユーザとこのユーザが入力した当該対象のクエリとはカテゴリが異なるクエリの特徴スコアとの大小関係がより一層明確となる。これにより、シード情報の特徴スコアの推定精度がさらに向上する。
【０１０５】
［本発明のプログラムとしての態様］
本発明は特徴スコア計算装置１の機能部２０，７０の一部若しくは全てとしてコンピュータを機能させるプログラムで構成しこれを当該コンピュータに実行させることで実現できる。または、同装置１が実行する過程Ｓ１０１〜Ｓ１０６，Ｓ２０１〜Ｓ２１０の一部若しくは全てをコンピュータに実行させるプログラムで構成しこれを当該コンピュータに実行させることで実現できる。そして、このプログラムをそのコンピュータが読み取り可能な周知の記録媒体（例えば、ＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）、ＭＯ（Ｍａｇｎｅｔｏ‐Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）‐ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）‐ＲＯＭ、ＣＤ‐Ｒ、ＣＤ‐ＲＷ、ＨＤＤ、ＳＳＤ、リムーバブルディスク等）に格納して提供できる。または、前記プログラムをインターネットや電子メール等でネットワークを介して提供できる。
【符号の説明】
【０１０６】
１…特徴スコア計算装置
１０…クリックログＤＢ
２０…ログ解析部
３０…ユーザクエリＤＢ、４０…ユーザＵＲＬＤＢ、５０…クエリＵＲＬＤＢ
６０…シードＤＢ、６１…逆シードＤＢ
７０…特徴スコア計算部（特徴スコア計算手段）
８０…ユーザスコアＤＢ、９０…クエリスコアＤＢ、１００…ＵＲＬスコアＤＢ
【図１】
0006040136.tif 000024
【図２】
0006040136.tif 000025
【図３】
0006040136.tif 000026