[Machine Learning] 결정 트리
결정 트리
결정 트리는 예/아니오로 답할 수 있는 어떤 질문들이 있고,
그 질문들의 답을 따라가면서 데이터를 분류하는 알고리즘입니다.
지니 불순도 (Gini Impurity)
결정 트리에서는 여러 질문들의 답을 따라가면서 데이터를 분류한다고 했는데요,
결정 트리를 만들 때 각 노드에 어떤 질문 또는 분류가 들어갈지를 어떻게 고를까요?
머신 러닝 프로그램이 결정 트리를 만들 때에는
경험을 통해 직접 정해나가야 합니다.
여러 데이터를 분류해보면서 각 위치에서 어떤 노드가 제일 좋을지를 결정하는 것입니다.
이를 위해서는 좋은지 안좋은지를 평가할 기준이 있어야 하는데요,
결정 트리에서는 이것을 지니 불순도(Gini Impurity)라고 합니다.
지니 불순도는 데이터 셋 안에 서로 다른 분류들이 얼마나 섞여있는지를 나타냅니다.
지니 불순도는 데이터 셋이 얼마나 분순한지를 숫자로 표현해줍니다. (지니 불순도가 클수록 불순합니다.)
수식으로 나타내면 아래와 같습니다.
\[ \displaystyle GI = 1 - \sum_{i=1}^{J}p_{i}^{2} \hbox{, J: number of classes} \]
분류 노드 평가하기
좋은 분류 노드는 최대한 많은 학습 데이터 예측을 맞춥니다.
해당 노드로 온 데이터 셋을 A라고 분류했을 때,
그 데이터 셋에 A에 해당하는 데이터가 많을수록 좋고,
데이터 셋이 순수할수록(지니 불순도가 낮을수록) 좋은 분류 노드라고 말할 수 있습니다.
만약 데이터 셋의 불순도가 높은데 그 데이터 셋이 분류될 카테고리를 정해버린다면
틀리게 분류되는 데이터가 많겠죠.
이렇게, 분류 노드를 만들려고 하는 경우에 데이터의 불순도를 계산하면
어느 정도를 맞게 분류할 수 있을지를 한 번에 알 수 있습니다.
질문 노드 평가하기
결정 트리에서 좋은 질문은 데이터를 잘 나누는 질문입니다.
데이터를 C1 또는 C2로 분류를 하려고 할 때,
어떤 노드에서 A인가요? 라는 질문을 했을 때 데이터가 두 개로 나뉘는데,
A인 데이터는 모두 C1이고 다른 데이터는 모두 C2라면 이 질문은 데이터를 아주 잘 나누는 질문이므로 좋은 질문입니다.
정리하면, 좋은 질문 노드는 섞여있는 데이터를 잘 나눠서 점점 더 분류하기 쉽게 만들어줍니다.
나뉜 데이터 셋들이 순수할수록(지니 불순도가 낮을수록) 더 좋은 질문입니다.
따라서 질문 노드의 성능을 판단할 때는 나뉜 두 데이터 셋에 지니 불순도를 사용합니다.
예를 들어, 100개의 데이터가 A인가요? 를 묻는 질문 노드를 거쳐간다고 하겠습니다.
A인 데이터는 60개이고, 그 중 C1이 40개, C2가 20개가 있고,
A가 아닌 데이터는 40개이고, 그 중 C1이 10개, C2가 30개가 있다고 하겠습니다.
이럴 경우에 A인 데이터와 A가 아닌 데이터의 \(GI\)는 아래와 같습니다.
\[ GI_{A} = 0.444, GI_{not A} = 0.375 \]
이걸 평균을 내주면 됩니다.
그냥 합치는 건 아니고 각 데이터의 크기만큼 무게를 줘서 합쳐줍니다.
\[ \displaystyle GI_{avg} = \frac{60}{100}GI_{A} + \frac{40}{100}GI_{not A} \]
이런 식으로 이 질문이 데이터를 얼마나 잘 나누는지를 수치로 표현할 수 있습니다.
낮을수록 좋고 높을수록 안좋은 것입니다.
노드 고르기
이렇게 매 상황에서 노드를 평가하는 방법을 알아봤는데,
이를 이용해서 어떤 노드를 쓸지를 골라야합니다.
분류할 데이터의 불순도가 \(GI_{1}\)이고,
질문 노드의 후보로 다음 2개가 있다고 하겠습니다.
- A인가요?
- B인가요?
A인가요? 에 대한 지니 불순도는 \(GI_{2}\)
B인가요? 에 대한 지니 불순도는 \(GI_{3}\) 일 때,
\(GI_{1}\)이 제일 낮다면 바로 분류를 하면 되고,
\(GI_{2}\)이 제일 낮다면 노드로 A인가요? 를 골라주고,
\(GI_{3}\)이 제일 낮담녀 노드로 B인가요? 를 골라주면 됩니다.
속성이 숫자형일 때 질문 노드
여태는 이것인가요? 이런 식으로 속성이 참 거짓으로만 나뉠 때만 다뤘는데요,
만약 데이터가 숫자형으로 있는 경우에는 만들 수 있는 질문이 굉장히 많습니다.
예를 들어 독감인지 아닌지를 분류하고 싶은데,
체온을 이용한 질문 노드를 쓰고 싶다고 하겠습니다.
그리고 사람들의 체온이 36.3도, 36.5도, 36.8도, 37.1도, 37.4도, 37.8도, 38도, 38.4도 이렇게 있다고 한다면,
모든 평균 체온에 대해서 지니 불순도를 계산합니다.
그러니까, 아래와 같이 많은 질문들을 하는 것입니다.
- 열이 36.4도를 넘나요?
- 열이 36.65도를 넘나요?
- 열이 36.95도를 넘나요?
이런식으로 각 질문들을 쓸 때의 지니 불순도를 계산해서
불순도가 가장 낮은 질문 노드를 체온을 이용한 질문 노드로 사용해주면 됩니다.
속성 중요도 (Feature importance)
속성 중요도를 계산하기 위해서는 노드 하나하나의 중요도인 노드 중요도(node importance)를 알아야 합니다.
노드 중요도는 아래와 같은 식으로 계산할 수 있습니다.
\[ \displaystyle NI = \frac{n}{m} \cdot GI - \frac{n_{left}}{m} \cdot GI_{left} - \frac{n_{right}}{m} \cdot GI_{right} \hbox{, n: 노드까지 오는 데이터 수, m: 전체 학습 데이터 수, GI: 노드 지니 불순도} \]
생각해보면 이 식은 한 노드에서 데이터를 두 개로 나눴을 때,
데이터 수에 비례해서 불순도가 얼마나 줄었는지를 계산하는 식입니다.
특정 노드가 얼마나 중요한 노드인지를 판단할 때,
이 노드 전후로 불순도가 얼마나 낮아졌다는 것을 사용하는 것입니다.
나눠지는 데이터 셋들에 대해 점점 더 알아간다 해서 이 수치를 정보 증가량(information gain)이라고도 합니다.
이런 식으로 질문 노드의 중요도를 다 계산해 줬다면, 이걸 써서 속성 중요도를 구할 수 있습니다.
A라는 속성이 얼마나 중요한지 알고 싶다고 하겠습니다.
A인가요? 라는 질문을 갖는 모든 노드의 중요도를 더하고, 트리 안에 있는 모든 노드의 중요도의 합으로 나눠줍니다.
쉽게 생각하면, 전체적으로 낮춰진 불순도에서 특정 속성 하나가 낮춘 불순도가 얼마인지를 계산하는 것입니다.
특정 속성을 질문으로 갖는 노드들의 중요도의 평균을 구한 것과 비슷해서
이 값을 속성의 평균 지니 감소(Mean Gini decrease)라고도 합니다.
각 속성의 평균 지니 감소를 사용하면 어떤 속성이 결정 트리에서 평균적으로 얼마나 불순도를 낮췄는지를 계산할 수 있고,
이걸로 결정 트리 안에서 그 속성이 얼마나 중요한지를 알 수 있는 것입니다.
Leave a comment