(57)【要約】      （修正有）【課題】キーワード間の関連性を、検索対象全体から直接的に測ることなく高精度に求める。【解決手段】ユーザにより指定される条件に対応するキーワード集合におけるキーワード間の関連度スコアを算出するキーワード関連度スコア算出装置において、前記キーワード集合から、２つのキーワードの組み合わせの集合を取得し、キーワード組み合わせ格納手段に格納する組み合わせ取得手段と、文字列をノードのラベルとする既存の階層構造を表すデータを格納する階層構造格納手段を参照することにより、前記キーワード組み合わせ格納手段に格納された前記キーワードの組み合わせのそれぞれについて、前記既存の階層構造における前記キーワードの組み合わせに対応する２つのノード間の関係に基づいて、当該組み合わせに係るキーワード間の関連度スコアを算出するスコア算出手段とを備える。【選択図】図１
2014102624.tif 000002
【特許請求の範囲】
【請求項１】
ユーザにより指定される条件に対応するキーワード集合におけるキーワード間の関連度スコアを算出するキーワード関連度スコア算出装置であって、
前記キーワード集合から、２つのキーワードの組み合わせの集合を取得し、キーワード組み合わせ格納手段に格納する組み合わせ取得手段と、
文字列をノードのラベルとする既存の階層構造を表すデータを格納する階層構造格納手段を参照することにより、前記キーワード組み合わせ格納手段に格納された前記キーワードの組み合わせのそれぞれについて、前記既存の階層構造における前記キーワードの組み合わせに対応する２つのノード間の関係に基づいて、当該組み合わせに係るキーワード間の関連度スコアを算出するスコア算出手段と
を備えることを特徴とするキーワード関連度スコア算出装置。
【請求項２】
前記スコア算出手段は、前記キーワードの組み合わせに対応する２つのノード間の関係が親子関係である可能性を示す第１の推定値と、前記キーワードの組み合わせに対応する２つのノード間の関係が兄弟関係である可能性を示す第２の推定値とを２つの関連度スコアとして算出する
ことを特徴とする請求項１に記載のキーワード関連度スコア算出装置。
【請求項３】
前記スコア算出手段は、前記キーワードの組み合わせのそれぞれについて、前記２つの関連度スコアをキーワード組み合わせスコア格納手段に格納し、
前記キーワード組み合わせスコア格納手段に格納された情報に基づいて、キーワードの組み合わせにおける第１のキーワードと第２のキーワード以外の他キーワードと前記第１のキーワードの組み合わせの関連度スコア、及び当該他キーワードと前記第２のキーワードの組み合わせの関連度スコアに基づいて、前記第１のキーワードと前記第２のキーワードの組み合わせに対応する関連度スコアを更新する
ことを特徴とする請求項２に記載のキーワード関連度スコア算出装置。
【請求項４】
ユーザにより指定される条件に対応するキーワード集合におけるキーワード間の関連度スコアを算出するキーワード関連度スコア算出装置が実行するキーワード関連度スコア算出方法であって、
前記キーワード集合から、２つのキーワードの組み合わせの集合を取得し、キーワード組み合わせ格納手段に格納する組み合わせ取得ステップと、
文字列をノードのラベルとする既存の階層構造を表すデータを格納する階層構造格納手段を参照することにより、前記キーワード組み合わせ格納手段に格納された前記キーワードの組み合わせのそれぞれについて、前記既存の階層構造における前記キーワードの組み合わせに対応する２つのノード間の関係に基づいて、当該組み合わせに係るキーワード間の関連度スコアを算出するスコア算出ステップと
を備えることを特徴とするキーワード関連度スコア算出方法。
【請求項５】
前記スコア算出ステップにおいて、前記キーワード関連度スコア算出装置は、前記キーワードの組み合わせに対応する２つのノード間の関係が親子関係である可能性を示す第１の推定値と、前記キーワードの組み合わせに対応する２つのノード間の関係が兄弟関係である可能性を示す第２の推定値とを２つの関連度スコアとして算出する
ことを特徴とする請求項４に記載のキーワード関連度スコア算出方法。
【請求項６】
前記スコア算出ステップにおいて、前記キーワード関連度スコア算出装置は、前記キーワードの組み合わせのそれぞれについて、前記２つの関連度スコアをキーワード組み合わせスコア格納手段に格納し、
前記キーワード組み合わせスコア格納手段に格納された情報に基づいて、キーワードの組み合わせにおける第１のキーワードと第２のキーワード以外の他キーワードと前記第１のキーワードの組み合わせの関連度スコア、及び当該他キーワードと前記第２のキーワードの組み合わせの関連度スコアに基づいて、前記第１のキーワードと前記第２のキーワードの組み合わせに対応する関連度スコアを更新する
ことを特徴とする請求項５に記載のキーワード関連度スコア算出方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のキーワード関連度スコア算出装置における組み合わせ取得手段、及びスコア算出手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索の分野に関し、特に、ユーザがシステムから提示されたキーワードを選択して、検索対象を絞り込みながら検索を行うことができる検索サービスにおいて、提示するキーワードを予めシステムが整理しておくことで、ユーザの検索を支援する機能を備えた検索サービスに関するものである。
【背景技術】
【０００２】
ユーザによる検索を支援する機能の一つとして、システムが検索キーワード候補をユーザに提示するキーワードサジェストがある(Google（登録商標）Suggest: http://www.google.com/webhp?complete=1&hl=ja/)。キーワードサジェスト機能を用いることで、ユーザがキーワードとして表現しにくい、または具体的なキーワードとして思い出せない曖昧な検索要求を持つ場合でも、システムから提示されたキーワードを選択することで検索対象を絞り込むことができ、効率よく検索を実行することができる。
【０００３】
しかしながら、システムが提示するキーワードの数が多い場合、キーワード集合を整理せずにリスト形式でユーザに提示するのでは、キーワード集合の関連性が明示的になっておらず、キーワード集合の関連性を把握しにくい。ユーザはキーワード集合の関連性を把握することで、例えば、類似するキーワードの中でどれが最も自分の検索要求に近いキーワードかを決定しやすかったり、どのような順番でキーワードを選択して検索を実行するかといった検索方針を立て易くなると考えられる。また、システムが関連性があるキーワードを近くに配置して提示することで、ユーザがキーワード集合の関連性を把握するのを支援できると考えられる。
【０００４】
したがって、システムがキーワード集合を整理せずにリスト形式でユーザに提示すると、ユーザ自身が提示されたキーワード集合の関連性を把握して選択するキーワードを決定しなければならず、検索コストがかかってしまう。これを解決するための手段の一つとして、システムがキーワード集合を整理してユーザに提示することが考えられ、キーワード集合の整理の手法としてキーワードのクラスタリングを用いることができる(非特許文献1)。この手法では、検索対象全体、例えばキーワード集合を文書内に含む文書集合の中に含まれるキーワードの出現回数や、他のキーワードとの共起回数などを考慮してキーワード間の関連性を定義する。そして、定義したキーワード間の関連性に基づいて、キーワード集合をクラスタリングすることにより、少数のキーワード集合をひとつのクラスタとしてまとめることができる。非特許文献1に開示された技術では、キーワード集合から複数のクラスタを生成して高さ1の階層構造を構築しているが、この操作をくり返すことにより、キーワード集合を階層構造で表現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】小西、上原子、小柳、"単語クラスタリングを用いた検索キーワードの提示"、第7回情報科学技術フォーラム(FIT2008)、2008
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述した従来技術におけるキーワードの出現回数や共起回数に基づくキーワードの階層的クラスタリング手法では、本来ならばキーワード間に関連性があるにも関わらず、検索対象全体の中での出現回数や共起回数が少ないために関連性が低いと判定されてしまうキーワードの組み合わせが出てくるという課題がある。これにより、本来はシステムが近くに配置してユーザに提示すべきクラスタやキーワードが遠くに配置されてしまう。そのため、ユーザはクラスタ間やキーワード間の関連性を把握しにくくなり、検索効率が低下してしまう。
【０００７】
本発明は上記の課題に鑑みてなされたものであり、キーワード間の関連性を、検索対象全体から直接的に測ることなく高精度に求めることを可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明は、ユーザにより指定される条件に対応するキーワード集合におけるキーワード間の関連度スコアを算出するキーワード関連度スコア算出装置であって、
前記キーワード集合から、２つのキーワードの組み合わせの集合を取得し、キーワード組み合わせ格納手段に格納する組み合わせ取得手段と、
文字列をノードのラベルとする既存の階層構造を表すデータを格納する階層構造格納手段を参照することにより、前記キーワード組み合わせ格納手段に格納された前記キーワードの組み合わせのそれぞれについて、前記既存の階層構造における前記キーワードの組み合わせに対応する２つのノード間の関係に基づいて、当該組み合わせに係るキーワード間の関連度スコアを算出するスコア算出手段とを備えることを特徴とするキーワード関連度スコア算出装置として構成される。
【０００９】
前記スコア算出手段は、前記キーワードの組み合わせに対応する２つのノード間の関係が親子関係である可能性を示す第１の推定値と、前記キーワードの組み合わせに対応する２つのノード間の関係が兄弟関係である可能性を示す第２の推定値とを２つの関連度スコアとして算出するように構成することができる。
【００１０】
また、前記スコア算出手段は、前記キーワードの組み合わせのそれぞれについて、前記２つの関連度スコアをキーワード組み合わせスコア格納手段に格納し、前記キーワード組み合わせスコア格納手段に格納された情報に基づいて、キーワードの組み合わせにおける第１のキーワードと第２のキーワード以外の他キーワードと前記第１のキーワードの組み合わせの関連度スコア、及び当該他キーワードと前記第２のキーワードの組み合わせの関連度スコアに基づいて、前記第１のキーワードと前記第２のキーワードの組み合わせに対応する関連度スコアを更新するようにしてもよい。
【００１１】
また、本発明は、前記キーワード関連度スコア算出装置が実行するキーワード関連度スコア算出方法、及び、コンピュータを、前記キーワード関連度スコア算出装置における組み合わせ取得手段、及びスコア算出手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１２】
本発明によれば、既存の階層構造におけるキーワードの組み合わせに対応する２つのノード間の関係に基づいてキーワード間の関連性を算出することとしたので、検索対象全体から直接的に測ることなくキーワード間の関連性を高精度に求めることが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態に係るキーワード関連度スコア算出装置１００の構成図である。
【図２】キーワード関連度スコア算出装置１００における処理の全体の流れを示すフローチャートである。
【図３】検索対象ＤＢ２０のデータ例を示す図である。
【図４】キーワード組み合わせＤＢ４０のデータ例を示す図である。
【図５】参照ＤＢ６０のデータ例を示す図である。
【図６】階層構造の例（ｌｅａｆは省略）を示す図である。
【図７】スコア算出処理（Ｓ１３０）の詳細フローチャートである。
【図８】キーワード組み合わせスコアＤＢ７０のデータ例を示す図である。
【図９】間接スコア算出処理（Ｓ１４０）の詳細フローチャートである。
【図１０】更新後のキーワード組み合わせスコアＤＢ７０のデータ例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１５】
本実施の形態では、従来技術における課題を解決するために、複数の既存の階層構造を用いることにより、キーワードの組み合わせとして最も小さい単位である２つのキーワード間の関連性を２つのスコアを用いて表現する。以下、本実施の形態に係る具体的なシステム、及び処理動作について説明する。
【００１６】
＜システム構成＞
図１は、本発明の実施の形態に係るキーワード関連度スコア算出装置１００の構成図である。なお、図１には、キーワード関連度スコア算出装置１００と通信を行うユーザ端末２００（例：ＰＣ、スマートフォン等）も示されている。
【００１７】
図１に示すように、本実施の形態に係るキーワード関連度スコア算出装置１００は、情報取得部１０、検索対象ＤＢ（データベース）２０、情報格納部３０、キーワード組み合わせＤＢ４０、スコア算出部５０、参照ＤＢ６０、キーワード組み合わせスコアＤＢ７０、及び間接スコア算出部８０を有する。ここでの各ＤＢは、複数のテーブルからなるデータを格納する格納手段である。
【００１８】
キーワード関連度スコア算出装置１００は、例えば、１つ又は複数のコンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、キーワード関連度スコア算出装置１００の各部が有する機能は、当該キーワード関連度スコア算出装置１００を構成するコンピュータに内蔵されるＣＰＵやメモリ、ハードディスクなどのハードウェア資源を用いて、各部で実施される処理に対応するプログラムを実行することによって実現することが可能である。より具体的には、プログラムに従って、計算対象の文字列等のデータをメモリから読み出し、ＣＰＵにより演算を行って、メモリに格納する動作を繰り返しながら処理が実行される。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００１９】
なお、キーワード関連度スコア算出装置１００を複数のコンピュータで構成する場合、例えば、図１に示す複数のＤＢ（格納手段）のうちの一部又は全部をキーワード関連度スコア算出装置１００の外部にネットワーク接続されたデータベース装置に備えることができる。
【００２０】
また、図１に示す機能区分は一例に過ぎず、本実施の形態で説明する処理を実行できる構成であれば、機能区分は図１に示すものに限られない。例えば、スコア算出部５０が、スコア算出処理機能に加えて、間接スコア算出部８０の機能を備えることとしてもよい。
【００２１】
図２は、本実施の形態に係る処理全体のフローチャートである。以下、図２のフローチャートの手順に沿って、各機能部の処理や各ＤＢの内容について詳細に説明する。
【００２２】
＜情報取得部１０＞
情報取得部１０は、ユーザが指定する条件と検索対象ＤＢ２０のデータを入力として、ユーザが指定する条件と関連があるキーワード集合を出力する（ステップＳ１１０）。すなわち、情報取得部１０は、ユーザ端末２００から受信するユーザが指定した条件に対応して検索対象ＤＢ２０に格納されているキーワード集合を検索対象ＤＢ２０から取得し、出力する。
【００２３】
検索対象ＤＢ２０のデータ例を図３に示す。図３に示すとおり、検索対象ＤＢ２０はユーザが指定する条件とその条件と関連があるキーワード集合をカラムとする。例えば、検索対象ＤＢ２０は、ユーザが指定する条件を既存の検索エンジン(例、goo（登録商標）: http://www.goo.ne.jp/)に問い合わせたときに得られる検索結果の中に含まれる複数の文書の中で出現回数が多い単語の集合をキーワード集合として格納することで構築できる。このとき、各レコード内のキーワード集合は重複を許さずに格納するものとする。ただし、異なるレコードに同じキーワードが出現することは許容する。
【００２４】
検索対象ＤＢ２０は予め生成しておくものであり、検索対象ＤＢ２０の生成には、例えば非特許文献1に記載された技術を用いることができる。また、ユーザが指定する条件とは、例えば「三浦半島」のような限定された地域や、「神奈川県旅行」のような特定の目的に基づいてユーザが入力した１つ以上のキーワードのことを表す。
【００２５】
＜情報格納部３０＞
情報格納部３０は、情報取得部１０が出力するキーワード集合を入力として、N（Ｎは自然数）個のキーワードの全ての組み合わせ(kw1, kw2)を生成し、当該組み合わせをキーワード組み合わせＤＢ４０に格納する(図２のステップＳ１２０)。すなわち、情報格納部３０は、N(N−１)／２個の組み合わせを生成し、キーワード組み合わせＤＢ４０に格納する。
【００２６】
キーワード組み合わせＤＢ４０のデータ例を図４に示す。キーワード組み合わせＤＢ４０はキーワードの組に対応するkw1とkw2をカラムとし、一つのレコードが一つのキーワード組み合わせを表す。
【００２７】
＜スコア算出部５０＞
スコア算出部５０は、情報格納部３０により出力したキーワード組み合わせＤＢ４０のデータと参照ＤＢ６０のデータとをそれぞれ読み出して入力とし、score1(kw1, kw2)とscore2(kw1, kw2)を算出し、算出した値をキーワード組み合わせスコアＤＢ７０に出力する(ステップＳ１３０）。図２に示すとおり、ステップＳ１３０のスコア算出処理は、ステップＳ１２０で取得したキーワード組み合わせのそれぞれに対して行われる。
【００２８】
ここで、score1(kw1, kw2)とscore2(kw1, kw2)はそれぞれのキーワードをラベルとする２つの中間ノードが既存の階層構造でどのような位置関係であるかの推定値であり、キーワード間の関連性を表す指標として用いるものである。
【００２９】
図５に、参照ＤＢ６０のデータ例を示す。図５に示すように、参照ＤＢ６０は、親ノードと子ノード集合をカラムとし、既存の階層構造を子ノードに葉ノード(leafとする)を含まない高さ1の部分木に分割し、それぞれの部分木の親ノードと子ノード集合をひとつのレコードとして格納している。例えば、既存の階層構造が深さ４の完全２分木である場合には、その階層構造は７つの高さ1の部分木に分割される。
【００３０】
ここで、既存の階層構造は各ノードがプロパティとしてラベルを持ち、そのラベルはキーワード組み合わせＤＢ４０に格納されているような文字列からなるとする。また、参照ＤＢ６０には高さ1の部分木がM個の既存の階層構造のうちどの階層構造の中に含まれているかを区別する番号(図５における識別番号)が格納されており、番号が一致するレコードをすべて取り出して１つの階層構造を完全に再現することは容易であるものとする。参照ＤＢ６０は、例えばgooカテゴリ(http://oshiete.goo.ne.jp/category/list/)のカテゴリを用いて構築可能な階層構造を用いて人手によって予め生成しておく。なお、本実施の形態において使用する既存の階層構造は、特定の手法によって生成されるものに限定されるわけではなく、種々の既存の階層構造を用いることができる。
【００３１】
ここで、階層構造における用語を定義する。階層構造の例を図６に示す。図６は高さ4の完全２分木のうち、根ノード(図６におけるroot)と1から14までの番号が書かれた○で表現された中間ノードを表現したものであり、16個のleafは省略している。ここで、番号Nは中間ノードのラベルを表すものとし、Nは1以上14以下の自然数である。ここで、図６の階層構造の例は完全2分木であるが、本発明で２つのスコアの算出に用いる階層構造はこれに限るものではない。
【００３２】
「上位語・下位語」：キーワードの上位語とは、キーワードからrootまで階層構造を下位階層に戻ることなくたどるときに通過する中間ノードのラベルとrootである。また、キーワードの下位語とは、キーワードからleafまで階層構造を上位階層に戻ることなくたどるときに通過する中間ノードのラベルである。例えば、図６において、番号5の上位語は番号2とrootであり、下位語は番号11と番号12である。また、番号12の上位語は番号5と番号2とrootであり、下位語は存在しない。
【００３３】
「２つのキーワードの間に含まれる中間ノード」：kw1とkw2においてkw1がkw2の上位語(または下位語)であるとき、kw1の下位語(または上位語)であり、かつ、kw2の上位語(または下位語)である中間ノードをそれら２つのキーワードの間に含まれる中間ノードと表す。このとき、２つのキーワードの間に含まれる中間ノードの個数はラベルがkw1である中間ノードの高さをd1、ラベルがkw2である中間ノードの高さをd2とすると｜d1 −d2｜−1である。例えば図６において、番号1と番号7の間に含まれる中間ノードはラベルが番号3である中間ノードである。
【００３４】
「直系の関係」：kw1がkw2の上位語または下位語であるとき、kw1とkw2は直系の関係であると表現する。例えば図６において、番号1は、番号3、番号4、番号7、番号8、番号9、番号10とそれぞれ直系の関係である。一方、ラベルが番号5である中間ノードからラベルが番号9である中間ノードまで階層構造をたどるためには、ラベルが番号5である中間ノードよりも上位階層にある、それぞれラベルが番号2、番号1、番号4である３つの中間ノードを順にたどらなければならないため、この２つのキーワードは直系の関係ではない。
【００３５】
「ancestor・共通の最若祖先」：kw1とkw2のそれぞれの上位語の集合をとり、２つの集合において共通の要素のうち最も高さが低い中間ノードのラベルと一致する上位語をancestorとする。そして、kw1とancestorの間に含まれる中間ノードの個数とkw2とancestorの間に含まれる中間ノードの個数が一致する場合、ancestorを共通の最若祖先と表現する。例えば図６において、番号7と番号9についてそれぞれの上位語の集合は｛番号3,番号1,root｝と｛番号4,番号1,root｝であるから共通の要素は番号1とrootであり、番号1がancestorである。そして、番号7とancestorの間に含まれる中間ノードの個数と番号9とancestorの間に含まれる中間ノードの個数はともに1であるから、番号1は共通の最若祖先である。一方、番号4と番号7について、それぞれの上位語の集合は｛番号1,root｝と｛番号3,番号1,root｝であるから共通の要素は番号1とrootであり、番号1がancestorであるが、番号4とancestorの間に含まれる中間ノードの個数は0個、番号7とancestorの間に含まれる中間ノードの個数は1個で一致しないので、番号1は共通の最若祖先ではない。同様に、番号3と番号6については、ancestorと共通の最若祖先はともにrootであり、番号2と番号3については、ancestorはrootであるが、rootは共通の最若祖先ではない。
【００３６】
次に、２つのスコアscore1(kw1, kw2)、score2(kw1, kw2)について説明する。
【００３７】
score1(kw1, kw2)は、既存の階層構造においてkw1とkw2をラベルとする２つの中間ノードが親子関係である可能性を示す推定値であり、kw1とkw2が既存の階層構造において直系の関係であり、かつ、それらの間に含まれる中間ノードの個数が少ないほど高スコアとなる。例えば図６において、score1(番号1,番号4) > score1(番号1、番号10)となる。
【００３８】
score2(kw1, kw2)は、既存の階層構造においてkw1とkw2をラベルとする２つの中間ノードが兄弟関係である可能性を示す推定値であり、kw1とkw2が既存の階層構造において共通の最若祖先を持ち、かつ、kw1あるいはkw2と２つのキーワードの共通の最若祖先の間に含まれる中間ノードの個数が少ないほど高スコアとなる。例えば図６において、score2(番号3,番号4) > score2(番号7,番号10)となる。
【００３９】
以下では、図２のステップＳ１３０のスコア算出処理について、図７のフローチャートに従って詳細に説明する。
【００４０】
キーワード組み合わせＤＢ４０の各レコード(kw1, kw2)において、以下の処理を行う。
【００４１】
kw1、kw2、score1(kw1, kw2)=0、score2(kw1, kw2)=0をキーワード組み合わせスコアＤＢ７０に格納する（ステップＳ２１０）。キーワード組み合わせスコアＤＢ７０はkw1、kw2、score1、score2をカラムとするＤＢである。
【００４２】
参照ＤＢ６０のM個の階層構造それぞれについて、識別番号の昇順に、kw1、kw2と一致する中間ノードを探索する（ステップＳ２２０）。
【００４３】
kw1とkw2をラベルとする中間ノードが存在する場合、例えば以下のようにして、２つのスコアを算出する(ステップＳ２３０、Ｓ２５０）。ただし、スコアの算出方法は以下の方法に限るものではない。
【００４４】
［kw1とkw2が直系の関係である場合(ステップＳ２３０、Ｓ２４０)］
kw1とkw2が直系の関係であるかどうかを調べ、直系の関係である場合、score1(kw1, kw2)を以下の式により算出する(ステップＳ２３０)。
【００４５】
【数１】
2014102624.tif 000003
ここで、nはkw1とkw2の間に含まれる中間ノードの個数を表す。
【００４６】
次に、ステップＳ２３０で算出したscore1(kw1, kw2)をキーワード組み合わせスコアＤＢ７０に格納する処理を行う(ステップＳ２４０)。ここでは、キーワード組み合わせスコアＤＢ７０に格納されているscore1(kw1, kw2)=AとステップＳ２３０で算出したスコアを比較して、A < score1(kw1, kw2)である場合のみ、キーワード組み合わせスコアＤＢ７０にscore1(kw1, kw2)を格納し、スコアを更新する。スコアを更新した場合、kw1がkw2の上位語である場合はそのまま、kw2がkw1の上位語である場合はkw1とkw2を入れ替えてキーワード組み合わせスコアＤＢ７０にkw1とkw2を格納する。ここで、k番目の階層構造について処理をしているとき、Aは1番目から(k−1)番目の階層構造について処理したときにステップＳ２３０で算出され、ステップＳ２４０でキーワード組み合わせスコアＤＢ７０に格納されたscore1(kw1, kw2)であるとする。ただし、kは1以上M以下の自然数である。
【００４７】
［kw1とkw2に共通の最若祖先がいる場合(ステップＳ２５０、Ｓ２６０）］
kw1とkw2が直系の関係になく、kw1とkw2に共通の最若祖先がいる場合、score2(kw1, kw2)を以下の式により算出する(ステップＳ２５０)。
【００４８】
【数２】
2014102624.tif 000004
ここで、mはkw1またはkw2と共通の祖先の間に含まれる中間ノードの個数を表す。また、tは0以上の整数で、例えば人手によって設定された閾値であり、例えばt=4やt=5である。
【００４９】
次に、ステップＳ２５０で算出したscore2(kw1, kw2)をキーワード組み合わせスコアＤＢ７０に格納する処理を行う(ステップＳ２６０)。
【００５０】
ここでは、キーワード組み合わせスコアＤＢ７０に格納されているscore2(kw1, kw2)=BとステップＳ２５０で算出したスコアを比較して、B < score2(kw1, kw2)である場合のみ、キーワード組み合わせスコアＤＢ７０にscore2(kw1, kw2)を格納し、スコアを更新する。ここで、l番目の階層構造について処理をしているとき、Bは1番目から(l−1)番目の階層構造について処理したときにステップＳ２５０で算出され、ステップＳ２６０でキーワード組み合わせスコアＤＢ７０に格納されたscore2(kw1, kw2)である。ただし、lは1以上M以下の自然数である。
【００５１】
図８に、キーワード組み合わせスコアＤＢ７０のデータ例を示す。
【００５２】
＜間接スコア算出部８０＞
間接スコア算出部８０は、キーワード組み合わせスコアＤＢ７０のデータを入力として、score1(kw1, kw2)とscore2(kw1, kw2)を更新する(図２のステップＳ１４０)。以下では、ステップＳ１４０の間接スコア算出処理について、図９のフローチャートに従って詳細に説明する。ただし、スコアの算出方法については以下の方法に限るものではない。
【００５３】
図９に示すように、score1(kw1, kw2)=0かつscore2(kw1, kw2)=0であるキーワード組み合わせ(kw1, kw2)に対して、間接スコア算出部８０は以下の処理を行う。
【００５４】
score1(kw1, α)=a、かつ、score2(α, kw2)=aとなるα、aがあるかどうかを調べ、ある場合に、ステップＳ３１０として以下の処理を行う。
【００５５】
ステップＳ３１０）kw1をαとkw2の共通の最若祖先とみなすことができるため、キーワード組み合わせスコアＤＢ７０にscore1(kw1, kw2)=aを格納する。ここで、αはキーワード組み合わせスコアＤＢ７０に格納されているキーワード、aはキーワード組み合わせスコアＤＢ７０に格納されているscore1である。
【００５６】
score1(kw1, α)=a、かつ、score2(α, kw2)=aとなるα、aがない場合、score1(β, kw1)=b、かつ、score1(β, kw2)=bとなるβ、bがあるかどうかを調べ、ある場合に、ステップＳ３２０として以下の処理を行う。
【００５７】
ステップＳ３２０）βをkw1とkw2の共通の最若祖先とみなすことができるため、キーワード組み合わせスコアＤＢ７０にscore2(kw1, kw2)=bを格納する。ここで、βはキーワード組み合わせスコアＤＢ７０に格納されているキーワード、bはキーワード組み合わせスコアＤＢ７０に格納されているscore1である。
【００５８】
間接スコア算出部８０によって更新されたキーワード組み合わせスコアＤＢ７０のデータ例を図１０に示す。
【００５９】
なお、上記の例は２つの関連度スコアがともに０であるキーワードの組み合わせに対して関連度スコアの更新をしているが、これは一例に過ぎず、２つの関連度スコアがともに０でないキーワードの組み合わせに対しても関連度スコアを更新することができる。この場合、例えば、２つの関連度スコアがそれぞれどのような範囲のスコアであるキーワードの組み合わせについて関連度スコアの更新をするかを、間接スコア算出部８０に予め設定しておき、間接スコア算出部８０は、この設定に基づいて、関連度スコアの更新処理を行う。
【００６０】
上記のように、間接スコア算出部８０は、組み合わせに係る２つのキーワードと異なるキーワードと、組み合わせに係るキーワードとの組み合わせに対応する関連度スコアに基づいて、間接的に組み合わせに係る２つのキーワード間の関係を推定し、関連度スコアを更新する。
【００６１】
（実施の形態の効果）
本実施の形態に係る技術によれば、キーワード間の関連性を検索対象全体からは直接的には測ることができない場合でも高精度に求めることが可能となる。これにより、キーワードのクラスタリングの精度を向上させることが可能となり、関連性が高いクラスタやキーワードを近くに配置することが可能となる。また、これにより、ユーザはクラスタ間やキーワード間の関連性を把握することが容易になり、システムから提示された選択肢を効率よく選択することが可能となり、ユーザの検索効率が向上する。
【００６２】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６３】
１０  情報取得部
２０  検索対象ＤＢ
３０  情報格納部
４０  キーワード組み合わせＤＢ
５０  スコア算出部
６０  参照ＤＢ
７０  キーワード組み合わせスコアＤＢ
８０  間接スコア算出部
１００  キーワード関連度スコア算出装置
２００  ユーザ端末
【図１】
2014102624.tif 000005
【図２】
2014102624.tif 000006
【図３】
2014102624.tif 000007
【図４】
2014102624.tif 000008
【図５】
2014102624.tif 000009
【図６】
2014102624.tif 000010
【図７】
2014102624.tif 000011
【図８】
2014102624.tif 000012
【図９】
2014102624.tif 000013
【図１０】
2014102624.tif 000014