(57)【特許請求の範囲】
【請求項１】
ベクトル集合を代表する代表ベクトル生成方法において、
予め入力ベクトル集合に属する全ての要素のベクトルの長さを同じ長さに正規化して入力ベクトル集合記憶手段に格納しておき、
入力手段からベクトル量子化数、代表ベクトル集合を算出する際の総学習回数である終了回数、次回代表ベクトルを生成するまでの学習回数である検査回数が入力されると、初期化手段が、学習に必要な初期設定を行う初期化ステップと、
代表ベクトル更新手段が、前記入力ベクトル集合記憶手段から選択した入力ベクトルと、既に生成され代表ベクトル集合記憶手段に格納されている各代表ベクトルとの距離を計算し、代表ベクトルの中で最も該入力ベクトルとの距離が小さい代表ベクトルを抽出し、計算された該距離を抽出した代表ベクトルの部分ひずみに加算し、該代表ベクトルを更新する学習ステップと、
正規化手段が、前記学習ステップで更新された前記代表ベクトルを前記入力ベクトル集合と同じ長さに正規化し、前記代表ベクトル集合記憶手段に格納する正規化ステップと、
からなり、
前記学習ステップと前記正規化ステップを前記終了回数に達するまで繰り返し行うことを特徴とする代表ベクトル生成方法。
【請求項２】
前記学習ステップにおいて、
K-means法を用いてクラスタの重心を求めて代表ベクトルを更新する
請求項１記載の代表ベクトル生成方法。
【請求項３】
代表ベクトル生成手段が、前記学習ステップの学習回数が前記検査回数に達し、かつ、代表ベクトル数が、入力されたベクトル量子化数よりも小さい場合は、前記代表ベクトルに関する部分ひずみが最も大きな代表ベクトルを選択し、選択された該代表ベクトルと同じベクトル値を持つ新たなベクトルを生成する代表ベクトル生成ステップを行う
請求項１記載の代表ベクトル生成方法。
【請求項４】
ベクトル集合を代表する代表ベクトル生成装置であって、
予め入力ベクトル集合に属する全ての要素のベクトルの長さを同じ長さに正規化して格納された入力ベクトル集合記憶手段と、
入力手段からベクトル量子化数、代表ベクトル集合を算出する際の総学習回数である終了回数、次回代表ベクトルを生成するまでの学習回数である検査回数が入力されると、初期化手段が、学習に必要な初期設定を行う初期化手段と、
前記入力ベクトル集合記憶手段から選択した入力ベクトルと、既に生成され代表ベクトル集合記憶手段に格納されている各代表ベクトルとの距離を計算し、代表ベクトルの中で最も該入力ベクトルとの距離が小さい代表ベクトルを抽出し、計算された該距離を抽出した代表ベクトルの部分ひずみに加算し、該代表ベクトルを更新する代表ベクトル更新手段と、
前記代表ベクトル更新手段で更新された前記代表ベクトルを前記入力ベクトル集合と同じ長さに正規化し、前記代表ベクトル集合記憶手段に格納する正規化手段と、
を有することを特徴とする代表ベクトル生成装置。
【請求項５】
請求項４記載の代表ベクトル生成装置を構成する各手段としてコンピュータを機能させるための代表ベクトル生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、代表ベクトル生成方法及び装置及びプログラムに係り、特に、ベクトル集合からそれを代表する代表ベクトル算出（抽出）する代表ベクトル生成方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
ベクトル集合から代表ベクトルを算出する方法として、例えば、K-means法がある。この方法は、ベクトル集合を代表ベクトルによってベクトル量子化した際の量子化誤差を最小にする基準で代表ベクトルを算出する（例えば、特許文献１、非特許文献１参照）。
【特許文献１】特許第３２５４１０９号公報
【非特許文献１】大津展之、栗田多喜夫、関田巌、"パターン認識"，朝倉書店，１９９６
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の従来技術では、入力となるベクトル集合中に存在するクラスタが多次元正規分布に近くなることを暗に仮定している。しかし、この仮定が全く当てはまらないベクトル集合があり、その場合には近傍のベクトル群を代表する意味での適切な代表ベクトルを算出できない問題がある。その典型的な例は、ベクトル集合の各要素ベクトルが原点から離れた特徴空間の表面近くに偏在する場合や入力となるベクトルの生成過程においてベクトル長を一定とする場合などである。このような場合において、ベクトル集合が部分集合を考えたとき、その重心は原点に近いところとなり、重心の近傍にはベクトルが存在しないという現象が起こり易い。すなわち、重心の近傍ほどベクトルの存在確率が大きいという正規分布が成立していない。そのため、従来技術によって得られた代表ベクトルがベクトル集合をよく表していないという問題が生じていた。
【０００４】
本発明は、上記の点に鑑みなされたもので、近傍のベクトル群を代表する意味での適切な代表ベクトルを算出することが可能な代表ベクトル生成方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
図１は、本発明の原理を説明するための図である。
【０００６】
本発明（請求項１）は、ベクトル集合を代表する代表ベクトル生成方法において、
予め入力ベクトル集合に属する全ての要素のベクトルの長さを同じ長さに正規化して入力ベクトル集合記憶手段に格納しておき（ステップ１）、
入力手段からベクトル量子化数、代表ベクトル集合を算出する際の総学習回数である終了回数、次回代表ベクトルを生成するまでの学習回数である検査回数が入力されると、初期化手段が、学習に必要な初期設定を行う初期化ステップ（ステップ２）と、
代表ベクトル更新手段が、入力ベクトル集合記憶手段から選択した入力ベクトルと、既に生成され代表ベクトル集合記憶手段に格納されている各代表ベクトルとの距離を計算し、代表ベクトルの中で最も該入力ベクトルとの距離が小さい代表ベクトルを抽出し、計算された該距離を抽出した代表ベクトルの部分ひずみに加算し、該代表ベクトルを更新する学習ステップ（ステップ３）と、
正規化手段が、学習ステップで更新された代表ベクトルを入力ベクトル集合と同じ長さに正規化し、代表ベクトル集合記憶手段に格納する正規化ステップ（ステップ４）と、
からなり、
学習ステップと正規化ステップを終了回数に達するまで繰り返し行う。
【０００７】
また、本発明（請求項２）は、学習ステップにおいて、
K-means法を用いてクラスタの重心を求めて代表ベクトルを更新する。
【０００８】
また、本発明（請求項３）は、代表ベクトル生成手段が、学習回数が検査回数に達し、かつ、代表ベクトル数が、入力されたベクトル量子化数よりも小さい場合は、代表ベクトルに関する部分ひずみが最も大きな代表ベクトルを選択し、選択された該代表ベクトルと同じベクトル値を持つ新たなベクトルを生成する代表ベクトル生成ステップを行う。
【０００９】
図２は、本発明の原理構成図である。
【００１０】
本発明（請求項４）は、ベクトル集合を代表する代表ベクトル生成装置であって、
予め入力ベクトル集合に属する全ての要素のベクトルの長さを同じ長さに正規化して格納された入力ベクトル集合記憶手段１０１と、
入力手段１からベクトル量子化数、代表ベクトル集合を算出する際の総学習回数である終了回数、次回代表ベクトルを生成するまでの学習回数である検査回数が入力されると、初期化手段が、学習に必要な初期設定を行う初期化手段２と、
入力ベクトル集合記憶手段１０１から選択した入力ベクトルと、既に生成され代表ベクトル集合記憶手段に格納されている各代表ベクトルとの距離を計算し、代表ベクトルの中で最も該入力ベクトルとの距離が小さい代表ベクトルを抽出し、計算された該距離を抽出した代表ベクトルの部分ひずみに加算し、該代表ベクトルを更新する代表ベクトル更新手段５と、
代表ベクトル更新手段５で更新された代表ベクトルを入力ベクトル集合と同じ長さに正規化し、代表ベクトル集合記憶手段１０２に格納する正規化手段６と、を有する。
【００１１】
本発明（請求項５）は、請求項４記載の代表ベクトル生成装置を構成する各手段としてコンピュータを機能させるための代表ベクトル生成プログラムである。
【発明の効果】
【００１２】
上記のように、本発明によれば、入力となるベクトル集合の長さを同じ長さに正規化することと、代表ベクトルを更新しながら算出する過程において、その長さをベクトル集合のベクトルと同じ長さに制約することにより、入力ベクトル集合が存在する多次元空間の超球面上に代表ベクトルが存在する状態を実現し、結果として近傍のベクトル群を代表する意味での適切な代表ベクトルを算出することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面と共に本発明の実施の形態を説明する。
【００１４】
図３は、本発明の一実施の形態における特徴抽出装置の構成を示す。
【００１５】
同図に示す装置は、入力部１、初期化部２、入力ベクトル選択部３、距離計算部４、代表ベクトル更新部５、正規化部６、部分ひずみ計算部７、代表ベクトル生成部８、入力ベクトル集合記憶部１０１、代表ベクトル集合記憶部１０２から構成される。
【００１６】
入力部１は、ベクトル量子化数、終了回数、検査回数を入力する。
【００１７】
初期化部２は、学習に必要なパラメータの初期設定を行う。
【００１８】
入力ベクトル選択部３は、入力ベクトル集合記憶部１０１からランダムに１つの入力ベクトルを選択し、初期化部２及び距離計算部４に出力する。
【００１９】
距離計算部４は、入力ベクトル集合記憶部１０１から取得した入力ベクトルと、代表ベクトル集合記憶部１０２に格納されている各代表ベクトルとのユークリッド２乗距離を算出する。
【００２０】
代表ベクトル更新部５は、代表ベクトルの中で最も入力ベクトルとの距離が小さい代表ベクトルを選択し、距離計算部４で求められた距離を部分ひずみに加算し、当該代表ベクトルを更新する。
【００２１】
正規化部６は、代表ベクトルの長さを入力ベクトル集合のベクトルの長さに合わせて正規化する。なお、全ての要素ベクトルの長さが既に正規化されている場合には当該機能は省略することができる。
【００２２】
部分ひずみ計算部７は、代表ベクトルと組となっている部分ひずみとして、入力ベクトルとの距離を計算して設定する。
【００２３】
代表ベクトル生成部８は、選択された代表ベクトルと同じベクトル値を持つ代表ベクトルを生成する。このとき前述の特許文献１や非特許文献１のK-means法を用いるものとする。これにより、ベクトル量子化した際の量子化誤差を最小にすることができる。
【００２４】
以下に示す方法は、競合学習を用いる例である。
【００２５】
図４の動作に先立って、入力ベクトル集合記憶部１０１に格納されている入力ベクトル集合の要素ベクトルの各次元の値ｘｉを、予め以下の式により予め長さを１に正規化しておくものとする。
【００２６】
【数１】
0004751913.tif 000002
ここで、ベクトルのＭは次元数を表す。
【００２７】
図４は、本発明の一実施の形態における特徴抽出方法のフローチャートである。
【００２８】
ステップ１０１）  入力部１からベクトル量子化数（ｎ）、終了回数（Ｌ）、検査回数（Ｃ）を入力する。ここで、終了回数Ｌは、代表ベクトル集合を算出する際の総学習回数を表し、検査回数Ｃは代表ベクトルを順次生成する際、次回代表ベクトルを生成するための学習回数を表す。
【００２９】
ステップ１０２）  次に、初期化部２において、学習に必要なパラメータの初期設定を行う。既に生成された代表ベクトル数ｑを定義して、１を代入し（ｑ＝１）、検査回数Ｃに達するまでの学習回数をカウントする部分回数ｒを定義して初期値０を代入し（ｒ＝０）、入力ベクトル集合記憶部１０１から入力ベクトル選択部３を介してランダムに１つの入力ベクトルを選択し、そのベクトル値を１個目の代表ベクトルと定め、付帯する部分ひずみの値に０を代入する。
【００３０】
ステップ１０３）  制御部９は、部分回数ｒが検査回数Ｃに達しており、かつ代表ベクトル数ｑがベクトル量子化数ｎよりも小さい（ｒ＝Ｃかつｑ＜ｎ）か否かを判断する。ここでＹｅｓであれば、ステップ１１０に移行し、Ｎｏならば、以下の処理を行う。
【００３１】
ステップ１０４）  入力ベクトル選択部３において、入力ベクトル集合記憶部１０１からランダムに１つの入力ベクトルを選択する。
【００３２】
ステップ１０５）  距離計算部４において、選択された入力ベクトルＸと代表ベクトル集合記憶部１０２に格納されている既に生成された各代表ベクトルＷとのユークリッド２乗距離を計算する。
【００３３】
ステップ１０６）  代表ベクトル更新部５は、代表ベクトル中で最も入力ベクトルＸとの距離が小さい代表ベクトルＷを選出し、メモリ（図示せず）に格納する。同じ距離の代表ベクトルがあった場合は、代表ベクトル集合記憶部１０２に登録が若い代表ベクトルを選択する。また、入力ベクトルと選択された代表ベクトルとの距離を、各代表ベクトルに付帯している「部分ひずみ」に加算する。
【００３４】
代表ベクトル更新部５は、メモリ（図示せず）に格納されているステップ１０４で選出された代表ベクトルを更新する。まず、選出された代表ベクトルＷ、入力ベクトルＸ、学習係数ｇを用いて、仮の代表ベクトルＷをＷ←Ｗ＋ｇ（Ｘ−Ｗ）により求める。更に、正規化部６において、ベクトルの各次元の値ｗｉを以下の式（２）により正規化する。
【００３５】
【数２】
0004751913.tif 000003
ステップ１０７）  次に、制御部９において、部分回数ｒと学習回数ｔとに１を加える。
【００３６】
ステップ１０８）  学習回数ｔがＬに達しているか否かを判断する。ここで、Ｙｅｓであれば、ステップ１０９に移行し、ＮＯであれば、ステップ１０３に戻る。
【００３７】
ステップ１０９）  全ての代表ベクトルを「代表ベクトル集合」として代表ベクトル集合記憶部１０２に保存し、終了する。
【００３８】
ステップ１１０）  上記のステップ１０３〜１０９の処理を繰り返し、ステップ１０３において、部分回数ｒが検査回数Ｃに達し、代表ベクトル数ｑがベクトル量子化数ｎより小さい場合は、以下の代表ベクトル生成処理を行う。
【００３９】
部分回数ｒを０クリアする（ｒ＝０）。
【００４０】
ステップ１１１）  部分ひずみ計算部７において、部分ひずみ計算を行う。「部分ひずみ」とは、入力ベクトル集合を各代表ベクトルで量子化した際に生じる量子化誤差を代表ベクトル毎に集計した値である。実際に計算することも可能であるが、ここでは、学習の度に入力ベクトルとの距離を加算してきた「部分ひずみ」を各代表ベクトルに関する部分ひずみ（真値）の近似と考え、最も部分ひずみの大きな代表ベクトルを選択する。また、全ての部分ひずみの値を０にする。
【００４１】
ステップ１１２）  次に、代表ベクトル生成部８において、選択した代表ベクトルに基づいて新たな代表ベクトルを生成する。すなわち、選択された代表ベクトルと同じベクトル値を持つ新たな代表ベクトルを１個生成する。
【００４２】
ステップ１１３）  制御部９において、代表ベクトル数ｑに１を足して、ステップ１０３に移行する。
【００４３】
以上のようにして、初期的に１個であった代表ベクトルが学習を検査回数Ｃ繰り返す毎に１個ずつ追加されていき、最終的に量子化数ｎに等しい個数まで生成される。また、代表ベクトルの学習が繰り返されていき、最終的に終了回数Ｌに達したときに、すべての代表ベクトルを「代表ベクトル集合」として，代表ベクトル集合記憶部１０２に保存し、終了する。
【００４４】
また、上記の図３に示す構成における構成要素の動作をプログラムとして構築し、代表ベクトル生成装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００４５】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００４６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００４７】
本発明は、ベクトル量子化のための代表ベクトル生成技術に適用可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における代表ベクトル生成装置の構成図である。
【図４】本発明の一実施の形態における代表ベクトル生成方法のフローチャートである。
【符号の説明】
【００４９】
１  入力手段、入力部
２  初期化手段、初期化部
３  入力ベクトル選択部
４  距離計算部
５  代表ベクトル更新手段、代表ベクトル更新部
６  正規化手段、正規化部
７  部分ひずみ計算部
８  代表ベクトル生成部
１０１  入力ベクトル集合記憶手段、入力ベクトル集合記憶部
１０２  代表ベクトル集合記憶手段、代表ベクトル集合記憶部
【図１】
0004751913.tif 000004
【図２】
0004751913.tif 000005
【図３】
0004751913.tif 000006
【図４】
0004751913.tif 000007