Decision tree 정리

Decision Tree (의사결정나무)

결정 트리의 학습 -> 결정 트리를 구축하는 방법. Grow a tree

Supervised learning에 사용되는 방법과 같이 특징 (features)들과 class의 index로 데이터가 구성된다. 

Decision Tree (DT)의 leaf는 클래스의 index를, branch or node는 decision node가 된다. 

decision node에서는 가능한 feature값으로 branch를 형성한다. 각 node가 내부에 있는 경우에 feature이 하나이다. 

feature에 따라 branch를 형성하고, 만약 node가 leaf인 경우 class의 index가 존재한다.

출처: 위키피디아, 결정 트리 학습 

여기서 남자인가? 는 node(root node), 사망, 생존은 leaf가 되고 나이, sibsp는 feature가 된다.

DT에서 중요한 것은 각 node에서 적용되는 split criteria이다. 만약 처음에 상당히 중요한 질문을 하게 되면 쉽게 모델은 다음 쉬운 질문들을 통해서 문제를 맞춰갈 수 있다.

Node를 나누는 split Criteria는

ID3는 Entropy에 기초한 information gain, CART는 Gini index를 사용한다.

Entropy는 uncertainty를 계량화하기위한 것으로 다음과 같이 표현된다.

Entropy가 높을 수록 uncertainty는 증가하고, entropy가 낮을수록 확실성은 증가한다.

Information gain은 feature A를 사용해서 얻는 entropy의 감소 정도이다.

Value(A)는 feature A가 가질 수 있는 모든 값의 set이다. Dv는 D의 부분집합으로 D는 전체 데이터 집합이고 feature A가 v를 갖는 set이다.

가 가장 큰 feature와 v를 찾았다면, 다음으로  가 가장 큰 feature와 v를 찾는다. 이런 방법으로 가장 Information gain이 최대인 즉 entropy의 감소 기대 값이 가장 큰 (불확실성을 크게 줄이는) feature와 value를 선택해 node를 결정한다. 만약 node에 class의 index가 한종류라면 leaf node가 된다.