JP6640896B2 - データ処理装置、データ処理方法およびプログラム - Google Patents

Description

本発明の実施形態は、データ処理装置、データ処理方法およびプログラムに関する。

ビッグデータ時代の到来に伴い、例えばパタン認識などで事例として利用される特徴ベクトルを大量に保有する必要性が増加している。これに伴い、特徴ベクトルを保有するためのメモリやＨＤＤなどのハードウェアコストが増大している。この問題の解決策の一つとして、直積量子化により特徴ベクトルのメモリサイズを削減する方法が知られている。直積量子化は、特徴ベクトルを複数のサブベクトルに分割し、コードブックを参照して、各サブベクトルをクラスタの代表ベクトルのインデックスに置き換えることにより、特徴ベクトルを圧縮コードに変換する技術である。コードブックは、保有すべき特徴ベクトル集合をサブベクトルごとにクラスタリングし、各クラスタの代表ベクトルをインデックスと対応付けることによって生成されるルックアップテーブルである。

特徴ベクトルを複数のサブベクトルに分割する際、従来は、個々のサブベクトルの次元数が同一となるように特徴ベクトルを均等に分割するのが一般的である。しかし、この方法では異なるサブベクトル間で分散の度合いに大きな偏りが生じ、コードブックを生成する際にサブベクトルによってはクラスタ数が過剰あるいは過小となる場合がある。そして、このように生成されたコードブックを用いて特徴ベクトルの直積量子化を行うと、量子化効率が低下する懸念がある。

特許第５６３７９３９号公報 特許第２６４１２０９号公報

H．J´egou，M．Douze，and C．Schmid，"Product quantization for nearest neighbor search," IEEE Trans．On PAMI，vol.33，no.1，pp.117−128，2011．

本発明が解決しようとする課題は、特徴ベクトルを効率よく量子化できるデータ処理装置、データ処理方法およびプログラムを提供することである。

実施形態のデータ処理装置は、サブベクトル群生成部と、コードブック生成部と、変換部と、を備える。サブベクトル群生成部は、Ｎ個のＤ次元特徴ベクトルからなる特徴ベクトル集合から、Ｍ個（ただし、Ｍ＜Ｄ）のサブベクトル群を生成する。前記Ｍ個のサブベクトル群の各々は、前記Ｎ個のＤ次元特徴ベクトルの各々から得られたＮ個の次元可変サブベクトルからなる。前記Ｎ個の次元可変サブベクトルの各々は、前記Ｄ次元特徴ベクトルから抽出された１以上の次元の値を要素とする。前記Ｍ個のサブベクトル群のうちの少なくとも１つのサブベクトル群における前記次元可変サブベクトルの要素の数が他のサブベクトル群における前記次元可変サブベクトルの要素の数と異なる。コードブック生成部は、前記Ｍ個のサブベクトル群ごとに、前記Ｎ個の次元可変サブベクトルをクラスタリングして、各クラスタの代表ベクトルをインデックスと対応付けたコードブックを生成する。変換部は、前記コードブックを用いた直積量子化により、前記Ｎ個のＤ次元特徴ベクトルの各々を、Ｍ個のインデックスの組み合わせからなる圧縮コードに変換する。前記サブベクトル群生成部は、前記Ｍ個のサブベクトル群同士で前記次元可変サブベクトルの分散の度合いが近くなるように、前記特徴ベクトル集合から前記Ｍ個のサブベクトル群を生成する。

図１は、特徴ベクトル集合の一例を示す図である。 図２は、特徴ベクトル集合からサブベクトル群を生成する従来の方法を説明する図である。 図３は、コードブックを生成する従来の方法を説明する図である。 図４は、コードブックを参照して特徴ベクトルを圧縮コードに変換する方法を説明する図である。 図５は、コードブックを参照して特徴ベクトルを圧縮コードに変換する方法を説明する図である。 図６は、第１実施例に係るデータ処理装置の機能的な構成例を示すブロック図である。 図７は、特徴ベクトル集合からサブベクトル群を生成する様子を示す図である。 図８は、サブベクトル群生成部による処理の具体例を示すフローチャートである。 図９は、コードブックを生成する様子を示す図である。 図１０は、第２実施例に係るデータ処理装置の機能的な構成例を示すブロック図である。 図１１は、クラスタ数上限値の探索方法を説明する図である。 図１２は、第３実施例に係るデータ処理装置の機能的な構成例を示すブロック図である。 図１３は、差分ルックアップテーブルの一例を示す図である。 図１４は、コードブック更新部による処理の概要を説明する図である。 図１５は、データ処理装置のハードウェア構成例を示すブロック図である。

以下、実施形態のデータ処理装置、データ処理方法およびプログラムを、図面を参照して詳細に説明する。本実施形態は、直積量子化により特徴ベクトルを圧縮コードに変換する技術を対象とし、特に、サブベクトルの生成方法とサブベクトル群のクラスタリング方法を改良することにより、特徴ベクトルを効率よく量子化できるようにしたものである。

＜直積量子化の概要＞
まず、本実施形態の具体的な説明に先立ち、従来の一般的な方法による直積量子化の概要を説明する。直積量子化により特徴ベクトルを圧縮コードに変換する技術は、保有すべき特徴ベクトル集合からコードブックを生成するフェーズと、このコードブックを用いて特徴ベクトル集合に含まれる各特徴ベクトルを圧縮コードに変換するフェーズとからなる。なお、以下の説明においては、保有すべき特徴ベクトル集合に含まれる特徴ベクトルの数をＮ、各特徴ベクトルの次元数をＤ、特徴ベクトルをサブベクトルに分割する分割数（特徴ベクトルから生成されるサブベクトルの数）をＭとする。

まず、特徴ベクトル集合からコードブックを生成するフェーズについて説明する。特徴ベクトル集合の一例を図１に示す。図１に示すように、特徴ベクトル集合２００は、Ｎ個のＤ次元特徴ベクトル（以下、単に「特徴ベクトル」と呼ぶ）２１０からなる。図１に示す例では、直積量子化の概要を分かり易く説明するために各特徴ベクトル２１０の次元数Ｄを６としているが、実際の特徴ベクトル２１０の次元数Ｄは、より大きな値であることが一般的である。

特徴ベクトル集合２００からコードブックを生成する際は、まず、例えば図２に示すように、特徴ベクトル集合２００に含まれる各特徴ベクトル２１０をＭ個のサブベクトル２２０に分割して、Ｍ個のサブベクトル群２３０を生成する。図２に示す例では、特徴ベクトル２１０の分割数（サブベクトル群２３０の数）Ｍを３としている。

特徴ベクトル２１０からＭ個のサブベクトル２２０への分割は、従来の一般的な方法によると、サブベクトル２２０同士の次元数が同一となる均等分割である。図２の例では、６次元（Ｄ＝６）の特徴ベクトル２１０を３分割（Ｍ＝３）するため、各サブベクトル２２０の次元数は２となる。Ｍ個のサブベクトル群２３０の各々は、特徴ベクトル集合２００に含まれるＮ個の特徴ベクトル２１０の各々から得られたＮ個のサブベクトル２２０からなり、１つのサブベクトル群２３０に含まれるＮ個のサブベクトル２２０は、Ｎ個の特徴ベクトル２１０から各々抽出された共通の次元を要素とする。例えば、１番目の特徴ベクトル２１０の第１次元と第２次元を要素とするサブベクトル２２０、２番目の特徴ベクトル２１０の第１次元と第２次元を要素とするサブベクトル２２０、・・・、Ｎ番目の特徴ベクトル２１０の第１次元と第２次元を要素とするサブベクトル２２０が１つのサブベクトル群２３０を構成する。このようなサブベクトル群２３０が、特徴ベクトル２１０の分割数Ｍ分生成される。

次に、Ｍ個のサブベクトル群２３０の各々に対してＫ−ｍｅａｎｓクラスタリングを行い、各サブベクトル群２３０に含まれるＮ個のサブベクトル２２０をＫ個のクラスタにクラスタリングする。そして、サブベクトル群２３０ごとに、Ｋ個のクラスタの代表ベクトルとインデックスとを対応付けたコードブックを生成する。Ｋの値は、特徴ベクトル集合２００に含まれる特徴ベクトル２１０の数Ｎよりも十分に小さい値である。ここでは、コードブックにおけるインデックスを８ビットで表現することを想定し、Ｋの値を２^８＝２５６とする。

図２の例のように特徴ベクトル２１０の分割数Ｍ＝３に応じて特徴ベクトル集合２００から３個のサブベクトル群２３０を生成した場合は、図３に示すように、３個のサブベクトル群２３０の各々に対してＫ−ｍｅａｎｓクラスタリング（Ｋ＝２５６）を行うことで、３個のサブベクトル群２３０の各々が、それぞれ２５６個のクラスタにクラスタリングされる。そして、各クラスタの代表ベクトルが、そのクラスタの代表ベクトルを指し示す値であるインデックス（ＩＤ：１〜２５６）と対応付けられることにより、コードブック２４０が生成される。クラスタの代表ベクトルは、例えば、そのクラスタのセントロイドである。

次に、コードブック２４０を用いて特徴ベクトル集合２００に含まれる各特徴ベクトル２１０を圧縮コードに変換するフェーズについて説明する。特徴ベクトル集合２００に含まれる各特徴ベクトル２１０を圧縮コードに変換する際は、まず、図４に示すように、特徴ベクトル集合２００から特徴ベクトル２１０を１つ取り出して、この特徴ベクトル２１０を、コードブック２４０の生成時と同じ方法でＭ個（図４の例では３個）のサブベクトル２２０に分割する。そして、Ｍ個のサブベクトル２２０の各々について、上述のように生成されたコードブック２４０を参照して、サブベクトル２２０に最も近い代表ベクトルを特定し、その代表ベクトルに対応するインデックスを取得する。そして、取得したＭ個のインデックスを、特徴ベクトル２１０における各サブベクトル２２０の順序に従って配置し、圧縮コード２５０を生成する。このようにして、Ｄ次元の特徴ベクトル２１０が長さＭの圧縮コード２５０に変換される。

以上の処理を、特徴ベクトル集合２００に含まれるＮ個の特徴ベクトル２１０の全てに対して実施することにより、図５に示すように、特徴ベクトル集合２００がＮ個の圧縮コード２５０からなる圧縮コード集合２６０に変換される。特徴ベクトル集合２００を圧縮コード集合２６０に変換して保存することにより、メモリサイズの削減を図ることができる。特徴ベクトル集合２００を圧縮コード集合２６０に変換することによるデータの圧縮率は、特徴ベクトル２１０の分割数Ｍが小さいほど、また、サブベクトル群２３０に対するＫ−ｍｅａｎｓクラスタリングのクラスタ数Ｋの値が小さいほど高くなる。一方、圧縮コード２５０による特徴ベクトル２１０の表現力は、特徴ベクトル２１０の分割数Ｍが大きいほど、また、サブベクトル群２３０に対するＫ−ｍｅａｎｓクラスタリングのクラスタ数Ｋの値が大きいほど高くなる。このため、特徴ベクトル２１０の分割数ＭやＫ−ｍｅａｎｓクラスタリングのクラスタ数Ｋの値は、アプリケーションで要求される表現力を維持しつつ圧縮率をできるだけ高められるように、つまり、良好な量子化効率が得られるように決定される。

＜実施形態の概要＞
以上説明した従来の一般的な直積量子化の方法では、特徴ベクトル２１０の分割数Ｍ（つまりサブベクトル２２０の次元数）やＫ−ｍｅａｎｓクラスタリングのクラスタ数Ｋの値が固定であるため、上述のコードブック２４０を生成する際に、サブベクトル群２３０によっては過剰あるいは過小なクラスタが生成されてしまう場合がある。そして、このように生成されたコードブック２４０を用いて特徴ベクトル２１０の直積量子化を行うと、量子化効率が低下する懸念がある。

そこで本実施形態では、直積量子化において、予め量子化レベルのパタンを決めることなく、サブベクトル群２３０ごとに最適な量子化レベル（クラスタ数）を自動決定し、量子化効率を改善する。具体的には、Ｘ−ｍｅａｎｓクラスタリングの手法を用いて、サブベクトル群２３０ごとの量子化レベルを自動決定する。Ｘ−ｍｅａｎｓクラスタリングとは、Ｋ−ｍｅａｎｓクラスタリングを改良したクラスタリング手法であり、最適なクラスタ数を自動決定できる。
（参考文献）Dan Pelleg，Andrew Moore，“X-means：Extending K-means with Efficient Estimation of the Number of Clusters” School of Computer Science，Carnegie Mellon University，Pittsburgh，PA 15213 USA．

ただし、Ｘ−ｍｅａｎｓクラスタリングには、クラスタリング対象のサブベクトル群２３０におけるサブベクトル２２０の分散が大きいと、自動決定されるクラスタ数が多くなり、クラスタリングの所要時間が莫大になるという問題がある。サブベクトル群２３０におけるサブベクトル２２０の分散は、サブベクトル２２０の次元数が多いほど増加する。この問題を解決するため、本実施形態では、サブベクトル２２０の生成方法を改良する。

従来は、上述のように、全てのサブベクトル２２０の次元数が同じになるように特徴ベクトル２１０を均等に分割していた。この場合、サブベクトル群２３０間においてサブベクトル２２０の分散の度合いにばらつきが生じるため、サブベクトル２２０の分散が極端に大きなサブベクトル群２３０と、そうでないサブベクトル群２３０とが生成される可能性がある。

これを防ぐため、本実施形態ではサブベクトル２２０の次元を可変にし（以下では、このサブベクトル２２０を「次元可変サブベクトル２２０」と表記する）、さらに、各サブベクトル群２３０における次元可変サブベクトル２２０の分散が等程度になるように、特徴ベクトル集合２００に含まれる特徴ベクトル２１０の次元選択を行うことで、Ｍ個のサブベクトル群２３０を生成する。そして、このＭ個のサブベクトル群２３０を用いてコードブック２４０を生成し、直積量子化により特徴ベクトル２１０を圧縮コード２５０に変換する。

以下では、以上のような本実施形態の概念を実現する具体的な実施例について説明する。なお、以下の説明において、同様の機能を持つ構成要素については同一の符号を付して、重複した説明を適宜省略する。

＜第１実施例＞
図６は、第１実施例に係るデータ処理装置１０Ａの機能的な構成例を示すブロック図である。本実施例のデータ処理装置１０Ａは、図６に示すように、サブベクトル群生成部１１と、コードブック生成部１２と、変換部１３とを備える。

サブベクトル群生成部１１は、Ｎ個の特徴ベクトル２１０からなる特徴ベクトル集合２００から、Ｍ個のサブベクトル群２３０を生成する。Ｍ個のサブベクトル群２３０の各々は、Ｎ個の特徴ベクトル２１０の各々から得られたＮ個の次元可変サブベクトル２２０からなる。Ｎ個の次元可変サブベクトル２２０の各々は、特徴ベクトル２１０から抽出された１以上の次元の値を要素とする。サブベクトル群生成部１１が生成するサブベクトル群２３０の数Ｍは、特徴ベクトル２１０の次元数Ｄよりも小さい値であるが、従来のように固定の値ではなく適応的に定まる可変の値である。

図７は、サブベクトル群生成部１１が特徴ベクトル集合２００からＭ個のサブベクトル群２３０を生成する様子を示す図であり、図１に例示した特徴ベクトル集合２００から３個のサブベクトル群２３０を生成する様子を示している。サブベクトル群生成部１１は、従来のように特徴ベクトル集合２００に含まれる各特徴ベクトル２１０を均等分割するのではなく、図７に示すように、特徴ベクトル集合２００に含まれる各特徴ベクトル２１０の次元選択を行うことで、Ｍ個（図７の例ではＭ＝３）のサブベクトル群２３０を生成する。このとき、サブベクトル群生成部１１は、Ｍ個のサブベクトル群２３０同士で次元可変サブベクトル２２０の分散の度合いが近くなるように次元選択を行って、特徴ベクトル集合２００からＭ個のサブベクトル群２３０を生成する。このため、異なるサブベクトル群２３０間で、次元可変サブベクトル２２０の次元数（要素の数）が同一にはならない。つまり、サブベクトル群生成部１１が生成するＭ個のサブベクトル群２３０のうちの少なくとも１つのサブベクトル群２３０における次元可変サブベクトル２２０の要素の数が、他のサブベクトル群２３０における次元可変サブベクトル２２０の要素の数と異なる。

図８は、サブベクトル群生成部１１による処理の具体例を示すフローチャートである。サブベクトル群生成部１１は、例えば図８のフローチャートで示す処理を実施することにより、次元可変サブベクトル２２０の分散の度合いが同程度のＭ個のサブベクトル群２３０を生成することができる。

サブベクトル群生成部１１は、まず、特徴ベクトル集合２００とクラスタ数上限値Ｔを取得する（ステップＳ１０１）。クラスタ数上限値Ｔは、ユーザにより設定される超パラメタである。

次に、サブベクトル群生成部１１は、特徴ベクトル集合２００に含まれるＮ個の特徴ベクトル２１０について、各次元でＸ−ｍｅａｎｓクラスタリングを行い、次元ごとに最適クラスタ数Ｃを算出する（ステップＳ１０２）。

次に、サブベクトル群生成部１１は、最適クラスタ数Ｃが小さい順に、特徴ベクトル２１０から最適クラスタ数Ｃが同じ次元を抽出してグループ化する（ステップＳ１０３）。そして、グループに属する次元の数Ｇとそのグループに属する次元の最適クラスタ数Ｃとからサブベクトル群２３０の最適クラスタ数Ｇ^Ｃを算出し、Ｇ^Ｃがクラスタ数上限値Ｔ以下であるか否かを判定する（ステップＳ１０４）。

ここで、Ｇ^Ｃがクラスタ数上限値Ｔ以下であれば（ステップＳ１０４：Ｙｅｓ）、サブベクトル群生成部１１は、そのグループ（特徴ベクトル２１０から抽出された次元の組み合わせ）を次元可変サブベクトル２２０とし、特徴ベクトル集さ２００に含まれるＮ個の特徴ベクトル２１０に対応するＮ個の次元可変サブベクトル２２０からなるサブベクトル群２３０を出力する（ステップＳ１０５）。

一方、Ｇ^Ｃがクラスタ数上限値Ｔを超えている場合は（ステップＳ１０４：Ｎｏ）、サブベクトル群生成部１１は、そのグループを分割し（ステップＳ１０６）、分割されたグループに属する次元の数Ｇが１になったか否かを判定する（ステップＳ１０７）。そして、分割されたグループに属する次元の数Ｇが１でなければ（ステップＳ１０７：Ｎｏ）、ステップＳ１０４に戻って以降の処理を繰り返す。つまり、サブベクトル群生成部１１は、サブベクトル群２３０の最適クラスタ数Ｇ^Ｃがクラスタ数上限値Ｔを超えているグループについては、Ｇ^Ｃがクラスタ数上限値Ｔ以下になるまで、または、グループに属する次元の数Ｇが１になるまで、そのグループを分割する。そして、サブベクトル群２３０の最適クラスタ数Ｇ^Ｃがクラスタ数上限値Ｔ以下になる（ステップＳ１０４：Ｙｅｓ）、または、グループに属する次元の数Ｇが１になると（ステップＳ１０７：Ｙｅｓ）、ステップＳ１０５に進んでサブベクトル群２３０を出力する。

その後、サブベクトル群生成部１１は、特徴ベクトル２１０から全ての次元を抽出したか否かを判定し（ステップＳ１０８）、特徴ベクトル２１０から抽出していない次元があれば（ステップＳ１０８：Ｎｏ）、ステップＳ１０３に戻って以降の処理を繰り返す。そして、特徴ベクトル２１０から全ての次元を抽出してステップＳ１０５の処理が完了すると、図８のフローチャートで示す一連の処理を終了する。

コードブック生成部１２は、サブベクトル群生成部１１により生成されたＭ個のサブベクトル群２３０ごとに、Ｎ個の次元可変サブベクトル２２０をクラスタリングして、各クラスタの代表ベクトルをインデックスと対応付けたコードブック２４０を生成する。

例えば、コードブック生成部１２は、Ｍ個のサブベクトル群２３０ごとに、サブベクトル群２３０の生成時に推定される最適クラスタ数Ｇ^ＣをＫとするＫ−ｍｅａｎｓクラスタリングを行うことで、コードブック２４０を生成する。あるいは、コードブック生成部１２は、Ｍ個のサブベクトル群２３０ごとにＸ−ｍｅａｎｓクラスタリングを行うことで、コードブック２４０を生成するようにしてもよい。

図９は、コードブック生成部１２がコードブック２４０を生成する様子を示す図であり、図７に例示した３個のサブベクトル群２３０からコードブック２４０を生成する様子を示している。コードブック生成部１２は、上述のように、サブベクトル群２３０ごとに、そのサブベクトル群２３０の最適クラスタ数に基づいて次元可変サブベクトル２２０をクラスタリングする。このため、コードブック生成部１２により生成されるコードブック２４０は、図９に示すように、各サブベクトル群２３０に対応するクラスタ数が同一にはならない。つまり、Ｍ個のサブベクトル群２３０のうちの少なくとも１つのサブベクトル群２３０に対応するクラスタ数が他のサブベクトル群２３０に対応するクラスタ数とは異なるコードブック２４０が生成される。

変換部１３は、コードブック生成部１２により生成されたコードブック２４０を用いた直積量子化により、特徴ベクトル集合２００に含まれるＮ個の特徴ベクトル２１０の各々を圧縮コード２５０に変換して、Ｎ個の圧縮コード２５０からなる圧縮コード集合２６０を出力する。コードブック生成部１２が生成する上述のコードブック２４０を用いた直積量子化により、特徴ベクトル集合２００に含まれるＮ個の特徴ベクトル２１０を効率よく量子化することができる。なお、変換部１３が特徴ベクトル２１０を圧縮コード２５０に変換する方法は、使用するコードブック２４０が異なることを除いて、従来の一般的な方法と同様であるため、詳細な説明は省略する。

以上のように構成される本実施例のデータ処理装置１０によれば、実利用可能な計算時間でコードブック２４０を生成することができ、このコードブック２４０を用いて特徴ベクトル２１０を直積量子化することで、特徴ベクトル２１０の量子化効率を改善することができる。また、特徴ベクトル２１０の量子化効率が改善されることにより、大量の特徴ベクトル２１０を少ないメモリで保有することが可能となる。

＜第２実施例＞
次に、第２実施例について説明する。本実施例は、上述の第１実施例に対し、量子化レベルを決定するパラメタとなるクラスタ数上限値Ｔを調整する機能を付加したものである。その他の機能は上述の第１実施例と同様であるため、以下では、本実施例に特有の機能についてのみ説明する。

実際の運用を考慮すると、特徴ベクトル集合２００を圧縮コード集合２６０に変換する前後における検索精度の変動率をどこまで許容するか、あるいは、特徴ベクトル集合２００を圧縮コード集合２６０に変換することによる圧縮率をどこまで高めるかといった目標が必要となる。このため、検索精度の変動率または圧縮率に対する目標値を超パラメタとして設定することが求められる。

ここで検索精度は、クエリを使って特徴ベクトル２１０を検索した回数をＸ、検索結果が正解であった数をＹとしたときに、Ｙ／Ｘで表される。また、検索結果の変動率は、特徴ベクトル集合２００を圧縮コード集合２６０に変換する前の検索精度をＺｂ、特徴ベクトル集合２００を圧縮コード集合２６０に変換した後の検索精度をＺａとしたときに、１−Ｚａ／Ｚｂで表される。また、圧縮率は、特徴ベクトル集合２００のデータサイズをｘ、圧縮コード集合２６０とコードブック２４０とを合せたデータサイズをｙとしたときに、ｙ／ｘで表される。

検索精度の変動率や圧縮率は、直積量子化の量子化レベルに応じて変化する。そこで本実施例では、検索精度の変動率または圧縮率が超パラメタとして設定された目標値に近づくように、量子化レベルを決定するパラメタとなるクラスタ数上限値Ｔを調整する。ただし、全てのクラスタ数上限を探索すると計算量が膨大になるため、後述の方法により探索を効率化する。

図１０は、第２実施例に係るデータ処理装置１０Ｂの機能的な構成例を示すブロック図である。本実施例のデータ処理装置１０Ｂは、図１０に示すように、上述の第１実施例のデータ処理装置１０Ａ（図６参照）に対し、パラメタ調整部１４を追加した構成である。また、本実施例では、超パラメタとして、２つのクラスタ数上限値Ｔａ，Ｔｂが設定されるのに加え、検索精度の変動率または圧縮率に対する目標値と、探索の繰り返し回数とが設定される。

パラメタ調整部１４は、上述の検索精度の変動率または圧縮率が、超パラメタとして設定された目標値に近づくように、後述の方法により２つのクラスタ数上限値Ｔａ，Ｔｂのいずれか一方を変更する操作を、超パラメタとして設定された繰り返し回数だけ繰り返すことにより、クラスタ数上限値Ｔを探索的に決定する。

本実施例のデータ処理装置１０Ｂは、超パラメタとして設定された２つのクラスタ数上限値Ｔａ，Ｔｂを各々用いて、第１実施例と同様の直積量子化による特徴ベクトル集合２００の圧縮を個別に行う。そして、上述の検索精度の変動率または圧縮率を、クラスタ数上限値Ｔａ，Ｔｂごとに計算する。このときの計算結果は、図１１に示す３つのパタンに分類できる。パラメタ調整部１４は、これら３つのパタンに応じて、クラスタ数上限値Ｔａ，Ｔｂのいずれか一方を以下のように変更し、最適なクラスタ数上限値Ｔを探索する。図１１は、クラスタ数上限値Ｔの探索方法を説明する図であり、圧縮率を目標値に近づけるように最適なクラスタ数上限値Ｔを探索する場合の例を示している。

図１１（ａ）は、クラスタ数上限値Ｔａを用いた場合の圧縮率とクラスタ数上限値Ｔｂを用いた場合の圧縮率との双方が目標値よりも高い場合を示している。この場合は、圧縮率が低くなるようにクラスタ数上限値Ｔを調整することが望ましい。そこで、パラメタ調整部１４は、圧縮率が目標値に近い方のクラスタ数上限値Ｔ（図１１（ａ）の例ではクラスタ数上限値Ｔａ）を固定し、もう一方のクラスタ数上限値Ｔ（図１１（ａ）の例ではクラスタ数上限値Ｔｂ）を変更する。このとき、図１１（ａ）の例のように、固定するクラスタ数上限値Ｔを用いたときの圧縮率と、変更するクラスタ数上限値を用いたときの圧縮率との傾きが正であれば、変更するクラスタ数上限値Ｔを固定するクラスタ数上限値Ｔよりも小さい値に変更する。一方、この傾きが負であれば、変更するクラスタ数上限値Ｔを固定するクラスタ数上限値Ｔよりも大きい値に変更する。

図１１（ｂ）は、クラスタ数上限値Ｔａを用いた場合の圧縮率とクラスタ数上限値Ｔｂを用いた場合の圧縮率との双方が目標値よりも低い場合を示している。この場合は、圧縮率が高くなるようにクラスタ数上限値Ｔを調整することが望ましい。そこで、パラメタ調整部１４は、圧縮率が目標値に近い方のクラスタ数上限値Ｔ（図１１（ｂ）の例ではクラスタ数上限値Ｔｂ）を固定し、もう一方のクラスタ数上限値Ｔ（図１１（ｂ）の例ではクラスタ数上限値Ｔａ）を、図１１（ａ）の例とは増減の方向が逆になるように変更する。すなわち、図１１（ｂ）の例のように、固定するクラスタ数上限値Ｔを用いたときの圧縮率と、変更するクラスタ数上限値を用いたときの圧縮率との傾きが正であれば、変更するクラスタ数上限値Ｔを固定するクラスタ数上限値Ｔよりも大きい値に変更する。一方、この傾きが負であれば、変更するクラスタ数上限値Ｔを固定するクラスタ数上限値Ｔよりも小さい値に変更する。

図１１（ｃ）は、クラスタ数上限値Ｔａを用いた場合の圧縮率とクラスタ数上限値Ｔｂを用いた場合の圧縮率との一方が目標値よりも高く、他方が目標値よりも低い場合を示している。この場合は、２つのクラスタ数上限値Ｔａ，Ｔｂの間に最適なクラスタ数上限値Ｔが存在する可能性が高い。そこで、パラメタ調整部１４は、圧縮率が目標値に近い方のクラスタ数上限値Ｔ（図１１（ｃ）の例ではクラスタ数上限値Ｔａ）を固定し、もう一方のクラスタ数上限値Ｔ（図１１（ｃ）の例ではクラスタ数上限値Ｔｂ）を、２つのクラスタ数上限値Ｔａ，Ｔｂの中間の値に変更する。

図１１（ａ）、図１１（ｂ）および図１１（ｃ）に示す３つのパタンに対応した処理は、検索精度の変動率を目標値にするときも同様である。すなわち、クラスタ数上限値Ｔａを用いた場合の検索精度の変動率とクラスタ数上限値Ｔｂを用いた場合の検索精度の変動率との双方が目標値よりも高い場合は、図１１（ａ）の例と同様にクラスタ数上限値Ｔａ，Ｔｂのいずれか一方を変更し、クラスタ数上限値Ｔａを用いた場合の検索精度の変動率とクラスタ数上限値Ｔｂを用いた場合の検索精度の変動率との双方が目標値よりも低い場合は、図１１（ｂ）の例と同様にクラスタ数上限値Ｔａ，Ｔｂのいずれか一方を変更し、クラスタ数上限値Ｔａを用いた場合の検索精度の変動率とクラスタ数上限値Ｔｂを用いた場合の検索精度の変動率との一方が目標値よりも高く、他方が目標値よりも低い場合は、図１１（ｃ）の例と同様にクラスタ数上限値Ｔａ，Ｔｂのいずれか一方を変更すればよい。

本実施例のデータ処理装置１０Ｂは、パラメタ調整部１４がクラスタ数上限値Ｔａ，Ｔｂのいずれか一方を変更するたびに、変更されたクラスタ数上限値Ｔを用いて第１実施例と同様の直積量子化による特徴ベクトル集合２００の圧縮を行い、上述の検索精度の変動率または圧縮率を計算する。そして、超パラメタとして設定された繰り返し回数に達するまで、上述の処理を繰り返すことで、最適なクラスタ数上限値Ｔを効率的に絞り込むことができる。

以上のように、本実施例では、直積量子化による検索精度の変動率または圧縮率が設定された目標値に近づくようにクラスタ数上限値Ｔを探索的に決定するようにしているので、上述の第１実施例と同様に特徴ベクトル２１０の量子化効率を改善できることに加え、目的に合せたパラメタ調整を容易に行うことができるといった効果が得られる。

＜第３実施例＞
次に、第３実施例について説明する。本実施例は、上述の第２実施例に対し、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加された場合に、コードブック２４０の更新が必要か否かを判定し、更新が必要と判定した場合のみコードブック２４０を更新する機能を付加したものである。その他の機能は上述の第１実施例と同様であるため、以下では、本実施例に特有の機能についてのみ説明する。

実際の運用では、保有すべき特徴ベクトル集合２００に新たな特徴ベクトル２１０を随時追加することが求められる場合がある。ここで、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加されるたびにコードブック２４０を更新すると、コードブック２４０の更新に多くの計算時間を要することとなり効率的でない。そこで本実施例では、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加された場合に、コードブック２４０の更新が必要か否かを判定する。そして、更新が必要と判定した場合に、コードブック２４０の必要な部分だけ更新する。

コードブック２４０の更新が必要な場合とは、新たな特徴ベクトル２１０から生成される次元可変サブベクトル２２０のうちの少なくとも１つが、その次元可変サブベクトル２２０に対応するクラスタの分散の範囲に収まらない場合、つまり、新たな特徴ベクトル２１０の追加によって、少なくともいずれかのサブベクトル群２３０のいずれかのクラスタの分散の範囲が拡大する場合である。本実施例では、このような場合に、分散の範囲が拡大するクラスタを更新の対象とし、コードブック２４０の当該クラスタの代表ベクトルを更新する。

図１２は、第３実施例に係るデータ処理装置１０Ｃの機能的な構成例を示すブロック図である。本実施例のデータ処理装置１０Ｃは、図１２に示すように、上述の第１実施例のデータ処理装置１０Ａ（図６参照）に対し、差分ルックアップテーブル生成部１５と、コードブック更新部１６とを追加した構成である。

差分ルックアップテーブル生成部１５は、差分ルックアップテーブル２８０を生成する。差分ルックアップテーブル２８は、元の特徴ベクトル集合２００から生成されたＭ個のサブベクトル群２３０の各々について、クラスタごとの次元可変サブベクトル２２０の分散の範囲を示す値をそのクラスタのインデックスと対応付けたルックアップテーブルである。クラスタにおける次元可変サブベクトル２２０の分散の範囲は、そのクラスタの代表ベクトルとそのクラスタに属する次元可変サブベクトル２２０との間の距離の最大値で表すことができる。したがって、クラスタごとにそのクラスタの代表ベクトルと次元可変サブベクトル２２０との間の距離の最大値をインデックスに対応付けて格納することで、差分ルックアップテーブル２８０を生成することができる。

図１３は、差分ルックアップテーブル２８０の一例を示す図である。差分ルックアップテーブル２８０は、図１３に示すように、上述のコードブック２４０と同様の形式のルックアップテーブルであるが、サブベクトル群２３０ごとのクラスタのインデックスに対応付けて格納される要素値が、そのクラスタの代表ベクトルではなく、そのクラスタの代表ベクトルと次元可変サブベクトル２２０との間の距離の最大値（そのクラスタの分散の範囲を示す値）となっている。

差分ルックアップテーブル２８０は、例えば、コードブック２４０の生成時にコードブック２４０と併せて生成することができる。すなわち、サブベクトル群２３０ごとに次元可変サブベクトル２２０をクラスタリングして各クラスタの代表ベクトルを求めた後、それぞれのクラスタごとに、そのクラスタの代表ベクトルとそのクラスタに属するそれぞれの次元可変サブベクトル２２０と間の距離を求める。そして、求めた距離の最大値をそのクラスタのインデックスと対応付けることにより、図１３に示したような差分ルックアップテーブル２８０を生成することができる。

コードブック更新部１６は、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加された場合に、新たな特徴ベクトル２１０から上述の第１実施例と同様の手法によりＮ個の次元可変サブベクトル２２０を生成する。そして、これらＮ個の次元可変サブベクトル２２０の各々について、その次元可変サブベクトル２２０に対応するサブベクトル群２３０（元の特徴ベクトル集合２００から生成されたＭ個のサブベクトル群２３０のうちの１つ）のクラスタのうち、その次元可変サブベクトル２２０に最も近い代表ベクトルを持つクラスタを求める。そして、コードブック更新部１６は、上述の差分ルックアップテーブル２８０を参照し、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０とクラスタの代表ベクトルとの間の距離を、そのクラスタのインデックスに対応付けられて差分ルックアップテーブル２８０に格納された要素値と比較することにより、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０がクラスタの分散の範囲に収まるか否かを判定する。すなわち、コードブック更新部１６は、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０とクラスタの代表ベクトルとの間の距離が差分ルックアップテーブル２８０に格納された要素値以下であれば、分散の範囲に収まると判定し、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０とクラスタの代表ベクトルとの間の距離が差分ルックアップテーブル２８０に格納された要素値よりも大きければ、分散の範囲に収まらないと判定する。

コードブック更新部１６は、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０の全てに対して以上の判定を行い、全ての次元可変サブベクトル２２０が対応するクラスタの分散の範囲に収まる場合は、コードブック２４０の更新は不要と判定する。一方、対応するクラスタの分散の範囲に収まらない次元可変サブベクトル２２０がある場合は、コードブック２４０の更新が必要と判定する。そして、コードブック更新部１６は、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０が加わることで分散の範囲が拡大することになるクラスタを更新の対象とし、新たな特徴ベクトル２１０から生成した次元可変サブベクトル２２０も含め、そのクラスタに属する次元可変サブベクトル２２０に対して、Ｘ−ｍｅａｎｓクラスタリングを行う。そして、このＸ−ｍｅａｎｓクラスタリングにより得られたクラスタのセントロイドの値で、コードブック２４０の中で更新の対象となるクラスタの代表ベクトルを更新する。

このとき、コードブック更新部１６は、Ｘ−ｍｅａｎｓクラスタリングにより複数のセントロイドが得られた場合は、コードブック２４０の中で更新の対象となるクラスタを複数のクラスタに分割する。そして、分割後のクラスタごとに、そのセントロイドの値を代表ベクトルとしてインデックスと対応付ける。この結果、コードブック２４０のインデックスの数が増えることになる。

図１４は、コードブック更新部１６による処理の概要を説明する図であり、次元Ｘ_１と次元Ｘ_２からなる２次元の次元可変サブベクトル２２０をサブベクトル空間にマッピングした様子を示している。ここでは、元の特徴ベクトル集合２００から生成されたサブベクトル群２３０に対するクラスタリングにより、各次元可変サブベクトル２２０が、図１４（ａ）に示すように、クラスタＣ１とクラスタＣ２の２つのクラスタにクラスタリングされているものとする。

ここで、新たな特徴ベクトル２１０から生成した新たな次元可変サブベクトル２２０が、特徴ベクトル空間上で図１４（ｂ）に示すようにマッピングされる場合を考える。この図１４（ｂ）に示す例では、新たな次元可変サブベクトル２２０は、クラスタＣ２の分散の範囲Ｒ＿Ｃ２内に収まっている。したがって、コードブック更新部１６は、次元Ｘ_１と次元Ｘ_２からなる２次元の次元可変サブベクトル２２０については、新たな特徴ベクトル２１０の追加によるコードブック２４０の更新は不要と判断する。そして、他の次元の次元可変サブベクトル２２０についても同様にコードブック２４０の更新が不要と判断すれば、コードブック更新部１６は、新たな特徴ベクトル２１０が特徴ベクトル集合２００に追加されてもコードブック２４０を更新しない。

次に、新たに追加される特徴ベクトル２１０が複数あり、これら複数の特徴ベクトル２１０の各々から生成した次元Ｘ_１と次元Ｘ_２からなる２次元の次元可変サブベクトル２２０が、特徴ベクトル空間上で図１４（ｃ）に示すようにマッピングされる場合を考える。ここでは、複数の新たな次元可変サブベクトル２２０はいずれも、クラスタＣ１の代表ベクトルよりはクラスタＣ２の代表ベクトルに近いものとする。この図１４（ｃ）に示す例では、新たな次元可変サブベクトル２２のいくつかが、クラスタＣ２の分散の範囲Ｒ＿Ｃ２から外れている。したがって、コードブック更新部１６は、クラスタＣ２を更新の対象とする。そして、クラスタＣ２に属する元の次元可変サブベクトル２２０と新たな次元可変サブベクトル２２０とを対象にＸ−ｍｅａｎｓクラスタリングを行い、このＸ−ｍｅａｎｓクラスタリングにより得られたセントロイドの値で、コードブック２４０のクラスタＣ２の代表ベクトルを更新する。

このとき、Ｘ−ｍｅａｎｓクラスタリングにより図１４（ｄ）に示すように２つのセントロイドが得られた場合、つまり、Ｘ−ｍｅａｎｓクラスタリングによりクラスタＣ２が２つのクラスタＣ２ａ，Ｃ２ｂに分割される場合、コードブック更新部１６は、コードブック２４０のクラスタＣ２を２つのクラスタＣ２ａ，Ｃ２ｂに分割し、それぞれのセントロイドをクラスタＣ２ａ，Ｃ２ｂの代表ベクトルとして、個別にインデックスに対応付ける。以上の処理により、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加されたときのコードブック２４０の更新を効率よく行うことができる。

以上のように、本実施例では、特徴ベクトル集合２００に新たな特徴ベクトル２１０が追加された場合に、コードブック２４０の更新が必要か否かを判定し、更新が必要と判定した場合のみコードブック２４０を更新するようにしているので、上述の第１実施例と同様に特徴ベクトル２１０の量子化効率を改善できることに加え、新たな特徴ベクトル２１０の追加によるコードブック２４０の更新を効率よく行うことができるといった効果が得られる。

＜補足説明＞
上述した各実施例のデータ処理装置１０Ａ，１０Ｂ，１０Ｃ（以下、総称して「データ処理装置１０」と表記する）は、一例として、一般的なコンピュータとしてのハードウェアを用いた実行環境で動作するプログラムによる実装が可能である。この場合、データ処理装置１０における上述の各機能的な構成要素（サブベクトル群生成部１１、コードブック生成部１２、変換部１３、パラメタ調整部１４、差分ルックアップテーブル生成部１５、コードブック更新部１６）は、ハードウェアとソフトウェア（プログラム）との協働により実現される。

図１５は、データ処理装置１０のハードウェア構成例を示すブロック図である。データ処理装置１０は、例えば図１５に示すように、ＣＰＵ（Central Processing Unit）１０１などのプロセッサ回路、ＲＯＭ（Read Only Memory）１０２やＲＡＭ（Random Access Memory）１０３などの記憶装置、表示パネルや各種操作デバイスが接続される入出力Ｉ／Ｆ１０４、ネットワークに接続して通信を行う通信Ｉ／Ｆ１０５、各部を接続するバス１０６などを備えた、一般的なコンピュータを利用したハードウェア構成とすることができる。

また、上述した構成のハードウェア上で実行されるプログラムは、例えば、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disc）などのコンピュータで読み取り可能な記録媒体に記録されてコンピュータプログラムプロダクトとして提供される。また、上述した構成のハードウェア上で実行されるプログラムを、インターネットなどのネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、上述した構成のハードウェア上で実行されるプログラムをインターネットなどのネットワーク経由で提供または配布するように構成してもよい。また、上述した構成のハードウェア上で実行されるプログラムを、ＲＯＭ１０２などに予め組み込んで提供するように構成してもよい。

上述した構成のハードウェア上で実行されるプログラムは、データ処理装置１０の各機能的な構成要素を含むモジュール構成となっており、例えば、ＣＰＵ１０１（プロセッサ回路）が上記記録媒体からプログラムを読み出して実行することにより、上述した各部がＲＡＭ１０３（主記憶）上にロードされ、ＲＡＭ１０３（主記憶）上に生成されるようになっている。なお、データ処理装置１０の各機能的な構成要素は、複数のコンピュータに跨って実現される構成であってもよい。また、上述の機能的な構成要素の一部または全部を、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field-Programmable Gate Array）などの専用のハードウェアを用いて実現することも可能である。

以上述べた少なくとも一つの実施形態によれば、特徴ベクトルを効率よく量子化できる。

以上、本発明の実施形態を説明したが、ここで説明した実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。ここで説明した新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。ここで説明した実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１０（１０Ａ，１０Ｂ，１０Ｃ） データ処理装置
１１ サブベクトル群生成部
１２ コードブック生成部
１３ 変換部
１４ パラメタ調整部
１５ 差分ルックアップテーブル生成部
１６ コードブック更新部
２００ 特徴ベクトル集合
２１０ 特徴ベクトル（Ｄ次元特徴ベクトル）
２２０ サブベクトル（次元可変サブベクトル）
２３０ サブベクトル群
２４０ コードブック
２５０ 圧縮コード
２６０ 圧縮コード集合
２８０ 差分ルックアップテーブル

Claims (8)

1. Ｎ個のＤ次元特徴ベクトルからなる特徴ベクトル集合から、Ｍ個（ただし、Ｍ＜Ｄ）のサブベクトル群を生成するサブベクトル群生成部であって、前記Ｍ個のサブベクトル群の各々は、前記Ｎ個のＤ次元特徴ベクトルの各々から得られたＮ個の次元可変サブベクトルからなり、前記Ｎ個の次元可変サブベクトルの各々は、前記Ｄ次元特徴ベクトルから抽出された１以上の次元の値を要素とし、前記Ｍ個のサブベクトル群のうちの少なくとも１つのサブベクトル群における前記次元可変サブベクトルの要素の数が他のサブベクトル群における前記次元可変サブベクトルの要素の数と異なる、前記サブベクトル群生成部と、
   前記Ｍ個のサブベクトル群ごとに、前記Ｎ個の次元可変サブベクトルをクラスタリングして、各クラスタの代表ベクトルをインデックスと対応付けたコードブックを生成するコードブック生成部と、
   前記コードブックを用いた直積量子化により、前記Ｎ個のＤ次元特徴ベクトルの各々を、Ｍ個のインデックスの組み合わせからなる圧縮コードに変換する変換部と、
   を備え、
   前記サブベクトル群生成部は、前記Ｍ個のサブベクトル群同士で前記次元可変サブベクトルの分散の度合いが近くなるように、前記特徴ベクトル集合から前記Ｍ個のサブベクトル群を生成する
   データ処理装置。
2. 前記コードブック生成部は、前記Ｍ個のサブベクトル群ごとに、推定されるサブベクトル群の最適クラスタ数に基づいて前記Ｎ個の次元可変サブベクトルをクラスタリングして、前記Ｍ個のサブベクトル群のうちの少なくとも１つのサブベクトル群に対応するクラスタ数が他のサブベクトル群に対応するクラスタ数と異なる前記コードブックを生成する
   請求項１に記載のデータ処理装置。
3. 前記サブベクトル群生成部は、前記Ｎ個のＤ次元特徴ベクトルの各次元について最適クラスタ数Ｃを求めて最適クラスタ数Ｃが同じ次元をグループ化し、ＧＣ（ただし、Ｇはグループに属する次元の数）で表されるサブベクトル群の最適クラスタ数がクラスタ数上限値Ｔを超えるグループについては、ＧＣ≦ＴまたはＧ＝１になるまでグループを分割することにより、前記特徴ベクトル集合から前記Ｍ個のサブベクトル群を生成する
   請求項１に記載のデータ処理装置。
4. 前記Ｎ個のＤ次元特徴ベクトルの各々を前記圧縮コードに変換する前後における検索精度の変動率、または、前記Ｎ個のＤ次元特徴ベクトルの各々を前記圧縮コードに変換することによる圧縮率が、設定された目標値に近づくように、前記クラスタ数上限値Ｔを探索的に決定するパラメタ調整部をさらに備える
   請求項３に記載のデータ処理装置。
5. 前記Ｍ個のサブベクトル群の各々について、前記クラスタごとの前記次元可変サブベクトルの分散の範囲を示す値を前記インデックスと対応付けた差分ルックアップテーブルを生成する差分ルックアップテーブル生成部と、
   前記特徴ベクトル集合に新たな特徴ベクトルが追加された場合に、新たな特徴ベクトルから生成される次元可変サブベクトルの各々のクラスタを求め、前記差分ルックアップテーブルを参照して、新たな特徴ベクトルから生成される全ての次元可変サブベクトルが対応するクラスタの分散の範囲に収まるか否かを判定し、対応するクラスタの分散の範囲に収まらない次元可変サブベクトルがあれば、前記コードブックの当該クラスタの代表ベクトルを更新するコードブック更新部と、をさらに備える
   請求項１乃至４のいずれか一項に記載のデータ処理装置。
6. 前記コードブック更新部は、更新の対象となるクラスタを複数のクラスタに分割し、分割後のクラスタごとに代表ベクトルをインデックスと対応付ける
   請求項５に記載のデータ処理装置。
7. Ｎ個のＤ次元特徴ベクトルからなる特徴ベクトル集合から、Ｍ個（ただし、Ｍ＜Ｄ）のサブベクトル群を生成するサブベクトル群生成工程であって、前記Ｍ個のサブベクトル群の各々は、前記Ｎ個のＤ次元特徴ベクトルの各々から得られたＮ個の次元可変サブベクトルからなり、前記Ｎ個の次元可変サブベクトルの各々は、前記Ｄ次元特徴ベクトルから抽出された１以上の次元の値を要素とし、前記Ｍ個のサブベクトル群のうちの少なくとも１つのサブベクトル群における前記次元可変サブベクトルの要素の数が他のサブベクトル群における前記次元可変サブベクトルの要素の数と異なる、前記サブベクトル群生成工程と、
   前記Ｍ個のサブベクトル群ごとに、前記Ｎ個の次元可変サブベクトルをクラスタリングして、各クラスタの代表ベクトルをインデックスと対応付けたコードブックを生成するコードブック生成工程と、
   前記コードブックを用いた直積量子化により、前記Ｎ個のＤ次元特徴ベクトルの各々を、Ｍ個のインデックスの組み合わせからなる圧縮コードに変換する変換工程と、
   を含み、
   前記サブベクトル群生成工程は、前記Ｍ個のサブベクトル群同士で前記次元可変サブベクトルの分散の度合いが近くなるように、前記特徴ベクトル集合から前記Ｍ個のサブベクトル群を生成する
   データ処理方法。
8. コンピュータに、
   Ｎ個のＤ次元特徴ベクトルからなる特徴ベクトル集合から、Ｍ個（ただし、Ｍ＜Ｄ）のサブベクトル群を生成するサブベクトル群生成部であって、前記Ｍ個のサブベクトル群の各々は、前記Ｎ個のＤ次元特徴ベクトルの各々から得られたＮ個の次元可変サブベクトルからなり、前記Ｎ個の次元可変サブベクトルの各々は、前記Ｄ次元特徴ベクトルから抽出された１以上の次元の値を要素とし、前記Ｍ個のサブベクトル群のうちの少なくとも１つのサブベクトル群における前記次元可変サブベクトルの要素の数が他のサブベクトル群における前記次元可変サブベクトルの要素の数と異なる、前記サブベクトル群生成部の機能と、
   前記Ｍ個のサブベクトル群ごとに、前記Ｎ個の次元可変サブベクトルをクラスタリングして、各クラスタの代表ベクトルをインデックスと対応付けたコードブックを生成するコードブック生成部の機能と、
   前記コードブックを用いた直積量子化により、前記Ｎ個のＤ次元特徴ベクトルの各々を、Ｍ個のインデックスの組み合わせからなる圧縮コードに変換する変換部の機能と、
   を実現させ、
   前記サブベクトル群生成部は、前記Ｍ個のサブベクトル群同士で前記次元可変サブベクトルの分散の度合いが近くなるように、前記特徴ベクトル集合から前記Ｍ個のサブベクトル群を生成する
   プログラム。

Images