The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 1 -
遺伝的プ
ン
編集距離を利用
特徴的
VLDC
木パ
ーン
獲得
Acquisition of Characteristic Tree Patterns with
VLDC’s by Genetic Programming and Edit Distance
中居
翔平
*1
宮原
哲浩
*1
久保山
哲
*2
内田
智之
*1
鈴木
祐介
*1
Shohei Nakai Tetsuhiro Miyahara Tetsuji Kuboyama Tomoyuki Uchida Yusuke Suzuki
*1
広島市立大学情報科学研究科
*2
学習院大学計算機
ン
ー
Graduate School of Information Sciences, Hiroshima City University Computer Centre, Gakushuin University
Knowledge discovery from structured data is an important task in machine learning and data mining. We propose a learning method for acquiring characteristic tree patterns with VLDC’s from positive and negative tree structured data by using Genetic Programming and tree edit distance. We report experimental results on applying our method to glycan data.
1.
め
木 構 造 ー 機 械 学 習 や ー イ ン 研 究
注目さ い ． 糖鎖 木構造を ， 酸(DNA) ンパ 質 続く3番目 重要 生体分子 あ ．遺伝的プ ン
(Genetic Programming, GP) [Poli 08] ，遺伝的ア
(GA) 遺伝子型を拡張 ，構造的表現 木構造 を扱え う
あ ．
遺 伝 的 プ ン 編 集 距 離 を利 用 正 例 負
例 木 ー 特徴的 VLDC木パ ーン[Zhang 94]を獲 得 提案手 法[Nakai 13] ，新 糖鎖 ー を適 用
有 効 性 を 確 認 ， 本 稿 報 告 ．
VLDC(variable-length don’t care) 木 ー 一 部 を代 入 構 造 的 変 数
あ ．関連研究 ，遺伝的プ ン 特徴的
木 パ ーン 獲 得手 法[Nagamine 07]，有 向 フ構造 対 進化的計算手法 [Katagiri 00]やTTSP フパ ーン 進化 的獲得手法[Nagai 12] あ ．
2.
準備
本稿 ，木構造 順序木構造を持 ，木構造 ー
構造的特徴を表現 ，VLDC木パ ーン 呼ぶ木構 造パ ーン を用 い ． VLDC 木パ ーン ， ノー ベ ー を表現 ，木 ー 一部を代入 VLDC変数を持 ． こ VLDC変数 Path-VLDC Umbrella-VLDC 2種類
あ ． 木 ー 葉 ま 経 路 一 部 代 入 可 能
VLDC変数をPath-VLDC いう．表記 | 表さ ．木
ー 葉ま 経路 一部 ， 経路 一部 ノー
出 い 部 分 木 代 入 可 能 VLDC 変 数 を
Umbrella-VLDC いう ． 経 路 一 番 ノー 出
い 部分木 含ま く い．表記
⋀
表さ ．木 ー T1 木 ー T2 編集距離 treedist(T1,T2) ，T1 を T2 変換 ノー 削除，ノー 挿入，ノー ベ 置 換 3種類 編集操作を用い 編集 際 総 和 最小値 定義 [Zhang 89]．SをVLDC木パ ーンP
け 可能 VLDC変数 代入 全 集合 ．P
VLDC変数 代入 s∈Sを適用 得 木 ー をP(s) ．
P(s) 木 ー T 編集距離 最小 代入s∈S
，P(s) T 編集距離を，P T 編集距離treedist(P,T) 定義 [Zhang 94]． VLDC木パ ーン 木 ー 編集距離
例を図1 示 ．こ 例 ，ノー 削除，ノー 挿入，ノー ベ 置換 編集 全 1 い ．
図1 : VLDC木パ ーンP 木 ー T 編集距離
3. GP
と編集距離を利用
た特徴的
VLDC
木
パターン
獲得
以 定義 ，特徴的VLDC木パ ーン獲得問題を対象 ，GP 獲得手法を述 ．
特徴的VLDC木パ ーン獲得問題：
入力：正 例 負 例 木 ー 有限集合D 問題：D 特徴を表 VLDC木パ ーンを獲得 ．
GP-0 GP-AUC いう２ ，木構造 基 く通常 GP
獲得手法を提案 ．異 点 VLDC木パ ーンP 木 ー T ッ こ 定義 ，個体 あ VLDC木パ ーンP 適合度 定義 あ ， ほ 設定 同 あ ．P
D 正 例集合 ッ 割合をP 正 例支持度 い
う． P D 負 例集合 ッ い割合を P 負 例支 持度 いう．(P 正 例支持度 + P 負 例支持度)/2をP 総支持度 いう．
GP-0 treedist(P,T)=0 あ 時 け，P T ッ
いう．P 総支持度をP 適合度 定義 ． GP-AUC 編集距離 閾値d 対 ，treedist(P,T)≦d あ 時 け， P
T ッ いう．D 正 例集合 対 P ッ
正 例 割合を P 真陽性率 いう．D 負 例集合 対
P ッ 負 例 割合をP 偽陽性率 いう． d
値を こ 得 P 真陽性率 偽陽性率 計算
ROC分析 AUC値をP 適合度 定義 ．
GP 特徴的VLDC木パ ーンを獲得 手法：
1. 正 例木 ー 集 合 使用 さ い ノー ベ ，親 ノ
ー 子 ノー ベ 関 係 ， 木 ー イ ノー 個
数 最大値，子 数 最大値を 求 ．
連絡先：宮原哲浩，広島市立大学情報科学研究科，〒731-3194
広島市安佐南区大塚東3-4-1，miyares13@info.hiroshima-cu.ac.jp
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 2 -
2. 1 求 値を基 ン 初期VLDC木パ ーン集合
を生成 ．
3. VLDC木パ ーン 適合度を求 ．
4. 適合度 大 さ 比例 確率 VLDC木パ ーン
選択を行う．
5. 交叉，突然変異 部分木交換，部分木追加，部分木削除 ，
逆位，複製 遺伝的操作 ，次世代 集団を生成 ．
図2 VLDC木パ ーン 交叉 例を示 ．
6. 終了条件 あ 世代数ま 達 い ば終了 ． う
け ば5 生成さ 次世代 集団を現世代 集団 3 戻 ．
図2：VLDC木パ ーン 交叉例
4.
実験
3. 説明 2 手法を用 い GP 適 合度 高 い
VLDC 木パ ーン を獲得 実 験を行 ． 実 験 ー
KEGG GLYCAN ー ベー 登録さ い 次 3種類
糖鎖 ー を使用 ．白血病 関 正 例 ー 177個， 負 例 ー 302個．結腸癌 関 正 例 ー 87個，負 例 ー 47個．嚢胞性線維症 CF症 関 正 例 ー
89個，負 例 ー 71個．GP パ ー 次 通 あ
． 個 体 数:50， 交 叉 確 率:0.7， 突 然 変 異 確 率:0.1， 逆 位 確 率:0.1， 複 製 確 率:0.1， 最 大 世代 数:200， ー ッ イ :4， ー ン イ :4，エ ー イ :5．編集 次 う 設 定 ．ノー 削除 ノー 挿入 1 ．ノー ベ 置 換 編 集 ， 糖 ベ 同 結 合 ベ 同
時 0，糖 ベ けま 結合 ベ け 同 時 0.5，糖 ベ 異 結合 ベ 異 時 1 ．
3種類 ー を使用 時 2 手法 最終世代 最
良個体 適合 度 値 10 試行 平均値 を表 1 示 ．
GP-0 ，正 例支持度，負 例支持度，適合度，総支持度
値 最 終世 代 最 良 個体 値 あ ．GP-AUC ，適 合 度 値 最終世代 最良個体 値 あ ．さ ，最終世代
最良個体 総支持度 最大 う 編集距 離 閾値 d を 定 総支持度，正 例支持度，負 例支持度を示 ．
GP-0 GP-AUC 適合度 推移 10試行 平均値 を図3
示 ．図 4 白血病 関 ー を与 え GP-AUC
最終世代 最良個体 あ VLDC木パ ーン 例を示 ．
5.
おわり
遺伝的プ ン 編集距離を利用 特徴的 VLDC 木パ ーンを獲得 手法を，3種類 糖鎖 ー 適用
有 効 性 を確 認 ． 糖 鎖 ー 以 外 木 構 造 ー 提
案 手 法 を適 用 有 効 性 を検 証 実 験 を行 うこ 課 題
考え ．
表1：GP-0 GP-AUC け 最終世代 最良個体 比較
GP-0 GP-AUC
使用データ 白血病 結腸癌 CF症 白血病 結腸癌 CF症
正 例支持度 0.72 0.37 0.45 0.81 0.97 0.88
負 例支持度 0.92 0.95 0.92 0.90 0.77 0.78
適合度 0.82 0.66 0.68 0.91 0.93 0.86
総支持度 0.82 0.66 0.68 0.86 0.87 0.83
図3: 各世代 適合度 平均値 推移
図4: GP-AUC 最良個体 あ VLDC木パ ーン
参考文献
[Katagiri 00] H.Katagiri et al., Genetic Network Programming - Application to Intelligent Agents, Proc. IEEE Int. Conf. Systems, Man, and Cybernetics, pp.3829-3834, 2000.
[Nagai 12] S.Nagai et al., Acquisition of Characteristic TTSP Graph Patterns by Genetic Programming, Proc. 2012 IIAI International Conference on Advanced Applied Informatics, pp.340-344, 2012.
[Nagamine 07] M. Nagamine et al., A Genetic Programming Approach to Extraction of Glycan Motifs Using Tree Structured Patterns, Proc. AI 2007, Lecture Notes in Artificial Intelligence, Springer-Verlag vol.4830, pp.150-159, 2007.
[Nakai13] S.Nakai et al., Acquisition of Characteristic Tree Patterns with VLDC's by Genetic Programming and Edit Distance, Proc. 2013 IIAI International Conference on Advanced Applied Informatics, pp.147-151, 2013.
[Poli 08] R.Poli et al., A Field Guide to Genetic Programming, Lulu Press, 2008.
[Zhang 89] K.Zhang and D. Shasha, Simple Fast Algorithms for the Editing Distance between Trees and Related Problems, SIAM Journal on Computing, Vol.18, No.6, pp.1245-1262, 1989. [Zhang 94] K.Zhang et al., Approximate Tree Matching in the Presence of Variable Length Don’t Cares, Journal of Algorithms Vol.16, No.1, pp.33-66, 1994.
0.5 0.6 0.7 0.8 0.9 1
GP-AUC(白血病) GP-0(白血病) GP-AUC(結腸癌) GP-0(結腸癌) GP-AUC(CF症) GP-0(CF症)
1 20 40 60 80 100 120 140 160 180 200
世代数 適
