[ML] 머신러닝 모델: Decision Tree(의사결정나무)

머신러닝의 다양한 모델들 중 하나인 Decision Tree(의사결정 나무)에 대해서 알아보는 시간을 가졌다. 최근 DSC 동아리에서 시행하는 프로젝트로 다양한 머신러닝 용어와 모델들에 대해서 알게 되어 대학교에 들어와서 가장 생산적인 활동이 아니었나 싶다...흑

 

어찌 되었던 우선 많고 어려운 용어를 다 배제시키고 일상적인 단어로 표현한다면 '의사결정 나무 = 스무고개 놀이 ' 라고 보면 될 거 같다. 이래도 이 해가 어렵다면 밑에 그림을 보고 이해해보자! 

 

의사결정 나무 예시

의사결정나무는 분류와 회귀 방법에 모두 적용이 가능하다! 먼저 분류 과정에 대해 말하자면, 새로운 데이터가 특정 teriminal node에 속한다는 정보를 확인하고 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류! 시키는 것입니다.

반면에 회귀는 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 된다. 이 때 예측값의 종류는 terminal node의 갯수와 같다. 

 

<불순도 / 불확실성>

의사결정 나무는 하나의 분기 때마다 변수 영역을 두개로 구분한다. 그렇다면 대체 어떤 기준으로 영역을 나눌까?

분류나무는 구분 뒤 각 영역의 순도(homogeneity)의 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다. 그리고 이러한 이상적인 상태를 정보획득(information gain)이라고도 부른다....이 용어는 참고만 하면 좋겠다. 따라서 이번엔 순도를 계산하는 3가지 방식을 소개하겠다.

 

먼저, 엔트로피 라는 지표이다. 엔트로피는 예를들어서 A영역에 속한 모든 레코드가 동일한 범주에 속할경우 즉, 불확실성이 최소=순도 최대 일때 엔트로피는 0이다. 반면에 범주가 둘뿐이며 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우 즉, 불확실성이 최대=순도 최소 일때 엔트로피는 1의 값을 갖는다.

즉, 엔트로피라는 지표가 0에 가까워지는 것이 의사결정 나무가 제대로 성능을 발휘할 것이라는 결론을 내릴 수 있겠다.

 

<모델학습>

1. 재귀적 분기(Recursive partitioning) ( 소득과 주택크기 = 파라미터 / 소유여부 = 종속변수 )

이후 가능한 모든 분기점에 대해 엔트로피/지니계수를 구해 분기 전과 비교해 정보획득을 조사합니다.

예를들면 1번째 레코드와 2번째부터 나머지 레코드와의 엔트로피와 다음엔 1,2번째 레코드와 3번째부터 나머지 레코드까지의 엔트로피를 비교하면서 뭐가 더좋은지 보고 그렇게 계속적으로 3,4,5,6,.... 진행을한다 ( 그래서 재귀적이라는 이름이 붙은 것 같다) + 참고로 변수의 갯수에 따라 또 그만큼 재귀적 분기를 또 실시해주어야 한다!

 

2. 가지치기(pruning)

모든 terminal node의 순도가 100%(엔트로피가 0)인 상태를 Full tree라고 하는데 이렇게 Full tree를 생성한 뒤

적절한 수준에서 terminal node를 결합(가지치기)를 해주어야 한다. 왜냐면 이것은 분기가 너무 많아서 학습데이터에 과적합을 막기 위한 것이다( 과적합에 대한 구체적인 개념은 저번시간에 다루었다!)

분기 수가 증가할 때 처음에는 새로운 데이터에 대한 오분류(잘못분류)율이 감소하지만 일정 수준 이상이 되면 오분류율이 되레 증가하는 현상(과적합 현상)이 발생한다. ( 즉, 오분률이 갑자기 증가하는 시점=과적합 발생 시점 )

이름 가지치기라 자르는 개념이라고 생각할 수 있지만 실질적으로 수행하는 동작은 합치는 동작이다.

 

<비용 함수(Cost Function)>

 

마지막으로 가지치기의 비용함수(cost functio)를 보자. 의사결정나무는 이 비용함수를 최소로 하는 분기를 찾아내도록 학습된다. 정의는 밑과 같다.

 

* CC(T)=Err(T)+α×L(T)CC(T)=Err(T)+α×L(T)

 

CC(T)=의사결정나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값)

ERR(T)=검증데이터에 대한 오분류율

L(T)=terminal node의 수(구조의 복잡도)

Alpha=ERR(T)와 L(T)를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀)