JP4781466B2

JP4781466B2 - 文書重要度算出プログラム

Info

Publication number: JP4781466B2
Application number: JP2009508735A
Authority: JP
Inventors: 郁生斎藤
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2007-03-16
Filing date: 2007-03-16
Publication date: 2011-09-28
Anticipated expiration: 2027-03-16
Also published as: WO2008126184A1; JPWO2008126184A1; US8260788B2; US20090313246A1

Description

本発明は、複数の文書についてそれぞれの重要度を算出する文書重要度算出プログラム、文書重要度算出装置、文書重要度算出方法に関するものである。

従来、Ｗｅｂページ等のリンクを有する文書の検索を行う検索システムにおいて、検索結果の表示順位を決定するための技術がある（例えば、特許文献１、特許文献２、非特許文献１、非特許文献２参照）。特許文献１の技術は、検索対象文書のリンク関係だけから各文書の重要度を決定し、重要度の高い順に検索結果を表示する。
米国特許第６２８５９９９号明細書米国特許出願公開第２００５／００７１７４１号明細書 "The PageRank Citation Ranking: Bringing Order to the Web"：Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd （1998年1月29日） "Efficient Computation of PageRank" ：Taher H. Haveliwala（1999年10月18日）

しかしながら、特許文献１の技術は、重要度算出のための制約が大きく、検索対象文書のリンク関係だけから検索対象文書の重要度を算出することしかできなかった。

また、従来の技術を基にして、複数の種類のパラメータの影響を考慮した重要度を算出するための幾つかの方法がある。特許文献２の技術においては、リンク関係に基づいて重要度を算出し、その重要度を他のパラメータに基づいて修正する方法が示されているが、リンク関係により計算された情報が他のパラメータに基づく修正により失われてしまう。また、特許文献２の技術において、多くの種類のパラメータの影響を考慮する具体的な方法は示されていない。

また、パラメータ毎に重要度を算出し、得られた複数の重要度に重み付けを与える方法等が考えられるが、それぞれのパラメータに対する重要度を算出するために、時間のかかる繰り返し計算をパラメータの数だけ行うことになるため、パラメータ数が増えると計算量が膨大になってしまう。

本発明は上述した問題点を解決するためになされたものであり、文書に関するパラメータの影響を考慮した文書の重要度を効率的に算出する文書重要度算出プログラム、文書重要度算出装置、文書重要度算出方法を提供することを目的とする。

上述した課題を解決するため、本発明は、Ｎ個の文書それぞれの重要度の算出をコンピュータに実行させる文書重要度算出プログラムであって、全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定ステップと、縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復ステップとをコンピュータに実行させる。

また、本発明は、Ｎ個の文書それぞれの重要度の算出を行う文書重要度算出装置であって、全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定部と、縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復部とを備える。

また、本発明は、Ｎ個の文書それぞれについての重要度の算出を行う文書重要度算出方法であって、全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定ステップと、縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復ステップとを実行する。

本実施の形態に係る検索システムの構成の一例を示すブロック図である。本実施の形態に係る文書リストファイルの一例を示す表である。本実施の形態に係る作成日時リストファイルの一例を示す表である。本実施の形態に係るリンク関係ファイルの一例を示す表である。本実施の形態に係る評価リストファイルの一例を示す表である。本実施の形態に係る参照回数リストファイルの一例を示す表である。本実施の形態に係る重要度算出部の動作の一例を示すフローチャートである。本実施の形態に係る重要度リストファイルの一例を示す表である。従来の反復計算処理の一例を示すフローチャートである。本実施の形態に係る反復計算処理の一例を示すフローチャートである。本実施の形態に係る行列決定処理により決定された行列Ｄの一例を示す表である。本実施の形態に係る反復計算処理により計算された計算結果の一例を示す表である。本実施の形態に係る集計データの一例を示す表である。本実施の形態に係るリンク関係の一例を示す表である。本実施の形態に係るリンク関係データの一例を示す表である。本実施の形態に係る第１の実施例において行列決定処理により決定された重みデータを示す表である。本実施の形態に係る第１の実施例において行列決定処理により決定された行列Ｄを示す表である。本実施の形態に係る第１の実施例において反復計算処理により計算された計算結果を示す表である。本実施の形態に係る第２の実施例において行列決定処理により決定された重みデータを示す表である。本実施の形態に係る第２の実施例において行列決定処理により決定された行列Ｄを示す表である。本実施の形態に係る第２の実施例において反復計算処理により計算された計算結果を示す表である。本実施の形態に係る第３の実施例において行列決定処理により決定された重みデータを示す表である。本実施の形態に係る第３の実施例において行列決定処理により決定された行列Ｄを示す表である。本実施の形態に係る第３の実施例において反復計算処理により計算された計算結果を示す表である。本実施の形態に係る第４の実施例において行列決定処理により決定されたＲａｎｄ（）の値を示す表である。本実施の形態に係る第４の実施例において行列決定処理により決定された行列Ｄを示す表である。本実施の形態に係る第４の実施例において反復計算処理により計算された計算結果を示す表である。本実施の形態に係る第５の実施例において行列決定処理により決定された行列Ｄを示す表である。本実施の形態に係る第５の実施例において反復計算処理により計算された計算結果を示す表である。

以下、本発明の実施の形態について図面を参照しつつ説明する。

本実施の形態においては、本発明の文書重要度算出装置を適用した検索システムについて説明する

まず、本実施の形態に係る検索システムの構成について説明する。

図１は、本実施の形態に係る検索システムの構成の一例を示すブロック図である。この検索システムは、端末１、検索サーバ２、文書管理部３、検索インデックス管理部４、重要度算出部５を備える。端末１、検索サーバ２、文書管理部３、検索インデックス管理部４、重要度算出部５は、それぞれコンピュータで実現される。

文書管理部３は、検索サーバ２による検索の対象となる文書である検索対象文書を管理する。検索インデックス管理部４は、検索対象文書の検索インデックスを登録すると共に、重要度算出部５から送信される検索対象文書の重要度リストファイルを検索インデックスに反映する。端末１は、参照者の操作に従って、検索の指示、文書の参照の指示を検索サーバ２へ送信する。また、端末１は、参照者による検索対象文書の評価を検索サーバ２へ送信する。

検索サーバ２は、端末１からの検索の指示に従って、検索インデックス管理部４の検索インデックスを用いて検索対象文書を検索し、検索結果を端末１へ送信する。また、検索サーバ２は、端末１からの文書の参照の指示に従って、指示された文書を文書管理部３から取得し、端末１へ送信すると共に、文書の参照の履歴を参照履歴情報として重要度算出部５へ送信する。また、検索サーバ２は、端末１から送信された検索対象文書の評価を重要度算出部５へ送信する。

重要度算出部５は、ＣＰＵ及びメモリを有し、ＣＰＵがメモリ上で実行するプログラムとして、文書リスト作成部１２、作成日時抽出部１３、リンク解析部１４、評価受付部１５、参照回数算出部１６、行列決定部１７、反復計算部１８を備える。なお、パラメータ取得部は、実施の形態における文書リスト作成部１２、作成日時抽出部１３、リンク解析部１４、評価受付部１５、参照回数算出部１６に対応する。

文書リスト作成部１２は、文書管理部３に管理された検索対象文書のリストである文書リストファイルを作成する。図２は、本実施の形態に係る文書リストファイルの一例を示す表である。作成日時抽出部１３は、文書管理部３に管理された検索対象文書の作成日時のリストである作成日時リストファイルを作成する。図３は、本実施の形態に係る作成日時リストファイルの一例を示す表である。リンク解析部１４は、文書管理部３に管理された検索対象文書のリンクを解析し、解析結果をリンク関係ファイルとして生成する。図４は、本実施の形態に係るリンク関係ファイルの一例を示す表である。評価受付部１５は、検索サーバ２から送信された検索対象文書の参照者による評価を受信し、評価リストファイルとして生成する。図５は、本実施の形態に係る評価リストファイルの一例を示す表である。参照回数算出部１６は、参照履歴情報から検索対象文書の参照回数を算出し、参照回数リストファイルとして生成する。図６は、本実施の形態に係る参照回数リストファイルの一例を示す表である。

次に、重要度算出部５の動作について説明する。

図７は、本実施の形態に係る重要度算出部の動作の一例を示すフローチャートである。まず、文書リスト作成部１２、作成日時抽出部１３、リンク解析部１４、評価受付部１５、参照回数算出部１６は、各文書のパラメータを取得し、文書リストファイル、作成日時リストファイル、リンク関係ファイル、評価リストファイル、参照回数リストを生成するパラメータ取得処理を行う（Ｓ１１、パラメータ取得ステップ）。次に、行列決定部１７は、これらの各ファイルに基づいて、検索対象文書の重要度の算出のための行列Ｄを決定する行列決定処理を行う（Ｓ１２、行列決定ステップ）。次に、反復計算部１８は、行列Ｄを用いて検索対象文書の重要度を算出する反復計算処理を行い、算出結果を重要度リストファイルとして検索インデックス管理部４へ送信し（Ｓ１３、反復計算ステップ）、このフローは終了する。図８は、本実施の形態に係る重要度リストファイルの一例を示す表である。

次に、反復計算処理の原理について説明する。

まず、検索対象文書の総数をＮとし、文書管理部３により検索対象文書に１からＮまでのＩＤが振られたとする。また、ＩＤがｎである検索対象文書をＰ＿ｎとする。また、正の実数をｕ＿ｎ（ｎ＝１，２，…Ｎ）とするとき、ｕ＿ｎを要素とする縦ベクトルをｕとする。ｄ＿ｉ＿ｊ（ｉ，ｊ＝１，２，…Ｎ）を任意の正の実数とし、第（ｉ，ｊ）成分がｄ＿ｉ＿ｊである行列をＤとする。

線形代数のペロン・フロベニウスの定理より、任意のＤに対して、Ｄは正の固有値（ｅ
ｕ＝Ｄｕを満たす０でないベクトルｕが存在するような数ｅのこと。このときのｕをｅに対するＤの固有ベクトルという）を持ち、そのうちの最大のものをＤのフロベニウス根という。フロベニウス根ｅに対するＤの固有ベクトルｕは正のベクトルであり、そのうち｜ｕ｜＝１となるものはただ１つである。ここでのノルムは無限大ノルム（｜ｕ｜＝ｍａｘ｛｜ｕ＿ｎ｜；ｎ＝１，２，…，Ｎ｝）とする。

検索対象文書Ｐ＿ｎ（ｎ＝１，２， …，Ｎ）に与えられた様々なパラメータ（例：リンク関係、作成日時、参照者による評価、文書の参照回数など）に応じて、システムの設計者は自由にＤを定義することができる。このように定義したＤに対して、Ｄのフロベニウス根ｅと、｜ｕ｜＝１を満たすようなｅに対する正の固有ベクトルｕはただ１組存在するので、このときのｕ＿ｎをＰ＿ｎの重要度と定義する。

ここで、Ｐ＿ｎからＬ＿ｎ個のリンクがあると仮定し、次式のようにｄ＿ｍ＿ｎを定義すれば、ｕ＝Ｄｕ，｜ｕ｜＝１を満たすｕは、特許文献１の技術と同様な値を算出することができる。ここでのノルムは、１ノルム（｜ｕ｜＝ｕ＿１＋ｕ＿２＋…＋ｕ＿Ｎ）とし、Ｐ＿ｎから出るリンクの数をＬ＿ｎとする。また、定数ｃ＝０．１５とする。

ｄ＿ｍ＿ｎ＝ｃ／Ｎ
（Ｐ＿ｎからＰ＿ｍへのリンクがないとき）
ｄ＿ｍ＿ｎ＝ｃ／Ｎ＋（１−ｃ）／Ｌ＿ｎ
（Ｐ＿ｎからＰ＿ｍへのリンクがあるとき）

次に、特許文献１等の技術を用いた従来の反復計算処理と、本実施の形態に係る反復計算部１８による反復計算処理とを比較する。

まず、従来の反復計算処理について説明する。図９は、従来の反復計算処理の一例を示すフローチャートである。まず、従来の反復計算処理は、繰り返し回数ｋ＝１とし、長さＮの縦ベクトルｖ＿ｋの要素を全て１として初期化を行う（Ｓ２１）。次に、従来の反復計算処理は、ｋを１増加させる（Ｓ２２）。次に、従来の反復計算処理は、ｖ＿ｋ＝Ｄｖ＿（ｋ−１）を計算する（Ｓ２３）。

次に、従来の反復計算処理は、今回得られたｖ＿ｋと前回得られたｖ＿（ｋ−１）から差のノルム｜ｖ＿ｋ−ｖ＿（ｋ−１）｜を計算し、｜ｖ＿ｋ−ｖ＿（ｋ−１）｜＜ｓであるか否かの判断を行う（Ｓ３１）。ここで、しきい値ｓは、十分小さい正の整数であり、例えばｓ＝０．００００１である。｜ｖ＿ｋ−ｖ＿（ｋ−１）｜＜ｓでない場合（Ｓ３１，Ｎｏ）、処理Ｓ２２へ戻り、処理Ｓ２２以降を繰り返す。｜ｖ＿ｋ−ｖ＿（ｋ−１）｜＜ｓである場合（Ｓ３１，Ｙｅｓ）、従来の反復計算処理は、ｖ＿ｋを重要度ベクトルｕとし（Ｓ３２）、このフローは終了する。

但し、従来の反復計算処理に用いるＤの各列の要素はリンク関係に基づく確率であり、Ｄの各列の要素の和が１でなければならないという制約がある。この制約を満たさない場合、ｖ＿ｋは発散し、重要度を算出することができなくなる。

次に、本実施の形態に係る反復計算処理について説明する。図１０は、本実施の形態に係る反復計算処理の一例を示すフローチャートである。この図において、図９と同一符号は、図９に示された対象と同一処理を示しており、ここでの説明を省略する。従来の反復計算処理と比較すると、本実施の形態の反復計算処理は、処理Ｓ２３の代わりに処理Ｓ２４，Ｓ２５を実行する。

まず、反復計算部１８は、従来の反復計算処理と同様の処理Ｓ２１，Ｓ２２を実行する。次に、反復計算部１８は、ｅ＿（ｋ−１）＝｜Ｄｖ＿（ｋ−１）｜を計算し（Ｓ２４）、ｖ＿ｋ＝（１／ｅ＿（ｋ−１））Ｄｖ＿（ｋ−１）を計算する（Ｓ２５）。

次に、反復計算部１８は、従来の反復計算処理と同様の処理Ｓ３１を実行する。｜ｖ＿ｋ−ｖ＿（ｋ−１）｜＜ｓでない場合（Ｓ３１，Ｎｏ）、反復計算部１８は、処理Ｓ２２へ戻り、処理Ｓ２２以降を繰り返す。｜ｖ＿ｋ−ｖ＿（ｋ−１）｜＜ｓである場合（Ｓ３１，Ｙｅｓ）、反復計算部１８は、従来の反復計算処理と同様の処理Ｓ３２を実行し、このフローは終了する。

本実施の形態に係る反復計算処理によれば、ｋが大きくなると、ｅ＿ｋはｅに、ｖ＿ｋはｕに収束していく。また、処理Ｓ３１により、ｖ＿ｋの変化が十分小さくなったところで繰り返し計算を終了する。つまり、反復計算部１８は、ｅｕ＝Ｄｕを満たすｕの近似値であるｖ＿ｋを算出する。

本実施の形態に係る反復計算処理は、処理Ｓ２４，Ｓ２５により、Ｄに従来の制約を与えなくてもｖ＿ｋを収束させることができる。

次に、本実施の形態に係る反復計算処理の具体例について説明する。

図１１は、本実施の形態に係る行列決定処理により決定された行列Ｄの一例を示す表である。ここでは、Ｎを６とし、この表のようにＤを決定したとする。このＤは、従来のＤのような制約はなく、各要素が正の実数であれば良い。図１２は、本実施の形態に係る反復計算処理により計算された計算結果の一例を示す表である。この表は、処理Ｓ２２により設定される繰り返し回数ｋ、処理Ｓ２４により算出されるＤｖ＿（ｋ−１）、ｅ＿（ｋ−１）、処理Ｓ２５により算出されるｖ＿ｋ、処理Ｓ３１により算出されるｖ＿ｋ−ｖ＿（ｋ−１）、ｖ＿（ｋ−１）−ｖ＿ｋ、｜ｖ＿ｋ−ｖ＿（ｋ−１）｜の計算結果を示し、それぞれの計算結果を繰り返し回数ｋ毎に示す。この例においては、繰り返し回数ｋ＝１０の時点で、｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿１０をＤに対する重要度ベクトルｕとする。

次に、行列決定処理の概要について説明する。

本実施の形態においては、上述の反復計算処理により、行列Ｄは自由に定義することができるため、検索システムの設計者は、検索対象文書の新しさや参照者からの評価などをＤに反映させることができる。ここでは、検索対象文書の作成日時、評価、参照回数、リンク関係に基づいてＤを決定する例を用いて、行列決定処理の概要を説明する。

Ｐ＿ｍの作成日時が、行列決定処理時のｐ日前とする。ここで、行列決定部１７は、現在の日時と作成日時リストファイルからｐを算出する。検索対象文書の作成日時が計算時のｐ日前のときの重みをｘ＿ｍ（正の実数）とする。ｘ＿ｍは、ｐが小さいほど大きい値になるように設定される。

また、検索対象文書Ｐ＿ｍの評価をｙ＿ｍ（正の実数）と置く。ここで、行列決定部１７は、ｙ＿ｍは評価リストファイルから算出する。ｙ＿ｍは、評価が高いほどの大きい値になるように設定される。

検索対象文書Ｐ＿ｍの参照回数をｚ＿ｍ（正の実数）と置く。ここで、行列決定部１７は、参照回数リストファイルからｚ＿ｍを算出する。ｚ＿ｍは、参照回数が多いほど大きい値になるように設定される。

次に、行列決定部１７は、リンク関係ファイルからＰ＿ｎからＰ＿ｍへのリンクの有無を判断し、リンクの有無によってＤの要素ｄ＿ｍ＿ｎを決定する。また、ここでは、ｄ＿ｍ＿ｎの算出にｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍの積を用いる場合を示す。ｄ＿ｍ＿ｎは、次式で定義される。

ｄ＿ｍ＿ｎ＝ｃｘ＿ｍｙ＿ｍｚ＿ｍ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがないとき）
ｄ＿ｍ＿ｎ
＝ｃｘ＿ｍｙ＿ｍｚ＿ｍ
＋ｘ＿ｍｘ＿ｎｙ＿ｍｙ＿ｎｚ＿ｍｚ＿ｎ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがあるとき）

ここでは、ｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍがｄ＿ｍ＿ｎへ与える影響は、ｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍ、ｘ＿ｎ、ｙ＿ｎ、ｚ＿ｎの積で表したが、和や他の演算によって表しても良い。

このように、システムの設計者は、複数のパラメータ（ここでは、作成日、評価、参照回数、リンク関係）の影響を考慮したＤを自由に決定することができる。

次に、行列決定処理に用いるデータの具体例について説明する。

まず、行列決定部１７は、データの集計を行い、集計したデータを集計データとする。図１３は、本実施の形態に係る集計データの一例を示す表である。ここでは、検索対象文書数Ｎを６とし、データの集計日を２００７年２月７日とする。行列決定部１７は、作成日時リストファイルから作成日を取得し、データの集計日（現在）と作成日の日付の差ｐを算出し、評価リストファイルから所定の基準を満たす有用な評価の数である有用評価数ｑを取得し、参照回数リストファイルから参照回数ｒを取得する。この表は、Ｐ＿ｎ（ｎ＝１，２，…６）のそれぞれについて、作成日、日付の差ｐ、有用評価数ｑ、参照回数ｒを集計した結果を示す。

図１４は、本実施の形態に係るリンク関係の一例を示す表である。ここでは、Ｐ＿ｎ（ｎ＝１，２，…６）の間に、この図に示されたリンク関係が存在するとする。行列決定部１７は、このリンク関係を示したリンク関係ファイルからリンク関係を集計し、リンク関係データとする。図１５は、本実施の形態に係るリンク関係データの一例を示す表である。この表において、“ｆｒｏｍ”の欄に示された文書は、リンク元であり、“ｔｏ”の欄に示された文書は、リンク先を示す。また、“○”が付いた欄に対応するリンク元とリンク先の間にリンクが存在することを示す。また、Ｐ＿ｎから出るリンクの数Ｌ＿ｎがリンク元毎に集計されている。

次に、重要度算出部５の動作の実施例について説明する。以下の実施例においては、上述した集計データ及びリンク関係データの値の例を用いる。

まず、重要度算出部５による動作の第１の実施例として、作成日を重要視した重要度を算出する場合について説明する。

まず、行列決定処理において、行列決定部１７は、集計データから、検索対象文書Ｐ＿ｍについてのパラメータ毎の重みデータとして、作成日の重みを表す重みデータｘ＿ｍ、有用評価数の重みを表す重みデータｙ＿ｍ、参照回数の重みを表す重みデータｚ＿ｍを算出する。ｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍは、それぞれ次式で定義される。

ｘ＿ｍ＝ｅｘｐ（−ｐ／１００）＊１．５
ｙ＿ｍ＝ｌｏｇ（ｑ＋２）＊０．２
ｚ＿ｍ＝ｌｏｇ（ｒ＋２）＊０．０３

この式によりｘ＿ｍが高く設定される。図１６は、本実施の形態に係る第１の実施例において行列決定処理により決定された重みデータを示す表である。次に、行列決定部１７は、リンク関係データからＰ＿ｎからＰ＿ｍへのリンクの有無を判断し、リンクの有無と重みデータに従ってＤの要素ｄ＿ｍ＿ｎを決定する。ここでは、ｄ＿ｍ＿ｎの算出にｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍの和を用いる場合を示す。ｄ＿ｍ＿ｎは、次式で定義される。

ｄ＿ｍ＿ｎ＝ｃ／Ｎ＋ｘ＿ｍ＋ｙ＿ｍ＋ｚ＿ｍ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがないとき）
ｄ＿ｍ＿ｎ
＝ｃ／Ｎ＋ｘ＿ｍ＋ｙ＿ｍ＋ｚ＿ｍ
＋（１−ｃ）*（ｘ＿ｍ＋ｙ＿ｍ＋ｚ＿ｍ）／Ｌ＿ｎ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがあるとき）
ｃ＝０．１５

次に、行列決定部１７は、上述したリンク関係データの値と重みデータの値に対して上式を適用することによりＤを決定する。図１７は、本実施の形態に係る第１の実施例において行列決定処理により決定された行列Ｄを示す表である。この図において、行に付された番号はｍを示し、列に付された番号はｎを示し、ｍとｎで指定される要素はｄ＿ｍ＿ｎの値を示す。

次に、反復計算部１８は、上述した反復計算処理のフローを実行することにより、重要度ベクトルｕを算出する。図１８は、本実施の形態に係る第１の実施例において反復計算処理により計算された計算結果を示す表である。ｋ＝１０で｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿１０をＤに対する重要度ベクトルｕとする。また、反復計算部１８は、得られたｕの要素である重要度ｕ＿ｍ（ｍ＝１，２，…６）の大きさの順位を、Ｐ＿ｍ（ｍ＝１，２，…６）の表示順位（ランク）としても良い。上述した重み付けにより、作成日から集計日までの期間ｐが小さいＰ＿１、Ｐ＿２の表示順位が高くなることが分かる。上述した第１の実施例によれば、作成日、有用評価数、参照回数、リンク関係の影響を考慮しつつ、作成日の影響を強めた重要度及び表示順位を得ることができる。

次に、重要度算出部５による動作の第２の実施例として、有用評価数を重要視した重要度を算出する場合について説明する。

まず、行列決定処理において、重みデータｘ＿ｍ、ｙ＿ｍ、ｚ＿ｍは、それぞれ次式で定義される。

ｘ＿ｍ＝ｅｘｐ（−ｐ／１００）＊０．２
ｙ＿ｍ＝ｌｏｇ（ｑ＋２）＊１．２
ｚ＿ｍ＝ｌｏｇ（ｒ＋２）＊０．０３

この式を、第１の実施例と比較すると、最後の係数の大きさが異なり、ｙ＿ｍが高く設定される。図１９は、本実施の形態に係る第２の実施例において行列決定処理により決定された重みデータを示す表である。次に、行列決定部１７は、この重みデータを用い、第１の実施例と同様にしてＤを決定する。図２０は、本実施の形態に係る第２の実施例において行列決定処理により決定された行列Ｄを示す表である。

次に、反復計算部１８は、上述した反復計算処理のフローを実行することにより、重要度ベクトルｕを算出する。図２１は、本実施の形態に係る第２の実施例において反復計算処理により計算された計算結果を示す表である。ｋ＝１０で｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿１０をＤに対する重要度ベクトルｕとする。上述した重み付けにより、有用評価数ｑが大きいＰ＿４、Ｐ＿６の表示順位が上位になることが分かる。上述した第２の実施例によれば、作成日、有用評価数、参照回数、リンク関係の影響を考慮しつつ、有用評価数の影響を強めた重要度及び表示順位を得ることができる。

次に、重要度算出部５による動作の第３の実施例として、参照回数を重要視した重要度を算出する場合について説明する。

ｘ＿ｍ＝ｅｘｐ（−ｐ／１００）＊０．２
ｙ＿ｍ＝ｌｏｇ（ｑ＋２）＊０．２
ｚ＿ｍ＝ｌｏｇ（ｒ＋２）＊０．２

この式を、第１の実施例と比較すると、最後の係数の大きさが異なり、ｚ＿ｍが高く設定される。図２２は、本実施の形態に係る第３の実施例において行列決定処理により決定された重みデータを示す表である。次に、行列決定部１７は、この重みデータを用い、第１の実施例と同様にしてＤを決定する。図２３は、本実施の形態に係る第３の実施例において行列決定処理により決定された行列Ｄを示す表である。

次に、反復計算部１８は、上述した反復計算処理のフローを実行することにより、重要度ベクトルｕを算出する。図２４は、本実施の形態に係る第３の実施例において反復計算処理により計算された計算結果を示す表である。ｋ＝１１で｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿１１をＤに対する重要度ベクトルｕとする。上述した重み付けにより、参照回数ｒが大きいＰ＿４、Ｐ＿３の表示順位が上位になることが分かる。上述した第３の実施例によれば、作成日、有用評価数、参照回数、リンク関係の影響を考慮しつつ、参照回数の影響を強めた重要度及び表示順位を得ることができる。

次に、重要度算出部５による動作の第４の実施例として、重みデータをランダムに設定して重要度を算出する場合について説明する。

まず、行列決定部１７は、ｄ＿ｍ＿ｎの重みデータをそれぞれランダムな数として設定する。次に、行列決定部１７は、リンク関係ファイルからＰ＿ｎからＰ＿ｍへのリンクの有無を判断し、リンクの有無と重みデータに従ってＤの要素ｄ＿ｍ＿ｎを決定する。ｄ＿ｍ＿ｎは、次式で定義される。

ｄ＿ｍ＿ｎ＝ｃ／Ｎ＋Ｒａｎｄ（）
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがないとき）
ｄ＿ｍ＿ｎ
＝ｃ／Ｎ＋＋（１−ｃ）／Ｌ＿ｎ＋Ｒａｎｄ（）
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがあるとき）
ｃ＝０．１５

ここで、Ｒａｎｄ（）は、０以上１未満のランダムな実数を生成する関数である。図２５は、本実施の形態に係る第４の実施例において行列決定処理により決定されたＲａｎｄ（）の値を示す表である。図２６は、本実施の形態に係る第４の実施例において行列決定処理により決定された行列Ｄを示す表である。

次に、反復計算部１８は、上述した反復計算処理のフローを実行することにより、重要度ベクトルｕを算出する。図２７は、本実施の形態に係る第４の実施例において反復計算処理により計算された計算結果を示す表である。ｋ＝８で｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿８をＤに対する重要度ベクトルｕとする。上述した第４の実施例によれば、リンク関係の影響を考慮しつつ、乱数の影響を与えた重要度及び表示順位を得ることができる。

次に、重要度算出部５による動作の第５の実施例として、重みデータを用いず、リンク関係のみから重要度を算出する場合について説明する。

まず、行列決定部１７は、リンク関係ファイルからＰ＿ｎからＰ＿ｍへのリンクの有無を判断し、リンクの有無に従ってＤの要素ｄ＿ｍ＿ｎを決定する。ｄ＿ｍ＿ｎは、次式で定義される。

ｄ＿ｍ＿ｎ＝ｃ／Ｎ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがないとき）
ｄ＿ｍ＿ｎ
＝ｃ／Ｎ＋＋（１−ｃ）／Ｌ＿ｎ
（ｍ，ｎ＝１，２，…Ｎ）
（Ｐ＿ｎからＰ＿ｍへのリンクがあるとき）
ｃ＝０．１５

図２８は、本実施の形態に係る第５の実施例において行列決定処理により決定された行列Ｄを示す表である。このＤは、リンク関係のみを反映した行列である。

次に、反復計算部１８は、上述した反復計算処理のフローを実行することにより、重要度ベクトルｕを算出する。図２９は、本実施の形態に係る第５の実施例において反復計算処理により計算された計算結果を示す表である。ｋ＝１４で｜ｖ＿ｋ−ｖ＿（ｋ−１）｜がしきい値を下回ったため、反復計算部１８は、繰り返し計算を終了し、ｖ＿１４をＤに対する重要度ベクトルｕとする。上述した第５の実施例によれば、重み付けを用いないことにより、特許文献１の技術と同様、リンク関係のみからも重要度及び表示順位を得ることができる。

本実施の形態によれば、検索システムの設計者は、上述した反復計算処理のアルゴリズムを用いることにより、従来より少ない制約の中で複数のパラメータの重み付けを定義し、行列Ｄを決定することができる。また、パラメータの数に関わらず、１回の行列演算で重要度を算出することができるため、全てのパラメータの情報を失わず、且つ高速に重要度を算出することができる。

また、本実施の形態に係る文書重要度算出装置は、情報処理装置に容易に適用することができ、情報処理装置の性能をより高めることができる。ここで、情報処理装置には、例えばサーバ、ＰＣ（Personal Computer）等が含まれ得る。

更に、文書重要度算出装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、文書重要度算出プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、文書重要度算出装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。

本発明によれば、文書に関するパラメータの影響を考慮した文書の重要度を効率的に算出することができる。

Claims

Ｎ個の文書それぞれの重要度の算出をコンピュータに実行させる文書重要度算出プログラムであって、
全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定ステップと、
縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復ステップと
をコンピュータに実行させる文書重要度算出プログラム。
請求項１に記載の文書重要度算出プログラムにおいて、
前記文書のパラメータは、該文書へのリンク関係、該文書の作成日時、該文書の参照者による該文書の評価、該文書の参照回数の少なくともいずれかを含むことを特徴とする文書重要度算出プログラム。
請求項１または請求項２に記載の文書重要度算出プログラムにおいて、
前記行列決定ステップは、前記Ｎ個の文書のうちｍ番目の文書の前記パラメータ、または前記Ｎ個の文書のうちｍ番目の文書及びｎ番目の文書の前記パラメータに基づいて、Ｄのｍ行ｎ列目の要素を算出することを特徴とする文書重要度算出プログラム。
請求項１乃至請求項３のいずれかに記載の文書重要度算出プログラムにおいて、
前記所定の条件は、前記計算前の縦ベクトルｖと前記計算後の縦ベクトルｖとの差のノルムが所定の閾値を下回る場合であることを特徴とする文書重要度算出プログラム。
請求項１乃至請求項４のいずれかに記載の文書重要度算出プログラムにおいて、
更に行列決定ステップの前に、前記文書毎の前記パラメータを取得するパラメータ取得ステップをコンピュータに実行させることを特徴とする文書重要度算出プログラム。
Ｎ個の文書それぞれの重要度の算出を行う文書重要度算出装置であって、
全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定部と、
縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復部と
を備える文書重要度算出装置。
Ｎ個の文書それぞれについての重要度の算出を行う文書重要度算出方法であって、
全ての要素が正の実数であるＮ次の正方行列Ｄ、正の実数ｅ、前記Ｎ個の文書それぞれの重要度を要素とする縦ベクトルｕがペロン・フロベニウスの定理によりｅｕ＝Ｄｕを満たすことを用いるために、前記文書に関する少なくとも１種類のパラメータに基づいて行列Ｄの要素を決定する行列決定ステップと、
縦ベクトルｕの近似値として求める縦ベクトルｖの初期化を行い、（Ｄｖ）／｜Ｄｖ｜を新たな縦ベクトルｖとする計算を行い、縦ベクトルｖが所定の条件を満たすまで該計算を反復し、縦ベクトルｖの要素をそれぞれ対応する文書の重要度とする反復ステップと
を実行する文書重要度算出方法。