What is Decision Trees?

Decision trees(결정 트리)의 기본적인 형태이다.

• Internal nodes(Decision nodes) 들은 속성을 test한다
• Branch, 기준에 따라 가지가 나뉘어 진다
• Leaf nodes 결과값을 의미한다. (predictions)
• CART(Classification and Regression trees)라고도 불린다

 

<Example>

왼쪽 결정 트리 오른쪽 결정 경계

DT(Decision Trees) 고려할 점

• 모든 객체는 속성-값 pair로 구성
• Target function은 이산변수을 다룸
• 명제 논리 필요 (Ex 키위는 지름이 10cm보다 작다)
• 이상치에 유연하게 대응 가능
• 일반화가 가능하도록 조정
• Leaf node에 가능한 같은 Label에  해당하는 값들을 분류

---

DT를 모든 데이터에 대해 잘게 분류할 수 있지만 고려할점에 써있는것과 마찬가지로 일반화가 잘 이뤄지지 않기 때문에 유의해야한다. 효율적인 DT 구성 방식은 무엇이 있을까?

 

우선 DT는 적어도 NP-complete문제이다. NP(Non Polynomial), 다항시간에 풀수 없는 문제라는 뜻으로 컴퓨터를 이용한다고 해도 풀 수 없는 문제라는 뜻이다. 알수 없는 수많은 시간이 걸려야 풀 수 있다는 뜻인데, 남은 선택은 최적의 방법을 근사하는 방법을 찾는 것이다. DT는 최적의 결과를 도출하기 위해 greedy 기법을 사용한다. greedy 기법은 어느 기준을 두고 가장 좋은 방향으로 선택하는 것이다. DT에서는 좋은 분할(split)을 기준으로 진행한다.

 

정확률(accuracy)는 DT에서 좋은 지표로 사용되지 못하는데 아래 예시를 살펴보자.

위의 노드 하나로만 분류한 정확률과 아래 2개 노드를 확장시켜 측정한 정확률이 일치한다. 이는 효율적인 DT를 선택함에 부정확성을 불러온다.

 

따라서 DT의 좋은 분할을 측정하기 위해 정보이론(information theory)이 적용된다. intuition은 각 leaf node의 확률 분포(probability distributions)를 정량화하여 무질서도(정보량, uncertainty)를 측정한다.

---

Quantifying Uncertainty (무질서도 정량화)

• Entropy는 화학에서 무질서도를 의미하는데, 컴퓨터 공학의 정보이론 관점에서는 엔트로피가 높을수록 정보량이 많다고 정의한다.

예를 들어 참, 거짓으로 나뉜 명제가 있다고 할 때 참으로만 이루어진 집합은 어떤 요소를 뽑아도 참이 자명하기 때문에 정보가 없다. 하지만 참, 거짓이 반반 섞인 명제 집합인 경우 참, 거짓이 확실하지 않으므로 내재된 정보량이 많다고 한다.

• 정보량 측정 수식 \(\textbf{Entropy} H(x) = -\sum_{i=1}^{n}{P(x=i)log_2{P(x=i)}}\)
• 단위 Unit => bits

 

Entropy Graph

High Entropy 특징

• Uniform distribution
• Flat Histogram
• Sample's value is less predictable (sample target이 불분명)

Low Entropy 특징

• Distribution with many peaks and valleys
• Many lows and highs histogram
• Sample's value is more predictable (sample target이 예측하기 쉬움)

왼쪽 High Entropy 오른쪽 Low Entropy

 

Conditional Entropy Property

 

• \(H(x)\) is always positive
• Chain Rule 성립 \(H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X)\)
• If X and Y independent, then X doesn't tell anything about Y: \(H(Y|X) = H(Y)\)

IG(Information Gain) = MI(Mutual Information)

비가 올 확률에 대한 명제와 내가 오늘 기분이 좋을 명제는 서로 독립이다. 이때 내가 기분이 좋다는 정보가 비가 올지 안올지에 대한 예측에 도움을 주진 않는다.

• If X tells everything about Y : \(H(Y|X) = 0\)

X가 Y에 대해 모두 설명할수 있다면 예측 확률이 1이기 때문에 정보량이 없다는 뜻이고 entropy값이 0이된다. 수식에 1을 대입해도 0이 나오는 것을 확인 할 수 있다.

• By knowing X, we can only decrease uncertainty about Y : \(H(Y|X) \leq H(Y)\)

X를 통해 Y의 target을 얻는데 정보를 준다면 정보량이 적어졌다는 뜻으로 위의 대소관계가 성립한다. 수식을 통해서도 위의 부등식이 성립함을 알 수 있다.

 

Information Gain (Mutual information)

• information gain in 𝑌 due to 𝑋, or the mutual information of 𝑌 and 𝑋 : \(IG(Y|X) = H(Y) - H(Y|X) \)
• If X is completely uninformative about Y : \(IG(Y|X) = 0\)
• If X is completely informative about Y : \(IG(Y|X) = H(X)\)

DT 적용 : IG = entropy(parent) - [average entropy(children)]

다시 좋은 Decision Tree를 설정하는 관점으로 돌아와보자. 좋은 DT를 설정하는 정도를 측정하기 위한 척도로 entropy를 사용하고 IG까지 내용의 전개가 이어졌다.

정리해보면 DT가 데이터들을 제대로 분류하였다면 Leaf node들의 데이터 집단의 average entropy는 0에 근사한 값일 수록 좋을 것이다. 분류가 잘되어 같은 target끼리 모여 있으므로 entropy값이 적을 것이기 때문이다.

 

그리고 각 branch마다 부모노드의 데이터 집단 entropy와 자식노드들의 데이터 집단 average entropy의 차(IG)를 구한다면 값이 부모노드의 entropy보다 작아질수록 데이터가 분류되고 있음을 의미한다. 정보량을 잃는다는건 분류가 되고 있다고 생각하자!

 

Decision Tree Algorithm

Simple, Greedy, Recursive approach, builds up tree node by node

1. pick an attribute to split at a non-terminal node
2. split examples into groups based on attribute value
3. for each group:
   if no examples - return majority from parent
   else if all examples in same class - return class • else loop to step 1

 

What is Good Tree?

• Not small DT depth : 너무 낮으면 underfitting 우려가 있다. 물론 중요한 attribute만 골라 최소의 깊이를 쌓는 것은 중요하다.
• Not big DT depth : 너무 높으면 overfitting 우려가 있다. 컴퓨터 자원의 연산량이 증가하여 비효율적이며 애매한 attribute 3개를 이용한 것과 핵심 attribute 하나로 분류한 결과가 같다면 후자를 선택하는게 바람직하다.
• “Occam's Razor" : find the simplest hypothesis that fits the observations -> 가장 작고 효율적인 DT를 찾는게 목적

Decision Trees Regression

DT로 회귀 문제를 풀 수 있을까? 

Pruning(가지치기)

모든 데이터와 오차제곱합(RSS)이 최소가 되는 특성-값을 기준으로 가지치기하여 구역을 나누어 회귀 문제를 해결

https://modern-manual.tistory.com/29

• Years-4.5가 RSS가 최소가 되는 기준
• 그다음 나뉘어진 영역을 기준으로 각 영역의 평균값과 다음 특성-값과의 RSS가 최소가 되는 기준을 찾는다
• 모든 특성만큼 반복 후 가지치기에 따른 결과 예측

Algorithm

Top-Down 방식

1. 변수(특성) \(X_{1},X_{2}, ~ X_{j}, ~,X_{p}\) 들에 대해 해당되는 범위 내 값을 s라 할때 모든 데이터에 대해 오차제곱합(RSS)이 최소가 되는 (\(X_{j}\), cutpoint s)를 찾는다
2. (\(X_{j}\), cutpoint s)에 의해 나뉜 두 영역 \(R_{1}(j,s)=\left\{X | X_{j} <s \right\}, \; R_{2}(j,s)=\left\{X | X_{j} >s \right\}\)
3. 각 영역에 대해  \(\sum_{i:x_{i}\in R_{1}(j,s)}(y_{i}-\hat{y_{R_{1}}})^2+\sum_{i:x_{i}\in R_{2}(j,s)}(y_{i}-\hat{y_{R_2}})^2\)가 최소가 되도록 1번 방식을 반복한다.
4. 만약 가지치기가 끝난 경우 예측 후 해당 영역의 평균값을 예측값으로 한다

그렇다면 최적의 Depth, Node 수는 무엇일까?

모든 Subtree를 구한뒤 비교하는 것은 비효율적이다. => Cost complexity pruning 적용

• tuing parameter \(\alpha\)로 말단노드 개수(leaf node) \(|T|\)를 조정
• RSS + \(\alpha|T|\) 수식 이용하여 적당한 subtree 선택
  \(\sum_{m=1}^{|T|}\sum_{x_{i}\in R_{m}}(y_{i}-\hat{y_{R_{m}}})^2+\alpha|T|\)

Tree size에 따른 MSE 관계

 Decision Tree Miscelleny

• 너무 적은 데이터로 인해 적절한 DT를 찾지 못함
• Overfitting 문제
• Greedy algorithm은 global optimum이 아니다
• Continous attributes : split based on a threshoold
• Regression : choose split to minimize squared error with IG

---

 Comparison  to  k-NN

Pros of DT than k-NN

• Fast at test time
• Rubust to scale of inputs
• Easy to deal with missing values

Pros of k-NN than DT

•  Able to treat attributes in complex way
• Can incorporate interesting distance measures
• Better predict in practice