(57)【特許請求の範囲】
【請求項１】
各ユーザが各アイテムを選択したか否かあるいは選択した頻度を示したアイテム選択情報を、前記ユーザと前記アイテムに関する行列情報として扱ってクラスタリングするために、
所定のユーザクラス割り当て確率式に基づき、前記行列情報における前記ユーザのそれぞれを複数のユーザクラスにクラス分けし、
所定のアイテムクラス割り当て確率式に基づき、前記行列情報における前記アイテムのそれぞれを複数のアイテムクラスにクラス分けし、
前記ユーザクラスと前記アイテムクラスとの組み合わせによって一意に特定されるユーザ・アイテムブロックごとに、確率モデル上で当該ユーザクラスのユーザが当該アイテムクラスのアイテムを選択する仮の確率である仮選択確率を所定のアイテム選択確率式に基づいて与え、
前記所定のユーザクラス割り当て確率式、前記所定のアイテムクラス割り当て確率式、および、前記所定のアイテム選択確率式から算出される前記行列情報の事後確率の最大化を図ることで、前記行列情報を前記ユーザ単位および前記アイテム単位の両方でクラスタリングする共クラスタリング装置であって、
前記した各ユーザクラスに対して各アイテムクラスに関する所定のアイテムクラス指定確率を与え、前記した各アイテムクラスに対して各ユーザクラスに関する所定のユーザクラス指定確率を与え、前記所定のアイテム選択確率式は、前記ユーザ・アイテムブロックごとの、前記所定のアイテムクラス指定確率と前記所定のユーザクラス指定確率との乗算値または乗算値に基づく値として前記仮選択確率を算出する式であり、
前記アイテム選択情報と前記行列情報とを格納する記憶部と、
最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記ユーザの所属するユーザクラスを、前記所定のユーザクラス割り当て確率式と前記仮選択確率とに基づいて更新するユーザクラス更新部と、
最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記アイテムの所属するアイテムクラスを、前記所定のアイテムクラス割り当て確率式と前記仮選択確率とに基づいて更新するアイテムクラス更新部と、
最新の前記行列情報に基づいて、前記行列情報の事後確率を算出する共クラスタリング結果評価部と、
を備えることを特徴とする共クラスタリング装置。
【請求項２】
所定条件を満たすまで、前記ユーザクラス更新部、前記アイテムクラス更新部および前記共クラスタリング結果評価部による処理を繰り返させ、前記所定条件を満たしたとき、最新の前記行列情報に基づいた前記ユーザと前記アイテムに関する共クラスタリングの結果を前記記憶部に格納する共クラスタリング終了判定部、をさらに備える
ことを特徴とする請求項１に記載の共クラスタリング装置。
【請求項３】
前記ユーザクラス更新部は、
最新の前記行列情報から、更新する前記ユーザを１つ選び、
その選んだ前記ユーザを移行させる先となる既存および新規の前記ユーザクラスのそれぞれの移行確率を算出し、
当該それぞれの移行確率にしたがって当該ユーザを移行させる先の前記ユーザクラスを決定し、
当該決定に基づいて前記ユーザクラスに関する情報を更新する
ことを特徴とする請求項１または請求項２に記載の共クラスタリング装置。
【請求項４】
前記アイテムクラス更新部は、
最新の前記行列情報から、更新する前記アイテムを１つ選び、
その選んだ前記アイテムを移行させる先となる既存および新規の前記アイテムクラスのそれぞれの移行確率を算出し、
当該それぞれの移行確率にしたがって当該アイテムを移行させる先の前記アイテムクラスを決定し、
当該決定に基づいて前記アイテムクラスに関する情報を更新する
ことを特徴とする請求項１または請求項２に記載の共クラスタリング装置。
【請求項５】
各ユーザが各アイテムを選択したか否かあるいは選択した頻度を示したアイテム選択情報を、前記ユーザと前記アイテムに関する行列情報として扱ってクラスタリングするために、
所定のユーザクラス割り当て確率式に基づき、前記行列情報における前記ユーザのそれぞれを複数のユーザクラスにクラス分けし、
所定のアイテムクラス割り当て確率式に基づき、前記行列情報における前記アイテムのそれぞれを複数のアイテムクラスにクラス分けし、
前記ユーザクラスと前記アイテムクラスとの組み合わせによって一意に特定されるユーザ・アイテムブロックごとに、確率モデル上で当該ユーザクラスのユーザが当該アイテムクラスのアイテムを選択する仮の確率である仮選択確率を所定のアイテム選択確率式に基づいて与え、
前記所定のユーザクラス割り当て確率式、前記所定のアイテムクラス割り当て確率式、および、前記所定のアイテム選択確率式から算出される前記行列情報の事後確率の最大化を図ることで、前記行列情報を前記ユーザ単位および前記アイテム単位の両方でクラスタリングする共クラスタリング装置による共クラスタリング方法であって、
前記した各ユーザクラスに対して各アイテムクラスに関する所定のアイテムクラス指定確率を与え、前記した各アイテムクラスに対して各ユーザクラスに関する所定のユーザクラス指定確率を与え、前記所定のアイテム選択確率式は、前記ユーザ・アイテムブロックごとの、前記所定のアイテムクラス指定確率と前記所定のユーザクラス指定確率との乗算値または乗算値に基づく値として前記仮選択確率を算出する式であり、
前記共クラスタリング装置は、前記アイテム選択情報と前記行列情報とを格納する記憶部を備え、
ユーザクラス更新部が、最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記ユーザの所属するユーザクラスを、前記所定のユーザクラス割り当て確率式と前記仮選択確率とに基づいて更新するユーザクラス更新ステップと、
アイテムクラス更新部が、最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記アイテムの所属するアイテムクラスを、前記所定のアイテムクラス割り当て確率式と前記仮選択確率とに基づいて更新するアイテムクラス更新ステップと、
共クラスタリング結果評価部が、最新の前記行列情報に基づいて、前記行列情報の事後確率を算出する共クラスタリング結果評価ステップと、
を実行することを特徴とする共クラスタリング方法。
【請求項６】
共クラスタリング終了判定部が、所定条件を満たすまで、前記ユーザクラス更新部、前記アイテムクラス更新部および前記共クラスタリング結果評価部による各ステップを繰り返させ、前記所定条件を満たしたとき、最新の前記行列情報に基づいた前記ユーザと前記アイテムに関する共クラスタリングの結果を前記記憶部に格納するステップを実行する
ことを特徴とする請求項５に記載の共クラスタリング方法。
【請求項７】
前記ユーザクラス更新部は、前記ユーザクラス更新ステップにおいて、
最新の前記行列情報から、更新する前記ユーザを１つ選び、
その選んだ前記ユーザを移行させる先となる既存および新規の前記ユーザクラスのそれぞれの移行確率を算出し、
当該それぞれの移行確率にしたがって当該ユーザを移行させる先の前記ユーザクラスを決定し、
当該決定に基づいて前記ユーザクラスに関する情報を更新する
ことを特徴とする請求項５または請求項６に記載の共クラスタリング方法。
【請求項８】
前記アイテムクラス更新部は、前記アイテムクラス更新ステップにおいて、
最新の前記行列情報から、更新する前記アイテムを１つ選び、
その選んだ前記アイテムを移行させる先となる既存および新規の前記アイテムクラスのそれぞれの移行確率を算出し、
当該それぞれの移行確率にしたがって当該アイテムを移行させる先の前記アイテムクラスを決定し、
当該決定に基づいて前記アイテムクラスに関する情報を更新する
ことを特徴とする請求項５または請求項６に記載の共クラスタリング方法。
【請求項９】
請求項１ないし請求項４のいずれか一項に記載の共クラスタリング装置を構成するコンピュータに実行させることを特徴とする共クラスタリングプログラム。
【請求項１０】
請求項９に記載の共クラスタリングプログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノンパラメトリックベイズモデル（ディリクレ過程混合モデル）に基づく、各ユーザが各アイテムを選択したか否かあるいは選択した頻度を示したアイテム選択情報（購買履歴データなど）に対する共クラスタリング（ユーザとアイテムの両方を同時にクラスタリングする手法：Co-clustering）の技術に関する。
【背景技術】
【０００２】
近年、情報の高度化や多様化が進み、膨大な情報の中から必要な情報を効率よく抽出する技術が求められている。そのような状況の中、例えば、インターネットの普及などにより世界中から容易に商品を購入できるようになったことや、ユーザの嗜好が多様化してきたことなどにともない、企業にとってユーザのニーズを詳細に把握することがますます重要になってきている。
【０００３】
ユーザのニーズを把握する１つのアプローチとして、複数ユーザのアイテム購入履歴（購買履歴データ）を元にユーザ群を、購買履歴の似通った幾つかのユーザグループに分けるユーザクラスタリング（セグメンテーション）がある。また、ユーザクラスタリングと同様に、アイテム群を、同じユーザに購入されやすいアイテムグループに分ける、アイテムクラスタリングも考えられている。ユーザクラスタリングの場合には、同じユーザグループに所属するユーザの共通点を見出すことでユーザのニーズや嗜好の把握に役立てることができる。また、アイテムクラスタリングの場合には、同じアイテムグループに所属するアイテムの共通点を見出すことで新商品の開発に役立てることができる。
【０００４】
ここで、ユーザとアイテムのいずれかに関するクラスタリングだけではなく、共クラスタリングも考えられている。共クラスタリングとは、ユーザとアイテムの一方をクラスタリングする際に、他方のクラスタリング結果を相互に利用しながらユーザクラスとアイテムクラスから定まるユーザ・アイテムブロック（以下、単に「ブロック」ともいう。）を求め、消費者行動の把握につながるより有用な情報を得ようとするアプローチである。
【０００５】
図１０は、購買履歴データの共クラスタリングの例を示す図である。図１０において、今、Ｎ人のユーザが、Ｍ個のアイテムのそれぞれについて、購入したか否かに関する購買履歴データを考える。これまでの購買履歴データは、図１０における左図のように行列Ｒで表現される。すなわち、Ｎ×Ｍ行列Ｒの（ｉ,ｊ）要素Ｒｉ,ｊはユーザｉ（ｉ＝１,２,…,Ｎ）がアイテムｊ（ｊ＝１,２,…,Ｍ）を購入していた場合に「１」、購入していない場合「０」をとるものとする。
【０００６】
ここで、ユーザとアイテムのそれぞれを共クラスタリングしたものが図１０の右図である。右図では、同じユーザクラスに属するユーザ、同じアイテムクラスに属するアイテムがそれぞれ隣り合うように、ソートしてある。このように共クラスタリングすることによって、「１」の部分、「０」の部分がより局所的に集中し、「ブロック化」されていることがわかる。なお、ソートは、必ず、ユーザ単位あるいはアイテム単位で行われる。
【０００７】
ユーザ（またはアイテム）をクラスタリングする際にアイテム（またはユーザ）クラスを制約に加えてクラスタリングを行うことで、ユーザクラスとアイテムクラスから規定される「ユーザ・アイテムブロック」が得られ、得られたユーザ・アイテムブロックからユーザクラスやアイテムクラスの特徴を把握することができる。この方法は、ユーザとアイテムを個別にクラスタリングする方法よりも、より詳細な情報が得られることが期待される。
【０００８】
共クラスタリングを実現する１つの方法に、Kempらにより提案されたInfinite Relational Model（ＩＲＭ）（非特許文献１参照）がある。
ＩＲＭでは、まず、与えられたデータを生成する、もっともらしい、データの生成過程（生成プロセス）をモデル化する。すなわち、「与えられたデータは、このような生成過程によって生成されたのではないか」という仮説を立てる。次に、この仮説の下で、与えられたデータを最もうまく説明するモデルを探索する。
【０００９】
ここで、図１１を参照して、ＩＲＭが仮定するデータ生成プロセスを、購買履歴データを用いて説明する。図１１は、ＩＲＭのデータ生成プロセスの説明図である。図１０の場合と同様、ユーザｉがアイテムｊを購入する（していた）場合に「１」、購入（しない）していない場合に「０」をとるものとする。
【００１０】
（ＩＲＭのプロセス１）
[１−１]ユーザ全体を、複数のユーザクラスに分割する。すなわち、まず、複数のユーザクラスの集合（ユーザクラス集合）を生成し、各ユーザはユーザクラス（のひとつ）ｋを選択し、そこに所属（帰属）する。なお、ユーザクラス数Ｋは、固定ではなく変動する、つまり、データに合わせて決定される。
[１−２]アイテム全体を、複数のアイテムクラスに分割する。すなわち、まず、複数のアイテムクラスの集合（アイテムクラス集合）を生成し、各アイテムは、アイテムクラス（のひとつ）ｓを選択し、そこに所属（帰属）する。なお、アイテムクラス数Ｓは、固定ではなく変動する、つまり、データに合わせて決定される。
【００１１】
（ＩＲＭのプロセス２）
[２−１]任意のユーザクラス（のひとつ）と任意のアイテムクラス（のひとつ）の組に対し（すなわち、任意の「ユーザ・アイテムブロックｋｓ」に対し）、そのブロック固有の購入確率である「０〜１」の範囲の実数値をひとつ割り当てる。
[２−２]特定のユーザクラスに属するユーザは、特定のアイテムクラスに属するアイテムを、そのユーザ・アイテムブロックに割り当てられている購入確率にしたがって購入する、と仮定する。
【００１２】
そして、与えられた購買履歴データが、前記プロセスを表現した確率モデルに基づいて生成されたものとみなし、与えられた購買履歴データを最もよく説明するモデルを学習する、すなわち、与えられたデータからモデル学習を行う。
例えば、前記生成過程ではユーザとアイテムがそれぞれ「（ある）クラスに所属する」と述べているが、具体的なクラスヘの割り当て（すなわちクラスタリング）は述べていない。具体的なクラスヘの割り当てについては、データごとに異なる、最も適した（データを最もよく説明する）割り当て法があるはずである。これを探索する必要があり、そうすることが、データを共クラスタリングすることになる。
【００１３】
一般に、ユーザクラスとアイテムクラスの割り当てパターンは膨大に存在するため、一度に最適なクラスタリング結果を得るのは困難である。そのため、以下で述べるサンプリングを用いて、クラスタリングを行う。サンプリングでは、まず、ランダムなクラスタリング結果を初期値とし、目的関数である事後確率が大きくなるように逐次的にクラスタリング結果を改善する。
【００１４】
ここで、事後確率とは、条件付確率の一種であり、特定の情報を考慮に入れた条件での、特定の変数に関する確率である。また、事前確率とは、前記した特定の情報がない条件での、特定の変数に関する確率である。例えば、ベイズの定理によれば、事前確率に尤度（関数）を乗算すると事後確率が得られる。事後確率は、モデル学習の結果の良さの尺度となりえる。
【００１５】
ＩＲＭについての説明を続けると、具体的には、まず、初期値として、ユーザとアイテムをランダムにクラスタリングする。次に、与えられた購買履歴データの事後確率（後記する式（５））が大きくなるように、ユーザの帰属ユーザクラスとアイテムの帰属アイテムクラスの各々を逐次的に更新していく。評価値である事後確率がこれ以上変化（改善）されなくなった時点で帰属クラスの更新を停止する。
【００１６】
以下、ＩＲＭが仮定する確率モデルと共クラスタリング結果の評価式について説明する。まず、以下がデータとして観測される量である。
・ユーザ数はＮ、アイテム数はＭである。
・行列Ｒは購買履歴データを表し、Ｎ×Ｍ行列Ｒの（ｉ,ｊ）要素Ｒｉ,ｊはユーザｉ（ｉ＝１,２,…,Ｎ）がアイテムｊ（ｊ＝１,２,…,Ｍ）を購入していた場合に「１」、購入していない場合に「０」をとるものとする。
【００１７】
これらが得られた下で、以下のような確率モデルを仮定する。
（ユーザクラス割り当ての事前確率）
Ｚ＝｛z１,z２,…,zＮ｝はユーザのクラス割り当てを表し、ｚｉ＝ｋはユーザｉの帰属ユーザクラスがｋであることを意味する。したがって、ユーザクラス数をＫとすると、ｚｉ∈｛１,２,…,Ｋ｝（ｉ＝１,２,…,Ｎ）である。このとき、ｎｋをユーザクラスｋに帰属するユーザ数（ｚｉ＝ｋとなるｉの個数：ユーザクラスサイズ）とするとΣＫｋ＝１ｎｋ＝Ｎ（「ΣＫｋ＝１」は「ｋ」が「１」から「Ｋ」までの値をとる、という意味である。以下同様）であって、ユーザへのユーザクラス割り当てＺの事前確率は、式（１）（ユーザクラス割り当て確率式）となる。ただし、α＞０は定数（ハイパーパラメータ）である。
【数１】
0004934058.tif 000002
【００１８】
ここで、事前確率（分布）は、購買履歴データＲを知る前の状態（すなわちＲの観測の「事前」の状態）での、クラス分けの「良さ」をあらわす尺度であると考えることができる。ユーザクラス数Ｋやユーザクラスサイズｎｋが変化することによって、式（１）に示すＰ（Ｚ;α）の値が変化する。直感的には、各ユーザクラスサイズｎｋが大きいほど、また、ユーザクラス数Ｋが少ないほど（α＜１の場合）良いクラス割り当てであると考えることを意味する。なお、ユーザクラス数Ｋは事前に固定されるのではなく、与えられたデータになるべく適した数値となるように逐次更新（変更）され、最終的に決定される。
【００１９】
購買履歴データＲを知った後の状態では、基本的に、各ユーザ・アイテムブロックは、共クラスタリングした結果、「１」ばかり、もしくは、「０」ばかり、という、「１」と「０」がはっきりしたブロックになることが理想である。しかし、そのことだけを目指すと（そのことだけを目的関数として最適化してしまうと）、できるだけ小さなブロックを作ろうとしてしまう。なぜなら、極端な例として、全ユーザ・アイテムブロックの要素をすべて一つずつにすれば、「１」と「０」が一番はっきりするからである。しかし、このような、「すべての要素が別のブロック」という状態は、「ブロック分けをする」という観点からはバランスに欠け、望ましくない。これを補正するのが、事前確率Ｐ（Ｚ；α）である。後記するＰ（Ｗ；β）についても同様である。
【００２０】
（アイテムクラス割り当ての事前確率）
同様に、Ｗ＝｛ｗ１,ｗ２,…,ｗＭ｝はアイテムのクラス割り当てを表し、ｗｊ＝ｓはアイテムｊの帰属アイテムクラスがｓであることを意味する。したがって、アイテムクラス数をＳとすると、ｗｊ∈｛１,２,…,Ｓ｝（ｊ＝１,２,…,Ｍ）である。このとき、ｍｓをアイテムクラスｓに帰属するアイテム数（ｗｊ＝ｓとなるｊの個数）とするとΣＳｓ＝１ｍｓ＝Ｍであって、アイテムへのアイテムクラス割り当てＷの事前確率は、式（２）（アイテムクラス割り当て確率式）となる。また、アイテムクラス数Ｓは事前に固定されるのではなく、与えられたデータになるべく適した数値となるように逐次更新（変更）され、最終的に決定される。β＞０は定数（ハイパーパラメータ）である。
【数２】
0004934058.tif 000003
【００２１】
（行列Ｒの出現確率）
さらに、Θ＝｛θｋ,ｓ｜ｋ＝１,２,…,Ｋ,  ｓ＝１,２,…,Ｓ｝は、ユーザクラスｋとアイテムクラスｓから決まるユーザ・アイテムブロック（ｋ,ｓ）ごとの購買確率である。すなわち、ユーザクラスｋに所属するユーザは、アイテムクラスｓの所属するアイテムをθｋ,ｓの確率で購入する(（１−θｋ,ｓ）の確率で購入しない)ことを意味する(「ベルヌーイ試行」と呼ばれる)。したがって、Ｚ,Ｗ,Θが与えられた下での、観測データであるＲの出現確率は式（３）で表される。なお、前記したように、ユーザクラス数Ｋとアイテムクラス数Ｓは、固定ではなく、逐次更新されるものである。
【数３】
0004934058.tif 000004
ただし、Ｒの各要素はおのおの独立に生成されたものと仮定する。式（３）は、Ｒが与えられた下での、Θの「良さ」（尤度）である。
【００２２】
（購買確率）
θｋ,ｓは、単なる「０」〜「１」の大きさの一様乱数で生成されるのではなく、通常はベータ分布によって生成される、と考える（すなわちθｋ,ｓの事前分布としてベータ分布を用いる）。そこで、ベータ分布のパラメータをγ＝｛γ０,γ１｝とすると、θｋ,ｓの事前分布は式（４）で表される。なお、Γ（ｘ）はガンマ関数である。
【数４】
0004934058.tif 000005
【００２３】
以上が、ＩＲＭにおいて仮定する確率モデルである。
このモデルの下で、与えられた購買履歴データＲに関して、最適な共クラスタリングの結果を求める。共クラスタリング結果であるユーザクラス割り当てＺとアイテムクラス割り当てＷに関して、Ｒが与えられた下での、ＺとＷの事後確率は式（５）で与えられる。
Ｐ（Ｚ,Ｗ｜Ｒ；α,β,γ）  ・・・式（５）
【００２４】
そして、最適な共クラスタリングとは、この式（５）で与えられる事後確率が最大（厳密な最大ではなく計算した中での最大でよい）となる共クラスタリング結果を求めることに他ならない。すなわち、式（５）は、購買履歴データＲに対する、共クラスタリング結果Ｚ,Ｗの当てはまりの良さを表す評価関数であり、この値が大きいほど良い共クラスタリング結果であるとみなすことができる。
【００２５】
式（５）は、以下のようにして計算できる。すなわち、ＩＲＭの仮定の下、式（１）,（２）,（３）,（４）を用いて、確率モデル(購買履歴データの同時分布)は式（６）のように表現できる。
Ｐ（Ｒ,Θ,Ｚ,Ｗ；α,β,γ）＝
Ｐ(Ｒ｜Θ,Ｚ,Ｗ)Ｐ(Ｚ;α)Ｐ(Ｗ;β)Ｐ(Θ;γ）  ・・・式（６）
【００２６】
ここで、購買履歴データＲが与えられた下での条件付分布は式（７）のように表現できる。
Ｐ（Ｚ,Ｗ,Θ｜Ｒ；α,β,γ）  ・・・式（７）
【００２７】
また、ベイズの定理から、式（７）は式（８）のように表現できる。
【数５】
0004934058.tif 000006
【００２８】
式（８）の右辺の分母Ｐ（Ｒ；α,β,γ）は定数となるため、分子の項について考える。すなわち、式（９）,（１０）のように表現できる。
【数６】
0004934058.tif 000007
【００２９】
ここで、θｋ,ｓ（∈Θ)の事前分布としてベルヌーイ分布の共役事前分布であるベータ分布を用いたため、Θは式（１１）,（１２）に表現するように積分消去することができる。すなわち、式（９）の左辺と式（１０）との両辺をΘについて積分し、その後、式（１１）の積分を実行すると、式（１２）のようにΘが消えることになる。
【数７】
0004934058.tif 000008
【００３０】
式（１１）の左辺は前記した式（５）のＰ（Ｚ,Ｗ｜Ｒ；α,β,γ）に他ならず、これが式（１２）により計算できることになる。式（１２）の各項は、それぞれ、式（１）,（２）,（３）から計算できる。
【００３１】
ＩＲＭの特徴は、従来の(共)クラスタリング手法のほとんどが事前に必要とするクラス数を、予め与えることなく、与えられたデータから、クラス数Ｋ,Ｓを統計的学習の枠組みで自動的に決定できる点にある。通常、購買履歴データなどの実データにおけるクラス数は事前には未知であり、他の従来手法のようにクラス数に対する評価尺度を元に探索的にクラス数を決定する必要が無い。
【非特許文献１】Kemp, C., Tenenbaum, J. B., Griffiths, T. L., Yamada, T.＆ Ueda, N., “Learning systems of concepts with an infinite relational model.” In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06), pages 381-388, June 2006.
【発明の開示】
【発明が解決しようとする課題】
【００３２】
しかしながら、ＩＲＭを購買履歴データに適用する場合、以下の二つの点が問題となる。
（問題１）
購買履歴データＲが疎（スパース）である。すなわち、Ｒｉ,ｊ＝１（購入する）となる要素に比べて、Ｒｉ,ｊ＝０（購入しない）となる要素数が圧倒的に多いにもかかわらず、ＩＲＭはＲｉ,ｊ＝１とＲｉ,ｊ＝０を対等に扱うモデルになっているため、購買履歴データを扱うことが困難である（結果の精度がよくない）。
【００３３】
（問題２）
購買履歴データＲにおいて、Ｒｉ,ｊ＝０となる要素は、必ずしも「購入しない」ことを意味するのではなく、むしろ、「購入する／しないが不明である」と解釈すべきである。例えば、一般にユーザは、現在未購入のアイテムを、場合によっては、将来的には購入する（Ｒｉ,ｊ＝０の箇所がＲｉ,ｊ＝１となる）可能性があると考えるのが自然である。すなわち、購買履歴データＲは欠損値が多数存在するデータとみなせる。しかし、ＩＲＭは欠損値が存在するデータを対象として考案されたモデルではないため、このような状況をうまく扱えない（結果の精度がよくない）。
【００３４】
以上をまとめると、従来技術であるＩＲＭは、必ずしも購買履歴データを扱うのに適したモデルではないと言える。
【００３５】
そこで、本発明は、前記した問題を解決するためになされたものであり、購買履歴データのような欠損値を含んだデータ（購買履歴データＲにおいて、Ｒｉ,ｊ＝０の箇所がＲｉ,ｊ＝０でない可能性を持つようなデータ）に、より適した生成プロセス（確率モデル）に基づいて、ユーザとアイテムを共クラスタリングすることを課題とする。
【課題を解決するための手段】
【００３６】
前記課題を解決するために、本発明は、各ユーザが各アイテムを選択したか否かあるいは選択した頻度を示したアイテム選択情報を、前記ユーザと前記アイテムに関する行列情報として扱ってクラスタリングするために、所定のユーザクラス割り当て確率式に基づき、前記行列情報における前記ユーザのそれぞれを複数のユーザクラスにクラス分けし、所定のアイテムクラス割り当て確率式に基づき、前記行列情報における前記アイテムのそれぞれを複数のアイテムクラスにクラス分けし、前記ユーザクラスと前記アイテムクラスとの組み合わせによって一意に特定されるユーザ・アイテムブロックごとに、確率モデル上で当該ユーザクラスのユーザが当該アイテムクラスのアイテムを選択する仮の確率である仮選択確率を所定のアイテム選択確率式に基づいて与え、前記所定のユーザクラス割り当て確率式、前記所定のアイテムクラス割り当て確率式、および、前記所定のアイテム選択確率式から算出される前記行列情報の事後確率の最大化を図ることで、前記行列情報を前記ユーザ単位および前記アイテム単位の両方でクラスタリングする共クラスタリング装置であって、前記した各ユーザクラスに対して各アイテムクラスに関する所定のアイテムクラス指定確率を与え、前記した各アイテムクラスに対して各ユーザクラスに関する所定のユーザクラス指定確率を与え、前記所定のアイテム選択確率式は、前記ユーザ・アイテムブロックごとの、前記所定のアイテムクラス指定確率と前記所定のユーザクラス指定確率との乗算値または乗算値に基づく値として前記仮選択確率を算出する式であり、前記アイテム選択情報と前記行列情報とを格納する記憶部と、最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記ユーザの所属するユーザクラスを、前記所定のユーザクラス割り当て確率式と前記仮選択確率とに基づいて更新するユーザクラス更新部と、最新の前記行列情報の入力を受け付け、前記行列情報における１つ以上の前記アイテムの所属するアイテムクラスを、前記所定のアイテムクラス割り当て確率式と前記仮選択確率とに基づいて更新するアイテムクラス更新部と、最新の前記行列情報に基づいて、前記行列情報の事後確率を算出する共クラスタリング結果評価部と、を備える。
【００３７】
かかる発明によれば、所定のアイテム選択確率式が、ユーザ・アイテムブロックごとの、所定のアイテムクラス指定確率と所定のユーザクラス指定確率との乗算値または乗算値に基づく値として仮選択確率を算出する式であり、所定のユーザクラス割り当て確率式と仮選択確率とに基づいてユーザクラスを更新し、所定のアイテムクラス割り当て確率式と仮選択確率とに基づいてアイテムクラスを更新し、最新の行列情報に基づいて行列情報の事後確率を算出することで、購買履歴データのような欠損値を含んだデータに、より適した生成プロセス（確率モデル）に基づいて、ユーザとアイテムを共クラスタリングすることができる。
【００３８】
また、本発明は、所定条件を満たすまで、前記ユーザクラス更新部、前記アイテムクラス更新部および前記共クラスタリング結果評価部による各ステップを繰り返させ、前記所定条件を満たしたとき、最新の前記行列情報に基づいた前記ユーザと前記アイテムに関する共クラスタリングの結果を前記記憶部に格納する共クラスタリング終了判定部、をさらに備えることが望ましい。
【００３９】
かかる発明によれば、所定条件を満たしたとき、最新の行列情報に基づいたユーザとアイテムに関する共クラスタリングの結果を記憶部に格納することで、共クラスタリングを適切なタイミングで終了させることができる。
【００４０】
また、本発明は、前記ユーザクラス更新部が、最新の前記行列情報から、更新する前記ユーザを１つ選び、その選んだ前記ユーザを移行させる先となる既存および新規の前記ユーザクラスのそれぞれの移行確率を算出し、当該それぞれの移行確率にしたがって当該ユーザを移行させる先の前記ユーザクラスを決定し、当該決定に基づいて前記ユーザクラスに関する情報を更新することが望ましい。
【００４１】
かかる発明によれば、移行確率にしたがって、ユーザを移行させる先のユーザクラスを決定することで、共クラスタリングがデッドロック（不適切な膠着状態）に陥る事態を回避することができる。
【００４２】
また、本発明は、前記アイテムクラス更新部が、最新の前記行列情報から、更新する前記アイテムを１つ選び、その選んだ前記アイテムを移行させる先となる既存および新規の前記アイテムクラスのそれぞれの移行確率を算出し、当該それぞれの移行確率にしたがって当該アイテムを移行させる先の前記アイテムクラスを決定し、当該決定に基づいて前記アイテムクラスに関する情報を更新することが望ましい。
【００４３】
かかる発明によれば、移行確率にしたがって、アイテムを移行させる先のアイテムクラスを決定することで、共クラスタリングがデッドロック（不適切な膠着状態）に陥る事態を回避することができる。
【００４４】
また、本発明に係る共クラスタリングプログラムは、前記した共クラスタリング装置を構成するコンピュータに実行させることを特徴とする。このような構成により、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【００４５】
また、本発明に係るコンピュータに読み取り可能な記録媒体は、前記した共クラスタリングプログラムが記録されたことを特徴とする。このような構成により、この記録媒体を装着されたコンピュータは、この記録媒体に記録されたプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００４６】
本発明によれば、購買履歴データのような欠損値を含んだデータに、より適した生成プロセス（確率モデル）に基づいて、ユーザとアイテムを共クラスタリングすることができる。
【発明を実施するための最良の形態】
【００４７】
以下、図面を参照（言及図以外の図も適宜参照）して、本発明を実施するための最良の形態（以下、「実施形態」という。）について詳細に説明する。まず、理解を助けるため、本実施形態のデータ生成プロセスについて説明し、その後、共クラスタリング装置について説明する。
【００４８】
＜データ生成プロセス＞
本実施形態では、ＩＲＭが仮定するデータ生成プロセスとは異なるデータ生成プロセスを仮定する。図９は、本実施形態において仮定するデータ生成プロセスの説明図である。
【００４９】
（本実施形態のプロセス１）
[１−１]ユーザ全体を、複数のユーザクラスに分割する。すなわち、まず、複数のユーザクラスの集合（ユーザクラス集合）を生成し、各ユーザはユーザクラス（のひとつ）ｋを選択し、そこに所属（帰属）する。
[１−２]アイテム全体を、複数のアイテムクラスに分割する。すなわち、まず、複数のアイテムクラスの集合（アイテムクラス集合）を生成し、各アイテムは、アイテムクラス（のひとつ）ｓを選択し、そこに所属（帰属）する。
なお、本実施形態のプロセス１は、前記したＩＲＭのプロセス１とまったく同じである。
【００５０】
（本実施形態のプロセス２）
[２−１]各ユーザクラスに対し、各アイテムクラスのうちどのクラスを選択（指定）しやすいか、という確率（アイテムクラス指定確率）を割り当てる。すなわち、各ユーザクラスｋには、アイテムクラス上の多項分布がひとつ割り当てられる。これはアイテムクラス数をＳとすると、ΣＳｓ＝１θｋ,ｓ＝１となるｓ個の非負実数θｋ,ｓ（≧０）を割り当てることに相当する。ここで、θｋ,ｓは、ユーザクラスｋに属するユーザにとって、アイテムクラスｓを選択（指定）する確率であり、サイコロに例えると、ｓという目の出る確率に対応する。
【００５１】
[２−２]同様に、各アイテムクラスに対し、各ユーザクラスのうちどのクラスを選択（指定）しやすいか、という確率（ユーザクラス指定確率）を割り当てる。すなわち、各アイテムクラスsには、ユーザクラス上の多項分布がひとつ割り当てられる。これはユーザクラス数をＫとすると、ΣＫｋ＝１φｓ,ｋ＝１となるＫ個の非負実数φｓ,ｋ（≧０）を割り当てることに相当する。φｓ,ｋは、アイテムクラスｓに属するユーザにとって、ユーザクラスｋを選択（指定）する確率である。
【００５２】
[２−３]各ユーザは、それが帰属するユーザクラスが持つアイテムクラス指定確率に基づいてアイテムクラスを選択（指定）し、各アイテムは、それが帰属するアイテムクラスが持つユーザクラス指定確率に基づいてユーザクラスを選択（指定）する。その結果、両者が一致したときに、該当するユーザは該当するアイテムを購入する、と考える（みなす）。
本実施形態のプロセス２は、前記したＩＲＭのプロセス２と大きく異なる。
【００５３】
ＩＲＭの場合と同様に、本実施形態では、与えられた購買履歴データ（アイテム選択情報）が、前記プロセスを表現した確率モデルに基づいて生成されたものとみなし、データを共クラスタリングする。具体的には、ＩＲＭと同様に、ユーザとアイテムをランダムにクラスタリングした状態からユーザの帰属ユーザクラスとアイテムの帰属アイテムクラスの各々を逐次的に更新していくことにより、共クラスタリング結果を得る。ここで、ＩＲＭと同様に、本実施形態においても、与えられたデータからクラス数を統計的学習の枠組みで自動的に決定できる。
【００５４】
次に、本実施形態が仮定する確率モデルと共クラスタリング結果の評価式について説明する。ＩＲＭの場合と同様、まず、以下がデータとして観測される量である。
・ユーザ数はＮ、アイテム数はＭである。
・行列Ｒは購買履歴データを表し、Ｎ×Ｍ行列Ｒの（ｉ,ｊ）要素Ｒｉ,ｊはユーザｉ（ｉ＝１,２,…,Ｎ）がアイテムｊ（ｊ＝１,２,…,Ｍ）を購入していた場合に「１」、購入していない場合に「０」をとるものとする。
【００５５】
これらが得られた下で、以下のような確率モデルを仮定する。
（ユーザクラス割り当ての事前確率、アイテムクラス割り当ての事前確率）
Ｐ（Ｚ;α）,Ｐ（Ｗ;β）については、ＩＲＭの場合とまったく同じであり、式（１）,（２）をそのまま用いる。
（行列Ｒの出現確率）
Ｚ,Ｗ,Θ,Φが与えられた下での、観測データであるＲの出現確率は式（１３）のように表現できる。
【数８】
0004934058.tif 000009
【００５６】
この式（１３）は、Ｒが与えられた下での、Θ、Φの「良さ」(尤度)である。この式（１３）は、本実施形態の特徴の１つであり、ＩＲＭの対応する式（３）と大きく違っている。ここでは、ユーザクラスｚｉとアイテムクラスｗｊが、互いに同じアイテムクラスｗｊ,ユーザクラスｚｉを選択（指定）したときのみ購入すると仮定するというプロセスが、式（１３）（アイテム選択確率式）中の（θｚｉ,ｗｊφｗｊ,ｚｉ）Ｒｉ,ｊに反映されている。
【００５７】
この「（θｚｉ,ｗｊφｗｊ,ｚｉ）Ｒｉ,ｊ」において、「θｚｉ,ｗｊ」は、ユーザクラスｚｉに属するユーザがアイテムクラスｗｊを選択（指定）する確率（アイテムクラス指定確率）である。また、「φｗｊ,ｚｉ」は、アイテムクラスｗｊに属するアイテムがユーザクラスｚｉを選択（指定）する確率（ユーザクラス指定確率）である。したがって、このモデルにおいて、「θｚｉ,ｗｊφｗｊ,ｚｉ」は、ユーザクラスｚｉに属するユーザがアイテムクラスｗｊに属するアイテムを購入する確率（仮選択確率）となる。
【００５８】
そして、「Ｒｉ,ｊ」は、「購入する」ときに「１」となり、「購入しない」ときに「０」となる数値である。したがって、「（θｚｉ,ｗｊφｗｊ,ｚｉ）Ｒｉ,ｊ」の値は、「購入する」ときに「（θｚｉ,ｗｊφｗｊ,ｚｉ）」（「θｚｉ,ｗｊ」と「φｗｊ,ｚｉ」との乗算値）の値がそのまま残り、「購入しない」ときに「１」になる（「０」以外の数値の０乗は「１」であるので。また、「０」の「０」乗は便宜上「１」と扱えばよい）。つまり、「（θｚｉ,ｗｊφｗｊ,ｚｉ）Ｒｉ,ｊ」のすべての積をとった式（１３）は、このモデルにおける、観測データである行列Ｒの出現確率となる。
【００５９】
なお、仮選択確率としては、前記した乗算値そのものでなくても、乗算値の累乗や累乗根など、乗算値に基づいて算出された値を採用してもよい。
【００６０】
このようにして行列Ｒの出現確率を算出することで、Ｒｉ,ｊ＝１（購入する）となる要素に比べてＲｉ,ｊ＝０（購入しない）となる要素数が圧倒的に多い場合や、欠損値を含んだ購買履歴データの場合などにも適するデータ生成プロセスを実現することができる。
【００６１】
（ユーザクラスｋに属するユーザがアイテムクラスｓを選択（指定）する確率）
Θ＝｛θｋ,ｓ｜ｋ＝１,２,…,Ｋ,  ｓ＝１,２,…,Ｓ｝（ただし、θｋ,ｓ≧０,ΣＳｓ＝１θｋ,ｓ＝１）の事前確率（分布）としては、式（１４）のようなディリクレ分布を用いる。
【数９】
0004934058.tif 000010
ただし、以下、簡単のためγｋ＝γとする。
【００６２】
（アイテムクラスｓに属するアイテムがユーザクラスｋを選択（指定）する確率）
同様に、Φ＝｛φｓ,ｋ｜ｓ＝１,２,…,Ｓ,  ｋ＝１,２,…,Ｋ｝（ただし、φｓ,ｋ≧０,ΣＫｋ＝１φｓ,ｋ＝１）の事前分布としては、式（１５）のようなディリクレ分布を用いる。
【数１０】
0004934058.tif 000011
ただし、以下、簡単のためηｓ＝ηとする。
【００６３】
前記した式（１４）,（１５）が、ＩＲＭにおける式（４）に対応している。以上が、本実施形態が仮定する確率モデルである。
【００６４】
ＩＲＭの場合と同様、ＺとＷの事後確率である式（５）が最大となる共クラスタリング結果を求めることを考える。これを計算するため、まず、本実施形態における確率モデル(購買履歴データの同時分布)は式（１６）,（１７）のように表現できる。
【数１１】
0004934058.tif 000012
ここで、Θ＝｛θｋ,ｓ｜ｋ＝１,２,…,Ｋ,  ｓ＝１,２,…,Ｓ｝,Φ＝｛φｓ,ｋ｜ｓ＝１,２,…,Ｓ,  ｋ＝１,２,…,Ｋ｝はそれぞれ多項分布のパラメータを表し、また、a、β、γ、ηはハイパーパラメータ(定数)を表す。
【００６５】
Θ、Φの事前分布として、多項分布の共役事前分布である、ディリクレ分布を用いたことによって、実際にはΘ、Φは式（１８）,（１９）のように積分消去することができる。すなわち、式（１６）の左辺と式（１７）の両辺をΘとΦについて積分し、その後、式（１８）の積分を実行すると、式（１９）のようにΘ、Φが消えることになる。
【数１２】
0004934058.tif 000013
【００６６】
したがって、この積分は解析的に解くことができ、陽にΘ、Φを考える必要はない。前記積分を実際に実行して、具体的に代入すると、ＺとＷの事後確率は、式（２０）,（２１）のようになる。
【数１３】
0004934058.tif 000014
【００６７】
なお、ｌ（ｋ,ｓ）は、ユーザクラスｋに所属するユーザがアイテムクラスｓに所属するアイテムを購入した回数を表す。すなわち、その回数は式（２２）の通りである。
【数１４】
0004934058.tif 000015
ただし、δ(ｘ)はｘが真の場合に「１」、それ以外に「０」となる関数(デルタ関数)とする。
【００６８】
本実施形態において、共クラスタリングを行うということは、式（２１）を最大化するようなＺとＷを求めることと等価である。
【００６９】
＜共クラスタリング装置＞
次に、本実施形態の共クラスタリング装置について説明する。なお、本実施形態では、サンプリングアルゴリズムを用いる。図１は、本実施形態に係る共クラスタリング装置の構成を模式的に示す機能ブロック図である。共クラスタリング装置１００は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、入出力インタフェース等から構成されるコンピュータ装置である。共クラスタリング装置１００は、図１に示すように、演算手段１、記憶手段２（記憶部）、キーボードやマウスなどの入力手段３、液晶表示機などの出力手段４を備え、それらがバスライン５で接続されている。
【００７０】
演算手段１は、前処理部１１、初期化部１２、ユーザクラス更新部１３、アイテムクラス更新部１４、共クラスタリング結果評価部１５、共クラスタリング終了判定部１６、および、動作領域であるメモリ１７を備えている。
記憶手段２は、購買履歴データ（行列情報）を格納する購買履歴ＤＢ２１、共クラスタリング結果を保存（格納）する共クラスタリング結果保存部２２、および、プログラム２３を備えている。
【００７１】
プログラム２３は、前処理２３１、初期化２３２、ユーザクラス更新２３３、アイテムクラス更新２３４、共クラスタリング結果評価２３５、および、共クラスタリング終了判定２３６の各機能プログラムを備えている。
演算手段１の前処理部１１，初期化部１２，ユーザクラス更新部１３，アイテムクラス更新部１４，共クラスタリング結果評価部１５および共クラスタリング終了判定部１６は、それぞれ、プログラム２３の前処理２３１，初期化２３２，ユーザクラス更新２３３，アイテムクラス更新２３４，共クラスタリング結果評価２３５および共クラスタリング終了判定２３６の各機能プログラムをメモリ１７に読み込んで展開することで実現される。
【００７２】
ここで、図２を参照して共クラスタリング装置１００の処理の流れについて説明し、その中で演算手段１の各部の動作について詳述する。図２は、共クラスタリング装置１００の処理の流れを示すフローチャートである。
【００７３】
まず、前処理部１１は前処理を行う（ステップＳ１）。具体的には、前処理部１１は、購買履歴ＤＢ２１に格納された購買履歴データから行列Ｒを作成する。ここで、Ｒの（ｉ,ｊ）要素を表すＲｉ,ｊは、ユーザｉがアイテムｊを購入していた場合に「１」、購入していない場合に「０」とする。また、ユーザ数をＮ、アイテム数をＭとする。
【００７４】
ステップＳ１の後、初期化部１２は初期化を行う（ステップＳ２）。具体的には、初期化部１２は、ユーザの仮の帰属ユーザクラスＺ＝｛zｉ｜ｉ＝１,２,…,Ｎ｝と、アイテムの仮の帰属アイテムクラスＷ＝｛ｗｊ｜ｊ＝１,２,…,Ｍ｝を適当に決定する。これにより、仮のユーザクラス数Ｋ、仮のアイテムクラス数Ｓも決定される。ここでは、例えば、ランダムに帰属クラスを割り当てる方法や、各データをそれぞれ別のクラス(その場合、ユーザクラス数Ｎ、アイテムクラス数Ｍとなる)とする方法などを用いる。
【００７５】
続いて、ユーザクラス更新部１３はユーザクラス更新を行う（ステップＳ３）。ステップＳ３について図３を参照して説明する。図３はステップＳ３の処理を細分化したフローチャートである。
【００７６】
ユーザクラス更新部１３は、まず、ユーザクラスを更新する対象となるユーザをランダムに１人選び、選んだユーザのインデックスをｉとする（ステップＳ３１：更新対象ユーザ選択）。次に、ユーザｉがユーザクラスｋ＊（∈｛１,２,…,Ｋ,Ｋ＋1｝）を選択する確率を算出し（ステップＳ３２：ユーザクラス帰属確率算出）、算出した確率に基づいてユーザｉの帰属ユーザクラスを決定する（ステップＳ３３：帰属ユーザクラス決定）。このように、（移行）確率に基づいてユーザの移行先ユーザクラスを決定することで、共クラスタリングがデッドロック（不適切な膠着状態）に陥る事態を回避することができる。
【００７７】
最後に、決定した帰属ユーザクラスによってｚｉを更新する（ステップＳ３４：ユーザクラス更新）。なお、このユーザクラス更新によって、空のユーザクラスが発生した場合は、そのユーザクラスが消去されるので、ユーザクラス数が減少することになる。また、逆に、このユーザクラス更新によって、新規のユーザクラスが発生した場合は、その分、ユーザクラス数が増加することになる。
【００７８】
ここで、ステップＳ３２について詳述する。ユーザｉがユーザクラスｋ＊を選択する確率（ユーザクラス割り当て確率式）は、式（２３）で表される。ただし、ｋ＊＝１,２,…,Ｋ,Ｋ＋1、である。
Ｐ（ｚｉ＝ｋ＊｜Ｒ,Ｚ−１,Ｗ；α,β,γ,η）  ・・・式（２３）
また、Ｚ−１＝｛z１,z２,…,zｉ-２,zｉ-１,zｉ＋１,zｉ＋２,…,zＮ-１,zＮ｝（Ｚからzｉを除いたもの）とすると、式（２３）を式（２４）,（２５）,（２６）のように表すことができる。
【数１５】
0004934058.tif 000016
【００７９】
ここで、ｋ＊∈｛１,２,…,Ｋ,Ｋ＋1｝であること、つまり、既存のＫ個のクラスに加えて、新たなＫ＋１番目のクラスを選ぶ確率も計算することに注意が必要である。ｋ＊が既存クラスである場合は式（２７）のように表現でき、ｋ＊が新規クラスである場合は式（２８）のように表現できる。
【００８０】
ｋ＊が既存クラスである場合:
【数１６】
0004934058.tif 000017
ｋ＊が新規クラスである場合：
【数１７】
0004934058.tif 000018
【００８１】
なお、ｎ−ｉ,ｋはユーザｉを購買履歴データから取り除いたときのユーザクラスｋに所属するユーザ数を表し、ｌ（ｋ,ｓ）は、式（２２）で定義されたように、ユーザクラスｋに所属するユーザがアイテムクラスｓに所属するアイテムを購入した回数を表す。また、ｌ−ｉ（ｋ,ｓ）はユーザｉを購買履歴データから取り除いたときのｌ（ｋ,ｓ）、ｌ＋ｉ（ｋ,ｓ）はユーザｉをユーザクラスｋに割り当てたときのｌ（ｋ,ｓ）を表す。
【００８２】
図２に戻って説明を続けると、ステップＳ３の後、アイテムクラス更新部１４はアイテムクラス更新を行う（ステップＳ４）。ステップＳ４について図４を参照して説明する。図４はステップＳ４の処理を細分化したフローチャートである。
【００８３】
アイテムクラス更新部１４は、まず、アイテムクラスを更新する対象となるアイテムをランダムに１つ選び、選んだアイテムのインデックスをｊとする（ステップＳ４１：更新対象アイテム選択）。次に、アイテムｊがアイテムクラスｓ＊(∈｛１,２,…,Ｓ,Ｓ＋1｝)を選択する確率を算出し（ステップＳ４２：アイテムクラス帰属確率算出)、算出した確率に基づいてアイテムｊの帰属アイテムクラスを決定する（ステップＳ４３：帰属アイテムクラス決定)。このように、（移行）確率に基づいてアイテムの移行先アイテムクラスを決定することで、共クラスタリングがデッドロック（不適切な膠着状態）に陥る事態を回避することができる。
【００８４】
最後に、決定した帰属アイテムクラスによってｗｊを更新する(ステップＳ４４：アイテムクラス更新)。なお、このアイテムクラス更新によって、空のアイテムクラスが発生した場合は、そのアイテムクラスが消去されるので、アイテムクラス数が減少することになる。また、逆に、このアイテムクラス更新によって、新規のアイテムクラスが発生した場合は、その分、アイテムクラス数が増加することになる。
【００８５】
ここで、ステップＳ４２について詳述する。アイテムｊがアイテムクラスｓ＊を選択する確率（アイテムクラス割り当て確率式）は、式（２９）と表される。ただし、ｓ＊＝１,２,…,Ｓ,Ｓ＋1、である。
Ｐ（ｗｊ＝ｓ＊｜Ｒ,Ｚ,Ｗ−ｊ；α,β,γ,η）  ・・・式（２９）
【００８６】
また、Ｗ−ｊ＝｛ｗ１,ｗ２,…,ｗｊ-２,ｗｊ-１,ｗｊ＋１,ｗｊ＋２,…,ｗＮ-１,ｗＮ｝（Ｗからｗｊを除いたもの）であり、Ｒｊ＝｛Ｒ１ｊ,Ｒ２ｊ,…,ＲＮｊ｝とおくと、式（２９）を式（３０）,（３１）,（３２）のように表すことができる。
【数１８】
0004934058.tif 000019
【００８７】
ここで、ユーザクラス更新部の場合と同様、ｓ＊∈｛１,２,…,Ｓ,Ｓ＋1｝であり、既存のＳ個のクラスに加えて、新たなＳ＋１番目のクラスを選ぶ確率も計算する。ｓ＊が既存クラスである場合は式（３３）のように表現でき、ｓ＊が新規クラスである場合は式（３４）のように表現できる。
【００８８】
ｓ＊が既存クラスである場合:
【数１９】
0004934058.tif 000020
ｓ＊が新規クラスである場合：
【数２０】
0004934058.tif 000021
【００８９】
ここで、ｍ−ｊ,ｓはアイテムｊを購買履歴データから取り除いたときのアイテムクラスｓに所属するアイテム数を表し、ｌ−ｊ（ｋ,ｓ）はアイテムｊを購買履歴データから取り除いたときのｌ（ｋ,ｓ）、ｌ＋ｊ（ｋ,ｓ）はアイテムｊをクラスｋに割り当てたときのｌ（ｋ,ｓ）を表す。
【００９０】
図２に戻って説明を続けると、ステップＳ４の後、共クラスタリング結果評価部１５は、共クラスタリング結果評価、つまり、ユーザクラスタリング結果Ｚとアイテムクラスタリング結果Ｗの評価を行う（ステップＳ５）。評価には、ユーザクラスタリング結果Ｚとアイテムクラスタリング結果Ｗの事後確率を、式（３５）,（３６）から算出し、用いる。
式（３５）,（３６）により算出される値が大きいほど、良いクラスタリング結果であるとみなせる。
【数２１】
0004934058.tif 000022
【００９１】
ステップＳ５の後、共クラスタリング終了判定部１６は、共クラスタリング終了判定、つまり、ユーザクラスの更新とアイテムクラスの更新を終了させるか否かの判定を行う（ステップＳ６）。例えば、共クラスタリング結果の評価値（Ｚ,Ｗの事後確率）に変化がなくなったところで終了させればよい。また、予め指定しておいた更新回数を超えたところで終了させてもよい。あるいは、それらの組み合わせや、その他の条件によりこの終了判定を行ってもよい。
【００９２】
ステップＳ６で「継続（終了しない）」と判定された場合、ステップＳ３に戻る。
ステップＳ６で「終了」と判定された場合、共クラスタリング終了判定部１６は共クラスタリング結果（Ｚ,Ｗ）を共クラスタリング結果保存部２２に保存する（ステップＳ７）。このステップＳ６により、共クラスタリングを適切なタイミングで終了させることができる。
【００９３】
このように、本実施形態の共クラスタリング装置１００によれば、購買履歴データのような欠損値を含んだデータに、より適した生成プロセス（確率モデル）に基づき、従来技術と比べて、ユーザとアイテムを良好に共クラスタリングすることができる。特に、従来法であるＩＲＭとの違いをまとめると、以下のようになる。
【００９４】
ＩＲＭではユーザがアイテムを購入する事象と購入しない事象の両方を対等に考慮し、式（３）で表されるような、ベルヌーイ分布に基づきユーザとアイテムを双方向にクラスタリングしている。
【００９５】
一方、本実施形態では、ユーザはアイテムを購入する／しない、ではなくユーザとアイテムは互いに選択（指定）しあい、互いが一致したときにアイテムを購入する、と想定（仮定）し、式（１３）で表現されるような多項分布にしたがってユーザとアイテムが互いに選択しあう、と考えている。
【００９６】
別の表現を用いれば、ＩＲＭがユーザ・アイテムブロックにおけるベルヌーイ分布に基づきユーザとアイテムを双方向にクラスタリングするのに対して、本実施形態は、ユーザクラス／アイテムクラス上での多項分布に基づきユーザとアイテムを双方向にクラスタリングする。
【００９７】
ユーザがアイテムを購入する事象（ユーザとアイテムが互いに選択（指定）しあう事象）のみを考慮することによって、ユーザがアイテムを購入しない事象を考慮する必要がなくなる。これにより、購買履歴データにおける欠損部分、つまり、今は購入していないが将来購入されるアイテム箇所、に対処可能となる。
【００９８】
なお、共クラスタリング装置１００を構成するコンピュータに実行させる共クラスタリングプログラムを作成し、コンピュータにインストールすることにより、コンピュータは、その共クラスタリングプログラムに基づいた各機能を実現することができる。また、その共クラスタリングプログラムをＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）等の種々の記録媒体に記録することができる。
【００９９】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、本発明を適用する対象となる購買履歴データは、行列Ｒの各要素が、「０」と「１」などの二値で示されたものでなくても、選択する頻度を表す「０」以上の整数で示されたものであってもよい。その場合、行列Ｒの各要素は、「購入した／しない」ではなく、「購入した回数」を示すことになり（「０」は購入していないことを示す）、各確率計算時等にその購入した回数を考慮すればよい。
【０１００】
また、本発明は、購買履歴データ以外にも、ユーザのＷｅｂページへのアクセス履歴データ（Ｗｅｂページがアイテムに相当）、文書・単語データ（文書がユーザ、その文書に現れる単語がアイテムに相当）、論文・著者データ（論文がユーザ、その論文を執筆した著者がアイテムに相当）など多種のデータに適用できる。つまり、特許請求の範囲において、「ユーザ」は必ずしも「人」を指すわけではなく、また、「アイテム」は必ずしも「物」を指すわけではなく、適宜それら以外のものを指すと解釈してよい。
【０１０１】
また、本実施形態のモデルに基づいて共クラスタリングをする際、前記した説明ではサンプリングによる方法を示したが、変分ベイズアルゴリズムなどの他の学習アルゴリズムによる方法を採用することもできる。
さらに、より評価値の大きい共クラスタリング結果Ｚ,Ｗを得るため（質の悪い局所解に陥るのを防ぐため）、ユーザクラス・アイテムクラス更新の間に、それぞれのクラス割り当てＺ,Ｗを確率的に変化させる操作などを加えることも可能である。
【０１０２】
また、複数のユーザまたはアイテムを同時に他のクラスに変更するようにしてもよい。
その他、ハードウェア、ソフトウェアの具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【０１０３】
＜実施例＞
次に、実データ（購買履歴データ）に対して、「本実施形態の共クラスタリング装置１００による共クラスタリング」を実行した場合と、「ＩＲＭ（従来技術）による共クラスタリング」を実行した場合との比較結果について説明する。
【０１０４】
（使用したデータ）
実データとして、映画に対してユーザが実際に評価した履歴からなるデータ“MovieLens”を用いた。評価値は「１」,「２」,「３」,「４」,「５」の５つの値をとる。そして、ユーザが評価を行った映画をユーザが購入したアイテムとみなし、ユーザが評価を行っていない映画をユーザが購入していないアイテムとみなし、ユーザ数943、アイテム数1682の購買履歴データを作成した。図５は、その購買履歴データの行列Ｒを示す図である。図５において、縦軸がユーザを表し、横軸がアイテムを表し、また、黒い点はＲｉ,ｊ＝１（商品を購入したこと）、白い点はＲｉ,ｊ＝０（商品を購入していないこと）をそれぞれ表す（図６、図７についても同様）。
【０１０５】
（実施方法）
各手法におけるハイパーパラメータ値は、以下のとおりである。
本実施形態:α＝β＝0.1,γ＝η＝0.01（ｋ＝１,２,…,Ｋ,  ｓ＝１,２,…,Ｓ）
ＩＲＭ:α＝β＝0.1,γ＝η＝0.01（ｋ＝１,２,…,Ｋ,  ｓ＝１,２,…,Ｓ）
【０１０６】
また、初期化部１２においては、ユーザとアイテムをそれぞれ１００クラスにランダムに分けてＺ,Ｗを初期化し、共クラスタリング終了判定部１６においては、10000回連続で評価値（Ｚ,Ｗの事後確率（分布））が更新されなかったときに共クラスタリングを終了させた。
【０１０７】
（実施結果）
購買履歴データＲに対して、ＩＲＭと本実施形態による手法とをそれぞれ適用した結果を定性的に比較および評価する。図６は、ＩＲＭの手法の適用結果を示す図である。図７は、本実施形態の手法の適用結果を示す図である。
図６および図７において、共クラスタリングによって得られたユーザクラス、アイテムクラスごとにユーザとアイテムをソートしており、クラスの区切りを実線で表している。また、左上から要素数の大きい順に各クラスを並べている。
【０１０８】
各手法により得られたユーザクラス数／アイテムクラス数は、ＩＲＭの手法において39/54、本実施形態の手法において33/57であった。どちらの手法によってもユーザ・アイテムブロック単位で購買履歴（黒の部分）が密集している結果が得られることが分かる。ただし、ＩＲＭの手法では、購入履歴の少ないユーザ・アイテム群を一括りにして巨大なユーザ・アイテムブロック（図６の左上部分）を構成してしまっており、購入履歴データの大部分を占めるＲｉ,ｊ＝０の影響を受けていることが分かる。これに対して、本実施形態の手法では、ＩＲＭの手法に比べてＲｉ,ｊ＝１（黒）の部分が図７に示すように全体的に分布しており、Ｒｉ,ｊ＝０の影響をあまり受けていないことが確認できる。
【０１０９】
ここで、図８は、本実施形態の手法により得られたアイテムクラスごとの映画タイトルの一部を示す図である。図８に示すように、クラス６（アイテムクラス６）はヒット作、クラス２９（アイテムクラス２９）はホラー映画、クラス３５（アイテムクラス３５）は子供・家族向けの映画のアイテムクラスであることが分かり、本実施形態の手法によって特徴のあるアイテムクラスが得られていることが分かる。
【０１１０】
ＩＲＭの手法では、ここまで精度の高いクラスタリング結果は得られない。改めて説明すると、例えば、図６に示すように、ＩＲＭの手法では、Ｒｉ,ｊ＝０（購入しない）の影響を強く受け、左端に大きくて白いアイテムクラス１の領域ができてしまい、また、そのアイテムクラス１の領域には、複数のジャンルにまたがる雑多な映画のタイトルが含まれている（具体的なタイトル名は省略）。そして、ＩＲＭの手法でもっとも問題となるのは、この左端の大きくて白いアイテムクラスの領域の発生である。この領域は、アクセス数の少ない映画の寄せ集め領域になっているので、いろいろなジャンルの映画が混在してしまう。一方、図７に示すように、本実施形態の手法では、そのような大きくて白いアイテムクラスの領域は発生していない。
【図面の簡単な説明】
【０１１１】
【図１】本実施形態に係る共クラスタリング装置の構成を模式的に示す機能ブロック図である。
【図２】共クラスタリング装置の処理の流れを示すフローチャートである。
【図３】ステップＳ３の処理を細分化したフローチャートである。
【図４】ステップＳ４の処理を細分化したフローチャートである。
【図５】実データ（購買履歴データ）の行列Ｒを示す図である。
【図６】ＩＲＭの手法の適用結果を示す図である。
【図７】本実施形態の手法の適用結果を示す図である。
【図８】本実施形態の手法で得られたアイテムクラスごとの映画タイトルの一部を示す図である。
【図９】本実施形態において仮定するデータ生成プロセスの説明図である。
【図１０】購買履歴データの共クラスタリングの例を示す図である。
【図１１】ＩＲＭのデータ生成プロセスの説明図である。
【符号の説明】
【０１１２】
１      演算手段
２      記憶手段
１１    前処理部
１２    初期化部
１３    ユーザクラス更新部
１４    アイテムクラス更新部
１５    共クラスタリング結果評価部
１６    共クラスタリング終了判定部
２１    購買履歴ＤＢ
２２    共クラスタリング結果保存部
２３    プログラム
１００  共クラスタリング装置
【図１】
0004934058.tif 000023
【図２】
0004934058.tif 000024
【図３】
0004934058.tif 000025
【図４】
0004934058.tif 000026
【図５】
0004934058.tif 000027
【図６】
0004934058.tif 000028
【図７】
0004934058.tif 000029
【図８】
0004934058.tif 000030
【図９】
0004934058.tif 000031
【図１０】
0004934058.tif 000032
【図１１】
0004934058.tif 000033