Decision Tree Learning - 1

 

 

 

2021.10.21 - [Game AI] - 의사 결정 - Decision Tree

의사 결정 - Decision Tree

 

 

개요

 

Decision Tree는 효율적인 학습 대상이다. Strong Supervision(결과가 맞았는지 틀렸는지 피드백)을 통해 만들어진 행동들로 동적 생성이 가능하다. 

 

 

---

 

ID3

 

게임 AI에서 Decision Tree 학습에는 일반적으로 ID3라는 걸 쓴다. 산업적으로는 C4, C4.5, C5같은 최적화 버전이 더 있으니 참고.

 

건강함	엄폐중	탄약O	공격
부상	엄폐중	탄약O	공격
건강함	엄폐중	탄약X	수비
부상	엄폐중	탄약X	수비
부상	노출됨	탄약O	수비

 

위와 같은 예시 데이터들이 있을 때, 각각의 열을 속성이라고 칭한다. (마지막 열은 제외)

 

알고리즘은

1. Decision Tree에 있는 리프노드 하나로 시작을 한다. 그리고 리프노드에는 예시 데이터들이 할당된다.
2. 리프노드는 다시 두 그룹으로 쪼개진다. 이 때  가장 효율적인 트리를 생성할 수 있는 속성을 기준으로 쪼개진다.
3. 노드가 분화됐다면, 다시 각각의 노드에 예시 데이터의 부분집합을 할당한다.
4. 그리고 알고리즘을 각각의 노드에 대하여 반복한다.

 

그러면 어떻게 효율적인 속성을 고를까? 직관적으로는 탄약이 먼저 노드를 쪼개기에 좋아보인다. 탄약이 없으면 확실히 수비를 선택하니까. 그 다음으로는 엄폐여부가 좋다. 탄약이 있는 상태에서 엄폐중이라면 확실히 공격이다. 체력의 여부는 공격이나 수비를 결정하는데 큰 도움이 되지는 못한다.

 

ID3 알고리즘에서는 각 속성이 얼마나 효율적인지 수학적으로 나타내기 위해 속성에 엔트로피를 부여한다. 만약 모든 데이터에서 속성이 같은 값을 가진다면, 해당 속성으로 노드를 분화할 필요가 없으니 엔트로피 값은 0이다. 만약 모든 데이터에서 속성이 균등하게 분포되어 있다면 엔트로피는 1로 최대이다.