根付きラベル付き木の地均し距離について
5
0
0
全文
(2) . 川口 泰雅. . 平田耕一 .
(3) . 九州工業大学大学院情報工学府.
(4) .
(5)
(6) . 九州工業大学大学院情報工学研究院.
(7)
(8)
(9) . .
(10)
(11) . . はじめに. 木構造データのデータマイニングや機械学習では つの木構造データの非類似度を計算する必要がある 木 の非類似度として有名なものに木編集距離 がある 木編集距離は一方の木から他方の木への変換に要する 編集操作の最小回数で定義される 木編集距離には さまざまな変種が提案されている ! が アライメント距離 " を除きその多くがメト リックとなる 一方で 無順序木の編集距離やアラ イメント距離の計算は #$% &'( 困難となる " )) 木編集距離以外の木の非類似度としては 木編集距離 の定数下限を与えるラベルや次数などの局所情報のヒ ストグラムに基づく距離が知られている * これら は 木編集距離と比較して高速に計算することができる が メトリックとなるものは存在しない 一方 地均し距離 + , - とは 主に類似画像検索の分野で用いられる つの画像を比 較する距離であり つの画像における素性の分布 +シ グネチャ, 間の輸送問題の解として定式化される この 地均し距離は 素性間の距離 +基盤距離, がメトリック であればメトリックとなることが保証できる - この地均し距離を木構造に拡張した研究として 等高 葉ラベル無順序木間の地均し距離 ) が挙げられる た だ この地均し距離の計算方法を一般の根付き葉ラベル 付き木にまで拡張することは容易ではない そこで本論文では 根付きラベル付き無順序木に対 連絡先：九州工業大学大学院情報工学府 〒 福岡県飯塚市川津 .
(12)
(13)
(14) . して 完全部分木 および 完全部分木とその補完全部 分木のヒストグラムに基づいた地均し距離を定式化し それを計算するアルゴリズムを実装する また この距 離はメトリックとなるため 無順序木でも多項式時間で 計算可能となる木編集距離の変種のうち最も一般的な 制限距離 . )/ と比較し その特徴について解析する. . 準備. 本章では 木の地均し距離の定式化のための諸定義を 導入する. ¾º½. 木. 閉路を持たない連結無向グラフを木という ノード の集合 辺集合 からなる木 0 + , に対して を単に と表す 木 に含まれるノードの 数 を のサイズといい で表す ) つのノードを根として選んだ木を根付き木という また 根付き木 の根ノードを + , と表す から根までの経路上にあるノードのうち で ないものを の先祖という の先祖がノード である ことを と表し 0 または であるとき と表す また を先祖に持つノードを の子孫 という 特に かつ と が隣接しているとき を の親といい を の子という また 子を持た ないノードを葉という ノードの子の数を次数という 木 に対して が の部分グラフであるとき を の部分木であるという また に対して. － 84 －.
(15) と に含まれる のすべての子孫からなる部分木を と表し の を根とする完全部分木という から完全部分木 を取り除いてできる木を と 表し 補完全部分木という のすべての完全部分木 の重集合とすべての補完全部分木の重集合を それぞ れ + , 0 + , 0 0 + , と表す ここで 補完全部分木の重集合 に根ノードの補完全部分木を含めないのは 根ノード の補完全部分木は必ず空の木になるためである その 代わりに元の木そのものをヒストグラムに持つことで 後述する木の距離がメトリックになることを保証する また 木 のすべての完全部分木と補完全部分木の重 集合を + , 0 + , + , と表す 木に関する基本的な操作は 木の各ノードを一つず つ調べることである これを木の走査という 走査の 手順として 親を走査してから 子を走査する先行順走 査と子をすべて走査してから 親を走査する後行順走 査を考える ノード に対して の先行順走査に おける順番を
(16) + , 後行順における順番を
(17) + , と 表す このとき に対して
(18) + ,
(19) +, かつ
(20) + ,
(21) +, のとき は の左にあるといい は の右にあるという 各頂点の子に左右の順序を指定している根付き木を 根付き順序木といい 指定していない根付き木を根付 き無順序木という また 各ノードがアルファベット 1 によってラベル付けされている木をラベル付き木とい う 本論文では 根付きラベル付き無順序木を単に木と いう. ¾º¾. ヒストグラムに基づく距離. 木 に対して が完全部分木として に出現 する頻度を + , とし が補完全部分木として に出現する頻度を + , とする このとき + , + , をそれぞれ の完全部分木ヒストグラム 補完 全部分木ヒストグラムといい 次のように定義する. . , 0 + + ,, + , 0 + + ,, +. + , . + , . + , と + , の 距離を完全部分木距離といい + , と表す また + , と + , の 距離 を補完全部分木距離といい + , と表す 具体的. + ,. + , 2 + , とする 完全部分木. 0. と補完全部分木からなるヒストグラムとそれに基づく 距離をそれぞれ相補完全部分木ヒストグラム + , 相補完全部分木距離 + , といい 次のように定 義する. + , 0 + + ,, + , 0 . ヒストグラム + , の要素数は ) である これ は + , と + , がともに元の木を含むためである また これらヒストグラムに基づく距離を それぞれ のヒストグラムに含まれる要素数の和で割ることで 任 意の木間の距離を / から ) の範囲に正規化することが できる この正規化した距離を正規完全部分木距離 正 規補完全部分木距離 正規相補完全部分木距離といい 次のように定義する. 3 + , 0 3 + , 0 3 + , 0. . , 0. +. . ½ ¾ . . ½ ¾ . , 0. +. + , + , + , + ,. + , 2 + , 2 + , 2 . ¾º¿ 地均し距離 特徴量
(22) と重み のペアの集合をシグネチャとい い 0 +
(23) , と表す の要素 +
(24) , の特徴量を
(25) で表す 地均し距離（4 # 5 以降単に という）とは つのシグネチャ間に 定義される距離である つのシグネチャが与えられた とき 一方から他方への輸送問題を考え その最小コス トが距離となる 0 +
(26) , 0 + , をシグネチャとする
(27) 間の距離を基盤距離（ ）といい +
(28) , と表す また
(29) から への輸送量を で 表し
(30) から への輸送コストを +
(31) , とする と つのシグネチャ間の総コストは次のように表さ れる. +
(32) , . なは 次のような式で定義される. . ½ ¾ . + , + , + ,. . . このとき 以下の制約を満たし 総コストが最小となる を求める フロー ) . － 85 －. . / . . .
(33) " . . . . . 0 . . . . . . . . . . 制約 ) は 輸送元である から輸送先である に輸送 することを表している（逆はない） 制約 と " は 輸 送量が各要素の重みを超えることはないことを表して いる 制約 は 輸送できる限界まで輸送することを表 している であるとき つの この輸送問題の最適フローが シグネチャ間の 4#5 を次のように定義する. + , 0 0. . . . . +
(34) , +
(35) , , . . +. . 完全部分木である 重みは が木 におけるその完 全部分木または補完全部分木の出現回数であり 3 が木 におけるその完全部分木または補完全部分木の出現 率である これにより 重みの総和はそれぞれ が木 のノード数 であり が ) であり 3 が ) である 次に 基盤距離を考える 基盤距離はシグネチャの要 素の特徴量間に定義される距離である ここでは特徴 量が完全部分木もしくは補完全部分木 つまり木である ため 基盤距離には木間の距離を用いる 本研究では 基盤距離として 完全部分木距離 正規完全部分木 距離 3 補完全部分木距離 正規補完全部分木距離 3 相補完全部分木距離 正規相補完全部分木距離 3 を用いる これら木のシグネチャと基盤距離を組み合わせるこ とにより木の 4#5 を表 ) のように定義する. つのシグネチャの重みの総和が異なるとき 4#5 によって つのシグネチャ間の部分一致が可能である これは重みの総和の小さいシグネチャが重みの総和の 大きいシグネチャの一部のみと輸送を行うことにより 実現することができる 4#5 について以下の定理が成り立つ . 表 4#5. + , + , + , + , + , + ,.
(36) . 定理 つのシグネチャの重みの総和が等しく 基盤距離がメトリックである場合 その 4#5 もメト リックである また 4#5 は + , 時間で計算 可能である ここで 0 6 である. . 木の地均し距離. 本節では 木の新しい距離として 4#5 を用いた距離 を定式化する 4#5 の計算には シグネチャとシグネチャの特徴量 間の距離である基盤距離が必要となる そこで 木の 4#5 を定式化するために まず 木からシグネチャへ の変換を考える 本研究では 木 のシグネチャとし て以下の - つを考える. 0. 3 0. 0. 3 0 . 0. 3. 0. . . + , + , 0 + ,. )7. 木の 4#5 シグネチャ. 基盤距離. + , 3 + , + , 3 + , + , 3 + ,. + , 3 + , + , 3 + , + , 3 + ,. 表 ) の各 4#5 のシグネチャには必ず元の木が含まれ るため 変換が位置である また 基盤距離がメトリッ クであるため 定理 ) の系として以下が成り立つ.
(37). 系 表 ) の木の 4#5 はすべてメトリックである ま た これらの 4#5 は + , 時間で計算可能であ る ここで 0 6 である. . 正規制限距離との比較. 本章では 木の地均し距離を計算するアルゴリズム を実装し ' 型糖鎖データに適用した結果を正規制限 距離と比較する ここで正規制限距離は 編集距離の 変種である制限距離 . )/ を正規化したものであり つの木 間の制限距離を + , としたとき. + , + , . + , 0 + , . + , 0 + , + , + , . + , 0 + , + , 0 + , + , + , + , 0 ). . . . 特徴量は 3 が木 の完全部分木であり 3 が木 の補完全部分木であり 3 が木 の相補.
(38) ½ ¾ ½ ¾ . で求められる距離である. 実験に使用する ' 型糖鎖データは全部で /) 個で 最大ノード数は "! 最小ノード数は ) ノード数の平均は ))/-.- 高さの平均は - /"/! 次数の平均は / "である 図 ) は 小数点第 位で四捨五入した各距離に対し その値をとる木の組合わせの割合を表している 図中. － 86 －.
(39) は正規制限距離 4#5) は 4#5 は を示す また 図 に 縦軸を 横軸を正規制限距離としたときの分布を 図 " に 縦軸を 横軸を正規制限距離としたと きの分布を示す プロットの直径と色は その点におけ る木の組数を表しており 同じ点に多くの組が存在する ほど 直径は大きくなり 色は濃くなる 図 ) より は正規制限距離に比べ大きい 値を取る傾向にあり はほとんどの木の組が 距離 ) をとることがわかる これは は距離 の計算に完全部分木しか用いていないため木の構造情 報を詳細に反映できていないからだと考えられる 図 図 " より どちらの 4#5 も正規制限距離とは 異なる値を取り 極端に値の異なる木の組合せがあるこ とがわかる これは 4#5 が編集操作に基づく距離と は異なる基準で木の距離を計算しているといえる 具体 的に 正規制限距離に対して + , が大き くなっている木の組合せには以下のようなものがある .
(40). 100 constrained EMD1 EMD2 80. 60 percent. の. 40. 20. 0 0. 図. 次数の低い木同士で葉のみが異なる木の組合せ. 1. 各距離の分布. 0.8 0.7 0.6 0.5. 正規制限距離に対して が大きくなっている 木の組合せには以下のようなものがある. 0.3.
(41). 0.8. 1. 同じ部分木を多数持つ木とその部分木と正規完全 部分木距離が小さい木の組合せ.
(42). )7. 0.4 0.6 distance. 0.9. 逆に 正規制限距離に対して + , が小さ くなっている木の組合せには以下のようなものがある.
(43). 0.2. 0.4. 0.2 0.1. ノード数の大きい木同士で一部のノードだけが異 なる木の組合せ ほとんどのノードの次数が の木同士で葉と根が すべて異なる木の組合せ 図 に例を示す. 0 0. 図 7. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9. 1. （縦軸）と正規制限距離（横軸）の分布 1. 逆に 正規制限距離に対して が小さくなっ ている木の組合せには以下のようなものがある.
(44). 0.9 0.8 0.7. 同じ部分木を多数持つ木とその部分木と正規相補 完全部分木距離が小さい木の組合せ. 0.6 0.5 0.4. . 0.3. まとめ. 0.2. 本研究では 完全部分木 および その補完全部分木 のヒストグラムに基づいた根付きラベル付き木の地均 し距離を定式化した この木の地均し距離には 編集操 作に基づく距離とは異なる性質を持ち メトリックとな り多項式時間で計算できる距離である 距離を求める ことが可能になった この木の地均し距離は 木からシグネチャへの変換方 法と基盤距離の つの組合せにより実現されているた. 0.1 0 0. 図 "7 分布. － 87 －. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9. 1. （縦軸）と正規制限距離（横軸）の.
(45) A B I. B. C. C. D D. 図. . D. D D. D. B. D. 木の組合せの例. 7. B. B. B. このとき正規制限距離. 0 ). / -!! . D. 0. め その両方について新しい手法を適用する または組 合せを変えることにより また違った性質を持つ距離を 作り出すことが可能である そのため 今後の課題とし ては 異なる木の地均し距離の定式化と その特徴につ いて精査することが挙げられる. 参考文献
(46)
(47)
(48)
(49)
(50)
(51)
(52)
(53) .
(54) . . !. " " #$ " %% & ' %
(55) . ()'*. +,+ + -. *!. - ' . / 0 " 1 . -, * . '%%2 34 2 . . 5!. * ' " 6 4 .
(56)
(57)
(58)
(59)
(60) . 2%7 7 8 9%7 2 : ';. . ,!.
(61)
(62)
(63)
(64)
(65)
(66)
(67) . 5 < / # 0 . / # . . - . => %
(68). . -!. . !
(69) . + ? 6%. 3 '4 7 . . 34 2 @ 7 ,. "$3. ' . . A3> . . / . 6 7. =2. . . ,!.
(70) . * *--.
(71) .
(72) ' ?7 " # 2 . . : 34 2 7 . '%$. 2 . % !.
(73)
(74)
(75)
(76)
(77)
(78)
(79)
(80)
(81)
(82)
(83) " 1 . 22% %. . . , !. ". *+- *,*. 5!. 1 . . A 24 . . 5$ . +! . " "#$
(84)
(85)
(86)
(87) " 1 ' . . /%22. * 5*. . =:4 %77. *!. － 88 －.
(88)
関連したドキュメント
Schwann氏細胞は軸索を囲む長管状を呈し，内部 に管状の髄鞘を含み，Ranvier氏絞輪部では多数の指
(6)
ポンプの回転方向が逆である 回転部分が片当たりしている 回転部分に異物がかみ込んでいる
光を完全に吸収する理論上の黒が 明度０，光を完全に反射する理論上の 白を 10
優越的地位の濫用は︑契約の不完備性に関する問題であり︑契約の不完備性が情報の不完全性によると考えれば︑
他方、額縁その他これに類する物品で、木製又は金属製の枠に取り付けたものは、44.14 項又 は
・ ○○ エリアの高木は、チョウ類の食餌木である ○○ などの低木の成長を促すた
1 第 5２.11 項（綿織物（綿の重量が全重量の 85％未満のもので、混用繊維の全部又は大部分 が人造繊維のもののうち、重量が 1 平方メートルにつき
