#분류문제 #Decision tree

    의사결정나무라고 불리는 이 모델은 인간이 이해하기에 꽤나 직관적이다. "if-then" 방식으로 특정 속성(attribute)에 대해서 가지로 나누고 그 밑 가지에 또 다른 속성으로 나누어, 궁극적으로는 특정 클래스에 속하는 것을 보여주는 방식이다. Desicion tree에 들어가는 데이터의 형식은 각각의 attribute 값의 속성 레벨 값과, 궁극적으로 데이터가 속하는 클래스 정보이다. Attribute 속성 레벨값은 범주형 자료값일 수도 있고, 이산형 값일 수도 있다. 

ex) Day1 ; <outlook>, <Temperature>, <Humidity>, <Wind>, <Class information, PlayTennis?>

Decision tree의 머신러닝 기법들로는 ID3(Iterative dichotomiser 3), C 4.5, CART 알고리즘이 있다.

Decision tree의 대표 알고리즘에 해당하는 ID3 알고리즘에 대해서 살펴보자. 

 

1. 전체 데이터를 포함하는 Root node를 생성한다. 

2. 샘플들이 단 하나의 클래스에 속한다면, 그 단계 노드가 잎이 되고 그 클래스 정보로 레이블을 부여한다.

3. 하위 가지치기로 나눌 수 있는 속성이 비어있어도, 그 단계 노드가 잎이 되고 클래스 수가 가장 높은 값으로 레이블을 부여한다.

 4. 2,3번이 아니라면, 즉 하나의 노드로 끝날 수 없는 경우라면 아래의 과정을 시작한다.

   4.1 가장 information gain 효과가 큰 속성을 선택한다. (위의 그림의 경우라면, 전날 음주 여부가 information gain이 커서 root node가 된 것이다)

   4.2 그 속성을 루트 노드로 설정하고, 값에 가지를 생성한다. 

   4.3 상위 속성을 만족하는 하위 가지를 생성하여 새로운 하위 노드들을 생성한다. 각 노드에 대하여 단계2로 이동한다.

 

*만약, 해당 노드에 속하는 샘플들이 모두 같은 클래스를 가지는 경우 아래로 가지치기를 더이상 진행하지 않는다.

또한, 더이상 노드에 넣을 속성값을 선택할 수 없다면, 가지치기를 멈춘다.

ID3 알고리즘은 위에서부터 아래로 내려가는 하향식 의사결정 방식이고, greedy search 방식을 통해서 가능한 tree들 중에서 가장 적합한 tree를 선택하고자 한다. 이때, 새로운 노드를 형성할 때나 tree를 선택할 때 기준이 되는 것은 information gain이다. 그리고 한번 상위 노드값의 트리 속성이 결정되면, 번복하지 않는다는 특성을 가지고 있다. 

Occams' razor의 원칙에 따라서 가장 단순한 모델, 즉 같은 informaion gain 효과가 있다면 단순한 트리 구성을 가지고 있는 것이 우선적으로 선택된다.