(57)【要約】【課題】RWRを用いたアイテム推薦を、より小規模な計算機であっても適用可能とする。【解決手段】RWRを用いたアイテム推薦装置であって、ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報を格納したアイテム履歴記憶手段１２０から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する擬似逆行列算出手段１３０と、擬似逆行列を用いて推薦アイテムを決定する推薦アイテム決定手段１４０とを有し、擬似逆行列算出手段１３０は、遷移行列から生成される行列をそのまま用いて擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、前記擬似逆行列を算出する。【選択図】図１
2014228918.tif 000002
【特許請求の範囲】
【請求項１】
RWR（Random Walk with Restart）を用いたアイテム推薦装置であって、
ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報を格納したアイテム履歴記憶手段から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する擬似逆行列算出手段と、
前記擬似逆行列を用いて推薦アイテムを決定する推薦アイテム決定手段と、を有し、
前記擬似逆行列算出手段は、前記遷移行列から生成される行列をそのまま用いて前記擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、前記擬似逆行列を算出すること
を特徴とするアイテム推薦装置。
【請求項２】
請求項１記載のアイテム推薦装置であって、
前記擬似逆行列算出手段は、前記遷移行列の大きさと、当該アイテム推薦装置が備えるリソースとを用いて、前記擬似逆行列の算出ができるか否かを判別すること
を特徴とするアイテム推薦装置。
【請求項３】
請求項１または２記載のアイテム推薦装置であって、
前記擬似逆行列算出手段は、当該アイテム推薦装置が備えるメモリ容量が、前記遷移行列の大きさに所定数を乗じた大きさ未満の場合、前記擬似逆行列の算出ができないと判別すること
を特徴とするアイテム推薦装置。
【請求項４】
コンピュータが行う、RWR（Random Walk with Restart）を用いたアイテム推薦方法であって、
ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報を格納したアイテム履歴記憶部から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する擬似逆行列算出ステップと、
前記擬似逆行列を用いて推薦アイテムを決定する推薦アイテム決定ステップと、を行い、
前記擬似逆行列算出ステップは、前記遷移行列から生成される行列をそのまま用いて前記擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、前記擬似逆行列を算出すること
を特徴とするアイテム推薦方法。
【請求項５】
請求項４記載のアイテム推薦方法であって、
前記擬似逆行列算出ステップは、前記遷移行列の大きさと、前記コンピュータが備えるリソースとを用いて、前記擬似逆行列の算出ができるか否かを判別すること
を特徴とするアイテム推薦方法。
【請求項６】
請求項４または５記載のアイテム推薦方法であって、
前記擬似逆行列算出ステップは、前記コンピュータが備えるメモリ容量が、前記遷移行列の大きさに所定数を乗じた大きさ未満の場合、前記擬似逆行列の算出ができないと判別すること
を特徴とするアイテム推薦方法。
【請求項７】
請求項１から３のいずれか一項に記載のアイテム推薦装置としてコンピュータを機能させるためのアイテム推薦プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アイテム推薦において、Random Walk with Restart（RWR）に基づいて推薦するアイテムを決定するアイテム推薦装置、アイテム推薦方法、およびアイテム推薦プログラムに関する。
【背景技術】
【０００２】
ユーザとアイテムからなるグラフを、複数のサービスなどのドメインを考慮して集計して構築し、RWRを適用する事により推薦するアイテムを決定する方法がある（例えば、非特許文献１参照）。
【０００３】
また、RWRの計算を行うにあたり、逆行列を求めるのに適した行列分解手法であるLU分解を用いて逆行列を求め、RWRの計算を高速化する手法がある（例えば、特許文献1参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2012-160015号公報
【非特許文献】
【０００５】
【非特許文献１】堤田恭太、中辻真、内山俊郎、戸田浩之、内山匡：アクセスログを用いたクロスドメイン環境における情報推薦、第154回DBS・第107回IFAT合同研究発表会、2012年8月
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献１の技術で用いられるRWRの計算は、推薦を受ける被推薦ユーザの数が膨大な場合や、被推薦ユーザの利用履歴や付与した評点の情報が更新されるたびに新たに計算し直さなければならないため、膨大な計算量が必要となってしまう問題がある。
【０００７】
また、上記特許文献１は、RWRの計算を高速に行う方法であるが、前処理としてグラフを表す遷移行列のLU分解が必要となるため、利用される計算機の構成や処理能力によっては行列を読み込むためのメモリが不足し、計算が行えなくなることがある。
【０００８】
本発明は、上記の事情に鑑みなされたもので、本発明の目的は、RWRを用いたアイテム推薦を、より小規模な計算機であっても適用可能とするアイテム推薦装置、アイテム推薦方法、およびアイテム推薦プログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、第１の本発明は、RWR（Random Walk with Restart）を用いたアイテム推薦装置であって、ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報を格納したアイテム履歴記憶手段から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する擬似逆行列算出手段と、前記擬似逆行列を用いて推薦アイテムを決定する推薦アイテム決定手段と、を有し、前記擬似逆行列算出手段は、前記遷移行列から生成される行列をそのまま用いて前記擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、前記擬似逆行列を算出する。
【００１０】
上記アイテム推薦装置において、前記擬似逆行列算出手段は、前記遷移行列の大きさと、当該アイテム推薦装置が備えるリソースとを用いて、前記擬似逆行列の算出ができるか否かを判別する。
【００１１】
上記アイテム推薦装置において、前記擬似逆行列算出手段は、当該アイテム推薦装置が備えるメモリ容量が、前記遷移行列の大きさに所定数を乗じた大きさ未満の場合、前記擬似逆行列の算出ができないと判別する。
【００１２】
第２の本発明は、コンピュータが行う、RWRを用いたアイテム推薦方法であって、ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報を格納したアイテム履歴記憶部から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する擬似逆行列算出ステップと、前記擬似逆行列を用いて推薦アイテムを決定する推薦アイテム決定ステップと、を行い、前記擬似逆行列算出ステップは、前記遷移行列から生成される行列をそのまま用いて前記擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、前記擬似逆行列を算出する。
【００１３】
上記アイテム推薦方法において、前記擬似逆行列算出ステップは、前記遷移行列の大きさと、前記コンピュータが備えるリソースとを用いて、前記擬似逆行列の算出ができるか否かを判別する。
【００１４】
上記アイテム推薦方法において、前記擬似逆行列算出ステップは、前記コンピュータが備えるメモリ容量が、前記遷移行列の大きさに所定数を乗じた大きさ未満の場合、前記擬似逆行列の算出ができないと判別する。
【００１５】
第３の本発明は、上記アイテム推薦装置としてコンピュータを機能させるためのアイテム推薦プログラムである。
【発明の効果】
【００１６】
本発明によれば、RWRを用いたアイテム推薦を、より小規模な計算機であっても適用可能とするアイテム推薦装置、アイテム推薦方法、およびアイテム推薦プログラムを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態における情報推薦装置の構成図である。
【図２】本発明の一実施の形態におけるアイテム履歴データベースのテーブルのイメージ図である。
【図３】本発明の一実施の形態における情報推薦装置の処理のフローチャートである。
【図４】本発明の一実施の形態における擬似逆行列構築処理のフローチャートである。
【図５】本発明の一実施の形態における遷移行列のイメージ図である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図１は、本発明の一実施の形態における情報推薦装置（アイテム推薦装置）の構成を示す。
【００２０】
図示する情報推薦装置は、RWR（Random Walk with Restart）を用いてアイテムを推薦する装置であって、被推薦ユーザＩＤ取得部１１０、アイテム履歴データベース１２０、擬似逆行列構築部１３０、推薦アイテム予測処理部１４０、およびアイテム提示部１５０を備える。
【００２１】
被推薦ユーザＩＤ取得部１１０は、所定の外部装置または外部システムから、推薦するアイテムを提示する被推薦ユーザＩＤを取得する。
【００２２】
アイテム履歴データベース１２０（アイテム履歴記憶手段）には、ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とを含むアイテム履歴情報が格納されている。
【００２３】
擬似逆行列構築部１３０（擬似行列算出手段）は、アイテム履歴データベース１２０から取得したアイテム履歴情報を用いて、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す遷移行列を生成し、当該遷移行列から生成される行列の擬似逆行列を算出する。また、擬似逆行列構築部１３０は、遷移行列から生成される行列をそのまま用いて擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、擬似逆行列を算出する。
【００２４】
推薦アイテム予測処理部１４０（推薦アイテム決定手段）は、擬似逆行列構築部１３０が算出した擬似逆行列を用いて、推薦アイテムを決定する。
【００２５】
アイテム提示部１５０は、推薦アイテム予測処理部１４０が決定した推薦アイテムを、被推薦ユーザの端末１に提示する。
【００２６】
図２は、本実施形態におけるアイテム履歴データベース１２０のテーブルのイメージある。アイテム履歴データベース１２０は、各ユーザが、過去に利用した各アイテムの履歴情報が蓄積されたデータベースである。図示するアイテム履歴データベース１２０は、ユーザＩＤと、アイテムＩＤと、メタデータＩＤと、アイテムへの評価値とがそれぞれ対応付けて記憶されて、参照可能なデータベースとなっている。
【００２７】
アイテムは、コンピュータ上のコンテンツやプログラム、スーパー等での販売品など、様々なジャンルの品目を示すものである。メタデータは、対応するアイテムに関連する情報である。例えば、アイテムがアプリケーションプログラムの場合、その説明文に含まれる特徴的なキーワードであって、アイテムが商品の固有名の場合、それの該当するカテゴリー名（例えば、アイスクリーム等）などが考えられる。評価値は、各ユーザの対応するアイテムに対する評価を示す指標である。例えば、映画の評判サイト等の場合はユーザが付与した5段階評価、ページの閲覧の有無の場合は0か1、購買の有無などがある。なお、他の外部システムによって推定された値を評価値として利用することとしてもよい。
【００２８】
なお、アイテム履歴データベース１２０は、図２に示すように１つのテーブルで実現される場合に限定されず、複数のテーブルから構成されていてもよい。例えば、ユーザのアイテムの利用履歴について格納されたデータベースと、メタデータについて格納されたデータベースとを有し、個別に参照できるような形で実現されていてもよい。
【００２９】
また、アイテム履歴データベース１２０の各列のデータが存在しないサービスに適用される場合は、後述する図５に示す遷移行列が構築可能であって、後述する図３のＳ２２０の擬似逆行列を構築する処理、およびＳ２３０の推薦アイテムを決定する処理が行える限り、行や列の一部はなくてもよい。例えば、メタデータが存在しないサービスに適用される場合は、メタデータＩＤの情報および遷移行列上の行や列はなくてもよい。
【００３０】
なお、本実施形態の情報推薦装置は、例えば、ＣＰＵと、メモリと、ＨＤＤ等の外部記憶装置などを備えた汎用的なコンピュータシステムを用いることができる。このコンピュータシステムにおいて、ＣＰＵがメモリ上にロードされた情報推薦装置用のプログラムを実行することにより、情報推薦装置の各機能が実現される。また、情報推薦装置用のプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ−ＲＯＭなどのコンピュータ読取り可能な記録媒体に記憶することも、ネットワークを介して配信することもできる。
【００３１】
次に、本実施形態の処理について説明する。
【００３２】
図３は、本実施形態における情報推薦装置の処理のフローチャートである。図３のフローチャートに沿って、被推薦ユーザに対して推薦アイテムを提示する処理について、図１の構成図を参照し説明する。
【００３３】
ステップ２１０）  まず、被推薦ユーザＩＤ取得部１１０は、被推薦ユーザのＩＤを取得し、推薦アイテム予測処理部１４０に出力する。被推薦ユーザＩＤは、例えば、当該情報推薦装置に接続された外部の装置、システムなどのコンピュータから入力される。
【００３４】
ステップ２２０）  擬似逆行列構築部１３０は、アイテム履歴データベース１２０からユーザＩＤ、アイテムＩＤ、メタデータＩＤおよび評価値を取得し、後述する図４の処理により擬似逆行列を構築する。なお、ステップ２２０の擬似逆行列の構築処理は、ステップ２１０とは非同期に、バッチ処理などであらかじめ行っておくものとする。あるいは、Ｓ２１０の被推薦ユーザのＩＤを取得したタイミングで行うこととしてもよい。
【００３５】
ステップ２３０）  推薦アイテム予測処理部１４０は、被推薦ユーザＩＤ取得部１１０から被推薦ユーザＩＤを、擬似逆行列構築部１３０から擬似逆行列をそれぞれ受け取り、RWRを用いて被推薦ユーザに推薦するアイテムを決定する。
【００３６】
ステップ２４０）  アイテム提示部１５０は、推薦アイテム予測処理部１４０が決定した推薦アイテムを、被推薦ユーザに提示する。具体的には、ネットワークを介して、被推薦ユーザの端末に推薦アイテムの情報を送信し、表示する。
【００３７】
なお、図１の本実施形態では、情報推薦装置はアイテム履歴データベース１２０を含む構成として説明したが、この実施例に限定されることなく、アイテム履歴データベース１２０は、情報推薦装置の外部のデータベースであって、情報推薦装置は外部のデータベースであるアイテム履歴データベース１２０にアクセスし、データを取得することとしてもよい。
【００３８】
また、例えば、推薦アイテム予測処理部１４０の計算部分など、一部の処理がバッチ処理的に行われる場合には、推薦アイテム予測処理部１４０は、算出した推薦アイテムを一旦外部のデータベースに格納しておき、必要に応じて外部のデータベースにアクセスして推薦アイテムを取得し、アイテム提示部１５０へ出力することとしてもよい。
【００３９】
次に、図３のＳ２２０で、擬似逆行列構築部１３０が擬似逆行列を構築する処理について説明する。
【００４０】
図４は、擬似逆行列構築処理のフローチャートである。図４に沿って、擬似逆行列構築部１３０の処理の一例を説明する。
【００４１】
ステップ５１０）  まず、アイテム履歴データベース１２０から、各行毎に、ユーザＩＤ、アイテムＩＤ、メタデータＩＤおよび評価値を取得し、ユーザＩＤとアイテムＩＤとメタデータＩＤとのすべての2つの組合せ（順列）について、評価値を関連付ける（「ユーザＩＤとアイテムＩＤと評価値」、「ユーザＩＤとメタデータＩＤと評価値」、「アイテムＩＤとユーザＩＤと評価値」、「アイテムＩＤとメタデータＩＤと評価値」、「メタデータＩＤとユーザＩＤと評価値」、「メタデータＩＤとアイテムＩＤと評価値」）。
【００４２】
例えば、ユーザＩＤがu1、アイテムＩＤがi1、メタデータIDがm1、評価値が5であるような行の場合には、例えば、「u1とi1の評価値が5」、「u1とm1の評価値が5」等のように評価値を関連付ける。評価値が設定されていない行の場合には、評価値に例えば1などの固定値を用いるものとする。
【００４３】
ステップ５２０）  ステップ５１０で得られたユーザ、アイテムおよびメタデータの任意の組合せとその評価値を用いて、評価値行列Rを構築する。評価値行列Rのj行k列番目の要素をrj,kとする。例えば、jがu1、kがi1のときは、評価値の5を該当するrj,k（rju1,i1）に埋める。
【００４４】
ステップ５３０）  ステップ５２０で構築した評価値行列Rを、各列の値の和が1になるように正規化処理を行って、遷移行列Aを得る。遷移行列Aのj行k列番目の要素をaj,kと表すとき、要素aj,kは、評価値rj,kを用いて式（1）の通りに求められる。図５は、本実施形態において用いられる遷移行列のイメージである。遷移行列は、ユーザとアイテムの利用履歴関係およびアイテムとメタデータの関係を表す行列である。
【数１】
2014228918.tif 000003
【００４５】
ステップ５４０）  ここで、pをアイテムの関連度を格納する列ベクトル、αを0＜α＜1を満たす定数、Aをステップ５３０で得られた遷移行列、qを被推薦ユーザを表す起点ノードのみが1である列ベクトルとすると、RWRは式(2)のように表される。
【数２】
2014228918.tif 000004
【００４６】
さらに、RWR式(2)を式(3)の通りに変形し、得られたRWR式(3)の{I-(1-α)A}部分を、行列W（遷移行列Aから生成される行列）と置く。式(3)のIは、単位行列である。
【数３】
2014228918.tif 000005
【００４７】
ステップ５５０）  そして、式(3)のWが、当該情報推薦装置で処理できるか否かを判別する。すなわち、当該情報推薦装置で、擬似逆行列W-1の算出が可能か否かを判別する。算出可能か否かの条件分岐は、ステップ５３０で生成された遷移行列Aの大きさと、当該情報推薦装置（計算機、コンピュータ）が実装するリソースとを用いて判別される。
【００４８】
例えば、当該情報推薦装置が備えるメモリ容量が、遷移行列Aの大きさに所定数を乗じた大きさ未満の場合、擬似逆行列の算出ができないと判別することが考えられる。すなわち、Wが情報推薦装置のメモリに確保できるか否かより判別する。具体的には、情報推薦装置のメモリ容量が、遷移行列Aのデータサイズの3倍以上の場合は算出可能であると判別し、遷移行列Aのデータサイズの3倍よりも小さい場合は算出不可能であると判別することが考えられる。
【００４９】
処理可能な場合は（Ｓ５５０：ＹＥＳ）、ステップ５５１へ進み、処理不可能な場合は（Ｓ５５０：ＮＯ）、ステップ５５２へ進む。
【００５０】
ステップ５５１）  式(3)のWの擬似逆行列W-1を求める。Wを特異値分解して式(4)とするとき、擬似逆行列W-1は式(5)として得られる。式(5)のΣ-1の成分σ-1iiは、Σの成分をσiiとすると、σ-1ii=1/σiiとして得られる。
【数４】
2014228918.tif 000006
【数５】
2014228918.tif 000007
【００５１】
ステップ５５２）  式(3)のWにコンパクトに変換する行列を掛けながら、擬似逆行列W-1を算出する。Wはn行n列の行列とし、ランダムに要素を生成したn行r列の行列ΩをWの転置行列WTに掛けて式(6)を得る。rは、擬似逆行列W-1をコンパクトに変換するため、nより小さい値とする。より小規模な計算機を情報推薦装置として用いる場合、または処理の高速化を期待する場合は、より小さな値をrに設定し、より精確な計算結果が必要となる場合はよりnに近い値を設定して用いる。例えば、n=10000の場合には、r=100とするなど、情報推薦装置のリソースに応じて設定することが考えられる。なお、rの値は100に限定されることなく、nより小さい自然数の範囲内で設定可能である。
【００５２】
次に、式(7)により、Wに式(6)のYを掛けて行列Bを得る。さらに、式(8)により、式(7)のBに、ランダムに要素を生成したr行r列の行列Ψを掛けてZを求める。式(9)により、式(8)のZの転置行列ZTにBを掛けてCを得る。式(10)により、r行r列にコンパクトになったCを特異値分解して、式(10)、(11)により、ステップ５５１と同様にΣ-1を求めてからZとYTを掛けてW-1を得る。
【数６】
2014228918.tif 000008
【数７】
2014228918.tif 000009
【数８】
2014228918.tif 000010
【数９】
2014228918.tif 000011
【数１０】
2014228918.tif 000012
【数１１】
2014228918.tif 000013
【数１２】
2014228918.tif 000014
【００５３】
ステップ５６０）  ステップ５５１もしくはステップ５５２で得た擬似逆行列W-1を推薦アイテム予測処理部１４０へ出力し、擬似逆行列構築部１３０の処理を終了する。
【００５４】
最後に、擬似逆行列構築部１３０から取得した擬似逆行列W-1を用いて推薦するアイテムを決定する推薦アイテム予測処理部１４０の処理について説明する。すなわち、取得した被推薦ユーザＩＤと各アイテムＩＤとの関連度を求め、その値の高いアイテムを推薦アイテムとするRWR（前述の式(3)）を用いる。
【００５５】
前述の通り、式(3)のqの被推薦ユーザを表すベクトルの要素を1とし、W-1にqを掛けて得られるベクトルpからアイテムを表すノードについて関連度の高いものを、推薦アイテムとしてアイテム提示部１５０へ出力する。
【００５６】
なお、本実施形態では、被推薦ユーザに対してアイテムを提示する手順について記述したが、qを表すものをアイテム（被推薦アイテム）、出力をアイテムとすると、被推薦アイテムと関連の強いアイテムを提示することができる。また、qをメタデータとし、推薦対象をアイテムとすると、メタデータと関連の強いアイテムの提示が可能となる。
【００５７】
以上説明した本実施形態では、遷移行列から生成される行列をそのまま用いて擬似逆行列の算出ができない場合、前記行列を当該行列より小さな行列に変換し、擬似逆行列を算出する。これにより、本実施形態では、小規模な計算機であっても、RWRを用いた情報推薦を実施することができる。すなわち、利用する計算機の構成や処理能力によっては行列を読み込むためのメモリが不足し、計算が行えなくなることを回避することができる。
【００５８】
なお、本発明は上記実施形態に限定されるものではなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５９】
１１０：被推薦ユーザＩＤ取得部
１２０：アイテム履歴データベース
１３０：擬似逆行列構築部
１４０：推薦アイテム予測処理部
１５０：アイテム提示部
【図１】
2014228918.tif 000015
【図２】
2014228918.tif 000016
【図３】
2014228918.tif 000017
【図４】
2014228918.tif 000018
【図５】
2014228918.tif 000019