(57)【特許請求の範囲】
【請求項１】
Ｎ個の第一対象物とＭ個の第二対象物のそれぞれの関連度を示すＮ行Ｍ列の基礎行列を、３つの第一行列、第二行列及び第三行列に分解して前記第一対象物及び前記第二対象物とをクラスタリングするデータ分析装置であって、
前記基礎行列の各要素に対して、前記関連度を示す値が入力された前記基礎行列を取得する取得部と、
前記第一対象物及び前記第二対象物のクラスタ数を示すＫを設定する設定部と、
前記基礎行列を少なくとも３つの前記基礎行列の部分行列に分割する分割部と、
前記部分行列のそれぞれに対して、特異値の大きい方からＫ個までを用いた特異値分解を行った結果を用いて、変換行列を生成する変換行列生成部と、
前記部分行列のそれぞれと、それらに対応する変換行列とで内積計算を行い、前記部分行列を圧縮する内積計算部と、
圧縮された前記部分行列を用いて、３階のテンソルを作成するテンソル生成部と、
前記テンソルを、ＣＰ分解(ＣＡＮＤＥＣＯＭＰ／ＰＡＲＡＦＡＣ分解)を用いて分解する分解部と、
前記分解部の分解結果を用いて、前記基礎行列を３つに分解した前記第一行列、前記第二行列及び前記第三行列を算出する算出部と、
前記第一行列、前記第二行列及び前記第三行列の少なくとも一つを出力することで、前記第一対象物及び前記第二対象物のクラスタリング結果を出力する出力部と、
を含むデータ分析装置。
【請求項２】
さらに、前記取得部で取得された前記基礎行列が対称行列でない場合に、前記基礎行列の転置行列を用いて対称行列に変形する入力変形部を含む
請求項１に記載のデータ分析装置。
【請求項３】
前記変換行列生成部は、計算した特異値分解の結果を用いて、特異値全体の和に対して、特異値の上位からの和が所定値以上になるＫを設定する
請求項１または２に記載のデータ分析装置。
【請求項４】
前記変換行列生成部は、計算した特異値分解の結果を用いて、特異値全体の２乗和に対して、特異値の上位からの２乗和が所定値以上になるＫを設定する
請求項１または２に記載のデータ分析装置。
【請求項５】
前記分解部は、特異値分解を用いて分解する
請求項１〜４のいずれか一項に記載のデータ分析装置。
【請求項６】
さらに、
前記算出部で算出した前記第一行列及び前記第三行列のクラスタリング結果が、定義域外になった場合、定義域に入るようにクラスタ数を変動させて前記第一行列及び前記第三行列を変形するパラメータ変形部を含む
請求項１〜５のいずれか一項に記載のデータ分析装置。
【請求項７】
Ｎ個の第一対象物とＭ個の第二対象物のそれぞれの関連度を示すＮ行Ｍ列の基礎行列を、３つの第一行列、第二行列及び第三行列に分解して前記第一対象物及び前記第二対象物とをクラスタリングするデータ分析方法をコンピュータに実行させるためのプログラムであって、
前記データ分析方法は、
前記基礎行列の各要素に対して、前記関連度を示す値が入力された前記基礎行列を取得する取得ステップと、
前記第一対象物及び前記第二対象物のクラスタ数を示すＫを設定する設定ステップと、
前記基礎行列を少なくとも３つの前記基礎行列の部分行列に分割する分割ステップと、
前記部分行列のそれぞれに対して、特異値の大きい方からＫ個までを用いた特異値分解を行った結果を用いて、変換行列を生成する変換行列生成ステップと、
前記部分行列のそれぞれと、それらに対応する変換行列とで内積計算を行い、前記部分行列を圧縮する内積計算ステップと、
圧縮された前記部分行列を用いて、３階のテンソルを作成するテンソル生成ステップと、
前記テンソルを、ＣＰ分解(ＣＡＮＤＥＣＯＭＰ／ＰＡＲＡＦＡＣ分解)を用いて分解する分解ステップと、
前記分解ステップの分解結果を用いて、前記基礎行列を３つに分解した前記第一行列、前記第二行列及び前記第三行列を算出する算出ステップと、
前記第一行列、前記第二行列及び前記第三行列の少なくとも一つを出力することで、前記第一対象物及び前記第二対象物のクラスタリング結果を出力する出力ステップと、
を含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析装置及びプログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク化が進み、様々な機器を介して様々なデータが収集され蓄積されるようになった。様々なデータとはＷＥＢサイトのアクセス情報であったり、顧客の購買履歴であったり、番組の録画視聴履歴であったり、顧客の年齢・性別などの情報である。そのなかで、ＳＮＳ（Social Networking Service）の友達関係や購買履歴などを用いて、ユーザを、好みなどの属性ごとにクラスタリングし、商品をお勧めするなどのレコメンドサービスが行われている。現在知られているクラスタリングの方法として、テンソルのスペクトル分解を用いて、クラスタリング結果を求める方法が提案されている（例えば非特許文献１参照）。非特許文献１では、入力行列をテンソルに拡張して、特異値分解とその三次元拡張であるＣＰ分解を用いて、入力データとなる行列を３つの行列の積で近似できるような行列として求める。それらのクラスタリング結果を用いることで、推薦サービスなどが可能となる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】A Tensor Approach to Learning Mixed Membership Community Models, October 28, 2013
【発明の概要】
【発明が解決しようとする課題】
【０００４】
先行技術では、入力データをテンソルに拡張するため、計算メモリと計算時間が入力データサイズの３乗オーダーになり、計算コストが大きい。また、入力行列に対称性が仮定されており、クラスタ構造を表す行列にフルランクが仮定されている。これは実際にビジネスで取得されるデータに適用する上では厳しい制約である。
【０００５】
そこで本発明は、計算メモリを削減し、かつ、入力行列に制約を設けないデータ分析装置及びプログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明の一態様に係るデータ分析装置は、Ｎ個の第一対象物とＭ個の第二対象物のそれぞれの関連度を示すＮ行Ｍ列の基礎行列を、３つの第一行列、第二行列及び第三行列に分解して第一対象物及び第二対象物をクラスタリングするデータ分析装置であって、基礎行列の各要素に対して、関連度を示す値が入力された基礎行列を取得する取得部と、第一対象物及び第二対象物のクラスタ数を示すＫを設定する設定部と、基礎行列を少なくとも３つの基礎行列の部分行列に分割する分割部と、部分行列のそれぞれに対して、特異値の大きい方からＫ個までを用いた特異値分解を行った結果を用いて、変換行列を生成する変換行列生成部と、部分行列のそれぞれと、それらに対応する変換行列とで内積計算を行い、前記部分行列を圧縮する内積計算部と、圧縮された部分行列を用いて、３階のテンソルを作成するテンソル生成部と、テンソルを、ＣＰ分解(ＣＡＮＤＥＣＯＭＰ／ＰＡＲＡＦＡＣ分解)を用いて分解する分解部と、分解部の分解結果を用いて、基礎行列を３つに分解した第一行列、第二行列及び第三行列を算出する算出部と、第一行列、第二行列及び第三行列の少なくとも一つを出力することで、第一対象物及び第二対象物のクラスタリング結果を出力する出力部と、を含む。
【０００７】
なお、これらの包括的または具体的な態様は、システム、方法、集積回路、コンピュータプログラムまたはコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体で実現されてもよく、システム、方法、集積回路、コンピュータプログラム及び記録媒体の任意な組み合わせで実現されてもよい。
【発明の効果】
【０００８】
本発明のデータ分析装置及びプログラムは、計算に使用するメモリ量、計算時間を削減し、入力データに制約を設けないクラスタリングが可能となる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１に係るデータ分析方法を実行するためのデータ分析システムの概略構成を示すブロック図である。
【図２】実施の形態１に係る入力行列の一例を示す説明図である。
【図３】実施の形態１に係るデータ分析装置の概略構成を示すブロック図である。
【図４】実施の形態１に係るデータ分析装置の分割部の説明図である。
【図５】実施の形態１に係る入力行列の一例を示す説明図である。
【図６】図５の入力行列を基にしてデータ分析方法を行い、得られたパラメータの一例を示す説明図である。
【図７】実施の形態１に係るデータ分析方法の流れを示すフローチャートである。
【図８】実施の形態１に係るデータ分解装置の構成を示すブロック図の変形例である。
【図９】実施の形態２に係るデータ分析装置の概略構成を示すブロック図である。
【図１０】実施の形態２に係るデータ分析装置の入力変形部を示す説明図である。
【図１１】実施の形態２に係るデータ分析装置のパラメータ変形部におけるパラメータの変形例を示す説明図である。
【図１２】実施の形態２に係るデータ分析方法の流れを示すフローチャートである。
【発明を実施するための形態】
【００１０】
（本発明の基礎となった知見）
本発明者は、「背景技術」の欄において記載した方法に関し、以下の問題が生じることを見出した。
【００１１】
従来の方法は、入力として与えられる行列を３次元のテンソル形式に変形する必要がある。そのため、計算時のメモリの使用量と計算時間が入力データサイズの３乗オーダーが必要になる。しかしながら、大規模なデータを扱う際に、計算コストが大きく、データをメモリに載せて計算することができないという課題があった。また、入力行列が対称行列であり、さらにその入力情報に潜在的に含まれているクラスタ構造がフルランクであることを仮定している。しかしながら、購買履歴などの、あるユーザがある商品を買ったという情報は、行列形式では、ユーザ×商品になり、対称形にはならない。さらに、クラスタ構造がフルランクであるとは、ユーザ側のクラスタ数と商品側のクラスタ数が同じであることを仮定している。これは、現実的には考えにくく、実問題を扱う上では非常に厳しい制約となっている。
【００１２】
このような問題を解決するため、本発明の一態様にかかるデータ分析方法は、Ｎ個の第一対象物とＭ個の第二対象物のそれぞれの関連度を示すＮ行Ｍ列の基礎行列を、３つの第一行列、第二行列及び第三行列に分解して第一対象物及び第二対象物をクラスタリングするデータ分析方法であって、基礎行列の各要素に対して、関連度を示す値が入力された基礎行列を取得する取得ステップと、第一対象物及び第二対象物のクラスタ数を示すＫを設定する設定ステップと、基礎行列を少なくとも３つの基礎行列の部分行列に分割する分割ステップと、部分行列のそれぞれに対して、特異値の大きい方からＫ個までを用いた特異値分解を行った結果を用いて、変換行列を生成する変換行列生成ステップと、部分行列のそれぞれと、それらに対応する変換行列とで内積計算を行い、部分行列を圧縮する内積計算ステップと、圧縮された部分行列を用いて、３階のテンソルを作成するテンソル生成ステップと、テンソルを、ＣＰ分解を用いて分解する分解ステップと、分解ステップの分解結果を用いて、基礎行列を３つに分解した第一行列、第二行列及び第三行列を算出する算出ステップと、第一行列、第二行列及び第三行列の少なくとも一つを出力することで、第一対象物及び第二対象物のクラスタリング結果を出力する出力ステップと、を含むデータ分析方法。
【００１３】
これにより、大規模なテンソルを生成することなくデータサイズの２乗オーダーの計算メモリと計算時間が可能となる。したがって、大規模なデータでもメモリに載せての計算が可能となる。
【００１４】
例えば、さらに、取得ステップで取得された基礎行列が対称行列でない場合に、基礎行列の転置行列を用いて対称行列に変形する入力変形ステップを含んでもよい。
【００１５】
これにより、非対称の入力データにおいても、対称形に変形して計算が可能となる。
【００１６】
例えば、変換行列生成ステップで計算した特異値分解の結果を用いて、特異値全体の和に対して、特異値の上位からの和が所定値以上になるＫを設定してもよい。
【００１７】
これにより、クラスタ数であるＫを自動で設定することが可能となる。
【００１８】
例えば、変換行列生成ステップで計算した特異値分解の結果を用いて、特異値全体の２乗和に対して、特異値の上位からの２乗和が所定値以上になるＫを設定してもよい。
【００１９】
これにより、クラスタ数であるＫを自動で設定することが可能となる。
【００２０】
例えば、分解ステップは、特異値分解を用いて分解してもよい。
【００２１】
これにより、一般的に良く知られている特異値分解のみを利用しての計算が可能となる。
【００２２】
例えば、さらに、算出ステップで算出した第一行列及び第三行列のクラスタリング結果が、定義域外になった場合、定義域に入るようにクラスタ数を変動させて第一行列及び第三行列を変形するパラメータ変形ステップを含んでもよい。
【００２３】
これにより、クラスタ構造がフルランクでないものに対しても、正確なクラスタリングを可能とする。
【００２４】
また、本発明の一態様にかかるデータ分析装置は、Ｎ個の第一対象物とＭ個の第二対象物のそれぞれの関連度を示すＮ行Ｍ列の基礎行列を、３つの第一行列、第二行列及び第三行列に分解して第一対象物及び第二対象物をクラスタリングするデータ分析装置であって、基礎行列の各要素に対して、関連度を示す値が入力された基礎行列を取得する取得部と、第一対象物及び第二対象物のクラスタ数を示すＫを設定する設定部と、基礎行列を少なくとも３つの基礎行列の部分行列に分割する分割部と、部分行列のそれぞれに対して、特異値の大きい方からＫ個までを用いた特異値分解を行った結果を用いて、変換行列を生成する変換行列生成部と、部分行列のそれぞれと、それらに対応する変換行列とで内積計算を行い、部分行列を圧縮する内積計算部と、圧縮された部分行列を用いて、３階のテンソルを作成するテンソル生成部と、テンソルを、ＣＰ分解を用いて分解する分解部と、分解部の分解結果を用いて、基礎行列を３つに分解した第一行列、第二行列及び第三行列を算出する算出部と、第一行列、第二行列及び第三行列の少なくとも一つを出力することで、第一対象物及び第二対象物のクラスタリング結果を出力する出力部と、を備える。
【００２５】
これにより、大規模なテンソルを生成することなくデータサイズの２乗オーダーの計算メモリと計算時間が可能となる。したがって、大規模なデータでもメモリに載せての計算が可能となる。
【００２６】
また、本発明の一態様にかかるプログラムは、コンピュータに、上記のデータ分析方法を実行させるためのプログラムである。
【００２７】
これにより、大規模なテンソルを生成することなくデータサイズの２乗オーダーの計算メモリと計算時間が可能となる。したがって、大規模なデータでもメモリに載せての計算が可能となる。
【００２８】
なお、これらの包括的または具体的な態様は、システム、方法、集積回路、コンピュータプログラムまたはコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体で実現されてもよく、システム、方法、集積回路、コンピュータプログラム及び記録媒体の任意な組み合わせで実現されてもよい。
【００２９】
（実施の形態１）
以下、実施の形態について、図面を参照しながら具体的に説明する。なお、以下で説明する実施の形態は、いずれも包括的または具体的な例を示すものである。以下の実施の形態で示される数値、形状、材料、構成要素、構成要素の配置位置及び接続形態、ステップ、ステップの順序等は、一例であり、本発明を限定する主旨ではない。また、以下の実施の形態における構成要素のうち、最上位概念を示す独立請求項に記載されていない構成要素については、任意の構成要素として説明される。
【００３０】
[システムの全体構成]
図１は、実施の形態１に係るデータ分析方法を実行するためのデータ分析システムの概略構成を示すブロック図である。
【００３１】
データ分析システム１は、Ｎ個の対象物（第一対象物）のそれぞれに対するＭ個の対象物（第二対象物）の関連の有無を示すＮ行Ｍ列の基礎行列を入力として、３つの行列に分解して、ユーザをクラスタリングするデータ分析方法を実行する。対象物は、ユーザや商品などを表し、関連度を表す基礎行列とは、例えば、ＳＮＳの友達関係であると、ユーザ同士が友達であると「関連あり」、友達でないと「関連なし」となり、Ｎ個の対象物とＭ個の対象物は同じものを表し、実際の基礎行列はＮ行Ｎ列の対称行列となる。また、基礎行列が購買履歴であると、Ｎ個の対象物をユーザ、Ｍ個の対象物が商品であり、ユーザが商品を購入したことを「関連あり」とし、購入していないことを「関連なし」とする。
【００３２】
図２は、基礎行列の一例を示す説明図である。
【００３３】
図２に示す基礎行列では、Ｎ個の対象物がＮ個の対象物のそれぞれに対する関連の有無を示している。基礎行列の各要素に対しては、関連の有無を示す値が入力されている。具体的に、関連がある要素に対しては「１」が代入されており、関連のない要素には「０」が代入されている。例えば、図２にあげる基礎行列をＳＮＳの友達関係を表すデータとした場合、友達関係であるならば「１」が、友達関係でないならば「０」が入力される。なお、データの値と形式は、あくまでも一例であり、これに限定されるものではない。
【００３４】
そして、データ分析システム１は、この基礎行列を３つの行列に分解したものを算出することで、対象物をクラスタリングする。
【００３５】
具体的に、データ分析システム１は、図１に示すように、入力装置２００と、表示装置３００と、データ分析装置４００とを備えている。入力装置２００と、表示装置３００と、データ分析装置４００とはネットワーク５００を介して通信可能に接続されている。
【００３６】
ネットワーク５００とは、イーサネット（登録商標）等の有線ネットワーク、無線ＬＡＮ等の無線ネットワーク、公衆網、または、これらのネットワークが組み合わされたネットワーク等である。公衆網とは、電気通信事業者が、不特定多数の利用者の通信のために提供している通信回線のことであり、例えば、一般電話回線またはＩＳＤＮなどが挙げられる。
【００３７】
入力装置２００は、Ｎ行Ｍ列の基礎行列が入力される装置である。入力装置２００は、例えばキーボード、タッチパネル、ポインティングデバイスなどの入力部２１０を備えたパーソナルコンピューター、スマートフォン、フィーチャーフォン、タブレット端末などである。入力装置２００は、Ｎ行Ｍ列の基礎行列が入力されると、当該基礎行列を、ネットワーク５００を介してデータ分析装置４００に送信する。
【００３８】
表示装置３００は、クラスタリング結果を表す３つの行列のうち少なくとも一つの行列がデータ分析装置４００から入力されると、当該少なくとも一つの行列を表示する装置である。表示装置３００は、例えばディスプレイなどの表示部３１０を備えたパーソナルコンピューター、スマートフォン、フィーチャーフォン、タブレット端末などである。表示装置３００の表示部３１０に表示された少なくとも一つの行列を解析者が閲覧することで、クラスタリングされた結果を解析することができる。
【００３９】
なお、本実施の形態では、入力装置２００と表示装置３００とが独立した異なる端末である場合を例示しているが、入力装置２００と表示装置３００とが一台の端末であってもよい。また、入力装置２００と表示装置３００とデータ分析装置４００が一台の端末であってもよいし、ネットワークを介さずに接続されていてもよい。
【００４０】
［データ分析装置］
データ分析装置４００は、Ｎ行Ｍ列の基礎行列を入力として、クラスタリング結果である３つの行列を算出する処理装置である。実施例１では、入力される基礎行列は、Ｎ行Ｎ列の対称行列として説明を行う。データ分析装置４００は、例えば、サーバ、パーソナルコンピューター、スマートフォン、フィーチャーフォン、タブレット端末などである。
【００４１】
図３は、データ分析装置４００の概略構成を示すブロック図である。
【００４２】
図３に示すように、データ分析装置４００は、取得部４１０と、処理部４２０と、出力部４３０とを備えている。
【００４３】
取得部４１０は、入力装置２００からネットワーク５００を介して入力された基礎行列を取得し、処理部４２０に出力する。処理部４２０は、取得部４１０から入力された基礎行列を３つの行列に分解する処理部であり、ＣＰＵ、ＲＡＭ、ＲＯＭ等を備える。処理部４２０は、設定部４２１、分割部４２２、変換行列生成部４２３、内積計算部４２４、テンソル生成部４２５、分解部４２６、パラメータ計算部４２７と、を備える。
【００４４】
設定部４２１は、クラスタリングを行う際に用いられるクラスタ数を記憶している。例えば、対象物をＫ個のクラスタに分けるなどの設定値である。なお、設定項目は、設定部４２１に予め記憶されていなくとも、入力装置２００から入力された設定値を設定項目としてもよい。この場合、入力装置２００から取得部４１０を介して受信した設定項目を設定部４２１が記憶する。また、後に説明するように入力された基礎行列の情報を用いて自動的に決められてもよい。
【００４５】
分割部４２２は、入力された基礎行列を少なくとも３つの部分行列に分割する。具体例として、３つの部分行列を生成する場合を、図４を用いて説明する。基礎行列のデータサイズＮに対して、Ｘ，Ａ，Ｂ，Ｃ⊂Ｎとなる４つの集合を任意の方法で生成する。そして、入力された基礎行列Ｇ∈｛０，１｝N×Nに対して、ＧX,A∈｛０，１｝X×A、ＧX,B∈｛０，１｝X×B、ＧX,C∈｛０，１｝X×Cとなるような部分行列ＧX,A、ＧX,B、ＧX,Cを生成する。
【００４６】
変換行列生成部４２３は、分割部で生成した部分行列のそれぞれに対して特異値分解を行い、特異値の上位Ｋ番目までの分解結果を用いて、それぞれの部分行列に対応する変換行列を生成する。具体的には、変換行列生成部４２３は、式（１）〜式（３）を用いて、それぞれの部分行列に対応する変換行列を生成する。
【００４７】
【数１】
0006608721.tif 000002
【００４８】
ここで、Ｋは設定部４２１にて設定された値を用いてもよいし、特異値分解を行った結果を用いて、例えば、特異値の総和または２乗和に対する特異値の上位Ｋ番目までの和または２乗和がある一定の比率（所定値）を超えるようなＫを設定してもよい。ここで、ある一定の比率とは、７０％以上として設定し、この範囲を満たしていれば自由に決めてよい。
【００４９】
内積計算部４２４は、分割部で生成した部分行列と、変換行列生成部で生成した変換行列との内積計算により、それぞれの部分行列を圧縮する。具体的には、ｘ∈Ｘ、ｋ∈Ｋに対して部分行列ＧX,Aと変換行列ＷAとについては、式（４）で内積計算して圧縮する。
【００５０】
【数２】
0006608721.tif 000003
【００５１】
ただし、ＶA∈ＲX×Kで、ＶA(x,k)はｘ行ｋ列目の要素である。
【００５２】
同様に、部分行列ＧX,B、ＧX,Cと変換行列
【数３】
0006608721.tif 000004
とについては、式（５）、（６）で内積計算して圧縮する。
【００５３】
【数４】
0006608721.tif 000005
【００５４】
これにより、それぞれの部分行列を圧縮した行列が生成される。
【００５５】
テンソル生成部４２５は、内積計算部４２４で生成した３つの圧縮された部分行列を３階のテンソル形式に変形する。具体的には、式（７）を用いて、テンソル形式に変形する。
【００５６】
【数５】
0006608721.tif 000006
【００５７】
ただし、ＶA（x,k）はＶAのｘ行目の行ベクトルである。
【００５８】
分解部４２６は、テンソル生成部４２５で生成したテンソルを、ＣＰ分解を用いて分解する。なお、ＣＰ分解は、行列に定義された特異値分解を３次元のテンソルに適用できるように拡張したものであるため、特異値分解を用いて同様の分解を行ってもよい。分解結果は、式（８）に基づいて、求めるべきパラメータである３つの行列の一部を含む形で算出される。
【００５９】
【数６】
0006608721.tif 000007
【００６０】
パラメータ計算部４２７は、分解部で分解した結果を用いて、求めるべきパラメータである３つの行列ΠT、Ｐ、Πを計算する。具体的には、式（９）〜式（１３）を用いて計算する。
【００６１】
【数７】
0006608721.tif 000008
【００６２】
なお、Πを求める際に、確率的ブロックモデル（ＳＢＭ）を仮定するならば、式（１４）を用いてもよい。
【００６３】
【数８】
0006608721.tif 000009
【００６４】
また、混合メンバシップ・ブロックモデルを仮定するならば、式（１５）を用いてもよい。
【００６５】
【数９】
0006608721.tif 000010
【００６６】
出力部４３０は、第一行列、第二行列、第三行列の少なくとも一つを表示装置３００に出力する。出力部４３０は、基礎行列、第一行列、第二行列及び第三行列を一括して出力してもよいし、これらを組み合わせて出力してもよい。また、出力部４３０は、最終的な、第一行列、第二行列、第三行列の積を出力情報の一つとして出力してもよい。
【００６７】
図５は、本実施の形態に係る基礎行列の一例である。図６は、本実施の形態に係るパラメータである３つの行列の一例である。
【００６８】
例えば、図１０のように９行９列の基礎行列を与え、Ｋ＝３とすると、図１１に示すように、ΠTに相当する９行３列の第一行列と、Ｐに相当する３行３列の第二行列と、Πに相当する３行９列の第三行列として算出される。例えば、図５の入力行列をＳＮＳの友達関係のデータとすると、図６のパラメータの第一行列は、「ユーザＵ１は、クラスタＣ１に属する」という意味を示す。これにより、クラスタＣ１に属するユーザは、Ｕ１、Ｕ４、Ｕ６であることがわかる。同様に、クラスタＣ２、Ｃ３に属するユーザもパラメータから知ることができる。第三行列に関しては、基礎行列が対称であるため、第一行列と同じ意味を示す行列になっている。第二行列は、第一行列のクラスタと第三行列のクラスタとの関連強度を表す行列を意味する。この第二行列からは、同じクラスタ間の関連は強いが、違うクラスタとは関連が全くないことを意味している。
【００６９】
［データ分析方法］
次に、本実施の形態に係るデータ分析方法について説明する。
【００７０】
図７は、本実施の形態に係るデータ分析方法の流れを示すフローチャートである。
【００７１】
入力装置２００では、基礎行列の各要素に、関連の有無を示す値が入力される。また、入力装置２００では、クラスタ数を示すＫの値も入力される。これらの入力後においては、入力装置２００は、基礎行列及びＫをデータ分析装置４００に出力する。なお、設定項目がすでにデータ分析装置４００の設定部４２１に設定されていて、それが以降の処理に用いられる場合には、入力装置２００での設定項目の入力は不要である。
【００７２】
データ分析装置４００の取得部４１０は、入力装置２００からネットワークを介して入力された基礎行列及びＫを取得する（ステップＳ１０１）。
【００７３】
また、設定部４２１は、取得部４１０で取得したＫを設定項目として記憶する（ステップＳ１０２）。
【００７４】
次に、分割部４２２は、基礎行列から３つの部分行列を生成する（ステップＳ１０３）。
【００７５】
次に、変換行列生成部４２３は、ステップＳ１０３にて生成した３つの部分行列に対して、特異値分解を行い、その結果の特異値の上位Ｋ個を用いた分解結果を用いて、３つの部分行列に対応した３つの変換行列を生成する（ステップＳ１０４）。
【００７６】
次に、内積計算部４２４は、ステップＳ１０３で生成した部分行列と、ステップＳ１０４で生成した変換行列との内積計算を行うことで、部分行列を圧縮した行列を生成する（ステップＳ１０５）。
【００７７】
次に、テンソル生成部４２５は、ステップＳ１０５にて圧縮した部分行列を用いて、３階のテンソル形式のデータを生成する（ステップＳ１０６）。
【００７８】
次に、分解部４２６は、ステップＳ１０６にて生成したテンソルを、ＣＰ分解を用いて分解する（Ｓ１０７）。
【００７９】
次にパラメータ計算部４２７は、ステップＳ１０７の分解結果を用いて、パラメータを計算する（Ｓ１０８）。
【００８０】
最後に、出力部４３０は、ステップＳ１０８で算出したパラメータのうち少なくとも一つを表示装置３００に出力し、終了する（Ｓ１０９）。
【００８１】
図８は、実施の形態１の変形例を示すブロック図である。実施の形態１における分割部がない場合も本データ分析方法は可能である。一例を示すと、分割部４２２で用いた集合Ｘ，Ａ，Ｂ，Ｃ⊂ＮをＮ，Ｎ，Ｎ，Ｎ⊂Ｎと置き換える。つまりは、分割を行わずに、基礎行列をそのまま用いて計算する方法である。以降の計算処理もＸ，Ａ，Ｂ，Ｃ⊂ＮをＮ，Ｎ，Ｎ，Ｎ⊂Ｎと読み替えて同様の計算が可能である。これは、基礎行列の分割を行うと、基礎行列をすべて使わずに計算するため、情報の欠落が存在する。その情報の欠落を、基礎行列をすべて用いることで防ぐ効果がある。特に基礎行列のデータサイズが小さい時に有効になる方法である。
【００８２】
［効果等］
本実施の形態１において、先行技術のような大規模なテンソルを作成する必要がなくなり、データサイズＮの２乗オーダーのメモリ使用量と計算時間で処理を行うことができるようになった。そのため、大規模な入力データ（基礎行列）に対してもメモリに載せて計算することが可能になる。
【００８３】
（実施の形態２）
実施の形態１で例示したデータ分析方法は、入力される基礎行列が対称であるものに限定されている。また、パラメータである第二行列Ｐにフルランク性が仮定されている。そのため、購買履歴のような非対称かつ第二行列がフルランクでないような基礎行列を扱うことができない。このような基礎行列に対して、基礎行列を対称形に変形する方法と、フルランクでない第二行列を算出する方法について説明する。なお、実施の形態１と同じ機能については、同じ符合を振り当てて、説明を省略する。
【００８４】
図９は、データ分析装置４０１の概略構成を示すブロック図である。
【００８５】
処理部４４０は、実施の形態１の処理部４２０に加えて、入力変形部４２８及びパラメータ変形部４２９を備える。
【００８６】
入力変形部４２８は、入力された基礎行列が非対称の時、基礎行列の転置行列を用いて、対称形に変形する。図１０は、変形の一例を示す図である。式（１６）のように、基礎行列の転置行列と０で埋められた行列を用いて、入力された基礎行列を対称形に変形する。
【００８７】
【数１０】
0006608721.tif 000011
【００８８】
以降の計算を、この対称に変形した基礎行列を用いて計算を行う。なお、入力された基礎行列が対称行列の場合であっても、この変形を行って計算することは可能であるため、対称の時にも、変形を行ってもよい。
【００８９】
パラメータ変形部４２９は、パラメータ計算部４２７によって算出されたパラメータである第一行列と第三行列のいずれかが、定義域外の情報になっている際に、定義域に収まるように第一行列または第三行列に新たな行または列を追加または削減して、定義域外のノードを新規クラスタに割り当てる。ここでいう定義域とは、各対象物がいずれか１つのクラスタに所属するという条件である。２つ以上のクラスタに所属する、または、どのクラスタにも所属しないことは定義域外となる。さらに、変形した第一行列または第三行列を用いて、第二行列を再計算する。具体的には、式（１７）〜式（１９）により、第一行列及び第三行列を変形する。
【００９０】
【数１１】
0006608721.tif 000012
【００９１】
ここで、式（１８）におけるＵｎｉｑｕｅ関数は、重複する要素を削除する関数である。
【００９２】
図１１は、パラメータである第一行列の変形の方法を示す一例である。変形前の第一行列の対象物Ｍ７、Ｍ８、Ｍ９、Ｍ１０は定義域外になっていることがわかる。ただし、Ｍ７とＭ８は同じクラスタで、Ｍ９とＭ１０は同じクラスタであることがわかる。そのため、新しく２つのクラスタＣ４、Ｃ５を追加し、それぞれに割り当てることで、定義域に収まる第一行列を作成できる。第三行列に関しても同様に可能である。
【００９３】
図１２は、本実施の形態２に係るデータ分析方法の流れを示すフローチャートである。入力装置２００では、基礎行列の各要素に、関連の有無を示す値が入力される。また、入力装置２００では、クラスタ数を示すＫの値も入力される。これらの入力後においては、入力装置２００は、基礎行列及びＫをデータ分析装置４０１に出力する。なお、設定項目がすでにデータ分析装置４０１の設定部４２１に設定されていて、それが以降の処理に用いられる場合には、入力装置２００での設定項目の入力は不要である。
【００９４】
データ分析装置４０１の取得部４１０は、入力装置２００からネットワークを介して入力された基礎行列及びＫを取得する（ステップＳ１０１）。
【００９５】
また、設定部４２１は、取得部４１０で取得したＫを設定項目として記憶する（ステップＳ１０２）。
【００９６】
次に、入力変形部４２８は、基礎行列の転置行列を用いて、基礎行列を対称形に変形し、この変形した基礎行列を以降、基礎行列として利用する（ステップＳ１１０）。
【００９７】
次に、分割部４２２は、基礎行列から３つの部分行列を生成する（ステップＳ１０３）。
【００９８】
次に、変換行列生成部４２３は、ステップＳ１０３にて生成した３つの部分行列に対して、特異値分解を行い、その結果の特異値の上位Ｋ個を用いた分解結果を用いて、３つの部分行列に対応した３つの変換行列を生成する（ステップＳ１０４）。
【００９９】
次に、内積計算部４２４は、ステップＳ１０３で生成した部分行列と、ステップＳ１０４で生成した変換行列との内積計算を行うことで、部分行列を圧縮した行列を生成する（ステップＳ１０５）。
【０１００】
次に、テンソル生成部４２５は、ステップＳ１０５にて圧縮した部分行列を用いて、３階のテンソル形式のデータを生成する（ステップＳ１０６）。
【０１０１】
次に、分解部４２６は、ステップＳ１０６にて生成したテンソルを、ＣＰ分解を用いて分解する（Ｓ１０７）。
【０１０２】
次にパラメータ計算部４２７は、ステップＳ１０７の分解結果を用いて、パラメータを計算する（Ｓ１０８）。
【０１０３】
次に、パラメータ変形部４２９は、第一行列または、第三行列が定義域外になっている時、定義域に収まる形に変形し、その変形した第一行列と第三行列を用いて、第二行列を再計算する（Ｓ１１１）。
【０１０４】
最後に、出力部４３０は、ステップＳ１０８で算出したパラメータのうち少なくとも一つを表示装置３００に出力し、終了する（Ｓ１０９）。
【０１０５】
［効果等］
本実施の形態２により、入力される基礎行列が非対称であり、第二行列がフルランクでない基礎行列に対しても、正確に計算が可能になる。つまりは、購買履歴などの非対称構造の情報を用いてクラスタリングが可能になる。
【０１０６】
なお、上記各実施の形態において、各構成要素は、専用のハードウェアで構成されるか、各構成要素に適したソフトウェアプログラムを実行することによって実現されてもよい。各構成要素は、ＣＰＵまたはプロセッサなどのプログラム実行部が、ハードディスクまたは半導体メモリなどの記録媒体に記録されたソフトウェアプログラムを読み出して実行することによって実現されてもよい。
【０１０７】
また、上記各実施の形態において、特定の処理部が実行する処理を別の処理部が実行してもよい。また、複数の処理の順序が変更されてもよいし、複数の処理が並行して実行されてもよい。
【０１０８】
以上、一つまたは複数の態様に係るデータ分析方法について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を本実施の形態に施したものや、異なる実施の形態における構成要素を組み合わせて構築される形態も、一つまたは複数の態様の範囲内に含まれてもよい。
【産業上の利用可能性】
【０１０９】
本発明は、クラスタリングに用いられるデータ分析方法、データ分析装置及びプログラムとして有用である。すなわち、本発明は、推薦システムや文章分類などクラスタリングを必要とする様々な分野で応用可能である。
【符号の説明】
【０１１０】
１              データ分析システム
２００              入力装置
３００              表示装置
４００、４０１      データ分析装置
４１０              取得部
４２０、４４０      処理部
４２１              設定部
４２２              分割部
４２３              変換行列生成部
４２４              内積計算部
４２５              テンソル生成部
４２６              分解部
４２７              パラメータ計算部
４２８              入力変形部
４２９              パラメータ変形部
５００              ネットワーク
【図１】
0006608721.tif 000013
【図２】
0006608721.tif 000014
【図３】
0006608721.tif 000015
【図４】
0006608721.tif 000016
【図５】
0006608721.tif 000017
【図６】
0006608721.tif 000018
【図７】
0006608721.tif 000019
【図８】
0006608721.tif 000020
【図９】
0006608721.tif 000021
【図１０】
0006608721.tif 000022
【図１１】
0006608721.tif 000023
【図１２】
0006608721.tif 000024