Decision Tree와 CART

도입

많은 Tree기반 분석 방법론의 기본 토대가 되는 의사결정나무(Decision Tree)와 대표적인 의사결정나무의 일종인 CART(Classification And Regression Tree)에 대해 정리해보고자 합니다.

출처 : https://injo.tistory.com/15

이미지를 보면 간단하게 이해할 수 있습니다. 위 이미지의 데이터는 대표적인 분류 문제인 Titanic입니다. Decision Tree는 말그대로 변수들을 거치면서 단순하게 분류를 해나가는 것으로 볼 수 있습니다.

- Is passenger Male? 은 루트노드

- Age <18?, 3rd Class? Embarked from Southhampton? 등은 규칙노드

- Died or Survived는 리프 노드에 해당합니다.

---

CART

CART는 Decision Tree를 생성하는 대표적인 알고리즘입니다. 실제로 Tree기반의 머신러닝 기법들(Random Forest, XGBoost, LightGBM, GBDT 등)은 CART기반으로 구현되어 있습니다.

하지만 단순 CART모델은 bias-variance Trade off에서 high variance의 성질을 가지고 있다는 것이 단점입니다. 달리 말하면 Overfitting하기 너무 쉽다는 문제를 가지고 있습니다.

---

Tree의 척도

CART는 Classification and Regression 이라는 이름에 걸맞게 분류문제와 회귀문제 모두에 쓰일 수 있습니다. CART의 목적함수는 각 분할에서 정보이득(IG)을 최대화하는 것입니다.

 

 

Regression

Regression 문제에서는 선형회귀 분석의 척도와 같이 RSS(Residual Sum of Square)를 사용합니다.

출처 : www.RiskPrep.com

쉽게 설명하면, 예측값과 실제값의 차를 제곱한것입니다.

회귀분석을 공부하셨던 분들이라면 쉽게 이해하실 수 있을 것 같습니다.

 

Classification

분류 척도에는 대표적으로 두가지가 사용됩니다. 지니계수와 Cross-entropy입니다.

 

- 지니계수(Gini index)

지니 계수는 일종의 불순도 지표입니다. 달리말하면, 특정 Class에 속하는 관측치의 비율을 제외한 값입니다.

간단한계산 과정은 다음과 같습니다.

 

위 이미지에서 좌측은

와 같이 계산되고, 우측은

와 같이 계산됩니다.

이때 지니계수는 0~0.5의 값을 가지게 도는데 작을수록 좋다고(=불순도가 낮다=분산이 작다 = 정보이득이 많다)고 할 수 있습니다.
처음에 각 Box의 지니계수를 구한다음 가중치를 곱해주는것을 잘 이해하지 못했는데 아래 사이트를 참고하면서 이해하게 되었습니다. 표현을 빌리자면, Weighted Gini Impurity of the split based on performance in class 라고합니다.

towardsdatascience.com/what-is-gini-impurity-how-is-it-used-to-construct-decision-trees-75d01ed78812

What is Gini Impurity? How is it used to construct decision trees?

 

- 엔트로피 불순도

 

과정은 지니 불순도와 비슷합니다.

계산식은 위의 수식과 같고 위 이미지에 따른 계산방법은 아래의 수식과 같습니다.

 

재귀적 분기(Recursive Binary Splitting)

재귀적 분기는 특정 영역인 하나의 노드 내에서 하나의 변수 값을 기준으로 분기하여 새로 생성된 자식 노드들의 동질성이 최대화 되도록 분기점을 선택하는 과정입니다. 즉, 불순도가 작은 지점을 찾는 과정입니다

 

범주형 변수에서는 Gini index

수치형 변수에서는 Variance

를 이용합니다.

 

트리를 만들기 위한 알고리즘은 다음이 반복됩니다.

1. 데이터 Ordering

2. 데이터 2등분(binary)

3. 엔트로피 계산

4. 1~2번재 데이터 vs 나머지로 이등분

5. 엔트로피 계산

6. ....

7. 분기

8.. 데이터 ordering

9. 반복

 

 

가지치기(Pruning)

가지치기는 DecisionTree의 고질적 문제인 Overfitting을 해결할 수 있는 수단입니다. 가지를 잘라서 버리는 다는 개념 보다는 합치는 것이라고 이해해야합니다.

출처 : https://niceguy1575.tistory.com/

다음과 같이 CostFunction을 이용하여 Pruning과정을 거칩니다. 여기서 alpha는 hyper parameter에 해당합니다.

 

Decision Tree의 장단점

 

장점

- 모델이 explainable합니다. (굉장히 단순합니다)

- 시각화가 쉽고 비전문가도 이해하기 쉽습니다

- 연속형과 범주형 모두 처리 가능합니다.

 

단점

- 데이터가 수직/수평적으로 구분되지 못할때 분류율이 떨어지고 트리가 복잡해집니다.

- 두 변수가 비슷한 정보력을 가지고 있ㅇ르때 약간의 차이에 의해 다른 변수가 선택되면(multicolinearity 문제) 트리 구성이 크게 달질 수 있습니다.

 

After CART

도입에 CART기반의 Tree based ML이 굉장히 잘 사용되고 있다고 하였습니다.

기본적으로는 Boostrap부터 파생되어 Bagging, Random Forest, Boosting등의 방법으로 발전해나가고 있습니다.  

다음에는 이와 관련된 내용을 정리해볼까 합니다!

 

참고

niceguy1575.tistory.com/entry/%EB%8D%B0%EC%9D%B4%ED%84%B0-%EB%A7%88%EC%9D%B4%EB%8B%9D-9-Decision-TREE-%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95%EB%82%98%EB%AC%B4%EC%99%80-%EB%82%98%EB%AC%B4%EC%9D%98-%ED%9B%84%EC%98%88%EB%93%A4Bagging-Random-forest-Boosting

[데이터 마이닝-9] Decision TREE (의사결정나무)와 나무의 후예들(Bagging, Random forest, Boosting)