머신 러닝 정리 4- Decision Tree

현실 세계에서는 rule base 가 완벽하게 동작하기 어렵다. 

 

• 모든 결정이 consistent 한 것이 아니다. (오늘은 비가 오지만 나가고 싶을 수 있다.)
• error 가 관측치에 있기도 하다. 
• 모든 정보를 다 보기도 어렵다.  (놓친 feature)

 

그렇다면 우선, error 가 있는 경우에 통계적 기법을 가미해서 learning 을 할 수 있는 방법은 무엇이 있을까? 

 

Decision Tree 를 통해 가능하다.

사전 version space를 통해 만들어진 결과물로 decision tree 를 만들 수 있다. 

 

http://archive.ics.uci.edu/ml/datasets/Credit+Approval 

UCI Machine Learning Repository: Credit Approval Data Set

에서 credit card approval 데이터 셋을 얻을 수 있다. 

 

• 690 Instances total 
• 307 positive instance 

credit card 신청인 총 690 인 중, 307 명만 허가된 데이터 셋이다. 

 

A1 ~ A15 features 

 

A1: b, a.
A2: continuous.
A3: continuous.
A4: u, y, l, t.
A5: g, p, gg.
A6: c, d, cc, i, j, k, m, r, q, w, x, e, aa, ff.
A7: v, h, bb, j, n, z, dd, ff, o.
A8: continuous.
A9: t, f.
A10: t, f.
A11: continuous.
A12: t, f.
A13: g, p, s.
A14: continuous.
A15: continuous.
A16: +,- (class attribute)

 

A1 feature 

• 98 positive when a 
• 112 negative when a 
• 206 positive when b 
• 262 negative when b 
• 3 positive when ?
• 9 negative when ? 

...

 

A9 feature

• 284 positive when t 
• 77 negative when t 
• 23 positive when f 
• 306 negative when f 

...

 

 

A1 으로만 판결을 내리면 아래와 같다. 

A1 의 특성만으로 판결을 내리는 것은 무리가 있다.

A9 특성을 사용하면 A1 보다는 더 좋은 결과를 내나, 여전히 많이 틀리긴 한다. 

 

이제 본격적으로 Decision Tree 를 살펴보자. 

드디어 Entropy에 대해 정리할 기회가 왔다. 

 

 

Entropy 

어떤 특성을 더 잘 확인할 수 있을지 알려주는 지표

머신 러닝에서 중요한 목표중 하나는 바로 uncertainty 를 줄이는 것이다. 

(A1 보다 A9 의 uncertainty 가 적은건 자명해보인다.)

 

이러한 uncertainty 는 어떻게 정량화 할 수 있을까? 

entropy 가 높을 수록 uncertainty도 높다. 

 

엔트로피에 대한 정리 

https://bskyvision.com/389

[정보이론] 정보량과 엔트로피의 의미

https://memesoo99.tistory.com/38

Information Theory 이해하기 - 정보량과 Entropy

 

3줄 정리 

1. 정보량: 놀람의 정도 수치화, 단일 사건에 대한 정보량 

$$I(x_j) = -\log_a p(x_j)$$

확률이 1에 가까워 질 수록 정보량은 0, 0에 가까워 질 수록 무한대로 수렴 즉 확률이 낮을 수록 놀랍다. (놀랍다 = 정보량이 많다.)

 

2. 엔트로피는 어떤 사건에 대한 확률 분포의 정보량 

$$\sum^N_{i=1} -P(x_i)\log P(x_i)$$

각 사건의 정보량 $I(a)$ 에해당 정보가 등장할 확률$P(a)$를 곱해준다(사건을 표현하기 위해 요구되는 평균 자원)

 

 

Entropy H 

Features 은 random variables 이다.

$H(X) = - \sum_x P(X=x) \log_a P(X=x)$

 

 

Joint Entropy 

결합 entropy 는 의미도 이름 그 자체라 어렵지 않다. 아래 링크 참고

 

https://bskyvision.com/604

[정보이론] 결합(joint) 엔트로피와 조건부(conditional) 엔트로피

 

Conditional Entropy 

 

사전 지식 

 

확률 질량 함수 

 

이산 확률 변수의 확률 분포를 나타내는 함수 

 

확률 밀도 함수 

 

연속 확률 변수의 확률 분포를 나타내는 함수 

 

결합 확률 질량 함수 

 

두 이산 확률 변수 X, Y 가 각각 아래와 같이 존재할 때, X 가 $x_i$ 의 값을 갖고 Y 가 $y_j$의 값을 가질 확률은 다음과 같이 나타낼 수 있다. 

$P( X = x_i, Y = y_j) = p_{i,j} (i = 1,2,3,4 ...,m, j = 1,2,3,4 ..., n)$

$p_{i,j}$ 를 이산확률변수 X,Y 의 결합 확률 질량 함수라 한다. X, Y 각각 특정한 값을 가질 때 확률을 뜻한다. 

 

아래의 예시를 살펴보자 

 

• 조건: 3개의 빨간 공, 2개의 노란 공, 4개의 초록 공이 들어있는 주머니
• 행위: 임의로 2개의 공을 꺼낸다. 
• 뽑은 빨간 공의 개수: 확률변수 X, 뽑은 노란 공의 개수: 확률변수 Y
• X,Y 로 이루어진 순서쌍: (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0) 총 6개
• 분모는 9개중 2개를 뽑는 경우 즉, 9개 중 2개를 뽑는 가능성이 전체의 경우 

1) 빨간 공 0개, 노란 공 0개, (초록 공 2개)를 뽑는 경우의 확률:

 

2) 빨간 공 0개, 노란 공 1개, (초록 공 1개)를 뽑는 경우의 확률: 

 

 

3) 빨간 공 0개, 노란 공 2개, (초록 공 0개)를 뽑는 경우의 확률:

 

 

4) 빨간 공 1개, 노란 공 0개, (초록 공 1개)를 뽑는 경우의 확률:

 

 

5) 빨간 공 1개, 노란 공 1개, (초록 공 0개)를 뽑는 경우의 확률:

 

 

6) 빨간 공 2개, 노란 공 0개, (초록 공 0개)를 뽑는 경우의 확률:

 

결합확률분포표

모든 확률을 더하면 당연히 1이다.

 

 

 

결합 확률 밀도 함수

 

두 개의 연속확률변수 X와 Y가 존재할 때, X가 a이상 b이하이면서 Y가 c이상 d이하일 확률은 다음과 같이 나타낸다.

여기서 $f(x, y)$를 연속확률변수 X, Y의 결합확률밀도함수라고 부른다.

 

임의로 선택한 30세 성인의 키를 연속확률변수 X라고 하면 키가 170-175cm일 확률

 

$f(x)$는 연속확률변수 X의 확률밀도함수

 

30세 성인의 키가 170cm이상 175cm이하이면서 동시에 몸무게가 80kg 이상 85kg이하일 확률은 결합확률밀도함수를 사용

 

키와 몸무게는 완전히 독립적이라고 볼 수 없기 때문이다. 두 확률변수가 만약에 서로 통계적으로 독립이라면 아래와 같이 단순히 두 확률을 곱하는 것으로 확률을 구할 수 있다.

 

 

주변확률질량함수

 

질량이라는 단어로 이산확률변수와 관련된 것임을 알 수 있다. 

 

두 개 확률변수의 결합확률질량함수가 주어진 상황에서 오직 한가지 확률변수의 확률함수만을 알고 싶은 경우가 있다. 이산확률변수 X, Y의 결합확률질량함수가 $p(x, y)$라고 하자. 이 결합확률질량함수로부터 알고 싶은 것이 오직 확률변수 X의 확률함수라면 Y에 대한 정보는 필요없다. 

 

이산확률변수 X, Y의 결합확률질량함수가 주어진 상황에서 X와 Y의 주변확률질량함수는 각각 다음과 같이 구한다.

 

$p_X(x) = \sum_{all y} p(x, y)$

 

$p_Y(y) = \sum_{all x}p(x,y)$

 

즉 각 확률 변수가 특정한 값을 가질 때 다른 확률 변수가 가질 수 있는 모든 값들의 확률을 더한 것이다. 

 

주변확률밀도함수

 

밀도라는 단어로 연속확률변수와 관련된 것임을 알 수 있다.

 

 결합확률밀도함수도 마찬가지로 주어진 상황에서 오직 한가지 확률변수의 확률함수만을 알고 싶은 경우에 사용한다. 

 

$f_X(x) = \int^{\infty}_{- \infty} f(x,y) dy$

 

$f_Y(y) = \int^{\infty}_{- \infty} f(x,y) dx$

 

예제를 통해 살펴보자. 아래와 같이 이산 확률 변수를 갖는 결합 확률 분포표가 있다고 하자. 

주변확률 질량함수는 어떻게 구할까? 간단하게 X = 0 일 때, 가능한 모든 Y 의 값을 더해주면 X = 0 일때의 주변질량함수의 값이다. 

 

정리하면 아래와 같다. 

 

길고 긴 사전 배경을 살펴보았다. 이제 조건부 엔트로피에 대해 살펴보자. 

 

표현식은 아래와 같다. 

 

$H(Y | X) = \sum_{x} p_{X}(x)H(Y|X = x) = \sum_{x}p_{X}(x)\sum_{y}p_{Y|X}(y|x)\log_2 \frac{1}{p_{Y|X}(y|x)}$

 

X가 주어졌을 때 Y의 엔트로피 $H(Y|X)$

 

식만 주어졌을 때는 도통 감이 안온다. 아래를 통해 살펴보자. 

특정 상황에 대한 결합 분포표를 통해 주변 확률질량함수를 구했다. 

 

 

$H(Y|X)$

$H(X|Y)$

H(Y|X)와 H(X|Y)는 일반적으로 다른 값을 갖는다. 

 

위와 같이 수식으로 보면 이해가 좀 어렵다. 아래의 예시를 살펴보자. 

(아래 예시는 https://wooono.tistory.com/104 블로그의 내용을 발췌했음을 밝힘)

 

 

Decision Tree 를 구성 단계

decision tree 를 구성하는 방식은 다양하다. 그러하니 여기서는 가장 간단한 ID3 algorithm 을 다룬다. 

1. Root 노드의 불순도 계산
2. 나머지 속성에 대해 분할 후 자식노드의 불순도 계산
3. 각 속성에 대한 Information Gain 계산 후 Information Gain(Root노드와 자식노드의 불순도 차이)이 최대가 되는 분기조건을 찾아 분기
4. 모든 leaf 노드의 불순도가 0이 될때까지 2,3을 반복 수행한다.

※ Information Gain 이란? 

분기 이전의 불순도와 분기 이후의 불순도의 차이를 정보 획득이라 한다. 

불순도가 1인 상태에서 0.7인 상태로 바뀌었다면 정보 획득(information gain)은 0.3이다. 아래의 예시를 통해 경험적으로 개념을 습득해보자. 

※ 불순도란? 

분기기준을 선택하기 위해서는 불순도(impurity)라는 개념을 사용. 복잡성을 의미하며, 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻한다.

Entropy, Gini 등 여러 함수가 해당 될 수 있다. (Entropy Gini 차이: Gini 가 속도가 더 빠르나, Entropy 가 비교적 정확하게 분류한다고 알려져있다.)

1. Root 노드의 불순도 계산

경기의 참가 여부로 먼저 Root 노드를 설정한다. 

 

2. 나머지 속성에 대해 분할 후 자식노드의 불순도 계산

• 날씨

  

• 온도

  

• 습도

  

•  바람

  

 

3. 각 속성에 대한 Information Gain 계산 후 Information Gain(Root노드와 자식노드의 불순도 차이)이 최대가 되는 분기조건을 찾아 분기

4. 모든 leaf 노드의 불순도가 0이 될때까지 2,3을 반복 수행한다.

예를 들어, "맑음"으로 분류된 노드는 "날씨 = 맑음" 인 데이터만 가지고 와서 다시 분할 전 엔트로피를 계산한다.

 

최종결과

일반화 

깊어질 수록 train,test 셋에 대한 accuracy

위 구성방법을 사용하여 트리를 형성하게 되면, leaf 노드가 순도 100%의 한가지 범주만을 가지게 되는 Full tree(최대 트리)를 형성하게 된다. 

하지만 이러한 최대 트리는 새로운 데이터에 적용할 때 과적합 문제(Overfitting)가 발생하여 일반화 성능이 떨어지게 된다. 

따라서 형성된 결정트리에 대해 가지치기(Pruning)를 수행하여 일반화 성능을 높힌다.

 

가지치기 (pruning)

• 가지치기란 최대트리로 형성된 결정트리의 특정 노드 밑의 하부 트리를 제거하여 일반화 성능을 높히는 것을 의미한다. (오버피팅을 막기위해 사용된다.) 
• 더 많은 가지가 생기지 않도록 최대 깊이, leaf 노드의 최대 개수, 한 노드가 분할하기 위한 최소 데이터 수 등의 제한이 가능하다.

가지치기의 비용함수

• 의사결정나무는 아래 비용함수를 최소로 하는 분기를 찾아내도록 학습된다. 
• $CC(T) = Err(T) + \alpha × L(T)$  

 

• $CC(T)$
  • 의사결정나무의 비용 복잡도
  • 오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값
• $ERR(T)$
  • 검증데이터에 대한 오분류율
• $L(T)$
  • terminal node의 수
  • 구조의 복잡도
• $\alpha$
  • ERR(T)와 L(T)를 결합하는 가중치
  • 사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀

간단한 수식이다. 

 

Decision Tree의 장단점

장점

• 데이터의 전처리 (정규화, 결측치, 이상치 등) 를 하지 않아도 된다.
• 수치형과 범주형 변수를 한꺼번에 다룰 수 있다.

한계

• 만약 샘플의 사이즈가 크면 효율성 및 가독성이 떨어진다.
• 과적합으로 알고리즘 성능이 떨어질 수 있다.
  • 이를 극복하기 위해서 트리의 크기를 사전에 제한하는 튜닝이 필요하다.
• 한 번에 하나의 변수만을 고려하므로 변수간 상호작용을 파악하기가 어렵다.
• 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다.
  • 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다.
• 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다.
  • 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.
• 이같은 문제를 극복하기 위해 등장한 모델이 바로 랜덤포레스트이다.
  • 같은 데이터에 대해 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법이다.

 

단순하게 살펴보아도 변수간의 상관관계는 전혀 반영되지 않으며, Greedy 알고리즘 특성상 최적의 해가 아니라는 것을 알 수 있다. 또한 과적합이 일어나기도 쉽다. 그러나 랜덤포레스트의 기반이 됨과 동시에 수학적으로 살펴볼 구석들이 있었다는 점에서 꼭 살펴보고 넘어가야 한다.