(57)【特許請求の範囲】
【請求項１】
パターン検索を行う検索装置において、
学習パターンを複数のクラスタに分類して検索辞書を作成する検索辞書作成手段と、
前記検索辞書にもとづいて、前記クラスタの中から、入力された検索パターンと至近のクラスタを検出する至近クラスタ検出手段と、
至近クラスタに属しているすべての学習パターンを前記検索パターンと比較して、前記検索パターンと所定の距離を持つ学習パターンを検出する学習パターン検出手段と、
前記学習パターン検出手段で検出された前記学習パターン及び前記検索辞書を用いて、検索範囲を決定する検索範囲決定手段と、
前記検索範囲に属しているすべての学習パターンの中から前記検索パターンの検索を行う検索手段と、
を有することを特徴とする検索装置。
【請求項２】
前記検索辞書作成手段は、前記学習パターン間の距離により、すべての前記学習パターンをいくつかのクラスタに分類し、前記クラスタの代表、前記クラスタの半径、前記クラスタ間同士の距離、前記学習パターン、前記検索パターンと前記至近クラスタを検出するときの前記クラスタの比較順番を求めて、前記検索辞書を作成することを特徴とする請求項１記載の検索装置。
【請求項３】
前記検索辞書作成手段は、前記クラスタの代表を求める際に、特徴量でパターンを表現する場合は、前記クラスタに属しているすべての前記学習パターンの前記特徴量の各次元の平均値を求め、求められた前記平均値を前記クラスタの代表とすることを特徴とする請求項２記載の検索装置。
【請求項４】
前記検索辞書作成手段は、前記クラスタの代表を求める際に、特徴量以外でパターンを表現する場合は、前記クラスタに属しているすべての前記学習パターンについて、各学習パターン間の距離を計算して、前記クラスタに属しているすべての前記学習パターンとの距離の和が最小になる学習パターンを前記クラスタの代表とすることを特徴とする請求項２記載の検索装置。
【請求項５】
前記検索辞書作成手段は、前記クラスタの半径を求める際に、前記クラスタに属しているすべての前記学習パターンと前記クラスタの代表間の距離を計算し、最大距離を前記クラスタの半径とすることを特徴とする請求項２記載の検索装置。
【請求項６】
前記検索辞書作成手段は、前記クラスタ間同士の距離を求める際に、前記クラスタの代表間の距離を前記クラスタ間同士の距離とすることを特徴とする請求項２記載の検索装置。
【請求項７】
前記検索辞書作成手段は、前記学習パターンまたは前記検索パターンと前記クラスタ間の距離を求める際に、前記学習パターンまたは前記検索パターンと前記クラスタ代表間の距離を、前記学習パターンまたは前記検索パターンと前記クラスタ間の距離とすることを特徴とする請求項２記載の検索装置。
【請求項８】
前記検索辞書作成手段は、前記至近クラスタを検出するときの前記クラスタの比較順番を求める際に、特徴量でパターンを表現する場合は、すべての前記クラスタの代表について、前記クラスタの代表の前記特徴量の各次元の平均値を求め、求められた前記平均値と近傍のクラスタを最初に比較するように、比較順番を求めることを特徴とする請求項２記載の検索装置。
【請求項９】
前記検索辞書作成手段は、前記至近クラスタを検出するときの前記クラスタの比較順番を求める際に、特徴量以外でパターンを表現する場合は、すべての前記クラスタ間の距離の和が最小になるクラスタを最初に比較するクラスタとし、最初に比較する前記クラスタと他のクラスタ間の距離を上昇順でソートして、ソートされた順番を比較順番とすることを特徴とする請求項２記載の検索装置。
【請求項１０】
前記検索辞書作成手段は、階層構造からなり、すべての前記クラスタ間の距離、前記クラスタの比較順番及び各クラスタの情報を上位の階層に持ち、前記クラスタの情報は、前記クラスタの代表の構造データ、前記クラスタの半径、前記クラスタに属している学習パターンの数及び前記クラスタに属している学習パターン情報から構成されることを特徴とする請求項２記載の検索装置。
【請求項１１】
前記検索辞書作成手段は、前記学習パターン情報として、前記学習パターンの名前、前記学習パターンの構造データ及び前記学習パターンと前記クラスタの代表の間の距離から構成されることを特徴とする請求項１０記載の検索装置。
【請求項１２】
前記至近クラスタ検出手段は、前記検索辞書に格納されている前記クラスタの比較順番で前記クラスタを選択し、前記クラスタの代表と前記検索パターンの間の距離を計算し、前記検索パターンと近傍のクラスタを求めて、クラスタの比較範囲を縮小していくことを特徴とする請求項１記載の検索装置。
【請求項１３】
前記至近クラスタ検出手段は、前記クラスタの比較範囲を求める際に、前記検索辞書に格納されているクラスタ比較順番ｉのクラスタ番号をS(i)、検出途中段階での前記検索パターンとの距離が最小であるクラスタをＣMinClass、前記検索辞書に格納されているＣMinClassとクラスタＣS(i)間の距離をＤ（ＣMinClass, ＣS(i)）、検出途中段階で求められた検索パターンとＣMinClass間の距離をＤMinCとした場合に、
Ｄ（ＣMinClass, ＣS(i)）＜２＊ＤMinC
を満たす、すべてのクラスタを前記クラスタの比較範囲とすることを特徴とする請求項１２記載の検索装置。
【請求項１４】
前記検索範囲決定手段は、クラスタの検索範囲、前記クラスタの検索範囲にあるクラスタに属している学習パターンの検索をする必要があるかどうかの判定及び検索する必要があるクラスタに属している前記学習パターンの検索範囲、を求めることを特徴とする請求項１記載の検索装置。
【請求項１５】
前記検索範囲決定手段は、前記クラスタの検索範囲を求める際に、クラスタＣMinClassとクラスタＣi 間の距離をＤ（ＣMinClass, Ｃi ）、検索パターンｑとＣMinClass間の距離をＤ（ｑ, ＣMinClass）、検索途中段階で求められた前記検索パターンと前記学習パターン間の最小距離をＤMinP、前記検索辞書に格納されているクラスタＣi の半径をＲi とした場合に、
Ｄ（ＣMinClass, Ｃi ）＜Ｄ（ｑ, ＣMinClass）＋ＤMinP＋Ｒi 
を満たす、すべてのクラスタを前記クラスタの検索範囲とすることを特徴とする請求項１４記載の検索装置。
【請求項１６】
前記検索範囲決定手段は、前記クラスタの検索範囲にあるクラスタに属している学習パターンを検索する必要があるかどうかを判定する際に、検索パターンｑと前記クラスタの検索範囲にあるクラスタＣi 間の距離Ｄ（ｑ, Ｃi ）を計算した場合に、
Ｄ（ｑ, Ｃi ）＜ＤMinP＋Ｒi 
を満たす場合は、前記クラスタに属している学習パターンを検索する必要があると判定することを特徴とする請求項１４記載の検索装置。
【請求項１７】
前記検索範囲決定手段は、前記学習パターンの検索範囲を求める際に、前記検索辞書に格納されているクラスタＣi に属している学習パターンｐとクラスタＣi の代表間の距離をＤ（ｐ, Ｃi ）とした場合に、
Ｄ（ｐ, Ｃi ）＞Ｄ（ｑ, Ｃi ）−ＤMinP
を満たす、すべての学習パターンを検索範囲とすることを特徴とする請求項１４記載の検索装置。
【請求項１８】
パターン検索を行う検索方法において、
検索辞書作成手段により、学習パターンを複数のクラスタに分類して検索辞書を作成し、
至近クラスタ検索手段により、前記検索辞書作成手段により作成された前記検索辞書にもとづいて、前記クラスタの中から、入力された検索パターンと至近のクラスタを検出し、
学習パターン検出手段により、前記至近クラスタ検索手段により検出された至近クラスタに属しているすべての学習パターンを前記検索パターンと比較して、前記検索パターンと所定の距離を持つ学習パターンを検出し、
検索範囲決定手段により、前記学習パターン検出手段により検出された前記学習パターン及び前記検索辞書を用いて、検索範囲を決定し、
検索手段により、前記検索範囲決定手段により決定された前記検索範囲に属しているすべての学習パターンの中から前記検索パターンの検索を行うことを特徴とする検索方法。
【請求項１９】
前記至近クラスタ検索手段は、前記至近クラスタの検出の際には、前記検索辞書に格納されている前記クラスタの比較順番で前記クラスタを選択し、前記クラスタの代表と前記検索パターンの間の距離を計算し、前記検索パターンと近傍のクラスタを求めて、前記クラスタの比較範囲を縮小していくことを特徴とする請求項１８記載の検索方法。
【請求項２０】
コンピュータにパターン検索を実行させる検索プログラムを記録したコンピュータ読み取り可能な記録媒体において、
学習パターンを複数のクラスタに分類して検索辞書を作成する検索辞書作成手段、
前記検索辞書にもとづいて、前記クラスタの中から、入力された検索パターンと至近のクラスタを検出する至近クラスタ検出手段、
至近クラスタに属しているすべての学習パターンを前記検索パターンと比較して、前記検索パターンと所定の距離を持つ学習パターンを検出する学習パターン検出手段、
前記学習パターン検出手段で検出された前記学習パターン及び前記検索辞書を用いて、検索範囲を決定する検索範囲決定手段、
前記検索範囲に属しているすべての学習パターンの中から前記検索パターンの検索を行う検索手段、
としてコンピュータを機能させることを特徴とする検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は検索装置、検索方法及び検索プログラムを記録したコンピュータ読み取り可能な記録媒体に関し、特にパターン検索を行う検索装置、パターン検索を行う検索方法及びコンピュータにパターン検索を実行させる検索プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
パターン検索及び構造検索技術は、文字、音声、画像のパターンや化合物分子構造、ＲＮＡの二次構造等をコンピュータを用いて検索する技術であり、近年の多様化、複雑化した情報化社会の発展に伴って、より高速、高精度に検索しようとする要望が高まっている。
【０００３】
また、完全に一致するパターンや構造を検索しようとするだけでなく、もっとも類似したパターンや構造を検索したいという場合がある。
例えば、情報化学分野には、化合物の構造がよく似ていると性質がよく似ているではないかという構造・活性問題が古くから研究されており、このような場合、数百万の化合物分子構造を効率よく分類したり、類似構造を効率よく検索したいという強い要望がある。
【０００４】
パターン検索の分野では、パターンの特徴量を用いて、パターン間の距離または類似度を定義し、その距離または類似度を用いて入力未知パターン（以降、検索パターン）をすべての被検索パターン（以降、学習パターン）と比較して、検索パターンを推定する総当たり検索法が知られている。
【０００５】
ところが、総当たり検索法では、パターン間の距離または類似度の計算には非常に手間がかかるので、すべての大量な学習パターンと比較すると、莫大な時間がかかるという大きな欠点がある。
【０００６】
このため、従来では、あらかじめ学習パターン間の距離を求め、学習パターンをいくつかのクラスタに分類して検索を行う大分類検索法が広く用いられている。
【０００７】
例えば、特開平６−２５１１５６号公報では、パターン間の距離を用いて、学習パターンをいくつかのクラスタに分類し、検索パターンの特徴量を変換しながら、各クラスタの代表と比較して、一番近いクラスタを求める。
【０００８】
そして、求められたクラスタに属しているすべての学習パターンを検索パターンと比較して、検索パターンを推定している。
一方、情報化学分野で、新しい化合物を合成するとき、設計された分子構造とよく似ているもの、または部分的によく似ているものを検索する場合、化合物分子構造間の距離または類似度をどのように定義するか、化合物分子構造をどのように表現するか、化合物をどのように分類するか、どのように類似構造を検索するか、が問題になってくる。
【０００９】
特開平７−２８８４４号公報では、物質の立体構造を点集合で表現し、２つの立体構造を重ねあわせることにより、構造間の距離を計算する。そして、類似構造を検索するとき、幾何学的な関係による候補を絞り込んで、検索範囲を縮小しながら検索している。
【００１０】
【発明が解決しようとする課題】
しかし、上記のような従来の大分類検索法では、検索速度は速くはなるが、検索精度が悪いといった問題があった。
【００１１】
図１８は大分類検索法の精度上の問題点を示す図である。（Ａ）はクラスタが重なる場合、（Ｂ）はクラスタが重ならない場合を示している。
（Ａ）に示す検索では、まず、入力パターンｑとクラスタ代表との距離が、最も短いクラスタとして、クラスタＡが求まったとする（すなわち、図でＤ１＜Ｄ２）。
【００１２】
そして、クラスタＡ内の複数の学習パターンと入力パターンｑとの距離を比較する。すると、最も短い距離ｄ１である学習パターンａが類似パターンとして求まる。
【００１３】
ところが、入力パターンｑとクラスタ代表との距離がクラスタＡよりも長いクラスタであるクラスタＢに対し、クラスタＢ内の学習パターンｂとの距離ｄ２の方が、距離ｄ１よりも短い。すなわち、この学習パターンｂが、実際には入力パターンｑに最も類似しているパターンである。
【００１４】
（Ｂ）の場合も同様に、検索パターンｑとクラスタＡの距離Ｄ１の方がクラスタＢとの距離Ｄ２より短いが、類似パターンは学習パターンａではなく、実際にはクラスタＢ内にある学習パターンｂが、検索パターンｑと最も類似する類似パターンとなる（ｄ２＜ｄ１より）。
【００１５】
したがって、大分類検索法の検索精度は、学習パターン間の距離の定義とその計算方法、学習パターン自身の表現方法及び学習パターンをクラスタに分類する際の分類方法に強く依存しており、もっとも類似なパターンを確実に検索できる保証がないといった問題があった。
【００１６】
また、上記の従来技術では、入力パターンの特徴量を変換したり、物質の立体構造の特性を利用したりして、精度の向上を図ろうとしているが、いずれにしろ、パターンの距離や表現方法及び分類方法に依存しているため、検索精度の信頼性が十分に高いものとはいえなかった。
【００１７】
本発明はこのような点に鑑みてなされたものであり、パターンの距離や表現方法及び分類方法に依存せず、高速、高精度の検索を行う検索装置を提供することを目的とする。
【００１８】
また、本発明の他の目的は、パターンの距離や表現方法及び分類方法に依存せず、高速、高精度の検索を行う検索方法を提供することである。
さらに、本発明の他の目的は、パターンの距離や表現方法及び分類方法に依存せず、高速、高精度の検索を行う検索プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することである。
【００１９】
【課題を解決するための手段】
本発明では上記課題を解決するために、パターン検索を行う検索装置において、学習パターンを複数のクラスタに分類して検索辞書を作成する検索辞書作成手段と、前記検索辞書にもとづいて、前記クラスタの中から、入力された検索パターンと至近のクラスタを検出する至近クラスタ検出手段と、至近クラスタに属しているすべての学習パターンを前記検索パターンと比較して、前記検索パターンと所定の距離を持つ学習パターンを検出する学習パターン検出手段と、前記学習パターン検出手段で検出された前記学習パターン及び前記検索辞書を用いて、検索範囲を決定する検索範囲決定手段と、前記検索範囲に属しているすべての学習パターンの中から前記検索パターンの検索を行う検索手段と、を有することを特徴とする検索装置が提供される。
【００２０】
ここで、検索辞書作成手段は、学習パターンを複数のクラスタに分類して検索辞書を作成する。至近クラスタ検出手段は、検索辞書にもとづいて、クラスタの中から、入力された検索パターンと至近のクラスタを検出する。学習パターン検出手段は、至近クラスタに属しているすべての学習パターンを検索パターンと比較して、検索パターンと所定の距離を持つ学習パターンを検出する。検索範囲決定手段は、学習パターン検出手段で検出された学習パターン及び検索情報を用いて、検索範囲を決定する。検索手段は、検索範囲に属しているすべての学習パターンの中から検索パターンの検索を行う。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。図１は本発明の検索装置の原理を示す図である。検索装置１は、パターン（構造を含む）検索及び類似パターン検索を行う。
【００２２】
検索辞書作成手段１１は、構造上または性質上パターン間の相違を表す尺度としての距離、またはパターンがどのぐらい似ているかを表す尺度としての類似度等の情報にもとづき、学習パターンを複数のクラスタに分類して検索辞書を作成する。検索辞書の詳細については後述する。
【００２３】
至近クラスタ検出手段１２は、検索辞書にもとづいて、クラスタの中から、入力された検索パターンｑと最も近い至近クラスタＣを検出する。
学習パターン検出手段１３は、至近クラスタＣに属しているすべての学習パターンを検索パターンｑと比較して、検索パターンｑと所定の距離（以降、最小距離とする）を持つ学習パターンｐを検出する。
【００２４】
検索範囲決定手段１４は、学習パターン検出手段１３で検出された学習パターンｐ及び検索辞書を用いて、検索範囲を決定する。
すなわち、学習パターンｐと検索パターンｑとの距離、検索辞書に格納されているクラスタ間の距離、クラスタの半径等を用いて検索範囲（図の斜線部）を決める。詳細は後述する。
【００２５】
検索手段１５は、検索範囲に属しているすべての学習パターンの中から検索パターンｑのパターン検索及び類似パターン検索を行う。
次に検索装置１の動作概要について説明する。図２〜図４は至近クラスタ検出手段１２の動作を説明する図である。
【００２６】
図２の多次元空間上に複数のクラスタと検索パターンｑが示されている。まず、多次元空間の中心にあるクラスタＣ１と検索パターンｑの距離ｄａを求める。そして、距離ｄａの２倍の距離２ｄａを半径に持つ円Ｅａを最初のクラスタ比較範囲とし、この円Ｅａ内にある複数のクラスタから、至近クラスタを求めていく。
【００２７】
円Ｅａを求めた後、検索辞書に格納されたクラスタ比較順番（検索パターンｑと比較していく際のクラスタの比較順序であり、クラスタＣ１との距離が短い順に検索パターンｑとクラスタとを比較していく。図ではクラスタＣ１との距離が短い順にＣ２、Ｃ３〜Ｃ６を付してある）にもとづいて、検索パターンｑと円Ｅａ内のクラスタの距離を求め、そのとき前回に求めた距離よりも小さい場合にはクラスタ比較範囲を小さくしていく。
【００２８】
例えば、次のクラスタＣ２と検索パターンｑとの距離を求め、その距離がクラスタＣ１と検索パターンｑとの距離よりも短ければ、クラスタ比較範囲となる円を小さくし、その範囲内でまた比較順番にもとづいたクラスタとの距離をさらに求め、順次、クラスタ比較範囲を小さくしていく。
【００２９】
図３はクラスタ比較範囲を小さくしている途中段階を示している。クラスタＣ６と検索パターンｑの距離ｄｂを求める。そして、距離２ｄｂを半径に持つ円Ｅｂをクラスタ比較範囲とし、この円Ｅｂ内にあるクラスタから、至近クラスタを求めていく。
【００３０】
図４は至近クラスタを求めた図である。上記のようにクラスタ比較範囲を小さくしていき、最終的に円Ｅｃ内のクラスタＣ６を至近クラスタとして検出している。
【００３１】
このようにクラスタ比較範囲を次第に小さくしていくことで、検索パターンｑと最も距離の近い至近クラスタを効率よく高速に検出することができる。
次に学習パターン検出手段１３と検索範囲決定手段１４の動作について説明する。図５は学習パターン検出手段１３と検索範囲決定手段１４の動作を説明する図である。
【００３２】
学習パターン検出手段１３は、至近クラスタＣMinClassが求まった後、至近クラスタＣMinClassに属しているすべての学習パターンと、検索パターンｑとを比較して、距離が最短の学習パターンＰMinClassを求める。
【００３３】
また、クラスタＣMinClassと検索パターンｑとの距離と、学習パターン検出手段１３で求めた学習パターンＰMinClassと検索パターンｑとの距離と、からなる半径Ｒを持つ円Ｅｄが求まる。
【００３４】
次に検索範囲決定手段１４は、円Ｅｄと重なるクラスタがあるかどうかを判断する。クラスタ間の距離などの検索に必要な情報は、検索辞書に格納されているため既知である。
【００３５】
したがって、図ではクラスタＣk が円Ｅｄと重ならないことが判断でき、検索範囲対象外となる。また、クラスタＣh が円Ｅｄと重なることを認識する。
検索範囲決定手段１４は、次に円Ｅｅ（検索パターンｑと学習パターンＰMinClass間の距離を半径に持つ円）と重なるクラスタがあるかどうかを判断する。クラスタＣh は、円Ｅｄと重なるが円Ｅｅとは重ならないため、検索範囲対象外とし、円Ｅｄと円Ｅｅに重なるクラスタＣi を選択する。
【００３６】
ここで、円Ｅｅに重なるクラスタＣi の領域は、領域Ｓａのみであるが、多次元空間に配置されているパターンを考えているので、領域Ｓａを含む図の斜線部分Ｓｂが最終的な検索範囲として求まる。
【００３７】
その後、検索手段１５では、この検索範囲Ｓｂに属しているすべての学習パターンの中から検索パターンｑの検索を行うことになる。なお、至近クラスタの検出や検索範囲決定等の動作のアルゴリズムについては、数式を用いて詳細に後述する。
【００３８】
以上説明したように、本発明の検索装置１では、検索辞書をあらかじめ作成しておき、検索辞書にもとづいて、入力された検索パターンと最も近い至近クラスタを検出し、検索パターンと至近クラスタ内で最小距離を持つ学習パターンを検出する。
【００３９】
そして、検出した学習パターン及び検索辞書を用いて、検索範囲を段階的に決定していって、最終的に求めたその検索範囲内で検索を行う構成とした。
したがって、従来のようにパターン間の距離の定義とその計算方法、パターン表現方法及びパターンのクラスタ分類方法を設定して、これらの方法に依存した形で検索を行うのではないので、検索速度及び検索精度が向上し、信頼性の高い検索を行うことが可能になる。
【００４０】
次に本発明の検索装置１の詳細構成について図６、７を用いて説明する。図６は検索装置１の構成を示す図である。
検索パターン情報格納手段１７は、検索パターンの情報を格納している。検索パターンの情報は、検索パターンの名前と検索パターンの構造データから構成される。
【００４１】
パターンの構造データは、パターンの表現方法により異なる。例えば、特徴量でパターンを表現する場合は、特徴量がパターンの構造データとして格納される。
【００４２】
また、グラフ理論上のグラフでパターンを表現する場合は、パターンに対応している重み付きグラフが、パターンの構造データとして格納される。なお、パターン自身がパターンの構造データとして格納されても構わない。
【００４３】
検索辞書格納手段１１ａは、検索辞書作成手段１１で作成された検索辞書を格納する。図７は検索辞書内の検索辞書データを示す図である。図に示すように検索辞書データ１００は階層構造になっている。
【００４４】
検索辞書データ１００は、すべてのクラスタ間の距離１０１、検索パターンと至近クラスタを求めるときのクラスタの比較順番１０２及び各クラスタの情報から構成されている。
【００４５】
各クラスタの情報１０３は、クラスタ１〜クラスタｎのデータから構成される。それぞれは、クラスタ代表の構造データ１０４、クラスタの半径１０５、クラスタに属している学習パターンの数１０６、クラスタに属している複数の学習パターン情報１０７−１〜１０７−ｍから構成されている。
【００４６】
例えば、学習パターン情報１０７−１は、学習パターン１の名前１０７ａ、学習パターン１の構造データ１０７ｂ、学習パターン１とクラスタ代表間の距離１０７ｃから構成されている。学習パターン情報１０７−２〜１０７−ｍも構成は同様である。
【００４７】
メモリＭ１は、検索パターン情報格納手段１７から読み出された１つの検索パターンの名前と構造データを格納する。
メモリＭ２〜Ｍ４は、クラスタ代表の構造データ１０４、クラスタの半径１０５、クラスタに属している学習パターンの数１０６を格納する。メモリＭ５は、学習パターン情報１０７−１〜１０７−ｍを格納している。
【００４８】
メモリＭ６、Ｍ７は、それぞれ検索パターンと最も近い至近クラスタの情報（クラスタの番号と距離) 、検索パターンと最も類似な学習パターンの情報（学習パターンの名前と距離) を格納する。
【００４９】
至近クラスタ検出手段１２は、検索辞書格納手段１１ａに格納された検索辞書を用いて、メモリＭ１に格納された検索パターンと最も近い至近クラスタを求め、その結果をメモリＭ６に記憶させる。
【００５０】
学習パターン検出手段１３は、メモリＭ６に記憶されている至近クラスタに属しているすべての学習パターンをメモリＭ１に格納されている検索パターンと比較して、距離が最短の学習パターンを求め、求めた学習パターンの名前とその最小距離をメモリＭ７に格納させる。
【００５１】
検索範囲決定手段１４は、検索辞書に格納しているクラスタ間の距離、クラスタの半径及びメモリＭ７に格納されている最小距離を用いて検索範囲を決める。検索手段１５は、検索範囲決定手段１４で求められた検索範囲に属しているすべての学習パターンを、メモリＭ１に格納している検索パターンと比較して、最も類似なパターンを検索する。
【００５２】
記憶手段１６は、検索手段１５で検索された類似パターンの名前と構造データを格納する。
次に検索装置１の装置適用例として、情報端末装置に適用させた場合の装置構成について説明する。図８は検索装置１を情報端末装置に適用させた場合の装置構成を示す図である。
【００５３】
情報端末装置２は、キーボード２１、外部記憶装置２２、ディスプレイ２３、プロセッサ部２４から構成される。
キーボート２１は、ユーザが操作を指示するための入力装置であり、その他の入力装置が付加されていてもよい。
【００５４】
外部記憶装置２２は、検索パターンの構造データ、検索辞書、検索結果及びソフトウェアを格納する。
また、検索パターン情報格納手段１７と検索辞書格納手段１１ａをこの外部記憶装置２２の一部として構成することができる。さらに、記憶手段１６によって検索された、類似パターンの名前と構造データを格納してもよい。
【００５５】
外部記憶装置２２の具体例として、例えばハードディスクなどで構成することができる。ディスプレイ２３は、ユーザに対するメッセージや検索パターンのデータ、検索の結果などを表示するための出力装置である。
【００５６】
プロセッサ部２４は、外部記憶装置２２に格納されているソフトウェアなどに従って、実際の処理を行う。プロセッサ部２４は、具体的にはマイクロプロセッサやパーソナルコンピュータなどのコンピュータシステムで構成することができる。
【００５７】
そして、至近クラスタ検出手段１２、学習パターン検出手段１３、検索範囲決定手段１４及び検索手段１５は、このプロセッサ部２４の上で動作するソフトウェアによって構成することができる。
【００５８】
次に本発明の検索装置１の動作をさらに詳細に説明する。まず、検索パターン情報格納手段１７に格納されている検索パターンについて説明する。
検索パターン情報格納手段１７に格納されている検索パターンの構造データは、パターンの表現方法、距離の定義とその計算法により異なる。
【００５９】
例えば、文字パターン、音声パターン、指紋パターン、顔パターンの場合は、各パターンの特徴量が検索パターンの構造データとして格納される。
化合物分子構造、ＲＮＡの二次構造の場合は、重み付きグラフで表現でき、それぞれの重み付きグラフが検索パターンの構造データとして格納される。
【００６０】
線図形パターンの場合は、線図形の輪郭線データや、線図形自身のデータなどが検索パターンの構造データとして格納される。
パターンの構造データは、そのパターンに対する表現方法、距離の定義とその計算法に関係する。具体的には例えば、文字パターンに対して、ペリフェラル特徴量のユークリッド距離は、パターンｐi の特徴を（ｐi1, ｐi2, …, ｐim) で表現すると、パターンｐi とパターンｐj の間のユークリッド距離は次の式（１）で計算される。
【００６１】
【数１】
0003903610.tif 000002
次に検索辞書格納手段１１ａで学習パターンを格納する際の学習パターンの分類方法について説明する。検索辞書格納手段１１ａは、図７で説明したような検索辞書を格納する。
【００６２】
学習パターンの分類方法については、一般に公表されているパターンの分類方法の中から、処理するパターンに対応している任意の分類方法を選択できる。
例えば、文字パターンに対して、最長距離クラスタリング法がある。最長距離クラスタリング法は、クラスタ間の距離を各クラスタ内の任意の２つのパターン間の距離の中で最長な距離によって定義し、この距離が最小となる２つのクラスタを統合する。２つのクラスタＣi とＣj 間の距離は式（２）で定義される。
【００６３】
【数２】
ｄ（Ｃi , Ｃj ）＝｛ｍａｘ  ｄ（ｐi , ｐj ）｜ｐi ∈Ｃi , ｐj ∈Ｃj ｝…（２）
次に検索辞書格納手段１１ａに格納されているクラスタの代表を求める方法について説明する。クラスタの代表を求める方法について、特徴量でパターンを表現する場合は、クラスタに属しているすべての学習パターンの特徴量の各次元の平均値を求め、求められた特徴量の平均値をそのクラスタの代表とする。
【００６４】
また、特徴量以外の方法でパターンを表現する場合は、クラスタに属しているすべての学習パターンについて、各学習パターン間の距離を計算し、該当するクラスタ内にあるすべての学習パターン間の距離の和が最小になる学習パターンをそのクラスタの代表とする。
【００６５】
次に検索辞書格納手段１１ａに格納されているクラスタの半径を求める方法について説明する。クラスタの半径を求める方法について、クラスタに属しているすべての学習パターンと該当するクラスタ代表の間の距離を計算し、その中で最大の距離をクラスタの半径とする。そして、クラスタ代表間の距離をクラスタ間の距離とし、パターンとクラスタ間の距離をパターンとクラスタ代表間の距離とする。
【００６６】
次に検索辞書格納手段１１ａに格納されている検索パターンと最も近い至近クラスタを求めるときのクラスタの比較順番について説明する。
検索パターンと最も近い至近クラスタを求めるときのクラスタの比較順番について、特徴量でパターンを表現する場合は、すべてのクラスタ代表について、それらの特徴量の各次元の平均値を求め、求められた特徴量の平均値と最も近いクラスタを最初に比較するクラスタとする。
【００６７】
特徴量以外の方法でパターンを表現する場合は、すべてのクラスタとの距離の和が最小になるクラスタを最初に比較するクラスタとする。そして、最初に比較するクラスタと他のクラスタ間の距離を上昇順でソートして、ソートされた順番をその後のクラスタの比較順番とする。
【００６８】
次に至近クラスタ検出手段１２について説明する。至近クラスタ検出手段１２は、検索辞書を用いて、メモリＭ１に格納されている検索パターンと最も近い至近クラスタを求める部分である。
【００６９】
検索パターンと最も近い至近クラスタを求めるとき、検索パターンをすべてのクラスタと比較するのではなく、クラスタが比較範囲に含まれているかどうかを判定しながら最も近いクラスタを求めていく。
【００７０】
クラスタの判定順番は検索辞書に格納されているクラスタの比較順番である。つまり、学習パターンのサンプルからなる多次元空間上の中心（例えば、図２で説明したクラスタＣ１）と近い距離の順（例えば、図２で説明したクラスタＣ２〜Ｃ６の順）にクラスタを比較する。そうすることにより、クラスタの比較回数が少なくなり、最も近い至近クラスタを高速に求めることができる。
【００７１】
具体的には、クラスタの比較範囲の初期値を検索辞書にあるすべてのクラスタと設定する。検索辞書に格納されているクラスタの比較順番で１つのクラスタを選択して、選択されたクラスタがクラスタ比較範囲に含まれているかどうかを判定する。
【００７２】
含まれている場合は、クラスタの代表と検索パターンの間の距離を計算し、検索パターンと近いクラスタを求める。
その後、現段階で求められた検索パターンとクラスタ間の最小距離及び検索辞書に格納されているクラスタ間の距離を用いて次に比較するクラスタの比較範囲を決める。式（３）にクラスタが比較範囲に含まれているかどかを判定する条件を示す。
【００７３】
【数３】
Ｄ（ＣMinClass, ＣS(i)）＜２＊ＤMinC              …（３）
ここで、ＣMinClassは現段階で求められた最も近いクラスタを表す。ＤMinCは検索パターンとクラスタＣMinClassの間の距離を表し、初期値を最大値と設定する。ここでの最大値はコンピュータ上でＤMinC変数の型が表現できる値の範囲の上限である。S(i)は検索辞書に格納されているクラスタの比較順番に第ｉ番のクラスタの番号を表す。
【００７４】
式（３）を満たさないクラスタは検索パターンとの間の距離が、ＤMinCより大きいので、比較する必要がない。
このようにして、検索パターンとクラスタの比較を繰り返すことにより、ＤMinCは小さくなり、従って、式（３）を満たすクラスタの集合は小さくなる。
【００７５】
従って、検索パターンと最も近いクラスタを高速に求めることができる。そして、求められた至近クラスタの番号とその最小距離をメモリＭ６に格納させる。
図９、図１０は至近クラスタ検出手段１２の動作を説明する図である。最初、図９に示すように、検索パターンｑとクラスタＣS(1)の間の距離を計算して、その距離をＤMinCに格納し、MinClass=S(1) になる。
【００７６】
この時、式（３）を満たすクラスタの集合は点線円Ｅ１に含まれているクラスタである。つまり、次の比較範囲は点線円Ｅ１に含まれているクラスタとなる。図１０は検索パターンｑとクラスタＣS(k)を比較した後、式（３）を満たすクラスタの集合（点線円Ｅ２に含まれているクラスタ) を示している。
【００７７】
次に学習パターン検出手段１３及び検索範囲決定手段１４の動作について説明する。図１１は学習パターン検出手段１３と検索範囲決定手段１４の動作を説明する図である。
【００７８】
学習パターン検出手段１３は、至近クラスタ検出手段１２で求められた至近クラスタＣMinClassに属しているすべての学習パターンと検索パターンとを比較して、距離が最も小さい学習パターンＰMinClassを求める。そして、求められた最小距離をメモリＭ７に格納して、ＤMinPで表す。
【００７９】
図１１に示すように、至近クラスタ検出手段１２と学習パターン検出手段１３で求められた結果、ＤMinCとＤMinPにより検索範囲は、点線円Ｅ３に含まれている学習パターンと考えられる。
【００８０】
したがって、検索範囲決定手段１４は、まず、クラスタの検索範囲を求め、次にクラスタの検索範囲にあるクラスタに属している学習パターンを検索する必要があるかどうかを判定する。
【００８１】
続いて、検索する必要があるクラスタに属している最終的な学習パターンの検索範囲を決める。その後、検索手段１５が検索パターンと最も類似な学習パターンをこの学習パターンの検索範囲の中から検索する。クラスタの検索範囲は、次の式（４）を満たすクラスタの集合である。
【００８２】
【数４】
Ｄ（ＣMinClass, Ｃi ）＜Ｄ（ｑ, ＣMinClass）＋ＤMinP＋Ｒi …（４）
ここで、Ｒi はクラスタＣi の半径を表す。式（４）を満たさないということは、図１１に示す点線円Ｅ３の外側にあることを意味している。
【００８３】
点線円Ｅ３の外側にあるクラスタ（図のＣk ）は、このクラスタに属している学習パターンと検索パターンｑとの間の距離はＤMinPより大きいことは明らかなので、検索する必要がない。
【００８４】
図１１に示すクラスタＣi とＣh は式（４）を満たす。式（４）を満たすクラスタがどのぐらい検索パターンｑと離れているか、そのクラスタに属している学習パターンを検索する必要があるかどうか、つまり、そのクラスタが点線円Ｅ４と重なっているかどうかを判定するために、検索パターンｑと式（４）を満たすクラスタＣi 間の距離Ｄ（ｑ, Ｃi ）を計算する。
【００８５】
その距離が次の式（５）を満たすなら、そのクラスタが点線円Ｅ４と重なっているので、そのクラスタに属している学習パターンを検索する必要がある。
【００８６】
【数５】
Ｄ（ｑ, Ｃi ）＜ＤMinP＋Ｒi                             …（５）
式（４）を満たして式（５）を満たさないということは、図１１に示す点線円Ｅ３と重なっているが、点線円Ｅ４と重なっていないことを意味している。
【００８７】
このようなクラスタ（図のＣh ）に属している学習パターンと検索パターンｑの間の距離はＤMinPより大きいので、検索する必要がない。
したがって、図１１に示すクラスタＣi は式（４）と式（５）を満たすクラスタである。
【００８８】
また、求められた式（４）と式（５）を満たすクラスタに属しているすべての学習パターンを検索する必要がない。つまり、点線円Ｅ４に含まれる可能性がある学習パターンだけ検索すればよい。
【００８９】
次の式（６）を満たす学習パターンｐは点線円Ｅ４に含まれる可能性があるため、検索する必要がある。
【００９０】
【数６】
Ｄ（ｐ, Ｃi ）＞Ｄ（ｑ, Ｃi ）−ＤMinP                  …（６）
図１１に示すクラスタＣi は式（４）と式（５）を満たすクラスタであり、クラスタＣi の斜線部分は式（６）を満たす学習パターンを含む部分である。
【００９１】
このように、最終的に検索範囲を求めて、検索手段１５が、この検索範囲内で、検索を実行する。
次に至近クラスタ検出手段１２の動作をフローチャートを用いて説明する。図１２は至近クラスタ検出手段１２の動作手順を示すフローチャートである。
【００９２】
至近クラスタ検出手段１２は、検索辞書を用いて、メモリＭ１に格納されている検索パターンｑと最も近いクラスタを求める部分である。
〔Ｓ１〕クラスタの比較順番ｉ＝１、検索パターンと最も近いクラスタの番号ＭｉｎＣｌａｓｓ＝Ｓ（ｉ）、検索パターンと最も近いクラスタの間の距離ＤMinC＝最大値、クラスタの数ｎを設定する。ここで、Ｓ（ｉ）は検索辞書に格納されているクラスタの比較順番ｉのクラスタ番号を表す。最大値はコンピュータ上にＤMinC変数の型が表現できる値の範囲の上限である。
〔Ｓ２〕クラスタＣS(i)は式（３）を満たすかどうかを判定する。すなわち、検索パターンをＣS(i)と比較する必要があるかどうかを判定する。式（３）を満たす場合はステップＳ３へ、満たさない場合ステップＳ６へ行く。
〔Ｓ３〕検索パターンｑとクラスタＣS(i)の間の距離を計算する。
〔Ｓ４〕ステップＳ３で求めた距離を、現段階で求められた最小距離と比較し、小さい場合はステップＳ５へ、そうでなければステップＳ６へ行く。
〔Ｓ５〕検索パターンと最も近いクラスタの名前、検索パターンと最も近いクラスタ間の距離を書き直す。
〔Ｓ６〕次に比較するクラスタを設定する。
〔Ｓ７〕クラスタが全部処理されたかどうかを判定する。全部処理されていない場合はステップＳ２へ戻り、全部処理された場合は終了する。
【００９３】
次に学習パターン検出手段１３の動作をフローチャートを用いて説明する。図１３は学習パターン検出手段１３の動作手順を示すフローチャートである。
学習パターン検出手段１３は、検索パターンと最も近いクラスタＣMinClassに属している学習パターンの中に、検索パターンｑとの距離が最も小さい学習パターンを求める部分である。
〔Ｓ１１〕学習パターンの番号ｉ＝１、学習パターンと検索パターンの間の距離ＤMinP＝最大値を設定する。
〔Ｓ１２〕検索パターンｑとクラスタＣMinClassに属している学習パターンｐi の間の距離Ｄ（ｑ, ｐi ）を計算する。
〔Ｓ１３〕ステップＳ１２で求めた距離とＤMinPとを比較し、ＤMinPより小さい場合はステップＳ１４へ、そうでなければステップＳ１５へ行く。
〔Ｓ１４〕ＤMinPと学習パターンの名前を書き直す。
〔Ｓ１５〕学習パターンの番号に１を増やす。
〔Ｓ１６〕すべての学習パターンが処理されたかどうかを判定する。すべて処理されていない場合はステップＳ１２へ戻る。全部処理された場合は終了する。
【００９４】
次に検索範囲決定手段１４と検索手段１５の動作をフローチャートを用いて説明する。図１４、図１５は検索範囲決定手段１４と検索手段１５の動作手順を示すフローチャートである。
【００９５】
検索範囲決定手段１４は検索範囲を決め、検索手段１５はその範囲内にある学習パターンと検索パターンとを比較して、最も類似な学習パターンを検索する部分である。
〔Ｓ２１〕クラスタの番号ｉ＝１、クラスタの数ｎを設定する。
〔Ｓ２２〕クラスタＣi がＣMinClassであるかどうかを判定する。ＣMinClassであれば、ステップＳ３３へ、そうでなければステップＳ２３へ行く。
〔Ｓ２３〕このクラスタが式（４）を満たすかどうかを判定する。満たす場合はステップＳ２４へ、満たさない場合はステップＳ３３へ行く。
〔Ｓ２４〕検索パターンｑとクラスタＣi の間の距離Ｄ（ｑ, Ｃi ）を計算する。
〔Ｓ２５〕ステップＳ２４の距離が式（５）を満たすかどうかを判定する。満たす場合はステップＳ２６へ、満たさなければステップＳ３３へ行く。
〔Ｓ２６〕学習パターンの番号ｊ＝１、クラスタＣi に属している学習パターンの数ｍを設定する。
〔Ｓ２７〕学習パターンｐj が式（６）を満たすかどうかを判定する。つまり、ｐj を検索する必要があるかどうかを判定する。式（６）を満たす場合はステップＳ２８へ、満たさない場合はステップＳ３１へ行く。
〔Ｓ２８〕検索パターンｑとｐj の間の距離を計算する。
〔Ｓ２９〕ステップＳ２８で求めた距離が最小かどうかを判定する。最小ならばステップＳ３０へ、そうでなければステップＳ３１へ行く。
〔Ｓ３０〕ＤMinPと類似パターンの名前を書き直す。
〔Ｓ３１〕学習パターンの番号を１増やす。
〔Ｓ３２〕Ｃi に属しているすべての学習パターンが全部処理されなかったら、ステップＳ２７に戻る。全部処理されたら、ステップＳ３３へ行く。
〔Ｓ３３〕クラスタの番号を増やす。
〔Ｓ３４〕全部のクラスタが処理されたら終了、そうではなければステップＳ２２へ戻る。
【００９６】
次に本発明の検索装置１を用いて、具体的に文字パターンを検索した際の検索速度及び検索精度について説明する。
文字パターンは、紙に印刷された文字画像をスキャナでコンピュータに入力されたものである。
【００９７】
また、２次ペリフェラル特徴量で文字パターンを表現し、文字パターン間のユークリッド距離で文字パターン間の相違を表す。３３５５個の文字パターンを最長距離法によって５００クラスタまでクラスタリングし、クラスタの一部分を図１６のように示す。図１６は文字パターンのクラスタの一部分を示す図である。
【００９８】
そして、各クラスタの代表、半径、クラスタ間の距離を求め、検索辞書を作成する。この検索辞書を用いて、総当り法と本発明の検索装置１で１００６５個の未学習パターン（検索パターン）を検索した。
【００９９】
その結果は、総当たり法の場合が検索精度が１００％、検索速度が３３５５回、本発明の検索装置１では検索精度が１００％、検索速度が８１５．９０回であった。
【０１００】
このように、検索精度はいずれも１００％であるが、本発明での検索速度は総当り法の４．１１倍速くなった。なお、検索精度と検索速度の定義は次の式（７）と式（８）で定義される。
【０１０１】
【数７】
検索精度＝｛（検索結果＝総当たり法の検索結果）の個数÷（総検索文字パターン数）｝×１００％                                      …（７）
【０１０２】
【数８】
検索速度＝（パターンを検索する時の距離の計算回数の和）÷（総検索文字パターン数）                                                …（８）
以上説明したように、本発明によれば、検索パターンと最も類似なパターンを高速、正確に検索できる。特に、本発明の検索装置１の検索精度は、パターンの表現方法、パターン間の距離の定義とその計算法、パターンの分類方法に依存しない。
【０１０３】
したがって、パターン認識分野における未知パターンを完全に認識できない問題を部分的に解決することや、大量の構造を持つデータの中から構造データを高速に検索する問題、または類似な構造を持つデータを高速に検索する問題等を解決することが可能になる。
【０１０４】
次に本発明の検索方法について説明する。図１７は本発明の検索方法の処理手順を示すフローチャートである。
〔Ｓ４１〕検索辞書作成手段は、学習パターンを複数のクラスタに分類して検索辞書を作成する。
〔Ｓ４２〕至近クラスタ検索手段は、検索辞書にもとづいて、クラスタの中から、入力された検索パターンと至近のクラスタを検出する。
〔Ｓ４３〕学習パターン検出手段は、至近クラスタに属しているすべての学習パターンを検索パターンと比較して、検索パターンと最小距離を持つ学習パターンを検出する。
〔Ｓ４４〕検索範囲決定手段は、学習パターン及び検索辞書を用いて、検索範囲を決定する。
〔Ｓ４５〕検索手段は、検索範囲に属しているすべての学習パターンの中から検索パターンの検索を行う。
【０１０５】
以上説明したように、本発明の検索方法は、学習パターンを複数のクラスタに分類して検索辞書を作成し、検索辞書にもとづいて、入力された検索パターンと至近の至近クラスタを検出し、検索パターンと至近クラスタ内で最小距離を持つ学習パターンを検出し、検出した学習パターン及び検索辞書を用いて、検索範囲を決定して検索を行う方法とした。
【０１０６】
これにより、パターンの距離や表現方法及び分類方法に依存せず、高速、高精度の検索を行うことが可能になる。
また、以上説明したような検索装置１及び検索方法の機能を実現するためのコンピュータプログラムは、半導体メモリや磁気記録媒体などの記録媒体に記述させることができる。
【０１０７】
これにより、市場に流通させる場合に、ＣＤ−ＲＯＭやフロッピーディスク等の可搬型記録媒体にプログラムを格納して流通させたり、ネットワークを介して接続されたコンピュータの記憶装置に格納しておき、ネットワークを通じて他のコンピュータに転送することもできる。
【０１０８】
なお、コンピュータで実行する際には、コンピュータ内のハードディスク装置等にプログラムを格納しておき、メインメモリにロードして実行する。
【０１０９】
【発明の効果】
以上説明したように、本発明の検索装置は、学習パターンを複数のクラスタに分類して検索辞書を作成し、検索辞書にもとづいて、入力された検索パターンと最も近い至近クラスタを検出し、検索パターンと至近クラスタ内で所定の距離を持つ学習パターンを検出し、検出した学習パターン及び検索辞書を用いて、検索範囲を決定して検索を行う構成とした。これにより、パターン間の距離や表現方法及び分類方法に依存せず、高速、高精度の検索を行うことが可能になる。
【図面の簡単な説明】
【図１】  本発明の検索装置の原理を示す図である。
【図２】  至近クラスタ検出手段の動作を説明する図である。
【図３】  至近クラスタ検出手段の動作を説明する図である。
【図４】  至近クラスタ検出手段の動作を説明する図である。
【図５】  学習パターン検出手段と検索範囲決定手段の動作を説明する図である。
【図６】  検索装置の構成を示す図である。
【図７】  検索辞書内の検索辞書データを示す図である。
【図８】  検索装置を情報端末装置に適用させた場合の装置構成を示す図である。
【図９】  至近クラスタ検出手段の動作を説明する図である。
【図１０】  至近クラスタ検出手段の動作を説明する図である。
【図１１】  学習パターン検出手段と検索範囲決定手段の動作を説明する図である。
【図１２】  至近クラスタ検出手段の動作手順を示すフローチャートである。
【図１３】  学習パターン検出手段の動作手順を示すフローチャートである。
【図１４】  検索範囲決定手段と検索手段の動作手順を示すフローチャートである。
【図１５】  検索範囲決定手段と検索手段の動作手順を示すフローチャートである。
【図１６】  文字パターンのクラスタの一部分を示す図である。
【図１７】  本発明の検出方法の処理手順を示すフローチャートである。
【図１８】  大分類検索法の精度上の問題点を示す図である。（Ａ）はクラスタが重なる場合を示す図である。（Ｂ）はクラスタが重ならない場合を示す図である。
【符号の説明】
１  検索装置
１１  検索辞書作成手段
１２  至近クラスタ検出手段
１３  学習パターン検出手段
１４  検索範囲決定手段
１５  検索手段
Ｃ  至近クラスタ
ｐ  学習パターン
ｑ  検索パターン
【図１】
0003903610.tif 000003
【図２】
0003903610.tif 000004
【図３】
0003903610.tif 000005
【図４】
0003903610.tif 000006
【図５】
0003903610.tif 000007
【図６】
0003903610.tif 000008
【図７】
0003903610.tif 000009
【図８】
0003903610.tif 000010
【図９】
0003903610.tif 000011
【図１０】
0003903610.tif 000012
【図１１】
0003903610.tif 000013
【図１２】
0003903610.tif 000014
【図１３】
0003903610.tif 000015
【図１４】
0003903610.tif 000016
【図１５】
0003903610.tif 000017
【図１６】
0003903610.tif 000018
【図１７】
0003903610.tif 000019
【図１８】
0003903610.tif 000020