推定値高精度化システム、推定値高精度化方法および推定値高精度化プログラム
【課題】二部グラフに対してリンク解析を行った際、エッジ数の多いノードに生じる不必要な値の増加を防ぎ、ユーザ、アイテムが各々持つ特性値の推定精度を高めることができる推定値高精度化システムを提供する。
【解決手段】ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３を用いて、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築し、前記各ノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に、前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成し、前記二部グラフに対して、リンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計が閾値より小さくなるまで更新するユーザ・アイテム関係解析部１０４を備える。
【解決手段】ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３を用いて、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築し、前記各ノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に、前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成し、前記二部グラフに対して、リンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計が閾値より小さくなるまで更新するユーザ・アイテム関係解析部１０４を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザ、アイテム間の関係を利用した、ユーザ、アイテムそれぞれの特性に関する推定精度を向上させる技術に関する。
【背景技術】
【０００２】
選択、被選択や、作成、被作成といったような、なんらかの関係をもつユーザとアイテムがあるとき、ユーザに関連するアイテムの特性からユーザの特性が推定される、または、アイテムに関連するユーザの特性からアイテムの特性が推定される場合がある。
【０００３】
例えば、ユーザとＷｅｂページの閲覧関係を利用して、将来的に犯罪行為につながる危険性について分析することを考える。Ｗｅｂページになんらかの方法で「危険度」が与えられているとき、閲覧関係から危険なユーザを推定することができる。
【０００４】
逆に、ユーザに何らかの方法で、「危険度」が与えられているとき、閲覧関係によって危険なＷｅｂページを推定することができる。ユーザ、Ｗｅｂページ両者に「危険度」が与えられている場合、閲覧関係によって双方の危険度に関する推定を高精度にすることができる。
【０００５】
他にも、検索システムユーザと検索結果として得られるＷｅｂページのクリック関係を利用して、ユーザ、Ｗｅｂページの持つ特定の分野に関する専門性を分析する場合や、ユーザと、ユーザの作成した文書の関係を利用して、文書、ユーザの信頼性を分析する場合などが例として考えられる。
【０００６】
ユーザ、アイテムに与えられた特性値に加え、ユーザ、アイテム間の関係を利用することによって、それぞれの特性値に関する推定精度を高める方法が考えられてきた。ある特性の推定値を初期値とするユーザとアイテムをそれぞれノードとし、ユーザ、アイテム間の関係をエッジとした二部グラフとして表現する。二部グラフに対し、例えば非特許文献１に記載のＣｏ−ＨＩＴＳ（Ｈｙｐｅｒｌｉｎｋ−Ｉｎｄｕｃｅｄ Ｔｏｐｉｃ Ｓｅａｒｃｈ）などのリンク解析手法を適用するといった方法がある。
【０００７】
尚、従来、予め与えられた悪性リストに対して、アクセス先とアクセス元の関係を利用してその悪性リストの擬陽性、擬陰性を排除する技術が特許文献１に記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−３９７４９号公報
【非特許文献】
【０００９】
【非特許文献１】Ｄ．Ｈｏｎｇｂｏ、Ｌ．Ｍｉｃｈａｅｌ Ｒ．、Ｋ．Ｉｒｗｉｎ、“Ａ Ｇｅｎｅｒａｌｉｚｅｄ Ｃｏ−ＨＩＴＳ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｂｉｐａｒｔｉｔｅ Ｇｒａｐｈｓ”、ＫＤＤ ’０９、 ２００９、ｐｐ．２３９−２４７
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、従来の技術では、多くのエッジを持つノードの値が不必要に高くなってしまう場合があるという問題点があった。例えば犯罪危険度の例で考えると、わずかに危険性のあるページを多く見ているユーザは、大変危険なページを少量見ているユーザよりも危険性がはるかに高いとされてしまう可能性がある。
【００１１】
本発明は上記課題を解決するものであり、その目的は、二部グラフに対してリンク解析を行った際、エッジ数の多いノードに生じる不必要な値の増加を防ぎ、ユーザ、アイテムが各々持つ特性値の推定精度を高めることができる推定値高精度化システム、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するための本発明の推定値高精度化システムは、ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化システムであって、特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築手段と、前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成手段と、前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新手段と、を備えたことを特徴としている。
【００１３】
上記構成によれば、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる不必要な値の増加を防ぐことができる。
【発明の効果】
【００１４】
本発明によれば、選択、被選択や、作成、被作成といった、なんらかの関係が存在するユーザ、アイテムの持つ、ある特性値に関して、双方の特性値の推定精度を高めることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態例を示すシステム構成図。
【図２】本発明の一実施形態例におけるユーザＤＢの例を示す説明図。
【図３】本発明の一実施形態例におけるアイテムＤＢの例を示す説明図。
【図４】本発明の一実施形態例におけるユーザ・アイテム関係ＤＢの例を示す説明図。
【図５】本発明の一実施形態例におけるユーザ・アイテム関係解析部が行う処理のフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００１７】
本発明は、二部グラフにおいて、各ノードの初期値を考慮したリンク解析をした際の、ノードの持つ値がエッジ数によって左右されないように正規化をすることにより、従来方法よりユーザ、アイテムのもつ特性の推定精度を向上させるものである。
【００１８】
図１は本実施形態例による推定値高精度化システムの構成を示している。図１において、推定値高精度化システム１００は、ユーザＤＢ（データベース）１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３およびユーザ・アイテム関係解析部１０４を備えている。
【００１９】
ユーザＤＢ１０１はユーザに与えられた特性推定値が格納され、例えば図２のように構成されている。
【００２０】
アイテムＤＢ１０２はアイテムに与えられた特性推定値が格納され、例えば図３のように構成されている。
【００２１】
ユーザ・アイテム関係ＤＢ１０３はユーザとアイテムの関係を表す情報が格納され、例えば図４のように構成されている。
【００２２】
ユーザ・アイテム関係解析部１０４は、ユーザＤＢ１０１、アイテムＤＢ１０２およびユーザ・アイテム関係ＤＢ１０３を利用して、ユーザとアイテムの関係を表す行列を作成して二部グラフを構築する本発明の二部グラフ構築手段と、二部グラフのリンク解析のための重み行列を作成する本発明の重み行列作成手段と、前記二部グラフに対してリンク解析を行いユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新する本発明のノード値更新手段の、各機能を図５のフローチャートに沿って実行する。
【００２３】
前記二部グラフ構築手段の機能は、図５のＳｔｅｐ１〜Ｓｔｅｐ４（ユーザ・アイテム関係を二部グラフとして扱うための操作）により実行され、前記重み行列作成手段の機能は、図５のＳｔｅｐ５、Ｓｔｅｐ６により実行され、前記ノード値更新手段の機能は、図５のＳｔｅｐ７（ノードの持つ値をエッジを通して伝播させるというリンク解析の操作）、Ｓｔｅｐ８により実行される。
【００２４】
推定値高精度化システム１００は、例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＲＯＭ，ＲＡＭ，ＣＰＵ、入力装置、出力装置、通信インターフェース、ハードディスク、記録媒体およびその駆動装置を備えている。
【００２５】
このハードウェアリソースとソフトウェアリソース（ＯＳ、アプリケーションなど）との協働の結果、推定値高精度化システム１００は、図１に示すように、ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３、ユーザ・アイテム関係解析部１０４を実装する。
【００２６】
前記ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３は、ハードディスクあるいはＲＡＭなどの保存手段・記憶手段に構築されているものとする。
【００２７】
次に、上記のように構成された装置の動作を図５のフローチャートに沿って詳細に説明する。
【００２８】
まずあらかじめ、図２に示すようなユーザＤＢ１０１、図３に示すようなアイテムＤＢ１０２、図４に示すようなユーザ・アイテム関係ＤＢ１０３が与えられているものとする。
【００２９】
Ｓｔｅｐ１
推定値高精度化システム１００のユーザ・アイテム関係解析部１０４は、ユーザＤＢ１０１よりユーザに与えられた推定値（特性値）を読み込み、ユーザｕiに初期値ｘi0を与える。
【００３０】
Ｓｔｅｐ２
推定値高精度化システム１００のユーザ・アイテム関係解析部１０４は、アイテムＤＢ１０２よりユーザに与えられた推定値（特性値）を読み込み、アイテムｖjに初期値ｙj0を与える。
【００３１】
Ｓｔｅｐ３
【００３２】
【数１】
【００３３】
Ｓｔｅｐ４
アイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成する。Ｓｔｅｐ３で作成したユーザとアイテムの関係を表す行列Ａuvを転置し、Ａvuとする。
【００３４】
【数２】
【００３５】
Ｓｔｅｐ５
ユーザノード群Ｕからアイテムノード群Ｖへの重み行列Ｗuvを作成する。エッジを通してノードからノードに影響を伝えられる際に、エッジの本数で正規化されるように重みをつける。これにより、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる、不必要な値の増加を防ぐ。
【００３６】
【数３】
【００３７】
Ｓｔｅｐ６
アイテムノード群Ｖからユーザノード群Ｕへの重み行列Ｗvuを作成する。Ｓｔｅｐ５と同様の正規化を行うことにより、重み行列の作成を行う。
【００３８】
【数４】
【００３９】
Ｓｔｅｐ７
Ｕ、Ｖ両ノードの情報を、エッジを通してお互いに伝播させ、ノードの持つ値を更新する。これは、ノードの持つ値を、エッジを通して伝播させるというリンク解析の操作であり、例えば非特許文献１などの方法を用いることもできる。
【００４０】
ユーザのノード値ｘi、アイテムのノード値ｙjは、
【００４１】
【数５】
【００４２】
ここで、λu，λvは、０から１までの任意の定数である。
【００４３】
Ｓｔｅｐ８
ノードが更新される値の合計が閾値θより小さくなるまで、Ｓｔｅｐ７の操作を繰り返す。
【００４４】
【数６】
【００４５】
本実施形態例と従来技術との大きな違いは、ノード間のエッジの有無を行列式の要素とし、ユーザとアイテムの関係を表す行列（Ａuv，Ａvu）からの、重み行列（Ｗuv，Ｗvu）の正規化の仕方にある。従来技術では、エッジを通して影響を伝える際にエッジの本数で正規化するのに対し、本実施形態例ではエッジを通して影響を伝えられる際に、エッジの本数で正規化を行う。これにより、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる、不必要な値の増加を防ぐことができる。
【００４６】
すなわち、従来技術では、伝播によってノードの値を更新させる際に、伝播の影響を与える側のノードが持つエッジの数で正規化している（例えば非特許文献１の２４０頁の「２．ＰＲＥＬＩＭＩＮＡＲＩＥＳ」の１３行目、１４行目に
【００４７】
【数７】
【００４８】
と開示されている）。
これに対し本実施形態例では、伝播によってノードの値を更新させる際に、伝播の影響を受ける側のノードを持つエッジの数で正規化している。
【００４９】
すなわち、本実施形態例では、図５のＳｔｅｐ５において行列Ｗuv（式（４））を作成することにより、その行列の各要素である
【００５０】
【数８】
【００５１】
図５のＳｔｅｐ６において行列Ｗvu（式（６））を作成することにより、その行列の各要素である
【００５２】
【数９】
【００５３】
また、本実施形態の推定値高精度化システムにおける各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の推定値高精度化方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００５４】
１００…推定値高精度化システム
１０１…ユーザＤＢ
１０２…アイテムＤＢ
１０３…ユーザ・アイテム関係ＤＢ
１０４…ユーザ・アイテム関係解析部
【技術分野】
【０００１】
本発明は、ユーザ、アイテム間の関係を利用した、ユーザ、アイテムそれぞれの特性に関する推定精度を向上させる技術に関する。
【背景技術】
【０００２】
選択、被選択や、作成、被作成といったような、なんらかの関係をもつユーザとアイテムがあるとき、ユーザに関連するアイテムの特性からユーザの特性が推定される、または、アイテムに関連するユーザの特性からアイテムの特性が推定される場合がある。
【０００３】
例えば、ユーザとＷｅｂページの閲覧関係を利用して、将来的に犯罪行為につながる危険性について分析することを考える。Ｗｅｂページになんらかの方法で「危険度」が与えられているとき、閲覧関係から危険なユーザを推定することができる。
【０００４】
逆に、ユーザに何らかの方法で、「危険度」が与えられているとき、閲覧関係によって危険なＷｅｂページを推定することができる。ユーザ、Ｗｅｂページ両者に「危険度」が与えられている場合、閲覧関係によって双方の危険度に関する推定を高精度にすることができる。
【０００５】
他にも、検索システムユーザと検索結果として得られるＷｅｂページのクリック関係を利用して、ユーザ、Ｗｅｂページの持つ特定の分野に関する専門性を分析する場合や、ユーザと、ユーザの作成した文書の関係を利用して、文書、ユーザの信頼性を分析する場合などが例として考えられる。
【０００６】
ユーザ、アイテムに与えられた特性値に加え、ユーザ、アイテム間の関係を利用することによって、それぞれの特性値に関する推定精度を高める方法が考えられてきた。ある特性の推定値を初期値とするユーザとアイテムをそれぞれノードとし、ユーザ、アイテム間の関係をエッジとした二部グラフとして表現する。二部グラフに対し、例えば非特許文献１に記載のＣｏ−ＨＩＴＳ（Ｈｙｐｅｒｌｉｎｋ−Ｉｎｄｕｃｅｄ Ｔｏｐｉｃ Ｓｅａｒｃｈ）などのリンク解析手法を適用するといった方法がある。
【０００７】
尚、従来、予め与えられた悪性リストに対して、アクセス先とアクセス元の関係を利用してその悪性リストの擬陽性、擬陰性を排除する技術が特許文献１に記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−３９７４９号公報
【非特許文献】
【０００９】
【非特許文献１】Ｄ．Ｈｏｎｇｂｏ、Ｌ．Ｍｉｃｈａｅｌ Ｒ．、Ｋ．Ｉｒｗｉｎ、“Ａ Ｇｅｎｅｒａｌｉｚｅｄ Ｃｏ−ＨＩＴＳ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｂｉｐａｒｔｉｔｅ Ｇｒａｐｈｓ”、ＫＤＤ ’０９、 ２００９、ｐｐ．２３９−２４７
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、従来の技術では、多くのエッジを持つノードの値が不必要に高くなってしまう場合があるという問題点があった。例えば犯罪危険度の例で考えると、わずかに危険性のあるページを多く見ているユーザは、大変危険なページを少量見ているユーザよりも危険性がはるかに高いとされてしまう可能性がある。
【００１１】
本発明は上記課題を解決するものであり、その目的は、二部グラフに対してリンク解析を行った際、エッジ数の多いノードに生じる不必要な値の増加を防ぎ、ユーザ、アイテムが各々持つ特性値の推定精度を高めることができる推定値高精度化システム、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するための本発明の推定値高精度化システムは、ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化システムであって、特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築手段と、前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成手段と、前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新手段と、を備えたことを特徴としている。
【００１３】
上記構成によれば、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる不必要な値の増加を防ぐことができる。
【発明の効果】
【００１４】
本発明によれば、選択、被選択や、作成、被作成といった、なんらかの関係が存在するユーザ、アイテムの持つ、ある特性値に関して、双方の特性値の推定精度を高めることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態例を示すシステム構成図。
【図２】本発明の一実施形態例におけるユーザＤＢの例を示す説明図。
【図３】本発明の一実施形態例におけるアイテムＤＢの例を示す説明図。
【図４】本発明の一実施形態例におけるユーザ・アイテム関係ＤＢの例を示す説明図。
【図５】本発明の一実施形態例におけるユーザ・アイテム関係解析部が行う処理のフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００１７】
本発明は、二部グラフにおいて、各ノードの初期値を考慮したリンク解析をした際の、ノードの持つ値がエッジ数によって左右されないように正規化をすることにより、従来方法よりユーザ、アイテムのもつ特性の推定精度を向上させるものである。
【００１８】
図１は本実施形態例による推定値高精度化システムの構成を示している。図１において、推定値高精度化システム１００は、ユーザＤＢ（データベース）１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３およびユーザ・アイテム関係解析部１０４を備えている。
【００１９】
ユーザＤＢ１０１はユーザに与えられた特性推定値が格納され、例えば図２のように構成されている。
【００２０】
アイテムＤＢ１０２はアイテムに与えられた特性推定値が格納され、例えば図３のように構成されている。
【００２１】
ユーザ・アイテム関係ＤＢ１０３はユーザとアイテムの関係を表す情報が格納され、例えば図４のように構成されている。
【００２２】
ユーザ・アイテム関係解析部１０４は、ユーザＤＢ１０１、アイテムＤＢ１０２およびユーザ・アイテム関係ＤＢ１０３を利用して、ユーザとアイテムの関係を表す行列を作成して二部グラフを構築する本発明の二部グラフ構築手段と、二部グラフのリンク解析のための重み行列を作成する本発明の重み行列作成手段と、前記二部グラフに対してリンク解析を行いユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新する本発明のノード値更新手段の、各機能を図５のフローチャートに沿って実行する。
【００２３】
前記二部グラフ構築手段の機能は、図５のＳｔｅｐ１〜Ｓｔｅｐ４（ユーザ・アイテム関係を二部グラフとして扱うための操作）により実行され、前記重み行列作成手段の機能は、図５のＳｔｅｐ５、Ｓｔｅｐ６により実行され、前記ノード値更新手段の機能は、図５のＳｔｅｐ７（ノードの持つ値をエッジを通して伝播させるというリンク解析の操作）、Ｓｔｅｐ８により実行される。
【００２４】
推定値高精度化システム１００は、例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＲＯＭ，ＲＡＭ，ＣＰＵ、入力装置、出力装置、通信インターフェース、ハードディスク、記録媒体およびその駆動装置を備えている。
【００２５】
このハードウェアリソースとソフトウェアリソース（ＯＳ、アプリケーションなど）との協働の結果、推定値高精度化システム１００は、図１に示すように、ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３、ユーザ・アイテム関係解析部１０４を実装する。
【００２６】
前記ユーザＤＢ１０１、アイテムＤＢ１０２、ユーザ・アイテム関係ＤＢ１０３は、ハードディスクあるいはＲＡＭなどの保存手段・記憶手段に構築されているものとする。
【００２７】
次に、上記のように構成された装置の動作を図５のフローチャートに沿って詳細に説明する。
【００２８】
まずあらかじめ、図２に示すようなユーザＤＢ１０１、図３に示すようなアイテムＤＢ１０２、図４に示すようなユーザ・アイテム関係ＤＢ１０３が与えられているものとする。
【００２９】
Ｓｔｅｐ１
推定値高精度化システム１００のユーザ・アイテム関係解析部１０４は、ユーザＤＢ１０１よりユーザに与えられた推定値（特性値）を読み込み、ユーザｕiに初期値ｘi0を与える。
【００３０】
Ｓｔｅｐ２
推定値高精度化システム１００のユーザ・アイテム関係解析部１０４は、アイテムＤＢ１０２よりユーザに与えられた推定値（特性値）を読み込み、アイテムｖjに初期値ｙj0を与える。
【００３１】
Ｓｔｅｐ３
【００３２】
【数１】
【００３３】
Ｓｔｅｐ４
アイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成する。Ｓｔｅｐ３で作成したユーザとアイテムの関係を表す行列Ａuvを転置し、Ａvuとする。
【００３４】
【数２】
【００３５】
Ｓｔｅｐ５
ユーザノード群Ｕからアイテムノード群Ｖへの重み行列Ｗuvを作成する。エッジを通してノードからノードに影響を伝えられる際に、エッジの本数で正規化されるように重みをつける。これにより、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる、不必要な値の増加を防ぐ。
【００３６】
【数３】
【００３７】
Ｓｔｅｐ６
アイテムノード群Ｖからユーザノード群Ｕへの重み行列Ｗvuを作成する。Ｓｔｅｐ５と同様の正規化を行うことにより、重み行列の作成を行う。
【００３８】
【数４】
【００３９】
Ｓｔｅｐ７
Ｕ、Ｖ両ノードの情報を、エッジを通してお互いに伝播させ、ノードの持つ値を更新する。これは、ノードの持つ値を、エッジを通して伝播させるというリンク解析の操作であり、例えば非特許文献１などの方法を用いることもできる。
【００４０】
ユーザのノード値ｘi、アイテムのノード値ｙjは、
【００４１】
【数５】
【００４２】
ここで、λu，λvは、０から１までの任意の定数である。
【００４３】
Ｓｔｅｐ８
ノードが更新される値の合計が閾値θより小さくなるまで、Ｓｔｅｐ７の操作を繰り返す。
【００４４】
【数６】
【００４５】
本実施形態例と従来技術との大きな違いは、ノード間のエッジの有無を行列式の要素とし、ユーザとアイテムの関係を表す行列（Ａuv，Ａvu）からの、重み行列（Ｗuv，Ｗvu）の正規化の仕方にある。従来技術では、エッジを通して影響を伝える際にエッジの本数で正規化するのに対し、本実施形態例ではエッジを通して影響を伝えられる際に、エッジの本数で正規化を行う。これにより、二部グラフに対してのリンク解析を行った際、エッジ数の多いノードに生じる、不必要な値の増加を防ぐことができる。
【００４６】
すなわち、従来技術では、伝播によってノードの値を更新させる際に、伝播の影響を与える側のノードが持つエッジの数で正規化している（例えば非特許文献１の２４０頁の「２．ＰＲＥＬＩＭＩＮＡＲＩＥＳ」の１３行目、１４行目に
【００４７】
【数７】
【００４８】
と開示されている）。
これに対し本実施形態例では、伝播によってノードの値を更新させる際に、伝播の影響を受ける側のノードを持つエッジの数で正規化している。
【００４９】
すなわち、本実施形態例では、図５のＳｔｅｐ５において行列Ｗuv（式（４））を作成することにより、その行列の各要素である
【００５０】
【数８】
【００５１】
図５のＳｔｅｐ６において行列Ｗvu（式（６））を作成することにより、その行列の各要素である
【００５２】
【数９】
【００５３】
また、本実施形態の推定値高精度化システムにおける各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態の推定値高精度化方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【００５４】
１００…推定値高精度化システム
１０１…ユーザＤＢ
１０２…アイテムＤＢ
１０３…ユーザ・アイテム関係ＤＢ
１０４…ユーザ・アイテム関係解析部
【特許請求の範囲】
【請求項１】
ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化システムであって、
特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築手段と、
前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成手段と、
前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新手段と、
を備えたことを特徴とする推定値高精度化システム。
【請求項２】
ユーザに与えられた特性推定値が格納されたユーザデータベースと、
アイテムに与えられた特性推定値が格納されたアイテムデータベースと、
ユーザとアイテムの関係を表す情報が格納されたユーザ・アイテム関係データベースとを備え、
前記二部グラフ構築手段は、前記ユーザデータベースに格納された特性推定値をユーザのノード値とし、前記アイテムデータベースに格納された特性推定値をアイテムのノード値とし、
前記ユーザ・アイテム関係データベースに格納された情報に基づく、前記ユーザノードとアイテムノード間のエッジの有無を要素として、ユーザノード群Ｕからアイテムノード群Ｖへのユーザとアイテムの関係を表す行列Ａuv、およびアイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成し、
前記重み行列作成手段は、
【数１０】
を作成し、
【数１１】
を作成することを特徴とする請求項１に記載の推定値高精度化システム。
【請求項３】
ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化方法であって、
二部グラフ構築手段が、特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築ステップと、
重み行列作成手段が、前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成ステップと、
ノード値更新手段が、前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新ステップと、
を備えたことを特徴とする推定値高精度化方法。
【請求項４】
前記二部グラフ構築ステップは、
ユーザに与えられた特性推定値を格納したユーザデータベースから該特性推定値を読み込んでユーザのノード値とするステップと、
アイテムに与えられた特性推定値を格納したアイテムデータベースから該特性推定値を読み込んでアイテムのノード値とするステップと、
ユーザとアイテムの関係を表す情報を格納したユーザ・アイテム関係データベースから該情報を読み込んで、前記ユーザノードとアイテムノード間のエッジの有無を要素としてユーザノード群Ｕからアイテムノード群Ｖへのユーザとアイテムの関係を表す行列Ａuvを作成するステップと、
前記作成された行列Ａuvを転置して、アイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成するステップを備え、
前記重み行列作成ステップは、
【数１２】
を作成するステップと、
【数１３】
を作成するステップを備えた、
ことを特徴とする請求項３に記載の推定値高精度化方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させる推定値高精度化プログラム。
【請求項１】
ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化システムであって、
特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築手段と、
前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成手段と、
前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新手段と、
を備えたことを特徴とする推定値高精度化システム。
【請求項２】
ユーザに与えられた特性推定値が格納されたユーザデータベースと、
アイテムに与えられた特性推定値が格納されたアイテムデータベースと、
ユーザとアイテムの関係を表す情報が格納されたユーザ・アイテム関係データベースとを備え、
前記二部グラフ構築手段は、前記ユーザデータベースに格納された特性推定値をユーザのノード値とし、前記アイテムデータベースに格納された特性推定値をアイテムのノード値とし、
前記ユーザ・アイテム関係データベースに格納された情報に基づく、前記ユーザノードとアイテムノード間のエッジの有無を要素として、ユーザノード群Ｕからアイテムノード群Ｖへのユーザとアイテムの関係を表す行列Ａuv、およびアイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成し、
前記重み行列作成手段は、
【数１０】
を作成し、
【数１１】
を作成することを特徴とする請求項１に記載の推定値高精度化システム。
【請求項３】
ユーザ、アイテムの各々に与えられた特性推定値の精度を高める推定値高精度化方法であって、
二部グラフ構築手段が、特性推定値が各々付与されたユーザとアイテムを各々ノードとし、ユーザ、アイテム間の関係をエッジとし、ユーザノードとアイテムノードのエッジの有無を要素とするユーザとアイテムの関係を表す行列を作成して二部グラフを構築する二部グラフ構築ステップと、
重み行列作成手段が、前記二部グラフのリンク解析のための重み行列であって、前記ユーザとアイテムの関係を表す行列の要素であるエッジについての重みを要素とし、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてノードの持つ値を更新させる際に前記伝播の影響を受ける側のノードが持つエッジの数で正規化される重み行列を作成する重み行列作成ステップと、
ノード値更新手段が、前記二部グラフに対して、前記ユーザノードおよびアイテムノードの情報をエッジを通して互いに伝播させてリンク解析を行い、前記ユーザとアイテムの各ノードの更新量の合計がしきい値より小さくなるまで更新するノード値更新ステップと、
を備えたことを特徴とする推定値高精度化方法。
【請求項４】
前記二部グラフ構築ステップは、
ユーザに与えられた特性推定値を格納したユーザデータベースから該特性推定値を読み込んでユーザのノード値とするステップと、
アイテムに与えられた特性推定値を格納したアイテムデータベースから該特性推定値を読み込んでアイテムのノード値とするステップと、
ユーザとアイテムの関係を表す情報を格納したユーザ・アイテム関係データベースから該情報を読み込んで、前記ユーザノードとアイテムノード間のエッジの有無を要素としてユーザノード群Ｕからアイテムノード群Ｖへのユーザとアイテムの関係を表す行列Ａuvを作成するステップと、
前記作成された行列Ａuvを転置して、アイテムノード群Ｖからユーザノード群Ｕへのユーザとアイテムの関係を表す行列Ａvuを作成するステップを備え、
前記重み行列作成ステップは、
【数１２】
を作成するステップと、
【数１３】
を作成するステップを備えた、
ことを特徴とする請求項３に記載の推定値高精度化方法。
【請求項５】
コンピュータを請求項１又は２に記載の各手段として機能させる推定値高精度化プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１２−５９１４１（Ｐ２０１２−５９１４１Ａ）
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願番号】特願２０１０−２０３５４４（Ｐ２０１０−２０３５４４）
【出願日】平成２２年９月１０日（２０１０．９．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願日】平成２２年９月１０日（２０１０．９．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]