第四章決定木

4.1基本プロセス

決定ツリーは、分類または回帰可能な指導学習モデルの1つです.決定ツリーは、通常、1つのルーティングノード、複数の内部ノード、および複数のLeafノードまたは端末ノードを含む.
Leafノードの場合、決定結果に対応し、他のノードは属性テストに対応します.各ノードに含まれるサンプルセットは,属性テスト結果に基づいてサブノードに分割され,ルーティングノードをすべてのサンプルを含む集合と見なし,ルーティングノードから各Leafノードに延びるプロセスは一連の判断とテストのプロセスである.
意思決定ツリー学習の目標は,より汎用性の高い意思決定ツリーを得ることである.基本プロセスは、単純で直感的なパーティション化とクエリーポリシーに基づいて再帰的に実行できます.

# Pseudo Code for Decision Tree
input : training set D, Feature A
def TreeGenerate(D,A)
1: node 생성
2: if D의 샘플이 같은 클래스 C에 속하면:
3: 		해당 node를 레이블이 C인 Terminal Node로 정함
4: if A = 0 or D의 샘플이 A 속성에 같은 값 취할 경우:
5: 		해당 node를 Terminal Node로 정하고, 해당 클래스는 D 샘플 중 가장 많은 샘플의 수가 속한 속성으로 정함
6: A에서 최적의 분할 속성 a*를 선택
7: for a*의 각 값 a*[v]에 대해 다음:
		node에서 하나의 가지를 생성.
        D_v는 a*[v] 속성값을 가지는 샘플의 하위 집합으로 표기
        if D_v = 0:
        	해당 가지 node를 Terminal Node로 정하고 해당 클래스는 D 샘플 중 가장 많은 클래스로 정함
        else:
        	TreeGenerate(D_v, A\{a*})을 가지 노드로 정함

output : node를 Root Node로 하는 Decision Tree

🔎 上記のアルゴリズムから、決定ツリーは、次の3つの状況によって再帰的なプロセスが発生していることがわかります.
ノードに含まれるすべての例が同じクラスに属している場合は、分割は行われません...(1)

属性セットが0である場合、またはすべての例がすべての属性で同じ値をとる場合、分割は行われません...(2)

ノードに含まれるサンプルセットが0の場合、分割は行われません...(3)

2つ目の場合、ノードは端末ノードとして定義され、このクラスはノードに含まれる例で多数を占めるクラスとして定義される.
3つ目の場合、ノードは同様にエンドノードとして定義されるが、このクラスは親ノードに含まれる例の多くが属するクラスとして設定される.
注意すべき点は,(2)次の場合はそのノードの後方分布,(3)次の場合は親ノードのサンプル分布をそのノードの前方分布として用いることである.

4.2選択分割

4.2.1情報ゲイン

情報エントロピーは試料セットの純度を測定する最も一般的な指標である.サンプルセットDDDのkk第1クラスのサンプルがpk(k=1,2,...,87 Y∣)pk(k=1,2,...,|Y|)pk(k=1,2,...,8739 Y∣)である場合、Dの情報エントロピーは、
Ent(D)=−∑k=1∣Y∣pk log2pkEnt(D) = -\sum_{k=1}^{|Y|}p_k~log_2p_kEnt(D)=−k=1∑∣Y∣​pk​ log2​pk​
すなわち、Ent(D)Ent(D)Ent(D)Ent(D)の値が小さいほど、DDDの純度が高くなる.
離散属性を持つ属性aaaが取れる値がVVV個{a 1,a 2,...,aV}{a^1,a^2,...,a^V}{a 1,a 2,...,aV}であれば、サンプル数の多い分岐ノードの影響力がより大きいため、サンプルセットDDDに対して属性aaaは分割により得られる情報ゲイン(Information Gain)を計算することができる.
Gain(D,a)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv)Gain(D,a) = Ent(D) -\sum_{v=1}^{V}\frac{|D^v|}{|D|} Ent(D^v)Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)
一般に,情報利得が大きいほど,属性aを用いて分割した場合に得られる純度の向上が高い.したがって,情報利得に基づいて決定ツリーの分割属性を選択することができる.

Yesを+と定義し、Noを-と定義すると、+は9、-は5となります.「Wind」機能を使用した場合の情報ゲインは、次のように計算されます.

上記の[中心プロパティ](Center Properties)を使用すると、次の情報利得が得られます.

両者を比較すると,中心を用いてSセットを分類する場合,Windを用いて分類する場合よりも情報利得が大きく,以下に示すようにすべての特徴を同様にして情報利得を行うことが分かった.

このとき、情報ゲイン最大の特徴を最適分割属性として指定し、次に情報ゲイン最大の特徴を優先分割属性として指定し、分割を継続する.

決定木学習アルゴリズムの核心は,最大情報利得を持つ特性をROOT NODEに最も近づけることである.

4.2.2情報ゲイン率

決定ツリーの結果、各Leafノードに1つのサンプルしか含まれていない場合、このLeafノードの純度はピークに達し、汎用性が悪く、新しいサンプルを効率的に予測することができない.
実際には、情報利得規則は、モデルに悪影響を及ぼすより多くの値を取ることができる属性に有利である.
決定ツリーメソッドの1つであるC 4.5情報ゲインではなく、最適な分割属性を選択します.
GainRatio(D,a)=Gain(D,a)IV(a)Gain_Ratio(D, a) =\frac{Gain(D,a)}{IV(a)}GainR​atio(D,a)=IV(a)Gain(D,a)​
上記の式では、属性aの内在値を以下に示す.
IV(a)=−∑v=1V∣Dv∣∣D∣log2∣Dv∣∣D∣IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|} log_2\frac{|D^v|}{|D|}IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
したがって,属性aの利用可能な値が多ければ多いほど(Vが大きいほど),IV(a)の値が大きくなる.
ここで注意すべき点は、収益率ルールが取得可能な値の少ない属性に偏っているため、C 4である.5アルゴリズムは,属性分割法を用いず,最大収益率を得る.
C4.5アルゴリズムは,人間的手法を用いて,分割属性候補における情報利得が平均値より高い属性を探し出し,そこから収益率が最も高い属性を選択する.

4.2.3キニー係数

CART決定木はキニー係数(Gini Index)を用いて分割属性を選択する.
Gini(D)=∑k=1∣Y∣∑k′≠−kpkpk′Gini(D) =\sum_{k=1}^{|Y|}\sum_{k'\not=- k}p_kp_{k'}Gini(D)=k=1∑∣Y∣​k′​=−k∑​pk​pk′​
=1−∑k=1∣Y∣pk2= 1-\sum_{k=1}^{|Y|}p_k^2=1−k=1∑∣Y∣​pk2​
直感的に言えば、Gini(D)Gini(D)Gini(D)Gini(D)はデータセットDDDにおいて任意の2つのサンプルを選択し、平均した2つのサンプルは異なるカテゴリの確率である.従って、Gini(D)Gini(D)Gini(D)が低いほど、データセットDDDの純度が高くなる.
そこで,最適分割属性として,候補属性セットAから分割後のキニー係数が最小となる属性を選択した.すなわち,全属性に対してキニー係数を計算した後,キニー係数を小さい順に区分した場合,不純度が最も低かった.
🔎 数式で表すと、
a∗=arg⁡min⁡a∈AGini Index(D,a)a* =\arg\min_{a\in A}Gini~Index(D,a)a∗=argmina∈A​Gini インデックス(D,a)になりました.

4.3枝切り(Prunning)

枝分かれは決定木学習アルゴリズムにおける過フィッティングに対応する主な手段である.決定ツリー学習では,訓練サンプルをできるだけ正確に分類するために,ノードの分割過程が繰り返され,過剰な繰返しが過剰な枝分かれを招くことがある.
この場合、「トレーニングサンプルをよく勉強しすぎて、トレーニングセット自体のいくつかの特徴がすべてのデータが持つ一般的な特性を誤認している」という問題が発生する可能性があります.そのため、適切なリスクを回避するために、アクティブに枝を切る必要があります.
💡 枝を切るのは何ですか.
エンドノードを適切なレベルにマージして、決定ツリーと一致しないようにします.

4.3.1予修枝（Pre-Plunning）

プリスプリットは,決定ツリーが成熟する前にアルゴリズムを停止する方法である.たとえば、すべてのインスタンスがクラスに属しているか、属性値が同じ場合は停止します.あるいは、実施例が研究者が任意に設定した数字より少ない場合、樹木の描画を停止するか、または研究者が任意に不順度を設定し、対応するキニー係数/エントロピーに達すると、樹木の描画を停止することもできる.

4.3.2後枝切り(Post-Plunning)

後で枝を打つのは、まず決定木を描き終え、下から上へ枝を打つ方法です.この場合は検証データまたは予測一般化誤差を用い,一般化誤差が分岐後に改善された場合はLeaf Nodeを用いてSubTreeを置き換える.
🔎 先に紹介したCARTアルゴリズムでは,後枝切りのCost−Complexiy概念を提案し,式は以下の通りである.
CC(T)=Err(T)+α∗L(T)CC(T) = Err(T) +\alpha * L(T)CC(T)=Err(T)+α∗L(T)

CC(T):ツリーのコスト複雑度

Er(T):誤分類率(不純度)

L(T):端末ノード数(=構造複雑度)

α\alphaα : Err(T)とL(T)を組み合わせた重み(＝複雑性パラメータ)

こちらです.α\alphaα複雑度パラメータを使用して、ツリーの複雑度を調整します.α\alphaα大きくなると決定木の終端ノードが少し多くなるとCCCC値が大きくなるので、枝を多く取ることで簡単なモデルが作成され、逆に終端ノードが小さくなるとCCCCCC値も大きくならないので、より複雑なモデルが作成されます.
.
.
.

Reference

堅牢な機械学習-機械学習の基本概念の人工知能教科書、株洲の花

https://sanghyu.tistory.com/8