(57)【要約】      （修正有）【課題】協調フィルタリング処理に係る計算処理、特に固有値の計算を効率化する手法を提供する。【解決手段】n人のユーザのm個のアイテムに対する嗜好および／または受容の度合いが肯定的であることを表すスコア１または否定的または未知であることを表すスコア０の何れかを要素とし、縦横が各ユーザと各アイテムとの和集合からなる（n＋m）×（n＋m）の正方行列、2012079225.tif 000096（ただし、Ｚは、縦横がn×mの二値の行列、Ｏはゼロ値行列）が与えられたとき、ユーザとアイテムとが強い関係性を有する組み合わせを少なくとも一つのクラスターとして抽出する処理の中で前記行列Sの最大固有値λ1および固有ベクトルw1を算出するにあたり、（n＋m）×（n＋m）次元の前記行列Sのスパース性に着目して固有値を求める計算式をn×n次元に縮小することにより固有値計算に伴う負担を低減する。【選択図】なし【特許請求の範囲】
【請求項１】
n 人のユーザのm 個のアイテム（n、m は１より大きい整数）に対する嗜好および／または受容の度合いが肯定的であることを表すスコア１または否定的または未知であることを表すスコア０の何れかを要素とし、縦横が各ユーザと各アイテムとの和集合からなる（n＋m ）×（n＋m ）の正方行列、
【数１】
2012079225.tif 000086
（ただし、Ｚは、縦横がn×m の二値の行列、Ｏはゼロ値行列）
が与えられたとき、ユーザとアイテムとが強い関係性を有する組み合わせを少なくとも一つのクラスターとしてコンピュータが抽出する処理であって、
前記行列S の最大固有値λ1 および固有ベクトルw1 を算出するにあたり、前記固有ベクトルw1 をユーザについての部分ベクトルwu1 とアイテムについての部分ベクトルwi1 とに分け、前記行列S の固有値を求める計算式を、
【数２】
2012079225.tif 000087
の２つに分割し、（３）式よりwu1 を用いてwi1 を表した
【数３】
2012079225.tif 000088
を（２）式に代入してなる
【数４】
2012079225.tif 000089
の固有値計算を解いてベクトルwu1 を求め、
求めたwu1 を（４）式に適用してベクトルwi1 を求めることにより固有ベクトルw1を得、
得られた固有ベクトルw1 の各要素が予め定められた閾値以上か否かに応じて各要素に対応するユーザおよびアイテムが第１のクラスターに属するか否かを少なくとも決定する分類工程と、
前記分類工程の決定に基づく第１のクラスターのユーザに対して第１のクラスターのアイテムを推薦候補とする推薦工程とを備えることを特徴とする協調フィルタリング処理方法。
【請求項２】
前記分類工程は、（４）、（５）式に代えて、（２）式よりwi1 を用いてwu1 を表した
【数５】
2012079225.tif 000090
を（３）式に代入してなる
【数６】
2012079225.tif 000091
の固有値計算を解いてベクトルwi1 を求め、
求めたwi1 を（６）式に適用してベクトルwu1 を求めることにより固有ベクトルw1を得る請求項１に記載の方法。
【請求項３】
前記分類工程は、n ＜m の場合に（４）および（５）式を用いて固有ベクトルw1 を得る請求項１に記載の方法。
【請求項４】
前記分類工程は、n ＞m の場合に（６）および（７）式を用いて固有ベクトルw1 を得る請求項２に記載の方法。
【請求項５】
前記分類工程は、ユーザとアイテムの組み合わせを二以上のクラスターとして抽出するために第１のクラスターに属するユーザおよびアイテムを決定した後、（１）式の行列S に逐次的クラスター抽出のアルゴリズムを適用し、
前記アルゴリズムは、第k クラスター（k は１より大きい整数）を抽出するにあたり、k ＝２のときは（１）式の行列S の各対角要素を所定の規則に基づき修正した行列であり、k ＞２のときは、第（k −１）クラスターを抽出する際に用いた行列Sk-1 の各対角要素を所定の規則に基づき修正した行列
【数７】
2012079225.tif 000092
（ただし、Wu はsii を第i 対角要素に持つn×n 対角行列、i は１以上n 以下の整数、Wi はsn+t,n+t を第t 対角要素に持つm×m 対角行列、t は１以上m 以下の整数）
の最大固有値λkおよび固有ベクトルwk を算出するために、前記固有ベクトルwk をユーザについての部分ベクトルwuk とアイテムについての部分ベクトルwik とに分け、前記行列Sk の固有値を求める計算式を、
【数８】
2012079225.tif 000093
（ただし、InおよびImはそれぞれn 次元、m 次元の単位行列）
の２つに分割し、（１０）式よりwuk を用いてwik を表した下記（１２）式を（９）式に代入してなる下記（１１）式の固有値計算を解いてwuk を求め、求めたwuk を（１２）式に適用してwik を求めることにより固有ベクトルwk を得、
【数９】
2012079225.tif 000094
あるいは、（９）式からwik を用いてwuk を表した下記（１４）式を（１０）式に代入してなる下記（１３）式の固有値計算を解いてwik を求め、求めたwik を（１４）式に適用してwuk を求めることにより固有ベクトルwk を得、
【数１０】
2012079225.tif 000095
得られた固有ベクトルwk の各要素が予め定められた閾値と比較して閾値以上か否かに応じて各要素に対応するユーザおよびアイテムが第k クラスターに属するか否かを決定する請求項１〜４の何れか一つに記載の方法。
【請求項６】
前記分類工程は、n ＜m の場合に（１１）および（１２）式を用いて固有ベクトルwk を得る請求項５に記載の方法。
【請求項７】
前記分類工程は、n ＞m の場合に（１３）および（１４）式を用いて固有ベクトルwk を得る請求項５に記載の方法。
【請求項８】
請求項１または２に記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、協調フィルタリング処理方法およびプログラムに関する。
【背景技術】
【０００２】
協調フィルタリングでは、嗜好の類似した近傍ユーザ群を抽出し、群内のユーザが好むアイテムを推薦することで、ネットワーク上で疑似的に「くちこみ」が実装される（例えば、非特許文献１参照）。
いま、n 人のユーザとm 個のアイテムの関連性を表すn×m データ行列Z =[zij] が得られたとする。
たとえば、商品の購買履歴データであれば、zij はユーザi がアイテムj を購入していれば「１」、それ以外は「０」（ゼロ）を持つものとし、要素「０」は必ずしも否定的な関係のみではなく未評価（未購入）を含む。
【０００３】
発明者らは、ユーザやアイテムを区別なくノードととらえると、関係性データは社会科学におけるネットワークグラフとの類似性を有することに着目し、グラフ構造の均衡化に基づく手法を発展させることで、ユーザ・アイテム共クラスターを抽出する手法を提案した（例えば、特許文献１、非特許文献２参照）。
【０００４】
即ち、CartwrightとHararyは、均衡がとれているシステムでは、互いに正の関係性を持つノードからなる二つのグループに分割されることを示している（例えば、非特許文献３参照）。また、Davisは構造の均衡化をより一般化してとらえ、２群分割された部分集合がさらに小さな部分集合に分割できる場合として、その再分割後の部分集合がその中では互いに正の関係性を持つ一方で異なる部分集合間では正の関係性を持たない状況を指摘している（例えば、非特許文献５参照）。
そこで、発明者らは前記特許文献１および非特許文献２において、n×m の長方形状の関係性データに未知要素０（ゼロ）を組み込むことで、正方形状の(n＋m)×(n＋m) ブロック行列としてユーザ・アイテム関係性行列を再構築する手法を示した。
【０００５】
【数１】
2012079225.tif 000002
さらに、標本間の類似度を要素に持つ関係性データからファジィクラスターを逐次的に抽出するTsuda らの手法（例えば、非特許文献４参照）を援用することで、共クラスター抽出を行った。
より詳細に述べると、要素i とj の非負の類似度をeij とおき、eij =eji, eij ≧0 であるとする。第k クラスター（k は１より大きい整数）のメンバシップベクトルwk の抽出のための目的関数は以下のように定義される。
【０００６】
【数２】
2012079225.tif 000003
ここで、第２項はクラスターの重なりを防ぐためのペナルティ項で、第１クラスターの抽出では０（ゼロ）とおかれる。dup(wk, wt) が制約を満たすために付加されたペナルティ項であり、
【０００７】
【数３】
2012079225.tif 000004
のようにおく。βt はペナルティ項の重みで、前記非特許文献４ではクラスターの凝集度を考慮して以下のように定めている。
【０００８】
【数４】
2012079225.tif 000005
ηはペナルティ項が第１項より十分大きくなる値とする。
最適なwk は行列S =[sij] の最大固有値に対応する固有ベクトルとして求まる。
【０００９】
【数５】
2012079225.tif 000006
【００１０】
協調フィルタリング問題では、ユーザ・アイテムクラスターの抽出時にユーザが排他的であれば必ずしもアイテムは排他的である必要はなく、いくつかのクラスターで共有されうるべきである（前記非特許文献２参照）。そこで、アイテムの共有を許容する場合には、メンバシップベクトルwt を
【００１１】
【数６】
2012079225.tif 000007
と分割し、
【００１２】
【数７】
2012079225.tif 000008
と
【００１３】
【数８】
2012079225.tif 000009
とおいた上で、ユーザのみが排他的となるように
【００１４】
【数９】
2012079225.tif 000010
なる制約を用いる。そのため、第k 番目のクラスターの抽出に用いる関係性行列では、対角要素sii を以下のように修正して最大固有値と対応する固有ベクトルを算出する。
【００１５】
【数１０】
2012079225.tif 000011
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２０１０−７３１９５号公報
【非特許文献】
【００１７】
【非特許文献１】J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker, L. R. Gardon and J. Riedl: Grouplens: applying col-laborative filtering to usenet news; Communications of the ACM, Vol.40, No.3, pp.77-87 (1997)
【非特許文献２】本多克宏、野津亮、市橋秀友: 逐次的なユーザ・アイテム クラスター抽出に基づく協調フィルタリング, システム制御 情報学会論文誌, Vol.22, No.10, pp.364-370 (2009)
【非特許文献３】D. Cartwright and F. Harary: Structural balance, a generalization of Heider's theory, Psychological Review , Vol. 63, pp. 167-293 (1956)
【非特許文献４】K. Tsuda, M. Minoh and K. Ikeda: Extracting straight lines by sequential fuzzy clustering, Pattern Recognition Letters, Vol. 17, pp. 643-649 (1996)
【非特許文献５】J. A. Davis: Clustering and structural balance in graph, Human Relation, Vol. 20, pp. 181-187 (1967)
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述の協調フィルタリングによる処理手法は高い推薦性能を得ることができたものの、以下の課題がある。
（１）縦横が（ユーザ数＋アイテム数）の(n＋m)×(n＋m)行列は大きく、計算処理に時間  がかかる。特に固有値の計算に要する時間の比重が大きい。固有値計算に用いる行列の  要素数を減らすことが望まれている。
【００１９】
（２）新規のユーザに対する推薦アイテムの探索手順が未定義である。従来の計算モデル  をそのまま適用すると、新規ユーザが来た場合には、すべての計算を再度、行う必要が  あり、処理が煩雑であり、かつ時間を要する。そこで、簡便な計算で新規ユーザの追加  に適用できるような計算モデルの改良が望まれている。
この発明は、以上のような事情を考慮してなされたものであって、関係性ブロック行列のスパース性に着目して、協調フィルタリング処理に係る計算処理、特に固有値の計算を効率化する手法を提供するものである。
【課題を解決するための手段】
【００２０】
この発明は、関係性ブロック行列のスパース性に着目して、協調フィルタリングに係る計算処理を効率的に行う手法を実現し、かつ新規ユーザが追加されても前記計算処理に係る負担を最小限にとどめる手法を提供するものである。
【００２１】
前述の課題を解決するために、この発明は、
（ｉ）n 人のユーザのm 個のアイテム（n、m は１より大きい整数）に対する嗜好および／または受容の度合いが肯定的であることを表すスコア１または否定的または未知であることを表すスコア０の何れかを要素とし、縦横が各ユーザと各アイテムとの和集合からなる（n＋m ）×（n＋m ）の正方行列、
【数１１】
2012079225.tif 000012
【００２２】
（ただし、Ｚは、縦横がn×m の二値の行列、Ｏはゼロ値行列）
が与えられたとき、ユーザとアイテムとが強い関係性を有する組み合わせを少なくとも一つのクラスターとしてコンピュータが抽出する処理であって、前記行列S の最大固有値λ1 および固有ベクトルw1 を算出するにあたり、前記固有ベクトルw1 をユーザについての部分ベクトルwu1 とアイテムについての部分ベクトルwi1 とに分け、前記行列S の固有値を求める計算式を、
【数１２】
2012079225.tif 000013
の２つに分割し、（７）式よりwu1 を用いてwi1 を表した
【数１３】
2012079225.tif 000014
【００２３】
を（６）式に代入してなる
【数１４】
2012079225.tif 000015
の固有値計算を解いてベクトルwu1 を求め、求めたwu1 を（８）式に適用してベクトルwi1 を求めることにより固有ベクトルw1を得、得られた固有ベクトルw1 の各要素が予め定められた閾値以上か否かに応じて各要素に対応するユーザおよびアイテムが第１のクラスターに属するか否かを少なくとも決定する分類工程と、前記分類工程の決定に基づく第１のクラスターのユーザに対して第１のクラスターのアイテムを推薦候補とする推薦工程とを備えることを特徴とする協調フィルタリング処理方法を提供する。また、この発明は、
【００２４】
（ii）前記分類工程が、前記（８）、（９）式に代えて、（６）式よりwi1 を用いてwu1 を表した
【数１５】
2012079225.tif 000016
を（７）式に代入してなる
【数１６】
2012079225.tif 000017
の固有値計算を解いてベクトルwi1 を求め、
求めたwi1 を（１０）式に適用してベクトルwu1 を求めることにより固有ベクトルw1を得る協調フィルタリング処理方法を提供する。
また、異なる観点から、この発明は、前記（ｉ）または（ii）の方法をコンピュータに実行させるためのプログラムを提供する。
【発明の効果】
【００２５】
この発明の協調フィルタリング処理方法は、各ユーザおよび各アイテムの前記クラスターへの属否を判断する固有ベクトルw1 を算出するにあたり、縦横が（n＋m ）×（n＋m ）の正方行列S の固有値を求める計算式を直接解く代わりに、前記（ｉ）では縦横がn ×n の行列ZZT の計算式である（９）式の固有値計算を行うので、（n＋m ）×（n＋m ）次元の固有値計算を直接解く場合に比べて計算時間を短縮することができる。即ち、繰り返し計算を伴う固有値計算を（n＋m ）×（n＋m ）次元からn ×n 次元に縮小するので固有値計算に伴う負担を低減することができる。
【００２６】
また、前記（ii）では、縦横がm ×m の行列ZTZ の計算式である（１１）式の固有値計算を行うので、（n＋m ）×（n＋m ）次元の固有値計算を直接解く場合に比べて計算時間を短縮することができる。即ち、繰り返し計算を伴う固有値計算を（n＋m ）×（n＋m ）次元からm ×m 次元に縮小するので固有値計算に伴う負担を低減することができる。
前記（ｉ）または（ii）の方法をコンピュータに実行させるためのプログラムについても同様の効果を奏する。
【００２７】
この発明において、分類工程は、１以上のユーザとアイテムとのクラスターを抽出する。前記（ｉ）または（ii）の方法では、そのうち第１クラスターの抽出に係る特徴に着目している。第２クラスター以降の抽出に係る特徴については後述する。
（１）式の正方行列S は、n 人のユーザがm 個のアイテムを評価する場合の各スコアの行列としてのn×m 次元の評価値行列を（n＋m ）×（n＋m ）次元の正方行列に拡張したものである。一般に、協調フィルタリングは、評価値行列の一部に評価済みのスコアが格納され、一部が未評価（欠測値）の状態で適用される。協調フィルタリングは前記評価値行列中の欠測値の推定に用いられるからである。各スコアのとり得る範囲は、事例に応じて適宜決定される。各スコアがどのような範囲をとり得るかにかかわらず、この発明においては前記評価値行列の各スコアが予め定められた閾値以上か否かに注目し、拡張された正方行列S の要素をゼロまたは正値に２値化する。スコアが未知の要素はゼロで置換する。
【００２８】
（１）式の正方行列S は、認知的均衡化理論において用いられる関係性行列の形式に適合させるべく前記評価値行列を拡張したものである。各各要素sijがとり得る値は予め定められる。嗜好の度合いおよび／または受容の度合いを表すスコアの一例として、次のものが挙げられる。各ユーザが各アイテムを評価した評価値があれば、その評価値をスコアとして適用できる。また、各ユーザの各アイテムについての購入履歴のデータがあれば、その購入履歴データをスコアとして適用できる。
【００２９】
それらのスコアと前記正方行列の要素sijがとる値との対応関係の一例として、次のものが挙げられる。肯定的な関係、即ち、ユーザの評価として「好む」とされた場合やユーザがそのアイテムを購入済の場合に対応して「＋１」、未知または否定的な関係、即ち、ユーザの評価が「好まない」または「その他」とされた場合やそのアイテムについてユーザが未購入（不明を含んでもよい）の場合に対応して「０」（ゼロ）が定められる。
逐次的クラスター抽出のアルゴリズムは、ファジィクラスタリングの一手法として知られ、n ×n 関係性行列が与えられた場合に、関係性の強い個体の群（クラスター）を一つずつ逐次的に取り出す手法である。
最小均衡化アルゴリズムは、関連性行列が与えられたときに系の乖離度合いが最小となる均衡状態に不均衡な辺の関係を変化させる手順を求めるアルゴリズムである（例えば、O. Katai and S. Iwai: Studies on the balancing, the minimal balancing, and the minimum balancing processes for social groups with planar and nonplanar graph structures, J. Math. Psychol., 18, 2, 141-176 (1978)参照）。前記アルゴリズムを適用すると、系の各ノード（この発明におけるユーザおよびアイテムに対応する）が２つのグループに分類される。同一グループに属するユーザは評価が類似し、各ユーザと同一グループに属するアイテムに高い評価を与えている。
【図面の簡単な説明】
【００３０】
【図１】この発明の実験例２において、アイテムのクラスター指標を更新せずに新規ユーザの割合を増やしていったときの平均誤差の推移を示すグラフである。
【発明を実施するための形態】
【００３１】
以下、この発明の好ましい態様について説明する。
前記分類工程は、n ＜m の場合に（８）および（９）式を用いて固有ベクトルw1 を得るようにしてもよい。このようにすれば、m ×m の（１１）式よりも次元数の少ないn ×n の（９）式の固有値計算を解いて、計算時間をより短縮することができる。
また、前記分類工程は、n ＞m の場合に（１０）および（１１）式を用いて固有ベクトルw1を得るようにしてもよい。このようにすれば、n ×n の（９）式よりも次元数の少ないm ×m の（１１）式の固有値計算を解いて、計算時間をより短縮することができる。
【００３２】
さらに、前記分類工程は、ユーザとアイテムの組み合わせを二以上のクラスターとして抽出するために第１のクラスターに属するユーザおよびアイテムを決定した後、（５）式の行列S に逐次的クラスター抽出のアルゴリズムを適用し、前記アルゴリズムは、第k クラスター（k は１より大きい整数）を抽出するにあたり、k ＝２のときは（５）式の行列S の各対角要素を所定の規則に基づき修正した行列であり、k ＞２のときは、第（k −１）クラスターを抽出する際に用いた行列Sk-1 の各対角要素を所定の規則に基づき修正した行列
【数１７】
2012079225.tif 000018
【００３３】
（ただし、Wu はsii を第i 対角要素に持つn×n 対角行列、i は１以上n 以下の整数、Wi はsn+t,n+t を第t 対角要素に持つm×m 対角行列、t は１以上m 以下の整数）の最大固有値λkおよび固有ベクトルwk を算出するために、前記固有ベクトルwk をユーザについての部分ベクトルwuk とアイテムについての部分ベクトルwik とに分け、前記行列Sk の固有値を求める計算式を、
【数１８】
2012079225.tif 000019
（ただし、InおよびImはそれぞれn 次元、m 次元の単位行列）の２つに分割し、（１４）式よりwuk を用いてwik を表した下記（１６）式を（１３）式に代入してなる下記（１５）式の固有値計算を解いてwuk を求め、求めたwuk を（１６）式に適用してwik を求めることにより固有ベクトルwk を得、
【００３４】
【数１９】
2012079225.tif 000020
あるいは、（１３）式からwik を用いてwuk を表した下記（１８）式を（１４）式に代入してなる下記（１７）式の固有値計算を解いてwik を求め、求めたwik を（１８）式に適用してwuk を求めることにより固有ベクトルwk を得、
【００３５】
【数２０】
2012079225.tif 000021
得られた固有ベクトルwk の各要素が予め定められた閾値と比較して閾値以上か否かに応じて各要素に対応するユーザおよびアイテムが第k クラスターに属するか否かを決定するようにしてもよい。
【００３６】
このようにすれば、各ユーザおよび各アイテムの前記クラスターへの属否を判断する固有ベクトルwk を算出するにあたり、縦横が（n＋m ）×（n＋m ）の正方行列Sk の固有値を求める計算式を直接解く代わりに、縦横がn ×n の行列Z(Im −Wi )-1ZT の計算式である（１５）式の固有値計算を行うので、（n＋m ）×（n＋m ）次元の固有値計算を直接解く場合に比べて計算時間を短縮することができる。即ち、繰り返し計算を伴う固有値計算を（n＋m ）×（n＋m ）次元からn ×n 次元に縮小するので固有値計算に伴う負担を低減することができる。
【００３７】
また、前記（ii）では、縦横がm ×m の行列ZT(In −Wu )-1Z の計算式である（１７）式の固有値計算を行うので、（n＋m ）×（n＋m ）次元の固有値計算を直接解く場合に比べて計算時間を短縮することができる。即ち、繰り返し計算を伴う固有値計算を（n＋m ）×（n＋m ）次元からm ×m 次元に縮小するので固有値計算に伴う負担を低減することができる。
前記（ｉ）または（ii）の方法をコンピュータに実行させるためのプログラムについても同様の効果を奏する。
【００３８】
ここで、前記分類工程は、n ＜m の場合に（１５）および（１６）式を用いて固有ベクトルwk を得るようにしてもよい。
このようにすれば、m ×m の（１７）式よりも少ない次元数のn ×n の（１５）式の固有値計算を解いて、計算時間をより短縮することができる。
【００３９】
また、前記分類工程は、n ＞m の場合に（１７）および（１８）式を用いて固有ベクトルwk を得るようにしてもよい。
このようにすれば、n ×n の（１５）式よりも少ない次元数のm ×m の（１７）式の固有値計算を解いて、計算時間をより短縮することができる。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
【００４０】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
≪前提とする協調フィルタリング処理≫
この発明の理解を容易にするために、まず、前提となる協調フィルタリング処理について簡単に説明しておく。
表１は、n 人のユーザ（u-1，・・・，u-n）とm 個のアイテム（i-1，・・・，i-m）の関係性を表すn×m 関係性行列Z の例である。
【００４１】
【表１】
2012079225.tif 000022
【００４２】
表１の行列の要素で、「１」は正の関係性、即ち、ユーザが対象のアイテムを嗜好および／または受容していることを表す。「０」（ゼロ）は負の関係性、即ち、ユーザが対象のアイテムを嗜好および／または受容していないか、または関係性未知、即ち、対象アイテムに対するユーザの嗜好や受容の度合いが未知であることを表す。前述の正の関係性は肯定的関係性、負の関係性は否定的または未知の関係性ともいえる。
たとえば、購買履歴であれば、「１」は「購入歴あり」（嗜好している）を表し、「０」は「購入歴なし」を表すが、その「購入歴なし」には「その製品が好きでない」（嗜好していない）と「今後購入する可能性がある」（嗜好が未知）の両方が含まれる。
【００４３】
このような関係性行列Z を用いてユーザとアイテムの関係性を表す手法はすでに知られている。関係性行列が与えられたとき、ユーザとアイテムのすべての組についての関係性を表現するために、全体の（n＋m）×（n＋m）関係性行列、S =[sij] を表２のようなブロック行列で表す。
表２は、n人のユーザ（u-1，・・・，u-n）とm個のアイテム（i-1，・・・，i-m）を合わせたn＋m個の項目間の（n＋m）×（n＋m）関係性行列の例である。
関係性が規定されていないユーザ間（およびアイテム間）の関係性については「０」を代入して処理している。
また、前記ブロック行列S を式で表現すると、以下の通りである。
【００４４】
【数２１】
2012079225.tif 000023
ここで、ブロック行列Sは、最初のn 個（または残りのm 個）の項がn 人のユーザ（またはm 種類のアイテム)に対応している。
【００４５】
【表２】
2012079225.tif 000024
行列S が求まると、S = [sij]の最大固有値に対応する固有ベクトルとして、第1クラスターへの所属度合いを表すn＋m 次元ベクトルw1 =[w1i] が求められる。
【００４６】
表３は、n人のユーザ（u-1，・・・，u-n）とm個のアイテム（i-1，・・・，i-m）を合わせたn＋m個の項目についてのn＋m 次元固有ベクトルの例である。表３の固有ベクトルにおいてすべての要素は０（ゼロ）以上であり、値が大きいほど第１クラスターへの所属度合いが大きいことを示している。算出された固有ベクトルに基づいて第１クラスターを抽出するには、例えば、予め定められた閾値以上の要素を有するユーザを第１クラスターに所属するメンバーとすればよい。
なお、関係性行列から最大固有値とそれに対応する固有ベクトルを求める具体的な方法としては、既存の汎用的な方法（たとえば、べき乗法やヤコビ法など）を利用すればよい。
【００４７】
【表３】
2012079225.tif 000025
【００４８】
以上のようにして、第１クラスターが抽出された後に２番目以降のクラスターを抽出する手順は次の通りである。第k 番目のクラスターを抽出する場合は、k-1 番目までのクラスターに所属するユーザが含まれないようにする必要があるので、重なりがなくなるための制約を定めなければならない。ただし、アイテムについては複数のクラスターに共有されてもかまわない。たとえば、アイテムA とB を好むユーザ群のクラスターのほかにアイテムA とC を好むユーザ群のクラスターが存在してもかまわない。したがって、ユーザのみについて重複を排除するための制約として、
【００４９】
【数２２】
2012079225.tif 000026
を用いる。ここで、
【００５０】
【数２３】
2012079225.tif 000027
は、
【００５１】
【数２４】
2012079225.tif 000028
のうちでユーザに関する部分を抜き出したn 次元ベクトルである。表４は、n 人のユーザ（u-1，・・・，u-n）について所属度を並べたn次元固有ベクトルの例である。
【００５２】
【表４】
2012079225.tif 000029
制約を満たすベクトル
【００５３】
【数２５】
2012079225.tif 000030
を求めるために、行列S の対角要素sii を以下におきかえる。
【００５４】
【数２６】
2012079225.tif 000031
ただし、βt は重み係数で、たとえば、以下のように定める。
【００５５】
【数２７】
2012079225.tif 000032
ここで、ηはβt が十分大きくなるように適宜定める係数である。
修正後の行列S の最大固有値に対応する固有ベクトルは、
【００５６】
【数２８】
2012079225.tif 000033
となる。
表５は、第k クラスターの所属度ベクトルを算出する際の関係性行列の例である。ユーザについての対角要素が、上で求めた値に置き換えられている。
【００５７】
【表５】
2012079225.tif 000034
≪改良された計算モデル−第１クラスターの抽出≫
以上で述べた従来の計算モデルの計算量、特に固有値計算に係る処理負荷を軽減し、かつ、新規ユーザが追加された場合に簡便な処理で対応できる、この発明に係る計算モデルについて説明する。
着眼点は、次の通りである。表２のブロック行列の非対角ブロックの要素がすべて０（ゼロ）であることを考慮してその特性を生かせば、第１クラスターのクラスター指標の計算、即ち、（１）式の関係性行列S の固有値問題は以下の二つに分割できる。
【００５８】
【数２９】
2012079225.tif 000035
ここで、λ1 はS の最大固有値である。また、
【００５９】
【数３０】
2012079225.tif 000036
はユーザについてのクラスター指標のベクトルであり、
【００６０】
【数３１】
2012079225.tif 000037
はアイテムについてのクラスター指標ベクトルである。
（２０）式から
【００６１】
【数３２】
2012079225.tif 000038
なる関係が得られるので、（１９）式に代入することで、wu1 の算出が
【００６２】
【数３３】
2012079225.tif 000039
【００６３】
なる固有値問題に帰着される。（２２）式に公知のべき乗法やヤコビ法などを適用して行列ZZT に係る固有値計算を行い、ユーザについてのクラスター指標のベクトルwu1 を算出することができる。wu1 が得られたら、得られたwu1 を（２１）式に適用し、アイテムについてのクラスター指標ベクトルwi1 が求められる。（２２）式の固有値計算は繰り返し計算を伴うが、ここで注目すべき点は、行列ZZT の要素数が（ユーザ数）×（ユーザ数）であり、従来のS の要素数よりも少ないことである。また、（２１）式は、掛け算を１回実行するだけであり繰り返し計算を含まない。よって、表２のS にべき乗法やヤコビ法などを適用して表３の固有ベクトルを算出する従来の手法に比べると、固有値の計算量が低減される。
【００６４】
以上の計算は、（２２）式を用いてユーザについてのクラスター指標のベクトルwu1 を先に計算し、その結果に基づいてアイテムについてのクラスター指標ベクトルwi1 を計算するものである。
これと異なり、アイテムについてのクラスター指標ベクトルwi1 を先に計算し、その結果に基づいてユーザについてのクラスター指標のベクトルwu1 を計算する手順もある。
その場合は、（１９）式から、
【００６５】
【数３４】
2012079225.tif 000040
なる関係が得られるので、（２０）式に代入することで、wi1 の算出が
【００６６】
【数３５】
2012079225.tif 000041
として、ZTZ の固有値問題に帰着できる。
【００６７】
固有値計算に用いる行列ZTZ の要素数は（ユーザ数）×（ユーザ数）であり、従来のS の要素数よりも少ない。よって、表２のS にべき乗法やヤコビ法などを適用して表３の固有ベクトルを算出する従来の手法に比べると、固有値の計算量が低減される。
いずれの計算手順が有利かは、行列ZZTとZTZ の要素数、即ち、ユーザ数とアイテム数の大小関係による。即ち、
（１）（ユーザ数）＜（アイテム数）なら、ユーザの指標を先に計算する方が速くなり、
（２）（ユーザ数）＞（アイテム数）なら、アイテムの指標を先に計算する方が速くなる。
前記（１）または（２）のいずれか適当な方を選択することで、固有値問題の対象となる行列の要素数をS の25% 以下に削減できる。
【００６８】
≪改良された計算モデル−第２クラスター以降の抽出≫
以上の処理手順により、第１クラスターのメンバーを抽出した後、第２クラスター以降の抽出手順について説明する。
一般に第k クラスター（k は、１より大きい整数）の抽出の際には、すでに抽出されたメンバーが重複して抽出されないように考慮しつつクラスター抽出を行わなければならない（共クラスター抽出）。
【００６９】
ただし、この発明においては、表２のように、n 人のユーザとm 個のアイテムを正方形状の(n＋m)×(n＋m) ブロック行列としたユーザ・アイテム関係性行列を用いており、ユーザとアイテムの両方の重複を避けた共クラスター抽出を行うこともできるが、アイテムの重複を許容しユーザの重複のみを避けるようにすることもでき、逆にユーザの重複を許容しアイテムの重複のみを避けるようにすることもできる。
ここでは、クラスター間でのアイテムの重複を許容し、ユーザのみについて重複を排除する態様を説明する。共クラスター抽出のため、従来手法と同様にTsudaらの手法（前記非特許文献４参照）を援用する。
【００７０】
≪クラスター抽出の具体例≫
表１に示す関係性行列Z を例にして、この発明の具体的な処理手順を示す。
まず、第１クラスターのクラスター指標の計算例を示す。改めて、関係性行列Z =[zij] を以下に示す。
【００７１】
【表６】
2012079225.tif 000042
この関係性行列Z に対する転置行列ZT は、次のようになる。
【００７２】
【表７】
2012079225.tif 000043
関係性行列Z の要素数が、n＞m、即ち（ユーザ数）＞（アイテム数）であるとする。その場合、アイテムについてのクラスター指標のベクトルwi1 をまず算出する。固有値計算に用いる行列ZTZ を以下に示す。
【００７３】
【表８】
2012079225.tif 000044
行列ZTZ は、m個のアイテム間の関連性を表す（m×m）関係性データ行列である。要素の値が大きいほど、関係性が強いことを示す。例えば、各アイテムが商品なら、合わせ買いの頻度が高いことを示している。
第１クラスターを抽出する。行列ZTZ の最大固有値に対応する固有ベクトルとして、アイテムのクラスター指標
【００７４】
【数３６】
2012079225.tif 000045
を求める。その結果を表９に示す。
【００７５】
【表９】
2012079225.tif 000046
表９は、m 個のアイテム（i-1，・・・，i-m）について所属度を並べたm 次元の固有ベクトルである。
求められた固有ベクトルwi1 を次の式、
【００７６】
【数３７】
2012079225.tif 000047
に適用し、ユーザのクラスター指標
【００７７】
【数３８】
2012079225.tif 000048
を求める。以上の処理手順で、第１クラスターを抽出することができる。
続いて、第k クラスター（ただし、k は１より大きい整数）の共クラスター抽出について説明する。
【００７８】
第k クラスターを抽出する際の関係性行列は、表５および（３）式または（４）式に示したように、関係性行列S のユーザについての対角要素をsii に置換したものである。ここで、sii を第i対角要素に持つn×n対角行列をWu と置く。表１０に対角行列Wuを示す。
【００７９】
【表１０】
2012079225.tif 000049
【００８０】
表１０で、siiは、ユーザi に対するペナルティ重みである。ユーザi がまだどのクラスターにも所属していなければ、siiは０（ゼロ）に近い値である。ユーザi がすでにどこかに所属していれば、siiは負の小さな値になる。また、Wi をsn+t,n+t を第t 対角要素に持つ対角行列とする。
このとき、修正後の関係性データ行列は
【００８１】
【数３９】
2012079225.tif 000050
となり、固有値問題は以下のように分解される。
【００８２】
【数４０】
2012079225.tif 000051
ただし、In はn×n、Im はm×mの単位行列であり、λk はSk の最大固有値である。
ユーザのクラスター指標ベクトルwuk の算出は、以下の何れかの手順で算出する固有値問題に帰着される。
第１の手順は、次の式を用いて、ユーザのクラスター指標ベクトルwuk を先に計算するものである。固有値計算に用いる行列は（ユーザ数）×（ユーザ数）の要素を持つ。
【００８３】
【数４１】
2012079225.tif 000052
次の表１１に、上式の対角行列（In-Wu）の例を示す。
【００８４】
【表１１】
2012079225.tif 000053
第２の手順は、次の式を用いて、アイテムのクラスター指標ベクトルwik を先に求めるものである。固有値計算に用いる行列は（アイテム数）×（アイテム数）の要素を持つ。
【００８５】
【数４２】
2012079225.tif 000054
次の表１２に、上式の（In-Wu）-1の例を示す。
【００８６】
【表１２】
2012079225.tif 000055
上式で
【００８７】
【数４３】
2012079225.tif 000056
の各要素は、
【００８８】
【数４４】
2012079225.tif 000057
で求められる。
このように、関係性行列S のスパース性を利用することで、従来に比べて計算量の削減が可能となる。
【００８９】
≪新規ユーザへの適応≫
つぎに、新たなユーザが追加された場面を考える。即ち、すでに十分な数のユーザのデータが収集されており、
【数４５】
2012079225.tif 000058
と
【００９０】
【数４６】
2012079225.tif 000059
が求まった後に、新規ユーザ（第n+1 ユーザ）を追加する場合である。
【００９１】
新規ユーザのm 種類のアイテムに関する関連性を要素とするベクトルをzn+1 =(zn+1,1,…,zn+1,m)Tとする。従来の計算モデルではユーザの追加は考慮されていなかったが、この発明に係る協調フィルタリング処理手法によれば、ユーザとアイテムのクラスター指標を分離して算出しているため、信頼性の高いwik が求められているなら、そこから第(n＋1) ユーザのメンバシップ指標が推定可能であると期待できる。
nが十分に大きく、
【００９２】
【数４７】
2012079225.tif 000060
が精度良く求まっているならば、第n+1 ユーザを加えた履歴データに対して上述の計算を行ったとしても、その結果求められる
【００９３】
【数４８】
2012079225.tif 000061
と
【００９４】
【数４９】
2012079225.tif 000062
とはほとんど変化しないと考えられるからである。
そこで、
【００９５】
【数５０】
2012079225.tif 000063
を信頼できる値であるとし、再計算をせずに第n+1 ユーザのクラスター指標のみを簡便に計算する。
（２４）式から、wuk,n+1 とwik の間には以下の関係が得られる。
【００９６】
【数５１】
2012079225.tif 000064
したがって、第(n＋1) ユーザの第kクラスターへの帰属度の推定値は、以下のように求められる。
【００９７】
【数５２】
2012079225.tif 000065
同様に、アイテムの追加も考えられる。第(m＋1) アイテムとn 人のユーザとの関連性ベクトルが
【００９８】
【数５３】
2012079225.tif 000066
と得られたなら、（２５）式から、
【００９９】
【数５４】
2012079225.tif 000067
なる関係が得られるため、第(m＋1) アイテムのクラスターk への帰属度の推定値は、以下のように求められる。
【０１００】
【数５５】
2012079225.tif 000068
運用に際しては、一旦、充分な量のトレーニングデータからwuk とwik が求められたなら、wuk やwik に大きな変化が生じないとみなされる範囲内で、固有値計算を行うことなしにユーザとアイテムの追加が随時可能となる。
≪新規ユーザ追加の具体例≫
新規ユーザ（第n+1 ユーザ）を追加する場合の計算例を以下に示す。
次の表１３は、第n+1 ユーザの各アイテムに対する履歴データの例である。即ち、第n+1 ユーザの追加により、表１の関係性行列Z の第n+1 行目の項目u-（n+1）に追加されるべき各アイテムについての要素である。
【０１０１】
【表１３】
2012079225.tif 000069
表１３に示すベクトルの各要素は、第n+1 ユーザがm個のアイテム（i-1，・・・，i-m）について購入したか否かを示している。
次の表１４は、第k クラスターにおけるアイテムのクラスター指標を示すm 次元の固有ベクトルwik を示している。表１４の各要素は、m 個のアイテム（i-1，・・・，i-m）について、第k クラスターへの所属度を示す固有ベクトルである。
【０１０２】
表１４の固有ベクトルは、新規ユーザを追加する前に、n人のユーザについてのデータから計算された値である。これに対して、たかだか一人のユーザ（第n+1 ユーザ）のデータが付加されただけでは、再計算を行っても変化がほとんどないと考えられる。よって、この固有ベクトルを、そのまま第n+1 ユーザのクラスター指標計算に用いる。
【０１０３】
【表１４】
2012079225.tif 000070
そうすれば、第n+1 ユーザの第k クラスターへの所属度は、（２９）式から類推されるように、
【０１０４】
【数５６】
2012079225.tif 000071
と、
【０１０５】
【数５７】
2012079225.tif 000072
との内積、即ち、m 回の掛け算と足し算を行い、それを、
【０１０６】
【数５８】
2012079225.tif 000073
で割り算するだけで計算できる。このように、新規ユーザが追加されたときの計算は、非常に簡便である。
【０１０７】
≪実験例≫
この発明の有効性を示すために、以下の実験を行った。
実験には、日本経済新聞社のNEEDS-SCAN/PANELより、2000年の購買調査の対象となった996 世帯が18 種類の製品を所有しているか否かのデータ（996×18 データ行列）を用いた。
実験例１：計算時間の比較
この発明では、当該推薦を行う際のクラスター抽出にかかる時間の比較を行った。固有値計算はQR分解とハウスホルダー変換により行った。また、Intel Xeon CPU3.0GHz を搭載したWindows(登録商標) XP コンピュータを用いた。
下の表１５に、この実験に係る関係性行列Zのデータの一例を示す。
【０１０８】
【表１５】
2012079225.tif 000074
この実験において、固有値計算を行う(996+18)×(996+18)関係性行列のデータの一例を次の表１６に示す。
【０１０９】
【表１６】
2012079225.tif 000075
【０１１０】
計算時間の比較結果を表１７に示す。表１７で、計算方法の「full matrix」は前記非特許文献２に示した従来の計算方法を示す。「user matrix」は、この発明おいてn×n 行列の固有値問題から先にwu1（あるいはwuk ）を算出するアプローチを用いた場合であり、「item matrix」は、この発明においてm×m 行列からwi1（あるいはwik ）を先に算出する場合である。ただし、当然のことではあるが、「user matrix」および「item matrix」のいずれのアプローチを用いた場合も同じクラスターが抽出されている。
【０１１１】
【表１７】
2012079225.tif 000076
【０１１２】
次の表１８は、「full matrix」の計算方法において求まる固有ベクトルのデータの一例を示している。即ち、996人のユーザ（u-1，・・・，u-996）と18個のアイテム（i-1，・・・，i-18）を合わせた(996+18)個の項目についての(996+18)次元固有ベクトルである。
【０１１３】
【表１８】
2012079225.tif 000077
「full matrix」の計算方法では、ユーザのクラスター指標（996個世帯に対応する各要素）とアイテムのクラスター指標（18種類の製品に対応する各要素）が一括で計算される。
一方、「user matrix」の計算方法においては、固有値計算を行うのは、関係性行列ZZT である。次の表１９は、関係性行列ZZT のデータの一例を示している。
【０１１４】
【表１９】
2012079225.tif 000078
表１９に示すように、関係性行列ZZT は、996人のユーザ間の関連性を表す(996×996)の要素からなる関係性行列である。
次の表２０は、表１９の関連性行列から求まる固有ベクトルのデータの一例を示している。
【０１１５】
【表２０】
2012079225.tif 000079
表２０に示すように、固有ベクトルは、996人のユーザ（u-1，・・・，u-996）についての996次元のベクトルである。
ユーザのクラスター指標wu1のみが固有値計算で算出される。アイテムのクラスター指標wi1 は、
【０１１６】
【数５９】
2012079225.tif 000080
により、即ち、アイテムごとに、996回の掛け算と足し算、および1回の割り算のみという簡便な計算で算出される。
【０１１７】
また、「item matrix」の計算方法では、先にアイテムのクラスター指標wi1（あるいはwik ）を固有値計算により算出し、その後に、求まっているクラスター指標から簡略計算のみでユーザのクラスター指標wu1（あるいはwuk ）を算出する。「item matrix」の計算方法で固有値計算を行うのは、関係性行列ZTZ である。次の表２１は、関係性行列ZTZ のデータの一例を示している。
【０１１８】
【表２１】
2012079225.tif 000081
表２１に示すように、関係性行列ZTZ は、18種類のアイテム間の関連性を表す(18×18)の要素からなる関係性データ行列である。
次の表２２は、表２１の関係性行列から求まる固有ベクトルのデータの一例を示している。
【０１１９】
【表２２】
2012079225.tif 000082
表２２に示すように、固有ベクトルは、18個のアイテム（i-1，・・・，i-18）についての18次元のベクトルである。
アイテムのクラスター指標wi1 のみが固有値計算で算出される。ユーザのクラスター指標wu1 は、
【０１２０】
【数６０】
2012079225.tif 000083
により、即ち、ユーザごとに、18回の掛け算および足し算と1回の割り算のみという簡便な計算で算出される。
【０１２１】
以上、従来の「full matrix」、この発明による「user matrix」および「item matrix」の３種類の計算方法での計算時間の比較結果を示す表１７から、この発明による計算処理の手順に従えば、従来手法の241秒に比べて計算時間が大幅に削減できたことが分かる。「user matrix」では、従来の約68％ の計算時間であり、「user matrix」の場合は、従来の約2％ の計算時間にとどまっている。この実験例では、アイテム数m =18 がユーザ数n =996よりも大幅に少ないことから、アイテム行列を用いた際の効率化の効果が特に際立っている。本実験のデータでは、アイテム数が少ないことが初めから分かっているため、実用の際には「item matrix」の計算方法を採用すればよいことは事前に分かっている。つまり、「full matrix」あるいは「user matrix」を行う必要がないことは、あらかじめ分かる。しかし、この比較実験で「user matrix」をあえて実行した意義は次の点にある。即ち、「full matrix」の縦横の項目数996+18 =1014 のわずか2% に満たない18項目を減らして固有値計算を行った「user matrix」であっても、計算時間が約32％短縮された。このことから、固有値の計算に係る行列の要素数を減らすというこの発明の思想の有効性が示されたといえる。
【０１２２】
実験例２：新規ユーザへの適応
つぎに、新規ユーザへの適応について、実験を行った。実験の手順は次のようなものである。実験例１と同じ996人のユーザを、アイテムのクラスター指標wi1 （あるいはwik ）の算出に用いるトレーニングデータ（トレーニングユーザ）と、評価用のテストデータに分ける。
そして、クラスター構造（wu1 とwi1 、あるいはwuk とwik ）の推定に用いるトレーニングユーザの数を徐々に減じ、残りを新規ユーザ（テストユーザ）とみなしてメンバシップ指標を簡便な計算のみで推定した。
次の表２３は、トレーニングデータに用いるユーザ数を500とした場合の関係性行列Z のデータの一例を示している。
【０１２３】
【表２３】
2012079225.tif 000084
トレーニングデータ（u-1からu-500）の情報のみから、アイテムのクラスター指標wi1 を固有値計算で算出する。
一方、テストデータとしたユーザ（u-501からu-996）のクラスター指標wu1 は、トレーニングデータのみから算出されたwik を用いて、
【０１２４】
【数６１】
2012079225.tif 000085
という簡便な計算のみで算出する。
テストユーザ（新規のユーザ）について、アイテムのクラスター指標の更新なしに計算した値wu1 と、実験例１ですべてのユーザをトレーニングデータとして計算したクラスター指標wu1 とを比較する実験を行った。
図１は、前述のようにテストユーザ数を変えながら、アイテムのクラスター指標の更新なしに計算した値wu1 とすべてのユーザをトレーニングデータとして計算したクラスター指標wu1 との平均誤差の推移を示すグラフである。
【０１２５】
図１に示すように、500 件以上のユーザをトレーニングユーザとした場合には、テストユーザについても誤差0.001 以下でメンバシップ指標を推定できた。例えば、表２０に示すように、固有ベクトル各要素は、０（ゼロ）以上かつ１以下の値をとる。表２０の固有ベクトルの最小の要素は、0.1である。この固有ベクトルwu1 の各要素の値は、各ユーザが第１クラスターに属するか否かの判定のために予め定められた閾値と比較される。第k クラスターの固有ベクトルwuk についても同様である。前記閾値は０から１の間に設定されるが、通常、0.1 以下の小さな閾値でクラスターへの属否を判定することは考えられない。これに対して、図１に示すように、996 人中500 人を新規ユーザとしたときの誤差は、0.001 以下である。この誤差は、最小の要素の値である0.1 に対して1% 以下にとどまっている。即ち、新規ユーザがトレーニングユーザ数とほぼ同じになる500人より少ないか同程度までは、精度よく推定できていることが分かる。
【０１２６】
以上のことから、充分な量の関係性データからクラスター構造を推定したのちは、簡便な計算のみで新規ユーザに対しても帰属クラスターが精度よく推定できることが示された。
また、トレーニングユーザと同数程度の新規ユーザが追加されたのちは、クラスター構造の再構築が必要といえる。
【０１２７】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【図１】
2012079225.tif 000097