(57)【要約】【課題】クエリ間の関連性を正確かつ簡単に把握することができる情報処理装置、情報処理方法、プログラム、および広告情報処理システムを提供すること。【解決手段】ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、前記各２つのクエリの双方を検索したユーザ数に基づいて算出する算出部と、前記各２つのクエリの間の関連付けの有無と、前記各２つのクエリの間の関連度とを示すグラフデータを生成する生成部と、前記グラフデータに基づいてクエリを分類する分類部と、を備える情報処理装置。【選択図】図２
2018151789.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、前記各２つのクエリの双方を検索したユーザ数に基づいて算出する算出部と、
前記各２つのクエリの間の関連付けの有無と、前記各２つのクエリの間の関連度とを示すグラフデータを生成する生成部と、
前記生成部によって生成されたグラフデータに基づいてクエリを分類する分類部と、
を備える情報処理装置。
【請求項２】
前記生成部は、更に、前記グラフデータにおける前記複数のクエリの中から、関連付けされたクエリの数が１つであるクエリを選択し、前記選択したクエリと、前記選択したクエリと関連付けされたクエリとの間の親子関係を設定し、
前記分類部は、前記生成部により設定された親子関係に基づいてクエリを分類する、
請求項１に記載の情報処理装置。
【請求項３】
前記生成部は、前記グラフデータにおいて関連付けされたクエリの数が２つ以上であるクエリについて、前記関連度が最も低いクエリとの関連付けを削除して、関連付けされたクエリの数が１つであるクエリを生成し、前記生成したクエリと、前記生成したクエリと関連付けされたクエリとの間の親子関係を設定する、
請求項２に記載の情報処理装置。
【請求項４】
前記分類部は、前記グラフデータにおける前記複数のクエリの中から、１つのクエリをランダムに選択し、前記選択したクエリを基準として所定のリンク数以内で接続されたクエリを１つのグループに分類する、
請求項１に記載の情報処理装置。
【請求項５】
前記分類部は、前記クエリのランダムな選択を複数回行うことにより１つクエリが複数のグループに分類される場合には、前記１つのクエリと、前記１つのクエリと関連付けされたクエリとの間の関連度に基づいて、前記１つのクエリが分類される１つのグループを決定する、
請求項４に記載の情報処理装置。
【請求項６】
前記生成部は、前記グラフデータにおける前記複数のクエリの中から、所定数以上のクエリと関連付けされたクエリを削除し、
前記分類部は、前記削除したクエリ以外のクエリを分類する、
請求項１に記載の情報処理装置。
【請求項７】
前記生成部は、更に、前記グラフデータにおける前記複数のクエリの中から、関連付けされたクエリの数が１つであるクエリを選択し、前記選択したクエリと、前記選択したクエリと関連付けされたクエリとの間の親子関係を設定し、
前記分類部は、前記複数のクエリの中から、前記選択したクエリ以外の１つのクエリをランダムに選択し、前記ランダムに選択したクエリを基準として所定のリンク数以内で接続されたクエリと、前記ランダムに選択したクエリおよび前記所定のリンク数以内で接続されたクエリと親子関係が設定されたクエリとを１つのグループに分類する、
請求項６に記載の情報処理装置。
【請求項８】
コンピュータが、
ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、前記各２つのクエリの双方を検索したユーザ数に基づいて算出し、
前記各２つのクエリの間の関連付けの有無と、前記各２つのクエリの間の関連度とを示すグラフデータを生成し、
前記グラフデータに基づいてクエリを分類する、
情報処理方法。
【請求項９】
コンピュータに、
ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、前記各２つのクエリの双方を検索したユーザ数に基づいて算出させ、
前記各２つのクエリの間の関連付けの有無と、前記各２つのクエリの間の関連度とを示すグラフデータを生成させ、
前記グラフデータに基づいてクエリを分類させる、
プログラム。
【請求項１０】
請求項１から７のいずれか一項に記載の情報処理装置と、
ユーザの端末装置からクエリを受信し、前記受信したクエリに応じた検索の結果を前記端末装置に送信する検索サーバと、
前記情報処理装置から出力されたクエリの分類結果に基づいて、前記検索サーバが受信した前記クエリと関連付けされた広告情報を決定する広告情報処理装置と、
を備え、
前記検索サーバは、更に、前記広告情報処理装置によって決定された前記広告情報を前記端末装置に送信する、
広告情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、プログラム、および広告情報処理システムに関する。
【背景技術】
【０００２】
従来、ウェブ検索において、ユーザが入力したキーワード（クエリ）を解析する技術についての研究が進められている。例えば、過去に入力されたクエリのリストを用いてクエリ間の関連性を解析することで、利便性の高い検索サービスを提供することが可能となる（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−９７０２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
クエリの解析においては、クエリ間の関連性をいかに正確に把握できるかが重要となる。また、膨大な数のクエリが解析対象となるため、解析処理を簡易化することも求められている。
【０００５】
本発明は、このような事情を考慮してなされたものであり、クエリ間の関連性を正確かつ簡単に把握することが可能な情報処理装置、情報処理方法、プログラム、および広告情報処理システムを提供することを目的の一つとする。
【課題を解決するための手段】
【０００６】
本発明の一態様は、ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、前記各２つのクエリの双方を検索したユーザ数に基づいて算出する算出部と、前記各２つのクエリの間の関連付けの有無と、前記各２つのクエリの間の関連度とを示すグラフデータを生成する生成部と、前記グラフデータに基づいてクエリを分類する分類部と、を備える情報処理装置である。
【発明の効果】
【０００７】
本発明の一態様によれば、クエリ間の関連性を正確かつ簡単に把握することができる。
【図面の簡単な説明】
【０００８】
【図１】第１実施形態における情報処理システム１の構成図である。
【図２】第１実施形態における情報処理装置７の機能構成を示す図である。
【図３】第１実施形態におけるクエリ間の関連性を示すグラフデータである。
【図４】第１実施形態における情報処理装置７の処理の一例を示すフローチャートである。
【図５】第１実施形態におけるノード処理の一例を説明した図である。
【図６】第１実施形態におけるノード処理の一例を説明した図である。
【図７】第１実施形態におけるノード処理の一例を説明した図である。
【図８】第１実施形態におけるノード間の親子関係を示す木構造を示す図である。
【図９】第２実施形態における情報処理装置７の処理の一例を示すフローチャートである。
【図１０】第２実施形態におけるクエリ間の関連性を示すグラフデータである。
【図１１】第２実施形態におけるノード処理の一例を説明した図である。
【図１２】第３実施形態における情報処理装置７の処理の一例を示すフローチャートである。
【図１３】第３実施形態におけるクエリ間の関連性を示すグラフデータである。
【図１４】第３実施形態におけるノード処理の一例を説明した図である。
【図１５】第１実施形態における情報処理システム１Ａの構成図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照し、本発明の情報処理装置、情報処理方法、プログラム、および広告情報処理システムの実施形態について説明する。情報処理装置は、ユーザの端末装置から送信されたクエリ間の関連度を示す重複検索スコアを算出し、算出した重複検索スコアに基づいてクエリの分類を行う。
【００１０】
＜第１実施形態＞
図１は、第１実施形態における情報処理システム１の構成図である。情報処理システム１は、例えば、一以上の端末装置３と、一以上の検索サーバ５と、一以上の情報処理装置７とを備える。端末装置３と、検索サーバ５とは、ネットワークＮＷによって互いに接続されており、このネットワークＮＷを介して互いに通信する。ネットワークＮＷは、例えば、ＷＡＮ（Wide Area Network）やＬＡＮ（Local Area Network）、インターネット、専用回線、無線基地局、プロバイダなどを含む。
【００１１】
［端末装置］
端末装置３は、検索サービスを利用するユーザによって操作される。端末装置３は、例えば、パーソナルコンピュータ、スマートフォンなどの携帯電話やタブレット端末、ＰＤＡ（Personal Digital Assistant）などのコンピュータ装置である。端末装置３では、ユーザの操作に基づいて動作するブラウザまたはアプリケーションプログラムが、情報提供を要求するクエリを検索サーバ５に送信し、クエリと関連付けされた検索情報を検索サーバ５から受信する。
【００１２】
［検索サーバ］
検索サーバ５は、端末装置３からクエリを受信し、受信したクエリに基づいて検索の結果を提供する。検索サーバ５は、クエリと、コンテンツの参照情報（例えばＵＲＬなど）とを関連付けた検索データベース（図示しない）を備えている。検索サーバ５は、端末装置３からクエリを受信した場合、検索データベースから、クエリに関連付けられたコンテンツを参照するための参照情報を抽出し、端末装置３に送信する。
【００１３】
検索サーバ５は、端末装置３から受信したクエリと、クエリの送信元の端末装置３のユーザの識別情報とを関連付けした履歴情報を記憶部（図示しない）に記憶する。ユーザの識別情報とは、例えば、端末装置３に備えられたウェブブラウザごとに管理されるクッキー（HTTP cookie）に関する情報や、端末装置３のＩＰアドレスなどである。これらの識別情報は、クエリを入力したユーザの識別情報とみなすことができる。また、ユーザが検索サーバ５にアクセスする際にログインを行っている場合、そのログインＩＤをユーザの識別情報としてよい。
［情報処理装置］
情報処理装置７は、検索サーバ５から履歴情報を取得し、取得した履歴情報を用いてクエリの分類を行う。図２は、情報処理装置７の機能構成を示す図である。情報処理装置７は、例えば、取得部１０と、関連度算出部１２（算出部）と、生成部１４と、分類部１６と、記憶部１８とを備える。情報処理装置７に含まれる各機能部は、複数の装置に分散されてもよい。例えば、関連度算出部１２と他の機能部とは別体の装置によって実現されてもよい。記憶部１８は、ＮＡＳ（Network Attached Storage）などの記憶装置であってもよい。
【００１４】
関連度算出部１２、生成部１４、および分類部１６は、例えば、ＣＰＵ（Central Processing Unit）などのプロセッサが、記憶部１８に記憶されたプログラム（ソフトウェア）を実行することにより実現される。プログラムは、例えば、ネットワークＮＷを介してアプリケーションサーバからダウンロードされてもよいし、予め情報処理装置７にプリインストールされていてもよい。また、これらの機能部は、ＬＳＩ（Large Scale Integration）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）などのハードウェアによって実現されてもよいし、ソフトウェアとハードウェアの協働によって実現されてもよい。記憶部１８は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ、またはこれらのうち複数が組み合わされたハイブリッド型記憶装置などによって実現される。
【００１５】
取得部１０は、端末装置３から送信されたクエリと、送信元の端末装置３のユーザの識別情報とが関連付けされた履歴情報を検索サーバ５から取得し、記憶部１８に記憶させる。
【００１６】
関連度算出部１２は、ネットワーク検索に用いられた複数のクエリにおける各２つのクエリの間の関連度を、各２つのクエリの双方を検索したユーザ数に基づいて算出する。例えば、関連度算出部１２は、記憶部１８から履歴情報を読み出し、クエリ間の関連度を示す重複検索スコアを算出する。重複検索スコアＳｃｏｒｅは、例えば、以下の式（１）によって算出される。
【００１７】
【数１】
2018151789.tif 000003
【００１８】
式（１）において、Ａｕｓｅｒは、クエリＡの検索ユーザ数であり、Ｂｕｓｅｒは、クエリＢの検索ユーザ数であり、ＡＬＬｕｓｅｒは、検索ユーザ数全体であり、Ａｕｓｅｒ∧Ｂｕｓｅｒは、クエリＡとクエリＢとの双方を検索しているユーザ数である。重複検索スコアＳｃｏｒｅは、値が大きいほど、クエリＡとクエリＢとの関連度が強いことを示す。また、クエリＡとクエリＢとの検索ユーザ数が互いに近いほど、重複検索スコアＳｃｏｒｅが高くなる傾向になる。関連度算出部１２は、重複検索スコアを算出した２つのクエリを示す情報と、算出した重複検索スコアとを関連付けした情報（以下、「重複検索スコア情報」と呼ぶ）を記憶部１８に記憶させる。
【００１９】
生成部１４は、複数のクエリにおける各２つのクエリの間の関連付けの有無と、この各２つのクエリの間の関連度とを示すグラフデータを生成する。また、生成部１４は、生成したグラフデータにおける複数のクエリの中から、関連付けされたクエリの数が１つであるクエリを選択し、この選択したクエリと、この選択したクエリと関連付けされたクエリとの間の親子関係を設定する。例えば、生成部１４は、記憶部１８から読み出した履歴情報を用いて、図３に示すようなグラフデータを生成する。
【００２０】
図３では、計８個のクエリがノードＡからＨとして示されている。図３において、リンクＬ１からリンクＬ９が各ノード間の関連付けの有無を示している。リンクＬ１からリンクＬ９によって互いに結ばれた２つのノードは、同一のユーザによって双方が検索された２つのクエリを示している。図３において括弧内に示された数値は、各リンクの重複検索スコアを示している。
【００２１】
例えば、図３においては、ノードＡと、ノードＤとは、リンクＬ４によって接続され、その重複検索スコアは“６”であることが示されている。また、ノードＡは、リンクＬ５によってノードＢと接続され、その重複検索スコアは“８”であり、リンクＬ３によってノードＣと接続され、その重複検索スコアは“４”であり、リンクＬ４によってノードＤと接続され、その重複検索スコアは“６”であり、リンクＬ２によってノードＥと接続され、その重複検索スコアは“５”であることが示されている。すなわち、ノードＡは、ノードＢとの関連性が最も高いことが分かる。
【００２２】
分類部１６は、生成部１４によって生成されたグラフデータに基づいてクエリを分類する。分類部１６によるクエリの分類処理の詳細については後述する。
【００２３】
記憶部１８は、取得部１０が検索サーバ５から取得した履歴情報、関連度算出部１２が算出した重複検索スコア情報、生成部１４によって生成されたグラフデータ、分類部１６によって分類されたクエリの分類結果などを記憶する。
【００２４】
［情報処理装置の処理］
次に、図４を参照しながら情報処理装置７の動作について説明する。図４は、情報処理装置７の処理の一例を示すフローチャートである。
【００２５】
まず、取得部１０は、履歴情報を検索サーバ５から取得し、記憶部１８に記憶させる（ステップＳ１０１）。
【００２６】
次に、関連度算出部１２は、記憶部１８から履歴情報を読み出し、読み出した履歴情報に基づいて重複検索スコアを算出する（ステップＳ１０３）。関連度算出部１２は、重複検索スコア情報を記憶部１８に記憶させる。
【００２７】
次に、生成部１４は、記憶部１８から重複検索スコア情報を読み出して、クエリ間の関連性を示すグラフデータを生成する（ステップＳ１０５）。例えば、生成部１４は、図３に示すようなクエリ間の関連性を示すグラフデータを生成する。
【００２８】
次に、生成部１４は、接続先のノードの数が１つであるノード（以下、「末端ノード」と呼ぶ）の処理を行う（ステップＳ１０７）。例えば、生成部１４は、グラフデータにおいて、末端ノードを選択し、選択した末端ノードを「子ノード」とし、選択した末端ノードの接続先のノードを「親ノード」として親子関係を設定する。
【００２９】
図５は、図３に示されたグラフデータに対するノード処理の一例を説明する図である。図３に示すグラフデータにおいては、２つの末端ノード（ノードＤおよびノードＦ）が存在する。図５のステップＳ１０７（１回目）に示されるように、生成部１４は、例えば、処理対象の末端ノードとしてノードＤを選択し、選択したノードＤを「子ノード」とし、ノードＤの接続先であるノードＡをノードＤの「親ノード」として親子関係を設定する。親子関係の設定が完了したノードＤは、グラフデータからは削除されたとみなして以降の処理が行われる。図５では、削除されたノードは点線で示されている。
【００３０】
次に、生成部１４は、全ての末端ノードの処理が完了したか否かを判定する（ステップＳ１０９）。生成部１４は、全ての末端ノードの処理が完了していないと判定した場合、未処理の末端ノードに対して上記の親子関係の設定を行う。図５に示す例においてノードＤの処理が完了した後には、未処理の末端ノードであるノードＦが存在する。このため、図５のステップＳ１０７（２回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＦを選択し、選択したノードＦを「子ノード」とし、ノードＦの接続先であるノードＥをノードＦの「親ノード」として親子関係を設定する。
【００３１】
上記のノードＦに対する処理の結果、ノードＥは、ノードＡのみに接続された末端ノードとなる。このため、図５のステップＳ１０７（３回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＥを選択し、選択したノードＥを「子ノード」とし、ノードＥの接続先であるノードＡをノードＥの「親ノード」として親子関係を設定する。
【００３２】
一方、生成部１４は、全ての末端ノードの処理が完了したと判定した場合、グラフデータに含まれる全てのノードの処理が完了したか否かを判定する（ステップＳ１１１）。生成部１４は、全てのノードの処理が完了していないと判定した場合、未処理のノード（ここでは、関連付けされたクエリの数が２つ以上であるクエリが未処理のノードとなる）の中で、接続先のノードの数が最も少ないノードを処理対象として選択し、選択したノードに接続された複数のリンクの内、重複検索スコアが最も低いリンクを削除する（ステップＳ１１３）。リンクが削除されることにより新たに末端ノードが生成されるため、生成部１４は、この新たに生成された末端ノードに対する上記の処理を行う。
【００３３】
図５に示す例において末端ノードであるノードＥの処理が完了した後には、未処理のノードであるノードＡ、Ｂ、Ｃ、Ｇ、およびＨが存在する。このため、生成部１４は、全てのノードの処理が完了していないと判定し、上記のリンクの削除処理を行う。例えば、図５に示す例において、接続先のノードの数が最も少ないノードとして、接続先のノードの数が２つであるノードＡ、Ｃ、Ｇ、およびＨが処理対象の候補となる。生成部１４は、ノードＡ、Ｃ、Ｇ、およびＨのいずれかを１つを処理対象として選択し（図５に示す例ではノードＡを選択し）、選択したノードＡに接続された複数のリンクＬ５およびＬ３の内、重複検索スコアが低いリンクＬ３を削除する。リンクＬ３が削除されたことにより、ノードＡおよびノードＣが末端ノードとなる。なお、生成部１４は、選択したノードに接続された複数のリンクの中で重複検索スコアが最も低いリンクが複数存在する場合には、任意の１つのリンクを削除してよい。
【００３４】
図６は、図５に示す例においてリンクＬ３が削除された後のノード処理の一例を説明する図である。図６のステップＳ１０７（４回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＡを選択し、選択したノードＡを「子ノード」とし、ノードＡの接続先であるノードＢをノードＡの「親ノード」として親子関係を設定する。さらに、図６のステップＳ１０７（５回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＣを選択し、選択したノードＣを「子ノード」とし、ノードＣの接続先であるノードＢをノードＣの「親ノード」として親子関係を設定する。
【００３５】
図６に示す例において末端ノードであるノードＣの処理が完了した後には、未処理のノードであるノードＢ、Ｇ、およびＨが存在する。このため、接続先のノードの数が最も少ないノードとして、接続先のノードの数が２つであるノードＢ、Ｇ、およびＨが処理対象の候補となる。生成部１４は、ノードＢ、Ｇ、およびＨのいずれかを１つを処理対象として選択し（図６に示す例ではノードＢを選択し）、選択したノードＢに接続された複数のリンクＬ７およびＬ８の内、重複検索スコアが低いリンクＬ７を削除する。リンクＬ７が削除されたことにより、ノードＢおよびノードＧが末端ノードとなる。
【００３６】
図７は、図６に示す例においてリンクＬ７が削除された後のノード処理の一例を説明する図である。図７のステップＳ１０７（６回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＢを選択し、選択したノードＢを「子ノード」とし、ノードＢの接続先であるノードＨをノードＢの「親ノード」として親子関係を設定する。さらに、図７のステップＳ１０７（７回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＧを選択し、選択したノードＧを「子ノード」とし、ノードＧの接続先であるノードＨをノードＧの「親ノード」として親子関係を設定する。
【００３７】
一方、生成部１４は、全てのノードの処理が完了したと判定した場合、クエリ間の親子関係を示す木構造を生成する（ステップＳ１１５）。図８は、図５から図７において設定された親子関係をまとめた木構造を示す図である。図８に示す木構造では、第１から第５階層までの各層にノードが配置されている。
【００３８】
次に、分類部１６は、生成部１４によって生成された木構造を用いてクエリを分類する（ステップＳ１１７）。例えば、分類部１６は、木構造における階層に基づいてクエリを分類する。分類部１６は、同一階層に位置するクエリを同一のグループに属するクエリとして分類してよい。また、分類部１６は、予め設定された階層以下のクエリを同一のグループに属するクエリとして分類してもよい。クエリの分類に利用される基準は任意である。以上により、情報処理装置７は、本フローチャートの処理を終了する。
【００３９】
以上において説明した第１実施形態によれば、クエリ間の関連性を正確かつ簡単に把握することができる。
【００４０】
＜第２実施形態＞
以下、第２実施形態について説明する。第１実施形態と比較して、第２実施形態の情報処理装置７は、分類部１６におけるクエリの分類処理が異なる。このため、構成などについては第１実施形態で説明した図および関連する記載を援用し、詳細な説明を省略する。
【００４１】
［情報処理装置の処理］
次に、図９を参照しながら情報処理装置７の動作について説明する。図９は、第２実施形態における情報処理装置７の処理の一例を示すフローチャートである。
【００４２】
まず、取得部１０は、履歴情報を検索サーバ５から取得し、記憶部１８に記憶させる（ステップＳ２０１）。
【００４３】
次に、関連度算出部１２は、記憶部１８から履歴情報を読み出し、読み出した履歴情報に基づいて重複検索スコアを算出する（ステップＳ２０３）。関連度算出部１２は、重複検索スコア情報を記憶部１８に記憶させる。
【００４４】
次に、生成部１４は、記憶部１８から重複検索スコア情報を読み出して、クエリ間の関連性を示すグラフデータを生成する（ステップＳ２０５）。例えば、生成部１４は、図１０に示すようなクエリ間の関連性を示すグラフデータを生成する。図１０に示すグラフデータにおいては、計１０個のクエリがノードＡからＪとして示されている。
【００４５】
次に、分類部１６は、生成したグラフデータにおいて、処理対象とする１つのノードをランダムに選択する（ステップＳ２０７）。次に、分類部１６は、選択したノードを基準として、所定のリンク数以内で接続されたクエリを１つのグループに分類する（ステップＳ２０９）。
【００４６】
図１１は、図１０に示されたグラフデータに対するノード処理の一例を説明する図である。図１１のステップＳ２０７およびＳ２０９（１回目）に示されるように、分類部１６は、例えば、処理対象のノードとしてノードＪを選択する。次に、分類部１６は、ノードＪを基準として、例えば、リンク数が３以内で接続されたノードを同一のグループ（Ｊグループ）に属するノードとして分類する。リンク数が３以内で接続されたノードには、ノードＪとリンクＬ１１を介して直接的に接続されたノードＩ（リンク数１）と、ノードＪとリンクＬ１１およびＬ１０を介して接続されたノードＨ（リンク数２）と、ノードＪとリンクＬ１１、Ｌ１０、およびＬ９を介して接続されたノードＧ（リンク数３）と、ノードＪとリンクＬ１１、Ｌ１０、およびＬ８を介して接続されたノードＢ（リンク数３）とが含まれる。
【００４７】
次に、分類部１６は、全てのノードの分類処理が完了したか否かを判定する（ステップＳ２１１）。分類部１６は、全てのノードの分類処理が完了していないと判定した場合、ノードの分類処理が完了していないノードの中から、処理対象とする１つのノードをランダムに選択し、上記の分類処理を再度行う。
【００４８】
図１１に示す例においてノードＪを基準とした分類が完了した後には、未分類のノードであるノードＡ、Ｃ、Ｄ、Ｅ、およびＦが存在する。このため、分類部１６は、全てのノードの分類処理が完了していないと判定し、ノードＡ、Ｃ、Ｄ、Ｅ、およびＦの中から、処理対象とする１つのノードをランダムに選択し、上記の分類処理を行う。図１１のステップＳ２０７およびＳ２０９（２回目）に示されるように、分類部１６は、例えば、処理対象とするノードとしてノードＦを選択する。
【００４９】
次に、分類部１６は、ノードＦを基準として、例えば、リンク数が３以内で接続されたノードを同一のグループ（Ｆグループ）に属するノードとして分類する。リンク数が３以内で接続されたノードには、ノードＦとリンクＬ１を介して直接的に接続されたノードＥ（リンク数１）と、ノードＦとリンクＬ１およびＬ２を介して接続されたノードＡ（リンク数２）と、ノードＦとリンクＬ１、Ｌ２、およびＬ４を介して接続されたノードＤ（リンク数３）と、ノードＦとリンクＬ１、Ｌ２、およびＬ５を介して接続されたノードＢ（リンク数３）と、ノードＦとリンクＬ１、Ｌ２、およびＬ３を介して接続されたノードＣ（リンク数３）とが含まれる。
【００５０】
ここで、ノードＢは、ノードＪを基準としたグループ（Ｊグループ）と、ノードＦを基準としたグループ（Ｆグループ）との双方に所属することになる。このように、クエリのランダムな選択を複数回行うことにより、１つのノードが複数のグループに所属することになった場合には、分類部１６は、このノードと、このノードの接続先の各ノードとの重複検索スコアの大きさに基づいて、いずれのグループに分類するかを決定する。
【００５１】
例えば、ノードＪを基準とした分類処理においてノードＪからノードＢに至る経路上のノードＢと接続されたリンク（図１１に示す例では、リンクＬ８（１０））と、ノードＦを基準とした分類処理においてノードＦからノードＢに至る経路上のノードＢと接続されたリンク（図１１に示す例では、リンクＬ５（８））とでは、リンクＬ５（８）よりもリンクＬ８（１０）の重複検索スコアが高い。この場合、ノードＢは、重複検索スコアが高い（すなわち、Ｊグループとの結び付きが強い）と考えられるため、分類部１６は、ノードＢをＪグループに分類する。なお、ノードＪを基準としたリンクＬ８と、ノードＦを基準としたリンクＬ５との重複検索スコアが互いに同じである場合には、分類部１６は、ノードＢを任意の一方のグループに分類してよい。
【００５２】
一方、分類部１６は、全てのノードの分類処理が完了したと判定した場合、分類結果を記憶部１８に記憶させる。以上により、情報処理装置７は、本フローチャートの処理を終了する。
【００５３】
以上において説明した第２実施形態によれば、クエリ間の関連性を正確かつ簡単に把握することができる。また、処理対象とする１つのノードをランダムに選択して、この選択したノードを基準とした分類処理を行うことで処理を簡略化することができる。
【００５４】
＜第３実施形態＞
以下、第３実施形態について説明する。第１実施形態と比較して、第３実施形態の情報処理装置７は、分類部１６におけるクエリの分類処理が異なる。このため、構成などについては第１実施形態で説明した図および関連する記載を援用し、詳細な説明を省略する。
【００５５】
［情報処理装置の処理］
次に、図１２を参照しながら情報処理装置７の動作について説明する。多くのクエリと関連付けされるクエリは、スパムなどによって不正に検索が行われたキーワードである場合がある。このような多くのクエリと関連付けされるクエリを含む履歴情報に対して処理を行うと、クエリ間の関連性が複雑化し、分類処理の精度が低下する場合がある。そこで、本実施形態の情報処理装置７では、所定数以上のクエリと関連付けされるクエリを削除し、削除したクエリ以外のクエリについて分類処理を行う。図１２は、第３実施形態における情報処理装置７の処理の一例を示すフローチャートである。
【００５６】
まず、取得部１０は、履歴情報を検索サーバ５から取得し、記憶部１８に記憶させる（ステップＳ３０１）。
【００５７】
次に、関連度算出部１２は、記憶部１８から履歴情報を読み出し、読み出した履歴情報に基づいて重複検索スコアを算出する（ステップＳ３０３）。関連度算出部１２は、重複検索スコア情報を記憶部１８に記憶させる。
【００５８】
次に、生成部１４は、記憶部１８から重複検索スコア情報を読み出して、クエリ間の関連性を示すグラフデータを生成する（ステップＳ３０５）。例えば、生成部１４は、図１３に示すようなクエリ間の関連性を示すグラフデータを生成する。図１３に示すグラフデータにおいては、計１０個のクエリがノードＡからＪとして示されている。
【００５９】
次に、生成部１４は、生成したグラフデータにおいて、接続先のノードの数が所定数以上であるノードを削除する（ステップＳ３０７）。図１４は、図１３に示されたグラフデータに対するノード処理の一例を説明する図である。図１４のステップＳ３０７に示されるように、生成部１４は、接続先のノードの数が所定数以上である（図１４に示す例では、接続先のノードの数が５つ以上）ノードＢを削除する。これにより、ノードＩは、接続先を有さないノードとなる。この場合、分類部１６は、ノードＩは、Ｉグループに属するノードとして分類する。
【００６０】
次に、生成部１４は、接続先のノードの数が１つである末端ノードの処理を行う（ステップＳ３０９）。図１４に示す例においてノードＢが削除された後のグラフデータにおいては、２つの末端ノード（ノードＤおよびノードＦ）が存在する。図１４のステップＳ３０９（１回目）に示されるように、生成部１４は、例えば、処理対象の末端ノードとしてノードＤを選択し、選択したノードＤを「子ノード」とし、ノードＤの接続先であるノードＡをノードＤの「親ノード」として親子関係を設定する。
【００６１】
次に、生成部１４は、全ての末端ノードの処理が完了したか否かを判定する（ステップＳ３１１）。生成部１４は、全ての末端ノードの処理が完了していないと判定した場合、未処理の末端ノードに対して上記の親子関係の設定を行う。図１４に示す例においてノードＤの処理が完了した後には、未処理の末端ノードであるノードＦが存在する。このため、図１４のステップＳ３０９（２回目）に示されるように、生成部１４は、処理対象の末端ノードとしてノードＦを選択し、選択したノードＦを「子ノード」とし、ノードＦの接続先であるノードＥをノードＦの「親ノード」として親子関係を設定する。
【００６２】
一方、生成部１４が全ての末端ノードの処理が完了したと判定した場合、分類部１６は、グラフデータにおける複数のノードの中から処理対象とする１つのノードをランダムに選択する（ステップＳ３１３）。次に、分類部１６は、選択したノードを基準として、所定のリンク数以内で接続されたクエリを１つのグループに分類する（ステップＳ３１５）。例えば、図１４のステップＳ３１３およびＳ３１５（１回目）に示されるように、分類部１６は、例えば、処理対象とするノードとしてノードＪを選択する。次に、分類部１６は、ノードＪを基準として、例えば、リンク数が３以内で接続されたノードを同一のグループ（Ｊグループ）に属するノードとして分類する。リンク数が３以内で接続されたノードには、ノードＪとリンクＬ１１を介して直接的に接続されたノードＨ（リンク数１）と、ノードＪとリンクＬ１２を介して直接的に接続されたノードＧ（リンク数１）とが含まれる。
【００６３】
次に、分類部１６は、全てのノードの分類処理が完了したか否かを判定する（ステップＳ３１７）。分類部１６は、全てのノードの分類処理が完了していないと判定した場合、ノードの分類処理が完了していないノードの中から、処理対象とする１つのノードをランダムに選択し、上記の分類処理を再度行う。
【００６４】
図１４に示す例においてノードＪを基準とした分類が完了した後には、未分類のノードであるノードＡ、Ｃ、およびＥが存在する。このため、分類部１６は、全てのノードの分類処理が完了していないと判定し、ノードＡ、Ｃ、およびＥの中から、処理対象とする１つのノードをランダムに選択し、上記の分類処理を行う。図１４のステップＳ３１３およびＳ３１５（２回目）に示されるように、分類部１６は、例えば、処理対象とするノードとしてノードＣを選択する。次に、分類部１６は、ノードＣを基準として、例えば、リンク数が３以内で接続されたノードを同一のグループ（Ｃグループ）に属するノードとして分類する。リンク数が３以内で接続されたノードには、ノードＣとリンクＬ３を介して直接的に接続されたノードＡ（リンク数１）と、ノードＣとリンクＬ１３を介して直接的に接続されたノードＥ（リンク数１）とが含まれる。
【００６５】
また、上記の末端ノード処理において、ノードＡ（親ノード）の子ノードと設定されたノードＤ、およびノードＥ（親ノード）の子ノードと設定されたノードＦは、親ノードと同じグループ（Ｃグループ）に所属するノードとして分類される。
【００６６】
一方、分類部１６は、全てのノードの分類処理が完了したと判定した場合、分類結果を記憶部１８に記憶させる。以上により、情報処理装置７は、本フローチャートの処理を終了する。
【００６７】
以上において説明した第３実施形態によれば、クエリ間の関連性を正確かつ簡単に把握することができる。また、多くのクエリと関連付けされるクエリを削除することで、クエリ間の関連性の複雑化を回避でき、クエリの分類処理の精度を向上させることができる。
【００６８】
＜第４実施形態＞
以下、第４実施形態について説明する。第１実施形態と比較して、第４実施形態の情報処理システムが、広告情報処理装置をさらに備える点が異なる。このため、構成などについては第１実施形態で説明した図および関連する記載を援用し、詳細な説明を省略する。
【００６９】
図１５は、広告情報処理システム１Ａの構成図である。広告情報処理システム１Ａは、例えば、図１に示す端末装置３、検索サーバ５、および情報処理装置７に加えて、広告情報処理装置９を備える。広告情報処理装置９は、検索サーバ５および情報処理装置７と接続されている。
【００７０】
［広告情報処理装置］
広告情報処理装置９は、情報処理装置７から出力されたクエリの分類結果に基づいて、検索サーバ５が端末装置３から受信したクエリに応じた広告情報を決定する。広告情報処理装置９は、決定した広告情報を検索サーバ５に出力する。検索サーバ５は、端末装置３から受信したクエリに対する検索の結果とともに、広告情報処理装置９から入力された広告情報を端末装置３に送信する。
【００７１】
例えば、広告情報処理装置９は、複数の広告情報と、広告情報の各々と関連付けされたクエリとを記憶する記憶部（図示しない）を備えている。広告情報処理装置９は、上記の第１から第３実施形態における情報処理装置７によって出力された分類結果に基づいて、検索サーバ５が端末装置３から受信したクエリと関連付けされた広告情報、あるいは、このクエリと同じグループに分類された他のクエリと関連付けされた広告情報を検索サーバ５に出力する。
【００７２】
上記の第４実施形態の広告情報処理システム１Ａによれば、端末装置３のユーザが入力したクエリに適した広告情報を、端末装置３に提供することができる。これにより、広告効果の高いサービスを実現することができる。
【００７３】
上記の実施形態では、クエリ間の重複検索スコアに基づいてクエリを分類する方法について説明した。なお、クエリの分類を行う場合には、クエリが検索された時間に関する情報があわせて使用されてもよい。例えば、分類部１６は、検索サーバ５から取得した履歴情報と、検索サーバ５が端末装置３から各クエリを受信した時間に関する情報とが関連付けされた情報を用いて、クエリ間の関連性を示すグラフデータを生成してもよい。このグラフデータにおいては、関連付けされたクエリ間における時間的な検索の順序が有向グラフによって示されている。また、検索サーバ５が端末装置３から各クエリを受信した時間（検索時間）または各クエリ間の検索時間の差分が、各ノードまたはリンクに紐付けされている。このようなグラフデータを生成することで、例えば、あるユーザは、クエリＡを検索した後にクエリＢを検索しているといった検索の時系列情報を把握することができ、クエリの分類をより詳細に行うことができる。
【００７４】
以上、本発明を実施するための形態について実施形態を用いて説明したが、本発明はこうした実施形態に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【符号の説明】
【００７５】
１‥情報処理システム、１Ａ‥広告情報処理システム、３‥端末装置、５‥検索サーバ、７‥情報処理装置、９‥広告情報処理装置、１０‥取得部、１２‥関連度算出部、１４‥生成部、１６‥分類部、１８‥記憶部、ＮＷ‥ネットワーク
【図１】
2018151789.tif 000004
【図２】
2018151789.tif 000005
【図３】
2018151789.tif 000006
【図４】
2018151789.tif 000007
【図５】
2018151789.tif 000008
【図６】
2018151789.tif 000009
【図７】
2018151789.tif 000010
【図８】
2018151789.tif 000011
【図９】
2018151789.tif 000012
【図１０】
2018151789.tif 000013
【図１１】
2018151789.tif 000014
【図１２】
2018151789.tif 000015
【図１３】
2018151789.tif 000016
【図１４】
2018151789.tif 000017
【図１５】
2018151789.tif 000018