Tree PCAによる任意形状の木構造を抽出するアルゴリズム

人工知能学会研究会資料
SIG-FPAI-B502-17
Tree PCA による任意形状の木構造を抽出するアルゴリズム
Algorithms for Extracting Arbitrarily Shaped Subtrees
by Tree PCA
山崎朋哉 1∗
Tomoya Yamazaki1
山本章博 1
Akihiro Yamamoto1
久保山哲二 2
Tetsuji Kuboyama2
1
1
京都大学情報学研究科
Graduate School of Informatics, Kyoto University
2
学習院大学計算機センター
2
Computer Centre, Gakushuin University
Abstract: We propose two eﬃcient algorithms based on Tree PCA, extracting principal component subtrees from a set of labeled rooted unordered tree data. Both of them are instances of the
scheme of Tree PCA provided in our previous work. The naive methods based on Tree PCA require hard computation costs, that is, each of eﬃcient algotirhms is diﬀerent from each of instances
of the scheme. In our previous work, we proposed an eﬃcient algorithm for extracting principal
component paths based on top-down mappings. In this paper, we propose two eﬃcient algorithms
for extracting principal component subtrees, not only paths, based on top-down and bottom-up
mappings. The key idea of our methods is computing the largest common subtrees among all
given tree data eﬃciently. As a result, we can extract more characteristic subtrees from a set of
given tree data. We confirm the utility by applying an algorithm based on top-down mappings
and comparing the previous work.
1
はじめに
近年, 高次元数値データを解析するために, Pearson
によって提唱された主成分分析 (以下 PCA) が広く使
われている．PCA は, 与えられたデータの集合を互い
に相関のない特徴にまとめるために，できるだけ情報
量の損失の少ない低次元空間へ射影する．また, グラフ
や木構造といった複雑なデータから有用な部分構造を
捕らえることは非常に重要な問題である. 本稿では, 木
構造データの集合から有意な特徴を持つ構造を抽出す
るために, 木構造への PCA(以下 Tree PCA) を考察
する．
Tree PCA は近年研究が進んできている. Wang と
Marron[6] によって初めて Tree PCA が定式化され,
MRA 画像から得られた血管の構造を表す二分木に対
して適用された. そして, Aydin ら [2] によってラベル
無し根付き二分木に対する Tree PCA を線形時間で解
くアルゴリズムが提唱され, Alfaro ら [1] は, Aydin ら
の手法をラベル無し根付き k 分木へ拡張した. しかし,
∗ 連絡先：京都大学大学院情報学研究科
〒 606-8501 京都府京都市左京区吉田本町総合研究
7 号館 3 階 324・327 号室
E-mail:[email protected]
それらの先行研究では, 主成分としてパスしか抽出す
ることができなかった．そこで我々は, より一般的な根
付きラベル付き無順序木から, 任意の形状の部分木を
主成分として抽出する Tree PCA のスキーマを提案し
た [8].
我々の提案した Tree PCA のスキーマでは, 抽出す
る木構造の形状の規則 R と, データの特徴空間を構成
するためのマッピングが入力として必要であり, それ
らの入力によって, 効率的なアルゴリズムは異なる. [8]
では, R としてパス, マッピングとして, トップダウン
マッピングを用いたときの線形時間のアルゴリズムと
実験結果を示した．
本稿では, 入力として特徴空間を構成するためのマッ
ピングのみを与えたときに, 抽出する木構造の形状の規
則を与えることなく, 主成分を抽出する効率的なアル
ゴリズムを提案する. 提案手法は, Tree PCA のスキー
マに従うと, R として全入力データ間の最大共通部分
木の形状を与えていることに等しいが, この最大共通部
分木はマッピングの制約に従うため, 明示的に R を指
定する必要が無い. また, 提案手法はマッピングの制約
としてトップダウンマッピングとボトムアップマッピ
ングの二つの場合において, 入力データ数に対して線形
− 63 −
T1
である.
T2
v2
2
準備
本稿で扱う木とは, 非巡回連結有向グラフであり, V
をノード集合, E ⊆ V × V を枝集合, r を根ノードと
したとき, 木は T = (V, E, r) と表す. また, 木の集合
のことを森と呼ぶ. ノード間の祖先関係を ≤ で表し,
u, v ∈ V に対して, u ≤ v は v が u の祖先であること
を表す. 特に u ≤ v かつ u ̸= v のとき, u < v と記す.
根ノードを r としたとき, v ∈ V \ {r} の親ノードを
parent(v), v ∈ V の子ノード集合を child(v) と記す.
ノード v ∈ V の深さを dep(v) と記す. ノードのラベル
はアルファベット Σ 中の記号であり, 各ノードに一つラ
ベルが与えられる. 木 T = (V, E, r) に対して, ラベル関
数を α : V → Σ と定義する. ノード v ∈ V を根とする
T 中の完全部分木を T (v) と定義し, v の子ノード集合を
根とした森を T [v] = {T (u) | u ∈ child(v)} とする. 木
T1 = (V1 , E1 , r1 ) 中のノード v に T2 = (V2 , E2 , r2 ) を
連結するとは, T1 を T1′ = (V1 ∪ V2 , E1 ∪ E2 ∪ {(v, r2 )})
に変える操作のことをいう. 本稿では, ラベル付き根付
き無順序木を対象とし, 簡単のために T = (V, E) と記
し, T = (V, E) に対して, v ∈ V を v ∈ T とも記す.
二つの木 T1 = (V1 , E1 ), T2 = (V2 , E2 ) に対して, ノー
ド v ∈ V1 の削除と挿入, v のラベルを u ∈ V2 のラベル
へ置換する 3 つの操作を編集操作と呼び, それぞれの編
集コストを γ(v → λ), γ(λ → u), γ(v → u) と記す. 木
T1 から木 T2 に変換するための編集操作に要するコスト
の最小値を編集距離と呼ぶ. また, γ(v → u) ≥ γ(v →
λ) + γ(λ → u) を満たすとき, 編集操作にラベルの置換
を考慮しないことと同じである. このとき, 木 T1 から
木 T2 に変換するための編集操作に要するコストの最小
値を indel(insert-deletion) 距離と呼ぶ.
2.1
マッピング
マッピング M ⊆ V1 ×V2 とは, 二つの木構造間のノー
ドの対の集合であり, それに与える制約 R によって様々
なマッピングが存在する. ここで, M |T1 , M |T2 をそれ
ぞれ T1 , T2 中で M に含まれるノードの集合とし,
M |T1 = {x1 ∈ V1 | ∃x2 ∈ V2 , (x1 , x2 ) ∈ M }
M |T2 = {x2 ∈ V2 | ∃x1 ∈ V1 , (x1 , x2 ) ∈ M }
と定義する. このとき, 編集に要するコストの合計 γ(M )
が, 以下の式で与えられる.
γ(M ) =
∑
(x,y)∈M
γ(x → y) +
∑
x∈M |T1
γ(x → λ) +
∑
y∈M |T2
γ(λ → y).
T1
w1
v1
v7
w2
T2
w1
v1
w3
v2
v3
v5
w4
w6
v4
v6
w5
w7
v3
v6
v4
w2
w3
w4
w5
v5
図 1: 左図がボトムアップマッピング, 右図がトップダウン
マッピングの例.
また, T1 と T2 の間の編集距離を求めることは γ(M ) を
最小にするようなマッピング M を発見することと等価
であることが示されており [4], そのような M を T1 , T2
間の最適なマッピングと呼ぶ.
Tai マッピング [4]
二つの木が無順序木であるときの Tai マッピング M
の条件を以下に示す. マッピング M に対して, 任意の
ノードの対 (v1 , v2 ), (u1 , u2 ) ∈ M が以下の条件を満た
すとき, M は Tai マッピングであるという.
v1 = u1 ⇐⇒ v2 = u2 (一対一の関係),
v1 < u1 ⇐⇒ v2 < u2 (祖先関係の保存).
トップダウンマッピング [7]
M が木 T1 , T2 の Tai マッピングであるとき, 任意の
ノードの対 (u, v) ∈ M (ただし, u, v は根ノードではな
い) に対して, (parent(u), parent(v)) ∈ M が存在する
とき, M をトップダウンマッピングという.
ボトムアップマッピング [5]
木 T1 , T2 の Tai マッピングを M とおくとき, 任意の
ノードの対 (u, v) ∈ M が以下の 2 つの条件
∀u′ ∈ T1 (u) s.t. ∃v ′ ∈ T2 (v), (u′ , v ′ ) ∈ M,
∀v ′ ∈ T2 (v) s.t. ∃u′ ∈ T1 (u), (u′ , v ′ ) ∈ M,
を満たすとき, M をボトムアップマッピングという.
トップダウンマッピングとボトムアップマッピングの
例を図 1 に示す. ここで, 制約 R を満たす T1 , T2 間の最
適なマッピングを MR (T1 , T2 ) と記す. また, T1 , T2 間
′
の最大共通部分木 LCSTR (T1 , T2 ) は, MR
= {(u, v) |
(u, v) ∈ MR ∧ α(u) = α(v)} の要素数が最大となる
MR′ から誘導される部分木であり, LCSTR (T1 , ϵ) =
LCSTR (ϵ, T1 ) = T1 と定義する. このとき, MR に基づ
′
く木間距離を dR (T1 , T2 ) = |T1 | + |T2 | − |MR | − |MR
|
と定義する. 制約 R が Tai マッピングの制約に等しい
とき, dR (T1 , T2 ) は木間編集距離に等しい.
2.2
Tree PCA
本節では, [8] による Tree PCA のスキーマについて
説明する. 木 T = (V, E) とマッピングの制約 R に対し
− 64 −
w6
て, ACR (T ) は T 中の R を満たす全部分木の集合であ
り, 以下のように定義する.
Algorithm 1 木構造の縮約
INPUT : 木 T = (V, E).
T ′ = (V ′ , E ′ ) ← T .
for v ∈ V ′ do
if child(v) が同一のラベルを含む then
L ← child(v) 中のラベルが同じノード集合の
集合.
for l ∈ L do
x ∈ l に対して α(x) = α(w) を満たすノード
w を定義.
T ′ ← (V ′ ∪ {w} \ l, E ′ ∪ {(w, x) | x ∈ l ∪
{v}} \ {(v, x) | x ∈ l}).
end for
end if
end for
OUTPUT : T ′ = (V ′ , E ′ ).
ACR (T ) = {t | MR (t, T )|t = V }.
ここで, 木 T, E に対して, 木 T の AC(E) への射影点を
以下のように定義する.
P{E,R} (T ) ≡ arg min {dR (T, T ′ )}.
T ′ ∈ACR (E)
P{E,R} (T ) は, 空木 ϵ から E までの軸上の射影点である
木を表す. 以下では, 簡単のために P{E,R} を PE と記
す. ここで, 木の入力データ集合 T によって構成され
る木の集合である特徴空間を T S(T ) と定義する. (詳
しくは後述.) このとき, T の第一主成分を表す木は以
下のように定義する.
∑
PC 1 (T , R) ≡ arg min
dR (T, PE (T )).
(1)
E∈T S(T ) T ∈T
次に, 第 k 主成分を考察する. 集合 S1 , . . . , Sk が与え
られたとき, ⊎ を
S1 ⊎ · · · ⊎ Sk ≡ {{s, t} | s ∈ S, t ∈ T }
a
と定義する. また, 森の集合 FS = {F1 , . . . , Fn } とマッ
ピング M が与えられたとき, FS M は以下のように定
義する.
{
FS M =
F1
{Fn , {F1 , . . . , Fn−1 }M } = M (Fn , {F1 , . . . , Fn−1 }M )
T1
if |FS | = 1,
otherwise.
このとき, T の AC (t1 ) ⊎ · · · ⊎ AC (tk ) への射影点は包
除原理を用いて以下のように定義する.
|PS |
arg min
∑
(−1)n+1
PS ∈AC (t1 )⊎···⊎AC (tk ) n=1
∑
dR (T, FS MR ).
FS ∈{U ⊂PS ||U |=n}
ここで, 簡単のために, 第 1 ∼ 第 k − 1 主成分までを
P C1 , . . . , P Ck−1 と記すとき, 第 k 主成分は以下のよう
に定義する.
PC k (T , R) ≡ arg min
∑
E∈T S(T ) T ∈T
3
∑
dR (T, t).
c
b
c
b
ST
T3
a
c
a
a
b
dummy
a
a
b
b
c
a
b
a
d
a
図 2: 入力データである木構造 T1 , T2 , T3 に対する super tree
ST の例. ST 中の黒いノードは MTD (T1 , T2 ) 中のノードを
表す.
3.1
P{(t1 ,...,tk ),R} (T )
≡
T2
a
トップダウンマッピングに基づくアルゴ
リズム
本節では, トップダウンマッピングに基づき, 任意形
状の部分木を抽出する効率的な Tree PCA のアルゴリ
ズムを提案する. マッピングの制約 TD を置換を考慮
しないトップダウンマッピングの制約としたとき, T の
特徴空間 T STD を以下のように定義する.
T STD (T ) = {LCSTTD (s, t) | s, t ∈ T ∪ {ϵ} ∧ s ̸= t}.
t∈P{(PC 1 ,...,PC k−1 ,E),R} (T )
提案手法
[8] では, 主成分としてパスを抽出する効率的なアル
ゴリズムを提案した. すなわち, 特徴空間 T S(T ) をパ
スの集合と定義していた. 本節では, T S(T ) を最大共
通部分木の集合と定義することで, パスに限らない一般
的な構造を抽出する二つのアルゴリズムを示す. これ
らのアルゴリズムはトップダウンマッピングとボトム
アップマッピングに基づく. ここで, 前処理として入力
データの木構造は Algorithm 1 に従って縮約する. 縮
約することで, 同一の親ノードからなる子ノード集合
が, 同じラベルを持たないことを保証する.
この特徴空間から (1) 式を用いて第一主成分を求める
とき, 素朴な実装だと, 特徴空間に O(|T |2 ) 個の要素を
持つため, DTD を dTD (T1 , T2 ) に要する計算量とする
と, 合計で O(|T |3 DTD ) の時間が必要となる. 本節で
は, |T | に対して線形なアルゴリズムを提案する.
また, 木 T = (V, E) 中の部分木 t = (V ′ , E ′ ) に対し
て, (V \ V ′ , E \ E ′ ) を T \ t と記す. このとき, 任意の木
構造 T1 , T2 に対して, MTD (T1 , T2 ) = LCSTTD (T1 , T2 )
が成立するため, Algorithm 2 に従った super tree ST
が構成できる. 三つの木構造から構成される super tree
の例を図 2 に示す. ここで, 木 T = (V, E) と, ノード v
− 65 −
Algorithm 2 Super tree の構成
Algorithm 3 Super tree からの主成分抽出
INPUT : 木集合 T = {T1 , . . . , Tn }.
ST ← Σ 以外のラベルを持つダミーノード d.
ST ← 根ノード d に T1 を連結.
for t ∈ T \ {T1 } do
for T ∈ ST [d] do
if LCST(t, T ) ̸= ϕ then
Lt ← t \ LCST(t, T ) の親ノードの集合 .
for v ∈ Lt do
ST 中の v に t[v] を連結.
end for
Break the inner loop.
end if
end for
end for
OUTPUT : ST .
INPUT : Super tree ST = (VST , EST , rST ).
PC ← ϕ
/*P C は主成分を表す木構造*/
s ← rST
/*s はスタック*/
while s is not ϕ do
v ← Popping s
for c ∈ child(v) do
if 2w1 (c) > w2 (c) then
P C が ST の部分木となるように c を連結.
s にノード c を追加.
w1 (c) ← 0 に更新.
end if
end for
end while
OUTPUT : PC .
に対して,
{
δ(v, V ) =
1
0
if v ∈ V,
otherwise.
b
c
と定義したとき, ST = (VST , EST ) の各ノード v に, 以
下の定義に従う二つの重み w1 (v), w2 (v) を与える.
∑
w1 (v) =
δ(v, MTD (T, ST )|ST )
(2)
T ∈T
w2 (v) =
∑
δ(v, VST \ MTD (T, ST )|ST )
(3)
T ∈T
第一主成分は (2) 式と (3) 式を用いて以下のように求
めることができる.
P C1 (T , TD) = arg max
∑
T ∈ACTD (ST ) v∈T
{w1 (v) − w2 (v)} −
⇔ P C1 (T , TD) = arg max
∑
T ∈ACTD (ST ) v∈T
∑
w1 (v)
v∈ST \T
{2w1 (v) − w2 (v)}
(4)
このことから, 図 2 の例では, 黒点部分からなる部分木
を主成分として抽出することができる. この重みを全
て与えた ST から第一主成分を抽出する効率的なアル
ゴリズムを Algorithm 3 に示す. また, 第 k 主成分抽
出のためには, 第 k − 1 成分までで抽出した ST 上の部
分木中のノードの重み w1 を 0 に変え, 第一主成分と同
様に Algorithm 3 を用いて求めることができる.
3.2
rev(T )
T
a
b
e
b
e
b
dummy
c
dummy
dummy
b
b
a
a
a
図 3: 入力データの木 T に対する rev(T ) を表す. rev(T ) の
黒点部分からなる部分木を, R′ に基づく rev(T ) のマッピン
グの対象としたとき, その等価なマッピングの対象が T の黒
点部分からなる部分木の集合である.
ドに対して T [v] の最大の深さ dep(T [v]) を定義する. T
を帰りがけ順に走査していき, そのときのノード v の深
さが dep(T [v]) と等しくなるまでダミーノードを加え
た木を T ′ とおく. T ′ を根ノードから各葉ノードまでの
パスに分解して, 親子関係が逆になるように全てのパス
を反転させ, それらをダミーノードに連結した木 Tr′ を
構成する. そして, Tr′ を Algorithm 1 に従って縮約し
た木を rev(T ) と定義する. その rev(T ) の例を図 3 に
示す. また, rev(T ) = {rev(T ) | T ∈ T } と定義する.
本節では TD に以下の制約を加えた制約を TD′ と定
義する. 入力データ集合 T に対して, T1′ , T2′ を rev(T )
′
中の木構造とする. このとき, ∀v ∈ MTD (T1′ , T2′ )|Ti (i =
1, 2) に対して,
{w | w ∈ Ti′ ∧ dep(v) = dep(w) ∧ α(v) = α(w)}
ボトムアップマッピングに基づくアルゴ
リズム
本節では, ボトムアップマッピングに基づき, 任意形
状の部分木を抽出する効率的な Tree PCA のアルゴリ
ズムを提案する. 木 T = (V, E) に対して, 新たな木
rev(T ) を構成する手順を示す. まず, v ∈ V 中の各ノー
dummy
= {w | w ∈ Ti′ ∧ dep(v) = dep(w)}
を満たす. このとき, BU を置換を考慮しないボトム
アップマッピングの制約としたとき, BU に基づくマッ
ピングと, rev(T1 ), rev(T2 ) 間の TD′ に基づくマッピン
グを, 基の T1 , T2 に当てはめ直したマッピングは T1 , T2
− 66 −
が縮約の前処理を行っているとき等しい. 図 3 に具体
例として, T の BU に基づくマッピングの対象となる
部分木と, それと等価な rev(T ) の R′ に基づくマッピ
ングの対象となる部分木の例を示す.
rev(T ) の定義を用いることで, T の特徴空間 T SBU
は
T SBU (T ) = {LCSTBU (s, t) | s, t ∈ T ∪ {ϵ} ∧ s ̸= t}
⇔ T STD′ (T ) = {LCSTTD′ (s, t) | s, t ∈ rev(T ) ∪ {ϵ} ∧ s ̸= t}.
と導くことができる. 上式と (4) 式から, 以下の式を導
くことができる.
∑
PC 1 (T , BU) ≡ arg min
dBU (T, PE (T ))
5
本稿では, 複数の木構造データ集合から Tree PCA の
スキーマに従った, 全ての入力データ間の最大共通部
分木を基にした主成分を抽出する二つのアルゴリズム
を提案した. この二つのアルゴリズムはトップダウン
マッピングとボトムアップマッピングの制約に従って
いる. 素朴な実装では, 全ての入力データ間の最大共通
部分木を求めるだけで O(|T |2 ) の計算量が必要である
が, 主に以下に示す二つの貢献により, |T | に対して線
形時間で主成分を抽出する効率的なアルゴリズムを提
案することができた. その貢献とは,
1. T に対するトップダウンマッピングを基にした
O(T ) の時間計算量しか要さない super tree の
構成.
E∈T SBU (T ) T ∈T
⇔ P C1 (T , TD′ ) =
arg max
T ∈ACTD′ (ST )
∑
{2w1 (v) − w2 (v)}.
v∈rev(T )
2. ボトムアップマッピングを用いたアルゴリズムの
場合, トップダウンマッピングと同様のアルゴリ
ズムを用いることが可能な, BU の制約と等価な
マッピングの制約 R′ の提案.
このことから, BU に基づくマッピングに従った主成分
も前節と同様に, Algorithm 2 と Algorithm 3 を用いて,
|T | に対して線形時間で求めることができる.
4
まとめ
実験
実際に KEGG/GLYCAN データベースから取得した
糖鎖のデータセットを用いて実験を行った. 用いたデー
タセット中のデータは Leukemic, Erythrocyte のいず
れかのクラスに分類されており, それぞれ, 140,127 の
データ数を持つ. 糖鎖データは各ノードと枝にラベル
が付与されているが, 本稿では [3] と同様に, 枝のラベ
ルをその枝の子ノードのラベルとみなす. また, 本稿で
は糖鎖データはラベル付き根付き無順序木とみなす.
提案手法と [8] によって実際に得られた主成分を比較
する. [8] では, 全ての木構造をパスに分解した後, それ
らのパス間のトップダウンマッピングを共通部分とし
た super tree を構築していた. この super tree は, 提案
手法での Algorithm 1 によって構成される super tree
と形状は同じである. まず, 図 4 に [8] で得られた super
tree と, 主成分を表すパスを示す. 図 5 に提案手法で得
られた super tree と主成分を表す部分木を示す.
図 4 と図 5 の結果から, 共通する枝分かれの構造を
多く持つ Leukemic に対しても [8] では主成分としてパ
スしか抽出していなかったが, 提案手法では, 枝分かれ
を持つ構造を主成分として抽出できていることがわか
る. また, [8] では, 葉ノード側の重要度の低い構造を
含んだ根から葉までのパスしか抽出することができな
かった. これに対して, 提案手法ではそのような重要度
の低い部分構造以外の特徴的な部分構造のみを抽出で
きることが Erythrocyte の結果から分かる.
である. また, 提案手法を実データに適用し, 実際に主
成分を抽出することで [8] よりも特徴的な部分木を抽出
できることを示した. 今後の課題として, 既存手法との
精度比較を行うことが挙げられる.
謝辞
本研究の一部は，JST、CREST の支援を受けたもの
である.
参考文献
[1] C. A. Alfaro, B. Aydn, C. E. Valencia, E. Bullitt, and A. Ladha. Dimension reduction in principal component analysis for trees. Computational
Statistics and Data Analysis, 74:157 – 179, 2014.
[2] B. Aydin, G. Pataki, H. Wang, E. Bullitt, and
J. S. Marron. A principal component analysis for
trees. Ann. Appl. Stat., 3(4):1597–1615, 12 2009.
[3] T. Kuboyama, K. Hirata, K. F. Aoki(Kinoshita),
H. Kashima, and H. Yasuda. A gram distribution kernel applied to glycan classification and motif extraction. Genome Informatics, 17(2):25–34,
2006.
[4] K.-C. Tai. The tree-to-tree correction problem. J.
ACM, 26(3):422–433, 1979.
− 67 −
(a) Leukemic
(b) Erythrocyte
図 4: それぞれ, Leukemic と Erythrocyte の super tree を表す. 一番目の太線と二番目の太線が, それぞれ [8] での第一主成
分のパス, 第二主成分のパスを表す.
(a) Leukemic
(b) Erythrocyte
図 5: それぞれ, Leukemic と Erythrocyte の super tree を表す. 太線部分はそれぞれ提案手法での第一主成分を表す.
[5] G. Valiente. An eﬃcient bottom-up distance between trees. In SPIRE 2001., pages 212–219, 2001.
[6] H. Wang and J. S. Marron. Object oriented data
analysis: Sets of trees. Ann. Statist., 35(5):1849–
1873, 10 2007.
[7] J. T.-L. Wang and K. Zhang. Finding similar
consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34(1):127–
137, 2001.
[8] T. Yamazaki, A. Yamamoto, and T. Kuboyama.
Tree PCA for extracting dominant substructures
from labeled rooted trees. In Discovery Science,
volume 9356, pages 316–323. Springer, 2015.
− 68 −

Download Report