패턴인식 - 6. Decision tree (1)

- 지난 시간에 PW, k-NN을 활용하여 분류기를 설계하는 방법을 배웠다. 이번 시간에는 결정 트리를 이용해서 분류기를 만드는 방법을 알아본다.

1. Decision Tree

- 분류를 위한 tree를 만드는 것이다.

- 오렌지와 레몬을 구분할 특징 벡터 [height, width]가 있다고 하자.

- Decision tree의 각 step에서 feature값의 정도에 따라 child를 선택해 내려가면 분류 결과에 도달하게 된다.

- 위의 예시는 판단오류에 해당한다.

- 이렇게 tree에 노드를 더 추가하면 지금 당장은 완벽하게 오류를 0으로 만들 수 있지만 트리를 탐색하는데 더 많은 시간이 필요하다.

 

- 즉 decision tree는 features를 통해 class에 따른 특징 공간을 나누는 것이다. 

- 위의 예시에서는 특징이 두개이므로 2차원 공간에서 분류가 이루어진다. 2차원 공간을 쪼개서 class들의 공간으로 나눈다.

- 판단 오류를 최소한으로 하는 decision tree를 잘 설계해야 한다.

 

- 위의 예시에서 width, height 특징들은 서로 독립이였다.

- 만약 x1,x2가 서로 상관 관계를 갖는다면 x3라는 새로운 축으로 변환이 가능하다.

- 또 다른 decision tree의 예시이다. branch 개수나 feature 조건의 판단은 얼마든지 다양할 수 있다.

 

- 정리하면 feature가 {x1, x2, ..., xd} 이면 decision space는 d차원이 된다. 그 공간을 쪼개서 class C = {c1, c2, ..., cn} 들의 구역으로 나누는게 decision tree이다.

- tree 형태이기 때문에 각 샘플의 판단은 root에서 leaf까지의 경로로 결정되고 그 경로가 decision space의 한 영역을 구분짓는다.

 

- k-NN은 입력이 들어오면 주변 샘플과의 거리를 살펴서 본인의 class를 판단한다. 그래서 모든 sample을 전수조사해야 한다.

- 하지만 decision Tree는 미리 space를 class별로 분할한 다음에 입력을 집어넣는 것이다. 따라서 판단 속도가 빠르다.

2. Entropy

 

 

 

- 클래스 0과1에 속하는 샘플수에 따라서 엔트로피를 구한 모습이다. 어느 한 클래스로 잘 분류될수록 엔트로피는 낮다.

- leaf 노드들의 엔트로피가 낮을 수록 좋은 decision tree이다.

3. Information Gain

- 현재 루트 노드의 엔트로피는 약 0.91로 아주 큰 상태다.

- 어떤 속성을 활용하여 한 step을 거쳤을때 leaf 노드의 엔트로피는 각각 0, 1이다.

- information gain을 구해보면 위와 같다. 1/3은 149개중 50개가 왼쪽 leaf node로 갔다는 뜻이고 2/3은 149개중 99개가 오른쪽 leaf node로 갔다는 뜻이다.

- information gain은 entropy를 얼마나 낮추었는가를 나타낸다.

- 어떤 attribute를 가지고 tree를 만들었을 때 information gain이 클수록 더 효과적이다 라고 할 수 있다.

4. Build a Decision Tree

- decision tree를 만들기 위한 도구들은 다 준비됐다. 이제 직접 만들어보자.

- 어떤 feature들의 얼만큼 threshold를 가지고 나눌 것인지 결정하면 된다.

- 원리는 간단하다 IG가 가장 큰 경우를 찾아서 트리를 뻗어나가면 된다.

 

- 아래는 가장 간단한 greedy, recursive approach로 tree를 만드는 방법이다.

1. attribute를 하나 골라서 split한다.

2. 나누어진 두 그룹에 대해서

• 만약 그룹에 example이 하나도 없으면 1로 돌아간다
• example들이 모두 같은 class에 속하면 return
• IG값이 만족스럽지 않다면 다시 1로 돌아간다.