(57)【要約】【課題】よりソーシャルネットワークに適した伝搬方法によってユーザ属性を伝搬することで、ノイズを含んで伝搬してしまう問題を解決し、高精度に未知のユーザ属性を推定する。【解決手段】ソーシャルネットワークの情報と前記ソーシャルネットワークに含まれるユーザの属性集合とに基づき、ユーザ属性が未知であるユーザの属性集合を推定するためのユーザ属性推定装置において、ある属性を有することを仮定した入力ユーザについて、前記ソーシャルネットワーク上で関係のある他のユーザと属性を共有しているほど低く、共有していないほど高くなるユーザコストを算出するユーザコスト算出手段と、前記ソーシャルネットワークに含まれる各ユーザについての前記ユーザコスト算出手段により算出するユーザコストに基づいて、前記ソーシャルネットワークにおける総コストを最小化するようなユーザ属性集合を推定するユーザ属性推定手段と、を備える。【選択図】図１
2014041437.tif 000002
【特許請求の範囲】
【請求項１】
ソーシャルネットワーク記憶部に格納されたソーシャルネットワークの情報と、ユーザ属性記憶部に格納された前記ソーシャルネットワークに含まれるユーザの属性集合とに基づき、ユーザ属性が未知であるユーザの属性集合を推定するためのユーザ属性推定装置であって、
ある属性を有することを仮定した入力ユーザについて、前記ソーシャルネットワーク上で関係のある他のユーザと属性を共有しているほど低く、共有していないほど高くなるユーザコストを算出するユーザコスト算出手段と、
前記ソーシャルネットワークに含まれる各ユーザについての前記ユーザコスト算出手段により算出するユーザコストに基づいて、前記ソーシャルネットワークにおける総コストを最小化するようなユーザ属性集合を推定するユーザ属性推定手段と、
を備えたことを特徴とするユーザ属性推定装置。
【請求項２】
前記ユーザコスト算出手段は、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと関連する関連ユーザ集合を抽出する関連ユーザ集合抽出手段と、
前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間コストを、前記関連ユーザ集合の各関連ユーザについて算出する全関連ユーザ間コスト算出手段とを備え、
前記全関連ユーザ間コスト算出手段により算出されたユーザ間コストを前記関連ユーザ集合について足し合わせることにより前記ユーザコストを算出する
ことを特徴とする請求項１に記載のユーザ属性推定装置。
【請求項３】
前記全関連ユーザ間コスト算出手段は、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間類似度を、前記関連ユーザ集合の各関連ユーザについて算出するユーザ間類似度算出手段と、
前記ユーザ属性記憶部に格納されているユーザ属性に基づいて、前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間属性距離を、前記関連ユーザ集合の各関連ユーザについて算出する算出するユーザ間属性距離算出手段と、
前記ユーザ間類似度算出手段により算出されたユーザ間類似度と前記ユーザ間属性距離算出手段により算出されたユーザ間属性距離とに基づいて、前記ユーザ間コストを算出するユーザ間コスト算出手段と、
を備えることを特徴とする請求項２に記載のユーザ属性推定装置。
【請求項４】
ソーシャルネットワーク記憶部に格納されたソーシャルネットワークの情報と、ユーザ属性記憶部に格納された前記ソーシャルネットワークに含まれるユーザの属性集合とに基づき、ユーザ属性が未知であるユーザの属性集合を推定するためのユーザ属性推定装置が実行するユーザ属性推定方法であって、
ある属性を有することを仮定した入力ユーザについて、前記ソーシャルネットワーク上で関係のある他のユーザと属性を共有しているほど低く、共有していないほど高くなるユーザコストを算出するユーザコスト算出ステップと、
前記ソーシャルネットワークに含まれる各ユーザについての前記ユーザコスト算出ステップにより算出するユーザコストに基づいて、前記ソーシャルネットワークにおける総コストを最小化するようなユーザ属性集合を推定するユーザ属性推定ステップと、
を備えたことを特徴とするユーザ属性推定方法。
【請求項５】
前記ユーザコスト算出ステップは、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと関連する関連ユーザ集合を抽出する関連ユーザ集合抽出ステップと、
前記入力ユーザと前記関連ユーザ集合抽出ステップにより抽出された関連ユーザとの間のユーザ間コストを、前記関連ユーザ集合の各関連ユーザについて算出する全関連ユーザ間コスト算出ステップと、
前記全関連ユーザ間コスト算出ステップにより算出されたユーザ間コストを前記関連ユーザ集合について足し合わせることにより前記ユーザコストを算出するステップと
を備えることを特徴とする請求項４に記載のユーザ属性推定方法。
【請求項６】
前記全関連ユーザ間コスト算出ステップは、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと前記関連ユーザ集合抽出ステップにより抽出された関連ユーザとの間のユーザ間類似度を、前記関連ユーザ集合の各関連ユーザについて算出するユーザ間類似度算出ステップと、
前記ユーザ属性記憶部に格納されているユーザ属性に基づいて、前記入力ユーザと前記関連ユーザ集合抽出ステップにより抽出された関連ユーザとの間のユーザ間属性距離を、前記関連ユーザ集合の各関連ユーザについて算出する算出するユーザ間属性距離算出ステップと、
前記ユーザ間類似度算出ステップにより算出されたユーザ間類似度と前記ユーザ間属性距離算出ステップにより算出されたユーザ間属性距離とに基づいて、前記ユーザ間コストを算出するユーザ間コスト算出ステップと、
を備えることを特徴とする請求項５に記載のユーザ属性推定方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のユーザ属性推定装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザ属性を推定するための技術に係り、特に、ソーシャルネットワークにおいてユーザ属性を公開していないユーザの属性を推定するための技術に関する。
【背景技術】
【０００２】
ユーザ属性を推定するための第１の従来技術として、地理属性とユーザ属性の関係を学習し利用することで、与えられた地理属性から未知のユーザ属性を推定するユーザ属性推定装置がある（例えば、特許文献１参照）。
【０００３】
また、第２の従来技術として、ソーシャルネットワーク上における近さを定義し、近いユーザから属性を伝搬させることによって、未知のユーザ属性を推定するユーザ属性推定装置がある（例えば、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−２３８１６９号公報
【非特許文献】
【０００５】
【非特許文献１】Alan Mislove, Bimal Viswanath, Krishna P. Gummadi, Peter Druschel, "You are who you know: inferring user profiles in online social networks". In Proceedings of the third ACM international conference on Web search and data mining, pages 251-260, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
第１の従来技術と同様の手法を用いることで、ユーザが使う単語や、地理情報、時間情報などの特徴量をもとに、ユーザ属性を推定することができる。例えば、「期末試験」という単語を使うユーザは学生である確率が高い、などとするものである。しかし、これらの情報を持たないような活発でないユーザに対してはユーザ属性を推定することができなかった。
【０００７】
第２の従来技術はその課題に対し、ソーシャルネットワーク上で近い周囲ユーザの属性が与えられるまたは第１の従来技術を利用して推定できる場合に、これを利用し伝搬することによって、活発でないユーザに対してもユーザ属性の推定を可能としている。しかし、ソーシャルネットワーク上で直接の関係がないユーザ、例えば友人の友人といったようなユーザからも属性を伝搬しているため、伝搬される側のユーザが持たない属性まで伝搬してしまう、つまりノイズを含んで伝搬してしまうという問題があった。
【０００８】
本発明は、上記の点に鑑みなされたものであり、よりソーシャルネットワークに適した伝搬方法によってユーザ属性を伝搬することで、ノイズを含んで伝搬してしまう問題を解決し、高精度に未知のユーザ属性を推定することを可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明は、ソーシャルネットワーク記憶部に格納されたソーシャルネットワークの情報と、ユーザ属性記憶部に格納された前記ソーシャルネットワークに含まれるユーザの属性集合とに基づき、ユーザ属性が未知であるユーザの属性集合を推定するためのユーザ属性推定装置であって、
ある属性を有することを仮定した入力ユーザについて、前記ソーシャルネットワーク上で関係のある他のユーザと属性を共有しているほど低く、共有していないほど高くなるユーザコストを算出するユーザコスト算出手段と、
前記ソーシャルネットワークに含まれる各ユーザについての前記ユーザコスト算出手段により算出するユーザコストに基づいて、前記ソーシャルネットワークにおける総コストを最小化するようなユーザ属性集合を推定するユーザ属性推定手段と、を備えたことを特徴とするユーザ属性推定装置として構成される。
【００１０】
前記ユーザコスト算出手段は、例えば、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと関連する関連ユーザ集合を抽出する関連ユーザ集合抽出手段と、
前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間コストを、前記関連ユーザ集合の各関連ユーザについて算出する全関連ユーザ間コスト算出手段とを備え、
前記全関連ユーザ間コスト算出手段により算出されたユーザ間コストを前記関連ユーザ集合について足し合わせることにより前記ユーザコストを算出するように構成することができる。
【００１１】
前記全関連ユーザ間コスト算出手段は、例えば、
前記ソーシャルネットワーク記憶部に格納されているソーシャルネットワーク情報に基づいて、前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間類似度を、前記関連ユーザ集合の各関連ユーザについて算出するユーザ間類似度算出手段と、
前記ユーザ属性記憶部に格納されているユーザ属性に基づいて、前記入力ユーザと前記関連ユーザ集合抽出手段により抽出された関連ユーザとの間のユーザ間属性距離を、前記関連ユーザ集合の各関連ユーザについて算出する算出するユーザ間属性距離算出手段と、
前記ユーザ間類似度算出手段により算出されたユーザ間類似度と前記ユーザ間属性距離算出手段により算出されたユーザ間属性距離とに基づいて、前記ユーザ間コストを算出するユーザ間コスト算出手段とを備えることにより構成することができる。
【００１２】
前記ユーザ属性推定装置は、前記ユーザ属性推定手段により算出された結果に基づいて、属性値を出力する出力手段を更に有してもよい。
【００１３】
また、本発明は、前記ユーザ属性推定装置が実行するユーザ属性推定方法として構成することもできる。また、本発明は、コンピュータを、前記ユーザ属性推定装置における各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１４】
本発明によれば、ソーシャルネットワーク上で関連のあるユーザ間のみで属性を伝搬し、それを例えば全ユーザについて再帰的に繰り返すことで、ソーシャルネットワーク上で関係のないユーザが持つノイズとなるような属性の影響を低減しながら属性を伝搬することができるので、伝搬される側のユーザが持たない属性まで伝搬してしまうという問題を解決し、高精度に未知のユーザ属性を推定することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態におけるユーザ属性推定装置１０の構成図である。
【図２】本発明の実施の形態におけるユーザ属性推定部１２の動作のフローチャートの例である。
【図３】本発明の実施の形態におけるユーザコスト算出部１４の動作のフローチャートである。
【図４】本発明の実施の形態におけるソーシャルネットワーク記憶部１５に格納される情報の例である。
【図５】本発明の実施の形態におけるユーザ属性記憶部１６に格納される情報の例である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１７】
（実施の形態の概要）
まず、本実施の形態の概要について説明する。本実施の形態では、各ユーザはソーシャルネットワーク上で関係のあるユーザとのみ属性を共有しやすいというモデリングを行い、与えられたソーシャルネットワーク全体における総コストを最小化するようにユーザから関連ユーザへと属性を伝搬することで、ユーザ属性が未知であるユーザの属性を推定するものである。すなわち直感的には、あるユーザAと関係のあるユーザBへ、さらにユーザBと関係のあるユーザCへと、再帰的な伝搬が行われるモデリングである。ただしその際、ただ再帰的に伝搬し、最も確率の高い属性のみを考慮する最尤推定ではなく、とりうる全ての属性の可能性を考慮し、その組み合わせを最適化するようなベイズ推定を行う。
【００１８】
ここで、あるユーザがある属性を持つコストはユーザコストと呼び、ソーシャルネットワーク上で関係のあるユーザと属性を共有しているほど低く、共有していないほど高いものとする。また、与えられたソーシャルネットワーク全体におけるコストは総コストと呼び、ユーザコストを全ユーザについて合計したものとする。
【００１９】
（ユーザ属性推定装置１０の構成）
図１は、与えられたソーシャルネットワークとそれに含まれるユーザの属性集合に基づき、ユーザ属性が未知であるユーザの属性を推定するためのユーザ属性推定装置１０のブロック図を示す。
【００２０】
同図に示すように、ユーザ属性推定装置１０は、入力部１１、ユーザ属性推定部１２、ユーザコスト算出部１４、ソーシャルネットワーク記憶部１５、関連ユーザ集合抽出部１７、全関連ユーザ間コスト算出部１８、ユーザ間類似度算出部１９、ユーザ属性記憶部１６、ユーザ間属性距離算出部２０、ユーザ間コスト算出部２１、出力部１３を有する。
【００２１】
本実施の形態に係るユーザ属性推定装置１０は、各記憶部となる記憶装置（メモリ、ハードディスク等）を備えるコンピュータに、入力部１１、ユーザ属性推定部１２、ユーザコスト算出部１４、ソーシャルネットワーク記憶部１５、関連ユーザ集合抽出部１７、全関連ユーザ間コスト算出部１８、ユーザ間類似度算出部１９、ユーザ属性記憶部１６、ユーザ間属性距離算出部２０、ユーザ間コスト算出部２１、出力部１３の処理に対応するプログラムを実行させることにより実現可能である。より具体的には、プログラムに従って、計算対象のデータをメモリ等から読み出し、ＣＰＵにより演算を行って、メモリ等に格納する動作を繰り返しながら処理が実行される。当該プログラムは、可搬メモリ等の記憶媒体に格納して配布し、上記コンピュータにインストールして用いてもよいし、ネットワーク上のサーバからダウンロードして上記コンピュータにインストールしてもよい。また、ソーシャルネットワーク記憶部１５、ユーザ属性記憶部１６のいずれか又は全部を学習及び推論の処理を行うコンピュータ内に備えずに、当該コンピュータからネットワーク経由でアクセス可能な外部装置に備えてもよい。
【００２２】
以下にユーザ属性推定装置１０の各構成・動作をより詳細に説明する。
【００２３】
＜入力部１１＞
入力部１１では、予測したいユーザ集合の情報を入力として受け付ける。そして、ユーザIDなどのユーザの検索キーとなるような情報Uinへの変換を行い、ユーザ属性推定部１２へと出力する。
【００２４】
また、受け付ける情報は、ソーシャルネットワークSまたはソーシャルネットワークの範囲S'であってもよい。その場合は、ソーシャルネットワークSやS'に含まれる全てのユーザ集合または属性が公開されていないユーザ集合を抽出することで入力ユーザ集合Uinを得る。
【００２５】
＜ユーザ属性推定部１２＞
ユーザ属性推定部１２では、入力部１１から入力ユーザ集合Uinを入力として受け付ける。そして、ユーザコスト算出部１４へとユーザuと属性aとイテレーションtにおけるユーザ集合USの属性推定結果AUS,tを出力し、ユーザuが属性aをとった場合のユーザコストC(u,a)を受け取る。ここで、ユーザ集合USとは与えられたソーシャルネットワークSに含まれる全てのユーザの集合である。そして、受け取ったユーザコストC(u,a)に基づいて、実施の形態の概要において述べたモデリングにおける総コストの最小化を行い、出力部１３に対してユーザ集合Uinが持つ属性AUinを出力する。総コストの最小化手法としては、ユーザのソーシャルネットワーク上の関係を有向であると定義するならば変分ベイズ法、サンプリング法など、無向であると定義するならば前記2手法に加え動的計画法などの利用が考えられる。手法によっては、上記イテレーションが行われない手法もある。
【００２６】
図２は、例として属性集合Aに含まれる属性aが離散値であった場合にギブスサンプリングを利用した場合のユーザ属性推定部１２の動作を示すフローチャートであり、以下の説明において、対応する図２のステップ番号を適宜示す。
【００２７】
まず、与えられたソーシャルネットワークにおける全ユーザ集合Usについて、各ユーザがとりうる全ての属性集合Aに含まれる属性aをとった場合のユーザコストC(u,a)を算出する（図２のステップ２１）。具体的には、ユーザコストC(u,a)の算出はユーザコスト算出部１４によって行われ、ユーザ属性推定部１２はその算出結果であるユーザコストC(u,a)を受け取る。そして、ユーザ属性推定部１２は、下記の式にようにC(u,a)を正規化することによってP(a|u)を算出する（図２のステップ２２）。
【００２８】
【数１】
2014041437.tif 000003
このP(a|u)をもとにイテレーションtにおけるユーザuの属性推定結果au,tをサンプリングする（図２のステップ２３）。この際、最大のP(a|u)であるau,tを選ぶのではなく、P(a|u)に基づいてau,tを確率的に選ぶ点に注意されたい。これは、前述したように、とりうる全ての属性の可能性を考慮し、その組み合わせを最適化するようなベイズ推定を行うためである。P(a|u)はユーザコストを元に算出されているため、ユーザコストをより小さくするようなau,tが選ばれやすい。そのため、複数の可能性を考慮しながら、総コストを最適化することを可能としている。
【００２９】
そして、サンプリングしたau,tにおけるユーザコストC(u,au,t)を算出し、これを全ユーザ集合Usについて足し合わせることで、総コストC(US,AU,t)を算出する（図２のステップ２４）。そして、算出した総コストとイテレーションt-1の総コストの差が閾値ε以下になるまで繰り返す。差がε以上であった場合はイテレーション回数に1を足す。
【００３０】
なお、属性集合Aに含まれる属性aが連続値であった場合は、サンプリングを次のように行う。まず、P(a|u)がなんらかの分布に従うと仮定し、その分布のパラメタを、後述する関連ユーザ集合Urelの属性aと後述するユーザ間類似度sim(u,u')から推定する。例えば、正規分布であると仮定するならば、ユーザ間類似度sim(u,u')を重みとした属性aの重み付き平均と、重み付き分散をパラメタとして利用する。推定したパラメタを持つ正規分布からサンプリングを行うが、正規分布から乱数を発生させる方法としてはボックス・ミュラー法などを利用する。
【００３１】
＜ユーザコスト算出部１４＞
ユーザコスト算出部１４では、ユーザ属性推定部１２からユーザuと属性aとユーザ属性推定結果AUS,tを入力として受け付ける。そして、全関連ユーザ間コスト算出部１８において算出した、ユーザuが属性aをとった場合の関連ユーザ集合Urelに含まれるユーザu'とのユーザ間コストC(u,u',a)に基づいて、ユーザuが属性aをとった場合のユーザコストC(u,a)を算出し、ユーザ属性推定部１２へと出力する（図３のステップ３１〜３４）。
【００３２】
C(u,a)は、下式のように、ユーザ間コストC(u,u',a)を関連ユーザ集合Urelについて足し合わせることによって求められる。
【００３３】
【数２】
2014041437.tif 000004
図１に示すように、ユーザコスト算出部１４は、ソーシャルネットワーク記憶部１５、関連ユーザ集合抽出部１７、全関連ユーザ間コスト算出部１８、ユーザ属性記憶部１６を有する。
【００３４】
以下にユーザコスト算出部１４の各構成・動作をより詳細に説明する。図３は、ユーザコスト算出部１４の動作を示すフローチャートであり、以下の説明において、対応する図３のステップ番号を適宜示す。
【００３５】
＜ソーシャルネットワーク記憶部１５＞
ソーシャルネットワーク記憶部１５に格納されるデータの例を図４に示す。
【００３６】
ソーシャルネットワーク記憶部１５では、ユーザ集合USのソーシャルネットワーク情報を格納する。ソーシャルネットワーク情報は、ユーザがどのユーザとの関連を持っているかの情報および、関連の強さを示す情報である。関連とは、Twitter（登録商標）のフォローのような有向の情報でも、Facebook（登録商標）の友達登録のような無向の情報でもよい。また、関連とは、2ユーザの間で友達登録がなされているかなどのようにユーザ同士が明示的に行うものであっても、ある期間において2ユーザの間で投稿に対する返信などがなされているかから抽出するものであってもよい。関連の強さを示す情報とは、会話の頻度、文字数、返信が続く回数、返信が行われるまでにかかる時間、共通の友人数などといった情報である。
【００３７】
当該ソーシャルネットワーク記憶部１５は、これらの情報が保存され、復元可能なものであればよく、特定のものに限定されない。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶されるもの、もしくは、Webページを保持するWebサーバや、データベースを具備するデータベースサーバ等である。
【００３８】
＜ユーザ属性記憶部１６＞
ユーザ属性記憶部１６に格納されるデータの例を図５に示す。
【００３９】
ユーザ属性記憶部１６では、ユーザ集合USの属性集合Aを格納する。属性aは複数の属性名aiと属性値aijの組である。属性名には、性別、年代、居住地、出身地、母国語、利用可能な言語、職業、勤務先、学歴情報（出身または在学中の大学、高校…など）、所属集団名、宗教、指示する政党、経験スポーツ、嗜好（好きな食べ物、好きな音楽、好きな本…など、または、その度合いが含まれてもよい）、趣味、既婚/未婚、家族構成…などが含まれる。例えば、図５に示す例では、IDがIDaのユーザについて、属性名が「職業」である属性の属性値が「学生」であることが示されている。
【００４０】
また、ユーザ属性記憶部１６に格納される属性集合Aは、第１の従来技術と同様の手法を用いて算出したユーザ属性、または各ユーザ属性を持つ確率値であってもよい。
【００４１】
また、ユーザ属性記憶部１６は、ユーザ集合USのプロフィール集合Pを格納するものでもよい。プロフィールPには、自己紹介文や、友人などからの紹介文などが含まれる。この場合は、前処理として、プロフィールを形態素解析し、形態素解析結果に属性名が含まれるかのマッチングなどによって、属性集合Aを抽出する。
【００４２】
当該ユーザ属性記憶部１６は、これらの情報が保存され、復元可能なものであればよく、特定のものに限定されない。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶されるもの、もしくは、Webページを保持するWebサーバや、データベースを具備するデータベースサーバ等である。
【００４３】
＜関連ユーザ集合抽出部１７＞
関連ユーザ集合抽出部１７では、ユーザ属性推定部１２からユーザuを入力として受け付ける。そして、ソーシャルネットワーク記憶部１５に格納されたソーシャルネットワークから、ユーザuの関連ユーザ集合Urelを抽出し、全関連ユーザ間コスト算出部１８へと出力する（図３のステップ３１）。
【００４４】
関連ユーザ集合Urelはイテレーションtによらないため、ソーシャルネットワークが与えられた際に先に計算し、保持しておくものでもよい。
【００４５】
＜全関連ユーザ間コスト算出部１８＞
全関連ユーザ間コスト算出部１８では、ユーザ属性推定部１２からユーザuと属性aと属性推定結果AUS,tを、関連ユーザ集合抽出部１７からユーザuの関連ユーザ集合Urelを入力として受け付ける。そして、ユーザ間コスト算出部２１において算出した、ユーザuが属性aをとった場合のユーザu'とのユーザ間コストC(u,u',a)をユーザコスト算出部１４へと出力する（図３のステップ３２〜３３）。
【００４６】
図１に示すように、全関連ユーザ間コスト算出部１８は、ソーシャルネットワーク記憶部１５、ユーザ間類似度算出部１９、ユーザ属性記憶部１６、ユーザ間属性距離算出部２０、ユーザ間コスト算出部２１を有する。
【００４７】
以下に全関連ユーザ間コスト算出部１８の各構成・動作をより詳細に説明する。
【００４８】
＜ユーザ間類似度算出部１９＞
ユーザ間類似度算出部１９では、ユーザ属性推定部１２からユーザuを、関連ユーザ集合抽出部１７からユーザu'を、ソーシャルネットワーク記憶部１５から関連の強さを示す情報を入力として受け付ける。そして、ユーザuとユーザu'のユーザ間類似度sim(u,u')を算出し、ユーザ間コスト算出部２１へと出力する（図３のステップ３２）。
【００４９】
sim(u,u')は、例えば、第２の従来技術においては、下記の式によって求められるが、下記の式に、関連の強さを示す情報に含まれる特徴量の全てまたは一部を加えた方法であってもよい。また、sim(u,u')を関連ユーザ集合Urelについて足し合わせると1になるよう正規化を行う。
【００５０】
【数３】
2014041437.tif 000005
ここで、distは下記の関数である。
【００５１】
【数４】
2014041437.tif 000006
ただし、Kは、ユーザuとユーザu'の間の、共通の近隣ユーザを経由した経路集合であるとする。また、strengthは下記の関数である。
【００５２】
【数５】
2014041437.tif 000007
ここで、X'ijは下記のように求める。
【００５３】
【数６】
2014041437.tif 000008
ただし、Xijはユーザiとユーザjが過去に会話した回数であるとする。
【００５４】
また、ユーザ間類似度sim(u,u')はイテレーションtによらないため、ソーシャルネットワークが与えられた際に先に計算し、保持しておくものでもよい。
【００５５】
＜ユーザ間属性距離算出部２０＞
ユーザ間属性距離算出部２０では、ユーザ属性推定部１２から属性aと属性推定結果AUS,tを、関連ユーザ集合抽出部１７からユーザu'を、ユーザ属性記憶部１６に格納されているイテレーション回数0におけるユーザ集合USの属性AUS,0を入力として受け付ける。そして、属性aとユーザu'の属性推定結果au',tのユーザ間属性距離diff(a,au',t)および属性aとイテレーション回数0におけるユーザuの属性au,0のユーザ間属性距離diff(a,au,0)を算出し、ユーザ間コスト算出部２１へと出力する（図３のステップ３２）。ただし、属性推定結果au',tが存在しない場合には、属性au',0を利用する。また、イテレーション回数0におけるユーザuの属性au,0が存在しない場合には、ユーザ間属性距離diff(a,au,0)は0とする。
【００５６】
diff(a,a')は、下記の式によって求められる。すなわち、共有する属性値の数である。属性値が連続値であった場合には、属性間のコサイン類似度やピアソン相関の逆数といった距離によって求め、属性値が確率値であった場合には、一致した属性への確率値の合計によって求められる。
【００５７】
【数７】
2014041437.tif 000009
＜ユーザ間コスト算出部２１＞
ユーザ間コスト算出部２１では、ユーザ間類似度算出部１９からsim(u,u')と、ユーザ間属性距離算出部２０からdiff(a,au',t)とdiff(a,au,0)を入力として受け取る。そして、ユーザ間コストC(u,u',a)を算出し、ユーザコスト算出部１４へと出力する（図３のステップ３３）。
【００５８】
C(u,u',a)は、下記の式によって求められる。
【００５９】
【数８】
2014041437.tif 000010
ここで、αは重みパラメタであり、関連ユーザu'との属性距離とユーザuの初期値との属性距離のどちらをどの程度重視するかのパラメタである。
【００６０】
＜出力部１３＞
出力部１３では、ユーザ属性推定部１２からユーザ集合Uinが持つ属性aUinを入力として受け付ける。そして、各属性名aiにおける属性値aijを出力する。
【００６１】
ここで、出力とは、ディスプレイへの表示、プリンタへの印字、音出力、外部装置への送信等を含む概念である。出力部は、ディスプレイやスピーカ等の出力デバイスを含むと考えても含まないと考えてもよい。出力部は、出力デバイスのドライバソフトまたは、出力デバイスのドライバソフトと出力デバイス等で実現され得る。
【００６２】
（具体例）
以下、具体的な例を用いて本実施の形態の処理について説明する。
【００６３】
ここでは、下記の条件における具体例を説明する。
【００６４】
・入力は入力ユーザuである
・属性名aiには職業と居住地が含まれる
・属性値a職業jには学生と会社員が含まれる
・属性値a居住地jには東京と神奈川が含まれる
・ユーザ属性記憶部１６には第１の従来技術と同様の手法を用いて算出したユーザ属性が格納されている
・総コスト最小化手法にはギブスサンプリングを用いる
ユーザ属性推定部１２において、まず、ユーザuが持つ属性au,tをサンプリングする。このために、ユーザコスト算出部１４を通じ、ユーザuがとりうる全ての属性aについてユーザコストC(u,a)を得る。例えば、C(u,a職業:学生，居住地:東京)が2、C(u,a職業:学生，居住地:神奈川)が3、C(u,a職業:会社員，居住地:東京)が6、C(u,a職業:会社員，居住地:神奈川)が1だとすると、P(u,a職業:学生，居住地:東京)は(1/2)/(1/2+1/3+1/6+1/1)=0.25、同様に、P(u,a職業:学生，居住地:神奈川)が0.167、P(u,a職業:会社員，居住地:東京)が0.083、P(u,a職業:会社員，居住地:神奈川)が0.5と算出できる。この確率をもとに、例えば、ユーザuが持つ属性としてa職業:会社員，居住地:神奈川がサンプリングされたとすると、イテレーションtにおけるユーザuの属性推定結果au,tにa職業:会社員，居住地:神奈川が代入される。このサンプリングを全ユーザ集合USに対して繰り返し、サンプリングした属性におけるコストC(u, a職業:会社員，居住地:神奈川)を全ユーザについて足し合わせることで総コストC(US,AUS,t)を得る。以上のステップをイテレーションし、前イテレーションにおける総コストC(US,AUS,t-1)との差がε以下になるまで繰り返す。
【００６５】
なお、属性値が連続値、例えば、IT系への嗜好の度合いなどの場合、例えば、関連ユーザがu1、u2、u3で、sim(u,u1)=0.6、au1=0.8、sim(u,u2)=0.3、au1=0.6、sim(u,u3)=0.1、au1=0.4だとすると、この重み付き平均は(0.6×0.8+0.3×0.6+0.1×0.4)/(0.6+0.3+0.1)=0.6、重み付き分散の二乗は(0.6×0.8^2+0.3×0.6^2+0.1×0.4^2)/(0.6+0.3+0.1)−0.6^2=0.148と算出できる。そして、この2つをパラメタとした正規分布から、ボックス・ミュラー法を利用して乱数を発生させることで、サンプリングを行う。
【００６６】
ユーザコスト算出部１４において、ユーザu、属性a職業:学生，居住地:東京が入力される場合の例を説明する。まず、関連ユーザ集合抽出部１７によって、ソーシャルネットワーク記憶部１５から関連ユーザ集合Urelを得る。そして全関連ユーザ間コスト算出部１８を通じ、関連ユーザ集合Urelに含まれる全ユーザu'について、ユーザ間コストC(u,u', a職業:学生，居住地:東京)を得る。これを関連ユーザ集合Urelについて足し合わせることでユーザコストC(u, a職業:学生，居住地:東京)を算出し、ユーザ属性推定部１２へと出力する。
【００６７】
全関連ユーザ間コスト算出部１８において、ユーザu、ユーザu'、属性a職業:学生，居住地:東京が入力される場合の例を説明する。まず、ユーザ間類似度算出部１９において、共通の友人間における会話回数をホップ数でわったものを全て足し合わせることで、ユーザuとユーザu'のユーザ間類似度を算出する。例えば、ユーザuとユーザu'の共通の友人がua、ubであり、ユーザuとユーザu'は5回、ユーザuとユーザuaは3回、ユーザu'とユーザuaは1回、ユーザuとユーザubは4回、ユーザu'とユーザubは6回会話していたとすると、5+(3+1)/2+(4+6)/2=12となる。これを正規化することで、例えば0.6となったとする。同時に、ユーザ間属性距離算出部２０において、属性a職業:学生，居住地:東京とユーザu'の属性推定結果au',tのユーザ間属性距離diff(a,au',t)および属性aとイテレーション回数0におけるユーザuの属性au,0のユーザ間属性距離diff(a,au,0)を求める。例えば、ユーザu'の属性推定結果au',tがa職業:会社員，居住地:神奈川であったとすれば、属性aと属性推定結果au',tは2つの属性名の属性値が異なるので、diff(a,au',t)は2となる。同様に、diff(a,au,0)が1と求められたとする。次に、ユーザ間コスト算出部２１において、C(u,u', a職業:学生，居住地:東京)を算出する。αを0.8とすると、0.6×2+0.8×1=2と算出することができる。
【００６８】
なお、属性値が確率値、例えば、ユーザuの職業：学生の確率が0.4、職業：会社員の確率が0.6で、ユーザu'の職業：学生の確率が0.2、職業：会社員の確率が0.8の場合、ユーザ間属性距離は、この2つのコサイン類似度やピアソン相関の逆数をとったものとして求める。
【００６９】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７０】
１０  ユーザ属性推定装置
１１  入力部
１２  ユーザ属性推定部
１３  出力部
１４  ユーザコスト算出部
１５  ソーシャルネットワーク記憶部
１６  ユーザ属性記憶部
１７  関連ユーザ集合抽出部
１８  全関連ユーザ間コスト算出部
１９  ユーザ間類似度算出部
２０  ユーザ間属性距離算出部
２１  ユーザ間コスト算出部
【図１】
2014041437.tif 000011
【図２】
2014041437.tif 000012
【図３】
2014041437.tif 000013
【図４】
2014041437.tif 000014
【図５】
2014041437.tif 000015