관리 메뉴

귀퉁이 서재

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

머신러닝

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

Baek Kyun Shin 2019. 7. 22. 23:23

결정 트리(Decision Tree, 의사결정트리, 의사결정나무라고도 함)는 분류(Classification)와 회귀(Regression) 모두 가능한 지도 학습 모델 중 하나입니다. 결정 트리는 스무고개 하듯이 예/아니오 질문을 이어가며 학습합니다. 매, 펭귄, 돌고래, 곰을 구분한다고 생각해봅시다. 매와 펭귄은 날개를 있고, 돌고래와 곰은 날개가 없습니다. '날개가 있나요?'라는 질문을 통해 매, 펭귄 / 돌고래, 곰을 나눌 수 있습니다. 매와 펭귄은 '날 수 있나요?'라는 질문으로 나눌 수 있고, 돌고래와 곰은 '지느러미가 있나요?'라는 질문으로 나눌 수 있습니다. 아래는 결정 트리를 도식화한 것입니다.

출처: 텐서 플로우 블로그

이렇게 특정 기준(질문)에 따라 데이터를 구분하는 모델을 결정 트리 모델이라고 합니다. 한번의 분기 때마다 변수 영역을 두 개로 구분합니다. 결정 트리에서 질문이나 정답을 담은 네모 상자를 노드(Node)라고 합니다. 맨 처음 분류 기준 (즉, 첫 질문)을 Root Node라고 하고, 맨 마지막 노드를 Terminal Node 혹은 Leaf Node라고 합니다.

출처: ratsgo's blog

전체적인 모양이 나무를 뒤짚어 높은 것과 같아서 이름이 Decision Tree입니다.

프로세스

결정 트리 알고리즘의 프로세스를 간단히 알아보겠습니다.

출처: 텐서 플로우 블로그

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

출처: 텐서 플로우 블로그

나뉜 각 범주에서 또 다시 데이터를 가장 잘 구분할 수 있는 질문을 기준으로 나눕니다. 이를 지나치게 많이 하면 아래와 같이 오버피팅이 됩니다. 결정 트리에 아무 파라미터를 주지 않고 모델링하면 오버피팅이 됩니다. 

출처: 텐서 플로우 블로그

가지치기(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에 속하는 데이터의 비율)

엔트로피 예제

공식을 활용하여 엔트로피를 구하는 예제를 살펴보겠습니다. 아래는 경사, 표면, 속도 제한을 기준으로 속도가 느린지 빠른지 분류해놓은 표입니다.

경사 표면 속도 제한 속도
steep bumpy yes slow
steep smooth yes slow
flat bumpy no fast
steep smooth no fast

첫줄을 보면 경사가 가파르고(steep), 표면이 울퉁불퉁하고(bumpy), 속도 제한이 있다면(yes) 속도가 느리다(slow)라고 분류했습니다. X variables가 경사, 표면, 속도 제한이고, Y variable이 속도입니다. 이때 엔트로피를 기반으로 결정 트리 모델링 해보겠습니다.

속도 라벨에는 slow, slow, fast, fast로 총 4개의 examples가 있습니다. Pi는 한 영역 안에 존재하는 데이터 가운데 범주 i에 속하는 데이터의 비율이라고 했습니다. i를 slow라고 했을 때, P_slow = 0.5입니다. slow 라벨 갯수 = 2개, 전체 examples 수 = 4개이기 때문에 P_slow = 2/4 = 0.5입니다. 마찬가지로, P_fast도 0.5입니다. fast 라벨 갯수가 2개이기 때문에 2/4로 0.5입니다. 즉 P_slow = 0.5, P_fast = 0.5입니다.

그렇다면 현재 범주 전체의 엔트로피는 얼마일까요? 바로 1입니다. 서로 다른 데이터가 정확히 반반 있기 때문입니다. 위에서 봤던 엔트로피 공식에 그래도 대입을 해 엔트로피를 구해보겠습니다.

엔트로피 공식

Entropy = - P_slow * log(P_slow) - P_fast * log(P_fast) = - 0.5 * log₂(0.5) - 0.5 * log₂(0.5) = 1

공식에 의해서도 1이라고 구할 수 있고, 데이터가 정확히 반반 (slow 2개, fast 2개)이므로 1이라고 할 수 있습니다.

정보 획득 (Information gain)

엔트로피가 1인 상태에서 0.7인 상태로 바뀌었다면 정보 획득(information gain)은 0.3입니다. 분기 이전의 엔트로피에서 분기 이후의 엔트로피를 뺀 수치를 정보 획득이라고 합니다. 정보 획득은 아래와 같이 공식화할 수 있습니다.

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

entropy(parent)는 분기 이전 엔트로피이고, entropy(children)은 분기 이후 엔트로피입니다. 이때, [weighted average] entropy(children)는 entropy(childeren)의 가중 평균을 뜻합니다. 분기 이후 엔트로피에 대해 가중 평균을 하는 이유는 분기를 하면 범주가 2개 이상으로 쪼개지기 때문입니다. 범주가 하나라면 위 엔트로피 공식으로 바로 엔트로피를 구할 수 있습니다. 하지만 범주가 2개 이상일 경우 가중 평균을 활용하여 분기 이후 엔트로피를 구하는 것입니다.

결정 트리 알고리즘은 정보 획득을 최대화하는 방향으로 학습이 진행됩니다. 어느 feature의 어느 분기점에서 정보 획득이 최대화되는지 판단을 해서 분기가 진행됩니다. 

위에서 예로 든 속도 문제를 다시 보겠습니다. 맨 처음 전체 엔트로피 = 1 이라고 했습니다. 즉, entropy of parent = 1입니다.

entropy(parent) = 1

경사 기준 분기

우선, 경사(grade)를 기준으로 첫 분기를 해보겠습니다. 전체 데이터 중 steep는 3개, flat는 1개 있습니다. steep와 flat을 기준으로 분기를 해주면 결과는 아래와 같습니다. steep에 해당하는 데이터는 총 3개이며, 이때의 속도는 slow, slow, fast입니다. 반면 flat에 해당하는 데이터는 1개이며, 이때의 속도는 fast입니다. flat에 해당하는 노드의 엔트로피는 얼마일까요? (아래 그림에서 오른쪽 노드) 한 노드에 fast라는 하나의 데이터만 존재하므로 엔트로피는 0입니다.

따라서, entropy(flat) = 0 입니다.

출처: Udacity

이제 entropy(steep). 즉, steep로 분기했을 때의 엔트로피를 구해보겠습니다. 이는 위 그림의 왼쪽 노드에 해당합니다. slow가 2개, fast가 1개이므로 P_slow = 2/3, P_fast = 1/3입니다. 따라서 엔트로피 공식에 의해 

entropy(steep) = - P_slow * log2(P_slow) - P_fast * log2(P_fast) = - (2/3) * log2(2/3) - (1/3) * log2(1/3) = 0.9184 입니다.

entropy(flat) = 0 이고, entropy(steep) = 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

(weighted average of steep = 3/4인 이유는 4개의 데이터 중 steep에 해당하는 데이터는 3개이기 때문입니다. 마찬가지로 weighted average of flat = 1/4인 이유는 4개의 데이터 중 flat에 해당하는 데이터는 1개이기 때문입니다.)

따라서, 경사(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/2) * log2(1/2) - (1/2) * log2(1/2) = 1

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

입니다. 따라서,

information gain = entropy(parent) - [weighted average] entropy(children)  = 1 - (2/4) * 1 - (2/4) * 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) * log2(1) = 0

입니다. 따라서,

information gain = 1 - (2/4) * 0 - (2/4) * 0 = 1입니다.

경사, 표면, 속도제한 기준으로 분기 했을 때 정보 획득은 각각 0.3112, 0, 1입니다. 결정트리는 정보 획득이 가장 많은 방향으로 학습이 진행된다고 했습니다. 따라서 첫 분기점을 속도제한 기준으로 잡습니다. 이런식으로 max_depth나 min_sample_split으로 설정한 범위까지 분기를 하게 됩니다. 이것이 바로 결정트리의 전체적인 알고리즘입니다.

실습

사이킷런에서 제공하는 유방암 데이터를 활용하여 결정트리 분류 실습을 해보겠습니다. 전반적인 방식은 지금까지 했던 다른 머신러닝 모델과 유사합니다. Classifier를 만들고, fitting한 뒤, Test해보는 식입니다. Classifier만 DecisionTreeClassfier를 사용한다는 것을 제외하고는 다른게 거의 없습니다.

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로 설정해주면 오버피팅을 막아 훈련 세트 정확도는 아까보다 떨어지지만 테스트 세트 정확도가 더 높아졌습니다.

References

Reference1: 텐서 플로우 블로그 (결정 트리)

Reference2: ratsgo's blog (의사결정나무)

27 Comments
  • 프로필사진 Inmo Chung 2020.02.06 13:45 너무 도움이 됐습니다. 쓰신 글 모두 잘 읽어볼게요.
  • 프로필사진 Baek Kyun Shin 2020.02.06 16:08 신고 엇 감사드립니다 ~! 도움이 되셨다니 제가 다 기쁘네요 ^^
  • 프로필사진 이동희 2020.04.14 09:40 안녕하세요, 항상 좋은 글 잘 보고 있습니다~

    혹시 위에 엔트로피 공식에서 'Pi = 범주 i에 속한 데이터의 비율'이라고 하셨는데, '한 개 범주내에 존재하는 i번째 데이터 클래스의 비율'이 좀 더 명확한 표현일까요? 작성하신 의도를 제가 제대로 파악하지 못한 점이 혹시나 있을수도 있어서 조심스레 여쭤봅니다~ ㅎㅎ

  • 프로필사진 Baek Kyun Shin 2020.04.14 10:47 신고 안녕하세요~ 읽어주셔서 감사합니다.

    제가 Pi를 좀 불명확하게 표현했었네요. 좀 더 정확하게 표현하자면,

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

    이라고 할 수 있을 것 같습니다. i번째보다는 범주 i라고 명시하는 게 더 정확하다고 생각합니다.

    위에서 제가 예시로 든 P_slow를 보시면,
    - 한 영역: 여기서는 slow, slow, fast, fast로 총 4개의 데이터를 포함한 영역
    - 범주 slow: slow를 포함하는 데이터 (총 2개) 입니다.

    따라서 한 영역 안에 존재하는 데이터 가운데 범주 slow에 속하는 데이터의 비율: 1/2이 되는 것입니다.

    동희님께서 말씀하신 것도 유사한 뜻이 되기는 하지만 이렇게 하는 게 조금 더 명확한 표현이지 않을까 싶습니다. ^^

  • 프로필사진 이동희 2020.04.20 11:23 명확한 설명 감사합니다!! ^^
  • 프로필사진 장원영 2020.07.11 14:16 글 잘 보고 있습니다.
    [weighted average] entropy(children) = weighted average of steep * entropy(steep) + weighted average of flat * entropy(flat)
    이것도 그냥 공식인건가요 ?

    다른 곳에서 봤을 때는
    G(S) = E(S) - E(S`) 로만 표시가 되어 있어서 여쭈어 봅니다.
  • 프로필사진 Baek Kyun Shin 2020.07.11 19:42 신고 읽어주셔서 감사합니다.

    [weighted average] entropy(children) = weighted average of steep * entropy(steep) + weighted average of flat * entropy(flat) 도 일종의 공식이라고 보시면 됩니다.
    이를 가중 평균이라고 합니다.

    또한, 다른 자료에서 보신 G(S) = E(S) - E(S`)은 정보 획득(Information gain)을 구하는 공식을 뜻하는 것 아닌가 싶습니다.

    G(S): 정보 획득
    E(S): 변화 전 엔트로피
    E(S`): 변화 후 엔트로피의 가중 평균
    이라 하면 G(S) = E(S) - E(S`) 가 됩니다.
    찾으신 자료가 어떤 것인지 몰라 정확하지는 않습니다 ^^
  • 프로필사진 장원영 2020.07.11 14:19 또 질문이 생겨서..
    x 항목이 3개이니 max_depth = 3 이 되어야 하는 것이 아닌지요 ?

    항목과 max_depth는 상관성은 없는 건지요?
  • 프로필사진 Baek Kyun Shin 2020.07.11 19:45 신고 아, 맨 아래 코드는 제가 설명을 위해 예로 든 자료와는 다른 데이터로 돌린 것이라 max_depth가 다릅니다.
    코드에서는 사이킷런에서 제공하는 유방암 데이터를 결정트리로 돌린 것이고 이때 max_depth를 4로 설정한 겁니다.

    참고로 말씀드리면, 위에서 설명할 때 예로든 grade, bumpiness, speed limit을 속성으로 갖는 데이터는 속성이 총 3개 이므로 max_depth가 최대 3이 되는 게 맞습니다. 코드 작성시 max_depth를 설정하지 않아도 default로 끝까지 탐색을 합니다.
    즉, tree = DecisionTreeClassifier(random_state=0)
    이렇게만 해도 최대 깊이가 3개가 되게 하죠
    그러나 오버피팅을 막기 위해 보통은 max_depth=2 정도로 최대 깊이보다 작게 설정합니다.

    설명이 장황 했는데, 이해가 안 가는 게 있으시다면 또 말씀해주세요 ~
  • 프로필사진 장원영 2020.07.13 10:00 첫번째 문제는 제가 로그 공식을 몰라서 생겼던 문제였습니다. 지금은 이해 했습니다.
    두번째 문제에 대한 친절한 설명 감사드립니다.
    앞으로도 정독 해 보겠습니다.
  • 프로필사진 Baek Kyun Shin 2020.07.13 10:44 신고 감사합니다 ^^
  • 프로필사진 nv 2020.07.28 14:50 DecisionTreeClassifier 는 기본으로 지니 계수를 이용해 데이터 세트를 분할하는것으로 알고있는데 지니 계수도 알려주실 수 있나요?
  • 프로필사진 Baek Kyun Shin 2020.08.02 01:02 신고 앗 이 댓글을 이제야 봤네요 답변이 늦어져 죄송합니다 ㅠㅠ
    불순도를 측정하는 지표로는 엔트로피도 있고 지니 계수도 있습니다. 제 포스팅에서는 엔트로피를 예로 들어 설명을 드렸습니다.
    말씀하신 것처럼 DecisionTreeClassifier의 분류 기준은 default가 지니 계수입니다. criterion='entropy'로 설정하면 엔트로피로 불순도를 구해 분류를 합니다.
    지니 계수를 구하는 공식은 검색하면 바로 나올 겁니다 :)
  • 프로필사진 선채소 2021.04.25 13:40 신고 오늘도 잘보고 갑니다. 학부 기계학습 수업 공부하는데에 도움 많이 되네요! 감사합니다.
  • 프로필사진 Baek Kyun Shin 2021.04.25 22:22 신고 감사드립니다 ^^
  • 프로필사진 P.hD 2021.05.05 23:53 신고 안녕하세요 글 잘보았습니다!
    결정트리에서 불순도를 최소화하는 방향으로 학습을 진행한다고 하셨는데
    그 방법은 어떻게 알수있나요? 그러니까 특정 기준(질문)을 정하는 방법은 어떻게 구하나요?
    혹시 거기에도 여러 방법이 있는걸까요?
  • 프로필사진 Baek Kyun Shin 2021.05.06 19:18 신고 안녕하세요! 읽어주셔서 감사드립니다.

    엔트로피(Entropy)는 불순도(Impurity)를 수치적으로 나타낸 척도입니다. 따라서 불순도를 최소화하는 방향으로 학습한다는 의미는 엔트로피에 따라(엔트로피 공식을 이용해) 학습한다는 의미와 같은 말입니다.
    본문에서 설명드린 엔트로피에 따라 분기하는 게 바로 불순도를 최소화하는 방향으로 학습하는 것입니다.
    물론 엔트로피 외에도 지니 계수를 활용하는 방법도 있습니다.
  • 프로필사진 ㅅㅎ 2021.05.16 12:40 자세한 설명 너무너무너무 감사합니다ㅠㅠㅠ 진짜 도움 많이 됐어요.
    다른 글도 열심히 읽어보겠습니다.
  • 프로필사진 Baek Kyun Shin 2021.05.16 13:14 신고 아이고 읽어주셔서 감사합니다 ~ ^^
  • 프로필사진 IY 2021.06.05 10:59 제 은인이십니다
  • 프로필사진 IY 2021.06.05 10:59 제 은인이십니다
  • 프로필사진 IY 2021.06.05 11:00 정말 도움 많이 됐습니다! 명쾌하고 설명 flow도 너무 좋네요!!
  • 프로필사진 Baek Kyun Shin 2021.06.05 15:53 신고 과찬이십니다. 참고한 자료가 좋았던 거죠 ㅎㅎ 댓글 남겨주셔서 감사드립니다 :)
  • 프로필사진 Who 2021.09.28 19:40 글을 쉽게 잘 쓰시네요 큰 도움 됐습니다
  • 프로필사진 Baek Kyun Shin 2021.09.28 22:24 신고 도움이 되셨다니 기쁘네요. 읽어주셔서 감사합니다 ^^
  • 프로필사진 카펠 2022.03.08 21:39 신고 정말 학습에 큰 도움되었습니다. 감사합니다!
  • 프로필사진 Baek Kyun Shin 2022.03.09 11:19 신고 읽어주셔서 고맙습니다!
댓글쓰기 폼