(57)【要約】  【課題】ユーザの利用履歴に基づく協調フィルタリングの計算量を減らし、ユーザ数やアイテム数が多い場合でも処理に要する時間を短縮可能にする。  【解決手段】ログ収集モジュール１は、ユーザａ，ｂ，ｃ，ｄが各アイテムを利用したときの評価値を収集する。収集された評価値は、利用履歴データ２として蓄積される。スコア算出モジュール３は、ユーザが未評価のアイテムに対する予測評価値を算出する。予測評価値の算出に際しては、対象ユーザにおいて同じ値になる項の計算を省略して予測評価値を算出する。算出された予測評価値は、スコア算出結果４として保持される。推薦アイテム抽出モジュール５は、スコア算出結果４に基づいて、予測評価値が高いアイテムをユーザに推薦する。  【選択図】図１
2005122368.tif 000002
【特許請求の範囲】
【請求項１】
全ユーザの利用履歴データに基づいて対象ユーザへの推薦アイテムを抽出するための高速協調フィルタリング方法において、
各ユーザの各アイテムに対する評価値を利用履歴データとして収集する利用履歴データ収集過程と、
前記利用履歴データから対象ユーザの未評価アイテムに対する予測評価値を算出する予測評価値算出過程と、
前記予測評価値に基づいて対象ユーザへの推薦アイテムを抽出する推薦アイテム抽出過程とを有し、
前記予測評価値算出過程は、対象ユーザにおいて同一値である項の計算を省略して予測評価値を算出することを特徴とする高速協調フィルタリング方法。
【請求項２】
前記予測評価値算出過程は、対象ユーザとその他のユーザの相関値の算出を含み、該相関値の算出では、対象ユーザとその他のユーザの両者が評価済みの評価済みアイテムについてのみの計算を行うことを特徴とする請求項１に記載の高速協調フィルタリング方法。
【請求項３】
対象ユーザおよびその他のユーザの各アイテムに対する評価値から算出できる値を予め計算して保存しておき、前記相関値の算出に際してはその保存された値を用いることを特徴とする請求項２に記載の高速協調フィルタリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速協調フィルタリング方法に関し、特に、ユーザの利用履歴からアイテムを推薦するリコメンダシステムで利用される高速協調フィルタリング方法に関する。
【背景技術】
【０００２】
従来、ユーザの利用履歴からアイテム（商品など）を推薦するリコメンダシステムで利用される協調フィルタリング技術として、全ユーザの履歴情報を収集し、収集された利用履歴に基づきユーザ間の相関値や類似度を算出し、対象ユーザの未評価アイテムに対する予測評価値（スコア）を算出するMemory based algorithm（メモリ ベースト アルゴリズム）が知られている。
【０００３】
Memory based algorithmでは、下記（１）式にしたがってアイテムの予測評価値Ｐａ，ｊを算出する。
【０００４】
【数１】
2005122368.tif 000003
【０００５】
通常、リコメンダシステムでは、各ユーザに対して上記（１）式により未評価アイテムの予測評価値（スコア）Ｐａ，ｊを算出し、そのスコアの上位数件のアイテムを推薦する手法が採用される。
【０００６】
上記（１）式におけるユーザａとユーザｉの相関値ｗ（ａ，ｉ）としてはPearson（ピアソン）相関値やベクトル類似度などが用いられる。Pearson相関値、ベクトル類似度はそれぞれ、下記（２），（３）式によって定義される。
【０００７】
【数２】
2005122368.tif 000004
【０００８】
【数３】
2005122368.tif 000005
【非特許文献１】John S.Breese et al:“Empirical Analysis of Predictive Algorithms for Collaborative Filtering”Proceeding of the 14th Conference of Uncertainty on Artificial Intelligence, pp.43-52,1998
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記従来技術のMemory based algorithmでは、未評価アイテムの予測評価値Ｐａ，ｊの算出において、全ユーザおよび全アイテムを計算対象としているため、ユーザ数やアイテム数の増加の伴い、その算出の処理時間が膨大になってしまうという課題がある。
【００１０】
また、各ユーザに対し、協調フィルタリングによって算出されたスコアの上位数件のアイテムを推薦するという仕組みでリコメンダシステムを実装する場合、上記従来技術のMemory based algorithmでは、後述するところから明らかになるように、不要な計算が行われている。
【００１１】
本発明の目的は、上記課題を解決し、ユーザの利用履歴に基づく協調フィルタリングの計算量を減らし、ユーザ数やアイテム数が多い場合でも協調フィルタリング処理に要する時間を短縮することができる高速協調フィルタリング方法を提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明は、全ユーザの利用履歴データに基づいて対象ユーザへの推薦アイテムを抽出するための高速協調フィルタリング方法において、各ユーザの各アイテムに対する評価値を利用履歴データとして収集する利用履歴データ収集過程と、前記利用履歴データから対象ユーザの未評価アイテムに対する予測評価値を算出する予測評価値算出過程と、前記予測評価値に基づいて対象ユーザへの推薦アイテムを抽出する推薦アイテム抽出過程とを有し、前記予測評価値算出過程は、対象ユーザにおいて同一値である項の計算を省略して予測評価値を算出することを第１の特徴とする。
【００１３】
また、本発明は、前記予測評価値算出過程が、対象ユーザとその他のユーザの相関値の算出を含み、該相関値の算出では、対象ユーザとその他のユーザの両者が評価済みの評価済みアイテムについてのみの計算を行うことを第２の特徴とする。
【００１４】
さらに、本発明は、対象ユーザおよびその他のユーザの各アイテムに対する評価値から算出できる値を予め計算して保存しておき、前記相関値の算出に際してはその保存された値を用いることを第３の特徴とする。
【発明の効果】
【００１５】
本発明では、予測評価値の算出に際し、対象ユーザにおいて同一値になる項の計算を省略するので、各ユーザの全アイテムに対する予測評価値の計算にかかるコストを（ユーザ数）×（ユーザの平均評価アイテム数）にすることができ、予測評価値を求める際の計算量を大幅に減らすことができる。
【００１６】
また、本発明では、対象ユーザとその他のユーザの相関値の算出に際し、対象ユーザとその他のユーザの両者が評価済みの評価済みアイテムについてのみの計算を行い、いずれかが未評価のアイテムについての計算は行わないので、その計算量を大幅に減らすことができる。
【００１７】
さらに、対象ユーザおよびその他のユーザの各アイテムに対する評価値から算出できる値を予め計算して保存しておき、相関値算出に際してはその保存された値を用いることにより、さらに計算量を減らすことができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明を説明する。図１は、本発明に係る高速協調フィルタリング方法が適用されたリコメンダシステムのブロック図であり、図２は、予測評価値算出の動作概要の説明図である。ここでは、ユーザａ，ｂ，ｃ，ｄ、アイテム（イ），（ロ），（ハ），（ニ），（ホ），・・，（ヘ）が存在する場合を想定する。
【００１９】
ログ収集モジュール１は、ユーザａ，ｂ，ｃ，ｄが各アイテムを利用したときの評価値を収集する。収集された評価値は、利用履歴データ２として蓄積される。スコア算出モジュール３は、ユーザの未評価アイテムに対する予測評価値を算出する。算出された予測評価値は、スコア算出結果４として保持される。推薦アイテム抽出モジュール５は、スコア算出結果４に基づいて、予測評価値が高いアイテムをユーザに推薦する。
【００２０】
図２に示すように、ユーザａのアイテム（イ），（ロ），（ハ），（ニ），（ホ）に対する評価値（「5,1,4,2,3」）が既に収集されており、ユーザｂ，ｃ，ｄについてはアイテム（イ），（ロ），（ハ），（ニ），（ホ）に対する評価値に加えてさらにアイテム（へ）に対する評価値が収集されていると仮定する。なお、本例では、数値の大きさで評価程度まで表しているが、評価する場合を「１」、評価しない場合を「０」などによって表すようにしてもよい。
【００２１】
ユーザａのアイテム（へ）に対する評価値を予測する場合、つまり、ユーザａを対象ユーザとする場合、ユーザａと他のユーザｂ，ｃ，ｄとの間で評価値の相関あるいは類似度を調べる。本例では、ユーザａとユーザｃの相関あるいは類似度が大である。この場合、ユーザａのアイテム（ヘ）に対する評価値は、ユーザｃのアイテム（へ）に対する評価値「5」程度になると予測できる。上記のようにして未評価アイテムに対する予測評価値が算出され、予測評価値の高い上位数件の未評価アイテムが推薦アイテムとして抽出される。
【００２２】
予測評価値は、上記（１）式によって算出できるが、本発明では、以下に述べるように、上記（１）式を簡略化し、不要な計算を行わないようにして計算にかかるコストを少なくする。
【００２３】
Memory based algorithmにおいて予測評価値Ｐａ，ｊを算出するための上記（１）式は、下記（４）式のように変形できる。
【００２４】
【数４】
2005122368.tif 000006
【００２５】
上記（４）式は、さらに下記（５）式のように変形できる。
【００２６】
【数５】
2005122368.tif 000007
【００２７】
上記（５）式の右辺第１項および第３項は、ユーザａにおいて同一値になるので定数とみなすことができる。リコメンダシステムでは、計算結果の値そのものよりも全アイテム中の各アイテムに対する予測評価値Ｐａ，ｊの順位を重視し、そのスコアが上位数件のアイテムを推薦するので、それを考慮すると、予測評価値Ｐａ，ｊは、下記（６）式で十分となる。
【００２８】
【数６】
2005122368.tif 000008
【００２９】
上記（６）式による効果は以下のとおりである。ユーザｉの、あるアイテムに対する評価値が０のとき、上記（６）式におけるΣの中は０となり、計算を省略することができる。これに対して上記（１）式のΣの中は同条件においても
【００３０】
【数７】
2005122368.tif 000009
【００３１】
となり、和（ＳＵＭ）を求める必要がある。
【００３２】
ユーザａの全アイテムに対する予測評価値の計算にかかるコストは、上記（６）式によれば（ユーザ数）×（ユーザの平均評価アイテム数）となるが、上記（１）式によれば（ユーザ数）×（アイテム数）である。アイテム数に比べてユーザの平均評価アイテム数は極めて少ないので、予測評価値を求める際の計算量を大幅に減らすことができる。
【００３３】
また、上記（２），（３）式を以下のように簡略化することにより、Pearson相関値、ベクトル類似度を求める際の算出量を減らすことができる。まず、Pearson相関値を算出する上記（２）式の簡略化について説明する。
【００３４】
上記（２）式の分母の左側部に注目して展開すると、下記（８）式が得られる。
【００３５】
【数８】
2005122368.tif 000010
【００３６】
同様に、上記（２）式の分母の右側部に注目して展開すると、下記（９）式が得られる。
【００３７】
【数９】
2005122368.tif 000011
【００３８】
さらに、、上記（２）式の分子に注目して展開すると、下記（１０）式が得られる。
【００３９】
【数１０】
2005122368.tif 000012
【００４０】
ここで、
【００４１】
【数１１】
2005122368.tif 000013
【００４２】
【数１２】
2005122368.tif 000014
【００４３】
【数１３】
2005122368.tif 000015
【００４４】
【数１４】
2005122368.tif 000016
【００４５】
とし、上記（３）式を上記（８），（９），（１０）式を用いて表すと、下記（１５）式が得られる。上記Ａ，Ｂ，Ｃ，Ｄは、ユーザａおよびその他のユーザの各アイテムに対する評価値から予め計算して保存しておくことができる。
【００４６】
【数１５】
2005122368.tif 000017
【００４７】
また、各ユーザの未評価データを考慮しないで未評価値のスコアを算出する場合には、ＩをＩａ∩Ｉｉ に置き換えた下記（１６）式によってPearson相関値を計算することができる。
【００４８】
【数１６】
2005122368.tif 000018
【００４９】
ただし、ここで、Ａ，Ｂ，Ｃ，Ｄは、上記（１１），（１２），（１３），（１４）式で表されるものである。
【００５０】
さらに、ユーザａの全ユーザに対するPearson相関値は、下記（１７）式で表すことができる。
【００５１】
【数１７】
2005122368.tif 000019
【００５２】
リコメンダシステムにおいて、Pearson相関値は、ユーザａと全ユーザとの間で比較可能であれば実用上問題ないので、上記（１７）式の
【００５３】
【数１８】
2005122368.tif 000020
【００５４】
は、省略しても差し支えない。したがって、Pearson相関値は、下記（１９）式で十分となる。
【００５５】
【数１９】
2005122368.tif 000021
【００５６】
上記（１６），（１９）式による効果は以下のとおりである。上記（１６）式では、ユーザａとユーザｉの評価済みアイテムに比例して計算量が増加する。これに対して上記（２）式ではアイテム数に比例して計算量が増加する。総アイテム数に比べて評価済みアイテム数は極めて少ないのが普通であるので、上記（１６）式によれば計算量を大幅に減らすことができる。
【００５７】
また、上記（１６）式において、上記（１１），（１２），（１３），（１４）式で表されるＡ，Ｂ，Ｃ，Ｄを予め計算して保持しておくことにより、さらに計算量を減らすことが可能であり、実質的には
【００５８】
【数２０】
2005122368.tif 000022
【００５９】
の計算コストＯ（ｎ２）が上記（１６）式の計算コストとなる。上記（１９）式を採用すればさらに計算量を減らすことができる。
【００６０】
次に、ベクトル類似度を算出する上記（３）式の簡略化について説明する。上記（３）式は、下記（２１）式のように変形できる。
【００６１】
【数２１】
2005122368.tif 000023
【００６２】
ベクトル類似度は、ユーザａと全ユーザとの間で比較可能であれば実用上問題ないので、上記（２１）式の
【００６３】
【数２２】
2005122368.tif 000024
【００６４】
は、省略しても差し支えない。したがって、
【００６５】
【数２３】
2005122368.tif 000025
とすると、ベクトル類似度は、下記（２４）式で十分となる。
【００６６】
【数２４】
2005122368.tif 000026
【００６７】
上記（２４）式を採用すれば、上記（２３）式で表されるＡを予め計算して保持しておくことにより、計算量を減らすことができる。また、乗算の回数を１回減らすことができる。
【００６８】
以上、説明したように本発明によれば、協調フィルタリングの計算量を減らすことができ、例えばユーザ数やアイテム数がそれぞれ数万程度の場合、協調フィルタリング処理に要する時間を、従来技術に比べて１／１０程度に短縮することができる。
【図面の簡単な説明】
【００６９】
【図１】本発明に係る高速協調フィルタリング方法が適用されたリコメンダシステムのブロック図である。
【図２】予測評価値算出の動作概要の説明図である。
【符号の説明】
【００７０】
１・・・ログ収集モジュール、２・・・利用履歴データ、３・・・スコア算出モジュール、４・・・スコア算出結果、５・・・推薦アイテム抽出モジュール、ａ〜ｄ・・・ユーザ、（イ）〜（ヘ）・・・アイテム
【図１】
2005122368.tif 000027
【図２】
2005122368.tif 000028