결정트리(Decision Tree)

 

 

 

이번 포스팅은 결정트리(Decision Tree)

에 대해서 학습해보겠습니다

해당 포스팅을 보고 학습하겠습니다.

 

 

https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-4-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACDecision-Tree

머신러닝 - 4. 결정 트리(Decision Tree)

https://wooono.tistory.com/104

[ML] 의사결정트리(Decision Tree) 란?

---

 

 

1. 결정트리(Decision Tree)란?

 

의사결정트리, 의사결정나무라고도 합니다.

 

결정 모델이 Tree 구조를 가지고 있기 때문에

Decision(결정) Tree(나무)라고 합니다.

분류(classification)와 회귀(regression) 모두 가능합니다.

스무고개를 하듯 예(True)/아니오(False)의 질문을 이어가며 학습한다고 합니다.

 

 

 

 

아래는 타이타닉호의 탑승객 생존여부에 대한 의사 결정 트리 예시입니다.

타이타닉호에서는 실제로 사고가 난 후 여자와 아이들을 우선적으로 구조했었고, 

'성인 남성의 생존율' 이 적었습니다.

 

이 사실에 근거해서 타이타닉 사망자,생존자 예측을 해보면

위와 같은 질문을 던지는 트리 구성으로 사망자와 생존자에 대한 예측이 가능합니다.

또한, 예측 결과에 대한 도식화도 비교적 보기 쉽게 구성이 가능합니다,

 

---

 

2. 결정트리의 구조

 

결정트리에서의

한번의 분기 때마다 질문에 따라 변수 영역을 두개로 분류합니다.

이 질문이나 정답을 담은 박스를 Node라고 한다고 하면,

 

맨 처음 노드를 Root Node

중간 분류 노드를 Intermediate Node 

가장 마지막 노드를 Terminal Node 혹은 Leaf Node라고 합니다.

 

 

---

 

3. 불순도(impurity)와 엔트로피(Entropy) 

 

결정트리에서의 분기의 기준을 정할때 불순도(inpurity)라는 기준을 사용하는데요,

불순도란 범주 내에 서로 다른 데이터가 얼마나 섞인지를 나타낸다고 하네요.

다양한 개체들이 섞여있을수록 불순도가 높습니다.

 

불순도를 수치적으로 나타내는 지수가 두가지 있습니다.

지니(Gini)지수, 엔트로피(Entropy) 지수 입니다.

 

 

1) 지니(Gini) 지수

 

m은 데이터의 종류 개수

p는 선택된 데이터 종류에 대한 확률을 나타냅니다.

1에서 이 모든 확률의 제곱의 합을 빼주면 지니 함수를 구할 수 있습니다. 

 

아래의 데이터의 지니 지수를 구하면

 

데이터의 종류는 빨간공, 파란공 2개가 되고,

빨간공의 확률의 제곱은 전체 공 16개 중 10의 제곱 = (10/16) ^ 2

파란공의 확률은 전체 공 16개 중 6의 제곱 = (6/16) ^ 2

지니 지수는 1 - ((10/16)^2 - (6/16)^2) = 약0.47 이 됩니다.

 

 

2) 엔트로피(Entropy) 지수

pi는 각 데이터 종류마다의 확률이 됩니다.

log 함수를 씌워주고 다시 확률을 곱해주네요.

앞에 -를 곱해 양수로 만들어 줍니다.

 

빨간공 : 10/16 * log2(10/16)

파란공 : 10/16 * log2(10/16)이 되므로

엔트로피 지수는 -6/16log2(6/16) -10/16log2(10/16) = 약 0.95가 됩니다.

 

 

분기를 할땐 지니, 엔트로피와 같은 불순도 함수의 값이 줄어드는 방향으로

트리를 형성해야 한다고 합니다.

 

---

 

4. 정보 획득 (Information gain)

 

정보 획득이란 이전 엔트로피에서 분기 이후의 엔트로피를 뺀 수치입니다.

예를들어 분기전 엔트로피가 1이고 분기 후의 엔트로피가 0.6이라면

정보획득은 0.4 입니다.

 

Information gain = entropy(parent) - [weighted average] entropy(children)

수식화 하자면 위와 같습니다.

 

결정 트리는 이 정보 획득을 최대화 하도록 학습이 진행됩니다.

불순도를 0으로 수렴하도록 만드는 것과도 같은 말이겠네요.

 

 

정보획득의 과정은

1. Root 노드의 불순도 계산

2. 나머지 속성에 대해 분할하고 자식 노드의 불순도 계산

3. 각 속성에 대한 정보 획득(Information Gain) 값 계산 후 

정보 획득(Information Gain)이 최대가 되는 분기조건을 찾아 분기

4. 모든 leaf 노드에서 불순도가 0이 될때까지 2,3을 반복함

 

으로 이루어 진다고 합니다.

 

 

아래의 엔트로피 예제를 통해 해당 정보 획득을 구해보겠습니다.

Information gain = entropy(parent) - [weighted average] entropy(children)

 

경사, 표면, 속도 제한을 기준으로

속도의 느림, 빠름을 분류한 표입니다.

경사	표면	속도 제한	속도
가파름	울퉁불퉁	있음	느림
가파름	매끈	있음	느림
평평함	울퉁불퉁	없음	빠름
가파름	매끈	없음	빠름

 

먼저, 속도에 대한 엔트로피를 구하면 

i를 '느림'으로 잡겠습니다.

'p_느림'은 4개 중 2개 이므로 0.5입니다.

'p_빠름'도 마찬가지로 4개 중 2개이므로 0.5 입니다.

-----

 

속도에 대한 엔트로피를 구해보면

-P_느림 * log2(P_느림) - P_빠름 * log2(P_빠름)

=  -0.5 * log2(0.5) - 0.5 * log2(0.5) = 1 

이 값이  entropy(parent) 가 됩니다.

 

-----

경사 '평평함'의 기준으로 엔트로피를 구하면

평평함은 한개고, 해당되는 속도가 1개이므로

엔트로피는 0이 됩니다.

 

경사  '가파름' 기준의 분기에 대한 엔트로피를 구하면

'가파름'의 개수는 3 이고 이때, 속도는 '느림','느림','빠름' 입니다.

 즉 가파름 기준으로 'P_느림' 은 2/3

'P_빠름' 은 1/3 가 됩니다.

경사에 대한 엔트로피를 구하면 

P_느림 * log2(P_느림) - P_빠름 * log2(P_빠름)

= -(2/3) * log2(2/3)  - (1/3) * log2(1/3)

-0.66 * 0.47 - 0.33 * 0.17 = 0.9182

이 값에 대한 가중 평균을 구하면 

[weighted average] entropy(children) = weighted average of 가파름 * entropy(가파름) + weighted average of 평평함 * entropy(평평함)

= 3/4 * (0.9182) + 1/4 * (0) =  0.6886이 됩니다.

 

이제 경사의 정보 획득을 구할 수 있습니다

information gain = entropy(parent) - [weighted average] entropy(children)식에 대입하면

1 - 0.6888 = 0.3112

가 됩니다.

 

------

 

마찬가지로 표면에 대한 엔트로피를 구해보겠습니다.

표면 '울퉁불퉁'의 기준으로 엔트로피를 구하면

울퉁불퉁은 두개고, 해당되는 속도가 2개입니다.

속도는 '느림','빠름' 한개씩이므로

엔트로피는 

-P_느림 * log2(P_느림) - P_빠름 * log2(P_빠름)

= -(1/2) * log2(1/2) -(1/2) *log2(1/2)  = 1

이 됩니다.

 

울퉁불퉁의 엔트로피가 1이므로,

표면  '매끈' 기준의 분기에 대한 엔트로피도 1이 됩니다.

 

가중 평균을 구하면 

[weighted average] entropy(children) = weighted average of 울퉁불퉁* entropy(울퉁불퉁) + weighted average of 매끈 * entropy(매끈)

= 2/4 * 1 + 2/4 * 1 =  1이 됩니다.

 

표면에 대한 정보획득은 

information gain = entropy(parent) - [weighted average] entropy(children)

1 - 1 =

0 이 됩니다.

 

------

 

마지막으로 속도 제한에 대한 엔트로피를 구해보겠습니다.

속도제한 '있음'의 기준으로 엔트로피를 구하면

'있음'은 두개고, 해당되는 속도가 '느림' 2개입니다.

엔트로피는 

-P_느림 * log2(P_느림) - P_빠름 * log2(P_빠름)

= -(2/2) * log2(2/2) -(0/2) *log2(0/2)  = 0

이 됩니다.

속도제한 '없음'의 기준도 마찬가지로 0 이 됩니다.

 

가중 평균을 구하면 

[weighted average] entropy(children) = weighted average of 있음 * entropy(있음) + weighted average of 없음 * entropy(없음)

= 2/4 * 0 + 2/4 * 0 =  0이 됩니다.

 

따라서 속도 제한에 대한 정보획득은

information gain = entropy(parent) - [weighted average] entropy(children)

1 - 0 =

1이 됩니다. 

 

경사, 표면, 속도제한을 기준으로 분기를 했을때

정보 획득은 각각 0.3112 , 0, 1입니다.

결정트리는 정보 획득이 가장 많은 방향으로 학습이 진행됩니다.

그래서 첫 분기점을 속도제한을 기준으로 잡습니다.

 

이 과정을 반복하며,

모든 leaf 노드에서 불순도가 0이 되도록 합니다.

 

---

5. 가지치기(Pruning)

 

 

위의 정보 획득 과정에서 모든 leaf 노드에서 불순도가 0이 되도록 합니다.

그런데 이 과정에서 과적합(Overfitting)이 발생할 수 있습니다.

 

가지치기란 최대 트리로 형성된 결정트리의 특정 노드 및의 하부 트리를 제거하므로서

이 과적합을 막으며 성능을 높이는 것이라고 합니다.

 

max_depth, max_node_leaf를 설정하므로서 가치치기를 진행합니다.

(ML의 boost, randomforest 에서의 파라미터로 많이 봤던..!)

 

 

---

 

6. 장단점

 

1) 장점 

데이터의 전처리를 하지 않아도 됩니다.

수치형, 범주형 변수를 한꺼번에 다룰 수 있습니다.

 

2) 단점

샘플 사이즈가 크면 효율성과 가독성이 떨어짐

과적합의 위험이 있음.

한 번에 하나의 변수를 고려하므로, 상호작용을 파악하기 어려움

약간의 차이로 트리의 구성이 많이 달라짐.

 

 

---

 

 

 

이상으로 결정트리 모델을 알아보았습니다.

 

결정트리의 단점을 극복하기 위해 등장한 모델이 

랜덤포레스트라고 합니다.

(나무가 모여 숲을 이룬다)

 

그리고 이 랜덤포레스트의 알고리즘을 활용한

다양한 부스터 모델들이 많이 쓰이고 있죠!

 

그래서인지 max_depth라던지, max_node_leaf의 

파라미터 개념과

해당 모델들이 전처리가 필요하지 않았던 이유도

좀 더 이해가 되었습니다.

 

 

틀린점이 있다면 지적 부탁드립니다.