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