データ分析装置、及びデータ分析プログラム
【課題】ソフトウェア的にクラスタリングを実装した場合にも処理速度を低下させない。
【解決手段】データ分析装置１０は、大容量低速記憶部２０と、高速にアクセスが可能な小容量高速記憶部２２とを備え、複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、２分木構造において親，子の順序で大容量低速記憶部２０の連続するアドレスに格納し、大容量低速記憶部２０から、所定数の連続するアドレスに格納されたデータ要素群の部分要素群を抽出して、小容量高速記憶部２２に格納し、小容量高速記憶部２２に格納された部分要素群に含まれる各データ要素のデータ値をヒープソートにより並び替え、並び替えた部分要素群に基づいて、大容量低速記憶部２０において当該部分要素群に対応するアドレスに格納されたデータ値を更新し、更新された大容量低速記憶部２０に格納されたデータ要素群に基づきクラスタリングを行う。
【解決手段】データ分析装置１０は、大容量低速記憶部２０と、高速にアクセスが可能な小容量高速記憶部２２とを備え、複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、２分木構造において親，子の順序で大容量低速記憶部２０の連続するアドレスに格納し、大容量低速記憶部２０から、所定数の連続するアドレスに格納されたデータ要素群の部分要素群を抽出して、小容量高速記憶部２２に格納し、小容量高速記憶部２２に格納された部分要素群に含まれる各データ要素のデータ値をヒープソートにより並び替え、並び替えた部分要素群に基づいて、大容量低速記憶部２０において当該部分要素群に対応するアドレスに格納されたデータ値を更新し、更新された大容量低速記憶部２０に格納されたデータ要素群に基づきクラスタリングを行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析装置、及びデータ分析プログラムに関する。
【背景技術】
【０００２】
大量のデータを分析するひとつの手法にクラスタ分析がある。クラスタ分析には大別して、非階層的クラスタリングと階層的クラスタリングとがある。従来では、大量データのクラスタ分析には、アルゴリズムが比較的簡単で高速処理が可能なＫ−ｍｅａｎｓ法等の非階層的クラスタリングの手法が用いられることが多かった。
【０００３】
しかしながら、非階層的クラスタリングの手法には、最終的な分類結果が初期分類の影響を受けやすく、また局所最適になりやすいという分類性能の問題がある。これに対して、階層的クラスタリング手法では、高次元ベクトルデータを分類する上で、等方等分散のクラスタを仮定するＫ−ｍｅａｎｓ法に比べて分類性能が良いという利点があるが、処理に時間がかかるため分類対象のデータ数が膨大となると適用できないという問題があった。
【０００４】
この問題に対して、例えば下記の特許文献１や特許文献２のように、２分探索を高速に処理する専用のハードウェアを導入することで、ヒープ構造に関する処理高速化を実現することも考えられるが、専用のハードウェアの導入にはコストがかかってしまう。そこで、下記の非特許文献１では、クラスタリング対象データのデータ構造にヒープ構造を用いることで、階層的クラスタリング処理をソフトウェア的にも高速化できる手法を提案している。
【特許文献１】特開平１０−３３６２１６号公報
【特許文献２】特開２００３−２２３３１５号公報
【非特許文献１】Ｋｕｒｉｔａ，Ｔ．， Ａｎ ｅｆｆｉｃｉｅｎｔ ａｇｇｌｏｍｅｒａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ａ ｈｅａｐ， Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， Ｖｏｌ．２４， ナンバー３， ｐｐ．２０５−２０９， １９９１．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術で用いられているデータ構造ではメモリアクセスの局所性が低いため、ヒープ構造に使用可能なデータ量がメインメモリサイズより大きくなると、２分木構造中の要素位置を順次データ交換する際にメインメモリとＨＤＤ中のスワップ用記憶領域との間のデータ転送が高頻度で発生し、処理速度が極端に遅くなってしまっていた。
【０００６】
本発明の目的の１つは、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しないデータ分析装置、及びデータ分析プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１に記載のデータ分析装置の発明は、第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、複数の要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親である要素、当該親の子である要素の順序で前記第１の記憶手段の連続するアドレスに格納する第１格納手段と、前記第１の記憶手段から、所定数の連続するアドレスに格納された前記データ要素群の部分要素群を抽出して、前記第２の記憶手段に格納する第２格納手段と、前記第２の記憶手段に格納された前記部分要素群に含まれる各要素のデータ値をヒープソートにより並び替える手段と、前記データ値が並び替えられた部分要素群に基づいて、前記第１の記憶手段において当該部分要素群に対応するアドレスに格納されたデータ値を更新する手段と、を含み、前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ことを特徴とする。
【０００８】
請求項２に記載の発明は、請求項１に記載のデータ分析装置において、前記第１格納手段は、前記２分木構造の上位層又は下位層のいずれかから順に、前記データ要素群を前記第１の記憶手段の連続するアドレスに格納する、ことを特徴とする。
【０００９】
請求項３に記載の発明は、請求項１又は２に記載のデータ分析装置において、前記第１格納手段は、前記データ要素群を、前記所定数の要素からなる２分木構造のデータブロックに分割するとともに、当該分割された各データブロックについてそれぞれ親である要素、当該親の子である要素の順序で前記第１の記憶手段の連続するアドレスに格納し、前記第２格納手段は、前記データブロック毎にデータを抽出して前記第２の記憶手段に格納する、ことを特徴とする。
【００１０】
請求項４に記載の発明は、請求項１乃至３のいずれかに記載のデータ分析装置において、前記第１の記憶手段から前記所定数の連続するアドレスに格納された部分要素群を新たに抽出して、当該新たに抽出した部分要素群のデータ値を更新する処理を所定の終了条件が満たされるまで繰り返して実行した後に、前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ことを特徴とする。
【００１１】
請求項５に記載の発明は、請求項４に記載のデータ分析装置において、前記データ要素群は、クラスタリングの対象とする複数のスカラ又はベクトルデータ間のそれぞれの距離データをデータ要素とし、前記所定の終了条件が満たされた後に前記第１の記憶手段に格納されたデータ要素群に基づいてクラスタリングを行う、ことを特徴とする。
【００１２】
請求項６に記載の発明は、請求項５に記載のデータ分析装置において、前記所定の条件が満たされた後に、前記２分木構造の根のデータ要素を距離データとした２つのクラスタリング対象データを同一のクラスタとして分類する手段と、前記同一のクラスタに分類されたクラスタリング対象データのいずれか一方に関する全ての距離データを前記データ要素群のデータ要素の中から削除する手段と、をさらに含み、前記第１格納手段は、前記データ要素が削除されたデータ要素群を２分木構造に再び配列するとともに、当該配列したデータ要素群を前記第１の記憶手段に格納する、ことを特徴とする。
【００１３】
請求項７に記載の発明は、請求項１乃至６のいずれかに記載のデータ分析装置において、前記第２格納手段は、前記第１の記憶手段から前記データ要素群の異なる部分要素群を複数抽出して前記第２の記憶手段に格納し、前記第２の記憶手段に格納された各部分要素群についてのヒープソートを並列処理により行う、ことを特徴とする。
【００１４】
請求項８に記載のデータ分析プログラムの発明は、第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、を備えるコンピュータに、複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親である要素、当該親の子であるデータ要素の順序で前記第１の記憶手段に格納する第１格納ステップと、前記第１の記憶手段に格納されたデータ要素群から、所定数の連続するアドレスのデータブロックを抽出して、前記第２の記憶手段に格納する第２格納ステップと、前記第２の記憶手段に格納された前記データブロックについて、当該データブロックに含まれる各データ要素のデータ値に基づいてヒープソートを行うステップと、前記ヒープソートにより並び替えられた前記データブロックに基づいて、前記第１の記憶手段に格納された当該データブロックのデータ値を更新するステップと、を実行させ、前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ように機能させることを特徴とする。
【発明の効果】
【００１５】
請求項１に記載の発明によれば、ヒープソートの処理単位毎に２分木構造を維持したまま連続するアドレスに格納するためメモリアクセスの局所性が高まり、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しない。
【００１６】
請求項２に記載の発明によれば、ヒープソートの処理順にデータを格納しておくことで、大規模容量ディスクとメモリ間のスワッピングの発生を抑制することができる。
【００１７】
請求項３に記載の発明によれば、ヒープソートの処理単位のデータブロック毎にまとめて大容量ディスクに格納し、そのデータブロック単位でメモリに転送して処理を行うことで、大規模容量ディスクとメモリ間のスワッピングの発生を抑制することができる。
【００１８】
請求項４に記載の発明によれば、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットのヒープソートの処理速度を極端に低下させずに処理できる。
【００１９】
請求項５に記載の発明によれば、データ量がメインメモリサイズより大きい大規模なデータセットに対してクラスタリング処理を行う際に、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、処理速度が極端に低下しないようにできる。
【００２０】
請求項６に記載の発明によれば、クラスタリングの結果、データ構造を再構築して処理を継続する場合にも、処理速度が極端に低下しないようにできる。
【００２１】
請求項７に記載の発明によれば、同一の層に位置するデータブロックについては並列処理が容易であり、ヒープソートの処理を高速化できる。
【００２２】
請求項８に記載の発明によれば、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しないようにコンピュータを機能させることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための好適な実施の形態（以下、実施形態という）を、図面に従って説明する。
【００２４】
図１には、本実施形態に係るデータ分析装置の機能ブロック図を示す。図１に示されるように、データ分析装置１０は、機能的な構成として、大容量低速記憶部２０、小容量高速記憶部２２、データ管理部２４、２分木データ配列部２６、ヒープソート処理部２８、及びクラスタリング処理部３０を備える。なお、データ管理部２４、２分木データ配列部２６、ヒープソート処理部２８、及びクラスタリング処理部３０の各機能は、コンピュータシステムたるデータ分析装置１０がコンピュータプログラムに従って動作することにより実現されるものとしてよい。また、コンピュータプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、フラッシュメモリ等のコンピュータが読み取り可能なあらゆる形態の情報記録媒体に格納され、データ分析装置１０に接続された図示しない媒体読み取り装置によりデータ分析装置１０に読み込まれることとしてもよい。また、コンピュータプログラムは、ネットワークを介してデータ分析装置１０にダウンロードされることとしても構わない。
【００２５】
大容量低速記憶部２０は、ハードディスク装置やフラッシュメモリ等により構成される大容量の記憶装置である。大容量低速記憶部２０は、データやプログラムが格納される他、メモリのスワップ領域としても用いられる。
【００２６】
小容量高速記憶部２２は、ＲＡＭ（ランダムアクセスメモリ）やキャッシュ（１次，２次キャッシュ）等により構成される高速にアクセスが可能な記憶装置である。小容量高速記憶部２２は、大容量低速記憶部２０に対して記憶容量が小さいが高速に読み・書き等のアクセスをすることができる。
【００２７】
データ管理部２４は、大容量低速記憶部２０と小容量高速記憶部２２との間でデータ転送を行う入出力コントローラである。データ管理部２４は、ＣＰＵ（中央処理装置）から指示されたメモリアドレスに基づいて、メモリに格納されたデータの読み出し又は書き込みを行う。
【００２８】
２分木データ配列部２６は、複数のデータ要素からなるヒープソートの処理対象データを２分木構造に配列するとともに、処理対象データを所定の要素数からなる２分木構造のデータブロックに分割して、大容量低速記憶部２０に格納する際の順序を決定する。ここで、２分木データ配列部２６は、データブロックの番号に対応づけてそのデータブロックが大容量低速記憶部２０のどのアドレスに格納されたかを記憶しておくこととしてもよい。
【００２９】
図２には、２分木データ配列部２６により２分木構造に配列された処理対象データの一例を示す。図２に示されるように、データ要素「１」を親として、その下にデータ要素「２」及び「３」がデータ要素「１」の子として配列されている。２分木データ配列部２６は、このような２分木構造の配列規則に従って処理対象データを順に配列していく。
【００３０】
次に、２分木データ配列部２６は、２分木構造に配列された処理対象データを、所定数の要素からなる２分木構造のデータブロックに分割する。例えば、処理対象データを、親，子，親，子の４層の２分木構造のデータブロックに分割する場合には、図２に示されているように１５個のデータ要素からなるデータブロック毎に処理対象データを分割する。
【００３１】
図３に示されるように、分割された各データブロックは、それぞれ２分木構造における親，子の順序で大容量低速記憶部２０に順次格納される。具体的には、１つのデータブロックが１５個のデータからなるとすると以下のように格納される。まず、データブロック０には、データ要素「１」から「１５」までのデータが格納される。ここで、データブロック０では、２分木構造の根に位置するデータ要素「１」を親として、その子のデータ要素「２」，「３」、そして３層目のデータ要素の１つ（例えばデータ要素「４」）を親としてその子のデータ要素「８」，「９」、同様にデータ要素「５」，「１０」，「１１」という規則で配列して大容量低速記憶部２０の連続するメモリアドレスに格納する。他のデータブロックに関しても同様の規則に従って大容量低速記憶部２０に格納する。
【００３２】
ヒープソート処理部２８は、処理対象データのヒープソートを実行する。ヒープソート処理部２８は、ハードディスク等の記憶装置に格納されたヒープソートプログラムに基づいて、大容量低速記憶部２０から抽出した処理対象データを小容量高速記憶部２２に格納した上で、その格納した処理対象データに対してヒープソートを行う。ここで、処理対象データのデータサイズが膨大となると、小容量高速記憶部２２には格納しきれない状態となるため、本実施形態では、大容量低速記憶部２０から処理対象データの一部のデータブロックを抽出して、小容量高速記憶部２２に格納してヒープソートを行い、そのヒープソートの結果を大容量低速記憶部２０に戻した上で、新たなデータブロックを小容量高速記憶部２２に転送してヒープソートを行うという処理を順次繰り返す。上記の処理は、全てのデータブロックに対してヒープソート処理が終了するまで繰り返される。
【００３３】
なお、各データブロックについて行われる根を最小値とするヒープソートの処理の概要は以下の通りである。データブロックの要素数が１５の時に、各データブロックの要素を２分木構造の順序で配列した配列Ｎ（要素数ｎ＝１５）として、ｉを整数としてｉ＝ｎ／２、ａ＝ｉとした場合に、配列ＮのデータＮ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較して、Ｎ［ａ］が最小の時にはデータの入れ替えを行わない。そして、ｉをデクリメントした上で、ａ＝ｉとして、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。ここで、Ｎ［２ａ］が最小の時には、Ｎ［ａ］とＮ［２ａ］のデータを入れ替え、ａに２ａを代入して、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。ここで、Ｎ［２ａ＋１］が最小の時には、Ｎ［ａ］とＮ［２ａ＋１］のデータを入れ替え、ａに２ａ＋１を代入して、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。上記の処理をｉのデクリメントを行いながら繰り返し、ａが１になるまで処理を行う。
【００３４】
ヒープソート処理部２８は、処理対象データ全体に対するヒープソートの処理を例えば以下の手順で行う。ヒープソート処理部２８は、まず大容量低速記憶部２０に格納されたデータブロックの中から、最下層のデータブロックの少なくとも一部を抽出して、小容量高速記憶部２２に格納する。そして、ヒープソート処理部２８は、小容量高速記憶部２２に格納されたデータブロックに対して上述したアルゴリズムに従ってヒープソートを実行する。なお、小容量高速記憶部２２には複数のデータブロックを転送して、各データブロックについてのヒープソートを並列処理にしてもよい。並列に処理するデータブロック数は、小容量高速記憶部２２のデータ容量と、データブロックのデータサイズに応じて決定することとしてよい。
【００３５】
クラスタリング処理部３０は、クラスタリング処理の対象とするデータ（以下、クラスタリング対象データとする）を複数のクラスタに分類する。クラスタ構造は、階層構造にすることとしてもよい。例えば、複数の文書からなる文書群を複数のクラスタに分類する場合には、各文書から抽出された特徴ベクトルをクラスタリング対象データとすることができる。
【００３６】
本実施形態では、クラスタリング対象データを特徴ベクトルとし、２つの特徴ベクトル間の距離をそれぞれ算出して、それらの距離データをヒープソートの処理対象データとして最小値が２分木構造の根にくるようにヒープソートを行う。そして、ヒープソートの結果得られた距離が小さい特徴ベクトル同士を同一のクラスタに分類することとする。すなわち、クラスタリング対象データたる要素数ｎの特徴ベクトルＤ１〜Ｄｎに対して、それぞれのベクトルデータの距離、ｄ１，２，ｄ１，３，…，ｄ１，ｎ，…，ｄｎ−１，ｎを算出し、それらのデータ群をヒープソート対象データとする。なお、ｄｉ，ｊとは特徴ベクトルＤｉとＤｊとの距離であるとする。また、ヒープソート対象データ数は、クラスタリング対象データがｎ個あるとすると、ｎ（ｎ−１）／２となる。
【００３７】
クラスタリング処理部３０では、ヒープソート対象データを２分木データ配列部２６により２分木構造に配列するとともに、配列したヒープソート対象データを所定数（例えば１５個）のデータからなるデータブロックに分割して、データブロック毎に大容量低速記憶部２０に格納する。格納されたヒープソート対象データは、データブロック毎に小容量高速記憶部２２に読み込まれて順次ヒープソートが実行される。
【００３８】
なお、ヒープソートの同じ層に位置するデータブロックについてヒープソートが終了し、その上位に位置するデータブロックについてヒープソートを開始する際には、上位のデータブロック並びに下位のデータブロックのうち少なくとも上位のデータブロックに接続しているノードについて小容量高速記憶部２２に読み込み、上位のデータブロックのヒープソートを行う。そして、ヒープソートは、下位の階層から上位の階層へと順次処理を進めて、最上位のデータブロックについての処理が終了するまで実行される。
【００３９】
ヒープソート処理が終了すると、クラスタリング処理部３０は、ヒープソートの結果、例えば根に格納されたデータ要素がｄｋ，ｌである場合には、特徴ベクトルＤｋとＤｌとが同じクラスタに属すると判断する。そして、クラスタリング処理部３０は、ヒープソート対象データについて、同じクラスタに属する特徴ベクトルＤｋとＤｌとを同じ要素とみなして、どちらか一方の要素と他の特徴ベクトルとの距離データをヒープソート対象データの中から削除する。ここで、２分木データ配列部２６は、要素が削除されたヒープソート対象データに基づいて２分木構造の配列を再構築し、大容量低速記憶部２０に格納する。
【００４０】
クラスタリング処理部３０は、所定の終了条件を満たすまで、クラスタリング対象データに対するクラスタリング処理を実行する。所定の終了条件とは、例えばクラスタリング対象データが所定数まで絞り込まれたこととしてもよいし、その他にも、クラスタ数が所定数に達したこと、又は距離が所定の範囲内にある特徴ベクトルがなくなるまで等の様々な条件を採ることとしてよい。
【００４１】
次に、図４を参照しつつ、本実施形態に係るデータ分析装置１０によるクラスタリング処理の一連の流れを説明する。
【００４２】
まず、データ分析装置１０は、複数の特徴ベクトルを要素としたクラスタリング対象データを読み込む（Ｓ１０１）。データ分析装置１０は、読み込んだクラスタリング対象データのそれぞれの特徴ベクトル間の距離データ（以下、ヒープソート対象データとする）を算出し（Ｓ１０２）、ヒープソート対象データを２分木構造に配列する（Ｓ１０３）。データ分析装置１０は、２分木構造に配列したヒープソート対象データを所定要素数からなるデータブロックに分割して、ＨＤＤ等の大容量低速記憶部２０に一旦格納する（Ｓ１０４）。
【００４３】
次に、データ分析装置１０は、大容量低速記憶部２０に一旦格納されたヒープソート対象データの中から、データブロックを単位として抽出し、ＲＡＭ等の小容量高速記憶部２２に格納するとともに、格納したデータブロックの根のノードに最小値が配置されるようにヒープソートを行う（Ｓ１０５）。データ分析装置１０は、上記のヒープソートを下位の層のデータブロックから順次実行し、全てのデータブロック、すなわち最上位の層のデータブロックについて処理が終了したか否かを判断し（Ｓ１０６）、終了していない場合には（Ｓ１０６：Ｎ）、未処理のデータブロックを読み込んでヒープソートを実行する。一方で、全てのデータブロックについて処理が終了した場合には（Ｓ１０６：Ｙ）、ヒープソートの結果、距離が近いクラスタリング対象データ同士を同一のクラスタに分類するとともに、同一のクラスタに分類された一方のデータに関する距離データをヒープソート対象データの中から削除する（Ｓ１０７）。データ分析装置１０は、クラスタリングの結果が所定の終了条件、例えばクラスタ数が所定数まで達したか否か、又は最小の距離が所定条件内にあること等を満たしているか否かを判断し（Ｓ１０８）、その終了条件を満たしていない場合には（Ｓ１０８：Ｎ）、ヒープソート対象データを再配列するとともに以下の処理を繰り返し、終了条件を満たしている場合には（Ｓ１０８：Ｙ）、クラスタリング処理を終了する。また、データ分析装置１０は、上記処理により得られたクラスタリング結果をディスプレイに表示することとしてもよい。
【００４４】
以上説明した本実施形態に係るデータ分析装置１０によれば、データ分析装置１０がコンピュータプログラムに基づいてクラスタリング処理を行う場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して処理速度を極端に低下させないようにできる。
【００４５】
なお、本発明は上記の実施形態に限定されるものではなく、例えばデータブロック毎にそのデータブロックが現在処理対象になっているのか否かを示すフラグを対応づけて記憶することとしてもよい。フラグはそのデータブロックが処理されていない状態（クリアー状態）であれば「０」を、処理されている状態（ビジー状態）であれば「１」を格納しておくこととしてよい。そして、データ分析装置１０は、処理対象とするデータブロックのフラグがクリア状態「０」であるものを発見するまで読み出しを継続して並列処理を行うこととしてよい。また、処理対象データに応じて構築された２分木構造に応じて、最適な処理順序を予め決定した上でデータの並列処理を行うこととしてもよい。
【図面の簡単な説明】
【００４６】
【図１】本実施形態に係るデータ分析装置の機能ブロック図である。
【図２】２分木構造に配列された処理対象データの一例を示す図である。
【図３】処理対象データをメモリアドレスに格納する順序を示す図である。
【図４】クラスタリング処理の一連の流れを説明するフロー図である。
【符号の説明】
【００４７】
１０ データ分析装置、２０ 大容量低速記憶部、２２ 小容量高速記憶部、２４ データ管理部、２６ ２分木データ配列部、２８ ヒープソート処理部、３０ クラスタリング処理部。
【技術分野】
【０００１】
本発明は、データ分析装置、及びデータ分析プログラムに関する。
【背景技術】
【０００２】
大量のデータを分析するひとつの手法にクラスタ分析がある。クラスタ分析には大別して、非階層的クラスタリングと階層的クラスタリングとがある。従来では、大量データのクラスタ分析には、アルゴリズムが比較的簡単で高速処理が可能なＫ−ｍｅａｎｓ法等の非階層的クラスタリングの手法が用いられることが多かった。
【０００３】
しかしながら、非階層的クラスタリングの手法には、最終的な分類結果が初期分類の影響を受けやすく、また局所最適になりやすいという分類性能の問題がある。これに対して、階層的クラスタリング手法では、高次元ベクトルデータを分類する上で、等方等分散のクラスタを仮定するＫ−ｍｅａｎｓ法に比べて分類性能が良いという利点があるが、処理に時間がかかるため分類対象のデータ数が膨大となると適用できないという問題があった。
【０００４】
この問題に対して、例えば下記の特許文献１や特許文献２のように、２分探索を高速に処理する専用のハードウェアを導入することで、ヒープ構造に関する処理高速化を実現することも考えられるが、専用のハードウェアの導入にはコストがかかってしまう。そこで、下記の非特許文献１では、クラスタリング対象データのデータ構造にヒープ構造を用いることで、階層的クラスタリング処理をソフトウェア的にも高速化できる手法を提案している。
【特許文献１】特開平１０−３３６２１６号公報
【特許文献２】特開２００３−２２３３１５号公報
【非特許文献１】Ｋｕｒｉｔａ，Ｔ．， Ａｎ ｅｆｆｉｃｉｅｎｔ ａｇｇｌｏｍｅｒａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ａ ｈｅａｐ， Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， Ｖｏｌ．２４， ナンバー３， ｐｐ．２０５−２０９， １９９１．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術で用いられているデータ構造ではメモリアクセスの局所性が低いため、ヒープ構造に使用可能なデータ量がメインメモリサイズより大きくなると、２分木構造中の要素位置を順次データ交換する際にメインメモリとＨＤＤ中のスワップ用記憶領域との間のデータ転送が高頻度で発生し、処理速度が極端に遅くなってしまっていた。
【０００６】
本発明の目的の１つは、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しないデータ分析装置、及びデータ分析プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１に記載のデータ分析装置の発明は、第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、複数の要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親である要素、当該親の子である要素の順序で前記第１の記憶手段の連続するアドレスに格納する第１格納手段と、前記第１の記憶手段から、所定数の連続するアドレスに格納された前記データ要素群の部分要素群を抽出して、前記第２の記憶手段に格納する第２格納手段と、前記第２の記憶手段に格納された前記部分要素群に含まれる各要素のデータ値をヒープソートにより並び替える手段と、前記データ値が並び替えられた部分要素群に基づいて、前記第１の記憶手段において当該部分要素群に対応するアドレスに格納されたデータ値を更新する手段と、を含み、前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ことを特徴とする。
【０００８】
請求項２に記載の発明は、請求項１に記載のデータ分析装置において、前記第１格納手段は、前記２分木構造の上位層又は下位層のいずれかから順に、前記データ要素群を前記第１の記憶手段の連続するアドレスに格納する、ことを特徴とする。
【０００９】
請求項３に記載の発明は、請求項１又は２に記載のデータ分析装置において、前記第１格納手段は、前記データ要素群を、前記所定数の要素からなる２分木構造のデータブロックに分割するとともに、当該分割された各データブロックについてそれぞれ親である要素、当該親の子である要素の順序で前記第１の記憶手段の連続するアドレスに格納し、前記第２格納手段は、前記データブロック毎にデータを抽出して前記第２の記憶手段に格納する、ことを特徴とする。
【００１０】
請求項４に記載の発明は、請求項１乃至３のいずれかに記載のデータ分析装置において、前記第１の記憶手段から前記所定数の連続するアドレスに格納された部分要素群を新たに抽出して、当該新たに抽出した部分要素群のデータ値を更新する処理を所定の終了条件が満たされるまで繰り返して実行した後に、前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ことを特徴とする。
【００１１】
請求項５に記載の発明は、請求項４に記載のデータ分析装置において、前記データ要素群は、クラスタリングの対象とする複数のスカラ又はベクトルデータ間のそれぞれの距離データをデータ要素とし、前記所定の終了条件が満たされた後に前記第１の記憶手段に格納されたデータ要素群に基づいてクラスタリングを行う、ことを特徴とする。
【００１２】
請求項６に記載の発明は、請求項５に記載のデータ分析装置において、前記所定の条件が満たされた後に、前記２分木構造の根のデータ要素を距離データとした２つのクラスタリング対象データを同一のクラスタとして分類する手段と、前記同一のクラスタに分類されたクラスタリング対象データのいずれか一方に関する全ての距離データを前記データ要素群のデータ要素の中から削除する手段と、をさらに含み、前記第１格納手段は、前記データ要素が削除されたデータ要素群を２分木構造に再び配列するとともに、当該配列したデータ要素群を前記第１の記憶手段に格納する、ことを特徴とする。
【００１３】
請求項７に記載の発明は、請求項１乃至６のいずれかに記載のデータ分析装置において、前記第２格納手段は、前記第１の記憶手段から前記データ要素群の異なる部分要素群を複数抽出して前記第２の記憶手段に格納し、前記第２の記憶手段に格納された各部分要素群についてのヒープソートを並列処理により行う、ことを特徴とする。
【００１４】
請求項８に記載のデータ分析プログラムの発明は、第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、を備えるコンピュータに、複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親である要素、当該親の子であるデータ要素の順序で前記第１の記憶手段に格納する第１格納ステップと、前記第１の記憶手段に格納されたデータ要素群から、所定数の連続するアドレスのデータブロックを抽出して、前記第２の記憶手段に格納する第２格納ステップと、前記第２の記憶手段に格納された前記データブロックについて、当該データブロックに含まれる各データ要素のデータ値に基づいてヒープソートを行うステップと、前記ヒープソートにより並び替えられた前記データブロックに基づいて、前記第１の記憶手段に格納された当該データブロックのデータ値を更新するステップと、を実行させ、前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、ように機能させることを特徴とする。
【発明の効果】
【００１５】
請求項１に記載の発明によれば、ヒープソートの処理単位毎に２分木構造を維持したまま連続するアドレスに格納するためメモリアクセスの局所性が高まり、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しない。
【００１６】
請求項２に記載の発明によれば、ヒープソートの処理順にデータを格納しておくことで、大規模容量ディスクとメモリ間のスワッピングの発生を抑制することができる。
【００１７】
請求項３に記載の発明によれば、ヒープソートの処理単位のデータブロック毎にまとめて大容量ディスクに格納し、そのデータブロック単位でメモリに転送して処理を行うことで、大規模容量ディスクとメモリ間のスワッピングの発生を抑制することができる。
【００１８】
請求項４に記載の発明によれば、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、データ量がメインメモリサイズより大きい大規模なデータセットのヒープソートの処理速度を極端に低下させずに処理できる。
【００１９】
請求項５に記載の発明によれば、データ量がメインメモリサイズより大きい大規模なデータセットに対してクラスタリング処理を行う際に、専用のハードウェアを用いずに、ソフトウェア的にクラスタリングを実装した場合にも、処理速度が極端に低下しないようにできる。
【００２０】
請求項６に記載の発明によれば、クラスタリングの結果、データ構造を再構築して処理を継続する場合にも、処理速度が極端に低下しないようにできる。
【００２１】
請求項７に記載の発明によれば、同一の層に位置するデータブロックについては並列処理が容易であり、ヒープソートの処理を高速化できる。
【００２２】
請求項８に記載の発明によれば、データ量がメインメモリサイズより大きい大規模なデータセットに対して、処理速度が極端に低下しないようにコンピュータを機能させることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための好適な実施の形態（以下、実施形態という）を、図面に従って説明する。
【００２４】
図１には、本実施形態に係るデータ分析装置の機能ブロック図を示す。図１に示されるように、データ分析装置１０は、機能的な構成として、大容量低速記憶部２０、小容量高速記憶部２２、データ管理部２４、２分木データ配列部２６、ヒープソート処理部２８、及びクラスタリング処理部３０を備える。なお、データ管理部２４、２分木データ配列部２６、ヒープソート処理部２８、及びクラスタリング処理部３０の各機能は、コンピュータシステムたるデータ分析装置１０がコンピュータプログラムに従って動作することにより実現されるものとしてよい。また、コンピュータプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、フラッシュメモリ等のコンピュータが読み取り可能なあらゆる形態の情報記録媒体に格納され、データ分析装置１０に接続された図示しない媒体読み取り装置によりデータ分析装置１０に読み込まれることとしてもよい。また、コンピュータプログラムは、ネットワークを介してデータ分析装置１０にダウンロードされることとしても構わない。
【００２５】
大容量低速記憶部２０は、ハードディスク装置やフラッシュメモリ等により構成される大容量の記憶装置である。大容量低速記憶部２０は、データやプログラムが格納される他、メモリのスワップ領域としても用いられる。
【００２６】
小容量高速記憶部２２は、ＲＡＭ（ランダムアクセスメモリ）やキャッシュ（１次，２次キャッシュ）等により構成される高速にアクセスが可能な記憶装置である。小容量高速記憶部２２は、大容量低速記憶部２０に対して記憶容量が小さいが高速に読み・書き等のアクセスをすることができる。
【００２７】
データ管理部２４は、大容量低速記憶部２０と小容量高速記憶部２２との間でデータ転送を行う入出力コントローラである。データ管理部２４は、ＣＰＵ（中央処理装置）から指示されたメモリアドレスに基づいて、メモリに格納されたデータの読み出し又は書き込みを行う。
【００２８】
２分木データ配列部２６は、複数のデータ要素からなるヒープソートの処理対象データを２分木構造に配列するとともに、処理対象データを所定の要素数からなる２分木構造のデータブロックに分割して、大容量低速記憶部２０に格納する際の順序を決定する。ここで、２分木データ配列部２６は、データブロックの番号に対応づけてそのデータブロックが大容量低速記憶部２０のどのアドレスに格納されたかを記憶しておくこととしてもよい。
【００２９】
図２には、２分木データ配列部２６により２分木構造に配列された処理対象データの一例を示す。図２に示されるように、データ要素「１」を親として、その下にデータ要素「２」及び「３」がデータ要素「１」の子として配列されている。２分木データ配列部２６は、このような２分木構造の配列規則に従って処理対象データを順に配列していく。
【００３０】
次に、２分木データ配列部２６は、２分木構造に配列された処理対象データを、所定数の要素からなる２分木構造のデータブロックに分割する。例えば、処理対象データを、親，子，親，子の４層の２分木構造のデータブロックに分割する場合には、図２に示されているように１５個のデータ要素からなるデータブロック毎に処理対象データを分割する。
【００３１】
図３に示されるように、分割された各データブロックは、それぞれ２分木構造における親，子の順序で大容量低速記憶部２０に順次格納される。具体的には、１つのデータブロックが１５個のデータからなるとすると以下のように格納される。まず、データブロック０には、データ要素「１」から「１５」までのデータが格納される。ここで、データブロック０では、２分木構造の根に位置するデータ要素「１」を親として、その子のデータ要素「２」，「３」、そして３層目のデータ要素の１つ（例えばデータ要素「４」）を親としてその子のデータ要素「８」，「９」、同様にデータ要素「５」，「１０」，「１１」という規則で配列して大容量低速記憶部２０の連続するメモリアドレスに格納する。他のデータブロックに関しても同様の規則に従って大容量低速記憶部２０に格納する。
【００３２】
ヒープソート処理部２８は、処理対象データのヒープソートを実行する。ヒープソート処理部２８は、ハードディスク等の記憶装置に格納されたヒープソートプログラムに基づいて、大容量低速記憶部２０から抽出した処理対象データを小容量高速記憶部２２に格納した上で、その格納した処理対象データに対してヒープソートを行う。ここで、処理対象データのデータサイズが膨大となると、小容量高速記憶部２２には格納しきれない状態となるため、本実施形態では、大容量低速記憶部２０から処理対象データの一部のデータブロックを抽出して、小容量高速記憶部２２に格納してヒープソートを行い、そのヒープソートの結果を大容量低速記憶部２０に戻した上で、新たなデータブロックを小容量高速記憶部２２に転送してヒープソートを行うという処理を順次繰り返す。上記の処理は、全てのデータブロックに対してヒープソート処理が終了するまで繰り返される。
【００３３】
なお、各データブロックについて行われる根を最小値とするヒープソートの処理の概要は以下の通りである。データブロックの要素数が１５の時に、各データブロックの要素を２分木構造の順序で配列した配列Ｎ（要素数ｎ＝１５）として、ｉを整数としてｉ＝ｎ／２、ａ＝ｉとした場合に、配列ＮのデータＮ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較して、Ｎ［ａ］が最小の時にはデータの入れ替えを行わない。そして、ｉをデクリメントした上で、ａ＝ｉとして、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。ここで、Ｎ［２ａ］が最小の時には、Ｎ［ａ］とＮ［２ａ］のデータを入れ替え、ａに２ａを代入して、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。ここで、Ｎ［２ａ＋１］が最小の時には、Ｎ［ａ］とＮ［２ａ＋１］のデータを入れ替え、ａに２ａ＋１を代入して、Ｎ［ａ］，Ｎ［２ａ］，Ｎ［２ａ＋１］を比較する。上記の処理をｉのデクリメントを行いながら繰り返し、ａが１になるまで処理を行う。
【００３４】
ヒープソート処理部２８は、処理対象データ全体に対するヒープソートの処理を例えば以下の手順で行う。ヒープソート処理部２８は、まず大容量低速記憶部２０に格納されたデータブロックの中から、最下層のデータブロックの少なくとも一部を抽出して、小容量高速記憶部２２に格納する。そして、ヒープソート処理部２８は、小容量高速記憶部２２に格納されたデータブロックに対して上述したアルゴリズムに従ってヒープソートを実行する。なお、小容量高速記憶部２２には複数のデータブロックを転送して、各データブロックについてのヒープソートを並列処理にしてもよい。並列に処理するデータブロック数は、小容量高速記憶部２２のデータ容量と、データブロックのデータサイズに応じて決定することとしてよい。
【００３５】
クラスタリング処理部３０は、クラスタリング処理の対象とするデータ（以下、クラスタリング対象データとする）を複数のクラスタに分類する。クラスタ構造は、階層構造にすることとしてもよい。例えば、複数の文書からなる文書群を複数のクラスタに分類する場合には、各文書から抽出された特徴ベクトルをクラスタリング対象データとすることができる。
【００３６】
本実施形態では、クラスタリング対象データを特徴ベクトルとし、２つの特徴ベクトル間の距離をそれぞれ算出して、それらの距離データをヒープソートの処理対象データとして最小値が２分木構造の根にくるようにヒープソートを行う。そして、ヒープソートの結果得られた距離が小さい特徴ベクトル同士を同一のクラスタに分類することとする。すなわち、クラスタリング対象データたる要素数ｎの特徴ベクトルＤ１〜Ｄｎに対して、それぞれのベクトルデータの距離、ｄ１，２，ｄ１，３，…，ｄ１，ｎ，…，ｄｎ−１，ｎを算出し、それらのデータ群をヒープソート対象データとする。なお、ｄｉ，ｊとは特徴ベクトルＤｉとＤｊとの距離であるとする。また、ヒープソート対象データ数は、クラスタリング対象データがｎ個あるとすると、ｎ（ｎ−１）／２となる。
【００３７】
クラスタリング処理部３０では、ヒープソート対象データを２分木データ配列部２６により２分木構造に配列するとともに、配列したヒープソート対象データを所定数（例えば１５個）のデータからなるデータブロックに分割して、データブロック毎に大容量低速記憶部２０に格納する。格納されたヒープソート対象データは、データブロック毎に小容量高速記憶部２２に読み込まれて順次ヒープソートが実行される。
【００３８】
なお、ヒープソートの同じ層に位置するデータブロックについてヒープソートが終了し、その上位に位置するデータブロックについてヒープソートを開始する際には、上位のデータブロック並びに下位のデータブロックのうち少なくとも上位のデータブロックに接続しているノードについて小容量高速記憶部２２に読み込み、上位のデータブロックのヒープソートを行う。そして、ヒープソートは、下位の階層から上位の階層へと順次処理を進めて、最上位のデータブロックについての処理が終了するまで実行される。
【００３９】
ヒープソート処理が終了すると、クラスタリング処理部３０は、ヒープソートの結果、例えば根に格納されたデータ要素がｄｋ，ｌである場合には、特徴ベクトルＤｋとＤｌとが同じクラスタに属すると判断する。そして、クラスタリング処理部３０は、ヒープソート対象データについて、同じクラスタに属する特徴ベクトルＤｋとＤｌとを同じ要素とみなして、どちらか一方の要素と他の特徴ベクトルとの距離データをヒープソート対象データの中から削除する。ここで、２分木データ配列部２６は、要素が削除されたヒープソート対象データに基づいて２分木構造の配列を再構築し、大容量低速記憶部２０に格納する。
【００４０】
クラスタリング処理部３０は、所定の終了条件を満たすまで、クラスタリング対象データに対するクラスタリング処理を実行する。所定の終了条件とは、例えばクラスタリング対象データが所定数まで絞り込まれたこととしてもよいし、その他にも、クラスタ数が所定数に達したこと、又は距離が所定の範囲内にある特徴ベクトルがなくなるまで等の様々な条件を採ることとしてよい。
【００４１】
次に、図４を参照しつつ、本実施形態に係るデータ分析装置１０によるクラスタリング処理の一連の流れを説明する。
【００４２】
まず、データ分析装置１０は、複数の特徴ベクトルを要素としたクラスタリング対象データを読み込む（Ｓ１０１）。データ分析装置１０は、読み込んだクラスタリング対象データのそれぞれの特徴ベクトル間の距離データ（以下、ヒープソート対象データとする）を算出し（Ｓ１０２）、ヒープソート対象データを２分木構造に配列する（Ｓ１０３）。データ分析装置１０は、２分木構造に配列したヒープソート対象データを所定要素数からなるデータブロックに分割して、ＨＤＤ等の大容量低速記憶部２０に一旦格納する（Ｓ１０４）。
【００４３】
次に、データ分析装置１０は、大容量低速記憶部２０に一旦格納されたヒープソート対象データの中から、データブロックを単位として抽出し、ＲＡＭ等の小容量高速記憶部２２に格納するとともに、格納したデータブロックの根のノードに最小値が配置されるようにヒープソートを行う（Ｓ１０５）。データ分析装置１０は、上記のヒープソートを下位の層のデータブロックから順次実行し、全てのデータブロック、すなわち最上位の層のデータブロックについて処理が終了したか否かを判断し（Ｓ１０６）、終了していない場合には（Ｓ１０６：Ｎ）、未処理のデータブロックを読み込んでヒープソートを実行する。一方で、全てのデータブロックについて処理が終了した場合には（Ｓ１０６：Ｙ）、ヒープソートの結果、距離が近いクラスタリング対象データ同士を同一のクラスタに分類するとともに、同一のクラスタに分類された一方のデータに関する距離データをヒープソート対象データの中から削除する（Ｓ１０７）。データ分析装置１０は、クラスタリングの結果が所定の終了条件、例えばクラスタ数が所定数まで達したか否か、又は最小の距離が所定条件内にあること等を満たしているか否かを判断し（Ｓ１０８）、その終了条件を満たしていない場合には（Ｓ１０８：Ｎ）、ヒープソート対象データを再配列するとともに以下の処理を繰り返し、終了条件を満たしている場合には（Ｓ１０８：Ｙ）、クラスタリング処理を終了する。また、データ分析装置１０は、上記処理により得られたクラスタリング結果をディスプレイに表示することとしてもよい。
【００４４】
以上説明した本実施形態に係るデータ分析装置１０によれば、データ分析装置１０がコンピュータプログラムに基づいてクラスタリング処理を行う場合にも、データ量がメインメモリサイズより大きい大規模なデータセットに対して処理速度を極端に低下させないようにできる。
【００４５】
なお、本発明は上記の実施形態に限定されるものではなく、例えばデータブロック毎にそのデータブロックが現在処理対象になっているのか否かを示すフラグを対応づけて記憶することとしてもよい。フラグはそのデータブロックが処理されていない状態（クリアー状態）であれば「０」を、処理されている状態（ビジー状態）であれば「１」を格納しておくこととしてよい。そして、データ分析装置１０は、処理対象とするデータブロックのフラグがクリア状態「０」であるものを発見するまで読み出しを継続して並列処理を行うこととしてよい。また、処理対象データに応じて構築された２分木構造に応じて、最適な処理順序を予め決定した上でデータの並列処理を行うこととしてもよい。
【図面の簡単な説明】
【００４６】
【図１】本実施形態に係るデータ分析装置の機能ブロック図である。
【図２】２分木構造に配列された処理対象データの一例を示す図である。
【図３】処理対象データをメモリアドレスに格納する順序を示す図である。
【図４】クラスタリング処理の一連の流れを説明するフロー図である。
【符号の説明】
【００４７】
１０ データ分析装置、２０ 大容量低速記憶部、２２ 小容量高速記憶部、２４ データ管理部、２６ ２分木データ配列部、２８ ヒープソート処理部、３０ クラスタリング処理部。
【特許請求の範囲】
【請求項１】
第１の記憶手段と、
前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、
複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段の連続するアドレスに格納する第１格納手段と、
前記第１の記憶手段から、所定数の連続するアドレスに格納された前記データ要素群の部分要素群を抽出して、前記第２の記憶手段に格納する第２格納手段と、
前記第２の記憶手段に格納された前記部分要素群に含まれる各データ要素のデータ値をヒープソートにより並び替える手段と、
前記データ値が並び替えられた部分要素群に基づいて、前記第１の記憶手段において当該部分要素群に対応するアドレスに格納されたデータ値を更新する手段と、を含み、
前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ことを特徴とするデータ分析装置。
【請求項２】
前記第１格納手段は、前記２分木構造の上位層又は下位層のいずれかから順に、前記データ要素群を前記第１の記憶手段の連続するアドレスに格納する、
ことを特徴とする請求項１に記載のデータ分析装置。
【請求項３】
前記第１格納手段は、前記データ要素群を、前記所定数のデータ要素からなる２分木構造のデータブロックに分割するとともに、当該分割された各データブロックについてそれぞれ親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段の連続するアドレスに格納し、
前記第２格納手段は、前記データブロック毎にデータを抽出して前記第２の記憶手段に格納する、
ことを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項４】
前記第１の記憶手段から前記所定数の連続するアドレスに格納された部分要素群を新たに抽出して、当該新たに抽出した部分要素群のデータ値を更新する処理を所定の終了条件が満たされるまで繰り返して実行した後に、前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ことを特徴とする請求項１乃至３のいずれかに記載のデータ分析装置。
【請求項５】
前記データ要素群は、クラスタリングの対象とする複数のスカラ又はベクトルデータ間のそれぞれの距離データをデータ要素とし、
前記所定の終了条件が満たされた後に前記第１の記憶手段に格納されたデータ要素群に基づいてクラスタリングを行う、
ことを特徴とする請求項４に記載のデータ分析装置。
【請求項６】
前記所定の条件が満たされた後に、前記２分木構造の根のデータ要素を距離データとした２つのクラスタリング対象データを同一のクラスタとして分類する手段と、
前記同一のクラスタに分類されたクラスタリング対象データのいずれか一方に関する全ての距離データを前記データ要素群のデータ要素の中から削除する手段と、をさらに含み、
前記第１格納手段は、前記データ要素が削除されたデータ要素群を２分木構造に再び配列するとともに、当該配列したデータ要素群を前記第１の記憶手段に格納する、
ことを特徴とする請求項５に記載のデータ分析装置。
【請求項７】
前記第２格納手段は、前記第１の記憶手段から前記データ要素群の異なる部分要素群を複数抽出して前記第２の記憶手段に格納し、
前記第２の記憶手段に格納された各部分要素群についてのヒープソートを並列処理により行う、
ことを特徴とする請求項１乃至６のいずれかに記載のデータ分析装置。
【請求項８】
第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、を備えるコンピュータに、
複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段に格納する第１格納ステップと、
前記第１の記憶手段に格納されたデータ要素群から、所定数の連続するアドレスのデータブロックを抽出して、前記第２の記憶手段に格納する第２格納ステップと、
前記第２の記憶手段に格納された前記データブロックについて、当該データブロックに含まれる各データ要素のデータ値に基づいてヒープソートを行うステップと、
前記ヒープソートにより並び替えられた前記データブロックに基づいて、前記第１の記憶手段に格納された当該データブロックのデータ値を更新するステップと、を実行させ、
前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ように機能させることを特徴とするデータ分析プログラム。
【請求項１】
第１の記憶手段と、
前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、
複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段の連続するアドレスに格納する第１格納手段と、
前記第１の記憶手段から、所定数の連続するアドレスに格納された前記データ要素群の部分要素群を抽出して、前記第２の記憶手段に格納する第２格納手段と、
前記第２の記憶手段に格納された前記部分要素群に含まれる各データ要素のデータ値をヒープソートにより並び替える手段と、
前記データ値が並び替えられた部分要素群に基づいて、前記第１の記憶手段において当該部分要素群に対応するアドレスに格納されたデータ値を更新する手段と、を含み、
前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ことを特徴とするデータ分析装置。
【請求項２】
前記第１格納手段は、前記２分木構造の上位層又は下位層のいずれかから順に、前記データ要素群を前記第１の記憶手段の連続するアドレスに格納する、
ことを特徴とする請求項１に記載のデータ分析装置。
【請求項３】
前記第１格納手段は、前記データ要素群を、前記所定数のデータ要素からなる２分木構造のデータブロックに分割するとともに、当該分割された各データブロックについてそれぞれ親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段の連続するアドレスに格納し、
前記第２格納手段は、前記データブロック毎にデータを抽出して前記第２の記憶手段に格納する、
ことを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項４】
前記第１の記憶手段から前記所定数の連続するアドレスに格納された部分要素群を新たに抽出して、当該新たに抽出した部分要素群のデータ値を更新する処理を所定の終了条件が満たされるまで繰り返して実行した後に、前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ことを特徴とする請求項１乃至３のいずれかに記載のデータ分析装置。
【請求項５】
前記データ要素群は、クラスタリングの対象とする複数のスカラ又はベクトルデータ間のそれぞれの距離データをデータ要素とし、
前記所定の終了条件が満たされた後に前記第１の記憶手段に格納されたデータ要素群に基づいてクラスタリングを行う、
ことを特徴とする請求項４に記載のデータ分析装置。
【請求項６】
前記所定の条件が満たされた後に、前記２分木構造の根のデータ要素を距離データとした２つのクラスタリング対象データを同一のクラスタとして分類する手段と、
前記同一のクラスタに分類されたクラスタリング対象データのいずれか一方に関する全ての距離データを前記データ要素群のデータ要素の中から削除する手段と、をさらに含み、
前記第１格納手段は、前記データ要素が削除されたデータ要素群を２分木構造に再び配列するとともに、当該配列したデータ要素群を前記第１の記憶手段に格納する、
ことを特徴とする請求項５に記載のデータ分析装置。
【請求項７】
前記第２格納手段は、前記第１の記憶手段から前記データ要素群の異なる部分要素群を複数抽出して前記第２の記憶手段に格納し、
前記第２の記憶手段に格納された各部分要素群についてのヒープソートを並列処理により行う、
ことを特徴とする請求項１乃至６のいずれかに記載のデータ分析装置。
【請求項８】
第１の記憶手段と、前記第１の記憶手段よりも記憶容量が小さく、高速にアクセスが可能な第２の記憶手段と、を備えるコンピュータに、
複数のデータ要素からなるデータ要素群を２分木構造に配列するとともに、当該２分木構造において親であるデータ要素、当該親の子であるデータ要素の順序で前記第１の記憶手段に格納する第１格納ステップと、
前記第１の記憶手段に格納されたデータ要素群から、所定数の連続するアドレスのデータブロックを抽出して、前記第２の記憶手段に格納する第２格納ステップと、
前記第２の記憶手段に格納された前記データブロックについて、当該データブロックに含まれる各データ要素のデータ値に基づいてヒープソートを行うステップと、
前記ヒープソートにより並び替えられた前記データブロックに基づいて、前記第１の記憶手段に格納された当該データブロックのデータ値を更新するステップと、を実行させ、
前記更新された前記第１の記憶手段に格納されたデータ要素群を所定の処理に供する、
ように機能させることを特徴とするデータ分析プログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２００９−１４６２１５（Ｐ２００９−１４６２１５Ａ）
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願番号】特願２００７−３２３７１７（Ｐ２００７−３２３７１７）
【出願日】平成１９年１２月１４日（２００７．１２．１４）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願日】平成１９年１２月１４日（２００７．１２．１４）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]