| 内容要旨 | | 画像と全文データの内容に対する検索はデータベースの応用として注目され,盛んに研究されている.特徴ベクトルの記述法を用いて,画像と全文データの内容を表す手段は主流となりつつある.そこで,特徴ベクトルのインデックス構築方法は,画像と全文データの内容検索に対して如何に高速化できるかの鍵となる.本研究では,このような課題に関して新しい特徴ベクトルのインデックスモデルを取り上げ,深く検討していた.そこで, 1. 特徴ベクトルのインデックスを構築する従来のクラスタリング法の長所を継承する上,実際の応用にとってより便利に使える新たなインデックス法,再帰的クラスタリング法を取り上げた. 2. 再帰的クラスタリング法で構築した特徴ベクトルのインデックスに適応する探索手法を検討した.この方法によって,検索処理の高速化を実現する同時に,従来の手法で未解決の課題,探索処理中検索対象の漏れの問題を解決した. 再帰的クラスタリングは相互間の類似性によって特徴ベクトルのインデックスを構築する手法である.再帰的クラスタリングで特徴ベクトルのインデックスを構築する際,クラスタ内の特徴ベクトルの数が決めた数値以下に至るまで特徴ベクトルを互いの類似度合いに依り繰り返しグルーピングする.その間,異なるレベルのクラスタが生成される.このように生成されたクラスタを互いの上位と下位関係に依り連結し,Cluster-treeという特徴ベクトルの木構造のインデックスが構成される. 実験検証の結果によると,Cluster-treeの平均探索コストは枝の数とほとんど関係せず,単に検索範囲の変化にだけ依存するという良い性質を持つ.そのため,Cluster-treeの枝の数は単に実際のアプリケーションのニーズ,例えば,二次記憶装置の1ページ中に記録できるCluster-treeの中間ノードの最大数に応して,あるいは実際の特徴ベクトルの分布状態によって設定することができる.この優れた特性があるこそ,実際の応用にとってかなり便利になる. 本モデルでは,再帰的クラスタリング法で構築したCluster-treeに適用する探索処理手法を検討する際,n次元の包囲球というクラスタの記述法を導入した.この記述法は従来の単なるクラスタ中心を用いた記述法と比べ,クラスタ中の特徴ベクトルの分布範囲を有限空間領域で明確に確定するため,Cluster-treeの探索処理において検索対象を絞る判断基準を簡単な数式でまとめることができる.そして,具体的なデータ対象に依存せず一般的な標準探索方式を求めることは可能になった. 特徴ベクトルの様々な分布状態および具体的な検索サンプルに依存しないクラスタリング法で作った特徴ベクトルのインデックスにとって,ある具体的な検索条件と関連する検索対象が複数のクラスタ,つまり複数の部分木の中に分布することがありうる.このような現象が存在するこそ,従来の木構造インデックスの探索手法はクラスタリングで構築したインデックスの探索に対して適用しない.この問題をめくって多くの研究によっていくつかの案が上げられたが,今まで発表された研究結果を考察してみると,検索対象の漏れの問題を根本的に解決する方法は示されていなかった. 本モデルは,クラスタの包囲球と検索範囲のn次元空間中の位置関係を利用して,すべての検索対象を速く絞り出す方法,排除探索法を取り上げた.この探索方針を導入することによって,特徴ベクトルの記述手法を用いた類似検索の高速化を実現できた一方,従来の探索処理法に残されている検索対象の漏れの問題をうまく解決した.多くの実験検証結果によると,このモデルは従来の手法と比べ,特徴ベクトルの記述法を用いた画像と全文データベースの類似検索処理の有効性と効率性を改善することを実現した.検索対象の数がデータベース中のデータ総件数に占める割合が10%以下の場合,同じ検索対象の漏れの問題を持たない線形探索法と比べ,本モデルの必要な検索コストは約三分の一しか取らない. |
| 審査要旨 | | 本論文は、「類似検索における特徴ベクトルの索引法」と題し、画像データや全文データのように、多次元ベクトルで表現され、曖昧さや多義性を持つ情報を検索する場合に、検索サンプルに類似するデータを網羅的に探索しこれを抽出する手法である類似検索を実現するための、インデックスの構築手法とデータ探索手法を開発した成果を述べたものであり、6章から構成されている。 第1章は「序論」であり、本研究の主題である類似検索の必要性、従来の種々の研究結果とその限界、本研究の目的とその研究課題について述べている。 第2章は「本モデルに関連する基本概念」と題し、本研究における検索モデルの骨子について述べている。すなわち、特徴ベクトルによるインデックスを再帰的クラスタリングによって構成する基本的な概念について述べると共に、排除探索方式を導入することによってトップダウン手法を用いた効率的な類似検索が可能となることを述べている。 第3章は「Cluster-tree」と題し、多次元データベース構築のための手段であるインデキシング手法について、新たに導入した再帰的クラスタリング手法の具体的なアルゴリズムとその記述法および結果として構成されるクラスタツリーの特徴について述べると共に、その処理コストについて詳細な評価を試み、従来の手法に比較すると分類コストにおいて、再帰的クラスタリング手法が優れていることを示している。 第4章は「排除探索」と題し、再帰的クラスタリング手法で構成したクラスタツリーに対し、従来の探索手法では非効率であった検索問題が本研究で提案した排除探索を適用することによって効率化されたことを示している。すなわち、クラスタ記述において包囲球という新しい概念を導入し、全体の検索範囲を再帰的に縮小しながら検索範囲外のデータを部分木単位で排除するという手法について説明し、その有効性を論理的に示している。また検索コストの減少をはかる改善手法を導入し、その効果について述べている。 第5章は「実装と性能検証」であり、シルエット画像データと、英文全文テキストデータを例に取り、類似検索方式を実装したシステムの詳細について述べると共に、その性能について検証し、本方式の有効性を示している。すなわち、本方式と従来の検索方式の各々における検索コストを実データを用いて比較することによって本方式の優位性を実証している。また、実際の検索において起こりうる特異な探索条件での問題点についても言及し、これを改善する手法について述べると共に大幅な効率化が実現できることを示している。 第6章は「結論」であり、本研究で導入された新しいモデルの有効性について評価すると共に、従来の手法に比して改善された点について考察している。 以上これを要するに、本論文は曖昧さや多義性を有するデータからなるデータベースの検索を可能とする類似検索手法を導入し、そのデータ構築手法、データ検索手法の具体的なアルゴリズムを提案すると共に、その性能評価を行なうことによって方式の有用性を示したものであり、電子工学上貢献するところが大きい。 よって本論文は東京大学工学系研究科電子工学専攻における博士(工学)の論文審査に合格と認められる。 |