(57)【要約】      （修正有）【課題】ユーザおよびアイテムを適切に分類することにより高い精度で推薦すべきアイテムを決定することのできる協調フィルタリング処理方法および協調フィルタリング処理プログラムを提供する。【解決手段】ｎ人のユーザがｍ個のアイテムの評価を行う評価値行列を格納する工程と、未評価の要素を含む前記評価値行列を縦横が各ユーザと各アイテムからなる（ｎ＋ｍ）×（ｎ＋ｍ）の正方行列Ａに拡張する拡張工程と、得られた正方行列Ａに認知的均衡理論における最小均衡化のアルゴリズムを適用し各ユーザおよび各アイテムを２つに分類する工程と、分類結果に基づいて対象ユーザに推薦すべきアイテムを決定する工程とを備える。【選択図】図３
2010073195.tif 000002
【特許請求の範囲】
【請求項１】
ｎ人のユーザのｍ個のアイテム（ｎ、ｍは自然数）に対する嗜好の度合いおよび／または受容の度合いを表す各スコアを、縦横がｎ×ｍの評価値行列として記憶部に格納する工程と、
前記スコアが未知の要素を含む前記評価値行列を縦横が各ユーザと各アイテムとの和集合からなる（ｎ＋ｍ）×（ｎ＋ｍ）の正方行列、
【数１】
2010073195.tif 000072
（ここで、aijは、２値または３値をとる要素であり、iおよびjはいずれも０以上かつ（ｎ＋ｍ）未満の整数）
に拡張する拡張工程と、
（１）２値の要素からなる前記正方行列Ａに逐次的クラスター抽出のアルゴリズムを適用し、各ユーザおよび各アイテムを３つ以上のグループに分類するか、または、
（２）３値の要素からなる前記正方行列Ａに認知的均衡理論における最小均衡化のアルゴリズムを適用し、各ユーザおよび各アイテムを２つのグループに分類する工程と、
分類結果に基づいて対象ユーザに推薦すべきアイテムを決定する推薦工程とを備え、
前記拡張工程は、前記評価値行列の要素のうち予め定められた閾値未満のスコアが格納された要素および前記スコアが未知の要素をゼロで置換し他の要素を正値で置換して２値化するか、または、要素のうち前記スコアが未知の要素をゼロで置換し前記スコアが前記閾値未満の要素を負値で置換し、前記スコアが前記閾値以上の要素を正値で置換して３値化された要素からなる行列、
【数２】
2010073195.tif 000073
（ここで、ｉは０以上かつｎ未満の整数、ｊは０以上かつｍ未満の整数）
を決定する第１の工程と、
前記行列Ａのうちユーザとアイテムとの関係を示す対角ブロックに前記行列Ｚおよびその転置行列ＺTを配置しユーザどうしの関係を示す対角ブロックおよびアイテムどうしの関係を示す対角ブロックにゼロ行列をそれぞれ配置して前記アルゴリズムを適用し得る正方行列、
【数３】
2010073195.tif 000074
を得る第２の工程とを含み、各工程をコンピュータが実行することを特徴とする協調フィルタリング処理方法。
【請求項２】
前記逐次的クラスター抽出のアルゴリズムは、正方行列Ａに基づき、その各対角要素siiを所定の規則に基づき修正した正方行列Ａkに係る（ｎ＋ｍ）次元の固有値ベクトル、
【数４】
2010073195.tif 000075
を求め、さらにＡkの対角要素siiを前記規則に基づき修正して既に抽出されたクラスターのメンバーがその後に抽出されないようにし、修正後の正方行列の固有値ベクトルを求める処理を逐次Ｋ回繰り返すことにより、Ｋ個の固有ベクトルｗ1〜ｗKを求めるものであり、
前記推薦工程は、ｗ1〜ｗKの固有ベクトルのうち、ｐ番目の固有ベクトルｗpの第ｑ次元目の要素が、所定の第１基準を満たす場合ｑ番目のユーザがｐ番目のクラスターに所属すると判断する工程と、
固有ベクトルｗpの第（ｎ＋ｒ）次元目の要素が所定の第２基準を満たす場合、ｑ番目のユーザにｒ番目のアイテムを推奨すべきであると判断する工程を少なくとも有してなる請求項１に記載の方法。
【請求項３】
前記逐次的クラスター抽出のアルゴリズムは、Ａkの対角要素siiのうち各ユーザに対応するｉ＝１からｎまでを修正し、各アイテムに対応するｉ＝（ｎ＋１）から（ｎ＋ｍ）までをゼロとする請求項２に記載の方法。
【請求項４】
第１の基準は、当該要素の値が他の各固有ベクトルの第ｑ次元目の要素以上であることであり、
第２の基準は、当該要素の値がｗpの第（ｎ＋１）〜第（ｎ＋ｍ）次元の他の要素以上であることである請求項１〜３のいずれか一つに記載の方法。
【請求項５】
第１の基準は、当該要素が予め定められた値より大きいことであり、
第２の基準は、当該要素が予め定められた値より大きいことである請求項１〜３のいずれか一つに記載の方法。
【請求項６】
前記最小均衡化のアルゴリズムは、正方行列Ａに基づく固有値ベクトル、
【数５】
2010073195.tif 000076
（ここで、eiは１以下の実数値であり、iは０以上かつ（ｎ＋ｍ）未満の整数）
を求める工程と、
前記固有値ベクトルeの各要素がゼロ以上かゼロ未満かにより各要素に対応するユーザおよびアイテムを２つのグループに分類する工程を含む請求項１〜５のいずれか一つに記載の方法。
【請求項７】
前記推薦工程は、対象とするユーザと同じグループに属する各アイテムを推薦する請求項１〜６のいずれか一つに記載の方法。
【請求項８】
前記推薦工程は、公知の協調フィルタリング手法により推薦すべきアイテムを仮決定し、仮決定されたアイテムのうちで対象ユーザと同じグループに属するアイテムを推薦すべきアイテムとして最終決定する請求項１〜６のいずれか一つに記載の方法。
【請求項９】
前記拡張工程は、各ユーザが各アイテムを好む度合いを評価したものを嗜好の度合いを表すスコアとする請求項１〜７のいずれか一つに記載の方法。
【請求項１０】
前記拡張工程は、各ユーザが各アイテムを購入した履歴を受容の度合いを表すスコアとする請求項１〜７のいずれか一つに記載の方法。
【請求項１１】
ｎ人のユーザのｍ個のアイテム（ｎ、ｍは自然数）に対する嗜好の度合いおよび／または受容の度合いを表す各スコアを、縦横がｎ×ｍの評価値行列として記憶部に格納する処理と、
前記スコアが未知の要素を含む前記評価値行列を縦横が各ユーザと各アイテムとの和集合からなる（ｎ＋ｍ）×（ｎ＋ｍ）の正方行列、
【数６】
2010073195.tif 000077
（ここで、aijは、２値または３値をとる要素であり、iおよびjはいずれも０以上かつ（ｎ＋ｍ）未満の整数）
に拡張する拡張処理と、
（１）２値の要素からなる前記正方行列Ａに逐次的クラスター抽出のアルゴリズムを適用し、各ユーザおよび各アイテムを３つ以上のグループに分類するか、または、
（２）３値の要素からなる前記正方行列Ａに認知的均衡理論における最小均衡化のアルゴリズムを適用し、各ユーザおよび各アイテムを２つのグループに分類する処理と、
分類結果に基づいて対象ユーザに推薦すべきアイテムを決定する推薦処理とをコンピュータに実行させるための協調フィルタリング処理プログラムであって、
前記拡張処理は、前記評価値行列の要素のうち予め定められた閾値未満のスコアが格納された要素および前記スコアが未知の要素をゼロで置換し前記スコアが前記閾値未満の要素を負値で置換し、前記スコアが前記閾値以上の要素を正値で置換して３値化された要素からなる行列、
【数７】
2010073195.tif 000078
（ここで、ｉは０以上かつｎ未満の整数、ｊは０以上かつｍ未満の整数）
を決定する第１の処理と、
前記行列Ａのうちユーザとアイテムとの関係を示す対角ブロックに前記行列Ｚおよびその転置行列ＺTを配置しユーザどうしおよびアイテムどうしの関係を示す対角ブロックにゼロ行列を配置して前記アルゴリズムを適用し得る正方行列、
【数８】
2010073195.tif 000079
を得る第２の処理とを含むことを特徴とする協調フィルタリング処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、認知的均衡理論、逐次的クラスター抽出手法をユーザおよびアイテムの分類に適用した協調フィルタリング処理方法および協調フィルタリング処理プログラムに関する。
【背景技術】
【０００２】
ネットワークが発達した今日では、多数の情報源からしばしば過剰とも思える数の情報を容易に収集することができる。このような環境下では、収集された情報からユーザにとって必要な情報を獲得するためのフィルタリング手法が重要になる。協調フィルタリングは、ネットワーク上でいわゆる"くちこみ"を実現するためのアプローチであり、情報過多に対する処置法でもある。
【０００３】
協調フィルタリングは、多数のユーザが多種のアイテムを評価した評価値を含む評価値行列が与えられた際に、既知の評価値から未評価のアイテムに対する評価値を予測することで、各ユーザに特化した推薦を行うものである。協調フィルタリングは、データ行列中の欠測値を推定する問題ともとらえられる（例えば、非特許文献１参照）。欠測値の推定は、近傍に基づくアルゴリズム、すなわち、対象ユーザに類似した嗜好をもつユーザ（近傍ユーザ）が好むアイテムを推薦するという原理に基づいている。代表的な手法であるGroupLensアルゴリズム（例えば、非特許文献２参照）では、ピアソン相関係数により近傍ユーザが探索され、それらの評価値の重み付き平均値から未評価値を予測する。
【０００４】
協調フィルタリングにクラスター分析を適用するものが提案されている（例えば、非特許文献３、４参照）。クラスター分析は多数の対象を類似した対象からなる"クラスター"にグループ化（分類）する手法であり、似ている対象はなるべく同一クラスターとなり、相違する対象は異なるクラスターとなるように分類することが目的となる。すなわち、クラスター分析の適用は、評価値行列においてアイテムを評価したユーザを近傍ユーザとそれ以外のユーザに適切に分類することが目的である。あるいは、評価値行列においてユーザに評価されたアイテムを近傍アイテムとそれ以外のアイテムに適切に分類することが目的である。
【０００５】
一方、認知的均衡理論は、社会心理学の分野で確立された理論であって、社会集団の相互作用、個人の認知体系と社会集団との相互作用、あるいは対人関係における相互作用の説明に用いられる。より具体的には、人やモノどうしの関係が「好む」、「好まない」の正負の関係で表現されるとき、均衡化へ向けてその関係を変更するような圧力が働くとする理論である。系の解析にはグラフ理論、すなわち、ノード（項あるいは頂点ともいう）とエッジ（枝あるいは辺ともいう）の集合で構成されるグラフの性質についての理論が用いられる。前述の正負の関係をグラフの各枝に対応させたとき、不均衡な系を均衡化させる過程が均衡化過程のアルゴリズムとして提供される。そのアルゴリズムに従ってノードを２つのクラスターにグループ化することができる。
【０００６】
この発明に関連する認知的均衡理論の文献を挙げると、HeiderのP-O-X 理論（例えば、非特許文献５参照）、P-O-X 理論をより一般的な多項関係のモデルに適用したもの（例えば、非特許文献６〜９参照）、それらのモデルにおいて最小均衡化過程を導く方法（非特許文献１０，１１参照）が知られている。
また、この発明に関連する逐次的クラスター抽出手法の文献として、津田らの手法（例えば、非特許文献１２、１３参照）が挙げられる。前記文献は、画像からの図形描出を具体的な適用例に挙げて逐次的クラスター抽出の手法を述べている。さらにまた、Davisは、グラフの均衡化における３群以上への分割可能性を議論している（例えば、非特許文献１４参照）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】J. L. Herlocker, J. A. Konstan, A. Borchers and J. Riedl: An algorithmic framework for performing collaborative filtering, Proc. of Conference on Research and Development in Information Retrieval (1999)
【非特許文献２】J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker, L. R. Gardon and J. Riedl: Grouplens: applying collaborative filtering to usenet news, Communications of the ACM, 40, 3, 77-87 (1997)
【非特許文献３】K. Honda, N. Sugiura, H. Ichihashi and S. Araki: Collaborative filtering using principal component analysis and fuzzy clustering, Web Intelligence: Research and Development, Lecture Notes in Artificial Intelligence 2198, Springer, 394-402 (2001)
【非特許文献４】K. Honda and H. Ichihashi: Component-wise robust linear fuzzy clustering for collaborative filtering, International Journal of Approximate Reasoning, 37, 2, 127-144 (2004)
【非特許文献５】F. Heider: The Psychology of Interpersonal Relations, John Wiley (1958)
【非特許文献６】F. Harary: A structural analysis of situation in the middle east in 1961, J. Conflict Resolution, 5, 2, 167-178 (1961)
【非特許文献７】D. Cartwright and F. Harary: Structural balance, a generalization of Heider's theory, Psychological Review, 63, 167-293 (1956)
【非特許文献８】T. M. Newcomb: An approach to the study of communicative acts, Psychological Review, 60, 393-404 (1953)
【非特許文献９】A. Notsu, H. Ichihashi and K. Honda: Agent simulation based on perceptual balance, International Journal of Computer Science and Network Security, 6, 12, 50-54 (2006)
【非特許文献１０】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)
【非特許文献１１】O. Katai and S. Iwai: On the characterization of balancing processes of social systems and the derivation of the minimal balancing processes, IEEE Trans. Systems, Man, and Cybernetics, SMC-8, 5, 337-348 (1978)
【非特許文献１２】津田 宏治、 仙田 修司、 美濃 導彦、 池田 克夫: “逐次的ファジィクラスタリングとそのノイズに対するロバスト性、” 電子情報通信学会論文誌、 J80-D-II, 1, pp. 190-197, 1997.
【非特許文献１３】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)
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前述したように、協調フィルタリングは、個人（各ユーザ）に適応した情報検索システムを構築するための重要なテーマである。そして、精度よく評価値を予測し、予測結果に基づいて適切な推薦を行うために種々のアプローチがなされている。そして、それらのアプローチの中にはユーザおよびアイテムのクラスター分析を行って予測の精度を改善するものがある（非特許文献３、４参照）。一方、認知的均衡化理論は、社会心理学の分野で人やモノを分類する手法を提供し成功を収めてきた手法である。クラスター分析が協調フィルタリングにおける予測精度の改善に有効であるなら、認知的均衡化理論をクラスター分析の手法に適用できるのではないかと発明者は考えた。しかし、発明者の知る限り、協調フィルタリングのような工業応用分野への適用事例はこれまで知られていない。また、協調フィルタリングで欠測値の推定に用いられる評価値行列は縦横に並ぶ項目がアイテムとユーザであって互いに異なりかつ評価値行列の各要素はアナログ値的であるのに対し、認知的均衡化過程のアルゴリズムで計算に用いられる関係性行列は縦横に並ぶ項目が同じ正方行列形式が一般的であり、関係性行列の各要素は正の関係を示す値（例えば１）または負の関係を示す値（例えば−１）とデジタル値的である。従って、認知的均衡化理論の解析手法を協調フィルタリングに適用できるようにするためには解析手法を工夫しなければならない。
【０００９】
この発明は、以上のような事情を考慮してなされたものであって、ユーザおよびアイテムを適切に分類することにより高い精度で推薦すべきアイテムを決定することのできる協調フィルタリング処理方法および協調フィルタリング処理プログラムを提供するものである。
【００１０】
発明者は、２値の関係性データ行列と社会科学におけるネットワークグラフとの類似性に着目し、ユーザおよびアイテムの分類に認知的均衡化理論を用いるという着想に基づき鋭意検討を行った。その結果、ユーザ同士の相関係数、あるいは、アイテム同士の相関係数を求めることなく、認知的均衡化理論を協調フィルタリングに適用してユーザおよびアイテムを適切に分類するための具体的手法を見出した。また、前記手法により協調フィルタリングによる評価予測の精度を向上させ得ることを実証した。認知的均衡化理論により構造を均衡化するアプローチは、個体とアイテムの区別のない関係性行列の最大固有値に対応する固有ベクトルを用いて個体やアイテムを２分割することで均衡化を図るものである。
さらに、正方形状の関係性データの固有値問題を解くことで逐次的にクラスターを抽出する手法が提案されている。発明者らは、両者のアイデアを融合することで、長方形状の関係性データから逐次的にユーザとアイテムの共クラスターを抽出することにより、逐次的クラスター抽出手法を協調フィルタリングに適用するための具体的手法を見出した。また、前記手法により協調フィルタリングによる評価予測の精度をさらに向上させ得ることを実証した。
【課題を解決するための手段】
【００１１】
この発明では、協調フィルタリングにおけるユーザやアイテムの分類のための認知的なアプローチを提案する。この発明は認知的均衡理論を分類問題へ応用するものであって、ユーザによる各アイテムの嗜好度合いを二者択一の過程とみなした関連性行列において、ユーザおよびアイテムを認知的均衡理論に基づく手法により２つのグループに分類する。
この発明は、ｎ人のユーザのｍ個のアイテム（ｎ、ｍは自然数）に対する嗜好の度合いおよび／または受容の度合いを表す各スコアを、縦横がｎ×ｍの評価値行列として記憶部に格納する工程と、前記スコアが未知の要素を含む前記評価値行列を縦横が各ユーザと各アイテムとの和集合からなる（ｎ＋ｍ）×（ｎ＋ｍ）の正方行列、
【数１】
2010073195.tif 000003
（ここで、aijは、２値または３値をとる要素であり、iおよびjはいずれも０以上かつ（ｎ＋ｍ）未満の整数）に拡張する拡張工程と、（１）２値の要素からなる前記正方行列Ａに逐次的クラスター抽出のアルゴリズムを適用し、各ユーザおよび各アイテムを３つ以上のグループに分類するか、または、（２）３値の要素からなる前記正方行列Ａに認知的均衡理論における最小均衡化のアルゴリズムを適用し、各ユーザおよび各アイテムを２つのグループに分類する工程と、分類結果に基づいて対象ユーザに推薦すべきアイテムを決定する推薦工程とを備え、前記拡張工程は、前記評価値行列の要素のうち予め定められた閾値未満のスコアが格納された要素および前記スコアが未知の要素をゼロで置換し他の要素を正値で置換して２値化するか、または、要素のうち前記スコアが未知の要素をゼロで置換し前記スコアが前記閾値未満の要素を負値で置換し、前記スコアが前記閾値以上の要素を正値で置換して３値化された要素からなる行列、
【数２】
2010073195.tif 000004
（ここで、ｉは０以上かつｎ未満の整数、ｊは０以上かつｍ未満の整数）
を決定する第１の工程と、前記行列Ａのうちユーザとアイテムとの関係を示す対角ブロックに前記行列Ｚおよびその転置行列ＺTを配置しユーザどうしの関係を示す対角ブロックおよびアイテムどうしの関係を示す対角ブロックにゼロ行列をそれぞれ配置して前記アルゴリズムを適用し得る正方行列、
【数３】
2010073195.tif 000005
を得る第２の工程とを含み、各工程をコンピュータが実行することを特徴とする協調フィルタリング処理方法を提供する。
【００１２】
また異なる観点から、この発明は、ｎ人のユーザのｍ個のアイテム（ｎ、ｍは自然数）に対する嗜好の度合いおよび／または受容の度合いを表す各スコアを、縦横がｎ×ｍの評価値行列として記憶部に格納する処理と、前記スコアが未知の要素を含む前記評価値行列を縦横が各ユーザと各アイテムとの和集合からなる（ｎ＋ｍ）×（ｎ＋ｍ）の正方行列、
【数４】
2010073195.tif 000006
（ここで、aijは、２値または３値をとる要素であり、iおよびjはいずれも０以上かつ（ｎ＋ｍ）未満の整数）に拡張する拡張処理と、（１）２値の要素からなる前記正方行列Ａに逐次的クラスター抽出のアルゴリズムを適用し、各ユーザおよび各アイテムを３つ以上のグループに分類するか、または、（２）３値の要素からなる前記正方行列Ａに認知的均衡理論における最小均衡化のアルゴリズムを適用し、各ユーザおよび各アイテムを２つのグループに分類する処理と、分類結果に基づいて対象ユーザに推薦すべきアイテムを決定する推薦処理とをコンピュータに実行させるための協調フィルタリング処理プログラムであって、前記拡張処理は、前記評価値行列の要素のうち予め定められた閾値未満のスコアが格納された要素および前記スコアが未知の要素をゼロで置換し前記スコアが前記閾値未満の要素を負値で置換し、前記スコアが前記閾値以上の要素を正値で置換して３値化された要素からなる行列、
【数５】
2010073195.tif 000007
（ここで、ｉは０以上かつｎ未満の整数、ｊは０以上かつｍ未満の整数）を決定する第１の処理と、前記行列Ａのうちユーザとアイテムとの関係を示す対角ブロックに前記行列Ｚおよびその転置行列ＺTを配置しユーザどうしおよびアイテムどうしの関係を示す対角ブロックにゼロ行列を配置して前記アルゴリズムを適用し得る正方行列、
【数６】
2010073195.tif 000008
を得る第２の処理とを含むことを特徴とする協調フィルタリング処理プログラムを提供する。
【発明の効果】
【００１３】
この発明の協調フィルタリング処理方法において、前記拡張工程は、前記評価値行列の要素のうち予め定められた閾値未満のスコアが格納された要素および前記スコアが未知の要素をゼロで置換し他の要素を正値で置換して２値化するか、または、要素のうち前記スコアが未知の要素をゼロで置換し前記スコアが前記閾値未満の要素を負値で置換し、前記スコアが前記閾値以上の要素を正値で置換して３値化された要素からなる行列Ｚを決定する第１の工程と、ユーザとアイテムとの関係を示す対角ブロックに前記行列Ｚおよびその転置行列ＺTを配置しユーザどうしの関係を示す対角ブロックおよびアイテムどうしの関係を示す対角ブロックにゼロ行列をそれぞれ配置して行列Ｚを正方行列Ａに拡張する第２の工程とを含むので、評価値行列が拡張されてなる２値の正方行列Ａに逐次的クラスター抽出のアルゴリズムを適用し、または、３値の正方行列Ａを認知的均衡理論で用いられる関連性行列とみなしてそれに最小均衡化のアルゴリズムを適用することができる。前記アルゴリズムの適用により正方行列Ａに係るユーザおよびアイテムを適切に分類することができる。そして、分類結果に基づき、対象ユーザに推薦すべきアイテムを高い精度で決定することができる。最小均衡化のアルゴリズムを適用すれば、ユーザおよびアイテムを２つのグループに分類することができる。また、逐次的クラスター抽出のアルゴリズムを適用すれば、ユーザおよびアイテムを３以上のグループに分類することができる。
【００１４】
この発明において、評価値行列は、ｎ人のユーザがｍ個のアイテムを評価する場合の各スコアの行列である。ここで、協調フィルタリングは、評価値行列の一部に評価済みのスコアが格納され、一部が未評価（欠測値）の状態で適用される。協調フィルタリングは前記評価値行列中の欠測値の推定に用いられるからである。各スコアのとり得る範囲は、事例に応じて適宜決定される。各スコアがどのような範囲をとり得るかにかかわらず、この発明においては各スコアが予め定められた閾値以上か否かに注目し、ゼロもしくは正値に２値化し、または、ゼロ、負値もしくは正値に３値化する。スコアが未知の要素はゼロで置換する。
【００１５】
また、正方行列Ａは、認知的均衡化理論において用いられる関係性行列の形式に適合させるべく前記評価値行列を拡張したものである。行列Ａの各要素aijがとり得る値は予め定められる。嗜好の度合いおよび／または受容の度合いを表すスコアの一例として、次のものが挙げられる。各ユーザが各アイテムを評価した評価値があれば、その評価値をスコアとして適用できる。また、各ユーザの各アイテムについての購入履歴のデータがあれば、その購入履歴データをスコアとして適用できる。
【００１６】
それらのスコアと前記正方行列の要素aijがとる値との対応関係の一例として、次のものが挙げられる。肯定的な関係、即ち、ユーザの評価として「好む」とされた場合やユーザがそのアイテムを購入済の場合に対応して「＋１」、未知または否定的な関係、即ち、ユーザの評価が「好まない」または「その他」とされた場合やそのアイテムについてユーザが未購入（不明を含んでもよい）の場合に対応して「０」（ゼロ）が定められる。以上は、２値化の対応関係の一例である。
【００１７】
３値化の対応関係の一例としては、２値化と同様に肯定的な関係を「＋１」とし、未知の関係、即ち、ユーザの評価が「その他」とされた場合やそのアイテムについてユーザが未購入（不明を含んでもよい）の場合に対応して「０」（ゼロ）が定められ、さらに、否定的な関係、即ち、ユーザの評価が「好まない」とされた場合に対応して「−１」が定められてもよい。
評価値行列を正方行列Ａに拡張する処理は拡張工程で行われる。
逐次的クラスター抽出のアルゴリズムは、ファジィクラスタリングの一手法として知られ、ｎ×ｎ関係性行列が与えられた場合に、関係性の強い個体の群（クラスター）を一つずつ逐次的に取り出す手法である。
最小均衡化アルゴリズムは、関連性行列が与えられたときに系の乖離度合いが最小となる均衡状態に不均衡な辺の関係を変化させる手順を求めるアルゴリズムである（非特許文献１０，１１参照）。前記アルゴリズムを適用すると、系の各ノード（この発明におけるユーザおよびアイテムに対応する）が２つのグループに分類される。同一グループに属するユーザは評価が類似し、各ユーザと同一グループに属するアイテムに高い評価を与えている。
【００１８】
推薦工程は、対象ユーザに推薦すべきアイテムを決定する工程である。決定は、ユーザおよびアイテムの分類結果に基づいて行われる。
逐次的クラスター抽出のアルゴリズムを適用する場合と最小均衡化アルゴリズムを適用する場合の特徴は次の通りである。
最小均衡化アルゴリズムは、逐次的クラスター抽出のアルゴリズムに比べて単純な処理で推薦すべきアイテムを決定することができる。また、評価値行列に欠測値があっても、従来手法より精度よく推薦すべきアイテムを決定することができる。
一方、最小均衡化アルゴリズムは、ユーザ・アイテムクラスターを２分類するに留まるが逐次的クラスター抽出のアルゴリズムは、３以上のユーザ・アイテムクラスターを抽出することができるため、より高い精度で推薦すべきアイテムを決定することが期待できる。
さらに、逐次的クラスター抽出のアルゴリズムでは、前記正方行列の要素aijが２値化される。従って、前記正方行列のもとになるスコアが２値以上であれば適用可能である。即ち、アンケート調査等、ユーザの積極的な協力、関与により３値以上に分類されたスコアを用いる場合に限らず、例えば、商品の購買履歴のような、「購入済」、「未購入」程度の粗い分類のデータであっても、これをスコアとして用い、推薦すべきアイテムを決定することができる。従って、購買履歴のような自動的に収集されるデータも適用対象となり、適用可能な範囲がより広範である。
前述の購買履歴データでは、「購入済」は、ユーザがアイテムを「好む」と同等とみなされるのに対し、「未購入」は「好まない」と「今後購入の可能性あり」の両方を含む。もとのスコアがこのように２値の粗い分類の場合でも、それを前記正方行列の要素aijとして用いることができる。勿論、３値以上に分類されたスコアであっても、閾値以上か否かで２値化することが可能である。
この発明の協調フィルタリング処理プログラムも前述の協調フィルタリング処理方法と同様の作用効果を奏する。
【図面の簡単な説明】
【００１９】
【図１】従来の認知的均衡理論の一つであるHeiderのP-O-X理論における均衡状態と不均衡状態を示す説明図である。（ａ）は均衡状態、（ｂ）は不均衡状態である。
【図２】均衡状態にある系では項の集合が二つのグループに分類されることを示す説明図である。
【図３】この発明に係る協調フィルタリングの処理手順を示すフローチャートである。
【図４】この発明に係る実験例２において、関係性データ行列の作成に用いた人工データを示すグラフである。
【図５】この発明に係る逐次クラスタリング手法により抽出された各クラスターの第１の分類結果を示すグラフである。
【図６】この発明に係る逐次クラスタリング手法により抽出された各クラスターの第２の分類結果を示すグラフである。
【図７】この発明に係る逐次クラスタリング手法の各回における凝集度の遷移を示すグラフである。
【図８】この発明に係る実験例２の購買履歴データに基づく推薦において製品ごとのROC曲線を示すグラフである。
【発明を実施するための最良の形態】
【００２０】
以下、この発明の好ましい態様について説明する。
前記逐次的クラスター抽出のアルゴリズムは、正方行列Ａに基づき、その各対角要素siiを所定の規則に基づき修正した正方行列Ａkに係る（ｎ＋ｍ）次元の固有値ベクトル、
【数７】
2010073195.tif 000009
を求め、さらにＡkの対角要素siiを前記規則に基づき修正して既に抽出されたクラスターのメンバーがその後に抽出されないようにし、修正後の正方行列の固有値ベクトルを求める処理を逐次Ｋ回繰り返すことにより、Ｋ個の固有ベクトルｗ1〜ｗKを求めるものであり、前記推薦工程は、ｗ1〜ｗKの固有ベクトルのうち、ｐ番目の固有ベクトルｗpの第ｑ次元目の要素が、所定の第１基準を満たす場合ｑ番目のユーザがｐ番目のクラスターに所属すると判断する工程と、固有ベクトルｗpの第（ｎ＋ｒ）次元目の要素が所定の第２基準を満たす場合、ｑ番目のユーザにｒ番目のアイテムを推奨すべきであると判断する工程を少なくとも有してなるものであってもよい。このようにすれば、前記正方行列Ｚに逐次的クラスター抽出のアルゴリズムを適用して、Ｋ個の固有ベクトルを求めることにより、ユーザとアイテムをＫ個のグループ（クラスター）に分類することができる。そして、求められたＫ個の固有ベクトルの要素が所定の第１基準を満たすか否かを調べることにより、あるユーザがあるクラスターに所属するか否かを決定することができる。さらに、各ユーザが所属するクラスターの固有ベクトルの要素が第２基準を満たすか否かを調べることにより、あるユーザにあるアイテムを推薦すべきか否かを決定することができる。
【００２１】
さらに、前記逐次的クラスター抽出のアルゴリズムは、Ａkの対角要素siiのうち各ユーザに対応するｉ＝１からｎまでを修正し、各アイテムに対応するｉ＝（ｎ＋１）から（ｎ＋ｍ）までをゼロとしてもよい。このようにすれば、各アイテムに対応する対角要素をゼロにするので、既に抽出されたクラスターのユーザはそのクラスターに抽出されず、アイテムはその後のクラスターに抽出され得るようにすることができる。この発明に係る協調フィルタリングでは、抽出されたユーザ・アイテムのクラスターにおいて、ユーザが排他的であれば必ずしもアイテムは排他的である必要はなく、いくつかのクラスターで共有されてもかまわない。むしろ、その方が妥当であるといえる。例えば、アイテムＡとＢを好むユーザ群のクラスターのほかにアイテムＡとＣを好むユーザ群のクラスターが存在してもかまわないからである。
【００２２】
さらに、第１の基準は、当該要素の値が他の各固有ベクトルの第ｑ次元目の要素以上であることであって、第２の基準は、当該要素の値がｗpの第（ｎ＋１）〜第（ｎ＋ｍ）次元の他の要素以上であることであってもよい。このようにすれば、あるユーザに深く関連するクラスターを決定することができ、また、あるユーザに優先的に推薦すべきアイテムを決定することができる。
【００２３】
あるいは、第１の基準は、当該要素が予め定められた値より大きいことであって、第２の基準は、当該要素が予め定められた値より大きいことであってもよい。このようにすれば、あるユーザとあるクラスターとが所定の基準よりも深く関連するか否かを決定することができ、また、あるユーザにあるアイテムを推薦すべきか否かを所定の基準に基づいて決定することができる。
【００２４】
前記最小均衡化のアルゴリズムは、正方行列Ａに基づく固有値ベクトル
【数８】
2010073195.tif 000010
（ここで、eiは１以下の実数値であり、iは０以上かつ（ｎ＋ｍ）未満の整数）
を求める工程と、前記固有値ベクトルeの各要素がゼロ以上かゼロ未満かにより各要素に対応するユーザおよびアイテムを２つのグループに分類する工程を含んでいてもよい。このようにすれば、最小均衡化アルゴリズムに従ってユーザおよびアイテムを２つのグループに適切に分類することができる。
【００２５】
また、前記推薦工程は、対象とするユーザと同じグループに属する各アイテムを推薦するようにしてもよい。このようにすれば、対象ユーザと同じグループに属する各ユーザから高い評価を得たアイテムが確実に推薦される。
【００２６】
あるいは、前記推薦工程は、公知の協調フィルタリング手法により推薦すべきアイテムを仮決定し、仮決定されたアイテムのうちで対象ユーザと同じグループに属するアイテムを推薦すべきアイテムとして最終決定するようにしてもよい。このようにすれば、従来の協調フィルタリング手法により仮決定されたアイテムを、対象ユーザと同じグループに属する各ユーザから高い評価を得たアイテムに絞り込んで推薦がなされるので、推薦されたアイテム中の外れをより少なくできる。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
【００２７】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
この発明に係る実施形態を説明するまえに、基礎となる認知的均衡と最小均衡化過程について簡単に説明しておく。
【００２８】
≪認知的均衡と最小均衡化過程≫
1. P-O-X 理論
HeiderのP-O-X 理論（例えば、非特許文献５参照）は認知的均衡について議論したものであり、人間と状況の関係を8つの形式に分類し、それぞれの関係を正（＋）または負（−）の2値で表して考察している。例えば、図１の右側ように、人 P が人 O と他の対象 X からなる系の中で、
・P は O を好む
・O は X を好む
・P は X を好まない
という関係がある場合を考える。ここで、図中、正および負の関係は、それぞれ実線および破線で示されている。Heiderは均衡がとれた状況では人 P はストレスを感じない一方、均衡がとれていない状況ではストレスを感じて不快であると考え、P-O-X による系での均衡を3辺の符号の積で表して、積が正（＋）であるときを均衡状態とみなした。すなわち、図１の右側のような（＋）×（＋）×（−）＝（−）となるときに均衡がとれていないとし、図１の左側のように均衡がとれた状況へ移行すべきであるとした。ただし、均衡状態は唯一ではなく、幾つもの状況が考えられる（非特許文献５参照）。
【００２９】
2. 多項関係への一般化と最小均衡化過程
次に、P-O-X 理論を多項関係へ一般化する。ただし、以下では人とものを区別しないモデル（例えば、非特許文献６〜９参照）を用いる。
ある多項グラフGの関係性行列A(G)＝[ aij ] の要素を以下のように定義する。
【００３０】
【数９】
2010073195.tif 000011
【００３１】
Cartwright と Harary の均衡概念では、均衡状態にある系では項（頂点）の集合は二つの部分集合に分割されるか一つにまとめられる、とされる。そして、同じ部分集合内の項同士の関係は正となり、異なる集合の項同士は負の関係をもつ。その一例を図２に示す。図２では、第1の部分集合に属する各項1, 2, 5に＋１、第2の部分集合に属する各項3, 4に−１が割り当てられている。
ｎ個の項からなるグラフGにおいて、一方の部分集合に属する項に＋１、他方の項に−１を割り当てるなら、均衡状態にある系を表す符号ベクトル s = (s1, s2, …, sn )T の要素は、
【００３２】
【数１０】
2010073195.tif 000012
【００３３】
のようになる。ただし、Tはベクトルの転置を表す。例えば、図２では、符号ベクトルは s = (1, 1, -1, -1, 1)T となる。
次に、あるグラフGの関係性行列A(G)＝[ aij ] と均衡状態のグラフG'との間の乖離度合いを考える。 G' におけるグループが符号ベクトル s = (s1, s2, …, sn )T により表されるとすると、乖離度合いは以下のようになる。
【００３４】
【数１１】
2010073195.tif 000013
【００３５】
乖離度合い l（エル）が最小となる均衡状態 G'' に至る過程を最小均衡化過程と呼び、その際の符号ベクトル s* は以下の関係を満たす。
【００３６】
【数１２】
2010073195.tif 000014
【００３７】
均衡化はグラフ内の不均衡な辺の関係を変化させることで行われる。ただし、最小均衡化過程は必ずしも唯一のものではない。
Katai と Iwai （非特許文献１０，１１参照）は最小均衡化過程を導く方法について議論している。最小均衡化を行う際には、
【００３８】
【数１３】
2010073195.tif 000015
および
【００３９】
【数１４】
2010073195.tif 000016
という関係がある。ただし、e* は A(G) の最大固有値 λ* に対応する固有ベクトルであり、
【００４０】
【数１５】
2010073195.tif 000017
はユークリッドノルムである。従って、近似的に最適な符号ベクトル s* は、以下のように求められる。
【００４１】
【数１６】
2010073195.tif 000018
【００４２】
≪協調フィルタリングにおける認知的なユーザ分類≫
次に、協調フィルタリングにおけるユーザの分類に前述の認知的均衡および最小化均衡過程を適用する、この発明の特徴的なアプローチについて説明する。
【００４３】
1. 協調フィルタリングにおける問題空間
ｎ人のユーザがｍ種類のアイテムを評価した（ｎ×ｍ）評価値行列 X＝[ xij ] が与えられたとする。ただし、xij はユーザ i のアイテム j に対する評価値である。
【００４４】
近傍に基づくアルゴリズムの代表例であるGroupLens（非特許文献２参照）では、ユーザ i がアイテム j を好む度合いの予測値として、他のユーザが与えた評価値の重み付き平均値を用いている。
【００４５】
【数１７】
2010073195.tif 000019
ただし、
【００４６】
【数１８】
2010073195.tif 000020
はユーザ i の評価値の平均値である。重み riu はユーザ i と u の類似度を表しており、GroupLensではピアソン相関係数が用いられている。
【００４７】
また、評価値行列の値を予測に直接的に用いるのではなく、事前に簡潔な予測モデルを作成するアプローチもある。Hondaら（非特許文献３、４参照）はユーザをいくつかのグループに分割しながらグループごとに予測モデルを推定するアプローチとして線形ファジィクラスタリングに基づく予測法を提案している。線形ファジィクラスタリングは対象を多次元空間内で直線や平面に類した形状のグループ（クラスター）に分割する手法であり、クラスターを代表するプロトタイプが局所的な主部分空間と同一視されるため、局所的な主成分分析ともとらえられる。
【００４８】
2. ユーザ分類に対する認知的アプローチ
2-1. 認知的均衡理論を協調フィルタリングへ適用する際の問題点
前述のように、認知的均衡理論においては、人やものなど、対象の関係性が正負の値をとるデータとして定義される。このように各対象（項目）間の関係性を示すデータは関係データと呼ばれる。関係データは前述した関係性行列の要素としてとらえることができる。関係データに基づいて項目（対象）を分類する手法は種々提案されているが、いずれの手法においても原則的にすべての項目間の関係性が正方行列の形式で与えられていることを前提にしている。
【００４９】
表１は、ｎ個の項目（対象）間の関係性を示すｎ×ｎ関係データ行列の例である。一般に、関係データに基づく分類手法では、すべての項目間の関係が求められていることを前提にしている。すなわち、表の縦と横の要素は同じものが並んでおり、欠測はないものとされている。ただし、拡張された理論では、関係が未知の組についてその関係性行列の要素に 0 を代入することで“正でも負でもない未知要素”としての処理を可能としている。
【００５０】
【表１】
2010073195.tif 000021
【００５１】
一方、協調フィルタリングにおいては、“ユーザ”と“アイテム”のような異なる対象間の関係性を示すデータのみが与えられる。即ち、協調フィルタリングで与えられる評価値行列は、異なる項目（対象）間の関係性のみが与えられた長方形状の関係データ行列となる。
表２は、ｎ人のユーザ（u-1，…，u-n）がｍ個のアイテム（i-1，…，i-m）を評価した ｎ×ｍ 評価値行列の例である。
【００５２】
【表２】
2010073195.tif 000022
【００５３】
表１の関係性行列と異なり、表２の評価値行列は、異種の対象間の関係しか求められていない。すなわち、表の縦と横の要素は異なっている。さらに、欠測があることが前提となっており、表中の空欄は欠測（未評価）を表す。
認知的均衡理論を協調フィルタリングに適用するには、なんらかの方法で、縦と横の要素が異なる長方形状の評価値行列を縦と横の要素が同じ正方行列の形式の関係データ（関係性行列）に変換する必要がある。評価値行列から正方行列形式の関係性行列が得られたら、得られた関連性行列に認知的均衡理論で提案されている分類手法を適用して各項目を分類できる。
【００５４】
ところで、クラスター分析の分野においても、縦と横の要素が異なる長方形状の関係データが与えられた場合に、それを正方行列形式の関係性行列に変換する研究がなされている（例えば、James C. Bezdek, Richard J. Hathaway and Jacalyn M. Huband: Visual Assessment of Clustering Tendency for Rectangular Dissimilarity Matrices, IEEE Transactions on Fuzzy Systems, 15, 5, 890-903 (2007)を参照）。それによれば、長方形状の関係データが与えられた場合には、表の縦の項目（ｎ個）と横の項目（ｍ個）を合わせたｎ＋ｍ個の項目間の（ｎ＋ｍ）×（ｎ＋ｍ）の正方形状の関係データへの拡張が行われる。表３は、従来の手法によりｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせた評価値行列をｎ＋ｍ個の項目間の（ｎ＋ｍ）×（ｎ＋ｍ）の正方形状の関係性行列に拡張した参考例である。表３中、“*”で示された要素は欠測である。従来の分類手法を適用するには、まず、拡張された関連性行列中の欠測要素を補完しなければならない。その際、観測されている要素から求められる相関係数などを用いた補完法が用いられている。しかし、補完における誤差が分類結果に大きく影響するため、分析者がどのように補完するかを適切に定めなければならないという欠点がある。
【００５５】
【表３】
2010073195.tif 000023
【００５６】
2-2. 適用の方針
ここで、認知的均衡の概念に基づいて協調フィルタリングにおける近傍ユーザおよび近傍アイテムを探索することを考える。推薦器としての協調フィルタリングを考えた際には、ユーザのアイテムに対する評価値の予測は二者択一の過程ととらえられる。すなわち、予測値が事前に設定した閾値以上であるアイテムを推薦する推薦器であるなら、閾値よりも大きいか小さいかのみが問題となるので、評価値行列 X＝［ xij ］ の要素を関係性行列における“正の関係”と“負の関係”の二者に置き換えることができる。そして、互いに“正の関係”をもつユーザとアイテムのグループに分類することで、近傍ユーザおよび近傍アイテムを見つけられる。
まず、評価値行列 X = ［ xij ］ の要素（通常、5点満点の5段階評価や、7点満点の7段階評価などで得られる評価値）を二者択一の部分的な関係性行列（ｎ×ｍ行列）Z＝［ zij ］ に変換する。
【００５７】
【数１９】
2010073195.tif 000024
ここで、εが事前に定めた閾値である。ユーザとアイテムのすべての組についての関係性を表現するために、全体の関係性行列 A＝［ aij ］ を以下のブロック行列で表す。
【００５８】
【数２０】
2010073195.tif 000025
【００５９】
ここで、最初のｎ個（または残りのｍ個）の項がｎ人のユーザ（またはｍ種類のアイテム)に対応しているが、Cartwright と Harary のモデルと同様にユーザとアイテムは区別されない。従って、近傍ユーザと近傍アイテムとが同時に見つけられる。以下、この手法で見出された近傍ユーザおよび近傍アイテムの集合をユーザ／アイテム近傍と呼ぶ。
【００６０】
ところで、このモデルではユーザ同士（またはアイテム同士）の関係は未知である。その部分の要素にどのような値を用いて関係性行列への拡張を行うべきかが問題となる。従来の発想に従えば、何らかの手法を用いて各要素として妥当な値を推定することになろう。しかし、前述のように、拡張された認知的均衡理論では関係が未知の組について 0 を代入することで“正でも負でもない未知要素”としての処理を可能としている。そこでこの発明では、各要素を推定する発想をやめて最もシンプルな手法をとる。即ち、評価値行列 Z＝［ zij ］ の中の未評価要素を 0 とおくのと同様に、ユーザ同士およびアイテム同士の関係に相当する A の対角ブロックに ０（ゼロ行列）を与えて関係性行列を得る。
【００６１】
以上のように、この発明では、
（１）協調フィルタリングにおける評価の予測値が、事前に設定した閾値以上か否かという観点でとらえることにより、評価値行列の各要素を「正の関係」、「負の関係」および「未評価」のいずれかを示す値に置き換え、
（２）評価値行列の縦の項目（ユーザ、ｎ人）と横の項目（アイテム、ｍ個）を合わせた（ｎ＋ｍ）×（ｎ＋ｍ）の正方形状の関係データへ拡張し、
（３）ユーザ同士およびアイテム同士の関係に相当する対角ブロックに ０（ゼロ行列）を与える
ことによって、認知的均衡理論を協調フィルタリングにおけるユーザ／アイテム近傍の探索方法に適用可能とする。
【００６２】
表４は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目間の（ｎ＋ｍ）×（ｎ＋ｍ）関係性行列の例である。
評価値行列中の未評価要素に対応する欠測値に関係性不明を表すゼロを代入しているほか、関係性が規定されていないユーザ間およびアイテム間の関係性についてもゼロを代入して処理している。
【００６３】
【表４】
2010073195.tif 000026
【００６４】
2-3.最小均衡化のアルゴリズムによるユーザおよびアイテムの分類
前述の手順で評価値行列を拡張して関係性行列を得たら、得られた関係性行列に基づいてユーザとアイテムを分類する。分類の手法としては、認知的均衡理論の分野で知られた手法が適用可能である。具体的には、前記非特許文献１０，１１による最小均衡化過程の導出手法を適用する。その手法によれば、与えられた関係性行列から、その関係性行列の最大固有値に対応する固有ベクトル e＝［ ei ］を算出する。そして、その要素の正負から２つのグループへのグループ分けを表す符号ベクトル s＝［ si ］を得る。
【００６５】
【数２１】
2010073195.tif 000027
【００６６】
表５は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目についてのｎ＋ｍ次元の固有ベクトルの例である。固有ベクトルの各要素は、各ユーザおよび各アイテムについて関係性行列に基づいて算出されたスコアと解される。
【００６７】
関係性行列から最大固有値とそれに対応する固有ベクトルを求める方法は、既存の汎用的な方法（たとえば、べき乗法やヤコビ法など）を利用すればよい。
【００６８】
【表５】
2010073195.tif 000028
【００６９】
また、表６は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目についてのｎ＋ｍ次元符号ベクトルの例である。表６の符号ベクトルは、表５の固有ベクトルに対応する。
siが互いに1（または互いに―1）同士のユーザおよびアイテムを、正の関係性にあるユーザおよびアイテムの対、即ちユーザ／アイテム近傍であるとみなす。
【００７０】
【表６】
2010073195.tif 000029
【００７１】
以上のようにしてユーザ／アイテムの対が決定される。その結果を認知的均衡理論にあてはめて説明すると、グラフの項（ユーザおよびアイテム）は二つのグループに分割される。同じグループ内の項の間には正の関係がある一方、異なるグループに属する項の間には負の関係があるようになる。即ち、ユーザとアイテムが区別なく、かつ、同時に分割される。
【００７２】
2-4.分類結果の協調フィルタリングへの適用
次に、前述の手法でユーザ／アイテムが分類された場合に、その分類結果を協調フィルタリングに適用する具体的な態様について説明する。
【００７３】
2-4-1. 推薦アイテムの再現率を向上させる態様
この態様は、すべての未評価近傍アイテムをユーザに推薦するシンプルな態様である。求められた符号ベクトルから、ユーザと同じ符号をもつアイテムは近傍アイテムとみなされる。そこで、
（１）符号ベクトルの要素 si が1のユーザ i に、sj が1のアイテム j をすべて推薦し、
（２）符号ベクトルの要素 si が-1のユーザiに、sj が-1のアイテムjをすべて推薦する
ものである。
【００７４】
この態様は、次の特徴を有する。
（１）ユーザ／アイテム分類後に同グループ所属のアイテムをすべて推薦するために、総推薦数が未評価アイテムのおよそ半分となり、推薦されるアイテム数が多くなる。すなわち、高い評価を得たアイテムを精度よく推薦するのに適している。多くのアイテムを推薦してほしいと希望するユーザに対して有効なアプローチである。
（２）未評価値を予測した後にその大きさに基づいて推薦アイテムを選定するのではなく、直接的にユーザと関連の強いアイテムを選別している。
（３）5点満点などの未評価値の予測精度にとらわれず、閾値以上か否かの二者択一の問題を直接的に扱っており、評価値の非線形性（評価値1点と2点の間の差と4点と5点の間の差が等しくない、などの偏り）を考慮する必要がない。
【００７５】
2-4-2. 推薦アイテムの適合率を向上させる態様
この態様は、従来の協調フィルタリング法（たとえば、GroupLensなど）で評価値を予測したうえで、推薦するアイテムを対象のユーザと同じグループのアイテムに絞り込む（推薦するアイテムをより厳選する）ものである。
より具体的な実装方法として、GroupLensと併用する場合を例に挙げて説明する。
GroupLensで予測値 yij が閾値ε以上である場合に、アイテム j をユーザ i に推薦するものとする。このとき、ユーザ i のアイテム j に対する予測値 yij が閾値ε以上で、かつ、符号ベクトルの要素 si＝sj のとき、アイテム j をユーザ i に推薦するものである。
【００７６】
この態様は、高いスコアを得たアイテムのみを推薦したい場合に適している。従来の協調フィルタリング手法（GropuLensなど）によるアイテムの絞り込みとこの発明によるアイテムの絞り込みという2種類の選別方法を併用することで、より確信度の高い少数のアイテムを推薦することができる。すなわち、なるべく外れのない厳選された推薦のみを求めるユーザに対して有効なアプローチである。
【００７７】
2-5. 実験例１
この実施形態に係る手法の有効性を検証するために、以下の実験を行った。
2-5-1.実験手法
まず、インターネット上で運営されている映画お勧めサイトのMovieLens（http://www.movielens.org/）から検証用に公開されている評価値データを用いて、検証を行った。このデータは943人のユーザが1682種類の映画の中から見たことのあるものについて5段階評価した100,000件の履歴からなっている。ここでは、「各ユーザは少なくとも20種類以上の映画を評価している（874ユーザ：n=874）」および「各映画は少なくとも50人以上のユーザにより評価されている（598映画：m=598）」という条件を満たすように選定した82,275件を用いて実験を行った。
【００７８】
実験では、評価値を16,455件ずつの5つの集合に5等分し、交差確認法（CV法）により有効性の検証を行った。即ち、1つの集合（テストデータ）を残り4つ（トレーニングデータ）から予測する。このタスクを集合の入替で5回実施し、精度の平均値を求めた。
評価値が4以上となる映画がユーザに推薦されるべきアイテムであると仮定して、推薦精度の検証を行った。評価尺度としては、適合率と再現率の2種類を用いた。適合率および再現率は、いずれも最低値は０、最高値は１でありその範囲内の値をとる。
１。適合率＝（推薦された映画のうち、評価値が4以上の数）／（推薦された映画の数）
２。再現率＝（評価値が4以上の映画のうち、推薦された数）／（評価値が4以上の映画の数）
適合率が高い（１に近い）ほど「ごみが少ない確実な推薦」ができていることを示す。また、再現率が高い（１に近い）ほど「高評価アイテムを見落とさない推薦」ができていることを示す。
【００７９】
なお、交差確認法における5回の嗜好のそれぞれは、以下の手順に従って実行した。
(ステップ1)  (16,455×4)個の評価値（トレーニングデータ）から、（874×598）評価値行列X＝［ xij ］を作成する。
(ステップ2)  (874×598)の部分的な関係性行列 Z＝［ zij ］を作成する。
(ステップ3)  (874＋598)×(874＋598)の関係性行列 A＝［ aij ］を作成する。
(ステップ4)  (874＋598)次元の固有ベクトル e＝［ ei ］ を求める。
(ステップ5)  (874＋598)次元の符号ベクトル s＝［ si ］ を求める。
(ステップ6)  16,455個の評価値（テストデータ）のそれぞれについて、項目2-4-1「推薦アイテムの再現率を向上させる態様」または項目2-4-2「推薦アイテムの適合率を向上させる態様」に沿って、推薦システムから推薦されるか否かを判別する。
(ステップ7)  “推薦の有無”が“評価値が閾値以上か否か”に合致している度合いを、適合率と再現率の二つの評価尺度で評価する。
評価結果をそれぞれ以下に示す。
【００８０】
なお、比較対象としては、(a) GroupLensにおいてユーザ間の相関係数を考慮したモデル、(b) GroupLensにおいてアイテム間の相関係数を考慮したモデル、の2種類を用いた。また、項目2-4-2「推薦アイテムの適合率を向上させる態様」ではそれぞれのGroupLensモデルにおける推薦アイテムの絞り込み効果を検証した。
【００８１】
2-5-2. 実験結果
【表７】
2010073195.tif 000030
【００８２】
表７に示すように、「推薦アイテムの再現率を向上させる態様」は、多くのアイテムを推薦してほしいと希望するユーザに対して有効なアプローチであることが確認できた。
【００８３】
【表８】
2010073195.tif 000031
【００８４】
表８に示すように、「推薦アイテムの適合率を向上させる態様」は、なるべく外れのない厳選された推薦のみを求めるユーザに対して有効なアプローチであることが確認できた。
以上のように、この発明では、協調フィルタリングにおけるユーザ分類に対する認知的なアプローチを提案した。この発明においては、ユーザとアイテムは区別なく同時に二つの認知的に均衡がとれたグループへ分割される。分割結果を協調フィルタリングに適用する手法として２つの態様を示した。いずれもシンプルな態様であるが、従来手法に比べて適合率または再現率が向上し、この発明の有効性が実証された。
【００８５】
≪認知的均衡を適用した処理手順のまとめ≫
この発明による協調フィルタリングの処理手順を整理して説明する。図３は、この発明に係る協調フィルタリングの処理手順を示すフローチャートであって、「推薦アイテムの再現率を向上させる態様」に係る手順を示している。以下、図３に沿って処理の手順を示している。図３に示す処理は、具体的にはコンピュータが実行する処理として実現される。
【００８６】
まず、コンピュータにより制御される記憶部の記憶領域内に、ｎ人のユーザによってｍ個のアイテムが評価されたｎ×ｍの評価値行列Xを作成する（ステップS1）。評価値行列Xが作成されたら、(9)式に示すように、評価値行列Xに基づいて、各要素が予め定められた閾値εより大きいか否かに応じ１、−１、未評価の場合はゼロの要素を有する部分的な関連性行列Z = ［zij］を作成する（ステップS2）。続いて、部分的な関連性行列Zを（10）式の要領で拡張し、関係性行列Aを作成する（ステップS3）。そして、公知の手法を用いて関連性行列Aの固有ベクトル e （表５参照）を求める（ステップS4）。さらに、固有ベクトル e に基づいて符号ベクトル s （表６参照）を作成する（ステップS5）。
【００８７】
符号ベクトルの値が「１」か「−１」かに応じて、各ユーザsiおよび各アイテムsjを２つのグループに分類する。そして、いま、推薦を行う対象のユーザsiが「１」のグループか「−１」のグループ化を判断する（ステップS11）。対象のユーザが「１」のグループに属する場合（ステップS11のYes）は、対象ユーザと同じ「１」のグループに属する sj＝1 の各アイテムを対象のユーザに推薦する（ステップS12）。一方、対象のユーザが「−１」のグループに属する場合（ステップS11のNo）は、対象ユーザと同じグループに属する sj＝−1 各アイテムを対象のユーザに推薦する（ステップS13）。
【００８８】
なお、図３では、推薦の手法として「推薦アイテムの再現率を向上させる態様」を採用した場合を例示した。これに対して、推薦の手法が「推薦アイテムの適合率を向上させる態様」の場合は、図３のステップS11以降の処理を「推薦アイテムの適合率を向上させる態様」に応じた処理に置換すればよい。この置換は当業者にとって容易である。
【００８９】
≪変形例≫
例えば、分割結果を協調フィルタリングに適用する手法は、この実施形態で示した手法に限られない。例えば、GroupLensで未評価値を推定する前述の算出式（8）には、ユーザ間の相関係数 riu あるいはこれに対応するアイテム間の相関係数が用いられる。この発明による分類結果を考慮して同一のグループに属するユーザ／アイテムと異なるグループに属するユーザ／アイテムに対しそれぞれ異なる相関係数を算出することにより、より高精度な評価値の推定を実現することも可能である。
【００９０】
≪３群以上へのクラスタリング≫
1. ３群以上のクラスター抽出の意義
以上の実施形態では、最小均衡化のアルゴリズムを適用し、各ユーザおよび各アイテムを２つのグループにクラスタリングする手法を述べた。各ユーザおよび各アイテムを３つ以上のグループにクラスタリングする手法について述べる。３グループ以上へのクラスタリングを行うことは、以下のような点で技術的意義がある。
【００９１】
（１）ユーザとアイテムを２群にクラスタリングした場合、「同じグループのアイテムをすべてユーザに推薦する」という態様では、過多に推薦されてしまい、好ましくない場合がある。このような場合に、GroupLensなど従来の推薦手法と前述の最小均衡化のアルゴリズムとを組み合わせて推薦アイテムを厳選することで精度を上げる（ゴミを減らす）ことも考えられる。しかし、3群以上へのより細かな分割ができれば、従来法との組み合わせにより手順を複雑にすることなく精度を向上させ得る。
【００９２】
（２）最小均衡化のアルゴリズムを適用する場合、評価値（好きか嫌いか）が明示的に与えられる場合にしか利用できない。すなわち、ユーザに対して評価を答えてもらう必要があり、多数のユーザの能動的な協力なしには利用できない。そのため、例えば、「買ったか買っていないか」という購買履歴のように、システム管理者が自動的に取得できるデータに対しては適応が不可能である。購買履歴の場合、正の関係性に対応する「買った」に対して、「買っていない」は「好まない」と「未購入（購入可能性あり）」の両方を含むためである。
この実施形態は、これらの点に対応できる手法として、３群以上へのクラスター抽出を示す。
【００９３】
2. 逐次的クラスター抽出手法
まず、この手法の基礎となる津田らの手法（前述の非特許文献１２、１３参照）について説明しておく。津田らの手法は、協調フィルタリングについてではなく、一般的なファジィクラスタリングについて論じたものであるが、ｎ個の個体の間の類似性からなるｎ×ｎ関係性行列が与えられた場合に、関係性の強い個体の群（クラスター）を一つずつ逐次的に取り出す手法として適用できる。
【００９４】
前記非特許文献１２、１３で、津田らは、標本間の類似度を要素に持つ関係性データからファジィクラスターを逐次的に抽出する手法を提案している。標本ｉとｊの非負の類似度をｅijとおき、ｅij＝ｅji，ｅij≧０であるとすると、クラスター内の標本間の類似度の和は以下のように書ける。
【００９５】
【数２２】
2010073195.tif 000032
ただし、ｗ1＝（ｗ11，…，ｗ1n）Tはｎ次元のメンバシップベクトルであり、以下の制約に従うものとする。
【００９６】
【数２３】
2010073195.tif 000033
このとき、Ｌsfceを最小とする最適なベクトルｗ1は、以下の要素を持つ行列、即ち、データ間のつながりの深さを表す類似度行列、Ｓ＝［ｓij］の最大固有値に対応する固有ベクトルとして求まる。
【００９７】
【数２４】
2010073195.tif 000034
ベクトルｗ1を類似度行列Ｓの固有ベクトルとして求めることで、一つのクラスターが取り出される。
２個目以降のクラスターを、既に抽出されたクラスターと重なりなく抽出するために、第ｋクラスターのメンバシップベクトルｗkの抽出では、類似度行列に修正を加える。即ち、
【００９８】
【数２５】
2010073195.tif 000035
なる制約が付加され、目的関数は以下のように修正される。
【００９９】
【数２６】
2010073195.tif 000036
ここで、dup（ｗk，ｗt）が制約を満たすために付加されたペナルティ項であり、
【０１００】
【数２７】
2010073195.tif 000037
のようにおく。βtはペナルティ項の重みで、前記非特許文献１３では、クラスターの凝集度を考慮して以下のように定めている。
【０１０１】
【数２８】
2010073195.tif 000038
ηはペナルティ項が第１項より十分大きくなる値とする。従って、最適なｗkは以下の行列Ｓ＝［ｓij］の最大固有値に対応する固有ベクトルとして求まる。
【０１０２】
【数２９】
2010073195.tif 000039
ベクトルｗkを類似度行列Ｓの固有ベクトルとして求めることで、ｋ番目のクラスターが取り出される。以下、類似度行列を修正し、修正後の類似度行列Ｓの固有ベクトルを求める処理を繰り返すことにより、逐次クラスターを取り出すことができる。
3. 逐次的クラスター抽出手法の具体例
具体的な例を挙げて津田らの手法を説明する。今、ｎ×ｎ関係性行列Ｓが以下のように与えられたとする。津田らの手法においては、要素ｓijは個体ｉとｊの類似性を表す０から１までの間の数字をもち、値が大きいほど類似性が大きいとする。また、対角要素のｓii（同じ個体同士の関係）は０とおくものとする。
【０１０３】
【表９】
2010073195.tif 000040
【０１０４】
上の表は、ｎ個の項目（対象）間の関係性を示すｎ×ｎ関係データ行列の例である。
ただし、要素ｓijは個体ｉとｊの類似性を表す０から１までの間の数字をもち、値が大きいほど類似性が大きいとする。また、対角要素のｓii（同じ個体同士の関係）は０とおくものとする。
各個体が第ｋ番目のクラスター（群）に所属する度合いを表すｎ次元ベクトルをｗkとおく。まず、第１番目のクラスターでは、ｗ1は上の行列Ｓの最大固有値に対応する固有ベクトル（要素はすべて０以上の数字）として求まる。
【０１０５】
【表１０】
2010073195.tif 000041
【０１０６】
上の表は、ｎ個の個体についてのｎ次元固有ベクトルの例である。
関係性行列から最大固有値とそれに対応する固有ベクトルを求める方法は、既存の汎用的な方法（たとえば、べき乗法やヤコビ法など）を利用すればよい。
要素はすべて０以上となる。値が大きいほど第１クラスターへの所属度合いが大きく、所属しない個体は０に近い値（または０）を持つ。
２番目以降のクラスター（第ｋ番目のクラスター）を抽出する場合は、ｋ−１番目までのクラスターに所属する個体が含まれないようにする必要があるので、重なりがなくなるための制約として、
【０１０７】
【数３０】
2010073195.tif 000042
を用いる。ここで、Ｔはベクトルの内積を表す。
制約を満たすベクトルｗkを求めるために、行列Ｓの対角要素を以下におきかる。
【０１０８】
【数３１】
2010073195.tif 000043
ただし、βtは重み係数で、例えば、以下のように定める。
【０１０９】
【数３２】
2010073195.tif 000044
ここで、ηはβtが十分大きくなるように適宜定める係数である。
修正後の行列Ｓの最大固有値に対応する固有ベクトルがｗkとなる。
【０１１０】
≪協調フィルタリングにおける逐次的なユーザ分類の導入≫
1. 津田らの手法の協調フィルタリングへの適用について
以上の津田らの手法を、認知的均衡理論によるユーザおよびアイテムの分類手法に応用する具体的手順を説明する。ここで、前述の認知的均衡理論における関係性行列と津田らの手法における関係性行列の最も大きな違いは、「津田らの手法では要素がすべて０以上であるが、認知的均衡理論では１，−１および０の３種類のいずれかを要素とする」点にある。そこで、認知的均衡理論における関係性行列で、要素をすべて０以上とすることの妥当性と技術的な意義とを考える。
【０１１１】
Davisは、グラフの均衡化における３群以上への分割可能性を議論している（前述の非特許文献１４参照）。そして、２群分割された部分集合がさらに小さな部分集合に分割できる場合として、その再分割後の部分集合がその中では互いに正の関係性を持つ一方で異なる部分集合間では正の関係性を持たない状況を指摘した。ただし、前記非特許文献１４は、社会科学の観点から概念を述べたものであり、分類の方法論を論じたものではない。
そこで発明者らは、グラフ構造の均衡化に基づくユーザ・アイテム分類アプローチを３群以上への分割に拡張するために、津田らの逐次的なクラスター抽出手法との融合を図り、互いに関連性の強いユーザ・アイテムのクラスターを逐次的に抽出しながら、グラフ構造の観点から均衡化がとれた分割を得ることを検討し次の知見を得た。
【０１１２】
Davisの示唆に基づけば、「１（正の関係性）」のみに着目し、「０と−１は区別せず」に取り扱えることから、「群内は正の関係」「群間はそれ以外」とできる。そうすると、負の関係（−１）を関係性なし（０）と融合して、｛０または１｝の関係性行列にできる。認知的均衡理論における関係性行列をこのように０または１の行列にすることによって、津田らの手法が応用できるようになる。
さらに、負の関係（−１）を関係性なし（０）と融合して考えることは、購買履歴データのような「買ったか買っていないか」の情報と等しい。従って、購買履歴データのような２値の形式の問題への適用においても、逐次的ファジィクラスタリングを適用した場合の優位性が期待できる。
【０１１３】
2. 逐次的ユーザ・アイテム分類の計算方法
購入の有無のようなユーザとアイテムの関連を示す２値からなるｎ×ｍデータ行列Ｚ＝［ｚij］が得られたとする。ただし、ｚijはユーザｉがアイテムｊを購入していれば「１」、それ以外は「０」を持つものとし、要素「０」は必ずしも否定的な関係のみではなく未評価（未購入）を含むものとする。ユーザとアイテムのように異なる項目間の関連性のみを持つデータは、長方形状の関係データと呼ばれる。以下では、前述のBezdekらと同様に対称な正方行列となる関係データを再構築したうえで、構造の均衡化と同様にユーザとアイテムを区別しない分割を考える。
ただし、未評価を許容する立場からユーザ間およびアイテム間の関係性もすべて欠測とみなして、対角ブロックの要素を補完することなしにすべて「０」とおき、以下の（ｎ＋ｍ）×（ｎ＋ｍ）ブロック行列として関連性行列Ｓ＝［ｓij］を定義する。
【０１１４】
【数３３】
2010073195.tif 000045
そして、Ｓが非負の類似度からなる関係性データであるとみなされることから、逐次的ファジィクラスター抽出法と同様のアプローチでユーザ・アイテムの共クラスターを抽出する。ただし、ユーザ間およびアイテム間の関係性をすべて「０」とするアプローチは、ユーザのみまたはアイテムのみのクラスターは抽出せずに、ユーザ・アイテムの組である共クラスターの抽出に限定したものとなっており、ユーザにアイテムを推薦するという協調フィルタリングの目的に特化したモデルといえる。
次に、Ｋ個（Ｋ≧１）のクラスターの抽出時に用いる制約について考える。前述の津田らの手法では、すべての個体について区別がなされていないため、クラスター間の重なりを排除するために
【０１１５】
【数３４】
2010073195.tif 000046
なる制約が用いられた。しかし、ここで考える協調フィルタリング問題では、ユーザ・アイテムクラスターの抽出時にユーザが排他的であれば必ずしもアイテムは排他的である必要はなく、いくつかのクラスターで共有されうるべきである。例えば、アイテムＡとＢを好むユーザ群のクラスターのほかにアイテムＡとＣを好むユーザ群のクラスターが存在してもかまわない。そこで、アイテムの共有を許容する場合には、メンバシップベクトルｗtを
【０１１６】
【数３５】
2010073195.tif 000047
と分割し、
【０１１７】
【数３６】
2010073195.tif 000048
とおいたうえで、ユーザのみが排他的となるように
【０１１８】
【数３７】
2010073195.tif 000049
なる制約を用いる。そのため、第ｋ番目のクラスターの抽出に用いる関係性行列では、対角要素ｓiiを以下のように修正して最大固有値と対応する固有ベクトルを算出する。
【０１１９】
【数３８】
2010073195.tif 000050
3. 逐次的ユーザ・アイテム分類の具体例
以下に、具体例を挙げて説明する。まず、購買履歴データのように、ユーザとアイテムの間の関係性データ（正の関係を持つか、それ以外（負の関係もしくは関係性なし））を表す行列Ｚ＝［ｚij］が与えられた場合を考える。
【０１２０】
【表１１】
2010073195.tif 000051
【０１２１】
上の表は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）の関係性を表すｎ×ｍ関係性行列の例である。
１は正の関係性を表す。０は負の関係性または関係性未知を表す。例えば、購買履歴であれば、１は購入歴あり、０は購入歴なしを表すが、購入歴なしには「その製品が好きでない」と「今後購入する可能性がある」の両方が含まれる。
もし、評価値のデータ行列Ｘ＝［ｘij］が与えられたならば、以下のように変換することでＺ＝［ｚij］が作成される。
【０１２２】
【数３９】
2010073195.tif 000052
ここで、εは、事前に定めた閾値である。ユーザとアイテムのすべての組についての関係性を表現するために、全体の（ｎ＋ｍ）×（ｎ＋ｍ）関係性行列Ｓ＝［ｓij］を以下のブロック行列で表す。
【０１２３】
【数４０】
2010073195.tif 000053
最初のｎ個（または残りのｍ個）の項がｎ人のユーザ（またはｍ種類のアイテム）に対応している。
【０１２４】
【表１２】
2010073195.tif 000054
【０１２５】
上の表は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目間の（ｎ＋ｍ）×（ｎ＋ｍ）関係性行列の例である。
関係性が規定されていないユーザ間（およびアイテム間）の関係性については０を代入して処理している。
行列Ｓ＝［ｓij］の最大固有値に対応する固有ベクトルとして、第１クラスターへの所属度合いのｎ＋ｍ次元ベクトルｗk＝｛ｗki｝が求められる。
【０１２６】
【表１３】
2010073195.tif 000055
【０１２７】
上の表は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目についてのｎ＋ｍ次元固有ベクトルの例である。
すべての要素は０以上であり、値が大きいほど第１クラスターへの所属度合いが大きい。
関係性行列から最大固有値とそれに対応する固有ベクトルを求める方法は、既存の汎用的な方法（たとえば、べき乗法やヤコビ法など）を利用すればよい。
２番目以降のクラスター（第ｋ番目のクラスター）を抽出する場合は、ｋ−１番目までのクラスターに所属するユーザが含まれないようにする必要があるので、重なりがなくなるための制約を定めなければならない。ただし、アイテムについては複数のクラスターに共有されてもかまわない。例えば、アイテムＡとＢを好むユーザ群のクラスターのほかにアイテムＡとＣを好むユーザ群のクラスターが存在してもかまわない。従って、ユーザのみについて重複を排除するための制約として、
【０１２８】
【数４１】
2010073195.tif 000056
を用いる。ここで、
【０１２９】
【数４２】
2010073195.tif 000057
はｗk＝｛ｗki｝のうちでユーザに関する部分を抜き出したｎ次元ベクトルである。
【０１３０】
【表１４】
2010073195.tif 000058
上の表は、ｎ人のユーザ（u-1，…，u-n）について所属度を並べた次元固有ベクトルの例である。
制約を満たすベクトル
【０１３１】
【数４３】
2010073195.tif 000059
を求めるために、行列Ｓの対角要素を以下におきかる。
【０１３２】
【数４４】
2010073195.tif 000060
ただし、βtは重み係数で、例えば、以下のように定める。
【０１３３】
【数４５】
2010073195.tif 000061
ここで、ηはβtが十分大きくなるように適宜定める係数である。
修正後の行列Ｓの最大固有値に対応する固有ベクトルが
【０１３４】
【数４６】
2010073195.tif 000062
となる。
【０１３５】
【表１５】
2010073195.tif 000063
【０１３６】
ユーザについての対角要素が、上で求めた値に置き換えられている。
4. 協調フィルタリングへの適用における運用
クラスターの数をいくつまで抽出するのかについては、
（１）予め定めた数まで抽出する、
（２）予め閾値を適宜定め、すべてのユーザがいずれかのクラスターに閾値以上の所属度合いをもつようになるまで繰り返す、
などの方法がありうる。
クラスターの抽出が終了したら、各ユーザについて、所属度合いが最大となるクラスターを「所属クラスター」と定める。
【０１３７】
【表１６】
2010073195.tif 000064
【０１３８】
上の表は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目についてのｎ＋ｍ次元の所属度ベクトルをＫ本並べた行列の例である。
各ユーザについて、所属度の値が最大となるクラスターが「所属クラスター」と定められる。
例えば、ユーザ１は第１番目のクラスター、ユーザｎは第Ｋ番目のクラスターに所属するとする。
ユーザの所属クラスターが決まったら、各ユーザについて自分が所属するクラスターで所属度合いの大きいアイテムを推薦すべきアイテムとして選別する。
【０１３９】
【表１７】
2010073195.tif 000065
【０１４０】
上の表は、ｎ人のユーザ（u-1，…，u-n）とｍ個のアイテム（i-1，…，i-m）を合わせたｎ＋ｍ個の項目についてのｎ＋ｍ次元の所属度ベクトルをＫ本並べた行列の例である。
各ユーザについて、自分が所属するクラスターで所属度合いの大きいアイテムが、順に推薦されるべきアイテムとして選別される。
例えば、ユーザ１が第１番目のクラスターに所属するなら、第１番目のクラスターへの所属度合いの大きいアイテム（たとえばアイテムｍ）が推薦される。
各ユーザにいくつのアイテムを推薦するかは、
（１）  予め定めた数のアイテムを推薦する、
（２）  予め定めた閾値以上の所属度を持つアイテムをすべて推薦する、
などの方法がありうる。
【０１４１】
5. 実験例２
5-1. 人工データを用いた実験
提案手法の特徴を調べるために、人工データを用いた実験を行った。図４は、この実験例において、関係性データ行列の作成に用いた元データを示すグラフである。３０人のユーザ（○）と３０個のアイテム（×）が三角形の頂点（（０，０），（０，８），（４，５））に平均を持つ正規分布状に散布され、２次元平面上にユーザ・アイテム間の関係を表現しており、○と×のユークリッド距離ｄijに基づいて、ユーザ・アイテム間の３０×３０関連性行列Ｚ＝［ｚij］を以下のように作成した。
【０１４２】
【数４７】
2010073195.tif 000066
ここで、３０×３０個の要素のうち、２７０個が「１」となり、残りが「０」となった。クラスター数はＫ＝３、ペナルティ項の重みはη＝１０とした。また、ここではユーザだけでなくアイテムも排他的な分類をされるとして、
【０１４３】
【数４８】
2010073195.tif 000067
という制約を用いた。
【０１４４】
図５は、１回目に抽出されたクラスター（クラスター１）、クラスター１のメンバシップとの重なりを排除する制約を付加した２回目に抽出されたクラスター（クラスター２）、およびクラスター１と２の両方との重なりを排除した３回目に抽出されたクラスター（クラスター３）のそれぞれについて、クラスターごとに得られたメンバシップｗiと最大メンバシップを持つクラスターに分類した際の分類結果を元データの空間で示すグラフである。図５（ａ）〜図５（ｃ）では、黒色がユーザを、灰色がアイテムを示し、縦軸がメンバシップ値を表す。図５（ｄ）では、「太字で大きな印」、「細字で中程度の印」、「太字で小さな印」が三つのクラスターを示している。図から、提案法で関係性の強いユーザとアイテムの組をクラスターとして逐次的に抽出できていることが分かる。特に、他との関連の強いユーザやアイテム（塊の中心付近のユーザ・アイテム）ほど大きなメンバシップ値を持っており、関連の強弱の指標として利用できるといえる。
【０１４５】
次に、データ行列に欠測がある場合の影響について調べるために、２７０個の「１」要素のうち、ランダムに選択した１８０個を「０」に置き換えて、同様の実験を行った。得られた結果を、図６に示す。欠測が多く含まれる場合でも関係性の強いユーザとアイテムの近傍を抽出できていることから、協調フィルタリングのように疎な関係性データにも適用可能であることが分かる。
【０１４６】
5-2. 購買履歴データに基づく協調フィルタリング
以上で述べたように、提案手法は、協調フィルタリングに認知的均衡を適用すべく拡張されたユーザ・アイテムの関係性行列につき、その関係性行列から３群以上のクラスターを抽出するため、さらに前記関係性行列を２値行列とし、逐次的クラスター抽出手法を適用するものである。
この提案手法を実世界の購買履歴データに適応し、協調フィルタリングモデルとしての有効性を検証する。日本経済新聞社が、2000年の購買調査を行ったデータ（市販されていたもの）を用いた。996世帯が以下の18製品を所有しているか否かのデータ（996×18データ行列）である。
【０１４７】
調査対象の１８製品を以下に示す。括弧内は所有世帯数である。
１、自動車（８２５）、
２、ピアノ（３４０）、
３、ＶＴＲ（９３３）、
４、ルームエアコン（９１１）、
５、パソコン（５８８）、
６、ワープロ（５０６）、
７、ＣＤ（８４４）、
８、ＶＤ（３２５）、
９、自動二輪車（２９４）、
１０、自転車（８９３）、
１１、大型電気冷蔵庫（８５８）、
１２、中・小型電気冷蔵庫（２０６）、
１３、電子レンジ（９６２）、
１４、オーブン（３４７）、
１５、コーヒーメーカー（６１７）、
１６、電気洗濯機（９８６）、
１７、衣料乾燥機（２２６）、
１８、食器乾燥機（２４２）。
【０１４８】
5-2-1. テストデータの作成法
実験では、９９６世帯をランダムに並べ替えた上で２等分し、その一方をテストデータとして、それぞれの製品について所有の有無を未知とした際の分類結果から、所有の有無を予測した精度を調べた。また、予測の対象製品としては、所有率が極端に高いもの（８割以上）と低いもの（３割未満）を除いて、ピアノ、パソコン、ワープロ、ＶＤ、オーブン、コーヒーメーカーの６種類を用いた。
【０１４９】
提案法では、テスト世帯の未知要素について、対象製品の要素「１」をすべて「０」に置き換えて逐次的にユーザ・アイテムクラスターを抽出し、ユーザをメンバシップ最大となるクラスターに割り当てた際の当該クラスターでのアイテムのメンバシップをもとに推薦の有無を決定した。すなわち、アイテムのメンバシップが大きいほど推薦されるべき製品であるとした。ただし、個々の製品が複数のクラスターに共有される場面も想定し、
【０１５０】
【数４９】
2010073195.tif 000068
という制約を用いた。さらに、ユーザの分類を明確にするために、逐次的にクラスターを抽出する際に閾値を最大メンバシップの８割と設定し、メンバシップが閾値未満のユーザのメンバシップを０にした。ペナルティ項の重みはη＝１０００００とした（メンバシップの切り捨てに伴い、前節よりも大きな値を用いている）。
具体的に説明する。いま、第２アイテム（ｉ−２）が予測対象であり、ｕ−４９９から９９６がテスト世帯であるとする。テスト世帯について、予測対象アイテムのデータをすべて０に置き換える。ここで、０は必ずしも「この製品を好まない」とは限らず、「今後購入する可能性あり」も含む。
【０１５１】
【表１８】
2010073195.tif 000069
【０１５２】
【表１９】
2010073195.tif 000070
テスト世帯のｕ−４９９から９９６について、ｉ−２の要素をすべて０（未購入）に置き換える。
【０１５３】
テスト世帯のｕ−４９９から９９６について、ｉ−２の要素をすべて０（未購入）に置き換えた。
ただし、０は「今後購入する可能性あり」も含む。
5-2-2. 検証における予測と精度計算
ｕ−４９９から９９６のそれぞれがｉ−２と同じグループに入れば、０を１に置き換える。置き換えた後のデータ（灰色の部分）と、元のデータ（灰色の部分）一致割合で精度を測る。
【０１５４】
5-2-3. 精度検証に用いた尺度
ROC曲線の下側領域の面積を尺度として用いた。ROC曲線とはROC曲線は検査方法間の比較を視覚的に行う際に用いられるもので、推薦器の精度（どの程度ゴミを少なくしながら多くの有効な推薦が行われたか）を測る尺度である。本実験であれば、推薦するか否かのcut-off ポイント（提案法であればアイテムのメンバシップ値の閾値、相関に基づく手法であれば相関の平均値の閾値）を順に変化させた際に、縦軸に真陽性率（True Positive Rate）、横軸に偽陽性率（False Positive Rate）をとって値をプロットしたものとなる。また、曲線よりも下の領域の面積が大きいほど、つまり曲線が左上に上がっているほど、精度が良いことを示している。
【０１５５】
推薦の際の閾値を順に変化させた際に、真陽性率（推薦されるべきアイテムが正しく推薦された比率）と偽陽性率（推薦されるべきでないアイテムが推薦された比率）を2次元平面内にプロットした曲線がROC曲線であり、その下側領域の面積が０．５のときがランダムに推薦した場合の精度に対応し、値が大きいほど精度が良いとみなされる。
5-2-4. 提案法におけるユーザとアイテムのグループ分け
また、逐次的にクラスターを抽出する際に、各回の実行において求められた凝集度（（14）式）が図７のようにＫ＝１０でほぼ収束した。すなわち、抽出されたクラスターの数Ｋが１０のときにほぼすべてのユーザがいずれかのクラスターへ配分されている。そこで、逐次的にクラスターを抽出する処理はＫ＝１０で終了とした。
【０１５６】
実用上は、すべてのユーザが０でないメンバシップを持つようになるまで、逐次的なクラスター抽出を継続する方法もありうる。しかし、本実験では第１０クラスターが極端に小さなクラスターとなったため、その時点でクラスターの抽出を終了した。
その後、各ユーザについて所属度合いが最大となるクラスター（所属クラスター）を決定し、自分が所属するクラスターに対する所属度合いが大きいアイテムが推薦されるものとした。推薦に際しては、所属度合いがいくら以上なら推薦するかという閾値を定めるが、閾値を０から順に増やした際の真陽性率と偽陽性率を調べていくことでROC曲線を描き、その下側領域の面積を求めた。
【０１５７】
5-2-5. 比較対象の予測法
比較対象の予測手法としては、アイテム間の相関をもとに、テスト世帯が所有している製品との相関の平均値から推薦の有無を決定する手法を用いた。すなわち、バスケット分析における併せ買いの可能性が高い製品を推薦するために、製品間の相関を指標としているものである。また、この手法はアイテム間の相関に基づくGroupLens を｛０，１｝の評価値に適応したものに等しい。
トレーニング用のデータ（上の例なら、ｕ−１から４４８）からアイテム間の相関係数を求め、テスト世帯について個々の世帯が購入済みのアイテムと予測対象のアイテムとの相関係数の平均値が大きいアイテムを推薦した。推薦の際、相関係数の平均値がいくら以上なら推薦するかの閾値を変化させながらROC曲線を描き、その下側領域の面積を求めた。
【０１５８】
5-2-6. 有効性の検証
図８に、製品ごとに得られたROC 曲線の比較結果を示す。図中、実線が提案法で得られたROC曲線を、波線が比較手法で得られたROC曲線を表す。数字は、それぞれの下の領域の面積を示す。ROC曲線の座標および面積の算出には、統計ソフトウェアのSPSS13.0.1Jを用いた。
ROC曲線の下側領域の面積を、交差検証法で比較した。２分割されたデータのそれぞれに対する結果とその平均値を以下に比較する。
【０１５９】
【表２０】
2010073195.tif 000071
【０１６０】
図８に示す、テスト集合１の結果については、ＶＤを除く５製品について提案手法のROC曲線が左上に上がり、曲線下の領域の面積（６製品の平均値）も提案法が０．５９１と比較手法の０．５６１を上回っていることから、提案法の精度が高いことが分かる。
交差検証としてトレーニングデータとテストデータを入れ替えて同様の実験をした場合も面積の平均値が「提案法：０．５８０、比較手法：０．５７２」と提案法が上回った。
【０１６１】
以上のように、提案手法が購買可能性を精度よく予測できていることから、購買履歴に基づく協調フィルタリング法として有効であるといえる。
即ち、提案法は、なるべくゴミを少なくしながら多くの有効な推薦を行う性能が高いことが確認された。
【０１６２】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【０１６３】
P、O：人
X：対象
1, 2, 3, 4, 5：項
【図１】
2010073195.tif 000080
【図２】
2010073195.tif 000081
【図３】
2010073195.tif 000082
【図４】
2010073195.tif 000083
【図７】
2010073195.tif 000084
【図８】
2010073195.tif 000085
【図５】
2010073195.tif 000086
【図６】
2010073195.tif 000087