"コンピュータが、主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法。前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項1に記載の方法。前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第1および第2子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第1子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第2子クラスターのみを探索クラスターとし、前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す請求項1または2に記載の方法。前記データベースは、i登録すべきベクトルデータの集合を親クラスターの初期値とする工程、ii親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、iii親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、ivゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第1の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第2の子クラスターに分類するクラスター分割工程、v生成された第1および第2の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものである請求項1~3の何れか一つに記載の方法。主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置。前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなる請求項5に記載の装置。前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第1および第2子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第1子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第2子クラスターのみを探索クラスターとし、前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す請求項5または6に記載の装置。前記データベースは、i登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、ii親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、iii親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、ivゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第1の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第2の子クラスターに分類するクラスター分割部、v生成された第1および第2の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものである請求項5~7の何れか一つに記載の装置。主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラム。LSHなど、ハッシュ関数を用いた手法は、距離計算に要する処理時間が短縮されるという利点があるが、ハッシュテーブルを格納するメモリー領域を必要とする。また、各データ点にハッシュ関数を適用して得られるハッシュ値は、一種の乱数と捉えることができ、探索の精度はランダムに変化する。安定した精度を得るためには十分な数のデータ点を探索することが前提となるが、データ点が増加すると探索に要する処理時間も増大するため両者はトレードオフの関係にあるとの見方もできる。一方、二分木構造を用いた手法は、ハッシュ関数を用いた手法に比べると木構造を保持するために必要なメモリー容量が一般に少なくてすむ。また、ハッシュ関数を用いて乱数を発生させることがないため個々の探索の精度が安定している。しかし、ハッシュ関数を用いた手法に比べると、木構造を辿って探索を行うために要する処理時間が一般的に長くかかると考えられている。しかし、二分木によって距離計算対象とすべきデータ点を効率的に絞り込むことができれば、処理時間を短縮できる。この発明は、以上のような事情を考慮してなされたものであって、主成分分析PrincipalComponentAnalysis、PCAに基づく二分木を用いて最近傍のデータ点を効率的に探索して推定し、処理時間の短縮を実現する近似最近傍探索方法、装置およびプログラムを提供する。この発明は、コンピュータが、主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする工程とを実行することを特徴とする近似最近傍探索方法を提供する。また異なる観点から、この発明は、主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部とを備えることを特徴とする近似最近傍探索装置を提供する。さらに異なる観点から、この発明は、主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースおよびクエリーとしてのベクトルデータが与えられたとき、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターにする初期化部と、前記クエリーから対象クラスターに属する各ベクトルデータの平均としての平均ベクトルを差引いて前記クエリーを補正するクエリー補正部と、補正されたクエリーと、前記対象クラスターの主成分分析を行って得られる第一主成分ベクトルとの内積を計算して前記対象クラスターに対するクエリー主成分得点とするクエリー得点算出部と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを前記クエリーに対する最近傍点が含まれ得る探索クラスターとし、前記クエリー主成分得点が正ならば前記対象クラスターを親クラスターとしたときの第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択部と、前記選択部で決定された探索クラスターを対象クラスターとして前記クエリー補正部、前記クエリー得点算出部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返す二分木探索部と、末端の階層の1以上の探索クラスターに属する各ベクトルデータとクエリーとの距離を計算し、クエリーから最も近い距離のベクトルデータを最近傍のデータとする最近傍点決定部としてコンピュータを機能させることを特徴とする近似最近傍探索プログラムを提供する。近似最近傍探索方法は、主成分得点に応じた第1および第2子クラスターを有する二分木の階層構造にベクトルデータが分類された近似最近傍探索用データベースを探索するにあたり、探索の対象とする対象クラスターの初期値を前記二分木の根ノードのクラスターとする工程と、前記クエリーから平均ベクトルを差引いて前記クエリーを補正するクエリー補正工程と、補正されたクエリーと、前記対象クラスターの第一主成分ベクトルとの内積を計算してクエリー主成分得点とするクエリー得点算出工程と、前記クエリー主成分得点がゼロ以下ならば前記対象クラスターを親クラスターとしたときの第1子クラスターを探索クラスターとし、前記クエリー主成分得点が正ならば第2子クラスターを探索クラスターとし、同じ階層のすべての対象クラスターについて探索クラスターを決定する選択工程と、前記選択工程で決定された探索クラスターを対象クラスターとして前記クエリー補正工程、前記クエリー得点算出工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返す二分木探索工程とを備えるので、クエリーとの距離計算を行うベクトルデータを絞り込むことができる。クエリー主成分得点はベクトルの内積という単純な計算で得ることができる。よって、最近傍とされるデータ点を効率的に探索できる。この発明による近似最近傍探索装置および近似最近傍探索プログラムも同様の効果を奏する。この発明において、クラスターは、同じ類に属するベクトルデータの集合を示すもので、二分木構造のノードに対応する。その具体的な態様の例は、各要素の値がメモリーに格納されたベクトルデータのリストである。この発明によれば、データベースは平衡な完全二分木の構造を有する。末端の葉ノードのクラスターを除いた各クラスターは、2つの子クラスターをそれぞれ有する。即ち、二分木の根と葉を除いた階層高さにある各クラスターは、根ノード側にあるクラスターの子ノードであると同時に、葉ノード側にあるクラスターの親ノードである。主成分分析は、複数の変数間の相関を把握するために導入される公知の手法であって、クラスターが与えられたとき第一主成分ベクトルおよび主成分得点主成分スコアとも呼ばれるを算出する手法は公知である。例えば、第一主成分ベクトルは、共分散行列の固有値問題を解いて得ることができる。以下、この発明の好ましい態様について説明する。この発明によるデータベースの生成方法において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。さらに、前記選択工程に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定工程をさらに備え、前記選択工程は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第1および第2子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第1子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第2子クラスターのみを探索クラスターとし、前記二分木探索工程は、前記クエリー補正工程、前記クエリー得点算出工程、前記精度判定工程および前記選択工程を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。また、前記データベースは、i登録すべきベクトルデータの集合を親クラスターの初期値とする工程、ii親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正工程、iii親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出工程、ivゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第1の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第2の子クラスターに分類するクラスター分割工程、v生成された第1および第2の子クラスターをそれぞれ親クラスターとして前記平均補正工程、前記得点算出工程および前記クラスター分割工程の処理を繰り返し、予め定められた階層の二分木を生成する二分木生成工程により生成されたものであってもよい。前記平均補正工程は、各クラスターについて得られた平均ベクトルを前記データベースの一部として格納し、前記得点算出工程は、各クラスターについて得られた第一主成分ベクトルを前記データベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。さらに、この発明は、前述したこの発明によるデータベースの生成装置において、前記データベースは、その二分木の階層構造における末端の階層のクラスターごとに各ベクトルデータが連続するように各ベクトルデータの順序が並べ替えられてなるものであってもよい。このようにすれば、クラスターごとの各ベクトルデータが連続していない場合に比べて、クラスターごとにベクトルデータを読み込んで探索に係る計算をする際の処理時間を短縮することができる。さらに、前記選択部による処理に先立って、前記対象クラスターのクエリー主成分得点の絶対値を得、得られた絶対値が閾値以下か否かを判断する精度判定部をさらに備え、前記選択部は、前記絶対値の大きさが前記閾値以下のときは前記対象クラスターを親クラスターとしたときの第1および第2子クラスターをいずれも探索クラスターとし、前記クエリー主成分得点の絶対値が前記閾値より大きいときは、前記クエリー主成分得点がゼロ以下ならば前記第1子クラスターのみを探索クラスターとし、前記クエリー主成分得点が正ならば前記第2子クラスターのみを探索クラスターとし、前記二分木探索部は、前記クエリー補正部、前記クエリー得点算出部、前記精度判定部および前記選択部による処理を前記二分木の末端の階層に至るまで繰り返すようにしてもよい。ここで、クエリー主成分得点の絶対値は、第一主成分ベクトルに沿う方向においてクエリーがクラスターの境界からどれだけ離れた距離にあるかを表す。クエリーがクラスターの境界に近いときは、前記境界の向こう側のクラスターに最近傍点が存する可能性が無視できない。この発明によれば、前記距離が閾値以下のときは前記境界の両側のクラスターをいずれも探索クラスターとするので、一方のクラスターのみを探索クラスターとする場合に比べて真の最近傍点を探索できる可能性がより高くなる。また、この発明によるデータベースの生成装置において、前記平均補正部は、各クラスターについて得られた平均ベクトルをデータベースの一部として格納し、前記得点算出部は、各クラスターについて得られた第一主成分ベクトルをデータベースの一部として格納してもよい。このようにすれば、格納された平均ベクトルおよび第一主成分ベクトルを探索の際に用いることができる。前記データベースは、i登録すべきベクトルデータの集合を親クラスターの初期値とする初期設定部、ii親クラスターに属する各ベクトルデータの平均としての平均ベクトルを各ベクトルデータから差引いて差分ベクトルをそれぞれ生成する平均補正部、iii親クラスターの主成分分析を行って得られる第一主成分ベクトルと親クラスターに属する各差分ベクトルとの内積をそのベクトルデータの主成分得点としてそれぞれ計算する得点算出部、ivゼロ以下の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第1の子クラスターに分類し、正の主成分得点が得られたときはその主成分得点に係るベクトルデータを前記第2の子クラスターに分類するクラスター分割部、v生成された第1および第2の子クラスターをそれぞれ親クラスターとして前記平均補正部、前記得点算出部および前記クラスター分割部による処理を繰り返し、予め定められた階層の二分木を生成する二分木生成部により生成されたものであってもよい。この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。≪主成分分析に基づく2分木を用いる近似最近傍探索≫図1は、この発明に係る二分木を用いたクラスター分割の様子を示す説明図である。クラスター分割は、主成分分析に基づいて行われる。図1に示すように二分木の根ルートノードに相当する全データ点の集合S図1のクラスター1~4を合わせた全体のクラスターが与えられたとする。近似最近傍探索の処理を実行するコンピュータは、そのクラスターSをまず2分割し、2つのノード図1のクラスター1および3のクラスターとクラスター2および4のクラスターを作る。次に、前記コンピュータは、2つのノードをそれぞれ2分割する。即ち、クラスター1および3のデータ点集合を2分割し、リーフノードとしてのクラスター1およびクラスター3を作る。また、クラスター2および4のデータ点集合を2分割し、リーフノードとしてのクラスター2およびクラスター4を作る。以上のように全データ点の集合Sに対して二分割を繰り返して二分木構造を生成し、各データ点をリーフノードとしてのクラスター1~4に分類することによって、近似最近傍探索用のデータベースを生成する。≪データベースへの登録処理と探索処理≫この発明に係る近似最近傍探索の処理およびその近似最近傍探索の前提となるデータベースの登録処理は、コンピュータが予め用意された処理プログラムを実行することによって実現される。登録処理を実行するコンピュータと近似最近傍探索の処理を実行するコンピュータは同一のものでもよいが、異なるものであってもよい。また、いわゆるクラウドコンピュータのように、登録処理および/または最近傍探索の処理探索処理を複数のコンピュータが協働して処理する態様であってもよい。図2は、この発明に係る登録処理を実行するコンピュータの、ハードウェア構成例を示すブロック図である。図2に示すように、コンピュータ25は、ROM13、CPU11、RAM15、データベース格納部17、指示入力部19および通信インターフェイス部23を備える。ROM13は、登録処理に係るプログラムを予め格納する。CPU11は、ROM13に格納されたプログラムを実行する。RAM15は、CPU11が処理に用いるワークエリアを提供する。データベース格納部17は、生成されたデータベースを格納する、指示入力部19は、ユーザーからの指示を受付ける、表示部21は、ユーザーに対して情報を表示する。通信インターフェイス部23は、外部の機器と通信を行う。コンピュータ25の具体的態様としては、ファイルサーバやパーソナルコンピュータが挙げられる。また、必要とされるメモリー容量や処理能力を満足すれば、携帯情報端末、高機能携帯電話や機器に組み込まれたマイクロコンピュータも前記態様に含まれる。データベース格納部17としては、例えばフラッシュメモリなどの不揮発性記憶素子やハードディスクドライブなどの記憶装置が適用可能である。指示入力部19の具体的態様としては、キーボード、マウス、タッチパネルなどが挙げられる。表示部21の具体的態様としては液晶や有機ELを用いた表示装置が挙げられる。通信インターフェイス部23の具体的態様としては、有線、無線を問わずインターネットやLANに接続される各種通信インターフェイスやUSBインターフェイスなどが挙げられる。探索処理を実行するコンピュータも同様のハードウェア構成を備える。以下の説明では、簡単のために登録処理と探索処理が同じコンピュータで実行されるものとする。≪登録処理:二分木の生成≫この実施形態で、CPU11が、データベースにデータ点を登録する際に二分木構造を如何に生成するのか、その処理手順について具体的に述べる。データ点の集合の一例として、各顔画像から抽出された特徴量データが与えられたとする。各特徴量データは、それが抽出された顔画像のデータと関連付けて提供されるものとする。各データ点は30次元のベクトルデータであって、データ点数は100万件であるとする。これは、100万人の顔画像が登録されたデータベースからある人物の顔認識を行うことを意味する。CPU11は、データ点の全体集合Sを対象にSに属する全データの平均値平均ベクトルを求める。さらに、全体集合Sを対象に主成分分析を行い、第一主成分ベクトルを求める。全体集合Sは、二分木構造の根ノードに対応する。CPU11は、各データ点を表すベクトルデータから前記平均ベクトルを引いた差分のベクトルを求め、その差分ベクトルと前記第一主成分ベクトルとの内積を、各データ点の主成分得点として求める。そして、主成分得点の符号の正負、詳細には主成分得点がゼロ以下か正かに応じて全体集合Sに属するデータ点を2分割する。ここで、前記差分ベクトルと前記第一主成分ベクトルとの内積は、前記差分ベクトルを第一主成分ベクトルに射影したときのベクトル成分といえる。そして、前記差分ベクトルは、各データ点を表すベクトルから平均ベクトルを引いたものであるが、これは各データ点を表すベクトルの座標原点を全データの平均値の座標点にとりなおしたベクトルといえる。よって、各データ点の主成分得点、即ち、前記平均値を原点とした第一主成分ベクトル方向の成分は、全体集合Sに属する約半数のデータ点が正の値をとり、約半数のデータ点がゼロ以下の値をとる。結果的に、根ノードは、主成分得点がゼロ以下の約50万件のデータ点の子クラスター子ノードC201と、主成分得点が正の約50万件のデータ点の子クラスターC202とに分けられる。続いてCPU11は、それぞれの子クラスターC201およびC202を同様の手順でさらに2分割する。この処理を階層の深さm回mは末端の葉ノードの階層を除いた二分木の高さを表す自然数だけ繰り返して、100万件の全データを2m個のクラスターノード、Cmi1≦i≦2mに分ける。mの値は、正しく最近傍点を探し出す割合が最もよくなるように予め定められる。CPU11は、各クラスターに属するデータ点の平均値、即ち平均ベクトルと主成分ベクトルとをそれぞれデータベース格納部17に記憶しておく。以上の手順で生成される二分木構造は、根ノードから2分割を繰り返して生成される高さm1の完全二分木である。m1階層目に得られる2m個のクラスターはそれぞれ葉ノードと呼ばれる。各データ点には、どの葉ノードのクラスターに含まれるかのクラスター番号が対応付けられてデータベースに格納される。なお、各データ点とそれが抽出された顔画像のデータとの対応関係および各顔画像のデータも前記データベースに格納される。クラスターノードの分割について、さらに詳しく説明する。ある一つのクラスターに入っているデータ点の集合をとする。ここでxkは距離空間Rdにおけるベクトルデータ縦ベクトルを表す。xkをxkから全データの平均値を引いたベクトル、即ち、平均値補正されたベクトルとする。Nはそのクラスターに入っているデータ点の数を表す。次にの主成分得点fkk=1,...,Nを散布行列XTXを用いて求める。ここで、あるクラスのデータ点の集合Xの主成分得点fkは、Xの特異値のうちで最大のものに対応付けられる。fkの符号がゼロ以下か正かに応じて、各クラスターに所属するデータを二つの子クラスターに分割する。以上が、クラスター分割の詳細である。ここで、CPU11は、各データ点をクラスター毎に並べ替える。このことで、プログラミング言語のコンパイラーの最適化機能が有効になり、高速の検出が可能になる。即ち、元のデータは読み込みの順に並べられていてクラスター毎には並んでいなく、一つのクラスターに属するデータはひと塊りにはなっていない。そのために、クラスター毎にその中のデータを順に読み込んで計算する場合の計算速度が遅くなる。特にプログラミング言語のコンパイラーの最適化オプションによる計算高速化が十分に行われない。好ましくは、クラスター毎にひと塊りとなるようにデータを並べ替える処理を近似最近傍探索用データベースの生成方法で行う。このことで、コンパイラーの最適化機能が有効に働き近傍探索の計算を早くすることができる。図3は、この発明に係る登録処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図3で、第1行目は、木の根深さd=1から葉ノードの一つ手前の階層d=mに至るまで処理を繰り返すことを示している。繰り返す処理は、第2~15行目に記載された二分木の生成である。第2行目は、処理の対象とする階層の各ノードnについて、第3~14行目に記載の処理を繰り返すことを示している。CPU11は、登録すべきデータ点が与えられたとき、ノードnのクラスターに属する全てのデータ点の平均として平均ベクトルを計算し第3行目、平均値補正されたベクトルxを計算する第4行目。続いてCPU11は、最も大きな固有値に対応する主成分ベクトルpを計算する第5~6行目。pは第一主成分ベクトルである。ここで、計算により求められた平均ベクトルと主成分ベクトルpとを記憶する第7行目。さらにCPU11は、ノードnの各ベクトルデータデータ点xについて第8行目第9~13行目の処理を実行する。即ち、各データ点の主成分得点がゼロ以下か否かをしらべ第9行目、ゼロ以下であれば左側の子ノードにそのデータ点を格納する第10行目。左側の子ノードは、第1子ノードに相当する。一方、主成分得点が正であれば第11行目、右側の子ノードにそのデータ点を格納する第12行目。右側の子ノードは、第2子ノードに相当する。このようにして、ノードnの各データ点を左右いずれかの子ノードに分割し、この分割を木の根から深さd=mまで繰り返すことで、高さm1の二分木構造を生成する。図4は、この発明に係る登録処理により生成された木構造の一例を示す説明図である。図4で、○印はノードを示しており、上位のノードと下位のノードを結ぶ線は親ノードと子ノードの関係を示している。その線の横に記したf≦0は主成分得点がゼロ以下のデータ点が属する子ノードを、f>0は主成分得点が正のデータ点が属する子ノードをそれぞれ示している。図4に示す木は、木の高さm1=5である。各ノードを示す○印の中の番号は、各ノードを識別するIDノードIDである。根ノードのノードIDは101であり、その子ノードのノードIDは201と202である。ノードIDの100の位は階層の深さdに対応しており、10および1の位は同じ階層に属する各ノードにユニークな番号である。図5は、この発明に係るデータベースの具体的な構造の例を示す説明図である。データベース格納部17に格納されるデータの例を示している。図5でaは各データ点に係る構造を示している。aで横方向に並ぶ一連の数値、即ち各行の数値は一つのデータ点に対応する。図5の例では、100万個のデータ点が登録されているので、縦方向に100万個の数値が並ぶ。aの左端の欄は、各データ点を識別する点IDである。各データ点に1~1000000の数字を付している。aの右端の欄は、各データ点を結ぶリンクドリストである。このリンクドリストは、同じ葉ノードに属する他の点の点IDを格納する。ゼロの値は、リストの末尾を示している。aの左端欄と右端欄に挟まれた部分は、各データ点を表すベクトルデータの値である。この実施形態において、各データ点は30次元のベクトルデータである。各次元に対応する30個の実数値が各データ点のベクトルを表す。bはaの右端欄のリンクドリストの先頭の点IDを示している。16個のIDは、各葉ノードの先頭の点IDを示している。即ち、aの右端欄のリンクドリストは、葉ノードの単位でリンクドリストを格納している。CPU11は、このリンクドリストをもとにデータを並び替える。その結果、クラスター毎にひと塊りになったデータベースが作成される。そのデータベースを用いて近似最近傍探索が行われる。≪探索処理:クエリー点の最近傍にあると判断するデータ点の探索≫ここでは、クエリー点が与えられたときに、近似最近傍探索を行う方法を説明する。この実施形態において、クエリー点は、クエリーとして与えられた顔画像から抽出されたデータ点、即ちクエリーの特徴量としてのベクトルデータである。CPU11は、与えられた検索質問画像データベクトルqから平均ベクトルを引いて差分ベクトルを求める。前記平均ベクトルは、登録処理の際にデータベースの全データの集合Sに係る平均値のベクトルとして求められたものであり、データベース格納部17に格納されている。次に、CPU11は、qから平均ベクトルを引いた差分のベクトルqと全データ集合Sに係る第一主成分ベクトルpとの内積f≦<q,p>を計算する。fは、qの主成分得点である。この主成分得点fがゼロ以下の場合はqの最近傍のデータ点はクラスターC201に属しており、主成分得点fが正の場合はqの最近傍点はクラスターC202に属しているものとする。CPU11は、その次の階層についても同様の処理を繰り返す。即ち、深さdの階層において、qの最近傍点が属しているとされたクラスターCdiの平均ベクトルをqから引いて差分のベクトルqdiを求める。例えば、深さd=2の階層において、qの最近傍点がクラスターC202に属しているとされたとする。CPU11は、クラスターC202の平均ベクトルをqから引いて、差分のベクトルq202求める。この場合、深さd=2、その深さd=2の階層に属する各ノードにユニークな番号i=02である。次に、CPU11は、qdiとクラスターCdiの第一主成分ベクトルpdiとの内積fdi=<qdi,pdi>を計算する。fdiは、クラスターCdiについてのqdiの主成分得点である。先の例については、f202=<q202,p202>を計算することになる。この主成分得点fdiがゼロ以下の場合、qdiの最近傍のデータ点はクラスターCに属しており、主成分得点fdiが正の場合はqdiの最近傍点はクラスターCに属しているものとする。ここで、図4に示す二分木の例で、親ノードとしてのクラスターCdiから生成される深さd1の2つの子ノードのノードIDは、左側の子ノードが2i-1であり、右側の子ノードが2iである。例えば、クラスターC202から生成される左側の子ノードはC303であり、右側の子ノードはC304である。以上のようにして、CPU11は、根ノードから順番に深い階層へ向けて子ノードを辿り、qの最近傍点が属する葉ノードを判断する。そして、最近傍点が属すると判断した葉ノードに属する各データ点とqとの距離計算を行って、最も距離の小さいデータ点を最近傍点とする。二分木を葉ノードの階層まで辿ることによって、qとの距離計算を行うべきデータ点の数を絞り込む。ただし、qがクラスターの境界近くに存する場合は、最近傍点が属すると判断した子ノードでない方に最近傍点が存することがあり得る。このような判断の誤りを防ぐために、判断の確からしさを示す指標とその指標についての閾値εとを予め定めておき、指標が閾値εより小さい場合はもう一方のクラスターについても探索を行うことが好ましい。前記指標として、qの主成分得点fdiの絶対値│fdi│を用いることができる。│fdi│は、クラスターCdiの第一主成分ベクトルに沿う方向においてクエリー点qがクラスター境界からどれほど離れているかを示す。qがクラスターの境界に近いほどもう一方のクラスターに最近傍点が存する可能性が高いので、判断の確からしさの指標として用いることができる。好ましくは、このもう一方のクラスターを探索対象とする処理を実現するために、CPU11は、階層の深さdにおけるqの主成分得点fdiの絶対値│fdi│を計算する。そして、│fdi│が前述の閾値εより小さい場合、そのときの深さdの値、主成分得点を計算したクラスターCdiのノードIDおよび主成分得点fdiの符号ゼロ以下か正かを示す値をRAM15上に確保した探索クラスターテーブルに登録する。前記クラスターの両方の子ノードを辿れるようにするためである。CPU11は、根ノードから順番に深い階層へ向けて子ノードを辿り、一つの葉ノードに至る。この一つめの葉ノードを距離計算の対象とする。好ましくはCPU11は、前述の探索クラスターテーブルに登録されたクラスターがあるか否かを調べる。登録されたクラスターがあれば、そのクラスターのもう一方の子ノードについても葉ノードまで辿る。この二つめの葉ノードを距離計算の対象に加える。なお、探索クラスターテーブルには、一つめの葉ノードまで辿ったときに登録されたクラスターの主成分得点fdiの符号が格納されている。CPU11は、この符号に基づいてもう一方の子ノードを判断する。なお、既に両方の子ノードを辿ったクラスターについては、そのことが識別できるように、探索クラスターテーブルに格納された符号を、ゼロ以下を示す値でも正を示す値でもない第三の値に書き換えてもよい。一例では、主成分得点fdiがゼロ以下を示す値として-1、正を示す値として1、第三の値としてゼロを用いる。CPU11は、二つめの葉ノードへ向けて子ノードを辿る過程においても、qの主成分得点fdiの絶対値│fdi│が閾値εより小さい場合は、探索クラスターテーブルにデータを追加登録する。CPU11は、探索クラスターテーブルに登録された全てのクラスターについて両方の子ノードを辿ってそれぞれの末端の葉ノードを特定する。特定された各葉ノードに属する各データ点について、qとの距離計算をそれぞれ実行する。それらデータ点のうち、qに対して最小の距離となるデータ点を最近傍点とする。最近傍探索としては、最近傍点が最終的な出力である。ただし、この最近傍探索を用いた顔認識処理としては、100万件の顔画像のデータのうち、クエリーの顔画像に最も近いものを最終的な出力とする必要がある。その処理は次のようにして実現できる。各データ点には、それが100万件の顔画像データのうちどのデータから抽出されたものかが対応付けられてデータベースに登録されている。そこで、最近傍点が抽出された顔画像データをその顔画像データを顔認識の結果として出力する。以上の手順は一般にバックトラッキングと呼ばれるもので、それを本近似最近傍探索法に適用したものがこれまでの説明である。以上のように、各ノードにおいて、クエリー点qに係る主成分得点fdiの符号によりクエリー点の所属する子ノードを決定し、二分木のノードを辿って探索を行う。一つの葉ノードまで辿る限りにおいては、二分木生成工程はm回の繰り返し計算を行えば足りる。しかし、一つの葉ノードに存在するデータ点のみを距離計算の対象とするだけでは、十分な探索精度が得られないことがある。qがクラスターの境界近くにあって探索していないクラスターの中に最近傍の点が存する場合があるためである。そこで探索するクラスターの範囲を合理的に拡張するため、指標としての│fdi│および閾値εを導入する。もしクエリー点とクラスターの境界との距離がεよりも小さければ、境界の反対側にあるクラスターも探索する。図6は、この発明に係る探索クラスターテーブルの具体例を示す説明図である。図6の探索クラスターテーブルには、IDが202、304および303のノードが登録されている。ノードIDは、図4の木に対応している。ノード202を最初に辿ったときの主成分得点f202の符号は正1である。図4の木では、右側の子ノード304へ進んだことを示している。そのノード304も探索クラスターテーブルに登録されている。ノード304を最初に辿ったときのf304の符号はゼロ以下-1である。よって、左側の子ノード407へ進んだことを示している。深さd=4のノードは登録されてない。│f407│が閾値ε以上であったことが分かる。よって、片方のノードだけを辿ったことになる。ここでは、ノード407の右側の子ノード514が第1の葉ノードであったとする。第1の葉ノードまで辿った後、CPU11が図6の探索クラスターテーブルを参照すると、ノード202が登録されている。最初に辿ったときの符号は正である。そこで、CPU11は、ノード202のもう一方の子ノード、即ち、f202の符号がゼロ以下の各データ点が属するノード303を探索する。図6には、そのノード303が登録されている。よって、最初にノード303を探索したときの│f303│が閾値ε以上であったことが分かる。他のノードは図6では登録されていないので、片方のノードだけを辿ったことがわかる。ここでは、ノード406を経た葉ノード512が第2の葉ノードであったとする。第2の葉ノードまで辿った後、CPU11がさらに図6の探索クラスターテーブルを参照すると、ノード304が登録されている。最初に辿ったときの符号はゼロ以下であるので、次は正の符号に対応する子ノード408を経て葉ノードへ進む。ここでは、ノード515が第3の葉ノードであったとする。さらに、探索クラスターテーブルにはノード303が登録されている。最初に辿ったときの符号は正であるので、次はゼロ以下の符号に対応する子ノード405を経て葉ノードへ進む。ここでは、ノード510が第4の葉ノードであったとする。以上のように、CPU11は、探索クラスターテーブルに登録された各ノードのもう一方の子ノードを辿る。その結果として見出された葉ノード、図6の例では、第1~4の葉ノード514、512、515および510に属する各データ点について、qとの距離計算を実行し最近傍点を決定する。なお、これまでの説明では、CPU11が第1の葉ノードまで辿った後に探索クラスターテーブルを参照して第2の葉ノードまで辿るものとした。その後さらに探索クラスターテーブルを参照して第3の葉ノードまで辿るものとした。また、CPU11は、第3の葉ノードまで辿った後に探索クラスターテーブルを参照して第4の葉ノードまで辿るものとした。前述したバックトラッキングである。しかし、探索の手順はこれに限らない。異なる態様として、階層ごとに探索すべきノードをすべて探索し、その結果として次の階層で探索の対象とすべきノードを探索クラスターテーブルに登録した後に次の階層へ進むようにしてもよい。次の階層では、探索クラスターテーブルに登録されたノードを全て探索し、その結果としてさらに次の階層で探索対象とすべきノードを探索クラスターテーブルに登録する。二分木の末端の葉ノードに達するまでこれを繰り返す。いずれの手順でも同様の結果が得られる。両者はいずれもこの発明に含まれる。前者の態様、即ちバックトラッキングの方が後者の態様に比べてノードの探索に要するメモリーを節約することができる。ただし、所要メモリー量に有意差が生じるのは大量の葉ノードを探索する場合である。図7は、この発明に係る探索処理をコンピュータが実行する処理手順を擬似コードで示した説明図である。図7で、第1および2行目は、前述の登録処理によって予め生成された二分木構造ノードリストを対象に探索することを示している。なお、探索の対象とするノードのIDを格納するのは変数listである。CPU11は、変数listの初期値として、根ルートのIDを設定する。第3行目は、前記ノードリストの根深さd=1から葉ノードの前階層d=mまで処理を繰り返すことを示している。繰り返す処理は、第4~19行目に記載されている。第4行目は、深さdのノードのうち、探索の対象とする各ノードnについて、第5~13行目に記載の処理を繰り返すことを示している。探索の対象とするノードは、この行の処理に至るまでに、変数listに格納されている。初期値として、第1行目の処理で根ノードのIDが格納されている。その後は、第8、12および14行目の処理で、次の階層で探索すべき対象が一時変数tempに格納される。第18行目の処理で、変数listに次の階層における探索対象が累積的に格納される。CPU11は、クエリーqが与えられたとき、その主成分得点を計算し、主成分得点の絶対値が予め定められた正の値ε以下か否かを判断する第5行目。なお、qの主成分得点を得るために、qと主成分ベクトルpとの内積を計算する。各ノードの主成分ベクトルpと平均ベクトルは、登録処理の際にデータベースに格納されている第6~7行目。qの主成分得点の絶対値がε以下の場合、CPU11は、対象としているノードnの両方の子ノードを探索の対象とすべく一時変数tempに両方の子ノードのノードIDを格納する。ここで、一時変数tempは、次の階層において探索の対象とすべきノードのIDを格納する第8~9行目。両方の子ノードを探索するために、探索クラスターテーブルを用いる手法は既に説明した。一方、qの主成分得点の絶対値がεより大きい場合第10行目、CPU11は、qの主成分得点に応じて以下のように処理を行う。qの主成分得点がゼロ以下の場合第11行目、CPU11は、一時変数tempに左側の子ノードのIDを格納し、探索の対象とする第12行目。図3の登録処理において、左側の子ノードは主成分得点がゼロ以下のデータ点を格納している。一方、qの主成分得点が正の場合第13行目、右側の子ノードのIDを一時変数tempに格納し探索の対象とする第14行目。図3の登録処理において、右側の子ノードは主成分得点がゼロより大きいデータ点を格納している。そして、CPU11は、一時変数tempの内容を変数listに代入する第18行目。よって、変数listは、探索すべきノードのIDを格納する。最後の深さmに至るまで処理を繰り返し、変数listに格納されたノードIDに含まれるデータ点、即ち葉ノードのうち探索すべきノードに含まれる各データ点について、qとの距離をそれぞれ計算し、最も近い距離にあるデータ点を最近傍点とする第20~23行目。≪実験例≫この発明の有効性を示すため、近似最近傍探索法と従来の線形探索との比較実験を行った。線形探索については、打ち切りなしの場合および打ち切りありの場合の両方を比較対象とした。線形探索の打ち切りなしとは、全てのデータ点pとクエリー点qとの距離を計算し最も距離の短いデータ点を見つける方法である。これは、最も単純であるが計算時間のかかる方法である。線形探索の打ち切りありとは、1件のデータ点pとクエリー点qの距離の計算途中にそれまでに見つかっている最も近いデータ点との距離よりも長くなれば、そこで計算を打ち切って次のデータ点pとクエリー点qとの距離計算に移る方法である。データ点pとクエリー点qの距離は2乗距離ユークリッド距離の2乗で定義され、それは各次元毎の差の2乗の和である。この発明による近似最近傍探索法については、クラスター数、すなわち木の高さmとノード間の境界までの距離閾値εを種々変化させて最適な値を決定した。データ点は、以下のMATLABコードのように、30次元データを正規乱数で作成した。各次元変数の標準偏差を100から400までの一様乱数で与えた。データ点総数は100万件である。クエリー点は同様にして作成した1000件のデータ点である。計算機はDellPrecisionT3500IntelRXeonRW3250267GHzCPU325MB.OSはWindowsXPである。線形探索の打ち切りなしで、平均検出時間は2840ms、打ち切りありでは1128msであった。図8は、この発明による近似最近傍探索と従来の線形探索との比較実験の結果を示すグラフである。図8で、横軸は線形探索の打ち切りなし平均検出時間は2840msを100として計算時間をパーセントで示している。縦軸は正しく最近傍データを見つけた割合をで示している。図8に示すように階層の深さmはm=15が最適である。したがって葉ノードの数は215=32768が最適である。表1は、実際の時間で示している。これらのテスト結果は、コンパイラーの最適化オプションを用ない場合のものであるが、c言語のVisualcの最適化オプションを用いれば、m=13が最適であり、たとえば平均検出時間145msで精度80であった。線形探索の打ち切り有りを100としたときの4の時間で80の精度が得られている。前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。"