Decision Tree Learning (2)

2023.11.26 - [Game AI] - Decision Tree Learning - 1

Decision Tree Learning - 1

 

 

 

ID는 연속적인 속성에서 동작할 수 없고 속성의 값들이 많을 경우에도 활용이 어렵다. 따라서 속성의 값들은 몇 개(주로 2개)의 이산적인 카테고리로 나뉘어져야 한다.

 

Single Split

 

연속적인 값들은 역치(threshold) 를 정하면 기준으로 사용할 수 있다. 가령 체력이 50 이상이면 '건강함' 체력이 50 미만이면 '부상'으로 분류할 수 있다.

 

이런 역치 값들은 동적으로 계산될 수 있는데, 주어진 정보량이 가장 많게 되는 값을 선택하면 된다.

 

 

가령 아래와 같은 데이터가 있다고 가정하자.

체력	행동
50	방어
39	공격
25	방어
17	방어

 

위 데이터에서는 역치를 25~39사이로 잡고. 이 역치보다 체력이 높으면 공격, 낮으면 방어를 선택한다고 했을 때 가장 정보가 많이 주어진다.

 

따라서 25~39의 중간 값인 32를 역치로 설정하는 것은 합리적이다.

 

그런데 이런 역치 값들은 데이터에 의존한다. 따라서 데이터가 다르면 역치 값도 달라질 수 있다. 

 

다중 카테고리

속성을 단 두개의 카테고리로 나누는 건 비합리적이여 보일 수 있다. 가령 체력이 0에 가까워 빈사 상태인 것과, 단순히 부상인 것은 크게 다르기 때문이다.

 

그러나 가능한 카테고리가 추가될수록 가능한 시나리오가 exponential하게 증가한다. 

 

물론, 여러 카테고리를 나눌 수 있는 알고리즘들이 존재하며, 이런 알고리즘들은 인공 신경망 같이 그냥 카테고리를 분류할 수 있기만 하면 된다.

 

그러나 게임에서 이런 알고리즘들은 거의 쓸 일이 없다. ID3 자체가 재귀적으로 생성되기 때문에, 같은 속성이 여러 노드에 걸쳐 여러 번 사용될 수 있기 때문이다. 심지어는 같은 속성으로 구분한 branch 바로 아래에 동일한 속성이 올 수 있다.

 

예를 들면 체력 "50"을 기준으로 branch를 나눈 뒤에, 다시 체력이 "25"미만일 때로 branch를 나눌 수 있기 때문이다. 이러면 체력이 0~24일때, 25~49일때, 50~일 때로 구분이 가능하다.