이번에는 decision tree에 대해서 알아볼 것이다. 대표적인 Machine Learning모델 중 하나인 것 같다.

Decision Tree Model

Decision Tree Model: 각 feature을 노드로 branch를 그 feature의 value로 하여 분류하는 기법, feature노드들로 tree생성

• 맨 위: Root node
• 다른 모든 노드: decision nodes
• 맨 아래: Leaf node

Learning Process

1. Root node에서 어떤 feature을 사용할 것인지
2. 그 후 각 방향에 어떤 node를 놓을 지 결정
3. 그 후에 맞는 위치에 data들을 옮김.

그럼 여기서 우리가 생각해봐야할 건, 노드들을 어떻게 나눌 것이냐 이다.

그걸 위해서 우리는 entropy에 대해서 살짝 알 필요가 있다.Entropy & Cross Entropy

또한, 어느정도로 노드를 나눌 것인가를 생각해보면,

• node가 하나의 클래스만 존재하면 그 노드는 이제 분할 중단
• 트리 최대 깊이 설정 후 넘지 않도록 한다.
• purity score 가 임계값 미만일 때
• 노드에 example 수가 임계값 미만일 때

이다.

Measuring Purity

Entropy & Cross Entropy

여기서 나온 것처럼 Entropy를 구하기 위한 식으로는

• $p_1=\frac{3}{6},p_0=1-p_1$
• $H(p_1)=-p_1log_2(p_1)-p_0log_2(p_0) = -p_1log_2p_1-(1-p_1)log_2(1-p_1)$

이다.

좀 더 직관적으로 설명해보자면,
entropy는 결국 정보의 불확실성을 나타내는 지표이며, 질문의 개수이다. 질문의 개수는 적을 수록 정보는 확실하다고 볼 수 있다. 고로 우리는 Entropy를 감소시키는 방향으로 decsion tree를 구성할 것이다.

Choosing a split information gain

그럼 위에서 말한 entropy의 감소란 무엇일까? 어떻게 하면 우리는 정보를 좀 더 확실하다 할 수 있는가.

정보를 얼마나 얻었는 지를 보면서 확인할 수 있다.

여기서 쓰일 수치 계산 법은 information gain이라는 식이다.

결국 entropy의 감소를 우리는 information gain과 같은 것이라고 볼 수 있는 것이다.

그럼 information gain을 어떻게 구할 수 있을 지 살펴보자.

먼저 이미지에서 고양이인 이미지를 분류한다고 했을 때,

전체 고양이 중에 각 브랜치에 속하는 비율 x 각 브랜치의 엔트로피 로 얼마나 엔트로피가 높은 지를 파악할 수 있다.
=> 이렇게 하면 각 노드(feature)의 엔트로피를 구할 수 있게된다. (여기서 가장 작은 애를 선택해서 노드로 정하면 됨)

이렇게 해서 etnropy의 정도를 구하고 그걸 root의 엔트로피 정도에 빼줌으로써 얼마나 entropy가 감소하였는 지 파악할 수 있다.

먼저 식은,

• $H(p_1^{root})-(w^{left}H(p_1^{left})+w^{right}H(p_1^{right}))$
• $p_1^{root}$: root node의 비율 => root node에 존재하는 정답의 비율
• $p_1^{left}$: left node의 비율 => left node에 존재하는 정답의 비율
• $p_1^{right}$: right node의 비율 => rigth node에 존재하는 정답의 비율
• $w^{left}$: 왼쪽 branch에 곱해지는 가중값 => 전체 중에 left에 속하는 example의 개수
• $w^{right}$: 왼쪽 branch에 곱해지는 가중값 => 전체 중에 right에 속하는 example의 개수
  **여기서 오른쪽 왼쪽을 나누는 건 고양이인가(yes) 아닌가(no)이다.

좀 더 직관적으로 설명하면, 그냥 이전에 root node에서 entropy를 가지고 있었는데, 이걸 어떤 feature기준으로 example들을 분류하니까 그만큼 entropy가 줄어들었다.
고로, 이 둘의 차이가 클 수록 entropy가 많이 줄어들었고, 정보가 좀 더 확실해졌다고 볼 수 있는 것이다.

정리해보자면,
1. root node의 example들 확인
2. 가능한 모든 특징에 대한 information gain을 계산., 가장 높은 information gain을 갖는 애를 선택
3. dataset을 선택된 feature에 대해 나누고 tree의 왼쪽 오른쪽 branch를 생성
4. 그리고 이러한 분할 프로세스를 위에서 말한 기준을 만족 시킬 떄까지 계속 반복(하나의 노드가 하나의 class로만 이루어져 있을 때, 여기서 Purity score=information gain etc..)

Using one-hot encoding of categorical features

이전까지 예로 들었던, decision tree는 feature value가 2가지(yes or no)를 갖을 때를 예로 들었다.

만약 3개 이상의 feature value를 갖는다면, 어떻게 표현하면 좋을까?

가장 간단한 방법으로는 one-hot encoding이라는 방법을 하는데,

그냥 해당하는 feature value의 값응 1로 설정하고 해당하지 않는 feature value는 0으로 설정하여 계산하는 것이다.

이건 그냥 하나의 feature을 feature value의 개수만큼 이진 분류 feature들로 더 만드는 것이다.

Continuous valued features

regression 문제에서 봤던 연속형 변수를 갖는(ex. 집값, 키, 체중 etc..)것 들에 대해서는 어떻게 하는게 좋을까?

Decision tree는 이러한 문제에 대해서 그냥 기준점을 정하고 그 기준점으로 분류하여 원래와 같이 진행한다.

Regression Tree

Decision Tree로 regression 문제는 어떻게 처리할 수 있을까?

각 노드에서 feature value들의 분산을 구하여 entropy처럼 사용하여 좋은 feature들을 고르고 트리의 구성을 진행하고

마지막 노드에서 나온 값들의 평균을 구하여 예측을 진행한다.

Using multiple decision trees

현재는 training example중 하나라도 값이 변하면 tree의 전체 구조를 변경하여 새로우 tree를 만들어줘야한다.

이러한 문제를 해결하기 위해, 우리는 많은 decision tree들을 사용해서 좀 더 명확한 값을 도출해볼 수 있다.]

이러한 방식을 ensemble이라고 하며,

가장 간단한 방법은 3개의 decision tree를 ensemble했다고 가정하면, 내가 새로 분류할 example을 입력으로 넣고 각 tree의 결과에서 많이 나온 결과로 결정한다.

Sampling with replacement

Tree의 ensemble을 위해 우리는 더 많은 데이터셋이 필요하다.

이러한 추가적인 데이터 셋을 만들기 위해 원래 가지고 있던 데이터에서 무작위로 sampling하여 구성하지만, 중복도 허용하는 방법으로 새로운 데이터 셋을 만들어 낸다.

Random forest algorithm

위에서 말한 방법으로 새롭게 만들어진 data set들을 사용하여 새로운 tree들을 만드는데, 여기에 추가로 feature들도 다 사용하는 것이 아닌 random으로 전체중 일부만 사용하여 더욱 새로운 형태의 Tree를 만들어낸다.

XGBoost

간단하게 설명해서 잘못 분류된 example들에 집중하여 더욱 성능을 끌어올리겠다는 개념이다.
replacement를 허용하여 sampling한 데이터로 만든 tree에서 data를 예측하게 하고 잘못 예측한 example들에 집중하여 가중치를 부여해서 다시 sampling을 하게하고
그 데이터로 다시 tree를 생성하여 성능을 끌어올리는 방법이다.

결국 이렇게 나온 decision tree는 표로 되어있는 데이터 형식에서 잘 작동하지만 이미지, 오디오, text와 같은 비정형 데이터에 대해서는 적절하지 못하다.