(57)【要約】【課題】  非負値行列分解において、欠損値が存在する場合であっても、行列の欠損値を補完し、クラスタの抽出を可能にする。【解決手段】  本発明は、ユーザの商品購買数を示す非負行列X（商品購買行列X）、ユーザの商品カテゴリ購買数を示す非負行列Y（カテゴリ購買行列Y）の要素に欠損値がある場合でも、商品と商品カテゴリの関係を表現した非負行列W（商品カテゴリ対応行列W）を用いて、商品購買行列X、カテゴリ購買行列Yを、それぞれユーザとクラスタの関係を示す非負行列A（ユーザ特徴行列A）とクラスタと商品の関係を示す非負行列B（商品特徴行列B）の積、ユーザ特徴行列Aとクラスタと商品カテゴリの関係を示す非負行列C（カテゴリ特徴行列C）の積に分解し、ユーザ、商品、商品カテゴリにより特徴づけられるクラスタを抽出する。【選択図】  図１０
2016031678.tif 000002
【特許請求の範囲】
【請求項１】
行列形式で与えられるデータからクラスタを抽出するクラスタ抽出装置であって、
第１のオブジェクト群と第２のオブジェクト群の関係について、第１のオブジェクトiを行、第２のオブジェクトjを列とし、該第１のオブジェクトiと該第２のオブジェクトjの関連度を示す非負行列でありミクロ属性をもつ第１のオブジェクト関連度情報行列X=｛xij}と、
前記第１のオブジェクト群と第３のオブジェクト群の関係について、前記第１のオブジェクトiを行、第３のオブジェクトkを列として、該第１のオブジェクトiと該第３のオブジェクトkの関連度を示す非負行列でありマクロ属性をもつ第２のオブジェクト関連度情報行列Y=｛yik｝と、
前記第２のオブジェクト群と前記第３のオブジェクト群の関係について、前記第２のオブジェクトjを行、前記第３のオブジェクトkを列として、該第２のオブジェクトjが該第３のオブジェクトkと関係がある場合は非負実数、関係がない場合をゼロを要素とする非負行列でありミクロな属性とマクロな属性の関係を表す第３のオブジェクト関連度情報行列W={wjk}と、
を取得する情報処理手段と、
前記第１のオブジェクト群と、該第１のオブジェクト群を分類するクラスタ群の関係について、前記第１のオブジェクトiを行、クラスタrを列として、第１のオブジェクトiのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第１のオブジェクト特徴行列A、
及び、
前記第２のオブジェクト群と前記クラスタ群の関係について、前記第２のオブジェクトjを行とし、クラスタrを列として、該第２のオブジェクトjのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第２のオブジェクト特徴行列B、
及び、
前記第３のオブジェクト群と前記クラスタ群の関係について、前記第３のオブジェクトkを行とし、クラスタrを列として、該第３のオブジェクトkのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第３のオブジェクト特徴行列C
を、前記第３のオブジェクト関連度情報行列Wを用いて求める特徴行列推定手段と、
前記特徴行列推定手段で求められた前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列B、前記第３のオブジェクト特徴行列Cから少なくとも１つの特徴づけられたクラスタを抽出する特徴行列処理手段と、
を有することを特徴とするクラスタ抽出装置。
【請求項２】
前記特徴行列推定手段は、
前記第１のオブジェクト関連度情報行列Xのある列のすべての要素が欠損している場合、または、該第１のオブジェクト関連度情報行列Xまたは前記第２のオブジェクト関連度情報行列Yの少なくとも１つの要素が欠損している場合に、
前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列B、及び、前記第３のオブジェクト特徴行列Cを初期化する特徴行列初期化手段と、
パラメータ更新の最大変化幅を示す変数δを初期化する変数初期化手段と、
前記第１のオブジェクト特徴行列Aを第１の更新式により更新し、第１の更新条件に基づいて該変数δを更新する第１のオブジェクト特徴行列A更新手段と、
前記第２のオブジェクト特徴行列Bを第２の更新式により更新し、第２の更新条件に基づいて該変数δを更新する第２のオブジェクト特徴行列B更新手段と、
前記第３のオブジェクト特徴行列Cを第３の更新式により更新し、第３の更新条件に基づいて該変数δを更新する第３のオブジェクト特徴行列C更新手段と、
繰り返しのカウントを更新するカウント更新手段と、
前記繰り返しのカウントが最大数以下、または、前記変数δが所定の閾値εより大きい場合には、前記変数初期化手段、前記第１のオブジェクト特徴行列A更新手段、前記第２のオブジェクト特徴行列B更新手段、前記第３のオブジェクト特徴行列C更新手段、及び前記カウント更新手段を繰り返す繰り返し手段と、
を実行する手段を含み、
前記第１の更新式を、
【数４３】
2016031678.tif 000045
とし、
前記第２の更新式を、
【数４４】
2016031678.tif 000046
とし、
前記第３の更新式を、
【数４５】
2016031678.tif 000047
とし、
（但し、前記第１の更新式、前記第２の更新式、前記第３の更新式において、
【数４６】
2016031678.tif 000048
とし、
【数４７】
2016031678.tif 000049
は前記第１のオブジェクト関連度情報行列Xの第i行目で欠損していない列j全体、
【数４８】
2016031678.tif 000050
は前記第２のオブジェクト関連度情報行列Yの第i行目で欠損していない列ｋ全体、
【数４９】
2016031678.tif 000051
は前記第１のオブジェクト関連度情報行列Xの第ｊ列目で欠損していない行i全体、
【数５０】
2016031678.tif 000052
は前記第２のオブジェクト関連度情報行列Yの第k列目で欠損していない行i全体、
【数５１】
2016031678.tif 000053
は前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列Bによるxijの推定値、
【数５２】
2016031678.tif 000054
は前記第１のオブジェクト特徴行列A、前記第３のオブジェクト特徴行列Cによるyikの推定値）
前記第１の更新条件を、
更新前の第１のオブジェクト特徴行列Aの要素の値と更新後の第１のオブジェクト特徴行列Aの要素の値の差の絶対値の最大値
【数５３】
2016031678.tif 000055
（但し、
【数５４】
2016031678.tif 000056
は代入処理前の第１のオブジェクト特徴行列Aの要素の値、
【数５５】
2016031678.tif 000057
は代入処理後の第１のオブジェクト特徴行列Aの要素の値）
が前記変数δより大きければ、
【数５６】
2016031678.tif 000058
と更新するものとし、
前記第２の更新条件を、
更新前の第２のオブジェクト特徴行列Bの要素の値と更新後の第２のオブジェクト特徴行列Bの要素の値の差の絶対値の最大値
【数５７】
2016031678.tif 000059
(但し、
【数５８】
2016031678.tif 000060
は、代入処理前の第２のオブジェクト特徴行列Bの要素の値、
【数５９】
2016031678.tif 000061
は、代入処理後の第２のオブジェクト特徴行列Bの要素の値）
が前記変数δより大きければ、
【数６０】
2016031678.tif 000062
と更新するものとし、
前記第３の更新条件を、
更新前の第３のオブジェクト特徴行列Cの要素の値と更新後の第３のオブジェクト特徴行列Cの要素の値の差の絶対値の最大値
【数６１】
2016031678.tif 000063
（但し、
【数６２】
2016031678.tif 000064
は、代入処理前の第３のオブジェクト特徴行列Cの要素の値、
【数６３】
2016031678.tif 000065
は、代入処理後の第３のオブジェクト特徴行列Cの要素の値）
が前記変数δより大きければ、
【数６４】
2016031678.tif 000066
と更新するものとする
請求項１記載のクラスタ抽出装置。
【請求項３】
前記特徴行列推定手段は、
前記第１のオブジェクト関連度情報行列X=｛xij｝と前記第２のオブジェクト関連度情報行列Y=｛yik｝には、任意の第１のオブジェクトiについて、前記第２のオブジェクトjの和と前記第３のオブジェクトkは類似した値をとるという関係が成立する
請求項１または２に記載のクラスタ抽出装置。
【請求項４】
前記第１のオブジェクトは、ユーザであり、
前記第２のオブジェクトは、商品であり、
前記第３のオブジェクトは、商品のカテゴリである
請求項１乃至３のいずれか１項に記載のクラスタ抽出装置。
【請求項５】
行列形式で与えられるデータからクラスタを抽出するクラスタ抽出方法であって、
第１のオブジェクト群と第２のオブジェクト群の関係について、第１のオブジェクトiを行、第２のオブジェクトjを列とし、該第１のオブジェクトiと該第２のオブジェクトjの関連度を示す非負行列でありミクロ属性をもつ第１のオブジェクト関連度情報行列X=｛xij}と、
前記第１のオブジェクト群と第３のオブジェクト群の関係について、前記第１のオブジェクトiを行、第３のオブジェクトkを列として、該第１のオブジェクトiと該第３のオブジェクトkの関連度を示す非負行列でありマクロ属性をもつ第２のオブジェクト関連度情報行列Y=｛yik｝と、
前記第２のオブジェクト群と前記第３のオブジェクト群の関係について、前記第２のオブジェクトjを行、前記第３のオブジェクトkを列として、該第２のオブジェクトjが該第３のオブジェクトkと関係がある場合は非負実数、関係がない場合をゼロを要素とする非負行列でありミクロな属性とマクロな属性の関係を表す第３のオブジェクト関連度情報行列W={wjk}と、
を取得する情報処理ステップと、
前記第１のオブジェクト群と、該第１のオブジェクト群を分類するクラスタ群の関係について、前記第１のオブジェクトiを行、クラスタrを列として、第１のオブジェクトiのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第１のオブジェクト特徴行列A、
前記第２のオブジェクト群と前記クラスタ群の関係について、前記第２のオブジェクトjを行とし、クラスタrを列として、該第２のオブジェクトjのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第２のオブジェクト特徴行列B、
前記第３のオブジェクト群と前記クラスタ群の関係について、前記第３のオブジェクトkを行とし、クラスタrを列として、該第３のオブジェクトkのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第３のオブジェクト特徴行列Cを、前記第３のオブジェクト関連度情報行列Wを用いて求める特徴行列推定ステップと、
前記特徴行列推定ステップで求められた前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列B、前記第３のオブジェクト特徴行列Cから特徴づけられたクラスタを抽出する特徴行列処理ステップと、
を行うことを特徴とするクラスタ抽出方法。
【請求項６】
前記特徴行列推定ステップにおいて、
前記第１のオブジェクト関連度情報行列Xのある列のすべての要素が欠損している場合、または、該第１のオブジェクト関連度情報行列Xまたは前記第２のオブジェクト関連度情報行列Yの少なくとも１つの要素が欠損している場合に、
前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列B、及び、前記第３のオブジェクト特徴行列Cを初期化する特徴行列初期化ステップと、
パラメータ更新の最大変化幅を示す変数δを初期化する変数初期化ステップと、
前記第１のオブジェクト特徴行列Aを第１の更新式により更新し、第１の更新条件に基づいて該変数δを更新する第１のオブジェクト特徴行列A更新ステップと、
前記第２のオブジェクト特徴行列Bを第２の更新式により更新し、第２の更新条件に基づいて該変数δを更新する第２のオブジェクト特徴行列B更新ステップと、
前記第３のオブジェクト特徴行列Cを第３の更新式により更新し、第３の更新条件に基づいて該変数δを更新する第３のオブジェクト特徴行列C更新ステップと、
繰り返しのカウントを更新するカウント更新ステップと、
前記繰り返しのカウントが最大数以下、または、前記変数δが所定の閾値εより大きい場合には、前記変数初期化ステップ、前記第１のオブジェクト特徴行列A更新ステップ、前記第２のオブジェクト特徴行列B更新ステップ、前記第３のオブジェクト特徴行列C更新ステップ、及び前記カウント更新ステップを繰り返す繰り返し、
前記第１の更新式を、
【数６５】
2016031678.tif 000067
とし、
前記第２の更新式を、
【数６６】
2016031678.tif 000068
とし、
前記第３の更新式を、
【数６７】
2016031678.tif 000069
とし、
（但し、前記第１の更新式、前記第２の更新式、前記第３の更新式において、
【数６８】
2016031678.tif 000070
とし、
【数６９】
2016031678.tif 000071
は前記第１のオブジェクト関連度情報行列Xの第i行目で欠損していない列j全体、
【数７０】
2016031678.tif 000072
は前記第２のオブジェクト関連度情報行列Yの第i行目で欠損していない列ｋ全体、
【数７１】
2016031678.tif 000073
は前記第１のオブジェクト関連度情報行列Xの第ｊ列目で欠損していない行i全体、
【数７２】
2016031678.tif 000074
は前記第２のオブジェクト関連度情報行列Yの第k列目で欠損していない行i全体、
【数７３】
2016031678.tif 000075
は前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列Bによるxijの推定値、
【数７４】
2016031678.tif 000076
は前記第１のオブジェクト特徴行列A、前記第３のオブジェクト特徴行列Cによるyikの推定値）
前記第１の更新条件を、
更新前の第１のオブジェクト特徴行列Aの要素の値と更新後の第１のオブジェクト特徴行列Aの要素の値の差の絶対値の最大値
【数７５】
2016031678.tif 000077
（但し、
【数７６】
2016031678.tif 000078
は代入処理前の第１のオブジェクト特徴行列Aの要素の値、
【数７７】
2016031678.tif 000079
は代入処理後の第１のオブジェクト特徴行列Aの要素の値）
が前記変数δより大きければ、
【数７８】
2016031678.tif 000080
と更新するものとし、
前記第２の更新条件を、
更新前の第２のオブジェクト特徴行列Bの要素の値と更新後の第２のオブジェクト特徴行列Bの要素の値の差の絶対値の最大値
【数７９】
2016031678.tif 000081
(但し、
【数８０】
2016031678.tif 000082
は、代入処理前の第２のオブジェクト特徴行列Bの要素の値、
【数８１】
2016031678.tif 000083
は、代入処理後の第２のオブジェクト特徴行列Bの要素の値）
が前記変数δより大きければ、
【数８２】
2016031678.tif 000084
と更新するものとし、
前記第３の更新条件を、
更新前の第３のオブジェクト特徴行列Cの要素の値と更新後の第３のオブジェクト特徴行列Cの要素の値の差の絶対値の最大値
【数８３】
2016031678.tif 000085
（但し、
【数８４】
2016031678.tif 000086
は、代入処理前の第３のオブジェクト特徴行列Cの要素の値、
【数８５】
2016031678.tif 000087
は、代入処理後の第３のオブジェクト特徴行列Cの要素の値）
が前記変数δより大きければ、
【数８６】
2016031678.tif 000088
と更新するものとする
請求項５記載のクラスタ抽出方法。
【請求項７】
コンピュータを、
請求項１乃至４のいずれか１項の記載のクラスタ抽出装置の各手段として機能させるためのクラスタ抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタ抽出装置及び方法及びプログラムに係り、特に、E-Commerce(電子商取引)サービスにおいて、行列形式で与えられる商品文書データからクラスタを発見するクラスタ抽出装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
POS(Point of Sales)データに代表される購買履歴などの構造化されたデータや、テキストデータ、画像データなど構造化されていないデータの多くは前処理によって行列形式により表現できることが知られている。これら行列表現されたデータ中に存在するクラスタを発見するための手法として、非負値のみからなる行列を分解する非負値行列分解(NMF：Non-negative Matrix Factorization、以下「NMF」と記す)と呼ばれる手法の有用性がこれまで示されている(例えば非特許文献１参照)。NMFを適用する際に入力される行列データはそれより低次のランクの行列の積に分解される。この各低次行列がそれぞれ各行、各列に対応する事物のクラスタへの寄与度を表しており、クラスタ発見が可能となる。したがって例えば購買履歴データに対し適用することで抽出されたクラスタをもとにユーザへのおすすめ商品リストを作成したり、ニュース記事文書集合に対する適用結果から記事の自動分類が可能となる。
【０００３】
NMFの購買データへの適用例を図１に示す。
【０００４】
購買データを表す商品購買行列X={xij}は行列中の第i行目に対応するユーザによる第ｊ列目に対応する商品の購買数がxijの値となるI行J列の行列である。したがって、商品購買行列Xは行と列がそれぞれ特定のユーザと商品に対応していることになる。このことを「商品購買行列Xがユーザ属性と商品属性を持つ」、と呼ぶこととする。この商品購買行列XにNMFを適用することで、
【０００５】
【数１】
2016031678.tif 000003
となるI行R列のユーザ特徴行列A={air}とJ行R列の商品特徴行列B={bjr}が求まる。但し、記号
【０００６】
【数２】
2016031678.tif 000004
は両者が類似していることを示し、記号の上付きの記号Tは行列の転置を表す。図１のユーザ特徴行列Aの『クラスタ１』に対応する列に着目すると、「ユーザ１」、「ユーザ２」、「ユーザ３」に対応する1行目、2行目、3行目の値が０より大きい値となっていることが分かる。これは「ユーザ１」、「ユーザ２」、「ユーザ３」が『クラスタ１』に所属することを示している。また商品特徴行列Bの『クラスタ１』に対応する行に着目すると、1列目の「ビール１」、2列目の「ビール２」、3列目の「ビール３」という商品に該当する列の値が０より大きい値となっていることが分かる。これは「ビール１」、「ビール２」、「ビール３」という３つの単語が同じユーザに購入されやすいという『クラスタ１』のもつ特徴を表しているといえる。したがって、この「ビール１」、「ビール２」、「ビール３」という商品をまとめて"クラスタ１の商品特徴"と呼ぶ。同様に、『クラスタ１』に所属するユーザのことを"クラスタ１のユーザ特徴"と呼ぶ。『クラスタ１』の商品特徴とユーザ特徴をまとめて"クラスタ１の特徴"と呼ぶこととする。このようにNMFの適用によって得られたユーザ特徴行列Aと商品特徴行列Bをもとに図２のようなクラスタ抽出が可能となる。
【０００７】
なお、クラスタの総数に相当する商品特徴行列のランク数は、解析する前に予め決定しておくものとする。
【０００８】
また、NMFはクラスタ抽出だけでなく欠損値の補完にも利用できることが知られている。その例を図３に示す。図３の商品購買行列X={xij}の定義は図１と同じである。ただし、図１の商品購買行列との違いは、「ユーザ１」の「ビール３」の購買数を表す要素が欠損していることにある。このような場合であってもNMFは他の観測されている値をもとにユーザ特徴行列Aと商品特徴行列Bを求めることができる。ここで求めたユーザ特徴行列Aと商品特徴行列Bを利用することで元の商品購買行列X={xij}の欠損成分を補完した商品購買行列の推定値
【０００９】
【数３】
2016031678.tif 000005
が求まり、欠損していた要素の値も求めることができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】澤田宏, "非負値行列因子分解NMFの基礎とデータ／信号解析への応用", 電子情報通信学会誌, Vol. 95, No. 9, pp. 829-833, 2012.
【非特許文献２】K. Takeuchi, K. Ishiguro, A. Kimura, and H. Sawada, Non-negative Multiple Matrix Factorization, Proceedings of 23rd International Joint Conference on Artificial Intelligence (IJCAI2013), pp. 1713-1720, 2013.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
これ以降、ユーザ属性と商品属性を合わせて「ミクロ属性」と呼ぶこととする。合わせて、このミクロ属性と対応関係を持つ属性のことを「マクロ属性」と呼ぶこととする。
【００１２】
マクロ属性の例には、ミクロ属性である商品属性と対応関係をもつ、商品カテゴリを表すカテゴリ属性が挙げられる。総カテゴリ数をKとする時、商品属性とカテゴリ属性の対応関係はJ×K行列W={wjk}によって表現できる。当該行列Wは、要素wjkが商品jがカテゴリkに属する時1, そうでなければ0をとる行列である。なお、wjkの値は0または1に限定されず、0または正の整数値であればよい。ただし、負の数は用いない。
【００１３】
本発明で考える問題は、ミクロ属性とマクロ属性の対応関係を与える行列Wが既知のもと、ミクロ属性をもつ商品購買行列X={xij}、マクロ属性をもつカテゴリ購買行列Y={yik}という２つの行列からクラスタ抽出を行うという問題である。なお、カテゴリ購買行列Yは要素yikがユーザiのカテゴリkに属する商品の購買数を表す行列である。また、商品購買行列X={xij}とカテゴリ購買行列Y={yik}の間には、任意のユーザiに対して、
【００１４】
【数４】
2016031678.tif 000006
（ただし、jはカテゴリkに属する商品）との関係が成立する。つまり、任意のユーザについて、商品購買数の和とカテゴリの購買数は類似した値をとる。
【００１５】
ここでの類似の程度は、NMFを適用する際に用いた行列の類似尺度（類似していることを記号
【００１６】
【数５】
2016031678.tif 000007
で表現する）として何を利用するかにより定まる。例えば任意の２つのI行J列の行列U={uij}, V={vij}の類似の尺度として、ユークリッド距離を用いて定義できる
【００１７】
【数６】
2016031678.tif 000008
を利用する場合を考える。但し、
【００１８】
【数７】
2016031678.tif 000009
の値が小さければ小さいほど両者が類似していることを表し、両者が完全に一致した時には0になる。
【００１９】
この尺度のもと、
【００２０】
【数８】
2016031678.tif 000010
と行列分解を行った際の両者の類似の程度は
【００２１】
【数９】
2016031678.tif 000011
で与えられる。商品購買行列X={xij}とカテゴリ購買行列Y={yik}の要素間には、任意のユーザiに対して、(Σjxij−yik)2（ただし、jはカテゴリkに属する商品）の値が
【００２２】
【数１０】
2016031678.tif 000012
の値と同等となる程度の類似性が必要となる。ユークリッド距離以外の尺度でも同様である。
【００２３】
しかしながら、上記の非特許文献１の技術は単一の行列を扱う手法であり、ミクロ属性を持つ商品購買行列X={xij}と、マクロ属性を持つカテゴリ購買行列Y={yik}の２つの行列を入力することはできなかった。一方、上記の非特許文献２では複数の行列を同時に扱うことは可能である。したがって、欠損のない商品購買行列Xとカテゴリ購買行列Yであれば、図４に示すように
【００２４】
【数１１】
2016031678.tif 000013
という行列分解と、
【００２５】
【数１２】
2016031678.tif 000014
という行列分解を行うことで図５に示すようにクラスタ抽出結果を得ることが可能である（C={ckr}はK行R列のカテゴリ特徴行列を表す）。しかしながら、この非特許文献２は行列Wによって表現されるミクロ属性とマクロ属性の関係性は考慮していないために、欠損値が補完できず、適切なクラスタ抽出が行えない状況が存在する。図６にその例を示す。
【００２６】
図６では商品購買行列X={xij}の「ビール3」に該当する列の要素が全て欠損値となっていることが分かる。非特許文献２の方法では、商品購買行列Xの「ビール1」，「ビール2」，「ビール3」に該当する列とカテゴリ購買行列Yのビールカテゴリに該当する列の関係性は考慮されない。そのため、商品特徴行列Bの「ビール3」に該当する列の要素の推定には商品購買行列Xの「ビール3」の該当する列の要素が必要となり、この列全てが欠損値の場合には正しく欠損値を補完することができない。
【００２７】
本発明は、上記の点に鑑みなされたもので、非負値行列分解において、ミクロな属性とマクロな属性の関係を考慮して行列分解を行うことで、図６のように従来の手法では扱うことのできなかった欠損値が存在する場合であっても、行列の欠損値を補完し、クラスタ抽出が可能なクラスタ抽出装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２８】
一態様によれば、行列形式で与えられるデータからクラスタを抽出するクラスタ抽出装置であって、
第１のオブジェクト群と第２のオブジェクト群の関係について、第１のオブジェクトiを行、第２のオブジェクトjを列とし、該第１のオブジェクトiと該第２のオブジェクトjの関連度を示す非負行列でありミクロ属性をもつ第１のオブジェクト関連度情報行列X=｛xij}と、
前記第１のオブジェクト群と第３のオブジェクト群の関係について、前記第１のオブジェクトiを行、第３のオブジェクトkを列として、該第１のオブジェクトiと該第３のオブジェクトkの関連度を示す非負行列でありマクロ属性をもつ第２のオブジェクト関連度情報行列Y=｛yik｝と、
前記第２のオブジェクト群と前記第３のオブジェクト群の関係について、前記第２のオブジェクトjを行、前記第３のオブジェクトkを列として、該第２のオブジェクトjが該第３のオブジェクトkと関係がある場合は非負実数、関係がない場合をゼロを要素とする非負行列でありミクロな属性とマクロな属性の関係を表す第３のオブジェクト関連度情報行列W={wjk}と、
を取得する情報処理手段と、
前記第１のオブジェクト群と、該第１のオブジェクト群を分類するクラスタ群の関係について、前記第１のオブジェクトiを行、クラスタrを列として、第１のオブジェクトiのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第１のオブジェクト特徴行列A、
及び、
前記第２のオブジェクト群と前記クラスタ群の関係について、前記第２のオブジェクトjを行とし、クラスタrを列として、該第２のオブジェクトjのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第２のオブジェクト特徴行列B、
及び、
前記第３のオブジェクト群と前記クラスタ群の関係について、前記第３のオブジェクトkを行とし、クラスタrを列として、該第３のオブジェクトkのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列である第３のオブジェクト特徴行列Cを、前記第３のオブジェクト関連度情報行列Wを用いて求める特徴行列推定手段と、
前記特徴行列推定手段で求められた前記第１のオブジェクト特徴行列A、前記第２のオブジェクト特徴行列B、前記第３のオブジェクト特徴行列Cから少なくとも１つの特徴づけられたクラスタを抽出する特徴行列処理手段と、
を有するクラスタ抽出装置が提供される。
【発明の効果】
【００２９】
一態様によれば、ミクロ属性を持つ非負行列X、マクロ属性を持つ非負行列Y、ミクロ属性とマクロ属性の双方を持つ非負行列Wを用いて行列分解を行うことにより、従来手法では扱うことができなかった欠損値が存在する場合であっても、クラスタ抽出が可能となる。
【図面の簡単な説明】
【００３０】
【図１】非負値行列分解（NMF）の適用例。
【図２】非負値行列分解（NMF）を適用して得られるクラスタリング結果の例。
【図３】非負値行列分解（NMF）を適用することによる欠損値補完の例。
【図４】非特許文献２の方法の適用例。
【図５】非特許文献２の方法を適用して得られるクラスタリング結果の例。
【図６】非特許文献２の方法を適用することによる欠損値補完が不可能となる例。
【図７】本発明を適用することによる欠損値補完の例（その１）。
【図８】本発明を適用することによる欠損値補完の例（その２）。
【図９】本発明の一実施の形態における概要動作のフローチャート。
【図１０】本発明の一実施の形態におけるクラスタ抽出装置の構成例。
【図１１】本発明の一実施の形態における商品購買情報テーブルの例。
【図１２】本発明の一実施の形態におけるカテゴリ購買情報テーブルの例。
【図１３】本発明の一実施の形態における商品カテゴリ対応情報テーブルの例。
【図１４】本発明の一実施の形態におけるユーザ特徴テーブルの例。
【図１５】本発明の一実施の形態における商品特徴テーブルの例。
【図１６】本発明の一実施の形態におけるカテゴリ特徴テーブルの例。
【図１７】本発明の一実施の形態におけるクラスタ抽出装置の処理のフローチャート。
【図１８】本発明の一実施の形態における特徴行列推定処理のフローチャート。
【発明を実施するための形態】
【００３１】
以下、図面と共に本発明の実施の形態を説明する。
【００３２】
まず、本発明で用いる行列を一般化した形態を示す。
【００３３】
オブジェクト関連度情報行列Xを、第１のオブジェクト群と第２のオブジェクト群の関係について、第１のオブジェクトiを行、第２のオブジェクトjを列とし、第１のオブジェクトiと第２のオブジェクトjの関連度を表すゼロ以上の実数を要素とし、ミクロ属性を有する非負行列とする。
【００３４】
オブジェクト関連度情報行列Yを、第１のオブジェクト群と第３のオブジェクト群の関係について、第１のオブジェクトiを行、第３のオブジェクトkを列とし、第１のオブジェクトiと第３のオブジェクトkの関連度を表すゼロ以上の実数を要素とし、マクロ属性を有する非負行列とする。
【００３５】
オブジェクト関連度情報行列Wを、第２のオブジェクト群と第３のオブジェクト群の関係について、第２のオブジェクトjを行、第３のオブジェクトkを列として、第２のオブジェクトjが第３のオブジェクトkと関係がある場合は非負実数、関係がない場合はゼロを要素とし、ミクロ属性とマクロ属性の両方を有する非負行列とする。
【００３６】
オブジェクト特徴行列Aを、第１のオブジェクト群とクラスタ群の関係について、第１のオブジェクトiを行、クラスタrを列として、第１のオブジェクトiのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列とする。
【００３７】
オブジェクト特徴行列Bを、第２のオブジェクト群とクラスタ群の関係について、第２のオブジェクトjを行、クラスタrを列として、第２のオブジェクトjのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列とする。
【００３８】
オブジェクト特徴行列Cを、第３のオブジェクト群とクラスタ群の関係について、第３のオブジェクトkを行、クラスタrを列として、第３のオブジェクトkのクラスタrへの所属度合いを表すゼロ以上の実数を要素とする非負行列とする。
【００３９】
以下の説明では、オブジェクト関連度情報行列Xを「商品購買行列X」、オブジェクト関連度情報行列Yを「カテゴリ購買行列Y」、オブジェクト関連度情報行列Wを「商品カテゴリ対応行列W」とし、第１のオブジェクトを「ユーザ」、第２のオブジェクトを「商品」、第３のオブジェクトを「商品のカテゴリ」とし、オブジェクト特徴行列Aを「ユーザ特徴行列A」、オブジェクト特徴行列Bを「商品特徴行列B」、オブジェクト特徴行列Cを「カテゴリ特徴行列C」として説明する。
【００４０】
また、各オブジェクトの内容は、商品購買情報テーブル、カテゴリ購買情報テーブル、商品カテゴリ対応情報テーブルとして図１１〜図１３を参照して後述する。
【００４１】
本発明では、ミクロな属性とマクロな属性の関係を表す商品カテゴリ対応行列Wを利用して、従来の手法では扱うことのできなかった欠損値が存在する場合であっても、欠損値を補完し、クラスタ抽出が可能な非負値行列分解手法を提案する。本発明では、図６で入力として用いた商品購買行列Xとカテゴリ購買行列Yに加え、商品の所属カテゴリを表すJ行K列の商品カテゴリ対応行列W={wjk}を利用する。このデータを用いて、本発明では非特許文献２の方法と同じく、
【００４２】
【数１３】
2016031678.tif 000015
という行列分解形を考える。ただし、本発明では商品特徴行列Bとカテゴリ特徴行列Cの間にWTB=Cが成立するという制約条件を導入する。上記の設定のもと、図７に図６と同じ欠損値を持つ商品購買行列Xに対する本発明の適用例を示す。
【００４３】
制約条件WTB=Cにより、図７中の商品特徴行列Bが与えられたもとでは、カテゴリ特徴行列Cは商品特徴行列Bの要素を用いて図中で示す要素の値を持たなくてはならない。すると、カテゴリ購買行列Yとそれの予測値
【００４４】
【数１４】
2016031678.tif 000016
の間で等号が成り立つためにはb31=1,b32=0が成り立たなければならないことが分かる。
【００４５】
したがって、この制約条件により、商品特徴行列Bの「ビール3」に該当する列の要素が推定でき、商品購買行列Xの「ビール3」の該当する列の欠損値も補完可能となり所望の結果が得られていることが分かる。本発明の方法は、図８に示すようにカテゴリ購買行列Yに欠損値があっても適用可能である。
【００４６】
図７のようにある列全てが欠損する、"列欠損"のパターンについては、従来の非特許文献２記載の方法では扱うことができなかった。これに対して、本発明はこのような列欠損パターンについて取り扱うことが可能である。
【００４７】
更に、図８のように、商品購買行列Xの列欠損になっている商品（図７の「ビール3」）に対応するカテゴリ（図７の「ビールカテゴリ」）のカテゴリ購買行列Yの列が列欠損にはなっていない場合も本発明は取り扱うことができる。
【００４８】
図９は、本発明の一実施の形態における概要動作のフローチャートである。
【００４９】
ステップ１）  クラスタ抽出装置は、外部から入力された商品購買行列、カテゴリ購買行列、商品カテゴリ対応行列を取得し、各行列の要素をテーブルのフィールドに設定する。
【００５０】
ステップ２）  各テーブルの情報を用いて各特徴行列を推定する。
【００５１】
ステップ３）  各特徴行列を出力する。
【００５２】
図１０は、本発明の一実施の形態における装置の構成例である。
【００５３】
同図に示すクラスタ抽出装置１は、商品購買情報処理部１０、カテゴリ購買情報処理部２０、商品カテゴリ対応情報処理部３０、特徴行列推定部４０、特徴行列処理部５０、記憶部６０を有し、入出力部７０は入力装置や表示装置等の外部装置２に接続されている。
【００５４】
記憶部６０は、商品購買情報テーブル６１、カテゴリ購買情報テーブル６２、商品カテゴリ対応情報テーブル６３、ユーザ特徴テーブル６４、商品特徴テーブル６５、カテゴリ特徴テーブル６６を有する。
【００５５】
以下に各テーブルについて説明する。なお、テーブル形式のデータは行列形式にて表現できることから、以下では、各テーブルと各特徴行列を同一視し、区別せずに用いる。
【００５６】
＜商品購買情報テーブル６１＞
商品購買情報テーブル６１は、図１１に示すように、ユーザIDフィールド(i)、商品IDフィールド(j)、購買数フィールド(xij)を有する。ユーザIDフィールド(i)は、商品購買情報処理部１０により追加されたユーザを特定する識別子が設定される。商品IDフィールド(j)は、商品購買情報処理部１０により追加されたユーザの購入した商品を特定する識別子が設定される。購買数フィールド(xij)は、商品購買情報処理部１０により"１"、または当該商品の当該ユーザの購買数が設定される。なお、購買数の値には"０"または正の整数値を設定できるが、負の数を設定することはできない。
【００５７】
＜カテゴリ購買情報テーブル６２＞
カテゴリ購買情報テーブル６２は、図１２に示すように、ユーザIDフィールド(i)、カテゴリIDフィールド(k)、購買数フィールド(yik)を有する。ユーザIDフィールド(i)は、カテゴリ購買情報処理部２０により追加されたユーザを特定する識別子が設定される。カテゴリIDフィールド(k)は、カテゴリ購買情報処理部２０により追加されたユーザの購入した商品のカテゴリを特定する識別子が設定される。購買数フィールド(yik)は、カテゴリ購買情報処理部２０により"１"、または当該カテゴリの当該ユーザの購買数が設定される。なお、購買数の値には"０"または正の整数値を設定できるが、負の数を設定することはできない。
【００５８】
＜商品カテゴリ対応情報テーブル６３＞
商品カテゴリ対応情報テーブル６３は、図１３に示すように、商品IDフィールド(j)、カテゴリIDフィールド(k)、所属値フィールド(wjk)を有する。商品IDフィールド(j)は、商品カテゴリ対応情報処理部３０により商品を特定する識別子が設定される。カテゴリIDフィールド(k)は、商品カテゴリ対応情報処理部３０によりカテゴリを特定する識別子が設定される。所属値フィールド(wjk)には、商品カテゴリ対応情報処理部３０によって当該商品が当該カテゴリに所属する場合には"１"、そうでなければ"０"が設定される。
【００５９】
＜ユーザ特徴テーブル６４＞
ユーザ特徴テーブル６４は、図１４に示すように、ユーザIDフィールド(i)と、クラスタIDフィールド(r)と、ユーザ特徴値フィールド(air)を有する。ユーザIDフィールド(i)には特徴行列推定部４０によりユーザを特定する識別子が設定される。クラスタIDフィールド(r)には、特徴行列推定部４０によりクラスタを特定する識別子が設定される。ユーザ特徴値フィールド(air)には、特徴行列推定部４０により算出された当該ユーザの当該クラスタに対する特徴値が設定される。
【００６０】
＜商品特徴テーブル６５＞
商品特徴テーブル６５は、図１５に示すように、商品IDフィールド(j)と、クラスタIDフィールド(r)と、商品特徴値フィールド(bjr)を有する。商品IDフィールド(j)には特徴行列推定部４０により商品を特定する識別子が設定される。クラスタIDフィールド(r)には、特徴行列推定部４０によりクラスタを特定する識別子が設定される。商品特徴値フィールド(bjr)には、特徴行列推定部４０により算出された当該商品の当該クラスタに対する特徴値が設定される。
【００６１】
＜カテゴリ特徴テーブル６６＞
カテゴリ特徴テーブル６６は、図１６に示すように、カテゴリIDフィールド(k)と、クラスタIDフィールド(r)と、カテゴリ特徴値フィールド(ckr)を有する。カテゴリIDフィールド(k)には特徴行列推定部４０によりカテゴリを特定する識別子が設定される。クラスタIDフィールド(r)には、特徴行列推定部４０によりクラスタを特定する識別子が設定される。カテゴリ特徴値フィールド(ckr)には、特徴行列推定部４０により算出された当該カテゴリの当該クラスタに対する特徴値が設定される。
【００６２】
上記の構成における動作を説明する。
【００６３】
図１７は、本発明の一実施の形態におけるクラスタ抽出装置の処理のフローチャートである。
【００６４】
本実施の形態では、商品購買行列、カテゴリ購買行列及び商品カテゴリ対応行列を入力として特徴行列を推定し、特徴行列を出力することを考える。以下に具体的な動作を説明する。
【００６５】
ステップ１００）商品購買情報処理部１０は、入力された商品購買行列に基づき、ユーザID毎および商品ID毎の購買数を商品購買情報テーブル６１に格納する処理を行う。具体的には、商品購買情報処理部１０は、図１１に示す商品購買情報テーブル６１に、追加されたユーザ、商品、購買数に応じて、ユーザIDフィールド、商品IDフィールド、購買数フィールドの値を設定した行を挿入する。
【００６６】
商品購買情報処理部１０による商品購買情報更新のタイミングは、例えば、システム管理者が外部装置２から供給されるデータをもとに手動で管理できるようにしてもよいし、新たな購買が発生した場合に外部装置２が自動的に処理を起動するようにしてもよい。
【００６７】
ステップ２００）カテゴリ購買情報処理部２０は、入力されたカテゴリ購買行列に基づき、ユーザID毎およびカテゴリID毎の購買数をカテゴリ購買情報テーブル６２に格納する処理を行う。具体的には、カテゴリ購買情報処理部２０は、図１２に示すカテゴリ購買情報テーブル６２に、追加されたユーザ、カテゴリ、購買数に応じて、ユーザIDフィールド、カテゴリIDフィールド、購買数フィールドの値を設定した行を挿入する。
【００６８】
カテゴリ購買情報処理部２０によるカテゴリ購買情報更新のタイミングは、例えば外部装置２から供給されるPOSデータをもとにシステム管理者が手動で管理できるようにしてもよいし、新たな購買が発生した場合に外部装置２から自動的に処理を起動するようにしてもよい。
【００６９】
ステップ３００）商品カテゴリ対応情報処理部３０は、入力された商品カテゴリ対応行列に基づき、ユーザID毎およびカテゴリID毎の所属値を商品カテゴリ対応情報テーブル６３に格納する処理を行う。具体的には、商品カテゴリ対応情報処理部３０は、図１３に示す商品カテゴリ対応情報テーブル６３に、追加された商品、カテゴリに応じて、ユーザIDフィールド、カテゴリIDフィールド、所属値フィールドの値を設定した行を挿入する。
【００７０】
商品カテゴリ対応情報処理部３０による商品カテゴリ対応情報更新のタイミングは、例えば外部装置２から供給されるPOSデータをもとにシステム管理者が手動で管理できるようにしてもよいし、新たな商品が出現した場合に外部装置２から自動的に処理を起動するようにしてもよい。
【００７１】
ステップ４００）特徴行列推定部４０は、以下の方法で特徴を推定し、記憶部６０のユーザ特徴テーブル６４、商品特徴テーブル６５、カテゴリ特徴テーブル６６に格納する。図１８に特徴行列推定時のフローチャートを示す。以下において、商品購買情報テーブル６１中に存在する全データを
【００７２】
【数１５】
2016031678.tif 000017
とし、カテゴリ購買情報テーブル６２中に存在する全データを
【００７３】
【数１６】
2016031678.tif 000018
とし、商品カテゴリ対応情報テーブル６３に存在する全データを
【００７４】
【数１７】
2016031678.tif 000019
とする。ユーザ特徴行列A、商品特徴行列B、カテゴリ特徴行列Cをそれぞれ、
【００７５】
【数１８】
2016031678.tif 000020
とする。Iが全ユーザ数、Jが全商品数、Kが全カテゴリ数、Rが全クラスタ数を表す。iがユーザを特定する識別子、jが商品を特定する識別子、kがカテゴリを特定する識別子、rがクラスタを特定する識別子に対応する。
【００７６】
ステップ４１０）ユーザ特徴行列Aおよび商品特徴行列B、カテゴリ特徴行列Cをそれぞれ初期化する。また、終了条件の閾値ε、最大繰り返し回数を設定する。
【００７７】
ステップ４２０）終了条件に用いる変数として特徴更新の最大変化幅を示す変数δを初期化する。
【００７８】
ステップ４３０）後述する式(1)に従いユーザ特徴行列Aを更新する。その後、更新前のユーザ特徴行列Aの要素の値と更新後のユーザ特徴行列Aの要素の値の差の絶対値の最大値
【００７９】
【数１９】
2016031678.tif 000021
がδより大きければ、
【００８０】
【数２０】
2016031678.tif 000022
と更新する。なお記号「←」は右辺の計算結果を左辺の変数に代入する処理を意味する。なお、代入処理前のユーザ特徴行列Aの要素の値を
【００８１】
【数２１】
2016031678.tif 000023
とし、代入処理後のユーザ特徴行列Aの要素の値を
【００８２】
【数２２】
2016031678.tif 000024
として記述した。
【００８３】
ステップ４４０）後述する式（2）に従い商品特徴行列Bを更新する。その後、更新前の商品特徴行列Bの要素の値と更新後の商品特徴行列Bの要素の値の差の絶対値の最大値
【００８４】
【数２３】
2016031678.tif 000025
がδより大きければ、
【００８５】
【数２４】
2016031678.tif 000026
と更新する。代入処理前の商品特徴行列Bの要素の値を
【００８６】
【数２５】
2016031678.tif 000027
とし、代入処理後の商品特徴行列Bの要素の値を
【００８７】
【数２６】
2016031678.tif 000028
として記述した。
【００８８】
ステップ４５０）後述する式(3)に従いカテゴリ特徴行列Cを更新する。その後、更新前のカテゴリ特徴行列Cの要素の値と更新後のカテゴリ特徴行列Cの要素の値の差の絶対値の最大値
【００８９】
【数２７】
2016031678.tif 000029
がδより大きければ、
【００９０】
【数２８】
2016031678.tif 000030
と更新する。代入処理前のカテゴリ特徴行列Cの要素の値を
【００９１】
【数２９】
2016031678.tif 000031
とし、代入処理後のカテゴリ特徴行列Cの要素の値を
【００９２】
【数３０】
2016031678.tif 000032
として記述した。
【００９３】
ステップ４６０）計算繰り返し回数に１を加え、更新する。
【００９４】
ステップ４７０）計算繰り返し回数が予め定めた最大繰り返し数を超えるか、特徴更新による最大変化幅を表すδが予め定めた閾値εより小さければ終了し、そうでなければ、更新した後ステップ４２０に戻る。
【００９５】
ステップ４３０，４４０，４５０における式(1),式(2),式(3)は以下の通りである。
【００９６】
【数３１】
2016031678.tif 000033
但し、
【００９７】
【数３２】
2016031678.tif 000034
とする。また、
【００９８】
【数３３】
2016031678.tif 000035
は行列Xの第i行目で欠損していない列j全体、
【００９９】
【数３４】
2016031678.tif 000036
は行列Yの第i行目で欠損していない列ｋ全体を表す。同様に
【０１００】
【数３５】
2016031678.tif 000037
は行列Xの第ｊ列目で欠損していない行i全体、
【０１０１】
【数３６】
2016031678.tif 000038
は行列Yの第k列目で欠損していない行i全体を表す。
【０１０２】
【数３７】
2016031678.tif 000039
はユーザ特徴行列A、商品特徴行列Bによるxijの推定値、
【０１０３】
【数３８】
2016031678.tif 000040
はユーザ特徴行列A、カテゴリ特徴行列Cによるyikの推定値であると見なせる。
【０１０４】
上記の式(1)、式(2)、式(3)は、前述の制約条件が反映されたものである。
【０１０５】
上記の式(1)、式(2)、式(3)の各更新式は全てのユーザi、商品j、カテゴリkについて、
【０１０６】
【数３９】
2016031678.tif 000041
が成立する時、左辺と右辺が一致し、更新の最大変化幅を示す変数δの値が閾値ε以下となるため、更新が停止することが分かる。またあるユーザiについて、全てのj, kについて、
【０１０７】
【数４０】
2016031678.tif 000042
である時に式(1)の更新を行うと、右辺の分子が右辺の分母より大きくなるために、airを現在の値よりも大きくなるように更新することとなり、
【０１０８】
【数４１】
2016031678.tif 000043
と
【０１０９】
【数４２】
2016031678.tif 000044
の値が大きくなるようにユーザ特徴テーブル６４のユーザ特徴値フィールドの特徴airを更新する。
【０１１０】
ステップ５００）図１７を再度参照する。特徴行列処理部５０は、ユーザ特徴テーブル６４、商品特徴テーブル６５、カテゴリ特徴テーブル６６を参照し、リクエストの引数に対応する特徴を出力する。
【０１１１】
出力処理は、例えば、外部装置２から特徴出力のリクエストが入力された場合に実行すればよい。出力は全特徴を出力する場合には、ユーザ特徴テーブル６４、商品特徴テーブル６５、カテゴリ特徴テーブル６６の全ての行を出力すればよいし、クラスタの商品特徴のみを利用する場合には、例えば、リクエストの引数をクラスタＩＤとして、商品特徴テーブル６５から、該クラスタＩＤを持つ行の商品ＩＤフィールド、商品特徴値フィールドを出力した後、商品特徴値フィールドの値の大きい順に商品ＩＤ１０件を特定することでクラスタの商品特徴を求めることができる。
【０１１２】
なお、上記の実施の形態では、商品購買行列とカテゴリ購買行列を表現した行列からクラスタを抽出する例を示しているが、この例に限定されない。例えば、文書と文書中の単語を出現数を表現する行列、文書の所属カテゴリとカテゴリ中の単語の出現数を表現する行列の組など、商品、ユーザ、カテゴリのように１つ１つにID番号を付与して識別可能であり行列形式としてデータを表現することが可能な事物であり、商品とその所属カテゴリのようにミクロとマクロの関係性が存在するものならば、あらゆるものが本装置によるクラスタ抽出が可能である。また、出現数や購入回数のように整数である必要もなく、一般に0以上の実数であればよい。入力となる行列が３つ以上存在する場合にも本発明による方法は適用可能である。例えば、入力される行列として、商品購買行列、カテゴリ購買行列、商品カテゴリ対応行列の３つの行列に加えて、例えば２０代女性、３０代男性等のユーザグループ毎の購入商品を表すグループ購買行列、ユーザとその所属グループを表すユーザグループ対応行列を加えた計５つの行列を入力とする場合、上記の制約条件WTB=Cの他にもう一つ制約条件が増えることになるが、当該制約条件WTB=Cはそのまま利用することが可能である。
【０１１３】
本実施の形態に係るクラスタ抽出装置１は、例えば、１つ又は複数のコンピュータに、本実施の形態で説明した処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、クラスタ抽出装置１が有する機能は、当該コンピュータに内蔵されるCPUやメモリ、ハードディスクなどのハードウェア資源を用いて、クラスタ抽出装置１で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【０１１４】
本発明は、上記の実施の形態に限定されることなく、種々変更・応用が可能である。
【符号の説明】
【０１１５】
１  クラスタ抽出装置
２  外部装置
１０  商品購買情報処理部
２０  カテゴリ購買情報処理部
３０  商品カテゴリ対応情報処理部
４０  特徴行列推定部
５０  特徴行列処理部
６０  記憶部
６１  商品購買情報テーブル
６２  カテゴリ購買情報テーブル
６３  商品カテゴリ対応情報テーブル
６４  ユーザ特徴テーブル
６５  商品特徴テーブル
６６  カテゴリ特徴テーブル
７０  入出力部
【図１】
2016031678.tif 000089
【図２】
2016031678.tif 000090
【図３】
2016031678.tif 000091
【図４】
2016031678.tif 000092
【図５】
2016031678.tif 000093
【図６】
2016031678.tif 000094
【図７】
2016031678.tif 000095
【図８】
2016031678.tif 000096
【図９】
2016031678.tif 000097
【図１０】
2016031678.tif 000098
【図１１】
2016031678.tif 000099
【図１２】
2016031678.tif 000100
【図１３】
2016031678.tif 000101
【図１４】
2016031678.tif 000102
【図１５】
2016031678.tif 000103
【図１６】
2016031678.tif 000104
【図１７】
2016031678.tif 000105
【図１８】
2016031678.tif 000106