(57)【要約】【課題】  この発明は、少ないメモリ使用量でデータの検索を行うことができる、データ検索方法を提供することを目的とする。【解決手段】  入力データ１０に対する類似度の高い、第一の所定の数のクラスタを選択し、クラスタリスト４２を作成する。次に、クラスタリスト４２を第二の所定の数のグループ４３，４４に分割する。次に、一のグループに属するクラスタ内のデータと、入力データ１０との類似度を計算し、入力データ１０に対する類似度の高い、第三の所定の数のデータを選択する。当該第三の所定の数のデータの選択を各グループ単位で実行し、上位候補リスト４９を作成する。【選択図】        図１ 
2005063100.tif 000002
【特許請求の範囲】
【請求項１】
所定の規則に基いてクラスタリングされた複数のデータの中から入力データに類似するデータを検索するデータ検索装置において、
前記入力データに対する類似度の高い、第一の所定の数のクラスタを選択する候補クラスタ選択手段と、
前記候補クラスタ選択手段において選択された前記第一の所定の数のクラスタを、第二の所定の数のグループに分割し、一のグループに属する前記クラスタ内の前記データと、前記入力データとの類似度を計算し、前記入力データに対する類似度の高い、第三の所定の数のデータを選択する処理を、前記グループの各々毎に実行するグループ分割・候補データ選択手段とを、備えている、
ことを特徴とするデータ検索装置。
【請求項２】
各グループ毎に選択された前記第三の所定の数のデータから、第四の所定の数のデータを選択する上位候補選択手段を、さらに備えている、ことを特徴とする請求項１に記載のデータ検索装置。
【請求項３】
グループ分割・候補データ選択手段は、
（前記候補クラスタ選択手段により選択されたクラスタの類似度順位）／（前記第二の所定の数）、に基いて導出される剰余の同じクラスタ同士を、同じグループに属するように分割する、
ことを特徴とする請求項１または請求項２に記載のデータ検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データ検索装置に係る発明であって、特に、入力されたデータに類似したデータをデータベースから検索し、類似度の高い候補データを選択するデータ検索装置に関するものである。
【背景技術】
【０００２】
従来の技術に係るデータ検索方法において、同じ種類または類似度の近い種類毎にクラスタリングされた、データベースに保持されている複数のデータの中から、入力データに類似度の近いデータを選択する場合には、まず、各クラスタの有する代表値と入力データとの類似度を計算していた。そして、類似度の高い所定の数のクラスタを選択した後に、当該選択された全クラスタ内の全データと入力データとの類似度を一度に計算していた。そして、入力データとの類似度の高い所定の数のデータが候補として選択されていた。
【０００３】
ここで、関連する従来技術として、以下に示すものが存在する（例えば、特許文献１，２，３，４参照）。
【０００４】
【特許文献１】特開平５−２５０４１２号公報
【特許文献２】特開２００１−１３４５７３号公報
【特許文献３】特開２００１−１３４５９３号公報
【特許文献４】特開２００１−１３４５８４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記した従来のデータ検索方法では、類似度の高い所定の数の選択された全クラスタ内の全データと、入力データとの類似度を一度に計算するに際して、当該全計算結果を保持するために、一時的にメモリの使用量が増大し、このためだけに、大きなメモリ領域を用意する必要があった。
【０００６】
そこで、この発明は、少ないメモリ使用量でデータの検索を行うことができる、データ検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的を達成するために、本発明に係る請求項１に記載のデータ検索装置は、所定の規則に基いてクラスタリングされた複数のデータの中から入力データに類似するデータを検索するデータ検索装置において、前記入力データに対する類似度の高い、第一の所定の数のクラスタを選択する候補クラスタ選択手段と、前記候補クラスタ選択手段において選択された前記第一の所定の数のクラスタを、第二の所定の数のグループに分割し、一のグループに属する前記クラスタ内の前記データと、前記入力データとの類似度を計算し、前記入力データに対する類似度の高い、第三の所定の数のデータを選択する処理を、前記グループの各々毎に実行するグループ分割・候補データ選択手段とを、備えているものであっても良い。
【発明の効果】
【０００８】
本発明の請求項１に記載のデータ検索装置は、所定の規則に基いてクラスタリングされた複数のデータの中から入力データに類似するデータを検索するデータ検索装置において、前記入力データに対する類似度の高い、第一の所定の数のクラスタを選択する候補クラスタ選択手段と、前記候補クラスタ選択手段において選択された前記第一の所定の数のクラスタを、第二の所定の数のグループに分割し、一のグループに属する前記クラスタ内の前記データと、前記入力データとの類似度を計算し、前記入力データに対する類似度の高い、第三の所定の数のデータを選択する処理を、前記グループの各々毎に実行するグループ分割・候補データ選択手段とを、備えているので、当該装置を用いた類似データ検索処理を行うことにより、類似計算の際に必要となるメモリの領域を減少させることができる。つまり、使用するメモリ量は、一のグループに属するクラスタのデータと入力データとの類似度を計算結果を保持するだけの量であれば足り、例えば、第一の所定の数のクラスタをＰ個のグループに分割するのあれば、従来必要であったメモリ量の約１／Ｐまでメモリ量を削減することができる。
【発明を実施するための最良の形態】
【０００９】
以下、この発明をその実施の形態を示す図面に基いて具体的に説明する。
【００１０】
＜実施の形態１＞
本実施の形態に係るデータ検索方法は、入力データに対する類似度の高い所定の数のクラスタを選択し、当該選択したクラスタを幾つかのグループに分割し、分割したグループ単位で、クラスタ内のデータと入力データとの類似度を計算し、類似度の高いデータを選択することが特徴である。
【００１１】
図１は、本実施の形態に係るデータ検索方法を実現する装置の構成を示す概略ブロック図である。
【００１２】
図１において、データ入力手段１により検索入力データ（以下、単に入力データと称する）が入力される。
【００１３】
また、データベース２には、同じ種類または類似度の近い種類等、所定の規則に基いてクラスタリングされた複数のデータが、クラスタ単位で記憶されている。
【００１４】
つまり、図２に示すようにデータベース２には、Ｃ１〜Ｃｎのクラスタが記憶されており、各クラスタＣ１〜Ｃｎ内には、所定の規則に基いてクラスタリングされたデータ群ｄ１〜ｄｎ、および各クラスタの代表値ａ１〜ａｎが保持されている。
【００１５】
ここで、代表値ａ１〜ａｎとは、例えば、各クラスタＣ１〜Ｃｎに属しているデータ群ｄ１〜ｄｎの平均値である。
【００１６】
クラスタＣ１には、データ群ｄ１として、データ（Ｃ１−Ｖ１，Ｃ１−Ｖ２，・・・Ｃ１−Ｖｍ１）が保持されており、代表値ａ１として、代表値（Ｃ１−Ｍ）が保持されている。また、クラスタＣｎには、データ群ｄｎとして、データ（Ｃｎ−Ｖ１，Ｃ１−Ｖ２，・・・Ｃ１−ＶｍＮ）が保持されており、代表値ａｎとして、代表値（Ｃｎ−Ｍ）が保持されている。
【００１７】
図１に話を戻して、候補クラスタ選択手段３は、データ入力手段１で入力した入力データとの類似度の高いクラスタを選択する手段である。
【００１８】
また、グループ分割・候補データ選択手段４は、候補クラスタ選択手段３により選択されたクラスタを所定の数のグループに分割し、各グループ単位で、グループに属する各クラスタ内のデータの中から、入力データとの類似度の高い所定の数のデータを選択する手段である。
【００１９】
さらに、上位候補選択手段５は、グループ分割・候補データ選択手段４において、各グループ単位で所定の数ずつ選択したデータを類似度の高い順にソートして、予め定められた数の上位候補データを出力手段６へ出力する手段である。
【００２０】
なお、出力手段６は、上位候補選択手段５により選択された上位候補データを表示装置等に出力する手段である。
【００２１】
次に、候補クラスタ選択手段３、グループ分割・候補データ選択手段４、および上位候補選択手段５のそれぞれにおける処理の流れを、図３，５，７に示すフローチャートに基いて説明する。
【００２２】
まず、はじめに、図１で示したデータ入力手段１が、検索対象である入力データを入力すると、候補クラスタ選択手段３は、図３に示すフローチャートの流れで処理動作を行う。
【００２３】
具体的に、データ入力手段１が入力データを受け取ると、候補クラスタ選択手段３は、まず、データベース２が記憶している各クラスタＣ１〜Ｃｎの各代表値ａ１〜ａｎと、当該受け取った入力データとの類似度をそれぞれ計算する（ステップＳ３１）。ここで、類似度の計算方法として、例えば、ユークリッド距離等の距離計算や、確率計算などを用いることができる。
【００２４】
図４に、入力データ１０と、全てのクラスタＣ１〜Ｃｎの代表値ａ１〜ａｎとの類似度の計算結果４０を示す。計算結果４０において、例えば、類似度Ｌ（ｄ，Ｃ１−Ｍ）は、入力データ１０とクラスタＣ１の代表値ａ１との類似度であり、類似度Ｌ（ｄ，Ｃｎ−Ｍ）は、入力データ１０とクラスタＣｎの代表値ａｎとの類似度である。
【００２５】
次に、全てのクラスタＣ１〜Ｃｎの代表値ａ１〜ａｎと、入力データ１０との類似度計算が終了したら、計算結果４０を、例えば、類似度の高い順等の所定の順序でソート処理する（本実施の形態では、類似度の高い順序でソート処理する）（ステップＳ３２）。当該ソート結果４１を図４に示す。
【００２６】
図４に示すソート結果４１では、クラスタＣ３の代表値ａ３に対する類似度Ｌ（ｄ、Ｃ３−Ｍ）が最も大きな値となっており、次に、クラスタＣ１の代表値ａ１に対する類似度Ｌ（ｄ、Ｃ１−Ｍ）の値が２番目に大きな値となっており、最後に、クラスタＣ２の代表値ａ２に対する類似度Ｌ（ｄ、Ｃ２−Ｍ）の値が最も小さな値となっている。
【００２７】
次に、ソート結果４１において、最も高い類似度から予め設定されている上位数番目までの類似度を選択し、これらの選択した類似度を計算するに際して用いた各代表値の属する各クラスタを示す、クラスタ番号から成るクラスタリスト４２を、グループ分割・候補データ選択手段４に向けて出力して（ステップＳ３３）、候補クラスタ選択手段３の処理は終了する。
【００２８】
本実施の形態では、図４に示すように、上位４番目までの類似度を選択している。そして、これらの選択した類似度を計算するに際して用いた各代表値ａ３，ａ１，ａｎ，ａ４の属する４つクラスタＣ３，Ｃ１，Ｃｎ，Ｃ４を示す、クラスタ番号から成るクラスタリスト４２を作成する。
【００２９】
クラスタリスト４２のクラスタ番号の配列は、対応する類似度の大小の順に対応している。つまり、図４のソート結果４１から分かるように、類似度は、Ｌ（ｄ，Ｃ３−Ｍ）＞Ｌ（ｄ，Ｃ１−Ｍ）＞Ｌ（ｄ，Ｃｎ−Ｍ）＞Ｌ（ｄ，Ｃ４−Ｍ）＞・・・、との関係にあるので、作成されるクラスタリスト４２は、クラスタＣ３のクラスタ番号、クラスタＣ１のクラスタ番号、クラスタＣｎのクラスタ番号、クラスタＣ４のクラスタ番号の順で構成される。
【００３０】
なお、予め候補クラスタ選択手段３に、上位何番目までの類似度を選択するかを設定することにより、作成されるクラスタリスト４２の構成（大きさ）は決定される。
【００３１】
さて次に、図１で示したグループ分割・候補データ選択手段４が、図４に示したクラスタリスト４２を受け取ると、グループ分割・候補データ選択手段４は、図５に示すフローチャートの流れで処理動作を行う。
【００３２】
まず、当該受け取ったクラスタリスト４２を所定の数のグループに分割する（ステップＳ４１）。
【００３３】
本実施の形態では、図６に示すように、クラスタ番号３とクラスタ番号１とから成る第一のグループ４３と、クラスタ番号ｎとクラスタ番号４とから成る第二のグループ４４とに、クラスタリスト４２を２つのグループに分割する。
【００３４】
ここで、分割するグループの数は、グループ分割・候補データ選択手段４に予めに設定しておくことが可能である。
【００３５】
次に、第一のグループ４３に属するクラスタ番号３，１に対応するクラスタＣ３，Ｃ１内の個々のデータと、入力データ１０との類似度を各々計算する（ステップＳ４２）。
【００３６】
具体的に、クラスタＣ３に属するデータＣ３−Ｖ１〜Ｃ３−Ｖｍ３と、入力データ１０との類似度Ｌ（ｄ，Ｃ３−Ｖ１）〜Ｌ（ｄ，Ｃ３−Ｖｍ３）を計算し、クラスタＣ１に属するデータＣ１−Ｖ１〜Ｃ１−Ｖｍ１と、入力データ１０との類似度Ｌ（ｄ，Ｃ１−Ｖ１）〜Ｌ（ｄ，Ｃ１−Ｖｍ１）を計算し、当該計算結果データから成る類似度結果４５を作成する。
【００３７】
次に、類似度結果４５の各要素を所定の順序（ここでは、類似度の高い順序）で、ソート処理する（ステップＳ４３）。当該ソート処理により、図６に示すようにソート結果４７が構成される。
【００３８】
図６に示すソート結果４７では、クラスタＣ１に属するデータＣ１−Ｖ５に対する類似度Ｌ（ｄ，Ｃ１−Ｖ５）が最も大きな値となっており、次に、クラスタＣ３に属するデータＣ３−Ｖ２に対する類似度Ｌ（ｄ，Ｃ３−Ｖ２）の値が２番目に大きな値となっており、最後に、クラスタＣ１に属するデータＣ１−Ｖｍ１に対する類似度Ｌ（ｄ，Ｃ１−Ｖｍ１）の値が最も小さな値となっている。
【００３９】
次に、ソート結果４７から所定の上位番目までの類似度結果データを候補として選択し、当該選択した類似度結果データを保存する（ステップＳ４４）。
【００４０】
ここでは、上位２番目までの類似度結果データＬ（ｄ，Ｃ１−Ｖ５），Ｌ（ｄ，Ｃ３−Ｖ２）とを上位候補データとして選択し、保存する。これにより、図６の上位候補リスト４９の一部が確定した状態となる。なお、上位何番目まで選択し、保存するかは、予めグループ分割・候補データ選択手段４に設定しておくことも可能である。
【００４１】
ステップＳ４４までの処理が終了すると、次に、ステップＳ４１で分割した全グループに対して、ステップＳ４２〜Ｓ４４までの処理を終了しているか否かを判定する（ステップＳ４５）。
【００４２】
今の場合、第一のグループ４３に対する一連の処理（ステップＳ４２〜Ｓ４４）までは終了しているが、第二のグループ４４に対する当該一連の処理は未だ終了していないので、ステップＳ４５で「Ｎ」となり、ステップＳ４６へと移行する。
【００４３】
ステップＳ４６では、上記一連の処理（ステップＳ４２〜Ｓ４４）を実行する処理対象を第一のグループ４３から第二のグループ４４に変更する処理を行い、当該第二のグループ４４に対してステップＳ４２の処理を開始する。
【００４４】
ステップＳ４２では、第二のグループ４４に属するクラスタ番号ｎ，４に対応するクラスタＣｎ，Ｃ４内の個々のデータと、入力データ１０との類似度を各々計算する。
【００４５】
具体的に、クラスタＣｎに属するデータＣｎ−Ｖ１〜Ｃｎ−ＶｍＮと、入力データ１０との類似度Ｌ（ｄ，Ｃｎ−Ｖ１）〜Ｌ（ｄ，Ｃｎ−ＶｍＮ）を計算し、クラスタＣ４に属するデータＣ４−Ｖ１〜Ｃ４−Ｖｍ４と、入力データ１０との類似度Ｌ（ｄ，Ｃ４−Ｖ１）〜Ｌ（ｄ，Ｃ４−Ｖｍ４）を計算し、当該計算結果データから成る類似度結果４６を作成する。
【００４６】
次に、類似度結果４６の各要素を所定の順序（ここでは、類似度の高い順序）で、ソート処理する（ステップＳ４３）。当該ソート処理により、図６に示すようにソート結果４８が構成される。
【００４７】
図６に示すソート結果４８では、クラスタＣ４に属するデータＣ４−Ｖ８に対する類似度Ｌ（ｄ，Ｃ４−Ｖ８）が最も大きな値となっており、次に、同じくクラスタＣ４に属するデータＣ４−Ｖ７に対する類似度Ｌ（ｄ，Ｃ４−Ｖ７）の値が２番目に大きな値となっており、最後に、クラスタＣｎに属するデータＣｎ−ＶｍＮに対する類似度Ｌ（ｄ，Ｃｎ−ＶｍＮ）の値が最も小さな値となっている。
【００４８】
次に、ソート結果４８から所定の上位番目までの類似度結果データを候補として選択し、当該選択した類似度結果データを保存する（ステップＳ４４）。
【００４９】
ここでは、第一のグループ４３のときと同様に、上位２番目までの類似度結果データＬ（ｄ，Ｃ４−Ｖ８），Ｌ（ｄ，Ｃ４−Ｖ７）とを上位候補データとして選択し、保存する。これにより、図６の上位候補リスト４９の他の部分が確定した状態となる。
【００５０】
よって、第一のグループ４３による処理により保存されている類似度結果データＬ（ｄ，Ｃ１−Ｖ５），Ｌ（ｄ，Ｃ３−Ｖ２）と、第二のグループ４４による処理により保存された類似度結果データＬ（ｄ，Ｃ４−Ｖ８），Ｌ（ｄ，Ｃ４−Ｖ７）とにより、上位候補リスト４９は完成する。
【００５１】
ステップＳ４４までの処理が終了すると、次に、ステップＳ４１で分割した全グループに対して、ステップＳ４２〜Ｓ４４までの処理を終了しているか否かを判定する（ステップＳ４５）。
【００５２】
今の場合、全てのグループ４３，４４に対する一連の処理（ステップＳ４２〜Ｓ４４）が終了しているので、ステップＳ４５で「Ｙ」となり、完成した上位候補リスト４９を上位候補選択手段５に対して出力する（ステップＳ４７）。
【００５３】
以上により、グループ分割・候補データ選択手段４における一連の処理は終了する。
【００５４】
さて次に、図１で示した上位候補選択手段５が、図６に示した上位候補リスト４９を受け取ると、上位候補選択手段５は、図７に示すフローチャートの流れで処理動作を行う。
【００５５】
まず、上位候補選択手段５では、受け取った上位候補リスト４９を類似度の高い順にソート処理する（ステップＳ５１）。当該ソート処理により、図８に示すようにソート結果５０が構成される。
【００５６】
図８に示すソート結果５０では、クラスタＣ４に属するデータＣ４−Ｖ８に対する類似度Ｌ（ｄ，Ｃ４−Ｖ８）が最も大きな値となっており、次に、クラスタＣ３に属するデータＣ３−Ｖ２に対する類似度Ｌ（ｄ，Ｃ３−Ｖ２）の値が２番目に大きな値となっており、次に、クラスタＣ４に属するデータＣ４−Ｖ７に対する類似度Ｌ（ｄ，Ｃ４−Ｖ７）の値が３番目に大きな値となっており、最後に、クラスタＣ１に属するデータＣ１−Ｖ５に対する類似度Ｌ（ｄ，Ｃ１−Ｖ５）の値が最も小さな値となっている。
【００５７】
次に、ソート結果５０から所定の上位番目までの類似度結果データを最終候補として選択し、当該選択した最終候補データを出力手段６に対して出力する（ステップＳ５２）。
【００５８】
ここでは、上位３番目までの類似度結果データＬ（ｄ，Ｃ４−Ｖ８），Ｌ（ｄ，Ｃ３−Ｖ２），Ｌ（ｄ，Ｃ４−Ｖ７）を最終候補として選択し、図８に示すように、最終候補データ５１を形成し、当該最終候補データ５１を出力手段６に対して出力する。
【００５９】
なお、上位何番目まで選択するかは、予め上位候補選択手段５に設定しておくことも可能である。
【００６０】
最後に、出力手段６は、受け取った最終候補データ５１を表示装置等に対して出力する。
【００６１】
以上により、本実施の形態に係るデータ検索方法では、グループ分割・候補データ選択手段４において、クラスタリスト４２を所定の数のグループに分割し、各グループ毎に上位候補データの選択処理を行うので、全てのクラスタリスト４２に対して一度に上位候補データを選択する従来の場合より、メモリの使用量を削減できる。
【００６２】
つまり、使用するメモリ量は、一のグループに属するクラスタのデータと入力データとの類似度の計算結果を記憶するだけの量であれば足り、例えば、クラスタリスト４２をＰ個のグループに分割するのあれば、従来必要であったメモリ量の約１／Ｐまでメモリ量を削減することができる。
【００６３】
また、クラスタリスト４２を分割するグループ数が増えれば、上位候補リスト４９に属するデータ数も増大する。そこで、上位候補選択手段５において、上位候補リスト４９に属するデータ数の絞込みを行い、最終候補データ５１を作成することにより、適正の数のデータのみを最終選択することができる。
【００６４】
＜実施の形態２＞
本実施の形態に係るデータ検索方法は、図１で示したグループ分割・候補データ選択手段４によるクラスタリスト４２のグループ分割方法を、以下の式に基いて行うことが特徴である。次式１でａ％ｂは、ａをｂで割ったときの余りを表す。ここで、ａ，ｂは正の整数である。
【００６５】
（クラスタリストの順位）％（分割するグループ数）    ・・・式１
つまり、本実施の形態に係るグループ分割・候補データ選択手段４では、クラスタリスト４２を構成する各データを、式１から得られる剰余毎にグループ分けする。
【００６６】
例えば、候補クラスタ選択手段３により、図９に示すようなクラスタリスト４２が構成されたとする。
【００６７】
図９に示すように、入力データ１０と最も類似度の高い代表値を有しているのはクラスタＣ３であり、次にクラスタＣ８であり、クラスタＣ６、クラスタＣ１の順となり、選択されたクラスタ番号の中で最も入力データ１０との類似度の低い代表値を有しているのは、クラスタＣ５である。なお、当該類似度の高い順がクラスタリスト４２の順位とする。
【００６８】
さて、図９に示したクラスタリスト４２と式１とに基いて、当該クラスタリスト４２を３つのグループに分割する場合について説明する。
【００６９】
まず、クラスタリスト４２の順位が１位であるクラスタＣ３を所定のグループに属させるに際して、式１より、１％３は１÷３の剰余であり、１となる。したがって、クラスタＣ３は、剰余が「１」のクラスタの集合である第一のグループ４２ａに属する。
【００７０】
次に、クラスタリスト４２の順位が２位であるクラスタＣ８を所定のグループに属させるに際して、式１より、２％３は２÷３の剰余であり、２となる。したがって、クラスタＣ８は、剰余が「２」のクラスタの集合である第二のグループ４２ｂに属する。
【００７１】
次に、クラスタリスト４２の順位が３位であるクラスタＣ６を所定のグループに属させるに際して、式１より、３％３は３÷３の剰余であり０となる。したがって、クラスタＣ６は、剰余が「０」のクラスタの集合である第三のグループ４２ｃに属する。
【００７２】
また、クラスタリスト４２の順位が４位であるクラスタＣ１を所定のグループに属させるに際して、式１より、４％３は４÷３の剰余であり、１となる。したがって、クラスタＣ１は、剰余が「１」のクラスタの集合である第一のグループ４２ａに属する。
【００７３】
当該処理を全てのクラスタリスト４２の構成成分に対して実行することにより、図９に示すように、第一のグループ４２ａには、クラスタＣ３，Ｃ１，Ｃ２が当該順で属することになり、第二のグループ４２ｂには、クラスタＣ８，Ｃ１０，Ｃ９が当該順で属することになり、第三のグループ４２ｃには、クラスタＣ６，Ｃ４，Ｃ５が当該順で属することになる。
【００７４】
以上のように本実施の形態では、式１に基いてクラスタリスト４２の構成成分を各グループに分割させることにより、最終的に、グループ分割・候補データ選択手段４により得られる上位候補リスト４９内のデータの中で、入力データ１０との類似度の高いデータが上位候補として残る確率が高くなり、候補データ検索精度を実施の形態１に係る分割方法よりも向上させることができる。
【００７５】
つまり、実施の形態１に係る分割方法では、入力データ１０との類似度の高い代表値を有する、クラスタリスト４２の上位のクラスタが、同じグループに属する。
【００７６】
したがって、当該上位のクラスタが属するグループにおいて、入力データ１０との類似度の高いデータを選択する場合に、高い類似度同士の比較処理となり、例えば、クラスタリスト４２の１，２，３番目の３つのクラスタが同じグループ内に属している場合には、２番目のクラスタや３番目のクラスタに属するデータが上位候補リスト４９のデータとして選択される確率が下がる。
【００７７】
これにより、上位候補リスト４９を構成するデータとして、２，３番目のクラスタよりも下位の順位にあるクラスタに属するデータが選択される可能性が高くなる。
【００７８】
しかし、本実施の形態に係る分割方法の場合には、クラスタリスト４２の上位に位置するクラスタを異なるグループに属させており、上位のクラスタを一のグループに偏在させていないので、実施の形態１の場合よりも、上位に位置するクラスタに属するデータが上位候補リスト４９として選択される可能性が増加する。
【００７９】
結果として、検索データの精度をより向上させることが可能となる。
【００８０】
以上の各実施の形態で説明したデータ検索方法を実現する、本発明に係るデータ検索装置は、例えば、文字認識装置に実装される。
【００８１】
当該文字認識装置では、ペン入力または手入力により入力された文字パターンを、座標データ等で表された入力文字データに変換される。文字認識装置には、予め複数個の文字データを格納するデータベース（図１のデータベース２が、これに相当する）が設けられ、変換された入力文字データに対して類似性の高い文字データを、当該データベースから候補として選択する際に、本発明のデータ検索装置が用いられる。具体的な本発明に係るデータ検索装置の適用例を以下に示す。
【００８２】
＜適用例＞
図１０に示すように、接続部１０１を介して補助入力装置１０２が携帯電話１０３にデータ送信可能に接続されている。そして、ユーザがペン等の筆記媒体を用いて補助入力装置１０２の入力部１０４上に文字を筆記する。
【００８３】
この状態で、入力部１０４上で描かれた文字が、入力部１０４によって検知された筆記情報である文字パターンを、図示していない制御手段に入手される。ここでは、図１０に示すように、制御手段が手書き文字１１０（「ア」）の文字パターンを入手したとする。
【００８４】
次に、制御手段は入力部１０４で得られた文字パターンを、図示していない文字認識手段に送り、文字認識手段では、たとえば、「特開平９−１９８４６６：オンライン文字認識方法およびオンライン文字認識装置」に開示されたオンライン文字認識技術を用いて、得られた文字パターンを認識し、文字認識結果を出力する。ここでは、図１１に示す文字認識結果１３３が得られたとする。
【００８５】
このうに、手書き文字１１０の入力に基いて、図１１に示す候補文字データを選択する場合に、本発明に係るデータ検索装置を適用することができる。
【図面の簡単な説明】
【００８６】
【図１】実施の形態１に係るデータ検索方法を実現する装置の構成を示す概略ブロック図である。
【図２】データベースに記憶されている、クラスタリングされたデータの様子を示す概念図である。
【図３】候補クラスタ選択手段における処理の流れを示すフローチャートである。
【図４】候補クラスタ選択手段における処理により、変化するデータの様子を示す図である。
【図５】グループ分割・候補データ選択手段における処理の流れを示すフローチャートである。
【図６】グループ分割・候補データ選択手段における処理により、変化するデータの様子を示す図である。
【図７】上位候補選択手段における処理の流れを示すフローチャートである。
【図８】上位候補選択手段における処理により、変化するデータの様子を示す図である。
【図９】実施の形態２に係るグループ分割・候補データ選択手段における処理により、変化するデータの様子を示す図である。
【図１０】本発明に係るデータ検索装置の適用例を説明するための図である。
【図１１】本発明に係るデータ検索装置の適用例を説明するための図である。
【符号の説明】
【００８７】
１  データ入力手段、２  データベース、３  候補クラスタ選択手段、４  グループ分割・候補データ選択手段、５  上位候補選択手段、６  出力手段、１０  入力データ、４０  計算結果、４１，４７，４８，５０  ソート結果、４２  クラスタリスト、４３，４２ａ  第一のグループ、４４，４２ｂ  第二のグループ、４２ｃ  第三のグループ、４５，４６  類似度結果、Ｃ１〜Ｃｎ  クラスタ、ａ１〜ａｎ  代表値、ｄ１〜ｄｎ  データ群、４９  上位候補リスト、５１  最終候補データ。
【図１】
2005063100.tif 000003
【図２】
2005063100.tif 000004
【図３】
2005063100.tif 000005
【図４】
2005063100.tif 000006
【図５】
2005063100.tif 000007
【図６】
2005063100.tif 000008
【図７】
2005063100.tif 000009
【図８】
2005063100.tif 000010
【図９】
2005063100.tif 000011
【図１０】
2005063100.tif 000012
【図１１】
2005063100.tif 000013