近似最近傍探索方法、最近傍探索プログラムおよび装置
【課題】主成分分析に基づく二分木を用いて、最近傍のデータ点を効率的に探索する、近似最近傍探索方法を提供する。
【解決手段】主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベース、およびクエリーベクトルデータが与えられたとき、探索対象クラスターの初期値を前記二分木の根ノードとし、前記クエリーから対象クラスターの平均ベクトルを差引いて補正し、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を、前記対象クラスターに対するクエリー主成分得点とする。前記クエリー主成分得点がゼロ以下ならば、第１子クラスターを、前記クエリー主成分得点が正ならば第２子クラスターを探索クラスターとし、末端の階層に至るまで探索を繰り返す。末端の階層の探索クラスターに属し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする。
【解決手段】主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベース、およびクエリーベクトルデータが与えられたとき、探索対象クラスターの初期値を前記二分木の根ノードとし、前記クエリーから対象クラスターの平均ベクトルを差引いて補正し、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を、前記対象クラスターに対するクエリー主成分得点とする。前記クエリー主成分得点がゼロ以下ならば、第１子クラスターを、前記クエリー主成分得点が正ならば第２子クラスターを探索クラスターとし、末端の階層に至るまで探索を繰り返す。末端の階層の探索クラスターに属し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、主成分分析に基づく二分木を用いた近似最近傍探索方法、最近傍探索プログラムおよびその方法を用いた装置に関する。
【背景技術】
【０００２】
最近傍探索とはデータ集合の中からクエリー（検索質問点）と最も近い距離にあるデータ（最近傍点）を探す問題である。すなわち、d個の数値的特徴を表すためのd次元の距離空間Rd においてn 個のデータの集合S と、それらデータと同じ次元数のクエリー q ∈ Rdが与えられたとき、データの集合S の中からクエリーq と最も近いデータpnn を探索することである。ここで、各データp は距離空間Rd 中の一つの点であり、d次元のベクトルデータで表される。以下で各データをデータ点とも呼ぶ。クエリーも各データと同様に、距離空間Rd 中の一つの点としてd次元のベクトルデータで表される。以下でクエリーをクエリー点とも呼ぶ。
【０００３】
最近傍探索の最も基本的な解法は、データ集合S 内の全データ点 とクエリー点q との距離計算を行い、距離の最も近いものを探索する方法である。これを線形探索という。すべてのデータ点とクエリー点q との距離計算を行う方法は、一般に距離計算の対象となるデータ点の数が多いため、処理の高速化を図った手法がいくつか提案されている。しかし、データ点の数および次元数が大きなデータベースを扱う場合、線形探索に比べて処理時間が大幅に短縮される最近傍探索の手法はほとんどない。
そこで、探索の精度をある程度犠牲にするかわりに処理時間を大幅に短縮する近似最近傍探索の手法が提案されている。近似最近傍探索では探索のエラー率を実用上問題ない程度に抑えながら、線形探索に比べて非常に短い処理時間で最近傍点を探索することができる。
【０００４】
近似最近傍探索の応用例として、物体認識や顔認識が挙げられる。物体認識や顔認識では、予め様々な物体や顔の画像から特徴量をベクトルデータ（データ点）として抽出しデータベースに保存しておく。検索質問として画像が与えられたとき、その画像から同様に特徴量を取り出して、近似最近傍探索のクエリーとする。そして、クエリーに近い特徴量を持つデータ点を出力結果とすることで、そのデータ点が抽出された物体や顔画像を特定する。これによって、物体認識や顔認識が可能となる。
近似最近傍探索の応用分野として、前述の物体認識や顔認識の他に知識発見、データマイニング、機械学習、データ圧縮、マルチメディア・データベース、文書検索および統計処理などが知られている。
【０００５】
近似最近傍探索の代表的な手法として、LSH（Locality Sensitive Hashing）が挙げられる（例えば、非特許文献１参照）。LSHの手法では、データベースに登録すべきデータ点を表すベクトルデータを入力するとスカラ値を出力するハッシュ関数を各データ点に適用し、前記ハッシュ関数から出力される値（ハッシュ値）に基づいてデータ点を分類する。そして、分類されたデータ点のテーブル（ハッシュテーブル）を作成し前記データベースに含めて登録しておく。このハッシュ関数は、ベクトル間距離の近いものが似たハッシュ値をとり、遠いものは似たハッシュ値をとらないように定義される。その結果、近い距離にあるデータ点が同じ類に属するように分類されてハッシュテーブルに登録される。
【０００６】
クエリー点が与えられたとき、そのクエリー点に前記ハッシュ関数を適用してクエリー点のハッシュ値を得る。前記データベースに登録されたデータ点のうち、クエリー点のハッシュ値と等しいハッシュ値の類に属するデータ点のみとの間で距離計算を行う。距離計算の対象となるデータ点は、クエリー点のハッシュ値を用いてハッシュテーブルを参照することで得られる。LSHは、距離計算の対象を特定の類に属するデータ点に限定することによって処理時間を短縮している。
【０００７】
一方、LSHとは異なるアプローチとして、二分木を用いた近似最近傍探索の手法が提案されている（例えば、非特許文献２参照）。
また、データ集合を探索することなく識別を行う手法が提案されており、その中で主成分得点を用いてクラスターを２分割することが記載されている（例えば、非特許文献３〜５参照）。ただし、非特許文献３および４は、データ点の全体集合を二分割することのみが記載されている。非特許文献５は、非特許文献３および４の木の高さを任意の自然数まで拡張したものである。
非特許文献５で、データ点のクラスタリング（分割）に主成分分析（Principal component analysis, PCA）を用いているが、これは、識別精度が分割位置のランダムな選択によって変動するのを防止するためである。より詳細には、主成分得点（Principal Component Score）の正負の符号によるクラスターの２分割を繰り返し行って二分木を生成するが、葉ノード（リーフ）が初期分割である。また、非特許文献５では、クラスタリングのための繰り返しアルゴリズムによって最終的なクラスターが決定され、その中心ベクトルと共分散行列のみが識別器に用いられる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M.Datar, N.Immorlica, P.Indyk and V.S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proc. of the 20th annual symposium on Computational Geometry, pp.253-262, 2004.
【非特許文献２】S.Arya, D.M. Mount, R.Silverman and A.Y. Wu, "An optimal algorithm for approximate nearest neighbor searching," Journal of the ACM, vol.45, no.6, pp.891-923, 1998.
【非特許文献３】H. Ichihashi, A. Notsu and K. Honda, "Semi-hard c-means clustering with application to classifier design," Proc. of the IEEE International Conference on Fuzzy System, World Congress on Computational Intelligence, Barcelona, Spain, pp. 2788-2795, 2010.
【非特許文献４】H. Ichihashi, A. Notsu, K. Honda, T. Katada and M. Fujiyoshi, "Improvement in the performance of camera based vehicle detector for parking lot," Proc. of 2010 IEEE International Conference on Fuzzy System, Barcelona, Spain, Juli. 18-23, 2010.
【非特許文献５】H. Ichihashi, K. Honda and A. Notsu, "Comparison of Scaling Behavior Between Fuzzy c-Means Based Classifier with Many Parameters and LibSVM," Proc. of the IEEE International Conference on Fuzzy Systems, pp. 386-393, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
LSHなど、ハッシュ関数を用いた手法は、距離計算に要する処理時間が短縮されるという利点があるが、ハッシュテーブルを格納するメモリー領域を必要とする。また、各データ点にハッシュ関数を適用して得られるハッシュ値は、一種の乱数と捉えることができ、探索の精度はランダムに変化する。安定した精度を得るためには十分な数のデータ点を探索することが前提となるが、データ点が増加すると探索に要する処理時間も増大するため両者はトレードオフの関係にあるとの見方もできる。
一方、二分木構造を用いた手法は、ハッシュ関数を用いた手法に比べると木構造を保持するために必要なメモリー容量が一般に少なくてすむ。また、ハッシュ関数を用いて乱数を発生させることがないため個々の探索の精度が安定している。しかし、ハッシュ関数を用いた手法に比べると、木構造を辿って探索を行うために要する処理時間が一般的に長くかかると考えられている。しかし、二分木によって距離計算対象とすべきデータ点を効率的に絞り込むことができれば、処理時間を短縮できる。
この発明は、以上のような事情を考慮してなされたものであって、主成分分析（Principal Component Analysis、PCA）に基づく二分木を用いて最近傍のデータ点を効率的に探索して推定し、処理時間の短縮を実現する近似最近傍探索方法、装置およびプログラムを提供する。
【課題を解決するための手段】
【００１０】
この発明は、コンピュータが、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法を提供する。
【００１１】
また異なる観点から、この発明は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置を提供する。
【００１２】
さらに異なる観点から、この発明は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラムを提供する。
【発明の効果】
【００１３】
近似最近傍探索方法は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースを探索するにあたり、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの第一主成分ベクトルとの内積を計算してクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを探索クラスターとし、前記クエリー主成分得点が正ならば第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程とを備えるので、クエリーとの距離計算を行うベクトルデータを絞り込むことができる。クエリー主成分得点はベクトルの内積という単純な計算で得ることができる。よって、最近傍とされるデータ点を効率的に探索できる。
この発明による近似最近傍探索装置および近似最近傍探索プログラムも同様の効果を奏する。
【００１４】
この発明において、クラスターは、同じ類に属するベクトルデータの集合を示すもので、二分木構造のノードに対応する。その具体的な態様の例は、各要素の値がメモリーに格納されたベクトルデータのリストである。
この発明によれば、データベースは平衡な完全二分木の構造を有する。末端の葉ノードのクラスターを除いた各クラスターは、２つの子クラスターをそれぞれ有する。即ち、二分木の根と葉を除いた階層（高さ）にある各クラスターは、根ノード側にあるクラスターの子ノードであると同時に、葉ノード側にあるクラスターの親ノードである。
主成分分析は、複数の変数間の相関を把握するために導入される公知の手法であって、クラスターが与えられたとき第一主成分ベクトルおよび主成分得点（主成分スコアとも呼ばれる）を算出する手法は公知である。例えば、第一主成分ベクトルは、共分散行列の固有値問題を解いて得ることができる。
【図面の簡単な説明】
【００１５】
【図１】この発明に係る二分木を用いたデータ点分割の様子を示す説明図である。
【図２】この発明に係る登録処理を実行するコンピュータの、ハードウェア構成例を示すブロック図である。
【図３】この発明に係る登録処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。
【図４】この発明に係る登録処理によって生成された木構造の一例を示す説明図である。
【図５】この発明に係るデータベースの具体的な構造の例を示す説明図である。
【図６】この発明に係る探索クラスター・テーブルの具体例を示す説明図である。
【図７】この発明に係る探索処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。
【図８】この発明による近似最近傍探索と従来の線形探索との比較実験の結果を示すグラフである。
【発明を実施するための形態】
【００１６】
以下、この発明の好ましい態様について説明する。
この発明によるデータベースの生成方法において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。
【００１７】
さらに、前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。
【００１８】
また、前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする工程、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割工程、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものであってもよい。
【００１９】
前記平均補正工程は、各クラスターについて得られた平均ベクトルを前記データベースの一部として格納し、前記得点算出工程は、各クラスターについて得られた第一主成分ベクトルを前記データベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。
【００２０】
さらに、この発明は、前述したこの発明によるデータベースの生成装置において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。
【００２１】
さらに、前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。
【００２２】
また、この発明によるデータベースの生成装置において、前記平均補正部は、各クラスターについて得られた平均ベクトルをデータベースの一部として格納し、前記得点算出部は、各クラスターについて得られた第一主成分ベクトルをデータベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。
【００２３】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割部、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものであってもよい。
この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。
【００２４】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
≪主成分分析に基づく２分木を用いる近似最近傍探索≫
図１は、この発明に係る二分木を用いたクラスター分割の様子を示す説明図である。クラスター分割は、主成分分析に基づいて行われる。
【００２５】
図１に示すように二分木の根（ルート）ノードに相当する全データ点の集合Ｓ（図１のクラスター１〜４を合わせた全体のクラスター）が与えられたとする。近似最近傍探索の処理を実行するコンピュータは、そのクラスターＳをまず２分割し、２つのノード（図１のクラスター１および３のクラスターとクラスター２および４のクラスター）を作る。次に、前記コンピュータは、２つのノードをそれぞれ２分割する。即ち、クラスター１および３のデータ点集合を２分割し、リーフノードとしてのクラスター１およびクラスター３を作る。また、クラスター２および４のデータ点集合を２分割し、リーフノードとしてのクラスター２およびクラスター４を作る。以上のように全データ点の集合Ｓに対して二分割を繰り返して二分木構造を生成し、各データ点をリーフノードとしてのクラスター１〜４に分類することによって、近似最近傍探索用のデータベースを生成する。
【００２６】
≪データベースへの登録処理と探索処理≫
この発明に係る近似最近傍探索の処理およびその近似最近傍探索の前提となるデータベースの登録処理は、コンピュータが予め用意された処理プログラムを実行することによって実現される。登録処理を実行するコンピュータと近似最近傍探索の処理を実行するコンピュータは同一のものでもよいが、異なるものであってもよい。また、いわゆるクラウドコンピュータのように、登録処理および／または最近傍探索の処理（探索処理）を複数のコンピュータが協働して処理する態様であってもよい。
【００２７】
図２は、この発明に係る登録処理を実行するコンピュータの、ハードウェア構成例を示すブロック図である。図２に示すように、コンピュータ２５は、ＲＯＭ１３、ＣＰＵ１１、ＲＡＭ１５、データベース格納部１７、指示入力部１９および通信インターフェイス部２３を備える。ＲＯＭ１３は、登録処理に係るプログラムを予め格納する。ＣＰＵ１１は、ＲＯＭ１３に格納されたプログラムを実行する。ＲＡＭ１５は、ＣＰＵ１１が処理に用いるワークエリアを提供する。データベース格納部１７は、生成されたデータベースを格納する、指示入力部１９は、ユーザーからの指示を受付ける、表示部２１は、ユーザーに対して情報を表示する。通信インターフェイス部２３は、外部の機器と通信を行う。
【００２８】
コンピュータ２５の具体的態様としては、ファイルサーバやパーソナルコンピュータが挙げられる。また、必要とされるメモリー容量や処理能力を満足すれば、携帯情報端末、高機能携帯電話や機器に組み込まれたマイクロコンピュータも前記態様に含まれる。
データベース格納部１７としては、例えばフラッシュメモリなどの不揮発性記憶素子やハードディスクドライブなどの記憶装置が適用可能である。指示入力部１９の具体的態様としては、キーボード、マウス、タッチパネルなどが挙げられる。表示部２１の具体的態様としては液晶や有機ＥＬを用いた表示装置が挙げられる。通信インターフェイス部２３の具体的態様としては、有線、無線を問わずインターネットやＬＡＮに接続される各種通信インターフェイスやＵＳＢインターフェイスなどが挙げられる。
探索処理を実行するコンピュータも同様のハードウェア構成を備える。以下の説明では、簡単のために登録処理と探索処理が同じコンピュータで実行されるものとする。
【００２９】
≪登録処理：二分木の生成≫
この実施形態で、ＣＰＵ１１が、データベースにデータ点を登録する際に二分木構造を如何に生成するのか、その処理手順について具体的に述べる。
データ点の集合の一例として、各顔画像から抽出された特徴量データが与えられたとする。各特徴量データは、それが抽出された顔画像のデータと関連付けて提供されるものとする。各データ点は30次元のベクトルデータであって、データ点数は100万件であるとする。これは、100万人の顔画像が登録されたデータベースからある人物の顔認識を行うことを意味する。
【００３０】
ＣＰＵ１１は、データ点の全体集合Ｓを対象にＳに属する全データの平均値（平均ベクトル）を求める。さらに、全体集合Ｓを対象に主成分分析を行い、第一主成分ベクトルを求める。全体集合Ｓは、二分木構造の根ノードに対応する。ＣＰＵ１１は、各データ点を表すベクトルデータから前記平均ベクトルを引いた差分のベクトルを求め、その差分ベクトルと前記第一主成分ベクトルとの内積を、各データ点の主成分得点として求める。そして、主成分得点の符号の正負、詳細には主成分得点がゼロ以下か正かに応じて全体集合Ｓに属するデータ点を２分割する。
【００３１】
ここで、前記差分ベクトルと前記第一主成分ベクトルとの内積は、前記差分ベクトルを第一主成分ベクトルに射影したときのベクトル成分といえる。そして、前記差分ベクトルは、各データ点を表すベクトルから平均ベクトルを引いたものであるが、これは各データ点を表すベクトルの座標原点を全データの平均値の座標点にとりなおしたベクトルといえる。よって、各データ点の主成分得点、即ち、前記平均値を原点とした第一主成分ベクトル方向の成分は、全体集合Ｓに属する約半数のデータ点が正の値をとり、約半数のデータ点がゼロ以下の値をとる。
【００３２】
結果的に、根ノードは、主成分得点がゼロ以下の約50万件のデータ点の子クラスター（子ノード）Ｃ201と、主成分得点が正の約50万件のデータ点の子クラスターＣ202とに分けられる。
続いてＣＰＵ１１は、それぞれの子クラスターＣ201およびＣ202を同様の手順でさらに２分割する。この処理を階層の深さｍ回（ｍは末端の葉ノードの階層を除いた二分木の高さを表す自然数）だけ繰り返して、100万件の全データを２m個のクラスター（ノード）、Ｃmi（１≦i≦２m）に分ける。ｍの値は、正しく最近傍点を探し出す割合が最もよくなるように予め定められる。
【００３３】
ＣＰＵ１１は、各クラスターに属するデータ点の平均値、即ち平均ベクトルと主成分ベクトルとをそれぞれデータベース格納部１７に記憶しておく。以上の手順で生成される二分木構造は、根ノードから２分割を繰り返して生成される高さ（ｍ＋１）の完全二分木である。ｍ＋１階層目に得られる２m個のクラスターはそれぞれ葉ノードと呼ばれる。
各データ点には、どの葉ノードのクラスターに含まれるかのクラスター番号が対応付けられてデータベースに格納される。なお、各データ点とそれが抽出された顔画像のデータとの対応関係および各顔画像のデータも前記データベースに格納される。
クラスター（ノード）の分割について、さらに詳しく説明する。ある一つのクラスターに入っているデータ点の集合を
【００３４】
【数１】
とする。ここでｘkは距離空間Ｒdにおけるベクトルデータ（縦ベクトル）を表す。ｘ*kをｘkから全データの平均値を引いたベクトル、即ち、平均値補正されたベクトルとする。
【数２】
Ｎはそのクラスターに入っているデータ点の数を表す。
【００３５】
次に
【数３】
の主成分得点ｆk（ｋ＝１，…，Ｎ）を散布行列Ｘ*TＸ*を用いて求める。ここで、あるクラスのデータ点の集合Ｘ*の主成分得点ｆkは、Ｘ*の特異値のうちで最大のものに対応付けられる。
ｆkの符号がゼロ以下か正かに応じて、各クラスターに所属するデータを二つの子クラスターに分割する。
以上が、クラスター分割の詳細である。
【００３６】
ここで、ＣＰＵ１１は、各データ点をクラスター毎に並べ替える。このことで、プログラミング言語のコンパイラーの最適化機能が有効になり、高速の検出が可能になる。
即ち、元のデータは読み込みの順に並べられていてクラスター毎には並んでいなく、一つのクラスターに属するデータはひと塊りにはなっていない。そのために、クラスター毎にその中のデータを順に読み込んで計算する場合の計算速度が遅くなる。特にプログラミング言語のコンパイラーの最適化オプションによる計算高速化が十分に行われない。好ましくは、クラスター毎にひと塊りとなるようにデータを並べ替える処理を近似最近傍探索用データベースの生成方法で行う。このことで、コンパイラーの最適化機能が有効に働き近傍探索の計算を早くすることができる。
【００３７】
図３は、この発明に係る登録処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図３で、第１行目は、木の根（深さｄ＝１）から葉ノードの一つ手前の階層（ｄ＝ｍ）に至るまで処理を繰り返すことを示している。繰り返す処理は、第２〜１５行目に記載された二分木の生成である。
第２行目は、処理の対象とする階層の各ノードｎについて、第３〜１４行目に記載の処理を繰り返すことを示している。
ＣＰＵ１１は、登録すべきデータ点が与えられたとき、ノードｎのクラスターに属する全てのデータ点の平均として平均ベクトルを計算し（第３行目）、平均値補正されたベクトルｘ*を計算する（第４行目）。
【００３８】
続いてＣＰＵ１１は、最も大きな固有値に対応する主成分ベクトルｐを計算する（第５〜６行目）。ｐは第一主成分ベクトルである。ここで、計算により求められた平均ベクトルと主成分ベクトルｐとを記憶する（第７行目）。
さらにＣＰＵ１１は、ノードｎの各ベクトルデータ（データ点）ｘについて（第８行目）第９〜１３行目の処理を実行する。即ち、各データ点の主成分得点がゼロ以下か否かをしらべ（第９行目）、ゼロ以下であれば左側の子ノードにそのデータ点を格納する（第１０行目）。左側の子ノードは、第１子ノードに相当する。
一方、主成分得点が正であれば（第１１行目）、右側の子ノードにそのデータ点を格納する（第１２行目）。右側の子ノードは、第２子ノードに相当する。
このようにして、ノードｎの各データ点を左右いずれかの子ノードに分割し、この分割を木の根から深さｄ＝ｍまで繰り返すことで、高さ（ｍ＋１）の二分木構造を生成する。
【００３９】
図４は、この発明に係る登録処理により生成された木構造の一例を示す説明図である。図４で、○印はノードを示しており、上位のノードと下位のノードを結ぶ線は親ノードと子ノードの関係を示している。その線の横に記した「ｆ≦０」は主成分得点がゼロ以下のデータ点が属する子ノードを、「ｆ＞０」は主成分得点が正のデータ点が属する子ノードをそれぞれ示している。図４に示す木は、木の高さ（ｍ＋１）＝５である。各ノードを示す○印の中の番号は、各ノードを識別するＩＤ（ノードＩＤ）である。根ノードのノードＩＤは１０１であり、その子ノードのノードＩＤは２０１と２０２である。ノードＩＤの１００の位は階層の深さｄに対応しており、１０および１の位は同じ階層に属する各ノードにユニークな番号である。
【００４０】
図５は、この発明に係るデータベースの具体的な構造の例を示す説明図である。データベース格納部１７に格納されるデータの例を示している。
図５で（ａ）は各データ点に係る構造を示している。（ａ）で横方向に並ぶ一連の数値、即ち各行の数値は一つのデータ点に対応する。図５の例では、100万個のデータ点が登録されているので、縦方向に100万個の数値が並ぶ。（ａ）の左端の欄は、各データ点を識別する点ＩＤである。各データ点に１〜１００００００の数字を付している。
【００４１】
（ａ）の右端の欄は、各データ点を結ぶリンクドリストである。このリンクドリストは、同じ葉ノードに属する他の点の点ＩＤを格納する。ゼロの値は、リストの末尾を示している。（ａ）の左端欄と右端欄に挟まれた部分は、各データ点を表すベクトルデータの値である。この実施形態において、各データ点は３０次元のベクトルデータである。各次元に対応する３０個の実数値が各データ点のベクトルを表す。
（ｂ）は（ａ）の右端欄のリンクドリストの先頭の点ＩＤを示している。１６個のＩＤは、各葉ノードの先頭の点ＩＤを示している。即ち、（ａ）の右端欄のリンクドリストは、葉ノードの単位でリンクドリストを格納している。
ＣＰＵ１１は、このリンクドリストをもとにデータを並び替える。その結果、クラスター毎にひと塊りになったデータベースが作成される。そのデータベースを用いて近似最近傍探索が行われる。
【００４２】
≪探索処理：クエリー点の最近傍にあると判断するデータ点の探索≫
ここでは、クエリー点が与えられたときに、近似最近傍探索を行う方法を説明する。この実施形態において、クエリー点は、クエリーとして与えられた顔画像から抽出されたデータ点、即ちクエリーの特徴量としてのベクトルデータである。
ＣＰＵ１１は、与えられた検索質問画像データ（ベクトルｑ）から平均ベクトルを引いて差分ベクトルを求める。前記平均ベクトルは、登録処理の際にデータベースの全データの集合Ｓに係る平均値のベクトルとして求められたものであり、データベース格納部１７に格納されている。次に、ＣＰＵ１１は、ｑから平均ベクトルを引いた差分のベクトルｑ*と全データ集合Ｓに係る第一主成分ベクトルｐとの内積ｆ≦＜ｑ*，ｐ＞を計算する。ｆは、ｑの主成分得点である。この主成分得点ｆがゼロ以下の場合はｑの最近傍のデータ点はクラスターＣ201に属しており、主成分得点ｆが正の場合はｑの最近傍点はクラスターＣ202に属しているものとする。
【００４３】
ＣＰＵ１１は、その次の階層についても同様の処理を繰り返す。即ち、深さｄの階層において、ｑの最近傍点が属しているとされたクラスターＣdiの平均ベクトルをｑから引いて差分のベクトルｑ*diを求める。例えば、深さｄ＝２の階層において、ｑの最近傍点がクラスターＣ202に属しているとされたとする。ＣＰＵ１１は、クラスターＣ202の平均ベクトルをｑから引いて、差分のベクトルｑ*202求める。この場合、深さｄ＝２、その深さｄ＝２の階層に属する各ノードにユニークな番号ｉ＝０２である。次に、ＣＰＵ１１は、ｑ*diとクラスターＣdiの第一主成分ベクトルｐdiとの内積ｆdi＝＜ｑ*di，ｐdi＞を計算する。ｆdiは、クラスターＣdiについてのｑ*diの主成分得点である。先の例については、ｆ202＝＜ｑ*202，ｐ202＞を計算することになる。この主成分得点ｆdiがゼロ以下の場合、ｑ*diの最近傍のデータ点はクラスターＣ(d+1)(2i-1)に属しており、主成分得点ｆdiが正の場合はｑ*diの最近傍点はクラスターＣ(d+1)(2i)に属しているものとする。ここで、図４に示す二分木の例で、親ノードとしてのクラスターＣdiから生成される深さｄ＋１の２つの子ノードのノードＩＤは、左側の子ノードが（２ｉ−１）であり、右側の子ノードが（２ｉ）である。例えば、クラスターＣ202から生成される左側の子ノードはＣ303であり、右側の子ノードはＣ304である。
【００４４】
以上のようにして、ＣＰＵ１１は、根ノードから順番に深い階層へ向けて子ノードを辿り、ｑの最近傍点が属する葉ノードを判断する。そして、最近傍点が属すると判断した葉ノードに属する各データ点とｑとの距離計算を行って、最も距離の小さいデータ点を最近傍点とする。二分木を葉ノードの階層まで辿ることによって、ｑとの距離計算を行うべきデータ点の数を絞り込む。
【００４５】
ただし、ｑがクラスターの境界近くに存する場合は、最近傍点が属すると判断した子ノードでない方に最近傍点が存することがあり得る。このような判断の誤りを防ぐために、判断の「確からしさ」を示す指標とその指標についての閾値εとを予め定めておき、指標が閾値εより小さい場合はもう一方のクラスターについても探索を行うことが好ましい。前記指標として、ｑの主成分得点ｆdiの絶対値│ｆdi│を用いることができる。│ｆdi│は、クラスターＣdiの第一主成分ベクトルに沿う方向においてクエリー点ｑがクラスター境界からどれほど離れているかを示す。ｑがクラスターの境界に近いほどもう一方のクラスターに最近傍点が存する可能性が高いので、判断の「確からしさ」の指標として用いることができる。
【００４６】
好ましくは、このもう一方のクラスターを探索対象とする処理を実現するために、ＣＰＵ１１は、階層の深さｄにおけるｑの主成分得点ｆdiの絶対値│ｆdi│を計算する。そして、│ｆdi│が前述の閾値εより小さい場合、そのときの深さｄの値、主成分得点を計算したクラスターＣdiのノードＩＤおよび主成分得点ｆdiの符号（ゼロ以下か正かを示す値）をＲＡＭ１５上に確保した探索クラスター・テーブルに登録する。前記クラスターの両方の子ノードを辿れるようにするためである。
【００４７】
ＣＰＵ１１は、根ノードから順番に深い階層へ向けて子ノードを辿り、一つの葉ノードに至る。この一つめの葉ノードを距離計算の対象とする。
好ましくはＣＰＵ１１は、前述の探索クラスター・テーブルに登録されたクラスターがあるか否かを調べる。登録されたクラスターがあれば、そのクラスターのもう一方の子ノードについても葉ノードまで辿る。この二つめの葉ノードを距離計算の対象に加える。なお、探索クラスター・テーブルには、一つめの葉ノードまで辿ったときに登録されたクラスターの主成分得点ｆdiの符号が格納されている。ＣＰＵ１１は、この符号に基づいてもう一方の子ノードを判断する。
【００４８】
なお、既に両方の子ノードを辿ったクラスターについては、そのことが識別できるように、探索クラスター・テーブルに格納された符号を、ゼロ以下を示す値でも正を示す値でもない第三の値に書き換えてもよい。一例では、主成分得点ｆdiがゼロ以下を示す値として−１、正を示す値として１、第三の値としてゼロを用いる。
ＣＰＵ１１は、二つめの葉ノードへ向けて子ノードを辿る過程においても、ｑの主成分得点ｆdiの絶対値│ｆdi│が閾値εより小さい場合は、探索クラスター・テーブルにデータを追加登録する。
【００４９】
ＣＰＵ１１は、探索クラスター・テーブルに登録された全てのクラスターについて両方の子ノードを辿ってそれぞれの末端の葉ノードを特定する。特定された各葉ノードに属する各データ点について、ｑとの距離計算をそれぞれ実行する。それらデータ点のうち、ｑに対して最小の距離となるデータ点を最近傍点とする。
最近傍探索としては、最近傍点が最終的な出力である。ただし、この最近傍探索を用いた顔認識処理としては、100万件の顔画像のデータのうち、クエリーの顔画像に最も近いものを最終的な出力とする必要がある。その処理は次のようにして実現できる。各データ点には、それが100万件の顔画像データのうちどのデータから抽出されたものかが対応付けられてデータベースに登録されている。そこで、最近傍点が抽出された顔画像データをその顔画像データを顔認識の結果として出力する。以上の手順は一般にバックトラッキングと呼ばれるもので、それを本近似最近傍探索法に適用したものがこれまでの説明である。
【００５０】
以上のように、各ノードにおいて、クエリー点ｑに係る主成分得点ｆdiの符号によりクエリー点の所属する子ノードを決定し、二分木のノードを辿って探索を行う。一つの葉ノードまで辿る限りにおいては、二分木生成工程はｍ回の繰り返し計算を行えば足りる。しかし、一つの葉ノードに存在するデータ点のみを距離計算の対象とするだけでは、十分な探索精度が得られないことがある。ｑがクラスターの境界近くにあって探索していないクラスターの中に最近傍の点が存する場合があるためである。そこで探索するクラスターの範囲を合理的に拡張するため、指標としての│ｆdi│および閾値εを導入する。もしクエリー点とクラスターの境界との距離がεよりも小さければ、境界の反対側にあるクラスターも探索する。
【００５１】
図６は、この発明に係る探索クラスター・テーブルの具体例を示す説明図である。図６の探索クラスター・テーブルには、ＩＤが２０２、３０４および３０３のノードが登録されている。ノードＩＤは、図４の木に対応している。ノード２０２を最初に辿ったときの主成分得点ｆ202の符号は正（＋１）である。図４の木では、右側の子ノード３０４へ進んだことを示している。そのノード３０４も探索クラスター・テーブルに登録されている。ノード３０４を最初に辿ったときのｆ304の符号はゼロ以下（−１）である。よって、左側の子ノード４０７へ進んだことを示している。深さｄ＝４のノードは登録されてない。│ｆ407│が閾値ε以上であったことが分かる。よって、片方のノードだけを辿ったことになる。ここでは、ノード４０７の右側の子ノード５１４が第１の葉ノードであったとする。
【００５２】
第１の葉ノードまで辿った後、ＣＰＵ１１が図６の探索クラスター・テーブルを参照すると、ノード２０２が登録されている。最初に辿ったときの符号は正である。そこで、ＣＰＵ１１は、ノード２０２のもう一方の子ノード、即ち、ｆ202の符号がゼロ以下の各データ点が属するノード３０３を探索する。図６には、そのノード３０３が登録されている。よって、最初にノード３０３を探索したときの│ｆ303│が閾値ε以上であったことが分かる。他のノードは図６では登録されていないので、片方のノードだけを辿ったことがわかる。ここでは、ノード４０６を経た葉ノード５１２が第２の葉ノードであったとする。
【００５３】
第２の葉ノードまで辿った後、ＣＰＵ１１がさらに図６の探索クラスター・テーブルを参照すると、ノード３０４が登録されている。最初に辿ったときの符号はゼロ以下であるので、次は正の符号に対応する子ノード４０８を経て葉ノードへ進む。ここでは、ノード５１５が第３の葉ノードであったとする。
【００５４】
さらに、探索クラスター・テーブルにはノード３０３が登録されている。最初に辿ったときの符号は正であるので、次はゼロ以下の符号に対応する子ノード４０５を経て葉ノードへ進む。ここでは、ノード５１０が第４の葉ノードであったとする。
以上のように、ＣＰＵ１１は、探索クラスター・テーブルに登録された各ノードのもう一方の子ノードを辿る。その結果として見出された葉ノード、図６の例では、第１〜４の葉ノード５１４、５１２、５１５および５１０に属する各データ点について、ｑとの距離計算を実行し最近傍点を決定する。
【００５５】
なお、これまでの説明では、ＣＰＵ１１が第１の葉ノードまで辿った後に探索クラスター・テーブルを参照して第２の葉ノードまで辿るものとした。その後さらに探索クラスター・テーブルを参照して第３の葉ノードまで辿るものとした。また、ＣＰＵ１１は、第３の葉ノードまで辿った後に探索クラスター・テーブルを参照して第４の葉ノードまで辿るものとした。前述したバックトラッキングである。しかし、探索の手順はこれに限らない。異なる態様として、階層ごとに探索すべきノードをすべて探索し、その結果として次の階層で探索の対象とすべきノードを探索クラスター・テーブルに登録した後に次の階層へ進むようにしてもよい。次の階層では、探索クラスター・テーブルに登録されたノードを全て探索し、その結果としてさらに次の階層で探索対象とすべきノードを探索クラスター・テーブルに登録する。二分木の末端の葉ノードに達するまでこれを繰り返す。いずれの手順でも同様の結果が得られる。両者はいずれもこの発明に含まれる。前者の態様、即ちバックトラッキングの方が後者の態様に比べてノードの探索に要するメモリーを節約することができる。ただし、所要メモリー量に有意差が生じるのは大量の葉ノードを探索する場合である。
【００５６】
図７は、この発明に係る探索処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図７で、第１および２行目は、前述の登録処理によって予め生成された二分木構造（ノードリスト）を対象に探索することを示している。なお、探索の対象とするノードのＩＤを格納するのは変数listである。ＣＰＵ１１は、変数listの初期値として、根ルートのＩＤを設定する。
第３行目は、前記ノードリストの根（深さｄ＝１）から葉ノードの前階層（ｄ＝ｍ）まで処理を繰り返すことを示している。繰り返す処理は、第４〜１９行目に記載されている。
第４行目は、深さｄのノードのうち、探索の対象とする各ノードｎについて、第５〜１３行目に記載の処理を繰り返すことを示している。探索の対象とするノードは、この行の処理に至るまでに、変数listに格納されている。初期値として、第１行目の処理で根ノードのＩＤが格納されている。その後は、第８、１２および１４行目の処理で、次の階層で探索すべき対象が一時変数tempに格納される。第１８行目の処理で、変数listに次の階層における探索対象が累積的に格納される。
【００５７】
ＣＰＵ１１は、クエリーｑが与えられたとき、その主成分得点を計算し、主成分得点の絶対値が予め定められた正の値ε以下か否かを判断する（第５行目）。なお、ｑの主成分得点を得るために、ｑと主成分ベクトルｐとの内積を計算する。各ノードの主成分ベクトルｐと平均ベクトルは、登録処理の際にデータベースに格納されている（第６〜７行目）。
ｑの主成分得点の絶対値がε以下の場合、ＣＰＵ１１は、対象としているノードｎの両方の子ノードを探索の対象とすべく一時変数tempに両方の子ノードのノードＩＤを格納する。ここで、一時変数tempは、次の階層において探索の対象とすべきノードのＩＤを格納する（第８〜９行目）。両方の子ノードを探索するために、探索クラスター・テーブルを用いる手法は既に説明した。
【００５８】
一方、ｑの主成分得点の絶対値がεより大きい場合（第１０行目）、ＣＰＵ１１は、ｑの主成分得点に応じて以下のように処理を行う。ｑの主成分得点がゼロ以下の場合（第１１行目）、ＣＰＵ１１は、一時変数tempに左側の子ノードのＩＤを格納し、探索の対象とする（第１２行目）。図３の登録処理において、左側の子ノードは主成分得点がゼロ以下のデータ点を格納している。
【００５９】
一方、ｑの主成分得点が正の場合（第１３行目）、右側の子ノードのＩＤを一時変数tempに格納し探索の対象とする（第１４行目）。図３の登録処理において、右側の子ノードは主成分得点がゼロより大きいデータ点を格納している。
そして、ＣＰＵ１１は、一時変数tempの内容を変数listに代入する（第１８行目）。よって、変数listは、探索すべきノードのＩＤを格納する。
【００６０】
最後の深さｍに至るまで処理を繰り返し、変数listに格納されたノードＩＤに含まれるデータ点、即ち葉ノードのうち探索すべきノードに含まれる各データ点について、ｑとの距離をそれぞれ計算し、最も近い距離にあるデータ点を最近傍点とする（第２０〜２３行目）。
【００６１】
≪実験例≫
この発明の有効性を示すため、近似最近傍探索法と従来の線形探索との比較実験を行った。線形探索については、打ち切りなしの場合および打ち切りありの場合の両方を比較対象とした。線形探索の打ち切りなしとは、全てのデータ点ｐとクエリー点ｑとの距離を計算し最も距離の短いデータ点を見つける方法である。これは、最も単純であるが計算時間のかかる方法である。線形探索の打ち切りありとは、１件のデータ点ｐとクエリー点ｑの距離の計算途中にそれまでに見つかっている最も近いデータ点との距離よりも長くなれば、そこで計算を打ち切って次のデータ点ｐとクエリー点ｑとの距離計算に移る方法である。データ点ｐとクエリー点ｑの距離は２乗距離（ユークリッド距離の２乗）で定義され、それは各次元毎の差の２乗の和である。
【００６２】
この発明による近似最近傍探索法については、クラスター数、すなわち木の高さｍとノード間の境界までの距離閾値εを種々変化させて最適な値を決定した。データ点は、以下のＭＡＴＬＡＢコードのように、３０次元データを正規乱数で作成した。各次元（変数）の標準偏差を１００から４００までの一様乱数で与えた。データ点総数は１００万件である。
【００６３】
【数４】
【００６４】
クエリー点は同様にして作成した１０００件のデータ点である。計算機はDell Precisi on T3500 Intel（R）Xeon（R）W3250 （2.67GHz)CPU, 3.25 MB．OS はWindows XP である。
線形探索の打ち切りなしで、平均検出時間は284.0 ms、打ち切りありでは112.8 ms であった。
【００６５】
図８は、この発明による近似最近傍探索と従来の線形探索との比較実験の結果を示すグラフである。図８で、横軸は線形探索の打ち切りなし（平均検出時間は284.0 ms）を100％として計算時間をパーセントで示している。縦軸は正しく最近傍データを見つけた割合を％で示している。図８に示すように階層の深さｍはｍ＝１５が最適である。したがって葉ノードの数は２15＝３２７６８が最適である。表１は、実際の時間で示している。これらのテスト結果は、コンパイラーの最適化オプションを用ない場合のものであるが、ｃ言語のVisual c の最適化オプションを用いれば、ｍ＝１３が最適であり、たとえば平均検出時間1.45msで精度80％であった。線形探索の打ち切り有りを100％としたときの4％の時間で80％の精度が得られている。
【表１】
【００６６】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００６７】
１、２、３、４：クラスター
１１：ＣＰＵ
１３：ＲＯＭ
１５：ＲＡＭ
１７：データベース格納部
１９：指示入力部
２１：表示部
２３：通信インターフェイス部
２５：コンピュータ
【技術分野】
【０００１】
この発明は、主成分分析に基づく二分木を用いた近似最近傍探索方法、最近傍探索プログラムおよびその方法を用いた装置に関する。
【背景技術】
【０００２】
最近傍探索とはデータ集合の中からクエリー（検索質問点）と最も近い距離にあるデータ（最近傍点）を探す問題である。すなわち、d個の数値的特徴を表すためのd次元の距離空間Rd においてn 個のデータの集合S と、それらデータと同じ次元数のクエリー q ∈ Rdが与えられたとき、データの集合S の中からクエリーq と最も近いデータpnn を探索することである。ここで、各データp は距離空間Rd 中の一つの点であり、d次元のベクトルデータで表される。以下で各データをデータ点とも呼ぶ。クエリーも各データと同様に、距離空間Rd 中の一つの点としてd次元のベクトルデータで表される。以下でクエリーをクエリー点とも呼ぶ。
【０００３】
最近傍探索の最も基本的な解法は、データ集合S 内の全データ点 とクエリー点q との距離計算を行い、距離の最も近いものを探索する方法である。これを線形探索という。すべてのデータ点とクエリー点q との距離計算を行う方法は、一般に距離計算の対象となるデータ点の数が多いため、処理の高速化を図った手法がいくつか提案されている。しかし、データ点の数および次元数が大きなデータベースを扱う場合、線形探索に比べて処理時間が大幅に短縮される最近傍探索の手法はほとんどない。
そこで、探索の精度をある程度犠牲にするかわりに処理時間を大幅に短縮する近似最近傍探索の手法が提案されている。近似最近傍探索では探索のエラー率を実用上問題ない程度に抑えながら、線形探索に比べて非常に短い処理時間で最近傍点を探索することができる。
【０００４】
近似最近傍探索の応用例として、物体認識や顔認識が挙げられる。物体認識や顔認識では、予め様々な物体や顔の画像から特徴量をベクトルデータ（データ点）として抽出しデータベースに保存しておく。検索質問として画像が与えられたとき、その画像から同様に特徴量を取り出して、近似最近傍探索のクエリーとする。そして、クエリーに近い特徴量を持つデータ点を出力結果とすることで、そのデータ点が抽出された物体や顔画像を特定する。これによって、物体認識や顔認識が可能となる。
近似最近傍探索の応用分野として、前述の物体認識や顔認識の他に知識発見、データマイニング、機械学習、データ圧縮、マルチメディア・データベース、文書検索および統計処理などが知られている。
【０００５】
近似最近傍探索の代表的な手法として、LSH（Locality Sensitive Hashing）が挙げられる（例えば、非特許文献１参照）。LSHの手法では、データベースに登録すべきデータ点を表すベクトルデータを入力するとスカラ値を出力するハッシュ関数を各データ点に適用し、前記ハッシュ関数から出力される値（ハッシュ値）に基づいてデータ点を分類する。そして、分類されたデータ点のテーブル（ハッシュテーブル）を作成し前記データベースに含めて登録しておく。このハッシュ関数は、ベクトル間距離の近いものが似たハッシュ値をとり、遠いものは似たハッシュ値をとらないように定義される。その結果、近い距離にあるデータ点が同じ類に属するように分類されてハッシュテーブルに登録される。
【０００６】
クエリー点が与えられたとき、そのクエリー点に前記ハッシュ関数を適用してクエリー点のハッシュ値を得る。前記データベースに登録されたデータ点のうち、クエリー点のハッシュ値と等しいハッシュ値の類に属するデータ点のみとの間で距離計算を行う。距離計算の対象となるデータ点は、クエリー点のハッシュ値を用いてハッシュテーブルを参照することで得られる。LSHは、距離計算の対象を特定の類に属するデータ点に限定することによって処理時間を短縮している。
【０００７】
一方、LSHとは異なるアプローチとして、二分木を用いた近似最近傍探索の手法が提案されている（例えば、非特許文献２参照）。
また、データ集合を探索することなく識別を行う手法が提案されており、その中で主成分得点を用いてクラスターを２分割することが記載されている（例えば、非特許文献３〜５参照）。ただし、非特許文献３および４は、データ点の全体集合を二分割することのみが記載されている。非特許文献５は、非特許文献３および４の木の高さを任意の自然数まで拡張したものである。
非特許文献５で、データ点のクラスタリング（分割）に主成分分析（Principal component analysis, PCA）を用いているが、これは、識別精度が分割位置のランダムな選択によって変動するのを防止するためである。より詳細には、主成分得点（Principal Component Score）の正負の符号によるクラスターの２分割を繰り返し行って二分木を生成するが、葉ノード（リーフ）が初期分割である。また、非特許文献５では、クラスタリングのための繰り返しアルゴリズムによって最終的なクラスターが決定され、その中心ベクトルと共分散行列のみが識別器に用いられる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M.Datar, N.Immorlica, P.Indyk and V.S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proc. of the 20th annual symposium on Computational Geometry, pp.253-262, 2004.
【非特許文献２】S.Arya, D.M. Mount, R.Silverman and A.Y. Wu, "An optimal algorithm for approximate nearest neighbor searching," Journal of the ACM, vol.45, no.6, pp.891-923, 1998.
【非特許文献３】H. Ichihashi, A. Notsu and K. Honda, "Semi-hard c-means clustering with application to classifier design," Proc. of the IEEE International Conference on Fuzzy System, World Congress on Computational Intelligence, Barcelona, Spain, pp. 2788-2795, 2010.
【非特許文献４】H. Ichihashi, A. Notsu, K. Honda, T. Katada and M. Fujiyoshi, "Improvement in the performance of camera based vehicle detector for parking lot," Proc. of 2010 IEEE International Conference on Fuzzy System, Barcelona, Spain, Juli. 18-23, 2010.
【非特許文献５】H. Ichihashi, K. Honda and A. Notsu, "Comparison of Scaling Behavior Between Fuzzy c-Means Based Classifier with Many Parameters and LibSVM," Proc. of the IEEE International Conference on Fuzzy Systems, pp. 386-393, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
LSHなど、ハッシュ関数を用いた手法は、距離計算に要する処理時間が短縮されるという利点があるが、ハッシュテーブルを格納するメモリー領域を必要とする。また、各データ点にハッシュ関数を適用して得られるハッシュ値は、一種の乱数と捉えることができ、探索の精度はランダムに変化する。安定した精度を得るためには十分な数のデータ点を探索することが前提となるが、データ点が増加すると探索に要する処理時間も増大するため両者はトレードオフの関係にあるとの見方もできる。
一方、二分木構造を用いた手法は、ハッシュ関数を用いた手法に比べると木構造を保持するために必要なメモリー容量が一般に少なくてすむ。また、ハッシュ関数を用いて乱数を発生させることがないため個々の探索の精度が安定している。しかし、ハッシュ関数を用いた手法に比べると、木構造を辿って探索を行うために要する処理時間が一般的に長くかかると考えられている。しかし、二分木によって距離計算対象とすべきデータ点を効率的に絞り込むことができれば、処理時間を短縮できる。
この発明は、以上のような事情を考慮してなされたものであって、主成分分析（Principal Component Analysis、PCA）に基づく二分木を用いて最近傍のデータ点を効率的に探索して推定し、処理時間の短縮を実現する近似最近傍探索方法、装置およびプログラムを提供する。
【課題を解決するための手段】
【００１０】
この発明は、コンピュータが、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法を提供する。
【００１１】
また異なる観点から、この発明は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置を提供する。
【００１２】
さらに異なる観点から、この発明は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラムを提供する。
【発明の効果】
【００１３】
近似最近傍探索方法は、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースを探索するにあたり、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの第一主成分ベクトルとの内積を計算してクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを探索クラスターとし、前記クエリー主成分得点が正ならば第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程とを備えるので、クエリーとの距離計算を行うベクトルデータを絞り込むことができる。クエリー主成分得点はベクトルの内積という単純な計算で得ることができる。よって、最近傍とされるデータ点を効率的に探索できる。
この発明による近似最近傍探索装置および近似最近傍探索プログラムも同様の効果を奏する。
【００１４】
この発明において、クラスターは、同じ類に属するベクトルデータの集合を示すもので、二分木構造のノードに対応する。その具体的な態様の例は、各要素の値がメモリーに格納されたベクトルデータのリストである。
この発明によれば、データベースは平衡な完全二分木の構造を有する。末端の葉ノードのクラスターを除いた各クラスターは、２つの子クラスターをそれぞれ有する。即ち、二分木の根と葉を除いた階層（高さ）にある各クラスターは、根ノード側にあるクラスターの子ノードであると同時に、葉ノード側にあるクラスターの親ノードである。
主成分分析は、複数の変数間の相関を把握するために導入される公知の手法であって、クラスターが与えられたとき第一主成分ベクトルおよび主成分得点（主成分スコアとも呼ばれる）を算出する手法は公知である。例えば、第一主成分ベクトルは、共分散行列の固有値問題を解いて得ることができる。
【図面の簡単な説明】
【００１５】
【図１】この発明に係る二分木を用いたデータ点分割の様子を示す説明図である。
【図２】この発明に係る登録処理を実行するコンピュータの、ハードウェア構成例を示すブロック図である。
【図３】この発明に係る登録処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。
【図４】この発明に係る登録処理によって生成された木構造の一例を示す説明図である。
【図５】この発明に係るデータベースの具体的な構造の例を示す説明図である。
【図６】この発明に係る探索クラスター・テーブルの具体例を示す説明図である。
【図７】この発明に係る探索処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。
【図８】この発明による近似最近傍探索と従来の線形探索との比較実験の結果を示すグラフである。
【発明を実施するための形態】
【００１６】
以下、この発明の好ましい態様について説明する。
この発明によるデータベースの生成方法において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。
【００１７】
さらに、前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。
【００１８】
また、前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする工程、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割工程、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものであってもよい。
【００１９】
前記平均補正工程は、各クラスターについて得られた平均ベクトルを前記データベースの一部として格納し、前記得点算出工程は、各クラスターについて得られた第一主成分ベクトルを前記データベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。
【００２０】
さらに、この発明は、前述したこの発明によるデータベースの生成装置において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。
【００２１】
さらに、前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。
【００２２】
また、この発明によるデータベースの生成装置において、前記平均補正部は、各クラスターについて得られた平均ベクトルをデータベースの一部として格納し、前記得点算出部は、各クラスターについて得られた第一主成分ベクトルをデータベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。
【００２３】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割部、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものであってもよい。
この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。
【００２４】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
≪主成分分析に基づく２分木を用いる近似最近傍探索≫
図１は、この発明に係る二分木を用いたクラスター分割の様子を示す説明図である。クラスター分割は、主成分分析に基づいて行われる。
【００２５】
図１に示すように二分木の根（ルート）ノードに相当する全データ点の集合Ｓ（図１のクラスター１〜４を合わせた全体のクラスター）が与えられたとする。近似最近傍探索の処理を実行するコンピュータは、そのクラスターＳをまず２分割し、２つのノード（図１のクラスター１および３のクラスターとクラスター２および４のクラスター）を作る。次に、前記コンピュータは、２つのノードをそれぞれ２分割する。即ち、クラスター１および３のデータ点集合を２分割し、リーフノードとしてのクラスター１およびクラスター３を作る。また、クラスター２および４のデータ点集合を２分割し、リーフノードとしてのクラスター２およびクラスター４を作る。以上のように全データ点の集合Ｓに対して二分割を繰り返して二分木構造を生成し、各データ点をリーフノードとしてのクラスター１〜４に分類することによって、近似最近傍探索用のデータベースを生成する。
【００２６】
≪データベースへの登録処理と探索処理≫
この発明に係る近似最近傍探索の処理およびその近似最近傍探索の前提となるデータベースの登録処理は、コンピュータが予め用意された処理プログラムを実行することによって実現される。登録処理を実行するコンピュータと近似最近傍探索の処理を実行するコンピュータは同一のものでもよいが、異なるものであってもよい。また、いわゆるクラウドコンピュータのように、登録処理および／または最近傍探索の処理（探索処理）を複数のコンピュータが協働して処理する態様であってもよい。
【００２７】
図２は、この発明に係る登録処理を実行するコンピュータの、ハードウェア構成例を示すブロック図である。図２に示すように、コンピュータ２５は、ＲＯＭ１３、ＣＰＵ１１、ＲＡＭ１５、データベース格納部１７、指示入力部１９および通信インターフェイス部２３を備える。ＲＯＭ１３は、登録処理に係るプログラムを予め格納する。ＣＰＵ１１は、ＲＯＭ１３に格納されたプログラムを実行する。ＲＡＭ１５は、ＣＰＵ１１が処理に用いるワークエリアを提供する。データベース格納部１７は、生成されたデータベースを格納する、指示入力部１９は、ユーザーからの指示を受付ける、表示部２１は、ユーザーに対して情報を表示する。通信インターフェイス部２３は、外部の機器と通信を行う。
【００２８】
コンピュータ２５の具体的態様としては、ファイルサーバやパーソナルコンピュータが挙げられる。また、必要とされるメモリー容量や処理能力を満足すれば、携帯情報端末、高機能携帯電話や機器に組み込まれたマイクロコンピュータも前記態様に含まれる。
データベース格納部１７としては、例えばフラッシュメモリなどの不揮発性記憶素子やハードディスクドライブなどの記憶装置が適用可能である。指示入力部１９の具体的態様としては、キーボード、マウス、タッチパネルなどが挙げられる。表示部２１の具体的態様としては液晶や有機ＥＬを用いた表示装置が挙げられる。通信インターフェイス部２３の具体的態様としては、有線、無線を問わずインターネットやＬＡＮに接続される各種通信インターフェイスやＵＳＢインターフェイスなどが挙げられる。
探索処理を実行するコンピュータも同様のハードウェア構成を備える。以下の説明では、簡単のために登録処理と探索処理が同じコンピュータで実行されるものとする。
【００２９】
≪登録処理：二分木の生成≫
この実施形態で、ＣＰＵ１１が、データベースにデータ点を登録する際に二分木構造を如何に生成するのか、その処理手順について具体的に述べる。
データ点の集合の一例として、各顔画像から抽出された特徴量データが与えられたとする。各特徴量データは、それが抽出された顔画像のデータと関連付けて提供されるものとする。各データ点は30次元のベクトルデータであって、データ点数は100万件であるとする。これは、100万人の顔画像が登録されたデータベースからある人物の顔認識を行うことを意味する。
【００３０】
ＣＰＵ１１は、データ点の全体集合Ｓを対象にＳに属する全データの平均値（平均ベクトル）を求める。さらに、全体集合Ｓを対象に主成分分析を行い、第一主成分ベクトルを求める。全体集合Ｓは、二分木構造の根ノードに対応する。ＣＰＵ１１は、各データ点を表すベクトルデータから前記平均ベクトルを引いた差分のベクトルを求め、その差分ベクトルと前記第一主成分ベクトルとの内積を、各データ点の主成分得点として求める。そして、主成分得点の符号の正負、詳細には主成分得点がゼロ以下か正かに応じて全体集合Ｓに属するデータ点を２分割する。
【００３１】
ここで、前記差分ベクトルと前記第一主成分ベクトルとの内積は、前記差分ベクトルを第一主成分ベクトルに射影したときのベクトル成分といえる。そして、前記差分ベクトルは、各データ点を表すベクトルから平均ベクトルを引いたものであるが、これは各データ点を表すベクトルの座標原点を全データの平均値の座標点にとりなおしたベクトルといえる。よって、各データ点の主成分得点、即ち、前記平均値を原点とした第一主成分ベクトル方向の成分は、全体集合Ｓに属する約半数のデータ点が正の値をとり、約半数のデータ点がゼロ以下の値をとる。
【００３２】
結果的に、根ノードは、主成分得点がゼロ以下の約50万件のデータ点の子クラスター（子ノード）Ｃ201と、主成分得点が正の約50万件のデータ点の子クラスターＣ202とに分けられる。
続いてＣＰＵ１１は、それぞれの子クラスターＣ201およびＣ202を同様の手順でさらに２分割する。この処理を階層の深さｍ回（ｍは末端の葉ノードの階層を除いた二分木の高さを表す自然数）だけ繰り返して、100万件の全データを２m個のクラスター（ノード）、Ｃmi（１≦i≦２m）に分ける。ｍの値は、正しく最近傍点を探し出す割合が最もよくなるように予め定められる。
【００３３】
ＣＰＵ１１は、各クラスターに属するデータ点の平均値、即ち平均ベクトルと主成分ベクトルとをそれぞれデータベース格納部１７に記憶しておく。以上の手順で生成される二分木構造は、根ノードから２分割を繰り返して生成される高さ（ｍ＋１）の完全二分木である。ｍ＋１階層目に得られる２m個のクラスターはそれぞれ葉ノードと呼ばれる。
各データ点には、どの葉ノードのクラスターに含まれるかのクラスター番号が対応付けられてデータベースに格納される。なお、各データ点とそれが抽出された顔画像のデータとの対応関係および各顔画像のデータも前記データベースに格納される。
クラスター（ノード）の分割について、さらに詳しく説明する。ある一つのクラスターに入っているデータ点の集合を
【００３４】
【数１】
とする。ここでｘkは距離空間Ｒdにおけるベクトルデータ（縦ベクトル）を表す。ｘ*kをｘkから全データの平均値を引いたベクトル、即ち、平均値補正されたベクトルとする。
【数２】
Ｎはそのクラスターに入っているデータ点の数を表す。
【００３５】
次に
【数３】
の主成分得点ｆk（ｋ＝１，…，Ｎ）を散布行列Ｘ*TＸ*を用いて求める。ここで、あるクラスのデータ点の集合Ｘ*の主成分得点ｆkは、Ｘ*の特異値のうちで最大のものに対応付けられる。
ｆkの符号がゼロ以下か正かに応じて、各クラスターに所属するデータを二つの子クラスターに分割する。
以上が、クラスター分割の詳細である。
【００３６】
ここで、ＣＰＵ１１は、各データ点をクラスター毎に並べ替える。このことで、プログラミング言語のコンパイラーの最適化機能が有効になり、高速の検出が可能になる。
即ち、元のデータは読み込みの順に並べられていてクラスター毎には並んでいなく、一つのクラスターに属するデータはひと塊りにはなっていない。そのために、クラスター毎にその中のデータを順に読み込んで計算する場合の計算速度が遅くなる。特にプログラミング言語のコンパイラーの最適化オプションによる計算高速化が十分に行われない。好ましくは、クラスター毎にひと塊りとなるようにデータを並べ替える処理を近似最近傍探索用データベースの生成方法で行う。このことで、コンパイラーの最適化機能が有効に働き近傍探索の計算を早くすることができる。
【００３７】
図３は、この発明に係る登録処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図３で、第１行目は、木の根（深さｄ＝１）から葉ノードの一つ手前の階層（ｄ＝ｍ）に至るまで処理を繰り返すことを示している。繰り返す処理は、第２〜１５行目に記載された二分木の生成である。
第２行目は、処理の対象とする階層の各ノードｎについて、第３〜１４行目に記載の処理を繰り返すことを示している。
ＣＰＵ１１は、登録すべきデータ点が与えられたとき、ノードｎのクラスターに属する全てのデータ点の平均として平均ベクトルを計算し（第３行目）、平均値補正されたベクトルｘ*を計算する（第４行目）。
【００３８】
続いてＣＰＵ１１は、最も大きな固有値に対応する主成分ベクトルｐを計算する（第５〜６行目）。ｐは第一主成分ベクトルである。ここで、計算により求められた平均ベクトルと主成分ベクトルｐとを記憶する（第７行目）。
さらにＣＰＵ１１は、ノードｎの各ベクトルデータ（データ点）ｘについて（第８行目）第９〜１３行目の処理を実行する。即ち、各データ点の主成分得点がゼロ以下か否かをしらべ（第９行目）、ゼロ以下であれば左側の子ノードにそのデータ点を格納する（第１０行目）。左側の子ノードは、第１子ノードに相当する。
一方、主成分得点が正であれば（第１１行目）、右側の子ノードにそのデータ点を格納する（第１２行目）。右側の子ノードは、第２子ノードに相当する。
このようにして、ノードｎの各データ点を左右いずれかの子ノードに分割し、この分割を木の根から深さｄ＝ｍまで繰り返すことで、高さ（ｍ＋１）の二分木構造を生成する。
【００３９】
図４は、この発明に係る登録処理により生成された木構造の一例を示す説明図である。図４で、○印はノードを示しており、上位のノードと下位のノードを結ぶ線は親ノードと子ノードの関係を示している。その線の横に記した「ｆ≦０」は主成分得点がゼロ以下のデータ点が属する子ノードを、「ｆ＞０」は主成分得点が正のデータ点が属する子ノードをそれぞれ示している。図４に示す木は、木の高さ（ｍ＋１）＝５である。各ノードを示す○印の中の番号は、各ノードを識別するＩＤ（ノードＩＤ）である。根ノードのノードＩＤは１０１であり、その子ノードのノードＩＤは２０１と２０２である。ノードＩＤの１００の位は階層の深さｄに対応しており、１０および１の位は同じ階層に属する各ノードにユニークな番号である。
【００４０】
図５は、この発明に係るデータベースの具体的な構造の例を示す説明図である。データベース格納部１７に格納されるデータの例を示している。
図５で（ａ）は各データ点に係る構造を示している。（ａ）で横方向に並ぶ一連の数値、即ち各行の数値は一つのデータ点に対応する。図５の例では、100万個のデータ点が登録されているので、縦方向に100万個の数値が並ぶ。（ａ）の左端の欄は、各データ点を識別する点ＩＤである。各データ点に１〜１００００００の数字を付している。
【００４１】
（ａ）の右端の欄は、各データ点を結ぶリンクドリストである。このリンクドリストは、同じ葉ノードに属する他の点の点ＩＤを格納する。ゼロの値は、リストの末尾を示している。（ａ）の左端欄と右端欄に挟まれた部分は、各データ点を表すベクトルデータの値である。この実施形態において、各データ点は３０次元のベクトルデータである。各次元に対応する３０個の実数値が各データ点のベクトルを表す。
（ｂ）は（ａ）の右端欄のリンクドリストの先頭の点ＩＤを示している。１６個のＩＤは、各葉ノードの先頭の点ＩＤを示している。即ち、（ａ）の右端欄のリンクドリストは、葉ノードの単位でリンクドリストを格納している。
ＣＰＵ１１は、このリンクドリストをもとにデータを並び替える。その結果、クラスター毎にひと塊りになったデータベースが作成される。そのデータベースを用いて近似最近傍探索が行われる。
【００４２】
≪探索処理：クエリー点の最近傍にあると判断するデータ点の探索≫
ここでは、クエリー点が与えられたときに、近似最近傍探索を行う方法を説明する。この実施形態において、クエリー点は、クエリーとして与えられた顔画像から抽出されたデータ点、即ちクエリーの特徴量としてのベクトルデータである。
ＣＰＵ１１は、与えられた検索質問画像データ（ベクトルｑ）から平均ベクトルを引いて差分ベクトルを求める。前記平均ベクトルは、登録処理の際にデータベースの全データの集合Ｓに係る平均値のベクトルとして求められたものであり、データベース格納部１７に格納されている。次に、ＣＰＵ１１は、ｑから平均ベクトルを引いた差分のベクトルｑ*と全データ集合Ｓに係る第一主成分ベクトルｐとの内積ｆ≦＜ｑ*，ｐ＞を計算する。ｆは、ｑの主成分得点である。この主成分得点ｆがゼロ以下の場合はｑの最近傍のデータ点はクラスターＣ201に属しており、主成分得点ｆが正の場合はｑの最近傍点はクラスターＣ202に属しているものとする。
【００４３】
ＣＰＵ１１は、その次の階層についても同様の処理を繰り返す。即ち、深さｄの階層において、ｑの最近傍点が属しているとされたクラスターＣdiの平均ベクトルをｑから引いて差分のベクトルｑ*diを求める。例えば、深さｄ＝２の階層において、ｑの最近傍点がクラスターＣ202に属しているとされたとする。ＣＰＵ１１は、クラスターＣ202の平均ベクトルをｑから引いて、差分のベクトルｑ*202求める。この場合、深さｄ＝２、その深さｄ＝２の階層に属する各ノードにユニークな番号ｉ＝０２である。次に、ＣＰＵ１１は、ｑ*diとクラスターＣdiの第一主成分ベクトルｐdiとの内積ｆdi＝＜ｑ*di，ｐdi＞を計算する。ｆdiは、クラスターＣdiについてのｑ*diの主成分得点である。先の例については、ｆ202＝＜ｑ*202，ｐ202＞を計算することになる。この主成分得点ｆdiがゼロ以下の場合、ｑ*diの最近傍のデータ点はクラスターＣ(d+1)(2i-1)に属しており、主成分得点ｆdiが正の場合はｑ*diの最近傍点はクラスターＣ(d+1)(2i)に属しているものとする。ここで、図４に示す二分木の例で、親ノードとしてのクラスターＣdiから生成される深さｄ＋１の２つの子ノードのノードＩＤは、左側の子ノードが（２ｉ−１）であり、右側の子ノードが（２ｉ）である。例えば、クラスターＣ202から生成される左側の子ノードはＣ303であり、右側の子ノードはＣ304である。
【００４４】
以上のようにして、ＣＰＵ１１は、根ノードから順番に深い階層へ向けて子ノードを辿り、ｑの最近傍点が属する葉ノードを判断する。そして、最近傍点が属すると判断した葉ノードに属する各データ点とｑとの距離計算を行って、最も距離の小さいデータ点を最近傍点とする。二分木を葉ノードの階層まで辿ることによって、ｑとの距離計算を行うべきデータ点の数を絞り込む。
【００４５】
ただし、ｑがクラスターの境界近くに存する場合は、最近傍点が属すると判断した子ノードでない方に最近傍点が存することがあり得る。このような判断の誤りを防ぐために、判断の「確からしさ」を示す指標とその指標についての閾値εとを予め定めておき、指標が閾値εより小さい場合はもう一方のクラスターについても探索を行うことが好ましい。前記指標として、ｑの主成分得点ｆdiの絶対値│ｆdi│を用いることができる。│ｆdi│は、クラスターＣdiの第一主成分ベクトルに沿う方向においてクエリー点ｑがクラスター境界からどれほど離れているかを示す。ｑがクラスターの境界に近いほどもう一方のクラスターに最近傍点が存する可能性が高いので、判断の「確からしさ」の指標として用いることができる。
【００４６】
好ましくは、このもう一方のクラスターを探索対象とする処理を実現するために、ＣＰＵ１１は、階層の深さｄにおけるｑの主成分得点ｆdiの絶対値│ｆdi│を計算する。そして、│ｆdi│が前述の閾値εより小さい場合、そのときの深さｄの値、主成分得点を計算したクラスターＣdiのノードＩＤおよび主成分得点ｆdiの符号（ゼロ以下か正かを示す値）をＲＡＭ１５上に確保した探索クラスター・テーブルに登録する。前記クラスターの両方の子ノードを辿れるようにするためである。
【００４７】
ＣＰＵ１１は、根ノードから順番に深い階層へ向けて子ノードを辿り、一つの葉ノードに至る。この一つめの葉ノードを距離計算の対象とする。
好ましくはＣＰＵ１１は、前述の探索クラスター・テーブルに登録されたクラスターがあるか否かを調べる。登録されたクラスターがあれば、そのクラスターのもう一方の子ノードについても葉ノードまで辿る。この二つめの葉ノードを距離計算の対象に加える。なお、探索クラスター・テーブルには、一つめの葉ノードまで辿ったときに登録されたクラスターの主成分得点ｆdiの符号が格納されている。ＣＰＵ１１は、この符号に基づいてもう一方の子ノードを判断する。
【００４８】
なお、既に両方の子ノードを辿ったクラスターについては、そのことが識別できるように、探索クラスター・テーブルに格納された符号を、ゼロ以下を示す値でも正を示す値でもない第三の値に書き換えてもよい。一例では、主成分得点ｆdiがゼロ以下を示す値として−１、正を示す値として１、第三の値としてゼロを用いる。
ＣＰＵ１１は、二つめの葉ノードへ向けて子ノードを辿る過程においても、ｑの主成分得点ｆdiの絶対値│ｆdi│が閾値εより小さい場合は、探索クラスター・テーブルにデータを追加登録する。
【００４９】
ＣＰＵ１１は、探索クラスター・テーブルに登録された全てのクラスターについて両方の子ノードを辿ってそれぞれの末端の葉ノードを特定する。特定された各葉ノードに属する各データ点について、ｑとの距離計算をそれぞれ実行する。それらデータ点のうち、ｑに対して最小の距離となるデータ点を最近傍点とする。
最近傍探索としては、最近傍点が最終的な出力である。ただし、この最近傍探索を用いた顔認識処理としては、100万件の顔画像のデータのうち、クエリーの顔画像に最も近いものを最終的な出力とする必要がある。その処理は次のようにして実現できる。各データ点には、それが100万件の顔画像データのうちどのデータから抽出されたものかが対応付けられてデータベースに登録されている。そこで、最近傍点が抽出された顔画像データをその顔画像データを顔認識の結果として出力する。以上の手順は一般にバックトラッキングと呼ばれるもので、それを本近似最近傍探索法に適用したものがこれまでの説明である。
【００５０】
以上のように、各ノードにおいて、クエリー点ｑに係る主成分得点ｆdiの符号によりクエリー点の所属する子ノードを決定し、二分木のノードを辿って探索を行う。一つの葉ノードまで辿る限りにおいては、二分木生成工程はｍ回の繰り返し計算を行えば足りる。しかし、一つの葉ノードに存在するデータ点のみを距離計算の対象とするだけでは、十分な探索精度が得られないことがある。ｑがクラスターの境界近くにあって探索していないクラスターの中に最近傍の点が存する場合があるためである。そこで探索するクラスターの範囲を合理的に拡張するため、指標としての│ｆdi│および閾値εを導入する。もしクエリー点とクラスターの境界との距離がεよりも小さければ、境界の反対側にあるクラスターも探索する。
【００５１】
図６は、この発明に係る探索クラスター・テーブルの具体例を示す説明図である。図６の探索クラスター・テーブルには、ＩＤが２０２、３０４および３０３のノードが登録されている。ノードＩＤは、図４の木に対応している。ノード２０２を最初に辿ったときの主成分得点ｆ202の符号は正（＋１）である。図４の木では、右側の子ノード３０４へ進んだことを示している。そのノード３０４も探索クラスター・テーブルに登録されている。ノード３０４を最初に辿ったときのｆ304の符号はゼロ以下（−１）である。よって、左側の子ノード４０７へ進んだことを示している。深さｄ＝４のノードは登録されてない。│ｆ407│が閾値ε以上であったことが分かる。よって、片方のノードだけを辿ったことになる。ここでは、ノード４０７の右側の子ノード５１４が第１の葉ノードであったとする。
【００５２】
第１の葉ノードまで辿った後、ＣＰＵ１１が図６の探索クラスター・テーブルを参照すると、ノード２０２が登録されている。最初に辿ったときの符号は正である。そこで、ＣＰＵ１１は、ノード２０２のもう一方の子ノード、即ち、ｆ202の符号がゼロ以下の各データ点が属するノード３０３を探索する。図６には、そのノード３０３が登録されている。よって、最初にノード３０３を探索したときの│ｆ303│が閾値ε以上であったことが分かる。他のノードは図６では登録されていないので、片方のノードだけを辿ったことがわかる。ここでは、ノード４０６を経た葉ノード５１２が第２の葉ノードであったとする。
【００５３】
第２の葉ノードまで辿った後、ＣＰＵ１１がさらに図６の探索クラスター・テーブルを参照すると、ノード３０４が登録されている。最初に辿ったときの符号はゼロ以下であるので、次は正の符号に対応する子ノード４０８を経て葉ノードへ進む。ここでは、ノード５１５が第３の葉ノードであったとする。
【００５４】
さらに、探索クラスター・テーブルにはノード３０３が登録されている。最初に辿ったときの符号は正であるので、次はゼロ以下の符号に対応する子ノード４０５を経て葉ノードへ進む。ここでは、ノード５１０が第４の葉ノードであったとする。
以上のように、ＣＰＵ１１は、探索クラスター・テーブルに登録された各ノードのもう一方の子ノードを辿る。その結果として見出された葉ノード、図６の例では、第１〜４の葉ノード５１４、５１２、５１５および５１０に属する各データ点について、ｑとの距離計算を実行し最近傍点を決定する。
【００５５】
なお、これまでの説明では、ＣＰＵ１１が第１の葉ノードまで辿った後に探索クラスター・テーブルを参照して第２の葉ノードまで辿るものとした。その後さらに探索クラスター・テーブルを参照して第３の葉ノードまで辿るものとした。また、ＣＰＵ１１は、第３の葉ノードまで辿った後に探索クラスター・テーブルを参照して第４の葉ノードまで辿るものとした。前述したバックトラッキングである。しかし、探索の手順はこれに限らない。異なる態様として、階層ごとに探索すべきノードをすべて探索し、その結果として次の階層で探索の対象とすべきノードを探索クラスター・テーブルに登録した後に次の階層へ進むようにしてもよい。次の階層では、探索クラスター・テーブルに登録されたノードを全て探索し、その結果としてさらに次の階層で探索対象とすべきノードを探索クラスター・テーブルに登録する。二分木の末端の葉ノードに達するまでこれを繰り返す。いずれの手順でも同様の結果が得られる。両者はいずれもこの発明に含まれる。前者の態様、即ちバックトラッキングの方が後者の態様に比べてノードの探索に要するメモリーを節約することができる。ただし、所要メモリー量に有意差が生じるのは大量の葉ノードを探索する場合である。
【００５６】
図７は、この発明に係る探索処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図７で、第１および２行目は、前述の登録処理によって予め生成された二分木構造（ノードリスト）を対象に探索することを示している。なお、探索の対象とするノードのＩＤを格納するのは変数listである。ＣＰＵ１１は、変数listの初期値として、根ルートのＩＤを設定する。
第３行目は、前記ノードリストの根（深さｄ＝１）から葉ノードの前階層（ｄ＝ｍ）まで処理を繰り返すことを示している。繰り返す処理は、第４〜１９行目に記載されている。
第４行目は、深さｄのノードのうち、探索の対象とする各ノードｎについて、第５〜１３行目に記載の処理を繰り返すことを示している。探索の対象とするノードは、この行の処理に至るまでに、変数listに格納されている。初期値として、第１行目の処理で根ノードのＩＤが格納されている。その後は、第８、１２および１４行目の処理で、次の階層で探索すべき対象が一時変数tempに格納される。第１８行目の処理で、変数listに次の階層における探索対象が累積的に格納される。
【００５７】
ＣＰＵ１１は、クエリーｑが与えられたとき、その主成分得点を計算し、主成分得点の絶対値が予め定められた正の値ε以下か否かを判断する（第５行目）。なお、ｑの主成分得点を得るために、ｑと主成分ベクトルｐとの内積を計算する。各ノードの主成分ベクトルｐと平均ベクトルは、登録処理の際にデータベースに格納されている（第６〜７行目）。
ｑの主成分得点の絶対値がε以下の場合、ＣＰＵ１１は、対象としているノードｎの両方の子ノードを探索の対象とすべく一時変数tempに両方の子ノードのノードＩＤを格納する。ここで、一時変数tempは、次の階層において探索の対象とすべきノードのＩＤを格納する（第８〜９行目）。両方の子ノードを探索するために、探索クラスター・テーブルを用いる手法は既に説明した。
【００５８】
一方、ｑの主成分得点の絶対値がεより大きい場合（第１０行目）、ＣＰＵ１１は、ｑの主成分得点に応じて以下のように処理を行う。ｑの主成分得点がゼロ以下の場合（第１１行目）、ＣＰＵ１１は、一時変数tempに左側の子ノードのＩＤを格納し、探索の対象とする（第１２行目）。図３の登録処理において、左側の子ノードは主成分得点がゼロ以下のデータ点を格納している。
【００５９】
一方、ｑの主成分得点が正の場合（第１３行目）、右側の子ノードのＩＤを一時変数tempに格納し探索の対象とする（第１４行目）。図３の登録処理において、右側の子ノードは主成分得点がゼロより大きいデータ点を格納している。
そして、ＣＰＵ１１は、一時変数tempの内容を変数listに代入する（第１８行目）。よって、変数listは、探索すべきノードのＩＤを格納する。
【００６０】
最後の深さｍに至るまで処理を繰り返し、変数listに格納されたノードＩＤに含まれるデータ点、即ち葉ノードのうち探索すべきノードに含まれる各データ点について、ｑとの距離をそれぞれ計算し、最も近い距離にあるデータ点を最近傍点とする（第２０〜２３行目）。
【００６１】
≪実験例≫
この発明の有効性を示すため、近似最近傍探索法と従来の線形探索との比較実験を行った。線形探索については、打ち切りなしの場合および打ち切りありの場合の両方を比較対象とした。線形探索の打ち切りなしとは、全てのデータ点ｐとクエリー点ｑとの距離を計算し最も距離の短いデータ点を見つける方法である。これは、最も単純であるが計算時間のかかる方法である。線形探索の打ち切りありとは、１件のデータ点ｐとクエリー点ｑの距離の計算途中にそれまでに見つかっている最も近いデータ点との距離よりも長くなれば、そこで計算を打ち切って次のデータ点ｐとクエリー点ｑとの距離計算に移る方法である。データ点ｐとクエリー点ｑの距離は２乗距離（ユークリッド距離の２乗）で定義され、それは各次元毎の差の２乗の和である。
【００６２】
この発明による近似最近傍探索法については、クラスター数、すなわち木の高さｍとノード間の境界までの距離閾値εを種々変化させて最適な値を決定した。データ点は、以下のＭＡＴＬＡＢコードのように、３０次元データを正規乱数で作成した。各次元（変数）の標準偏差を１００から４００までの一様乱数で与えた。データ点総数は１００万件である。
【００６３】
【数４】
【００６４】
クエリー点は同様にして作成した１０００件のデータ点である。計算機はDell Precisi on T3500 Intel（R）Xeon（R）W3250 （2.67GHz)CPU, 3.25 MB．OS はWindows XP である。
線形探索の打ち切りなしで、平均検出時間は284.0 ms、打ち切りありでは112.8 ms であった。
【００６５】
図８は、この発明による近似最近傍探索と従来の線形探索との比較実験の結果を示すグラフである。図８で、横軸は線形探索の打ち切りなし（平均検出時間は284.0 ms）を100％として計算時間をパーセントで示している。縦軸は正しく最近傍データを見つけた割合を％で示している。図８に示すように階層の深さｍはｍ＝１５が最適である。したがって葉ノードの数は２15＝３２７６８が最適である。表１は、実際の時間で示している。これらのテスト結果は、コンパイラーの最適化オプションを用ない場合のものであるが、ｃ言語のVisual c の最適化オプションを用いれば、ｍ＝１３が最適であり、たとえば平均検出時間1.45msで精度80％であった。線形探索の打ち切り有りを100％としたときの4％の時間で80％の精度が得られている。
【表１】
【００６６】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００６７】
１、２、３、４：クラスター
１１：ＣＰＵ
１３：ＲＯＭ
１５：ＲＡＭ
１７：データベース格納部
１９：指示入力部
２１：表示部
２３：通信インターフェイス部
２５：コンピュータ
【特許請求の範囲】
【請求項１】
コンピュータが、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、
前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法。
【請求項２】
前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項１に記載の方法。
【請求項３】
前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、
前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、
前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す請求項１または２に記載の方法。
【請求項４】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする工程、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割工程、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものである請求項１〜３の何れか一つに記載の方法。
【請求項５】
主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、
前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置。
【請求項６】
前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項５に記載の装置。
【請求項７】
前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、
前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、
前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す請求項５または６に記載の装置。
【請求項８】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベ
クトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割部、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものである請求項５〜７の何れか一つに記載の装置。
【請求項９】
主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、
前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラム。
【請求項１】
コンピュータが、主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、
前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法。
【請求項２】
前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項１に記載の方法。
【請求項３】
前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、
前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、
前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す請求項１または２に記載の方法。
【請求項４】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする工程、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割工程、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものである請求項１〜３の何れか一つに記載の方法。
【請求項５】
主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、
前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置。
【請求項６】
前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項５に記載の装置。
【請求項７】
前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、
前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第１および第２子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第１子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第２子クラスターのみを探索クラスターとし、
前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す請求項５または６に記載の装置。
【請求項８】
前記データベースは、（i）登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、（ii）親クラスターに属する各ベクトルデータの平均としての平均ベ
クトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、（iii）親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、（iv）ゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第１の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第２の子クラスターに分類するクラスター分割部、（v）生成された第１および第２の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものである請求項５〜７の何れか一つに記載の装置。
【請求項９】
主成分得点に応じた第１および第２子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、
前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、
補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、
前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第１子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第２子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、
前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、
末端の階層の１以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−７３２５６（Ｐ２０１３−７３２５６Ａ）
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願番号】特願２０１１−２０９５８８（Ｐ２０１１−２０９５８８）
【出願日】平成２３年９月２６日（２０１１．９．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＷＩＮＤＯＷＳ
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願日】平成２３年９月２６日（２０１１．９．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＷＩＮＤＯＷＳ
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
[ Back to top ]