(57)【要約】【課題】一般のＷｅｂページに加え、ブログに対しても適切な検索用インデックスを作成する。【解決手段】クエリログから相関の強いクエリ同士をグループ化してクラスタリングを行う工程と、クラスタのターム集合に対してラベル付けを行う工程と、各クラスタのタームに基づいてルートセットを作成する工程と、ルートセットに含まれる各ノードに基づいてベースセットを作成する工程と、ベースセットからＨＩＴＳアルゴリズムにより最大固有値に対応する固有ベクトルおよび最大固有値以外の固有値に対応する固有ベクトルに基づいてコミュニティ抽出を行う工程と、コミュニティ抽出結果のオーソリティおよびハブからフレーズの抽出を行う工程と、上記クラスタ、ラベル、タームおよびフレーズに基づいてディレクトリを作成する工程と、ディレクトリに基づいて検索用のインデックスを作成する工程とを備える。【選択図】図４
2008191877.tif 000002
【特許請求の範囲】
【請求項１】
対象となる所定期間のクエリログから相関の強いクエリ同士をグループ化してクラスタリングを行うクラスタリング工程と、
上記クラスタリングにより得られたターム集合に対してラベル付けを行うラベリング工程と、
ラベルの付された各クラスタのタームに基づいて当該タームを含むクラスタ毎のノードの集合であるルートセットを作成するルートセット作成工程と、
作成されたルートセットに含まれる各ノードに基づいて当該ノードのクラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成するベースセット作成工程と、
作成されたベースセットからＨＩＴＳアルゴリズムにより最大固有値に対応する固有ベクトルおよび最大固有値以外の固有値に対応する固有ベクトルに基づいてコミュニティ抽出を行うコミュニティ抽出工程と、
コミュニティ抽出結果の上位序列の所定数のオーソリティおよびハブからフレーズの抽出を行うフレーズ抽出工程と、
上記クラスタ、ラベル、タームおよびフレーズに基づいて各コミュニティ内のオーソリティおよびハブの位置付けを表すディレクトリを作成するディレクトリ作成工程と、
作成されたディレクトリに基づいて検索用のインデックスを作成するインデックス作成工程とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項２】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記クラスタリング工程は、
上記クエリログからクエリと共起語の発生頻度を表すクエリ／共起語の行列を作成する工程と、
作成されたクエリ／共起語の行列から検索ターム間の相関を表す共起行列を作成する工程と、
作成された共起行列から相関の強いクエリ同士をグループ化してクラスタリングを行う工程とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項３】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記ラベリング工程は、カテゴリデータを用いてラベルを付すことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項４】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記ルートセット作成工程は、各クラスタのタームにより、キーワードと対応するノードの対応を表すキーワード／ＵＲＬテーブルを検索してクラスタ毎のノードの集合であるルートセットを作成することを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項５】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記ベースセット作成工程は、作成されたルートセットに含まれる各ノードにつき、ノードとリンクの相手方のノードの対応を表すＵＲＬ／リンクテーブルを検索することで、クラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成することを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項６】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記コミュニティ抽出工程は、最大固有値に対応する固有ベクトルの計算と最大固有値以外の固有値に対応する固有ベクトルの計算とを並列的に行うことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項７】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記コミュニティ抽出工程の最大固有値に対応する固有ベクトルの計算は、
オーソリティの重みベクトルとハブの重みベクトルの両者の要素を「１」とする初期化の工程と、
係数行列Ｅとオーソリティの重みベクトルの乗算結果のハブの重みベクトルへの代入、ハブの重みベクトルの絶対値の計算、ハブの重みベクトルをハブの重みベクトルの絶対値で除算した結果のハブの重みベクトルへの代入、係数行列ＥＴとハブの重みベクトルの乗算結果のオーソリティの重みベクトルへの代入、オーソリティの重みベクトルの絶対値の計算、オーソリティの重みベクトルをオーソリティの重みベクトルの絶対値で除算した結果のオーソリティの重みベクトルへの代入を順次に行い、値が収束まで繰り返す工程とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項８】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記コミュニティ抽出工程の最大固有値以外の固有値に対応する固有ベクトルの計算は、子空間反復法により計算を行うことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項９】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記フレーズ抽出工程は、抽出された上位所定数のオーソリティおよびハブのノードにつきフレーズ辞書を用いて特徴的なフレーズを抽出することを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項１０】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記ディレクトリ作成工程は、
第１階層にラベルを設定する工程と、
第２階層に各タームを設定する工程と、
第３階層にフレーズ抽出で得られたフレーズを設定する工程と、
第４階層に、対応するオーソリティのうち最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に設定する工程と、
第５階層に、ハブのうち最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に設定する工程とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項１１】
請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、
上記インデックス作成工程は、
第１階層にコミュニティを設定する工程と、
第２階層に大キーワードを設定する工程と、
第３階層に小キーワードを設定する工程と、
上記第３階層に合致するノードのＵＲＬとオーソリティ／ハブの区別を対応付けて設定する工程とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成方法。
【請求項１２】
対象となる所定期間のクエリログから相関の強いクエリ同士をグループ化してクラスタリングを行うクラスタリング手段と、
上記クラスタリングにより得られたターム集合に対してラベル付けを行うラベリング手段と、
ラベルの付された各クラスタのタームに基づいて当該タームを含むクラスタ毎のノードの集合であるルートセットを作成するルートセット作成手段と、
作成されたルートセットに含まれる各ノードに基づいて当該ノードのクラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成するベースセット作成手段と、
作成されたベースセットからＨＩＴＳアルゴリズムにより最大固有値に対応する固有ベクトルおよび最大固有値以外の固有値に対応する固有ベクトルに基づいてコミュニティ抽出を行うコミュニティ抽出手段と、
コミュニティ抽出結果の上位序列の所定数のオーソリティおよびハブからフレーズの抽出を行うフレーズ抽出手段と、
上記クラスタ、ラベル、タームおよびフレーズに基づいて各コミュニティ内のオーソリティおよびハブの位置付けを表すディレクトリを作成するディレクトリ作成手段と、
作成されたディレクトリに基づいて検索用のインデックスを作成するインデックス作成手段とを備えたことを特徴とするコミュニティ抽出による検索用インデックス作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等のネットワーク上に存在するＷｅｂサイト、ブログ（Blog、Web Log：日記風のサイト）等の多数のノードの中から所望の情報を豊富に掲載するノードを提示する技術に関する。
【背景技術】
【０００２】
インターネット上の膨大な情報の中から所望の情報を効率的に閲覧するために検索エンジンが用いられている。
【０００３】
これらの検索エンジンでは、一般に、各ノードのページに含まれるキーワードを予めインデックス化しておき、そのインデックスに対して検索クエリを実行することで、指定した検索タームを含むノードの一覧を取得し、その一覧を経由してノードへのアクセスを行うようになっている。
【０００４】
しかしながら、単に所定のキーワードが含まれるか否かという観点からのノードの選定では、同じキーワードが用いられているものであっても所望するものとは全く異なるトピック（話題）に関するノードである可能性も低くなく、ユーザが満足する結果が得られないことも多い。
【０００５】
このような問題に対し、共通のトピックを扱うノードの集合であるコミュニティに着目することで検索精度を高められるのではないかという模索がなされている。コミュニティを特定することができれば、そのトピックから外れたノードを除外することができ、検索精度を高めることが可能になる。
【０００６】
特定のトピックに関するＷｅｂページ集合を抽出する手法としてＨＩＴＳ（Hyperlink Induced Topic Search）アルゴリズムが存在する（非特許文献１）。ＨＩＴＳアルゴリズムは、検索クエリ（トピック）に関して、トピックに関する情報が豊富なページをオーソリティ（authority）、オーソリティへのリンクが豊富なページをハブ（hub）と定義し、それらの集合をコミュニティとして抽出し、Ｗｅｂページの関係性を把握する手法である。
【０００７】
しかし、ＨＩＴＳアルゴリズムには、トピックドリフト（topic drift）と呼ばれる問題点が指摘されている。これは、個人のリンク集のページにおいては複数のトピックのリンク集を掲載しているものが多く、ハブの中に目的とは異なるトピックのリンクが含まれている場合、それらのリンク先のページのオーソリティとしての値が高くなってしまい、目的とするトピックと関連のないページがオーソリティと認識されてしまう現象である。図１はトピックドリフトの例を示す図であり、リンク集のＷｅｂページＰ１がトピック「ラーメン」についてのＷｅｂページＰ２とトピック「サッカー」についてのＷｅｂページＰ３にリンクしているものとすると、本来はＷｅｂページＰ２とＷｅｂページＰ１が「ラーメン」コミュニティＣ１と認識され、ＷｅｂページＰ３とＷｅｂページＰ１が「サッカー」コミュニティＣ２と認識されるべきところ、一つのコミュニティＣ３と認識されてしまうことになる。
【０００８】
このようなトピックドリフトの問題を改善する試みとして、いくつかの手法が提案されている。
【０００９】
非特許文献２では、ハブに含まれているリンク集の中にＤＯＭ（Document Object Model）を導入することにより、ハブを細分化することでＨＩＴＳアルゴリズムを改良している。
【００１０】
また、非特許文献３では、センタ（centers）とファン（fans）という概念を用い、あるトピックに対してセンタとして複数のＵＲＬ（Uniform Resource Locator）を与え、それらのＵＲＬ全てにリンクするページをファンとして抽出する。センタに含まれるページをファンの多数からリンクされるものへと更新処理を繰り返すことにより、トピックにおける中心的なページ集合を求めている。
【００１１】
なお、上述のようにＷｅｂ全体を対象としてリンク構造を解析してページ集合を抽出する研究は行われてきたが、近年爆発的に普及しているブログの特性に着目して行われた研究は存在しない。
【非特許文献１】J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999).
【非特許文献２】Integrating the Document Object Model with Hyperlinks for Enhanced Topic Distillation and Information Extraction Proc. of the 10th International WWW conference, pp.211-220, 2001
【非特許文献３】「ハイパーリンクのグラフ構造に基づくＷｅｂコミュニティの洗練」村田 剛志 人工知能学会誌, Vol.17, No.3, pp.322-329, 2002.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
昨今のブログの爆発的な普及によりブログに対する検索需要も増大してきているが、上述したようにブログの特性に着目して行われた研究は存在せず、新たな手法が要望されている。すなわち、ブログは従来のＷｅｂサイトとは異なり、以下に説明するような特性があり、ＨＩＴＳアルゴリズムをそのまま適用すると多くのトピックにおいてトピックドリフトと同様の問題が発生し、目的に合ったコミュニティを抽出することが難しい。
【００１３】
（１）マルチトピックス（Multi-topics）性
ブログにおいては、一つのブログ記事（エントリ）に複数のトピック（マルチトピックス）が含まれる現象がよく見られる。このようなマルチトピックスがあると、前述したトピックドリフトと同様の問題が発生する。図２はブログ記事のマルチトピックスの例を示す図であり、ブログＢ１１のトピック「ラーメン」についてブログＢ１２からリンクし、ブログＢ１１のトピック「サッカー」についてブログＢ１３からリンクしているものとすると、本来はブログＢ１１とブログＢ１２が「ラーメン」コミュニティＣ１１と認識され、ブログＢ１１とブログＢ１３が「サッカー」コミュニティＣ１２と認識されるべきところ、一つのコミュニティＣ１３と認識されてしまうことになる。
【００１４】
このように、同じブログに対するリンク元が異なるコミュニティに属する可能性があり得るため、リンク元のリンク意図を識別して異なるコミュニティに属するのか否かの見分けが必要となる。ブログでもリンク（inbound links、outbound links）およびトラックバックによってＷｅｂページと同様に巨大なグラフを構築しており、Ｗｅｂページと比較してコミュニティの性質はより顕著となっているが、マルチトピックス性に起因して正確なコミュニティの抽出が妨げられる。
【００１５】
（２）エントリ依存性
ブログではエントリ毎にトピックが異なることが多く、一般的なサイトを単位とする手法では正確にコミュニティを抽出することができない。
【００１６】
（３）時効性
ブログのコミュニティは短期間のうちに消滅したり新たに発生したりすることが多く、ブログないしコミュニティを特徴付けるタームも同様に短期間のうちに変化していく。従って、これらの変化に追随できる仕組としなければならない。
【００１７】
（４）情報の散在、非組織化
ブログでは通常のＷｅｂページと比較して情報が散在しており、組織化されていない。従って、単にコミュニティ単位にブログをまとめるだけでなく、階層化された見通しのよいものとしなければならない。
【００１８】
（５）トラックバックリンクの存在
ブログでは通常のリンクに加えトラックバックリンクが存在し、その取り扱いをいかなるものにするか決定しなければならない。
【００１９】
このように、ブログ記事のコミュニティ性が顕在であるにもかかわらず、このコミュニティを中心に整理するブログ検索エンジンはまだ存在しない。
【００２０】
本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、一般のＷｅｂページに加え、ブログに対してもコミュニティ中心に階層的に整理した適切な検索用インデックスを作成することのできるコミュニティ抽出による検索用インデックス作成方法およびその装置を提供することにある。
【課題を解決するための手段】
【００２１】
上記の課題を解決するため、本発明にあっては、請求項１に記載されるように、対象となる所定期間のクエリログから相関の強いクエリ同士をグループ化してクラスタリングを行うクラスタリング工程と、上記クラスタリングにより得られたターム集合に対してラベル付けを行うラベリング工程と、ラベルの付された各クラスタのタームに基づいて当該タームを含むクラスタ毎のノードの集合であるルートセットを作成するルートセット作成工程と、作成されたルートセットに含まれる各ノードに基づいて当該ノードのクラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成するベースセット作成工程と、作成されたベースセットからＨＩＴＳアルゴリズムにより最大固有値に対応する固有ベクトルおよび最大固有値以外の固有値に対応する固有ベクトルに基づいてコミュニティ抽出を行うコミュニティ抽出工程と、コミュニティ抽出結果の上位序列の所定数のオーソリティおよびハブからフレーズの抽出を行うフレーズ抽出工程と、上記クラスタ、ラベル、タームおよびフレーズに基づいて各コミュニティ内のオーソリティおよびハブの位置付けを表すディレクトリを作成するディレクトリ作成工程と、作成されたディレクトリに基づいて検索用のインデックスを作成するインデックス作成工程とを備えるコミュニティ抽出による検索用インデックス作成方法を要旨としている。
【００２２】
また、請求項２に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記クラスタリング工程は、上記クエリログからクエリと共起語の発生頻度を表すクエリ／共起語の行列を作成する工程と、作成されたクエリ／共起語の行列から検索ターム間の相関を表す共起行列を作成する工程と、作成された共起行列から相関の強いクエリ同士をグループ化してクラスタリングを行う工程とを備えるようにすることができる。
【００２３】
また、請求項３に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記ラベリング工程は、カテゴリデータを用いてラベルを付すようにすることができる。
【００２４】
また、請求項４に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記ルートセット作成工程は、各クラスタのタームにより、キーワードと対応するノードの対応を表すキーワード／ＵＲＬテーブルを検索してクラスタ毎のノードの集合であるルートセットを作成するようにすることができる。
【００２５】
また、請求項５に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記ベースセット作成工程は、作成されたルートセットに含まれる各ノードにつき、ノードとリンクの相手方のノードの対応を表すＵＲＬ／リンクテーブルを検索することで、クラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成するようにすることができる。
【００２６】
また、請求項６に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記コミュニティ抽出工程は、最大固有値に対応する固有ベクトルの計算と最大固有値以外の固有値に対応する固有ベクトルの計算とを並列的に行うようにすることができる。
【００２７】
また、請求項７に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記コミュニティ抽出工程の最大固有値に対応する固有ベクトルの計算は、オーソリティの重みベクトルとハブの重みベクトルの両者の要素を「１」とする初期化の工程と、係数行列Ｅとオーソリティの重みベクトルの乗算結果のハブの重みベクトルへの代入、ハブの重みベクトルの絶対値の計算、ハブの重みベクトルをハブの重みベクトルの絶対値で除算した結果のハブの重みベクトルへの代入、係数行列ＥＴとハブの重みベクトルの乗算結果のオーソリティの重みベクトルへの代入、オーソリティの重みベクトルの絶対値の計算、オーソリティの重みベクトルをオーソリティの重みベクトルの絶対値で除算した結果のオーソリティの重みベクトルへの代入を順次に行い、値が収束まで繰り返す工程とを備えるようにすることができる。
【００２８】
また、請求項８に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記コミュニティ抽出工程の最大固有値以外の固有値に対応する固有ベクトルの計算は、子空間反復法により計算を行うようにすることができる。
【００２９】
また、請求項９に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記フレーズ抽出工程は、抽出された上位所定数のオーソリティおよびハブのノードにつきフレーズ辞書を用いて特徴的なフレーズを抽出するようにすることができる。
【００３０】
また、請求項１０に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記ディレクトリ作成工程は、第１階層にラベルを設定する工程と、第２階層に各タームを設定する工程と、第３階層にフレーズ抽出で得られたフレーズを設定する工程と、第４階層に、対応するオーソリティのうち最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に設定する工程と、第５階層に、ハブのうち最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に設定する工程とを備えるようにすることができる。
【００３１】
また、請求項１１に記載されるように、請求項１に記載のコミュニティ抽出による検索用インデックス作成方法において、上記インデックス作成工程は、第１階層にコミュニティを設定する工程と、第２階層に大キーワードを設定する工程と、第３階層に小キーワードを設定する工程と、上記第３階層に合致するノードのＵＲＬとオーソリティ／ハブの区別を対応付けて設定する工程とを備えるようにすることができる。
【００３２】
また、請求項１２に記載されるように、コミュニティ抽出による検索用インデックス作成装置として構成することができる。
【発明の効果】
【００３３】
本発明のコミュニティ抽出による検索用インデックス作成方法およびその装置にあっては、一般のＷｅｂページに加え、ブログに対しても適切な検索用インデックスを作成することができる。
【発明を実施するための最良の形態】
【００３４】
以下、本発明の好適な実施形態につき説明する。
【００３５】
<システム構成>
図３は本発明の一実施形態にかかるシステムの構成例を示す図である。
【００３６】
図３において、本システムは、コミュニティ抽出の対象となるタームのクラスタリングを行うクラスタリングサーバ１と、クラスタリングされたタームに基づいてコミュニティの抽出を行い、検索用インデックスを作成するコミュニティ抽出サーバ２と、作成された検索用インデックスに基づいてブログの検索を行うブログ検索サーバ３と、インターネット等のネットワーク４を介してブログ検索サーバ３にアクセスして検索を要求し検索結果を取得するユーザ端末５と、処理に用いられる各種のデータを保持するデータベース類１０１〜１０６とを備えている。
【００３７】
クラスタリングサーバ１は、ブログ検索サーバ３から所定期間内の検索内容を示すクエリ（検索ターム）ログを収集してクエリログＤＢ１０１に格納するクエリログ収集部１１と、クエリログ（ＰＶ（Page View）数等による上位の所定数を対象）からクエリと共起語（主たる検索タームであるクエリに付随する検索ターム）の発生頻度を表すクエリ／共起語の行列を経て検索ターム間の相関を表す共起行列を作成する共起行列作成部１２と、共起行列から相関の強いクエリ同士をグループ化してクラスタリングを行い、結果をターム集合としてターム集合ＤＢ１０２に格納するクラスタリング処理部１３と、クラスタリングされた各クラスタのターム集合に対してカテゴリＤＢ１０３のカテゴリデータを用いてラベルを付すラベリング部１４とを備えている。
【００３８】
コミュニティ抽出サーバ２は、コミュニティ抽出のための事前処理として、対象範囲内の全ブログを想定されるキーワードにより検索し、キーワードと対応するノード（ブログエントリのＵＲＬ）の対応を表すキーワード／ＵＲＬテーブルを作成するとともに、各ノードの書誌情報を記録したＵＲＬ／書誌情報テーブルを作成してブログＤＢ１０４に格納するブログ検索部２１と、各ブログのリンク（そのノードから他のノードを参照するアウトバウンドリンク、そのノードに対するトラックバックリンク、そのノードを参照してくるインバウンドリンク）を抽出し、ノードとリンクの相手方のノードの対応を表すＵＲＬ／リンクテーブルを作成してブログＤＢ１０４に格納するリンク取得部２２とを備えている。
【００３９】
コミュニティ抽出サーバ２は、更に、ターム集合ＤＢ１０２の各クラスタのタームによりブログＤＢ１０４のキーワード／ＵＲＬテーブルを検索してクラスタ毎のノードの集合であるルートセットを作成するルートセット作成部２３と、作成されたルートセットに含まれる各ノードにつきブログＤＢ１０４のＵＲＬ／リンクテーブルを検索することで、クラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成するベースセット作成部２４と、作成されたベースセットからＨＩＴＳアルゴリズムによりコミュニティ抽出を行うコミュニティ抽出部（ＨＩＴＳ計算部）２５と、抽出された上位所定数のオーソリティおよびハブのノードにつき、フレーズ辞書１０５およびＵＲＬ／書誌情報テーブルを用いて特徴的なフレーズを抽出するフレーズ抽出部２６と、クラスタ、ラベル、ターム（ターム集合に含まれる各ターム）、フレーズに基づいて各コミュニティ内のオーソリティおよびハブの位置付けを表すディレクトリを作成するディレクトリ作成部２７と、作成されたディレクトリに基づいて検索用のインデックスを作成してインデックスＤＢ１０６に格納するインデックス作成部２８とを備えている。
【００４０】
<動作>
図４は上記の実施形態の全体的な処理の流れを示す図である。
【００４１】
図４において、クラスタリングサーバ１のクエリログ収集部１１はブログ検索サーバ３から対象となる所定期間のクエリログを収集し、クエリログＤＢ１０１に格納する（ステップＳ１）。図５はクエリログの例を示す図であり、主たる検索タームであるクエリと、その検索に際して同時に設定された第２、第３・・・の検索タームである共起語とが、ＰＶ数を伴って記録されたものとなっている。なお、順位はクエリのＰＶ数に応じて付されており、上位所定数のデータを後続の処理の対象とする。また、セッション情報やカテゴリ関連付けの情報をクエリの属性として付加してもよい。
【００４２】
図４に戻り、これと並行して、コミュニティ抽出サーバ２のブログ検索部２１はブログの検索を行ってキーワード／ＵＲＬテーブルおよびＵＲＬ／書誌情報テーブルを作成するとともに、リンク取得部２２は各ブログのリンクを抽出してＵＲＬ／リンクテーブルを作成し、これらをブログＤＢ１０４に格納する（ステップＳ２）。図６はキーワード／ＵＲＬテーブルの例を示す図であり、所定のキーワードとそのキーワードを多く含むブログのＵＲＬとが対応付けられたものとなっている。図７はＵＲＬ／書誌情報テーブルの例を示す図であり、ノードのＵＲＬ毎にタイトル、作者、要約、更新日等が記録されたものとなっている。図８はＵＲＬ／リンクテーブルの例を示す図であり、ブログのＵＲＬに対し、本文と、アウトバンドＵＲＬと、トラックバックＵＲＬと、インバウンドＵＲＬとが対応付けられたものとなっている。
【００４３】
図４に戻り、クラスタリングサーバ１の共起行列作成部１２はクエリログＤＢ１０１からクエリログを取得し、クエリ／共起語の行列Ｍを作成する（ステップＳ３）。図９はクエリ／共起語の行列Ｍの例を示す図であり、複数のクエリと複数の共起語の組み合わせに対するＰＶ数が記録されたものとなっている。
【００４４】
図４に戻り、クラスタリングサーバ１の共起行列作成部１２はクエリ／共起語の行列Ｍから
Ｗ＝ＭＭＴ  （ＭＴはＭの転置行列）
で計算される共起行列Ｗを作成する（ステップＳ４）。図１０は共起行列Ｗの例を示す図であり、複数のクエリ同士の組み合わせに対する相関値ｗが記録されたものとなっている。
【００４５】
図４に戻り、クラスタリングサーバ１のクラスタリング処理部１３は共起行列Ｗの各相関値ｗから、相関の強いクエリ同士をグループ化してクラスタリングを行い、結果をターム集合としてターム集合ＤＢ１０２に格納する（ステップＳ５）。クラスタ内のタームの数（ｍ）には上限を設ける（例：ｍ＝６）。図１１はターム集合の例を示す図であり、（ａ）は各クエリのクラスタリングの様子を概念的に示したもの、（ｂ）はターム集合のデータ形式の例である。ここでは、クエリ「クリスマス」とクエリ「イルミネーション」の相関が強いものとして、これらが同じクラスタ＃１に入れられたものとしている。
【００４６】
図４に戻り、クラスタリングサーバ１のラベリング部１４はターム集合ＤＢ１０２に格納されたターム集合に対してカテゴリＤＢ１０３のカテゴリデータを用いてラベルを付し、ターム集合ＤＢ１０２に格納する（ステップＳ６）。図１２はカテゴリデータの例を示す図であり、クラスタ＃１のターム「クリスマス」「イルミネーション」の上位階層（全てのタームより上位である直近の階層）の「祝日、記念日、年中行事」がラベルとして選ばれたことを示している。図１３はターム集合（ラベル付）の例を示す図であり、（ａ）は各クエリのラベリングの様子を概念的に示したもの、（ｂ）はラベルが付されたターム集合のデータ形式の例である。ここでは、「クリスマス」「イルミネーション」のクラスタ＃１にラベル「祝日、記念日、年中行事」が付され、「ラーメン○○館」のクラスタ＃２にラベル「フードテーマパーク」が付され、「アジア大会」のクラスタ＃３にラベル「国際大会」が付され、「焼酎」のクラスタ＃４にラベル「アルコール」が付されたものとしている。
【００４７】
図４に戻り、コミュニティ抽出サーバ２のルートセット作成部２３はターム集合ＤＢ１０２のラベルの付された各クラスタのタームによりブログＤＢ１０４のキーワード／ＵＲＬテーブルを検索してクラスタ毎の出現頻度上位のノード（ノード数ｎは例えばｎ＝１０）の集合（ｍ個のタームについてｎ個のノードとなるため最大でｍ×ｎ個のノード）であるルートセットを作成する（ステップＳ７）。キーワード／ＵＲＬテーブルの例は既に図６に示した。図１４は作成されたルートセットの例を示す図であり、各クラスタに対応するノードのＵＲＬが記録されたものとなっている。
【００４８】
図４に戻り、コミュニティ抽出サーバ２のベースセット作成部２４は作成されたルートセットに含まれる各ノードにつきブログＤＢ１０４のＵＲＬ／リンクテーブルを検索することで、クラスタ毎のリンク先とリンク元のノードの集合であるベースセットを作成する（ステップＳ８）。なお、トラックバックリンクはインバウンドリンクとして扱う。ＵＲＬ／リンクテーブルの例は既に図８に示した。図１５は作成されたベースセットの例を示す図であり、各クラスタに対応するリンク先のＵＲＬとリンク元のＵＲＬとが記録されたものとなっている。
【００４９】
図４に戻り、コミュニティ抽出サーバ２のコミュニティ抽出部２５は作成されたベースセットからＨＩＴＳアルゴリズムによりコミュニティ抽出を行う（ステップＳ９）。以下、コミュニティ抽出の処理につき詳細に説明する。
【００５０】
図１６はコミュニティ抽出の概要を示す図であり、説明を簡便にするためにノードが６個の場合を示している。実際には、対象とするブログの範囲にもよるが、本出願人の運営するサービスで検索対象とするノード（ブログエントリ）数は数千万〜数億に達する。
【００５１】
図１６において、各ノードＮ１〜Ｎ６はオーソリティの重みａとハブの重みｈとが対になって、トピック（各クラスタ毎のテーマとなる話題）の数だけａ、ｈの対が存在する。なお、ａ、ｈのサブスクリプト（下付数字）は対応するノードの番号を示し、スーパースクリプト（上付数字）はトピックの番号を示している。
【００５２】
また、図１６ではあるトピックにつき、各ノードＮ１〜Ｎ６に矢印付の線で示されるようなリンク関係（矢印の先がリンク先、反対側がリンク元）があることがベースセットで示されているものとする。
【００５３】
オーソリティの重みａはそのノードにリンクしてくるハブの重みの総和と定義されるため、図１６の場合のあるトピックについてのオーソリティの重みａ１〜ａ６は図１７（ａ）に示すようになり、係数部分を行列ＥＴと置けば、ハブの重みベクトルに左から行列ＥＴを乗算したものがオーソリティの重みベクトルとなる。
【００５４】
同様に、ハブの重みｈはそのリンク先のノードのオーソリティの重みの総和と定義されるため、図１６の場合のあるトピックについてのハブの重みｈ１〜ｈ６は図１７（ｂ）に示すようになり、係数部分は行列Ｅとなり、オーソリティの重みベクトルに左から行列Ｅを乗算したものがハブの重みベクトルとなる。
【００５５】
これらのオーソリティおよびハブの重みのベクトル式を相互に代入することにより、図１７（ｃ）に示すように、オーソリティの重みベクトルは自己に左側から行列ＥＴＥを乗算したものとなり、ハブの重みベクトルは自己に左側から行列ＥＥＴを乗算したものとなる。従って、オーソリティおよびハブの重みベクトルを求めることは、行列ＥＴＥ、ＥＥＴの固有値に対応する固有ベクトルを求めることにほかならない。ただし、次元が多い場合は公式等から即座に固有値および固有ベクトルを求めることはできず、反復した数値計算が必要になる。
【００５６】
従来のＨＩＴＳアルゴリズムの研究においては、各Ｗｅｂサイトについて１つのトピックにおけるオーソリティ−ハブ関係を抽出するために、基本固有ベクトル値のみを用いていたが、本発明においては、ブログの特徴に鑑み、各エントリについて複数のトピックにおけるオーソリティ−ハブ関係を抽出するため、基本固有ベクトル値と合わせて、その他の複数の固有ベクトル値についても計算を行うこととしている。
【００５７】
図１８はコミュニティ抽出のための固有ベクトルの計算処理の例を示すフローチャートである。
【００５８】
図１８において、処理を開始すると（ステップＳ１０１）、最大固有値に対応する固有ベクトルの計算（ステップＳ１０２）と最大固有値以外の固有値に対応する固有ベクトルの計算（ステップＳ１０７）とを並列的に行い、両者の完了をもって処理を終了する（ステップＳ１１３）。
【００５９】
最大固有値に対応する固有ベクトルの計算（ステップＳ１０２）では、初期化処理として、オーソリティの重みベクトルとハブの重みベクトルの両者の全要素を「１」とする（ステップＳ１０３）。
【００６０】
次いで、行列Ｅとオーソリティの重みベクトルの乗算結果のハブの重みベクトルへの代入、ハブの重みベクトルの絶対値の計算、ハブの重みベクトルをハブの重みベクトルの絶対値で除算した結果のハブの重みベクトルへの代入、行列ＥＴとハブの重みベクトルの乗算結果のオーソリティの重みベクトルへの代入、オーソリティの重みベクトルの絶対値の計算、オーソリティの重みベクトルをオーソリティの重みベクトルの絶対値で除算した結果のオーソリティの重みベクトルへの代入を順次に行う（ステップＳ１０４）。
【００６１】
そして、値が収束したか否か判断し（ステップＳ１０５）、収束していない場合は演算処理（ステップＳ１０４）を繰り返し、収束した場合はその時点でのオーソリティの重みベクトルとハブの重みベクトルの要素を大小の序列をもって出力する（ステップＳ１０６）。
【００６２】
一方、最大固有値以外の固有値に対応する固有ベクトルの計算（ステップＳ１０７）では、子空間反復法（Subspace Iteration）により計算を行う。
【００６３】
ｋ番目までの固有値を求めるものとすると、Ｇ＝ＥＴＥで表される行列Ｇを計算するとともに、行列Ｇのｋ列までの部分行列Ａを求める（ステップＳ１０８）。
【００６４】
次いで、行列Ｇと行列Ａの乗算結果を行列Ａに代入する（ステップＳ１０９）。
【００６５】
次いで、変数ｉを１からｋまで変化させ、その都度に行列Ａのｉ列について図示の演算結果を順次に代入する（ステップＳ１１０）。これは「Gram-Schmidt Orthonormalization」に基づいている。
【００６６】
そして、値が収束したか否か判断し（ステップＳ１１１）、収束していない場合は演算処理（ステップＳ１０９）から処理を繰り返し、収束した場合は、部分行列Ａの各列は行列Ｇのｋ番目までの固有値に対応した固有ベクトルとなり、固有値の順番毎に、その時点でのオーソリティの重みベクトルとハブの重みベクトルの要素を大小の序列をもって出力する（ステップＳ１１２）。
【００６７】
図１９は最大固有値に対応する固有ベクトルの演算処理（ステップＳ１０４）の１回目の計算例を示し、図２０は２回目の計算例を示しており、同様の計算を繰り返すことにより所定の値に収束していく。
【００６８】
図２１は最大固有値以外の固有値に対応する固有ベクトルの演算処理（ステップＳ１０８）の計算例を示し、図２２（ａ）は演算処理（ステップＳ１０９）の計算例を示し、図２２（ｂ）は演算処理（ステップＳ１１０）の計算例を示し、図２２と同様の計算を繰り返すことにより所定の値に収束していく。
【００６９】
図２３はコミュニティ抽出結果の例を示す図であり、第１、第２、・・・のクラスタ（トピック）についてのオーソリティおよびハブの序列が出力され、それぞれに最大固有値に対応するオーソリティおよびハブの序列と、最大固有値以外の固有値に対応するオーソリティおよびハブの序列とが含まれる。ノードが複数のコミュニティに属する場合には異なるオーソリティの重みおよびハブの重みを持つことから、コミュニティを仕分けることができ、それぞれのコミュニティ内のオーソリティおよびハブを見つけることもできる。ブログにおいては、各エントリが、あるトピックについてはオーソリティとなり、あるトピックについてはハブになることがある。
【００７０】
図４に戻り、コミュニティ抽出サーバ２のフレーズ抽出部２６はコミュニティ抽出結果の上位序列の所定数のオーソリティおよびハブにつき、フレーズ辞書１０５およびＵＲＬ／書誌情報テーブルを用いてキーとなるフレーズの抽出を行い、ディレクトリ作成部２７はクラスタ、ラベル、ターム（ターム集合に含まれる各ターム）、フレーズに基づいて各コミュニティ内のオーソリティおよびハブの位置付けを表すディレクトリを作成し、インデックス作成部２８は作成されたディレクトリに基づいて検索用のインデックスを作成し、インデックスＤＢ１０６に格納する（ステップＳ１０）。
【００７１】
図２４はコミュニティのディレクトリ構造の例を示す図であり、図１３のクラスタ＃１についての例であるが、ラベル「祝日、記念日、年中行事」を第１階層にして、第２階層にターム「クリスマス」「イルミネーション」が入り、「クリスマス」の下の第３階層にはフレーズ抽出で得られた「プレゼント」「ディナー」等が入り、「イルミネーション」の下の第３階層にはフレーズ抽出で得られた「クリスマス」「表参道」等が入り、それぞれの第３階層の下の第４階層には対応するオーソリティが最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に入り、その下の第５階層にハブが最大固有値に対応するもの、最大固有値以外の固有値に対応するものの順に入る。なお、オーソリティ直前までの階層を３階層としているが、検索時の使い勝手等を考慮して階層を任意に増減することができる。
【００７２】
図２５はインデックスデータの例を示す図であり、第１階層をコミュニティとし、第２階層を大キーワードとし、第３階層を小キーワードとし、それらに合致するノードのＵＲＬとオーソリティ／ハブの区別が対応付けられている。
【００７３】
ブログ検索サーバ３（図３）はユーザ端末５からネットワーク４を介して検索要求を受け付けると、インデックスＤＢ１０６の検索用のインデックスに基づいて検索を行い、検索結果をユーザ端末５に返す。
【００７４】
<総括>
以上説明したように、本発明の実施形態にあっては、次のような利点がある。
【００７５】
（１）複数の固有ベクトルを利用することで、リンク先のエントリに複数のトピックが存在する場合でも、ブログの複数トピックに対応するコミュニティを見つけ出すことができる。しかも、リンク構造分析のみに着目してコミュニティをトピックごとに整理し階層化することができる。
【００７６】
（２）ブログのサイト単位ではなくエントリ単位にコミュニティの抽出を行うため、エントリ毎にトピックが異なる場合にも精度の高いコミュニティ抽出を行うことができる。
【００７７】
（３）ブログ検索のクエリログを利用して随時にオフライン（offline）処理を行い、常にランキング上位の検索クエリを利用することで、話題性のあるコミュニティをつかめ、新生や消滅するコミュニティを対象に絞り込むことが可能となる。
【００７８】
（４）それぞれのコミュニティ内にオーソリティおよびハブの存在で自然に階層的な構造が作り上げられていることを利用することで、今までは散在していたブログの情報を組織化し、階層構造として表示することができ、閲覧者にとって情報が探しやすくなる。それにより、例えばあるトピックについてブログの情報を調べる場合、より凝縮した内容のみ調べたい場合はオーソリティとなるエントリを調べれば済み、より掘り下げてそのトピックがブログでどの様に言及されているかを調べたい場合はハブとなるエントリを調べるといった使い分けができるようになる。従って、ブログで発信される情報の信頼性を図る指標を提供することができる。
【００７９】
（５）トラックバックリンクをインバウンドリンクとして扱うことにより、大きな変更を加えずにＨＩＴＳアルゴリズムを用いることができる。
【００８０】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【図面の簡単な説明】
【００８１】
【図１】トピックドリフトの例を示す図である。
【図２】ブログ記事のマルチトピックスの例を示す図である。
【図３】本発明の一実施形態にかかるシステムの構成例を示す図である。
【図４】実施形態の全体的な処理の流れを示す図である。
【図５】クエリログの例を示す図である。
【図６】キーワード／ＵＲＬテーブルの例を示す図である。
【図７】ＵＲＬ／書誌情報テーブルの例を示す図である。
【図８】ＵＲＬ／リンクテーブルの例を示す図である。
【図９】クエリ／共起語の行列の例を示す図である。
【図１０】共起行列の例を示す図である。
【図１１】ターム集合の例を示す図である。
【図１２】カテゴリデータの例を示す図である。
【図１３】ターム集合（ラベル付）の例を示す図である。
【図１４】ルートセットの例を示す図である。
【図１５】ベースセットの例を示す図である。
【図１６】コミュニティ抽出の概要を示す図（その１）である。
【図１７】コミュニティ抽出の概要を示す図（その２）である。
【図１８】コミュニティ抽出のための固有ベクトルの計算処理の例を示すフローチャートである。
【図１９】固有ベクトルの計算例を示す図（その１）である。
【図２０】固有ベクトルの計算例を示す図（その２）である。
【図２１】固有ベクトルの計算例を示す図（その３）である。
【図２２】固有ベクトルの計算例を示す図（その４）である。
【図２３】コミュニティ抽出結果の例を示す図である。
【図２４】コミュニティのディレクトリ構造の例を示す図である。
【図２５】インデックスデータの例を示す図である。
【符号の説明】
【００８２】
１        クラスタリングサーバ
１１      クエリログ収集部
１２      共起行列作成部
１３      クラスタリング処理部
１４      ラベリング部
２        コミュニティ抽出サーバ
２１      ブログ検索部
２２      リンク取得部
２３      ルートセット作成部
２４      ベースセット作成部
２５      コミュニティ抽出部
２６      フレーズ抽出部
２７      ディレクトリ作成部
２８      インデックス作成部
３        ブログ検索サーバ
４        ネットワーク
５        ユーザ端末
１０１    クエリログＤＢ
１０２    ターム集合ＤＢ
１０３    カテゴリＤＢ
１０４    ブログＤＢ
１０５    フレーズ辞書
１０６    インデックスＤＢ
【図１】
2008191877.tif 000003
【図２】
2008191877.tif 000004
【図３】
2008191877.tif 000005
【図４】
2008191877.tif 000006
【図５】
2008191877.tif 000007
【図６】
2008191877.tif 000008
【図７】
2008191877.tif 000009
【図８】
2008191877.tif 000010
【図９】
2008191877.tif 000011
【図１０】
2008191877.tif 000012
【図１１】
2008191877.tif 000013
【図１２】
2008191877.tif 000014
【図１３】
2008191877.tif 000015
【図１４】
2008191877.tif 000016
【図１５】
2008191877.tif 000017
【図１６】
2008191877.tif 000018
【図１７】
2008191877.tif 000019
【図１８】
2008191877.tif 000020
【図１９】
2008191877.tif 000021
【図２０】
2008191877.tif 000022
【図２１】
2008191877.tif 000023
【図２２】
2008191877.tif 000024
【図２３】
2008191877.tif 000025
【図２４】
2008191877.tif 000026
【図２５】
2008191877.tif 000027