(57)【特許請求の範囲】
【請求項１】
コンピュータを、
学習用データを取得する学習用データ取得手段、
複数のノードとこれら複数のノード同士の間を接続する複数のリンクとからなるネットワークについて、当該ネットワーク上のノードからノードへのリンクを介した遷移のマルコフ連鎖を、それぞれがバイアス付きマルコフ連鎖で表される複数のクラスタに分けるクラスタ分けを、前記学習用データを用いて機械学習し、学習結果の各クラスタを表す各バイアス付きマルコフ連鎖の定常状態を計算することにより、それら学習結果の各クラスタに対する前記ネットワーク上の各ノードの帰属度を表す帰属度情報を求めて記憶する記憶手段、
ユーザから検索条件を受け取る検索条件受付手段、
前記ユーザから受け取った前記検索条件に合致するノード群と、前記帰属度情報と、に基づき、前記検索条件に適合するクラスタを抽出するクラスタ抽出手段、
前記ネットワークの中から、前記クラスタ抽出手段により抽出されたクラスタに属するノード群からなる部分ネットワークを切り出す部分ネットワーク切り出し手段、
切り出された前記部分ネットワークを対象として、前記検索条件に合致するノード群を種ベクトルとするパーソナライズド・ページランクアルゴリズムの演算を実行することにより、前記部分ネットワーク上の各ノードの重要度を計算し、計算した重要度に基づいて前記検索条件に対する前記ユーザへの検索結果を生成する重要度計算手段、
として機能させるためのプログラム。
【請求項２】
前記学習用データは、ユーザごとに、過去に前記検索条件受付手段が当該ユーザから受け付けた個々の検索条件に対する検索結果のデータであり、
前記記憶手段は、ユーザごとに、当該ユーザについての過去の検索結果のデータを用いてユーザごとのクラスタ分けを機械学習し、学習結果であるユーザごとのクラスタ分けに従って前記帰属度情報をユーザごとに求めて記憶し、
前記クラスタ抽出手段は、前記検索条件の発行元のユーザに対応する前記帰属度情報を用いて、当該検索条件に適合するクラスタを抽出する、
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
学習用データを取得する学習用データ取得手段と、
複数のノードとこれら複数のノード同士の間を接続する複数のリンクとからなるネットワークについて、当該ネットワーク上のノードからノードへのリンクを介した遷移のマルコフ連鎖を、それぞれがバイアス付きマルコフ連鎖で表される複数のクラスタに分けるクラスタ分けを、前記学習用データを用いて機械学習し、学習結果の各クラスタを表す各バイアス付きマルコフ連鎖の定常状態を計算することにより、それら学習結果の各クラスタに対する前記ネットワーク上の各ノードの帰属度を表す帰属度情報を求めて記憶する記憶手段と、
ユーザから検索条件を受け取る検索条件受付手段と、
前記ユーザから受け取った前記検索条件に合致するノード群と、前記帰属度情報と、に基づき、前記検索条件に適合するクラスタを抽出するクラスタ抽出手段と、
前記ネットワークの中から、前記クラスタ抽出手段により抽出されたクラスタに属するノード群からなる部分ネットワークを切り出す部分ネットワーク切り出し手段と、
切り出された前記部分ネットワークを対象として、前記検索条件に合致するノード群を種ベクトルとするパーソナライズド・ページランクアルゴリズムの演算を実行することにより、前記部分ネットワーク上の各ノードの重要度を計算し、計算した重要度に基づいて前記検索条件に対する前記ユーザへの検索結果を生成する重要度計算手段と、
を備える検索装置。
【請求項４】
コンピュータを、
ネットワークでリンクを辿ってノードからノードへ遷移していくエージェントが同一時点で当該ネットワークの各ノードに存在する確率をそれぞれ成分とする活性ベクトルについて、当該活性ベクトルの確率的時間発展を表すクラスタ毎の関係式を用いて、ある時刻における前記活性ベクトルを直前の時刻における前記活性ベクトルから計算する計算手段であって、クラスタ毎の前記関係式は、前記ある時刻の前記活性ベクトルが、前記ネットワークのリンク構造に応じたマルコフ連鎖の遷移確率行列に従った前記直前の時刻の前記活性ベクトルの遷移結果、を中心とするあらかじめ定められた確率分布に従うとし、学習用データが観測結果として得られた場合の活性ベクトルの尤度を最大化するように定められていることを特徴とする計算手段、および、
クラスタ毎に、そのクラスタについての前記関係式を、時刻を順次進めながら繰り返し前記計算手段に計算させることで、前記関係式に含まれるパラメータを順次更新し、前記計算手段による前記関係式の計算が終了条件を満たしたときの前記パラメータに基づき、当該クラスタを特定する特定手段、
として機能させるためのプログラム。
【請求項５】
ネットワークでリンクを辿ってノードからノードへ遷移していくエージェントが同一時点で当該ネットワークの各ノードに存在する確率をそれぞれ成分とする活性ベクトルについて、当該活性ベクトルの確率的時間発展を表すクラスタ毎の関係式を用いて、ある時刻における前記活性ベクトルを直前の時刻における前記活性ベクトルから計算する計算手段であって、クラスタ毎の前記関係式は、前記ある時刻の前記活性ベクトルが、前記ネットワークのリンク構造に応じたマルコフ連鎖の遷移確率行列に従った前記直前の時刻の前記活性ベクトルの遷移結果、を中心とするあらかじめ定められた確率分布に従うとし、学習用データが観測結果として得られた場合の活性ベクトルの尤度を最大化するように定められていることを特徴とする計算手段と、
クラスタ毎に、そのクラスタについての前記関係式を、時刻を順次進めながら繰り返し前記計算手段に計算させることで、前記関係式に含まれるパラメータを順次更新し、前記計算手段による前記関係式の計算が終了条件を満たしたときの前記パラメータに基づき、当該クラスタを特定する特定手段と、
を備えるクラスタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び検索装置に関する。
【背景技術】
【０００２】
非特許文献１には、ウェブページ及びハイパーリンクから構成されるグラフの構造から、個々のウェブページ（ノード）の重要度を示す「ページランク」を適切に定めるページランクアルゴリズムが示されている。概略的にいえば、ページランクアルゴリズムは、マルコフ連鎖の定常状態において各ノードに振り分けられた「確率」に応じて、各ノードのページランク値を定める。このアルゴリズムは、一人のエージェントがリンクを辿りながらノードからノードへと、グラフ上をランダムに歩き回る過程（マルコフランダムウォーク）とのアナロジーに基づいている。ノードにエージェントが存在する確率が高いほど、そのノードのページランク値が高くなる。
【０００３】
また、非特許文献１には、パーソナライズド・ページランク（以下、「ＰＰＲ」と略す）アルゴリズムについても説明されている。通常のページランクアルゴリズムは特定の視点に依存しないのに対し、ＰＰＲアルゴリズムは、個々のユーザの興味や関心、過去の検索行動を加味したユーザ固有のページランクを計算する。すなわち、ＰＰＲでは、過去の検索履歴等から事前に分かっているユーザが関心を持っているウェブページ（ノード）群（例えばユーザからの検索クエリに合致するページ群）を種ノードセットとし、ネットワーク上の各ノードからそのセットに含まれる種ノードに対し（リンクが無くても）エージェントが一定の割合でジャンプするとして、ページランクを計算する。これにより、種ノードセットに近いノード群のページランクが通常のページランクアルゴリズムを用いる場合よりも高くなる。ある時点でのユーザの関心（これは検索履歴等で表現し得る）に即したＰＰＲを計算するには、通常のページランクの計算と同程度の時間を要する。ユーザから検索クエリ（「ユーザクエリ」と呼ぶ）が与えられるたびに、そのユーザの最新の関心に沿ったＰＰＲを計算するのは所要時間の観点で現実的ではない。
【０００４】
非特許文献２には、改良したページランクアルゴリズムを用いてウェブ検索を高速に行う手法が開示されている。この手法では、個々のユーザクエリに応じたマルコフ連鎖計算を行うのではなく、事前に（すなわち、オフラインで）複数の種ノードセットのそれぞれについての重要度を、ＰＰＲアルゴリズムにより求めておく。個々の種ノードセットは、それぞれ、何らかの「トピック」すなわち「分野」を表わす。そして、ユーザクエリを受け取るたびに（すなわち、オンラインでは）、そのユーザクエリの各分野に対する帰属度をそれぞれ求め、それら各分野についての帰属度を係数として、事前に求めておいた分野依存の重要度の線形和を計算する。
【０００５】
この手法は、本来のＰＰＲアルゴリズムならばユーザクエリごとにマルコフ連鎖の計算をすることでそのクエリに詳細に依存したノード重要度・ランキングを求めるところを、計算時間上それが許されないので、その代用物として個々の分野のそれぞれについて求めたノード重要度・ランキングを適当に重ね合わせたものを求めているに過ぎない。
【０００６】
また、ネットワークのクラスタリングまたはネットワークからのコミュニティの抽出についての従来技術として、非特許文献３〜７に示されるものがある。
【０００７】
非特許文献３に開示される方式では、各リンクについて"betweenness"（媒介性）を計算し、betweennessの高いリンクはコミュニティ間を結ぶリンクとみなし、これらを順次切断することにより、ネットワークをクラスタ（コミュニティ）に分割する。この方式により得られるクラスタは、相互にオーバーラップ（すなわち異なるクラスタが同じノードを共有すること）しない。
【０００８】
非特許文献４及び５に開示される方式では、各リンクの個々のコミュニティへの帰属度等をパラメータとして、ネットワークの確率的生成モデルを構築する。これに対象とするネットワークのリンク構造（データ）を代入して尤度を定め、尤度を最大化するパラメータを求めることにより、ネットワークを構成するクラスタ（コミュニティ）を求める。この方式では、クラスタ同士のオーバーラップを許してクラスタリングあるいはコミュニティ抽出を行うことができる。
【０００９】
非特許文献６に開示される方式では、ネットワーク上のマルコフランダム過程（マルコフ連鎖）を考え、これに凝集過程を加味する。通常のマルコフランダム過程（expansion）と凝集（inflation）とを交互に繰り返すことにより、やがて遷移確率行列は連結部分に分割される。各連結部分が各クラスタに対応する。この方式により抽出されるクラスタは、オーバーラップが一切ない。
【００１０】
特許文献７に開示される方式では、各ノードを「芯」とするマルコフランダム過程（パーソナライズドページランクアルゴリズム）から得られた定常状態確率分布ベクトルをK-mean法でクラスタリングする。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Page, L. et al. Stanford Digital Library Technologies Project (1998). [online]、[平成23年1月10日検索]、インターネット〈http://www-db.stanford.edu/~backrub/pageranksub.ps〉
【非特許文献２】Haveliwara, T. "Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search," IEEE Transactions on Knowledge and Data Engineering, 15, pp. 784-796, 2003年7月
【非特許文献３】Newman, M. E. J. & Girvan, M. “Finding and evaluating community structure in networks.” Physical Review E 69, 026113 (2004).
【非特許文献４】Airoldi, E. M., Blei, D. M. & Xing, E. P. “Mixed membership stochastic Blockmodels.” Journal of Machine Learning Research 9, 1981-2014 (2008).
【非特許文献５】Ball, B. Karrer, B. & Newman, M. E. J. “Effective and principled method for detecting communities in networks.” Physical Review E 84, 036103 (2011).
【非特許文献６】Van Dongen, S. “Graph clustering by flow simulation.” PhD thesis, University of Utrecht (2000)
【非特許文献７】Chung, F. & Tsiatas, A. “Finding and visualizing graph clusters using PageRan optimization.” Proceedings of WAW 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の１つの側面では、ユーザからのクエリに即したパーソナライズド・ページランクアルゴリズムに基づく検索を、本発明を用いない場合よりも高速に実行できるようにすることを目的とする。
【００１３】
本発明の別の側面では、リンクに向きを有しないネットワークについて、あるいは、リンクに向き又は重みを有するネットワークについて、クラスタ同士の重なりを許容したクラスタリング（クラスタ分け）を可能とすることを目的とする。
【課題を解決するための手段】
【００１４】
請求項１に係る発明は、コンピュータを、学習用データを取得する学習用データ取得手段、複数のノードとこれら複数のノード同士の間を接続する複数のリンクとからなるネットワークについて、当該ネットワーク上のノードからノードへのリンクを介した遷移のマルコフ連鎖を、それぞれがバイアス付きマルコフ連鎖で表される複数のクラスタに分けるクラスタ分けを、前記学習用データを用いて機械学習し、学習結果の各クラスタを表す各バイアス付きマルコフ連鎖の定常状態を計算することにより、それら学習結果の各クラスタに対する前記ネットワーク上の各ノードの帰属度を表す帰属度情報を求めて記憶する記憶手段、ユーザから検索条件を受け取る検索条件受付手段、前記ユーザから受け取った前記検索条件に合致するノード群と、前記帰属度情報と、に基づき、前記検索条件に適合するクラスタを抽出するクラスタ抽出手段、前記ネットワークの中から、前記クラスタ抽出手段により抽出されたクラスタに属するノード群からなる部分ネットワークを切り出す部分ネットワーク切り出し手段、切り出された前記部分ネットワークを対象として、前記検索条件に合致するノード群を種ベクトルとするパーソナライズド・ページランクアルゴリズムの演算を実行することにより、前記部分ネットワーク上の各ノードの重要度を計算し、計算した重要度に基づいて前記検索条件に対する前記ユーザへの検索結果を生成する重要度計算手段、として機能させるためのプログラムである。
【００１５】
請求項２に係る発明は、前記学習用データは、ユーザごとに、過去に前記検索条件受付手段が当該ユーザから受け付けた個々の検索条件に対する検索結果のデータであり、前記記憶手段は、ユーザごとに、当該ユーザについての過去の検索結果のデータを用いてユーザごとのクラスタ分けを機械学習し、学習結果であるユーザごとのクラスタ分けに従って前記帰属度情報をユーザごとに求めて記憶し、前記クラスタ抽出手段は、前記検索条件の発行元のユーザに対応する前記帰属度情報を用いて、当該検索条件に適合するクラスタを抽出する、ことを特徴とする請求項１に記載のプログラムである。
【００１６】
請求項３に係る発明は、学習用データを取得する学習用データ取得手段と、複数のノードとこれら複数のノード同士の間を接続する複数のリンクとからなるネットワークについて、当該ネットワーク上のノードからノードへのリンクを介した遷移のマルコフ連鎖を、それぞれがバイアス付きマルコフ連鎖で表される複数のクラスタに分けるクラスタ分けを、前記学習用データを用いて機械学習し、学習結果の各クラスタを表す各バイアス付きマルコフ連鎖の定常状態を計算することにより、それら学習結果の各クラスタに対する前記ネットワーク上の各ノードの帰属度を表す帰属度情報を求めて記憶する記憶手段と、ユーザから検索条件を受け取る検索条件受付手段と、前記ユーザから受け取った前記検索条件に合致するノード群と、前記帰属度情報と、に基づき、前記検索条件に適合するクラスタを抽出するクラスタ抽出手段と、前記ネットワークの中から、前記クラスタ抽出手段により抽出されたクラスタに属するノード群からなる部分ネットワークを切り出す部分ネットワーク切り出し手段と、切り出された前記部分ネットワークを対象として、前記検索条件に合致するノード群を種ベクトルとするパーソナライズド・ページランクアルゴリズムの演算を実行することにより、前記部分ネットワーク上の各ノードの重要度を計算し、計算した重要度に基づいて前記検索条件に対する前記ユーザへの検索結果を生成する重要度計算手段と、を備える検索装置である。
【００１７】
請求項４に係る発明は、コンピュータを、ネットワークでリンクを辿ってノードからノードへ遷移していくエージェントが同一時点で当該ネットワークの各ノードに存在する確率をそれぞれ成分とする活性ベクトルについて、当該活性ベクトルの確率的時間発展を表すクラスタ毎の関係式を用いて、ある時刻における前記活性ベクトルを直前の時刻における前記活性ベクトルから計算する計算手段であって、クラスタ毎の前記関係式は、前記ある時刻の前記活性ベクトルが、前記ネットワークのリンク構造に応じたマルコフ連鎖の遷移確率行列に従った前記直前の時刻の前記活性ベクトルの遷移結果、を中心とするあらかじめ定められた確率分布に従うとし、学習用データが観測結果として得られた場合の活性ベクトルの尤度を最大化するように定められていることを特徴とする計算手段、および、クラスタ毎に、そのクラスタについての前記関係式を、時刻を順次進めながら繰り返し前記計算手段に計算させることで、前記関係式に含まれるパラメータを順次更新し、前記計算手段による前記関係式の計算が終了条件を満たしたときの前記パラメータに基づき、当該クラスタを特定する特定手段、として機能させるためのプログラムである。
【００１８】
請求項５に係る発明は、ネットワークでリンクを辿ってノードからノードへ遷移していくエージェントが同一時点で当該ネットワークの各ノードに存在する確率をそれぞれ成分とする活性ベクトルについて、当該活性ベクトルの確率的時間発展を表すクラスタ毎の関係式を用いて、ある時刻における前記活性ベクトルを直前の時刻における前記活性ベクトルから計算する計算手段であって、クラスタ毎の前記関係式は、前記ある時刻の前記活性ベクトルが、前記ネットワークのリンク構造に応じたマルコフ連鎖の遷移確率行列に従った前記直前の時刻の前記活性ベクトルの遷移結果、を中心とするあらかじめ定められた確率分布に従うとし、学習用データが観測結果として得られた場合の活性ベクトルの尤度を最大化するように定められていることを特徴とする計算手段と、クラスタ毎に、そのクラスタについての前記関係式を、時刻を順次進めながら繰り返し前記計算手段に計算させることで、前記関係式に含まれるパラメータを順次更新し、前記計算手段による前記関係式の計算が終了条件を満たしたときの前記パラメータに基づき、当該クラスタを特定する特定手段と、を備えるクラスタリング装置である。
【発明の効果】
【００１９】
請求項１又は３に係る発明によれば、ユーザからのクエリに即したパーソナライズド・ページランクアルゴリズムに基づく検索を、本発明を用いない場合よりも高速に実行できる。
【００２０】
請求項２に係る発明によれば、ユーザの過去の検索の傾向に即した検索結果を求めることができる。
【００２１】
請求項４又は５に係る発明によれば、リンクに向き又は重みを有するネットワークについて、クラスタ同士の重なりを許容したクラスタリング（クラスタ分け）が可能となる。
【図面の簡単な説明】
【００２２】
【図１】マルコフ連鎖のクラスタリング処理の手順の一例を示すフローチャートである。
【図２】クラスタリング結果を用いた検索処理の手順の一例を示すフローチャートである。
【図３】実施形態の検索システムの構成を示す図である。
【図４】マルコフ連鎖のクラスタリング処理の手順の別の例を示すフローチャートである。
【発明を実施するための形態】
【００２３】
＜基本的な考え方＞
従来のＰＰＲ（パーソナライズド・ページランク）アルゴリズムがリアルタイムでノードの重要度（ページランク値）やランキングを求めることができない理由は、マルコフ連鎖の計算を、対象とする大規模なネットワーク全体で実行するからである。インターネット上のウェブページ全体（ＷＷＷ：Wold Wide Web）に対してそのような計算を行うのにはかなりの時間を要する。
【００２４】
しかしながら、ユーザクエリ（検索要求）に依存したノード重要度・ランキングを求めるためには、本来ネットワーク全体ではなく、ユーザクエリに関連する部分のみでマルコフ連鎖計算を行えば十分なはずである。例えば、創薬に関するクエリに依存したノード重要度・ランキングをマルコフ連鎖計算で求める場合、マルコフ連鎖の範囲（すなわち、ネットワーク上でエージェントが歩き回る範囲）に医学、薬学、生化学等に関する領域は含めるべきであろうが、例えば航空工学、美術、考古学に関する領域は不要であろう。
【００２５】
したがって、ネットワークからユーザクエリに関連する「部分」を適切に切り出し、ＰＰＲアルゴリズムのマルコフ連鎖計算をこの「部分」に限定して実行することにより、ネットワーク全体に対してその計算を行うよりも短い時間で、ユーザクエリに依存したノード重要度・ランキングを求めることができるはずである。
【００２６】
そこで、本実施形態では、ネットワーク全体でのマルコフ連鎖をクラスタリングし、これにより生成された複数のクラスタの中から、ユーザクエリに関連するクラスタを抽出する。そして、元のネットワークのうちの、抽出したクラスタに対応する部分ネットワークについてのみ、ＰＰＲアルゴリズムによるマルコフ連鎖の計算を実行する。
【００２７】
ここで注意すべきは、本実施形態で行うクラスタリングは、ネットワークのノードとリンクの静的構造のクラスタリングではなく、そのネットワーク上のノード間のリンクをエージェントがランダムウォークするという動的なマルコフ連鎖過程のクラスタリングであるという点である。
【００２８】
本実施形態でのクラスタリングは、ネットワーク上を歩き回るエージェントに関する次のアナロジーに基づく。すなわち、種ノードセットへのジャンプを持たない通常のページランクアルゴリズムでのマルコフ連鎖は、ネットワーク全体を特定の志向を持たずに放浪するエージェントの運動に模される。一方、ネットワーク上の特定の方面に偏在して歩き回るエージェントは、この方面に対応する何らかの分野・トピックを志向しながら探索を行っているとみなすことができる。これを志向性マルコフ連鎖とよぶことにする。
【００２９】
そこで、本実施形態では、機械学習の理論に基づき、ネットワーク全体でのマルコフ連鎖を、複数の志向性マルコフ連鎖をクラスタとする形で構造化する。このクラスタリングは、個々のユーザの過去の検索履歴のようなユーザごとの情報、又はネットワークの構造などに基づくユーザによらない情報等の既知の情報を用いて、事前に（すなわちオンラインでのユーザクエリに応じた検索の前に）行っておく。クラスタリングはネットワーク全体に対してマルコフ連鎖の計算を行うためにある程度の時間を要するが、個別の検索の前に（例えば週に一度など）行われるので、これに要する時間はオンラインでの検索処理の場面では現れてこない。
【００３０】
そして、本実施形態では、このような事前のクラスタリング結果を用いて、ユーザクエリを処理する際の計算範囲を限定する。すなわち、ユーザクエリに対応する種ノードセットの個々のクラスタへの帰属度を求め、求めた帰属度に従ってユーザクエリに関連する１個以上のクラスタを選び出す。そして、元のネットワークのうち、選び出された１個以上のクラスタに属するノードを部分ネットワークとして抽出する。この部分ネットワーク上で種ノードセットを用いてＰＰＲアルゴリズムを実行することにより、種ノードセットに依存したノード重要度・ランキング処理が、ネットワーク全体の上でＰＰＲアルゴリズムを実行する場合よりも短時間で計算されることとなる。
＜導入：ベイズの枠組みに基づいたＰＰＲアルゴリズムの定式化＞
【００３１】
以下では、確率分布
【数１】
0005895813.tif 000002
の確率分布
【数２】
0005895813.tif 000003
を導入し、ベイズ（Bayes）の枠組みに基づいて
【数３】
0005895813.tif 000004
を推定することを試みる。ここで、Ｎは、対象のネットワークに含まれるノードの総数である。以下では混乱を避けるために、
【数４】
0005895813.tif 000005
を「活性ベクトル」ｐと呼び、
【数５】
0005895813.tif 000006
についてだけ「確率」という言葉を用いることにする。
【００３２】
活性ベクトルｐの各成分ｐｎ（ｎは１〜Ｎの整数）は、ネットワーク上の識別番号ｎのノード（以下「ノードｎ」と呼ぶ）にエージェントが存在する確率であり、これをノードｎの「活性」と呼ぶ。すなわち、活性ベクトルｐは、ある時点におけるネットワーク上の各ノードｎにエージェントが存在する確率（すなわち「活性」）の分布を示している。
【００３３】
エージェントが時間の経過に伴ってネットワーク上のリンクを辿ってランダムウォークすることを考えると、活性ベクトルｐは時間の経過に伴って発展していく。この活性ベクトルｐの確率的時間発展（stochastic dynamics）はマルコフ性を満たすと仮定する。すなわち、活性ベクトルｐの時系列
【数６】
0005895813.tif 000007
の確率（このような時系列が生じる確率）は、
【数７】
0005895813.tif 000008
と表される。ｔ、ｔ’は、０を始点とする離散的な時刻を示している。
【００３４】
この確率的時間発展をさらに詳しく説明する。時刻ｔの活性ベクトルｐすなわち
【数８】
0005895813.tif 000009
は、
【数９】
0005895813.tif 000010
を中心とするガウス分布に従うと仮定する。ただし、
【数１０】
0005895813.tif 000011
はマルコフ連鎖の遷移確率行列（ｍは１〜Ｎの整数）であり、
【数１１】
0005895813.tif 000012
かつ
【数１２】
0005895813.tif 000013
を満たす。遷移確率行列は、ネットワーク内のノードｍからノードｎへリンクを辿ってエージェントが遷移する確率を行列として表現したものである。例えばエージェントがノードから出る１以上のリンクを等確率で選択するとみなした場合、遷移確率行列は、ネットワークの構造、すなわちノード間がどのようにリンクされているか、のみに依存する。この場合、遷移確率行列は、ネットワークの構造を表す隣接行列の情報のみから計算される（例えば非特許文献１参照）。なお、遷移確率行列は、必ずしもこれに限られるものではない。この代わりに、本出願人が特願２０１１−１７９５１２号にて開示するように、遷移確率がネットワーク構造だけでなくリンク先のノードの重要度にも依存するようにした遷移確率行列を用いてもよい。
【００３５】
上述のガウス分布に従うとの仮定（すなわちノード間の遷移が遷移確率通りではなく、ガウス分布に従った誤差が生じるとの仮定）の下では、次の関係式が成り立つ。
【数１３】
0005895813.tif 000014
この式の中の「Ｎ（）」はガウス分布（正規分布）を示しており、αはこの分布の分散である。記号「〜」は右辺と左辺が（規格化定数の部分を除いて等しいことを示す）。
【００３６】
この式が表す確率Ｐは、
【数１４】
0005895813.tif 000015
で条件付けられているが、証拠（evidence）に関する情報を含まないという意味で、
【数１５】
0005895813.tif 000016
の事前確率（prior probability）とみなしてよい。ちなみに、分散αを無限大に近づけた極限（言い換えれば、温度Ｔα＝１／αを０に近づけた極限）では、通常の「決定論的」なマルコフ連鎖
【数１６】
0005895813.tif 000017
が得られる。
【００３７】
ここで、時刻ｔの活性ベクトルｐが、ノイズすなわち何らかの不確かさにより
【数１７】
0005895813.tif 000018
に劣化して観測されたとする。この劣化をガウス分布で記述すると、以下のようになる。
【数１８】
0005895813.tif 000019
βはガウス分布の分散である。これは時刻ｔの活性ベクトルｐの尤度関数（likelihood function）である。
【００３８】
ベイズ（Bayes）の公式から、時刻ｔの活性ベクトルｐの事後確率（posterior probability）は次式で表される。
【数１９】
0005895813.tif 000020
となる。式(1.1)および(1.2)を用いて、
【数２０】
0005895813.tif 000021
を得る。この式は、ガウス分布×ガウス分布はガウス分布であるというよく知られた事実を再現するものである。
【００３９】
ＭＡＰ（Maximum a Posteriori：最大事後確率）推定で時刻ｔの活性ベクトルｐを定める。
【数２１】
0005895813.tif 000022
【００４０】
この式においてβ／（α＋β）をｒとおくと、α／（α＋β）は（１−ｒ）であり、次の式が得られる。
【数２２】
0005895813.tif 000023
【００４１】
式(1.4)はＰＰＲアルゴリズムの式そのものである。ここで、時刻（ｔ−１）での活性ベクトルｐ、すなわち
【数２３】
0005895813.tif 000024
は条件付確率の「条件」であり、事前に与えられている必要がある。しかしながら、定常状態を仮定するならば、
【数２４】
0005895813.tif 000025
が成り立つ。したがって、式(1.4)を反復計算することにより、
【数２５】
0005895813.tif 000026
を求めることができる。この計算はＰＰＲアルゴリズムの計算に他ならない。
【００４２】
以上の説明において、式(1.1）が表す事前確率は、「ネットワーク中をあてどなく放浪するランダムウォーカー」をモデル化したものと解釈される。上記のベイズ定式に基づけば、ある領域（例えば医学関係）を志向する、すなわち、いわば「目的意識を持ってネットワーク中を探索するランダムウォーカー」を想定することも可能である。ある領域（分野）を表す種ベクトル
【数２６】
0005895813.tif 000027
を用意し、事前確率を次式で定める。
【数２７】
0005895813.tif 000028
すなわち、エージェントのうち割合ｑが種ベクトルの示す状態へと遷移し、残りの割合（１−ｑ）が前の時刻（ｔ−１）の状態から遷移行列に従って遷移すると仮定する。このとき、式(1.4)に相当する式は、
【数２８】
0005895813.tif 000029
となる。
【００４３】
なお、志向領域が二つ以上ある場合には、混合ガウス分布を扱うことになるが、同様の取扱が可能である。
＜マルコフ連鎖のクラスタリング＞
【００４４】
上述したＰＰＲアルゴリズムのベイズ定式化に機械学習の正統的な手法（潜在変数の手法）を導入することにより、マルコフ連鎖をクラスタリングするアルゴリズムを導出できることを以下に示す。
【００４５】
ここで議論するマルコフ連鎖クラスタリングとは、以下で定義されるものである。
【００４６】
すなわち、連結性を満たすネットワークがあり、このネットワーク全体でのマルコフ連鎖（次式）を考える。
【数２９】
0005895813.tif 000030
【００４７】
ここで、個々のクラスタを次のバイアス付きマルコフ連鎖（biased Markov chains）で定義する。
【数３０】
0005895813.tif 000031
【００４８】
ここで
【数３１】
0005895813.tif 000032
はｋ番目のクラスタの「芯」を表わすＮ次元ベクトルであり、
【数３２】
0005895813.tif 000033
である。ｋは１〜Ｋ（Ｋはクラスタの総数）の整数である。ｑｋはクラスタｋの、芯
【数３３】
0005895813.tif 000034
からの広がりを表わすパラメータであり、ｑｋが０に近い（１に近い）ならば広がりは大きい（小さい）。
【００４９】
マルコフ連鎖(a)に関して、D個のデータ点から成る観測データ
【数３４】
0005895813.tif 000035
が与えられたとする。ただし、
【数３５】
0005895813.tif 000036
はデータ点ｄを表わすN次元ベクトルであり、
【数３６】
0005895813.tif 000037
である。このような観測データから以下に説明する枠組みに基づき、クラスタの芯及び広がりを推定する。このようにして、マルコフ連鎖(a)を、個々のクラスタを表す複数のバイアス付きマルコフ連鎖(b)へとクラスタリングする。すなわち、観測データに含まれるＤ個のデータ点を用いた機械学習により、それらデータ点に適合したクラスタ分けを求める。
【００５０】
ところで、観測データ、すなわち、学習用データ
【数３７】
0005895813.tif 000038
を用意する方法としては、次のようなものが考えられる。
【００５１】
（１）ユーザの検索履歴から求める。
例えば、ユーザからの過去のＤ個の検索クエリ（ユーザクエリ）に対応するＤ個の検索結果を、観測データを構成する個々のデータ点ｄでの種ベクトル
【数３８】
0005895813.tif 000039
とする。種ベクトルは、例えば、ネットワーク上のＮ個のノードのうち、ユーザクエリの検索結果として求められたノードの値を正値（例えば「１」）とし、それ以外のノードの値を「０」とするＮ次元のベクトルを考え、さらに成分の総和が１となるように規格化、すなわち、
【数３９】
0005895813.tif 000040
とすることにより得られるものである。「検索結果として求められたノード」は、クエリが表す検索条件に合致したノード（例えば、検索条件に対する適合度が閾値以上のノード、又はページランク値（あるいはＰＰＲ値）を加味した適合度が閾値以上のノード、又は適合度が上位であるあらかじめ定めた数のノード、等）であってもよいし、それら検索条件に合致したノード群のうちユーザが実際に選択したものであってもよい。ネットワークとしてＷＷＷを考えた場合、個々のウェブページがノードであり、検索サイトに対してユーザが送信した検索条件（例えばキーワードの論理式）がユーザクエリに該当し、その検索条件に合致するウェブページ又はそれらウェブページのうちユーザが閲覧したページを「１」、それ以外のページを「０」とするベクトルを考え、これを成分の総和が1になるように規格化したものが種ベクトルである。このような種ベクトルをＤ個集めたものを、学習のための観測データとして用いる。
【００５２】
なお、ここでいう「ユーザ」は、個人であっても、複数人からなるグループであってもよい。いずれの場合も、過去の「ユーザ」の検索履歴を用いてネットワーク上のクラスタリングを機械学習することで、その「ユーザ」用にパーソナライズされたクラスタ分け結果が得られる。
【００５３】
（２）ネットワーク上の各ノードのリンク状態を観測データとする。
例えば、各ノードについて、そのノードから出るリンクのリンク先のノードに対応する成分を正値（例えば「１」）とし、それ以外のノードの成分を「０」とするＮ次元のベクトルを考え、これを成分の総和が1になるように規格化したものを種ベクトルとする。この場合、データ点の数Ｄは、ネットワーク上のノード数Ｎに等しい。
【００５４】
（３）ネットワーク上でのランダムウォークのシミュレーションにより観測データを生成する。
例えば、ネットワーク上でランダムウォークのシミュレーションを実行し、エージェント（ランダムウォークする者）が、連続するＬステップ（１ステップである１つのノードから別のノードへとエージェントが移動する）の間に立ち寄ったＬ個のノードに対応する成分を正値（例えば「１」）とし、その他のノードに対応する成分を「０」とするＮ次元ベクトルを考え、これを成分の総和が1になるように規格化したものを種ベクトルとする。例えば、シミュレーションで発生させたエージェントの移動軌跡（ノード列）の中からこのような種ベクトルをＤ個切り出せばよい。
【００５５】
上述の方法（１）により観測データを用意した場合は、マルコフ連鎖のクラスタリングは、いわばユーザクエリをクラスタリングすることと等しい。例えば、あるグループ（例えば企業等の組織）から発せられたクエリ群に対応する観測データを用いることで、そのグループが何に興味を持っているのか等を反映したクラスタリング結果が得られる。また、方法（２）又は（３）を用いて観測データを用意した場合には、ネットワーク全体の上でのマルコフ連鎖を、どのようなバイアス付きマルコフ連鎖の組合せに分解できるかが求められる。
【００５６】
以下、このような観測データを用いた、ネットワーク上のマルコフ連鎖のクラスタリングの機械学習について説明する。
【００５７】
次のガウス分布を考える。
【数４０】
0005895813.tif 000041
ここで、
【数４１】
0005895813.tif 000042
とする。
【００５８】
ここで、潜在変数
【数４２】
0005895813.tif 000043
を次のように定義する。
【数４３】
0005895813.tif 000044
ｚｋは潜在変数の第ｋ成分である（ｋは１〜Ｋまでの整数）。ｚｋ=1は、クラスタｋが選ばれることを示している。潜在変数は、クラスタリングにより得ようとするクラスタ（言い換えればバイアス付きマルコフ連鎖）の総数と同じ数の成分を有する。式(2.2a)は、潜在変数のＫ個の成分のうち、いずれか１つが「１」であり、その他は「０」であることを示す。
【００５９】
ここで、成分ｚｋが「１」である確率をπｋとする。すなわち、
【数４４】
0005895813.tif 000045
この確率は、クラスタｋが選ばれる確率である。
【数４５】
0005895813.tif 000046
【数４６】
0005895813.tif 000047
【００６０】
確率の乗法定理（product rule）から次の式が導かれる。
【数４７】
0005895813.tif 000048
【００６１】
ここで、ベクトルτは前述した観測データの成分（種ベクトル）である。したがって、最大化すべき尤度は次のように表現される。
【数４８】
0005895813.tif 000049
【００６２】
式(2.7)の最左辺と最右辺の対数を取ることにより、次式が導かれる。
【数４９】
0005895813.tif 000050
【００６３】
以下に説明する例では、機械学習のためのアルゴリズムとしてＥＭ（Expectation and Maximization）アルゴリズムを用いる。ただし、ＥＭアルゴリズムは採用し得る手法の一例に過ぎず、ｋ−ｍｅａｎｓ法等といった他の手法を用いてももちろんよい。
【００６４】
ＥＭアルゴリズムでは、まずＥステップにて、次式で定義されるクラスタｋへの帰属度γ（ｚｋ）を計算する。
【数５０】
0005895813.tif 000051
(2.9)式の中央の項にベイズの定理を適用することにより、最左辺が導かれる。なお、ここで、
【数５１】
0005895813.tif 000052
である。
【００６５】
次のＭステップについて説明する。上述の式(2.8)を
【数５２】
0005895813.tif 000053
に関して微分したものを０とする（事後確率の最大値では式(2.8)の微分は０である）ことで、次式が得られる。
【数５３】
0005895813.tif 000054
ここで、
【数５４】
0005895813.tif 000055
である。この式(2.10)は、次のように導かれる。
【数５５】
0005895813.tif 000056
【００６６】
すなわち、式(2.8)の微分を求め、これが０になるとして計算を行うことで、式(2.10)が導かれる。式(2.10）は、マルコフ連鎖を表している。
【００６７】
ここで、Ｄ個のデータ点を持つ観測データ（学習用データ）
【数５６】
0005895813.tif 000057
が与えられたとする。そして、式(2.8)で表される対数確率をD個のデータ点にわたって総和したものを評価値Ｑとして導入する。すなわち、評価値Ｑは次式で表される。
【数５７】
0005895813.tif 000058
【００６８】
この式(2.11)の最左辺及び中央の辺を、
【数５８】
0005895813.tif 000059
に関して微分したものを０とすることで、次式(2.12)が導かれる。
【数５９】
0005895813.tif 000060
である。
【００６９】
また、式(2.11)のqｋに関する微分を０とすることで、次式(2.15)が導かれる。
【数６０】
0005895813.tif 000061
【００７０】
また、式(2.11)の最左辺及び中央の辺に同じ項を加えることで、次式(2.16)が得られる。
【数６１】
0005895813.tif 000062
この式(2.16）の両辺をπｋに関して微分し、その微分結果の値を０とすることで、次式(2.17)が導かれる。
【数６２】
0005895813.tif 000063
【００７１】
以上に示した導出は、Christopher M. Bishop 著の“Pattern Recognition And Machine Learning (Information Science and Statistics)” (出版社Springer, 2006/8/17)の第９章に記載されている正統的なＥＭアルゴリズムの適用手法を、ネットワーク上のマルコフ連鎖のクラスタリングに適用することにより導かれる。
＜クラスタリング処理の流れ：オフライン処理＞
【００７２】
以上をまとめると、本実施形態におけるクラスタリング処理の流れは、図１に示すような流れとなる。すなわち、Ｄ個のデータ点からなる観測データ（学習用のデータ）
【数６３】
0005895813.tif 000064
が与えられたとする。
【００７３】
この実施形態では、データ点ｄに関するマルコフ連鎖は次式(I)で表される（上述の式(2.10)から導かれる）。
【数６４】
0005895813.tif 000065
である。すなわち、(I)式は、ネットワーク上の各ノードにエージェントが存在する確率が、ある一定割合β／（α＋β）の分だけはデータ点ｄの種ベクトルτ（ｄ）ｏｌｄに依存し（すなわち割合β／（α＋β）は種ベクトルが表すノード群にエージェントが回帰するものとし）、残りの分は各クラスタｋのマルコフ連鎖によって求められる確率を各クラスタｋへの帰属度に応じて足し合わせたものであることを表している。
【００７４】
クラスタリング処理では、まず、図１のＳ１０に示すように、式(I)の右辺の各項に含まれる変数の値を仮決めする。なお、遷移確率行列Ｔは、例えばページランクアルゴリズムの場合と同様の方法で、ネットワークのリンク構造等に基づいてあらかじめ求められているものとする。また、α及びβは、式(1.1）及び(1.2)に現れるガウス分布の分散であり、これらの値はユーザが指定しておく。
【００７５】
このように変数を仮決め（Ｓ１０）した後、式(I)を計算する（Ｓ１２）。
【００７６】
次に、ＥＭアルゴリズムのＥステップで、帰属度γ（ｚｄｋ）を次式(II)で計算する（Ｓ１４）。
【数６５】
0005895813.tif 000066
【００７７】
次に、Mステップにて、次の式（IIIa）〜(IIIc)が表す各値を計算する（Ｓ１６）。
【数６６】
0005895813.tif 000067
【００７８】
また、これら式(I)〜(IIIc)で求められた各変数の値を、次の繰り返しの演算のために、１ステップ前の値を表す変数（時刻ｔ−１における確率、及び添え字old付きの変数）に設定する（Ｓ１８）。
【００７９】
そして、次式(IV)で定義される評価値Ｑの、現時刻ｔと直前の時刻（ｔ−１）との間での差の大きさが十分に小さくなる（すなわち、その差の大きさがあらかじめ定めた閾値εよりも小さくなる）まで、時刻ｔを１ずつ進めて、Ｓ１２からＳ１８の処理を繰り返す（Ｓ２０）。
【数６７】
0005895813.tif 000068
【００８０】
現時刻ｔと直前の時刻（ｔ−１）との間での評価値Ｑの差の大きさが閾値εよりも小さくなったときの式(IIIa)及び(IIIb）の計算結果が、観測データ（学習用データ）から求められる各クラスタｋの芯
【数６８】
0005895813.tif 000069
及び広がりｑｋとなる。これら芯及び広がりにより、各クラスタｋが規定されることとなる。
【００８１】
本実施形態では、以上に説明したマルコフ連鎖のクラスタリングの結果を用いて、ネットワーク上のノード群をクラスタリングする。すなわち、各ノードが、マルコフ連鎖のクラスタリング結果のどのクラスタに属するかを判定する。各ノードの帰属先のクラスタは必ずしも１つに限定される必要はなく、例えば１つのノードが複数のクラスタに対しそれぞれ個別の帰属度合いで帰属していると捉えるようにしてもよい。
【００８２】
このノードのクラスタリング処理では、これまで説明した手続きで定められた各クラスタの芯及び広がりを用いて、次式で定義されるマルコフ連鎖の定常状態を求める（すなわち、パーソナライズドページランクアルゴリズムを実行する）。
【数６９】
0005895813.tif 000070
【００８３】
(V)式は、上述の(b)式（数３０）と同じものであり、マルコフ連鎖のクラスタリング結果であるクラスタｋを表すバイアス付きマルコフ連鎖の式である。
【００８４】
定常状態の求め方は、通常のマルコフ連鎖計算の方法に従う。すなわち、
【数７０】
0005895813.tif 000071
が収束するまで、時刻ｔを１ずつ進めて(V)式の計算を繰り返す。
【００８５】
クラスタｋはこうして得られた定常状態
【数７１】
0005895813.tif 000072
により規定される（添え字のsは定常状態steady stateを意味する）。ここで
【数７２】
0005895813.tif 000073
は、「ノードｎのクラスタｋへの帰属度」を表す。すなわち、この値が大きい（すなわち１に近い）ほど、ノードｎがクラスタｋに帰属（すなわち所属）する可能性は高く、この値が小さい（すなわち０に近い）ほど、ノードｎがクラスタｋに帰属する可能性は低い。このように、(VI)式で表される帰属度ベクトルｐ［ｓ，ｋ］は、ネットワーク上の各ノードがクラスタｋに属する度合いの、ノード番号ｎに沿った分布を表す。
【００８６】
このようにして、(VI)式により表されるクラスタｋに対する各ノードｎの帰属度からなるベクトルが、クラスタリング結果として求められる。このクラスタリング結果は、後述するオンラインでの検索処理に利用される。
【００８７】
以上に説明したマルコフ連鎖のクラスタリング処理は、ネットワーク上の全ノードを対象としてＰＰＲアルゴリズムを実行する必要があるため、計算のためにかなりの時間を要する。しかしながら、ユーザクエリの内容は検索の度ごとに様々に変化するのに対し、過去のユーザ（グループの場合もある）の検索履歴等に基づくマルコフ連鎖のクラスタ分け状態の変化は時間的にかなり緩やかである。したがって、一度求めたクラスタリングの結果はある程度長い期間にわたって利用しても、ユーザクエリに対して十分な精度の検索結果（ランキング結果）が得られるので、クラスタリング処理をクエリの度に毎回行わなくてもよい。そこで、本実施形態では、このようなクラスタリング処理を、ユーザクエリにリアルタイムで応答するオンライン処理とは別に、例えば１週間に１回や１日に１回などといったあらかじめ定められたタイミングでのオフライン処理として実行する。すなわち、例えば、定期的に、ユーザごとに、そのユーザの検索履歴等から生成した学習用の観測データを用い、上述の手法によりクラスタリングを学習する。この学習により、(VI)式で表される各クラスタｋの特徴を表すベクトルが求められる。求められたベクトルは、ユーザのＩＤ（識別情報）に対応づけて保存され、オンラインでの検索処理の際に参照される。
＜クラスタリング結果を利用した検索：オンライン処理＞
【００８８】
次に、上述のようなマルコフ連鎖のクラスタリング結果を用いた、ユーザクエリに対するリアルタイムでの検索処理（オンライン処理）の一例を、図２を参照して説明する。
【００８９】
図２の手順は、ユーザからの検索クエリ（ユーザクエリ）が到来したことをトリガとして実行される。なお、ユーザは検索システムに対するログインを済ませており、この結果、検索システムはクエリを発したユーザのＩＤを知っているものとする。
【００９０】
この手順では、検索システムは、まず、そのユーザクエリに含まれる検索条件（例えば１以上のキーワードからなる論理式など）に合致するノード（例えばウェブページ）を、ネットワーク（例えばＷＷＷ）上から検索する（Ｓ３０：一次検索）。この一次検索では、ページランク等に基づく個々のノードの重要度は考慮せず、単純に検索条件に合致するノード（すなわち検索条件に対する適合度が閾値以上のノード、又は適合度が上位のあらかじめ定めた数のノード）を求める。検索条件に対する適合度は、従来の検索技術を用いて求めればよい。このような一次検索の結果から、ユーザクエリに対応する種ノードセット、
【数７３】
0005895813.tif 000074
を生成する。この種ノードセットは、例えば、ネットワーク上のＮ個のノードのうちユーザクエリの検索条件に合致するものとして求められたノードに対応する成分を正値（例えば「１」）とし、それ以外のノードに対応する成分を「０」とするＮ次元のベクトルである。種ノードセットは、ユーザクエリの特徴をネットワーク内での検索条件に合致するノードの分布（どのノードが検索条件に合致しているかを示す分布）として表現したものである。
【００９１】
また、検索システムは、保存されている各ユーザのクラスタリング結果の情報のうち、今回のユーザクエリを発したユーザに対応するクラスタリング結果の情報を取得する。なお、保存されているクラスタリング結果が、複数の個人からなるユーザグループに対応するものである場合、ログインしたユーザがどのグループに属するかをディレクトリデータベース等から求め、求めたグループに対応するクラスタリング結果の情報を取得すればよい。
【００９２】
次に、検索システムは、この種ノードセットのクラスタｋへの帰属度
【数７４】
0005895813.tif 000075
を次式に従って計算する（Ｓ３２）。
【数７５】
0005895813.tif 000076
【００９３】
(A1)式の計算で用いられるノードｎのクラスタｋへの帰属度ｐｎ［ｓ，ｋ］は、クエリ発行元のユーザに対応するクラスタリング結果の情報に含まれている。(A1)式の右辺は、ベクトルτ（すなわち種ノードセット）とベクトルｐ［ｓ，ｋ］（すなわちネットワーク上の各ノードのクラスタｋに対する帰属度を成分とするベクトル）との内積を求める演算である。種ノードセットが表すユーザクエリの特徴を表すノード群と、ベクトルｐ［ｓ，ｋ］が表すクラスタｋへの帰属（所属）度合いが高いノード群との共通性が高いほど、帰属度Ｒｋの値は大きくなる。
【００９４】
次に、検索システムは、(A1)式の演算により求めた帰属度
【数７６】
0005895813.tif 000077
の値が大きいクラスタから順にＬ個のクラスタを抽出する（Ｓ３４）。Ｌは、抽出するクラスタの個数を表す値であり、事前に定めておく。
【００９５】
そして、検索システムは、抽出されたL個のクラスタのそれぞれにおいて、
【数７７】
0005895813.tif 000078
（θの値は事前に定めておく）を満たすノードを選ぶ（Ｓ３６）。ここで、ｋは、抽出されたL個のクラスタの識別番号である。すなわち、Ｓ３６では、クラスタｋへの帰属度ｐｎ［ｓ，ｋ］は０から１までの値をとるアナログ値であるが、この値が閾値θ以上であるノードｎを、クラスタｋに属するノードとして選別するのである。このように閾値θの値が、クラスタｋに属するノードと判定される帰属度の下限値を規定する。
【００９６】
このようにしてL個のクラスタを通じて選び出されたノード群と、元のネットワーク上のそれらノード同士の間のリンクと、からネットワークを構成する（Ｓ３８）。このネットワークは、元のネットワークの部分ネットワークになっている。すなわち、Ｓ３８では、元のネットワークから、抽出されたクラスタのノードのみからなる部分ネットワークを切り出すのである。
【００９７】
この部分ネットワークの構造を定める隣接行列は次式で表される。
【数７８】
0005895813.tif 000079
ただし、i,j=1,2,…,N（ｔ）であり、N（ｔ）は、この部分ネットワークを構成するノードの総数（N（ｔ）＜Ｎ）である。
【００９８】
この手順では、次に、次式で定義されるマルコフ連鎖の定常状態を求める（Ｓ４０）。すなわち、ＰＰＲアルゴリズムを実行するのである。
【数７９】
0005895813.tif 000080
ただし、
【数８０】
0005895813.tif 000081
は遷移確率行列である。なお、ここで例示した遷移確率行列は、ネットワーク上のリンクをすべて等価値とみなしたもの（すなわちあるノードに存在するエージェントが、そのノードから出る複数のリンクを等確率で選択するとみなしたもの）であり、通常のページランクアルゴリズムで用いられているものである。この遷移確率行列は、ネットワークのリンク構造のみから規定されるものであり、マルコフ連鎖の時間発展（時間の経過）によって変化しない静的なものである。
【００９９】
ただし、これは一例に過ぎない。この代わりに、例えばリンクの先のノードの評価値（重要度）が高いほど、そのリンクが選ばれる確率（遷移確率）が高くなるように遷移確率行列を定めてもよい。この場合、マルコフ連鎖の時間発展に伴って各ノードの評価値が変化するに連れ、遷移確率行列も変化する。このように遷移確率行列も時間的に更新しながら、マルコフ連鎖の式(A2)の計算を繰り返すことで、定常解を求めればよい。なお、遷移確率をリンク先ノードの評価値に応じて定める方式については、本出願人による特願２０１１−１７９５１２号の明細書に詳しく説明されているので、ここではこれ以上の説明は省略する。
【０１００】
(A2)式における
【数８１】
0005895813.tif 000082
はＮ（ｔ）次元のベクトルであり、Ｎ次元ベクトル
【数８２】
0005895813.tif 000083
から部分ネットワークのＮ（ｔ）個のノードに対応する成分だけを取り出して構成されたものである。Ｎ（ｔ）次元ベクトル
【数８３】
0005895813.tif 000084
も同様にしてＮ次元ベクトル
【数８４】
0005895813.tif 000085
から構成される。
【０１０１】
式(A2)のＰＰＲアルゴリズムにより求められた定常状態のページランク値
【数８５】
0005895813.tif 000086
で部分ネットワーク上のＮ（ｔ）個の各ノードの重要度を定める。すなわち、
【数８６】
0005895813.tif 000087
がノードｉの重要度を表わす。こうして定められた重要度の大きさに従って、Ｎ（ｔ）個のノードをランク付けする（Ｓ４２）。なお、計算したノードの重要度と、当該ノードのユーザクエリ（検索条件）への適合度と、の両方を加味した評価値を求め、その評価値が高い順に各ノードをランク付けしてもよい。そして、このランク付け結果に従って、ユーザクエリに対する応答情報を生成し、クエリを発したユーザに対してその応答情報を返す（Ｓ４４）。応答情報は、例えば、ランク順に並べたノードのリスト（例えばウェブページへのリンクをランク順に並べたリスト）等である。
【０１０２】
以上の手順により、ユーザクエリに対して、ＰＰＲ値を考慮した応答情報が求められる。この検索処理では、(A2)式に示すＰＰＲアルゴリズムの計算を行うが、この計算の対象となるのは、ネットワーク全体ではなく、種ノードセットに対する帰属度（類似度）の高いクラスタだけから構成される部分ネットワークである。このため、計算に要するコストは、ネットワーク全体を対象とする通常のＰＰＲアルゴリズムの演算の場合に比べて遙かに少ない。したがって、ユーザクエリに対してほぼリアルタイムで検索結果が求められる。
【０１０３】
以上の例では、種ノードセットτを一次検索により求めたが、これは一例に過ぎず、別の方式で種ノードセットを求めてもよい。
＜システム構成の例＞
【０１０４】
以上に説明したオフライン（クラスタリング）処理及びオンライン（検索）処理を実行する検索システムの構成の例を、図３に示す。
【０１０５】
図３において、ネットワーク情報記憶装置１０は、処理の対象となるネットワーク（例えばＷＷＷ）の情報（以下「ネットワーク情報」と呼ぶ）を記憶する記憶装置である。ネットワーク情報には、当該ネットワークの構造を示す情報、すなわち当該ネットワーク内のノード同士のリンク接続の関係を示す情報が含まれる。このネットワーク構造情報は、例えば隣接行列の形で表現される。なお、周知のように隣接行列Ａｎｍは、ノードｍからノードｎへリンクが張られていればＡｎｍ＝１、そうでなければＡｎｍ＝０となる行列である。また、ネットワーク情報には、各ノードの詳細情報が含まれていてもよい。例えばノードがウェブページである場合、そのウェブページ内のテキスト情報が詳細情報の一例である。ＷＷＷのように時間の経過に伴ってネットワークの構造や個々のノードの内容が変化し得るネットワークを対象とする場合、クローラー１２が定期的にネットワークを巡回し、その巡回結果に従ってネットワーク情報記憶装置１０内のネットワーク情報を更新する。
【０１０６】
学習用データ記憶装置１４は、ネットワーク上でのマルコフ連鎖過程のクラスタ分けの学習に用いる学習用データ（上述の「観測データτ」）を記憶する装置である。各ユーザの関心に沿った検索を実現しようとする場合には、学習用データ記憶装置１４には、ユーザごとの学習用データを記憶しておく。ユーザごとの学習用データとしては、例えば、上に例示した個々のユーザの検索履歴を用いればよい。この場合、例えば、後述する検索処理部２０の検索結果を学習用データ記憶装置１４に記憶するようにすればよい。学習用データ記憶装置１４には、ユーザごとに、学習に用いるデータ点の個数Ｄだけ検索結果の情報が記憶されていればよく、例えばユーザが新たに検索を行うごとに、そのユーザのＤ個の検索結果のうちの最も古いものを学習用データ記憶装置１４から削除し、今回の検索結果を追加すればよい。
【０１０７】
クラスタリング処理部１６は、ネットワーク情報記憶装置１０に記憶されているネットワーク構造の情報と、学習用データ記憶装置１４に記憶されている学習用データとを用いて、上述した図１の処理手順を実行することにより、当該ネットワーク上のマルコフ連鎖のクラスタリングを学習する。この学習処理は、クラスタリングの更新タイミングが到来するごとに実行する。ユーザクエリにリアルタイムで応答する処理をオンライン処理と呼ぶ場合、この学習処理はオフライン処理と言える。
【０１０８】
ここで、クラスタリング処理部１６は、クラスタの芯や広がりなどの変数の値を一時データ記憶部１７から読み出して図１のＳ１２，Ｓ１４，及びＳ１６の各計算を実行し、Ｓ１８でその計算結果に応じて一時データ記憶部１７内のそれら変数の値を更新する。一時データ記憶部１７は、例えば、検索システムが実装されるコンピュータのメインメモリ内に確保された記憶領域である。クラスタリング処理部１６の処理の実行により求められたクラスタリング結果のデータ（上述の(IV)式で表されるノードｎのクラスタｋへの帰属度のデータ）は、クラスタリング結果記憶装置１８に保存される。ユーザごとの学習用データを用いてクラスタリングの学習を行った場合は、例えばユーザＩＤに対応づけるなどの形で、ユーザごとにクラスタリング結果が保存される。
【０１０９】
検索処理部２０は、ユーザからクエリを受け付け、そのクエリに対して図２の検索処理をリアルタイムで実行する（オンライン処理）。この処理において、検索処理部２０は、ネットワーク情報記憶装置１０に記憶された各ノードの詳細情報（例えば各ウェブページのテキスト情報）を対象として、ユーザクエリの検索条件に基づいて一次検索（図２のＳ３０）を実行し、種ノードセットを求める。そして、求めた種ノードセットと、クラスタリング結果記憶装置１８に記憶された当該ユーザのクラスタリング結果の情報を用いることにより、Ｓ３２〜Ｓ３６の処理を行うことにより、ＰＰＲ演算（Ｓ４０）の対象とするノード群を選別する。そして、ネットワーク情報記憶装置１０に記憶されたネットワーク構造の情報から、それら選別されたノード群のみからなる部分ネットワークを生成する（Ｓ３８）。そして、部分ネットワークに対してＰＰＲ演算を実行する（Ｓ４０）ことにより各ノードのＰＰＲ値を求め、そのＰＰＲ値に基づいてそれらノードのランク付けを行い（Ｓ４２）、そのランク付けの結果に基づいてユーザに対して応答を行う（Ｓ４４）。なお、検索処理部２０は、以上の処理を実行する際の作業用のデータ、例えばＳ３０〜Ｓ３８の各ステップの処理結果、Ｓ４０のＰＰＲアルゴリズムにおける各繰り返しでの計算結果、Ｓ４２でのランク付け結果等を一時データ記憶部２２に書き込み、また一時データ記憶部２２内のそれらデータを後続の各ステップでの計算において利用する。
＜クラスタリングの別の例＞
【０１１０】
以上では、ネットワーク上のマルコフ連鎖をクラスタリングし、その結果得られるクラスタの情報を用いてそのネットワークに対する検索を実行するシステムについて説明した。しかしながら、以上のシステムの例で説明したクラスタリング方式はあくまで一例に過ぎない。そこで、以下では、ネットワーク上のマルコフ連鎖をクラスタリングする方式の別の例について説明する。
【０１１１】
上述の例では、クラスタリングのために、クラスタの芯及び広がりというパラメータを用いた。これに対し、この例では、そのようなパラメータは用いない。ただし、ノード間の遷移が遷移確率行列通りではなく、遷移確率行列を中心として、ある確率分布に従った誤差が生じると仮定する点は、この例も同じである。
【０１１２】
上述の例も、以下に説明する例も、ネットワーク上のマルコフ連鎖を用いている。マルコフ連鎖に注目した理由は、リンクに方向がある場合であっても、あるいは、リンクにアナログ値の重みがある場合であっても、そのネットワーク上でのマルコフ連鎖を全く自然に定義することができるからである。
【０１１３】
ネットワーク上のマルコフ連鎖は、リンクを辿りながらネットワークをランダムに移動するエージェント（ランダムウォーカー）の動きを表わすものととらえることができる。ネットワークが複数のクラスタ（リンク密度が高い部分：コミュニティとも呼ぶ）から構成されているならば、ランダムウォーカーの動きは、一つのクラスタに対応する領域に暫く滞留し、その後、別のクラスタに対応する領域に移ってそこに暫く滞留し、その後、さらに別のクラスタに対応する領域に移ってそこに暫く滞留し、…というものになるであろう。
【０１１４】
ランダムウォーカーが現在どの辺りにいるかの情報が得られたとする。この情報が生成される過程を次のような確率モデルで表わす。
【０１１５】
(1)  ネットワーク上のランダムウォーカーはいずれか一つのクラスタ（以下では、「コミュニティ」と呼ぶことともある）に対応する領域にいて、そこをランダムに動き回っている。どの領域にいるかは確率的に決まる。
【０１１６】
(2)  (1)で確率的に決められたクラスタに対応する領域を動き回っているランダムウォーカーの現在の居場所を観測した結果、どの辺りにいるかの情報が得られる。
【０１１７】
観測が独立に何回も行われて、ランダムウォーカーの居場所に関するデータがたくさん集まったとする。これらのデータを上記の確率モデルに代入したものが「尤度」である。尤度は（仮に決めた）クラスタリング構造あるいは（仮に決めた）コミュニティ構造の関数である。そこで、尤度を最大化するようにクラスタリング構造（コミュニティ構造）を定める。これが求めるべき（最も確からしい）クラスタリング構造（コミュニティ構造）である。
【０１１８】
この例でも、対象となるネットワークを隣接行列Ａで表現する。
【数８７】
0005895813.tif 000088
【０１１９】
ここで、ｎ，ｍ＝１，２，…，Ｎであり、Ｎは当該ネットワークに含まれるノードの総数である。また、上述のシステムの例では、隣接行列のｎ行ｍ列の要素Ａｎｍは、０か１のいずれかの値をとり、ノードｍからノードｎへのリンクがネットワーク上に存在すれば１、存在しなければ０であった。これに対し、以下の例では、要素Ａｎｍは、０か１かではなく、アナログ値、すなわち、ある連続的な数値範囲（例えば０〜１の実数）内のいずれかの値をとる。この要素Ａｎｍの値は、ノードｍからノードｎへのリンクの強度（重み）を示す。
【０１２０】
このネットワークの上のマルコフ連鎖は、このネットワークにおける確率の伝搬のことであり、次の式で表される。
【数８８】
0005895813.tif 000089
このベクトルｐ（ｔ）の第ｎ成分ｐｎ（ｔ）は、時刻ｔにおいてノードｎに割り当てられた確率密度であり、以下の式で表される。
【数８９】
0005895813.tif 000090
ここで、行列Ｔはマルコフ連鎖の遷移確率行列であり、以下の式で表される。
【数９０】
0005895813.tif 000091
遷移確率行列Ｔは次式を満たす。
【数９１】
0005895813.tif 000092
これにより、確率の保存則が成り立つ。
【数９２】
0005895813.tif 000093
ここで、
【数９３】
0005895813.tif 000094
である。
【０１２１】
このように定めることで、マルコフ連鎖は、ネットワーク上でのあるエージェントのランダムウォークとみなすことができ、ｐｎ（ｔ）は、エージェント（ランダムウォーカー）が時刻ｔにおいてノードｎにて見出される（すなわち時刻ｔにノードｎ上に存在する）確率ととらえることが可能となる。
【０１２２】
式(3.2a)、(3.2b)で表した「全体」マルコフ連鎖を、それぞれ
【数９４】
0005895813.tif 000095
で表されるＫ個の「局所」マルコフ連鎖へとクラスタリングすることを考える。これらＫ個のクラスタ（局所マルコフ連鎖）は、互いに重複する部分（すなわち複数のクラスタに属するノード）を持っていてもよい。
【０１２３】
このクラスタリングのために、Ｄ個の学習用データの集合（次式）を用意する。
【数９５】
0005895813.tif 000096
ここで、
【数９６】
0005895813.tif 000097
である。
【０１２４】
この学習用データの集合としては、例えば、ネットワーク上での、あるランダムウォーカーの存在位置を、時刻を変えてＤ回観察した結果を用いてもよい。例えば、ｄ番目の観察の際にランダムウォーカーがノードｍ上で発見された場合、その観察結果は次式で表される。
【数９７】
0005895813.tif 000098
ここで、δｍｎはクロネッカーのδである。すなわち、ある観察ｄにて得られた学習用データは、その観察の際にランダムウォーカーが存在するノードｍに対応する第ｍ成分は１、それ以外の成分は０である、Ｎ次元のベクトルである。学習用データの数Ｄがネットワークのノード数Ｎよりも十分大きいとするならば、これらＤ個の中で、τ（ｄ）はＤｐｍ（ＰＲ）回登場すると考えられる。ただし、ｐｍ（ＰＲ）は、別途事前に単独に計算されたマルコフ連鎖（式(3.2a)、(3.2b)）の定常状態の第ｍ成分である。このとき、式(3.2b)においてｍが１からDまでの総和を求める必要はなく、重複を考慮すれば、ｍが１からNまでの総和を計算すれば十分である。
【０１２５】
学習用データを用いたクラスタリングの枠組みは、上述したBishopの著書” Pattern recognition and machine learning”の第９章に示される方式に従う。
【０１２６】
まず、Ｋ次元の二値のランダム変数、
【数９８】
0005895813.tif 000099
を導入する。Ｋは、クラスタリングにより生成しようとするクラスタの総数である。ここで、このランダム変数のＫ個の成分のうちの特定の１つ、すなわち
【数９９】
0005895813.tif 000100
が１であり、その他の成分は０である。
ここで、
【数１００】
0005895813.tif 000101
が、
【数１０１】
0005895813.tif 000102
の事前確率（prior probability）であるとする。この場合、次式が成り立つ。
【数１０２】
0005895813.tif 000103
ここで、結合確率、すなわち、
【数１０３】
0005895813.tif 000104
を考える。この結合確率は、学習用データτ（ｄ）と、クラスタｋが選ばれることを示す二値の潜在変数ｚｄｋと、活性ベクトルｐ（ｋ）を変数とする確率である。ここで、
【数１０４】
0005895813.tif 000105
とする。
式(4.3)において、
【数１０５】
0005895813.tif 000106
は、
【数１０６】
0005895813.tif 000107
の事前確率であり、これは、一般に、
【数１０７】
0005895813.tif 000108
が最も起こりやすくなるように選ばれる。ここで、
【数１０８】
0005895813.tif 000109
は、
【数１０９】
0005895813.tif 000110
が与えられたときの
【数１１０】
0005895813.tif 000111
の確率である（すなわち、
【数１１１】
0005895813.tif 000112
の尤度関数である）。
ベイズの定理から、次式が得られる。
【数１１２】
0005895813.tif 000113
上記Bishopの著書に示された方式に従って、結合確率の対数をとる。
【数１１３】
0005895813.tif 000114
ここで事後確率
【数１１４】
0005895813.tif 000115
を用いることで、結合確率の対数の期待値Ｑを求める。
【数１１５】
0005895813.tif 000116
式(4.8)の右辺の導出には、次式の関係を用いた。
【数１１６】
0005895813.tif 000117
【０１２７】
上述のシステムの説明では、事前確率の分布（事前分布）としてガウス分布を用いた例（式(1.1)参照）を示したが、以下では、事前分布としてガウス分布を用いた場合と、ディリクレ分布を用いた場合の例をそれぞれ示す。
【０１２８】
（ガウス事前分布を用いたマルコフ連鎖クラスタリング）
事前分布としてガウス分布を用いると、結合確率は以下に示すものとなる。
【数１１７】
0005895813.tif 000118
ベイズの定理から、次の関係が求められる。
【数１１８】
0005895813.tif 000119
上述のように、
【数１１９】
0005895813.tif 000120
であるから、結合確率の対数は以下のようになる。
【数１２０】
0005895813.tif 000121
したがって、結合確率の対数の期待値Ｑは次のようになる。
【数１２１】
0005895813.tif 000122
この導出には、次の関係を用いた。
【数１２２】
0005895813.tif 000123
ここで、この期待値Ｑを
【数１２３】
0005895813.tif 000124
に関して最大化することで、以下の関係式が得られる。
【数１２４】
0005895813.tif 000125
ここで、
【数１２５】
0005895813.tif 000126
である。
なお、式(5.7)の導出は以下の通りである。
【数１２６】
0005895813.tif 000127
ここで、
【数１２７】
0005895813.tif 000128
とすると、
【数１２８】
0005895813.tif 000129
は、確率の保存則を満たす。すなわち、
【数１２９】
0005895813.tif 000130
となる。
なぜなら、
【数１３０】
0005895813.tif 000131
だからである。
ここで、
【数１３１】
0005895813.tif 000132
という制約の下で、
【数１３２】
0005895813.tif 000133
に関してＱを最大化すると、次式が導かれる。
【数１３３】
0005895813.tif 000134
学習用データの数Ｄが、ネットワークのノード数Ｎよりも十分に大きい場合には、式(5.5)の期待値Ｑを次のように近似することができる。
【数１３４】
0005895813.tif 000135
ここで、
【数１３５】
0005895813.tif 000136
は、マルコフ連鎖(3.2a)、(3.2b)の定常状態における、ネットワーク上のノード全体にわたる確率分布である。すなわち、
【数１３６】
0005895813.tif 000137
は次式を満たす。
【数１３７】
0005895813.tif 000138
期待値Ｑを
【数１３８】
0005895813.tif 000139
に関して最大化することで、次式が導かれる。
【数１３９】
0005895813.tif 000140
また、期待値Ｑを
【数１４０】
0005895813.tif 000141
という制約の下で、
【数１４１】
0005895813.tif 000142
に関して最大化することで、次式が導かれる。
【数１４２】
0005895813.tif 000143
【０１２９】
以上をまとめると、この例におけるクラスタリング処理の流れは、図４に示すようなものとなる。
【０１３０】
この例では、学習用データｄに関するマルコフ連鎖は次式(I)（上述の式(5.7)、(5.8)と同じ）で表される。
【数１４３】
0005895813.tif 000144
ここで
【数１４４】
0005895813.tif 000145
である。すなわち、活性ベクトルｐ（ｋ）は、時間ステップが（ｔ−１）からｔへと進むと、この式(I)に従って時間発展する。
【０１３１】
クラスタリング処理では、まず、図４のＳ５０に示すように、式(I)の右辺の各項に含まれる変数の値を仮決めする。また、遷移確率行列Ｔは、例えばページランクアルゴリズムの場合と同様の方法で、ネットワークのリンク構造等に基づいてあらかじめ求められているものとする。また、α及びβは、式(5.2)、(5.3)に現れるガウス分布の分散であり、これらの値はユーザが指定しておく。
仮決めした
【数１４５】
0005895813.tif 000146
により、式(I)の右辺の
【数１４６】
0005895813.tif 000147
が決まる（式(4.4a)、(4.4b)参照）。
このように変数を仮決め（Ｓ５０）した後、上述した式(I)により
【数１４７】
0005895813.tif 000148
を計算する（Ｓ５２）。
次に、帰属度γｄｋを次式(II)（上述の式(5.2)参照）で計算する（Ｓ５４）。
【数１４８】
0005895813.tif 000149
【０１３２】
次に、次の式（III)によりπｋｎｅｗを計算する（Ｓ５６）。
【数１４９】
0005895813.tif 000150
なお、学習用データ数Ｄがネットワークのノード数Ｎよりも十分大きい場合は、式(I)、(II)、(III)として以下のものを用いればよい。
【数１５０】
0005895813.tif 000151
【０１３３】
以上のようにして、Ｓ５２、Ｓ５４及びＳ５６の計算が完了すると、これら式(I)〜(III)で求められた各変数の値を、次の繰り返しの演算のために、１ステップ前の値を表す変数（時刻ｔ−１における確率、及び添え字old付きの変数）に設定する（Ｓ５８）。
【０１３４】
そして、式(5.5)（ＤがＮより十分大きい場合は式(5.11)）により評価値Ｑを求め、求めた評価値Ｑと１つ前の時刻（ｔ−１）において求めた評価値Ｑとの差が十分小さく（例えばその差の絶対値があらかじめ定めた閾値εより小さく）なったかどうかを判定する（Ｓ５９）。すなわち、Ｓ５９では、時間発展の繰り返し演算が収束したかどうかを判定している。この判定の結果が否定（Ｎｏ：今回と前回の評価値Ｑの差が十分小さくなっていない、すなわち収束していない）の場合、時刻ｔを１進めて、Ｓ５２からＳ５８の処理を繰り返す。Ｓ５９の判定結果が肯定（Ｙｅｓ）の場合、図４の処理を終了する。
【０１３５】
図４の処理終了時の式(I)が、クラスタｋの部分的なマルコフ連鎖を表している。このように、図４に示した手順では、時間ステップを１つずつ進めながら(I)〜(III)式を繰り返し演算することで、(I)式中のパラメータＤｋ及びγｄｋが調整されていき、各クラスタｋの形が定まってくるのである。
【０１３６】
なお、この例では、時間ステップ毎の評価値（期待値）Ｑの差が十分小さくなったことで繰り返し演算が収束したと判断し、繰り返し演算（Ｓ５２〜Ｓ５９の処理ループ）を終了したが、これは一例に過ぎない。繰り返し演算の上限回数をあらかじめ定めておき、繰り返し演算が収束しなくても、その繰り返し演算の実行回数が上限回数に達した場合には、繰り返し演算を終了してもよい。この場合、繰り返し演算の終了時点での各パラメータＤｋ及びγｄｋを含んだ式(I)を、マルコフ連鎖の各クラスタｋを規定する式として用いるようにしてもよい。
【０１３７】
（ディリクレ事前分布を用いたマルコフ連鎖クラスタリング）
事前分布としてディリクレ分布を用いると、結合確率は以下に示すものとなる。
【数１５１】
0005895813.tif 000152
【０１３８】
なお、この式では、ディリクレ分布のパラメータを、それぞれ以下のように定めている。
【数１５２】
0005895813.tif 000153
【数１５３】
0005895813.tif 000154
【０１３９】
このように定めたことで、例えば、
【数１５４】
0005895813.tif 000155
が０であれば、起こりうるすべてのパターンの確率が均等となる（上記Bishopの著書のFigure 2.5参照）。
【０１４０】
ベイズ定理から、次式が得られる。
【数１５５】
0005895813.tif 000156
ここで、上述した結合確率、すなわち、
【数１５６】
0005895813.tif 000157
の対数をとると、次のようになる。
【数１５７】
0005895813.tif 000158
この結合確率の対数を用いて、期待値Ｑを次のように定義する。
【数１５８】
0005895813.tif 000159
なお、この式を得るにあたっては、次の関係を用いた。
【数１５９】
0005895813.tif 000160
ここで、
【数１６０】
0005895813.tif 000161
という制約の下で、
【数１６１】
0005895813.tif 000162
に関して期待値Ｑを最大化すると、次の関係式が得られる。
【数１６２】
0005895813.tif 000163
ここで、
【数１６３】
0005895813.tif 000164
である。
この関係式の導出は以下の通りである。
【数１６４】
0005895813.tif 000165
また、期待値Ｑを
【数１６５】
0005895813.tif 000166
という制約の下で、
【数１６６】
0005895813.tif 000167
について最大化することで、次の関係式が得られる。
【数１６７】
0005895813.tif 000168
【０１４１】
なお、学習用データ数Ｄがネットワークのノード数Ｎよりも十分に大きい場合には、式(6.5)の期待値Ｑを次のように近似できる。
【数１６８】
0005895813.tif 000169
この近似した期待値Ｑを、
【数１６９】
0005895813.tif 000170
という制約の下で、
【数１７０】
0005895813.tif 000171
について最大化することで、次の関係式が得られる。
【数１７１】
0005895813.tif 000172
また、期待値Ｑを、
【数１７２】
0005895813.tif 000173
という制約の下で、
【数１７３】
0005895813.tif 000174
について最大化すると、次の関係式が得られる。
【数１７４】
0005895813.tif 000175
【０１４２】
以上をまとめると、ディリクレ事前分布を用いる例では、学習用データｄに関するマルコフ連鎖は次式(I)（上述の式(6.7)、(6.8)と同じ）で表される。
【数１７５】
0005895813.tif 000176
ここで、
【数１７６】
0005895813.tif 000177
である。
【０１４３】
ディリクレ事前分布を用いる場合のクラスタリング処理の手順は、図４に例示したガウス事前分布を用いる場合の手順と同様でよい。
【０１４４】
すなわち、この手順では、図４のＳ５０に示すように、式(I)の右辺の各項に含まれる変数の値を仮決めする。また、遷移確率行列Ｔは、例えばページランクアルゴリズムの場合と同様の方法で、ネットワークのリンク構造等に基づいてあらかじめ求められているものとする。また、α及びβは、式(6.1)等に現れるディリクレ分布のパラメータであり、これらの値はユーザが指定しておく。
【０１４５】
仮決めした
【数１７７】
0005895813.tif 000178
により、式(I)の右辺の
【数１７８】
0005895813.tif 000179
が決まる（式(4.4a)、(4.4b)参照）。
【０１４６】
このように変数を仮決め（Ｓ５０）した後、上述した式(I)により
【数１７９】
0005895813.tif 000180
を計算する（Ｓ５２）。
次に、帰属度γｄｋを次式(II)（上述の式(6.2)参照）で計算する（Ｓ５４）。
【数１８０】
0005895813.tif 000181
次に、次の式（III)によりπｋｎｅｗを計算する（Ｓ５６）。
【数１８１】
0005895813.tif 000182
【０１４７】
なお、学習用データ数Ｄがネットワークのノード数Ｎよりも十分大きい場合は、式(I)、(III)の代わりに、式(6.11)、(6.12)を用いればよい。
【０１４８】
その他の処理ステップは、ガウス事前分布と同様でよい。
【０１４９】
ディリクレ事前分布を用いる例でも、図４の繰り返し処理が終了した時点の式(I)が、クラスタｋの部分的なマルコフ連鎖を表している。このように、図４に示した手順では、時間ステップを１つずつ進めながら式(I)〜(III)を繰り返し演算することで、(I)式中のパラメータＤｋ及びγｄｋが調整されていき、各クラスタｋの形が定まってくるのである。
【０１５０】
以上、マルコフ連鎖のクラスタリングの学習方式についていくつかの例を説明した。マルコフ連鎖のクラスタリングができれば、それはノードのクラスタリングもできたことを意味する。すなわち、マルコフ連鎖のクラスタリング結果を用いて、各クラスタｋ（部分マルコフ連鎖）の定常状態を求め、その定常状態において各ノードｎにエージェントが存在する確率を、そのノードｎのそのクラスタｋへの帰属度として求めることで、ノードのクラスタ分けができる。より詳しくは、例えば、これらの方式によりマルコフ連鎖のクラスタリング結果、すなわち図４の繰り返し処理が終了した時点の式(I)を用いて、ネットワーク上のノード群のクラスタリングを行ってもよい。
【０１５１】
この場合のノード群のクラスタリングは、実施形態のシステムにおけるノード群のクラスタリング（すなわち、式(V)の繰り返し演算により定常状態を求める方式）と同様の処理により行えばよい。
【０１５２】
すなわち、事前分布としてガウス分布、ディリクレ分布のいずれを用いる場合でも、図４の繰り返し処理が終了した時点の式(I)を、時間ステップを進めつつ繰り返し演算する。この繰り返しにより定常状態に達すると、その定常状態における各クラスタ番号ｋの活性ベクトル（前述の実施形態における式(VI)、すなわち帰属度ベクトル、と同じもの）を求める。この活性ベクトルの各成分、すなわち
【数１８２】
0005895813.tif 000183
は、「ノードｎのクラスタｋへの帰属度」を表す。すなわち、この値が大きいほど、ノードｎがクラスタｋに帰属する可能性は高い。このように帰属度ベクトルは、ネットワーク上の各ノードがクラスタｋに属する度合いの、ノード番号ｎに沿った分布を表す。これが、ノードのクラスタリング結果である。各ノードｎは、それぞれ帰属度ベクトルにおける当該ノードｎの成分である０以上１以下の数値で示される度合いで、各クラスタｋに属しているといえる。また、帰属度についての閾値をあらかじめ定め、各クラスタｋに対する帰属度がこの閾値以上であるノードを、そのクラスタｋに属するノードと判定してもよい。この場合、同じノードｎが、異なる複数のクラスタｋに属することもあり得る。
【０１５３】
なお、以上では、マルコフ連鎖のクラスタリングの学習のための学習用データとして、ユーザの検索履歴から求めた種ベクトルやネットワーク上の各ノードのリンク状態、ランダムウォーカーが存在するノードの観察結果（数９８参照）等の様々な例を挙げたが、この他にも次のような学習用データを用いてもよい。
【数１８３】
0005895813.tif 000184
ここで、
【数１８４】
0005895813.tif 000185
は遷移確率行列の成分である。すなわち、ｍ番目の学習用データ
【数１８５】
0005895813.tif 000186
は、ノードｍからネットワーク上の各ノードｎ（ｎ＝１，…，Ｎ）への遷移確率をそれぞれ第ｎ成分とするベクトルである。学習用データ数のＤがネットワークのノード数Ｎよりも十分大きいとするならば、これらＤ個の中で、
【数１８６】
0005895813.tif 000187
は
【数１８７】
0005895813.tif 000188
回登場すると考えられる。ただし、
【数１８８】
0005895813.tif 000189
は、別途事前に単独に計算されたマルコフ連鎖（式(3.2a)、(3.2b)）の定常状態
【数１８９】
0005895813.tif 000190
の第ｍ成分である。このとき、式(3.2b)においてｍが１からDまでの総和を求める必要はなく、重複を考慮すれば、ｍが１からNまでの総和を計算すれば十分である。
【０１５４】
以上、クラスタリングの別の例を説明した。例示したクラスタリング処理は、例えば、図３の装置構成におけるクラスタリング処理部１６で実行される。この場合、クラスタリング処理部１６は、ネットワーク情報記憶装置１０に記憶された隣接行列Ａnmの情報と、情報は学習用データ記憶装置１４に記憶された学習用データとを用いて、上述した処理（図４参照）を実行すればよい。
【０１５５】
また、以上では、事前分布としてガウス分布及びディリクレ分布を用いる例を説明したが、他の確率分布を事前分布として用いてもよい。
【０１５６】
以上に説明した「クラスタリングの別の例」によれば、（ノード数Nの2乗）×（クラスタ数K）で律速される計算時間でネットワークをクラスタリングできる。
【０１５７】
上記実施形態及び「クラスタリングの別の例」に示したクラスタリング方式では、ネットワークでリンクを辿ってノードからノードへ遷移していくエージェントが同一時点で当該ネットワークの各ノードに存在する確率をそれぞれ成分とする活性ベクトルｐについて、当該活性ベクトルの確率的時間発展を表すクラスタ毎の関係式（すなわち式(I)〜(III),
(IIIa),(IIIb),(IIIc)）を用いて、ある時刻における前記活性ベクトルを直前の時刻における前記活性ベクトルから計算する。このクラスタ毎の前記関係式は、ある時刻の活性ベクトルが、ネットワークのリンク構造に応じたマルコフ連鎖の遷移確率行列に従った直前の時刻の活性ベクトルの遷移結果、を中心とするあらかじめ定められた確率分布（例えばガウス分布、ディリクレ分布）に従うとし、学習用データが観測結果として得られた場合の活性ベクトルの尤度を最大化する（すなわち式(4.3)、(5.3)、(6.1)等に示される結合確率を最大化する）ように定められている。そして、図１及び図４に例示したように、クラスタ毎に、そのクラスタについての関係式を、時刻を順次進めながら繰り返し計算することで、関係式に含まれるパラメータを順次更新し、この繰り返し計算がある終了条件（例えば図１のＳ２０、図４のＳ５９）を満たしたときのパラメータを含んだ関係式を、当該クラスタを表現する式に決定する。
【０１５８】
以上に例示した検索システムは、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用ＬＳＩ(Large Scale Integration)、ＡＳＩＣ（Application Specific Integrated Circuit、特定用途向け集積回路）又はＦＰＧＡ（Field Programmable Gate Array）等のハードウエア回路として構成してもよい。
【符号の説明】
【０１５９】
１０  ネットワーク情報記憶装置、１２  クローラー、１４  学習用データ記憶装置、１６  クラスタリング処理部、１８  クラスタリング結果記憶装置、２０  検索処理部。
【図１】
0005895813.tif 000191
【図２】
0005895813.tif 000192
【図３】
0005895813.tif 000193
【図４】
0005895813.tif 000194