(57)【要約】【課題】汎化能力を高めた特徴選択装置を提供する。【解決手段】遺伝的アルゴリズムを用いて、サンプルの特徴を選択する特徴選択装置であって、カテゴリ間の決定境界である超平面からのすべての学習用サンプルの距離を算出する手段と、すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定する手段と、設定された２つの超平面からはみ出した学習用サンプルに対して、２つの超平面からはみ出した長さに応じたペナルティ値を計算する手段と、２つの超平面の間隔と、ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を基準サンプルの評価値とする手段と、基準サンプル評価手段を用いてすべての学習用サンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する手段とを備えた。【選択図】図１
2012238075.tif 000002
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させる特徴選択装置であって、
カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出手段と、
すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定手段と、
前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算手段と、
前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価手段と、
前記基準サンプル評価手段を用いてすべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価手段と
を備えたことを特徴とする特徴選択装置。
【請求項２】
遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させるために、距離算出手段と、マージン設定手段と、ペナルティ計算手段と、基準サンプル評価手段と、評価手段とを備えた特徴選択装置における特徴選択方法であって、
前記距離算出手段が、カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出ステップと、
前記マージン設定手段が、すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定ステップと、
前記ペナルティ計算手段が、前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算ステップと、
前記基準サンプル評価手段が、前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価ステップと
前記評価手段が、前記基準サンプル評価手段を用いてすべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価ステップと
を有することを特徴とする特徴選択方法。
【請求項３】
遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させる特徴選択装置上のコンピュータに特徴選択処理を行わせる特徴選択プログラムであって、
カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出ステップと、
すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定ステップと、
前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算ステップと、
前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価ステップと
前記基準サンプル評価ステップにより、すべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価ステップと
を前記コンピュータに行わせることを特徴とする特徴選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン認識の識別精度を向上させる技術のひとつである、特徴を選択する技術（以下、特徴選択と称する）に関し、特にその中で遺伝的アルゴリズム（以下、ＧＡと称する）を用いる技術に関する。
【背景技術】
【０００２】
ＧＡを用いた特徴選択の従来の技術としては、学習用の多くのパターンおよび各々の成果カテゴリ情報から構成されるデータベースを用い、特徴の組合せを変化させてデータベースを用いた識別および識別率の集計を繰り返し、識別率を適応度とする探索をＧＡで行う方法が知られている（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】浜本義彦、古里眞理、金山知余、富田眞吾：「遺伝的アルゴリズムを用いた特徴選択法」信学論（Ａ）、ｖｏｌ．Ｊ７８−Ａ、ｎｏ．１０、ｐｐ．１３８５−１３８９（１９９５）．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の特徴選択の技術では、汎化能力を高めることができなかった。識別における汎化能力とは、学習サンプルだけに対してだけでなく未知のサンプルに対しても高い識別率で識別できる能力であり、実用上非常に重要な特性である。汎化能力を重視した識別器である線形ＳＶＭの考え方によれば、決定境界と近接した学習サンプルとのユークリッド距離である「マージン」をできる限り高めることが識別器の汎化能力を高めるのに有効であるとされているが、このような考え方に基づく特徴選択の技術はこれまでなかった。
【０００５】
本発明は、このような事情に鑑みてなされたもので、汎化能力を高める特徴選択の技術を実現することができる特徴選択装置、特徴選択方法及び特徴選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させる特徴選択装置であって、カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出手段と、すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定手段と、前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算手段と、前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価手段と、前記基準サンプル評価手段を用いてすべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価手段とを備えたことを特徴とする。
【０００７】
本発明は、遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させるために、距離算出手段と、マージン設定手段と、ペナルティ計算手段と、基準サンプル評価手段と、評価手段とを備えた特徴選択装置における特徴選択方法であって、前記距離算出手段が、カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出ステップと、前記マージン設定手段が、すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定ステップと、前記ペナルティ計算手段が、前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算ステップと、前記基準サンプル評価手段が、前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価ステップと前記評価手段が、前記基準サンプル評価手段を用いてすべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価ステップとを有することを特徴とする。
【０００８】
本発明は、遺伝的アルゴリズムを用いて、サンプルの特徴を選択することによりパターン認識の識別精度を向上させる特徴選択装置上のコンピュータに特徴選択処理を行わせる特徴選択プログラムであって、カテゴリ間の決定境界である超平面からのすべての学習用のサンプルの距離を算出する距離算出ステップと、すべての学習用サンプルの中の１個を選んで基準サンプルとし、決定境界の両側の前記基準サンプルと決定境界の距離の位置それぞれに２つの超平面を設定するマージン設定ステップと、前記設定された２つの超平面からはみ出した学習用のサンプルに対して、前記２つの超平面からはみ出した長さに応じたペナルティ値を計算するペナルティ計算ステップと、前記２つの超平面の間隔と、前記ペナルティ値とに基づいて、ロバスト性の評価尺度を算出し、該評価尺度の値を前記基準サンプルの評価値とする基準サンプル評価ステップと前記基準サンプル評価ステップにより、すべての学習用のサンプル毎に、それらを基準サンプルとして用いた時の評価値を算出し、その中の最小値を選択された特徴の評価値として出力する評価ステップとを前記コンピュータに行わせることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、遺伝的アルゴリズムを用いた特徴選択において、染色体の適応度として線形ＳＶＭのソフトマージンをベースとする評価尺度を用いたため、線形ＳＶＭと同様に汎化能力の高い特徴選択を行うことができるという効果が得られる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態の構成を示すブロック図である。
【図２】染色体の構造を示す説明図である。
【図３】図１に示す染色体評価手段８の構成を示すブロック図である。
【図４】学習サンプルの集合をψ、標準パターンをＷ１，Ｗ２とすると選択された特徴空間におけるψの分布を示す模式図である。
【図５】特徴空間における標準パターンと決定境界、サンプルの位置関係の概念図である。
【図６】図１に示す特徴選択装置１の処理動作を示すフローチャートである。
【図７】図１に示す全世代染色体集合格納手段４の構成を示す説明図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、本発明の一実施形態による特徴選択装置を説明する。図１は同実施形態の構成を示すブロック図である。この図において、符号１は、コンピュータ装置によって構成する特徴選択装置である。符号２は、装置全体を統括して動作を制御する全体制御手段である。符号３は、初期の染色体集合を作成する初期染色体集合作成手段である。符号４は、全世代の染色体集合を格納する全世代染色体集合格納手段である。符号５は、選択確率値を算出する選択確率値算出手段である。符号６は、世代数をカウントする世代数カウンタである。符号７は、個別世代実行部である。符号７１は、交叉処理を行う交叉実行手段である。符号７２は、突然変異処理を行う突然変異実行手段である。符号７３は、複製処理を実行する複製実行手段である。符号７４は、染色体集合の並べ替えを行う染色体集合並べ替え手段である。符号８は、染色体の評価を行う染色体評価手段である。
【００１２】
まず、識別手法について説明する。識別手法には種々の方法があるが、本実施形態では、入力パターンと各カテゴリーの標準パターンとのユークリッド距離の中で最小値をとる標準パターンに対応するカテゴリーを識別結果とする最小距離識別を用いることとする。最小距離識別では２カテゴリー問題の場合、決定境界は２つの標準パターンを結ぶ線分を二等分する超平面となる。標準パターンは、学習サンプルの平均とする。
【００１３】
次に、図２を参照して、染色体の構造について説明する。図２は染色体の構造を示す図である。原特徴の次元数をＬとして、Ｌ次元の中で選択する次元を表現するベクトルを想定し、これを特徴選択ベクトルλと呼ぶ。この特徴選択ベクトルを、本実施形態ではそのままＧＡにおける染色体として用いる。λが選択する特徴の個数をＫで表し、図２に示すように特徴選択ベクトルを構成する。このベクトルは個別の要素が対応する特徴の使用の有無を表し、「１」が「使用する」、「０」が「使用しない」を表す。図２では、各々の次元の「１」で示された破線の枠で「使用する」の適用範囲を表している。個々の要素の値を、λ１，λ２，・・・，λＬで表す。
【００１４】
次に、図３を参照して、図１に示す染色体評価手段８の構成を説明する。図３は、図１に示す染色体評価手段８の構成を示すブロック図である。学習サンプルの原特徴の集合をΨ、学習サンプルの数をＮ、Ψの個別の要素をＸｉ（ｉ＝１，２，・・・，Ｎ）、Ｘｉが属するカテゴリの情報をｙｉで表し、カテゴリ１をｙｉ＝１、カテゴリ２をｙｉ＝−１で表す。このｙｉを教師信号と呼ぶ。識別対象とするカテゴリの個数を２、個々のカテゴリをカテゴリ１およびカテゴリ２とし、原特徴の次元数をＬとする。学習サンプル集合の格納手段８１には、学習サンプルの原特徴の集合をΨおよびすべての教師信号が事前に格納される。
【００１５】
原特徴空間における標準パターンの作成手段８２は、特徴選択装置１が起動した際に最初に動作する。全体制御手段２の動作の開始は、原特徴空間における標準パターンの作成手段の処理が完了した後で開始される。原特徴空間における標準パターンの作成手段８２は、原特徴空間における標準パターンを以下のように作成し、教師信号を用いてＸ１，Ｘ２，・・・，ＸＮの要素をカテゴリ１とカテゴリ２に分け、各々について平均を算出し、それらを原特徴空間におけるカテゴリ１と２の標準パターンとしてＭ１，Ｍ２で表す。
【００１６】
サンプルとカテゴリ間の距離算出手段８５は、決定境界からのサンプルの距離の算出手段８４から入力されたサンプルとカテゴリｋ（ｋ＝１、２）との、λの適用を前提とした距離を以下のように算出する。まず、λの適用を前提とした基本的なベクトル間の距離は以下の通りである。原特徴空間中の２つのベクトルＸＡ，ＸＢと特徴選択ベクトルλが与えられたとする。ＸＡ＝（ＸＡ１，ＸＡ２，・・・，ＸＡＬ）、ＸＢ＝（ＸＢ１，ＸＢ２，・・・，ＸＢＬ）とする。この時、ベクトルＸＡの要素ＸＡｉ（１≦ｉ≦Ｌ）の中から、対応するλｉが１に等しい要素だけを抽出し、それらをまとめてＫ次元のベクトル〜ＸＡ＝（〜ＸＡ１，〜ＸＡ２，・・・，〜ＸＡＫ）（〜は、Ｘの頭に付く、以下同様）を作成する。ＸＢからも同様の方法でＫ次元のベクトル〜ＸＢ＝（〜ＸＢ１，〜ＸＢ２，・・・，〜ＸＢＫ）を作成する。この２つを用いて、λを前提としたＸＡとＸＢの距離を（１）式の関数ｆＤにより算出する。（１）式は、ｆｄが特徴選択ベクトルλで選択された特徴だけを用いて算出したユークリッド距離であることを表す。
【数１】
2012238075.tif 000003
【００１７】
次に、カテゴリ１とカテゴリ２の標準パターンの間の距離を基準として、それがλが変わっても常に一定値「１」となるように特徴空間の座標系をスケール変換する方法を説明する。まず、任意のサンプルの原特徴をＸとし、これからλで選択された特徴でベクトルを作成し、これを〜Ｘ（〜は、Ｘの頭に付く）とする。また、原特徴の標準パターンＭｋ（ｋ＝１，２）からλで選択された特徴でベクトルを作成し、これを〜Ｍｋ（ｋ＝１，２）（〜は、Ｍの頭に付く、以下同様）とする。この〜Ｍｋ（ｋ＝１，２）を用いて、〜Ｘは（２）式の変換を受け、Ｋ次元のベクトルｘに変換される。
【数２】
2012238075.tif 000004
【００１８】
（２）式と同じ変換がカテゴリｋ（ｋ＝１、２）の標準パターンに対しても（３）式により行われる。
【数３】
2012238075.tif 000005
【００１９】
（３）式におけるＷｋは正規化後の標準パターンであり、これもＫ次元のベクトルである。（３）式により、ここではλが変わるごとに標準パターンが新たに作成されることになる。サンプルとカテゴリ間の距離算出手段８５では、任意のサンプルとカテゴリｋ（ｋ＝１、２）との距離を、ｆｄ（ｘ，Ｗｋ）により算出して出力する。
【００２０】
次に、図３を参照して、染色体評価手段８による染色体λの評価を行う動作を説明する。染色体評価手段８は、染色体λが入力されると、決定境界からのサンプルの距離の算出手段８４、ロバスト性の評価手段８６の順番に動作してそれを評価し、スコアを出力する。このスコアを適応度と呼ぶ。決定境界からのサンプルの距離の算出手段８４は、まず学習サンプルの集合Ψの各要素を（２）式によって変換した集合を作成し、これを｛ｘ１，ｘ２，・・・，ｘＮ｝とし、ψで表わす。
【００２１】
カテゴリ１とカテゴリ２の標準パターンの間の距離が１になるようにスケール変換を行なった特徴空間において、学習サンプルの集合をψ、標準パターンをＷ１，Ｗ２とすると選択された特徴空間におけるψの分布の模式図を図４に示す。図４において、黒丸がカテゴリ１のサンプル、白丸がカテゴリ２のサンプルを表す。またＨ０はカテゴリ間の決定境界の超平面を表す。
【００２２】
次に、決定境界からのサンプルの距離の算出手段８４は、決定境界Ｈ０からｘｉ（ｉ＝１，２，・・・，Ｎ）までのユークリッド距離ｈ（ｘｉ）（ｉ＝１，２，・・・，Ｎ）を算出する。具体的には、サンプルとカテゴリ間の距離算出手段を起動して、カテゴリ１、２との距離ｆＤ（ｘｉ，Ｗ１）、ｆＤ（ｘｉ，Ｗ２）を算出し、算出結果を用いて（４）式によりｈ（ｘｉ）を算出する。
【数４】
2012238075.tif 000006
【００２３】
特徴空間における標準パターンと決定境界、サンプルの位置関係の概念図を図５に示す。（４）式で算出されるｈ（ｘｉ）には正負の符号がついており、ｘｉがＨ０から見てカテゴリ１の側にあるときはｈ（ｘｉ）＞０、カテゴリ２の側にあるときはｈ（ｘｉ）＜０となる。また教師信号ｙｉとの積の符号によって識別結果の正誤を判断でき、ｈ（ｘｉ）・ｙｉ＞０であれば正しい識別結果、ｈ（ｘｉ）・ｙｉ＜０であれば誤った識別結果を意味する。
【００２４】
次に、ロバスト性の評価手段８６は、個別のｘｉについてｈ（ｘｉ）・ｙｉの符号を調べ、ｈ（ｘｉ）・ｙｉ＞０であれば以下に述べる（１）〜（３）によってｘｉにおけるロバスト性の評価尺度Ｓｉを算出し、ｈ（ｘｉ）・ｙｉ＜０であれば（１）〜（３）で算出される値の範囲よりも十分大きい正値の定数をＳｉとする。そして、すべてのｘｉについてＳｉの算出を行った後、Ｓｉの集合から最小値を算出し、その値を染色体λの適応度として出力する。
【００２５】
（１）マージンの設定
Ｈ０の両側の距離｜ｈ（ｘｉ）｜の位置に超平面Ｈ１，Ｈ２を設定する。Ｈ１，Ｈ２のいずれかにｘｉは含まれる。そして、Ｈ１とＨ２の間隔２・｜ｈ（ｘｉ）｜を算出し、これを２／ωｉで表す。すなわち、このｘｉは線形ＳＶＭのサポートベクトルに相当し、ここでは「サポートポイント」と呼ぶ。また、２／ωｉは線形ＳＶＭと同じくマージンを意味する。
【００２６】
（２）ペナルティの計算
上記（１）により設定されたマージンからはみ出したサンプルに対するペナルティを計算する。Ｈ１により特徴空間はＨ０の側の領域とその反対側の領域に二分割され、前者の領域に含まれているカテゴリ１のサンプルは分布の分離の度合いを低下させるとみなしてＨ１からの距離に比例するペナルティを与えるものとする。同様の処理をカテゴリ２のサンプルに対してもＨ２を用いて行う。これを定式化したものが（５）式である。
【数５】
2012238075.tif 000007
【００２７】
（５）式においてξｉｊがψの個別要素ｘｊに与えられるペナルティである。（５）式は、ｘｊがマージンからはみ出した場合には（すなわちｈ（ｘｊ）＞１／ωｉの場合）、はみ出した長さである（１／ωｉ−ｙ（ｊ）・ｈ（ｘｊ）の、１／ωｉに対する比率である（１−ｙ（ｊ）・ｈ（ｘｊ）・ωｉ）をペナルティとして与え、はみ出さない場合には０を与えることを意味する。そして、全体としてのペナルティとしてそれらの合計値ΣＮｊ＝１ξｉｊを算出する。
【００２８】
（３）最終的なＳｉの計算
（１）で算出したマージンの値２／ωｉと、（２）で算出したペナルティの値ΣＮｊ＝１ξｉｊを用いて、Ｓｉを以下の（６）式で計算する。
【数６】
2012238075.tif 000008
【００２９】
（６）式において、第１項はマージンを大きくとるための項であり、第２項はマージンからはみだしたサンプルに対するペナルティの項である。そしてＣは第１項と第２項のバランスをとるための定数であり、実験的に決定する。Ｓｉは低いほど良い値であるので、（７）式によって最小値を選択する。
【数７】
2012238075.tif 000009
【００３０】
次に、図６を参照して、図１に示す特徴選択装置１の処理動作を説明する。図６は、図１に示す特徴選択装置１の処理動作を示すフローチャートである。特徴選択装置１は遺伝的アルゴリズム（ＧＡ）に基づいて動作することを基本とする。ＧＡにおける世代の番号（世代数）をＧＮとする。全体制御手段２は、まずＧＮ＝１とし、この値を世代数カウンタ６にセットする（ステップＳ１）。続いて、全体制御手段２は初期染色体集合作成手段３に対して動作開始を指示する。
【００３１】
ここで、全世代染色体集合格納手段４の構成を説明する。図７（ａ）は全世代染色体集合格納手段４の構成例であり、ＧＮｍａｘ個の染色体集合が個別の染色体集合格納部に格納される。全世代染色体集合格納手段４における個別の染色体集合格納部は各世代番号ＧＮに対応しており、ＧＮの染色体集合格納手段をＡ（ＧＮ）で表わす。個別の染色体集合格納部は、図７（ｂ）に示すように、１個の染色体格納部は染色体を格納する領域、適応度を格納する領域、選択される確率を格納する領域とから構成する。染色体集合格納手段には最大Ｋβ個の染色体格納部を格納できる。個別の染色体集合格納部はすべて、特徴選択装置１が起動時は空である。
【００３２】
初期染色体集合作成手段３は、以下のようにＡ（１）を設定する。Ｋ個の染色体の各個体の特徴選択ビット列の各ビットの値を一定確率Ｐｆ０で「０」に、１−Ｐｆ０で「１」に設定する。続いて、各個体のサンプル選択ビット列の各ビットの値を一定確率Ｐｐ０で「０」に、１−Ｐｐ０で「１」に設定し、それらの個体をすべてＡ（１）の要素とする。Ａ（１）の各個体における学習サンプルの識別率Ｐαを適応度とし、その降順にＡ（１）の個体を並び替える（ステップＳ２）。そして、各順位の染色体が選択される確率を選択確率値算出手段５により算出し、全世代染色体集合格納手段４の選択確率を格納する領域に書き込む。
【００３３】
ここで、選択確率値算出手段５の動作を説明する。選択確率値算出手段５は、第ｒ位の染色体が選択される確率値ＰＳ（ｒ）を（８）式で算出する。
【数８】
2012238075.tif 000010
上式においてＭａｘは２変数の中の最大値を出力する関数である。
【００３４】
次に、初期染色体集合作成手段３の動作完了後、個別世代実行部７の動作に移る。全体制御手段２は、まず世代数カウンタ６に格納されたＧＮの値に１を加算する（ステップＳ３）。そして、全体制御手段２は交叉実行手段７１に実行を指示する。交叉実行手段７１は、Ａ（ＧＮ−１）から個別の染色体格納部の選択確率の領域に書かれた確率値によりランダムに個別の染色体格納部のペアを選び、それらから２つの染色体を複製し、複製した染色体のペアを用いて交叉を行って新たに２つの染色体を生成し、それらを染色体評価手段８に送って各々の適応度ψを算出させ、適応度の値とともに染色体をＡ（ＧＮ）に追加する。
【００３５】
この処理をＫ１／２回繰り返すことでＫ１個の個体が生成されＡ（ＧＮ）の要素とする（ステップＳ４）。交叉は二点交叉とし、染色体のサンプル選択ビット列と特徴選択ビット列のそれぞれに対して独立に行なう。これは、染色体全体に単純に交叉を適用すると、両ビット列の一方のみに交叉が施され、両者の同時選択が実行できない恐れがあるからである。
【００３６】
次に、全体制御手段２は突然変異実行手段７２に実行を指示する。突然変異実行手段７２は、Ａ（ＧＮ−１）から個別の染色体格納部の選択確率の領域に書かれた確率値によりランダムに１個の染色体格納部を選んで複製を行い、複製した染色体に対して一定確率で染色体のビット列を反転しＡ（ＧＮ）の要素とする（ステップＳ５）。この処理をＫ２回繰り返すことで、Ａ（ＧＮ）にはＫ２個の個体が追加される。特徴選択ビット列とサンプル選択ビット列のビットを反転させる確率はそれぞれＰｆｍ，Ｐｐｍとする。
【００３７】
次に、全体制御手段２は、複製実行手段７３に実行を指示する。複製実行手段７３は、Ａ（ＧＮ−１）から個別の染色体格納部の選択確率の領域に書かれた確率値によりランダムにＫ３個の染色体格納部を選び、各々の染色体と適応度をＡ（ＧＮ）に追加する（ステップＳ６）。以上の中で、Ｋ１、Ｋ２、Ｋ３の合計はｋβに等しい値とする。最後に、全体制御手段２は染色体集合並べ替え手段７４に実行を指示する。染色体集合並べ替え手段７４は、Ａ（ＧＮ）の各個体を適応度の大きさの降順に並べ替える（ステップＳ７）。以上が１つの世代のＧＡの処理である。
【００３８】
そして、ＧＮ＝ＧＮｍａｘであるか否かを判定し（ステップＳ８）、ＧＮ＝ＧＮｍａｘであればそこで動作を完了して、Ａ（ＧＮｍａｘ）の第１位の染色体格納手段の染色体を取り出して最終結果として出力する。ＧＮ＝ＧＮｍａｘでなければ、ステップＳ３に戻って処理を繰り返す。
【００３９】
以上説明したように、ＧＡを用いた特徴選択において、染色体の適応度として線形ＳＶＭのソフトマージンをベースとする評価尺度を用いているため、線形ＳＶＭと同様に汎化能力の高い特徴選択を行うことができる。
【００４０】
なお、図１における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより特徴選択処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００４１】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【産業上の利用可能性】
【００４２】
遺伝的アルゴリズムを用いて、特徴を選択することによりパターン認識の識別精度を向上させることが不可欠な用途に適用できる。
【符号の説明】
【００４３】
１・・・特徴選択装置、２・・・全体制御手段、３・・・初期染色体集合作成手段、４・・・全世代染色体集合格納手段、５・・・選択確率値算出手段、６・・・世代数カウンタ、７・・・個別世代実行部、７１・・・交叉実行手段、７２・・・突然変異実行手段、７３・・・複製実行手段、７４・・・染色体集合並べ替え手段、８・・・染色体評価手段
【図１】
2012238075.tif 000011
【図２】
2012238075.tif 000012
【図３】
2012238075.tif 000013
【図４】
2012238075.tif 000014
【図５】
2012238075.tif 000015
【図６】
2012238075.tif 000016
【図７】
2012238075.tif 000017