[連載] フリーソフトによるデータ解析・マイニング 第18

Rと樹木モデル(1)

 


1.樹木モデルとは

樹木モデル(tree-based model)は、非線形回帰分析、判別分析のひとつの方法で、回帰の問題では回帰木(regression tree)、分類の問題では分類木(classification tree)あるいは決定木(decision tree)と呼ばれている。

樹木モデルは、説明変数の値を分岐させ、それらを組み合わせて、判別・予測のモデルを構築する。分析の結果はIF-THENのような簡潔なルールを生成させ、またそのルールを樹木構造で図示することができるため、理解しやすいことから、その応用が急速に広がっている。

 図1に示す散布図の回帰モデルの構築を考えてみよう。このような単回帰の場合は、従来の回帰では直線、あるいは曲線でモデルを構築するが、回帰木の場合は、図2に示すような軸(変数)と平行する直線を組み合わせた階段型折れ線でモデルを構築する。図3が図2の樹木構造の図示である。

1 回帰直線と回帰曲線

2 樹木モデルによる回帰折れ線

 

3 回帰木

 

3の木は次に示すIF-THENルールの記述と等価である。

 

1) root  

  2) IF {Price>=16.1} THEN {4.596} 

3) IF {Price< 16.1} THEN{ 

    4) IF{Price< 14.05}    THEN {3.486}

    5) IF{Price>=14.05}THEN {4.033}

    }

  

 樹木モデルに関する研究は、1960年代初期までさかのぼる。今日、広く用いられているのはCHAIDCARTC4.5/C5.0/See5をベースとしたアルゴリズムである。

CHAID(Chi-squared automatic interaction detection)J. A. Hartiganによって1975年に発表された、上記の3種類の中で最も古いアルゴリズムである。CHAID1963J.A.Morganらによって提案されたAID(automatic interaction detection)を発展させたもので、変数の分岐基準としてカイ2乗統計量やF検定統計量など統計学で多く用いられている統計量が用いられている。

CHAIDはデータ解析の専用ソフトSASSPSSの統計パッケージに採用されていることにより広く用いられている。

CART(classification and regression trees) は、カリフォルニア大学のL.BreimanR.A. OlshenC.J.Stone、スタンフォード大学のJ.H.Friedman1970年代初めごろから共同研究を始め、1980年代初めごろに公開したアルゴリズムである。

CARTは、説明変数を2進分岐させ、2進木を生成する。初期のCARTでは、分岐の評価基準として経済学者ジニ(Gini)によって提案されているジニ係数をジニ多様性指標(Gini’s diversity index)として用いたが、最近は情報利得(information gain)なども用いられている。CARTは、樹木をあらかじめ何の制限もせずに生長させ、データと対話しながら樹木の剪定を行う方法を取っている。この点は、樹木が生長し過ぎないように事前に制御するCHAIDと大きく異なる。

C4.5/C5.0/See5は、オーストラリアのJ. Ross Quinlanが機械学習のアプローチで1986年に発表したID3(iterative dichotomiser 3)を改良・発展させたものである。

現在、J. Ross QuinlanRULEQUEST RESEARCH というソフトウェア会社を運営しながらシドニーにあるNew South Wales大学でコンサルティング教授としてデータマイニングの分野で活躍している。

C4.5/C5.0/See5は、2進木に限らないのがCARTとの大きな違いである。C4.5/C5.0/See5の前身であるID3では、分岐の評価基準として情報利得(information gain)を用いたが、C4.5/C5.0/See5では、利得比(gain ratio)を用いている。

これらの樹形モデルのアルゴリズムはそれぞれ特徴を持っており、どのアルゴリズムが優れているかは評価し難い。

 これらの樹形モデルの大きい違いは樹木の生成・生長、樹木の剪定のアルゴリズムである。

樹木の生成・生長とは、データセットから樹木の幹・枝となる説明変数を選定し、分岐基準によって分岐させ、樹木を生長させるのに関する樹木モデルの核の部分である。

樹木の剪定とは、生長し過ぎた樹木を何らかの基準に基づいて枝刈りし、当てはめの良い簡潔な樹木モデルを構築する作業である。

このようなアルゴリズムの詳細については紙面上の制約により割愛せざるを得ない。

Rには、樹木モデル関数treerpartがある。最近、rpartを多変量回帰木(Multivariate regression trees)拡張させたmvpartが公開されている。これらは、CARTの親族であると考えられる。

 

2.樹木モデル関数tree

関数treeでは、節の分岐の評価基準、つまりそれぞれの節で、どのような分割が最適であるかに関する評価は尤離度(deviance)とジニ(Gini)係数を用いている。デフォルトは、尤離度になっている。

関数treeでは、被説明変数(応答変数)が量的であるか、質的であるかによって、自動的に予測問題であるか、それとも判別問題であるかを識別して分析を行うので、通常では引数のパラメータの指定を行わなくてもよい。

関数treeの書き式を次に示す。書き式の中の引数formは、線形回帰分析関数lmの場合と同じである。その詳細はhelp(tree)で確認できる。

tree(form,data,・・・)

関数オブジェクトtreeクラスの主なメソッド関数を表1に示す。関数treeを用いるためにはパッケージtreeをロード(library(tree)) しなければならない。

 

1 関数treeクラスの主なメソッド

メソッド名

機    能

print

結果を返す

summary

要約を返す

plot.tree

樹木の図を返す

prune.tree

剪定を行う

predict.tree

予測・判別を行う

snip.tree

樹木の剪定を行う

partition.tree

直線による分割図を返す

cv.tree

交差確認を行う

 

 実際のデータを用いて、これらの使用例を示す。

 

(1) 関数treeの回帰木

ここではRに用意されているデータcarsを用いることにする。データcars50個体(観測体)2変数のデータフレームである。変数は、車の速度(speed)とブレーキを掛けた後停車までの距離(dist)の計測値である。ここでは、測度(speed)を説明変数、ブレーキを掛けた後停車までの距離(dist)を被説明変数とする。

 

>cars.tr<-tree(dist~speed,data=cars)

>print(cars.tr)

node), split, n, deviance, yval

      * denotes terminal node

1) root 50 32540.0 42.98 

  2) speed < 17.5 31  8307.0 29.32 

    4) speed < 12.5 15  1176.0 18.20 

      8) speed < 9.5 6   277.3 10.67 *

      9) speed > 9.5 9   331.6 23.22 *

    5) speed > 12.5 16  3535.0 39.75 *

  3) speed > 17.5 19  9016.0 65.26 

    6) speed < 23.5 14  2847.0 55.71 *

    7) speed > 23.5 5  1318.0 92.00 *

 

これが回帰木のIF-THENルールである。

返された結果の毎行は次のような項目を順に並べている。

 

node), split, n, deviance, yval

 

node)は分岐のノード()の番号、splitは分岐の条件、nはそのノードに含まれている個体の数、devianceはその節の分岐基準尤離度である。yvalはその節の被説明変数値で、判別分析の場合はグループの名前となる。星印が付いている行は端末の節であり、葉とも呼ぶ。

回帰木のルールは次のように樹木構造で図示することができる。関数plot.tree.treeは省略できる。

 

> plot(cars.tr,type="u")

> text(cars.tr)

 

図4 データcarsの回帰木1

 

また、説明変数が1つの場合は、被説明変数と説明変数の2次元の散布図に、階段型回帰折れ線を追加することができる。

 

> plot(cars$speed,cars$dist)

> partition.tree(cars.tr,add=T,col=2)

5 データcarsの回帰木の折れ線

 

生成した木が冗長な場合もある。その場合は何らかの基準に基づいて剪定を行うことが必要である。剪定は、関数prune.treeを次ぎのように用いることができる。例えば、葉を4つにしたいときには、引数best=4にする。

 

> (cars.tr1<-prune.tree(cars.tr,best=4))

node), split, n, deviance, yval

      * denotes terminal node

 

1) root 50 32540 42.98 

  2) speed < 17.5 31  8307 29.32 

    4) speed < 12.5 15  1176 18.20 *

    5) speed > 12.5 16  3535 39.75 *

  3) speed > 17.5 19  9016 65.26 

    6) speed < 23.5 14  2847 55.71 *

    7) speed > 23.5 5  1318 92.00 *

> plot(cars.tr1); text(cars.tr1,all=T)

 

6 剪定を行ったcarsの回帰木

 

> plot(cars$speed,cars$dist)

> partition.tree(cars.tr1,add=T,col=2)

 

7 剪定を行ったcarsの回帰木の折れ線

 

(2) 関数treeの分類木

 分類木ではデータirisを用いることにする。

 

> (iris.tr<-tree(Species~.,data=iris))

 

> plot(iris.tr,type="u"); text(iris.tr)

 

8 関数treeによるirisの分類木

 

  上記の結果から分類木のノード127以下は無意味であることがわかる。ノードを指定した木の剪定は関数snip.treeを用いる。引数nodesに、次ぎのようにノードの番号を指定すると、そのノードが刈り取られた結果が返される。図9にその分類木を示す。

 

>(iris.tr1<-snip.tree(iris.tr,nodes=c(12,7)))

>plot(iris.tr1,type=u”);text(iris.tr1)

 

9 剪定されたirisの分類木

 

図9から分かるように、この分類木には、2つの変数Petal.LengthPetal.Widthのみが用いられている。このような2変数のみの場合は、partition.treeを用いて、10のように、2変数の散布図に分類の分割直線を加えることができる。

 

>iris.label<-c("S", "C", "V")[iris[, 5]]

>plot(iris[,3],iris[,4],type="n")

>text(iris[,3],iris[,4],labels=iris.label)

>partition.tree(iris.tr1,add=T,col=2,cex=1.5)

 

10 分類の分割

 

関数summaryは決定木の基本的な情報を返す。

 

> summary(iris.tr1)

 

 

(3) 木の剪定の目安

生長し過ぎた樹木の剪定を行う場合、どのように剪定するかが問題である。

学習データでは、木を大きく生長させることで、予測・分類の精度を上げることが可能である。ただし、木の生長が大きくなると同時に、ルールが煩雑になり、解釈が難しくなる場合も少なくない。また、生長し過ぎた結果をテストデータに当てはめたとき、適応が良くないことがよく知られている。

そこで、大きい木をどこまで剪定(枝を切る)するかを決める基準が必要である。

関数treeでは、幾つかの方法があるが、ここでは交差確認法による尤離度(deviance)の値を用いる方法を説明する。

関数treeには、n交差確認を行う関数cv.tree がある。n重交差確認におけるデフォルトのn10になっている。交差確認法による剪定のための尤離度の考察は、次ぎのように関数cv.treeを用いる。引数FUN=prune.treeは最適なサイズの木をprune.treeによって生成する。

 

>iris.cv<-cv.tree(iris.tr,FUN=prune.tree)

>plot(iris.cv)

 

11 サイズ対尤離度のプロット1

 

読者が同じのコマンドを実行しても図11と同じのグラフが得られるとは限らない。その理由は後ほど述べる。

11の縦軸は尤離度、横軸は葉の数(サイズ)である。横軸のサイズ4のとき尤離度が最も小さい。これはサイズ4の木がモデルの候補として考えられることを示唆する。しかし、同じの操作を繰り返して実行すると、場合によっては尤離度が最小となるサイズが3になったり、5になったりすることがある。これは交差確認を行う際、データの分割の結果が毎回異なるからである。

折衷の案として、上記のコマンドに続いて、次ぎのように同じの作業を複数回行い、その平均値を用いることが考えられる。ここでは上記の交差確認を10回繰り返し、その平均値を用いることにする。10回が不十分と考える場合は、回数をさらに増やせばよい。

 

> for(i in 2:10) iris.cv$dev<-iris.cv$dev+

cv.tree(iris.tr,FUN=prune.tree)$dev

> iris.cv$dev=iris.cv$dev/10;plot(iris.cv)

12 剪定サイズ対尤離度のプロット2

 

交差確認を10回繰り返した結果、尤離度を最小とするサイズは4である。サイズ4にした木の剪定を次に示す。この結果は、図9と同じであることに注意して欲しい。

 

>prune.tree(iris.tr,best=4)

 

このアプローチでは、データによっては計算がうまくいかない場合がある。

 

(4) 予測と判別

樹形モデルの構築の目的は、学習データ以外のデータについての予測と判別を行うことである。

学習データを用いて構築したモデルを用いて、新たなデータについての予測と判別を行う関数はpredict.treeである。ただし、ここの.treeは省略することができる。その書き式は、基本的には回帰分析および判別分析と同じであるが、引数としてtype = c("vector", "tree", "class", "where")が用意され、問題に合わせて返す結果を指定することができる。

type=”vector”を指定すると、回帰問題では予測値、分類問題では属性に関する確率が返される。type=”tree”を指定すると、新たなデータによるノード尤離度devianceとそのノードに属する個体数nが返される。type=”class”を指定すると、新たなデータの属性の判別結果が返される。type=”where”を指定すると、各個体(ケース)が到達するノードの番号を返す。

 次に、irisデータの奇数行を学習データ、偶数行をテストデータとした判別の例を示す。

 

#データセットを作成する。

>even.n<-2*(1:75)-1; train.data<-iris[even.n,]

>test.data<-iris[-even.n,-5]

>Iris.lab<-factor(c(rep("S",25),rep("C",25),rep("V",25)))

>train.data[,5]<-Iris.lab

 

#学習データによる分類木を構築する。

>Iris.tr<-tree(Species~.,train.data)

 

#分類木の剪定を行う。

>Iris.tr1<-prune.tree(Iris.tr,best=3)

 

#分類木による新たなデータを分類する。

>Iris.res<-predict(Iris.tr1,test.data,type="class")

> table(Iris.lab,Iris.res)

        Iris.res

Iris.lab C  S  V

       C 24  0  1

       S  0 25  0

       V  3  0 22

 

関数treeには、以上で説明・使用したメソッド以外に、tree.controltree.screenstile.treetext.treeprune.misclassna.tree.replacedeviance.treeなどがある。