(57)【要約】 【課題】  各クラスタに含まれるベクトル数の偏りをより少なくすることができるクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体を提供する。【解決手段】  次元縮退手段１１は、多次元ベクトルデータを２次元ベクトルデータに変換し、画像化手段１２は、２次元ベクトルデータを２値画像データに変換する。領域抽出手段１３は、２値画像データが示す画像を構成する画素のうち２次元ベクトルに対応する画素の中から、隣接する画素から構成される初期領域を抽出する。クラスタ範囲決定手段１４は、初期領域ごとに、画素の度数の分布から２次元正規分布を抽出し、抽出した２次元正規分布ごとの平均と標準偏差とに基づいて、クラスタの範囲を決定する。クラスタ決定手段１５は、画素がクラスタの範囲に含まれるか否かおよび評価値Ｈによって、画素をクラスタに分類する。【選択図】      図１
2009048575.tif 000002
【特許請求の範囲】
【請求項１】
多次元ベクトルを表す多次元ベクトルデータを入力する入力手段と、
入力手段によって入力された多次元ベクトルデータを、予め定める次元変換方式によって２次元ベクトルを表す２次元ベクトルデータに変換する次元変換手段と、
次元変換手段によって変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化手段と、
画像化手段によって変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出手段と、
領域抽出手段によって抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定手段と、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定手段によって範囲が決定されたクラスタに、各画素を分類する画素分類手段とを含むこと特徴とするクラスタリング装置。
【請求項２】
前記予め定める分類条件は、
画素に付与される度数が１つの正規分布のみを構成する度数の場合は、その度数が付与される画素を、その度数が構成する正規分布に対応するクラスタに分類し、
画素に付与される度数の一部が複数の正規分布を構成する度数の場合は、その度数が付与される画素を、その度数の一部が構成する複数の正規分布のうち、正規分布の標準偏差を平均で除算した評価値が最も大きい正規分布に対応するクラスタに分類し、
画素に付与される度数がいずれの正規分布をも構成しない度数の場合は、その度数が付与される画素を、その度数が付与される画素に最も近い範囲のクラスタのうち、前記評価値が最も大きいクラスタに分類することを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
多次元ベクトルを表す多次元ベクトルデータを入力する入力ステップと、
入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する次元変換ステップと、
次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化ステップと、
画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出ステップと、
領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定ステップと、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する画素分類ステップとを含むこと特徴とするクラスタリング方法。
【請求項４】
多次元ベクトルを表す多次元ベクトルデータを入力する入力ステップと、
入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する次元変換ステップと、
次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化ステップと、
画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出ステップと、
領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定ステップと、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する画素分類ステップとを、コンピュータに実行させるためのプログラム。
【請求項５】
請求項４に記載のプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の要素からなる集合を部分集合であるクラスタに分割するクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体に関し、より詳細には、多次元ベクトルの集合をベクトル間の類似度に基づいてクラスタに分割するクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
複数の要素からなる集合の中から類似する要素を見つけ出して、集合をいくつかの部分集合に分割することをクラスタリングという。クラスタリングは、ウェブ（Ｗｅｂ）あるいは企業内などで利用される大量の情報の分類に適用され、クラスタリングによって大量の情報を類似する情報に分割することができる。クラスタリングは、必要とする情報を速く見つけることを可能とし、さらに類似する情報の特長を情報の概要として示すことを可能とすることができるので、情報の検索に利用することができる。
【０００３】
ベクトルの集合のクラスタリングには、階層的クラスタリングと非階層的クラスタリングとがある。
【０００４】
階層的クラスタリングは、たとえば集合にＮ個のベクトルが含まれる場合、まず個々のベクトルからなるＮ個のクラスタを形成する。次に、２つのベクトルの距離に基づいて、各ベクトルをそれぞれ含む２つのクラスタ間の距離を計算し、クラスタ間の距離が最も小さい２つのクラスタ同士を１つに併合する。そして、この併合を、すべてのクラスタが１つのクラスタに併合されるまで順次繰り返して、クラスタの階層構造を形成する。たとえばクラスタの数をｋ個と決めて、ｋ個のクラスタからなる階層で区切ることによって、ベクトルをｋ個のクラスタに分類することができる。
【０００５】
非階層的クラスタリングは、階層構造を用いないでベクトルを分類するクラスタリングである。代表的な非階層的クラスタリングとして、ｋ平均法（以下「k-means法」という）がある。k-means法は、ベクトル間の距離に応じてｋ個のクラスタに分類する。集合に含まれるベクトルの数をＮ個、クラスタの数をｋ個とするときのk-means法によるクラスタリングの手順を示す。
【０００６】
手順１では、Ｎ個のベクトルの中の任意のｋ個のベクトルを、ｋ個のクラスタのそれぞれの中心を示すベクトルの初期値とする。手順２では、Ｎ個のベクトルを、クラスタの中心のベクトルが最も近いクラスタに分類する。手順３では、各クラスタに含まれるベクトルの平均を新たなクラスタの中心とする。手順４では、クラスタの中心が変化しなくなるまで手順２および手順３を繰り返して、クラスタの中心が変化しなくなったところで終了する。
【０００７】
上述した階層的クラスタリングおよびk-means法による非階層的クラスタリングはいずれも、クラスタ数ｋを人手によって指定する必要がある。
【０００８】
クラスタ数ｋを人手によって指定しなくともよい従来の技術の例として、文書の自動分類方法がある。この文書の自動分類方法は、処理時間が許容時間内になるようにクラスタ数を決定し、文書の内容を表現する意味要素の強さに応じて、文書をベクトルで表現して分類する（たとえば特許文献１参照）。
【０００９】
【特許文献１】特開平１０−１７１８２３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来の技術の例では、クラスタ数を自動的に決定することができても、各クラスタに含まれるベクトル数に偏りが生じる可能性があるという問題がある。たとえば、階層的クラスタリングは、クラスタ数によっては、全ベクトル数の２％のベクトルを含むクラスタと全ベクトル数の４０％のベクトルを含むクラスタとに分類されるというように、各クラスタに含まれるベクトル数に偏りが生じる場合がある。
【００１１】
この階層的クラスタリングを情報の検索に利用して、検索結果を表示するとき、１つのクラスタに分類されるベクトルの数が多い場合は、類似する文書の数が多くなるので、所望の文書を見つけるのに多くの時間がかかる。あるいは表示される文書の数が少ない場合は、その中に所望の文書が含まれないことがあり得る。
【００１２】
この偏りを是正するためには、階層構造を図示したデンドログラムつまり樹形図を用いて、人手によって、ベクトル数の多いクラスタをより低い階層で分割し、あるいは、ベクトル数の少ないクラスタをより高い階層で併合する必要がある。
【００１３】
k-means法による非階層的クラスタリングは、手順１でのクラスタの中心の初期値の決め方によって、クラスタリングの結果に差が生じる。たとえば、クラスタの初期値の中心が特定の領域に集中し、かつ１つのクラスタの初期値の中心がその領域から離れている場合、階層的クラスタリングと同様に、各クラスタに含まれるベクトル数に偏りが生じる。この偏りを是正するためには、クラスタリングの結果を人手によって修正する必要がある。
【００１４】
本発明の目的は、各クラスタに含まれるベクトル数の偏りをより少なくすることができるクラスタリング装置、クラスタリング方法、プログラムおよび記録媒体を提供することである。
【課題を解決するための手段】
【００１５】
本発明は、多次元ベクトルを表す多次元ベクトルデータを入力する入力手段と、
入力手段によって入力された多次元ベクトルデータを、予め定める次元変換方式によって２次元ベクトルを表す２次元ベクトルデータに変換する次元変換手段と、
次元変換手段によって変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化手段と、
画像化手段によって変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出手段と、
領域抽出手段によって抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定手段と、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定手段によって範囲が決定されたクラスタに、各画素を分類する画素分類手段とを含むこと特徴とするクラスタリング装置である。
【００１６】
また本発明は、前記予め定める分類条件は、
画素に付与される度数が１つの正規分布のみを構成する度数の場合は、その度数が付与される画素を、その度数が構成する正規分布に対応するクラスタに分類し、
画素に付与される度数の一部が複数の正規分布を構成する度数の場合は、その度数が付与される画素を、その度数の一部が構成する複数の正規分布のうち、正規分布の標準偏差を平均で除算した評価値が最も大きい正規分布に対応するクラスタに分類し、
画素に付与される度数がいずれの正規分布をも構成しない度数の場合は、その度数が付与される画素を、その度数が付与される画素に最も近い範囲のクラスタのうち、前記評価値が最も大きいクラスタに分類することを特徴とする。
【００１７】
また本発明は、多次元ベクトルを表す多次元ベクトルデータを入力する入力ステップと、
入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する次元変換ステップと、
次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化ステップと、
画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出ステップと、
領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定ステップと、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する画素分類ステップとを含むこと特徴とするクラスタリング方法である。
【００１８】
また本発明は、多次元ベクトルを表す多次元ベクトルデータを入力する入力ステップと、
入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する次元変換ステップと、
次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化ステップと、
画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出ステップと、
領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定ステップと、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する画素分類ステップとを、コンピュータに実行させるためのプログラムである。
また本発明は、前記プログラムを記録したコンピュータ読取可能な記録媒体である。
【発明の効果】
【００１９】
本発明によれば、入力手段によって、多次元ベクトルを表す多次元ベクトルデータが入力され、次元変換手段によって、入力手段によって入力された多次元ベクトルデータが、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換される。
【００２０】
そして、画像化手段によって、次元変換手段によって変換された２次元ベクトルデータが、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換され、領域抽出手段によって、画像化手段によって変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域が抽出される。
【００２１】
さらに、クラスタ範囲決定手段によって、領域抽出手段によって抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布が抽出され、抽出された正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲がクラスタの範囲として決定され、画素分類手段によって、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定手段によって範囲が決定されたクラスタに、各画素が分類される。
【００２２】
すなわち、画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができるので、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、画素をクラスタに分類することによって、各クラスタに含まれるベクトル数の偏りをより少なくすることができる。文書データを多次元ベクトルデータとして表して、検索に適用すれば、文書データをより速く検索することができる。
【００２３】
また本発明によれば、入力ステップでは、多次元ベクトルを表す多次元ベクトルデータを入力する。次元変換ステップでは、入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する。画像化ステップでは、次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する。
【００２４】
領域抽出ステップでは、画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する。クラスタ範囲決定ステップでは、領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定する。そして、画素分類ステップでは、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する。
【００２５】
すなわち、本発明に係るクラスタリング方法を適用すれば、画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができるので、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、画素をクラスタに分類することによって、各クラスタに含まれるベクトル数の偏りをより少なくすることができる。文書データを多次元ベクトルデータとして表して、検索に適用すれば、文書データをより速く検索することができる。
【００２６】
また本発明によれば、多次元ベクトルを表す多次元ベクトルデータを入力する入力ステップと、
入力ステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する次元変換ステップと、
次元変換ステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する画像化ステップと、
画像化ステップで変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する領域抽出ステップと、
領域抽出ステップで抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定するクラスタ範囲決定ステップと、
クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定ステップで範囲が決定されたクラスタに、各画素を分類する画素分類ステップを、コンピュータに実行せるためのプログラムとして提供することができる。
【００２７】
また本発明によれば、前記プログラムを記録したコンピュータ読取可能な記録媒体として提供することができる。
【発明を実施するための最良の形態】
【００２８】
図１は、本発明の実施の一形態であるクラスタリング自動化装置１の機能の構成を示すブロック図である。本発明に係るクラスタリング方法は、クラスタリング自動化装置１によって処理される。
【００２９】
クラスタリング装置であるクラスタリング自動化装置１は、多次元ベクトルデータ入力手段（以下、入力手段という）１０、次元縮退手段１１、画像化手段１２、領域抽出手段１３、クラスタ範囲決定手段１４およびクラスタ決定手段１５を含んで構成される。
【００３０】
クラスタリング自動化装置１は、たとえばコンピュータによって構成される。クラスタリング自動化装置１を構成するコンピュータは、キーボードおよびマウスなどの入力装置と、ディスプレイなどの表示装置あるいはプリンタなどの印刷装置を含む出力装置と、通信回線たとえばＬＡＮ（Local Area Network）を介して情報を送受信する通信装置と、半導体メモリあるいはハードディスク装置によって構成され、プログラムおよびデータを記憶する記憶装置と、記憶装置に記憶されるプログラムを実行して、入力装置、出力装置、および通信装置を制御する中央処理装置（Central Processing Unit：以下「ＣＰＵ」という）とを含む。プログラムは、クラスタリング自動化装置１を制御するためのプログラムであり、ＯＳ（Operating System）およびアプリケーションプログラムを含んでもよい。コンピュータは、一般的に知られているコンピュータでよく、詳細な説明は省略する。
【００３１】
入力手段１０は、多次元ベクトルデータ記憶装置２に記憶される多次元ベクトルデータを読み出して、クラスタリング自動化装置１に入力する。多次元ベクトルデータは、多次元ベクトルを表すデータである。多次元ベクトルは、たとえば文書データをその内容などによって多次元ベクトルとして表したものである。
【００３２】
多次元ベクトルデータ記憶装置２は、通信回線たとえばＬＡＮに接続される記憶装置であり、コンピュータに含まれる通信装置によって、多次元ベクトルデータ記憶装置２に記憶される情報を読み出すことができる。図１に示した構成では、多次元ベクトルデータ記憶装置２を、クラスタリング自動化装置１とは別の独立した装置として構成したが、多次元ベクトルデータ記憶装置２をクラスタリング自動化装置１に含めてもよい。
【００３３】
次元変換手段である次元縮退手段１１は、入力手段１０よって入力された多次元ベクトルデータを、予め定める次元変換方式によって、２次元ベクトルを表す２次元ベクトルデータに変換する。予め定める次元変換方式は、たとえば多次元尺度構成法（Multi-
Dimensional Scaling：以下「ＭＤＳ」と略す）を用いて変換する方式である。
【００３４】
ＭＤＳは、計量多次元尺度構成法（Metric MDS：以下「計量ＭＤＳ」という）および非計量多次元尺度構成法（Non-metric MDS：以下「非計量ＭＤＳ」という）に分類される。計量ＭＤＳは、対象間の距離データに基づいて対象を空間的に布置する方法であり、非計量ＭＤＳは、対象間の距離データあるいは距離データに対応する非類似度データに基づいて、対象を空間的に布置する方法である（たとえば齋藤堯幸、宿久洋著、「関連データの解析法」初版、共立出版株式会社、２００６年９月１０日、ｐ３７−ｐ１２３参照）。
【００３５】
計量ＭＤＳおよび非計量ＭＤＳのうちのいずれの方法も、対象を布置する空間の次元数を対象の次元数よりも少なくすることによって、ベクトル間の距離関係つまり類似度関係を可能な限り保持したまま次元を縮退することができる。距離に関しては、たとえばユークリッド距離を用いてもよい。次元を縮退する方法としては、ＭＤＳ以外にも、多次元ベクトルデータが示す多次元ベクトル間の距離関係を可能な限り保持したまま、より低次元のベクトルに次元を縮退する他の方法、たとえば主成分分析法を用いてもよい。
【００３６】
図２は、次元縮退手段１１によって変換された２次元ベクトルの位置を示すＸＹ座標系２１の一例を示す図である。２次元ベクトルデータが示す２次元ベクトルの位置をＸＹ座標における座標（ｘ，ｙ）で表す。「×」印の位置が、始点を座標（０，０）としたときの各２次元ベクトルの先端の位置を示す。
【００３７】
画像化手段１２は、次元縮退手段１１によって変換された２次元ベクトルデータを、２値画像データに変換する。２値画像データは、「０」および「１」のうちのいずれかの値をとる画素から構成される画像を表すデータである。画像化手段１２は、次に示す手順に従って、２次元ベクトルデータを２値画像データに変換する。
【００３８】
手順１では、２次元ベクトルデータが示す２次元ベクトルのＸＹ座標における位置を座標（ｘ，ｙ）とするとき、ｘの最大値Ｘｍａｘ、ｙの最大値Ｙｍａｘ、ｘの最小値Ｘｍｉｎ、およびｙの最小値Ｙｍｉｎを求め、さらにｘの範囲Ｌｘ＝Ｘｍａｘ−Ｘｍｉｎ、およびｙの範囲Ｌｙ＝Ｙｍａｘ−Ｙｍｉｎを求める。
【００３９】
手順２では、２値画像データが示す画像の解像度をｍ×ｎ、ｍおよびｎを自然数、２次元ベクトルデータが示す２次元ベクトルの数をＮとするとき、条件１および条件２を満たす最小のｍおよびｎを求める。条件１は、ｍ：ｎ＝（Ｌｘ＋１）：（Ｌｙ＋１）であり、条件２は、ｍ×ｎ≧Ｎである。条件１および条件２を満たすことによって、２次元ベクトルデータが示す２次元ベクトル間の距離関係つまり類似度関係を可能な限り保持したまま、２次元ベクトルデータを２値画像データに変換することができる。
【００４０】
手順３では、画素のＸＹ座標における位置を座標（Ｘ，Ｙ）とするとき、変換式Ｘ＝ｘ×ｍ／（Ｌｘ＋１）およびＹ＝ｙ×ｎ／（Ｌｙ＋１）によって、２次元ベクトルデータが示す２次元ベクトルの座標（ｘ，ｙ）を、画素の座標（Ｘ，Ｙ）に変換する。変換後、２次元ベクトルが変換された座標にある画素の値を「１」、２次元ベクトルが変換された座標にない画素の値を「０」とする。
【００４１】
手順１〜３によって、２次元ベクトルデータが示す２次元ベクトル間の距離関係つまり類似度関係を可能な限り保持したまま、２次元ベクトルデータを２値画像データに変換することができる。
【００４２】
図３は、画像化手段１２によって変換された画像２２の一例を示す図である。桝目の１つ１つの矩形が１つの画素２２１を表し、白色の矩形は画素値が「０」の画素であり、斜線を付した矩形は画素値が「１」の画素である。
【００４３】
図４は、画像化手段１２によって変換された画素のデータ構造３１の一例を示す図である。各画素は、ｉおよびｊを自然数とするとき、構造体型配列Ｇ［ｉ］［ｊ］のデータ構造で表され、各Ｇ［ｉ］［ｊ］は、画素値、クラスタ情報、ステータス情報および度数を含む。度数は、２次元ベクトルデータが２値画像データに変換に変換されたとき、各画素について、画素の座標（Ｘ，Ｙ）が同じになる２次元ベクトルの数であり、「分布度数」ともいう。たとえば、画素の位置が座標（１，１）である画素に変換される２次元ベクトルの数が４個であると、その画素の度数は「４」となる。クラスタ情報およびステータス情報については、後述する。
【００４４】
図４に示したデータ構造３１では、画素Ｇ［１］［１］の画素値は「１」であり、後述するステータス情報は「未処理」であり、度数は「４」である。同様に、画素Ｇ［２］［１］の画素値は「１」であり、ステータス情報は「未処理」であり、度数は「５」である。画素Ｇ［３］［１］の画素値は「１」であり、ステータス情報は「未処理」であり、度数は「７」である。画素Ｇ［ｍ］［ｎ］の画素値は「０」であり、ステータス情報は「未処理」であり、度数は「０」である。
【００４５】
図５は、領域抽出手段１３によって抽出された初期領域が示された画像２３の一例を示す図である。領域抽出手段１３は、画像化手段１２によって変換された２値画像データが示す画像を構成する画素のうち、画素値が「１」である画素の中から、隣接する画素同士を１つの領域として抽出し、抽出した領域を初期領域とする。隣接は、画素がＸ軸方向つまり図５に示した桝目の幅方向、またはＹ軸方向つまり図５に示した桝目の高さ方向に隣接することをいう。図５に示した画像２３には、４つの初期領域２３ａ〜２３ｄが示されている。初期領域２３ａは４つの画素によって構成され、初期領域２３ｂは１つの画素によって構成され、初期領域２３ｃは３つの画素によって構成され、初期領域２３ｄは２つの画素によって構成されている。
【００４６】
図６は、領域抽出手段１３による領域抽出処理後の画素のデータ構造３２の一例を示す図である。クラスタ情報は、初期領域を識別するための番号である。ステータス情報は、初期領域を抽出する際に用いる画素の状態を示す情報であり、「未処理」はまだいずれの初期領域としても抽出されていないことを示し、「処理済」はすでにいずれかの初期領域として抽出されたことを示す。
【００４７】
図６に示したデータ構造３２では、画素Ｇ［１］［１］のクラスタ情報は「１」であり、ステータス情報は「処理済」であり、度数は「４」である。同様に、画素Ｇ［２］［１］のクラスタ情報は「１」であり、ステータス情報は「処理済」であり、度数は「５」である。画素Ｇ［３］［１］のクラスタ情報は「１」であり、ステータス情報は「処理済」であり、度数は「７」である。画素Ｇ［ｍ］［ｎ］のクラスタ情報は「ｋ」であり、ステータス情報は「処理済」であり、度数は「２」である。
【００４８】
クラスタ範囲決定手段１４は、領域抽出手段１３によって抽出された各初期領域に含まれる画素の度数の分布に基づいて、クラスタの範囲を決定する。すなわち、次元縮退手段１１および画像化手段１０２は、隣接する画素を初期領域とすることによって、類似度の高いデータ同士を１つの領域とし、クラスタ範囲決定手段１４は、度数の分布に基づいてクラスタの範囲を決定することによって、さらに類似度の高いデータ同士を１つのクラスタに集約する。
【００４９】
領域抽出手段１３によって抽出された各初期領域に含まれる画素の度数の分布は、複数の正規分布である２次元正規分布が混合された２次元混合正規分布であるとみなすことができる。すなわち、各初期領域を構成する画素の度数の分布が、複数の山が形成される２次元混合正規分布であり、複数の山のうちの各山がそれぞれ１つの２次元正規分布と仮定して、２次元混合正規分布を構成する２次元正規分布を抽出することができる。
【００５０】
２次元混合正規分布から２次元正規分布を抽出する方法として、たとえばＥＭ（
Expectation Maximization）アルゴリズムを用いた方法がある。ＥＭアルゴリズムは、尤度の期待値を求めるＥステップ（Expectation Step）と、尤度の期待値を最大化するＭステップ（Maximization Step）とを交互に繰り返すことによって、確かではない情報を含む観測データから最尤推定を行うための反復アルゴリズムである（たとえば赤穂昭太郎著、「ＥＭアルゴリズムの幾何学」、情報処理Ｖｏｌ．３７、Ｎｏ．１、１９９６年参照）。
【００５１】
クラスタ範囲決定手段１４は、次に示す手順で２次元混合正規分布から２次元正規分布を抽出する。各初期領域の分布が２次元混合正規分布であり、各初期領域の各山が１つの２次元正規分布であると仮定して、ＥＭアルゴリズムを用いた手順の例を示す。
【００５２】
手順１では、各初期領域ｃの度数の分布について、ＥＭアルゴリズムを用いて２次元正規分布を抽出する。ここに、ｃは１〜Ｕの自然数であり、Ｕは初期領域の数である。手順２では、各初期領域ｃについて抽出された各２次元正規分布について、Ｘ軸方向の平均ｘｃｔ、Ｙ軸方向の平均ｙｃｔ、Ｘ軸方向の標準偏差σｘｃｔ、およびＹ軸方向の標準偏差σｙｃｔを算出する。ここに、ｔは１〜Ｒの自然数であり、Ｒは初期領域で抽出された２次元正規分布の数である。
【００５３】
手順３では、座標（ｘｃｔ，ｙｃｔ）を中心とし、Ｘ軸方向の半径をｐ×σｘｃｔとし、Ｙ軸方向の半径をｑ×σｙｃｔとする楕円内の範囲をクラスタの範囲として決定する。ここに、ｐおよびｑは、「３」以下の正の実数であり、ｐおよびｑを変化させることによって所望のクラスタの範囲とすることができる。たとえば、Ｘ軸方向の正規分布を考えるとき、ｐ＝１とすると、クラスタの範囲に６８．３％の画素を含めることができる。さらに、ｐ＝２とすると、９５．４％の画素を含めることができ、ｐ＝３とすると、９９．７％の画素を含めることができる。
【００５４】
図７は、クラスタ範囲決定手段１４によって抽出された２次元正規分布２４の一例を示す図である。２次元正規分布２４は、Ｙ＝Ｘ＋ａの直線２４１上での２次元正規分布であり、高さは各画素の度数２４２を示す。
【００５５】
図８は、クラスタ範囲決定手段１４によって抽出された２次元正規分布２５の一例を示す図である。２次元正規分布２５は、Ｘ軸方向の２次元正規分布である。範囲２５１は、クラスタのＸ軸方向の範囲であり、範囲２５１の長さは、Ｘ軸方向の半径がｐ×σｘｃｔの楕円のＸ軸方向の直径に相当する。
【００５６】
図９は、クラスタ範囲決定手段１４によるクラスタ範囲決定処理後の画素のデータ構造３３の一例を示す図である。クラスタ範囲決定手段１４によってクラスタの範囲が決定された後は、クラスタ情報は、クラスタを識別するための番号であり、各画素が入っているクラスタの範囲のクラスタの番号を示す。
【００５７】
図９に示したデータ構造３３では、画素Ｇ［１］［１］のクラスタ情報は「１」であり、画素Ｇ［２］［１］のクラスタ情報は「１」および「２」であり、画素Ｇ［３］［１］のクラスタ情報は「２」であり、画素Ｇ［ｍ］［ｎ］のクラスタ情報は「ｋ’」である。画素Ｇ［２］［１］は、クラスタ情報が「１」のクラスタの範囲と、クラスタ情報が「２」のクラスタの範囲に入っている。ステータス情報および度数は、図６に示したデータ構造３２と同じであり、重複を避けるために説明は省略する。
【００５８】
クラスタ決定手段１５は、画素が、クラスタ範囲決定手段１４によって決定されたクラスタの範囲内に入っているか否かによって、次に示す手順で画素を各クラスタに分類する。手順１では、各画素のクラスタ情報をチェックし、１つのクラスタの番号のみがある場合は、すなわち画素の度数が１つの正規分布のみを構成する度数の場合は、その画素をそのクラスタ情報が示す番号のクラスタに分類する。
【００５９】
手順２では、画素のクラスタ情報に、クラスタの番号がない場合は、すなわち、画素の度数がいずれの正規分布をも構成しない度数の場合は、その画素に最も距離が近いクラスタの範囲のクラスタに分類する。最も距離が近いクラスタが複数ある場合は、最も距離が近い複数のクラスタのうち、評価値Ｈの値が最大であるクラスタに分類する。評価値Ｈは、各クラスタに対応する２次正規分布のＸ軸方向の標準偏差とＹ軸方向の標準偏差との平均を、各２次正規分布のＸ軸方向の平均とＹ軸方向の平均との平均で除算した値であり、式Ｈ＝（（σｘｃｔ＋σｙｃｔ）／２）／（（ｘｃｔ＋ｙｃｔ）／２）＝（σｘｃｔ＋σｙｃｔ）／（ｘｃｔ＋ｙｃｔ）によって算出する。ここに、ｘｃｔはＸ軸方向の平均、ｙｃｔはＹ軸方向の平均、σｘｃｔはＸ軸方向の標準偏差、σｙｃｔはＹ軸方向の標準偏差である。
【００６０】
手順３では、画素のクラスタ情報に、複数のクラスタの番号がある場合は、すなわち、画素の度数の一部が複数の正規分布を構成する度数の場合は、その複数のクラスタのうち、評価値Ｈが最大であるクラスタに画素を分類する。
【００６１】
図１０は、クラスタ決定手段１５によって画素がクラスタに分類された画像２６の一例を示す図である。画像２６には、３つのクラスタ２６ａ〜２６ｃが示されている。
【００６２】
クラスタ決定手段１５は、評価値Ｈを用いて画素を分類するので、いずれのクラスタの範囲にも入らない画素および複数のクラスタの範囲に入る画素を、度数がより小さく分散の大きい正規分布のクラスタに分類することができる。すなわち、画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができるので、山の高さがより低くかつ広がりがより広い正規分布のクラスタに分類されるベクトル数を増加することができ、各クラスタのベクトル数の偏りをより低減することができる。
【００６３】
このように、入力手段１０によって、多次元ベクトルを表す多次元ベクトルデータが入力され、次元縮退手段１１によって、入力手段１０によって入力された多次元ベクトルデータが、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換される。
【００６４】
そして、画像化手段１２によって、次元縮退手段１１によって変換された２次元ベクトルデータが、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換され、領域抽出手段１３によって、画像化手段１２によって変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される初期領域が抽出される。
【００６５】
さらに、クラスタ範囲決定手段１４によって、領域抽出手段１３によって抽出された各初期領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布が抽出され、抽出された正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲がクラスタの範囲として決定され、クラスタ決定手段１５によって、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、クラスタ範囲決定手段１４によって範囲が決定されたクラスタに、各画素が分類される。
【００６６】
すなわち、画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができるので、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、画素をクラスタに分類することによって、各クラスタに含まれるベクトル数の偏りをより少なくすることができる。文書データを多次元ベクトルデータとして表して、検索に適用すれば、文書データをより速く検索することができる。
【００６７】
さらに、前記予め定める分類条件は、画素に付与される度数が１つの正規分布のみを構成する度数の場合は、その度数が付与される画素を、その度数が構成する正規分布に対応するクラスタに分類するし、画素に付与される度数の一部が複数の正規分布を構成する度数の場合は、その度数が付与される画素を、その度数の一部が構成する複数の正規分布のうち、正規分布の標準偏差を平均で除算した評価値が最も大きい正規分布に対応するクラスタに分類し、画素に付与される度数がいずれの正規分布をも構成しない度数の場合は、その度数が付与される画素を、その度数が付与される画素に最も近い範囲のクラスタのうち、前記評価値が最も大きいクラスタに分類することである。
【００６８】
したがって、正規分布の標準偏差を平均で除算した評価値を用いることによって、正規分布を構成しない度数の画素および複数の正規分布を構成する度数の画素を、度数がより少なく分散の大きいクラスタに分類することができ、各クラスタに含まれる画素数つまりベクトル数の偏りをより少なくすることができる。
【００６９】
図１１は、画像化手段１２が実行する画像化処理の処理手順を示すフローチャートである。次元縮退手段１１によって多次元ベクトルデータが２次元ベクトルデータに変換された後、ステップＡ１に移る。
【００７０】
ステップＡ１では、２次元ベクトルデータが示す２次元ベクトルのＸＹ座標における位置を座標（ｘ，ｙ）とするとき、ｘの最大値Ｘｍａｘ、ｙの最大値Ｙｍａｘ、ｘの最小値Ｘｍｉｎ、およびｙの最小値Ｙｍｉｎから、ｘの範囲Ｌｘ＝Ｘｍａｘ−Ｘｍｉｎ、およびｙの範囲Ｌｙ＝Ｙｍａｘ−Ｙｍｉｎを求める。ステップＡ２では、２値画像データが示す画像の解像度をｍ×ｎ、文書データ数つまり２次元ベクトルの数をＮとするとき、条件１および条件２を満たす最小のｍおよびｎを求める。条件１は、ｍ：ｎ＝（Ｌｘ＋１）：（Ｌｙ＋１）であり、条件２は、ｍ×ｎ≧Ｎである。ここに、ｍおよびｎは自然数である。
【００７１】
ステップＡ３では、２次元ベクトルデータが示す２次元ベクトルの位置を示す座標（ｘ，ｙ）を、式Ｘ＝ｘ×ｍ／（Ｌｘ＋１）、および式Ｙ＝ｙ×ｎ／（Ｌｙ＋１）によって、２値画像データが示す画像上の画素の座標（Ｘ，Ｙ）に変換する。変換後、２次元ベクトルデータが示す２次元ベクトルが対応している画素の値を「１」、２次元ベクトルデータが示す２次元ベクトルが対応していない画素の値を「０」として、画像化処理を終了する。ステップＡ１〜Ａ３は、画像化ステップである。
【００７２】
図１２は、領域抽出手段１３が実行する領域抽出処理の処理手順を示すフローチャートである。画像化手段１２が、図１１に示した画像化処理を終了すると、ステップＢ１に移る。
【００７３】
ステップＢ１では、各画素Ｇ［ｉ］［ｊ］について、画像化手段１２による画像化処理の結果に基づいて画素値を「０」または「１」とし、ステータス情報を初期値として「未処理」とし、座標（ｉ，ｊ）つまり構造体型配列Ｇ［ｉ］［ｊ］の初期値として、ｉ＝１，ｊ＝１とする。ステップＢ２では、ｉ＝ｉ＋１、ｊ＝１として順次画素をチェックする。ただし、ｉ＝１およびｊ＝１のときは、この処理をパスする。
【００７４】
ステップＢ３では、ｉ＝ｍ＋１であるか否かを判定する。ｉ＝ｍ＋１であると、ステップＢ１１に進み、ｉ＝ｍ＋１でないと、ステップＢ４に進む。ステップＢ４では、ステータス情報が「未処理」であるか否かを判定する。ステータス情報が未処理であると、ステップＢ５に進み、ステータス情報が未処理でないと、ステップＢ２に戻る。ステップＢ５では、ステータス情報を「処理済」とする。ステップＢ６では、画素値が「１」であるか否かを判定する。画素値が「１」であると、ステップＢ７に進み、画素値が「１」でないと、ステップＢ２に戻る。
【００７５】
ステップＢ７では、座標（ｉ，ｊ）の画素に隣接する画素について順次画素値が「１」か否かを調べる。ステップＢ８では、隣接する画素で画素値が「１」、かつステータス情報が「未処理」のものがあるか否かを判定する。隣接する画素で画素値が「１」、かつステータス情報が「未処理」のものがあると、ステップＢ９に進み、隣接する画素で画素値が「１」、かつステータス情報が「未処理」のものがないと、ステップＢ１３に進む。
【００７６】
ステップＢ９では、その隣接する画素へ移動する。すなわち座標（ｉ，ｊ）をその隣接する画素の座標にする。ステップＢ１０では、移動した画素のステータス情報を「処理済」として、ステップＢ７に戻る。ステップＢ１１では、ｉ＝１、ｊ＝ｊ＋１とする。ステップＢ１２では、ｊ＝ｎ＋１であるか否かを判定する。ｊ＝ｎ＋１であると、領域抽出処理を終了し、ｊ＝ｎ＋１でないと、ステップＢ２に戻る。
【００７７】
ステップＢ１３では、隣接する４方向をチェックしたか否かを判定する。隣接する４方向をチェックした場合は、ステップＢ１４に進み、隣接する４方向をチェックしない場合は、ステップＢ７に戻る。ステップＢ１４では、最初の移動元であるか否かを判定する。最初の移動元であると、ステップＢ１６に進み、最初の移動元でないと、ステップＢ１５に進む。最初の移動元か否かは、たとえばステップＢ９で、隣接する画素に移動するとき、移動前の画素の座標（ｉ，ｊ）を順次記憶しておき、ステップＢ１４で、最初の移動前の座標と同じであるか否かを判断する。
【００７８】
ステップＢ１５では、１つ前の移動元の画素に戻る。すなわち、画素の座標を１つ前に移動した移動前の画素の座標（ｉ，ｊ）に戻す。ステップＢ１６では、画素値が「１」である隣接する画素を１つの初期領域として決定して、ステップＢ２に戻る。ステップＢ１〜ステップＢ１６は、領域抽出ステップである。
【００７９】
図１３は、クラスタ範囲決定手段１４が実行するクラスタ範囲決定処理の処理手順を示すフローチャートである。領域抽出手段１３が、図１２に示した領域抽出処理を終了すると、ステップＣ１に移る。
【００８０】
ステップＣ１では、各初期領域ｃについて、ＥＭアルゴリズムを用いて、各初期領域の２次元混合正規分布からその分布を構成する２次元正規分布を求める。ここに、ｃは１〜Ｕの自然数であり、Ｕは初期領域の数である。ステップＣ２では、各初期領域ｃについて求められた各２次元正規分布の平均ｘｃｔおよびｙｃｔと、標準偏差σｘｃｔおよびσｙｃｔとを求める。ここに、ｔは、１〜Ｒの自然数であり、Ｒは各２次元混合正規分布から求められた２次元正規分布の数である。
【００８１】
ステップＣ３では、点（ｘｃｔ，ｙｃｔ）を中心とするＸ軸方向の半径ｐ×σｘｃｔ、およびＹ軸方向の半径ｐ×σｙｃｔの楕円範囲をクラスタの範囲として、クラスタ範囲決定処理を終了する。ステップＣ１〜ステップＣ３は、クラスタ範囲決定ステップである。
【００８２】
図１４は、クラスタ決定手段１５が実行するクラスタ決定処理の処理手順を示すフローチャートである。クラスタ範囲決定手段１４が、図１３に示したクラスタ範囲決定処理を終了すると、ステップＤ１に移る。
【００８３】
ステップＤ１では、対応するクラスタが１つであるか否かを判定する。クラスタ情報に１つのクラスタの番号のみがあると、対応するクラスタが１つであると判定して、ステップＤ６に進む。クラスタ情報にあるクラスタの番号が１つのみでないと、対応するクラスタが１つでないと判定して、ステップＤ２に進む。ステップＤ２では、対応するクラスタがないか否かを判定する。クラスタ情報にクラスタの番号がないと、対応するクラスタがないと判定して、ステップＤ３に進む。クラスタ情報にクラスタの番号があると、対応するクラスタがあると判定して、ステップＤ７に進む。
【００８４】
ステップＤ３では、最短距離のクラスタが１つであるか否かを判定する。最短距離のクラスタが１つであると、ステップＤ６に進み、最短距離のクラスタが１つでないと、ステップＤ４に進む。ステップＤ４では、その画素を、複数の最短距離のクラスタのうち、評価値Ｈが最大のクラスタに分類する。評価値Ｈは、式Ｈ＝（σｘｃｔ＋σｙｃｔ）／（ｘｃｔ＋ｙｃｔ）によって算出する。ここに、ｘｃｔはＸ軸方向の平均、ｙｃｔはＹ軸方向の平均、σｘｃｔはＸ軸方向の標準偏差、σｙｃｔはＹ軸方向の標準偏差である。
【００８５】
ステップＤ５では、すべての画素を分類したか否かを判定する。すべての画素を分類すると、クラスタ決定処理を終了し、すべての画素を分類していないと、ステップＤ１に戻り、次の画素について処理する。ステップＤ６では、その画素をそのクラスタに分類して、ステップＤ５に進む。ステップＤ７では、その画素を、対応する複数のクラスタのうち、評価値Ｈが最大のクラスタに分類して、ステップＤ５に進む。ステップＤ１〜ステップＤ７は、画素分類ステップである。
【００８６】
画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができる。評価値Ｈを用いて画素を分類するので、いずれのクラスタの範囲にも入らない画素および複数のクラスタの範囲に入る画素を、度数がより小さく分散の大きい正規分布のクラスタに分類することができる。したがって、山の高さがより低くかつ広がりがより広い正規分布のクラスタに分類されるベクトル数を増加することができ、各クラスタのベクトル数の偏りをより低減することができる。
このように、入力手段１０によって処理されるステップでは、多次元ベクトルを表す多次元ベクトルデータを入力する。次元縮退手段１１によって処理されるステップでは、入力手段１０によって処理されるステップで入力された多次元ベクトルデータを、予め定める次元変換条件に従って２次元ベクトルを表す２次元ベクトルデータに変換する。
【００８７】
図１１に示したフローチャートのステップＡ１〜ステップＡ３では、次元縮退手段１１によって処理されるステップで変換された２次元ベクトルデータを、対応する２次元ベクトルの有無を示す値で表され、かつ対応する２次元ベクトルの数を表す度数が付与される画素からなる画像を表す画像データに変換する。図１２に示したフローチャートのステップＢ１〜ステップＢ１６では、図１１に示したフローチャートのステップＡ１〜ステップＡ３で変換された画像データが示す画素のうち、対応する２次元ベクトルが有ることを示す値で表される画素の中から、隣接する画素によって構成される領域を抽出する。
【００８８】
図１３に示したフローチャートのステップＣ１〜ステップＣ３では、図１２に示したフローチャートのステップＢ１〜ステップＢ１６で抽出された各領域に含まれる画素に付与された度数の分布から、その分布を構成する正規分布を抽出し、抽出した正規分布ごとに、各正規分布の平均を中心とし、かつ標準偏差に基づいて決められる範囲をクラスタの範囲として決定する。そして、図１４に示したフローチャートのステップＤ１〜ステップＤ７では、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、図１３に示したフローチャートのステップＣ１〜ステップＣ３で範囲が決定されたクラスタに、各画素を分類する。
【００８９】
すなわち、本発明に係るクラスタリング方法を適用すれば、画素をクラスタに分類することによって、画素に対応する多次元ベクトルをクラスタに分類することができるので、クラスタに分類される画素の数を均一化するための予め定める分類条件に従って、画素をクラスタに分類することによって、各クラスタに含まれるベクトル数の偏りをより少なくすることができる。文書データを多次元ベクトルデータとして表して、検索に適用すれば、文書データをより速く検索することができる。
【００９０】
クラスタリング自動化装置１を制御するプログラムは、コンピュータに、本発明に係るクラスタリング方法の各ステップを実行させるためのプログラムでもある。したがって、本発明は、コンピュータにクラスタリング方法の各ステップを実行させるためのプログラムとして提供することができる。
【００９１】
上述した実施の形態では、プログラムは、コンピュータの記憶装置たとえば半導体メモリあるいはハードディスク装置などの記憶装置に記憶されているが、これらの記憶装置に限定されるものではなく、コンピュータで読取り可能な記録媒体に記録されていてもよい。記録媒体は、たとえば図示しない外部記憶装置としてプログラム読取装置を設け、そこに記録媒体を挿入することによって読取り可能な記録媒体であってもよいし、あるいは他の装置の記憶装置であってもよい。
【００９２】
いずれの記録媒体であっても、記憶されているプログラムがコンピュータからアクセスされて実行される構成であればよい。あるいはいずれの記録媒体であっても、プログラムが読み出され、読み出されたプログラムが、記憶装置のプログラム記憶エリアに記憶されて、そのプログラムが実行される構成であってもよい。さらに通信ネットワークを介して他の装置からダウンロードされてプログラム記憶エリアに記憶させてもよい。ダウンロード用のプログラムは、予めコンピュータの記憶装置に記憶しておくか、あるいは別な記録媒体からプログラム記憶エリアにインストールしておく。
【００９３】
本体と分離可能に構成される記録媒体は、たとえば磁気テープ／カセットテープなどのテープ系の記録媒体、フレキシブルディスク／ハードディスクなどの磁気ディスクもしくはＣＤ−ＲＯＭ（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）／フラッシュＲＯＭなどの半導体メモリを含む固定的にプログラムを担持する記録媒体であってもよい。したがって、本発明は、コンピュータにクラスタリング方法の各ステップを実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体として提供することができる。
【図面の簡単な説明】
【００９４】
【図１】本発明の実施の一形態であるクラスタリング自動化装置１の機能の構成を示すブロック図である。
【図２】次元縮退手段１１によって変換された２次元ベクトルの位置を示すＸＹ座標系２１の一例を示す図である。
【図３】画像化手段１２によって変換された画像２２の一例を示す図である。
【図４】画像化手段１２によって変換された画素のデータ構造３１の一例を示す図である。
【図５】領域抽出手段１３によって抽出された初期領域が示された画像２３の一例を示す図である。
【図６】領域抽出手段１３による領域抽出処理後の画素のデータ構造３２の一例を示す図である。
【図７】クラスタ範囲決定手段１４によって抽出された２次元正規分布２４の一例を示す図である。
【図８】クラスタ範囲決定手段１４によって抽出された２次元正規分布２５の一例を示す図である。
【図９】クラスタ範囲決定手段１４によるクラスタ範囲決定処理後の画素のデータ構造３３の一例を示す図である。
【図１０】クラスタ決定手段１５によって画素がクラスタに分類された画像２６の一例を示す図である。
【図１１】画像化手段１２が実行する画像化処理の処理手順を示すフローチャートである。
【図１２】領域抽出手段１３が実行する領域抽出処理の処理手順を示すフローチャートである。
【図１３】クラスタ範囲決定手段１４が実行するクラスタ範囲決定処理の処理手順を示すフローチャートである。
【図１４】クラスタ決定手段１５が実行するクラスタ決定処理の処理手順を示すフローチャートである。
【符号の説明】
【００９５】
１  クラスタリング自動化装置
１０  多次元ベクトルデータ入力手段
１１  次元縮退手段
１２  画像化手段
１３  領域抽出手段
１４  クラスタ範囲決定手段
１５  クラスタ決定手段
１６  多次元ベクトルデータ記憶手段
【図１】
2009048575.tif 000003
【図２】
2009048575.tif 000004
【図３】
2009048575.tif 000005
【図４】
2009048575.tif 000006
【図５】
2009048575.tif 000007
【図６】
2009048575.tif 000008
【図７】
2009048575.tif 000009
【図８】
2009048575.tif 000010
【図９】
2009048575.tif 000011
【図１０】
2009048575.tif 000012
【図１１】
2009048575.tif 000013
【図１２】
2009048575.tif 000014
【図１３】
2009048575.tif 000015
【図１４】
2009048575.tif 000016