결정 트리(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)

를 바탕으로 필사하며 공부

 

 

---

 

* 결정 트리 (Decision Tree, 의사 결정 트리, 의사 결정 나무)

 

- 분류 (Classification)와 회귀(Regression) 모두 가능한 지도 학습 모델 중 하나

- 결정 트리는 스무고개 하듯이 예/아니오 질문을 이어가며 학습한다.

 

ex) 매, 펭귄, 돌고래, 곰을 구분한다고 생각해보자.

- 매와 펭귄은 날개가 있고, 돌고래와 곰은 날개가 없다.

- '날개가 있나요?' 라는 질문을 통해 매, 펭귄 / 돌고래, 곰 을 나눌 수 있다.

- 매와 펭귄은 '날 수 있나요?' 라는 질문을 통해 나눌 수 있고,

  돌고래와 곰은 '지느러미가 있나요?' 라는 질문을 통해 나눌 수 있다.

 

출처: 텐서 플로우 블로그 / 위 블로그

 

- 이렇게 특정 기준 (질문)에 따라 데이터를 구분하는 모델을 결정 트리 모델이라고 한다.

- 한 번의 분기 때마다 변수 영역을 두 개로 구분한다.

 

- 결정 트리에서 질문이나 정답을 담은 네모 상자 : 노드(Node)

- 맨 첫 분류 기준 (첫 질문) : Root Node

- 맨 마지막 노드 : Terminal Node / Leaf Node

 

출처: ratsgo's blog / 위 블로그

 

- 전체적인 모양이 나무를 뒤집어 높은 것과 같아 이름이 Decision Tree이다.

 

 

---

 

* 결정 트리 알고리즘의 프로세스

출처: 텐서 플로우 블로그 / 위 블로그

 

- 먼저 위와 같이 데이터를 가장 잘 구분할 수 있는 질문을 기준으로 나눔

 

출처: 텐서 플로우 블로그 / 위 블로그

 

- 나뉜 각 범주에서 또 다시 데이터를 가장 잘 구분할 수 있는 질문을 기준으로 나눔

- but, 지나치게 많이하면 아래와 같이 오버피티잉 됨.

- 결정 트리에 아무 파라미터를 주지 않고 모델링하면 오버피팅이 된다.

 

 

 

---

* 가지치기 (Pruning)

 

- 오버피팅을 막기 위한 전략으로 가지치기(Pruning)라는 기법이 있음

- 트리에 가지가 너무 많다면 오버피팅이라 볼 수 있음

- 가지치기: 나무의 가지를 치는 작업

  즉, 최대 깊이나 터미널 노드의 최대 개수, 혹은 한 노드가 분할하기 위한 최소 데이터 수를 제한하는 것

 

- min_sample_split 파라미터를 조정하여 한 노드에 들어있는 최소 데이터 수를 정해주기

- min_sample_split=10 이면 한 노드에 10개의 데이터가 있다면, 그 노드는 더 이상 분기를 하지 않음

 

- max_depth를 통해 최대 깊이를 지정해줄 수도 있다.

- max_depth=4 라면, 깊이가 4보다 크게 가지를 치지 않는다.

- 가지치기는 사전 가지치기와 사후 가지치기가 있지만 sklearn에서는 사전 가지치기만 지원한다.

 

 

 

---

 

* 알고리즘: 엔트로피(Entropy), 불순도(Impurity)

 

- 불순도(Impurity): 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지

- 아래 그림에서 위쪽 범주는 불순도가 낮고, 아래쪽 범주는 불순도가 높다.

- 즉, 위쪽 범주는 순도(Purity)가 높고, 아래쪽 범주는 순도가 낮다.

- 위쪽 범주는 다 빨간점인데 하나만 파란점이므로 불순도가 낮다.

- 반면 아래쪽 범주는 5개는 파란점, 3개는 빨간점으로 서로 다른 데이터가 많이 섞여 있어 불순도가 높다.

 

출처: ratsgo's blog / 위 블로그

 

- 한 범주에 하나의 데이터만 있다면 불순도가 최소(순도는 최대)이고,

  한 범주에 서로 다른 두 데이터가 정확히 반반 있다면 불순도가 최대(순도는 최소)이다.

- 결정 트리는 불순도를 최소화(순도 최대화)하는 방향으로 학습을 진행한다.

 

 

- 엔트로피(Entropy) : 불순도(Impurity)를 수치적으로 나타낸 척도

- 엔트로피가 높다 = 불순도가 높다

  엔트로피가 낮다 = 불순도가 낮다

- 엔트로피 = 1 : 불순도 최대 / 서로 다른 데이터가 정확히 반반 있다.

  엔트로피 = 0 : 불순도 최소 / 한 범주 안에 하나의 데이터만 있다.

 

 

- 엔트로피 구하는 공식: 

출처: 위 블로그

(pi = 한 영역 안에 존재하는 데이터 가운데, 범주 i에 속하는 데이터 비율)

 

 

 

---

 

* 정보 획득 (Information gain)

 

- 엔트로피가 1 -> 0.7 로 바뀌었다면 정보 획득(information gain)은 0.3이다.

- 정보 획득: (분기 이전의 엔트로피) - (분기 이후의 엔트로피)

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

 

- entropy(parent)는 분기 이전의 엔트로피이고, entropy(chlidren)은 분기 이후의 엔트로피

- [weighted average] entropy(children)은 entropy(children)의 가중 평균을 의미

- 분기 이후 엔트로피에 대해 가중 평균을 하는 이유는 범주가 2개 이상으로 쪼개지기 떄문

 

- 결정 트리 알고리즘은 정보 획득을 최대화하는 방향으로 학습이 진행된다.

- 어느 feature의 어느 분기점에서 저옵 획득이 최대화되는지 판단하기 위해 분기가 진행된다.

 

 

 

 

---

 

* 실습

 

- 전반적인 방식은 지금까지 했던 다른 머신러닝 모델과 유사

- Classifier를 만들고, fitting한 뒤, Test해본다.

- Classifier만 DecisionTreeClassifier을 사용한다는 것 빼고는 다른게 없다.

 

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
	cancer.data, cancer.target, stratify=cancer.target, random_state=42)
tree = DecisionTreeClassifier(random_state=0)
tree.fit(X_train, y_train)
print("훈련 세트 정확도: {:.3f}".format(tree.score(X_train, y_train)))
print("테스트 세트 정확도: {:.3f}".format(tree.score(X_test, y_test)))

>>> 훈련 세트 정확도: 1.000
>>> 테스트 세트 정확도: 0.937

 

- 결정 트리의 default는 max_depth, min_sample_split 제한이 없으므로 한 범주에 한 종류의 데이터가 남을 때까지 가지를 친다.

- 따라서 훈련 세트의 정확도는 100%이지만 테스트 세트의 정확도는 93.7%이다.

 

tree = DecisionTreeClassifier(max_depth=4, random_state=0)
tree.fit(X_train, y_train)

print("훈련 세트 정확도: {:.3f}".format(tree.score(X_train, y_train)))
print("테스트 세트 정확도: {:.3f}".format(tree.score(X_test, y_test)))

>>> 훈련 세트 정확도: 0.988
>>> 테스트 세트 정확도: 0.951

 

- 반면 max_depth=4로 설정해주면 오버피팅을 막아 훈련 세트 정확도는 좀 떠렁지지만, 테스트 세트 정확도가 더 높아졌다.

 

 

 

 

---

 

 

 

* 엔트로피 예제

 

출처: 위 블로그

 

- 위 표는 경사, 표면, 속도 제한을 기준으로 속도가 느린지 빠른지 분류해놓은 표

- X variables가 경사, 표면, 속도 제한이고, Y variable이 속도

- 이 때 엔트로피를 기반으로 결정 트리를 모델링 해보겠다.

 

- 속도 라벨에는 slow, slow, fast, fast 총 4개의 examples들이 있다.

- Pi는 한 영역 안에 존재하는 데이터 가운데 범주 i에 속하는 데이터의 비율

- i가 slow라면 slow 라벨 갯수 = 2개, 전체 라벨 갯수 = 4개 이기 때문에 P_slow = 2/4 = 0.5

- 마찬가지로 P_fast = 0.5

 

- 그렇다면, 현재 범주 전체의 엔트로피는? 1

  - 서로 다른 데이터가 정확히 반반 있기 때문

 

 

- 위에서 본 엔트로피 공식에 그대로 대입해 앤트로피를 구해보자

출처: 위 블로그

 

Entropy = -P_slow*log2(P_slow) - P_fast*log2(P_fast)

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

 

 

---

 

* 경사 기준 분기

 

- 먼저 경사(grade)를 기준으로 첫 분기를 해보자.

- 전체 데이터 중 steep은 3개, 이 때의 속도는 각각 slow, slow, fast이다.

- flat의 데이터는 총 1개, 이 때의 속도는 fast

 

- flat에 해당하는 노드의 엔트로피는?

출처: Udacity / 위 블로그

- 오른쪽 노드에서 한 노드에 fast라는 하나의 데이터만 존재하기 때문에 엔트로피는 0이다.

- 따라서, entropy(flat) = 0

 

- entropy(steep)은 왼쪽 노드

  - slow가 2개, fast가 1개

  - entropy(steep) = - P_slow * log2(P_slow) - P_fast * log2(P_fast)

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

                               = 0.9184

 

- 분기 이후 노드에 대한 가중 평균 구해보자

- [weighted average] entropy(children)

  = weighted average of steep * entropy(steep) + weighted average of flat * entropy(flat)

  = (3/4) * (0.9184) + (1/4) * 0

  = 0.6888

 

- 따라서 경사(grade)를 기준으로 분기한 후의 엔트로피는 0.6888

 

- 이제 정보 획득 공식을 통해 정보 획득량을 구해보자

- information gain

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

  = 1 - 0.6888

  = 0.3112

 

- 경사 feature를 기준으로 분기를 했을 때는 0.3112만큼의 정보 획득(information gain)이 있다는 뜻!

 

 

---

 

* 표면 기준 분기

 

- 표면(bumpiness)를 기준으로 분기 했을 때는 bumpy에 slow, fast, smooth에도 slow, fast가 있다.

- 하나의 범주에 대해 서로 다른 데이터가 정확히 반반이므로 엔트로피는 1.

 

- entropy(bumpy) = - P_slow * log2(P_slow) - P_fast * log2(P_fast) = 1

- entropy(smooth) = - P_slow * log2(P_slow) - P_fast * log2(P_fast) = 1

 

- [weighted average] entropy(children)

  = weighted average of bumpy * entropy(bumpy) + weighted average of smooth * entropy(smooth)

  = (2/4) * 1 + (2/4) * 1

  = 1

 

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

 

- 표면을 기준으로 분기했을 때는 정보 획득이 전혀 없다는 뜻!!

 

 

---

* 속도 제한 기준 분기

 

출처: Udacity / 위 블로그

- entropy(yes) = -P_slow * log2(P_slow) - P_fast * log2(P_fast) = -1 * log2(1) - 0 * log2(0) = 0

- entropy(no) = -P_slow * log2(P_slow) - P_fast * log2(P_fast) = 0 * log2(0) - 1 * log(1) = 0

 

따라서, information gain = 1 - (2/4) * 0 - (2/4) * 0 = 1

 

 

---

 

- 경사, 표면, 속도제한 기준으로 분기했을 때 정보 획득은 각각 0.3112, 0, 1이다.

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

- 따라서 첫 분기점을 속도제한 기준으로 잡는다.

- 이런식으로 max_depth나 min_sample_split으로 설정한 범위까지 분기를 하게 된다.

- 이것이 바로 결정트리의 전체적인 알고리즘