(57)【要約】【課題】識別率を最大化しつつ、次元数を最小化する識別因子のセットを選択することができる識別因子選択装置を提供すること。【解決手段】サンプルがいずれのグループに属するかを識別するための複数の識別因子のうち、識別に用いる識別因子のセットを示す情報を染色体とし、該染色体が示す識別因子を用いて識別を行ったときの識別率を適応度とし、遺伝的アルゴリズムを用いて識別率を最大化する識別因子のセットを探索する第１の探索部と、第１の探索部が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、用いる識別因子の数を適応度として遺伝的アルゴリズムを用いて、用いる識別因子の数を最小化する識別因子のセットを探索する第２の探索部とを具備することを特徴とする。【選択図】図１
2013003672.tif 000002
【特許請求の範囲】
【請求項１】
サンプルがいずれのグループに属するかを識別するための複数の識別因子のうち、識別に用いる識別因子のセットを示す情報を染色体とし、該染色体が示す識別因子を用いて識別を行ったときの識別率を適応度とし、遺伝的アルゴリズムを用いて前記識別率を最大化する識別因子のセットを探索する第１の探索部と、
前記第１の探索部が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、用いる識別因子の数を適応度として遺伝的アルゴリズムを用いて、前記用いる識別因子の数を最小化する識別因子のセットを探索する第２の探索部と
を具備することを特徴とする識別因子選択装置。
【請求項２】
前記第２の探索部における遺伝的アルゴリズムでは、前の世代の染色体と、前記全ての識別因子を用いないことを示す染色体とを交叉させて、次の世代の染色体を生成することを特徴とする請求項１に記載の識別因子選択装置。
【請求項３】
前記第２の探索部は、前記交叉により生成した染色体のうち、前記第１の探索部が探索した識別因子のセットを用いたときの識別率に応じた条件を満たす染色体を、次の世代の染色体とすることを特徴とする請求項２に記載の識別因子選択装置。
【請求項４】
複数の前記サンプルについて、各識別因子の値と、属するグループを示す情報とを記憶する記憶部と、
前記記憶部が記憶する情報を用いて、指定された識別因子のセットを用いたときの識別率を算出する染色体評価部と
を具備し、
前記第１の探索部および前記第２の探索部における遺伝的アルゴリズムを用いた探索は、前記染色体評価部を用いて行うこと
を特徴とする請求項１に記載の識別因子選択装置。
【請求項５】
識別因子選択装置における識別因子選択方法であって、
前記識別因子選択装置が、サンプルがいずれのグループに属するかを識別するための複数の識別因子のうち、識別に用いる識別因子のセットを示す情報を染色体とし、該染色体が示す識別因子を用いて識別を行ったときの識別率を適応度とし、遺伝的アルゴリズムを用いて、識別率を最大化する識別因子のセットを探索する第１の探索過程と、
前記識別因子選択装置が、前記第１の探索部が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、用いる識別因子の数を適応度として遺伝的アルゴリズムを用いて、用いる識別因子の数を最小化する識別因子のセットを探索する第２の探索過程と
を有することを特徴とする識別因子選択方法。
【請求項６】
前記第２の探索過程における遺伝的アルゴリズムでは、前の世代の染色体と、前記全ての識別因子を用いないことを示す染色体とを交叉させて、次の世代の染色体を生成することを特徴とする請求項５に記載の識別因子選択方法。
【請求項７】
前記第２の探索過程において、前記交叉により生成した染色体のうち、前記第１の探索部が探索した識別因子のセットを用いたときの識別率に応じた条件を満たす染色体を、次の世代の染色体とすることを特徴とする請求項６に記載の識別因子選択方法。
【請求項８】
複数の前記サンプルについて、各識別因子の値と、属するグループを示す情報とを記憶する記憶部が記憶する情報を用いて、指定された識別因子のセットを用いたときの識別率を算出する染色体評価過程
を有し、
前記第１の探索過程および前記第２の探索過程における遺伝的アルゴリズムを用いた探索は、前記染色体評価過程を含むこと
を特徴とする請求項５に記載の識別因子選択方法。
【請求項９】
コンピュータに、請求項５から請求項８のいずれか一項に記載の識別因子選択方法を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、識別因子選択装置、識別因子選択方法およびプログラムに関する。
【背景技術】
【０００２】
従来、パターン認識に用いる特徴を、遺伝的アルゴリズム（以降、ＧＡという）を用いて選択する技術がある。より具体的には、学習用の多くのパターンおよび各々の正解カテゴリ情報から構成されるデータベースを用い、特徴の組合せを変化させてデータベースを用いた識別および識別率の集計を繰り返し、識別率や次元数を適応度とする探索をＧＡで行う。
この分野の従来技術は、非特許文献１で示された識別率を最大化する方法と、非特許文献２で示された、すべての特徴を用いた場合と比較して識別率が低下しない範囲で特徴の次元数を最小化する方法がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】浜本義彦、古里眞理、金山知余、富田眞吾、“遺伝的アルゴリズムを用いた特徴選択法”、信学論(A)、vol.J78-A,no.10、pp.1385-1389(1995).
【非特許文献２】木村義政、鈴木章、小高和己、“遺伝的アルゴリズムを用いた類似文字識別のための特徴選択”、画電学誌、vol.40,no.1、pp.200- 207(2011).
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１の技術においては、識別率を最大化する特徴のセットを選択することができるものの、次元数の最小化はされていないという問題がある。また、非特許文献２の技術においては、すべての特徴を用いた場合と比較して識別率が低下しない範囲で特徴の次元数を最小化することができるものの、識別率の最大化は行われないという問題がある。
【０００５】
本発明は、このような事情に鑑みてなされたもので、その目的は、識別率を最大化しつつ、次元数を最小化する識別因子のセットを選択することができる識別因子選択装置、識別因子選択方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
（１）この発明は上述した課題を解決するためになされたもので、本発明の一態様は、サンプルがいずれのグループに属するかを識別するための複数の識別因子のうち、識別に用いる識別因子のセットを示す情報を染色体とし、該染色体が示す識別因子を用いて識別を行ったときの識別率を適応度とし、遺伝的アルゴリズムを用いて前記識別率を最大化する識別因子のセットを探索する第１の探索部と、前記第１の探索部が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、用いる識別因子の数を適応度として遺伝的アルゴリズムを用いて、前記用いる識別因子の数を最小化する識別因子のセットを探索する第２の探索部とを具備することを特徴とする識別因子選択装置である。
【０００７】
（２）また、本発明の他の態様は、上述の識別因子選択装置であって、前記第２の探索部における遺伝的アルゴリズムでは、前の世代の染色体と、前記全ての識別因子を用いないことを示す染色体とを交叉させて、次の世代の染色体を生成することを特徴とする。
【０００８】
（３）また、本発明の他の態様は、上述の識別因子選択装置であって、前記第２の探索部は、前記交叉により生成した染色体のうち、前記第１の探索部が探索した識別因子のセットを用いたときの識別率に応じた条件を満たす染色体を、次の世代の染色体とすることを特徴とする。
【０００９】
（４）また、本発明の他の態様は、上述の識別因子選択装置であって、複数の前記サンプルについて、各識別因子の値と、属するグループを示す情報とを記憶する記憶部と、前記記憶部が記憶する情報を用いて、指定された識別因子のセットを用いたときの識別率を算出する染色体評価部とを具備し、前記第１の探索部および前記第２の探索部における遺伝的アルゴリズムを用いた探索は、前記染色体評価部を用いて行うことを特徴とする。
【００１０】
（５）また、本発明の他の態様は、識別因子選択装置における識別因子選択方法であって、前記識別因子選択装置が、サンプルがいずれのグループに属するかを識別するための複数の識別因子のうち、識別に用いる識別因子のセットを示す情報を染色体とし、該染色体が示す識別因子を用いて識別を行ったときの識別率を適応度とし、遺伝的アルゴリズムを用いて、識別率を最大化する識別因子のセットを探索する第１の探索過程と、前記識別因子選択装置が、前記第１の探索部が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、用いる識別因子の数を適応度として遺伝的アルゴリズムを用いて、用いる識別因子の数を最小化する識別因子のセットを探索する第２の探索過程とを有することを特徴とする識別因子選択方法である。
【００１１】
（６）また、本発明の他の態様は、上述の識別因子選択方法であって、前記第２の探索過程における遺伝的アルゴリズムでは、前の世代の染色体と、前記全ての識別因子を用いないことを示す染色体とを交叉させて、次の世代の染色体を生成することを特徴とする。
【００１２】
（７）また、本発明の他の態様は、上述の識別因子選択方法であって、前記第２の探索過程において、前記交叉により生成した染色体のうち、前記第１の探索部が探索した識別因子のセットを用いたときの識別率に応じた条件を満たす染色体を、次の世代の染色体とすることを特徴とする。
【００１３】
（８）また、本発明の他の態様は、上述の識別因子選択方法であって、複数の前記サンプルについて、各識別因子の値と、属するグループを示す情報とを記憶する記憶部が記憶する情報を用いて、指定された識別因子のセットを用いたときの識別率を算出する染色体評価過程を有し、前記第１の探索過程および前記第２の探索過程における遺伝的アルゴリズムを用いた探索は、前記染色体評価過程を含むことを特徴とする。
【００１４】
（９）また、本発明の他の態様は、コンピュータに、上述の（５）から（８）のいずれか一項に記載の識別因子選択方法を実行させるためのプログラムである。
【発明の効果】
【００１５】
この発明によれば、識別率を最大化しつつ、次元数を最小化する識別因子のセットを選択することができる。
【図面の簡単な説明】
【００１６】
【図１】この発明の一実施形態による特徴選択装置１０の構成を示す概略ブロック図である。
【図２】同実施形態における染色体を説明する概念図である。
【図３】同実施形態における染色体集合記憶部７０が記憶する染色体集合の構成を示す図である。
【図４】同実施形態における識別率最大化探索部５０の動作を説明するフローチャートである。
【図５】同実施形態における次元数最小化探索部６０を動作するフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して、本発明の実施の形態について説明する。図１は、この発明の一実施形態による特徴選択装置１０の構成を示す概略ブロック図である。本実施形態における識別因子選択装置である特徴選択装置１００は、画像のパターン認識を行う際に用いる、画像の特徴（識別因子）を選択する。すなわち、特徴選択装置１００は、サンプル画像がいずれのグループに属するかを識別するための複数の識別因子のうち、識別率を最大化しつつ、次元数（使用する識別因子の数）を最小化するような識別因子のセットを選択する。識別因子選択装置１００は、学習パターン集合記憶部１０、標準パターン作成部２０、標準パターン記憶部３０、染色体評価部４０、識別率最大化探索部５０、次元数最小化探索部６０、染色体集合記憶部７０、選択結果出力部８０を含んで構成される。
【００１８】
学習パターン集合記憶部１０は、学習パターン（学習サンプル）の特徴の集合（特徴ベクトル）を記憶する。特徴の次元数をＬ、識別対象とするカテゴリー数をＨ、各カテゴリーをＣ１、Ｃ２、・・・ＣＨと表記する。学習パターンの数、すなわち学習サンプル数をＮ、第ｉ学習サンプルの特徴ベクトルをＶｉ＝（Ｖｉ１、Ｖｉ２、・・・ＶｉＬ）と表記する。また、学習サンプルの集合をψで表わす。ここで、Ｖｉｊは、第ｉ学習サンプルのｊ番目の特徴の特徴量を示す。
学習パターン集合記憶部１０（記憶部）は、各学習サンプルの特徴ベクトルＶｉと、その学習サンプルが属するカテゴリー名Ｃ（Ｖｉ）とを対応づけて記憶している。すなわち、学習パターン集合記憶部１０は、各識別因子の値と、属するグループを示す情報とを記憶する。学習パターン集合記憶部１０が記憶する、これらの情報は、標準パターン作成部２０および染色体評価部４０に対して提供される。なお、本実施形態では、学習パターン集合記憶部１０は、学習パターンの特徴ベクトルを記憶するとして説明したが、学習パターンの画像を記憶しておき、該画像から特徴ベクトルの各値を算出するようにしてもよい。
【００１９】
標準パターン作成部２０は、カテゴリー毎に、該カテゴリーに属する学習パターンの特徴量の平均値をとり、それらの値からなる特徴ベクトルを該カテゴリーの標準パターンとする。具体的には、標準パターン作成部２０は、以下の式（１）を用いて、学習パターン集合記憶部１０が記憶する学習パターンの集合ψから、各カテゴリーＣｋ（ｋ＝１、２、・・・Ｈ）の標準パターンＷｋ＝（Ｗｋ１、Ｗｋ２、・・・ＷｋＬ）を算出し、標準パターン記憶部３０に記憶させる。なお、学習サンプルの集合ψのｉ番目のサンプルＶｉにおけるｊ次元目の特徴量をＶｉｊ、Ｖｉが属するカテゴリーをＣ（Ｖｉ）とする。式（１）におけるδは、クロネッカーのデルタである。
【００２０】
【数１】
2013003672.tif 000003
【００２１】
標準パターン記憶部３０は、各カテゴリーＣｋに対応付けて、該カテゴリーの標準パターンＷｋを記憶する。カテゴリーＣｋの標準パターンＷｋは、上述したように、カテゴリーＣｋに属する学習パターンの特徴毎に特徴量の平均をとった値を要素とする特徴ベクトルである。
【００２２】
染色体評価部４０は、指定された染色体が示す特徴を識別に用いて、学習パターン集合記憶部１０が記憶する各学習パターンがいずれのカテゴリーに入るかを識別し、その識別結果の正答率である識別率を算出する。ここで、染色体とは、各特徴を、識別に用いるか否かを示す情報である。すなわち、識別に用いる識別因子のセットを示す情報である。また、染色体評価部４０は、指定された染色体の非選択次元数を算出する。
【００２３】
識別率最大化探索部５０（第１の探索部）は、染色体の適応度として識別率を用いて、ＧＡにより、識別率を最大化する識別因子のセットを探索する。次元数最小化探索部６０（第２の探索部）は、染色体の適応度として識別率と非選択次元数を組み合わせて用いて、ＧＡにより、識別率最大化探索部５０により得られた識別率を保ちつつ次元数を最小化する識別因子の組み合わせを探索する。次元数最小化探索部６０は、識別率最大化探索部５０が探索した識別因子のセットを示す染色体と、全ての識別因子を用いないことを示す染色体とを用い、非選択次元数を適応度として遺伝的アルゴリズムを用いて、用いる識別因子の数を最小化する識別因子のセットを探索する。ここで、非選択次元数とは、その染色体で選択されていない特徴の数のことである。なお、非選択次元数を適応度とすることは、用いる識別因子の数が小さいほど適応度が高い、適応度とすることに相当する。また、識別率最大化探索部５０および次元数最小化探索部６０は、探索を行う際に、各染色体を染色体評価部４０に指定して、該染色体を評価する。
【００２４】
染色体集合記憶部７０は、識別率最大化探索部５０および次元数最小化探索部６０が生成する各世代の染色体を記憶する。選択結果出力部８０は、次元数最小化探索部６０の探索結果、すなわち識別率が最大であり、かつ、次元数が最小である識別因子の組み合わせを示す情報を出力する。この出力は、表示デバイスによる表示や、印刷デバイスによる紙への印字、通信デバイスによるデータの出力などのいずれであってもよい。
【００２５】
図２は、本実施形態における染色体を説明する概念図である。染色体は、特徴を選択するビット列である。このビット列のビット数は特徴ベクトルの次元数Ｌであり、図２はＬ = 7の場合の例である。このビット列は各ビットが対応する特徴を、識別因子として使用するか否かを示しており、“１”が「使用する」、“０”が「使用しない」を表わす。図２に示す染色体“０１０１００１”の場合、７個の特徴のうち、破線で示された２、４、７番目の３つの特徴の値（特徴量）が使用される。図２にはカテゴリーがＣ１の学習パターンＶ１、Ｖ２と、カテゴリーがＣ２の学習パターンＶ３、Ｖ４とについて、染色体が“０１０１００１”であるときに識別因子として使用される特徴量を、破線で囲んでいる。
【００２６】
すなわｔ、学習パターンＶ１“８２１３５２７”のうち、２、４、７番目の特徴量である“２”、“３”、“７”が識別因子として用いられる。同様に、学習パターンＶ２“７１２２６３６”のうち、２、４、７番目の特徴量である“１”、“２”、“６”が識別因子として用いられる。学習パターンＶ３“８３６８２１３”のうち、２、４、７番目の特徴量である“３”、“８”、“３”が識別因子として用いられる。学習パターンＶ４“９２７９１２１”のうち、２、４、７番目の特徴量である“２”、“９”、“１”が識別因子として用いられる。また、染色体のビット列は記号β１、β２、・・・βＬで表わされる。
【００２７】
図３は、染色体集合記憶部７０が記憶する染色体集合の構成を示す図である。染色体は、ＧＡの１つの世代（ＧＮで表す）に対応してＫ個生成される。１つの世代ＧＮの染色体集合をＡ（ＧＮ）で表す。染色体集合記憶部７０は、識別率最大化探索部５０および次元数最小化探索部６０が生成した全世代（０世代からＧＮｅ２世代）の染色体集合Ａ（０）、Ａ（１）、・・・Ａ（ＧＮｅ２）を記憶する。１つのＧＮ世代に対応する染色体集合Ａ（ＧＮ）にはＫ個の染色体が、各々の適応度の値とともに格納され、ＧＮは０からＧＮｅ２までである。
【００２８】
次に、染色体評価部４０の詳細について説明する。染色体評価部４０は、識別率最大化探索部５０または次元数最小化探索部６０から１個の染色体を与えられると、識別率Ｐα と非選択次元数Ｒαを以下のように算出する。
【００２９】
（１）識別率Ｐαの算出
識別手法には公知の種々の方法があり、いずれの方法を用いてもよい。本実施形態の染色体評価部４０は、入力パターンと各カテゴリーの標準パターンとのユークリッド距離の中で、最小値をとる標準パターンに対応するカテゴリーを識別結果とする、最小距離識別を用いる。
【００３０】
染色体評価部４０は、標準パターン記憶部２０に格納されている標準パターンＷｋ＝  （Ｗｋ１，Ｗｋ２，・・・ＷｋＬ）を用いて学習パターン集合記憶部１０に格納されている集合ψに属する学習サンプル各々について識別を行う。具体的には、まず、染色体評価部４０は、学習サンプルの特徴ベクトルＸ＝（Ｘ１，Ｘ２，・・・ＸＬ）と、各カテゴリーＣｋの標準パターンＷｋとの距離Ｄｋを式（２）を用いて算出する。式（２）の右辺は染色体のビット列によって選択された特徴のみを用いて算出したユークリッド距離である。
【００３１】
【数２】
2013003672.tif 000004
【００３２】
染色体評価部４０は、算出した距離Ｄ１、Ｄ２、・・・ＤＨの中で最小の距離に対応するカテゴリーを識別結果とする。
そして、染色体評価部４０は、学習サンプルの集合ψにおいて正しく識別されたパターン数をＮｃとして、識別率Ｐαを式（３）を用いて算出する。
【００３３】
【数３】
2013003672.tif 000005
【００３４】
（２）  非選択次元数Ｒαの算出
また、染色体評価部４０は、非選択次元数Ｒαを、式（４）を用いて算出する。なお、式（４）で示すように、非選択次元数Ｒαは、識別因子としてもちいられていない特徴の数である。したがって、非選択次元数Ｒαの値が大きいほど、小さな次元数が達成されていることを表す。
【００３５】
【数４】
2013003672.tif 000006
【００３６】
図４は、識別率最大化探索部５０の動作を説明するフローチャートである。ここではＧＡが用いられる。ＧＡの世代数をＧＮと表記する。また、染色体集合記憶部７０が記憶する世代ＧＮにおける染色体集合とその個体数をそれぞれＡ（ＧＮ）、Ｋとし、最大世代数をＧＮe１とする。なお、ここで最大世代数ＧＮe１とは、識別率最大化探索部５０による生成される染色体の世代数の最大値であり、予め設定された数である。すなわち、識別率最大化探索部５０は、世代０から世代ＧＮe１の染色体を生成する。
【００３７】
まず、識別率最大化探索部５０は、世代数ＧＮの初期値を“０”とする（Ｓａ１）。次に、識別率最大化探索部５０は、世代数ＧＮ＝０、すなわち初期の染色体集合Ａ（０）を生成する。具体的には、識別率最大化探索部５０は、Ｋ個の染色体の各個体の各ビットの値を一定確率Ｐｆ０で“０”に、１−Ｐｆ０で“１”に設定し、それらの個体をすべて初期の染色体集合Ａ（０）の要素とする。識別率最大化探索部５０は、初期の染色体集合Ａ（０）に属する各染色体の評価を染色体評価部４０に指示し、その結果に基づき、染色体集合Ａ（０）を適応度の降順にソートする（Ｓａ２）。なお、このときの各染色体の評価は、識別率を適応度とする。また、識別率最大化探索部５０は、ソート結果の染色体とその適応度（識別率）とを対応付けて、染色体集合記憶部７０に記憶させる。
【００３８】
次に、識別率最大化探索部５０は、世代数ＧＮに“１”を足す（Ｓａ３）。識別率最大化探索部５０は、染色体集合Ａ（ＧＮ−１）からＫ１／２組の染色体のペアを取り出して、交叉１の操作を行い、Ｋ１個の染色体を生成し、染色体集合Ａ（ＧＮ）の要素とする（Ｓａ４）。この交叉１の操作の詳細については、後述する。次に、識別率最大化探索部５０は、染色体集合Ａ（ＧＮ−１）からＫ２個の染色体を取り出して、突然変異の操作を行い、Ｋ２個の染色体を生成し、染色体集合Ａ（ＧＮ）の要素とする（Ｓａ５）。
【００３９】
次に、識別率最大化探索部５０は、染色体集合Ａ（ＧＮ）に属する各染色体の評価を染色体評価部４０に指示し、その結果に基づき、染色体集合Ａ（ＧＮ）を適応度の降順にソートする（Ｓａ６）。なお、このときの各染色体の評価も、識別率を適応度とする。また、識別率最大化探索部５０は、ソート結果の染色体とその適応度（識別率）とを対応付けて、染色体集合記憶部７０に記憶させる。そして、識別率最大化探索部５０は、世代数ＧＮが最大世代数ＧＮe１以上であるか否かを判定する（Ｓａ７）。世代数ＧＮが最大世代数ＧＮe１以上でないときは（Ｓａ７−Ｎｏ）、ステップＳａ３に戻って、処理を繰り返す。また、世代数ＧＮが最大世代数ＧＮe１以上であるときは（Ｓａ７−Ｙｅｓ）、処理を終了する。
【００４０】
なお、ステップＳａ４、Ｓａ５の処理により作成される染色体の個体数は、各々Ｋ１個、Ｋ２個であり、Ｋ１とＫ２は、これらの合計がＫとなるように予め設定しておく。最大世代数ＧＮｅ１の処理が完了した後は、最終世代のＡ（ＧＮｅ１）の１位の個体の適応度である識別率を基準識別率Ｐα０として次元数最小化探索部６０に渡す。そしてＡ（ＧＮｅ１）の１位の個体によりＡ（ＧＮｅ１）のすべての要素を置き換える処理を行い、次元数最小化探索部６０に渡す。この渡されたＡ（ＧＮｅ１）が後段の処理の初期染色体集合となる。１位の個体だけでＡ（ＧＮｅ１）を構成するのは、次元数最小化探索部６０の探索処理において、一般のＧＡとは異なり初期染色体集合の多様性にまったく頼らないことを意味する。
【００４１】
（１）交叉１
上述のステップＳａ４における交叉１の処理について説明する。交叉１において染色体が選択される確率は適応度の順位によって決まり、適応度が高いほど選択される確率も高い。ここでは、識別率最大化探索部５０は、適応度の大きさが第ｎ位の個体が選択される確率ＰＳ（ｎ）を、式（５）により算出する。
【００４２】
【数５】
2013003672.tif 000007
【００４３】
式（５）において、Ｍａｘ（ｘ，ｙ）は２変数の中の最大値を出力する関数である。また、μとσは実験的に決める定数であり０≦μ≦１、０≦σ≦１である。式（５）におけるμｎは、染色体の適応度の順位降下に伴い一定の比率μで選択の確率を低減するものである。また、σは順位の低い染色体に対しても最低限である一定の確率を与える作用を持つ。識別率最大化探索部５０は、処理対象となる染色体を式（５）の確率で無作為に選択する。識別率最大化探索部５０は、このようにして染色体集合Ａ（ＧＮ−１）から染色体のペアを選択し、選択したペアで交叉を行なうことで２つの染色体を作成する。
【００４４】
作成した染色体については、染色体評価部４０が、識別率Ｐαを式（３）により算出して適応度とする。そして、識別率最大化探索部５０は、これらの染色体と適応度とを、Ａ（ＧＮ）の要素とする。この処理をＫ１／２回繰り返すことでＫ１個の個体が生成され、Ａ（ＧＮ）の要素とされる。なお、交叉の方法としては、交叉点をランダムで２つ選び、２つの交叉点に挟まれている部分を入れ換える、二点交叉を用いる。
【００４５】
（２）突然変異
上述のステップＳａ５における突然変異の処理について説明する。識別率最大化探索部５０は、Ａ（ＧＮ−１）から１個の染色体を式（５）の確率で無作為に選択し、一定確率で染色体のビット列を反転して、１つの染色体を作成する。作成した染色体については、染色体評価部４０が、識別率Ｐαを式（３）により算出して適応度とする。そして、識別率最大化探索部５０は、これらの染色体と適応度とを、Ａ（ＧＮ）の要素とする。この処理をＫ２回繰り返す。これにより、Ａ（ＧＮ）の個体数は交叉１で生成されるＫ１個と合わせてＫ１＋Ｋ２＝Ｋ個となる。ここでビットを反転させる確率はＰｆｍとする。
【００４６】
図５は、次元数最小化探索部６０を動作するフローチャートである。ＧＡの世代数は、前段（識別率最大化探索部５０）と同じくＧＮで表し、世代数ＧＮにおける染色体集合も前段と同じくＡ（ＧＮ）で表し、各世代における染色体集合の個体数は前段と同じＫとする。また、この処理での最大世代数はＧＮｅ２で表わす。
【００４７】
まず、次元数最小化探索部６０は、ＧＮの初期値を、前段の最大世代数ＧＮｅ１とする（Ｓｂ１）。次に、次元数最小化探索部６０は、前段の探索から受け取ったＡ（ＧＮｅ１）の１位の個体を、Ｋ個に複製する。次元数最小化探索部６０は、このＫ個に複製した染色体の集合を、染色体集合Ａ（ＧＮｅ１）とする（Ｓｂ２）。次元数最小化探索部６０は、染色体集合Ａ（ＧＮｅ１）を染色体集合記憶部７０に記憶させる。
【００４８】
次に、次元数最小化探索部６０は、世代数ＧＮに“１”を足す（Ｓｂ３）。そして、次元数最小化探索部６０は、染色体集合Ａ（ＧＮ−１）から染色体を取り出して、ヌル染色体との間で、交叉２の操作を行い、Ｋ３個の染色体を生成し、染色体集合Ａ（ＧＮ）の要素とする。この交叉２の操作の詳細については、後述する。なお、ヌル染色体とは、全てのビットが“０”、すなわち全ての特徴を識別に用いないことを示す染色体である。さらに、次元数最小化探索部６０は、染色体集合Ａ（ＧＮ−１）からＫ４個の染色体を取り出して、複製し染色体集合Ａ（ＧＮ）の要素とする（Ｓｂ４）。
【００４９】
次に、次元数最小化探索部６０は、染色体集合Ａ（ＧＮ）に属する各染色体の評価を染色体評価部４０に指示し、その結果に基づき、染色体集合Ａ（ＧＮ）を非選択次元数の降順にソートする（Ｓｂ５）。なお、このときの各染色体の評価は、識別率と非選択次元数とを適応度とする。また、次元数最小化探索部６０は、ソート結果の染色体とその適応度とを対応付けて、染色体集合記憶部７０に記憶させる。そして、次元数最小化探索部６０は、世代数ＧＮが最大世代数ＧＮe２以上であるか否かを判定する（Ｓｂ６）。世代数ＧＮが最大世代数ＧＮe２以上でないときは（Ｓｂ６−Ｎｏ）、ステップＳｂ３に戻って、処理を繰り返す。また、世代数ＧＮが最大世代数ＧＮe２以上であるときは（Ｓｂ６−Ｙｅｓ）、処理を終了する。
【００５０】
なお、ステップＳｂ４の交叉２と複製の処理により作成される染色体の個数は、各々Ｋ３個とＫ４個であり、Ｋ３とＫ４は、これらの合計がＫとなるように予め設定しておく。そして最大世代数ＧＮｅ２までが完了したのち、Ａ（ＧＮｅ２）の第１位の染色体を最終結果として、選択結果出力部８０に出力する。
【００５１】
（１）交叉２
上述のステップＳｂ４における交叉２の処理について説明する。本処理では、特別な染色体としてすべてのビットを”０”とした染色体（ヌル染色体）を用いる。これをλ０で表す。交叉２では、ひとつの世代数ＧＮに対して以下の（ａ）〜（ｇ）の処理をＡ（ＧＮ）  の要素数がＫ３に達するまで繰り返し行う。
（ａ）次元数最小化探索部６０は、２つの染色体をＡ（ＧＮ−１）から式（５）の確率で無作為に選択する。これらの染色体を、λ１とλ２とする。
（ｂ）次元数最小化探索部６０は、一定の確率Ｐｈでλ１、λ２の片側の染色体をヌル染色体λ０で置き変える。
（ｃ）次元数最小化探索部６０は、λ１、λ２から二点交叉により、新たな染色体λ１’、λ２’を生成する。
【００５２】
（ｄ）次元数最小化探索部６０は、染色体λ１’、λ２’の評価を、染色体評価部４０に指示する。染色体評価部４０は、染色体λ１’、λ２’の識別率Ｐα１、Ｐα２を式（３）により算出する。
（ｅ）染色体評価部４０は、染色体λ１’、λ２’を用いたときの非選択次元数Ｒα１、Ｒα２を、式（４）により算出し適応度とする。
（ｆ）次元数最小化探索部６０は、Ｐα０≦Ｐα１であればλ１’をＡ（ＧＮ）の新たな要素とする。Ａ（ＧＮ）の要素数がＫ３に達すれば処理を完了する。
（ｇ）次元数最小化探索部６０は、Ｐα０≦Ｐα２であればλ２’をＡ（ＧＮ）の新たな要素とする。Ａ（ＧＮ）の要素数がＫ３に達すれば処理を完了する。
【００５３】
この交叉２の特徴は以下の２点である。１点目の特徴は、上記（ｂ）の処理でヌル染色体を片方の親とする交叉を行うことである。ヌル染色体は次元数が０であり、適応度である非選択次元数Ｒαは理論的な最大値Ｌである。識別能力を持たないためそのままでは使えないが、このヌル染色体の局所的な領域には有効な情報が含まれており、それを取り込むために、ここでは染色体の中の部分ビット列を交換する働きを持つ二点交叉を用いる。２点目の特徴は、（ｆ）と（ｇ）の処理において、交叉により生成した新たな個体を採用する際に識別率を基準識別率Ｐα０を下回らないことをチェックすることである。
【００５４】
（２）複製
上述のステップＳｂ４における複製の処理について説明する。次元数最小化探索部６０は、染色体集合Ａ（ＧＮ−１）から１個の染色体を式（５）の確率で無作為に選択し、そのままＡ（ＧＮ）の要素とする。この処理をＫ４回繰り返す。これにより、染色体集合Ａ（ＧＮ）の個体数は交叉２で生成されるＫ３個と合わせてＫ３＋Ｋ４＝Ｋ個となる。
【００５５】
なお、上述の実施形態において、識別率最大化探索部５０および次元数最小化探索部６０は、それぞれ予め決められた世代数（ＧＮｅ１、ＧＮｅ２）まで、処理を繰り返すとして説明したが、これに限らず、適応度が所定の値以上となるまで、あるいは、適応度の前回値との差分が所定の値以下となるまで処理を繰り返すようにしてもよい。また、識別率最大化探索部５０と次元数最小化探索部６０とにおいて生成する各世代の染色体数を同一の値としたが、異なっていてもよい。
また、上述の実施形態において、パターン認識において、特徴の各々を識別因子として用いるか否かを選択しているが、パターン認識に限らず、その他のものを識別対象とし、識別対象に関する情報の各々を識別因子として用いるか否かを選択するようにしてもよい。
【００５６】
また、上述の実施形態において、交叉２の処理では、識別率が基準識別率以上であることを、次の世代の染色体とする条件としているが、基準識別率に応じた条件を満たすようにすればよく、例えば、基準識別率の所定の割合（例えば９０％）以上であることを条件にしてもよいし、基準識別率から当該識別率を引いた結果が所定の範囲内（例えば５％以上）であることを条件にしてもよい。
【００５７】
以上のように、ＧＡを用いて識別率を最大化する特徴選択を行ってから、その結果を用いてＧＡを用いて次元数を最小化する特徴選択を行う処理をすることで、識別率を最大化しつつ、次元数を最小化することができる。さらに、該処理を行うにあたって、後段のＧＡを用いて次元数を最小化する特徴選択の中で一定の確率で、すべてのビットに「使用しない」を表す値を設定した染色体（ヌル染色体）を片方の親とする交叉を行うことにより、前段から与えられた初期染色体集合に多様性が不足していても、ヌル染色体から有効な情報を得ることで多様性の不足を補い、高速なＧＡによる特徴選択を行うことができる。
【００５８】
また、図１における特徴選択装置１００の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより特徴選択装置１００機能を実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
【００５９】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００６０】
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【００６１】
１００…特徴選択装置
１０…学習パターン集合記憶部
２０…標準パターン作成部
３０…標準パターン記憶部
４０…染色体評価部
５０…識別率最大化探索部
６０…次元数最小化探索部
７０…染色体集合記憶部
８０…選択結果出力部
【図１】
2013003672.tif 000008
【図２】
2013003672.tif 000009
【図３】
2013003672.tif 000010
【図４】
2013003672.tif 000011
【図５】
2013003672.tif 000012