ML memo - Decision Tree

Decision Tree

특징

decision boundary 가 축과 모양이 같음

ID3

Entropy 를 이용함. 이건 낮을 수록 좋음.

Entropy = − ∑ pi​log2​pi​​

$$

information gain 은 정보를 얻기 전 entropy - 정보를 얻은 후 Entropy 이다.

feature 에는 여러 value 가 있을텐데 각 value 마다 entropy 를 구해서 산술평균함.

각 tree node 마다 information gain 을 가장 많이 주는 feature를 고름.

C4.5

InformationGain 을 개량한 GainRatio = InformationGain/SplitIIinfo 를 사용함.

node 가 [3, 4, 5] 로 나눈다면 이것에 대해서 다시 Entropy 를 구해서 나눈다는 이야기.

ID 의 경우 Entropy 가 0 이 필연적이라 Information Gain 이 매우 큼. 

하지만 ID 로 tree 를 구성하면 이는 매우 쓸모없음.

그런데 ID 가 [1,1,1,1,...1] 로 나누므로 나뉜것의 entropy 는 매우 높음. 

따라서 D 에 대해서 Information Gain 보다 GainRatio 가 더 값이 작아져 ID 같은 케이스의 가치를 모델차원에서 낮게 평가 가능함.

 

ID3 에서 Missing value, Numeric value, Pruning, Rule Conversion 기능이 추가됨.

J48

C4.5 개량

Cart

ID3 와 달리 Feature 에 따라서 나누지 않고 모든 feature 의 value 에 따른 binary tree 임.

GINI Inpurity 를 사용함. 두번 골랐을 때 다른게 나올 확률로 작을수록 좋은것.

$GINI\ =\ -\sum _{\ }^{\ }p_i^2$GINI = − ∑ p2i​

$$

위를 이용해서 Information Gain 을 계산함.

ID3 와 마찬가지로 마찬가지로 나뉜비율에 따라 산술평균해서 뺌.