분류(Classification) – 의사결정 나무(Decision Tree) 2편

이번 글에서는 의사결정 나무(Decision Tree)를 구현할 때 최적의 분리(split)을 찾는 방법과 불순도를 평가하는 지니 계수와 엔트로피에 대해 살펴보려 한다.

■ 의사결정 나무의 장단점

지난 글에서 살펴봤듯이 의사결정 나무는 해석가능한 모델이다. 즉, 예측 결과를 알 수 있을 뿐만 아니라 왜 그렇게 예측하는지에 대한 설명이 가능하다. 또한, 분류 시 계산이 쉽고 빠르며(다만, 학습에 시간이 걸린다), 간단하고 정확하다는 장점이 있다.

그러나 의사결정 나무는 탐욕 알고리즘(greedy algorithm)이다. 다른 말로 ‘divdie and conquer’라고도 하는데 위에서 아래로 내려가며 반복적으로 파티션을 나눈다. 한 번 이뤄진 분리는 다시 되돌릴 수 없다.

또한 결정 경계(decision boundary)가 축에 평행하다는 한계점을 갖고 있다. 결정 경계란, 즉, 어떤 선을 경계로 이쪽과 저쪽을 구분하는 선을 말한다.

위와 같이 동그라미와 세모 데이터가 좌표평면에 있다고 하자. 이 때 빨간 선을 기준으로 한 쪽은 동그라미, 한 쪽은 세모로 분리가 가능하다. 바로 이 빨간 선이 결정 경계가 된다. 이를 의사결정 나무로 표현한 것이 우측의 도표이다. 의사결정 나무는 이렇게 축에 평행한 결정 경계만 갖게 되며 한 속성을 하나씩만 분리할 수 없다는 단점을 갖고 있다.

참고로 kNN의 결정 경계는 다음의 이미지처럼 임의적(arbitrary) 형태를 갖는다. k값이 커질수록 그 경계가 스무스한 곡선을 갖게 된다.

또한 의사결정 나무는 동일한 데이터로 어떤 기준을 언제 사용하느냐에 따라 다양한 나무를 그릴 수 있다. 그렇다면 최적의 의사결정 나무는 어떻게 찾고, 무엇을 기준으로 평가할 수 있을까?

■ 불순도(Impurity) – 지니 계수(Gini Index)

의사결정 나무의 분리가 잘 된 것을 평가하기 위해서는 불순도(impurity)라는 개념을 먼저 알아야 한다. 어려운 개념은 아니다. 우리는 이미 직관적으로, 분리 후의 결과가 하나의 클래스에만 속하는 것이 더 좋은 것을 안다. 즉, 어떤 기준을 적용하고 난 결과의 불순도가 낮을수록 더 좋다.

지니 계수(Gini index)를 들어본 적이 있을 것이다. 지니 계수는 경제적 불평등을 표현하는 방법인데 지니계수가 1에 가까울수록 소수의 사람이 다 해먹는 것을 의미하고, 0에 가까울수록 모두가 평등함을 의미한다. 의사결정 나무에서도 마찬가지이다. 지니 계수가 0에 가까울수록 그 클래스에 속한 불순도가 낮으므로 좋다.

예를 들어 클래스 A에 속한 데이터가 0개, 클래스 B에 속한 데이터가 10개라고 하자. 조건부 확률을 보면 전체 데이터 10개 중에 클래스 A에 속할 확률은 0/10 = 0 퍼센트이고, 클래스 B에 속할 확률은 10/10 = 100 퍼센트이다. 식에 대입하면 1 – [(0^2) + (1^2)] = 0 이 나온다. 몇 가지 예시를 통해 지니 계수를 계산해보자.

지니 계수의 범위는 0부터 (1-1/n)까지이다. 위의 예시는 클래스가 2개이므로 0.5일 때 불순도가 가장 높다. 그렇다면 분리 후 지니 계수는 어떻게 구할까?

먼저 부모 노드(회색 도형)의 지니 계수를 공식을 이용하여 계산한다. 그 뒤 분리된 지니 계수는 각 파티션의 크기가 가중치로 계산된다. 위의 예시에서 children은 2개의 파티션(주황색 도형)이다.

해당 파티션의 퀄리티를 평가하기 위해 지니 계수를 구하는 방법은 다음과 같다. 먼저 왼쪽 주황색 도형의 지니 계수와 오른쪽 주황색 도형의 지니 계수를 각각 구한 뒤, 전체 데이터 중에 몇 개가 왼쪽 주황색 도형에 속하는지(5/10), 몇개가 오른쪽 주황색 도형에 속하는지(5/10)를 구하여 지니 계수와 곱하고, 더하면 된다. 이를 식으로 표현하면 아래와 같다.

지금까지 살펴본 의사결정 나무의 지니 계수는 모두 이분법으로 나눠졌을 때였다. 만약 연속형 속성이라 여러 기준으로 나누는 다분법일때는 어떻게 구할까?

먼저 속성을 숫자 순서로 배치한 뒤, Gini(children)을 구하는 방법을 이용해 모든 노드의 지니 계수를 계산하면 된다. 그 뒤 가장 낮은 지니 계수를 갖는 split position을 선택하면 된다. 이 방법은 굉장히 단순 무식하며, 비효율적이다.

다시 한 번 위의 예시에서 지니 계수가 낮은 구간을 살펴보면, 라벨이 Y –> N 으로 바뀔 때, 또는 N –> Y로 바뀔 때 지니 계수가 가장 낮다는 것을 알 수 있다. 즉, 모든 노드의 지니 계수를 구할 필요 없이 라벨이 바뀔 때의 지니 계수만 구하면 된다.

■ 불순도(impurity) – 엔트로피(Entropy)와 정보 이득(Information Gain)

불순도를 계산하는 또 다른 방법으로는 엔트로피가 있다. 정보 이득이라고도 하는데, 간단히 말해서 데이터가 불순(impure)할수록 우리가 얻을 수 있는 정보량은 적다. 예를 들어 어떤 데이터를 가지고 결정을 내리고 싶은데 데이터가 반반 확률을 보여준다면, 결정을 내리기 힘들 것이다. 즉, 데이터에 결정을 내릴만한 충분한 정보가 없다고 보는 것이다.

엔트로피를 구하는 공식은 다음과 같다. 엔트로피의 범위는 0~log(nc) 사이의 값을 갖는다. 지니 계수와 마찬가지로 엔트로피 역시 0에 가까울수록 좋다.

엔트로피에 대한 상세한 설명은 다음에 좀 더 자세히 다루기로 하겠다. 이 글에서는 의사결정 나무를 만들 때, gain을 최대화 하는 지점에서 분리를 하고, 더 이상 정보를 획득하지 않을 때 — 즉 엔트로피가 0일 때 분리를 멈춘다는 것만 알아두자.

엔트로피의 단점으로는 파티션을 많이 만들려고 하는 성질에 있다. 예를 들어 각 id 단위로 파티션을 쪼갠다면 하나의 파티션 안의 불순도는 적겠지만 그 크기 역시 매우 작아져 오버피팅(Overfitting)의 문제가 생길 수 있다. 다음 글에서 의사결정 나무에서의 오버피팅 문제를 살펴보고, 어떻게 하면 오버피팅을 피해 의사결정 나무를 그릴 것인지 알아보겠다.