패턴인식 - 7. Decision tree (2)

1. Decision tree 만들기 예제

- class, 기다린다, 안기다린다 = { yes, no }

- feature = {alt, bar, fri, ..., est} 내가 배고픈 정도, 식당의 여건 등등

- X, 식당 = {x1, x2, ..., x12}

- 식당이 input으로 들어왔을 때 기다릴지 말지를 결정하는 decision tree를 만들어보자.

 

- Information Gain을 최대로 할 수 있는 attribute를 선택해서 split해보자.

- 첫번째 attribute로 Type을 골랐을때, Patrons을 골랐을때 split되는 결과는 다르다. 

- 각각의 경우 IG를 구해보면 다음과 같다. IG(patrons)가 더 크기 때문에 더 좋은 tree라고 선택한다.

- 분류가 아직 덜된 leaf노드에 대해서 다음 split을 수행한다.

- 지금 상황에서 선택한 patrons가 반드시 가장 좋은 결과물 tree를 보장하지는 않는다. 우리는 greedy한 방식으로 tree를 만들고 있기 때문이다. 

2. 좋은 나무란?

- 트리가 너무 작으면 결정이 잘 안될 수 있다.

- 반대로 너무 크면 계산 효율이 떨어진다. 너무 세세하게 나눠버리면 overfitting되어 오히려 성능이 안 좋을 수 있다.

- Occam's Razor : 관찰 데이터에 대해 잘 맞는 심플한 가정을 사용해서 너무 복잡하지 않은 모델을 만들어야 한다.

 

- 트리를 쪼갤 수록 판단에 사용되는 데이터가 지수배로 줄어든다. 따라서 모든 판단에 대해서 어느정도 의미가 있으려면 굉장히 많은 데이터가 필요하다.

- 아까도 말했지만 tree가 너무 세세하게 쪼개지면 overfitting 문제가 생긴다.

- geedy한 방식으로 tree를 만들고 있기 때문에 global optimum을 찾는게 아니라 효율적으로 근접해지려고 노력한다.

- 만약 쪼개는 step이 연속적인 값에 대한 판단이라면 부등식으로 나누어야 한다. 그럼 그 threshold를 얼마로 잡을 건지에 대한 문제도 생긴다. 

- 즉 decision tree는 디자이너가 tuning을 해야 하는 부분이 많다.

 

- k-NN은 sample간의 거리를 구해서 판단에 활용한다 따라서 남자, 여자 같이 class 구분이 필요한 경우는 decision tree가 더 유리할 수 있다.

- k-NN은 판단할때 여러 feature를 동시에 고려한다 따라서 feature간의 가중치를 둬야 하는 상황도 생길 수 있다. 그러나 decision tree는 feature를 한 번에 하나만 쓰기 때문에 scale문제가 생기지 않는다.

- k-NN은 판단할때 모든 데이터를 살펴봐서 거리를 구해야 한다 하지만 tree는 한번 만들어지면 결정하는데 시간이 오래 걸리지 않는다.

 

- feature들의 상호작용 있는 경우는 k-NN이 훨씬 유리하다. (pixel을 따져야 하는 경우) 따라서 일반적으로 feature가 많을 수록 결정트리보다 더 좋은 예측을 한다.