의사결정 나무 / 정보 이득 / 이득율 / 지니 인덱스

 의사결정 나무(Decision Tree)의 알고리즘 자체는, 누구라도 생각할 수 있을 법한 그런 아이디어입니다. 다만 그 과정 중  '어떤 잣대를 들이밀어 가지를 분기(또는 분할)시킬 것인가'-는 꽤나 고민이 필요한 문제일 겁니다. 어떤 가지가 뻗어나갈 때, 저희는 당연히 뻗어나가는 가지들이 최대한 같은 클래스에 속하는 샘플을 포함하기를 원하겠죠. 이러한 상황을, 저희는 노드의 순도(Purity)가 높다고 말합니다. 가령, 어떤 데이터가 키, 몸무게, 혈액형 등을 특성으로 갖는다면, 키, 몸무게, 혈액형이 노드가 되고, 저희의 목표는 이러한 노드(특성) 중 어떤 놈들을 우선적으로 선택하여 분기를 시작할 것인지, 생각해야하고, 이러한 우선적 선택의 기준의 해당 노드의 순도입니다. 

 이런 순도가 높고 낮음을, 어떻게 선택하는가. 그 기준으로 제시되는 것이 정보 엔트로피(Information entrophy)와 지니값(Gini value)입니다. 정보 엔트로피의 경우, 가장 일반적으로 사용되는 지표인데, 수식은 아래와 같습니다.

자신이 가진 데이터(샘플)에서 각각의 클래스에 대한 비율-을 사용했습니다. 이러한 비율은 당연히 0과 1 사이의 값이고, 이를 -log의 정의역으로 사용했으니, log의 특성(x가 0에 가까워질수록 급격하게 y가 증가한다)을 써먹고자 하는 의도가 보이는 것 같습니다. p값이 클수록, 어떤 클래스에 대한 비율이 굉장히 크다라는 말이니까, 이건 클래스가 몰려있다는 거고, 그럼 이건 순도가 높은걸 의미하겠죠. 그러나 -log니까, 엔트로피값 자체는 작아지게 될겁니다. 정리하면 Ent(D)값이 작을수록 D의 순도는 높아집니다. 쨋든 이를 통해, 정보 이득(Information gain)을 계산할 수 있습니다. 수식은 아래와 같습니다.

 여기서 D는 데이터, 샘플로 보시면되고, a는 어떤 노드, 특성으로 생각하시면 됩니다. 보시면 Ent(D)에서 해당 특성에 속하는 부분집합들에 대한 엔트로피를 빼죠. 앞서 말하길, Ent(D)가 작을수록, D의 순도는 높다고 했었으니, 순도가 높을수록, Gain(D,a)는 커지겠지요. 이를 통해 분기를 시작할 노드를 선택할 수 있습니다. Gain이 높은 노드를 우선 선택하면 되니까요. 다만, 각 노드마다 단 하나의 샘플을 갖는 경우를 생각해보면, 순도가 무조건 최고값을 가지게 되는 것을 알 수 있는데, 이러한 이유로 정보 이득은 일반화 성능이 매우 저조합니다. 때문에 이득율(Gain ration)라는 것을 사용하는데, 수식은 아래와 같습니다.

 정보 이득을 어떤 속성의 내재 값(Intrinsic value)로 나눠줌으로써, 일종의 정규화를 건 것으로 생각해도 좋을 것 같습니다. IV식 자체가 Ent식과 거의 유사하네요. 다만 이경우에는 어떤 속성이 취할수 있는 값의 수가 많아질수록(V가 커질수록), 내재값이 쑥쑥 커져버립니다. 이또한 문제가 되겠지요. 해서 해당 기준을 사용할 경우, 단순히 이득율이 가장 큰 노드를 선택하기보다는, 휴리스틱한 방법을 활용하여, 정보 이득이 평균 수준보다 높은 속성 중 그중 가장 이득율이 높은 것을 선택합니다. 

 이외에, CART Algorithm의 경우 지니값을 이용합니다. 수식은 아래와 같습니다.

 직관적으로, 지니값의 의미는 어떤 데이터에서 임의의 두 샘플을 선택했을 때, 이들이 서로 다른 클래스일 확률을 나타냅니다. 그래서 다른 확률을 다 더하시든지, 전체 확률(=1)에서 같을 확률을 빼시든지 2가지 방법으로 생각하실 수 있습니다. 쨋든, 당연히 이러한 지니값은, 낮을수록 순도가 높은 것입니다. 이를 통해 지니 인덱스(Gini index)를 생각할 수 있습니다. 수식은 아래와 같습니다.

 이 경우, 단순히 지니값을 적당한 비율로 곱해 더했으니, 여전히 낮은 지니 인덱스값이 좋은 순도를 보장하는 셈입니다.

 이러한 기준 외에도 여러 기준들이 존재합니다. 다만 실제로는 이러한 규칙들이 의사결정 트리의 길이에만 영향을 줄 뿐, 일반화 성능에 대해서는 유한한 영향만이 있다는 연구 결과가 있습니다. 뭘 쓰든 사실 거기서 거기였다-라는 셈입니다. 물론 차이가 전혀 없지는 않으나 2% 이내 였다고 하네요. 오히려 추후 설명할 가지치기(Pruning)이 일반화 성능에 더 큰 영향을 끼치며, 데이터에 노이즈가 포함되어 있을 경우, 약 25%의 성능 향상을 노려볼 수 있다고 합니다. 사실 실제 데이터에는 노이즈가 없는 경우를 찾기가 더 어렵다는 것을 생각하면, 가지치기에 더 집중할 필요가 명확하겠습니다.