情報分析（第 5 回） 2012年 5 月 23 日

情報分析（ 第 5 回） 2012 年 5 月 23 日 辻慶太
■はじめに
今日は SVM の続きと決定木（ decision tree ）についてお話します。決定木は SVM や判別分析と同様，
事前にいくつかのグループ（ カテゴ リー）と，所属グループ不明の個体が与えられた時，各個体がどのグ
ループに属するかを自動判定してくれる手法です。前回の SVM や判別分析と異なる点は，決定木はいくつ
かの判定ルールと共に結果を表示してくれるので，なぜその個体がそのグループに分類されたのか結果を
追いやすい点です。例えば「その個体は男性ですか？女性ですか？」
「年齢は 42 歳以上ですか？」といった
ルールが有効だと自動的に判断し（ 例えば「年齢は 41 歳以上ですか？」より「年齢は 42 歳以上ですか？」
の方がルールとして優れているとデータを見て自動判断してくれます），表示してくれ，かつ判定したい
個体をグループ分けしてくれるのです。結果を人間が見て理解しやすい点が SVM との大きな違いです。
■今日の授業で考えて（ 覚えて）ほしいこと
(1) リーフノード，ルート ノード，エントロピー，相互情報量とはどのようなものか？
(2) SVM などに比べた決定木の長所は何か？
■決定木を用いた研究例
・ 桑城克教ら (2011)「ネットオークションの商品情報を用いた決定木学習による出品者の行動パター
ンの分類」標準化研究.
・ 野崎要ら (2011)「プログラミング教育における学習者の履歴データに基づく状況把握のための決定
木構築」電子情報通信学会総合大会講演論文集.
・ 中園美香ら
論文集.
・ 國土将平
(2010)「 pLSI 手法+多目的決定木によるレコメンド 手法紹介」日本計算機統計学会大会
(2009)「決定木分析と発育発達研究」子ど もと発育発達.
・ 安俊相ら (2008)「訪問者に対する不安感を目的変数とした決定木：戸建住宅団地における独居高齢
者宅への訪問者に対する不安感の研究」学術講演梗概集. F-1, 都市計画, 建築経済・住宅問題
・ 荻田泰宏ら (2008)「決定木学習を用いた人名情報抽出のための規則生成」全国大会講演論文集 第 70
回平成 20 年 (2).
(2007)「教育費支出の動機構造の解明にむけて : 教育意識の決定木分析」教育社会学研究
・ 古宮嘉那子ら (2007)「決定木を用いた中国語の疑問文の訳語選択ルールの生成」情報処理学会研究
報告. NL, 自然言語処理研究会報告.
・ 杉井学ら (2007)「機械学習によるスパムメールの特徴の決定木表現 (セッション 4-B : セキュリティ
応用技術) 」情報処理学会研究報告. CSEC, コンピュータセキュリティ.
・ 古畑裕介ら (2006)「決定木アルゴ リズムに基づく自然言語文書の話題分析 (通信・オフィスシステ
ム) 」電子情報通信学会技術研究報告. OIS, オフィスインフォメーションシステム.
・ 小磯拓也ら (2006)「 Web 資源からの決定木学習による Web ページに対するキーワード 付与」情報
処理学会研究報告. 自然言語処理研究会報告.
・ 澤島秀成ら (2005)「ユーザ属性と製品評価の関係分析における決定木の有用性」デザイン学研究.
・ 樋口清秀ら (2005)「 郵便局の評価に関するデータマイニング試論{決定木手法による分析の評価と
可能性」貯蓄経済理論研究会年報.
・ 古田和久
1
顧客番号
001
002
003
004
性別
年齢
20
20
40
30
女性
男性
男性
女性
表
1:
職業
商品 A
会社員
○
その他
×
教員
○
会社員
○
合計購買金額
30,000
24,000
78,000
12,000
顧客プロファイル
■決定木の例
例えば表 1 のような顧客プロファイルと，その顧客の戦略商品 A の購買の有無（○が購入顧客，×が非
購入顧客）を示すデータベースがあったとする。このデータベースから作成された「 商品 A の購買の有
無」に関する決定木の例が図 1 である。図の決定木では，木の各中間ノード にデータを分類するための分
割テスト（ splitting test ）が示されている。また，各中間ノード は分割テストを適用した結果のとり得る
（ 二つの ）値に対応する（ 二つの ）下向きの枝をもつ。一方，各終端ノード は，ここで注目している「商
品 A の購買の有無」を示すラベルをもつ。
この例のデータベース中の各顧客は，この決定木を使って，いずれかの終端ノード に分類される。決定
木の（ 中間ノード の一つである）頂点ノード はデータベースの全データ集合に対応する。データベース中
のある顧客は，この頂点ノード の 1 レコード である。このレコード は，頂点ノード の分割テストである
「年齢が 30 以下」であるかど うかで，二つのうちのいずれかの下位ノード に分類される。たとえば ，年齢
が 15 である顧客は，テストの適用結果である Yes に対応する左の下位ノード に分類される。下位ノード
においても，同様に，ノード の分割テストを適用した結果に従って，いずれかの下位ノード へ分類される。
こうした分類を繰り返すことで，各顧客は最終的にいずれかの終端ノード に分類される。
たとえばこの決定木の一番左の終端ノード に至る経路は，
「 年齢が 30 以下でかつ性別が女性という条件
を満たす顧客は商品 A を購買した」という法則を表している。従って今後たとえば「年齢が 30 以下」で，
かつ「性別が女性」の顧客が店に入ってきたら，この顧客は商品 A を買う可能性が高いと予測して店員は
接客するといった対応が可能になる。
各終端ノード は，そのノード に分類される顧客の「商品 A の購買の有無」から，ラベルづけされる。一
般的には，
「 ○」の頻度が「×」の頻度より多い終端ノード のラベルは「○」，その道の場合は「×」とする
ことが多い。その場合，
「 ○」とラベルづけされた終端ノード は「商品 A を購買した」顧客グループ，
「 ×」
とラベルづけされた終端ノード は「商品 A を購買しなかった」顧客グループに対応している。
決定木は 2 種類に分けることが出来る。
「商品 A の購買の有無」のように，注目する属性値がカテゴ リ型
である場合は「分類木」と呼ばれることがある。一方，注目する属性が「合計購買金額」のような数値型
である場合は「回帰木」と呼ばれることがある。図 2 に「合計購買金額」に関する回帰木の例を示す。回
帰木の各終端ノード のラベルは，そのノード に分類される顧客グループの，注目している数値属性値（こ
の場合「合計購買金額」）の平均値とする場合が多い。
「合計購買金額」が未知の顧客が，回帰木でいずれ
かの顧客グループに分類された場合，その顧客の「合計購買金額」の予測値を，その顧客グループの平均
値とする場合，終端ノード のラベルを平均値としておくと便利なためである。
・
「商品 A の購買の有無」のように，注目する属性がカテゴ リ型の木 → 分類木
・
「合計購買金額」のように，注目する属性が数値型の木 → 回帰木
※ 2 つ合わせて決定木。
2
図
1: 「商品 A の購買の有無」に関する決定木（ 分類木）の例
図
2: 「合計購買金額」に関する決定木（ 回帰木）の例
3
■決定木の特徴
・ SVM などと異なり，人間が見て理解しやすいルールになっている。
・ データが欠損値を含んでいる場合でも扱いやすい
・ 非線形のデータに対して良い結果を与えることが多い。一方，線形なデータの場合はあまりよい結
果を与えないことが知られている。即ち，それなら判別分析や回帰分析の方がまだ良い。
・ ニューラルネットなどに比べ，高速に計算できる。
■用語
・ 木：1 のような分岐構造（→ 木というと根が下のはずだが，なぜか逆さまにして描く）
・ 頂点（ルート ）ノード ：木の一番上の部分
・ 終端（ リーフ ）ノード ： 〃 下
・ 決定木は，頂点ノード から終端ノード に至るまでの IF-THEN ルールの組み合わせと考えることが
できる。このとき終端ノード のラベルは，この IF-THEN ルールの結論部に相当する。
・ 目的属性（ target attribute ）
：
「商品 A の購買の有無」，
「 合計購買金額」のように，IF-THEN ルー
ルの結論部に現れる属性
・ 条件属性（ conditional
attribute ）：IF-THEN ルールの条件部に現れる属性
■決定木の求め方
以下では相互情報量を用いた決定木構築方法について説明する。例えば「商品 A 」の値が○か×かを導
く為の情報として表 2，表 3 のようなデータがあったとする。
「性別」が「女性」
：Y 1
「商品 A 」の値：
X
Yes ×
0.54
0.06
0.60
表
2: ルール 1 の情報
○
No 0.10
0.30
0.40
0.64
0.36
「年齢」が「 20 以下」
：Y 2
「商品 A 」の値：
X
Yes ×
0.30
0.30
0.60
表
3: ルール 2 の情報
○
No 0.34
0.06
0.40
0.64
0.36
表 2 から例えば ，性別が女性で商品 A を買った（○）人は全体の 54 ％であること，性別が女性で商品
A を買わなかった（× ）人は全体の 6 ％であること，であることが分かる。同様に表 3 から例えば年齢が
4
20 以下で商品 A を買った（ ○）人は全体の 30 ％であることなどが分かる。これらの表からは例えば以下
のルールが導ける：
ルール 1: Y1
（「性別」が「女性」）⇒（「商品 A 」が「○」）
ルール 2: Y2
（「年齢」が「 20 以下」）⇒（「商品 A 」が「×」）
この時，ルール 1 とルール 2 だったらど ちらの方が優れているか？ ルールの優秀さは「あいまいさの少
なさ」で評価することができる（あるいは「間違って分類してしまう確率の低さ」と言った方が分かりや
すいかもしれない。が，以下では伝統に従って「あいまいさの少なさ」という表現を用いることにする）
。
ではこの「あいまいさ」はどのように表せるか？
普通の硬貨 A を投げると表が出る確率は 50 ％，裏が出る確率は 50 ％である。ここで硬貨を真っ二つに
切って貼り合わせ，両方とも表になったマンガに出て来るようないかさま硬貨 B を考える。この硬貨は表
が出る確率は 100 ％，裏が出る確率は 0 ％である。この時，硬貨 A を投げたとき表裏ど ちらが出るかに関
する「あいまいさ」
（ 予想して間違えてしまう確率）は，硬貨 B を投げたとき表裏ど ちらが出るかに関す
る「あいまいさ」
（ 予想して間違えてしまう確率）より高い。従って「あいまいさ」の尺度を作るとした
ら上記のような大小関係になる尺度になるべきである。これにはエントロピーという以下のような尺度が
ある。
あるデータ集合 S の事象 X に関する「あいまいさ」は以下の式で定義されるエントロピー （ entropy ）
で測ることができる。
k
X
H (S ) = H (X ) = ; p log
j =1
j
k pj
ここで pj は X の k 種類ある事象 a1 ,...,ak のうち，事象 aj (1 ≦ j ≦ k) の出現率とする。ただし ,
ai aj = 0(i ≠ j ) であるとする。また H (S ) ≧ 0 である。
先ほどの硬貨の例で言うと，X は「硬貨の出る面」といったものであり，種類 k は 2 で，事象は「表」
と「裏」である。硬貨 B の「硬貨の出る面」に関するエントロピーは：
H (X ) = ;1:00 log2 1:00 ; 0:00 log2 0:00
= 0:00
即ち，硬貨 B のエントロピーは最低であり，あいまいさは全くない（表が出るか裏が出るか予想して外れ
ることはない）ことが分かる。一方硬貨 A の方は：
H (X ) = ;0:50 log2 0:50 ; 0:50 log2 0:50
=
となる。即ち，硬貨 B のエントロピーより高くなることが分かる。このようにエントロピーは先ほど ，あ
いまいさの尺度に要請した性質を満たしている。
5
先ほどの「商品 A の値：X 」に関しては , 「○」, 「×」の二つの事象がある。
「ルール 1:Y 1 」と「商品
A の値：X 」との関連として，先ほどの表 2 のようなデータが得られているとすると，
「 商品 A の値：X 」
がもつエントロピーは：
H (X ) = ;0:64 log2 0:64 ; 0:36 log2 0:36
= 0:943
である。
次に「ルール 1:Y 1（ 性別が女性か ）」に対して \Yes"である人達を考える。その人達の間では「○（ 買
う）」
「×（ 買わない）」の割合はそれぞれ 0:54=0:6 = 0:9，0:06=0:6 = 0:1 であるから：
H (X jY 1 = Y es) = ;0:9 log2 0:9 ; 0:1 log2 0:1
= 0:469
同様に「ルール 1：Y 1（ 性別が女性か ）」に対して \No"である人達を考えると，その人達の間では「○
（ 買う）
」
「×（ 買わない）」の割合はそれぞれ 0:10=0:40 = 0:25，0:30=0:40 = 0:75 であるから：
H (X jY 1 = No) = (
) log2 ( )
= 0:811
;(
) log2 ( )
である。
「女性」
「男性」の割合はそれぞれ 0.6, 0.4 であるから, 「ルール 1：Y 1（ 性別が女性か ）
」を導入
することで「商品 A の値：X 」に関するエントロピーは：
H (X jY 1) = (
H (X jY 1 = Y es) + ( ) H (X jY 1 = No)
= ( ) 0:469 + ( ) 0:811
)
= 0:606
となる。この値は先ほどの H (X ) = 0:943 よりも 0.337 ほど 低くなっている。即ち「性別が女性か」とい
うルールを加えることで全体のエントロピーが減ったと言える。このエントロピー（＝あいまいさ）の減
少 H (X ) H (X Y 1) = 0:337 が「ルール 1：Y 1（ 性別が女性か ）」の「商品 A の値：X 」に関する相互情
報量である。
練習：同様に「ルール 2：Y 2（ 年齢が 20 以下か ）
」の相互情報量も同様に計算してみよう。
H (X ) H (X Y 2) = 0:099 と求まる。先ほどの「ルール 1：Y 1（ 性別が女性か ）」は相互情報量は 0.337
であった。従って先ほどのルール 1 の方が，あいまいさをより大きく減らすという点で，ルール 2 よりも
有効と言える。このように相互情報量は「商品 A 」に関するルール同士を比較するのに有用である。決定
木では相互情報量の大きいルールを予測に採用していく。
;
j
;
j
6
■枝刈り
データには通常ノイズが含まれる。そのようなノイズに対しても細かくデータ分割を進めていくと，決
定木が例外的な値・誤りに適合してしまう。これを過学習，あるいはオーバーフィッティング（ overtting ）
という。過学習が起きると必要以上の細かい分類となり，結果として予測精度が悪くなってしまう。さら
に，過学習した決定木から得られる目的属性に関する法則は複雑で理解しづらいものとなる。
枝刈り（ pruning プルーニング，剪定）はそうした過学習を回避する手法である。枝刈りには，(1) 事
前枝刈りと (2) 事後枝刈りの 2 種類がある。
(1) 木の作成段階で，過学習であるか否かを判断し ，データ分割を終了することを事前枝刈り（ prepruning ）という。事前枝刈りは，各ノード の最適分割テストによるデータ分割前後における，カイ 2 乗
検定，相互情報量の増加度，エラーの減少度，平均 2 乗誤差の減少度などの情報から，そのノード のデー
タ分割が精度向上に寄与するかど うかを予測して，データ分割を続けるか，そのノード で分割を終了する
かを判断する。
(2) 一方，まず十分大きな木を作成し ，その木の過学習部分を後でとり除くことを事後枝刈り（ postpruning ）とよぶ。事後枝刈りにおいて，木のどの部分木が過学習であるかを判定するために，学習デー
タとは別の検証データを用意し ，検証データを使って不要な部分木を削除する手法を総称して「 training
and validation set 法」と呼ぶ。事前枝狩り手法に比べ，より大きな木を構築するためのコストが余計に必
要となるが，事後枝刈りによる木のほうが，予測精度が高くなることが多く，現在はこの手法による決定
木の調整を行うシステムが多い。
■いくつかのアルゴリズム
決定木（ 樹木モデル ）に関する研究は，1960 年代初期までさかのぼる。現在では以下の手法（アルゴ リ
ズム）が広く用いられている：
・CHAID (Chi-squared automatic interaction detection)
CHAID は 1963 年 J. A. Morgan らが提案した AID (automatic interaction detection) を，J. A. Hartigan
が 1975 年に発展させたもので，最も古いアルゴ リズムである。CHAID はデータ解析の専用ソフト SAS
と SPSS で採用されており，今でも広く用いられている。分岐の基準としてカイ 2 乗統計量や F 検定統計
量など ，統計学で広く用いられている統計量を用いている。
・CART (classication and regression trees)
1980 年代初め頃，カリフォルニア大学の L. Breiman，R. A. Olshen，C. J. Stone，スタンフォード 大学
の J. H. Friedman が公開した。CART は，樹木を制限なしに生長させ，対話的に剪定を行う方法を取って
いる。この点で，樹木が生長し過ぎないよう事前に制御する CHAID と大きく異なっている。また 2 進木
しか生成しない点で異なっている。初期の CART は，分岐の基準としてジニ係数（ 経済学者ジニ（ Gini ）
が提案）を用いていたが，最近は情報利得（ information gain ）なども用いている。
・C4.5/C5.0/See5
オーストラリアの J. Ross Quinlan が 1986 年に発表した ID3 (iterative dichotomiser 3) を改良・発展
させたもの。2 進木以外も生成するのが CART との大きな違い。枝狩りは事後にも行う。ID3 は，分岐の
基準として情報利得（ information gain ）を用いていたが ，C4.5/C5.0/See5 は，利得比（ gain ratio ）を
7
用いている。現在，J. Ross Quinlan は 1997 年から RuleQuest Research というソフトウェア会社を運営
している。C4.5 は Quinlan のホームページ http://www.rulequest.com/Personal/ で入手できる。
上記のアルゴ リズムはそれぞれ特徴を持っており，どのアルゴ リズムが優れているかは評価し難い。
※以下は難しいので興味があったら：
■決定木の最適分割テスト 発見アルゴリズム
多くの決定木では，上述の相互情報量のような基準で最適なルールを，各中間ノード における分割テス
トに利用する。J. Ross Quinlan の有名な決定木システム ID3 では，この相互情報量の基準で最適な分割テ
ストが，その後継システムにあたる C4.5 では，相互情報量の変形であるゲイン率（ gain ratio ）を最適に
2
する分割テストが，それぞれ使われている。また, CART システムでは gini インデックス（ = 1
k pik ，
ここで pik はノード i 内のクラス k のデータの割合）を最適にする分割テストが使われている。一般的に，
決定木の分割テストには，後述する凸関数性をもつ目的関数で最適となるものを利用するのがよいとさ
れる。
以下では , （ 凸関数性をもつ）相互情報量に基づく日的関数を最適とする分割テストを発見する代表的
なアルゴ リズムを紹介する。今，dom(A) = a1 a2 ::: ak を k 個の離散値をとる属性 A のド メインとす
る。1 条件属性中のカテゴ リ型の属性 C 上では , V
dom(C ) なる分割テストが存在する。2 V はデー
タベースを二つの部分集合 S1 = t tC ] V と S2 = t tC ] = V に分割する。ただし，あるレコード t
のある属性 C の値を tC ] とする。例えばカテゴ リ型の属性 C は 中学生，高校生，大学生 の 3 つの値
を取るとすると，これに基づく分割テスト V には次の 3 通りが考えられ，それぞれデータベースを 2 つ
の集合に分ける。即ち：
;P
f
fj
2 g
g
fj
2 g
f
g
S1 = ftjtC ] = 中学生 g と S2 = ftjtC ] = 高校生，大学生 g
または
S1 = ftjtC ] = 中学生，高校生 g と S2 = ftjtC ] = 大学生 g
または
S1 = ftjtC ] = 高校生 g と S2 = ftjtC ] = 中学生，大学生 g
の 3 通りである。数値型の属性 N の場合は , dom(N ) なる数直線上のある分割点 s でデータ集合を
t R tN ] s と S2 = t R s < tN ] に分割する。
1) 事前集計
f 2 j
g
f 2 j
g
f 男，女 g という 2 個の要素からなるド メインを持つ。
，バナナ g であったら，V は f みかん g かもしれないし f リンゴ ，バナナ g かもしれない。
1 ド メインとは値の集合のことである。
「性別」という属性は
2
は部分集合を表す記号である。
( )は が
V dom C
V
S1 =
dom(C ) の部分集合であることを表す。dom(C ) = f リンゴ ，みかん
8
S をデータベース中の全レコード の集合とし , xi (S1 ) を部分集合 S1 S 中の A の値が ai （ つまり
tA] = ai ）であるレコード 数とする。A が k 個の離散値をとる場合，部分集合 S1 は xi (S1 ) (i = 1 ::: k)
を要素にもつ k 次元空間の点 x(S1 ) として特徴づけることができる。この点のことを（ S を S1 と S2 に
分割する）分割テストのスタンプポイント（ stamppoint ）とよぶ。ただし , S2 は S1 の補集合とする。3
例えば 表 4 のようなデータがあった時，商品購買に関するカテゴ リーを A とすると，A の値は a1 = 商
品○（ 買った ）
，a2 = 商品×（ 買わなかった ）の 2 つとなる。即ち k = 2 である。この時，S1 を中学
生，S2 を高校生及び大学生とすると，S1 のスタンプポイントは (18,2) となる。S2 のスタンプポイントは
(41-18,49-2)=(23,47) となる。合計の人数（＝合計のデータ数）が分かっているので，S1 のスタンプポイ
ントが決まればその補集合である S2 のスタンプポイントは（データ数から S1 を引くことで求められる）
。
商品○（ 買った ）
商品×（ 買わなかった ）
合計
18
16
7
41
2
14
33
49
20
30
40
90
中学生
高校生
大学生
合計
表
4:
学生に関するスタンプポイント例
スタンプポイントの座標値が決まればそれに対応する目的関数値が決まる。相互情報量だったら先ほど
のようにして計算できる。以下では，再び以下の相互情報量に基づく目的関数 Ent を例に解説を進める。
Ent(x(S1 )) = H (S ) ; (jS1 j H (S1 ) + jS2 j H (S2 ))=jS j
j j
ただし ， S をデータ集合 S のデータ数とする。
各条件属性に対し ，あらゆる V あるいは s と，それに対応する Ent(x(S1 ))(= Ent(x(S2 ))) は，最適
な分割テストを発見する過程で頻繁に計算する必要がある。そこで Ent(x(S1 )) を効率的に計算するため，
カテゴ リ型の条件属性 C については , dom(C ) 中の単一の要素からなる各 V （これを原子とよぶ ）に対し
て事前にスタンプポイントを計算しておく。例えば先ほどの例だと「中学生か否か」
「高校生か否か」
「大
学生か否か」の 3 つが原子となる。数値型の条件属性 N に対してはレコード 数が巨大である場合は以下
のようなバケット分割を行い，各バケットに対するスタンプポイントを計算する。
2) 数値属性の場合（バケット 分割）
レコード t の数値属性 A の値を tA] と表記することにする。属性 A の定義域を，次のような交わりの
ないバケット（ bucket ）
（ 区画（ partition ）ともいう）の列：
B1 B2 ::: BM
Bi = xi yi ] xi yi < xi+1
に分割し，すべてのレコード の属性 A の値が必ずどれかのバケットに入るようにする。このように分割
すると，任意のレコード t R に対して tA] を含むあるバケット Bj がただ一つ存在することになる。こ
のようにバケットを用意しておくと，連続するバケット Bs , Bs+1 ,...,Bt をつないで，区間 xs yt ] をつくる
ことができる。Bi = x x] であるようなこれ以上分解できないバケットを特に，最小粒度バケット（ nest
bucket ）とよぶ。たとえば ，属性 A が年齢を表しているとすると，A の定義域は非負整数で 120 以下で
2
3
x はベクトル，xi はベクトル x の要素である。混乱しないように。
9
図
3: 2 クラス問題
しょう。したがって 121 個の最小粒度バケット i i] (i = 0 1 ::: 120) をつくることができる。別の例とし
て，A を銀行の数百万人の顧客おのおのの預金残高とすると，その定義域は 0 から 1010 まで及ぶかも知
れず，結果として，最小粒度のバケット数は（ 顧客の総数である）数百万に達することもあり得る。この
ように最小粒度バケットの数が巨大な場合は，最小粒度のバケットでなくても十分大きい数（たとえば数
千）のバケットを考えれば，それらを連結することで区間について実用上十分な近似を得ることができる。
3) 2 クラスの最適分割
目的属性が 2 値の場合のカテゴ リ型属性 C 上の最適分割テスト V
dom(C ) を計算するアルゴ リズ
ムを考える。いま, C が dom(C ) = c1 ，
c2 ::: cm のように m 値をとるとすると, V は 2m;1 通り存在す
る。それぞれの V のスタンプポイント p = (x1 ，
x2 ) を図 3 のような 2 次元平面上にプロットする。この平
面上で最適化の基準である上述の Ent 関数は，この平面の a1 > 0, b1 > 0 である任意の 2 点 a = (a1 ，
a2 )，
b = (b1 ，
b2 ) と，その 2 点間に存在する点 c = (1 )a + b (0 1) に対し：
f
g
;
Ent(c) maxfEnt(a) Ent(b)g
を満足する。このように，任意の 2 点間の最大値（あるいは最小値）が，その 2 端点で現れる性質をもつ
関数を凸関数（ convex function ）という。この不等式から，最大の Ent 値をとる分割ルール V に対応す
るスタンプポイントはプロットされた点のうち，凸包上にある点（ 図 3(b) において線でつながっている
点）のいずれかに限定される。Ent 関数のように凸関数性をもつ目的関数を最適化する分割テストを求め
る場合，以下のアルゴ リズムにより O(m log m) 時間で最適な分割テスト V を求めることができる。
4) 2 クラス最適化分割アルゴリズム
(1)
条件属性 C 上の全原子を x1 =(x1 + x2 ) の値で降順に (O(m log m) 時間で) ソートする（ ci ，xi をそ
れぞれソートされた m 個の原子列の i 番目の値，i 番目の原子のスタンプポイントとする）
。
(2) p0 = (0 0)
(3) V = (4) i = 1 から m までの各 i に対し
10
(a)
(b)
(c)
pi = pi;1 + xi
V = V fci g
pi の Ent 関数値が最大値を更新したら V = V とする。
■ R による決定木構築
まずパッケージ tree をインストールし読み込む。
「パッケージ 」→「パッケージのインストール」→ ミ
ラーサイト一覧から「 Japan (Tsukuba) 」などを選ぶ → パッケージ一覧から「 tree 」を選ぶ。\tree" パッ
ケージをインストールしたら，次にそれを読み込む。
「パッケージ 」→「パッケージの読み込み」→ パッ
ケージ一覧から「 tree 」を選ぶ。これで \tree" パッケージが使えるようになる。
データとして \market survey.csv" という名前のファイルを作ったとすると，決定木作成は以下のよう
に行う：
> x <- read.table("market survey.csv", header=TRUE, sep=",")
> x.tr <- tree(pick~., x)
> plot(x.tr)
> text(x.tr)
これにより図 4 のような出力が得られる。market
survey.csv 中の変数の意味は以下の通りである：
pick：優先的に利用する電話会社が AT&T かど うか
income：世帯収入
moves：過去５年間の引っ越し回数
age：被調査者の年齢
education：教育水準
employment：職業の種類
usage：月平均使用量
nonpub：電話帳への掲載の有無
reach.out：割引サービ スの利用
card：テレフォンカード 所有の有無
さて以下のような \tree.control" オプションを用いてパラメータを設定すると決定木の大きさなどを変
えることができる：
> w.tr <- tree(pick~., x, control=tree.control(1000, mincut = 5, minsize = 10, mindev = 0.008))
> plot(w.tr)
> text(w.tr)
ここで \1000"は学習用データのレコード 数，mincut はノード をさらに分割するか判断する為の子ノード
最小レコード 数，minsize は同じ くノード をさらに分割するか判断するための親ノード 最小レコード 数，
mindev はノード 内の尤離度を表す。mincut は minsize の半分よりも大きくすることはできない。
決定木ではモデルの当てはまりの良さを損なわない範囲で，単純な木を構成し直すための剪定を行うこ
とが多い。剪定を行う場合，snip.tree 関数を用いる。例えば以下のようにする。
> w.tr.snip <- snip.tree(w.tr)
入力待ち状態になったら剪定したい木の分岐部分にカーソルを合わせ，クリックする。要らない部分のす
べてでクリックしたらグラフィック画面上で右クリックし「停止」を選ぶ。するとコンソール画面にクリッ
11
図
4:
電話会社のマーケティング調査
クした分岐部分の番号が \node number"という形で表示されるのでその番号をメモしておく。ここで 3 番，
4 番，5 番の分岐部分で剪定したかったならば以下のように入力する：
> w.tr.snip <- snip.tree(w.tr, nodes=c(3,4,5))
> plot(w.tr.snip)
> text(w.tr.snip)
で結果を確認できる。
上では snip.tree 関数を使ってグラフィカルに分岐番号を把握したが，以下のように入力すればテキス
トで決定木を得ることが出来る。そこから分岐番号を把握することも出来る。
> w.tr
■練習問題
車の燃費，車の重量，排気量，走行距離，車種，から成るデータを fuel.xls として作成しました。車の
燃費を，他の変量から予測する回帰木を tree 関数によって作成して下さい。
12