[머신러닝] 결정 트리(Decision tree)

결정 트리 (Decision tree)

결정 트리(Decision tree)는 의사 결정 규칙과 그 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종입니다. 의사 결정 분석에서 목표에 가장 가까운 결과를 낼 수 있는 전략을 찾기 위해 주로 사용됩니다. 또한, 분류(Classification)와 회귀(Regression) 모두 가능한 지도 학습(Supervised learning) 모델 중 하나입니다.

위 그림은 결정 트리를 도식화한 그림입니다. 트리에서 최상위 노드를 Root Node라고 하고, 자식 노드가 없는 가장 최하위 노드를 Leaf Node, Treminal Node 혹은 External Node 라고 합니다. 자식 노드를 가지고 있는 노드를 Internal Node라고 합니다.

위 그림은 생존인지 사망인지 의사결정 해주는 decision tree입니다. 구조를 보면 Internal node는 “조건문”이고, 예시로는 성별 == 남자, 나이 > 9.5, sibsp > 2.5 조건문으로 나타나 있습니다. Edge는 조건 결과에 따른 분기로 yes 인 경우면 왼쪽으로, no 인 경우면 오른쪽 노드로 내려갑니다. External node는 결과(사망 or 생존)를 보여줍니다.

생성 알고리즘

성능이 좋은 Decision tree를 위해서는 좋은 트리의 조건을 고려해 주어야 합니다.

좋은 트리의 조건

1. Leaf node에서 통일된 label(class)의 데이터만 남는 것 -> 이는 높은 분류 정확도와 의사결정 정확도를 의미합니다.

2. 트리의 높이(혹은 깊이)가 짧은 것 -> 트리의 높이(깊이)가 짧을수록 수행 속도가 빨라집니다.

어떤 feature를 먼저 고려하는가에 따라 트리의 깊이가 달라질 수 있습니다. 좋은 트리의 조건을 모두 만족시키려면 어떤 방법으로 트리를 생성 하면 될까요?

트리 생성 방법

트리를 생성할 때, 순서는 Root node에서 leaf nodes 순서로 행해져야 합니다. Root 노드는 모든 데이터를 고려한다고 가정하며 하위 노드(자식 노드)로 내려가면서 데이터들이 분류됩니다.

1. 노드에서 고려할 데이터가 이미 하나의 class에만 속하였거나, 더 이상 고려할 feature가 없으면 Leaf node로 여기고 자식노드를 생성하지 않습니다.

• -> 고려할 feature가 더 이상 없어서 leaf node가 된 경우, 가장 많은 수의 calss를 결과 값으로 채택합니다.

1. 각 노드에서 고려할 feature 선택 시, 데이터들을 가장 잘 나눠주는 feature를 선택합니다. 이때 Leaf node에서 완벽하게 데이터들이 나눠진다는 보장은 없습니다.

2. 선택된 feature에 대한 조건 별로(값마다) 자식노드를 생성합니다.

3. 각 자식 노드에서는 해당 조건을 만족하는 데이터만 고려하여 1부터 반복합니다.

2번 과정에서 나온 데이터들을 가장 잘 나눠주는 feature 를 정의하기 전에 직관적으로 본다면 각 자식 노드에 동일 class에 속한 데이터들만 해당된다면 feature들을 잘 나누었다고 할 수 있습니다.

이때, Purity라는 용어가 나오는데 이는 한 쪽 데이터만 존재할 수록 더 pure하다는 것을 의미합니다.

Entropy (Impurity)

Purity의 반대 개념은 Entropy(Impurity)입니다. “Entropy가 크다” 라는 것은 “더 Chaotic 하다” 라는 것을 의미합니다. 또한 Informatio theory에 따르면 “Entropy가 크다”는 더 정보가 많다는것을 의미하기도 합니다.

위의 그림에서는 왼쪽이 가장 Entropy가 높고 오른쪽으로 갈수록 Purity하다고 표현할 수 있습니다.

수식은 다음과 같이 표현할 수 있습니다.

P_i는 Class i의 확률을 의미하며, (i 클래스의 데이터 / 전체 데이터)로써 계산 합니다.

예시로 극단적인 경우의 Entropy 값을 관찰해 본 그림입니다.

이 Entropy를 tree 생성에 적용될 때는 각 노드마다 어떤 feature를 고려하는 것이 좋을지 고를 때 입니다. 자식 노드들이 가지는 데이터가 pure 할 수록 좋은 것 이라고 한다면 부모 노드의 purity와 자식 노드들의 purity를 비교 했을 때, 그 차이가 클수록 더 좋은 feature라고 할 수 있습니다.

Information Gain

Entropy(impurity)가 클수록 더 많은 정보를 가지고 있다는 것을 의미하기도 합니다. Information theory에서는 Entropy(impurity)를 정보의 함량이라고도 보고 있습니다. 부모 노드 -> 자식 노드 방향으로 데이터 흐르므로 부모 노드에서 정보의 함량이 더 크다는 것을 알 수 있습니다.

따라서, IG(Informatio Gaint) = 부모 노드의 entropy(impurity) - 자식 노드들의 entropy(impurity)라고 할 수 있습니다. IG 값이 클 수록 자식 노드들이 가지는 데이터가 더 pure 하다는 것을 의미합니다.

앞서 나와 있었던 트리 생성 방법에서 순서 2번을 다시 정리하면

1. 각 노드에서 고려할 feature 선택 시, 데이터들을 가장 잘 나눠주는 feature를 선택 (가장 IG가 큰 feature 선택)

이라고 정리할 수 있겠습니다.

참고 자료

머신러닝 수업자료_DECISION TREE(순천향대학교 빅데이터공학과 정영섭 교수님)