의사결정나무 Decision Tree

의사결정나무 Decision Tree

 

 

ID3

ID3 알고리즘은 Iterative Dichotomiser 3의 약자입니다. Dichotomiser는 “이분하다”라는 뜻의 프랑스어로, 반복적으로 이분하는 알고리즘,  Impurity 값으로 엔트로피 (Entropy)를 사용

 

C4.5 알고리즘

정교한 불순도 지표 (Information gain ratio) 활용
범주형 변수 뿐 아니라 연속형 변수를 사용 가능
결측치가 포함된 데이터도 사용 가능
과적합을 방지하기 위한 가지치기

 

ID3 알고리즘에서는 각 시점에서 모든 지표에 대한 분기 전후의 엔트로피를 기반으로 Information Gain (IG)을 계산하고, 이를 최대화하는 방향으로 지표를 결정했습니다.

한계점 : 데이터를 너무 잘게 분해할 수록 Gain값이 좋아지기 때문에 좋은 지표라고 볼 수 없습니다.

C4.5 알고리즘에서는 이와 같은 문제를 해결하기 위해, Information Gain Ratio(GR)라는 지표를 사용

IG는 ID3 알고리즘에서의 Information Gain을 의미하며,  IV는  Intrinsic Value 를 의미

 

특정 지표로 분기했을 때 생성되는 가지의 수를 N𝑁이라고 하고, i𝑖번째 가지에 해당하는 확률을 pi 라고할 때

CART 알고리즘

CART는 ID3알고리즘과 비슷한 시기에, 별도로 개발된 알고리즘으로 Classification And Regression Tree의 약자

불순도: Gini index
Binary tree
Regression tree

CART 알고리즘에서는 모든 조합에 대해 Gini index를 계산한 후, Gini index가 가장 낮은 지표를 찾아 분기

데이터의  통계적 분산정도 를 정량화해서 표현한 값

Regression에서는 분기 지표를 선택할 때 사용하는 index를 불순도 (Entropy, Gini index)가 아닌, 실제값과 예측값의 오차를 사용

where  𝑦^𝑅𝑗  is the mean response for training observartions within  𝑗 th box

전체 오차값

 

------------------------------------------------------------------------------------------------------------------------------------------------------

예측 나무모델

분할을 하고 Y값의 평균을 보여줌

어떻게 분할을 할 것 인가

비용함수를 최소화하는 cm은 그 지역 Y평균값이 된다.

 

X1 = [2,3,5,6,7]일 때 X1≥2로 분할하면 j=1, s=2가 된다.

X1	X2	X3
2	5	1
3	6	7

분할점은 총 6개가 존재하고 모든경우를 고려하여 최적분할변수와 분할점을 찾는다.(Greedy search)

만약 X2≥5이면, j=2 ,s =5

 

분류 나무모델

분류나무 분할법칙

오분류율

 

Information Gain(IG)

 

 

Decision tree의 단점