決定木（１） - 数学、ときどき統計、ところによりＩＴ

データの分類に使われる代表的なアルゴリズムの1つである決定木を取り上げます。

各 $\mathcal{X}_{j}$ ( $j=1$ , 2, $\ldots$ , $k$ ) を質的データまたは量的データとし、 $k$ 個の説明変数 $\mathcal{X}:=$ $\mathcal{X}_{1}$ $\times$ $\mathcal{X}_{2}$ $\times$ $\ldots$ $\times$ $\mathcal{X}_{k}$ を持つ $n$ 個の対象が $m$ 個のクラス $\mathcal{Y}=\{c_{i}\}_{i=1}^{m}$ に分類されているとします。 $\mathcal{X}$ をクラスに分類するとは $\mathcal{X}$ を互いに共通部分を持たない部分集合に分割することなので、 $c_{i}$ は次の条件を満たす $\mathcal{X}$ の部分集合とします：

$\displaystyle \mathcal{X}=\bigcup_{i=1}^{m}c_{i},\quad c_{i}\cap c_{j}=\emptyset \ (i\neq j).$

対象 $i$ に関する説明変数の値を $a_{i\cdot}:=(a_{i1},a_{i2},\ldots,a_{ik})\in \mathcal{X}$ 、目的変数の値を $b_{i}\in\mathcal{Y}$ 、 $s:=\{(a_{i\cdot},b_{i})\} _{i=1}^{n}$ 、 $s_{\mathcal{X}}:=\{a_{i\cdot}\}_{i=1}^{n}$ とします。

所与の分類 $\mathcal{Y}$ と説明変数 $\mathcal{X}$ の関係性を仮説として表現するために次で定義する決定木を利用します。

定義１（決定木）　 $r$ を $\mathcal{X}$ の空でない部分集合とし、 $r$ の(空集合を含まない)適当な部分集合族 $T$ と写像 $L$ , $R:T\to T\cup\{\emptyset\}$ について次の関係が成り立つとする。

$t\in T$ に対し $L(t)\neq\emptyset$ ならば $L(t)$ は $t$ の真部分集合である。
$R$ は次を満たす： \begin{equation*} R(t)=\begin{cases} t\setminus L(t), & L(t)\in T,\\ \emptyset, & L(t)=\emptyset. \end{cases} \end{equation*}
$T\supsetneq\{r\}$ であり、任意の $t\in T\setminus\{r\}$ に対して $L(t')=t$ または $R(t')=t$ を満たす $t'\in T$ が存在する。

このとき組 $(T,\{L,R\})$ を決定木*1と呼ぶ。また決定木を扱っていることが明らかな場合、 $T$ のことも決定木と呼ぶことにする。

決定木の性質を述べるために幾つかの言葉を準備します。

定義２　 $T$ を決定木とする。

各 $t\in T$ をノードと呼ぶ。
定義 1 における $r\in T$ を根ノードと呼ぶ。また $L(t)=R(t)=\emptyset$ を満たす $t\in T$ を終端ノードと呼び、 $T$ の終端ノード全体を $\widetilde{T}$ と書く。
$L(t)$ と $R(t)$ が空集合でないとき、 $L(t)$ と $R(t)$ を $t$ の子ノード、また $t$ を $L(t)$ (または $R(t)$ ) の親ノードと呼ぶ。 $t\in T$ に対して $t=L(t')$ または $t=R(t')$ を満たす $t'\in T$ を $t$ の祖先、 $t$ を $t'$ の子孫と呼ぶ。

上記の言葉を用いると、決定木とは根ノード以外の全てのノードに必ず親ノードが存在するような部分集合族と言い表すことが出来ます。

以下、決定木 $T$ の根ノードは $\mathcal{X}$ とします。また $\#\widetilde{T}$ は有限とします。

終端ノード $\widetilde{T}$ は $\mathcal{X}$ を互いに共通部分を持たない集合に分割している(つまりクラス分類を与えている)ことに注意して、求める仮説は仮説集合

$\displaystyle \mathcal{H}:=\{c^{T}\circ f^{T}:\mathcal{X}\to\mathcal{Y}\big|T\in\mathcal{T} \}$

の中から探すことにします。ただし $\mathcal{T}$ は決定木全体、 $f^{T}$ は $x\in\mathcal{X}$ から $x\in t$ を満たす $t\in\widetilde{T}$ への写像、 $c^{T}$ は $t\in\widetilde{T}$ を所与の何れかのクラス $c_{i}\in\mathcal{Y}$ ( $i=1$ , 2, $\ldots$ , $m$ )に対応させる写像です。

記法　表現を簡潔にするために、集合 $A$ のうち集合 $B$ との共通部分が占める割合をデータ $s_{\mathcal{X}}$ を使って測ったものを $p(B|A)$ で表すことにします：

$\displaystyle p(B|A)=\frac{\#(s_{\mathcal{X}}\cap A\cap B)}{\#(s_{\mathcal{X}}\cap A)}.$

特に $A=\mathcal{X}$ のとき $p(B)$ と書きます。

まず $c^{T}$ ですが、 $t \in T$ に占める $c_{i} \in \mathcal{Y}$ の割合 $p(c_{i}|t)$ が最大となる $c_{i}$ を対応させるものが自然と思われます。つまり

$\displaystyle c^{T}(t):=c_{i(t)},\quad i(t):=\underset{i;t\cap c_{i}\neq\emptyset}{\mathrm{arg\, max}} \ p(c_{i}|t).$

次に $f^{T}$ ですが、取りあえずは予測値と観測値との間の残差

$\displaystyle \widehat{R}(T,\ell,s):=\frac{1}{n}\sum_{i=1}^{n}\ell(s_{\mathcal{X}}\cap f^{T}(a_{i\cdot}),b_{i})$

(ただし $\ell(t,t')$ は $t$ , $t^{\prime}\neq \emptyset$ かつ $t\cap t^{\prime}\neq \emptyset$ である $\mathcal{X}$ の部分集合 $t$ と $t'$ の差を表現する損失関数)を最小化する仮説とします。

$j\in\{j'|f^{T}(a_{j'\cdot})=t,\,b_{j'}=c_{i}\}$ に対して $\ell(s_{\mathcal{X}}\cap f^{T}(a_{j\cdot}),b_{j})=\ell(s_{\mathcal{X}}\cap t,c_{i})$ なので

$\displaystyle \widehat{R}(T,\ell,s):=\frac{1}{n}\sum_{t\in\widetilde{T}}\sum_{i\in I(t)\vphantom{\widetilde{T}}}\#(s_{\mathcal{X}}\cap t\cap c_{i})\ell(s_{\mathcal{X}}\cap t,c_{i}).$

ただし $I(t):=\{i\,|\,s_{\mathcal{X}}\cap t\cap c_{i}\neq\emptyset\}$ .

ここで損失関数 $\ell$ として $\phi(0)=\phi(1)=0$ を満たす狭義上に凸の非負関数 $\phi$ を用いて

$\displaystyle \ell(s_{\mathcal{X}}\cap t,c_{i})=p(c_{i}|t)^{-1}\phi(p(c_{i}|t)),\quad i\in I(t)$

と表されるものを考えます。このとき残差 $\widehat{R}(T,\ell,s)$ を $\widehat{R}(T,\phi,s)$ と書くことにします。 $\widehat{R}(T,\phi,s)$ は次のように書き直せます。

$\displaystyle \widehat{R}(T,\phi,s)=\sum_{t\in\widetilde{T}}p(t)\sum_{i\in I(t)\vphantom{\widetilde{T}}}\phi(p(c_{i}|t)).$

例　以下は $\phi$ の例です。

(ジニ係数) $\phi(p):=p(1-p)$ ( $0\le p\le1$ )
(エントロピー) \begin{equation*} \phi(p)=\begin{cases} -p\log p, & 0<p\le1,\\ 0, & p=0. \end{cases} \end{equation*}

決定木が深くなることで $\widehat{R}(T,\phi,s)$ がどのように変化するかを調べます。

命題３　 $T$ の終端ノード $t$ を2つの集合 $t_{1}$ , $t_{2}$ ( $s_{\mathcal{X}} \cap t_{1}$ , $s_{\mathcal{X}} \cap t_{2} \neq \emptyset$ )に分割して $L(t):=t_{1}$ , $R(t):=t_{2}$ とし、 $T$ よりも1段階深くした決定木 $T\cup\{t_{1},t_{2}\}$ を考える。このとき \begin{equation*} \begin{split}\varDelta\widehat{R}(T,\phi,s;t_{1},t_{2}) & :=\widehat{R}(T,\phi,s)-\widehat{R}(T\cup\{t_{1},t_{2}\},\phi,s)\\ & =p(t)\sum_{i\in I(t)}\phi(p(c_{i}|t))-\sum_{j=1,2}p(t_{j})\sum_{i\in I(t_{j})}\phi(p(c_{i}|t_{j})) \end{split} \end{equation*} とすると $\varDelta\widehat{R}(T,\phi,s;t_{1},t_{2})\gt 0$ が成り立つ。つまり決定木 $T\cup\{t_{1},t_{2}\}$ による予測値は、決定木 $T$ による予測値と比べて観測値との残差を小さくする。

証明　 $I_{1}:=I(t_{1})\setminus I(t_{2})$ , $I_{2}:=I(t_{2})\setminus I(t_{1})$ , $I_{12}:=I(t_{1})\cap I(t_{2})$ とすると $I_{1}\cap I_{2}=\emptyset$ , $I_{i}\cap I_{12}=\emptyset$ , $I(t_{i})=I_{i}\cup I_{12}$ ( $i=1$ , $2$ ), $I(t)=I_{1}\cup I_{2}\cup I_{12}$ が成り立つ。 \begin{equation*} \begin{split}\varDelta\widehat{R}(T,\phi,s;t_{1},t_{2})=\sum_{i\in I_{12}} & \left\{ p(t)\phi(p(c_{i}|t))-\sum_{j=1,2}p(t_{j})\phi(p(c_{i}|t_{j}))\right\} \\ & +\sum_{j=1,2}\sum_{i\in I_{j}}\left\{ p(t)\phi(p(c_{i}|t))-p(t_{j})\phi(p(c_{i}|t_{j}))\right\} \end{split} \end{equation*} であるが、 $\phi$ の凸性 \begin{equation*} \phi(p(c_{i}|t))>\sum_{j=1,2}\frac{p(t_{j})}{p(t)}\phi(p(c_{i}|t_{j})). \end{equation*} より $\varDelta\widehat{R}(T,\phi,s;t_{1},t_{2})\gt 0$ が成り立つ。(証明終)

命題 3 および命題 4 より、集合の分割を繰り返すことで残差 $\widehat{R}(T,\phi,s)$ は徐々に小さくなっていき、各 $x\in s_{\mathcal{X}}$ が別々の終端ノードに属する状態になったとき残差 $\widehat{R}(T,\phi,s)$ はゼロとなります。しかしデータの間に共通性を見出してまとめていく行為を分類と呼んでいることに注意すれば、このような状態は我々が求めるべき答えでないことは明らかです。つまり $\widehat{R}(T,\phi,s)$ を最小化する方法では適切な仮説を決定できないことが分かります。

そこで今度は分割数が大きすぎることに対するペナルティ項を加えた

$\displaystyle \widehat{R}_{\alpha}(T,\phi,s):=\widehat{R}(T,\phi,s)+\alpha\#\widetilde{T}$

を最小化する仮説を求めることにします。 $\alpha \gt 0$ はペナルティの大きさを調整するパラメータ*2です。

注意　ペナルティ項は決定木における大域的な状態(決定木の大きさ)を調整するためのパラメータであり、局所的な状態(個々のノードにおける適切な分割割合)には関与しません。実際、 $t\in\widetilde{T}$ を集合 $t_{1}$ , $t_{2}$ に分割して

$\displaystyle \varDelta\widehat{R}_{\alpha}(T,\phi,s;t_{1},t_{2}):=\widehat{R}_{\alpha}(T,\phi,s)-\widehat{R}_{\alpha}(T\cup\{t_{1},t_{2}\},\phi,s)$

とすると

$\displaystyle \varDelta\widehat{R}_{\alpha}(T,\phi,s;t_{1},t_{2})=\varDelta\widehat{R}(T,\phi,s;t_{1},t_{2})-\alpha$

となり分割の仕方 $t_{1}$ , $t_{2}$ には影響を与えないことが分かります。

決定木（２）に続く

*1:正確には2分木による決定木と呼ぶべきですが、ここでは2分木しか扱わない為、単に決定木と呼ぶことにします。

*2: $\alpha$ は残差を最小にするパラメータ値を探索するアルゴリズムの処理対象外のパラメータです。このようなパラメータはハイパーパラメータと呼ばれています。