(57)【特許請求の範囲】
【請求項１】
様々な情報をその類似度により分類する情報クラスタリング装置であって、
情報を多次元ベクトルとして入力する情報入力手段と、
入力された情報ベクトルを自己組織化マップアルゴリズムにより、類似度の高い情報毎に２次元の自己組織化マップ上にマッピングするマッピング手段と、
生成された自己組織化マップ上の各ユニットが持つ参照ベクトルを利用し、２次元の自己組織化マップにおけるユニット間の距離を２次元の２つの軸の観点から算出し、自己組織化マップの各ユニット上に前記算出した距離をもつ距離マップを生成する距離マップ生成手段と、
前記距離マップ生成手段により作られた距離マップから、距離が閾値以上であるクラスタ境界となる位置を認識し、クラスタ境界が少し欠けている場合は、その前後の距離マップの状態からクラスタ境界を作り出して、クラスタ境界を閉包させたクラスタリングマップを生成するクラスタリングマップ生成手段と、
前記クラスタリングマップ上に作成されたクラスタ境界からクラスタ情報を取り出すクラスタ認識手段と、
取り出されたクラスタ情報を出力する出力手段と、
を有する情報クラスタリング装置。
【請求項２】
コンピュータを、様々な情報をその類似度により分離する情報クラスタリング装置として動作させる情報クラスタリングプログラムを記録したコンピュータ読取り可能な記録媒体であって、
情報を多次元ベクトルとして入力する情報入力処理と、
入力された情報ベクトルを自己組織化マップアルゴリズムにより、類似度の高い情報毎に２次元の自己組織化マップ上にマッピングするマッピング処理と、
生成された自己組織化マップ上の各ユニットが持つ参照ベクトルを利用し、２次元の自己組織化マップにおけるユニット間の距離を２次元の２つの軸の観点から算出し、自己組織化マップの各ユニット上に前記算出した距離をもつ距離マップを生成する距離マップ生成処理と、
前記距離マップ生成処理により作られた距離マップから、距離が閾値以上であるクラスタ境界となる位置を認識し、クラスタ境界が少し欠けている場合は、その前後の距離マップの状態からクラスタ境界を作り出して、クラスタ境界を閉包させたクラスタリングマップを生成するクラスタリングマップ生成処理と、
前記クラスタリングマップ上に生成されたクラスタ境界からクラスタ情報を取り出すクラスタ認識処理と、
取り出されたクラスタ情報を出力する処理と、
をコンピュータに実行させる情報クラスタリングプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ベクトルとして与えられている情報を、その類似度から分類する情報クラスタリング装置に関する。
【０００２】
【従来の技術】
情報のクラスタリングを行う装置として、k−mean 法やIsodata法の最近距離法に基づくアルゴリズム（長尾真、パターン情報処理、コロナ社、pp. 117-120,  1983）を用いたものがある。これらのアルゴリズムは、入力情報をn次元のベクトルとして扱い、情報間の類似度の差を、例えばそのユークリッド距離で表現し、その類似度からクラスタ分けを行う。
【０００３】
K−mean法は、クラスタ数Kを指定して、情報をK 個のクラスタに分類する方法である。最初にクラスタ数Kを指定し、K個のクラスタの中心となるベクトル（クラスタ中心）を与える。次に、すべての入力情報を最も距離の近いクラスタ中心を持つクラスタに分類する。そして、各クラスタにおいて、それに属する入力情報とクラスタ中心の距離を計算し、その平均をとり、それを新たなクラスタ中心とする。このクラスタ中心に対して、入力情報を再分類する。これを繰り返してクラスタリングを行う。
【０００４】
Isodata法は、最初にいくつかのパラメータを指定して、それにしたがって情報を分類する方法である。最初にクラスタ数の初期値、一つのクラスタの要素の数に関するパラメータ、クラスタの広がりに関するパラメータ、クラスタ間の距離に関するパラメータ、クラスタの統合を行う最大数を指定する。基本的には、K−mean 法と同様のクラスタリングを行う。クラスタリングの途中で、設定したパラメータ値にしたがって、小さなクラスタは統合したり、大きなクラスタは分割を行いながら進めていく。
【０００５】
【発明が解決しようとする課題】
K−mean法では、クラスタ数Kを指定する必要がある。このKが適切でない場合には情報の分類が有効に行うことができない。未知の分布を持つ情報をクラスタリングする場合、Kを適切に決定することは困難である。
【０００６】
Isodata法では、クラスタの大きさや個数を固定することなしにクラスタリングを行うことが可能である。しかし、いくつかのパラメータがクラスタリングの結果に大きく影響し、未知の分布を持つ情報をクラスタリングする場合には、パラメータを適切に決定することは困難である。
【０００７】
本発明の目的は、未知の分布を持つ入力情報を、煩雑なパラメータを設定することなしに、効率的に分類することのできる情報クラスタリング装置および情報クラスタリングプログラムを記録した記録媒体を提供することである。
【０００８】
【課題を解決するための手段】
本発明の情報クラスタリング装置は、情報を多次元ベクトルとして入力する情報入力手段と、入力された情報ベクトルを自己組織化マップ(SOM)上にその類似度の高い情報毎にマッピングするマッピング手段と、自己組織化マップから距離マップを生成する距離マップ生成手段と、距離マップからクラスタの境界をみつけ、クラスタリングマップを生成するクラスタリングマップ生成手段と、クラスタリングマップ上に作成されたクラスタの境界からクラスタ情報を取り出すクラスタ認識手段を有する。
【０００９】
情報入力手段により、分類する情報を多次元の情報ベクトルとしてシステムに入力する。入力された情報ベクトルと同じ次元のベクトル（参照ベクトル）を内部状態として持つユニットから構成されたマップを用意する。これがSOMとなる。マッピング手段により、自己組織化アルゴリズムを用いて、このSOM上のユニットの持つ参照ベクトルを、入力情報の分布を近似するように変化させていく。すべての情報ベクトルに対して、最も近い参照ベクトルを持つユニットを探索し、その位置に情報をマッピングする。結果的に、類似度の高い情報はマップ上で近い位置に配置される。
【００１０】
クラスタの違いを情報の分布が異なっているものとする。分布の違いはSOMを構成するユニットの持つ参照ベクトル間の差で表現できる。距離マップ生成手段により、ユニットの持つ参照ベクトルからユニットの隣同士の類似度の差を算出し、SOMのユニットとその値からなるマップを生成し、これを距離マップとする。クラスタリング生成手段により、距離マップからクラスタの境界をみつけ、クラスタ境界を記述したクラスタリングマップを生成する。距離マップ上では、類似度の差となる値を持つユニットが、クラスタの境界となるユニットである。クラスタ認識手段により、クラスタリングマップからクラスタ情報を取り出す。
【００１１】
ここで用いる自己組織化アルゴリズムは、初期パラメータに対してロバスト性が強いという性質を持っているので、従来のような煩雑なパラメータの設定が不要である。さらに、情報の分布をSOM上に近似し、クラスタリングを行うので、初期にクラスタ数を設定することなしに、クラスタリングを行うことができる。
【００１２】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１３】
図１を参照すると、本発明の一実施形態の情報クラスタリング装置は情報入力部１１とマッピング部１２と距離マップ生成部１３とクラスタリングマップ生成部１４とクラスタ認識部１５から構成されている。
【００１４】
情報入力部１１は情報を、n個の数値要素からなるベクトル
【００１５】
【外１】
0003712583.tif 000002
として入力する。ここで、ｉは情報の番号を表す。
【００１６】
マッピング部１２は、入力された情報（入力ベクトル）を自己組織化マップ上にその類似度の高い順にマッピング（配置）する。すなわち、図２に示すように、まず、ステップ２１は情報入力部１１から情報ベクトルを受け取る。ステップ２２に、ニューラルネットワークの一種である自己組織化マップ（Kohonen, T. :  Self−Organizing Maps, Springer−Verlag Berlin Heidelberg, 1995)を利用して、自己組織化アルゴリズムにより、情報の分布を近似するように自己組織化マップを生成する。ステップ２３にステップ２２で生成された自己組織化マップを距離マップ生成部１３に渡す。自己組織化マップは、図３に示すように、入力層３１と出力層３２から構成される。入力層３１は、入力ベクトルの次元の数であるn個のユニット３３から構成される。入力層３１は入力されたベクトルを出力層３２に渡す働きをする。出力層３２は、例えばe×f＝k個のユニット３４から構成される２次元のマップとする。出力層３２を構成するユニット３４は、それぞれ参照ベクトル
【００１７】
【外２】
0003712583.tif 000003
を持つ。参照ベクトルは入力ベクトルと同じ次元を持つ。
【００１８】
次に、自己組織化アルゴリズムを図４により説明する。
【００１９】
自己組織化アルゴリズムは、自己組織化マップの出力層３２の各ユニット３４の参照ベクトルを入力ベクトルに近づけていくことによって進められる。最終的には、入力情報の持つ分布を２次元の出力層３２に近似することになる。
【００２０】
まず、ステップ４０に、情報ベクトルを自己組織化マップの入力層３１に入力する。ステップ４１に、繰り返し回数tを０に初期化し、ステップ４２に入力ベクトルの数iを０に初期化する。ステップ４３に入力ベクトル
【００２１】
【外３】
0003712583.tif 000004
に最も近い参照ベクトルを持つユニットcを探索する。探索は
【００２２】
【数１】
0003712583.tif 000005
にしたがって行う。
【００２３】
すなわち、i番目の入力ベクトル
【００２４】
【外４】
0003712583.tif 000006
と出力層３２のj番目のユニットの参照ベクトル
【００２５】
【外５】
0003712583.tif 000007
の距離が最小となる出力層３２のユニットjをみつけ、それをユニットcとする。ここで、入力ベクトルと参照ベクトルの距離は、例えば
【００２６】
【数２】
0003712583.tif 000008
２のようなユークリッド距離で表現する。
【００２７】
次に、ステップ４４に、出力層３２のユニットcの近傍集合を形成する。この近傍集合は例えば、
【００２８】
【数３】
0003712583.tif 000009
で定義する。式（３）でdis（j, c)はユニットjとユニットcの距離を表し、ユニットcからの距離がr(t)より近いユニットjを集めたものを近傍集合とする。例えば、５１, ５２（図５）のようにとる。５１はユニットcを表し、５２は近傍集合を表す。ここでは近傍集合５２はユニットcを含み、２５個のユニットが含まれることとなる。
【００２９】
次に、ステップ４５に近傍集合５２に属するユニットの参照ベクトルを
【００３０】
【数４】
0003712583.tif 000010
にしたがって更新する。すなわち、近傍集合Nc(t) に属するユニットの参照ベクトルはその値を式（４）にしたがって更新し、それ以外のユニットの参照ベクトルは何もしない。ここで、距離r(t)と学習係数α(t)は、学習回数tに対して、一様に減少させる。以上のステップ４３から４５までの処理を繰り返し回数T、入力ベクトル数dだけ繰り返す（ステップ４６〜４９）。
【００３１】
最後に、ステップ５０に、ステップ４３と同様に各入力ベクトルに最も近い参照ベクトルを持つユニットを探索し、出力層３２にマッピングする。
【００３２】
距離マップ生成部１３は、自己組織化マップの出力層３２のユニットの参照ベクトルの値から距離マップを生成する。自己組織化マップの出力層３２のそれぞれの軸i, jについて、各ユニットに対する距離
【００３３】
【数５】
0003712583.tif 000011
を計算する。この値をマップi×jのマップ上に配置させ、３次元の距離マップ６１（図６）を生成する。出力層３２の各ユニットの参照ベクトルは、各ユニットの類似度が高ければ、距離dmij（式（５））が小さくなり、類似度が低い場合は大きくなる。距離マップ６１を作成すると、クラスタ間の境界に当たる部分が大きな値を持ち、クラスタ内は小さな値を持つこととなる。
【００３４】
クラスタリングマップ生成部１４は、距離マップ６１からクラスタリングマップを生成する。図７はクラスタリングマップを説明する図である。距離マップ６１に山の尾根だけを取り出して、それをクラスタリングの境界７２とし、クラスタリングマップ７１とする。クラスタの境界は、閉包となるように作成する。例えば、少し境界がかけている場合は、その前後の距離マップ６１の状態から境界を作り出す処理を行う。実際、距離マップ６１は、大きな山脈や小さな山脈があるので、閾値を設定して、その値以上であればクラスタ境界とする。
【００３５】
クラスタ認識部１５は、クラスタリングマップ７１からクラスタ境界を認識し、分類された入力情報の情報を取り出す。図８はクラス認識部１５を説明する図である。クラスタリングマップ７１の上に入力ベクトルを配置させた状態を表している。ユニット８１はクラスタの境界を示しており、８２は入力ベクトルを表している。８３はクラスタを表しており、図８では、入力ベクトルが４つのクラスタに分類されていることを示している。
【００３６】
図９は、クラスタリングマップ７１上に配置された入力ベクトルを、クラスタ毎に認識する実際の例を説明する図である。まず、入力ベクトルを一つ指定し、それが位置するユニット９１を求める。次に、そのユニットの上下左右９３を見て、それらのユニットに当たる入力ベクトルを探し、取り出す。次に、またユニットの上下左右９４を見て、それらのユニットに当たる入力ベクトルを取り出す。同様に、９６、９７と探していき、クラス内すべてのユニットの探索が終了すると、そのとき取り出された入力ベクトルが同じクラスタに属するものとなる。次に、また入力ベクトルを一つ指定して、同様の走査を行い、すべての入力ベクトルがどれかのクラスタに分類されたら処理を終了する。なお、９２（灰色の丸）はクラスタ境界を示している。
【００３７】
図１０を参照すると、本発明の他の実施形態の情報クラスタリング装置は、入力装置１０１と記憶装置１０２と出力装置１０３と記録媒体１０４とデータ処理装置１０５で構成されている。
【００３８】
入力装置１０１は情報を多次元ベクトルとして入力する。出力装置１０３はクラスタ情報を出力する。記録媒体１０４は以上説明した情報入力部１１からクラスタ認識部１５までの処理からなる情報クラスタリングプログラムを記録した、フロッピィ・ディスク、CD−ROM、光磁気ディスク等の記録媒体である。データ処理装置１０５はCPUを含み、記録媒体１０４から情報クラスタリングプログラムを読み込んで、これを実行する。
【００３９】
【発明の効果】
以上説明したように、本発明は、入力ベクトルを自己組織化マップにより、その分布を近似して、２次元マップ上に類似度が高い順に配置し、そこから距離マップとクラスタリングマップを生成し、クラスタを認識することにより、未知の分布を持つような入力情報の分類も、煩雑なパラメータを設定することなしに行うことができる効果がある。
【図面の簡単な説明】
【図１】本発明の一実施形態の情報クラスタリング装置の構成図である。
【図２】マッピング部１２の処理を示すフローチャートである。
【図３】自己組織化マップを示す図である。
【図４】自己組織化アルゴリズムの処理を示すフローチャートである。
【図５】ユニットcと近傍集合を示す図である。
【図６】距離マップを説明する図である。
【図７】クラスタリングマップを説明する図である。
【図８】クラスタを認識する方法を説明する図である。
【図９】クラスタを認識する方法を説明する図である。
【図１０】本発明の他の実施形態の情報クラスタリング装置の構成図である。
【符号の説明】
１１    情報入力部
１２    マッピング部
１３    距離マップ生成部
１４    クラスタリングマップ生成部
１５    クラスタ認識部
２１,２２,２３    ステップ
３１    自己組織化マップ入力層
３２    自己組織化マップ出力層
３３    自己組織化マップの入力層３１を構成するユニット
３４    自己組織化マップの出力層３２を構成するユニット
４０〜５０    ステップ
５１    ユニットc
５２    近傍集合
６１    距離マップ
７１    クラスタリングマップ
７２    クラスタ境界
８１    クラスタ境界
８２    入力ベクトルを表すもの
８３    クラスタ
９１    入力ベクトルの位置
９２    クラスタ境界
９３〜９７    クラスタ認識区間
１０１    入力装置
１０２    記憶装置
１０３    出力装置
１０４    記録媒体
１０５    データ処理装置
【図１】
0003712583.tif 000012
【図２】
0003712583.tif 000013
【図３】
0003712583.tif 000014
【図４】
0003712583.tif 000015
【図５】
0003712583.tif 000016
【図６】
0003712583.tif 000017
【図７】
0003712583.tif 000018
【図８】
0003712583.tif 000019
【図９】
0003712583.tif 000020
【図１０】
0003712583.tif 000021