編集距離と遺伝的プログラミングを利用した特徴的木パターンの獲得 中居 翔平（0820129） 知能工学科 機械学習研究室 指導：宮原 哲浩 准教授 1．はじめに 木データは表現能力の高い構造的データであり、 多くの分野で用いられている。糖鎖は核酸(DNA)と タンパク質に続く3番目に重要な生体分子で、各種 の糖が結合した一群の化合物であり、木構造をして いる。本研究は先行研究(久保田直人, 2010)で提案さ れた編集距離による比較方法と、遺伝的プログラミ ングを利用して、正事例と負事例から特徴的な VLDC付き木パターン(K.Zhang et al., 1994)を獲得 する手法を提案する。 また、図中の“|”, “Λ”は VLDC 変数を表す。 6.終了条件である世代数まで達していれば終了。そ うでなければ 5 で生成された次世代の集団を現世代 の集団として 3 へ戻る。 VLDC 付き木パターンの適合度は(正事例にマッ チする割合+負事例にマッチしない割合)/2 と定義す る。 2．木パターンと木データとの編集距離 木 T1 と木 T2 の編集距離は、T1 を T2 に変換するた めにノード削除、ノード挿入、ノードラベル置換の 3 種類の編集操作を用いて編集する際にかかるコス トの総和の最小値として定義される。 本研究における木パターンは木データの構造の一 部分を代入できる VLDC 変数を持つ。S を木パター ン P における可能な VLDC 変数への代入の全ての 集合としたとき、木パターン P の VLDC に代入 s ∈S を適用して得た木 P(s)と木データ T との編集距 離が最小になるときの P(s)と T の編集距離を、木パ ターン P と木データ T の編集距離と定義する。 3．遺伝的プログラミング(GP)を用いた単一 VLDC 付き木パターンの発見 VLDC 付き木パターン P と木データ T の編集距離 が 0 となるとき P と T がマッチするといい,これが 0 より大きいときマッチしないという。 単一 VLDC 付き木パターン発見問題とそれに対 するアルゴリズムを以下に示す。 入力：正事例、および負事例からなる木構造データ の有限集合 D 問題：GP により、正事例に多くマッチし、負事例 にあまりマッチしないような特徴的な VLDC 付き 木パターン P を発見する。 アルゴリズム 1.正事例木データ集合から使用されているノードラ ベル、ラベルの上下関係、木のサイズの最大値、子 の数の最大値を求める。 2.で求めた値を基にランダムに初期 VLDC 付き木パ ターン集合を生成する。 3.VLDC 付き木パターンの適合度を求める。 4.適合度の大きさに比例した確率によって VLDC 付 き木パターンの選択を行う。 5.交叉、突然変異、逆位、複製の遺伝的操作により、 次世代の集団を生成する。図 1 に交叉の例を示す。 図 1：VLDC 付き木パターンにおける交叉の例 4．実験 実験データとして KEGG GLYCAN データベー スに登録されている白血病に関する正事例データ 176 個、負事例データ 304 個を用いる。GP のパラ メータは次の通りである。 個体数:50、交叉確率:0.7、突然変異確率:0.1、逆位 確率:0.1、複製確率:0.1、最大世代数:200。 GP により正事例に多くマッチし、負事例にあま りマッチしない VLDC 付き木パターンを獲得する 試行を 10 回行った。図 2 は、各世代で最も適合度 の高い個体の適合度の 10 試行の平均値の推移であ る。図 2 から適合度が高いことがわかる。よって、 正事例に多くマッチし、負事例にほとんどマッチし ない木パターンを獲得することができたといえる。 適合度 1 0.8 0.6 0.4 0.2 0 適合度 正事例にマッチする割合 負事例にマッチしない割合 1 20 40 60 80 100 120 140 160 180 200世代数 図 2：最も適合度の高い個体の適合度の推移 5．おわりに 本研究では，遺伝的プログラミングを用いて，糖 鎖データの特徴を捉えた VLDC 付き木パターンを 発見する手法を提案した。
© Copyright 2025 ExpyDoc
