クラスタリング装置、クラスタリング方法およびクラスタリングプログラム
【課題】各クラスタの属性の判定に係る制約を無くし、かつクラスタ間の関係を分かりやすくする。
【解決手段】各データが属するクラスタを階層的に分割する分割部４３６と、分割部４３６によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部４４０と、を備える。
【解決手段】各データが属するクラスタを階層的に分割する分割部４３６と、分割部４３６によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部４４０と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置、クラスタリング方法およびクラスタリングプログラムに関する。
【背景技術】
【０００２】
データベース、データマイニング、情報の検索、市場解析を含む大量データの処理にとって、クラスタリング分析は重要な方法の１つである。クラスタリング分析の目的は、与えられたデータのうち、類似するデータ群をひとまとまりのクラスタとして複数のクラスタに分類することである。例えば、非特許文献１には、統計モデルをベースにしたクラスタリング手法が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｐ． Ｈｏｆｆ． Ｍｏｄｅｌ−ｂａｓｅｄ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ．Ｂａｙｅｓｉａｎ Ａｎａｌｙｓｉｓ， （１）：３２１−３４４， ２００６
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１のクラスタリング手法では、各クラスタの属性を「クラスタ固有」あるいは「全クラスタ共通」のいずれかしか判定できないという制約があるという問題がある。具体的には、例えば、クラスタ数が１０のとき、そのうち２つのクラスタに共通の属性があっても、その属性をクラスタに固有あるいは全クラスタに共通のいずれかしか判定できなかった。
【０００５】
また、非特許文献１のクラスタリング手法では、得られるクラスタの構造がフラットな構造であるため、クラスタ間の関係が分からないという問題があった。そのため、複数のクラスタに共通の属性を、クラスタを特徴づける属性としてクラスタに割り振ることができなかった。
【０００６】
そこで本発明は、上記問題に鑑みてなされたものであり、各クラスタの属性の判定に係る制約を無くし、かつクラスタ間の関係を分かりやすくすることを可能とする技術を提供することを課題とする。
【課題を解決するための手段】
【０００７】
本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、各データが属するクラスタを階層的に分割する分割部と、前記分割部によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部と、を備えることを特徴とするクラスタリング装置である。
【０００８】
また、本発明の一態様は、上記のクラスタリング装置において、前記各データに対し、ランダムにサブクラスを割り振るサブクラス割振部を更に備え、前記属性選択部は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、前記属性の値がサブクラス間で違いがない場合は、該属性の値を該サブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とすることを特徴とする。
【０００９】
また、本発明の一態様は、上記のクラスタリング装置において、前記属性選択部は、属性毎に該属性がサブクラスに固有である確率を算出し、該算出した確率に基づいて、該属性が前記サブクラス間で共通の属性か前記サブクラスに固有の属性かを判定することを特徴とする。
【００１０】
また、本発明の一態様は、上記のクラスタリング装置において、前記属性選択部は、前記データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出し、該算出した確率に基づいて前記データ毎に該データに割り振られるサブクラスを推定することを特徴とする。
【００１１】
また、本発明の一態様は、上記のクラスタリング装置において、前記サブクラスを識別するサブクラス識別情報の確率分布が二項分布で表され、前記属性がサブクラスに固有であるか否かを示す固有フラグの確率分布がベルヌーイ分布で表されることを特徴とする。
【００１２】
また、本発明の一態様は、各データが属するクラスタを階層的に分割する分割手順と、前記分割手順によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択手順と、を有するクラスタリングクラスタ分類方法である。
【００１３】
また、本発明の一態様は、コンピュータに、各データが属するクラスタを階層的に分割する分割ステップと、前記分割ステップによりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択ステップと、を実行するためのクラスタリングプログラムである。
【発明の効果】
【００１４】
本発明によれば、各クラスタの属性の判定に係る制約を無くし、かつクラスタ間の関係を分かりやすくすることができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態におけるクラスタリングシステムの概略ブロック図である。
【図２】本実施形態におけるユーザ端末のハードウェアの構成を示す概略ブロック図である。
【図３】本実施形態におけるサービスサーバのハードウェアの構成を示す概略ブロック図である。
【図４】本実施形態におけるファイルサーバのハードウェアの構成を示す概略ブロック図である。
【図５】本実施形態における計算サーバのハードウェアの構成を示す概略ブロック図である。
【図６】本実施形態における計算サーバの制御部の論理的な構成を示す概略ブロック図である。
【図７】ファイルＦに含まれるデータが格納されたテーブルＴ１の一例と、属性割付部による処理後のデータが格納されたテーブルＴ２の一例とが示された図である。
【図８】サブクラス割振部によりデータ毎にサブクラスが割り振られた１例を示すテーブルＴ３である。
【図９】図８のテーブルＴ３の観測値において、サブクラスに固有であるか否かを示す固有フラグｒの値の一例が示されたテーブルＴ４である。
【図１０】本実施形態における観測値ｙを推定する処理が示されたグラフィカルモデルである。
【図１１】固有フラグｒの値によりパラメタθまたはパラメタθ（チルタ）のいずれかが選択されることについて説明するための図である。
【図１２】変数推定部の論理的な構成を示す概略ブロック図である。
【図１３】本実施形態におけるデータベースサーバのハードウェアの構成を示す概略ブロック図である。
【図１４】クラスタリング結果記憶部に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ５である。
【図１５】クラスタリング結果記憶部に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ６である。
【図１６】クラスタの階層構造の一例が示された図である。
【図１７】映画のタイトルがクラスタリングされた結果の一例が示された図である。
【図１８】本実施形態における計算サーバの処理の流れを示すフローチャートである。
【図１９】本実施形態におけるクラスタリング処理に係る時間と、従来手法のクラスタリング処理に係る時間とを比較した図である。
【図２０】本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとのパープレキシティを比較したテーブルである。
【図２１】トップＮの正確性が各手法間で比較されたテーブルである。
【図２２】３つのパラメータが各手法間で比較されたテーブルである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照して詳細に説明する。本実施形態では、分類対象となるデータを分類するために各データに割り振られる識別子をクラス、同一のクラスが割り振られたデータの集合である分類結果をクラスタ、クラスタに含まれるデータを更に分類するために各データに割り振られる識別子をサブクラス、データの分類をクラスタリングと称し、以下説明する。
図１は、本実施形態におけるクラスタリングシステム１の概略ブロック図である。クラスタリングシステム１は、ユーザ端末１００と、サービスサーバ２００と、ファイルサーバ３００と、計算サーバ（クラスタリング装置）４００と、データベースサーバ５００とを有する。
【００１７】
ユーザ端末１００は、ユーザによって入力されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とをサービスサーバ２００に送信する。また、ユーザ端末１００は、サービスサーバ２００から供給されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを自装置が備える後述する表示部１０４に表示させる。
【００１８】
サービスサーバ２００は、ユーザ端末１００から送信されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とを受信し、受信したクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とをファイルサーバ３００に送信する。
また、サービスサーバ２００は、データベースサーバ５００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒをユーザ端末１００に送信する。
【００１９】
ファイルサーバ３００は、サービスサーバ２００から送信されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とを受信する。ファイルサーバ３００には、自装置が備える後述するデータファイル記憶部３０３にデータが分析対象毎にファイルで予め記憶されている。ここで、データは、例えば、ログ（例えば、映画毎に、各ユーザがその映画を見たか否かといった情報）、テキストファイル、画像ファイル、音声ファイルまたは動画ファイルである。
【００２０】
ファイルサーバ３００は、クラスタリング結果を要求する情報Ｒｑを受信した場合、データファイル記憶部３０３からファイルＦを読み出し、ファイルＦとクラスタ数Ｎを示す情報とファイルを計算サーバ４００に送信する。
【００２１】
計算サーバ４００は、ファイルサーバ３００から送信されたファイルＦとクラスタ数Ｎを示す情報とを受信し、受信したファイルＦに基づいて、クラスタ数がＮに到達するまで入力データをクラスタに分割する。計算サーバ４００は、分割により得られたクラスタリング結果を示す情報Ｒをデータベースサーバ５００に送信する。
【００２２】
データベースサーバ５００は、計算サーバ４００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを後述するクラスタリング結果記憶部５０３に記憶させる。また、データベースサーバ５００は、受信したクラスタリング結果を示す情報Ｒをサービスサーバ２００に送信する。
【００２３】
図２は、本実施形態におけるユーザ端末１００のハードウェアの構成を示す概略ブロック図である。ユーザ端末１００は、記憶部１０１と、制御部１０２と、通信部１０３と、表示部１０４と、入力部１０５を備える。
記憶部１０１には、制御部１０３が実行するための各種プログラムが記憶されている。
入力部１０２は、自端末のユーザから入力されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報を受け付ける。入力部１０２は、例えば、キーボードとマウスを備える。入力部１０２は、受け付けたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報を制御部１０３に出力する。
【００２４】
制御部１０３は、プログラムを記憶部１０１から読み出して実行することにより、例えば、クラスタリング結果を要求する情報Ｒｑの入力を受け付けるボタンとクラスタ数Ｎを示す情報を入力するための欄を表示部１０５に表示させる。これにより、ユーザ端末１００のユーザは、クラスタ数Ｎをキーボードから入力し、当該ボタンをマウスを用いてクリックすることにより、クラスタ結果を示す情報Ｒを要求することができる。
【００２５】
制御部１０３は、入力部１０２から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを通信部１０４に出力し、クラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを通信部１０４からサービスサーバ２００に送信させる。また、制御部１０３は、通信部１０４から供給されたクラスタリング結果を示す情報Ｒを表示部１０５に表示させる。
【００２６】
通信部１０４は、有線または無線方式で、サービスサーバ２００と通信可能に構成されている。通信部１０４は、制御部１０３による制御に従って、制御部１０３から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをサービスサーバ２００に送信する。
また、通信部１０４は、サービスサーバ２００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを制御部１０３に出力する。
【００２７】
表示部１０５は、例えば液晶表示パネルを備える。表示部１０５は、制御部１０３から供給されたクラスタリング結果を示す情報Ｒを表示する。
【００２８】
図３は、本実施形態におけるサービスサーバ２００のハードウェアの構成を示す概略ブロック図である。サービスサーバ２００は、通信部２０１と、呼出部２０２とを備える。
通信部２０１は、有線または無線方式で、ユーザ端末１００とファイルサーバ３００と通信可能に構成されている。通信部２０１は、ユーザ端末１００から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを受信する。
【００２９】
通信部２０１は、制御部２０２の制御により、受信したクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをファイルサーバ３００に送信する。
また、通信部２０１は、データベースサーバ５００から供給されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒをユーザ端末１００に送信する。
【００３０】
制御部２０２は、通信部２０１を制御して、クラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをファイルサーバ３００に送信させる。
制御部２０２は、通信部２０１を制御して、クラスタリング結果を示す情報Ｒをユーザ端末１００に送信させる。
【００３１】
図４は、本実施形態におけるファイルサーバ３００のハードウェアの構成を示す概略ブロック図である。ファイルサーバ３００は、通信部３０１と、制御部３０２と、データファイル記憶部３０３とを備える。
データファイル記憶部３０３は、自装置の外部から供給されたデータ（例えば、ログ、テキストファイル、画像ファイル）が蓄積される。これにより、データファイル記憶部３０３には、データが分析対象毎にファイルで予め記憶されている。
【００３２】
通信部３０１は、有線または無線方式で、サービスサーバ２００と計算サーバ４００と通信可能に構成されている。サービスサーバ２００から送信されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを受信する。通信部３０１は、制御部３０２の制御により、受信したクラスタリング結果を要求する情報Ｒｑを制御部３０２に出力する。
また、通信部３０１は、制御部３０２の制御に従って、制御部３０２によりデータ記憶部３０３から読み出されたファイルＦとクラスタ数Ｎを示す情報とを計算サーバ４００に送信する。
【００３３】
制御部３０２は、通信部３０１から供給されたクラスタリング結果を要求する情報Ｒｑを受け取った場合、データ記憶部３０３からクラスタリング対象のデータを含むファイルＦを読み出す。そして、制御部３０２は、読み出したファイルＦを、クラスタ数Ｎを示す情報と共に通信部３０１から計算サーバ４００に送信させる。
【００３４】
図５は、本実施形態における計算サーバ４００のハードウェアの構成を示す概略ブロック図である。計算サーバ４００は、通信部４０１と、制御部４０２とを備える。
通信部４０１は、ファイルサーバ３００から送信されたファイルＦとクラスタ数Ｎを示す情報とを受信し、受信したファイルＦとクラスタ数Ｎを示す情報を制御部４０２に出力する。
また、通信部４０１は、制御部４０２の制御に従って、制御部４０２から供給されたクラスタリング結果を示す情報Ｒをデータサーバ５００に送信する。
【００３５】
制御部４０２は、通信部４０１から供給されたファイルＦに含まれるデータに基づいて、クラスタ数がクラスタ数Ｎに到達するまで、ファイルＦに含まれるデータが属するクラスタを階層的に分割する。制御部４０２は、分割により得られたクラスタリング結果を示す情報Ｒを通信部４０１に出力し、クラスタリング結果を示す情報Ｒを通信部４０１からデータサーバ５００に送信させる。
【００３６】
図６は、本実施形態における計算サーバ４００の制御部４０２の論理的な構成を示す概略ブロック図である。制御部４０２は、識別情報割振部４２０と、クラスタリング処理部４３０とを備える。また、クラスタリング処理部４３０は、サブクラス割振部４３１と、属性選択部４４０と、変数推定部４３３と、エントロピー算出部４３４と、クラス抽出部４３５と、分割部４３６と、クラスタ数比較部４３７とを備える。また、属性選択部４４０は、サブクラス間差異判定部４３２と、変数推定部４３３とを備える。
【００３７】
識別情報割振部４２０は、通信部４０１から供給されたファイルＦに含まれるデータ毎に固有のデータ識別情報を割り付ける。また、識別情報割振部４２０は、ファイルＦに含まれる属性に固有の属性識別情報を割り付ける。
具体的な識別情報割振部４２０の処理の一例を、図７を用いて説明する。図７は、ファイルＦに含まれるデータの構造を表現したテーブルＴ１の一例と、識別情報割振部４２０による処理後のデータの構造を表現したテーブルＴ２の一例とが示された図である。
【００３８】
テーブルＴ１において、データ（例えば、映画のタイトル）と属性（例えば、ユーザ名）とに関連付けられて、観測値（０または１の値で、例えば、ユーザが映画毎にその映画を鑑賞したか否かの情報で、１が鑑賞した場合で０が鑑賞していない場合を示す）が示されている。
テーブルＴ１において、データＸＸのように、ファイルＦに含まれるデータが示されている。また、テーブルＴ１において、属性ＹＣのように、ファイルＦに含まれる属性が示されている。
【００３９】
テーブルＴ２において、各観測値（０または１の値）が、データを識別するデータ識別情報の一例であるデータｉ（ｉはデータのインデックスで、ｉは１からｌまでの整数）と、属性を識別する属性識別情報の一例である属性ｊ（ｊは属性のインデックスで、ｊは１からＪまでの整数）とに関連付けられている。
【００４０】
識別情報割振部４２０は、例えば、図７のテーブルＴ２に示すように、データ毎にデータ識別情報を割り振り、属性毎に属性識別情報を割り振る。これにより、識別情報割振部４２０は、各観測値ｙｉｊを、データ識別情報であるデータｉと属性識別情報である属性ｊとに関連付ける。識別情報割振部４２０は、各観測値ｙｉｊを示す情報を、データｉを示す情報と属性ｊを示す情報と共にサブクラス割振部４３１に出力する。
【００４１】
図６に戻って、サブクラス割振部４３１は、識別情報割振部４２０から供給されたデータｉに対し、仮にランダムにサブクラスを割り振る。サブクラス割振部４３１は、データｉ毎に関連付けられたサブクラスを示す情報を、各観測値ｙｉｊを示す情報とデータｉを示す情報と属性ｊを示す情報と共にサブクラス間差異判定部４３２に出力する。
サブクラス割振部４３１は、クラスタ数比較部４３７からクラスタ数が指定のクラスタ数Ｎに到達していない旨の情報を受け取った場合、または変数推定部４３３から計算が規定回数に到達していない旨の情報を受け取った場合、上記処理を繰り返す。
【００４２】
上記サブクラス割振部４３１の処理の図８の例を用いて説明する。図８は、サブクラス割振部４３１によりデータ毎にサブクラスが割り振られた１例を示すテーブルＴ３である。同図のテーブルＴ３の領域Ｒ８１に示されるように、サブクラス０またはサブクラス１が、データ１〜データＩまでランダムに割り振られている。例えば、データ１に対しては、サブクラス０が割り振られ、データＩに対しては、サブクラス１が割り振られている。
【００４３】
図６に戻って、サブクラス間差異判定部４３２は、属性ｊ毎にサブクラス間で観測値に差異が有るか否か判定する。そして、サブクラス間差異判定部４３２は、属性ｊ毎に観測値ｙｉｊがサブクラス間で違いがない場合には、その属性を仮に共通属性とし、サブクラスに固有であるか否かを示す固有フラグｒを０にする。
一方、サブクラス間差異判定部４３２は、属性ｊ毎に観測値ｙｉｊがサブクラス間で違いがない場合には、その属性を仮にサブクラス固有の属性とし、サブクラスに固有であることを示す固有フラグｒを１にする。これにより、サブクラス間差異判定部４３２は、属性ｊ毎にサブクラスに固有であるか否かを示す固有フラグｒの値を定める。
【００４４】
図９を用いて、サブクラス間差異判定部４３２の上記処理について説明する。図９は、図８のテーブルＴ３の観測値において、サブクラスに固有であるか否かを示す固有フラグｒの値の一例が示されたテーブルＴ４である。同図のテーブルＴ４において、図８のテーブルＴ３において、属性１、２および４は、サブクラス０（データ１）の場合に観測値が０で、サブクラス１（データＩ）の場合に観測値が１であり、サブクラス間で観測値が異なるので、固有フラグｒの値が１である。
【００４５】
一方、属性３およびＪは、サブクラス０（データ１）の場合に観測値が１で、サブクラス１（データＩ）の場合に観測値が１であり、サブクラス間で観測値が同じであるので、固有フラグｒの値が０である。
このように、サブクラス間差異判定部４３２は、クラスｋの属性ｊがサブクラス間で共通であるデータの数であるサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を算出する。ここで、ｎｋｊ０（〜）は、ｎｋｊ０の上に記号〜が付された記号である。また、ｎｋｊ１（〜）は、ｎｋｊ１の上に記号〜が付された記号である。また、サブクラス間差異判定部４３２は、クラスｋの属性ｊがサブクラスに固有であるデータの数であるサブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を算出する。
サブクラス間差異判定部４３２は、算出したサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を示す情報と、サブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を示す情報とを変数推定部４３３に出力する。
【００４６】
変数推定部４３３は、サブクラス間差異判定部４３２から入力されたサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を示す情報と、サブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を示す情報とに基づいて、ギブスサンプリングを用いて、クラスｋおよび属性ｊ毎に固有フラグｒｋｊの値（０または１）を推定する。ここで、ｋはクラスを識別する識別情報である。また、変数推定部４３３は、ギブスサンプリングを用いて、クラスｋおよびデータｉ毎にサブクラスを識別するサブクラス識別情報ｚｋｉの値（０または１）を推定する。これにより、クラスｋに含まれるデータｉ毎にデータｉが属するサブクラスを推定することができる。
【００４７】
変数推定部４３３は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達していない場合、サブクラス割振部４３１に計算が規定回数に到達していない旨の情報を出力する。
一方、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達した場合、変数推定部４３３は、推定した固有フラグｒｋｊの値を示す情報と、サブクラスを指定するサブクラス識別情報ｚｋｉの値を示す情報とをエントロピー算出部４３４に出力する。
【００４８】
エントロピー算出部４３４は、分割し得るクラスタである分割対象クラスタ毎にそのクラスタを分割した際の条件付きエントロピーを算出する。ここで、クラスタリングする前は全てのデータｉが１つのルートクラスタに入っているとみなせる。ゆえに、分割部４３６は、当該ルートクラスタを分割する際には、どちらのクラスタが分割されるか決定する必要がないので、エントロピー算出部４３４は、条件付きエントロピーを算出する必要はない。
【００４９】
一方、その全てのデータｉが、２つ以上のクラスタに分割された後には、現在存在するクラスタのうちどのクラスタを分割するか決定するために、エントロピー算出部４３４は、クラスタが分割された場合の条件付きエントロピーが未だ算出されていないクラスタに対して、クラスタが分割された場合の条件付きエントロピーを算出する。これにより、既に算出されているクラスタが分割された場合の条件付きエントロピーを再度算出する必要がないので、計算コストを削減することができる。
【００５０】
エントロピー算出部４３４は、算出した条件付きエントロピーを示す情報を、分割対象クラスタを識別するクラスタ識別情報に関連づけてクラスタ抽出部４３５に出力する。
【００５１】
クラスタ抽出部４３５は、未だ分割されていないクラスタに対して、そのクラスタが分割された場合の条件付きエントロピーを示す情報をクラスタを識別するクラスタ識別情報に関連づけて保持している。
クラスタ抽出部４３５は、エントロピー算出部４３４から供給された条件付きエントロピーと、保持している条件付きエントロピーのうち、エントロピーが最小となる分割対象クラスタを抽出する。クラスタ抽出部４３５は、抽出した分割対象クラスタを示す情報を分割部４３６に供給する。
【００５２】
また、クラスタ抽出部４３５は、エントロピーが最小となる分割対象クラスタのクラスタ識別情報に関連付けられた条件付きエントロピーを示す情報を消去し、分割されなかったクラスタを識別するクラスタ識別情報に関連付けられた条件付きエントロピーを示す情報を保持する。
【００５３】
分割部４３６は、クラスタ抽出部４３５から供給された分割対象クラスタを分割する際に、変数推定部４３３により推定されたデータｉが属するサブクラスを示す情報に基づいて、分割対象クラスタを２つのクラスタに分割する。
【００５４】
クラスタ数比較部４３７は、識別情報割振部４２０から供給されたクラスタ数Ｎと、現在のクラスタ数とを比較し、現在のクラスタ数が現在のクラスタ数Ｎに到達していたら、クラスタ結果を示す情報Ｒを通信部４０１に出力する。
一方、現在のクラスタ数が現在のクラスタ数Ｎに到達していない場合、クラスタ数比較部４３７は、クラスタ数が指定のクラスタ数Ｎに到達していない旨の情報をサブクラス割振部４３１に出力する。
【００５５】
続いて、変数推定部４３３の処理の詳細について図１０、１１および１２を用いて説明する。図１０は、本実施形態における観測値ｙを推定する処理が示されたグラフィカルモデルである。同図において、各変数または定数の関係が示されている。
同図において、α、β、γはハイパーパラメータで、予め定められた定数である。ｋはクラスを識別する識別情報である。
【００５６】
同図において、パラメタφｋは、ハイパーパラメータαを構成する変数α０とα１とから計算されることが示されている。パラメタφｋは、サブクラスを識別するサブクラス識別情報ｚｉが１を出力する確率であり、０〜１の連続値を取る。ここで、パラメタφｋの確率分布は、クラスｋ毎にハイパーパラメータαを構成する定数α０と定数α１とを引数とするディリクレ（Ｄｉｒｉｃｈｌｅｔ）分布で表される。
【００５７】
同図において、サブクラス識別情報ｚｉは、クラスｋとパラメタφｋによって算出される。本実施形態では、クラスｋは２つのサブクラスに分割されるので、サブクラス識別情報ｚｉは、０または１の値を取る。ここで、サブクラス識別情報ｚｉの確率分布は、データｉ毎およびクラスｋ毎に、パラメタφｋを引数とする二項（Ｂｉｎｏｍｉａｌ）分布で表される。
【００５８】
パラメタλｋｊは、固有フラグｒが１を出力する確率であり、０〜１の連続値を取る。パラメタλｋｊは、クラスｋとハイパーパラメータβを構成する定数β０と定数β１とから算出される。具体的には、パラメタλｋｊの確率分布は、クラスｋ毎およびデータｊ毎に、ハイパーパラメータβを構成する定数β０と定数β１とを引数とするベータ（Βｅｔａ）分布で表される。
【００５９】
固有フラグｒは、使用する変数を指定するフラグであり、０また１の値を取り得る。観測値ｙを推定する際に、固有フラグｒの値が１のときにはサブクラスｚｉに固有のパラメタθが使用され、固有フラグｒの値が０のときにサブクラスｚｉに共通のパラメタθ（チルタ）が使用される。ここで、図１０におけるθの上に〜が示されている記号をθ（チルタ）と称し、以後θ（チルタ）を用いて説明する。
【００６０】
固有フラグｒは、クラスｋとパラメタλｋｊとから算出される。具体的には、固有フラグｒｋｊの確率分布は、クラスｋ毎およびデータｊ毎に、パラメタλｋｊを引数とするベルヌーイ（Ｂｅｅｒｎｏｕｌｌｉ）分布で表される。
【００６１】
パラメタθｋｌｊは、固有フラグｒが１のとき、すなわちパラメタθｋｌｊがサブクラスｚｉに固有のときに用いられる変数である。一方、パラメタθｋｌｊ（チルタ）は、固有フラグｒが０のとき、すなわちパラメタθｋｌｊがサブクラスｚｉに共通のときに用いられる変数である。
パラメタθｋｌｊは、クラスｋと、サブクラスｌと、ハイパーパラメータγを構成する変数γ１０および変数γ１１とから算出される。具体的には、パラメタθｋｌｊの確率分布は、ハイパーパラメータγを構成する変数γ１０および変数γ１０を引数とするベータ分布で表される。
【００６２】
また、パラメタθｋｌｊ（チルタ）は、クラスｋと、サブクラスｌと、ハイパーパラメータγを構成する変数γ００および変数γ０１とから算出される。具体的には、パラメタθｋｌｊ（チルタ）の確率分布は、ハイパーパラメータγを構成する変数γ００および変数γ０１を引数とするベータ分布で表される。
【００６３】
観測値ｙｉｊは、サブクラスｚｉ、固有フラグｒｊ、パラメタθｚｊ、パラメタθｚｊ（チルタ）によって推定される値である。具体的には、観測値ｙｉｊの確率分布は、データｉ毎および属性ｊ毎に、パラメタθｚｊおよびパラメタθｚｊ（チルタ）を引数とするベルヌーイ（Ｂｅｅｒｎｏｕｌｌｉ）分布で表される。
【００６４】
図１０において、領域Ｒ１０１内の変数は、データ数Ｉの回数だけ繰り返し算出される。領域Ｒ１０２内の変数は、クラスタ毎に分割しうる分割数Ｌ（本実施形態では、２）と属性の数Ｊを乗じた値ＬＪ（本実施形態では、２Ｊ）の回数だけ繰り返し算出される
【００６５】
図１１は、固有フラグｒの値によりパラメタθまたはパラメタθ（チルタ）のいずれかが選択されることについて説明するための図である。同図において、棒グラフの中の色が黒である領域が観測値ｙｉｊが１が出現する確率であり、棒グラフの中の色が白である領域が観測値ｙｉｊが０が出現する確率である。
【００６６】
同図において固有フラグｒが１の場合、サブクラスｚがｌのとき、観測値ｙｉｊとして１が出現する確率θｌｊが観測値ｙｉｊとして０が出現する確率１−θｌｊより大きいことが示されている。一方、サブクラスｚがｌ´のとき、観測値ｙｉｊとして０が出現する確率θｌｊが観測値ｙｉｊとして１が出現する確率１−θｌｊより大きいことが示されている。すなわち、サブクラスｌとサブクラスｌ´との間で、観測値ｙｉｊとして１が出現する確率と０が出現する確率の比が、逆転していることが示されている。
【００６７】
一方、固有フラグｒが０の場合、サブクラスｌにおいて確率θｌｊが確率１−θｌｊより大きく、サブクラスｌ´における確率θｌ´ｊが確率１−θｌ´ｊより大きいことが示されている。すなわち、サブクラスｌとサブクラスｌ´との間で、観測値ｙｉｊとして１が出現する確率は０が出現する確率よりも共通して大きいことが示されている。
【００６８】
そこで、固有フラグｒが０の場合には、サブクラスに共通のパラメタθｌｊ（チルタ）が使用されることが示されている。このようにして、属性選択部４４０は、サブクラス間の属性を比較することにより固有フラグｒを選択する。これにより、クラスタリング処理部４３０は、選択された固有フラグｒに基づいて、サブクラスに固有のパラメタθｌｊとサブクラスに共通のパラメタθｌｊ（チルタ）のいずれかを使用するかを選択し、観測値ｙｉｊを推定することができる。そして、クラスタリング処理部４３０は、推定された観測値ｙｉｊが実際の観測値ｙｉｊと近くなるように、変数ｒと変数ｚを算出する。
【００６９】
図１２は、変数推定部４３３の論理的な構成を示す概略ブロック図である。変数推定部４３３は、クラス帰属判定部４３３＿１と、属性振分部４３３＿５とを備える。
クラス帰属判定部４３３＿１は、データｉ毎に当該データｉが帰属するサブクラスｚを推定する。ここで、クラス帰属判定部４３３＿１は、変数ｚ確率算出部４３３＿２と変数ｚ算出部４３３＿３とを備える。
【００７０】
図１０に示されるように、各変数に確率分布を導入したことで、クラスｋとハイパーパラメータα、βおよびγが与えられたという条件付きのデータ全体の同時確率Ｐ（ｙ，ｚ，ｒ，φ，λ，θ，θ（チルタ）｜ｋ，α，β，γ）は次の式（１）で表される。
【００７１】
【数１】
【００７２】
この同時確率を用いることによって、変数推定部４３３は、潜在するサブクラスにデータを割り振ることと、各サブクラスに固有の属性の検出とを同時に行うことができる。
ここで、式（１）がφ，λ，θで積分されると、以下の式（２）で表される。
【００７３】
【数２】
【００７４】
ここで、Γはガンマ関数である。また、ｎｋ０はクラスｋのサブクラス０のデータの数であり、ｎｋ１はクラスｋのサブクラス１のデータの数であり、ｎｋｊはクラスｋにおいて属性ｊを有するデータ数、ｎｋ０は属性０を有するクラスｋのデータ数である。また、ｎｋ０ｊ１（ｎｋ０ｊ０）は、クラスｋにおけるサブクラス０のデータであって、サブクラスに固有（サブクラス間で共通）のデータの数である。また、ｎｋ１ｊ１（ｎｋ１ｊ０）は、クラスｋにおけるサブクラス１のデータであって、サブクラスに固有（サブクラス間で共通）のデータの数である。ｎｋｊ１（ｎｋｊ０）は、クラスｋにおいて、サブクラスに固有（サブクラス間で共通）のデータ数である。
【００７５】
各変数が確率分布で表されるので、式（１）で現れるパラメタλ、φ、θおよびθ（チルタ）は、式（１）が積分されることによって解析的にその値が消え、式（２）ではパラメタλ、φ、θおよびθ（チルタ）が現れない。
【００７６】
変数ｚ確率算出部４３３＿２は、サブクラス間差異判定部４３２から供給された情報が示すサブクラス共通数ｎｋｊ０とサブクラス固有数ｎｋｊ１とを用いて、データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出する。具体的には、例えば、変数ｚ確率算出部４３３＿２は、属性毎の固有フラグｒの初期値を示す情報を用いて、サブクラスｚｉがｌである条件付き確率Ｐ（ｚｉ＝ｌ）を以下の式（３）に従って算出する。
【００７７】
【数３】
【００７８】
ここで、ｚ＼ｉは、データｉ以外のデータでサブクラスに割り振られた数である。また、ｎｋ＼ｉは、データｉ以外でクラスｋを有するデータの数であり、ｎｋｌ＼ｉは、データｉ以外クラスｋの中のサブクラスｌに割り振られたデータの数である。また、ｎｋ＼ｉｊ０（ｎｋ＼ｉｊ０）は、データｉ以外でクラスｋを有するデータであって、観測値ｙｉｊ＝０（ｙｉｊ＝１）に割り振られたデータの数である。また、ｎｋｌ＼ｉｊ０（ｎｋｌ＼ｉｊ０）は、データｉ以外でクラスｋの中のサブクラスｌに割り振られたデータであって、観測値ｙｉｊ＝０（ｙｉｊ＝１）に割り振られたデータの数である。
【００７９】
各変数が確率分布で表されるので、式（３）において、パラメタλ、φ、θおよびθ（チルタ）が現れない。ゆえに、変数推定部４３３は、パラメタλ、φ、θおよびθ（チルタ）を計算する必要がないので、計算量を減らすことができる。
【００８０】
変数ｚ確率算出部４３３＿２は、データｉ毎に算出した条件付き確率Ｐ（ｚｉ＝ｌ）を示す情報を変数ｚ算出部４３３＿３に出力する。
変数ｚ算出部４３３＿３は、乱数を算出する。変数ｚ算出部４３３＿３は、変数ｚ確率算出部４３３＿２から供給された条件付き確率Ｐ（ｚｉ＝ｌ）が、算出した乱数よりも大きい場合には、変数ｚを１とする。一方、変数ｚ算出部４３３＿３は、条件付き確率Ｐ（ｚｉ＝ｌ）が、算出した乱数以下の場合、変数ｚを０とする。
【００８１】
変数ｚ算出部４３３＿３は、この処理をデータｉ毎に算出された条件付き確率Ｐ（ｚｉ＝ｌ）を示す情報全てについて行い、現在のステップにおけるデータｉ毎にサブクラス識別情報ｚｉ（０または１の値）を算出する。
【００８２】
変数ｚ算出部４３３＿３は、算出したータｉ毎のサブクラス識別情報ｚｉの変化量を示す情報をエントロピー算出部４３４に出力する。また、変数ｚ算出部４３３＿３は、変化量を算出した旨の情報を属性振分部４３３＿５の後述する変数ｒ確率算出部４３３＿６に出力する。
【００８３】
続いて、属性振分部４３３＿５について説明する。属性振分部４３３＿５は、属性ｊ毎に固有のフラグｒｊの値を推定する。換言すれば、属性振分部４３３＿５は、属性ｊ毎に当該属性ｊがサブクラス間で固有の属性かサブクラス間で共通の属性かを推定する。
属性振分部４３３＿５は、変数ｒ確率算出部４３３＿６と、変数ｒ算出部４３３＿７とを備える。
【００８４】
変数ｒ確率算出部４３３＿６は、変数ｚ算出部４３３＿３から変化量を算出した旨の情を受け取ると、サブクラス間差異判定部４３２から供給された情報が示すサブクラス共通数ｎｋｊ０とサブクラス固有数ｎｋｊ１とに基づいて、属性ｊ毎に当該属性がサブクラスに固有である確率である固有フラグｒの条件付き確率Ｐ（ｒｊ）を以下の式（４）に従って算出する。
【００８５】
【数４】
【００８６】
ここで、ｒ＼ｊは、ｊ以外の固定フラグｒであり、ｙ＼ｊは、ｊ以外の観測値ｙである。各変数が確率分布で表されるので、式（４）においても、パラメタλ、φ、θおよびθ（チルタ）が現れない。ゆえに、変数推定部４３３は、パラメタλ、φ、θおよびθ（チルタ）を計算する必要がないので、計算量を減らすことができる。
【００８７】
変数ｒ確率算出部４３３＿６は、算出した属性ｊ毎の条件付き確率Ｐ（ｒｊ）を示す情報を変数ｒ算出部４３３＿７に出力する。
変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒ＝０の条件付き確率Ｐ（ｒｊ）よりも、現在のステップで算出された固有フラグｒ＝１の条件付き確率Ｐ（ｒｊ）が大きい場合、固有フラグｒを０から１に変更する。
一方、変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒ＝１の条件付き確率Ｐ（ｒｊ）よりも、現在のステップで算出された固有フラグｒ＝０の条件付き確率Ｐ（ｒｊ）が大きい場合、固有フラグｒを１から０に変更する。
【００８８】
上記２つに当てはまらない場合、変数ｒ算出部４３３＿７は、乱数を算出する。変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒの条件付き確率Ｐ（ｒｊ）を分母で、現在のステップで算出された固有フラグｒの条件付き確率Ｐ（ｒｊ）分子とする固有フラグｒの条件付き確率Ｐ（ｒｊ）の比率を算出する。
変数ｒ算出部４３３＿７は、算出した比率が、算出した乱数よりも大きい場合には、固有フラグｒを１とする。一方、変数ｒ算出部４３３＿７は、算出した比率が、算出した乱数以下の場合、固有フラグｒを０とする。
【００８９】
変数ｒ算出部４３３＿７は、クラスタ数が１の場合、この処理を属性ｊ毎に算出された条件付き確率Ｐ（ｒｊ）を示す情報全てについて行って、属性ｊ毎に固有フラグｒｊを決定する。
変数ｒ算出部４３３＿７は、クラスタ数が２以上の場合、その前までの処理で固有フラグｒが０となった属性以外の属性ｊについて、属性ｊ毎に固有フラグｒｊを決定する。
【００９０】
これにより、クラスタ数が２以上の場合、変数ｒ算出部４３３＿７は、その前までの処理で固有フラグｒが０となった属性以外についてのみ固有フラグｒｊを決定すればよいので、全ての属性で固有フラグｒｊを決定するのに比べて計算量を減らすことができる。
また、変数ｒ算出部４３３＿７が式（４）を用いて条件付き確率Ｐ（ｒｊ）を算出する際に、式（４）におけるガンマ関数の計算量が多いので、特に計算量を減らすことに貢献することができる。
【００９１】
続いて、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達した場合、現在の属性ｊ毎の固有フラグｒｊを示す情報をエントロピー算出部４３４に出力する。これにより、属性ｊ毎に当該属性ｊがサブクラスに固有であるかサブクラス間で共通であるかを決定することができる。
【００９２】
一方、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達していない場合、サブクラス割振部４３１に計算が規定回数に到達していない旨の情報を出力する。これにより、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達するまで、サブクラス割振部４３１はサブクラスを割り振り直させることができる。
【００９３】
なお、変数ｒ算出部４３３＿７は、変数ｒの変動量の総和が所定の閾値より小さくなるまで、サブクラス割振部４３１はサブクラスを割り振り直させてもよい。
具体的には、例えば、変数ｒ算出部４３３＿７は、直前のステップで算出された属性ｊ毎に算出された条件付き確率Ｐ（ｒｊ）を示す情報を保持している。変数ｒ算出部４３３＿７は、直前のステップの属性ｊの条件付き確率Ｐ（ｒｊ）に対する現在算出した属性ｊの条件付き確率Ｐ（ｒｊ）との変化量を算出する。
例えば、変数ｒ算出部４３３＿７は、直前のステップの属性ｊの条件付き確率Ｐ（ｒｊ）が０で、現在算出した属性ｊの条件付き確率Ｐ（ｒｊ）が１であるならば、変化量を１と算出する。
【００９４】
変数ｒ算出部４３３＿７は、上記処理を全ての属性ｊに対して行うことにより、属性ｊ毎の固有フラグｒｊの変化量を算出する。属性ｊ毎の固有フラグｒｊの変化量の絶対値の総和を算出し、算出した総和が所定の閾値より小さくなるまでサブクラス割振部４３１はサブクラスを割り振り直させるようにしてもよい。
【００９５】
以上の処理についてまとめると、属性選択部４４０は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、属性の値がサブクラス間で違いがない場合は、その属性の値をそのサブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とする。
また、属性選択部４４０は、属性毎にその属性がサブクラス間で固有である確率を算出し、その算出した確率に基づいて、その属性がサブクラス間で共通の属性かサブクラスに固有の属性かを判定する。
また、属性選択部４４０は、データ毎にそのデータに割り振られるサブクラスが所定のサブクラスである確率を算出し、算出した確率に基づいてデータ毎にそのデータに割り振られるサブクラスを推定する。
【００９６】
続いて、エントロピー算出部４３４は、変数ｒ算出部４３３＿７から供給された現在のデータｉ毎のサブクラス識別情報ｚｉに基づいて、条件付きエントロピーを算出する。具体的には、エントロピー算出部４３４は、以下の式（５）に従って、条件付きエントロピーＨ（Ｘ｜Ｙ）を算出する。
【００９７】
【数５】
【００９８】
ここで、Ｈ（Ｘ｜Ｙ）は、サブクラスの集合Ｙが与えられたときのデータの集合Ｘのエントロピーである。また、ｌはサブクラスのインデックスであり、Ｌはサブクラスの数であり、クラスタを２つのサブクラスに分割するので本実施形態ではＬは２である。また、Ｉはデータｉの数である。Ｐ（Ｘ＝ｘｉ｜Ｙ＝ｙｌ）は、データがｘｉでサブクラスがｙｌの条件付確率を表している。
【００９９】
エントロピー算出部４３４は、データにサブクラスを割り振る毎に、上記式（４）に従って、条件付きエントロピーを算出する。エントロピー算出部４３４は、算出した、条件付きエントロピーを示す情報をクラスタ抽出部４３５に出力する。
【０１００】
続いて、データベースサーバ５００について説明する。図１３は、本実施形態におけるデータベースサーバ５００のハードウェアの構成を示す概略ブロック図である。データベースサーバ５００は、通信部５０１と、制御部５０２と、クラスタリング結果記憶部５０３とを備える。
【０１０１】
通信部５０１は、計算サーバ４００から送信されたクラスタリング結果を示す情報Ｒを受信する。通信部５０１は、制御部５０２の制御に従って、受信したクラスタリング結果を示す情報Ｒをクラスタリング結果記憶部５０３に供給する。
また、通信部５０１は、受信したクラスタリング結果を示す情報Ｒをサービスサーバ２００に送信する。
【０１０２】
制御部５０２は、通信部５０１により受信されたクラスタリング結果を示す情報Ｒをクラスタリング結果記憶部５０３に記憶させる。これにより、クラスタリング結果記憶部５０３には、クラスタリング結果を示す情報Ｒが記憶される。
【０１０３】
図１４は、クラスタリング結果記憶部５０３に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ５である。同図において、データの識別情報と親クラスタの識別情報と所属クラスタの識別情報とが関連付けられている。ここで、所属クラスタとは、データが最終的に分類されたクラスタであり、親クラスタとは、所属クラスタを包含するクラスタであって所属クラスタが分割される直前のクラスタである。
【０１０４】
例えば、データ１の親クラスタの識別情報１であり、所属クラスタの識別情報が２であることが示されている。
このように、クラスタリング結果記憶部５０３には、データの識別情報とデータが属する所属クラスタの識別情報と当該所属クラスタの親クラスタの識別情報とが関連付けられて記憶される。
【０１０５】
図１５は、クラスタリング結果記憶部５０３に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ６である。同図において、固有フラグｒの値が、属性の識別情報とクラスタ識別情報（クラスタ１〜クラスタＮ）とに関連付けられている。例えば、属性１はクラスタ１では固有フラグｒが１なのでクラスタ１に固有の属性であるが、クラスタＮでは固有フラグｒが０なのでクラスタ間で共通の属性であることが示されている。
【０１０６】
図１６は、クラスタの階層構造の一例が示された図である。前提として、映画のタイトルがデータであり、属性はユーザの識別情報であるユーザｉｄである。観測値ｙはユーザｊが映画のタイトルＴｉを鑑賞したか否かを示す情報（鑑賞していれば１、鑑賞していなければ０）である。例えば、ユーザｊが映画のタイトルＴｉを鑑賞した場合には、その観測値は１であり、鑑賞していない場合にはその観測値は０である。ここで、ユーザが１０人であり、各ユーザにユーザｉｄが１から１０まで割り振られていることを想定する。
【０１０７】
同図において、最初の分岐Ｂ１６１では、全データが属していたクラスタｋ０は、クラスタｋ００とクラスタｋ０１に分割されている。クラスタｋ００に固有の属性は、ユーザｉｄが１、２、３、４、５である。これは、クラスタｋ００は、ユーザｉｄが１、２、３、４、５のユーザが鑑賞した映画のクラスタであることを意味する。
【０１０８】
一方、クラスタｋ０１に固有の属性は、ユーザｉｄが６、７、８、９、１０である。これは、クラスタｋ０１は、ユーザｉｄが６、７、８、９、１０のユーザが鑑賞した映画のクラスタであることを意味する。
【０１０９】
クラスタｋ００に固有の属性と、クラスタｋ０１に固有の属性とを比較すると、クラスタｋ００の共通属性はユーザｉｄが５以下であることから、ユーザｉｄの数が６より小さいユーザが鑑賞した映画タイトルが分類されていると解釈できる。一方、クラスタｋ０１の共通属性はユーザｉｄが６以上であるので、ユーザｉｄの数が６以上のユーザが鑑賞した映画タイトルが分類されていると解釈できる。
【０１１０】
このように、クラスタリング処理部４３０は、クラスタを階層的に分割するので、クラスタ結果を見た人は、クラスタに固有の属性を比較することにより、クラスタ間の関係を理解することができる。
【０１１１】
また、分岐Ｂ１６２では、クラスタｋ００は２つのクラスタｋ０００とクラスタｋ００１とに分割されている。クラスタｋ０００に固有の属性は、ユーザｉｄが奇数である。これは、クラスタｋ０００は、ユーザｉｄが１、２、３、４、５のうちユーザｉｄが奇数であるという条件を満たすユーザｉｄ（１、３、５）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１２】
同様に、クラスタｋ００１に固有の属性は、ユーザｉｄが偶数である。クラスタｋ００１は、ユーザｉｄが１、２、３、４、５のうちユーザｉｄが偶数であるという条件を満たすユーザｉｄ（２、４）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１３】
また、分岐Ｂ１６３では、クラスタｋ０１は２つのクラスタｋ０１０とクラスタｋ０１１とに分割されている。クラスタｋ０１０に固有の属性は、ユーザｉｄが奇数である。これは、クラスタｋ０００は、ユーザｉｄが６、７、８、９、１０のうちユーザｉｄが奇数であるという条件を満たすユーザｉｄ（７、９）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１４】
同様に、クラスタｋ０１１に固有の属性は、ユーザｉｄが偶数である。クラスタｋ００１は、ユーザｉｄが６、７、８、９、１０のうちユーザｉｄが偶数であるという条件を満たすユーザｉｄ（６、８、１０）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
このように、クラスタリング処理部４３０は、クラウタ間で共通の属性を削除し、各クラスタに固有の属性を抽出するので、人にクラスタを構成するデータの特徴を理解させることができる。
【０１１５】
更に、クラスタリング処理部４３０は、クラスタを階層化するので、クラスタを構成するデータは所属クラスタに固有の属性と所属クラスタの親クラスタに固有の属性とを有するので、人にクラスタを構成するデータの特徴を理解させることができる。
また、クラスタリング処理部４３０は、クラスタが階層化されることで、クラスタ間の相対的な近さがわかり、人にデータ全体の構造が理解させることができる。
【０１１６】
図１７は、映画のタイトルがクラスタリングされた結果の一例が示された図である。同図において、図１６に示されたクラスタｋ０００、クラスタｋ００１、クラスタｋ０１０、クラスタｋ０１１毎に各クラスタに含まれる映画のタイトルが示されている。ここで、図１７に示されているタイトル１からタイトル２２は、映画のタイトルである。
クラスタｋ０００を構成するデータはタイトル１から６までの６つの映画タイトルであり、クラスタｋ００１を構成するデータはタイトル７から１１までの５つの映画タイトルであり、クラスタｋ０１０を構成するデータはタイトル１２から１６までの５つの映画タイトルであり、クラスタｋ０１１を構成するデータはタイトル１７から２２までの６つの映画タイトルであることが示されている。
【０１１７】
図１８は、本実施形態における計算サーバ４００の処理の流れを示すフローチャートである。まず、制御部４０２は、通信部４０１を介してファイルサーバ３００から供給されたクラスタ数Ｎを示す情報を受け取る（ステップＳ１０１）。識別情報割振部４２０は、クラスタリング対象のデータ及び属性に識別情報を割り振る（ステップＳ１０２）。
【０１１８】
次に、サブクラス割振部４３１は、それぞれのクラスタにおいて各データが属するサブクラスを割り振る（ステップＳ１０３）。次に、サブクラス間差異判定部４３２は、属性ｊ毎に固有フラグｒｊの初期値を決定する（ステップＳ１０４）。次に、変数推定部４３３は、データｉ毎のサブクラス識別情報ｚｉと属性ｊ毎の固有フラグｒｊの値を推定する（ステップＳ１０５）。
【０１１９】
変数ｒ算出部４３３＿７は、計算の回数が規定回数に達したか否か判定する（ステップＳ１０６）。計算の回数が規定回数に達していない場合（ステップＳ１０６ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０３の処理に戻る。
一方、計算の回数が規定回数に達した場合（ステップＳ１０６ ＹＥＳ）、エントロピー算出部４３４は、現在のクラスタ数が２以上か否か判定する（ステップＳ１０７）。現在のクラスタ数が１の場合（ステップＳ１０７ ＮＯ）、分割部４３６は全データｉを２つのクラスタに分割し（ステップＳ１０８）、クラスタリング処理部４３０は、ステップＳ１１２の処理に進む。
一方、現在のクラスタ数が２以上の場合（ステップＳ１０７ ＹＥＳ）、エントロピー算出部４３４は、条件付きエントロピーを算出する（ステップＳ１０９）。
【０１２０】
次に、エントロピー算出部４３４は、現在存在する全てのクラスタに対して、当該クラスタが分割された場合の条件付きエントロピーを算出したか否か判定する（ステップＳ１１０）。現在存在する全てのクラスタに対して当該クラスタが分割された場合の条件付きエントロピーを算出していない場合（ステップＳ１１０ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０３に戻り、条件付きエントロピーが算出されていないクラスタに対してステップＳ１０３の処理を行う。
【０１２１】
一方、現在存在する全てのクラスタに対して当該クラスタが分割された場合の条件付きエントロピーを算出した場合（ステップＳ１１０ ＹＥＳ）、クラス抽出部４３５は、条件付きエントロピーが最小となる分割対象クラスタを抽出する（ステップＳ１１１）。
次に、分割部４３６は、抽出された分割対象クラスタを２つのクラスタに分割する（ステップＳ１１２）。
【０１２２】
クラスタ数比較部４３７は、分割部４３６による分割後のクラスタ数がファイルサーバ３００から供給されたクラスタ数Ｎに到達したか否か判定する（ステップＳ１１３）。分割後のクラスタ数がクラスタ数Ｎに到達していない場合（ステップＳ１１３ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０２の処理に戻る。
一方、分割後のクラスタ数がクラスタ数Ｎに到達した場合（ステップＳ１１３ ＹＥＳ）、クラスタ数比較部４３７は、クラスタ結果を示す情報Ｒを通信部４０１に出力する（ステップＳ１１４）。以上で、本フローチャートの処理を終了する。
【０１２３】
以上、本実施形態の計算サーバ４００は、クラスタを分割する毎に、各属性が分割後の複数のクラスタに共通する属性か分割後のクラスタに固有の属性かを決定し、各データが属するクラスタを階層的に分割する。
これにより、計算サーバ４００は、クラスタ固有の属性が減らすことができるので、クラスタの特徴を理解することが容易となる。また、計算サーバ４００は、クラスタを階層化したので、クラスタ間の関係を理解することが容易となる。
【０１２４】
また、本実施形態の計算サーバ４００は、クラスタリング処理の際に各変数を確率分布でモデル化したので、クラスタリング結果に数学的な妥当性を持たせることができる。その結果、同じ条件化では、計算サーバ４００は、常に同じクラスタリング結果を出力することができる。これにより、どんなユーザが計算サーバ４００を用いてデータをクラスタリングしても同じ結果が得られるので、クラスタリング手法に精通していないユーザでも容易に数学的に妥当性のあるクラスタリング結果を得ることができる。
【０１２５】
＜効果を実証する実験データ＞
続いて、本実施形態における手法ＨＳＣの効果について立証するために行った実験結果について、説明する。
【０１２６】
図１９は、本実施形態におけるクラスタリング処理に係る時間と、従来手法のクラスタリング処理に係る時間とを比較した図である。同図において、縦軸は時間（秒）であり、横軸は属性の数である。同図に置いて、本実施形態における手法はＨＳＣ（Ｈｉｅｒａｒｃｈｉｃａｌ Ｓｕｂｓｅｔ Ｃｌｕｓｔｅｒｉｎｇ）であり、従来手法は、非特許文献１に記載されたＳＣＢＳ（Ｓｕｂｓｅｔ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅ）である。
【０１２７】
また、括弧内のＮは、Ｎｅｔｆｌｉｘデータを用いてクラスタリングした結果であることを示し、括弧内のＰは、研究論文のデータを用いてクラスタリングした結果であることを示している。
【０１２８】
ここで、Ｎｅｔｆｌｉｘデータは、１９９９年１１が１１日から２００５年１２月３１日までに１００，４８０，５０７の採点（レーティング）記録からなる。採点記録は、４８０，１８９人の採点者によって採点された１７,７７０の映画からなる。
最初に、少なくとも２０映画を採点した採点者と少なくとも１００人のユーザによって採点された映画が選択されたこの前処理により、データセットを１３６，５８９人の採点者によって採点された９，２６４映画からなる８５，７３０，２０３採点記録までに削減した。各採点記録は、映画タイトルを識別する映画タイトルｉｄと、採点者を識別する採点者ｉｄと、採点と、時刻からなる。
【０１２９】
一方、研究論文のデータは、２００１年から２００８年までにACM CIKM, SIGIR, KDD, and WWWの予稿集における研究論文からなっている。研究論文に登場するストップワード、番号、コーパスに登場する回数が５回未満の単語が削除された。これにより、研究論文のデータは、全部で３０７８文章と２０２８６の種の単語からからなっている。
【０１３０】
同図に置いて、属性が２００００のときは、本実施形態における手法ＨＳＣと従来手法ＳＣＢＳとでクラスタリング処理にかかる時間にほとんど差がない。しかし、属性が増えるに従って、本実施形態における手法ＨＳＣは、従来手法ＳＣＢＳよりもクラスタリング処理にかかる時間が短くなっている。
すなわち、従来手法ＳＣＢＳは、属性の数が増えると処理にかかる時間が線形に増えるのに対して、本実施形態における手法ＨＳＣは、属性の数が増えたことによる影響を受けずに、処理にかかる時間をほぼ一定に保つことができる。
【０１３１】
以下、図１９の実験結果が得られた実験の方法について説明する。まず、研究論文データの文章の数と合わせるために、９，２６４の映画からランダムに３０７８の映画が選択された。次に、採点者（単語）の数が２０，０００から１００，０００まで増加させた。
次に、各データセットから採点者（論文）×映画（単語）の行列からなるデータ行列が準備された。
【０１３２】
次に、ギブスサンプリングの試行回数が１００にセットされ、クラスタの数を２０がセットされて、両方の手法が実行された。これにより、ルートクラスタから始まってクラスタ数が２０になるまでクラスタが繰り返し分割された。そして、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳを用いて、採点者（単語）の数を変える毎に、映画（文章）がクラスタに分類された。
【０１３３】
以上、本実施形態における計算サーバ４００は、クラスタを分割する毎に、各属性が分割後の複数のクラスタに共通する属性か分割後のクラスタに固有の属性かを決定するので、属性の数が多くなっても処理にかかる時間が従来手法ＳＣＢＳよりも増えない。換言すれば、本実施形態における計算サーバ４００は、クラスタを分割する毎にクラスタ間で共通の属性が増えていくので、計算量を減らすことができる。
【０１３４】
これにより、本実施形態における計算サーバ４００は、属性が所定に数より多くなるほどクラスタリングにかかる処理時間を従来手法ＳＣＢＳに比べて短縮することができる。換言すれば、本実施形態における計算サーバ４００は、属性の数が増加しても従来手法ＳＣＢＳと比べて計算量が増加しないという有利な効果を有する。
【０１３５】
図２０は、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとのパープレキシティを比較したテーブルである。同図に置いて、Ｎｅｔｆｌｉｘデータと、研究論文（Ｒｅｓｅａｒｖｈ Ｐａｐｅｒ）のデータとを用いたときの、本実施形態の手法ＨＳＣのパープレキシティの値と従来手法ＳＣＢＳのパープレキシティの値が示されている。ここで、パープレキシティ（ｐｅｒｐｌｅｘｉｔｙ）は、タスクの複雑性を表す尺度であり、クラスタリングの予測が正しければ、パープレキシティの値が小さくなる。
【０１３６】
同図において、Ｎｅｔｆｌｉｘデータについても、研究論文（Ｒｅｓｅａｒｖｈ Ｐａｐｅｒ）のデータを用いてクラスタリングした場合においても、本実施形態の手法ＨＳＣの方が従来手法ＳＣＢＳよりもパープレキシティが片側ｔ検定で有意に小さくなっていることが示されている。ここで、片側ｔ検定で従来手法ＳＣＢＳよりもはＰ＜０．０５で異なる場合、‘＊’の印が付けられ、Ｐ＜０．０１で異なる場合に、‘＊＊’の印が付けられている。
【０１３７】
これにより、本実施形態の手法ＨＳＣは、従来手法ＳＣＢＳよりもクラスタリングの予測が正しいという有利な効果を有する。
これは、従来手法ＳＣＢＳは、各属性は、各クラスタに固有か全クラスタに共通であるかの２者択一であるのに対し、本実施形態の手法ＨＳＣが様々なクラスタ間でどんな属性でも共通にできるという点で柔軟性があるからである。
【０１３８】
ここで、上記パープレキシティＰＰＸは、１００の異なるチェーン（ｃｈａｉｎｓ）からの１００個のデータを用いて、以下の式（６）に従って、算出される。
【０１３９】
【数６】
【０１４０】
ここで、Ｗはテスト属性の数、Ｇは（ギブス）サンプリング系列の異なり数、θｋｌｖｇは、モデルによってサンプリング系列の識別子ｇの中のクラスｋに付随するサブクラスｌにおける属性ｖにクラスｋが割り振られる確率である。また、ｇの上に〜が示されている記号をｇ（チルタ）と称し、θｋｌｖｇ（チルタ）は、モデルによってサンプリング系列の識別子ｇの中のクラスｋにおける属性ｖにクラスｋが割り振られる確率である。
【０１４１】
以下、図２０の実験結果が得られた実験の方法について説明する。この実験では生データをコーパスにある文章（Ｎｅｔｆｌｉｘデータの場合は文章で、研究論文の場合は単語）として、以下の方法でパープレキシティが計算された。ここで、生データにはデータと属性があり、そのデータと属性の組み合わせはＮｅｔｆｌｉｘデータの場合はそれぞれ映画と評論家で、研究論文の場合はそれぞれ論文と単語である。
【０１４２】
まず、研究論文の場合には、ある単語が１回でも出現した場合、その単語の出現数を１に変換した。一方、Ｎｅｔｆｌｉｘデータの場合には、ある映画のレーティングがが存在すれば、その映画のレーティングを１、そうでなければその映画のレーティングを０に変換した。
【０１４３】
次に、各生データの１０％をテストパートとしてランダムに分割し、残りのパートを学習データとした。生データ毎に、テストパートに対してパープレキシティを計算した。
次に、各モデルのパラメータを推定するために学習パートが使用された。最後に、サンプルが採取されたときにクラスタを識別する情報が保存された。
【０１４４】
図２１は、トップＮの正確性が各手法間で比較されたテーブルである。同図において、本実施形態の手法ＨＳＣと、従来の推薦方法であるＣｏｓｉｎｅとＰｅａｒｓｏｎとＩｔｅｍとＳＣＢＳとの間で推薦の正確性が比較されている。比較対象は、Ｎｅｔｆｌｉｘデータを用いて算出された１番目の推薦アイテムの正確性と、５番目の推薦アイテムの正確性と、１０番目の推薦アイテムの正確性である。
【０１４５】
ここで、ＣｏｓｉｎｅとＰｅａｒｓｏｎは、それぞれコサイン類似度またはピアソンの相関係数によって計測されたユーザの類似度に基づいて推薦する方法である。
また、Ｉｔｅｍは、文献（J. K. B. Sarwa, G. Karypis and J. Riedl. Item-based collaborative filtering recommendation algorithms. In WWW, pages 285-295, 2001.）で提案されたピアソンの相関係数によって計測された内容類似度に基づいて推薦する方法である。
【０１４６】
同図において、１０番目の推薦アイテムの正確性において、本実施形態の手法ＨＳＣの正確性の値が従来手法ＳＣＢＳの正確性の値よりも片側ｔ検定で有意に大きくなっている（Ｐ＜０．０５で異なる場合、‘＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは、推薦の正確性においても従来手法ＳＣＢＳよりも向上しているという有利な効果を持っている。
【０１４７】
以下、図２１の実験結果が得られた実験の方法について説明する。クラスタ間を区別し得る属性を選択するという点からみたクラスタの質を計測するために、Ｎｅｔｆｌｉｘデータを用いて協調フィルタリングタスクのパフォーマンスを計算した。Ｎｅｔｆｌｉｘデータにおけるレーティングのバイアスに着目して、ユーザの平均レーティングよりも対象アイテムのレーティングが高い場合にはそのアイテムを購入したとみなして１とし、それ以外の場合にはそのアイテムを購入しなかったとみなして０とした。
【０１４８】
このデータにおいて、ユーザと購入アイテムがそれぞれデータと属性に対応する。Ｋ倍のクロスバリデーション（ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ）を介して、各手法の推薦の予測精度を評価するためにシミュレーションを実行した。Ｋ倍のクロスバリデーション（ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ）とは、オリジナルデータがランダムにＫ個のサブサンプリングに置かれることである。
【０１４９】
このシミュレーションにおいて、テストデータにおける各ユーザを、学習データから採取されたユーザログを用いて各推薦方法を適用したターゲットユーザとして扱った。
この実験において、クラスの数は１２０に固定されたおり、各ユーザは本実施形態の手法ＨＳＣまたは従来手法ＳＣＢＳによって、１２０のクラスのうちの１つのクラスに割り振られた。そして、Ｋが２０という条件下で、１００００回の繰り返しに対して１００回のギブスサンプリングが行われた。
【０１５０】
そして、本実施形態の手法ＨＳＣと従来の４つの手法をデータセットに適用し、トップＮ（Ｎは１、５または１０）の推薦の正確性を比較した。
本実施形態の手法ＨＳＣと従来手法ＳＣＢＳに関しては、ユーザが属するクラスにおいて観測値ｙｉｊ＝１となる確率に従ってトップＮランクのアイテムをターゲットユーザに提示し、これらの推薦アイテムがテストデータに存在することを確認した。
【０１５１】
図２２は、３つのパラメータが各手法間で比較されたテーブルである。同図において、図２１と同じ条件下において各クラスタリング手法によって算出された推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）と、推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）と、Ｇｉｎｉ係数とが示されている。
【０１５２】
ここで、それぞれの指標について詳細に説明する。まず、推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）は、テスト期間にアイテムを購入したユーザ数に対する各推薦方法が推薦可能なユーザ数の割合である。推薦ユーザの被覆率が高いほど、多くのユーザにアイテムを推薦できるので、ユーザ全体にとって価値が高いシステムである。
【０１５３】
推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）は、テスト期間に購入されたアイテムのタイトル数に対する各推薦方法が推薦可能なアイテム数の割合である。推薦オブジェクトの被覆率は、システムが推薦できるシステム中のアイテムドメインの大きさを示す１つの指標である。従って、推薦オブジェクトの被覆率の低いシステムは、ごく限られた選択アイテムしか提示できないから、ユーザにとって価値が低いシステムである。
【０１５４】
Ｇｉｎｉ係数は、アイテムに対するユーザの購入者数の分布の統計的分散を示す指標である。Ｇｉｎｉ係数は、０から１の値をとり、低くなるほど分布が平等であり、高くなるほど分布が偏っていることを意味する。すなわち、値が０に近いほどアイテムごとの購入ユーザ数の格差が少なく、１に近いほど格差が大きいことを意味する。
【０１５５】
Ｇｉｎｉ係数が０の場合、分布が完全に平等、すなわち全てのオブジェクトが正確に同じ数のユーザによって購入されている。一方、Ｇｉｎｉ係数が１の場合、分布が完全に不平等、すなわち１つのアイテムがすべてのユーザによって購入され、他のアイテムは、どのユーザにも購入されてない。
【０１５６】
高いＧｉｎｉ係数となる結果は、２、３個の特定のアイテムがたいていのユーザによって高くランク付けされている傾向にあることを意味し、特定のアイテムばかりが推薦される傾向が強く、ユーザ毎の推薦アイテムの違いは小さくなる。すなわち、アイテム推薦は、ユーザ毎に特化されていないことを意味する。一方、Ｇｉｎｉ係数が０に近いほど、アイテムの推薦がユーザ毎に特化し、アイテム推薦がうまく行われていることを意味する。
【０１５７】
図２２において、本実施形態の手法ＨＳＣにおいて、推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）が最も高く、Ｇｉｎｉ係数が最も０に近い。この結果から、本実施形態の手法ＨＳＣは、他の手法よりも偏りが少なく広い範囲のアイテムをユーザ毎に特化して推薦できることが証明された。
【０１５８】
本実施形態の手法ＨＳＣは、ユーザ間による興味の違いを強調するために、より人気のある瑣末なアイテムに対してより低い重み付けをする。それにより、個人の好みに応じたアイテムに対してより大きな重みをつけることができ、その結果、アイテム推薦の正確性が向上している。
【０１５９】
また、図２２において、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとの間で、推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）は同じである。
一方、図２２において、本実施形態の手法ＨＳＣの推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）の値が従来手法ＳＣＢＳの推薦オブジェクトの被覆率の値よりも片側ｔ検定で有意に大きくなっている（Ｐ＜０．０１で異なる場合、‘＊＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは、従来手法ＳＣＢＳよりも、より多くの選択アイテムを提示できることを意味し、ユーザにとって価値が高いクラスリング手法である。
【０１６０】
図２２において、実施形態の手法ＨＳＣの推薦オブジェクトのＧｉｎｉ係数の値が従来手法ＳＣＢＳのＧｉｎｉ係数の値よりも片側ｔ検定で有意に小さくなっている（Ｐ＜０．０１で異なる場合、‘＊＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは従来手法ＳＣＢＳよりも、アイテムに対するユーザの購入者数の分布が平等であるので、全てのオブジェクトがより同数に近いユーザによって購入されていることを意味する。従って、本実施形態の手法ＨＳＣは従来手法ＳＣＢＳよりも、ユーザ毎に特化したアイテムを推薦できるという有利な効果を有する。
【０１６１】
また、本実施形態の計算サーバ４００の各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、計算サーバ４００に係る上述した種々の処理を行ってもよい。
【０１６２】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１６３】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１６４】
以上、本発明の実施形態について図面を参照して詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１６５】
１００ ユーザ端末
２００ サービスサーバ
３００ ファイルサーバ
４００ 計算サーバ（クラスタリング分類装置）
４０１ 通信部
４０２ 制御部
４２０ 識別情報割振部
４３０ クラスタリング処理部
４３１ サブクラス割振部
４３２ サブクラス間差異判定部
４３３ 変数推定部
４３４ エントロピー算出部
４３５ クラス抽出部
４３６ 分割部
４３７ クラスタ数比較部
４４０ 属性選択部
５００ データベースサーバ
【技術分野】
【０００１】
本発明は、クラスタリング装置、クラスタリング方法およびクラスタリングプログラムに関する。
【背景技術】
【０００２】
データベース、データマイニング、情報の検索、市場解析を含む大量データの処理にとって、クラスタリング分析は重要な方法の１つである。クラスタリング分析の目的は、与えられたデータのうち、類似するデータ群をひとまとまりのクラスタとして複数のクラスタに分類することである。例えば、非特許文献１には、統計モデルをベースにしたクラスタリング手法が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｐ． Ｈｏｆｆ． Ｍｏｄｅｌ−ｂａｓｅｄ ｓｕｂｓｐａｃｅ ｃｌｕｓｔｅｒｉｎｇ．Ｂａｙｅｓｉａｎ Ａｎａｌｙｓｉｓ， （１）：３２１−３４４， ２００６
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１のクラスタリング手法では、各クラスタの属性を「クラスタ固有」あるいは「全クラスタ共通」のいずれかしか判定できないという制約があるという問題がある。具体的には、例えば、クラスタ数が１０のとき、そのうち２つのクラスタに共通の属性があっても、その属性をクラスタに固有あるいは全クラスタに共通のいずれかしか判定できなかった。
【０００５】
また、非特許文献１のクラスタリング手法では、得られるクラスタの構造がフラットな構造であるため、クラスタ間の関係が分からないという問題があった。そのため、複数のクラスタに共通の属性を、クラスタを特徴づける属性としてクラスタに割り振ることができなかった。
【０００６】
そこで本発明は、上記問題に鑑みてなされたものであり、各クラスタの属性の判定に係る制約を無くし、かつクラスタ間の関係を分かりやすくすることを可能とする技術を提供することを課題とする。
【課題を解決するための手段】
【０００７】
本発明は上記の課題を解決するためになされたものであり、本発明の一態様は、各データが属するクラスタを階層的に分割する分割部と、前記分割部によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部と、を備えることを特徴とするクラスタリング装置である。
【０００８】
また、本発明の一態様は、上記のクラスタリング装置において、前記各データに対し、ランダムにサブクラスを割り振るサブクラス割振部を更に備え、前記属性選択部は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、前記属性の値がサブクラス間で違いがない場合は、該属性の値を該サブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とすることを特徴とする。
【０００９】
また、本発明の一態様は、上記のクラスタリング装置において、前記属性選択部は、属性毎に該属性がサブクラスに固有である確率を算出し、該算出した確率に基づいて、該属性が前記サブクラス間で共通の属性か前記サブクラスに固有の属性かを判定することを特徴とする。
【００１０】
また、本発明の一態様は、上記のクラスタリング装置において、前記属性選択部は、前記データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出し、該算出した確率に基づいて前記データ毎に該データに割り振られるサブクラスを推定することを特徴とする。
【００１１】
また、本発明の一態様は、上記のクラスタリング装置において、前記サブクラスを識別するサブクラス識別情報の確率分布が二項分布で表され、前記属性がサブクラスに固有であるか否かを示す固有フラグの確率分布がベルヌーイ分布で表されることを特徴とする。
【００１２】
また、本発明の一態様は、各データが属するクラスタを階層的に分割する分割手順と、前記分割手順によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択手順と、を有するクラスタリングクラスタ分類方法である。
【００１３】
また、本発明の一態様は、コンピュータに、各データが属するクラスタを階層的に分割する分割ステップと、前記分割ステップによりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択ステップと、を実行するためのクラスタリングプログラムである。
【発明の効果】
【００１４】
本発明によれば、各クラスタの属性の判定に係る制約を無くし、かつクラスタ間の関係を分かりやすくすることができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態におけるクラスタリングシステムの概略ブロック図である。
【図２】本実施形態におけるユーザ端末のハードウェアの構成を示す概略ブロック図である。
【図３】本実施形態におけるサービスサーバのハードウェアの構成を示す概略ブロック図である。
【図４】本実施形態におけるファイルサーバのハードウェアの構成を示す概略ブロック図である。
【図５】本実施形態における計算サーバのハードウェアの構成を示す概略ブロック図である。
【図６】本実施形態における計算サーバの制御部の論理的な構成を示す概略ブロック図である。
【図７】ファイルＦに含まれるデータが格納されたテーブルＴ１の一例と、属性割付部による処理後のデータが格納されたテーブルＴ２の一例とが示された図である。
【図８】サブクラス割振部によりデータ毎にサブクラスが割り振られた１例を示すテーブルＴ３である。
【図９】図８のテーブルＴ３の観測値において、サブクラスに固有であるか否かを示す固有フラグｒの値の一例が示されたテーブルＴ４である。
【図１０】本実施形態における観測値ｙを推定する処理が示されたグラフィカルモデルである。
【図１１】固有フラグｒの値によりパラメタθまたはパラメタθ（チルタ）のいずれかが選択されることについて説明するための図である。
【図１２】変数推定部の論理的な構成を示す概略ブロック図である。
【図１３】本実施形態におけるデータベースサーバのハードウェアの構成を示す概略ブロック図である。
【図１４】クラスタリング結果記憶部に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ５である。
【図１５】クラスタリング結果記憶部に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ６である。
【図１６】クラスタの階層構造の一例が示された図である。
【図１７】映画のタイトルがクラスタリングされた結果の一例が示された図である。
【図１８】本実施形態における計算サーバの処理の流れを示すフローチャートである。
【図１９】本実施形態におけるクラスタリング処理に係る時間と、従来手法のクラスタリング処理に係る時間とを比較した図である。
【図２０】本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとのパープレキシティを比較したテーブルである。
【図２１】トップＮの正確性が各手法間で比較されたテーブルである。
【図２２】３つのパラメータが各手法間で比較されたテーブルである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照して詳細に説明する。本実施形態では、分類対象となるデータを分類するために各データに割り振られる識別子をクラス、同一のクラスが割り振られたデータの集合である分類結果をクラスタ、クラスタに含まれるデータを更に分類するために各データに割り振られる識別子をサブクラス、データの分類をクラスタリングと称し、以下説明する。
図１は、本実施形態におけるクラスタリングシステム１の概略ブロック図である。クラスタリングシステム１は、ユーザ端末１００と、サービスサーバ２００と、ファイルサーバ３００と、計算サーバ（クラスタリング装置）４００と、データベースサーバ５００とを有する。
【００１７】
ユーザ端末１００は、ユーザによって入力されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とをサービスサーバ２００に送信する。また、ユーザ端末１００は、サービスサーバ２００から供給されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを自装置が備える後述する表示部１０４に表示させる。
【００１８】
サービスサーバ２００は、ユーザ端末１００から送信されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とを受信し、受信したクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とをファイルサーバ３００に送信する。
また、サービスサーバ２００は、データベースサーバ５００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒをユーザ端末１００に送信する。
【００１９】
ファイルサーバ３００は、サービスサーバ２００から送信されたクラスタリング結果を要求する情報Ｒｑと、クラスタ数Ｎを示す情報とを受信する。ファイルサーバ３００には、自装置が備える後述するデータファイル記憶部３０３にデータが分析対象毎にファイルで予め記憶されている。ここで、データは、例えば、ログ（例えば、映画毎に、各ユーザがその映画を見たか否かといった情報）、テキストファイル、画像ファイル、音声ファイルまたは動画ファイルである。
【００２０】
ファイルサーバ３００は、クラスタリング結果を要求する情報Ｒｑを受信した場合、データファイル記憶部３０３からファイルＦを読み出し、ファイルＦとクラスタ数Ｎを示す情報とファイルを計算サーバ４００に送信する。
【００２１】
計算サーバ４００は、ファイルサーバ３００から送信されたファイルＦとクラスタ数Ｎを示す情報とを受信し、受信したファイルＦに基づいて、クラスタ数がＮに到達するまで入力データをクラスタに分割する。計算サーバ４００は、分割により得られたクラスタリング結果を示す情報Ｒをデータベースサーバ５００に送信する。
【００２２】
データベースサーバ５００は、計算サーバ４００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを後述するクラスタリング結果記憶部５０３に記憶させる。また、データベースサーバ５００は、受信したクラスタリング結果を示す情報Ｒをサービスサーバ２００に送信する。
【００２３】
図２は、本実施形態におけるユーザ端末１００のハードウェアの構成を示す概略ブロック図である。ユーザ端末１００は、記憶部１０１と、制御部１０２と、通信部１０３と、表示部１０４と、入力部１０５を備える。
記憶部１０１には、制御部１０３が実行するための各種プログラムが記憶されている。
入力部１０２は、自端末のユーザから入力されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報を受け付ける。入力部１０２は、例えば、キーボードとマウスを備える。入力部１０２は、受け付けたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報を制御部１０３に出力する。
【００２４】
制御部１０３は、プログラムを記憶部１０１から読み出して実行することにより、例えば、クラスタリング結果を要求する情報Ｒｑの入力を受け付けるボタンとクラスタ数Ｎを示す情報を入力するための欄を表示部１０５に表示させる。これにより、ユーザ端末１００のユーザは、クラスタ数Ｎをキーボードから入力し、当該ボタンをマウスを用いてクリックすることにより、クラスタ結果を示す情報Ｒを要求することができる。
【００２５】
制御部１０３は、入力部１０２から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを通信部１０４に出力し、クラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを通信部１０４からサービスサーバ２００に送信させる。また、制御部１０３は、通信部１０４から供給されたクラスタリング結果を示す情報Ｒを表示部１０５に表示させる。
【００２６】
通信部１０４は、有線または無線方式で、サービスサーバ２００と通信可能に構成されている。通信部１０４は、制御部１０３による制御に従って、制御部１０３から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをサービスサーバ２００に送信する。
また、通信部１０４は、サービスサーバ２００から送信されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒを制御部１０３に出力する。
【００２７】
表示部１０５は、例えば液晶表示パネルを備える。表示部１０５は、制御部１０３から供給されたクラスタリング結果を示す情報Ｒを表示する。
【００２８】
図３は、本実施形態におけるサービスサーバ２００のハードウェアの構成を示す概略ブロック図である。サービスサーバ２００は、通信部２０１と、呼出部２０２とを備える。
通信部２０１は、有線または無線方式で、ユーザ端末１００とファイルサーバ３００と通信可能に構成されている。通信部２０１は、ユーザ端末１００から供給されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを受信する。
【００２９】
通信部２０１は、制御部２０２の制御により、受信したクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをファイルサーバ３００に送信する。
また、通信部２０１は、データベースサーバ５００から供給されたクラスタリング結果を示す情報Ｒを受信し、受信したクラスタリング結果を示す情報Ｒをユーザ端末１００に送信する。
【００３０】
制御部２０２は、通信部２０１を制御して、クラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とをファイルサーバ３００に送信させる。
制御部２０２は、通信部２０１を制御して、クラスタリング結果を示す情報Ｒをユーザ端末１００に送信させる。
【００３１】
図４は、本実施形態におけるファイルサーバ３００のハードウェアの構成を示す概略ブロック図である。ファイルサーバ３００は、通信部３０１と、制御部３０２と、データファイル記憶部３０３とを備える。
データファイル記憶部３０３は、自装置の外部から供給されたデータ（例えば、ログ、テキストファイル、画像ファイル）が蓄積される。これにより、データファイル記憶部３０３には、データが分析対象毎にファイルで予め記憶されている。
【００３２】
通信部３０１は、有線または無線方式で、サービスサーバ２００と計算サーバ４００と通信可能に構成されている。サービスサーバ２００から送信されたクラスタリング結果を要求する情報Ｒｑとクラスタ数Ｎを示す情報とを受信する。通信部３０１は、制御部３０２の制御により、受信したクラスタリング結果を要求する情報Ｒｑを制御部３０２に出力する。
また、通信部３０１は、制御部３０２の制御に従って、制御部３０２によりデータ記憶部３０３から読み出されたファイルＦとクラスタ数Ｎを示す情報とを計算サーバ４００に送信する。
【００３３】
制御部３０２は、通信部３０１から供給されたクラスタリング結果を要求する情報Ｒｑを受け取った場合、データ記憶部３０３からクラスタリング対象のデータを含むファイルＦを読み出す。そして、制御部３０２は、読み出したファイルＦを、クラスタ数Ｎを示す情報と共に通信部３０１から計算サーバ４００に送信させる。
【００３４】
図５は、本実施形態における計算サーバ４００のハードウェアの構成を示す概略ブロック図である。計算サーバ４００は、通信部４０１と、制御部４０２とを備える。
通信部４０１は、ファイルサーバ３００から送信されたファイルＦとクラスタ数Ｎを示す情報とを受信し、受信したファイルＦとクラスタ数Ｎを示す情報を制御部４０２に出力する。
また、通信部４０１は、制御部４０２の制御に従って、制御部４０２から供給されたクラスタリング結果を示す情報Ｒをデータサーバ５００に送信する。
【００３５】
制御部４０２は、通信部４０１から供給されたファイルＦに含まれるデータに基づいて、クラスタ数がクラスタ数Ｎに到達するまで、ファイルＦに含まれるデータが属するクラスタを階層的に分割する。制御部４０２は、分割により得られたクラスタリング結果を示す情報Ｒを通信部４０１に出力し、クラスタリング結果を示す情報Ｒを通信部４０１からデータサーバ５００に送信させる。
【００３６】
図６は、本実施形態における計算サーバ４００の制御部４０２の論理的な構成を示す概略ブロック図である。制御部４０２は、識別情報割振部４２０と、クラスタリング処理部４３０とを備える。また、クラスタリング処理部４３０は、サブクラス割振部４３１と、属性選択部４４０と、変数推定部４３３と、エントロピー算出部４３４と、クラス抽出部４３５と、分割部４３６と、クラスタ数比較部４３７とを備える。また、属性選択部４４０は、サブクラス間差異判定部４３２と、変数推定部４３３とを備える。
【００３７】
識別情報割振部４２０は、通信部４０１から供給されたファイルＦに含まれるデータ毎に固有のデータ識別情報を割り付ける。また、識別情報割振部４２０は、ファイルＦに含まれる属性に固有の属性識別情報を割り付ける。
具体的な識別情報割振部４２０の処理の一例を、図７を用いて説明する。図７は、ファイルＦに含まれるデータの構造を表現したテーブルＴ１の一例と、識別情報割振部４２０による処理後のデータの構造を表現したテーブルＴ２の一例とが示された図である。
【００３８】
テーブルＴ１において、データ（例えば、映画のタイトル）と属性（例えば、ユーザ名）とに関連付けられて、観測値（０または１の値で、例えば、ユーザが映画毎にその映画を鑑賞したか否かの情報で、１が鑑賞した場合で０が鑑賞していない場合を示す）が示されている。
テーブルＴ１において、データＸＸのように、ファイルＦに含まれるデータが示されている。また、テーブルＴ１において、属性ＹＣのように、ファイルＦに含まれる属性が示されている。
【００３９】
テーブルＴ２において、各観測値（０または１の値）が、データを識別するデータ識別情報の一例であるデータｉ（ｉはデータのインデックスで、ｉは１からｌまでの整数）と、属性を識別する属性識別情報の一例である属性ｊ（ｊは属性のインデックスで、ｊは１からＪまでの整数）とに関連付けられている。
【００４０】
識別情報割振部４２０は、例えば、図７のテーブルＴ２に示すように、データ毎にデータ識別情報を割り振り、属性毎に属性識別情報を割り振る。これにより、識別情報割振部４２０は、各観測値ｙｉｊを、データ識別情報であるデータｉと属性識別情報である属性ｊとに関連付ける。識別情報割振部４２０は、各観測値ｙｉｊを示す情報を、データｉを示す情報と属性ｊを示す情報と共にサブクラス割振部４３１に出力する。
【００４１】
図６に戻って、サブクラス割振部４３１は、識別情報割振部４２０から供給されたデータｉに対し、仮にランダムにサブクラスを割り振る。サブクラス割振部４３１は、データｉ毎に関連付けられたサブクラスを示す情報を、各観測値ｙｉｊを示す情報とデータｉを示す情報と属性ｊを示す情報と共にサブクラス間差異判定部４３２に出力する。
サブクラス割振部４３１は、クラスタ数比較部４３７からクラスタ数が指定のクラスタ数Ｎに到達していない旨の情報を受け取った場合、または変数推定部４３３から計算が規定回数に到達していない旨の情報を受け取った場合、上記処理を繰り返す。
【００４２】
上記サブクラス割振部４３１の処理の図８の例を用いて説明する。図８は、サブクラス割振部４３１によりデータ毎にサブクラスが割り振られた１例を示すテーブルＴ３である。同図のテーブルＴ３の領域Ｒ８１に示されるように、サブクラス０またはサブクラス１が、データ１〜データＩまでランダムに割り振られている。例えば、データ１に対しては、サブクラス０が割り振られ、データＩに対しては、サブクラス１が割り振られている。
【００４３】
図６に戻って、サブクラス間差異判定部４３２は、属性ｊ毎にサブクラス間で観測値に差異が有るか否か判定する。そして、サブクラス間差異判定部４３２は、属性ｊ毎に観測値ｙｉｊがサブクラス間で違いがない場合には、その属性を仮に共通属性とし、サブクラスに固有であるか否かを示す固有フラグｒを０にする。
一方、サブクラス間差異判定部４３２は、属性ｊ毎に観測値ｙｉｊがサブクラス間で違いがない場合には、その属性を仮にサブクラス固有の属性とし、サブクラスに固有であることを示す固有フラグｒを１にする。これにより、サブクラス間差異判定部４３２は、属性ｊ毎にサブクラスに固有であるか否かを示す固有フラグｒの値を定める。
【００４４】
図９を用いて、サブクラス間差異判定部４３２の上記処理について説明する。図９は、図８のテーブルＴ３の観測値において、サブクラスに固有であるか否かを示す固有フラグｒの値の一例が示されたテーブルＴ４である。同図のテーブルＴ４において、図８のテーブルＴ３において、属性１、２および４は、サブクラス０（データ１）の場合に観測値が０で、サブクラス１（データＩ）の場合に観測値が１であり、サブクラス間で観測値が異なるので、固有フラグｒの値が１である。
【００４５】
一方、属性３およびＪは、サブクラス０（データ１）の場合に観測値が１で、サブクラス１（データＩ）の場合に観測値が１であり、サブクラス間で観測値が同じであるので、固有フラグｒの値が０である。
このように、サブクラス間差異判定部４３２は、クラスｋの属性ｊがサブクラス間で共通であるデータの数であるサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を算出する。ここで、ｎｋｊ０（〜）は、ｎｋｊ０の上に記号〜が付された記号である。また、ｎｋｊ１（〜）は、ｎｋｊ１の上に記号〜が付された記号である。また、サブクラス間差異判定部４３２は、クラスｋの属性ｊがサブクラスに固有であるデータの数であるサブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を算出する。
サブクラス間差異判定部４３２は、算出したサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を示す情報と、サブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を示す情報とを変数推定部４３３に出力する。
【００４６】
変数推定部４３３は、サブクラス間差異判定部４３２から入力されたサブクラス共通数ｎｋｊ０（〜）及びｎｋｊ１（〜）を示す情報と、サブクラス固有数ｎｋ０ｊ１、ｎｋ０ｊ０、ｎｋ１ｊ０及びｎｋ１ｊ１を示す情報とに基づいて、ギブスサンプリングを用いて、クラスｋおよび属性ｊ毎に固有フラグｒｋｊの値（０または１）を推定する。ここで、ｋはクラスを識別する識別情報である。また、変数推定部４３３は、ギブスサンプリングを用いて、クラスｋおよびデータｉ毎にサブクラスを識別するサブクラス識別情報ｚｋｉの値（０または１）を推定する。これにより、クラスｋに含まれるデータｉ毎にデータｉが属するサブクラスを推定することができる。
【００４７】
変数推定部４３３は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達していない場合、サブクラス割振部４３１に計算が規定回数に到達していない旨の情報を出力する。
一方、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達した場合、変数推定部４３３は、推定した固有フラグｒｋｊの値を示す情報と、サブクラスを指定するサブクラス識別情報ｚｋｉの値を示す情報とをエントロピー算出部４３４に出力する。
【００４８】
エントロピー算出部４３４は、分割し得るクラスタである分割対象クラスタ毎にそのクラスタを分割した際の条件付きエントロピーを算出する。ここで、クラスタリングする前は全てのデータｉが１つのルートクラスタに入っているとみなせる。ゆえに、分割部４３６は、当該ルートクラスタを分割する際には、どちらのクラスタが分割されるか決定する必要がないので、エントロピー算出部４３４は、条件付きエントロピーを算出する必要はない。
【００４９】
一方、その全てのデータｉが、２つ以上のクラスタに分割された後には、現在存在するクラスタのうちどのクラスタを分割するか決定するために、エントロピー算出部４３４は、クラスタが分割された場合の条件付きエントロピーが未だ算出されていないクラスタに対して、クラスタが分割された場合の条件付きエントロピーを算出する。これにより、既に算出されているクラスタが分割された場合の条件付きエントロピーを再度算出する必要がないので、計算コストを削減することができる。
【００５０】
エントロピー算出部４３４は、算出した条件付きエントロピーを示す情報を、分割対象クラスタを識別するクラスタ識別情報に関連づけてクラスタ抽出部４３５に出力する。
【００５１】
クラスタ抽出部４３５は、未だ分割されていないクラスタに対して、そのクラスタが分割された場合の条件付きエントロピーを示す情報をクラスタを識別するクラスタ識別情報に関連づけて保持している。
クラスタ抽出部４３５は、エントロピー算出部４３４から供給された条件付きエントロピーと、保持している条件付きエントロピーのうち、エントロピーが最小となる分割対象クラスタを抽出する。クラスタ抽出部４３５は、抽出した分割対象クラスタを示す情報を分割部４３６に供給する。
【００５２】
また、クラスタ抽出部４３５は、エントロピーが最小となる分割対象クラスタのクラスタ識別情報に関連付けられた条件付きエントロピーを示す情報を消去し、分割されなかったクラスタを識別するクラスタ識別情報に関連付けられた条件付きエントロピーを示す情報を保持する。
【００５３】
分割部４３６は、クラスタ抽出部４３５から供給された分割対象クラスタを分割する際に、変数推定部４３３により推定されたデータｉが属するサブクラスを示す情報に基づいて、分割対象クラスタを２つのクラスタに分割する。
【００５４】
クラスタ数比較部４３７は、識別情報割振部４２０から供給されたクラスタ数Ｎと、現在のクラスタ数とを比較し、現在のクラスタ数が現在のクラスタ数Ｎに到達していたら、クラスタ結果を示す情報Ｒを通信部４０１に出力する。
一方、現在のクラスタ数が現在のクラスタ数Ｎに到達していない場合、クラスタ数比較部４３７は、クラスタ数が指定のクラスタ数Ｎに到達していない旨の情報をサブクラス割振部４３１に出力する。
【００５５】
続いて、変数推定部４３３の処理の詳細について図１０、１１および１２を用いて説明する。図１０は、本実施形態における観測値ｙを推定する処理が示されたグラフィカルモデルである。同図において、各変数または定数の関係が示されている。
同図において、α、β、γはハイパーパラメータで、予め定められた定数である。ｋはクラスを識別する識別情報である。
【００５６】
同図において、パラメタφｋは、ハイパーパラメータαを構成する変数α０とα１とから計算されることが示されている。パラメタφｋは、サブクラスを識別するサブクラス識別情報ｚｉが１を出力する確率であり、０〜１の連続値を取る。ここで、パラメタφｋの確率分布は、クラスｋ毎にハイパーパラメータαを構成する定数α０と定数α１とを引数とするディリクレ（Ｄｉｒｉｃｈｌｅｔ）分布で表される。
【００５７】
同図において、サブクラス識別情報ｚｉは、クラスｋとパラメタφｋによって算出される。本実施形態では、クラスｋは２つのサブクラスに分割されるので、サブクラス識別情報ｚｉは、０または１の値を取る。ここで、サブクラス識別情報ｚｉの確率分布は、データｉ毎およびクラスｋ毎に、パラメタφｋを引数とする二項（Ｂｉｎｏｍｉａｌ）分布で表される。
【００５８】
パラメタλｋｊは、固有フラグｒが１を出力する確率であり、０〜１の連続値を取る。パラメタλｋｊは、クラスｋとハイパーパラメータβを構成する定数β０と定数β１とから算出される。具体的には、パラメタλｋｊの確率分布は、クラスｋ毎およびデータｊ毎に、ハイパーパラメータβを構成する定数β０と定数β１とを引数とするベータ（Βｅｔａ）分布で表される。
【００５９】
固有フラグｒは、使用する変数を指定するフラグであり、０また１の値を取り得る。観測値ｙを推定する際に、固有フラグｒの値が１のときにはサブクラスｚｉに固有のパラメタθが使用され、固有フラグｒの値が０のときにサブクラスｚｉに共通のパラメタθ（チルタ）が使用される。ここで、図１０におけるθの上に〜が示されている記号をθ（チルタ）と称し、以後θ（チルタ）を用いて説明する。
【００６０】
固有フラグｒは、クラスｋとパラメタλｋｊとから算出される。具体的には、固有フラグｒｋｊの確率分布は、クラスｋ毎およびデータｊ毎に、パラメタλｋｊを引数とするベルヌーイ（Ｂｅｅｒｎｏｕｌｌｉ）分布で表される。
【００６１】
パラメタθｋｌｊは、固有フラグｒが１のとき、すなわちパラメタθｋｌｊがサブクラスｚｉに固有のときに用いられる変数である。一方、パラメタθｋｌｊ（チルタ）は、固有フラグｒが０のとき、すなわちパラメタθｋｌｊがサブクラスｚｉに共通のときに用いられる変数である。
パラメタθｋｌｊは、クラスｋと、サブクラスｌと、ハイパーパラメータγを構成する変数γ１０および変数γ１１とから算出される。具体的には、パラメタθｋｌｊの確率分布は、ハイパーパラメータγを構成する変数γ１０および変数γ１０を引数とするベータ分布で表される。
【００６２】
また、パラメタθｋｌｊ（チルタ）は、クラスｋと、サブクラスｌと、ハイパーパラメータγを構成する変数γ００および変数γ０１とから算出される。具体的には、パラメタθｋｌｊ（チルタ）の確率分布は、ハイパーパラメータγを構成する変数γ００および変数γ０１を引数とするベータ分布で表される。
【００６３】
観測値ｙｉｊは、サブクラスｚｉ、固有フラグｒｊ、パラメタθｚｊ、パラメタθｚｊ（チルタ）によって推定される値である。具体的には、観測値ｙｉｊの確率分布は、データｉ毎および属性ｊ毎に、パラメタθｚｊおよびパラメタθｚｊ（チルタ）を引数とするベルヌーイ（Ｂｅｅｒｎｏｕｌｌｉ）分布で表される。
【００６４】
図１０において、領域Ｒ１０１内の変数は、データ数Ｉの回数だけ繰り返し算出される。領域Ｒ１０２内の変数は、クラスタ毎に分割しうる分割数Ｌ（本実施形態では、２）と属性の数Ｊを乗じた値ＬＪ（本実施形態では、２Ｊ）の回数だけ繰り返し算出される
【００６５】
図１１は、固有フラグｒの値によりパラメタθまたはパラメタθ（チルタ）のいずれかが選択されることについて説明するための図である。同図において、棒グラフの中の色が黒である領域が観測値ｙｉｊが１が出現する確率であり、棒グラフの中の色が白である領域が観測値ｙｉｊが０が出現する確率である。
【００６６】
同図において固有フラグｒが１の場合、サブクラスｚがｌのとき、観測値ｙｉｊとして１が出現する確率θｌｊが観測値ｙｉｊとして０が出現する確率１−θｌｊより大きいことが示されている。一方、サブクラスｚがｌ´のとき、観測値ｙｉｊとして０が出現する確率θｌｊが観測値ｙｉｊとして１が出現する確率１−θｌｊより大きいことが示されている。すなわち、サブクラスｌとサブクラスｌ´との間で、観測値ｙｉｊとして１が出現する確率と０が出現する確率の比が、逆転していることが示されている。
【００６７】
一方、固有フラグｒが０の場合、サブクラスｌにおいて確率θｌｊが確率１−θｌｊより大きく、サブクラスｌ´における確率θｌ´ｊが確率１−θｌ´ｊより大きいことが示されている。すなわち、サブクラスｌとサブクラスｌ´との間で、観測値ｙｉｊとして１が出現する確率は０が出現する確率よりも共通して大きいことが示されている。
【００６８】
そこで、固有フラグｒが０の場合には、サブクラスに共通のパラメタθｌｊ（チルタ）が使用されることが示されている。このようにして、属性選択部４４０は、サブクラス間の属性を比較することにより固有フラグｒを選択する。これにより、クラスタリング処理部４３０は、選択された固有フラグｒに基づいて、サブクラスに固有のパラメタθｌｊとサブクラスに共通のパラメタθｌｊ（チルタ）のいずれかを使用するかを選択し、観測値ｙｉｊを推定することができる。そして、クラスタリング処理部４３０は、推定された観測値ｙｉｊが実際の観測値ｙｉｊと近くなるように、変数ｒと変数ｚを算出する。
【００６９】
図１２は、変数推定部４３３の論理的な構成を示す概略ブロック図である。変数推定部４３３は、クラス帰属判定部４３３＿１と、属性振分部４３３＿５とを備える。
クラス帰属判定部４３３＿１は、データｉ毎に当該データｉが帰属するサブクラスｚを推定する。ここで、クラス帰属判定部４３３＿１は、変数ｚ確率算出部４３３＿２と変数ｚ算出部４３３＿３とを備える。
【００７０】
図１０に示されるように、各変数に確率分布を導入したことで、クラスｋとハイパーパラメータα、βおよびγが与えられたという条件付きのデータ全体の同時確率Ｐ（ｙ，ｚ，ｒ，φ，λ，θ，θ（チルタ）｜ｋ，α，β，γ）は次の式（１）で表される。
【００７１】
【数１】
【００７２】
この同時確率を用いることによって、変数推定部４３３は、潜在するサブクラスにデータを割り振ることと、各サブクラスに固有の属性の検出とを同時に行うことができる。
ここで、式（１）がφ，λ，θで積分されると、以下の式（２）で表される。
【００７３】
【数２】
【００７４】
ここで、Γはガンマ関数である。また、ｎｋ０はクラスｋのサブクラス０のデータの数であり、ｎｋ１はクラスｋのサブクラス１のデータの数であり、ｎｋｊはクラスｋにおいて属性ｊを有するデータ数、ｎｋ０は属性０を有するクラスｋのデータ数である。また、ｎｋ０ｊ１（ｎｋ０ｊ０）は、クラスｋにおけるサブクラス０のデータであって、サブクラスに固有（サブクラス間で共通）のデータの数である。また、ｎｋ１ｊ１（ｎｋ１ｊ０）は、クラスｋにおけるサブクラス１のデータであって、サブクラスに固有（サブクラス間で共通）のデータの数である。ｎｋｊ１（ｎｋｊ０）は、クラスｋにおいて、サブクラスに固有（サブクラス間で共通）のデータ数である。
【００７５】
各変数が確率分布で表されるので、式（１）で現れるパラメタλ、φ、θおよびθ（チルタ）は、式（１）が積分されることによって解析的にその値が消え、式（２）ではパラメタλ、φ、θおよびθ（チルタ）が現れない。
【００７６】
変数ｚ確率算出部４３３＿２は、サブクラス間差異判定部４３２から供給された情報が示すサブクラス共通数ｎｋｊ０とサブクラス固有数ｎｋｊ１とを用いて、データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出する。具体的には、例えば、変数ｚ確率算出部４３３＿２は、属性毎の固有フラグｒの初期値を示す情報を用いて、サブクラスｚｉがｌである条件付き確率Ｐ（ｚｉ＝ｌ）を以下の式（３）に従って算出する。
【００７７】
【数３】
【００７８】
ここで、ｚ＼ｉは、データｉ以外のデータでサブクラスに割り振られた数である。また、ｎｋ＼ｉは、データｉ以外でクラスｋを有するデータの数であり、ｎｋｌ＼ｉは、データｉ以外クラスｋの中のサブクラスｌに割り振られたデータの数である。また、ｎｋ＼ｉｊ０（ｎｋ＼ｉｊ０）は、データｉ以外でクラスｋを有するデータであって、観測値ｙｉｊ＝０（ｙｉｊ＝１）に割り振られたデータの数である。また、ｎｋｌ＼ｉｊ０（ｎｋｌ＼ｉｊ０）は、データｉ以外でクラスｋの中のサブクラスｌに割り振られたデータであって、観測値ｙｉｊ＝０（ｙｉｊ＝１）に割り振られたデータの数である。
【００７９】
各変数が確率分布で表されるので、式（３）において、パラメタλ、φ、θおよびθ（チルタ）が現れない。ゆえに、変数推定部４３３は、パラメタλ、φ、θおよびθ（チルタ）を計算する必要がないので、計算量を減らすことができる。
【００８０】
変数ｚ確率算出部４３３＿２は、データｉ毎に算出した条件付き確率Ｐ（ｚｉ＝ｌ）を示す情報を変数ｚ算出部４３３＿３に出力する。
変数ｚ算出部４３３＿３は、乱数を算出する。変数ｚ算出部４３３＿３は、変数ｚ確率算出部４３３＿２から供給された条件付き確率Ｐ（ｚｉ＝ｌ）が、算出した乱数よりも大きい場合には、変数ｚを１とする。一方、変数ｚ算出部４３３＿３は、条件付き確率Ｐ（ｚｉ＝ｌ）が、算出した乱数以下の場合、変数ｚを０とする。
【００８１】
変数ｚ算出部４３３＿３は、この処理をデータｉ毎に算出された条件付き確率Ｐ（ｚｉ＝ｌ）を示す情報全てについて行い、現在のステップにおけるデータｉ毎にサブクラス識別情報ｚｉ（０または１の値）を算出する。
【００８２】
変数ｚ算出部４３３＿３は、算出したータｉ毎のサブクラス識別情報ｚｉの変化量を示す情報をエントロピー算出部４３４に出力する。また、変数ｚ算出部４３３＿３は、変化量を算出した旨の情報を属性振分部４３３＿５の後述する変数ｒ確率算出部４３３＿６に出力する。
【００８３】
続いて、属性振分部４３３＿５について説明する。属性振分部４３３＿５は、属性ｊ毎に固有のフラグｒｊの値を推定する。換言すれば、属性振分部４３３＿５は、属性ｊ毎に当該属性ｊがサブクラス間で固有の属性かサブクラス間で共通の属性かを推定する。
属性振分部４３３＿５は、変数ｒ確率算出部４３３＿６と、変数ｒ算出部４３３＿７とを備える。
【００８４】
変数ｒ確率算出部４３３＿６は、変数ｚ算出部４３３＿３から変化量を算出した旨の情を受け取ると、サブクラス間差異判定部４３２から供給された情報が示すサブクラス共通数ｎｋｊ０とサブクラス固有数ｎｋｊ１とに基づいて、属性ｊ毎に当該属性がサブクラスに固有である確率である固有フラグｒの条件付き確率Ｐ（ｒｊ）を以下の式（４）に従って算出する。
【００８５】
【数４】
【００８６】
ここで、ｒ＼ｊは、ｊ以外の固定フラグｒであり、ｙ＼ｊは、ｊ以外の観測値ｙである。各変数が確率分布で表されるので、式（４）においても、パラメタλ、φ、θおよびθ（チルタ）が現れない。ゆえに、変数推定部４３３は、パラメタλ、φ、θおよびθ（チルタ）を計算する必要がないので、計算量を減らすことができる。
【００８７】
変数ｒ確率算出部４３３＿６は、算出した属性ｊ毎の条件付き確率Ｐ（ｒｊ）を示す情報を変数ｒ算出部４３３＿７に出力する。
変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒ＝０の条件付き確率Ｐ（ｒｊ）よりも、現在のステップで算出された固有フラグｒ＝１の条件付き確率Ｐ（ｒｊ）が大きい場合、固有フラグｒを０から１に変更する。
一方、変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒ＝１の条件付き確率Ｐ（ｒｊ）よりも、現在のステップで算出された固有フラグｒ＝０の条件付き確率Ｐ（ｒｊ）が大きい場合、固有フラグｒを１から０に変更する。
【００８８】
上記２つに当てはまらない場合、変数ｒ算出部４３３＿７は、乱数を算出する。変数ｒ算出部４３３＿７は、前のステップで算出された固有フラグｒの条件付き確率Ｐ（ｒｊ）を分母で、現在のステップで算出された固有フラグｒの条件付き確率Ｐ（ｒｊ）分子とする固有フラグｒの条件付き確率Ｐ（ｒｊ）の比率を算出する。
変数ｒ算出部４３３＿７は、算出した比率が、算出した乱数よりも大きい場合には、固有フラグｒを１とする。一方、変数ｒ算出部４３３＿７は、算出した比率が、算出した乱数以下の場合、固有フラグｒを０とする。
【００８９】
変数ｒ算出部４３３＿７は、クラスタ数が１の場合、この処理を属性ｊ毎に算出された条件付き確率Ｐ（ｒｊ）を示す情報全てについて行って、属性ｊ毎に固有フラグｒｊを決定する。
変数ｒ算出部４３３＿７は、クラスタ数が２以上の場合、その前までの処理で固有フラグｒが０となった属性以外の属性ｊについて、属性ｊ毎に固有フラグｒｊを決定する。
【００９０】
これにより、クラスタ数が２以上の場合、変数ｒ算出部４３３＿７は、その前までの処理で固有フラグｒが０となった属性以外についてのみ固有フラグｒｊを決定すればよいので、全ての属性で固有フラグｒｊを決定するのに比べて計算量を減らすことができる。
また、変数ｒ算出部４３３＿７が式（４）を用いて条件付き確率Ｐ（ｒｊ）を算出する際に、式（４）におけるガンマ関数の計算量が多いので、特に計算量を減らすことに貢献することができる。
【００９１】
続いて、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達した場合、現在の属性ｊ毎の固有フラグｒｊを示す情報をエントロピー算出部４３４に出力する。これにより、属性ｊ毎に当該属性ｊがサブクラスに固有であるかサブクラス間で共通であるかを決定することができる。
【００９２】
一方、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達していない場合、サブクラス割振部４３１に計算が規定回数に到達していない旨の情報を出力する。これにより、変数ｒ算出部４３３＿７は、属性ｊ毎の固有フラグｒｊの計算の回数が規定回数（ギブスサンプリングの回数）に達するまで、サブクラス割振部４３１はサブクラスを割り振り直させることができる。
【００９３】
なお、変数ｒ算出部４３３＿７は、変数ｒの変動量の総和が所定の閾値より小さくなるまで、サブクラス割振部４３１はサブクラスを割り振り直させてもよい。
具体的には、例えば、変数ｒ算出部４３３＿７は、直前のステップで算出された属性ｊ毎に算出された条件付き確率Ｐ（ｒｊ）を示す情報を保持している。変数ｒ算出部４３３＿７は、直前のステップの属性ｊの条件付き確率Ｐ（ｒｊ）に対する現在算出した属性ｊの条件付き確率Ｐ（ｒｊ）との変化量を算出する。
例えば、変数ｒ算出部４３３＿７は、直前のステップの属性ｊの条件付き確率Ｐ（ｒｊ）が０で、現在算出した属性ｊの条件付き確率Ｐ（ｒｊ）が１であるならば、変化量を１と算出する。
【００９４】
変数ｒ算出部４３３＿７は、上記処理を全ての属性ｊに対して行うことにより、属性ｊ毎の固有フラグｒｊの変化量を算出する。属性ｊ毎の固有フラグｒｊの変化量の絶対値の総和を算出し、算出した総和が所定の閾値より小さくなるまでサブクラス割振部４３１はサブクラスを割り振り直させるようにしてもよい。
【００９５】
以上の処理についてまとめると、属性選択部４４０は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、属性の値がサブクラス間で違いがない場合は、その属性の値をそのサブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とする。
また、属性選択部４４０は、属性毎にその属性がサブクラス間で固有である確率を算出し、その算出した確率に基づいて、その属性がサブクラス間で共通の属性かサブクラスに固有の属性かを判定する。
また、属性選択部４４０は、データ毎にそのデータに割り振られるサブクラスが所定のサブクラスである確率を算出し、算出した確率に基づいてデータ毎にそのデータに割り振られるサブクラスを推定する。
【００９６】
続いて、エントロピー算出部４３４は、変数ｒ算出部４３３＿７から供給された現在のデータｉ毎のサブクラス識別情報ｚｉに基づいて、条件付きエントロピーを算出する。具体的には、エントロピー算出部４３４は、以下の式（５）に従って、条件付きエントロピーＨ（Ｘ｜Ｙ）を算出する。
【００９７】
【数５】
【００９８】
ここで、Ｈ（Ｘ｜Ｙ）は、サブクラスの集合Ｙが与えられたときのデータの集合Ｘのエントロピーである。また、ｌはサブクラスのインデックスであり、Ｌはサブクラスの数であり、クラスタを２つのサブクラスに分割するので本実施形態ではＬは２である。また、Ｉはデータｉの数である。Ｐ（Ｘ＝ｘｉ｜Ｙ＝ｙｌ）は、データがｘｉでサブクラスがｙｌの条件付確率を表している。
【００９９】
エントロピー算出部４３４は、データにサブクラスを割り振る毎に、上記式（４）に従って、条件付きエントロピーを算出する。エントロピー算出部４３４は、算出した、条件付きエントロピーを示す情報をクラスタ抽出部４３５に出力する。
【０１００】
続いて、データベースサーバ５００について説明する。図１３は、本実施形態におけるデータベースサーバ５００のハードウェアの構成を示す概略ブロック図である。データベースサーバ５００は、通信部５０１と、制御部５０２と、クラスタリング結果記憶部５０３とを備える。
【０１０１】
通信部５０１は、計算サーバ４００から送信されたクラスタリング結果を示す情報Ｒを受信する。通信部５０１は、制御部５０２の制御に従って、受信したクラスタリング結果を示す情報Ｒをクラスタリング結果記憶部５０３に供給する。
また、通信部５０１は、受信したクラスタリング結果を示す情報Ｒをサービスサーバ２００に送信する。
【０１０２】
制御部５０２は、通信部５０１により受信されたクラスタリング結果を示す情報Ｒをクラスタリング結果記憶部５０３に記憶させる。これにより、クラスタリング結果記憶部５０３には、クラスタリング結果を示す情報Ｒが記憶される。
【０１０３】
図１４は、クラスタリング結果記憶部５０３に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ５である。同図において、データの識別情報と親クラスタの識別情報と所属クラスタの識別情報とが関連付けられている。ここで、所属クラスタとは、データが最終的に分類されたクラスタであり、親クラスタとは、所属クラスタを包含するクラスタであって所属クラスタが分割される直前のクラスタである。
【０１０４】
例えば、データ１の親クラスタの識別情報１であり、所属クラスタの識別情報が２であることが示されている。
このように、クラスタリング結果記憶部５０３には、データの識別情報とデータが属する所属クラスタの識別情報と当該所属クラスタの親クラスタの識別情報とが関連付けられて記憶される。
【０１０５】
図１５は、クラスタリング結果記憶部５０３に記憶されているクラスタリング結果を示す情報Ｒの一例が示されたテーブルＴ６である。同図において、固有フラグｒの値が、属性の識別情報とクラスタ識別情報（クラスタ１〜クラスタＮ）とに関連付けられている。例えば、属性１はクラスタ１では固有フラグｒが１なのでクラスタ１に固有の属性であるが、クラスタＮでは固有フラグｒが０なのでクラスタ間で共通の属性であることが示されている。
【０１０６】
図１６は、クラスタの階層構造の一例が示された図である。前提として、映画のタイトルがデータであり、属性はユーザの識別情報であるユーザｉｄである。観測値ｙはユーザｊが映画のタイトルＴｉを鑑賞したか否かを示す情報（鑑賞していれば１、鑑賞していなければ０）である。例えば、ユーザｊが映画のタイトルＴｉを鑑賞した場合には、その観測値は１であり、鑑賞していない場合にはその観測値は０である。ここで、ユーザが１０人であり、各ユーザにユーザｉｄが１から１０まで割り振られていることを想定する。
【０１０７】
同図において、最初の分岐Ｂ１６１では、全データが属していたクラスタｋ０は、クラスタｋ００とクラスタｋ０１に分割されている。クラスタｋ００に固有の属性は、ユーザｉｄが１、２、３、４、５である。これは、クラスタｋ００は、ユーザｉｄが１、２、３、４、５のユーザが鑑賞した映画のクラスタであることを意味する。
【０１０８】
一方、クラスタｋ０１に固有の属性は、ユーザｉｄが６、７、８、９、１０である。これは、クラスタｋ０１は、ユーザｉｄが６、７、８、９、１０のユーザが鑑賞した映画のクラスタであることを意味する。
【０１０９】
クラスタｋ００に固有の属性と、クラスタｋ０１に固有の属性とを比較すると、クラスタｋ００の共通属性はユーザｉｄが５以下であることから、ユーザｉｄの数が６より小さいユーザが鑑賞した映画タイトルが分類されていると解釈できる。一方、クラスタｋ０１の共通属性はユーザｉｄが６以上であるので、ユーザｉｄの数が６以上のユーザが鑑賞した映画タイトルが分類されていると解釈できる。
【０１１０】
このように、クラスタリング処理部４３０は、クラスタを階層的に分割するので、クラスタ結果を見た人は、クラスタに固有の属性を比較することにより、クラスタ間の関係を理解することができる。
【０１１１】
また、分岐Ｂ１６２では、クラスタｋ００は２つのクラスタｋ０００とクラスタｋ００１とに分割されている。クラスタｋ０００に固有の属性は、ユーザｉｄが奇数である。これは、クラスタｋ０００は、ユーザｉｄが１、２、３、４、５のうちユーザｉｄが奇数であるという条件を満たすユーザｉｄ（１、３、５）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１２】
同様に、クラスタｋ００１に固有の属性は、ユーザｉｄが偶数である。クラスタｋ００１は、ユーザｉｄが１、２、３、４、５のうちユーザｉｄが偶数であるという条件を満たすユーザｉｄ（２、４）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１３】
また、分岐Ｂ１６３では、クラスタｋ０１は２つのクラスタｋ０１０とクラスタｋ０１１とに分割されている。クラスタｋ０１０に固有の属性は、ユーザｉｄが奇数である。これは、クラスタｋ０００は、ユーザｉｄが６、７、８、９、１０のうちユーザｉｄが奇数であるという条件を満たすユーザｉｄ（７、９）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
【０１１４】
同様に、クラスタｋ０１１に固有の属性は、ユーザｉｄが偶数である。クラスタｋ００１は、ユーザｉｄが６、７、８、９、１０のうちユーザｉｄが偶数であるという条件を満たすユーザｉｄ（６、８、１０）のユーザが鑑賞した映画のタイトルが分類されたクラスタであることを意味する。
このように、クラスタリング処理部４３０は、クラウタ間で共通の属性を削除し、各クラスタに固有の属性を抽出するので、人にクラスタを構成するデータの特徴を理解させることができる。
【０１１５】
更に、クラスタリング処理部４３０は、クラスタを階層化するので、クラスタを構成するデータは所属クラスタに固有の属性と所属クラスタの親クラスタに固有の属性とを有するので、人にクラスタを構成するデータの特徴を理解させることができる。
また、クラスタリング処理部４３０は、クラスタが階層化されることで、クラスタ間の相対的な近さがわかり、人にデータ全体の構造が理解させることができる。
【０１１６】
図１７は、映画のタイトルがクラスタリングされた結果の一例が示された図である。同図において、図１６に示されたクラスタｋ０００、クラスタｋ００１、クラスタｋ０１０、クラスタｋ０１１毎に各クラスタに含まれる映画のタイトルが示されている。ここで、図１７に示されているタイトル１からタイトル２２は、映画のタイトルである。
クラスタｋ０００を構成するデータはタイトル１から６までの６つの映画タイトルであり、クラスタｋ００１を構成するデータはタイトル７から１１までの５つの映画タイトルであり、クラスタｋ０１０を構成するデータはタイトル１２から１６までの５つの映画タイトルであり、クラスタｋ０１１を構成するデータはタイトル１７から２２までの６つの映画タイトルであることが示されている。
【０１１７】
図１８は、本実施形態における計算サーバ４００の処理の流れを示すフローチャートである。まず、制御部４０２は、通信部４０１を介してファイルサーバ３００から供給されたクラスタ数Ｎを示す情報を受け取る（ステップＳ１０１）。識別情報割振部４２０は、クラスタリング対象のデータ及び属性に識別情報を割り振る（ステップＳ１０２）。
【０１１８】
次に、サブクラス割振部４３１は、それぞれのクラスタにおいて各データが属するサブクラスを割り振る（ステップＳ１０３）。次に、サブクラス間差異判定部４３２は、属性ｊ毎に固有フラグｒｊの初期値を決定する（ステップＳ１０４）。次に、変数推定部４３３は、データｉ毎のサブクラス識別情報ｚｉと属性ｊ毎の固有フラグｒｊの値を推定する（ステップＳ１０５）。
【０１１９】
変数ｒ算出部４３３＿７は、計算の回数が規定回数に達したか否か判定する（ステップＳ１０６）。計算の回数が規定回数に達していない場合（ステップＳ１０６ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０３の処理に戻る。
一方、計算の回数が規定回数に達した場合（ステップＳ１０６ ＹＥＳ）、エントロピー算出部４３４は、現在のクラスタ数が２以上か否か判定する（ステップＳ１０７）。現在のクラスタ数が１の場合（ステップＳ１０７ ＮＯ）、分割部４３６は全データｉを２つのクラスタに分割し（ステップＳ１０８）、クラスタリング処理部４３０は、ステップＳ１１２の処理に進む。
一方、現在のクラスタ数が２以上の場合（ステップＳ１０７ ＹＥＳ）、エントロピー算出部４３４は、条件付きエントロピーを算出する（ステップＳ１０９）。
【０１２０】
次に、エントロピー算出部４３４は、現在存在する全てのクラスタに対して、当該クラスタが分割された場合の条件付きエントロピーを算出したか否か判定する（ステップＳ１１０）。現在存在する全てのクラスタに対して当該クラスタが分割された場合の条件付きエントロピーを算出していない場合（ステップＳ１１０ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０３に戻り、条件付きエントロピーが算出されていないクラスタに対してステップＳ１０３の処理を行う。
【０１２１】
一方、現在存在する全てのクラスタに対して当該クラスタが分割された場合の条件付きエントロピーを算出した場合（ステップＳ１１０ ＹＥＳ）、クラス抽出部４３５は、条件付きエントロピーが最小となる分割対象クラスタを抽出する（ステップＳ１１１）。
次に、分割部４３６は、抽出された分割対象クラスタを２つのクラスタに分割する（ステップＳ１１２）。
【０１２２】
クラスタ数比較部４３７は、分割部４３６による分割後のクラスタ数がファイルサーバ３００から供給されたクラスタ数Ｎに到達したか否か判定する（ステップＳ１１３）。分割後のクラスタ数がクラスタ数Ｎに到達していない場合（ステップＳ１１３ ＮＯ）、クラスタリング処理部４３０は、ステップＳ１０２の処理に戻る。
一方、分割後のクラスタ数がクラスタ数Ｎに到達した場合（ステップＳ１１３ ＹＥＳ）、クラスタ数比較部４３７は、クラスタ結果を示す情報Ｒを通信部４０１に出力する（ステップＳ１１４）。以上で、本フローチャートの処理を終了する。
【０１２３】
以上、本実施形態の計算サーバ４００は、クラスタを分割する毎に、各属性が分割後の複数のクラスタに共通する属性か分割後のクラスタに固有の属性かを決定し、各データが属するクラスタを階層的に分割する。
これにより、計算サーバ４００は、クラスタ固有の属性が減らすことができるので、クラスタの特徴を理解することが容易となる。また、計算サーバ４００は、クラスタを階層化したので、クラスタ間の関係を理解することが容易となる。
【０１２４】
また、本実施形態の計算サーバ４００は、クラスタリング処理の際に各変数を確率分布でモデル化したので、クラスタリング結果に数学的な妥当性を持たせることができる。その結果、同じ条件化では、計算サーバ４００は、常に同じクラスタリング結果を出力することができる。これにより、どんなユーザが計算サーバ４００を用いてデータをクラスタリングしても同じ結果が得られるので、クラスタリング手法に精通していないユーザでも容易に数学的に妥当性のあるクラスタリング結果を得ることができる。
【０１２５】
＜効果を実証する実験データ＞
続いて、本実施形態における手法ＨＳＣの効果について立証するために行った実験結果について、説明する。
【０１２６】
図１９は、本実施形態におけるクラスタリング処理に係る時間と、従来手法のクラスタリング処理に係る時間とを比較した図である。同図において、縦軸は時間（秒）であり、横軸は属性の数である。同図に置いて、本実施形態における手法はＨＳＣ（Ｈｉｅｒａｒｃｈｉｃａｌ Ｓｕｂｓｅｔ Ｃｌｕｓｔｅｒｉｎｇ）であり、従来手法は、非特許文献１に記載されたＳＣＢＳ（Ｓｕｂｓｅｔ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｂｉｎａｒｙ Ｓｅｑｕｅｎｃｅ）である。
【０１２７】
また、括弧内のＮは、Ｎｅｔｆｌｉｘデータを用いてクラスタリングした結果であることを示し、括弧内のＰは、研究論文のデータを用いてクラスタリングした結果であることを示している。
【０１２８】
ここで、Ｎｅｔｆｌｉｘデータは、１９９９年１１が１１日から２００５年１２月３１日までに１００，４８０，５０７の採点（レーティング）記録からなる。採点記録は、４８０，１８９人の採点者によって採点された１７,７７０の映画からなる。
最初に、少なくとも２０映画を採点した採点者と少なくとも１００人のユーザによって採点された映画が選択されたこの前処理により、データセットを１３６，５８９人の採点者によって採点された９，２６４映画からなる８５，７３０，２０３採点記録までに削減した。各採点記録は、映画タイトルを識別する映画タイトルｉｄと、採点者を識別する採点者ｉｄと、採点と、時刻からなる。
【０１２９】
一方、研究論文のデータは、２００１年から２００８年までにACM CIKM, SIGIR, KDD, and WWWの予稿集における研究論文からなっている。研究論文に登場するストップワード、番号、コーパスに登場する回数が５回未満の単語が削除された。これにより、研究論文のデータは、全部で３０７８文章と２０２８６の種の単語からからなっている。
【０１３０】
同図に置いて、属性が２００００のときは、本実施形態における手法ＨＳＣと従来手法ＳＣＢＳとでクラスタリング処理にかかる時間にほとんど差がない。しかし、属性が増えるに従って、本実施形態における手法ＨＳＣは、従来手法ＳＣＢＳよりもクラスタリング処理にかかる時間が短くなっている。
すなわち、従来手法ＳＣＢＳは、属性の数が増えると処理にかかる時間が線形に増えるのに対して、本実施形態における手法ＨＳＣは、属性の数が増えたことによる影響を受けずに、処理にかかる時間をほぼ一定に保つことができる。
【０１３１】
以下、図１９の実験結果が得られた実験の方法について説明する。まず、研究論文データの文章の数と合わせるために、９，２６４の映画からランダムに３０７８の映画が選択された。次に、採点者（単語）の数が２０，０００から１００，０００まで増加させた。
次に、各データセットから採点者（論文）×映画（単語）の行列からなるデータ行列が準備された。
【０１３２】
次に、ギブスサンプリングの試行回数が１００にセットされ、クラスタの数を２０がセットされて、両方の手法が実行された。これにより、ルートクラスタから始まってクラスタ数が２０になるまでクラスタが繰り返し分割された。そして、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳを用いて、採点者（単語）の数を変える毎に、映画（文章）がクラスタに分類された。
【０１３３】
以上、本実施形態における計算サーバ４００は、クラスタを分割する毎に、各属性が分割後の複数のクラスタに共通する属性か分割後のクラスタに固有の属性かを決定するので、属性の数が多くなっても処理にかかる時間が従来手法ＳＣＢＳよりも増えない。換言すれば、本実施形態における計算サーバ４００は、クラスタを分割する毎にクラスタ間で共通の属性が増えていくので、計算量を減らすことができる。
【０１３４】
これにより、本実施形態における計算サーバ４００は、属性が所定に数より多くなるほどクラスタリングにかかる処理時間を従来手法ＳＣＢＳに比べて短縮することができる。換言すれば、本実施形態における計算サーバ４００は、属性の数が増加しても従来手法ＳＣＢＳと比べて計算量が増加しないという有利な効果を有する。
【０１３５】
図２０は、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとのパープレキシティを比較したテーブルである。同図に置いて、Ｎｅｔｆｌｉｘデータと、研究論文（Ｒｅｓｅａｒｖｈ Ｐａｐｅｒ）のデータとを用いたときの、本実施形態の手法ＨＳＣのパープレキシティの値と従来手法ＳＣＢＳのパープレキシティの値が示されている。ここで、パープレキシティ（ｐｅｒｐｌｅｘｉｔｙ）は、タスクの複雑性を表す尺度であり、クラスタリングの予測が正しければ、パープレキシティの値が小さくなる。
【０１３６】
同図において、Ｎｅｔｆｌｉｘデータについても、研究論文（Ｒｅｓｅａｒｖｈ Ｐａｐｅｒ）のデータを用いてクラスタリングした場合においても、本実施形態の手法ＨＳＣの方が従来手法ＳＣＢＳよりもパープレキシティが片側ｔ検定で有意に小さくなっていることが示されている。ここで、片側ｔ検定で従来手法ＳＣＢＳよりもはＰ＜０．０５で異なる場合、‘＊’の印が付けられ、Ｐ＜０．０１で異なる場合に、‘＊＊’の印が付けられている。
【０１３７】
これにより、本実施形態の手法ＨＳＣは、従来手法ＳＣＢＳよりもクラスタリングの予測が正しいという有利な効果を有する。
これは、従来手法ＳＣＢＳは、各属性は、各クラスタに固有か全クラスタに共通であるかの２者択一であるのに対し、本実施形態の手法ＨＳＣが様々なクラスタ間でどんな属性でも共通にできるという点で柔軟性があるからである。
【０１３８】
ここで、上記パープレキシティＰＰＸは、１００の異なるチェーン（ｃｈａｉｎｓ）からの１００個のデータを用いて、以下の式（６）に従って、算出される。
【０１３９】
【数６】
【０１４０】
ここで、Ｗはテスト属性の数、Ｇは（ギブス）サンプリング系列の異なり数、θｋｌｖｇは、モデルによってサンプリング系列の識別子ｇの中のクラスｋに付随するサブクラスｌにおける属性ｖにクラスｋが割り振られる確率である。また、ｇの上に〜が示されている記号をｇ（チルタ）と称し、θｋｌｖｇ（チルタ）は、モデルによってサンプリング系列の識別子ｇの中のクラスｋにおける属性ｖにクラスｋが割り振られる確率である。
【０１４１】
以下、図２０の実験結果が得られた実験の方法について説明する。この実験では生データをコーパスにある文章（Ｎｅｔｆｌｉｘデータの場合は文章で、研究論文の場合は単語）として、以下の方法でパープレキシティが計算された。ここで、生データにはデータと属性があり、そのデータと属性の組み合わせはＮｅｔｆｌｉｘデータの場合はそれぞれ映画と評論家で、研究論文の場合はそれぞれ論文と単語である。
【０１４２】
まず、研究論文の場合には、ある単語が１回でも出現した場合、その単語の出現数を１に変換した。一方、Ｎｅｔｆｌｉｘデータの場合には、ある映画のレーティングがが存在すれば、その映画のレーティングを１、そうでなければその映画のレーティングを０に変換した。
【０１４３】
次に、各生データの１０％をテストパートとしてランダムに分割し、残りのパートを学習データとした。生データ毎に、テストパートに対してパープレキシティを計算した。
次に、各モデルのパラメータを推定するために学習パートが使用された。最後に、サンプルが採取されたときにクラスタを識別する情報が保存された。
【０１４４】
図２１は、トップＮの正確性が各手法間で比較されたテーブルである。同図において、本実施形態の手法ＨＳＣと、従来の推薦方法であるＣｏｓｉｎｅとＰｅａｒｓｏｎとＩｔｅｍとＳＣＢＳとの間で推薦の正確性が比較されている。比較対象は、Ｎｅｔｆｌｉｘデータを用いて算出された１番目の推薦アイテムの正確性と、５番目の推薦アイテムの正確性と、１０番目の推薦アイテムの正確性である。
【０１４５】
ここで、ＣｏｓｉｎｅとＰｅａｒｓｏｎは、それぞれコサイン類似度またはピアソンの相関係数によって計測されたユーザの類似度に基づいて推薦する方法である。
また、Ｉｔｅｍは、文献（J. K. B. Sarwa, G. Karypis and J. Riedl. Item-based collaborative filtering recommendation algorithms. In WWW, pages 285-295, 2001.）で提案されたピアソンの相関係数によって計測された内容類似度に基づいて推薦する方法である。
【０１４６】
同図において、１０番目の推薦アイテムの正確性において、本実施形態の手法ＨＳＣの正確性の値が従来手法ＳＣＢＳの正確性の値よりも片側ｔ検定で有意に大きくなっている（Ｐ＜０．０５で異なる場合、‘＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは、推薦の正確性においても従来手法ＳＣＢＳよりも向上しているという有利な効果を持っている。
【０１４７】
以下、図２１の実験結果が得られた実験の方法について説明する。クラスタ間を区別し得る属性を選択するという点からみたクラスタの質を計測するために、Ｎｅｔｆｌｉｘデータを用いて協調フィルタリングタスクのパフォーマンスを計算した。Ｎｅｔｆｌｉｘデータにおけるレーティングのバイアスに着目して、ユーザの平均レーティングよりも対象アイテムのレーティングが高い場合にはそのアイテムを購入したとみなして１とし、それ以外の場合にはそのアイテムを購入しなかったとみなして０とした。
【０１４８】
このデータにおいて、ユーザと購入アイテムがそれぞれデータと属性に対応する。Ｋ倍のクロスバリデーション（ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ）を介して、各手法の推薦の予測精度を評価するためにシミュレーションを実行した。Ｋ倍のクロスバリデーション（ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ）とは、オリジナルデータがランダムにＫ個のサブサンプリングに置かれることである。
【０１４９】
このシミュレーションにおいて、テストデータにおける各ユーザを、学習データから採取されたユーザログを用いて各推薦方法を適用したターゲットユーザとして扱った。
この実験において、クラスの数は１２０に固定されたおり、各ユーザは本実施形態の手法ＨＳＣまたは従来手法ＳＣＢＳによって、１２０のクラスのうちの１つのクラスに割り振られた。そして、Ｋが２０という条件下で、１００００回の繰り返しに対して１００回のギブスサンプリングが行われた。
【０１５０】
そして、本実施形態の手法ＨＳＣと従来の４つの手法をデータセットに適用し、トップＮ（Ｎは１、５または１０）の推薦の正確性を比較した。
本実施形態の手法ＨＳＣと従来手法ＳＣＢＳに関しては、ユーザが属するクラスにおいて観測値ｙｉｊ＝１となる確率に従ってトップＮランクのアイテムをターゲットユーザに提示し、これらの推薦アイテムがテストデータに存在することを確認した。
【０１５１】
図２２は、３つのパラメータが各手法間で比較されたテーブルである。同図において、図２１と同じ条件下において各クラスタリング手法によって算出された推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）と、推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）と、Ｇｉｎｉ係数とが示されている。
【０１５２】
ここで、それぞれの指標について詳細に説明する。まず、推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）は、テスト期間にアイテムを購入したユーザ数に対する各推薦方法が推薦可能なユーザ数の割合である。推薦ユーザの被覆率が高いほど、多くのユーザにアイテムを推薦できるので、ユーザ全体にとって価値が高いシステムである。
【０１５３】
推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）は、テスト期間に購入されたアイテムのタイトル数に対する各推薦方法が推薦可能なアイテム数の割合である。推薦オブジェクトの被覆率は、システムが推薦できるシステム中のアイテムドメインの大きさを示す１つの指標である。従って、推薦オブジェクトの被覆率の低いシステムは、ごく限られた選択アイテムしか提示できないから、ユーザにとって価値が低いシステムである。
【０１５４】
Ｇｉｎｉ係数は、アイテムに対するユーザの購入者数の分布の統計的分散を示す指標である。Ｇｉｎｉ係数は、０から１の値をとり、低くなるほど分布が平等であり、高くなるほど分布が偏っていることを意味する。すなわち、値が０に近いほどアイテムごとの購入ユーザ数の格差が少なく、１に近いほど格差が大きいことを意味する。
【０１５５】
Ｇｉｎｉ係数が０の場合、分布が完全に平等、すなわち全てのオブジェクトが正確に同じ数のユーザによって購入されている。一方、Ｇｉｎｉ係数が１の場合、分布が完全に不平等、すなわち１つのアイテムがすべてのユーザによって購入され、他のアイテムは、どのユーザにも購入されてない。
【０１５６】
高いＧｉｎｉ係数となる結果は、２、３個の特定のアイテムがたいていのユーザによって高くランク付けされている傾向にあることを意味し、特定のアイテムばかりが推薦される傾向が強く、ユーザ毎の推薦アイテムの違いは小さくなる。すなわち、アイテム推薦は、ユーザ毎に特化されていないことを意味する。一方、Ｇｉｎｉ係数が０に近いほど、アイテムの推薦がユーザ毎に特化し、アイテム推薦がうまく行われていることを意味する。
【０１５７】
図２２において、本実施形態の手法ＨＳＣにおいて、推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）が最も高く、Ｇｉｎｉ係数が最も０に近い。この結果から、本実施形態の手法ＨＳＣは、他の手法よりも偏りが少なく広い範囲のアイテムをユーザ毎に特化して推薦できることが証明された。
【０１５８】
本実施形態の手法ＨＳＣは、ユーザ間による興味の違いを強調するために、より人気のある瑣末なアイテムに対してより低い重み付けをする。それにより、個人の好みに応じたアイテムに対してより大きな重みをつけることができ、その結果、アイテム推薦の正確性が向上している。
【０１５９】
また、図２２において、本実施形態の手法ＨＳＣと従来手法ＳＣＢＳとの間で、推薦ユーザの被覆率（Ｕｓｅｒ Ｃｏｖｅｒａｇｅ）は同じである。
一方、図２２において、本実施形態の手法ＨＳＣの推薦オブジェクトの被覆率（Ｉｔｅｍ Ｃｏｖｅｒａｇｅ）の値が従来手法ＳＣＢＳの推薦オブジェクトの被覆率の値よりも片側ｔ検定で有意に大きくなっている（Ｐ＜０．０１で異なる場合、‘＊＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは、従来手法ＳＣＢＳよりも、より多くの選択アイテムを提示できることを意味し、ユーザにとって価値が高いクラスリング手法である。
【０１６０】
図２２において、実施形態の手法ＨＳＣの推薦オブジェクトのＧｉｎｉ係数の値が従来手法ＳＣＢＳのＧｉｎｉ係数の値よりも片側ｔ検定で有意に小さくなっている（Ｐ＜０．０１で異なる場合、‘＊＊’の印が付けられている）。
このことから、本実施形態の手法ＨＳＣは従来手法ＳＣＢＳよりも、アイテムに対するユーザの購入者数の分布が平等であるので、全てのオブジェクトがより同数に近いユーザによって購入されていることを意味する。従って、本実施形態の手法ＨＳＣは従来手法ＳＣＢＳよりも、ユーザ毎に特化したアイテムを推薦できるという有利な効果を有する。
【０１６１】
また、本実施形態の計算サーバ４００の各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、計算サーバ４００に係る上述した種々の処理を行ってもよい。
【０１６２】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１６３】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１６４】
以上、本発明の実施形態について図面を参照して詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１６５】
１００ ユーザ端末
２００ サービスサーバ
３００ ファイルサーバ
４００ 計算サーバ（クラスタリング分類装置）
４０１ 通信部
４０２ 制御部
４２０ 識別情報割振部
４３０ クラスタリング処理部
４３１ サブクラス割振部
４３２ サブクラス間差異判定部
４３３ 変数推定部
４３４ エントロピー算出部
４３５ クラス抽出部
４３６ 分割部
４３７ クラスタ数比較部
４４０ 属性選択部
５００ データベースサーバ
【特許請求の範囲】
【請求項１】
各データが属するクラスタを階層的に分割する分割部と、
前記分割部によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部と、
を備えるクラスタリング装置。
【請求項２】
前記各データに対し、ランダムにサブクラスを割り振るサブクラス割振部を更に備え、
前記属性選択部は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、前記属性の値がサブクラス間で違いがない場合は、該属性の値を該サブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とすることを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
前記属性選択部は、属性毎に該属性がサブクラスに固有である確率を算出し、該算出した確率に基づいて、該属性が前記サブクラス間で共通の属性か前記サブクラスに固有の属性かを判定することを特徴とする請求項１または請求項２に記載のクラスタリング装置。
【請求項４】
前記属性選択部は、前記データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出し、該算出した確率に基づいて前記データ毎に該データに割り振られるサブクラスを推定することを特徴とする請求項２または請求項３に記載のクラスタリング装置。
【請求項５】
前記サブクラスを識別するサブクラス識別情報の確率分布が二項分布で表され、前記属性がサブクラスに固有であるか否かを示す固有フラグの確率分布がベルヌーイ分布で表されることを特徴とする請求項２から請求項４のいずれか１項に記載のクラスタリング装置。
【請求項６】
各データが属するクラスタを階層的に分割する分割手順と、
前記分割手順によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択手順と、
を有するクラスタリング方法。
【請求項７】
コンピュータに、
各データが属するクラスタを階層的に分割する分割ステップと、
前記分割ステップによりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択ステップと、
を実行するためのクラスタリングプログラム。
【請求項１】
各データが属するクラスタを階層的に分割する分割部と、
前記分割部によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択部と、
を備えるクラスタリング装置。
【請求項２】
前記各データに対し、ランダムにサブクラスを割り振るサブクラス割振部を更に備え、
前記属性選択部は、属性毎に該属性の値がサブクラス間で違いがあるか否か判定し、前記属性の値がサブクラス間で違いがない場合は、該属性の値を該サブクラス間で共通の属性とし、属性の値がサブクラス間で違いがある場合は、その属性をサブクラス固有の属性とすることを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
前記属性選択部は、属性毎に該属性がサブクラスに固有である確率を算出し、該算出した確率に基づいて、該属性が前記サブクラス間で共通の属性か前記サブクラスに固有の属性かを判定することを特徴とする請求項１または請求項２に記載のクラスタリング装置。
【請求項４】
前記属性選択部は、前記データ毎に該データに割り振られるサブクラスが所定のサブクラスである確率を算出し、該算出した確率に基づいて前記データ毎に該データに割り振られるサブクラスを推定することを特徴とする請求項２または請求項３に記載のクラスタリング装置。
【請求項５】
前記サブクラスを識別するサブクラス識別情報の確率分布が二項分布で表され、前記属性がサブクラスに固有であるか否かを示す固有フラグの確率分布がベルヌーイ分布で表されることを特徴とする請求項２から請求項４のいずれか１項に記載のクラスタリング装置。
【請求項６】
各データが属するクラスタを階層的に分割する分割手順と、
前記分割手順によりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択手順と、
を有するクラスタリング方法。
【請求項７】
コンピュータに、
各データが属するクラスタを階層的に分割する分割ステップと、
前記分割ステップによりクラスタが分割される毎に、分割後の複数のクラスタに共通する属性と分割後のクラスタに固有の属性とを選択する属性選択ステップと、
を実行するためのクラスタリングプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１２−２４３２２５（Ｐ２０１２−２４３２２５Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１５２４５（Ｐ２０１１−１１５２４５）
【出願日】平成２３年５月２３日（２０１１．５．２３）
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月２３日（２０１１．５．２３）
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
[ Back to top ]