DEIM Forum 2017 F7-4

最適な順序付き決定木の高速発見とその文書分類への応用
長部 和仁†

宇野毅明††

有村 博紀†† 北海道大学情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目†† 国立情報学研究所 〒 101-8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{kz-osabe,arim}@ist.hokudai.ac.jp, ††uno@nii.jp
あらまし

本研究では，分類ラベル付きの二値データベースから，制約をみたし，データ中での分類誤差を最小化す

るような決定木を厳密に求める問題，およびそれを用いた文書分類問題を考察する．変数順序なし決定木の族 DT に対して，Nijssen らは，頻出アイテム集合マイニングを応用した網羅的探索を用いて，訓練集合中で識別精度最大の決定木を求めるアルゴリズム DL8 を与えた．しかし，DL8 は大きな時間計算量と空間計算量を要するため，大規模なデータに適用することは困難である．そこで本研究では，決定木の部分族として，決定木中のすべてのパスの順序を一意に固定した順序付き決定木 (ordered decision tree) の族 OT を導入し，この族 OT に対して制約を満たす最適決
定木を効率良く計算するアルゴリズム ODT を提案する．また，ODT アルゴリズムに対し，データベース縮約による処理の効率化と，データの不均衡に応じた重み付けを導入する．実験では，Bag of Words 形式の文書集合とアイテム集合形式のデータセットの関係に着目し，ODT アルゴリズムを用いたラベル付き文書集合の分類を行うことで，分類過程の解釈可能性，実行効率，および不均衡データへの対応における提案手法の有効性を検証する．
キーワード

決定木, パターン列挙, 頻出アイテム集合, データマイニング, テキストマイニング, 文書分類

1. は じ め に
近年，実務的な機械学習の領域において，識別精度の向上だ

一つも発見できなかったとしても，制約を満たす木が存在しないとは限らない．実際は算出可能な木に対し，単にヒューリス
ティックが到達しなかったというケースがありうる．

けではなく，なぜそのような識別結果が出たのか，その過程をこれに対し，2007 年に Nijssen らは DL8 という最適決定木

明確にすることが求められている．この点において，深層学習の厳密発見アルゴリズムを提案した [5]．このアルゴリズムは，などの精度に優れる機械学習の手法の一部は，直感的に理解しとりうるすべての木を網羅的に探索することで，訓練集合に対にくい識別過程を持つため，そうした実務上の解釈可能性の要する識別精度最大の決定木を，与えられた制約のもとで厳密に請にそぐわない場合がある．

発見することができる．

一方で，解釈可能性の高さで注目されているのが，決定木のDL8 は枝刈り条件の導入などにより効率的に網羅的な探索を手法である．決定木は，木構造で識別過程を可視化できるため，行うことができるが，速度やメモリの面で課題が残り，データあるデータがなぜそのラベルに分類されたかを人間が理解するセットによっては上手く動作しないことが著者らの論文においことが容易である．こうした点に着目し，Eto, Fujimaki らはて述べられている [6]．

2014 年に異種混合学習と呼ばれる学習モデルを提案した [2]．

1. 2 研 究 目 的

これは，決定木をベースに識別器を構成することで人間可読な以上のように，従来の決定木構築アルゴリズムのうち，C4.5

識別過程を担保し，決定木の各葉に対して回帰モデルを割り振などのヒューリスティックに基づくものは高速だが，探索の網ることで，解釈可能性と識別精度の両立を図るものである．

羅性がなく算出する解の精度に問題がある．一方で，DL8 は厳このような背景から，より高性能な決定木構築アルゴリズムの開発が期待されているといえる．

1. 1 関 連 研 究

密な最適解を発見できるが，実行上の効率の面で問題を抱えているということがいえる．
単一の決定木の精度を向上させる場合，訓練集合に対して精現在広く利用されている決定木アルゴリズムとして，C4.5 な

度最大な決定木を厳密発見できる DL8 は望ましいが，その一どのヒューリスティックに基づくものがある [7]．C4.5 は，決方で，決定木構築にかかる時間計算量，空間計算量があまりに定木の各ノードを，ジニ係数やエントロピーなどの情報理論的大きい場合，実務領域での利用が困難になる．

スコア関数に基づいて選択する．

こうした背景から，我々は，精度と計算効率の両面で，より適こうしたアルゴリズムはトップダウンの形で高速かつ省メモ

切な位置づけのアルゴリズムを開発する．C4.5 のようなヒュー

リに決定木を構築できる一方で，網羅的な探索を行っておらリスティックよりも高精度であり，DL8 のような厳密発見手法

ず，精度の最適性の保証を持たない．例えば，訓練集合に対し，よりも省メモリであるアルゴリズム ODT を提案する．

C4.5 が算出した木よりも高い精度を実現する決定木は存在しまた，提案アルゴリズムを用いて，文書分類の実験を行う．

うる．また，C4.5 が訓練集合からある制約条件のもとで木を既存アルゴリズムと提案アルゴリズムの精度・計算効率の比較

を行い，実際に分類過程の可視化を試みることで，アルゴリズ

ンを全て出力する問題である．

ムの有効性を検証する．

［定義 2］（頻出アイテム集合マイニング問題） 入 力 と し て 二

2. 準

備

2. 1 データベース

値データベース E ，制約パラメータとして最小頻度 σ ∈ [0..m]が与えられたとき，f reqE (p) >= σ となるようなすべてのパター
ン p を出力せよ．

I = {i1 , . . . , in } を n 個の変数からなる変数空間とする．n

頻出アイテム集合マイニング問題を解く代表的なアルゴリ

個の変数（またはアイテム）の組 x = (i1 , . . . , in ) を，タプル

ズムとして，Agrawal らによるアプリオリアルゴリズム [1]，(tuple) とよぶ．タプル空間を X ⊂=I とおく．
タプルに対し，正例または負例を表すブール値 y ∈ Y = {0, 1}

Bayardo らによるバックトラックアルゴリズム [3] などがある．
2. 4 決定木の族

を，分類ラベルとよぶ．タプルと分類ラベルの組 e = (x, y) を，

本稿では，頂点のテストとしてアイテムをもち，内部頂点の分類例（またはデータ）とよぶ．分類ラベル付きデータベース（ま分岐数が常に 2 である二分決定木のみを扱い，これを単に決定たはデータベース）は，m 個の例の組 E = {e1 , . . . , em }⊂=X ×Y木とよぶ．はじめに，変数順序を持たない順序なし決定木のクを指す．

ラス DT を導入する．

変数空間に含まれる変数の総数およびデータベース中の［定義 3］（順序なし決定木） アイテム集合 I 上の順序なし決

例数を，以後それぞれ n = |I| と m = |E| で表す．また，定木（decision tree）DT は，次のように定義される頂点ラベ

データベース中の個々の例 ei ∈ E の添字 i を TID とよび，

ル付き 2 分木 T = (V (T ), E(T ), root(T ), labelT ) である．

T id(E) := [1..m] で E の添字集合を表す．

•

V (T ) は頂点集合であり，E(T ) は 1-枝と 0-枝と呼ばれ

2. 2 パターンと出現リスト

る有向辺の集合である．唯一の入次数 0 の頂点 root(T ) ∈ V (T )I 上の論理式であるリテラルとパターンを定義する．

は根である．

各変数 i ∈ I に対して，その否定を ¬i と表記する．変数空•頂点集合 V (T ) は内部頂点と葉からなる．各内部頂点間上の任意のタプル x ∈ I について，x の i 番目の要素が 1 でv ∈ V (T ) は，1-枝と 0-枝と呼ばれる 2 つの有向辺をもち，そあるとき i ∈ x，0 であるとき ¬i ∈ x である．

れぞれ，1-子と 0-子と呼ばれる子 v.1 と v.0 へと接続する．各

変数とその否定をリテラル（literal）と呼ぶ．リテラルの全体集合を Σ := I ∪ ¬I とする．ただし，集合 ¬I := { ¬i | i ∈ I }である．

Σ 上 の サ イ ズ d の パ タ ー ンと は ，リ テ ラ ル の 有 限 集 合

葉 l ∈ V (T ) は枝および子をもたない．

•

関 数 labelT = testT ∪ classT は ，各 頂 点 に ラ ベ ル

を 対 応 づ け る ラ ベ ル 関 数で あ る ．各 内 部 頂 点 v に 対 し て ，labelT (v) = testT (v) は変数 i ∈ I を返す．各葉 l に対して，

p = {z1 , . . . , zd }⊂=Σ であり，リテラルの論理積 z1 ∧ · · · ∧ zd を表す．ただし，任意のパターンにおいて，変数 i とその否定 ¬ilabelT (l) = classT (l) は分類ラベル y ∈ Y を返す．

が同時に含まれることはない．したがって，任意のパターン pと定義する．決定木 T 中のパスを，T 中の根から任意のノーのサイズ |p| <= n = |I| である．

ド v までの連続する有向辺の列と定義する．パスの長さ |p| は，［定義 1］（リテラルとパターンの評価値） 任意のタプル x ∈パスに含まれる辺の総数である．決定木 T 中の任意のノード v

X に対して，x に対するパターン p の評価値 ϕp (x) ∈ Y = {0, 1}の深さは，根から v へのパスの長さである．

を次のように定義する:

決定木 T 中の内部頂点の集合を node(T )，葉の集合を leaf (T )決定木 T に対して，そのサイズを T の総頂点数 k(T ) =•変数 i ∈ I に対して，ϕi (x) := 1 ⇐⇒ i ∈ x.

•

変数の否定 ¬i ∈ ¬I に対して，ϕ¬i (x) := ¬ϕi (x).

パスの長さ d(T ) = maxp∈T |p|，葉数を T に含まれる葉の総数•

パターン p = {z1 , . . . , zd } = z1 ∧ · · · ∧ zd に対して，l(T ) = |leaf (T )| と定める．T はすべての内部頂点が 2 つの子

ϕp (t) := ϕz1 ∧ · · · ∧ ϕzd .
データベースまたはその部分集合 E におけるパターン p の出現リストとは，パターン p の評価値 ϕp (ti ) が真となる E の
添字の集合であり，OccE (p) := { i ∈ [1..m] | ϕp (ti ) = 1 } と定|V (T )| = |node(T )| + |leaf (T )| と定義し，その深さを最長のをもつ全二分木なので，常に k(T ) = 2l(T ) − 1 となる．

T.1 と T.0 で，それぞれ，根 root(V ) の 1 子と 0 子を根とす
る T の部分木を表し，T の 1 木と 0 木と呼ぶ．
決定木は，タプルに対して分類ラベルを返す分類関数と見る

義する．E 中のパターン p の頻度 (frequency) を f reqE (p) :=ことができる．

|OccE (p)| ∈ [0..m] とする．

［定義 4］（決定木が定義する分類関数） 決定木 T が定める分

以後，文脈から明らかならば，E とその添字集合 T id(E)，

類関数は関数 ψT : X → Y であり，任意のタプル x ∈ X に対しおよび添字集合 T id(E ′ ) と対応する E ′ ⊂=E 中の例集合を区別て ψT (x) := ψ(root(T ), x) と定義される．任意の頂点 v ∈ V (T )でのパターン p の出現を OccE ′ (p) などとも書く．

に対して，ψT (v, x) の値は次のように再帰的に定義される:

if v は葉, ℓ,

しない．出現リストは添字集合であるため，出現リスト E ′ 中

2. 3 頻出アイテム集合マイニング問題
二値データベース E において，出現頻度が閾値 σ 以上であるようなパターンを σ-頻出パターンとよぶ．頻出アイテム集合
マイニング問題とは，データベース E における σ-頻出パター

ψ(v, x) =ψ(v.1, x), ψ(v.0, x),

if v は内部頂点かつ t ∈ x,

(1)

if v は内部頂点かつ t ̸∈ x,

内部頂点 v に対して t := test(v) は I 上の変数であり，葉 v に表 1: サイズ n のデータベースにおいて決定木の予測関数 ψT が定め

ま る 変 数 間 の 全 順 序と す る ．ord(i) を 変 数 i の 変 数 順 序

る 2 × 2 分割表

番 号，ord−1 (j) を ord におけ る 第 j 番目 の 変数 と する と ，

ord−1 (1) <I · · · <I ord−1 (n) である．
変数順序 <I のもとで，順序付き決定木の族 OT を導入する．

ψT (x) = 1

ψT (x) = 0

y=1

m1

n1 − m1

n1

y=0

m0

m0 − m0

n0

m

n−m

n

(2)

［定義 6］ 決定木 T が順序付き (ordered) であるとは，I 上にある変数順序 ord が存在して，T 中の任意の根から葉までのパス上の変数が全順序 <I の昇順で並んでいることをいう．

対して ℓ := class(v) ∈ Y はクラスラベルである．上記の評価

以後，OT I,ord で，I 上の変数順序 ord にしたがう順序付きにおいて，ある頂点 v で式 ψ(v, x) が評価された場合に，タプ

決定木 (ordered decision tree) の族を表す．定義より，任意の

ル x は葉 v へ到達するという．

I
ord に対して OT I,ord ⊂=DT である．文脈より明らかな時には

データベース E における決定木 T の頂点 v の頻度を，v へ到達する E 中のタプルの総数 σE (v) ∈ [1..m] と定義する．Eにおける T の葉の最小頻度を，全ての葉に対する頻度の最小値

添字 I と ord を略する．

3. 先行研究：DL8 アルゴリズム
DL8 アルゴリズムは，Njissen らによって提案された，最適

σE (T ) := minv∈leaf (T ) σE (v) ∈ [0..m] と定義する．
以後，I 上の決定木（decision tree）の族を，DT I で表す．

決定木の厳密発見アルゴリズムである [5]．DL8 アルゴリズム

ただし，文脈上変数空間が明らかなとき，I を省略して DT とは，頻出アイテム集合マイニングが列挙するアイテム集合と決⊂書く．任意の部分族 C ⊂=DT に対して，Ck,d,σ =C で，サイズが定木のパスの関係性に着目し，訓練集合における精度最大の決

k 以下で，深さ d 以下，葉の最小頻度が σ 以上となる C に属す

定木を網羅的探索によって発見する．

3. 1 アイテム集合とパスの関係

る決定木の族を表す．

決定木 T 中のパスを考える．パス中の各有向辺は，隣接

2. 5 分類スコア
本節では決定木 T の分類スコアを導入する [4]．

する内部頂点のうち，より深さが浅い点 (始点)v のラベル

n 個の例を含むデータベース E を仮定する．本小節のみ，labelT (v) = testT (v) = i，またはその否定 ¬i がタプルに含まデータベース中の例数を n で表記するので注意されたい．
各例 e = (x, y) ∈ E に対して分類ラベル y ∈ Y と決定木 T
による予測ラベル ψT (x) ∈ Y を考えて，次のように非負整数
非負整数 n1 ，n0 は，それぞれ E 中の正例の数と負例のすべての例を振り分けることを考えると，T 中の任意の葉 ℓ に到達する例 e = (x, y) が満たすべき条件は，x が T 中の根から

数である．

•

パスはパターン p = {z1 , . . . , zd } によって一意に表現することができる．
このとき，決定木 T ∈ DT によって，データベース E 中の

n1 , n0 , m1 , m0 ∈ N を定める:•れるか否かの判定に対応する．したがって，決定木中の任意の非負整数 m1 ，m0 は，それぞれ予測ラベルが正の例のうち，E 中のラベルが 1 である例の数，0 である例の数である．
表 1 に，関連する 2 × 2 分割表を示す．n = n1 + n0 が成立

葉 ℓ までのパスに存在するすべての辺に対応するリテラルの集
合 p = {z1 , . . . , zd } を含むことと一致する．
［補題 1］ リテラルの全体集合 Σ におけるサイズ d のパターン

すること，および決定木による予測値が 0 となる正例の数，決の全体集合を PΣ (d) としたとき，PΣ (d) 上の長さ d の順列の定木の予測値が 1 となる負例の数はそれぞれ n1 − m1 と m0 と∗全体集合 PΣ(d) = perm(PΣ (d)) は決定木の族 DT における長なることは，定義より明らかである．

さ d のとりうるパスの全体集合 PDT (d) と等しい．

分類関数 ψT : X → Y と例 e = (x, y) ∈ X × Y に対して，

y ̸= ψT (x) のとき，e で誤分類（error）が起きたという．
［定義 5］（経験誤差と精度）サイズ n >= 0 の任意のデータベー
ス E⊂=X × Y に対して，分類関数 ψT の E における誤分類数を，補題 1 より，深さ d の決定木の族 DT ∗,d,∗ に存在しうるパス∪d∗i=1 PΣ (i) である．したがって，DT ∗,d,∗∗の全体集合は，PΣ
=∗における全ての木は PΣ
に含まれる要素の組み合わせで表現できる．また，データベース E に対する頻出アイテム集合

ψT の経験誤差 (empirical error) を，E における ψT による誤マイニングによって列挙される σ-頻出パターンの全体集合∪∗
を PΣ,σ= di=1 perm(p ∈ {PΣ (i)|f reqE (p) >= σ}) とすると，分類数の比率∗DT ∗,d,σ における全ての木は PΣ,σに含まれる要素の組み合わψT が誤分類した例の個数 #Err(ψT , E) とおき，E におけるErrn (ψT ; E) :=#Err(ψT , E)
∈ [0, 1]nせで表現できる．

(3)

3. 2 DL8 アルゴリズムの構造と定める．本節のように，Y = {1, 0} の 2 クラス分類の場

DL8 アルゴリズムは，前処理として頻出アイテム集合マイニ

合，分割表より，#Err(ψT , E) := (n1 − m1 ) + m0 ∈ [0..n]ングを実行し，その解集合をメモリ上に保持したうえで，制約である．さらに，E における ψT の経験精度（accuracy）をを満たす決定木を全て試す再帰手続きを行う．

Accn (ψT ; E) := 1 − Errn (ψT ; E) ∈ [0, 1] とおく．

［補題 2］ 決定木の族 DT における任意の決定木 T について，

2. 6 順序付き決定木の族

T の根の左右の部分木 TL と TR が，それぞれ T のとりうる全I 上の変数順序 (variable ordering) ord : [1..n] → [1..n]ての候補部分木の中で経験精度最大であるとき，T は DT 中では ，変 数 の 添 字 上 の 置 換 で あ る ．<I を ，ord に 対 し て 定

経験精度最大である．

Algorithm 1: アルゴリズム ODT
Algorithm ODT(I, ord, E, σmin , kmax , dmax )Algorithm 2: 再帰手続き RecODT
Procedure RecODT(p, Occ, tail , d, Θ)

Output: 最適木の根へのポインタ root、そのサイズ k、Output: サイズごとの最適決定木 τk からなる

経験誤差 err からなる三つ組 τopt = (root, k, err)

決定木プロファイル Opts = {τ1 , . . . , τkmax }

begin

begin

1

Θ := (σmin , kmax , dmax , m := |E|, n := |I|, I, ord, E);2p0 := ∅; T id(E) := [1..m]; tail0 := n, d0 := 0;

3

Opts := RecODT(p0 , T id(E), tail0 , d0 , Θ);2

y1 := arg maxy∈Y |Occy |; err1 := |Occ| − |Occy1 |;4

return τopt := arg minτ ∈Opts τ.err;

3

Opts := ∅; Opts[1] := a new leaf l with1

(σmin , kmax , dmax , m, n, I, ord, E) := Θ;// Step1: サイズ k = 1 の最適木を見つける

l.label := y, l.err := err1 ;補題 2 より，DL8 アルゴリズムは再帰的な分割統治法を用い

44. 提案手法：ODT アルゴリズム

5(O0 , O1 ) := OccDeliver(p.last, Occ, I);

6

for i := 1, . . . , tail do

DL8 アルゴリズムは制約のもとで経験精度最大の決定木を厳7

密発見することができるが，順列の全列挙に相当する大きな時8間計算量がかかり，頻出アイテム集合の総数に等しい数の候補
パスをメモリ上に保持するために，入力に対して指数的な空間

9Opts 1 := RecODT(p∪{item}, O1 [item],

10

Opts 0 := RecODT(p∪{¬item}, O0 [item],i − 1, d + 1, Θ);i − 1, d + 1, Θ);族を，ある変数順序のもとでの順序付き決定木の族に制約し，その中で経験精度最大の決定木を厳密発見することで，集合の11全列挙に相当する時間，および入力に対する多項式領域へと計算量を改善する [10]．

item := ord−1 (i);if (|O1 [item]| >= σmin ) and (|O0 [item]| >= σmin )then

計算量がかかる [6]．
我々が提案する ODT アルゴリズムは，対象とする決定木のif d + 1 > dmax then return Opts;// Step2: サイズ k > 1 の最適木を見つけるて経験精度最大の決定木を厳密発見することができる．

foreach τ1 ∈ Opts 1 and τ0 ∈ Opts 0 with
τ1 .k + τ0 .k < kmax do

12τ := a new optimal tree triple;

13

τ.k := 1 + τ1 .k + τ0 .k;［定義 7］（最適順序付き決定木発見問題） 順序付き決定木の14

τ.err := τ1 .err + τ0 .err;

族 OT に対して，入力として変数集合 I = {i1 , . . . , in } (n >
= 1)

15

if (Opts[k] = null) or

本研究で考察する問題は次のとおりである．

と，変数順序 <I ，I 上のデータベース E = {e1 , . . . , em }⊂=X ×>Y (m >
1)，制約パラメータとして最大サイズkmax== 0 と，>
最大深さ dmax = 0，葉の最小頻度 σmin ∈ [0..m] が与えられた
とき，制約を満たす順序付き決定木 T ∈ OT k,d,σ すべての中(τ.err < Opts[k].err) thenif (Opts[k] =| null) then16

DecNodeRefCount(Opts[k].root);

17

IncNodeRefCount(τ1 );18

で，経験誤差 Errn (ψT ; E) を最小化する順序付き決定木 Tmin

19

IncNodeRefCount(τ0 );を出力せよ．

20

τ.root := a new node v withOT ⊂=DT であるために，最適木発見のために OT において試
行すべき木の総数は DT におけるそれを下回り，問題の複雑性は減少する．一方で，OT における最大の経験精度は，DT の族における最大の経験精度よりも劣化しうる．

v.test := item, v.1 := τ1 , v.0 := τ0 ;Opts[k] := τ ;21

22foreach τ ∈ (Opts 1 ∪ Opts 0 ) do

23

DecNodeRefCount(τ.root);

4. 1 アルゴリズムの概要
図 1 に最適な順序決定木を計算する提案アルゴリズム ODT

24

return Opts;を示し，図 2 にその再帰手続き RecODT を示す．
アルゴリズム ODT は，頻出アイテム集合の列挙木をパスのイテムごとの出現リスト集合 O1 と O0 を計算した後に，自分探索空間として再帰的な深さ優先探索を行い，制約を満たす

自身を左右の子に対して再帰的に呼び出す．親へバックトラッ

OT 上の最適決定木を発見する．

クする際には，各サイズ k ごとに，ボトムアップに求めた最適手続き RecODT は，探索木の根となる空パターン ∅ から，パスとなるパターンを構築しながら，再帰的にアイテム集合束上

木のサイズ k ，最適スコア err ，最適木の根のポインタ root からなる 3 つ組 τ = (root, k, err) を返す．

を探索し，分割統治法を用いてボトムアップに最適決定木を求

手続き RecODT における各繰り返しでは，左右の子の候補めていく．手続き RecODT は，現在のパス p と，その出現リス

として，メモリ上に最大 kmax 個の決定木を構築し，それらをト Occ，および p に追加する候補アイテムの最大の添字 tail と組み合わせた木のうち，各サイズ毎に経験誤差が最小の木を選

再帰の深さ d を親から受け取り，Occ から二つの子のためのア

択して，最適木プロファイルに登録する．手続き RecODT の出現リストの振り分けを行う副手続き

Topt ∈ ODT Ik,d,σ を，O(N + k2 ) = poly(k, n, m) 作業領域

OccDeliver および、不要なメモリの回収を行う副手続きと O(M (N + nk 3 )) = O(M · poly(k, m, n)) 計算時間で出力

Algorithm 3:

IncNodeRefCount と DecNodeRefCount
Procedure OccDeliver(item, Occ, I)∪
Output: (O1 , O0 ) = ( t∈Occ,i∈I,i<I item {i | i ∈ t.x},∪/ t.x})t∈Occ,i∈I,i<I item {i | i ∈begin

する．ここで，n = |I| は変数の個数であり，m = |E| はデー
タベースの例数，N = O(mn) は E の総アイテム数であり，

M = O(2n ) は E における頻出パターンの総数である．
証明: まず，領域計算量について検討する．アルゴリズム Re-

cODT の入力となる構造体 Θ の領域計算量は，データベース E

1(O1 , O0 ) := (∅, ∅);の総要素数 O(mn) = N によって N に抑えられる．パス p の2for each t ∈ Occ do

長さは高々d < n，出現リスト Occ の長さは高々m，出現リス

3

for each i ∈ I such that i <I item do

ト集合 O1 , O0 の総要素数は合わせて mn である．候補木を格4

if i ∈ t.x then Add {i} to O1 [t] ;納する配列 Opts は，探索木のルートと，再帰のアクティブな

5

else Add {i} to O0 [t] ;深さに一つずつ存在し，それぞれ候補木へのポインタを k 個も6

return (O1 , O0 );Procedure IncNodeRefCount(v)の木のノード数は定義より O(k) である．前述の参照カウンタ
により，探索木のルートと，再帰のアクティブな深さの候補木

begin
7

つため，候補木配列に必要な領域は O(k) となる．また，個々

v.refc := v.refc + 1;
Procedure DecNodeRefCount(v)
begin

8

v.refc := v.refc − 1;9

if v.refc = 0 then10

DecNodeRefCount(v.0);

11

DecNodeRefCount(v.1);

12

delete v;

各繰り返しで親にバックトラックする前に，Opts1 ∪ Opts0 に含まれる部分木のうち，選択されなかったものすべてについて，参照カウンタを用いてそれらの頂点を削除することでメモリを回収する．

ODT の基本的なアイデアは次の通りである．

集合 Opts に含まれる以外の木は全てメモリから回収されるた
め，ある時点においてメモリ上に存在する実ノード数は O(k 2 )個である．したがって総領域計算量は O(N + k 2 ) 領域となる．
続いて，時間計算量について検討する．RecODT の探索木の総ノード数は頻出アイテム集合マイニングの解総数 M = O(2n )である．この M 個のノードそれぞれに，手続き RecODT の計
算時間がかかる．RecODT の各行のうち，5 行目の OccDeliverについては，|Occ||I| = O(mn) = N 時間がかかる．6 行目のループは O(n) 回，11 行目のループは O(k 2 ) 回実行され，17行目，22 行目の処理はいずれも O(k) 時間で実行できる．他の行の処理は全て定数時間である．よって，手続き RecODT にかかる計算時間は O(mn + n · k 3 ) 時間であり，アルゴリズム全体の総計算時間は O(M (N + nk 3 )) となる．以上で示された． □定理 1 より，ODT の時間計算量のオーダーは DL8 と同様に

まず，変数順序 ord を仮定することで，各パスについて，ア

入力サイズに対する指数時間である一方で，領域計算量は入力

イテム集合との一意な正規形を仮定できる．そのため，頻出ア

サイズの多項式メモリを達成し，DL8 の指数メモリに対して大イテム集合の列挙木と ODT の列挙木が一致し，パターンを列

幅な改善を行なっている．

挙しながら同時に決定木の構築を行うことができる．これによ

5. データベース縮約

り，DL8 が要していた，頻出アイテム集合マイニングの解集合を保持するための入力サイズに対して指数的な領域が不要にな

頻出アイテム集合マイニングにおいて，入力パラメータや制る．また，変数順序の導入により，頻出アイテム集合の列挙木

約条件を利用して事前にデータベースを圧縮する手法を，デーと ODT の列挙木を一致させることができる．こうすることで，タベース縮約とよぶ．

探索木のノードの個数が順列の総数から集合の総数へと減少し，
総実行時間の減少が見込まれるほか，頻出アイテム集合マイニ
ングで開発された様々な技術の流用や，双方のアルゴリズムで必要とされる情報の共有などが可能となる．

ODT アルゴリズムの実装では，Uno らの 2004 年の論文に示されるデータベース縮約の手法 [9] を取り入れている．
まず，ODT の入力パラメータのうち，葉の最小頻度 σmin が定まると，頻度が σmin 未満または 1 − σmin より大きい全ての

4. 2 アルゴリズムの計算量

アイテム，およびそれを含むアイテム集合が候補パスとならな

本小節では，アルゴリズム ODT の計算量を解析する．

いことが直ちにいえる．したがって，アルゴリズムを実行する［定理 1］（ODT の計算量） 順序付き決定木の族 OT に対し前に，前処理として頻度制約を満たさないアイテムをデータて，図 1 のアルゴリズム ODT は，変数集合 I と，変数順

ベースから削除しても，得られる解は同一となる．

序 ord，入力データベース E ，制約パラメータとして最大サ

また，このようにしてアイテムを削除したデータベース中に，

イズ k >= 0，最大の深さ d >= 0，葉の最小頻度 σ ∈ [0..m]

タプルとラベルの構成が全く同じである例が生じることがある．

を受け取り，与えられた制約を満たす全ての可能な順序付

こうした同一の例を一つにまとめ，まとめた個数分の重みで扱き 決 定 木 の 中 で ，経 験 誤 差 を 最 小 化 す る 順 序 付 き 決 定 木

うことで，アルゴリズム中で走査するデータ数を減らしつつ，

Algorithm 4:

表 2: データセットの属性

重み付きエラー導入時の RecODT の 2

|E|

|I|

行目

name

// Step1: サイズ k = 1 の最適木を見つける∑
y1 := arg maxy∈Y ( ey ∈Occy w[ey .label]);∑∑err1 := ( e∈Occ w[e.label]) − ( ey ∈Occy w[ey1 .label]);MBSM 374 2611 29

345

CORP

329

1

1

同一の結果を得ることができる．

ODT では，データベースの読み込み時にそれぞれのアイテ
ムの頻度を数え上げ，頻出でないアイテムはメモリ上に格納せず除外して処理する．さらに，非頻出なアイテムを除いたデー
タベースのうち，タプルとラベルが同一のデータは一つに縮約し，計算時にそのデータ一つの重みを縮約した個数倍して扱う．
データベース縮約によってアルゴリズムの最悪時計算量は変化しないが，特に σmin が大きい場合に，候補アイテムの総数とデータ件数を削減し，時間計算量とメモリ使用量を減少させることができる．

6. 不均衡データに対する重み付け
訓練集合中の分類ラベルのごとのデータ数に偏りのあるデー
タを，不均衡データとよぶ．不均衡データ上で分類誤差を基準にモデル選択を行うと，誤差は小さいものの，識別モデルとしての意味が薄い学習結果が生じる場合がある．たとえば，正例と負例の割合が 1:9 であるようなデータベースに対して決定木学習を行うと，全ての要素を負とするサイズ 1 の木が，精度 90％を達成するモデルとして選択されてしまうことが考えられる．

正例 負例

374 2611 45

ブラリ長ぶんの二値ベクトルを生成する．
このとき，BoW 構築に用いる単語のボキャブラリをアイテ
ム空間 I に，BoW の各単語をアイテムに対応させると，任意の BoW はタプルとみなすことができる．
それぞれの BoW に，文書が所属するカテゴリを示すラベルを紐付けた識別ラベル付き文書集合を考えると，これは ODTが入力として受け取るデータベースと同一の形式とみなすことができ，単語の有無の情報を用いて文書分類を行う決定木を，ODT アルゴリズムによって学習することができる．

8. 実

験

提案手法 ODT を用いた文書分類の実験を行う．

8. 1 デ ー タ
実験対象の文書集合として，DEIM2016（注 1） の最終論文集を用いた．論文集のうち，pdf が存在する日本語の論文のみを選
び，タイトル・アブストラクト・キーワードを抽出したものを文書とする．これを形態素解析ソフト MeCab（注 2） によって分か
ち書きし，BoW 表現に変換したものをタプルとして用いた．タ
プルに対し，以下の分類ラベル列を用意した．

•

マイクロブログ・ソーシャルメディア (MBSM): DEIM2016

このモデルは，正例と負例の比率が既知であれば自明であり，のセッション表で，「マイクロブログ分析」1〜3 か，「ソーシャ

また正例の予測には全く役立たない．負例を誤って正例として

ルメディア」1〜3 に登録されていれば 1，さもなくば 0

しまう偽陽性 (false positive) の削減よりも，存在する正例を見逃してしまう偽陰性 (false negative) を減らすことに重きが置•

企業 (CORP): 論文のいずれかの著者の所属が企業またはその研究所であれば 1，さもなくば 0

かれる応用では，こうした学習結果は望ましくない場合がある．

各タプルに上記の分類ラベルをそれぞれ割りつけたものを同

このような不均衡データに関する問題に対して，いくつか名の分類ラベル付きデータベースとし，決定木学習を行った．

のアプローチが提案されている [8]．データレベルのアプロー
チには，正例を水増しする over sampling，負例を間引く undersampling などがあり，アルゴリズムレベルのアプローチには，
データベース中のラベル分布の偏りに応じて各訓練データの重みを補正する重み付け (example weighting) などがある．

8. 2 プログラム
使用したプログラムは次のとおりである．

•

ODT: 4. 節のアルゴリズム ODT を C++で実装したもの．最適化手法として，4. 節に述べた Occurrence Deliver とODT アルゴリズムはデータベース縮約の同一データ縮約に

データベース縮約を組み込んだ．候補アイテムの順序としては，

より既にそれぞれのデータに対する重み情報を持っており，自データベース中のアイテムの頻度が大きいものからの降順を採然な拡張で重み付けの補正を導入できる．ODT アルゴリズム用している．

に対して，重み付けの補正を導入した際に，アルゴリズム 2 の•ODT-W: ODT に対し，6. 節で述べた重み付け補正を加2 行目を書き換えたものをアルゴリズム 4 に示す．ここで，w

えたもの．補正として，訓練データの正例の重み合計と負例のは分類ラベルごとに設定する重みの配列である．

重み合計が等しくなるような w を設定している．

7. ODT アルゴリズムによる文書分類
BoW (Bag of Words) は，文章にある単語が含まれていれば
1，そうでなければ 0 を格納したバイナリ列によって文章を表•DL8: 文献 [5, 6] の著者らによるオリジナルの C++実装

を入手して用いた．

•

C4.5: データマイニングツール Weka（注 3） に搭載されている C4.5 の Java 版実装である J48 を用いた．

現する文書モデルである．BoW の構築にあたっては，単語集合であるボキャブラリを用意し，ボキャブラリ中のそれぞれの語（注 1）：http://db-event.jpn.org/deim2016/

が含まれているか否かを 1 または 0 で表現することで，ボキャ（注 2）：http://taku910.github.io/mecab/（注 3）：http://www.cs.waikato.ac.nz/ml/weka/表 3: 決定木学習に要した実行時間 (sec)

MBSM

CORP

σmin

ODT DL8 C4.5

ODT

DL8 C4.550

0.16 0.65

2.59

0.15 15.69

2.43

40

0.93 −(b)

2.61

0.92

−(b)

2.64

(b)

2.78

30

4.71 −

(b)

2.76

4.61

−

20

62.33 −(b)

2.77

52.69

−(b)

2.84

10

577.96 −

−

(b)

3.10

図 1: MBSM データセットに σmin = 10 でセットに σmin = 5 でODT を適用した結果得た木の一覧

C4.5 を適用した結果(b)2.85 562.21

5−(a) −(b)

3.46

−(a)

−(b)

3.99

2

−(a) −(b)

4.03

−(a)

−(b)

4.90

図 2: MBSM データ

得た木の設定では 600 秒以内に実行が完了しなかった．C4.5 は常にパラメータに線形程度のごく短時間で実行が完了している．

表 4: 最大経験精度とその際の木サイズ

MBSM
σmin

ODT

以上の結果より，DL8 アルゴリズムはメモリ使用量の面で本

CORP
C4.5

Accn

k

Accn

50

0.8797

1 0.8797

40

0.8797

30

ODT
k

Accn

研究の実験に適さないこと，および実行時間の面では ODT に

C4.5
k

Accn

k

1 0.9225

1 0.92251

1 0.8797

1 0.9225

1 0.922510.8797

1 0.8797

1 0.9251

7 0.92251200.8797

1 0.8797

1 0.9305

7 0.92251

100.8957

7 0.8797

1 0.9332

7 0.92251−(a) −(a) 0.9305

3比して C4.5 が優れていることがわかる．

8. 4 実験 2：経験精度と木サイズ
メモリ使用量の面で実験に適さないとわかった DL8 アルゴ
リズムを除き，ODT アルゴリズムと C4.5 アルゴリズムについて，経験精度と出力された木を比較する．表 4 に，学習の結果得られた木の経験精度とサイズを示す．

6. 節の議論より，サイズ 1 の木は自明な木であり，学習結果

5−(a) −(a) 0.89572−(a) −(a) 0.9519 41a: 実行時間 600 秒を超えたため未計測分割を決定するために用いられる最小データ数を制約している．

b : 使用メモリ 64GB を超えたため実行不可

分割を決定する例数が少ないことは，過学習のリスクを高める

7−(a) −(a) 0.9599 19として意味が薄い．また，σmin は一つの葉に分類される最小データ数を制約するパラメータであり，同時に決定木の一つのため，より大きな σmin パラメータで，サイズ 1 よりも大きい
可視化時の解釈可能性と実行速度を考慮し，ODT および DL8木が得られることが分析上望ましい．

には，木のサイズ制約 kmax として 7 を指定した．C4.5 には木

この観点では，ODT は網羅的探索により C4.5 よりも大きな

サイズ制約のパラメータが存在しないため，サイズ制限は与え

σmin で非自明な木を得られており，アルゴリズムの有効性がず，ヒューリスティックによる探索が終了するサイズまで実行確認できる．一方で，C4.5 は ODT が時間的に実行困難なパラしている．

メータでも動作し，サイズは大きいものの，経験精度の高い木

実験環境は，PC（CPU Intel Core i7 3.3GHz, Memory 64GB,

OS Ubuntu 14.04）, コンパイラ g++ ver4.8.4 を用いた．

を得ることができている点で優れているといえる．
図に，MBSM データセットに σmin = 10 で ODT が算出し8. 3 実験 1：実行効率

た木，および σmin = 5 で C4.5 が算出した木を示す．ODT は，

MBSM および CORP のデータセットについて，それぞれ一度の実行で経験精度最大の木をすべてのとりうる深さについ

ODT，DL8，C4.5 の３つのアルゴリズムで決定木の学習をて出力することができるため，３種類の木を出力している．サ行った．

イズ 7 の木を解釈すると，「投稿」を含み，「検索」を含まず，「問

速度に関する実験結果を表 3 に示す．まず，DL8 アルゴリズ

題」を含むデータはマイクロブログ・ソーシャルメディアカテ

ムは，ほとんどの実験設定において実験環境上限の 64GB 以上

ゴリであるという決定木になっている．マイクロブログの根幹のメモリを消費し，動作しなかった．これは，本稿の実験で用をなす「投稿」という単語を根に持つのは対象カテゴリ上自然

いたデータセットのアイテム種別数が約 2600 と通常の頻出マイであり，「検索」を含まないのはこの語を含む論文は情報検索のニング用データセットに比して多く，前処理のアイテム集合列

セッションに割り振られているためであると推測できる．
「問題」

挙によって生じる解の個数（アイテム種別数 n に対して O(2n )）に関しては普遍的な語であるため，過学習の可能性も考えられが膨大になっているためだと考えられる．一方で，ODT は前処る．C4.5 が算出した木は，「フォロー」という，マイクロブログ

理の結果をメモリに保持せず実行しており，データベース縮約サービスである Twitter（注 4） の機能名を含むものをクラス 1 にで制約を満たさないアイテムを除去しているため，また，C4.5

割り振っており，直感的な結果である．

はヒューリスティックにより全解探索をしていないためこうし8. 5 実験 3：重み付けによる出力木の変化た問題を回避できている．

実験で用いている NBSM および CORP のデータは，いずれそれぞれのアルゴリズムの実行時間については，ODT はパラ
メータの変化に対して指数的に実行時間が増加し，σmin = 5, 2

（注 4）：http://twitter.com/

く手法を考察した．
実験の結果，Bag of Words 形式の文書のように候補アイテム
数が多くスパースなデータにおいて，ODT アルゴリズムは最小例数制約の変化に対して指数的な時間計算量がかかるが，最小例数制約の大きい設定でも有意味な木を発見できること，一方で既存研究である C4.5 アルゴリズムは高速であるが，最小例数制約を小さくしなければ有意味な木を発見できないことを
図 3: CORP データセットに σmin = 50 で ODT-W を適用した結果得た木の一覧

確認した．また，DL8 アルゴリズムは候補アイテム数が多い設
定ではメモリ消費が大きく動作困難であることがわかった．
本稿の実験では，一種類の実データのみを用いたため，実験の網羅性に欠けているほか，データ件数の少なさと不均衡性により，テスト精度の計測ができていない．したがって，より適切なデータを用いた実験が求められる．
また，タプルに連続値を含むデータベースに対応したアルゴ

図 4: MBSM データセットに σmin = 10 で ODT-W を適用した結果得た木の一覧

リズムの改良や，ODT アルゴリズムによって発見した決定木を複数組み合わせたモデルによる精度向上，より効果的な辞書
順の発見などは，今後の課題である．

も 6. 節で述べた不均衡データであり，例の割合が負例に偏っている．前小節の実験において，高い σmin の設定でサイズ 1 の自謝辞

明な木が出力されてしまうのは，こうしたデータの偏りによる．

第一著者の長部および第三著者の有村は，産業技術総合研究

ここでは，ODT に対して，訓練データの正例の重み合計と所の瀬々 潤氏，東京大学大学院の津田 宏治氏，寺田 愛花氏，

負例の重み合計を等しくするような重みベクトル w = (1, yy01 )美添 一樹氏に は，データベースからの決定木構築および，木を設定した ODT-W を用いて分析を行い，不均衡データに対す探索を用いたパターン発見，大規模化について，また東京大学

る対策を試みた．実験の設定上，ODT が算出する木はエラー

大学院の小宮山 純平氏および湊基盤 S プロジェクトの石畠 正

数最小ではなく，エラーにかかる重みの総和最小となるため，

和氏には，頻出アイテム集合発見の信頼度解析について貴重な最大の精度の木といった捉え方ができなくなり，精度の定量的ご議論とご教示をいただきました．ここに謝意を表します．

評価が難しくなる．したがって，本稿では，いくつかの出力解の例を示すに留める．
図 3 は，CORP データセットに σmin = 50 で ODT-W を適用して得た木の一覧である．同一のパラメータでは，ODT,DL8,C4.5のいずれもサイズ 1 の木しか算出することができなかったが，

ODT-W では重み付けにより，有意味な木を算出できている．
各ノードには，「精度」「分析」「確認」「データ」など，データ分析に関する用語が並び，それらのクラスが 1 に割り振られている．ここから，企業に所属する著者を含む研究グループの関心がデータ分析に向いていることが推察される．
図 4 は，MBSM データセットに σmin = 10 で ODT-W を適用して得た木の一覧である．前節に記載した重みなしの分析結果と比べ，語の構成がやや変化している．
「投稿」を含むものを

1 に割り振るのは同様だが，「調査」「明らか」という語もクラス
1 への割り振り条件になっている．マイクロブログやソーシャ
ルメディアを扱う論文が，何かを「調査」し，「明らか」にする傾向を持っていると考えれば，筋の通る結果であるといえる．

9. お わ り に
本稿では，決定木の部分族である順序付き決定木の族 OTに対して，入力の多項式領域のメモリしか用いずに，先行研究

DL8 と同一のオーダーの時間計算量で，制約を満たす最適決定
木を厳密に発見する提案アルゴリズム ODT を与えた．また，
提案アルゴリズム ODT を用いて，文書分類問題を効率的に解文

献[1] R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In Proc. the 20th International
Conference on Very Large Data Bases (VLDB’94), pages 487–
499. Morgan Kaufmann, 1994.
[2] R. Eto, R. Fujimaki, S. Morinaga, and H. Tamano. FullyAutomatic Bayesian Piecewise Sparse Linear Models. Proc.
AISTATS, 33:238–246, 2014.
[3] R. J. B. Jr. Eﬃciently mining long patterns from databases.
In Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD’98), pages 85–93. ACM Press, 1998.
[4] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundationsof machine learning. MIT press, 2012.
[5] S. Nijssen and E. Fromont. Mining optimal decision trees fromitemset lattices. In Proc. the 13th ACM SIGKDD int’l. conf. on
Knowledge Discovery and Data Mining, pages 530–539. ACM,
2007.
[6] S. Nijssen and E. Fromont. Optimal constraint-based decision
tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21(1):9–51, 2010.
[7] J. R. Quinlan. C4.5: programs for machine learning. Morgan
Kaufmann,, 1993.
[8] Y. Sun, M. S. Kamel, A. K. Wong, and Y. Wang. Cost-sensitive
boosting for classification of imbalanced data. Pattern Recognition, 40(12):3358–3378, 2007.
[9] T. Uno, M. Kiyomi, and H. Arimura. LCM ver. 2: Eﬃcient
Mining Algorithms for Frequent / Closed / Maximal Itemsets.
Workshop on Frequent Itemset Mining, 2004.
[10] 長部 和仁, 宇野 毅明, and 有村博紀. アイテム集合列挙に基づく
最適な順序付き決定木の高速発見. Technical report, 人工知能基本問題研究会資料 102, 人工知能学会 SIG-FPAI, 2016 年 12 月.