(57)【特許請求の範囲】
【請求項１】
複数の異なる事例の各々についての複数の異なる観測項目の観測値から成る事例集合であって、各観測項目の観測値の集合を表す観測値集合を含む事例集合を初期事例集合として入力する入力手段と、
前記観測値集合を前記観測項目毎に配列にして格納する記憶手段と、
前記記憶手段に格納された前記配列を参照し、前記観測値集合における観測値の変動の減少が最大になるように、前記配列の要素を昇順に整列した後にｐ番目の要素で逐次二分割していくことにより前記初期事例集合を階層的にクラスタリングする演算手段を備え、
前記変動は、ｔ（Ｘ（ｉ）［１，ｎ］）であって、
【数１】
0004004584.tif 000039
の式にしたがって、前記演算手段により計算され、
（ここで、Ｘ（ｉ）［１，ｎ］は、観測項目ｉの観測値集合）
前記変動の減少は、ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）であって、
ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）＝ｔ（Ｘ（ｉ）［１，ｎ］−ｔ（Ｘ（ｉ）［１，ｐ］）−ｔ（Ｘ（ｉ）［ｐ＋１，ｎ］）
の式にしたがって、前記演算手段により計算されることを特徴とするクラスタリング装置。
【請求項２】
請求項１において、前記記憶手段は、
前記観測値が０でない観測項目と当該観測項目の観測値とから成る事例集合を記憶することを特徴とするクラスタリング装置。
【請求項３】
請求項１において、前記演算手段は、
前記観測項目を、前記観測値集合における観測値の変動が大きい順に並べ替えた後に、並び替えた観測項目の１番から逐次二分割していき、前記変動の減少の最大値を求め、観測項目iの当該最大値が、観測項目i+1の変動以上であれば、観測項目i+1から先の観測項目の逐次二分割を行わないことを特徴とするクラスタリング装置。
【請求項４】
請求項１において、前記演算手段は、
前記観測値集合を同じ観測値をもつ部分集合に分割し、前記配列を当該部分集合単位で逐次二分割していくことを特徴とするクラスタリング装置。
【請求項５】
入力手段と記憶手段と演算手段を用いたクラスタリング方法であって、
前記入力手段が、複数の異なる事例の各々についての複数の異なる観測項目の観測値から成る事例集合であって、各観測項目の観測値の集合を表す観測値集合を含む事例集合を初期事例集合として入力するステップと、
前記記憶手段が、前記観測値集合を前記観測項目毎に配列にして格納するステップと、
前記演算手段が、前記記憶手段に格納された前記配列を参照し、前記観測値集合における観測値の変動の減少が最大になるように、前記配列の要素を昇順に整列した後にｐ番目の要素で逐次二分割していくことにより前記初期事例集合を階層的にクラスタリングするステップを含み、
前記変動は、ｔ（Ｘ（ｉ）［１，ｎ］）であって、
【数２】
0004004584.tif 000040
の式にしたがって、前記演算手段により計算され、
（ここで、Ｘ（ｉ）［１，ｎ］は、観測項目ｉの観測値集合）
前記変動の減少は、ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）であって、
ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）＝ｔ（Ｘ（ｉ）［１，ｎ］−ｔ（Ｘ（ｉ）［１，ｐ］）−ｔ（Ｘ（ｉ）［ｐ＋１，ｎ］）
の式にしたがって、前記演算手段により計算されることを特徴とするクラスタリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層分類法に属するクラスタリング装置及び方法に関するものである。
【０００２】
更に詳述すると、本発明は、例えば音声認識処理あるいは情報検索処理などの情報処理に好適な、クラスタリング装置及び方法に関するものである。
【０００３】
【従来の技術】
クラスタリングは統計的な分類手法の一つであり、社会科学・生物学など分類を必要とする研究で広く利用されている。一方、産業上でも音声認識装置，情報検索装置など情報処理分野を中心に広く利用されている。
【０００４】
クラスタリング手法にはさまざまなものがある。その概要は「統計学辞典」（竹中  啓，東洋経済新報社）などに詳しいが、大別すると以下のようになる。
【０００５】
第１は、分割分類法と呼ばれる手法であって、事例（分類対象を事例と呼ぶ）集合を重なりなく部分集合に分割する手法である。
【０００６】
第２は、階層分類法と呼ばれる手法であって、事例集合を上下階層に分類する手法である。
【０００７】
これらの分類法のうち、従来の代表的な階層分類法は、凝集型クラスタリング法である。この凝集型クラスタリング法において、入力に用いるデータは、各事例について、観測項目の観測値を測定した表である。例えば、次に示す表１は６個の事例それぞれについて二つの観測項目の観測値を測定した表である。
【０００８】
【表１】
0004004584.tif 000002
【０００９】
このような表１を使って、次のような手順で事例の階層的な分類を作成する。
【００１０】
１．観測値の表を基に事例間の類似度を計算する。この場合、 6Ｃ2 ＝１５個の距離が得られる。
【００１１】
２．以下の操作を、クラスタの数が１になるまで繰り返す。
【００１２】
３．距離が最小となる二つのクラスタ（もしくは事例）を合併して、新しいクラスタを作成する。
【００１３】
４．クラスタ（もしくは事例）間の距離を計算し直す。
【００１４】
【発明が解決しようとする課題】
しかしながら、上述した従来の代表的な階層分類法では、明らかに、事例間の距離の数が事例の数に二乗にほぼ比例して増加する。すなわち、事例の数をＮとした場合に、距離を保存する記憶領域（装置）の数がＮ2 に比例して増加する。
【００１５】
このため、事例の数が増えた場合には、距離を保存しておく記憶領域が不足してクラスタリングの実行が困難になる、という問題がある。また、最小の距離を求める計算の回数も多くなるため、多くの実行時間がかかるという問題も発生する。
【００１６】
このような問題を避けるために、従来は対象事例の数を制限したり、非階層手法と組み合わせる等の手法をとっていた。
【００１７】
よって本発明の目的は、上述の点に鑑み、従来から採られていた手法によることなく、数多くの事例を階層的に分類する能力を持つクラスタリング装置及び方法を提供することにある。
【００１８】
【課題を解決するための手段】
上記の目的を達成するために、本発明のクラスタリング装置は、複数の異なる事例の各々についての複数の異なる観測項目の観測値から成る事例集合であって、各観測項目の観測値の集合を表す観測値集合を含む事例集合を初期事例集合として入力する入力手段と、
前記観測値集合を前記観測項目毎に配列にして格納する記憶手段と、前記記憶手段に格納された前記配列を参照し、前記観測値集合における観測値の変動の減少が最大になるように、前記配列の要素を昇順に整列した後にｐ番目の要素で逐次二分割していくことにより前記初期事例集合を階層的にクラスタリングする演算手段を備え、
前記変動は、ｔ（Ｘ（ｉ）［１，ｎ］）であって、
【数３】
0004004584.tif 000003
の式にしたがって、前記演算手段により計算され、
（ここで、Ｘ（ｉ）［１，ｎ］は、観測項目ｉの観測値集合である。）
前記変動の減少は、ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）であって、
ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）＝ｔ（Ｘ（ｉ）［１，ｎ］−ｔ（Ｘ（ｉ）［１，ｐ］）−ｔ（Ｘ（ｉ）［ｐ＋１，ｎ］）
の式にしたがって、前記演算手段により計算されることを特徴とする。また、本発明のクラスタリング方法は、入力手段と記憶手段と演算手段を用いたクラスタリング方法であって、前記入力手段が、複数の異なる事例の各々についての複数の異なる観測項目の観測値から成る事例集合であって、各観測項目の観測値の集合を表す観測値集合を含む事例集合を初期事例集合として入力するステップと、前記記憶手段が、前記観測値集合を前記観測項目毎に配列にして格納するステップと、前記演算手段が、前記記憶手段に格納された前記配列を参照し、前記観測値集合における観測値の変動の減少が最大になるように、前記配列の要素を昇順に整列した後にｐ番目の要素で逐次二分割していくことにより前記初期事例集合を階層的にクラスタリングするステップを含み、
前記変動は、ｔ（Ｘ（ｉ）［１，ｎ］）であって、
【数４】
0004004584.tif 000004
の式にしたがって、前記演算手段により計算され、
（ここで、Ｘ（ｉ）［１，ｎ］は、観測項目ｉの観測値集合である。）
前記変動の減少は、ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）であって、
ｂ（Ｘ（ｉ）［１，ｎ］，ｐ）＝ｔ（Ｘ（ｉ）［１，ｎ］−ｔ（Ｘ（ｉ）［１，ｐ］）−ｔ（Ｘ（ｉ）［ｐ＋１，ｎ］）
の式にしたがって、前記演算手段により計算されることを特徴とする。
【００１９】
ここで、前記観測値が０でない観測項目と当該観測項目の観測値とから成る事例集合を記憶することにより、クラスタリングに必要とされる記憶領域を縮小することができる。
【００２０】
また、前記観測項目を、前記観測値集合における観測値の変動が大きい順に並べ替えた後に、並び替えた観測項目の１番から順番に最適分割点を求めることによって、前記配列を逐次二分割していくことにより、所要の演算回数を減少させることが可能である。同様に、前記観測値集合を同じ観測値をもつ部分集合に分割し、前記配列を当該部分集合単位で逐次二分割していくことによっても、演算回数を減少させることが可能である。
【００２１】
【発明の実施の形態】
実施の形態の概要
以下に詳述するクラスタリング方法では、事例の観測値の表を基に、事例集合の変動の減少を最大にするように事例集合を逐次に二分割していく手法を用いる。
【００２２】
ここで、観測値の表を圧縮して処理に必要な記憶領域を縮小することも可能である。
【００２３】
また、上記の手法において、観測項目を初期事例集合の変動の値の大きな順に整列することによって、計算回数を減少させることも可能である。
【００２４】
さらに、上記の手法において、観測値の異なる頻度の間を二分割することで計算回数を減少させることも可能である。
【００２５】
換言すると、本発明を適用したクラスタリング方法は、以下に列挙する▲１▼，▲２▼，▲３▼の特色を有する。
【００２６】
▲１▼  逐次二分割：
最初に事例集合を一つのクラスタとする。次に、これを逐次二分割する。すなわち、従来の凝集型手法が事例を併合しながら最終的に一つのクラスタを作成するのと逆の手法を採る。
【００２７】
▲２▼  距離の不使用：
事例間の距離を使わない。本発明を適用したクラスタリング方法では、事例の観測値のデータに基づいて、事例のクラスタリングを行なう。いま、事例の数をＮ，観測項目の数をＭとした場合、必要とする記憶領域の大きさはＮ×Ｍに比例する。一般のクラスタリング問題では、Ｍは小さな定数とみなすことができるため、Ｎに比例することになる。
【００２８】
このため、従来より必要とする記憶領域が大幅に減少し、これに伴って処理に要する時間も大きく減少する。
【００２９】
▲３▼  クラスタの特徴を説明可能：
本発明を適用したクラスタリング方法を実行して得られる階層は、二分木である。この二分木の根ノードは、全事例集合をカバーする最大のクラスタとなっている。葉ノードには、事例集合が格納されている。内部の各ノードは観測項目に対応しており、ここから二つの枝が下方に出ている。各事例は、ノードに対応する観測項目の観測値が閾値を超えていれば左の枝の下に分類され、そうでなければ右の枝の下に分類されている。
【００３０】
この特色によって、事例集合があるクラスタに分類された理由を、二分木をルートからその事例までたどることで知ることができる。すなわち、途上に出現する観測項目の頻度の大小の形で知ることができる。このような特色は従来の凝集型クラスタリング手法にはなく、本発明を適用したクラスタリング方法に独自の特色である。
【００３１】
以下に、かかるクラスタリング方法を具体的に説明していく。
【００３２】
実施の形態１
まず、本クラスタリング方法の処理に必要となる入力データの構成、ならびに、本クラスタリング方法の処理に用いる語句や数式について説明する。
【００３３】
（１）事例集合について
本クラスタリング方法を実行するためのクラスタリング装置（図１参照）へ入力するデータは、事例の集合を表わすデータである。ここで、事例は複数の観測項目の観測値からなる。また、観測値は数値である。
【００３４】
従来の技術の欄で示した表１は、事例集合の例を示す。この表１には事例が６個あり、それぞれａからｆまでの名称を与えている。また、観測項目は２個あり、それぞれ番号１，２を与えている。
【００３５】
以下、この表を初期事例集合としてクラスタリング装置（後に、図１を参照して詳述する）に入力し、本クラスタリング方法を実行させる。
【００３６】
（２）配列型メモリについて
本文での配列の要素の参照の仕方を二通り規定する。
【００３７】
配列型メモリＡのｊ番目の要素をＡ［ｊ］で参照する。一つの要素の参照である。配列は要素の集合であるため、以下では配列と集合を同じ意味で使う。
【００３８】
配列Ａのｓ番目の要素からｅ番目（ｓ≦ｅ）までの要素をＡ［ｓ，ｅ］で参照する。すなわち、部分集合の参照である。
【００３９】
配列Ａの
【００４０】
【外１】
0004004584.tif 000005
【００４１】
で表す。
【００４２】
配列Ａ［ｓ，ｅ］の要素の数を｜Ａ［ｓ，ｅ］｜で表す。
【００４３】
（３）観測値集合について
事例集合の観測項目ｉがｎ個の観測値を持つとする。この観測値の集合をｎ次元の配列（メモリ）に格納する。この配列をＸ(i) で表す。上の添字（ｉ）はこの配列が項目（ｉ）のものであることを示している。
【００４４】
前節の約束に従うと観測項目ｉの全観測値はＸ(i) ［１，ｎ］となる。
【００４５】
また、表１の場合
【００４６】
【外２】
0004004584.tif 000006
【００４７】
である。
【００４８】
（４）観測値集合の変動について
観測値集合Ｘ(i) ［１，ｎ］が与えられたとする。この観測値集合の変動は次式で計算する。
【００４９】
【数１】
0004004584.tif 000007
【００５０】
観測値集合が平均値の周りに集まっていれば変動は小さくなる。すなわち、変動は観測値集合のまとまり具合の指標である。
【００５１】
例えば、表１の観測項目１，２の変動を計算すると、次のようになる。まず、観測項目１については
ｔ（Ｘ(1) ［１，６］）＝（１−２）2 ×２＋（２−２）2 ×２＋（３−２）2 ×２＝４である。
【００５２】
一方、観測項目２の観測値の平均値は２であり、ｔ（Ｘ(2) ［１，６］）＝（１−２）2 ×３＋（３−２）2 ×３＝６となる。すなわち、観測項目２の観測値集合の方が、まとまりが悪いことが分かる。
【００５３】
（５）観測値集合の二分割について
観測値集合Ｘ(i) ［１，ｎ］が与えられたとする。この配列をｐ番目の要素で二分割するとは、次の操作を指す。
【００５４】
まず、Ｘ(i) ［１，ｎ］の要素を小さい順に並べ直す。すなわち、配列Ｘ(i) ［１，ｎ］を昇順に整列する。
【００５５】
次にＸ(i) ［１，ｎ］をＸ(i) ［１，ｐ］とＸ(i) ［ｐ＋１，ｎ］の二つの部分集合に分割する（１≦ｐ＜ｎ）。
【００５６】
例えば、Ｘ(1) ［１，６］＝｛１，１，２，２，３，３｝の二番目の要素による二分割の結果、Ｘ(1) ［１，２］＝｛１，１｝，Ｘ(1) ［３，６］＝｛２，２，３，３｝を得る。
【００５７】
またＸ(2) ［１，６］＝｛１，１，１，３，３，３｝の三番目の要素による二分割の結果、Ｘ(2) ［１，３］＝｛１，１，１｝，Ｘ(2) ［４，６］＝｛３，３，３｝を得る（要素を昇順に整列していることに注意）。
【００５８】
（６）変動の減少について
観測値集合Ｘ(i) ［１，ｎ］を、Ｘ(i) ［１，ｐ］とＸ(i) ［ｐ＋１，ｎ］に二分割する。この結果に対して、ｔ（Ｘ(i) ［１，ｎ］）（分割前の観測値集合の変動），ｔ（Ｘ(i) ［１，ｐ］）（分割した部分集合１の変動），ｔ（Ｘ(i) ［ｐ＋１，ｎ］）（分割した部分集合２の変動）を計算できる。
【００５９】
これらを使って、ｐによる二分割で発生する変動減少ｂ（Ｘ(i) ［１，ｎ］，ｐ）を次式で計算できる。
【００６０】
【数２】
0004004584.tif 000008
【００６１】
変動の減少が大きいほど、分割で得られた二つの部分集合のまとまりが良くなったことを示す。
【００６２】
（７）変動減少計算法について
観測値集合Ｘ(i) ［１，ｎ］のすべての可能な二分割の変動減少ｂ（Ｘ(i) ［１，ｎ］，ｐ）（１≦ｐ＜ｎ）を効率的に求める手法を示す。
【００６３】
式（２）は集合の全変動から、その部分集合の変動を引いたものである。統計学によれば（例えば柳井晴夫ほか「多変量解析ハンドブック」現代数学社１７ページ）、これは部分集合間の変動に一致する。すなわち、
【００６４】
【数３】
0004004584.tif 000009
【００６５】
である。
【００６６】
式（３）の中の
【００６７】
【外３】
0004004584.tif 000010
【００６８】
であり、最初に一度計算しておけば良い。また、
【００６９】
【外４】
0004004584.tif 000011
【００７０】
は以下に示す漸化式を使って効率的に計算することができる。尚、観測項目ｉは明らかなので、肩の添字（ｉ）は省略した。
【００７１】
【数４】
0004004584.tif 000012
【００７２】
次に、図１を参照して、本クラスタリング方法を実行するためのハードウェア構成を説明する。図１において、２は入力装置であり、初期事例集合を入力する。４は演算装置であり、図２に示す処理手順に従って、本クラスタリング方法を実行する。６はＲＯＭであり、図２に示したフローチャートをプログラムの形態で記憶してある。８はＲＡＭであり、上記の配列型メモリのほか、ワークエリアとして使用される。１０は演算結果を出力するための出力装置である。
【００７３】
次に、図２に示すフローチャートを参照して、本クラスタリング方法における処理ステップを説明する。
【００７４】
（１）ステップＳ１（初期事例集合の入力処理）について
ここでは、最初の入力データとして、表１に例示した初期事例集合を入力する。
【００７５】
（２）ステップＳ２（終了条件の確認処理）について
このステップには事例の集合を入力する。最初は、ステップＳ１を介して初期事例集合、すなわち表１を入力する。このステップＳ２の処理には以下の通り、ステップＳ２ＡとステップＳ２Ｂが含まれる。
【００７６】
初期事例集合の事例数があらかじめ規定している数（Ｋで表す。ここではＫ＝２とする）以下でなければ（ステップＳ２Ａ）、次のステップＳ２Ｂに進む。
【００７７】
次に、初期事例集合の各事例間で観測値が一致しないものが含まれる場合には（ステップＳ２Ｂ）、次のステップＳ３に進む。
【００７８】
ここでは既に述べた通り、初期事例集合（表１）には事例が６個ある。また表１には観測値が一致しないものが含まれるため、次の処理ステップＳ３に進む。
【００７９】
処理ステップＳ３には、入力された事例集合を渡す。
【００８０】
なお、初期事例集合があらかじめ規定している数Ｋ以下である場合、または、初期事例集合の各事例間で各観測値がすべて一致する場合、すなわち初期事例集合がこれ以上分割できない場合もありえるが、この場合には、すべての処理を終了する。
【００８１】
（３）ステップＳ３（最適観測項目の選択処理）について
受け取る事例数をｎとする。すなわち、すべての観測項目はｎ個の観測値を持つ。ここでは以下の処理を行なう。
【００８２】
１．各観測項目ｉを対象に以下の処理を行なう。
【００８３】
２．Ｘ(i) ［１，ｎ］の要素を値の小さい順に並べ直す。
【００８４】
３．Ｘ(i) ［１，ｎ］のすべての可能な二分割を行ない、そのときの変動減少ｂ（Ｘ(i) ［１，ｎ］，ｐ）を記録する（１≦ｐ＜ｎ）。
【００８５】
記録した結果から、最大の変動減少を与える観測項目ｉb とその分割点ｐb を求める。これらを最適観測項目、および最適分割点と呼ぶ。
【００８６】
さらに、
【００８７】
【外５】
0004004584.tif 000013
【００８８】
で計算する。
【００８９】
次段の「事例集合の分割処理ステップＳ４」には、
１．入力された事例集合
２．最適観測項目
３．分割閾値
を渡す。
【００９０】
表１を入力した場合の本処理ステップの動作は、次の通りである。ここで、観測項目１，２のすべての二分割で得られた変動減少は、以下の表２に示す通りである。
【００９１】
【表２】
0004004584.tif 000014
【００９２】
この表２の見方は、以下の通りである。観測項目２のｐ＝３番目の要素による二分割の変動減少は６．０となっている。その意味は、次の通りである。
【００９３】
すなわち、表１の観測項目２の観測値集合Ｘ(2) ［１，６］を昇順に整列し、｛１，１，１，３，３，３｝を作成する。この集合の３番目の要素を使って二分割を行なうと｛１，１，１｝と｛３，３，３｝が得られる。これより、変動ｂ（［Ｘ(2) ［１，６］，３］）＝６．０が得られることを示している。
【００９４】
また、表２よりこの場合が最大の変動減少となっていることがわかる。この結果、次の「事例集合の分割処理ステップＳ４」には、入力の６事例と観測項目番号２と分割閾値２（すなわち（１＋３）／２で計算した値）を渡す。
【００９５】
（４）ステップＳ４（事例集合の分割処理）について
前段のステップからは、事例集合，最適観測項目，分割閾値を受取り、以下の処理を行なう。
【００９６】
入力された各事例の最適観測項目の値が、分割閾値より大きければグループ１に分類する。そうでなければ、グループ２に分類する。この二つの事例集合を、次の処理ステップに渡す。
【００９７】
現在の事例集合は表１そのものである。これを、最適観測項目２とその分割閾値２を使って二つのグループに分割すると、次に示す表３および表４のようになる。これらの表３，表４を次の処理ステップに渡す。
【００９８】
【表３】
0004004584.tif 000015
【００９９】
【表４】
0004004584.tif 000016
【０１００】
（５）ステップＳ５（樹形図の作成処理）について
ここでは、以下の処理を実行する。
【０１０１】
１．ノードを作成し（二分割する前の事例集合に対応するノード）、その下に２本の枝を生成する（ステップＳ５Ａ）。左の枝の下には、グループ１の事例集合を対応させる。右の枝の下には、グループ２の事例集合を対応させる。
【０１０２】
２．グループ１に属する事例集合を使って、ステップＳ２からステップＳ５までの処理（図２で一点鎖線で囲った部分）を再帰的に実行する（ステップＳ５Ｂ）。
【０１０３】
３．グループ２に属する事例集合を使って、ステップＳ２からステップＳ５までの処理（図２で一点鎖線で囲った部分）を再帰的に実行する（ステップＳ５Ｃ）。
【０１０４】
ステップＳ２では、各再帰処理の対象となる事例数があらかじめ規定している数Ｋ以下である場合（ステップＳ２Ａ）、または、各再帰処理の対象となる各事例間で各観測値がすべて一致する場合（ステップＳ２Ｂ）には、これ以上の分割はできないので、その再帰処理を終了し、次のステップに進む。
【０１０５】
これを実例で説明する。表１の初期事例集合を使った場合には、ステップＳ５には表３および表４のデータが入力される。そうすると、図３に示す樹形図１が得られる。
【０１０６】
次に、ステップＳ２によって、表３の事例、すなわち｛ｂ，ｅ，ｆ｝をグループ１として使った再帰処理を開始する。
【０１０７】
この事例集合の最適観測項目は１、最適分割点は１となり、分割閾値は２となる。これを使って二分割すると｛ｅ，ｆ｝，｛ｂ｝が得られ、図４に示す樹形図２が得られる。
【０１０８】
次に、｛ｅ，ｆ｝をグループ１として再度再帰処理（ステップＳ５Ｂ）を開始するが、事例数が２≦２なのでこの再帰処理を終了し（ステップＳ２Ａ）、次のステップに進む。すなわち、｛ｂ｝をグループ２として次の再帰処理（ステップＳ５Ｃ）をするが、これも事例数が１≦２なのでこの再帰処理を終了する。以上で｛ｂ，ｅ，ｆ｝をグループ１として使った再帰処理（ステップＳ５Ｂ）が終了する。
【０１０９】
次に、｛ａ，ｃ，ｄ｝をグループ２とした再帰処理（ステップＳ５Ｃ）を行なう。今までと同様の処理の結果、図５に示す樹形図３が得られる。これで処理全体が停止する。
【０１１０】
（実施の形態１による効果）
以上説明した通り、本実施の形態１によれば、事例を分類する樹形図を得ることができる。しかも、事例集合から距離行列を求める操作は必要ない。先に述べたように、事例の数をＮとした場合の距離行列の大きさはＮ2 である。
【０１１１】
一方、本実施の形態１で必要とする記憶領域の大きさは、観測項目数をＭとしたとき、Ｎ×Ｍである。一般にＭ＜＜Ｎであるから、本実施の形態１のほうが、小さな記憶装置で済む。また、より小さな記憶装置の中の処理であるため、実行時間も高速となる。
【０１１２】
また、図５より各クラスタの特徴を明示的に知ることができる。例えば、事例｛ｅ，ｆ｝を持つクラスタは「観測項目２の頻度が２以上でかつ観測項目１の頻度が２以上」という特徴を持つことが分かる。
【０１１３】
以上が、実施の形態１についての説明である。
【０１１４】
その他の実施の形態について
上述した処理手順は、
（ａ）ある観測項目の観測値に同じ値がほとんど出現しない場合
（ｂ）観測項目の数が事例の数より小さい場合
に有効である。しかし、上記の性質を満さない観測値の場合には、以下に示す手法を用いた方が効率的である（表１は同じ値が出現しているので、以下に説明する手法で処理する方が効率的になる）。
【０１１５】
以下では、そのような例として文書集合のクラスタリング問題を考えた手法の実例を具体的に示す。
【０１１６】
本発明を適用して文書集合をクラスタリングする一つの方法は、次のようなものである。文書集合全体を対象として異なる単語を調査する。そして、これらの単語を観測項目とし、その出現頻度を観測値とする。例えば、あるニュース記事の集合に対してこのような表を作成すると、次に示す表５のようになる。
【０１１７】
【表５】
0004004584.tif 000017
【０１１８】
この表５から、次のことが判る。
【０１１９】
（イ）観測項目（単語）の数が膨大になり、表が巨大になる。
【０１２０】
（ロ）観測値（頻度）の大多数は０であり、次が１、その次が２…となる傾向がある。
【０１２１】
さらに、このような性質のデータの場合、先に示した「最適観測項目の選択処理ステップＳ３」で最大のｂ（Ｘ(i) ［１，ｎ］，ｐ）を与えるｉb とｐb を求めるのは、次のような問題がある。
【０１２２】
問題α．観測項目ｉの数が増えると、それだけ二分割の評価回数が増大して処理時間が増大する。
【０１２３】
問題β．ある観測項目ｉの
【０１２４】
【外６】
0004004584.tif 000018
【０１２５】
のに無駄が多い。例えば表５の観測項目「飛行機」の観測値（見えている範囲を対象とする。以下も同様）は
【０１２６】
【外７】
0004004584.tif 000019
【０１２７】
３回の二分割を要する。しかし必要なのは、０と１の間の二分割の評価だけである。０と０の間の二分割は最大変動減少を与えないため、この評価は無駄である。
【０１２８】
以下、表が膨大になる問題、および二分割で起きる二つの問題の解決手法を具体的に説明する。
【０１２９】
実施の形態２
上述した通り、言語データをもとに作成する事例の表（例えば表５）は巨大になる。しかし、頻度０の部分が大半を占めているので、大幅に圧縮することができる。
【０１３０】
すなわち、各事例（記事）で頻度が０でない単語と、その頻度だけを記憶装置に格納する（単語頻度リスト表と呼ぶ）。さらに、全単語（観測項目）のリストを作成しておく。次に示す表６は、表５に対応する単語頻度リスト表を示す。
【０１３１】
【表６】
0004004584.tif 000020
【０１３２】
この表６に対応する全単語リストは｛飛行機，大統領，条約｝となる。観測項目の番号は、この単語リストの順番に従うものとする。「大統領」は観測項目２となる。
【０１３３】
二分割はある単語に着目して行なう。そこで必要なのは、各記事でのその単語の出現頻度である。これは、単語頻度リスト表と全単語リストがあれば即座に求めることができる。すなわち、単語頻度リスト表と全単語リストを使えば膨大な表を使うことなく、表５と同等な処理を実現できる。
【０１３４】
（実施の形態２による効果）
以上説明した通り、本実施の形態によれば、膨大な表を使うこと、および、そのための処理が不要となる。
【０１３５】
実施の形態３
観測項目ｉの数が多くなると「最適観測項目の選択処理ステップＳ３」での二分割評価の数が増大し、処理時間が長くなる。ここでは、一部のｉについてのみ二分割を評価するだけで最適な観測項目と分割点を求める手法を示す。いわば、無駄な観測項目の評価をしない手法を示す。これには「変動」の性質を利用する。
【０１３６】
まず、変動減少に関する基本的な性質について述べる。ｎ個の要素からなる観測値集合Ｘ(i) ［１，ｎ］を考える。この観測値集合の変動はｔ（Ｘ(i) ［１，ｎ］）である。任意の点ｐでＸ(i) ［１，ｎ］を分割すると変動の減少ｂ（Ｘ(i) ［１，ｎ］，ｐ）が生ずる。これらの間には式（７）で示す関係があることが知られている（例えば前掲の「多変量解析ハンドブック」）。
【０１３７】
【数５】
0004004584.tif 000021
【０１３８】
この不等式は、集合を分割すれば非負の変動減少があること、変動減少の最大値は高々元の集合の持っている変動となることを示している。
【０１３９】
ここで初期事例集合Ｘ(i) ［１，Ｎ］，（１≦ｉ≦Ｍ），（ｎ≦Ｎ）が与えられたとする。この集合の観測項目を変動ｔ（Ｘ(i) ［１，Ｎ］）の大きな順に並び替える。すなわち、次の関係が成り立つようにしておく。
【０１４０】
【数６】
0004004584.tif 000022
【０１４１】
「最適観測項目の選択処理ステップＳ３」では、並び替えた観測項目の１番から順番に最適分割点を求めていく。ここで、次の規則が成り立つことが証明できる。
【０１４２】
観測値集合Ｘ(i) ［１，ｎ］を対象に二分割を行なった結果、
【０１４３】
【外８】
0004004584.tif 000023
【０１４４】
とする。もし
【０１４５】
【数７】
0004004584.tif 000024
【０１４６】
が成立するならば、ｉ＋１以降の観測項目は二分割の評価を行なう必要がない。そこまでで得られている最適観測項目と、その最適分割点が求める解である。
【０１４７】
【数８】
0004004584.tif 000025
【０１４８】
が成立することを示せば良い。
【０１４９】
式（７）が成立するので、
【０１５０】
【外９】
0004004584.tif 000026
【０１５１】
で
【０１５２】
【数９】
0004004584.tif 000027
【０１５３】
が成立する。観測項目は大きさの順に整列されているため
【０１５４】
【数１０】
0004004584.tif 000028
【０１５５】
である。もし
【０１５６】
【数１１】
0004004584.tif 000029
【０１５７】
が成立するなら、
【０１５８】
【数１２】
0004004584.tif 000030
【０１５９】
となって題意は証明された。
【０１６０】
これを、具体例で説明する。先に述べた「観測値集合の変動」における計算より、表１の観測項目１の変動は４であり、観測項目２の変動は６である。変動の大きい順に観測項目を並べ替えると２，１の順となる。
【０１６１】
次に、各観測項目の最適な二分割を計算する。まず、観測項目２の最適な二分割と、その変動減少を求める。これは、表２よりｐ＝３で６．０となることがわかる。ところで、この変動減少６．０は次の観測項目１の変動４より大きい。すなわち、上記ルールの条件が成立する。よって、観測項目１の二分割の評価をする必要はなくなり、計算を大幅に削減できる。
【０１６２】
以上の手法を使った「最適観測項目の選択処理ステップＳ３」の動作は下記の通りである。まず、初期事例集合の観測項目の変動を計算し、観測項目を変動の大きな順に整列しておくのが前提である。
【０１６３】
１．各観測項目ｉを対象に以下の処理を行なう。
【０１６４】
２．Ｘ(i) ［１，ｎ］の要素を値の小さい順に並べ直す。
【０１６５】
３．Ｘ(i) ［１，ｎ］のすべての可能な二分割を行ない、
【０１６６】
【外１０】
0004004584.tif 000031
【０１６７】
を記録する。
【０１６８】
４．もし
【０１６９】
【外１１】
0004004584.tif 000032
【０１７０】
ならば処理を終了する。
【０１７１】
解の中から、最大の変動減少を与える観測項目ｉb と、その最適分割点ｐb を求める。
【０１７２】
さらに、
【０１７３】
【外１２】
0004004584.tif 000033
【０１７４】
で計算する。
【０１７５】
次の処理ステップへ渡すデータは、先に述べた「最適観測項目の処理ステップＳ３」の場合と同じである。
【０１７６】
実施の形態４
ここでは、先に述べた二分割の問題βの解決手法を示す。
【０１７７】
先に述べたように、ある観測項目での二分割は異なる頻度間で実施すればよい。このためには、観測値集合をそのまま配列に格納するのでなく、頻度毎に格納すると便利である。以下、その実現手法を示す。
【０１７８】
ある観測項目ｉにｋ(i) 種類の頻度があるとする。これを、小さな順番に、配列ｆ(i) ［ｊ］，（１≦ｊ≦ｋ(i) ）に格納する。例えば表５から、単語「大統領（ｉ＝２）」には０と１と２の三種類の頻度がある。そこで、ｆ(2) ［１］＝０、ｆ(2) ［２］＝１、ｆ(2) ［３］＝２となる。
【０１７９】
次に、ｊ番目の頻度を持つ観測値集合を列挙したものを配列要素Ｅ(i) ［ｊ］に格納する。例えば、単語が「大統領」（ｉ＝２）の場合、１番目の頻度である０を持つ要素を列挙してＥ(2) ［１］＝｛０，０｝となる。同様に、Ｅ(2) ［２］＝｛１｝，Ｅ(2) ［３］＝｛２｝となる。以降では、単語ｉに着目していることが明らかなので、肩の添字(i) を省略する。
【０１８０】
Ｅ［ｊ］には観測値集合の列挙が入るので、Ｅは配列の配列となる。そこで、要素の参照手法が先に述べた「配列型メモリ」の場合と異なる。以下、変更点を述べる。
【０１８１】
（イ）｜Ｅ［ｊ］｜は配列Ｅ［ｊ］が格納している集合の要素数を示す。
【０１８２】
（ロ）Ｅ［ｓ，ｅ］は配列Ｅ［ｓ］からＥ［ｅ］までの各観測値集合の和集合を表す。
【０１８３】
（ハ）Ｅの要素の平均は下記の式に従って計算する。
【０１８４】
【数１３】
0004004584.tif 000034
【０１８５】
次に、頻度を使った二分割について説明する。観測項目ｉの全観測値集合をこれまでと同様Ｘ［１，ｎ］とする。これは、Ｅ［１，ｋ］に一致する。観測値集合Ｅ[1,k] のｐ番目の頻度による二分割とは、Ｅ［１，ｐ］とＥ［ｐ＋１，ｋ］に分割（１≦ｐ＜ｋ）することである。
【０１８６】
また、二分割によって発生する変動減少は次式のように計算できる。
【０１８７】
【数１４】
0004004584.tif 000035
【０１８８】
以上のデータ、計算式を基に、頻度間の二分割が可能となる。この場合の「最適観測項目の選択処理ステップＳ３」の処理は次のようになる。
【０１８９】
１．各観測項目ｉを対象に以下の処理を行なう。
【０１９０】
２．Ｘ(i) ［１，ｎ］データを配列メモリＥ(i) ［１，ｋ(i) ］に格納する。
【０１９１】
３．Ｅ(i) ［１，ｋ(i) ］のすべての可能な二分割を行ない、そのときの変動減少ｂ（Ｅ(i) ［１，ｋ(i) ］，ｐ）を記録する（１≦ｐ＜ｋ(i) ）。
【０１９２】
最大の変動減少を与えるｉb とｐb を求める。また
【０１９３】
【外１３】
0004004584.tif 000036
【０１９４】
で求める。次の処理に渡すデータは、上記ステップＳ３の場合と同じである。
【０１９５】
本手法では異なる頻度間で二分割を評価するため、頻度の種類が少なければ評価回数が大幅に減少する。最初に示した表１の場合も頻度の種類は少ない。例えば、この表の観測項目２では１と３の間の一回の評価で済む。一方、以前の手法であれば５回の評価が必要となる。
【０１９６】
なお、
【０１９７】
【外１４】
0004004584.tif 000037
【０１９８】
は以下の漸化式で効率的に計算できる。
【０１９９】
【数１５】
0004004584.tif 000038
【０２００】
（実施の形態３および４による効果）
実施の形態３における観測項目の整列は、初期事例集合の観測項目の変動が大きくばらついている場合に有効である。
【０２０１】
実施の形態４における頻度間の二分割は、同じ頻度が多数出現する場合に有効である。
【０２０２】
また、言語データは両方の性質をもっているため、両方の手法を適用することで大きく処理効率を改善できる。
【０２０３】
【発明の効果】
以上説明した通り、本発明によれば、従来から採られていた手法によることなく、数多くの事例を階層的に分類する能力を持つクラスタリング方法を実現することができる。その結果、本発明によれば、事例集合が与えられた場合に、これらを樹形図の形で高速にクラスタリングすることができる。
【０２０４】
すなわち、従来のクラスタリングの手法では、事例集合を一旦、事例間の距離行列に変換する必要があったが、本発明によればこの必要がない。このため、より小さなメモリでクラスタリングを行なうことができる。
【０２０５】
さらに、事例集合中の頻度の性質によって、本発明特有の処理効率を改善する手法を採ることができる。本発明による手法は、観測項目の数が大きいデータ、観測値の大半がゼロであるスパースなデータに対するクラスタリングに特に効果を発揮する。これに該当する典型的データとして、例えば応用上重要である言語データがある。
【図面の簡単な説明】
【図１】本発明を実施するためのハードウェア構成を示すブロック図である。
【図２】本発明の実施の形態の一例を示すフローチャートである。
【図３】図２による処理の結果として得られた樹形図の一例を示す説明図である。
【図４】図２による処理の結果として得られた樹形図の一例を示す説明図である。
【図５】図２による処理の結果として得られた樹形図の一例を示す説明図である。
【図１】
0004004584.tif 000041
【図２】
0004004584.tif 000042
【図３】
0004004584.tif 000043
【図４】
0004004584.tif 000044
【図５】
0004004584.tif 000045