[기계학습] 7. Decision Tree

1. Decision Tree and Impurity

1. Decision Tree (DT)

1) Decision Tree

의사결정트리는 데이터 분류를 나무의 모양에 빗대어 데이터의 규칙을 찾는 방법이다. 계층와 분기를 가지며, IF-THEN 규칙에 기반하여 분류한다. IF에서는 분기, THEN는 Label을 반드시 가진다.

2) Characteristics of DT

의사결정트리는 다음과 같은 특징을 가진다. (2,3,4,7은 함께 다니는 특징이다! 한번 생각해보자)

1. Recursive partitioning : 재귀적인 분할
2. Explicit rule extraction : 규칙이 명확하다
3. Interpretability : 모델 해석에 설명력이 있다
4. Axis-orthogonal partitioning : 직교의 파티셔닝, 덕분에 위아래의 여러 특징이 나타남
5. Greedy method : 각각의 시점에서 최적의 선택을 한다
6. Robust to nominal, variables outliers, missing values : 세가지에 영향을 적게 받는다
7. Variable selection : 변수 선택이 가능

3) Terminologies of DT

분기를 하는 root를 포함한 모든 node들은 변수를 의미한다. 예외로 leaf node들은 class label를 나타낸다. 참고로 모든 노드들은 노드안의 분포에 따라 하나의 클래스로 결정된다. 노드 안에 네모 3개와 동그라미 2개가 있다면, 이 노드는 네모의 클래스를 가진다.

위의 결정트리 예시를 보자. 트리를 통해 옆의 직교 파티셔닝을 하는 표를 볼 수 있다. 변수의 개수에 따른 차원에서, 변수 축에 직교하는 선을 그어 공간을 분리하는 방식으로 분류한다. 그리고 여기서도 마지막 자식 노드가 label임을 볼 수 있다.

4) Decision Rule of DT

이제 결정트리를 만들어보자.
결정트리를 만들기 위해서 우리는 두가지만 알면 된다.

1. 어떤 변수를 가지고 분기할지
2. 그 변수의 어떤 변수 값에서 분기할지

사람이 임의로 모델에 적용하면 된다! 그렇다면 그 기준은 어떻게 정해야 할까?
바로 Impurity drop, 즉 불순도를 떨어트려 본다. 불순도는 해당 노드에 얼마나 데이터들이 섞여있는가를 의미한다.

5) Impurity Measurements

불순도를 측정하는 방법은 크게 위의 4가지 방식이 있으며, 그 중 Entropy와 Gini index를 주로 사용한다. 위의 j는 클래스별 인덱스를 의미한다.

위는 3가지 노드에 속하는 데이터들의 클래스를 의미한다. 첫번째 경우는 w1의 확률이 1, w2의 확률이 0으로 pure한 상태이다. 세번째 경우는 w1의 확률이 1/2, w2의 확률이 1/2으로 가장 Impurity가 높은 상태이다.

Entropy와 Gini Index를 계산해보면, 둘 다 pure할수록 0에 가까우며 불순도가 높아질수록 Entropy는 1에, Gini Index는 0.5에 가까운 것을 볼 수 있다. 아래 표를 통해서도 불순도가 높아질수록 높은 값을 가지는 것을 볼 수 있다.

Entropy를 토대로 Impurity drop을 진행해보자. 우리는 분기가 진행될 수록 불순도가 감소하기를 기대한다. 따라서 분기를 하고 각각의 자식노드에 대한 불순도를 측정하여 부모노드와의 차이를 구하는 방식으로 분기가 적절한지 알아볼 수 있다. 이때 차이값을 Information gain라고 부르며, Information gain이 클 수록 많이 불순도가 감소하였음을 의미하므로 큰 값을 가진 분기를 선택한다. 두 자식 불순도의 합이 부모의 불순도보다 클 수 있기 때문에 각각의 자식 불순도에 가중치를 부여한다.

2. Characteristics of Decision Tree

2. Decision Tree (DT)

1) Full Tree (Full Grown Tree)

이전 시간에 보았듯이 복잡도가 올라가면 Overfit의 확률이 높아지고, 내려가면 Underfit이 될 수 있다. 그리고 결정트리는 복잡도를 조절할 수 있는 특징이 있다. 데이터가 겹쳐있지 않다고 가정할 때, 학습 데이터의 정확도를 조절할 수 있다. 더 이상 불순도를 drop 할 수 없을 때 까지 끝까지 분기해 모든 노드의 불순도가 0인 상태를 풀 트리(Full Tree)라고 하며, 이때 OverFit이 발생한다. 반대로 Max Depth를 설정해 분기를 제한하면 강제로 UnderFit하게 만들 수 있다. 1번의 분기만 이루어진 결정트리는 스텀프 트리(Stump Tree) 라고 한다.

2) Greedy Method

현재 시점에서 최선의 선택을 하는 것을 그리디 라고 한다. 간단하고 쉽지만, 동시에 지역 최적화(local optimal)이면서 전체에서 최적(global optimal)이 아닐 수 있다는 단점이 있다. 아래 그림에서도 첫번째 이미지의 첫번째 분기에서도 최적화 된 값을 따랐지만, 두번째 그림을 통해 결국 지역 최적화였다는 점을 알 수 있다.

3) Gini Index 와 Entropy

두 가지 방식의 불순도는 비슷한 경향을 가진다. 하지만 아래 예시와 같이 항상 같은 경향은 보이지 않을 수 있다.

4) When to Stop?

OverFitting과 UnderFitting은 어떻게 조절할까?

첫번째로는 Data partitioning이다. leaves의 수가 많아질 수록 Complextity도 커지므로, 이전에 보았던 Complexity와 Error 그래프와 위의 그래프는 같은 그래프이다. 위에서 가장 적절하다고 판단된 점을 기준으로 그 아래는 UnderFit, 위는 OverFit한 모델이 되므로, 해당 지점을 찾는다.

두번째로는 Max depth, Max leaf nodes, Min data for split의 외부 설정으로 Overfitting을 방지할 수 있다. Parameter는 모델 내부에서 Model을 조절한다. 반면에 모델 외부에서 Parameter에 영향을 주는 것을 Hyper Parameter라고 한다. 즉 우리가 설정할 수 있는 값이다. Ridge Linear Regression을 예시로 보면, Parameter에는 결정식의 계수인 β가 있으며, Hyper Parameter에는 α와 같은 Control parameter가 있다.

Decision Tree에서는 분기의 갯수, Depth가 커질 수록 OverFit에 가까워지고 작아질 수록 UnderFit에 가까워진다. leaf nodes의 수는 Complexity에 영향을 주고 결국 leaves의 수가 많아지면 OverFit, 적어지면 UnderFit에 가까워진다. 참고로 leaf nodes의 수는 모델의 설명력을 나타내는 Rule의 수를 의미한다. 마지막으로 data for split, 즉 노드안의 data의 개수를 의미한다. 예를 들어 노드 안의 데이터가 5개 이하면 split하지 않는다. 결국 이 세 가지의 제약이 하고자 하는 것은 "너무 많이 분기하지 마라" 인 것이다. 이 세가지를 하나만 쓸 수 도 있고, 여러 개를 동시에 사용할 수도 있다.

세번째로는 정말 중요한 Regularization이다. tree의 size를 통한 Complexity, 모든 노드들의 불순도의 합을 통한 error를 의미한다. 따라서 아래식을 Cost로 하여 최소화 하는 것을 목적으로 한다.

5) Pruning

사실 거의 모든 Decision Tree의 패키지에는 Pruning(가지치기) 기능이 default로 내장되어 있어 적당한 트리를 생성할 수 있다. Pruning는 Full Tree를 만들고 나서, 의미없는 가지들을 잘라낸다. validation data가 필요하지 않지만 계산량은 늘어나는 특징이 있다.

Pruning Algorithm

알고리즘을 보기 전에 의미없는 노드는 무엇일까? 일단 우리는 계속해서 트리의 Cost를 판단할 것이다. 바로 아래와 같이! 식을 보면 굉장히 익숙한데 이는 바로 위에서 본 Regularization이다. 가지치기 이후에도 Cost가 증가하지 않으면, 가지치기를 당한 노드들은 의미가 없는 노드가 된다. 이러한 방식을 Cost Complexity Prunning이라고 한다.

알고리즘은 다음과 같다.

1. Full Tree를 만든다
2. Pruning
   2-1. Sub Tree를 찾는다
   2-2. Cost(Full Tree)와 Cost(Sub Tree)를 계산한다
   2-3. 만약 Cost(Full Tree) > Cost(Sub Tree)이면 Sub Tree를 선택한다
   2-4. 다시 2번을 재귀적으로 반복한다

6) Robust to Nominal Variables, Outliers, Missing Values

Decision Tree의 특징 중 하나는 위의 세가지 문제가 있어도 활용할 수 있다는 점이다. 대부분의 모델에서는 Nominal Variables가 있으면 One Hot Encoding을 해주거나, Outliers가 있으면 sensitive 해지거나, Missing Values가 있으면 작동하지 않으므로 반드시 채워넣어 줘야 한다. 하지만 Decision Tree의 상황을 보자.

Nominal Variables은 그냥 돌리면 된다. 오히려 이전에는 Nominal한 데이터를 사용했다. Outliers는 더 다수결로 판단하므로 class Rule에 크게 영향을 주지 않는다. k-NN의 경우에는 새로운 영역을 만들 수 도 있다는 점을 생각해보자. Missing Values가 있으면 그냥 없는 data는 빼고 분기를 결정한다. (많은 Missing은 당연히 오차가 클 수 밖에 없다)

7) Variable selection

Decision Tree의 특징 중 마지막은 변수 선택이다. 아래의 표와 그래프를 보자. 의사 결정 생성과정을 통해서 많은 변수중에서 어떤 독립변수가 상대적으로 종속변수에 영향을 더 주는지, 영향을 더 주는지 파악할 수 있다. 고혈압에 대한 Decision Tree를 만드는 과정에서 Age와 Heart Rate를 가장 중요한 변수로 선택되었다. 따라서 우리는 이 두 변수가 고혈압에 영향을 많이 주는 요소라고 판단할 수 있다는 것이다. 선택된 변수들을 통해 다른 알고리즘을 사용하여 새로운 예측 모델을 생성할 수도 있다!

2. Nonlinear Regression

그러면 축에 직교로 파티셔닝 하지 않으면 오차를 더 줄일 수 있지 않을까?
직교의 파티셔닝을 통해 우리는 강력한 설명력을 보장할 수 있었다. 하지만 NonLinear하게 나눈다면 성능은 좋아질 수 있지만 설명력을 잃어버린다. Decision Tree의 핵심은 설명력이며, 설명이 필요하지 않다면 결정트리를 사용할 의미가 없다. 성능이 중요하면 다른 알고리즘을 사용하자. 하지만 유의해야 하는 부분도 있는데, 바로 모든 Rule들이 x와 y의 인과관계를 정확히 반영하고 있다는 확신을 가져서는 안된다. 결과론적인 Rule들이 생성되었을 수도 있기 때문이다. 언제나 조심하고 의심하고 확인해보자.

1) Decision Tree Regression

NonLinear 파티셔닝은 어렵지만, NonLinear Regression은 당연히 가능하다. Classification의 분기 규칙은 Impurity였지만, Regression은 error의 제곱의 합과 분산으로 분기 규칙을 가진다. 사실상 불순도와 분산은 같은 의미를 가지는 데, 분산이 높다는 것은 여러 값이 분포해있으므로 결국 불순도도 높다. 분산이 크면 분기가 되므로, 결국 비슷한 y값끼리 node를 형성할 것이다.

2) Decision Tree Algorithms

주로 CART(Classsification And Regression Tree)기반의 알고리즘을 사용한다. 하지만 다양한 tree 알고리즘을 사용할 수 있다. 설정을 통해서 내부적인 Split criteria도 바꿀 수 있다.

3. Summary

Classification algorithm based on IF-THEN rule
• Easy to use, understand
• Produce rules that are easy to interpret & implement (white-box model, 원인을 알아 사후대응이 가능)
• Variable selection & reduction is automatic
• Do not require the assumptions of statistical models
• Can work without extensive handling of missing data (can learn data with N/A)
• Pruning

Cons
• Greedy + Axis-orthogonal = Low accuracy