The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
1D3-2
2
クラス分類の為の遺伝的プログラミングを用いた
特徴量変換手法の提案
A method of multiple feature construction for two symbolic classification problems
using Genetic Programming
白石 駿英
∗1 Toshihide SHIRAISHI吉田 倫也
∗1 Tomoya YOSHIDA山本 詩子
∗2 Utako YAMAMOTO廣安 知之
∗2 Tomoyuki HIROYASU∗1
同志社大学大学院生命医科学研究科
Graduate School of Life and Medical Sciences, Doshisha University∗2
同志社大学生命医科学部
Faculty of Life and Medical Sciences, Doshisha University
In this paper, a feature transformation method for two-class classification using genetic programming (GP) is proposed．GP derives a transformation formula to improve the classification accuracy of SVM．In this paper, we propose a weight function to evaluate converted feature space and the proposed function is used as an evaluate function of GP．In the proposed function, the ideal two-class distribution of items is assumed and the distance between the actual and ideal distributions is calculated．The weight is imposed to these distances. To examine the effectiveness of the proposed function, numerical experiment is performed．As the result, the classification accuracy of the proposed method is better than that of the previous method.
1.
はじめに
近年，機械学習による識別問題が盛んに研究されてきた． 機械学習における識別問題に関して，精度の高い識別器を構 築することにより，識別精度を高めるといった報告が多数為 されている[G.E.Hinton 06][V. N. Vapnik 98][F. Otero 03]．
具体的な識別器としてニューラルネットワーク(Neural Net-work:NN)，決定木(Decision Tree)やSVM(Support Vecter Machine)といった精度の高い様々な手法が提案されている．
応用分野としては，金属製品の異常検知問題や癌の腫瘍の良 性・悪性の識別等があり，幅広い分野で識別問題の解決手法と して用いられている．
しかし，より良い識別精度を達成する為には，識別器の判 別の能力だけでなく，識別器が判別する特徴量空間を考慮す る必要がある．データが複雑な特徴量分布を持つ場合，識別 器の識別能力は下がってしまうことが考えられる．また，NN
やSVMではパラメータを変更することにより，最適な識別線
を探索することが可能である．SVMではグリッドサーチによ
り，自動で最適な識別線を求めるパラメータを探索できる[F. Friendrichs 05]．しかし，その探索は関数の種類に制約があり，
柔軟なものであるとは言えない．
そ こ で ，本 稿 で は 識 別 の 精 度 を 高 め る 特 徴 量 空 間 を 構築するアプローチとして遺伝的プログラミング (Ge-netic Programing:GP[Koza 92]) を用いた特徴量変換方法
で あ る GPMFC(Genetic Programing Multiple Feature construction)[Zhang 12]における特徴量変換手法を検討する．
具体的には，与えられた特徴量空間を決定木やルール学習等の 識別器の識別精度を高める目的で新しい空間に演算により変換 する変換式を構築する．その際，GPの遺伝的操作を分類に最
適な特徴量空間を得る為に行う．今回，先行研究で用いられて いる評価関数よりも精度の高い特徴量空間が構築可能である 評価関数を提案した．評価実験により，既存手法と提案手法に よって構築した特徴量空間における識別率を比較した．
連絡先: 白石 駿英，同志社大学大学院生命医科学研究
科，京都府 京田辺市多々羅都谷 1-3，0774-65-6130， [email protected]
2.
GPMFC
GPMFCは最適化手法である遺伝的プログラミング(GP)
を用いて分類最適な特徴量を得る為の変換式を構築する手法 である．また，ユーザは特徴量に関する事前知識に関係なくこ のアルゴリズムにより分類最適な特徴量を得ることができる．
GPMFCではGPの評価，選択，交叉，突然変異といった遺
伝的操作を繰り返し行うことにより特徴量変換式の最適化を図 る．以下にGPMFCのアルゴリズムを示す．
Step.1 初期化(Initialization)
初期個体群として，ランダムに集団数だけの個体（木構 造の変換式）を生成する．
Step.2 評価(Evaluation)
各個体の適合度を評価関数によって計算する．各個体に よる変換式によって特徴量を変換し，変換した特徴量に おいて分布の重なるデータの範囲を求める．この区間に ある特徴量の数を求め，これを評価値とする．遺伝的操 作(選択)の際に評価値が低い木構造程が高い評価となる．
図.1にデータの変換と評価値の概要図を示す．
図1: 変換式の評価
また，図.2に特徴量変換後のヒストグラムのイメージ図
を示す．評価関数はこの図のように視覚的に見ると，2ク
ラス分布が両側に分かれているものを評価する．
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
図2: 1次元特徴量ヒストグラム
Step.3 選択(Selection)
集団の中から適合度を基準として， 次世代に残す個体を 集団数だけ選択する．
Step.4 交叉(Crossover)
集団の中からランダムに選択した2個体を対象とし，そ
れぞれランダムに交叉点を選んだ後，枝を差し替え交配 する．
Step.5 突然変異(Mutation)
対象となる個体からランダムに突然変異点を選択し，突 然変異点以降の木をランダムに作成した突然変異木と入 れ替える．
Step.6 終了条件(Terminal Criterion)
予め決めておいた終了条件に到達するまでStep 2∼Step 5を繰り返す．主な終了条件として探索世代数や目的の
個体に達したか否かなどが挙げられる．GPMFCでは評
価値が0となり，データの属性が完全に分離することを
目的として最適化を行う．
3.
属性の分布を考慮した評価関数の検討
3.1
先行研究の評価関数における問題点
前章の先行研究におけるGPMFCの評価関数には問題点が
存在する．それは，1次元に変換した特徴量平面において，2
クラス分布が重なる領域での頻度のみを考慮することである． 図.2のような2クラスの重なりを表す領域の中の分布の善し
悪しを既存手法では評価することができない，その為，識別を 向上させる平面を得ることができるとは限らず，既存手法は最 適な評価関数とは言えない．ここで，図.3に2クラス分類精
度の低くなる平面と精度の高くなる平面について示す．右側の 図のような特徴量分布を持つ平面がより良い評価を受けるよう に評価関数を考慮する必要がある．
: 1
: 2
図3: 1次元2クラス分布の比較
このように2クラス分布の重なる領域において，識別に不
利な平面は2クラスデータが交互に配置される場合である．そ
れに対して，識別に有利な平面では2クラスデータは分離中
心を境としてある程度局在するように分布することが考えられ る．そこで，本稿では理想的な2クラス分布を仮定し，実際
に得られる特徴量分布との誤差をペナルティーとして評価する 評価関数を提案する．次章でその評価手法について述べる．
3.2
提案手法
GPMFCの特徴量変換における評価方法として，事前に理
想的な2クラス分布に対する知識を与えるような方法を提案
する．この手法ではまず，理想的な1次元データに変換され
る特徴量の分布をその値の大きさの順位の大小によって決定す る．次に，1次元特徴量変換データをソートして，変換データ
と理想的なデータの属性を比較する．属性に誤りが生じた場合 はそのデータの位置を考慮したペナルティー(重み)を付加す
る．重みは2つの属性の分離中心から離れるほど重く設定す
ることにより，2つの理想的な属性の分離状態により近くする
ことが可能となる．図.4に評価関数の概要図を示す．この図で
は，両属性に2次の重み関数を設定した場合について示して
いる．次章の評価実験においても同様に，2次の重み関数を用
いている．
:
1
:
図4: 重み関数概要図
4.
評価実験
提案手法と先行研究の手法を比較する評価実験を行い，提 案手法の評価関数の有効性を評価する．また，変換前のデータ よりも識別結果が向上するかも併せて評価を行う．
4.1
実験方法
実験では学習データとしてBreast Cancer Wisconsinの乳
癌データ[Merz C.J. 98](データ数420)を用いる．また，識別
の検証には5fold-crossvalidationを用い，学習データを336
サンプルと未学習データを84サンプルとする．変換したデー
タをSVMを用いて識別し，識別結果を上記の2つの手法に
ついて比較する．また，得られた特徴量平面がどのような分布 を持つかも併せて比較する．
4.2
実験パラメーター
表1に今回の実験で用いるGPのパラメータを示す．この
パラメータは提案手法と先行研究の手法において共通である．
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
表1: GPのパラメータ
パラメータ 値
個体数 1000
世代数 100
交叉率 0.6
突然変異率 0.3
特徴量数 3
関数ノードの種類 ＋，−，×，÷ 交叉方法 一点交叉 選択方法 トーナメント選択
4.3
実験結果
図.7に提案手法と先行研究の手法において，識別率の比較
を行った結果を示す．なお，この実験では提案手法と既存手法 の比較をしやすくする為に識別率の低いデータを用いた．その 為，前述のBreast Cancer Wisconsinの乳癌データから特に
識別率の低い特徴量を3種類抽出した．このデータのSVMに
よる識別率はRBFカーネルを用い70.95%である．まず，実
際にデータを変換した際の一次元の特徴量分布を，図.5に既
存手法，図.6に提案手法について示す．既存手法においては
データの分布が重なる領域において，2つのクラス分布が入り
交じっているが，提案手法においては，2クラスの領域がある
程度分かれた分布を得た．
図5: 特徴量ヒストグラム(既存手法)
図6: 特徴量ヒストグラム(提案手法)
次に，識別率について示す．識別率はGPMFC10試行の平均
値を算出して示した．提案手法による平均の識別率は73.34%と
なり，従来手法の平均識別率65.58%を上回り，かつ変換前よ
りも2.39%識別率が向上した．この結果により提案手法の有
効性が示唆された．
40 50 60 70 80 90
(%
)
図7: 識別率の比較(10試行平均)
5.
まとめ
今回の実験から，GPMFCの評価関数には単純な分布を考
慮する手法よりも，事前知識を含む評価関数が適していること が示された．しかし，学習サンプル数が同数必要であるなどの 課題を解決する必要がある．また，多クラスの分類問題につい て，GPMFCを用いた特徴量変換手法を検討する必要がある．
一方で，この手法がどの種類の識別器と相性が良いのかとい うことも検討項目として挙げられる．今回は２クラス分類にお いて精度の高いSVMを選んだが，今後はNNや決定木にお
いて，この手法を適応し，精度の比較検討を行っていく．
参考文献
[G.E.Hinton 06] G.E.Hinton and R.R. Salakhutdinov. Re-ducing the Dimensionality of Data with Neural Net-works. Science, Vol. 313, No. 5786, pp. 504-507, 2006.
[V. N. Vapnik 98] V. N. Vapnik. Statistical Learning The-ory. Wiley, 1998.
[F. Otero 03] F. Otero, M. Silva, A. Freitas, and J. Nievola, Genetic programming for attribute construction in data mining, in Genetic Programming (Lecture Notes in Computer Science, vol. 2610.) Berlin, Germany: Springer, 2003, pp. 101-121.
[F. Friendrichs 05] Frauke Friedrichs and Christian, Evolu-tionary tuning of multiple SVM parameters,Trends in Neurocomputing: 12th European Symposium on Ar-tificial Neural Networks 2004,Volume 64, March 2005, Pages 107-117.
[Zhang 12] K.Neshatian,Mengjie Zhang,and P.Andreae, A filter approach to multiple feature construction for symbolic learning classifiers using genetic program-ming : Evolutionary Computation, IEEE Transactions on, Vol. 16, No. 5, pp.645-661,oct. 2012.
[Merz C.J. 98] Merz C.J. Blake and C.L. , Uci repository of ma- chinelearning databases, 1998.
[Koza 92] J.Koza: Genetic programming,on the program-ming of computers by means of natural selection, MIT Press, 1992
