(57)【要約】 【課題】  クラスタのベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能なクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体を提供する。【解決手段】    度数分布データ作成手段１１が、複数のベクトルデータから、１つ以上の隣接する階級をクラスタとして、度数分布データを作成する。クラスタ決定手段１２は、所定のクラスタに含まれる各階級のうち最も大きな度数を有する階級である特定階級と、同一クラスタ内の他の階級との間の度数分布空間上の距離について、所定のクラスタに含まれる各階級のうち最も大きな度数を有する階級である特定階級と同一クラスタ内の他の階級の度数差で除した値であるばねの長さに基づいて、所定のクラスタを分割する。さらに、クラスタ統合手段１４は、クラスタの度数の合計値が、各クラスタの度数の合計値の平均未満である場合には、平均未満のクラスタと他の平均未満のクラスタと統合する。【選択図】  図１
2009087057.tif 000002
【特許請求の範囲】
【請求項１】
複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成する度数分布データ作成手段と、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級との間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理するクラスタ決定手段と、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合するクラスタ統合手段と、を含むことを特徴とするクラスタリング装置。
【請求項２】
複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成するステップと、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級との間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理するステップと、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合するステップと、を有することを特徴とするクラスタリング方法。
【請求項３】
コンピュータに、
複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成する手順、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級との間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理する手順、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合する手順、を実行させるためのプログラム。
【請求項４】
請求項３に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルデータをベクトル間類似度に基づいてクラスタリングする際のベクトルデータのクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
情報の中から類似する情報を見つけ出し、いくつかの集合に分けることをクラスタリングと言う。ＷＷＷ(World Wide Web)および企業内などに存在する大量の情報にクラスタリングを適用し、クラスタリングされた情報を検索に用いれば、情報の中から必要とする情報に迅速にたどり着くことができ、検索結果の概要を容易に知ることができるなどの利点を有する。ベクトルデータとは、点、線、面で構成される図形要素を座標値として管理しているデータである。ベクトル化された情報をクラスタリングする方法としては、階層的クラスタリングと非階層的クラスタリングがある。
【０００３】
階層的クラスタリングは、ｎ個の対象からなるデータが与えられたとき、まず、１個の対象だけを含むｎ個のクラスタ（Ｃ１〜Ｃｎ）がある初期状態を作成する。この初期状態から、対象とするデータＸ１およびＸ２間の非類似度を距離として表した場合の距離Ｄ（Ｘ１，Ｘ２）を算出する。次に、距離Ｄ（Ｘ１，Ｘ２）からクラスタＣ１およびＣ２間の距離Ｄ（Ｃ１，Ｃ２）を算出し、クラスタＣ１とその他のクラスタＣｍ（１≦ｍ≦ｎ）およびＣ２間の距離Ｄ（Ｃ１，Ｃｍ）も算出し、最もこの距離の近い２つのクラスタを逐次的に併合する。そして、全ての対象データが、一つのクラスタに併合されるまで併合を繰り返すことで階層構造を獲得する。予め、クラスタ数ｋを決めれば、ｋ個のクラスタに分かれる階層で区切ることによって、データをクラスタリングすることができる。
【０００４】
非階層的クラスタリングは、与えられたデータが階層構造をなさないクラスタリング手法であり、代表的な方法としてはｋ−ｍｅａｎｓ法がある。この方法は、データをベクトル化し、そのベクトルデータの集合をその距離に応じてｋ個のベクトルデータの集合にクラスタリングするものである。クラスタ数をｋ、分類すべき全ベクトルデータの数をｎとし、以下にｋ−ｍｅａｎｓ法の処理手順を示す。
（１）ｋ個のクラスタ中心の初期値をｎ個のベクトルの中から適当に選ぶ。
（２）ｎ個の各ベクトルデータを、最も近いクラスタ中心の初期値をもつクラスタに分類する。
（３）ｋ個の各クラスタにおいて、各々に含まれるベクトルデータの平均値を新たなクラスタ中心値とする。
（４）上記２と３を繰り返し、クラスタ中心値が変化しなくなったところで終了する。
【０００５】
上述のように、階層的クラスタリング、ｋ−ｍｅａｎｓ法のいずれもクラスタ数ｋを事前に人が決定することでクラスタリング結果を得ることができる。
【０００６】
クラスタ数ｋを人が決定するのではなく、自動的に決定する従来技術として、処理時間に基づいてクラスタ数ｋを決定し、クラスタリングを行う方法および装置がある（たとえば、特許文献１参照）。
【０００７】
【特許文献１】特開平１０−１７１８２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従来の技術ではクラスタ数を自動的に決定できても、得られたクラスタリング結果が必ずしも所望の結果となるとは限らない。例えば、階層的クラスタリングについては、クラスタ数によっては各クラスタのデータ数に偏りが生じる場合がある。場合によっては、全データ数の２％のデータを含むクラスタと４０％のデータを含むクラスタが共存する場合がある。例えば、文書情報の検索において利用するときに、検索結果を表示するときに上述のようなデータの偏りがあるクラスタが共存すると、表示される類似文書の数が多くなり、所望する文書を見つけることが困難である、また、表示される類似文書の数が少なくなり、所望する文書が表示されないなどといった問題が生じる可能性もある。これらの問題を防止するためには、階層構造を図示した樹形図（デンドログラム）に基づいて、人がデータ数の多いクラスタをより低い階層で分割するか、データ数の少ないクラスタをより高い階層で統合することによって、各クラスタのデータ数に偏りがなく、類似文書が集まったクラスタを構成する必要がある。
【０００９】
ｋ−ｍｅａｎｓ法においては、処理手順（１）におけるクラスタ中心の初期値の設定に応じてクラスタリング結果が変化する。例えば、複数の初期値がある領域に密集して設定され、１つの初期値のみがその領域から離れて設定されると、階層的クラスタリングと同様に各クラスタのデータ数に偏りが生じる場合がある。これを防止するには、クラスタ中心の初期値がランダムになるように、人が修正する必要があり、いずれのクラスタリング方法においても、データ数の多いクラスタとデータ数の少ないクラスタが存在し、データ数に偏りが生じないようなクラスタリングをすることが困難であるという問題がある。
【００１０】
したがって本発明の目的は、ベクトルデータをクラスタリングする場合において、ベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能なクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体を提供することである。
【課題を解決するための手段】
【００１１】
本発明は、複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成する度数分布データ作成手段と、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級のとの間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理するクラスタ決定手段と、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合するクラスタ統合手段と、を含むことを特徴とするクラスタリング装置である。
【００１２】
また本発明は、複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成するステップと、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級のとの間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理するステップと、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合するステップと、を有することを特徴とするクラスタリング方法である。
【００１３】
また本発明は、コンピュータに、
複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、前記度数分布において、度数を有し、かつ１つ以上の隣接する階級に含まれるデータをクラスタとして、前記クラスタに含まれる各データの階級およびその階級における度数を表す度数分布データを作成する手順、
前記度数分布データの中で、度数を有し、かつ２つ以上の隣接する階級を含む所定のクラスタに含まれ、かつ各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタであって、前記特定階級と同一クラスタ内の他の階級のとの間の度数分布空間上の距離について、前記特定階級と同一クラスタ内の他の階級の度数差で除した値をばねの長さとしたときに、
相互に隣接する階級が、前記ばねの長さと、クラスタ全体での前記ばねの長さの平均との差が０以上である階級のデータを含む第１クラスタと、前記第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、前記所定のクラスタを分割可能であり、前記度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理する手順、
クラスタに含まれる各データの各階級における度数の合計値が、各クラスタに含まれる各データの各階級における度数の合計値の平均未満である場合には、前記度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合する手順、を実行させるためのプログラムである。
【００１４】
また本発明は、前記プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１５】
本発明によれば、クラスタリング装置は、度数分布データ作成手段が、複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、１つ以上の隣接する階級をクラスタとして、度数分布データを作成する。クラスタ決定手段は、所定のクラスタに含まれる各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタと、第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、特定階級と同一クラスタ内の他の階級の度数差で除した値であるばねの長さに基づいて、所定のクラスタを分割可能である。また、クラスタ決定手段は、度数分布データ作成手段によって作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理する。さらに、クラスタ統合手段は、クラスタの度数の合計値が、各クラスタの度数の合計値の平均未満である場合には、平均未満のクラスタと、周囲の階級を含む他の平均未満のクラスタと統合する。したがって、クラスタリング装置は、ベクトルデータをクラスタリングする場合に、クラスタは、度数の差の大きな階級で分割され、クラスタの度数の合計値の小さなクラスタは、周囲に存在する度数の合計値の小さい他のクラスタと結合させられるので、クラスタ内の階級間での度数密度がほぼ均一となり、各クラスタに含まれるベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能である。また、初期に度数分布に集計することによって、以後に取り扱うデータ量を減らすことができるため、高速に演算することができる。
【００１６】
また本発明によれば、クラスタリング方法は、複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、１つ以上の隣接する階級をクラスタとして、度数分布データを作成する。所定のクラスタに含まれる各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタと、第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、特定階級と同一クラスタ内の他の階級の度数差で除した値であるばねの長さに基づいて、所定のクラスタを分割を実行することができる。また、作成された度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理する。さらに、クラスタの度数の合計値が、各クラスタの度数の合計値の平均未満である場合には、平均未満のクラスタと、周囲の階級を含む他の平均未満のクラスタと統合する。したがって、クラスタリング方法は、ベクトルデータをクラスタリングする場合に、クラスタは、度数の差の大きな階級で分割され、クラスタの度数の合計値の小さなクラスタは、周囲に存在する度数の合計値の小さい他のクラスタと結合させられるので、クラスタ内の階級間での度数密度がほぼ均一となり、各クラスタに含まれるベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能である。また、初期に度数分布に集計することによって、以後に取り扱うデータ量を減らすことができるため、高速に演算することができる。
【００１７】
また本発明によれば、プログラムは、コンピュータが、度数分布データ作成手段が、複数のベクトルデータを、１または複数のパラメータで表される度数分布に集計し、１つ以上の隣接する階級をクラスタとして、度数分布データを作成するように機能させる。所定のクラスタに含まれる各階級のうち最も大きな度数を有する階級である特定階級のデータを含む第１クラスタと、第１クラスタに含まれる階級のデータを除く残余の階級のデータを含む第２クラスタとに、特定階級と同一クラスタ内の他の階級の度数差で除した値であるばねの長さに基づいて、所定のクラスタを分割を実行するように機能させる。また、度数分布データにおけるクラスタを所定のクラスタとして処理し、所定のクラスタから第２クラスタが分割されたときには、第２クラスタを新たな所定のクラスタとして、再び処理するように機能させる。さらに、クラスタの度数の合計値が、各クラスタの度数の合計値の平均未満である場合には、平均未満のクラスタと、周囲の階級を含む他の平均未満のクラスタと統合するように機能させる。したがって、プログラムは、ベクトルデータをクラスタリングする場合に、クラスタは、度数の差の大きな階級で分割され、クラスタの度数の合計値の小さなクラスタは、周囲に存在する度数の合計値の小さい他のクラスタと結合させられるので、クラスタ内の階級間での度数密度がほぼ均一となり、各クラスタに含まれるベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能である。また、初期に度数分布に集計することによって、以後に取り扱うデータ量を減らすことができるため、高速に演算することができる。
【００１８】
また本発明によれば、プログラムを記録したコンピュータ読み取り可能な記録媒体は、前記プログラムを記録しているので、コンピュータに前記記録媒体を読取らせることによって、コンピュータに前記クラスタリング方法の各ステップを実行させることができ、クラスタの度数の合計値およびクラスタ内の度数密度がほぼ均一となり、各クラスタに含まれるベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能である。また、初期に度数分布に集計することによって、以後に取り扱うデータ量を減らすことができるため、高速に演算することができる。
【発明を実施するための最良の形態】
【００１９】
図１は、本発明の実施の一形態のクラスタリング装置５０の電気的構成を示すブロック図である。図２は、度数分布データ作成手段１１において、多次元のベクトルデータが初期クラスタに分類されるまでの工程を模式的に示した図である。図２（１）〜（３）は、２次元空間で相互に直交する座標軸をＸ軸およびＹ軸として、その座標軸上にそのベクトルデータを示している。
【００２０】
クラスタリング装置５０は、図１に示すように、度数分布データ作成手段１１、クラスタ決定手段１２、およびクラスタ統合手段１４を含んで構成される。
【００２１】
さらに、度数分布データ作成手段１１は、次元縮退手段１５、度数分布化手段１６、および初期クラスタ抽出手段１７を備える。
【００２２】
中央演算処理装置が所定のプログラムを実行処理することによって、度数分布データ作成手段１１、クラスタ決定手段１２、およびクラスタ統合手段１４、次元縮退手段１５、度数分布化手段１６、初期クラスタ抽出手段１７として機能する。
【００２３】
度数分布データ作成手段１１は、図示しない記憶部に予め記憶されたベクトルデータ、または、図示しない入力部から入力されるベクトルデータを、未確定のクラスタ段階である初期クラスタとして分類されている度数分布データに変換する。本実施形態では、個々のデータの類似度を距離関係として表したベクトルデータを処理対象としている。
【００２４】
次元縮退手段１５は、ベクトルデータの次元数を削減することによって、３次元以上の多次元のベクトルデータを、図２（１）に示すように、２次元ベクトルデータに変換する。次元縮退手段１５において多次元のベクトルデータを２次元ベクトルデータに次元縮退する場合を説明する。次元縮退の方法としては、たとえば、多次元尺度構成法（multi-
dimensional scaling；MDS、以下ＭＤＳと記載）がある。ＭＤＳは、計量多次元尺度構成法（metric MDS；計量ＭＤＳ）と非計量多次元尺度構成法（non-metric MDS；非計量ＭＤＳ）に分類される。計量ＭＤＳは、対象間の与えられた距離データをもとに対象の空間的布置を構成する方法である。非計量ＭＤＳは、対象間の距離データあるいは距離データに対応する非類似度データをもとに対象間の空間的布置を構成する方法である（齋藤堯幸，宿久洋（２００６）「関連性データの解析法」  共立出版  ３７〜１２３頁）。いずれの方法も、布置する空間の次元数を対象の次元数より減らすことによって、ベクトル間の距離関係、すなわち、類似度関係を比較的保ったまま次元縮退することができる。距離に関しては、たとえば、ユークリッド距離を用いてもよい。次元縮退の方法としては多次元尺度構成法以外にも多次元のベクトルデータにおけるベクトル間の距離関係をなるべく保ったまま低次元のベクトルに次元縮退する方法として、たとえば主成分分析を用いてもよい。
【００２５】
度数分布化手段１６は、図２（２）に示すように、２次元ベクトルデータを２値画像データに変換する。
【００２６】
図３は、度数分布化手段１６が、２次元ベクトルデータを２値画像データに変換する動作処理を示すフローチャートである。次元縮退手段１５によって２次元ベクトルデータが作成されたとき、あるいは度数分布データ作成手段１１に２次元ベクトルデータが入力されたとき、ステップＡ０からＡ１に移る。
【００２７】
ステップＡ１において、度数分布化手段１６は、２値画像データに変換する２次元ベクトルデータの座標を（ｘ,ｙ）とするとき、ｘ,ｙの最大値Ｘｍａｘ，Ｙｍａｘと最小値Ｘｍｉｎ，Ｙｍｉｎとから、ｘ,ｙの範囲Ｌｘ＝Ｘｍａｘ−ＸｍｉｎとＬｙ＝Ｙｍａｘ−Ｙｍｉｎとを求めた後、ステップＡ２に移る。
【００２８】
ステップＡ２では、２値画像データの解像度をｍ×ｎ（ｍ，ｎはともに自然数）、データ数をＮとするとき、以下の条件１と条件２を満たす最小のｍ，ｎを求めた後、ステップＡ３に移る。
条件１  ｍ：ｎ＝（Ｌx＋１）:（Ｌy＋１）
条件２  ｍ×ｎ≧Ｎ
【００２９】
ただし条件１について、ｍ，ｎは自然数であり、条件１を完全には満たせないので最も近い自然数ｍ, ｎを求めることとなる。条件１と条件２を満たすことによって、２次元ベクトル間の距離比（類似度関係）をなるべく保ったまま、ステップＡ３に進むことが可能となる。
【００３０】
ステップＡ３では、２次元ベクトルデータを２値画像データに変換する。２次元ベクトルデータの座標（ｘ,ｙ）を２値画像データ上の座標（Ｘ,Ｙ）に変換する。変換式を以下に示す。
【００３１】
【数１】
2009087057.tif 000003
【００３２】
【数２】
2009087057.tif 000004
【００３３】
２次元ベクトルデータが対応する画素の画素値を１とし、２次元ベクトルデータが対応していない画素の画素値を０とすることで、２値画像データを構成する。
【００３４】
図３を参照して、ステップＡ３で２次元ベクトルデータを２値画像データに変換した後、ステップＡ４で本処理を終了する。
【００３５】
ステップＡ１〜Ａ３によって、２次元ベクトル間の距離比（類似度関係）をなるべく保ったまま２次元ベクトルデータを２値画像データに変換することが可能となり、また、度数分布化手段１６における式１、式２に示されるような縮小率を変化させることで目的に応じて初期クラスタを変化させることができる。
【００３６】
本実施の形態では、各初期クラスタの１画素が、度数分布における１つの階級に対応しており、初期クラスタ抽出手段１７は、図２（３）に示すように、画素値が１である画素のうち、隣接する画素どうし、すなわち階級どうしを２値画像データから１つの領域として抽出し、初期領域である初期クラスタを決定する。隣接する階級とは、２つの階級の座標をそれぞれ（Ｘ１，Ｙ１）、（Ｘ２，Ｙ２）、２つの階級間の距離を
【００３７】
【数３】
2009087057.tif 000005
【００３８】
としたときに、２つの階級間の距離が１となる階級をいう。
図４は、初期クラスタ抽出手段１７が、２値画像データを、初期クラスタとして分類されている度数分布データに変換する動作処理を示すフローチャートである。度数分布化手段１６によって、２値画像データが作成されたとき、ステップＢ０からＢ１に移る。
【００３９】
ステップＢ１では、度数分布化手段１６において、画素値は「０」または「１」、ステータス情報は、チェック済ならば「処理済」、未チェックならば「未処理」、座標は（ｉ，ｊ）（１≦ｉ≦ｍ，１≦ｉ≦ｎ），初期値はｉ＝１，ｊ＝１に設定してステップＢ２に移る。
【００４０】
ステップＢ２では、ｉ＝１、ｊ＝１でのチェックは終了しているか否かを判断する。ステップＢ２で、終了していると判断した場合には、ステップＢ３に移り、終了していないと判断した場合には、ステップＢ４に移る。
【００４１】
ステップＢ３において、ｉ＝ｉ＋１、ｊ＝ｊとしてステップＢ４に移る。
ステップＢ４では、ｉ＝ｍ＋１であるか否かを判断する。ステップＢ４で、ｉ＝ｍ＋１であると判断した場合には、ステップＢ１２に移り、ｉ＝ｍ＋１でないと判断した場合には、ステップＢ５に移る。
【００４２】
ステップＢ５では、ステータス情報が未処理か否かを判断する。ステップＢ５で、未処理であると判断した場合には、ステップＢ６に移り、未処理でないと判断した場合には、ステップＢ３に移る。
【００４３】
ステップＢ６では、ステータス情報を処理済としてステップＢ７に移る。
ステップＢ７では、画素値が１か否かを判断する。ステップＢ７で、画素値が１であると判断した場合には、ステップＢ８に移り、画素値が１でないと判断した場合には、ステップＢ３に移る。
【００４４】
ステップＢ８では、座標（ｉ，ｊ）の隣接する画素について、順次画素値が１か否かを調べてステップＢ９に移る。
【００４５】
ステップＢ９では、隣接する画素で画素値が１で未チェックのものがあったか否かを判断する。ステップＢ９で、隣接する画素で画素値が１で未チェックのものがあったと判断した場合には、ステップＢ１０に移り、未チェックのものがないと判断した場合には、ステップＢ１６に移る。
【００４６】
ステップＢ１０では、隣接する画素で画素値が１で未チェックの画素のうちの１つの画素へ移動してステップＢ１１に移る。
【００４７】
ステップＢ１１では、ステータス情報を処理済としてステップＢ９に移る。
ステップＢ１５では、隣接する４方向をチェックしたか否かを判断する。ステップＢ１５で、チェックしたと判断した場合には、ステップＢ１６に移り、チェックしていないと判断した場合には、ステップＢ８に移る。
【００４８】
ステップＢ１６では、最初の移動元の階級であるか否かを判断する。本実施形態においては、深さ優先探索のように、見つけた画素値が１の画素を先へ先へとチェックしていき、それ以上先に画素値が１の画素がなくなった時点で後戻りしながら未チェックの隣接する画素値１の画素をチェックしていく。
【００４９】
ステップＢ１６で、最初の移動元の階級であると判断した場合には、ステップＢ１８に移り、最初の移動元の階級でないと判断した場合には、ステップＢ１７に移る。
【００５０】
ステップＢ１７では、１つ前の移動元、すなわち、移動前のステップＢ９時点の画素に戻ってステップＢ１５に移る。
【００５１】
ステップＢ１８では、画素値が１の隣接する画素を１つのクラスタとして、初期クラスタを決定してステップＢ３に移る。
【００５２】
ステップＢ１２では、ｉ＝１，ｊ＝ｊ＋１にしてステップＢ１３に移る。
ステップＢ１３では、ｊ＝ｎ＋１であるか否かを判断する。ステップＢ１３で、ｊ＝ｎ＋１であると判断した場合には、座標（ｍ，ｎ）までの全画素のチェックが終了したとしてステップＢ１４で本処理を終了する。ｊ＝ｎ＋１でないと判断した場合には、ステップＢ３に移る。
【００５３】
図５は、画素のデータ構造を構造体型配列で表した図である。座標が（ｉ，ｊ）である画素（ｉ，ｊ）のデータ構造を構造体型配列ｇ[ｉ][ｊ]で表している。各画素は、０または１の画素値と、処理済または未処理のいずれであるかについて記載されるステータス情報と、２次元ベクトルデータの該当数である分布度数を有する。分布度数は、たとえば、画素（１,１）に対応する２次元ベクトルデータが４つあるならば、この画素の分布度数は４となる。図５の構造体型配列では、たとえば、ｇ[１][１]においては、画素値は「１」、ステータス情報は「処理済」、分布度数は「４」が格納されている。
【００５４】
初期クラスタ抽出手段１７が、画素値が１である画素から初期クラスタを決定することによって、各初期クラスタについての度数分布データが求まり、各初期クラスタの各画素、すなわち、各階級の度数が求まる。
【００５５】
図６は、クラスタのデータ構造を構造体型配列で表した図である。座標が（ｉ，ｊ）に布置された階級を含むクラスタのデータ構造を構造体型配列ｇ[ｉ][ｊ]で表している。クラスタ番号は、初期クラスタの番号である。図６の構造体型配列では、たとえば、ｇ[１][１]においては、クラスタ番号は「１」、分布度数は「４」が格納されている。
【００５６】
度数分布データ作成手段１１によって、類似度の高いベクトルデータどうしはある階級に集約するようになり、初期クラスタはある階級を頂点とするような山状の分布傾向を示す。
【００５７】
クラスタ決定手段１２は、判別式に基づいて初期クラスタ内の各階級の結合および分割を行い、クラスタを決定する。判別式には、階級間の距離と各階級の度数を用いて表現した擬似的なばねの長さとそれを用いたフックの法則の式を用いる。ここでフックの法則の式を以下に示す。
【００５８】
【数４】
2009087057.tif 000006
【００５９】
ここで、Ｆはばねに働く力、ｋはばね定数であって、ばねの強さあるいは硬さを表し、ばねに固有の定数である。ｕは、ばねの伸びである。ばねの伸びｕは以下の式で表現される。
【００６０】
【数５】
2009087057.tif 000007
【００６１】
ここで、ｗはばねの長さ、Ｗはばねの自然長である。自然長とは、外から力を加えないときのばね固有の長さである。ばねの片方の端点を固定し、それを原点としてばねを伸び縮みさせた場合、ｕ＝ｗ−Ｗ＞０のときに、ばねには縮もうとする力、すなわち、原点に近づこうとする力（原点への引力）が働き、ｕ＝ｗ−Ｗ＜０のときに、ばねには伸びようとする力、すなわち、原点から離れようとする力（原点に対する斥力）が働く。
【００６２】
擬似的にばねの長さを定義し、フックの法則の式を判別式として用い、階級間に発生する力が引力の場合は、階級間の結合を行い、斥力の場合は、階級間の分割を行うと判定する。
【００６３】
次に、クラスタ決定手段１２は、判別式に基づいて、初期クラスタからクラスタを決定する。
【００６４】
図７は、クラスタ決定手段１２が、クラスタを決定する動作処理を示すフローチャートである。初期クラスタ抽出手段１７が、画素値が１である画素から初期クラスタを決定したとき、ステップＣ０からＣ１に移る。
【００６５】
ステップＣ１では、階級数が２以上の各初期クラスタにおいて、度数最大の階級を頂点ｔとする。頂点ｔの座標を（Ｘｔ，Ｙｔ）とした場合の頂点ｔと、同一クラスタ内に存在している、座標が（ｉ，ｊ）である他の階級（以下、階級（ｉ，ｊ）と表す）との間の距離を
【００６６】
【数６】
2009087057.tif 000008
【００６７】
とする。頂点ｔと同一クラスタ内の他の階級（ｉ，ｊ）との度数差をＤ（ｉ，ｊ）する。また、Ｌ（ｉ，ｊ）／Ｄ（ｉ，ｊ）をばねの長さ、クラスタ全体でのばねの長さの平均を自然長ＮＬと定義してステップＣ２へ移る。ここで、自然長ＮＬは、全クラスタ（単一の階級からなるクラスタを除いた残りのクラスタ群）でのばねの長さの平均である。
【００６８】
図８は、クラスタ決定手段１２が、クラスタを決定する具体例を示す図である。各クラスタの階級内に記載された数値は、度数である。ＸＹ座標上には、初期クラスタであるＰ，Ｑ，Ｒ，Ｓが存在している。たとえば、初期クラスタＱにおける頂点をｔＱとすると、ｔＱは、座標（７，４）に位置し、度数７である。したがって、ｔＱと座標（６，４）との距離は、Ｌ（６，４）＝１、ｔＱと座標（６，４）との度数差は、Ｄ（６，４）＝７−５＝２、Ｌ（６，４）/Ｄ（６，４）＝０．５である。また、クラスタ全体でのばねの長さの平均は以下のようにして求める。
【００６９】
まず、各領域においてＬ/Ｄを求める。
領域Ｐ：（１）１／２（座標（３，５）），（２）（√２）／５（座標（（２，５））
領域Ｑ：（３）１／２（（６，４）），（４）１／１（（７，５））,（５）２／６（（７，６））,（６）（√２）／５（（８，５））,（７）（√５）／６（（８，６））
領域Ｒ：なし（対象外）
領域Ｓ：（８）１／８
【００７０】
次に、平均ＮＬを求める。
ＮＬ＝（（１）＋（２）＋（３）＋（４）＋（５）＋（６）＋（７）＋（８））/８＝０．４２５となる。
【００７１】
また、図８の座標（２，２）のみからなるクラスタのように単一の階級からなるクラスタには処理を行わない。
【００７２】
図７を参照して、ステップＣ２では、各クラスタについて、頂点ｔからの距離が近い階級から順に、頂点ｔと対象階級が同一クラスタか否かを判定していく。フックの法則を以下の式５で定義する。ｋは正の定数である。
【００７３】
【数７】
2009087057.tif 000009
【００７４】
クラスタ決定手段１２は、Ｆ＜０ならば頂点ｔへの引力が働いているので、頂点ｔと対象階級は同一クラスタとし、Ｆ＞０ならば頂点ｔに対する斥力が働いているので別クラスタとする。Ｆ＝０の場合は引力も斥力も働いていないが、初期クラスタとなっていることから類似度は高いとみなすことができるので、同一クラスタとする。
【００７５】
本実施形態の前提として、多次元のベクトルデータは、ｋ−ｍｅａｎｓ法などの従来手法によるクラスタリングの結果、各クラスタのデータ数に極端に差が表れないようなデータを対象としている。よって、次元縮退、度数分布化を行なうと、１つの階級の度数が極端に高くなるような傾向と度数の低い階級数が広く集まる傾向を示す。
【００７６】
各階級を順に判定していき、クラスタが別クラスタと判定された階級を境界とすることで、距離１で連結する階級である隣接階級で構成される、頂点ｔを含む領域と含まない領域（境界となる階級を含む）に２分割されたならば、頂点ｔを含む領域を第１クラスタとして確定し、含まない領域を第２クラスタである新たなクラスタとする。また、クラスタ内の全ての階級が同一領域と判定されたならば、その領域をひとかたまりのクラスタとして決定する。クラスタが決定された後はステップＣ３へ移る。
【００７７】
図９は、クラスタ決定手段１２が、図８における初期クラスタＱについて、クラスタを決定する工程の具体例を示す図である。図９（１）の座標上には、クラスタＱが示されている。黒く塗りつぶされた階級が、頂点ｔＱであり、頂点ｔＱは、度数７の階級（７，４）である。クラスタの決定においては、頂点ｔＱからの距離が近い階級から順に、フックの法則の式によってクラスタ判定を行う。図９（２）に示すように、斜線が引かれた階級（６，４）および階級（７，５）は、ともにＬ（ｉ，ｊ）/Ｄ（ｉ，ｊ）―ＮＬ＞０、すなわち、Ｆ＜０となるため、頂点ｔＱと同一クラスタと判定される。図９（３）に示すように、記号「×」でしめされる階級（７，６）および階級（８，５）は、ともにＬ（ｉ，ｊ）/Ｄ（ｉ，ｊ）―ＮＬ＜０、すなわち、Ｆ＞０となるため、頂点ｔＱと別クラスタと判定される。図９（４）に示すように、クラスタ決定手段１２が順に判定していき、クラスタが別クラスタと判定された階級を境界とすることで、隣接階級で構成される頂点ｔＱを含む領域、すなわち、階級（６，４）および階級（７，５）と、含まない領域、すなわち、階級（７，６）および階級（８，５）および階級（８，６）に２分割されたならば、頂点ｔＱを含む領域（クラスタＶ）をひとかたまりのクラスタとして決定し、含まない領域（クラスタＺ）を新たなクラスタとする。
【００７８】
図７を参照して、ステップＣ４では、全てのクラスタの判定を終了しているか否かを判断する。ステップＣ４で、全てのクラスタについて判定を終了していると判断した場合には、ステップＣ５に移り、クラスタ決定手段１２は処理を終了する。判定を終了していないと判断した場合には、ステップＣ１に移る。
【００７９】
ステップＣ１に移ると、新たなクラスタについてステップＣ１〜Ｃ３を繰り返し、前記クラスタＺのように、クラスタを分割して新たなクラスタとなったものも含め、全てのクラスタを判定し、クラスタが確定した場合には、処理を終了する。
【００８０】
クラスタ決定手段１２が、Ｌ（ｉ，ｊ）/Ｄ（ｉ，ｊ）で表現される距離と度数の比（ばねの長さ）をフックの法則で表現される判別式に用い、この判別式に基づいてクラスタ決定手段１２を用いることで、２つの効果が得られる。第１の効果として、クラスタにおいて頂点が突出して高くない（度数があまり高くない）場合には、より多くの階級と結合してクラスタを構成する。これによって、1つのクラスタのデータ数が増加するようになる。第１の効果として、クラスタにおいて頂点が突出して高い（度数が非常に高い）場合にはより近辺の階級とのみ1つのクラスタを構成するようになる。これによって、1クラスタのデータ数の増加が抑えられる。この２つの効果によって、クラスタ間のデータ数の差が抑えられる。
【００８１】
クラスタ統合手段１４は、クラスタ決定手段１２によって、決定されたクラスタのうち、クラスタに含まれる度数の合計値が、各クラスタに含まれる度数の合計値の平均未満である場合には、度数の合計値が平均未満のクラスタと、このクラスタに含まれるデータの階級の周囲の階級を含む、度数の合計値が平均未満の他のクラスタと統合し、最終的なクラスタ結果を求める。
【００８２】
図１０は、クラスタ統合手段１４が、度数の合計値が平均未満のクラスタどうしを統合する動作処理を示すフローチャートである。クラスタ決定手段１２が、クラスタの決定を終了したとき、ステップＤ０からＤ１に移る。
【００８３】
ステップＤ１では、各クラスタの度数の合計値の平均Ｈを求め、ステップＤ２に移る。
ステップＤ２では、各クラスタの度数の合計値が平均Ｈ未満のクラスタについては、このクラスタ内の階級の周囲の階級、すなわち、このクラスタ内の階級と距離が１または２の平方根（以下、√２で示す）の階級を含む、度数の合計値が平均未満の他のクラスタと統合する。距離が１または√２の階級を含む、統合先候補クラスタが複数ある場合は、各統合先候補クラスタの頂点と度数の合計値が平均Ｈ未満の他のクラスタの頂点の間のばねの長さを求め、ばねの長さが最大となる統合先候補クラスタと統合する。また、距離が１または√２の統合先クラスタが全く存在しない場合には、処理は行わない。ここで、ばねの長さが最大となる統合先候補クラスタと統合するのは、ばねの長さが長い方がデータ数が少なく、データが広い階級に分布している領域である傾向にあるからである。ばねの長さを統合先クラスタの決定の基準に用いることで、データ数の少ないクラスタどうしが統合され、各クラスタのデータ数の差が縮まり、均等に近づく効果が得られる。
【００８４】
ステップＤ３では、全てのクラスタの度数の合計値が平均Ｈ以上になったか否かを判断する。ステップＤ３で、全てのクラスタについて、度数の合計値が平均Ｈ以上になったと判断した場合には、ステップＤ４に移り、クラスタ統合手段１４は、処理を終了する。全てのクラスタについて、度数の合計値が平均Ｈ以上になっていないと判断した場合には、ステップＤ１に移る。
【００８５】
以上のように本発明によれば、ベクトルデータをクラスタリングする場合に、クラスタは、度数の差の大きな階級で分割され、クラスタの度数の合計値の小さなクラスタは、周囲に存在する度数の合計値の小さい他のクラスタと結合させられるので、クラスタ内の階級間での度数密度がほぼ均一となり、各クラスタに含まれるベクトルデータ数に偏りが生じないようなクラスタリングを行うことが可能である。また、初期に度数分布に集計することによって、以後に取り扱うデータ量を減らすことができるため、高速に演算することができる。
【００８６】
また、本発明は、クラスタリング装置に限定されるものではなく、クラスタリング方法、コンピュータをクラスタリング装置として機能させるためのプログラム、および前記プログラムを記録した記録媒体をも包含する。記憶媒体としては前記プログラムを記録することが可能なすべての記憶媒体を挙げることができる。また、コンピュータ等は、前記プログラムを記憶媒体から読出したり、前記プログラムを通信ネットワークを介して受信したりし、前記プログラムを実行して、本発明を実施することができる。複数のコンピュータからなる装置においては、複数の処理を複数の端末に分散して行うことができる。
【００８７】
プログラムは、クラスタリング装置５０の図示しない記憶部、たとえば半導体メモリあるいはハードディスク装置などの記憶装置に記憶されているが、これらの記憶装置に限定されるものではなく、コンピュータで読取り可能な記録媒体に記録されていてもよい。記録媒体は、たとえば図示しない外部記憶装置としてプログラム読取装置を設け、そこに記録媒体を挿入することによって読取り可能な記録媒体であってもよいし、あるいは他の装置の記憶装置であってもよい。
【００８８】
本体と分離可能に構成される記録媒体は、たとえば磁気テープ／カセットテープなどのテープ系の記録媒体、フレキシブルディスク／ハードディスクなどの磁気ディスクもしくはＣＤ−ＲＯＭ（Compact Disk Read Only Memory）／ＭＯ（Magneto Optical disk）／ＭＤ（Mini Disc）／ＤＶＤ（Digital Versatile Disk）などの光ディスクのディスク系の記録媒体、ＩＣ（Integrated Circuit）カード（メモリカードを含む）／光カードなどのカード系の記録媒体、またはマスクＲＯＭ／ＥＰＲＯＭ（Erasable Programmable
Read Only Memory）／ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only 
Memory）／フラッシュＲＯＭなどの半導体メモリを含む固定的にプログラムを担持する記録媒体であってもよい。したがって、本発明は、コンピュータにクラスタリング方法の各工程を実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体として提供することができる。記録媒体に記録されたプログラムをコンピュータが実行することによって、前記実施の形態と同様の効果を達成することができる。
【００８９】
また、クラスタリング装置の他の形態として、多次元のベクトルデータにおいても、実現することが可能である。クラスタリング装置の他の形態においても、クラスタリング装置が、上述の実施の形態と同様の構成を備えることによって、上述の実施の形態と同様の効果を達成することができる。
【００９０】
（実施例）
階層的クラスタリングを用いて最終的に人が決定したクラスタであって、データ数を１０個ずつ含む１０個のクラスタに分かれる１００００次元のベクトルデータ（データ数１００）について本発明のクラスタリング方法を適用した。ベクトルデータは、技術関連文書１００件を、システム開発、設計、ナレッジマネジメントなどの１０個のカテゴリに分類して、各カテゴリに含まれる１０件の文書を抽出して、１００件の文書を構成し、各文書について形態素解析を実施して、ベクトル化を行うことによって得た。
【００９１】
まず次元縮退手段１５によって、次元数１００００のベクトルを次元数２に次元縮退した。図１１は、次元縮退手段１５によって、次元数１００００のベクトルデータを次元数２に次元縮退して示す図である。
【００９２】
次に度数分布化手段１６によって、２次元のベクトルデータを２値画像データに変換した。図１２は、度数分布化手段１６によって、２次元のベクトルデータを２値画像データに変換して示す図である。なお図１２の括弧内に示される数字は、それぞれの画素における度数を表す。図１１の座標から、Ｘｍａｘ＝１３５．３５８６、Ｘｍｉｎ＝−１６０．７６、Ｙｍａｘ＝１６３．９７９２、Ｙｍｉｎ＝−１１９．００６となることから、条件１および２を満たすｍおよびｎをそれぞれ、ｍ＝１１、ｎ=１０として、式（１）および（２）に基づいて、２値画像の座標を求めた。
【００９３】
次に初期クラスタ抽出手段１７によって初期クラスタを抽出した。図１３は、初期クラスタ抽出手段１７によって抽出される初期クラスタを示す図である。２点鎖線で囲まれた範囲が１つのクラスタであり、クラスタにおける頂点の画素を斜線で示している。
【００９４】
次にクラスタ決定手段１２によって、初期クラスタを分割した。図１４は、クラスタ決定手段１２によって、初期クラスタを分割して示す図である。初期クラスタは、破線の部分で分割される。また度数と各階級間の距離に基づいて、クラスタ決定手段１２によってクラスタの決定を行なう。図１５は、クラスタ決定手段１２によって決定されたクラスタを示す図である。なお図１５では、分割状態がわかるように各画素間の間隔をあけて表示している。
【００９５】
次にクラスタ統合手段１４によってクラスタを統合した。図１６は、クラスタ統合手段１４によって統合された最終的なクラスタを示す図である。鎖線円で囲まれた範囲が１つのクラスタであり、図中の数字は各クラスタのデータ数を表している。図１７は、最終的に各クラスタに含まれる技術文書を示す。図１７は、クラスタの番号と、そのクラスタに含まれる技術文書が最初に含まれていたカテゴリを示す図である。カテゴリは、左側の括弧内の数字がカテゴリの番号を表し、右側の数字がカテゴリ内での番号を表す。
【００９６】
図１８は、実施例のベクトルデータについて、階層的クラスタリングを用いて最終的に人が決定した理想的なクラスタを示す図である。鎖線円で囲まれた範囲が１つのクラスタを表している。図１６および図１７を比較すると判るように、本発明のクラスタリング方法を用いることによって、各クラスタのデータ数がほぼ均等にかつ想定したクラスタに近く分割されることが判る。
【図面の簡単な説明】
【００９７】
【図１】本発明の実施の一形態のクラスタリング装置５０の電気的構成を示すブロック図である。
【図２】度数分布データ作成手段１１において、多次元のベクトルデータが初期クラスタに分類されるまでの工程を模式的に示した図である。
【図３】度数分布化手段１６が、２次元ベクトルデータを２値画像データに変換する動作処理を示すフローチャートである。
【図４】初期クラスタ抽出手段１７が、２値画像データを、初期クラスタとして分類されている度数分布データに変換する動作処理を示すフローチャートである。
【図５】画素のデータ構造を構造体型配列で表した図である。
【図６】クラスタのデータ構造を構造体型配列で表した図である。
【図７】クラスタ決定手段１２が、クラスタを決定する動作処理を示すフローチャートである。
【図８】クラスタ決定手段１２が、クラスタを決定する具体例を示す図である。
【図９】クラスタ決定手段１２が、クラスタを決定する具体例を示す図である。
【図１０】クラスタ統合手段１４が、度数の合計値が平均未満のクラスタどうしを統合する動作処理を示すフローチャートである。
【図１１】次元縮退手段１５によって、次元数１００００のベクトルデータを次元数２に次元縮退して示す図である。
【図１２】度数分布化手段１６によって、２次元のベクトルデータを２値画像データに変換して示す図である。
【図１３】初期クラスタ抽出手段１７によって抽出される初期クラスタを示す図である。
【図１４】クラスタ決定手段１２によって、初期クラスタを分割して示す図である。
【図１５】クラスタ決定手段１２によって決定されたクラスタを示す図である。
【図１６】クラスタ統合手段１４によって統合された最終的なクラスタを示す図である。
【図１７】クラスタの番号と、そのクラスタに含まれる技術文書が最初に含まれていたカテゴリを示す図である。
【図１８】実施例のベクトルデータについて、階層的クラスタリングを用いて最終的に人が決定した理想的なクラスタを示す図である。
【符号の説明】
【００９８】
１１  度数分布データ作成手段
１２  クラスタ決定手段
１４  クラスタ統合手段
１５  次元縮退手段
１６  度数分布化手段
１７  初期クラスタ抽出手段
５０  クラスタリング装置
【図１】
2009087057.tif 000010
【図２】
2009087057.tif 000011
【図３】
2009087057.tif 000012
【図４】
2009087057.tif 000013
【図５】
2009087057.tif 000014
【図６】
2009087057.tif 000015
【図７】
2009087057.tif 000016
【図８】
2009087057.tif 000017
【図９】
2009087057.tif 000018
【図１０】
2009087057.tif 000019
【図１１】
2009087057.tif 000020
【図１２】
2009087057.tif 000021
【図１３】
2009087057.tif 000022
【図１４】
2009087057.tif 000023
【図１５】
2009087057.tif 000024
【図１６】
2009087057.tif 000025
【図１７】
2009087057.tif 000026
【図１８】
2009087057.tif 000027