データベースに含まれる第1のベクトルデータxn次元をバイナリ符号であるy=y1y2...yd、ただし、n>>dに変換するハッシュ型近似最近傍探索方法において、下記式A~式Cより前記バイナリ符号yを得る下記ハッシュ関数hxに適用する変換行列rを定める方法であって、ここに、前記バイナリ符号yは次のように表わされる、前記第1のベクトルデータxを前記バイナリ符号yのビット数である前記dの次元に射影したときの第2のベクトルデータhを下記式Dで規定したとき、ただし、下記式Eが最小になる変換行列Fを求め、この変換行列Fを式Aの変換行列rとする、ただし、wijは前記データベースの第1のベクトルデータxにつき、式Fを最小とする重みである、ハッシュ関数の変換行列を定める方法。前記変換行列Fを求める際に前記重みwijを正規化する、請求項1に規定の方法。前記正規化は、前記データベースにおける第1のベクトルデータxでの近傍の分布を下記式Gのスコアで定義し、この分布スコアの対角行列D=diagd1......dmをもとめて、グラフラプラシアン理論に基づき行なう、請求項2に記載の方法。原データベースの原データから訓練データを抽出する訓練データ生成部と、前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、前記第1のハッシュ関数を用いて前記原データベースの原データをバイナリ符号化するバイナリ符号化部と、バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備える検索サーバと、入力された検索対象データを前記第1のハッシュ関数を用いてバイナリ符号化する第2のバイナリ符号化部を備えるクライアント端末と、前記クライアント端末の第2のバイナリ符号化部でバイナリ符号化された検索対象データと前記バイナリ符号化された原データとを比較する比較部と、を備える、ハッシュ型近似最近傍探索装置において、前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、ハッシュ型近似最近傍探索装置。ハッシュ型近似最近傍探索装置に用いられる検索サーバであって、原データベースの原データから訓練データを抽出する訓練データ生成部と、前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、前記第1のハッシュ関数を用いて前記原データベースの原データをバイナリ符号化するバイナリ符号化部と、バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備え、前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、検索サーバ。原データベースの原データから訓練データを抽出する訓練データ生成部と、前記訓練データを第1のベクトル化方法に基づきベクトル化処理する第1のベクトル化処理部と、ベクトル化処理された前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、前記原データを前記第1のベクトル化方法に基づきベクトル化処理する第2のベクトル化処理部と、前記第1のハッシュ関数を用いて前記ベクトル化処理された原データをバイナリ符号化するバイナリ符号化部と、バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備える検索サーバと、入力された検索対象データを前記第1のベクトル化方法に基づきベクトル化処理する第3のベクトル化処理部と、前記ベクトル化処理された検索対象データを前記第1のハッシュ関数を用いてバイナリ符号化する第2のバイナリ符号化部を備えるクライアント端末と、前記クライアント端末の第2のバイナリ符号化部でバイナリ符号化された検索対象データと前記バイナリ符号化された原データとを比較する比較部と、を備える、ハッシュ型近似最近傍探索装置において、前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められるハッシュ型近似最近傍探索装置。ハッシュ型近似最近傍探索装置に用いられる検索サーバであって、原データベースの原データから訓練データを抽出する訓練データ生成部と、前記訓練データを第1のベクトル化方法に基づきベクトル化処理する第1のベクトル化処理部と、ベクトル化処理された前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、前記原データを前記第1のベクトル化方法に基づきベクトル化処理する第2のベクトル化処理部と、前記第1のハッシュ関数を用いて前記ベクトル化処理された原データをバイナリ符号化するバイナリ符号化部と、バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備え、前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、検索サーバ。請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を利用するハッシュ型近似最近傍探索方法。前記データベースとして所定の訓練データベースを用いて、請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するステップと、特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換するステップと、検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するステップと、該検索対象バイナリ符号を前記テストデータバイナリ符号と比較するステップと、備えるハッシュ型近似最近傍探索方法。前記データベースとして所定の訓練データベースを用いて、請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するハッシュ関数特定部と、特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換する変換部と、検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するバイナリ符号作成部と、該検索対象バイナリ符号を前記テストデータバイナリ符号と比較する比較部と、備えるハッシュ型近似最近傍探索装置。コンピュータを、前記データベースとして所定の訓練データベースを用いて、請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するハッシュ関数特定部と、特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換する変換部と、検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するバイナリ符号作成部と、該検索対象バイナリ符号を前記テストデータバイナリ符号と比較する比較部と、備えるハッシュ型近似最近傍探索装置として機能させるコンピュータプログラム。インターネット上に存在するデータの量は拡大の一途をたどっているので、検索サイトに用いられる検索アルゴリズムには更なる精度の向上が期待されている。そこで本発明者らは、検索サイト用の検索アルゴリズムとして現在利用されている上記LSHに着目し、その改良、即ち検索精度の向上を検討した。その結果、LSHでは、そこで用いられる下記ハッシュ関数hisignにおいて変換ベクトルrがランダムに決められているため、ベクトルデータをバイナリ符号に変換したとき、もととなるベクトルデータ間の類似関係が充分に維持されないおそれがあると考えた。非特許文献3には、ベクトルデータが含まれるデータベースの特性を当該変換ベクトルに反映させ、もってバイナリ符号に変換する際にベクトルデータ間の類似関係維持を図ろうとする試みが示されている。しかしながら非特許文献3に記載の方法は、主成分分析法を利用しているため、非線形構造をなす多次元空間のデータベースの特性を充分に変換ベクトルに反映させることには無理がある。そこで本発明者らは、変換ベクトルにデータベースがなす非線形構造を反映させるべく鋭意検討を重ねた結果、この発明に想到した。即ち、この発明の第1の局面は次のように規定される。データベースに含まれる第1のベクトルデータxn次元をバイナリ符号であるy=y1y2...yd、ただし、n>>dに変換するハッシュ型近似最近傍探索方法において、下記式A~式Cより前記バイナリ符号を得る下記ハッシュ関数hxに適用する変換行列rを定める方法であって、ここに、前記バイナリ符号yは次のように表わされる、前記第1のベクトルデータxを前記バイナリ符号yのビット数である前記dの次元に射影したときの第2のベクトルデータhを下記式Dで規定したとき、ただし、下記式Eが最小になる変換行列Fを求め、この変換行列Fを式Aの変換行列rとする、ただし、wijは前記データベースの第1のベクトルデータxにつき、式Fを最小とする重みである、ハッシュ関数の変換行列を定める方法。第1の局面に規定の発明の基本原理を以下に説明する。高次元ベクトルデータをバイナリ符号に変換するアルゴリズムの多くが、次元削減のアルゴリズムに基づいている。次元削減の目的は、高次元空間上でベクトルデータがなす、低次元の部分空間を推定することである。近年、全体では非線形構造を成していても、局所的には通常のユークリッド空間と同じ構造をなす、多様体の性質を利用した非線形次元削減手法が幾つか提案されている。その内、LocallyLinearEmbeddingは、局所的な範囲で低次元の線形モデルをあてはめ、それらが滑らかに繋がるように全体の多様体を推定する。このLLEによる多様体構造の推定方法を用いて、ベクトルデータがなす非線形な関係をとらえたバイナリ符号を得る。以下、Weissらと同様に、問題の簡単化のため、式の制約条件を緩和する。局所的な範囲で低次元の線形モデルをあてはめるため、それぞれのベクトルデータxiを、近傍のベクトルデータxj∈Niを用いて再構成することを考える。これは、以下の再構成誤差を最小化することで表される。ここで、wijは、再構成する際の重みである。再構成には近傍のベクトルデータを用いるため、重みの大きさの任意性を解決するためΣjwij1とする。各ベクトルデータでの再構成誤差は、と表わせる。ここで、CjkTとした。この再構成誤差は、ラグランジュ乗数ηiを用いてとなる。極致を求めるため、wijについて偏微分し0とおくことで、以下の線形方程式を解く問題となる。以上の重みを求める計算については、deRidderらやPanらの研究で詳述されている。近傍による再構成の重みwijで表される、それぞれのベクトルデータにおける局所的な関係を、バイナリ符号に反映させるため、Weissらの最小化問題において、式の目的関数を以下のものに置き換える式E。さらに、新規データのバイナリ符容易に求められるよう、変換行列F∈Rn×dによる線形変換を考える式D。ここで、式の制約条件を満たすため、平均ベクトルx ̄で引いた。バイナリ符号の集合をHh1hmと表すと、式の目的関数は、以下のように表される。ここで、MTとした。さらに、式の制約条件は、となり、式6の目的関数の最小化は、と表わせる。これは、ラグランジュの未定乗数法から、となるので、Fで偏微分して0としておくことにより、以下の一般固有値問題へと帰着する。上記において、ベクトルデータhは、ベクトルデータxをバイナリ符号yのビット数であるdの次元に射影したものである。変換行列Fを式Aの変換行列rへ当てはめる。上記において、局所的な近傍構造を表す重みWijを、それぞれのベクトルデータの近傍から求める。しかし、注目しているベクトルデータに対して、近傍が密集して位置するものもあれば、遠く離れて位置するものもある。そこで、この分布の偏りによる影響を軽減するため、各ベクトルデータでの近傍の分布を表すスコアを定義する。近傍の分布を考慮した変換行列Fは、分布スコアからなる対角行列Ddiagd1dmにより、以下の最小化問題を解くことで得られる。これは、ラグランジュの未定乗数法から、と表わすことができる。さらに、Xがフルランク行列であれば、XTXは正則となることから、Xがフルランク行列ではない場合は、特異値分解を用いて、行列Xのランク数lと等しい次元の部分空間に射影する。上記の処理はいわゆるグラフラプラシアンの理論を用いて、重みWijを正規化したことを意味し、n次空間のベクトルデータxをd次空間への射影するとき、n次空間におけるベクトルデータxの分布の偏りの影響を軽減できる。よって、ベクトルデータ得られた変換行列Fはデータベースの特性をより正確に反映したものとなる。このようにして定められた変換行列を有するハッシュ関数を用いてハッシュ型近似最近傍検索を行なうシステム1を図1に示す。図1において、訓練データベース3、テストデータベース13、テストデータバイナリ符号データベース19はサーバのメモリ装置の所定の領域が対応される。訓練データベース3のデータはベクトル化処理部5において所定の方法でベクトル化される。ハッシュ関数特定部7は、ベクトル化された訓練データベース3のデータ第1のベクトルデータxの一部又は全部を用いて、既述の処理を行ない、変換ベクトルFを特定し、もって、第1のベクトルデータxをバイナリ符号化するハッシュ関数を特定する。テストデータベース13のデータは、ベクトル化処理部15において、ベクトル化処理部5と同一の方法でベクトル化される。バイナリ符号化部17は、ハッシュ関数特定部7で特定されたハッシュ関数を用いてベクトル化されたテストデータベースのデータの一部又は全部をバイナリ符号に変換し、テストデータバイナリ符号データベース19に保存する。クライアントPCが検索対象特定部20に対応し、この検索対象特定部20においてユーザが検索対象を特定する。特定された検索対象はベクトル化処理部21においてベクトル化処理される。このベクトル化処理の方法は、既述のベクトル化処理部5において、訓練データベース3のデータを第1のベクトルデータに変換したベクトル化処理法と同一である。このようにしてベクトル化された検索対象はバイナリ符号化部23において、ハッシュ関数特定部7で特定されたハッシュ関数を用いてバイナリ符号化される。比較部25は、検索対象のバイナリ符号をテストデータバイナリ符号データベース19に保存されているテストデータバイナリ符号と比較し、例えば、検索対象のバイナリ符号に対する距離が所定の閾値以内のものを、近い順に出力する。この発明の探索方法を評価するために、ベンチマークに20newsgroupsとCIFAR10を用いて、従来手法との比較実験を行った。従来手法には、LocalitySensitiveHashing、KernelizedLocalitySensitiveHashingを選択した。この内、アルゴリズム中に乱数生成を含むLSHとKLSHについては、5回実行して平均をとった。20newsgroupsは、Usenetnewsgroupから取得した18845件のニュースグループの文書からなる。各文書は、異なる20個のニュースグループのいずれかに分類され、11314件が訓練データセットとして、7531件がテストデータとして与えられる。各アルゴリズムの訓練には、訓練データセットからランダムに選択した5000件を用いた。実験では、前処理として単語のステミングとストップワードの除去を行ったのち、文書頻度の大きいほうから2000語を選択し、tfidfにより重み付けを行った文書ベクトルを作成した。本発明のパラメータは、事前実験により求めた最適値、近傍数k205、分布スコアのガウスカーネル幅λ40を用いた。図1は、20newsgroupsでビット数を8から64まで変化させた場合の、検索結果上位400件における適合率を表したグラフである。全てのビット数で、本件発明NSHが最も大きな適合率となっている。図3は、20newsgroupsで検索結果の上位件数を変化させた場合の、ビット数64における再現率を表したグラフである。全ての上位件数で、本件発明NSHが最も大きな再現率となっているのがわかる。図4は、20newsgroupsにおける再現率と適合率を表したグラフである。曲線が右上に伸びるほど検索精度が高いと言える。本件発明NSHが、従来手法と比較して、正確性網羅性ともに高いことがわかる。20newsgroupsは、20個のカテゴリに分類されているが、それらは、コンピュータの話題やスポーツの話題など、大きく分類することもできる。これらは高次元の文書ベクトル空間で、類似した話題のものが集まりながらも、粗密をなして複雑な構造を成していると予想する。ベクトルデータの非線形構造を推定し、分布の偏りを重みにより考慮する本件発明NSHは、従来手法と比較して、この複雑な文書ベクトル空間を正しくとらえられたと考える。CIFAR10は、飛行機や自動車、イヌなどの10種類のラベルが付与されクラス分けされた、60000個の32×32のカラー画像が含まれており、50000個が訓練データセットとして、10000個がテストデータセットとして与えられる。各アルゴリズムの訓練には、訓練データセットからランダムに選択した5000個を用いた。実験では、RGBごとに4×4領域6方向4スケールで3×4×4×6×41152次元のGIST特徴ベクトルを抽出し、それをバイナリ符号に変換した。本件発明NSHのパラメータは、事前実験により求めた最適値、近傍数k90、分布スコアのガウスカーネル幅λ05を用いた。図5は、CIFAR10でビット数を8から64まで変化させた場合の、検索結果上位1000件における適合率を表したグラフである。全てのビット数で、本件発明NSHが最も大きな適合率となっている。図6は、CIFAR10で検索結果の上位件数変化させた場合の、ビット数64における再現率を表したグラフである。全ての上位件数で、本件発明NSHが最も大きな再現率となっているのがわかる。図7は、CIFAR10における再現率と適合率を表したグラフである。本件発明NSHが、従来手法と比較して、正確性網羅性ともに高いことがわかる。CIFAR10には、飛行機や自動車などからなる乗り物画像と、イヌやシカなどからなる生物画像に、大きく分けられる。しかし、画像全体では特定の色が多く使用されている、背景が類似しているなどの要因で、特徴空間上では、乗り物画像と生物画像がはっきりと区別されることなく、粗密をなして分布していると予想する。分布の偏りを重みにより抑えつつ、ベクトルデータがなす非線形な構造を推定するNSHは、この特徴空間上の複雑なデータ関係を、従来手法と比較して正しくとらえられたと考える。図8は、CIFAR10で、SHとNSHによる32ビットのバイナリ符号を用いた、自動車の画像での検索結果上位20件を並べたものである。左上端の画像が検索質問画像であり、正解の画像は緑色の枠で、不正解の画像は赤色の枠で囲んだ。SHと比較して、本件発明NSHでは適合画像が多く、検索精度が高いことがわかる。本件発明NSHは、特徴空間上の局所的な近傍構造に基づいて、ベクトルデータがなす非線形構造をとらえた短いバイナリ符号を得る。文書データベンチマーク20newsgroupsと画像データベンチマークCIFAR10を用いた比較実験から、SpectralHashingなどの従来手法よりも高い検索精度を得られることが確認できた。実施例のハッシュ型近似近最傍探索装置100を図9に示す。この装置100は、検索サーバ101とクライアント端末200がネットワークN1を介して接続されている。任意の数のクライアント端末200をネットワークN1へ接続可能で、ネットワークN1はインターネット300へ開いていてもよい。検索サーバ101はデータ保存部110とデータ処理部120とを備える。データ保存部110は原データ取得保存部111を備える。この原データ取得保存部111は被検索対象となるデータを、インターネット300を介して外部のデータベースから取得し、保存する。外部のデータベースは特定のデータが整理保存された商用、または検索用のデータベースはもとより、法人若しくは個人が運営するホームページ、ブログ、ツイッター等も含まれるものとする。訓練データ抽出更新部113は、原データ取得保存部111に保存されたデータから無作為にデータを抽出し、訓練データとする。抽出するデータ数は特に限定されるものではないが、既述の試験例に準じて5000個程度とすることが好ましい。なお、この訓練データは周期的に、若しくは任意のタイミングで更新することが好ましい。ベクトル化処理部121及びハッシュ関数特定部123の動作は、図1のベクトル化処理部5及びハッシュ関数特定部7と同じである。即ち、訓練データ抽出更新部121で抽出されたデータを特徴量次元削減法等の汎用的な手法第1のベクトル化方法でベクトル化処理し、ハッシュ関数特定部123において、本発明の手法に従いハッシュ関数第1のハッシュ関数を特定する。ベクトル化処理部121は原データ取得保存部111のデータの全部をまたは所定のルールで選択されたその一部を訓練データと同様にベクトル化処理する。ベクトル化処理され原データは、バイナリ符号化部125においてバイナリ符号化データに次元削減される前処理130。このとき、ハッシュ関数特定部123において特定されたハッシュ関数が利用される。バイナリ符号化されたデータはバイナリ符号化データ保存部115に保存される。クライアント端末200において、検索対象となるデータが入力部210で指定される。指定されたデータはベクトル化処理部221において、検索サーバ101のベクトル化処理部121と同一の方法によりベクトル化される。バイナリ符号化部223には、検索サーバ101のハッシュ関数特定部123で特定されたハッシュ関数が提供され、ベクトル化された検索対象データをバイナリ符号化する。このようにしてバイナリ符号化された検索対象データは検索サーバ101の比較部127へ送られる。比較部127はバイナリ符号化された検索対象データとバイナリ符号化データ保存部115に保存されているバイナリ符号化された原データとを比較し、所定のルールに従い近似するデータを抽出する。比較部127で抽出されたデータはクライアント端末200の出力部230へ送られ、ここで出力される。なお、出力部230はバイナリ符号化されたデータをデコード逆ハッシュ関数処理、逆ベクトル処理し、原データの状態で表示できる。この比較部を端末側に配置することができる。また、比較部を、検索サーバ及び端末と独立して設置することもできる。