(57)【要約】【課題】データのマッチングを効率的に行う。【解決手段】複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出する際に、データマッチングの対象となる多次元のデータ群に基づいて１次元自己組織化マップを作成し、多次元インデキシングを行い、２次記憶部上の連続した領域に多次元データを保持する。マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索し、そのユニットの近傍に位置するユニットを１次元自己組織化マップから選択し、これに属する多次元データを２次記憶部から参照し、ベクトル間の距離計算を行い、計算結果に対し所定の処理を行って出力する。１次元自己組織化マップから得られる情報で探索範囲を限定することにより、きわめて高速な最近傍検索が可能となる。【選択図】　図５
2004046612.tif 000002
【特許請求の範囲】
【請求項１】
複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するデータマッチング方法において、
データマッチングの対象となる多次元のデータ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成するステップと、
前記作成された１次元自己組織化マップに基づいて多次元インデキシングを行い、２次記憶部上の連続した領域に多次元データを保持するステップと、
前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索するステップと、
前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択するステップと、
前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行うステップと、
上記ベクトル距離計算の結果に対し所定の処理を行って出力するステップと、を備えることを特徴とするデータマッチング方法。
【請求項２】
前記１次元自己組織化マップの作成ステップが、入力層がすべてのユニットと結合されており、各ユニットには入力層に入力されるデータと同じ次元数の参照ベクトルが対応している自己組織化ネットワークにおいて、
入力層に入力されたベクトルと最も近い参照ベクトルを持つユニットを検索するステップと、
前記検索されたユニットとその近傍にあるユニットの参照ベクトルを入力ベクトルに近づけるステップと、
を備えることを特徴とする請求項１記載のデータマッチング方法。
【請求項３】
前記１次元自己組織化マップの学習アルゴリズムが、
参照ベクトルをランダムな値で初期化するステップと、
入力ベクトルに最も近い参照ベクトルを持つユニットを検出するステップと、前記検出されたユニットおよびその近傍領域の参照ベクトルを更新するステップと、
参照ベクトルが収束するまで上記ステップを繰り返すステップと、
を備えることを特徴とする請求項２記載のデータマッチング方法。
【請求項４】
前記データマッチングが、指定された検索条件に適合するデータの検索であることを特徴とする請求項１から３のいずれか記載のデータマッチング方法。
【請求項５】
前記検索されるデータが文書データ、静止画または動画である画像データ、音声データのいずれかもしくはこれらの組み合わせであることを特徴とする請求項４記載のデータ検索方法。
【請求項６】
前記データマッチングが、画像のパターン認識であることを特徴とする請求項１から３のいずれか記載のデータマッチング方法。
【請求項７】
前記データマッチングが、データマイニングであることを特徴とする請求項１から３のいずれか記載のデータマッチング方法。
【請求項８】
複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するデータマッチング装置において、
データマッチングの対象となる多次元のデータ群を保持するデータベースと、前記データベースに保持された多次元データ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成するための演算部と、
前記演算部で作成された１次元自己組織化マップに基づいて多次元インデキシングを行うための主記憶部と、
前記主記憶部で実行された多次元インデキシングに基づいて、多次元データを連続した領域に保持する２次記憶部と、
を備え、前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索し、前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択し、前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行い、上記ベクトル距離計算の結果に対し所定の処理を行って出力することを特徴とするデータマッチング装置。
【請求項９】
複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するデータマッチングプログラムにおいて、
データマッチングの対象となる多次元のデータ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成する処理と、
前記作成された１次元自己組織化マップに基づいて多次元インデキシングを行い、２次記憶部上の連続した領域に多次元データを保持する処理と、
前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索する処理と、
前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択する処理と、
前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行う処理と、
上記ベクトル距離計算の結果に対し所定の処理を行って出力する処理と、
をコンピュータに実行させるためのデータマッチングプログラム。
【請求項１０】
前記請求項９に記載のデータマッチングプログラムを格納したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、１次元自己組織化マップを用いた高次元データの高速近傍検索によるデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
近年のコンピュータなど電子計算機の高性能化、記憶容量の大容量化および低価格化により、情報の電子化、ＩＴ化の急速な普及が進み、電子化されたデータが利用される機会が飛躍的に増大した。電子化されたデータは紙のデータに比較して複製や加工、共有が容易であり、しかも検索の面などで優れている。特に最近ではインターネットの普及により、文書のみならず画像や映像、音声データなどのマルチメディアデータが頻繁に扱われるようになった。このような背景において、所望のデータやこれに類似するデータの検索や分類、整理などの技術が重要となっている。ここでは、マルチメディアデータの検索、データマイニング、パターン認識、機械学習、コンピュータ・ビジョン、統計データ解析などを含めてデータマッチングと呼ぶ。
【０００３】
データマッチングをコンピュータで行う際、マルチメディアデータはコンピュータ内部では特徴量のベクトルで表現することができる。特徴量のベクトルは、指定された検索条件に類似するデータをデータベース中から検索する際にも利用できる。図１に特徴量ベクトルを利用したマルチメディア・コンテンツ検索の一例を示す。類似検索を行う検索条件として特徴量のベクトルを指定すると、検索の実行は検索条件のベクトルとデータベース中のベクトルの距離を計算し、距離の小さいものを検索結果として出力する。このように、条件として与えられたベクトルとの距離が小さいベクトルをデータベース中から検索することを、最近傍検索（ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｓｅａｒｃｈ）と呼ぶ。最近傍検索では、複数の特徴量を多次元ベクトルで表現し、ベクトル間の距離によりデータ同士の類似性を判定している。例えば、文書検索の場合には、索引語の重みベクトルで文書や検索条件を表現することができる。また画像の類似検索の場合には、カラーヒストグラム、テクスチャ特徴量、形状特徴量などから成る特徴量ベクトルにより画像データを表現する。
【０００４】
このような特徴量ベクトルに基づくコンテンツの類似検索として、線形探索が知られている。線形探索では、データベース中のすべてのデータに関する特徴量ベクトルを検索条件のベクトルと逐次的に比較するため、データベースの規模に比例した計算量が必要となる。計算量の増大は計算機側の処理の負担の増大、要処理時間の増大に繋がる。このため、データベースが大規模化した際の検索システムの処理効率に深刻な影響を及ぼすことになる。したがって、最近傍検索を効率的に行なうための多次元インデキシング技術の開発が、重要な課題として従来より活発に研究されてきた。
【０００５】
【発明が解決しようとする課題】
しかしながら、このような研究にも拘わらず決定的な方式は開発されていない。特徴量ベクトルの次元数は非常に大きいため、高次元空間における効率的な多次元インデキシング技術の開発は容易でない。
【０００６】
例えば、ユークリッド空間における多次元インデキシング手法には、Ｒ−ｔｒｅｅ、ＳＳ−ｔｒｅｅ、ＳＲ−ｔｒｅｅなどが提案されている。また、より一般的な距離空間を対象にしたインデキシング手法としては、ＶＰ−ｔｒｅｅ、ＭＶＰ−ｔｒｅｅ、Ｍ−ｔｒｅｅなどが提案されている。これらのインデキシング手法は、多次元空間を階層的に分割することにより、探索範囲を限定することを基本としている。探索範囲を限定すれば、その分だけ計算量も少なくて済む。しかしながら、高次元空間では、ある点の最近点と最遠点との間に距離的な差が生じなくなるという現象が起こる。この「次元の呪い（ｃｕｒｓｅ　ｏｆ　ｄｉｍｅｎｓｉｏｎａｌｉｔｙ）」として知られる現象によって、探索する領域を限定することができなくなり、結果として線形探索に近い計算量が必要になってしまうという問題点がある。
【０００７】
高次元空間における上記の問題点に対処するために、近似的な最近傍検索についても研究が進められている。たとえば、ハッシュ法に基づく近似検索手法や空間充填曲線（ｓｐａｃｅ−ｆｉｌｌｉｎｇ　ｃｕｒｖｅ）を用いて、高次元空間の点を索引付けする手法なども提案されているが、実用化には至っていない。
【０００８】
一方、文書データ（テキスト）と画像データが混在するクロスメディア情報検索では、一度の検索で所望の検索結果を得ることが困難であり、ユーザは複数回のやりとりによって所望の検索結果を得ることが多々ある。したがって、クロスメディア情報検索では特徴量ベクトルに基づく最近傍検索の実行回数が必然的に多くなってしまう。このような場合、完全な最近傍検索は必要ではなく、むしろ高速な近似的な最近傍検索のほうが望ましいということができる。
【０００９】
さらに、近年の肥大化したデータベース中からの検索においては、高速なＲＡＭなどの半導体メモリのみで処理することができず、より大容量であるがアクセス速度の劣るハードディスクなどの２次記憶媒体を使って行われることが一般的である。この場合、ハードディスクへのアクセス速度は半導体メモリに比べて極めて遅いため、ハードディスクへのアクセス速度がボトルネックとなって検索処理速度を上げることができないという問題もあった。
【００１０】
本発明は、このような問題を解決するためになされたものである。本発明の主な目的は、近似的な最近傍検索として１次元自己組織化マップを利用し、さらに２次記憶媒体へのアクセスを効率化することによって高効率かつ高速なデータマッチングを実現可能なデータ検索装置、データ検索方法、データ検索プログラムおよびコンピュータで読み取り可能な記録媒体を提供することにある。
【００１１】
【課題を解決するための手段】
上記の目的を達成するために、本発明の請求項１に記載されるデータマッチング方法は、複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するデータマッチング方法に関する。このデータマッチング方法は、データマッチングの対象となる多次元のデータ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成するステップと、前記作成された１次元自己組織化マップに基づいて多次元インデキシングを行い、２次記憶部上の連続した領域に多次元データを保持するステップと、前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索するステップと、前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択するステップと、前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行うステップと、上記ベクトル距離計算の結果に対し所定の処理を行って出力するステップとを備えることを特徴とする。
【００１２】
また、本発明の請求項２に記載されるデータマッチング方法は、前記請求項１に記載される特徴に加えて、前記１次元自己組織化マップの作成ステップが、入力層がすべてのユニットと結合されており、各ユニットには入力層に入力されるデータと同じ次元数の参照ベクトルが対応している自己組織化ネットワークにおいて、入力層に入力されたベクトルと最も近い参照ベクトルを持つユニットを検索するステップと、前記検索されたユニットとその近傍にあるユニットの参照ベクトルを入力ベクトルに近づけるステップとを備えることを特徴とする。
【００１３】
さらに、本発明の請求項３に記載されるデータマッチング方法は、上記請求項２に記載される特徴に加えて、前記１次元自己組織化マップの学習アルゴリズムが、参照ベクトルをランダムな値で初期化するステップと、入力ベクトルに最も近い参照ベクトルを持つユニットを検出するステップと、前記検出されたユニットおよびその近傍領域の参照ベクトルを更新するステップと、参照ベクトルが収束するまで上記ステップを繰り返すステップとを備えることを特徴とする。
【００１４】
さらにまた、本発明の請求項４に記載されるデータマッチング方法は、上記請求項１から３のいずれかに記載される特徴に加えて、前記データマッチングが、指定された検索条件に適合するデータの検索であることを特徴とする。
【００１５】
さらにまた、本発明の請求項５に記載されるデータマッチング方法は、上記請求項４に記載される特徴に加えて、前記検索されるデータが文書データ、静止画または動画である画像データ、音声データのいずれかもしくはこれらの組み合わせであることを特徴とする。
【００１６】
さらにまた、本発明の請求項６に記載されるデータマッチング方法は、上記請求項１から３のいずれかに記載される特徴に加えて、前記データマッチングが、画像のパターン認識であることを特徴とする。
【００１７】
さらにまた、本発明の請求項７に記載されるデータマッチング方法は、上記請求項１から３のいずれかに記載される特徴に加えて、前記データマッチングが、データマイニングであることを特徴とする。
【００１８】
また、本発明の請求項８に記載されるデータマッチング装置は、複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するものである。このデータマッチング装置は、データマッチングの対象となる多次元のデータ群を保持するデータベースと、前記データベースに保持された多次元データ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成するための演算部と、前記演算部で作成された１次元自己組織化マップに基づいて多次元インデキシングを行うための主記憶部と、前記主記憶部で実行された多次元インデキシングに基づいて、多次元データを連続した領域に保持する２次記憶部とを備える。さらに、前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索し、前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択し、前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行い、上記ベクトル距離計算の結果に対し所定の処理を行って出力することを特徴とする。
【００１９】
さらに、本発明の請求項９に記載されるデータマッチングプログラムは、複数の特徴量を持ちこれらの特徴量をベクトルで表現可能な多次元のデータに対し、条件を指定して所望のデータを抽出するデータマッチングプログラムに関する。このデータマッチングプログラムは、データマッチングの対象となる多次元のデータ群に基づいて、同じ次元数の参照ベクトルを備えるユニットに分割した１次元自己組織化マップを作成する処理と、前記作成された１次元自己組織化マップに基づいて多次元インデキシングを行い、２次記憶部上の連続した領域に多次元データを保持する処理と、前記所望のデータを抽出するマッチング条件をベクトルとして表現し、マッチング条件ベクトルに最も近い参照ベクトルを持つユニットを１次元自己組織化マップから検索する処理と、前記１次元自己組織化マップから検索されたユニットの近傍に位置するユニットを１次元自己組織化マップから選択する処理と、前記選択されたユニットに属する多次元データを前記２次記憶部から参照し、ベクトル間の距離計算を行う処理と、上記ベクトル距離計算の結果に対し所定の処理を行って出力する処理とをコンピュータに実行させる。
【００２０】
さらに、本発明の請求項１０に記載されるコンピュータで読み取り可能な記録媒体は、前記請求項９に記載されるデータマッチングプログラムを格納するものである。記録媒体には、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷやフレキシブルディスク、磁気テープ、ＭＯ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、ＤＶＤ＋Ｒなどの磁気ディスク、光ディスク、光磁気ディスク、半導体メモリその他のプログラムを格納可能な媒体が含まれる。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて説明する。ただし、以下に示す実施の形態は、本発明の技術思想を具体化するためのデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体を例示するものであって、本発明はデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体を以下のものに特定しない。
【００２２】
さらに、この明細書は、特許請求の範囲を理解し易いように、実施の形態に示される部材に対応する番号を、「特許請求の範囲の欄」、および「課題を解決するための手段の欄」に示される部材に付記している。ただ、特許請求の範囲に示される部材を、実施の形態の部材に特定するものでは決してない。なお、各図面が示す部材の大きさや位置関係などは、説明を明確にするため誇張していることがある。
【００２３】
本明細書において、データマッチングの対象となるデータには、テキストなどの文書データ、静止画または動画である画像データ、音楽や演奏、公演、スピーチなどの音声データといったマルチメディアデータが含まれる。またデータマッチングには、文書や映像といった単独種類のデータもしくは複数種類のデータが混在するデータベース中からのマルチメディアデータの検索、データマイニング、パターン認識、機械学習、コンピュータ・ビジョン、統計データ解析などが含まれる。ここでデータマイニングとは、統計的・数理的な手法により、多様で大量のデータから自動的に有用な情報を発見する処理を指す。有用な情報には、データの傾向、パターン、相関関係、規則などが含まれる。データマイニングで使われる手法には、統計的データ解析、決定木、ニューラルネットワークなどがあり、これらの手法ではデータを多次元のベクトルで表現することが多い。このような場合において、あるデータに類似したデータを探すための処理に、本発明の最近傍探索を利用することができる。
【００２４】
［特徴量ベクトル］
本明細書において特徴量ベクトルには、電子データ（メディア・コンテンツ）の種類に応じて様々なものが設定できる。様々なメディア・コンテンツに従った検索を行う場合、データベース中に含まれるメディア全体の内容すなわちデータそのものを用いると、非常に大規模なデータを取り扱わなければならない。そのため、データコンテンツの内容を顕著に表す特徴量を使用する。特徴量は多次元ベクトル形式の特徴量ベクトルとして表す。ここで多次元について説明すると、データがｎ個の属性の性質を持ち、ｎ個の属性値の並びにより表現されるとき、このデータをｎ次元データと呼び、各データはｎ次元空間内に配置される。一般にｎが大きい場合を多次元データと呼び、各データを検索する際には多次元空間内を検索することとなる。
【００２５】
文書コンテンツを表す特徴量としては、文書内に出現する単語の内、文書内容を顕著に表す単語を索引語として抽出し、その索引語の頻度を特徴量として用いる。
【００２６】
画像コンテンツを表す特徴量としては、色情報、形状情報、テクスチャ情報が用いられる。色情報は、ＲＧＢ表色系やＣＩＥ　Ｌａｂ表色系などに従って画像内の色分布をヒストグラムに変換したものを多次元ベクトルとする。形状情報、テクスチャ情報は、Ｗａｖｅｌｅｔ変換などで周波数分解した値を多次元ベクトルとする。
【００２７】
映像コンテンツを表す特徴量としては、各画像間の動きベクトルの大きさを多次元ベクトルで表現し、映像の特徴量とする。
【００２８】
音楽コンテンツを表す特徴量としては、音楽内に現れる各音の音高を基に、音高の時間的推移や音高差の分布を多次元ベクトルで表現したものを特徴量として用いる。
【００２９】
また、多次元ベクトルでコンテンツ特徴量を表現し、コンテンツが類似したデータを検索する技術は、上記のマルチメディア情報検索分野だけに限らず、データマイニング、パターン認識、機械学習、コンピュータ・ビジョン、統計データ解析のような幅広い分野で利用されている。これらの分野では、データが有する様々な属性の値が、そのデータの特徴量として多次元ベクトルで表現されている。
【００３０】
本明細書においてデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体は、データマッチングを行うシステムそのもの、ならびにデータマッチングに関連する入出力、表示、演算、通信その他の処理をハードウェア的に行う装置や方法に限定するものではない。ソフトウェア的に処理を実現する装置や方法も本発明の範囲内に包含する。例えば汎用の回路やコンピュータにソフトウェアやプログラム、プラグイン、オブジェクト、ライブラリ、アプレット、コンパイラなどを組み込んでデータマッチングそのものあるいはこれに関連する処理を可能とした汎用あるいは専用のコンピュータ、ワークステーション、端末、携帯型電子機器、ＰＤＣやＣＤＭＡ、Ｗ−ＣＤＭＡ、ＦＯＲＭＡなどの携帯電話、ＰＨＳ、ＰＤＡ、ページャ、スマートフォンその他の電子デバイスも、本発明のデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体の少なくともいずれかに含まれる。また本明細書においては、プログラム自体もデータマッチング装置に含むものとする。
【００３１】
本発明の実施例において使用されるコンピュータなどの端末同士、およびサーバやこれらに接続される操作、制御、表示、各種処理その他のためのコンピュータ、あるいはプリンタなどその他の周辺機器との接続は、例えばＩＥＥＥ１３９４、ＲＳ−２３２ＣやＲＳ−４２２、ＵＳＢなどのシリアル接続、パラレル接続、あるいは１０ＢＡＳＥ−Ｔ、１００ＢＡＳＥ−ＴＸなどのネットワークを介して電気的に接続して通信を行う。接続は有線を使った物理的な接続に限られず、無線ＬＡＮやＢｌｕｅｔｏｏｔｈなどの電波、赤外線、光通信などを利用した無線接続などでもよい。さらに観察像のデータ保存などを行うための記録媒体には、メモリカードや磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどが利用できる。
【００３２】
［データマッチング装置］
以下、本発明に係るデータマッチングの一実施例として、マルチメディアデータの検索に利用した例を図２に基づいて説明する。この図に示すデータマッチング装置１は汎用あるいは専用のコンピュータなどが利用でき、演算部２と主記憶部３と２次記憶部４を備える。演算部２はＣＰＵやＭＰＵ、システムＬＳＩやＩＣなどで構成され、自己組織化マップの作成や特徴量ベクトルの距離計算その他の必要な演算を実行する。演算部２はこれらの処理が可能なようにハードウェア的に構成することもでき、または演算プログラムを実行させてソフトウェア的に実現させてもよい。主記憶部３は、高速な汎用もしくは組み込みメモリで構成され、ＳＤＲＡＭ、ＤＤＲＲＡＭ、ＲＤＲＡＭ、ＥＤＯＲＡＭ、ファーストページＲＡＭといったＲＡＭ等の半導体メモリが利用できる。２次記憶部４はハードディスク（固定ディスク）などの二次記憶媒体で構成され、主記憶部３に比べ大容量のものを使用する。ディスクアクセス速度は速いほど好ましいが、一般に主記憶部３に比して遅い。さらにデータマッチング装置１には必要に応じてマウスやキーボードなどの入力部５が接続される。
【００３３】
データベース６は、検索対象のデータを保存する記憶媒体であり、大容量のハードディスクなどが利用される。一般にはサーバ側のホストコンピュータに内蔵あるいは接続されており、データマッチング装置１と通信可能に接続されている。またデータベース６は、データマッチング装置１内部に備えることもでき、さらに２次記憶部４と兼用することもできる。
【００３４】
データベース６中から所望のデータを検索するための検索条件の入力は、直接特徴量のベクトルを指定する他、予めキーワードを設定しておき、入力されたキーワードに応じた特徴量ベクトルに変換して検索条件とすることもできる。この変換はデータマッチング装置１内部で行われるため、ユーザは特徴量ベクトルを意識することなくキーワードで検索することができる。
【００３５】
検索条件の入力は、データマッチング装置１がスタンドアロンで運用される場合は、入力部５から入力される。またネットワークで運用される場合は、さらにネットワーク接続されたクライアント側のコンピュータや携帯電話などの端末７から入力する。ネットワーク接続としてはＬＡＮやＷＡＮ、インターネットなどが利用できる。この形態では、データマッチング装置１がサーチエンジンとして機能し、各端末から入力された検索条件に対して検索を行った結果をそれぞれの端末に出力する。
【００３６】
［自己組織化マップ］
本発明の実施例では、マルチメディアデータの検索に１次元自己組織化マップを用いて、高速な近似的最近傍検索を行った。自己組織化マップは、高次元空間での近傍関係を可能な限り維持しつつ、低次元空間に高次元のデータを配置するという特性を持っている。一般には、高次元データを２次元上に配置し、人間が相互の配置関係を視覚的に把握できるようにしている。例えば特開平１１−１２０１８０号公報では、自己組織化マップを用いて２次元平面上にデータを配置することにより、類似関係を人間の目で視覚的に把握しやすい位置関係に表す例が示されている。このように自己組織化マップを用いる例では、２次元平面上への展開が一般的である。
【００３７】
これに対し本発明においては、２次元自己組織化マップではなく１次元自己組織化マップにデータを写像した。この理由は、近傍検索の検索時間の効率を向上させるためである。仮に２次元自己組織化マップ上にデータを写像した場合、あるデータの近傍に存在するデータを検索するためには、隣接する８方向についてユニットにアクセスしなければならない。これだと単にアクセス数が増加するだけでなく、不要なデータが多く検索対象となってしまい、時間効率が悪化する。
【００３８】
これに対し１次元自己組織化マップに写像した場合、左右２方向のユニットにだけアクセスすればよく、アクセス数が軽減する。また後述するように、各ユニットのデータを順次２次記憶上に配置することにより、２次記憶上をランダムにアクセスすることなく、ユニットに対応したデータを一括して取得することができるようになり、近傍検索の検索時間効率の向上が望める。また写像処理（マッピング）に要する時間についても、２次元マップを１次元マップとすることでユニット数が減る場合には使用する参照ベクトルも少なくなるためマッピング時間も軽減する。以上のように、本発明では２次元上でなく１次元上に配置することで、より簡素かつ高速な処理を可能としている。さらに後述するように、１次元上に写像する近似でも、精度の低下は殆ど問題とならず、むしろ精度が向上しているとも言えることが実験により確認された。
【００３９】
自己組織化マップ（ｓｅｌｆ−ｏｒｇａｎｉｚｉｎｇ　ｍａｐ：ＳＯＭ）は、教師なし競合学習により、高次元データを低次元データに写像する２階層型のニューラルネットワークである。自己組織化マップでは、高次元空間での近傍関係をできる限り保ちつつ、低次元空間へデータを配置するという位相的整列性と呼ばれる特徴を持っている。自己組織化マップの典型的な適用例は、多次元データの可視化であり、この場合には高次元データを２次元平面上に配置することを行なう。
【００４０】
図３は、ｎ次元の入力データを２次元平面上に配置する自己組織化ネットワークの例を示している。ネットワークの入力層は、２次元平面上に格子状に配置されたすべてのユニットと結合されており、各ユニットには、入力層に入力されるデータと同じ次元数の参照ベクトル（ｒｅｆｅｒｅｎｃｅ　ｖｅｃｔｏｒ）ｍ１〜６が対応している。学習の過程では、入力層に入力されたベクトルと最も近い参照ベクトルを持つユニットを探し、このユニットとその近傍にあるユニットの参照ベクトルを入力ベクトルに近づけるという操作を繰り返す。このようにして、同じような位相的特徴を持ったユニットが近傍領域に集まり、結果的に入力データの位相的特徴を反映した自己組織化マップが作られることになる。
【００４１】
［自己組織化マップの学習アルゴリズム］
上記の自己組織化マップの学習アルゴリズムを図４のフローチャートに基づいて説明する。
（ステップＳ１）参照ベクトルｍｉをランダムな値で初期化する。
（ステップＳ２）入力ベクトルｘに最も近い参照ベクトルｍｃを持つユニットｃを見つける。その際の計算式は、以下の数１のようになる。
【００４２】
【数１】
2004046612.tif 000003
【００４３】
（ステップＳ３）ユニットｃおよびｃの近傍領域の参照ベクトルｍｉを以下の数２により更新する。ここで、ｈｃｉはユニットｃから離れるにつれ、小さな値になるように設定する。また、ｈｃｉは学習が進むにつれ、単調に減少するようにする。
【００４４】
【数２】
ｍｉ＝ｍｉ＋ｈｃｉ（ｘ−ｍｉ）
【００４５】
（ステップＳ４）参照ベクトルが収束するまでステップ２に戻って処理を繰り返す。
【００４６】
［自己組織化マップを用いた最近傍検索手法］
以上のようにして作成された自己組織化マップは、高次元空間での近傍関係をできる限り保ちつつ、入力データを低次元空間へ配置することができるという特長を備える。この特長を用いると、高次元空間での最近傍検索を低次元空間での最近傍検索問題に置き換えることができると考えられる。ただ、自己組織化マップの学習には誤差がともなう上、低次元のマップ上では高次元空間での距離が保存されていないため、低次元マップだけを用いて最近傍検索を行うには問題がある。
【００４７】
そこで本発明の実施例では、自己組織化マップにより得られた低次元空間での近傍関係から、最近傍検索の探索範囲を限定し、限定されたデータに関してだけ、元の高次元空間上で距離を計算するという方法を採用した。また、探索範囲の限定を効率的に行なうために１次元の自己組織化マップを用いている。図５に、１次元自己組織化マップを用いた最近傍検索手法の概略を示す。
【００４８】
［多次元インデキシングの作成］
次に図５に基づき、データマッチング装置が１次元自己組織化マップを用いて多次元インデキシングを作成する過程を説明する。
【００４９】
（１）自己組織化マップの学習アルゴリズムにより、多次元データを１次元上に配置する。データマッチング装置１がデータベース６にアクセスし、演算部２はデータベース６に格納されているデータを読み込み、主記憶部３に１次元自己組織化マップを展開する。ユニット数をｋとすると、データはｋ個のクラスタに分割されることになる。
【００５０】
（２）各クラスタに属するデータを、２次記憶部４上の連続した領域に格納する。またこの際、１次元自己組織化マップ上の各ユニットに２次記憶部４上の格納領域を示すポインタを持たせる。なお２次記憶部４には、１次元に変換したデータでなく元の多次元データを格納する。
【００５１】
多次元データをハードディスクなどの２次記憶部４上の連続した領域に格納することで、効率的なアクセスが可能となる。アクセス速度や回数、効率等は、使用するディスクアクセスのアルゴリズムに依存するものの、一般にはディスクへのアクセス要求が生じると、目標となるデータのみならず、その近傍のデータも一括してメモリに取り込まれる。したがって必要なデータがまとまって存在しているほど、一回のアクセスで取り込まれたデータ中に必要なデータが含まれているヒット率は高くなり、結果的にアクセス回数は少なくて済むことになる。これによって効率的なアクセスが実現され、高速化が見込まれる。特にハードディスクのアクセス速度はメモリに比べて極めて遅く、処理速度向上のボトルネックとなっていたため、この部分での効率化は処理速度の劇的な改善をもたらす。
【００５２】
［最近傍検索］
以上のようにして作成された多次元インデキシングを用いて、データマッチング装置は以下の手順で最近傍検索を実行する。
【００５３】
（１）入力された検索条件のベクトルに最も近い参照ベクトルを持つユニットｃを、演算部２は主記憶部３の１次元自己組織化マップから探し出す。
【００５４】
（２）１次元自己組織化マップ中から探し出されたユニットｃの、近傍に位置するユニットを１次元自己組織化マップから選択する。選択されたユニットが保持するポインタに従って、各ユニットに属する多次元データを２次記憶部４から参照し、ベクトル間の距離計算を行う。このようにして、参照ベクトルを持つユニットおよびその近傍に位置するユニットに属するデータに対してのみ、検索条件ベクトルとの距離計算を行う。
【００５５】
（３）上記で計算された結果を、距離の小さい順にソートし、これを最近傍検索の結果として出力する。
【００５６】
以上のようにして、１次元自己組織化マップを用いた最近傍検索の結果が得られる。検索条件ベクトルと比較して距離計算が行われるデータは、２次記憶部４上の連続した領域に格納されているため、２次記憶部４へのアクセスはきわめて効率的に行うことが可能となる。実験の結果、１次元自己組織化マップ上の各ユニットに割り当てられる多次元データの数は大きく偏ることなく、概ね平均化している。したがって、２次記憶部４へのアクセス回数は数回程度に抑えられる。
【００５７】
［距離尺度］
多次元ベクトル間の距離尺度には様々なものがある。本発明の実施例においてはユークリッド距離を用いているが、本発明はこれに限定されるものでない。
【００５８】
一般的に用いられている距離尺度には、Ｌｐノルムあるいはミンコフスキー距離と呼ばれているものがある。これは、数３のベクトルに対して、数４のように定義される。
【００５９】
【数３】
2004046612.tif 000004
【００６０】
【数４】
2004046612.tif 000005
【００６１】
数４において、ｐ＝１の場合を特にマンハッタン距離、またｐ＝２の場合をユークリッド距離と呼ぶ。Ｌｐノルム以外にも、マハラノビス距離などがあるが、自己組織化マップでは通常、ユークリッド距離が用いられる。ただこれら以外にも、ｅａｒｔｈ　ｍｏｖｅｒ’ｓ　ｄｉｓｔａｎｃｅ、ｔａｎｇｅｎｔ　ｄｉｓｔａｎｃｅ、Ｈａｕｓｄｏｒｆｆ　ｄｉｓｔａｎｃｅ、ｕｎｆｏｌｄｅｄｄｉｓｔａｎｃｅなど、様々な距離尺度があり、本発明においても適宜利用できる。
【００６２】
［実施例１］
１次元自己組織化マップを用いた最近傍検索手法の有効性を調べるために、類似画像検索実験と文書検索実験を行った。まず、類似画像検索実験について説明する。類似画像検索実験では、Ｃｏｒｅｌデータベースから抽出した４２，３８１件のカラー写真画像を用いた。また、このうち、４２４件（全体の１％）の画像データをランダムに抽出し、検索画像とした。これらの画像データから、図６に示すような、次元数の異なる４種類の特徴量ベクトルを作成した。
【００６３】
自己組織化マップを用いた最近傍検索の精度を調べるためには、検索された画像のうち、どれが正解であるかという情報が必要である。このため、各検索画像と全画像データとの間のユークリッド距離を線形探索により求め、距離の小さい４００件を正解データとした。与えられた検索画像から、自己組織化マップを用いた最近傍検索により、上位４００件の検索結果を出力し、これを正解データと比較することにより適合率を算出した。
【００６４】
自己組織化マップを用いた最近傍検索では、検索条件によって適合率は変化する。適合率が変化する主な要因は、１次元マップ上の総ユニット数、および、検索の際に用いる近傍数である。ここで、近傍数とは、探索候補の絞り込みの際にいくつのユニットを参照したかを意味しており、具体的には、検索質問の属するユニットに加え、その近傍のユニットをいくつ参照したかを示す。以下では、検索質問の属するユニットのみを参照したときは近傍数１、検索質問の属するユニットに加え、その左右両側のユニットを参照したときは近傍数３というように表すことにする。なお、近傍数３の際、検索質問が１次元マップ上の左端（あるいは右端）のユニットに属している場合には、そのユニットの右側（あるいは左側）しか参照しない。
【００６５】
図７は、ユニット数が１０、近傍数３のときの適合率曲線を、また図８は、ユニット数が２０、近傍数３のときの適合率曲線をそれぞれ示している。横軸方向は検索結果数を、縦軸方向は平均適合率を表しており、グラフは上位ｎ件の結果が検索された時点での平均適合率をプロットしたものである。また図９は、さまざまな条件のもとでの平均Ｒ適合率と検索質問１件当たりの平均距離計算回数を示している。
【００６６】
ここでＲ適合率（Ｒ−ｐｒｅｃｉｓｉｏｎ）とは、検索質問に適合する結果の総数をＲとするとき、上位からＲ番目までの検索結果を出力した時点での適合率を意味する。Ｒ適合率は、上位に順位付けされた検索結果の有効性を示す評価尺度である。
【００６７】
図９から分かるように、同じ検索条件のもとでは、適合率は次元数が大きくなるにつれ低下する傾向にあるが、距離計算回数は次元数によらずにほぼ一定である。したがってこの方法は、次元数が増大した場合にも高速性が失われることはない。なお、距離計算回数が次元数によらず一定である理由は、各ユニットに割り当てられるデータ数が概ね平均化しているためである。図１０に、ユニット数２０の際に各ユニットに割り当てられたデータ数を示すが、１次元マップ上の各ユニットに割り当てられるデータ数が極端にばらついていないことを読み取ることができる。
【００６８】
［実施例２］
以上の実施例１では、類似画像検索を対象にした実験結果を示した。画像特徴量の次元数は、数１０〜数１００次元程度であるが、これよりも次元数が大きい場合の手法の有効性を調べるために、実施例２としてベクトル空間モデル（ｖｅｃｔｏｒ　ｓｐａｃｅ　ｍｏｄｅｌ：ＶＳＭ）に基づく文書検索を対象とした実験を行なった。
【００６９】
文書検索のベクトル空間モデルでは、文書中から索引語を抽出し、文書を索引語の出現頻度に基づくベクトルで表現する。文書ベクトルの次元数は、文書集合全体にわたる索引語の総数と等しいため、次元数はきわめて大きくなる。
【００７０】
この実施例２では、検索対象のデータベースとして、情報検索評価用のテストコレクションであるＭＥＤＬＩＮＥを用いた。ＭＥＤＬＩＮＥは、英文の検索対象文書１，０３３文書、検索質問３０文書から成る小規模なコレクションであり、各検索質問にはどの文書が適合しているかという適合情報が用意されている。なお、各検索質問に対する平均適合文書数は２３．２文書である。
【００７１】
まず前処理として、ＭＥＤＬＩＮＥコレクションから「ａ」や「ａｂｏｕｔ」などの不要語４３９単語、および全文書中に１回しか出現しなかった単語を削除した。その後、ポーター・アルゴリズム（Ｐｏｒｔｅｒ　ａｌｇｏｒｉｔｈｍ）によるステミングを行なった結果、４，３２９個の索引語が得られた。以上の処理により得られた索引語から４，３２９次元の文書ベクトルを構成した。この際、索引語の重み付けとして、局所的重み付けには対数化索引語頻度を、大域的重み付けにはエントロピーを、文書正規化にはコサイン正規化を用いた。
【００７２】
文書検索の評価では、通常のベクトル空間モデルに基づく最近傍検索（線形探索）と自己組織化マップを用いた最近傍検索の両者とも３０件の検索結果を出力し、出力結果をＭＥＤＬＩＮＥの適合情報と比較することにより適合率を求めた。この際、自己組織化マップを用いた最近傍検索では、ユニット数２０、近傍数３の条件で検索を行なった。図１１に、文書検索の適合率曲線を示すが、自己組織化マップを用いた検索のほうがわずかながら良い結果を与えている。なお、ベクトル空間モデルに基づく検索のＲ適合率は０．５３であり、自己組織化マップを用いた検索のＲ適合率は０．５８であった。また、自己組織化マップを用いた最近傍検索の平均距離計算回数は１検索質問当たり１４１回であり、これは線形探索の約１／７に相当する。従って、条件が同一であれば処理時間も約１／７に短縮することができ、高速化が実現される。
【００７３】
以上はＭＥＤＬＩＮＥコレクションの適合情報に対する評価であるが、次に、自己組織化マップによる最近傍検索の近似誤差について述べる。ベクトル空間モデルの検索結果を正解とみなした場合、自己組織化マップを用いた検索結果のＲ適合率は０．６８であった。したがって、上位３０件までの検索では３２％の近似誤差が生じていることになる。しかし、近似誤差があるにもかかわらず、ＭＥＤＬＩＮＥの適合情報に対する評価では、通常のベクトル空間モデルよりも適合率が高くなっている。このことから、最近傍検索を近似するという意味からは結果に若干の誤差があるものの、検索そのものの絶対的な評価として考えれば、通常の最近傍検索よりも精度が高いということができ、処理速度の短縮に加えて精度の面でも優れていることが明らかとなった。
【００７４】
【発明の効果】
以上のように、本発明のデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体は、従来の線形探索方式に比べて、極めて効率的なデータマッチングを実行可能であり、処理に要する計算量を極減し、処理時間を大幅に短縮できるという特長を実現する。それは、本発明のデータマッチング方法、データマッチング装置、データマッチングプログラムおよびコンピュータで読み取り可能な記録媒体が、自己組織化マップを用いて高次元データを従来のような２次元空間でなく、１次元空間上に配置することにより、最近傍検索の検索範囲を限定し、限定された範囲に存在するデータに対してのみベクトルの距離計算を行っているからである。これによって、最近傍検索の検索範囲を大きく削減することができ、膨大なデータベース中のデータすべてに対し逐次的に距離計算を行う線形探索に比べて、計算量を飛躍的に低減できる。
【００７５】
さらに、本発明は１次元空間上に配置された１次元自己組織化マップに基づいて、１次元に変換されたデータでなく高次元のデータを２次記憶媒体上の連続した領域に格納する構成としている。このため、２次記憶媒体から主記憶素子上に読み込まれるデータには連続した一連のデータが含まれることとなり、少ないアクセス回数で必要なデータを取り込むことが可能となり、この結果ディスクアクセスの回数が極めて少なくなり、アクセス速度の遅さがボトルネックとなっていた問題を解消し、高速かつ高効率のデータマッチング処理を可能としている。このため、大規模なデータ集合に対しても、きわめて高速な最近傍検索を行なうことが可能である。
【図面の簡単な説明】
【図１】特徴量ベクトルを利用したマルチメディア・コンテンツ検索の一例を示す概念図である。
【図２】本発明の一実施例に係るデータマッチング装置の一例を示す概略ブロック図である。
【図３】ｎ次元の入力データを２次元平面上に配置する自己組織化ネットワークの一例を示す概念図である。
【図４】自己組織化マップの学習アルゴリズムの一例を示すフローチャートである。
【図５】本発明の一実施例に係る１次元自己組織化マップを用いた最近傍検索を示す概念図である。
【図６】本発明の実施例１に係る画像検索に使用した特徴量ベクトルの概略を示す表である。
【図７】本発明の実施例１に係る画像検索の結果としてユニット数が１０、近傍数３のときの適合率曲線を示すグラフである。
【図８】本発明の実施例１に係る画像検索の結果としてユニット数が２０、近傍数３のときの適合率曲線を示すグラフである。
【図９】本発明の実施例１に係る画像検索の結果として平均Ｒ適合率および平均距離計算回数を示す表である。
【図１０】ユニット数２０において各ユニットに割り当てられたデータ数を示すグラフである。
【図１１】本発明の実施例２に係る文書検索の結果として適合率曲線を示すグラフである。
【符号の説明】
１・・・データマッチング装置
２・・・演算部
３・・・主記憶部
４・・・２次記憶部
５・・・入力部
６・・・データベース
７・・・端末
【図１】
2004046612.tif 000006
【図２】
2004046612.tif 000007
【図３】
2004046612.tif 000008
【図４】
2004046612.tif 000009
【図５】
2004046612.tif 000010
【図６】
2004046612.tif 000011
【図７】
2004046612.tif 000012
【図８】
2004046612.tif 000013
【図９】
2004046612.tif 000014
【図１０】
2004046612.tif 000015
【図１１】
2004046612.tif 000016