(57)【特許請求の範囲】
【請求項１】
コンピュータを、
複数のデータ要素間に設定された有向の接続関係を示す接続情報を取得する取得手段と、
有向の接続関係を有する複数のデータ要素に、当該複数のデータ要素の各データ要素から接続され、且つ、当該複数のデータ要素の各データ要素に接続する仮想データ要素を追加して、前記取得手段により取得される接続情報を更新する第１更新手段と、
前記複数のデータ要素のうち他のデータ要素への接続数が２以上である第１の値に満たないデータ要素を選択すると共に、当該選択したデータ要素の接続数が前記第１の値に達するまで前記仮想データ要素への接続関係を設定して、前記第１更新手段により更新される接続情報を更新する第２更新手段と、
前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された、前記第２更新手段により更新される接続情報に示される接続関係を双方向化して、前記第２更新手段により更新される接続情報を更新する第３更新手段と、
前記第３更新手段により更新される接続情報に示される各接続関係の重みを算出する算出手段
として機能させるためのプログラム。
【請求項２】
前記コンピュータをさらに、
前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された接続関係を示す隣接行列を、各データ要素からの接続数が予め定められた第２の値に一致するように生成する生成手段として機能させ、
前記算出手段は、前記生成手段により生成された隣接行列を前記第３更新手段により更新した後に、当該更新された隣接行列に基づき、各データ要素からの接続関係の重みが合計で１となるように算出する
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記第１の値は、前記複数のデータ要素のデータ要素数で、前記取得手段により取得される接続情報に示される接続数を除して算出される平均の接続数に基づいて定められる
ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
前記コンピュータをさらに、
前記複数のデータ要素毎の評価値を、前記算出手段により算出される各接続関係の重みに従って更新する処理を、予め定められた終了条件が満足されるまで繰り返し実行する更新手段
として機能させるための請求項１から３のいずれかに記載のプログラム。
【請求項５】
複数のデータ要素間に設定された有向の接続関係を示す接続情報を取得する取得手段と、
有向の接続関係を有する複数のデータ要素に、当該複数のデータ要素の各データ要素から接続され、且つ、当該複数のデータ要素の各データ要素に接続する仮想データ要素を追加して、前記取得手段により取得される接続情報を更新する第１更新手段と、
前記複数のデータ要素のうち他のデータ要素への接続数が２以上である第１の値に満たないデータ要素を選択すると共に、当該選択したデータ要素の接続数が前記第１の値に達するまで前記仮想データ要素への接続関係を設定して、前記追加更新手段により更新される接続情報を更新する第２更新手段と、
前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された、前記第２更新手段により更新される接続情報に示される接続関係を双方向化して、前記第２更新手段により更新される接続情報を更新する第３更新手段と、前記第３更新手段により更新される接続情報に示される各接続関係の重みを算出する算出手段と、を含む
ことを特徴とする情報分析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び情報分析装置に関する。
【背景技術】
【０００２】
論文、特許文献、ウェブページ等の文書間には引用、参照等の有向の接続関係があり、これらの文書をデータ要素（ノード）、接続関係をリンクとしたネットワークの情報を解析し有意な情報を得ることが行われている。例えば、下記の非特許文献１には、多くの引用を集める文書ほど価値が高くなるようにして、各文書の評価値を算出する技術が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Lawrence Page, Sergey Brin,Rajeev Motwani, Terry Winograd,“The PageRank CitationRanking: Bringing Order to the Web”、［online］、1998年1月26日、インターネット〈URL：http://www-db.stanford.edu/~backrub/pageranksub.ps〉
【発明の概要】
【発明が解決しようとする課題】
【０００４】
過去の文献を引用する文書群から構成されるネットワークにおいては、リンクを通じて評価値が過去の文書へと流れてしまうため、リンクを仮想的に双方向化して各文書の評価値を算出することが考えられる。この際、被引用数が少ないが引用数の多い文書を不当に高く評価することがないよう、各文書の引用数を規定値に揃えて計算する技術も提案されている。ただし、こうした場合にも、引用数が少ない文書が評価の高い文書を引用していると、実際の文書の価値よりも高い評価値が算出されてしまうことがあった。
【０００５】
本発明の目的は、有向の接続関係があるデータ要素間の接続関係を双方向化して各データ要素の評価値を算出する場合に、他のデータ要素への接続数が少ないデータ要素が接続先のデータ要素と結びつきが過度に強くなることを抑制するプログラム及び情報分析装置を提供することにある。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、請求項１に記載の発明は、コンピュータを、複数のデータ要素間に設定された有向の接続関係を示す接続情報を取得する取得手段と、有向の接続関係を有する複数のデータ要素に、当該複数のデータ要素の各データ要素から接続され、且つ、当該複数のデータ要素の各データ要素に接続する仮想データ要素を追加して、前記取得手段により取得される接続情報を更新する第１更新手段と、前記複数のデータ要素のうち他のデータ要素への接続数が予め定められた第１の値に満たないデータ要素を選択すると共に、当該選択したデータ要素の接続数が前記第１の値に達するまで前記仮想データ要素への接続関係を設定して、前記第１更新手段により更新される接続情報を更新する第２更新手段と、前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された、前記第２更新手段により更新される接続情報に示される接続関係を双方向化して、前記第２更新手段により更新される接続情報を更新する第３更新手段と、前記第３更新手段により更新される接続情報に示される各接続関係の重みを算出する算出手段として機能させるためのプログラムである。
【０００７】
また、請求項２に記載の発明は、前記コンピュータをさらに、前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された接続関係を示す隣接行列を、各データ要素からの接続数が予め定められた第２の値に一致するように生成する生成手段として機能させ、前記算出手段は、前記生成手段により生成された隣接行列を前記第３更新手段により更新した後に、当該更新された隣接行列に基づき、各データ要素からの接続関係の重みが合計で１となるように算出することを特徴とする請求項１に記載のプログラムである。
【０００８】
また、請求項３に記載の発明は、前記第１の値は、前記複数のデータ要素のデータ要素数で、前記取得手段により取得される接続情報に示される接続数を除して算出される平均の接続数に基づいて定められることを特徴とする請求項１又は２に記載のプログラムである。
【０００９】
また、請求項４に記載の発明は、前記コンピュータをさらに、前記複数のデータ要素毎の評価値を、前記算出手段により算出される各接続関係の重みに従って更新する処理を、予め定められた終了条件が満足されるまで繰り返し実行する更新手段として機能させるための請求項１から３のいずれかに記載のプログラムである。
【００１０】
また、請求項５に記載の発明は、複数のデータ要素間に設定された有向の接続関係を示す接続情報を取得する取得手段と、有向の接続関係を有する複数のデータ要素に、当該複数のデータ要素の各データ要素から接続され、且つ、当該複数のデータ要素の各データ要素に接続する仮想データ要素を追加して、前記取得手段により取得される接続情報を更新する第１更新手段と、前記複数のデータ要素のうち他のデータ要素への接続数が予め定められた第１の値に満たないデータ要素を選択すると共に、当該選択したデータ要素の接続数が前記第１の値に達するまで前記仮想データ要素への接続関係を設定して、前記追加更新手段により更新される接続情報を更新する第２更新手段と、前記複数のデータ要素及び前記仮想データ要素のそれぞれに設定された、前記第２更新手段により更新される接続情報に示される接続関係を双方向化して、前記第２更新手段により更新される接続情報を更新する第３更新手段と、前記第３更新手段により更新される接続情報に示される各接続関係の重みを算出する算出手段と、を含むことを特徴とする情報分析装置である。
【発明の効果】
【００１１】
請求項１及び５に記載の発明によれば、有向の接続関係があるデータ要素間の接続関係を双方向化して各データ要素の評価値を算出する場合に、他のデータ要素への接続数が少ないデータ要素が接続先のデータ要素と結びつきが過度に強くなることを抑制できる。
【００１２】
請求項２に記載の発明によれば、データ要素間の接続関係の重みをデータ要素からデータ要素への遷移確率で表す場合に、他のデータ要素への接続数が少ないデータ要素が接続先のデータ要素と結びつきが過度に強くなることを抑制できる。
【００１３】
請求項３に記載の発明によれば、データ要素全体における平均の接続数に満たないデータ要素が接続先のデータ要素と結びつきが過度に強くなることを抑制できる。
【００１４】
請求項４に記載の発明によれば、他のデータ要素への接続数が少ないデータ要素が評価の高いデータ要素に接続していた場合、過度に高い評価値を得ることを抑制できる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係る情報分析装置の機能ブロック図である。
【図２】ネットワークの一例を示す図である。
【図３】ノード群に仮想ノードを追加して拡張したネットワークの一例を示す図である。
【図４】双方向化された隣接行列の表すネットワークの一例を示す図である。
【図５】ノード間のリンクを単純に双方向化した場合の例（Ａ）と、本実施形態で用いた手法で双方向化した場合の例（Ｂ）を示す図である。
【図６】ノードの評価値の算出処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための実施の形態（以下、実施形態という）を、図面に従って説明する。
【００１７】
図１には、本実施形態に係る情報分析装置１０の機能ブロック図を示した。図１に示されるように、情報分析装置１０は、ノードデータ取得部１００、仮想ノード追加設定部１０２、隣接行列生成部１０４、正則化処理部１０６、双方向化処理部１０８、遷移確率行列生成部１１０、評価値更新部１１２、及び処理結果保持部１１４を含む。上記の各部の機能は、ＣＰＵ等の制御手段、メモリ等の記憶手段、外部デバイスとデータを送受信する入出力手段等を備えたコンピュータが、コンピュータ読み取り可能な情報記憶媒体に格納されたプログラムを読み込み実行することで実現されるものとしてよい。なお、プログラムは情報記憶媒体によって情報分析装置１０として機能するコンピュータに供給されることとしてもよいし、インターネット等のデータ通信手段を介してコンピュータに供給されることとしてもよい。
【００１８】
ノードデータ取得部１００は、複数のノード（データ要素）の各データを取得すると共に、各ノードのリンク先（接続先）を示す接続情報を取得するものである。なお、本実施形態におけるノード（データ要素）とは、グラフ理論におけるグラフを構成する節点（頂点）に相当し、リンク（接続関係）とは節点を結ぶ辺（エッジ）に相当するものであって、本実施形態では電子文書等の１つのデータファイルを１つのノードに対応させた例について説明する。例えば、情報分析装置１０が文書間の引用ネットワークを解析する場合には、文書をノード、文書間の引用関係をリンクとしてよい。その場合に、ノードデータ取得部１００は、文書を格納したデータベースにアクセスして文書を取得することとしてよく、取得した文書が引用する文書（引用文書）の情報は、取得した文書の内容から取得してもよいし、文書を格納しているデータベースに問い合わせて取得することとしてもよい。例えば、文書が特許文献である場合には、特許文献における先行技術文献の欄から引用文書を特定してもよいし、特許文献の識別情報に基づいて審査情報を取得し、当該取得した審査情報に基づいて引用文書を特定することとしてもよい。また、文書が科学技術論文である場合には、科学技術論文の引用欄から引用文書を抽出することとしてよい。
【００１９】
図２には、ノードデータ取得部１００により取得されるノードデータに基づき、各ノードをその接続関係に従って接続したネットワークの一例を示す図である。図２において、１つのノードは１つの文書に対応しており、ノードｉ（ｎｉ）からノードｊ（ｎｊ）へ接続する矢印は、ノードｉがノードｊを引用する関係を表している。
【００２０】
仮想ノード追加設定部１０２は、ノードデータ取得部１００により取得されたノード群に仮想ノードを追加すると共に、当該追加した仮想ノードとノード群の間にリンクを設定するものである。仮想ノードは、ノード群の全てのノードに引用され、そしてノード群の全てのノードを引用されるノードである。ここで、仮想ノード追加設定部１０２は、ノード群に含まれるノードのうち、他のノードを引用する引用数が規定値に満たないノードについては、引用数が規定値に達するまで、仮想ノードを引用するようにノードの接続情報を設定する。なお、引用数の規定値は、所与の定数としてもよいし、ノード群における平均の引用数としてもよいし、ノード群における引用数の最大値であってもよい。ノード群における平均の引用数が整数でない場合には、平均の引用数を四捨五入、切り捨て、又は切り上げにより整数とすることとしてよい。なお、仮想ノード追加設定部１０２は、ノードデータ取得部１００により取得されたノード群の接続関係を示す隣接行列に、仮想ノードの行及び列を追加し、仮想ノードと、ノード群の各ノードとの間に接続関係を設定することで隣接行列を更新し、さらに、ノード群に含まれるノードのうち他のノードへの接続数が予め定められた第１の値に満たないノードを選択すると共に、当該選択したノードの接続数が第１の値に達するまで仮想データ要素への接続関係を設定して、上記更新された隣接行列をさらに更新することとしてよい。
【００２１】
図３には、ノードデータ取得部１００により取得されたノード群に仮想ノードを追加して拡張したネットワークの一例を示す。図３に示されるように、仮想ノードはノード群の全てのノードと少なくとも１つの双方向のリンクを有している。このうち引用数が少ないノードからは、仮想ノードへの複数本のリンクが設けられる。例えば、引用数の規定値が３であり、ノードｉの引用数が２である場合には、ノードｉから仮想ノードへ１本の引用リンクが設定されることとなり、ノードｊの引用数が１である場合には、ノードｊから仮想ノードへ２本の引用リンクが設定される。
【００２２】
隣接行列生成部１０４は、ノードデータ取得部１００により取得されたノード群に、仮想ノード追加設定部１０２により仮想ノードが追加されると共に仮想ノードへのリンクが設定されて拡張されたネットワークを表す隣接行列を生成するものである。
【００２３】
具体的には、隣接行列生成部１０４は、ノードj（ｎｊ）がノードi（ｎｉ）を引用している時に、隣接行列Ａの成分Ａｉｊを以下の式（１）で表す。
Ａｉｊ＝１      （１）
ここで、ｉ及びｊは１〜Ｎ（Ｎは仮想ノードを含めたノード数）の自然数である。ただし、ノードjがノードiをＬ回引用している場合には、Ａｉｊ＝Ｌとなる。また、ノードjがノードiを引用していないときにはＡｉｊは以下の式（２）で表す。
Ａｉｊ＝０      （２）
なお、各ノードは自分自身を引用することはないため隣接行列Ａの対角成分は以下の式（３）で表される。
Ａｉｉ＝０      （３）
本実施形態では、以上の処理により隣接行列Ａを生成する。
【００２４】
ここで、ノードｊのアウトリンク数（引用数）ｋｏｕｔ（ｊ）は以下の式（４）で、ノードｊのインリンク数（被引用数）ｋｉｎ（ｊ）は以下の式（５）で表される。
【数１】
0005545063.tif 000002
【数２】
0005545063.tif 000003
【００２５】
正則化処理部１０６は、各ノードのアウトリンク数をｍ（ｍは自然数）本に揃える処理（正規化）を行うものである。具体的には、正規化処理部は、全てのノードには少なくとも規定値以上の引用数があるため、ｉ≠ｊのときｋｏｕｔ（ｊ）≠０であり、隣接行列Ａを以下の式（６）により変換して、正規化された隣接行列Ａ（チルダ）を生成する。
【数３】
0005545063.tif 000004
また、ｉ＝ｊのときには以下の式（７）となる。
【数４】
0005545063.tif 000005
【００２６】
双方向化処理部１０８は、正規化された隣接行列Ａ（チルダ）におけるリンクを双方向化して、隣接行列を更新するものである。双方向化処理部１０８は、ｉ≠ｊのとき、正規化された隣接行列Ａ（チルダ）を用いて、双方向化された隣接行列Ａ（オーバーライン）を以下の式（８）により生成する。
【数５】
0005545063.tif 000006
また、ｉ＝ｊのときには、双方向化された隣接行列Ａ（オーバーライン）は以下の式（９）により表される。
【数６】
0005545063.tif 000007
なお、双方向化された隣接行列Ａ（オーバーライン）は、式（１０）に示されるように対称行列である。
【数７】
0005545063.tif 000008
【００２７】
ここで、双方向化された隣接行列Ａ（オーバーライン）に基づくノードｊのアウトリンク数ｋ（ｊ）は、以下の式（１１）により得られる。
【数８】
0005545063.tif 000009
ただし、κ（ｊ）は以下の式（１２）により表される。
【数９】
0005545063.tif 000010
【００２８】
図４には、双方向化された隣接行列の表すネットワークの一例を示した。図４において、ノードｊからの実線のリンクが元々ノード間に設定されているリンクを示し、点線のリンクが双方向化処理により新たに設定されたリンクを示している。なお、ノードｊのアウトリンク数ｋ（ｊ）の第１項目は、実線のリンクに基づく項であり、第２項目は、双方向化処理により追加された点線のリンクに基づく項である。
【００２９】
遷移確率行列生成部１１０は、双方向化された隣接行列を、各ノードにおいてアウトリンクの重みの総計が１となるように（すなわち、リンクの重みが確率を表すように）規格化するものである。具体的には、遷移確率行列生成部１１０は、双方向化された隣接行列に基づき、遷移確率行列Ｔｉｊを以下の式（１３）により生成する。
【数１０】
0005545063.tif 000011
なお、一般にＴｉｊは対称行列ではない。式（１３）を式（８）〜（１２）に基づいて展開すると、式（１４）のようになる。
【数１１】
0005545063.tif 000012
式（１４）からも明らかなようにＴｉｊはｍに依存しない。
【００３０】
図５には、ノード間のリンクを単純に双方向化した場合の例（Ａ）と、本実施形態で用いた手法で双方向化した場合の例（Ｂ）を示した。図５では、ノードｉが、多くの引用を集める価値の高いノードｊのみを引用している場合を想定している。ここで、ノードｊからのノードｉに与える影響、すなわち遷移確率行列Ｔｉｊの値を求める。ノードｉはノードｊを引用し、逆の引用はないから、式（１４）に基づき、Ｔｉｊは以下の式（１５）により表される。
【数１２】
0005545063.tif 000013
式（１４）から、ノードｊのノードｉに対する影響は、ノードｉのアウトリンク数ｋ（ｉ）に反比例する。ここで、図５（Ａ）の場合には、ｋ（ｉ）＝１であるのに対して、図５（Ｂ）の場合には、ｋ（ｉ）＝Ｌとなる（Ｌは引用数の規定値（最低本数）でＬ＞１である）から、（Ａ）の場合に比べて（Ｂ）の場合には、ノードｊからノードｉへの影響は１／Ｌに低減される。なお、（Ｂ）の場合には、（Ｌ−１）本のリンクにより仮想ノードからノードｉへの影響が及ぼされるが、仮想ノードは、全てのノードを引用し、また全てのノードから引用されるノードであるため、全ノードにおける平均的な評価値を有する。そのため、（Ａ）では（Ｂ）よりもノードｊからの影響をＬ倍で受けることに比べると、ノードｉが引用している全ノードから受ける評価値の総計は減少することとなり、ノードｉが、被引用数が少ないにもかかわらず、引用先のノードの価値が高いことにより大きな評価を受けることが回避される。
【００３１】
評価値更新部１１２は、遷移確率行列生成部１１０により生成された遷移確率行列に基づいて、各ノードの評価値を予め定められた終了条件が満足されるまで繰り返し更新するものである。評価値更新部１１２により更新された各ノードの評価値が大きい順に各ノードの順位（ランク）が決まる。以下、評価値更新部１１２による処理の一例を以下説明する。
【００３２】
評価値更新部１１２は、ノードｉの評価値ｐｉを以下の式（１６）により算出する。
【数１３】
0005545063.tif 000014
ここで、ｄは０≦ｄ≦１を満たす実数定数であり、評価値更新部１１２は、全てのノードｉにおいてｐｉの値の変化量が予め定められた条件（例えば、ｐｉの変化量が閾値以下となる）を満たすまで、繰り返し式（１５）による評価値の更新を繰り返すこととしてよい。なお、各ノードが有する評価値の初期値は予め付与することとしてよい。
【００３３】
処理結果保持部１１４は、評価値更新部１１２により更新された各ノードの評価値（ランク値）を保持するものである。処理結果保持部１１４に保持された各ノードの評価値は、各種の処理に供されることとしてよい。例えば、情報分析装置１０は、処理対象の複数のノードの中から、指定された検索条件に合致するノードを検索し、当該検索されたノードを、処理結果保持部１１４に保持される各ノードの評価値に基づく順位で表示させる表示データを生成し出力することとしてよい。
【００３４】
次に、図６に示されるフローチャートを参照して、情報分析装置１０により行われるノードの評価値の算出処理の一例について説明する。
【００３５】
図６に示されるように、情報分析装置１０は、複数のノードを含むノード群と、各ノード間に定められた有向リンク（引用関係）の情報を含むノードデータを取得する（Ｓ１００１）。情報分析装置１０は、取得したノード群に仮想ノードを追加する（Ｓ１００２）。ここで、情報分析装置１０は、ノード群に含まれるノードのうち未選択のノードを１つ選択し（Ｓ１００３）、当該選択したノードのアウトリンク数（引用数）が規定値に達していない場合には（Ｓ１００４：Ｎ）、アウトリンク数が規定値に達するまで仮想ノードへのリンクを設定する（Ｓ１００５）。上記選択したノードのアウトリンク数が規定値以上である場合（Ｓ１００４：Ｙ）、又はＳ１００５の処理を終えると、情報分析装置１０はノード群に未選択のノードがあるか否かを判断し（Ｓ１００６）、未選択のノードがある場合には（Ｓ１００６：Ｙ）、Ｓ１００３に戻ってそれ以降の処理を繰り返し、未選択のノードがない場合には（Ｓ１００６：Ｎ）、Ｓ１００７の処理に進む。
【００３６】
情報分析装置１０は、以上の処理により仮想ノードを含むノード群の間に設定されたリンクにより構成されるネットワークの情報を示す隣接行列を生成する（Ｓ１００７）。そして、情報分析装置１０は、上記生成した隣接行列に対して、各ノードからのアウトリンク数を一定数に揃える正則化処理を行うと共に（Ｓ１００８）、さらに正則化された隣接行列に対して、各有向リンクを双方向化する双方向化処理を行う（Ｓ１００９）。情報分析装置１０は、双方向化された隣接行列に基づいて、各ノードからのアウトリンクの重みを、当該アウトリンクを介して他のノードにデータ値が遷移する遷移確率を示すように規格化して遷移確率行列を算出する（Ｓ１０１０）。
【００３７】
情報分析装置１０は、上記算出した遷移確率行列に従って各ノードの評価値（ランク値）を順次更新する処理を、各ノードの評価値の変化量が所与の閾値を下回るまで実行し（Ｓ１０１１）、各ノードの評価値を得て処理を終了する。
【００３８】
本実施形態に係る情報分析装置１０では、ノード間の引用関係を双方向化し、各ノードの引用数を計算上揃えた上で各ノードの評価値を算出する際に、全てのノードと接続、被接続の関係にある仮想ノードを引用数が規定値に達するまで引用するようにしたことで、引用数の少ないノードが引用先のノードと結びつきが強くなることを回避している。こうして、被引用数が少ないにもかかわらず、引用先のノードの価値が高いことにより大きな評価を受けるノードが存在しないようにした。
【００３９】
本実施形態では、文書をノード、引用関係をリンクとした例を説明したが、本発明は上記の例に限られず、有向リンクにより接続されるノード全般に同様に適用されるものであることはもちろんである。
【符号の説明】
【００４０】
１０  情報分析装置、１００  ノードデータ取得部、１０２  仮想ノード追加設定部、１０４  隣接行列生成部、１０６  正則化処理部、１０８  双方向化処理部、１１０  遷移確率行列生成部、１１２  評価値更新部、１１４  処理結果保持部。
【図１】
0005545063.tif 000015
【図２】
0005545063.tif 000016
【図３】
0005545063.tif 000017
【図４】
0005545063.tif 000018
【図５】
0005545063.tif 000019
【図６】
0005545063.tif 000020