Decision Tree Learning - (3) incremental way

 

2023.12.03 - [Game AI] - Decision Tree Learning (2)

Decision Tree Learning (2)

 

 

Incremental Learning

 

지금까지는 온전한 데이터들이 들어오면 그걸로 Decision Tree를 만들어 냈다. 그러나 새로운 데이터들이 들어온다면 이런 데이터들을 어떻게 처리해야 할까? 

 

가장 간단한 방법은 그냥 Decision Tree전체를 다 만들어버리는 방법이지만 딱 봐도 비효율적이다.

 

따라서 새로운 데이터를 처리할 방법이 더 필요하다.

 

ID4

 

incremental하게 Decision Tree를 만드는 가장 간단한 알고리즘은 ID4이다. 이름에서 알 수 있듯 ID3과 연관이 있다.

 

먼저 ID4 알고리즘을 수행하기 위해서 Tree의 각 노드는 자신까지 닿았던 모든 데이터들을 가지고 있어야 한다.

 

 

그 다음 조건에 따라서 알고리즘을 수행한다. 알고리즘의 핵심은 데이터가 추가된 뒤에도 Decision Tree가 아직 최적의 information gain 갖는 구조로 되어있는지를 체크하는 것이다. 만약 그렇다면, 데이터를 자식 노드에게 넘긴다. 만약 아니라면 자신과 자신의 sub tree를 재 계산한다. 이런식이면 데이터가 추가되더라도 depth가 무한정 깊어지진 않는다.

 

한계

 

ID4가 학습이 불가능 하다고 판단할 때가 있는데, 이건 ID4가 적합하지 않은 Tree를 생성핸다는 말이 아니라, 데이터가 추가될때마다 rebuild가 계속 발생하는 것을 의미한다. (즉, 유의미한 패턴을 찾지 못해 학습이 이뤄지지 않았다는 것)

 

ID3 알고리즘은 엄밀히 따지면 휴리스틱한 알고리즘이다. 노드의 정보(엔트로피)가 일종의 추정치이기 때문. 그렇기에 이 값들이 최선은 아니다. 실제로 더 나은 방법들도 존재하나, 게임AI에서는 손해를 감수하면서까지 적용할 가치가 있는지 따져야 하며, 보통 회의적이다.