(57)【要約】【課題】検索に用いられるクエリを代表するラベルを正確かつ容易に抽出する。【解決手段】Ｗｅｂページを検索する際に用いられたクエリ(q)の集合と、検索されたＷｅｂページを特定するＵＲＬの集合を対象として、前記クエリ(q)の各々と、そのクエリ(q)に基づく検索結果の中からクリックされたＵＲＬ(u)とを互いに関連付けたグラフデータ(G1)を生成し、グラフデータ(G1)に対してリンク構造解析を行うことによりＵＲＬ(u)のクエリ(q)に対する重要度を表すＵＲＬスコアを算出し、ＵＲＬスコアに基づいて選択された複数のＵＲＬ(u)を対象として、その複数のＵＲＬ(u)のそれぞれに関連付けられたクエリ(q)同士の類似度に基づいて複数のＵＲＬ(u)を複数のクラス(Kn)にクラスタリングし、そのクラス(Kn)に属するＵＲＬに関連付けられた複数のクエリ(q)に含まれる語句の中から当該クラス(Kn)を代表するラベルを抽出するようにする。【選択図】  図１
2016062445.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｅｂページを検索する際に用いられたクエリの集合と、検索された前記Ｗｅｂページを特定するＵＲＬの集合とを対象として、前記クエリの各々と、そのクエリに基づく検索結果の中からクリックされたＵＲＬとを互いに関連付けたグラフデータを生成するグラフデータ生成部と、
前記グラフデータに対してリンク構造解析を行い、前記ＵＲＬの前記クエリに対する重要度を表すＵＲＬスコアを算出するスコア算出部と、
前記ＵＲＬスコアに基づいて選択された複数のＵＲＬを対象として、前記複数のＵＲＬのそれぞれに関連付けられたクエリ同士の類似度に基づいて前記複数のＵＲＬを複数のクラスにクラスタリングするクラスタリング部と、
前記クラスに属するＵＲＬに関連付けられた複数のクエリに含まれる語句の中から前記クラスを代表するラベルを抽出するラベル抽出部と
を備えることを特徴とするラベル抽出装置。
【請求項２】
請求項１記載のラベル抽出装置において、
前記ラベル抽出部は、前記クラスのＵＲＬに対応する複数のクエリに対して前記ラベルをそれぞれ付与して記憶する
ことを特徴とするラベル抽出装置。
【請求項３】
請求項２記載のラベル抽出装置において、
前記ＵＲＬの集合に含まれる全てのＵＲＬに対する全クリック数と、前記クラスに属するＵＲＬに対するクリック数との割合を表すクリック率を求めるクリック率算出部と
を更に備え、
前記ラベル抽出部は、前記クリック率が所定の条件を満たす場合に前記クエリに対して前記ラベルを対応付けて記憶する
ことを特徴とするラベル抽出装置。
【請求項４】
請求項２または３記載のラベル抽出装置において、
前記スコア算出部は、前記クラスタリング部によりクラスタリングされた前記クラスに属する複数のＵＲＬに関連付けられた複数のクエリのクエリスコアを算出した後その統計値を求め、
前記ラベル抽出部は、前記クラス毎の前記クエリスコアの統計値に基づいて前記ラベルの重要度を表す順位付けを行うラベル順位決定部を有する
ことを特徴とするラベル抽出装置。
【請求項５】
請求項１乃至４いずれか一項記載のラベル抽出装置において、
前記グラフデータは、前記クエリ、および、前記ＵＲＬをノードとして、前記クエリと前記ＵＲＬとを互いにエッジで結んだリンク構造の２部グラフである
ことを特徴とするラベル抽出装置。
【請求項６】
請求項５記載のラベル抽出装置において、
前記スコア算出部は、前記２部グラフのノードから、このノードに関連付けられた他のノードへランダムにテレポートするランダムウォークにより前記ＵＲＬスコアを算出する
ことを特徴とするラベル抽出装置。
【請求項７】
請求項１乃至６いずれか一項記載のラベル抽出装置において、
前記ラベル抽出部は、前記クエリに含まれる前記語句の出現頻度に応じて前記ラベルを抽出する
ことを特徴とするラベル抽出装置。
【請求項８】
Ｗｅｂページを検索する際に用いられたクエリの集合と、検索された前記Ｗｅｂページを特定するＵＲＬの集合とを対象として、前記クエリの各々と、そのクエリに基づく検索結果の中からクリックされたＵＲＬとを互いに関連付けたグラフデータをグラフデータ生成部により生成するグラフデータ生成ステップと、
前記グラフデータに対してスコア算出部によりリンク構造解析を行い、前記ＵＲＬの前記クエリに対する重要度を表すＵＲＬスコアを算出するスコア算出ステップと、
前記ＵＲＬスコアに基づいて選択された複数のＵＲＬを対象として、前記複数のＵＲＬのそれぞれに関連付けられたクエリ同志の類似度に基づいてクラスタリング部により前記複数のＵＲＬを複数のクラスにクラスタリングするクラスタリングステップと、
前記クラスに属するＵＲＬに関連付けられた複数のクエリに含まれる語句の中からラベル抽出部により前記クラスを代表するラベルを抽出するラベル抽出ステップと
を有することを特徴とするラベル抽出方法。
【請求項９】
コンピュータに対し、
Ｗｅｂページを検索する際に用いられたクエリの集合と、検索された前記Ｗｅｂページを特定するＵＲＬの集合とを対象として、前記クエリの各々と、そのクエリに基づく検索結果の中からクリックされたＵＲＬとを互いに関連付けたグラフデータを生成するグラフデータ生成ステップと、
前記グラフデータに対してリンク構造解析を行い、前記ＵＲＬの前記クエリに対する重要度を表すＵＲＬスコアを算出するスコア算出ステップと、
前記ＵＲＬスコアに基づいて選択された複数のＵＲＬを対象として、前記複数のＵＲＬのそれぞれに関連付けられたクエリ同志の類似度に基づいて前記複数のＵＲＬを複数のクラスにクラスタリングするクラスタリングステップと、
前記クラスに属するＵＲＬに関連付けられた複数のクエリに含まれる語句の中から前記クラスを代表するラベルを抽出するラベル抽出ステップと
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベル抽出装置、ラベル抽出方法およびプログラムに関し、特に、検索エンジンに対して入力されるクエリについて、そのクエリを代表するようなラベルを抽出するラベル抽出装置、ラベル抽出方法およびプログラムに関するものである。
【背景技術】
【０００２】
従来、Ｗｅｂ上の検索エンジンは、ユーザにより入力された検索キーワード（以下、単に「キーワード」と呼ぶ。）をクエリとして、このキーワードを含むＷｅｂページを検索し、その検索結果として抽出された複数のＷｅｂページのＵＲＬを端末装置の画面上にリスト表示する。
【０００３】
ユーザは、端末装置の画面上にリスト表示された複数のＵＲＬの中から１つをクリック（選択）し、端末装置を介してコンテンツサーバにより管理されるサイトにアクセスすることにより所望のＷｅｂページを閲覧している（例えば、特許文献１を参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−２８５０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この場合、ユーザによって適切なキーワード（クエリ）が入力されなければ、そのユーザが所望するＷｅｂページに容易に辿り着くことはできない。このため、検索サーバのオペレータは、入力されるクエリに基づく検索結果の中からユーザにより選択されるであろうＷｅｂページを予想し、その予想に基づいて、どのようなカテゴリのＷｅｂページの検索に用いられるクエリであるかを予め分類しておく。
【０００６】
これにより検索サーバの検索エンジンでは、クエリが入力されたとき、そのクエリに対して予め分類しておいたカテゴリに関連するＷｅｂページのＵＲＬを検索結果として提示することができる。
【０００７】
しかしながら、クエリの分類はオペレータの判断であるため、必ずしも相応しくないうえに手間および時間を要していた。そこで、発明者等は、検索エンジンに入力されるクエリに対するＵＲＬのクリックログの中から、そのＵＲＬをクリックした多くのクエリを代表するラベルを抽出し、これを検索に用いることにより、検索の効率化を図ることを考えた。
【０００８】
しかし、オペレータによるラベルの抽出が不適切であると、検索エンジンは見当はずれの検索結果を提示することになり、ユーザにとっては所望のＷｅｂページにたどり着くまでに多大な時間を要するので検索効率が低下するという問題があった。
【０００９】
本発明は上記した問題に鑑みなされたものであり、その目的は、効率的に検索可能な代表的なラベルをクエリから抽出するラベル抽出装置、ラベル抽出方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１０】
この目的を達成するために、本発明に係るラベル抽出装置は、Ｗｅｂページを検索する際に用いられたクエリ（ｑ）の集合と、検索された前記Ｗｅｂページを特定するＵＲＬ（ｕ）の集合とを対象として、前記クエリ（ｑ）の各々と、そのクエリ（ｑ）に基づく検索結果の中からクリックされたＵＲＬ（ｕ）とを互いに関連付けたグラフデータ（Ｇ１）を生成するグラフデータ生成部（２２）と、前記グラフデータ（Ｇ１）に対してリンク構造解析を行い、前記ＵＲＬ（ｕ）の前記クエリ（ｑ）に対する重要度を表すＵＲＬスコアを算出するスコア算出部（２３）と、前記ＵＲＬスコアに基づいて選択された複数のＵＲＬ（ｕ）を対象として、前記複数のＵＲＬ（ｕ）のそれぞれに関連付けられたクエリ同士の類似度に基づいて前記複数のＵＲＬ（ｕ）を複数のクラス（Ｋｎ）にクラスタリングするクラスタリング部（２５）と、前記クラス（Ｋｎ）に属するＵＲＬ（ｕ）に関連付けられた複数のクエリ（ｑ）に含まれる語句の中から前記クラス（Ｋｎ）を代表するラベルを抽出するラベル抽出部（２６）とを備えることを特徴とする。
【００１１】
本発明に係るラベル抽出装置において、前記ラベル抽出部（２６）は、前記クラス（Ｋｎ）のＵＲＬ（ｕ）に対応する複数のクエリ（ｑ）に対して前記ラベルをそれぞれ付与して記憶するようにしてもよい。
【００１２】
本発明に係るラベル抽出装置において、前記ＵＲＬ（ｕ）の集合に含まれる全てのＵＲＬ（ｕ）に対する全クリック数と、前記クラス（Ｋｎ）に属するＵＲＬ（ｕ）に対するクリック数との割合を表すクリック率を求めるクリック率算出部（２６ａ）とを更に備え、前記ラベル抽出部（２６）は、前記クリック率が所定の条件を満たす場合に前記クエリ（ｑ）に対して前記ラベルを対応付けて記憶するようにしてもよい。
【００１３】
本発明に係るラベル抽出装置において、前記スコア算出部（２３）は、前記クラスタリング部（２５）によりクラスタリングされた前記クラス（Ｋｎ）に属する複数のＵＲＬ（ｕ）に関連付けられた複数のクエリ（ｑ）のクエリスコアを算出した後その統計値を求め、前記ラベル抽出部（２６）は、前記クラス（Ｋｎ）毎の前記クエリスコアの統計値に基づいて前記ラベルの重要度を表す順位付けを行うラベル順位決定部（２６ｂ）を有するようにしてもよい。
【００１４】
本発明に係るラベル抽出装置において、前記グラフデータ（Ｇ１）は、前記クエリ（ｑ）、および、前記ＵＲＬ（ｕ）をノードとして、前記クエリ（ｑ）と前記ＵＲＬ（ｕ）とを互いにエッジで結んだリンク構造の２部グラフ（Ｇ１）であるようにしてもよい。
【００１５】
本発明に係るラベル抽出装置において、前記スコア算出部（２３）は、前記２部グラフ（Ｇ１）のノードから、このノードに関連付けられた他のノードへランダムにテレポートするランダムウォークにより前記ＵＲＬスコアを算出するようにしてもよい。
【００１６】
本発明に係るラベル抽出装置において、前記ラベル抽出部（２６）は、前記クエリ（ｑ）に含まれる前記語句の出現頻度に応じて前記ラベルを抽出するようにしてもよい。
【００１７】
本発明に係るラベル抽出方法は、Ｗｅｂページを検索する際に用いられたクエリ（ｑ）の集合と、検索された前記Ｗｅｂページを特定するＵＲＬ（ｕ）の集合とを対象として、前記クエリ（ｑ）の各々と、そのクエリ（ｑ）に基づく検索結果の中からクリックされたＵＲＬ（ｕ）とを互いに関連付けたグラフデータ（Ｇ１）をグラフデータ生成部（２２）により生成するグラフデータ生成ステップと、前記グラフデータ（Ｇ１）に対してスコア算出部（２３）によりリンク構造解析を行い、前記ＵＲＬ（ｕ）の前記クエリ（ｑ）に対する重要度を表すＵＲＬスコアを算出するスコア算出ステップと、前記ＵＲＬスコアに基づいて選択された複数のＵＲＬ（ｕ）を対象として、前記複数のＵＲＬ（ｕ）のそれぞれに関連付けられたクエリ同士の類似度に基づいてクラスタリング部（２５）により前記複数のＵＲＬ（ｕ）を複数のクラス（Ｋｎ）にクラスタリングするクラスタリングステップと、前記クラス（Ｋｎ）に属するＵＲＬ（ｕ）に関連付けられた複数のクエリ（ｑ）に含まれる語句の中からラベル抽出部（２６）により前記クラス（Ｋｎ）を代表するラベルを抽出するラベル抽出ステップとを有することを特徴とする。
【００１８】
本発明に係るプログラムは、コンピュータに対し、Ｗｅｂページを検索する際に用いられたクエリ（ｑ）の集合と、検索された前記Ｗｅｂページを特定するＵＲＬ（ｕ）の集合とを対象として、前記クエリ（ｑ）の各々と、そのクエリ（ｑ）に基づく検索結果の中からクリックされたＵＲＬ（ｕ）とを互いに関連付けたグラフデータ（Ｇ１）を生成するグラフデータ生成ステップと、前記グラフデータ（Ｇ１）に対してリンク構造解析を行い、前記ＵＲＬ（ｕ）の前記クエリ（ｑ）に対する重要度を表すＵＲＬスコアを算出するスコア算出ステップと、前記ＵＲＬスコアに基づいて選択された複数のＵＲＬ（ｕ）を対象として、前記複数のＵＲＬ（ｕ）のそれぞれに関連付けられたクエリ同士の類似度に基づいて前記複数のＵＲＬ（ｕ）を複数のクラス（Ｋｎ）にクラスタリングするクラスタリングステップと、前記クラス（Ｋｎ）に属するＵＲＬ（ｕ）に関連付けられた複数のクエリ（ｑ）に含まれる語句の中から前記クラス（Ｋｎ）を代表するラベルを抽出するラベル抽出ステップとを実行させることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、Ｗｅｂページを検索する際に用いられるクエリ（ｑ）の各々と、そのクエリ（ｑ）に基づく検索結果の中からクリックされたＵＲＬ（ｕ）とを互いに関連付けたグラフデータ（Ｇ１）に対するリンク構造解析により、ＵＲＬ（ｕ）のクエリ（ｑ）に対する重要度を表すＵＲＬスコアを算出し、そのＵＲＬスコアに基づいて選択された複数のＵＲＬ（ｕ）を対象として、その複数のＵＲＬ（ｕ）にそれぞれ関連付けられたクエリ（ｑ）同志の類似度に基づいて複数のクラスにクラスタリングし、そのクラスに属するＵＲＬ（ｕ）に関連付けられた複数のクエリ（ｑ）に含まれる語句の中から、このクラスを代表するラベルを抽出することにより、ＵＲＬスコアおよびクラスタリングにより絞り込まれたＵＲＬ（ｕ）に関連付けられている複数のクエリ（ｑ）に含まれる語句をラベルとして抽出することになる。したがって、効率的に検索可能な代表するラベルをクエリ（ｑ）から抽出することができる。
【００２０】
本発明によれば、ラベル抽出部（２６）は、クラス（Ｋｎ）のＵＲＬ（ｕ）に対応する複数のクエリ（ｑ）に対してラベルをそれぞれ付与して記憶することにより、検索エンジンはこのクエリ（ｑ）にはこのラベルが対応付けられていることを認識することができる。これにより検索エンジンは、そのラベルに予め対応付けておいた検索結果のＵＲＬ（ｕ）を提供することが可能となる。
【００２１】
本発明によれば、ＵＲＬ（ｕ）の集合に含まれる全てのＵＲＬ（ｕ）に対する全クリック数と、クラス（Ｋｎ）に属するＵＲＬ（ｕ）に対するクリック数との割合を表すクリック率が所定の閾値よりも高い場合にのみ、クエリ（ｑ）に対してラベルを対応付けて記憶することにより、クリック数の少ない、信頼性の低いクラス（Ｋｎ）のラベルを排除することが可能となる。
【００２２】
本発明によれば、クラス（Ｋｎ）の複数のＵＲＬ（ｕ）に対応する複数のクエリ（ｑ）のクエリスコアの平均値を求め、クラス（Ｋｎ）毎のクエリスコアの平均値に基づいてラベルの重要度を表す順位付けを行うことができるので、検索エンジンは、クエリ（ｑ）に付与されたラベルの重要度に応じた検索処理を実行することが可能となる。
【００２３】
本発明によれば、クエリ（ｑ）に含まれる語句の出現頻度に応じてラベルを抽出するので、クエリ（ｑ）の中で最も出現頻度の高い語句を、クエリを代表するラベルとして抽出することが可能となる。
【図面の簡単な説明】
【００２４】
【図１】第１乃至第３の実施の形態におけるラベル抽出システムの構成を示すシステム構成図である。
【図２】第１の実施の形態におけるラベル抽出サーバの構成を示すブロック図である。
【図３】第１の実施の形態におけるラベル抽出サーバの制御部のソフトウェア構成を示すブロック図である。
【図４】第１の実施の形態におけるクリックログを示す図である。
【図５】第１の実施の形態におけるクエリ・ベクトル表現を示す図である。
【図６】第１の実施の形態におけるＵＲＬとクエリとを互いに関連付けた２部グラフを示す図である。
【図７】第１の実施の形態における２部グラフ上でシードＵＲＬが指定された状態を示す図である。
【図８】第１の実施の形態におけるクラスタリングされた１つのクラスに含まれるシードＵＲＬおよびそれに対応するクエリを含むクラスタ結果画面を示す図である。
【図９】第１の実施の形態におけるラベル付クラスタ結果画面を示す図1である。
【図１０】第１の実施の形態におけるサブカテゴリラベル一覧画面を示す図である。
【図１１】第１の実施の形態におけるサブカテゴリ対応クエリ一覧画面（１）を示す図である。
【図１２】第１の実施の形態におけるサブカテゴリ対応クエリ一覧画面（２）を示す図である。
【図１３】第１の実施の形態におけるラベル抽出処理手順を示すフローチャートである。
【図１４】第１の実施の形態における検索画面（１）を示す図である。
【図１５】第１の実施の形態における検索画面（２）を示す図である。
【図１６】第２の実施の形態におけるラベル抽出付与部の構成を示すブロック図である。
【図１７】第３の実施の形態におけるラベル抽出付与部のラベル順位決定部によるラベル順位の決定の説明に供する図である。
【図１８】第３の実施の形態における順位付サブカテゴリラベル一覧画面を示す図である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について説明する。
【００２６】
＜第１の実施の形態＞
以下、図面を参照しながら本発明の第１の実施の形態について説明する。
【００２７】
＜ラベル抽出システムの全体構成＞
第１の実施の形態におけるラベル抽出システム１のラベル抽出サーバ２は、端末装置３により検索サーバ４に対して入力されたクエリが何に関連するものであるかを自動的に分類し、その分類結果であるラベルをクエリの語句から抽出し、そのクエリにラベルを付与するものである。
【００２８】
図１に示すように、ラベル抽出システム１は、過去の検索に用いられたクエリから予めラベルを抽出するラベル抽出サーバ２、ユーザＵＳＲが検索を行う際にクエリを入力するために用いられる端末装置３、その端末装置３からのクエリに基づく検索要求に応じて、このクエリに応じたＵＲＬを検索エンジンにより検索する検索サーバ４、その検索サーバ４による検索結果の中から端末装置３においてクリック（選択）されたＵＲＬに対応するＷｅｂページを読み出して端末装置３へ提供するコンテンツサーバ５によって構成されている。
【００２９】
＜ラベル抽出サーバの構成＞
ラベル抽出サーバ２は、図２に示すように、ＣＰＵ(Central Processing Unit)構成の演算装置１０、ハードディスク等の記憶装置１１、液晶ディスプレイ等の表示装置１２、通信インタフェース１３およびバス１４等を含むコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールし、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。
【００３０】
また、コンピュータプログラムは、コンピュータ読取可能な記録媒体や記憶装置に格納された状態でラベル抽出サーバ２に提供されても良く、或いは電気通信回線を介してラベル抽出サーバ２に提供されても良い。
【００３１】
図３に示すように、ラベル抽出サーバ２の演算装置１０と記憶装置１１にインストールされたコンピュータプログラムが協働することによって、クリックデータ取得部２１、２部グラフ生成部２２、スコア算出部２３、ペア抽出部２４、ＵＲＬクラスタリング部２５、ラベル抽出付与部２６およびＧＵＩ制御部２７が構成されている。
【００３２】
記憶装置１１には、ログ記憶部３１、グラフ記憶部３２、スコア記憶部３３、クラスタ結果記憶部３４およびラベル付データ記憶部３５が構成されている。
【００３３】
＜ログ記憶部＞
ログ記憶部３１は、図４に示すようなクリックログＬＧを予め蓄積しておく機能を有している。
【００３４】
このクリックログＬＧは、Ｗｅｂページを検索する際に端末装置３を介して用いられたクエリと、このクエリをキーワードとして検索サーバ４の検索エンジンにより検索されたときの検索結果である複数のＵＲＬのうち、端末装置３を介してユーザＵＳＲによりクリック（選択）されたＵＲＬ（以下、これを「クリックＵＲＬ」と呼ぶ。）と、を互いに関連付けたデータである。
【００３５】
このようなクエリとクリックＵＲＬとを互いに関連付けたデータを「クリックデータ」という。なお、クリックログＧＬは、個々のクリックログＬＧ１、ＬＧ２、……、の集まりである。
【００３６】
このクリックログＬＧ１およびＬＧ２は、クリックＵＲＬを選択した端末装置３の「ＩＰアドレス」、クリックＵＲＬが選択されたときの「時刻（time）」、「セッション（Session）」、クリックＵＲＬの「検索ランク(Rank)」、「クエリ」および「クリックＵＲＬ」からなる。ログ記憶部３１は、このようなクリックログＬＧ１、ＬＧ２、……、を数日から数カ月間にわたって複数の端末装置３から取得して蓄積し、例えば数千万乃至億単位の個数を予め用意しておく。
【００３７】
＜クリックデータ取得部＞
クリックデータ取得部２１は、ログ記憶部３１からクリックデータを取得する機能と、これらクリックデータを２部グラフ生成部２２へ出力する機能を有している。
【００３８】
＜２部グラフ生成部＞
２部グラフ生成部２２は、クリックデータに基づいて２部グラフを生成する機能と、同一のクリックＵＲＬ(http://xxx.yyy.zzz)を有するクリックデータに基づいて、図５に示すような、クリックＵＲＬと、そのクリックＵＲＬがクリックされたときのクエリの各々（「プロポーズ」、「血液型」、「占い」、「映画」）とからなるクエリ・ベクトル表現ＣＶを生成する機能を有している。
【００３９】
このクエリ・ベクトル表現ＣＶは、「クリックＵＲＬ」と、「クエリ」と、クリックＵＲＬに対する一定期間においてクリックが重複して行われたときの「頻度」との３つ組によって構成されている。
【００４０】
なお、２部グラフ生成部２２は、クリックＵＲＬに対するクエリ・ベクトル表現ＣＶのうち、「頻度」が所定の閾値（例えば「２０」）以下の場合、クリックＵＲＬに対してそのクエリがキーワードとして用いられることの信頼度が低いと判断し、それらのクエリ（この場合、「占い」、「映画」）を２部グラフを生成する際のノードから除外する機能についても有している。
【００４１】
このクエリ・ベクトル表現ＣＶは、第１要素の「クエリ」を行インデックス、第２要素の「クリックＵＲＬ」を列インデックス、第３要素の「頻度」を、これら行列インデックスの値成分とする疎な行列と表現することができる。また、この行列は、行のクエリ部と、列のＵＲＬ部からなる２部グラフの一つの表現形態である。
【００４２】
２部グラフ生成部２２は、図６に示すように、複数のクリックデータに基づいて複数のクリックＵＲＬの集合と、そのクリックＵＲＬに関連付けられた複数のクエリの集合とを対象として、クリックＵＲＬおよびクエリをノードとし、クリックＵＲＬとクエリとを互いにエッジ（リンク）で結んだリンク構造の２部グラフＧ１を生成する機能を有している。
【００４３】
ここで、２部グラフＧ１とは、クリックＵＲＬの集合と、クエリの集合とに分割したとき、クリックＵＲＬ同士およびクエリ同士のノード間にはエッジが存在しないが、クリックＵＲＬの集合とクエリの集合との間の任意のノード間にはエッジが存在するグラフのことである。
【００４４】
２部グラフ生成部２２は、この２部グラフＧ１をスコア算出部２３へ出力するとともに、この２部グラフＧ１および上述したクエリ・ベクトル表現ＣＶをグラフ記憶部３２に記憶する機能についても有している。
【００４５】
＜グラフ記憶部＞
グラフ記憶部３２は、２部グラフ生成部２２から受け取った２部グラフＧ１およびクエリ・ベクトル表現ＣＶを記憶し、スコア算出部２３からの要求に応じてこの２部グラフＧ１を読み出して出力し、ペア抽出部２４からの要求に応じてクエリ・ベクトル表現ＣＶを読み出して出力する機能を有している。
【００４６】
＜スコア算出部＞
スコア算出部２３は、２部グラフＧ１のグラフ構造をあたかもインターネット上のハイパーリンク構造のようにみなしてリンク構造分析を行うことにより、クリックＵＲＬのクエリに対する重要度を表すＵＲＬスコア、および、クエリのクリックＵＲＬに対する重要度を表すクエリスコアを算出する機能を有している。
【００４７】
ここで、クリックＵＲＬのＵＲＬスコアが高いほどクエリとの関連度が強く重要度が高いことを意味し、このＵＲＬスコアが低いほどクエリとの関連度が弱く重要度が低いことを意味する。関連度が強いというのは、そのクエリに基づいてそのクリックＵＲＬが選択される回数が多く、そのクエリとそのＵＲＬとは強く関連していることを意味する。重要度が高いというのは、そのクリックＵＲＬが複数のクエリにより選択された回数が多いので、多数のユーザにとって選択される重要なＵＲＬであることを意味する。
【００４８】
同様に、クエリのクエリスコアが高いほどクリックＵＲＬとの関連度が強く重要度が高いことを意味し、このクエリスコアが低いほどクリックＵＲＬとの関連度が弱く重要度が低いことを意味する。関連度が強いというのは、そのクリックＵＲＬに対してそのクエリが検索キーワードとして使用される回数が多く、そのクエリとそのＵＲＬとは強く関連していることを意味する。重要度が高いというのは、そのクエリが複数のクリックＵＲＬの選択に用いられる回数が多いので、多数のユーザにとって使用される重要なクエリであることを意味する。
【００４９】
インターネット上のハイパーリンク構造の分析方法としては、例えば、”mining the web-Discovering Knowledge from Hypertext Data”(Soumen Chakrabarti, Morgan Kaufmann Publishers,2003)の教科書に解説されているように、PageRank(登録商標), HITS, SALSA などが一般的に良く知られている。
【００５０】
スコア算出部２３では、２部グラフＧ１に対して、biased-PageRank(登録商標)によりクリックＵＲＬのＵＲＬスコアを算出する機能を有している。ここで、biased-PageRank とは、Haveliwala の Topic-Sensitive PageRank（Topic-Sensitive PageRank: A context-sensitive ranking algorithm for web search, Haveliwala, IEEE Transactions on Knowledge and Data Engineering, vol 15, num 4, pages 784-796,2003）で用いられた手法である。
【００５１】
また、２部グラフＧ１に対するスコアの計算については、非特許文献（Sumio Fujita, Keigo Machinaga, Georges Dupret : Click-graph modeling for facet attribute estimation of web search queries. RIAO 2010: 190-197）にも開示されている。
【００５２】
上記の PageRank は、ある確率でランダムにノード間をテレポートするランダムウォークによってリンク構造を分析する手法であり、ノードに対して特定の意味付けを持たない重要度を求める。
【００５３】
これに対し、biased-PageRank (Topic-Sensitive PageRank) は、特定のノード集合のうち１つのノード（この場合、後述するシードＵＲＬ）に対して、ある確率でランダムにテレポートするランダムウォークによってリンク構造を分析する手法である。
【００５４】
このため、biased-PageRank では、このノード集合との関連度が考慮されたＵＲＬスコアが算出される。また、biased-PageRank は、 PageRank と同様に、エッジを多く集めているノードが、そうではないノードに比べて高いＵＲＬスコアを持つことになるので、重要度を反映していることにもなる。
【００５５】
スコア算出部２３では、ＵＲＬスコアを算出する前に、予め特定のトピック（例えば「恋愛」）について、多くのユーザが選択するであろうとオペレータが考えたクリックＵＲＬを「シードＵＲＬ」として指定する機能を有している。
【００５６】
この場合、図７に示すように、２つのクリックＵＲＬ（ｕ１）｛「http://www.renai.co.jp」｝、クリックＵＲＬ（ｕ２）｛「http://www.kekkon.co.jp」｝がシードＵＲＬ（ｕｓ１）、（ｕｓ２）として表示されている例である。
【００５７】
説明の簡易化のために２つのシードＵＲＬ（ｕｓ１）、（ｕｓ２）だけを表示しているが、実際は多数のシードＵＲＬ（ｕｓ１）、（ｕｓ２）、……、が指定されている。ここでクリックＵＲＬ（ｕ１）、（ｕ２）、……、（Ｕｎ）がｎ個存在するとき、シードＵＲＬ（ｕｓ１）、（ｕｓ２）、……、の個数はクリックＵＲＬ（Ｕｎ）よりも少なくなる。
【００５８】
このとき、指定されたシードＵＲＬ（ｕｓ１）、（ｕｓ２）、……、とエッジで結ばれたクエリｑを特定することができる。図７に示す例では、この場合、シードＵＲＬ（ｕｓ１）、（ｕｓ２）に対しては、９個のクエリｑ（「デート」、「プロポーズ」、「相性」、「告白」、「遊園地」、「小説」、「占い」、「遠距離」、「映画」）が関連付けられている。
【００５９】
スコア算出部２３は、２部グラフＧ１に対してbiased-PageRank による次の（式１）および、この（式１）を展開した（式２）に基づいて、全てのクリックＵＲＬ（ｕ１）、（ｕ２）、……、（Ｕｎ）のクエリｑに対する重要度を表すＵＲＬスコアを算出する。
Ｐt+1(u)＝Σ(q、u)∈E Ｐt(q)・Ｐqu ……………………………………………（式１）
Ｐt+1(u)＝Σ(q、u)∈E Ｐt(q)・｛ｃ(q,u)／Σ(q'、u)∈E c(q',u)｝…………（式２）
【００６０】
これらの（式１）および（式２）について簡単に説明する。ｕはクリックＵＲＬ、ｑはクエリを意味する。ｔは時間（ランダムウォークの歩数（回数））を表す。Ｐt+1(u)は、２部グラフＧ１のノード間をｔ＋１の回数だけランダムウォークしたとき、クリックＵＲＬ(u)にいる確率を表す。
【００６１】
Ｐquは、あるクエリ(q)からあるクリックＵＲＬ(u)へ移動する確率を表す。（ｑ、ｕ）∈Ｅは、クエリ(q)とクリックＵＲＬ(u)の全てのペアの集合を表し、（ｑ、ｕ）はあるクリックＵＲＬ(u)と互いに関連付けられたあるクエリ(q)とのペアを表している。
【００６２】
ｃ(u,q)は、あるクエリ(q)と、あるクリックＵＲＬ(u)との間のクリック数、すなわち、クエリ(q)でクリックＵＲＬ(u)をクリックした回数を表している。なお、クエリ（q’）は、クエリ(q)とは異なるクエリを表している。したがって、クエリ(q)が「デート」であれば、クエリ(q’)は「デート」以外の「プロポーズ」〜「映画」の何れかである。
【００６３】
これらの（式１）および（式２）で示されるＰt+1(u)の確率を全てのクリックＵＲＬ(u)に対して行列式で表し、ランダムウォークを（ｔ＋１）回繰り返し、Ｐt+1(u)が収束するときのＵＲＬスコア（収束値）ｍ(t+1)は（式３）で表わされる。この（式３）により、全てのノード（クリックＵＲＬ(u)）のＵＲＬスコアｍを表現することが可能となる。
ｍ(t+1)＝αＤ-1Ａｍt＋（１−α）ｓ………………………………………………（式３）
【００６４】
ここで、Ｄ-1Ａは、あるシードＵＲＬ(u)からあるクエリ(q)へ移動する確率を行列で表したものであり、Ｐuqを全てのノードペア（シードＵＲＬ(u)およびクエリ(q)）に対して表現したものである。αは係数となっており、（１−α）ｓは、（式３）の行列式が収束するように調整するためのベクトルであり、「ランダムジャンプ」と呼ばれている。
【００６５】
すなわち、ＵＲＬスコアｍというのは、ランダムウォークする確率＋シードＵＲＬへランダムジャンプする確率との加算結果である。このランダムウォークする確率とシードＵＲＬへランダムジャンプする確率との割合をどれくらい重視するかを調整するために係数α（０＜α＜１）が乗算されているのである。したがって、（式３）を簡単に表現すると、ＵＲＬスコアｍ＝α（ランダムウォークする確率）+（１−α）（シードＵＲＬへランダムジャンプする確率）となる。
【００６６】
スコア算出部２３は、クリックＵＲＬ(ｕ１)、(ｕ２)、……、（ｕｎ）のそれぞれのＵＲＬスコアｍを算出し、閾値スコアｓｈにしたがって選択された上位数万個ほどのシードＵＲＬ（Ｕ）を選出した後、それらシードＵＲＬ(Ｕ）のＵＲＬスコアｍをペア抽出部２４へ出力するとともに、スコア記憶部３３へ出力する機能を有している。
【００６７】
このようにスコア算出部２３は、クリックＵＲＬ(ｕｎ）に対してそれぞれのＵＲＬスコアｍが収束するまでスコア算出処理を繰り返し、ＵＲＬスコアｍの高い上位数万個ほどのＵＲＬ（ｕｃ）を選出するので、この上位数万個のＵＲＬ（ｕｃｎ）はシードＵＲＬ（ｕ）に対応したＷｅｂページの内容に近く、かつ、クエリｑに対する重要度の高い順（ＵＲＬスコアｍの高い順）に並べられることが可能となる。
【００６８】
＜スコア記憶部＞
スコア記憶部３３は、スコア算出部２２から取得した上位数万個ほどのＵＲＬ(ｕｃ）のＵＲＬスコアｍを記憶するとともに、ペア抽出部２４からの要求に応じてＵＲＬ(ｕｃ）のＵＲＬスコアｍを読み出し、ペア抽出部２４へ出力する機能を有している。
【００６９】
＜ペア抽出部＞
ペア抽出部２４は、スコア算出部２２により閾値スコアｓｈに基づいて選択された上位数万個ほどのＵＲＬ(ｕｃ）に対応したクエリ・ベクトル表現ＣＶをグラフ記憶部３２から取得し、それらのクエリ・ベクトル表現ＣＶに基づいて、ＵＲＬ(ｕｃ）に関連付けられた複数のクエリｑを抽出する機能を有している。
【００７０】
すなわち、ペア抽出部２４は、例えば、ＵＲＬ(ｕｃ１）がシードＵＲＬ（ｕｓ１）であった場合、そのＵＲＬ（ｕｃ１）に対してはクエリｑ（「デート」、「プロポーズ」、「相性」、「告白」、「遊園地」、「小説」、「占い」）を抽出し、シードＵＲＬ(ｕ２) がシードＵＲＬ（ｕｓ２）であった場合、そのＵＲＬ（ｕｃ２）に対してはクエリｑ（「相性」、「告白」、「遠距離」、「映画」）を抽出する。
【００７１】
ペア抽出部２４は、このようにして抽出したＵＲＬ（ｕｃ１）、（ｕｃ２）、……、（ｕｃｎ）、およびクエリｑのペアＰ１、Ｐ２、…、ＰｎをＵＲＬクラスタリング部２５へ出力する機能を有している。
【００７２】
＜ＵＲＬクラスタリング部＞
ＵＲＬクラスタリング部２５は、閾値スコアｓｈに基づいて選択された上位数万個ほどのＵＲＬ(ｕｃｎ）、およびクエリｑのペアＰ１、Ｐ２、……、Ｐｎをクラスタリングの対象とし、このＵＲＬ(ｕｃｎ）と関連付けられたクエリｑ同士の類似度に基づいてクラスタリングを行う機能を有する。
【００７３】
この場合、ＵＲＬクラスタリング部２５は、ＵＲＬスコアｍの最も高い１番目のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑのベクトル表現を最初に取得する。以下、ｎ番目のＵＲＬ（ｕｃ）と表現する場合、ＵＲＬスコアｍが最上位からｎ番目に高いＵＲＬ（ｕｃ）のことを意味するものとする。
【００７４】
例えば、ＵＲＬスコアの最も高い１番目のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑのベクトル表現として例えば「血液型がｂ型」、「血液型がｂ型の女性」を取得した場合、これらを形態素解析技術により単語単位に分解し、ｗｏｒｄ１：「血液型」、ｗｏｒｄ２：「ｂ型」、ｗｏｒｄ３：「女性」を要素とする。
【００７５】
実際、１番目のＵＲＬ（ｕｃ）にペアリングされているクエリｑは多数存在し、単語の数についても多数存在するが、ここでは、都合上、ｗｏｒｄ１〜３の３種類だけが存在する例をもって以下説明する。この場合、ｗｏｒｄ１〜３まで３個あるので３次元として考える。
【００７６】
ＵＲＬクラスタリング部２５は、１番目のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑに出現するｗｏｒｄ１〜ｗｏｒｄ３の出現頻度に応じて各ｗｏｒｄ１〜３の重み付け値ｗｓ１〜ｗｓ３を求める。この場合、例えば、ｔｆ−ｉｄｆと呼ばれる重み付け値（重み付けされたスコア）の算出方法を用いる。
【００７７】
その結果、例えば、ｗｏｒｄ１の重み付け値ｗｓ１が「０．７２」、ｗｏｒｄ２の重み付け値ｗｓ２が「０．５１」、および、ｗｏｒｄ３の重み付け値ｗｓ３が「０．３２」であるとすると、この１番目のＵＲＬ（ｕｃ）に関連付けられた複数のクエリｑをベクトル表現したものは重み付け値（０．７２、０．５１、０．３２）となる。
【００７８】
ＵＲＬクラスタリング部２５は、ｗｏｒｄ１〜３の重み付け値ｗｓ１〜３に基づいて重心ベクトルｃｏｇ１を算出し、この１番目のＵＲＬ（ｕｃ）の重心ベクトルｃｏｇ１で代表されるクラスＫ１を生成し、ＵＲＬスコアが２番目以降のＵＲＬ（ｕｃ）がクラスＫ１に属するか否か判断する。
【００７９】
ＵＲＬクラスタリング部２５は、ＵＲＬスコアの２番目に高いＵＲＬ（ｕｃ）にペアリングされているクエリｑの複数のベクトル表現を取得し、１番目のＵＲＬ（ｕｃ）の場合と同様に２番目のＵＲＬ（ｕｃ）に対応するクエリの重心ベクトルｃｏｇ２を求める。
【００８０】
ＵＲＬクラスタリング部２５は、１番目のＵＲＬ（ｕｃ）の重心ベクトルｃｏｇ１と、２番目のＵＲＬ（ｕｃ）の重心ベクトルｃｏｇ２とを比較し、重心ベクトルｃｏｇ１に対して重心ベクトルｃｏｇ２の類似度が高いと判断した場合、２番目のＵＲＬ（ｕｃ）が１番目のクラスＫ１に属すると認識する。
【００８１】
ここで、重心ベクトルｃｏｇ１に対して重心ベクトルｃｏｇ２の類似度が高いとは、重心ベクトルｃｏｇ１の方向及び重心ベクトルｃｏｇ２の方向が同一であり、その角度差が小さいことを意味する。
【００８２】
具体的に重心ベクトルの類似度の算出には、いわゆるコサイン類似度を用いる。このコサイン類似度とは、ベクトル同士のなす角度の大きさをコサインで表現したものであり、コサイン類似度の値が１に近ければ２つのベクトルは互いに類似しており、コサイン類似度の値が０に近ければ類似していないことを表す。
【００８３】
すなわち、ベクトルの向きが一致している時、２つのベクトルのコサイン類似度は最大値の１をとなり、２つのベクトルの向きが直交であれば０、２つのベクトルの向きが逆方向であれば最小値の−１をとなる。
【００８４】
したがって、重心ベクトルｃｏｇ１、ｃｏｇ２のコサイン類似度の値が予め設定された閾値ｓｈ２よりも大きい場合、重心ベクトルｃｏｇ１に対して重心ベクトルｃｏｇ２の類似度が高いので、２番目のＵＲＬ（ｕｃ）が１番目のＵＲＬ（ｕｃ）のクラスＫ１に属することになる。
【００８５】
ＵＲＬクラスタリング部２５は、重心ベクトルｃｏｇ１、ｃｏｇ２のコサイン類似度の値が予め設定された閾値ｓｈ２（例えば「０．７」）よりも小さい場合、２番目のＵＲＬ（ｕｃ）が１番目のシードＵＲＬ（ｕｃ）のクラスＫ１に属することはないと判断し、この２番目のＵＲＬ（ｕｃ）における重心ベクトルｃｏｇ２で代表される２番目のクラスＫ２を新たに生成する。
【００８６】
このようにしてＵＲＬクラスタリング部２５は、残り全てのシードＵＲＬ（ｕｃ）に対してクラスタリングを行うことにより、複数のＵＲＬ（ｕｃ）を複数のクラスＫｎにクラス分類することができる。
【００８７】
なおクラスタリング処理においては、閾値ｓｈ２を高く設定すればクラス分類のクラス数ｎを増大させ、閾値ｓｈ２を低く設定すればクラス分類のクラス数ｎを減少させることが可能である。
【００８８】
ＵＲＬクラスタリング部２５は、クラスタリング結果であるクラスＫ１、Ｋ２、……、Ｋｎのクラスタ結果データをクラスタ結果記憶部３４に出力するとともに、このクラスＫ１、Ｋ２、……、Ｋｎのクラスタ結果データをＧＵＩ(Graphical User Interface)制御部２７へ出力する機能を有している。
【００８９】
＜クラスタ結果記憶部＞
クラスタ結果記憶部３４は、ＵＲＬクラスタリング部２５からのクラスＫ１、Ｋ２、……、Ｋｎのクラスタ結果データを記憶するとともに、ラベル抽出付与部２６からの要求に応じてクラスタ結果データを出力する機能を有している。
【００９０】
＜ラベル抽出付与部＞
ラベル抽出付与部２６は、クラスＫｎにクラスタリングされた複数のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑのベクトル表現の中から出現頻度の高い語句をラベルとして抽出し、このラベルを複数のＵＲＬ（ｕｃ）および複数のクエリｑに付与する機能を有している。なお、このラベルは、クラスＫｎを表す代表的な名称または要約表現としてＵＲＬ（ｕｃ）およびクエリｑに対して用いられる。
【００９１】
ここで、ラベル抽出付与部２６によるラベルの抽出処理としては、複数のクエリｑのベクトル表現を形態素解析し、日本語に対しては短単位の単語に分解し、最も出現頻度の高い単語をラベルとして抽出するものである。ここで、短単位とは、現代語において意味を持つ最小の単位であり、国立国語研究所により規定されたものである。また、単語とは、それ単独で１つの意味をなす語である。
【００９２】
なお、ラベル抽出付与部２６は、単語に分解する際、日本語の名詞相当句として不適切な部分を除外する。例えば、「の性格」のように助詞から始まっている語句、「型の女性」のように接尾辞から始まっている語句、および、「ｂ型の」のように助詞で終わっている語句等ついては日本語の名詞相当句として不適切な部分であるため除外する。
【００９３】
ラベル抽出処理部２６は、単語の出現頻度を求めるが、このとき、文字数の長さに拘らず、全ての単語の出現頻度をクラスＫｎに属する複数のＵＲＬに関連付けられている複数のクエリｑについて求める。
【００９４】
このときラベル抽出処理部２６は、単に最大の出現頻度の単語を抽出してしまうと、常に文字数「１」の単語列が最大の出現頻度になってしまう。そこでラベル抽出処理部２６では、ラベルとしてその意味を理解し易い長い単語を選択できるように、文字数の多さに応じて単語に重み付けを行う。
【００９５】
これにより、ラベル抽出付与部２６では、クラスＫｎに属する複数のＵＲＬ（ｕｃ）の内容を代表するような名称または要約表現として、その意味の理解し易い長さの単語（この場合、例えば「血液型」）をラベルとして抽出することが可能となる。
【００９６】
なお、ラベル抽出処理部２６によるラベル抽出処理の方法としては、上述したように重み付けを用いる方法に限るものではなく、単語の長さに応じて予め設定した定数をその単語に加算する方法や、長い単語の出現頻度については、それ自体の出現頻度に、その単語に含まれる部分の出現頻度を加算する方法であってもよい。
【００９７】
ラベル抽出付与部２６は、このようにして抽出したラベル（「血液型」）がクラスＫｎを代表する名称であるとして用い、クラスＫｎに属する複数のＵＲＬ（ｕｃ）やクエリｑにこのラベルをそれぞれ付与したラベル付データを生成した後、これをラベル付データ記憶部３５へ出力するとともにＧＵＩ制御部２７へ出力する機能を有している。
【００９８】
このようにしてクラスＫ１、Ｋ２、……、Ｋｎ毎に抽出されたラベルは、スコア算出部２３においてＵＲＬスコアｍを算出する際に、シードＵＲＬ（ｕ）を指定したときのトピック（「恋愛」）を上位のメインカテゴリと考えた場合、その下位のサブカテゴリを表すサブカテゴリラベルまたはタグであるとみなすことが可能である。なお、以下の説明では、このラベルを「サブカテゴリラベル」または単に「ラベル」と呼ぶ。
【００９９】
＜ＧＵＩ制御部＞
ＧＵＩ制御部２７は、ＵＲＬクラスタリング部２５からのクラスＫ１のクラスタ結果データに基づいて、図８に示すようなクラスタ結果画面Ｋ１Ｇを生成し、これを表示装置１２に表示する機能を有している。
【０１００】
このクラスタ結果画面Ｋ１Ｇには、このクラスＫ１にクラスタリングされた１番目のＵＲＬ（ｕｃ）｛http://www.blood.co.jp/｝よび２番目のシードＵＲＬ（ｕｃ）｛http://www.ketueki.co.jp/girl｝と、これらの２つのＵＲＬ（ｕｃ）にそれぞれペアリングされている複数のクエリｑが表示されている。
【０１０１】
例えば、１番目のＵＲＬ（ｕｃ）{http://www.blood.co.jp/}には、この１番目のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑ（「血液型ｂ女性」、……、「血液型がｂ型の特徴」、……、「血液型がｂ型の女性」、……）が表示されている。
【０１０２】
また、２番目のＵＲＬ（ｕｃ）{http://www.ketueki.co.jp/bgirl} には、この２番目のＵＲＬ（ｕｃ）にペアリングされている複数のクエリｑ（「血液型がｂ型の恋愛」、「血液型がｂ型の女性」……、「血液型がｂ型の男特徴」、……）が表示されている。
【０１０３】
同様にＧＵＩ制御部２７は、ＵＲＬクラスタリング部２５からのクラスＫ２、Ｋ３、……、のクラスタ結果データに基づいて、図示しないクラスタ結果画面Ｋ２Ｇ、Ｋ３Ｇ、……、を生成し、これを表示装置１２に表示することが可能である。
【０１０４】
また、ＧＵＩ制御部２７では、ラベル抽出付与部２６から取得したラベル付データに基づいて、図９に示すようなラベル付クラスタ結果画面Ｋ１ＬＧを生成し、これを表示装置１２に表示する機能を有している。
【０１０５】
ラベル付クラスタ結果画面Ｋ１ＬＧには、このクラスＫ１にクラスタリングされた１番目のＵＲＬ（ｕｃ）｛http://www.blood.co.jp/｝および２番目のＵＲＬ（ｕｃ）｛http://www.ketueki.co.jp/girl｝に対してサブカテゴリラベル（「血液型」）が表示されている。なお、このラベル付クラスタ結果画面Ｋ１ＬＧは、サブカテゴリラベル（「血液型」）が新たに追加されている以外、クラスタ結果画面Ｋ１Ｇ（図８）と同じ内容である。
【０１０６】
このラベル付クラスタ結果画面Ｋ１ＬＧにより、１番目のＵＲＬ（ｕｃ）に対応するＷｅｂページおよび２番目のＵＲＬ（ｕｃ）に対応するＷｅｂページは、「血液型」に関するＷｅｂページであると、ラベル抽出サーバ２のオペレータは理解することが可能となる。
【０１０７】
さらに、ＧＵＩ制御部２７は、ラベル抽出付与部２６によりクラスＫ１、Ｋ２、……、Ｋｎ毎にラベルを抽出したので、クラスＫ１、Ｋ２、……、Ｋｎのラベル付データに基づいて、図１０に示すような、サブカテゴリラベル一覧画面ＳＫＧ１を生成し、これを表示装置１２に表示する機能についても有している。
【０１０８】
この場合、サブカテゴリラベル一覧画面ＳＫＧ１では、トピック（「恋愛」）をメインカテゴリ（上位）と考えた場合のサブカテゴリ（下位）と考えられる例えば「血液型」、「プロポーズ」、「彼女」、「彼氏」、「結婚」、「相談」、「不倫」、「メール」のサブカテゴリラベルがクラスＫ１〜Ｋ８のクラスタ番号毎に８個表示されている。
【０１０９】
ＧＵＩ制御部２７は、サブカテゴリラベル一覧画面ＳＫＧ１において例えば「プロポーズ」がクリックされると、サブカテゴリラベルである「プロポーズ」が付与された全てのクエリｑをクリック数（検索数）の多い順番にしたがって並べたサブカテゴリ対応クエリ一覧画面ＳＫＧ２を生成し、これを表示装置１２に表示する機能を有している。
【０１１０】
このサブカテゴリ対応クエリ一覧画面ＳＫＧ２では、全てのクエリｑにサブカテゴリラベルである「プロポーズ」が対応付けられている。したがって、ラベル抽出サーバ２のオペレータは、サブカテゴリ対応クエリ一覧画面ＳＫＧ２に基づいて、クエリ「結婚」にはラベル「プロポーズ」、クエリ「名言集」にはラベル「プロポーズ」、……、「逆プロポーズ」にはラベル「プロポーズ」が対応付けられていることを認識することが可能となる。
【０１１１】
なお、１つのクエリｑに対して、複数のサブカテゴリラベルが対応付けられることもある。例えば、図１２に示すサブカテゴリ対応クエリ一覧画面ＳＫＧ２ｓのように、「名言集」のクエリに対しサブカテゴリラベルとして「プロポーズ」および「名言」が対応付けられている場合である。
【０１１２】
この場合、例えば、クラスＫｎのラベルが「名言集」であり、そのクラスＫｎのクエリｑに「名言集」が含まれていれば、この「名言集」のクエリｑには、「プロポーズ」と「名言」の双方のサブカテゴリラベルが付与されることになるからである。
【０１１３】
＜端末装置＞
端末装置３は、図示しないが、制御部、記憶部、入力部、表示部および通信インタフェース等を含むコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールし、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。
【０１１４】
＜検索サーバおよびコンテンツサーバ＞
検索サーバ４およびコンテンツサーバ５は、ラベル抽出サーバ２と同様、図示しないが、制御部、記憶部および通信インタフェース等を含むコンピュータ（ハードウェア）にコンピュータプログラム（ソフトウェア）をインストールし、コンピュータの各種ハードウェア資源とコンピュータプログラムとが協働することによって実現される。
【０１１５】
＜ラベル抽出動作＞
このような構成のラベル抽出システム１において、Ｗｅｂページを検索する際に用いられるクエリおよびクリックＵＲＬのクリックデータに基づいてラベルを抽出するラベル抽出動作について、図１３のフローチャートを参照しながら説明する。
【０１１６】
演算装置１０は、クリックデータ取得部２１によりログ記憶部３１に記憶されている多数のクリックデータを取得し（ステップＳＰ１）、これら多数のクリックデータに基づいてクリックＵＲＬおよびクエリｑをノードとしてエッジで結んだ２部グラフＧ１を生成する（ステップＳＰ２）。
【０１１７】
演算装置１０は、２部グラフＧ１を構成するクリックＵＲＬのうち、トピック（「恋愛」）に相当するページをシードＵＲＬ（ｕ１）、（ｕ２）として指定したうえで、全てのクリックＵＲＬ（ｕｎ）に対するＵＲＬスコアｍを算出する（ステップＳＰ３）。
【０１１８】
この後、演算装置１０は、複数のシードＵＲＬ（ｕ１）、（ｕ２）のＵＲＬスコアｍが閾値スコアｓｈよりも大きく、かつＵＲＬスコアｍの大きい値の方から上位数万個のＵＲＬ（ｕｃｎ）を選出する。
【０１１９】
この場合、演算装置１０では、トピック（「恋愛」）に相当するＷｅｂページをシードＵＲＬ（ｕ１）、（ｕ２）として予め指定した上でＵＲＬスコアｍを算出しているので、上位数万個のＵＲＬ（ｕｃｎ）はトピックに偏った「恋愛」に関するＷｅｂページに関連するものとなる。
【０１２０】
演算装置１０は、ＵＲＬスコアｍの上位数万個のＵＲＬ（ｕｃｎ）と、それに関連付けられた複数のクエリｑとを抽出し（ステップＳＰ４）、上位数万個のＵＲＬ（ｕｃｎ）間のクエリ同志の類似性（コサイン類似度）に基づいてＵＲＬクラスタリング処理を行う（ステップＳＰ５）。
【０１２１】
演算装置１０は、ＵＲＬクラスタリング処理の結果得られる複数のクラスＫ１、Ｋ２、……、Ｋｎに属する複数のＵＲＬ（ｕｃｎ）に関連付けられた複数のクエリｑのベクトル表現の中から出現頻度の高い語句を、各クラスＫｎを代表するラベル（サブカテゴリラベル）として抽出する（ステップＳＰ６）。
【０１２２】
そして演算装置１０は、このサブカテゴリラベルを各クラスＫｎにおける複数のＵＲＬ（ｕｃｎ）や複数のクエリｑに付与することにより、クエリｑをサブカテゴリラベルによって表したラベル付データを生成し（ステップＳＰ６）、これをラベル付データ記憶部３５に記憶することによりラベル抽出処理を終了する。
【０１２３】
これによりラベル抽出サーバ２は、従来のようにクエリｑの分類をオペレータの判断で行っていたときと比較して、クラスＫｎを代表するラベルを正確かつ短時間のうちに抽出し、そのラベルをクエリｑに付与することができる。かくして、クエリｑにとっては、トピック（「恋愛」）に関係した重要なＷｅｂページの内容を象徴するようなサブカテゴリラベルがクラスＫｎを代表して付与されることになる。
【０１２４】
これにより、ラベル抽出システム１では、予めラベル付与されたクエリが検索サーバ４に入力されると、検索サーバ４はそのラベルに基づいてユーザＵＳＲが所望すると予想されるＷｅｂページに対応した最適なＵＲＬを検索結果として端末装置３へ提供することができる。
【０１２５】
実際上、検索サーバ４は、図１４に示すように、端末装置３に表示した検索画面ＳＲＣＨ１においてクエリｑとして例えば「結婚」が入力されると、ラベル抽出装置２のラベル付データ記憶部３５からクエリ「結婚」のラベル付データを読み出す。これにより検索サーバ４は、クエリ「結婚」にはサブカテゴリラベル「プロポーズ」が付与されていることを認識することができる。
【０１２６】
検索サーバ４は、サブカテゴリラベル「プロポーズ」に予め設定しておいた例えば４つのＷｅｂページ（「プロポーズの言葉」、「結婚  Wikibedia」、「プロポーズ場所」、「結婚式場特集」）のＵＲＬを検索結果として端末装置３の検索画面ＳＲＣＨ１に表示する。
【０１２７】
このとき検索サーバ４は、従来のように、「結婚」のキーワードが含まれたタイトルのあらゆる種類のＷｅｂページを検索結果として単に羅列表示するのではなく、過去の履歴に基づいて、そのユーザＵＳＲが望むであろう「結婚」に繋がるための予め設定しておいた「プロポーズの言葉」、「結婚  Wikibedia」、「プロポーズ場所」、「結婚式場特集」等のＷｅｂページのＵＲＬを検索結果として提示することができる。
【０１２８】
このように、ユーザＵＳＲが必ずしも適切なキーワード（クエリｑ）を入力していなくても、検索サーバ４は「結婚」のクエリｑから実際に多数のユーザＵＳＲがクリックした過去の実績に基づくＷｅｂページのＵＲＬを、ユーザＵＳＲにとって所望するであろう検索結果として提示することができるので、ユーザＵＳＲに対する検索の効率化を図ることができる。
【０１２９】
なお、検索サーバ４は、図１５に示す検索画面ＳＲＣＨ２のように、クエリｑとして例えば「シカゴ  ニューヨーク」が検索エンジンに入力されると、ラベル抽出装置２のラベル付データ記憶部３５からクエリ「シカゴ  ニューヨーク」のラベル付データを読み出す。
【０１３０】
これにより検索サーバ４は、クエリ「シカゴ  ニューヨーク」には例えばサブカテゴリラベル「フライトインフォーメーション」および「天気予報」が付与されていることを認識することができる。
【０１３１】
かくして検索サーバ４は、サブカテゴリラベル「フライトインフォーメーション」に予め設定しておいたＷｅｂページ（「フライトインフォーメーション  シカゴ→ニューヨーク」および「天気予報  シカゴ」、「天気予報  ニューヨーク」）をコンテンツサーバ５から読み出し、これらを端末装置３の検索画面ＳＲＣＨ２に直接表示することが可能である。
【０１３２】
これにより検索サーバ４は、ＷｅｂページのＵＲＬを検索結果として提示しない分だけ、ユーザＵＳＲにとって所望するであろうＷｅｂページへダイレクトに導くことができるので、ユーザＵＳＲに対する検索の効率化を一段と向上させることができる。
【０１３３】
このときユーザＵＳＲは、端末装置３により検索サーバ４の検索エンジンに対してクエリ「シカゴ  ニューヨーク」と入力するだけで、「フライトインフォーメーション  シカゴ→ニューヨーク」および「天気予報  シカゴ」、「天気予報  ニューヨーク」のＷｅｂページを端末装置３により直ちに取得して目視確認することができる。
【０１３４】
＜第２の実施の形態＞
続いて、第２の実施の形態について説明する。この第２の実施の形態におけるラベル抽出サーバ２では、図１６に示すように、ラベル抽出付与部２６にクリック率算出部２６ａが設けられた構成を有している。
【０１３５】
このクリック率算出部２６ａは、図１７に示すように、２部グラフＧ１全体の全クリックＵＲＬに対する全クリック数（Ａ）を算出するとともに、ラベル付けされたクラスＫ１のクリック数（Ｂ１）、……、クラスＫｎのクリック数（Ｂｎ）を算出した後、クラスＫｎ毎に全クリック数（Ａ）とクリック数（Ｂｎ）との割合を表すクリック率（Ｂ１／Ａ、……、Ｂｎ／Ａ）をそれぞれ算出する。
【０１３６】
ラベル抽出付与部２６は、これらクラスＫｎ毎のクリック率が所定の条件としてある閾値よりも大きい場合に、そのクラスＫｎのクエリｑに対してラベルを付与したラベル付データを生成して記憶する。
【０１３７】
一方、ラベル抽出付与部２６は、クラスＫｎ毎のクリック率が閾値以下の場合、そのクラスＫｎのＵＲＬ（ｕｃｎ）に対するクリックの信頼性が低いと考えられるので、そのようなクラスＫｎのクエリｑにはラベルを付与しない。これによりラベル抽出サーバ２は、信頼性の低いラベルをクエリｑに付与してしまうことによる検索精度の低下を防止することができる。
【０１３８】
＜第３の実施の形態＞
次に、第３の実施の形態について説明する。この第３の実施の形態におけるラベル抽出サーバ２では、図１６に示したように、ラベル抽出付与部２６にラベル順位決定部２６ｂが設けられた構成を有している。
【０１３９】
この場合、ラベル抽出付与部２６のラベル順位決定部２６ｂは、クラスＫ１に対応付けられるサブカテゴリラベル（「血液型」）、クラスＫ２に対応付けられるサブカテゴリラベル（「プロポーズ」）、……、のラベルの重要性の順位を決定する機能を有している。
【０１４０】
この場合、ラベル順位決定部２６ｂは、サブカテゴリラベルが付与されたクラスＫ１に属する複数のＵＲＬ（ｕｃｎ）に関連付けられた複数のクエリｑのクエリスコアを算出した後その統計値（例えば平均値）を求め、サブカテゴリラベルが付与されたクラスＫ２に対応する全クエリｑのクエリスコアを算出した後その平均値を求め、クラスＫ３以降についてもクエリスコアの平均値を求める。
【０１４１】
この場合、ラベル順位決定部２６ｂは、クエリスコアの平均値を求めるようにしたが、これに限るものではなく、クエリスコアの中央値、最頻値等のその他種々の統計値を用いるようにしてもよい。
【０１４２】
ここで、クエリスコアは、クエリｑのＵＲＬ（ｕｃｎ）に対する重要度を表すものであり、スコア算出部２３によりＵＲＬスコアｍを算出するときと同様の算出方法により求められ、上述した（式３）で表される。ただし、（式１）および（式２）は、ｕとｑとが入れ替わり、次の（式４）および（式５）となる。
【０１４３】
Ｐt+1(q)＝Σ(q、u)∈E Ｐt(u)・Ｐu q ……………………………………………（式４）
Ｐt+1(q)＝Σ(q、u)∈E Ｐt(u)・｛ｃ(q,u)／Σ(q'、u)∈E c(q',u)｝…………（式５）
【０１４４】
ラベル順位決定部２６ｂは、クラスＫ１、Ｋ２、……、Ｋｎのクエリスコアの平均値の大きい順番にしたがってサブカテゴリラベルの順位を決定し、その順位を反映したラベル付データを生成し、これをラベル付データ記憶部３５へ出力するとともに、ＧＵＩ制御部２７へ出力する。
【０１４５】
ＧＵＩ制御部２７は、サブカテゴリラベルの順位を反映したラベル付データに基づいて、図１８に示すような、順位付サブカテゴリラベル一覧画面ＳＫＧ３を生成して表示装置１２に表示し、オペレータに対して目視確認させることができる。
【０１４６】
サブカテゴリラベルの順位が低いクラスＫｎは、そのサブカテゴリラベルの信頼性が低く、そのサブカテゴリラベルが付与されたクエリｑについては、検索エンジンによる検索精度が低くなる可能性が高い。
【０１４７】
これにより、検索サーバ４では、所定の順位以下のサブカテゴリラベルに対応するクラスＫｎのクエリｑについて、検索エンジンの検索時にそのクエリｑに付与されたサブカテゴリラベルを用いることを防止することができる。
【０１４８】
＜他の実施の形態＞
なお、上述した実施の形態においては、検索サーバ４はクエリｑに対してＷｅｂページのＵＲＬを検索結果として端末装置３へ出力するようにした場合について述べた。しかしながら、本発明はこれに限らず、検索サーバ４はクエリｑに対して例えばバナー広告のＵＲＬを検索結果として端末装置３へ出力するようにしても良い。
【０１４９】
また上述した実施の形態においては、形態素解析の対象として日本語のクエリｑを単語単位に分解し、その出現頻度の多い単語をラベルとして抽出するようにした場合について述べたが、本発明はこれに限らず、英語、その他、種々の外国語のクエリｑを単語単位に分解し、その出現頻度の多い単語をラベルとして抽出するようにしてもよい。
【０１５０】
さらに上述した実施の形態においては、検索サーバ４では、例えば「結婚」のクエリｑが検索エンジンに入力されたことに対して、実際に多数のユーザＵＳＲがクリックした過去の実績に基づいて、そのユーザＵＳＲがおそらく望むであろう「結婚」に繋がるための「プロポーズの言葉」、「結婚  Wikibedia」、「プロポーズ場所」、「結婚式場特集」等のＷｅｂページのＵＲＬを検索結果として提示するようにした場合について述べた。
【０１５１】
しかしながら、本発明はこれに限らず、ユーザＵＳＲより入力されたクエリｑに対して、実際に多数のユーザＵＳＲがクリックした過去の実績とは無関係にコンテンツの提供者側が意図的に設定した任意のＷｅｂページのＵＲＬを検索結果として提示するようにしても良い。
【符号の説明】
【０１５２】
１……ラベル抽出システム、２……ラベル抽出サーバ（ラベル抽出装置）、３……端末装置、４……検索サーバ、５……コンテンツサーバ、６……インターネット、１０……演算装置、１１……記憶装置、１２……表示装置、１３……通信インタフェース、１４……バス、２１……クリックデータ取得部、２２……２部グラフ生成部（グラフデータ生成部）、２３……スコア算出部（スコア算出部）、２４……ペア（ＵＲＬ及びクエリ）抽出部、２５……ＵＲＬクラスタリング部（クラスタリング部）、２６……ラベル抽出付与部、２６ａ……クリック率算出部（クリック率算出部）、２６ｂ……ラベル順位決定部（ラベル順位決定部）、２７……ＧＵＩ制御部、３１……ログ記憶部、３２……グラフ記憶部、３３……スコア記憶部、３４……クラスタ結果記憶部、３５……ラベル付データ記憶部。
【図２】
2016062445.tif 000003
【図３】
2016062445.tif 000004
【図４】
2016062445.tif 000005
【図５】
2016062445.tif 000006
【図６】
2016062445.tif 000007
【図７】
2016062445.tif 000008
【図８】
2016062445.tif 000009
【図９】
2016062445.tif 000010
【図１０】
2016062445.tif 000011
【図１１】
2016062445.tif 000012
【図１２】
2016062445.tif 000013
【図１３】
2016062445.tif 000014
【図１４】
2016062445.tif 000015
【図１５】
2016062445.tif 000016
【図１６】
2016062445.tif 000017
【図１７】
2016062445.tif 000018
【図１８】
2016062445.tif 000019
【図１】
2016062445.tif 000020