2020. 7. 19. 16:24ㆍML in Python/Knowledge
이 게시글에서는 Decision Tree의 개념만 다룰 것이다. Python으로 구현하고자 한다면 아래 실습링크를 통해서 학습하길 바란다.
https://todayisbetterthanyesterday.tistory.com/38
[Python] 의사결정나무(DecisionTree) 구현 - 분류(Classifier)/회귀(Regressor)/가지치기(Pruning)
*아래 학습은 Fastcampus의 "머신러닝 A-Z까지"라는 인터넷 강의에서 실습한 내용을 복습하며 학습과정을 공유하고자 복기한 내용입니다. 의사결정 나무는 간단하게 말해서 if~else와 같이 특정 조��
todayisbetterthanyesterday.tistory.com
1. 요약
의사결정 나무는 간단하게 말해서 if~else와 같이 특정 조건을 기준으로 O/X로 나누어 분류/회귀를 진행하는 tree구조의 분류/회귀 데이터마이닝 기법이다.
이해도가 매우 높고 직관적이라는 장점이 있다. 하지만 변동성이 높고 샘플에 민감할 수 있다는 단점 또한 존재한다.
여튼, 높은 해석력과 직관성, 그리고 범용성으로 인해 실제에서 많이 사용되며, 의사결정나무도 많은 머신러닝 기법과 동일하게 종속변수의 형태에 따라 분류와 회귀 문제로 나뉜다.
종속변수가 범주형일 경우 Decision Tree Classification으로 분류를 진행하고, 종속변수가 연속형일 경우 Decision Tree Regression으로 회귀를 진행한다.
2. Tree구조의 이해
아래 그림을 한 번 보자.
이는 Tree구조인데 Decision Tree만이 아니라 자료구조에서 사용되는 Tree와 같은 형태이다. Tree를구성하는 가장 큰 두 가지 구성 요소는 node와 edge이다. node는 분류의 기준이 되는 변수가 위치하는 곳이다. 위에서는 사각형을 가리킨다. Decision Tree에서는 node를 기준으로 샘플을 나누는 작업을 진행한다.
node
node에는 Parent node / Child node / Root node / Leaf node / Internal node가 존재한다.
- Parent node는 상대적인 개념으로 특정 노드의 바로 위 노드를 의미한다.
- Childe node는 Parent node와 반대되는 상대적 개념으로 특정 노드의 바로 아래 노드를 의미한다.
- Root node는 상위 노드가 없는 가장 위에 존재하는 노드를 의미한다.
- Leaf node (= Tip)는 Childe노드가 없는 가장 아래의 노드를 의미한다. 위에서 보면 3개가 존재한다.
- Internal node는 Leaf node가 아닌 노드를 의미한다.
edge
edge는 노드를 연결시키는 다리역할을 한다. 이는 샘플을 분류하는 조건이 위치하는 곳이다. node에는 변수가 위치하나 edge에는 조건이 위치한다는 것을 헷갈리지 말자.
그리고 마지막으로 depth를 알아야한다. depth는 트리를 구성하는 직접적인 요소는 아니지만, 각각의 트리가 가진 중요한 특성으로 여겨진다.
depth
depth는 Root node에서 특정 노드까지 도달하기 위해 거쳐야하는 Edge의 수이며, 트리의 depth가 얼마냐고 할 때는 Root node부터 Leaf node까지 거쳐야하는 edge 수를 보통 의미한다. 위 그림의 Tree는 depth=3 인 트리인 것이다.
3. 엔트로피 ( Entropy )
Decision Tree( 의사결정나무 )의 원리를 수학적으로 알아보기 전에 엔트로피에 대해서 알아볼 필요가 있다. play tennis란 예제를 통해서 알아보도록 하자. 아래의 데이터 셋은 play tennis 데이터로 마지막 열에 Play Tennis가 Target이고 Outlook / Temperature / Humidity / Wind 가 Features이다.
그리고 아래는 종속변수가 2개이기에 이진형(two class) 변수이다.
우리의 목표는 위의 데이터셋을 통해서 테니스를 칠 것인가 예상하는 Decision Tree를 만들어내고자 한다. Decision Tree는 다음처럼 형성될 것이다.
이 트리를 나누는 기준이 무엇이었을까? 이 기준으로 사용되는 것이 바로 엔트로피(Entropy)이다. 물론 다른
목적함수도 많이 쓰인다. 연속형 변수일 경우 MSE/MAPE와 같은 목적함수/비용함수(loss function)를 많이 사용하며, 파이썬 실습때 알아본 기본적인 DecisionTree에 적용된 목적함수/비용함수는 gini계수가 쓰인다.
여기서는 엔트로피(Entropy)를 기준으로 트리가 형성되는 과정을 다룰 것이다. 다시 돌아가서 엔트로피를 직관적으로 말하자면, 0 또는 1일 확률이 최소이며 0.5일 확률이 최대인 함수이다. 바로 아래의 곡선이 play tennis 예제를 활용한 엔트로피 함수를 표현한 것이다.
확률이 0.5가 최대가 되는 지점을 보면 Play tennis가 No/Yes가 고루고루 섞여 0.5의 확률을 갖는다. 반면 0일 경우는 NO만 1일 경우는 YESY만 존재한다. 즉 잘 섞여있는 경우 entropy가 높고 분리가 확실하게 되어있을 수록 entropy는 낮아진다.
이 엔트로피 함수를 수식으로 표현하면 아래와 같다. ( 정확히 말하면 Cross-Entropy함수이다. )
p = 0 을 대입해보자, 이때 entropy = 0 이다. p = 1을 대입해도 0이 나온다. 1/2를 대입하면 entropy = 1이다.
즉, 의사결정나무는 이 엔트로피를 낮추는 방향(분류를 제대로 하는 방향)으로 분류작업을 진행한다.
그렇다고 엔트로피를 아무런 순서없이 랜덤하게 낮추는 것은 아니다. 이것은 Information Gain을 통해서 각각의 변수의 중요도를 결정한다.
4. Information Gain
Information Gaind은 Decision Tree에서 변수의 중요도를 선택하는 지표이다. Entropy로 낮추는 방향으로 의사결정나무가 형성될때, 각 변수들의 Information Gain이 계산된다. Information Gain을 식으로 표현하자면 아래와 같다.
이 Information Gain이 높으면 상위노드(parent node)로 간다. 그리고 낮다면 하위노드(child node)로 가는 것이다. 아래 그림을 통해서 보자.
위 그림을 보면 Outlook이 가장 높은 Root node이다. 분명 Outlook과 Humidity, Wind, Overcast는 중요도가 정해지지 않았던 설명변수(features)였다. 하지만 의사결정나무가 형성된 이후에는 중요도가 생긴 셈이다. 이 중요도를 결정한 것이 바로 Information Gain이다.
위의 트리를 보면 가지가 3개로 정해졌는데 Entropy를 낮추는 방향으로 가지가 형성된다고 하였다. 그러면 Entropy(before)은 Outlook인 것을 알겠는데 Entropy(after)은 무엇을 뜻하는 것인가? Humidity인가? Overcast인가? Wind인가? 셋 다 같은 depth = 1인 노드인데 무엇을 어떻게 적용할지의 문제가 생긴다. 그래서 Information Gain에 사용될 Entropy(after)을 계산하는 방식으로 가중평균을 사용한다.
위의 그림을 보면 Entropy(before)은 Root node의 Entropy이고 Entropy(after1)은 Humidity node, Entropy(after2)는 Overcast node, Entropy(after3)는 Wind node의 Entropy이다. 이 childe node 3가지의 entropy를 가중평균내는것은 아래 식과 같다. 그리고 이 식이 바로 Entropy(after)에 들어갈 값이다.
위의 식을 일반화하면 아래 식과 같다. 이것은 다시말해 Information Gain에 사용되는 Entropy(after)이다.
정리를 하자면 Information Gain은 아래와 같다고 하였다.
여기서 before부분은 상위노드이고, Entropy after는 하위 분류된 노드들의 Entropy 가중평균이며, Decision Tree를 구성할 때, 이 Information Gain이 높은 노드가 상위 노드로 위치하며 Entropy를 낮추는 방향으로 Decision Tree가 형성된다. ( Gini와 오분류율을 사용한 Decision Tree더라도 과정이 동일하다. )
5. Decision Classification Tree ( 의사결정 분류 나무 )
위의 트리에서 기준이 되는 petal width를 X1이라고 하고, petal length를 X2라고 해보자. 그러면 위의 play tennins 의사결정 나무를 영역으로 표시하면 다음과 같은 block형태로 같은 형태로 표시할 수 있다. (완전하게 동일하진 않다.)
위의 영역을 보면 X1이 t3보다 클 경우와 작을 경우, t1보다 작을경우/X2가 t2보다 클 경우와 작을 경우로 분리된다. 즉, 설명변수의 특성이 특정 값을 기준으로 나누어지는 영역을 만들어 낸다는 것이다. 이때, 각 영역(위의 영역표에서 Rm)을 나누는 기준은 Inforamtion Gain을 최대화 시키는 지점(t1,t2,t3)인 것이다.
이때 나눠진 영역들의 sample을 통해서 target Y가 특정 집단에 속할 경우 추정이 가능하다.
결정된 Rm(영역)에 대해서, m번째 노드가 k범주일 확률은 m번째 노드에 있는 전체 샘플의 개수 중에서 y = k 인 개수이다.
즉, 영역내에서 상대 비율의 개념이다.
그리고 이 상대비율이 가장 커지는 Pmk범주가 추정된 Y의 범주이다.
위의 의사결정나무 예시를 보면 색칠해진 부분의 class = setosa / versicolor / virginica가 바로 추정된 Y의 범주인 것이다. 위의 나무에서 Pm(setosa) = 50/50이고, Pm(versicolor) = 49/54이고, Pm(virginica) = 45/46으로 가장 큰 범주가 선택된 것이다.
5. Decision Regression Tree ( 의사결정 회귀 나무 )
위의 트리는 Decision Regression Tree이다. Classification Tree와 생김새는 비슷하나, 위의 추정 value를 보면 0.052, 0.714 등 연속형(실수) 값을 출력한다. 이 트리를 구성하는 과정은 Classification에서 영역으로 표시한 방법과 동일하다.
이를 다시 R1~R5까지 나눈 조건을 아래와 같이 표기할 수 있다.
이때 발생하는 Y의 추정값은 아래의 식과 같이 표기된다.
이때 x가 Rm에 포함될 경우 Cm이란 일정한 값을 도출하는 것이다. 이를 시각적으로 한 번 생각해 생각해보면 아래와 같이 계단형으로 표시될 수 있다. 실제로 위의 트리에서 나눈 조건이 무한하지 않기에 계단형 형태가 도출되는 것이다.
그렇다면 Decision Regression Tree에서는 Rm(나눠진 영역)을 어떻게 구성하나? 우선 Classification 모형과 마찬가지로 일정 기준으로 나눈다. 특정 기준으로
이때 classification에서는 엔트로피/지니계수를 사용했지만, regression에서는 mse를 사용하여 이를 최소화 하는 s점을 찾는다.
(y_i - c_i)^2는 MSE를 나타내며 C hat은 그렇기에 아래와 같이 범주에 속한 값들의 평균을 사용한 것이다.
이러한 방식으로 Decision Regression Tree의 영역구분이 이루어진다. (Classification도 동일하다 MSE -> Entropy or Gini 사용)
결론적으로 Cm은 그 범주에 포함되어있는 샘플들의 평균값이며
예측값은 타겟의 특성이 해당 범주에 속할 경우 Cm값이 곧 예측값이라는 것이다.
그렇기에 Regression Tree의 경우 연속형 값이 결과값으로 나타나지만, 실제 연속적인 그래프의 형태보단 계단적 형태의 결과값이 나타난다.
이상 범주형/연속형 종속변수를 갖는 Decision Classification Tree / Decision Regression Tree에 대해서 알아보았다.
※ ADP 지식
추가적으로 지니지수의 형태는 아래와 같다. 지니지수 또한 의사결정 트리에서 사용되며, 엔트로피와 동일하게 높을수록 분류의 불순도가 높다고 판단되어 이 지니지수를 낮추는 방향으로 분류작업을 진행한다.
게다가 상황에 따른 알고리즘 분류와 기준 변수 선택법은 다르다. 아래의 모든 기준 변수 선택법에 대해서는 다루지 못하겠지만, 공통적으로 분류문제(이산형 변수)의 경우는 기준 변수가 높을수록 불순도가 높은 것이며, 낮추는 방향으로 학습을 진행한다.
그리고 회귀문제(연속형 변수)의 경우는 F-통계량을 사용할 경우, 값이 클수록 오차의 변동에 비해 처리(treatment)의 변동이 크다는 것을 의미하여 자식노드들간이 이질적임을 의미한다. 그렇기에 F-통계량이 커지는 방향(p-value는 작아지는 방향)으로 가지분할을 수행하며, 분산의 감소량을 고려하는 경우에도 이 값이 최대화되는 방향으로 가지분할을 수행한다.
간단하게 말해서, 분류의 경우는 기준 변수를 낮추는 방향으로, 회귀의 경우는 기준변수를 높이는 방향으로 학습을 진행한다는 것이다.
알고리즘\목표변수 | 이산형 목표변수 | 연속형 목표변수
CHAID(다지분할) | 카이제곱 통계량 | ANOVA F-통계량
CART(이진분할) | 지니지수 | 분산감소량
C4.5 | 엔트로피 지수 | x