3.6.1 정보 이득 최대화: 자원을 최대로 활용

가장 정보가 풍부한 특성으로 노드를 나누기 위해 트리 알고리즘으로 최적화할 목적 함수를 정의합니다. 이 목적 함수는 각 분할에서 정보 이득을 최대화합니다. 정보 이득은 다음과 같이 정의합니다.

여기에서 f는 분할에 사용할 특성입니다. D_p와 D_j는 부모와 j번째 자식 노드의 데이터셋입니다. I는 불순도(impurity) 지표입니다. N_p는 부모 노드에 있는 전체 샘플 개수입니다. N_j는 j번째 자식 노드에 있는 샘플 개수입니다. 여기에서 볼 수 있듯이 정보 이득은 단순히 부모 노드의 불순도와 자식 노드의 불순도 합의 차이입니다. 자식 노드의 불순도가 낮을수록 정보 이득이 커집니다. 구현을 간단하게 하고 탐색 공간을 줄이기 위해 (사이킷런을 포함해서) 대부분의 라이브러리는 이진 결정 트리를 사용합니다. 즉, 부모 노드는 두 개의 자식 노드 D_left와 D_right로 나누어집니다.