(57)【特許請求の範囲】
【請求項１】
複数のドメインの各々のオブジェクト間の関係を示す関係データの観測値に基づいて、前記ドメイン毎にオブジェクトのクラスタリングを実行するクラスタリング装置であって、
前記複数のドメインの各々のオブジェクトｉ，ｊ間の関係を示す観測値ｘi,j、前記複数のドメインの各々の潜在クラスタ数Ｋ1,Ｋ2、各オブジェクトｉが所属するクラスタを示すクラスタ割り当て変数ｚ1,i、各オブジェクトｊが所属するクラスタを示すクラスタ割り当て変数ｚ2,j、各オブジェクトｉに対するクラスタリングの必要性の有無を示すrelevance変数ｒ1,i、各オブジェクトｊに対するクラスタリングの必要性の有無を示すrelevance変数ｒ2,j、及びハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を記憶する記憶手段と、
前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記relevance変数ｒ1,i、ｒ2,jの各々の初期値を設定して前記記憶手段に記憶する初期設定手段と、
前記記憶手段から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、及び前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jをサンプリングにより算出し、前記潜在クラスタ数Ｋ1,Ｋ2を決定し、前記算出した前記relevance変数ｒ1,i、ｒ2,j及び前記クラスタ割り当て変数ｚ1,i、ｚ2,j、並びに前記決定した前記潜在クラスタ数Ｋ1,Ｋ2によって、前記記憶手段に記憶してある前記relevance変数ｒ1,i、ｒ2,j、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記潜在クラスタ数Ｋ1,Ｋ2を更新し記憶する隠れ変数更新手段と、
前記隠れ変数更新手段による更新を、所定の解析終了条件を満足するまで繰り返す解析終了条件判定手段と、
を含むクラスタリング装置。
【請求項２】
前記隠れ変数更新手段は、
クラスタリングの必要性がないことを示すｒ1,i＝０であって、かつ、クラスタが割り当てられないことを示すｚ1,i＝０であるパターン、クラスタリングの必要性があることを示すｒ1,i＝１であって、かつ、ｚ1,i＝１，・・・，Ｋ1の何れかであるＫ1個のパターン、及びｒ1,i＝１であって、かつ、新たなクラスタが割り当てられることを示すｚ1,i＝Ｋ1＋１であるパターンからなるＫ1＋２個のパターンの各々について、算出対象のオブジェクトｉに関する前記観測値ｘi,jの分布が、前記パターンとなる他のオブジェクトi’に関する前記観測値ｘi’,jの分布にどの程度似ているかに基づく前記Ｋ1＋２個のパターンの各々の第１確率と、オブジェクトi’全体でのｒ1,i’＝０となるオブジェクトi’の割合、ｒ1,i’＝１となるオブジェクトi’の割合、及びｒ1,i’＝１となるオブジェクトi'全体における各クラスタのサイズの割合に基づくＫ1＋２個のパターンの各々の第２確率とに基づいて計算される前記Ｋ1＋２個のパターンの各々となる確率に従って、前記算出対象のオブジェクトｉの各々について前記Ｋ1＋２個のパターンの何れかをサンプリングにより決定して、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,Iを算出し、
クラスタリングの必要性がないことを示すｒ2,j＝０であって、かつ、クラスタが割り当てられないことを示すｚ2,j＝０であるパターン、クラスタリングの必要性があることを示すｒ2,j＝１であって、かつ、ｚ2,j＝１，・・・，Ｋ2の何れかであるＫ2個のパターン、及びｒ2,j＝１であって、かつ、新たなクラスタが割り当てられることを示すｚ2,j＝Ｋ2＋１であるパターンからなるＫ2＋２個のパターンの各々について、算出対象のオブジェクトｊに関する前記観測値ｘi,jの分布が、前記パターンとなる他のオブジェクトj’に関する前記観測値ｘi,j’の分布にどの程度似ているかに基づく前記Ｋ2＋２個のパターンの各々の第３確率と、オブジェクトj’全体でのｒ2,j’＝０となるオブジェクトj’の割合、ｒ2,j’＝１となるオブジェクトj’の割合、及びｒ2,j’＝１となるオブジェクトj’全体における各クラスタのサイズの割合に基づくＫ2＋２個のパターンの各々の第４確率とに基づいて計算される前記Ｋ2＋２個のパターンの各々となる確率に従って、前記算出対象のオブジェクトｊの各々について前記Ｋ2＋２個のパターンの何れかをサンプリングにより決定して、各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jを算出する請求項１記載のクラスタリング装置。
【請求項３】
前記記憶手段は、補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを更に記憶し、
前記隠れ変数更新手段は、更に、前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを算出して、前記記憶手段に記憶してある前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを更新し、
前記記憶手段から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑ、前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、ハイパーパラメータα1をサンプリングにより算出し、ハイパーパラメータα2をサンプリングにより算出し、ハイパーパラメータａ、ｂをサンプリングにより算出し、Ｋ1個のクラスタ及びＫ2個のクラスタの各組み合わせに対するハイパーパラメータｃk,l、ｄk,lをサンプリングにより算出し、ハイパーパラメータｅ1、f1をサンプリングにより算出し、ハイパーパラメータｅ2、f2をサンプリングにより算出し、前記算出した前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2によって前記記憶手段に記憶してある前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を更新し記憶するハイパーパラメータ更新手段を更に含み、
前記解析終了条件判定手段は、前記隠れ変数更新手段及び前記ハイパーパラメータ更新手段による更新を任意の順番で実行する過程を、所定の解析終了条件を満足するまで繰り返す請求項１又は２記載のクラスタリング装置。
【請求項４】
複数のドメインの各々のオブジェクト間の関係を示す関係データの観測値に基づいて、前記ドメイン毎にオブジェクトのクラスタリングを実行するクラスタリング装置におけるクラスタリング方法であって、
前記クラスタリング装置は、前記複数のドメインの各々のオブジェクトｉ，ｊ間の関係を示す観測値ｘi,j、前記複数のドメインの各々の潜在クラスタ数Ｋ1,Ｋ2、各オブジェクトｉが所属するクラスタを示すクラスタ割り当て変数ｚ1,i、各オブジェクトｊが所属するクラスタを示すクラスタ割り当て変数ｚ2,j、各オブジェクトｉに対するクラスタリングの必要性の有無を示すrelevance変数ｒ1,i、各オブジェクトｊに対するクラスタリングの必要性の有無を示すrelevance変数ｒ2,j、及びハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を記憶する記憶部と解析部とを備え、
前記解析部は、
前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記relevance変数ｒ1,i、ｒ2,jの各々の初期値を設定して前記記憶部に記憶する初期設定ステップと、
前記記憶部から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、及び前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jをサンプリングにより算出し、前記潜在クラスタ数Ｋ1,Ｋ2を決定し、前記算出した前記relevance変数ｒ1,i、ｒ2,j及び前記クラスタ割り当て変数ｚ1,i、ｚ2,j、並びに前記決定した前記潜在クラスタ数Ｋ1,Ｋ2によって、前記記憶部に記憶してある前記relevance変数ｒ1,i、ｒ2,j、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記潜在クラスタ数Ｋ1,Ｋ2を更新し記憶する隠れ変数更新ステップと、
前記隠れ変数更新ステップによる更新を、所定の解析終了条件を満足するまで繰り返す解析終了条件判定ステップと、
を実行するクラスタリング方法。
【請求項５】
前記隠れ変数更新ステップは、
クラスタリングの必要性がないことを示すｒ1,i＝０であって、かつ、クラスタが割り当てられないことを示すｚ1,i＝０であるパターン、クラスタリングの必要性があることを示すｒ1,i＝１であって、かつ、ｚ1,i＝１，・・・，Ｋ1の何れかであるＫ1個のパターン、及びｒ1,i＝１であって、かつ、新たなクラスタが割り当てられることを示すｚ1,i＝Ｋ1＋１であるパターンからなるＫ1＋２個のパターンの各々について、算出対象のオブジェクトｉに関する前記観測値ｘi,jの分布が、前記パターンとなる他のオブジェクトi’に関する前記観測値ｘi’,jの分布にどの程度似ているかに基づく前記Ｋ1＋２個のパターンの各々の第１確率と、オブジェクトi’全体でのｒ1,i’＝０となるオブジェクトi’の割合、ｒ1,i’＝１となるオブジェクトi’の割合、及びｒ1,i’＝１となるオブジェクトi’全体における各クラスタのサイズの割合に基づくＫ1＋２個のパターンの各々の第２確率とに基づいて計算される前記Ｋ1＋２個のパターンの各々となる確率に従って、前記算出対象のオブジェクトｉの各々について前記Ｋ1＋２個のパターンの何れかをサンプリングにより決定して、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,Iを算出し、
クラスタリングの必要性がないことを示すｒ2,j＝０であって、かつ、クラスタが割り当てられないことを示すｚ2,j＝０であるパターン、クラスタリングの必要性があることを示すｒ2,j＝１であって、かつ、ｚ2,j＝１，・・・，Ｋ2の何れかであるＫ2個のパターン、及びｒ2,j＝１であって、かつ、新たなクラスタが割り当てられることを示すｚ2,j＝Ｋ2＋１であるパターンからなるＫ2＋２個のパターンの各々について、算出対象のオブジェクトｊに関する前記観測値ｘi,jの分布が、前記パターンとなる他のオブジェクトj’に関する前記観測値ｘi,j’の分布にどの程度似ているかに基づく前記Ｋ2＋２個のパターンの各々の第３確率と、オブジェクトj’全体でのｒ2,j’＝０となるオブジェクトj’の割合、ｒ2,j’＝１となるオブジェクトj’の割合、及びｒ2,j’＝１となるオブジェクトj’全体における各クラスタのサイズの割合に基づくＫ2＋２個のパターンの各々の第４確率とに基づいて計算される前記Ｋ2＋２個のパターンの各々となる確率に従って、前記算出対象のオブジェクトｊの各々について前記Ｋ2＋２個のパターンの何れかをサンプリングにより決定して、各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jを算出する請求項４記載のクラスタリング方法。
【請求項６】
前記記憶部は、補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを更に記憶し、
前記隠れ変数更新ステップは、更に、前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを算出して、前記記憶部に記憶してある前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑを更新し、
前記記憶部から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、前記補助変数ｎk,l、￣ｎk,l、ｍt,k、ｍ1,k、ｍ2,l、ｑ、￣ｑ、前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、ハイパーパラメータα1をサンプリングにより算出し、ハイパーパラメータα2をサンプリングにより算出し、ハイパーパラメータａ、ｂをサンプリングにより算出し、Ｋ1個のクラスタ及びＫ2個のクラスタの各組み合わせに対するハイパーパラメータｃk,l、ｄk,lをサンプリングにより算出し、ハイパーパラメータｅ1、f1をサンプリングにより算出し、ハイパーパラメータｅ2、f2をサンプリングにより算出し、前記算出した前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2によって前記記憶部に記憶してある前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を更新し記憶するハイパーパラメータ更新ステップを更に含み、
前記解析終了条件判定ステップは、前記隠れ変数更新ステップ及び前記ハイパーパラメータ更新ステップによる更新を任意の順番で実行する過程を、所定の解析終了条件を満足するまで繰り返す請求項４又は５記載のクラスタリング方法。
【請求項７】
請求項１〜請求項３の何れか１項に記載のクラスタリング装置を構成する各手段として、コンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、方法、及びプログラムに係り、特に、複数のドメインの各々のオブジェクト間の関係を示す関係データの観測値に基づいて、ドメイン毎にオブジェクトのクラスタリングを実行するクラスタリング装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
複数のオブジェクトの関係を表現した「関係データ」の解析は、顧客の購買情報（顧客×商品×店舗）、ソーシャルネットワークサービス(SNS)上の友達関係（ユーザ×ユーザ）、科学論文の引用・共著関係（著者×論文×引用論文）など、主にウェブを通じて収集される大量の実データの存在により大きな注目を集めている。
【０００３】
多くの関係データでは、あまりに大量のオブジェクトが存在して目視による完全な把握が不可能であるため、それらの関係性を簡潔に、かつ直観的に理解しやすい形で整理・表現する技術が必要とされている。特にその中でも、多数の関係情報を利用して、「似たような関係を持つオブジェクト集合」を発見する関係データ中のオブジェクトクラスタリング手法は多数の研究が報告されている(例えば、非特許文献１、２)。
【０００４】
それらの中でも、Infinite Relational Model (IRM) （非特許文献３参照）は、２オブジェクト間の関係データを行列として表現した際、行および列のインデックスを同時にクラスタリング可能である。例えば、（顧客×商品）で表現される購買履歴データの場合、行を顧客番号、列を商品番号として顧客による商品の購買履歴の有無を行列で表現できる。IRMは、この行列から似たような買い方をする顧客グループと、似たような売れ方をする商品グループとを抽出する。
【０００５】
また、バイクラスタリング(biclustering)と呼ばれる手法も同様の解析を行うことが可能である。中でもBayesian Clustered Tensor Factorization (BCTF)（非特許文献４参照）は、入手できる関係情報が複数種（例えば購買履歴の例では、購入履歴・お気に入り履歴など）の場合でもオブジェクトのクラスタリングが可能である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Erosheva, Fienberg, and Lafferty, “Mixedmembership model of sceientific publications”, PNAS, Vol. 101 (suppl 1), pp. 5２２0-5２２７, 2004.
【非特許文献２】Zhu, Yu and Gong, “Stochastic relational models for large-scale dyadic data using MCMC”, In Proc. NIPS, 2009.
【非特許文献３】Kemp, Tenenbaum, Griffiths, Yamada, and Ueda, “Learning systems of concepts with an infinite relational model”, In Proc. AAAI, 2006.
【非特許文献４】Sutskever, Salakhutdinov, and Tenenbaum, “Modelling relational data using Bayesian clustered tensor factorization”, In Proc. NIPS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明で解決する問題は、実際の関係データで頻繁に発生するデータのスパースネスの問題である。
【０００８】
これまで見たように、関係データの解析法として多くの手法が提案されてきたが、どの先行技術においてもこのスパースネスに対する対処法は検討されていなかった。ここでは、まずデータのスパースネスの問題を説明し、具体的にIRM法（上記の非特許文献３）の場合に、データスパースネスの問題を含んだデータを解析するとどのような悪影響が出るかを例示する。
【０００９】
実世界で収集される関係データの多くは非常にスパースである。例えば、（顧客×商品）の購買関係を表した購買履歴データでは、ごく少数のペアだけが「購入された」、すなわち関係がある、とされる。これは例えばSNS上の友達関係でも同じである。この状況でランダムな少数のノイズの情報が重畳すると、本来のデータが非常にスパースであるのでノイズの情報と「有意な」情報との見分けがつかなくなる。このため、データの解析結果、具体的にはオブジェクトのクラスタリングが困難になる。
【００１０】
これを具体的な実験例で示したのが図１３（Ａ）、（Ｂ）である。図１３（Ａ）は、ある会社での社員間のメールの送受信を表した観測データである。黒い点があると、それに対応する行の社員から、対応する列の社員へメールが送信されたことを示す。このデータをクラスタリングすることによって、各社員を少数のグループへ分割する。既存技術の１つであるIRM法（非特許文献３）を利用した結果を、図１３（Ｂ）に示す。ここで、図１３（Ｂ）中の縦横の線分は社員のグループ分けを表している。ここで、大きく問題が２つ生じている。第一に、一番左上の領域に着目すると、ほとんどの観測データはメールがなかったことを示している。しかし、これはデータがそもそもスパースであることから当然であり、このような関係クラスタが学習されても特に新しい知見を得ることができたとは言えない。第二に、右下の方向に着目すると、多数のグループ分けの線分が重なってしまっている。これは、ヒトの目で見て解釈できないほど小さなクラスタが大量にできていることを意味する。このままではせっかく解析してもせっかくの解析結果を人間が解釈することができない。
【００１１】
本発明は、上記の事情を鑑みてなされたもので、スパースネスのある関係データから、データ構造に関係のないオブジェクトを自動的に排除して、解析精度が高いクラスタリング結果を得ることができるクラスタリング装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の目的を達成するためにクラスタリング装置は、複数のドメインの各々のオブジェクト間の関係を示す関係データの観測値に基づいて、前記ドメイン毎にオブジェクトのクラスタリングを実行するクラスタリング装置であって、前記複数のドメインの各々のオブジェクトｉ，ｊ間の関係を示す観測値ｘi,j、前記複数のドメインの各々の潜在クラスタ数Ｋ1,Ｋ2、各オブジェクトｉが所属するクラスタを示すクラスタ割り当て変数ｚ1,i、各オブジェクトｊが所属するクラスタを示すクラスタ割り当て変数ｚ2,j、各オブジェクトｉに対するクラスタリングの必要性の有無を示すrelevance変数ｒ1,i、各オブジェクトｊに対するクラスタリングの必要性の有無を示すrelevance変数ｒ2,j、及びハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を記憶する記憶手段と、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記relevance変数ｒ1,i、ｒ2,jの各々の初期値を設定して前記記憶手段に記憶する初期設定手段と、前記記憶手段から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、及び前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jをサンプリングにより算出し、前記潜在クラスタ数Ｋ1,Ｋ2を決定し、前記算出した前記relevance変数ｒ1,i、ｒ2,j及び前記クラスタ割り当て変数ｚ1,i、ｚ2,j、並びに前記決定した前記潜在クラスタ数Ｋ1,Ｋ2によって、前記記憶手段に記憶してある前記relevance変数ｒ1,i、ｒ2,j、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記潜在クラスタ数Ｋ1,Ｋ2を更新し記憶する隠れ変数更新手段と、前記隠れ変数更新手段による更新を、所定の解析終了条件を満足するまで繰り返す解析終了条件判定手段と、を含んで構成されている。
【００１３】
本発明に係るクラスタリング方法は、複数のドメインの各々のオブジェクト間の関係を示す関係データの観測値に基づいて、前記ドメイン毎にオブジェクトのクラスタリングを実行するクラスタリング装置におけるクラスタリング方法であって、前記クラスタリング装置は、前記複数のドメインの各々のオブジェクトｉ，ｊ間の関係を示す観測値ｘi,j、前記複数のドメインの各々の潜在クラスタ数Ｋ1,Ｋ2、各オブジェクトｉが所属するクラスタを示すクラスタ割り当て変数ｚ1,i、各オブジェクトｊが所属するクラスタを示すクラスタ割り当て変数ｚ2,j、各オブジェクトｉに対するクラスタリングの必要性の有無を示すrelevance変数ｒ1,i、各オブジェクトｊに対するクラスタリングの必要性の有無を示すrelevance変数ｒ2,j、及びハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を記憶する記憶部と解析部とを備え、前記解析部は、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記relevance変数ｒ1,i、ｒ2,jの各々の初期値を設定して前記記憶部に記憶する初期設定ステップと、前記記憶部から前記観測値ｘi,j、前記潜在クラスタ数Ｋ1,Ｋ2、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、前記relevance変数ｒ1,i、ｒ2,j、及び前記ハイパーパラメータα1、α2、ａ、ｂ、ｃk,l、ｄk,l、ｅ1、ｅ2、f1、f2を取得し、各オブジェクトｉの前記relevance変数ｒ1,i及び前記クラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊの前記relevance変数ｒ2,j及び前記クラスタ割り当て変数ｚ2,jをサンプリングにより算出し、前記潜在クラスタ数Ｋ1,Ｋ2を決定し、前記算出した前記relevance変数ｒ1,i、ｒ2,j及び前記クラスタ割り当て変数ｚ1,i、ｚ2,j、並びに前記決定した前記潜在クラスタ数Ｋ1,Ｋ2によって、前記記憶部に記憶してある前記relevance変数ｒ1,i、ｒ2,j、前記クラスタ割り当て変数ｚ1,i、ｚ2,j、及び前記潜在クラスタ数Ｋ1,Ｋ2を更新し記憶する隠れ変数更新ステップと、前記隠れ変数更新ステップによる更新を、所定の解析終了条件を満足するまで繰り返す解析終了条件判定ステップと、を実行する。
【００１４】
本発明によれば、各オブジェクトｉのrelevance変数ｒ1,i及びクラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊのrelevance変数ｒ2,j及びクラスタ割り当て変数ｚ2,jをサンプリングにより算出して更新することを繰り返すことにより、スパースネスのある関係データから、データ構造に関係のないオブジェクトを自動的に排除して、解析精度が高いクラスタリング結果を得ることができる。
【００１５】
本発明に係るプログラムは、上記のクラスタリング装置の各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００１６】
以上説明したように、本発明のクラスタリング装置、方法、及びプログラムによれば、各オブジェクトｉのrelevance変数ｒ1,i及びクラスタ割り当て変数ｚ1,I、並びに各オブジェクトｊのrelevance変数ｒ2,j及びクラスタ割り当て変数ｚ2,jをサンプリングにより算出して更新することを繰り返すことにより、スパースネスのある関係データから、データ構造に関係のないオブジェクトを自動的に排除して、解析精度が高いクラスタリング結果を得ることができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】本発明のイメージを表わした図である。
【図２】本発明の実施の形態に係るクラスタリング装置の構成を示す概略図である。
【図３】本発明の実施の形態に係るクラスタリング装置におけるクラスタリング処理ルーチンの内容を示すフローチャートである。
【図４】本発明の実施の形態に係るクラスタリング装置の隠れ変数更新部のフローチャートである。
【図５】隠れ変数更新部によるクラスタの追加手順のフローチャートである。
【図６】隠れ変数更新部によるクラスタの整理手順のフローチャートである。
【図７】本発明の実施の形態に係るクラスタリング装置のrelevanceパラメータ更新部のフローチャートである。
【図８】本発明の実施の形態に係るクラスタリング装置のrelevant観測パラメータ更新部のフローチャートである。
【図９】本発明の実施の形態に係るクラスタリング装置のirrelevant観測パラメータ更新部のフローチャートである。
【図１０】本発明の実施の形態に係るクラスタリング装置のハイパーパラメータ更新部のフローチャートである。
【図１１】（Ａ）単一ドメインデータに対する定量評価の結果を示す図、及び（Ｂ）２ドメインデータに対する定量評価の結果を示す図である。
【図１２】（Ａ）ＩＲＭ法によるクラスタリング結果を示す図、及び（Ｂ）提案する発明によるクラスタリング結果を示す図である。
【図１３】（Ａ）観測された関係データを示す図、及び（Ｂ）従来技術であるＩＲＭ法によるクラスタリング結果を示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜概要＞
【００２０】
まず、本発明の概要について説明する。
【００２１】
本発明は、多くの実際の関係データに見られるデータスパースネスの影響を抑制する機能をもった関係データのクラスタリング手法である。まず、技術的な新規性の一点目として、関係データの構造化・抽象化に必要なオブジェクトと必要でないオブジェクトが存在するという仮定のもとで、クラスタリングにおける各オブジェクトの必要性をrelevance変数という量で表現する。次に技術的な新規性の二点目として、このオブジェクトの必要性と、クラスタリングによるデータの構造化・抽象化を表現する変数とを同時に最適化することで、オブジェクトの取捨選択とデータ抽象化の両方をバランスする解析結果を得ることが可能である。
【００２２】
図１が、本発明で提案するクラスタリングシステムのコンセプトを模式的に表した図である。提案法では、IRM法をベースとして、この手法をスパースな関係データに適用しても先に述べた問題を回避して、直感的に理解しやすいクラスタリング結果を得ることを目的とする。
【００２３】
そこで、本発明では、図１の右側の絵のように、スパースな観測データを抽象化・構造化して表現するうえで必要のない(irrelevant)オブジェクトを初めから分離し、必要のある(relevant)オブジェクトだけに着目しその中でクラスタリングを行う手法を提案する。これによれば、図１の右側における左上のrelevantデータ内では人の目でみても解釈可能な少数のブロックだけができるようにオブジェクトのクラスタリングが学習される。さらに、各ブロックはよりくっきりとした絵になる。これは、各ブロックは全く関係を持たない、あるいは高い確率で関係を持つオブジェクト集合の組み合わせを表現していることを意味する。これは複雑な関係データを定性的に解釈するうえで有効である。
【００２４】
なお、本実施の形態ではもっぱら二項関係、すなわち二つのドメインの各々のオブジェクト間の関係データをクラスタリングする場合を例に説明するが、三項関係あるいはさらに高次の関係の場合も拡張は自明であるので省略する。
【００２５】
まず、解析したい関係データの集合をXとする。二項関係の場合、Xは第一ドメインのオブジェクトiと第二ドメインのオブジェクトjの関係を表すので、X = { xij}、すなわち行番号i , 列番号j の位置の値xijでiとjの関係を表す観測量xij が与えられる。IRM法ではxijは{0,1}の二値であるが、これも整数、実数等への拡張は自明であるので説明を省略し、本実施の形態では二値変数と仮定して記載する。iはドメイン1に属するオブジェクトのインデックスでi = 1, 2, …, N1 である。j はドメイン2に属するオブジェクトのインデックスでj = 1, 2, …, N2とする。
【００２６】
この関係データXが与えられたときに、クラスタ割り当て変数 Z, およびrelevance変数 Rの２つの未知変数を推定することが提案手法の主な処理になる。その出力結果の一例が図１の右の図である。この図では、解析結果であるZ, Rを用いて与えらえた関係データを複数のオブジェクトのクラスタへと分割した図を描いている。
【００２７】
Z = {z1,i, z2,j} は各ドメインのオブジェクトのクラスタへの割り当てを表す隠れ変数である。例えばドメイン1のオブジェクトiがk番目のクラスタに所属する場合、z1,i= kと表現する。なお、Zは文脈に応じて1-of-K表現をとるものとする。すなわちz1,i = kのときz1,i,k= 1、z1,i,l = 0 (l ≠ k)である。この変数を推定することで、各オブジェクトを抽象化したクラスタとしてその性質を検討できるようになる。IRM法ではこのZだけを推定するだけであったが、先の述べたスパースネスに起因する問題を解決するため、本発明ではさらにR = {r1,i, r2,j}という隠れ変数を定義する。この変数は、各オブジェクトがクラスタリングするうえで必要(relevant)か、あるいはクラスタリングする必要がない(irrelevant)かを表す。例えばドメイン1のオブジェクトiがrelevant (irrelevant)である場合r1,i = 1 (0) という値をとるものとする。
【００２８】
図１の右側の絵では、r1,i= 1、r2,j = 1のオブジェクトが左上方向に集まるように、さらにZの値をそろえるようにクラスタリング結果を可視化している。クラスタ及びrelevance変数の境界部分は全体の行列を内分する線分で分割し、観測された関係データを少数のクラスタの組み合わせで分割表現している。第一オブジェクトあるいは第二オブジェクトのどちらかがr = 0、すなわちirrelevantとなった関係データの領域には、スパースネスに起因する一様な観測値の集合やノイズに起因する観測値が集められている。これらはデータの特徴的な振る舞い、すなわち特定の内部構造（クラスタ）を持たないと考えられる。したがって、このようなオブジェクトにはクラスタ構造を仮定せず、クラスタリングから除外する。結果、上記図１の右側の左上部分のように、relevant (r = 1)なオブジェクトだけによる、少数かつ疎密のはっきりした定性的に解釈しやすいクラスタ構造を抽出ことができる。
【００２９】
まとめると、本発明では、relevance変数Rを計算することによって、このようなirrelevantなオブジェクトによる観測量を排除したうえで、relevantすなわち何らかの特徴をもつオブジェクトだけを集めてクラスタリング変数Zを精確に推定する。これにより、重要な部分データだけを抽出し、より正確な解析と定性的な結果の解釈を容易なものにすることを可能とする。
【００３０】
＜システム構成＞
【００３１】
図２は、本発明の実施の形態に係るクラスタリング装置１００の模式図の一例である。クラスタリング装置１００は、解析したい観測データの入力を受け付ける入力部１と、クラスタリングを行う解析部２と、入力および計算された変数を記憶する記憶部３と、クラスタリング結果を出力する出力部４と、を備えている。
【００３２】
入力部１は、既知のビデオカメラ、マイクロフォン、記憶装置などの入力器により実現される。また、出力部４はディスプレイ、プリンタ、磁気ディスクなどで実装される。
【００３３】
解析部２は、初期設定部２１、変数計算部２２、及び解析終了条件判定部２８を備えている。変数計算部２２は、隠れ変数更新部２３、relevanceパラメータ更新部２４、relevant観測パラメータ更新部２５、irrelevant観測パラメータ更新部２６、及びハイパーパラメータ更新部２７を備えている。
【００３４】
記憶部３は、定数３１、観測値３２、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５、relevanceパラメータ３６、relevant観測パラメータ３７、irrelevant観測パラメータ３８、補助変数３９、及びハイパーパラメータ３１０から構成される。
【００３５】
初期設定部２１は、入力部1より入力された情報を記憶部３の各部へと記憶するとともに、記憶部３の各部の値の初期化を行う。
【００３６】
変数計算部２２は記憶部３の情報を利用して、記憶部３の各部の情報を更新、保存する。変数計算部２２の処理の流れについては、隠れ変数更新部２３、relevanceパラメータ更新部２４、relevant観測パラメータ更新部２５、irrelevant観測パラメータ更新部２６、ハイパーパラメータ更新部２７、を任意の順番で実施すればよい。また、特に出力部４において必要としない場合にはrelevanceパラメータ更新部２４、relevant観測パラメータ更新部２５、irrelevant観測パラメータ更新部２６、及びハイパーパラメータ更新部２７は実施しなくても良い。
【００３７】
隠れ変数更新部２３は、記憶部３に保存された情報を利用して、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５、relevant観測パラメータ３７、補助変数３９、及びハイパーパラメータ３１０を更新し、保存する。
【００３８】
relevanceパラメータ更新部２４は、記憶部３に保存された情報を利用して、relevanceパラメータ３６を更新し、保存する。
【００３９】
relevant観測パラメータ更新部２５は、記憶部３に保存された情報を利用して、relevant観測パラメータ３７を更新し、保存する。
【００４０】
irrelevant観測パラメータ更新部２６は、記憶部３に保存された情報を利用して、irrelevant観測パラメータ３８を更新し、保存する。
【００４１】
ハイパーパラメータ更新部２７は、記憶部３に保存された情報を利用して、ハイパーパラメータ３７を更新し、保存する。
【００４２】
解析終了条件判定部２８は、変数計算部２２および記憶部３を監視し、解析終了条件を満たしかどうかを判定する。
【００４３】
出力部４は解析終了条件判定部２８を監視し、解析終了の判断が行われた場合、所定の解析結果の出力を実施する。
【００４４】
＜クラスタリング装置の動作＞
【００４５】
次に、本実施の形態に係るクラスタリング装置１００の作用について説明する。まず、各種の定数及び観測値の時系列データが入力部１を介してクラスタリング装置１００に入力されると、クラスタリング装置１００において、図３に示すクラスタリング処理ルーチンが実行される。
【００４６】
まず、ステップＳ１０１において、初期設定部２１によって、入力部１により入力された、定数及び観測値の時系列データを受け付けて、記憶部３に格納する。
【００４７】
そして、ステップＳ１０２において、初期設定部２１によって、記憶部３の各種パラメータを初期化する。ステップＳ１０３では、繰り返し回数を示す変数ｉｔｒに初期値１を設定する。
【００４８】
次のステップＳ１０４では、隠れ変数更新部２３によって、記憶部３の情報に基づいて、クラスタ割り当て変数及びrelevance変数を更新して、記憶部３に記憶する。ステップＳ１０５では、relevanceパラメータ更新部２４によって、記憶部３の情報に基づいて、relevanceパラメータを更新して、記憶部３に記憶する。ステップＳ１０６では、relevance観測パラメータ更新部２５によって、記憶部３の情報に基づいて、relevance観測パラメータを更新して、記憶部３に記憶する。
【００４９】
そして、ステップＳ１０７において、irrelevance観測パラメータ更新部２６によって、記憶部３の情報に基づいて、irrelevance観測パラメータを更新して、記憶部３に記憶する。ステップＳ１０８では、ハイパーパラメータ更新部２７によって、記憶部３の情報に基づいて、ハイパーパラメータを更新して、記憶部３に記憶する。
【００５０】
そして、ステップＳ１０９において、解析終了条件判定部２８によって、解析終了条件を満足したか否かを判定する。解析終了条件は、例えば、繰り返し変数ｉｔｒが、予め決めておいた繰り返し回数になったことである。解析終了条件を満足していない場合には、ステップＳ１１０において、変数ｉｔｒを１インクリメントして、上記ステップＳ１０４へ戻る。一方、解析終了条件を満足する場合には、ステップＳ１１１において、上記ステップＳ１０４で最終的に更新されたクラスタ割り当て変数及びrelevance変数に基づくクラスタリング結果を出力部４により出力して、クラスタリング処理ルーチンを終了する。
【００５１】
次に、図３の各ステップの処理を実行する、クラスタリング装置１００の構成および処理の詳細について説明する。
【００５２】
＜初期設定部２１＞
【００５３】
初期設定部２１は、入力部１を通じて、解析したい観測データの時系列データＸおよび複数の定数の入力を受け付け、記憶部３の各部の値の初期化を行う。
【００５４】
入力データは以下のような形式であり、初期設定部２１でロードされる。
【００５５】
まず、以下の定数が入力され、記憶部３の定数３１に記憶される。N1は第一ドメインのオブジェクト総数、N2は第二ドメインのオブジェクト総数である。K01, K202はそれぞれ第一ドメイン、第二ドメインのクラスタ数の初期値である。Lは解析終了条件判定部２８に使用する終了条件である。これは例えば変数計算部２２の最大繰り返し回数、あるいは何らかの評価値の変化率の閾値など、解析の目的に応じて決定する。
【００５６】
入力される観測データXはN1×N2の行列データである。X = { xij }, i = 1, 2, .., N1 , j = 1, 2, …, N2、すなわち行番号i , 列番号j の位置の値xijでiとjの関係を表す観測量xij が定義される。このXを観測値３２に記憶する。定義域はタスクに応じて適切に定める。
【００５７】
次に、以下のハイパーパラメータとよばれる定数が入力され、ハイパーパラメータ３１０に記憶される。α1, α2はクラスタ割り当て変数の分布を定義する。a, bはirrelevant観測パラメータの分布を定義する。c1,1, …, cK1,K2, d1,1, …, dK1,K2はrelevant観測パラメータの分布を定義する。e1,e2,f1,f2はrelevanceパラメータの分布を定義する。各ハイパーパラメータの値の定義域は解析の目的に応じて決定する。
【００５８】
これらの入力を受け付けたのち、記憶部３のうち値が記憶されていない各部の値を初期化する。
【００５９】
潜在クラスタ数３３には、K1≦ K01, K2 ≦ K02となるように正の整数値を設定する。通常、K1= K01, K2 = K02とすればよい。
【００６０】
クラスタ割り当て変数３４のz1,1, …, z1,N1については1, …, K1の値のいずれかの値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。また、クラスタ割り当て変数３４のz2,1, …, z2,N2については1, …, K2の値のいずれかの値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。
【００６１】
relevance変数３５には、0または1の値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。
【００６２】
relevantパラメータ３６の各要素には、0より大きく1未満の値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。
【００６３】
relevance観測パラメータ３７の各要素には、観測値に合わせた定義域の値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。
【００６４】
irrelevance観測パラメータ３８の各要素には、観測値に合わせた定義域の値をランダムに、あるいは後述するモデルに基づいて確率的に値を設定する。
【００６５】
補助変数３９には、記憶部３の他の部分の値が完了したのちに、後述するモデルに基づいて計算した値を設定する。
【００６６】
以下、本実施の形態では、Xが0あるいは1の二値をとるバイナリデータの場合を例にとって説明する。データの定義域が異なる場合、各部の具体的な設計は変化するが、その際必要になる変更点は例えば、参考文献１（ビショップ, C. M., “パターン認識と機械学習”, シュプリンガージャパン, 2007.）に代表される教科書を参照することで簡単に決定・実装可能である。
【００６７】
初期化処理の終了後、処理を変数計算部２２に移す。
【００６８】
＜モデルの定式化（記憶部３）＞
【００６９】
それでは主に記憶部３に保存される情報について、モデルにおけるそれらの意味とともに説明する。
【００７０】
本発明では、観測された関係データXに基づいて、オブジェクトを少数のパターン、すなわち潜在クラスタへと分割することで関係データの構造をとらえやすくするのが目的である。しかし、非常に高次元かつスパースなデータのため、構造をもたないirrelevantなオブジェクトの存在が予想される。そこで、潜在クラスタの推定とともに、オブジェクトがrelevantかirrelevantかを予測することでスパースな関係データに対しても応用可能な解析手法を実現する。
【００７１】
まず、本発明とIRM法等の既存手法との一番の違いであるrelevance変数３５のモデルについて説明する。r1,i= {0, 1}は、ドメイン1のオブジェクトiのrelevanceを表す変数である。r1,i = 1 (0)の場合、ドメイン1のオブジェクトiはこのデータの潜在的な構造化に必要である（必要でない）ということを表す。同様にr2,j= {0,1}はドメイン2のオブジェクトjのrelevanceを表す。これらの変数は二値のバイナリ変数なので、その生成モデルとしてはベルヌイ分布、そのパラメータに対してはベータ分布を利用することが計算上望ましいのでそれで説明するが、分布の選択はこれに限らない。これらの変数の確率的なモデル（生成モデル）は、以下の（１）式〜（４）式で表される。
【００７２】
【数１】
0005746086.tif 000002
【００７３】
ここでλ1,i、λ2,jはそれぞれr1,i、r2,jが1となる確率を表すrelevanceパラメータ３６である。このように、各オブジェクトのrelevance変数、すなわち各オブジェクトがデータの潜在的な内部構造に関係があるのか、あるいはただのノイズと考えてよいのかを推定することで、次のクラスタ推定にその情報を活かす点が技術的な新規性である。
【００７４】
潜在クラスタ数３３は、各ドメインにおける潜在クラスタ数を表す。また、クラスタ割り当て変数３４は各オブジェクトのクラスタ割り当てをあらわす。K1はドメイン1、K2はドメイン2の潜在クラスタ数である。IRMおよび提案法では、これらの値を用いて元のデータの抽象化を行う。つまり、多数(N個)あるオブジェクトを少数(K個)のクラスタへと割り当てることで、N1*N2の大量の観測関係データを少数(K1*K2)の代表的なオブジェクト集合間の関係に抽象化して、人間にとって把握しやすくする。これらの変数はデータに合わせて自動的に推定する未知数であり、そのモデルとしてChinese Restaurant Process (CRP)（参考文献２）を利用する。
【００７５】
参考文献２：Klimat, Yang, “The Enron Corpus: A New Dataset for Email Classifiation Reserach”, in Proceedings of ECML, 2004.
【００７６】
CRPとは、N個のオブジェクトi = 1, 2, …, Nを未知数のクラスタへと分割する確率モデルである。i番目のオブジェクトがk番目のクラスタへと割り当てられる確率は、1, 2, …, i-1番目までのオブジェクトのクラスタ割り当てが与えられたもとで、以下の（５）式で定められる。
【００７７】
【数２】
0005746086.tif 000003
【００７８】
ここで、Kはi-1番目までのオブジェクトの異なりクラスタ数であり、nkは同じくi-1番目までのオブジェクトのうち、k番目のクラスタに割り当てられたクラスタの数である。上記（５）式の右辺第一式は、i番目のオブジェクトが現在存在するクラスタに割り当てられる確率は、すでに各クラスタに割り当てられたオブジェクトの数に比例するということを表す。一方、上記（５）式の右辺第二式は、ハイパーパラメータαに比例する確率で新しいクラスタ(K+1番目)を生成する、ということを意味する。
【００７９】
本実施の形態では、このCRPをドメイン1、ドメイン2のrelevantオブジェクトのクラスタ割り当てに利用する。すなわち、以下の（６）式〜（９）式に従って、ドメイン1、ドメイン2のrelevantオブジェクトのクラスタ割り当てを行う。
【００８０】
【数３】
0005746086.tif 000004
【００８１】
ここで、CRPは上記（５）式で表される確率モデルである。また、δ()は指定されたポイントのみ確率1のデルタ関数である。上のモデル化のポイントは、relevantなオブジェクト、すなわちr = 1となるオブジェクトは内在するクラスタ構造が期待されるため、CRPによってクラスタ割り当て変数zを生成する。一方でr = 0のirrelevantなオブジェクトにはクラスタ構造を仮定しないため、「その他」クラスタ、すなわちz = 0を割り当てる。
【００８２】
このモデルにより、スパースネスによる多くの無意味な情報をirrelevantとして排除することで、CRPによる潜在クラスタの割り当てを、relevantなオブジェクトだけで実施することが可能となる。結果、スパースネスの問題を回避したクラスタリングが実現可能となる。
【００８３】
２種の隠れ変数（relevance変数およびクラスタ割り当て変数）のモデルを決定したので、続いて実際の観測データxi,jの生成過程のモデル化を説明する。本実施の形態ではバイナリの関係データを仮定すると、以下の（１０）式〜（１２）式に示すようなモデル化が考えられる。
【００８４】
【数４】
0005746086.tif 000005
【００８５】
ここで、θk,lは、ドメイン1のクラスタkと、ドメイン2のクラスタlとの間のオブジェクト関係の観測パラメータ（relevant観測パラメータ３７）であり、φはirrelevantなオブジェクトを含む関係データの生成確率パラメータ（irrelevant観測パラメータ３８）である。Z = {z1,i,  z2,j}, R = {r1,i, r2,j}は隠れ変数の集合である。
【００８６】
観測データxi,jの生成モデルを示す上記（１２）式は少々技巧的である。この式は、ドメイン1のオブジェクトiとドメイン2のオブジェクトjとがともにrelevanceである(r1,i= r2,j = 1)場合にのみ各オブジェクトの所属するクラスタ(z1,i, z2,j)に応じたrelevant観測パラメータ３７を利用する。それ以外、すなわちどちらかのオブジェクトがirrelevantな場合にはirrelevant観測パラメータ３８を利用する。これによって、relevanceとクラスタ分けによって異なる観測パラメータが利用されるため、この違いによって変数更新時の評価値が変化することから各隠れ変数を推定することが可能になる。
【００８７】
＜変数の最適化と出力(変数計算部２２)＞
変数計算部２２の目的は、観測データX が与えられた際に、何らかの意味で最適な、記憶部３に格納された各変数を記憶・更新することである。
【００８８】
本発明では、大域的最適解に収束することが保障されているギブスサンプリングという手法を利用した最適化法の実装方法を説明する。
【００８９】
なお、各変数等の更新・最適化法は変分ベイズ法、最尤推定法等、多数存在しており、各種標準的な最適化手法を利用することができる（参考文献３）。
【００９０】
参考文献３： Antoniak, “Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems”, The Annals of Statistics, Vol. 2, No. 6, pp.1152-1174, 1974.
【００９１】
変数計算部２２は記憶部３の情報を利用して、記憶部３の各部の情報を更新、保存する。変数計算部２２の処理の流れは、隠れ変数更新部２３、relevanceパラメータ更新部２４、relevant観測パラメータ更新部２５、irrelevant観測パラメータ更新部２６、ハイパーパラメータ更新部２７、を任意の順番で実施すればよい。また、特に出力部４において必要としない場合にはrelevanceパラメータ更新部２４、relevant観測パラメータ更新部２５、irrelevant観測パラメータ更新部２６、ハイパーパラメータ更新部２７は実施しなくても良い。
【００９２】
＜隠れ変数更新部２３＞
隠れ変数更新部２３は、記憶部３に保存された情報を利用して、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５、relevant観測パラメータ３７、補助変数３９、及びハイパーパラメータ３１０を更新し、保存する。
【００９３】
まず、サンプリングの過程で必要となる補助変数３９の計算方法を、以下の（１３）式〜（１８）式に示す。 k = 1, 2, …, K1、l = 1, 2, …, K2でインデックスされている量は、全てのインデックスの組み合わせについて計算する。
【００９４】
【数５】
0005746086.tif 000006
【００９５】
これらの変数を用いて、全てのz1,i, r1,i, z2,j, r2,jをサンプリングする。本実施の形態ではz1,i(z2,j)とr1,i(r2,j)を同時にサンプリングする方法を説明する。
【００９６】
z1,i, r1,iの値のとりうる組み合わせパターンは以下のとおりである。
【００９７】
z1,i= 0,. r1,i = 0
z1,i = 1, …, K1, r1,i = 1
z1,i= K1+1, r1,i = 1
【００９８】
最初のパターンはオブジェクトiをirrelevantと判定する場合であり、最後のパターンはオブジェクトiのために新しいクラスタを生成する場合である。
【００９９】
上記のK1+2個のパターンの各々が選ばれる確率を、標準的なギブスサンプリング法（参考文献１）に従い、以下の（１９）式で各々計算する。そして、パターン毎に計算された確率に従ってK1+2個のパターンのうち一つのパターンを選択して、サンプリング結果として保存する。
【０１００】
【数６】
0005746086.tif 000007
【０１０１】
ここで、各項における¬(1,i)は、その変数全体集合から(1,i)のインデックスに対応する要素をすべて排除した集合を表し、¬iは、同様にiのインデックスに対応する要素をすべて排除した集合を表し、+iは逆にiのインデックスに対応する要素のみを集めた集合を表す。
【０１０２】
K1+2個のパターンについて、ハイパーパラメータおよび上記の補助変数を、与えられた集合についてそれぞれ計算し、上記（１９）式の評価を行う。
【０１０３】
まず、上記（１９）式の右辺第一項は、パターン毎に以下の（２０）式のように評価できる。この項は、オブジェクト全体でのスパースネスすなわちrelevant, irrelevantなオブジェクトの割合(e, f, rで計算される項)と、各クラスタのサイズ（m ,αで計算される項）の割合で、K+2個のパターンの各々への帰属確率を計算するものである。
【０１０４】
【数７】
0005746086.tif 000008
【０１０５】
ここでmを具体的に計算すると、以下の（２１）式のようになる。
【０１０６】
【数８】
0005746086.tif 000009
【０１０７】
上記（１９）式の右辺第二項は、パターン毎に以下の（２２）式、（２３）式のように評価できる。これは、オブジェクトiに関する観測関係データの分布が、K+2個のパターンの各々に従う他の観測データの分布とどの程度似ているかを表している。
【０１０８】
【数９】
0005746086.tif 000010
【０１０９】
ここでBはベータ関数を表す。iの選択によって変化する補助変数の具体的な計算は以下の（２４）式〜（３３）式のようになる。
【０１１０】
【数１０】
0005746086.tif 000011
【０１１１】
なお、新しいK1+1番目のクラスタを生成するパターンの場合、c,d,θおよび補助変数のうちk = K1+1目のクラスタに対応する量を仮想的に生成しておく必要がある。この手続きは初期設定部２１に準ずる。さらに、上記のサンプリングにおいてこの新しいパターンがサンプリングされた場合には、仮想的に生成しておいた量を記憶部３のそれぞれ対応する部分に格納したうえで、K1を1だけインクリメントする。
【０１１２】
全てのオブジェクトについてサンプリングが終了したのち、クラスタの整理を行う。すなわち、各ドメインにおいて再度補助変数３９をすべて計算する。このとき、m1,k = 0となる第一ドメインのクラスタkをすべて消去する。これに応じてc,d,Z,θおよび補助変数のうち、消去されるクラスタに対応する要素は、記憶部３から削除され、また潜在クラスタ数K1は消去されたクラスタ数だけデクリメントする。
【０１１３】
第二ドメインのオブジェクトjに対する隠れ変数のサンプリングは、第一ドメインのオブジェクトiに対するサンプリング手続きと対称であるので、ここでは省略する。全ドメインでのサンプリングが終了したのち、補助変数３９をすべて計算しなおして、最新の隠れ変数の値を反映させる。
【０１１４】
最終的に、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５, relevant観測パラメータ３７、補助変数３９、及びハイパーパラメータ３１０を、サンプリングされた値によってすべて更新し、記憶部３の各部へと格納して隠れ変数の更新処理が完了する。
【０１１５】
ここで、上記ステップＳ１０４における隠れ変数更新部２３のフローチャートの一例を図４に示す。
【０１１６】
まず、ステップＳ１２１において、記憶部３から、定数３１、観測値３２、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５, 及びハイパーパラメータ３１０を読み込む。ステップＳ１２２において、第１ドメインのオブジェクトを識別する変数ｉを初期値１に設定する。
【０１１７】
そして、ステップＳ１２３において、上記（２４）式〜（３３）式に従って、変数ｉに応じた各補助変数を計算して、上記（１９）式〜（２２）式に従って、Ｋ1＋２個のパターンの各々となる確率を計算する。そして、計算されたＫ1＋２個のパターンの各々となる確率に従って、何れかの１つのパターンを選択するようにサンプリングして、relevance変数ｒ1,i、クラスタ割り当て変数ｚ1,iを決定する。
【０１１８】
次にステップＳ１２４では、上記ステップＳ１２３で決定されたクラスタ割り当て変数ｚ1,iがＫ1＋１であるか否かを判定する。クラスタ割り当て変数ｚ1,iが、新しく生成したクラスタを示すＫ1＋１である場合には、ステップＳ１２５において、新しいクラスタをドメイン１に追加して、ステップＳ１２６へ移行する。一方、クラスタ割り当て変数ｚ1,iが、Ｋ1以下である場合には、ステップＳ１２６へ移行する。
【０１１９】
ステップＳ１２６では、上記ステップＳ１２３でサンプリングされ、又は上記ステップＳ１２５で更新されたrelevance変数ｒ1,i、クラスタ割り当て変数ｚ1,iを、メモリ（図示省略）に保存する。
【０１２０】
ステップＳ１２７では、ｉを１インクリメントして、ステップＳ１２８において、変数ｉがＮ1より大きいか否かを判定する。変数ｉがＮ1以下である場合には、上記ステップＳ１２３へ戻る。一方、変数ｉがＮ1より大きい場合には、全てのオブジェクトｉについてrelevance変数ｒ1,i、クラスタ割り当て変数ｚ1,iをサンプリングしたとして、ステップＳ１２９へ進む。
【０１２１】
ステップＳ１２９では、利用されなかったドメイン１のクラスタを整理する。次のステップＳ１３０では、第２オブジェクトを識別する変数ｊに初期値１を設定し、そして、ステップＳ１３１において、上記（２４）式〜（３３）式と同様の式に従って、変数ｊに応じた各補助変数を計算して、上記（１９）式〜（２２）式と同様の式に従って、Ｋ2＋２個のパターンの各々となる確率を計算する。そして、計算されたＫ2＋２個のパターンの各々となる確率に従って、何れかの１つのパターンを選択するようにサンプリングして、relevance変数ｒ2,j、クラスタ割り当て変数ｚ2,jを決定する。
【０１２２】
次にステップＳ１３２では、上記ステップＳ１３１で決定されたクラスタ割り当て変数ｚ2,jがＫ2＋１であるか否かを判定する。クラスタ割り当て変数ｚ2,jが、新しく生成したクラスタを示すＫ2＋１である場合には、ステップＳ１３３において、上記ステップＳ１２５と同様に、新しいクラスタをドメイン２に追加して、ステップＳ１３４へ移行する。一方、クラスタ割り当て変数ｚ2,jが、Ｋ2以下である場合には、ステップＳ１３４へ移行する。
【０１２３】
ステップＳ１３４では、上記ステップＳ１３１でサンプリングされ、又は上記ステップＳ１３３で更新されたrelevance変数ｒ2,j、クラスタ割り当て変数ｚ2,jを、メモリ（図示省略）に保存する。
【０１２４】
ステップＳ１３５では、ｊを１インクリメントして、ステップＳ１３６において、変数ｊがＮ2より大きいか否かを判定する。変数ｊがＮ2以下である場合には、上記ステップＳ１３１へ戻る。一方、変数ｊがＮ2より大きい場合には、全てのオブジェクトｊについてrelevance変数ｒ2,j、クラスタ割り当て変数ｚ2,jをサンプリングしたとして、ステップＳ１３７へ進む。
【０１２５】
ステップＳ１３７では、利用されなかったドメイン２のクラスタを整理する。
【０１２６】
次のステップＳ１３８では、上記ステップＳ１２６、Ｓ１３４で保存されたrelevance変数ｒ1,i、ｒ2,j、クラスタ割り当て変数ｚ1,i、ｚ2,j及び観測値３２に基づいて、上記（１３）式〜（１８）式に従って、補助変数３９を計算する。
【０１２７】
そして、ステップＳ１３９において、定数３１、観測値３２、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５、relevanceパラメータ３６、relevant観測パラメータ３７、補助変数３９、及びハイパーパラメータ３１０を更新して記憶して、処理を終了する。
【０１２８】
上記ステップＳ１２５におけるクラスタの追加手順のフローチャートの一例を図５に示す。
【０１２９】
ステップＳ１５０において、第２ドメインのクラスタを識別する変数ｌを初期値１に設定し、ステップＳ１５１において、cK1+1,lの値を適当に決定して、メモリ（図示省略）に確保する。ステップＳ１５２では、dK1+1,lの値を適当に決定して、メモリに確保する。
【０１３０】
そして、ステップＳ１５３では、変数ｌを１だけインクリメントし、ステップＳ１５４において、変数ｌがＫ2より大きいか否かを判定する。変数ｌがＫ2以下であれば、上記ステップＳ１５１へ戻るが、一方、変数ｌがＫ2より大きければ、ステップＳ１５５へ移行する。
【０１３１】
ステップＳ１５５では、変数ｌを初期値１に設定し、ステップＳ１５６において、nK1+1,lの値を適当に決定して、メモリに確保する。ステップＳ１５７では、￣nK1+1,lの値を適当に決定して、メモリに確保する。
【０１３２】
そして、ステップＳ１５８では、変数ｌを１だけインクリメントし、ステップＳ１５９において、変数ｌがＫ2より大きいか否かを判定する。変数ｌがＫ2以下であれば、上記ステップＳ１５６へ戻るが、一方、変数ｌがＫ2より大きければ、ステップＳ１６０へ移行する。
【０１３３】
ステップＳ１６０では、変数ｌを初期値１に設定し、ステップＳ１６１において、qK1+1,lの値を適当に決定して、メモリに確保する。ステップＳ１６２では、変数ｌを１だけインクリメントし、ステップＳ１６３において、変数ｌがＫ2より大きいか否かを判定する。変数ｌがＫ2以下であれば、上記ステップＳ１６１へ戻るが、一方、変数ｌがＫ2より大きければ、ステップＳ１６４へ移行する。
【０１３４】
ステップＳ１６４では、m1,K1+1の値を適当に決定して、メモリに確保する。そして、ステップＳ１６５で、K1を1だけインクリメントして、処理を終了する。
【０１３５】
上記ステップＳ１２９におけるクラスタの整理手順のフローチャートの一例を図６に示す。
【０１３６】
ステップＳ１７０において、上記（１５）式に従って、補助変数m1,1, …, m1,k, …, m1,K1を再計算する。そして、ステップＳ１７１において、変数ｋをＫ1に設定し、ステップＳ１７２では、ｍ1,k＝０であるか否かを判定する。ｍ1,k＝０である場合には、クラスタｋは使われていないと判断し、後述するステップＳ１７５へ移行する。一方、ｍ1,k＝０でない場合には、ステップＳ１７３において、変数ｋを１だけデクリメントして、ステップＳ１７４において、変数ｋが１未満であるか否かを判定する。変数ｋが１以上である場合には、上記ステップＳ１７２へ戻る。一方、変数ｋが１未満である場合には、クラスタの整理手順を終了する。
【０１３７】
ステップＳ１７５では、第１ドメインのオブジェクトを識別する変数ｉに初期値１を設定し、ステップＳ１７６において、ｚ1,i＞ｋであるか否かを判定し、ｚ1,i＞ｋであれば、ステップＳ１７７で、ｚ1,iの値を1小さくして更新する。一方、ｚ1,i＞ｋでない場合には、ステップＳ１７８へ移行する。
【０１３８】
ステップＳ１７８では、変数ｉを１だけインクリメントして、ステップＳ１７９において、変数ｉがＮ1より大きいか否かを判定する。変数ｉがＮ1以下である場合には、上記ステップＳ１７６へ戻るが、一方、変数ｉがＮ1より大きい場合には、ステップＳ１８０へ移行する。
【０１３９】
ステップＳ１８０では、ｋ*にｋを設定し、ステップＳ１８１において、l = 1, 2, …, K2に対して、ck*,l の値を ck*+1,lで上書きして更新する。ステップＳ１８２では、l = 1, 2, …, K2に対して、dk*,l の値を、dk*+1,lで上書きして更新する。ステップＳ１８３では、l = 1, 2, …, K2に対して、θk*,lの値を、θk*+1,lで上書きして更新する。ステップＳ１８４では、l = 1, 2, …, K2に対して、nk*,lの値を、nk*+1,lで上書きして更新する。ステップＳ１８５では、l = 1, 2, …, K2に対して、nk*,lの値を、nk*+1,lで上書きして更新する。そして、ステップＳ１８６では、m1,k*の値を、m1,k*+1で上書きして更新する。
【０１４０】
ステップＳ１８７では、k*を１だけインクリメントして、ステップＳ１８８において、k*が、Ｋ1であるか否かを判定する。k*がＫ1でない場合には、上記ステップＳ１８１へ戻る。一方、k*がＫ1である場合には、ステップＳ１８９へ移行する。
【０１４１】
ステップＳ１８９では、l = 1, 2, …, K2に対しck*,l をメモリから消去する。ステップＳ１９０では、l = 1, 2, …, K2に対しdk*,lをメモリから消去する。ステップＳ１９１では、l = 1, 2, …, K2に対しθk*,lをメモリから消去する。ステップＳ１９２では、l = 1, 2, …, K2に対しnk*,lをメモリから消去する。ステップＳ１９３では、l = 1, 2, …, K2に対し￣nk*,lをメモリから消去する。そして、ステップＳ１９４において、m1,k*をメモリから消去する。
【０１４２】
次のステップＳ１９５では、Ｋ1の値を、１だけ小さくして更新し、上記ステップＳ１７３へ移行する。
【０１４３】
＜relevanceパラメータ更新部２４＞
relevanceパラメータ更新部２４は、記憶部３に保存された情報を利用して、relevanceパラメータ３６を更新し、保存する。
【０１４４】
この更新は、例えば記憶部３の説明に利用した確率分布を利用することで、共役性により簡単に実装可能である。
【０１４５】
具体的には、ドメイン1のオブジェクトiに関するrelevanceパラメータ、およびドメイン2のオブジェクトjに関するrelevanceパラメータは、以下の（３４）式、（３５）式に示す確率分布に従ってサンプリングすれば良い。これらの計算は、各ドメインで幾つのオブジェクトがrelevancve, irrelevanceと判断されているかの割合（クラスタリングに必要と判断されたオブジェクトと、必要ないと判断されたオブジェクトの割合）に応じてパラメータを決定することを意味する。
【０１４６】
【数１１】
0005746086.tif 000012
【０１４７】
上記ステップＳ１０５におけるrelevanceパラメータ更新部２４の更新手順のフローチャートの一例を図7に示す。
【０１４８】
まず、ステップＳ２００において、記憶部３より、定数３１、relevance変数３５、及びハイパーパラメータ３１０をロードする。そして、ステップＳ２０１において、変数ｉを１に設定する。ステップＳ２０２では、上記（３４）式に示す確率分布を計算し、計算した確率分布に従って、λ1,iの値をサンプリングにより決定して更新する。
【０１４９】
次のステップＳ２０３では、変数ｉを１だけインクリメントし、ステップＳ２０４において、変数ｉが、Ｎ1より大きいか否かを判定する。変数ｉがＮ1以下である場合には、上記ステップＳ２０２へ戻るが、一方、変数ｉがＮ1より大きい場合には、ステップＳ２０５へ移行する。
【０１５０】
ステップＳ２０５では、変数ｊを１に設定する。ステップＳ２０６では、上記（３５）式に示す確率分布を計算し、計算した確率分布に従って、λ2,jの値をサンプリングにより決定して更新する。
【０１５１】
次のステップＳ２０７では、変数ｊを１だけインクリメントし、ステップＳ２０８において、変数ｊが、Ｎ2より大きいか否かを判定する。変数ｊがＮ2以下である場合には、上記ステップＳ２０６へ戻るが、一方、変数ｊがＮ2より大きい場合には、ステップＳ２０９へ移行する。
【０１５２】
ステップＳ２０９では、更新されたrelevanceパラメータλ1,i、λ2,jを記憶部３のrelevanceパラメータ３６に格納し、更新を終了する。
【０１５３】
＜relevant観測パラメータ更新部２５＞
relevant観測パラメータ更新部２５は、記憶部３に保存された情報を利用して、relevant観測パラメータ３７を更新し、保存する。
【０１５４】
この更新は、例えば記憶部３の説明に利用した確率分布を利用することで、共役性により簡単に実装可能である。
【０１５５】
具体的には、ドメイン1のクラスタkとドメイン2のクラスタlに関するrelevant観測パラメータは以下の（３６）式に示す確率分布に従ってサンプリングすれば良い。これらの計算は、第一ドメインのクラスタkと第二ドメインのクラスタlの間の観測関係データの値がどのように分布しているか（関係をもつオブジェクトそれぞれのクラスタｋ、ｌの割り当てが一致する観測関係データ全体で、観測値がどのように分布しているか）、という情報に応じてパラメータを決定することを意味する。
【０１５６】
【数１２】
0005746086.tif 000013
【０１５７】
上記ステップＳ１０６におけるrelevant観測パラメータ更新部２５の更新手順のフローチャートの一例を図８に示す。
【０１５８】
まず、ステップＳ２１０において、記憶部３により、定数３１, 潜在クラスタ数３２, 補助変数３９, ハイパーパラメータ３１０をロードする。そして、ステップＳ２１１において、変数ｋを１に設定し、ステップＳ２１２で、変数ｌを１に設定する。
【０１５９】
そして、ステップＳ２１３において、上記（３６）に示す確率分布を計算し、計算された確率分布に従って、θk,lの値をサンプリングにより決定して更新する。
【０１６０】
そして、ステップＳ２１４において、変数ｌを１だけインクリメントし、ステップＳ２１５において、変数ｌがＫ2より大きいか否かを判定する。変数ｌがＫ2以下である場合には、上記ステップＳ２１３へ戻る。一方、変数ｌがＫ2より大きい場合には、変数ｋを１だけインクリメントし、変数ｋがＫ1より大きいか否かを判定する。変数ｋがＫ1以下である場合には、上記ステップＳ２１２へ戻る。一方、変数ｋがＫ1より大きい場合には、ステップＳ２１８において、更新されたθk,lを記憶部３のrelevant観測パラメータ３７に格納し、更新を終了する。
【０１６１】
＜irrelevant観測パラメータ更新部２６＞
irrelevant観測パラメータ更新部２６は、記憶部３に保存された情報を利用して、irrelevant観測パラメータ３８を更新し、保存する。
【０１６２】
この更新は、例えば記憶部３の説明に利用した確率分布を利用することで、共役性により簡単に実装可能である。
【０１６３】
具体的には以下の（３７）式に示す確率分布に従ってサンプリングすれば良い。これらの計算は、irrelevantと判断された観測関係データの値がどのように分布しているか（クラスタリングに必要ないと判断されたオブジェクトに関係する観測関係データ全体で、観測値がどのように分布しているか）、という情報に応じてパラメータを決定することを意味する。
【０１６４】
【数１３】
0005746086.tif 000014
【０１６５】
上記ステップＳ１０７におけるirrelevant観測パラメータ更新部２６の更新手順のフローチャートの一例を図9に示す。
【０１６６】
まず、ステップＳ２２０において、記憶部３により、定数３１、補助変数３９、ハイパーパラメータ３１０をロードする。そして、ステップＳ２２１において、上記（３７）式に示す確率分布を計算し、計算された確率分布に従って、φの値をサンプリングにより決定し更新する。
【０１６７】
ステップＳ２２２では、更新されたφを記憶部３のirrelevant観測パラメータ３８に格納し、更新を終了する。
【０１６８】
＜ハイパーパラメータ更新部２７＞
ハイパーパラメータ更新部２７は、記憶部３に保存された情報を利用して、ハイパーパラメータ３１０を更新し、保存する。
【０１６９】
ここでは、事前分布としてガンマ分布を仮定した場合のサンプリング法を説明する。なお、以下簡単のためガンマ分布のパラメータは省略しGamma(・)とのみ表記する。
【０１７０】
α1は以下の（３８）式に従ってサンプリングする。
【０１７１】
【数１４】
0005746086.tif 000015
【０１７２】
ここでGamma(・)はガンマ関数を表す。
【０１７３】
α2は以下の（３９）式に従ってサンプリングする。
【０１７４】
【数１５】
0005746086.tif 000016
【０１７５】
a, bは以下の（４０）式に従ってサンプリングする。
【０１７６】
【数１６】
0005746086.tif 000017
【０１７７】
ck,l, dk,lは以下の（４１）式に従ってサンプリングする。
【０１７８】
【数１７】
0005746086.tif 000018
【０１７９】
e1, f1は以下の（４２）式に従ってサンプリングする。
【０１８０】
【数１８】
0005746086.tif 000019
【０１８１】
e2, f2は以下の（４３）式に従ってサンプリングする。
【０１８２】
【数１９】
0005746086.tif 000020
【０１８３】
上記ステップＳ１０８におけるハイパーパラメータ更新部２７の更新手順のフローチャートの一例を図10に示す。
【０１８４】
まず、ステップＳ２３０において、記憶部３により、定数３１、観測値３２、潜在クラスタ数３３、クラスタ割り当て変数３４、relevance変数３５、補助変数３９、及びハイパーパラメータ３１０をロードする。そして、ステップＳ２３１において、上記（３８）式が示す確率分布を計算し、計算された確率分布に従って、α1の値をサンプリングして更新する。ステップＳ２３２において、上記（３９）式が示す確率分布を計算し、計算された確率分布に従って、α2の値をサンプリングして更新する。
【０１８５】
そして、ステップＳ２３３において、上記（４０）式が示す確率分布を計算し、計算された確率分布に従って、ａ，ｂの値をサンプリングして更新する。ステップＳ２３５において、上記（４２）式が示す確率分布を計算し、計算された確率分布に従って、ｅ1，ｆ1の値をサンプリングして更新する。ステップＳ２３６において、上記（４３）式が示す確率分布を計算し、計算された確率分布に従って、ｅ2，ｆ2の値をサンプリングして更新する。
【０１８６】
そして、ステップＳ２３７において、変数ｋを１に設定し、ステップＳ２３８において、変数ｌを１に設定する。そして、ステップＳ２３９で、上記（４１）式に示す確率分布を計算し、計算された確率分布に従って、ｃk,l、ｄk,lの値をサンプリングして更新する。
【０１８７】
そして、ステップＳ２４０において、変数ｌを１だけインクリメントし、ステップＳ２４１において、変数ｌがＫ2より大きいか否かを判定する。変数ｌがＫ2以下である場合には、上記ステップＳ２３９へ戻る。一方、変数ｌがＫ2より大きい場合には、ステップＳ２４２へ進む。
【０１８８】
ステップＳ２４２では、変数ｋを１だけインクリメントし、ステップＳ２４３において、変数ｋがＫ1より大きいか否かを判定する。変数ｋがＫ1以下である場合には、上記ステップＳ２３８へ戻る。一方、変数ｋがＫ1より大きい場合には、ステップＳ２４５へ進む。
【０１８９】
ステップＳ２４５では、更新されたハイパーパラメータを記憶部３のハイパーパラメータ３１０に格納し、更新を終了する。
【０１９０】
なお、ハイパーパラメータの更新には、他にも様々な方法を利用することができる。また、ハイパーパラメータは必ずしも更新しなくても良い。
【０１９１】
＜解析終了条件判定部２８＞
解析終了条件判定部２８は、変数計算部２２を監視し、変数の更新処理を続けるか終了するかを判定する。
【０１９２】
一般に変数の更新は繰り返し処理により最適値へ近づく。しかし、いつ繰り返しを止めるかについては様々な方法がある。以下の実験結果では、最も簡単に定数Lとして繰り返し回数の最大値を入力しておき、変数の更新処理の繰り返し回数がLとなった時点で更新処理を終了することとした。
【０１９３】
設定した解析終了条件が満たされていない場合、再び変数計算部２２に処理を戻す。設定した解析終了条件が満たされると、解析結果は、ユーザが規程した所望の形で出力部４へと出力される。
【０１９４】
＜単一ドメインデータ、更に高次の関係データの場合＞
ここまで、２ドメインの各々のオブジェクト間の関係データについてシステムの構成方法を示してきたが、本発明は単一のドメインにおけるオブジェクト間の関係データ、あるいはさらに高次の関係データへの拡張も容易である。
【０１９５】
単一ドメインD内のN種のオブジェクトi, j (i,j = 1, 2, …, N)の間の関係データを処理する場合、N1 = N2 = N, K01= K02 = K0, K1 = K2 = K, α1=α2 =α, e1 = e2 = e, f1 = f2= fのように定数・ハイパーパラメータの縮約を行う。さらに、隠れ変数やrelevanceパラメータはそれぞれ1種類のみとなるのでzi, ri ，λiと表記できる。これに従い、各更新部の具体的な処理を修正すれば良い。
【０１９６】
また、逆に高次の関係、例えば3ドメインの各々のオブジェクト間の関係データの場合には各定数・各変数にドメイン3に対応する要素を追加すれば良い。
【０１９７】
いずれの場合も各部の修正は自明であるため、説明を省略する。
【０１９８】
＜実験例＞
次に、本実施の形態で提案する関係データのクラスタリング手法を用いた実験の結果について説明する。実験では単一ドメインデータ、２ドメインデータそれぞれについて、２種類の人工データ、２種類の実データで評価を行った。
【０１９９】
単一ドメインデータとしては、人工データであるN = 500(small), 1000(large)のデータをシミュレーションで生成した。真の潜在クラスタ数Kは両データでK=3とした。実データとしては、上記参考文献２で提供されたEnron社の社内Emailデータを利用した。このデータはN=151人の社員間のメールを記録したものである。本実験では2001年8月(Enron Aug.)と2011年10月(Enron Oct.)の月内のメール記録を利用して、社員iから社員jへのメールが一通でもあればxi,j = 1、メールがなければxi,j = 0としてデータを生成した。
【０２００】
２ドメインデータとしては、人工データである{N1, N2} = {400,500}(small), {800, 900}(large)のデータをシミュレーションで生成した。真の潜在クラスタ数は両方のデータで{K1, K2} = {4, 5}とした。実データとしては、携帯電話でのマンガ購買履歴データを利用した。これは第一ドメインがユーザ、第二ドメインがマンガであり、データ収集期間中にあるユーザiが当該サービスでマンガjを購入した場合にxi,j= 1、購買しなければxi,j = 0としてデータを生成した。観測データは非常に膨大であるため、本実験ではN1 = 1000人のユーザをランダムに選択して、N2 = ３１6のマンガとの購買関係データを抽出するデータセットを2種類(Cartoon 1, Cartoon 2)準備した。
【０２０１】
定量評価として、テストデータ対数尤度を用いた。与えられた観測関係データから、およそ1%の観測データを未知のテストデータとしてランダムに選択し、変数計算部２２の処理から除外する。解析終了後、それらテストデータの対数尤度を計算し、それをテストデータ数で平均した数値の大小で、提案する本発明の出力したクラスタリング結果の精度を測る。
【０２０２】
実験結果を図１１（Ａ）、（Ｂ）に示す。対数尤度は数字が大きいほど良い。この結果よりわかるように、本発明によれば、relevance変数のないIRM法に比べて、全てのデータで対数尤度が向上することが分かった。
【０２０３】
続いて、定性的な評価を行う。図１２（Ａ）、（Ｂ）はCartoon 1データのクラスタリング結果である。観測データが非常にスパースかつノイジーであるため、IRM法のクラスタリング結果は解釈の困難なクラスタが多数生成されてしまっている。一方で提案法ではrelevance変数の導入により、スパースな観測データが右側(r2,j= 0)の領域に分割され、推定される潜在クラスタ数が少数に抑えられている。これにより、結果の定性的な解釈がより容易になった。
【０２０４】
各クラスタを詳しくみると、例えばl = 2の第二ドメインのクラスタには、テレビアニメ・映画などになったような非常に有名なマンガや、いわゆる古典と呼ばれる名作、中でも売り上げだけの大きい少年・少女漫画誌に掲載された作品がクラスタリングされた。またl = 3のクラスタには主に２０歳代から４０歳代の男性を対象とした漫画が多く集まった。
【０２０５】
このように、提案法で関係データを解析すると、既存の手法に比べ、スパースネスの影響を抑えたうえでより定性的に解釈しやすいデータのクラスタリングが可能であり、さらに数値評価の上でもより高いデータ解析精度を実現することが可能である。
【０２０６】
以上説明したように、本発明の実施の形態に係るクラスタリング装置によれば、第１ドメインの各オブジェクトｉのrelevance変数ｒ1,i及びクラスタ割り当て変数ｚ1,I、並びに第２ドメインの各オブジェクトｊのrelevance変数ｒ2,j及びクラスタ割り当て変数ｚ2,jをサンプリングにより算出して更新することを繰り返すことにより、スパースネスのある関係データから、データ構造に関係のないオブジェクトを自動的に排除して、解析精度が高いクラスタリング結果を得ることができる。また、人手による解釈が容易なクラスタリング結果を得ることができる。
【０２０７】
また、データのスパースネスの問題がある関係データに対しても、オブジェクトを複数のクラスタに抽象化し、可視化やデータ解析を容易に行うことができる。
【０２０８】
また、relevance変数の導入によって、スパースネスのある関係データからデータ構造に関係のないオブジェクトを自動的に排除することが可能になり、スパースネスの悪影響を抑制できる。また、データの構造化・抽象化に必要なオブジェクトだけを抽出してクラスタリングすることで、少数の理解しやすいクラスタが抽出され、人手によるデータクラスタリング結果の解釈が容易になる。
【０２０９】
relevance変数の導入によって、スパースネスのある関係データに対して、より実際のデータに即した構造化が実現できるため、未知データ（テストデータ）の予測も既存手法よりも高精度に実現できる。
【０２１０】
また、オブジェクトが構造化・抽象化に必要かどうかと、クラスタリングによる抽象化とを同時に推定可能である。
【０２１１】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０２１２】
例えば、上述のクラスタリング装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０２１３】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０２１４】
１     入力部
２     解析部
３     記憶部
４     出力部
２１   初期設定部
２２   変数計算部
２３   隠れ変数更新部
２４   relevanceパラメータ更新部
２５   relevant観測パラメータ更新部
２６   irrelevant観測パラメータ更新部
２７   ハイパーパラメータ更新部
２８   解析終了条件判定部
１００ クラスタリング装置
【図３】
0005746086.tif 000021
【図４】
0005746086.tif 000022
【図５】
0005746086.tif 000023
【図６】
0005746086.tif 000024
【図７】
0005746086.tif 000025
【図８】
0005746086.tif 000026
【図９】
0005746086.tif 000027
【図１０】
0005746086.tif 000028
【図１】
0005746086.tif 000029
【図２】
0005746086.tif 000030
【図１１】
0005746086.tif 000031
【図１２】
0005746086.tif 000032
【図１３】
0005746086.tif 000033