(57)【特許請求の範囲】
【請求項１】
テキスト文書群を検索する情報検索装置であって、
人の間の関係を示すソーシャルグラフを格納したソーシャルグラフ記憶手段と、
検索対象文書を格納した検索対象文書記憶手段と、
文書と人との関係情報を格納した人・文書関係情報記憶手段と、
検索前に、人単位で、該人に関係する文書群に対するインデックスを構築し、インデックス記憶手段に格納するインデックス構築手段と、
検索者を一意に識別する検索者ＩＤと検索条件が入力されると、該検索者ＩＤの検索者を起点として前記ソーシャルグラフ記憶手段のソーシャルグラフの範囲を広げて探索し、探索された距離が近い人のインデックスを前記インデックス記憶手段を参照して取得し、入力された前記検索条件と該インデックスを用いて前記検索対象文書記憶手段を検索する検索手段と、
検索された文書の上位Ｎ件を前記検索者の情報端末に出力する出力手段と、
を有することを特徴とする情報検索装置。
【請求項２】
前記検索手段で検索された文書に対して、文書と前記検索条件との適合度の値、及び前記ソーシャルグラフ記憶手段のソーシャルグラフにおける検索者から該文書に関係する人への距離の値を用いて該文書のスコア値を算出するスコア算出手段と、
これから探索する人と前記検索者との距離と、文書がとり得る適合度の上限値を用いて、これから探索する人に関係する文書がとり得る最大のスコアを導出し、前記スコア算出手段で算出された検索途中の文書の最低スコアと導出された最大のスコアとを比較し、該最大のスコアが該最低のスコアを超えないと判断できた時点で前記ソーシャルグラフの探索を終了する手段と、
を有する請求項１記載の情報検索装置。
【請求項３】
請求項１または２に記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索装置及びプログラムに係り、特に、多数の情報（文書やデータ）の中から、検索条件に適合する情報を検索する情報検索装置及びプログラムに関する。
【０００２】
詳しくは、検索者に関わる別の情報を利用して、検索結果をパーソナライズする情報検索装置及びプログラムに関する。
【０００３】
特に、本発明は、検索結果を表すソーシャルグラフの情報を用いて、文書やデータをランキングする情報検索装置及びプログラムに関する。
【背景技術】
【０００４】
典型的なパーソナライズ検索の例として、「ジャガー」という検索条件を入力した場合に、動物好きの人に対しては動物のジャガーを提示した方が適切であるし、また、車好きの人に対してはジャガー社の車を提示する方が望ましい。しかし、Ｗｅｂの検索エンジンやデータベース管理システムに代表される従来のパーソナライズ機能を持たない検索装置では、入力される検索条件と蓄積されている文書・データをもとに、検索結果を決定していた。
【０００５】
また、パーソナライズ機能に関する既存の検索技術としては、利用者のＷｅｂブラウザのブックマークを利用するもの（例えば、非特許文献１、２参照）、クリックログを利用するもの（例えば、非特許文献３参照）が挙げられる。
【非特許文献１】Glen Jeh, Jennifer Widom, "Scaling personalized web search,"  International World Wide Web conference, Pages: 271-279,2003
【非特許文献２】"Personalized search." Communications of the ACM vol. 45, No.9, Pages:50-55, 2002.
【非特許文献３】Zhicheng Dou, Ruihua Song, Ji-Rong Wen, "A Large-scale Evaluation and Analysis of Personalized Search Strategies", International World Wide Web Conference, Pages: 581-590 2007.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のパーソナライズ機能を持たない検索技術では、同一の検索条件に対して、検索毎に異なる趣味趣向を検索結果に反映することができないという問題があった。また、パーソナライズ機能を有する技術についても、文書やデータに関係する人（著作情報等）と検索者の距離を用いて検索結果をパーソナライズする検索技術は過去に知られていない。
【０００７】
人が信頼できる情報を得る方法の一つとして、友人から友人へと情報を伝播するクチコミの方法があげられる。
【０００８】
本発明は、上記の点に鑑みなされたもので、クチコミ情報が上位ランキングされるように検索結果をパーソナライズすることが可能な情報検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明は、テキスト文書群を検索する情報検索方法であって、
人の間の関係を示すソーシャルグラフを格納したソーシャルグラフ記憶手段と、
検索対象文書を格納した検索対象文書記憶手段と、
文書と人との関係情報を格納した人・文書関係情報記憶手段と、を有する情報検索装置において、
検索者を一意に識別する検索者ＩＤと検索条件が入力される（ステップ１）と、
検索者ＩＤに基づいてソーシャルグラフ記憶手段を検索し、該検索者ＩＤの検索者と距離が近い人のＩＤを検索し（ステップ２）、該距離が近い人のＩＤに基づいて人・文書関係情報記憶手段から該距離が近い人のＩＤに関係する文書を検索し（ステップ３）、該文書を検索対象文書として、検索条件で検索対象文書記憶手段を検索する（ステップ４）検索ステップと、
検索された文書の上位Ｎ件を検索者の情報端末に出力する出力ステップ（ステップ５）と、を行う。
【００１１】
図２は、本発明の原理構成図である。
【００１２】
本発明（請求項１）は、テキスト文書群を検索する情報検索装置であって、
人の間の関係を示すソーシャルグラフを格納したソーシャルグラフ記憶手段１３と、
検索対象文書を格納した検索対象文書記憶手段５と、
文書と人との関係情報を格納した人・文書関係情報記憶手段４と、
検索前に、人単位で、該人に関係する文書群に対するインデックスを構築し、インデックス記憶手段に格納するインデックス構築手段と、
検索者を一意に識別する検索者ＩＤと検索条件が入力されると、該検索者ＩＤの検索者を起点としてソーシャルグラフ記憶手段１３のソーシャルグラフの範囲を広げて探索し、探索された距離が近い人のインデックスをインデックス記憶手段を参照して取得し、入力された検索条件と該インデックスを用いて検索対象文書記憶手段を検索する検索手段１と、
検索された文書の上位Ｎ件を検索者の情報端末に出力する出力手段１３と、を有する。
【００１３】
また、本発明（請求項２）は、検索手段１で検索された文書に対して、文書と検索条件との適合度の値、及びソーシャルグラフ記憶手段のソーシャルグラフにおける検索者から該文書に関係する人への距離の値を用いて該文書のスコア値を算出するスコア算出手段と、
これから探索する人と検索者との距離と、文書がとり得る適合度の上限値を用いて、これから探索する人に関係する文書がとり得る最大のスコアを導出し、スコア算出手段で算出された検索途中の文書の最低スコアと導出された最大のスコアとを比較し、該最大のスコアが該最低のスコアを超えないと判断できた時点でソーシャルグラフの探索を終了する手段と、を有する。
【００１６】
本発明（請求項３）は、請求項１または２に記載の情報検索装置を構成する各手段としてコンピュータを機能させるための情報検索プログラムである。
【発明の効果】
【００１７】
従来は、Ｗｅｂブラウザのブックマークや利用者のクリックログを利用するものであるのに対し、本発明では、人の間の関係を利用してランキングすることで、検索者との距離の近い人に関係する文書を、検索結果の上位にランキングすることが可能となる。
【００１８】
また、本発明では、従来から用いられている文書と検索条件との適合度の値に加えて、ソーシャルグラフにおける検索者と該文書に関係する人の距離に基づきスコア値を算出し、検索結果の文書順を決定する。これにより、情報が人伝いに伝播する距離を加味して検索結果のランキングを行うことができる。
【００１９】
また、本発明では、事前に人単位でその人に関係する文書群に対してインデックスを構築し、検索時には、検索者の起点とし、入力される検索条件とソーシャルグラフにおいて検索者に近い人のインデックスを用いて、適合度の高い文書を検索し、順次検索者から距離の遠い人へとソーシャルグラフの探索を繰り返し、探索先の人のインデックスを用いて文書の検索を行い、検索結果候補を構築する。これにより、既存のインデックス技術を利用することで、高速に検索処理を行うことができる。
【００２０】
更に、本発明では、検索者が検索件数を指定して検索を行う場合、検索者を起点としてソーシャルグラフを遠方へと探索する際に、検索途中で得られた最低スコアの文書とこれから探索する人に関係する文書がとり得る最大のスコアとを比較し、後者スコアが前者スコアを超えないことが判断できた時点で、探索を終了する。これにより、情報の全検索を避けることで、検索処理の更なる高速化を行うことができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図３は、本発明の一実施の形態におけるソーシャル情報検索装置の構成図である。
【００２３】
ソーシャル情報検索装置１０は、情報検索部１、インデックス構築部２、ソーシャルグラフ記憶部３、人と文書の関係情報記憶部（以下、単に関係情報記憶部と記す）４、検索対象文書蓄積部５、インデックス記憶部６から構成される。
【００２４】
ここで、ソーシャルグラフ記憶部３、関係情報記憶部４、検索対象文書蓄積部５、インデックス記憶部６は、ディスク装置等の記憶手段である。インデックス記憶部６は、転置ファイルやＢ+-treeなどの検索処理を高速化するためのデータ構造を有する。
【００２５】
図４は、本発明の一実施の形態におけるソーシャルグラフ記憶部のソーシャルグラフの例を示す。
【００２６】
同図において、点は人を表しており、人から人への関係は点の間を接続する矢印として表現されている。簡略化のため、両端に矢印を持つ線を用いて双方向の矢印を表現しており、人のＩＤと人から人への距離がソーシャルグラフ記憶部３に格納されている。
【００２７】
例えば、mixiなどのソーシャル・ネットワーキング・サービスでは、ある人Ａが別の人Ｂの日記を見たことを「足あと」として記録するが、これは、ＡからＢへの関係として表現することができる。同様に、Ａが別の人Ｂの日記に対して「コメント」を加えた場合も、ＡからＢへの関係と捉えることができる。また、ＡとＢとが「友人」の関係にある場合は、ＡとＢとの双方向の関係として表現することができる。ソーシャルグラフを構成する際には、これらの「足あと」「コメント」「友人関係」の情報のいずれか１つ以上を用いて構成すればよい。また、人から人への距離は、ソーシャルグラフにおけるホップ数（ノード間の距離）によって決められるか、もしくは、参照（足あと）と情報の追加（コメント）の要因の線形和により定義される距離により定義されるかの、いずれかの方法がある。
【００２８】
例えば、検索条件Ｑに関するＡからＢへの距離は、ＡとＢがソーシャルグラフにおいて隣接する場合には、次の式で定義する例があげられる。
【００２９】
式１）
距離（Ａ，Ｂ，Ｑ）＝
α×｛Ａが情報の追加をしたＱにマッチするＡの全友人の文書数｝
／｛Ａが情報の追加をしたＱにマッチするＢの文書数｝
＋β×｛Ａが参照したＱにマッチするＡの全友人の文書数｝
／｛Ａが参照したＱにマッチするＢの文書数｝
但し、α、βは線形和と正規化のための数値であるとする。
【００３０】
また、ＡとＢがソーシャルグラフにおいて隣接しない場合には、ソーシャルグラフ上でＡからＢへの到達可能パスを求めパスを構成する任意の２つのノード間の距離を式１で求めた値の総和を、ＡからＢへの距離として定義する。到達パスが複数ある場合は、疎の最小値をＡからＢへの距離として定義する。
【００３１】
別の距離の表現として、グラフにおけるホップ数で定義される距離は次の式で与えられる。
【００３２】
式２）
距離（Ａ，Ｂ）＝｛ＡからＢへの最短パス長｝
文書スコアが満たすべき特徴は、検索条件に対する文書の適合度が高ければ文書のスコアを高くし、且つ、検索者からその文書の著者への距離が大きいほど文書のスコアを低くする、を満たす必要がある。その一例として、次の式で定義される文書スコアが挙げられる。
【００３３】
式３）
文書スコア（ｔ）＝（検索条件に対する文書ｔの適合度）／（検索者から文書ｔの著者への距離）
なお、式３における、「検索者からの文書ｔの適合度」は、転置ファイルなどの既存手法により算出される適合度であり、「検索者から文書ｔの著者への距離」はソーシャルグラフにより得られる数値である。
【００３４】
図５は、本発明の一実施の形態における人と文書の関係情報記憶部の例を示す。当該人と文書の関係情報記憶部４には、人の人ＩＤと当該人との関係（距離）と当該人ＩＤに関係する文書ＩＤが格納される。
【００３５】
図６５は、本発明の一実施の形態におけるインデックス記憶部の例を示しており、ある人Ａに関係する文書に対するインデックスの例である。同図において、ある単語に関係する文書ＩＤ（ｄ１，ｄ５，…）、文書内の単語の出現頻度等の文書にかかる値（ｔ１５、ｔ８）が格納される。
【００３６】
図７は、本発明の一実施の形態における情報検索部の構成を示す。
【００３７】
同図に示す情報検索部１は、検索部１１、スコア算出部１２、検索結果選択部１３、メモリＡ１４，メモリＢ１５から構成される。
【００３８】
検索部１１は、情報端末２０から、検索者を特定する情報（以下では、検索者ＩＤと記す）と検索条件が入力されると、ソーシャルグラフ記憶部３に格納されたソーシャルグラフ、人と文書の関係情報記憶部４に格納された人と文書の関係序情報、インデックス記憶部６に格納されたインデックス情報を検索し、メモリＡ１４に格納する。
【００３９】
スコア算出部１２は、検索者と検索された人の距離を用いてスコアを算出し、検索結果候補としてメモリＢ１５に格納する。
【００４０】
検索結果選択部１３は、インデックス記憶部６内のインデックスの取り得る最高のスコアがスコア算出部１２で算出された上位n件のスコアを超えない時点において、メモリＢ１５の検索候補の上位ｎを選択して情報端末２０に出力する。
【００４１】
インデックス構築部２は、情報検索部１の検索処理の高速化のために、検索処理の前に、検索対象文書蓄積部５より文書を読み込み、人単位でその人に関係する文書群に対してインデックスを構築し、インデックス記憶部６に格納する。これにより、情報検索部１において、検索者を起点として、入力された検索条件とソーシャルグラフにおいて検索者に隣接する人のインデックスを用いて適合度の高い文書を検索する。
【００４２】
次に、上記の構成における動作を説明する。
【００４３】
図８は、本発明の一実施の形態におけるインデックス構築部のフローチャートである。
【００４４】
ステップ１０１）  インデックス構築部２は、検索対象文書蓄積部５から検索対象となる文書を読み込む。
【００４５】
ステップ１０２）  次に、人と文書の関係情報記憶部４から人と文書の関係情報を読み込み、文書を関係する人毎にグループ化する。
【００４６】
ステップ１０３）  インデックスの構築を終了していない人を選択し、その人に係る文書群に対して、インデックスを構築して、インデックス記憶部６に格納する。インデックスの構築方法としては、転置ファイルによる方法や、B+-treeによる方法等がある。
【００４７】
ステップ１０４）  全ての検索体操文書に対する処理が完了したかを判定し、完了している場合には、当該インデックス構築処理を終了し、完了していない場合には、ステップ１０５に移行する。
【００４８】
ステップ１０５）  人と文書の関係情報のうち、処理が終了していない人を選択し、ステップ１０３に移行する。
【００４９】
次に、上記のインデックスの構築の処理が完了しているものとして、情報検索部１の処理を説明する。
【００５０】
図９は、本発明の一実施の形態における情報検索部のフローチャートである。
【００５１】
ステップ２０１）  情報端末２０から検索者を特定する情報（検索者ＩＤ）と検索者が入力する検索条件（検索式）及び出力される上位件数（Ｎ件）を入力する。
【００５２】
ステップ２０２）  情報検索部１の検索部１１は、検索者ＩＤに基づいて、ソーシャルグラフ記憶部３からソーシャルグラフを取得して、人の探索の開始点を変数Ｓに設定し、検索結果候補を空（＝｛｝）に初期化する。Ｓは、探索済みの人の集合を保持する変数であり、当該情報検索部１のメモリＡ１４に格納されている。
【００５３】
ステップ２０３）  検索部１１は、変数Ｓに含まれる任意の人から最も距離の近い人ｓ（但し、Ｓに含まれない）をソーシャルグラフから特定して、変数Ｓに追加する。
【００５４】
ステップ２０４）  ｓと入力された検索条件に基づいて、インデックス記憶部６を検索し、スコア算出部１２において、得られた文書に対して上記の式３）を用いてスコアを計算して、検索結果候補として、メモリＢ１５に格納する。なお、インデックスを用いた検索条件の処理の方法としては、転置ファイルによる方法やB+-treeによる方法等がある。
【００５５】
ステップ２０５）  これまでの検索結果候補の最小スコアと今後探索して得られる文書の最大スコアを比較して、後者のスコアが前者のスコアを越えないと場合（Ｙｅｓ）は、探索を終了し、そうでない場合（Ｎｏ）、更にソーシャルグラフ記憶部３の探索を続ける。
【００５６】
今後探索して得られる文書の最大スコアは、前述の式１もしくは式２から得られる距離と、文書がとり得る適合度の上限値を用いて、式３から導出することができる。
【００５７】
ステップ２０６）最後に、検索結果選択部１３において、メモリＢ１５に格納されている検索結果候補を情報端末２０に出力することで、検索者に結果を提示する。
【００５８】
次に、上記の情報検索処理について詳細に説明する。
【００５９】
以下では、人の距離としてソーシャルグラフのホップ数を利用し、検索者はＡであり、検索条件は"出張"という単語を含む文書を探す条件を示し、検索結果は上位２０件を求めるものとして説明する。
【００６０】
図９は、本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ１）である。
【００６１】
情報検索部１の検索部１１は、検索者を特定する情報（検索者ＩＤ：Ａ）と当該検索者Ａが入力する検索条件が情報端末２０から入力されると、検索者ＩＤ（Ａ）に基づいてソーシャルグラフ記憶部３からホップ数＝１のソーシャルグラフを取得する。図９の例において取得されるのは、Ｇ，Ｈ，Ｃ，Ｅである。次に、検索部１１は、取得した当該ソーシャルグラフ（Ｇ，Ｈ，Ｃ，Ｅ）に基づいて、インデックス記憶部６を参照し、検索者であるＡを中心としてＡからホップ数＝１の人であるＧ、Ｈ，Ｃ，Ｅの人の文書に関する文書に関するインデックスと、入力された検索条件"出張"に基づいて検索結果候補を取得し、メモリＡ１４に格納する。
【００６２】
次に、スコア算出部１２は、メモリＡ１４から検索候補を読み出して、Ａからの距離である"１"を用いて文書スコアを算出する。当該文書スコアに基づいて検索結果候補をソートし、メモリＢ１５に格納する。
【００６３】
図１０は、本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ２）である。
【００６４】
検索部１１は、検索者Ａからホップ数＝２でソーシャルグラフ記憶部３を検索し、取得した人Ｊ，Ｋ，Ｄ，Ｂ，Ｆに基づいてインデックス記憶部６を検索し、得られたインデックスを用いて、検索条件"出張"に基づいて検索し、メモリＡ１４に格納する。
【００６５】
スコア算出部１２は、メモリＡ１４から検索候補を取得し、Ａからの距離"２"を用いて、文書のスコアを算出し、スコアに基づいて検索候補をソートして、スコアと共に当該検索候補をメモリＢ１５の検索結果候補に追加する。この時点で検索結果候補の最低スコアである２０位の文書スコアは３．４であると仮定する。
【００６６】
図１１は、本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ３）である。
【００６７】
ここでは、上記と同様にして、検索者Ａからホップ数＝３で探索される人のインデックスを用いて検索条件"出張"に基づいて検索する。検索された文書がとり得る適合度の上限値を１．０と仮定した場合、ここでは、ホップ数が"３"であるため、上記の式３により、最大のスコアは、
文書スコア＝１．０／３＝３．３となる。
【００６８】
仮に現在の２０位の文書スコアが３．４であるとすると、ホップ数３以降で、３．４のスコアを超える文書は見つからないことが判定できる。この場合は、２０位までの検索結果が確定し、ソーシャルグラフの探索を終了して、図１２の過程までの検索結果候補を最終結果として情報端末２０に返却する。
【００６９】
上記の図３、図７に示す構成要素の動作をプログラムとして構築し、当該情報検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７０】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００７１】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００７２】
本発明は、人と文書との関係性を有する文書検索技術に適用可能である。
【図面の簡単な説明】
【００７３】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるソーシャル情報検索装置の構成図である。
【図４】本発明の一実施の形態におけるソーシャルグラフの構成を示す図である。
【図５】本発明の一実施の形態における人と文書の関係情報記憶部の例である。
【図６】本発明の一実施の形態におけるインデックス記憶部の例である。
【図７】本発明の一実施の形態における情報検索部の構成図である。
【図８】本発明の一実施の形態におけるインデックス構築部のフローチャートである。
【図９】本発明の一実施の形態における情報検索部のフローチャートである。
【図１０】本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ１）である。
【図１１】本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ２）である。
【図１２】本発明の一実施の形態における検索処理の詳細な動作を示す図（ステップ３）である。
【符号の説明】
【００７４】
１  検索手段、情報検索部
２  インデックス構築部
３  ソーシャルグラフ記憶手段、ソーシャルグラフ記憶部
４  人・文書関係情報記憶手段、人と文書の関係情報記憶部
５  検索対象文書記憶手段、検索対象文書蓄積部
６  インデックス記憶部
１１  検索部
１２  スコア算出部
１３  出力手段、検索結果選択部
１４  メモリＡ
１５  メモリＢ
【図１】
0005054593.tif 000002
【図２】
0005054593.tif 000003
【図３】
0005054593.tif 000004
【図４】
0005054593.tif 000005
【図５】
0005054593.tif 000006
【図６】
0005054593.tif 000007
【図７】
0005054593.tif 000008
【図８】
0005054593.tif 000009
【図９】
0005054593.tif 000010
【図１０】
0005054593.tif 000011
【図１１】
0005054593.tif 000012
【図１２】
0005054593.tif 000013