의사결정 나무와 랜덤 포레스트

• 본문의 일부는 Data Science from scratch(밑바닥부터 시작하는 데이터 과학)을 참고했습니다.

의사결정나무란?

Supervised Learning(교사학습)의 모델 중 하나로, 다양한 의사결정 경로(decision path)와 결과를 나타내는 나무 구조를 사용한다.
간단하게 보면 스무고개와 비슷하다.

• 식물인가요?
• 네
• 꽃이 있나요?
• 네
• 장미인가요?
• 네

의사결정나무는 장점이 많다. 이해하고 해석하기가 쉽고, 프로세스가 꽤 명백하다. 숫자형 데이터와 범주형 데이터를 동시에 다룰 수 있고, 특정 변수의 값이 누락되어도 사용할 수 있다.
하지만 학습 데이터에 대한 최적의 의사결정나무를 찾는 것은 무척 어려운 문제이다. 또 의사결정나무는 새로운 데이터에 대한 일반화 성능이 좋지 않아 오버피팅되기 쉽다.
의사결정나무는 크게 범주형 데이터를 반환하는 분류나무(classification tree)와 숫자형 결과를 반환하는 회귀나무(classification tree)로 나누기도 한다.

엔트로피

의사결정나무를 만들기 위해 먼저 어떤 질문을 물을지, 어떤 순서로 질문할지 정해야 한다. 각 질문에는 가능성이 전혀 없는 옵션도 있고 그렇지 않은 옵션도 있다. 예컨데 동물의 다리가 4개일 때 소나 돼지일 수는 있지만 오리일 수는 없다. 모든 질문은 그 답에 따라 남아있는 모든 옵션을 분류시킨다. 그렇기 때문에 예측하려는 대상에 대한 가장 많은 정보를 담은 질문을 고르는 게 좋다. 한편 질문을 던져도 결과값에 대한 새로운 정보를 줄 수 없는 질문은 좋은 질문이 아니다.
여기서 얼마만큼의 정보를 담고 있는가를 엔트로피(entropy)라고 한다. 또 기존의 엔트로피가 무질서도(disorder)를 의미하듯 데이터의 ‘불확실성(uncertainty)’를 의미하기도 한다. (불확실성으로 기억하자.) 예컨데 데이터포인트가 여러 클래스에 고르게 분포된 상황을 불확실성이 높으며 엔트로피가 높다고 한다.
한 데이터 포인트가 클래스 \(c_i\), 클래스에 속할 확률이 \(p_i\)라면 엔트로피는 다음처럼 표시할 수 있다.

모든 \(p_i\)가 0또는 1에 가까우면 엔트로피는 아주 작을 것이고, 데이터가 고르게 분포되어 \(p_i\)가 0과 1의 중간쯤에 있다면 엔트로피는 큰 값을 가진다.

입력데이터는 입력/라벨의 쌍으로 구성되어 각 클래스 레이블의 확률은 별도로 계산해야 한다. 엔트로피를 구할 때는 레이블과 무관하게 확률 값들만 알면 된다.

파티션의 엔트로피

의사결정의 각 질문(단계)는 데이터를 여러 파티션으로 분할한다. (데이터를 여러 개의 작은 셋으로 나눈다.) 예컨데 다리가 2개인가 라는 질문에 대해서 다리가 2개인 동물과 그렇지 않은 동물로 파티션이 분류된다.
데이터셋을 여러 개의 파티션으로 나누더라도 데이터셋 전체의 엔트로피를 계산할 수 있어야 하는데, 파티션 하나 하나가 낮은 엔트로피를 가지면 전체의 엔트로피도 낮아야 하고, 파티션 하나 하나가 높은 엔트로피를 가지면 전체의 엔트로피도 높아야 한다.

따라서 데이터 S를 \(q_1,...,q_m\)의 비율을 갖는 파티션 \(S_1,...,S_m\)로 나누면 엔트로피는 다음과 같이 구할 수 있다.

파티션을 나눌 때 주의할 점도 있다. 다양한 값을 가질 수 있는 변수를 통해 파티션을 나누면 오버피팅으로 인해 엔트로피가 낮아진다. 예를 들어 사용자에 대한 의사결정나무에 사용자 ID를 변수로 사용할 경우 파티션 당 한 사람만이 속하게 돼 엔트로피는 0이지만 새로운 데이터를 처리할 수 없게 된다. 이러한 변수들은 되도록 피하거나, 변수의 값을 다시 나눠 선택 가능한 값의 종류를 줄이는 게 좋다.

의사결정나무 만들기

의사결정남누는 결정 노드(decision node)와 잎 노드(leaf node)로 구성된다. 결정 노드는 질문을 주고 답변에 따라 다른 경로를 안내하며, 잎 노드는 예측값(y)을 알려준다.

• 모든 데이터 포인트의 클래스 레이블이 동일하다면 그 예측값이 해당 클래스 레이블인 잎 노드를 만들고 종료
• 나눌 수 있는 변수가 남아 있지 않으면(스무고개의 질문이 없으면) 가장 빈도 수가 높은 클래스 레이블로 예측하는 잎 노드를 만들고 종류
• 그게 아니면 각 변수로 데이터의 파티션을 나눈다.
• 파티션을 나눴을 때 엔트로피가 가장 나눈 변수를 선택한다.
• 선택된 변수에 대한 결정 노드를 추가한다.
• 남은 변수들로 각 파티션에 대해 위 과정을 반복한다.

이와 같은 방법을 greedy한(탐욕적인) 알고리즘이라고 한다. 왜냐하면 순간순간에 최적이라고 생각되는 선택을 하기 때문이다. 하지만 순간에는 최적이 아닐지어도 나무 전체에 긍정적인 선택이 존재한다.

데이터에 따라 만들어진 의사결정나무는 학습 데이터에 관해서 예측 오류가 0일 수도 있다. 이런 경우 보통 모델이 오버피팅되었다고 해석되므로 말단의 가지를 치는 pruning 과정을 거치기도 한다.

랜덤포레스트

의사결정나무는 오버피팅될 가능성이 높기 때문에 이를 방지할 수 있는 대표적인 방법 중 하나로 랜덤포레스트(random forest)라는 것이 있다. 이는 여러 개의 의사결정나무를 만들고 그들의 다수결로 결과를 선택하는 방법이다.
랜덤포레스트를 구현하기 위해서는 랜덤하게 나무를 얻어야 한다. 이를 위한 한 가지 방법으로 데이터를 bootstrap하는 것이 있다. 데이터가 input일 때 bootstrap_sample(input)의 결과물을 각 나무의 입력으로 넣어 학습시키는 것이다. 이렇게 하면 각 나무가 서로 다른 데이터로 구축돼 랜덤성이 생긴다.

앙상블 방법

두 번째 방법으로 파티션을 나누는 변수에 랜덤성을 부여하는 것이 있다. 모든 변수 중 최적의 변수를 고르는 것이 아닌 일부 변수 중 최적의 변수를 찾는 방법이다. 이런 방법을 앙상블 학습 혹은 앙상블 방법이라고 부르는데, 성능이 떨어지는 (대게 bias가 높고 variance가 낮은 – 언더피팅하는) 여러 모델을 동시에 활용해 전체적으로 성능이 좋은 모델을 구축하는 데에 쓰인다. 앙상블 방법은 인공신경망 등 다른 모델에서도 사용할 수 있으나 의사결정나무처럼 ‘빠른 알고리즘’에 곧잘 쓰인다.

이렇게 구축된 랜덤포레스트는 매우 인기가 많고 두루 쓰이는 알고리즘 중 하나이다.