(57)【特許請求の範囲】
【請求項１】
クラスター分析処理装置が行なうクラスター分析処理方法であって、
該クラスター分析処理装置のクラスター分析処理部が、
データの各々の間の類似度の行列から各行の類似度の最大値を探索し、類似度の最大値と、該最大値をとる列の番号を要素とする次候補記憶テーブルを作成し、該次候補記憶テーブルを探索し、前記類似度の行列内の最大値と、その最大値をとる行ＩＤ、列ＩＤを求める処理と、
新たなクラスターを生成し、前記類似度の行列に追加するとともに、前記類似度の行列から前記最大値をとる行ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる行ＩＤの値を列ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を列ＩＤとする全てのデータを前記類似度の行列から削除し、前記次候補記憶テーブルから前記最大値をとる行ＩＤ、列ＩＤの値を行ＩＤとするデータを削除する処理を有し、
これら処理を所定の終了条件が満たされるまで繰り返すことを特徴とするクラスター分析処理方法。
【請求項２】
コンピュータを、クラスター分析処理部を有するクラスター分析処理装置として動作させるクラスター分析処理プログラムを記録した記録媒体であって、
クラスター分析処理部が、
Ｎ個のデータの各々の間の類似度の行列から各行の類似度の最大値を探索し、類似度の最大値と、該最大値をとる列の番号を要素とする次候補記憶テーブルを作成し、該次候補記憶テーブルを探索し、前記類似度の行列内の最大値と、その最大値をとる行ＩＤ、列ＩＤを求める処理と、
新たなクラスターを生成し、前記類似度の行列に追加するとともに、前記類似度の行列から前記最大値をとる行ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる行ＩＤの値を列ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を列ＩＤとする全てのデータを前記類似度の行列から削除し、前記次候補記憶テーブルから前記最大値をとる行ＩＤ、列ＩＤの値を行ＩＤとするデータを削除する処理と
を所定の終了条件が満たされるまで繰り返す
ことを特徴とする、クラスター分析処理装置としてコンピュータを動作させるためのクラスター分析処理プログラムを記録した記録媒体。
【請求項３】
クラスター分析処理部が、
Ｎ個のデータの各々の間の類似度の行列から各行の類似度の最大値を探索し、類似度の最大値と、該最大値をとる列の番号を要素とする次候補記憶テーブルを作成し、該次候補記憶テーブルを探索し、前記類似度の行列内の最大値と、その最大値をとる行ＩＤ、列ＩＤを求める処理と、
新たなクラスターを生成し、前記類似度の行列に追加するとともに、前記類似度の行列から前記最大値をとる行ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を行ＩＤとする全てのデータ、前記最大値をとる行ＩＤの値を列ＩＤとする全てのデータ、前記最大値をとる列ＩＤの値を列ＩＤとする全てのデータを前記類似度の行列から削除し、前記次候補記憶テーブルから前記最大値をとる行ＩＤ、列ＩＤの値を行ＩＤとするデータを削除する処理と
を処理終了の条件が満たされるまで繰り返す
ことを特徴とするクラスター分析処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はクラスター分析処理方法および装置に関する。
【０００２】
【従来の技術】
近年、インターネットなどのコンピュータネットワークの普及により、不特定多数を対象に電子化された大量の情報がやりとりされている。これらの大量の情報の中から重要な情報を獲得するために、様々な分析手法が存在する。中でも、類似した情報同士を結び付け２分木を生成するクラスター分析方法は、情報の分類手法として数多く利用されている。
【０００３】
クラスター分析とは「異質なものの混ざりあっている対象（それは個体＝ものの場合もあるし、変数の場合もある）を、それらの間に何らかの意味で定義された類似度(similarity)を手がかりにして似たものを集め、いくつかの均質なものの集落（クラスター）を分類する方法を総称したもの」である（“多変量統計解析法”田中、脇本、現代数学社、１９８３初版）。
【０００４】
簡単にアルゴリズムを説明すると、個々のデータの数をＮとして、
１．データ集合Ｄ＝｛１，．．．，Ｎ｝の各データ間の類似度を計算
２．データ集合Ｄから最も類似したデータの組（ｉ，ｊ）を探索
３．ｉ，ｊから新たなクラスターｋを生成し、データ集合Ｄに加える
４．データ集合Ｄからｉ，ｊを削除する
５．終了条件を満たすまで、上記１，２，３，４を繰り返す
となる。終了条件とは、例えば「クラスターの数がｍ個まで」や、上記アルゴリズムの２で「類似度の値によって類似していると判断されなくなった場合」などがある。図９が、クラスター分析処理のイメージ図である。
【０００５】
実際にクラスター分析を行う対象としては、文書の自動分類などがある。新聞記事などの大量の文書を集めておき、類似した内容の文書同士を収集させ分類する方法として利用される。この場合、各文書の特徴を、要素が文書内に存在する単語と１対１に対応したベクトル（特徴ベクトル）として表現する。各単語に対応する要素は、文書に対するその単語の重要度（重み）を実数値化して表現する。単語の重みの計算方法は、その単語の出現頻度や文書集合全体における分布の割合や文字数の長さなどを利用して決定する手法（“Automatic Text Processing ”Gerard Salton, ADDISONWESLEY pub. 1989）が一般的である。こうして得られたベクトルを用いて各文書間の類似度（距離）を定義する。例えばユークリッド空間におけるベクトル同士のなす角(cosθ) などを利用する。これにより、類似した文書同士を同じクラスターに分けていき、類似度から閾値を利用して類似していないと判断したときに、処理を止める。この結果、いくつかの文書のまとまりを得ることができる。
【０００６】
【発明が解決しようとする課題】
この分析手法は、処理対象が多くなると、次のように非常に計算回数が多くなるという欠点がある。
【０００７】
（１）各データ間の類似度の計算にＮ×Ｎ（Ｎはデータ数）回かかる。
【０００８】
（２）最も類似しているデータの組の探索がＮ×Ｎ回かかる。
【０００９】
（３）２つのクラスターをひとつににまとめる新たなクラスターを生成する場合、残りの個々のデータ（最初は、Ｎ−２個）との類似度の計算を行う。
【００１０】
データｉとデータｊに対し（ｉ，ｊ）の類似度と（ｊ，ｉ）の類似度は等しい（対称性が成り立つ）とすると、（１）や（２）の計算回数は１／２になるが、オーダとしてはＮの２乗に変化はない。
【００１１】
本発明の目的は、計算回数のオーダを最小でＮ（データの個数）にするラスター分析処理方法、装置、およびクラスター分析処理プログラムを記録した記録媒体を提供することにある。
【００１２】
【課題を解決するための手段】
（２）の計算において、処理の途中結果を記録しておき、次の類似しているデータの組の探索時に利用することで、処理回数のオーダを最小でＮ（データの個数）にする方法を提案する。
【００１３】
データ間の類似度の値を要素とするＮ×Ｎの行列を生成する。この行列をＡ＝｛Ａｉｊ｝（ｉ，ｊ＝１，．．．，Ｎ）とする。行列Ａから最大値をとるデータの組（ｉmax ，ｊmax ）を見つけることを考える。
【００１４】
あらかじめ（実数値、列ＩＤ）を組とした、Ｎ個の一時的な領域を用意する（これを次候補記憶テーブルＴ＝｛Ｔｉ ：Ｔｉ ＝（値、列ＩＤ），ｉ＝１，．．．．Ｎ｝とする）。各Ｔｉには、行列Ａの行ｉにおける最大値とその列ＩＤを入れる。式で表すと、
0003675682.tif 000002
となる。次に、次候補記憶テーブルＴの要素Ｔｉ＝（値、列ＩＤ）の値が最大となるｉを見つける。こうして得られたｉとＴｉの列ＩＤが最大値をとるデータの組となる。
【００１５】
クラスター分析の場合、こうして得られたデータｉmax とｊmax から新しいクラスターｋを生成し、クラスターｋとそれ以外のデータ（個数Ｎ−２）との類似度を計算し直し、最大値を探索する。このとき次候補記憶テーブルＴを利用すると高速に探索できる。新たなクラスターｋ（行ＩＤはＮ＋１とする）を生成することにより行列Ａの中で変更されるのは行ｉmax ，ｊmax ，ｋと列ｉmax ，ｊmax ，ｋである。この変更に伴い次候補記憶テーブルＴの値の更新が確実に必要なのはｉmax ，ｊmax ，ｋであり、そのうち行内の最大値の探索が必要なのはｋのみとなる。また、次候補記憶テーブルＴの要素で、列ＩＤの値がｉmax かｊmax と同じであれば最大値の再計算をするが、それ以外は次候補記憶テーブルＴ内の要素の値がそのまま利用できる。すなわち、次候補記憶テーブルＴを用いることにより、行列Ａの最大値とそのデータの組の探索の計算回数のオーダーは最小時Ｎまで期待できる。すなわち、次候補記憶テーブルＴを探索するだけで最大値が見つかるとき、そのときの計算回数のオーダはＮになる。
【００１６】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１を参照すると、本発明の一実施形態のクラスター分析処理装置は、データ入力部１０１とデータ記憶部１０２とクラスター分析処理部１０３と表示部１０４で構成されている。
【００１８】
データ入力部１０１は処理を施したいデータを入力するためのものである。処理を施したいデータは、類似度（距離）が定義できるデータであればよく、〔従来の技術〕で説明した文書情報なども処理対象にできる。また、このとき各データ間の類似度を計算する関数も入力する。これは、装置側で扱える関数を提示し、装置利用者がその中から選択する方法もとれる。
【００１９】
データ記憶部１０２は、データ入力部１０１で入力された情報を記憶する。
【００２０】
クラスター分析処理部１０３は、データ入力部１０１で入力されたデータおよびデータ間の類似度計算用関数を用いてクラスター分析を行う。このとき、最も類似したデータの組の探索に、次候補記憶テーブルＴを用いて高速化を計っている。
【００２１】
表示部１０４は、クラスター分析の結果を表示する。
【００２２】
図２はクラスター分析処理部１０３の処理を示すフローチャートである。データ集合Ｄ（Ｎ個）の各データ間の類似度Ａ＝｛Ａｉｊ｝（ｉ，ｊ＝１，．．．，Ｎ）を計算する（ステップ２０１）。類似度の行列｛Ａｉｊ｝の各行ＩＤを探索し、類似度の最大値とそのときの列ＩＤを求め、次候補記憶テーブルＴ＝（Ｔ1，．．．，ＴN）：Ｔk（ｖａｌ，ｉｎｄｅｘ）に入れ、次候補記憶テーブルを探索し、類似度｛Ａｉｊ｝の最大値を探索する（ステップ２０２）。ｉmax，ｊmaxから新たなクラスターｋを生成し、データ集合Ｄに加える（ステップ２０４）。例えば集合Ｄ「りんご、きゅうり、なし」があったとすると、果物という観点から「りんご」と「なし」が近くて、これから新たなクラスター「果物」ができあがる。データ集合Ｄからｉmax，ｊmaxを削除する（ステップ２０５）。以上を、所定の終了条件が満たされるまで繰り返す（ステップ２０３）。
【００２３】
図３は図２中のステップ２０２の詳細を示すフローチャートである。なお、この処理に入る前に列ＩＤ番号Ｔｉ．ｉｎｄｅｘ＝−１に設定されている。まず類似度の行列Ａの行ＩＤ番号であるｉを初期化する（ステップ３０１）。行列Ａの最大値ｍａｘＶとその行ＩＤ番号ｍａｘＮｉ、列ＩＤ番号ｍａｘＮｉを初期化する（ステップ３０２）。行ＩＤ番号Ｔｉ．ｉｎｄｅｘの値を調べる（ステップ３０３，３０４），列ＩＤ番号Ｔｉ．ｉｎｄｅｘ＝−２であれば最大値を計算する必要がないのでステップ３０８に進み、行ＩＤ番号ｉを＋１する。列ＩＤ番号Ｔｉ．ｉｎｄｅｘが−１であれば、行ＩＤ番号がｉの類似度を求める必要があるので、類似度｛Ａｉｊ｝（ｌ＝１，．．．，Ｎ）の最大値を求め、その値をＴｉ．ｖａｌに保存し、そのときの列ＩＤ番号ｌをＴｉ．ｉｎｄｅｘに保存する（ステップ３０５）。ｍａｘＶとＴｉ．ｖａｌを比較し（ステップ３０６）、Ｔｉ．ｖａｌの方が大きければｍａｘＶ，ｍａｘＮｉ，ｍａｘＮｊにそれぞれＴｉ．ｖａｌ，ｉ，Ｔｉ．ｉｎｄｅｘを代入する（ステップ３０７）。行ＩＤ番号ｉを＋１する（ステップ３０８）。以上、ステップ３０３から３０８までの処理を行ＩＤ番号ｉがＮより大きくなるまで繰り返す（ステップ３０９）。
【００２４】
以上の処理により、次候補記憶テーブルＴ＝Ｔk（ｖａｌ，ｉｎｄｅｘ）、類似度の行列｛Ａｉｊ｝（ｉ，ｊ＝１〜Ｎ）内の最大値ｍａｘＶと、そのときの行ＩＤおよび列ＩＤ番号ｍａｘＮｉ，ｍａｘＮｊが求まる。
【００２５】
図４は図１中のステップ２０５の詳細を示すフローチャートである。
【００２６】
まず、ｉ行（ｉ＝１〜Ｎ）、ｍａｘＮｉ列の類似度ＡｉｍａｘＮｉ，ｉ行（ｉ＝１〜Ｎ）、ｍａｘＮｊ列の類似度ＡｉｍａｘＮｊ，ｍａｘＮｉ行、ｍａｘＮｊ列の類似度ＡｍａｘＮｉｍａｘＮｊをいずれも−１とする（ステップ４０１）。行ＩＤ番号ｉを初期化する（ステップ４０２）。行ＩＤ番号ｉがｍａｘＮｉまたはｍａｘＮｊに等しければ、行ＩＤ番号ｉの類似度の最大値は求めなくてもよいので、列ＩＤ番号Ｔｉ．ｉｎｄｅｘ＝−２とする（ステップ４０３〜４０５）。ｉがｍａｘＮｉ、ｍａｘＮｊでなく、Ｔｉ．ｉｎｄｅｘがｍａｘＮｉまたはｍａｘＮｊに等しい場合、Ｔｉ、ｉｎｄｅｘがｍａｘＮｉ、ｍａｘＮｊのデータが削除されるため、最大値を求める必要があるので、Ｔｉ．ｉｎｄｅｘ＝−１とする（ステップ４０６〜４０８）。行ＩＤ番号ｉを＋１する（ステップ４０９）。以上、ステップ４０３から４０９までの処理をｉがＮより大きくなるまで繰り返す（ステップ４１０）。
【００２７】
次に、類似度の行列｛Ａｉｊ｝に、Ａ（Ｎ＋１）ｊ，Ａｉ（Ｎ＋１）（ｉ，ｊ＝１〜Ｎ＋１）を追加し、Ｔ(N+1) ．ｉｎｄｅｘ＝−１とする（ステップ４１１）。最後に、データ数Ｎを＋１インクリメントする（ステップ４１２）。
【００２８】
次に、本実施形態を具体例により説明する。
【００２９】
クラスター分析を行うデータを、例えば１９９９年６月のＡ社が発行している新聞記事一ケ月分とする。記事間の類似度は、〔従来の技術〕で説明した文書の特徴ベクトル間の成す角(cosθ) を用いる。
【００３０】
図５は、類似度の行列Ａから次候補記憶テーブルＴを用いて最大値を探索する例である。「文書ｉと文書ｊの類似度と文書ｊと文書ｉの類似度は同じ」であるから、実際の類似度の行列Ａの半分を利用する。行列Ａからの最大値の探索が初めてであれば、次候補記憶テーブルＴの各要素には値が入っていないため、全ての各行において最大の類似度とその列ＩＤを記録する。このようにして次候補記憶テーブルＴに入れられた値を利用して上から順に最大値を探索する。図５の例では、最大値を取る行ＩＤ番号と列ＩＤ番号の組が（５，２）でそのときの値が０．４６であった。それらから、新たなクラスターを生成し、古いクラスター情報を削除した例が図５である。
【００３１】
図６では、まず、類似度の行列Ａの２と５の行と列それぞれの情報を空にし、さらに新たなクラスター情報をＮ＋１として追加する。また、それに合わせて、次候補記憶テーブルＴの内容も変更する。Ｔ2 とＴ5 の情報は削除し、ＴN+1 には行列Ａの行ＩＤ番号Ｎ＋１内の最大値とその列ＩＤ番号を記録する。それ以外に列ＩＤ番号の値が２あるいは５となる要素が存在すれば、その値も更新する。そのような要素がなければ、次の最大値の探索時の計算回数は［（次候補記憶テーブルＴの探索）＋（行Ｎ＋１の最大値探索）］となり、オーダーはＮとなる。
【００３２】
図７は、文書の自動分類書類における文書数に対する処理時間を従来方法と本発明の方法とで比較して示す図である。処理対象はアンケートの自由回答文で、文書間の類似度の計算には（従来の技術）で説明した特徴ベクトル間の成す角を利用した、従来方法では文書数に２乗で比例して計算時間が増えていくが、本方法ではほぼ線形に増えていくことが確認できる。
【００３３】
図８は本発明の他の実施形態のクラスター分析処理装置のブロック図である。
【００３４】
本実施形態のクラスター分析処理装置は入力装置５０１と記憶装置５０２、５０３と出力装置５０４と記録媒体５０５とデータ処理装置５０６で構成されている。入力装置５０１、記憶装置５０２、出力装置５０４は図１中のデータ入力部１０１、データ記憶部１０２、表示部１０４にそれぞれ対応する。記憶装置５０３はハードディスクである。記録媒体５０５は図２〜図４の処理からなるクラスター分析処理プログラムを記録したフロッピィ・ディスク、ＣＤ−ＲＯＭ、光磁気ディスクなどの記録媒体である。データ処理装置５０６は記録媒体５０５からクラスター分析処理プログラムを読み込んでこれを実行するＣＰＵである。
【００３５】
【発明の効果】
以上説明したように、本発明によれば、計算回数のオーダを最小でＮ（データの個数）にすることができる。
【図面の簡単な説明】
【図１】本発明の一実施形態のクラスター分析処理装置の構成図である。
【図２】クラスター分析処理部１０３の処理を示すフローチャートである。
【図３】図１中のステップ２０２の詳細を示すフローチャートである。
【図４】図１中のステップ２０５の詳細なフローチャートである。
【図５】類似度の行列Ａからの最大値の探索例を示す図である。
【図６】類似度の行列Ａからの最大値の探索例を示す図である。
【図７】文書の自動分類処理における文書数の処理時間の関係を従来方法と本発明で比較して示す図である。
【図８】本発明の他の実施形態のクラスター分析処理装置の構成図である。
【図９】クラスター分析のイメージ図である。
【符号の説明】
１０１    データ入力部
１０２    データ記憶部
１０３    クラスター分析部
１０４    表示部
２０１〜２０５、３０１〜３０９、４０１〜４１２    ステップ
５０１    入力装置
５０２、５０３    記憶装置
５０４    出力装置
５０５    記録媒体
５０６    データ処理装置
【図１】
0003675682.tif 000003
【図２】
0003675682.tif 000004
【図３】
0003675682.tif 000005
【図４】
0003675682.tif 000006
【図５】
0003675682.tif 000007
【図６】
0003675682.tif 000008
【図７】
0003675682.tif 000009
【図８】
0003675682.tif 000010
【図９】
0003675682.tif 000011